Random Maze Generator in C (Source Code Included)

Amazon I actually walk you through creating a random maze at Program to Create a Random Maze. You can check how I approached this interesting problem. The entire source code is shown below!

I developed this program in C which accepts a set of parameters and generates a random maze based on those parameters, then generates a .m file which Matlab uses to display the maze and its solution.

The reason I chose Matlab is Matlab has nice support for displaying a drawing of basic lines and shapes.

The way this program works is it uses the mathematical notion of a SET.

Consider a 5-by-5 maze, which has 25 cells totally. The initial configuration of the maze should be that all walls are up, and that situation is simulated by having each cell belong to its own set.

Now you find a wall at random, check to see if the cells sharing that wall belong to the same set. If so, ignore them because they are already connected with each other. If not, knock down the wall and merge them so that they are in the same set.

The point is that there should be exactly one path to go from one cell to another. If you keep knocking down walls this way, at some point all cells will belong to the same set while only several walls are knocked down. Then a maze is generated and you are done.

Here is a screen shot of a rectangular maze (50 units by 50 units):



And here is a screen shot of a pentagon maze (5 sides, 10 units a side and 10 levels deep):



And here is a screen shot of an oval or a round or circle maze (30 sides, 2 units a side, 10 levels deep):



As promised here's the entire source code in C++. Use it wisely.

/*
Michael Wen
6/1/2003
This program generates a random rectangular maze given the width and the height.
*/
#include<iostream>
#include<fstream>
#include<string>
#include<vector>
#include<ctime>
using namespace std;

double unit=1, xOffset, yOffset;
int width, height, numOfCells;
ofstream fout2;
vector<int> lottery, sol;

void remove(int);
void findSol(int, int);
void displaySol();

class Maze{
public:
	Maze(int);
	int find_root(int);	
	void union_cell(int, int);
	
	vector<int> s;  /* parent's id */
	vector<double> xcoord;  /* lower right coordinate x */
	vector<double> ycoord;  /* lower right coordinate y */
/* for the next two vectors, -1 means down, 0 means must be up 1 means up */
	vector<int> down;	  /* lower wall; knocked down or there */
	vector<int> right;  /* right wall; knocked down or there */
	vector<int> visited;  /* 1 means visited and 0 means not visited yet while finding solution */
};

Maze *d;

/*
precondition: n must be a positive integer
postcondition: s, xcoord, ycoord, down, right, visited are assigned values
*/
Maze::Maze(int n){
	int i,x,y,temp;

	for(i=0; i<n; i++){
		s.push_back(-1);
		x = i%width+1;
		y = height-i/width-1;
		xcoord.push_back(xOffset+x*unit);
		ycoord.push_back(yOffset+y*unit);
		temp = i>=width*(height-1) ? 0 : 1;
		down.push_back(temp);
		temp = (i+1)%width==0 ? 0 : 1;
		right.push_back(temp);
		visited.push_back(0);
	}
}
/*
precondition: n must be >= 0 and < s.size()
postcondition: return the root of n
*/
int Maze::find_root(int n){
	return s[n]<0 ? n : find_root(s[n]);
}
/*
precondition: root1 and root2 both must be >= 0 and < s.size()
postcondition: root1 and root2 belong to the same set
*/
void Maze::union_cell(int root1, int root2){
	s[find_root(root2)] = root1;
}

int main(int argc, char** argv){
/* exit if something is missing in the command line */
	if(argc!=5){
		cout << 'usage: exe <width> <height> <file1> <file2>
';
		cout << '<width>: # of columns, must be >= 2
';
		cout << '<height>: # of rows, must be >= 2
';
		cout << '<file1>: maze w/t solution file's name
';
		cout << '<file2>: maze w/ solution file's name
';
		cout << endl;
		exit(1);
	}

	char *file, *file2;
	ofstream fout;
	int i, victim, neighbor, neighbor2;
	width = atoi(argv[1]);
	height = atoi(argv[2]);
/* exit if the user provides unacceptable information */
	if(width<2 || height<2){
		cout << 'unacceptable command line, forced exit

';
		exit(1);
	}

/* initialize the random number generator */
	srand(time(0));   

/* store critical data in variables */
	xOffset = width/20.0;
	yOffset = height/20.0;
	numOfCells = width*height;
	file = argv[3];
	file2 = argv[4];
	d = new Maze(width*height);

/* push all elements into a vector except the last one because it has no walls to knock down */
	for(i=0; i<width*height-1; i++)
		lottery.push_back(i);
/* use a while loop to construct the maze */
	while(lottery.size()!=0){ 
		victim = lottery[rand()%lottery.size()];
/*victim has two neighbors*/
		if(d->down[victim]!=0 && d->right[victim]!=0){
			neighbor = victim+1;
			neighbor2 = victim+width;
/* if neither of them is joined, pick one and knock down the mutual wall */
			if(d->find_root(neighbor)!=d->find_root(victim) &&
				d->find_root(neighbor2)!=d->find_root(victim)){
				if(rand()%2==0){
					d->union_cell(victim, neighbor);
					d->right[victim] = -1;
				}
				else{
					d->union_cell(victim, neighbor2);
					d->down[victim] = -1;
				}
			}
/* if only one of them is joined, join another one and knock down the intersecting wall AND remove victim in vector lottery */
			else if(d->find_root(neighbor)!=d->find_root(victim)){
				d->union_cell(victim, neighbor);
				d->right[victim] = -1;
				remove(victim);
			}
			else if(d->find_root(neighbor2)!=d->find_root(victim)){
				d->union_cell(victim, neighbor2);
				d->down[victim] = -1;
				remove(victim);
			}
/* if both of them are joined, remove victim in vector lottery */
			else
				remove(victim);
			
		}
/*victim has one neighbor*/
		else{
/* determine which neighbor it is and if they are joined if not joined, join them and knock down the wall if joined, do nothing */
			if((victim+1)%width==0){
				neighbor = victim+width;
				if(d->find_root(neighbor)!=d->find_root(victim)){
					d->union_cell(victim, neighbor);
					d->down[victim] = -1;
				}
			}
			else{
				neighbor=victim+1;
				if(d->find_root(neighbor)!=d->find_root(victim)){
					d->union_cell(victim, neighbor);
					d->right[victim] = -1;
				}
			}
			remove(victim);
		}
	}

/* generate code for matlab to display the maze */
	fout.open(file);	
	fout2.open(file2);

/*first draw lines for outside walls in both files, note there are 4 openings*/
	fout << 'axis([0 ' << 2*xOffset+width*unit << ' 0 ' << 2*yOffset+height*unit 		<< ']);';
fout << endl;
/*upper line*/
	fout << 'x=[' << xOffset << ' ' << xOffset+width*unit << '];' << endl;
	fout << 'y=[' << yOffset+height*unit << ' ' << yOffset+height*unit << '];' << 			endl;
	fout << 'line(x,y)' << endl;
/*left line*/
	fout << 'x=[' << xOffset << ' ' << xOffset << '];' << endl;
	fout << 'y=[' << yOffset+height*unit-unit << ' ' << yOffset << '];' << endl;
	fout << 'line(x,y)' << endl;
/*right line*/
	fout << 'x=[' << xOffset+width*unit << ' ' << xOffset+width*unit << '];' << 			endl;
	fout << 'y=[' << yOffset+height*unit << ' ' << yOffset+unit << '];' << endl;
	fout << 'line(x,y)' << endl;
/*lower line*/
	fout << 'x=[' << xOffset << ' ' << xOffset+width*unit << '];' << endl;
	fout << 'y=[' << yOffset << ' ' << yOffset << '];' << endl;
	fout << 'line(x,y)' << endl;

/*second file...*/
	fout2 << 'axis([0 ' << 2*xOffset+width*unit << ' 0 ' << 					2*yOffset+height*unit << ']);';
fout2 << endl;
/*upper line*/
	fout2 << 'x=[' << xOffset << ' ' << xOffset+width*unit << '];' << endl;
	fout2 << 'y=[' << yOffset+height*unit << ' ' << yOffset+height*unit << '];' 			<< endl;
	fout2 << 'line(x,y)' << endl;
/*left line*/
	fout2 << 'x=[' << xOffset << ' ' << xOffset << '];' << endl;
	fout2 << 'y=[' << yOffset+height*unit-unit << ' ' << yOffset << '];' << endl;
	fout2 << 'line(x,y)' << endl;
/*right line*/
	fout2 << 'x=[' << xOffset+width*unit << ' ' << xOffset+width*unit << '];' << 			endl;
	fout2 << 'y=[' << yOffset+height*unit << ' ' << yOffset+unit << '];' << endl;
	fout2 << 'line(x,y)' << endl;
/*lower line*/
	fout2 << 'x=[' << xOffset << ' ' << xOffset+width*unit << '];' << endl;
	fout2 << 'y=[' << yOffset << ' ' << yOffset << '];' << endl;
	fout2 << 'line(x,y)' << endl;

/*draw interior walls in both files*/
	for(i=0; i<numOfCells; i++){
		if(d->right[i]==1 && d->down[i]==1){
			fout << 'x=[' << d->xcoord[i]-unit << ' ' << d->xcoord[i] << ' ';
fout << d->xcoord[i] << '];' << endl;
			fout << 'y=[' << d->ycoord[i] << ' ' << d->ycoord[i] << ' ';
fout << d->ycoord[i]+unit << '];' << endl;
			fout << 'line(x,y)' << endl;

			fout2 << 'x=[' << d->xcoord[i]-unit << ' ' << d->xcoord[i] << ' ';
fout2 << d->xcoord[i] << '];' << endl;
			fout2 << 'y=[' << d->ycoord[i] << ' ' << d->ycoord[i] << ' ';
fout2 << d->ycoord[i]+unit << '];' << endl;
			fout2 << 'line(x,y)' << endl;
		}
		else if(d->right[i]==1){
			fout << 'x=[' << d->xcoord[i] << ' ' << d->xcoord[i] << '];' << 					endl;
			fout << 'y=[' << d->ycoord[i] << ' ' << d->ycoord[i]+unit << '];' 					<< endl;
			fout << 'line(x,y)' << endl;
			fout2 << 'x=[' << d->xcoord[i] << ' ' << d->xcoord[i] << '];' << 					endl;
			fout2 << 'y=[' << d->ycoord[i] << ' ' << d->ycoord[i]+unit << 					'];' << endl;
			fout2 << 'line(x,y)' << endl;
		}
		else if(d->down[i]==1){
			fout << 'x=[' << d->xcoord[i]-unit << ' ' << d->xcoord[i] << '];' 					<< endl;
fout << 'y=[' << d->ycoord[i] << ' ' << d->ycoord[i] << '];' << 			endl;
			fout << 'line(x,y)' << endl;
			fout2 << 'x=[' << d->xcoord[i]-unit << ' ' << d->xcoord[i] <<						'];' << endl;
			fout2 << 'y=[' << d->ycoord[i] << ' ' << d->ycoord[i] << '];' << 					endl;
			fout2 << 'line(x,y)' << endl;
		}
	}
	fout.close();

/* find and put solution code in the solution file */
	findSol(0, numOfCells-1);

	return 0;
}

/*
precondition: victim should, but not must, be an element in lottery
postcondition: victim is erased from lottery
*/
void remove(int victim){
	vector<int>::iterator vi;
	for(vi=lottery.begin(); vi!=lottery.end(); vi++)
		if(*vi==victim){
			lottery.erase(vi);
			return;
		}
}
/*
precondition: from and to must be >= 0 and < numOfCells
postcondition: findSol terminates by either calling displaySol or running out; sol stores the solution to the maze
*/
void findSol(int from, int to){
	sol.push_back(from);
	d->visited[from] = 1;
	if(from==to){
		displaySol();	
		exit(0);
	}
/*right wall is knocked down*/
	if(from>=0 && from<numOfCells && d->right[from]==-1){
		if(d->visited[from+1]!=1) {
			findSol(from+1, to);
			sol.pop_back();
		}
	}
/*lower wall is knocked down*/
	if(from>=0 && from<numOfCells && d->down[from]==-1){
		if(d->visited[from+width]!=1) {
			findSol(from+width, to);
			sol.pop_back();
		}
	}
/*upper wall is knocked down*/
	if(from-width>=1 && from-width<numOfCells && 
d->down[from-width]==-1){
		if(d->visited[from-width]!=1) {
			findSol(from-width, to);
			sol.pop_back();
		}
	}
/*left wall is knocked down*/
	if(from%width!=0 && from-1>=1 && from-1<numOfCells && 
d->right[from-1]==-1){
		if(d->visited[from-1]!=1) {
			findSol(from-1, to);
			sol.pop_back();
		}
	}
}
/*
precondition: none
postcondition: put code for displaying the maze in file2
*/
void displaySol(){
	int i;
	
	if(sol.size()<=1){
		fout2.close();
		return;
	}
	fout2 << 'hold on
';
/* construct vectors x and y then use plot command to plot 'g' in plot means green */
	fout2 << 'x=[';
	for(i=0; i<sol.size(); i++){
		fout2 << d->xcoord[sol[i]]-unit/2  <<  ' ';
	}
	fout2 << '];
y=[';
	for(i=0; i<sol.size(); i++){
		fout2 << d->ycoord[sol[i]]+unit/2  <<  ' ';
	}
	fout2 << '];' << endl;
	fout2 << 'plot(x,y,'g')' << endl;

	fout2.close();
}

Any question let me know by making a comment below!