Olivier Pons

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.