grim7reaper

Un artisan du code

Génération et résolution de labyrinthes parfaits

Cet article provient de mon ancien site Internet.

Présentation

Les labyrinthes parfaits

Les algorithmes présentés dans cet article ne gèrent que les labyrinthes parfaits. Dans de tels dédales, chaque cellule est reliée aux autres pas un seul et unique chemin élémentaire.

Un labyrinthe parfait Un labyrinthe imparfait

Parmi les deux images précédentes, seule la première est un labyrinthe parfait.

Les algorithmes de génération

Il existe de nombreux algorithmes permettant la création de labyrinthes parfaits. On peut classer ces algorithmes par rapport :

En ce qui me concerne, j’ai implémenté les algorithmes en tant que « créateur de passages ». Cela signifie que l’état initial est un labyrinthe où chaque cellule est isolée par quatre murs, puis l’algorithme va ouvrir des passages au fur et à mesure. Ils auraient également pu être mis en oeuvre en tant que « poseur de murs » (un état initial vide, puis création de murs au fur et à mesure), bien que cela aurait demandé quelques adaptations pour Hunt & Kill.

Les deux premiers algorithmes présentés sont de type tree. Cela signifie que chaque itération est basée sur la précédente et à chaque étape on a un labyrinthe valide. Le dernier algorithme est de type set ce qui signifie qu’il utilise des ensembles indépendants mais (néanmoins cohérents). On obtient un labyrinthe valide à la fin de l’algorithme, lorsque tous les ensembles sont liés.

Le Growing Tree

C’est un algorithme qui est capable de créer des labyrinthes composés de motifs différents selon la méthode de tirage employée.

On commence par prendre une cellule et on l’ajoute dans une liste. Ensuite, on se déplace dans une cellule adjacente à cette dernière à condition qu’elle n’ait jamais été visitée. On ajoute cette cellule à la liste. Puis on choisit une nouvelle cellule dans cette liste, selon la méthode de tirage choisie, et on lui applique le même traitement. Lorsqu’une cellule est entourée de cellules visitées elle est retirée de la liste. L’algorithme se termine quand la liste est vide (le labyrinthe est achevé).

La façon de choisir une nouvelle cellule dans la liste doit être choisie parmi les méthodes suivantes :

Cet algorithme a une complexité spatiale en O(N), N étant le nombre de cellules composant le labyrinthe. Cependant, en utilisant la méthode de tirage the most recent, c’est l’algorithme de génération le plus rapide.

Labyrinthe généré avec l’algorithme Growing Tree

Le Hunt & Kill

Il semblerait que ce soit l’un des algorithmes les plus facile à modifier pour essayer d’avoir des motifs originaux car il n’y a aucune règle particulière à appliquer systématiquement.

Son mode de fonctionnement est similaire au backtracking récursif, sauf lorsqu’il n’y a plus aucune cellule inexplorée à côté de la cellule courante. Dans ce cas, on passe en mode Hunt et on recherche dans l’ensemble du labyrinthe la première cellule vierge qui côtoie au moins une cellule explorée. À ce moment-là, on la Kill (on la connecte à la cellule explorée adjacente) et on recommence à se déplacer à partir d’elle. Le labyrinthe est terminé si, lorsque que l’on passe en mode Hunt, on ne trouve plus aucune cellule à « chasser ».

Cet algorithme ne requiert aucun espace mémoire en plus de celui occupé par le labyrinthe lui-même. Il est donc adapté à la création de grands labyrinthes. Cependant, il faut noter qu’en contrepartie cet algorithme est lent (mais cela pourrait être optimisé, en utilisant un peu plus de mémoire), principalement à cause du temps de chasse des dernières cellules. Les labyrinthes générés par cette méthode présentent un facteur « rivière » élevé (mais pas autant que ceux générés par backtracking récursif). On peut diminuer ce facteur en entrant plus souvent, de manière aléatoire, en mode Hunt.

Labyrinthe généré avec l’algorithme Hunt & Kill

L’algorithme d’Eller

C’est un algorithme peu gourmand en mémoire. En effet, il crée le labyrinthe ligne après ligne ce qui permet de ne charger que deux lignes en mémoire (la courante et la suivante). Enfin, contrairement aux deux algorithmes précédents, il utilise une approche basée sur des ensembles.

Afin d’éviter la création de boucles ou de passages fermés indépendants, chaque cellule fait partie d’un groupe (un groupe peut être composé d’une seule cellule). Un groupe contient toutes les cellules qui sont reliées entre elles par un chemin.
La génération d’une ligne est composée de deux étapes :

  1. examen des cellules adjacentes dans la ligne en cours, puis connexion des cellules (création de passages horizontaux) de manière aléatoire ;
  2. examen des cellules entre la ligne courante et la ligne suivante, puis connexion des cellules (création des passages verticaux) de manière aléatoire.

Attention, les connexions ne sont pas totalement aléatoires. Elles doivent respecter à quatre règles :

  1. on ne doit pas connecter horizontalement deux cellules appartenant au même groupe (sinon il y a création d’une boucle) ;
  2. lorsque l’on réalise une connexion horizontale il faut fusionner les groupes (les cellules sont maintenant liées, elles appartiennent donc au même groupe) ;
  3. toutes les cellules appartenant à un groupe d’une cellule doivent participer à la création d’une connexion verticale (sinon elles resteront isolées) ;
  4. lorsque l’on a réalisé les connexions verticales, toutes les cellules qui ne font partie d’aucun groupe doivent être placées dans un groupe qui les contient elles seules (afin de les connecter à l’itération suivante, cf. règle 3).

Cependant, ces conditions ne sont pas suffisantes. Au cours de tests, j’ai pu remarquer que, si l’on applique uniquement ces quatre règles, on pouvait observer la formation de groupes de cellules totalement isolés du reste du labyrinthe (et donc la structure obtenue n’est plus parfaite). En effet, s’il y a bien une règle pour empêcher l’apparition de cellules isolées (règle 3), il n’y a rien en ce qui concerne les groupes. Si un groupe de cellules n’a pas au moins un lien vers la ligne suivante il sera irrémédiablement isolé du reste de la structure car il n’y a jamais de retour en arrière et on ne lie pas vers le haut. C’est pour remédier à ce problème que j’ai créé la règle suivante :

Au passage, on remarque que cet algorithme est particulièrement adapté à la génération de labyrinthe théoriquement infini (la création s’effectuant ligne après ligne, on n’est pas limité par la quantité de mémoire). Il permet également de générer des labyrinthes de manière incrémentale.

Labyrinthe généré avec l’algorithme Eller

Les algorithmes de résolution

Il existe de nombreux algorithmes permettant la résolution de labyrinthes. On peut les classer par rapport :

Pour mon solveur, j’ai implémenté deux algorithmes de résolution qui sont différents sur de nombreux points :

Le backtracking

Cet algorithme est rapide quel que soit le type du labyrinthe, mais il nécessite l’utilisation d’une pile dont la taille peut atteindre (dans le pire des cas) le nombre de cellules composant le labyrinthe. Il a donc une complexité spatiale en O(N), N étant le nombre de cellules du labyrinthe.

Le principe est extrêmement simple. À chaque étape, trois cas peuvent se présenter :

  1. si l’on rencontre une impasse ou une cellule inexplorable (cellule condamnée ou déjà explorée) on va remonter jusqu’à l’intersection précédente (en dépilant). Chaque cellule dépilée est scellée ;
  2. sinon, si on a atteint la sortie alors l’algorithme se termine ;
  3. sinon on se déplace dans une des directions libres.

Lorsque l’on essaye un nouveau chemin on le marque, et lorsque l’on se trouve dans le cas 1 (c’est-à-dire que l’on retourne en arrière) on efface les marques que l’on avait placées et on condamne le passage. Lorsque que l’algorithme s’arrête, il ne reste plus qu’un seul chemin marqué : c’est la solution (ou une des solutions, s’il en existe plusieurs).

Cette méthode va toujours trouver une solution, si tant est qu’il y en aie une. Cependant, ça ne sera pas forcément la plus courte (ce qui n’est pas un problème dans mon cas, étant donné que la solution est unique).

Le dead-end filling

C’est un algorithme de résolution simple qui est rapide et qui ne requiert aucune mémoire supplémentaire (contrairement à la méthode précédente).

On parcourt le labyrinthe et à chaque fois que l’on rencontre une impasse on la remonte jusqu’à arriver à une intersection. Lors de cette remontée, toutes les cellules traversées sont scellées. À la fin, il ne restera que la (cas d’un labyrinthe parfait) ou les solutions.

Cet algorithme ne peut pas « couper » accidentellement le chemin entre le début et l’arrivée, puisque chaque étape du processus préserve la topologie du labyrinthe. De plus, le processus ne s’arrêtera pas trop tôt car le résultat final ne peut pas contenir d’impasses.

Téléchargement

Pour ceux que cela intéresse, le code complet est disponible ici

Le code est sous GPLv3. Il est écrit en C89, aucune dépendance particulière n’est requise (hormis l’afficheur, optionnel, qui nécessite la bibliothèque SDL). Le projet est composé de :

Attention, j’ai écrit ce code il y a au moins trois ans et je n’y ai pas retouché depuis… J’ai uniquement modifié le processus de construction en remplaçant le Makefile fait main par un truc basé sur CMake, mais le code en lui-même est le code original.

Cela implique que le code est clairement moins bon que ce que je produit actuellement (le code est commenté en français par exemple…), donc ne soyez pas surpris. Cela dit, ce n’est pas non plus Beyrouth (il y a très peu de warnings même avec gcc et clang en mode parano’), le code est relativement propre (surtout pour mon niveau de l’époque sachant que ce fut mon premier projet en C d’une taille notable).

Dans les trucs un peu sympa à voir dans le code, il y a la représentation assez compacte d’une cellule de labyrinthe (beaucoup d’info’ dans seulement 8 bits). Rien de très original, mais à l’époque j’étais assez content de moi (le zoom et le défilement du labyrinthe dans l’afficheur m’avait aussi demandé du boulot, même si rétrospectivement ce n’est pas un truc monstrueux non plus).

Liens externes

  1. Le facteur « rivière » est lié à la densité d’impasses et de carrefours dans un labyrinthe. Un labyrinthe avec un facteur « rivière » faible va comporter beaucoup d’impasses tandis qu’un labyrinthe avec un facteur « rivière » élevé aura moins d’impasses (mais elles seront plus longues).↩