Maze-solving algorithm: Difference between revisions

Revision as of 01:15, 31 July 2011

Revision as of 01:17, 31 July 2011

Line 12:

The wall follower, the best-known rule for traversing mazes, is also known as either the ''left-hand rule'' or the ''right-hand rule''. If the maze is [[Simply connected space|''simply connected'']], that is, all its walls are connected together or to the maze's outer boundary, then by keeping one hand in contact with one wall of the maze the player is guaranteed not to get lost and will reach a different exit if there is one; otherwise, he or she will return to the entrance.

Another perspective into why wall following works is topological. If the walls are connected, then they may be deformed into a loop or circle.<ref>http://www.youtube.com/watch?v=IIBwiGrUgzc</ref>. Then wall following reduces to walking around a circle from start to finish. To further this idea, notice that by grouping together connected components of the maze walls, the boundaries between these are precisely the solutions, even if there is more than one solution (see figures on the right).

If the maze is not simply connected (i.e. if the start or endpoints are in the center of the structure or the pathways cross over and under each other), this method will not be guaranteed to help the goal to be reached.