Doolhofoplossen met flood fill voor micromouse-robots

Flood fill is het algoritme dat de meeste Micromouse-wedstrijden wint, en het is een uitstekende introductie in het plannen onder onzekerheid. Anders dan bij padfinding uit een boek begint een doolhofrobot niet met de volledige kaart — hij moet muren ontdekken terwijl hij rijdt. Flood fill is precies daarvoor gebouwd. Kijk hem werken in de Maze Solver Simulator.

Een afstandsveld, geen pad

Flood fill geeft elke cel een getal: de afstand tot het doel. De doelcellen krijgen nul. Vanaf daar krijgt elke niet-geblokkeerde buurcel één meer dan haar laagste buur, en dat breidt zich uit totdat elke bereikbare cel een waarde heeft.

De robot bewaart nooit een route. Hij staat alleen in een cel, kijkt naar zijn buren, en stapt naar elke cel waarvan het getal precies één lager is. Het afstandsveld is het plan, en daarom herstelt hij soepel wanneer de kaart verandert.

Optimisme over onbekende muren

De robot kan het hele doolhof niet zien, dus flood fill behandelt elke muur die hij nog niet heeft waargenomen als open. Dat optimisme levert de kortst mogelijke schatting op en houdt de robot in beweging richting het doel in plaats van hem doelloos te laten verkennen.

Onthult een sensor een muur die als open werd aangenomen, dan legt de robot hem vast — aan beide kanten van de gedeelde rand — en berekent hij het afstandsveld opnieuw. Het plan corrigeert zichzelf, en de robot gaat verder vanaf waar hij is.

Waarom de eerste rit niet het kortste pad is

Een verrassing die vaak voorkomt: flood fill garandeert geen kortste route bij de eerste rit. Omdat hij op optimistische aannames werkte, vond hij een manier naar het doel, niet noodzakelijk de beste. Echte Micromouse-robots werken in twee fasen:

1. Een zoekrit die genoeg van het doolhof verkent om een nauwkeurige kaart te bouwen.
2. Een snelheidsrit over het kortste pad dat de voltooide kaart oplevert.

In het begin telt efficiënt verkennen zwaarder dan optimaliteit in de eerste rit.

Flood fill tegenover BFS en A*

Breadth-first search en A* plannen over een graaf die je al kent. Flood fill is ontworpen voor een doolhof dat je nog aan het ontdekken bent: hij vult telkens opnieuw wanneer er een nieuwe muur opduikt. Wiskundig is de vloed een breedte-eerst-berekening van afstanden — het verschil is dat flood fill verwacht dat de kaart blijft veranderen en dat opnieuw vullen goedkoop is.

Hij verslaat ook eenvoudig muurvolgen (houd altijd één hand aan een muur), dat geen doel in het midden van het doolhof kan bereiken en zelden een kort pad vindt.

De lus van waarnemen, plannen en bewegen

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

Houd waarnemen, in kaart brengen, plannen en bewegen als gescheiden stappen. Die grens is wat dezelfde planner laat draaien in een browsersimulator, op je desktop en op een ESP32 met echte afstandssensoren en encoders.

De vloed in het geheel

Het afstandsveld is een breedte-eerst-uitbreiding vanaf het doel, en het is kort genoeg om volledig uit te schrijven:

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++;
      }
    }
  }
}

Dat is het hele algoritme. Op een 16×16-doolhof bezoekt hij hoogstens 256 cellen en draait hij op een Arduino ruimschoots binnen een milliseconde — en daarom is opnieuw vullen bij elke nieuw ontdekte muur volledig betaalbaar, en waarom niemand moeite doet met incrementele updates.

Een muur aan beide kanten vastleggen

De meest voorkomende bug in flood fill zit helemaal niet in de vloed. Een muur wordt gedeeld door twee cellen, en hem aan slechts één kant vastleggen levert een kaart op waar de robot er in de ene richting doorheen kan en in de andere niet:

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
}

(dir + 2) % 4 is de tegenovergestelde richting — noord wordt zuid, oost wordt west. Het symptoom van een fout daarin is een robot die een route recht door een muur plant die hij zelf heeft vastgelegd, en dat is werkelijk verwarrend om te zien.

Geheugen op een Arduino

Een 16×16-doolhof in de 2 KB SRAM van een Uno is krap maar haalbaar, en de rekensom is de moeite waard voordat je het op de harde manier uitzoekt:

De wachtrij is het duurste deel en het makkelijkst te verkleinen: één array met samengepakte r<<4|c-bytes halveert hem naar 256 B. Zit je nog steeds krap, dan levert de muurkaart in 2 bits per cel nog eens 192 B op. De meeste mensen grijpen op dit punt naar een ESP32 of een Mega, en dat is een verdedigbare keuze — maar de oefening om het passend te maken is op zichzelf al leerzaam.

Doelcellen kiezen

Een standaard Micromouse-doel is een 2×2-blok in het midden, niet één cel, en dat is geen detail. Alle vier de cellen op afstand 0 zaaien betekent dat de robot kiest voor de zijde van het blok die hij het goedkoopst kan bereiken — wat sneller én robuuster is dan je vastleggen op één specifieke cel die je misschien alleen van een lastige kant kunt naderen.

De bovenstaande code handelt dit al af: geef alle vier de cellen mee in goals, en de vloed begint gelijktijdig vanaf elk ervan. Dat is een wezenlijk voordeel van de aanpak met een afstandsveld — meerdere doelen kosten niets, terwijl A* een aangepaste heuristiek nodig zou hebben.

Goed verkennen

Flood fill vertelt de robot waar hij heen moet gegeven wat hij weet. Hij zegt niets over wat hij zou moeten leren, en een robot die alleen maar de gradiënt afdaalt bereikt het doel zonder het meeste van het doolhof te hebben gezien — waardoor het “kortste pad” van de snelheidsrit alleen het kortste is onder de gangen die hij toevallig heeft gelopen.

Het gebruikelijke wedstrijdcompromis is de tweede of de derde rij: bereik het doel, vul dan terug richting het startpunt en rij die route, wat vanzelf een andere verzameling gangen onthult. Twee doorlopen leveren doorgaans een kaart op die goed genoeg is dat de snelheidsrit binnen een paar procent van optimaal ligt.

Storingzoeken

Die vijfde rij is de belangrijke, en die mag duidelijk gezegd worden: het algoritme is niet het moeilijke deel van een Micromouse. Flood fill is veertig regels en je kunt hem volledig controleren in de simulator zonder hardware. Het moeilijke deel is dat de robot na tien cellen niet meer staat waar hij denkt dat hij staat, en een perfect plan dat vanuit een fictieve positie wordt uitgevoerd in een muur rijdt.

Probeer het zelf

Stap cel voor cel door de Maze Solver Simulator en kijk hoe het afstandsveld telkens opnieuw wordt berekend zodra de robot een muur ontdekt. De getallen zien veranderen is de snelste manier om te begrijpen waarom de robot altijd een plan heeft.