/*****************************************************************************
Programmer:     Dave Kush

Date:           Tue Oct  2 11:49:20 2001

File Name:      mazeEngine.java

Description:
******************************************************************************/

import java.applet.Applet;
import java.awt.*;
import javax.swing.*;
import java.util.*;
import java.lang.*;

public class mazeEngine extends Applet {

  public static int center = 20;
  public static int scale = 10;
  public static int xDim = 40;
  public static int yDim = 25; 
  public static Vector segmentList = new Vector();
  public static Random R = new Random();
  public static Vector Matrix = new Vector();

  public void init() { 
    loadMatrix(); 
    setEdgeNodes(); 
  } //init

  public static void loadMatrix()
  { 
    for (int i = 0; i < xDim; i++) {
      for (int j = 0; j < yDim; j++) {
        Matrix.addElement(new node(i, j));
      }
    }
  } //loadMatrix

  public static void setEdgeNodes()
  {
    for (int i = 0; i < Matrix.size(); i++) {
      if (((node)Matrix.elementAt(i)).getX() == 0 ||
          ((node)Matrix.elementAt(i)).getY() == 0 ||
          ((node)Matrix.elementAt(i)).getX() == xDim - 1 ||
          ((node)Matrix.elementAt(i)).getY() == yDim - 1) {
        ((node)Matrix.elementAt(i)).isEdge = true;
      }
      else { 
        ((node)Matrix.elementAt(i)).isInternal = true; 
      }
    }
  } //setEdgeNodes 
       
  public static int gnr(int a)
  {
    int ret = Math.abs(R.nextInt());
    return ret%a;
  } //gnr

  public static node randomInternalNeighborNode(node existing) 
  {
    Vector legalInodes = new Vector(); 
    for (int i = 0; i < Matrix.size(); i++) {
      if (existing.getX() == ((node)Matrix.elementAt(i)).getX()) {
        if (existing.getY() + 1 == ((node)Matrix.elementAt(i)).getY() 
         || existing.getY() - 1 == ((node)Matrix.elementAt(i)).getY()) 
          legalInodes.addElement(Matrix.elementAt(i));
      }  
      else if (existing.getY() == ((node)Matrix.elementAt(i)).getY()) { 
        if (existing.getX() + 1 == ((node)Matrix.elementAt(i)).getX() 
         || existing.getX() - 1 == ((node)Matrix.elementAt(i)).getX()) 
          legalInodes.addElement(Matrix.elementAt(i));
      }  
    }
  
    int pos = 0;
    if (legalInodes.size() == 0) {
      return existing;
    }
    else {
      pos = gnr(legalInodes.size());
      ((node)Matrix.elementAt(pos)).setOccupied();
      return ((node)legalInodes.elementAt(pos));
    }
  } //randomInternalNeighborNode 

  public static node randomEdgeNeighborNode(node existing) 
  {
    Vector legalNeighbors = new Vector(); 
    for (int i = 0; i < Matrix.size(); i++) {
      if (((node)Matrix.elementAt(i)).isEdgeNode()) {
        if (existing.getX() == ((node)Matrix.elementAt(i)).getX()) {
          if (existing.getY() + 1 == ((node)Matrix.elementAt(i)).getY() 
           || existing.getY() - 1 == ((node)Matrix.elementAt(i)).getY()) 
            legalNeighbors.addElement(Matrix.elementAt(i));
        }  
        else if (existing.getY() == ((node)Matrix.elementAt(i)).getY()) { 
          if (existing.getX() + 1 == ((node)Matrix.elementAt(i)).getX() 
           || existing.getX() - 1 == ((node)Matrix.elementAt(i)).getX()) 
            legalNeighbors.addElement(Matrix.elementAt(i));
        }  
      }
    }
    int pos = gnr(legalNeighbors.size());
    return ((node)legalNeighbors.elementAt(pos));
  } //randomEdgeNeighborNode 

  public static boolean isDuplicate(segment seg)
  {
    for (int i = 0; i < segmentList.size(); i++) {
      if(((segment)segmentList.elementAt(i)).x1 == seg.x2 && 
        ((segment)segmentList.elementAt(i)).y1 == seg.y2 && 
        ((segment)segmentList.elementAt(i)).x2 == seg.x1 && 
        ((segment)segmentList.elementAt(i)).y2 == seg.y1) {
          return true;
      } 
      else if(((segment)segmentList.elementAt(i)).x1 == seg.x1 && 
        ((segment)segmentList.elementAt(i)).y1 == seg.y1 && 
        ((segment)segmentList.elementAt(i)).x2 == seg.x2 && 
        ((segment)segmentList.elementAt(i)).y2 == seg.y2) {
          return true;
      } 
    }
    return false;
  } //isDuplicate


  public static boolean allOccupied()
  {
    for(int i = 0; i < Matrix.size(); i++) {
      if (!((node)Matrix.elementAt(i)).isOccupied()) {
        return false;
      }
    }
    return true;
  } //allOccupied  

  public void paint(Graphics g) {

    Date initial = new Date();
    node n1 = new node(0, 0);
    node n2 = new node(0, 0);

    //draw the segments that form the edge
    while (segmentList.size() < (((xDim*2) + (yDim*2)) - 6))
    {
      n1 = ((node)Matrix.elementAt(gnr(Matrix.size())));    
      if (n1.isEdgeNode()) {
        n2 = randomEdgeNeighborNode(n1); 
        segment theSegment = new segment(n1, n2);
        if (!isDuplicate(theSegment)) {
          n1.setOccupied();
          n2.setOccupied();
          g.drawLine(center + (n1.getX()*scale), center + (n1.getY()*scale), 
                     center + (n2.getX()*scale), center + (n2.getY()*scale));
          segmentList.addElement(new segment(n1, n2));
        }
      }
    }           

    //draw the segments that form the inside 
    while (allOccupied() != true) {
      n1 = ((node)Matrix.elementAt(gnr(Matrix.size())));    
      n2 = randomInternalNeighborNode(n1); 
      if (n1.isOccupied() && !n2.isOccupied()) {
          g.drawLine(center + (n1.getX()*scale), center + (n1.getY()*scale), 
                     center + (n2.getX()*scale), center + (n2.getY()*scale));
        if (!n2.isOccupied()) n2.setOccupied();
      }
    }

    //calculate how long it took to generate the maze
    Date end = new Date();
    Long a = new Long(initial.getTime());
    Long b = new Long(end.getTime());
    Long elapsed = new Long((b.longValue()/1000) - (a.longValue()/1000)); 
    
    String stime = new String(elapsed.toString());
    g.drawString("Maze generation completed in: " + stime + " seconds", center, 
                  center + (yDim*scale) + 3);
  } //paint

} //class mazeEngine

class node
{
  int xCoord, yCoord;
  boolean isEdge, isInternal, occ;
  node () {}
  node (int X, int Y) { xCoord = X; yCoord = Y; }
  public int getX() { return xCoord; }
  public int getY() { return yCoord; }
  public boolean isEdgeNode() { return isEdge; }
  public boolean isInternalNode() { return isInternal; }
  public boolean isOccupied() { return occ; }
  public void setOccupied() { occ = true; }
  public void release() { occ = false; }
} //class noce

class segment
{
  node one, two;
  int x1, y1, x2, y2;
  segment(node first, node second) 
  { one = first; 
    two = second; 
    x1 = one.getX();
    y1 = one.getY();
    x2 = two.getX();
    y2 = two.getY();

  } 

  void printElement()
  {
    System.out.println(x1 + " " + y1 + " and " + x2 + " " + y2);
  }

} //class segment