Game design, game programming and more

The StarCraft path-finding hack

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.

How did we get here?

In an earlier article on this blog I alluded to the path-finding difficulties. StarCraft was built on the Warcraft engine, which renders terrain-art using a tile-engine that’s optimized to draw 32×32 pixel square tiles made of 16 8×8 pixel square cells. I architected Warcraft this way because it had worked well for our Super Nintendo and Genesis titles. Those game consoles had hardware support for drawing 8×8 cells, but the behavior was easy to emulate on a PC.

Because the camera perspective of Warcraft I and II were almost top-down, the edges of objects (forests, terrain, buildings) on game maps are either horizontal or vertical, so the render-engine’s representation of the world as a square tile-map is conducive to easy path-finding. In those games each 32×32 tile was either passable or un-passable. I’ve shown a few of the passable tiles tile-edges in the image below in green. Some tiles appeared passable but actually were not; below you can see the barracks building artwork does not fill the 48×4896×96 area it sits on completely, leaving two tiles that appear passable but actually are not (red).

Annotated Warcraft 2 screen captured show tile edges

Warcraft 2 map with 32x32 tiles

But along the way the development team switched StarCraft to isometric artwork to make the game more visually attractive (details in previous post). But the underlying terrain engine wasn’t re-engineered to use isometric tiles, only the artwork which was redrawn.

The new camera perspective looked great but in order for path-finding to work properly it was necessary to increase the resolution of the path-finding map: now each 8×8 tile was either passable or un-passable, increasing the size of the path-finding map by a factor of 16. While this finer resolution enabled more units to be squeezed onto the map, it also meant that searching for a path around the map would require substantially more computational effort to search the larger pathing-space.

Path-finding was now more challenging because diagonal edges drawn in the artwork split many of the square tiles unevenly, making it hard to determine whether a tile should be passable or not. Ensuring that all tiles were correctly marked required painstaking effort.

And the StarCraft map editor was horribly difficult to write because of the many edge-cases necessitated by laying down diagonal shapes onto a square tile-map. Writing the specialized “tile-fixup” code necessitated months programming time.

Unlike Diablo, which used an isometric tile-rendering engine, the StarCraft development team kept the old engine even as new problems with the approach continued to be discovered week by week.

This image shows how a bridge was made up of 8×8 cells; several are shown in green. The almost isometric perspective of the artwork unevenly slices through the cells, leading to a stair-stepped edge along each side of the bridge, as you can see where the red line cuts each tile into an irregular shape.

Annotated StarCraft screen captured show tile edges

StarCraft map with 8x8 cells

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.

Rush hour

If there was any one major problem with path-finding it was that harvesting units (Terran SCV, Zerg drone, Protoss probe) would get jammed up trying to harvest crystals or vespene gas (hereafter “minerals”), and they would grind to a halt. While a player was busy managing an attack or constructing a secondary, the harvesters back at the home base would jam up, halting the flow of minerals into the treasury. When next the player looked up the entire build-queue would have collapsed due to lack of cash.

The basic problem with resource-gathering is that players want to max-out the number of harvesters working on each mineral deposit to maximize their cash flow. Those harvesters are commuting between the minerals and their base so they’re constantly running headlong into other harvesters traveling in the opposite direction. Given enough harvesters in a small space it’s entirely possible that some get jammed in and are unable to move until the mineral deposit is mined out.

How do we get out of here?

I either volunteered or was asked to look into the problem; I just can’t remember after all this time. After studying the path-finding code extensively I realized that there was no way I was smart enough to just “fix the problem”. So I came up with a dirty hack instead.

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.

My idea was simple: whenever harvesters are on their way to get minerals, or when they’re on the way back carrying those minerals, they ignore collisions with other harvesters in the same state other units. By eliminating the inter-unit collision code for the harvesters there is never a rush-hour commute to get jammed up, and harvesters operate efficiently.

It’s possible to notice this behavior by selecting a large group of harvesters who are working a plot of crystals and telling them to halt. They immediately spread out to find tiles that aren’t occupied by other harvesters.

The behavior is obvious if you look, but hidden in plain sight — it doesn’t rise to the level of conscious awareness, though professional-level players and map-makers/modders do notice.

In short, it just works, which is the best kind of hack.

And while there was a lot more work required to finish the game, that hack was what enabled us to launch without massive and time-consuming re-engineering.

The development team was able to work around some of the other path-finding problems and just plain ignore the rest, though the Protoss Dragoon in particular ended up with a bad reputation because, as the largest ground-unit, it frequently failed to path well.

The final result was that path-finding was good enough, and we all learned a hard lesson about hope and wishful thinking as scheduling tools.

About Patrick Wyatt

As a game developer with more than 22 years in the industry I have helped build small companies into big ones (VP of Blizzard, Founder of ArenaNet, COO of En Masse Entertainment); lead the design and development efforts for best-selling game series (Warcraft, Diablo, Starcraft, Guild Wars); written code for virtually every aspect of game development (networking, graphics, AI, pathing, sound, tools, installers, servers, databases, ecommerce, analytics, crypto, dev-ops, etc.); designed many aspects of the games I've shipped; run platform services teams (datacenter operations, customer support, billing/accounts, security, analytics); and developed state-of-the-art technologies required to compete in the AAA+ game publishing business.

  • http://twitter.com/KeefJudge Keith Judge

    Fascinating! Clearly, I haven’t played Starcraft enough to realise it’s played on a screen aligned grid. :-)

  • Tijmen van den Heuvel

    Terran’s dont have Carriers, Protoss do!

    • http://www.codeofhonor.com/blog Patrick Wyatt

      Argh… fixing. Is there a word for a brain-typo?

      • Evan

        Brain fart

      • http://www.codeofhonor.com/blog Patrick Wyatt

        That’s the one!

  • http://twitter.com/shityblis Igor Polyakov

    *vespene
    *Protoss Carrier

    • http://www.codeofhonor.com/blog Patrick Wyatt

      “Bespene” – whoops! I apparently used the original name of the element during development; it was later changed to vespene. And in regard to the “Terran” Carrier, I guess I invented a cow-level unit.

      • Andrew B.

        While you’re at it, pain-staking is actually pains-taking, though the word usually doesn’t have a hyphen at all.

      • http://twitter.com/apetresc Adrian Petrescu

        Oh wow, that’s an interesting bit of lore! So was “Bespene” a play on “Bespin” from Star Wars (I believe they mined a drug-like gas there), which the lawyers asked to rename, or something like that?

      • http://www.facebook.com/heinermann Adam Heinermann

        Also, “Pillbox” is the Bunker, and “Mutalid” is the Mutalisk. There were a few others that were renamed as well.

  • John

    What’s crazy is that this hack is still in StarCraft II today! Workers on their way to collect minerals or gas won’t collide with any units at all, friend or foe.

    One can abuse the mechanic to run workers past Zealots on ‘hold position’ at a choke point, stack workers to all attack a single unit, or get workers out of a surround that would kill any other units.

    • Bennett Piater

      This mechanic was kept for its good gameplay results, as where many other originally unintended hacks.

      • BmB

        This is why I absolutely loathe so-called “competitive” players, they cling bone headedly to exploits and glitches as if they were anything other than poor game programming messing up the intended design.

    • David Espart

      And the funniest thing is that this “feature” is taught in the official tutorials of the game to learn to play multiplayer games.

  • http://www.facebook.com/profile.php?id=670697857 Adrià Facchi

    Is funny because now this hack has been also implemented in SC2 and it has been extended also to collisions against any other unit. Of course the pro scene has exploited this fact http://wiki.teamliquid.net/starcraft2/Mineral_Walk

  • Evan

    “My idea was simple: whenever harvesters are on their way to get minerals, or when they’re on the way back carrying those minerals, they ignore collisions with other harvesters in the same state.”

    Actually it’s ignore collisions with *any* other units, is it not? That’s why worker drills work — you tell the workers to mine, they’ll start walking through other units, then you tell them to stop and it’ll bump them out of the way.

    One of (“the”?) most famous illustration of this was game 2 of the July vs Best OSL (http://www.youtube.com/watch?v=GlfO33YkTfw&t=4m0s) — at about 4:00 the zerg player July tells his workers to mine the minerals in the protoss player Best’s base; the zealot and dragoon are holding position between the assimilators; but at 4:31 July tells the workers to stop, which causes them to spread out and nudge everything else out of the way.

    I also put a video up demoing how you this interacts with stasis: http://www.youtube.com/watch?v=I9mCau4a130 (the same trick can be used to move stasised units, unless the stasised units are themselves workers who were mining — then other workers will pass through but not move the stasised units out of the way)

    • Chris

      Immediately thought of the same game as well. Pat is the father of the drone drill! :D

    • http://www.codeofhonor.com/blog Patrick Wyatt

      Great videos; thanks for sharing!

      You’re right — harvesters ignore collisions with all other units; I’ve updated the article to reflect that. I should have re-played StarCraft before committing this article to print; it’s been five or six years since I’ve played an SC game because there are so many others to choose from.

      I believe my original proposal to solve the harvester pathing problem was no inter-harvester collisions, but as you pointed out the implementation is no inter-unit collisions. Can’t remember why that ended up being the case — perhaps implementation simplicity? It certainly has a lot of “secondary” effects which dramatically increase the micro game, and afford great opportunities for awesome tactical endeavors, as your videos show.

      • http://www.facebook.com/tobberoth Tobias Dersén

        I would think it was set to “no inter-unit collisions” to not make the game unbalanced. Think about it, if SCVs don’t go through other units while mining, a zerg can simply send a few lings into the mineral field, they won’t even have to attack the SVCs to shut down mining completely. When the defending player sends in his own units to kill the zerglings, he’s actually messing up for himself, since his SCVs aren’t passing through his own units either.

  • Wei Liu

    Aha, so it is you who invented the no-collision hack for harvesters! ;-)

  • http://twitter.com/RealHeyoka Matt

    Awesome read. Workers not having collision size has particularly huge effects in professional play, in both defensive situations (trapping early zealots in your mineral line) as well as offensive (drone drilling up or down a ramp).

    Also gives a lot of insight as to why dragoons and goliaths have such a miserable time trying to get across ramps.

  • http://twitter.com/dancow Dan Nguyen

    So how far off the main branch was the Protoss unit? What kind of features had to be reimplemented for it? I’m assuming it still inherited from whatever base unit class there was, right?

    • Adam Heinermann

      AFAIK they didn’t seem like they were far from the base class. Protoss units had functions to do calculations involving shields, but they could have been applicable to any other unit (units that don’t have shields simply don’t include them in calculations). The Carrier and Reaver were special though, and required their own unique entries in the unit structure for the “hangar units” that they constructed. The behaviours for these “uncontrollable” units are also unique. The merge ability for templar is also another unique Protoss-only mechanic that they had to implement.

  • mOatles
  • Matteo Lucchini

    And that’s how probe drilling is done…amazing!

  • That Guy

    You probably want to tag this “starcraft” as well.

    • http://www.codeofhonor.com/blog Patrick Wyatt

      Thanks; done!

  • http://www.facebook.com/profile.php?id=7941978 Nathaniel Tucker

    The mechanic of working non-collision is so fundamental even the lowest level players in Starcraft 2 now understand it and how to use it in other situations.

    This has given rise to strategies like walling off with a unit to prevent run-bys but using the gather mineral to pull workers through; also using workers to prevent retreat by passing them through enemy units then a-moving.

    • http://www.codeofhonor.com/blog Patrick Wyatt

      You’re right: in the 15 (!!!) years since StarCraft was released what was once a trick hidden in plain sight that few noticed has become a basic element of strategy.

  • David Neto

    I was hoping to find something else. Is is some kind of Hill climb? Depth first search? A*?

    • http://www.facebook.com/heinermann Adam Heinermann

      They use A* at a higher level region/node system, with an array-based binary min heap to determine the costs. I don’t know exactly what’s done afterwards but I think they use string pulling against their sorted, pre-computed list of all terrain edges(AKA contours, as they seem to be called) to bring the path down to the tile/pixel level. There is a function called GetClosestReachable (known because of its obvious left-over debug string) that tries to get the closest edge from a unit, which is called for each node in the rough path.

  • Passafist

    I definitely noticed the isometric look on top of the square grid when map-making. Copy-pasting from one map to the other could be quite frustrating as it rarely lined up nicely. Usually had to go in and individually correct the lines with the tile editor (scmdraft.)

    However because worker drills were born of this, I don’t mind so much.

  • http://www.facebook.com/NaibStilgar Stilgar Naib

    You may want to rethink calling this feature a “hack”. I don’t have much experience with path finding algorithms but I have a lot of experience with high level StarCraft and other RTS games. If you want to keep the way resources are gathered in StarCraft (multiple patches clustered together) you would probably need to implement this feature even if you had the perfect isometric model of the map. Problem is that once you have some number of SCVs they would start walking around each other. This would mean economy cannot scale in a linear fashion as you train more workers which is quite important for an economy-based RTS games. I think this is why the feature was carried into StarCraft II

    A couple of interesting points
    - The workers walk through any type of unit and not only other workers. This is important because you are often defending your mineral line and on a low level it would be confusing if you just left a couple of units in the mineral line and your economy suddenly broke down.
    - In StarCraft I you can only do this if when you send the worker to mine the mineral is visible. In StarCraft II you can send it to a mineral field covered by FoW. In practice this means that only Zerg can abuse this trick to scout the opponent in StarCraft I because only Zerg can get a view of the mineral in an opponent’s base via Overlord.

    P.S. I hope you haven’t forgotten my question about this version of the engine – http://images1.wikia.nocookie.net/__cb20080413225332/starcraft/images/9/98/SC1_Alpha6.jpg

    • Dave Churchill

      It was a ‘hack’ in the sense that it was not a feature they had originally planned on, but it was necessary to get around a technical feature. It’s one of those cases where a bug-fix ‘feature’ becomes an iconic and important aspect of gameplay, without the intention of doing so.

      • http://www.codeofhonor.com/blog Patrick Wyatt

        Yup, exactly.

    • Passafist

      Actually, there is some thought that the worker wandering may have helped create a softer cap for efficient mining. Rather than having a hard cap 22/24 possible workers. After 24/24 there is absolutely no reason to add any more workers. But then a decreased rate of income meant you did want to expand more often, but if you were forced to over-make workers and delay expanding, it was a complete loss.

      • http://www.facebook.com/NaibStilgar Stilgar Naib

        Hmm you are correct. However it would have resulted in significantly different games. Not that we would have known at that point.

  • Dave Churchill

    Another great article! Something which you didn’t mention, but is pretty relevant to this article is that the BW path-finding doesn’t take unit sizes into account. Whether you have a zealot or an ultralisk selected, it will produce the same path to your goal. We had to remove several maps from our AI Tournament map pool because of this issue, since they had some obstacles which small units could fit through but larger ones couldn’t. Since the game didn’t care, the large ones would simply get stuck and not be able to move.

  • Allan

    Great read! I work at a small game development company. We are currently pushing an update to one of our tablet games and your talk about bug fixes is particularly relevant. I will be sure to pass this article along to the rest of our devs. A lot of the topics you bring about are good to know for all games not just starcraft or rts’s.

  • Alexander Spasov

    I actually thought that starcraft used each pixel as a possible position…. That would explain a lot of my wonders when gauging starcraft’s performance and memory consumption while trying to build an engine with similar abilities during high school ^^
    Could you explain the pathfinding in more detail, like the general structure (base algorithm and optimisations, like map representation) without the little hacks? Sorry if its too much to ask, I’m just fascinated with the way the early RTS games were written, and starcraft seems to be of the more mysterious sort with all those corner cases :)

    • http://www.codeofhonor.com/blog Patrick Wyatt

      The basics of the set of path-finding algorithms, which were authored by Brian Fitzgerald (who will consequently be able to speak with much more authority on the subject) were:

      1. On map-load, split the map cells into regions which were small (say roughly 10×10 32×32 tiles on average), contiguous and didn’t contain any major obstacles. Path-finding inside these areas could be done using A* with few occasions for bumping into obstacles.

      2. On map-load, create a higher-level map containing region adjacency. Because the regions were irregularly shaped, this higher level map was a graph of nodes rather than a tile-map.

      3. For inter-region path-finding use A* on the higher-level map so that it was not necessary to grind through *every* *single* *8×8* tile on the map — too time-consuming.

      4. As units moved, mark their locations on the individual cells they occupied. Traverse around occupied cells, with lots of special case logic for all sorts of edge cases, unit behaviors, and occupancy cases (bad vs. allied units). The special-case logic included a state machine with something on the order of 40 different states, if I recall correctly.

      5. Separate pathing behavior for flying units, obviously. I plan another article on another hack used for flying units.

      • Alexander Spasov

        On point 1, does the game update the regions at any point? I just messed around in the editor making mazes with siege tanks (relatively big mazes, so as to include at least 2 regions) and the pathfinding worked pretty much flawlessly (i.e. following a proper path, not bumping around stuff). On the other hand, when I separated the other part of the map with a wall, and walled off one of the two entrances with buildings (the one that would screw up the better path), the tank I sent to cross the map bumped straight into the wall and then hugged the wall (so to say, that was just the new route I guess) until it came within the closest proximity to the target location (i.e. the point at the wall closest to it), ignoring the fact that there was a valid route on the other side of the wall – some kind of region-expanded greedy search subcase?

      • http://www.facebook.com/heinermann Adam Heinermann

        No the game does not update the regions at any point. They are generated once on map load. The exact structures used for this can be found here: https://code.google.com/p/bwapi/source/browse/branches/bwapi4/bwapi/BWAPI/Source/BW/Pathing.h

        Also, there are 35 pathing states for units which I extracted from the Broodwar Beta here: https://code.google.com/p/bwapi/source/browse/branches/bwapi4/bwapi/BWAPI/Source/BW/Path.h

      • Guest
      • Momchil Atanasov

        Ok, I got a bit confused… I though map cells were smaller than map tiles. Why would you split them into regions, shouldn’t you merge them?

        If tiles are 8×8 pixels, then how big are the cells?

        Also, if I understand correclty, there is a higher-level pathfinding with regions as nodes and a lower-one within those regions. How do you handle the different unit-sizes when doing the finder low-level pathfinding? Do you still use A* or another algorithm with some type of edge traversing?

        P.S. In the article above, shouldn’t the density of the barracks be 96×96 instead?

      • http://www.codeofhonor.com/blog Patrick Wyatt

        Sorry for the confusion! I’ve edited the article to use “cells” to refer to 8×8 pixel blocks, and tiles for 32×32 pixel blocks.

        When I said that the artwork “split” the tiles, I mean that the way the artists drew the isometric artwork caused them to appear partially unpassable, unlike War2 tiles which visibly appear to be wholly passable or wholly unpassable.

        In regard to finding paths for different unit sizes, the path-finding algorithm (A*) is aware of how much space a unit requires to pass through a gap.

        And finally, you’re right: 48×48 should have been 96×96. Apparently I need an editor!

  • Alexander Spasov

    I always thought that starcraft has 32×32 positions per tile… That explains why I was marvelling at the game’s performance and memory footprint on a 256×256 map while trying to build an engine with similar features and performance back in my last months at high school… ^_^
    If it’s not too much to ask, could you tell us about the basic structure behind the pathfinder – chosen algorithm, map representation structure/hierarchy, basically the general things without the corner cases? I’ve always been fascinated with the early RTS games as they were the thing that got me hooked to gaming/programming/computers in general early on.

    • Alexander Spasov

      Ignore, double posted for some reason… Sorry :(

  • http://www.facebook.com/people/Stephen-Wu/1177292180 Stephen Wu

    There was an issue with the non unit collision in Warcraft 3 with the ghoul unit. Basically in Warcraft 3 the Ghoul was a combat unit, but also the wood gathering unit for the Undead. Undead players would exploit this by what they called forest walking. In combat, ghoul’s would be order to collect lumber and they would walk through opponents armies giving them perfect surrounds.

    This obviously being overpowered was quickly fixed. I always wondered how this problem was fixed without harming gathering efficiency for the Undead race. Any thoughts?

    • http://www.facebook.com/NaibStilgar Stilgar Naib

      I think the gathering efficiency was not very important in this case. First of all trees in WarCraft are a secondary resource while minerals in SC are much more important. In addition trees are were laid out in a different manner in WarCraft III. For example there was no need for workers to stack on one tree. The economy of trees was also balanced around the fact that trees disappear fast and you have to harvest them at long distances one way or another. If I recall correctly even the gathering rate for trees was different for different races. Ghouls harvested more per trip than peasants and peons didn’t they? It is quite possible that the gathering efficiency was damaged a little bit but the game was not balanced around that so it didn’t matter that match. By contrast if you change the gathering efficiency in StarCraft you change EVERYTHING.

  • egfx

    Ha, this is interesting! I was in the QA department at Blizzard for just over a year. I don’t think we’ve met but I must have been a nightmare to your dev team. I found a bug that held up the release of Diablo 2 Expansion for a few weeks and was pretty much responsible for hundreds of syncing issue “graphics” bugs that flooded the WC3 tracker. From the QA departments point of view, we weren’t going to let you play as a ninja in multiplayer without owning the expansion set ;) and it wasn’t cool that you could click around a warcraft 3 map and see opppsing units and buildings flashing in and out. In essence your right. It was your decision and the producers call to make. From my point of view. The idea was, I think, we were working at Blizzard and we sought out to the best job for the product as we could do and Blizzard made perfect products.

    • http://www.codeofhonor.com/blog Patrick Wyatt

      I left Blizzard in 2000 to start ArenaNet, and so wasn’t around for the release of Diablo 2 or WC3, both of which released after I left. Glad you found those bugs! In particular the WC3 “flashing” bug would have ruined competitive play so that was an important find.

      • egfx

        well, it was serendipitous I guess. I got two fancy CRT’s As the Graphics QA team lead – so naturally I used them to play games against myself in search for “graphics” bugs. It turned out I found some. I just visualize it as 3D Game Engine Quantum Entanglement theory. I can only imagine how hard it was too fix!

  • http://aaronbonner.tumblr.com/ Aaron Bonner

    Do you think there is any hope at all that Blizzard will open source starcraft and its editor?

    • http://www.codeofhonor.com/blog Patrick Wyatt

      I don’t think it will ever be released, sad to say. Can’t release the sound code because it contains proprietary code licensed from 3rd-party, lots of embarrassment to be found in the code quality & comments, massive tool-set/tool-source-code would have to be released, relies upon Visual Studio 6, no documentation to speak of, no profit-motive or upside beyond PR value, creates competitor to SC2 brand-line extension, etc. etc. etc.

  • http://twitter.com/The_Young_Kumar Rishi Sadhir

    Love these man, keep it up.

  • Tac

    As a Starcraft player and programmer, I wouldn’t call “mineral walking” (as it’s called nowadays) a “hack”. It was a brilliant solution to an otherwise very difficult problem. It works very predictable, unobtrusive to casual players, but also an advanced technique that is useful for experienced players and pros.

    Trying to retrofit iso graphics on a tile game, on the other hand…. These are the kinds of things I would never allow myself to do sober :)

  • Anna Garrett

    The one day I don’t check your blog there is a post – just my luck!

    Was a great read and very interesting. I’ll have to remember this next time I pop out my Starcraft disk for a few games. Keep it up Pat! :D

    • http://www.codeofhonor.com/blog Patrick Wyatt

      Thanks, and glad you enjoyed the read! You can sign up to receive my articles via email — there’s a “Subscribe” link at the top. I use a mail service which monitors the blog RSS feed and sends mail when articles are published (but no more than once a day). I’m still working on the formatting, but at the very least you’ll know when I’ve published something because my posting frequency is irregular at best!

  • http://www.facebook.com/zoltan.mate.146 Zoltan Mate

    can i get the sourcecode of starcraft?

    • Joe Merol

      lol

  • Zo

    All of the three races’ worker units look like they’re floating while moving. When the worker units move on top of each other, this floating movement probably looks better then if the units were two-legged and had a walking animation.

    Did the worker units have walking animations sometime during development, and was this specifically changed to floating movement after your no-collision-hack was implemented?

  • RK

    Patrick, I owe thanks to the development and that work on the path fiding error for saving me once – one of the early Terran missions requires keeping a base for 30 minutes. Rookie me, I idled around with no enemy in sight, and got completely overrun the last minute until no Terran unit remained to be seen .. I won the mission nonetheless, back then seemingly by sheer miracle, because one of my SUVs had itself gotten trapped among chrystals so much that the attacking Zerglings couldn’t find a path to it. Now I know whom to thank for this!

  • unk32

    Path-finding probably the problem of century. It solved so many times and not solved still. Right now playing Diablo 3 and character and companion frequently stuck somewhere, unable to avoid corners and moving through hack: server teleporting companions.

  • Vitya

    Hehe, looks like most game features actually are bugs and hacks…

    Pat, have you some memories about developing Rock n’ Roll Racing?
    I’ve already knows that you works for creating ‘Tracks compiler’, and original game engine was RDS racing (not count RPM racing).
    If you can tell more or something interesting, I wish you to write a story in your blog.
    If not, maybe something about gamedev on old systems (Snes, Sega) – what software and hardware you have used, what problems were (systems limitations), e.t.c.

  • Allen Jiang

    thanks for sharing! I have a question, does starcraft use for dead reckoning or entity interpolation for client-side prediction?thank you in advanced.

  • abcdefgqwerty

    Its funny how given all that brood war is considered one of if not the greatest rts game ever made. A lot of times bugs and glitches actually turn out to make a game better by allowing for more skill such as stop lurkers or mutalisk stacking. Look at street fighter 2 a crossup was actually just some kind of hit detection bug yet now its a standard in fighting games.

  • cma

    Are you aware of the bug in which a group of workers can move while stacked at the same time (like right clicking minerals) and still be able to attack while still ignoring unit collision? Like having 12 scvs all stacked up, occupying one unit of space attacking at the same time? This can done with an empty vespene geyser, and is difficult to execute.

    1. Select workers
    2. Right click an empty vespene geyser
    3. Before the workers get to the geyser, hold shift and right click the geyser
    4. Still holding shift and before the workers get to geyser, press ‘a’ and left click a unit/building or a part of a map to attack.
    5. If executed correctly, the workers will move as one unit, and will not spread out even when attacking.

    This is truly a rarely known fact and only Starcraft veterans would know this glitch/bug. Even with the current patches this bug is not fixed, leading me to question what causes this. If you know please answer! If you do not understand what I am talking about I’ll upload a short video to demonstrate.

    • http://www.codeofhonor.com/blog Patrick Wyatt

      I don’t think I’ve seen that one, and I’m sure folks would love to see a video! The reason the bug likely exists is due to state-management issues. The pathing code is complicated enough that there is a way to change from one state where workers are stackable to another state without transitioning through the unstacking behavior.

      • cma

        Well here it is, I made it in a few minutes.

        http://www.youtube.com/watch?v=vlEMs0FhWfE

        An actually useful glitch/bug to defend rushes.

      • http://www.codeofhonor.com/blog Patrick Wyatt

        Awesome! Thanks for posting.

  • MillLalush

    I made a popular video describing in detail the movement/attack/patrol quirks that made advanced forms of “micro” possible for professional players in Starcraft 1.

    For Starcraft II, players have long been complaining about units feeling sluggish and behaving inconsistently. Anyway. The purpose of my video was to show the SC2 developers, in explicit detail, the factors which made unit control feel so fresh and responsive in Brood War (as well as to point out the bugs/inconsistencies in the SC2 engine that make the opposite true for that game).

    I thought you might find the video interesting. Shows exactly how devoted players used the quirks of your coding/design to the extreme in order to gain every advantage they possibly could.

    http://www.youtube.com/watch?v=CFO9gKGFPBM

  • Anonymous

    I find the pathfinding, with their hack, extremely interesting is SC. I fact, if we compare with SC2 and many RTS, every unit in SC had a different looking walking behavior wich provided them with a different personality. I think about dragoon, vulture, goliath, Reaver…
    In modern game every unit just glide perfectly!

  • Alisha Fox

    This is my very first time that I am visiting here and I’m truly pleasurable to see everything at one place.http://minionrushworking.blogspot.com/