maze.java

这是一个实现自动生成随机迷宫

         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() {
          // Called every time something is about to be drawn to
          // check the applet size and adjust variables that depend
          // on the size.  This includes a graphics context for the
          // applet.
       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) {  // don't bother filling with background color
        paint(g);                     //   because redrawMaze() does that anyway
    }
    
    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() {
           // run method for thread repeatedly makes a maze and then solves it
       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() {
            // Create a random maze.  The strategy is to start with
            // a grid of disconnnected "rooms" separated by walls.
            // then look at each of the separating walls, in a random
            // order.  If tearing down a wall would not create a loop
            // in the maze, then tear it down.  Otherwise, leave it in place.
        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];  // position of walls between rooms
        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) {
       // Tear down a wall, unless doing so will form a loop.  Tearing down a wall
       // joins two "rooms" into one "room".  (Rooms begin to look like corridors
       // as they grow.)  When a wall is torn down, the room codes on one side are
       // converted to match those on the other side, so all the cells in a room
       // have the same code.   Note that if the room codes on both sides of a
       // wall already have the same code, then tearing down that wall would 
       // create a loop, so the wall is left in place.
            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) {
               // Try to solve the maze by continuing current path from position
               // (row,col).  Return true if a solution is found.  The maze is
               // considered to be solved if the path reaches the lower right cell.
         if (maze[row][col] == emptyCode) {
             maze[row][col] = pathCode;      // add this cell to the path
             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) ||     // try to solve maze by extending path
                  solveMaze(row,col-1) ||     //    in each possible direction
                  solveMaze(row+1,col) ||
                  solveMaze(row,col+1) )
                return true;
             // maze can't be solved from this cell, so backtract out of the cell
             maze[row][col] = visitedCode;   // mark cell as having been visited
             putSquare(row,col,visitedCode);
             try { Thread.sleep(speedSleep); }
             catch (InterruptedException e) { }
          }
          return false;
    }

}