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

L'algorithme de Kruskal est un algorithme d'arbre couvrant minimal qui peut être adapté à 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 également un algorithme d'arbre couvrant minimal, mais comme ils génèrent des labyrinthes identiques et que celui de Kruskal s'exécute plus rapidement, 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 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 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 garantissant 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 distinct (un composant unique).
• Énumérez tous les murs entre les cellules adjacentes comme des arêtes potentielles.

Étape 2 : Trier les murs

• Mélangez ou classez les murs de manière aléatoire. 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 du labyrinthe ne nécessite pas de pondération).

Étape 3 : Traitement des murs

• Parcourez 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), supprimez 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 seul arbre couvrant.
• À la fin, chaque cellule est connectée aux autres sans boucles ni sections isolées.

L'algorithme de Kruskal s'appuyant 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 lors de la génération du labyrinthe. Vous pouvez voir mon implémentation PHP de l'algorithme Union-Find ici : Ensemble disjoint (algorithme Union-Find) en PHP