LSRB-Pfadvereinfachung für Linienlabyrinth-Roboter

Ein Linienlabyrinth-Roboter, der nur der Linke-Hand-Regel folgt, erreicht das Ziel immer – und nimmt dafür immer eine absurde Route: jede Sackgasse hinunter, wieder hinaus, wandernde Abzweigungen, die nirgendwohin führten. LSRB ist der Trick, der aus diesem ersten tollpatschigen Lauf einen optimalen zweiten Lauf macht – mit fast keinem Speicher und gar keiner Karte.

Es braucht ein Zeichenarray. Das ist die gesamte Datenstruktur.

Vier Symbole

Jedes Mal, wenn der Roboter eine Kreuzung verlässt, hängt er ein Zeichen an, das beschreibt, was er tat:

• L – links abgebogen
• S – geradeaus gefahren
• R – rechts abgebogen
• B – umgekehrt, was nur je an einer Sackgasse geschieht

Nach dem Erkundungslauf ist diese Zeichenkette der gefahrene Pfad. Sie ist außerdem, darin vergraben, der Pfad, der hätte gefahren werden sollen.

Die eine Einsicht

Jedes B in der Zeichenkette markiert einen Fehler: Der Roboter fuhr in einen Abzweig, der nirgendwohin führte, und musste rückwärts hinaus. Die Drehung vor dem B wie die danach gehörten beide zu diesem vergeudeten Umweg.

Jedes B also gemeinsam mit seinen Nachbarn betrachten – ein Drei-Zeichen-Fenster wie L B L. Diese drei Züge führten den Roboter in eine Sackgasse und wieder hinaus und ließen ihn in eine Richtung zeigen. Es gibt immer eine einzelne Drehung, die dasselbe Ergebnis ohne Umweg erzeugt hätte. Das Tripel durch diese eine Drehung ersetzen und die Sackgasse verschwindet aus der Route.

Das Beispiel nachvollziehen. Der Roboter erreicht die mittlere Kreuzung ostwärts fahrend und nimmt den linken Abzweig (L) – den Sporn nach Norden. Er endet sackgassen und kehrt um (B). Zurück an der Kreuzung südwärts fahrend nimmt er erneut den linken Abzweig (L), der nun ostwärts zeigt. Nettoeffekt: Er fuhr ostwärts hinein und ostwärts hinaus. Das ist S – geradeaus durch.

Die sechs Ersetzungen

Es gibt nur sechs Fenster, die auftreten können – denn das mittlere Zeichen ist immer B und ein B steht nie neben einem anderen B:

Jede Zeile lässt sich per Aufsummieren von Drehwinkeln herleiten – links als −90°, geradeaus als 0°, rechts als +90° und umkehren als 180° zählen. L B L ist −90 + 180 − 90 = 0°, also S. S B S ist 0 + 180 + 0 = 180°, also B. Die Tabelle ist nichts zum Auswendiglernen – sie fällt aus der Rechnung.

Anwenden, bis es sich setzt

Ein Durchgang reicht nicht. Einen Umweg zu kollabieren kann zwei Drehungen zusammenschieben, die nun ein neues reduzierbares Fenster bilden – also wiederholt scannen, bis ein voller Durchgang nichts mehr ändert:

void simplify(String& path) {
  bool changed = true;
  while (changed) {                       // a collapse can expose another
    changed = false;
    for (int i = 0; i + 2 < path.length(); i++) {
      if (path[i + 1] != 'B') continue;   // only windows centred on a turn-back
      path = path.substring(0, i) + fold(path[i], path[i + 2])
                                   + path.substring(i + 3);
      changed = true;
      break;
    }
  }
}

Ein langer Abzweig vom Hauptkorridor kollabiert Durchgang für Durchgang eine Kreuzung nach der anderen, bis nichts von ihm übrig ist. Wenn die Schleife austritt, enthält die Zeichenkette gar kein B mehr – der Beweis, dass sie fertig ist: Denn jeder übrige Sackgassenumweg würde weiter eines zeigen.

Die optimierte Route fahren

Der zweite Lauf ist weit einfacher als der erste. Keine Entscheidungen bleiben: Der Roboter folgt der Linie, und an jeder Kreuzung verbraucht er das nächste Zeichen aus der vereinfachten Zeichenkette und biegt entsprechend ab. Kreuzungsklassierung zählt weiter – er muss wissen, dass er eine Kreuzung erreichte –, doch Kreuzungswahl ist nun nur das nächste Symbol lesen.

Darum sehen Labyrinthroboter im zweiten Lauf so viel schneller aus. Nicht nur ist die Route kürzer; der Roboter muss an keiner Kreuzung mehr langsamer werden, schauen und denken. Man kann die Grundgeschwindigkeit für die Wiederholung erhöhen, weil jede Drehung im Voraus bekannt ist.

Was LSRB nicht kann

LSRB arbeitet auf einem perfekten Labyrinth – ohne Schleifen, exakt ein Pfad zwischen zwei beliebigen Punkten. Enthält das Labyrinth einen Kreis, kann die Linke-Hand-Regel ewig kreisen und die Ersetzungsregeln haben keine Sackgasse zum Kollabieren.

Sobald Schleifen möglich sind, braucht man eine echte Karte und eine Graphensuche. Das ist das Gebiet von Flood Fill, das ein Distanzfeld über das ganze Labyrinth aufbaut und hinabsteigt, und das der Labyrinthlöser-Simulator nach seiner Erkundungsphase fährt. LSRB ist das richtige Werkzeug, wenn das Labyrinth ein Baum ist – was geklebte Linienlabyrinthe fast immer sind –, und es kostet wenige Dutzend Bytes, wo Flood Fill ein volles Raster kostet.