Maze Algorithms (1997)

Mazes in general (and hence algorithms to create Mazes) can be organized along seven different classifications. These are: Dimension, Hyperdimension, Topology, Tessellation, Routing, Texture, and Focus. A Maze can take one item from each of the classes in any combination.

Dimension: The dimension class is basically how many dimensions in space the Maze covers. Types are:

2D: Most Mazes, either on paper or life size, are this dimension, in which it's always possible to display the plan on the sheet of paper and navigate it without overlapping any other passages in the Maze. 3D: A three dimensional Maze is one with multiple levels, where (in the orthogonal case at least) passages may go up and down in addition to the four compass directions. A 3D Maze is often displayed as an array of 2D levels, with "up" and "down" staircase indicators. Higher dimensions: It's possible to have 4D and higher dimension Mazes. These are sometimes rendered as 3D Mazes, with special "portals" to travel through the 4th dimension, e.g. "past" and "future" portals. Weave: A weave Maze is basically a 2D (or more accurately a 2.5D) Maze, but where passages can overlap each other. In display it's generally obvious what's a dead end and what's a passage that goes underneath another. Life size Mazes that have bridges connecting one portion of the Maze to another are partially Weave.

Hyperdimension: The hyperdimension class refers to the dimension of the object you move through the Maze, as opposed to the dimension of the Maze environment itself. Types are:

Non-hypermaze: Virtually all Mazes, even those in higher dimensions or with special rules, are normal non-hypermazes. In them you work with a point or small object, such as a marble or yourself, which you move from point to point, and the path behind you forms a line. There's an easily countable number of choices at each point. Hypermaze: A hypermaze is where the solving object is more than just a point. A standard hypermaze (or a hypermaze of the 1st order) consists of a line where as you bend and move it the path behind it forms a surface. A hypermaze can only exist in a 3D or higher dimension environment, where the entrance to a hypermaze is also a line instead of a point. A hypermaze is fundamentally different since you need to be aware of and work with multiple parts along the line at the same time, where there's nearly an infinite number of states and things you can do with the line at any time. The solving line is infinite, or the endpoints are fixed outside of the hypermaze, to prevent one from crumpling the line into a point, which could then be treated as a non-hypermaze. Hyperhypermaze: Hypermazes can be of arbitrarily high dimension. A hyperhypermaze (or a hypermaze of the 2nd order) increases the dimension of the solving object again. Here the solving object is a plane, where as you move it the path behind you forms a solid. A hyperhypermaze can only exist in a 4D or higher dimension environment.

Topology: The topology class describes the geometry of the space the Maze as a whole exists in. Types are:

Normal: This is a standard Maze in Euclidean space. Planair: The term "planair" refers to any Maze with an abnormal topology. This usually means connecting the edges of the Maze in interesting fashions. Examples are Mazes on the surface of a cube, Mazes on the surface of a Moebius strip, and Mazes that are equivalent to being on a torus with the left and right sides wrapping and the top and bottom wrapping.

Tessellation: The tessellation class is the geometry of the individual cells that compose the Maze. Types are:

Orthogonal: This is a standard rectangular grid where cells have passages intersecting at right angles. In the context of tessellations, this can also be called a Gamma Maze. Delta: A Delta Maze is one composed of interlocking triangles, where each cell may have up to three passages connected to it. Sigma: A Sigma Maze is one composed of interlocking hexagons, where each cell may have up to six passages connected to it. Theta: Theta Mazes are composed of concentric circles of passages, where the start or finish is in the center, and the other on the outer edge. Cells usually have four possible passage connections, but may have more due to the greater number of cells in outer passage rings. Upsilon: Upsilon Mazes are composed of interlocking octagons and squares, where each cell may have up to eight or four possible passages connected to it. Zeta: A Zeta Maze is on a rectangular grid, except 45 degree angle diagonal passages between cells are allowed in addition to horizontal and vertical ones. Omega: The term "omega" refers to most any Maze with a consistent non-orthogonal tessellation. Delta, Sigma, Theta, and Upsilon Mazes are all of this type, as are many other arrangements one can think up, e.g. a Maze composed of pairs of right triangles. Crack: A crack Maze is an amorphous Maze without any consistent tessellation, but rather has walls or passages at random angles. Fractal: A fractal Maze is a Maze composed of smaller Mazes. A nested cell fractal Maze is a Maze with other Mazes tessellated within each cell, where the process may be repeated multiple times. An infinite recursive fractal Maze is a true fractal, where the Maze contains copies of itself, and is in effect an infinitely large Maze.

Routing: The routing class is probably the most interesting with respect to Maze generation itself. It refers to the types of passages within whatever geometry defined in the categories above.

Perfect: A "perfect" Maze means one without any loops or closed circuits, and without any inaccessible areas. Also called a simply-connected Maze. From each point, there is exactly one path to any other point. The Maze has exactly one solution. In Computer Science terms, such a Maze can be described as a spanning tree over the set of cells or vertices. Braid: A "braid" Maze means one without any dead ends. Also called a purely multiply connected Maze. Such a Maze uses passages that coil around and run back into each other (hence the term "braid") and cause you to spend time going in circles instead of bumping into dead ends. A well-designed braid Maze can be much harder than a perfect Maze of the same size. Unicursal: A unicursal Maze means one without any junctions. Sometimes the term Labyrinth is used to refer to constructs of this type, while "Maze" means a puzzle where choices are involved. A unicursal Maze has just one long snake-like passage that coils throughout the extent of the Maze. It's not really difficult unless you accidentally get turned around half way through and make your way back to the beginning again. Sparseness: A sparse Maze is one that doesn't carve passages through every cell, meaning some are left uncreated. This amounts to having inaccessible locations, making this somewhat the reverse of a braid Maze. A similar concept can be applied when adding walls, resulting in an irregular Maze with wide passages and rooms. Partial braid: A partial braid Maze is just a mixed Maze with both loops and dead ends in it. The word "braid" can be used quantitatively, in which a "heavily braid Maze" means one with many loops or detached walls, and a "slightly braid Maze" means one with just a few.

Texture: The texture class is subtle, and describes the style of the passages in whatever routing in whatever geometry. They're not really on/off flags as much as general themes. Here are several example variables one can look at:

Bias: A passage biased Maze is one with straightaways that tend to go in one direction more than the others. For example, a Maze with a high horizontal bias will have long left-right passages, and only short up-down passages connecting them. A Maze is usually more difficult to navigate