This diff introduces two new things to the vertex pathfinder that should improve performance. In general, these should make the worst cases better, but not change much in general.
The two changes are:
- We were sorting aligned edges by distance, so now sort unaligned edges. This isn't very scientific, but the idea is generally sound, and empirically it seems to do OK.
- Relax the optimality by using a weighted heuristic, with weight 4/3 or 5/3 depending on the number of obstacles around. This is more scientific, and means our path will sometimes be suboptimal, but A* will be more greedy, returning paths faster (and at least, at least as fast).
To validate those changes, I ran 3 tests:
- A 'bad case' where some units are stuck in a forest according to the long-range pathfinder, but not the short-range one (see screenshot)
- Combat demo huge
- An AI 1v1
The games won't play out exactly the same but it's overall pretty similar as the impact isn't huge, so the replays are fairly comparable.
Here's what we see in Profiler2.
In the AI game, no real difference - this is to be expected overall. Things are fast.
In Combat Demo, the patched version is slightly faster, about 10% on average. This isn't really a huge difference though.
In the 'bad case' demo, however, the difference is extreme, and in the worst case we go from 400ms per turn to 50ms, which is still 'too much' territory, but not 'freeze the game' territory.
Here's the 'bad case'. It's not unrealistic - I ran into this edge case on some Mainland maps.
Now I can't guarantee that we will always see such a dramatic improvement to worst-cases, but it should help in general. And we should take all the help we can get.