A navigation heuristic, not a graph search

Skip the road graph.
Draw the line instead.

Real navigation engines build a graph of every road and search it — Dijkstra, A*, thousands of nodes evaluated per query. TraceRoute tries a cheaper idea: draw a straight line from A to B, and pick whichever waypoints sit closest to it. No graph, no search tree — just projections and a sort. Order-of-magnitude less computation per route, which means less CPU time and less energy per query.

Try the routing engine ↓ See how it works
Same routing logic, 3 languages: 🐍 Python ⚙️ C++ ☕ Java + JavaFX

Try it as a router

Think of the dots as waypoints — intersections, charging stations, delivery stops. Pick a start and destination; the red dots are the ones your route would actually pass near. Teal marks the origin, purple the destination.

Why this is cheaper than a real router

A production navigation engine searches a graph. TraceRoute replaces that search with four constant-time geometry steps per waypoint — no traversal, no priority queue.

  1. 01

    Draw the direct line

    Instead of a road graph, TraceRoute starts from the one line every router already knows: the straight shot from origin to destination.

  2. 02

    Project each waypoint

    Every candidate point is dropped perpendicularly onto that line — one multiplication-heavy step, no recursion, no queue.

  3. 03

    Discard what's off-route

    Waypoints whose projection falls outside the origin–destination segment are dropped — they'd be a detour, not a shortcut.

  4. 04

    Rank by detour distance

    What's left is sorted by how far it sits off the direct line — the closest ones are the cheapest real-world route to follow.

Built for constrained hardware

The same routing logic, tuned for three very different power budgets.

🐍 Python

Prototype

Where the routing heuristic was proven out — matplotlib made every projection error visible immediately.

⚙️ C++

Low-power target

Manual memory management, no runtime, no GC pauses — the profile you'd want on an embedded or battery-powered device.

☕ Java

Production

Powers this demo's routing engine, plus a native JavaFX desktop visualizer for inspecting routes offline.