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. L'algorithme de Prim, également un algorithme d'arbre couvrant minimal, constitue une alternative à l'algorithme de Kruskal. Cependant, comme ils génèrent des labyrinthes identiques et que l'algorithme de Kruskal est plus rapide, je n'ai pas jugé utile d'implémenter l'algorithme 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., mathématicien, statisticien et informaticien américain. Il l'a décrit pour la première fois en 1956 dans son article intitulé « Sur le plus court sous-arbre couvrant d'un graphe et le problème du voyageur de commerce ».

L'algorithme est conçu pour trouver l'arbre couvrant minimal (MST) d'un graphe, en veillant à ce que tous les sommets soient connectés avec le poids total d'arêtes minimal possible tout en évitant les cycles.

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

Étape 1 : Initialiser

• Considérez chaque cellule du labyrinthe comme un ensemble distinct (un composant unique).
• Répertoriez tous les murs entre cellules adjacentes comme des arêtes potentielles.

Étape 2 : Trier les murs

• Mélangez ou ordonnez aléatoirement les murs. Si vous implémentez l'algorithme 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 : Parois de traitement

• Parcourez les murs mélangés.
• Si les deux cellules séparé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 font déjà partie du 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.
• Au final, chaque cellule est connectée aux autres sans boucles ni sections isolées.

L'algorithme de Kruskal reposant sur la fusion d'ensembles, il peut être optimisé grâce à l'algorithme Union-Find, qui permet de suivre efficacement les cellules connectées lors de la génération du labyrinthe. Vous pouvez consulter 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 labyrinthe de chasse et de meurtre
• Générateur de labyrinthe avec l'algorithme de Wilson
• Générateur de labyrinthe de type Backtracker récursif