Gerador de labirintos do algoritmo de Wilson

O algoritmo de Wilson é um método de caminhada aleatória com loop apagado que gera árvores de abrangência uniformes para a criação de labirintos. Isto significa que todos os labirintos possíveis de um determinado tamanho têm a mesma probabilidade de serem gerados, o que a torna 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 é muito mais rápido, pelo que não me dei ao trabalho de implementar aqui o algoritmo de Aldous-Broder.

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 de abrangência uniforme utilizando uma parede aleatória apagada por loop foi criado por David Bruce Wilson.

Wilson introduziu este algoritmo originalmente em 1996 enquanto pesquisava árvores de abrangência aleatória e cadeias de Markov na teoria da probabilidade. Embora o seu trabalho fosse principalmente em matemática e física estatística, o algoritmo foi 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 garante que o labirinto final está totalmente ligado, sem qualquer loop, criando caminhos iterativamente a partir de células não visitadas usando caminhadas aleatórias.

Passo 1: Inicializar

• Comece com uma grelha 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 qualquer e marque-a como visitada. Este serve como ponto de partida do labirinto durante a geração.

Passo 3: Caminhada aleatória com apagamento de loop

• Escolha uma célula não visitada e inicie uma caminhada aleatória (movendo-se em direções aleatórias).
• Se a caminhada chegar a uma célula já visitada, apague quaisquer loops no caminho.
• Assim que a caminhada se ligar à região visitada, marque todas as células 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 realizar caminhadas aleatórias até que todas as células façam parte do labirinto.