Gerador de labirintos de caça e matança

O algoritmo Hunt and Kill é na realidade uma versão modificada do Recursive Backtracker. A modificação consiste em digitalizar (ou "caçar") sistematicamente uma nova célula para continuar a partir do momento em que não é possível prosseguir, ao contrário de uma verdadeira pesquisa recursiva, que regressará sempre à célula anterior na pilha.

Por este motivo, este algoritmo pode ser facilmente adaptado para gerar labirintos com aspeto e comportamento diferentes, bastando para isso optar por entrar no modo "caça" com maior frequência ou de acordo com regras específicas. A versão aqui implementada só entra no modo "caça" quando não consegue ir mais longe da célula actual.

Um labirinto perfeito é um labirinto em que existe exatamente um caminho de qualquer ponto do labirinto para qualquer outro ponto. Isto significa que não pode acabar por andar em círculos, mas encontrará frequentemente becos sem saída, obrigando-o a dar meia volta e regressar.

Os mapas de labirinto gerados aqui incluem uma versão predefinida sem posições de início e fim, para que possas decidir por ti próprio: haverá uma solução de qualquer ponto do labirinto para qualquer outro ponto. Se quiseres inspiração, podes ativar uma posição de início e de fim sugerida - e até ver a solução entre as duas.

Sobre o Algoritmo de Caça e Morte

O algoritmo Hunt and Kill é um método simples, mas eficaz, para gerar labirintos. É um pouco semelhante a uma pesquisa em profundidade (ou seja, o algoritmo Recursive Backtracker), exceto que, quando não consegue ir mais longe da posição atual, varre (ou "caça") sistematicamente o labirinto para encontrar uma nova célula para prosseguir. O algoritmo é constituído por duas fases principais: caminhada e caça.

Como funciona o algoritmo Hunt and Kill para a geração de labirintos

Passo 1: Comece numa célula aleatória

• Encontre uma célula aleatória na grelha e marque-a como visitada.

Etapa 2: Fase de caminhada (caminhada aleatória)

• Escolha um vizinho aleatório não visitado.
• Vá até esse vizinho, marque-o como visitado e crie um caminho entre a célula anterior e a nova.
• Repita até que não haja mais vizinhos não visitados.

Etapa 3: Fase de caça (retrocesso via varrimento)

• Analise a grelha linha a linha (ou coluna a coluna).
• Encontre a primeira célula não visitada que tenha pelo menos um vizinho visitado.
• Ligue esta célula a um vizinho visitado para retomar a fase de caminhada.
• Repita até que todas as células tenham sido visitadas.