Wall Follower maze algorithm
The Wall Follower keeps one hand on the wall and walks, which always gets you out of a maze whose start and exit are on the outside wall.
How it works
This version keeps its left hand on the wall: at every step it tries to turn left, then straight, then right, then turns around. It never needs to remember where it has been.
If the start and exit are both on the maze's outer wall, following one wall is guaranteed to reach the exit, because that wall is one continuous line. It may walk down many dead ends and back on the way, so its walk is long; the white path shown is the walk with the back-tracking removed.
What to watch for
Watch it hug the left wall into every dead end and straight back out, sweeping the maze in one continuous line.
Properties
- Shortest path
- No
- Finds the exit
- Yes, when start and exit are on the outer wall
- Explores
- Often a lot of the maze
- Memory
- None
Race it
Same maze, same speed, first to the exit wins: Wall Follower vs Depth-First Search. Or put it in a gauntlet, where the winner stays on.
FAQ
Does the wall follower always work?
Only when the start and exit are on the same connected wall, like the outer edge. Inside a maze with loops it can circle an island forever.
Left hand or right hand?
Either works; they just explore the maze in opposite orders.