Ant simulation

Complex ant colony behaviour emerges from the interaction between the individual ants and the rest of the colony to provide a large, stable, and efficient system to provide food and continue existing. Using GPGPU (general purpose graphics processing unit) programs we can simulate this behaviour efficiently and in real time.

The plan

I wanted to build a large scale 2d ant simulation, where each ant is simulated in detail and accurately executes behaviours that let them work together to get food and build a colony. Originally I just wanted it to be a free-spinning simulation, but I later added interaction mechanics not unlike a sort of "god game".

Key ideas

For this simulation there were some key ideas that I wanted to implement. I wanted everything in the system to be physically modelled (i.e. collisions between all entities in the system). I wanted a fungible energy collection system, for entities to move or be created energy must be used. Each nests goal is to collect energy to produce more ants, the energy collection is executed by the ants themselves.

I wanted robust and physically accurate interaction between all of the entities of the system with no smoke or mirrors.

Finally I wanted this to all run in real time, and be rendered interactively.

This was originally implemented only on the CPU, but eventually all of the code was moved to the GPU utilising GLSL compute shaders with a OpenGL rendering pipeline.

Ants

Basic pheromones

Ants can form large scale behavioural patterns that help the colony grow without the need for significant intellect, by communicating with pheromones, and "hard coded" useful behaviours. Simulating ants therefore becomes an attractive if you want to show emergent behaviour on a large scale - as each ant requires minimal computation.

An interesting fact about ant pheromones, is that they do not constitute a scalar field, each pheromone trail encodes direction in more than just the gradient. This allows the ants to have a more robust trail than if each ant purely followed density gradients.

Another key piece of information I found is that the pheromone trails actively diffuse like a fluid - just over long time scales.

With these two factors in mind, I decided to model my pheromone fields using an Eulieran vector field grid - coupled with a fluid simulation style diffusion. These pheremone fields can be sampled and updated by the ants.

I originally set out with only two pheromone fields in mind:

The home pheromone would be laid by an ant moving away from home (vector quantity laid down being the negative of the ants velocity). The food pheromone would be laid once an ant had found some food, also laying a trail towards food).

The simple behaviour each ant would follow can be described as:

And:

The ant will follow preexisting food trails, or follow a random walk looking for food. When an ant finds a food source, it collects some energy replenishing its own personal store and also carries some back for the colony. The ants aim is to get this energy back to it's colony, to drop this "energy" off into the colony - such that more ants may be produced. If the ant doesn't find any food it will return to the colony to pick up energy from the store.

Mathamtically we can define our ants proposed heading by a set of equations.

\[ %\itertext{Looking for food} \begin{align} \text{Food finding state:}\\ H(t) &= R_f \phi(t) + A_F P_f(x)\\ \text{Home finding state:}\\ H(t) &= R_h \phi(t) + A_H P_h(x) \end{align} \]

Where \(\phi(t)\) a randomised vector varying over time, that lets ants find new food sources or find the path if pushed off. The constants \(R_{f,h}\) are can control how much random walking the ants will have during food or home finding states. The constants A_{F,H} contain the influence of the food and home pheromone trails respectively. The pheromone trails \(P_f, P_h\) are updated by the ants using their instantaneous velocity:

\[ \begin{align} \text{Food finding state:}\\ P_h(x,t) &= P(x,t) - |V(t)|\\ \text{Home finding state:}\\ P_f(x,t) &= P(x,t) - |V(t)| \end{align} \]

We can model the pheromone field with a simple decay function

\[ \frac{\partial P(x,t)}{\partial t} = -DecayFactor \]

Pheromone diffusion

When the pheromone trail is laid down in real life, it acts very much like a fluid over longer timescales. The trails diffuse and merge together allowing similar trails to combine and reinforce each other. With all of the pheromones on the grid in a large 2d texture, a simple diffusion computational shader is implemented with multiple passes to simulate this diffusion. Since the fluids do not have a strong advocation term, this is neglected.

Each point on the mesh at \(i,j\) is updated with some diffusion factor D limiting the rate of diffusion. We can run the diffusion step multiple times to increase numerical stability.

\[ P_{i,j} = (1-D)p_{i,j} + D\sum{p_{i+dx,j+dy}} \]

This minor diffusion step allows for much more interesting behaviour and is rather critical for stable paths. Similar small paths can diffuse and join up to make one larger more optiomal path.

Ant colonies

Ant colonies have a simple existence, they are an entity in the world with a health and energy store but cannot move. They can use the energy store to produce new ants, or a queen ant that will leave and produce a new nest. All the ants and queens will have the same affiliation and will not attack each other, they also share a unified set of pheremone fields. Ants leave the nest looking for food, and if they find it will come back and replenish the energy store. If the ants do not find food they will come back and resupply from the nests store. If the energy store reaches zero, the nest dies.

First implementation

The first implementation of the ant project was on the CPU, with a multithreaded entity system and basic decay based pheremone fields. The limiting factor for the performance of the system was the pheremone computation. The decay step, and diffusion steps had very high performance costs - and a complex quad-tree for culling updates over empty sections would have been needed.

Fluid decay and diffusion is trivial to implement on the GPU, this worked in tandem with the CPU implementation - but it soon hit another bottleneck for transfering the pheremones from CPU<->GPU.

First GPU implementation

To eliminate all of the bottlenecks in transfering data between CPU and GPU all of the computation was moved into compute shaders.

The first GPU implementation stored each of the pheromone fields on a image on the GPU, and the ant data was stored in one SSBO wich contained all of the entity infomation. The key infomation the entities store are:

Note that the entity list is a union of all of the different types of entity, and is a fixed capacity swaplist. A shader was executed over the whole entity list for physics simulation (collisions etc), and a shader including the nest and ant behaviour was executed over the whole list as well.

This implementation had significant downsides, the performance of the shaders was poor due to the large conditional branching of the AI section, and how compute shaders are execute. Even though there was only 1 nest, the nest code was executed and discarded over all of the ants in the SSBO.

Filling out the world

To make the play environment more interesting and dynamic other animals were introduced to provide a source of food and fear for each colony. Prey animals gain energy passively, and can rapidly reproduce if left unchecked. Predator animals require lots of food, but easily kill other animals and have a fast move speed.

Newly born prey animals are both small and fast, making them hard to chase for predators - allowing for a pseudo stable system.

Some method of interaction was then required to allow the predators to hunt the fast moving prey. Instead of adding some more complex vision system, a smell pheromone is created per type.

Each entity passively generates a circle smell pheromones that let other animals to either try and move away or towards it.
The predator entities attempt to avoid each other, and aggressively follow prey and ant smells.

Prey try and group up in herds, and flee from the predators.

The ants try and follow the prey and predator smells to attack them and eat them.

When every animal dies its corpse gets left behind. The corpse gives off the normal smell, but its energy decreases over time and the corpse is removed when the energy hits 0.

Terrain

The world that these ants, and creatures interact on is a flat toroidal surface. The world wraps around on the x and y dimension naturally, without distorsion. This however is very boring and does not allow for interesting behaviours. To allow the prey a chance, the world should include impassible barriors that can act like reefs for the small prey to hide amongst.

A simple 2d heightmap is generated using perlin noise, and loaded onto the GPU as a texture. This texture is included in the collision pass and is rendered in the scene as a 3d heightmap.

Second implementation

Even with the increasing quantity of types of entity the data is still kept in single uniform SSBO. To improve on the AI shader performance the different types now were given separate shaders, so no large branches are excused. With GPU execution, indirected memory access is not as terrible as with a CPU. CPUs rely heavily on prefetched memory and speculative exertion, which is almost impossible with indirection systems. GPUs do have these features, but due to the scheduling of shaders the cost is almost always amortised with execution of other systems. When an entity of type \(N\) is inserted into the main entity array, its index is added to an indirection array \(I_N\). When the entity in the SSBO array (a swaplist) is moved, the indirection is updated. When the AI shader of type \(N\) is executed it is executed over the indirection list \(I_N\) and uses this to index into the mainarray. Each work group of AI shaders is therefore guaranteed to be fully saturated with entities of type \(N\).

One of the downsides to this is that each entity needs to keep track of the position its listing in the indirection list to efficiently update its indirection listing.

Collision performance

The naive implementation of collision detection is \(N^2\) in complexity and there are many smart algorithms for decreasing the complexity. The one issue is that any algorithm that is picked must be feasibly implemented to run on a GPU. A good system to pick, with a good tradeoff in performance and complexity is a spacial binning system with fixed chunk sizes. The fixed chunk sizes means that it is easy to select what bin each entity must sit in, and also are easy to reason about ownership on a parralaised implementation.

The first step in our algorithm is for each entity to add its own ID to the chunks collision list that it resides in. Each chunk has a reasonable fixed size array, and an atomically updated entity count. It is assumed the entity density in the chunk will not reasonably go above some limit and that these stacks will not overflow. If the entity straddles chunk boundaries (especially if it is very large), then it must be placed into all of the chunks it occupies.

After this initial pass, each chunk now contains a list of every entity that are in it, this has occured in \(O(N)\) time. Each entity now must collect a list of unique IDs of entities that it could feasibly collide with. By iterating over the chunks an entity resides in, then inserting unique Ids it into a thread local stack of collision candidates we have very poor algorithmic complexity - but reasonable performance due to small stack sizes.

Each collision has two com portents: Physical, Behavioral. The entities must be displaced so that they no longer intersect (assuming they are spherical) and imparted with a collision velocity. The behavioural aspect is more interesting, when two classes of entities collide they may want to perform actions on each other. Using a switch-case table a form of multiple dispatch is created where the AI collision behaviour may be executed.

The kinds of behaviour may be: ants taking or depositing food from the nest, predators dealing damage when colliding with non predators. Ants of different factions also will deal damage to each other to attempt to wipe out the competing factions.

Gamification

At this point we have an interesting ant simulation in a small world filled with predators and prey trying to survive and reproduce. To make this more interesting the viewer is given slightly more control over the ants then before using two controls.

The colony ant reproduction rate is a constant related to the probability an ant nets will produce a new ant over a given time period. The player can reduce this if there are no obvious food sources, or increase this if they are attacked by a predator. The queen reproduction rate has a similar function.

The ant attack pheromone is related to the real world equivalent in the "death pheromone" when an ant dies it releases a pheromone that causes other ant to come and attack in a frenzy. This means that predators approaching the nest will quickly be swarmed with ants. The attack pheromone had a similar idea, when ants die they will paint a region of the pheromone field with directions towards the entity that killed them. This field turned out to be very useful as a general "go over here" direction for the player to broad strokes direct their colony.

Inspired by RTS games, a fog of war was implemented the players vision is obscured by a fog which is lifted within some distance of home pheromones.

Plans for the future

Swap list races

Due to the complexity in the swap lists I believe there is some interesting racy conditions in the code, these will hopefully be fixed.

ECS

As the system has evolved it has progressed towards an Entity-Component-System style of data storage and code execution.

Ideally I would like to split the main entity SSBO into:

I would also like to pull out some type based constants and make them variable per entity like movement speed changing for entities that are hurt etc.

Per nest control

In line with per-ant variables I would like the interaction with ant colonies to be more granular, at the moment you can only change the reproductions for all ant colonies as they live on a shared table - ideally these variables would be stored in the nest specific SSBO.

Ant upgrades

In line with the gamification of the simulation, I think it would be good to be able to spend energy to improve the ants that you can produce (faster, higher HP, more damage).

Better graphics

Everything is a blob

Youtube

Some youtube links of the ants development