Generador de laberintos del algoritmo de Wilson

El algoritmo de Wilson es un método de recorrido aleatorio sin bucles que genera árboles de expansión uniformes para la creación de laberintos. Esto significa que todos los laberintos posibles de un tamaño determinado tienen la misma probabilidad de generarse, lo que lo convierte en una técnica de generación de laberintos imparcial. El algoritmo de Wilson puede considerarse una versión mejorada del algoritmo de Aldous-Broder, ya que genera laberintos con características idénticas, pero se ejecuta mucho más rápido, por lo que no me he molestado en implementar el algoritmo de Aldous-Broder aquí.

Un laberinto perfecto es un laberinto en el que hay exactamente un camino desde cualquier punto del laberinto a cualquier otro punto. Eso significa que no puedes acabar dando vueltas en círculo, pero a menudo te encontrarás con callejones sin salida que te obligarán a dar media vuelta y volver atrás.

Los mapas de laberintos generados aquí incluyen una versión por defecto sin posiciones de inicio y final, para que puedas decidirlas por ti mismo: habrá una solución desde cualquier punto del laberinto a cualquier otro punto. Si quieres inspirarte, puedes activar una posición inicial y final sugeridas, e incluso ver la solución entre ambas.

Acerca del algoritmo de Wilson

El algoritmo de Wilson para generar árboles de expansión uniformes utilizando una pared aleatoria con bucles borrados fue creado por David Bruce Wilson.

Wilson introdujo originalmente este algoritmo en 1996 mientras investigaba árboles de expansión aleatorios y cadenas de Markov en teoría de probabilidad. Aunque su trabajo se centró principalmente en matemáticas y física estadística, desde entonces el algoritmo ha sido ampliamente adoptado para la generación de laberintos debido a su capacidad para producir laberintos perfectamente uniformes.

Cómo funciona el algoritmo de Wilson para la generación de laberintos

El algoritmo de Wilson garantiza que el laberinto final esté completamente conectado sin bucles, creando iterativamente caminos a partir de celdas no visitadas mediante recorridos aleatorios.

Paso 1: Inicializar

• Comience con una cuadrícula llena de paredes.
• Define una lista de todas las celdas de paso posibles.

Paso 2: Elija una celda inicial aleatoria

• Elige una celda al azar y márcala como visitada. Esto sirve como punto de partida del laberinto durante la generación.

Paso 3: Paseo aleatorio con borrado de bucles

• Elija una celda no visitada y comience una caminata aleatoria (moviéndose en direcciones aleatorias).
• Si la caminata llega a una celda ya visitada, borre cualquier bucle en el camino.
• Una vez que la caminata se conecta a la región visitada, marque todas las celdas de la ruta como visitadas.

Paso 4: Repetir hasta visitar todas las celdas :

• Continúe seleccionando celdas no visitadas y realizando recorridos aleatorios hasta que cada celda sea parte del laberinto.