"Gravity well" in Box2D

Questions about the LÖVE API, installing LÖVE and other support related questions go here.
Forum rules
Before you make a thread asking for help, read this.
User avatar
airstruck
Party member
Posts: 650
Joined: Thu Jun 04, 2015 7:11 pm
Location: Not being time thief.

Re: "Gravity well" in Box2D

Post by airstruck » Fri Jun 24, 2016 5:47 am

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.

User avatar
emanevitaerc
Prole
Posts: 16
Joined: Sun Mar 13, 2016 7:21 am

Re: "Gravity well" in Box2D

Post by emanevitaerc » Fri Jun 24, 2016 12:38 pm

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.

User avatar
airstruck
Party member
Posts: 650
Joined: Thu Jun 04, 2015 7:11 pm
Location: Not being time thief.

Re: "Gravity well" in Box2D

Post by airstruck » Fri Jun 24, 2016 12:50 pm

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.

User avatar
airstruck
Party member
Posts: 650
Joined: Thu Jun 04, 2015 7:11 pm
Location: Not being time thief.

Re: "Gravity well" in Box2D

Post by airstruck » Sat Jun 25, 2016 12:22 pm

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.

User avatar
ivan
Party member
Posts: 1530
Joined: Fri Mar 07, 2008 1:39 pm
Contact:

Re: "Gravity well" in Box2D

Post by ivan » Sat Jun 25, 2016 3:36 pm

airstruck wrote: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.
airstruck wrote: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.

Post Reply

Who is online

Users browsing this forum: Google [Bot] and 6 guests