Suppose you're writing a video game that takes place on a large rectangle (2d). You have a large list of entities (monsters, spells, and so forth, represented as points) living on this rectangle, and you need to know which pairs are within Euclidean distance 1 of each other, and for each such pair, what their distance is, so you can figure out how each affects its neighbors. This information must be updated every frame of the game.

In this particular case, the entities are moving rapidly, but we can assume that they often retain their relative positions. For example, groups of them may move in formation, or entities may move like cars on a highway. We can also assume that their minimum distance has some bound, or at very least, there is an upper bound on the number of neighbors each node can have.

Brute force is O(n^2) per frame. Using a data structure such as a KD-tree or a Delaunay triangulation, we may be able to improve that to O(n log n). But since the relative structure of the group is roughly constant, is there a way to achieve typical-case linear time?

If I were to get serious about this problem myself, I'd start with a Delaunay triangulation, see if I could use it to efficiently find the pairs of points of less than unit distance, and then see if there was an efficient way to use the previous frame's Delaunay triangulation to accelerate generating the current frame's triangulation.

This is mostly academic for me, since my tests in Python so far reveal that brute force has the best wall clock time. But surely I can't be the only person curious about this problem -- anyone who has ever written a game must have given it some thought. SciPy's KDTrees can produce the data I'm looking for with sparse_distance_matrix but the wall clock time for building and querying a KD tree was much worse than brute force in the cases I tried. Perhaps KDTrees involve more Python and less C than the brute force code I used (scipy.spatial.distance.pdist), or perhaps the time coefficient for the KDTrees is just very high on its own.

  • $\begingroup$ It would be good to add details: items count, groups count, are those elements the same, when you move (frame, player moves?) or new points appear, what changes? If you start from elements with their distance and then check changes only would it help? (Not by another triangulation or recalculation) It is unclear what this game does, how points move etc. O is asymptotic, if you have dozen points it will be faster. Since relative distance is almost the same, why do you recalculate it on every frame? Are you willing to change Euclidian distance to different one? $\endgroup$ – Evil Apr 20 '16 at 4:06
  • $\begingroup$ Tens of thousands of items, no strictly defined groups, elements are identical (for now), no new points appear (for now). Euclidean only (for now). Not sure what you mean by O is asymptotic; I'm looking for a data structure that gives typical case linear time; I don't care about worst case (within reason). Relative distances may not change much, but they do change. Not recalculating them would lead to errors. $\endgroup$ – Ed Krohne Apr 22 '16 at 2:38

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.