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. Tout au long de la création, chaque cellule est dans l’un de ces 3 états :

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 (1) ;
3. “Vierge”: la cellule n’est ni “Dedans” ni “Frontière”.

Commencez par choisir une cellule “Vierge” au hasard, marquez la comme “Dedans”, puis marquez tous ses voisins en tant que “Frontière”. Le labyrinthe est terminé lorsqu’il n’y a plus de cellules “Frontière” (ce qui signifie par conséquent qu’il n’y a plus de cellules “Vierges”, elles sont toutes “Dedans”). Cet algorithme génère des labyrinthes avec un facteur “rivière” très bas, plein de petits culs-de-sac, et la solution est rapide à trouver en général. Lorsqu’il est correctement implémenté, c’est l’algorithme le plus rapide, en seconde position après celui d’Eller.