How to handle simultaneous collision so that order of processing does not matter?

Question

Suppose there are 3 balls colliding at the same time. I find that the order in which I resolve collisions makes a difference in the final result, which ofcourse makes no sense.

To explain and keep things simple, consider 3 balls in 1D, all same mass, elastic collision. The numbers at the top are the speeds and the arrows is the direction. Assume they are currently all touching each others, i.e. in collision

 -->2   -->1 <---3
   O     O       O
   A     B       C

This shows ball A hitting ball B from the back and ball B and C are colliding face on.

Now if we resolve collision A with B first, followed by resolving collision B with C, but using the new speed of B, this should give the same result if we instead have resolved collision of B with C, followed by resolving A with B (using the new speed of B).

But it does not.

first case: A with B, followed by B with C

A with B gives

 -->1   -->2
   O     O  
   A     B  

and B with C gives (but using new B speed of 2 above, not the original speed of 1)

 <--3   -->2
   O     O  
   B     C  

Hence the final result is

 -->1   <--3  ---->2
   O     O       O
   A     B       C

second case: B with C, followed by A with B

B with C gives

 <--3   --->1
   O     O  
   B     C

A with B (but using new speed of B of 3 above, not original 1)

<--3    -->2
   O     O  
   A     B  

Hence final result is

 <--3  -->2   ---->1
   O     O       O
   A     B       C

You can see the final state is different.

What Am I doing wrong? and more importantly, what is the correct method to handle this?

For simulation with many balls and also collision with walls, this case is very possible. (for example, ball hitting a wall and being hit by another ball at the same time, would give same problem as above, the order gives different results).

Currently I use a loop to iterate over all objects and resolve collisions between each 2 at a time. Hence the order I use is arbitrary (order is just the index of the ball in an array).

Answer 1

You are not doing anything wrong but your collision response is not yet finished. In the first one A B are still colliding, and in the second one B and C are still colliding. So you should resolve those collisions.

And if you collide you will get the same answer A <--3 , B-->1, C-->2

Although in your simulation you objects can collide at the same time, in reality they will never. There will be always a little time(may be very very little) between collisions. So for simplicity physics engines resolve collision by pairs. But they should do it until all pairs are seperated. And this requires more than one iterations. And the numbers of iterations may become very high if you are trying to simulate stacking bodies like configuration.

you can check

how to sort objects for Guendelman shock propagation?

for further information to reduce iterations.