5 ms·

Something has puzzled me about pathfinding in games. There is a well-known algorithm[1] for finding an optimal path: you start at the destination, assign that

Something has puzzled me about pathfinding in games. There is a well-known algorithm[1] for finding an optimal path: you start at the destination, assign that a cost of 0, make a queue from the points that can reach it directly, compute for each of those points the minimum "cost of directly reaching a marked point + cost written on the marked point", and then, while the queue is nonempty, taking the point with the cheapest minimum cost, marking that point with that cost, adding the point's neighbors to the queue, and recomputing the "minimum cost" for everything that can directly reach the point. You can then either terminate when your source point gets marked, or maybe keep going and keep the whole table around for the next time you need a path to that destination. At least in turn-based games like Civilization, where most of the runtime is spent letting the player think while refreshing the display, it seems eminently feasible to do this every time a unit is given a goto command. (Also the number of points isn't that large: probably a few thousand distinct squares, much less if you restrict yourself to continents.) Yet Civilization II, at least, yields obviously suboptimal results, and I think I read that one thing it does is run a "perfect" search for every square on the screen, but do something more stupid if part of the optimal path is off the visible screen. In an RTS, the terrain is probably somewhat more continuous, so there may be more "points" to deal with, and probably more paths need to be computed. Structures are built and destroyed, changing the terrain and the paths; units are moved around much more frequently, though arguably the presence of units should be ignored unless you're very close to the destination. Commands are issued much faster. All these add to the problem, but still... I would expect games to be implemented first with perfect pathfinding, and then, if that was prohibitively expensive, to have optimizations, possibly "lossy optimizations" (i.e. heuristics), perhaps a bunch of caching or maybe "computing things at low resolution first"... And every optimization could be easily tested against the perfect pathfinding. If the optimizations would often lead to abysmal path-choosing, then this would be very easy to discover in testing. So I'm surprised that games could have been released with pathfinding bad enough to become infamous. And yet this seems to have happened in multiple games (e.g. in Starcraft). How? Am I severely underestimating the problem difficulty? Did people not even try for perfection because of how slow CPUs were? Did people just assume basic heuristics would work and not bother to check—I guess they didn't have the advantage of learning from the failures of the previous generation? [1] "Dijkstra's algorithm" seems to be what the kids call it. Did Dijkstra only ever come up with one algorithm? I think "frontier algorithm" would be an improvement. Oh well. https://en.wikipedia.org/wiki/Dijkstra%27s_algorithm https://en.wikipedia.org/wiki/Dijkstra%27s_algorithm

morsch 9y ago
According to TFA, they're using A-star[1]. This seems to be common.[2] Am I severely underestimating the problem difficulty? Did people not even try for perfection because of how slow CPUs were? Did people just assume basic heuristics would work and not bother to check—I guess they didn't have the advantage of learning from the failures of the previous generation? I am not a game programmer but presumably: yes, yes, no. Though TFA says the original edition's A-star implementation was "outright broken". [1] https://en.wikipedia.org/wiki/A*_search_algorithm https://en.wikipedia.org/wiki/A*_search_algorithm [2] https://gamedev.stackexchange.com/questions/5013/how-does-pathfinding-in-rts-games-work https://gamedev.stackexchange.com/questions/5013/how-does-pa...
Zardoz84 9y ago
If you think Age of Empires path finding was bad, try "Thandor: The invasion". The pathfinding was so bad, that sometimes, the mech units would begin to do clacket dancing. However, the game had some stuff that make it interesting (true 3d terrain for his time, and a lot unit types; air, earth, water and amphibe units). Sadly had a really bad IA.
Jakob 9y ago
Dijkstra’s algorithm is not what you would use for efficient path finding. See http://theory.stanford.edu/~amitp/GameProgramming/#pathfinding http://theory.stanford.edu/~amitp/GameProgramming/#pathfindi... for details. I think the biggest problem is collisions with other moving objects. I haven’t seen any library which solves this in a general manner for all kinds of games since they have different strategies. In Starcraft the most efficient way for a group of units to pass a bridge might not be the best one (e.g. sending fast and weak units first without any defense). Nowadays I don’t know of any bigger game with particular bad pathfinding, though.
adanto6840 9y ago
That sounds great, in theory! One thing I've found to be the case after making the switch from web stacks to gamedev is that theory is quite often a very different ballgame versus the practical application of the theory. For turn-based games, absolutely -- and I suspect that's why you rarely see pathfinding brought up as a big concern for turn-based games. They have plenty of time to re-compute paths, there's a perfect sequence for map invalidations, etc... But for RTS or simulation games, the latter being where I draw my experience from[0], it's really a different beast -- you touched on some of the reasons why, such as map invalidation & larger total scales (units, nodes, commands, etc). What happens is, you do this -- and then you fire up a build and find that the game freezes every time you need a path. Okay, let's get some concurrency going -- easy! But how are we going to handle map invalidation/sync between threads? Definitely solvable. Then you find, it's still too slow -- thread overrun! You can't do realtime pathfinding for 500 units through 100k nodes, why not? Is it the sync/concurrency locks? Meanwhile, you've spent all this time trying to get perfect paths to run fast and you could instead be working on what the gameplay needs; maybe that's pathfinding related too, perhaps some units should only be able to use paths that have 5x5 clearance while others need 10x10, etc... How do you deal with nodes that are unreachable -- do you allow the pathfinder to explore the entire terrain, only to find there aren't any paths? Sure, you can do some initial exploration first; but perhaps 'reachability' differs per unit-type, or maybe you have uni-directional traversals, etc. Or how about avoiding other units? Etc... :) Pathfinding generally isn't really that difficult to get to an MVP implementation of; but it IS hard to get something that is anywhere near "perfect", for every single case, and especially if it needs to be realtime or if your map changes. The requirements inevitably continue to add up (out of gameplay necessity, not client demand per-say), and each respective aspect of it nearly always takes an incredibly large amount of time to implement, test, debug, and ship. FWIW, our game[0] implements ~5 fairly distinct pathfinding "approaches" to deal with various situations like these (windowed, various levels of hierarchical / JPS, vanilla A*, cooperative, etc), some with more "complete-ness" than others. I can assure you that it's anything but pure theory-craft, and honestly it can sometimes be fairly difficult to reason fully reason about it without trying things. That's another awesome thing about gamedev, though also a negative as well -- sometimes you can "reason yourself to death" and it's often better to form a high-level plan and then give it a try, so you can quickly see where the holes in your approach are & and how surmountable (or not) those pitfalls may be. In any case, I think my point can be largely summed up by saying that it's likely very often a case of "easier said than done" when truly considering the entirety of the problem. One final thing to consider is that, when it comes to games, allowing a failure case (or a full-map expansion) is basically a no-go -- the last thing you want is for a player to see a stuck unit, or a frame drop, and in that way it's very much an "all or nothing" exercise. :) 0 - Co-Creator & developer of SimAirport http://store.steampowered.com/app/598330 http://store.steampowered.com/app/598330 (in Early Access & under continual active development)

morsch 9y ago

According to TFA, they're using A-star[1]. This seems to be common.[2] Am I severely underestimating the problem difficulty? Did people not even try for perfection because of how slow CPUs were? Did people just assume basic heuristics would work and not bother to check—I guess they didn't have the advantage of learning from the failures of the previous generation? I am not a game programmer but presumably: yes, yes, no. Though TFA says the original edition's A-star implementation was "outright broken". [1] https://en.wikipedia.org/wiki/A*_search_algorithm https://en.wikipedia.org/wiki/A*_search_algorithm [2] https://gamedev.stackexchange.com/questions/5013/how-does-pathfinding-in-rts-games-work https://gamedev.stackexchange.com/questions/5013/how-does-pa...

Zardoz84 9y ago

If you think Age of Empires path finding was bad, try "Thandor: The invasion". The pathfinding was so bad, that sometimes, the mech units would begin to do clacket dancing. However, the game had some stuff that make it interesting (true 3d terrain for his time, and a lot unit types; air, earth, water and amphibe units). Sadly had a really bad IA.

Jakob 9y ago

Dijkstra’s algorithm is not what you would use for efficient path finding. See http://theory.stanford.edu/~amitp/GameProgramming/#pathfinding http://theory.stanford.edu/~amitp/GameProgramming/#pathfindi... for details. I think the biggest problem is collisions with other moving objects. I haven’t seen any library which solves this in a general manner for all kinds of games since they have different strategies. In Starcraft the most efficient way for a group of units to pass a bridge might not be the best one (e.g. sending fast and weak units first without any defense). Nowadays I don’t know of any bigger game with particular bad pathfinding, though.

adanto6840 9y ago

That sounds great, in theory! One thing I've found to be the case after making the switch from web stacks to gamedev is that theory is quite often a very different ballgame versus the practical application of the theory. For turn-based games, absolutely -- and I suspect that's why you rarely see pathfinding brought up as a big concern for turn-based games. They have plenty of time to re-compute paths, there's a perfect sequence for map invalidations, etc... But for RTS or simulation games, the latter being where I draw my experience from[0], it's really a different beast -- you touched on some of the reasons why, such as map invalidation & larger total scales (units, nodes, commands, etc). What happens is, you do this -- and then you fire up a build and find that the game freezes every time you need a path. Okay, let's get some concurrency going -- easy! But how are we going to handle map invalidation/sync between threads? Definitely solvable. Then you find, it's still too slow -- thread overrun! You can't do realtime pathfinding for 500 units through 100k nodes, why not? Is it the sync/concurrency locks? Meanwhile, you've spent all this time trying to get perfect paths to run fast and you could instead be working on what the gameplay needs; maybe that's pathfinding related too, perhaps some units should only be able to use paths that have 5x5 clearance while others need 10x10, etc... How do you deal with nodes that are unreachable -- do you allow the pathfinder to explore the entire terrain, only to find there aren't any paths? Sure, you can do some initial exploration first; but perhaps 'reachability' differs per unit-type, or maybe you have uni-directional traversals, etc. Or how about avoiding other units? Etc... :) Pathfinding generally isn't really that difficult to get to an MVP implementation of; but it IS hard to get something that is anywhere near "perfect", for every single case, and especially if it needs to be realtime or if your map changes. The requirements inevitably continue to add up (out of gameplay necessity, not client demand per-say), and each respective aspect of it nearly always takes an incredibly large amount of time to implement, test, debug, and ship. FWIW, our game[0] implements ~5 fairly distinct pathfinding "approaches" to deal with various situations like these (windowed, various levels of hierarchical / JPS, vanilla A*, cooperative, etc), some with more "complete-ness" than others. I can assure you that it's anything but pure theory-craft, and honestly it can sometimes be fairly difficult to reason fully reason about it without trying things. That's another awesome thing about gamedev, though also a negative as well -- sometimes you can "reason yourself to death" and it's often better to form a high-level plan and then give it a try, so you can quickly see where the holes in your approach are & and how surmountable (or not) those pitfalls may be. In any case, I think my point can be largely summed up by saying that it's likely very often a case of "easier said than done" when truly considering the entirety of the problem. One final thing to consider is that, when it comes to games, allowing a failure case (or a full-map expansion) is basically a no-go -- the last thing you want is for a player to see a stuck unit, or a frame drop, and in that way it's very much an "all or nothing" exercise. :) 0 - Co-Creator & developer of SimAirport http://store.steampowered.com/app/598330 http://store.steampowered.com/app/598330 (in Early Access & under continual active development)