Line Maze Solver Simulator with LSRB Routing

Controls

Mode picks between the full three-act run—explore, simplify, then speed-run—and jumping straight to the finished route. Run speed sets how fast the robot drives. Start, Pause and Step run it continuously or one move at a time, Reset replays the same maze, and New maze generates a fresh one. Focus the canvas and use Space, N, R, M and F for the same controls from the keyboard.

The route memory strip below the maze is the part worth watching. It fills in one symbol per move while the robot drives, then rewrites itself during the simplify phase as each substitution fires.

Theory

A line maze robot is built in two layers, and keeping them apart is what makes it tractable.

The lower layer is an ordinary line follower. An eight-channel reflectance array reads the tape, the readings collapse into a single weighted error, and a PID loop turns that error into two different wheel speeds. This layer knows nothing about mazes.

The upper layer only wakes up when the tape branches. It classifies the junction—left, right, T, cross, dead end, or finish—picks a branch by the left-hand rule, and appends one character to a string. The bar drawn across the robot’s nose in this simulator is that array, and you can watch a whole side light up as a branch opens.

The catch is that the instant reading is ambiguous. A T junction, a crossroads and the finish block all report every channel black. The robot has to commit past the junction and read again before it knows what it just crossed.

Algorithm

Exploration uses the left-hand rule: at every cell take the leftmost available option, and only turn back when a dead end leaves nothing else. On a maze with no loops that always reaches the finish, and it is stateless enough to verify by hand.

Every move appends a symbol. L, S and R are turns; B only ever appears where the robot reversed out of a dead end. So each B in the finished string marks a mistake, together with the turn before it and the turn after it.

That three-character window is always replaceable by a single turn, because the three moves are just angles that add up. Counting left as −90°, straight as 0°, right as +90° and back as 180°, L B L sums to 0°, which is S—drive straight through instead of entering the spur at all. The six substitution rules are that arithmetic, tabulated.

One pass is not enough: collapsing a detour can push two turns together that now form a new reducible window, so the rules are applied repeatedly until nothing changes. When the loop ends there is no B left in the string, which is the proof it is finished—any remaining dead end would still show one.

Source code

// 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 is the substitution table, and it is short because it is only angle arithmetic: add the two turns either side of the 180° reversal, wrap into ±180°, and map the result back to a symbol.

Circuit diagram

The robot this lab models is the one in the line maze solver build path: an Arduino Nano reading an eight-channel reflectance array on its analog pins, driving two geared motors through a TB6612FNG.

The wiring rule that matters most is the power split. The motor battery reaches the driver’s VM pin and nothing else; the Arduino’s 5 V supplies logic only; and every ground—board, driver, sensor array, battery negative—must be tied together, or the control signals have no reference and the failure is silent.