Record history of cost changes in pathfinder

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

Start with libopenage/pathfinding/cost_field.h, then read the pathfinder and curves documentation to understand how CostField changes are applied and how curve data is stored. Run ./run test -d pathfinding.tests.path_demo 1 to observe the current pathfinder. Done means changed cell costs are recorded separately from current values and can support returning to an earlier grid state.