¿Qué algoritmo has usado en el pasado para generar un laberinto 2D simple?
algorithm
procedural-generation
jdeseno
fuente
fuente
Prefiero los laberintos apretados que crea el algoritmo de Kruskal.
La descripción estándar del Algoritmo de Kruskal es inapropiada ya que no distingue las ubicaciones en el gráfico de los grupos de ubicaciones, al tiempo que se basa en un juego de palabras sobre la elección de la estructura de datos, lo que lleva a ambigüedades de descripción que confunden a los novatos. Por lo tanto, rechazo la termonología de Kruskal.
Usaré los siguientes términos:
Y de esos, obtenemos:
fuente
Wikipedia tiene un gran recurso sobre la generación de laberintos . He usado un algoritmo de prims aleatorio con excelentes resultados. El algoritmo de división se ve interesante pero nunca lo he usado.
Aquí está el ejemplo de Wikipedia de prim's en el trabajo.
fuente
Una manera fácil es hacer una lista de los muros norte y oeste, y luego permutarlos. Dale un número a cada habitación. Luego explote una de las paredes de la lista, siempre y cuando las dos habitaciones no tengan el mismo número, luego propague uno de los números a todas las otras habitaciones con el mismo número. Sigue hasta que te quedes sin paredes. Esto funciona para laberintos rectangulares o, en realidad, cualquier otro laberinto en el que pueda dar una lista de "habitaciones potencialmente conectadas". Además, es bastante sencillo de programar.
fuente
También echaría un vistazo a algunos de los algoritmos utilizados en el desarrollo de Roguelike. Hay un buen recurso inicial en Rogue Basin
fuente
Hay una buena carrera aquí: https://journal.stuffwithstuff.com/2014/12/21/rooms-and-mazes/
Los pasos básicos fueron:
Código aquí: https://github.com/munificent/hauberk/blob/db360d9efa714efb6d937c31953ef849c7394a39/lib/src/content/dungeon.dart
fuente
Usted preguntó cuál usé, así que me aseguraré de responder eso. Utilicé el algoritmo Recursive Backtracker en mi juego de laberinto en Rootbeer Games .
Esto es evidencia de que utilicé el algoritmo, por favor no lo vea como un anuncio de mi trabajo.
fuente