mm_spacer

Updates

Please subscribe to our news feed to receive the latest information: XML/RSS feed HTML feed
Last update: 3 July 2011.

General information

The seminar Crowd Simulation is given as a part of the GMT Master program at the Utrecht University. The course is given in the 4th period on Tuesday (13.15-15.00) in BBL-069 and Friday (15.15-17.00) in BBL-071.

Course overview

In computer games and virtual environments many characters move around. Such characters have to plan their paths to move from one location to another. These paths must avoid collisions with the environment and with other characters. Also it is important that these paths are natural, that is, the characters must move around in ways similar to real people in real crowds. In this seminar we will study a number of the recent results on path planning and crowd simulation, and how they can be applied in computer games.

Schedule

Week Date Topic Paper Speaker Deadline
 17 April 26 Introduction 0 Roland Geraerts Read paper 0
  April 29 Path planning 1, (2), 3 Roland Geraerts Abstracts
 18 May 3 Path planning errors   Everyone Assignment 1
  May 6 No seminar      
 19 May 10 No seminar      
  May 13 Path planning 4, 5 Emre, Gwen Abstracts
 20 May 17 Path planning 6, 7 Bart, Walter Abstracts
  May 20 Social force models 8, 10 Rudi, Robin Abstracts
 21 May 24 Social force models (SFM) 13 Jessica Abstracts
  May 27 SFM/Flow 12, 14 Emre, Gwen Abstracts
 22 May 31 No seminar      
  June 3 No seminar      
 23 June 7 Flow 16, 17 Bart, Walter Abstracts
  June 10 Flow, Crowds 18, 19 Rudi, Robin Abstracts
 24 June 14 Crowds 20, 21 Jessica, Emre Abstracts
  June 17 Behavior 22, 23 Gwen, Bart Abstracts
 25 June 21 Behavior, Massive crowds 24, 26 Walter, Rudi Abstracts
  June 24 No seminar      
 26 June 28 Evaluation 30, 31 Robin, Jessica Abstracts
  July 1 No seminar     Assignment 2

Assignments

In the zeroth assignment, you have to read an introduction paper to grasp some preliminaries on motion planning (read it before April 26th). To develop some insights about current problems and challenges in the field of path planning, you will be studying a game in the first assignment. Next, you have to write a short document for each paper that will be discussed. Each student will discuss three papers which will be assigned on April 26. At the end of the seminar, you have to create and hand in a paper on how some interesting problems can be solved.

Assignment 1

In the first assignment you have to collect some footage from a game in which path planning or crowd simulation issues went dramatically wrong. These issues include the quality of motion, occurrence of collisions, repeated motions, reaction on dynamic changes, groups of characters, etcetera. Such issues sometimes reveal themselves when you deliberately try to create `problems'. For example, stand in the way of moving characters, park a car on the sideways, move to difficult camera positions, or destroy an object or building. While some examples can be found on the web (see for example this overview, or the results from last year), you need to create the footage yourself. You can use e.g. Fraps to capture a relevant part. (Please convert the result to a `standard' format like wmf to ensure that your movie can be played.) If the capturing fails you could use a (web/photo/film) camera to record a clip. Next, take a representative picture of it and put it, together with a short discussion of what went wrong and how it could be fixed, onto three PowerPoint slides. The movie and slides must be handed in on May 3 at the start of the meeting where they will be discussed. You'll present and discuss your results during 5 - 7.5 minutes.

The resulting movies and presentations can be found here.

Abstracts

For each paper presentation (starting at April 29), except for your own presentations, you have to write a 1 page document including a short summary (at most half a page) in your own words (and don’t forget to include a few lines on the experiments). Next --and this is the part where you can score valuable points-- you need to spent a few paragraphs on a critical assessment of the paper, i.e. include some challenges, shortcomings, surprising and innovative elements. Don't forget to include a few lines on some frequently occurring `errors', e.g. many authors claim too much, make many assumptions, draw conclusions that are too general, don't setup their experiments correctly, etcetera. Finally, include a few (e.g. 3) relevant questions you can ask during the presentation. To ease the grading process, please include the following headings: Summary, Assessment, Questions. A printed copy must be handed in at the end of the presentation.

For the second half of the papers, you only need to spend 5-10 lines of text on the Summary. In addition, spend at least half a page on the assessment. Now that you've read more than half of all papers, it's easier to put your paper in the right perspectives. Besides the mentioned points, you could also take a look at this paper (and in particular Section 4), which provides some additional reviewing criteria.

Assignment 2

The goal of the second assignment is to write a document on how the techniques that you have seen during the seminar can be used to solve path planning and crowd simulation problems in actual games. In the first assignment you have all created videos of problems with path planning in games.

From these we have selected the following interesting issue:
  • Heterogeneous crowds. Consider the movies of e.g. Gwen and Robin. It seems that the crowd is managed by only one or a few simple behaviors. In future games, the crowd will be much more heterogeneous. For instance, some characters might wander around, some have their own long term goals, and others just might go with the flow when it is crowded. The most papers we have seen during the seminar concentrate on only one of such elements (and on one type of entity such as humans, monsters, cars, etc.). Give an extensive list of possible behaviors that could facilitate such a heterogeneous crowd and describe a crowd simulation system that can deal with such a diversity. Can we just combine the current techniques/papers to achieve the desired effect (if yes, how?) or do we need more techniques (which ones)? What data structure could we use to efficiently facilitate the simulation?

You need to write a 10-page document describing how an heterogeneous crowd can be simulated. You should write the paper as if it was meant as a recommendation for the programmer of the game. So it should have enough details to convince the programmer that this is a good idea and that he should investigate the approach further. Explain the problems you observe, give a global description of the techniques you suggest for improvement, and indicate why you think they would solve the problem. Give references to the papers from which you have taken the techniques. In your writing assume that the reader has a good knowledge of computer science but no knowledge of the techniques discussed in the seminar. Try to be as critical on your own paper as you were on the paper you have reviewed. This paper must be mailed to Roland preferably before or on July 1 at 17.00. Since this is a strict deadline, make sure you start in time.

Presentations of research papers

Each student will be assigned three research papers which have to be presented. A PC and projector will be present. When you are preparing your presentation, do it in such a way that people who don't know the paper (but have a computer science background) still can follow your presentation. So, explain the global idea, algorithms and definitions clearly and give some examples. Also, try to give the intuition/motivation behind the formulas you show (e.g. decompose the formula and explain each term and create a picture which clarifies the formula, or use the blackboard). Next, do not put too much text on your slides (i.e. at most 7 lines of text) and include a picture. If you are displaying charts or tables, please explain all axes, legend, etc. You are of course free to steal additional information (such as movies and java applets) from the Internet to make your point. Please also consider related or future work (i.e. work that refers to your paper). Try to speak for about 25-30 minutes (10 minutes is really too short). The remainder (15-20 minutes) should be used for discussions. Finally, a high grade can be obtained if you are very critical about the paper and put it in the right perspectives with other research papers.

The following papers are discussed (tentative; will be fit on the number of participants):

# Topic Title Author(s)
0 Introduction Motion Planning L.E. Kavraki and S.M. LaValle
1 Path planning The corridor map method: a general framework for real-time high-quality path planning R. Geraerts and M.H. Overmars
2   Enhancing Corridor Maps for Real-Time Path Planning in Virtual Environments (background material; making an abstract is not required.) R. Geraerts and M.H. Overmars
3   Planning Short Paths with Clearance using Explicit Corridors [more info] R. Geraerts
4   Probabilistic Roadmaps for Path Planning in High-Dimensional Configuration Spaces
More info; paper analyzes the PRM:
Reachability-based analysis for Probabilistic Roadmap planners
L.E. Kavraki et al
5   RRT-connect: An efficient approach to single-query path planning
More info: LaValle's website
J.J. Kuffner and S.M. LaValle
6   Finding Paths for Coherent Groups using Clearance
More info: taxonomy, PhD thesis on formations
A. Kamphuis and M.H. Overmars
7   Indicative Routes for Path Planning and Crowd Simulation [more info] I. Karamouzas et al
8 Social force models Steering Behaviors For Autonomous Characters C.W. Reynolds
9   Social Potential Fields A Distributed Behavioral Control for Autonomous Robots J.H. Reif and H. Wang
10   Social force model for pedestrian dynamics D. Helbing and P. Molnar
11   A Physically-Based Particle Model of Emergent Crowd Behaviors L. Heïgeas et al
12   Controlling Individual Agents in High-Density Crowd Simulation N. Pelechano et al
13   A Predictive Collision Avoidance Model for Pedestrian Simulation [movie] I. Karamouzas and M. Overmars
14 Flow Flow Tiles S. Chenney
15   The Flow of Human Crowds R.L. Hughes
16   Controlling the movement of crowds in computer graphics by using the mechanism of particle swarm optimization Y.P. Chen and Y.Y. Lin
17   Continuum Crowds A. Treuille et al
18   Directing Crowd Simulations Using Navigation Fields S. Patil et al
19 Crowds Real-time Navigation of Independent Agents Using Adaptive Roadmaps A. Sud et al
20   Real-time crowd motion planning: Scalable Avoidance and Group Behavior B. Yersin et al
21   Crowd Patches: Populating Large-Scale Virtual Environments for Real-Time Applications B. Yersin et al
22 Behavior Scalable Behaviors for Crowd Simulation M. Sung et al
23   Hierarchical Model for Real Time Simulation of Virtual Human Crowds S.R. Musse and D. Thalmann
24   Composite Agents H. Yeh et al
25   Intuitive Crowd Behaviour in Sense Urban Environments using Local Laws C. Loscos et al
26 Massive crowds Aggregate Dynamics for Dense Crowd Simulation R. Narain et al
27   The Virtual Marathon: Parallel Computing Supports Crowd Simulations E. Yilmaz et al
28 GPU techniques Multi Agent Navigation on the GPU A. Bleiweiss
29   GPU Accelerated Path-planning for Multi-agents in Virtual Environments L.G. Fischer
30 Evaluation Data Driven Evaluation of Crowds A. Lerner et al
31   SteerBench: a benchmark suite for evaluating steering behaviors S. Singh et al
32 Rendering Survey of Real-Time Rendering Techniques for Crowds G. Ryder and A.M. Day
33   Visualizing Crowds in Real-Time F. Tecchia et al

Grading

There will be no exam but grading will depend on the quality of the given presentations (10%+10%+20%), the first assignment (5%), the second assignment (25%), abstracts (20%), and the active participation in the meetings (10%). To qualify for second change exam the original mark should at least be a 4. Also you must actively participate in at least 75% of the meetings and give both presentations satisfactory.

The grades can be found here.

Teacher

For additional information about the seminar, please contact Roland Geraerts.

A visually convincing path inside a virtual environment with a large green ball.