Towards Believable Crowds: A Generic Multi-Level Framework for Agent Navigation

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