Incorrect pathfinding and path following around chokes (bottlenecks)

[PunkPun]

As players really don't like the current behaviour, multiplayer map making meta has pivoted to wide and open maps, where in RA any choke through which an army is expected to move is no smaller than 7 cells. This is a fairly harsh restriction, and it basically means that majority of maps consist of a large arena with obstacles of various sizes dotted around. Bridges are only ever used for small objectives.

Speaking of bridges, they are they main offenders. Mission maps are filled with bridges and plenty of other 1-3 cell chokes, and unlike in in the aforementioned multiplayer maps, they are the main way of progressing. As we don't possess the luxury of changing mission map design I think it's a fairly serious issue to tackle. Granted, a lot of bridges are also the only path so pathfinder can brute force with BlockedByActor.None.

Now onto describing the issues with the current pathfinder:

1. The first pathfinder layer BlockedByActor.All considers all actors as blocking. Meaning if there are friendly units in a choke or moving though a choke, and a path exits to the destination that isn't through that choke, the unit will take that path, regardless of it being 100x worse.
2. If the units managed to pathfind successfully through a choke, then the issue extends to path following. When a unit is following a path and is unable to enter the next cell in that path, it calls on the pathfinder. In bottlenecks units tend to need wait for other units to move, meaning when repathing the 1st issue kicks in. The path is temporarily blocked so the units tend to pick a path that is 100x worse.
3. The picked worse path is not only going against player expectations, but also is often dangerous territory. If you don't catch your units misbehaving then they are as good as dead, especially harvesters as they are autonomous thus much less likely to be noticed.

A few gifs for best case scenarious. Large bridge, I've given the order while the bridge was empty, not a massive amount of units, the alternative path is death:

• If it was a 1 cell choke the majority of units would have taken the alternative path.
• If I would have given an order while something was on the bridge, all units except the ones on the bridge would have taken an alternative path. (it's common for the player to give followup orders to fix unit behaviour, but in this case against player expectation any order would only makes the situation worse)

To reproduce find an area that has 1 chokey entrance and another entrance somewhere far away. Though the easiest method is in an open field to create the bottlenecks yourself with walls. You get the most control that way.

How to go about fixing these issues:

1. The pathfinding layers need to be merged together and options for nudging allied units or bypassing moving units instead added as weights. (would close PathFinding, mutli BlockedByActor check aware #19221)
   • It's important to not ignore moving units and add weights as we don't want units to create chokepoint scenarios in plain open fields and devolve into a single file formations.
2. The pathfinder should consider units that are actively searching / following a path as moving. This step is fairly difficult, one way would be to check wether the Move activity is active. This poses multiple issues.
   • Move activity becomes active on first frame of its activation, meaning that when an order is given to a group of units the first unit to pathfind will still consider the rest of the units in that group as non moving, only the last unit of the group will pathfind correctly.
   • Third party mods might want to use a different activity for moving.
3. Change the path following behaviour to re-pathfind when the next cell to enter has a higher enter cost (instead of only when blocked). This would fix the issue of when the path actually gets blocked. Without this a group of units will take a very long time to realise that the path is no longer valid, and I imagine with enough units deadlocks could occur.

I had attempted to solve this in bleed...PunkPun:OpenRA:no-chokes. The solution is incomplete

[PunkPun]

Related #3241 #3880 #4813 #5968

[anvilvapre]

Perhaps the path planner should become group aware. Plan paths for a whole group at once. Where it first decides on a formation, priority and follow order of the group - before finding one path - with alternatives - for the group to follow. To avoid the units of the group to compete for the same cells.

Perhaps units should be able to reserve a cell in future. To allow units to follow in each others steps without having to replan. This would cause them to nicely wait to be able to pass a narrow bridge - if walking around is not faster? The enemy would still be able to interrupt/override these reservations.

[PunkPun]

The current pathfinding layer system was made to address grid locking #16408. So it is of upmost importance for the future pathfinder does not regress it.

Grid locking means 2 units expecting each other to move out of the way, making them forever stuck until one of them dies or a player issues an order.