Homepage > Crowd simulation > List of publications > Paper

We study how we can automatically create a data structure that represents the walkable surfaces in such an environment, and how it can be updated dynamically and efficiently when it changes. We refer to this structure as a navigation mesh. This mesh enables efficient crowd simulation, which is our next topic of research. We study and develop a crowd simulation framework and its components, which ranges from global (AI) planning to local animation. We create models for realistic crowd behaviors, which includes studying how (groups of) people move and avoid collisions in such environments, based on agent profiles and semantics (such as terrain annotations).

A Generic Multi-Level Framework for Agent Navigation

A five-level hierarchy for path planning and crowd simulation systems.

A five-level hierarchy for path planning and crowd simulation systems. The geometric levels, which can be solved using our algorithms and software, require an efficient navigation mesh of the environment.

Abstract

Path planning and crowd simulation are important computational tasks in computer games and applications of high social relevance, such as crowd management and safety training. Virtual characters (agents) need to autonomously find a path from their current position to a designated goal position. This is usually solved by running the A* algorithm on a grid or a navigation mesh. However, in many modern applications, strictly traversing the resulting path is not sufficient. Agents need to be able to deviate from these paths, e.g. to avoid each other or react to dynamic changes in the environment. Multiple levels of planning are necessary to efficiently simulate realistic behavior, and the underlying data structures and algorithms should support those levels. Many existing crowd simulation frameworks do not have this flexibility.

In this paper, we propose a five-level hierarchy for agent navigation in virtual environments. The five levels are high-level planning, global route planning, route following, local movement, and animation. The three center levels concern geometric planning and require a navigation mesh that represents the navigable space of the environment. We describe an efficient and flexible navigation mesh for 2D and multi-layered 3D environments. We also present our crowd simulation software that uses this mesh; we outline its architecture and show that the framework is easily extendible. Finally, we show that our software can simulate large autonomous crowds in real-time.

References

  • Wouter G. van Toll, Norman S. Jaklin and, Roland Geraerts. A Generic Multi-Level Framework for Agent Navigation. Poster at 8th International ACM SIGGRAPH Conference on Motion in Games, 2015 (Paris, France / Lisbon, Portugal).

  • Wouter G. van Toll, Norman S. Jaklin and, Roland Geraerts. Towards Believable Crowds: A Generic Multi-Level Framework for Agent Navigation. In ICT.OPEN 2015 (ICT.OPEN 2015).
    This paper has received the best presentation award as well as the best poster award ASCI 2015.
    Our ICT.OPEN 'meet the demo' presentation has received an honorable mention (top 3 out of 40 demo's) by NWO.

    Full text Poster Presentation

  • Wouter G. van Toll, Atlas F. Cook IV, Marc J. van Kreveld and Roland Geraerts. The Explicit Corridor Map: Using the Medial Axis for Real-Time Path Planning and Crowd Simulation. In International Computational Geometry Multimedia Exposition, Symposium on Computational Geometry 2016. SoCG 2016, 70:1-70:5, Boston, USA, 2016.

    pdf Path planning demo

Software

Our Explicit Corridor Map (ECM) Crowd Simulation Framework creates high-quality navigation meshes and uses them for path planning and crowd simulation. More information can be read on the software page.