2D multiple circle collision response

Question

I'm trying to implement simple 2D circle collision system. There are circles with different radiuses and velocities (the larger the circle the slower it is). Contrary to all the questions on the Stack, the circles do not bounce at all.

There is no problem with collision response for two circles that overlap. There are two approaches that I thought of:

1. Pushing the circles apart with displacements dependent on the ratio of circles' radiuses.
2. Pushing the smaller circle away so it doesn't collide with the bigger circle anymore.

However, neither of these approaches works for multiple circle collisions. Let's consider an easy example:

Three circles are moving towards the same point but with different velocities:

In the next frame they overlap like this:

Then with either of the two approaches the smallest circle gets pushed away from the biggest one:

And then the right-most circle would push the smallest circle to the right making an infinite collision loop.

Of course, the more circles, the more complicated the collision resolving would be. Additionally, I'm going to add static walls thus making collision system even more complex.

What algorithm can I use to make multiple collisions work? I guess that the desired effect would look like this:

Answer 1

The way that common physics engines work is that they deal with collision responses for each pair of colliding objects independently.

In your case that means when the three circles are overlapping it would try to do something like push the circles apart in each colliding pair by just a little bit.

Since dealing with pairs at a time isn't going to give a global solution in one pass (a resolution to one overlap may make another overlap worse), multiple iterations are done until either there are no overlaps, or the maximum number of iterations has been reached.

For best quality results you move the objects only a very small amount each time, but have a high number of max iterations. For fastest results however, you move the objects more and have a lower number of max iterations.

In your specific case, the objects have penetrated too deeply for a standard collision response "push objects apart" algorithm to give very good quality.

If you can prevent the objects from penetrating each other so deeply, you'll have better results.

One way to do this would be to not let your objects move so quickly.

Another way to do this would be to do multiple smaller movement steps and collision responses per game loop instead of moving the full amount in one go.

A third way could be to do swept shape collision detection to find where exactly an object collides with other objects while moving along its path. In this scenario if implemented as described, you move each object one at a time and check for collision times and make it move only as far as it can and then stop. This ought to work decently in practice but you might see some strange interactions when many objects move relatively long distances each frame.

Basically, objects that move too far in a frame are a source of problems in many types of physics algorithms, including yours, causing the problems you are trying to overcome (:

Answer 2

I agree with mostly everything Alan Wolfe said except the following :

Since dealing with pairs at a time isn't going to give a global solution in one pass (a resolution to one overlap may make another overlap worse), multiple iterations are done until either there are no overlaps, or the maximum number of iterations has been reached.

The system I implement only needs to make ~2 iterations through the collision resolver to converge onto a valid solution. There are two significant details which I've picked up on.
The first is to split up your x-direction and y-direction collisions.
The second is to move every object at the same time before resolving the pair-wise collisions.

So here's the flow of my implementation:

1. Collect each objects 'wanted' movement (either through AI or user input)
2. For each object, apply its x-direction movement
3. For each pairwise collision, append the reaction to the two object's lists of 'pushes' (which could be in x & y direction)
4. For each object, sum up its reaction list and apply that movement to its position
5. Repeat steps 2-4 but for the y-direction

You should also put in checks or flags for each object so that you don't recalculate collisions
This process will converge quicker and is more deterministic since it waits until all collisions have been resolved before applying changes