Maze-solving algorithm: Difference between revisions

Revision as of 13:16, 24 March 2009

Revision as of 09:53, 25 March 2009

Line 1:

There are a number of different '''maze solving [[algorithm]]s''', that is, automated methods for the solving of [[maze]]s. A few important maze solving algorithms are explained below. The random mouse, wall follower, pledge, and Tremaux [[algorithms]] are designed to be used inside the maze by a traveler with no prior knowledge of the maze, whereas the [[dead-end]] filling algorithmand isshortest path algorithms are designed to be used by a person or computer program that can see the whole maze at once.

Mazes containing no loops are known as "standard", or "perfect" mazes, and are equivalent to a [[Tree (graph theory)| ''tree'']] in graph theory. Thus many maze solving algorithms are closely related to [[graph theory]]. Intuitively, if one pulled and stretched out the paths in the maze in the proper way, the result could be made to resemble a tree <ref>http://www.youtube.com/watch?v=k1tSK5V1pds</ref>.

Line 29:

== Tremaux's algorithm ==

Tremaux's algorithm is an efficient method to find the way out of a maze that requires drawing a line on the floor to mark a path, and is guaranteed to work for all mazes that have well-defined passages. On arriving at a junction, pick a direction and mark it and the direction you came from. When arriving at a marked junction pick an unmarked passage if possible. If it is not possible to pick an unmarked passage take a marked one, marking it again (you can pick the path you came from). Never pick a twice marked path, where you will never need to take any passage more than twice. If there is no exit, this method will take you back to the start. Tremaux's algorithm effectively implements a [[depth-first search]].<ref>http://riemannsurfaces.info/OtherTopics/Maze%20search,%20Tremaux%20generalized.html</ref>

== Dead-end filling ==

Line 35:

Dead-end filling cannot accidentally "cut off" the start from the finish since each step of the process preserves the topology of the maze. Furthermore, the process won't stop "too soon" since the end result cannot contain any dead-ends. Thus if dead-end filling is done on a perfect maze (maze with no loops), then only the solution will remain. If it is done on a partially braid maze (maze with some loops), then every possible solution will remain but nothing more. [http://www.astrolog.org/labyrnth/algrithm.htm]

== Shortest path algorithm ==

When a maze has multiple solutions, the solver may want to find the shortest path from start to finish. This algorithm find the shortest path by implementing a [[breadth-first search]]. The algorithm uses a [[queue (data structure)|queue]] to visit cells in increasing distance order from the start until the finish is reached. Each visited cell needs to keep track of its distance from the start or which adjacent cell nearer to the start caused it to be added to the queue. When the finish ___location is found, follow the path of cells backwards to the start, which is the shortest path.

== References ==