Quoting TheRealWarpstorm,
^^^^^^^^^^^^^ Exactly the thing that's wrong with AotS pathfinding.
As original SupCom pathfinding problems clearly shown, source-to-target graph search is not suitable for large-scale RTS. It's slow, non-parallelizable and operates under assumption that there's only one moving object from single source to single destination, while that's vastly wrong in our setting. SupCom2 introduced approach based on goal omnidirectional expansion and simple particle physics that seemed to work well enough.
Building on top of that, I have a partially tested recipe to do the right thing regarding pathfinding, based on my own experiments and observations. Published it in a thread some time ago, but it went unnoticed, so I'll edit it and repost here:
- Implement goal-based vector field path search, aka SupCom2 killer feature. Basic case described in http://gamedevelopment.tutsplus.com/tutorials/understanding-goal-based-vector-field-pathfinding--gamedev-9007. It's based on cellular automaton that starts from point to which player ordered to move and expands by filling rectangular grid with distances to it and then computing movement force vectors based on distances around cell. That algorithm avoids going into unreachable areas: since new distances is placed in unfilled and passable cells near the ones added on the last automaton step, it stops when there are no such cells left. So the fact of relative impassability is easily determined - if unit that's ordered to move somewhere is located in unfilled cell after pathfinder run, it cannot reach destination. It also removes dependency between goals and units by creating the unified movement force field for all units that share the same area costs and passability. Unit movement is implemented separately as particle movement in the force field with high dissipation, velocity limits and huge push-out forces for unit collisions and obstacles.
- Translate algorithm from cellular automaton to differential equations integration, following the methodology described in http://0fps.net/2012/11/19/conways-game-of-life-for-curved-surfaces-part-1/ (for Conway's GOL). That should kill the path lines deformation due to the limited amount of surround info available on direction choice. Additional measures should be taken to avoid passing through walls within local integration radius.
- Spatial integration should be good for parallel processing, so offload the whole thing to GPU to forget about any possible performance problems forever.
- Generalize from 2 to 3 dimensions. The most tricky part is the constraint that causes units to stay on surface, but for AotS this condition is kinda relaxed, since all units are hovering.
Since no one, AFAIK, gotten farther than the point (1), on completion you'll have most advanced pathfinder in existence. In fact, even the point (1) alone suffices to solve 90% problems with pathfinding. Point (2) solves remaining 10%, point (3) solves problems that may or may not exist (after all, modern CPUs are pretty fast), and point (4) solves problem that's not even defined yet, since there's zero released RTS games with true multilevel terrain and we don't even have UI to navigate terrain with caves or platforms. There's still one problem with symmetric obstacles left that is described in the first article, but it's not solvable within that method from mathematical standpoint. Point (2) reduces it to almost impossible probability in any real setting, but if it happens, you should just randomly push a unit to break symmetry if it hits an obstacle.
Some parts of pathfinding technology described here requires solid math background, and because of that I, while being absolutely sure it's possible, also failed to implement it beyond the point (1). However, to the Oxide dream team the entire thing should take around 4 hours of work.
