Developed by Blizzard following the sucessful WarCraft series, Starcraft is undoubtably one of the most innovative and popular RTS games to hit the market. Introducing for the first time three races all completly unique yet perfectly balanced, this made for some fantastic gameplay with zergling rushes, to siege tank massacres.

With starcraft having such a cult following there are bountiful mods available from simplistic character changes to new scenarios, and challenges to face. The fact that Starcraft has been game of the year sums up just how good this game is, so crank it up if you are not already playing it!

Image RSS Feed Latest Screens
SC MOD for android StarCraft Hybrid War unit: Hybrid Juggernault StarCraft Hybrid War unit: Hybrid Juggernault
Blog RSS Feed Report abuse Latest News: The StarCraft path-finding hack

0 comments by Kurohige on Jun 2nd, 2015

The StarCraft path-finding hack

february 20, 2013 by

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).

Annotated Warcraft 2 screen captured show tile edges

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.

Annotated StarCraft screen captured show tile edges

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.

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.

-----

Related video (time about 4:00, in OSL 2008 July vs Best set 2): Youtube.com

Media RSS Feed Latest Video
Downloads RSS Feed Latest Downloads
Sc2mod-v0.3
StarCraft

Sc2mod-v0.3

May 19, 2015 Starcraft 2 mod - 2015 Demo 0 comments

Menu image, background, some animations changed. Terran ambience sound added, terran music removed.

Gravity Mod v1.1
StarCraft

Gravity Mod v1.1

Apr 29, 2015 Gravity Mod Full Version 0 comments

I decided to close project. That is stage on which it was after last changes. Added XN-Forge, more upgrades, few improoved AI, partial control over units...

Starcraft 2 mod - v0.2
StarCraft

Starcraft 2 mod - v0.2

Apr 26, 2015 Starcraft 2 mod - 2015 Demo 0 comments

News : Attack/ explosion sounds optimized. Some ships movement sounds added. Scout model changed. Some terran building added ( wip models ).

Starcraft 2 mod - v0.1
StarCraft

Starcraft 2 mod - v0.1

Apr 21, 2015 Starcraft 2 mod - 2015 Demo 6 comments

All wireframes changed. Some buttons changed. Unit stats like in sc2. Effect sounds like in sc2.

SC1 H.O.T.S MOD 0.01 - Phoenix
StarCraft

SC1 H.O.T.S MOD 0.01 - Phoenix

Apr 20, 2015 Starcraft1 Heart of the swarm MOD Full Version 0 comments

Add to Phoenix - New Units Enjoy the starcraft 2 Heart of the swarm in starcraft 1 brood war

LOTV Siege Tank in SC1
Game

LOTV Siege Tank in SC1

Apr 5, 2015 Other 3 comments

If you want siege tanks carried in siege mode in sc1, this one is for you. What i did is i added a movement script in the siege tank in siege mode (both...

Post comment Comments  (60 - 70 of 126)
Daywalkers
Daywalkers May 31 2007, 1:04pm says:

I'm SC GOSU SC RULLZ

+1 vote     reply to comment
shadowless
shadowless May 29 2007, 10:33pm says:

Blizzard is still going to keep Battle.net open to StarCraft when SC2 comes out. Blizzards is still probably going to make patches, so I think they'll still support the original StarCraft for a few more years (hopefully longer.)

My mod was unaffected by the 1.15.0 patch, so I will keep going with it.

+1 vote     reply to comment
winskymin
winskymin Mar 21 2009, 10:02pm replied:

can u help me where to download the full version of starcraft not the demo or just send me the setup.exe @winskymin@yahoo.com thanks

+1 vote     reply to comment
Lord_Grievous
Lord_Grievous May 22 2007, 5:38am says:

Blizzard has announced StarCraft II

Woot :)

+1 vote     reply to comment
Psiyon
Psiyon May 19 2007, 11:07am says:

www.starcraft2.com
Its FINALLY HERE!!!!!

+1 vote     reply to comment
1n3flip
1n3flip May 15 2007, 10:07pm says:

aww cant belvie blizzard is gonna kill off sc to make sc2 successful

+1 vote     reply to comment
Shadie_18
Shadie_18 Apr 11 2007, 1:47pm says:

well thats blizzard for you always stayin one step ahead of the game, give it a couple months after release someone will find a loop hole and start makin mods................lol

+1 vote     reply to comment
Psiyon
Psiyon Mar 27 2007, 3:29pm says:

Blizzard is about to release all of our impending doom. Patch 1.15 is on the way to kill all mods, in one swift strike.

* Do note, its not going to kill them, but kill all good hope for them without firegraft*

The good is that patch 1.15 prevents pretty much all hacks known.

+1 vote     reply to comment
Shadie_18
Shadie_18 Mar 22 2007, 11:39pm says:

Shadowless is right if u want better graphics play warcraft 3 or command and conquer generals but if u want an awesome RTS game for lower end system starcraft is the way to go, and there are more then 50,000 people who play and love this game online so why dont u go on the blizzard forums in the starcraft area and try and complain there........LOL

+1 vote     reply to comment
Clonest
Clonest Mar 19 2007, 9:38pm says:

FORGET STARCRAFT ORGINAL CHARACTERS...BRING IT ON WITH THE STAR TREK AND BSG SHIPS!!!!!!!!

+1 vote     reply to comment
Post a Comment
click to sign in

You are not logged in, your comment will be anonymous unless you join the community today (totally free - or sign in with your social account on the right) which we encourage all contributors to do.

2000 characters limit; HTML formatting and smileys are not supported - text only

Icon
StarCraft
Platforms
Windows, Mac, N64
Developer & Publisher
Blizzard Entertainment
Engine
Unknown
Contact
Send Message
Official Page
Blizzard.com
Release Date
Released Feb 6, 1998
Game Watch
Track this game
Share
Community Rating

Average

9.3

293 votes submitted.

You Say

-

Ratings closed.

Highest Rated (5 agree) 10/10

Best game hands down!

Oct 21 2011, 11:49pm by Zealot55

Style
Genre
Real Time Strategy
Theme
Fighter
Players
Single & Multiplayer
Project
AAA
Boxshot
Boxshot
Sequels
Starcraft II: Heart of the Swarm, Released Mar 11, 2013
Logo
StarCraft II: Wings of Liberty, Released Jul 27, 2010
Logo
StarCraft, Released Feb 6, 1998
Logo
Twitter

Latest tweets from

It can take up to a few hours for tweets to begin appearing.

Embed Buttons

Promote StarCraft on your homepage or blog by selecting a button and using the embed code provided (more).

StarCraft StarCraft
StarCraft
Statistics
Last Update
6 hours ago
Watchers
172 members
Mods
94
Addons
28
Files
215
News
42
Features
3
Tutorials
5
Reviews
21