The StarCraft path-finding hack
february 20, 2013 by patrick wyatt
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 andSupreme 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 tilestile-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).
Warcraft 2 map with 32×32 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.
StarCraft map with 8×8 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.
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.
Related video (time about 4:00, in OSL 2008 July vs Best set 2): Youtube.com