If the universe objects use getters and setters for their position, and keep a reference to the universe object, they can update the caches themselves. This is particularly easy with the following described "cache" structure. However, it's also fair to just remove all moved objects from the cache, check them separately on distance lookup and regenerate their cache entry (i.e. cache invalidation, cache miss and cache fill).
If you only lookup all objects within a fixed distance, a square grid with an edge length of this distance allows you to restrict your search to only four grid squares, no matter where you look for objects within that distance.
However, if you want to support arbitrary distances, a fixed grid would force you to either look up many squares (some possibly empty) or inspect a large square you only want very few obects within. This can be solved using a hierarchical grid: It makes the universe a square and constructs a quadtree of squares, the children of each node representing a different quarter of their parent square each. A square is a leaf and no further sectioned if one of the following conditions hold:
- The edge length of the square is not greater than (D times) the minimum distance we will ever look up
- The square contains at most one object (M objects)
(The "standard version" of this datastructure features M=D=1, but it can be beneficial to make these numbers a little higher, say 2, for efficiency. Experiments are necessary here).
Since the position within this tree is directly implied by the object's coordinates, it's very easy to keep it up-to-date.
Now in order to lookup nearby objects, you simply go down the tree structure and gather all leaves that overlap the circle representing your search domain. All objects within leaves fully within the search domain can be directly added to your result set. Finally you search all leaves only partially overlapping your search circle by testing each object individually. The total cost of this operation is O(n
representing the result size and m
representing the universe size (both measured in number of objects).