Ci-dessous, les différences entre deux révisions de la page.
labyrinthe [2015/05/18 18:04] jonathanperret créée |
labyrinthe [2017/09/28 15:44] |
||
---|---|---|---|
Ligne 1: | Ligne 1: | ||
- | 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é. | ||