Simulateur de solveur de labyrinthe (remplissage)

Commandes

Choisissez un mode — Explore, then speed-run ou Speed-run only — et appuyez sur Start pour le regarder résoudre, ou avancez un mouvement par un avec Step. New maze construit un nouveau labyrinthe aléatoire ; Reset rejoue le même. Trois vitesses, des raccourcis clavier et le plein écran gardent l’essai maîtrisable. Les lignes épaisses sont les murs du labyrinthe, les couloirs ombrés sont partout où le robot a exploré (impasses comprises), et la ligne épaisse est le plus court chemin trouvé par remplissage par diffusion.

Théorie

Un labyrinthe sur grille est fait de cases reliées par des arêtes ouvertes, avec des murs entre les autres. Pour trouver l’itinéraire le plus court, un robot doit d’abord connaître le labyrinthe — ce labo fonctionne donc en deux phases.

Exploration. Le robot parcourt le labyrinthe en profondeur avec la règle de la main gauche : à chaque jonction, il tourne à gauche s’il le peut, sinon tout droit, puis à droite. Quand il atteint une impasse, il revient sur ses pas jusqu’à la dernière jonction et prend la branche suivante. Répéter cela jusqu’à visiter chaque case cartographie tout le labyrinthe — y compris tous les mauvais chemins qu’il a fallu écarter.

Optimisation. Avec la carte complète, un remplissage par diffusion attribue à l’objectif une distance de zéro et propage des valeurs croissantes vers l’extérieur par chaque arête ouverte. Chaque case contient désormais sa distance à l’objectif, donc le plus court chemin est simplement ceci : depuis le départ, avancez toujours vers un voisin d’un numéro inférieur. Le robot parcourt cet itinéraire à toute vitesse — bien plus court que l’exploration sinueuse.

Algorithme

1. Explorez le labyrinthe en profondeur avec la règle de la main gauche, en ressortant de chaque impasse, jusqu’à visiter toutes les cases.
2. Enregistrez chaque arête ouverte des deux côtés pour que la carte terminée connaisse chaque mur.
3. Remplissez par diffusion depuis l’objectif : étiquetez-le 0 et propagez des distances croissantes vers l’extérieur par chaque arête ouverte.
4. Lisez le plus court chemin sur le champ : depuis le départ, avancez à répétition vers un voisin dont la distance est inférieure d’un.
5. Parcourez à toute vitesse cet itinéraire jusqu’à l’objectif.
6. Comparez la longueur d’exploration à la longueur du plus court chemin pour voir combien d’errance la carte a économisée.

Code source

Gardez l’exploration, la cartographie, la planification et le mouvement comme des fonctions séparées :

// Phase 1 — map the whole maze, backtracking out of dead ends
exploreDepthFirst(map, robot);        // left-hand rule until every cell is visited

// Phase 2 — flood-fill the finished map and run the shortest path
map.floodFill(goal);                  // goal = 0, distances ripple outward
for (Cell c = start; c != goal; c = map.lowerNeighbor(c))
  robot.driveTo(c);                   // always step one distance lower

Cette frontière rend le même planificateur testable dans ce labo en navigateur, sur un ordinateur de bureau et sur le contrôleur ESP32 final.

Hypothèses et différences avec le matériel

Le labo rend la cartographie propre en supprimant la partie difficile d’un vrai Micromouse : l’odométrie. Le robot simulé avance d’exactement une case par pas sans patinage des roues, sans biais de gyroscope ni erreur de virage à 90°, et ses trois capteurs de distance rendent compte des murs parfaitement sans faux positifs. Un montage physique sur ESP32 accumule des erreurs de cap et de distance à chaque mouvement, doit se recaler contre les murs et doit filtrer les mesures de temps de vol contre la lumière du soleil et les chutes d’alimentation — c’est pourquoi le tutoriel sur les virages précis et le guide de remplissage par diffusion passent plus de temps sur le mouvement que sur la planification. Utilisez ce simulateur pour comprendre pourquoi le remplissage par diffusion replanifie, pas pour valider votre couche de mouvement.

Schéma de câblage

Utilisez un régulateur externe calibré pour le courant de blocage des moteurs. L’ESP32 et les capteurs ont besoin d’un rail logique stable même lorsque les moteurs s’inversent.