Algorithme de Prim
On part d'un labyrinthe dont tous les murs sont fermés.
On crée :
- une liste de cellules "non visitées" (pleine au départ)
- une liste de murs (initialement les murs adjacents d'une cellule choisie aléatoirement)
Tant qu'il y a des murs dans la liste :
- on choisit un mur au hasard dans la liste.
- si une seule des deux cellules que le mur divise est visitée, alors :
- on ouvre un passage à travers ce mur
- on marque la cellule "non visitée" comme "visitée" (on la supprime de la liste)
- on ajoute les murs voisins de la cellule à la liste des murs.
- on retire le mur de la liste.