Maze solving algorithm
Encyclopedia
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 Trémaux algorithms are designed to be used inside the maze by a traveler with no prior knowledge of the maze, whereas the dead-end
filling and shortest 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
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.
or perhaps a mouse. It is simply to proceed in a straight line until a junction is reached, and then to make a random decision about the next direction to follow. Although theoretically such a method would always eventually find the right solution
, it is also possible that it never finds any solution
. Because the random mouse might walk any path multiple times, this algorithm is extremely slow.
, 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. 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.
Wall-following can be done in 3D or higher dimensional mazes if its higher dimensional passages can be projected onto the 2D plane in a deterministic manner. For example, if in a 3D maze "up" passages can be assumed to lead northwest, and "down" passages can be assumed to lead southeast, then standard wall following rules can then be applied. However, unlike in 2D, this requires that the current orientation be known, to determine which direction is the first on the left or right.
) can solve this problem.
The Pledge algorithm, designed to circumvent obstacles, requires an arbitrarily chosen direction to go toward. When an obstacle is met, one hand (say the right hand) is kept along the obstacle while the angles turned are counted. When the solver is facing the original direction again, and the angular sum of the turns made is 0, the solver leaves the obstacle and continues moving in its original direction.
The hand is removed from the wall only when both "sum of turns made" and "current heading" are at zero. This allows the algorithm to avoid traps shaped like an upper case letter "G". Assuming the algorithm turns left at the first wall, one gets turned around a full 360 degree
s by the walls. An algorithm that only keeps track of "current heading" leads into an infinite loop as it leaves the lower rightmost wall heading left and runs into the curved section on the left hand side again. The Pledge algorithm does not leave the rightmost wall due to the "sum of turns made" not being zero at that point. It follows the wall all the way around, finally leaving it heading left outside and just underneath the letter shape.
This algorithm allows a person with a compass to find his way from any point inside to an outer exit of any finite and fair two-dimensional maze, regardless of the initial position of the solver. However, this algorithm will not work in doing the reverse, namely finding the way from an entrance on the outside of a maze to some end goal within it.
A path is either unvisited, marked once or marked twice. Every time a direction is chosen it is marked by drawing a line on the floor (from junction to junction). In the beginning a random direction is chosen (if there is more than one).
On arriving at a junction that has not been visited before (no other marks), pick a random direction (and mark the path). When arriving at a marked junction and if your current path is marked only once then turn around and walk back (and mark the path a second time). If this is not the case, pick the direction with the fewest marks (and mark it, as always).
When you finally reach the solution, paths marked exactly once will indicate a direct way back to the start. If there is no exit, this method will take you back to the start where all paths are marked twice.
In this case each path is walked down exactly twice, once in each direction. The resulting walk is called a bidirectional double-tracing.
Essentially, this algorithm is a variant of depth-first search
.
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
, while another, the A* algorithm, uses a heuristic
technique. The breadth-first search algorithm uses a 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.
Algorithm
In mathematics and computer science, an algorithm is an effective method expressed as a finite list of well-defined instructions for calculating a function. Algorithms are used for calculation, data processing, and automated reasoning...
s, that is, automated methods for the solving of maze
Maze
A maze is a tour puzzle in the form of a complex branching passage through which the solver must find a route. In everyday speech, both maze and labyrinth denote a complex and confusing series of pathways, but technically the maze is distinguished from the labyrinth, as the labyrinth has a single...
s. A few important maze solving algorithms are explained below. The random mouse, wall follower, Pledge, and Trémaux algorithms are designed to be used inside the maze by a traveler with no prior knowledge of the maze, whereas the dead-end
Cul-de-sac
A cul-de-sac is a word of French origin referring to a dead end, close, no through road or court meaning dead-end street with only one inlet/outlet...
filling and shortest 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
Tree (graph theory)
In mathematics, more specifically graph theory, a tree is an undirected graph in which any two vertices are connected by exactly one simple path. In other words, any connected graph without cycles is a tree...
in graph theory. Thus many maze solving algorithms are closely related to graph theory
Graph theory
In mathematics and computer science, graph theory is the study of graphs, mathematical structures used to model pairwise relations between objects from a certain collection. A "graph" in this context refers to a collection of vertices or 'nodes' and a collection of edges that connect pairs of...
. 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.
Random mouse algorithm
This is a trivial method that can be implemented by a very unintelligent robotRobot
A robot is a mechanical or virtual intelligent agent that can perform tasks automatically or with guidance, typically by remote control. In practice a robot is usually an electro-mechanical machine that is guided by computer and electronic programming. Robots can be autonomous, semi-autonomous or...
or perhaps a mouse. It is simply to proceed in a straight line until a junction is reached, and then to make a random decision about the next direction to follow. Although theoretically such a method would always eventually find the right solution
Las Vegas algorithm
In computing, a Las Vegas algorithm is a randomized algorithm that always gives correct results; that is, it always produces the correct result or it informs about the failure. In other words, a Las Vegas algorithm does not gamble with the verity of the result; it gambles only with the resources...
, it is also possible that it never finds any solution
Termination analysis
In computer science, a termination analysis is program analysis which attempts to determine whether the evaluation of a given program will definitely terminate. Because the halting problem is undecidable, termination analysis cannot work correctly in all cases. The aim is to find the answer...
. Because the random mouse might walk any path multiple times, this algorithm is extremely slow.
Wall follower
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 connectedSimply connected space
In topology, a topological space is called simply connected if it is path-connected and every path between two points can be continuously transformed, staying within the space, into any other path while preserving the two endpoints in question .If a space is not simply connected, it is convenient...
, 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. 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.
Wall-following can be done in 3D or higher dimensional mazes if its higher dimensional passages can be projected onto the 2D plane in a deterministic manner. For example, if in a 3D maze "up" passages can be assumed to lead northwest, and "down" passages can be assumed to lead southeast, then standard wall following rules can then be applied. However, unlike in 2D, this requires that the current orientation be known, to determine which direction is the first on the left or right.
Pledge algorithm
Disjoint mazes can still be solved with the wall follower method, if the entrance and exit to the maze are on the outer walls of the maze. If however, the solver starts inside the maze, it might be on a section disjoint from the exit, and wall followers will continually go around their ring. The Pledge algorithm (named after Jon Pledge of ExeterExeter
Exeter is a historic city in Devon, England. It lies within the ceremonial county of Devon, of which it is the county town as well as the home of Devon County Council. Currently the administrative area has the status of a non-metropolitan district, and is therefore under the administration of the...
) can solve this problem.
The Pledge algorithm, designed to circumvent obstacles, requires an arbitrarily chosen direction to go toward. When an obstacle is met, one hand (say the right hand) is kept along the obstacle while the angles turned are counted. When the solver is facing the original direction again, and the angular sum of the turns made is 0, the solver leaves the obstacle and continues moving in its original direction.
The hand is removed from the wall only when both "sum of turns made" and "current heading" are at zero. This allows the algorithm to avoid traps shaped like an upper case letter "G". Assuming the algorithm turns left at the first wall, one gets turned around a full 360 degree
Degree (angle)
A degree , usually denoted by ° , is a measurement of plane angle, representing 1⁄360 of a full rotation; one degree is equivalent to π/180 radians...
s by the walls. An algorithm that only keeps track of "current heading" leads into an infinite loop as it leaves the lower rightmost wall heading left and runs into the curved section on the left hand side again. The Pledge algorithm does not leave the rightmost wall due to the "sum of turns made" not being zero at that point. It follows the wall all the way around, finally leaving it heading left outside and just underneath the letter shape.
This algorithm allows a person with a compass to find his way from any point inside to an outer exit of any finite and fair two-dimensional maze, regardless of the initial position of the solver. However, this algorithm will not work in doing the reverse, namely finding the way from an entrance on the outside of a maze to some end goal within it.
Trémaux's algorithm
Trémaux's algorithm, invented by Charles Pierre Trémaux, is an efficient method to find the way out of a maze that requires drawing lines on the floor to mark a path, and is guaranteed to work for all mazes that have well-defined passages.A path is either unvisited, marked once or marked twice. Every time a direction is chosen it is marked by drawing a line on the floor (from junction to junction). In the beginning a random direction is chosen (if there is more than one).
On arriving at a junction that has not been visited before (no other marks), pick a random direction (and mark the path). When arriving at a marked junction and if your current path is marked only once then turn around and walk back (and mark the path a second time). If this is not the case, pick the direction with the fewest marks (and mark it, as always).
When you finally reach the solution, paths marked exactly once will indicate a direct way back to the start. If there is no exit, this method will take you back to the start where all paths are marked twice.
In this case each path is walked down exactly twice, once in each direction. The resulting walk is called a bidirectional double-tracing.
Essentially, this algorithm is a variant of depth-first search
Depth-first search
Depth-first search is an algorithm for traversing or searching a tree, tree structure, or graph. One starts at the root and explores as far as possible along each branch before backtracking....
.
Dead-end filling
Dead-end filling is an algorithm for solving mazes that looks at the entire maze at once. It can be used for solving mazes on paper or with a computer program, but it is not useful to a person inside an unknown maze. The method is to 1) find all of the dead-ends in the maze, and then 2) "fill in" the path from each dead-end until the first junction met. A video of dead-end filling in action can be seen here: http://www.youtube.com/watch?v=yqZDYcpCGAIhttp://www.youtube.com/watch?v=FkueaIT6RSU&NR=1.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. One possible algorithm finds the shortest path by implementing a breadth-first searchBreadth-first search
In graph theory, breadth-first search is a graph search algorithm that begins at the root node and explores all the neighboring nodes...
, while another, the A* algorithm, uses a heuristic
Heuristic
Heuristic refers to experience-based techniques for problem solving, learning, and discovery. Heuristic methods are used to speed up the process of finding a satisfactory solution, where an exhaustive search is impractical...
technique. The breadth-first search algorithm uses a 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.
Azkaban algorithm
Any non-cursal maze with definite rectangular structure can be solved using this approach.The maze is represented as a two dimensional matrix and the Azkaban values are used to represent the weight of each box which denotes the available pathways.The open ends of the maze is detected if the box direction extends the row or column size of the matrix considering that the entry or exit point would be present in the corner of the maze. A(0,4) tree is derived using the values of the box. A path between two open ended points is noted and it is the direction to cross over the maze.See also
- Mazes
- Maze generation algorithmMaze generation algorithmMaze generation algorithms are automated methods for the creation of mazes.- Graph theory based methods :A maze can be generated by starting with a predetermined arrangement of cells with wall sites between them...
- "Stop or My Dog Will ShootStop or My Dog Will Shoot"Stop or My Dog Will Shoot!" is the twentieth episode of The Simpsons eighteenth season and first aired May 13, 2007. When Santa's Little Helper rescues a lost Homer, he becomes a local hero and the Simpsons decide to enroll him in Police Dog Academy, where he is teamed with Lou and they become a...
", an episode of The SimpsonsThe SimpsonsThe Simpsons is an American animated sitcom created by Matt Groening for the Fox Broadcasting Company. The series is a satirical parody of a middle class American lifestyle epitomized by its family of the same name, which consists of Homer, Marge, Bart, Lisa and Maggie...
in which LisaLisa SimpsonLisa Marie Simpson is a fictional main character in the animated television series The Simpsons. She is the middle child of the Simpson family. Voiced by Yeardley Smith, Lisa first appeared on television in The Tracey Ullman Show short "Good Night" on April 19, 1987. Cartoonist Matt Groening...
uses Tremaux's algorithm
External links
- Think Labyrinth: Maze algorithms (details on these and other maze solving algorithms)
- MazeBlog: Solving mazes using image analysis
- Maze generation and solving Java applet
- Video: Maze solving simulation