Gerador de labirintos do algoritmo de Wilson

Algoritmo de Wilson é um método de caminhada aleatória sem laços que gera árvores geradoras uniformes para a criação de labirintos. Isso significa que todos os labirintos possíveis de um determinado tamanho têm a mesma probabilidade de serem gerados, tornando-o uma técnica de geração de labirintos não enviesada. O algoritmo de Wilson pode ser considerado uma versão aprimorada do algoritmo de Aldous-Broder, pois gera labirintos com características idênticas, mas é executado muito mais rapidamente, então não me preocupei em implementar o algoritmo de Aldous-Broder aqui.

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 Wilson

O algoritmo de Wilson para gerar árvores geradoras uniformes usando uma parede aleatória sem laços foi criado por David Bruce Wilson.

Wilson introduziu originalmente este algoritmo em 1996, enquanto pesquisava árvores geradoras aleatórias e cadeias de Markov na teoria da probabilidade. Embora seu trabalho tenha sido principalmente em matemática e física estatística, o algoritmo foi amplamente adotado para geração de labirintos devido à sua capacidade de produzir labirintos perfeitamente uniformes.

Como o algoritmo de Wilson funciona para a geração de labirintos

O algoritmo de Wilson garante que o labirinto final esteja totalmente conectado, sem nenhum loop, criando caminhos iterativamente a partir de células não visitadas por meio de caminhadas aleatórias.

Passo 1: Inicializar

• Comece com uma grade preenchida com paredes.
• Defina uma lista de todas as células de passagem possíveis.

Passo 2: Escolha uma célula inicial aleatória

• Escolha uma célula aleatória e marque-a como visitada. Esta será o ponto de partida do labirinto durante a geração.

Etapa 3: Caminhada Aleatória com Apagamento de Loops

• Escolha uma célula não visitada e inicie uma caminhada aleatória (movendo-se em direções aleatórias).
• Se o percurso chegar a uma célula já visitada, apague quaisquer loops no caminho.
• Assim que o percurso conectar-se à região visitada, marque todas as células no caminho como visitadas.

Passo 4: Repita até que todas as células sejam visitadas:

• Continue selecionando células não visitadas e realizando caminhadas aleatórias até que todas as células façam parte do labirinto.

Leitura adicional

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

• Gerador de labirinto de algoritmo de Eller
• Gerador de labirintos de backtracker recursivo
• Gerador de Labirinto Caçar e Matar