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

Indicative Routes for Path Planning and Crowd Simulation

An indicative route guides the agents towards the goal, resulting in a customized, smooth path.


An important challenge in virtual environment applications is to steer virtual characters through complex and dynamic worlds. The characters should be able to plan their paths and move toward their desired locations, avoiding at the same time collisions with the environment and with other moving entities. In this paper we propose a general method for realistic path planning, the Indicative Route Method (IRM). In the irm, a so-called indicative route determines a global route for the character, whereas a corridor around this route is used to handle a broad range of other path planning issues, such as avoiding characters and computing smooth paths. As we will show, our method can be used for real-time navigation of many moving characters in complicated environments. It is fast, flexible and generates believable paths.


  • Ioannis Karamouzas, Roland Geraerts and Mark Overmars. Indicative Routes for Path Planning and Crowd Simulation. In The Fourth International Conference on the Foundations of Digital Games (FDG'09) , pp. 113-120, 2009.

    pdf pptx

Our follow up reseach can be found here where characters consider weighted terrain types (instead of homogeneous terrains), and where the amount of smooting (i.e. looking ahead) can be controlled.

The Indicative Route Method

The IRM generates the smooth (green) path based on a given indicative route. In this example, we took a shortest minimum-clearance path computed by the technique described here. Based on the character's current position (blue disk), its closest point on the corridor's boundaries (black disk) is computed. This information is used to compute the retracted point r on the medial axis (red disk). We then take the last intersection point on the indicative route (black disk) with a maximum empty disk placed on r. This point is the next attraction point for the character, forming a potential field (visualized as arrows in the last part of the animation). The character moves in that direction and the process repeats until the goal is reached.

Animation of the Indicative Route Method (IRM).