SFTtech/openage

Record history of cost changes in pathfinder

Open

#1,680 opened on Aug 25, 2024

View on GitHub
 (4 comments) (0 reactions) (0 assignees)Python (12,130 stars) (1,135 forks)batch import
area: simulationgood first issuelang: c++nice new thing ☺

Description

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

Contributor guide

Tech stack
cpp
Domain
backenddataperformance
Issue type
feature
DifficultyEstimated implementation difficulty for a new contributor, from 1 for very small changes to 5 for expert-level work.
5
Estimated timeA rough time range for an experienced contributor to investigate, implement, test, and prepare a pull request.
3-5 days
Activity statusHow available the issue appears right now: fresh, active, stale, blocked, or waiting on maintainer input.
fresh
ClarityHow clearly the issue explains the expected change, acceptance criteria, and next step.
clear
Prerequisites
C++ programmingcurve data typesopenage pathfinding module
Newbie friendlinessA 1-100 score estimating how approachable this issue is for first-time contributors.
15
Research direction
Start by reading the curve documentation (doc/code/curves.md) and the pathfinding documentation (doc/code/pathfinding/README.md). Then examine the current CostField implementation in libopenage/pathfinding/cost field.h and cost field.cpp to understand how cells are stored. Review issue #1678 for the array curve proposal. The goal is to add a separate cost history storage using curves, recording changes when cell values are modified. See the comments in the issue for any additional discussion.