Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Age of Empires Definitive Edition's pathing and movement

richg42.blogspot.com

Post reply on HN
Print view View original

61–70 of 94 posts

Re: Age of Empires Definitive Edition's pathing and movement

#61

Post by megaman22 »

AstralStorm wrote: post #16
creato wrote: post #12

Earlier quoted context omitted.

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.

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.

Re: Age of Empires Definitive Edition's pathing and movement

#62

Post by hart_russell »

baldfat wrote: post #53
faitswulff wrote: post #7

The fact that this post seems to be engendered by a comment on a forum ("The pathfinding in the game is terrible.") reminds me of 'Designing Video Games is Hard Work, But the Millions of Angry Players Make It All Worthwhile' http://thehardtimes.net/harddrive/designing-video-games-hard...

I use to be a high level Age of Kings player (Even got an invite to the first World Cyber Olympics in NYC). The pathing was ALWAYS horrible but the PATCHING by the developer was even worse. There were times when the community just banned certain things because they were just broken (Teuten's Town halls were only costing wood but did more damage than high costing resource units and buildings). As a high level player a…

Sounds a lot like brood war. If you can micro your units well you have a significant advantage.

Re: Age of Empires Definitive Edition's pathing and movement

#63

Post by preben »

baldfat wrote: post #53
faitswulff wrote: post #7

The fact that this post seems to be engendered by a comment on a forum ("The pathfinding in the game is terrible.") reminds me of 'Designing Video Games is Hard Work, But the Millions of Angry Players Make It All Worthwhile' http://thehardtimes.net/harddrive/designing-video-games-hard...

I use to be a high level Age of Kings player (Even got an invite to the first World Cyber Olympics in NYC). The pathing was ALWAYS horrible but the PATCHING by the developer was even worse. There were times when the community just banned certain things because they were just broken (Teuten's Town halls were only costing wood but did more damage than high costing resource units and buildings). As a high level player a…

Brood War does this all the time. The pathing is notoriously bad[1] and nothing has been done to fix it because it's not a problem. It allows players extinguish themselves by working with the weird behaviors.

[1] Day[9] on Pathing in BW https://youtu.be/rWvoMrYCQBU?t=17m50s

Re: Age of Empires Definitive Edition's pathing and movement

#64

Post by megaman22 »

simias wrote: post #4

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.

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.

Re: Age of Empires Definitive Edition's pathing and movement

#65

Post by AstralStorm »

quadcore wrote: post #54

Cool. I've coded a RTS myself, and I might be able to add some information. DE's pather gives up if after many thousands of iterations it can't make forward progress towards the goal, to avoid spending CPU cycles on hopeless pathing unnecessarily. (It's more complex than this, but that's the gist of it.) The right way to do that is to make a unit pop the action on top of its stack if it cant perform it. So if a unit…

Pretty decent, alternative approach is to form virtual "formations" when units near each other and move as blocs. This removes multiple problems like units bumping into each other on the way and is kind of the behaviour a strategy player would expect. On obstruction, make neighbours slow down and indeed use obstruction avoidance (local pathfinding) to "squish" the formations. Return to these later when possible.

Marching squares indeed produces a similar result of "squishing". However as it is ran per unit you will have more collisions.

Re: Age of Empires Definitive Edition's pathing and movement

#66

Post by AstralStorm »

crispweed wrote: post #34
rcfox wrote: post #25

Earlier quoted context omitted.

I think it's more popular nowadays to do a search on an adjacency graph of polygons and then smooth the path with something like the funnel algorithm. http://digestingduck.blogspot.ca/2010/03/simple-stupid-funne...

Yes, a lot of people are doing this, and it's not a bad approach. There's another approach you can take for continuous space pathfinding, however, which is to use visibility graphs. See http://www.cs.kent.edu/~dragan/ST-Spring2016/visibility%20gr... , for example, for some explanation and diagrams. This is the approach I used in PathEngine (www.pathengine.com). A lot of people are put off by the possibility for graph…

And I suppose when encountering them (since they were culled not truly removed) switching to a backup collision avoidance mechanism or replanning?

Re: Age of Empires Definitive Edition's pathing and movement

#67

Post by AstralStorm »

megaman22 wrote: post #61
AstralStorm wrote: post #16

Earlier quoted context omitted.

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.

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.

Re: Age of Empires Definitive Edition's pathing and movement

#68

Post by crispweed »

AstralStorm wrote: post #66
crispweed wrote: post #34

Earlier quoted context omitted.

Yes, a lot of people are doing this, and it's not a bad approach. There's another approach you can take for continuous space pathfinding, however, which is to use visibility graphs. See http://www.cs.kent.edu/~dragan/ST-Spring2016/visibility%20gr... , for example, for some explanation and diagrams. This is the approach I used in PathEngine (www.pathengine.com). A lot of people are put off by the possibility for graph…

And I suppose when encountering them (since they were culled not truly removed) switching to a backup collision avoidance mechanism or replanning?

The trick is to detect obstacles that are likely to have minimal affect on the global result of pathfinding search, e.g. convex obstacles that are in the middle of open spaces, or, more specifically in the case of PathEngine, obstacles that don't combine with other nearby obstacles to form larger blockages.

After the initial graph search, the path is modified to avoid these obstacles locally (by pushing the path around the obstacles, essentially), before it's returned from the pathfinding query.

So the way it's set up in PathEngine this optimisation is largely hidden from application code (code that calls into the pathfinding API).

Leaving this to be handled later on, by agent local obstacle avoidance, could also work..

Re: Age of Empires Definitive Edition's pathing and movement

#69

Post by AstralStorm »

megaman22 wrote: post #64
simias wrote: post #4

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.

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.

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

Re: Age of Empires Definitive Edition's pathing and movement

#70

Post by AstralStorm »

z3t4 wrote: post #13

A 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).

And this is why Age of Empires never got its pathing or engine rewritten in later versions... oh wait.
Post reply on HN