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