Moving hundreds of units effectively

General
#1

I’m making an RTS game where I need to move hundreds of units at once. I want movement to be similar to Supreme Commander 2’s and Starcraft 2’s “flow field” or “flocking” behaviour.

My initial solution was to use RVOControllers on my units, and when a move order is issued, they become children of a GameObject with an AIPath, so only one path is calculated per group. I have 2 problems with this:

1- This method kinda works if my selection contains only adjacent units, but it doesn’t as soon as my units are sparsely separated since they’re all contained in a single GameObject that moves in a general direction (they don’t regroup).

2- Even if I only do pathfinding on a single object, there’s always a small delay (0.5s) before the object actually moves even though the console says 0s. I saw other people having this problem on Windows but never saw a solution. This is unrelated to my particular RTS needs, as it happens even with the simplest setup.

So concerning point 1, what would be the best approach to have local avoidance, fast pathfinding AND regrouping? If you can give an answer for point 2, that’s just icing on the cake :D.

Thanks!

#2

Well, that is a hard problem I must say.
Random stuff:

  1. Reduce graph complexity, i.e use navgraphs if possible or lower density grid graph. You would want quadtree graphs, but those are not implemented in this system yet.
  2. Try to use MultiTargetPath, a single MultiTargetPath can calculate all paths for a small group of units close to each other at almost the same cost as a single one… I am not sure if it supports multithreading yet though.
  3. The FlowField algorithm is not something I have implemented or have any plans to implement soon (I havent read much on how it works, have to do that some time).
  4. Your approach of making all units children of a single GO wouldn’t work very well. An alternative approach is to make all units move in the general direction of the target initially and then update their direction as more paths are calculated.
  5. More multithreading! (if possible)
  6. Check the Optimizations tab, if you can understand any of the descriptions, try applying them, it might give you a few percent faster pathfinding (nothing really exciting, sorry).
  7. I have no idea what could cause that 0.5 second wait. Is it only occurring the first time you issue a pathfinding request or every time?
  8. You could try splitting the units into several small groups (in which all units are close to each other), then do pathfinding only once per group. Also, see 2.

Also, the flocking behavior is not very pathfinding related (more of local avoidance), the queuing behavior is though. Also see http://www.red3d.com/cwr/steer/ (you might want to check out UnitySteer as well if it is not too heavy-weight for your game).