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

61–70 of 87 posts

Re: The StarCraft path-finding hack

#61

Post by AnIrishDuck »

onedognight wrote: post #60
AnIrishDuck wrote: post #38

Earlier quoted context omitted.

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 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. What you are describing is the complexity for a single path. But there are lots of units that need to be placed and have their paths potentially interact to achieve some goal. This seems very analogous to circuit routing.

Fair enough, once you start needing to path many units at a time (where their movements can potentially conflict with each other), then it starts to sound a lot more like circuit routing.

Re: The StarCraft path-finding hack

#62

Post by saraid216 »

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…

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

It's worth pointing out that I've seen a similar argument made for Street Fighter 2: that a lack of rebalancing is what made it such a popular tournament play, or some such.

Re: The StarCraft path-finding hack

#63

Post by skittlebrau »

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…

I worked at Ensemble Studios (Age of Empires) and by the time we shipped Age of Mythology we had much better tools for dealing with sync bugs. Most of the run of the mill ones could be tracked down pretty quickly, but there were still plenty of painful ones. What made them easier to track down was a more advanced tracking/logging system for the simulation state history. The simulation was littered with tons of sync logging code that tracked the execution flow and values of things as they were calculated/updated. When the state went out of sync, all the machines would dump their last couple updates worth of logging (often several gigs) and you could diff them to see where things diverged. If you were making a synced simulation game, a nicely done version of this type of thing would be pretty useful to have, especially if you made a good diff tool to go with it.

It's not completely obvious what technology you could make that would make it easier to avoid sync bugs in the first place. You could make a good network command-passing and simulation timing library, but in my experience the majority of problems did not come from bugs with the networking itself. Most of the sync bugs were from things like uninitialized variables, memory overwrites, using user input or other local machine state directly in the simulation without going through a multiplayer command, using a non-synced random number generator in the sim, DirectX changing the FPU rounding mode on you, etc. (Using a "safer" language would help with stuff like uninitialized variables/memory overwrites of course, but at an inevitable performance cost. Static code analysis tools are pretty good at finding these type of problems now too.)

Re: The StarCraft path-finding hack

#64

Post by AnIrishDuck »

ChuckMcM wrote: post #43
AnIrishDuck wrote: post #38

Earlier quoted context omitted.

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 ce…

I was confused by your original comment. You're absolutely right though; trying to path a squad of multiple units so that their routes don't conflict is much harder. I can see how it could be very similar to circuit routing.

Heck, it probably has the same basic time complexity and is amenable to the same algorithmic solutions.

Re: The StarCraft path-finding hack

#65

Post by saraid216 »

GavinB wrote: post #16
john_b wrote: post #6

Earlier quoted context omitted.

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

A fun unit in multiplayer isn't really a good excuse for a gamebreaking behavior in single player. An examination of what it was that made the Carrier fun might have revealed ways to get similar effects (long range, able to fire while retreating, requires paying minerals for continued use . . .) in a unit that wasn't such a weird gamebreaker. Most people just liked Carriers because it cast a field of enemy unit and A…

> A fun unit in multiplayer isn't really a good excuse for a gamebreaking behavior in single player.

Actually, it is. Single player is basically a financial dead end: you play it through X times, interact with very few people, and put the game away.

If you end up breaking it in favor of gameplay where players are generating content on your behalf (each other)... the loss rapidly disappears as people stop playing the single-player because it not only sucks, it's irrelevant.

Re: The StarCraft path-finding hack

#66

Post by jiggy2011 »

I've been curious for a while as to how path-finding gets implemented in real world games.

For example, the common algorithm appears to be A* where you use some heuristic to guess the most efficient path but update the path when you find another is more efficient (for example you hit a large wall on the first path).

This is easy enough when you have only one moving object (because you can just compute that path at the start and then follow it), however in a real game there are likely many moving colideable objects and you might choose a path that causes you to get stuck or have to take a very suboptimal path.

The most "correct" way to do it would be to recalculate the path for each moving object on each frame, but this would probably lead to unacceptably poor performance.

So you can wait until you get stuck and then try and find a path out (which may be impossible). Or you can divide your path into recursive sub-paths and compute different sub-paths as you move.

Now for simulation this is interesting, for example if you order a military unit to move to some location in real life then you would expect them to at least consult a map before setting off however there may be unanticipated situations on the ground which mean that they have to take a suboptimal path. So pathfinding inefficiency might add realism.

I have noticed that overall path finding is much improved in modern games, especially RTS. So curious roughly how their implementation works.

Re: The StarCraft path-finding hack

#67

Post by martinced »

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…

Wow. That's an impressive hack.

I remember when I played Warcraft 2 (also mentioned in TFA) competitively (WC 2 wasn't meant to be played on the Internet, but we'd use Kali to simulate a LAN over the Internet and then we'd use trust-based ranking websites)...

The "build" was to put two barracks (or any other building) just touching each other by a corner and you'd then put three units in a special formation: then any rush would result in the rusher only being able to attack with one unit while you'd have three units hitting the attacker.

Needless to say rushes weren't a big part of the game in WC2 ; )

Re: The StarCraft path-finding hack

#68

Post by d0m »

There was a fun bug with zerg in the early days of Starcraft where you could build everywhere on the map even your drone wasn't there. I don't remember exactly how, but I know it was using a mineral path-finding bug :O

Re: The StarCraft path-finding hack

#69

Post by mcfunley »

bradleyjg wrote: post #58
Rastafarian wrote: post #48

Earlier quoted context omitted.

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

Do you happen to know who invented it? Was it someone else at MIT?

1_COOL_GUY was #1 on bnet for a long while using the reaver drop coupled with the map hack. Not sure if he invented this either, but this was before Zileas (a legit player) came along.

(Can't believe I remember these details.)

Re: The StarCraft path-finding hack

#70

Post by ihsw »

mitchi wrote: post #30
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…

I played Warcraft 3 and the same trick was used to surround a hero with ghouls. Since ghouls are also the unit that gathers lumber for the Undead Race, they enter a no-collision state when you right click on a tree. This behavior was patched because it was too strong. You would just click on a tree behind the enemy hero and all your ghouls would pass through all the other units (footmen for example) and they could su…

Another WC3 glitch is Shades (invisible scouting units) that triggered collision but you couldn't target them due to being invisible. Eventually players caught on and lined Shades up to create impassible and invisible walls.

To combat this you had to devote significant resources to units and buildings that could reveal invisible units, and eventually Blizzard patched it. Very interesting.

Post reply on HN