Required Skills: C++

Difficulty: Easy

In the openage pathfinder, a portal node graph is used in the first stage of the search to find the sectors the path travels through using an A* search algorithm. Currently, this node graph is created dynamically on every path request to the pathfinder which takes a significant amount of time. Since the node graph only changes very infrequently (i.e. only if the portals change), we can theoretically create it once on the first path request and then reuse it on subsequent requests.

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:

• Implement a dedicated method that creates the portal node graph(s). Currently, the graph is created in Pathfinder::portal_a_star. Note that there may be multiple pathfinding grids and each of them creates a differ ent node graph.
• Store the portal node graph(s) where they can be accessed when computing new paths. The Grid class should be a good candidate.
• Change Pathfinder::portal_a_star in such a way that it uses the precomputed portal node graph.
• (optional) Use callgrind to compare the speed of the old implementation with your solution that uses precomputed graphs.

valgrind --tool=callgrind ./run test -d pathfinding.tests.path_demo 1

• (optional; Difficulty: medium) Recompute the portal node graph when the portals have changed. This can happen when a CostField on the grid gets changed.

Further Reading

• Pathfinder documentation
• openage::path pathfinding module