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 The Fourth International Conference on the Foundations of Digital Games (FDG'09) , pp. 113-120, 2009.
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.
