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.

The roachs have a friend/foe database. Roachs they have collided with slide to the foe end of the scale, wheras roachs they have herded with (moved parallel to) become their friends.

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.

Collisions

Overlap Collisions: (where the bounding sphere for one roach overlaps with the bounding sphere of another) These are resolved by freezing one roach and moving the other along the vector from the centre of the frozen roach to the centre of the unfrozen roach until the unfrozen roach no longer overlaps. The reason for freezing rather than standard Newtonian physics calculations is that when multiple roachs collide in a single frame, calculations can simply begin at the most locked in roach and work outwards from there, freezing each roach as it is processed. The unfrozen roach's rotation is pointed away from the frozen roach instantaneously. The rotation of the roachs represents the direction of their movement NOT the orientation of their bodies - ie a roach can face forwards but walk backwards out of a collision. The orientation of their bodies can be determined after the script has run by smoothing over the rotation curves.

Early Warning System: Roachs have a 'last minute repel' whereby if they are getting very close to another roach they begin to gradually change direction and rotation away from it. The rate of change is determined by how close they are to an overlap collision. This is intended to prevent the overlap collisions from ever executing, however it will not force a roach out of a collision in the same way the overlap collisions algorithm will.

Escape Route Searching: Roachs look around them and determine the bearing of all their neighbours (projected into the roach's local XY plane to take account for when roachs are not on a perfectly flat surface). They look for the largest gap or escape route possible by finding the largest of the difference between subsequent sorted bearings of neighbours. For example if there is a roach due east of them and a roach due south then the best escape route is to the north west. The roach will gradually change rotation (the rate of change determined by the global simulation speed) towards this bearing.