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. Commencez en choisissant une cellule au hasard dans le labyrinthe. Ensuite, creusez au hasard dans le labyrinthe tant que vous ne rencontrez pas de cellule déjà creusée. Dans ce dernier cas, revenez à la cellule précédemment creusée et recommencez. Plus précisément, lorsque vous revenez en arrière, essayez avec la cellule sur laquelle vous êtes revenu de creuser à nouveau dans le sens essayé pour la dernière fois. Ainsi vous faites moins de boucles le long du tracé, et vous aurez en résultat un seul et long passage ajouté au labyrinthe. Le labyrinthe est terminé lorsque toutes les cellules ont été ajoutées au labyrinthe. Cet algorithme a les mêmes problèmes de performance que celui d’Aldous-Broder : le premier chemin tiré au hasard peut mettre beaucoup de temps à trouver la cellule de départ, mais néanmoins à partir du moment où quelques chemins on été tirés, le reste du labyrinthe est très rapidement fini. En moyenne il est cinq fois plus rapide que l’algorithme d’Aldous-Broder, et deux fois plus rapide que les algorithmes expliqués précédemment. Notez qu’il peut être accéléré par deux lorsqu’il est programmé en tant qu’ajouteur de murs, parce que les murs sur les côtés sont dès le début considérés comme une partie du labyrinthe, et les premiers murs ajoutés sont connectés beaucoup plus rapidement.

Publié dans

Poster un commentaire

Vous devriez utiliser le HTML:
<a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>