Biter Path Cache

[darklich14]

What does the number mean to the right of the path cache coordinate? I see the matching color at the surface coordinate shown in the path cache, but the numbers are huge on some of those. Way too long to simply be the length of the path, unless it's getting in a loop somewhere and backtracking on itself for hundreds of thousands of tiles. Is it the length of the path multiplied by the entities trying to use the cached path?

Screenshot from 2019-05-13 10-22-07.png (2.67 MiB) Viewed 1639 times

[Oxyd]

It is the current cost of the record in the cache, as used by the GreedyDual cache replacement policy. The initial cost when a path is inserted into the cache is the total number of tiles visited by the A* algorithm – that is, the size of the open and closed sets.

[darklich14]

After briefly skimming the GreedyDual concept, is that to say the larger the number for the path, the more expensive it would be to reevaluate it? So it's not that it inherently costs more to keep the path around - it would just be more of a hit to have to reevaluate it?

[Oxyd]

GreedyDual tries to balance the cost of finding the path and the usefulness of keeping the path cached. So if you have a path that was really expensive to find, but it doesn't get any hits, its cost will keep decreasing until it gets dropped out of the cache. Meanwhile, if another path is being retrieved from the cache regularly, its cost is reset to the cost it took to find it each time it's retrieved, so it's kept in the cache.

[darklich14]

I see, Thank you for the clarification. In any case, it seems for game performance's sake, a large number would suggest it be good to go destroy the biters which are keeping that path alive.

[Oxyd]

Only in the sense that it would make room in the cache for one more path. A path in the cache doesn't consume any CPU. Then again, having fewer biters is always better for performance.

[darklich14]

I usually see the value numbers in the thousands, tens of thousands sometimes, but i feel like values in the 100s of thousands are not very common. Low hanging fruit for cleaning up. The biters on that path are gone and the number is falling.