Units can fail to go around large obstacles when short-pathing

[elexis]

In the replay for r23063 (still works with r23074) uploaded at ​Phab:F1100948, at minute 34, there were about 50 naked fanatics that failed to find a path to the enemy units and thus lost the battle without delivering damage.

There was a small passage between houses / pyramids that was obstructed by units, and as a result, the attackers seems to have just not computed any valid path, or followed the longpath, aborted due to the shortpathfinder and then gave up.

See the screenshots at ​Phab:F1100948#36 and F1100948#37.

The bug is easily reproducible by loading the savegame from that minute uploaded at ​Phab:F1100948#38, changing the perspective to the green player / go2die / naked fantic owner and then ordering the units to attack one of the cavalry units behind the pyramid or move behind the pyramid.

[wraitii]

This is caused by the max-range of the short-range pathfinder not being large enough to go around the houses in all cases [EDIT: in this instance, because the outer-most corner of the houses isn't reachable).

The only fix is to increase the max-range of the short-range pathfinder, but that can increase lag in general.

IMO it's a won't-fix - perhaps we. can increase the max short-range pathfinder a bit, but these kind of issues are inherently unfixable without unit pushing and/or a single pathfinding system.

Edit: also this isn't a regression. Well it technically is, because this sort of bug was fixed by the 'don't add domain edges to the short pathfinder' thing, which I reverted in July, but that particular hack had its own set of problems. We can re-revert that, but fundamentally some edge cases will break whatever we try.

[elexis]

See discussion on ​http://irclogs.wildfiregames.com/2019-10/2019-10-16-QuakeNet-%230ad-dev.log

This is caused by the max-range of the short-range pathfinder not being large enough to go around the houses in all cases

14:06 < wraitii> at least is soudns plausible

The constant SHORT_PATH_MAX_SEARCH_RANGE was lowered in r22526. Increasing to 10 doesn't resolve the specific situation in the replay. We didn't actually check what the states of these units are, it could be that, but it could also be something randomly different or unknown in the unit pathing logic.

One could create a replay with only one move command for one or more of the naked fanatics, load the savegame and that minimal replay from commandline and analyze the unit logic in nonvisual mode (​https://pastebin.com/raw/5xzKwLFx)

[Imarok]

"This is caused by the max-range of the short-range pathfinder not being large enough to go around the houses in all cases" What if the short-range pathfinder increases its max-range if it can't find any path?

[wraitii]

"This is caused by the max-range of the short-range pathfinder not being large enough to go around the houses in all cases" What if the short-range pathfinder increases its max-range if it can't find any path?

This already happens. With a sufficiently large range, it will start causing noticeable lag. We can increase 10 to something higher.

Based on elexis comments, I will try to recreate the situation and check if increasing the range does fix it.

[wraitii]

Minimal replay of the bug as of rP23683

[wraitii]

Much worse situation. You need a max_range of 50 for this one, and it _will_ lag noticeably. And that's a single unit computing a single short path.

[wraitii]

In this example, the entity #2393 has no path. So it will keep trying up to any arbitrary upper bound of MAW_RANGE, including the whole map, lagging absurdly in the process.

[wraitii]

See replays above for some example of why we can't really put an arbitrarily high max-range. It will start lagging, possibly so much that the game becomes unplayable.

It would even be fairly easy for an ill-intentioned player to trigger a similar situation to commands.3.txt but with many more units, making the game unplayable and causing the opponent to resign, to avoid losing a game for example.

Further, because of #3700, it might actually make it possible to disconnect any arbitrary player just by having a faster computer.

I reckon 6 was a poor choice of MAX_RANGE, and I'll bump it back up to 14, which should be "good enough" for most cases, including most of the larger buildings.

[wraitii]

​Phab:D2754 reintroduces a longer range. See also #5586.

[wraitii]

In 23699:

Fix some cases of units getting stuck.

This fixes an off-by-one error that led to entities sometimes getting stuck against obstructions.
It also increases the max-range of the short pathfinder to help entities find their way around corridors and house blocks.

Fixes rP22609 (off-by-one error) and reverts the range changes from rP22526

Reported By: Freagarach

Fixes #5586 . Refs #5624

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

[wraitii]

In 23867:

Abort formation-walking on any message from UnitMotion.

Units in formation can occasionally request many short paths (and thus introduce crippling lag) if their offset is obstructed.
This particularly happen when the formation is idle, since the offset then always remains obstructed.

To prevent this, it is OK to immediately stop pathing on any motion message (obstructed, failure, success). This does not break formation movement since messages are only sent when the formation controller is not moving (this finishes what was started in rP23496).

Ideally, this hack could be removed if the short-pathfinder was quick enough / units were better at aborting.

Fixes concern raised by Freagarach on rP23806.

Refs #5624 in that the max-short-path range is the source of the lag.

Reviewed By: Angen

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

[wraitii]

This has been mitigated for A24, and I don't think we can do better until we remove the short-pathfinder or can use it over much larger ranges.

Lowering priority and pushing to A25.