Mazes

Generating perfect mazes with depth first search

by Stephen R. Schmitt

Definition

A perfect maze can be generated easily with a computer using a depth first search algorithm. In a perfect maze, there is one and only one path from any point in the maze to any other point. That is, there are no inaccessible sections, no circular paths, and no open regions.

Maze data structures

A two dimensional maze can be represented as a rectangular array of square cells. Each cell has four walls. The state of each wall (north, south, east, and west) of each cell is maintained in a data structure consisting of an array of records. Each record stores a Boolean value that represents the state of each wall in a cell. To create a path between adjacent cells, the exit wall from the current cell and the entry wall to the next cell are removed. For example, if the next cell is to the right (east) of the current cell, remove the right (east) wall of the current cell and the left (west) wall of the next cell.

Algorithm

Depth first search assumes that, initially, all cell walls are in place. Then these operations are executed:

Select any cell in the array as the current cell. Set the count of cells visited to one.
If one or more neighbor cells exist that have not been visited,

Pick one at random as the next cell.
Remove the walls between the cells.
Make the next cell the current cell.
Increment count of cells visited.
else, if none exist

make the previous cell the current cell (backtrack).

Repeat step 2 until the count of cells visited equals total number of cells.

When the algorithm is completed, every cell has been visited and therefore no cell is inaccessible. Since each cell is visited once (backtracking doesn't count), creation of any open areas or paths that circle back on themselves is prevented. Because one and only one path will exist between any two cells in the maze, the start and end points can be placed anywhere.

Zeno source code

Zeno 1.2 is an interpreter for the Zeno programming language. It is an easy to learn and is suitable for educational purposes.

Download Page

% size of maze
const ROWS : int := 7
const COLS : int := 7

% cell stack to hold a list of cell locations
type LOC : record
           row, col : int
           end record

var stack : array[ROWS*COLS] of LOC
var tos   : int
var next  : array[4] of LOC
var move  : array[4] of LOC
var curr  : LOC

type CELL : record
            N, E, S, W : boolean
            end record

% set total cells to number of cells in grid
const total   : int := ROWS*COLS
var   visited : int

% the maze of cells
var Maze : array[ROWS,COLS] of CELL


program

    var i, j, r, c : int
    
    init_cells

    % choose a cell at random and make it the current cell
    randomize
    curr.row := randint( 1, ROWS )
    curr.col := randint( 1, COLS )
    visited  := 1
   
    while (visited < total)
        % find all neighbors of current cell with all walls intact
        j := 0
        for i := 1...4 do
            r := curr.row + move[i].row
            c := curr.col + move[i].col
            % check for valid next cell
            if (1 <= r) and (r <= ROWS) and (1 <= c) and (c <= COLS) then
                % check if previously visited
                if Maze[r,c].N and Maze[r,c].E and Maze[r,c].S and Maze[r,c].W then
                    % add to possible next cells
                    incr j
                    next[j].row := r
                    next[j].col := c
                end if
            end if
        end for
        
        if (j >= 1) then   
            % current cell has one or more unvisited neighbors
            % so, choose one at random
            i := randint(1, j)
            % remove the walls between it and current cell
            if (next[i].row - curr.row) = 0 then    
                % next on same row
                r := next[i].row
                if next[i].col > curr.col then      
                    % move east
                    c := curr.col
                    Maze[r,c].E := false
                    c := next[i].col
                    Maze[r,c].W := false
                else                                
                    % move west
                    c := curr.col
                    Maze[r,c].W := false
                    c := next[i].col
                    Maze[r,c].E := false
                end if
            else                                    
                % next on same column
                c := next[i].col
                if next[i].row > curr.row then      
                    % move south
                    r := curr.row
                    Maze[r,c].S := false
                    r := next[i].row
                    Maze[r,c].N := false
                else                                
                    % move north
                    r := curr.row
                    Maze[r,c].N := false
                    r := next[i].row
                    Maze[r,c].S := false
                end if
            end if
            % push current cell location on the cell stack
            incr tos
            stack[tos].row := curr.row
            stack[tos].col := curr.col
            % make the new cell current cell
            curr.row := next[i].row
            curr.col := next[i].col
            % add 1 to visited cell count
            incr visited
        else
            % reached dead end, backtrack
            % pop the most recent cell from the cell stack
            % and make it the current cell
            curr.row := stack[tos].row
            curr.col := stack[tos].col
            decr tos
        end if 
    end while
    
    put_maze

end program

procedure init_cells

    var i, j : int

    % set all walls of each cell in maze
    for i := 1...ROWS do
        for j := 1...COLS do
            Maze[i,j].N := true
            Maze[i,j].E := true
            Maze[i,j].S := true
            Maze[i,j].W := true
        end for
    end for

    % index for top of cell stack 
    tos := 0

    % array of single step movements between cells
    move[1].row := -1   % north
    move[1].col :=  0
    move[2].row :=  0   % east
    move[2].col :=  1
    move[3].row :=  1   % south
    move[3].col :=  0
    move[4].row :=  0   % west
    move[4].col := -1

end procedure

procedure put_maze

    var i, j, k : int

    for i := 1...ROWS do
        for k := 1...2 do
            for j := 1...COLS do
                if (k = 1) then 
                    if (Maze[i,j].N) then
                        put "+---"...
                    else
                        put "+   "...
                    end if
                    if (j = COLS) then
                        put "+"...
                    end if
                elsif (k = 2) then
                    if (Maze[i,j].W) then
                        put "|   "...
                    else
                        put "    "...
                    end if
                    if (j = COLS) then
                        put "|"...
                    end if
               end if
            end for
            put ""
        end for
    end for
    for j := 1...COLS do
        put "+---"...
    end for
    put "+"
    
end procedure

Sample output

+---+---+---+---+---+---+---+ 
|       |                   | 
+---+   +---+   +---+---+---+ 
|   |       |               | 
+   +---+   +---+---+---+   + 
|       |                   | 
+   +---+---+---+---+---+   + 
|       |               |   | 
+---+   +   +---+   +---+   + 
|       |   |       |       | 
+   +   +   +   +   +   +---+ 
|   |   |   |   |   |       | 
+   +---+   +   +---+---+   + 
|           |               | 
+---+---+---+---+---+---+---+

AbCd Classics - free on-line books