CPSC 215 Lab 8, 10/28/99: Random Maze Generator

For this lab you need to write an applet that generates random mazes using the algorithm described in class. The minimum requirements for your program are:

  1. Your maze generation program must terminate. After the maze has been completely dug out, you should display a message (using showStatus for example) to inidicate this.
  2. Your program must generate different mazes each time (your mazes must be random and can not exhibit any regular patterns).
  3. Your program should work with mazes of any dimension. The size of the graphical representation of your maze should also be variable. (no more than two lines of code should be modified to effect such a change). These settings are determined by the variables bh, bw, mh and mw (see code template).
  4. Determine what happens if instead of a random initial direction, the initial direction is always north.

Here again, is the general description of the algorithm, starting with some fixed starting position x,y (such as center or corner):
  1. "dig out" the space at position x,y (set M[x][y] 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).
You've been provided with an applet template. Although this course is not concerned with graphics, I ask you to to go through the code and try to understand it. This is a good opportunity to review how to set up applets and do simple graphics. In particular, note the following:
  1. Graphics g = getGraphics(); // gets drawing object of applet
  2. g.setColor(Color.red) // sets drawing color (default is black)
  3. g.fillRect(x,y,width,height) // draw rectangle at x,y of indicated size
More Hints:

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 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[mw-1][mh-1] is the largest legal coordinate. Do not confuse mw and mh with bw and bh, which represent the size of the rectangle used to draw each maze cell.

Here is the applet I wrote (may not run on your browser though). Its dimensions are 51X41 (can you guess why not 50X40?) and the graphical representation uses 10x10 rectangles. I used an array byte[][] M, with 0 representing wall and 1 representing path. I used 0,1,2,3 to represent north, east, south and west respectively (so the modulo operation can be used to change direction given any random initial direction).