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  (20 - 30 of 126)
Firestorm51493
Firestorm51493 Feb 18 2011, 9:49am says:

Why are all starcraft mods dead, bad or cheep remakes of SC2?

+2 votes     reply to comment
Templarfreak
Templarfreak Feb 22 2011, 4:33pm replied:

These, "cheap remakes" are no where near done...You cannot call them cheap until they are finished, and the reason all those mods are dead...Is because they ARE finished!

+2 votes     reply to comment
Firestorm51493
Firestorm51493 Mar 2 2011, 1:57pm replied:

What do they do that's original? nothing. And with what I see only a few mods could be called done. Yes some are done but still.

+2 votes     reply to comment
LeonelC
LeonelC Dec 30 2010, 2:09pm says:

I Bought Starcraft 2 without knowing it was the limited version, and it expires in february :(

Damn, the Games purchase changed a lot and now sucks balls, :,(

I remember when i was 5, to buy, the only thing I needed was money, not a program, Internet, and a credit card like now :/.

Starcraft 2 is a perfect game, but... now the purchasing of a simple game requires a lot of useless stuff

+3 votes     reply to comment
omegasin
omegasin Jun 18 2010, 12:11pm says:

can someone make a starcraft halo mod? i would but i cant figure it out. i love halo wars but cant always play it and the 360 controls can be annoying. please!

+3 votes     reply to comment
SU154
SU154 May 26 2010, 3:09am says:

Oh...I'm sorry ,but I can't seem to understand what you guys are duscussing about .Do you wanna make a SC1 mod with SC2 features or SC2 mod bringing back the old gameplay ?

0 votes     reply to comment
ElderPredator
ElderPredator Feb 14 2010, 10:01am says:

Ho love StarCraft,check this... Moddb.com

+2 votes     reply to comment
shadowboss6
shadowboss6 Jan 20 2010, 3:58am says:

hey im looking for a mod that changes the colors of the races instead of the standard colors

+2 votes     reply to comment
DedMustDie
DedMustDie Jul 3 2010, 11:26am replied:

You don't really need a mod for that - advanced editors allow you to use one of 255 colors. Some of them (colors I mean) are "glitched" and cause units to change color every second ;p

+2 votes     reply to comment
Templarfreak
Templarfreak Aug 27 2009, 3:31am says:

hey any1 wanna help with a sc2 mod for sc1 im working on? we need ppl good with art...... thats about it me and this other guy can do the rest

+3 votes     reply to comment
lol1234
lol1234 Jan 1 2010, 11:40pm replied:

dont look at me man i suck at coding and all other elements of modding XD

+2 votes     reply to comment
MPSGA
MPSGA Nov 3 2009, 3:03pm replied:

Don't you also need AI pro?

+2 votes     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
1 day ago
Watchers
172 members
Mods
94
Addons
28
Files
215
News
42
Features
3
Tutorials
5
Reviews
21