Algorithme de Prim

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.