Introduction

This article describes an algorithm for the generation of random mazes, and includes an implementation of the algorithm in C++. In the interest of completeness, code is also provided to display the results of the algorithm using a Windows "console" application.

Background

The term "maze" encompasses a wide variety of two-dimensional (2D) figures through which a player must find a path. For the purposes of this article, "maze" is taken to mean a 2D map consisting of open and closed areas, with a single open path from start to finish.

Furthermore, the design of the mazes generated here is constructed using right angles only. However, it should be noted that at sufficiently high resolution, these right angles can resolve into a variety of shapes and curves, and in such cases reliance upon right angles will not be apparent to the end user. An example of an output figure rendered by the program is shown below: 



Note that this program represents a very rudimentary application of the algorithm. A more realistic application might render each filled square as a rectangular prism (e.g., a cube) and allow the user's character to maneuver between these using a 3D rendering engine. For example, one game I developed around these mazes presents them using 3D wireframe models, as shown in the figure below: 


The presentation technology used to generate this wireframe display is outside the scope of this article. But the underlying generation of the level maps is exactly as described here. The mazes generated by the code presented here can be translated into polygons such as these in a mechanical fashion.

Using the Code

The actual code for this article is quite brief, and is presented in its entirety below this section. I used the MinGW compiler during development, but any C++ compiler capable of targeting Win32 should be capable of compiling the source. In fact, the platform-dependent portion of the code is really limited to the gotoxy() function. In the code presented here, this function calls the Win32 SetConsoleCursorPosition() function. However, this implementation is shown only in the interest of providing a complete, runnable project.

Prior to the call to print_maze() made from main(), the array "whole_maze" holds a generalized representation of the maze. This representation is applicable to maze games running on a wide variety of computing platforms. The whole_maze array is two-dimensional, with size equal to (XSIZE + 2) in the left (major) dimension and (YSIZE + 2) in the other dimension. XSIZE and YSIZE are compile-time constants. These define the size of the maze, which is rectangular in shape. The addition of 2 to each of these reflects the presence of a constant, solid, single-unit border surrounding all mazes. The element whole_maze[0][0] corresponds to the topmost, leftmost coordinate in the maze display, and whole_maze[XSIZE+1][YSIZE+1] corresponds to the bottommost, rightmost coordinate.

Each element of this array will contain a 0, 1, or 2. Zero signifies a solid polygon which obstructs character movement. One signifies an open path (empty space) which is not part of the "solution" path from start to finish. Values of two are used to mark the solution path. This path begins at the leftmost column of the overall maze, and continues to the rightmost column.
/***********
Generates and prints single-solution mazes to the Win32 console.
 
By J. Beau Wilkinson
***********/
 
#include <cstdio>
#include <windows.h>
#include <iostream>
 
using std::cout;

 
#define XSIZE 25
#define YSIZE 15
#define DIFFICULTY 12
#define OBFUSCATION_LOOP_RUNS (XSIZE * YSIZE * 20) 
 
//Logic constants for map contents
#define SOLUTION_PATH 2
#define FALSE_PATH 1
#define NO_PATH 0
 
//North is designated as pointing to top of display
#define EAST 0
#define SOUTH 1
#define WEST 2
#define NORTH 3
 
//ASCII block
#define MAZE_WALL ((char)219)
 
//Positions cursor in Win32 app
void gotoxy(int x, int y)
{
    COORD coord;
    coord.X = x;
    coord.Y = y;
    SetConsoleCursorPosition(GetStdHandle(STD_OUTPUT_HANDLE), coord);
}
 
//Display a text representation of the maze
void print_maze(int a[XSIZE][YSIZE]) 
{
    int x,y;
 
    //Clear the screen
    system("cls");
 
    //Print a border
    for(x=1; x<=XSIZE ; ++x )
    {
        //"1" means top row
        gotoxy(x,1);
        cout<<MAZE_WALL;
 
        //+2 accounts for top and bottom borders
        gotoxy(x,YSIZE+2);
        cout<<MAZE_WALL;
    } 
 
    //Print the maze's inside, one coordinate at a timex
    for(y=0; y<YSIZE ; ++y )
    {
        for(x=0; x<XSIZE ; ++x )
        {
            gotoxy(x+1,y+2);
    
            switch(a[x][y]){
            //Wall
            case NO_PATH:
                cout<<MAZE_WALL;
                break;
    
            //False path... show " "
            case FALSE_PATH:
                cout<<' ';
                break;
    
            //Solution path... show "."
            case SOLUTION_PATH:
                cout<<'.';
                break;
            }
        }
    }
}
 
void make_solution(int a[XSIZE][YSIZE]){
 
    //After each turn in the correct path, this variable
    //  will be set to the length of the "leg" i.e. the
    //  number of squares that the path continues before 
    //  the next turn. 3 is a suitable initial value for
    //  any maze.
    int path_leg_length=3;
 
    //Temporary position and direction variables
    int x=0,y=0;
    int d=EAST;
 
    bool facing_east_west=true;
 
    //Start at a random row at column 0
    y=rand()%YSIZE;
 
    //Build correct path column by column
    while(x<XSIZE)
    {
        //March forward designated leg length in current direction
        while(path_leg_length-- && x<(XSIZE))
        {
            switch(d)
            {
            case EAST:
                a[x++][y]=SOLUTION_PATH;
                break;
 
            case SOUTH:
                a[x][y++]=SOLUTION_PATH;
                break;
 
            case WEST:
                a[x--][y]=SOLUTION_PATH;
                break;
 
            case NORTH:
                a[x][y--]=SOLUTION_PATH;
                break;
            }
          }
 
          int tempx,tempy;
 
        do
        {
            tempx=x;
            tempy=y;
 
            //Time for a turn...
            // e/w ->  n/s ; n/s -> east
            if(facing_east_west)
            {
                d=(rand()%2)?NORTH:SOUTH;
 
            }else{
                d=EAST;
            }
 
            //Close to end; just complete the path
            if(XSIZE-x<3)
            {
                d=EAST;
                path_leg_length=XSIZE-x;
            }
 
            /*Don't require travel to West... a compromise
            that simplifies things. In practice, the user
            in the heat of battle will perceive a series of
            left and right turns w/o noticing absolute 
            direction. Also, the user will inevitably 
            deviate from the correct path, possibly requiring
            travel to the west. */
 
            //Set path_leg_length... must be at least 3 or we will make
            // "rooms," which would defy the design criteria stating that
            // there ought only to be one correct path through the maze.
            if(facing_east_west)
            {
                path_leg_length=((rand()%(XSIZE/DIFFICULTY)+2));
            }else{
                path_leg_length=((rand()%(YSIZE/DIFFICULTY)+2));
            }
 
            switch(d)
            {
                case EAST:
                    tempx+=path_leg_length;
                    break;
            
                case SOUTH:
                    tempy+=path_leg_length;
                    break;
 
                case WEST:
                    tempx-=path_leg_length;
                    break;
 
                case NORTH:
                    tempy-=path_leg_length;
                    break;
            }
            //check here for overflow condition - JBW
        }while(tempx<0||tempy<0||tempy>=YSIZE);
 
        // Decided on a new direction... if prior direction
        //  was vertical, new direction is horizontal and vice-versa
        facing_east_west=!facing_east_west;
    }
}
 
//For a given X,Y coord. within a given maze, determines if
//  opening up X,Y as a path will obfuscate the maze without
//  introducing an additional path b/w start and finish. Also,
//  the logic below will prevent "orphaned" openings, i.e.
//  isolated paths that don't connect to anything else.
bool valid_for_obfuscation(int x, int y,int a[XSIZE][YSIZE])
{
    //Check ranges
    if(x<=0) return false;
    if(y<0) return false;
    if(x>=XSIZE-1) return false;
    if(y>=YSIZE) return false;
 
    //Already part of the open paths
    if(a[x][y]) return false;
 
    //It's a valid point of obfuscation iff exactly one of the adjacent
    // points is open. If 2+ such points are open, then we're potentially
    // creating a "shortcut," which would result in a 2nd path between
    // start and finish. If 0 such points are open, we're potentially
    // creating an orphan.
    int ret=0;
  
    if(a[x+1][y]) ++ret;
    if(x-1>=0 && a[x-1][y]) ++ret;
    if(y+1<YSIZE  && a[x][y+1]) ++ret;
    if(y-1>=0 && a[x][y-1]) ++ret;
 
    if (ret==1)return true;
    else return false;
}
 
void obfuscate_maze(int a[XSIZE][YSIZE])
{
    int x,y;
    int c=0;
 
    for(int ob=0; ob < OBFUSCATION_LOOP_RUNS; ++ob)
    {
        x=rand()%XSIZE;
        y=rand()%YSIZE;
    
        if(valid_for_obfuscation(x,y,a))
        {
            c++;
            a[x][y]=FALSE_PATH;
        }
    }
}
 
int main()
{
    //"static" doesn't affect values or lifetime here, only location,
    //  i.e. it keeps these off the stack w/o requiring use of a
    //  global variable.
    static int whole_maze[XSIZE+2][YSIZE+2];
 
    srand(time(0));
    int (*maze_innards)[YSIZE];
 
    do{

 //Just a simple way to surround maze w/ walls... see below...
        for(int idx=0; idx<XSIZE+2; ++idx)
            for(int idx2=0; idx2<YSIZE+2; ++idx2)
                whole_maze[idx][idx2]=0;
 
 // "Innards" exclude the outer wall... it's worth noting that the array mapping
 //   function inherent to the nested "for" loops just above is completely 
 //   abandoned by the cast operation below. However, the overall purpose of this
 //   "for" block (i.e. to surround maze_innards with walls, which is assumed by
 //   the solve/obfuscate algorithm) is preserved. 

        maze_innards=(int(*)[YSIZE])(&whole_maze[0][1]);
 
        make_solution(maze_innards);
        obfuscate_maze(maze_innards);
        print_maze(maze_innards);
 
        cout<<"\n\n\nPress ENTER for next map...\n";
        cout<<"\n\n\nPress CTRL+C to exit...\n";
 
        getchar();
 
    }while(true);
 
    return 0;
}

Points of Interest

In summary, the algorithm works by first defining the "solution" to the maze. The solution path begins at the left side of the maze and proceeds to the right side. This solution path is generated by the make_solution() function. The solution path consists of a number of "legs". Each leg is a straight, contiguous section of open squares (in the array, these show up as "2" values). The average length of each leg is random, but is affected by the DIFFICULTY constant. At the completion of each leg, a new direction for the next leg is selected. A North / South leg will always be followed by a leg running East. An East-running leg will be followed by a North or South-running leg.

There are no West-running legs. This simplifies the algorithm, and should not be readily apparent to the end user. The path taken by the user will consist of a series of left and right turns, and the proportion of left turns to right is not altered by the exclusion of westbound solution legs. Also, the user will almost always become lost or disoriented at some point. Typically, the user will in fact have to travel West to rejoin the solution path. It will thus not be obvious that the "perfect" solution never heads West.

After its generation, the solution is augmented in ways guaranteed not to introduce additional solutions. This augmentation is termed "obfuscation" in the comments and identifiers within the source given above. Obfuscation is performed by the obfuscate_maze() function. It places "1" values into the whole_maze array to obscure the solution path. The obfuscate_maze() function randomly selects X, Y coordinates contained within the whole_maze array. The number of points selected is controlled by the constant named OBFUSCATION_LOOP_RUNS. This function then calls another function, which is named valid_for_obfuscation(), to determine whether the selected coordinate should receive a "1" value.

The valid_for_obfuscation() function is really the heart of the algorithm. Coordinates are considered "valid" recipients of a "1" (false path) value if they border one and only one open ("1" or "2" element value) coordinate. Coordinates bordering more than one open square are not valid points for obfuscation. Placing a "1" in such a coordinate would introduce a cyclic path, or perhaps a shortcut. In either case, the single correct path would be augmented by additional correct paths, defying the specification. Coordinates with no adjacent open squares are not valid for obfuscation either, since inaccessible paths are considered undesirable. Over the course of execution of obfuscate_maze(), points will become invalid / valid for obfuscation. So, it is necessary to call valid_for_obfuscation() multiple times per point. OBFUSCATION_LOOP_RUNS will thus often exceed the total number of array elements. Lower values of OBFUSCATION_LOOP_RUNS will produce a maze with fewer possible wrong turns.