Processing 1.0 - Processing Discourse - collision detection help

We closed this forum 18 June 2010. It has served us well since 2005 as the ALPHA forum did before it from 2002 to 2005. New discussions are ongoing at the new URL http://forum.processing.org. You'll need to sign up and get a new user account. We're sorry about that inconvenience, but we think it's better in the long run. The content on this forum will remain online.

Index › Programming Questions & Help › Programs › collision detection help

‹ Previous Topic | Next Topic ›

Pages: 1

collision detection help (Read 907 times)

oompa_l

collision detection help
Dec 31^st, 2008, 5:36am

hi

i was playing with the boids algorithm but couldn't keep my boids from partly overlapping no matter how much I changed their separation values. in my boids example each boid represents an entry in a table and each one's readius is unique.

I have tried to implement a collision detection but in the process have gotten all bogged down. I got somewhere with the billiards app here: http://www.skanaar.com/applets/billiards/ but i was finding that the distances at which the boids were colliding did not match their radii - and i got bogged down trying to make the collision work with the very tidy system of accumulating vectors...

i also sort of get the hack here
http://processing.org/hacks/hacks:collision_detection but am not sure how to implement it. The circles one looks quite different then the rectangular one which looks like a boolean check. THe question here is what to do if the boolean returns false - how to follow through with the collision resolution...

I'm wondering if someone can suggest a good way of doing what I want - to ensure that my boids do not occupy the same space...

thanks

PhiLho

Re: collision detection help
Reply #1 - Dec 31^st, 2008, 1:09pm

This is not a simple problem. You will find several forum threads on the topic. The Wikipedia article on Collision detection might get you started. For simple objects, people often recommend to use spatial partitioning to reduce the number of checks (no needs to check if two objects on opposite corners of sketch will collide, if they are small enough).

oompa_l

Re: collision detection help
Reply #2 - Jan 2^nd, 2009, 7:54am

do you know offhand of any good examples that show this spatial partitioning you are speaking of?

are you saying the hack is too resource heavy for a check across a large array of objects?

here's my example where I am trying to implement code I found:

http://upsdn.ca/processing/Flocking_experiment_02/applet/

it's not quite working but I'm not sure why...

here's the specific code I added for collisions:

Quote:

  void run(ArrayList boids) {
    flock(boids);
    update();
    borders();
    render();
    collision(boids);
  }

void collision(ArrayList boids){

    //collision detection
    for(int i=0;i<boids.size();i++){
      for(int j=i+1;j<boids.size();j++){
        Boid one = (Boid) boids.get(i);
        Boid two = (Boid) boids.get(j);
        one.collisionDetect(two);
      }
  }
}

void collisionDetect(Boid b){
    float distance = loc.distance(loc,b.loc);
    //float distance = loc.distance(
    if( distance < domain ){
      float vxSum = 0.5*(vel.x + b.vel.x);
      float vySum = 0.5*(vel.y + b.vel.y);

      float forceMag = ((b.vel.x-loc.x)*(vel.x-vxSum) + (b.vel.y-loc.y)*(vel.y-vySum));
      float xForce = 0.25*(loc.x-b.vel.x)*forceMag/distance;
      float yForce = 0.25*(loc.y-b.vel.y)*forceMag/distance;
      /*
      vel.x   = vel.x + table.elasticity * xForce;
      vel.y   = vel.y + table.elasticity * yForce;
      b.vel.x = b.vel.x - table.elasticity * xForce;
      b.vel.y = b.vel.y - table.elasticity * yForce;
      */
      vel.x   = vel.x + 0.9 * xForce;
      vel.y   = vel.y + 0.9 * yForce;
      b.vel.x = b.vel.x - 0.9 * xForce;
      b.vel.y = b.vel.y - 0.9 * yForce;

      b.loc.x = loc.x + (domain+1)*(b.loc.x-loc.x)/distance;
      b.loc.y = loc.y + (domain+1)*(b.loc.y-loc.y)/distance;
    }
  }

PhiLho

Re: collision detection help
Reply #3 - Jan 2^nd, 2009, 10:49am

The hack is fine but it doesn't address the problem of pruning the number of checks if the population is important. With a few hundred of agents, your approach is probably viable.
As discussed in colliding with 2 agents, this technique is fine but is harder to extend to multiple collisions (if needed).

I recall I saw an example of primitive (fixed grid) spacial partitioning in this forum. I haven't tried it yet myself. I am also perplex on using this technique on objects of non-atomic size, which can be in several cells. Should we use only their center Make big cells around them

oompa_l

Re: collision detection help
Reply #4 - Jan 2^nd, 2009, 6:08pm

this might be the primitive example you were talking about...I wasn't sure what was going on with it but I might be able piece things together given your thoughts.

http://users.design.ucla.edu/~mflux/p5/hashcollision2/applet/

i mucked around with my loops around the initial assigning of boids for collision check and it seems a little better :
Quote:

void collision(ArrayList boids){

    //collision detection
    for(int i=0;i<boids.size();i++){
      Boid one = (Boid) boids.get(i);
      for(int j=0;j<boids.size();j++){
        if (j!=i){
        Boid two = (Boid) boids.get(j);
        one.collisionDetect(two);
        }
      }
  }
}

the problem Iam finding now is that the boids sometimes flat out disappear upon collision - why is this happening, and any ideas on fixing that?

Pages: 1

‹ Previous Topic | Next Topic ›