Algorithme de Wilson

Labyrinthes : différents algorithmes

Algorithme de Wilson

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 Wilson

C’est une version améliorée de l’algorithme d’Aldous-Broder, en ce sens que les labyrinthes générées sont exactement du même type, avec des labyrinthes crées selon une probabilité égale, mis à part que l’algorithme de Wilson est beaucoup plus rapide. Il requiert un espace mémoire pouvant aller jusqu’à la taille du labyrinthe.

Étapes de l’algorithme :

1. Commencez en choisissant une cellule au hasard dans le labyrinthe.
2. Creusez au hasard dans le labyrinthe tant que vous ne rencontrez pas de cellule déjà creusée.
3. Si vous rencontrez une cellule déjà creusée :
   • Revenez à la cellule précédemment creusée
   • Essayez avec la cellule sur laquelle vous êtes revenu de creuser à nouveau dans le sens essayé pour la dernière fois
4. Répétez jusqu’à ce que toutes les cellules aient été ajoutées au labyrinthe.

Avantages de cette méthode :

• Cette approche réduit les boucles le long du tracé
• Résulte en un seul et long passage ajouté au labyrinthe

Performance et caractéristiques :

• Mêmes défis de performance que l’algorithme d’Aldous-Broder :
  • Le premier chemin tiré au hasard peut mettre beaucoup de temps à trouver la cellule de départ
  • Une fois quelques chemins tirés, le reste du labyrinthe est très rapidement complété
• En moyenne :
  • Cinq fois plus rapide que l’algorithme d’Aldous-Broder
  • Deux fois plus rapide que les algorithmes expliqués précédemment

Optimisation :

Il peut être accéléré par deux lorsqu’il est programmé en tant qu’ajouteur de murs, car :

• Les murs sur les côtés sont dès le début considérés comme une partie du labyrinthe
• Les premiers murs ajoutés sont connectés beaucoup plus rapidement