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 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, where 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. All of these describe creating the Maze by carving passages, however unless otherwise specified each can also be done by adding walls:

Algorithm Dead End % Type Focus Bias Free? Memory Time Solution %
Unicursal 0 Tree Wall Yes N^2 261 100.0
Recursive Backtracker 10 Tree Passage Yes N^2 24 19.0
Hunt and Kill 11 (21) Tree Passage no 0 55 (105) 9.5 (3.9)
Recursive Division 23 Tree Wall Yes N 8 7.2
Binary Tree 25 Set Either no 0* 7 2.0
Sidewinder 27 Set Either no 0* 8 2.6
Eller's Algorithm 28 Set Either no N* 10 4.2 (3.2)
Wilson's Algorithm 29 Tree Either Yes N^2 51 (26) 4.5
Aldous-Broder Algorithm 29 Tree Either Yes 0 222 (160) 4.5
Kruskal's Algorithm 30 Set Either Yes N^2 32 4.1
Prim's Algorithm 36 (31) Tree Either Yes N^2 21 2.3
Growing Tree 49 (39) Tree Either Yes N^2 43 11.0

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?
Random Mouse 1 no You Inside / Above no Yes no
Wall Follower 1 no You Inside / Above Yes Yes Yes
Pledge Algorithm 1 no You Inside / Above Yes Yes Yes
Chain Algorithm 1 Yes You + no Yes no Yes
Recursive Backtracker 1 Yes You no Yes no Yes
Trémaux's Algorithm 1 Yes You Inside / Above no no Yes
Dead End Filler All + no Maze Above no Yes Yes
Cul-de-sac Filler All + no Maze Above no Yes Yes
Blind Alley Sealer All + Yes Maze no no no Yes
Blind Alley Filler All Yes Maze Above no Yes no
Collision Solver All Shortest Yes You + no no no Yes
Shortest Paths Finder All Shortest Yes You + no Yes no Yes
Shortest Path Finder 1 Shortest Yes You + no Yes no Yes

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 June 30, 2014.