Générateur de labyrinthe d’algorithme de Wilson

L’algorithme de Wilson est une méthode de marche aléatoire effacée en boucle 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 sont également susceptibles d’être générés, ce qui en fait une technique de génération de labyrinthe 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 fonctionne beaucoup plus rapidement, donc je n’ai pas pris la peine de mettre en œuvre l’algorithme d’Aldous-Broder ici.

Un labyrinthe parfait est un labyrinthe dans lequel il existe exactement un chemin reliant n’importe quel point du labyrinthe à n’importe quel autre point. Cela signifie que vous ne pouvez pas finir par tourner en rond, mais vous rencontrerez souvent des culs-de-sac, ce qui vous obligera à faire demi-tour et à revenir en arrière.

Les cartes de labyrinthe générées ici incluent une version par défaut sans aucune position de départ et d'arrivée, vous pouvez donc les décider vous-même : il y aura une solution de n'importe quel point du labyrinthe à n'importe quel autre point. Si vous voulez trouver de l'inspiration, vous pouvez activer une position de départ et d'arrivée suggéré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 effacé en boucle a été créé par David Bruce Wilson.

Wilson a initialement introduit cet algorithme en 1996 alors qu’il recherchait des arbres couvrants aléatoires et des chaînes de Markov en théorie des probabilités. Bien que son travail ait été principalement en mathématiques et en 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 sculptant de manière itérative des chemins à partir de cellules nonvisites à l’aide de promenades aléatoires.

Étape 1 : Initialiser

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

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

• Choisissez n’importe quelle cellule aléatoire et marquez-la comme visitée. Cela sert de point de départ du labyrinthe pendant la génération.

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

• Choisissez une cellule nonvisée et commencez une marche aléatoire (se déplaçant dans des directions aléatoires).
• Si la promenade atteint une cellule déjà visitée, effacez toutes les boucles dans le chemin.
• Une fois que la promenade 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 des cellules nonvissées et à effectuer des promenades aléatoires jusqu’à ce que chaque cellule fasse partie du labyrinthe.