Path Planning and Mapping: Flood Fill to SLAM
You can plan a route through a known grid, replan as new obstacles appear, and explain how a robot builds the map it is planning on.
Reactive navigation gets a robot around a room without ever knowing where it is. That runs out quickly: a purely reactive robot cannot be told go to the kitchen, and it will happily loop forever in a room shaped like a horseshoe. Planning is the answer, and it needs something reactive control never has—a map.
This path starts where the map is free. In a maze, flood fill floods distances outward from the goal and the robot simply walks downhill, replanning the instant it discovers a wall it had assumed was open. Then the world gets messier: A* plans across an occupancy grid where cells have costs, obstacles need inflating, and the heuristic decides whether your planner is fast or merely correct.
The last node is the honest one. Every planner above assumes you have a map, and a real robot has to build one while moving on wheels that lie to it. SLAM is what happens when mapping and localization refuse to be separated, and loop closure is what stops the map bending as odometry drifts. An IMU earns its place here for the same reason: it measures rotation directly, which wheels that slip simply cannot.
Before you start
You need to be comfortable with two-dimensional arrays and basic algorithmic thinking — queues, and the idea of visiting cells in an order. The motor control path is worth doing first, because every planner here assumes the robot can execute a commanded move and report roughly how far it went.
What you will be able to do
- Flood a grid with distances from a goal and follow the gradient down to it.
- Run A* with a heuristic you can show never overestimates, and explain why that property is what makes the result shortest.
- Turn range readings into an occupancy grid by ray casting, updating free and occupied cells separately.
- Say why odometry alone cannot produce a usable map over a long run, and what SLAM adds.
Where people get stuck
A heuristic that overestimates. A* only guarantees the shortest path when the heuristic never claims a distance larger than the true remaining cost. Using Euclidean distance on a 4-connected grid, or scaling a heuristic up to make the search faster, silently returns paths that are not shortest.
Planning for a point robot. The path is computed through the grid, but the robot has width. A route that grazes a corner is geometrically valid and physically a collision. Inflate obstacles by the robot’s radius before planning, and the problem disappears.
Treating unknown as free. A cell nothing has observed is not empty — it is unmeasured. Plan through it as free space and the robot confidently drives into whatever was never seen. Unknown is a third state, and it needs to stay a third state.
Diagonal moves costing one. On an 8-connected grid a diagonal step covers √2 cells, not one. Charging it as one produces paths that prefer staircases and distances that are simply wrong.
Assuming the robot is where odometry says. Every planner here operates on a pose. Wheel odometry drifts without bound, so a perfect plan is executed from a position that is increasingly fictional. That gap is the entire motivation for the last node on this path.
What you need
| What | Why this path needs it | Notes |
|---|---|---|
| Comfort with 2D arrays and queues | Every algorithm here is a loop over a grid | No advanced maths; a queue and a nested loop is the whole toolkit |
| A robot that executes commanded moves | A plan is worthless if the robot cannot drive it | The motor control path gets you here |
| A gyro or IMU | Wheels cannot measure a rotation they slipped through | MPU-6050; the mapping nodes depend on heading |
| A range sensor, ideally scanning | Cells only become known by being measured | A servo-swept sonar is enough to build a crude grid |
| Somewhere to visualise a grid | Debugging a planner by watching a robot is nearly impossible | Print ASCII to serial, or use the labs on this path |
The two labs run entirely in the browser, so you can complete the flood-fill and coverage nodes with no hardware at all.
Why the path runs in this order
The maze comes first because the map is free. In a micromouse maze the world is a grid by construction — cells are a known size, walls are on cell boundaries, and the robot’s position is always a cell index. That removes every perception problem at once and leaves only the planning, which is the thing you are here to learn. Flood fill in a known grid is the cleanest possible introduction to “compute a distance field, then walk downhill”.
A* comes second because it removes the maze’s conveniences one at a time. Cells now have costs rather than just walls. The grid is larger, so expanding all of it is wasteful and a heuristic becomes worth having. The robot has width, so obstacles need inflating. And cells can be unknown, which is a genuinely new idea the maze never needed.
Occupancy grids come third because they are where the map stops being given to you. Ray casting turns a range reading into evidence about many cells at once — everything along the ray is more likely free, the endpoint is more likely occupied — and updating those two separately is the whole technique.
The IMU sits here deliberately. It arrives at the exact node where heading error starts writing itself into the map, because a gyro measures rotation directly and wheels that slip simply cannot.
SLAM comes last because it is the admission that the previous nodes were assuming something false. Every planner above operates on a pose, and every pose above came from odometry that drifts without bound. SLAM is what happens when you stop pretending mapping and localisation can be solved separately.
Coverage closes the path because it is the problem that most obviously needs a map and most obviously cannot be done reactively. “Have I been everywhere?” is a question only memory can answer.
Checkpoints: how to know a stage landed
| Stage | The check | What a pass looks like |
|---|---|---|
| Flood fill | Print the distance field for a small maze | The goal is 0, values increase outward, and walls create the detours you expect |
| Replanning | Reveal a wall the robot had assumed open | The field updates and the robot’s next move changes — without re-exploring |
| A* correctness | Run it on a grid where you know the answer by hand | Same length as the hand-computed shortest path, every time |
| Admissibility | Deliberately scale your heuristic up by 2× | The search gets faster and the path gets longer — now you have seen the trade |
| Diagonal cost | Plan across open space on an 8-connected grid | The path is a straight diagonal, not a staircase; diagonals cost √2 |
| Obstacle inflation | Plan past a corner with inflation off, then on | Off, the path grazes the corner; on, it clears by the robot’s radius |
| Occupancy grid | Sweep a sensor across a doorway and render the grid | Free space appears along the rays, occupied cells at the ends, unknown behind walls |
| Unknown handling | Ask your planner to route into unmapped space | It refuses, or it commits deliberately — either is fine, guessing is not |
| Drift | Drive a closed loop and compare the start and end of the map | The map does not close — that gap is exactly what loop closure exists to fix |
| Coverage | Run a planned sweep and a random walk for the same duration | The planned sweep covers far more, and you can state both percentages |
Where this path stops
This path plans in a static, two-dimensional, known-size world. Each of those words is a limitation worth naming.
Static. Nothing here handles a person walking across the plan. Dynamic obstacles need a local planner running underneath the global one, replanning far faster than A* over a whole grid can.
Two-dimensional. A grid of free and occupied cells is a floor plan. It cannot represent a table you can drive under but not through, which is why serious robots use 3D representations or layered costmaps.
Grid-based. Sampling planners such as RRT and RRT* handle high-dimensional spaces — a robot arm’s joint space, for instance — where a grid is hopeless. They trade the shortest-path guarantee for the ability to work at all.
The path also does not cover particle filters or Monte Carlo localisation, which is how a robot finds itself in a map it was given rather than one it is building. That is the simpler and far more common problem, and it is worth knowing it exists before reaching for full SLAM.
Learning roadmap
The path
Follow the nodes in order—each unlocks the next once you have done it. Your progress saves on this device.
0 / 9 done
Common questions
Frequently asked questions
What is the difference between flood fill and A* for robot path planning?
Flood fill computes the distance from the goal to every cell in the grid, so the robot can then walk downhill from wherever it happens to be. A* searches from a single start toward a single goal and expands only the cells a heuristic suggests are promising. Flood fill is the right choice in a micromouse maze, because the robot is constantly discovering new walls and needs to replan from a new position every few cells—having every cell's distance already computed makes that free. A* is the right choice on a large grid where you plan once from a known start and expanding the whole map would be wasteful.
Why does my A* path clip the corners of obstacles?
Because you planned for a point and the robot has width. The path is geometrically valid through the grid and physically a collision, because the planner never knew the robot occupies more than one cell. The standard fix is to inflate every obstacle by the robot's radius before planning—grow the occupied cells outward—so that any path the planner finds is automatically clear for the real robot. This is much simpler and more reliable than trying to check clearance while searching.
What makes an A* heuristic admissible, and why does it matter?
An admissible heuristic never overestimates the true remaining cost to the goal. That single property is what guarantees A* returns the shortest path—overestimate anywhere and the search can commit to a route it should have rejected. The common ways to break it are using Euclidean distance on a 4-connected grid, where the true cost is Manhattan and always at least as large, and deliberately scaling the heuristic up to make the search faster. The second is a real technique, but it trades the shortest-path guarantee away, and you should know you are trading it.
Do I need SLAM for a hobby robot?
Only when the robot must know where it is over a long run in a space it has not been given a map of. If you can supply a map, localisation alone is much simpler. If the space is small enough that odometry drift stays tolerable—a maze, a single room, a few minutes of driving—you do not need it either. SLAM earns its complexity when both conditions fail at once, and that is a real threshold rather than a badge: plenty of genuinely capable robots never need it.
Why does my occupancy grid map bend as the robot drives?
Because odometry drift is being written into the map. Every scan is placed at the pose the robot believed it had, so a heading estimate that has slowly rotated puts a straight corridor into the map as a curve. Nothing about the mapping is wrong—it is faithfully recording a pose that is fiction. This is precisely what loop closure fixes: recognising that the robot has returned somewhere it has been before, and correcting the whole trajectory so the two observations agree.
Why should unknown cells not be treated as free space?
Because a cell nothing has observed is unmeasured, not empty, and the difference decides whether the robot drives into things it never saw. Treat unknown as free and the planner will happily route through a region no sensor has ever covered—which is usually exactly where the furniture is, since occluded space and occupied space correlate strongly. Keep unknown as a distinct third state alongside free and occupied, and decide deliberately whether a given planner is allowed to route through it.