Computer Science/61b/Homework/hw9/Maze.java

This page contains computer code. Unlike all articles on the lensowiki, which are released under the GFDL, this code is released under the GPL.

Copyright 2006, 2007 Paul Borokhov. All rights reserved.

This code 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 2 of the License, or (at your option) any later version.

The code 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, write to the Free Software Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA

/* 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();
	}
}