Caching for pathfinding

[kostmo]

To improve the performance of #836, a caching mechanism could be designed that optimizes for the common case: a robot repeatedly invokes path with identical arguments and follows the yielded directions precisely.

1. If the robot takes a step off of the optimal path, the computed path shall be invalidated.
2. If the robot invokes the path command again with different arguments, the previous computed path shall be discarded.
3. If the list of entities that are unwalkable for the invoking robot changes, invalidate the cache.
4. Map modifications
   1. If an entity is added or removed at a Manhattan distance farther from the robot than the computed path length, the cache is unaffected.
   2. "unwalkable" entities (an entity is placed or removed that is "unwalkable" with respect to the invoking robot)
      1. If an "unwalkable" entity is added to the map, the computed path shall only be invalidated if the new entity lies on the path.
      2. If an "unwalkable" entity is removed from the map, the computed path shall be invalidated.
   3. "target" entities (if the path command had been invoked with the modified entity as a target)
      1. Adding
         1. If a target entity is added that lies on the computed path, the computed path is truncated to that entity's location
         2. If a target entity is added that does not lie on the computed path, invalidate the cache
      2. Removing
         1. If a target entity is removed that is the destination of the computed path, invalidate the cache
         2. If a target entity is removed that is not the destination of the computed path, the cache is unaffected

[byorgey]

This sounds nice in theory but it seems like it might be premature optimization. I am worried that the logic to invalidate the cache would be more expensive than just recomputing a path every time.

• Would there be just a single global cached path? Or one per robot?
• One per robot would make the most logical sense (after all, two robots could be simultaneously following different paths), but I worry about keeping those updated. If the map is modified, do you then have to scan through every robot to see whether any of them have a cached path that needs to be invalidated? That would obviously be disastrous for performance.
• Alternatively, instead of invalidating cached paths directly, we could simply keep a log of world changes, and have the path command itself be responsible for checking whether the cached path needs to be invalidated. But that sounds complicated, especially since we'd have to make sure the "world changes log" is somehow windowed so it doesn't grow without bound.

[xsebek]

Well, how would we determine if the optimisations are premature? I am not sure we are using the path enough yet to make a good decision. But once we do, could we use the new counters to count path queries/etc. @kostmo?

I am also interested in the simple alternatives, like keeping the original path and letting robots recalculate if they need to.

[xsebek]

It would be cool if we could update the shortest distance cache of A* directly and let it recompute the result.

My hope is that the path metric of the algorithm would itself determine if the update is relevant. Most of your points still apply @kostmo, but I was considering if we could avoid throwing out all the work.

[kostmo]

Well, how would we determine if the optimisations are premature? I am not sure we are using the path enough yet to make a good decision.

I've created a demo in #1594 where I think the kind of caching I describe here would help a lot.
When the robot clears a patch of flowers such that the next one is far away, the game stutters heavily as the lengthy path is recalculated upon every tick.

Other than the stuttering issue, the emergent roaming/grazing behavior is quite fun to observe and could feature in various scenarios.

[kostmo]

#1595 implements caching and demonstrates a dramatic improvement to the roaming/grazing performance.

[xsebek]

@kostmo great, but isn't that measured against turning off an on navigation for each turn? 🤔

Also how is everything else affected? 😅