UnitMotion can go into dead ends when too many units are around

[Silier]

See picture of stucked units because of that ​https://drive.google.com/file/d/1VhF1dRdCrxB7AQ1N-V9V0TSJxVK-78dS/view?usp=sharing

and replay from rP23919

[wraitii]

"minimal" reproduction of the weird pathing

[wraitii]

There's actually a few things at play here, but I'd say every component individually is working fine:

• Units give up (after a long while) when they can't find a path. This results in the stuckiness above, but only when there are a _lot_ of units. I don't think it's a huge issue. They're not actually stuck, just gave up.
• When the are obstructed, they compute short paths; If that fails, they 'pop' long waypoints to avoid issues with waypoints obstructed by units. In a case like the order in the replay above, this means they compute a path that crosses impassable terrain, after a while.
• The short-pathfinder has a limited domain, and can't go beyond that. It will still try to get closer to the goal in its limited domain.

All of the above combine to give the behaviour of a unit that fails to path, pops waypoints, calls the short-pathfinder, which finds it cannot path to the long-waypoint but can get close by moving further into the 'wrong' direction, and so on, until the unit cannot get any closer, at which point it recomputes a long-path, which sets it back on its way.

One thing to improve is to stop popping if the long waypoint is too far away, as that no longer really makes sense. Would likely avoid the issue in the first place.

---

The title is technically wrong, because the pathfinder never tries to move through impassable terrain. I've reworded it.

[wraitii]

In 24429:

Improve UnitMotion behaviour when working around obstructions.

This improves behaviour when units need to go around a concave obstacle. They would tend to clump inside the 'dead-end' before realising they needed to go around. This was rather easy to trigger on Acropolis. See included Unit Motion Integration Test.

The cause is the logic that removed the next long waypoint when obstructed. While that behaviour is desirable, removing too many waypoints means the unit tries to short-path, using a small domain range, to a goal that's impassable, meaning they go as close as they can in Euclidian distance, i.e. towards the dead end.

This changes that behaviour by only deleting waypoints within a certain distance from the entity, scaling with search-space range. It's tricky to find a good compromise between performance and behaviour here, but the values I've picked seem OK.

However, the fact that the entity would ultimately remove all waypoints and thus trigger a full path recomputation was actually a feature, inherited from D2754 / rP23699. This diff therefore handles that explicitly, doing so on a more regular basis to behave better overall.

As a further cleanup, "m_FailedPathComputations" is incremented in HandleObstructedMove, as it is quite possible to never increment it in PathResult despite not getting actionnable paths. This thus renames it to m_FailedMovements, and uses the opportunity to clean up PathResult(), by only having one path for both short and long-range paths. Further, PathResult now does not immediately request new paths, leaving that to Move(), to avoid requesting transient paths that aren't actionnable.
This also makes it possible to revert rP22815. It requires increasing the MAX_FAILED variable, or more units get stuck as they reach the max more often.

The search-space expansion is slightly slowed, and with a little more delay, as a performance optimisation. From testing, this doesn't impact real movement much as units short paths tend to be invalidated by the next turn, as other units move, anyways.

Clarify comment around the vertex-pathfinder search-space bounds hack, and ensure it isn't used for the very worst cases of units being stuck, as it could be a pessimisation then.

Finally, this explicits a 2011 hack where if the long-pathfinder fails to return a valid path the goal's center is used directly. This happens when the goal is unreachable to the long-pathfinder, which may be because it is actually unreachable or because only the short-pathfinder can reach it. In those situations, the hack allows a last-ditch attempt at reaching it before failing to move entirely. Performance wise, this is faster overall for actually unreachable goals, since it skips all the intermediate steps. For reachable goals, it might be occasionally slower, but that case is quite rare (certainly rarer than unreachable goals).

Reported By: Angen

Fixes #5795

Differential Revision: ​https://code.wildfiregames.com/D3203