"Gravity well" in Box2D

[airstruck]

I'm not sure the force of gravity calculation is necessary, it seems like you should be able to just multiply vector components to get an acceleration vector and avoid the squaring and square rooting. Then again I really have no idea what I'm doing, but doing it that way looks alright at least. I got your example working with some minor fixes and a very large value for G, but it doesn't "feel" significantly better than using vector components.

Here's the O(n) solution I had in mind. It calculates the center of mass for all bodies and then moves each body towards it. This should give the exact same results as the O(n^2) solution I posted earlier.

Code: Select all

local G = 0.0667
local bodies = world:getBodyList()

if #bodies > 1 then

    local ms, cx, cy = 0, 0, 0 -- mass sum and center of mass for all bodies
    
    for _, b in ipairs(bodies) do
        local m, x, y = b:getMass(), b:getWorldCenter()
        cx = cx + x * m
        cy = cy + y * m
        ms = ms + m
    end
    
    cx = cx / ms
    cy = cy / ms
        
    for _, b in ipairs(bodies) do
        local x, y = b:getWorldCenter()
        b:applyForce((cx - x) * ms * G, (cy - y) * ms * G)
    end

end

This solution should be pretty efficient. Again, I'm not sure how realistic it is, but it "feels" good.

[emanevitaerc]

Looks good. But I suspect that it might be a problem for the way Box optimizes the simulation. If a good deal of the bodies that would otherwise be sleeping are now moving very gradually, wouldn't it result in a lot more calculations? From a gameplay perspective, the gravity well only really needs to affect objects when the effect is significant enough to notice.

[airstruck]

Sure, just manage two tables of bodies as we discussed earlier, one with massive bodies and one with mobile bodies (some bodies might be in both tables). The first loop should work on the massive bodies and the second should work on the mobile bodies. Or if you really don't want some bodies moving (stars?), make them static and skip static bodies in the loop. Or if you want bodies to go to sleep when you fling them off into space, you could query the viewport for fixtures to work and let damping get them (I think this would work, not sure), but it's weird for things to slow down and go to sleep when you fling them into space, so you might as well delete them.

If a good deal of the bodies that would otherwise be sleeping are now moving very gradually, wouldn't it result in a lot more calculations

Specifically, my first solution was O(n^2), meaning n-squared "units of work" need to be done to process n bodies (exponential time complexity). Ivan's solution was O((n^2+n)/2) I believe; the number of units of work to process n bodies would be the nth triangular number (better than exponential). My second solution is O(n), meaning only one unit of work per body (linear complexity), which is I think as good as you can hope for with this kind of thing.

I get that you're asking if box2d will have to do more calculations, but I wanted to address time complexity first. If Ivan's solution can support 300 bodies (for example), then my original solution will only support about 200, but the linear solution should support 45000 (all other things being equal, and aside from any limits in box2d). The details of what G is and where the bodies list come from were just meant as an example. You might want to come up with G by scaling the real G by your world scale (as in planets are 10 million times bigger than 0.1 to 10 meters) and by your time scale (you don't want to wait a month for a moon to go around a planet), or just mess with it until it looks right.

[airstruck]

Don't use the solution I posted. It's an efficient way to model attraction, but it's not a good simulation of gravitational attraction. It's more like elastic attraction, where the force becomes stronger as objects get farther away from each other. With gravity, the force becomes stronger as objects get closer together. I'm not sure it's possible to simulate gravitational attraction between multiple bodies in O(n) time, because the center of mass is no longer useful when force needs to be inversely proportional to distance. The solution I posted would be great to model something like a swarm of insects, but no good for planets. Ivan's solution will work if you flip the signs on dx and dy (should be x2 - x1 and y2 - y1) and use a very large G (around 20000; not sure what the implications of this are). You can probably optimize it a bit by not applying any force to an object if the force that would normally be applied to it is very small.

[ivan]

I'm not sure it's possible to simulate gravitational attraction between multiple bodies in O(n) time, because the center of mass is no longer useful when force needs to be inversely proportional to distance

Might be possible if you calculate the overall center of mass for all bodies, then you could do a second pass and deduce the effect of gravity for each body. But the math gets quite complicated.

The solution I posted would be great to model something like a swarm of insects, but no good for planets. Ivan's solution will work if you flip the signs on dx and dy (should be x2 - x1 and y2 - y1) and use a very large G (around 20000; not sure what the implications of this are).

You're probably better off increasing the mass of the bodies. Box2d works with kilograms/meters.
There are other caveats too. For example, Box2D would clamp the velocity of fast moving objects, so it's not the ideal solution for planet-scale simulations. Box2D also uses "positional correction" and other tricks which are not 100% physically accurate.