Collision Resolution

Question

I know quite well how to check for collisions, but I don't know how to handle the collision in a good way.

Simplified, if two objects collide I use some calculations to change the velocity direction. If I don't move the two objects they will still overlap and if the velocity is not big enough they will still collide after next update. This can cause objects to get stuck in each other.

But what if I try to move the two objects so they do not overlap. This sounds like a good idea but I have realised that if there is more than two objects this becomes very complicated. What if I move the two objects and one of them collides with other objects so I have to move them too and they may collide with walls etc.

I have a top down 2D game in mind but I don't think that has much to do with it. How are collisions usually handled?

This question is asked on behalf of Wooh

Answer 1

Daniel Kodicek covers this topic in great detail in his book, Mathematics & Physics for Programmers.

Kodicek does two things to achieve natural-looking collision resolution:

• His collision detection function calculates the exact time two objects will collide.
• He recalculates new velocities at the time of collision, so objects never overlap.

I uploaded a demo based on Kodicek's collision detection and resolution.

update: Here's a collision detection & resolution algorithm that is very similar to Kodicek's method. With source code. I still recommend Kodicek's book, as his algorithm is implemented slightly differently and much more thoroughly explained.

Answer 2

What if you check the collision before the objects move, instead of afterwards? Or, in other words, you reject the new position if the objects collide, reusing the old one in that case?

Pseudocode:

  tmpPosition1 = Obj1.position
  tmpPosition2 = Obj2.position
  updatePosition(Obj1)
  updatePosition(Obj2)
  if collided(Obj1,Obj2) then
      updateVelocities( Obj1, Obj2 )
      Obj1.position = tmpPosition1
      Obj2.position = tmpPosition2
  endif

This way the objects will bump with each other when they are about to collide, if your update step is small enough the player shouldn't notice anything strange in the representation.

Answer 3

Whenever two objects overlap, check if they are moving towards or away from each other. Do the collision only if they move towards each other.

It's pretty easy with vector math, simply calculate:

dot_product(B.position - A.position, A.velocity - B.velocity)

If the result is positive the objects move towards each other.

Answer 4

I could be misunderstanding, but it looks like you're asking two questions: 1. what are some general ways of dealing with collision resolution the term you're looking for is 'impulse based simulation', and there are a bunch of papers that can do it better justice than I can.

In summary you want to euler step your physics simulation in momentum space, which is mass times velocity (don't do things force based, your integrator isn't doing it right anyway).

For angular response, luckily the greatest and least moments of inertia can always be reduced to two orthogonal axes (in 2D), which means a matrix multiply will work generally, and if you line these up with the X and Y axes, it turns into a 2D vector.

When you have collision you figure out response based on the linear and angular moments at the point of collision, and a good fudge factor is, if you have interpenetration, to apply some penalty force (as mentioned above) to get the two bodies apart.

From the point you'll end up adding more and more rules to control aberrant behavior, like capping maximum angular momentum so things don't spin like tops, etc., but this is a good start.

Keep it simple if you can.

1. How do you solve multi body collision problems

The only real way to do this is with a system of linear equations and a lot of solving. The practical way to do it is have a system like the one above, and have the physics just naturally resolve over time.

Most games that do things like rolling, or standing on moving surfaces, have a hybrid model where your feet are attached to a surface (or wheels to the road) to accomodate for the physics time stepping (which would result in interpenetration-response cycles and wouldn't work).

Hope this helps. If you need any math examples, let me know.

Answer 5

The way this is usually solved in physics engines is by applying a penalty force. Moving the rigid body after inter-penetration will not look good if your rigid bodies are moving at higher velocities (you will see momentary jerking motions), although as a first step, you should try that and see if it suits your requirements.

A penalty force is applied like a spring-damper, where the penalty force is increased the more you have inter-penetrated the rigid body and is lessened in subsequent frames. Think of it as springs. When two rigid bodies inter-penetrate, they each encounter an invisible spring which dampens their progression (that is, prevents more inter-penetration) and applies the previously mentioned penalty force until the bodies are no longer penetrating.

It is a broad topic but hopefully the above information will get you started.