Updates

Please subscribe to our news feed to receive the latest information:
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

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.

• 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):

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.