Publication details

Real-Time Density-Based Crowd Simulation
Wouter G. van Toll, Atlas F. Cook IV, Roland Geraerts
Computer Animation and Virtual Worlds (CAVW), vol. 23 (1), pp. 59-69, 2012.
Full text (pdf)

Also presented at a national conference:
Realistic Crowd Simulation with Density-Based Path Planning
Wouter G. van Toll, Atlas F. Cook IV, Roland Geraerts
In ICT.OPEN 2012, ASCI track.
Received the Best Presentation Award of ASCI 2012.
Full text (pdf) - Presentation (ppt) - Poster (pdf)


Virtual characters in games and simulations often need to plan visually convincing paths through a crowded environment. This paper describes how crowd density information can be used to guide a large number of characters through a crowded environment. Crowd density information helps characters avoid congested routes that could lead to traffic jams. It also encourages characters to use a wide variety of routes to reach their destination.

Our technique measures the desirability of a route by combining distance information with crowd density information. We start by building a navigation mesh for the walkable regions in a polygonal 2D or multi-layered 3D environment. The skeleton of this navigation mesh is the medial axis. Each walkable region in the navigation mesh maintains an up-to-date density value. This density value equals the area of all characters inside a given region divided by the total area of this region. These density values are mapped onto the medial axis to form a weighted graph. An A* search on this graph yields a backbone path for each character, and forces are used to guide the characters through the weighted environment. The characters periodically replan their routes as the density values are updated. Our experiments show that we can compute congestion-avoiding paths for tens of thousands of characters in real-time.

BibTeX citation

    author = {van Toll, W.G. and {Cook IV}, A.F. and Geraerts, R.},
    title = {Real-time density-based crowd simulation},
    journal = {Computer Animation and Virtual Worlds},
    volume = {23},
    number = {1},
    pages = {59--69},
    year = {2012}

More information

Additional information can be found on the research page of Roland Geraerts.