Micromouse bauen: Labyrinth-Roboter mit Flood-Fill

Was du baust

Einen Roboter, der in ein nie gesehenes Labyrinth gesetzt wird, die Mitte findet und dann auf der kürzesten Route zurückfährt, deren Existenz er beweisen kann.

Diese zweite Hälfte unterscheidet eine Micromouse von jedem anderen Roboter dieser Seite. Ein Linienfolger reagiert. Ein Ausweicher reagiert. Eine Micromouse erinnert sich – sie baut beim Fahren eine Karte und plant dann über Zellen, die sie nicht besucht hat. Es ist das kleinste komplette Robotikproblem: Sensorik, Bewegung, Kartierung und Planung – alles muss auf einmal gehen.

Die Zwei-Lauf-Strategie

Wettbewerbsmäuse bekommen mehrere Läufe und werden nach dem schnellsten gewertet. Daraus entsteht eine Strategie, die sich auch ohne Zeitnahme zu kopieren lohnt:

Lauf eins – erkunden. Vorsichtig fahren, aufzeichnen, welche Zellen welche Wände haben, und die Mitte erreichen. Tempo ist egal; die Karte ist das Produkt.

Lauf zwei – ausnutzen. Fertige Karte per Flood-Fill fluten, kürzeste Route berechnen und fahren, ohne anzuhalten, um schon Bekanntes zu tasten.

Die Trennung zählt, weil beide Läufe Gegensätzliches wollen. Erkunden will langsame, vorsichtige Bewegung und ständiges Tasten. Schnelllaufen will Entschlossenheit. Beides auf einmal zu versuchen ergibt einen Roboter, der beides schlecht kann.

Warum der Algorithmus nicht der schwere Teil ist

Flood-Fill ist wirklich simpel: Gib der Zielzelle Distanz 0, jedem Nachbarn 1 mehr als dem niedrigsten erreichbaren Nachbarn, und schreite dann immer zu einer niedrigeren Zahl. Es sind wenige Dutzend Zeilen, und auf einem Gitter ist es beweisbar kürzest.

Der schwere Teil ist, dass er voraussetzt, dass der Roboter weiß, in welcher Zelle er ist.

Eine falsch gezählte Zelle oder ein paar Mal 88° statt 90° gedreht, und der Planer löst nun das Labyrinth für einen Roboter, der woanders ist. Das Symptom macht wahnsinnig: Der Algorithmus ist perfekt, die Verdrahtung in Ordnung, und der Roboter fährt selbstbewusst in eine Wand.

Also steckt die Baureihenfolge unten den größten Aufwand in Bewegung und fügt den Planer zuletzt hinzu. Den Planer beweist du separat im Labyrinthlöser-Simulator, wo Position konstruktionsbedingt exakt ist – genau deshalb lohnt sich dortiges Simulieren zuerst.

Stückliste

Gesamt: ca. $70–95, plus Labyrinth.

Drei Distanzsensoren, nicht einer. Ein einzelner Frontsensor zwingt den Roboter zum Drehen, um zu schauen – was Zeit kostet und, weit schlimmer, bei jeder Beobachtung Steuerkursfehler einführt. Drei feste Sensoren lassen den Roboter alle drei Wände einer Zelle in einem Moment lesen, ohne sich zu bewegen. Das ist der Unterschied zwischen einer Maus, die verlässlich kartiert, und einer, die bei jeder Wandprüfung Fehler anhäuft.

Denke daran, dass alle drei VL53L0X-Sensoren auf Adresse 0x29 hochkommen – du brauchst also drei GPIOs an XSHUT, um sie nacheinander hochzufahren und Adressen neu zu vergeben – und das bei jedem Boot neu, weil die Änderung flüchtig ist.

Achte auf den RAM. Ein 16×16-Flood-Fill-Distanzfeld als uint8_t gespeichert sind 256 Byte, plus Wandkarte, plus Queue. Auf 2 KB eines Uno passt das – aber nur absichtlich, was selbst eine gute Übung ist und ein Grund, warum viele hier zum ESP32 wechseln.

Baureihenfolge

1 – Drei saubere Distanzmesswerte besorgen. Vorn, links, rechts, per VL53L0X-Time-of-Flight-Sensoren. Sie teilen einen I²C-Bus und booten auf derselben Adresse – also einen nach dem anderen hochfahren, indem du die anderen in Reset hältst und beim Start Adressen neu vergibst. Jeden an einer Wand bekannter Distanz bestätigen, bevor du etwas montierst.

2 – Geradeaus fahren und eckig drehen lassen. Das ist das echte Projekt. Folge Wandfolgen und präzise Drehungen: PID-Regelkreis auf die Seitensensoren zum Mittighalten, kreiselintegrierte Drehungen statt Encodercounts und Neu-Ausrichten an einer Vorderwand, wann immer eine da ist. Erst weitergehen, wenn der Roboter zehn Drehungen fahren kann und noch richtig schaut.

3 – Zellen verlässlich zählen. Encoder sagen vorher, wo eine Grenze sein sollte; die fallende Flanke einer Seitenwand bestätigt, wo sie wirklich ist. Bei Widerspruch der Wand glauben – sie ist eine physische Landmarke, keine akkumulierte Schätzung.

4 – Wände in eine Karte aufzeichnen. Zwei Bit pro Zelle für vier Wände, und ein 16×16-Labyrinth passt in wenige Hundert Byte. Aufzeichnen, was du siehst, sobald du es siehst.

5 – Flood-Fill hinzufügen. Jetzt hat der Planer ehrliche Daten. Distanzen neu berechnen, sobald eine neu entdeckte Wand den aktuellen Plan entwertet – dieses Umplanen ist der ganze Grund, warum Flood-Fill statt einer Einmalsuche genutzt wird.

Hardware-Notizen, die zählen

Klein schlägt schnell. Der Roboter muss in einer Zelle wenden. Ein enges Chassis mit Rädern nah am Drehzentrum wendet sauber; ein langes streift bei jeder Drehung Wände – und keine Abstimmung repariert Geometrie.

Spiel ist Steuerkursfehler. Jede Wendedrehung kehrt die Motoren um, und ein loses Getriebe verliert die ersten paar Grad – etwa 0,9° Steuerkurs auf 42-mm-Rad bei 4° Spiel. N20-Motoren mit Metallgetriebe gibt es aus diesem Grund.

Seitensensoren leicht vorn und angewinkelt montieren. Geradeaus zeigend sehen sie eine Wand erst, wenn sie perfekt danebenstehen – der Roboter erfährt also spät von der Wand. Ein kleiner Vorwärtswinkel gibt dem Regelkreis Vorschau.

Den Sensoren stabile Versorgung geben. Ein VL53L0X liefert auf einbrechender Schiene plausibel aussehende falsche Zahlen statt offensichtlich zu versagen – die schlimmste Fehlerart, weil sich die Karte mit Wänden füllt, die nicht da sind.

Wie gut aussieht

Zwei dieser Zeilen verdienen Betonung.

Wanderkennung kennt keine Teilpunkte. Eine falsch aufgezeichnete Wand verdirbt die Karte, Flood-Fill berechnet dann einen selbstbewussten Weg durch eine Wand, und der Schnelllauf fährt geradewegs hinein. Es gibt keine gnädige Degradation – weshalb der Erkundungslauf langsam fährt.

Die Driftzeilen sind das echte Projekt. Der Algorithmus ist nicht der schwere Teil – Flood-Fill sind etwa vierzig Zeilen, und du kannst ihn vollständig im Simulator ohne Hardware testen. Schwer ist, dass der Roboter nach zehn Zellen nicht mehr dort ist, wo er sich wähnt – und eine Maus, die 20 mm pro zehn Zellen driftet, berührt an der fernen Labyrinthseite eine Wand. Alles, was eine echte Micromouse funktionsfähig macht – Wandfolgekorrektur, kreiselgestützte Drehungen, Encoderkalibrierung –, existiert, um diese eine Zahl zu bekämpfen.

Wenn es schiefgeht

Fast jeder Eintrag dieser Tabelle ist ein Bewegungs- oder Tastfehler statt Algorithmus. Diese Verteilung ist das Nützlichste, was du vor Beginn wissen kannst – denn sie sagt dir, wohinein du deine Wochenenden steckst.

Willst du die Kartierungs- und Planungsideen ohne Hardware, fährt der Labyrinthlöser-Simulator dieselbe Zwei-Phasen-Strategie im Browser, und der Pfadplanungs- und Kartierungs-Lernpfad trägt sie weiter zu A* und SLAM. Für einen weit billigeren ersten Labyrinthroboter nutzt der Linien-Labyrinthlöser Band statt Wänden und braucht gar keine Distanzsensoren.