/*
MazeTile.java 3.1

Written by Kevin N. Haw and JoAnn K. Haw, www.thehaws.org.  
Please mail comments via the link at our website.

Implements maze drawing in Java, 1.1 (to support older versions of 
Netscape and IE).

All contents copyright 2000-2005 by Kevin N. Haw and JoAnn K. Haw.  The authors 
grant permission to freely distribute and modify this program as long as this
copyright notice and all copyright notices embedded in the program 
remain intact.

MazeTile
This class serves as a building block for mazes.  Each tile is a polygon
that is fitted together with other tiles.  Sides from each tile are removed
to form paths in the maze.  Sides left intact for the maze's walls.

Tiles (currently) have the following restrictions:
1) All tiles must be homogeneous.  That is, each tile must have same shape 
   and orientation as all others.
  1a) As a result, only 4 and 6 sided polygons can be used.
2) Edges between tiles are single, straight line segments.
  2a) Each tile is defined by a polygon.


To use:
First, the caller invokes the static method MazeTile.AllocateMaze() with a
boundary rectangle and a polygon to use as a template for the tiles.  A MazeTile
is returned.  The user then invokes constructmaze() on that MazeTile every time
that a new maze is to be created.  Additional methods solve the maze, paint it,
determine what tile contains a given point, or find the corner tiles of the maze.

*/


import java.awt.*;
import java.awt.event.*;

import java.awt.Graphics;
import java.util.Vector;
import java.awt.Point;
import java.awt.Rectangle;
import java.io.PrintStream;
import java.awt.Color;
import java.awt.Polygon;
import java.applet.AppletContext;
import java.net.URL;
import java.lang.Thread;

class MazeTile  
  {
  // Copyright and version data
  public static String copyMsg = "MazeTile: Copyright Kevin N. Haw and JoAnn K. Haw, 2000-2005.";
  public static String verMsg = "MazeTile v 3.1";
  public static int verno = 0x300100;   // Byte0=revision, byte1= minor version, byte2= major version

  // Define variables to manage an entire maze 
  Vector theMaze;              // List of all MazeTiles in this maze

  // Define data for each instance of the class 
  Point Center;
  Polygon TilePoly;                          // This tile's polygon
  MazeTile Neighbor[];                       // Array of references to neighboring tiles.
                                             //   NULL indicates maze boundary
  boolean pathToNeighbor[];                  // TRUE if neighbor has path, FALSE
                                             //   if blocked by a wall
  boolean tileMapped;                        // Working variable for maze creation and solving




  // This constructor creates a maze tile, not connected to any neighbors.
  MazeTile(Polygon poly,                     // Shape of tile
    Vector maze)                             // Maze this tile is part of
    {
	int i;
	int sumX=0, sumY=0;         // Used to calculate tile center

	// Record the tile's shape
	TilePoly = poly;

    // Allocate arrays to express tile's relationship with neighbors
    Neighbor = new MazeTile[TilePoly.npoints];
	pathToNeighbor = new boolean[TilePoly.npoints];

    // Sum and average the points in the polygon to find the center
    for(i=0; i<TilePoly.npoints; i++)
	  {
	  sumX = sumX + TilePoly.xpoints[i];
	  sumY = sumY + TilePoly.ypoints[i];
	  
	  // While we're looping, initialize arrays
	  pathToNeighbor[i] = false;
	  Neighbor[i] = null;
	  }
    Center = new Point(sumX/TilePoly.npoints, sumY/TilePoly.npoints);

	// Reference the maze and make this tile a member of it
	theMaze = maze;
	theMaze.addElement(this);
	}



  // This constructor creates a maze tile and (recursively) all its neighbors,
  // linking them together.  Many of the temporary  variables required to do
  // this are passed as parameters so they will not persist once the maze has been
  // constructed.
  MazeTile(Point p,             // center point of new tile
    int parentIndex,            // index into parent's neighbor[] array
    Vector tileListVector,      // List of all MazeTiles 
    Vector tileListPointVector,	// List of MazeTiles center points
    Polygon masterTilePoly,		// Shape of tile centered on (0,0)
    Polygon neighborOffset,		// Center of each neighbor tile 
    Rectangle bounds)			// Boundaries to draw maze 
    {
    int i, j;                   // Ubiquitous counter variables
	int TileListIndex;          // Index into vectors of tiles and center points
	Point p2 = new Point();     // Center point of new (neighbor) tile

    // Reference the master list of tiles that form this maze
	theMaze = tileListVector;

	// Add this tile to the master tile list 
    theMaze.addElement(this);

	// Add center point for this tile to the master point list 
    tileListPointVector.addElement(new Point(p));

    // Log center of this tile 
	Center = new Point(p);

    // Indicate this tile is not yet part of the maze 
	tileMapped = false;

    // Set up the polygon for this tile, based on master polygon 
    TilePoly = new Polygon(masterTilePoly.xpoints,
      masterTilePoly.ypoints, masterTilePoly.npoints);
	TilePoly.translate(p.x, p.y);   // Move to location centered on p 

    // Set up structures that reference neighbor tiles so
	//   they will be the right size
    Neighbor = new MazeTile[TilePoly.npoints];
	pathToNeighbor = new boolean[TilePoly.npoints];

    // Now, go through all the neighbors and define the tiles for them 
	for(i=0; i<TilePoly.npoints; i++)
	  {
	  // Initialize so no paths to neighbor tiles exist 
	  pathToNeighbor[i] = false;

	  // Set p2 to center of neighbor polygon i 
	  p2.setLocation(p);
	  p2.translate( neighborOffset.xpoints[i], neighborOffset.ypoints[i]);
	  
	  /* If p2 is in the maze boundaries and has not had a tile created for it,
	     make a tile. */
	  if(bounds.contains(p2))
	    {
	    // Neighbor would be within maze boundaries.  See if it exists
	    //   yet or if it should be created now.
	    TileListIndex = tileListPointVector.indexOf(p2);
	    if( TileListIndex == -1) 
  	      {
		  // Neighbor does not yet exist - create it
		  Neighbor[i] = new MazeTile(p2, 	//  p
	        tileListPointVector.indexOf(p),	//  parentIndex
            tileListVector,					//  tileListVector
            tileListPointVector,			//  tileListPointVector
            masterTilePoly,					//  masterTilePoly
            neighborOffset,					//  neighborOffset
            bounds);						//  bounds
		  }
        else
		  {
		  // Neighbor exists - reference it 
		  Neighbor[i] = (MazeTile)theMaze.elementAt(TileListIndex);
		  }
        }
      else
	    {
		// Neighbor would be outside boundaries - null out the reference
		Neighbor[i] = null;
		}
	  }
	}

  // Create a routine to allocate the tiles in a maze when they are homogenous
  // (all shaped and facing the same way).  It sets up temporary maze management
  // variables, calls the recursive constructor above, and finally returns the
  // first mazeTile in the maze.  ConstructMaze() may then be called to actually create the
  // paths in the maze.
  //  poly - polygon for the shape of the MazeTiles
  //  r - boundaries within which to draw the maze
  public static MazeTile AllocateMaze(Polygon poly, Rectangle r)
    {
    int i;
	Point NewPoint = new Point();
	MazeTile firstTile;

    // Allocate temporary maze management variables.  They will be referenced
	// locally for each new tile in its constructor.
	Vector tileListVector = new Vector();     
	Vector tileListPointVector = new Vector();
	Polygon masterTilePoly = 			 // Record the shape of all tiles
	  new Polygon(poly.xpoints, poly.ypoints,  poly.npoints);
    Polygon neighborOffset = new Polygon();
    Rectangle bounds = new Rectangle(r); // Start boundaries at drawing bounds

    // Now, shrink the boundaries to fit the edges of the tile polygons 
    bounds.grow(-( poly.getBounds().width ), -( poly.getBounds().height ));

    // Calculate the center of neighbor tiles.  Since the tiles
    // are homogenous, neighbor i is located at the sum of the vectors
    // for the polygon's points (i and i+1)
	for(i=0; i<masterTilePoly.npoints; i++)
	  {
      // Start with vertex i 
	  NewPoint.setLocation(masterTilePoly.xpoints[i], 
	    masterTilePoly.ypoints[i]);

      if(i == (masterTilePoly.npoints - 1) )
	    {
		// Last vertex in polygon.  Use first (0) vertex as i+1 
		NewPoint.translate(masterTilePoly.xpoints[0], 
		  masterTilePoly.ypoints[0]); 
		}
      else
	    {
		// Not last vertex in polygon.  Use vertex i+1 
		NewPoint.translate(masterTilePoly.xpoints[i+1], 
		  masterTilePoly.ypoints[i+1]); 
		}

      // Add new point to represent neighbor i tile's center 
	  neighborOffset.addPoint(NewPoint.x, NewPoint.y);
	  }

    // Static variables initialized.  Call recursive constructor at 
    //  center of boundary box
    NewPoint.setLocation(bounds.getLocation());
	NewPoint.translate(bounds.width/2, bounds.height/2);
    firstTile = 
    new MazeTile(NewPoint, //  p
      -1,				   //  parentIndex
      tileListVector,	   //  tileListVector
      tileListPointVector, //  tileListPointVector
      masterTilePoly,	   //  masterTilePoly
      neighborOffset,	   //  neighborOffset
      bounds);			   //  bounds

    // Success
	return(firstTile);
    }






  // Create a routine to allocate the tiles in a maze when they are heterogenous.
  // Basically, match each edge of each polygon to its neighbor and then set up
  // the proper references before returning the first mazeTile in the maze. 
  // ConstructMaze() may then be called to actually create the paths in
  // the maze.
  //  thePolygons - the polygons that should be made into linked MazeTiles
  public static MazeTile AllocateMaze(Vector thePolygons)
    {
    int i, j, k;
	MazeTile firstTile;
	Vector edgeList = new Vector();       // Used to figure out which polygons are neighbors
	Vector edgeIndex = new Vector();	  // Tracks how edges relate to their polygon tiles
	Vector tileList = new Vector(); 	  // Tracks matching MazeTiles
	Vector tileIndexList = new Vector();  // Tracks matching MazeTiles by index
	Polygon currentPoly;
	Rectangle currentEdge;
	MazeTile currentTile = null;
	Vector tileListVector = new Vector();  // Working reference to theMaze
	
	// Loop through all polygons in thePolygons
	for(i=0; i<thePolygons.size(); i++)
	  {
      // Get a working reference to the polygon
	  currentPoly = (Polygon)thePolygons.elementAt(i);

      // Create a mazeTile at the appropriate location for this polygon
	  currentTile = new MazeTile(currentPoly, tileListVector);

      // Loop through all the edges of this polygon
	  for(j=0;j<currentPoly.npoints;j++)
	    {


		// Create a two point polygon describing this edge of the tile
		currentEdge = 
		  new Rectangle(new Point(currentPoly.xpoints[j],currentPoly.ypoints[j]));
		currentEdge.add(
		  currentPoly.xpoints[(j+1)%currentPoly.npoints],
		  currentPoly.ypoints[(j+1)%currentPoly.npoints]);

        // Now, see if the edge is already in edgeList vector (indicatring that another MazeTile
		// shares this edge)
        k = edgeList.indexOf(currentEdge);
        if( k != -1)
          {
		  // There was a match, indicating two tiles are
		  // neighbors.  Cross reference them.
          MazeTile otherTile = (MazeTile)tileList.elementAt(k);
		  int otherIndex = ((Integer)edgeIndex.elementAt(k)).intValue();
		  currentTile.Neighbor[j] = otherTile;
		  otherTile.Neighbor[otherIndex] = currentTile;

          // Remove the edge from our lists
		  edgeList.removeElementAt(k);
		  edgeIndex.removeElementAt(k);
		  tileList.removeElementAt(k);
          }
		else
		  {
		  // There was no match - add the edge to the master list
		  edgeList.addElement(currentEdge);
		  edgeIndex.addElement(new Integer(j));
		  tileList.addElement(currentTile);
		  }
		
		}
	  }

    // Success
	return(currentTile);
    }








  // This routine builds the paths in an a maze already allocated via AllocateMaze(), above.
  // It marks all tiles in the maze as unmapped and then calls the recursive
  // constructMaze() (below) for each tile to actually build the paths.
  public void constructMaze()
    {
	int i,j;

	// Step through all tiles in theMaze and mark them as unmapped.
    for (i=0; i<theMaze.size(); i++)
	  {
	  ((MazeTile)theMaze.elementAt(i)).tileMapped = false;
	  }

	// Now call recursive construction routine to build maze
    this.constructMaze(-1);
	}

  // This recursive method sets up the paths for a maze tile, calling itself
  // for any neighbors not yet visited
  public void constructMaze(int parentRef)
    {
	Vector possiblePathList = new Vector();
	Vector pathDirectionList = new Vector();
	MazeTile theTile;
	int theDirection;
	int neighborDirection = -1;
	int i, j;

	// Mark this tile as mapped
	tileMapped = true;

    // Check all neighbors and see which have yet to be visited
	for(i=0; i<TilePoly.npoints; i++)
	  {
	  // As long as we're here, erase any previous paths
      pathToNeighbor[i] = false;

	  // If neighbor does not exist (eg: it's outside maze 
	  // boundaries), skip to next neighbor
	  if (Neighbor[i] == null)
	    continue;

      // Neighbor exists - see if it is mapped yet
	  if (Neighbor[i].tileMapped == false)
	    {
		// Neighbor not mapped yet - add it to the list of paths
		possiblePathList.addElement(Neighbor[i]);
		pathDirectionList.addElement(new Integer(i));  // Record which way the path is
		}
	  }

    // We now have a list of neighboring tiles that are not yet
	// part of the maze.  Pick one at random and create a path
	// to it.  Loop through all of them.
	while(possiblePathList.size() > 0)
	  {
	  // Pick a tile at random
	  i = (int) (possiblePathList.size() * Math.random());

      // Get a reference to the tile
      theTile = (MazeTile)possiblePathList.elementAt(i);
	  theDirection = ((Integer)pathDirectionList.elementAt(i)).intValue();

	  // If the tile is still not part of the maze, create a path to it
	  if(Neighbor[theDirection].tileMapped == false)
	    {
	    // Mark the path
        pathToNeighbor[theDirection] = true;

		// For the next step, we need to be able to tell the neighbor who
		// its parent is (this tile) and in what direction it lies.  To do
		// this, loop through the neighbor's references to its neighbors 
		// until we see a reference back to this tile.
		for(j=0; j<Neighbor[theDirection].TilePoly.npoints; j++)
		  {
		  // See if this edge of the neighbor's tile points back at us
		  if(Neighbor[theDirection].Neighbor[j] == this)
		    {
			// It does.  Record it.
			neighborDirection = j;
			break;
			}
		  }

 		// Now recursively travel the path to the neighbor, telling it this tile
 		// is the parent.  The recursion will all paths from there to the rest 
 		// of the maze.
	    Neighbor[theDirection].constructMaze(neighborDirection);
		}

      // Remove this path from the list of possible paths
      possiblePathList.removeElementAt(i);
	  pathDirectionList.removeElementAt(i);
	  }


    // Manually mark the parent tile (the one that recursively 
    // branched to this one) as having a path here.  The loops above
	// would not have done this because it had already been mapped 
	// when the loop executed.
	if(parentRef != -1)
	  pathToNeighbor[parentRef] = true;

	}


  // Routine to indicate which tile has been selected at a given point (used
  // with mouse clicks primarily)
  public MazeTile contains(Point p)
    {
    int i;

	// Step through all tiles in theMaze 
	// and see if any of them contain the point.
    for (i=0; i<theMaze.size(); i++)
	  {
      // Check the point against the tile's bounding polygon
	  if ( ((MazeTile)theMaze.elementAt(i)).TilePoly.contains(p) )
	    {
		// We have a match!
		return((MazeTile)theMaze.elementAt(i));
		}
	  }

    // No match.  Return null reference.
	return(null);
	}


  // This method returns which tile is in which corner of the maze.
  // To indictae which corner, the user passes in one of the following:
  //     "LT" - Left, top
  //     "RT" - Right, top
  //     "LB" - Left, bottom
  //     "RB" - Right, bottom
  //     
  public MazeTile corner(String pDirection)
    {
    int i;
	String direction = new String (pDirection);
	boolean leftMost = false;    // True if user wants the leftmost tile
	boolean rightMost = false;   // True if user wants the rightmost tile
	boolean topMost = false;     // True if user wants the topmost tile
	boolean bottomMost = false;  // True if user wants the bottommost tile
	MazeTile theTile;            // Working variable for looping through tiles
	MazeTile cornerTile;         // The current candidate for the corner tile

    // Convert parameter string to lower case
	direction = direction.toLowerCase();

	// Check for leftmost string "L"
	if (direction.indexOf('l') != -1)
	  leftMost = true;

	// Check for rightmost string "R"
	if (direction.indexOf('r') != -1)
	  rightMost = true;

	// Check for topmost string "T"
	if (direction.indexOf('t') != -1)
	  topMost = true;

	// Check for bottommost string "B"
	if (direction.indexOf('b') != -1)
	  bottomMost = true;

    // Start by looking at the first tile in the maze
    cornerTile = (MazeTile)theMaze.firstElement();

	// Step through remaining tiles in theMaze 
	// and see if any is the corner.
    for (i=1; i<theMaze.size(); i++)
	  {
      // Set up working variable
      theTile = (MazeTile)theMaze.elementAt(i);

      // Check horizontal (or no preference)
	  if(  (leftMost && (cornerTile.Center.x >= theTile.Center.x) ) 
	   || (rightMost && (cornerTile.Center.x <= theTile.Center.x) ) 
	   || (leftMost==false && rightMost==false) )
	    {
		// We are at the horizontal extreme - check the vertical
	    if(    (topMost && (cornerTile.Center.y >= theTile.Center.y) ) 
	     || (bottomMost && (cornerTile.Center.y <= theTile.Center.y) )  
	     || (topMost==false && bottomMost==false) )
		   {
		   // Corner found
		   cornerTile = theTile;
		   }
		}
	  }

    // Return corner tile.
	return(cornerTile);
	}


  // Recursive routine calculates the path to a given tile
  Vector solve(MazeTile end)
    {
    int i;
	Vector theSolution;

    // Mark this tile as being visited for finding the solution
	tileMapped = true;

	// Determine if this tile is the endpoint for the solution search
	if (this == end)
	  {
	  // Solution is found - return the solution, adding this tile to it
	  theSolution = new Vector();
	  theSolution.addElement(this);
	  return (theSolution);
	  }

    // This tile is not the solution.  Keep looking, searching
    // each of the neighboring tiles.
	for(i=0; i<TilePoly.npoints; i++)
	  {
      // If there is not a neighbor in this direction (eg: maze edge)
	  // or if the neighbor is not accesible (there's a wall),
	  // then skip to next side.
	  if(Neighbor[i] == null || pathToNeighbor[i] == false)
	    continue;

      // If this neighbor has not yet been visited, check it out
	  if(!Neighbor[i].tileMapped)
	    {
		// Recursively check the neighbor
		if( (theSolution = Neighbor[i].solve(end)) != null)
		  {
		  // Solution was found - add this tile to it and exit
          theSolution.addElement(this);
	      return (theSolution);
		  }
		}
	  }

	// Solution not found.  This is a dead end.  Let caller know.
	return(null);
	}


  // Method calculates the path between two MazeTiles
  // in the same maze.  It allocates and returns a Vector
  // with a list of tiles forming the solution.  A null
  // returned indicates no path.
  // This method can be called via any tile in the maze.
  public Vector solve(MazeTile start, MazeTile end)
    {
    int i;

	// Begin by marking all tiles as unvisited.
    for (i=0; i<theMaze.size(); i++)
	  {
	  ((MazeTile)theMaze.elementAt(i)).tileMapped = false;
	  }

    // Now, call recursive routine to build a solution.
	return(start.solve(end));
	}

  // Draw one tile with the pen already set.
  void DrawTile(Graphics g)
    {
    int i;

    // Draw edges for tile 
	for(i=0; i<TilePoly.npoints; i++)
	  {
	  // Mark edge with color indicating connection to neighbor 
	  if(pathToNeighbor[i] == false)
	    {
        // Draw the line to mark the edge 
        if(i == (TilePoly.npoints - 1) )
          {
          // Last line in polygon - wrap back to point zero 
          g.drawLine(TilePoly.xpoints[i], TilePoly.ypoints[i], 
                     TilePoly.xpoints[0], TilePoly.ypoints[0]);
  	  	  }
        else
          {
          // Not last line - draw between i & i+1 
          g.drawLine(TilePoly.xpoints[i],   TilePoly.ypoints[i], 
                     TilePoly.xpoints[i+1], TilePoly.ypoints[i+1]);
  	  	  }
		}
	  }
    }

  // Draw all tiles in the given pen color.
  public void paint(Graphics g, Color fgColor) 
    {
	int i,j;
    MazeTile ThisTile;

    // Draw maze in specified color 
    g.setColor(fgColor);

    // Draw each tile 
    for (i=0; i<theMaze.size(); i++)
	  {
      ThisTile = (MazeTile)theMaze.elementAt(i);
	  ThisTile.DrawTile(g);
	  }
	}
  }