//Collision Detection
//Spatial hashing technique
//by Flux 12/19/05

//  Notes:
//  This demonstration shows one way of implementing 
//  a fast collision detection routine using spatial hasing.
//  Note that this trades memory for processing speed.
//  The basic idea is to avoid comparing every node with
//  every OTHER node, just their neighbors on a grid.
//  This avoids the n^2 calculation time needed when comparing
//  every node to every other node and speeds things up happily.



mass test[]=new mass[200];                                              //  Declare a set of 200 point masses.
hashVec hv=new hashVec();                                               //  Define a hash lookup table and tools found in hashlookup.pde

float massRadius=15;                                      
boolean drawCollisions=true;

void setup()
{
  size(400,220,P3D);
  ellipseMode(CENTER);
  for(int i=0;i<test.length;i++)
  {
    test[i]=new mass(random(width),random(height));                     //  Create masses at random points in the sketch.
  }
}

void draw()
{
  background(255);
  
  stroke(220);                                                          //  Draw a grid representing the spatial grid used for hashing.
  for(int x=0;x<width;x+=hv.gridSize)
    line(x,0,x,height);
  for(int y=0;y<height;y+=hv.gridSize)
    line(0,y,width,y);    
  noFill();
  
  hv.clearHashTable();                                                  //  Clear and redefine the hash table every step.

  for(int i=0;i<test.length;i++)
  {
    test[i].update();                                                   //  Update point masses. Time-stepping velocity onto position.
    test[i].dampScalar(FRICTION);                                       //  Dampen the velocity with some friction so things behave...
  }
  
  test[0].p=new vec(mouseX,mouseY);                                     //  Give control of the first mass to the mouse.
  
  for(int i=0;i<test.length;i++)                                
  {                                                                     //  Now that physics has updated, record positions into a hash table.
    hv.add(test[i].p);                                                  //  For example, at point (52,122), the values are rounded down
  }                                                                     //  and the hash key is a String "50100".

                                                                                                                                                                                                                                                                    
  for(int i=0;i<test.length;i++)                                        //  After the point masses have been sorted into a neat lookup table
  {                                                                     //  we can compare their distances efficiently.
  
    vec neighbors[]=hv.neighborsOf(test[i].p);                          //  hv.neighorsOf(vec cv) returns a vector list of neighboring mass points.
    
    for(int s=0;s<neighbors.length;s++)                                 //  Cycle through neighbors to test distances.
    {      
      if(neighbors[s]!=test[i].p)                                       //  Make sure the node being tested isn't tested against itself, causing a
      {                                                                 //  false collision.
      
        if(drawCollisions)       
        {
          stroke(248,85,82,76);                              
          line(neighbors[s],test[i].p);                                 //  Draw the collision line for visual feedback.
        }      
        
        if(dist(neighbors[s],test[i].p)<=massRadius)                    //  Test against distance to neighbor.
        {
          stroke(0,255,48);
          line(neighbors[s],test[i].p);          
          sfSingle(test[i],new mass(neighbors[s]),massRadius,.3);       //  If there is a collision, cause a counter spring force (I'm cheating here).
        }
      }
    }  
  }  
  
  stroke(0,22,62);
  for(int i=0;i<test.length;i++)
  {
    ellipse(test[i].p,massRadius);                                      //  Draw the point masses.
  }
}



//    CONTROLS:
void keyPressed()
{
  drawCollisions=!drawCollisions;
}
void mousePressed()
{
  setup();
}