Guide to The Minimalist Maze Solver: Optimizing the Flood-Fill Algorithm on an STM32 Blue Pill Micro-Mouse Chassis

The Minimalist Maze Solver: Optimizing the Flood‑Fill Algorithm on an STM32 Blue Pill Micro‑Mouse Chassis

Introduction

Building a fast, reliable maze‑solver for a Micro‑Mouse competition is a classic embedded challenge. This guide walks you through a minimalist implementation of the flood‑fill algorithm on the popular STM32 Blue Pill board mounted on a lightweight micro‑mouse chassis. You’ll learn how to squeeze every last millisecond out of the processor, reduce RAM usage, and keep your code clean enough to fit on a single .c file.

Keywords: Minimalist Maze Solver, Flood‑Fill Optimization, STM32 Blue Pill, Micro‑Mouse Chassis, Embedded Pathfinding.

1. Understanding the Maze Challenge

In a typical 16×16 IEEE Micro‑Mouse grid, each cell has four walls (North, East, South, West). The robot must explore unknown territory, map walls, and compute the shortest path back to the start. The flood‑fill algorithm assigns a distance value to every cell relative to the goal and then follows the decreasing gradient.

“The key to speed is not just a clever algorithm, but how you store and update the distance map on the MCU.” – Embedded Robotics Expert

2. Flood‑Fill Overview

The classic flood‑fill works in two phases:

1. Initialize every cell with a large number (e.g., 255).
2. Set the goal cell to 0 and propagate the value to neighbours, incrementing by 1 each step.

When the robot discovers a new wall, it re‑runs the flood‑fill on the updated map. Optimizations focus on reducing the number of passes and memory accesses.

3. Hardware Setup – STM32 Blue Pill + Micro‑Mouse Chassis

• Board: STM32F103C8T6 (72 MHz ARM Cortex‑M3, 20 KB RAM).
• Sensors: 4× IR distance sensors (front, left, right, back) using ADC channels.
• Motor Driver: L298N H‑bridge, PWM on TIM2.
• Power: 7.4 V Li‑Po with 5 V regulator for peripherals.

All components connect via the Blue Pill’s 40‑pin header; the firmware uses the STM32 HAL for portability.

4. Minimalist Code Architecture

The entire solver lives in maze_solver.c. The file is split into three logical sections:

1. Data structures – compact bit‑packed wall map and distance matrix.
2. Core flood‑fill routine – iterative, queue‑free, using a circular buffer.
3. Motor control & sensor reading – thin HAL wrappers for real‑time speed.

Tip: Keep the distance matrix in uint8_t (0‑255). This limits RAM to 256 bytes for a 16×16 maze.

// maze_solver.c – key definitions
#include "stm32f1xx_hal.h"

#define MAZE_SIZE 16
#define INF 255

// 2‑bit per wall: 00 – unknown, 01 – open, 10 – blocked
static uint8_t wall_map[MAZE_SIZE][MAZE_SIZE] = {0};
static uint8_t dist_map[MAZE_SIZE][MAZE_SIZE];   // distance to goal

// Simple circular buffer for flood‑fill frontier
static uint8_t queue[MAZE_SIZE * MAZE_SIZE];
static uint16_t q_head = 0, q_tail = 0;

/* -------------------------------------------------------------
   Flood‑fill – iterative, no recursion, no malloc
   ------------------------------------------------------------- */
void flood_fill(void) {
    // 1️⃣ Initialise all cells to INF
    for (uint8_t y = 0; y < MAZE_SIZE; y++) {
        for (uint8_t x = 0; x < MAZE_SIZE; x++) {
            dist_map[y][x] = INF;
        }
    }
    // 2️⃣ Goal cell (center) = 0
    uint8_t gx = MAZE_SIZE / 2, gy = MAZE_SIZE / 2;
    dist_map[gy][gx] = 0;
    queue[0] = (gy << 4) | gx;   // pack y|x into one byte
    q_head = 0; q_tail = 1;

    // 3️⃣ Propagation loop
    while (q_head != q_tail) {
        uint8_t cell = queue[q_head++];
        q_head &= (MAZE_SIZE*MAZE_SIZE-1);
        uint8_t cy = cell >> 4;
        uint8_t cx = cell & 0x0F;
        uint8_t cd = dist_map[cy][cx];

        // Examine 4 neighbours
        #define TRY(dir, nx, ny, mask)               \
            if ((wall_map[cy][cx] & mask) == 0) {    \
                if (dist_map[ny][nx] > cd + 1) {     \
                    dist_map[ny][nx] = cd + 1;      \
                    queue[q_tail++] = (ny<<4)|nx;   \
                    q_tail &= (MAZE_SIZE*MAZE_SIZE-1); \
                }                                     \
            }

        if (cy > 0)       TRY(N, cx, cy-1, 0x01); // North wall bit
        if (cx < MAZE_SIZE-1) TRY(E, cx+1, cy, 0x02); // East wall bit
        if (cy < MAZE_SIZE-1) TRY(S, cx, cy+1, 0x04); // South wall bit
        if (cx > 0)       TRY(W, cx-1, cy, 0x08); // West wall bit
        #undef TRY
    }
}

The macro TRY eliminates duplicated code and keeps the inner loop tight, which is crucial on a 72 MHz MCU.

5. Optimizing Memory & Speed

5.1 Bit‑Packed Wall Representation

Each cell stores four wall states in a single uint8_t using bit masks. This reduces the wall map from 256 bytes (if using bools) to 256 bytes anyway, but the bit‑wise checks are faster than array indexing.

5.2 Queue‑Free Propagation (Optional)

For very small mazes you can skip the queue entirely and perform a single pass scan until no changes occur. The trade‑off is more CPU cycles per pass but zero RAM for the queue.

5.3 Inline Assembly Hot‑Path (Advanced)

If you need sub‑millisecond reaction time, replace the TRY macro with an ARM‑thumb assembly block that reads and writes the distance matrix in a single LDRB/STRB pair. This guide keeps the code portable, so the assembly snippet is left as an exercise.

5.4 Compiler Optimizations

Build with -O3 -flto -ffast-math and enable __builtin_expect in critical branches:

#define likely(x)   __builtin_expect(!!(x), 1)
#define unlikely(x) __builtin_expect(!!(x), 0)

if (likely(wall_map[cy][cx] & OPEN_MASK)) { … }

6. Real‑World Testing & Tuning

After flashing the firmware, run the robot in an empty 16×16 grid. Record the following metrics (example data):

Metric	Unoptimized	Optimized
Average Cycle Time (ms)	4.8	2.3
Maximum RAM Usage (bytes)	304	256
Battery Consumption (mAh/Run)	45	38
Solution Speed (s)	28.6	22.1

Fine‑tune the PID controller for motor speed and adjust the sensor threshold to minimise false wall detections.

Show Debug Log Example

[00:00.001] Init – Goal (8,8)
[00.123] Wall detected N at (5,5)
[00.130] Flood‑fill started – queue size 1
[00.135] Cell (5,5) distance 12
…

7. Full Source Code Download

You can download the complete project (including Makefile, HAL config, and README) from the GitHub repository.

👉 Get the Code

8. Frequently Asked Questions

How do I reduce the flood‑fill runtime further?

Use a two‑phase approach: first run a coarse “wavefront” fill to the robot’s current vicinity, then switch to a fine‑grain fill when the robot is within 4 cells of the goal. This halves the number of cell updates per cycle.

Can I use a different MCU?

Yes. The algorithm is CPU‑agnostic. Port the HAL calls to your target (e.g., STM32F4, ESP32) and adjust the timing constants.

What if my maze is larger than 16×16?

Increase MAZE_SIZE and allocate the map in external SRAM or flash. Keep the distance type as uint16_t to avoid overflow.

Conclusion

By packing walls into bits, using an iterative queue, and leveraging the STM32 Blue Pill’s fast ARM core, you can build a minimalist maze solver that runs under 3 ms per flood‑fill iteration. The techniques shown here—memory‑tight data structures, micro‑optimizations, and clean code separation—are applicable to any embedded path‑finding problem.

Ready to race? Flash the firmware, place your robot on the start line, and watch the flood‑fill algorithm turn a chaotic maze into a smooth, high‑speed solution.