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...


2 Answers 2


KD-trees are definitely 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.

  • 1
    \$\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
    Commented Nov 15, 2014 at 19:41
  • 1
    \$\begingroup\$ This comment might be far in time but I thought that kd trees were precisely to find neighbors. They are not dynamic and easy to balance, but their purpose is precisely to find neighbors and many algorithms use them for that. AFAIK \$\endgroup\$ Commented Oct 16, 2020 at 8:55

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.


Here's a good review of their implementation:

Dynamic AABB Tree by Randy Gaul (archived from original)

  • \$\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
    Commented Nov 16, 2014 at 21:51
  • 1
    \$\begingroup\$ Could you update the Google code link? \$\endgroup\$
    – kolenda
    Commented Dec 29, 2016 at 16:04

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .