11 ms·

The StarCraft path-finding hack

250 points by willvarfar 14y ago

danso 14y ago
> Some bugs were related to the development process itself. The Protoss Carrier regularly lagged behind other units because it had its own way of doing … everything. At some point in time the code for the Carrier was branched from the main game code and had diverged beyond any hope of re-integration. Consequently any time a feature was added for other units, it had to be re-implemented for the Carrier. And any time a bug was fixed for other units, a similar bug would later be found in the Carrier code too, only more devious and difficult to fix. 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?)
- cube13 14y ago
  I think it's because of the way the unit works. The carrier itself doesn't actually attack anything. It produces and spawns interceptors which are independent and targetable(but not capable of taking orders) units, which then go out and attack the carrier's target. 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 http://www.youtube.com/watch?v=1Rqx8s2qKXM Also, when the carrier dies, all interceptors that it has launched die.
- wlesieutre 14y ago
  It functioned in a significantly different way from other units. They had to include the unit building mechanisms from factory buildings (for producing interceptors), and instead of having its own direct attacks it controlled a small fleet of child units with their own weapons. 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.
GavinB 14y ago
The Protoss Carrier regularly lagged behind other units because it had its own way of doing … everything. 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.
- john_b 14y ago
  ...and made it one of the most interesting units in multiplayer. In programmer-land, where all abstractions should be pure and elegant, the carrier (as implemented in SC1) may be abhorrent, but this is irrelevant because the customers (i.e. the players) loved it. 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.
  - Dove 14y ago
    Really? That's interesting. 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!
    - endtime 14y ago
      Since you're interested, here's the video (recorded by a SC1 pro) that catalyzed the SC1 behavior being recreated in the SC2 expansion: http://www.youtube.com/watch?v=1Rqx8s2qKXM http://www.youtube.com/watch?v=1Rqx8s2qKXM
      - GavinB 14y ago
        So the question is, should weird, hard to detect and buggy behavior that experienced players can exploit be kept as part of the game? It's a highly subjective and, to me, non-obvious answer. 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.
tomp 14y ago
I always thought that the fact that workers don't jam was one of the coolest little details of the game that made it so awesome! I never would have thought that it was basically an ugly, last-resort bugfix :)
- rvkn 14y ago
  It's become such an important part of the gameplay that it's funny to think it was just a fix.
  - baq 14y ago
    see also quake rocketjumping, strafe jumping, bunnyhopping, etc. when carmack wanted to fix all those issues in q3arena, the players protested, because the game was dull.
    - ChrisClark 14y ago
      And skiing in Starseige: Tribes, a bug with the jumping code. They had to reimplement it for all the following games.
      - nuclear_eclipse 14y ago
        From my memory, they actually discovered that bug during development and decided that it actually improved gameplay, so they made it a feature before it was released.
      - robertfw 14y ago
        And sadly, they never got it quite right! none of the subsequent tribes games had the same skiing behaviour. The only reason the competitive community in Tribes 2 has hung on for so long is that a community mod sped the game up to be more like Tribes 1. Forget about Tribes: Vengeance & Tribes Ascend, neither captured that same feel.
CyrusL 14y ago
One of the reasons Starcraft is interesting as an e-sport is because bugs like this have kept the game in racial balance for over a decade. 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 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 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 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 https://www.youtube.com/watch?v=Z4UTDudShDY
- bradleyjg 14y ago
  There were all kinds of discoveries like that. I remember when the reaver drop was invented by someone out of MIT. Can't remember his handle but he was one of the top players pre-brood war. Edit: Found him, Zileas aka Tom Cadwell. Brings back the memories.
  - Rastafarian 14y ago
    Reaver drop was not invented by Zileas, he only popularized it.
systematical 14y ago
You can see this when the workers run out of minerals and boom they expand all over the place. Awesome read and makes me feel great about some of my own git-r-dun hacks :-)
kevinh 14y ago
It's pretty cool to see the source of this. Back when I used to play Starcraft I primarily played UMS maps (custom game modes) and several of them were based on using "bugs" in the game engine to surmount situations that appeared impossible. 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.
- TeMPOraL 14y ago
  AD. exploding siege tank, it was actually a fix in one of the patches. Some players discovered that you could land a building on a tank if you time the landing right with switching to siedge mode, making the tank unreachable for meelee units (which were the kind of units usually used against the tank). It created an unfair advantage, so Blizzard removed it by making the tank explode when landed on. Funny fact: if you landed a building on your opponent's tank, you could actually get a label "Kills: 1" on the building :D.
invalidOrTaken 14y ago
What no one has mentioned is how many "essential" skills have arisen as a result of this hack. 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.
- mitchi 14y ago
  I played Warcraft 3 and the same trick was used to surround a hero with ghouls. Since ghouls are also the unit that gathers lumber for the Undead Race, they enter a no-collision state when you right click on a tree. This behavior was patched because it was too strong. You would just click on a tree behind the enemy hero and all your ghouls would pass through all the other units (footmen for example) and they could surround the hero and kill him. Once you kill the hero in Warcraft 3, there's no point fighting anymore :P
  - ihsw 14y ago
    Another WC3 glitch is Shades (invisible scouting units) that triggered collision but you couldn't target them due to being invisible. Eventually players caught on and lined Shades up to create impassible and invisible walls. 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.
glesperance 14y ago
I wonder what part of their path finding algo created a glitch like the drone float[1] [1] http://www.youtube.com/watch?v=7MN0wjoqmzU http://www.youtube.com/watch?v=7MN0wjoqmzU
- duskwuff 14y ago
  I suspect a hack was involved -- the animation leading up to the construction of a Zerg Extractor involves the drone hovering over the geyser temporarily. This requires the unit to be put into a "floating" state which wasn't properly cancelled if the build failed -- queueing up additional move commands would then allow it to clip through barriers. A number of similar bugs with queued commands existed. I get the sense that this feature wasn't adequately tested. :)
glesperance 14y ago
Here's an interesting list of bugs [1] (some related to path-finding some not) found in SC / Broodwars. [1] http://wiki.teamliquid.net/starcraft/Bugs http://wiki.teamliquid.net/starcraft/Bugs
stcredzero 14y ago
> Others, like a multiplayer synchronization bug, would pop up and require dedicated attention from several members of the programming team — sometimes weeks of effort for a single problem. Other game developers have reported similar experiences with their sync bugs: Ages of Empires and Supreme Commander. 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.
- groby_b 14y ago
  Yes and no. Video games are always extremely resource constrained. While you could solve networking in a generic way, it also means inefficiencies that many teams are not willing to take. (Also, it precludes certain shortcuts taken that allow FPSs to have eventual consistency, at a rudimentary level) 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.
- skittlebrau 14y ago
  I worked at Ensemble Studios (Age of Empires) and by the time we shipped Age of Mythology we had much better tools for dealing with sync bugs. Most of the run of the mill ones could be tracked down pretty quickly, but there were still plenty of painful ones. What made them easier to track down was a more advanced tracking/logging system for the simulation state history. The simulation was littered with tons of sync logging code that tracked the execution flow and values of things as they were calculated/updated. When the state went out of sync, all the machines would dump their last couple updates worth of logging (often several gigs) and you could diff them to see where things diverged. If you were making a synced simulation game, a nicely done version of this type of thing would be pretty useful to have, especially if you made a good diff tool to go with it. 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.)
ChuckMcM 14y ago
I remember thinking to myself, at a talk given by an Activision employee on some Mechwarrior pathing issues, that these guys were re-inventing printed circuit board layout. 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 :-)
- AnIrishDuck 14y ago
  Pathfinding is a much easier problem than circuit routing and can essentially be solved in O(n + k) where n is the number of nodes and k is the number of edges between nodes. 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/dp/1849967202/ http://www.amazon.com/Algorithm-Design-Manual-Steven-Skiena/...
  - ChuckMcM 14y ago
    "Pathfinding is a much easier problem than circuit routing" 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.
    - AnIrishDuck 14y ago
      I was confused by your original comment. You're absolutely right though; trying to path a squad of multiple units so that their routes don't conflict is much harder. I can see how it could be very similar to circuit routing. Heck, it probably has the same basic time complexity and is amenable to the same algorithmic solutions.
Havoc 14y ago
Nice article. Good balance between tech details & understandability. 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...
prawks 14y ago
> Because the project was always two months from launch it was inconceivable that there was enough time to re-engineer the terrain engine to make path-finding easier, so the path-finding code just had to be made to work. 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.
- kevingadd 14y ago
  That mindset is sadly pervasive in the game industry (no doubt other software as well, but imaginary ship dates have a terrifying power in games due to The Holidays)
  - prawks 14y ago
    I would imagine The Holidays wouldn't be a moving target as much as "soon" is, however.
grecy 14y ago
That article links to 'Dirty Coding Tricks'[1] - extremely interesting and well worth a read! [1] http://www.gamasutra.com/view/feature/132500/dirty_coding_tricks http://www.gamasutra.com/view/feature/132500/dirty_coding_tr...
acabal 14y ago
This is such an amazing blog. It's fascinating to read about the sloppy guts of games you spent hours on in your youth. 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.
barbs 14y ago
The "passing through other units" bug is well known in the community as "Mineral Walking" http://wiki.teamliquid.net/starcraft/Bugs#Mineral_Walk 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.
snippyhollow 14y ago
If you want to experiment with StarCraft's pathfinding, you can, with BWAPI http://code.google.com/p/bwapi/ http://code.google.com/p/bwapi/ . Particularly, there is some reverse-engineering information on pathfinding here http://code.google.com/p/bwapi/issues/detail?id=190&colspec=ID%20Stars%20Type%20Priority%20Status%20Milestone%20Summary http://code.google.com/p/bwapi/issues/detail?id=190&cols...
jiggy2011 14y ago
I've been curious for a while as to how path-finding gets implemented in real world games. 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.
- Paradigma11 14y ago
  you can find tons of information here: http://aigamedev.com/ http://aigamedev.com/ the most interesting stuff is behind a paywall, tough.
d0m 14y ago
There was a fun bug with zerg in the early days of Starcraft where you could build everywhere on the map even your drone wasn't there. I don't remember exactly how, but I know it was using a mineral path-finding bug :O
rtpg 14y ago
Am I the only one who is bothered by the fact that changing the perspective rendering somehow forced them to go and change the pathfinding? How recent is MVC design patterns?
thisisnotatest 14y ago
I got a kick of reading about how this hack was one of the things that enabled StarCraft to be released. As an eager 12-year-old, it seemed like I couldn't get it soon enough. But as a software engineer now, I can't stop cringing at this story. 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"?
Aardwolf 14y ago
I'm not a professional player but I also noticed back then that harvesters walked through each other! I thought it was done on purpose for this reason - and this confirms it :)

250 points by willvarfar 14y ago

danso 14y ago

> Some bugs were related to the development process itself. The Protoss Carrier regularly lagged behind other units because it had its own way of doing … everything. At some point in time the code for the Carrier was branched from the main game code and had diverged beyond any hope of re-integration. Consequently any time a feature was added for other units, it had to be re-implemented for the Carrier. And any time a bug was fixed for other units, a similar bug would later be found in the Carrier code too, only more devious and difficult to fix. 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?)

cube13 14y ago
I think it's because of the way the unit works. The carrier itself doesn't actually attack anything. It produces and spawns interceptors which are independent and targetable(but not capable of taking orders) units, which then go out and attack the carrier's target. 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 http://www.youtube.com/watch?v=1Rqx8s2qKXM Also, when the carrier dies, all interceptors that it has launched die.
wlesieutre 14y ago
It functioned in a significantly different way from other units. They had to include the unit building mechanisms from factory buildings (for producing interceptors), and instead of having its own direct attacks it controlled a small fleet of child units with their own weapons. 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.

GavinB 14y ago

The Protoss Carrier regularly lagged behind other units because it had its own way of doing … everything. 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.

john_b 14y ago
...and made it one of the most interesting units in multiplayer. In programmer-land, where all abstractions should be pure and elegant, the carrier (as implemented in SC1) may be abhorrent, but this is irrelevant because the customers (i.e. the players) loved it. 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.
- Dove 14y ago
  Really? That's interesting. 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!
  - endtime 14y ago
    Since you're interested, here's the video (recorded by a SC1 pro) that catalyzed the SC1 behavior being recreated in the SC2 expansion: http://www.youtube.com/watch?v=1Rqx8s2qKXM http://www.youtube.com/watch?v=1Rqx8s2qKXM
    - GavinB 14y ago
      So the question is, should weird, hard to detect and buggy behavior that experienced players can exploit be kept as part of the game? It's a highly subjective and, to me, non-obvious answer. 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.

tomp 14y ago

I always thought that the fact that workers don't jam was one of the coolest little details of the game that made it so awesome! I never would have thought that it was basically an ugly, last-resort bugfix :)

rvkn 14y ago
It's become such an important part of the gameplay that it's funny to think it was just a fix.
- baq 14y ago
  see also quake rocketjumping, strafe jumping, bunnyhopping, etc. when carmack wanted to fix all those issues in q3arena, the players protested, because the game was dull.
  - ChrisClark 14y ago
    And skiing in Starseige: Tribes, a bug with the jumping code. They had to reimplement it for all the following games.
    - nuclear_eclipse 14y ago
      From my memory, they actually discovered that bug during development and decided that it actually improved gameplay, so they made it a feature before it was released.
    - robertfw 14y ago
      And sadly, they never got it quite right! none of the subsequent tribes games had the same skiing behaviour. The only reason the competitive community in Tribes 2 has hung on for so long is that a community mod sped the game up to be more like Tribes 1. Forget about Tribes: Vengeance & Tribes Ascend, neither captured that same feel.

CyrusL 14y ago

One of the reasons Starcraft is interesting as an e-sport is because bugs like this have kept the game in racial balance for over a decade. 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 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 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 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 https://www.youtube.com/watch?v=Z4UTDudShDY

bradleyjg 14y ago
There were all kinds of discoveries like that. I remember when the reaver drop was invented by someone out of MIT. Can't remember his handle but he was one of the top players pre-brood war. Edit: Found him, Zileas aka Tom Cadwell. Brings back the memories.
- Rastafarian 14y ago
  Reaver drop was not invented by Zileas, he only popularized it.

systematical 14y ago

You can see this when the workers run out of minerals and boom they expand all over the place. Awesome read and makes me feel great about some of my own git-r-dun hacks :-)

kevinh 14y ago

It's pretty cool to see the source of this. Back when I used to play Starcraft I primarily played UMS maps (custom game modes) and several of them were based on using "bugs" in the game engine to surmount situations that appeared impossible. 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.

TeMPOraL 14y ago
AD. exploding siege tank, it was actually a fix in one of the patches. Some players discovered that you could land a building on a tank if you time the landing right with switching to siedge mode, making the tank unreachable for meelee units (which were the kind of units usually used against the tank). It created an unfair advantage, so Blizzard removed it by making the tank explode when landed on. Funny fact: if you landed a building on your opponent's tank, you could actually get a label "Kills: 1" on the building :D.

invalidOrTaken 14y ago

What no one has mentioned is how many "essential" skills have arisen as a result of this hack. 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.

mitchi 14y ago
I played Warcraft 3 and the same trick was used to surround a hero with ghouls. Since ghouls are also the unit that gathers lumber for the Undead Race, they enter a no-collision state when you right click on a tree. This behavior was patched because it was too strong. You would just click on a tree behind the enemy hero and all your ghouls would pass through all the other units (footmen for example) and they could surround the hero and kill him. Once you kill the hero in Warcraft 3, there's no point fighting anymore :P
- ihsw 14y ago
  Another WC3 glitch is Shades (invisible scouting units) that triggered collision but you couldn't target them due to being invisible. Eventually players caught on and lined Shades up to create impassible and invisible walls. 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.

glesperance 14y ago

I wonder what part of their path finding algo created a glitch like the drone float[1] [1] http://www.youtube.com/watch?v=7MN0wjoqmzU http://www.youtube.com/watch?v=7MN0wjoqmzU

duskwuff 14y ago
I suspect a hack was involved -- the animation leading up to the construction of a Zerg Extractor involves the drone hovering over the geyser temporarily. This requires the unit to be put into a "floating" state which wasn't properly cancelled if the build failed -- queueing up additional move commands would then allow it to clip through barriers. A number of similar bugs with queued commands existed. I get the sense that this feature wasn't adequately tested. :)

glesperance 14y ago

Here's an interesting list of bugs [1] (some related to path-finding some not) found in SC / Broodwars. [1] http://wiki.teamliquid.net/starcraft/Bugs http://wiki.teamliquid.net/starcraft/Bugs

stcredzero 14y ago

> Others, like a multiplayer synchronization bug, would pop up and require dedicated attention from several members of the programming team — sometimes weeks of effort for a single problem. Other game developers have reported similar experiences with their sync bugs: Ages of Empires and Supreme Commander. 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.

groby_b 14y ago
Yes and no. Video games are always extremely resource constrained. While you could solve networking in a generic way, it also means inefficiencies that many teams are not willing to take. (Also, it precludes certain shortcuts taken that allow FPSs to have eventual consistency, at a rudimentary level) 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.
skittlebrau 14y ago
I worked at Ensemble Studios (Age of Empires) and by the time we shipped Age of Mythology we had much better tools for dealing with sync bugs. Most of the run of the mill ones could be tracked down pretty quickly, but there were still plenty of painful ones. What made them easier to track down was a more advanced tracking/logging system for the simulation state history. The simulation was littered with tons of sync logging code that tracked the execution flow and values of things as they were calculated/updated. When the state went out of sync, all the machines would dump their last couple updates worth of logging (often several gigs) and you could diff them to see where things diverged. If you were making a synced simulation game, a nicely done version of this type of thing would be pretty useful to have, especially if you made a good diff tool to go with it. 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.)

ChuckMcM 14y ago

I remember thinking to myself, at a talk given by an Activision employee on some Mechwarrior pathing issues, that these guys were re-inventing printed circuit board layout. 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 :-)

AnIrishDuck 14y ago
Pathfinding is a much easier problem than circuit routing and can essentially be solved in O(n + k) where n is the number of nodes and k is the number of edges between nodes. 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/dp/1849967202/ http://www.amazon.com/Algorithm-Design-Manual-Steven-Skiena/...
- ChuckMcM 14y ago
  "Pathfinding is a much easier problem than circuit routing" 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.
  - AnIrishDuck 14y ago
    I was confused by your original comment. You're absolutely right though; trying to path a squad of multiple units so that their routes don't conflict is much harder. I can see how it could be very similar to circuit routing. Heck, it probably has the same basic time complexity and is amenable to the same algorithmic solutions.

Havoc 14y ago

Nice article. Good balance between tech details & understandability. 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...

prawks 14y ago

> Because the project was always two months from launch it was inconceivable that there was enough time to re-engineer the terrain engine to make path-finding easier, so the path-finding code just had to be made to work. 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.

kevingadd 14y ago
That mindset is sadly pervasive in the game industry (no doubt other software as well, but imaginary ship dates have a terrifying power in games due to The Holidays)
- prawks 14y ago
  I would imagine The Holidays wouldn't be a moving target as much as "soon" is, however.

grecy 14y ago

That article links to 'Dirty Coding Tricks'[1] - extremely interesting and well worth a read! [1] http://www.gamasutra.com/view/feature/132500/dirty_coding_tricks http://www.gamasutra.com/view/feature/132500/dirty_coding_tr...

acabal 14y ago

This is such an amazing blog. It's fascinating to read about the sloppy guts of games you spent hours on in your youth. 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.

barbs 14y ago

The "passing through other units" bug is well known in the community as "Mineral Walking" http://wiki.teamliquid.net/starcraft/Bugs#Mineral_Walk 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.

snippyhollow 14y ago

If you want to experiment with StarCraft's pathfinding, you can, with BWAPI http://code.google.com/p/bwapi/ http://code.google.com/p/bwapi/ . Particularly, there is some reverse-engineering information on pathfinding here http://code.google.com/p/bwapi/issues/detail?id=190&colspec=ID%20Stars%20Type%20Priority%20Status%20Milestone%20Summary http://code.google.com/p/bwapi/issues/detail?id=190&cols...

jiggy2011 14y ago

I've been curious for a while as to how path-finding gets implemented in real world games. 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.

Paradigma11 14y ago
you can find tons of information here: http://aigamedev.com/ http://aigamedev.com/ the most interesting stuff is behind a paywall, tough.

d0m 14y ago

There was a fun bug with zerg in the early days of Starcraft where you could build everywhere on the map even your drone wasn't there. I don't remember exactly how, but I know it was using a mineral path-finding bug :O

rtpg 14y ago

Am I the only one who is bothered by the fact that changing the perspective rendering somehow forced them to go and change the pathfinding? How recent is MVC design patterns?

thisisnotatest 14y ago

I got a kick of reading about how this hack was one of the things that enabled StarCraft to be released. As an eager 12-year-old, it seemed like I couldn't get it soon enough. But as a software engineer now, I can't stop cringing at this story. 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"?

Aardwolf 14y ago

I'm not a professional player but I also noticed back then that harvesters walked through each other! I thought it was done on purpose for this reason - and this confirms it :)