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:
Mark all walls as closed.
Select a room from the set of rooms, and add it to the "path".
Add the four walls of the room to the "wall list". This is the list that we keep processing until it is empty.
While the wall list is not empty:
Select a wall from the list.
Find the rooms adjacent to the wall.
If there are two adjacent rooms, and exactly one of them is not in the path:
Mark the wall as "Open".
Add the unvisited room to the path.
Add the walls adjacent to the unvisited room to the wall list.
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
