Gerador de Labirinto Caçar e Matar
Publicado: 16 de fevereiro de 2025 às 20:56:18 UTC
Gerador de labirinto que usa o algoritmo Hunt and Kill para criar um labirinto perfeito. Esse algoritmo é semelhante ao Recursive Backtracker, mas tende a gerar labirintos com corredores um pouco menos longos e sinuosos.Hunt and Kill Maze Generator
O algoritmo Hunt and Kill é, na verdade, uma versão modificada do Recursive Backtracker. A modificação consiste na busca sistemática (ou "caça") de uma nova célula para continuar quando não for possível ir além, em vez de uma busca recursiva verdadeira, que sempre voltará à célula anterior na pilha.
Por esse motivo, esse algoritmo pode ser facilmente adaptado para gerar labirintos com aparência e sensação diferentes, bastando optar por entrar no modo de "caça" com mais frequência ou de acordo com regras específicas. A versão implementada aqui só entra no modo de "caça" quando não é possível ir além 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 Hunt and Kill
O algoritmo Hunt and Kill é um método simples, porém eficaz, para gerar labirintos. Ele é um pouco semelhante a uma busca em profundidade (ou seja, o algoritmo Recursive Backtracker), exceto pelo fato de que, quando não é possível ir além da posição atual, ele faz uma varredura sistemática (ou "caça") no labirinto para encontrar uma nova célula para prosseguir. O algoritmo consiste em duas fases principais: caminhar e caçar.
Como o algoritmo Hunt and Kill funciona para a geração de labirintos
Etapa 1: Iniciar 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 não visitado.
- Mova-se para 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 por meio de varredura)
- Examine 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 até que todas as células tenham sido visitadas.