Generating Mazes

Mazes as Spanning Trees

Before we generate mazes, let's understand what makes a "perfect" maze. A perfect maze has a simple but powerful property: there is exactly one path between any two cells. No loops, no unreachable areas.

This might sound familiar. In graph theory, a structure where every node is connected with exactly one path between any pair is called a spanning tree. A perfect maze is simply a spanning tree of the grid graph.

Think about it: our grid is a graph where each cell is a node and adjacent cells share edges. A spanning tree visits every node while using the minimum number of edges (no cycles). In maze terms, this means:

• Every cell is reachable from every other cell
• No loops exist — you cannot walk in a circle
• Exactly one path connects any two points

This insight transforms maze generation from an artistic endeavor into a well-defined algorithmic problem: we need to build a spanning tree of our grid.

Recursive Backtracker (DFS-based)

One elegant way to build a spanning tree is with depth-first search. The recursive backtracker algorithm works exactly like DFS exploration, but instead of searching for a goal, it carves passages as it goes.

The algorithm is beautifully simple:

1. Start from a random cell, mark it as part of the maze
2. Choose a random unvisited neighbor
3. Carve a passage to that neighbor (remove the wall between)
4. Repeat from the new cell
5. When stuck (no unvisited neighbors), backtrack until you find a cell with unvisited neighbors

Because DFS goes as deep as possible before backtracking, this algorithm creates mazes with long, winding corridors. The passages tend to snake through the grid, creating a river-like texture.

Watch how different algorithms build their mazes. DFS creates those characteristic long corridors, while Prim's creates more branching structures, and Binary Tree has an obvious diagonal bias.

Different Algorithms, Different Textures

Just as BFS and DFS create different exploration patterns, different maze generation algorithms create different visual "textures." Each has its own character.

DFS Backtracker produces mazes with long, winding corridors. The passages feel like rivers carving through the grid. Corridors can extend far before hitting dead ends, creating a sense of depth.

Prim's Algorithm works differently. Instead of going deep, it maintains a frontier of walls that could be removed. At each step, it picks a random frontier wall and, if it would connect to an unvisited cell, removes it. This creates more branching, with an organic, tree-like feel. Passages split frequently, giving a more chaotic appearance.

Binary Tree is the simplest algorithm. For each cell, flip a coin: carve north or carve west (when possible). This creates a strong diagonal bias — notice how passages tend to flow toward the northwest corner. The algorithm is fast and simple, but the bias is obvious once you see it.

Look closely at each maze. DFS has those long snaking corridors. Prim's has more uniform branching. Binary Tree has that telltale diagonal bias — passages on the north and west edges always run straight.

The algorithm you choose depends on your goals. Want a maze that feels like exploring winding caves? Use DFS. Want something that feels more like a branching forest? Try Prim's. Need something fast and don't mind the bias? Binary Tree is your friend.

Solving the Maze

Here's where everything comes full circle. We have spent chapters learning pathfinding algorithms. We have just learned to generate mazes. What happens when we combine them?

Maze solving is simply pathfinding on a constrained graph. The walls define which cells connect to which. BFS will find the shortest path. DFS will find a path (though perhaps not the shortest). A* would work too, guiding the search toward the exit.

Notice the two phases. First, DFS carves out the maze structure, creating passages through the walls. Then the solver floods through the passages, finding a path from start to end.

The key insight: maze generation and maze solving are two sides of the same coin. Both are graph algorithms operating on the same underlying structure. Generation builds the spanning tree. Solving finds paths within it.

Racing Algorithms

Want to see BFS and DFS compete head-to-head? Watch them race to solve the same maze simultaneously. BFS explores methodically, level by level. DFS dives deep, backtracking when stuck.

BFS guarantees the shortest path but explores more cells. DFS might find a path faster, but it could be longer. The winner depends on the maze structure and where the exit lies.

Build Your Own

Theory is great, but nothing beats hands-on experience. Draw your own maze and watch the algorithm find a path through your creation.

Try creating obstacles, dead ends, and winding paths. Can you design a maze where no path exists? What happens when you block the exit?

Key Takeaways

• Perfect mazes are spanning trees of the grid graph — exactly one path between any two cells
• DFS-based generation (recursive backtracker) creates long, winding corridors
• Prim's algorithm creates more branching, organic-feeling mazes
• Binary Tree is simple but has an obvious diagonal bias
• Different algorithms produce different visual textures
• Maze solving uses the same pathfinding algorithms we have already learned
• Generation and solving are complementary operations on the same graph structure