In this post, we’ll see how to program an ant colony simulation. I got the initial idea from a friend and this implementation is a variation of his initial implementation.
The goal of this simulation is to have ants find optimal or close to optimal paths between food sources and the nest. While some ant simulators achieve this by trying to reproduce how ants behave in real life, this simulator is a much coarser representation of how ants really behave.
At the core of this simulation, we have ants move randomly. As they move, they update the distance from their current position to the nest. When they find food, they follow a path back to the nest based on this information. Also when finding food, they leave a trace for other ants to follow to find food.
The simulation can be accessed here. The rest of this post explains details of the implementation. Feel free to ask for any extra details in the comments.
The physical space is represented by “cells”, much like a chessboard. Each ant (represented in brown in the simulation) occupies a single cell at a specific time and can move to any of the adjacent cells. Both food (orange) sources and the nest (green) occupy a single cell. To make it more interesting, some obstacles are created. They are represented by blue blocks.
Ants: scavenge mode
When ants first leave the nest, which is their starting point in the simulation, they operate in scavenge mode. This means that their goal is to find a food source. This is achieved by following the three strategies below.
Ants: follow food trace
When an ant finds a food trail in any of the cells adjacent to its current one, it will follow it to find a food source.
The food trail is represented by the yellow-colored cells. We’ll see the details of how food trails are created later on this post.
Ants: random walks
If no food trail is found directly next to the ant’s current cell, the ant will move randomly to any adjacent cell.
Ants: update distance to the nest
Either when they’re following food trails or when they’re moving randomly, ants will update a value on the cells they traverse used to store the distance between them and the nest.
In the figure above, we have one ant displace a single cell to the right. As it does so, it updates the
nestDistance property on the cells. Each ant “counts” how many cells it has moved since leaving the nest. As it reaches new cells, it “prints” that value on the cells it traverses. Horizontal and vertical displacement increases the “distance counter” by one, while diagonal displacements increase it by two. That relative distance is represented on the figure above with a darker blue coloring for cells closer to the nest and lighter blue as cells are further away from the nest.
Additionally, each cells “remembers” only the smallest distance from the nest that any ant has printed in it. By doing so, only the shortest known path to the nest is stored in each cell.
Ants: delivery mode
When an ant, either by moving randomly or by following a food trail, reaches a food source, it changes its mode to delivery. In this mode, ants only concern will be getting back to the nest following the shortest known path. The following two strategies are performed in this state.
Ant: trace back to the nest
The main goal will be to go back to the nest. They will do so by following the cells with a decreasing distance to the nest. For any single “step”, an ant will choose the cell with the smallest distance to the nest value.
Ant: leave food trace
Additionally, as ants move back to the nest, they will leave a “trace” on the cells they step on to signal other ants of the presence of food.
Just like ants “count” how many cells they have moved away from the nest, they will count how many cells they move away from the food source. This is the value that they will imprint on the cells they traverse. This way other ants will have a way of knowing which direction to follow to find the food source. The relative distance between a cell and the food source is represented by coloring each cell with a darker yellow tone as the cell gets closer to the food source in the figure above.
An extra feature of these “food trails” is that they are transient and disappear over time. They are “restored” when an ant traverses it again while delivering food.
The food trails are not relevant for ants tracing back to the nest, they are useful only for ants in scavenge mode. When delivering to the nest, each ant will follow the “best path” as described by the nest distance inscribed on the cells it traverses.
With the simple strategies described above (and some extra details), it was possible to have ants find optimal or close to optimal paths between the nest and the food sources. On the other hand, the “look and feel” of a real ant colony wasn’t reproduced.