AList Agents = new AList();
AList InjuredAgents = new AList();
int numExitedAgents = 0;
int deathDueToTrampling = 0;

class Agent extends Base {
  static final int POINT = 0;
  static final int RECT = 1; 
  static final int BOX = 2;
  static final int SHAPES = 3;

  static final String Paused = "Paused"; // sorta like died but still visible.
  static final String CurrentExit = "CurrentExit";


  float size, speed, percent; //percent measured from n0->n1, speed - for travel from n1->n0
  float offset = 0;
  float mx,my,mz,magents;

  int shape;

  int stepsWaiting = 0;
  int maxStepsWaiting = 30;

  Agent(Edge edge, color c, int shape, String label, String type, float speed, float percent) {
    super(c, label, type, Agents);
    setHere(edge);
    this.speed = speed;
    this.shape = shape;
    this.percent = percent;
    setXYZ();
    setPaused(false);
    size = 2.0f;
  }
  Agent(Edge edge, color c, int shape, float speed, float percent) { // an agent w/ no label or type
    this(edge, c, shape, "", "", speed, percent);
  }
  void die() {
    Agents.remove(this);
    setHere(null);
  }
  void setShape(int shape) {
    this.shape = shape;
  }
  void setSpeed(float speed) {
    this.speed = speed;
  }
  float getSpeed() {
    return speed;
  }
  void setPaused(boolean paused) {
    setData(Paused, paused);
  }

  float getX(float percent, float offset, Edge e, Node n) {
    return (n.x + e.dx()*percent + e.normalX()*offset);
  }
  float getNX() {
    return getX(percent, offset, edge(), n0());    
  }

  float getY(float percent, Edge e, Node n) {
    return (n.y + e.dy()*percent);  
  }
  float getNY() {
    return getY(percent, edge(), n0());    
  }


  float getZ(float percent, float offset, Edge e, Node n) {
    return (n.z + e.dz()*percent + e.normalZ()*offset);
  }
  float getNZ() {
    return getZ(percent, offset, edge(), n0());    
  }


  void setXYZ() {
    if (graph != null && graph.steps() > 20)
      moveToward(getNX(), getNY(), getNZ(), abs(speed*2.0));
    else
      moveTo(getNX(), getNY(), getNZ());
  }

  float checkOffset(Edge ne) {
    return min(edge().getWidth()/2, max(-edge().getWidth()/2, linePointDistance(new point(n0().x,n0().z), new point(n1().x,n1().z), new point(getNX(), getNZ()), false)));
  }

  int numAgentsWithinRect(float width, float length) {
    AList agents = edge().getAgentsHere();
    Iterator it = agents.iterator();
    Agent agent;
    float progress;
    int numAgents = 0;

    while (it.hasNext()) {
      agent = (Agent) it.next();

      if ((abs(percent - agent.percent) * edge().len() < length) && (abs(agent.offset - offset) < width/2.0) && isInFrontOfMe(agent)) {
        numAgents ++;      
      }
    }

    return numAgents;    
  }


  int sign(float x1, float y1, float x2, float y2, float px, float py) {
    float sign = (py - y1) - (y2 - y1) / (x2 - x1) * (px - x1);
    return (sign < 0) ? -1 : 1; 
  } 

  boolean sameSideOfLine(float x1, float y1, float x2, float y2, float x3, float y3, float px, float py) {
    int sign1 = sign(x1,y1,x2,y2,x3,y3);
    int sign2 = sign(x1,y1,x2,y2,px,py);
    return sign1 == sign2;
  }

  boolean inPolygon(float x[], float y[], float px, float py) {
    boolean flag = true;
    int j,k;

    for (int i = 0; i<x.length; i++) {
      j = (i+1) % x.length;
      k = (i+2) % x.length;
      if (!sameSideOfLine(x[i], y[i], x[j], y[j], x[k], y[k], px, py)) return false;
    }
    return true;  
  }

  int numAgentsWithinRectOnEdge(float[] x, float[] z, Edge edge) {
    Agent agent;
    AList agents;
    int numAgents = 0;
    agents = edge.getAgentsHere();
    for (int j=0; j<agents.size(); j++) {
      agent = (Agent) agents.get(j);
      if (inPolygon(x,z,agent.x,agent.z)) {
        numAgents ++;
        mx += agent.x;
        my += agent.y;
        mz += agent.z;
      }
    }        
    return numAgents;    
  }

  int numAgentsWithinRect(float length, float width, Node node) {
    float x[] = new float[4];
    float z[] = new float[4];


    float delta = length / edge().len();

    x[0] = getX(percent+delta*0.01,offset-width/2.0, edge(), n0());
    z[0] = getZ(percent+delta*0.01,offset-width/2.0,edge(), n0());
    x[1] = getX(percent+delta,offset-width/2.0, edge(), n0());
    z[1] = getZ(percent+delta,offset-width/2.0, edge(), n0());
    x[2] = getX(percent+delta,offset+width/2.0, edge(), n0());
    z[2] = getZ(percent+delta,offset+width/2.0, edge(), n0());
    x[3] = getX(percent+delta*0.01,offset+width/2.0, edge(), n0());
    z[3] = getZ(percent+delta*0.01,offset+width/2.0, edge(), n0());

    mx = 0;
    my = 0; 
    mz = 0;
    int numAgents = 0;
    if ((percent+delta < 0.0) || (percent+delta>1.0)) {
      for (int i=0; i<node.edges.size(); i++) {
        numAgents += numAgentsWithinRectOnEdge(x,z, (Edge)node.edges.get(i));  
      }       
    } 
    else {
      numAgents = numAgentsWithinRectOnEdge(x,z, edge());
    }

    if (numAgents > 0) {
      mx = mx / numAgents;
      my = my / numAgents;
      mz = mz / numAgents;
    }
    return numAgents;
  }

  boolean isInFrontOfMe(Agent agent) {
    return (speed < 0) ? agent.percent < percent : agent.percent > percent;  
  }

  void step() {
    if (graph.steps() < 20) {
      setXYZ();
      return;
    }

    if(getBooleanData(Paused)) return;

    magents =   numAgentsWithinRect(speed * 2.0, Graph.singleFileWidth, toNode());
    if (magents/(speed*2.0 * Graph.singleFileWidth) > graph.trampleDensity) {
      if (random(1)>0.9995) {
        edge().trampled ++;
        //println("Agent: " + id + " trampled.  On edge: " + edge().id + " Tramplings on this edge: " + edge().trampled);
        deathDueToTrampling ++;
        die();
        return;  
      } 
      else  if (random(1)>0.8) {
        speed = -speed; 
        return;       
      } else if ((speed>0 && percent>0.9) || (speed<0 && percent<0.1)) {
         percent = (speed<0) ? 1:0;
         gotoNextEdge(); 
      }
      else {
        stepOffset(magents);

        return;
      }
    }

    float tempSpeed = (magents > 0 ? speed/sq(magents + 1) : speed);
    tempSpeed = (magents/(speed*2.0 * Graph.singleFileWidth) > graph.crowdedDensity) ? 0 : tempSpeed;

    percent = percent + tempSpeed/edge().len(); // NOTE: len() is the weighted length
    Node toNode = toNode();
    if (percent >= 1.0f || percent <= 0.0f) {
      if(toNode.getData(Base.Type)==Graph.Exit) {
        numExitedAgents ++;
        die();
        return;
      }
      gotoNextEdge();
    }

    stepOffset(magents);
    //setXYZ(delta);
  }

  void gotoNextEdge() {
      float newDelta = (percent >= 1.0f) ? percent - 1 : -percent;
      newDelta *= edge().len();
      
      Node oldToNode = toNode();
      Edge ne = nextEdge(toNode());
      setHere(ne);
      speed = (oldToNode==n0())?abs(speed):-abs(speed);
      if (speed<0) newDelta = edge().len() - newDelta;
      percent = newDelta/edge().len();
      offset = checkOffset(ne);
  }

  void stepOffset(float magents) {
    if (magents > 0) {
      float l1 = sq(mx - getX(percent, offset + Graph.personWalkPerStep/4.0, edge(), n0())) + sq(my - getY(percent,edge(), n0())) + sq(mz - getZ(percent, offset + Graph.personWalkPerStep/4.0,edge(), n0()));  
      float l2 = sq(mx - getX(percent, offset - Graph.personWalkPerStep/4.0, edge(), n0())) + sq(my - getY(percent, edge(), n0())) + sq(mz - getZ(percent, offset - Graph.personWalkPerStep/4.0,edge(), n0()));  

      offset += (l1>l2) ?  random(Graph.personWalkPerStep/4.0) : -random(Graph.personWalkPerStep/4.0);
    } 
    else {
      //offset += random(Graph.personWalkPerStep/2.0) - Graph.personWalkPerStep / 4.0;
    }
    offset = (offset > edge().getWidth()/2.0) ? edge().getWidth()/2.0 : offset;
    offset = (offset < -edge().getWidth()/2.0) ? -edge().getWidth()/2.0 : offset;

  }

  int sign(float x) { 
    return (x>0)?1:-1; 
  }

  void flee(float x, float y, float z) {
    float l1 = sq(x - getX(percent + speed, offset, edge(), n0())) + sq(y - getY(percent + speed, edge(), n0())) + sq(z - getZ(percent + speed, offset,edge(), n0()));  
    float l2 = sq(x - getX(percent - speed, offset, edge(), n0())) + sq(y - getY(percent - speed, edge(), n0())) + sq(z - getZ(percent - speed, offset,edge(), n0()));  
    speed = (l1 < l2) ? -speed : speed;
  }


  float getDistanceToExit(int exitnum) {
    Node n = toNode(); 
    return ((Float)((ArrayList) n.getData(Graph.ExitDistances)).get(exitnum)).floatValue();  
  }

  float getDistanceToExit() {
    return getDistanceToExit(getIntData(CurrentExit));  
  }

  Node n0() {
    return edge().n0;
  }
  Node n1() {
    return edge().n1;
  }
  Node toNode() {
    return speed>0?n1():n0();
  }
  Node fromNode() {
    return speed>0?n0():n1();
  }
  Edge edge() {
    return (Edge)here;
  }
  Edge nextEdge(Node n) {
    int i = getIntData(CurrentExit);
    Edge edge = n.getMinEdge(Graph.ExitDistances, i);
    if (edge == null) println("Couldn't find next edge for node: " +n.id);
    return edge;
  }

  Edge nextRandomEdge(Node n) {
    return n.getRandomEdge();//, (Edge)here);
    //return n.getMinEdge(Graph.ExitDistances, Graph.MinExit, (Edge)here);
  }

  void paint() {
    if (!showPeople) {
      switch(shape) {
      case POINT:
        paintPoint();
        break;
      case RECT:
        paintRect();
        break;
      case BOX:
        paintBox();
        break;
      }
      paintLabel(CENTER,x+shape,y+shape,z+shape);
    }
  }
  void paintBox(){
    fill(c);
    noStroke();
    pushMatrix();
    translate(x, y, z); 
    box(size);
    popMatrix();
  }
  void paintPoint(){
    stroke(c);
    point(x, y, z);
  }
  void paintRect(){
    fill(c);
    noStroke();
    billboard.BeginBillboard(x,y,z);
    rect(-size/2 , -size/2 , size , size*agentheightKeys );
    billboard.EndBillboard();

  }



  int getCurrentExit() {
    Integer currentExit = ((Integer)getData(Agent.CurrentExit));
    return currentExit == null ? -1 : currentExit.intValue();
  }


  int setAgentExit(boolean b) {
    int exitChoice;
    float d1,d2;
    float randNum;
    int ran = 0;

    if (getCurrentExit() == -1)
      this.setData(Agent.CurrentExit,this.toNode().getData(Graph.MinExit));
    d1 = getDistanceToExit();
    randNum = random(1.0f);
    if(randNum<Graph.randomAgents) {
      exitChoice = randomInt(ExitNodes.size());
    } 
    else {
      exitChoice = ((Integer)this.toNode().getData(Graph.MinExit)).intValue();
    }

    d2 = getDistanceToExit(exitChoice);

    if (d2 < 2.0*d1) {
      this.setData(Agent.CurrentExit,exitChoice);
      if (randNum < Graph.randomAgents)
        ran++;
    }
    return ran;
  }
}

class SetShape implements Ask {
  int shape;
  SetShape(int shape) {
    this.shape = shape;
  }
  void ask(Object o) {
    ((Agent)o).setShape(shape);
  }
}
class ScaleBy implements Ask {
  float percent;
  ScaleBy(float percent) {
    this.percent = percent;
  }
  void ask(Object o) {
    Agent a = (Agent)o;
    //a.setSpeed(a.getSpeed()*percent);
    a.size *= percent; // REMIND: make methods
  }
}