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 edges

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/dp/1849967202/ http://www.amazon.com/Algorithm-Design-Manual-Steven-Skiena/...

ChuckMcM 14y ago
"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 certainly got a feel for it being quite complicated.
- AnIrishDuck 14y ago
  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.
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 ago
  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.
  - lifeisstillgood 14y ago
    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.
    - ibrahima 14y ago
      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 http://www.teamliquid.net/blogs/viewblog.php?topic_id=306999

ChuckMcM 14y ago

"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 certainly got a feel for it being quite complicated.

AnIrishDuck 14y ago
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.

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 ago
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.
- lifeisstillgood 14y ago
  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.
  - ibrahima 14y ago
    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 http://www.teamliquid.net/blogs/viewblog.php?topic_id=306999