Geometric and Discrete Path Planning for Interactive Virtual Worlds


Geometric and Discrete Path Planning for Interactive Virtual Worlds

Wednesday, 27 July, 9:00 am - 10:30 am, Anaheim Convention Center, Room 304 AB

Path planning and navigation are indispensable components for controlling autonomous agents in interactive virtual worlds and in several types of video games. Due to the growing demands on the size and complexity of modern virtual worlds, a number of techniques have been developed for achieving intelligent navigation for the next generation of interactive multi-agent simulations.

This course reviews the evolution of the several related techniques, starting from classical planning and computational geometry techniques, and then gradually moving toward more advanced topics with a focus on recent developments. Topics range from discrete search and geometric representations to planning under different types of constraints and harnessing the power of graphics hardware in order to address Euclidean shortest paths and discrete search for multiple agents under limited time budgets. The use of planning algorithms beyond path planning is also discussed in the areas of crowd animation and whole-body motion planning for virtual characters.

The course was first offered at SIGGRAPH 2014. For this new version, complete course notes are available as a book recently published by the instructors.




Working knowledge of the fundamentals of algorithm analysis and development of interactive computer graphics systems.

Intended Audience

Game AI developers and researchers in computer animation and autonomous agents, and researchers interested in path planning.


Marcelo Kallmann
University of California, Merced

Mubbasir Kapadia
Rutgers University