LSRB Path Simplification for Line Maze Robots

A line maze robot that only follows the left-hand rule will always reach the finish, and it will always take a ridiculous route to get there—down every dead end, back out again, wandering branches that led nowhere. LSRB is the trick that turns that first clumsy run into an optimal second run, using almost no memory and no map at all.

It needs one array of characters. That is the entire data structure.

Four symbols

Every time the robot leaves a junction, it appends one character describing what it did:

• L — turned left
• S — went straight
• R — turned right
• B — turned back, which only ever happens at a dead end

After the exploration run, that string is the path taken. It is also, buried inside it, the path that should have been taken.

The one insight

Every B in the string marks a mistake: the robot entered a branch that led nowhere and had to reverse out. The turn before the B and the turn after it were both part of that wasted detour.

So look at each B together with its neighbours—a three-character window like L B L. Those three moves took the robot into a dead end and back out, leaving it facing some direction. There is always a single turn that would have produced the same outcome without the detour. Replace the triple with that one turn and the dead end vanishes from the route.

Trace the example. The robot arrives at the middle junction heading east and takes the left branch (L), which is the spur going north. It dead-ends and reverses (B). Back at the junction heading south, it takes the left branch again (L), which now points east. Net effect: it entered heading east and left heading east. That is S—straight through.

The six substitutions

There are only six windows that can occur, because the middle character is always B and a B never appears next to another B:

Explored	Replace with
L B R	B
L B S	R
L B L	S
R B L	B
S B L	R
S B S	B

You can derive every row by adding up turn angles, counting left as −90°, straight as 0°, right as +90°, and back as 180°. L B L is −90 + 180 − 90 = 0°, which is S. S B S is 0 + 180 + 0 = 180°, which is B. The table is not something to memorise—it falls out of the arithmetic.

Applying it until it settles

One pass is not enough. Collapsing a detour can push two turns together that now form a new reducible window, so you scan repeatedly until a full pass changes nothing:

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

A long branch off the main corridor collapses one junction at a time, pass after pass, until nothing is left of it. When the loop exits, the string contains no B at all—which is the proof that it is finished, since any remaining dead-end detour would still show one.

Running the optimised route

The second run is much simpler than the first. There are no decisions left: the robot follows the line, and at each junction it consumes the next character from the simplified string and turns accordingly. Junction classification still matters—it needs to know it has reached a junction—but junction choice is now just reading the next symbol.

This is why maze robots look so much faster on their second run. It is not only that the route is shorter; it is that the robot no longer has to slow down, look, and think at every intersection. You can raise the base speed for the replay because every turn is known in advance.

What LSRB cannot do

LSRB works on a perfect maze—one with no loops, exactly one path between any two points. If the maze contains a cycle, the left-hand rule can circle forever and the substitution rules have no dead end to collapse.

Once loops are possible you need a real map and a graph search. That is the territory of flood fill, which builds a distance field over the whole maze and descends it, and which the Maze Solver Simulator runs after its exploration phase. LSRB is the right tool when the maze is a tree—which taped line mazes almost always are—and it costs a few dozen bytes where flood fill costs a full grid.