CSC 17 Lab : Random Maze Generator

Due one week from date assigned, BEFORE THE NEXT LAB

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. A recursive algorithm is provided for you. Study the algorithm first. I'm assuming you attended the class when I went over how to do this assignment, but briefly, you will inherit a class that represents the maze with a 2D array int[][] M, of dimensions mheight rows by mwidth columns. You will override the digout function of the superclass using a recursive algorithm. The values inside each M[y][x] is initially zero, which graphically is represented by a green square. "Digging out" a maze location y,x means setting M[y][x]=1, AND calling drawblock(y,x); which changes the graphical representation to a black square. Because we tend to think of array coordinates in "row-major order", it is helpful to give the y (row) coordinate before the x (column) coordinate.

Here is the general description of the algorithm. Starting with some fixed starting position y,x (determined outside of digout)

  1. "dig out" the space at position y,x. This means set M[y][x]=1, and call drawblock(y,x);
  2. for each possible direction (n,e,s,w),
    1. look at the space two steps away in that direction (if you won't be looking out of bounds and if it's not already dug out).
    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).
  3. Optionally, call nextframe(40); to slow down the animation (by 40ms in this example) so you can see better how the program is running. Otherwise the maze will only be displayed once fully generated.
What makes the maze random is the order in which the directions are checked: Do you go N,E,S,W, or S,E,W,N, or some other order? Be sure that you understand this point: you are making not one but up to FOUR recursive calls inside digout. It's the order in which these recursive calls are made that makes the maze random. The choice of algorithm to randomize the ordering of directions is important. Conceptually, our maze is like a tree because from each point we extend it by up to four branches, and these branches will not intersect. If this tree is not truely random, meaning that some possibilities are more likely to occur than others, then the tree beneath the maze may not be balanced enough: it would be more likely to create a degenerate tree. Not only will such mazes be less interesting, but extremely unbalanced trees can cause recursion to crash due to stack overflow. This is much less likely to occur (virtually impossible), if our maze is truly random, meaning that every possible maze has an equal chance of appearing. For example, one possible algorithm is the following: choose a random initial direction: "direction = (int)(Math.random()*4);" then to change the direction, do "direction = (1 + direction)%4". By taking the remainder after dividing by 4, you are ensuring that the direction is between 0 and 3. But this algorithm is defective because some possibilities are excluded, such as direction 2 followed by direction 1.

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

int[] P = {0,1,2,3}; // initial identity permutation
for (int i=0;i < P.length-1;i++)
  { int r = i+(int)(Math.random()*(P.length-i));//r is between i and P.length-1
    int temp = P[i];   // swap each element with some random element.
    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 "mwidth" and "mheight" represent the dimensions (width and height) of the array, so M[mheight-1][mwidth-1] is the largest legal coordinate. That is, the y coordinate must be between 0 and mheight-1, inclusive and the x coordinate must be between 0 and mwidth-1, inclusive.

By default, the dimensions of my maze array are 41X41 (mheight,mwidth) and the graphical representation uses 20x20 rectangles (bh,bw). But your program should work even if these defaults change (they can be changed in the @Override customize() function). Choosing odd values for mheight,mwidth will result in a maze with a green border.

To simplify matters so you can concentrate on the problem, you've been provided with a superclass that already contains a lot of code: mazebase.java. Javadoc documentation for this class is available at mazebase.html. You only need to write a subclass that *overrides* (redefines) the "digout" function. Use this template. You don't need to change the name of the file or public class. Currently the function contains only some code that demonstrates the mechanics of the program. You are also encouraged to look at documentation of the base class to see what's provided for you (though this is more important for the followup lab).

YOU MAY NOT MAKE ANY CHANGES TO THE mazebase SUPERCLASS!

This is a core concept in good software engineering: code reuse and code compatibility. You often don't even have access or the legal right to change any existing code. The superclass has been designed so that no such changes are neccessary. You may configure the class according to your own needs by changing the values of variables and overriding methods in the superclass, but you may not edit the superclass.

The following variables are already declared in the mazebase superclass:

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 these and other variables, override the function public void customize(). You can use this function to change various parameters including mwidth, mheight, the size of the graphical squares (bh,bw) as well as the colors for the graphical represention. There are, however, certain other variables (aw,ah) that are set according to the values of other variables, and you should not change them. The constructor of the mazebase superclass calls the customize function first before setting up anything else. The following is a sample customize: 
    @Override
    public void customize()
    {
        bh*=2; // 4x size of graphical squares
        bw*=2;
        mwidth = 31;  mheight = 31;  // change dimensions of maze (keep'em odd)
        wallcolor = java.awt.Color.yellow;  // change maze color to yellow
    }

Challenge: Rewrite the digout function without using recursion. You will need to use a stack data structure. Refer to the triangles program as an example. However, this program is harder to do without recursion because the recursive calls can interfere with eachother. That is, making three consecutive recursive calls is not exactly the same as pushing three frames on a stack. Before making a recursive call, you need to check that the y,x coordinate to dig out has not been dug out already. With recursion, the second (and third) recursive call is not made until the first one (and second) completely returns, so the check is made before each recursive call. If you just push three frames on the stack, the check is not made for each simulated recursion: by the time the second (and third) frame is popped the maze may have already been changed. Therefore when you pop a frame off of the stack you must check again if the coordinate has already been dug out. Furthermore, you can only digout the intermediate square once you have rechecked the coordinate.