A* is the smartest way to search a maze. Every candidate cell gets a score: the cost so far (steps already taken) plus a guess of what remains (distance to the goal, as the crow flies). Because the guess never overestimates, the first route the search completes is guaranteed to be the shortest — and because the guess pulls the search toward the goal, A* explores far fewer cells than a blind search.
IRIN O1 (UPM, 2019) — a Webots e-puck controller with a
subsumption-style architecture (battery management, wall following,
light seeking) whose navigation layer plans paths with
A* search on a 20×20 occupancy grid. The planner is extracted
here as astar.py / astar.js
(1:1 ports, tested).
A* expands states in order of the evaluation function
\[ f(n) = g(n) + h(n) \]
where \(g(n)\) is the cost from the start to \(n\) and \(h(n)\) an admissible heuristic. The controller moves in 8 directions with a straight-line bias: straight moves cost \(0\) extra, diagonals cost \(2\), and the priority is \(f(n) = g(n) + 10\,h(n)\) with the Chebyshev heuristic
\[ h(x,y) = \max\bigl(|x - x_{\text{goal}}|,\; |y - y_{\text{goal}}|\bigr) \]
A priority queue holds the open set; expanded cells move to the closed set. Each cell stores the direction back to its parent (encoded as \((i + 4) \bmod 8\)), so the route is reconstructed by walking backward from the goal — exactly as in the C++ controller.
The visualizer animates the search: amber = open set, blue = closed set, green = the final route. Because \(h\) is admissible (never overestimates), the first route found is optimal.
Paint walls by clicking or dragging on the 20×20 grid, right-click (or the eraser button) to clear cells. Set Start / Set Goal pick the endpoints (drag them to move). Press Find path to run the search — watch the open set expand, the closed set fill, and the optimal route appear. The O1 arena preset loads the layout from the lab's Webots world.
github.com/alejp1998/irin_o1 — C++ controller, Python port, tests.