The Mechanics of SC2 [Part 1] - Page 4
Forum Index > SC2 General |
Worstcase
Switzerland45 Posts
| ||
SC2Phoenix
Canada2814 Posts
| ||
NaturalHacks
New Zealand77 Posts
| ||
SiNiquity
United States734 Posts
| ||
FarbrorAbavna
Sweden4856 Posts
| ||
TheGrimace
United States929 Posts
The removal of the 1 control group syndrome and 1a mentality would lessen the punishment you can dish with storm, banelings, fungal growth and tanks. A player being less attentive can still be punished, I don't think the new AI is really a con to the new engine, just a new way to play the game. I'm excited to see what we end up with. | ||
Merikh
United States918 Posts
| ||
InPlainSight
New Zealand40 Posts
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. | ||
pzea469
United States1520 Posts
| ||
intrigue
Washington, D.C9931 Posts
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? | ||
figq
12519 Posts
I think, as InPlainSight said, that A* still exists, supporting the steering swarm-AI. It's just that now it works on a set of circles / obstacles, as geometric algorithm, instead of a set of grid points, which has been more like a pure graph algorithm. In other words, the movement is not restricted by the grid, which Blizzard would have implemented in the past, if they could, but they couldn't, back then - the computation power wouldn't allow. That's why SC2 also needs significant CPU power, not just for the graphics, and it gets much worse if you have larger armies. 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. EDIT: if you want to get a sense of a swarm AI with similar pathfinding, steering and moving, here's an example from the RoboCup simulation league: | ||
Clearout
Norway1060 Posts
| ||
opiuman
United States187 Posts
| ||
stalife
Canada1222 Posts
| ||
sinn
United States132 Posts
On June 22 2010 22:29 sluggaslamoo wrote: Tile-based A* Pathfinding Example 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 | ||
sluggaslamoo
Australia4494 Posts
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. I never said A* wasn't used at all but I doubted that Tile-Based (or grid based) A* is used in SC2. Instead I would say that all the nodes only exist on the edges of obstacles. A different heuristic is used to traditional A* as well, try moving a unit around an edge the same way as I did with the dragoons and the unit will only tip the corner rather than hugging the wall first in SC2. Steering behaviour relies on 3 basic principles, separation, alignment and cohesion. It is a pro-active solution that gets units to move in a single cohesive group rather than the reactive solution of pushing units apart. 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? It is an automated capture the flag game, between AI units. The blue unit in the center is the attacker, the red units are defenders. The green lines are actually part of a rectangle which stretches between the attacker and the flag. However the bottom of the rectangle sits 90 degrees to the direction of the attacker. There are other green lines which indicate a "corridor" between defenders, where the attacker can continue to go through. The blue line indicates the direction in which the attacker is going to travel, it only goes left or right, the angle is not important. The green circle seems to get closer to the defender as they get closer to the attacker, but I have no idea what it represents. This might help explain 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 The arrows just points to the best tile in the open-list (from that tile) you can use in order to go back to the start. Pretty useless, and I would just ignore it. The heuristic is the manhattan distance to the red square. | ||
lololol
5198 Posts
| ||
sluggaslamoo
Australia4494 Posts
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 Not really, I've just been programming indy games for 10 years since I was 9 years old I want to become a game-designer or developer in the future though. Currently doing a Bachelor of IT which has nothing to do with games, and more to do with IT business than programming A high stable income is the most important thing for my future. I can always do fun stuff in my spare time. 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. While I don't think so either, pure steering behaviour can easily handle that problem on its own. I don't think its as complicated as you make it out to be . | ||
stet_tcl
Greece319 Posts
Looking forward for the next parts | ||
Swede
New Zealand853 Posts
I think that the AI in SC2 is exactly what it should be, for the most part (and no I don't want to win without trying). The AI should do exactly what you tell it to in the simplest way possible. It doesn't make sense for a ball of units moving at the same speed to spread out over a distance. That means that the outlying units will travel a significantly longer path than the ones closer to the center, and it means that when they near their destination (assuming they don't get interrupted by enemy units) they would have to converge again or remain split up. If they remain split up then they haven't achieved what you told them to do as effectively as possible (ie, they are not as close to the original destination as you planned). The only argument that I can think of for why they SHOULD split instead of remaining in a ball is that that is how it happened in BW (unless someone can argue otherwise?). It doesn't seem sensible to make units less logical and realistic for the purpose of making the game "harder"... Which it doesn't anyway. The new system makes manual splitting much more important to avoid splash damage type attacks (among other things). And on auto-surround... I don't think it's a big deal. It's exactly what I said above - each unit is calculating the simplest and most efficient path to perform the action you ordered (ie attack). If there is 1 Zergling already attacking a Marine, the next Zergling shouldn't attempt to attack that Marine from the same position, it should move to the next closest position and attack from there. I think auto-surround was terribly mislabeled. It's not like Zerglings split into a perfect concave preemptively. Really it's just the units NOT being incredibly retarded. Besides that, the efficiency of a surround can still be improved immensely by microing, and so I don't believe that the amount of skill has been reduced at all. | ||
| ||