Pathfinding I: Navigating the Graph

I outlined my general pathfinding approach in the previous blog post, but here’s a quick recap before diving into specifics: I’m using a hierarchical approach to pathfinding to reduce and better distribute the computation cost of finding a route in a potentially massive grid-based open world. While actors can navigate the world on a cell-by-cell basis, they can also use a predefined graph, resembling a road network, for longer, well-traveled routes. In addition, the world will be split into regions to further segment path calculations. This post covers the general pathfinding setup and how actors make use of the road network. Follow-up posts will describe how I extended the approach to handle region-level navigation and fine-grained cell-by-cell pathfinding on the grid.

The first step was ensuring that the graph data created in the editor would be available at runtime. I added an export function to my graph tool that saves the created nodes and connections to a data asset. At the start of the game, this data is loaded by a custom pathfinding subsystem, which acts as a central provider for all pathfinding functionality.

The subsystem exposes a function for requesting a path, which takes a start and end point plus a delegate to call with the result once it has been computed. For each pathfinding request, the subsystem creates an AsyncTask and passes it the provided arguments along with read access to the graph data. The AsyncTask then runs the actual pathfinding logic and calls back with an array of grid positions. Using background tasks in this way allows the system to handle multiple requests concurrently.

The pathfinding algorithms themselves are grouped as static functions in a separate class so they can be easily swapped or modified without touching the rest of the system. This keeps the AsyncTask implementation minimal and clean. For now, I’m using the trusty A* algorithm with Manhattan Distance as the heuristic, but I may experiment with alternatives and optimizations once I have a working draft of the full game world and can measure performance in a real scenario.

With the subsystem and algorithms ready, I needed a way for pawns to request and follow the generated paths. To keep things modular, I created two new actor components rather than extending my existing movement component. The new dedicated Pathfinding component handles pathfinding requests by relaying them to the subsystem, and waiting for the callback with the path result. Once received, it forwards the path to the second component, a PathFollower. The PathFollower is responsible for moving the pawn along the path by adjusting the movement direction input of my existing movement component. It checks regularly whether the pawn has reached the next waypoint and, if so, updates the movement direction toward the following waypoint, continuing until the destination is reached. This keeps the movement component “dumb” so it can be reused for both player and NPC movement.

Pawn navigating the node graph