Trading Space for Time in Grid-Based Path Finding

William Lee; Ramon Lawrence

AAAI Publications, Twenty-Seventh AAAI Conference on Artificial Intelligence

William Lee, Ramon Lawrence

Last modified: 2013-06-29

Abstract

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 Age™, DBA* requires less time for search and produces less suboptimal paths than the PRA* implementation used in Dragon Age™.

Keywords

path finding ; search ; games ; database ; real-time

Full Text: PDF