Fast query of objects based on location and radius

Question

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:

• Changing location of animals
• Creating new animals
• Removing animals

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.

Answer 1

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.

See: Trees or Grids? Indexing Moving Objects in Main Memory

Answer 2

kd-trees should work fine if there are many queries before the positions change (e.g., one per animal). Incremental updates probably would be fine as well, but an immutable kd-tree that is completely rebuilt when necessary has the advantage that the tree structure can be represented succinctly with an array. To find all points within a search disk, traverse the tree while pruning nodes whose half-plane completely excludes the search disk. You'll have to sort the results by distance at the end.