Simulatore di risolutore di labirinto con flood fill

Controlli

Scegli una modalità — Esplora, poi corri o Solo corsa rapida — e premi Avvia per guardarlo risolvere, oppure Passo una mossa alla volta. Nuovo labirinto costruisce un nuovo labirinto casuale; Reimposta riproduce quello stesso. Tre velocità, scorciatoie da tastiera e Schermo intero mantengono controllabile l’esecuzione. Le linee in grassetto sono i muri del labirinto, i corridoi ombreggiati sono ovunque il robot ha esplorato (vicoli ciechi inclusi) e la linea in grassetto è il percorso più breve trovato dal flood fill.

Teoria

Un labirinto a griglia è fatto di celle collegate da bordi aperti, con muri tra tutte le altre. Per trovare la rotta più breve un robot deve prima conoscere il labirinto, quindi questo laboratorio esegue due fasi.

Esplora. Il robot percorre il labirinto in profondità con la regola della mano sinistra: a ogni giunzione gira a sinistra se può, altrimenti va dritto e poi a destra. Quando incontra un vicolo cieco torna all’ultima giunzione e prende il ramo successivo. Ripetere l’operazione finché ogni cella è stata visitata mappa l’intero labirinto, inclusi tutti i percorsi sbagliati che ha dovuto escludere.

Ottimizza. Con la mappa completa, un flood fill assegna alla destinazione distanza zero e propaga valori crescenti verso l’esterno attraverso ogni bordo aperto. Ogni cella contiene ora la propria distanza dalla destinazione, quindi il percorso più breve è semplice: dalla partenza, passa sempre a un vicino con un numero inferiore di uno. Il robot percorre a velocità quel percorso, molto più corto dell’esplorazione con divagazioni.

Algoritmo

1. Esplora il labirinto in profondità con la regola della mano sinistra, tornando indietro da ogni vicolo cieco finché tutte le celle sono visitate.
2. Registra ogni bordo aperto su entrambi i lati, così la mappa finale conosce ogni muro.
3. Applica il flood fill dalla destinazione: etichettala 0 e propaga distanze crescenti verso l’esterno attraverso ogni bordo aperto.
4. Leggi il percorso più breve dal campo: dalla partenza, passa ripetutamente a un vicino la cui distanza è inferiore di uno.
5. Corri a velocità lungo quel percorso fino alla destinazione.
6. Confronta la lunghezza dell’esplorazione con quella del percorso più breve per vedere quanta divagazione abbia evitato la mappa.

Codice sorgente

Mantieni esplorazione, mappatura, pianificazione e movimento come funzioni separate:

// 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

Questo confine rende lo stesso pianificatore testabile in questo laboratorio nel browser, su un desktop e sul controllore ESP32 finale.

Ipotesi e differenze hardware

Il laboratorio rende pulita la mappatura eliminando la parte difficile di un vero Micromouse: l’odometria. Il robot simulato si muove esattamente di una cella per passo senza slittamento delle ruote, bias del giroscopio o errore di inversione a 90°, e i suoi tre sensori di distanza riportano i muri perfettamente senza falsi positivi. Una realizzazione ESP32 fisica accumula errore di orientamento e distanza a ogni mossa, deve riallinearsi rispetto ai muri e deve filtrare le letture ToF contro la luce del sole e il calo dell’alimentazione — ed è per questo che il tutorial sulle inversioni precise e la guida al flood fill dedicano più tempo al movimento che alla pianificazione. Usa questo simulatore per capire perché il flood fill ripianifica, non per dimostrare il tuo strato di movimento.

Schema elettrico

Usa un regolatore esterno dimensionato per la corrente di stallo dei motori. ESP32 e sensori necessitano di una pista logica stabile anche quando i motori si invertono.