Generador de laberintos con algoritmos de crecimiento de árboles

El algoritmo de árbol en crecimiento es interesante porque puede emular el comportamiento de varios otros algoritmos, dependiendo de cómo se elija la siguiente celda durante la generación. La implementación de esta página utiliza un enfoque de tipo cola, que prioriza la amplitud.

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 del árbol en crecimiento

El algoritmo del árbol en crecimiento es un método flexible y potente para generar laberintos perfectos. El algoritmo es interesante porque puede emular el comportamiento de varios otros algoritmos de generación de laberintos, como el algoritmo de Prim, el retroceso recursivo y la división recursiva, según cómo se seleccione la siguiente celda a procesar.

Cómo funciona el algoritmo del árbol en crecimiento

Paso 1: Inicialización

• Comience con una cuadrícula de celdas no visitadas.
• Elija una celda inicial aleatoria y agréguela a una lista.

Paso 2: bucle de generación del laberinto

• Mientras la lista de celdas no esté vacía:
  • Seleccione una celda de la lista según una estrategia específica (explicada a continuación).
  • Crear un pasaje desde la celda seleccionada hasta uno de sus vecinos no visitados (elegidos al azar).
  • Añade al vecino a la lista ya que ahora es parte del laberinto.
  • Si la celda seleccionada no tiene vecinos no visitados, elimínela de la lista.

Paso 3: Terminación

• El algoritmo finaliza cuando ya no hay más celdas en la lista, lo que significa que se ha tallado todo el laberinto.

Estrategias de selección de células (flexibilidad del algoritmo)

La característica que define al algoritmo del árbol en crecimiento es la forma en que se elige qué celda procesar a continuación. Esta elección afecta drásticamente la apariencia del laberinto:

Celda más nueva (comportamiento similar a una pila): Backtracker recursivo:

• Seleccione siempre la celda añadida más recientemente.
• Produce corredores largos y sinuosos con muchos callejones sin salida (como un laberinto de búsqueda en profundidad).
• Los laberintos suelen tener pasajes largos y son fáciles de resolver.

Célula aleatoria (algoritmo aleatorio de Prim):

• Seleccione una celda aleatoria de la lista cada vez.
• Crea un laberinto distribuido más uniformemente con caminos complejos y enredados.
• Menos pasillos largos y más ramificaciones.

Celda más antigua (comportamiento similar a una cola):

• Elija siempre la celda más antigua de la lista.
• Genera laberintos con una distribución más uniforme, como un patrón de búsqueda en amplitud.
• Pasajes cortos y tupidos con densas conexiones.
• (Esta es la versión implementada aquí)

Enfoques híbridos:

Combine estrategias para distintas características del laberinto. Por ejemplo:

• 90% más nuevo, 10% aleatorio: parece más bien un laberinto recursivo, pero con ramas ocasionales que dividen pasillos largos.
• 50% más nuevo, 50% más antiguo: equilibra los pasillos largos con un crecimiento tupido.