xna - Optimizing gravity calculations

I've got a bunch of objects of varying size and velocity which gravitate towards each other. On every update, I have to go over every object and add up the forces due to gravity of every other object. It doesn't scale very well, is one of two big bottlenecks I've found in my game, and I'm not sure what to do to improve the performance.

It feels like I should be able to improve the performance. At any given time, probably 99% of the objects in the system will only have a negligible influence on an object. I of course can't sort the objects by mass and only consider the top 10 largest objects or something, because the force varies with the distance more than with the mass (the equation is along the lines of force = mass1 * mass2 / distance^2). I think a good approximation would be to consider the largest objects and the closest objects, ignoring the hundreds of tiny fragments of rock on the other side of the world that can't possibly affect anything -- but in order to find out which objects are closest I have to iterate over all the objects, and their positions are changing constantly, so it's not like I can just do it once.

Currently I'm doing something like this:

private void UpdateBodies(List bodies, GameTime gameTime)
{
    for (int i = 0; i < bodies.Count; i++)
    {
        bodies[i].Update(i);
    }
}

//...


public virtual void Update(int systemIndex)
{
    for (int i = systemIndex + 1; i < system.MassiveBodies.Count; i++)
    {
        GravitatingObject body = system.MassiveBodies[i];

        Vector2 force = Gravity.ForceUnderGravity(body, this);
        ForceOfGravity += force;
        body.ForceOfGravity += -force;
    }


    Vector2 acceleration = Motion.Acceleration(ForceOfGravity, Mass);
    ForceOfGravity = Vector2.Zero;

    Velocity += Motion.Velocity(acceleration, elapsedTime);
    Position += Motion.Position(Velocity, elapsedTime);
}

(note that I've removed a lot of code -- for example the collision tests, I do not iterate over the objects a second time to detect collisions).

So I'm not always iterating over the whole list -- I only do that for the first object, and every time the object finds the force it feels toward another object, that other object feels the same force, so it just updates both of them -- and then that first object doesn't have to be considered again for the rest of the update.

The Gravity.ForceUnderGravity(...) and Motion.Velocity(...), etc. functions just use a bit of XNA's built in vector math.

When two objects collide, they create massless debris. It's kept in a separate list and the massive objects do not iterate over the debris as part of their velocity calculation, but each piece of debris must iterate over the massive particles.

This doesn't have to scale to incredible limits. The world isn't unlimited, it contains a border which destroys objects that cross it -- I'd like to be able to handle maybe a thousand or so objects, currently the game starts to choke around 200.

Any thoughts on how I might improve this? Some heuristic I can use to shave the loop length from hundreds down to just a few? Some code I can execute less often than every update? Should I just multithread it until it's fast enough to allow for a decent sized world? Should I try to offload the velocity calculations to the GPU? If so, how would I architect that? Can I keep static, shared data on the GPU? Can I create HLSL functions on the GPU and call them arbitrarily (using XNA) or do they have to be part of the draw process?

Answer

This sounds like a job for a grid. Divide your game space into a grid and for each grid cell keep a list of the objects currently in it. When objects move across a cell boundary, update which list they're in. When updating an object and searching for others to interact with, you can look at just the current grid cell and a few neighboring ones. You can tweak the size of the grid for the best performance (balancing the cost of updating the grid cells - which is higher when the grid cells are too small - with the cost of doing the searches, which is higher when the grid cells are too large).

This will, of course, cause objects that are farther apart than a couple of grid cells not to interact at all, which is probably an issue because a large accumulation of mass (either a big object, or a cluster of many small objects) should, as you mentioned, have a larger region of influence.

One thing you could do is keep track of the total mass within each grid cell, and treat the whole cell as a single object for the purposes of farther-away interactions. That is: when you calculate the force on an object, calculate the direct object-to-object acceleration for the objects in a few nearby grid cells, then add in a cell-to-cell acceleration for each farther-away grid cell (or maybe just the ones with a non-negligible amount of mass in them). By a cell-to-cell acceleration, I mean a vector computed using the two cells' total masses and the distance between their centers. That should give a reasonable approximation of the summed gravity from all the objects in that grid cell, but much more cheaply.

If the game world is very large, you could even use a hierarchical grid, like a quadtree (2D) or octree (3D), and apply similiar principles. Longer-distance interactions would correspond to higher levels of the hierarchy.