Sixth International Conference on Simulation Tools and Techniques

Research Article

Spatial Indexing in Agent-based Crowd Simulation

  • @INPROCEEDINGS{10.4108/icst.simutools.2013.251691,
        author={Nasri Othman and Linbo Luo and Wentong Cai and Michael Lees},
        title={Spatial Indexing in Agent-based Crowd Simulation},
        proceedings={Sixth International Conference on Simulation Tools and Techniques},
        keywords={agent-based simulation crowd simulation spatial indexing performance analysis},
  • Nasri Othman
    Linbo Luo
    Wentong Cai
    Michael Lees
    Year: 2013
    Spatial Indexing in Agent-based Crowd Simulation
    DOI: 10.4108/icst.simutools.2013.251691
Nasri Othman1, Linbo Luo1, Wentong Cai1,*, Michael Lees1
  • 1: Nanyang Technological University
*Contact email:


Crowd modeling and simulation has become a critical tool for understanding crowds and predicting their behaviours. This is accomplished by modelling the characteristics and behaviours of large groups of people, as well as their interactions. Agent-based crowd simulation may involve thousands of complex agents interacting in sophisticated ways, in close spatial proximity, with each other. A key challenge to the development of agent-based crowd simulation is the inherent complexity that is required to model all its necessary elements. A necessary feature of such a simulation is spatial indexing. This refers to the use of data structures to organize collections of simulation entities (e.g., agents and obstacles) in a manner which allows for efficient spatial querying. This is especially pertinent for large-scale crowd simulation with agents that sense their surrounding environment periodically, as the cost of spatial querying becomes computationally expensive if done naively. In this paper, we will describe our experience in improving the existing grid-based spatial indexing approach in our agent-based crowd simulation. Also, we will explore the integration of the adaptive spatial indices (e.g., R-tree and quad-tree) into our system. The performances of various spatial indexing techniques are examined in terms of efficiency and scalability.