Algorithme d’Aldous-Broder
Labyrinthes : différents algorithmes
Algorithme d’Aldous-Broder
Traduit en Français par moi-même. Les originaux sont ici.
L’algorithme d’Aldous-Broder
La chose la plus intéressante de cet algorithme est qu’il génère tous les labyrinthes possibles d’une taille donnée selon une probabilité égale. De plus il ne demande pas d’espace mémoire supplémentaire pour gérer une pile.
Fonctionnement de l’algorithme :
- Prenez une cellule au hasard, et imaginez qu’il y a un point.
- Déplacez ce point, sur une cellule voisine, au hasard.
- Si le point entre dans une cellule qui n’a pas encore été creusée, faites un lien entre la cellule précédente et la nouvelle (la séparation ne se transforme pas en mur mais en lien).
- Continuez ainsi jusqu’à ce que toutes les cellules aient été « creusées ».
Cet algorithme donne des labyrinthes avec un facteur « rivière » bas, à peine plus haut que celui de Kruskal. (En d’autres termes, pour une taille de labyrinthes donnée, il y aura plus de labyrinthes générés avec un facteur « rivière » bas que haut).
Le problème avec cet algorithme est qu’il est lent, principalement parce qu’il n’est pas très fûté. On est même pas sûr de le terminer, si, par exemple une ou deux cellules du labyrinthe ne sont jamais tirées, lors du tirage aléatoire. Néanmoins, comme le principe de tirage aléatoire est très rapide, cela contre balance la théorie, et très souvent la génération est nettement plus rapide que ce que l’on pourrait imaginer.
En moyenne il est sept fois plus lent que les algorithmes expliqués précédemment, et dans les cas les pires, il peut prendre bien plus de temps si l’algorithme de tirage aléatoire met beaucoup de temps à tirer les quelques dernières cellules qui n’ont pas été faites.
Cet algorithme peut être aussi implémenté en créant non pas en transformant les séparateur en liens, mais en murs. Si on considère qu’il n’y a pas de bords et que le labyrinthe « boucle » sur lui même (aller au Nord de la cellule la plus au Nord vous amènera à la cellule la plus au Sud par exemple). En tant que créateur de murs, cet algorithme devient presque deux fois plus rapide.