Indicative Routes for Path Planning and Crowd Simulation

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

Reference
Ioannis Karamouzas, Roland Geraerts and Mark Overmars.
Indicative Routes for Path Planning and Crowd Simulation.
In International Conference on the Foundations of Digital Games (FDG09), pp. 113-120, 2009.
Full text: [pdf] Presentation: [ppt;wmv]

An indicative route is given as input.    The route is retracted onto the medial axis and its corresponding corridor is computed.    The final smooth path is computed by using a simple force model.
Indicative route
Retraction and corridor
Final path
Movies
City Environment 2D    City Environment 3D
City Environment 2D [avi] [wmv]
City Environment 3D [avi] [wmv]

The Indicative Route Method (IRM)
The Indicative Route Method (IRM) in action.
The Indicative Route Method (IRM) in action [irm.wrl]

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.