The StarCraft path-finding hack
codeofhonor.com
codeofhonor.com
For example, the game was not designed to give mutalisks the ability to stack on top of each other. However, at some point in the early 2000s, it was discovered that when 11 mutalisks were grouped with 1 overlord, the mutas tended to stack: http://www.youtube.com/watch?v=NfqQYJzq7o0 . This meant that an attacking player could deal the damage of 11 units while only exposing the surface area of 1 of them. Using this technique, a pro gamer named July won the 3 OSL tournaments: http://wiki.teamliquid.net/starcraft/July .
With respect to the path-finding behavior described in the article, there is a funny aspect the author doesn't mention: mining workers still collide with buildings while mining, just not other workers. This lead to a technique known as the manner pylon: http://www.youtube.com/watch?v=EmS2ghQyAYI . If a protoss player builds a pylon in their opponent's mineral line with great timing, they can trap their opponent's workers between the minerals and the pylon. This renders the workers useless until the pylon is killed.
In Starcraft-speak, "manner" means being respectful (such as saying "good game" when you lose). The manner pylon got it's name because it is so incredibly annoying to deal with, it will cause anyone to lose their manners.
For those of you who might be familiar with Starcraft, but not the competitive scene, you should know that pro players are executing these techniques at a rate of hundreds of APM (actions per minute): https://www.youtube.com/watch?v=Z4UTDudShDY
Edit: Found him, Zileas aka Tom Cadwell. Brings back the memories.
(Can't believe I remember these details.)
It makes for a good story, and it's great fun for the person who discovers it. Players like it, because it lets them beat new players even more easily. But players don't always know what's best for them.
This is why Starcraft 2 multiplayer is structured to force players to play on complicated, resource balanced Blizzard approved maps. Starcraft 1 allowed ranked games on any map, and players largely played simplified, resource-soaked maps. Or played nothing but Big Game Hunters and Lost Temple. This was what players thought they wanted, but it wasn't what was best for the game.
Both SC2 and BW have two sets of maps, UMS maps with custom settings used for fun games and competitive maps made to be racially balanced and produce "good" games. In SC2 UMS maps are part of the arcade where as ladder games are played on tournament maps. The same is true for BW but blizzard didn't have an official ladder so 99% of the games on battle.net were UMS maps, but ICCUP ladder had the same competitive maps you see in SC2.
As far as the glitches are concerned, they were undoubtedly beneficial to BW, as the last balance patch was in 2001 when the game was in its infancy as far as strategy goes. For example TvZ could not be played in its current form without muta stacking and terran's still have more success despite it. 99% of players would never use these tricks of have them used against them, but it allowed for the game to advance strategically and added an additional element of skill.
As a result, in competitive play, players would leave one or two units at home, when they advance they would select all their front line units and move forward, when they retreat they would select all their front line units plus the units at base, and flowfield would cause the front line retreat to exceed unit velocity!
In the mutalisk stacking example, it ended up being a very good thing in terms of metagame balance. At the time, top Zerg players were having tremendous problems breaching Terran static defenses, and it proved to be relatively "fair" for them to have that option in the mid-game. Also worth noting is that just because it's simple doesn't make it easy; it still required good APM/Micro to manage and a solid understanding of the magic-boxing techniques.
Even now, in SC2, the idea that workers don't collide with each other when given a command to mine a remote mineral patch is necessary at high levels of play to use the drone drilling technique in order to avoid a pylon ramp-block, which is an extremely simple technique for the protoss to use, but disproportionately difficult situation for the Zerg to deal with. Even with the drone drilling technique, it's still relatively uphill and requires good micro. (see http://www.youtube.com/watch?v=M9CA9AahV1E )
As for the complicated "Blizzard Approved" maps, they're present in the ladders, but most have tweaks. Of particular note are the GSL (A/THE pro-league in south korea) maps that actually include a neutral supply depot at the bottom of the main ramp to prevent pylon ramp-blocks from being viable so as to prevent drone drilling from being necessary.
Similarly, KESPA (korean e-sports association) was one of the driving forces for map balance in brood war, and their version of the Lost Temple was considered very balanced for reasons much more strategically significant than "people like it".
It's worth pointing out that I've seen a similar argument made for Street Fighter 2: that a lack of rebalancing is what made it such a popular tournament play, or some such.
Prior to this trick's discovery, players stacked mutalisks by right clicking the group onto a mineral patch or gas geyser, which causes them to clump up more than right-clicking onto the ground (July, who you mention, actually won at least the first 2 OSLs without the benefit of this trick). I would imagine that air units in Starcraft have a similar hack applied to their moving collision detection as the workers do with mining, as the exhibit a lot of the same behaviors (okay with being on top of each other while moving, spread out as soon as they stop moving).
For instance, an everpresent threat in Starcraft is the Zerg Rush, in which a player skips building an economy to build zerglings---cheap, light, raider units--- to attack the opponent early before he has any defenses (as he, presumably, has not skipped building an economy). The zerglings are melee attackers, so holding a small choke point is an effective way of only allowing one or two zerglings to attack at a time, even if there are more (usually 6-8).
Of course, this poses a problem---if the tight spaces allow only two zerglings to attack, that's great, but the tight spaces also only allow two of your workers to fight back. Actual fighting units will slaughter worker units, so you've merely slowed your death, not prevented it.
Except! By ordering all your workers to harvest the same mineral patch, you can activate this collisionless behavior described in the article, and then fit your "super-group" of ten or so workers into small spaces---to fight the two zerglings at a time. The workers can definitely win now!
This has become a giant wall of text, but this is actually basic, easy, essential knowledge for the competitive starcraft 2 player, so it's fun to see its origins in this article.
To combat this you had to devote significant resources to units and buildings that could reveal invisible units, and eventually Blizzard patched it. Very interesting.
How the pathing trick is actually used to deal with zerglings is to have them walk ontop of the zerglings with the mineral trick and then attack, causing the workers to spread out around the unit trapping them while have the maximum amount of surface area to attack, as seen in this video. http://www.youtube.com/watch?v=X08jueOiGFk#t=140s
[1] http://gaming.stackexchange.com/questions/51630/why-are-ther...
[2] http://wiki.teamliquid.net/starcraft2/Buildings#Neutral_buil...
BW however did have a few bugs that were banned by tournament ogranizers [1].
I remember when I played Warcraft 2 (also mentioned in TFA) competitively (WC 2 wasn't meant to be played on the Internet, but we'd use Kali to simulate a LAN over the Internet and then we'd use trust-based ranking websites)...
The "build" was to put two barracks (or any other building) just touching each other by a corner and you'd then put three units in a special formation: then any rush would result in the rusher only being able to attack with one unit while you'd have three units hitting the attacker.
Needless to say rushes weren't a big part of the game in WC2 ; )
Really enjoyed this part of the article. When you have an infinitely long two-month period, you still can't complete a task that requires three months.
I guess it's comforting to know that even elite development teams also struggle with code design. I wonder how far off the branch the Carrier unit was that required it to have its own reimplemented features...and what kind of features needed to be reimplemented for it? (story-game events, path-finding?)
The unit, by itself, is closer to a building than an actual unit, because the player has to manually queue up interceptor production, which has a resource cost and takes time.
Since it does spawn the interceptors to attack, there are a lot of behaviors that it shows that other units don't. For one, the maximum range to a target where it can start to attack is fixed, like most units. At that range or lower, the carrier will launch it's interceptors, which will attack the target. However, there is also a longer "leash" range, where the carrier can move away from the target, after the interceptors have been launched, and they will keep attacking the target until the carrier goes out of the range, at which point the interceptors will go back to the carrier that spawned it. An explanation of this behavior can be found here: http://www.youtube.com/watch?v=1Rqx8s2qKXM
Also, when the carrier dies, all interceptors that it has launched die.
The engine wouldn't have been particularly flexible about that kind of thing, as almost every other unit has either a direct "shoot guns at the target" attack or no attack at all. The two exceptions to this were the Protoss carrier (air) and reaver (ground). Reavers would have been a bit simpler because their projectiles just find a path to the target and blow up; there's no need for swarming behavior, returning to the carrier to recharge, etc.
It's also a testament to Blizzard's dedication to polish, because although I was only ever a casual Starcraft player, I spent more hours on that game than any other game in my life and I never noticed any bugs that betrayed the apparent messiness of the codebase.
They had the same sorts of constraints, go from here to there, don't cross certain types of 'terrain' (traces in the layout case). Game units don't get to make vias though :-)
Circuit routing is an entirely different beast. A previously routed "shortest" trace from one node to another can obstruct a much shorter trace between two unrelated nodes. In this way it's similar to the traveling salesman problem, where early "greedy" choices made by the salesman can force him to make much less efficient choices later.
I remember circuit routing was an example in Skeina's Algorithm Design Manual [1], and believe he proved that it was indeed NP-complete, not polynomial like the general pathfinding problem.
1. http://www.amazon.com/Algorithm-Design-Manual-Steven-Skiena/...
I'm not sure I agree with that, the mechwarrior talk was pretty informative and the variability of terrain and dynamic obstacles made for some interesting challenges. It was particularly interesting when they talked about 'squad walking.' (going into a line in tight spaces etc) When I was thinking about writing my own RTS I did some simple experiments and certainly got a feel for it being quite complicated.
Heck, it probably has the same basic time complexity and is amenable to the same algorithmic solutions.
What you are describing is the complexity for a single path. But there are lots of units that need to be placed and have their paths potentially interact to achieve some goal. This seems very analogous to circuit routing.
Maybe it's too simplistic but in the vein of the outrageous hack I like it.
[1] http://www.teamliquid.net/blogs/viewblog.php?topic_id=306999
Moving a harvester unit past an invincible wall of enemies was one of these, which was accomplished by right clicking on a further mineral field. It's interesting to see that this was an intentional design decision.
Other tricks in those maps were definitely bugs, like the ability to infinitely cloak burrowing units by using an arbiter and other ones I can't remember. I think they fixed that bug though (although it would be unlikely to occur in real play).
Now that I think about it, there was one other trick in those maps that likely was a similar hack to fix a bug. You could destroy a siege tank if you tried to siege a tank in the location a terran building was landing in. It seems like it was a quick fix to two immovable units taking up the same position.
Reading these blog posts is always a treat.
Funny fact: if you landed a building on your opponent's tank, you could actually get a label "Kills: 1" on the building :D.
This seems like a pain point that's an opportunity in disguise. A technology that made it much easier to get multiplayer sync correct would be an enormous advantage.
> While programmers can become obsessed with finding the most pure, abstract, clean, even sublime solution to a problem, there are times in a project when a few sacrifices have to be made. If they’re done well no one notices the evil compromises that had to be made, as is true for the hacks written up by Brandon Sheffield in his article Dirty Coding Tricks.
Human beans [sic] are probably full of Dirty Coding Tricks -- as organisms, I mean. It's just that we work well enough.
As for "no one notices the evil compromises", the author is missing the second part: "except the people who have to look at that code a few years later". TANSTAAFL - at some point, somebody will pay.
This didn't matter back in the good old days, where tech progressed so rapidly that you'd basically started from scratch for each new game, but it bit a lot of teams in the last console cycle, where re-using made economic sense.
It's not completely obvious what technology you could make that would make it easier to avoid sync bugs in the first place. You could make a good network command-passing and simulation timing library, but in my experience the majority of problems did not come from bugs with the networking itself. Most of the sync bugs were from things like uninitialized variables, memory overwrites, using user input or other local machine state directly in the simulation without going through a multiplayer command, using a non-synced random number generator in the sim, DirectX changing the FPU rounding mode on you, etc. (Using a "safer" language would help with stuff like uninitialized variables/memory overwrites of course, but at an inevitable performance cost. Static code analysis tools are pretty good at finding these type of problems now too.)
[1] http://www.gamasutra.com/view/feature/132500/dirty_coding_tr...
Forget about Tribes: Vengeance & Tribes Ascend, neither captured that same feel.
The Carrier should have been scrapped entirely and replaced with a different air unit. Even to the latest upgrades of Starcraft I, the AI simply couldn't deal with the carrier effectively--they would always attack the interceptors first. This made using the carrier a cheap game-breaking trick against the computer.
Some of the quirky behavior of the SC1 carrier was even re-implemented into the upcoming SC2 expansion at the behest of fans. Why? Because it made the unit fun.
I've noticed that units never seem to have the good sense to target Brood Lords rather than Broodlings when they have a choice. It seemed odd, given that the AI had improved so much in other areas -- pathfinding, running from unwinnable fights, varying its opening strategies. It never occurred to me that things might be that way because it's fun!
Players get very attached to timing and knowledge based tricks, especially ones that give them an advantage. Does that mean they should get them? There's a tricky balance between alienating new players and rewarding skill and dedication in old players.
For example, take that trick with keeping a couple of void rays charged up on each other. I don't think that's something amazing everyone should aspire to. I think it's obnoxious.
That sort of thing is all right if it gives you interesting decisions to make -- and the video about the carriers argued well enough that it does. It ought to be overt, though: A pre-launch interceptors button, not hidden knowledge that invisible, unselectable interceptors stay out if you keep carriers moving.
Games with matchmaking systems don't need to dumb the game down in order for players to be able to play against each other and each have a roughly even chance of winning.
I'm not a SC1 purist - I'm happy I can rally workers to minerals from a base, and I even like the automining feature at the start of games in HoTS. But removing APM sinks and removing interesting/subtle unit mechanics are two very different things.
Supreme Commander for instance has much better user interface and unit control mechanisms. This makes it much more of a macro game, since micro managing units is not necessary to the same degree. And indeed some people really like micro managing stuff and for the others it serves as an excuse to why they suck at the game.
Although I love Starcraft 2 I think its UI is horrible in comparison to what else is out there. However it is an essential part of the game and it gives it character.
An examination of what it was that made the Carrier fun might have revealed ways to get similar effects (long range, able to fire while retreating, requires paying minerals for continued use . . .) in a unit that wasn't such a weird gamebreaker. Most people just liked Carriers because it cast a field of enemy unit and Ai stupidity around it. Once players get attached to a unit, you may be stuck keeping it in the game even if it's not really good for overall playability.
Just because it worked with this one unit doesn't mean the overall game experience couldn't have been better with something different in there. But once something is introduced, status quo bias takes hold in a major way.
Edit: I'll concede that you want the AI to be stupid in some ways so that it can be exploited. The Carrier just always seemed to me too extreme.
Actually, it is. Single player is basically a financial dead end: you play it through X times, interact with very few people, and put the game away.
If you end up breaking it in favor of gameplay where players are generating content on your behalf (each other)... the loss rapidly disappears as people stop playing the single-player because it not only sucks, it's irrelevant.
The new one's better, but definitely not exploit-free. A dozen speedlings in its mineral line will result in it recalling ALL its forces, rather than just what it needs to deal with the problem.
I sometimes think of the AI as an example of how hard it is to simulate human intelligence.
So much of the discussion here is focusing on SC and SC2. What about the software development aspect of this story?
What's the moral of Patrick Wyatt's tale? I mean, it's hard to argue that there's some parallel universe where Blizzard did things differently and StarCraft was an even BIGGER success. What would that even look like -- it became the national pastime of several countries, instead of just one? Yet I can't help but think how expensive it must have been for them to have made these poor decisions in design, implementation, and planning, each one compounding on top of all the previous ones, constantly delaying their launch.
So is the moral of the story, "here's why you shouldn't code for 'two months from launch' mode"? Or is it, "when the chips are down, you can take or leave all your fancy MVCs and UMLs, they don't make the difference between a mega-blockbuster and a dud or vaporware"?
http://wiki.teamliquid.net/starcraft/Bugs#Mineral_Walk
Also, I wonder if the author has thought of getting his articles on Starcraft (and maybe Warcraft 2) into Korean? I'm sure there'd be a huge audience for them.
For example, the common algorithm appears to be A* where you use some heuristic to guess the most efficient path but update the path when you find another is more efficient (for example you hit a large wall on the first path).
This is easy enough when you have only one moving object (because you can just compute that path at the start and then follow it), however in a real game there are likely many moving colideable objects and you might choose a path that causes you to get stuck or have to take a very suboptimal path.
The most "correct" way to do it would be to recalculate the path for each moving object on each frame, but this would probably lead to unacceptably poor performance.
So you can wait until you get stuck and then try and find a path out (which may be impossible). Or you can divide your path into recursive sub-paths and compute different sub-paths as you move.
Now for simulation this is interesting, for example if you order a military unit to move to some location in real life then you would expect them to at least consult a map before setting off however there may be unanticipated situations on the ground which mean that they have to take a suboptimal path. So pathfinding inefficiency might add realism.
I have noticed that overall path finding is much improved in modern games, especially RTS. So curious roughly how their implementation works.
Never really noticed path finding issues (well no more than other games)...except that one time I attempted a massive zerg rush. If you've got enough of them the pathfinding algo craps itself and sends them into the enemy base +- individually. So much for rushing...
A number of similar bugs with queued commands existed. I get the sense that this feature wasn't adequately tested. :)