Quote: Original post by Emergent
That's what I figure whatever they do must reduce to most of the time, but you can imagine situations where this would fail, so I'm guessing they must actually be doing something a little more robust. For instance, suppose you have a group of units selected across a ravine, and units on the different sides must follow very different paths to reach the same goal; something must be done to deal with cases like this.

I can think of a few ways to do it. One could be that all units that have line-of-sight to each other define a single "flock" and each "flock" generates their own path. Another one would be that when two or more units are touching (or close enough) they define a flock. When creating the path, any units within x units of the nearest flock will first move to join the flock before following the path as well.

It's certainly not easy, and they seem to have done a fantastic job. The bit right at the end of the video where the zerg swarm the enemy base, destroying it in seconds is awesome.

Quote: Original post by Kaze

Quote: Original post by InnocuousFox
@Kaze: In SC2, units will push through their buddies rather than repath around. You sure you aren't talking about the old one?

When did I mention SC2?

You didn't... but the OP did. That's what this thread is about. Your comment about re-pathing around people in the way was not correct in the arena of SC2.

Quote: Original post by CodekaI can think of a few ways to do it. One could be that all units that have line-of-sight to each other define a single "flock" and each "flock" generates their own path.

Ack! You do NOT want to do a ton of LOS checks just to see if a group is together. That would almost be worse than running A* for all the members.

Quote: Original post by InnocuousFox
Ack! You do NOT want to do a ton of LOS checks just to see if a group is together. That would almost be worse than running A* for all the members.

That might depend though on what you're already doing. If you have a LOS manager that is already maintaining a database of LOS statuses between the whole n^2 worth of units then this would be "free". A typicaly LOS manager amoritizes LOS checks over frames so you do no more than X per frame at the cost of some per-frame accuracy (so maybe a latency of up to ~250ms for the accuracy of a given LOS status). There are many other reasons you want LOS between units (though typically not between allies). It's very likely that they have this system in place; we certainly had one on every RTS or FPS game I've ever worked on.

However, LOS does seem like a strange way to go about group determination in an RTS. You already have various meta-data available. For instance groups can simply be determined by what units were selected together when an order was given. It would be informative to experiment to see what happens if you have 2 groups of zerglings and order them separately to attack a given unit. Do both groups flock together or flock independently?

-me

Quote: Original post by InnocuousFox

Quote: Original post by CodekaI can think of a few ways to do it. One could be that all units that have line-of-sight to each other define a single "flock" and each "flock" generates their own path.

Ack! You do NOT want to do a ton of LOS checks just to see if a group is together. That would almost be worse than running A* for all the members.

Well, that's why I also thought of the "touching" algorithm, which certainly seems more likely.

This actually looks similar to something I've been doing with particles. It's pretty easy and efficient to set up mutual seperation based on some sphere, which would translate well to seperating units based on their bounding sphere.

If you look to the video to around 4:50, you'll see that incoming units just move to the target location, while pushing away anyone within their 'bounding sphere'. If you just enforce this seperation constraint for all units, it would work out like this. The pushees also seem to slide aside rather than really walk, so it really looks similar to a cheap particle seperation simulation.

It's still awesome to apply this to RTS units, but it would be less mathy than suggested.

AIGameDev.com sent out this snippet yesterday to advertise their Game AI Conference in Paris later this year:

Quote: Recently, two videos have surfaced with demos of what I'd call "modern"
pathfinding in a RTS. Basically, technology that goes beyond just using A*
to plan shortest paths for each unit. In this case, SC2 stands for both
StarCraft 2 and Supreme Commander 2! Here are the videos:

FlowField Pathfinding in Supreme Commander 2
http://j.mp/8X2fBA (GameTrailers.com)
350+ Unit Zergling Swarm in StarCraft 2: Pathfinding Demo
http://j.mp/cvaKSK (YouTube.com)


The general concensus here is that A* is still used of course; in the
StarCraft 2 you'll see the group of zergling split into two around a large
obstacle, which is a sign that there are at least two shortest path
searches: one for each side. What's interesting there's a fluid-looking
simulation in there also, so the first units that arrive at the target get
pushed outwards by the latter units. It could be done using reactive
avoidance behaviors, but I'd be a little surprised as I've never seen it
look this good! A global fluid-like solver would probably help with
performance over many local avoidance queries.

Supreme Commander 2 actually mentions that their work is based on the
Continuum Crowds paper by the University of Washington.

Continuum Crowds: Project Page
http://grail.cs.washington.edu/projects/crowd-flows/


This kind of technology definitely uses a global fluid-like solver to help
units deal with dynamic obstacles better. The implementation seems very
robust, in particular when the two groups move through each other and one
is sent new orders half way through. It'd be interesting to see how
StarCraft 2 deals with those situations of having two moving groups heading
towards each other, or checking if indeed flow lanes are formed around
large obstacles.

Apparently these two videos are making the rounds [wink]

Quote: Original post by remigius
If you look to the video to around 4:50, you'll see that incoming units just move to the target location, while pushing away anyone within their 'bounding sphere'. If you just enforce this seperation constraint for all units, it would work out like this. The pushees also seem to slide aside rather than really walk, so it really looks similar to a cheap particle seperation simulation.

I agree... but the reason I think it is more than simply that is the individual units don't START straight at the target. They compress towards a stream as if they are waiting their turn slightly. That's why I believe they are also trying to get near the "main path".

Quote: Original post by swiftcoder
AIGameDev.com sent out this snippet yesterday [...]:

Quote: [...]
The general concensus here is that A* is still used of course; in the
StarCraft 2 you'll see the group of zergling split into two around a large
obstacle, which is a sign that there are at least two shortest path
searches: one for each side.
[...]

It's not obvious to me that this implies that A* is done twice. It could simply be that the repulsion terms in the flocking push some agents onto the other path. It's these kind of issues that, again, make me interested in how much deliberative planning is done vs. reactive stuff.

I agree. If they are only generally trying to stay near the path, but are being pushed by their fellows, splitting around obstacles (including ravines) is no big deal.