Cache paths

[dvaosta]

I've spent some time reading both this document and the code, and it seems that paths found by the long pathfinder are not cached but recomputed for each unit.

Now, I think a cache can significantly improve performances, especially in the cases where you select a bunch of units that are close to each other and you order them to move to a point that's quite far: in these cases, the units tend to converge on a single line, so why to compute the path for each of them?

So my proposal is to keep a cache of N paths (the most recent? The most frequently used? FIFO?); when a unit needs a path, we first search if in the cache there is already a path with the same target and a starting point that is less than X tiles away from the unit and we use the short range pathfinder to join that path (on which waypoint?), after having checked that that path can be reached, of course.

Possible improvements:

• Reuse a cached path also if the end point in less than X tiles from the unit target (and there are not better cached paths);
• Reuse part of a path also if the unit position and target are near to intermediate waypoints of the cached path (here the difficult part is to efficiently search if a point is contained in a path);

What do you think?

[Lion.Kanzen]

@elexis

[vladislavbelov]

2 minutes ago, dvaosta said:

I've spent some time reading both this document and the code, and it seems that paths found by the long pathfinder are not cached but recomputed for each unit.

Now, I think a cache can significantly improve performances, especially in the cases where you select a bunch of units that are close to each other and you order them to move to a point that's quite far: in these cases, the units tend to converge on a single line, so why to compute the path for each of them?

So my proposal is to keep a cache of N paths (the most recent? The most frequently used? FIFO?); when a unit needs a path, we first search if in the cache there is already a path with the same target and a starting point that is less than X tiles away from the unit and we use the short range pathfinder to join that path (on which waypoint?), after having checked that that path can be reached, of course.

Possible improvements:

• Reuse a cached path also if the end point in less than X tiles from the unit target (and there are not better cached paths);
• Reuse part of a path also if the unit position and target are near to intermediate waypoints of the cached path (here the difficult part is to efficiently search if a point is contained in a path);

What do you think?

Cache could be good. What we need to do when paths and/or obstructions are changing often, i.e. on a battlefield we always correct paths. Won't it add a visible overhead?

[dvaosta]

15 minutes ago, vladislavbelov said:

Cache could be good. What we need to do when paths and/or obstructions are changing often, i.e. on a battlefield we always correct paths. Won't it add a visible overhead?

For fast changing obstructions, the short range pathfinder is used (the long range one simply ignore other units). Regarding newly added buildings, I don't know if there are cases where the long range path is recomputed, but in the majority of cases also there the short range pathfinder is used to avoid them.

I don't think that use something like a FIFO cache would be a problem. In fact, also when a unit move along a very long path, that path remain valid for a long time (and in the meanwhile several new obstructions can be placed).

[vladislavbelov]

1 minute ago, dvaosta said:

For fast changing obstructions, the short range pathfinder is used (the long range one simply ignore other units). Regarding newly added buildings, I don't know if there are cases where the long range path is recomputed, but in the majority of cases also there the short range pathfinder is used to avoid them.

I don't think that use something like a FIFO cache would be a problem. In fact, also when a unit move along a very long path, that path remain valid for a long time (and in the meanwhile several new obstructions can be placed).

Then I think we could not the whole path caching, but patch version. Currently terrain is split on patches. So if any path goes through a patch we could cache it in this patch. Why not the whole path, because usually one piece of a path was changed and many paths have a common subpath.

Not sure, just ideas.

[Stan`]

@Itms might have more insight since he wrote parts with @sanderd17 @kanetaka @wraitii and @Ykkrosh

[elexis]

1 hour ago, dvaosta said:

Regarding newly added buildings, I don't know if there are cases where the long range path is recomputed, but in the majority of cases also there the short range pathfinder is used to avoid them.

The passability grid changes if someone constructs or destroys buildings (or if the water rises, or if one paints terrain with atlas or by other means).

Maybe existing paths aren't outdated, but new paths are computed with the new grid, right?

So the cache would have to be cleared if the grid changes, right?

Also we use A+ which computes the shortest path, couldn't the cache only be used in case where source and target position are identical to what's in the cache? Approximations can fail, for example if 2 units are close together but one is trapped on a mountain.

[dvaosta]

1 minute ago, elexis said:

The passability grid changes if someone constructs or destroys buildings (or if the water rises, or if one paints terrain with atlas or by other means).

Maybe existing paths aren't outdated, but new paths are computed with the new grid, right?

So the cache would have to be cleared if the grid changes, right?

Yes.

Quote

Also we use A+ which computes the shortest path, couldn't the cache only be used in case where source and target position are identical to what's in the cache? Approximations can fail, for example if 2 units are close together but one is trapped on a mountain.

This is why I wrote that we have to check if the path can be reached from the current unit position. Obviously you can reuse a path only if the starting point is few tiles (2? 3? 4?) away from the unit and the target is far enough, otherwise the resulting path may be too different from the optimal one.

[elexis]

So we end up computing a path to test if we can avoid computing a path? Might still be faster because the test path is shorter.

[bb_]

Not exactly computing a new path, since the hierarchical pathfinder has the reachable areas stored, so the only thing to check is if the realTarget and the pathTarget are in the same reachable area (and that is fairly cheap).

[dvaosta]

Moreover, to join the path I propose to use the short range pathfinder (AKA vertex pathfinder), and CCmpPathfinder::ComputeShortPath takes as one of the parameters a maximum range, so if the unit is unable to reach the path with few "steps", it just give up and compute another long path.

For example, suppose that you cache only paths longer than 50 tiles, and you allow to reuse a cached path only units that are max 3 tiles away from the starting point. You can call the short pathfinder with a range of 3-4 tiles, so if there are small obstructions the unit avoid them, but it doesn't walk for kilometers to join the path when there are large obstructions (walls, etc.).