Faulty collision handling for multiple entities

Started by
4 comments, last by oliii 18 years, 7 months ago
I'm testing my engine's collision and movement code. I've set up a simulation where I have 15 or so entities start at random locations on the screen, facing at random angles, and have them all move straight ahead until they bump into each other. There's no real collision response; if an entity is blocked it just doesn't move. My problem is that after all the entities are clumped together and can't move anymore some overlap with each other. As far as I know the collision test itself is working. The entities are represented as circles and are given a movement vector. When two entities are compared the collision test returns a value between 0.0 and 1.0, which represents the time within one frame that the two entities would collide (0.0 means they've already been touching, 1.0 means there'll be no overlap). The movement vectors of the two entities are multiplied by this value to get the respective translation vectors for the next update. The test worked well when I just had two entities, so I think the problem lies in when I test all the entities against each other. My algorithm looks like this:
Actor entity[] = new Actor[15]; // All the entities.
...
double time[] = new double[entity.length]; // Keep track of translation times for all entities for collision.
...
update {
// Set velocity vectors for all entities.
for (int i = 1; i < entity.length; i++)
entity.updateMovements(/* various variables */);

// Collision tests.
for (int i = 0; i < entity.length; i++) {
for (int j = i + 1; j < entity.length; j++) {
double tempTime = collisionTest(entity, entity[j]);

// Entities' velocities multiplied by smallest calculated time.
if (tempTime < time)
time = tempTime;

if (tempTime < time[j])
time[j] = tempTime;
}
}

// Actual movement.
for (int i = 0; i < entity.length; i++) {
entity.move(time);
time = 1.0;
}
}
I test all the entities against each other, keeping track of the times of collision between them. But I always keep track of the smallest times, so if the collision time for entity A and entity C is kept over the time for entity A and entity B; thus A is translated by the lower time (as it was to collide with C). I wonder if this is where I'm getting my overlaps. If I kept the time for A and C over the time for A and B, meaning A hit C before B, what do I do with B? If C hit A before B did, would I have to calculate the translation time for B again? I would be appreciative if someone could help me sort this out. Thank you.
Advertisement
if all was perfect, you would never get overlaps. but with innacuracies, you have to account for them. It's all playing with thresholds.

for example, you can limit the time an entity can move to a maximum value. say 1% of the overall time.

// Collision tests.for (int i = 0; i < entity.length; i++) {    for (int j = i + 1; j < entity.length; j++)     {        double tempTime = collisionTest(entity, entity[j]);                // Entities' velocities multiplied by smallest calculated time.        if (tempTime < time)            time = tempTime;        if (tempTime < time[j])            time[j] = tempTime;    }}// Actual movement.for (int i = 0; i < entity.length; i++) {    // if time big enough, ok, move the entity,     // else entites are too close and may overlap.    if (time > 0.01f)    {        entity.move(time);    }    time = 1.0f;}


really, since overlap is your problem, you should rather check Velocity * time than just time. If that is below a threshold, then don't move. There might be problems with this though, and the entities might feel 'sticky', since they have to move a minimum amount.

Also, don't consider a collision if

(entity0.Pos - entity1.Pos).Dot(entity0.Vel - entity1.Vel) > 0.0f

since the entites are moving away from each other, this will stop them getting glued together in case of an overlap.

EDIT : Yeah, check the value of (Velocity * time) rather than just time itself. If the length of the vector (Velocity * time) < a_small_value, then don't move the entity.

Everything is better with Metal.

Quote:Original post by oliii
if all was perfect, you would never get overlaps.

Are you talking about my collisionTest method? As if my problem could actually be in that?

Quote:Original post by oliii
Also, don't consider a collision if

(entity0.Pos - entity1.Pos).Dot(entity0.Vel - entity1.Vel) > 0.0f

since the entities are moving away from each other, this will stop them getting glued together in case of an overlap.

Don't worry, I do check this. My collision test is based on the Gamasutra article Pool Hall Lessons: Fast, Accurate Collision Detection between Circles or Spheres (login required).

My algorithm, for anyone that's curious, goes like this:
public double collisionTime(Actor A, Actor B) {   Get relative velocity from A to B (treat B as stationary). -> vel           if (vel.magnitude == 0.0)      return 1.0; // Actors stationary to each other.           Get relative position from A to B. -> pos           Get minimum possible distance between A and B: sum of their radii. -> minDist           if ((vel.magnitude + minDist) <= pos.magnitude)      return 1.0; // Actors would not reach each other.           Get unit vector of vel. -> unitVel           Get dot product of unitVel and pos. -> dotprod   if (dotprod > 0.0)      return 1.0; // Actors either moving parallel to or away from each other.           /* dotprod is also the projection of pos onto vel.  dotprod is the distance      along vel that's closest to B.      Therefore, the shortest distance between B and vel is the square root of      the squares of the magnitude of pos and dotprod. */           Get shortest distance between B and vel, (distance between B and its      projection onto vel). -> F           // F is shortest distance A would ever get to B as they travel.           if (F > minDist)      return 1.0; // A wouldn't touch B.           // F makes right triangle with minDist and a third value of T.   Use pythagoras to get T.           // If no such right triangle exists, T^2 would be negative.   if (T^2 < 0.0)      return 1.0;           Get the real distance, which is dotprod - T. -> realDist           if (vel.magnitude <= realDist)      return 1.0; // Final distance greater than relative velocity.           double time = realDist / vel.magnitude;           if (time < 0.0)      return 0.0;   else if (time > 1.0)      return 1.0;   else      return time;}


Anyway, thanks for your help oliii. I'll try out your threshold method to see if that does anything.
if you take the smallest time of collision for each balls, and move teh balls to that time of collision, what you'd end up with would be balls in contact. Theoretically, just in contact (distance between bodies = 0), so just above an overlap. But maths aren't precise, so instead of getting distance exactly 0, you get distance = -0.00001f or something.

You also have to apply a response, which effectively would make them move away from each other. If you don't you may have a problem where balls stick.

example

      B     |     |     |     V     A        B     A     |     |     V


so, A is never moving, B is always going down. B hits A, but A and B trajectory unchanged. Every frame, you will report a collision, but B will be stuck on A, unless B starts moving away from A.

So, you have to apply a response, and also move B.


here is another system, use in Quake3 for example.

1) treat each ball independently. Test collision with the world, and treat other moving balls as not moving (freeze-frame). See if a collision occurs.

2) A collision occured. Calculate the response for the two bodies, but do consider the other body's velocity and apply a response to it.

3) do that until path of that body is not obstructed anymore, then move to next body.

Everything is better with Metal.

Your "Quake 3" system sounds the most reasonable so far, so I'll work on that. That looks a lot like the final collision algorithm I read in the article General Collision Detection for Games Using Ellipsoids (did you write that, oliii?). It's probably time I worked on the collision response anyway.

I just wanted to clarify one last thing: as I calculate the response on a body do I actually update it as I go, or leave that until after similar to what I've been doing? I'm asking because I feel that if I don't update a body then when I move on to the next one I wouldn't know if it would ever hit the former as it (the former) went along the path I calculated before.
Quote:Original post by Zaxx
Your "Quake 3" system sounds the most reasonable so far, so I'll work on that. That looks a lot like the final collision algorithm I read in the article General Collision Detection for Games Using Ellipsoids (did you write that, oliii?). It's probably time I worked on the collision response anyway.

I just wanted to clarify one last thing: as I calculate the response on a body do I actually update it as I go, or leave that until after similar to what I've been doing? I'm asking because I feel that if I don't update a body then when I move on to the next one I wouldn't know if it would ever hit the former as it (the former) went along the path I calculated before.


I didn't write that article, no :) It's go a bug, or at least something really isn;t working.

usually (it all depends, people do things differently sometimes), you update the velocity (and angular velocity if you have some physics with inertia and angular momentums) as soon as you found a collision. then yo umove on to the next, and apply a change in velocity again.

here is what I would do

for (int i = 0; i < NumBodies; i ++){    float  tcoll; // time of collision    Vector Ncoll; // normal of collision     Vector Pcoll; // point of collision on body    Vector Dcoll; // penetration vector (used in case of overlap as a last ditch solution).    float tcollmax = timestep; // max time for collision search (set physics timestep first).    bool bFoundCollision;    do    {        bFoundCollision = false;        for (int j = 0; j < NumBodies; j ++)        {            float  ttemp;            Vector Ntemp;             Vector Ptemp;             Vector Dtemp;             if(Collide(Body, Body[j], Body.Velocity, tcollmax, ttemp, Ntemp, Ptemp, Dtemp))            {                tcoll = ttemp;                Ncoll = Ntemp;                Pcoll = Ptemp;                Dcoll = Dtemp;                tcollmax = tcoll; // try to find an earliest collision                bFoundCollision = true; // need to search for collisions again            }        }           // found a collision. Apply a response.        if(bFoundCollision)        {            ApplyCollisionResponse(Body, Body[j], tcoll, Ncoll, Pcoll, Dcoll);            timestep-= tcoll; // reduce the time left in the frame            tcollmax = dt; // new max time allowed for collision search        }    }    while(bFoundCollision);    // mo more collisions detected. Translate body to remaining of timestep.    TranslateBody(Body, dt);}


With intersections, you have to be a bit careful. stuff like infinite loops, ect... might appear. So, you could for example limit the number of iterations in the while loop.

The second loop also starts at 0, not i+1, since a bodies might collide again after the response, as you take each body separately and test collisions with a static environment.

Everything is better with Metal.

This topic is closed to new replies.

Advertisement