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 https://github.com/SFTtech/openage/pull/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.

[dmwever]

I have mostly finished a preliminary draft of this task, including separating out a FieldCache class. It is my first work with c++, but if you're good with me opening a pull request that may need a good bit of revision, I can push it on my lunch break or later today.

I still need to get a test set up properly as well. If you'd like to see that before I even bother with pushing, let me know.

[dmwever]

I took the approach of passing in an optional clear_cache flag as a parameter (defaulting to false) into the functions that access the FieldCache inside the integrator. This might not be the best way to do it.

I chose to use the openage::time::time_t class to force myself to understand it, as I hope to move to the history issue next, which uses curves. A FieldCost is marked as dirty if the latest change has happened AFTER the time_t parameter.

[heinezen]

@dmwever Yeah don't worry, you can just open a merge request and improve it along the way. Actually, if you want early feedback it's even better to publish it early as a draft.