Trading Space for Time in Grid-Based Path Finding

Authors

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

DOI:

https://doi.org/10.1609/aaai.v27i1.8528

Keywords:

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

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™.

AAAI 2013 Proceedings Cover

Downloads

Published

2013-06-29

How to Cite

Lee, W., & Lawrence, R. (2013). Trading Space for Time in Grid-Based Path Finding. Proceedings of the AAAI Conference on Artificial Intelligence, 27(1), 1625-1626. https://doi.org/10.1609/aaai.v27i1.8528

Issue

Vol. 27 No. 1 (2013): Twenty-Seventh AAAI Conference on Artificial Intelligence

Section

Pre-PhD Student Abstracts