le wiki du gnan club

Ceci est une ancienne révision du document !

On va essayer d'implémenter l'algorithme “Exploration exhaustive” donné sur la page Wikipédia : http://fr.wikipedia.org/wiki/Mod%C3%A9lisation_math%C3%A9matique_d%27un_labyrinthe

On part d'un labyrinthe où tous les murs sont fermés. Chaque cellule contient une variable booléenne qui indique si la cellule a déjà été visitée ou non (i.e. les cellules visitées sont celles qui appartiennent au chemin du labyrinthe en cours de construction).

Au départ, toutes les cellules sont marquées comme non visitées (faux).

On choisit arbitrairement une cellule et on la marque comme visitée (vrai).

Puis on regarde quelles sont les cellules voisines possibles et non visitées et on stocke la position en cours.

S'il y a au moins une possibilité, on en choisit une au hasard, on ouvre le mur et on recommence avec la nouvelle cellule.

S'il n'y en pas, on revient à la case précédente et on recommence.

Lorsque l'on est revenu à la case de départ et qu'il n'y a plus de possibilités, le labyrinthe est terminé.