Générateur de labyrinthe avec l'algorithme de Wilson

L'algorithme de Wilson est une méthode de marche aléatoire à boucle effacée qui génère des arbres couvrants uniformes pour la création de labyrinthes. Cela signifie que tous les labyrinthes possibles d'une taille donnée ont la même probabilité d'être générés, ce qui en fait une technique de génération de labyrinthes impartiale. L'algorithme de Wilson peut être considéré comme une version améliorée de l'algorithme d'Aldous-Broder, car il génère des labyrinthes avec des caractéristiques identiques, mais il s'exécute beaucoup plus rapidement, je n'ai donc pas pris la peine d'implémenter l'algorithme d'Aldous-Broder ici.

Un labyrinthe parfait est un labyrinthe dans lequel il existe exactement un seul chemin entre n'importe quel point du labyrinthe et n'importe quel autre point. Cela signifie que vous ne pouvez pas tourner en rond, mais que vous rencontrerez souvent des impasses qui vous obligeront à faire demi-tour.

Les cartes de labyrinthe générées ici comprennent une version par défaut sans position de départ et d'arrivée, afin que vous puissiez décider vous-même de ces positions : il y aura une solution de n'importe quel point du labyrinthe à n'importe quel autre point. Si vous souhaitez vous inspirer, vous pouvez activer une suggestion de position de départ et d'arrivée - et même voir la solution entre les deux.

À propos de l'algorithme de Wilson

L'algorithme de Wilson pour générer des arbres couvrants uniformes à l'aide d'un mur aléatoire à boucle effacée a été créé par David Bruce Wilson.

Wilson a initialement introduit cet algorithme en 1996 alors qu'il effectuait des recherches sur les arbres de recouvrement aléatoires et les chaînes de Markov en théorie des probabilités. Bien que ses travaux aient principalement porté sur les mathématiques et la physique statistique, l'algorithme a depuis été largement adopté pour la génération de labyrinthes en raison de sa capacité à produire des labyrinthes parfaitement uniformes.

Comment fonctionne l'algorithme de Wilson pour la génération de labyrinthes

L'algorithme de Wilson garantit que le labyrinthe final est entièrement connecté sans aucune boucle en créant de manière itérative des chemins à partir de cellules non visitées à l'aide de promenades aléatoires.

Étape 1 : Initialiser

• Commencez avec une grille remplie de murs.
• Définissez une liste de toutes les cellules de passage possibles.

Étape 2 : Choisissez une cellule de départ aléatoire

• Choisissez une cellule au hasard et marquez-la comme visitée. Cela sert de point de départ au labyrinthe pendant la génération.

Étape 3 : marche aléatoire avec effacement de boucle

• Choisissez une cellule non visitée et commencez une marche aléatoire (en vous déplaçant dans des directions aléatoires).
• Si le parcours atteint une cellule déjà visitée, effacez toutes les boucles du chemin.
• Une fois que le chemin se connecte à la région visitée, marquez toutes les cellules du chemin comme visitées.

Étape 4 : Répétez jusqu'à ce que toutes les cellules soient visitées :

• Continuez à sélectionner les cellules non visitées et à effectuer des promenades aléatoires jusqu'à ce que chaque cellule fasse partie du labyrinthe.