Labyrinthes : différents algorithmes

L’algorithme de Prim

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

Si vous voyez des fautes d’orthographe ou des corrections à apporter signalez-le moi je me ferai un plaisir de vous écouter !

L’algorithme de Prim

Il faut une place mémoire équivalente à la taille du labyrinthe.

États possibles des cellules :

1. “Dedans” : la cellule est une partie du labyrinthe et on a déjà creusé dedans au moins une fois
2. “Frontière” : la cellule n’est pas une partie du labyrinthe et on n’a pas encore creusé dedans, mais est à côté d’une cellule de type “Dedans”
3. “Vierge” : la cellule n’est ni “Dedans” ni “Frontière”

Étapes de l’algorithme :

1. Choisir une cellule “Vierge” au hasard
2. La marquer comme “Dedans”
3. Marquer tous ses voisins en tant que “Frontière”
4. Répéter jusqu’à ce qu’il n’y ait plus de cellules “Frontière”

Caractéristiques du labyrinthe généré :

• Facteur “rivière” très bas
• Nombreux petits culs-de-sac
• Solution rapide à trouver en général

Performance :

Lorsqu’il est correctement implémenté, c’est l’algorithme le plus rapide, en seconde position après celui d’Eller.