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<GravitatingObject> bodies, GameTime gameTime)
for (int i = 0; i < bodies.Count; 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.
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?