/* maze.cpp: Class that implements the creation and management of a maze. Uses a Recursive backtracking algorithm

   Copyright (C) 2008  Stuart William Coulson

   This program is free software: you can redistribute it and/or modify
   it under the terms of the GNU General Public License as published by
   the Free Software Foundation, either version 3 of the License, or
   (at your option) any later version.

   This program is distributed in the hope that it will be useful,
   but WITHOUT ANY WARRANTY; without even the implied warranty of
   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
   GNU General Public License for more details.

   You should have received a copy of the GNU General Public License
   along with this program.  If not, see <http://www.gnu.org/licenses/>.

*/

#include <stack>
#include <iostream>
#include <sps2regstructs.h>
#include <sps2lib.h>
#include <sps2util.h>
#include <sps2tags.h>
#include "sps2wrap.h"
#include "PS2Defines.h"
#include "dma.h"
#include "pipeline.h"
#include "maze.h"

mazePosition::mazePosition() {							// mazePosition Contructor
	x = 0;
	y = 0;
}

mazePosition::mazePosition(int posX, int posY) {		// mazePosition Constructor with position parameters
	x = posX;
	y = posY;
}

bool mazePosition::operator== (mazePosition param) {	// mazePosition Comparison operator
	if ((x == param.x) && (y == param.y)) {				// Return true if both position variables in the objects are the same else return false
		return true;
	}
	return false;
}

void mazePosition::operator= (mazePosition param) {		// mazePosition Assignment operator
	x = param.x;										// Assign position values from second object to the first
	y = param.y;
	
	return;
}

maze::maze(int xSize, int ySize) {						// maze Constructor
	mazeWidth = xSize;									// Save height and width variables based on parameters
	mazeHeight = ySize;
	mazeArray = new bitset<5>[mazeHeight * mazeWidth];	// Create a section of memory to hold the representation of the maze
	numberWalls = (mazeWidth * mazeHeight) * 4;			// Work out number of walls before any are removed. Needed when building the mesh of the walls.
	mazeWallPointer = 0;								// Wall mesh pointer set to 0
	generateMaze();										// Call the function that will randomly generate maze
}

maze::~maze() {											// maze Destructor
	delete mazeArray;									// Free memory holding maze representation
}


// Check to see if it is possible to move in a particular direction from a cell. Within memory each cell is represented by 5 bits. Bit 0 is only used during construction of maze. Bit 1 represents the north wall of a cell, bit 2 the west, bit 3 the east and bit 4 the south. If a bit is set there is a wall in that direction.
bool maze::moveDirection(int xCell, int yCell, mazeDirection direction) {		
	switch (direction) {														// Switch based on the direction we are interested in
		case up:																
			if (mazeArray[(yCell * mazeWidth) + xCell].test(1)) {				// Check maze representation for the correct cell and if bit 1 set then there is a wall above so moving up is impossible. Return false. Works in the same way for other directions but different bit is tested.
				return false;
			}
			break;
		case left:
			if (mazeArray[(yCell * mazeWidth) + xCell].test(2)) {
				return false;
			}
			break;
		case right:
			if (mazeArray[(yCell * mazeWidth) + xCell].test(3)) {
				return false;
			}
			break;
		case down:
			if (mazeArray[(yCell * mazeWidth) + xCell].test(4)) {
				return false;
			}
			break;
	}
	return true;																// If the bit is not set then true is returned as move can be made
}

bool maze::uploadTextures(const char * floorTexture, const char * wallTexture) {		// Upload the textures of the maze, floor and wall. Parameters will be filenames of the textures.
	if (!groundTex.LoadBitmap(floorTexture)) {											// Return a bool based on success so if a texture does not load it can be handled elsewhere.
		return false;
	}
	if (!wallTex.LoadBitmap(wallTexture)) {
		return false;
	}
	return true;
}

void maze::outputMaze() {																// Debugging function to see the maze in memory
	for (int x = 0; x < mazeWidth; x++) {												// Draw northern most outer wall which is alway there.
		cout << " _";
	}
	cout << endl;
	for (int y = 0; y < mazeHeight; y++) {												// Loop through each cell and print out the walls that surround it
		for (int x = 0; x < mazeWidth; x++) {
			if (x == 0) cout << "|";													// Print of the western most outer wall which is always there.
			if (mazeArray[y * mazeWidth + x].test(4)) cout << "_"; else cout << " ";	// If there is a southern wall to the cell print symbol
			if (mazeArray[y * mazeWidth + x].test(3)) cout << "|"; else cout << " ";	// If there is an eastern wall to the cell print symbol
		}
		cout << endl;
	}
	cout << numberWalls << endl;
}
		
void maze::generateMaze() {																	// Function that generates the maze representation in memory. Uses recursive backtracking.
	for (int y = 0; y < mazeHeight; y++) {													// Set all the walls of the maze in memory to 1 as we will carve them away as we progress. Also set all zero bits to 1 as we have yet to visit and cells.
		for (int x = 0; x < mazeWidth; x++) {
			mazeArray[y * mazeWidth + x].set();
		}
	}
	
	int xCell = rand() % mazeWidth;										// Select a random cell to begin
	int yCell = rand() % mazeHeight;
	
	mazeArray[yCell * mazeWidth + xCell].flip(0);						// Set this cells 0 bit to 0 as we have visited it
	
	stack<mazePosition> mazeStack;										// Create a stack that holds all of the cells we have visited so far and that have neighbours which have not been visit. Use the mazePosition object to hold these cell values.

	mazePosition tempPos(xCell, yCell);									// Create a mazePosition of the cell we have chosen and place it on the stack.
	
	mazeStack.push(tempPos);

	while (!mazeStack.empty()) {										// Enter loop that will gradually carve away walls until there are no more cells that have not bee visited. This is when the stack is empty.
		int randomWall;
		mazePosition currentCell = mazeStack.top();						// Get the top value off the stack and make it current cell

		if (currentCell.x == 0) {																// If the current cell is on the left hand edge of the maze
			if (currentCell.y == 0) {															// If the current cell is in the top left hand corner
				if (!mazeArray[1].test(0) && !mazeArray[mazeWidth].test(0)) mazeStack.pop();	// If this cells neighbours to the south and east have already been visited, pop it off the stack as it is not more use.
				else {
					randomWall = (rand() % 2) + 1;												// Else select randomly one of the two neighbouring walls

					while(true) {																// Loop until a wall has been removed
						if (randomWall == 1 && mazeArray[1].test(0)) {							// Select the eastern wall if that cell has not been visited
							mazeArray[1].flip(0);												// Following code is used many times during this function so to save words I will describe it once here. First set the 0 bit on the new cell to zero to indicate it has been visited.
							mazeArray[0].set(3, 0);												// Pull down the wall between the previous cell and our new cell. In memory each wall is represented twice so have to remove the wall on both sides. If we are moving to an eastern
							mazeArray[1].set(2, 0);												// cell will have to remove the eastern wall on our current cell and the western wall of our new cell for example.
							tempPos.x = 1;														// Create a mazePosition object for our new cell
							tempPos.y = 0;
							mazeStack.push(tempPos);											// Put our new cell on top of the stack
							numberWalls -= 2;													// Reduce our wall counter by two for later
							break;																// Break out of current switch statement
						}
						else if (randomWall == 2 && mazeArray[mazeWidth].test(0)) {				// Check if southern neighbour been visited 
							mazeArray[mazeWidth].flip(0);										// If it hasn't move downward using same code as before
							mazeArray[0].set(4, 0);
							mazeArray[mazeWidth].set(1, 0);
							tempPos.x = 0;
							tempPos.y = 1;
							mazeStack.push(tempPos);
							numberWalls -= 2;
							break;
						}
						else {																	// The random wall we chose was not suitable, increment the value and try again. Or loop back to first wall if we have reached the maximum wall value.
							randomWall++;
							if (randomWall > 2) randomWall = 1;
						}
					}
				}
			}
			else if (currentCell.y == mazeHeight - 1) {											// If the current cell is in the bottom left hand corner
				if (!mazeArray[(mazeHeight - 2) * mazeWidth].test(0) && !mazeArray[((mazeHeight - 1) * mazeWidth) + 1].test(0)) mazeStack.pop();
				else {
					randomWall = (rand() % 2) + 1;

					while(true) {																	// Same method as before but in different directions
						if (randomWall == 1 && mazeArray[(mazeHeight - 2) * mazeWidth].test(0)) {	// Northern wall
							mazeArray[(mazeHeight - 2) * mazeWidth].flip(0);
							mazeArray[(mazeHeight - 1) * mazeWidth].set(1, 0);
							mazeArray[(mazeHeight - 2) * mazeWidth].set(4, 0);
							tempPos.x = 0;
							tempPos.y = mazeHeight - 2;
							mazeStack.push(tempPos);
							numberWalls -= 2;
							break;
						}
						else if (randomWall == 2 && mazeArray[((mazeHeight - 1) * mazeWidth) + 1].test(0)) {	// Eastern wall
							mazeArray[((mazeHeight - 1) * mazeWidth) + 1].flip(0);
							mazeArray[(mazeHeight - 1) * mazeWidth].set(3, 0);
							mazeArray[((mazeHeight - 1) * mazeWidth) + 1].set(2, 0);
							tempPos.x = 1;
							tempPos.y = mazeHeight - 1;
							mazeStack.push(tempPos);
							numberWalls -= 2;
							break;
						}
						else {
							randomWall++;
							if (randomWall > 2) randomWall = 1;
						}
					}
				}
			}
			else {																							// If cell is somewhere of the western edge of maze but not in a corner
				if (!mazeArray[(currentCell.y - 1) * mazeWidth].test(0) && !mazeArray[(currentCell.y * mazeWidth) + 1].test(0) && !mazeArray[(currentCell.y + 1) * mazeWidth].test(0)) mazeStack.pop();
				else {
					randomWall = (rand() % 3) + 1;															// Same procedure but possible to move in three directions this time

					while(true) {					
						if (randomWall == 1 && mazeArray[(currentCell.y - 1) * mazeWidth].test(0)) {		// Northern wall
							mazeArray[(currentCell.y - 1) * mazeWidth].flip(0);
							mazeArray[(currentCell.y) * mazeWidth].set(1, 0);
							mazeArray[(currentCell.y - 1) * mazeWidth].set(4, 0);
							tempPos.x = 0;
							tempPos.y = currentCell.y - 1;
							mazeStack.push(tempPos);
							numberWalls -= 2;
							break;
						}
						else if (randomWall == 2 && mazeArray[(currentCell.y * mazeWidth) + 1].test(0)) {	// Eastern wall
							mazeArray[(currentCell.y * mazeWidth) + 1].flip(0);
							mazeArray[currentCell.y * mazeWidth].set(3, 0);
							mazeArray[(currentCell.y * mazeWidth) + 1].set(2, 0);
							tempPos.x = 1;
							tempPos.y = currentCell.y;
							mazeStack.push(tempPos);
							numberWalls -= 2;
							break;
						}
						else if (randomWall == 3 && mazeArray[(currentCell.y + 1) * mazeWidth].test(0)) {	// Southern wall
							mazeArray[(currentCell.y + 1) * mazeWidth].flip(0);
							mazeArray[currentCell.y * mazeWidth].set(4, 0);
							mazeArray[(currentCell.y + 1) * mazeWidth].set(1, 0);
							tempPos.x = 0;
							tempPos.y = currentCell.y;
							mazeStack.push(tempPos);
							numberWalls -= 2;
							break;
						}
						else {
							randomWall++;
							if (randomWall > 3) randomWall = 1;
						}
					}
				}
			}
		}
		else if (currentCell.x == mazeWidth - 1) {																		// Check to see if cell is on eastern edge of maze
			if (currentCell.y == 0) {																					// Check to see if cell is in top right corner of maze
				if (!mazeArray[mazeWidth - 2].test(0) && !mazeArray[(2 * mazeWidth) - 1].test(0)) mazeStack.pop();
				else {
					randomWall = (rand() % 2) + 1;																		// Same procedure as before

					while(true) {					
						if (randomWall == 1 && mazeArray[mazeWidth - 2].test(0)) {				// Western wall
							mazeArray[mazeWidth - 2].flip(0);
							mazeArray[mazeWidth - 1].set(2, 0);
							mazeArray[mazeWidth - 2].set(3, 0);
							tempPos.x = mazeWidth - 2;
							tempPos.y = 0;
							mazeStack.push(tempPos);
							numberWalls -= 2;
							break;
						}
						else if (randomWall == 2 && mazeArray[(2 * mazeWidth) - 1].test(0)) {	// Southern wall
							mazeArray[(2 * mazeWidth) - 1].flip(0);
							mazeArray[mazeWidth - 1].set(4, 0);
							mazeArray[(2 * mazeWidth) - 1].set(1, 0);
							tempPos.x = mazeWidth - 1;
							tempPos.y = 1;
							mazeStack.push(tempPos);
							numberWalls -= 2;
							break;
						}
						else {
							randomWall++;
							if (randomWall > 2) randomWall = 1;
						}
					}
				}
			}
			else if (currentCell.y == mazeHeight - 1) {																// Check to see if cell in bottom right hand corner
				if (!mazeArray[(mazeHeight - 2) * mazeWidth + (mazeWidth - 1)].test(0) && !mazeArray[(mazeHeight - 1) * mazeWidth + (mazeWidth - 2)].test(0)) mazeStack.pop();
				else {
					randomWall = (rand() % 2) + 1;																	// Same procedure

					while(true) {					
						if (randomWall == 1 && mazeArray[(mazeHeight - 2) * mazeWidth + (mazeWidth - 1)].test(0)) {	// Northern wall
							mazeArray[(mazeHeight - 2) * mazeWidth + (mazeWidth - 1)].flip(0);
							mazeArray[(mazeHeight - 1) * mazeWidth + (mazeWidth - 1)].set(1, 0);
							mazeArray[(mazeHeight - 2) * mazeWidth + (mazeWidth - 1)].set(4, 0);
							tempPos.x = mazeWidth - 1;
							tempPos.y = mazeHeight - 2;
							mazeStack.push(tempPos);
							numberWalls -= 2;
							break;
						}
						else if (randomWall == 2 && mazeArray[(mazeHeight - 1) * mazeWidth + (mazeWidth - 2)].test(0)) {	//Western wall
							mazeArray[(mazeHeight - 1) * mazeWidth + (mazeWidth - 2)].flip(0);
							mazeArray[(mazeHeight - 1) * mazeWidth + (mazeWidth - 1)].set(2, 0);
							mazeArray[(mazeHeight - 1) * mazeWidth + (mazeWidth - 2)].set(3, 0);
							tempPos.x = mazeWidth - 2;
							tempPos.y = mazeHeight - 1;
							mazeStack.push(tempPos);
							numberWalls -= 2;
							break;
						}
						else {
							randomWall++;
							if (randomWall > 2) randomWall = 1;
						}
					}
				}
			}
			else {																												// Cell must be on eastern wall of maze but not in corner
				if (!mazeArray[(currentCell.y - 1) * mazeWidth + (mazeWidth - 1)].test(0) && !mazeArray[(currentCell.y * mazeWidth) + (mazeWidth - 2)].test(0) && !mazeArray[(currentCell.y + 1) * mazeWidth + (mazeWidth - 1)].test(0)) mazeStack.pop();
				else {
					randomWall = (rand() % 3) + 1;																			// Same procedure

					while(true) {					
						if (randomWall == 1 && mazeArray[(currentCell.y - 1) * mazeWidth + (mazeWidth - 1)].test(0)) {		// Northern wall
							mazeArray[(currentCell.y - 1) * mazeWidth + (mazeWidth - 1)].flip(0);
							mazeArray[(currentCell.y * mazeWidth) + (mazeWidth - 1)].set(1, 0);
							mazeArray[(currentCell.y - 1) * mazeWidth + (mazeWidth - 1)].set(4, 0);
							tempPos.x = mazeWidth - 1;
							tempPos.y = currentCell.y - 1;
							mazeStack.push(tempPos);
							numberWalls -= 2;
							break;
						}
						else if (randomWall == 2 && mazeArray[(currentCell.y * mazeWidth) + (mazeWidth - 2)].test(0)) {		// Western wall
							mazeArray[(currentCell.y * mazeWidth) + (mazeWidth - 2)].flip(0);
							mazeArray[(currentCell.y * mazeWidth) + (mazeWidth - 1)].set(2, 0);
							mazeArray[(currentCell.y * mazeWidth) + (mazeWidth - 2)].set(3, 0);
							tempPos.x = mazeWidth - 2;
							tempPos.y = currentCell.y;
							mazeStack.push(tempPos);
							numberWalls -= 2;
							break;
						}
						else if (randomWall == 3 && mazeArray[(currentCell.y + 1) * mazeWidth + (mazeWidth - 1)].test(0)) {	// Southern wall
							mazeArray[(currentCell.y + 1) * mazeWidth + (mazeWidth - 1)].flip(0);
							mazeArray[(currentCell.y * mazeWidth) + (mazeWidth - 1)].set(4, 0);
							mazeArray[(currentCell.y + 1) * mazeWidth + (mazeWidth - 1)].set(1, 0);
							tempPos.x = mazeWidth - 1;
							tempPos.y = currentCell.y + 1;
							mazeStack.push(tempPos);
							numberWalls -= 2;
							break;
						}
						else {
							randomWall++;
							if (randomWall > 3) randomWall = 1;
						}
					}
				}
			}
		}
		else if (currentCell.y == 0) {																			// Check if cell on northern edge of maze but not in corners
			if (!mazeArray[currentCell.x - 1].test(0) && !mazeArray[currentCell.x + 1].test(0) && !mazeArray[mazeWidth + currentCell.x].test(0)) mazeStack.pop();
			else {
				randomWall = (rand() % 3) + 1;																	// Same procedure

				while(true) {					
					if (randomWall == 1 && mazeArray[currentCell.x - 1].test(0)) {				// Western wall
						mazeArray[currentCell.x - 1].flip(0);
						mazeArray[currentCell.x].set(2, 0);
						mazeArray[currentCell.x - 1].set(3, 0);
						tempPos.x = currentCell.x - 1;
						tempPos.y = 0;
						mazeStack.push(tempPos);
						numberWalls -= 2;
						break;
					}
					else if (randomWall == 2 && mazeArray[mazeWidth + currentCell.x].test(0)) {	// Southern wall
						mazeArray[mazeWidth + currentCell.x].flip(0);
						mazeArray[currentCell.x].set(4, 0);
						mazeArray[mazeWidth + currentCell.x].set(1, 0);
						tempPos.x = currentCell.x;
						tempPos.y = 1;
						mazeStack.push(tempPos);
						numberWalls -= 2;
						break;
					}
					else if (randomWall == 3 && mazeArray[currentCell.x + 1].test(0)) {			// Eastern wall
						mazeArray[currentCell.x + 1].flip(0);
						mazeArray[currentCell.x].set(3, 0);
						mazeArray[currentCell.x + 1].set(2, 0);
						tempPos.x = currentCell.x + 1;
						tempPos.y = 0;
						mazeStack.push(tempPos);
						numberWalls -= 2;
						break;
					}
					else {
						randomWall++;
						if (randomWall > 3) randomWall = 1;
					}
				}
			}
		}
		else if (currentCell.y == mazeHeight - 1) {																// Check if cell on southern edge of maze but not in corners
			if (!mazeArray[(mazeHeight - 1) * mazeWidth + (currentCell.x - 1)].test(0) && !mazeArray[(mazeHeight - 2) * mazeWidth + currentCell.x].test(0) && !mazeArray[(mazeHeight - 1) * mazeWidth + (currentCell.x + 1)].test(0)) mazeStack.pop();
			else {
				randomWall = (rand() % 3) + 1;

				while(true) {					
					if (randomWall == 1 && mazeArray[(mazeHeight - 1) * mazeWidth + (currentCell.x - 1)].test(0)) {			// Western wall
						mazeArray[(mazeHeight - 1) * mazeWidth + (currentCell.x - 1)].flip(0);
						mazeArray[(mazeHeight - 1) * mazeWidth + currentCell.x].set(2, 0);
						mazeArray[(mazeHeight - 1) * mazeWidth + (currentCell.x - 1)].set(3, 0);
						tempPos.x = currentCell.x - 1;
						tempPos.y = mazeHeight - 1;
						mazeStack.push(tempPos);
						numberWalls -= 2;
						break;
					}
					else if (randomWall == 2 && mazeArray[(mazeHeight - 2) * mazeWidth + currentCell.x].test(0)) {			// Northern wall
						mazeArray[(mazeHeight - 2) * mazeWidth + currentCell.x].flip(0);
						mazeArray[(mazeHeight - 1) * mazeWidth + currentCell.x].set(1, 0);
						mazeArray[(mazeHeight - 2) * mazeWidth + currentCell.x].set(4, 0);
						tempPos.x = currentCell.x;
						tempPos.y = mazeHeight - 2;
						mazeStack.push(tempPos);
						numberWalls -= 2;
						break;
					}
					else if (randomWall == 3 && mazeArray[(mazeHeight - 1) * mazeWidth + (currentCell.x + 1)].test(0)) {	// Eastern wall
						mazeArray[(mazeHeight - 1) * mazeWidth + (currentCell.x + 1)].flip(0);
						mazeArray[(mazeHeight - 1) * mazeWidth + currentCell.x].set(3, 0);
						mazeArray[(mazeHeight - 1) * mazeWidth + (currentCell.x + 1)].set(2, 0);
						tempPos.x = currentCell.x + 1;
						tempPos.y = mazeHeight - 1;
						mazeStack.push(tempPos);
						numberWalls -= 2;
						break;
					}
					else {
						randomWall++;
						if (randomWall > 3) randomWall = 1;
					}
				}
			}
		}
		else {														// A random cell in the maze but not on an edge or in a corner
			if (!mazeArray[(currentCell.y - 1) * mazeWidth + currentCell.x].test(0) && !mazeArray[(currentCell.y * mazeWidth) + (currentCell.x - 1)].test(0) && !mazeArray[(currentCell.y * mazeWidth) + (currentCell.x + 1)].test(0) && !mazeArray[(currentCell.y + 1) * mazeWidth + (currentCell.x)].test(0)) mazeStack.pop();
			else {
				randomWall = (rand() % 4) + 1;

				while(true) {					
					if (randomWall == 1 && mazeArray[(currentCell.y - 1) * mazeWidth + currentCell.x].test(0)) {			// Northern wall
						mazeArray[(currentCell.y - 1) * mazeWidth + currentCell.x].flip(0);
						mazeArray[(currentCell.y * mazeWidth) + currentCell.x].set(1, 0);
						mazeArray[(currentCell.y - 1) * mazeWidth + currentCell.x].set(4, 0);
						tempPos.x = currentCell.x;
						tempPos.y = currentCell.y - 1;
						mazeStack.push(tempPos);
						numberWalls -= 2;
						break;
					}
					else if (randomWall == 2 && mazeArray[(currentCell.y * mazeWidth) + (currentCell.x - 1)].test(0)) {		// Western wall
						mazeArray[(currentCell.y * mazeWidth) + (currentCell.x - 1)].flip(0);
						mazeArray[(currentCell.y * mazeWidth) + (currentCell.x)].set(2, 0);
						mazeArray[(currentCell.y * mazeWidth) + (currentCell.x - 1)].set(3, 0);
						tempPos.x = currentCell.x - 1;
						tempPos.y = currentCell.y;
						mazeStack.push(tempPos);
						numberWalls -= 2;
						break;
					}
					else if (randomWall == 3 && mazeArray[(currentCell.y * mazeWidth) + (currentCell.x + 1)].test(0)) {		// Eastern wall
						mazeArray[(currentCell.y * mazeWidth) + (currentCell.x + 1)].flip(0);
						mazeArray[(currentCell.y * mazeWidth) + (currentCell.x)].set(3, 0);
						mazeArray[(currentCell.y * mazeWidth) + (currentCell.x + 1)].set(2, 0);
						tempPos.x = currentCell.x + 1;
						tempPos.y = currentCell.y;
						mazeStack.push(tempPos);
						numberWalls -= 2;
						break;
					}
					else if (randomWall == 4 && mazeArray[(currentCell.y + 1) * mazeWidth + (currentCell.x)].test(0)) {		// Southern wall
						mazeArray[(currentCell.y + 1) * mazeWidth + (currentCell.x)].flip(0);
						mazeArray[(currentCell.y) * mazeWidth + (currentCell.x)].set(4, 0);
						mazeArray[(currentCell.y + 1) * mazeWidth + (currentCell.x)].set(1, 0);
						tempPos.x = currentCell.x;
						tempPos.y = currentCell.y + 1;
						mazeStack.push(tempPos);
						numberWalls -= 2;
						break;
					}
					else {
						randomWall++;
						if (randomWall > 4) randomWall = 1;
					}
				}
			}
		}
	}
	groundTerrain.LoadTerrainData(mazeWidth, mazeHeight);		// Create the floor of the maze using the modified terrain object
	createWalls();												// Convert maze representation into a renderable mesh
}

void maze::createWalls() {
	//Code taken from the modified terrain class LoadTerrainData function. See that function for a more detailed explanation of the workings
	
	// Get the address that we can call to later.
	mazeWallPointer = VIFStaticDMA.GetPointer();

	VIFStaticDMA.Add32(FLUSH);			// Make sure VU1 isn't busy
	VIFStaticDMA.Add32(STCYCL(1,1));	// Unpack linearly, i.e. don't skip any spaces
	VIFStaticDMA.Add32(BASE(32));		// The double buffers start at VU1 address 16 (giving us 16 QW to store data that won't change)
	VIFStaticDMA.Add32(OFFSET(496));	// The size of each buffer.

	VIFStaticDMA.AddUnpack(V4_32, 0, 1);	// Unpack 8QW of data that won't change
	VIFStaticDMA.AddVector(Pipeline.GetScaleVector());

	// The verts are 3QW each, and the 504QW is split in half. Therefore we have 252QW for each buffer.
	// Each buffer also has 2QW of info (GIFTag + Numverts), so we can process 83 vertices (249QW)
	// in each buffer. Each wall is 6 vertices so this means a buffer can hold 13 walls	.
	
	int numberWallsPerChunk = 13, xCell = 0, yCell = 0, checkWall = 1; 
	
	const float topCornerPosX = -(tileSize * mazeWidth) / 2;
	const float topCornerPosY = -(tileSize * mazeHeight) / 2;
	
	bool bFirst = true;
	
	// This is where we need the numberWalls variable we have been maintaining throughout the maze creation process.
	while(numberWalls > 0)
	{
		int numberWallsThisChunk;

		if(numberWalls > numberWallsPerChunk)
		{
			numberWallsThisChunk = numberWallsPerChunk;
			numberWalls -= numberWallsPerChunk;
		}
		else
		{
			numberWallsThisChunk = numberWalls;
			numberWalls -= numberWallsThisChunk;
		}

		VIFStaticDMA.AddUnpack(V4_32, 0, ((numberWallsThisChunk * 18) + 2), 1);
		VIFStaticDMA.Add128((numberWallsThisChunk * 18));
	
		VIFStaticDMA.Add128(
						GS_GIFTAG_BATCH(numberWallsThisChunk * 6, // NLOOP
								1,	// EOP
								1,	// PRE
								GS_PRIM(GS_TRIANGLE,  1,   1,   0 , 0,   0,   0,    0,   0),	// PRIM
								GIF_FLG_PACKED,
								GS_BATCH_3(GIF_REG_ST, GIF_REG_RGBAQ, GIF_REG_XYZ2)));
		
		// Code loops through each cell and checks to see what walls it is surrounded by. If it has a particular wall then 6 vertices are added into static memory in the correct position, with correct normals and correct texture coordinates to represent that wall. A counter makes sure we only add enough walls to fill the buffer.
		// When buffer is full we add a new buffer and keep adding walls. This is repeated until we have no more walls.
		for(int iWall = 0; iWall < numberWallsThisChunk;) {
			switch (checkWall) {
				case 1:
					if (mazeArray[(yCell * mazeWidth) + xCell].test(1)) {		// If there is a northern wall add the required vertices
						VIFStaticDMA.AddVector(Vector4(0, 1, 1, 0));																						// Tex coords + in W, a flag to set ADC or not.
						VIFStaticDMA.AddVector(Vector4(0, 0, 1, 0));																						// Normal
						VIFStaticDMA.AddVector(Vector4((topCornerPosX + (tileSize * xCell)), 0, (topCornerPosY + 0.1f + (tileSize * yCell)), 1));			// Position
						
						VIFStaticDMA.AddVector(Vector4(0, 0, 1, 0));																						// Tex coords + in W, a flag to set ADC or not.
						VIFStaticDMA.AddVector(Vector4(0, 0, 1, 0));																						// Normal	
						VIFStaticDMA.AddVector(Vector4((topCornerPosX + (tileSize * xCell)), wallHeight, (topCornerPosY + 0.1f + (tileSize * yCell)), 1));	// Position
						
						VIFStaticDMA.AddVector(Vector4(1, 0, 1, 0));																								// Tex coords + in W, a flag to set ADC or not.
						VIFStaticDMA.AddVector(Vector4(0, 0, 1, 0));																								// Normal
						VIFStaticDMA.AddVector(Vector4((topCornerPosX + (tileSize * (xCell + 1))), wallHeight, (topCornerPosY + 0.1f + (tileSize * yCell)), 1));	// Position
						
						VIFStaticDMA.AddVector(Vector4(0, 1, 1, 0));																						// Tex coords + in W, a flag to set ADC or not.
						VIFStaticDMA.AddVector(Vector4(0, 0, 1, 0));																						// Normal
						VIFStaticDMA.AddVector(Vector4((topCornerPosX + (tileSize * xCell)), 0, (topCornerPosY + 0.1f + (tileSize * yCell)), 1));			// Position
						
						VIFStaticDMA.AddVector(Vector4(1, 0, 1, 0));																								// Tex coords + in W, a flag to set ADC or not.
						VIFStaticDMA.AddVector(Vector4(0, 0, 1, 0));																								// Normal
						VIFStaticDMA.AddVector(Vector4((topCornerPosX + (tileSize * (xCell + 1))), wallHeight, (topCornerPosY + 0.1f + (tileSize * yCell)), 1));	// Position
						
						VIFStaticDMA.AddVector(Vector4(1, 1, 1, 0));																						// Tex coords + in W, a flag to set ADC or not.
						VIFStaticDMA.AddVector(Vector4(0, 0, 1, 0));																						// Normal
						VIFStaticDMA.AddVector(Vector4((topCornerPosX + (tileSize * (xCell + 1))), 0, (topCornerPosY + 0.1f + (tileSize * yCell)), 1));		// Position
						
						iWall++;		// Update the walls in buffer count
					}
					checkWall++;		// Increment the counter of which wall we a checking so next wall will be checked on next loop
					break;
				case 2:
					if (mazeArray[(yCell * mazeWidth) + xCell].test(2)) {			// If there is a western wall add the required vertices
						VIFStaticDMA.AddVector(Vector4(0, 1, 1, 0));																						// Tex coords + in W, a flag to set ADC or not.
						VIFStaticDMA.AddVector(Vector4(1, 0, 0, 0));																						// Normal
						VIFStaticDMA.AddVector(Vector4((topCornerPosX + 0.1f + (tileSize * xCell)), 0, (topCornerPosY + (tileSize * (yCell + 1))), 1));		// Position
						
						VIFStaticDMA.AddVector(Vector4(0, 0, 1, 0));																								// Tex coords + in W, a flag to set ADC or not.
						VIFStaticDMA.AddVector(Vector4(1, 0, 0, 0));																								// Normal
						VIFStaticDMA.AddVector(Vector4((topCornerPosX + 0.1f + (tileSize * xCell)), wallHeight, (topCornerPosY + (tileSize * (yCell + 1))), 1));	// Position
						
						VIFStaticDMA.AddVector(Vector4(1, 0, 1, 0));																						// Tex coords + in W, a flag to set ADC or not.
						VIFStaticDMA.AddVector(Vector4(1, 0, 0, 0));																						// Normal
						VIFStaticDMA.AddVector(Vector4((topCornerPosX + 0.1f + (tileSize * xCell)), wallHeight, (topCornerPosY + (tileSize * yCell)), 1));	// Position
						
						VIFStaticDMA.AddVector(Vector4(0, 1, 1, 0));																						// Tex coords + in W, a flag to set ADC or not.
						VIFStaticDMA.AddVector(Vector4(1, 0, 0, 0));																						// Normal
						VIFStaticDMA.AddVector(Vector4((topCornerPosX + 0.1f + (tileSize * xCell)), 0, (topCornerPosY + (tileSize * (yCell + 1))), 1));		// Position
						
						VIFStaticDMA.AddVector(Vector4(1, 0, 1, 0));																						// Tex coords + in W, a flag to set ADC or not.
						VIFStaticDMA.AddVector(Vector4(1, 0, 0, 0));																						// Normal
						VIFStaticDMA.AddVector(Vector4((topCornerPosX + 0.1f + (tileSize * xCell)), wallHeight, (topCornerPosY + (tileSize * yCell)), 1));	// Position
						
						VIFStaticDMA.AddVector(Vector4(1, 1, 1, 0));																						// Tex coords + in W, a flag to set ADC or not.
						VIFStaticDMA.AddVector(Vector4(1, 0, 0, 0));																						// Normal
						VIFStaticDMA.AddVector(Vector4((topCornerPosX + 0.1f + (tileSize * xCell)), 0, (topCornerPosY + (tileSize * yCell)), 1));			// Position
						
						iWall++;		// Update the walls in buffer count
					}
					checkWall++;		// Increment the counter of which wall we a checking so next wall will be checked on next loop
					break;
				case 3:
					if (mazeArray[(yCell * mazeWidth) + xCell].test(3)) {			// If there is a eastern wall add the required vertices
						VIFStaticDMA.AddVector(Vector4(0, 1, 1, 0));																						// Tex coords + in W, a flag to set ADC or not.
						VIFStaticDMA.AddVector(Vector4(-1, 0, 0, 0));																						// Normal
						VIFStaticDMA.AddVector(Vector4((topCornerPosX - 0.1f + (tileSize * (xCell + 1))), 0, (topCornerPosY + (tileSize * yCell)), 1));		// Position
						
						VIFStaticDMA.AddVector(Vector4(0, 0, 1, 0));																								// Tex coords + in W, a flag to set ADC or not.
						VIFStaticDMA.AddVector(Vector4(-1, 0, 0, 0));																								// Normal
						VIFStaticDMA.AddVector(Vector4((topCornerPosX - 0.1f + (tileSize * (xCell + 1))), wallHeight, (topCornerPosY + (tileSize * yCell)), 1));	// Position
						
						VIFStaticDMA.AddVector(Vector4(1, 0, 1, 0));																									// Tex coords + in W, a flag to set ADC or not.
						VIFStaticDMA.AddVector(Vector4(-1, 0, 0, 0));																									// Normal
						VIFStaticDMA.AddVector(Vector4((topCornerPosX - 0.1f + (tileSize * (xCell + 1))), wallHeight, (topCornerPosY + (tileSize * (yCell + 1))), 1));	// Position
						
						VIFStaticDMA.AddVector(Vector4(0, 1, 1, 0));																						// Tex coords + in W, a flag to set ADC or not.
						VIFStaticDMA.AddVector(Vector4(-1, 0, 0, 0));																						// Normal
						VIFStaticDMA.AddVector(Vector4((topCornerPosX - 0.1f + (tileSize * (xCell + 1))), 0, (topCornerPosY + (tileSize * yCell)), 1));		// Position
						
						VIFStaticDMA.AddVector(Vector4(1, 0, 1, 0));																									// Tex coords + in W, a flag to set ADC or not.
						VIFStaticDMA.AddVector(Vector4(-1, 0, 0, 0));																									// Normal
						VIFStaticDMA.AddVector(Vector4((topCornerPosX - 0.1f + (tileSize * (xCell + 1))), wallHeight, (topCornerPosY + (tileSize * (yCell + 1))), 1));	// Position
						
						VIFStaticDMA.AddVector(Vector4(1, 1, 1, 0));																							// Tex coords + in W, a flag to set ADC or not.
						VIFStaticDMA.AddVector(Vector4(-1, 0, 0, 0));																							// Normal
						VIFStaticDMA.AddVector(Vector4((topCornerPosX - 0.1f + (tileSize * (xCell + 1))), 0, (topCornerPosY + (tileSize * (yCell + 1))), 1));	// Position
						
						iWall++;		// Update the walls in buffer count
					}
					checkWall++;		// Increment the counter of which wall we a checking so next wall will be checked on next loop
					break;
				case 4:
					if (mazeArray[(yCell * mazeWidth) + xCell].test(4)) {			// If there is a southern wall add the required vertices
						VIFStaticDMA.AddVector(Vector4(0, 1, 1, 0));																							// Tex coords + in W, a flag to set ADC or not.
						VIFStaticDMA.AddVector(Vector4(0, 0, -1, 0));																							// Normal
						VIFStaticDMA.AddVector(Vector4((topCornerPosX + (tileSize * (xCell + 1))), 0, (topCornerPosY - 0.1f + (tileSize * (yCell + 1))), 1));	// Position
						
						VIFStaticDMA.AddVector(Vector4(0, 0, 1, 0));																									// Tex coords + in W, a flag to set ADC or not.
						VIFStaticDMA.AddVector(Vector4(0, 0, -1, 0));																									// Normal
						VIFStaticDMA.AddVector(Vector4((topCornerPosX + (tileSize * (xCell + 1))), wallHeight, (topCornerPosY - 0.1f + (tileSize * (yCell + 1))), 1));	// Position
						
						VIFStaticDMA.AddVector(Vector4(1, 0, 1, 0));																								// Tex coords + in W, a flag to set ADC or not.
						VIFStaticDMA.AddVector(Vector4(0, 0, -1, 0));																								// Normal
						VIFStaticDMA.AddVector(Vector4((topCornerPosX + (tileSize * xCell)), wallHeight, (topCornerPosY - 0.1f + (tileSize * (yCell + 1))), 1));	// Position
						
						VIFStaticDMA.AddVector(Vector4(0, 1, 1, 0));																								// Tex coords + in W, a flag to set ADC or not.
						VIFStaticDMA.AddVector(Vector4(0, 0, -1, 0));																								// Normal
						VIFStaticDMA.AddVector(Vector4((topCornerPosX + (tileSize * (xCell + 1))), 0, (topCornerPosY - 0.1f + (tileSize * (yCell + 1))), 1));		// Position
						
						VIFStaticDMA.AddVector(Vector4(1, 0, 1, 0));																								// Tex coords + in W, a flag to set ADC or not.
						VIFStaticDMA.AddVector(Vector4(0, 0, -1, 0));																								// Normal
						VIFStaticDMA.AddVector(Vector4((topCornerPosX + (tileSize * xCell)), wallHeight, (topCornerPosY - 0.1f + (tileSize * (yCell + 1))), 1));	// Position
						
						VIFStaticDMA.AddVector(Vector4(1, 1, 1, 0));																						// Tex coords + in W, a flag to set ADC or not.
						VIFStaticDMA.AddVector(Vector4(0, 0, -1, 0));																						// Normal
						VIFStaticDMA.AddVector(Vector4((topCornerPosX + (tileSize * xCell)), 0, (topCornerPosY - 0.1f + (tileSize * (yCell + 1))), 1));		// Position
						
						iWall++;		// Update the walls in buffer count
					}
					if (xCell == (mazeWidth - 1)) {		// When we have check all four walls of a cell we move onto the next. If we have reached the end of row we move to the next by incrementing yCell and setting xCell so we start at the beginning of said row
						xCell = 0;
						yCell++;
					}
					else xCell++;						// If we are not at the end of a row we just move to the next cell by incrementing xCell.
					checkWall = 1;
					break;
			}
		}
		if(bFirst)
		{
			bFirst = false;
			// If this is the first buffer then run the VU code from address 0 so that the initialisation
			// VU code is ran.
			VIFStaticDMA.Add32(MSCALL(0));
		}
		else
		{
			// For multiple times MSCNT means to continue where the VU code finished last time at the --cont.
			VIFStaticDMA.Add32(MSCNT);
		}

		// Notice that due to the quad buffer setup we don't need to flush here because we can upload, process, and render
		// all in parallel now. (the XGKick in the vector code will flush to make sure that we don't get ahead of ourselves)
	}

	VIFStaticDMA.Add32(FLUSH);
	VIFStaticDMA.DMARet();
}

void maze::render(const Matrix4x4 & matWorld) {			// Called when we want to render the maze. Although we pass the World matrix as a parameter this value is usually the identity matrix as we want the maze to remain in a fixed position as it is the environment
	renderFloor(matWorld);								// Render the floor
	renderWalls();										// Render the walls
}

void maze::renderFloor(const Matrix4x4 & matWorld) {
	groundTex.Upload(TEXBUF480);						// Upload the floor texture to texture buffer
	groundTex.Select();									// Select this texture
	
	groundTerrain.SetWorldMatrix(matWorld);				// Set the world matrix
	groundTerrain.Render();								// Call the bject render function
}

void maze::renderWalls() {
	wallTex.Upload(TEXBUF480);							// Upload and select the wall texture
	wallTex.Select();
	
	VIFDynamicDMA.Add32(FLUSH);							// Make sure VU1 is not busy
	
	// Upload the matrices in the dynamic buffer
	// because they can change every frame.
	VIFDynamicDMA.AddUnpack(V4_32, 1, 16);
	VIFDynamicDMA.AddMatrix(Pipeline.GetLightDirs());
	VIFDynamicDMA.AddMatrix(Pipeline.GetLightCols());
	VIFDynamicDMA.AddMatrix(Pipeline.GetViewProjection());
	VIFDynamicDMA.AddMatrix(Matrix4x4::IDENTITY);
	
	// Call the packet with the static data of the maze wall mesh that doesn't change per frame.
	VIFDynamicDMA.DMACall(mazeWallPointer);
}
