Abstract
Pathfinding in modern video games requires balancing memory constraints, real-time response times, and path optimality. This paper introduces DBA, a grid-based pathfinding algorithm that utilizes a pre-computed database of paths between abstracted regions. By combining hierarchical abstraction with compressed subgoal storage, DBA achieves near-optimal results with constant-time planning bounds. Experimental results on Dragon Age: Origins maps demonstrate that DBA outperforms industry-standard algorithms like PRA in both speed and path quality while maintaining a memory footprint suitable for mobile and console platforms.
Introduction
In large-scale game environments, hundreds of agents often require simultaneous pathfinding. While A is a standard solution, its variable response times and memory usage can be problematic under strict real-time constraints. Hierarchical approaches like Partial Refinement A (PRA) improve speed but often at the cost of path optimality, typically producing paths 5% to 15% longer than the shortest route. Conversely, real-time database-driven algorithms offer constant-time guarantees but often demand excessive pre-computation and storage. DBA addresses this gap by providing a "middle ground" that is faster and more accurate than PRA* without the massive memory overhead of previous database approaches.
The DBA* Algorithm
DBA* operates in two distinct phases: an offline pre-computation stage and an online pathfinding stage.
Offline Pre-computation
The algorithm begins by dividing the grid into $n \times n$ sectors. Within each sector, "regions" are identified as sets of cells reachable from one another without leaving the sector. Optimal paths between all adjacent regions are then calculated using A*.
To minimize storage, these paths are compressed into a sequence of "subgoals." A subgoal is selected such that an agent can reach it from the previous subgoal using simple greedy "hill-climbing." Finally, a global connectivity matrix is constructed using dynamic programming. Each entry $(i, j)$ in this $R \times R$ matrix (where $R$ is the number of regions) specifies the next adjacent region an agent should enter to reach region $j$ from region $i$.
Online Pathfinding
During execution, when an agent moves from point $A$ to point $B$, it identifies its current and target regions. It then performs a simple lookup in the pre-computed matrix to find the next region and follows the stored subgoals. This lookup and hill-climbing process ensures a nearly instantaneous and constant response time for the first move.
Experimental Evaluation
The performance of DBA was evaluated using ten benchmark maps from the game Dragon Age: Origins. These maps averaged approximately 96,739 open states. DBA was compared against PRA, HCDPS, and sgLRTA (LRTA* with subgoals).
Path Quality and Speed
DBA variants consistently achieved an average suboptimality of less than 3%, significantly better than the 5–15% range typical of PRA. Furthermore, DBA demonstrated superior move times compared to both PRA and HCDPS.
Memory Efficiency
A key advantage of DBA* is its memory efficiency. By using hill-climbable subgoals, the database remains under 200 KB on average for several configurations. This makes the algorithm viable for systems with limited RAM, such as mobile devices.
Discussion and Conclusion
DBA successfully decouples sector size from performance. In hierarchical algorithms like PRA, larger sectors typically lead to significantly worse paths. In DBA*, because inter-region paths are pre-calculated optimally, increasing sector size has a minimal impact on path quality.
The primary limitation of the current approach is its reliance on static environments; changes to the map (e.g., dynamic obstacles) would require updates to the pre-computed database. Future work will focus on efficient real-time updates to the path database to accommodate dynamic grid changes. Overall, DBA* provides a robust solution for high-performance pathfinding in resource-constrained environments.
Summary updated