Roach Crowd Sim

Rough concept

Similar to boids except that the cockroachs' bodies are parented to an empty/root bone which is shrinkwrapped to a low poly mesh (offset some distance from the floor) which marks the area the roach's are constrained to.

The system uses empties to input data. Custom properties define whether an empty represents an aligner, a control or a boid (roach). Controls (which can be of type 'follow' 'attract' 'repel' 'herd' 'panic' 'sleep' etc) are empties which affect boids within a certain radius during the simulation time. Proximity data is refreshed on a frame by frame basis. Aligners are used during setup to quickly orientate and configure a large number of boids using a weighted linear fall off to interpolate starting direction and speed between multiple aligners.

The roachs have an emotional state which is adjusted each frame by various influences (including how crowded the flock is, whether they have been involved in a collision, if they have strayed from the flock, or if they are under the influence of a controller). Emotional states decay/normalize over time.

Optimizations

Python is incredibly slow. With 500 boids there are 500x499 inter-boid distances (or separations) to measure. These are stored in a half-matrix (1/2 n (n + 1)) indexed by [boid with lower index of pair][boid with higher index of pair]. The separations are also indexed in another dict by their value ie dict[separation distance]=[index a][index b]. Both sortings of the separations are required so although the script is basically holding duplicate data, this will be faster than reindexing the half-matrix by separation size each time we need to find the pair which is closest together, or a list of all pairs which have collided.

Having to regenerate all the separations every frame would make the script run extremely slowly. Instead, we can only regenerate the critical separations (ie those inter-roach distances which are small enough to mean that either a collision has taken place, or that a roach can 'see' another roach - the user defines a 'sight distance' for the roaches). The sight distance will obviously be larger than the 2 * roach radius (the collision distance). As we know the maximum distance a roach can travel in a single frame (defined by the user), we can calculate how often separation data will need to be refreshed.

Ignoring the roach's radius for simplicity's sake, if a roach can see 1 unit away, and the maximum speed of a roach is 0.1 units, then any pairs of roaches whose separation is less than / equal to 1.1 units will need to be refreshed after 1 frame. After 2 frames a roach which was 1.2 units away could now be within the sight distance (as its max speed 0.1*2 frames = 0.2... + sight distance of 1 = 1.2). After 3 frames a roach which was 1.3 units away... and so on.

Once data has been refreshed, it lasts for a set number of frames before it needs to be refreshed again:

roachs within distance 0-1.1 need regenerating every frame roachs within distance 1-1.1.2 need regenerating every other frame roachs within distance 1-2.1.3 need regenerating every third frame roachs within distance 1-3.1.4 need regenerating every fourth frame roachs within distance 1-4.1.5 need regenerating every fifth frame

So for example on the 6th frame, the range from 0-1.3 and 1.5-1.6 needs refreshing, but the data from 1.3-1.5 is still valid as no roaches within this range or radii could possibly be within the sight distance even if they have moved at maximum speed.

My python code currently keeps track of the age of the separation data so only the bare minimum of data gets refreshed each frame saving a vast amount of computation time.