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.
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.
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.
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.