algorithm - code - algoritmo para generar laberintos

¿Qué es un buen algoritmo para generar un laberinto? (7)

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

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

mientras que VisitedCells <TotalCells encuentra a todos los vecinos de CurrentCell con todas las paredes intactas
si uno o más encontraron, eligen uno al azar
derribar la pared entre él y CurrentCell
presionar la ubicación de CurrentCell en CellStack
hacer la nueva celda CurrentCell
agregue 1 a VisitedCells else haga estallar la entrada de celda más reciente fuera de CellStack
que sea CurrentCell endIf endWhile

Supongamos que quiere un laberinto simple en una cuadrícula N por M, con un camino correcto y un buen número de callejones sin salida, pero que se ve "bien" (es decir, como alguien lo hizo a mano sin demasiados callejones sin salida y todo eso ) ¿Hay alguna manera conocida de hacer esto?

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

Retrotractor recursivo: Esto está relacionado de alguna manera con el método recursivo de resolución de rastreos descrito a continuación, y requiere apilar hasta el tamaño del Laberinto. Al tallar, sea lo más codicioso posible, y siempre corte en una sección sin hacer si está al lado de la celda actual. Cada vez que te muevas a una nueva celda, presiona la celda anterior en la pila. Si no hay celdas deshechas junto a la posición actual, saque la pila a la posición anterior. El laberinto termina cuando sacas todo de la pila. Este algoritmo da como resultado laberintos con un factor de "río" lo más alto posible, con un menor número de puntos muertos pero más largos, y generalmente una solución muy larga y sinuosas. 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 pared, porque al hacerlo tiende a dar lugar a una ruta de solución que sigue al borde exterior, donde todo el interior del Laberinto está unido al límite por un solo vástago.

Producen solo un 10% de callejones sin salida

http://www.astrolog.org/labyrnth/sample/recursiv.gif

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

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

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

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

Comience con una grilla llena de paredes. Elige una celda, márcala como parte del laberinto. Agrega las paredes de la celda a la lista de la pared. Si bien hay paredes en la lista:

Elige un muro al azar de la lista. Si la celda del lado opuesto aún no está en el laberinto:

(i) Haz que la pared sea un pasaje y marca la celda del lado opuesto como parte del laberinto.

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

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

Para obtener más información, haga clic aquí

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

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

Por extraño que parezca, cambiando ligeramente las reglas "canónicas" y comenzando desde una configuración aleatoria, el Juego de la vida de Conway parece generar laberintos bastante agradables.

(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 utilizar el algoritmo de Kruskal, pero al elegir aleatoriamente y eliminar el borde, pondere la elección en función de los tipos de bordes a los que está conectado.

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

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