Pololu 3pi Robot - Manual (Page 35)

// Path simplification. The strategy is that whenever we encounter a
// sequence xBx, we can simplify it by cutting out the dead end. For
// example, LBL -> S, because a single S bypasses the dead end
// represented by LBL.
void simplify_path()
{
// only simplify the path if the second-to-last turn was a 'B'
if(path_length < 3 || path[path_length-2] != 'B')
return;
int total_angle = 0;
int i;
for(i=1;i<=3;i++)
{
switch(path[path_length-i])
{
case 'R':
total_angle += 90;
break;
case 'L':
total_angle += 270;
break;
case 'B':
total_angle += 180;
break;
}
}
// Get the angle as a number between 0 and 360 degrees.
total_angle = total_angle % 360;
// Replace all of those turns with a single one.
switch(total_angle)
{
case 0:
path[path_length - 3] = 'S';
break;
case 90:
path[path_length - 3] = 'R';
break;
case 180:
path[path_length - 3] = 'B';
break;
case 270:
path[path_length - 3] = 'L';
break;
}
// The path is now two steps shorter.
path_length -= 2;
}
One interesting point about this code is that there are some sequences that should never be encountered by a left-
turning robot, like ‘RBR’, which would be replaced by ‘S’ according to this code. In a more advanced program, you
might want to keep track of inconsistencies like this, since they indicate some kind of a problem that could cause the
robot to get lost.
Now let’s step through a slightly more complicated maze, showing how we can simplify the path as we explore it:
Fully explore the maze using a left-hand-on-the-wall strategy.
Pololu 3pi Robot User's Guide © 2001–2014 Pololu Corporation
8. Example Project #2: Maze Solving Page 35 of 63