Boid-based systems are typically used to simulate flocks of animals in nature, such as avian flocks or fish schools. The naïve implementation has a time complexity of $O(n^2)$, as each boid perceives and reacts to every other, and thus scales poorly with flock size. Several optimizations and strategies have previously been explored to mitigate this fact, such as space partitioning of the game world where the simulation runs. This thesis explores the performance bottlenecks in an implementation utilizing some of these optimizations, mainly spatial hashing. The findings indicate that the major performance bottleneck is the aggregation of positions and headings required to enact the boid steering behaviors. This performance bottleneck can be alleviated by spatially hashing the game world, using a cell-based neighborhood, and parallelizing the computations over these cells. In addition, parameters controlling the simulation can be tweaked and upper-bound limits imposed on the number of interactions to further improve performance.
| Identifer | oai:union.ndltd.org:UPSALLA1/oai:DiVA.org:liu-204893 |
| Date | January 2024 |
| Creators | Norgren, Bo Valdemar |
| Publisher | Linköpings universitet, Institutionen för systemteknik |
| Source Sets | DiVA Archive at Upsalla University |
| Language | English |
| Detected Language | English |
| Type | Student thesis, info:eu-repo/semantics/bachelorThesis, text |
| Format | application/pdf |
| Rights | info:eu-repo/semantics/openAccess |
Page generated in 0.1364 seconds