Gerador de labirintos com algoritmo de árvore em crescimento

O algoritmo Growing Tree é interessante, porque pode emular o comportamento de vários outros algoritmos, dependendo de como a próxima célula é escolhida durante a geração. A implementação nesta página utiliza uma abordagem de largura em frente, semelhante a uma fila.

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 da Árvore em Crescimento

O algoritmo Growing Tree é um método flexível e poderoso para gerar labirintos perfeitos. O algoritmo é interessante porque pode emular o comportamento de vários outros algoritmos de geração de labirintos, como o algoritmo de Prim, o backtracking recursivo e a divisão recursiva, dependendo de como se seleciona a próxima célula a processar.

Como Funciona o Algoritmo da Árvore em Crescimento

Passo 1: Inicialização

• Comece com uma grelha de células não visitadas.
• Escolhe uma célula inicial aleatória e adiciona-a a uma lista.

Passo 2: Ciclo de Geração de Labirinto

• Enquanto a lista de células não estiver vazia: Selecione uma célula da lista com base numa estratégia específica (explicada abaixo). Esculpir uma passagem da célula selecionada para uma das suas vizinhas não visitadas (escolhidas aleatoriamente). Adiciona o vizinho à lista, já que agora faz parte do labirinto. Se a célula selecionada não tiver vizinhos não visitados, remova-a da lista.

Passo 3: Rescisão

• O algoritmo termina quando não há mais células na lista, o que significa que todo o labirinto foi esculpido.

Estratégias de Seleção de Células (Flexibilidade do Algoritmo)

A característica definidora do algoritmo Growing Tree é como escolhe qual célula processar a seguir. Esta escolha afeta dramaticamente a aparência do labirinto:

Célula Mais recente (Comportamento semelhante a uma pilha) – Retrocesso Recursivo:

• Selecione sempre a célula adicionada mais recentemente.
• Produz corredores longos e sinuosos com muitos becos sem saída (como um labirinto de busca em profundidade).
• Os labirintos tendem a ter passagens longas e são fáceis de resolver.

Célula aleatória (algoritmo de Prim randomizado):

• Escolhe uma célula aleatória da lista de cada vez.
• Cria um labirinto mais uniformemente distribuído, com caminhos complexos e emaranhados.
• Menos corredores longos e mais ramificações.

Célula mais antiga (Comportamento em fila):

• Escolhe sempre a célula mais antiga da lista.
• Gera labirintos com uma dispersão mais uniforme, como um padrão de pesquisa em largura.
• Passagens curtas e espessas com ligações densas.
• (Esta é a versão implementada aqui)

Abordagens Híbridas:

Combine estratégias para diferentes características do labirinto. Por exemplo:

• 90% mais recente, 10% aleatório: Parece sobretudo um labirinto recursivo de backtracking, mas com ramificações ocasionais que interrompem longos corredores.
• 50% mais recente, 50% mais antiga: Equilibra corredores longos com crescimento denso.

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 Kruskal
• Gerador de labirintos de caça e matança