OpenStreetMap Route Planning (A*)

What it did

Load a real OpenStreetMap .osm extract (a neighborhood-sized chunk of road network) and find the shortest path between two clicked points. A* with a Euclidean heuristic, implemented from first principles in modern C++.

The pipeline

1. Parse .osm XML → graph of nodes (intersections) + edges (road segments with distance + road class).
2. Build adjacency list.
3. A* with g(n) = distance-so-far, h(n) = Euclidean distance to goal, f(n) = g + h.
4. Render the source map + the path overlay via io2d.

What was actually tricky

• std::priority_queue is a min-heap by default ordering on the value, not the priority. Need a custom comparator that compares f(n), or store (f, node) pairs and pop based on the first field.
• Closed-set / open-set bookkeeping. Forgetting to mark a node closed lets A* expand it multiple times with stale gs and silently degrades to BFS.
• The Euclidean heuristic is admissible but loose. On a road graph it underestimates a lot — A* devolves toward Dijkstra-like behavior. A road-class-weighted heuristic (or just speeding up with a contraction hierarchy) is the real-world fix.

What I’d do differently with hindsight

• Use a contraction hierarchy for any non-toy graph. Pre-process the network into shortcut edges, then queries become near-O(log n). Every commercial routing engine does this.
• Multi-modal cost. Distance is the wrong objective; travel-time with road-class speeds is what people actually want. Then A* on expected time.
• A is for the planner; the controller is downstream.* This project conflates “find a path” with “draw a path.” A real autonomy stack separates global planning from local motion control, and the seams matter.

What it taught me

Two things. First, classical graph search is still the right answer for most “shortest X” problems — fancy ML approaches add a lot of weight for usually-marginal returns. Second, modern C++ (the project required C++17) is fine — the language reputation is worse than the experience, especially with a graph library and <algorithm> on hand.