OSOM - Massive Boids

Closed Human-Computer Interaction Computer Science Games Engineering Bachelor Master Project Thesis Games Research Lab

Background

In the late 70s, the first simulations emerged that features flocks of virtual birds, or boids. In these models, the boid agents move in accordance with their neighbours [5]. The feedback loop between perception and action results in dynamic neighbourhood relationships among the individuals [6]. When parallelising such simulations, conditional branches, random memory access and process synchronisation pose major challenges for memory organisation and algorithmic execution [4]. For the utilisation of graphics processing units (GPUs), which offer vast computational power, these challenges also need to specifically address the hardware’s architecture [3]. As a result, an early approach to GPU-driven boid simulation only outsourced the computation of local acceleration vectors and let the heavy neighbourhood calculations run on the CPU (O(n2) distance calculations), yielding an increase in performance from 30 to 1600 simulated agents at 60 frames per second (fps) [1]. The whole model can be calculated on GPUs if partitioning the simulation space into equally-sized cells and assigning agents to cells according to their position. Sorting the agents in accordance with their respective cells’ identifiers allows for coalesced memory access, efficiently resolving neighbourhood relations. An according implementation was shown to simulate 65536 boid agents at 60 fps [2].

Tasks

In this work, a boid model has to be conceived and implemented that makes use of the GPU and static space partition algorithms to simulate and interactively visualise a large number of boid agents in 3D space. Furthermore, the simulation needs to be setup in virtual reality using the HTC Vive system. Here, the challenge lies in either delimiting the simulation space so that the user’s relative location can remain fixed, or in providing means to track a flock across wide stretches without relying on camera motion to mitigate the effects of cyber sickness.

Prerequisites

A background in computer graphics, VR and any of the established game engines is a great asset for this work.

References

[1] Rosario De Chiara, Ugo Erra, Vittorio Scarano, and Maurizio Tatafiore. Massive simulation using gpu of a distributed behavioral model of a flock with obstacle avoidance. In Proceedings of vision, modeling and visualization, pages 233– 240, Stanford, CA, US, November 2004. Akademische Verlagsgesellschaft Aka.

[2] Ugo Erra, Bernardino Frola, Vittorio Scarano, and Iain Couzin. An efficient gpu implementation for large scale individual-based simulation of collective behavior. In High Performance Computational Systems Biology, 2009. HIBI ’09. International Workshop on, pages 51–58, 2009.

[3] Mark Joselli, E. Passo, Jose Ricardo Silva Junior, Marcelo Zamith, Esteban Clua, and E. Soluri. A flocking boids simulation and optimization structure for mobile multicore architectures. In XI Brazilian Symposium on Computer Games and Digital Entertainment, SBGames 2012 – Computing Track, 2012.

[4] Kalyan S. Perumalla and Brandon G. Aaby. Data parallel execution challenges and runtime performance of agent simulations on gpus. In Proceedings of the 2008 Spring Simulation Multiconference, SpringSim ’08, pages 116–123, San Diego, CA, USA, 2008. Society for Computer Simulation International.

[5] Craig W. Reynolds. Flocks, herds, and schools: A distributed behavioral model. In SIGGRAPH ’87 Conference Proceedings, volume 4, pages 25–34, 1987.

[6] Sebastian von Mammen and Christian Jacob. The spatiality of swarms — quantitative analysis of dynamic interaction networks. In Proceedings of Artificial Life XI, pages 662–669, Winchester, UK, 2008. MIT Press.

Contact Persons at the University Würzburg