Generador de laberintos con retroceso recursivo

El algoritmo de retroceso recursivo es en realidad una búsqueda en profundidad de propósito general. Al usarse para generar laberintos, se modifica ligeramente para elegir la ruta aleatoriamente, mientras que, si se usa para una búsqueda real, normalmente se buscaría en cada nivel en orden lineal. Suele producir laberintos con pasillos largos y sinuosos, y una solución muy larga y sinuosa.

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.

El algoritmo de retroceso recursivo es un método de búsqueda en profundidad para generar laberintos perfectos (laberintos sin bucles y con un único camino entre dos puntos cualesquiera). Es simple, eficiente y produce laberintos visualmente atractivos con pasillos largos y sinuosos.

A pesar de su nombre, no necesariamente tiene que implementarse mediante recursividad. Suele implementarse de forma iterativa mediante una cola LIFO (es decir, una pila). Para laberintos muy grandes, es más probable que la recursividad provoque un desbordamiento de la pila de llamadas, dependiendo del lenguaje de programación y la memoria disponible. Una cola LIFO se adapta más fácilmente al manejo de grandes cantidades de datos, incluso manteniéndola en disco o en una base de datos si la memoria disponible es insuficiente.

Cómo funciona

El algoritmo funciona mediante un enfoque de búsqueda en profundidad basado en pilas. A continuación, se detalla el proceso paso a paso:

1. Seleccione una celda de inicio y márquela como visitada.
2. Mientras haya celdas no visitadas: observe las celdas vecinas que aún no se han visitado. Si existe al menos un vecino no visitado: elija aleatoriamente uno de los vecinos no visitados. Retire la pared entre la celda actual y el vecino elegido. Muévase hasta el vecino elegido y márquelo como visitado. Empuje la celda actual a la pila. Si no existen vecinos no visitados: retroceda sacando la última celda de la pila.
3. Continúe este proceso hasta que la pila esté vacía.

Un dato interesante sobre este algoritmo es que funciona tanto como generador como solucionador de laberintos. Si se ejecuta en un laberinto ya generado y se detiene al llegar al punto final, la pila contendrá la solución.

De hecho, tengo dos versiones de este algoritmo en este sitio: una basada en colas LIFO para generar laberintos en esta página y otra basada en recursión para resolver laberintos, también laberintos generados por otros algoritmos (así es como se crean los mapas con las soluciones). Tener dos versiones diferentes es solo por diversión, porque soy un friki que lo encuentra interesante; cualquiera de las dos podría haber funcionado para ambos ;-)

Lectura adicional

Si te ha gustado esta publicación, puede que también te gusten estas sugerencias:

• Generador de laberintos con algoritmos de crecimiento de árboles
• Generador de laberintos de caza y matanza
• Generador de laberintos del algoritmo de Wilson