8.c. Left Hand on the Wall

The basic strategy for solving a non-looped maze is called “left hand on the wall”. Imagine walking through a real labyrinth – a human-sized maze built with stone walls – while keeping your left hand on the wall at all times. You’ll turn left whenever possible and only turn right at an intersection if there is no other exit. Sometimes, when you reach a dead end, you’ll turn 180 degrees to the right and start walking back the way you came. Eventually, as long as there are no loops, your hand will travel along each length of wall in the entire labyrinth exactly once, and you’ll find your way back to the entrance. If there is a room somewhere in the labyrinth with a monster or some treasure, you’ll find that on the way, since you’ll travel down every hallway exactly twice. We use this simple, reliable strategy in our 3pi maze solving example:

// This function decides which way to turn during the learning phase of
// maze solving.  It uses the variables found_left, found_straight, and
// found_right, which indicate whether there is an exit in each of the
// three directions, applying the "left hand on the wall" strategy.
char select_turn(unsigned char found_left, unsigned char found_straight,
  unsigned char found_right)
{
	// Make a decision about how to turn.  The following code
	// implements a left-hand-on-the-wall strategy, where we always
	// turn as far to the left as possible.
	if(found_left)
		return 'L';
	else if(found_straight)
		return 'S';
	else if(found_right)
		return 'R';
	else
		return 'B';
}

The values returned by select_turn() correspond to the values used by turn(), so these functions will work nicely together in our main loop.

Related Products

Pololu 3pi Robot
3pi Robot + USB Programmer + Cable Combo
3pi Expansion Kit with Cutouts - Black
3pi Expansion Kit without Cutouts - Black
3pi Robot + USB Programmer Combo
Log In
Pololu Robotics & Electronics
Shopping cart
(702) 262-6648
Same-day shipping, worldwide
Menu
Shop Blog Forum Support
My account Comments or questions? About Pololu Contact Ordering information Distributors