Maze cartoon

Maze Classification

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:

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:

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

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

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.

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:

Focus: The focus class is obscure, but shows that Maze creation can be divided into two general types: Wall adders, and passage carvers. This is usually just an algorithmic difference when generating, as opposed to a visual difference when observing, but is still useful to consider. The same Maze can be often generated in both ways:

Other: The above is by no means a comprehensive list of all possible classes or items within each class. They're just the types of Mazes I've actually created. :-) Note most every type of Maze, including Mazes with special rules, can be expressed as a directed graph, in which you have a finite number of states and a finite number of choices at each state, which is called Maze equivalence. Here are some other classes and types of Mazes:

Maze Creation Algorithms

Here's a list of general algorithms to create the various classes of Mazes described above:

Perfect Maze Creation Algorithms

There are a number of ways of creating perfect Mazes, each with its own characteristics. Here's a list of specific algorithms. Most of these are described as creating the Maze by carving passages, however unless otherwise specified each can also be done by adding walls.

Note there's a distinction between “fundamental algorithms”, and “derived algorithms”. Fundamental algorithms are fundamental ways of building a spanning tree, and usually are distinguished by the data structure or fundamental method used to select the next cell. Derived algorithms are specific implementations that either combine fundamental algorithms in any number of ways, or else insert special rules (such as intentionally giving bias to one type of passage over another). There are of course countless derived algorithms one can think up and implement. Only fundamental algorithms are listed below, of which there are only a few:

Algorithm Dead End % Type Focus Bias Free? Uniform? Memory Time Solution % Source
Unicursal 0 Tree Wall Yes never N^2 379 100.0 Walter Pullen
Recursive Backtracker 10 Tree Passage Yes never N^2 27 19.0 (Generic)
Hunt and Kill 11 (21) Tree Passage Yes never 0 100 (143) 9.5 (3.9) Walter Pullen
Recursive Division 23 Tree Wall Yes never N* 10 7.2 John Perry
Binary Tree 25 Set Either no never 0* 10 2.0 (Generic)
Sidewinder 27 Set Either no never 0* 12 2.6 Walter Pullen
Eller's Algorithm 28 Set Either no no N* 20 4.2 (3.2) Marlin Eller
Wilson's Algorithm 29 Tree Either Yes Yes N^2 48 (25) 4.5 David Wilson
Aldous-Broder Algorithm 29 Tree Either Yes Yes 0 279 (208) 4.5 David Aldous & Andrei Broder
Kruskal's Algorithm 30 Set Either Yes no N^2 33 4.1 Joseph Kruskal
Prim's Algorithm (true) 30 Tree Either Yes no N^2 160 4.1 Robert Prim
Prim's Algorithm (simplified) 32 Tree Either Yes no N^2 59 2.3 Robert Prim
Prim's Algorithm (modified) 36 (31) Tree Either Yes no N^2 30 2.3 Robert Prim
Growing Tree 49 (39) Tree Either Yes no N^2 48 11.0 Walter Pullen
Growing Forest 49 (39) Both Either Yes no N^2 76 11.0 Walter Pullen

This table summarizes the characteristics of the perfect Maze creation algorithms above. The Unicursal Maze algorithm (unicursal Mazes are technically perfect) is included for comparison. Descriptions of the columns follow:

Maze Solving Algorithms

There are a number of ways of solving Mazes, each with its own characteristics. Here's a list of specific algorithms:

Algorithm Solutions Guarantee? Focus Human Doable? Passage Free? Memory Free? Fast? Source
Random Mouse 1 no You Inside / Above no Yes no (Generic)
Wall Follower 1 no You Inside / Above Yes Yes Yes (Generic)
Pledge Algorithm 1 no You Inside / Above Yes Yes Yes Jon Pledge
Chain Algorithm 1 Yes You + no Yes no Yes Walter Pullen
Recursive Backtracker 1 Yes You no Yes no Yes (Generic)
Trémaux's Algorithm 1 Yes You Inside / Above no no Yes Charles Trémaux
Dead End Filler All + no Maze Above no Yes Yes (Generic)
Cul-de-sac Filler All + no Maze Above no Yes Yes Walter Pullen
Blind Alley Sealer All + Yes Maze no no no Yes Walter Pullen
Blind Alley Filler All Yes Maze Above no Yes no Walter Pullen
Collision Solver All Shortest Yes You + no no no Yes Walter Pullen
Shortest Paths Finder All Shortest Yes You + no Yes no Yes Walter Pullen
Shortest Path Finder 1 Shortest Yes You + no Yes no Yes (Generic)

This table summarizes the characteristics of the Maze solving algorithms above. Maze solving algorithms can be classified and judged by these criteria. Descriptions of the columns follow:

Other Maze Operations

There are more things that can be done with Mazes beyond just creating and solving them, as described below:

Algorithm Implementations

Back to Think Labyrinth!


This site produced by Walter D. Pullen (see Astrolog homepage), hosted on astrolog.org and Magitech, created using Microsoft FrontPage, page last updated July 31, 2022.