This will be the beginning of a multipart series on the differences of the mechanics of BroodWar and Starcraft 2. It will outline the pros and cons of each, with specific points and examples that hopefully everyone can understand and relate to. People prefer short and sweet, so I will try to get as close to that as possible, hence dividing this article into many threads over time.
What I intend to achieve is to allow more informed discussions about the mechanics of Starcraft 2. I often see irrational replies in threads that are mis-informed due to different use or lack of understanding. BroodWar fans end up looking like stubborn people who don't like change, and Starcraft 2 fans end up looking like people who want to win without trying.
Many of the points represented in this article will consist of estimations, I did not program BroodWar or Starcraft 2 so it's natural that there will be a lot of guess work on my part. Also please take my opinions with a grain of salt and make up your own opinion. Fact is fact, opinion is opinion, this article will contain elements of both.
Unit Control (Part 1) Unit Control involves the ability to for players to move units in a way that makes them more effective individually, whether it be dealing damage, avoiding damage, or effective movement.
As Unit Control is such a broad topic, this also will have to be split into a few parts. Part 1 will cover aspects revolving around pathfinding.
Pathfinding Starcraft 2 uses an AI pathfinding technique called flocking or swarm AI, the effect is coordinated movement the same as what you get with a school of fish or a flock of birds. Most likely Starcraft 2 uses an advanced algorithm that finds the fewest amount of waypoints and allows autonomous steering behaviour for units to smoothly hug their way around obstacles and other units.
From a purely development perspective Blizzard has done an extremely good job with this, it's quite a specialised field and there isn't a lot of information on it, with 200 units and chokes and obstacles everywhere it still works very efficiently and flawlessly. It is a technique which is highly regarded in the game development community, so it's understandable why Blizzard did it. Until I started playing BroodWar I also spent a long time trying to learn how to code this too.
BroodWar works a little differently. On an isometric map where each unit can only go in 8 directions, coupled with much lower processing power, this calls for a much more primitive pathfinding algorithm. The most common pathfinding algorithm in this situation would be a tile-based A* (A-Star) algorithm and just by looking at the units I would say this is a pretty good guess.
Tile-based A* Pathfinding Example
BroodWar Dragoons showcasing the A* algorithm
The map is filled with many nodes layed out like tiles, each unit follows these nodes one by one until they get to the destination, the nodes that units can take become waypoints. So while Starcraft 2 can avoid collision by using steering behaviour to hug their way around the small radius of another unit, BroodWar units are constrained by the fact that they are competing for waypoints. This is the main reason why you get much better surround in Starcraft 2 than in BroodWar., but also the reason why units have to spread out so much to move around.
Slight offsets cause the mutalisks take different waypoints when turning 180 degrees
Emulating BroodWar pathfinding by spamming waypoints towards a destination
The difference is that BroodWar relies almost solely on A* to get the units to move from one point to another, mapping every single node the unit needs to traverse over. In Starcraft 2, it seems that a lot of the pathfinding is left up to the unit individual, and waypoints are kept to a minimum.
Collision avoidance is also much more primitive in BroodWar as well. Units avoid collision by stopping to give-way while another unit moves around it or calculates a new path, this is probably one of the first things you learn about dealing with collision avoidance between units. You often see this in BroodWar with worker scouts, when one stops, and the other goes around, or both the players forcefully try to move them past and all it does is hold both the workers up.
In Starcraft 2, units will avoid obstacles and other units (but also flock together) using steering behaviour. Logically, every unit has sensors which when colliding with another unit, will signal for the unit to turn in an appropriate direction to avoid it. This allows units to weave in and out without calculating a whole new path or losing momentum, in a worst case scenario the units can ignore the collision radius, allowing for more fluid movement and higher movement efficiency overall.
OpenSteer: An open source library for autonomous steering behaviour
BroodWar zerglings are busy deciding who goes first, while SC2 zerglings start turning before they even get there
A lot of BroodWar fans dislike the new pathfinding AI and there's good reason to. One of the most effective tactics in the early game is flanking. If units move in a perfect tight ball, flanking will be useless, period. The reason zerglings dish so much damage to marines when they are spread out is because marines are ranged and zerglings are melee units. If you can effectively reduce the "surface area" of your army, your army will receive much less damage. This also becomes a compounded effect due to the difference in army size and damage growing bigger and bigger after each death.
Flash vs Effort (OSL Finals Game 3). Flash's un-attended marines competing for the same waypoints form a spread-out line, Effort punishes this with a well-timed zergling flank killing all the marines. Had Flash concentrated on his marines, this wouldn't have cost him the game
The other issue is that ideally, the amount of effort focused on unit movement should directly correlate to their effectiveness. Players that don't attend to their units should be able to be punished. However in Starcraft 2, there is a feeling that the AI can move the units better than humans, meaning that you get the opposite effect.
I can also see how bad unit movement can be frustrating for newer players, there is nothing worse for blizzard than to show what looks like an un-polished game. I believe that units should spread out if you carelessly move them about, but they should also not glitch out all the time due to bad pathfinding AI. We do not need to have people "fight the interface" to create good gameplay mechanics, but we still need the side-effects that improve gameplay as a result.
"Auto-surround" due to better pathfinding can be mitigated. Zerglings are faster off and on creep in Starcraft 2 than they were in BroodWar. Reducing the Zergling's on-creep and off-creep speed back to that of a worker and widening the radius means that an effective surround is necessary to take out a scouting worker, thus the skill of worker scouting can once again become a defining feature of good play.
A badly executed surround allows the probe to live on to fight another day
In a later issue, I will talk about Starcraft 2's extremely high rates of fire which also severely affects flanking ability and other mechanics. The next issue however will be about magic boxing and stacking, following that, probably moving shot.
This is a very cool article. Its nice to see the mechanics behind what we have all noticed, but just don't know enough about to put into an intelligible post. I'll be looking forward to your expansions on this, and how they tie together.
It's true that autosurround makes the game easier with regard to melee units. On the other hand, I really like the aesthetic effect of swarming over a group of marines with superfast zerglings in SC2 -- it's beautiful and feels cool.
So while I respect your plea, I think this is a mechanic perhaps best left to BW. Your solution of lowering zergling speed seems like a huge sacrifice simply to encourage possible worker surrounds. Your proposal of having zerglings (etc) spread out when you don't tend to them is interesting, but I'm not sure anyone really understands what you mean. How would they "spread out''? When are they "moved carelessly"? How would this encourage interesting gameplay?
In the end, I think we're stuck with autosurround, and I'm not sure that's bad. Manual surrounds are just a different mechanic for a different era.
Great read. From a more casual perspective I think that the improved AI is great. As the game evolves the better players will learn how to manipulate their units in creative ways.
Im looking forward to the firing rate article. My biggest struggle with sc2 so far has been how quickly the battles end.
On June 22 2010 22:48 kajeus wrote: It's true that autosurround makes the game easier with regard to melee units. On the other hand, I really like the aesthetic effect of swarming over a group of marines with superfast zerglings in SC2 -- it's beautiful and feels cool.
So while I respect your plea, I think this is a mechanic perhaps best left to BW. Your solution of lowering zergling speed seems like a huge sacrifice simply to encourage possible worker surrounds. Your proposal of having zerglings (etc) spread out when you don't tend to them is interesting, but I'm not sure anyone really understands what you mean. How would they "spread out''? When are they "moved carelessly"? How would this encourage interesting gameplay?
In the end, I think we're stuck with autosurround, and I'm not sure that's bad. Manual surrounds are just a different mechanic for a different era.
Yea the aesthetics are very pleasingl.... I love when a patch of zerglings are running through a slower group of hydralisks... Its especially cool when they switch directions.... The swarm!!!!
So that's why marines feels that they have tougher skin than SC BW, cause of it's intelligence in path finding than their predecessor. Goodjob at explaining :D
Really good article, an interesting read for sure.
I think I disagree about your line: "A lot of BroodWar fans dislike the new pathfinding AI and there's good reason to. One of the most effective tactics in the early game is flanking. If units move in a perfect tight ball, flanking will be useless, period."
It's shortsighted to say that this is only a negative thing, right? I mean, commentators like Day[9] have been spending the entire Beta lamenting the "one-control group syndrome" that leads to these perfect tight balls. The reason being that AoE abilities like storm, fungal growth, Collossi, etc really eat into groups like this, and units can really be caught out of position.
Lamenting the end of BW flanking is in some ways like the moving shot debate. It's a relic of an old engine, and wasn't likely to be replicated in a new engine. But this new engine has it's only quirks and limitations and it's just a matter of time until they're found. Then when SC3 comes out, we'll lament the end of those things.
On June 22 2010 22:48 kajeus wrote: Your proposal of having zerglings (etc) spread out when you don't tend to them is interesting, but I'm not sure anyone really understands what you mean. How would they "spread out''? When are they "moved carelessly"? How would this encourage interesting gameplay?
I think his point about spreading out is that if in BW you got a whole bunch of marines and A-clicked the other side of the map, they would spread out into a giant conga line and get owned by flanks, whereas in SC2 they stay in a very tight ball and flanks aren't as effective. He wants it so you have to baby sit your troops more carefully when moving your army.
I prefer how it is in SC2, bad pathfinding is the biggest problem with almost every RTS. I used to love WC3, but since playing SC2 I just can't play it any more because the god damn units just spaz out all the time.
On June 22 2010 22:56 Takkara wrote: Really good article, an interesting read for sure.
I think I disagree about your line: "A lot of BroodWar fans dislike the new pathfinding AI and there's good reason to. One of the most effective tactics in the early game is flanking. If units move in a perfect tight ball, flanking will be useless, period."
It's shortsighted to say that this is only a negative thing, right? I mean, commentators like Day[9] have been spending the entire Beta lamenting the "one-control group syndrome" that leads to these perfect tight balls. The reason being that AoE abilities like storm, fungal growth, Collossi, etc really eat into groups like this, and units can really be caught out of position.
Lamenting the end of BW flanking is in some ways like the moving shot debate. It's a relic of an old engine, and wasn't likely to be replicated in a new engine. But this new engine has it's only quirks and limitations and it's just a matter of time until they're found. Then when SC3 comes out, we'll lament the end of those things.
At least, that's my hope in all this.
You're absolutely right. "Careless spreading out" would effectively nerf fungal growth, storm, colossi, siege tanks, etc.
It could be lamented as causing the game to require LESS micro!
On June 22 2010 22:56 Takkara wrote: Really good article, an interesting read for sure.
I think I disagree about your line: "A lot of BroodWar fans dislike the new pathfinding AI and there's good reason to. One of the most effective tactics in the early game is flanking. If units move in a perfect tight ball, flanking will be useless, period."
It's shortsighted to say that this is only a negative thing, right? I mean, commentators like Day[9] have been spending the entire Beta lamenting the "one-control group syndrome" that leads to these perfect tight balls. The reason being that AoE abilities like storm, fungal growth, Collossi, etc really eat into groups like this, and units can really be caught out of position.
Lamenting the end of BW flanking is in some ways like the moving shot debate. It's a relic of an old engine, and wasn't likely to be replicated in a new engine. But this new engine has it's only quirks and limitations and it's just a matter of time until they're found. Then when SC3 comes out, we'll lament the end of those things.
At least, that's my hope in all this.
You're absolutely right. "Careless spreading out" would effectively nerf fungal growth, storm, colossi, siege tanks, etc.
It could be lamented as causing the game to require LESS micro!
U forget that spells like Storm were much more stronger due counter the "spreading out" of units from primitive AI.
Thank you for the excellent post. It's a good short read up that can really benefit your micro if you use this information well. Units behave so differently from BW that micro has to take on different shapes and forms.
Can you give examples of what players can do to improve on the built-in pathing, swarm-effect, etc? I think a major problem with players now is the "one control group" syndrom; people group all their units in one group, and while it makes for effective attacks early on, you really benefit from getting a bigger concave later on in the game. This can be achieved bu just splitting one control group hap-hazardly into two, and moving the groups seperately.
What options do players have to improve their micro, movement-wise?
On June 22 2010 23:11 exnomendei wrote: Thank you for the excellent post. It's a good short read up that can really benefit your micro if you use this information well. Units behave so differently from BW that micro has to take on different shapes and forms.
Can you give examples of what players can do to improve on the built-in pathing, swarm-effect, etc? I think a major problem with players now is the "one control group" syndrom; people group all their units in one group, and while it makes for effective attacks early on, you really benefit from getting a bigger concave later on in the game. This can be achieved bu just splitting one control group hap-hazardly into two, and moving the groups seperately.
What options do players have to improve their micro, movement-wise?
You could artificially create one on the spot by spamming waypoints till they form a line (as long as you break the magic box, the radius is 6 distance units wide, if your group is bigger than that it will form a line). If you continue to move in the direction of the line they should stay that way, then if you move sideways they should form a concave faster than normal.
Worth a shot if you think that units take too long to form a concave (its a bit risky though), the other thing though is you can just attack -> move -> attack and hold that ball so then all your units are in range already.
Unfortunately SC2 doesn't give you that much control in that regard, but ill hopefully have more tips with magic boxing and stacking as they are available in SC2 (although not as useful).
Its more about explaining though more than anything else
Really well put and I'm really looking forward to Part 2. I'm currently doing an Engineering Degree in Programming (Think that's what It's called, you'll have to forgive me, I'm French >_>) and Path finding really is an interesting subject, I have learned a whole bunch about it and I'll definitely be digging out OpenSteer.
Just wanted to add that the congoline thingie happens in sc2 sometimes too, this is usually caused by a very narrow choke, like the one on DO.
Sorry, couldn't provide a screenshot since I can't start reps, but if you look in the top right corner, units able to fit through that choke will congoline very easily when moving from 1 base to the next.
Edit: oh yea, a+ would read again... looking forward to the next article.
Really cool. This might actually explain a lot of the map design in SC2. People complain about not having wide open middles, but really if all the units travel in a ball aren't we better off with stuff in the way that helps to create disadvantages in positioning? It'd be interesting to run some pathing tests and see what kind of terrain can help to draw and extend unit lines out.
On June 22 2010 22:57 piochelin wrote: Soooo it was the AI then... i always thinked my goons were retarded
no ur goons were retarted....seriously those things were TERRIBLE nothing else in the game was nearly that bad
They weren't terrible... I mean come on, in the words of knickknack, goons were almost cute, if you squinted a little (points to any toss player who gets this reference
On June 23 2010 01:30 clickrush wrote: This post has two major qualities: 1. solid research and 2. unbiased and not judging.
I think #2 is the most important. There's a different between bias and opinion. The OP has opinions, but is not biased, and clearly identifies opinions as such.
Nicely written. It'd be nice if you could also mention unit acceleration/deceleration in the future. The way it works in Starcraft 2 is quite different from how it works in Starcraft 1.
On June 22 2010 22:29 sluggaslamoo wrote: Players that don't attend to their units should be able to be punished. However in Starcraft 2, there is a feeling that the AI can move the units better than humans, meaning that you get the opposite effect.
I think players do get punished for allowing their units to clump together as dictated by the pathfinding. From a zerg perspective I love it when Terran has their MM ball rolled together. It makes my banelings that much more effective. Splash damage and AOE damage seem much more prevalent in Starcraft 2 than in Brood War and I feel this is Blizzard's way of giving players a method to counter the AI's tendency to clump.
The only reason the AI seems better than humans at this point is because many of the game's tricks are still hidden and unexplored. Thorough research and knowledgable insight like yours help alleviate this problem and bring forward interesting gameplay.
This really helped me understand the differences. The parts about "competing for waypoints" really made a ton of sense. Nice and technical without getting TOO technical. This is really well done.
Excellent advice about reducing the "surface area" of your Infantry ball vs lings. I guess I kind of knew it intuitively, but I'll be more aware of it now that I've been through it so explicitly stated. Thanks so much!
Nice post. I think this will help a lot as maps become more open and players look for ways to form their units up into something of a moving concave (or instant surround in the case of melee units) rather than have them ball up all the time.
On June 22 2010 22:48 kajeus wrote: So while I respect your plea, I think this is a mechanic perhaps best left to BW. Your solution of lowering zergling speed seems like a huge sacrifice simply to encourage possible worker surrounds. Your proposal of having zerglings (etc) spread out when you don't tend to them is interesting, but I'm not sure anyone really understands what you mean. How would they "spread out''? When are they "moved carelessly"? How would this encourage interesting gameplay?
IMO the ultimate goal of an RTS interface should be to do what you tell it to, but to do nothing that you *don't* tell it to. If you want to bring your units together, the interface should let you, but it's *bad* that it does so for you, for two reasons:
1) If the AI is automatically bringing units together/surrounding, it is performing tactical decisions that a player should be required to make. In doing so, a player who is not good enough to make those decisions well may come out ahead in battles he shouldn't because the AI covered an area of tactical decision-making that he should be punished for not thinking about.
2) If the AI is automatically bringing units together, it makes it difficult for a player who *wants* to spread hits units out to do so.
The simple solution is for units to behave by moving in the formation they were in when they started (within reason). This way, a player can choose to bring his units together if he wants, but the AI doesn't do it *for* him. The magic boxes of SC1 behave somewhat like this, but it certainly could be refined.
Very nice analysis. I think the zergling's loss of efficiency as the game goes on is due to the clumping AI combined with the larger late-game armies, significantly less surface area per damage dealt.
On June 22 2010 22:56 Takkara wrote: Really good article, an interesting read for sure.
I think I disagree about your line: "A lot of BroodWar fans dislike the new pathfinding AI and there's good reason to. One of the most effective tactics in the early game is flanking. If units move in a perfect tight ball, flanking will be useless, period."
It's shortsighted to say that this is only a negative thing, right? I mean, commentators like Day[9] have been spending the entire Beta lamenting the "one-control group syndrome" that leads to these perfect tight balls. The reason being that AoE abilities like storm, fungal growth, Collossi, etc really eat into groups like this, and units can really be caught out of position.
Lamenting the end of BW flanking is in some ways like the moving shot debate. It's a relic of an old engine, and wasn't likely to be replicated in a new engine. But this new engine has it's only quirks and limitations and it's just a matter of time until they're found. Then when SC3 comes out, we'll lament the end of those things.
At least, that's my hope in all this.
You're absolutely right. "Careless spreading out" would effectively nerf fungal growth, storm, colossi, siege tanks, etc.
It could be lamented as causing the game to require LESS micro!
U forget that spells like Storm were much more stronger due counter the "spreading out" of units from primitive AI.
I'm wondering if this is part of the reason that many people feel siege tanks are too strong (besides the lack of overkill). Is the splash of the tank reduced proportionally to storm? I can find the liquidpedia link for how the splash works in sc2, but not in sc1.
I think that the more the game is played the less of a factor unit clumps are, in fact it becomes extremely disadvantageous. EMPs, Storms, Collossi, Banelings. They will all cause you a lot of problems if you leave you units conveniently clumped together.
But yeah, my one complaint with the current pathing system of sc2(don't get me wrong, it's way more awesome than that of broodwar, they've come a long way) is that banelings don't get priority and just wander around behind the zergling line if the lings get to the enemy first, and then ultralisks have a similar problem. I wish that the melee that deals the most damage would get priority and the grunts would move out of the way, but I guess it's nothing that some efficient micro-management can't cure...
scbw is still alive and kicking it is able to be played, personally I welcome the new changes, yes it allows newer players to not be excessively noob because controlling units is no longer illogical and requires less time to understand, I can also understand how broodwar players are annoyed at how easy the interface is used in comparison, considering they spent a large amount of time learning backwards gameplay mechanics of an outdated game,alot of professionals of starcraft1 will not transfer directly into starcraft 2 and that would definitely cause some unrest, but nevertheless the amount of new mechanics that require micro and skill are in starcraft 2 even this out, its a new game and has new styles yet to be developed please consider it, broodwar is still alive and kicking if you like those mechanics. I believe there is more thinking required and less clicks to negotiate a difficult ui (allowing for more multitasking [each task requires a few less clicks and attention])
Well written, though you hurt your case as an unbiased presenter when you say things like "BW players don't like this, and with good reason" and "here's how we can fix this."
I'd agree you did hurt your objective stance towards the center. I did enjoy the read though. I remember being frustrated when I returned to BW due to the path finding and losing a game due to the illogical movements of my units. It was a LAN game with a friend, but it stuck with me. I welcome the new AI, it will bite you if you don't pay attention, but it's a far better situation.
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.
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 do think that zerglings should get their speed lowered to that of a worker ON-creep so that my probe had somewhat of a chance to scout. However with speed upgrade it should be as fast as it is now. I like speedy lings, i just don't like un-upgraded lings catching up to my probe so easily early game.
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?
Most interesting article (series) I've read here since I've joined. Can't wait for the next ones!
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:
Great article, autonomous steering is part of my research and you summed it well from the basics of A* to the much more complex steering mechanisms used and how they influence everything. Nothing new to me but a good read for everyone else.
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
So many questions!!! :O I don't think I can answer them all sorry
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.
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.
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 .
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.
I can also see how bad unit movement can be frustrating for newer players, there is nothing worse for blizzard than to show what looks like an un-polished game. I believe that units should spread out if you carelessly move them about, but they should also not glitch out all the time due to bad pathfinding AI. We do not need to have people "fight the interface" to create good gameplay mechanics, but we still need the side-effects that improve gameplay as a result.
I really like this paragraph, especially the last sentence of it. Fighting the interface is not a sign of skill, its a sign of technology being incapable of recognizing what you want to do with your "stuff". However, there should always be methods in which you can execute in-game in order to maximize efficiency.
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.
I agree with this. From the description of the pathfinding, it seems like auto-surround is a logical step to the AI.
On June 23 2010 23:06 NaturalHacks wrote: Swede you hit the nail right on the head, are you by any chance the guy I used to play CSS with on scoutsknivez servers?
I was looking for part 2. I remember playing starcraft 1v1's for hours and feeling so exausted. I see now its becuase my units were running on outdated engines.
I think alot of Brood war fanatics (in a good way) are upset with seemingly a "dumbed down" system in SC2, yeah it's easier to accomplish things you could do in BW. But we have barely reached the beginning of advanced unit controls. For instance, what tricks and uses of the current system result in even more intelligent unit movement than before. We don't know. The basics are on par with the mid-upper level of unit control in BW, who knows what the upper level control will bring.
The biggest problem I have with the SC2 AI is that A-moving even small groups of units (under 20 units) causes them to bunch up into an ultra-tight ball. This causes the army to take MASSIVE amounts of splash damage, but at the same time take minimal damage from single-target attacks. Thus making for an environment where the 'right units' will cause a decimation for one side or the other, as it seems that one must control 8 units at a time to get them to not clump up so much. This could very well be the 'fighting the system' that happened in BW in SC2 form - BW: Units spread out a lot and get stuck on each other and just about everything, SC2: Units get stuck on nothing and clump into gigantic balls. Clearly both systems require the player to change their control methods to avoid the issues of each.
One small nitpick that's probably already been said but I've read in some old tutorials when I was learning A* back in '04 that SC used the the variant of A* that uses dynamically sized 'waypoints' (IE, if you have a map with a chose that is 3 tiles wide, you use a 3x3 way point rather than a 1 by 1 to reduce way point count). So its not always quite the simple 8 directional movement if those articles were correct.
On June 24 2010 13:04 Antisocialmunky wrote: One small nitpick that's probably already been said but I've read in some old tutorials when I was learning A* back in '04 that SC used the the variant of A* that uses dynamically sized 'waypoints' (IE, if you have a map with a chose that is 3 tiles wide, you use a 3x3 way point rather than a 1 by 1 to reduce way point count). So its not always quite the simple 8 directional movement if those articles were correct.
On June 24 2010 14:31 InPlainSight wrote: Units in sc1 also animate in 16 directions, supporting this.
Yeah I think I remember working on BW sprites a long time ago having 12 or 16 rotations, I never said they couldn't.
As I said...
On an isometric map where each unit can only go in 8 directions
It is the gridded isometric map which inherently supports 8 directions from a single cell, if the unit moves in-between those rotations it would have to skip a waypoint, the algorithm may allow it to do that, but units appear to not move in that way if possible. As shown by the dragoon pic.
The units move cell by cell and will zig-zag if they find an angle which they can't support in one movement, cell by cell movement on a fixed cell size grid will make units do this. Whether the unit can rotate in 4, 8, 12, 16, 32 directions doesn't matter, the units will still be competing for waypoints, meaning the amount that the units can rotate won't help them navigate around each other, which is the problem.
I don't see how waypoint sizing helps, waypoints usually don't have a size, and units will end up in the same position regardless of size. 3x3 ramps can fit around 6 zerglings, so I don't see how that works either. What I think you mean by dynamically sized waypoints, is that because a dragoon is a 2x2, it will move in steps of 2x2 rather than 1x1.
Keep in mind, this article isn't a tutorial on pathfinding, it discusses the types of pathfinding that causes different behaviour in BW and SC2, as it helps people understand why things like auto-surround occurs.
I'm all for debating about A* but that doesn't really belong in this thread, if you can prove that the units in BW actually behave in the way your theory suggests then by all means go ahead.
On June 22 2010 23:47 Peekay.switch wrote: One of the best article I've read on TL.
not dissing the OP, article is awesome, but even without your name being in name.identifier format it'd be plain to see you haven't read anything from before sc2 came out.
On June 22 2010 23:47 Peekay.switch wrote: One of the best article I've read on TL.
not dissing the OP, article is awesome, but even without your name being in name.identifier format it'd be plain to see you haven't read anything from before sc2 came out.
I mean it's not like you've been here from the stone age either. January of 09? You should hardly be talking down on people. And why mention it at all? The guy complimented the OP on a fantastic piece, who cares what his sample size is for "one of the best articles he's read". Stuff like this is where the whole "elitist" mentality comes from.
But really OP, fantastic work. I look forward to reading more.
I have a year in my eye of how hood this was. Without a doubt the best thread that mentioned SC2 to date. I liked the fact I didn't even know a lot of that stuff, and I really like the logic you put behind your conclusions, and your article is very nicely laid out. Amazing read and I hope to see more.
The new AI makes the game much more user friendly and allows more new players to enjoy the game. That's not to say that good players won't still dominate. The new AI will allow beginners to implement strategies and moves that they watch the pros pull off without having a ridiculously high APM only achievable by dedicating all your time to StarCraft.
The balling effect is not always a good thing. How your units are positioned in the ball can make a huge difference.
For example, if you have 12 lots + 6 stalkers vs 12 marines and 12 marauders. With the AI ball, your stalkers are in the front due to their faster walking speed. If you engage with that ball your stalkers will block the path of the lots causing them to run around the front line of stalkers.
So, you can still be punished for not paying attention to your moving army.
On June 22 2010 23:47 Peekay.switch wrote: One of the best article I've read on TL.
not dissing the OP, article is awesome, but even without your name being in name.identifier format it'd be plain to see you haven't read anything from before sc2 came out.
Always used that format for my names before SC2, I Don't see how "flaming" me for no apparent reason is necessary. Have you brought anything to this topic? I'm kind of new, but have been lurking these forums for a while and as far as I know, there is nothing stopping me from reading older articles.
As I mentioned, the reason why I thought it was one of the best article I've read on TL is because it is linked to my study field. The author managed to explain in depth a rather complex algorithm, but you would know that if you read more than 2 lines of my post.
And besides, isn't that how Opinion works? I can think something and you can differ on it? I've read a bunch of FE, thought they were ok, this article however, I really liked, which is one of the reason I posted, because I Am really looking forward to part 2.
If you've got something else to bring up, feel free to do it in PM.
Once again, really looking forward to Part 2, hopefully it'll be soon!
Interesting read, its important for people not to confuse nostalgia with decent ideas. Just because this isn't how BW worked doesn't instantly make it bad, and as other people have already pointed out, sc2 with things like fungal growth, collosi is really tailored to work around the mechanic explained here
EPT![[image loading]](http://www.policyalmanac.org/games/aStarT7.jpg)
![[image loading]](http://file.steamdc.com/img/starcraft/dragoon_path.gif)
![[image loading]](http://file.steamdc.com/img/starcraft/mutalisk.gif)
![[image loading]](http://file.steamdc.com/img/starcraft/lings_path2.gif)
![[image loading]](http://file.steamdc.com/img/starcraft/steering.gif)
![[image loading]](http://file.steamdc.com/img/starcraft/lings_path.gif)
![[image loading]](http://file.steamdc.com/img/starcraft/lings-flank.gif)
![[image loading]](http://file.steamdc.com/img/starcraft/zergsurround.gif)
I want to become a game-designer or developer in the future though.
