CSC 16 Lab 7 : Random Maze Generator

Due 11/1/2005

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 similar to the "random map" assignment, plus what you learned about recursion. 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.

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. 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.

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. However, you are encouraged to look at the class to get a sense of what's being provided for you.

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!