4 ms·

I 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

by simias 9y ago

I 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.

Doxin 9y ago
The old-timey pathfinding was probably optimising for memory usage, not speed or correctness.
- AstralStorm 9y ago
  Actually memory usage is and was speed too. Now CPUs are even faster still than memory. Just like then, you cannot just load a many megabyte map of nodes and expect pathing to churn it in 120 fps. Even with good cache locality. As a matter of fact, most pathing is local or inaccurate. The few exceptions I can think of are grand strategies and certain FPS that simulate world living beyond player's reach (immersive sims).
creato 9y ago
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.
- AstralStorm 9y ago
  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.
  - w0utert 9y ago
    'Pathfinding' in the scope of an RTS means a little more than just 'pathfinding' in the scope of a graph. If you had read the article you would have seen that there is a lot of dynamics behavior going on that is essential for the gameplay, but mostly unrelated to the A* search itself. I don't think you would find many books from the 80s about pathfinding for RTS games.
    - animal531 9y ago
      Exactly. There's a huge difference between a theoretical algorithm in a book (that performs 1 search) vs having 120 real time units all trying to walk together, or even worse, through each other. In the 80's and 90's you were lucky to dig up docs from BBS releases that had math and graphics tutorials in them, it was very hard to find anything practical.
      - AstralStorm 9y ago
        120 real units. By that you mean plotting 120 paths simultaneously using a common flow algorithm used by internet routers which is more than fast enough and reasonably easy to speed up or truncate. The tricky part is on assigning nodes on a contiguous map or reducing number of nodes. (Or expanding node resolution on demand.) Of course many games of the time side stepped it by using greedy truncated pathing instead. Easy, dirty, mediocre results.
    - AstralStorm 9y ago
      Actually, it is not, other than the fact that you have a limited time budget. In the old days, it was even simpler as you did not have to take multithreading or asynchronous behaviour into consideration. (Games still often run AI and physics on hard realtime tick but it is changing.) About the only thing necessary is to stabilise pathing so that it doesn't return vastly different path on every tick and handling inter object collisions well. This may mean additionally handling swarm movement algorithms for which were already known way back in early 90s. Also in widely known books. Games like Total Annihilation handled fast movement of hundreds of units at a time with decent to good pathing and a strong enough CPU - scaling the quality of pathing automatically with available CPU power to boot. Way better than AoE and it was released at about the same time - plus it has actually smooth terrain penalty unlike AoE chunky model underneath... Three challenge was rarely algorithm but instead engineering. Time crunch was as real then as nowadays.
ygra 9y ago
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.
- taneq 9y ago
  Yep, you fix the crash bugs, and then the game breaking bugs. And then, if you're lucky, you fix ALLLLLL the other bugs.
bri3d 9y ago
I'm mostly confused why the author bothered to do this. Age1 ran on computers that were, quite literally, one to two orders of magnitude slower than the ones this remake will run on, and as far as I remember nobody complained about performance issues. So why spend time (when the author argues they were time constrained) optimizing this part of the game for speed in particular? I can totally understand the need for a rewrite given all else the author writes about the algorithm, but the focus on speed as the first-line item is kind of confusing.
munificent 9y ago
Machines and compilers have different constraints and heuristics today than back then. It may be that the old code was optimal given compilers at the time and the relative performance of memory access versus CPU, but that today's compilers and memory hierarchies have changed that.
megaman22 9y ago
He mentioned optimizing it for x64 assembly. The original ran on old 32-bit processors. There were a lot fewer registers available back then and SSE hadn't even been released. Compilers weren't as smart either twenty years ago.
- AstralStorm 9y ago
  That easily explains why they got only 4x improvement... better algorithms would give like 100x but would no longer be authentic.

by simias 9y ago

Doxin 9y ago

The old-timey pathfinding was probably optimising for memory usage, not speed or correctness.

AstralStorm 9y ago
Actually memory usage is and was speed too. Now CPUs are even faster still than memory. Just like then, you cannot just load a many megabyte map of nodes and expect pathing to churn it in 120 fps. Even with good cache locality. As a matter of fact, most pathing is local or inaccurate. The few exceptions I can think of are grand strategies and certain FPS that simulate world living beyond player's reach (immersive sims).

creato 9y ago

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.

AstralStorm 9y ago
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.
- w0utert 9y ago
  'Pathfinding' in the scope of an RTS means a little more than just 'pathfinding' in the scope of a graph. If you had read the article you would have seen that there is a lot of dynamics behavior going on that is essential for the gameplay, but mostly unrelated to the A* search itself. I don't think you would find many books from the 80s about pathfinding for RTS games.
  - animal531 9y ago
    Exactly. There's a huge difference between a theoretical algorithm in a book (that performs 1 search) vs having 120 real time units all trying to walk together, or even worse, through each other. In the 80's and 90's you were lucky to dig up docs from BBS releases that had math and graphics tutorials in them, it was very hard to find anything practical.
    - AstralStorm 9y ago
      120 real units. By that you mean plotting 120 paths simultaneously using a common flow algorithm used by internet routers which is more than fast enough and reasonably easy to speed up or truncate. The tricky part is on assigning nodes on a contiguous map or reducing number of nodes. (Or expanding node resolution on demand.) Of course many games of the time side stepped it by using greedy truncated pathing instead. Easy, dirty, mediocre results.
  - AstralStorm 9y ago
    Actually, it is not, other than the fact that you have a limited time budget. In the old days, it was even simpler as you did not have to take multithreading or asynchronous behaviour into consideration. (Games still often run AI and physics on hard realtime tick but it is changing.) About the only thing necessary is to stabilise pathing so that it doesn't return vastly different path on every tick and handling inter object collisions well. This may mean additionally handling swarm movement algorithms for which were already known way back in early 90s. Also in widely known books. Games like Total Annihilation handled fast movement of hundreds of units at a time with decent to good pathing and a strong enough CPU - scaling the quality of pathing automatically with available CPU power to boot. Way better than AoE and it was released at about the same time - plus it has actually smooth terrain penalty unlike AoE chunky model underneath... Three challenge was rarely algorithm but instead engineering. Time crunch was as real then as nowadays.

ygra 9y ago

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.

taneq 9y ago
Yep, you fix the crash bugs, and then the game breaking bugs. And then, if you're lucky, you fix ALLLLLL the other bugs.

bri3d 9y ago

I'm mostly confused why the author bothered to do this. Age1 ran on computers that were, quite literally, one to two orders of magnitude slower than the ones this remake will run on, and as far as I remember nobody complained about performance issues. So why spend time (when the author argues they were time constrained) optimizing this part of the game for speed in particular? I can totally understand the need for a rewrite given all else the author writes about the algorithm, but the focus on speed as the first-line item is kind of confusing.

munificent 9y ago

Machines and compilers have different constraints and heuristics today than back then. It may be that the old code was optimal given compilers at the time and the relative performance of memory access versus CPU, but that today's compilers and memory hierarchies have changed that.

megaman22 9y ago

He mentioned optimizing it for x64 assembly. The original ran on old 32-bit processors. There were a lot fewer registers available back then and SSE hadn't even been released. Compilers weren't as smart either twenty years ago.

AstralStorm 9y ago
That easily explains why they got only 4x improvement... better algorithms would give like 100x but would no longer be authentic.