/*
MazeApplet.java 3.1

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

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.

This applet draws mazes based on various shaped tiles such as squares,
hexagons, or triangles.  A pulldown allows the user to select the shape and also
turn on or off a solution path.  The user can click his or her way through the
maze to try to solve it against a timer.  It requires the MazeTile class       
(distributed with this class or found at our website) to create the maze.
The two classes are usually placed in a common .jar file to allow for ease 
of use.

*/

import java.awt.*;
import java.awt.event.*;
import java.applet.*;
import java.util.Vector;


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

    MazeControls controls;   // The controls for drawing Mazes
    MazeCanvas canvas;       // The drawing area to display Mazes

    public void init() {
	setLayout(new BorderLayout());

	// Use the canvas that actually holds the maze.
	canvas = new MazeCanvas();
	canvas.init();

    // Put the canvas with the maze on top and the control panel on bottom.
	add("Center", canvas);
	add("South", controls = new MazeControls(canvas));
    }

    public void destroy() {
        remove(controls);
        remove(canvas);
    }

    public void start() {
	controls.setEnabled(true);
    }

    public void stop() {
	controls.setEnabled(false);
    }
  
    public void processEvent(AWTEvent e) {
        if (e.getID() == Event.WINDOW_DESTROY) {
            System.exit(0);
        }
    }

    public static void main(String args[]) {
	Frame f = new Frame("MazeApplet");
	MazeApplet	MazeApplet = new MazeApplet();

	MazeApplet.init();
	MazeApplet.start();

	f.add("Center", MazeApplet);
	f.setSize(300, 300);
	f.show();
    }

    public String getAppletInfo() {
        return "An interactive test of the Graphics.drawMaze and \nGraphics.fillMaze routines. Can be run \neither as a standalone application by typing 'java MazeApplet' \nor as an applet in the AppletViewer.";
    }
}

// The MazeCanvas actually holds the maze made of MazeTiles and handles clicks as user tries 
// to navigate the maze.
class MazeCanvas extends Panel implements MouseListener, MouseMotionListener {
  MazeTile firstTile;
  MazeTile startTile;
  MazeTile endTile;
  Vector theSolution;
  Color fgColor = Color.blue;     // Color of maze walls (default blue)
  Color bgColor = Color.white;    // Color for maze background (default white)
  Color solColor = Color.red;     // Color for solution & labels (default red)
  Color pathColor = Color.pink;   // Color of tiles the user is stepping through
  Color visitColor = Color.lightGray; // Color of tiles the user has visited

  boolean	newMaze = false;      // Flags request to make new maze
  boolean	solveMaze = false;    // Flags request to draw solution
  String mazeShape                // Shape of the maze
     = new String("Square");
  String oldMazeShape             // Shape of last maze drawn
     = new String("Square");

  Vector userPath;

  boolean thePath[];      // The path a user has navigated through the maze
  boolean visitedTiles[]; // All tiles a user has clicked on
  boolean mazeSolved = false;
  static long startTime, endTime;


  // Create an init() method to set up mouse listeners.
  public void init() 
    {
    addMouseListener(this);
    addMouseMotionListener(this);
    }

  // Override the destroy() method to remove mouse listeners.
  public void destroy()
    {
    removeMouseListener(this);
    removeMouseMotionListener(this);
    }

  public void paint(Graphics g) {
	Rectangle r = getBounds();
	int     i, j;                // Ubiquitous counter variables
	Point   p1, p2;              // Points for plotting maze solution
	boolean heterogenous = false; // Indicates heterogenous tile shapes
	Vector polyVector = new Vector();  // Vector of polygons for heterogenous tiles

	// See if a new maze is requested
	if(newMaze || firstTile == null)
	  {
  	  Polygon tileShape = new Polygon();

      // First, see if a new maze must be allocated
	  if(firstTile == null || !oldMazeShape.equalsIgnoreCase(mazeShape))
	    {
		// New maze is requested - start making the new tile shape
        if (mazeShape == null || mazeShape.equalsIgnoreCase("square"))
    	  {
          // By default, make square shaped tiles 
          tileShape.addPoint( 20, 20); // Northeast 
    	  tileShape.addPoint(-20, 20); // Southeast 
    	  tileShape.addPoint(-20,-20); // Southwest 
    	  tileShape.addPoint( 20,-20); // Southeast 
    	  }
    	else if ( mazeShape.equalsIgnoreCase("small squares") )
    	  {
          // Now, make a diamond shaped tile 
          tileShape.addPoint( 10, 10); // Northeast 
    	  tileShape.addPoint(-10, 10); // Southeast 
    	  tileShape.addPoint(-10,-10); // Southwest 
    	  tileShape.addPoint( 10,-10); // Southeast 
    	  }
    	else if ( mazeShape.equalsIgnoreCase("diamond") )
    	  {
          // Now, make a diamond shaped tile 
          tileShape.addPoint( 20,  0); // North 
    	  tileShape.addPoint(  0, 20); // East 
    	  tileShape.addPoint(-20,  0); // South 
    	  tileShape.addPoint(  0,-20); // West 
    	  }
        else if ( mazeShape.equalsIgnoreCase("hex") )
    	  {
          // Make hex shaped tiles 
          tileShape.addPoint( 17, 10); // Northeast 
          tileShape.addPoint(  0, 20); // North 
          tileShape.addPoint(-17, 10); // Northwest 
          tileShape.addPoint(-17,-10); // Southwest 
          tileShape.addPoint(  0,-20); // South 
          tileShape.addPoint( 17,-10); // Southeast 
    	  }
        else if ( mazeShape.equalsIgnoreCase("Butterfly") )
    	  {
          // Make Butterfly shaped tiles 
          tileShape.addPoint( 20, 20); // Northeast 
          tileShape.addPoint(  0, 10); // North 
          tileShape.addPoint(-20, 20); // Northwest 
          tileShape.addPoint(-20,-20); // Southwest 
          tileShape.addPoint(  0,-10); // South 
          tileShape.addPoint( 20,-20); // Southeast 
    	  }
        else if ( mazeShape.equalsIgnoreCase("Triangles")
               || mazeShape.equalsIgnoreCase("Small Triangles") )
    	  {
          // Mark tiles as having different shapes or orientations
		  heterogenous = true;
          int triangleWidth;
		  int triangleHeight;
          if(mazeShape.equalsIgnoreCase("Small Triangles"))
		    {
            triangleWidth=10;
            triangleHeight=17;
			}
		  else
		    {
            triangleWidth=20;
            triangleHeight=34;
			}

          // Because maze is heterogeneous, we can't just make one shape
		  // and ask MazeTile to duplicate it.  Instead, we need to make list
		  // of all shapes and pass that to MazeTile.
          // Make maze containing triangle polygons.  Create
          // two baseline triangles - one pointing up and the other down
          Polygon upTriangle = new Polygon();
          upTriangle.addPoint(((r.x+r.width)/2),       0); // Top 
          upTriangle.addPoint((((r.x+r.width)/2) - triangleWidth), triangleHeight); // Left 
          upTriangle.addPoint((((r.x+r.width)/2) + triangleWidth), triangleHeight); // Right 

          Polygon dnTriangle = new Polygon();
          dnTriangle.addPoint(((r.x+r.width)/2),      (triangleHeight*2)); // Bottom
          dnTriangle.addPoint((((r.x+r.width)/2) - triangleWidth), triangleHeight); // Left 
          dnTriangle.addPoint((((r.x+r.width)/2) + triangleWidth), triangleHeight); // Right 

          // Create triangles one row at a time
		  boolean done = false;
		  for(i=0; ;i++)
		    {
			// t1 and t2 are working copies of upTriangle and dnTriangle, respectively
			Polygon t1 = new Polygon(upTriangle.xpoints, 
			  upTriangle.ypoints, upTriangle.npoints);
			t1.translate(-i*triangleWidth, i*triangleHeight);
			Polygon t2 = new Polygon(dnTriangle.xpoints, 
			  dnTriangle.ypoints, dnTriangle.npoints);
			t2.translate(-i*triangleWidth, i*triangleHeight);
			
			// Check to see if t1 and t2 fit inside bounding rectangle r.
			if( ((i+1)*triangleWidth*2) >= r.width )
			  break;  // We've run out of width
			else if ( ((i+1)*triangleHeight) >= r.height )
			  break;  // We've run out of height

			// Now, add each triangle to the list for the maze
			for(j=0; j<i; j++)
			  {
              // Create upwards pointing triangle
			  polyVector.addElement(new Polygon(t1.xpoints, 
			    t1.ypoints, t1.npoints));

              // See if a downward pointing triangle will fit (it won't on
			  // the last pass)
			  if( ((i+2)*triangleHeight) < r.height )
			    {
			    polyVector.addElement(new Polygon(t2.xpoints, 
			      t2.ypoints, t2.npoints));
				}

              // Now, shift t1 & t2 over for the next tiles
			  t1.translate(triangleWidth*2,0);
			  t2.translate(triangleWidth*2,0);
			  }
			} /* i loop */
    	  }  /* Triangle if() */


        // Allocate the maze, using the appropriate method for the tile shapes
        if(heterogenous)
		  firstTile = MazeTile.AllocateMaze(polyVector);
		else
          firstTile = MazeTile.AllocateMaze(tileShape, r);
		
		// Store away the current tile shape
		oldMazeShape = mazeShape;

		// Force new maze to be drawn
		newMaze = true;
		}

    // Now, actually create paths in the maze
    firstTile.constructMaze();

    // Find the maze's solution
	startTile = firstTile.corner("lt"); // Left, topmost tile
	endTile = firstTile.corner("rb");   // Right, bottommost tile
	theSolution = firstTile.solve(startTile, endTile);

    // Set up a path for the user to navigate and list of visited tiles
    userPath = new Vector();
    visitedTiles = new boolean[firstTile.theMaze.size()];

    // Indicate new maze has yet to be solved by user
	mazeSolved = false;
    
    // Reset flag for new maze requests
    newMaze = false;
	}


  // If the maze has been solved, put up a message to that effect
  if(mazeSolved)
    {
    // Tell the user how they did
    g.setColor(solColor);
    if(solveMaze)
	  {
	  // They used the "draw solution" button.
      drawCenter(g, "Cheating with the 'solve' button, you completed the maze in "+ 
        (endTime-startTime)/1000 +" seconds.",
        new Point( (r.x+r.width)/2, (r.height+r.y)/2) );
	  }
	else
	  {
	  // They didn't cheat with the "draw solution" button.
      drawCenter(g, "Congratulations!  You have completed the maze in "+ 
        (endTime-startTime)/1000 +" seconds.",
        new Point( (r.x+r.width)/2, (r.height+r.y)/2) );
	  }
	}
  else
    {
	// Maze not solved - draw it and user's path
	// Clear the rectangle
    g.setColor(bgColor);
	g.fillRect(r.x, r.y, r.width, r.height);

    // Draw the path the user has taken through the maze
    for (i=0; i<firstTile.theMaze.size(); i++)
  	  {
  	  if(userPath.indexOf(firstTile.theMaze.elementAt(i)) != -1)
  	    {
  	    // Shade the polygon to indicate it is part of the path
        g.setColor(pathColor);
  	    g.fillPolygon(( (MazeTile)(firstTile.theMaze.elementAt(i)) ).TilePoly);
		}
	  else
	    {
		if(visitedTiles[i])
		  {
  	      // Shade the polygon to indicate it has been visited
          g.setColor(visitColor);
  	      g.fillPolygon(( (MazeTile)(firstTile.theMaze.elementAt(i)) ).TilePoly);
		  }
		}
  	  }

	// Draw the maze
	firstTile.paint(g, fgColor);

    // Draw start and end labels
    g.setColor(solColor);
    drawCenter(g, "start",startTile.Center);
    drawCenter(g, "end",endTile.Center);

    // Draw the solution if requested
	if (solveMaze)
	  {
      g.setColor(solColor);
      for (i=1; i<theSolution.size(); i++)
  	    {
  	    p1 = ( (MazeTile)(theSolution.elementAt(i-1)) ).Center;
  	    p2 = ( (MazeTile)(theSolution.elementAt(i)) ).Center;
  	  
  	    // Draw a line from cell to cell
        g.drawLine(p1.x, p1.y, p2.x, p2.y);
  	    }
      }
	}
  }

    public void redraw(boolean newMaze, 
                       boolean solveMaze, 
                       String mazeShape) {
	this.newMaze = newMaze;
	this.solveMaze = solveMaze;
	this.mazeShape = mazeShape;
	repaint();
    }


  // A convenient method for drawing labels centered within a maze tile
  void drawCenter(Graphics g, String s, Point p)
    {
	int hShift = g.getFontMetrics().stringWidth(s)/2;
    int vShift = (g.getFontMetrics().getDescent() 
                  - g.getFontMetrics().getAscent())/2;
				   
	g.drawString(s, p.x - hShift, p.y - vShift);
    }    

  // Create a method to handle navigation through the maze,
  // called on a mouseRelease() or a mouseDrag()
  // Find what mazeTile (if any) was clicked and mark
  // the user's path as appropriate.
  void navigateMaze(MouseEvent e)
    {
    Point p = new Point(e.getPoint());
    boolean leftButtonPush =
      (e.getModifiers()&java.awt.event.InputEvent.BUTTON1_MASK) != 0;
    boolean centerButtonPush =
      (e.getModifiers()&java.awt.event.InputEvent.BUTTON2_MASK) != 0;
    boolean rightButtonPush =
      (e.getModifiers()&java.awt.event.InputEvent.BUTTON3_MASK) != 0;

    int x = e.getX();
    int y = e.getY();
	int i, j;
	int tileIndex;   // Used to index MazeTiles in thePath vectors
	boolean repaintMaze = false;
	
    // Find the clicked tile
    MazeTile clickedTile = firstTile.contains(p);

    // See if the clicked tile should be added to the path
    if (clickedTile != null && leftButtonPush)
      {
      // Find index into boolean array for clicked tile
      tileIndex = firstTile.theMaze.indexOf(clickedTile);
      
      // Now, see if there user has ever navigated this maze
	  if(userPath.size() == 0)
	    {
		// This is the first time the user has clicked.  If it was 
		// on the start tile, add it to the path
		if(clickedTile == startTile)
		  {
          // Add the clicked tile to path	  
		  userPath.addElement(clickedTile);

		  // Indicate tile has been visited
		  visitedTiles[tileIndex]=true;
		  
		  // Record the start time for user trying the maze
		  startTime = System.currentTimeMillis();
		  
		  // Request a repaint of the maze
		  repaintMaze = true;
		  }
		}
      else
	    {
		// Not the first click - see if the user wanted to backtrack
		// along the already marked path
		i = userPath.indexOf(clickedTile);
		if(i != -1)
		  {
		  // The clicked tile was on the path.  Backtrack.
		  while(userPath.lastElement() != clickedTile)
		    {
            // Remove the tile from the path
		    userPath.removeElementAt(i+1);

            // Request a repaint of the maze
            repaintMaze = true;
		  	}
		  }
		else
		  {
		  // Not a backtrack.  If a neighbor of the last tile in the
		  // marked path, the user wants to add it to the path.
		  for(i=0; i<(clickedTile.TilePoly.npoints); i++)
		    {
			if(clickedTile.Neighbor[i] == userPath.lastElement() && 
			   clickedTile.pathToNeighbor[i])
			  {
			  // Yes - the clicked tile is adjacent to the last tile
			  // in the marked path
			  userPath.addElement(clickedTile);

			  // Indicate tile has been visited
			  visitedTiles[tileIndex]=true;

              // Request a repaint of the maze
              repaintMaze = true;
              
              // Finally, see if the user has completed the maze
			  if(clickedTile == endTile)
			    {
				// Success
				mazeSolved = true;
				
				// Record the start time for user trying the maze
				endTime = System.currentTimeMillis();
				}

			  break;
			  }
			}
		  }
		}

      // Check if a repaint of the maze is in order
      if(repaintMaze)
        repaint();
      }
	}

  // On a mouseclick, navigate the maze
  public void mouseReleased(MouseEvent e) 
    {
	navigateMaze(e);
	}

  // Set up an empty mouseMoved() method
  public void mouseMoved(MouseEvent e)
    {
	}

  // On a mouse drag, navigate the maze
  public void mouseDragged(MouseEvent e) 
    {
	navigateMaze(e);
    }

  public void mousePressed(MouseEvent e) 
    {
    }

  public void mouseClicked(MouseEvent e) 
    {
    }

  public void mouseEntered(MouseEvent e) 
    {
    }

  public void mouseExited(MouseEvent e) 
    {
    }
}

// Make the panel with the controls on it to select the maze shape and buttons
// to solve the maze or draw a new maze.
class MazeControls extends Panel
                  implements ActionListener {
    TextField s;
    TextField e;
	Choice shapeChoice;
    MazeCanvas canvas;

    public MazeControls(MazeCanvas canvas) {
	Button b = null;

	this.canvas = canvas;
	b = new Button("New Maze");
	b.addActionListener(this);
	add(b);
	b = new Button("Solve");
	b.addActionListener(this);
	add(b);

	// Make sure these selections match the strings in MazeCanvas.paint()
    shapeChoice = new Choice();
    shapeChoice.add("Square");    // Square is default - put it first in the menu
    shapeChoice.add("Small Squares");
    shapeChoice.add("Hex");
    shapeChoice.add("Diamond");
    shapeChoice.add("Butterfly");
    shapeChoice.add("Triangles");
    shapeChoice.add("Small Triangles");
    add(shapeChoice);
    }

    public void actionPerformed(ActionEvent ev) {
	String label = ev.getActionCommand();

	canvas.redraw(label.equals("New Maze"),
	              label.equals("Solve"),
	              shapeChoice.getSelectedItem());
    }
}