Algoritmo de generación de laberintos

Este algoritmo, también conocido como algoritmo de "retroceso recursivo", es una versión aleatoria del algoritmo de búsqueda en profundidad .

Este método, frecuentemente implementado con una pila , es una de las formas más sencillas de generar un laberinto mediante una computadora. Imaginemos que el espacio del laberinto es una gran cuadrícula de celdas (como un tablero de ajedrez gigante), donde cada celda comienza con cuatro paredes. Partiendo de una celda aleatoria, la computadora selecciona una celda vecina aleatoria que aún no ha sido visitada. Elimina la pared entre las dos celdas, marca la nueva celda como visitada y la agrega a la pila para facilitar el retroceso. La computadora continúa este proceso, considerando una celda sin vecinos sin visitar como un callejón sin salida. Al llegar a un callejón sin salida, retrocede por el camino hasta encontrar una celda con un vecino sin visitar, continuando la generación del camino al visitar esta nueva celda (creando una nueva unión). Este proceso continúa hasta que todas las celdas hayan sido visitadas, lo que provoca que la computadora retroceda hasta la celda inicial. De esta manera, nos aseguramos de que todas las celdas sean visitadas.

Como se indicó anteriormente, este algoritmo implica una recursión profunda que puede causar problemas de desbordamiento de pila en algunas arquitecturas informáticas. El algoritmo se puede reorganizar en un bucle almacenando la información de retroceso en el propio laberinto. Esto también proporciona una forma rápida de mostrar una solución, comenzando en cualquier punto y retrocediendo hasta el inicio.

Los laberintos generados mediante una búsqueda en profundidad tienen un bajo factor de ramificación y contienen muchos pasillos largos, porque el algoritmo explora lo más lejos posible a lo largo de cada rama antes de retroceder.

Este algoritmo es una versión aleatoria del algoritmo de Kruskal .

1. Crea una lista de todas las paredes y crea un conjunto para cada celda, cada uno de los cuales contendrá solo esa celda.
2. Para cada pared, en algún orden aleatorio:
   1. Si las celdas divididas por esta pared pertenecen a conjuntos distintos:
      1. Retire la pared actual.
      2. Une los conjuntos de las celdas que antes estaban divididas.

Existen varias estructuras de datos que se pueden utilizar para modelar los conjuntos de celdas. Una implementación eficiente que utiliza una estructura de datos de conjuntos disjuntos puede realizar cada operación de unión y búsqueda en dos conjuntos en un tiempo amortizado casi constante (específicamente,${\displaystyle O(\alpha (V))}$tiempo;${\displaystyle \alpha (x)<5}$para cualquier valor plausible de${\displaystyle x}$), por lo que el tiempo de ejecución de este algoritmo es esencialmente proporcional al número de paredes disponibles en el laberinto.

Da igual si la lista de paredes se genera inicialmente de forma aleatoria o si se elige una pared al azar de una lista no aleatoria; en ambos casos, es igual de fácil programarlo.

Debido a que el efecto de este algoritmo es producir un árbol de expansión mínima a partir de un grafo con aristas de igual peso, tiende a producir patrones regulares que son bastante fáciles de resolver.

Este algoritmo es una versión aleatoria del algoritmo de Prim .

1. Comienza con una cuadrícula llena de paredes.
2. Selecciona una celda y márcala como parte del laberinto. Agrega las paredes de la celda a la lista de paredes.
3. Si bien hay muros en la lista:
   1. Elige una pared al azar de la lista.
   2. Si solo se visita una de las células que divide la pared, entonces:
      1. Convierte la pared en un pasaje y marca la celda no visitada como parte del laberinto.
      2. Añade las paredes vecinas de la celda a la lista de paredes.
   3. Elimina la pared de la lista.

Cabe destacar que aplicar el algoritmo clásico de Prim a un grafo con pesos de aristas aleatorios generaría laberintos estilísticamente idénticos a los de Kruskal, ya que ambos son algoritmos de árbol de expansión mínima. En cambio, este algoritmo introduce variación estilística porque las aristas más cercanas al punto de partida tienen un peso efectivo menor.

Todos los algoritmos anteriores tienen sesgos de diversa índole: la búsqueda en profundidad está sesgada hacia los pasillos largos, mientras que los algoritmos de Kruskal/Prim están sesgados hacia muchos callejones sin salida cortos. El algoritmo de Wilson, ^{[ 1 ]} por otro lado, genera una muestra no sesgada de la distribución uniforme sobre todos los laberintos, utilizando caminatas aleatorias sin bucles .

El algoritmo comienza inicializando el laberinto con una celda elegida al azar. A continuación, partimos de una nueva celda, también elegida al azar, y realizamos un recorrido aleatorio hasta llegar a una celda que ya se encuentre en el laberinto. Sin embargo, si en algún momento el recorrido aleatorio alcanza su propio camino, formando un bucle, eliminamos dicho bucle antes de continuar. Cuando el bucle llega al laberinto, lo añadimos a este. Luego, realizamos otro recorrido aleatorio, eliminando el bucle, desde otra celda de inicio arbitraria, repitiendo el proceso hasta que todas las celdas estén ocupadas.

Este procedimiento se mantiene imparcial independientemente del método que utilicemos para elegir arbitrariamente las celdas iniciales. Por lo tanto, para simplificar, siempre podríamos elegir la primera celda vacía, por ejemplo, de izquierda a derecha y de arriba abajo.

El algoritmo de Aldous-Broder también produce árboles de expansión uniformes. Sin embargo, es uno de los algoritmos de laberintos menos eficientes. ^{[ 2 ]}

1. Seleccione una celda al azar como celda actual y márquela como visitada.
2. Mientras haya celdas no visitadas:
   1. Elige un vecino al azar.
   2. Si no se ha visitado al vecino elegido:
      1. Elimina la pared que separa la celda actual de la celda vecina elegida.
      2. Marca al vecino elegido como visitado.
   3. Establezca al vecino elegido como la celda actual.

Los laberintos se pueden crear mediante división recursiva , un algoritmo que funciona de la siguiente manera: Se comienza con el espacio del laberinto sin paredes. A esto se le llama cámara. Se divide la cámara con una pared (o varias paredes) colocadas aleatoriamente, donde cada pared contiene una abertura de pasaje también colocada aleatoriamente. Luego, se repite el proceso recursivamente en las subcámaras hasta que todas tengan el tamaño mínimo. Este método da como resultado laberintos con paredes largas y rectas que atraviesan el espacio, lo que facilita identificar las áreas que se deben evitar.

Por ejemplo, en un laberinto rectangular, construya dos paredes perpendiculares entre sí en puntos aleatorios. Estas dos paredes dividen la cámara grande en cuatro cámaras más pequeñas separadas por cuatro paredes. Elija tres de las cuatro paredes al azar y abra un agujero de una celda de ancho en un punto aleatorio de cada una de ellas. Continúe de esta manera recursivamente hasta que cada cámara tenga un ancho de una celda en cualquiera de las dos direcciones.

Esta es una forma sencilla y rápida de generar un laberinto. ^{[ 3 ]}

En cada iteración, este algoritmo crea un laberinto del doble de tamaño copiándose a sí mismo 3 veces. Al final de cada iteración, se abren 3 caminos entre los 4 laberintos más pequeños.

La ventaja de este método es su rapidez. La desventaja es que no permite obtener un laberinto del tamaño deseado, pero existen diversos trucos para sortear este problema .