The story behind

Since I was little I've always enjoyed solving mazes. But every time I wondered how they were created. I thought that there was a person whose whole purpose in life was to draw mazes for people to solve. But when I started learning about graphs, I was pleased to find a particular application for the algorithms used, that of creating mazes. In this article, I will only talk about the generating algorithms based on graphs.

Approch

Before diving into the algorithms, it's essential to understand the structure of a maze in terms of graph theory. A maze can be represented as a grid of cells, where each cell corresponds to a node in a graph. The connections between cells, or pathways, correspond to edges between these nodes. The goal of maze generation algorithms is to create a perfect maze, which is a type of maze where there is exactly one path between any two points. This ensures that there are no loops and no inaccessible areas within the maze.

Depth-First Search (DFS) Algorithm

The Depth-First Search (DFS) algorithm is one of the simplest methods for generating a maze. The basic idea is to start at a random node (or cell), mark it as visited, and then recursively visit its neighboring nodes that have not yet been visited. The key steps in the DFS-based maze generation algorithm are:

Choose a starting cell: Begin from a random cell in the grid.
Initialize a queue with the starting cell: This queue will help in maintaining the order of cells to be explored.
While the queue is not empty:
- Dequeue the front cell from the queue.
- If the dequeued cell has unvisited neighbors:
  - Randomly select one of the unvisited neighbors.
  - Remove the wall between the current cell and the selected neighbor.
  - Enqueue the selected neighbor.
  - Mark the selected neighbor as visited.
Repeat until all cells have been visited.

This algorithm creates a depth-first traversal of the graph, which inherently results in long, twisting passages with few short dead-ends.

Breadth-First Search (BFS) Algorithm

While the DFS algorithm is efficient and produces mazes with long corridors, the Breadth-First Search (BFS) algorithm offers a different approach. Instead of exploring deeply into one path before backtracking, BFS explores all neighbors at the present depth before moving on to nodes at the next depth level. This often results in mazes with a more uniform distribution of paths.

The BFS-based maze generation algorithm works as follows:

Choose a starting cell: Begin from a random cell in the grid.
Initialize a queue with the starting cell: This queue will help in maintaining the order of cells to be explored.
While the queue is not empty:
- While the queue is not empty.
- If the dequeued cell has unvisited neighbors:
  - Randomly select one of the unvisited neighbors.
  - Remove the wall between the current cell and the selected neighbor.
  - Enqueue the selected neighbor.
  - Mark the selected neighbor as visited.
Repeat until all cells have been visited.

BFS typically generates mazes with a more "bushy" structure, as the algorithm simultaneously explores paths at the same level of depth, leading to mazes with more uniform corridors and fewer dead-ends.

Kruskal's Algorithm

Kruskal's algorithm, typically used to find the minimum spanning tree of a graph, can be adapted for maze generation. The idea is to treat each cell in the grid as a separate set and gradually connect these sets by removing walls (i.e., adding edges) between cells until all cells are part of a single connected component (i.e., there is only one set left).

The steps to generate a maze using Kruskal’s algorithm are:

Initialize each cell as a separate set: Each cell is considered its own isolated component.
Create a list of all the walls: Each wall is a potential edge between two sets.
Randomly sort the list of walls: This ensures randomness in the maze structure.
For each wall in the sorted list:
- If the cells on either side of the wall belong to different sets:
  - Remove the wall (connect the cells).
  - Union the two sets into one.
Repeat until all cells are part of the same set.

Kruskal's algorithm is particularly useful for generating mazes with a high degree of randomness, as the walls are removed in a randomized order. The resulting mazes are well-distributed, with an even mix of long corridors and short dead-ends.

Prim's Algorithm

Prim’s algorithm, another method used for finding the minimum spanning tree, can also be applied to maze generation. The approach is somewhat similar to Kruskal's, but instead of starting with isolated cells, Prim's algorithm starts with a single cell and gradually grows the maze by adding the closest neighboring cells.

Here’s how to generate a maze using Prim’s algorithm:

Choose a starting cell: Start from a random cell in the grid.
Add all walls of the starting cell to a list: This list will help in choosing the next wall to remove.
While there are walls in the list:
- Randomly select a wall from the list.
- If the wall divides two cells that are not yet connected:
  - Remove the wall.
  - Add the neighboring cell to the maze.
  - Add the neighboring cell's walls to the list.
Continue until all cells are connected.

Prim’s algorithm generates a maze that has a more "organic" feel, with paths that naturally expand from the starting point. The mazes produced by this algorithm tend to have fewer long corridors but a denser network of shorter paths.

Conclusion

Each of these algorithms—DFS, BFS, Kruskal's, and Prim's—offers a unique approach to maze generation, resulting in mazes with distinct characteristics. Understanding these algorithms not only provides insight into the mathematical beauty of graph theory but also offers a deeper appreciation for the intricate designs behind mazes. Whether you prefer the long winding passages of DFS, the balanced corridors of BFS, or the randomized complexity of Kruskal's and Prim’s algorithms, the world of maze generation is a fascinating intersection of art and mathematics.

To see the results of the presented algorithms in action, visit the Maze Generation Demo.