The problem
I wanted to see pathfinding algorithms fight on a real map, not a textbook grid
Every Dijkstra vs. A* comparison I'd seen before this was on a toy grid, 20x20 squares, uniform edge weights, the kind of example that makes A* look like it barely matters. That's not what a real road network looks like. Manhattan has one-way streets, dead ends, avenues that are way faster than side streets, and an actual irregular graph shape. I wanted to parse the real thing and watch the algorithms explore it live instead of trusting a diagram in a textbook.
So Arcen loads an OSM extract of Manhattan into a graph, drives a few hundred vehicles around it continuously, and lets you click any two intersections to race Dijkstra, A*, and Bidirectional Dijkstra against each other on the same query. The sidebar shows exactly how many intersections each one had to check before it found the route.
Architecture
The moving pieces
On startup the backend pulls a Manhattan .osm file from S3 (or reads it locally in dev), parses it into a graph, and starts a 30 Hz tick loop that advances every vehicle and broadcasts positions over STOMP WebSocket. The Next.js frontend subscribes to that feed and draws the fleet on a MapLibre GL map, and hits plain REST endpoints for one-off route requests and the three-way benchmark.
How it works
~70k nodes, ~150k edges, no objects on the heap
The OSM file is a few hundred MB of XML, so I parse it with StAX instead of loading a DOM (which would've meant holding the whole tree in memory at once). It's a pull-based cursor: ask for the next node, next way, next tag, one event at a time. Only ways tagged with a driveable highway value get kept, and anything missing a maxspeed tag falls back to a default speed table keyed by road class (residential streets get 30 km/h, motorway links get 60, and so on).
The graph itself isn't a Map<Node, List<Edge>>. It's a set of parallel primitive arrays, the classic CSR-style layout: head[u] gives the first outgoing edge of node u, and each edge points to the next one from the same node via next[e]. No Node or Edge objects, no pointer chasing across the heap during a search. Edge weights are travel time in seconds (distance divided by the road's speed limit), not distance, so the "shortest" path is actually the fastest one, the way a GPS route actually behaves.
How it works
Three algorithms, one graph, same query
Click two points and /api/benchmark runs Dijkstra, A*, and Bidirectional Dijkstra against the exact same source/destination pair and reports nodes explored and compute time for each. Dijkstra expands outward in every direction with no sense of where the destination is. A* adds a heuristic, straight-line distance from the current node to the target divided by 120 km/h (the fastest road speed in the dataset), so it never overestimates the remaining time and stays admissible, and that alone biases the search toward the goal instead of expanding a circle around the source. Bidirectional Dijkstra runs two searches at once, one forward from the source, one backward from the destination over a reversed graph (so one-way streets are still respected), and stops as soon as the frontiers meet.
On this graph A* consistently checks far fewer intersections than plain Dijkstra, and Bidirectional Dijkstra usually lands somewhere between the two, sometimes beating A* on longer routes since both of its searches only have to cover half the distance.
How it works
30 fps over WebSocket, with cars that reroute mid-drive
A Spring @Scheduled(fixedRate = 33) tick fires roughly 30 times a second. Each tick advances every vehicle along its precomputed A* route by speed × deltaSeconds, tops the fleet back up to the target count by spawning new vehicles on random node pairs, and broadcasts every active vehicle's interpolated lat/lon and heading to /topic/vehicles. The frontend doesn't re-render React on every frame, it just shoves the new GeoJSON straight into a MapLibre source inside a requestAnimationFrame loop, which is the only way a few hundred moving points stay smooth in the browser.
Blocking a road is more than a visual overlay. Every tick checks whether any vehicle's remaining path crosses a newly blocked edge, and if it does, that vehicle gets re-routed from its current position to the same destination with a fresh A* call. Blocked edges are just a ConcurrentHashMap set on the graph that every router checks and skips over, so Dijkstra, A*, and the benchmark all automatically route around whatever's closed without knowing anything special about it.
What I'd fix
Two linear scans I've left alone because they haven't hurt yet
Snapping a click to the road network is O(n) and O(E)
Every time you click the map, the backend has to figure out which intersection (or which road segment, for blocking) you actually meant. Right now that's a straight linear scan: Haversine distance to every one of the ~70k nodes for a route click, or a point-to-segment distance check against every one of the ~150k edges for a road-block click.
// Finds the internal node index of the road intersection closest to
// the given geographical coordinate using the Haversine formula.
// ...
// O(n) linear scan — fast enough for cities up to ~100k nodes;
// a KD-tree can be added later for larger maps.
public int nearestNode(double lat, double lon) { ... }On Manhattan-sized data it's fast enough that I've never noticed it on a click. It would fall over on a state-sized graph, and the fix (a KD-tree or a grid index over the nodes) is a comment I wrote to myself and never came back for.
Bidirectional Dijkstra rebuilds the reverse graph every single query
The backward half of Bidirectional Dijkstra has to walk edges in reverse (so a one-way street gets traversed the right direction going backward from the destination). Instead of building that reversed graph once when the map loads, the router calls GraphBuilder.buildReverse(graph) fresh inside every single search, which allocates a full second copy of the edge arrays for every query that algorithm runs, including every vehicle spawn that happens to pick it.
It works because the graph is small enough that rebuilding the reverse costs low single-digit milliseconds. But it's clearly wasted work, and caching the reverse graph alongside the forward one at load time is the obvious next change I haven't made.