WithinDistance Implementation

[cami]

The callgrind with Geoffs Patch (gzipped, 3.1MB) is done. Like him, I only generated a universe (500 systems, mature spiral 3-arm, high densities, human, 5AI).

The callgrind reveals Condition::WithinDistance as a major bottleneck, which resorts to the poor double-loop implementation of ConditionBase::Eval(). This confirms Geoffs's earlier suspect. The second major bottleneck it reveals is Condition::Contains, that I already mentioned in another thread.

[Geoff the Medio]

The use of ConditionBase::Eval is not a problem specific to WithinDistance; any condition with valueref parameters or subconditions that aren't appropriately invariant will use this implementation. For example, this may be part of the reason evaluating Contains takes a long time: a subcondition referring to the root candidate will be re-evaluated for each root candidate.

I suspect it will be difficult to avoid this situation without a lot of special cases.

[tzlaine]

We might want to consider a spatially-efficient lookup table of some kind for the WithinDistance condition in particular. Such a thing might have all the problems Geoff mentioned in another thread about keeping caches in sync with the main data structures.

[Geoff the Medio]

We might want to consider a spatially-efficient lookup table of some kind for the WithinDistance condition in particular. Such a thing might have all the problems Geoff mentioned in another thread about keeping caches in sync with the main data structures.

A simpler first step might be to test systems' distance instead of testing all objects in those systems individually. Fleets outside systems could also be tested instead of all ships in them. This would require preprocessing the candidates to sort into containers (Systems, Fleets not in systems) and objects in those containers, which may or may not be faster in practice...

[cami]

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:

1. The edge length of the square is not greater than (D times) the minimum distance we will ever look up
2. 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 log m), n representing the result size and m representing the universe size (both measured in number of objects).