import java.awt.*;

public class Maze extends java.applet.Applet implements Runnable {

    int[][] maze;

    final static int backgroundCode = 0;
    final static int wallCode = 1;
    final static int pathCode = 2;
    final static int emptyCode = 3;
    final static int visitedCode = 4;

    Color[] color = new Color[5];  // colors associated with the preceding 5 constants;
    int rows = 21;          // number of rows of cells in maze, including a wall around edges
    int columns = 21;       // number of columns of cells in maze, including a wall around edges
    int border = 0;         // minimum number of pixels between maze and edge of applet
    int sleepTime = 5000;   // wait time after solving one maze before making another
    int speedSleep = 50;    // short delay between steps in making and solving maze

    Thread mazeThread;   // thread for creating and solving maze
    Graphics me = null;  // graphics context for applet; created in checkSize()

    int width = -1;   // width of applet, to be set by checkSize()
    int height = -1;  // height of applet, to be set by checkSize()

    int totalWidth;   // width of applet, minus border area (set in checkSize())
    int totalHeight;  // height of applet, minus border area (set in checkSize())
    int left;         // left edge of maze, allowing for border (set in checkSize())
    int top;          // top edge of maze, allowing for border (set in checkSize())

    boolean mazeExists = false;  // set to true when maze[][] is valid; used in
                                 // redrawMaze(); set to true in createMaze(), and
                                 // reset to false in run()



    Integer getIntParam(String paramName) {

       String param = getParameter(paramName);
       if (param == null)
          return null;
       int i;
       try {
          i = Integer.parseInt(param);
       }
       catch (NumberFormatException e) {
          return null;
       }
       return new Integer(i);
    }

    Color getColorParam(String paramName) {

       String param = getParameter(paramName);
       if (param == null || param.length() == 0)
          return null;
       if (Character.isDigit(param.charAt(0))) {  // try to parse RGB color
          int r=0,g=0,b=0;
          int pos=0;
          int d=0;
          int len=param.length();
          while (pos < len && Character.isDigit(param.charAt(pos)) && r < 255) {
              d = Character.digit(param.charAt(pos),10);
              r = 10*r + d;
              pos++;
          }
          if (r > 255)
             return null;
          while (pos < len && !Character.isDigit(param.charAt(pos)))
             pos++;
          if (pos >= len)
             return null;
          while (pos < len && Character.isDigit(param.charAt(pos)) && g < 255) {
              d = Character.digit(param.charAt(pos),10);
              g = 10*g + d;
              pos++;
          }
          if (g > 255)
             return null;
          while (pos < len && !Character.isDigit(param.charAt(pos)))
             pos++;
          if (pos >= len)
             return null;
          while (pos < len && Character.isDigit(param.charAt(pos)) && b < 255) {
              d = Character.digit(param.charAt(pos),10);
              b = 10*b + d;
              pos++;
          }
          if (b > 255)
             return null;
          return new Color(r,g,b);
       }
       if (param.equalsIgnoreCase("black"))
          return Color.black;
       if (param.equalsIgnoreCase("white"))
          return Color.white;
       if (param.equalsIgnoreCase("red"))
          return Color.red;
       if (param.equalsIgnoreCase("green"))
          return Color.green;
       if (param.equalsIgnoreCase("blue"))
          return Color.blue;
       if (param.equalsIgnoreCase("yellow"))
          return Color.yellow;
       if (param.equalsIgnoreCase("cyan"))
          return Color.cyan;
       if (param.equalsIgnoreCase("magenta"))
          return Color.magenta;
       if (param.equalsIgnoreCase("pink"))
          return Color.pink;
       if (param.equalsIgnoreCase("orange"))
          return Color.orange;
       if (param.equalsIgnoreCase("gray"))
          return Color.gray;
       if (param.equalsIgnoreCase("darkgray"))
          return Color.darkGray;
       if (param.equalsIgnoreCase("lightgray"))
          return Color.lightGray;
       return null;  // param is not a legal color
    }

    public void init() {
         Integer parm;
         parm = getIntParam("rows");
         if (parm != null && parm.intValue() > 4 && parm.intValue() <= 500) {
            rows = parm.intValue();
            if (rows % 2 == 0)
               rows++;
         }
         parm = getIntParam("columns");
         if (parm != null && parm.intValue() > 4 && parm.intValue() <= 500) {
            columns = parm.intValue();
            if (columns % 2 == 0)
               columns++;
         }
         parm = getIntParam("border");
         if (parm != null && parm.intValue() > 0 && parm.intValue() <= 100)
            border = parm.intValue();
         parm = getIntParam("sleepTime");
         if (parm != null && parm.intValue() > 0)
            sleepTime = parm.intValue();
         parm = getIntParam("speed");
         if (parm != null && parm.intValue() > 0 && parm.intValue() < 6)
            switch (parm.intValue()) {
               case 1: speedSleep = 1; break;
               case 2: speedSleep = 25; break;
               case 3: speedSleep = 50; break;
               case 4: speedSleep = 100; break;
               case 5: speedSleep = 200; break;
            }
         color[wallCode] = getColorParam("wallColor");
         if (color[wallCode] == null)
            color[wallCode] = Color.black;
         color[pathCode] = getColorParam("pathColor");
         if (color[pathCode] == null)
            color[pathCode] = new Color(200,0,0);
         color[emptyCode] = getColorParam("emptyColor");
         if (color[emptyCode] == null)
            color[emptyCode] = new Color(128,128,255);
         color[backgroundCode] = getColorParam("borderColor");
         if (color[backgroundCode] == null)
            color[backgroundCode] = Color.white;
         color[visitedCode] = getColorParam("visitedColor");
         if (color[visitedCode] == null)
            color[visitedCode] = color[emptyCode];
         setBackground(color[backgroundCode]);
    }

    void checkSize() {

       if (size().width != width || size().height != height) {
          width  = size().width;
          height = size().height;
          int w = (width - 2*border) / columns;
          int h = (height - 2*border) / rows;
          left = (width - w*columns) / 2;
          top = (height - h*rows) / 2;
          totalWidth = w*columns;
          totalHeight = h*rows;
          if (me != null)
             me.dispose();  // get rid of old graphics context
          me = getGraphics();
       }
    }

    public void start() {
        if (mazeThread == null) {
          mazeThread = new Thread(this);
          mazeThread.start();
        }
        else
           mazeThread.resume();
    }

    public void stop() {
        if (mazeThread != null)
            mazeThread.suspend();
    }

    public void destroy() {
       if (mazeThread != null)
          mazeThread.stop();
    }

    public void paint(Graphics g) {
        checkSize();
        redrawMaze(g);
    }

    public void update(Graphics g) {
        paint(g);
    }

    synchronized void redrawMaze(Graphics g) {
          // draws the entire maze
        g.setColor(color[backgroundCode]);
        g.fillRect(0,0,width,height);
        if (mazeExists) {
           int w = totalWidth / columns;  // width of each cell
           int h = totalHeight / rows;    // height of each cell
           for (int j=0; j<columns; j++)
               for (int i=0; i<rows; i++) {
                   if (maze[i][j] < 0)
                      g.setColor(color[emptyCode]);
                   else
                      g.setColor(color[maze[i][j]]);
                   g.fillRect( (j * w) + left, (i * h) + top, w, h );
               }
         }
    }

    synchronized void putSquare(int row, int col, int colorNum) {
           // draw one cell of the maze, to the graphics context "me"
        checkSize();
        int w = totalWidth / columns;  // width of each cell
        int h = totalHeight / rows;    // height of each cell
        me.setColor(color[colorNum]);
        me.fillRect( (col * w) + left, (row * h) + top, w, h );
    }

    public void run() {

       try { Thread.sleep(2000); } // wait a bit before starting
       catch (InterruptedException e) { }
       while (true) {
          makeMaze();
          solveMaze(1,1);
          try { Thread.sleep(sleepTime); }
          catch (InterruptedException e) { }
          mazeExists = false;
          checkSize();
          redrawMaze(me);   // erase old maze
       }
    }

    void makeMaze() {

        if (maze == null)
           maze = new int[rows][columns];
        int i,j;
        int emptyCt = 0; // number of rooms
        int wallCt = 0;  // number of walls
        int[] wallrow = new int[(rows*columns)/2];
        int[] wallcol = new int[(rows*columns)/2];
        for (i = 0; i<rows; i++)  // start with everything being a wall
            for (j = 0; j < columns; j++)
                maze[i][j] = wallCode;
        for (i = 1; i<rows-1; i += 2)  // make a grid of empty rooms
            for (j = 1; j<columns-1; j += 2) {
                emptyCt++;
                maze[i][j] = -emptyCt;  // each room is represented by a different negative number
                if (i < rows-2) {  // record info about wall below this room
                    wallrow[wallCt] = i+1;
                    wallcol[wallCt] = j;
                    wallCt++;
                }
                if (j < columns-2) {  // record info about wall to right of this room
                    wallrow[wallCt] = i;
                    wallcol[wallCt] = j+1;
                    wallCt++;
                }
             }
        mazeExists = true;
        checkSize();
        redrawMaze(me);  // show the maze
        int r;
        for (i=wallCt-1; i>0; i--) {
            r = (int)(Math.random() * i);  // choose a wall randomly and maybe tear it down
            tearDown(wallrow[r],wallcol[r]);
            wallrow[r] = wallrow[i];
            wallcol[r] = wallcol[i];
        }
        for (i=1; i<rows-1; i++)  // replace negative values in maze[][] with emptyCode
           for (j=1; j<columns-1; j++)
              if (maze[i][j] < 0)
                  maze[i][j] = emptyCode;
    }

    void tearDown(int row, int col) {

            if (row % 2 == 1 && maze[row][col-1] != maze[row][col+1]) {
                       // row is odd; wall separates rooms horizontally
                fill(row, col-1, maze[row][col-1], maze[row][col+1]);
                maze[row][col] = maze[row][col+1];
                putSquare(row,col,emptyCode);
                try { Thread.sleep(speedSleep); }
                catch (InterruptedException e) { }
             }
            else if (row % 2 == 0 && maze[row-1][col] != maze[row+1][col]) {
                      // row is even; wall separates rooms vertically
                fill(row-1, col, maze[row-1][col], maze[row+1][col]);
                maze[row][col] = maze[row+1][col];
                putSquare(row,col,emptyCode);
                try { Thread.sleep(speedSleep); }
                catch (InterruptedException e) { }
             }
    }

    void fill(int row, int col, int replace, int replaceWith) {
           // called by tearDown() to change "room codes".
        if (maze[row][col] == replace) {
            maze[row][col] = replaceWith;
            fill(row+1,col,replace,replaceWith);
            fill(row-1,col,replace,replaceWith);
            fill(row,col+1,replace,replaceWith);
            fill(row,col-1,replace,replaceWith);
        }
    }

    boolean solveMaze(int row, int col) {

         if (maze[row][col] == emptyCode) {
             maze[row][col] = pathCode;
             putSquare(row,col,pathCode);
             if (row == rows-2 && col == columns-2)
                 return true;  // path has reached goal
             try { Thread.sleep(speedSleep); }
             catch (InterruptedException e) { }
             if ( solveMaze(row-1,col) ||
                  solveMaze(row,col-1) ||
                  solveMaze(row+1,col) ||
                  solveMaze(row,col+1) )
                return true;

             maze[row][col] = visitedCode;
             putSquare(row,col,visitedCode);
             try { Thread.sleep(speedSleep); }
             catch (InterruptedException e) { }
          }
          return false;
    }

}