Qu'est ce qu'un bon algorithme pour générer un labyrinthe?

https://stackoverflow.com/questions/38502

09-06-2019
|

Question

Dites que vous voulez une simple labyrinthe sur un N par M grille, avec un chemin à travers, et un bon nombre de impasses, mais qui ressemble à "droite" (c'est à direcomme quelqu'un l'a fait à la main sans trop petit impasses et tout le reste).Est-il un moyen connu à ce faire?

La solution

À partir de http://www.astrolog.org/labyrnth/algrithm.htm

Récursive backtracker:C'est en quelque sorte liée à la récursivité backtracker méthode de résolution décrite ci-dessous, et nécessite de la pile jusqu'à la taille du Labyrinthe.Quand la sculpture, être aussi gourmande que possible, et toujours tailler dans un non section si l'on est à côté de la cellule courante.Chaque fois que vous passez à une nouvelle cellule, pousser l'ancienne cellule de la pile.Si il n'y a pas défait des cellules à côté de la position actuelle, de la pop la pile à la position précédente.Le Labyrinthe est fait quand vous pop tout hors de la pile.Cet algorithme résultats dans des Labyrinthes avec à peu près aussi élevé une "rivière" facteur que possible, avec de moins en moins, mais plus de temps dans des impasses, et généralement d'une très longue et sinueuse solution.Il s'exécute assez rapidement, bien que l'algorithme de Prim est un peu plus rapide.Retour en arrière récursif ne fonctionne pas comme un mur additionneur, car cela tend à donner une solution chemin qui suit le bord extérieur, où l'ensemble de l'intérieur du Labyrinthe, qui est attaché à la frontière par une seule tige.

Elles ne produisent que 10% des impasses

par exemple, est un labyrinthe généré par cette méthode.

Autres conseils

Il s'avère 12 classique des algorithmes pour générer des "parfait" labyrinthes.Un labyrinthe est parfait si elle en a une, et une seule solution.Voici quelques liens pour chaque algorithme, bruts de l'ordre de ma préférence.

Pour plus d'infos, découvrez mazelib sur GitHub, une bibliothèque Python la mise en œuvre de tous les standards labyrinthe génération/algorithmes de résolution.

Un assez simple solution pourrait être d'attribuer aléatoire des poids pour les bords du graphique et de l'appliquer L'algorithme de Kruskal pour trouver un minimum spanning tree.

Meilleure analyse jamais sur labyrinthe algorithmes de génération: http://www.jamisbuck.org/presentations/rubyconf2011/index.html (était sur HN il y a quelques jours).

Curieusement, en modifiant légèrement le "canonique" règles et à partir d'une configuration aléatoire, Conway Jeu de la Vie semble générer assez agréable labyrinthes!

(Je ne me souviens pas exactement de la règle, mais d'une façon très simple modification qui tend à "densifier" la population de cellules...)

Ma façon préférée consiste à utiliser l'algorithme de Kruskal, mais quand choisissant au hasard et bord à supprimer, le poids le choix sur la base des types d'arêtes qu'il est connecté.

En faisant varier le poids des différents types d'arêtes, vous pouvez générer des labyrinthes avec beaucoup de caractéristiques distinctes ou "personnalités".Voir mon exemple ici:

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

Une des méthodes pour générer un labyrinthe est le randomisés version de l'algorithme de Prim.

Commencez avec une grille complète de murs.Choisissez une cellule, de la marque comme une partie du labyrinthe.Ajouter les murs de la cellule et le mur de la liste.Alors qu'il y a des murs dans la liste:

Choisir aléatoirement mur de la liste.Si la cellule sur le côté opposé n'est pas dans le labyrinthe encore:

(i) Faire le mur, un passage et marque de la cellule sur le côté opposé à la partie du labyrinthe.

(ii) Ajouter les voisins, les murs de la cellule et le mur de la liste.

Si la cellule sur le côté opposé était déjà dans le labyrinthe, supprimer le mur de la liste.

Pour plus de compréhension sur ici

Voici l'algorithme DFS écrit comme pseudo-code:

créer un CellStack (LIFO) de tenir une liste des positions des cellules
ensemble TotalCells = nombre de cellules dans la grille
choisissez une cellule au hasard et l'appeler CurrentCell
ensemble VisitedCells = 1

alors que VisitedCells < TotalCells trouver tous les voisins de CurrentCell avec tous les murs intacts
si un ou plusieurs trouvée en choisir une au hasard
abattre le mur entre elle et CurrentCell
pousser CurrentCell localisation sur la CellStack
faire de la nouvelle cellule CurrentCell
ajouter 1 à VisitedCells d'autre pop la plus récente entrée de la cellule au large de la CellStack
faire CurrentCell endIf fintantque

Licencié sous: CC-BY-SA avec attribution

Non affilié à StackOverflow