“Geometric and Discrete Path Planning for Interactive Virtual Worlds” by Kapadia

  • ©Mubbasir Kapadia



Entry Number: 21


    Geometric and Discrete Path Planning for Interactive Virtual Worlds

Course Organizer(s):



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


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

    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.

ACM Digital Library Publication:

Overview Page: