Live data from Hacker News

The StarCraft path-finding hack

codeofhonor.com

31–40 of 87 posts

Re: The StarCraft path-finding hack

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

Re: The StarCraft path-finding hack

#32
post #19

Earlier quoted context omitted.

see also quake rocketjumping, strafe jumping, bunnyhopping, etc. when carmack wanted to fix all those issues in q3arena, the players protested, because the game was dull.

And skiing in Starseige: Tribes, a bug with the jumping code. They had to reimplement it for all the following games.

And sadly, they never got it quite right! none of the subsequent tribes games had the same skiing behaviour. The only reason the competitive community in Tribes 2 has hung on for so long is that a community mod sped the game up to be more like Tribes 1.

Forget about Tribes: Vengeance & Tribes Ascend, neither captured that same feel.

Re: The StarCraft path-finding hack

#33
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…

From what I understand it was pretty problematic to multiplayer too, since with a bunch of carriers it becomes difficult to manually target them behind all the interceptors.

Re: The StarCraft path-finding hack

#34
post #16
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…

Starcraft singleplayer always seemed sort of like Q3A singleplayer to me. Clearly not the main attraction.

Re: The StarCraft path-finding hack

#35

I wonder what part of their path finding algo created a glitch like the drone float[1] [1] http://www.youtube.com/watch?v=7MN0wjoqmzU

I suspect a hack was involved -- the animation leading up to the construction of a Zerg Extractor involves the drone hovering over the geyser temporarily. This requires the unit to be put into a "floating" state which wasn't properly cancelled if the build failed -- queueing up additional move commands would then allow it to clip through barriers.

A number of similar bugs with queued commands existed. I get the sense that this feature wasn't adequately tested. :)

Re: The StarCraft path-finding hack

#36
post #12

It's pretty cool to see the source of this. Back when I used to play Starcraft I primarily played UMS maps (custom game modes) and several of them were based on using "bugs" in the game engine to surmount situations that appeared impossible. Moving a harvester unit past an invincible wall of enemies was one of these, which was accomplished by right clicking on a further mineral field. It's interesting to see that thi…

AD. exploding siege tank, it was actually a fix in one of the patches. Some players discovered that you could land a building on a tank if you time the landing right with switching to siedge mode, making the tank unreachable for meelee units (which were the kind of units usually used against the tank). It created an unfair advantage, so Blizzard removed it by making the tank explode when landed on.

Funny fact: if you landed a building on your opponent's tank, you could actually get a label "Kills: 1" on the building :D.

Re: The StarCraft path-finding hack

#37
post #19

Earlier quoted context omitted.

see also quake rocketjumping, strafe jumping, bunnyhopping, etc. when carmack wanted to fix all those issues in q3arena, the players protested, because the game was dull.

And skiing in Starseige: Tribes, a bug with the jumping code. They had to reimplement it for all the following games.

From my memory, they actually discovered that bug during development and decided that it actually improved gameplay, so they made it a feature before it was released.

Re: The StarCraft path-finding hack

#38

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 "greedy" choices made by the salesman can force him to make much less efficient choices later.

I remember circuit routing was an example in Skeina's Algorithm Design Manual [1], and believe he proved that it was indeed NP-complete, not polynomial like the general pathfinding problem.

1. http://www.amazon.com/Algorithm-Design-Manual-Steven-Skiena/...

Re: The StarCraft path-finding hack

#39
post #16
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…

Then don't use the carrier... Long games against the computer were never fun in starcraft (or most other similar games). It becomes gamebreakingly easy to win if you survive long enough and the AI becomes utterly useless, it is clearly not something that the developers even cared to put some thought into. And that's okay, the real essence of starcraft is multiplayer.

Re: The StarCraft path-finding hack

#40
post #24
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…

Is changing the behavior of a group of units because it happens to be grouped with a distant unit really a good thing for the game? It makes for a good story, and it's great fun for the person who discovers it. Players like it, because it lets them beat new players even more easily. But players don't always know what's best for them. This is why Starcraft 2 multiplayer is structured to force players to play on compli…

Your comment on starcraft maps is off.

Both SC2 and BW have two sets of maps, UMS maps with custom settings used for fun games and competitive maps made to be racially balanced and produce "good" games. In SC2 UMS maps are part of the arcade where as ladder games are played on tournament maps. The same is true for BW but blizzard didn't have an official ladder so 99% of the games on battle.net were UMS maps, but ICCUP ladder had the same competitive maps you see in SC2.

As far as the glitches are concerned, they were undoubtedly beneficial to BW, as the last balance patch was in 2001 when the game was in its infancy as far as strategy goes. For example TvZ could not be played in its current form without muta stacking and terran's still have more success despite it. 99% of players would never use these tricks of have them used against them, but it allowed for the game to advance strategically and added an additional element of skill.

Post reply on HN