Short/Vertex Pathfinder Rewrite

[historic_bruno]

The short pathfinder is currently very inefficient, in situations where many units are moving close together (combat) it lags badly. The current design is not scalable. Performance will be the main criteria here, but also the behavior must be sensible in the context of 0 A.D. It must integrate nicely with the new long pathfinder (#1756). In particular we want to avoid pathing mismatches between pathfinders like we have currently (see #881). For possible direction, see this forum post: http://www.wildfiregames.com/forum/index.php?showtopic=13042&st=40#entry216735 [More info to come]

[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]

The short-range pathfinder is not something to be forgotten, but currently the highest priority should be given to fixing long-range bugs and unit motion bugs.

Also it probably won't be necessary to do a complete rewriting on the short pathfinder like we did for the long one, a thorough optimization work might be enough.

[wraitii]

There have been a variety of changes to UnitMotion to alleviate issues with the short-range pathfinder recently, but there are still some.

Generally speaking, we use the short-range pathfinder to handle unit obstructions, which the long-range doesn't see. However, in quite a few cases, this is simply to go around a unit in our path. In this situation, units "pushing" each other away might be a better, simpler, fix. We probably still need the short-range pathfinder for situations where units will run in a wall of other entities, for example a woman vs a wall of elephant, as it would just look silly, imo, for the woman to push the elephants.

However the short-range pathfinder scales very very very badly. It first has to get all obstructions in the area, then constructs their vector representation (passable vertices and view-blocking edges) then sorts a bunch of things then A* on those vertices. But at the same time it must compute a visibility graph of all these vertices. That last operation is dreadfully slow when there are enough obstructions, and it is basically O(N^N) where N is the number of vertices.

We need to optimize everything in this, from how many obstructions are actually checked (we can probably trivially eliminate a lot of them, or add them on demand to the system), to how visibility is computed, to A* itself possibly by returning a slightly suboptimal path.

Memory management is also an issue. Profiling indicates no particular hotspots, but about 10% of the time is spent in "free" and "new". The memory fragmentation probably hurts locality, which can't be good. Usage of isqrt64 is also quite slow (and might prevent some optimizations), see #3368. The visibility checks are anywhere between 15 and 45% of the spent time (hard to tell precisely as these functions are inlined).

[wraitii]

Attached patch, for example, trades off visibility checks for sqrt computations (!, a bit of debug code is in there).

What it does is quite similar to branch predicting: it changes A* to study only a subset of all vertexes before checking visibility (trying to choose visible and interesting vertices), and hopes for the best. If all goes well, such an approach could reduce computing times considerably. However, if we fail to find a path towards the goal, ,we have to backtrack and recompute everything, which is considerably slower. This is a lot like branch predicting in CPUs.

The algo I chose was based on distance computation, it would probably be a better idea to use something like angles to the goal and squared distance, or something. Also, the recomputation phase could be more efficient.

Another tradeoff in the above patch is memory as I had a fourth state to the open list.

In my test it does not seem to really improve performance, as we compute less visibility (about 30/40% less total, which is generally not enough) but many more distance calculations are done.

[wraitii]

Bumping to A20 and must have, this is the needed optimization: about 15/20% of a turn is spent in ComputeShortPath in MP games.

[mimo]

Not useful to bump it if nobody works on it. Put back to backlog

[fsincos]

Small optimization, removing some trivially unreachable vertices.

[fsincos]

Do a partial sort on the edgeSquares since we are mainly interested in the nearest ones.

[fsincos]

The above patches mainly deal with very crowded situations. It's entirely possible (and likely) that they will degrade performance in harmless situations slightly (not that it matters much, but I had to put that out there). I will attach pruned output from perf for a short "huge combat demo" game. Some explanations for what I did:

Clip: We can remove vertices in obstructions, but it's only done for edgeSquares since I'm lazy. The start (ID 0) and goal (ID 1) vertices are intentionally left out for obvious reasons. The first check just makes sure our "starting inside obstructions" hackery doesn't collapse upon itself. Maybe that could be removed.

partialsort: It's somewhat strange to do a full sort based on a rough heuristic (Euclidic distance to bottom-left corner) so we now do a partial sort instead. The patch is not really fleshed out / tuned at the moment.

These patches are merely intended as a stopgap measure until the rewrite (as a JPS, JPS-B or even JPS+ algorithm).

[fsincos]

Pruned (the values don't add up to 100%) perf output.

[Itms]

Hi, this looks good at first sight.

It would be better to create a new ticket for this, since this one is about a rewrite of the pathfinder (don't forget to read carefully SubmittingPatches).

Also the patches are tiny enough and could be merged.

Some comments:

• You can remove a pair of braces in Clip.patch
• You should try and use newlines and spaces to make the conditionals less wide and nicely aligned
• If the number of eight elements to sort is just heuristic, you should add a comment to say it could be tuned. If is has a geometric reason, you should also add a comment to explain it :P

Thanks for working on that. And unless you just don't want your name in the game at all, this kind of contributions is definitely enough to warrant a new entry in the credits :)

[Imarok]

Move tickets to Simulation as UI & Simulation got some sub components.