Opened 11 years ago

Last modified 5 years ago

#1942 new enhancement

Short/Vertex Pathfinder Rewrite

Reported by: historic_bruno Owned by:
Priority: Must Have Milestone: Backlog
Component: Simulation Keywords: pathfinding
Cc: Patch:

Description (last modified by fsincos)

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: [More info to come]

Attachments (4)

short-range_otp.patch (5.7 KB ) - added by wraitii 9 years ago.
Clip.patch (1.3 KB ) - added by fsincos 8 years ago.
Small optimization, removing some trivially unreachable vertices.
partialsort.patch (827 bytes ) - added by fsincos 8 years ago.
Do a partial sort on the edgeSquares since we are mainly interested in the nearest ones.
perf.hist.pruned (15.2 KB ) - added by fsincos 8 years ago.
Pruned (the values don't add up to 100%) perf output.

Download all attachments as: .zip

Change History (16)

comment:1 by historic_bruno, 11 years ago

Description: modified (diff)

comment:2 by Itms, 9 years ago

Keywords: pathfinding added

comment:3 by Itms, 9 years ago

Milestone: BacklogAlpha 19

comment:4 by Itms, 9 years ago

In 16751:

New long-range pathfinder.

Based on Philip's work located at;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

comment:5 by Itms, 9 years ago

Milestone: Alpha 19Backlog
Priority: Must HaveShould Have

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.

comment:6 by wraitii, 9 years ago

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).

by wraitii, 9 years ago

Attachment: short-range_otp.patch added

comment:7 by wraitii, 9 years ago

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.

Last edited 9 years ago by wraitii (previous) (diff)

comment:8 by wraitii, 9 years ago

Component: Core engineUI & Simulation
Milestone: BacklogAlpha 20
Priority: Should HaveMust Have

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

comment:9 by mimo, 8 years ago

Milestone: Alpha 20Backlog

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

by fsincos, 8 years ago

Attachment: Clip.patch added

Small optimization, removing some trivially unreachable vertices.

by fsincos, 8 years ago

Attachment: partialsort.patch added

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

comment:10 by fsincos, 8 years ago

Description: modified (diff)
Keywords: review added

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).

by fsincos, 8 years ago

Attachment: perf.hist.pruned added

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

comment:11 by Itms, 8 years ago

Keywords: review removed

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 :)

comment:12 by Imarok, 5 years ago

Component: UI & SimulationSimulation

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

Note: See TracTickets for help on using tickets.