/* Ready-to-run template for random maze generator (with wrong solution)

   When running the program, you have the option of passing in 3 parameters:
   the height (mh), width (mw) of the maze matrix, and the size of the
   graphical representation (bh).
*/

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

public class badmaze extends JFrame implements ActionListener
{
/* default values: */
static final int NORTH = 0;
static final int EAST = 1;
static final int SOUTH = 2;
static final int WEST = 3;
private int bh = 12;   	// height of a graphical block (for display only)
private int bw = 12;	// width of a graphical block
private int mh = 41;	// default height and width of maze (can change!)
private int mw = 51;
private int ah, aw;	// height and width of graphical maze
private int yoff = 40;    // init y-cord of maze
private Graphics g;
private int dtime = 40;   // 40 ms delay time  - set to 0 for immediate maze
private byte[][] M;	// the array for the maze
private Button startbutton;

public void paint(Graphics g) {} // override automatic repaint

public badmaze(int bh0, int mh0, int mw0)
 { 
   bh = bw = bh0;  mh = mh0;  mw = mw0;
   ah = bh*mh;
   aw = bw*mw;
   startbutton = new Button("Begin");
   startbutton.setBounds((aw/2)-40,yoff+20,80,30);
   Container pane = this.getContentPane(); // the "content pane" of window
   pane.setLayout(null); // else java will place items automatically
   pane.add(startbutton);
   startbutton.addActionListener( this );
   M = new byte[mh][mw];  // initialize maze (default all 0's - walls).
   this.setBounds(0,0,aw+10,10+ah+yoff);	
   this.setVisible(true);
   this.setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE);
   try{Thread.sleep(500);} catch(Exception e) {} // Synch with system
   g = getGraphics();    //g.setColor(Color.red);
 }

// The args determine block size, maze height, and maze width:
public static void main(String[] args)
    {
       int blocksize = 12, mheight = 41, mwidth = 51;
       if (args.length==3)
	   {
	       mheight=Integer.parseInt(args[0]);
	       mwidth=Integer.parseInt(args[1]);
	       blocksize=Integer.parseInt(args[2]);
	   }
       badmaze W = new badmaze(blocksize,mheight,mwidth);
    }

// this function is called when the "begin" button is clicked:
  public void actionPerformed( ActionEvent e )
   { 
     startbutton.setVisible(false);
     g.setColor(Color.green);
     g.fill3DRect(0,yoff,aw,ah,true);  
     // Modify the following line for a different starting point  *********
     digout(mh-1,10); // start digging!
   }   

    // Call this function to display a blue rectangle at MAZE coordinates
    // x,y.  It calls sleep to slow down the program for a nice effect.
public void drawblock(int y, int x)
    {
	g.setColor(Color.blue);
	//	g.fillRect(x*bw,yoff+(y*bh),bw,bh);
        g.fill3DRect(x*bw,yoff+(y*bh),bw,bh,true);
        try{Thread.sleep(dtime);} catch(Exception e) {} 
    }


/* ------------------------------------------------------------------- */
/*  *** main recursive procedure - This is what you have to write. *** */

 public void digout(int y, int x)  
 {
     // The following is a "naive", non-recursive solution that doesn't work:
     //  keep randomly choosing a direction to digout.  

     // We always dig out two spaces at a time: we look two spaces ahead
     // in the direction we're trying to dig out, and if that space has
     // not already been dug out, we dig out that space as well as the
     // intermediate space.  This makes sure that there's always a wall
     // separating adjacent corridors.

     M[y][x] = 1;  // initially dugout spot.
     drawblock(y,x);  // change graphical display
     while (true) // just run infinite loop - see if it'll dig out maze:
	 {
	     int dir = (int)(Math.random()*4); // randomint 0-3
	     if (dir==NORTH)  // look two spaces up
		 if (y-2>=0 && M[y-2][x]==0)
		     {
			 M[y-1][x] = M[y-2][x] = 1;
			 drawblock(y-1,x); drawblock(y-2,x);
			 y = y-2; // prepare for next loop iteration...
		     }
	     if (dir==SOUTH) // two spaces down
		 if (y+2<mh && M[y+2][x]==0)
		     {
			 M[y+1][x] = M[y+2][x] = 1;
			 drawblock(y+1,x); drawblock(y+2,x);
			 y = y+2;
		     }
	     if (dir==WEST) // two spaces left
		 if (x-2>=0 && M[y][x-2]==0)
		     {
			 M[y][x-1] = M[y][x-2] = 1;
			 drawblock(y,x-1); drawblock(y,x-2);
			 x = x-2;
		     }
	     if (dir==EAST) // two spaces right
		 if (x+2<mw && M[y][x+2]==0)
		     {
			 M[y][x+1] = M[y][x+2] = 1;
			 drawblock(y,x+1); drawblock(y,x+2);
			 x = x+2;
		     }
	 } // while

     // The above code doesn't work because it'll eventuall get stuck and
     // it won't know how to explore other posibilities that is has left
     // unexplored.  To do so we need to "remember" these other possibilities
     // on a stack structure.  But that is what recursion automates.  The
     // following is the algorithm you need to implement (also see lab
     // description).

     // Dig out y,x by making the matrix entry 1 and call drawblock to show it.
     // generate a random number between 0-3 (int)(Math.random()*4). 
     // This determines the INITIAL direction of the dig.
     // For each of four directions, see if the space two spaces ahead
     // is 0 (wall).  If so, dig through to that space - that is, 
     // make the intermediate space 1, and recursively call digout 
     // recursively on the coordinates two steps ahead.  
     // Be sure to do this for EACH direction (assuming you won't go 
     // out of bounds).  What's making the maze random is the *order*
     // that you do the digging.  Each call to digout can make up to
     // four recursive calls.
 } // digout

 } // class badmaze