In this article, I will show you a few techniques that you can use to make more interesting mazes.

We will be working here with perfect mazes on a square grid. A maze is perfect when there is exactly one path between each pair of rooms. There are several algorithms that generate perfect mazes. From a mathematical point of view, the ideal algorithm is one that produces each possible maze with equal probability. Such an algorithm is called unbiased.

As is usually the case with procedurally generated content, unbiased algorithms give us mazes that are not the best for games:

• They tend to look alike
• They tend to look homogeneous – all parts of the maze look alike
• They are unattractive

(Of course, a totally unbiased algorithm can generate all possible mazes. However, there are so many that the probability of generating an "interesting" maze is very low.)

A large part of this article will deal with introducing bias so that we can build sets of mazes that are visually distinct, or more obviously different within the set, or has features across different parts of the maze, and are visually more appealing.

Instead of developing new algorithms, we will make modifications to Prim's Algorithm. Prim's algorithm already has some bias, but not enough of the type that interests us. We use this algorithm because it is faster than unbiased ones, and the little bias it has does not stand in the way of what we want to do.

(If you are interested in other maze algorithms, check out this site or this book by the same author.)

All of this code written for this article was written with our Grids library for Unity.

Prim's Algorithm

We start with a set of walls, a set of rooms, and a set of pillars. Rooms are always open, pillars are always closed, and walls can be open or closed. The rooms and walls must satisfy these conditions:

• Each room is adjacent to four walls.
• Each wall is adjacent to one or two rooms.
• If a wall is adjacent to a room, the room is adjacent to the wall and vice versa.

The algorithm to generate a maze is this:

1. Mark all walls as closed.
2. Select a room from the set of rooms, and add it to the "path".
3. Add the four walls of the room to the "wall list". This is the list that we keep processing until it is empty.
4. While the wall list is not empty:
   1. Select a wall from the list.
   2. Find the rooms adjacent to the wall.
   3. If there are two adjacent rooms, and exactly one of them is not in the path:
      1. Mark the wall as "Open".
      2. Add the unvisited room to the path.
      3. Add the walls adjacent to the unvisited room to the wall list.
   4. Remove the wall from the wall list.

We now have a set of open objects (the rooms and open walls), and a set of closed objects (the set of pillars and closed walls).

I have left a few things vague in the description above.

What are rooms, pillars and walls exactly? Each of these is a connected set of cells from the grid. The set always has one or more cells. How we choose these sets give us different mazes.

How do we select the first room? Any way we like! Different strategies lead to different mazes.

How do we select a wall to process from the list? Any way we like! Different strategies lead to different mazes.

For vanilla Prim, we use the following scheme to decide which cells are rooms, walls, and pillars:

Rooms are white, walls are blue, and pillars are red. This is called a (2, 0, 2)-grid-coloring. Grid colorings are useful for all kinds of things, and we discuss them in more detail below.

We select the first room randomly, and we select walls randomly too.

With these settings, the resulting maze looks like this:

Grid Colorings

A grid coloring is a repeating pattern of k distinct colors. Here are a few examples:

Notice that in each pattern we can find two vectors u and v such that for any integers m and n and any cell at w, mu + nv + w has the same color as w. For example, the three colorings above have the following pairs of u and v:

1. u = (5, 0) and v = (3, 1)
2. u = (2, 0) and v = (1, 1)
3. u = (2, 0) and v = (1, 2)

The pairs are not unique, for example we could also use u = (2, -1) and v = (1, 2) for the first example. To make the algorithms easy to implement, we restrict ourselves to colorings where the y-component of u is 0. We then use the remaining components to identify the coloring. For the examples above:

1. (5, 3, 1)
2. (2, 1, 1)
3. (2, 1, 2)

With this scheme, the number of colors is equal to the first value multiplied with the last, so we see for the 3 colorings we get 5, 2, and 4 colors.

For the vanilla Prim algorithm, we use the (2, 0, 2)-coloring. Note that the triplet that describes a coloring is also not unique; the (2, 2, 2) coloring is the same as the (2, 0, 2) coloring. In practice, this does not matter for our purposes; all we need to do is find one of the descriptions of a coloring.

Of course, we use colors for the pictures, but in algorithms we use integers from 0 to k-1. So a coloring is a function C(x0, x1, y1, p) that for each point p returns an integer in the range 0..k-1. If ther is no confusion, I will drop the three color-parameters, and only write C(p) or C(x, y).

A generic version of this algorithm is slightly tricky to understand and implement. Instead, notice that you can make a m×n lookup table by hand where m is the smallest positive number for which (0, m) has the same color as (0, 0), and n is the smallest positive number for which (n, 0) has the same color as (0, 0). With this lookup table L(p), we can find any coloring with this formula:

C(p) = L(p.x mod m, p.y mod n)

Note that the mod here is always between 0 and k-1. For example, -1 mod 5 will be 4. I have written this article so that it does not matter which integer you use for which color. For more on grid colorings, see What are grid colorings? and for the hard-core math, see Hex Geometry for Game Developers (although the document deals with hex grids, the mathematics is exactly the same for square grids).

Using colorings to assign rooms, walls and pillars

We used the (2, 0, 2)-coloring to classify cells into rooms, walls and pillars.

• If C(p) == C(0, 0), p is a room.
• If C(p) == C(1, 0) or C(p) == C(0, 1), p is a wall.
• If C(p) == C(1, 1), p is a pillar.

Before going into the general idea, let's do another example. Here is the 5, 3, 1 coloring, but this time I have chosen the colors to make certain relationships clear:

Let's make a wall two connected yellow cells, or two connected blue cells, and a room the white cells.

The remaining cells are isolated yellow or blue cells on the border. We make these pillars.

Let's see if our three conditions hold:

Each room is adjacent to four walls. This is true, except for the rooms on the border. We get around this by making all rooms on the border pillars instead.

Each wall is adjacent to one or two rooms. This is true too.

If a wall is adjacent to a room the room is adjacent to the wall, and vice versa. This is true too. (If we use a picture like this, it will always be true and we need not check it. However, we will write functions later that will return for a wall its adjacent rooms, or return for a room its adjacent walls. When these functions return arbitrary point-sets, it will be important to check this condition.)

We can now run Prim's algorithm with this configuration. Here is the result:

This maze looks complete different from the first maze.

We can see better that it is the same algorithm if we use tiles like this: (and suitably rotated):

The following example is based on the (3, 0, 3)-coloring shown below.

To make it easier to see what is going on, I have recolored the grid so that walls have the same color.

• Rooms are white.
• Walls are dark blue and dark yellow.
• Pillars are light blue and light yellow.

As before, we make rooms on the border pillars too.

White this setup, it's easy to check that each room is adjacent to four walls, and each wall is adjacent to one or two rooms.

We can use the same coloring, but with the walls as shown below. (As before, rooms on the border are made into pillars). Again, each room is adjacent to four walls, and each wall is adjacent to one or two rooms.

This maze is derived in the same way from a (3, 1, 3)-coloring. Notice that the maze seems sheared, this is because the coloring is sheared.

This maze is derived in the same way from a (3, 2, 3)-coloring. This maze is even more sheared.

I think it is always possible to find a scheme that will work for any coloring, as long as the number of colors is 4 or higher. The checker board coloring (2, 1, 1) is an example that won’t work. If we make the one color walls and the other color rooms, then each wall is adjacent to four rooms, which means not all the conditions for our algorithm is satisfied.

Tiles

We can make a simple maze more elaborate by replacing each tile with a more intricate one.

There are 6 types of tile: rooms, pillars, open and closed horizontal walls, and open and closed vertical walls. Here is an example of a tile set for the 6 tiles, where each tile is 4×4, and the resulting maze.

(The tile set does not completely work at two of the borders, this can be fixed by simply ignoring two rows and columns).

When you design a tile, you have to make sure that the tile connects the correct neighbors. For example, the open horizontal tile must connect its western and eastern neighbors. But note that the compulsory connections are not the only ones possible. For example, in this tile design the pillar also connects its northern neighbor with its western neighbor. This works, because the western neighbor is designed so that this is always a dead-end.

The image above shows how the pillar (bottom right) connects its northern neighbor with its western neighbor. The connection is not a "true" connection, since the connection to the western neighbor leads to a dead-end.

Furthermore, you must ensure that no arrangement leads to cycles. And finally, you must make sure that all openings are connected to the path.

This gives us a very regular looking grid. In fact, the maze is equivalent to a maze design where the rooms are elaborate 7×7 tiles, and the walls are simple 1×7 or 7×1 tiles, and the pillars are 1×1 tiles.

There are a few things to note from this observation:

• Given a tile set design of the type above, we can derive the 4×4 tile set. Designing the 4×4 tile set is quite hard. In contrast, with the mixed set the only real design is the room.
• If we adjust the final algorithm to work with the mixed set instead, it is very easy to introduce variations, which allows us to build less regular looking mazes. For example, any 1×7 tile with an opening in an odd location can serve as valid wall.

Selecting which wall to process

So far we have gotten some cool variations on the vanilla Prim algorithm, but the mazes still have a type of blandness to them. One way to give the maze distinct characteristics is to use a strategy for selecting the wall other than random.

These first ones are not so interesting from a solvability point of view, but as we will see later, they make for useful building blocks. Some of the effects also depend on the order in which we add walls to the list. Unless specified, we added all walls in the order north, east, south, west.

Select the first wall

Select the last wall

Take fifth last, or if the list is too short, the first

Some of the following selection schemes makes use of different distance metrics. You should already be familiar with the Euclidean distance metric – this is the "standard" distance metric. In grid algorithms, two other metrics are often useful, and for our maze algorithms we use a third.

The Manhattan distance, or taxicab distance, or rook distance is how many moves a rook on a chessboard will make moving from one point to the other if it is allowed to only move one square at a time. It is given by d(p, q) = Abs(px – qx) + Abs(py – qy).

The Chebyshev distance, or chessboard distance is how many moves a kind must make to move from one square to another. It is given by d(p, q) = Max(Abs(px – qx), Abs(py - qy)).

The Knights distance is how many moves a Knight must make to get from one point to another. This metric is unusual because it behaves quite erratically over short distances. Over longer distances, it resembles the other metrics more closely in behavior. This property is useful to us because it prevents the maze to become "overcrowded" around a point too quickly if we choose to always process the closest wall to a point using this metric. Unfortunately, there is not a simple formula for this metric. You can find a correct implementation here.

A. Take the closest wall to the start using the Manhattan Norm

B. Take the closest wall to start Point using the Chebyshev norm

C. Take the closest wall to start Point using the Knight Norm

At first glance this looks somewhat similar to the previous strategy. One important difference is that the previous strategy always leads to an open row and column across the entire maze.

D. Select the furthest wall from start using the Euclidean norm

E. Select the furthest wall from start using the Manhattan norm

F. Select the furthest wall from start using the Knight distance

G. Of the last two, select the one closest to the last visited using the Knight distance

H. Of the last two, select the wall closest to start using the Knight norm

I. Take the first horizontal, or if no horizontal is available, take a random wall

J. Alternately select one of the last two vertical or horizontal walls randomly

K. A direction sequence (V, V, V, V, H, V, V, V, V, H, V, V, V, V, H, V, V, V, V, H...) is repeated. Choose one of the last two walls in the direction randomly

We can go on like this forever to generate a variety of mazes with distinct properties.

Some of the features include:

• how windy the maze is
• how regular the maze is
• how branchy it is
• how long the branches are on average
• how many long straights it has

Robust Prim

For the sections that follow, we need to make a slight modification to the maze generation algorithm.

The version at the beginning of this article prevents cycles by only adding a wall if it is adjacent to one unvisited room. We replace this check with an explicit test to see whether the adjacent rooms are already connected, and only add the wall if they are not. This modification allows us to add walls that are not in our list.

1. Mark all walls as closed.
2. Select a room from the set of rooms, and add it to the "path".
3. Add the four walls of the room to the "wall list". This is the list that we keep processing until it is empty.
4. While the wall list is not empty:
   1. Select a wall.
   2. Find the rooms adjacent to the wall.
   3. If there are two adjacent rooms, and they are not already connected*:
      1. Mark the wall as "Open".
      2. Add all unvisited rooms to the path.
      3. Add the walls adjacent to each unvisited room to the wall list.
   4. Remove the wall from the wall list.

*Connected here means there exists a path from the one to the other. It may be through the shared room, or through the rest of the maze.

This algorithm does not require that the wall we select is on the list. We will usually combine selecting a wall from the list with selecting a wall using some other criterion. The next sections will give some interesting criteria we can use.

This version of the algorithm is significantly slower than the vanilla version, which uses a trick to make it unnecessary to check connectedness explicitly. It is possible that a similar trick can be used to speed up the above algorithm; I don't know.

Symmetry and Patterns

Symmetry is useful in any type of procedural generation. It can make random patterns seem more designed, and make them more pleasing to the eye. With mazes, symmetry can also be useful to turn some of the more extreme bland mazes into something more interesting.

To get an overall symmetric effect, we will for each wall we process, also process its symmetric counterparts. We modify our algorithm to choose walls as follows:

1. If our current pattern is empty:
   1. Choose a wall from the wall list.
   2. Add a set of walls symmetric to the chosen wall to the pattern.
   3. Continue with this wall.
2. 2.Otherwise:
   1. Take the next wall from the pattern.
   2. Remove it from the pattern.
   3. Continue with this wall.

The type of symmetry we want determines which walls to add to the pattern list. For example, if we want 4-fold rotational symmetry, we add the wall rotated by 90, 180, and 270 degrees to the pattern.

Because the mazes are constrained to not contain any cycles, the resulting mazes are not always 100% symmetrical.

4-Fold Rotation

(Using selection scheme I)

Reflection

(Using selection scheme F)

(Using selection scheme G)

Translation

(Using selection scheme H)

Temporal Switching

Instead of using the same strategy to generate the entire maze, we can switch between strategies over time. This results in mazes with local features (depending on how we choose walls to begin with), but is not completely homogenous. Below are some examples of this.

Switching center of symmetry every 80 steps

(Using selection scheme F.)

Switching center of reflection every 40 steps

(We select the wall closest to the current symmetry using Euclidean distance.)

Switching from choosing closest point to start to furthest point from center 40, with center randomly chosen every 80, using Euclidean distance.

Switching between strategies A and D every 80 steps, (starting at the center of the maze).

Switching between strategies A and H every 80 steps.

Spatial switching

We can also change our strategies according to where we are in the maze.

To implement this:

1. Partition mazes into sets using some criterion.
2. Select a random partition, and apply a strategy to this this partition to select the next wall.

Below are some ideas for different ways of partitioning the grid.

Quadrant

Partition walls according to the quadrant in which they fall. Below, we partitioned diagonally opposite quadrants using either one of these schemes:

Select the last horizontal (or last, if no horizontal is available)

Select the last vertical wall (or last wall, if no vertical is available)

Here is the same switch, but this time we use a checker board coloring to determine which to use. To get different-sized blocks we floor-divide the point by an integer before calculating the coloring.

When we apply symmetry to the last ones, the results are surprising. Here is the last one, but with rotationally symmetric walls added too:

Here is another coloring partition (done by dividing the point by 3, 3), and what happens if we add rotational symmetry and translational symmetry.

In the following example, we partition the cells by calculating the color index mod 2 of the (5, 3, 1)-coloring. Below is the pattern with no symmetry, rotational symmetry, and reflective symmetry.

Sequential Generation

Before we get to more advanced techniques, we need to modify our algorithm so that it can continue generating a maze from a partially generated maze.

Although we can use this to switch between strategies, we have already seen how to do that without this modification (by simply doing it on the fly). The point of this modification is to combine techniques that cannot be altered on the fly (at least not easily), such as the recursive combination described later.

There are two variables in our version of the algorithm so far that are necessary for correct operation. The first is the path keeping track of nodes already visited The second is the wall list, keeping track of the walls we still need to explore.

To adapt the algorithm to work on a partial maze, we need to reconstruct these.

The path is reconstructed by selecting all rooms that have at least one wall that is open. (Remember, we mark all rooms except for those at the border as open at the beginning, so we cannot simply add the open rooms to the path).

For the wall-list, it is not really necessary to reconstruct the complete list. Instead, we will build it again as necessary. This allows us not to worry about the order of the walls (so that our wall selection scheme is not dependent on the order of the initial elements). The path will prevent us from expanding nodes unnecessarily. Doing this will work as long as the existing path does not partition the existing maze into disconnected sets. To get around this, once the wall list is empty, we need to check whether there are candidate walls left to process.

This will be the case if there are any rooms not on our path. A wall adjacent to such a room is a candidate.

Finally, we also put in another stop criterion. Now that we can continue, it will also be useful to stop before the maze is complete.

1. Mark all walls not in the input maze as closed.
2. Add all rooms adjacent to at least one wall to the path.
3. Find a wall that is adjacent to a room not in the path.
4. If such a wall exists, add it to the wall list.
5. While we want to continue and the wall list is not empty:
   1. Select a wall.
   2. Find the rooms adjacent to the wall.
   3. If there are two adjacent rooms, and they are not already connected:
      1. Mark the wall as "Open".
      2. Add all unvisited rooms to the path.
      3. Add the walls adjacent to each unvisited room to the wall list.
   4. Remove the wall from the wall list.
6. If all rooms are not connected:
   1. Find a wall adjacent to at least two partitions (such a wall must exist, otherwise all rooms will be connected).
   2. Add this wall to the wall list.
   3. Continue from step 5

Partitioning

With this method, we divide our grid into a set of smaller squares. (The squares overlap, so that two squares share a border). We then generate a maze as usual in each partition. Finally, we run the maze algorithm again on the entire maze to join the pieces together. Here are a few examples of how that looks:

(This example uses both reflection and rotation in each of the small grids, but select walls randomly)

We can employ grid colorings in the partition to select a strategy. For example, here is a version that uses the checkerboard coloring to select which symmetry type to use.

Recursive Combination

With this method, we generate a maze. We then blow up this maze by a factor (for example, so that each cell of the original now cover several cells in the new one). We then run a maze algorithm inside this bigger shape. Finally, we rerun the algorithm on the entire grid. We can repeat this a few times.

In the following grid we started with a 7×7 maze, and double it each time.

Here are some variations, with different factors and different number of times grown:

Other Ideas

I covered many ideas in this article, but there are some other interesting ones that I did not have time to explore yet.

• Using probabilistic switching.
• Using "strategy maps" instead of formulas to decide on strategies. A map is simply a grid the same size with an index denoting the strategy to use.
• Combining pure regular algorithms (that produce spirals, combs, and zig-zag mazes, and Hilbert-curves, for example). I tried to come up with selection schemes that would give these regular mazes, but did not have much success. It seems easier to produce these types of mazes directly.

A few notes on implementation

It's important to implement a correct version of the simplest version of your maze algorithm first, before designing a version with all the bells and whistles. This will serve as a benchmark for correctness, visual appearance and performance (if you need it).

During implementation, the following mistakes may crop out:

• A faulty condition that leads to infinite recursion. Because it is so expensive to make this mistake (if you implement this in Unity, for example, you have to kill Unity – potentially losing your scene – and restart it). Things that may cause infinite recursion:
  • Forgetting to remove a processed wall from the wall list.
  • Re-adding already processed walls to the list.
  • Adding floors or pillars to the list.
• False geometric / algebraic assumptions. For example, the following three statements are not always simultaneous true:
  • the maze is a rectangle with odd dimensions,
  • the center of the maze is at 0, 0
  • the border of the maze can never contain points colored the same as 0,0 (rooms, usually)
• Calculations involving the size of a maze when the maze is scaled, or its borders are removed, or the maze is positioned in a larger maze.
• Preserving the coloring when positioning a small maze into a bigger one.

Assertions are helpful to test your assumptions about the maze and the interim data structures, and are very helpful to flush out bugs.

Some useful assertions:

• Does the wall list start off non-empty?
• Does the wall list shrink after a wall has been removed?
• Does the center, your stating position, the four corners have the coloring you assume?
• Does a point have the coloring you thing it has after a transformation?
• Are distances or maze sizes what you expect (especially in algorithsm where smaller mazes are used to make bigger ones).

Conclusion

I have given some ideas here for making more interesting mazes. The main take-away points are these:

• You can use colorings to mark cells in a regular way, and exploit that in algorithms such as the maze generation variations discussed here.
• You can modify your algorithms to make "symmetric" moves to get overall symmetry. The same techniques also work well in other generation algorithms.
• You can modify strategies over time or space to get local features.

I hope if you implement maze algorithms you find some of these ideas useful.