Ant Colony Simulator

This project was inspired by Craig W. Reynold's paper on steering behaviors and Sebastian Lague's video on ant and slime simulations. I originally wrote this in college using Qt tools but was never satisfied with how it turned out. This year I decided to port it over to SFML and finish the features I was itching to implement using Neovim as my C++ code editor. This workflow was much lighter on my laptop whose age is starting to catch up to it. The source code is here. Now let's dive into the project.

Overview

The project utilizes object oriented programming to separate concerns and keep things clean and readable. The entry point of the application starts in main.cpp where it initializes an SFML window and instantiates the world object.

The World Class

The World class sets up the food, home, pheromones, and most importantly, our ants, while also managing updates to the simulation's entities and drawing them in the SFML window. There's also a small button initialized here to add ants to the world. The Food and Home objects are simple SFML shapes and drawable entities that we place in the world, but the magic happens with the Ant and Pheromone classes.

The Ant Class

Take a look at the Ant.h file and you'll find regular setters and getters many C++ classes define. In this post I want to touch on the following private members of the Ant class:

• sf::Vector2f position
• sf::Vector2f velocity
• sf::Clock clock
• std::unique_ptr<IMovementBehavior> movementBehavior

These members are at the heart of the Ant's behaviors in the simulation. When spawned, ants begin at the center of the world and are given randomized velocities, but most importantly, they are initialized with the wandering behavior. This wandering behavior (and other behaviors) uses a simplified 2D model for point particle physics which combines steering algorithms with discrete time integration to adjust the ant's velocity and achieve the desired behavior. Let's go over how I implemented this movement using basic physics principles. I'll assume you have a grasp of particle kinematics (motion of point particles).

Position and Velocity

In continuous time, position $\vec{p}(t)$ and velocity $\vec{v}(t)$ are related by:

However, computers and programs like SFML don't run on continuous time, but rather on really fast discrete time intervals that make the simulation look continuous. We have to modify this relationship to account for every frame rerender that SFML relies on to give our simulation life. To do so we use the discrete time relationship for position and velocity, using $\Delta t$ as our timestep in between each interval:

Rearranging to get the new position after a timestep $\Delta t$ gives us:

This is implemented in the code with the following line in the Ant's update method: position += velocity * deltaTime

But wait, if velocity $\vec{v}(t)$ were constant, the ant would simply move in a straight line and wouldn't display any wandering behavior at all, I mean what kind of ant wanders in a straight line, right? This is where steering behaviors come in. They are algorithms that change the velocity of an ant through a calculated and applied steering acceleration on every timestep $\Delta t$.

Steering Acceleration

The wandering movement algorithm found in the WanderBehavior.cpp file uses the calculateSteering() function to calculate a steering acceleration that we use to modify the ant's velocity on every timestep, which results in a more natural-looking wandering behavior. While Craig Reynolds' original paper describes this in terms of steering forces (refer to his paper here, particularly in the section describing Wandering) our implementation uses a simplified point-particle model where we work directly with acceleration.

Figure 1: Visualization of the wandering behavior algorithm

The algorithm works by maintaining a wander target point that moves along a set circular path called the wander circle placed directly in front of the ant. Here's how the acceleration vector is calculated step by step:

1. We maintain a wander target vector $\vec{w}_t$ that points to a position on the wander circle of radius $r_c$
2. On each frame, we add a small random displacement vector of length $r_j$ (jitter radius) to $\vec{w}_t$ wanderTarget += getRandomUnitVector() * wanderJitter;
3. This new wander vector is reprojected back onto onto the wander circle by normalizing it and multiplying by $r_c$, the radius of the wander circle wanderTarget = normalize(wanderTarget) * wanderRadius;
4. The wander circle itself is positioned at a distance $d_w$ in front of the ant in the direction of its current velocity at all times (called the wander distance). We calculate this wander distance vector $\vec{d}_w$ by normalizing the velocity of the ant (which gives us its direction) and multiplying by $d_w$

sf::Vector2f currentDirection = normalize(currentVel);
sf::Vector2f antToWanderCircle = currentDirection * wanderDistance;

5. The steering acceleration vector is then calculated with the following formula: $$\vec{a}_s = \vec{d}_w + \vec{w}_t$$

and implemented with: sf::Vector2f steeringAcceleration = antToWanderCircle + wanderTarget;

This produces an acceleration vector that changes smoothly over each time step, creating a natural-looking wandering behavior. Using Euler integration, we apply this steering acceleration to the ant's current velocity with the discrete time relationship

This is implemented simply with:

velocity += steeringAcceleration * deltaTime

Of course we don't want the ant to pass a certain velocity threshold, so we clamp the new velocity using the clamp function:

// from Ant.cpp
    velocity = Vector2Utils::clamp(velocity, MAX_SPEED);
// from Vector2Utils.h
  static sf::Vector2f clamp(const sf::Vector2f &v, float maxLength) {
    float sqrMag = squaredMagnitude(v);
    if (sqrMag > maxLength * maxLength) {
      float scale = maxLength / std::sqrt(sqrMag);
      return v * scale;
    }
    return v;
  }

Boundary Handling

As the Ant wanders it'll eventually reach the boundary of the window, at which point we want to make sure it reverts its path and doesn't escape our simulation (Good afternoon, Good evening, and Good night!).

So when an ant hits the window boundaries, its velocity component normal to the boundary is reversed:

And that's the wandering behavior in a nutshell. The next step in the simulation is to have ants deposit pheromones and follow them based on the pheromone type! So let's take a look at the Pheromone class.

The Pheromone class