Körper überlappen sich in der 2D-Physik-Simulation (Java)

Question

Ich habe ein Programm in Java gemacht, in dem Kreise ineinander springen und aufeinander in Richtung ziehen können.

Zum größten Teil (wenige Kreise auf dem Bildschirm) gibt es keine spürbaren Fehler. Das Problem beginnt zu passieren, wenn es eine große Menge an Kreisen auf dem Bildschirm gibt. Manchmal überlappen sich die Kreise, wenn es zu voll wird. Es ist, als ob das Gewicht aller anderen Kreise die Kreise zusammen zerkleinern, wodurch sie sich überlappen. Natürlich weiß es natürlich nichts darüber, wie viel ein Kreis wiegt, also ist es nicht wirklich zerquetscht. Am wahrscheinlichsten kann das Logikstück, das die Lösung von Kollisionen handhabt, nicht überfüllte Situationen umgehen.

Kreise werden in einem Array gespeichert, und jeder Kreis wird durch das Array unter Verwendung einer für Schleife durchlaufen, die sich mit den anderen Kreisen vergleicht. Wenn der Abstand zwischen der Mitte dieses Kreises und der Mitte des anderen Kreises geringer ist als die Summe ihrer Radien, kollidieren die Kreise. Die Geschwindigkeiten beider Kreise werden mit einer Gleichung für Kollisionen aktualisiert.

Ich denke, das Problem tritt auf, denn wenn ein Kreis umgeben ist, kann er möglicherweise eine aktualisierte Geschwindigkeit in den Kreis dahinter erhalten, während der Kreis dahinter auch eine aktualisierte Geschwindigkeit in den früheren Kreis empfängt. Mit anderen Worten, die beiden Kreise werden erzählt, um sich aufeinander zu bewegen, auch wenn sie bereits berühren. Sobald sie auf diese Weise überlappen, weiß ich nicht, warum sie ihre Überlappung nicht rückgängig machen.

Ich habe versucht, das berührende Szenario wieder herzustellen, wenn sie sich überlappen, indem Sie den Abstand, den sie überlappen, überlappen, und dann miteinander voneinander bewege; Jeder bewegt sich die Hälfte des überlappenden Abstandes auseinander. Dies ändert nicht die Geschwindigkeit des Kreises, nur ihre Position.

Das löst das Problem immer noch nicht. Wenn der Kreis umgeben ist und sich mit einem seiner benachbarten Kreise überlappt, wird seine Position geändert, sodass sie sich nicht überlappen, aber diese neue Position kann dazu führen, dass sich sie mit einem anderen Kreis überlappen. Das gleiche Problem.

Wenn es keine Schwerkraft gab, die die Kreise zusammen drängten, würden sie schließlich ihre überlappenden Probleme ausbreiten und lösen, aber die Schwerkraft verhindert, dass dies geschieht.

Weitere Informationen:

Die Schwerkraft wird bei der Berechnung der neuen Geschwindigkeiten nach einer Kollision nicht berücksichtigt.

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!