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.