What is maze theory?

Maze Theory are a restless team of digital creatives on a mission to conquer the world of virtual reality. We believe in pushing and redrawing the boundaries of the imagination and bringing to life virtual entertainment experiences that will engage and blow the senses.

A maze is a path or collection of paths, typically from an entrance to a goal. The word is used to refer both to branching tour puzzles through which the solver must find a route, and to simpler non-branching ("unicursal") patterns that lead unambiguously through a convoluted layout to a goal. The term "labyrinth" is generally synonymous with "maze", but can also connote specifically a unicursal pattern. The pathways and walls in a maze are typically fixed, but puzzles in which the walls and paths can change during the game are also categorised as mazes or tour puzzles.

Mazes have been built with walls and rooms, with hedges, turf, corn stalks, straw bales, books, paving stones of contrasting colors or designs, and brick, 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.

Indoors, mirror mazes are another form of maze, in which many of the apparent pathways are imaginary routes seen through multiple reflections in mirrors. Another 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. Mazes can be built with snow.

Quality conventions for designing mazes differ according to the medium each maze is to be rendered in: Mazes to be walked by people should not reveal a closed end from a primary branch point, so that any person traversing the maze must walk further, in order to determine if a turn leads to a viable path. Mazes traced on paper typically use long, mostly parallel, convoluted routes, even for paths that are dead ends, so that a person tracing the maze has difficulty identifying dead ends while the pencil is set at a branch point.

Maze generation is the act of designing the layout of passages and walls within a maze. There are many different approaches to generating mazes, with various maze generation algorithms for building them, either by hand or automatically by computer.

There are two main mechanisms used to generate mazes. In "carving passages", one marks out the network of available routes. In building a maze by "adding walls", one lays out a set of obstructions within an open area. Most mazes drawn on paper are done by drawing the walls, with the spaces in between the markings composing the passages.

Maze solving is the act of finding a route through the maze from the start to finish. Some maze solving methods are designed to be used inside the maze by a traveler with no prior knowledge of the maze, whereas others are designed to be used by a person or computer program that can see the whole maze at once.

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.

Mazes are often used in psychology experiments to study spatial navigation and learning. Such experiments typically use rats or mice. Examples are:

Numerous mazes of different kinds have been drawn, painted, published in books and periodicals, used in advertising, in software, and sold as art. In the 1970s there occurred a publishing "maze craze" in which numerous books, and some magazines, were commercially available in nationwide outlets and devoted exclusively to mazes of a complexity that was able to challenge adults as well as children (for whom simple maze puzzles have long been provided both before, during, and since the 1970s "craze").

Some of the best-selling books in the 1970s and early 1980s included those produced by Vladimir Koziakin, Rick and Glory Brightfield, Dave Phillips, Larry Evans, and Greg Bright. Koziakin's works were predominantly of the standard two-dimensional "trace a line between the walls" variety. The works of the Brightfields had a similar two-dimensional form but used a variety of graphics-oriented "path obscuring" techniques. Although the routing was comparable to or simpler than Koziakin's mazes, the Brightfields' mazes did not allow the various pathway options to be discerned easily by the roving eye as it glanced about.

Greg Bright's works went beyond the standard published forms of the time by including "weave" mazes in which illustrated pathways can cross over and under each other. Bright's works also offered examples of extremely complex patterns of routing and optical illusions for the solver to work through. What Bright termed "mutually accessible centers" (The Great Maze Book, 1973) also called "braid" mazes, allowed a proliferation of paths flowing in spiral patterns from a central nexus and, rather than relying on "dead ends" to hinder progress, instead relied on an overabundance of pathway choices. Rather than have a single solution to the maze, Bright's routing often offered multiple equally valid routes from start to finish, with no loss of complexity or diminishment of solver difficulties because the result was that it became difficult for a solver to definitively "rule out" a particular pathway as unproductive. Some of Bright's innovative mazes had no "dead ends", although some clearly had looping sections (or "islands") that would cause careless explorers to keep looping back again and again to pathways they had already travelled.

The books of Larry Evans focused on 3-D structures, often with realistic perspective and architectural themes, and Bernard Myers (Supermazes No. 1) produced similar illustrations. Both Greg Bright (The Hole Maze Book) and Dave Phillips (The World's Most Difficult Maze) published maze books in which the sides of pages could be crossed over and in which holes could allow the pathways to cross from one page to another, and one side of a page to the other, thus enhancing the 3-D routing capacity of 2-D printed illustrations.

Adrian Fisher is both the most prolific contemporary author on mazes, and also one of the leading maze designers. His book The Amazing Book of Mazes (2006) contains examples and photographs of numerous methods of maze construction, several of which have been pioneered by Fisher; The Art of the Maze (Weidenfeld & Nicolson, 1990) contains a substantial history of the subject, whilst Mazes and Labyrinths (Shire Publications, 2004) is a useful introduction to the subject.

A recent book by Galen Wadzinski (The Ultimate Maze Book) offers formalized rules for more recent innovations that involve single-directional pathways, 3-D simulating illustrations, "key" and "ordered stop" mazes in which items must be collected or visited in particular orders to add to the difficulties of routing (such restrictions on pathway traveling and re-use are important in a printed book in which the limited amount of space on a printed page would otherwise place clear limits on the number of choices and pathways that can be contained within a single maze). Although these innovations are not all entirely new with Wadzinski, the book marks a significant advancement in published maze puzzles, offering expansions on the traditional puzzles that seem to have been fully informed by various video game innovations and designs, and adds new levels of challenge and complexity in both the design and the goals offered to the puzzle-solver in a printed format.

India

Chartwell Castle in Johannesburg claims to have the biggest known uninterrupted hedgerow maze in the Southern world, with over 900 conifers. It covers about 6000 sq.m. (approximately 1.5 acres), which is around 5 times bigger than The Hampton Court Maze. The center is about 12m × 12m. The maze was designed and laid out by Conrad Penny.

While ancient maze-like symbols have been found the world over the first recorded maze whose purpose was to confound its visitors comes from the Greek myth of the Minotaur and the labyrinth (see Maze Mythology). In the myth the hero Theseus enters the labyrinth, kills the Minotaur and escapes by following out a string he had been unrolling as he traveled.

Many coins and carvings depicting this labyrinth have been recovered. The depiction is virtually identical wherever it has been found, a single pathway with many twists and turns but no branching paths that leads to the exit (this is sometimes referred to as a unicursal maze, while a branching path is referred to as multicursal). This depiction has led historians and maze enthusiasts to refer to a labyrinth as a single twisting path. And has even led some to reinterpret the myth to accommodate this view of the labyrinth.

This conclusion overlooks several pieces of evidence: First, on the island of Crete itself, where the myth originated, the walls of the ancient throne room are covered in a maze pattern of branching paths. Second, the fact that the depictions on coins and carvings are all so similar suggests that it is a symbol, not a map, of the labyrinth. Lastly, and chiefly, the myth itself describes the maze as so incredibly complex that Theseus with his string is  the only person to ever find their way out.

While the people of Crete may have never constructed anything like such a labyrinth, and perhaps not even conceived of a maze design that could confound a visitor, there is no question that those relating the myth imagined the possibility of such as place.

Therefore, the redefinition of labyrinth by some academics is a complete misnomer. This is a case where the common understanding of the word is the most true to its origins. When most people hear “labyrinth” they think something like “super-maze.” While a normal maze is something you trace with a pencil or make in a cornfield, a labyrinth is a fantastical location from which one may never escape.

The single path (unicursal) ”maze” doesn’t fit the common, or classic, definition of a labyrinth or a maze. So what do we call it? I have relegated it to “a maze-like path.” I decided on “maze-like” because the path appears at first glance to be maze, but upon closer inspection it lacks the central elements that defines a classic maze, challenge and choice.

Maze purposes:

Mazes have essentially five possible purposes: to escape, to get the prize, to trace a path, to be a metaphor, to be a stage.

Escape: By far the most common purpose of a maze is to challenge the visitor to find the means of passing through and escaping. This is true of pencil and paper mazes and most hedge mazes. Most maze tile designs found in cathedrals and churches are actually maze-like paths as described above, which of course have traveling the path and exiting as the goal. The few tile floor which are true mazes have escape as the objective.

Prize: Sometimes the goal isn’t to get out, but to get something that is hidden in the maze, this is often followed by the goal of escaping with the prize. Gathering prizes is the goal of most board games that use a maze as a game board. Many hedge mazes have reaching the center as a goal, usually followed with a easy exit. North American corn mazes often have several locations one must find before exiting in order to “beat the maze.”

Trace: I have not encountered an example of a maze of this type, so I guess I invented it. But it is such an obvious purpose for a maze that I am sure someone must have made a pencil and paper version at some point. The idea is to provide many routes by which the maze can be traversed to the exit, which would make getting to the exit easy. The challenge is to find the path through the maze that outlines a particular shape, such as cross or a face, or perhaps a even a word. The tricky part of creating such a maze is making sure that the multitude of other routes don’t accidentally outline unintended shapes.

Metaphor: Any maze pattern traced on a surface of a church, cathedral, mosque, shrine, or secret society lodge, has a metaphorical purpose along with any other purpose it may serve (usually tracing a route of escape, but sometimes the artist hasn’t even bothered to create a correct path). If the pattern is a maze-like path the metaphorical meaning usually centers around the path of life or enlightenment. Traveling the path is meant to bring a calm assurance that all will be well, either because of God’s care or by achieving detachment from the turmoil of life. If the pattern is a true maze then the metaphorical meaning usually centers around the struggle of traversing the choices of life. The challenge of travelling the path is meant to bring awareness of the difficulty of successfully navigating life. Occasionally both types are used as a general symbol for complexity or secrecy.

Stage: Lastly, sometimes a maze is intended to act as a stage for a larger drama. This is the purpose behind the Minotaur’s labyrinth, to create a setting for the Minotaur to hunt. Many hedge mazes built in England’s Victorian era appear to have been created either as lawn decoration or to provide a secluded locale in an otherwise open landscape. Mazes in movies are likewise often just a backdrop within which the story unfolds.

Maze types:

Putting aside the maze-like path, mazes have four states that determine their primary composition: continuous or non-continuous; simple or overlapping; objective or extra-dimensional; static or dynamic. A choice must be made in regard to each of these bifurcated poles in order for a maze to exist.

Continuous or non-continuous: A continuous maze is a maze whose borders all connect to form one long branching single wall. To solve a continuous maze the visitor merely needs to put a hand on one wall and follow it. Eventually they will reach the exit or prize. A non-continuous maze is made up of more than one branching border, and as a result a person who follows one wall will only visit part of the maze. The minor addition of multiple branching borders has a huge consequence: non-continuous mazes are, in the abstract, infinitely more difficult to solve than continuous mazes.

Simple or overlapping: A simple maze is any maze the plan of which can be drawn on a single sheet of paper with no overlapping paths. This does not mean the maze itself is two dimensional  The maze may have towers and staircases aplenty but when all these ups and downs are mapped on paper the design can be twisted around until all the paths are flat without any path going over or under another. An overlapping maze is obviously a maze which requires at least one path to go over or under another path and therefore cannot be mapped out on paper without drawing a bridge or a tunnel. An overlapping maze is by definition a non-continuous maze, requiring at least five separate borders to construct. The overlapping maze is, potentially, infinitely more difficult to solve than even a non-continuous simple maze.

Objective or extra-dimensional: An objective maze obeys the laws of classical physics in its design, while an extra-dimensional maze breaks the rules of normal space. Extra-dimensional maze do not exist in reality but there are several examples in fiction such as in the Dr. Who serial, Castrovalva, the Apple II video game Star Maze, and the Escher inspired climax of the movie Labyrinth. The first two of these examples make use of an impossible “forever floor” in which the visitor always returns to where they were no matter which way they travel. The latter example makes use of impossible gravity to contort the maze’s pathways. There are many other ways to warp reality in a maze, here are a few: Time can be warped so that visitors must navigate the modified time stream as well as the physical maze – the recent video game Portal 2 makes impressive use of time shifting as a puzzle element. Direction of travel can be “magically” altered – the Apple II video game The Bard’s Tale included a magical trap that randomly changes the player’s direction of travel without the player’s knowledge, the game also includes the reality shifting element of a teleportation spell and trap. A maze with multi-dimensional aspects can be infinitely more difficult than one without.

Static or dynamic: A static maze is a maze that holds its shape and rules of motion, dynamic maze changes its shape, symbols, or the rules of motion. The most common dynamic maze involve walls which move, such as in the animated movie The Cat Returns (the cats of the cat kingdom wear the walls like a big backpack and secretly move them). An example of a change in motion is a door which is sometimes locks one direction, and other times the opposite direction. An example of a change in symbols is the classic Scooby Doo move of switching the direction of a sign, as happens in the movie Labyrinth (tiny creatures move the tiles with marks on them). In the movie the Wrath of the Titans a maze is depicted which moves on a huge clockwork mechanism, changing the maze and threatening to crush its victims. But perhaps the ultimate dynamic maze is the House from  House of Leaves. The maze within the House changes more and more the deeper you go to, till the maze is so unstable it becomes a void.

Maze mediums:

In our daily lives, mazes occur in three basic forms: physical, conceptual, and psychological.

Physical: Almost all patterns classified as mazes are physical. This includes not only such large scale mazes as hedge mazes, but also paper and pencil type mazes. A physical maze exists in a form that the medium used to build the maze can be touched.

Conceptual: A conceptional maze is a maze which exists as a definite series of links or relationships which have not been illustrated or constructed by the author. This is more than just a person’s mental image of a maze (though that would count as a conceptional maze), it is system which, while it is a true maze, has no physical form apart from the rules which define its existence. For instance, I challenge you to get from Labyrinthos.net to “snow flakes gone wild” in three clicks (yes it is possible). The rules of this game has transformed all the links between several dozen sites into a conceptional maze. The maze has been created not because of the existence of the links, but by the purpose I have attached to them.

Psychological: The psychological maze is a cliche but is a true maze none the less. A person’s psyche becomes a maze when a goal is attached, such as, make the individual laugh, buy something, give something, come to a realization. The person pursuing this goal may be the individual themselves, “How can I stop myself overeating,” or another person, “How do I get him to stop overeating?” but regardless, the goal is achieved by mapping and navigating a path through the person’s psyche. For instance, you forgot your anniversary and you are late getting home from work. You have five minutes to consider what you will say. Your goals: 1. Make your spouse feel as little hurt as possible. 2. Don’t get shouted at. Should you grovel, be upbeat, laugh about it, lie? This kind of maze is highly complex and dynamic (see above) but it goes a long way if the individual in question wants you to succeed.

The Ultimate Maze:

The ultimate maze is a fantasy but the form it would need to take is self evident. It needn’t be large or complex, but instead intelligently dynamic, always allowing the slimmest of possibilities of achieving the goal. If the goal is impossible, it ceases to be a classic maze, but that doesn’t mean reaching the goal needs to be likely…even a one in million chance counts. The ultimate maze is one in which random chance has been minimized and the maze itself is smarter than the visitor, constantly changing the maze to keep the visitor from having any more than a sliver of a chance of achieving the goal. The ultimate maze is the product of the “mind” of a mighty computer or a demon who keeps the carrot dangling seemingly just out of reach.

< BACK

A maze-solving algorithm is an automated method for solving a maze. The random mouse, wall follower, Pledge, and Trémaux's 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 "simply connected", or "perfect" mazes, and are equivalent to a tree in graph theory. 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.

This is a trivial method that can be implemented by a very unintelligent robot or perhaps a mouse. It is simply to proceed following the current passage until a junction is reached, and then to make a random decision about the next direction to follow. Although such a method would always eventually find the right solution, this algorithm can be extremely slow.

The best-known rule for traversing mazes is the wall follower, 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 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 algorithm is a depth-first in-order tree traversal.

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 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.

Another concern is that care should be taken to begin wall-following at the entrance to the maze. 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. Should it be the case that wall-following begins late, attempt to mark the position in which wall-following began. 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. See the Pledge Algorithm, below, for an alternative methodology.

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 apply. However, unlike in 2D, this requires that the current orientation is known, to determine which direction is the first on the left or right.

Disjoint (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. 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 John Pledge of Exeter) can solve this problem.

The Pledge algorithm, designed to circumvent obstacles, requires an arbitrarily chosen direction to go toward, which will be preferential. When an obstacle is met, one hand (say the right hand) is kept along the obstacle while the angles turned are counted (clockwise turn is positive, counter-clockwise turn is negative). When the solver is facing the original preferential 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 degrees 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 (note 360 degrees is not equal to 0 degrees). 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 their way from any point inside to an outer exit of any finite 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, 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, but it is not guaranteed to find the shortest route.

An entrance of a passage is either unvisited, marked once or marked twice. Note that marking an entrance is not the same as marking a junction or a passage, because a junction may have multiple entrances, and a passage has an entrance at both ends. Dead ends can be thought of as junctions with one entrance (imagine there being a room at each dead end).

The algorithm works according to the following rules:

The "turn around and return" rule effectively transforms any maze with loops into a simply connected one; whenever we find a path that would close a loop, we treat it as a dead end and return. Without this rule, it is possible to cut off one's access to still-unexplored parts of a maze if, instead of turning back, we arbitrarily pick another entrance.

When you finally reach the solution, entrances marked exactly once will indicate a way back to the start. If there is no exit, this method will take you back to the start where all entrances are marked twice. In this case each passage is walked down exactly twice, once in each direction. The resulting walk is called a bidirectional double-tracing.

Essentially, this algorithm, which was discovered in the 19th century, has been used about a hundred years later as depth-first search.

Dead-end filling is an algorithm for solving mazes that fills all dead ends, leaving only the correct ways unfilled. 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 since this method looks at the entire maze at once. The method is to

Note that some passages won't become parts of dead end passages until other dead ends are removed first. A video of dead-end filling in action can be seen to the right.

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 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.

If given an omniscient view of the maze, a simple recursive algorithm can tell one how to get to the end. The algorithm will be given a starting X and Y value. If the X and Y values are not on a wall, the method will call itself with all adjacent X and Y values, making sure that it did not already use those X and Y values before. If the X and Y values are those of the end location, it will save all the previous instances of the method as the correct path.

This is in effect a depth-first search expressed in term of grid points. The omniscient view prevents entering loops by memorization. Here is a sample code in Java:

The maze-routing algorithm is a low overhead method to find the way between any two locations of the maze. The algorithm is initially proposed for chip multiprocessors (CMPs) domain and guarantees to work for any grid-based maze. In addition to finding paths between two locations of the grid (maze), the algorithm can detect when there is no path between the source and destination. Also, the algorithm is to be used by an inside traveler with no prior knowledge of the maze with fixed memory complexity regardless of the maze size; requiring 4 variables in total for finding the path and detecting the unreachable locations. Nevertheless, the algorithm is not to find the shortest path.

Maze-routing algorithm uses the notion of Manhattan distance (MD) and relies on the property of grids that the MD increments/decrements exactly by 1 when moving from one location to any 4 neighboring locations. Here is the pseudocode without the capability to detect unreachable locations.

When a maze has multiple solutions, the solver may want to find the shortest path from start to finish. There are several algorithms to find shortest paths, most of them coming from graph theory. One such algorithm finds the shortest path by implementing a breadth-first search, 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. The breadth-first search in its simplest form has its limitations, like finding the shortest path in weighted graphs.