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 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 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 roda muito mais rápido, então não me incomodei 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 de abrangência uniforme usando uma parede aleatória apagada por loop foi criado por David Bruce Wilson.

Wilson introduziu esse algoritmo originalmente em 1996 enquanto pesquisava árvores de abrangência aleatória e cadeias de Markov em teoria de probabilidade. Embora seu trabalho fosse 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 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 usando caminhadas aleatórias.

Etapa 1: Inicializar

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

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

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

Etapa 3: Caminhada aleatória com apagamento de loop

• Escolha uma célula não visitada e comece 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.
• Depois que a caminhada se conectar à região visitada, marque todas as células no caminho como visitadas.

Etapa 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.