I hate that it’s only available on windows 10. Bad move Microsoft!
Age of Empires Definitive Edition's pathing and movement
11–20 of 94 posts
Re: Age of Empires Definitive Edition's pathing and movement
#12I would've guessed that bad pathfinding in these old games was caused by very aggressive optimizations to improve performance but then the author starts off by saying: >DE's pathing system's findPath() function was speeded up by approx 3-4x faster vs. Age1's So the old code was just that bad? It's a bit odd, you'd expect such a critical piece of code in an RTS to be reasonably well written and optimized.
Before saying the old code was just bad, put yourself in the shoes of an AoE1 developer.
Google and stack overflow don't exist. If there is a good A* implementation to start from, it's still going to be hard to find. At the time AoE1 was developed, it would require considerably more skill and effort to develop a high quality path finding engine than it would today.
Contemporary games also had bad pathfinding. Today, we know what is possible with good pathfinding. Would you have known at the time? Just knowing what is possible is very valuable information. My guess is that if an AoE1 engineer could have time traveled for just a few minutes to observe modern pathfinding, they would be able to very quickly make progress on improving to something closer to what we expect today.
The old pathfinding might have been bad, but I wouldn't assume that it would have been easy to make it that much better at the time. We have a lot of knowledge now that is easy to take for granted.
Re: Age of Empires Definitive Edition's pathing and movement
#13A total rewrite is almost never worth it unless the thing you are rewriting is not under development in-production. eg. you don't have to fix bugs in the old version during the rewrite. As you will have a very clear specification and domain experience (if you also worked on the original).
Re: Age of Empires Definitive Edition's pathing and movement
#14I would've guessed that bad pathfinding in these old games was caused by very aggressive optimizations to improve performance but then the author starts off by saying: >DE's pathing system's findPath() function was speeded up by approx 3-4x faster vs. Age1's So the old code was just that bad? It's a bit odd, you'd expect such a critical piece of code in an RTS to be reasonably well written and optimized.
To add to the other replies: Game development happens under constant tight deadlines and doing things perfectly is almost never done because there's no time for it. Furthermore, starting with a pathfinding routine that returns the optimal path and then optimizing it so far that it can run under real-time constraints (you don't want a two-second pause when sending units around) is prone to break things. And figuring out why pathfinding results in bad paths in some cases can take quite a while (had to do so in a product that calculated cycling and hiking routes on a map). So I guess as long as the result is good enough (and the most common routes will be short anyway) there's no need to invest more time and instead focus on other things that are currently unshippably broken.
Re: Age of Empires Definitive Edition's pathing and movement
#15Something 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
Re: Age of Empires Definitive Edition's pathing and movement
#16I would've guessed that bad pathfinding in these old games was caused by very aggressive optimizations to improve performance but then the author starts off by saying: >DE's pathing system's findPath() function was speeded up by approx 3-4x faster vs. Age1's So the old code was just that bad? It's a bit odd, you'd expect such a critical piece of code in an RTS to be reasonably well written and optimized.
Before saying the old code was just bad, put yourself in the shoes of an AoE1 developer. Google and stack overflow don't exist. If there is a good A* implementation to start from, it's still going to be hard to find. At the time AoE1 was developed, it would require considerably more skill and effort to develop a high quality path finding engine than it would today. Contemporary games also had bad pathfinding. Today,…
Are you for real? The good path finding algorithms were devised in 80s and are described in detail in chestnuts like Cormen, Leiserson, Rivest, Stein Introduction to Algorithms. Released in 1990.
I can understand skimping $40 on a book... but not the argument that it was hard to find those things.
Re: Age of Empires Definitive Edition's pathing and movement
#17>DE's pathing system's findPath() function was speeded up by approx 3-4x faster vs. Age1's How would that make any impact at all given that the game ran just fine on 1997 hardware?
In addition to the other replies, depending on how the game is written, it can also help with battery life if the speedup allows the CPU to go to sleep (or lower it's frequency) more often.
Re: Age of Empires Definitive Edition's pathing and movement
#18Something 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 ch…
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
[2] https://gamedev.stackexchange.com/questions/5013/how-does-pa...
Re: Age of Empires Definitive Edition's pathing and movement
#19I would've guessed that bad pathfinding in these old games was caused by very aggressive optimizations to improve performance but then the author starts off by saying: >DE's pathing system's findPath() function was speeded up by approx 3-4x faster vs. Age1's So the old code was just that bad? It's a bit odd, you'd expect such a critical piece of code in an RTS to be reasonably well written and optimized.
To add to the other replies: Game development happens under constant tight deadlines and doing things perfectly is almost never done because there's no time for it. Furthermore, starting with a pathfinding routine that returns the optimal path and then optimizing it so far that it can run under real-time constraints (you don't want a two-second pause when sending units around) is prone to break things. And figuring o…
Yep, you fix the crash bugs, and then the game breaking bugs. And then, if you're lucky, you fix ALLLLLL the other bugs.
Re: Age of Empires Definitive Edition's pathing and movement
#20Something 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 ch…
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.