Algorithme de l’arbre qui grandit

Labyrinthes : différents algorithmes

Algorithme de l’arbre qui grandit

Traduit en Français par moi-même. Les originaux sont ici.

Si vous voyez des fautes d’orthographe ou des corrections à apporter signalez-le moi je me ferai un plaisir de vous écouter !

L’algorithme de l’arbre qui grandit (Growing tree algorithm)

C’est un algorithme générique, capable de créer des labyrinthes composés de motifs différents. Il requiert un espace pouvant aller jusqu’à la taille totale du labyrinthe.

Étapes de l’algorithme :

1. Commencez par prendre une cellule et ajoutez la dans une liste
2. Creusez dans une cellule liée à cette dernière et qui n’a jamais été creusée
3. Ajoutez la cellule destination dans la liste
4. Choisissez une cellule au hasard dans la liste et creusez (créez un passage) vers une cellule vierge (= qui n’a jamais été creusée)
5. Avec la cellule courante, s’il ne reste plus de liaison possible avec une cellule “vierge”, retirez la de la liste
6. Le labyrinthe est terminé lorsque la liste est vide

Variations et résultats :

• Si vous reprenez systématiquement la dernière cellule avec laquelle vous avez creusé, cet algorithme revient à celui du retour-récursif
• Si vous tirez toujours une cellule au hasard, le comportement se rapprochera de l’algorithme de Prim
• Si vous reprenez systématiquement la dernière cellule ajoutée à la liste, vous allez créer un labyrinthe avec le facteur “rivière” le plus bas possible, encore plus bas que l’algorithme de Prim
• Si vous recommencez de temps à autre sur la cellule la plus récente, et vous en prenez occasionnellement une au hasard, le labyrinthe aura :
  • Un facteur “rivière” haut
  • Une solution souvent courte et directe
• Si vous tirez au hasard parmi les dernières cellules ajoutées, le labyrinthe aura :
  • Un facteur “rivière” bas
  • Une solution longue et sinueuse