import java.util.Random;
import java.awt.*;


/** 
 MazeClass - Generates a random maze 
 @Author Patrick Muldoon <a href = "mailto:doon@labratsoftware.com"> <Doon@labratsoftware.com></a>
*/

class MazeClass
{
        Random r = new Random();
        
        boolean solved;
        int startX, startY;
        int height, width;
        public  int Maze[][];
        
/** 
 mazeClass() -Default Constructor
  creates and inits the maze array, sets a default height and width of 20
*/
public MazeClass(int h, int w)
{
        int j,k;
        height = h; width = w;
        Maze = new int[height][width];
        solved =false;
        for(j=0;j<height;j++)
                for(k=0;k<width;k++)
                        Maze[j][k] = 1;
        startX = Math.abs(r.nextInt()%(width-3))+1;
        startY = Math.abs(r.nextInt()%(height-3))+1;
        make(startX,startY);
}//end mazeClass (int,int,int)


/** void make.  
  The main recursive function.  It gets called over and over to generate the maze
*/
public void make(int x, int y)
{
        boolean isValid[];
        isValid = new boolean[4];
        int move;

        if(!solved && x==width-1)
        {
                Maze[y][x] = 0;
                solved = true;
                return;
        } //end if!solved
        else
        {
                Maze[y][x]=0;
                mind(isValid,x,y);

                while(movesLeft(isValid))
                {
                        move = pickMind(isValid);
                        if (move == 3)       //down
                                make(x,y+1); 
                        if (move == 2)       //up
                                make(x,y-1);
                        if (move == 1)       //right
                                make(x+1,y);
                        if (move == 0)       //left
                                make(x-1,y);
                        mind(isValid,x,y);
                } //end while
        } //end else
} //end make

public void go()
{
        make(startX,startY);
} //end go

/** boolean check
  This is the main part of the function.  It takes a direction, and checks it
  to make sure that it will form a valid maze. Ie no loops, at most one valid 
  soultion from x,y to the exit
*/
boolean check(int direction, int x, int y)
{
        int sum = 0;
        switch (direction) 
        {
                case 0: //left
                        if(x-1==0)
                                return false;
                        else
                                sum=(Maze[y-1][x-2]+Maze[y-1][x-1]+Maze[y][x-2]+Maze[y][x-1]+Maze[y+1][x-2]+Maze[y+1][x-1]);
                        break; //end left
                case 1: //right
                        if(solved && x+1 == width-1)
                                return false;
                        else if(x+1 == width-1)
                        {
                                return((Maze[y-1][x+1]+Maze[y][x+1]+Maze[y+1][x+1])==3);
                        }
                        else
                                sum=(Maze[y-1][x+1]+Maze[y][x+1]+Maze[y+1][x+1]+Maze[y-1][x+2]+Maze[y][x+2]+Maze[y+1][x+2]);
                        break; //end right
                case 2: //up
                        if(y-1==0)  
                                return false;
                        else
                                sum=(Maze[y-2][x-1]+Maze[y-2][x]+Maze[y-2][x+1]+Maze[y-1][x-1]+Maze[y-1][x]+Maze[y-1][x+1]);
                        break; //end up
                case 3: //down
                        if(y+1 == height-1)
                                return false;
                        else 
                                sum=(Maze[y+1][x-1]+Maze[y+1][x]+Maze[y+1][x+1]+Maze[y+2][x-1]+Maze[y+2][x]+Maze[y+2][x+1]);
                        break; //end down
        }; //end switch(direction)
        if (sum ==6)
                return true;
        else
                return false;
}//end check

/** void Mind
        This sets the array of valid moves. 
*/
void mind(boolean isValid[], int x, int y)
{
        isValid[3]=check(3,x,y); //down
        isValid[2]=check(2,x,y); //up
        isValid[1]=check(1,x,y); //right
        isValid[0]=check(0,x,y); //left
} //end mind

/** int pickmind - 
        This generates a valid move for the generator
        The brains of the generator
*/

int pickMind(boolean isValid[])
{
        int where;

        where=(Math.abs(r.nextInt()))%4;
        while(!isValid[where])
                where=(Math.abs(r.nextInt()))%4;
        return where;
}//end pickmind

/** boolean movesLeft
        returns true if there are any valid moves left for a certain square 
*/
boolean movesLeft(boolean isValid[])
{
        int j=0;
        while(!isValid[j])
        {
                j++;
                if(j==4)
                        return false;
        } //end while
        return true;
} //end movesleft

/** 
        will print the Maze as a series of 1's and 0's usefull for debugging
*/
public void print(Graphics g)
{
        int j,k;
        String s = new String();
        g.drawString("height "+String.valueOf(height)+" width "+String.valueOf(width),5,15);
        for(j=0;j<height;j++)
        {
                for(k=0;k<width;k++)
                        s = s+String.valueOf(Maze[j][k]);
                g.drawString(s,5,((j+1)*20)+50);
                s="";
        }//end for J
}//end print


public int getPlayerStartY()
{
        int start;
        start = Math.abs(r.nextInt()%height-1);
        while(Maze[start][1] != 0)
                start = Math.abs(r.nextInt()%height-1);
        return start;
} //end getplayer start
}