Nathan Sturtevant

Pathfinding: HOG | Multi-Player Games : Hearts, Spades

Pathfinding is a key task in robotics and games. Pathfinding systems need to be flexible and fast. They are often used to assist in a variety of tasks, including terrain analysis. Most efficient pathfinding systems are based on some type of abstraction mechanism.

Pathfinding for Commercial Games

Commercial games generally have tight memory and processing budgets, and so solutions for this space require careful management of these resources. In parts of 2006-07 I worked with BioWare to implement a pathfinding engine for their upcoming game Dragon Age. This system included a system that incremently computes paths during travel, avoiding delays in movement. The people at BioWare have done a great job extending this engine, and I'm looking forward to seeing the final game. This is a prototype shot of the abstraction from a test level in the game.

More details can be found in the slides for a talk given after completing part of the implementation for BioWare. A full description of the methods used can also be found in AI Wisdom 4.

Cooperative Pathfinding

I have been working on explicit and implicit cooperation during pathfinding with my master's student Renee Jansen, as well as with Michael Buro. Renee has done some nice work on getting units to pathfind together without paying the expense of fully-cooperative algorithms. (Movies will be posted here soon.)

Abstraction in Pathfinding and Search

I have collaborated with several other researchers in better understanding the role that abstraction plays in pathfinding and search. This has included a theoretical analysis of abstraction mechanisms, of the suboptimality that can be induced when using abstraction, as well as practical algorithms which use abstraction to great effect.


HOG is a research testbed which includes components for running pathfinding simulations, as well as many different abstraction techniques. HOG is freely available and has been used by a wide variety of researchers. HOG is not currently being updated, as a more general search framework is being developed which will support a larger set of domains and techniques.

Pathfinding-Related Publications