import java.awt.*; import javax.swing.*; import java.awt.event.*; import javax.swing.event.*; import java.util.*; public class Maze { static final int OPEN = 0; static final int CLOSED = 1; static final int UNVISITED = 0; static final int VISITED = 1; static final int NORTH = 1; static final int SOUTH = 2; static final int EAST = 3; static final int WEST = 4; int numRows = -1, numCols = -1; int startX, startY; int maxPathLength; // Convention: topleft is (0,0). Rows count downward, // columns go left to right. Thus maze[r][c] is r-th row from top, // c-th col from left. int[][][] maze; LinkedList solutionPath; public Maze (int numRows, int numCols) { this.numRows = numRows; this.numCols = numCols; // Make the array of walls. maze = new int [numRows][numCols][5]; // Initialize to closed. for (int x=0; x 0) && (maze[x][y][NORTH] == CLOSED) && (maze[x-1][y][0] == UNVISITED)) { possibleNeighbors[numValid] = new Coord (x-1,y); numValid ++; } // SOUTH if ((x  0) && (maze[x][y][WEST] == CLOSED) && (maze[x][y-1][0] == UNVISITED)) { possibleNeighbors[numValid] = new Coord (x,y-1); numValid ++; } if (numValid == 0) { return null; } // Now compact the array. Coord[] validNeighbors = new Coord [numValid]; for (int i=0; i solutionPath) { this.solutionPath = solutionPath; } public Coord[] getClosedNeighbors (Coord c) { Coord[] possibleNeighbors = new Coord [4]; int numValid = 0; int x = c.row; int y = c.col; // See if North is valid. if ( (x > 0) && (maze[x][y][NORTH] == CLOSED) ) { possibleNeighbors[numValid] = new Coord (x-1,y); numValid ++; } // SOUTH if ( (x  0) && (maze[x][y][WEST] == CLOSED) ) { possibleNeighbors[numValid] = new Coord (x,y-1); numValid ++; } if (numValid == 0) { return null; } // Now compact the array. Coord[] validNeighbors = new Coord [numValid]; for (int i=0; i 0) && (maze[x][y][NORTH] == OPEN) && (maze[x-1][y][0] == UNVISITED)) { possibleNeighbors[numValid] = new Coord (x-1,y); numValid ++; } // SOUTH if ((x  0) && (maze[x][y][WEST] == OPEN) && (maze[x][y-1][0] == UNVISITED)) { possibleNeighbors[numValid] = new Coord (x,y-1); numValid ++; } if (numValid == 0) { return null; } // Now compact the array. Coord[] validNeighbors = new Coord [numValid]; for (int i=0; i solutionPath; public void paintComponent (Graphics g) { int numRows = maze.length; int numCols = maze[0].length; Dimension D = this.getSize(); int cellHeight = D.height / numRows; int cellWidth = D.width / numCols; int xSeg = cellWidth / 4; int ySeg = cellHeight / 4; for (int i=0; i 
public class MazeMaker { static int desiredPathLength; static Maze maze; public static void main (String[] argv) { generateMaze (5, 5); } public static void generateMaze (int numRows, int numCols) { maze = new Maze (numRows, numCols); // We want to generate a path of this length: desiredPathLength = numRows * numCols; // Initially, we'll start with the top left cell and mark that as visited. Coord start = new Coord (0, 0); maze.markVisited (start); // Generate the maze path recursively. boolean found = recursiveGenerate (start, 1); if (! found) { System.out.println ("Could not create the whole maze"); } maze.display(); } static boolean recursiveGenerate (Coord c, int pathLength) { // Bottom out condition 1: if (pathLength == desiredPathLength) { // Done. We've created a maze path of the desired length. return true; } // Bottom out condition 2: see if there's a neighbor to visit. Coord[] validNeighbors = maze.getUnvisitedClosedNeighbors (c); if ((validNeighbors == null) || (validNeighbors.length == 0)) { // There's no neighbor whose wall we can break. So quit trying. return false; } // Otherwise, pick a random neighbor and proceed. int i = UniformRandom.uniform (0, validNeighbors.length-1); // Break the wall and mark the neighbor as visited. maze.breakWall (c, validNeighbors[i]); maze.markVisited (validNeighbors[i]); // Recurse. return recursiveGenerate (validNeighbors[i], pathLength+1); } }
 
 
 
// File: UniformRandom.java // // Author: Rahul Simha // Created: Sept 22, 1998. // // Uniform random number generator with different uniform // generators. public class UniformRandom { // Basic Lehmer generator - constants static final long m = 2147483647L; static final long a = 48271L; static final long q = 44488L; static final long r = 3399L; static long r_seed = 12345678L; public static void set_seed (long seed) { r_seed = seed; } // Basic Lehmer generator - uniform[0,1] // For more information see Knuth, Vol. II. public static double uniform () { long hi = r_seed / q; long lo = r_seed - q * hi; long t = a * lo - r * hi; if (t > 0) r_seed = t; else r_seed = t + m; return ( (double) r_seed / (double) m ); } // U[a,b] generator public static double uniform (double a, double b) { if (b > a) return ( a + (b-a) * uniform() ); else { System.out.println ("ERR in uniform(double,double):a="+a+"b="+b); return 0; } } // Discrete Uniform random generator - returns an // integer between a and b public static long uniform (long a, long b) { if (b > a) { double x = uniform (); long c = ( a + (long) Math.floor((b-a+1)*x) ); return c; } else if (a == b) return a; else { System.out.println ("ERR: in uniform(long,long):a="+a+"b="+b); return 0; } } public static int uniform (int a, int b) { return (int) uniform ((long) a, (long) b); } } // End of class "UniformRandom"
 
 
 
  In-Class Exercise 9: Download Maze.java an and MazeMaker.java. You will also nee d UniformRandom.java. Then compi le and execute. Why doesn't it produce a path of the desired length?  In-Class Exercise 9: Download Maze.java an and MazeMaker.java. You will also nee d UniformRandom.java. Then compi le and execute. Why doesn't it produce a path of the desired length