Depth-First Search Maze Generation

//Depth-First Search Maze Generation TorqueScript
//by Frankie L. Taylor 2004

//Based on DFS Algorithm found http://www.mazeworks.com/mazegen/mazetut/

//DFS Algorithm works like this:
//	1) Start at a random cell in the grid.
//	2) Look for a random neighbor cell you haven't been to yet.
//	3) If you find one, move there, knocking down the wall between the cells. 
//	   If you don't find one, back up to the previous cell.
//	4) Repeat steps 2 and 3 until you've been to every cell in the grid.

//When the while loop terminates, the algorithm is completed. Every cell has been 
//visited and thus no cell is inaccessible. Also, since we test each possible move 
//to see if we've already been there, the algorithm prevents the creation of any 
//open areas, or paths that circle back on themselves.

//We can put the start and end points wherever we want. This is another advantage
//of a perfect maze. Since, by definition, one and only one path will exist between 
//any two points in the maze, we know that given a start/end pair, a unique solution
// to the maze must exist.

//Depth-First Search is the most common algorithm used in maze generation programs: 
//it's simple to implement, works quickly, and generates very pretty mazes. 
//The algorithm can also be used to solve mazes. This is how MazeGen generates 
//solutions for all mazes, no matter which algorithm was used to create them.

//-------------------------------------------------------------------------------------

function mazeGenerate(%fileName,%cellMaxX,%cellMaxY){
	 
	//Pararmeters:	%filename	Name of maze file. The *.maz and *.maz.2 are added.
	//			%cellMaxX	Maximum number of horizontal cells.
	//			%cellMaxY	Maximum number or vertical cells.

	//Return:		nothing

	//Description:	Generates maze data in two formats. Data used to assemble random
	//			maze from independent DIF Interiors, DTS Shapes, and Images.

	%filename = "starter.fps/data/missions/" @ %filename @ ".maz"; //change directory path as needed.

	%cellBaseData =	"0000 1000 0100 0010 0001 1100 0110 0011 1001 1110 0111 1011 1101 1010 0101 1111";
	//cellBaseID:	 0    1    2    3    4    5    6    7    8    9    10   11   12   13   14   15
	%cellBaseDataPTR = 0;

	%cellNeighborData = "0 -1 -1 0 0 1 1 0";
	%cellNeighborDataPTR = 0;

	%cellBaseWallKnockoutData = "0 2 1 3 2 0 3 1"; //current,neighbor
	%cellBaseWallKnockoutDataPTR = 0;

	//create a CellStack (LIFO) to hold a list of cell locations
	%cellStackX[0] = 0;
	%cellStackY[0] = 0;
	%cellStackPTR = 0;

	//set TotalCells = number of cells in grid
	%cellTotal = %cellMaxX*%cellMaxY;

	//choose a cell at random and call it CurrentCell
	%cellCurrentX = getRandom(%cellMaxX);
	%cellCurrentY = getRandom(%cellMaxY);

	//create cells: cellBaseWall, cellBaseWallVariance (future use), cellBase, cellBaseVariance(future use)
	//Note: cellbase describes the the cell pattern (See Diagram 1). A cellbase contains upto 4 walls.
	//Each wall can be independent in shape/texture (variance).
	for (%cellX = 0;%cellX < %cellMaxX;%cellX++){
		for(%cellY = 0;%cellY < %cellMaxY;%cellY++){
			%cellBase[%cellX,%cellY] = 0;
			%cellBaseVariance[%cellX,%cellY] = getRandom(15);
			for(%loop = 0;%loop < 4;%loop++){
				%cellBaseWall[%cellX,%cellY,%loop] = 1; //cellwalls = 0:top, 1:left, 2:bottom, 3:right
				//make walls border by variance
				if ( %cellX == 0 || %cellX == %cellMaxX-1 || %cellY == 0 || %cellY == %cellMaxY-1){//borders
					%cellBaseWallVariance[%cellX,%cellY,%loop] = getRandom(16,24); //Borders are BaseWallVariety 16-24
				}
				else{//standard walls
					%cellBaseWallVariance[%cellX,%cellY,%loop] = getRandom(15); //BaseWallVariety 0-15
				}
			}
		}
	}

	//set VisitedCells = 1
	%cellVisited = 1;

	//while VisitedCells < TotalCells
	while(%cellVisited < %cellTotal){

		//find all neighbors of CurrentCell with all walls intact
		%cellNeighborDataPTR = 0;//restore cellNeighborData
		%cellNeighborCount = 0;//reset neighborCount (list)
		for(%loop = 0;%loop<4;%loop++){
			//calculate neighbors
			%cellX = getWord(%cellNeighborData,%cellNeighborDataPTR);
			%cellY = getWord(%cellNeighborData,%cellNeighborDataPTR+1);
			%cellNeighborDataPTR += 2;//increment cellNeighborData

			%cellX += %cellCurrentX;
			%cellY += %cellCurrentY;

			//check if base is within borders
			//if so, check if walls are intact add to neighbor list
			if( %cellX >= 0 && %cellX < %cellMaxX && %cellY >= 0 && %cellY < %cellMaxY ){
				%cellBaseWallsIntact = %cellBaseWall[%cellX,%cellY,0] + %cellBaseWall[%cellX,%cellY,1] + %cellBaseWall[%cellX,%cellY,2] + %cellBaseWall[%cellX,%cellY,3];
				if (%cellBaseWallsIntact == 4){
					//add to neighbor list
					%cellNeighborX[%cellNeighborCount] = %cellX;
					%cellNeighborY[%cellNeighborCount] = %cellY;
					%cellNeighborPos[%cellNeighborCount] = %loop;
					%cellNeighborCount++;
				}
			}
		}

		//if one or more neighbor found
		if (%cellNeighborCount > 0){

			//choose one of the neighbors at random
			%cellNeighborRandom = getRandom(%cellNeighborCount-1);

			//knock down the wall between it and CurrentCell
			%cellBaseWallKnockoutDataPTR = 0;//restore cellBaseWallKnockoutData
			for(%loop = 0;%loop<4;%loop++){//check walls
				%cellBaseWallKnockoutCurrent = getWord(%cellBaseWallKnockoutData,%cellBaseWallKnockoutDataPTR);
				%cellBaseWallKnockoutNeighbor = getWord(%cellBaseWallKnockoutData,%cellBaseWallKnockoutDataPTR+1);
				%cellBaseWallKnockoutDataPTR += 2;//increment cellBaseWallKnockoutData
				if(%cellNeighborPos[%cellNeighborRandom] == %loop){
					%cellBaseWall[%cellCurrentX,%cellCurrentY, %cellBaseWallKnockoutCurrent] = 0;
					%cellBaseWall[%cellNeighborX[%cellNeighborRandom],%cellNeighborY[%cellNeighborRandom],%cellBaseWallKnockoutNeighbor] = 0;
					%loop = 4;//break for loop
				}
			}

			//push CurrentCell location on the CellStack
			%cellStackX[%cellStackPTR] = %cellCurrentX;
			%cellStackY[%cellStackPTR] = %cellCurrentY;
			%cellStackPTR++;

			//make the new cell CurrentCell
			%cellCurrentX = %cellNeighborX[%cellNeighborRandom];
			%cellCurrentY = %cellNeighborY[%cellNeighborRandom];

			//add 1 to VisitedCells
			%cellVisited++;
		}
		else{
			//pop the most recent cell entry off the CellStack and make it CurrentCell
			%cellStackPTR--;
			%cellCurrentX = %cellStackX[%cellStackPTR];
			%cellCurrentY = %cellStackY[%cellStackPTR];
		}//endIf
	} //endWhile

	//maze completed, id cellbases
	for (%cellX = 0;%cellX < %cellMaxX;%cellX++){
		for(%cellY = 0;%cellY < %cellMaxY;%cellY++){
			%cellBaseWallSet1 = %cellBaseWall[%cellX,%cellY,0] @ %cellBaseWall[%cellX,%cellY,1] @ %cellBaseWall[%cellX,%cellY,2] @ %cellBaseWall[%cellX,%cellY,3];
			%cellBaseDataPTR = 0;//restore cellBaseData
			for(%loop = 0;%loop < 16;%loop++){
				%cellBaseWallSet2 = getWord(%cellBaseData,%cellBaseDataPTR);
				%cellBaseDataPTR++;//increment cellBaseData
				if(%cellBaseWallSet2 == %cellBaseWallSet1){
					%cellBase[%cellX,%cellY] = %loop;
                                        %loop = 16;//break
				}

			}
		}
	}

	//write maze data format I
	//Note: if variance is not required omit the lines.
	%file = new fileObject();
	%file.openforWrite(%fileName);
	for (%cellX = 0;%cellX < %cellMaxX;%cellX++){
		for(%cellY = 0;%cellY < %cellMaxY;%cellY++){
			%file.writeLine(%cellBase[%cellX,%cellY]);
			%file.writeLine(%cellBaseVariance[%cellX,%cellY]);
			for(%loop = 0;%loop < 4;%loop++){
				%file.writeLine(%cellBaseWall[%cellX,%cellY,%loop]);
				%file.writeLine(%cellBaseWallVariance[%cellX,%cellY,%loop]);
			}
		}
	}
	%file.close();
	%file.delete();

	//write maze data format II (Optional)
	%file = new fileObject();
	%file.openforWrite(%fileName@".2");
	for(%cellY = 0;%cellY < %cellMaxY;%cellY++){
		%writetext="";
		for (%cellX = 0;%cellX < %cellMaxX;%cellX++){
			%writetext = %writetext @ %cellBase[%cellX,%cellY] @ "\t";
		}
		%file.writeLine(%writetext);
	}
	%file.close();
	%file.delete();	

}