1
\$\begingroup\$

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?

\$\endgroup\$

2 Answers 2

1
\$\begingroup\$

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.

\$\endgroup\$
12
  • \$\begingroup\$ Did you check my edit? Am I right in thinking that the recursive method would be one (or maybe the only) way of theoretically detecting and resolving every possible collision during each time-step? \$\endgroup\$
    – M-R
    Mar 7, 2018 at 17:50
  • \$\begingroup\$ It has the same problem of potentially infinite recursion depth. You also want to be wary of spending your cycles too eagerly in a depth-first way: Let's say we have to go to a depth of 10 to resolve the collision between our first two objects A & B. Then we peel back to depth one and check the next pair B & C, and find that B gets displaced so that it never collided with A at all. Now that giant depth-10 recursion is outdated and did nothing for us. I'd recommend a breadth-first approach where you try to solve all first-order issues first, before proceeding to remaining second-order issues. \$\endgroup\$
    – DMGregory
    Mar 7, 2018 at 17:53
  • \$\begingroup\$ Could you edit your answer to include a method to ensure no collisions at the end of the time-step? I realise it's not needed and potentially extremely inefficient, but it would be interesting to see how it could be done. \$\endgroup\$
    – M-R
    Mar 7, 2018 at 17:58
  • \$\begingroup\$ No. As mentioned multiple times in the answer, there exist situations that fundamentally have no solution and so no amount of searching will ever get to a state where there are no remaining collisions. \$\endgroup\$
    – DMGregory
    Mar 7, 2018 at 18:08
  • \$\begingroup\$ I should say I'm referring to situations which do fundamentally have a solution. \$\endgroup\$
    – M-R
    Mar 7, 2018 at 18:10
0
\$\begingroup\$

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.

\$\endgroup\$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .