Last update: 10 August 2009

The seminar Path Planning is given as a part of the GMT Master program at the Utrecht University. The course is given in the 4th period on Monday (13.15-15.00) and Thursday (11.00-12.45) in BBL-501.

Path planning plays an important role in computer games and virtual environments. Characters in such environments 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, they look similar to paths humans would take. In this seminar we will study a number of the recent results on path planning and crowd simulation.

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 two papers. At the end of the seminar, you have to create and hand in a paper on how some interesting problems can be solved.

In the first assignment you have to collect some footage from a game in which path planning issues went dramatically wrong. These issues include general path planning, crowd planning and camera planning. While some examples can be found on the web (see for example these path finding bugs or even better this overview [pdf]), you need to create the footage yourself. You can use Fraps to capture a relevant part. If that fails you could use a (web/photo/film) camera to record a piece. 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 April 23 at the start of the meeting. Your work will be discussed during this meeting.

For each paper presentation (starting at May 4), except for your own presentations, you have to write a 1 page document including a short summary in your own words, some challenges, shortcomings, suprising and innovative elements, and a few relevant questions of the paper. (For May 4, write a 2 page document). A printed copy must be handed in at the start of the presentation.

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 most interesting/relevant issues:

• Unnatural crowd movements in Warcraft III: Reign of Chaos; see Pieter’s contribution.
• Unnatural global behavior in Resident Evil 4; see Cetin’s contribution.
• Unnatural local path planning/steering in Halo; see Geerten’s contribution.

For each of these three issues you need to write a 5-page document describing how you think the problems can be solved or at least improved using the techniques that have been discussed during this seminar. (So the total document should be 15 pages in length.) 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 problems. 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.

This paper must be mailed to Roland preferrably before or on July 3 at 18.00. Since this is a strict deadline, make sure you start in time. Note that you do not need papers 23 and 24 for this assignment.

Each student will be assigned two research papers which have to be presented. A PC and projector will be present. When you're preparing your presentation, do it in such a way that people who don't know the paper (but have a computer science background) can still follow your presentation. So, explain the algorithms and definitions clearly and give some examples. Also, do not put too much text on your slides. If you are displaying charts or tables, please explain all axes, legend, etc. You're of course free to steal additional information (such as movies and java applets) from the Internet. Try to speak for about 30 minutes. The remainder (15 minutes) should be used for discussions. The following papers are discussed.

There will be no exam but grading will depend on the quality of the given presentations (40%), 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.

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