Generador de laberints d'algoritmes de Wilson

L'algorisme de Wilson és un mètode de caminada aleatòria esborrada en bucle que genera arbres uniformes per a la creació de laberints. Això significa que tots els laberints possibles d'una mida determinada tenen la mateixa probabilitat de generar-se, la qual cosa la converteix en una tècnica de generació de laberints imparcial. L'algoritme de Wilson es pot considerar una versió millorada de l'algorisme d'Aldous-Broder, ja que genera laberints amb característiques idèntiques, però s'executa molt més ràpid, així que no m'he molestat en implementar l'algorisme d'Aldous-Broder aquí.

Un laberint perfecte és un laberint en el qual hi ha exactament un camí des de qualsevol punt del laberint fins a qualsevol altre punt. Això vol dir que no pots acabar donant voltes, però sovint et trobaràs amb carrerons sense sortida, obligant-te a donar la volta i tornar enrere.

Els mapes de laberint generats aquí inclouen una versió predeterminada sense cap posició d'inici i d'arribada, de manera que les podeu decidir vosaltres mateixos: hi haurà una solució des de qualsevol punt del laberint fins a qualsevol altre punt. Si voleu inspiració, podeu activar una posició d'inici i d'arribada suggerida, i fins i tot veure la solució entre les dues.

Sobre l'algoritme de Wilson

David Bruce Wilson va crear l'algoritme de Wilson per generar arbres que abasten uniformes mitjançant un mur aleatori esborrat en bucle.

Wilson va introduir originalment aquest algorisme l'any 1996 mentre investigava arbres d'abast aleatori i cadenes de Markov en teoria de probabilitats. Tot i que el seu treball va ser principalment en matemàtiques i física estadística, l'algoritme ha estat àmpliament adoptat per a la generació de laberints a causa de la seva capacitat per produir laberints perfectament uniformes.

Com funciona l'algoritme de Wilson per a la generació de laberints

L'algoritme de Wilson assegura que el laberint final estigui completament connectat sense cap bucle tallant de manera iterativa camins a partir de cel·les no visitades mitjançant caminades aleatòries.

Pas 1: inicialitzar

• Comenceu amb una quadrícula plena de parets.
• Definiu una llista de totes les cel·les de pas possibles.

Pas 2: trieu una cel·la inicial aleatòria

• Trieu qualsevol cel·la aleatòria i marqueu-la com a visitada. Això serveix com a punt de partida del laberint durant la generació.

Pas 3: caminada aleatòria amb esborrat de bucles

• Trieu una cel·la no visitada i comenceu a caminar aleatòriament (movint-vos en direccions aleatòries).
• Si la caminada arriba a una cel·la ja visitada, esborra qualsevol bucle del camí.
• Un cop la caminada connecti amb la regió visitada, marqueu totes les cel·les del camí com a visitades.

Pas 4: repetiu fins que es visitin totes les cel·les :

• Continueu seleccionant cel·les no visitades i realitzant caminades aleatòries fins que cada cel·la sigui part del laberint.