Gerador de Labirinto Caçar e Matar

O algoritmo Hunt and Kill é, na verdade, uma versão modificada do Recursive Backtracker. A modificação consiste em escanear (ou "caçar") sistematicamente uma nova célula para continuar a partir dela quando não for possível prosseguir, em oposição a uma busca recursiva verdadeira, que sempre retornará à célula anterior na pilha.

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

Um labirinto perfeito é um labirinto em que há exatamente um caminho de qualquer ponto do labirinto para qualquer outro ponto. Isso significa que você não pode acabar andando em círculos, mas frequentemente encontrará becos sem saída, forçando-o a dar meia-volta e retornar.

Os mapas de labirinto gerados aqui incluem uma versão padrão sem posições de início e fim, para que você possa decidir por si mesmo: haverá uma solução de qualquer ponto do labirinto para qualquer outro ponto. Se quiser se inspirar, você pode ativar uma sugestão de posição inicial e final e até mesmo ver a solução entre as duas.

Sobre o algoritmo de caça e eliminação

O algoritmo Hunt and Kill é um método simples, porém eficaz, para gerar labirintos. É semelhante a uma busca em profundidade (ou seja, o algoritmo Recursive Backtracker), exceto que, quando não consegue avançar a partir da posição atual, ele percorre sistematicamente (ou "caça") o labirinto para encontrar uma nova célula a partir da qual prosseguir. O algoritmo consiste em duas fases principais: caminhada e caça.

Como funciona o algoritmo de caça e eliminação para a geração de labirintos

Passo 1: Comece em uma célula aleatória.

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

Etapa 2: Fase de Caminhada (Caminhada Aleatória)

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

Etapa 3: Fase de Busca (Rastreamento reverso por meio de varredura)

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

Leitura adicional

Se você gostou deste post, você também pode gostar destas sugestões:

• Algoritmo de Árvore Crescente Gerador de Labirinto
• Gerador de labirintos do algoritmo de Kruskal
• Gerador de labirintos do algoritmo de Wilson