A Stream algorithm for crowd simulation to improve crowd coordination at all densities.

Abstract

Crowd simulation is becoming an essential part of computer sciences. In the last decades the research field has taken a flight. Current state-of-the-art micro simulation algorithms for crowd simulation are able to deliver very convincing results. Recently, vision-based algorithms have been developed that are based on the field of vision of individual agents. These algorithms allow agents to interact realistically at low to medium densities, but have trouble coordinating movement at high density. A concurrent development are flow algorithms. These algorithms are able to solve high density scenarios due to an inherent high level of coordination, but lack individuality of agents. Up till now, however, no algorithm exists that can handle both low densities as well as extremely high densities realistically. In this thesis we will define an algorithm that can handle the entire density spectrum. Agents are individual entities with personal goals and settings. The algorithm will incorporate the implicit, local coordination present in real-life crowds. We will show that coordination is essential in high density areas. Information is implicitly stored in a crowd's movement. We introduce the concept of streams to extract this information. The implicit global coordination of streams improves crowd flow and supports lane formation in extreme densities. We will implement this theory to achieve an algorithm that can handle all different densities. To allow for both individual as well as coordinated behaviour we will introduce the concept of incentive. An agent's incentive determines if it will display more individualistic behaviour or be group-oriented. This allows agents to display individualistic behaviour as long as possible, while still cooperating if necessary. Experiments show that the streams algorithm together with our incentive-based interpolation scheme are a valuable addition to current micro collision-avoidance algorithms. Our algorithm is able to handle higher densities correctly, whilst maintaining behaviour at low densities. The inherent coordination at high densities is missing in all current algorithms. Even at lower densities the streams algorithm contributes to quicker and clearer lane formation. Our algorithm is able to function properly at all densities.