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

71–80 of 87 posts

Re: The StarCraft path-finding hack

#71

Post by omni »

edias wrote: post #44
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 s…

I wasn't aware that competitive StarCraft had ever banned anything that was intended by the game engine, and Google isn't turning up anything. Could you provide a source?

Re: The StarCraft path-finding hack

#72

Post by GhotiFish »

GavinB wrote: post #24
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…

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…

Supreme commander 2 used flowfield for their pathfinding. Flowfield does an ok job, but it actively tries to group units together by giving them little pushes in the correct direction.

As a result, in competitive play, players would leave one or two units at home, when they advance they would select all their front line units and move forward, when they retreat they would select all their front line units plus the units at base, and flowfield would cause the front line retreat to exceed unit velocity!

Re: The StarCraft path-finding hack

#73

Post by prawks »

kevingadd wrote: post #42
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)

I would imagine The Holidays wouldn't be a moving target as much as "soon" is, however.

Re: The StarCraft path-finding hack

#74

Post by lifeisstillgood »

AnIrishDuck wrote: post #61
onedognight wrote: post #60

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

Maybe but it's more traffic - ten units can find Independant paths to a goal. If paths intersect on a pcb you must reroute. If the units paths intersect t one waits till other moves then continues.

Maybe it's too simplistic but in the vein of the outrageous hack I like it.

Re: The StarCraft path-finding hack

#75

Post by rtpg »

Am I the only one who is bothered by the fact that changing the perspective rendering somehow forced them to go and change the pathfinding? How recent is MVC design patterns?

Re: The StarCraft path-finding hack

#76

Post by TheMakeA »

omni wrote: post #71
edias wrote: post #44

Earlier quoted context omitted.

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

I wasn't aware that competitive StarCraft had ever banned anything that was intended by the game engine, and Google isn't turning up anything. Could you provide a source?

In tournament play, it isn't "banned" in a sense that you are fouled or disqualified for doing it. It's a map design and racial balance issue, which tournaments usually solve systematically by placing a neutral supply depot to prevent placing a 3rd blocking pylon. Check out [1] or [2] or search for "neutral supply depot" to find some more information.

[1] http://gaming.stackexchange.com/questions/51630/why-are-ther...

[2] http://wiki.teamliquid.net/starcraft2/Buildings#Neutral_buil...

Re: The StarCraft path-finding hack

#77

Post by edias »

omni wrote: post #71
edias wrote: post #44

Earlier quoted context omitted.

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

I wasn't aware that competitive StarCraft had ever banned anything that was intended by the game engine, and Google isn't turning up anything. Could you provide a source?

TheMaka already answered this specific case and there is indeed nothing technically "banned" in competitive SC2.

BW however did have a few bugs that were banned by tournament ogranizers [1].

[1] http://wiki.teamliquid.net/starcraft/Competitive_Rules

Re: The StarCraft path-finding hack

#78

Post by tec27 »

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…

While this is a fairly good explanation of some interesting things about Starcraft, I think something truly interesting about mutalisk stacking in particular is its actual discovery date. It wasn't, in fact, discovered in the 'early 2000s', but rather in mid 2006, a good 7 years after the game was released.

Prior to this trick's discovery, players stacked mutalisks by right clicking the group onto a mineral patch or gas geyser, which causes them to clump up more than right-clicking onto the ground (July, who you mention, actually won at least the first 2 OSLs without the benefit of this trick). I would imagine that air units in Starcraft have a similar hack applied to their moving collision detection as the workers do with mining, as the exhibit a lot of the same behaviors (okay with being on top of each other while moving, spread out as soon as they stop moving).

Re: The StarCraft path-finding hack

#79

Post by ibrahima »

lifeisstillgood wrote: post #74
AnIrishDuck wrote: post #61

Earlier quoted context omitted.

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.

Maybe but it's more traffic - ten units can find Independant paths to a goal. If paths intersect on a pcb you must reroute. If the units paths intersect t one waits till other moves then continues. Maybe it's too simplistic but in the vein of the outrageous hack I like it.

I think that's basically what SC1/BW did. There was a professional game last year[1] where one player (Jaedong, probably the best Zerg at the end of BW) had one unit blocking a ramp in his base, and something like 30 hydralisks stacked up behind it. He was attacking the enemy so he didn't notice at first and I think he probably lost his main army but then found a huge second army that had been stuck and just rolled the poor guy.

[1] http://www.teamliquid.net/blogs/viewblog.php?topic_id=306999

Re: The StarCraft path-finding hack

#80

Post by otoburb »

martinced wrote: post #67
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…

I think I still have my Kali key somewhere. Brings back great, old memories.
Post reply on HN