Department of Information and Computing Sciences

Departement Informatica Onderwijs
Bachelor Informatica Informatiekunde Kunstmatige intelligentie Master Computing Science Game&Media Technology Artifical Intelligence Business Informatics

Onderwijs Informatica en Informatiekunde

Vak-informatie Informatica en Informatiekunde

Path planning

Website:website containing additional information
Course code:INFOMPAP
Credits:7.5 ECTS
Period:period 2 (week 46 through 5, i.e., 14-11-2016 through 3-2-2017; retake week 16)
Participants:up till now 47 subscriptions
Schedule:Official schedule representation can be found in Osiris
Teachers:Dit is een oud rooster!
lecture   Mon 11.00-12.4546-51 BBG-023 Roland Geraerts
2-5 BBG-023
Wed 9.00-10.4546-51 RUPPERT-C

A huge challenge in computer games and virtual environments in general is to simulate (tens of) thousands of characters in real-time where they pro-actively and realistically avoid collisions with each other and with obstacles present in their environment. Also it is important that these paths are visually compelling or even realistic, that is, the characters must move around in ways similar to real people (or monsters). In this course we will study a number of the recent results on path planning and crowd simulation, and how they can be applied in computer games.

Besides knowing the state of the art in path planning and crowd simulation, you will become a critical reader, discover where the holes in the research are, participate in discussions and lead them, give better presentations, know how to set up experiments better, and write better review reports and assessments.

This year, the course will get a new title, i.e. Crowd Simulation, because it better fits the contents.

Literature:A selection of research papers will be provided during the course. You will have to give presentations about some of them, and write reviews and summaries of others.
Course form:This course is a seminar with regular meetings, three workshops, and many discussions. You will also have to study crowd simulation in current games and create a game in which this is improved. Presence during the meetings is mandatory.
Exam form:There will be no exam but grading will depend on the quality of the given presentation (15%), the game footage (10%), the quality of the game and paper (35%), as well as the abstracts/assessments (40%).
Minimum effort to qualify for 2nd chance exam:To qualify for second chance exam, the original mark should at least be a 4. Also you must actively participate in at least 75% of the meetings and your presentation satisfactory. You cannot pass the course if you skipped 6 or more abstracts.
Description:This course has the following learning goals. The student
  • knows the basic path planning problem, and knows how to translate these path planning problems to configuration space;
  • knows about sampling-based approaches to path planning and about exact and approximate versions of cell-decomposition as well as roadmap-based approaches to path planning, and is aware of the advantages and drawbacks of each of the methods;
  • knows about modern navigation meshes for representing the walkable space in virtual environments, such as triangulations, voxel-based methods, navigation graphs, Explicit Corridor Maps, and is aware of the advantages and drawbacks of each of the methods;
  • knows how to compute shortest paths in graphs (using A*/Dijkstra) and polygons (using funnels). Furthermore, the student knows how to create smooth paths using the Indicative Route Method;
  • knows about extensions to basic path planning (multiple robots, combinatorial motion planning, dynamic environments);
  • knows about different methods for collision avoidance (such Helbing's model, RVO, collision-prediction);
  • knows how to model crowd flows and streams and how to deal with massive crowds;
  • knows how to model different behaviors in crowds (small and large groups, personalities, panic);
  • knows how to build a crowd simulation framework;
  • knows how to evaluate a crowd simulation;
  • knows about several crowd simulation applications (such as evacuation, safety, training, games);
  • knows about implementation issues (basics, computation geometry (precision, accuracy), speed, multi-core);
  • knows how to critically assess a paper and has insight into the state of the art in crowd simulation, and is able to interpret, review, and compare state-of-the-art results in the field;
  • knows how to critically look at path planning and crowd simulation in games;
  • becomes a critical reader, discovers where the holes in the research are, participates in discussions and lead them, gives better presentations, knows how to set up experiments better, and writes better review reports and assessments.