Hello guys. I'm trying to write a simple 2D strategy game. However it has some specific features to consider while programming collision avoidance system. And I'm a bit stuck choosing appropriate algorithms. I was thinking that Warcraft 3 style collision avoidance could work but I'm not sure what are they using there.

So here are some special features that need to be considered:

1. The map is just flat and doesn't have static obstacles, so no pathfinding is required (or is it?)
2. The map will normally have 2 armies consisting of up to 300 units in total.
3. All units are controlled by AI (not the player). Which means that all 300 will normally have different goals (attacking or avoiding different enemy units)
4. Most of the time the order of each unit will be either to attack (follow) or to flee from another moving unit (not just to go to a specific point). So coordinates of the unit's goal will change constantly, as well as it's speed vector.

My explanation might sound a bit blurry, but I will be glad to provide a better explanation if needed.

As for Warcraft 3, I found that the way units avoid each other there would perfectly suit my needs.

While trying to figure out what approach they use in Warcraft 3, I found many answers that refer to pathfinding (it is typically said that clearance based pathfinding HAA* is used) but none of those referring to collision avoidance.

While trying to figure out what do they use in Warcraft 3, I found that units that are not moving at the moment are treated as normal obstacles, so when calculating a path, the area where they stand is marked as impassable. (I thought so because when there were some units standing in a line and I sent a unit right behind them, the unit was not walking just straight into this formation and then trying to find the way around, but from first chose it's pass in a way that went around these units even if sent from far away).

But what about moving units?

My guess is that the path is recalculated each time a collision occurs with all the nearby units (in some range of collision interest) are treated as obstacles as well. But that sounds a bit naive..

Anyway, with the features my game has, such approach is not feasible.

I found many answers that refer to pathfinding (it is typically said that clearance based pathfinding HAA* is used) but none of those referring to collision avoidance.

http://aigamedev.com/open/tutorials/clearance-based-pathfinding/

by finding a clear path, you avoid obstacles, thus collisions are avoided.

a game that uses some form of A* will typically re-calculate paths from time to such as when a path is deemed no longer valid. other approaches include only doing A* out to a limited range instead of the entire map, and re-calculating from time to time - used for lots of units and large maps where full blown A* of everything is too slow.

generally speaking, A* is known to be processor intensive, so you want to calculate path only when required.

note that heuristic approaches can also yield good results in your case (many units, not complex environment, no concave obstacles).

But imagine.. All units are moving all the time. So if one unit receives an order to follow other unit, then the path should be recalculated if not every frame, then at least quite often (because the goal position is changed). And also the passability map should be updated every frame (possibly a bit less often) based on the current unit's locations. It already looks like it's gonna consume lots of CPU. Generally speaking, the path calculated for a unit will already be invalid for the next frame... So, what is the solution?

Maybe in my case the Warcraft 3 solution is not feasible then?

Have you written any prototypes yet to show where the true bottlenecks are? Performance details and catches are often much easier to determine empirically than through guesswork, and it's probably faster to write some one-off tests than to spend days in the forums verbally debating.

Also, you might want to look into how libraries such as Detour Crowd handle dynamic collision avoidance.

Well, here is a basic prototype. Currently units just have basic steering behaviours like seek and flee. All units have a collision radius. And when a collision is detected they are simply separated. I haven't done any complex obstacle avoidance yet cause I'm still trying to figure out what strategy is best to use in my case. As you see, now units still often overlap each other and even if the collision with one unit is resolved, it might cause a collision with the other unit and so on. So, obviously, it's not the way I'm gonna leave it. So, here is a link http://www.fastswf.com/dAfu7cM if it helps (I'm using Flash AS3).

The finished version will be a top-down view strategy where units are controlled by player-written AI. The map will be quite small (probably up to 4 times bigger than you see it now compared to units' sizes).

How about steering towards path waypoints, and use a collision response that pushes agents away from each other.

At a glance, if you have no static objects, I don't think I'd bother using anything other than steering...maybe. It depends on how bunched up things get, and whether you think units are often going to form concave shapes which might get other units stuck, and how often units need to get around each other.

afaik, by experience (that being long hours in front of the game itself) i can say that all you need to do is make sure there's right kind of collision across the board on the z axis; and be able to draw correct lines across the board to the destination so the characters can follow them. Characters would be part of the equation as they cannot be run over. Can't really figure out that part.

I failed to do this a while back and don't see why anyone else shouldn't, truly :)

As I have been interested in League of Legends' minions for a while, I came across some of your issues aswell.

LoL engine is a derivative from WC3's.

Minions use steerings seek&avoid, busy-anotated nodes for non-moving units, and a simple collision avoidance system.

I am still investigating in this latter, it seems to be a kind of stop-and-go/stop-and-repath, maybe associated with something like a bug algorithm (http://www.gamasutra.com/blogs/MatthewKlingensmith/20130907/199787/Overview_of_Motion_Planning.php).

It is janky as heck to try and gather huge minion waves and let them meet in a MOBA, but if you want I can provide you with a record including hundreds of units.

Those crowds have a quite realistic macro-behavior.

Besides, you can maybe dig into cooperative pathfinding : http://www0.cs.ucl.ac.uk/staff/D.Silver/web/Applications_files/coop-path-AIWisdom.pdf.

It is extremely processor intensive, but should produce magnificent results.

Whatsoever, JTippetts' answer is the best i guess.