Labyrinthes parfaits sur une grille 40×28 : parcours récursif, Wilson, Eller ou Prim aléatoire ; résolution par A* (Manhattan, 4-voisinage). On peut dessiner des murs et déplacer le départ et le but.
À propos du modèle
Les labyrinthes et A* : un labyrinthe parfait est un arbre couvrant sur la grille des salles — un seul chemin entre cellules, tant que le champ n’est pas retouché. On le construit sur la même grille 40×28 que engineering/astar-dijkstra-grid. Les « salles » sont les cellules d’indices impairs (1,1)… ; les passages ouvrent à la fois les salles et le mur entre salles voisines, donc le labyrinthe est connexe et sans cycle jusqu’à ce qu’on édite. On dispose du parcours récursif (pile DFS), de Wilson (marches aléatoires à effacement des boucles), d’Eller (fusion d’ensembles par lignes, avec verticales aléatoires) et de Prim aléatoire (l’arbre croît depuis un front d’arêtes). Après génération, on lance **A* à heuristique de Manhattan et 4-voisinage** — le même modèle discret que le laboratoire A*, sans diagonales ni cellules « chères ». On peut ajouter des murs, effacer des passages et déplacer S/G ; au déplacement, les extrémités sont forcées praticables.
Public : Mathématiques discrètes et informatique : générateurs de labyrinthes et plus court chemin sur grille, à côté de A*/Dijkstra.
Notions clés
labyrinthe parfait
arbre couvrant
parcours récursif
algorithme de Wilson
algorithme d’Eller
Prim aléatoire
recherche A*
heuristique de Manhattan
Comment ça marche
Labyrinthe parfait en 40×28 : salles sur la grille impaire, les passages ouvrent les murs entre elles — un arbre sans cycle. Parcours récursif / Wilson / Eller / Prim donnent des arbres aléatoires différents ; puis le même A* de cours (4-voisinage, Manhattan) cherche le plus court chemin sur les murs déjà posés.
Questions fréquentes
Pourquoi les labyrinthes de Wilson et d’Eller « n’ont pas le même air » ?
Les deux construisent des arbres couvrants aléatoires sur la même grille, mais un autre aléa local (la racine de Wilson, les choix horizontaux d’Eller) donne un dessin différent à taille finie.
Est-ce le même A* que sur la page A* / Dijkstra ?
Les mêmes quatre directions, l’heuristique de Manhattan et le coût unitaire du pas sur les cellules libres. Ici pas de diagonales, ni de cellules pondérées, ni des modes Dijkstra ou glouton : seulement le A* de cours.
Peut-on casser la « perfection » du labyrinthe ?
Oui : la gomme crée un cycle (un second chemin entre régions) ; des murs en trop peuvent rompre la connexité. A* montrera la nouvelle topologie ; s’il n’y a pas de chemin jusqu’à G, aucun chemin.