Record history of cost changes in pathfinder

[heinezen]

Required Skills: C++

Difficulty: Hard

At the moment, changes to the movement cost of cells in the openage pathfinder always overwrite the old values. The old values are not saved anywhere, so going back to a previous state of the grid is currently not possible. Ideally, the grid should support going back in time, so we can roll back changes e.g. for multiplayer matches.

openage already provides the curve data types for storing values over time, so changes could be recorded using the same methods. An array curve (see #1678) would probably be the best option for storing values for a grid.

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 cost record storage for cells to the CostField implementation. The cost record should use curve. For performance reasons, the recorded values should be stored separately from the current cost values (so not in the cells vector).
• Record the changed cost whenever a modifying operation occurs for CostField, e.g. setting a cell value.

Further Reading

• Pathfinder documentation
• Curves documentation
• openage::path pathfinding module

[jere8184]

We would need to know the size of cost field at compile time right if we want to give it a curve::Array ? template it?

[heinezen]

The size of the fields will be fixed at compile time later on by enforcing a fixee terrain chunk size. Currently it's 10x10