Age of Empires Definitive Edition's pathing and movement(richg42.blogspot.com)
richg42.blogspot.com
Age of Empires Definitive Edition's pathing and movement
https://richg42.blogspot.com/2018/02/on-age-des-pathingmovement.html
93 comments
A corollary to this is that the more a game looks and feels like a fallible piece of software, the more players will react to it like a piece of software, ushering you onto the "infinite demands" feature treadmill in an attempt to make the game feel more complete.
If it all feels adequately justified by the scenario and core premises, then there's an actual resolution. They shut up and play.
If it all feels adequately justified by the scenario and core premises, then there's an actual resolution. They shut up and play.
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 broken pathing allowed me to micro my troops and get an advantage over other players. Most players play with the speed of a 4X and there were few of us who played by trying to make 150+ commands a minute.
So this horrible pathing was seen as an advantage by faster players.
Scale APM Description ~50 Casual player ~75 Experienced player ~150 Proficient player >200 Proficient player with superfluous actions
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 broken pathing allowed me to micro my troops and get an advantage over other players. Most players play with the speed of a 4X and there were few of us who played by trying to make 150+ commands a minute.
So this horrible pathing was seen as an advantage by faster players.
Scale APM Description ~50 Casual player ~75 Experienced player ~150 Proficient player >200 Proficient player with superfluous actions
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
[1] Day[9] on Pathing in BW https://youtu.be/rWvoMrYCQBU?t=17m50s
As a casual gamer I find this aggravating. Why should the NPCs be left dumber and less human than they could be? It breaks immersion and makes the game harder for novices to enjoy.
Because it's hard to fit a lot of intelligence into the game, when it has to run on a 90MHz Pentium I with 16MB of RAM available.
I thought it was pretty good, and more than enjoyable, when it came out 19 years ago.
I thought it was pretty good, and more than enjoyable, when it came out 19 years ago.
As did I back in the day. But now I'm older with less time to micromanage pathfinding. And our devices are much faster than when many of these games launched
Well, in general, the rest of the answer to your question is that newer games tend to have better pathfinding, but adding better pathfinding to older games will make them essentially different games. Casual players might like it; serious players would throw a shit-fit. It's one of those "we can, but should we?" questions; everyone's going to have a different opinion.
Now...I don't see why they couldn't have included it as a toggle-able option. I know that I've considered trying to build updated versions of old games, and when thinking about how to do it, that seemed like the best choice.
Now...I don't see why they couldn't have included it as a toggle-able option. I know that I've considered trying to build updated versions of old games, and when thinking about how to do it, that seemed like the best choice.
When I heard these arguments and no rush or no attacking 20 minutes it would get under my skins. To me the T in RTS was Time and many people wanted to remove Time out of the game.
This is precisely why RTS as a genre pretty much died.
This is precisely why RTS as a genre pretty much died.
Brood War hasn't had to ban a whole unit or building, though.
EDIT: Now that I think about it, the narrow ramps that you see in the campaign are banned for competitive maps because units like Dragoon will simply never go up or down one unless babysat the whole way, one by one, clicking a few pixels further with each move command so that the Dragoon doesn't go backward. Brood War is full of unbalanced and unworkable mechanics and was fixed not by Blizzard patches, but by literally professional pro map makers.
EDIT: Now that I think about it, the narrow ramps that you see in the campaign are banned for competitive maps because units like Dragoon will simply never go up or down one unless babysat the whole way, one by one, clicking a few pixels further with each move command so that the Dragoon doesn't go backward. Brood War is full of unbalanced and unworkable mechanics and was fixed not by Blizzard patches, but by literally professional pro map makers.
Sounds a lot like brood war. If you can micro your units well you have a significant advantage.
It's not really the same sort of thing. In this case, the programmers are dealing with the tricky problem of trying to fix the pathfinding somewhat while leaving the experience of the original game 'authentic'. The pathfinding is terrible, the pathfinding was terrible 21 years ago when the game came out. These forum posts are not surprising and unexpected whining, just a reminder new audiences are finding bad pathfinding from 21 years ago still bad.
In news from Spain, Generallissimo Francisco Franco is still dead.
In news from Spain, Generallissimo Francisco Franco is still dead.
Maybe the solution is a classic/pro mode and a novice/Renaissance mode.
splitting the player base is almost always a bad idea
If the alternative is completely alienating a large pool of potential customers then I don't see the disadvantage
Having played the game for a bit, one of the charming things is that the path finding still feels a lot like the original. It's certainly better. As mentioned, the new version fixes a lot of villager collision issues. They preserved the behaviors that made AoE what it was and fixed some of the bad aspects of it.
For people interested in path finding, there was some fascinating research done in the 90s:
http://faculty.nps.edu/ncrowe/snell2.htm
They used Snell's law to design pathfinding directly on region polygons, based on ray refraction. This is in contrast to the more common type of "grid searches" (A* being the most prominent example) which superimpose a grid and then do a wavefront graph search on that.
I remember implementing this "refraction search" in the 90s as a C++ PoC. It was a fascinating and elegant concept, but a complete bitch to get right due to its "continuous" nature (rays just barely hitting polygon vertices, parallel edges, numerical instability).
http://faculty.nps.edu/ncrowe/snell2.htm
They used Snell's law to design pathfinding directly on region polygons, based on ray refraction. This is in contrast to the more common type of "grid searches" (A* being the most prominent example) which superimpose a grid and then do a wavefront graph search on that.
I remember implementing this "refraction search" in the 90s as a C++ PoC. It was a fascinating and elegant concept, but a complete bitch to get right due to its "continuous" nature (rays just barely hitting polygon vertices, parallel edges, numerical instability).
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 explosion in situations where there are a lot of obstacles in an open environment, but PathEngine works around this quite effectively by detecting these kinds of obstacles and pulling them out of the visibility graph (and pathfinding search).
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 explosion in situations where there are a lot of obstacles in an open environment, but PathEngine works around this quite effectively by detecting these kinds of obstacles and pulling them out of the visibility graph (and pathfinding search).
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..
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..
Talk about a thankless job! That's an extensive list of bugs and working on someone else's (very old) playground is incredibly difficult.
I imagine its more of a passion project. If I had free time, I would love to delve into the internals of the game that I played so many times as a kid.
Side note: Age of Empires 2 was the first computer game that got me truly hooked on to computers. I was never interested in the shoot em ups, but a strategy game, with such gorgeous graphics (for the time) and compelling semi-historical storyline... it was enchanting!
Side note: Age of Empires 2 was the first computer game that got me truly hooked on to computers. I was never interested in the shoot em ups, but a strategy game, with such gorgeous graphics (for the time) and compelling semi-historical storyline... it was enchanting!
> gorgeous graphics (for the time)
Gorgeous and captivating 2D work, just like booting up the game Pharaoh after all these years. Just needed a user-made patch to allow higher resolution support.
>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?
How would that make any impact at all given that the game ran just fine on 1997 hardware?
In addition to the higher unit count there are a few bullet points in the article that indicate where saved/additional time is spent. From the sound of it, most importantly: "The DE pather was modified to have a much higher max iteration count than Age1's, so longer and more complex routes can be found."
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.
They also increased the iteration time to search for more complex paths, so I’m sure this helps with that.
IIRC the max unit cap is much higher.
The fact that you don't need to optimize something doesn't mean you shouldn't.
It does, actually. At least don't do it on my dime. Obviously learning is another ballgame.
At the least, it implies that you ought to carefully consider whether you should. Optimized code often makes trade-offs in complexity, flexibility, etc, not to mention the extra cost in development time.
With those costs, there should be a compelling benefit that you get out of it. Otherwise, it's not worthwhile.
With those costs, there should be a compelling benefit that you get out of it. Otherwise, it's not worthwhile.
Avoiding premature optimization is one of the most important best practices of modern software development.
This isn't premature... the algorithm and performance are understood. That said, I agree that it's not always the best use of time.
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.
>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.
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.
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.
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.
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.
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.
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.
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.
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.
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.
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.
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.
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.
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.
Yep, you fix the crash bugs, and then the game breaking bugs. And then, if you're lucky, you fix ALLLLLL the other bugs.
The old-timey pathfinding was probably optimising for memory usage, not speed or correctness.
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).
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).
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.
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.
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.
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.
I hate that it’s only available on windows 10. Bad move Microsoft!
Maybe 0 A.D. can fill that in for you.
It's sort of in between AoE 1 and 2, with a bit of Empire Earth mixed in as well. It was the go-to for people looking for a more modern AoE, prior to AoE:DE being released, and many people still consider it to be better than AoE:DE.
It's also open-source and free.
https://play0ad.com/
It's sort of in between AoE 1 and 2, with a bit of Empire Earth mixed in as well. It was the go-to for people looking for a more modern AoE, prior to AoE:DE being released, and many people still consider it to be better than AoE:DE.
It's also open-source and free.
https://play0ad.com/
Windows 8 is 5 years old.
Windows 7 is 8 years old.
Move on.
Move on.
And? Age isn't a good argument on its own. If Microsoft committed to providing security updates for Windows 7, I wouldn't see any reason to move off of it. Newer doesn't mean better, in this case.
It literally does if you use a SSD.
That's an argument on speed, not age. My argument on the OSes is that Windows 7 has more desirable functionality for me than Windows 8, 8.1, or 10 do. Despite being older, it's a better system; it behaves more in the way that I want an OS to behave.
Genuinely curious: what other platforms would you like to see this on?
I use windows 7, I refuse to use windows 10 because of the clear privacy issues in it. So I would’ve liked if it worked on windows 7.
Why, as a player, would there be platforms that he'd object to this being available on?
Windows 7, MacOS, or Linux, maybe. Anything that doesn't require access to the Windows Store.
I've got Windows 10 on my machine at work, and on my little netbook-style laptop, but just Windows 7 and Linux on the closest things to "gaming machines" that I've got.
I've got Windows 10 on my machine at work, and on my little netbook-style laptop, but just Windows 7 and Linux on the closest things to "gaming machines" that I've got.
I just did some teaching of A* on my stream on Tuesday night in golang, tonight we make it fast by implementing a proper priority queue from scratch.
https://www.twitch.tv/videos/233560937
Much simpler case since it is on a grid and turn based!
https://www.twitch.tv/videos/233560937
Much simpler case since it is on a grid and turn based!
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.
> Age1's pather's A* implementation was outright broken (the open list management was flawed, so the cheapest node wasn't always expanded upon during each iteration)
What is left of A* if even that doesn't work?!?
What is left of A* if even that doesn't work?!?
maybe it picked the cheapest node quite often. you might still get 85%-95% optimal paths - roughly heading the right way with occasional strange sidesteps and zigzags in the route
if it was completely broken it probably wouldn't have shipped that way, so the defect meant it was probably only somewhat broken and the end result was workable.
if it was completely broken it probably wouldn't have shipped that way, so the defect meant it was probably only somewhat broken and the end result was workable.
The easiest way to break A* is to use a non admissible (overestimating) heuristic. This will usually still produce reasonable paths but not optimal.
What they had was even more of a bug where some nodes were skipped from expansion.
What they had was even more of a bug where some nodes were skipped from expansion.
Just pre-compute everything. Put your vector fields in textures at map design time and be done with it. No point in overthinking this once its a simple lookup per frame.
The real fun is designing the agent's AI: exploration, avoidance, engagement ;)
Crowd Pathfinding And Steering Using Flow Field Tiles
http://www.gameaipro.com/GameAIPro/GameAIPro_Chapter23_Crowd...
Flow Field Pathfinding Tutorial
http://leifnode.com/2013/12/flow-field-pathfinding/
The real fun is designing the agent's AI: exploration, avoidance, engagement ;)
Crowd Pathfinding And Steering Using Flow Field Tiles
http://www.gameaipro.com/GameAIPro/GameAIPro_Chapter23_Crowd...
Flow Field Pathfinding Tutorial
http://leifnode.com/2013/12/flow-field-pathfinding/
> Put your vector fields in textures at map design time and be done with it.
I think you're forgetting there is no map design time in Age of Empires since the maps are RNG. Also, walls, structures, and destroyed forests are critical to gameplay, so it has to be an extremely dynamic process.
There are obviously ways to improve the pathfinding, https://github.com/SFTtech/openage has many plans, but your dismissals are starting from wrong assumptions.
I think you're forgetting there is no map design time in Age of Empires since the maps are RNG. Also, walls, structures, and destroyed forests are critical to gameplay, so it has to be an extremely dynamic process.
There are obviously ways to improve the pathfinding, https://github.com/SFTtech/openage has many plans, but your dismissals are starting from wrong assumptions.
Don't be so dismissive.
The point wasn't solving it perfectly, but to mimic the old behavior while avoiding certain bugs/things that made it less enjoyable.
And for AoE you cannot precompute everything. Things you have to tackle:
- Walls being built or torn down
- Trees being chopped down, gold being mined
- Units moving as a single group, not bumping into each other, not creating a dead lock when entering a narrow passage
- Units of various sizes (ram vs. villager)
And for AoE you cannot precompute everything. Things you have to tackle:
- Walls being built or torn down
- Trees being chopped down, gold being mined
- Units moving as a single group, not bumping into each other, not creating a dead lock when entering a narrow passage
- Units of various sizes (ram vs. villager)
> Put your vector fields in textures at map design time
This would not have been a great solution on the original AoE's 16MB target memory.
This would not have been a great solution on the original AoE's 16MB target memory.
I have invented and implemented very similar idea, and published an article about it along with source code, many years before that book and that article you’ve linked.
http://const.me/articles/robocalypse-pathfinding/
http://const.me/articles/robocalypse-pathfinding/
Sounds like many player complain about, that the game is too much like AoE1 :D
So far I played only one match but that felt pretty much like the AoE1.
So far I played only one match but that felt pretty much like the AoE1.
As someone who was a big RTS fan back in the 90s, the level of enthusiasm for AoE seems kind of odd to me. I always thought of it as an also-ran. I remember it coming out kind of late, only a little before Blizzard released StarCraft and basically killed the genre.
It did have a fairly unique setting among RTSes at least. So I could see the niche among historical enthusiasts who also wanted to play RTS. That wasn't me though.
It did have a fairly unique setting among RTSes at least. So I could see the niche among historical enthusiasts who also wanted to play RTS. That wasn't me though.
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 cant move somewhere, it just removes the action that says it should move there. Now, the trick is: a user click pushes an action which isnt the actual move but which generate actions with actual move. It allows the unit to not give up when it cant perform an action on a user order but make it retry later, say in half a second.
I implemented the A early exploration optimization*
I did something similar. The way I did that was that a unit of the group would perform an A* but on a grid that has say 64x less cells. The path would be marked and the following, per unit, precise A* would not push into the openlist a cell that's not in the marked grid. Subsequently, if another unit of the group starts a precise A* but is not itself on a marked cell, it performs again a big cell A* marking (union-ed with the previous one). Note that when you select units and perform actions with them, 1) they will have the same actions by definition and 2) they will group if you move them, which 3) makes that algorithm quickly efficient in practice.
The only requirement is a map of the walls at the size of the "big grid". Could be problematic I guess in some cases. Not that it doesn't take into account dynamic walls which is ok (units and such).
For short range paths, straight line paths are preferred vs. the tile path returned by findPath() if the straight line path is safe to traverse
I understand the constraint of this new Age of Empire. Still it's a good introduction for the next topic. I dont know what the guys from blizzard used in SC2 but here is what I did to improve the grid system.
Essentially it all goes down to 2 constraints: 1) you dont want a non-idle unit to be ever blocked by friendly idle units and 2) you want the attacking units to block any unit - because you dont want an attacking unit to move because eh, it's making damage right now. The difficulty is that (1) seems incompatible with (2) at first, when using A* (on a grid or anything else). (1) makes multiple units to be on one node, (2) and more generally combat, make you dramatically want a node to have only one unit for obvious reasons: you want a unit to be able to fire immediately if at order range and to block the other units.
The way I solved that is by using marching squares. All units moves freely on the map, at the "pixel scale", the floating point scale - though it's all integers because the network algorithm, the lockstep, needs integer. Anyway, so you have some fix point math which divide a cell into say, 1024 integer-units.
When performing a pathfinding, a marching square mesh is first built (environment can be precomputed, attacking units are dynamic walls I recall). But the trick and the cool thing is that, when building that marching square mesh, you can actually and easily make a graph of it, which includes a lot of the original cells nodes. Now that you have a graph, you can do an A* and (1) and (2) are all solved. It's quite super simple to implement and as fast as the grid basically. There is also an added benefit: it's easy to make units go straight all the time because the marching squares will gives you the vertex that are reflexes and units can jump from reflexes right away.
The magic moment is that when you select a group of unit and make it attack a single target, the units will form a circle in a very elegant way. Here: https://gfycat.com/TediousThoseKitty
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 cant move somewhere, it just removes the action that says it should move there. Now, the trick is: a user click pushes an action which isnt the actual move but which generate actions with actual move. It allows the unit to not give up when it cant perform an action on a user order but make it retry later, say in half a second.
I implemented the A early exploration optimization*
I did something similar. The way I did that was that a unit of the group would perform an A* but on a grid that has say 64x less cells. The path would be marked and the following, per unit, precise A* would not push into the openlist a cell that's not in the marked grid. Subsequently, if another unit of the group starts a precise A* but is not itself on a marked cell, it performs again a big cell A* marking (union-ed with the previous one). Note that when you select units and perform actions with them, 1) they will have the same actions by definition and 2) they will group if you move them, which 3) makes that algorithm quickly efficient in practice.
The only requirement is a map of the walls at the size of the "big grid". Could be problematic I guess in some cases. Not that it doesn't take into account dynamic walls which is ok (units and such).
For short range paths, straight line paths are preferred vs. the tile path returned by findPath() if the straight line path is safe to traverse
I understand the constraint of this new Age of Empire. Still it's a good introduction for the next topic. I dont know what the guys from blizzard used in SC2 but here is what I did to improve the grid system.
Essentially it all goes down to 2 constraints: 1) you dont want a non-idle unit to be ever blocked by friendly idle units and 2) you want the attacking units to block any unit - because you dont want an attacking unit to move because eh, it's making damage right now. The difficulty is that (1) seems incompatible with (2) at first, when using A* (on a grid or anything else). (1) makes multiple units to be on one node, (2) and more generally combat, make you dramatically want a node to have only one unit for obvious reasons: you want a unit to be able to fire immediately if at order range and to block the other units.
The way I solved that is by using marching squares. All units moves freely on the map, at the "pixel scale", the floating point scale - though it's all integers because the network algorithm, the lockstep, needs integer. Anyway, so you have some fix point math which divide a cell into say, 1024 integer-units.
When performing a pathfinding, a marching square mesh is first built (environment can be precomputed, attacking units are dynamic walls I recall). But the trick and the cool thing is that, when building that marching square mesh, you can actually and easily make a graph of it, which includes a lot of the original cells nodes. Now that you have a graph, you can do an A* and (1) and (2) are all solved. It's quite super simple to implement and as fast as the grid basically. There is also an added benefit: it's easy to make units go straight all the time because the marching squares will gives you the vertex that are reflexes and units can jump from reflexes right away.
The magic moment is that when you select a group of unit and make it attack a single target, the units will form a circle in a very elegant way. Here: https://gfycat.com/TediousThoseKitty
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.
Marching squares indeed produces a similar result of "squishing". However as it is ran per unit you will have more collisions.
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.
Yes definitely. That is orthogonal to the main pathfinder. Moving units doesnt count as "walls" and so they can just push each other using a physic/collision engine and move all together like one body as well using that engine which is a sort of "local pathfinder" in some ways (it can be tweak so that units tend to avoid each other and all).
Yes definitely. That is orthogonal to the main pathfinder. Moving units doesnt count as "walls" and so they can just push each other using a physic/collision engine and move all together like one body as well using that engine which is a sort of "local pathfinder" in some ways (it can be tweak so that units tend to avoid each other and all).
Something 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
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
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...
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...
'Perfect pathfinding' sucks with swarms. The first unit gets to the choke point; the rest about-face and start marching off the long way around the forest (because that's now the shortest path with the primary path blocked). Happened all the time in Warcraft I, and was astonishingly annoying.
It seems like a harder problem than that as well - you might want some of the units in the back of the swarm to go the long way because they'd wait a long time at the choke.
But maybe you don't want to do that - those units in the back are squishy and need to stick with the units at the front of the choke.
But maybe that's ok - the alternative path isn't too far away and it's not a risky move to make.
Maybe that's too complicated. Probably best to make the swarm operate as if other moving units don't exist (to make pathing predictable) and let the player micromanage via waypoints/grouping.
But maybe you don't want to do that - those units in the back are squishy and need to stick with the units at the front of the choke.
But maybe that's ok - the alternative path isn't too far away and it's not a risky move to make.
Maybe that's too complicated. Probably best to make the swarm operate as if other moving units don't exist (to make pathing predictable) and let the player micromanage via waypoints/grouping.
Typically in RTS it is better to keep formation. If the user spots that units are choking they will order them elsewhere.
The moving units are often easily handled via local avoidance as needed.
The moving units are often easily handled via local avoidance as needed.
Yes, pathfinding is different than path following. That is, finding an optimal path is one problem, and having units follow that path in a dynamic world while reacting accordingly is something else entirely.
Flow algorithms tend to handle this case (and other perfect cases too) more reasonably as they see a choke as a path with low carrying capacity and avoid it ahead of time. (If you're smart and the required carrying capacity is related to size of unit ball.)
The trouble is how to dynamically adjust weights. That is path following and reaction part which is quite outside the purview of path finding algorithms other than that they have to work in an online manner.
The trouble is how to dynamically adjust weights. That is path following and reaction part which is quite outside the purview of path finding algorithms other than that they have to work in an online manner.
Dijkstra’s algorithm is not what you would use for efficient path finding. See http://theory.stanford.edu/~amitp/GameProgramming/#pathfindi... for details.
I think the biggest problem is collisions with other moving objects. I haven’t seen any library which solves this in a general manner for all kinds of games since they have different strategies. In Starcraft the most efficient way for a group of units to pass a bridge might not be the best one (e.g. sending fast and weak units first without any defense).
Nowadays I don’t know of any bigger game with particular bad pathfinding, though.
I think the biggest problem is collisions with other moving objects. I haven’t seen any library which solves this in a general manner for all kinds of games since they have different strategies. In Starcraft the most efficient way for a group of units to pass a bridge might not be the best one (e.g. sending fast and weak units first without any defense).
Nowadays I don’t know of any bigger game with particular bad pathfinding, though.
That sounds great, in theory! One thing I've found to be the case after making the switch from web stacks to gamedev is that theory is quite often a very different ballgame versus the practical application of the theory.
For turn-based games, absolutely -- and I suspect that's why you rarely see pathfinding brought up as a big concern for turn-based games. They have plenty of time to re-compute paths, there's a perfect sequence for map invalidations, etc... But for RTS or simulation games, the latter being where I draw my experience from[0], it's really a different beast -- you touched on some of the reasons why, such as map invalidation & larger total scales (units, nodes, commands, etc).
What happens is, you do this -- and then you fire up a build and find that the game freezes every time you need a path. Okay, let's get some concurrency going -- easy! But how are we going to handle map invalidation/sync between threads? Definitely solvable. Then you find, it's still too slow -- thread overrun! You can't do realtime pathfinding for 500 units through 100k nodes, why not? Is it the sync/concurrency locks?
Meanwhile, you've spent all this time trying to get perfect paths to run fast and you could instead be working on what the gameplay needs; maybe that's pathfinding related too, perhaps some units should only be able to use paths that have 5x5 clearance while others need 10x10, etc... How do you deal with nodes that are unreachable -- do you allow the pathfinder to explore the entire terrain, only to find there aren't any paths? Sure, you can do some initial exploration first; but perhaps 'reachability' differs per unit-type, or maybe you have uni-directional traversals, etc. Or how about avoiding other units? Etc... :)
Pathfinding generally isn't really that difficult to get to an MVP implementation of; but it IS hard to get something that is anywhere near "perfect", for every single case, and especially if it needs to be realtime or if your map changes.
The requirements inevitably continue to add up (out of gameplay necessity, not client demand per-say), and each respective aspect of it nearly always takes an incredibly large amount of time to implement, test, debug, and ship.
FWIW, our game[0] implements ~5 fairly distinct pathfinding "approaches" to deal with various situations like these (windowed, various levels of hierarchical / JPS, vanilla A*, cooperative, etc), some with more "complete-ness" than others. I can assure you that it's anything but pure theory-craft, and honestly it can sometimes be fairly difficult to reason fully reason about it without trying things. That's another awesome thing about gamedev, though also a negative as well -- sometimes you can "reason yourself to death" and it's often better to form a high-level plan and then give it a try, so you can quickly see where the holes in your approach are & and how surmountable (or not) those pitfalls may be.
In any case, I think my point can be largely summed up by saying that it's likely very often a case of "easier said than done" when truly considering the entirety of the problem. One final thing to consider is that, when it comes to games, allowing a failure case (or a full-map expansion) is basically a no-go -- the last thing you want is for a player to see a stuck unit, or a frame drop, and in that way it's very much an "all or nothing" exercise. :)
0 - Co-Creator & developer of SimAirport http://store.steampowered.com/app/598330 (in Early Access & under continual active development)
For turn-based games, absolutely -- and I suspect that's why you rarely see pathfinding brought up as a big concern for turn-based games. They have plenty of time to re-compute paths, there's a perfect sequence for map invalidations, etc... But for RTS or simulation games, the latter being where I draw my experience from[0], it's really a different beast -- you touched on some of the reasons why, such as map invalidation & larger total scales (units, nodes, commands, etc).
What happens is, you do this -- and then you fire up a build and find that the game freezes every time you need a path. Okay, let's get some concurrency going -- easy! But how are we going to handle map invalidation/sync between threads? Definitely solvable. Then you find, it's still too slow -- thread overrun! You can't do realtime pathfinding for 500 units through 100k nodes, why not? Is it the sync/concurrency locks?
Meanwhile, you've spent all this time trying to get perfect paths to run fast and you could instead be working on what the gameplay needs; maybe that's pathfinding related too, perhaps some units should only be able to use paths that have 5x5 clearance while others need 10x10, etc... How do you deal with nodes that are unreachable -- do you allow the pathfinder to explore the entire terrain, only to find there aren't any paths? Sure, you can do some initial exploration first; but perhaps 'reachability' differs per unit-type, or maybe you have uni-directional traversals, etc. Or how about avoiding other units? Etc... :)
Pathfinding generally isn't really that difficult to get to an MVP implementation of; but it IS hard to get something that is anywhere near "perfect", for every single case, and especially if it needs to be realtime or if your map changes.
The requirements inevitably continue to add up (out of gameplay necessity, not client demand per-say), and each respective aspect of it nearly always takes an incredibly large amount of time to implement, test, debug, and ship.
FWIW, our game[0] implements ~5 fairly distinct pathfinding "approaches" to deal with various situations like these (windowed, various levels of hierarchical / JPS, vanilla A*, cooperative, etc), some with more "complete-ness" than others. I can assure you that it's anything but pure theory-craft, and honestly it can sometimes be fairly difficult to reason fully reason about it without trying things. That's another awesome thing about gamedev, though also a negative as well -- sometimes you can "reason yourself to death" and it's often better to form a high-level plan and then give it a try, so you can quickly see where the holes in your approach are & and how surmountable (or not) those pitfalls may be.
In any case, I think my point can be largely summed up by saying that it's likely very often a case of "easier said than done" when truly considering the entirety of the problem. One final thing to consider is that, when it comes to games, allowing a failure case (or a full-map expansion) is basically a no-go -- the last thing you want is for a player to see a stuck unit, or a frame drop, and in that way it's very much an "all or nothing" exercise. :)
0 - Co-Creator & developer of SimAirport http://store.steampowered.com/app/598330 (in Early Access & under continual active development)
> Okay, let's get some concurrency going!
Gentle reminder to the audience that AOE1's minimum target system was a single-core Pentium-90 with 16MB RAM, so this would not have helped at all :)
Gentle reminder to the audience that AOE1's minimum target system was a single-core Pentium-90 with 16MB RAM, so this would not have helped at all :)
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.
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.
Meanwhile I will be in forests... Kingdom Come.
http://thehardtimes.net/harddrive/designing-video-games-hard...