Gerador de labirintos de caça e matança

O algoritmo Hunt and Kill é, na verdade, uma versão modificada do Recursive Backtracker. A modificação consiste em escanear sistematicamente (ou "caçar") uma nova célula para continuar quando não pode avançar, ao contrário de uma verdadeira pesquisa recursiva, que sempre volta à célula anterior da pilha.

Por causa disso, este algoritmo pode ser facilmente adaptado para gerar labirintos com diferentes aspetos e sensações, apenas optando por entrar no modo "caça" com mais frequência ou de acordo com regras específicas. A versão implementada aqui só entra em modo de "caça" quando não consegue afastar-se da célula atual.

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. É algo 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, escaneia sistematicamente (ou "caça") o labirinto para encontrar uma nova célula a partir daí. O algoritmo consiste em duas fases principais: caminhada e caça.

Como funciona o algoritmo Hunt and Kill para a Geração de Labirintos

Passo 1: Começar numa célula aleatória

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

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

• Escolha um vizinho aleatório não visitado.
• Move-te para esse vizinho, marca-o como visitado e traça um caminho entre a célula anterior e a nova.
• Repete até não haver mais vizinhos por visitar.

Passo 3: Fase de Caça (Retrocesso via Scanning)

• 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 essa célula a um vizinho visitado para retomar a fase de caminhada.
• Repita até que todas as células tenham sido visitadas.

Leitura adicional

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

• Gerador de labirintos do algoritmo de Eller
• Gerador de labirintos do algoritmo de Wilson
• Gerador de labirintos de backtracker recursivo