Sign in to follow this  

RTS Algo to detect serounding units

This topic is 2839 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

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

Share this post


Link to post
Share on other sites
What you are talking about i would say involves many smaller (and somewhat larger) sub-algorithms.

a unit should have a radius (or maybe even a fov) that is passed into a function and you get returned a list of the units within that area.

for resources, a similar thing can be done for resource gathering spots..

flocking... well... this is a big area. Supreme Commander 2 was released today and it has flow field pathfinding, which also includes some flocking in it.

Edit: A quad tree of units based on position may not be a bad idea, especially in a rendering loop.

Share this post


Link to post
Share on other sites
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

Share this post


Link to post
Share on other sites
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.

Share this post


Link to post
Share on other sites
@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.

Share this post


Link to post
Share on other sites
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.

Share this post


Link to post
Share on other sites
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.

Share this post


Link to post
Share on other sites
"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.

Share this post


Link to post
Share on other sites
Your choice of using a grid is probably a good idea. Quadtrees are not really ideal for this sort of problem.

One way is to use a rectangular grid where each node contains a vector of units which are in it. When a unit moves, it needs to know which nodes it's in so it can have those nodes drop their reference to it. Units do not need to store the list of nodes they're in, as this can be calculated in O(1) when needed. But then searching those nodes is in O(n), although the maximum n will be relatively small. If units do store the nodes they're in, they can also store their position in the other structure, and combined with the "swap and pop" vector erase trick, you can do all this in O(1).
If you choose a node size proportional to the smallest unit size, you can determine the maximum number of units that can be in a node. This allows you to use statically allocated arrays instead of vectors, which will mean faster loading times and less memory usage. (The cost adds up when the number of nodes is potentially very large)

Share this post


Link to post
Share on other sites

This topic is 2839 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this