Bodies overlapping in 2D Physics simulation (Java)

Question

I made a program in Java where circles can bounce into each other and gravitate towards each other.

For the most part (few circles on the screen), there are no noticeable bugs. The problem starts to happen when there is a large amount of circles on screen. Sometimes, the circles will overlap if it gets too crowded. It's as if the weight of all the other circles are crushing the circles together, causing them to overlap. Of course, there program doesn't know anything about how much a circle weighs, so it's not really crushing. Most likely, the piece of logic that handles resolving collisions is not able to handle crowded situations.

Circles are stored in an array, and each circle goes through the array using a for loop, comparing itself to the other circles. If the distance between the center of this circle and the center of the other circle is less than the sum of their radii, then the circles are colliding. The velocities of both circles are updated using an equation for collisions.

I think the problem occurs because if a circle is surrounded, it might receive an updated velocity into the circle behind it, while the circle behind it also receives an updated velocity into the former circle. In other words, the two circles get told to move toward each other, even though they are already touching. Once they overlap this way, I don't know why they don't undo their overlap.

I've tried restoring touching scenario if they are overlapping by finding the distance they are overlapped, then moving them apart from each other; each moves half the overlap distance apart. This doesn't change the circle's velocity, only their position.

This still doesn't solve the problem. If the circle is surrounded, and it overlaps with one of it's neighboring circles, its position is changed so they aren't overlapping, but this new position may cause it to overlap with another circle. Same problem.

If there was no gravity pushing the circles together, they would eventually spread out and resolve their overlapping issues, but the gravity prevents this from happening.

Further information:

Gravity is not taken into account when calculating new velocities after a collision.

Answer 1

Sounds like your hunches about what is causing the problem are correct in both cases.

Unfortunately, there's no easy way to fix this issue - it pretty much means rewriting your whole collision detection & resolution code from scratch. You have to work out the exact timing of the first collision, update everything only that far, resolve the collision (do your velocity update) then work out the exact timing of the next collision, then repeat...

Writing a good physics engine is hard, there's a good reason that there are many textbooks on the market about this subject!

The cheap 'fix' for your problem is to reduce the time interval for updates - e.g. instead of updating the physics in 33ms steps (~30fps), try updating in 16ms steps (~60fps). This won't prevent the problem, but it will make it much less likely to occur. Halving the time step will also double the time the processor has to spend doing physics updates!

If you use the cheap fix, the time step which will work best for you will be determined by how frequently collisions occur - more collisions means smaller time steps. How frequently collisions occur basically depends on how fast the circles tend to move and their population density (how much of a given area is filled by circles).

UPDATE: A little more info on the 'proper' approach.

The update would go something like this:

1. Start updating a frame. Let's say we want to update as far as time tF.
2. For every pair of circles, work out when you would expect a collision to occur (ignoring all the other circles). Let's call this time tC.
3. Find the smallest value of tC. Let's say this is for the collision between circles A and B, and let's call that collision cAB.
4. If tC <= tF, update all of the circles up to time tC. Otherwise, go to step 6.
5. Resolve collision cAB. Go back to step 2!
6. Update all the circles to time tF.

As you might imagine, this can get quite complicated. Step 2 can be quite tricky (and coputationally expensive) for non-circular objects (especially once you include things like angular momentum, etc.) although there are a lot of tricks you can do here to speed it up. It's also basically impossible to know how many times you'll be looping between steps 2 and 5.

Like I said, doing good physics simulation is hard. Doing it in real-time is even harder!