Comment by creato | Hacker News Reader

Comment by creato | Hacker News Reader

Parent Full thread

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.

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.

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

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.

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.

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.

Most of the interesting optimizations specific to the problem domain of games (e.g. JPS, Theta*) appeared after 2000.

Anyway, the path finding feature is not finished once you have a graph traversal solution. Routing large armies with formations, varying unit sizes, dynamic terrain and collision detection remains fairly challenging in practice.

Indeed. But mostly due to engineering and time crunch, not because the algorithms are hard or unknown.

That's... not a good book for pathfinding algorithms, adapted to game programming. It's one of the sacred cows of this field, but it's not really much of a resource for real work.

The whole section of pathfinding is very weak, and doesn't mention A-Star at all, nor any refinements to it that have been developed over the years.

Correct. The difference between a programmer and code monkey is that a programmer can adapt known algorithms and devise new ones. A* is not mentioned but using heuristics to speed up searches is. (Which is the core of A* - it is Dijkstra's with a heuristic guess.) The general approaches are typically much better than an explicitly memorized algorithm that may or may not work in your case.

I used the book as an example of commonly available piece of literature from 90s, not as best source.

Requiring everything to be given in any easy and digested form is actually a weakness... and it might not even save time.

Having read a few books that were explicitly game oriented, none of them tackled big problems efficiently. Either they threw out vague ideas (no better than the actual algorithm book, often worse) or they fixated on the specific game.

Websites are no better nowadays. No depth and no breadth inn most of them. Stack Overflow is the epitome of no depth.

Toy get much more mileage by reading and understanding say Knuth's books than any gaming relayed book. Despite them not even roughing the subject. Now for details, true, access to actual papers and research is very useful, but I bet few game developers have that anyway.

The trap as in most rushed development is that you will choose the wrong direction then get to live with consequences. Internet does not help with it as one cannot properly communicate a problem you can't solve, and once you do the solution is almost always known. The best you would get is a set of recommendations which is most useful if you're completely green...

Time, experience and experiment trumps slightly better sources 9/10.

Reply on news.ycombinator.com