maze.java

这是一个迷宫的例子

   } // end if (paths < almostTotal) else
 } // end while (paths < pathsTotal)
} // end addPaths

/** Takes a partition_array (as described in addPaths()), and the values of two points we
   want to connect via a path, and attempts to create a path between them.  Returns true if
   successful. */
boolean addAPath(int[][] partition_array, int x1, int y1, int x2, int y2)
{
 // Make sure we are in the valid range for the maze.
 if ((x2 >= 0) && (x2 < num_columns) && (y2 >= 0) && (y2 < num_rows))
 {
   // Get the nodes corresponding to the points at (x1, y1) and (x2, y2).
   int a = num_columns * y1 + x1;
   int b = num_columns * y2 + x2;
   
   // Starting at "a", follow references until we get one that references itself.
   a = findRepresentative(partition_array, a);
   // Starting at "b", follow references until we get one that references itself.
   b = findRepresentative(partition_array, b);
   
   if (a != b)
   // If is is not equal to b, then there is no sequence of paths between the points.
   {
   // Depending on which value takes longer to reach, set the reference at a to equal
   // b, or vice-versa.  If both values take an equal number of iterations to reach, we
   // must add 1, because upon reaching one, we will have 1 more reference to follow to
   // get to the other one.
   if (partition_array[a][1] < partition_array[b][1])
     partition_array[a][0] = b;
   else
   {
     partition_array[b][0] = a;
     if (partition_array[a][1] == partition_array[b][1])
       partition_array[a][1] += 1;
   }

   // Connect the two vertices with a path
   if (0 == (x2 - x1))
     vert_path_colors[x1][y1 + (y2 - y1 - 1) / 2] = 1;
   else
     horz_path_colors[x1 + (x2 - x1 - 1) / 2][y1] = 1;

   return true;
   } // end if (a != b)
 } // end if ((x2 >= 0) && ...
 return false;
} // end addAPath(int x1, ...

/** Recursive function that finds the node representative of a given partition.
   Also optimizes the partition array by setting all of the nodes it visits along
   the way to point to this last node. */
private int findRepresentative(int[][] partition_array, int a)
{
 // If "a" does not reference itself, recursively call
 // this function until it does, and to speed things up, set the pointer in "a" to point
 // to this last node.
 if (partition_array[a][0] != a)
   partition_array[a][0] = findRepresentative(partition_array, partition_array[a][0]);
 return partition_array[a][0];
}

/** Check to see if the user has solved the maze, and if so, display a window. */
void checkForWin()
{
 if (locations[num_columns - 1][num_rows - 1]) // The user has solved the maze.
 {
   maze_solved = true;

   System.out.println("Maze solved!");
   Dialog d = new Dialog(new Frame(), "Maze solved!");
   d.setSize(150, 40);
   
   // The size (in pixels) of the screen.
   Dimension screenDims = getToolkit().getScreenSize();
   // Center the window on the screen.
   d.setLocation((screenDims.width - 150) / 2, (screenDims.height - 40) / 2);
   // Add a windowListener that will close the window.
   d.addWindowListener(new WindowAdapter()
     { public void windowClosing(WindowEvent e) { ((Dialog)e.getSource()).dispose(); } });
   d.show(); // Display the Dialog.
 }
}

/** A class that allows the interaction between the user and the screen. */
class MazeCanvas extends Canvas
{
 /** Contructor, adds mouse listners. */
 public MazeCanvas(int x, int y)
 {
   super(); // Call the superclass's constructor.

   // Add some classes to listen to the mouse and tell the canvas when to draw input from
   // the user (whenever the mouse is pressed or dragged), and when to check for a win
   // (whenever the mouse is released).
   addMouseListener( new MouseAdapter() {
     public void mousePressed(MouseEvent e) {drawUserInput(e.getX(), e.getY());}
     public void mouseReleased(MouseEvent e) { if (false == maze_solved) checkForWin(); } });
   addMouseMotionListener( new MouseMotionAdapter() {
     public void mouseDragged(MouseEvent e) { drawUserInput(e.getX(), e.getY()); } });

   // Set the size of the maze.
   setSize(x, y);
 }
 
 /**
  * Repaints the applet by drawing the maze and any paths the user has drawn.
  * @param g a reference to the Graphics object on which to draw
  */
 public void paint(Graphics g)
 {
   if (maze_exists)
   // Draw the maze.
   {
     int i, j; // looping variables.
     g.setColor(Color.black); // Maze is to drawn in black.
   
     // Draw the walls of the maze
     // Vertical walls.
     for (i = 0; i < num_columns - 1; i++)
       for (j = 0; j < num_rows; j++)
         if (0 == horz_path_colors[i][j])
       // A vertical wall exists where there is no horizontal path.
         {
           g.drawLine(offset_x + path_width  * (i + 1),
                      offset_y + path_height * j,
                      offset_x + path_width  * (i + 1),
                      offset_y + path_height * (j + 1));
         }
     // Horizontal walls.
     for (i = 0; i < num_columns; i++)
       for (j = 0; j < num_rows - 1; j++)
         if (0 == vert_path_colors[i][j])
         // A horizontal wall exists where there is no vertical path.
         {
           g.drawLine(offset_x + path_width  * i,
                      offset_y + path_height * (j + 1),
                      offset_x + path_width  * (i + 1),
                      offset_y + path_height * (j + 1));
         }

     // Draw the walls around the entrance and exit of the maze.
     g.drawLine(offset_x - path_width, offset_y ,
                offset_x + num_columns * path_width, offset_y);
     g.drawLine(offset_x + num_columns * path_width, offset_y,
                offset_x + num_columns * path_width, offset_y + (num_rows - 1) * path_height);
     g.drawLine(offset_x - path_width, offset_y + path_height,
                offset_x, offset_y + path_height);
     g.drawLine(offset_x, offset_y + path_height,
                offset_x, offset_y + num_rows * path_height);
     g.drawLine(offset_x + num_columns * path_width, offset_y + (num_rows - 1) * path_height,
            offset_x + (num_columns + 1) * path_width, offset_y + (num_rows - 1) * path_height);
     g.drawLine(offset_x, offset_y + num_rows * path_height,
                offset_x + (num_columns + 1) * path_width, offset_y + num_rows * path_height);

     // Draw the paths the user has taken
     // Vertical paths.
     for (i = 0; i < num_columns; i++)
     {
       for (j = 0; j < num_rows - 1; j++)
       {
         if (vert_path_colors[i][j] > 1)
         // The color of the path must be non-transparent if we are to draw it.
         {
           switch (vert_path_colors[i][j])
           {
             case 2: g.setColor(Color.red); break;
             case 3: g.setColor(Color.yellow); break;
             case 4: g.setColor(Color.green); break;
             case 5: g.setColor(Color.cyan); break;
             case 6: g.setColor(Color.blue); break;
             case 7: g.setColor(Color.magenta); break;
             case 8: g.setColor(Color.black); break;
             case 9: g.setColor(Color.white); break;            
             default: break;
           }
           // Draw the path.
           g.drawLine(offset_x + path_width  / 2 + path_width  * i,
                      offset_y + path_height / 2 + path_height * j,
                      offset_x + path_width  / 2 + path_width  * i,
                      offset_y + path_height / 2 + path_height * (j + 1));
         }
       }
     }
   
     // Horizontal paths.
     for (i = 0; i < num_columns - 1; i++)
       for (j = 0; j < num_rows; j++)
       {
         if (horz_path_colors[i][j] > 1)
         // The color of the path must be non-transparent if we are to draw it.
         {
           switch (horz_path_colors[i][j])
           {
             case 2: g.setColor(Color.red); break;
             case 3: g.setColor(Color.yellow); break;
             case 4: g.setColor(Color.green); break;
             case 5: g.setColor(Color.cyan); break;
             case 6: g.setColor(Color.blue); break;
             case 7: g.setColor(Color.magenta); break;
             case 8: g.setColor(Color.black); break;
             case 9: g.setColor(Color.white); break;
             default: break;
           }
           // Draw the path.
           g.drawLine(offset_x + path_width  / 2 + path_width  * i,
                      offset_y + path_height / 2 + path_height * j,
                      offset_x + path_width  / 2 + path_width  * (i + 1),
                      offset_y + path_height / 2 + path_height * j);
         }
       }

     // Determine what color pen or the eraser is selected.
     switch (color_chooser.getSelectedIndex())
     {
       case 0: g.setColor(background_color); break;
       case 1: g.setColor(Color.red); break;
       case 2: g.setColor(Color.yellow); break;
       case 3: g.setColor(Color.green); break;
       case 4: g.setColor(Color.cyan); break;
       case 5: g.setColor(Color.blue); break;
       case 6: g.setColor(Color.magenta); break;
       case 7: g.setColor(Color.black); break;
       case 8: g.setColor(Color.white); break;
       default: break;
     }

     // Draw the begining and ending paths (always there)
     g.drawLine(    offset_x + (num_columns - 1) * path_width  + path_width  / 2,
                    offset_y + (num_rows    - 1) * path_height + path_height / 2,
                2 * offset_x +  num_columns      * path_width,
                    offset_y + (num_rows    - 1) * path_height + path_height / 2);
     g.drawLine(0,                         offset_y + path_height / 2,
                offset_x + path_width / 2, offset_y + path_height / 2);

   }
   else if (maze_creating) // !maze_exists
   {
     // Clear the screen.
     g.clearRect(0, 0, getSize().width, getSize().height);
     // Display the wait string.
     String str = new String("Creating maze, please wait...");
     FontMetrics fm = g.getFontMetrics();
     g.drawString( str, (getSize().width  - fm.stringWidth(str)) / 2,
                        (getSize().height - fm.getHeight()     ) / 2 + fm.getAscent() );
   } // end if(maze_exists)
 } // end paint()


/** Draw the paths the user is drawing as he/she is drawing them.
    @param x the x-coordinate of the location clicked
    @param y the y-coordinate of the location clicked */
 public void drawUserInput(int x, int y)
 {
   // Determine what color pen or the eraser is selected.
   int pencolor = color_chooser.getSelectedIndex() + 1;

   int xlp = (int)((x - offset_x)/path_width);
   int ylp = (int)((y - offset_y)/path_height);
   int xof = (x - offset_x) % path_width - path_width / 2;
   int yof = (y - offset_y) % path_height - path_height / 2;
   int xpath = xlp;
   int ypath = ylp;
   boolean path_vertical = false;
   
   boolean path_up    = ((xlp >= 0) &&
			    (xlp < num_columns) &&
			    (ylp >  0) &&
			    (ylp < num_rows) &&
			    (vert_path_colors[xlp][ylp-1] != 0) &&
			    (locations[xlp][ylp] || locations[xlp][ylp-1]));
   boolean path_down  = ((xlp >= 0) &&
			    (xlp < num_columns) &&
			    (ylp >= 0) &&
			    (ylp < num_rows - 1) &&
			    (vert_path_colors[xlp][ylp] != 0) &&
			    (locations[xlp][ylp] || locations[xlp][ylp+1]));
   boolean path_right = ((xlp >= 0) &&
			    (xlp < num_columns - 1) &&
			    (ylp >= 0) &&
			    (ylp < num_rows) &&
			    (horz_path_colors[xlp][ylp] != 0) &&
			    (locations[xlp][ylp] || locations[xlp+1][ylp]));
   boolean path_left  = ((xlp > 0) &&
			    (xlp < num_columns) &&
			    (ylp >= 0) &&
			    (ylp < num_rows) &&
			    (horz_path_colors[xlp-1][ylp] != 0) &&
			    (locations[xlp][ylp] || locations[xlp-1][ylp]));

   int[] tryorder = new int[4];
   if (Math.abs(xof) < Math.abs(yof))
   {
	    tryorder[0] = (yof >= 0) ? 3 : 1;
	    tryorder[1] = (xof >= 0) ? 2 : 4;
	    tryorder[2] = 6 - tryorder[1];
	    tryorder[3] = 4 - tryorder[0];
   }
   else
   {
	    tryorder[0] = (xof >= 0) ? 2 : 4;
	    tryorder[1] = (yof >= 0) ? 3 : 1;
	    tryorder[2] = 4 - tryorder[1];
	    tryorder[3] = 6 - tryorder[0];
   }

   boolean foundpath = false;
   int i = 0;
   while (!foundpath && i < 4)
   {
	switch (tryorder[i])
	{
	case 1:
	  if (path_up)
	  {
	    xpath = xlp;
	    ypath = ylp - 1;
	    foundpath = true;
	    path_vertical = true;
	  }
	  break;
	case 2:
	  if (path_right)
	  {
	    xpath = xlp;
	    ypath = ylp;
	    foundpath = true;
	    path_vertical = false;
	  }
	  break;
	case 3:
	  if (path_left)
	  {
	    xpath = xlp - 1;
	    ypath = ylp;
	    foundpath = true;
	    path_vertical = false;
	  }
	  break;
	case 4:
	  if (path_down)
	  {
	    xpath = xlp;
	    ypath = ylp;
	    foundpath = true;
	    path_vertical = true;
	  }
	  break;
	}
	i++;
   }

   if (foundpath)
   {
	if (path_vertical)
	{
       vert_path_colors[xpath][ypath] = pencolor;
       locations[xpath][ypath] = true;
       locations[xpath][ypath + 1] = true;
	}
	else
	{
	  horz_path_colors[xpath][ypath] = pencolor;
	  locations[xpath][ypath] = true;
	  locations[xpath + 1][ypath] = true;
	}

	// Get a pointer to the graphics.
	Graphics g = getGraphics();
   
	switch (pencolor)
     {
	  case 1: g.setColor(background_color); break;
	  case 2: g.setColor(Color.red); break;
	  case 3: g.setColor(Color.yellow); break;
	  case 4: g.setColor(Color.green); break;
	  case 5: g.setColor(Color.cyan); break;
	  case 6: g.setColor(Color.blue); break;
	  case 7: g.setColor(Color.magenta); break;
	  case 8: g.setColor(Color.black); break;
	  case 9: g.setColor(Color.white); break;
	  default: break;
	}

	if (path_vertical)
	{
	  g.drawLine(offset_x +      path_width   / 2 + path_width  * xpath,
		     offset_y +      path_height  / 2 + path_height * ypath,
		     offset_x +      path_width   / 2 + path_width  * xpath,
		     offset_y + (3 * path_height) / 2 + path_height * ypath);
	}
	else
	{
	  g.drawLine(offset_x +      path_width   / 2 + path_width  * xpath,
		     offset_y +      path_height  / 2 + path_height * ypath,
		     offset_x + (3 * path_width)  / 2 + path_width  * xpath,
		     offset_y +      path_height  / 2 + path_height * ypath);
	}
	g.dispose();
   } // end if (foundpath)
 } // end DrawUserInput()
} // end class MazeCanvas
} // end class Maze