Gerador de labirintos com algoritmo de árvore em crescimento

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 do tipo fila de espera.

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 Crescente

O algoritmo da Árvore Crescente é 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, tais como o algoritmo de Prim, backtracking recursivo e 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.

Passo 2: Loop de geração do labirinto

• Enquanto a lista de células não estiver vazia:
  • Selecionar uma célula da lista com base numa estratégia específica (explicada abaixo).
  • Criar uma passagem da célula selecionada para um dos seus vizinhos não visitados (escolhido aleatoriamente).
  • Adiciona o vizinho à lista, uma vez que agora faz parte do labirinto.
  • Se a célula selecionada não tiver vizinhos não visitados, remova-a da lista.

Passo 3: Terminaçã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 caraterística que define o algoritmo da Árvore Crescente é a forma como se escolhe a célula a ser processada a seguir. Esta escolha afecta dramaticamente o aspeto do labirinto:

Célula mais recente (comportamento semelhante a uma pilha) - Backtracker recursivo:

• Sempre seleciona 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 aleatório):

• 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 semelhante a uma fila):

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

Abordagens híbridas:

Combinam estratégias para caraterísticas variadas do labirinto. Por exemplo:

• 90% mais recente, 10% aleatório: Parece-se mais com um labirinto de retrocesso recursivo, mas com ramos ocasionais que quebram longos corredores.
• 50% mais novo, 50% mais velho: Equilibra corredores longos com crescimento arbustivo.