How to Build a Maze
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 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 start and end points can easily be stored as individual variables. Then all we need to track, for each cell in the grid, are:
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.
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.
create a CellStack (LIFO) to hold a list of cell locations
set TotalCells = number of cells in grid
choose a cell at random and call it CurrentCell
set VisitedCells = 1
while VisitedCells < TotalCells
if one or more found
knock down the wall between it and CurrentCell
push CurrentCell location on the CellStack
make the new cell CurrentCell
add 1 to VisitedCells
make it CurrentCell
|When the while loop terminates, the algorithm is completed.
Every cell has been visited and thus no cell is inaccessible. Also, since
we test each possible move to see if we've already been there, the algorithm
prevents the creation of any open areas, or paths that circle back on
We can put the start and end points wherever we want. This is another advantage of a perfect maze. Since, by definition, one and only one path will exist between any two points in the maze, we know that given a start/end pair, a unique solution to the maze must exist.
Depth-First Search is the most common algorithm used in maze generation programs: it's simple to implement, works quickly, and generates very pretty mazes. The algorithm can also be used to solve mazes. This is how MazeGen generates solutions for all mazes, no matter which algorithm was used to create them.