Labyrinthes : différents algorithmes

Algorithme Retour-récursif

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 !

Retour-récursif

(« Recursive backtracker ») : cette méthode nécessite une pile qui doit pouvoir aller jusqu’à la taille totale du nombre de cellules. Lorsque vous creusez, soyez le plus gourmand possible, et creusez toujours dans une cellule sur laquelle vous n’avez jamais été, dans la mesure où elle touche celle qui est en cours.

Chaque fois que vous creusez :

1. Placez la cellule courante en haut de la pile ;
2. Creusez ;
3. Si, dans la cellule courante, vous ne pouvez plus creuser (donc il n’y a aucune cellule pas encore faite collée à la cellule courante), retirez la dernière cellule de la liste et considérez la comme la cellule courante.

Le labyrinthe est terminé lorsque votre pile est vide. Cet algorithme crée des labyrinthes avec le facteur « rivière » le plus grand possible, avec moins de cul-de-sac, et une grande distance entre eux, et la solution pour aller de l’un à l’autre est en générale longue et tortueuse. Cet algorithme est assez rapide, même si il l’est moins que l’algorithme de Prim.