The Mechanics of SC2 [Part 1] - Page 4

On June 23 2010 18:12 InPlainSight wrote:
I'm very interested in the way that path finding in sc2 works and I question whether A* is not used at all in Sc2 as it seems like the optimal path finding process for terrain traversal. Undoubtedly there are some very clever algorithms that could include steering that go into unit interactions but due to the grid base nature of building placement as well as some terrain like cliffs I would think that A* would still be in use.
I have actually been attempting to emulate the pathing in sc2 as a side project and have found a close estimate to how units move in sc2 through the use of A* in coordination with a system where units move- regardless of other units- then push each other apart allowing units to move towards there intended destination whilst not blocking each other. When units stop they simply get pushed by units who have a destination and do not pursue a destination of there own, this allows for units to move apparently unhindered through a large group of units and for them to appear to part.
Unfortunately I'm not educated on steering mechanics but your hypothesis to do with unit collisions there seems very strong, interesting post.

On June 23 2010 18:42 intrigue wrote:
i thought this was gonna be another long blob of text saying nothing, but i'm very pleasantly surprised. i would like to read the next articles =]

could you please explain this image a bit please? i'm not quite sure what i'm looking at, but it seems cool - purple line indicates direction of travel, orange circles are collision radii, and blue lines are the recalculated routes? what are the green circles/lines?

Capture the Flag: a single (bluish) attacker attempts to reach a central goal while four (reddish) defenders try to intercept ("tag") the attacker before it gets to the goal. The playing field is optionally littered with obstacles. This benchmark was proposed by Marcin Chady of the Working Group on Steering of the IGDA's AI Interface Standards Committee. The obstacles are spheres, depicted by their equator. Press F1 to add an obstacle (up to 100 of them), F2 to remove one. The "game" ends when the attacker reaches the goal or a defender tags the attacker. The demo automatically restarts a few seconds later. The attacker combines three basic steering behaviors: goal seeking, evasion and obstacle avoidance. The defenders combine pursuit and obstacle avoidance. A key to "non-stupid" behavior by the attacker was to notice when there is a defender-free "corridor" between it and the goal. When found, this corridor is depicted by a green outline. In this case the attacker uses pure seek and stops evading nearby defenders. The pursuit behavior of the defenders needed to specialized so that they "knew" not to predict the motion of the attacker past its goal. The defenders do not otherwise think about global strategy, for example they don't try to place themselves between the attacker and the goal. Currently defenders ignore each other, they probably should separate or avoid collisions with each other, ideally they would coordinate their pursuit. The attacker is easily confused when several defenders converge from different directions. Obstacles are always avoided by going toward the nearer edge, as discussed in the Steering Working Group's forum, this is frequently the "wrong" direction when considering the agent's other goals. I want to revisit this later.

On June 23 2010 19:19 sinn wrote:


Okay I'm a computer science major and I fully understand the A* search algorithm. I read your article and i did enjoy seeing the concept in use before my eyes. You'll have to forgive me, however, because I noticed one little thing that bothered me because I didn't understand it - why is the tile directly to the left of the red tile pointing to the lower right? Shouldn't it be pointing down? What kind of heuristic is being used here, lol

On June 23 2010 15:47 n.DieJokes wrote:
This is awesome, thank you. If you don't mind me asking, how did you learn all this? Are you a game developer

On June 23 2010 18:43 figq wrote:
Curious to test how the splitting around obstacles works - does it use probabilistic A*. What I mean is: send your army forward, and it has to go left and right around some obstacle; 40% split one way, 60% split the other way etc. I doubt this is done by pure individual swarm-AI, without analysis of the whole army composition. Maybe that's the main difference - they analyze the whole army for a given moving order separately, so if you reselect and reissue the same order, the behavior changes. I'm not sure, but is this the same in BW? - i think not, i think the unit there was choosing its own path and all units fighting for the same spot, regardless of army composition.