Pololu 3pi Robot - Manual (Page 34)

We’ll discuss the call to simplify_path() in the next section. Before that, let’s take a look at the second main loop,
which is very simple. All we do is drive to the next intersection and turn according to our records. After doing the last
recorded turn, the robot will be one segment away from the finish, which explains the final follow_segment() call in
the outline of maze_solve() above.
// SECOND MAIN LOOP BODY
follow_segment();
// Drive straight while slowing down, as before.
set_motors(50,50);
delay_ms(50);
set_motors(40,40);
delay_ms(200);
// Make a turn according to the instruction stored in
// path[i].
turn(path[i]);
8.e. Simplifying the Solution
After every turn, the length of the recorded path increases by 1. If your maze, for example, has a long zigzag
passageway with no side exits, you’ll see a sequence like ‘RLRLRLRL’ appear on the 3pi’s LCD. There’s no shortcut
that would get you through this section of the path faster than just following the left hand on the wall strategy.
However, whenever we encounter a dead end, we can simplify the path to something shorter.
Consider the sequence ‘LBL’, where ‘B’ stands for “back” and is the action taken when a dead end is encountered.
This is what happens if there is a left turn that branches off of a straight path and leads immediately to a dead end.
After turning 90° left, 180°, and 90° left again, the net effect is that the robot is heading in its original direction again.
The path can be simplified to a 0° turn: a single ‘S’. The following diagram depicts this scenario, showing the two
functionally equivalent paths from start to end:
Another example is a T-intersection with a dead end on the left: ‘LBS’. The turns are 90° left, 180°, and 0°, for a total
of 90° right. The sequence should be replaced with a single ‘R’.
In fact, whenever we have a sequence like ‘xBx’, we can replace all three turns with a turn corresponding to the total
angle, eliminating the U-turn and speeding up our solution. Here’s the code to handle this:
Pololu 3pi Robot User's Guide © 2001–2014 Pololu Corporation
8. Example Project #2: Maze Solving Page 34 of 63