Labyrinthes
Définitions
Un labyrinthe est une surface connexe. De telles surfaces peuvent avoir des topologies différentes : simple, ou comportant des anneaux ou des îlots.
On peut distinguer deux catégories de labyrinthe :
- les labyrinthes « parfaits » : chaque cellule est reliée à toutes les autres et, ce, de manière unique.
- les labyrinthes « imparfaits » (tous les labyrinthes qui ne sont pas parfaits) : ils peuvent donc contenir des boucles, des îlots ou des cellules inaccessibles.
Pour la suite, nous choisissons de représenter un labyrinthe par un graphe, dont les sommets représentent des cellules (tuples de coordonnées (ligne, colonne)) et les arêtes des passages entre deux cellules (l’absence d’arête équivaut alors à un mur).
Implémentation
Nous définissons une classe Labyrinthe
, héritant d’une classe Graphe
, et munie d’une méthode de représentation en mode semi-graphique (avec des caractères spéciaux).
Construction d’un labyrinthe
Il existe de très nombreux algorithmes de construction de labyrinthe…
Fusion aléatoire de chemins
- On part d’un labyrinthe dont tous les murs sont fermés,
- On associe une valeur unique (un identifiant) à chaque cellule,
- À chaque itération, on choisit un mur à ouvrir de manière aléatoire,
- Lorsqu’un mur est ouvert entre deux cellules adjacentes, les deux cellules sont liées entre elles et forment un « chemin ».
- À chaque fois que l’on tente d’ouvrir un passage entre deux cellules, on vérifie que ces deux cellules ont des identifiants différents.
- Si les identifiants sont identiques, c’est que les deux cellules sont déjà reliées et appartiennent donc au même chemin. On ne peut donc pas ouvrir le passage.
- Si les identifiants sont différents, le passage est ouvert, et l’identifiant de la première cellule est affecté à toutes les cellules du second chemin.
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.
Version modifiée
Bien que l’algorithme classique de Prim conserve une liste de bords, pour la génération de labyrinthes, nous pourrions plutôt maintenir une liste de cellules adjacentes. Si la cellule choisie au hasard comporte plusieurs bords qui la relient au labyrinthe existant, sélectionnez l’un de ces bords au hasard. Cela aura tendance à créer des branches légèrement plus nombreuses que la version basée sur les bords ci-dessus.
Algorithme d’Aldous-Broder
- On choisit une cellule au hasard comme « cellule courante » et on la marque comme « visitée ».
- Tant qu’il existe des cellules non visitées :
- On choisit un voisin au hasard,
- Si le voisin choisi n’a pas encore été visité :
- On ouvre un passage entre la « cellule courante » et le voisin choisi,
- On marque le voisin choisi comme étant visité,
- On fait du voisin choisi la « cellule courante ».
Pour en savoir plus …
https://weblog.jamisbuck.org/2011/1/17/maze-generation-aldous-broder-algorithm
Division récursive
- On part d’un labyrinthe sans aucun mur.
- On définit une « chambre » (rectangle interne au labyrinthe), initialement égale au labyrinthe entier.
- On coupe cette chambre en deux parties (de tailles égales ou aléatoirement) en construisant un mur (vertical ou horizontal – alternativement ou aléatoirement)
- On ouvre un passage au hasard dans ce grand mur
- On recommence avec les deux chambres
- La récursion s’arrête lorsqu’on ne peut plus couper la chambre en deux parties, au moins dans une direction.
Autres algorithmes
Wilson
https://weblog.jamisbuck.org/2011/1/20/maze-generation-wilson-s-algorithm.html
Hunt and kill
https://weblog.jamisbuck.org/2011/1/24/maze-generation-hunt-and-kill-algorithm.html
Jeu-démo en ligne
Voici un petit jeu-démo réalisé en Javascript par les élèves de terminales 2020-2021 : http://blaisepascal.fr/labyrinthe/
Sources :
https://fr.wikipedia.org/wiki/Mod%C3%A9lisation_math%C3%A9matique_de_labyrinthe
https://en.wikipedia.org/wiki/Maze_generation_algorithm