pioneerspacesim/pioneer — pull request #1910 by robn (2013-01-06 04:09:14+00:00)
Title: Helper to efficiently find nearby bodies

There's a few places where we loop through all the bodies to try and find ones that a near another body - scanner, alerts, missiles, ECM. Most of the time there's going to be nothing nearby, or some very small number, making most of those tests redundant.

This adds a helper object that runs at the start of each frame and builds a list of all bodies, sorted according to distance to the system origin. Other parts of the code can then query this to quickly find stuff near them.

Because its distance from the system origin, things still need to do a secondary test on what they get back because there's an chance they could match something on the other side of the system at equal distance. But generally they'll only have to check two or three objects instead of all of them.

I haven't actually tested to see how much of a difference this makes, but as we look to do more checks like this it seems that things could get a lot worse without it. #1663 is one example. Something I want to do soon is allow Lua to ask for an event when something comes within range of a ship. This would be useful for that (and maybe even replace alert, near-planet/near-station and other events).

I originally wanted to use `LengthSqr` instead of `Length` for the distance, but there's not enough precision in a double to represent close things over the range of an entire system. So there is the expense of a `sqrt` call for every body, but I can't see anything better.

The query part might be better as a binary search, but I chose a linear search because its just way easier to write - I always get iterative binary search wrong, and this is looking for ranges, not just equality. It can be rewritten if necessary.

I've come as far as I can with this, I think. Ideas for improvement very welcome.