10 ms·
Age of Empires Definitive Edition's pathing and movement
- simias 9y agoI 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.
- Doxin 9y agoThe old-timey pathfinding was probably optimising for memory usage, not speed or correctness.
- AstralStorm 9y agoActually 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).
- creato 9y agoBefore 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.
- AstralStorm 9y agoAre 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.
- w0utert 9y ago'Pathfinding' in the scope of an RTS means a little more than just 'pathfinding' in the scope of a graph. If you had read the article you would have seen that there is a lot of dynamics behavior going on that is essential for the gameplay, but mostly unrelated to the A* search itself. I don't think you would find many books from the 80s about pathfinding for RTS games.
- animal531 9y agoExactly. There's a huge difference between a theoretical algorithm in a book (that performs 1 search) vs having 120 real time units all trying to walk together, or even worse, through each other. In the 80's and 90's you were lucky to dig up docs from BBS releases that had math and graphics tutorials in them, it was very hard to find anything practical.
- AstralStorm 9y ago120 real units. By that you mean plotting 120 paths simultaneously using a common flow algorithm used by internet routers which is more than fast enough and reasonably easy to speed up or truncate. The tricky part is on assigning nodes on a contiguous map or reducing number of nodes. (Or expanding node resolution on demand.) Of course many games of the time side stepped it by using greedy truncated pathing instead. Easy, dirty, mediocre results.
- AstralStorm 9y agoActually, 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.
- ygra 9y agoTo 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.
- taneq 9y agoYep, you fix the crash bugs, and then the game breaking bugs. And then, if you're lucky, you fix ALLLLLL the other bugs.
- bri3d 9y agoI'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.
- munificent 9y agoMachines 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.
- megaman22 9y agoHe 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.
- AstralStorm 9y agoThat easily explains why they got only 4x improvement... better algorithms would give like 100x but would no longer be authentic.
- sdrothrock 9y agoTalk about a thankless job! That's an extensive list of bugs and working on someone else's (very old) playground is incredibly difficult.
- pm90 9y agoI 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!
- always_good 9y ago> gorgeous graphics (for the time) Google image search "age of empires 2." Those graphics are still amazing and can't really get much better, which is why all they need is HD remastering. 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.
- frozenport 9y agoReading a bunch of these, why not just change the sprites in Age 2 and call it a day? Sounds like bad management decisions.
- kbwt 9y ago>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?
- simonpantzare 9y agoIIRC the max unit cap is much higher.
- i2om3r 9y agoIn 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."
- Narishma 9y agoIn 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.
- numerlo 9y agoThe fact that you don't need to optimize something doesn't mean you shouldn't.
- Invisig0th 9y agoAvoiding premature optimization is one of the most important best practices of modern software development.
- qu4z-2 9y agoThis isn't premature... the algorithm and performance are understood. That said, I agree that it's not always the best use of time.
- softawre 9y ago
- faitswulff 9y agoThe 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-work-millions-angry-players-make-worthwhile/ http://thehardtimes.net/harddrive/designing-video-games-hard...
- kimikimi 9y agoA 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.
- pvg 9y agoIt'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.
- paulryanrogers 9y agoMaybe the solution is a classic/pro mode and a novice/Renaissance mode.
- s_m_t 9y agosplitting the player base is almost always a bad idea
- paulryanrogers 9y ago
- urza 9y agoMeanwhile I will be in forests... Kingdom Come.
- kakaorka 9y agoI hate that it’s only available on windows 10. Bad move Microsoft!
- overcast 9y agoWindows 8 is 5 years old. Windows 7 is 8 years old. Move on.
- khedoros1 9y agoAnd? 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.
- owenwil 9y agoIt literally does if you use a SSD.
- khedoros1 9y agoThat'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.
- artimaeis 9y agoGenuinely curious: what other platforms would you like to see this on?
- khedoros1 9y agoWindows 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.
- z3t4 9y agoA 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).
- AstralStorm 9y agoAnd this is why Age of Empires never got its pathing or engine rewritten in later versions... oh wait.
- waterhouse 9y agoSomething 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 https://en.wikipedia.org/wiki/Dijkstra%27s_algorithm
- Radim 9y agoFor people interested in path finding, there was some fascinating research done in the 90s: http://faculty.nps.edu/ncrowe/snell2.htm 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).
- rcfox 9y agoI 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-funnel-algorithm.html http://digestingduck.blogspot.ca/2010/03/simple-stupid-funne...
- crispweed 9y agoYes, 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%20graphs.pdf 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).
- AstralStorm 9y agoAnd I suppose when encountering them (since they were culled not truly removed) switching to a backup collision avoidance mechanism or replanning?
- discreditable 9y agoHaving 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.
- JepZ 9y ago> 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?!?
- shoo 9y agomaybe 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.
- AstralStorm 9y agoThe 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.
- gameswithgo 9y agoI 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 https://www.twitch.tv/videos/233560937 Much simpler case since it is on a grid and turn based!
- indescions_2018 9y agoJust 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_Pathfinding_and_Steering_Using_Flow_Field_Tiles.pdf http://www.gameaipro.com/GameAIPro/GameAIPro_Chapter23_Crowd... Flow Field Pathfinding Tutorial http://leifnode.com/2013/12/flow-field-pathfinding/ http://leifnode.com/2013/12/flow-field-pathfinding/
- maaaats 9y agoDon'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)
- arcticfox 9y ago> 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 https://github.com/SFTtech/openage has many plans, but your dismissals are starting from wrong assumptions.
- pjc50 9y ago> 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.
- Const-me 9y agoI 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/
- EddieSpeaks 9y agoAlso I have no idea why it needs the internet. I want to play it on a train commute but I can’t.
- JepZ 9y agoSounds 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.
- jandrese 9y agoAs 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.
- quadcore 9y agoCool. 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 https://gfycat.com/TediousThoseKitty