Generador de laberints d'algoritmes de Wilson

L'algoritme de Wilson és un mètode de passejada aleatòria amb esborrat de bucles que genera arbres d'expansió uniformes per a la creació de laberints. Això significa que tots els laberints possibles d'una mida determinada tenen la mateixa probabilitat de ser generats, convertint-lo en una tècnica de generació de laberints imparcial. L'algoritme de Wilson es pot considerar una versió millorada de l'algoritme d'Aldous-Broder, ja que genera laberints amb característiques idèntiques, però s'executa molt més ràpid, per la qual cosa no m'he molestat a implementar l'algoritme 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

L'algoritme de Wilson per generar arbres d'expansió uniformes utilitzant una paret aleatòria esborrada per bucles va ser creat per David Bruce Wilson.

Wilson va introduir originalment aquest algorisme el 1996 mentre investigava els arbres d'expansió aleatoris i les cadenes de Markov en la teoria de la probabilitat. Tot i que el seu treball es va centrar principalment en les matemàtiques i la física estadística, l'algoritme ha estat àmpliament adoptat des de llavors 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 garanteix que el laberint final estigui completament connectat sense bucles mitjançant la creació de camins iteratius a partir de cel·les no visitades mitjançant passejades aleatòries.

Pas 1: Inicialitzar

• Comença amb una quadrícula plena de parets.
• Defineix una llista de totes les cel·les de passatge 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 d'inici del laberint durant la generació.

Pas 3: Caminada aleatòria amb esborrat de bucles

• Trieu una cel·la no visitada i comenceu un passeig aleatori (movent-vos en direccions aleatòries).
• Si la caminada arriba a una cel·la ja visitada, esborra qualsevol bucle del camí.
• Un cop la caminada es 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 fent passejades aleatòries fins que totes les cel·les formin part del laberint.

Lectures addicionals

Si t'ha agradat aquesta publicació, també et poden agradar aquests suggeriments:

• Generador de laberints d'algoritmes de Kruskal
• Generador de laberints d'algoritmes d'arbres en creixement
• Generador de laberints d'algoritmes d'Eller