News for hackers. Stuff that matters.
Re:The StarCraft path-finding hack by onedognight on Wednesday February 20, 2013 @06:21PM (#5254063)
> 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.

Re:The StarCraft path-finding hack by AnIrishDuck on Wednesday February 20, 2013 @06:38PM (#5254175)
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 by lifeisstillgood on Wednesday February 20, 2013 @08:49PM (#5254839)
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 by ibrahima on Thursday February 21, 2013 @12:25AM (#5255594)
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