Precompute portal node graph in high-level pathfinder

[heinezen]

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

[jere8184]

I would like to take on this issue.

[jere8184]

So portal_a_star generates a path of portals right to get you from "source tile" to "dest tile", So we want to precompute these paths if I'm understanding correctly, would we precomompute these paths on a per tile basis i.e. calculate the portal path from every "source tile" to every "dest tile"?

[heinezen]

So portal_a_star generates a path of portals right to get you from "source tile" to "dest tile",

Not exactly. The portals only connect sectors on the grid (a sector may be 10x10 tiles for example), so it will rather find a sector path from the "source sector" to "destination sector". Therefore, portal_a_star also only computes a high-level path that consists of the sectors that are visited. The tile-based search happens at a later stage using a different method.

So we want to precompute these paths if I'm understanding correctly, would we precomompute these paths on a per tile basis i.e. calculate the portal path from every "source tile" to every "dest tile"?

I'm not sure if I'm misunderstanding you, but the task is not about precomputing any paths. What we want to precompute is the portal node graph, i.e. the connections between all the portals between sectors on the grid. This
graph will then be searched in portal_a_star using A* to find a sector path as mentioned above.

[heinezen]

I should also mention that if you work on this, please branch from this PR #1656

[heinezen]

Solved by #1708

[jere8184]

@heinezen For the optional task, I think I would have to change the way the graph's weights are calculated. Currently, when calculating the distance between two portal nodes, we are taking the physical distance. I guess this would have to change. Maybe flow_field way points could be used to calculate a more accurate distance that takes into account the path travelled.

[heinezen]

@jere8184 I think I would group the optional task with a new issue to make the grid dynamic, which would include quite a few other changes. We would have to check what distance changes are still performant on a dynamic grid. We could always calculate the exact distance using flood-fill (i.e. also recording the distance to each portal, when we find the portal connections). However, this may be expensive to run during a gameplay session.