Algoritmo de Árvore Crescente Gerador de Labirinto

O algoritmo da Árvore Crescente é 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 usa uma abordagem de busca em largura, semelhante a uma fila.

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 árvore crescente

O algoritmo da Árvore em Crescimento é 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 você seleciona a próxima célula a ser processada.

Como funciona o algoritmo da árvore crescente

Etapa 1: Inicialização

• Comece com uma grade de células não visitadas.
• Escolha uma célula inicial aleatória e adicione-a a uma lista.

Etapa 2: Loop de Geração do Labirinto

• Enquanto a lista de células não estiver vazia: Selecione uma célula da lista com base em uma estratégia específica (explicada abaixo). Abra uma passagem da célula selecionada para uma de suas vizinhas não visitadas (escolhida aleatoriamente). Adicione a vizinha à lista, já que agora ela faz parte do labirinto. Se a célula selecionada não tiver vizinhas não visitadas, remova-a da lista.

Etapa 3: Rescisã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 principal do algoritmo da Árvore em Crescimento é a forma como você escolhe qual célula processar em seguida. Essa escolha afeta drasticamente a aparência do labirinto:

Célula mais recente (comportamento semelhante a uma pilha) – Rastreador de retrocesso recursivo:

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

Célula aleatória (Algoritmo de Prim aleatorizado):

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

Célula mais antiga (comportamento semelhante a uma fila):

• Escolha sempre a célula mais antiga da lista.
• Gera labirintos com uma distribuição mais uniforme, semelhante a um padrão de busca em largura.
• Passagens curtas e arbustivas com densas conexões.
• (Esta é a versão implementada aqui)

Abordagens híbridas:

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

• 90% mais recentes, 10% aleatórios: Parece principalmente um labirinto recursivo com mecânica de backtracking, mas com ramificações ocasionais que interrompem longos corredores.
• 50% mais novas, 50% mais antigas: Equilibra longos corredores com crescimento denso.

Leitura adicional

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

• Gerador de labirintos do algoritmo de Wilson
• Gerador de labirintos do algoritmo de Kruskal
• Gerador de labirinto de algoritmo de Eller