tech dumps

hello@llwyd.io

24 October 2026

microboids 101

I’ve written previously about my microboids project; the original algorithm and the necessary mathematics in fixed point. I realised I had yet to do a write up of the overall implementation. This article aims to be as such.

microboids

microboids running on an ARM cortex M0+ microcontroller

Full source code is available here.

Introduction

microboids is an electronic implementation of the Boids algorithm on a micro controller. Boids is an algorithmic bird murmuration originally developed by Craig Reynolds in the 1980’s1,2. The algorithm begins with a number of birds (known as boids) and a set of rules that governs how they interact with each other1,2:

Every tick of the algorithm applies these rules to the birds and sets their next position and orientation as appropriate.

Hardware

I designed a custom PCB for microboids which consists of the following components:

microboids

Underside of the microboids circuit board

The full schematic can be found here.

Firmware

Screen Considerations

As discussed in a previous article the canvas for displaying the murmuration is in the range [-1.0, 1.0); represented using Q15 arithmetic. The struct pointf16_t is used to represent the (x,y) position in this format as such:

typedef struct
{
    int16_t x;
    int16_t y;
}
pointf16_t;

Prior to ‘drawing’ on the canvas this position is converted to an equivalent pixel (represented by column, page and bit) on the 128x64 resolution OLED display.

/* Format for a single bit on the SSD1306 display */
typedef struct
{
    uint8_t col;
    uint8_t page;
    uint8_t bit;
}
bit_t;

static bit_t PointToBit(const pointf16_t * const point)
{
    /* Scale from Q15 to uint8 */
    uint8_t x = QMath_Int16ToUInt8(point->x, 1U);
    uint8_t y = QMath_Int16ToUInt8(point->y, 2U);

    ASSERT(x < LCD_COLUMNS);
    ASSERT(y < (LCD_ROWS * LCD_PAGES));
    
    bit_t bit =
    {
        .col   = x,
        .page  = y >> 3,
        .bit   = y & ( LCD_ROWS - 1U ),
    };

    return bit;
}

Defining a bird

Each bird in the murmuration has the following properties:

The bird has two main states: Idle and Turning_X, where X is either N, E, S or T depending on the direction it is turning. The turning state is necessary for when the bird is near the edge of the canvas so that it can smoothly turn towards the centre and not exceed the edges.

#define NUM_BIRDS (48U)

typedef struct
{
    uint8_t angle;
    uint8_t avg_angle;
    pointf16_t p;
    bird_state_t state;
}
bird_t;

static bird_t bird[NUM_BIRDS];

Initialisation

Upon boot the firmware initialises the necessary peripherals (I2C for the display, GPIO for switch etc.) and configures the microcontroller to run at its maximum clock of 64MHz. With the hardware peripherals all configured the boids algorithm can then be initialised using Bird_Init().

#define NUM_BIRDS (48U)

extern void Bird_Init( uint32_t initial_seed )
{
    ASSERT(initial_seed != 0U);
    
    uint32_t rng = initial_seed;

    for( uint32_t idx = 0; idx < NUM_BIRDS; idx++)
    {
        rng = xorshift32(rng);
        int16_t x = (int16_t)(rng >> 16U);
        rng = xorshift32(rng);
        int16_t y = (int16_t)(rng >> 16U);
        rng = xorshift32(rng);

        bird[idx].angle = (uint8_t)(rng >> 24U); 
        bird[idx].avg_angle = bird[idx].angle;
        
        bird[idx].state = BirdState_Idle;

        bird[idx].p.x = x;
        bird[idx].p.y = y;
    }
}

Each bird is initialised with a randomised angle and position, the values generated using Xorshift, which generates pseudo-random numbers via shifts and XORs3.

static uint32_t xorshift32( uint32_t x )
{
    x ^= x << 13U;
    x ^= x >> 17U;
    x ^= x << 5U;

    return x;
}

The initial seed for the random number generator is derived from the microcontroller IC’s unique serial number. This 96-bit unique identifier4 is fed word by word (i.e. 32 bits at a time) into the microcontroller’s onboard Cyclic Redundancy Check (CRC) peripheral to produce a unique(ish) 32 bit seed. I went for this approach as I thought it would be interesting if each individual board had a unique seed so that they each had a personalised ‘starting point’. The process for generating the initial seed for the microcontroller is demonstrated in the snippet below:

#define UNIQUE_ID_BASE ( 0x1FFF7590 )
#define UNIQUE_ID_WORDS (96u / 32u)

_Static_assert(UNIQUE_ID_WORDS == 3u, "UNIQUE ID Incorrect size");

static uint32_t InitialSeed(void)
{
    /* Lazy way of enabling CRC */
    *((uint32_t *)0x40021038) |= ( 0x1 << 12 );
    
    /* Reset CRC */
    CRC->CR |= (0x1 << 0);
    
    volatile uint32_t * chip_id = (uint32_t *)UNIQUE_ID_BASE;
    uint32_t initial_seed = 0u;
    for(uint32_t idx = 0u; idx < UNIQUE_ID_WORDS; idx++)
    {
        CRC->DR = *(chip_id++);
        initial_seed = CRC->DR;
    }
    
    return initial_seed;
}

Runtime Loop

microboids

microboids algorithm running on desktop simulator

Every tick the algorithm loops through each bird and executes state-dependent code. The Idle state runs the boids algorithm on the bird while the Turning state runs an algorithm to gently turn the bird away from the edge of the canvas. Upon conclusion of each state the bird’s position is set as a pixel in the display buffer. Once all the birds have been updated the display buffer is written to the display as a single I2C transaction and the cycle starts again.

extern void Bird_Tick( void )
{
    for(uint8_t idx = 0; idx < NUM_BIRDS; idx++)
    {

        bird_t * const b = &bird[idx];

        /* Clear previous position from canvas */
        bit_t prev_bit = PointToBit(&b->p);
        Set(display_buffer, false, &prev_bit);
        
        switch(b->state)
        {
            case BirdState_Idle:
                Idle(b);
                break;
            case BirdState_TurningN:
            case BirdState_TurningE:
            case BirdState_TurningS:
            case BirdState_TurningW:
                Turning(b);
                break;
            default:
                ASSERT(false);
                break; 
        }
        
        b->state = NextState(b);

        /* Draw current position */
        bit_t bit = PointToBit(&b->p);
        Set(display_buffer, true, &bit);
    }
}

The tick is driven by a hardware timer (Timer 2) on the microcontroller configured to elapse every 31ms (roughly 30fps).

Determining the next state

Upon completion of the bird’s current state the NextState() function is called to determine whether the bird should be Idle or Turning. If the bird is near the edge of the canvas then it needs to transition to the Turning state. The edges of the canvas are offset with a fixed value labelled EDGE to define this region. Recalling that the canvas is defined by [1.0,1.0), the edge region east for example would be Q15_MAX - EDGE. If the bird entered this region, it would transition to Turning_E state that handles turning away from the east direction. When the bird is no longer in any edge-region it returns to the Idle state.

/* 0.15 ~= 0x1333 */
#define EDGE (0x1333)

_Static_assert(EDGE > 0, "Must be > 0");

static bird_state_t NextState(const bird_t * const b)
{
    bird_state_t next_state = BirdState_Idle;

    int16_t r = QMath_SubSat(Q15_MAX, EDGE, Q_NUM);
    int16_t l = QMath_AddSat(Q15_MIN, EDGE, Q_NUM);
    int16_t u = QMath_AddSat(Q15_MIN, EDGE, Q_NUM);
    int16_t d = QMath_SubSat(Q15_MAX, EDGE, Q_NUM);

    const pointf16_t * const p = &b->p;

    if( (p->x <= l) )
    {
        next_state = BirdState_TurningW;
    }
    else if( (p->x >= r) )
    {
        next_state = BirdState_TurningE;
    }
    else if( (p->y <= u) )
    {
        next_state = BirdState_TurningN;
    }
    else if( (p->y >= d) )
    {
        next_state = BirdState_TurningS;
    }
    else
    {
        next_state = BirdState_Idle;
    }


    return next_state;
}

Idle state (boids algorithm)

The Idle state runs the boids algorithm; applying the rules of separation, alignment and cohesion to each bird. The algorithm can be summarised as follows:

  1. Separation
    1. Determine nearby birds that are within the separation radius (and thus want to move away from)
    2. Calculate average position of nearby birds
    3. Rotate bird away from average position by SEP_ANGLE
  2. Cohesion
    1. Determine nearby birds that are within the cohesion radius (and thus move towards)
    2. Calculate average position of nearby birds
    3. Rotate bird towards average position by COH_ANGLE
  3. Move bird in direction of updated angle
  4. Alignment
    1. Calculate average angle of birds within the cohesion radius
    2. Determine shortest-angle-midpoint (SAM) between bird’s angle and average angle of birds within the cohesion radius.
    3. Set the bird’s angle to the calculated midpoint, i.e. half way between bird’s angle and average angle.

The algorithm involves a lot of averaging which isn’t trivial given that the M0+ processor does not have a divide operator5. The averaging is achieved by low pass filtering which can be achieved with only Add, Subtract and Multiply. Below is the averaging function which implemented a single pole low pass filter using Q15 Arithmetic:

int16_t QMath_Avg(int16_t p, int16_t x, int16_t alpha, uint16_t q)
{
    int16_t diff = QMath_SubSat(p, x, q);
    int16_t z = QMath_Mul(alpha, diff, q);

    int16_t y = QMath_AddSat(x, z, q);

    return y;
}

I’ve written a previous article about implementing single pole low pass filters here.

Collecting nearby birds

Each bird has a separation radius and cohesion radius which define two square hit-boxes6; if a nearby bird lies within this square then it is included as part of the separation and/or cohesion + alignment rules. For each bird every other bird’s position is compared to see if it lies within these regions. The collected number of birds is capped by MAX_NEARBY to save memory and processing time.

static bool IsPointInSquare(const pointf16_t * const b, 
const pointf16_t * const c, 
int16_t square_size)
{
    ASSERT(square_size > 0);
    
    bool result = false;
    /* Determine edges of the hit-box */
    int16_t r = QMath_AddSat(c->x, square_size, Q_NUM);
    int16_t l = QMath_SubSat(c->x, square_size, Q_NUM);
    int16_t u = QMath_SubSat(c->y, square_size, Q_NUM);
    int16_t d = QMath_AddSat(c->y, square_size, Q_NUM);

    /* Does the bird lie inside this? */
    if((b->x > l) && (b->x < r))
    {
        if((b->y > u) && (b->y < d))
        {
            result = true;
        }
    }
    return result;
}

/* Used to collect info of nearby birds based on index */
typedef struct
{
    uint32_t bird[MAX_NEARBY];
    uint32_t num;
}
nearby_t;

static void CollectNearbyBirds(bird_t * const current_bird, nearby_t * const near_birds, int16_t square_size)
{
    ASSERT(near_birds != NULL);
    ASSERT(square_size > 1);

    const pointf16_t * const c = &current_bird->p;
    near_birds->num = 0U;

    for(uint32_t idx = 0, collected = 0; (idx < NUM_BIRDS) && (collected < MAX_NEARBY); idx++)
    {
        ASSERT(near_birds->num < MAX_NEARBY);
        
        /* Don't need to collect itself */
        if(current_bird != &bird[idx])
        {
            const pointf16_t * const b = &bird[idx].p;
            if(IsPointInSquare(b, c, square_size))
            {
                /* Only collect other bird if it isn't turning */
                if(bird[idx].state == BirdState_Idle)
                {
                    near_birds->bird[near_birds->num] = idx;
                    near_birds->num++;
                    collected++;
                }
            }
        }
    }
}

Separation

#define SEP_ANGLE   (0x0A)
_Static_assert(SEP_ANGLE > 0, "Must be > 0");

#define SEP_RADIUS (0x0280)
#define COH_RADIUS (0x4000)

_Static_assert(COH_RADIUS > 0, "Must be > 0");
_Static_assert(SEP_RADIUS > 0, "Must be > 0");
_Static_assert(COH_RADIUS > SEP_RADIUS, "Cohesion radius must be larger than Separation radius");

quadrant_t quad = Quad_0;
/* Collect nearby birds */
CollectNearbyBirds(b, &nearby_sep, SEP_RADIUS);

if(nearby_sep.num > 0U)
{
    /* Calculate Average Point */
    const pointf16_t avg = AveragePoint(&nearby_sep);

    /* Which graph quadrant relative to the bird 
     * does the average point lie?
     */
    quad = TRIG_WhichQuadrant(&b->p, &avg);
    
    /* Calculate angle between bird's point and average point */
    uint8_t a = TRIG_ATan2(&b->p, &avg);
    
    /* Move away from the average point depending on the
     * angle and quadrant
     */
    switch(quad)
    {
        case Quad_0:
            if((a > DEG_225) || (a < DEG_45))
            {
                b->angle -= SEP_ANGLE;
            }
            else
            {
                b->angle += SEP_ANGLE;
            }
            break;
        case Quad_3:
            if((a < DEG_135) || (a > DEG_315))
            {
                b->angle += SEP_ANGLE;
            }
            else
            {
                b->angle -= SEP_ANGLE;
            }
            break;
        case Quad_1:
            if( (a < DEG_135) || (a > DEG_315) )
            {
                b->angle -= SEP_ANGLE;
            }
            else
            {
                b->angle += SEP_ANGLE;
            }
            break;
        case Quad_2:
            if((a > DEG_225) || (a < DEG_45) )
            {
                b->angle += SEP_ANGLE;
            }
            else
            {
                b->angle -= SEP_ANGLE;
            }
            break;
    }
}

Cohesion

Cohesion has the same logic as Separation except the angle is applied in the opposite direction.

#define COH_ANGLE   (0x01)
_Static_assert(COH_ANGLE > 0, "Must be > 0");
_Static_assert(COH_ANGLE < SEP_ANGLE, "Cohesion angle must be less than separation angle");

CollectNearbyBirds(b, &nearby_coh, COH_RADIUS);

if(nearby_coh.num > 0U)
{
    /* Calculate Average Point */
    const pointf16_t avg = AveragePoint(&nearby_coh);
    
    /* Which graph quadrant relative to the bird 
     * does the average point lie?
     */
    quadrant_t quad = TRIG_WhichQuadrant(&b->p, &avg);
    
    /* Calculate angle between bird's point and average point */
    uint8_t a = TRIG_ATan2(&b->p, &avg);
    
    /* Move towards the average point depending on the
     * angle and quadrant
     */
    switch(quad)
    {
        case Quad_0:
            if((a > DEG_225) || (a < DEG_45))
            {
                b->angle += COH_ANGLE;
            }
            else
            {
                b->angle -= COH_ANGLE;
            }
            break;
        case Quad_3:
            if((a < DEG_135) || (a > DEG_315))
            {
                b->angle -= COH_ANGLE;
            }
            else
            {
                b->angle += COH_ANGLE;
            }
            break;
        case Quad_1:
            if( (a < DEG_135) || (a > DEG_315) )
            {
                b->angle += COH_ANGLE;
            }
            else
            {
                b->angle -= COH_ANGLE;
            }
            break;
        case Quad_2:
            if((a > DEG_225) || (a < DEG_45) )
            {
                b->angle -= COH_ANGLE;
            }
            else
            {
                b->angle += COH_ANGLE;
            }
            break;
    }

}

Moving

The recently updated angle is used to propel the bird DISTANCE units in that direction.

#define DISTANCE (0xBFF)

/* Move bird distance in direction of angle */
TRIG_Translate16(&b->p, b->angle, DISTANCE);

Alignment

For my implementation the alignment happens after the separation and cohesion rules. After the bird has moved it will adjust its alignment towards the average angle of nearby birds:

if(nearby_coh.num > 0U)
{
    /* Calculate average angle of birds within cohesion radius */
    b->avg_angle = AverageAngle(b->avg_angle, &nearby_coh);
    /* Determine shortest-angle-midpoint and update the bird's
     * current angle */
    b->angle = TRIG_SAM(b->angle, b->avg_angle);
}

Turning state

When the bird enters the ‘Turning region’ defined by EDGE it transitions to the Turning state; which steers the bird back towards the centre of the canvas instead of applying the boids algorithm. The turning algorithm is described as follows:

  1. Calculate angle between bird and the centre of the canvas (i.e. (0.0, 0.0))
  2. Add PI to the result
  3. Calculate shortest-angle-midpoint between bird’s current angle and previously calculated angle
  4. Repeat previous step twice
  5. Update bird’s angle with result
  6. Move bird in direction of updated angle
/* Calculate angle between bird and centre of the canvas */
pointf16_t centre = {.x=0,.y=0};
uint8_t a = TRIG_ATan2(&b->p, &centre);

/* Add 180 Degrees (PI) */
a += DEG_180;

/* Determine shortest-angle-midpoint (x3) and update the bird's
 * current angle */
uint8_t delta = TRIG_SAM(b->angle, a);
delta = TRIG_SAM(b->angle, delta);
delta = TRIG_SAM(b->angle, delta);
b->angle = (uint8_t)delta;

/* Move bird in direction of updated angle */
TRIG_Translate16(&b->p, b->angle, DISTANCE);

Final Remarks

While the rules of the boids algorithm are clearly defined, a lot of the necessary parameters (such and turning angles, radii etc) were determined by experimentation and observing the resulting murmuration. One of the things I appreciate about art and engineering is the intersection of personalisation and the defined rules; the variables are all hand picked while the algorithm is clearly defined at a high level. There are plenty of implementations of boids out there but this is how I have implemented it. It makes for a nice trinket on my desk.

References

  1. C. Reynolds - Flocks, herds and schools: A distributed behavioural model link ↩ ↩2

  2. Craig Reynolds - Boids, background and update link ↩ ↩2

  3. Wikipedia - Xorshift link ↩

  4. RM0444 Rev 5 Section 41.1 link ↩

  5. Cortex-M0+ Devices Generic User Guide - Instruction set summary link ↩

  6. Wikipedia - Collision Detection link ↩