1,273
edits
Changes
no edit summary
{{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();
}
}
/* 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();
}
}