Incremental Heuristic Search in Games: The Quest for Speed


  • Maxim Likhachev Carnegie Mellon University
  • Sven Koenig University of Southern California



Robot path-planning methods can be used in real-time computer games but then need to run fast to ensure that the game characters move in real time, an issue addressed by incremental heuristic search methods. In this paper, we demon- strate how one can speed up D* Lite, an incremental heuristic search method that implements planning with the freespace assumption to move game characters in initially unknown or partially unknown terrain to given goal coordinates. We speed up D* Lite by implementing its priority queue with buckets rather than a binary heap. This non-trivial change reduces its runtime by a factor of two and effectively doubles the number of game characters that real-time computer games can afford.




How to Cite

Likhachev, M., & Koenig, S. (2021). Incremental Heuristic Search in Games: The Quest for Speed. Proceedings of the AAAI Conference on Artificial Intelligence and Interactive Digital Entertainment, 2(1), 118-120.