Trading Space for Time in Grid-Based Path Finding

Grid-based path finding is required in many games to move agents. We present an algorithm called DBA* that uses a database of pre-computed paths to reduce the time to solve search problems. When evaluated using benchmark maps from Dragon AgeTM, DBA* requires less time for search and produces less suboptimal paths than the PRA* implementation used in Dragon AgeTM.

Authors

• William Lee University of British Columbia
• Ramon Lawrence University of British Columbia

Keywords

No keywords are indexed for this paper.