Over the past few weeks we’ve been working on a quite a few tasks, one of which was about flocking. The flocking task was split up into three parts: 1) optimise a flocking simulation, 2) add a way to configure the simulation and 3) a method of getting statistics from the simulation so that it could be tuned.
Initially, the simulation was set up so that each flocking agent checked against every other agent and calculated if they were in range of any of it’s “sensors” and then acted on that input. So for the first part, I decided to set up a kd-tree and limit the checks to nodes that overlapped with each agents sensors (using a AABB). Nodes of the kd-tree were allocated once (sort of, I was using a std::vector for this) and reused to increase cache coherency and to make it easier to iterate over them. For simplicity’s sake, the tree was reconstructed each frame, but this didn’t seem to pose any tangible hit to performance – the gains were much greater.
Next I multithreaded it using OpenMP on the update loops of the agents. This was incredibly simple to do as the agents were designed so that they wouldn’t need synchronisation while updating, though it posed some problems later when it came to stat collection.
I also, after some profiling with callgrind, removed some of the slower math that was being hit the most. There was one function in particular that was particularly bad for oft-hit slow math which was a test that agents used to test if another agent was in range of one of it’s sensors. It involved square roots and an acos. I managed to delay a square root by modifying an early out to compare squares of values instead of values. Also, the code dealing with checking the differences in angles originally compared the acos of a dot product to the angle of a sensor. I reversed this calculation so it compared the cos of the sensor angle with the dot product and then cached the cos in the sensor. This removed all trigonometry from the function entirely.
Next step was the configuring stage. I decided on lua and a simple binding for configuration. This was pretty straightforward. I pretty much exposed agents, obstacles and sensor parameters with user data and a small library of setters each (I didn’t bother with getters because they didn’t seem useful in this instance), and then added a few extra functions for creating said things and setting up the overall simulation, like setting seed and whatnot. I also decided to make all the setter functions chainable to remove some repetitiveness.For fun I also made it so that when preditor agents collided with regular agents, they would also become preditors. A sort of zombie mode. Idea stolen from Corey.
Finally, for statistics and what not, I decided to spit out data relating to when agents became zombies and where things were during the simulation, and a few other tid bits. Because I wanted to keep this self contained I decided to write an ascii renderer for a graph and heatmap (on the train to uni… twice). Here is the result.
The graph represents infections over time and the heatmap is simply a normalised log of the positions of all agents during the simulation. The symbols used in the heatmap and the output size of the heatmap are also fully configurable in lua.
Anyway, here is a large gif (sorry).