¿Cuál es un buen algoritmo para generar un laberinto?

https://stackoverflow.com/questions/38502

09-06-2019
|

Pregunta

Supongamos que desea un laberinto simple en una cuadrícula de N por M, con un camino y un buen número de callejones sin salida, pero que parece "correcto" (es decir,como si alguien lo hubiera hecho a mano sin demasiados pequeños callejones sin salida y todo eso).¿Existe alguna forma conocida de hacer esto?

Solución

De http://www.astrolog.org/labyrnth/algrithm.htm

Retroceso recursivo:Esto está algo relacionado con el método de resolución de retroceso recursivo que se describe a continuación y requiere una acumulación del tamaño del Laberinto.Al tallar, sea lo más codicioso posible y siempre talle en una sección sin hacer si hay una al lado de la celda actual.Cada vez que te mueves a una nueva celda, empuja la celda anterior en la pila.Si no hay celdas sin crear junto a la posición actual, coloque la pila en la posición anterior.El Laberinto estará listo cuando saques todo de la pila.Este algoritmo da como resultado laberintos con un factor de "río" tan alto como sea posible, con menos callejones sin salida pero más largos y, por lo general, una solución muy larga y sinuosa.Funciona bastante rápido, aunque el algoritmo de Prim es un poco más rápido.El retroceso recursivo no funciona como un sumador de muros, porque al hacerlo tiende a dar como resultado un camino de solución que sigue el borde exterior, donde todo el interior del Laberinto está unido al límite mediante un solo tallo.

Producen sólo un 10% de callejones sin salida.

es un ejemplo de un laberinto generado por ese método.

Otros consejos

Resulta que existen 12 algoritmos clásicos para generar laberintos "perfectos".Un laberinto es perfecto si tiene una, y sólo una, solución.Aquí hay algunos enlaces a cada algoritmo, en el orden aproximado de mi preferencia.

Para más información, consulte mazelib en GitHub, una biblioteca de Python que implementa todos los algoritmos estándar de generación/resolución de laberintos.

Una solución bastante sencilla podría ser asignar pesos aleatorios a los bordes del gráfico y aplicar algoritmo de Kruskal para encontrar un árbol de expansión mínimo.

La mejor discusión jamás realizada sobre algoritmos de generación de laberintos: http://www.jamisbuck.org/presentations/rubyconf2011/index.html (estuvo en HN hace un par de días).

Curiosamente, cambiando ligeramente las reglas "canónicas" y partiendo de una configuración aleatoria, El juego de la vida de Conway ¡Parece generar laberintos bastante bonitos!

(No recuerdo la regla exacta, pero es una modificación muy simple que tiende a 'densificar' la población de células...)

Mi forma favorita es usar el algoritmo de Kruskal, pero cuando elijo aleatoriamente un borde para eliminar, pondera la elección según los tipos de bordes a los que está conectado.

Al variar los pesos para diferentes tipos de bordes, puedes generar laberintos con muchas características o "personalidades" distintas.Vea mi ejemplo aquí:

https://mtimmerm.github.io/webStuff/maze.html

Uno de los métodos para generar un laberinto es la versión aleatoria del algoritmo de Prim.

Comience con una cuadrícula llena de paredes.Elige una celda y márcala como parte del laberinto.Agregue las paredes de la celda a la lista de paredes.Si bien hay muros en la lista:

Elija una pared aleatoria de la lista.Si la celda del lado opuesto aún no está en el laberinto:

(i) Haga de la pared un pasaje y marque la celda en el lado opuesto como parte del laberinto.

(ii) Agregue las paredes vecinas de la celda a la lista de paredes.

Si la celda del lado opuesto ya estaba en el laberinto, elimina la pared de la lista.

Para mayor comprensión haga clic aquí

Aquí está el algoritmo DFS escrito como pseudocódigo:

crear un CellStack (LIFO) para contener una lista de ubicaciones de celdas
establecer TotalCells = número de celdas en la cuadrícula
elige una celda al azar y llámala CurrentCell
establecer celdas visitadas = 1

Mientras que las células visitadas <Totalcells encuentran a todos los vecinos de CurrentCell con todas las paredes intactas
Si uno o más se encuentra elige uno al azar
derribar la pared entre él y CurrentCell
empujar la ubicación de CurrentCell en CellStack
hacer que la nueva celda sea CurrentCell
Agregue 1 a las células visitadas que se encuentren la entrada de celda más reciente en el Cellstack
Hazlo CurrentCell endif

Licenciado bajo: CC-BY-SA con atribución

No afiliado a StackOverflow