Cost stamps (pathfinder)

Required Skills: C++

Difficulty: Medium

Our current model of the flow field pathfinder doesn't account for temporary changes of the cost grid, e.g. a building being placed on terrain. In this example, the building would change the movement cost of the grid (making affected tiles impassable) only as long as it exists. Once it is removed, the cells should return to their original cost value (e.g. that of the underlying terrain).

For flow fields there already exists a suggested solution for this in the form of cost stamps (check out the related article). Essentially, cost stamps record the original value of the cells when they change its value. Removing a stamp restores the original value.

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 cost stamps storage for cells to the CostField implementation. For performance reasons, the stamps should be stored separately from the current cost values (so not in the cells vector). Stamps should record
  • Time of "stamping"
  • Original cell value
• Add new methods for cost stamps to CostField. You should at least implement these functions:
  • CostField::stamp(..): Place a stamp down for a specific cell
  • CostField::unstamp(..): Restore the original value for a specific cell

Further Reading

• Pathfinder documentation
• openage::path pathfinding module

Read libopenage/pathfinding/cost_field.h and the pathfinding documentation first, then run ./run test -d pathfinding.tests.path_demo 1 to inspect the current behavior. Implement separate cost-stamp storage recording each stamp's time and original cell value, with stamp and unstamp operations. Done means temporary cell costs can be restored after a stamp is removed without storing stamps in the cells vector.