CSC 17 Lab 2 : Random Maze Generator

Due one week from date assigned

For this lab you need to write a program that generates random mazes using the recursive algorithm described in class. The program will use a 2D array. You will need to use recursion but the recursive algorithm is provided for you. I'm assuming you attended the class when I went over how to do this assignment.

Here again, is the general description of the algorithm. You start with a matrix M filled with 0's (wall or hedgerow). Starting with some fixed starting position y,x (such as center or corner):

  1. "dig out" the space at position y,x (set M[y][x] to 1).
  2. randomly pick an initial direction
  3. for each direction (starting with the random initial direction),
    1. look at the space two steps away in the current direction (if you won't be looking out of bounds).
    2. if that space is a wall (0), "dig through" (carve out intermediate square) to that space, and recursively execute the algorithm on that space (the one two steps away in the current direction).
To "dig out" a coordinate y,x in the maze:
  1. set the matrix value (M[y][x]) to 1.
  2. call the function "drawblock" at the same coordinates to draw the graphical representation. The "dug out" parts of the maze is represented by black squares (but of course, you can also invert the maze and condsider the green parts as dug out).

Use the the numbers 0, 1, 2, 3 to represent the four different directions. Then to choose a random initial direction, just use something like

"direction = (int)(Math.random()*4);"
To change the direction, use "direction = (1 + direction)%4". By taking the remainder after dividing by 4, you are ensuring that the direction is between 0 and 3. I suggest you work out the algorithm in more detail on paper before coding.

An even better way to randomize the maze is to use a random permutation: 

int[] P = {0,1,2,3};
for (int i=0;i < P.length;i++)
  { int r = (int)(Math.random()*P.length);
    int temp = P[i];  
    P[i] = P[r];
    P[r] = temp;
  }
Then use the array to set the directions.

Figuring out when you're going out of the bounds of the array could be tricky. The variables "mw" and "mh" represent the dimensions (width and height) of the array, so M[mh-1][mw-1] is the largest legal coordinate. That is, the y coordinate must be between 0 and mh-1, inclusive and the x coordinate must be between 0 and mw-1, inclusive.

By default, the dimensions of my maze array is 41X51 and the graphical representation uses 10x10 rectangles.

To simplify matters so you can concentrate on the problem, you've been provided with a template: maze.java. You only need to write the "digout" function at the end. Currently the function contains only some code that demonstrates the mechanics of the program. You are also encouraged to look at the class to get a sense of what's being provided for you (e.g, NORTH, SOUTH, EAST, WEST constants.)

You need to understand that the following variables are already declared in the mazegen class:

These are the variables that you must refer to in your function. There are other variables in the class that you can ignore (or experiment with). You need to understand that these variables are already declared inside the class - so DON'T DECLARE THEM AGAIN! The values of these variables are set in the constructor. To change them, note that the main function takes 3 optional command line arguments for mh, mw and the size of the graphical rectangle (in that order).

Read this again to make sure you know what to do!