write a java algorithm to randomly generate a maze using the code below.

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 delay(40) to slow down the animation so you can see better how the program is running. The parameter for delay is the number of milliseconds to delay.

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. I will describe two ways to do this. The easier way is to use 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}; // initial identity permutation for (int i=0;i  
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 is 41X51 and the graphical representation uses 10x10 rectangles. But your program should work even if these defaults change (they will).
 
To simplify matters so you can concentrate on the problem, you've been provided with a superclass that already contains a lot of code: mazedfs.java. 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 (it should stay "studentcode"). Currently the function contains only some code that demonstrates the mechanics of the program. You are also encouraged to look at the superclass 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 mazedfs superclass:
 

• byte[][] M: the 2D array for the maze.
• int mwidth and int mheight: width and height of 2D array for the maze

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 mheight, mwidth and the size of the graphical rectangle (in that order). It's also possible to change the name of your subclass to something other than "student" code by providing it as the first command-line parameter (before the three optional ones - if you want to do this look at main in mazedfs.java).

The main function is inside mazedfs, so run with 'java mazedfs' after compiling

import java.awt.*; import java.awt.event.*; import java.awt.Graphics; import javax.swing.*; import java.lang.reflect.*;

public class mazedfs extends JFrame implements KeyListener { /* default values: */ protected int mheight = 41; // default height and width of maze protected int mwidth = 51;

protected byte[][] M; // the array for the maze public static final int SOUTH = 0; public static final int EAST = 1; public static final int NORTH = 2; public static final int WEST = 3;

protected boolean showvalue = false; // affects drawblock protected boolean autodelay = true; // delays automatically between steps protected boolean usegif = false; // graphical properties: protected static int bh = 24; // height of a graphical block protected static int bw = 24; // width of a graphical block protected int ah, aw; // height and width of graphical maze protected int yoff = 42; // init y-cord of maze protected Graphics g; protected int dtime = 30; // ms delay time (for autodelay) protected Color wallcolor = Color.green; protected Color pathcolor = Color.black; protected Color dotcolor = Color.red; protected Image animatedgif; protected String gifname = "miner.gif";

// constructor, args determine block size, maze height, and maze width public mazedfs(int bh0, int mh0, int mw0) { bh = bw = bh0; mheight = mh0; mwidth = mw0; ah = bh*mheight; aw = bw*mwidth; M = new byte[mheight][mwidth]; // initialize maze (all 0's - walls). this.setBounds(0,0,aw+10,10+ah+yoff); this.setVisible(true); this.setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE); this.addKeyListener(this); try{Thread.sleep(500);} catch(Exception e) {} // Synch with system g = getGraphics(); //g.setColor(Color.red); setup(); }

// utility to load animated gif, called from setup after customize() protected void loadgif(String filename) { animatedgif = Toolkit.getDefaultToolkit().getImage(filename); prepareImage(animatedgif,this); try{Thread.sleep(100);} catch(Exception e) {} // Synch with system }//loadgif public void paint(Graphics g) {} // override automatic repaint

public void setup() { g.setColor(wallcolor); g.fill3DRect(0,yoff,aw,ah,true); // fill raised rectangle g.setColor(pathcolor); customize(); // optional startupcode if (usegif) loadgif(gifname); // placed here so user can define gif usage // showStatus("Generating maze..."); digout(mheight-2,mwidth-2); // start digging! (lab 2)

// digout exit square (if digout complete) if (M[mheight-2][mwidth-2]!=0) { M[mheight-1][mwidth-2] = M[mheight-2][mwidth-1] = 1; drawblock(mheight-2,mwidth-1); } solve(); // this is the function you will write for lab 3, part 1 trace(); // for part 2 play(); // for part 3 }

public void delay(int ms) { try {Thread.sleep(ms);} catch(Exception e) {} }

public void drawblock(int y, int x) { g.setColor(pathcolor); g.fillRect(x*bw,yoff+(y*bh),bw,bh); g.setColor(Color.yellow); // following line displays value of M[y][x] in the graphical maze: if (showvalue) g.drawString(""+M[y][x],(x*bw)+(bw/2-4),yoff+(y*bh)+(bh/2+6)); }

public void drawdot(int y, int x) { if (usegif && animatedgif!=null) { g.drawImage(animatedgif,x*bw,yoff+(y*bh),bw,bh,null); } else { g.setColor(dotcolor); g.fillOval(x*bw,yoff+(y*bh),bw,bh); } if (autodelay) try{Thread.sleep(dtime);} catch(Exception e) {} } public void drawgif(int y, int x) { drawdot(y,x); } //alias

public void drawMessage(String m) { g.setColor(Color.green); g.fillRect(0,yoff,bw*mwidth,bh); g.setColor(Color.blue); // erase line g.drawString(m,10,yoff+bh-4); }

////// the following functions are to be overriden in subclass:

public void customize() // user-defined initialization code {} // this is called before digout

/* function to generate random maze */

public void digout(int y, int x) // override for lab 2 (maze generation) { // generates maze - code in subclass } // digout

/* Write a routine to solve the maze. Start at coordinates x=1, y=1, and stop at coordinates x=mwidth-1, y=mheight-2. This coordinate was especially dug out after the program called your digout function (in the "actionPerformed" method). */ public void solve() // override for lab 3 part 1 { int x=1, y=1; // drawdot(y,x); // drawblock(y,x) will erase the dot // modify this function to move the dot to the end of the maze. That // is, when the dot reaches y==mheight-2, x==mwidth-2 } // solve

public void trace() // override for lab 3 part 2, { // draw a dot (without erasing it) along the OPTIMAL path }

/////////////////////////////////////////////////////////////// /// For part three (save a copy of part 2 version first!), you // need to implement the KeyListener interface.

public void play() // override for lab 3, final part { // code to setup game } // for this part you may also define some other instance vars outside of // the play function.

// skeleton implementation of KeyListener interface public void keyReleased(KeyEvent e) {} public void keyTyped(KeyEvent e) {} public void keyPressed(KeyEvent e) // override for key event handling { int key = e.getKeyCode(); // code for key pressed System.out.println("YOU JUST PRESSED KEY "+key); }

// main: public static void main(String[] args) throws Exception { String subclass = "studentcode"; int n = args.length; if (n==1 || n==4) subclass = args[0]; int blocksize = bh, mh = 41, mw = 41; // width/height need to be odd if (n==4 || n==3) { mh=Integer.parseInt(args[n-3]); mw=Integer.parseInt(args[n-2]); blocksize=Integer.parseInt(args[n-1]); } Constructor mcons = Class.forName(subclass).getConstructor(int.class,int.class,int.class); /*mazedfs W =(mazedfs)*/mcons.newInstance(blocksize,mh,mw); }//main

} // mazedfs