Backtracking

Contents

Maze Generation

Chapter 3 : Maze Generation

In this chapter, we will look at how the 'Mysterious Maze' program creates random mazes. The class of mazes that the program generates are referred to as Perfect mazes, because any two cells of the maze are connected by a single unique path. The program uses the top left cell as the start and the bottom right cell as the finish, but any two randomly selected cells could be chosen as start and finish. Perfect mazes do not contain any dead zones, areas which are inaccessible by any path. They also differ from Cyclic mazes, in which more than one solution to the maze is possible. A depth-first search algorithm is used to generate the maze.

The Algorithm

The program, like most maze generators, starts off by building a maze with all the walls between the cells intact. It then chooses a random cell as it's starting point and proceeds to knock down the walls using the following recursive algorithm.

Mark the current cell as 'Visited';

If the current cell has any neighbours which have not been visited 
	{
	 Choose one of the unvisited neighbours;
	 Push the current cell on the stack;
	 Knock down the wall between the current 
                   cell and the chosen cell;
	 Make the chosen cell the current cell;
	 Recursively call this function;
	}
else
	{
	 Pop the last current cell off the stack;
	 Backtrack to the previous execution of this function;
	}

This algorithm is topology independent - it will work for both 2D and 3D mazes, and the cells could be square, hexagonal, or whatever shape you choose. It does have a major problem though, the mazes it generates are comparatively easy to solve because it tends to produce long winding paths with little or no branching. Although there are many better maze generating algorithms, this one was chosen because of it's relative simplicity and it's use of backtracking.

The Data Structure

The maze is represented internally by the program as a three-dimensional array of cells, with the first and second dimensions being the Row and Column of the cell respectively, and the third dimension representing the attributes of the cell. Each cell in the maze has 3 binary attributes, BOTTOMWALL, which is 0 if the cell has no bottom wall and 1 if it does, RIGHTWALL, which similarly represents whether the cell has a right wall or not, and VISITED, which is used by the maze generation algorithm.

Thus, the maze above would be internally represented as -

Maze[0][0][RIGHTWALL]=0;    Maze[0][0][BOTTOMWALL]=1;
Maze[0][1][RIGHTWALL]=1;    Maze[0][1][BOTTOMWALL]=0;
Maze[0][2][RIGHTWALL]=1;    Maze[0][2][BOTTOMWALL]=0;

Maze[1][0][RIGHTWALL]=1;    Maze[1][0][BOTTOMWALL]=0;
Maze[1][1][RIGHTWALL]=1;    Maze[1][1][BOTTOMWALL]=0;
Maze[1][2][RIGHTWALL]=1;    Maze[1][2][BOTTOMWALL]=0;

Maze[2][0][RIGHTWALL]=0;    Maze[2][0][BOTTOMWALL]=1;
Maze[2][1][RIGHTWALL]=0;    Maze[2][1][BOTTOMWALL]=1;
Maze[2][2][RIGHTWALL]=1;    Maze[2][2][BOTTOMWALL]=1;

The Code

We will now look at the code that uses the depth-first search algorithm on the maze data structure in order to generate the maze.

The program calls the MakeMaze function to begin the maze generation. This function initializes the RIGHTWALL and BOTTOMWALL attributes of all the cells to 1 (remember the algorithm starts out with all walls intact). It also initializes all VISITED attributes to false. It then chooses a random cell as it's starting point, and proceeds to call the MakePath function with the Row and Column of this chosen cell as parameters.

MakePath is a backtracking function which takes 3 parameters, the Row and the Column of the cell it is currently evaluating, and the Direction that the previous execution of the algorithm had taken. It uses this Direction parameter to decide which wall to break down. Of course, when it is called initially by the MakeMaze function, the Direction parameter is blank, therefore no walls are broken. The first thing that the MakePath function does is to mark the current cell as visited (Maze[R][C][VISITED]=true).

The function then builds an array of the possible directions it can take (N,S,E or W), goes through these directions one by one, calling itself with the Row and Column of the cell in that direction, with the direction itself as the third parameter. Of course, it will only go in that direction if the cell in that direction has not already been visited.

A word of warning here, before we move on to see the program itself. Variables within recursive procedures like the MakePath function must be declared with the var statement. This is because undeclared variables do not revert to their previous values when the procedure backtracks to a previous execution. To understand what I mean, open the Mysterious Maze program in a text editor, and remove the word var wherever it occurs in the function. Then try running the program. You will find that the maze will have only been partially generated, and that the MakePath function stopped executing the first time it tried to backtrack. On to the program now, and have fun.

Prev : Decision Trees Next : Mysterious Maze