Flood Fill Maze Solving for Micromouse Robots

Flood fill is the algorithm that wins most Micromouse competitions, and it is a great introduction to planning under uncertainty. Unlike textbook pathfinding, a maze robot does not start with the full map—it has to discover walls as it drives. Flood fill is built for exactly that. Watch it run in the Maze Solver Simulator.

A distance field, not a path

Flood fill assigns every cell a number: its distance to the goal. The goal cells get zero. From there, each neighboring cell that is not blocked gets one more than its lowest neighbor, spreading outward until every reachable cell has a value.

The robot never stores a route. It just stands in a cell, looks at its neighbors, and steps to any one whose number is exactly one lower. The distance field is the plan, which is why it recovers gracefully when the map changes.

Optimism about unknown walls

The robot cannot see the whole maze, so flood fill treats every wall it has not yet sensed as open. That optimism produces the shortest possible estimate and keeps the robot moving toward the goal instead of exploring aimlessly.

When a sensor reveals a wall that was assumed open, the robot records it—on both sides of the shared edge—and recomputes the distance field. The plan corrects itself, and the robot continues from wherever it is.

Why the first run is not the shortest path

A common surprise: flood fill does not guarantee the shortest route on the first run. Because it acted on optimistic assumptions, it found a way to the goal, not necessarily the best one. Real Micromouse robots use two phases:

1. A search run that explores enough of the maze to build an accurate map.
2. A speed run along the shortest path that the completed map reveals.

Early on, efficient exploration matters more than first-run optimality.

Flood fill versus BFS and A*

Breadth-first search and A* plan over a graph you already know. Flood fill is designed for a maze you are still discovering: it re-floods whenever a new wall appears. Mathematically the flood is a breadth-first distance computation—the difference is that flood fill expects the map to keep changing and is cheap to recompute.

It also beats simple wall following (always keep one hand on a wall), which cannot reach a goal in the center of the maze and rarely finds a short route.

The sensing-planning-moving loop

void planOneCell(Maze& map, Robot& robot) {
  map.observe(robot.cell(), robot.senseLeftFrontRight());
  map.floodFill(centerGoals);
  Cell next = map.bestDescendingNeighbor(robot.cell());
  robot.turnAndMoveTo(next);
}

Keep sensing, mapping, planning, and motion as separate steps. That boundary is what lets the same planner run in a browser simulator, on your desktop, and on an ESP32 with real distance sensors and encoders.

Try it yourself

Step through the Maze Solver Simulator one cell at a time and watch the distance field recompute each time the robot discovers a wall. Seeing the numbers change is the fastest way to understand why the robot always has a plan.