|
Maze - Game Web |
|
 A maze is a complex tour puzzle in the form of a complex branching passage through which the solver must find a route. This is different from a labyrinth, which has an actual through-route and is not designed to be difficult to navigate (despite the common uses of the word to indicate various complex, confusing structures). The pathways and walls in a maze or labyrinth are fixed (pre-determined). Maze-type puzzles where the given walls and paths may change during the game are covered under the main puzzle category of tour puzzles.
Maze construction
Mazes have been built with walls and rooms, with hedges, turf, or with paving stones of contrasting colors or designs, or in fields of crops such as corn or, indeed, maize. Maize mazes can be very large; they are usually only kept for one growing season, so they can be different every year, and are promoted as seasonal tourist attractions. One type of maze consists of a set of rooms linked by doors (so a passageway is just another room in this definition). Players enter at one spot, and exit at another, or the idea may be to reach a certain spot in the maze. Mazes can also be printed or drawn on paper to be followed by a pencil or fingertip. One of the short stories of Jorge Luis Borges featured a book, called The Garden of Forking Paths, that was a literary maze. Various maze generation algorithms exist for building mazes, either by hand or by computer.
Generating mazes
There are many different approaches to automate the generation of mazes.
Stack-based approach
This is one of the simplest ways to generate a maze using a computer. Consider the space for a maze being a large grid of cells (like a large chess board), each cell starting with four walls. Starting from a random cell, the computer then selects a random neighbouring cell that has not yet been visited. The computer removes the 'wall' between the two cells and adds the new cell to a stack (this is analogous to drawing the line on the floor). The computer continues this process, with a cell that has no unvisited neighbours being considered a dead-end. When at a dead-end it backtracks through the path until it reaches a cell with an unvisited neighbour, continuing the path generation by visiting this new, unvisited cell (creating a new junction). This process continues until every cell has been visited, causing the computer to backtrack all the way back to the beginning cell. This approach guarantees that the maze space is completely visited.
As stated, the algorithm is very simple and does not produce overly-complex mazes. More specific refinements to the algorithm can help to generate mazes that are harder to solve.
Solving mazes
The mathematician Leonhard Euler was one of the first to analyze plane mazes mathematically, and in doing so made the first significant contributions to the branch of mathematics known as topology.
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.
The following algorithms are designed to be used inside the maze by a traveler with no prior knowledge of the maze.
Random mouse algorithm
This is a trivial method that can be implemented by a very unintelligent robot or perhaps a mouse. It is simply to proceed in a straight line until an obstruction is reached, and then to make a random decision about the next direction to follow.
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 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, as seen in the following video. Then wall following reduces to walking around a circle from start to finish.
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.
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 Exeter) can solve this problem (see "Turtle Geometry: the computer as a medium for exploring mathematics", Abelson & diSessa, 1980).
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.
Note that the use of "total turning" rather than just the "current direction" allows the algorithm to avoid traps shaped like an upper case "G". If one proceeds left into the trap, one gets turned around a full 360 degrees by the walls. A naive "current direction" algorithm gets into a limit cycle as it leaves the lower rightmost wall heading left and runs into the curved section on the left again. The Pledge algorithm does not leave the rightmost wall due to the total turning not being zero at that point. It follows the wall all the way around, finally leaving it heading left on the bottom outside.
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.
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 was referenced in The Simpsons episode Stop, or My Dog Will Shoot! when Lisa proposes this method for finding the exit of a tricky corn maze.
Mazes in psychology experiments
Mazes are often used in psychology experiments to study spatial navigation and learning. Such experiments typically use rats or mice. Examples are:- the Barnes maze,
- the Morris water maze,
- the radial arm maze.
Mazes in computer games
Mazes have long been a staple element in video games. In some games the entire objective of the game is to navigating mazes, while in other games the mazes are incorporated as only one element of the gameplay. See Video_game_genres#Maze, and List_of_maze_video_games.
Other types of mazes- Logic mazes - These are like standard mazes except they use rules other than "don't cross the lines" to restrict motion.
- Mazes in higher dimensions - It is possible for a maze to have three or more dimensions. A maze with bridges is three dimensional, and some natural cave systems are three dimensional mazes. The computer game Descent utilized fully three dimensional mazes. Any maze can be topologically mapped onto a three-dimensional maze.
- Picture maze - See Picture maze. A maze that forms a picture when solved.
- Dead end maze - A maze game where the route creates the dead ends.
- Turf mazes and Mizmazes - A pattern like a long rope folded up, without any junctions or crossings.
|
|
Games
