Risoluzione del labirinto con flood fill per robot Micromouse

Flood fill è l’algoritmo che vince la maggior parte delle competizioni Micromouse ed è un’ottima introduzione alla pianificazione in presenza di incertezza. Diversamente dal tracciamento dei percorsi dei libri di testo, un robot da labirinto non parte con la mappa completa: deve scoprire le pareti mentre avanza. Flood fill è progettato proprio per questo. Osserva l’algoritmo in azione nel Simulatore di risoluzione del labirinto.

Un campo di distanza, non un percorso

Flood fill assegna a ogni cella un numero: la sua distanza dall’obiettivo. Le celle dell’obiettivo ricevono zero. Da lì, ogni cella vicina non bloccata riceve un valore superiore di uno rispetto alla vicina con il valore più basso e la propagazione si espande verso l’esterno finché ogni cella raggiungibile non ha un valore.

Il robot non memorizza mai un percorso. Resta semplicemente in una cella, osserva le vicine e si sposta in quella il cui numero è esattamente più basso di uno. Il campo di distanza è il piano, ed è per questo che si riprende con eleganza quando la mappa cambia.

Ottimismo sulle pareti sconosciute

Il robot non vede tutto il labirinto, quindi flood fill considera aperte tutte le pareti che non ha ancora rilevato. Questo ottimismo produce la stima più breve possibile e mantiene il robot in movimento verso l’obiettivo invece di farlo esplorare senza una meta.

Quando un sensore rivela una parete che era stata supposta aperta, il robot la registra — su entrambi i lati del confine condiviso — e ricalcola il campo di distanza. Il piano corregge se stesso e il robot prosegue da dovunque si trovi.

Perché la prima corsa non è il percorso più breve

Una sorpresa comune: flood fill non garantisce il percorso più breve alla prima corsa. Poiché ha agito in base a supposizioni ottimiste, ha trovato un modo per raggiungere l’obiettivo, non necessariamente il migliore. I robot Micromouse reali usano due fasi:

1. Una corsa di ricerca che esplora una porzione sufficiente del labirinto per costruire una mappa accurata.
2. Una corsa rapida lungo il percorso più breve rivelato dalla mappa completata.

All’inizio, un’esplorazione efficiente conta più dell’ottimalità alla prima corsa.

Flood fill confrontato con BFS e A*

La ricerca in ampiezza e A* pianificano su un grafo già noto. Flood fill è progettato per un labirinto ancora in scoperta: ripete il riempimento ogni volta che compare una nuova parete. Matematicamente, il riempimento è un calcolo di distanza in ampiezza; la differenza è che flood fill prevede una mappa che continua a cambiare ed è economico da ricalcolare.

Supera anche il semplice seguimento della parete (tenere sempre una mano sulla parete), che non può raggiungere un obiettivo al centro del labirinto e raramente trova un percorso breve.

Il ciclo di rilevamento, pianificazione e movimento

void planOneCell(Maze& map, Robot& robot) {
  map.observe(robot.cell(), robot.senseLeftFrontRight());
  map.floodFill(centerGoals);
  Cell next = map.bestDescendingNeighbor(robot.cell());
  robot.turnAndMoveTo(next);
}

Mantieni separati rilevamento, mappatura, pianificazione e movimento. Questo confine permette allo stesso pianificatore di funzionare in un simulatore nel browser, sul desktop e su un ESP32 con sensori di distanza ed encoder reali.

Il flood fill completo

Il campo di distanza è un’espansione in ampiezza dall’obiettivo ed è abbastanza breve da poter scrivere per intero:

const uint8_t N = 16;                       // 16 x 16 maze
uint8_t dist[N][N];                         // distance to goal, per cell
uint8_t walls[N][N];                        // bitmask: 1=N, 2=E, 4=S, 8=W

// A simple ring buffer beats a std::queue on a microcontroller.
uint8_t queueR[N * N], queueC[N * N];

void floodFill(const uint8_t goals[][2], uint8_t goalCount) {
  memset(dist, 255, sizeof(dist));          // 255 = unreachable

  uint16_t head = 0, tail = 0;
  for (uint8_t g = 0; g < goalCount; g++) {
    const uint8_t r = goals[g][0], c = goals[g][1];
    dist[r][c] = 0;
    queueR[tail] = r; queueC[tail] = c; tail++;
  }

  const int8_t dr[4] = {-1, 0, 1, 0};       // N, E, S, W
  const int8_t dc[4] = { 0, 1, 0, -1};

  while (head < tail) {
    const uint8_t r = queueR[head], c = queueC[head];
    head++;

    for (uint8_t d = 0; d < 4; d++) {
      if (walls[r][c] & (1 << d)) continue;             // wall in the way

      const int8_t nr = r + dr[d], nc = c + dc[d];
      if (nr < 0 || nr >= N || nc < 0 || nc >= N) continue;

      if (dist[nr][nc] > dist[r][c] + 1) {              // 255 means unvisited
        dist[nr][nc] = dist[r][c] + 1;
        queueR[tail] = nr; queueC[tail] = nc; tail++;
      }
    }
  }
}

Questo è tutto l’algoritmo. Su un labirinto 16×16 visita al massimo 256 celle e richiede ben meno di un millisecondo su un Arduino: è per questo che rieseguire il flood fill per ogni nuova parete scoperta è completamente sostenibile e nessuno si preoccupa di usare aggiornamenti incrementali.

Registrare una parete su entrambi i lati

Il bug più comune del flood fill non riguarda affatto il riempimento. Una parete è condivisa tra due celle e registrarla soltanto da un lato produce una mappa in cui il robot può attraversarla in una direzione e non nell’altra:

void setWall(uint8_t r, uint8_t c, uint8_t dir) {
  walls[r][c] |= (1 << dir);

  const int8_t dr[4] = {-1, 0, 1, 0};
  const int8_t dc[4] = { 0, 1, 0, -1};
  const int8_t nr = r + dr[dir], nc = c + dc[dir];
  if (nr < 0 || nr >= N || nc < 0 || nc >= N) return;

  walls[nr][nc] |= (1 << ((dir + 2) % 4));   // the same wall, from the other side
}

L’espressione (dir + 2) % 4 è la direzione opposta: nord diventa sud, est diventa ovest. Il sintomo di questo errore è un robot che pianifica un percorso dritto attraverso una parete che lui stesso ha registrato, uno spettacolo davvero confondente.

Memoria su un Arduino

Un labirinto 16×16 nei 2 KB di SRAM di un Uno è impegnativo ma utilizzabile e conviene farne i conti prima di scoprirlo nel modo più difficile:

La coda è la parte costosa e la più facile da ridurre: un singolo array di byte impacchettati r<<4|c dimezza il consumo a 256 B. Se lo spazio è ancora stretto, impacchettare la mappa delle pareti a 2 bit per cella ne recupera altri 192 B. A questo punto la maggior parte delle persone sceglie un ESP32 o un Mega, ed è una decisione ragionevole, ma anche l’esercizio di farla entrare è istruttivo.

Scegliere le celle obiettivo

Un obiettivo Micromouse standard è un blocco 2×2 al centro, non una singola cella, e questo non è un dettaglio. Inizializzare tutte e quattro le celle con distanza 0 significa che il robot punta verso la faccia del blocco che riesce a raggiungere con il minore costo: è più veloce e robusto rispetto all’obiettivo di vincolarsi a una cella specifica dalla quale potrebbe dover avvicinarsi in una direzione scomoda.

Il codice qui sopra gestisce già questo caso: passa tutte e quattro le celle in goals e il flood fill inizia contemporaneamente da ognuna. È un vero vantaggio dell’approccio basato sul campo di distanza: più obiettivi non costano nulla, mentre A* richiederebbe un’euristica modificata.

Esplorare come si deve

Flood fill indica al robot dove andare in base a ciò che sa. Non dice nulla su ciò che dovrebbe imparare e un robot che scende soltanto il gradiente raggiungerà l’obiettivo senza aver visto gran parte del labirinto: il “percorso più breve” della corsa rapida sarà quindi il più breve soltanto tra i corridoi che il robot è per caso attraversato.

Il compromesso abituale nelle competizioni è la seconda o la terza riga: raggiungi l’obiettivo, poi propaga il riempimento verso l’inizio e percorri quel tragitto, rivelando naturalmente un insieme diverso di corridoi. Due traversate producono in genere una mappa abbastanza buona da mantenere la corsa rapida entro pochi punti percentuali dall’ottimale.

Risoluzione dei problemi

La quinta riga è quella importante e conviene dirlo chiaramente: l’algoritmo non è la parte difficile di un Micromouse. Flood fill è quaranta righe e puoi verificarlo completamente nel simulatore senza hardware. La parte difficile è che dopo dieci celle il robot non si trova più dove crede di trovarsi e un piano perfetto eseguito da una posizione fittizia finisce contro una parete.

Provalo tu stesso

Percorri il Simulatore di risoluzione del labirinto una cella alla volta e osserva il campo di distanza ricalcolarsi ogni volta che il robot scopre una parete. Vedere i numeri cambiare è il modo più rapido per capire perché il robot ha sempre un piano.