Crowd simulation in games
Lehtinen, Eero (2024)
2024
Tietotekniikan DI-ohjelma - Master's Programme in Information Technology
Informaatioteknologian ja viestinnän tiedekunta - Faculty of Information Technology and Communication Sciences
This publication is copyrighted. You may download, display and print it for Your own personal use. Commercial use is prohibited.
Hyväksymispäivämäärä
2024-06-07
Julkaisun pysyvä osoite on
https://urn.fi/URN:NBN:fi:tuni-202405216122
https://urn.fi/URN:NBN:fi:tuni-202405216122
Tiivistelmä
The main goal of this thesis is to find improvements to a game made by me titled Gunbug by investigating the performance and behavioral suitability of different algorithms and approaches to crowd simulations. The findings can also be used in other games or applications that require a similar type of crowd simulation. Practical aspects are emphasized to make it easy to utilize the findings in real applications.
Crowd simulation is controlling large groups of autonomous agents, such as pedestrians to simulate crowd behaviors. These behaviors include interactions between agents and the environment. Path planning is an important part of crowd simulation, as it governs how the crowd traverses the environment towards a target. Flow fields are suitable for crowd path planning because all crowd individuals can share the same calculation. Interactions between agents can be solved with flocking techniques. Spatial structures are useful when processing interactions that are dependent on other nearby agents. They enable avoiding the O(n^2) complexity of iterating through all other agents to find neighbors for each agent.
Gunbug is a shoot'em up action horde survival game. It needs to be able to simulate thousands of enemies attacking the player at the same time. The enemies need to be able to move smoothly through an environment filled with walls of arbitrary polygons. The simulation has high-performance requirements because the game needs to be run in real-time at a high refresh rate. This effectively leaves only a few milliseconds to do the simulation routine on each game tick. The game already uses flow fields and flocking techniques. The flocking is a large performance bottleneck and has undesirable jittery movements, so both performance and behavior need improvements.
Improvements were found in changing the separation distance function to quadratic and reducing the strength of the flow field forces to reduce jitter. Also, a bug in velocity clamping was fixed to reduce instability. Branchless techniques and parallelism were used to considerably reduce the run time of agent separation. Different spatial structures were compared and a simple array grid-based technique was found to be the fastest. K-d trees were found to be surprisingly slow. The total improvement in the simulation behavior was large. Also, the running time was reduced from 6.87 milliseconds to 0.93 milliseconds in the worst-case level in the evaluation program benchmark.
Crowd simulation is controlling large groups of autonomous agents, such as pedestrians to simulate crowd behaviors. These behaviors include interactions between agents and the environment. Path planning is an important part of crowd simulation, as it governs how the crowd traverses the environment towards a target. Flow fields are suitable for crowd path planning because all crowd individuals can share the same calculation. Interactions between agents can be solved with flocking techniques. Spatial structures are useful when processing interactions that are dependent on other nearby agents. They enable avoiding the O(n^2) complexity of iterating through all other agents to find neighbors for each agent.
Gunbug is a shoot'em up action horde survival game. It needs to be able to simulate thousands of enemies attacking the player at the same time. The enemies need to be able to move smoothly through an environment filled with walls of arbitrary polygons. The simulation has high-performance requirements because the game needs to be run in real-time at a high refresh rate. This effectively leaves only a few milliseconds to do the simulation routine on each game tick. The game already uses flow fields and flocking techniques. The flocking is a large performance bottleneck and has undesirable jittery movements, so both performance and behavior need improvements.
Improvements were found in changing the separation distance function to quadratic and reducing the strength of the flow field forces to reduce jitter. Also, a bug in velocity clamping was fixed to reduce instability. Branchless techniques and parallelism were used to considerably reduce the run time of agent separation. Different spatial structures were compared and a simple array grid-based technique was found to be the fastest. K-d trees were found to be surprisingly slow. The total improvement in the simulation behavior was large. Also, the running time was reduced from 6.87 milliseconds to 0.93 milliseconds in the worst-case level in the evaluation program benchmark.