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.

Publié dans

3 comments

Poster un commentaire

Vous devriez utiliser le HTML:
<a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>

Ce site utilise Akismet pour réduire les indésirables. En savoir plus sur comment les données de vos commentaires sont utilisées.