Pages

Tuesday, February 26, 2013

The Curious Case Of StarCraft’s Harvester Pathfinding Hack

StarCraft 2

Even the most mundane game mechanics sometimes boast extraordinary origins. In the StarCraft series, resource collectors ignore collisions whenever traveling to or returning with minerals. It’s a type of unit behavior universally experienced by every commander, but its beginnings tell a far more interesting story: ArenaNet co-founder and former Blizzard senior programmer Patrick Wyatt writes in aretrospective articlehow the simplified pathfinding arose from a quick and dirty hack to meet a looming release deadline for the original 1998 RTS.

“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 pathfinding easier, so the pathfinding code just had to be made to work,” Wyatt recalls.“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.”

The trickiest problem for StarCraft’s programmers involved harvesters clogging up the area around mineral nodes as they jostled for free grid space on the terrain. The issue snowballed at that point--cash-flow screeched to a halt because of the traffic jam, and the player’s bases and armies would fall apart as a result.

StarCraft Brood War

Wyatt’s solution forsook elegance for expediency, but it worked:“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 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.”

What’s more interesting is that Blizzard never removed the hack. Because of its effectiveness, it remained in subsequent releases in the franchise--yes, even StarCraft 2--and ingrained itself deeply into basic harvester strategy. Savvy eSport athletes even leveraged the hack as an unconventional tactic during tournaments--the2008 Brood War OSL matchupbetween July and Best is perhaps the most famous demonstration of using harvesters to sail through a blockade.

Wyatt goes into further detail on StarCraft’s grid design similarities with the WarCraft games and how pathfinding was affected during development. It’sa truly fascinating read.


No comments:

Post a Comment