Maze solving algorithm

Algorithms for solving mazes describe methods by which automates a way out of a maze can be found. There are algorithms that can a person trapped in a maze outside help, without them something about the maze white: the random path selection, the right-hand method, the Pledge algorithm and the Trémaux algorithm. In contrast, algorithms assume as the filling of dead ends or finding the shortest way out that the maze can be surveyed as a whole.

Mazes where you can not go in circles are also referred to as standard or perfect mazes. These are equivalent to a tree in the graph theory. This is intuitively clear if one imagines that one just bends the paths of perfect maze. If this is done in the right way, as the result of a tree looks very similar. Therefore, the graph theory also plays a large role in algorithms for solving mazes.

• 2.1 Populating dead ends
• 2.2 Finding the shortest way

Heuristics

Random path selection

This trivial method can be performed even by a very simple robot. It is simply so long to go straight ahead until you reach an intersection. There one chooses randomly for a direction in which one goes on. Because one way multiple times treading with this method, it generally takes a long time until you get to the exit. Nevertheless, one always reaches this.

Right -hand rule

The right-hand rule is the best known method to traverse a maze. One simply places his right hand on a wall of the maze, and then stops when passing through constant contact ( of course you can take the right and left hand use ). If all the walls are related or connected to the outside - that is, the maze is " simply connected " - guarantees the right-hand rule that you either reached a different outcome, or returns to the input.

There is a simple topological consideration that the right- hand rule as written: If the walls of the maze are related, they can be as long deform until they form a circle. The right-hand rule in this case leads to the fact that you hike around the circle from start to end. If one follows this idea even further and groups the connected components of the maze, the boundaries between these components, the solutions sought are accurate ( see opposite).

However, the right-hand rule may fail if the maze is not simply connected. This is for example the case when one puts on the first wall inside the maze, and the hand, for example, a part of this wall to a column. Then you walk forever in a circle. The right-hand rule is possibly useless when trying to achieve a specific goal within the maze.

The right-hand rule can be applied also in mazes with three or more dimensions. For this purpose, the crossings must in a well defined manner in a two-dimensional plane can be projected. Let, for example, in a three-dimensional maze "up" leading in " to the northwest " convert bearing veins or 'down' leading programs in " southeast " leading, one can apply the right- hand rule. However, it has - unlike in the two-dimensional case - the current orientation in the maze always be known in order to determine in which direction it or " left " goes " to the right".

Pledge algorithm

If input and output are connected to the outside wall, you can with the right - hand rule, find their way through a non- simply connected maze. If you start, however, in the interior of the maze, it can happen that you ever run at the right-hand rule along a wall in a circle, which is not connected to the output. The Pledge algorithm (named after Jon Pledge of Exeter) solves this problem (see " Turtle Geometry: the computer as a medium for exploring mathematics", Abelson & diSessa, 1980).

The Pledge algorithm, designed to circumnavigate obstacles, requires a random target direction. If you hit an obstacle, puts you a hand ( for example, getting the right ) on the obstacle and stops on the way forward to maintain contact. This one counts the angle to which one turns away when going forward from the target direction or missile? Onto the target direction. If you re- aligned in the target direction and is the sum of the rotations made ​​equal to zero, loosen the hand from the obstacle and goes straight again in the target direction.

The hand is only taken from the wall of the maze, if both conditions are met: " sum of turns made ​​equal to zero " and " current alignment equal to target direction." This prevents the algorithm to fall into traps that hold the shape of the capital letter " G". Suppose we enter from the right in the " G" and turns at the meeting on the left wall to the left, you turn 360 degrees. Would the algorithm provide now to leave the wall again because the current direction again consistent with the aim from the beginning, we would be caught in an endless loop. After you leave the lower right side of the "G" and go to the left, you again meet on the curved left side of the "G" and again makes a complete rotation. Pledge the algorithm exits, however, the lower right side of the "G " is not, as the " sum of the rotations made" not zero but 360 °. Instead, they continue to follow the wall, the inside of the "G" again leaves and takes the hand of the wall, if you look at s is at the bottom of the "G" and again looks to the left.

If there is a finite and fair two-dimensional maze, one can find with the Pledge algorithm and a compass from any point of the maze of the way out. Conversely, the algorithm does not work. So it is not possible with the Pledge algorithm in general, to find the entrance of a target inside the maze.

Trémaux algorithm

The Trémaux algorithm, invented by Charles Pierre Trémaux (1818-1895) in 1886, used markers, for example, on the ground, and is an efficient method to find the way out of a maze out. The algorithm is guaranteed to work in all mazes that have well-defined passages.

One way is either unvisited, simple or marked twice. At the beginning of a desired direction is selected (if there is more than one). Then each trodden passage of intersection is marked for intersection, for example with a line on the ground. When you reach an intersection at which one has never come (recognizable because there are no markings on the floor ), choose an arbitrary path in order to move on ( and marks it as described). When you reach the other hand, a marked crossing and is the corridor from which one comes straight, marked only once you turn around and go back ( and marks the passage a second time ). Otherwise one chooses a transition with as few marks ( and marked him as always). One finally reaches his goal, the direct route back to the start is marked with exactly one line.

If there is no output, you finally reach the starting point again, and all the transitions of the maze are marked with exactly two lines. In this case one has passed through every aisle of the maze exactly twice, once in each direction. The path is referred to as "bidirectional double- tracing".

Algorithm by Gaston Tarry

The French tax inspector Gaston Tarry (1843-1913) discovered in 1895 following solution algorithm for mazes:

With this method, the output is found guaranteed. Should the maze do not have an output, each intersection is visited and every course exactly twice trodden ( once in each direction ). The algorithm then stops again at the starting point. The method of Tarry 's it - other than the Pledge algorithm - also suitable to enter from outside in a maze and find a target inside. The algorithm of Trémaux is a special case of algorithm Tarry.

Knowledge of the entire maze

Filling of dead ends

Is the maze as a whole be surveyed, the approach can be found by filling any dead ends. The algorithm is suitable for mazes on paper or in a computer program, but not for people in an unknown maze. In this method, first all the dead ends are identified and these will be " filled in" to the next intersection. The following videos illustrate this process.

Since each step preserves the topology of the maze, the goal can not be unintentionally cut off from the start. In addition, the algorithm does not break "too early", since the result can not contain dead end. If, therefore, in a perfect maze - a maze where you can not go in a circle - filled all dead ends, only the approach remains. In a maze, where you can also go in a circle, all possible solutions.

Find the shortest way

If there are several potential solutions, it is interesting to know the shortest path from start to finish. This can be achieved, for example, with a breadth-first search. Using a queue while cells are examined in increasing distance from the starting point to the destination point is reached. From each visited cell must be noted how far it is away from the starting point ( or was entered by which neighboring cell from the current cell and therefore came into the queue ). The shortest approach is obtained by tracking the target point from the visited cells back to the starting point.