3 ms·

'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

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

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.