Ci-dessous, les différences entre deux révisions de la page.
labyrinthe [2015/05/18 18:18] jonathanperret quelques idées pour implémenter le labyrinthe |
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é. | ||
- | |||
- | Pour le faire dans Minecraft, il faut qu'on trouve pour chacune des opérations ci-dessus un équivalent Minecraftien. | ||
- | |||
- | * Marquer les cellules comme visitées : une cellule est visitée quand elle est creuse. On va commencer avec un bloc solide à la place du labyrinthe. | ||
- | * Regarder les cellules voisines possibles non visitées : on va regarder autour de la position actuelle quels sont les murs solides, derrière lesquels il y a une cellule non visitée (pleine). | ||
- | * Revenir à la cellule précédente : on va probablement devoir sauvegarder les positions successives dans un tableau. | ||
- | * | ||
- | |||
- | |||