UnitAI/UnitMotion should reduce repathing attempts when units are stopped

[Jonathan Waller]

Currently if a unit is following a command and can't reach the destination, it constantly retries which causes the game to slow down due to pathfinding being called so regularly. The attempts should be made less frequent and after a certain point the unit should give up and become idle.

[Josef Kufner]

I observed this behaviour too. When I have city with properly built walls, enemy units cannot walk inside and as amount of units gets higher, game is less and less playable (sometimes less than one FPS). When I open the gate, enemies can walk in and game is smooth again (before everyone dies).

Path finding and re-planning of AI units must be throttled to reasonable limits, preferrably by game itself rather than by AI.

When unreachable target is targeted by AI, it should be globaly blacklisted, until some building is destroyed (does not matter which one nor how). When any building is destroyed, blacklist should be re-evaluated for target reachability (but not too often). This way AI units will not attack unreachable buildings, but they will select walls and other border buildings.

I have version 0.0.14-3 from Debian.

[Josef Kufner]

I also noticed a huge difference between locked and unlocked gate. When gate is locked, AI uses much more CPU than when gate is not locked, but still closed.

[historic_bruno]

One of the best ways to encounter this currently is to try garrisoning the Mauryan support elephant in the CC. The ranges are messed up, so it fails, but it tries continuously. I suspect with a large group, it would cause severe lag.

[sanderd17]

I attached a small patch for testing (it's not serialised yet). The patch keeps the time since the creation of the unit, and allows only a certain number of paths over a certain time (set in the consts, here 15 paths over 20 seconds).

It works, in a way that when something is unreachable, after ~30 seconds, the units give up pathing in most cases (depending on how long they can walk before they hit the obstruction again). But I don't think it will help with the lag problem, as it takes 20 seconds for them to figure out they can't move.

As the number of long-range pathing requests per unit is under 1 per second, it's impossible to make this time a lot shorter. As the limit can perfectly be achieved with manual actions.

Another possibility would be to keep the units in formation until the formation actually reached the asked position (and only disband then). This would reduce the number of pathing requests as only the formation would request new paths. But it's not very good for the AI, as the AI doesn't always path using formations, and often gives a command per unit. This also won't work with units that can't use formations.

[Itms]

In 16751:

New long-range pathfinder.

Based on Philip's work located at ​http://git.wildfiregames.com/gitweb/?p=0ad.git;a=shortlog;h=refs/heads/projects/philip/pathfinder
Includes code by wraitii, sanderd17 and kanetaka.

An updated version of docs/pathfinder.pdf describing the changes in detail will be committed ASAP.

Running update-workspaces is needed after this change.

Fixes #1756.
Fixes #930, #1259, #2908, #2960, #3097
Refs #1200, #1914, #1942, #2568, #2132, #2563

[Itms]

This ticket is still relevant, to a lesser extend. The repathing attempts are currently reduced a lot thanks to the hierarchical pathfinder checking the accessibility before computing the paths.

However, the unit motion still tries to repath sometimes and there is a bit of optimization/code enhancement work to do.

[fsincos]

The attached patch should reduce excessive swarming. It's based on selecting the end point according to h²+4g instead of h * (this expression stems from minimum size of obstacles and Archimedic (linear) spirals). *: h = heuristic dist. to goal, g = length of the traversed path

You can test it e.g. in the huge combat demo by sending 200 units on one point (without engaging combat). Without the patch, roughly 80 units will stop and the rest will swarm around. With it, (almost) everyone will stop.

There remains a lot to do however:

• Units will still check for a path every turn, so it doesn't do that much for performance. Units could get "timed out" if they don't move when they aren't on their goal, which would solve this.
• The patch causes some issues with units "being lazy" in some special arrangements. A better "metric" would certainly help here.
• In the above "proof of concept" situation, units will continue to walk in place (!). This is not only very creepy, it's also a bug.

[Stan]

Don't know if this have been checked or not, in doubt I put it in the RFC queue

[wraitii]

I believe #4327 would make this mostly irrelevant, as fewer units will be stuck. In general trying less often is a lot of code for little real improvements (we don't have that many stuck units in the new pathfinder and all) so I'm closing this as invalid.

Furthermore, this is a unit motion bug landmine, having tried before.