Maze.java

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Random;


/**
 * This class is responsible for everything to do with mazes generated by the program. It stores all relevant information about itself but interactions with it are handled by other classes.
 *
 */
/**
 * @author Thomas
 *
 */
/**
 * @author Thomas
 *
 */
/**
 * @author Thomas
 *
 */
public class Maze {
	//class constants
		//Tile status definitions
			private static final int EMPTY = 0;
			private static final int FLOOR = 1;
			private static final int WALL  = 2;
			private static final int START = 3;
			private static final int EXIT  = 4;
			private static final int SENTRY  = 5;
			private static final int KEY = 6;
	
		// Maze generator constants
			private static final float CYCLECHANCE = (float) 0.75; //determines the chance cycles are allowed to possibly exist. The lower this number is the less cycles should be (probabilistically speaking) in the maze
			private static final int SENTRYSPACE = 3; // Space in between Sentries so they don't clump too close together and make impossible puzzles
		// Maze generator pseudo-constants -- these are constant after the class has been initialized.
			private  int DIFFICULTY = 15; //these are constant once the game starts-- they are changed in settings.java
			private  int NUMSEN = 3;//number of sentries 
			
	//class variables
		private Tile[][] maze;
		private ArrayList<Sentry> sentries;
		private boolean keyStatus,exitStatus;
		private int size;
		private Tile exit; //holds the exit tile while the key has yet to be found

	/**
	 * Constructor for the maze. Actually generates multiple mazes until it finds one that it thinks is good enough.
	 * 
	 * @param size Maze size
	 */
	public Maze(int size, int numSen, int diff){
		
		this.size = size;
		this.maze = new Tile[size][size];
		this.sentries = new ArrayList<Sentry>();
		NUMSEN = numSen;
		DIFFICULTY = diff;//this sets how hard the maze is -- a better explanation is found in goodMaze()
		
		//I SWEAR THIS IS THE ONE TIME DO...WHILE IS ACTAULLY WORTH 
		//Make a maze using generate maze, but if it's not good enough just try again until it is.
		do { // Initialize maze grid
			for (int n = 0; n < size; n++){
				for (int m = 0; m < size; m++){
					this.maze[n][m] = new Tile(n,m);
				}
			}
			generateMaze(size);
		} while (!goodMaze()); // Check if maze is good

		addSentries(NUMSEN);
		addKey(maze, size); 
		keyStatus = false;
		exitStatus = false;
		findSprites();
		exit = getTileType(EXIT);
		getTileType(EXIT).setType(FLOOR);
	}
	
	//this method figures out which sprite should be displayed for each tile
	//the sprites themselves are in a type BufferedImage [][] in Renderer
	//but the logic should be done in maze.java while the images stored 
	//in renderer because I don't want to store images outside of 
	//renderer. It also saves space
	/**
	 * Calculates which sprite should be displayed for each tile on the maze depending on what type of tile it is and also what type of tile its neighbors are
	 */
	private void findSprites() {
		
		Random x = new Random();
		int vert, avert, ahorz, horz = 0;//these are just to help me out with logic
		int triggers = 0;//has two uses -- explained below
		for (int n = 0; n < size; n++){
			for (int m = 0; m < size; m++){
				vert = horz = avert = ahorz = 0;
				triggers = 0;
				if (maze[n][m].getType() == FLOOR || maze[n][m].getType() == START || maze[n][m].getType() == EXIT ){//sets sprites for walkable areas
					maze[n][m].setImgRow(5);
					maze[n][m].setImgCol(x.nextInt(3));
				}else if (maze[n][m].getType() == WALL ){//sets sprites for walls
					//looks up, down, left and right to find walls and picks the appropriate wall sprite
					if(getN(maze[n][m]) == null ||(getN(maze[n][m]) != null && getN(maze[n][m]).getType() != WALL)){
						vert++;
						avert++;
						triggers++;//triggers here is the number of adjacent walls to the current tile
					}
					if(getS(maze[n][m]) == null ||(getS(maze[n][m]) != null && getS(maze[n][m]).getType() != WALL)){
						vert--;
						avert++;
						triggers++;
					}
					if(getE(maze[n][m]) == null ||(getE(maze[n][m]) != null && getE(maze[n][m]).getType() != WALL)){
						horz++;
						ahorz++;
						triggers++;
					}
					if(getW(maze[n][m]) == null ||(getW(maze[n][m]) != null && getW(maze[n][m]).getType() != WALL)){
						horz--;
						ahorz++;
						triggers++;
					}
					maze[n][m].setImgRow(triggers % 4);//just because when triggers = 4 I want imgrow = 0
					
					switch (triggers){
					case 0: maze[n][m].setImgCol(0);
							break;
					case 1: maze[n][m].setImgCol(2*horz + vert + 2);//so these are +-1 for up/down and left/right						
							break;
					case 2: maze[n][m].setImgCol(2*horz + vert + avert - ahorz + 3);//so these are +1 for up&down and left&right
							break;		
					case 3: maze[n][m].setImgCol(2*horz + vert + 2);
							break;
					case 4: maze[n][m].setImgCol(1);
							break;
					}
				}else if (maze[n][m].getType() == EMPTY){//we have special logic for empty tiles so it's not just walls! yay for visual candy
					if(getNW(maze[n][m]) == null || getNW(maze[n][m]) != null && (getNW(maze[n][m]).getType() != WALL && getNW(maze[n][m]).getType() != SENTRY && getNW(maze[n][m]).getType() != EMPTY)){
						triggers++;
					}if(getNE(maze[n][m]) == null ||getNE(maze[n][m]) != null && (getNE(maze[n][m]).getType() != WALL && getNE(maze[n][m]).getType() != SENTRY && getNE(maze[n][m]).getType() != EMPTY)){
						triggers++;
					}if(getSW(maze[n][m]) == null ||getSW(maze[n][m]) != null && (getSW(maze[n][m]).getType() != WALL && getSW(maze[n][m]).getType() != SENTRY && getSW(maze[n][m]).getType() != EMPTY)){
						triggers++;
					}if(getSE(maze[n][m]) == null ||getSE(maze[n][m]) != null && (getSE(maze[n][m]).getType() != WALL && getSE(maze[n][m]).getType() != SENTRY && getSE(maze[n][m]).getType() != EMPTY)){
						triggers++;
					}
					maze[n][m].setImgRow(4);
					maze[n][m].setImgCol((triggers)%4);	
				}else if (maze[n][m].getType() == KEY){//it's actaully not a key
					maze[n][m].setImgRow(0);
					maze[n][m].setImgCol(2);	
				}else if (maze[n][m].getType() == SENTRY){//this is the only sprite that I drew from scratch and it looks horrible lol
					maze[n][m].setImgRow(0);
					maze[n][m].setImgCol(5);	
				}
			}
		}
		
	}

	/**
	 * Sets the exit tile (and performs related sprite operations) when the key is collected.
	 */
	public void keyOff(){
		Tile temp = getTile(exit.getCol(), exit.getRow());
		temp.setType(EXIT);
		temp.setImgRow(0);
		temp.setImgCol(3);
		temp = getTileType(KEY);
		temp.setType(FLOOR);
		temp.setImgRow(5);
		temp.setImgCol(3);
		keyStatus = true;
	}
	
	/**
	 * Called when the player makes it to the end tile. 
	 * Displays the key on the pedestal.
	 */
	public void activateShrine(){
		exit.setImgRow(0);
		exit.setImgCol(4);
		exitStatus = true;
	}
	
	/**
	 * Set exit status.
	 * 
	 * @param exitStatus boolean
	 */
	public void setExitStatus(boolean exitStatus) {
		this.exitStatus = exitStatus;
	}

	/**
	 * Gets the exit status.
	 * 
	 * @return exit status as boolean
	 */
	public boolean isExitStatus() {
		return exitStatus;
	}

	/**
	 * Sets the keyStatus
	 * @param keyStatus whether or not the key has been taken
	 */
	public void setKeyStatus(boolean keyStatus) {
		this.keyStatus = keyStatus;
	}

	/**
	 * Adds instances of the Sentry class to a maze. Sentries cannot be less than SENTRYSPACE tiles close to each other or the start and exit tiles.
	 * 
	 * @param num is the number of sentries to create
	 */
	private void addSentries(int num) {
		
		Random x = new Random();
		Random y = new Random();
		int r = 0;
		int c = 0;
		ArrayList<Tile> avoid = new ArrayList<Tile>();
		boolean tooClose = false;
		
		while (num > 0) {
			r = x.nextInt(size);
			c = y.nextInt(size);
			tooClose = false;
		
			for (Sentry sentry: this.sentries ){
				avoid.add(getTile(sentry.getColumn(),sentry.getRow()));
			}
			
			avoid.add(getTileType(EXIT));
			avoid.add(getTileType(START));
			
			for (Tile tile: avoid){
				if(Math.sqrt(Math.pow(tile.getRow()-r,2) + Math.pow(tile.getCol()-c,2)) < SENTRYSPACE){
					tooClose = true;
				}
			}
			
			if (this.getTile(c, r).getType() == WALL && tooClose == false) {
				Sentry s = new Sentry(c, r);
				this.sentries.add(s);
				num--;
			}
		}
	}
	
	/**
	 * Function to add the key to the maze
	 * 
	 * @param maze is this maze
	 * @param size is the size of this maze
	 */
	private void addKey(Tile[][] maze, int size) {
		int row = size;
		int col = 0;
		do {
			Random x = new Random();
			Random y = new Random();
			row = x.nextInt(size);
			col = y.nextInt(size);
			if(maze[row][col].getType() == FLOOR && isCorner(maze[row][col])) { // if the tile is a floor and a corner, add a key to it
				maze[row][col].setType(KEY);
			}
		}while(maze[row][col].getType() != KEY); // continue the loop if the tile is not a floor or a corner
	}
	
	/**
	 * Function to check if a tile is a corner (one pathway only) - Andy
	 * 
	 * @param tile is the square/tile to check
	 * @return true if the checking square/tile is a corner
	 *         false if it is not
	 */
	private boolean isCorner(Tile tile) {
		int count = 0;
		if (getN(tile) != null && getN(tile).getType() == FLOOR) {// need to include null check because getN returns null if you check outside the maze -- tom
			count++;
		}
		if (getS(tile) != null && getS(tile).getType() == FLOOR) {
			count++;
		}
		if (getE(tile) != null && getE(tile).getType() == FLOOR) {
			count++;
		}
		if (getW(tile) != null && getW(tile).getType() == FLOOR) {
			count++;
		}
		if (count == 1) {
			return true;
		}
		return false;
	}
	
	/**
	 * Rotates sentries in the Maze.
	 */
	public void updateMaze(){
		for (Sentry sentry : this.sentries){
			sentry.updateDegree();
		}
	}

	/**
	 * Get a list of the sentries in the maze.
	 * 
	 * @return ArrayList of Sentries
	 */
	public ArrayList<Sentry> getSentries() {
		return this.sentries;
	}

	
	/**
	 * Maze generation function using pseudo BFS (random walk algorithm?) on Tile grid.
	 * 
	 * @param size Maze size
	 */
	private void generateMaze(int size) { // generates maze using random walk (at least that's what I think I'm doing)

		Random rand = new Random();
		
		Tile start = new Tile(rand.nextInt(size),rand.nextInt(size)); // Choose starting Tile at random
		start.setType(START);
		
		this.maze[start.getCol()][start.getRow()] = start;
		
		LinkedList<Tile> ends = new LinkedList<Tile>(); // Queue of Tiles representing paths that have not been closed as a List 
		LinkedList<Tile> choices = new LinkedList<Tile>(); // Holds the Tiles that can be traveled to from the current Tile
		
		int branches = 0;
		int temp = 0;
		
		Tile cur = null;
		Tile process = null;
		
		ends.add(start); // Add starting Tile to ends Queue
		
		while (!ends.isEmpty()){ // While there are still open paths
			
			cur = ends.remove(); // Take an open path from the Queue
			
			if (this.getN(cur)!= null){ // Add adjacent undiscovered Tiles to the choices list
				if(this.getN(cur).getType() == EMPTY) choices.add(getN(cur));
			}
			
			if (this.getS(cur)!= null){
				if(this.getS(cur).getType() == EMPTY) choices.add(getS(cur));
			}
			
			if (this.getE(cur)!= null){
				if(this.getE(cur).getType() == EMPTY) choices.add(getE(cur));
			}
			
			if (this.getW(cur)!= null){
				if(this.getW(cur).getType() == EMPTY) choices.add(getW(cur));
			}

			if (!choices.isEmpty()){		
				
				// Choose a number from 0 to the number of choices, skewed towards 0 by taking the uniform distribution to the power of 1.5
				branches = (int)Math.round(Math.sqrt(rand.nextFloat()*rand.nextFloat()*rand.nextFloat()))*(choices.size()-1);
				
				// Branches is the number of possible options that WILL be explored (not all available options may be explored)
				while (branches >= 0 && !choices.isEmpty()){ // For each remaining branch
					
					if (choices.size() == 1){ // Pick one of the choices randomly
						temp = 0;
					} else {
						temp = Math.round(rand.nextFloat())*(choices.size()-1);
					}
					 
					process = choices.remove(temp); // Take it off the choices list
					
					// Regulate the number of cycles by randomly checking the status of each direction from the current Tile
					if (rand.nextFloat() > CYCLECHANCE && getN(process)!= null && getN(process) != cur && getN(process).getType() == FLOOR){
						process.setType(WALL);
					} else if (rand.nextFloat() > CYCLECHANCE && getS(process)!= null && getS(process) != cur && getS(process).getType() == FLOOR){
						process.setType(WALL);
					} else if (rand.nextFloat() > CYCLECHANCE && getW(process)!= null && getW(process) != cur && getW(process).getType() == FLOOR){
						process.setType(WALL);
					} else if (rand.nextFloat() > CYCLECHANCE && getE(process)!= null && getE(process) != cur && getE(process).getType() == FLOOR){
						process.setType(WALL);
					} else {
						process.setType(FLOOR); // Set Tile to FLOOR if cycle test is passed or ignored
						ends.add(process); // Add Tile to the list of unfinished paths
					}

					branches--; // reduces the number of branches 
				}
				
				while (choices.size() > 0){ // Set remaining choices as wall after all the branches have been accounted
					process = choices.remove();
					process.setType(WALL);
				}
				
				// These finish off diagonal walling logic for 2,3 or 4 way forks.
				if (getN(cur) != null && getN(cur).getType() == FLOOR){ 
					if (getW(cur) != null &&getW(cur).getType() == FLOOR && getNW(cur).getType()!=FLOOR){
						getNW(cur).setType(WALL);//needed because these are essentially corners
					}
					
					if (getE(cur) != null &&getE(cur).getType() == FLOOR && getNE(cur).getType()!=FLOOR){
						getNE(cur).setType(WALL);
					}
				}
				
				if (getS(cur) != null && getS(cur).getType() == FLOOR){
					if (getW(cur) != null &&getW(cur).getType() == FLOOR && getSW(cur).getType()!=FLOOR){
						getSW(cur).setType(WALL);
					}
					
					if (getE(cur) != null &&getE(cur).getType() == FLOOR && getSE(cur).getType()!=FLOOR){
						getSE(cur).setType(WALL);
					}
				}
			}
		}

		cur.setType(EXIT); // Select the last visited node as the exit Tile
	}

	/**
	 * Check the number of unreachable Tiles in the maze. If there are too many, the maze is deemed too easy and thrown away
	 * 
	 * @return Boolean result
	 */
	private boolean goodMaze(){
		
		int count = 0;
		
		for (int n = 0;n < size;n++){
			for (int m = 0;m < size;m++){
				if (maze[n][m].getType() == EMPTY){
					count++;
				}
			}
		}
		//so the more unreachable tiles there are in the maze, the more likely that they're in larger clumps. Even if they aren't, they create large zones of walls, which make the maze easier to traverse while still looking organic
		if (count > DIFFICULTY){
			return false;
		} else {
			return true;
		}
	}
	
	/**
	 * Get relative Tile above some current Tile.
	 * NOTE: WILL RETURN NULL IF YOU ACCESS A TILE OUTSIDE THE ARRAY
	 * 
	 * @param tile Current Tile
	 * @return Tile above current Tile 
	 */
	public Tile getN(Tile tile){
		if(tile == null) return null;
		if (tile.getRow() > 0){
			return maze[tile.getCol()][tile.getRow()-1];
		} else {
			return null;
		}
	}
	
	/**
	 * Get relative Tile below some current Tile.
	 * NOTE: WILL RETURN NULL IF YOU ACCESS A TILE OUTSIDE THE ARRAY
	 * 
	 * @param tile Current Tile
	 * @return Tile below current Tile
	 */
	public Tile getS(Tile tile){
		if(tile == null) return null;
		if (tile.getRow() < size-1){
			return maze[tile.getCol()][tile.getRow()+1];
		} else {
			return null;
		}
	}
	
	/**
	 * Get relative Tile to the right of some current Tile.
	 * NOTE: WILL RETURN NULL IF YOU ACCESS A TILE OUTSIDE THE ARRAY
	 * 
	 * @param tile Current Tile
	 * @return Tile to the right of current Tile
	 */
	public Tile getE(Tile tile){
		if(tile == null) return null;
		if (tile.getCol() < size-1){
			return maze[tile.getCol()+1][tile.getRow()];
		} else {
			return null;
		}
	}
	
	/**
	 * Get relative Tile to the left some current Tile.
	 * NOTE: WILL RETURN NULL IF YOU ACCESS A TILE OUTSIDE THE ARRAY
	 * 
	 * @param tile Current Tile
	 * @return Tile to the left current Tile
	 */
	public Tile getW(Tile tile){
		if(tile == null) return null;
		if (tile.getCol() > 0){
			return maze[tile.getCol()-1][tile.getRow()];
		} else {
			return null;
		}
	}
	
	/**
	 * Get relative Tile to the upper-left some current Tile.
	 * 
	 * @param tile
	 * @return
	 */
	public Tile getNW(Tile tile){
		return getW(getN(tile));
	}
	
	/**
	 * Get relative Tile to the upper-right some current Tile.
	 * 
	 * @param tile
	 * @return
	 */
	public Tile getNE(Tile tile){
		return getE(getN(tile));
	}
	
	/**
	 * Get relative Tile to the lower-left some current Tile.
	 * 
	 * @param tile
	 * @return
	 */
	public Tile getSW(Tile tile){
		return getW(getS(tile));
	}
	
	/**
	 * Get relative Tile to the lower-right some current Tile.
	 * 
	 * @param tile
	 * @return
	 */
	public Tile getSE(Tile tile){
		return getE(getS(tile));
	}
	
	/**
	 * Finds the key status of the maze
	 * 
	 * @return the key status of the maze. True if the key has been picked up, false otherwise.
	 */
	public boolean isKeyStatus() {
		return keyStatus;
	}

	/**
	 * Finds the size of the maze (actually the number of rows/columns)
	 * 
	 * @return the number of rows or columns in the maze
	 */
	public int getSize() {
		return size;
	}

	/**
	 * Returns a specific tile at the specified row and column number
	 * 
	 * @param col the column in the maze that you are looking for
	 * @param row the row in the maze that you are looking for
	 * @return the specific tile at the specified row and column number
	 */
	public Tile getTile(int col, int row){
		return maze[col][row];
	}
	
	/**
	 * Gets the first instance of a Tile of the given type. Usually used to find EXIT, START and KEY tiles, hence why it only finds the first instance
	 * Returns null if it can't find anything (it really shouldn't)
	 * 
	 * @param type the type of the tile you're looking for
	 * @return Tile the first instance of a tile that you're looking for
	 */
	public Tile getTileType(int type){
		for(int n = 0;n < size;n++){
			for(int m = 0;m < size;m++){
				if(maze[n][m].getType() == type)return maze[n][m];
			}
		}
		return null;
	}
	
	//Irfan -renamed function for User.java
	/**
	 * Get the type of a Tile.
	 * 
	 * @param row the row in the maze that you are looking for
	 * @param col the column in the maze that you are looking for
	 * @return
	 */
	public int tileType(int row, int col){
		return maze[col][row].getType();
	}
	
	
}