2
\$\begingroup\$

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:

Initial state

In the next frame they overlap like this:

Colliding

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

After collision resolving

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:

Desired effect

\$\endgroup\$
  • \$\begingroup\$ Obviously, if you dont want imitate impulse-like calculations like from a physics engine, you have to adapt the movement direction and speed. For example, upon collision, you could change the movement direction and speed to the values of the slower object. Also, I think your solution #1 would work (although the case you show would have a strange bouncy effect that is unwanted). \$\endgroup\$ – vanguard2k Jul 16 '15 at 14:14
1
\$\begingroup\$

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 (:

\$\endgroup\$
  • 1
    \$\begingroup\$ The scenario I presented was just a theoretical flaw in an algorithms that I thought of. On second thoughts, the situation won't happen as the displacements in the time steps will be small enough (or so I think). I will implement collision response with pushing both circles away as you wrote and then report back. \$\endgroup\$ – user2648421 Jul 16 '15 at 20:07
  • 1
    \$\begingroup\$ Cool, it sounds like you ought to be safe then, with small steps (; \$\endgroup\$ – Alan Wolfe Jul 16 '15 at 20:08
  • 1
    \$\begingroup\$ I implemented the collision and it works well. Thank you for help. \$\endgroup\$ – user2648421 Jul 17 '15 at 7:46
0
\$\begingroup\$

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

\$\endgroup\$
  • \$\begingroup\$ Could you explain how your system guarantees convergence within two iterations? Let's say you have a stack of 20 boxes on top of each other, and they all move down a few units due to gravity. In general, a "push-out" collision response will cause all boxes to get stuck into eachother (as they are stacked right on top of eachother). Depending on the order in which the collisions are solved, it would take 20 or more iterations to converge to a perfect solution. Maybe I missed something in your approach. \$\endgroup\$ – Jelle van Campen Jul 28 '15 at 7:53

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.