Generador de laberintos con algoritmos de crecimiento de árboles

El algoritmo de Árbol Creciente 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 amplitud, similar al de las colas.

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 Creciente es un método flexible y potente para generar laberintos perfectos. Su interés radica en que puede emular el comportamiento de otros algoritmos de generación de laberintos, como el algoritmo de Prim, el retroceso recursivo y la división recursiva, dependiendo de 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). Cree un pasaje desde la celda seleccionada hasta uno de sus vecinos no visitados (elegidos al azar). Agregue el 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 quedan celdas en la lista, lo que significa que se ha tallado todo el laberinto.

Estrategias de selección celular (flexibilidad del algoritmo)

La característica distintiva del algoritmo del Árbol Creciente es cómo se elige la celda que se procesará a continuación. Esta elección afecta drásticamente la apariencia del laberinto:

Celda más reciente (comportamiento similar a una pila): Retroceso recursivo:

• Seleccione siempre la celda agregada 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 de Prim aleatorio):

• Elija 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, tupidos y con densas conexiones.
• (Esta es la versión implementada aquí)

Enfoques híbridos:

Combina 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 pasillos largos con crecimiento tupido.

Lectura adicional

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

• Generador de laberintos del algoritmo de Eller
• Generador de laberintos del algoritmo de Wilson
• Generador de laberintos de caza y matanza