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 :
- « Dedans » : la cellule est une partie du labyrinthe et on a déjà creusé dedans au moins une fois
- « 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 »
- « Vierge » : la cellule n’est ni « Dedans » ni « Frontière »
Étapes de l’algorithme :
- Choisir une cellule « Vierge » au hasard
- La marquer comme « Dedans »
- Marquer tous ses voisins en tant que « Frontière »
- 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.
3 comments