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. Commencez par prendre une cellule et ajoutez la dans une liste. Ensuite, creusez dans une cellule liée à cette dernière et qui n’a jamais été creusée. Ajoutez la cellule destination dans la liste. Puis 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). Puis, toujours avec la cellule courante, s’il ne reste plus de liaison possible avec une cellule « vierge », retirez la de la liste. La labyrinthe est terminé lorsque la liste est vide. Le côté intéressant de cet algorithme est qu’il vous donne la possibilité de créer des motifs en modifiant la manière dont vous choisissez les cellules de la liste. Par exemple, 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 mais 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 et une solution longue et sinueuse.