Bonus: Find the goal in an unseen maze

Everything at once

A new maze, a random start in its bottom rows, and a green goal in the far corner. There's no map and no route: the rover has only its lidar and your code from steps 4 to 6, which the starter gives you as working functions.

Optimism

You can't plan through a map you haven't made. You can plan through a map you're still making, though, if you decide what to believe about the parts you haven't seen. The simplest choice is optimism: treat every unknown cell as free. The plan then runs straight at the goal through unexplored space, and the rover drives it, mapping as it goes. When a newly seen wall crosses the plan, plan again.

Optimism has a neat property here. Unknown cells already count as free, so learning more can only add walls, and a plan can only get longer. There's never a better route to miss, so you need to replan only when a cell on your current path turns into a wall.

The pieces

• update(logodds, pose, scan) adds a scan to the map (step 4).
• plan_grid(logodds) blocks every cell within the rover's radius plus 1 cm of a cell with log-odds above 0, and leaves everything else free: the configuration space of what you know.
• free_cell(grid, logodds, xy) finds the free cell nearest a point; astar plans on the grid (step 5), and logodds.center(rows, cols) turns cells into points.
• pure_pursuit steers (step 6), with one change: if the lookahead point is more than 30° off the heading, it turns on the spot first. A new plan can point the rover back the way it came.

Your task

Finish navigate(goal). Every 4 ticks of 0.05 s (5 times a second) add a scan to the map. Then, if there's no path yet or any of its cells is now blocked in plan_grid(logodds), plan a new one from the rover to the goal. Every tick, drive for 0.05 s with pure_pursuit. Return how many plans you made. The Images tab shows your map and the latest plan.

The checks want the rover within 3 cm of the goal in under 60 s, without a bump, from any start.