Algoritmo para generar laberintos

En términos muy generales, un algoritmo para generar laberintos inicia con un grafo plano en el que cada arista representa una pared, y el objetivo final de dicho algoritmo es encontrar un subgrafo. Dependiendo del grafo inicial y el algoritmo empleado el subgrafo final puede ser un laberinto muy intrincado o uno muy simple.

El siguiente laberinto usa el algoritmo de búsqueda en profundidad y regresión reursiva (depth-first search, recursive backtracker). Selecciona un recuadro para que sea el punto incial del algoritmo y otro para que sea el punto final.

Búsqueda en profundidad

Es un algoritmo muy sencillo e intuitivo, pero a la vez muy ineficiente, que permite recorrer todos los nodos de un grafo. Inicia en un nodo y continua expandiéndose por un camino fijo hacia otros nodos hasta que llega al final del camino, entonces regresa por el camino ya recorrido hasta encontrar otro nodo con al menos una arista adicional para continuar por un camino distinto.

En particular para generar un laberinto el algoritmo inicia en una celda y se mueve a la siguiente borrando la pared que las conecta. Una vez que llega a un punto en el que no puede continuar regresa por el camino ya creado hasta encontrar una celda que tenga al menos una celda adyacente que no ha sido visitada.

Regresión recursiva

Este es un aspecto técnico que evita un desborde de memoria ya que potencialmente el algoritmo antes descrito visitará todas las celdas más de una vez, y mantendrá un registro de las celdas visitadas.

Para hacer las cosas simples se usa una pila o stack. A continuación una descripción general del algoritmo, que además hace muy fácil su implementación.

  1. Convertir la celda inicial en la celda actual y marcarla como visitada.
  2. Mientras queden celdas por visitar
    1. Si la celda actual tiene vecinas que no han sido visitadas
      • Agregar la celda actual a la pila
      • Eliminar la pared entre la celda actual y la celda a visitar
      • Marcar la celda actual como visitada
    2. En caso contrario verificar si la pila no está vacía y
      • Eliminar una celda de la pila
      • Hacer esa celda la celda actual

El caso presentado aquí no es exactamente el algoritmo antes descrito, ya que se establece un punto final en vez de dejar el algoritmo recorriendo todo el espacio disponible. Una vez encontrado un camino entre los dos puntos el algoritmo se ejecuta en las componentes conexas restantes para rellenar esos espacios

Recursos adicionales

Para más información puedes visitar: