Age of Empires Definitive Edition's pathing and movement
Cool. I&#x27;ve coded a RTS myself, and I might be able to add some information.<p><i>DE&#x27;s pather gives up if after many thousands of iterations it can&#x27;t make forward progress towards the goal, to avoid spending CPU cycles on hopeless pathing unnecessarily. (It&#x27;s more complex than this, but that&#x27;s the gist of it.)</i><p>The right way to do that is to make a unit <i>pop</i> 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.<p><i>I implemented the A</i> early exploration optimization*<p>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&#x27;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.<p>The only requirement is a map of the walls at the size of the &quot;big grid&quot;. Could be problematic I guess in some cases. Not that it doesn&#x27;t take into account dynamic walls which is ok (units and such).<p><i>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><p>I understand the constraint of this new Age of Empire. Still it&#x27;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.<p>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&#x27;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.<p>The way I solved that is by using marching squares. All units moves freely on the map, at the &quot;pixel scale&quot;, the floating point scale - though it&#x27;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.<p>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&#x27;s quite super simple to implement and as fast as the grid basically. There is also an added benefit: it&#x27;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.<p>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: <a href="https:&#x2F;&#x2F;gfycat.com&#x2F;TediousThoseKitty" rel="nofollow">https:&#x2F;&#x2F;gfycat.com&#x2F;TediousThoseKitty</a>