Prioritize some units when moving to a target

[ffm]

Units don't make way for other units. Reproduce (Example): at the beginning send all units to a point and if the cavalry is surrounded by the other units, try to send the cavalry away. It can't, because the idle units wont let it pass. Rev: 17060.

Idle units have a lower priority task as the horse. Other (more relevant) example would be: a ram trying to get on a fort, but champs are in the way. Solution would be moving the ram to the fort has a higher priority than th champ attacking the fort.

Women should move out of the way of men (no offense) with mission for fight.

And this should also affect allied team members. If you are in a team with a less skilled player, he could block your ram (without bad intention).

i propose a prioritization like: idle < just move < gather < fight < siege movement

Maybe the higher prioritized unit can push the lower one away.

[ffm]

Other example: guard with 40 units a ram, now try to send the ram away. so the guarded unit should have a higher priority than the guard.

[Stan]

This is actually a todo line 979 of CcmoUnitMotion.cpp

// TODO: if the target has UnitMotion and is higher priority,
// we should wait a little bit.

[Imarok]

Move tickets to Simulation as UI & Simulation got some sub components.

[elexis]

​Phab:D1490 for unit pushing.

[wraitii]

In 25182:

Add a simple 'pushing' logic to unit motion to improve movement.

This implements a form of crowd movement that I've generally called 'unit pushing' in the last few years.
Essentially, any two units will push each other away when they're too close. This makes it possible to ignore unit-unit obstructions, and thus makes movement much smoother in crowds.
This first iteration of this system only allows pushing between idle units and between moving units (i.e. a moving unit does not affect an idle one).
This is because the unitMotion logic to detect it is stuck & needs to use the pathfinders starts breaking: units can fail to move because they are pushed away from their intended movement, and the current logic fails to handle this gracefully.
Thankfully, the most value of this patch in terms of player experience is found in the improvements to group movements and shuttling.

Other impacts:

• As the short pathfinder is called less often, we can increase the starting search range & reduce the # of max turns, both improving collision recovery.
• The performance of idle units is slightly worsened, as they must be checked for idle-idle collisions. If needed a 'sleeping' system, as used in physics engine, could be implemented.
• In general, however, expect slight performance improvements, as fewer short paths are computed.
• Gathering efficiency should increase slightly, since shuttling times are likely reduced slightly.
• As a sanity change to improve some edge cases (units that say they're moving, i.e. pushable, but don't actually move), the 'going straight' logic is turned off if a short path has been computed. This requires a few cascading changes to work correctly.

Technical notes:

• To reduce the cost of the n^{2 comparisons that pushing requires, units are only compared within a small square on a grid which is lazily reconstructed each turn. The overhead seems rather small, and this is much simpler than keeping an up-to-date grid.}
• The design is intended to be parallelisable if needed someday.
• The pathfinder's CheckMovement ignores moving units in UnitMotion, as that is now the spec. Idle units are not ignored, which is required for the 'collision' detection to work correctly (see above).

Refs #3442 (not fixed - idle units are not pushed by moving units).
Fixes #5084 (the overlap can still happen, but units will push each other away).

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