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