Labyrinthlöser-Simulator für Flood-Fill-Planung

Steuerung

Wähle einen Modus — Erkunden, dann Bestzeit oder Nur Bestzeit — und drücke Start oder gehe Zug um Zug mit Schritt vor. Neues Labyrinth baut ein frisches Zufallslabyrinth; Zurücksetzen wiederholt dasselbe. Drei Geschwindigkeiten, Tastaturkürzel und Vollbild halten den Lauf kontrollierbar. Fette Linien sind Labyrinthwände, schattierte Korridore alles Erkundete (Sackgassen inklusive), die fette Linie der kürzeste Flood-Fill-Pfad.

Theorie

Ein Gitterlabyrinth sind Zellen, verbunden über offene Kanten, mit Wänden zwischen dem Rest. Für die kürzeste Route muss ein Roboter das Labyrinth erst kennen — dieses Labor fährt daher zwei Phasen.

Erkunden. Der Roboter läuft per Tiefensuche mit Linke-Hand-Regel: An jeder Kreuzung links, wenn möglich, sonst geradeaus, dann rechts. In einer Sackgasse kehrt er zur letzten Kreuzung um und nimmt den nächsten Abzweig. Wiederholt, bis jede Zelle besucht ist, kartiert das das ganze Labyrinth — inklusive aller falschen Wege, die es auszuschließen galt.

Optimieren. Auf fertiger Karte weist Flood-Fill dem Ziel Distanz null zu und propagiert steigende Werte über jede offene Kante nach außen. Jede Zelle hält nun ihre Zieldistanz — der kürzeste Pfad heißt schlicht: Vom Start immer auf einen Nachbarn mit um eins niedrigerer Zahl treten. Diesen Pfad fährt der Roboter als Bestzeit — weit kürzer als das wandernde Erkunden.

Algorithmus

1. Erkunde das Labyrinth per Tiefensuche mit Linke-Hand-Regel und kehre aus jeder Sackgasse um, bis alle Zellen besucht sind.
2. Trage jede offene Kante auf beiden Seiten ein, sodass die fertige Karte jede Wand kennt.
3. Flute vom Ziel: Beschrifte es mit 0 und propagiere steigende Distanzen über jede offene Kante nach außen.
4. Lies den kürzesten Pfad aus dem Feld: Vom Start wiederholt auf einen Nachbarn mit um eins niedrigerer Distanz treten.
5. Fahre diesen Pfad als Bestzeit zum Ziel.
6. Vergleiche Erkundungslänge mit Kürzesten-Länge, um zu sehen, wie viel Herumirren die Karte sparte.

Quellcode

Halte Erkundung, Kartierung, Planung und Bewegung als getrennte Funktionen:

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

Diese Grenze macht denselben Planer testbar in diesem Browser-Labor, auf einem Desktop und auf dem finalen ESP32-Controller.

Annahmen und Unterschiede zur Hardware

Das Labor macht Kartieren sauber, indem es den schweren Teil einer echten Micromouse entfernt: Odometrie. Der simulierte Roboter fährt exakt eine Zelle pro Schritt ohne Schlupf, ohne Gyro-Bias und ohne 90°-Drehfehler, und seine drei Abstandssensoren melden Wände perfekt ohne Fehlalarme. Ein physischer ESP32-Aufbau sammelt jeden Zug Kurs- und Distanzfehler, muss sich an Wänden neu ausrichten und ToF-Messwerte gegen Sonnenlicht und Spannungseinbruch filtern — darum verbringen das Präzisionskurven-Tutorial und die Flood-Fill-Anleitung mehr Zeit mit Bewegung als mit Planung. Nutze diesen Simulator, um zu lernen, warum Flood-Fill neu plant — nicht, um deine Bewegungsschicht zu beweisen.

Schaltplan

Nutze einen externen Regler, bemessen für den Motor-Blockierstrom. ESP32 und Sensoren brauchen eine stabile Logikschiene, auch wenn Motoren umsteuern.