Flood-Fill-Labyrinthlösen für Micromouse-Roboter

Flood Fill ist der Algorithmus, der die meisten Micromouse-Wettbewerbe gewinnt – und eine großartige Einführung in Planung unter Unsicherheit. Anders als Lehrbuchwegfindung startet ein Labyrinthroboter nicht mit der vollen Karte – er muss Wände beim Fahren entdecken. Genau dafür ist Flood Fill gebaut. Im Labyrinthlöser-Simulator laufen sehen.

Ein Distanzfeld, kein Pfad

Flood Fill weist jeder Zelle eine Zahl zu: ihre Entfernung zum Ziel. Die Zielzellen bekommen null. Von dort erhält jede Nachbarzelle, die nicht blockiert ist, eins mehr als ihr niedrigster Nachbar – Ausbreitung nach außen, bis jede erreichbare Zelle einen Wert hat.

Der Roboter speichert nie eine Route. Er steht in einer Zelle, schaut auf seine Nachbarn und tritt auf eine, deren Zahl exakt eins niedriger ist. Das Distanzfeld ist der Plan – weshalb es sich graceful erholt, wenn sich die Karte ändert.

Optimismus über unbekannte Wände

Der Roboter kann nicht das ganze Labyrinth sehen – Flood Fill behandelt also jede noch nicht gespürte Wand als offen. Dieser Optimismus erzeugt die kürzestmögliche Schätzung und hält den Roboter auf das Ziel zu in Bewegung statt ziellos erkunden.

Wenn ein Sensor eine Wand aufdeckt, die offen vermutet war, zeichnet der Roboter sie auf – auf beiden Seiten der gemeinsamen Kante – und berechnet das Distanzfeld neu. Der Plan korrigiert sich, und der Roboter fährt weiter, wo er ist.

Warum der erste Lauf nicht der kürzeste Pfad ist

Eine gängige Überraschung: Flood Fill garantiert im ersten Lauf nicht die kürzeste Route. Weil es auf optimistischen Annahmen handelte, fand es einen Weg zum Ziel, nicht unbedingt den besten. Echte Micromouse-Roboter nutzen zwei Phasen:

1. Einen Suchlauf, der genug Labyrinth erkundet, um eine genaue Karte zu bauen.
2. Einen Speedrun entlang des kürzesten Pfads, den die fertige Karte offenbart.

Anfangs zählt effizientes Erkunden mehr als Erstlaufoptimalität.

Flood Fill gegen BFS und A*

Breitensuche und A* planen über einen bereits bekannten Graphen. Flood Fill ist für ein Labyrinth entworfen, das noch entdeckt wird: Es flutet neu, wann immer eine neue Wand auftaucht. Mathematisch ist die Flut eine Breitensuche-Distanzberechnung – der Unterschied: Flood Fill erwartet, dass sich die Karte weiter ändert, und ist billig neu zu berechnen.

Es schlägt auch schlichtes Wandfolgen (immer eine Hand an der Wand), das ein Ziel in der Labyrinthmitte nicht erreicht und selten eine kurze Route findet.

Die Wahrnehmen-Planen-Fahren-Schleife

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

Wahrnehmung, Kartierung, Planung und Bewegung als getrennte Schritte halten. Diese Grenze lässt denselben Planer im Browsersimulator, auf dem Desktop und auf einem ESP32 mit echten Entfernungssensoren und Encodern laufen.

Die Flut, vollständig

Das Distanzfeld ist eine Breitensuche-Expansion vom Ziel – und kurz genug, um sie vollständig auszuschreiben:

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

Das ist der ganze Algorithmus. Auf einem 16×16-Labyrinth besucht er höchstens 256 Zellen und läuft auf einem Arduino deutlich unter einer Millisekunde – weshalb Neufluten bei jeder neu entdeckten Wand vollständig erschwinglich ist und sich niemand mit inkrementellen Updates aufhält.

Eine Wand auf beiden Seiten aufzeichnen

Der häufigste Flood-Fill-Fehler steckt gar nicht in der Flut. Eine Wand teilen sich zwei Zellen – und sie nur auf einer Seite aufzuzeichnen erzeugt eine Karte, in der der Roboter sie in eine Richtung passieren kann und in die andere nicht:

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
}

Das (dir + 2) % 4 ist die Gegenrichtung – Nord wird Süd, Ost wird West. Das Symptom bei Fehlern: Ein Roboter, der eine Route gerade durch eine Wand plant, die er selbst aufzeichnete – was wirklich verwirrend anzusehen ist.

Speicher, auf einem Arduino

Ein 16×16-Labyrinth auf 2 KB SRAM eines Uno ist eng, aber machbar – und die Rechnung lohnt sich, bevor man es auf die harte Art erfährt:

Die Queue ist der teure Teil und am leichtesten zu schrumpfen: Ein einzelnes Array gepackter r<<4|c-Bytes halbiert sie auf 256 B. Reicht es weiter nicht, holt Packen der Wandkarte in 2 Bits pro Zelle weitere 192 B zurück. Die meisten greifen hier stattdessen zu ESP32 oder Mega – eine vernünftige Entscheidung: Doch die Übung, es passend zu machen, lehrt selbst.

Zielzellen wählen

Ein Standard-Micromouse-Ziel ist ein 2×2-Block in der Mitte, keine einzelne Zelle – und das ist kein Detail. Alle vier Zellen mit Entfernung 0 zu setzen heißt: Der Roboter steuert an, welche Blockseite er am billigsten erreichen kann – schneller und robuster, als sich auf eine bestimmte Zelle festzulegen, die er aus unhandlicher Richtung anfahren müsste.

Der Code oben behandelt das bereits: Alle vier Zellen in goals übergeben, und die Flut beginnt von jeder gleichzeitig. Das ist ein echter Vorteil des Distanzfeldansatzes – mehrere Ziele kosten nichts, während A* eine modifizierte Heuristik bräuchte.

Ordentlich erkunden

Flood Fill sagt dem Roboter, wohin er gehen soll, gegeben was er weiß. Es sagt nichts darüber, was er lernen sollte – und ein Roboter, der nur je den Gradienten hinabsteigt, erreicht das Ziel, ohne den Großteil des Labyrinths gesehen zu haben: was die „kürzeste“ Speedrunstrecke nur unter den zufällig durchlaufenen Korridoren kürzest macht.

Der übliche Wettbewerbskompromiss ist die zweite oder dritte Zeile: Das Ziel erreichen, dann Richtung Start zurückfluten und das fahren – was natürlicherweise einen anderen Korridorsatz aufdeckt. Zwei Durchquerungen erzeugen typisch eine Karte, die gut genug ist, dass der Speedrun innerhalb weniger Prozent optimal liegt.

Fehlersuche

Die fünfte Zeile ist die wichtige – und lohnt klar auszusprechen: Der Algorithmus ist nicht der schwere Teil eines Micromouse. Flood Fill umfasst vierzig Zeilen und lässt sich im Simulator ohne Hardware vollständig verifizieren. Der schwere Teil: Nach zehn Zellen steht der Roboter nicht mehr dort, wo er glaubt – und ein perfekter Plan, von fiktiver Position ausgeführt, fährt in eine Wand.

Selbst ausprobieren

Den Labyrinthlöser-Simulator Zelle für Zelle durchgehen und zusehen, wie sich das Distanzfeld neu berechnet, sobald der Roboter eine Wand entdeckt. Die sich ändernden Zahlen zu sehen ist der schnellste Weg zu verstehen, warum der Roboter immer einen Plan hat.