Miklix

Algoritmo de Árvore Crescente Gerador de Labirinto

Publicado: 16 de fevereiro de 2025 às 21:37:01 UTC
Última atualização: 6 de março de 2025 às 09:56:23 UTC

Gerador de labirinto usando o algoritmo Growing Tree para criar um labirinto perfeito. Este algoritmo tende a gerar labirintos semelhantes ao algoritmo Hunt and Kill, mas com uma solução típica um pouco diferente.

Esta página foi traduzida automaticamente do inglês para torná-la acessível ao maior número possível de pessoas. Infelizmente, a tradução automática ainda não é uma tecnologia aperfeiçoada, portanto, podem ocorrer erros. Se preferir, você pode visualizar a versão original em inglês aqui:

Growing Tree Algorithm Maze Generator

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.


Gerar novo labirinto








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.

Compartilhe no BlueskyCompartilhe no FacebookCompartilhe no LinkedInCompartilhe no TumblrCompartilhar em XCompartilhe no LinkedInFixar no Pinterest

Mikkel Bang Christensen

Sobre o autor

Mikkel Bang Christensen
Mikkel é o criador e proprietário do miklix.com. Ele tem mais de 20 anos de experiência como programador de computador/desenvolvedor de software profissional e atualmente trabalha em tempo integral para uma grande empresa europeia de TI. Quando não está blogando, ele dedica seu tempo livre a uma grande variedade de interesses, hobbies e atividades, o que pode, até certo ponto, refletir-se na variedade de tópicos abordados neste site.