When should you check collisions?

Question

Suppose a basic game with several circles drawn to screen. The user can select and drag any ball and move it around the screen. Should the selected ball overlap with any other ball on screen, the other ball should displace so they are no longer touching.

The example I've seen use the following structure:

for (every ball pair):
   if (collision = true){
   - resolve collision
  }

However, with this method, isn't there a risk that a displacement could cause an overlap in a pair already checked, and therefore the overlap printed to the screen?

Would it not be better to re-check every ball pair's collision, every time a ball is displaced, rather than every time-step?

Maybe something like:

for (every ball pair):
    if (collision = true){
      -resolve collision
         for (every ball pair):
            if (collision = true){
              - resolve collision
              }
       }

EDIT:

Even the method I've listed above shouldn't always provide 100% accurate results. The only way I can think this could work is with some sort of recursive function which only stops when there are no more collisions. Does that seem right?

Answer 1

What if resolving the second-order collision itself produces a new collision? For full generality, you'd need to keep resolving collisions through a potentially unbounded number of layers of collisions until you finally reach a state where no further collisions remain.

And if the game were ever presented with an unresolvable state (eg. two objects wedged inside a static container too small for them both), then you'd have an infinite loop.

This is not an easy thing to sidestep. The chains of dependency that make the situation unresolvable can be arbitrarily deep and convoluted - we'd never know for sure if we've found a genuinely impossible situation or if "maybe just a few more iterations will crack it" in the general case. So a system that wants to guarantee it finds a solution if one exists is going to accept the possibility of searching for one forever.

So in practice we have to put a cut-off somewhere and say "we tried our best, maybe we'll find a better solution next frame"

Many physics engines will run some finite number of iterations where they try to resolve all collisions/constraint violations detected in the previous pass, then try to resolve all collisions/constraint violations remaining after that pass, etc, to a developer-controlled maximum number of steps.

Past here, they say "well, showing a slight penetration/constraint violation for a single frame isn't the worst sin, let's go with what we have for now and iterate again next frame"

Usually the errors that result are small and short-lived, working themselves out after a few frames. Or they're truly unresolvable situations like the over-confined objects example or a linked chain stretched beyond its maximum length, and trying to find a feasible solution is a fool's errand anyway.

To minimize errors seen this way, you'll want to avoid situations where you have a large number of bodies interacting together - particularly in stacks/chains where the propagation of collision/constraint resolution effects from one end to the other is limited by the number of iterations.

Answer 2

A physics approach is to treat balls as elastic objects. That means they have a position X, a speed V, and are subject to forces F that cause acceleration A.

When two balls would overlap, there is a force that compresses them. The direction of this force is normal to the surface, so for circles and spheres that points to the center. The magnitude of this force increases with the overlap, but you can smuggle how much it increases. This likely won't be noticeable.