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

Real-Time Path Planning in Heterogeneous Environments

A path (gray) in a forest (green) with obstacle trees (black), puddles (blue), fallen trees (brown) and a spot with a panoramic view (light gray). Two characters (adult and child) follow automatically computed indicative routes (solid and dashed black). The smoothed paths (solid red for the adult, dashed red for the child) are computed with our MIRAN method. Both the indicative routes and the paths are based on the characters' terrain preferences. The adult avoids puddles and fallen trees, and is attracted to the spot with the panoramic view. The child prefers to walk through puddles, climbs over the trees and is not interested in the panoramic view.


Modern virtual environments can contain a variety of characters and traversable regions. Each character may have different preferences for the traversable region types. Pedestrians may prefer to walk on sidewalks, but they may occasionally need to traverse roads and dirt paths. By contrast, wild animals might try to stay in forest areas, but they are able to leave their protective environment when necessary.

This paper presents a novel path planning method named MIRAN (Modified Indicative Routes and Navigation) that takes a character's region preferences into account. Given an indicative route as a rough estimation of a character's preferred route, MIRAN efficiently computes a visually convincing path that is smooth, keeps clearance from obstacles, avoids unnecessary detours, and allows local changes to avoid other characters. To the best of our knowledge, MIRAN is the first path planning method that supports the above features while using an exact representation of the navigable space.

Experiments show that with our approach a wide range of different character behaviors can be simulated. It also overcomes problems that occur in previous path planning methods. The resulting paths are well-suited for real-time simulations and gaming applications.


  • Norman S. Jaklin, Atlas F. Cook IV and Roland Geraerts. Real-Time Path Planning in Heterogeneous Environments. Computer Animation and Virtual Worlds (CAVW), 24(3):285-295, 2013.

    Full text Presentation
  • Norman S. Jaklin, Atlas F. Cook IV and Roland Geraerts. Stay off the lawn! Creating smooth paths based on region preferences. ICT.OPEN 2013 (ICT.OPEN 2013).

    poster poster pptx