maze.java

这是一个迷宫的例子

//package maze;

//Maze.java:  Version 4.1
//Written by Nathanael Berglund
//
//This program creates a maze and allows the user to attempt to solve it.
//------------------------------------------------------------------------
import java.applet.*;
import java.awt.*;
import java.text.*;
import java.awt.event.*;
import java.util.*;

/** A class for creating and displaying a maze on the screen, and
 allowing the user to try to solve it.
 @author Nathanael Berglund */
public class Maze extends Applet
{
/** A pseudo-random number used to create a different maze every time */
public Random rand;

/** The background color of the maze */
public Color background_color;

////////////////////////////////////////////////////////////////////////////
// Maze creation.
////////////////////////////////////////////////////////////////////////////
/** Indicates whether or not a maze has been created. */
protected boolean maze_exists;
/** Indicates if a maze is currently being created. */
protected boolean maze_creating;

////////////////////////////////////////////////////////////////////////////
// Maze Dimensions.
////////////////////////////////////////////////////////////////////////////
/** How much to offset the maze in order to center it in the x-direction. */
int offset_x;
/** How much to offset the maze in order to center it in the y_direction. */
int offset_y;
/** The width of the maze in terms of the path width. */
public int num_columns;
/** The height of the maze in terms of the path height. */
public int num_rows;
/** The width of the paths */
public int path_width;
/** The height of the paths. */
public int path_height;

////////////////////////////////////////////////////////////////////////////////////////
// Maze State.
////////////////////////////////////////////////////////////////////////////////////////
/** Indicates whether the user has solved the maze. */
public boolean maze_solved;
/** An array corresponding to the lattice points where paths meet.  Used to keep track of
   where the user has gone in the maze. */
boolean[][] locations;
/** Indicates, for each vertical path, what color to color the path and if it is free.
   (not blocked by a wall). */
int[][] vert_path_colors;
/** Indicates, for each horizontal path, what color to color the path and if it is free.
   (not blocked by a wall).*/
int[][] horz_path_colors;

///////////////////////////////////////////////////////////////////////////////////
// Visual display.
///////////////////////////////////////////////////////////////////////////////////
/** Let's the user chosse the pen color. */
public Choice color_chooser;
/** Button the creates a new maze. */
public Button reset_button;
/** TextField that let's the user set the desired number of columns in the maze */
public TextField num_columns_field;
/** TextField that let's the user set the desired number of rows in the maze */
public TextField num_rows_field;
/** A Canvas which holds the maze and allows the user to draw on it. */
public MazeCanvas maze_canvas;

/**
* Perform initialization for the maze, such as setting the
* background color, initaializing arrays, etc.
*/
public void init()
{
// Initialize some member variables.
maze_exists = false;
maze_creating = false;
color_chooser = new Choice();
reset_button  = new Button("Create New Maze");
num_columns_field = new TextField(4);
num_rows_field = new TextField(4);

 /* APPLET PARAMETERS:
    bgc_red
    bgc_green
    bgc_blue
    num_columns
    num_rows */

 // Get the red, green, and blue color parameters
 int red = 255, green = 255, blue = 255;
 String s = getParameter("bgc_red");
 if (null != s)
   red = Integer.parseInt(s);

 s = getParameter("bgc_green");
 if (null != s)
   green = Integer.parseInt(s);

 s = getParameter("bgc_blue");
 if (null != s)
   blue = Integer.parseInt(s);

 // Set the background color
 background_color = new Color(red, green, blue);
 setBackground(background_color);

 // Get the num_columns parameter.
 s = getParameter("num_columns");
 num_columns = (null == s) ? 50 : Integer.parseInt(getParameter("num_columns"));

 // Get the num_rows parameter.
 s = getParameter("num_rows");
 num_rows = (null == s) ? 50 : Integer.parseInt(getParameter("num_rows"));

 // Add the choices to the color chooser
 color_chooser.add("Eraser");
 color_chooser.add("Red");
 color_chooser.add("Yellow");
 color_chooser.add("Green");
 color_chooser.add("Cyan");
 color_chooser.add("Blue");
 color_chooser.add("Violet");
 color_chooser.add("Black");
 color_chooser.add("White");
 color_chooser.select(1); // Red is the default pen color.

 // Add the reset button
 add(reset_button);

 // Add a text label preceding the ColorChooser
 add(new Label("Pen Color:", Label.RIGHT)); 

 // Add the color chooser
 add(color_chooser);

 // Add a text label preceding the num_columns_field
 add(new Label("Desired Columns:", Label.RIGHT));

 // Add the num_columns_field
 add(num_columns_field);
 num_columns_field.setText(Integer.toString(num_columns));

 // Add a text label preceding the num_rows_field
 add(new Label("Desired Rows:", Label.RIGHT));

 // Add the num_rows_field
 add(num_rows_field);
 num_rows_field.setText(Integer.toString(num_rows));

 // Register the button event handler
 reset_button.addActionListener(new ActionListener(){
                                public void actionPerformed(ActionEvent e) { reset(); } });

 // Create and add the canvas
 maze_canvas = new MazeCanvas(getSize().width, getSize().height - 33);
   // 33 is the amount of height the top components will take up.
 add(maze_canvas);

} // end init()

/** Create/Recreate the maze. */
public void reset()
{
 maze_solved = false;

 // Initialize the random number generator, based on the current time.
 rand = new Random(System.currentTimeMillis());

 System.out.println("New maze requested.");
 System.out.println("Requested Columns: " + num_columns_field.getText());
 System.out.println("Requested Rows   : " + num_rows_field.getText());

 maze_creating = true;
 maze_exists = false;

 // Get a pointer to the graphics.
 Graphics g = maze_canvas.getGraphics();
 // Clear screen.
 g.clearRect(0, 0, maze_canvas.getSize().width, maze_canvas.getSize().height);

 // Display the wait string.
 String str = new String("Creating maze, please wait...");
 FontMetrics fm = g.getFontMetrics();
 g.drawString( str,
          (maze_canvas.getSize().width  - fm.stringWidth(str)) / 2,
          (maze_canvas.getSize().height - fm.getHeight()     ) / 2 + fm.getAscent() );
 g.dispose();  // Free the pointer to graphics.

 try
 {
   num_columns = Integer.parseInt(num_columns_field.getText());
   num_rows = Integer.parseInt(num_rows_field.getText());
 }
 catch (Exception e)
 {
   System.out.println("Error: Invalid number or no number in rows or columns field.");
   num_columns = 50;
   num_rows = 50;
   num_columns_field.setText("50");
   num_rows_field.setText("50");
   System.out.println("Columns changed to: 50");
   System.out.println("Rows    changed to: 50");
 }

 // Check for bad values, num_columns and num_rows must be at least 1
 if (num_columns < 1)
 {
   System.out.println("Error: Invalid number in columns field.");
   num_columns = 1;
   num_columns_field.setText("1");
   System.out.println("Columns changed to: 1");
 }
 if (num_rows < 1)
 {
   System.out.println("Error: Invalid number in rows field.");
   num_rows = 1;
   num_rows_field.setText("1");
   System.out.println("Rows changed to: 1");
 }

 /* Set the values for the path_width, and path_height.  (Note that
    we take (num_columns + 2), and (num_rows + 2) because we want there to be
    1 path of blank space to either side of the maze) */

 path_width =  ( maze_canvas.getSize().width  / (num_columns + 2));
 path_height = ( maze_canvas.getSize().height / (num_rows    + 2));

 // Check for bad values, path_width and path_height must be at least 2
 if (path_width < 2)
 {
   path_width = 2;
     // recompute num_columns
   num_columns = (maze_canvas.getSize().width / 2) - 2;
   num_columns_field.setText(Integer.toString(num_columns));
   System.out.println("Error: Too many columns.");
   System.out.println("Columns changed to: " + num_columns);
 }
 if (path_height < 2)
 {
   path_height = 2;
     // recompute num_rows
   num_rows = (maze_canvas.getSize().height / 2) - 2;
   num_rows_field.setText(Integer.toString(num_rows));
   System.out.println("Error: Too many rows.");
   System.out.println("Rows changed to: " + num_rows);
 }

 // Initialize the arrays
 locations        = new boolean[num_columns][num_rows ];
 vert_path_colors = new int[num_columns][num_rows - 1];
 horz_path_colors = new int[num_columns - 1][num_rows];
 
 // Intialize the maze to have no paths.
 int i, j;
 for (i = 0; i < num_columns - 1; i++)
 {
   for (j = 0; j < num_rows - 1; j++)
   {
     vert_path_colors[i][j] = 0;
     horz_path_colors[i][j] = 0;
   }
   horz_path_colors[i][num_rows - 1] = 0;
 }
 for (j = 0; j < num_rows - 1; j++)
   vert_path_colors[num_columns - 1][j] = 0;

 // Add paths to the maze
 System.out.print("Calculating random maze... ");
 addPaths();
 System.out.println("done.");

 maze_creating = false;
 maze_exists = true;

 // Reset the locations for the begining of the game.
 int a, b;
 for (b = 0; b < num_rows; b++)
   for (a = 0; a < num_columns; a++)
     locations[a][b] = false;
 locations[0][0] = true;

 // Determine the offset values to center the maze.
 offset_x = (maze_canvas.getSize().width  - num_columns*path_width) / 2;
 offset_y = (maze_canvas.getSize().height - num_rows*path_height  ) / 2;

 // Print information about the maze.
 System.out.println("New maze created.");
 System.out.println("Stats: ");
 System.out.println("       Canvas dimensions : " + maze_canvas.getSize().width + " x " +
                    maze_canvas.getSize().height);
 System.out.println("       Maze dimensions   : " + num_columns*path_width + " x " +
                    num_rows*path_height);
 System.out.println("       Rows              : " + num_rows);
 System.out.println("       Columns           : " + num_columns);
 System.out.println("       Path width        : " + path_width);
 System.out.println("       Path height       : " + path_height);

 // Draw the maze.
 maze_canvas.repaint();

} // end reset()


/**
* Add paths to a maze that has just been initialized and does not 
* yet have any paths.
*/
void addPaths()
// Add paths to the maze
{
 /*   The array "partition_array" will help us keep track of which locations are connected by
    a series of paths.  Define partition_array[n] to be a node, for appropriate values of n.
      Then:
    partition_array[n][0] = k, where k is used as a reference to the node: partition_array[k].
    partition_array[n][1] = j.  When this node references itself, j is defined to be the
    maximum number of pointers that one needs to follow to get from any node "equivalent" to
    this one to reach this one, and determine that this one points to itself.  We don't care
    what j is when this node doesn't reference itself.
      Two nodes will be defined as "equivalent" when one node can be reached from the other
    by following a series of references from one to the other.  Our goal is to create the
    array such that two points in the maze are connected by a series of paths exactly when
    the nodes corresponding to them in partition_array are "equivalent".
      We want to group the nodes into equivalence classes, so that in each class there is
    exactly one node that references itself, and we can get to that node from all of the
    other nodes in the equivalence class. */
 int[][] partition_array = new int[num_columns * num_rows][2];
 
 int a, b; // temporary variables
 for (a = 0; a < num_columns * num_rows; a++)
 {
   partition_array[a][0] = a; // Make each node reference itself intially.
   partition_array[a][1] = 1; // Only 1 pointer needs to be followed to reach a node from
                              // itself.
 }
 
 // (num_columns * num_rows) - 1 is the number of paths that
 // need to be created so that all lattice points are
 // accessible.  It is also not possible to create any more
 // paths than this without creating a "loop" in the maze.
 boolean almostFinished = false; // Indicates that "most" of the maze is not finished.
 int pathTotal = (num_columns * num_rows) - 1; // Total paths the maze will have.
 int almostTotal = 15 * pathTotal / 16; // How many paths make "most" of the maze finished.
 int x1, y1, x2, y2; // Coordinates of points we're trying to connect.
 int paths = 0; // Number of paths cureently in the maze.

 while (paths < pathTotal)
 {
   // Add another path

   /* Pick any lattice point in the maze.  Then try to draw a path from it to a randomly
      selected adjacent point.  The only restriction is that you cannot connect two lattice
      points already connected by a series of paths, for this will result in a "loop". */
   if (paths < almostTotal)
   // If the maze is not yet close to complete,
   // choose paths randomly.
   {
     x1 = Math.abs(rand.nextInt() % num_columns);
     y1 = Math.abs(rand.nextInt() % num_rows);

     // Attempt to create a path from this point.
     a = 2 * Math.abs(rand.nextInt() % 2) - 1;
     b = 2 * Math.abs(rand.nextInt() % 2) - 1;
     x2 = x1 + (a + b) / 2;
     y2 = y1 + (a - b) / 2;

     if (addAPath(partition_array, x1, y1, x2, y2)) paths++;
   }
   else
   // At this point, we search for availible paths systematically rather than randomly.
   {
     x1 = 0;
     y1 = 0;
     int dx = 1; // x-direction of path.
     int dy = 0; // y-direction of path.
     int tx = 0; // temporary variable.
     int i;      // looping variable.

     for (x1 = 0; x1 < num_columns; x1++)
     {
       for (y1 = 0; y1 < num_rows; y1++)
       {
         x2 = x1 + dx;
         y2 = y1 + dy;

         for (i = 0; i < 4; i++)
         {
           if (addAPath(partition_array, x1, y1, x2, y2)) paths++;
           
           // Rotate clockwise
           tx = -dy;
           dy = dx;
           dx = tx;
         } // end for (for i = 0...
       } // end for (y1 = 0...
     } // end for (x1 = 0...