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