3 ms·
> 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 edge
by onedognight 14y ago
> 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.
- AnIrishDuck 14y agoFair 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.
- lifeisstillgood 14y agoMaybe 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.
- ibrahima 14y agoI 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 http://www.teamliquid.net/blogs/viewblog.php?topic_id=306999