Patrick Wyatt was a programmer of Brood War who has shared a few awesome stories about the development of the game here and here. He’s back with a third installment, this time regarding an issue we’re all extremely close to: the pathfinding AI. It gives some amusing insight into the strange behavior of ramps and why workers have no collision size, among other things.
Game-unit path-finding is something that most players never notice until it doesn’t work quite right, and then that minor issue becomes a rage-inducing, end-of-the-world problem. During the development of StarCraft there were times when path-finding just didn’t work at all.
As the development of StarCraft dragged on it seemed like it would never be done: the game was always two months from launch but never seemed to get any closer to the mythical ship date. “Fortunately” — and I use that term advisedly — Blizzard had previous experience shipping games late.
While we always had launch-date “goals” (though “wishes” might be a better term) we tried not to announce publicly until there was a good chance that the game would be ready at that point. Blizzard’s “when it’s done” policy for game launch was as much an admission that no one had any idea when we would finish as it was a commitment to releasing quality products.
In any event, towards the end of the project we had a set of problems that prevented launching. Like any game in the latter stages of the development process there were defects galore that needed to be found and repaired and the bug count still numbered in the thousands.
Many of those bugs were trivial, and needed only a little attention to fix. Too bad they weren’t all like that.
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.
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.
But the biggest thing holding back StarCraft was unit path-finding.
It wasn’t that the path-finding was totally broken; in most cases it worked quite well. But there were enough edge-cases that the game was un-shippable.
Game units would get stuck and stop on the battlefield. Often they would go through elaborate efforts to find paths, inching forward or looping around but not making progress, and sometimes getting wedged and unable to move further. Entire task forces would get bogged down in what looked like the afternoon commute.
The problem was frustrating for players, but also made the AI weak and consequently made it impossible to balance the missions, wasting design time.
Though I was never a top-tier RTS player, before the game launched I was good at the game because I discovered that Goliaths were overpowered to make up for their poor path-finding abilities. Because they were larger than other ground units they needed wider spaces for path-finding, and so by carefully shepherding Goliaths around obstacles I was able to bring their firepower to bear in crucial situations to overcome “macro” players who would otherwise tear me to shreds. Sadly my skills only lasted a short while until the Goliaths were rebalanced. sigh
Early path-finding was rough — while there were well-chosen algorithms driving unit movement they were handicapped by some poor development decisions made during the course of the project.
Thanks. This blog is beyond awesome, and any programmer, specially a games programmer, will enjoy this series inmensely. I can only imagine what the Carrier code was like, and this bugs are directly correlated with the old inheritance model being adapted to games. If this game was made in components, they would've had wayyyy less code copypaste syndrome, and a much more dynamic model to approach bugs.
To handle all the tricky edge-cases, the pathing code exploded into a gigantic state-machine which encoded all sorts of specialized “get me out of here” hacks.
On February 21 2013 04:11 iPAndi wrote: Thanks. This blog is beyond awesome, and any programmer, specially a games programmer, will enjoy this series inmensely. I can only imagine what the Carrier code was like, and this bugs are directly correlated with the old inheritance model being adapted to games. If this game was made in components, they would've had wayyyy less code copypaste syndrome, and a much more dynamic model to approach bugs.
Couldn't agree more, pure awesomesauce right there
On February 21 2013 04:06 Sayle wrote: Oh man I thought this would be a thread about a new hack to give BW units good path-finding. Was hoping for Pucca vs the world in yet another thread.
This is much less entertaining :/
I was just thinking this, so I went offline and punched in all the cheat codes and smashed 7 PCs in frustration.
On February 21 2013 05:06 Wohmfg wrote: I love how these little quirks in games add so much to the top level of play.
How a game can be so perfect without being engineered that way.
There's a lot of cool stuff that wasn't intended to be as the developers imagined it.
Besides all the cool tricks there are in BW, Quake had bunnyhopping( i think it was first "introduced" in doom..not sure), GunZ has a bunch of animation-based tricks. Like Wall cancelling etc.
These blogs are always amazing to read. Seems like they didn't rewrite path finding after changing the tileset, someone correct me if I'm wrong. On the bright side, we got a lot of cool tricks like drone drills and such so win win? That best vs. July game though, the look on Bisu's face was priceless XD
On February 21 2013 05:06 Wohmfg wrote: I love how these little quirks in games add so much to the top level of play.
How a game can be so perfect without being engineered that way.
There's a lot of cool stuff that wasn't intended to be as the developers imagined it.
Besides all the cool tricks there are in BW, Quake had bunnyhopping( i think it was first "introduced" in doom..not sure), GunZ has a bunch of animation-based tricks. Like Wall cancelling etc.
Yeah exactly.
A lot of things that take a game to the next level professionally were never designed and take away from the immersion of the game which makes me question whether a game can be designed with the sole intention of being played at a very high level competitively.
It just makes me wonder if someone was to create a modernized version of BW (ala Dota1 -> Dota2), how much of those "dirty hacks" would have to be replicated just to keep all the little BW tricks intact, or if that's even possible.
The isometric on top of square tiles I definitely noticed while map-mapmaking. It can be very frustrating to copy-paste things from other maps. Even ramp copy-paste usually means trying to individually find the right tile to make it flow a little better.
On the plus side, worker drills were born and you have to love that.
On February 21 2013 07:01 2Pacalypse- wrote: Fascinating stuff!
It just makes me wonder if someone was to create a modernized version of BW (ala Dota1 -> Dota2), how much of those "dirty hacks" would have to be replicated just to keep all the little BW tricks intact, or if that's even possible.
I think BW's graphic is better than SC2's. If they could just increase the definition of the units's pixel and its shadings then we are golden.
On February 21 2013 05:06 Wohmfg wrote: I love how these little quirks in games add so much to the top level of play.
How a game can be so perfect without being engineered that way.
I would argue the "perfection" can from the persistence and innovative attitudes applied to the game because of the competitive scene built around it. It is only natural for players to try to exploit bugs or incorporate as many facets of a game into their play style. Regardless of whether these facets were intended or not. I think it may be even more unreasonable to expect a developer to truly know the effects of every input permutation in their game.
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. To handle all the tricky edge-cases, the pathing code exploded into a gigantic state-machine which encoded all sorts of specialized “get me out of here” hacks.
Expected, but fun to hear a definitive statement on it.
On February 21 2013 07:03 Falling wrote: Yes! My all time favourite blog.
The isometric on top of square tiles I definitely noticed while map-mapmaking. It can be very frustrating to copy-paste things from other maps. Even ramp copy-paste usually means trying to individually find the right tile to make it flow a little better.
On the plus side, worker drills were born and you have to love that.
Part of what I love about BW mapping, is how it's all workarounds, and because you have to come up with your own solutions, there's a lot of room for individuality and creativity.
On the other hand, the fact that the pathfinding algorithm for ground units somehow seems to have problems to figure out what the term "straight line" could possibly mean, especially that it's darn hard to make a mineral line, that hasn't some worker go bananas in one way or another, makes debugging a map quite the chore...
The reliance on hacks and hardcore hardcoded lard make Blizzard games such an unpleasant pain in the ass to mod. Jeez. And I doubt BW is anywhere near as bad as Diablo 2. Diablo 2... that game has some serious problems.
Blizzard’s “when it’s done” policy for game launch was as much an admission that no one had any idea when we would finish as it was a commitment to releasing quality products.
That quote made me laugh quite a bit! Great blog, as usual. I really hope he has more of those great stories to share about his time at Blizzard.
On February 21 2013 05:06 Wohmfg wrote: I love how these little quirks in games add so much to the top level of play.
How a game can be so perfect without being engineered that way.
There's a lot of cool stuff that wasn't intended to be as the developers imagined it.
Besides all the cool tricks there are in BW, Quake had bunnyhopping( i think it was first "introduced" in doom..not sure), GunZ has a bunch of animation-based tricks. Like Wall cancelling etc.
I found BW's awful pathfinding to be a distraction. I would say the most successful unintentional game mechanic in modern games came from Tribes, namely skiing, followed by rocket jumping and then Counterstrike model stacking.
I love reading articles like this, really gives you insight into the trials and tribulations of development. Plus i loved starcraft as a kid so my inner child is doing jumping jacks.
On February 21 2013 04:11 iPAndi wrote: Thanks. This blog is beyond awesome, and any programmer, specially a games programmer, will enjoy this series inmensely. I can only imagine what the Carrier code was like, and this bugs are directly correlated with the old inheritance model being adapted to games. If this game was made in components, they would've had wayyyy less code copypaste syndrome, and a much more dynamic model to approach bugs.
What's the inheritance vs component model of making things?
On February 21 2013 05:06 Wohmfg wrote: I love how these little quirks in games add so much to the top level of play.
How a game can be so perfect without being engineered that way.
There's a lot of cool stuff that wasn't intended to be as the developers imagined it.
Besides all the cool tricks there are in BW, Quake had bunnyhopping( i think it was first "introduced" in doom..not sure), GunZ has a bunch of animation-based tricks. Like Wall cancelling etc.
I found BW's awful pathfinding to be a distraction. I would say the most successful unintentional game mechanic in modern games came from Tribes, namely skiing, followed by rocket jumping and then Counterstrike model stacking.
I don't play any of those games, so for RTS's I would move shot at the top of successful unintentional game mechanics. But mineral slides and worker drills are pretty good discoveries as well.
On February 21 2013 05:06 Wohmfg wrote: I love how these little quirks in games add so much to the top level of play.
How a game can be so perfect without being engineered that way.
I would argue the "perfection" can from the persistence and innovative attitudes applied to the game because of the competitive scene built around it. It is only natural for players to try to exploit bugs or incorporate as many facets of a game into their play style. Regardless of whether these facets were intended or not. I think it may be even more unreasonable to expect a developer to truly know the effects of every input permutation in their game.
Exactly! So think of a game that is completely the developer's vision. There is less to exploit, there is less depth in the long run.
On February 21 2013 05:06 Wohmfg wrote: I love how these little quirks in games add so much to the top level of play.
How a game can be so perfect without being engineered that way.
I would argue the "perfection" can from the persistence and innovative attitudes applied to the game because of the competitive scene built around it. It is only natural for players to try to exploit bugs or incorporate as many facets of a game into their play style. Regardless of whether these facets were intended or not. I think it may be even more unreasonable to expect a developer to truly know the effects of every input permutation in their game.
Exactly! So think of a game that is completely the developer's vision. There is less to exploit, there is less depth in the long run.
Its a tricky business though because at times certain bugs or quirks need to be patched in order to preserve competitive stability. Being able to identify which issues require fixing from issues that are benign and may even contribute to the depth of the game is a difficult task. A developer could try waiting and let time tell the difference, but that risks permanently damaging the competitive scene if they wait too long to patch a bad issue, or they could jump they gun and patch a "good" issue which makes the game more bland. There is no definitive science to this and seems to often be a hell of a lot of luck.
"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. To handle all the tricky edge-cases, the pathing code exploded into a gigantic state-machine which encoded all sorts of specialized “get me out of here” hacks."
On February 21 2013 05:06 Wohmfg wrote: I love how these little quirks in games add so much to the top level of play.
How a game can be so perfect without being engineered that way.
There's a lot of cool stuff that wasn't intended to be as the developers imagined it.
Besides all the cool tricks there are in BW, Quake had bunnyhopping( i think it was first "introduced" in doom..not sure), GunZ has a bunch of animation-based tricks. Like Wall cancelling etc.
I found BW's awful pathfinding to be a distraction. I would say the most successful unintentional game mechanic in modern games came from Tribes, namely skiing, followed by rocket jumping and then Counterstrike model stacking.
I don't play any of those games, so for RTS's I would move shot at the top of successful unintentional game mechanics. But mineral slides and worker drills are pretty good discoveries as well.
I'd say the most successful broodwar issues are tight walls, stacked fliers, and patrol micro since they have you be used to make the game balanced.
Honestly, I thought this particular post was pretty low on information compared to the other few. It doesn't really say much about the path-finding except that it was messy and that they had to make workers "drill", both of which we already knew beforehand.
On February 21 2013 17:21 budar wrote: Honestly, I thought this particular post was pretty low on information compared to the other few. It doesn't really say much about the path-finding except that it was messy and that they had to make workers "drill", both of which we already knew beforehand.
i feel excactly this i was expecting more in the line of how patrol micro occured, was if with purpose or accident? Just an example
With him stating that the pathfinding code had so many get me out of here hacks and it being more a giant state machine than fundamentally good pathfinding code, I think it's safe to conclude that pretty much all odd behavior was accidental (most likely as a side-effect as a fix for something worse as with mineral walking, or as a 'good enough, sorta kinda working' thing.)
On February 21 2013 10:17 Shady Sands wrote: What's the inheritance vs component model of making things?
In the inheritance model, polymorphism is provided by subclassing. Specialized game objects subclass general game object classes and override their relevant methods. In the component model, polymorphism is provided by aggregation. Game objects are associated with a number of different components, each of which provides some behavior that the game objects exhibit. Exactly how these components relate to one another depends on the kind of component model implemented.
Inheritance model:
class GameObject: function Method(): //general functionality
class SpecializedGameObject (inherits GameObject): function Method(): //specific functionality
Component model:
class GameObject: Component[] components
Here's a link to a much better explanation than the one I provided.
On February 21 2013 07:52 Grumbels wrote: I wonder if they could have found a way to have workers have collision while mining for SC2.
And he has to be like my favorite person, such interesting blogs.
and remove worker drilling? yeurgh
The idea is that workers having no collision is something that we are all used to, but it's a bit weird and wasn't really the intention of the developers, as can be seen from this article (it's a hack to make the game work to meet a deadline).
Starcraft 2 was a chance to potentially change this mechanic and make workers always have collision, and because these days we have more computing power and better algorithms, there's a good chance they could have come up with something that was playable. And I was basically wondering if what they would have come up with had a chance to be superior to the current model.
With every change you make you lose something and it's not always obvious what you're getting back. Like Dustin Browder says: if you're too careful you'll never end up making a change to anything, at some point you're going to have to take risk.
I thought that maybe with worker collision a potential outcome could be that income per drone would be less straight forward and more interesting, so just wondering really. :o
Thanks for the share. Interesting read, brought back great memories of worker drills and made me think of how much less excitement could have been produced by the game if that simple hack wasn't included in the release. <3 Patrick Wyatt
Hacky fixes, sounds like when engineering and marketing have their bimonthly rage inducing encounter.
The carrier part was rather histarical, even thought I have had bugs like that in my own experience. When someone is in a rush, they tend to produce some rather terrifying code. Quite an entertaining read, thanks for posting it Heyoka.
I now wonder what he thinks of how hard it is to wall in in BW, and how micro can save some units by putting them out of reach of others because of those pixel differences.
EPT
![[image loading]](http://www.teamliquid.net/tlpd/images/Ticon_small.png)
Patrick Wyatt: 1
That best vs. July game though, the look on Bisu's face was priceless XD
Mineral Walk
