I
Ivan Kuznetsov
Guest
I asked my sea router for a route from the Atlantic side of Panama to the Pacific side. It returned 10,337 nautical miles, going all the way around South America. The Panama Canal is about 50 nautical miles long.
The router is auto-sea-way, an open-source routing graph I generated for the whole ocean surface of the planet. I built it because I could not find one with enough detail for Rhumb, the marine navigation app I make. The first version worked well enough to be encouraging, right up to Panama.
The router was reading its input data correctly. My mistake was in what I thought that data described. Anyone who builds on a dataset they did not make has a version of this bug. Mine was easy to notice because it was ten thousand miles long.
The existing open-source sea routers work from hand-drawn networks. eurostat/searoute and searoute-py use a static network of roughly 4,000 edges, and scgraph routes over a pre-curated shipping lane dataset. Those are the right tool for shipping logistics between major ports. They cannot tell a harbour entrance from open ocean, which is the part I needed. I had to generate my own graph, and that starts with finding the ocean.
There is no dataset that says "here is the ocean". What exists is the opposite. OpenStreetMap contributors tag shorelines with
This is a good deal for someone building a sea router. The land polygons are detailed, they are maintained, they cover the whole planet, and they are free. My build pipeline reads that shapefile, lays an H3 grid over everything that is not land, and connects neighbouring water cells into a graph. H3 is Uber's hexagonal index, and its cells nest inside each other, which matters later. Then A* runs over the graph.
Which water my router can see comes down entirely to what
Ships crossing Panama are lifted about 26 metres. They enter a lock, rise, cross Gatun Lake, and are lowered again on the other side. The water in the middle is fresh water held above a continental divide, which makes it a lake rather than sea.
So the coastline tag does exactly what it promises. It follows the Atlantic shore up to the lock gates, stops, and picks up again on the Pacific side. Between those two points the land polygons show unbroken ground. My grid generator saw unbroken land across the whole isthmus, put no water cells there, and A* did the only correct thing available to it. It went around a continent.
The Suez Canal caused me no trouble at all, and the reason is the same rule read the other way. Suez has no locks. It is a sea-level cut, the Mediterranean and the Red Sea are directly joined through it, and so the coastline follows the canal banks. The water gap is already in the land polygons. Corinth behaves the same way for the same reason.
This split runs through my whole passage table. Six natural straits and two sea-level canals came free, because the coastline follows both shores. Six other passages did not, and the deciding factor turned out to be a mapping convention rather than a physical one. Panama, Kiel and Welland have locks, so nobody carried the coastline through them. Three more sit at sea level with no locks at all and are missing anyway, because mappers tagged them as inland waterways and never as coast. All six had to be handled by hand.
The fix was simpler than the bug. The canal is in OpenStreetMap, in a different part of the data: it is tagged as water, instead of being implied by a gap in the land.
Each passage in my code can now carry a regional extract URL and a list of water types:
During a build, any passage that has a URL gets its regional
Panama went from 10,337 nm to 49.7 nm. The routing time went from 6.91 s to 72.4 ms, because A* no longer had to search its way around an entire continent before it could return an answer. Later changes to node snapping and to the graph format moved the measured transit to the 53.5 nm in the benchmark table further down.
Kiel had the same problem in a different form, routing around Denmark at 409 nm instead of taking the 84 nm canal. Water subtraction alone did not fix it.
A global hexagonal grid at one resolution is not affordable. A resolution fine enough for a lock chamber would need more cells across the Pacific than I could store or search, and a resolution coarse enough for the Pacific makes a lock chamber smaller than the rounding error.
So the grid cascades. Open ocean is covered at H3 resolution 3, where cells have an edge of roughly 32 nautical miles. Near a shoreline the cascade refines down to resolution 9, with edges of about 174 metres. Inside a declared passage corridor it goes further, to resolution 11 or 13.
The rule I settled on is that the leaf resolution comes from the physical width of the narrowest thing a ship has to fit through:
Kiel was set to resolution 11 at first. Twenty-five metre cells are small compared to the canal itself, and they were still too large to keep the lock entrances connected. Two water areas that a ship can pass between were represented by cells that did not touch, so the graph had no edge there, and A* went around Denmark. Moving Kiel to resolution 13 closed the gap.
Everything above worked on a regional test build around one bay in Turkey. The full planet build found things that bay never could.
Edge weights are stored quantized in hundredths of a nautical mile to keep the graph small. A resolution 13 cell edge is 3.5 metres, which is 0.0019 nm, or about a fifth of one centi-nm, so it rounds to zero. Every edge through Panama, Kiel, Corinth and Welland therefore cost A* nothing at all. The search was happy to wander through the canal system for as long as it liked. The fix is a clamp to a minimum of one centi-nm per edge, and it needed a full graph rebuild to take effect.
At 180 degrees longitude, cell polygons wrap and come out degenerate. My refinement logic read those broken shapes as coastline detail and refined into them. The planet graph carried about 433,000 spurious fine-resolution nodes in a line down the middle of the Pacific before I caught it.
Inland lakes, closed harbour basins, and small pockets of water that the coastline encircles all produce valid water cells that connect to nothing. The build now keeps only the largest connected component, which removed about 1.65 million nodes spread across roughly 91,500 separate fragments. What is left is a single connected component, so any two points on it are reachable from each other.
After A* finds a path I smooth it, because a hexagon path zigzags and no one steers like that. Smoothing is allowed to replace a run of cells with a straight line when that line does not cross a coastline. My coastline index was built from the original land polygons, so it did not know about the channels I had just subtracted. The straight line from one end of the canal to the other crossed no coastline that the index knew about, and the smoother happily drove the route across dry land. The index is now extracted from the land polygons after subtraction.
The full planet build runs on a Hetzner ccx53, which is 32 dedicated vCPUs and 128 GB of RAM, and takes about five hours.
The graph file is serialised with bitcode and compressed with zstd at level 19. Node H3 indices are sorted, so a coordinate lookup is a binary search instead of a spatial index, which removed the R-tree and a good amount of memory with it.
Routing on that graph, measured over 50 iterations per route:
The last two rows still bother me. The South Atlantic route is longer than the North Atlantic one and computes 28 times faster. I have a theory about coastline density and how far the search fans out, and I have not proved it yet.
The graph carries no depth data, and all water is treated as navigable. That is reasonable for a small sailing boat. If you draw more than a couple of metres, this is no substitute for a chart.
auto-sea-way is MIT and Apache 2.0 licensed and runs as a single binary with a graph file, or as a Docker image with the graph baked in. It powers the auto-routing in Rhumb. The
None of the problems in this article was a bug in a single component. The coastline tag is correct. The land polygons built from it are correct. The hexagonal grid, the A* search, the edge quantisation and the path smoother are each correct on their own. Every bug lived in the gap between two of them, at a place where they meant slightly different things by "water" or "distance". The coastline meant sea, and my router meant anything a boat can float on. The quantiser meant hundredths of a mile, and a res-13 cell is smaller than that.
The router is auto-sea-way, an open-source routing graph I generated for the whole ocean surface of the planet. I built it because I could not find one with enough detail for Rhumb, the marine navigation app I make. The first version worked well enough to be encouraging, right up to Panama.
The router was reading its input data correctly. My mistake was in what I thought that data described. Anyone who builds on a dataset they did not make has a version of this bug. Mine was easy to notice because it was ten thousand miles long.
Where my ocean came from
The existing open-source sea routers work from hand-drawn networks. eurostat/searoute and searoute-py use a static network of roughly 4,000 edges, and scgraph routes over a pre-curated shipping lane dataset. Those are the right tool for shipping logistics between major ports. They cannot tell a harbour entrance from open ocean, which is the part I needed. I had to generate my own graph, and that starts with finding the ocean.
There is no dataset that says "here is the ocean". What exists is the opposite. OpenStreetMap contributors tag shorelines with
natural=coastline, and from those tagged ways the project builds a set of land polygons, published as a shapefile that anyone can download. The ocean is what remains after you subtract the land.This is a good deal for someone building a sea router. The land polygons are detailed, they are maintained, they cover the whole planet, and they are free. My build pipeline reads that shapefile, lays an H3 grid over everything that is not land, and connects neighbouring water cells into a graph. H3 is Uber's hexagonal index, and its cells nest inside each other, which matters later. Then A* runs over the graph.
Which water my router can see comes down entirely to what
natural=coastline means. It means the line where the sea meets the land. That definition is precise and it is the right one for the people who made it. It is also the reason Panama disappeared.Why Panama is land and Suez is not
Ships crossing Panama are lifted about 26 metres. They enter a lock, rise, cross Gatun Lake, and are lowered again on the other side. The water in the middle is fresh water held above a continental divide, which makes it a lake rather than sea.
So the coastline tag does exactly what it promises. It follows the Atlantic shore up to the lock gates, stops, and picks up again on the Pacific side. Between those two points the land polygons show unbroken ground. My grid generator saw unbroken land across the whole isthmus, put no water cells there, and A* did the only correct thing available to it. It went around a continent.
The Suez Canal caused me no trouble at all, and the reason is the same rule read the other way. Suez has no locks. It is a sea-level cut, the Mediterranean and the Red Sea are directly joined through it, and so the coastline follows the canal banks. The water gap is already in the land polygons. Corinth behaves the same way for the same reason.
This split runs through my whole passage table. Six natural straits and two sea-level canals came free, because the coastline follows both shores. Six other passages did not, and the deciding factor turned out to be a mapping convention rather than a physical one. Panama, Kiel and Welland have locks, so nobody carried the coastline through them. Three more sit at sea level with no locks at all and are missing anyway, because mappers tagged them as inland waterways and never as coast. All six had to be handled by hand.
Cutting the canals open
The fix was simpler than the bug. The canal is in OpenStreetMap, in a different part of the data: it is tagged as water, instead of being implied by a gap in the land.
Each passage in my code can now carry a regional extract URL and a list of water types:
Code:
Passage {
name: "Panama Canal",
corridor: (-79.95, 8.88, -79.50, 9.42),
leaf_resolution: 13, // bumped from 11 — lock channels need 3.5m edges
geofabrik_url: Some("https://download.geofabrik.de/central-america/panama-latest.osm.pbf"),
water_types: &["lock", "reservoir", "lake", "river"],
},
Passage {
name: "Suez Canal",
corridor: (32.20, 29.85, 32.65, 31.32),
leaf_resolution: 11,
geofabrik_url: None, // sea-level canal, coastline provides gaps
water_types: &[],
},During a build, any passage that has a URL gets its regional
.osm.pbf downloaded from Geofabrik. I shell out to osmium-tool to pull the natural=water polygons out of it and keep only the listed water types. I clip the result to the passage corridor, so a whole country of rivers does not come along, and subtract it from the land index before any cells are generated. The rest of the pipeline never learns that anything unusual happened.Panama went from 10,337 nm to 49.7 nm. The routing time went from 6.91 s to 72.4 ms, because A* no longer had to search its way around an entire continent before it could return an answer. Later changes to node snapping and to the graph format moved the measured transit to the 53.5 nm in the benchmark table further down.
Kiel had the same problem in a different form, routing around Denmark at 409 nm instead of taking the 84 nm canal. Water subtraction alone did not fix it.
Resolution is chosen by physical width
A global hexagonal grid at one resolution is not affordable. A resolution fine enough for a lock chamber would need more cells across the Pacific than I could store or search, and a resolution coarse enough for the Pacific makes a lock chamber smaller than the rounding error.
So the grid cascades. Open ocean is covered at H3 resolution 3, where cells have an edge of roughly 32 nautical miles. Near a shoreline the cascade refines down to resolution 9, with edges of about 174 metres. Inside a declared passage corridor it goes further, to resolution 11 or 13.
The rule I settled on is that the leaf resolution comes from the physical width of the narrowest thing a ship has to fit through:
| Passage | Narrowest part | Resolution | Cell edge |
|---|---|---|---|
| Suez | ~200 m channel | res-11 | ~25 m |
| Bosphorus, Dover, Messina | wide straits | res-10 | ~66 m |
| Panama | ~33 m lock chambers | res-13 | ~3.5 m |
| Corinth | ~25 m cut | res-13 | ~3.5 m |
| Kiel | lock entrances | res-13 | ~3.5 m |
Kiel was set to resolution 11 at first. Twenty-five metre cells are small compared to the canal itself, and they were still too large to keep the lock entrances connected. Two water areas that a ship can pass between were represented by cells that did not touch, so the graph had no edge there, and A* went around Denmark. Moving Kiel to resolution 13 closed the gap.
Four bugs that only appear at planet scale
Everything above worked on a regional test build around one bay in Turkey. The full planet build found things that bay never could.
Canal transit became free
Edge weights are stored quantized in hundredths of a nautical mile to keep the graph small. A resolution 13 cell edge is 3.5 metres, which is 0.0019 nm, or about a fifth of one centi-nm, so it rounds to zero. Every edge through Panama, Kiel, Corinth and Welland therefore cost A* nothing at all. The search was happy to wander through the canal system for as long as it liked. The fix is a clamp to a minimum of one centi-nm per edge, and it needed a full graph rebuild to take effect.
The antimeridian filled with false detail
At 180 degrees longitude, cell polygons wrap and come out degenerate. My refinement logic read those broken shapes as coastline detail and refined into them. The planet graph carried about 433,000 spurious fine-resolution nodes in a line down the middle of the Pacific before I caught it.
A million and a half nodes led nowhere
Inland lakes, closed harbour basins, and small pockets of water that the coastline encircles all produce valid water cells that connect to nothing. The build now keeps only the largest connected component, which removed about 1.65 million nodes spread across roughly 91,500 separate fragments. What is left is a single connected component, so any two points on it are reachable from each other.
Smoothing cut through the canal banks
After A* finds a path I smooth it, because a hexagon path zigzags and no one steers like that. Smoothing is allowed to replace a run of cells with a straight line when that line does not cross a coastline. My coastline index was built from the original land polygons, so it did not know about the channels I had just subtracted. The straight line from one end of the canal to the other crossed no coastline that the index knew about, and the smoother happily drove the route across dry land. The index is now extracted from the land polygons after subtraction.
What it costs
The full planet build runs on a Hetzner ccx53, which is 32 dedicated vCPUs and 128 GB of RAM, and takes about five hours.
| Metric | Value |
|---|---|
| Nodes | 39,412,823 |
| Edges | 299,517,836 |
| Graph file | 717 MB |
| Connectivity | 100%, single component |
| Server memory after load | ~4.1 GiB resident |
The graph file is serialised with bitcode and compressed with zstd at level 19. Node H3 indices are sorted, so a coordinate lookup is a binary search instead of a spatial index, which removed the R-tree and a good amount of memory with it.
Routing on that graph, measured over 50 iterations per route:
| Route | Distance | P50 |
|---|---|---|
| Dover Strait | 18.4 nm | 0.4 ms |
| Panama Canal | 53.5 nm | 76.0 ms |
| Kiel Canal | 84.2 nm | 39.0 ms |
| Suez Canal | 141.2 nm | 13.1 ms |
| South Atlantic | 3,272.3 nm | 30.8 ms |
| North Atlantic | 3,040.5 nm | 869 ms |
The last two rows still bother me. The South Atlantic route is longer than the North Atlantic one and computes 28 times faster. I have a theory about coastline density and how far the search fans out, and I have not proved it yet.
The graph carries no depth data, and all water is treated as navigable. That is reasonable for a small sailing boat. If you draw more than a couple of metres, this is no substitute for a chart.
auto-sea-way is MIT and Apache 2.0 licensed and runs as a single binary with a graph file, or as a Docker image with the graph baked in. It powers the auto-routing in Rhumb. The
shore_buffer parameter, which keeps routes off headlands, exists because a user opened issue #26 and told me the routes hugged the coast too closely. More of that is welcome.Where the bugs were
None of the problems in this article was a bug in a single component. The coastline tag is correct. The land polygons built from it are correct. The hexagonal grid, the A* search, the edge quantisation and the path smoother are each correct on their own. Every bug lived in the gap between two of them, at a place where they meant slightly different things by "water" or "distance". The coastline meant sea, and my router meant anything a boat can float on. The quantiser meant hundredths of a mile, and a res-13 cell is smaller than that.