Algoritmo de Árvore Crescente Gerador de Labirinto

O algoritmo Growing Tree é interessante, porque ele 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 fila em largura.

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 da Árvore Crescente

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 você seleciona a próxima célula a ser processada.

Como funciona o algoritmo da árvore em crescimento

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 de 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 um de seus vizinhos não visitados (escolhidos aleatoriamente).
  • Adicione o vizinho à lista, pois agora ele faz parte do labirinto.
  • Se a célula selecionada não tiver vizinhos não visitados, remova-a da lista.

Etapa 3: Término

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

Estratégias de seleção de células (flexibilidade do algoritmo)

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

Célula mais nova (comportamento semelhante a uma pilha) – Backtracker 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).
• Labirintos tendem a ter passagens longas e são fáceis de resolver.

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

• Escolha uma célula aleatória da lista a 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 semelhante a uma fila):

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

Abordagens híbridas:

Combine estratégias para características variadas de labirinto. Por exemplo:

• 90% mais novo, 10% aleatório: parece mais um labirinto de rastreamento recursivo, mas com ramificações ocasionais que quebram corredores longos.
• 50% mais novo, 50% mais antigo: equilibra corredores longos com crescimento espesso.