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: |