Créer un générateur de labyrinthes

Le besoin : produire un parcours jouable à partir d’une grille

Dans un jeu, créer chaque labyrinthe à la main devient rapidement contraignant. Une génération automatique permet de renouveler les niveaux, d’adapter leur taille et de proposer une expérience différente à chaque partie. Le résultat ne doit pourtant pas être un dessin aléatoire : chaque cellule doit rester accessible et les passages doivent former un ensemble cohérent. La difficulté consiste donc à retirer les murs dans le bon ordre, sans isoler une partie de la grille. Une fois cette logique séparée de l’affichage, le même générateur peut alimenter un jeu, un exercice ou un outil de création de niveaux.

Représenter le labyrinthe avec une grille de cellules

Le labyrinthe est découpé en lignes et en colonnes. Chaque cellule conserve quatre murs : haut, droite, bas et gauche. Elle mémorise également si elle a déjà été visitée pendant la génération. Cette structure suffit pour décrire entièrement le niveau. Lorsqu’un passage est créé entre deux cellules voisines, le mur correspondant est supprimé dans les deux cellules. Retirer uniquement un côté produirait une représentation incohérente : une cellule indiquerait un passage tandis que sa voisine conserverait encore son mur.

Cette représentation reste indépendante du Canvas. Les données peuvent donc être exportées, transformées en tuiles ou utilisées par un système de collisions. Le Canvas ne fait qu’interpréter la grille pour dessiner les murs. Cette séparation entre données et rendu évite de lier le fonctionnement du générateur à une présentation particulière.

Creuser les passages avec un parcours en profondeur

La démonstration utilise un parcours en profondeur avec retour arrière. Le générateur part d’une cellule, cherche parmi ses voisines celles qui n’ont pas encore été visitées, puis en choisit une au hasard. Il supprime le mur qui les sépare, empile la cellule actuelle et poursuit depuis la nouvelle position. Lorsqu’aucune voisine disponible ne reste, il revient à la cellule précédente grâce à la pile. Le processus continue jusqu’à ce que toutes les cellules aient été parcourues.

Cette méthode produit un labyrinthe dit parfait : deux positions sont toujours reliées par un chemin unique. Il n’existe ni zone inaccessible ni boucle. D’autres algorithmes peuvent ensuite être ajoutés pour obtenir des structures plus ouvertes, davantage de croisements ou des salles.

Rendre la génération visible étape par étape

Exécuter toute la génération en une seule fois donne immédiatement le résultat, mais masque le raisonnement. La démonstration traite donc un nombre limité d’étapes à chaque image. La cellule active est mise en évidence, les cellules déjà parcourues sont différenciées et les passages apparaissent progressivement. Le réglage de vitesse modifie uniquement le nombre d’étapes exécutées pendant une frame. L’algorithme reste identique, qu’il soit observé lentement ou terminé presque instantanément.

Cette animation montre également pourquoi la pile est nécessaire. Le parcours avance tant qu’une cellule voisine reste disponible, puis remonte progressivement lorsqu’il atteint une impasse. Le retour arrière ne supprime aucun passage : il cherche simplement un ancien embranchement depuis lequel l’exploration peut reprendre.

Utiliser une graine aléatoire pour reproduire un résultat

Un générateur fondé directement sur l’aléatoire du navigateur produit un labyrinthe impossible à reproduire exactement. La ressource utilise donc une petite fonction pseudo-aléatoire initialisée par une graine. Avec la même taille et la même graine, le résultat reste identique. Cette possibilité est utile pour partager un niveau, analyser un défaut ou conserver une sélection de labyrinthes sans stocker toute la grille.

Le bouton de nouvelle graine permet au contraire de repartir sur une valeur différente. La graine devient ainsi un identifiant compact du niveau. Dans un jeu, elle peut être enregistrée dans une sauvegarde ou transmise dans une URL.

Vérifier le résultat avec un solveur automatique

Une fois la génération terminée, la démonstration peut rechercher le chemin entre l’entrée et la sortie. Le solveur parcourt les passages existants et mémorise l’origine de chaque cellule découverte. Lorsqu’il atteint la destination, il remonte ces références pour reconstruire le trajet. Le chemin affiché permet de vérifier visuellement que le labyrinthe est réellement traversable.

Le solveur n’intervient pas dans la génération. Il exploite uniquement les murs déjà enregistrés dans les cellules. Cette indépendance permet de remplacer l’algorithme de génération sans modifier la recherche de chemin, ou de réutiliser le solveur pour guider un personnage contrôlé par le joueur.

Adapter le générateur à un jeu JavaScript

La grille produite peut être convertie en carte de collisions, en ensemble de tuiles ou en niveau Canvas. Chaque mur peut devenir un obstacle, tandis que chaque cellule peut recevoir un objet, un adversaire ou une récompense. L’entrée et la sortie sont déjà identifiées. Il devient également possible de mesurer la longueur du chemin principal afin d’estimer la difficulté du niveau.