Publication details

Navigation for Characters and Crowds in Complex Virtual Environments
Wouter van Toll
PhD Thesis (Utrecht University, The Netherlands).
ISBN 978-90-393-6711-7. Defended on March 30, 2017.
Full text (pdf, 33.6 MB) - Compressed version (pdf, 9.4 MB) - UU digital repository (external)


In a crowd simulation, virtual walking characters need to compute and traverse paths through a virtual environment while avoiding collisions. Simulations of large crowds occur increasingly often in computer games, in which real-time performance is required. Also, there is an increasing demand for crowd simulations of real-world scenarios. For example, crowd simulations can be used to predict dangerous situations during crowded events such as festivals, or to estimate if a sports stadium can be evacuated within a certain amount of time.

Thus, path planning and crowd simulation are important research topics. Part I of this gives an overview of these topics and related work. A navigation mesh is an efficient representation of a virtual environment for the purpose of real-time path planning and crowd simulation. When planning a path in a navigation mesh, we actually compute a sequence of regions for the character to move through. Within these regions, the character can compute an indicative route, which it can then follow in real-time while avoiding other moving characters.

The rest of this thesis investigates how to use navigation meshes to model and simulate complex scenarios. Part II of this thesis revolves around the navigation mesh itself. It describes:

In Part III of this thesis, we develop new methods for path planning and crowd simulation in navigation meshes:

Part IV concludes that these algorithms and implementations can be used to efficiently simulate increasingly complex scenarios. The most important topics for future work are the automatic extraction of a multi-layered environment from raw 3D geometry, the extension of characters with sophisticated AI without losing efficiency, and the evaluation of how well a crowd simulation corresponds to real-world behavior.

BibTeX citation

    author = {van Toll, W.G.},
    title = {Navigation for Characters and Crowds in Complex Virtual Environments},
    school = {Utrecht University},
    year = {2017},
    isbn = {978-90-393-6711-7}