Transcript Indicative Routes for Path Planning and Crowd Simulation

Indicative Routes for Path Planning and
Crowd Simulation
Ioannis Karamouzas, Roland Geraerts, Mark Overmars
Path Planning
What is path planning
• Steer character from A to B
Computer games and path planning
• Fast and flexible
– Real-time planning for thousands of characters
– Flexibility to avoid other characters and local hazards
– Individuals and groups
• Natural Paths
–
–
–
–
–
–
Smooth
Collision-free
Short
Keep a preferred amount of clearance from obstacles
Flexible
…..
Path Planning
Maintain suspense of disbelief
• Realistic graphics and physics
• Still though, the path choices that characters make are poor
Errors in Path Planning
Existing Algorithms
Grid-based A* Algorithms
• Computational expensive
• Aesthetically unpleasant paths
Waypoint graphs
• Hand designed
• Do not adapt to changes in the
environment
Navigation Meshes
• Automatic construction is slow
• Paths need to be smoothed
Existing Algorithms
Local Methods
• Flocking [Reynolds, 1987 & 1999],
• Helbing’s Social Force Model [Helbing
et al, 2000]
• Reactive style planners
Local methods fail to find a route
• Suffer from local minima problems
• Lead to repeated motion
The Indicative Route Method
In real life, people
• Do not plan an exact path, but
• A preferred/desired global route
A path planning algorithm should produce:
• An Indicative Route
– Guides character to its goal
• A corridor
– Allows for flexibility
The Indicative Route Method
The IRM method in action:
• A collision-free indicative route determines the character’s
preferred route
• A corridor around this route defines the walkable area for
the character
• A smooth path is generated using a force-field approach
Computing Corridors
The Corridor Map
• Introduced by [Geraerts and Overmars, 2007]
• Provides a system of collision-free corridors
• Corridor: sequence of maximum clearance disks
The Corridor Map is computed as follows:
• The Generalized Voronoi Diagram is approximated using GPU [Hoff et al,
1999]
• Clearance + additional info is stored
3D Environment
Skeleton of the map
Corridor
Computing Corridors
Computing the Corridor Map
• Only required during preprocessing
• Very fast (50 ms, NVIDIA GeForce 8800 GTX)
Compute a corridor
• Retract the indicative route to the
Generalized Voronoi Diagram
• Find corresponding path in diagram
• Use clearance information as a
representation of the corridor
Local Navigation in IRM
Boundary force
• Find closest point on corridor boundary
• Increases to infinity when close to boundary
• 0 when clearance is large enough (or when on GVD)
Steering force
• An attraction point moves along the indicative route
• Attracts the character with a constant steering force
Noise force
• Create variation in paths
• Perlin noise is used
Local Navigation in IRM
Collision Avoidance Force
• Avoid collision with other characters and moving entities
• Helbing’s model can be used
• Additional models can be easily incorporated
Obtain the final path
• Force leads to an acceleration term
• Integration over time, update velocity/position/attraction
point
• Results in a smooth (C1-continuous) path
IRM method
Resulting vector field
• Indicative Route is the medial axis
Creating Indicative Routes
Use the Generalized Voronoi Diagram
• Retract start and goal
• Find shortest path (using A*)
• The corridor is obtained immediately
Use a network of Indicative Routes
• Created by level designer
• Voronoi-Visibility Complex [Wein et al, 2005]
A* on coarse grid
• Additional information can be incorporated
– For example flow into account
– Use the notion of Influence Regions
Crowd Simulation
Method can plan paths of a large number of characters
• Goal oriented behavior
– Each character has its own long term goal
– When a character reaches its goal, a new goal is chosen
• Wandering behavior
– Attraction points do a random walk on the indicative network
Experiments
• Goal-oriented behavior
• Simulation ran for 1000 steps
• Each step calculates 0.1s of simulation time
Crowd Simulation - Experiments
Test Environment
City environment
2D footprint (640 ms)
Crowd Simulation - Experiments
Performance
• 2.4 GHz Intel Core2 Duo, 2 GB memory
• One CPU core used
• 3000 characters, CPU usage 26%, FPS 33
Average simulation time per frame
CPU Load
0.07
60
0.06
sec / frame
CPU Load %
50
40
30
20
0.05
0.04
0.03
0.02
10
0.01
0
0
0
1000
2000
3000
Number of characters
4000
5000
0
1000
2000
3000
Number of characters
4000
5000
Crowd Simulation – Video
Current Research
Global behavior
• Incorporating influence regions
• Types of behavior (shopping, tourists, …)
Further improving the local methods
• Take mood and personality into account
• Dealing with small groups
Observing and modeling paths of real
humans
• Motion capture data
• Tracking pedestrians
Evaluation of the results
Project’s Website
• http://people.cs.uu.nl/ioannis/irm