Pathfinding in Computer Games


Nathan Sturtevant
Renee Jansen
Michael Buro
Rob Holte
Jonathan Schaeffer
Markus Enzenberger
Vadim Bulitko
Shanny Lu
Russ Greiner

Former Members

Mitja Lustrek
Sverrir Sigmundarson
Timothy Yau
Alejandro Isaza
Chris Rayner
Csaba Szepesvari
Ken Anderson
Kate Davison
Greg Lee
Alborz Geramifard
Pirooz Chubak
Douglas Deymon
Adi Botea
Peter Yap
Yngvi Björnsson


Mitja Lustrek and Vadim Bulitko
Thinking Too Much: Pathology in Pathfinding
The 18th European Conference on Artificial Intelligence (ECAI)
Patras, Greece, 2008

Alejandro Isaza, Csaba Szepesvári, Vadim Bulitko and Russell Greiner
Speeding Up Planning in Markov Decision Processes via Automatically Constructed Abstractions
The 24th Conference on Uncertainty in Artificial Intelligence (UAI)
Helsinki, Finland, 2008

Vadim Bulitko, Mitja Lušrek, Jonathan Schaeffer, Yngvi Björnsson and Sverrir Sigmundarson
Dynamic Control in Real-Time Heuristic Search
Journal of Artificial Intelligence Research (JAIR), Vol 32, 419-452, 2008

Alejandro Isaza, Jieshan Lu, Vadim Bulitko and Russell Greiner
A Cover-Based Approach to Multi-Agent Moving Target Pursuit
The Fourth Conference on Artificial Intelligence and Interactive Digital Entertainment (AIIDE)
Stanford, California, 2008

Vadim Bulitko, Nathan Sturtevant, Jieshan Lu and Timothy Yau
Graph Abstraction in Real-time Heuristic Search
Journal of Artificial Intelligence Research (JAIR), Vol 30, 51-100, 2007

D. Chris Rayner, Katherine Davison, Vadim Bulitko, Kenneth Anderson and Jieshan Lu
Real-Time Heuristic Search with a Priority Queue
Proceedings of the International Joint Conference on Artificial Intelligence (IJCAI), 2372-2377
Hyderabad, India, 2007

Alborz Geramifard, Pirooz Chubak and Vadim Bulitko
Biased Cost Pathfinding
Proceedings of the Artificial Intelligence and Interactive Digital Entertainment conference (AIIDE), 112-114
Marina del Rey, California, 2006

Vadim Bulitko and Greg Lee
Learning in Real Time Search: A Unifying Framework
Journal of Artificial Intelligence Research (JAIR), Vol 25, 119-157, 2006

Vadim Bulitko and Mitja Luvstrek
Lookahead Pathology in Real-Time Path-Finding
Proceedings of the National Conference on Artificial Intelligence (AAAI), AAAI Member Abstracts and Posters
Boston, Massachusetts, 2006

Nathan Sturtevant and Michael Buro
Improving Collaborative Pathfinding Using Map Abstraction
AIIDE, Marina del Rey, CA, 2006.

Douglas Demyen and Michael Buro
Efficient Triangulation-Based Pathfinding
AAAI, Boston 2006

Nathan Sturtevant and Michael Buro
Partial Pathfinding Using Map Abstraction and Refinement
AAAI, Pittsburgh, 2005.

Y. Björnsson, M. Enzenberger, R. Holte, and J. Schaeffer.
Fringe Search: Beating A* at Pathfinding on Game Maps.
IEEE Symposium on Computational Intelligence and Games, Essex, 2005.

A. Botea, M. Müller, and J. Schaeffer
Near Optimal Hierarchical Path-finding.
In Journal of Game Development, volume 1, issue 1, 2004.

Y. Björnsson, M. Enzenberger, R. Holte, J. Schaeffer, and P. Yap.
Comparison of Different Abstractions for Pathfinding on Maps.
International Joint Conference on Artificial Intelligence (IJCAI'03), 2003.

P. Yap.
Grid-based Pathfinding.
In proceedings of 15th Canadian Conference on Artificial Intelligence, Calgary, 2002.

P. Yap.
New Ideas in Pathfinding.
In proceedings of AAAI Spring Symposium: Artificial Intelligence and Interactive Entertainment, pp 95-97, Stanford, 2002.

P. Yap and J. Schaeffer.
Path-finding on a Grid.
In proceedings of 5th Joint Conference of Information Sciences (JCIS 2002), pp 454-457, Durham, 2002.


HOG is a pathfinding testbed with OpenGL visualization.

Pathfinding library

The pathfinding library is a testbed for running experiments with pathfinding algorithms with emphasis on environments found in computer games.


Version Date File Documentation
0.1.0 2003-08-07 Download View


HPA* is a software package for hierarchical path-finding. The model behind HPA* is described and evaluated in the paper "Near Optimal Hierarchical Path-Finding" listed above.
Download HPA*