Homepage > Crowd simulation > List of publications > Paper

We study how we can automatically create a data structure that represents the walkable surfaces in such an environment, and how it can be updated dynamically and efficiently when it changes. We refer to this structure as a navigation mesh. This mesh enables efficient crowd simulation, which is our next topic of research. We study and develop a crowd simulation framework and its components, which ranges from global (AI) planning to local animation. We create models for realistic crowd behaviors, which includes studying how (groups of) people move and avoid collisions in such environments, based on agent profiles and semantics (such as terrain annotations).

Path Planning for Groups using Column Generation

Multi-unit pathfinding: a screenshot from 'Cossacks: Back To War'.

Abstract

In computer games, one or more groups of units need to move from one location to another as quickly as possible. If there is only one group, then it can be solved efficiently as a dynamic flow problem. If there are several groups with different origins and destinations, then the problem becomes NP-hard. In current games, these problems are solved by using greedy ad hoc rules, leading to long traversal times or congestions and deadlocks near narrow passages. We present a centralized optimization approach based on Integer Linear Programming. Our solution provides an efficient heuristic to minimize the average and latest arrival time of the units.

Reference

  • Marjan van den Akker, Roland Geraerts, Han Hoogeveen and Corien Prins. Path Planning for Groups using Column Generation. In Motion in Games (MIG'10), Springer Lecture Notes in Computer Science (LNCS) 6459, pp. 94-105, 2010.

    Full text Full text YouTube

Our follow up reseach can be found here where we've integrated local collision avoidance behaviour.

Movie

The need for the proposed technique is demonstrated in the following movie.

Path finding challenged with large groups.