Solving mazes is a problem that is ancient. At least as old as the stories of the minotaur and Theseus from Greek mythology.
It is hardly surprising then that there are a number of ways to go about solving a maze and that a lot of people have put work into maze solving.
What may surprise you is just how important the problem is, even in current times. Essentially the same problem occurs in routing printed circuit boards, sending network traffic around the Internet, autonomous agents and the artificial intelligence of game opponents.
Wall Following
Ask almost anyone how to get out of a maze and they will describe some form of wall following. Keep your hand on one wall and keep going, sooner or later you will get to the exit. This would be fine except for two things. Firstly, you may have to visit almost the entire maze before you find the exit so this can be a very slow technique. Secondly, the maze may have islands in it. Unless all the walls are eventually connected to the outside, you may wander around forever without reaching the exit.
There is a competition for wall-followers but you certainly will not succeed at the normal competition by following a wall. The maze designers will have made sure of that.
Bellman
This is the name of the flooding approach. Imagine pouring water into the maze. The water will fill the maze and the best route to where you want to be can be found by riding on the wavefront. Although this algorithm is generally called Bellman’s algorithm, there are a number of variations developed by other people such as Lee. I have been unable to find a really good chronology of these method and so I cannot really be sure who did what. As far as the micromouse builder is concerned, these algorithms are the simplest to understand and to implement.
Look elsewhere on here for some practical methods for solving the maze in a micromouse.
Tremaux
In about 1882, a fellow called Tremaux described a process for solving any maze. It was described in terms of a physical maze and I have made no attempt to put it into any machine related form. What he said was this.
- As you walk down the maze, draw a line on one side, say the left, of the path.
- When you come to a new junction, take any path.
- At a dead end, or a previously visited junction, turn around and walk back the way you came.
- If you are on a previously walked path and you come to a previously visited junction, take any new path if there is one available.
- Never go down a paths marked on both sides.
Tarry
In 1895, Tarry published a method for solving mazes. You will need a sack of rocks.
- When entering a cell for the first time, place three rocks at the entrance.
- If this is not your first visit, place only one rock
- Pick an exit according to the following rules, in order:
0 rocks – not been there before, drop two rocks and carry on
1 rock – we have come in from there and we can leave that way. Drop one rock and leave.
3 rocks – This is how we got here in the first place. Only leave that way if there is no other choice.
2 rocks – We have been out that way before so don’t go that way again. - Only drop rocks if there are none already except as directed above.
This method will find a route but not all routes. It may not visit all the maze and will not automatically find the shortest route.
Theseus
A long time ago in a land far away…
The secret to this method is to enlist the assistance of a friend who has a long ball of string. Don’t forget to go appropriately armed.