The StarCraft path-finding hack(codeofhonor.com)
codeofhonor.com
The StarCraft path-finding hack
http://www.codeofhonor.com/blog/the-starcraft-path-finding-hack
22 comments
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.
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.
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 :-)
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 :-)
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/...
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/...
"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.
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.
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.
Heck, it probably has the same basic time complexity and is amenable to the same algorithmic solutions.
> 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.
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.
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.
Fair enough, once you start needing to path many units at a time (where their movements can potentially conflict with each other), then it starts to sound a lot more like circuit routing.
Maybe but it's more traffic - ten units can find Independant paths to a goal. If paths intersect on a pcb you must reroute. If the units paths intersect t one waits till other moves then continues.
Maybe it's too simplistic but in the vein of the outrageous hack I like it.
Maybe it's too simplistic but in the vein of the outrageous hack I like it.
I think that's basically what SC1/BW did. There was a professional game last year[1] where one player (Jaedong, probably the best Zerg at the end of BW) had one unit blocking a ramp in his base, and something like 30 hydralisks stacked up behind it. He was attacking the enemy so he didn't notice at first and I think he probably lost his main army but then found a huge second army that had been stuck and just rolled the poor guy.
[1] http://www.teamliquid.net/blogs/viewblog.php?topic_id=306999
[1] http://www.teamliquid.net/blogs/viewblog.php?topic_id=306999
> 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.
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.
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.)
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.)
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.
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.
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_tr...
[1] http://www.gamasutra.com/view/feature/132500/dirty_coding_tr...
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"?
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"?
The "passing through other units" bug is well known in the community as "Mineral Walking"
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.
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.
If you want to experiment with StarCraft's pathfinding, you can, with 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&cols...
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
[1] http://wiki.teamliquid.net/starcraft/Bugs
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.
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.
you can find tons of information here: http://aigamedev.com/
the most interesting stuff is behind a paywall, tough.
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...
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...
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
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 :)
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?
> 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?)
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?)
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
Also, when the carrier dies, all interceptors that it has launched die.
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.
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.
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.
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.
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.
...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.
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.
A fun unit in multiplayer isn't really a good excuse for a gamebreaking behavior in single player.
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.
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.
> A fun unit in multiplayer isn't really a good excuse for a gamebreaking behavior in single player.
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.
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.
Then don't use the carrier... Long games against the computer were never fun in starcraft (or most other similar games). It becomes gamebreakingly easy to win if you survive long enough and the AI becomes utterly useless, it is clearly not something that the developers even cared to put some thought into. And that's okay, the real essence of starcraft is multiplayer.
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!
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!
Well things like that are no fun. However much of the popularity and skill required to play Starcraft is not in because it is such a greatly designed game. Most of the challenge come from the point that the development team has found creative solutions around its limitations and that leaves a lot of opportunities to exploit and hack its shortcomings.
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.
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.
These units are basically specifically designed to require micro-ing from the player. Both brood lords and carriers are pretty weak if attacked head on (slow/low-hitpoints)-- their entire strength is in the fact that other units will auto-attack broodlings/interceptors first (which makes some "conceptual" sense since that's what actually attacking them).
Not at all. Maybe for beginners but at the competitive level brood lords are so good due to their cost efficiency in that they create "free" units and have very good synergy with infestors which are also known for their cost efficiency.
I'm not sure what your "Not at all" is in response to. I was saying it requires micro-ing from the person going up against them (specifically, you need to blink your stalkers under the brood lords, or tell your units to target the carriers and not the interceptors, etc etc). In other words, they are not units designed to be fought against by just a-clicking in their general direction and letting the AI do the work for you.
It is in response to "their entire strength is in the fact that other units will auto-attack broodlings/interceptors first" which is true but only for the very new players.
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
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.
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.
I think "creative use of game mechanics" is a large part of what makes e-sports popular. Boxer (the Michael Jordan, or perhaps Babe Ruth, of pro-gaming) wasn't popular so much for his mediocre mechanics or even his good micro,but primarily for his creativity.
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.
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.
Yeah, it's hard to get sympathy from me for upping micro requirements. That could be because I'm bad at it, and find it uninteresting. Those might also be related. :P
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.
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.
No, because it adds an element of skill that was missing from the SC2 carrier. Here is the video that caused the quirks to be included and Nony makes a very compelling case in it.
http://www.youtube.com/watch?v=1Rqx8s2qKXM
I don't know that that has anything to do with carriers specifically, though. The old AI just wasn't very smart -- there were lots of cheap game-breaking tricks you could use. Lurkers in the base entrance, for example, generally resulted in a computer going crazy until it starved itself. It's like it refused to do any teching until it could get a dozen infantry standing in the base entrance like it WANTED.
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.
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.
From what I understand it was pretty problematic to multiplayer too, since with a bunch of carriers it becomes difficult to manually target them behind all the interceptors.
Depending on the units you had at your disposal it needed a little practice or was really easy. A bunch of marines with medics (or hydralisks) for example just kill the interceptors quickly enough so carriers aren't a threat anymore. Goliaths worked very well with their range upgrade. Psi storms work wonders and don't even need to be targeted that accurately. There are plenty of cheap and easy options against carriers but I guess as usual with such high-level threats, you shouldn't let your opponent get to the point where they can employ them or at least stay informed on what they do so you can react accordingly.
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 :)
It's become such an important part of the gameplay that it's funny to think it was just a fix.
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.
And skiing in Starseige: Tribes, a bug with the jumping code. They had to reimplement it for all the following games.
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.
Forget about Tribes: Vengeance & Tribes Ascend, neither captured that same feel.
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.
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 . 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
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
Is changing the behavior of a group of units because it happens to be grouped with a distant unit really a good thing for the game?
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.
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.
Your comment on starcraft maps is off.
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.
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.
I think you grossly overestimate Blizzard's grasp of balance when compared to the SC/SC2 communities' grasp of balance. Compare the solutions and balance opinions of Dustin "Rocks are Balanced" Browder to Sean "Day[9]" Plott, for example.
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".
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".
Supreme commander 2 used flowfield for their pathfinding. Flowfield does an ok job, but it actively tries to group units together by giving them little pushes in the correct direction.
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!
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!
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.
Edit: Found him, Zileas aka Tom Cadwell. Brings back the memories.
Reaver drop was not invented by Zileas, he only popularized it.
Do you happen to know who invented it? Was it someone else at MIT?
1_COOL_GUY was #1 on bnet for a long while using the reaver drop coupled with the map hack. Not sure if he invented this either, but this was before Zileas (a legit player) came along.
(Can't believe I remember these details.)
(Can't believe I remember these details.)
This is true!
While this is a fairly good explanation of some interesting things about Starcraft, I think something truly interesting about mutalisk stacking in particular is its actual discovery date. It wasn't, in fact, discovered in the 'early 2000s', but rather in mid 2006, a good 7 years after the game was released.
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).
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).
> 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.
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.
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.
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 :-)
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.
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.
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.
Funny fact: if you landed a building on your opponent's tank, you could actually get a label "Kills: 1" on the building :D.
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.
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.
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
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.
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.
What your describing is called the drone drill, where you have all the workers attack at once, but this is a trick only used for dealing with the 3 pylon block (something banned in tournamnet play) as zerg. http://www.youtube.com/watch?v=M9CA9AahV1E
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
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
I wasn't aware that competitive StarCraft had ever banned anything that was intended by the game engine, and Google isn't turning up anything. Could you provide a source?
In tournament play, it isn't "banned" in a sense that you are fouled or disqualified for doing it. It's a map design and racial balance issue, which tournaments usually solve systematically by placing a neutral supply depot to prevent placing a 3rd blocking pylon. Check out [1] or [2] or search for "neutral supply depot" to find some more information.
[1] http://gaming.stackexchange.com/questions/51630/why-are-ther...
[2] http://wiki.teamliquid.net/starcraft2/Buildings#Neutral_buil...
[1] http://gaming.stackexchange.com/questions/51630/why-are-ther...
[2] http://wiki.teamliquid.net/starcraft2/Buildings#Neutral_buil...
[deleted]
TheMaka already answered this specific case and there is indeed nothing technically "banned" in competitive SC2.
BW however did have a few bugs that were banned by tournament ogranizers [1].
[1] http://wiki.teamliquid.net/starcraft/Competitive_Rules
BW however did have a few bugs that were banned by tournament ogranizers [1].
[1] http://wiki.teamliquid.net/starcraft/Competitive_Rules
Wow. That's an impressive hack.
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 ; )
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 ; )
I think I still have my Kali key somewhere. Brings back great, old memories.
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
[1] http://www.youtube.com/watch?v=7MN0wjoqmzU
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. :)
A number of similar bugs with queued commands existed. I get the sense that this feature wasn't adequately tested. :)
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.