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

L'algorithme de Wilson est une méthode de marche aléatoire sans 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 ont la même probabilité d'être générés, ce qui en fait une technique de génération de labyrinthes non biaisée. 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 aux caractéristiques identiques, mais il est beaucoup plus rapide ; c'est pourquoi je n'ai pas jugé utile 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 sans boucle a été créé par David Bruce Wilson.

Wilson a initialement introduit cet algorithme en 1996 lors de ses recherches sur les arbres couvrants aléatoires et les chaînes de Markov en théorie des probabilités. Bien que ses travaux aient porté principalement 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 traçant itérativement des chemins à partir des cellules non visitées à l'aide de marches aléatoires.

Étape 1 : Initialiser

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

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

• Choisissez une cellule au hasard et marquez-la comme visitée. Elle servira de point de départ pour la génération du labyrinthe.

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

• Choisissez une cellule non visitée et commencez une marche aléatoire (déplacement 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 parcours rejoint la région visitée, marquez toutes les cellules du chemin comme visitées.

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

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

Lectures complémentaires

Si vous avez apprécié cet article, vous aimerez peut-être aussi ces suggestions :

• Générateur de labyrinthe d'algorithme d'Eller
• Générateur de labyrinthe de chasse et de meurtre
• Générateur de labyrinthe d'algorithme d'arbre en croissance