Miklix

Gerador de labirintos com algoritmo de árvore em crescimento

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

Gerador de labirintos que usa 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 a tornar acessível ao maior número possível de pessoas. Infelizmente, a tradução automática ainda não é uma tecnologia aperfeiçoada, pelo que podem ocorrer erros. Se preferir, pode ver a versão original em inglês aqui:

Growing Tree Algorithm Maze Generator

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.


Gerar novo labirinto








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.

Partilhar no BlueskyPartilhar no FacebookPartilhar no LinkedInPartilhar no TumblrPartilhar em XPartilhar no LinkedInFixar no Pinterest

Mikkel Bang Christensen

Sobre o autor

Mikkel Bang Christensen
Mikkel é o criador e proprietário do miklix.com. Tem mais de 20 anos de experiência como programador informático/desenvolvedor de software profissional e trabalha atualmente a tempo inteiro para uma grande empresa europeia de TI. Quando não está a escrever no blogue, dedica o seu tempo livre a um vasto leque de interesses, passatempos e actividades, que podem, em certa medida, refletir-se na variedade de tópicos abordados neste sítio Web.