MazeWorks
Java Games and PuzzlesHomeBooksDownloadLinksEmail
How to Build a Maze


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: 

      
    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 
      find all neighbors of CurrentCell with all walls intact  
      if one or more found 
        choose one at random 
        knock down the wall between it and CurrentCell 
        push CurrentCell location on the CellStack 
        make the new cell CurrentCell 
        add 1 to VisitedCells
      else 
        pop the most recent cell entry off the CellStack 
        make it CurrentCell
      endIf
    endWhile 
     

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 themselves. 

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. 

MazeGen