Cover ERCIM News 57

This issue in pdf
(72 pages; 11,6 Mb)

Archive:
Cover ERCIM News 56
previous issue:
Number 56
January 2004:
Special theme:
Analysis, Planning, Diagnosis and Simulation of Industrial Systems

all previous issues

Next issue:
July 2004

Next Special theme:
Automated Software Engineering

About ERCIM News

Valid HTML 4.01!
spacer
 
< Contents ERCIM News No. 57, April 2004
SPECIAL THEME
 

Motion Planning in Virtual Environments and Games

by Mark Overmars

In games and other virtual environments, computer-controlled entities need to move around in natural ways. They must plan their routes amidst obstacles and other moving entities. Motion-planning techniques that originate from robotics have been adapted and effectively applied in such environments.

In its simplest form, the motion-planning problem requires a collision-free path to be computed for a moving body between start and goal positions. Motion planning was traditionally studied in the area of robotics in order to plan the motion of robot arms and robot vehicles. In recent years these techniques have been increasingly used in virtual environments and games. In such applications, computer-controlled entities move around and consequently their motion must be planned. In particular, we can distinguish the following types of motion:

  • navigation: entities must find a route to a particular goal while avoiding collisions with obstacles and other entities
  • animation: the internal (often articulated) movements of the entities must be computed, and must match the navigation through the environment
  • manipulation: entities manipulate objects in the environment, whose trajectories must be computed in relation to the manipulation itself.
  • Virtual environments and games offer a challenging problem setting because of the following aspects:
  • complexity: scenes are very complex, with up to a million obstacles
  • dynamic: scenes tend to be dynamic, ie obstacles can appear or disappear (for example when opening a door or when a fire starts)
  • real time: motions must be computed in real time, since one cannot temporarily stop the entities
  • multiple degrees of freedom: a reasonably accurate structure of the human body has over a hundred degrees of freedom, and the combined motion of these must be planned
  • multiple entities: multiple entities often move in the same environment, and must avoid each other and behave as a group
  • natural motion: to give the user the feeling of immersion, the resulting motions must be natural, that is, visually convincing.

Although a lot of research has been done on motion planning, current techniques cannot adequately solve these problems.

Navigation
The traditional approach in games is to script all motion. That is, the designer creates all possible motions for the entities beforehand, and only small deviations from these paths are allowed during the game. This clearly limits the behaviour of the entities and is a lot of work on the part of the designers, who must take every potential situation into account. In some types of games, in particular real-time strategy games, this is often combined with some A* approach on a grid that is laid on top of the world. Such an approach is limited to motion in a plane and can lead to unnatural behaviour, particularly when there are multiple moving entities (see Figure 1).

Figure 1: A scene from the game Command and Conquer Generals. Five units are ordered to move to the same spot but the motion planner sends one along a different route, leading to instant death for that unit.
Figure 1: A scene from the game Command and Conquer Generals. Five units are ordered to move to the same spot but the motion planner sends one along a different route, leading to instant death for that unit.

Our approach is based on the probabilistic roadmap (PRM) technique, developed in robotics. The idea is to automatically build a roadmap of all possible motions during a preprocessing phase. Once this roadmap is available it can be queried for particular motions. Although preprocessing is relatively expensive, during the game it allows motion queries to be answered almost instantaneously, even for complex environments. The planner can then easily handle instances with many degrees of freedom, as in Figure 2.

Figure 2: A table must move from one room to another through two doors. Combined translation and rotation is required for this. Even though the problem has six degrees of freedom, solutions are computed almost instantaneously.
Figure 2: A table must move from one room to another through two doors. Combined translation and rotation is required for this. Even though the problem has six degrees of freedom, solutions are computed almost instantaneously.

We are currently extending the approach to deal with dynamic changes within scenes, and to deal with highly articulated structures. A prime challenge here is to effectively combine the internal motion of the entities (ie the motion of their arms and legs) with their external motion through the environment.

Multiple Entities
As indicated in Figure 1, a challenging problem in virtual environments and games is the simultaneous motion of multiple entities. The traditional approach for this is to use flocking techniques, combined with goal searching based, for example, on A* algorithms. The basic idea of flocking is that entities adapt their motions to each other. They try to stay close to other entities (but not too close) and align their motion to that of nearby entities. In large open areas this leads to natural behaviour, as can be observed in schools of fish or flocks of birds. When there are many obstacles however, the group tends to break up and entities follow different routes to the goal, with not all of the entities necessarily reaching it successfully.

In our work we concentrate on keeping the group of entities coherent, ensuring they stay together and follow the same route to the goal. One way we achieve this is by using a deformable rotating rectangle to model the group as a whole. We plan the motion of the deformable rectangle using the PRM approach, and then apply a form of social potential field to steer the motion of the individual entities in the rectangle. This approach results in natural group motion (see Figure 3).

Figure 3: A flock of sheep moving inside a deformable rectangle. The deformable rectangle can easily get through the hole (by getting longer) and the sheep will stay inside it.
Figure 3: A flock of sheep moving inside a deformable rectangle. The deformable rectangle can easily get through the hole (by getting longer) and the sheep will stay inside it.

The MOVIE Project
The EU Information Society Technologies project MOVIE (Motion Planning in Virtual Environments) studies the use of sophisticated motion-planning techniques in virtual environments and games, and deals with all the aspects mentioned above: real-time planning in complex, dynamic environments, entities with multiple degrees of freedom, and planning the simultaneous motion of multiple entities. The project is also looking at simple manipulation problems. Because of the application domain, the quality of the resulting motion is of crucial importance. The MOVIE project commenced in January 2003, and is a collaboration between Utrecht University in the Netherlands, Tel Aviv University in Israel, and CNRS-LAAS and the company Kineo-CAM in France.

Link:
http://www.give.nl/movie

Please contact:
Mark Overmars, Utrecht University, The Netherlands
Tel: +31 30 253 37 36
E-mail: markov@cs.uu.nl
 

spacer