mazefog2.java

Tim duong di trong me cung mot thuat toan kha hay

*/
  void makeBoard(
    boolean displayFlag)          // true if we draw lines as we create maze
  {
    int boardHeight;              // height (in pixels) of actual game board
    int boardWidth;               // width (in pixels) of actual game board
    int col;                      // temporary column number (index)
    Graphics gr;                  // graphics context for <boardCanvas>
    int row;                      // temporary row number (index)

    /* Get a graphics context for drawing on the game board. */

    if (displayFlag)
      gr = boardCanvas.getGraphics();
    else
      gr = null;                  // to keep compiler happy

    /* Calculate the number of rows and columns for the game board, knowing the
    size of <boardCanvas> in pixels and the size of each board square. */

    boardHeight = boardCanvas.getSize().height; // for JDK1.1
    boardWidth = boardCanvas.getSize().width; // for JDK1.1
    if (displayFlag)
    {
      gr.setColor(BACKGROUND);    // clear board to background color
      gr.fillRect(0, 0, boardWidth, boardHeight);
    }

    numRows = (boardHeight - (2 * canvasBorder) - boardLineWidth)
      / boardGridSize;
    numRows = Math.max(3, numRows); // minimum of three rows

    numCols = (boardWidth - (2 * canvasBorder) - boardLineWidth)
      / boardGridSize;
    numCols = Math.max(3, numCols); // minimum of three columns

    /* Allocate new arrays.  Note that the internal game board has an extra
    column on the right and an extra row on the bottom to make programming
    logic easier. */

    boardDistance = new int[numRows + 1][numCols + 1]; // distance from exit
    boardLeft = new int[numRows + 1][numCols + 1]; // vertical lines
    boardTop = new int[numRows + 1][numCols + 1]; // horizontal lines

    /* Initialize the arrays to default values. */

    for (row = 0; row <= numRows; row ++)
      for (col = 0; col <= numCols; col ++)
      {
        boardDistance[row][col] = -1; // invalidate all distances from exit
        boardLeft[row][col] = LineEMPTY; // no vertical lines yet
        boardTop[row][col] = LineEMPTY; // no horizontal lines yet
      }
    exitCol = exitRow = 0;        // just to be safe, set some initial value
    startCol = startDistance = startRow = 0;
    userCol = userColOffset = userRow = userRowOffset = 0;

    /* Pick a random edge (top, left, right, bottom) and a random square on
    that edge to become the exit ... which is our starting point.  By this
    method, corners have a double chance of being selected. */

    switch ((int) (Math.random() * 4))
    {
      case 0:                     // top edge
        row = 0;                  // first row
        col = (int) (Math.random() * numCols); // random column
        boardLeft[row][col] = LineHIDDEN;     // left line
        boardLeft[row][col + 1] = LineHIDDEN; // right line
        boardTop[row + 1][col] = LineHIDDEN;  // bottom line
        if (displayFlag)
        {
          drawBoardLeftLine(gr, row, col, ColorLINE); // left line
          drawBoardLeftLine(gr, row, col + 1, ColorLINE); // right line
          drawBoardTopLine(gr, row + 1, col, ColorLINE); // bottom line
        }
        break;

      case 1:                     // left edge
        row = (int) (Math.random() * numRows); // random row
        col = 0;                  // first column
        boardTop[row][col] = LineHIDDEN;      // top line
        boardLeft[row][col + 1] = LineHIDDEN; // right line
        boardTop[row + 1][col] = LineHIDDEN;  // bottom line
        if (displayFlag)
        {
          drawBoardTopLine(gr, row, col, ColorLINE); // top line
          drawBoardLeftLine(gr, row, col + 1, ColorLINE); // right line
          drawBoardTopLine(gr, row + 1, col, ColorLINE); // bottom line
        }
        break;

      case 2:                     // right edge
        row = (int) (Math.random() * numRows); // random row
        col = numCols - 1;        // last column
        boardTop[row][col] = LineHIDDEN;      // top line
        boardLeft[row][col] = LineHIDDEN;     // left line
        boardTop[row + 1][col] = LineHIDDEN;  // bottom line
        if (displayFlag)
        {
          drawBoardTopLine(gr, row, col, ColorLINE); // top line
          drawBoardLeftLine(gr, row, col, ColorLINE); // left line
          drawBoardTopLine(gr, row + 1, col, ColorLINE); // bottom line
        }
        break;

      default:                    // bottom edge
        row = numRows - 1;        // last row
        col = (int) (Math.random() * numCols); // random column
        boardTop[row][col] = LineHIDDEN;      // top line
        boardLeft[row][col] = LineHIDDEN;     // left line
        boardLeft[row][col + 1] = LineHIDDEN; // right line
        if (displayFlag)
        {
          drawBoardTopLine(gr, row, col, ColorLINE); // top line
          drawBoardLeftLine(gr, row, col, ColorLINE); // left line
          drawBoardLeftLine(gr, row, col + 1, ColorLINE); // right line
        }
        break;
    }

    /* Remember where the exit is and mark the exit on the game board. */

    exitRow = row;                // save exit (goal) row number
    exitCol = col;                // save exit (goal) column number
    boardDistance[exitRow][exitCol] = 0; // exit is zero squares from itself
    if (displayFlag)
      drawBoardExit(gr, exitRow, exitCol); // mark exit on game board

    /* Complete the maze by recursion. */

    makeBoardRecurse(gr, exitRow, exitCol, displayFlag);

    /* Draw the user's position, which is the furthest from the exit. */

    userRow = startRow;           // set current position to starting position
    userCol = startCol;
    if (displayFlag)
      drawBoardUser(gr, userRow, userCol, userRowOffset, userColOffset,
        ColorUSER);               // mark user's position
    makeLinesVisible(gr, userRow, userCol, displayFlag);
                                  // this may reveal hidden lines

    /* Release the graphics context, because it's better to explicitly release
    the graphics context rather than wait for the garbage collector. */

    if (displayFlag)
      gr.dispose();               // release graphics context

  } // end of makeBoard() method


/*
  makeBoardRecurse() method

  The maze is created by recursively calling this method.  Each call has a
  starting row and column number.  We attempt to move in all four directions,
  in random order and with random distances.  Then we recurse with the end
  points of the successful attempts.  The recursion happens after our four
  attempts, because recursing on each attempt would generate too many spiral
  paths and not enough branches.
*/
  void makeBoardRecurse(
    Graphics gr,                  // graphics context of <boardCanvas>
    int fromRow,                  // recurse from this row number (index)
    int fromCol,                  // recurse from this column number (index)
    boolean displayFlag)          // true if we draw lines as we create maze
  {
    int attempt;                  // how far we want to move
    int branchCol;                // column number of branching point
    int branchRow;                // row number of branching point
    int direction;                // current direction
    int dirIncr;                  // pseudo-random increment for next direction
    int good;                     // number of good paths found
    int goodCols[];               // column numbers for good paths
    int goodRows[];               // row numbers for good paths
    int thisCol;                  // column number of current position
    int thisRow;                  // row number of current position

    /* Clear the list of known good paths (successful attempts). */

    good = 0;                     // nothing found yet
    goodCols = new int[4];        // four directions maximum size
    goodRows = new int[4];

    /* While we attempt to move in four directions, we don't make all of those
    moves from the caller's starting position.  The second and later directions
    choose a branching point off the previous path. */

    branchCol = thisCol = fromCol; // everyone starts in the same place
    branchRow = thisRow = fromRow;

    /* Choose the first direction at random, and choose a random increment
    between directions.  We pretend that there are five directions and ignore
    the fifth direction, because five is relatively prime to 1, 2, 3, and 4.
    This gives us four possible increments with one fake (wasted) direction.
    If we used only the four real directions, we would only have two possible
    increments (1 and 3) since 2 is not relatively prime to 4. */

    direction = (int) (Math.random() * 5); // initial direction from 0 to 4
    dirIncr = 1 + (int) (Math.random() * 4); // increment from 1 to 4

    for (int i = 0; i < 5; i ++)  // try each of "five" directions
    {
      /* Try to go a random distance in the given direction.  Start somewhere
      along the path between where we are now and where we last branched off. */

      branchRow = thisRow = branchRow
        + (int) (Math.random() * (thisRow - branchRow));
      branchCol = thisCol = branchCol
        + (int) (Math.random() * (thisCol - branchCol));
      attempt = 2 + (int) (Math.random() * 5); // attempted distance

      while (attempt > 0)
      {
        switch (direction)
        {
          case 0:                 // can we go up?
            if ((thisRow < 1)
            || (boardDistance[thisRow - 1][thisCol] >= 0))
            {
              attempt = 0;        // can't go up
            }
            else
            {
              thisRow --;         // go up
              boardTop[thisRow + 1][thisCol] = LineEMPTY; // remove old top
              boardTop[thisRow][thisCol] = LineHIDDEN; // add new top line
              boardLeft[thisRow][thisCol] = LineHIDDEN; // add new left line
              boardLeft[thisRow][thisCol + 1] = LineHIDDEN; // add new right line
              if (displayFlag)
              {
                drawBoardTopLine(gr, thisRow + 1, thisCol, BACKGROUND); // old top
                drawBoardTopLine(gr, thisRow, thisCol, ColorLINE); // new top
                drawBoardLeftLine(gr, thisRow, thisCol, ColorLINE); // new left
                drawBoardLeftLine(gr, thisRow, thisCol + 1, ColorLINE); // new right
              }
            }
            break;

          case 1:                 // can we go left?
            if ((thisCol < 1)
            || (boardDistance[thisRow][thisCol - 1] >= 0))
            {
              attempt = 0;        // can't go left
            }
            else
            {
              thisCol --;         // go left
              boardLeft[thisRow][thisCol + 1] = LineEMPTY; // remove old left
              boardTop[thisRow][thisCol] = LineHIDDEN; // add new top line
              boardLeft[thisRow][thisCol] = LineHIDDEN; // add new left line
              boardTop[thisRow + 1][thisCol] = LineHIDDEN; // add new bottom line
              if (displayFlag)
              {
                drawBoardLeftLine(gr, thisRow, thisCol + 1, BACKGROUND); // old left
                drawBoardTopLine(gr, thisRow, thisCol, ColorLINE); // new top
                drawBoardLeftLine(gr, thisRow, thisCol, ColorLINE); // new left
                drawBoardTopLine(gr, thisRow + 1, thisCol, ColorLINE); // new bottom
              }
            }
            break;

          case 2:                 // can we go right?
            if ((thisCol >= (numCols - 1))
            || (boardDistance[thisRow][thisCol + 1] >= 0))
            {
              attempt = 0;        // can't go right
            }
            else
            {
              thisCol ++;         // go right
              boardLeft[thisRow][thisCol] = LineEMPTY; // remove old right
              boardTop[thisRow][thisCol] = LineHIDDEN; // add new top line
              boardLeft[thisRow][thisCol + 1] = LineHIDDEN; // add new right line
              boardTop[thisRow + 1][thisCol] = LineHIDDEN; // add new bottom line
              if (displayFlag)
              {
                drawBoardLeftLine(gr, thisRow, thisCol, BACKGROUND); // old right
                drawBoardTopLine(gr, thisRow, thisCol, ColorLINE); // new top
                drawBoardLeftLine(gr, thisRow, thisCol + 1, ColorLINE); // new right
                drawBoardTopLine(gr, thisRow + 1, thisCol, ColorLINE); // new bottom
              }
            }
            break;

          case 3:                 // can we go down?
            if ((thisRow >= (numRows - 1))
            || (boardDistance[thisRow + 1][thisCol] >= 0))
            {
              attempt = 0;        // can't go down
            }
            else
            {
              thisRow ++;         // go down
              boardTop[thisRow][thisCol] = LineEMPTY; // remove old bottom
              boardLeft[thisRow][thisCol] = LineHIDDEN; // add new left line
              boardLeft[thisRow][thisCol + 1] = LineHIDDEN; // add new right line
              boardTop[thisRow + 1][thisCol] = LineHIDDEN; // add new bottom line
              if (displayFlag)
              {
                drawBoardTopLine(gr, thisRow, thisCol, BACKGROUND); // old bottom
                drawBoardLeftLine(gr, thisRow, thisCol, ColorLINE); // new left
                drawBoardLeftLine(gr, thisRow, thisCol + 1, ColorLINE); // new right
                drawBoardTopLine(gr, thisRow + 1, thisCol, ColorLINE); // new bottom
              }
            }