# What is the best way to handle simultaneous collisions in a physics engine?

I'm writing a 2d physics engine in javascript so that I can learn more about physics in video games. I have it working correctly for rigid body collisions, except for if any body collides with two or more other bodies at the same time.

Currently for each pair of colliding bodies (A, B) I modify their velocities and angular velocities based on the collision impulse, and nudge them out from each other so they aren't penetrating. But then collision detection and impulse calculations for other collisions involving A will be wrong.

What approaches can I explore to get my engine working for 3+ objects colliding with each other?

-
Related: gamedev.stackexchange.com/questions/15836/… and gamedev.stackexchange.com/questions/26181/… and I'm sure there's more, I just can't find the right now. – Byte56 Jul 19 '12 at 17:00

I use the following approach:

• compute reaction/restitution force contributions for each pair (A,B) and store these contributions in A and B's own accumulators
• compute restitution velocities from impulses (as you stated) and store them in the same fashion (as deltaV velocity residues in their own accumulators for each (A,B) pair)
• compute penalty displacements (again, accumulate displacements, do not apply them instantly!)

This approach is similar to how the Jacobi iterative algorithm works with linear simultaneous systems of equations. And it's not guaranteed to converge, but in my simulator it does the job quite smoothly.. in 3D (yes, an extra dimension adds twice the difficulty!).

Caveat: correct positions and velocities only after your collision detection/handling phase is over! That way you simultaneously update your colliding actors. Also, the restitution forces must be taken into account next time when you integrate for positions and velocities.

EDIT: Well, I guess you're using the already abused Verlet integration method (this one's become a household name within gamedev enthusiasts). In this specter of collision handling and integration, you might want to take a look here.

UPDATE: Some of the information on how to approach collision (and self collision for that matter of fact) can be found in these papers:

The approach I proposed is not by a long shot an original contribution, many games use it with plausible results and it was best employed by Jakobsen in his Hitman game engine.

From a somewhat practical experience, penalty forces (similar to linear or exponential springs getting their input from the penetration distance) do not properly solve penetrations when other forces from the bodies that collide manage to be greater than them. That's why I chose to combine three (almost redundant) approaches: Newtonian reaction forces (you push the wall, the wall pushes back), impulse derived velocities (snooker balls colliding) and a non-natural "move the bodies away from each other geometrically" solution. Together they seem to provide everything: get rid of most ugly interpenetration artifacts, colliding bodies tend to interact with each other on the long run (due to restitution velocities and forces - at least the forces that tended to drag the bodies in a collision scenario are cancelled out and the bodies bounce away from each other). Lastly, for further understanding of these simple but common concepts, I suggest analysing these slides.

My "abused method" epithet describing the Verlet integration steps is targeted at a popular culture belief that this is the Holy Grail of integration methods. It is just marginally better than its Symplectic Euler (also called by some semi-implicit Euler) cousin. Way more complicated integration methods exist (and all bear the implicit name in them). Powerful game engines make use of them, but indie developers don't have the time to experiment with those since Verlet, when tuned to a specific scenario, really does wonders. Also, there is absolutely no integration method that can deal with stiff constraints without a little cheating being involved (can't find the link, but the paper I'm referring to should be called "X.Provot - "Deformation Constraints in a Mass-spring Model to Describe Rigid Cloth Behaviour" ".

-
Thanks (+1)! What are 'restitution velocity' and 'penalty displacements'? Also, why do you say that verlet integration is 'abused'? Do you think it is a bad method to use? – Cam Jul 19 '12 at 18:14
Restitution velocities are exactly those velocities that you get from impulses, the only difference is that I compute them as residues (i.e. I store the difference between that impulse based velocity and the current velocity while keeping the current velocity untouched for further computations). Penalty displacements are vectors with a length determined by how much two object interpenetrate and it is the minimal length vector that can translate one object completely outside of the other. I usually add such a displacement to each object dividing the length by 2). – teodron Jul 20 '12 at 8:26
Brilliant answer! I have another question though. Say I accumulate the restitution velocities, won't they add up to a very non-realistic number? If I treat each collision with object A separately and just add up the effects on each object won't A not have its impulse spread between the objects? Instead full impulse will be applied to each which seems wrong to me intuitively – Cam Jul 20 '12 at 15:59
That's a very good question.. from one point of view, it seems plausible for impulses to additively contribute to the resulting velocity. Here's my (perhaps faulty!) reasoning: imagine three pool/snooker balls colliding. One of them should receive contributions from the other two in this additive fashion. Initially, I thought weighing these contributions and compute an weighted average for the final velocity, but since I wanted quick results, I skipped this idea. All in all, the colliding ball must get velocity contributions from the remaining two. Perhaps a highschool text book can help. – teodron Jul 20 '12 at 16:33
Perhaps I don't understand what you've explained, because the following example still concerns me: Consider a horizontally-long rectangle falling straight down, and suppose the floor is jagged (so composed of multiple side-by-side triangles). If there are n triangles, using your accumulative method, the rectangle will bounce back up at n times the speed it should! How can that situation be fixed? – Cam Jul 21 '12 at 0:06

I suggest that, instead of changing velocities, you change the forces acting upon an object. Don't "nudge" them out, rather, do it smoothly and utilizing already existing code. By doing this the bodies wont immediately (and rapidly, I suppose) change their velocities.

Check out Box2DJS for an example: http://box2d-js.sourceforge.net/index2.html.

-