Game client lags significantly when AI units try to find waypoints on large maps
xezon opened this issue · 8 comments
Game client lags significantly when AI units try to find waypoints on large maps. Easily reproducible on Twilight Flame map by placing a hard AI on top and player on bottom. AI will send units, piles them up on the cliffs, and cause lag spikes.
Explanation of issue from Map Creator perspective:
Replay file with lags:
ai_pathfinding_lag.zip
Game Room setup:
Units clogging and causing lags:
I tried to locate origin of performance issue in profiler, but have not been able to get clean call stacks due the lack of working pdb file.
PredatoR
Twilight flame has wrongly set waypoint paths. That's a big reason why units get stuck near the cliffs.
Well it has nothing to do with AI armies, because you can cause this lag yourself aswell as a player on TF. What Predator said is more likely, or it's the waypoint system in general.
Stalls also occur on tricky path finding, such as Dozer trying to drive into box.
generals.2023-06-10.16-52-52-20.mp4
If it will be fixed - there should be a monument in gold for those ))
This is where this issue happens:
The lag can be mitigated by limiting the time that internalFindPath can search for the path, perhaps something like the "PATHFIND_CELLS_PER_FRAME" constant which is used up the call tree. But that wouldn't solve the problem of the AI getting stuck.
I thought I posted this before but I can't find it... weird.
The AI is getting stuck on that cliff because there is a bug with how pathfinding along paths works. On Twilight-Flame in cliff-vs-cliff setups, the end-point of the attack-path is closer to the team than the origin of the attack-path.
I made a short video for clarification.
https://www.youtube.com/watch?v=czT-K7tpqCU
So there are two problems with pathfinding:
- Pathfinding is generally very bad at working with obstacles, be it cliffs or buildings
- Approaching teams will start approaching from closest waypoint of path to origin of where attack team was created, instead of approaching through actual intended start-point of path.
Here are a few more thoughts on the two issues:
Issue 1:
The pathfinding is far more superior in games like wc3 because wc3 is exclusively grid-based. The largest map-size in WC3 is a grid-size of around 256x256. All objects can only be rotated in 90 degrees angles and placed along this grid. Twilight Flame has a size of around 500x500 and while impassable areas are also grid-based in Zero Hour, building placement is not grid-based at all and allows free rotation around the X and Y coordinates in steps of 0.01. So instead of 256x256x4 you get 50.000x50.000x36.000 possible ways to place down a singular building on Twilight Flame. So by this alone, the pathfinding algorithm is a lot harder to optimize in Zero Hour. But still.. there is no excuse for the terrain pathfinding to be as shitty as it currently is, because it IS grid-based and non-dynamic. So even if you use construction-sites to flatten out a piece of terrain, the impassable-zones are hard-coded into the map and won't update. So I have a feeling that terrain pathfinding should be fully fix-able.
Issue 2:
Just to be clear, the issue isn't that the AI can skip waypoints if subsequent waypoints are closer. That is a required feature that cannot be touched. If you changed this, enemy armies would always leave your base again and start from the entrance with their attack again, every time they are re-ordered to attack. Being able to skip waypoints is required for the AI to work as intended.
The problem however is, that the AI only uses linear distance to determine what waypoint of the entire path is closest to them. And in edge-cases like twilight flame, this gives false results. Every individual point should be routed and checked for actual approach-distance instead of just checking linear distance. But then again, you would make the algorithm slower overall, just to make it work in edge-case-scenarios.