Pathfinding performance issues

[netnazgul]

Can't really vouch for this one being a new thing, but naval AI units put a skirmish game to a halt with just 5 cruisers trying to target my army on the ground out of their reach. Destroying cruisers one by one increased performance considerably, up to VSync-limited 60fps.

https://youtu.be/C9JkW2IwctA

Here's a replay, though it also has a lot of other unneeded stuff. Noted a perfdrop at around 5min, then it got better around 7:20; cruisers chase is closer to the end of the file.
https://www.dropbox.com/s/dh5b2qfgen02ex6/OpenRA-2020-03-01T182317Z.orarep?dl=0

[abmyii]

Confirmed this - the issue is MoveWithinRange. It isn't limited to AI nor even cruisers or boats in general, however, though the highest effect to FPS is when a cruiser is used. The easiest way to reproduce is to build a cruiser and force-fire on land that is out of range. Seems to be a regression from release-20200202 which doesn't lag in the same case.

[netnazgul]

Yes, a bunch of island-strapped AI units also cause the substantial FPS drop.

[abmyii]

Yes, a bunch of island-strapped AI units also cause the substantial FPS drop.

I'm nearly certain it's a regression from release-20200202, which isn't too bad because there isn't much to check in order to fix it. Have you tested the same conditions in that version yet, just to confirm that it is a regression?

[pchote]

The worst part of this was probably introduced by a28be21, which makes us we call the expensive MoveAdjacentTo.CalculatePathToTarget method 4 times per unit per tick instead of just once.

The best fix here will be to find a way to call this at most once every few ticks instead.

[pchote]

The check at https://github.com/OpenRA/OpenRA/blob/bleed/OpenRA.Mods.Common/Activities/Move/MoveAdjacentTo.cs#L129 is the ain bottleneck, which isn't affected by the check value. 4a609bb also hurt a lot, but there is no clear simple mitigation we can apply.

We could work around the worst of the regression by passing all the BlockedByActor values through Move.EvalPath and into the getPath so we can loop over them after the expensive domain filtering. This is not elegant, but should work if needed as a last resort.

A smarter solution would be to cache searchCells, which would allow them to be reused across multiple ticks. Some thought will need to go into when to invalidate the cache.

It also seems that AttackFollow.AttackActivity does not cancel itself or rate limit repathing attempts if the target is unreachable.

[abmyii]

@pchote Have you considered creating tests for the engine so as to avoid regressions such as these in the future? I know it will be a painful task, but it may be worth the time saved by making them.

[pchote]

Of course, and we already do for many things. But there is a big difference between deciding that something like this issue needs to be tested and designing an implementation that actually works.