It's easier than you think.
Our objective here is to create a perfect maze, the simplest type of maze for a computer to generate and solve. A perfect maze is defined as a maze which has one and only one path from any point in the maze to any other point. This means that the maze has no inaccessible sections, no circular paths, no open areas.
 
We'll assume a rectangular maze, since that's the easiest type to create, but with the method presented here, we can create mazes of almost any shape and size, even 3-dimensional ones. To begin with, we'll need a grid:
Each square of the grid is a cell. The horizontal and vertical lines represent the walls of the maze. The generation algorithm we're using will assume that, at the beginning, all the walls of the maze are up. Then we selectively knock down walls until we've made a working maze that fits our definition of "perfect." We'll need a data structure to store information about the cells. But exactly what data should we be tracking? Assuming that we're interested in solving the maze as well as creating it, here's a graphical representation of all the information necessary:
The maze borders are gray, the walls are white, the starting position is green, the ending position is red, the solution path is yellow, and the backtrack path is light gray. The start and end points can easily be stored as individual variables. Then all we need to track, for each cell in the grid, are:
- Any borders the cell has
- Which walls are still up
- If the solution path goes through it, and in which directions
- If the backtrack path goes through it, and in which directions
Here's one way to do it (this is by no means the only way): a 12x16 maze grid can be represented as an array m[16][12] of 16-bit integers. Each array element would contains all the information for a single corresponding cell in the grid, with the integer bits mapped like this:
To knock down a wall, set a border, or create a particular path, all we need to do is flip bits in one or two array elements. You might think we don't really need to track the borders, since we could just use the minimum and maximum array indices to determine them. That's true, but storing border information in the array makes our maze much more flexible. It means we can easily change the shape of the maze in various ways and still be able to use our 2D array and maze generating algorithm without any code modification.
 
With a data structure in place for holding the maze information, we can initialize the maze by setting the appropriate borders and putting up all of the walls. Then we're ready to implement the algorithm.
Depth-First Search
This is the simplest maze generation algorithm. It works like this:
1) Start at a random cell in the grid.
2) Look for a random neighbor cell you haven't been to yet.
3) If you find one, move there, knocking down the wall between the cells. If you don't find one, back up to the previous cell.
4) Repeat steps 2 and 3 until you've been to every cell in the grid.
Here's the DFS algorithm written as pseudocode: |
