Semaine 10 - Labyrinthe
Un labyrinthe est une surface connexe. De telles surfaces peuvent avoir des topologies différentes : simple, ou comportant des anneaux ou îlots :
- Une surface connexe simple
- Une surface connexe avec un îlot
Ces deux surfaces ne sont topologiquement pas équivalentes. Cette différence, rapportée aux labyrinthes, conduit à une distinction en deux catégories :
- celle des labyrinthes dits « parfaits » où chaque cellule est reliée à toutes les autres et, ce, de manière unique.
- celle des labyrinthes dits « imparfaits » qui sont tous les labyrinthes qui ne sont pas parfaits (ils peuvent donc contenir des boucles, des ilots ou des cellule inaccessibles).
[...]
On sait, de façon pragmatique, que l'on trouve obligatoirement la sortie d'un labyrinthe si on longe systématiquement un mur en le gardant, sans jamais le lâcher, à main droite ou à main gauche. Cette idée est vérifiée dans le cas d'un labyrinthe parfait, mais elle peut conduire à explorer la totalité du labyrinthe, c'est-à-dire à passer au moins une fois dans toutes les cellules sans exception. [...]
La preuve de cette découverte empirique est très simple. Si on ne sort pas d'un labyrinthe [en tenant toujours la main sur un des murs depuis l'entrée], c'est qu'on est en train de « tourner en rond ».
Comment est généré le labyrinthe ?
L'algorithme qui génère ce labyrinthe est plutôt simple. Il creuse un long tunnel en choisissant à chaque case une direction aléatoire vers une case qui n'a pas déjà été visitée jusqu'à ce qu'il n'ait plus de choix. Ensuite, il revient sur ses pas jusqu'à trouver une case à partir de laquelle il peut recommencer à creuser son tunnel. Une fois qu'il est revenu à la case initiale et qu'il n'y a plus de direction à visiter, il s'arrête.
Si on décortique, on obtient ceci :
- À partir d'une grille vide, faire de chaque case du contour un mur.
- Sélectionner une case au hasard comme case courante.
- Choisir une case voisine à la case courante qui n'a pas déjà été visitée.
- Bâtir un passage entre la case courante et cette case voisine.
- S'il n'y a plus de case voisine valide, revenir à la case précédente.
- Revenir à l'étape 3.
- Le labyrinthe est complété lorsque l'on revient à la première case visitée et qu'il n'y a plus de cases voisines disponibles.
La sortie est placée à la première case ayant été visitée et l'entrée est placée à la première case où l'algorythme a dû revenir sur ses pas.
Pour éviter que le labyrinthe ne soit qu'un ramassis de longs tunels, certains murs sont ensuite transformés en passages.