Invalidate flow field cache entry when cost field changes

[heinezen]

Required Skills: C++

Difficulty: Easy

The openage pathfinder uses flow fields to search for a path on the pathfinding grids (please read the documentation to familiarize yourself with the concepts). To avoid unnecessary computations, fields are cached and reused for similar paths.

Currently, flow fields in the cache never get invalidated or updated when the costs of cells on the grid change, so these changes are never reflected in path requests when using the cached fields. This also means that dynamic changes to the grid are also not possible at the moment which is a huge downsight. A dynamic grid is required for a lot of gameplay features (e.g. placing buildings, change in terrain), so cache invalidation should be implement as soon as possible.

The easiest way to address this issue is to mark sectors/cost fields that have changed as "dirty" and then evict and recompute the flow fields for them when a new path is requested.

To try out the current pathfinder, check out pathfinding demo 1 by running the following command:

./run test -d pathfinding.tests.path_demo 1

Tasks:

• Add a way to mark the CostField as dirty. The easiest way to do this is to use a bool flag but you can also use the openage::time::time_t type to record the time of the last change.
• Add a method is_dirty(..) to CostField and Sector that checks if the cost field or sector are dirty at the specified time.
• Check if the sector is dirty before looking up a cached field in the Integrator class. If it is dirty, the cached value should be evicted and recomputed.
• (optional; Difficulty: medium) Implement the cache as a separate class FieldCache to make the code a bit more structured.

Further Reading

• Pathfinder documentation
• openage::path pathfinding module

[heinezen]

Depends on #1656

[anupriyakkumari]

Hi, I'd like to take this up.

[heinezen]

@anupriyakkumari Hey, no problem go ahead :)

[yukirine]

Hey, I'd like to help with this too !

[heinezen]

@yukirine I don't think @anupriyakkumari has done anything with the issue yet, so you can just implement it I think ^^

[anupriyakkumari]

Hi, yes. I've been busy and haven't had the time to work on this just yet. Someone else can surely take it up.