Transcript Introduction

Seminar Crowd Simulation
Introduction
1
Who am I?
 Roland Geraerts
 Assistant professor
 Robotics background
 Research on path planning and
crowd simulation
2
Who are you?
 Master GMTE?
 Course Game Design?
 Course Motion and Manipulation?
 Interest in Games?
 Why do you follow the seminar?
 Interest in thesis projects?
 Who has exciting hobbies?
3
Goal of the seminar
 To obtain knowledge of current research in path planning
and crowd simulation
 Study and discuss papers
 To understand the limitations of the current techniques
 Determine the limitations and open problems in the papers
 To become a very critical reader
 Hand in many assessments of papers
 To understand the state-of-the-art in current games and
how this could be improved
 Study path planning in existing games
 Write paper about the applicability of new techniques
4
Why this seminar
 Path planning and crowd simulation are important research
topics in Utrecht
 Mark Overmars, Roland Geraerts, Frank van der Stappen,
PhD students (Ioannis Karamouzas, Saskia Groenewegen)
 Relation to animation research
 Gate project
 19 million Euro Dutch project
on game technology and
applications
 Thesis projects
 Future PhD positions
5
Practical aspects
 Meetings
 Tuesday 13.15-15.00 BBL-069
 Friday 15.15-17.00 BBL-071
 Presence is mandatory
 If you cannot come for a good reason
• Let me know beforehand
• Hand in abstracts before meeting
 Website
 http://www.cs.uu.nl/docs/vakken/mcrs/
 Check regularly for announcements and changes
 Download papers
 Find the secret page
6
Assignments
 Present two papers
 Each 30 minutes plus 15 minutes discussion
 Write paper abstracts/assessments
 Read papers before the presentation
 One page per paper
• Abstract in your own words
• Critical assessment
– Main limitations and open problems
– Surprising and innovative elements
– Do the authors claim too much, make many assumptions, draw
conclusions that are too general, not correctly setup their experiments?
• Two-three questions or points for discussion
 Hand in the two pages (on paper) on the day of the
presentation
• Use headings: Summary, Assessment, Questions
7
Assignments
 Study path planning in a modern game
 Investigate what goes wrong (path planning, crowds)
 Make a video (.wmv to make sure it works)
 Make 3 slides
 Bring them with you next Tuesday (May 3) for discussion
 Paper on path planning/crowd simulation in games
 At the end of the seminar (July 1)
 Write a paper (10 pages) on how the new techniques can be
used in games
 Based on the problems in two example videos
8
Grading
 Game study




5%
Presentations
15% + 25%
Abstracts
20%
Paper
25%
Active participation 10%
 To qualify for second change exam
 The original mark should at least be a 4;
 Actively participate in at least 75% of the meetings;
 Give both presentations satisfactory.
9
Tentative schedule
Week
Date
Topic
Speaker
Deadline
17
April 26
Introduction
Roland
Paper 0
April 29
Overview path planning research
Roland
Abstracts
May 3
Current problems in games
Students
Assignment 1
May 6
No seminar
May 10
Path planning
Students
Abstracts
May 13
Path planning
Students
Abstracts
May 17
Social force models
Students
Abstracts
May 20
Social force models
Students
Abstracts
May 24
Social force models
Students
Abstracts
May 27
Flow
Students
Abstracts
May 31
No seminar
June 3
No seminar
June 7
Flow
Students
Abstracts
June 10
Crowds
Students
Abstracts
June 14
Crowds
Students
Abstracts
June 17
Behavior
Students
Abstracts
June 21
Massive crowds
Students
Abstracts
June 24
No seminar?
June 28
Crowd evaluation
Students
Abstracts
July 1
Rendering/GPU techniques
Students
Assignment 2
18
19
20
21
22
23
24
25
26
10
Path planning
 Goal: bring characters (or a camera) from A to B
 Also vehicles, animals, camera, …
 Requirement: fast and flexible
 Real-time planning for thousands of characters
 Individuals and groups
 Dealing with local hazards
 Different types of environments
 Requirement: visually convincing paths
 The way humans move
 Smooth
 Short
 Keep some distance (clearance) to obstacles
 Avoid other characters
 …
13
Do we need a new path planning algorithm?
14
typical differences
Robotics
Games
Nr. entities
Nr. DOFs
CPU time
Interaction
Type path
Environment
Algorithms
Correctness
a few robots
many DOFs
much time available
anti-social
nice path
2D (or terrain), 3D
can be simple
fool-proof
many characters
a few DOFs
little time available
social
visually convincing path
2D, 2.5D (e.g. bridges)
must be simple
may be incorrect
Path planning algorithms in games
 Networks of waypoints
 Scripting
 Grid-based A* Algorithms
 Navigation meshes
 Local approaches
 Flocking
 Cheating
15
Errors in path planning
16
Errors in path planning
 Networks of waypoints are incorrect
 Hand designed
 Do not adapt to changes in the environment
 Do not adapt to the type of character
 Local methods fail to find a route
 Keep stuck behind objects
 Lead to repeated motion
 Groups split up
 Not planned as a coherent entity
 Paths are unnatural
 Not smooth
 Stay too close to network/obstacles
 Methodology is not general enough to handle all problems
17
What we study in the seminar
 Methodology/framework that solved these problems
 Developed in Utrecht (still in development)
 Applications (characters, cameras, groups, crowds, …)
 Local character behavior
 How do people walk toward locations
 How do they avoid each other
 Social force models
 Crowd behavior
 Flow models
 Planning approaches
 Crowd evaluation
 Massive crowds
 Crowd rendering
18
The Explicit Corridor Map:
Full/generic representation free space
 The Explicit Corridor Map
 Navigation mesh, or: a system of collision-free corridors
 Data structure: Medial axis + closest points
 Computed efficiently by using the GPU
Explicit Corridor Map (2D)
19
Explicit Corridor Map (multi-layered)
The Explicit Corridor Map:
Experiments
City environment
20
Footprint and Explicit Corridor Map: 0.3s
Corridors (macro scale)
 Computing a corridor: provides a global route Connect the
start and goal to the Medial axis
 Find corresponding shortest path in graph
 Corridor: concatenation of cells of the ECM
Corridor
21
A corridor with small obstacles
The Indicative Route Method (meso scale):
Introducing flexibility
 A path planning algorithm should NOT compute a path
 A one-dimensional path limits the character’s freedom
 Humans don’t do that either
 It should produce
 An Indicative/Preferred Route
• Guides character to goal
 A corridor
• Provides a global
(homotopic) route
• Allows for flexibility
22
The Indicative Route Method (meso scale):
Introducing flexibility
 “Algorithm”
 Compute a collision free indicative route from A to B
 Compute a corridor containing the route
 Move an attraction point along the indicative route
• The attraction point attracts the character
• The boundary of the corridor pushes it away
• Other characters and local hazards push the character away
23
Local method (micro scale)
 Boundary force
 Find closest point on corridor boundary
 Perpendicular to boundary
 Increases to infinity when closer to boundary
 Force is 0 when clearance is large enough (or when on the MA)
• Depends on the maximal speed of the character
• Should be chosen such as to avoid oscillations
 Steering force
 Towards attraction point
 Can be constant
 Obtain path
 Force leads to an acceleration term
 Integration over time,
update velocity/position/attraction point
 Yields a smooth (C1-continuous) path
24
IRM method
 Resulting vector field
 Indicative Route is short path
25
IRM method:
Experiments
City environment
26
Corridor and path: 2.8ms
Crowd simulation
 Method can plan paths for a large number of characters
 Force model is used for local avoidance
 Path variation models are integrated,
adding more realism
 Additional models can be
incorporated easily
 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 underlying graph
27
Collision-avoidance model
 Particle-based approaches
 E.g. Helbing model
 When characters get close to each other they push each other
away
 Force depends on the distance between their personal spaces
and whether they can see each other
 Disadvantages
 Reaction is late
 Also reaction when no collision
 Artifacts
Goal force
Avoidance force
Resulting force
28
Improved collision-avoidance model
 Collision-predication approach
 When characters are on collision course we compute the
positions at impact (of personal spaces)
 Direction depends on their relative position at impact
 Force depends on the distance to impact
 Care must be taken when combining forces
29
Goal force
Avoidance force
Resulting force
Improved collision-avoidance model
 Advantages
 Characters react earlier (like in real life)
 Characters choose routes that deviate only marginally from
original route (energy efficient)
 Emergent behavior, e.g. lane formation and characters
grouping
 Fast (thousands of characters in real time)
Helbing
30
Collision prediction
Improved collision-avoidance model
31
Improved collision-avoidance model
32
Current work
 Also allow speed changes
 Deal with small groups
33
Further work
 Get different types of high-level crowd behavior
 Wandering
 Shopping
 Hanging around
 …
 Combine different types of moving entities
 People
 Bikes
 Cars
 Animals
 Path planning in 3D
34
First assignment
 Study path planning/crowd simulation in a modern game
 Pick a game in which there is a lot of motion
•
•
•
•
Dynamic changes in the environment
Computer controlled characters (enemies, buddies, …)
Groups of characters (e.g. in RTS games)
Crowds (e.g. GTA, Assassin’s Creed, Sim games)
 Investigate what goes wrong
• Deliberately try to create problems
– Destroy objects/buildings
– Stand in the way of moving characters
– Park a car on the sidewalks
• Look at
– Quality of motion
– Occurrence of collisions
– Repeated motions (lack of variation), …
 Bonus points for spotting errors in 2.5D/3D games, dynamic
situations
35
First assignment
 Study path planning/crowd simulation in a modern game
 Make a video (preferably a .wmv file)
• Fraps
• Use a camera or webcam
• Sometimes in-game possible
 Make (at least) three slides in PowerPoint
• Name of the game, your name, picture, type of game
• Video(s)
• Description of the main things that go wrong and why (according
to you)
 Take with you on USB stick next Tuesday!
• Explain and discuss (5 - 7.5 minutes)
36
Some results of last year’s assignment
37