In an RTS game, how to efficiently gather units in the range of another one? Three things I would like to use that for: - Detecting an enemy unit is in attack range - Switching resources if the one gathering is empty or being gathered by another unit. - Flocking. Move around other units. Unless this one can be part of the path finding, but other problems comes: moving units will recreate the nodes, and will invalidate all current paths using the touching nodes. This one is probably the most important and most CPU consuming. My game have a max of 1000 units. It's not that many, but It is out of question to loop through all of them O(N^2) for every actions requiring it. I was thinking of using a quad tree, and processing only a certain amount of units per update frame. Like 100. So would take up to 10 frames for a unit to react. Is there a known "better" efficient way to deal with that problem? Thanks you

The problem you are trying to solve is "Nearest Neighbor". It's very important in collision detection and various other things. google around for terms like "Nearest Neighbor Collision detection" or "Nearest Neighbor algorithm" and such and you'll find a wealth of algorithms.

I wouldn't count out the naive approach until you know for sure that it's going to be a problem. Not every unit necessarily needs to run that search every frame. Personally, I would start with O(n^2) just to get things up and running and optimize when you need to. Obviously no harm in knowing that you'll need to make it better for sure.

-me

2d Spatial hashing... A simple grid usually works best for me. Granted I've never actually tried to use a quad tree for this sort of problem - but that's because I've not been in a situation like this where it was better than just using a grid for this same purpose. You can subdivide the world into a grid using however large or small spacings as you want.

While a quadtree is really good for some things like LOD of heightmaps and what not, I've always thought it to be overkill for 2d collision detection and the like which you mentioned.

Thanks for you replies.

@Palidine
"Nearest Neighbor algorithm" that is the terms I needed, thanks!

@popsoftheyear
You are right. Using a 2D grid with bigger tiles is a good solution. I did that in a previous project, it's just annoying when the unit is moving to register and unregister to the tiles. I find it inefficient in a way.

I don't think it's actually that innefficient. Anyway the quadtree will be subdivided much more if they are closer together and there will be just as much insertion/removal PLUS quadtree rebuilding... so it may actually be less efficient.

The problem which a quadtree solves better is when there is only 1 or 2 units in an area and you can use a much larger area, but in that case even on the grid it will only be 1 or 2 units being unregistered and registered into grid spacings anyway... there's really no performance win but yet the code is more complex.

In my RTS game, I take the non-hierarchical grid subdivision approach. Depending on the size of the map, I split it in, say 8x8 rectangular "regions" which are really just a collection of units. As the units move around, they get added to the regions which they are in. This grid is also used for resource nodes. I currently allow units to be in multiple regions simultaneously, although that forces me to use a hash set on the results of my spatial queries to eliminate duplicate results, which is quite uncool, but as it doesn't seem to be a performance bottleneck, it's probably going to stay like that.

One thing I've done to (somewhat prematurely) optimize memory usage is to have a pool of buffers shared by the entity collections in each region. That way, if there's a big army that moves on the map, it does not leave all the visited regions with big allocated buffers. Regions get their entity buffers from a pool and when the number of entities get low enough, they put their buffer back into the pool and get a smaller one.

That worked quite fine for me and seems to be friendly enough on performance.

"who is near me?" is essentially collision detection where the collision hull is the sensor radius of the unit. If your RTS is mostly planar, then a 2D grid is probably the fastest way to find this. Associating all units with grid cells is O(n) and finding who is within sensor radius is O(1). With only 1000 units though, either a grid or a tree will likely work just fine.

However, it would be good to leverage any existing data structure to do the job. What is your current method for broad-phase collision and visibility determination? If you already have a quad-tree or something like that, then try to use it for NPC proximity detection as well.

Thanks, I will go with the grid.

Right now I loop them all I don't have a quad tree or anything yet.