Plan the route

Point your robot at a goal behind walls. There is no line to ride and no rays to read this time, just a map, a start, and a goal with walls in between. Before it moves a single wheel, the robot has to plan the whole route.

The map on the right is a grid of cells. A* plans by exploring it one cell at a time, always expanding the most promising cell so far: the one with the smallest cost to reach it plus estimated cost still to go. That estimate is a heuristic, a hunch you write in code. A good hunch keeps the search pointed at the goal; a bad one, or none at all, sends it wandering.

The starter ships with no hunch. Read the skeleton in the editor: a plan_path that hands the engine your heuristic h(a, b), and an h that returns 0 for every cell. Press Run and watch what a search with no sense of direction does.

With h returning 0, every cell looks equally promising, so A* spreads out evenly in all directions and floods the board until it stumbles onto the goal. That is exactly Dijkstra’s algorithm: A* with the heuristic switched off.

It does reach the goal, so the first checkpoint clears. But look at the cell count under the grid: it explored most of the open board to get there. Reaching the goal is easy; reaching it without searching the whole map is the real problem, and that is the next gate.

Now give the search a sense of direction. Replace the return 0 inside h with the Manhattan distance from the cell being scored to the goal: the steps across plus the steps down, since the robot moves one cell at a time along the grid. Each cell carries a .col and a .row, so the guess is the gap in columns added to the gap in rows. Take the size of each gap, never a negative, then add them.

Press Run again. Same search, same path, but now every cell that steps toward the goal scores better than one that steps away, so A* stops flooding and beelines. Watch the cell count collapse. When it drops under the bar, the second checkpoint clears and the lesson is done.