Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

The StarCraft path-finding hack

codeofhonor.com

Post reply on HN
Print view View original

41–50 of 87 posts

Re: The StarCraft path-finding hack

#41

Post by groby_b »

stcredzero wrote: post #25

> 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. This seems like a pain point that's an opportunity in disguise. A technology that made it much easier to get mult…

Yes and no. Video games are always extremely resource constrained. While you could solve networking in a generic way, it also means inefficiencies that many teams are not willing to take. (Also, it precludes certain shortcuts taken that allow FPSs to have eventual consistency, at a rudimentary level)

As for "no one notices the evil compromises", the author is missing the second part: "except the people who have to look at that code a few years later". TANSTAAFL - at some point, somebody will pay.

This didn't matter back in the good old days, where tech progressed so rapidly that you'd basically started from scratch for each new game, but it bit a lot of teams in the last console cycle, where re-using made economic sense.

Re: The StarCraft path-finding hack

#42

Post by kevingadd »

prawks wrote: post #31

> 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. Really enjoyed this part of the article. When you have an infinitely long two-month period, you still can't complete a task that requires three months.

That mindset is sadly pervasive in the game industry (no doubt other software as well, but imaginary ship dates have a terrifying power in games due to The Holidays)

Re: The StarCraft path-finding hack

#43

Post by ChuckMcM »

AnIrishDuck wrote: post #38
ChuckMcM wrote: post #26

I remember thinking to myself, at a talk given by an Activision employee on some Mechwarrior pathing issues, that these guys were re-inventing printed circuit board layout. They had the same sorts of constraints, go from here to there, don't cross certain types of 'terrain' (traces in the layout case). Game units don't get to make vias though :-)

Pathfinding is a much easier problem than circuit routing and can essentially be solved in O(n + k) where n is the number of nodes and k is the number of edges between nodes. Circuit routing is an entirely different beast. A previously routed "shortest" trace from one node to another can obstruct a much shorter trace between two unrelated nodes. In this way it's similar to the traveling salesman problem, where early…

"Pathfinding is a much easier problem than circuit routing"

I'm not sure I agree with that, the mechwarrior talk was pretty informative and the variability of terrain and dynamic obstacles made for some interesting challenges. It was particularly interesting when they talked about 'squad walking.' (going into a line in tight spaces etc) When I was thinking about writing my own RTS I did some simple experiments and certainly got a feel for it being quite complicated.

Re: The StarCraft path-finding hack

#44

Post by edias »

invalidOrTaken wrote: post #14

What no one has mentioned is how many "essential" skills have arisen as a result of this hack. For instance, an everpresent threat in Starcraft is the Zerg Rush, in which a player skips building an economy to build zerglings---cheap, light, raider units--- to attack the opponent early before he has any defenses (as he, presumably, has not skipped building an economy). The zerglings are melee attackers, so holding a s…

What your describing is called the drone drill, where you have all the workers attack at once, but this is a trick only used for dealing with the 3 pylon block (something banned in tournamnet play) as zerg. http://www.youtube.com/watch?v=M9CA9AahV1E

How the pathing trick is actually used to deal with zerglings is to have them walk ontop of the zerglings with the mineral trick and then attack, causing the workers to spread out around the unit trapping them while have the maximum amount of surface area to attack, as seen in this video. http://www.youtube.com/watch?v=X08jueOiGFk#t=140s

Re: The StarCraft path-finding hack

#45

Post by edias »

tolmasky wrote: post #18
Dove wrote: post #13

Earlier quoted context omitted.

Really? That's interesting. I've noticed that units never seem to have the good sense to target Brood Lords rather than Broodlings when they have a choice. It seemed odd, given that the AI had improved so much in other areas -- pathfinding, running from unwinnable fights, varying its opening strategies. It never occurred to me that things might be that way because it's fun !

These units are basically specifically designed to require micro-ing from the player. Both brood lords and carriers are pretty weak if attacked head on (slow/low-hitpoints)-- their entire strength is in the fact that other units will auto-attack broodlings/interceptors first (which makes some "conceptual" sense since that's what actually attacking them).

Not at all. Maybe for beginners but at the competitive level brood lords are so good due to their cost efficiency in that they create "free" units and have very good synergy with infestors which are also known for their cost efficiency.

Re: The StarCraft path-finding hack

#46

Post by edias »

john_b wrote: post #6
GavinB wrote: post #3

The Protoss Carrier regularly lagged behind other units because it had its own way of doing … everything. The Carrier should have been scrapped entirely and replaced with a different air unit. Even to the latest upgrades of Starcraft I, the AI simply couldn't deal with the carrier effectively--they would always attack the interceptors first. This made using the carrier a cheap game-breaking trick against the computer…

...and made it one of the most interesting units in multiplayer. In programmer-land, where all abstractions should be pure and elegant, the carrier (as implemented in SC1) may be abhorrent, but this is irrelevant because the customers (i.e. the players) loved it . Some of the quirky behavior of the SC1 carrier was even re-implemented into the upcoming SC2 expansion at the behest of fans. Why? Because it made the unit…

No, because it adds an element of skill that was missing from the SC2 carrier. Here is the video that caused the quirks to be included and Nony makes a very compelling case in it. http://www.youtube.com/watch?v=1Rqx8s2qKXM

Re: The StarCraft path-finding hack

#48

Post by Rastafarian »

bradleyjg wrote: post #10
CyrusL wrote: post #5

One of the reasons Starcraft is interesting as an e-sport is because bugs like this have kept the game in racial balance for over a decade. For example, the game was not designed to give mutalisks the ability to stack on top of each other. However, at some point in the early 2000s, it was discovered that when 11 mutalisks were grouped with 1 overlord, the mutas tended to stack: http://www.youtube.com/watch?v=NfqQYJzq…

There were all kinds of discoveries like that. I remember when the reaver drop was invented by someone out of MIT. Can't remember his handle but he was one of the top players pre-brood war. Edit: Found him, Zileas aka Tom Cadwell. Brings back the memories.

Reaver drop was not invented by Zileas, he only popularized it.

Re: The StarCraft path-finding hack

#49

Post by tolmasky »

edias wrote: post #45
tolmasky wrote: post #18

Earlier quoted context omitted.

These units are basically specifically designed to require micro-ing from the player. Both brood lords and carriers are pretty weak if attacked head on (slow/low-hitpoints)-- their entire strength is in the fact that other units will auto-attack broodlings/interceptors first (which makes some "conceptual" sense since that's what actually attacking them).

Not at all. Maybe for beginners but at the competitive level brood lords are so good due to their cost efficiency in that they create "free" units and have very good synergy with infestors which are also known for their cost efficiency.

I'm not sure what your "Not at all" is in response to. I was saying it requires micro-ing from the person going up against them (specifically, you need to blink your stalkers under the brood lords, or tell your units to target the carriers and not the interceptors, etc etc). In other words, they are not units designed to be fought against by just a-clicking in their general direction and letting the AI do the work for you.

Re: The StarCraft path-finding hack

#50

Post by acabal »

This is such an amazing blog. It's fascinating to read about the sloppy guts of games you spent hours on in your youth.

It's also a testament to Blizzard's dedication to polish, because although I was only ever a casual Starcraft player, I spent more hours on that game than any other game in my life and I never noticed any bugs that betrayed the apparent messiness of the codebase.

Post reply on HN