Floodfill is the core maze-solving algorithm used in Micromouse competitions.
It calculates distance values (Manhattan distances) across the maze and directs the mouse to the lowest-valued neighboring cell.

Each cell in the maze is assigned a value equal to its Manhattan distance from the goal.
The mouse moves toward the smallest value until it reaches the center.

1. Initialize Maze

   • Set all cells as "unvisited" or "infinite distance".
   • Assign goal cell(s) a distance of 0.

2. Propagation

   • Add goal cell(s) to a queue.
   • While queue is not empty:
     • Dequeue current cell.
     • For each accessible neighbor:
       • If that cell’s distance is greater than current + 1, update and enqueue it.

3. Wall Updates

   • Each time a new wall is detected, recompute local distances.
   • Re-run floodfill as needed for real-time path correction.

4. Movement

   • Always move to the neighboring cell with the smallest distance value.

void floodfill_update(int goalX, int goalY) {
    reset_maze_distances();
    queue_add(goalX, goalY);
    maze[goalX][goalY] = 0;

    while (!queue_empty()) {
        cell_t c = queue_pop();
        for (dir in directions) {
            if (!wall_exists(c, dir)) {
                nx = c.x + dx[dir];
                ny = c.y + dy[dir];
                if (maze[nx][ny] > maze[c.x][c.y] + 1) {
                    maze[nx][ny] = maze[c.x][c.y] + 1;
                    queue_add(nx, ny);
                }
            }
        }
    }
}

Below is a simple flood fill implementation on an 8×8 grid. It recursively fills connected empty cells starting from a given point.

#include <stdio.h>

#define ROWS 8
#define COLS 8

// Grid: 0 = empty, 1 = wall, 2 = filled
int grid[ROWS][COLS] = {
    {1,1,1,1,1,1,1,1},
    {1,0,0,0,1,0,0,1},
    {1,0,1,0,1,0,0,1},
    {1,0,1,0,0,0,1,1},
    {1,0,1,1,1,0,0,1},
    {1,0,0,0,0,0,0,1},
    {1,1,1,1,1,1,0,1},
    {1,1,1,1,1,1,1,1}
};

void printGrid() {
    for(int i=0; i<ROWS; i++) {
        for(int j=0; j<COLS; j++) {
            if(grid[i][j] == 1) printf("# ");
            else if(grid[i][j] == 2) printf(". ");
            else printf("  ");
        }
        printf("\n");
    }
    printf("\n");
}

void floodFill(int x, int y, int target, int replacement) {
    if (x < 0 || x >= ROWS || y < 0 || y >= COLS) return;
    if (grid[x][y] != target) return;
    grid[x][y] = replacement;
    floodFill(x+1, y, target, replacement);
    floodFill(x-1, y, target, replacement);
    floodFill(x, y+1, target, replacement);
    floodFill(x, y-1, target, replacement);
}

int main() {
    printf("Original grid:\\n");
    printGrid();
    floodFill(1, 1, 0, 2);
    printf("After flood fill:\\n");
    printGrid();
    return 0;
}

Output Example:

Original grid:
########
#      #
# #  # #
# #   ##
# ###  #
#      #
###### #
########

After flood fill:
########
#......#
# #..# #
# #...##
# ###..#
#......#
######.#
########

• Represent maze as two 16×16 grids: one for walls, one for distances.
• Use a queue (FIFO) for BFS propagation.
• Use structs for cell coordinates (x, y, value).
• Initialize walls to “open”; update as IR sensors detect new ones.
• Print current maze distances for debugging.

You can test your algorithm using:
👉 Mackorone’s Micromouse Simulator

Steps:

1. Download the simulator and open in a code editor.
2. Replace solver.c and solver.h with your floodfill version.
3. Run simulation and verify correct movement.

Deliverable:
A working C implementation of Floodfill that successfully solves a 16×16 maze and adapts to discovered walls in real-time.