Generador de laberintos con retroceso recursivo

El algoritmo de retroceso recursivo es en realidad una búsqueda en profundidad de propósito general. Cuando se utiliza para generar laberintos, se modifica ligeramente para elegir el camino al azar, mientras que si se utiliza para fines de búsqueda reales, normalmente se buscaría en cada nivel en orden lineal. Tiende a producir laberintos con pasillos largos y sinuosos y una solución muy larga y tortuosa.

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). Es simple, eficiente y produce laberintos visualmente atractivos con pasillos largos y sinuosos.

A pesar de su nombre, no necesariamente tiene que implementarse mediante recursión. A menudo se implementa con un enfoque iterativo utilizando una cola LIFO (es decir, una pila). Para laberintos muy grandes, es más probable que el uso de la recursión resulte en un desbordamiento de la pila de llamadas, según el lenguaje de programación y la memoria disponible. Una cola LIFO se puede adaptar más fácilmente para manejar grandes cantidades de datos, incluso manteniendo la cola en el 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 muestra el desglose paso a paso:

1. Seleccione una celda de inicio y márquela como visitada.
2. Mientras haya celdas no visitadas:
   • Mira las celdas vecinas que aún no han sido visitadas.
   • Si existe al menos un vecino no visitado:
     • Elige al azar uno de los vecinos no visitados.
     • Eliminar la pared entre la celda actual y la vecina elegida.
     • Muévete hasta el vecino elegido y márcalo como visitado.
     • Empuja la celda actual hacia la pila.
   • Si no existen vecinos no visitados:
     • Retroceda haciendo estallar 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 de laberintos como solucionador de laberintos. Si lo ejecutas en un laberinto ya generado y simplemente te detienes cuando llegas al punto final decidido, la pila contendrá la solución del laberinto.

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