Creating A Random Maze - Step 4

◀ Creating A Random Maze - Step 3▶ Exercise #6: Solving Draught Puzzle Amazon Let’s apply the last step of the Four-Step Programming Model to generate a random maze!

Four Step Programming Model: Step 4
As I am coding, I realize I need more variables to store important information. Also, while constructing the maze, there are slightly more things I need to do than the skeleton suggests.

Since I will be displaying the maze, I need to store extra information such as each cell’s location. This is what xcoord and ycoord are for; they are the location of the lower right point of each cell.

Anyway, the entire program is well commented, so you shouldn’t have difficulty understanding any part of the program.

/*
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>\n";
		cout << "<width>: # of columns, must be >= 2\n";
		cout << "<height>: # of rows, must be >= 2\n";
		cout << "<file1>: maze w/t solution file's name\n";
		cout << "<file2>: maze w/ solution file's name\n";
		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\n\n";
		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\n";
/* 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 << "];\ny=[";
	for(i=0; i<sol.size(); i++){
		fout2 << d->ycoord[sol[i]]+unit/2  <<  ' ';
	}
	fout2 << "];" << endl;
	fout2 << "plot(x,y,'g')" << endl;

	fout2.close();
}

If you have written the entire program by yourself, then you definitely see a marked improvement in your skills!

If you are ambitious and adventurous enough, you can try writing a maze generator that generates a maze of a regular polygon of specified shape such as a triangle, a pentagon, or a hexagon.
This extra feature would take a lot of math skills, particularly in geometry, and knowing geometry well certainly gives you an edge with writing this program. This is yet another example on how closely related programming and math can be, as Chapter 16.12 discusses.

Next let’s solve a great puzzle called the Draught Puzzle!
◀ Creating A Random Maze - Step 3▶ Exercise #6: Solving Draught Puzzle