Computer Science Colloquium: Nathan Sturtevant

The Pathfinding Engine of Dragon Age: Origins

Abstract: What does it take to build a high-quality pathfinding engine? One might think that pathfinding in games is a simple case of using A*, which finds shortest paths. But, in practice, there are many other considerations for finding high-quality paths quickly in dynamic environments. This talk will give an overview of the techniques required to build the pathfinding engine of Dragon Age: Origins. Five iterations of improvements will be presented, starting from basic pathfinding approaches, and moving to a final system that creates high-quality, smooth paths. To conclude, we will discuss open challenges in pathfinding and what it would take to create a pathfinding system that finds human-quality paths.

Speaker Bio: Nathan Sturtevant is an Associate Professor in the Computer Science Department at the University of Denver. His scientific research focuses on search in Artificial Intelligence. This includes work on heuristic and combinatorial search for single and multiple agents, including bidirectional search, automated abstraction, heuristics, refinement search, search for game design, heuristic learning, inconsistent heuristics, cooperative search, large-scale and parallel search.
Particular applications include pathfinding and planning in memory-constrained real-time environments (e.g. commercial video games) as well as algorithms for building and using memory-based heuristics via large-scale search. Other work considers theoretical and practical issues in games with more than two players, including opponent modeling, learning, and imperfect information.

Export event as iCal