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

L’algorithme de Kruskal est un algorithme d’arbre couvrant minimum qui peut être adapté pour la génération de labyrinthe. Il est particulièrement efficace pour créer des labyrinthes parfaits. Une alternative à l’algorithme de Kruskal est l’algorithme de Prim, qui est également un algorithme de spanning-tree minimum, mais comme ils génèrent des labyrinthes identiques et les courses de Kruskal plus rapidement, je n’ai pas pris la peine de mettre en œuvre 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 le spanning-tree minimum (MST) d’un graphe, en s’assurant que tous les sommets sont connectés au poids total de bord minimal possible tout en évitant des 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 distinct (un composant unique).
• Répertoriez toutes les parois entre les cellules adjacentes en tant qu’arêtes potentielles.

Étape 2 : Trier les murs

• Mélangez ou commandez au hasard 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 : Murs de processus

• Itérer à travers les murs mélangé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, sautez 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 spanning-tree simple.
• À la fin, chaque cellule est connectée aux autres sans boucles ni sections isolées.

Étant donné que l’algorithme de Kruskal repose sur la fusion d’ensembles, il peut être optimisé en utilisant l’algorithme Union-Find, qui fournit un moyen efficace de suivre les cellules connectées pendant la génération de labyrinthes. Vous pouvez voir mon implémentation PHP de l’algorithme Union-Find ici : Ensemble disjoint (algorithme Union-Find) en PHP