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

L’algorithme de Kruskal est un algorithme à arbre couvrant minimal qui peut être adapté pour la génération de labyrinthes. Il est particulièrement efficace pour créer des labyrinthes parfaits. Une alternative à l’algorithme de Kruskal est l’algorithme de Prim, qui est aussi un algorithme d’arbre couvrant minimal, mais comme ils génèrent des labyrinthes identiques et que les runs de Kruskal sont plus rapides, je n’ai pas pris la peine d’implémenter celui de Prim.

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 Kruskal

L’algorithme de Kruskal a été créé par Joseph Bernard Kruskal, Jr., un mathématicien, statisticien et informaticien américain. Il a décrit l’algorithme pour la première fois en 1956 dans son article « On the Shortest Spanning Subtree of a Graph and the Traveling Salesman Problem ».

L’algorithme est conçu pour trouver l’arbre couvrant minimal (MST) d’un graphe, en s’assurant que tous les sommets sont connectés avec le poids total d’arête minimal possible tout en évitant les cycles.

Comment fonctionne l’algorithme de Kruskal pour la génération de labyrinthes

Étape 1 : Initialiser

• Traitez chaque cellule du labyrinthe comme un ensemble séparé (un composant unique).
• Listez tous les murs entre les cellules adjacentes comme arêtes potentielles.

Étape 2 : Trier les murs

• Mélange ou ordonne aléatoirement les murs. Si vous l’implémentez comme un véritable algorithme de Kruskal, triez les murs dans un ordre aléatoire (puisque la génération de labyrinthe ne nécessite pas de poids).

Étape 3 : Traiter les murs

• Itère à travers les murs dérangés.
• Si les deux cellules divisées par le mur appartiennent à des ensembles différents (c’est-à-dire qu’elles ne sont pas encore connectées dans le labyrinthe), retirez le mur et fusionnez les ensembles.
• S’ils sont déjà dans le même ensemble, saute le mur (pour éviter les cycles).

Étape 4 : Continuer jusqu’à la fin

• Répétez ce processus jusqu’à ce que toutes les cellules soient connectées, formant un arbre couvrant unique.
• À la fin, chaque cellule est connectée aux autres sans boucles ni sections isolées.

Puisque l’algorithme de Kruskal repose sur la fusion d’ensembles, il peut être optimisé en utilisant l’algorithme Union-Fin, qui offre un moyen efficace de suivre les cellules connectées lors de la génération du labyrinthe. Vous pouvez voir mon implémentation PHP de l’algorithme Union-Find ici : Lien

Lectures complémentaires

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

• Générateur de labyrinthes récursifs de type Backtracker
• Générateur de labyrinthe d’algorithme d’arbre de croissance
• Chasser et tuer générateur de labyrinthe