Corpos sobrepostos na simulação de física 2D (Java)

Question

Eu fiz um programa em Java onde os círculos podem se recuperar e gravitar uns aos outros.

Na maior parte (poucos círculos na tela), não há insetos perceptíveis. O problema começa a acontecer quando há uma grande quantidade de círculos na tela. Às vezes, os círculos se sobrepõem se ficar muito lotado. É como se o peso de todos os outros círculos estivessem esmagando os círculos juntos, fazendo com que eles se sobreponham. Claro, existe programa não sabe nada sobre o quanto um círculo pesa, então não é realmente esmagado. Muito provavelmente, a peça da lógica que lida com a resolução de colisões não é capaz de lidar com situações lotadas.

Os círculos são armazenados em uma matriz, e cada círculo passa pela matriz usando um loop para loop, comparando-se com os outros círculos. Se a distância entre o centro deste círculo e o centro do outro círculo for menor que a soma de seus radii, então os círculos estão colidindo. As velocidades de ambos os círculos são atualizadas usando uma equação para colisões.

Eu acho que o problema ocorre porque se um círculo é cercado, ele pode receber uma velocidade atualizada no círculo por trás dela, enquanto o círculo por trás também recebe uma velocidade atualizada no círculo antigo. Em outras palavras, os dois círculos são informados a se moverem em direção ao outro, embora já estejam tocando. Uma vez que eles se sobrepõem dessa maneira, não sei por que eles não desfazem sua sobreposição.

Eu tentei restaurar o cenário tocante se eles estiverem sobrepostos encontrando a distância que eles são sobrepostos, depois os movimentando um do outro; Cada um passa metade da distância de sobreposição. Isso não muda a velocidade do círculo, apenas sua posição.

Isso ainda não resolve o problema. Se o círculo é cercado, e se sobrepõe a um dos círculos vizinhos, sua posição é alterada para que eles não se sobreponsem, mas essa nova posição pode causar a sobreposição com outro círculo. Mesmo problema.

Se não houvesse gravidade empurrando os círculos juntos, eles eventualmente se espalhariam e resolveriam seus problemas sobrepostos, mas a gravidade impede que isso aconteça.

Mais informações:

Gravidade não é levada em conta ao calcular novas velocidades após uma colisão.

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!