# Collision Resolution

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

-
Can you clarify the type of game? "Top down 2D" could mean a lot of things: a Zelda-style action-adventure game, a vertical-scrolling shooter, or a pocket billiards game. All of these would have very different standard styles of handling collisions! – Ian Schreiber Nov 24 '10 at 19:48
I can't clarify that. The question isn't about what will happen as a result of a collision, it's about handling the multiple overlap problem. I think it's enough to know I'm bouncing objects off each other and I want them to behave realistically to answer this question. – CiscoIPPhone Nov 25 '10 at 14:21

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.

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.

-
Your demo link seems to be broken. – ashes999 Sep 16 '11 at 11:08
@ashes999: link fixed now! – Leftium Sep 18 '11 at 7:48
It's an algorithm for circles. How about boxes? – Anton Chikin Apr 10 '15 at 18:34
@AntonChikin: Kodicek's collision resolution algorithm only takes three inputs: mass, velocity, and normal at the point of collision. Kodicek always calculates the normal at the point of collision when detecting collisions. He explains many different types of collision detection, including a box hitting another box. Just plug in that collision detection algorithm into the collision resolution algorithm. See chapters 8-10 of Kodicek's book for a full explanation. (Note rotational physics requires more math, which is also covered later in the book...) – Leftium Apr 11 '15 at 2:11

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.

-
This is quite annoying, because you can't easily move parallel to objects because you can't move at al if you touch other objects. – Ikke Sep 21 '11 at 12:08

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.

-

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.

-
So instead of preventing inter-penetration this method allows it but provides resistance, almost like the objects are being compressed? – CiscoIPPhone Nov 25 '10 at 8:15
It provides resistance, yes, the resistance increases the more the body is trying to penetrate. In practice, if you have a low enough delta time (for example 10ms) it will not produce any inter-penetrations. The real advantage to this method however is when you do have bodies that have inter-penetrated for various reasons (position was changed, they are networked rigid bodies and their positions were corrected) and now need to be separated, because without this technique the bodies will explode out rather than gradually separate. – Samaursa Nov 25 '10 at 23:43

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.

-