Sign in to follow this  

Faulty collision handling for multiple entities

This topic is 4518 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

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[i].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[i], entity[j]);

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

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

// Actual movement.
for (int i = 0; i < entity.length; i++) {
entity[i].move(time[i]);
time[i] = 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.

Share this post


Link to post
Share on other sites
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[i], entity[j]);

// Entities' velocities multiplied by smallest calculated time.
if (tempTime < time[i])
time[i] = 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[i] > 0.01f)
{
entity[i].move(time[i]);
}
time[i] = 1.0f;
}




really, since overlap is your problem, you should rather check Velocity * time[i] than just time[i]. 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.

Share this post


Link to post
Share on other sites
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.

Share this post


Link to post
Share on other sites
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.

Share this post


Link to post
Share on other sites
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.

Share this post


Link to post
Share on other sites
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[i], Body[j], Body[i].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[i], 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[i], 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.

Share this post


Link to post
Share on other sites

This topic is 4518 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this