Algorithme de résolution de labyrinthe — expliqué visuellement et interactivement
L'analogie de l'eau
Imagine que le labyrinthe est une piscine vide avec des murs. Le but (centre du labyrinthe) est un robinet.
Tu ouvres le robinet — l'eau commence à couler et inonde toute la piscine. L'eau atteint d'abord les cases juste à côté du but, puis celles un peu plus loin, puis encore plus loin...
Chaque case reçoit un numéro : combien de pas elle est loin du but. Le robot suit toujours le numéro le plus bas. C'est mathématiquement garanti d'être le chemin le plus court.
Simulation Interactive — Essaie toi-même !
Clique sur les bords des cellules pour ajouter/retirer des murs, puis lance le flood fill pour voir comment l'algorithme calcule les distances.
200ms
Clique sur les bords des cellules pour placer des murs, puis clique "Lancer le Flood Fill"
Grille 8×8 • Clique sur les bords des cellules pour ajouter des murs • Le but est au centre (vert), le robot en bas-gauche (bleu)
Comment fonctionne le BFS (Breadth-First Search)
L'algorithme en 5 étapes simples :
1. On met le but dans une file d'attente avec la valeur 0
2. On prend la première cellule de la file
3. Pour chaque voisin accessible (pas de mur entre eux) qui n'a pas encore de valeur :
→ On lui donne la valeur du parent + 1
→ On l'ajoute à la file d'attente
4. On répète l'étape 2 jusqu'à ce que la file soit vide
5. Résultat : chaque cellule contient sa distance exacte au but
Pourquoi c'est optimal ? Le BFS explore les cellules couche par couche (d'abord toutes les cellules à distance 1, puis toutes celles à distance 2, etc.). Donc la première fois qu'une cellule est atteinte, c'est forcément par le chemin le plus court. Le robot suit ensuite le gradient descendant (toujours vers la valeur plus basse) → chemin optimal garanti.
Comment le robot prend ses décisions
À chaque case, le robot fait ceci :
1. Lire les capteurs ToF — Mesurer les distances avant, gauche, droite pour détecter les murs
2. Enregistrer les murs — Mettre à jour la carte interne (tableau 2D en mémoire)
3. Re-calculer le flood — Relancer le BFS depuis le but (les valeurs changent car on connaît plus de murs maintenant)
4. Regarder les 4 voisins — Nord, Est, Sud, Ouest (seulement ceux sans mur)
5. Aller vers le plus petit — Le voisin avec la valeur flood la plus basse = direction optimale
Les deux phases du tournoi
Phase 1 : Exploration (lente)
Le robot ne connaît pas le labyrinthe
Il avance lentement (SPEED_EXPLORE = 160)
À chaque case : lit les murs, met à jour la carte, re-flood
Il découvre les murs au fur et à mesure
But : atteindre le centre du labyrinthe
Phase 2 : Retour rapide
Le robot connaît tous les murs découverts
Il re-flood depuis le départ (coin bas-gauche)
Il fonce à vitesse max (SPEED_RETURN = 220)
Pas besoin de lire les capteurs — la carte est connue
But : revenir au départ le plus vite possible
Flood Fill vs Wall Following
Wall Following (suivi de mur) ❌
Simple : toujours garder la main droite sur le mur
Problème : ne fonctionne PAS si le labyrinthe a des îlots
Peut tourner en boucle infinie
Ne trouve JAMAIS le chemin optimal
Flood Fill (notre choix) ✅
Fonctionne sur tout type de labyrinthe
Gère les boucles, culs-de-sac, îlots
Trouve toujours le chemin le plus court
Standard des compétitions Micromouse depuis 40 ans
Structure du Code (6 fichiers)
config.hToutes les constantes : taille du labyrinthe, pins GPIO, vitesses, PID. Le seul fichier à modifier pour calibrer.
motors.hContrôle des 4 moteurs via L298N. PWM, encodeurs, PID pour aller droit, rotation précise.
sensors.hGestion des 3 capteurs VL53L0X ToF. Initialisation I2C, lecture, détection de murs.
movement.hMouvements haut-niveau : avancer d'une case, tourner 90°, demi-tour.
flood_fill.hLe cerveau : carte des murs, BFS, choix de direction, exploration et retour.
maze_robot_v3.inoProgramme principal : machine à états ATTENTE → EXPLORATION → RETOUR → FINI.
Calibration avant le tournoi
TURN_PULSES_90 — Le nombre de pulses encodeur pour un virage exact de 90°. Procédure : faire tourner le robot 4× à droite (360°) et ajuster jusqu'à ce qu'il revienne exactement à sa position initiale.
CELL_SIZE_MM — La taille d'une case du labyrinthe en mm. Sera dans le cahier des charges du tournoi.
WALL_THRESHOLD_MM — En dessous de cette distance (100mm par défaut), le capteur considère qu'il y a un mur. À ajuster selon la taille des cases.