The Pledge algorithm (named after John Pledge of Exeter) can solve this problem. 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. However, unlike in 2D, this requires that the current orientation is known, to determine which direction is the first on the left or right.ĭisjoint (where walls are not connected to the outer boundary/boundary is not closed) mazes can be solved with the wall follower method, so long as the entrance and exit to the maze are on the outer walls of the maze.
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 apply. 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. See the Pledge Algorithm, below, for an alternative methodology. Because wall-following will always lead you back to where you started, if you come across your starting point a second time, you can conclude the maze is not simply-connected, and you should switch to an alternative wall not yet followed. Should it be the case that wall-following begins late, attempt to mark the position in which wall-following began. If the maze is not simply-connected and one begins wall-following at an arbitrary point inside the maze, one could find themselves trapped along a separate wall that loops around on itself and containing no entrances or exits. if the start or endpoints are in the center of the structure surrounded by passage loops, or the pathways cross over and under each other and such parts of the solution path are surrounded by passage loops), this method will not necessarily reach the goal.Īnother concern is that care should be taken to begin wall-following at the entrance to the maze. If the maze is not simply-connected (i.e. 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). Then wall following reduces to walking around a circle from start to finish. If the walls are connected, then they may be deformed into a loop or circle. The algorithm is a depth-first in-order tree traversal.Īnother perspective into why wall following works is topological. If the maze is 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 solver is guaranteed not to get lost and will reach a different exit if there is one otherwise, the algorithm will return to the entrance having traversed every corridor next to that connected section of walls at least once. The best-known rule for traversing mazes is the wall follower, also known as either the left-hand rule or the right-hand rule.
0 kommentar(er)
