## Maze Generation

Mazes are designed to be complex; otherwise, they would not be used to make people lost. However, the techniques for creating mazes can actually be quite straightforward. You can create a complex maze by following a simple algorithm. This makes mazes ideal for diving into procedural content generation, a field of study devoted to building complex structures and art from code with little or no input from humans during the process. This tutorial will not provide any actual code, but rather is designed to be an introduction to maze generation algorithms. Let’s first look at an example algorithm:

1. Begin with an empty space with no walls.
2. Divide the space in half with a vertical wall.
3. Randomly place a single opening in the wall.
4. Divide each half in half with a horizontal wall.
5. Place an opening in each wall.
6. Repeat 2-5 for each new section until the desired level of detail is achieved.

This is an example of a recursive division algorithm. Following this algorithm, we end up with this: There are obvious weaknesses. One is that there are more horizontal walls than vertical walls. This is inevitably the case for any square maze created with this algorithm. The other problem is that it is somewhat predictable. Given a view of the whole maze, you can see an obvious middle point you must reach to get to the other side of the maze. You could find similar points that connect each quadrant of the maze to another quadrant. You can easily find the red, then green, then blue dots that you must pass through to access other parts of the maze. Connecting those and finding any other point in the maze from those is trivial. We could modify the algorithm, but related algorithms will have similar issues. Instead, we need a different model for our mazes, one that will give us flexibility to create all sorts of algorithms.

### Graph Theory and Mazes

We need to better define our goal. Let’s say that our ideal maze is a maze where every point in the maze is accessible to every other point in the maze in exactly one way. This means no loops and no inaccessible areas. We can see the recursive division algorithm achieved this, which makes sense. Since we only left one opening between halves at each level of detail, there could only be one path between them. Looking at mazes in this way though, of points connecting to other points, lets us use graph theory. For those not familiar with graph theory, it is a mathematical field of studying graphs, which are structures that have objects, or nodes, connected to each other through edges. If our nodes, for example, are cities, then we might consider the presence of a road between them to be an edge. In our maze example, we can set up various points that we assume will be empty, like a room, and connect them together in various ways.

Our definition of an ideal maze lets us do something interesting with our graph. If there is only one path to any node from any other node, we could use any node as the root node of a tree. Trees are a special type of graph, and a lot of algorithms have been invented for building and traversing tree structures.

Because mazes are random though, we do not know what the tree will look like until we generate it. This is okay. If we imagine our maze as a tree, we can traverse it to “discover” what that tree looks like, even if that is not determined until the traversal. There are two popular types of tree traversal/generation algorithms worth describing, and they each produce a very different kind of maze. After their description, I included another algorithm that is a sort of combination of the two.

### Depth-First Search

Depth-first search (DFS) is a simple tree traversal algorithm that works the way it sounds. First, keep going deeper in the tree until you can’t go any further. Then back up and try another branch. More specifically, the process is as follows:

1. Start at the root node, which can be arbitrarily chosen. Mark it as visited, and set it as the active node.
2. Do the following:
• If there are no unvisited children of the active node:
• If the active node is the root, you are done.
• Else, the parent of the active node becomes the new active node.
• Else:
• Pick a child, mark it as visited, and set it as active.
3. Repeat Step 2.

Since we are using this for maze generation, this requires a few tweaks. To implement this, I used a 2D array, where a 0 represents empty space and a 1 represents a wall. For example:

```1  1  1  1  1  1  1
1  0  0  0  1  0  1
1  1  1  0  1  0  1
1  0  1  0  0  0  1
1  0  1  1  1  0  1
1  0  0  0  0  0  1
1  1  1  1  1  1  1
```

The bold zeroes are our nodes. A zero between two nodes means the nodes are connected. A 1 means they are not connected, and there is instead a wall. We can begin with a map entirely filled with ones. Whenever we change a node to a zero, it means we have visited it. If we go back to thinking about this maze as a tree, then each node can have up to four children, one in each cardinal direction. This is not always the case, though, since sometimes, moving in a direction means leaving the edge of the maze or connecting to an already-visited node, creating a loop. If there is no direction to possibly connect to, then we back up to the previous node. Here is how we carved out the above maze. Red is the active node. Blue shows the possible next move. Orange is the path created so far. Normally, DFS would have a consistent yet arbitrary way of selecting the next node in the path. For a maze, though, it is better to choose randomly. Whenever there are multiple blue paths, one is chosen completely at random. Note that at steps 5 and 10, there were no options for possible moves. In these situations, we back up until there are possible moves. We can keep track of the path using a stack. With each move, add something about the move, such as coordinates, on the top of the stack. When backtracking, take the top coordinates off the stack and set that as the active node. When we arrive back at the root node (which we know we did if the stack of moves is empty), and there are no possible moves, we know we are done. Following this, I created a maze that looks like this: This does not have the same problem as recursive subdivision. There are no obvious ways to divide this maze in half. However, if you try following a path, you will notice that you are not actually faced with many choices when navigating this maze. There are a few dead ends, but most of the maze is just a couple long, winding paths. This might be preferred in many situations, but not always, so it is worth exploring other algorithms.

Simplified Prim’s Algorithm

Prim’s algorithm is in many ways opposite of DFS. It is breadth-first, so we will be looking very shallowly at a lot of paths before moving deeper. It is usually used for finding minimum spanning trees, or a tree with the fewest/shortest edges. The result is an optimal path that connects everything together. The algorithm looks something like this:

1. Start at the root node, which can be arbitrarily chosen. Add it to the tree.
2. Of all the edges that connect the tree to an unvisited node, choose the one with the smallest edge weight.
3. Repeat until all nodes are visited.

For our purposes in making a maze, we can simplify this by removing all concept of edge weight. We don’t want to find an optimal solution; that would be a very boring maze. Instead, we will choose the edge randomly. Imagine maintaining a list of possible next moves. Every time you visit a new node, you can add another move to its adjacent unvisited nodes to the list. However, unlike DFS, the next move is selected from the entire list, not just the ones from the last visited node. While this maze is also random, it is significantly different in appearance to a DFS maze. The modified Prim’s algorithm creates a maze with lots of dead ends, but very short paths. While this fixes the problem mentioned about DFS, it takes it to another extreme. There are so many dead ends that none of them go very far. You aren’t likely to be fooled by a dozen nearby dead ends that don’t even turn a corner.

### Combination of the two

Both maze algorithms have weaknesses, so I figured a combination of the two ideas would create a better balance. For this algorithm, like our simplified Prim’s algorithm, we maintain a list of edges, but we tend to stick to the same path a little longer like in DFS. Do this by defining some maximum number of moves before a jump, such as 5. Now, when we pick an edge, we then do DFS for only 5 moves before quitting and picking another edge like in Prim’s. For simplicity, it may not be necessary to maintain a stack of move history like in DFS. Instead, you could simply say that if you get stuck, switch back to the Prim’s algorithm instead of DFS, and start working elsewhere.

1. Start at an arbitrary root node. Add it to the tree.
2. Add this nodes edges to a list of possible edges to choose from.
3. Choose one of the edges to connect to. Add its edges to the list of edges. Also replace lastEdges with its edges.
4. Do the following MaxMovesBeforeJump times or until lastEdges is empty:
• Choose one edge from lastEdges and connect to it.
• Replace lastEdges with just the edges available from the last move.
5. Repeat 3 and 4 until there are no edges left.

After experimenting with different values for the maximum number of moves before a jump, I was able to get different mazes on the range of qualities we see from the DFS and Prim’s algorithm extremes.