View source for Computer Science/61b/Homework/hw9/Maze.java

{{code}}
 /* Maze.java */
 
 import java.util.*;
 import set.*;
 
 /**
  *  The Maze class represents a maze in a rectangular grid.  There is exactly
  *  one path between any two points.
  **/
 
 public class Maze {
 	
 	// Horizontal and vertical dimensions of the maze.
 	protected int horiz;
 	protected int vert;
 	// Horizontal and vertical interior walls; each is true if the wall exists.
 	protected boolean[][] hWalls;
 	protected boolean[][] vWalls;
 	
 	// Object for generting random numbers.
 	private static Random random;
 	
 	// Constants used in depth-first search (which checks for cycles in the
 	// maze).
 	private static final int STARTHERE = 0;
 	private static final int FROMLEFT = 1;
 	private static final int FROMRIGHT = 2;
 	private static final int FROMABOVE = 3;
 	private static final int FROMBELOW = 4;
 	
 	protected DisjointSets cells;
 	
 	private int targetind(int x, int y) {
 		return (x*vert)+y;
 	}
 	
 	/**
 	 *  Maze() creates a rectangular maze having "horizontalSize" cells in the
 	 *  horizontal direction, and "verticalSize" cells in the vertical direction.
 	 *  There is a path between any two cells of the maze.  A disjoint set data
 	 *  structure is used to ensure that there is only one path between any two
 	 *  cells.
 	 **/
 	public Maze(int horizontalSize, int verticalSize) {
 		int i, j;
 		
 		horiz = horizontalSize;
 		vert = verticalSize;
 		if ((horiz < 1) || (vert < 1) || ((horiz == 1) && (vert == 1))) {
 			return;     // There are no interior walls
 		}
 		
 		// Create all of the horizontal interior walls.  Initially, every
 		// horizontal wall exists; they will be removed later by the maze
 		// generation algorithm.
 		if (vert > 1) {
 			hWalls = new boolean[horiz][vert - 1];
 			for (j = 0; j < vert - 1; j++) {
 				for (i = 0; i < horiz; i++) {
 					hWalls[i][j] = true;
 				}
 			}
 		}
 		// Create all of the vertical interior walls.
 		if (horiz > 1) {
 			vWalls = new boolean[horiz - 1][vert];
 			for (i = 0; i < horiz - 1; i++) {
 				for (j = 0; j < vert; j++) {
 					vWalls[i][j] = true;
 				}
 			}
 		}
 		
 		// create new DjSet with all cells
 		cells = new DisjointSets(horiz*vert);
 		
 		// make an array of all the walls
 		Wall[] wallar = new Wall[horiz*(vert-1) + (horiz-1)*vert];
 		int ii=0;
 		for (int a=0; a<horiz-1; a++) {
 			for (int b=0; b<vert; b++) {
 				wallar[ii] = new Wall(a, b, Wall.V);
 				ii++;
 			}
 		}
 		for (int a=0; a<horiz; a++) {
 			for (int b=0; b<vert-1; b++) {
 				wallar[ii] = new Wall(a, b, Wall.H);
 				ii++;
 			}
 		}
 		
 		// now randomize their order
 		for (int w=wallar.length; w>1; w--) {
 			int targetindex = randInt(w);
 			Wall targetswap = wallar[targetindex];
 			wallar[targetindex] = wallar[w-1];
 			wallar[w-1] = targetswap;
 		}
 		
 		// now remove the walls if the cells they separate have no connection between them
 		for (ii=0; ii<wallar.length; ii++) {
 			Wall curwall = wallar[ii];
 			int cell1x, cell1y, cell2x, cell2y;
 			cell1x = curwall.x; // left or top
 			cell1y = curwall.y;
 			if (curwall.kind == Wall.H) { // horizontal wall
 				cell2x = cell1x; // bottom
 				cell2y = cell1y+1;
 			} else { // vertical wall
 				cell2x = cell1x+1; // right
 				cell2y = cell1y;
 			}
 			int rootc1 = cells.find(targetind(cell1x, cell1y));
 			int rootc2 = cells.find(targetind(cell2x, cell2y));
 			if (rootc1 != rootc2) {
 				if (curwall.kind == Wall.H) {
 					hWalls[curwall.x][curwall.y] = false;
 				} else {
 					vWalls[curwall.x][curwall.y] = false;
 				}
 				cells.union(rootc1, rootc2);
 			}
 		}
 	}
 	
 	/**
 	 *  toString() returns a string representation of the maze.
 	 **/
 	public String toString() {
 		int i, j;
 		String s = "";
 		
 		// Print the top exterior wall.
 		for (i = 0; i < horiz; i++) {
 			s = s + "**";
 		}
 		s = s + "*\n*";
 		
 		// Print the maze interior.
 		for (j = 0; j < vert; j++) {
 			// Print a row of cells and vertical walls.
 			for (i = 0; i < horiz - 1; i++) {
 				if (vWalls[i][j]) {
 					s = s + " *";
 				} else {
 					s = s + "  ";
 				}
 			}
 			s = s + " *\n*";
 			if (j < vert - 1) {
 				// Print a row of horizontal walls and wall corners.
 				for (i = 0; i < horiz; i++) {
 					if (hWalls[i][j]) {
 						s = s + "**";
 					} else {
 						s = s + " *";
 					}
 				}
 				s = s + "\n*";
 			}
 		}
 		
 		// Print the bottom exterior wall.  (Note that the first asterisk has
 		// already been printed.)
 		for (i = 0; i < horiz; i++) {
 			s = s + "**";
 		}
 		return s + "\n";
 	}
 	
 	/**
 	 * horizontalWall() determines whether the horizontal wall on the bottom
 	 * edge of cell (x, y) exists.  If the coordinates (x, y) do not correspond
 	 * to an interior wall, true is returned.
 	 **/
 	public boolean horizontalWall(int x, int y) {
 		if ((x < 0) || (y < 0) || (x > horiz - 1) || (y > vert - 2)) {
 			return true;
 		}
 		return hWalls[x][y];
 	}
 	
 	/**
 	 * verticalWall() determines whether the vertical wall on the right edge of
 	 * cell (x, y) exists. If the coordinates (x, y) do not correspond to an
 	 * interior wall, true is returned.
 	 **/
 	public boolean verticalWall(int x, int y) {
 		if ((x < 0) || (y < 0) || (x > horiz - 2) || (y > vert - 1)) {
 			return true;
 		}
 		return vWalls[x][y];
 	}
 	
 	/**
 	 * randInt() returns a random integer from 0 to choices - 1.
 	 **/
 	private static int randInt(int choices) {
 		if (random == null) {       // Only executed first time randInt() is called
 			random = new Random();  // Create a "Random" object with random seed
 		}
 		int r = random.nextInt() % choices;  // From 1 - choices to choices - 1
 		if (r < 0) {
 			r = -r;                          // From 0 to choices - 1
 		}
 		return r;
 	}
 	
 	/**
 	 * diagnose() checks the maze and prints a warning if not every cell can be
 	 * reached from the upper left corner cell, or if there is a cycle reachable
 	 * from the upper left cell.
 	 *
 	 * DO NOT CHANGE THIS METHOD.  Your code is expected to work with our copy
 	 * of this method.
 	 **/
 	protected void diagnose() {
 		if ((horiz < 1) || (vert < 1) || ((horiz == 1) && (vert == 1))) {
 			return;                                    // There are no interior walls
 		}
 		
 		boolean mazeFine = true;
 		
 		// Create an array that indicates whether each cell has been visited during
 		// a depth-first traversal.
 		boolean[][] cellVisited = new boolean[horiz][vert];
 		// Do a depth-first traversal.
 		if (depthFirstSearch(0, 0, STARTHERE, cellVisited)) {
 			System.out.println("Your maze has a cycle.");
 			mazeFine = false;
 		}
 		
 		// Check to be sure that every cell of the maze was visited.
 outerLoop:
 			for (int j = 0; j < vert; j++) {
 				for (int i = 0; i < horiz; i++) {
 					if (!cellVisited[i][j]) {
 						System.out.println("Not every cell in your maze is reachable from " +
 										   "every other cell.");
 						mazeFine = false;
 						break outerLoop;
 					}
 				}
 			}
 		
 		if (mazeFine) {
 			System.out.println("What a fine maze you've created!");
 		}
 	}
 	
 	/**
 	 * depthFirstSearch() does a depth-first traversal of the maze, marking each
 	 * visited cell.  Returns true if a cycle is found.
 	 *
 	 * DO NOT CHANGE THIS METHOD.  Your code is expected to work with our copy
 	 * of this method.
 	 */
 	protected boolean depthFirstSearch(int x, int y, int fromWhere,
 									   boolean[][] cellVisited) {
 		boolean cycleDetected = false;
 		cellVisited[x][y] = true;
 		
 		// Visit the cell to the right?
 		if ((fromWhere != FROMRIGHT) && !verticalWall(x, y)) {
 			if (cellVisited[x + 1][y]) {
 				cycleDetected = true;
 			} else {
 				cycleDetected = depthFirstSearch(x + 1, y, FROMLEFT, cellVisited) ||
 				cycleDetected;
 			}
 		}
 		
 		// Visit the cell below?
 		if ((fromWhere != FROMBELOW) && !horizontalWall(x, y)) {
 			if (cellVisited[x][y + 1]) {
 				cycleDetected = true;
 			} else {
 				cycleDetected = depthFirstSearch(x, y + 1, FROMABOVE, cellVisited) ||
 				cycleDetected;
 			}
 		}
 		
 		// Visit the cell to the left?
 		if ((fromWhere != FROMLEFT) && !verticalWall(x - 1, y)) {
 			if (cellVisited[x - 1][y]) {
 				cycleDetected = true;
 			} else {
 				cycleDetected = depthFirstSearch(x - 1, y, FROMRIGHT, cellVisited) ||
 				cycleDetected;
 			}
 		}
 		
 		// Visit the cell above?
 		if ((fromWhere != FROMABOVE) && !horizontalWall(x, y - 1)) {
 			if (cellVisited[x][y - 1]) {
 				cycleDetected = true;
 			} else {
 				cycleDetected = depthFirstSearch(x, y - 1, FROMBELOW, cellVisited) ||
 				cycleDetected;
 			}
 		}
 		
 		return cycleDetected;
 	}
 	
 	/**
 	 * main() creates a maze of dimensions specified on the command line, prints
 	 * the maze, and runs the diagnostic method to see if the maze is good.
 	 */
 	public static void main(String[] args) {
 		int x = 39;
 		int y = 15;
 		
 		/**
 		 *  Read the input parameters.
 		 */
 		
 		if (args.length > 0) {
 			try {
 				x = Integer.parseInt(args[0]);
 			}
 			catch (NumberFormatException e) {
 				System.out.println("First argument to Simulation is not an number.");
 			}
 		}
 		
 		if (args.length > 1) {
 			try {
 				y = Integer.parseInt(args[1]);
 			}
 			catch (NumberFormatException e) {
 				System.out.println("Second argument to Simulation is not an number.");
 			}
 		}
 		
 		Maze maze = new Maze(x, y);
 		System.out.print(maze);
 		maze.diagnose();
 	}
 }