Age of Empires Definitive Edition's pathing and movement
richg42.blogspot.com
richg42.blogspot.com
http://thehardtimes.net/harddrive/designing-video-games-hard...
If it all feels adequately justified by the scenario and core premises, then there's an actual resolution. They shut up and play.
In news from Spain, Generallissimo Francisco Franco is still dead.
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
[1] Day[9] on Pathing in BW https://youtu.be/rWvoMrYCQBU?t=17m50s
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.
I thought it was pretty good, and more than enjoyable, when it came out 19 years ago.
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.
This is precisely why RTS as a genre pretty much died.
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).
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).
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..
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.
How would that make any impact at all given that the game ran just fine on 1997 hardware?
With those costs, there should be a compelling benefit that you get out of it. Otherwise, it's not worthwhile.
>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.
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).
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.
I can understand skimping $40 on a book... but not the argument that it was hard to find those things.
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.
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.
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.
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.
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.
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.
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 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.
Move on.
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.
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://www.twitch.tv/videos/233560937
Much simpler case since it is on a grid and turn based!
What is left of A* if even that doesn't work?!?
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.
What they had was even more of a bug where some nodes were skipped from expansion.
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
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)
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.
This would not have been a great solution on the original AoE's 16MB target memory.
So far I played only one match but that felt pretty much like the AoE1.
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.
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
Marching squares indeed produces a similar result of "squishing". However as it is ran per unit you will have more collisions.
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).
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
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...
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.
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.
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)
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 :)
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.
The moving units are often easily handled via local avoidance as needed.
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.