I am developing a simple ecosystem simulation and I am stuck on choosing an optimal datastructure for the creatures.
What I basically have is a list of all animals in my current world with information about animal type and location. This list can grow very large - probably close to millions.
So, in order to implement some simple AI, I need to make this operation as fast as possible: Given a point on the map and a radius, give me a list of all animals within the radius sorted by the distance from center point.
The world would be 2d so we are limited to planar coordinates. Some of the operations I also need to support:
I read about kd trees and their ability to calculate nearest neighbour fast.
Questions:
do you think it will work in my case? If not, what data structure should I use to meet the requirements?
EDIT:
Here are some more details as requested in comments. The world wouldn't be too big - something that can fit a screen with animals being little circles. I should also support the scenario where the world could become fairly dense. Finally, I expect not more than a few dozens returned per query but as I will have a great number of those queries (one per each animal althrough this should be cached somehow probably but let's forget about that for simplicity for now) this to be as fast and efficient as possible.
Given your constraints (a large number of moving objects and a small world of presumably fixed size), a simple grid may be a better fit than a kd-tree.