Generador de laberintos del algoritmo de Eller

El algoritmo de Eller es un algoritmo de generación de laberintos que produce laberintos perfectos de manera eficiente (laberintos sin bucles y con un único camino entre dos puntos cualesquiera) utilizando un enfoque fila por fila. Produce laberintos similares al algoritmo de Kruskal, pero lo hace generando solo una fila a la vez, sin la necesidad de almacenar todo el laberinto en la memoria. Eso lo hace útil para generar laberintos muy grandes en sistemas muy limitados y para la generación de contenido procedimental.

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 de Eller

El algoritmo de Eller fue introducido por David Eller.

El algoritmo se destaca por su eficiente método fila por fila para la generación de laberintos, lo que lo hace ideal para laberintos infinitos o laberintos generados en tiempo real. Se cita con frecuencia en la literatura sobre generación de contenido procedimental y generación de laberintos, pero no he podido encontrar fuentes primarias que detallen su publicación original.

Cómo funciona el algoritmo de Eller para la generación de laberintos

El algoritmo de Eller procesa una fila a la vez, manteniendo y modificando conjuntos de celdas conectadas. Garantiza la conectividad al tiempo que evita los bucles y extiende eficientemente el laberinto hacia abajo.

Teóricamente, se puede utilizar para generar laberintos infinitos, sin embargo, para garantizar que el laberinto generado sea realmente solucionable, es necesario cambiar a la lógica de "fila final" en algún momento para terminar el laberinto.

Paso 1: Inicializar la primera fila

• Asigne a cada celda de la fila un ID de conjunto único.

Paso 2: Unir algunas celdas adyacentes horizontalmente

• Fusionar aleatoriamente celdas adyacentes estableciéndoles el mismo ID de conjunto. Esto garantiza que haya pasajes horizontales.

Paso 3: Crea conexiones verticales con la siguiente fila

• Para cada conjunto que aparece en la fila, al menos una celda debe conectarse hacia abajo (para garantizar la conectividad).
• Seleccione al azar una o más celdas de cada conjunto para conectarlas a la siguiente fila.

Paso 4: Pasar a la siguiente fila

• Continúe las conexiones verticales asignando el mismo ID de conjunto a las celdas correspondientes a continuación.
• Asignar nuevos ID de conjunto a cualquier celda no asignada.

Paso 5: Repita los pasos 2 a 4 hasta llegar a la última fila

• Continúe procesando fila por fila.

Paso 6: Procesar la última fila

• Asegúrese de que todas las celdas de la última fila pertenezcan al mismo conjunto fusionando todos los conjuntos separados restantes.