Algorithme de Kruskal

Labyrinthes : différents algorithmes

Algorithme de Kruskal

Traduit en Français par moi-même. Les originaux sont ici.

L’algorithme de Kruskal

Cet algorithme est intéressant parce qu’il ne « grandit » pas en créant le labyrinthe selon le principe d’un arbre, mais en enlevant des segments de murs au hasard dans tout le labyrinthe, et malgré ce, le labyrinthe est de type Parfait au final. ll requiert un espace mémoire proportionnel à la taille du labyrinthe.

Prérequis :

Il faut juste avoir la capacité d’énumérer toutes les séparations du labyrinthe et d’en tirer au hasard (habituellement, cela implique de créer une liste de tous les murs et la mélanger).

Étapes de l’algorithme :

1. Donnez à chaque cellule un numéro unique (Id)
2. Faite une boucle sur toutes les séparations du labyrinthe aléatoirement
3. Pour chaque séparation :
   • Si les cellules de chaque côté de ce mur ont un Id différent :
     • Supprimez ce mur
     • Gardez un des deux Ids
     • Appliquez cet Id des deux côtés partout où vous retrouvez l’un des deux Ids dans le labyrinthe
   • Si les cellules de chaque côté de la séparation ont déjà le même Id :
     • La séparation doit être transformée en mur (car il existe déjà un chemin de tracé pour les relier)

Caractéristiques :

• Cet algorithme donne des labyrinthes avec un facteur « rivière » bas, mais pas aussi bas que l’algorithme de Prim.
• L’opération de « fusion » des Ids peut être lente si elle est mal pensée.

Optimisation :

Il faut imaginer le labyrinthe en terme d’arbre et, lors de la fusion des « Ids », ne faire que déplacer les cellules dans les bonnes branches, afin de faire une fusion pratiquement instantanée. Bien programmé, cet algorithme est moyennement rapide.