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).

A Comparative Study of k-Nearest Neighbour Techniques in Crowd Simulation

A Comparative Study of k-Nearest Neighbour Techniques in Crowd Simulation.

We compare several data structures for performing k-nearest neighbor (kNN) queries, including BD-tree, Grid, k-d tree (FLANN, nanoflann), k-means, linear search, R-tree, and Voronoi diagram.

Abstract

The k-nearest neighbour (kNN) problem appears in many different fields of computer science, such as computer animation and robotics. In crowd simulation, kNN queries are typically used by a collision-avoidance method to prevent unnecessary computations. Many different methods for finding these neighbours exist, but it is unclear which will work best in crowd simulations, an application which is characterised by low dimensionality and frequent change of the data points. We therefore compare several data structures for performing kNN queries. We find that the nanoflann implementation of a k-d tree offers the best performance by far on many different scenarios, processing 100,000 agents in about 35 milliseconds on a fast consumer PC.

Test environments

Some test environments are depictured below.

Some of the different test scenarios. The left pictures shows the scenario with a clustered distribution of agents; the middle picture shows the evacuation scenario, and the right picture shows one of the Tour de France scenarios.

Some of the different test scenarios: clustered distribution, evacuation scenario, and the Tour de France scenario.

References

  • Jordi Vermeulen, Arne Hillebrand and Roland Geraerts. A Comparative Study of k-Nearest Neighbour Techniques in Crowd Simulation. Computer Animation and Virtual Worlds. Volume 28, Issue 3-4. CASA 2017, Seoul - South Korea, May 22-24, 2017.

    Full text zip Presentation

Trajectory data used in our experiments

We used the following trajectory data (in total 4.1GB) in our comparative study.

Each file consists of the following data (in binary format):

  • Bounding box of the environment (xmin, xmax, ymin, ymax): 4x8 bytes interpreted as doubles
  • For each time step(*):
    • The number of agents: 4 bytes interpreted as integer
    • For each agent:
      • Agent ID: 4 bytes interpresed as integer
      • X- and Y-coordinates, 2x8 bytes interpreted as doubles

(*) All file names that embody the word 'combine' represent trajectories that have been sampled 16 times per second. The others have been sampled 10 times per second.