Linienlabyrinth-Simulator mit LSRB-Routing

Steuerung

Modus wählt zwischen vollem Dreiakter — erkunden, vereinfachen, dann Bestzeit fahren — und direktem Sprung zur fertigen Route. Fahrgeschwindigkeit setzt das Tempo. Start, Pause und Schritt fahren kontinuierlich oder Zug um Zug, Zurücksetzen wiederholt dasselbe Labyrinth, und Neues Labyrinth erzeugt ein frisches. Fokussiere die Zeichenfläche und nutze Leertaste, N, R, M und F für dieselben Funktionen per Tastatur.

Der Routenspeicher-Streifen unter dem Labyrinth ist der sehenswerte Teil. Er füllt sich pro Zug um ein Symbol, während der Roboter fährt, und schreibt sich in der Vereinfachungsphase um, wenn jede Ersetzung feuert.

Theorie

Ein Linienlabyrinth-Roboter ist in zwei Schichten gebaut, und sie getrennt zu halten macht ihn handhabbar.

Die untere Schicht ist ein gewöhnlicher Linienfolger. Ein Achtkanal-Reflexionsarray liest das Band, die Messwerte kollabieren zu einem einzigen gewichteten Fehler, und ein PID-Kreis macht daraus zwei verschiedene Raddrehzahlen. Diese Schicht weiß nichts über Labyrinthe.

Die obere Schicht wacht nur auf, wenn das Band verzweigt. Sie klassifiziert die Kreuzung — links, rechts, T, Kreuz, Sackgasse oder Ziel — wählt per Linke-Hand-Regel einen Abzweig und hängt ein Zeichen an eine Zeichenkette. Der quer über die Roboternase gezeichnete Balken in diesem Simulator ist dieses Array, und du kannst zusehen, wie eine ganze Seite aufleuchtet, wenn sich ein Abzweig öffnet.

Der Haken: Die Momentanlesung ist mehrdeutig. T-Kreuzung, Vierweg und Zielblock melden alle jeden Kanal schwarz. Der Roboter muss sich über die Kreuzung hinaus festlegen und erneut lesen, bevor er weiß, was er gerade querte.

Algorithmus

Erkundung nutzt die Linke-Hand-Regel: An jeder Zelle die linkeste verfügbare Option nehmen und nur umkehren, wenn eine Sackgasse nichts anderes lässt. In einem Labyrinth ohne Schleifen erreicht das immer das Ziel und ist zustandslos genug, um es von Hand zu prüfen.

Jeder Zug hängt ein Symbol an. L, S und R sind Abbiegungen; B erscheint nur, wo der Roboter aus einer Sackgasse zurücksetzte. Jedes B in der fertigen Zeichenkette markiert also einen Fehler samt Zug davor und danach.

Dieses Dreizeichenfenster ist immer durch einen einzigen Zug ersetzbar, denn die drei Züge sind nur Winkel, die sich addieren. Mit links als −90°, geradeaus als 0°, rechts als +90° und zurück als 180° summiert sich L B L zu 0°, also S — fahre geradeaus durch statt in den Stichweg. Die sechs Ersetzungsregeln sind diese Arithmetik, tabelliert.

Ein Durchlauf genügt nicht: Das Falten eines Umwegs kann zwei Züge zusammenschieben, die nun ein neues reduzierbares Fenster bilden — die Regeln laufen daher wiederholt, bis sich nichts mehr ändert. Wenn die Schleife endet, bleibt kein B in der Zeichenkette — das ist der Beweis des Abschlusses, denn jede restliche Sackgasse zeigte noch eines.

Quellcode

// Repeat until a full pass changes nothing: collapsing one detour
// can push two turns together that are themselves reducible.
void simplify(String& route) {
  bool changed = true;
  while (changed) {
    changed = false;
    for (int i = 1; i + 1 < route.length(); i++) {
      if (route[i] != 'B') continue;          // windows centre on a turn-back
      route = route.substring(0, i - 1)
            + fold(route[i - 1], route[i + 1])
            + route.substring(i + 2);
      changed = true;
      break;
    }
  }
}

fold ist die Ersetzungstabelle und kurz, denn es ist nur Winkelarithmetik: Beide Züge um die 180°-Kehrtwende addieren, in ±180° wickeln und Ergebnis zurück auf ein Symbol abbilden.

Annahmen und Unterschiede zur Hardware

Klebeband ist als perfektes Schwarz auf perfektem Weiß gerendert, ohne Wölbung, Glanz oder Schatten, und das Reflexionsarray meldet ideale Binärwerte bei fester Höhe. Ein echtes IR-Array sieht Graustufen-Reflexionen, die sich mit Umgebungslicht, Sensorhöhe und Bandverschleiß verschieben — jeder Hardware-Lauf muss daher Weiß und Schwarz per Schwenk kalibrieren, wie der Verdrahtungsabschnitt notiert. Der Simulator fährt den PID-Kreis zudem in perfekter Periode und rückt pro Entscheidung eine saubere Zelle vor; auf einem Arduino erscheinen Schleifenjitter, Schlupf und 2-mm-Montageoffset als Fehlklassifikationen von Kreuzungen. Behandle Verstärkungen und LSRB-Zeichenkette hier als zu übertragende Logik, nicht als zu kopierende Zahlen.

Schaltplan

Der Roboter, den dieses Labor modelliert, ist der aus dem Linienlabyrinth-Baupfad: Ein Arduino Nano liest ein Achtkanal-Reflexionsarray an seinen Analogeingängen und treibt zwei Getriebemotoren über einen TB6612FNG.

Die wichtigste Verdrahtungsregel ist die Leistungstrennung. Die Motorbatterie erreicht den VM-Pin des Treibers und nichts sonst; die 5 V des Arduino versorgen nur Logik; und jede Masse — Board, Treiber, Sensorarray, Batterieminus — muss verbunden sein, sonst haben die Steuersignale keine Referenz, und der Fehler bleibt stumm.