11
\$\begingroup\$

Working on my game, I'm at the point where I need to track all of the units in the world so that I can do nearest-neighbor checks for combat. This is an RTS-like game, with potentially thousands of small automated units moving around.

I've been looking into KD-Trees and Quadtrees (especially Point Quadtrees). I'm still trying to learn the details of how they work, but so far Point Quadtrees are making the most sense to me. However, I'm getting the impression that KD-Trees are quicker to search, which is important with the number of points I'll have in the tree.

On the other hand, in my case, I'm going to be tracking a massive number of units that are always moving. From frame to frame, their positions will always be different. Quadtrees are apparently faster to rebalance than KD-Trees, but I don't know if that is applicable when you are rebalancing every point in the tree.

I'm wondering if it would be better in this case to just scrap the tree each frame and rebuild it from scratch, rather than try to rebalance every single point in the tree? If a Quadtree is quicker to rebalance, does that also mean it is quicker to build from scratch? If so, that might be more important for performance than the KD-Tree's search speed, depending on how much of a burden it is to create the tree, but I don't know...

\$\endgroup\$
12
\$\begingroup\$

KD-trees are definitively not dynamic enough to be considered, honestly. Moving a few units can easily require you to rebuild the whole KD-Tree. Plus, a KD-tree is very efficient for queries, but not so much for neighbor searching.

A quadtree is more flexible over time, as the modification are kept more locally. The disadvantage is that if you have many units at one place that move often, it may subdivide too much and require a lot of updates due the movement of units. You can set a threshold under which, no subdivisions can occur. But beware, that implies a lot of units could potentially be in the same leaf square.

If however you're only interested in finding all units within a constant radius r, you don't need quadtree and kd-tree right away. You can simply create a 2D array of cells of side of length r and stack your units in each cell according to their position. That way, you always have at worst 9 cells to search. Only if your map is huge, such a grid would be too large to implement.

There's two more entirely different structures we didn't spoke of : hierarchical AABBs and local-sensitive hash table. If the origin of each hierarchical AABB is described relative to the parent AABB, it has advantage that if a large group of unit keep its formation, then you don't need to update the smaller AABBs since they keep the same relative positions. Of course, rotating the formation could cause many updates, in that case the usage of other bounding volumes like spheres or oriented bounding boxes (OBB) may be more efficient.

Local-sensitive hash tables only gives approximate solutions efficiently, so I wouldn't bother with them.

What would I do ? I'd probably start with a simple grid, and when I need it, I'd upgrade it to a quadtree and if I need it, I'll combine it with a bounding volume hierarchy under some threshold: quadtrees work well at a large scale, relative bounding volumes work well at a small scale. Doing it gradually, I don't have to spend hour from the start to get the best data structure immediatly.

\$\endgroup\$
  • \$\begingroup\$ Thanks! I hadn't heard of hierarchical AABBs and local-sensitive hash tables, I'll look into them for the future. For now I'm going with a simple grid and will expand if needed, as you mentioned. :) \$\endgroup\$ – Nairou Nov 15 '14 at 19:41
4
\$\begingroup\$

Lærne's suggestions are great, but I would also suggest a dynamic bounding volume tree of AABBs. Conceptually the dynamic bounding volume tree keeps a balanced tree of nodes which can be queried at any time for near elements by passing in an AABB and retrieving an overlapping pair. The tree is not rebuilt every frame. Instead each node's AABB is slightly inflated when put into the tree, and the tree is only rebuilt whenever the node's actual AABB is no longer contained by the inflated AABB. I use it in my physics engine and it works great.

The Box2D source code has a great implementation of it.

https://github.com/erincatto/Box2D/blob/master/Box2D/Box2D/Collision/b2DynamicTree.h

Here's a good review of their implementation:

http://www.randygaul.net/2013/08/06/dynamic-aabb-tree/

\$\endgroup\$
  • \$\begingroup\$ Yeah, that's more or less what I meant by hierarchical AABB, I wasn't very precise. Oh, and in RTSes unit are often mobile, but in formations. So using coordinates relative to the parent AABB node can be quite efficient, with the "inflation" error margin. \$\endgroup\$ – Lærne Nov 16 '14 at 21:51
  • \$\begingroup\$ Could you update the Google code link? \$\endgroup\$ – kolenda Dec 29 '16 at 16:04

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.