SIGGRAPH 2014 Course Notes- This is the manuscript produced by the authors. Navigation Meshes and Real-Time Dynamic Planning for Virtual Worlds

Path planning and navigation play a significant role in simulated virtual environments and computer games. Computing collision-free paths, addressing clearance, and designing dynamic represen-tations and re-planning strategies are examples of important prob-lems with roots in computational geometry and discrete artificial intelligence search methods, and which are being re-visited with innovative new perspectives from researchers in computer graphics and animation. This course provides an overview of navigation structures and al-gorithms for achieving real-time dynamic navigation for the next generation of multi-agent simulations and virtual worlds. Building on top of classical techniques in computational geometry and dis-crete search, we review recent developments in real-time planning and discrete environment representations for the efficient and ro-bust computation of paths addressing different constraints in large, complex, and dynamic environments