# How do I efficiently check which object causes the most gravitational force in a list of thousands of objects?

I'm working on a proof-of-concept space engine, and one of its tasks is to find the object with the greatest sphere of influence towards the player; that is, the mass of the object, divided by the square root of the distance to the player. I don't see much optimization to do, as an octtree or a KDTree only works for points. Even though there might be a planet only a few thousand kilometers away, a black hole many million kilometers away might have a greater gravitational force on the player.

The current check is brute-force. I go through each object, and return the one with the highest gravitational pull on the player. I have around 10,000 objects to perform this check on, but I might increase this number to millions, later. Optimally, I want to perform the check during each frame, which currently lowers the frame rate from 1600 a second to around 100 a second, which is unacceptable.

A few ideas comes to mind, but none of which seems optimal:

1. Make the system run in its own thread. Great, if the user has a core they don't use for anything, but only gives more overhead if there are no more cores available.

2. Limiting the check to run only once every few frames, resulting in a better average frame rate. The frames that need to be checked will result in stuttering, so this seems like a bad road to go down.

3. Limiting the number of objects checked per frame, so no matter what, only 128 objects may be checked per frame. This has the advantages of solution 2, without the disadvantage of stuttering, as each frame is equally heavy. Still, the programmer in me somehow also dislikes this solution. Then again, game programming is quite different from what I have previously worked on.

I'm not asking solely just for the purpose of this specific system, but also to find the best practice for problems like this, where there must be a compromise between running frequently and performance.

Any suggestions specific to this problem, like how to optimize the function through a modified version of a KDTree, is also very much appreciated; but the question is directed more generally towards the best practice for such problem.

You can precompute most of this data with a spatial partitioning system. For each area in a KD-tree or quad-tree or spatial hash or whatever you want, you can compute the bodies that have meaningful influence over any that area.

To query which body has the highest influence on the player's ship, loop over all bodies influencing the area the ship is in. This is more or less identical to how you'd deal with collision in a grid where bodies might be larger than the width of the grid cells.

You can generate the initial data by adding all bodies to a single node in your tree. For any node that has more than N bodies (a tunable), split the node and recalculate the children's influencing bodies. Keep a minimum limit on the bodies; technically every body everywhere has influence on every other object but for gameplay reasons you can probably limit things to bodies that have more than k newtons (another tunable) of gravitational force. Basically the same as the usual octree/Kd-tree generation.

More simply, think of every body has having a bounding sphere encompassing its gravitational influence. Apply all the usual collision optimizations to that. Accept that bodies wont' have an infinite sphere of influence.

Or just use the GPU and generate a flow field.

• I like this solution of precomputation a lot, thank you. So basically making a one-time calculation giving each area of the KD-tree a list of bodies that can possibly be the one with the greatest gravitational force. Then keep subdividing untill very few possibilites are left for each box. The idea of letting the GPU take over is also great, but my GPU is already heavy at work at generating procedural content as well as rendering the world though. So I don't feel like I can push much more work on it, but still a good general suggestion. Jan 22 '14 at 15:07

If you're serious about attempting this, your best bet will be a combination of all 3 options, plus two more optimization strategies: spatial division (spatial hashing) and approximation. Kind of like mip-mapping you can treat far away objects as a single object.

Knowing how objects are divided in your universe or galaxy helps with approximation. Consider being somewhere within a particular solar system. In most solar systems it's fair to assume that 99% of the mass is in the star(s) - so unless you're getting "orbitally" close to a planet you can disregard any and all gravity from the system's planets. Including surrounding solar systems.

If you're somewhere between solar systems, again you can approximate each solar system's gravitational pull by disregarding all planetary masses and only consider the stars. Or provide a data structure for each solar system that provides the total mass of all the objects in the system, and use the center of the solar system as the center of gravity - at large distances whether a large object is several AU away from the center doesn't actually matter.

Considering that there are millions upon millions of solar systems in a galaxy, or perhaps you're even simulating multiple galaxies, then once again you can approximate by dividing your galaxy or galaxy clusters into evenly spaced sectors. Each sector stores the total combined mass contained within it, and the gravitational pull is the mass of the sector at its center. This is a close enough approximation even if you're in a neighboring sector.

Lastly, the force of gravity is a quadratic function. This means for any mass you have a certain distance at which its gravitational pull is no longer really relevant to your simulation. By tweaking this distance, you can easily sort out any and all objects whose mass to distance ratio is too high to have any effect on your simulation and simply discard them. You can store that information in a tree, perhaps sector-based, so that even when you do large jumps in position you get a fairly good set of masses that actually do have an effect on the simulation at that point in space.

Since you mentioned black holes, I wonder if you're maybe overestimate their effect. You may be surprised how little the gravitational pull of a black hole would have on our solar system if there were one within only 10 lightyears away or so. Or how heavy it would need to be to have a significant gravitational pull at this distance.

PS: If threading is required to run your game (smoothly or even just "playably"), then maybe just don't support single-core CPUs.

PPS: Also do some math on memory requirements. If you have 1 million mass objects in your galaxy and you could store them in 1 byte each, they would consume 1 Megabyte of memory. However you need to store their position in 3-dimensional space, which means 3 coordinates of data type double because the data range of floats may simply be too small to simulate the distances of objects in a galaxy. 3 times 8 bytes times 1 million makes 24 Megabytes.

More realistically each planet needs more than its position, probably its orientation, rotation, mass, what type of object it is, what it is composed of, who is living there, and so on. Make that 500 bytes per object and your memory requirement is 500 Megabytes. Make that 10 million objects and it's 5 Gigabytes.

CPU performance may actually be the smaller of your problems, you may soon find you'll need to swap sectors of planets in and out and replace them with just their approximate mass like I said earlier - if only to be able to actually keep your simulation's memory footprint in check.

• Some good suggestions, but my question on how to treat heavy algorithms that needs to run as frequently as possible in a game-engine stands. I have already successfully rendered multiple million stars at 300+ fps, even though they take some initial time to move to GraphicsRAM, it is the Sphere Of Influence function that ruins performance, which is the CPU, so my current bottleneck is the CPU. Jan 21 '14 at 22:48
• What do you need that function for, exactly? Still, the optimization techniques are in my post, spatial hashing, approximation, creating a tree of objects that actually have an influence at a given point or sector, and so on. You may even be able to offload this work to the GPU, properly optimized it may likely be faster than the CPU and with 300 fps you still have a lot of reserve (on your system at least). Jan 21 '14 at 23:17