Gerador de labirintos do algoritmo de Wilson

O algoritmo de Wilson é um método de passeio aleatório apagado por loops que gera árvores uniformes para a criação de labirintos. Isto significa que todos os labirintos possíveis de um dado tamanho têm a mesma probabilidade de serem gerados, tornando-o uma técnica de geração de labirintos imparcial. O algoritmo de Wilson pode ser considerado uma versão melhorada do algoritmo de Aldous-Broder, pois gera labirintos com características idênticas, mas corre muito mais rápido, por isso não me dei ao trabalho de implementar o algoritmo de Aldous-Broder aqui.

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 de Wilson

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

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

Como Funciona o Algoritmo de Wilson para a Geração de Labirintos

O algoritmo de Wilson assegura que o labirinto final está totalmente ligado sem quaisquer ciclos, ao esculpir iterativamente caminhos a partir de células não visitadas usando passeios aleatórios.

Passo 1: Inicializar

• Começa com uma grelha cheia de paredes.
• Defina uma lista de todas as células possíveis de passagem.

Passo 2: Escolha uma Célula Inicial Aleatória

• Escolhe qualquer célula aleatória e marca-a como visitada. Isto serve como ponto de partida do labirinto durante a geração.

Passo 3: Caminhada Aleatória com Apagamento de Loops

• Escolhe uma célula não visitada e começa uma caminhada aleatória (movendo-te em direções aleatórias).
• Se a caminhada chegar a uma cela já visitada, apague quaisquer laços no caminho.
• Quando o percurso se liga à região visitada, assinala todas as celas do percurso como visitadas.

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

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

Leitura adicional

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

• Gerador de labirintos do algoritmo de Kruskal
• Gerador de labirintos de backtracker recursivo
• Gerador de labirintos de caça e matança