Pathfinding II: Region-Level Navigation
- kevinmeergans
- Oct 5
- 3 min read
With basic pathfinding set up and working reliably on my designated road network, I started to focus on scaling up my solution to a potentially massive world. As hinted at in earlier posts, I did this by using a hierarchical pathfinding approach and introducing the concept of interconnected regions that make up the world. This way, when a character is trying to get from one side of the world to the other, he doesn’t need to calculate the entire detailed path start to finish (which could be quite expensive and time-consuming) but instead:
Quickly calculate a rough region-level path from the region he is currently in to the region where the destination is located, so he knows which regions he needs to pass through.
Calculate the detailed path from his current position only to the best-suited region exit that leads to the next region in the region-level path.
Each time the character enters a new region, calculate the detailed path to the next exit until the final goal region is reached.
Once in the goal region, calculate the detailed path from the entry point to the final destination.
As preparation, I extended my test environment by creating multiple small regions with connections between them. I also added a region ID to the data associated with each pathfinding node, shared by all nodes within the same region. To make this clearer during testing, I introduced color coding based on these region IDs, which helped me to quickly confirm that borders were set up correctly.
In order to efficiently use the region-level graph at runtime, I needed to generate the underlying data and precalculate certain values. I added an additional step to the existing pathfinding data asset export to handle this.
The first step was to go through all nodes in the network and find the pairs of nodes that form connections across region borders (different region IDs). Both nodes are added as region nodes, keeping their connection intact while also connecting them to all other region nodes with the same ID. This effectively creates a simplified variant of the original network, made up only of region border nodes.
In a separate pass, calculate the distances between a node and all of its connected nodes within the same region. This uses the original network and my existing detailed pathfinding function. The results are stored as connection data, giving me the traversal cost from any entry/exit of a region to any other. These values can later be used to determine efficient region-level paths. It would also make sense to cache all fastest paths between region nodes to avoid recalculating them at runtime, though I haven’t implemented this yet. Have a look at the two images below for a better understanding of the difference between the original network and the derived region graph.
Following the approach outlined earlier, the system can now calculate the best region-level path using the steps below. To speed this up, I extended my A* implementation with multi-goal support, allowing it to find the shortest routes from one start node to multiple destinations:
Calculate detailed paths from the start node to every exit of the start region.
Calculate detailed paths from the goal node to every entry into the target region.
Calculate region-level paths from each exit of the start region to each entry of the goal region.
Find the combination with the minimal total cost for all three parts. This gives us the best-suited start region exit, the region-level nodes to follow along, and finally the most efficient path to the goal.
This may sound like a lot, but because the region-level graph is fairly coarse, calculations remain fast. There’s still room for improvement, such as caching intra-region paths or optimizing the detailed partial paths for start and goal positions (for example, by accepting near-optimal paths with a good heuristic). I’ll revisit this once the game world has taken more shape.
The interplay between the existing Pathfinding and PathFollower components on my NPCs was adjusted as well to support partial paths. The Pathfinding component now stores both the region path and the current detailed partial path, and provides the latter to the PathFollower. The PathFollower then triggers an event to let the Pathfinding component know when it should calculate and provide the next detailed path segment.
With region-level pathfinding complete, there’s one major piece left to finish my navigation system: the cell-based pathfinding that will allow NPCs to walk off-road and navigate areas not covered by the road network. I’ll cover that in the next post.