これは Pololu 3pi Robot User’s Guide ≫ 8.c. Left Hand on the Wall の非公式日本語訳です。
目次
前： 8.b. Working with Multiple C Files in Atmel Studio
次： 8.d. The Main Loop(s)
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:
ループなし迷路を解く基本的な方法は「左手法」と呼ばれます。本物の迷宮－石壁で建てられた人間サイズの迷路－を、あなたの左手を常に壁に添えながら通ることを想像して下さい。できる限り左に曲がり、他に出口がない交差点で右に曲がるだけです。ときどき、行き止まりに到達すると、右に180度回転して、いま来た道を戻り始めます。最終的には、ループがない限り、あなたの手は迷路全体の壁のそれぞれの端から端に沿って一度だけ移動し、入口に戻る道を見つけます。迷路のどこかにモンスターや財宝が置かれている部屋がある場合は、途中で見つけることができます。なぜなら、すべての通路をきっかり2回移動するからです。3piの迷路解決例では、この単純で信頼性のある方法を使用します：
// 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.
select_turn()によって返される値はturn()によって使用される値に対応するため、これらの関数はメインループでうまく連携します。