Show HN: Dijkstra’s algorithm in the web browser with OpenStreetMap

Have you tried this with A* and seen any performance differences? This is very fast in the browser with a small map, but I imagine with a much larger map the difference would be noticeable.

Re: Show HN: Dijkstra’s algorithm in the web browser with OpenStreetMap

#5

Post by d33 » Tue, Oct 04, 2016, 9:48 PM UTC

How about an open source version?

Re: Show HN: Dijkstra’s algorithm in the web browser with OpenStreetMap

#6

Post by ctcliff » Tue, Oct 04, 2016, 9:48 PM UTC

soperj wrote: post #2

this is unbelievably relevant for me right now, because this is exactly what I was looking to implement. Any gotchas? Lessons learned?

The geographic rendering APIs tend to be incompatible with the graphing algorithms and data structures. It's better to optimize your data on the server for algorithmic simplicity and convert to a render-friendly format at render time.

Also, immutability is great when you're juggling 1000s of lon/lat arrays.

Re: Show HN: Dijkstra’s algorithm in the web browser with OpenStreetMap

#7

Post by ctcliff » Tue, Oct 04, 2016, 9:55 PM UTC

ddlutz wrote: post #4

Have you tried this with A* and seen any performance differences? This is very fast in the browser with a small map, but I imagine with a much larger map the difference would be noticeable.

I haven't, but even at this size the rendering is quite a bit slower than the calculation. For example, the delay on reload is almost entirely from rendering the shortest path tree.

Re: Show HN: Dijkstra’s algorithm in the web browser with OpenStreetMap

#8

Post by teraflop » Tue, Oct 04, 2016, 10:35 PM UTC

Anyone who's interested in this might want to check out the OSRM project, which uses a much more complex routing algorithm to efficiently find paths through the entire OSM graph, instead of just a tiny subset: http://map.project-osrm.org/

(Also, it's open-source.)

Re: Show HN: Dijkstra’s algorithm in the web browser with OpenStreetMap

#9

Post by mastazi » Tue, Oct 04, 2016, 11:07 PM UTC

teraflop wrote: post #8

Anyone who's interested in this might want to check out the OSRM project, which uses a much more complex routing algorithm to efficiently find paths through the entire OSM graph, instead of just a tiny subset: http://map.project-osrm.org/ (Also, it's open-source.)

Are there any instructions? It took me a long while to figure out how to drop pins (the placeholder text says you have to press Enter, but you actually need to use the mouse), and now I have no idea how to display the route.

Re: Show HN: Dijkstra’s algorithm in the web browser with OpenStreetMap

#10

Post by Doctor_Fegg » Tue, Oct 04, 2016, 11:21 PM UTC

teraflop wrote: post #8

Anyone who's interested in this might want to check out the OSRM project, which uses a much more complex routing algorithm to efficiently find paths through the entire OSM graph, instead of just a tiny subset: http://map.project-osrm.org/ (Also, it's open-source.)

OSRM is wonderful.

I run bike routing for North America and Western Europe using a heavily customised instance of OSRM (based on OSM data, of course):

http://cycle.travel/map