Supposons que vous vouliez un labyrinthe simple sur une grille N par M, avec un seul chemin, et un bon nombre d'impasses, mais qui ait l'air "correct" (c'est-à-dire comme si quelqu'un l'avait fait à la main sans trop de petites impasses et tout ça). Existe-t-il un moyen connu de faire cela ?
Il s'avère qu'il existe 11 algorithmes classiques pour générer des labyrinthes "parfaits". Un labyrinthe est parfait s'il a une, et une seule, solution. Voici quelques liens vers chaque algorithme, dans l'ordre approximatif de mes préférences.
Pour plus d'informations, consultez le site mazelib sur GitHub, une bibliothèque Python mettant en œuvre tous les algorithmes standard de génération et de résolution de labyrinthes.
Vous dites ici que l'automate cellulaire génère des labyrinthes parfaits, mais votre bibliothèque dit le contraire. Comment cela se fait-il ? github.com/theJollySin/mazelib/blob/master/docs/
@JeroSquartini Vous avez tout à fait raison. En fin de compte, je suppose que j'ai juste vraiment souhaitent qu'il y ait encore 12 algorithmes classiques de génération de labyrinthes. Et tandis que l'automate cellulaire es très populaire, il n'est certainement pas "parfait".
De http://www.astrolog.org/labyrnth/algrithm.htm
Recursive backtracker : Cette méthode est quelque peu liée à la méthode de résolution récursive backtracker décrite ci-dessous, et nécessite une pile de la taille du labyrinthe. Lorsque vous creusez, soyez aussi gourmand que possible, et creusez toujours dans une section non construite s'il y en a une à côté de la cellule actuelle. Chaque fois que vous passez à une nouvelle case, poussez la case précédente sur la pile. S'il n'y a aucune case non construite à côté de la position actuelle, remontez la pile à la position précédente. Le labyrinthe est terminé lorsque vous retirez tout ce qui se trouve sur la pile. Cet algorithme donne des labyrinthes avec un facteur "rivière" aussi élevé que possible, avec moins d'impasses mais plus longues, et généralement une solution très longue et sinueuse. Il fonctionne assez rapidement, bien que l'algorithme de Prim soit un peu plus rapide. Le retour en arrière récursif ne fonctionne pas comme un additionneur de murs, car il a tendance à donner une solution qui suit le bord extérieur, où tout l'intérieur du labyrinthe est attaché à la frontière par une seule tige.
Ils ne produisent que 10% d'impasses
est un exemple de labyrinthe généré par cette méthode.
Le backtracker récursif génère une solution assez fleuve, comme indiqué. L'algorithme d'Eller est peut-être plus intéressant, car il possède des propriétés similaires à celles des algorithmes aléatoires (qui donnent de bons pourcentages de solutions "river-y" et de solutions "dead-end"), mais il est beaucoup plus rapide.
Une solution assez simple consisterait à attribuer des poids aléatoires aux arêtes du graphe et à appliquer la méthode suivante L'algorithme de Kruskal pour trouver un arbre d'envergure minimale.
La meilleure discussion jamais tenue sur les algorithmes de génération de labyrinthes : http://www.jamisbuck.org/presentations/rubyconf2011/index.html (c'était sur HN il y a quelques jours).
Ce n'est pas seulement une grande discussion sur la génération de labyrinthes. C'est un excellent exemple d'une présentation technique faite parfaitement .
Wow, c'est la meilleure discussion sur la génération de labyrinthes que j'ai jamais vue. Quelle présentation fantastique !
Curieusement, en modifiant légèrement les règles "canoniques" et en partant d'une configuration aléatoire, Le jeu de la vie de Conway semble générer de jolis labyrinthes !
(Je ne me souviens pas de la règle exacte, mais c'est une modification très simple qui tend à "densifier" la population de cellules...).
L'une des méthodes permettant de générer un labyrinthe est la version randomisée de l'algorithme de Prim.
Commencez avec une grille pleine de murs. Choisissez une cellule, marquez-la comme faisant partie du labyrinthe. Ajoutez les murs de la cellule à la liste des murs. Tant qu'il y a des murs dans la liste :
Choisissez un mur au hasard dans la liste. Si la cellule du côté opposé n'est pas encore dans le labyrinthe :
(i) Faites du mur un passage et marquez la cellule du côté opposé comme faisant partie du labyrinthe.
(ii) Ajoutez les parois voisines de la cellule à la liste des parois.
Si la cellule du côté opposé se trouvait déjà dans le labyrinthe, retirez le mur de la liste.
Prograide est une communauté de développeurs qui cherche à élargir la connaissance de la programmation au-delà de l'anglais.
Pour cela nous avons les plus grands doutes résolus en français et vous pouvez aussi poser vos propres questions ou résoudre celles des autres.
