Maze Generator & Solver

Les générateurs de labyrinthes créent des labyrinthes aléatoires et résolubles à l'aide de divers algorithmes, chacun produisant des labyrinthes aux caractéristiques visuelles et au niveau de difficulté propres. Il s'agit à la fois d'un outil et d'un casse-tête : le joueur peut générer de nouveaux labyrinthes de n'importe quelle taille et tenter de les résoudre, ou observer le fonctionnement des algorithmes de génération et de résolution en temps réel. La compréhension des différents algorithmes de génération ajoute une dimension pédagogique, car chaque méthode produit des labyrinthes aux propriétés uniques : longs couloirs, nombreuses impasses, nombreuses ramifications ou motifs ressemblant à des cours d'eau.

Règles

1. Choisissez les dimensions du labyrinthe (largeur et hauteur) ainsi qu’un algorithme de génération.
2. Générez le labyrinthe. Le résultat est toujours un labyrinthe parfait : il existe exactement un chemin entre deux cellules quelconques, sans boucles ni zones inaccessibles.
3. Résolvez le labyrinthe en trouvant le chemin menant du point de départ (généralement en haut à gauche) à la sortie (généralement en bas à droite).
4. Si vous le souhaitez, observez l’animation étape par étape de l’algorithme de génération ou de résolution.
5. Comparez différents algorithmes pour voir comment ils influencent la difficulté et l’aspect du labyrinthe.

Algorithmes de génération

• Backtracker récursif (DFS) : part d’une case choisie au hasard, trace un chemin vers une case voisine non visitée choisie au hasard, puis revient sur ses pas en cas de blocage. Produit de longs couloirs sinueux avec relativement peu de ramifications. Crée des labyrinthes d’aspect organique et modérément difficiles à résoudre.
• Algorithme de Prim : maintient une frontière de murs candidats et sélectionne aléatoirement des murs à supprimer, faisant croître le labyrinthe vers l’extérieur à la manière d’un arbre. Produit des labyrinthes avec des impasses plus courtes et davantage de ramifications, créant un aspect plus touffu.
• Algorithme de Kruskal : supprime aléatoirement des murs entre des cellules appartenant à différentes composantes connexes jusqu’à ce que l’ensemble de la grille soit connecté. Produit des labyrinthes très uniformes, sans biais ni motif apparent.
• Division récursive : part d’une grille vide et ajoute de manière récursive des murs comportant des passages d’une seule cellule. Permet d'obtenir des labyrinthes comportant de longs murs droits et présentant un aspect hachuré caractéristique. Ils ont tendance à être plus faciles à résoudre.
• Algorithme d'Aldous-Broder : une marche aléatoire qui creuse des passages vers des cellules non visitées. Permet d’obtenir des labyrinthes parfaitement uniformes (chaque labyrinthe possible a la même probabilité d’apparaître), mais est très lent pour les grandes grilles.
• Algorithme de Wilson : utilise des marches aléatoires à boucles effacées pour générer des labyrinthes à arbre couvrant uniforme. Mathématiquement élégant, il produit des résultats non biaisés, mais le temps de génération est variable.
• Algorithme d’Eller : génère le labyrinthe ligne par ligne à l’aide d’un suivi d’ensembles. Économe en mémoire, il peut générer des labyrinthes d’une longueur infinie, car il ne doit stocker que la ligne en cours.
• Arbre binaire : chaque case est reliée à sa voisine du nord ou de l’est (choisie au hasard). Extrêmement rapide et simple, mais produit un biais diagonal notable. Chaque labyrinthe présente des couloirs dégagés le long de deux bords.

Algorithmes de résolution

• Suivi des murs : Suivre le mur de gauche ou de droite. Fonctionne pour tous les labyrinthes simplement connexes. Simple mais pas optimal.
• Recherche en largeur (BFS) : explore toutes les cases situées à une distance N avant de passer à la distance N+1. Garantit le chemin le plus court.
• Recherche en profondeur (DFS) : explore aussi profondément que possible avant de revenir en arrière. Permet de trouver rapidement un chemin (pas nécessairement le plus court).
• Recherche A* : utilise une heuristique (généralement la distance de Manhattan jusqu’à l’objectif) pour privilégier l’exploration vers la sortie. Permet de trouver le chemin le plus court tout en explorant moins de cellules que la BFS.
• Remplissage des impasses : identifie toutes les impasses et les comble en remontant jusqu’à la jonction la plus proche. Le chemin restant non comblé constitue la solution.
• Algorithme de Tremaux : méthode systématique permettant de résoudre n’importe quel labyrinthe en marquant les passages. Peut être mise en œuvre par un individu parcourant un labyrinthe physique.

L'étude mathématique des labyrinthes remonte à plusieurs siècles, mais la génération algorithmique de labyrinthes a débuté avec l'avènement des ordinateurs. L'un des tout premiers algorithmes connus de génération de labyrinthes est apparu dans les années 1970, lorsque des programmeurs amateurs, sur les premiers micro-ordinateurs tels que le Commodore PET et l'Apple II, ont écrit des programmes simples pour afficher des labyrinthes aléatoires à l'écran. L’algorithme dit « de l’arbre binaire » a été l’un des premiers à être utilisé en raison de son extrême simplicité : il peut être implémenté en quelques lignes de BASIC seulement.

L'étude formelle des algorithmes de génération de labyrinthes est étroitement liée à la théorie des graphes. Un labyrinthe parfait (c'est-à-dire comportant exactement un chemin entre deux cellules quelconques) est mathématiquement équivalent à un arbre couvrant du graphe de la grille. Les différents algorithmes de génération de labyrinthes sont, en réalité, autant de méthodes distinctes permettant de calculer des arbres couvrants aléatoires. Ce lien a été formalisé dans les années 1990, lorsque des chercheurs ont démontré que l’algorithme de Wilson et celui d’Aldous-Broder produisaient des arbres couvrants uniformes — ce qui signifie que chaque labyrinthe possible a la même probabilité d’être généré.

La génération de labyrinthes est devenue un incontournable de l’enseignement de la programmation et de l’informatique ludique. Des ouvrages tels que « Mazes for Programmers » de Jamis Buck (2015) explorent de manière systématique des dizaines d’algorithmes de labyrinthes, accompagnés de leurs implémentations, et ce sujet constitue un exercice courant dans les cours d’informatique destinés à enseigner les algorithmes de graphes, la récursivité et les structures de données. L’attrait visuel que procure le fait de voir des algorithmes générer des labyrinthes étape par étape en fait des éléments populaires dans les outils de visualisation d’algorithmes et les tutoriels de programmation.

Dans l’univers du jeu vidéo, la génération procédurale de labyrinthes est fondamentale pour le genre « roguelike », où chaque partie se déroule dans un donjon généré aléatoirement. Des jeux comme « Rogue » (1980), « NetHack » (1987) et des titres modernes tels que « Hades » (2020) et « Dead Cells » (2018) utilisent des variantes d’algorithmes de génération de labyrinthes pour créer des niveaux rejouables. Ce domaine continue d’évoluer, les chercheurs explorant la génération de labyrinthes en 3D, les grilles non rectangulaires (hexagonales, triangulaires, circulaires) et les algorithmes de génération produisant des labyrinthes présentant des caractéristiques de difficulté spécifiques.