Ever since getting lost on a hike this summer, I've had the drive to figure out how to compute the easiest climb from one point to another. Continuing my experiments with the HTML5 canvas element, I wanted to see if JavaScript in the browser was powerful enough for some computationally intense routing algorithms. It turns out it is. Click the elevation model below once to set a starting point and once to set an end point and see the A* algorithm find a path between the two points.
Source library here.
Some notes about the implementation:
- Works fastest in Chrome. Will not even load in IE7 or earlier because there's no HTML5 support there.
- The images I used were from the USGS 1/3-Arc Second National Elevation Dataset which you can download from the National Map Viewer. We're losing a lot of detail going from a TIFF to a PNG. This algorithm will work on any image loaded into the canvas element, but the results might be funky when using a color image or any terrain with shaded relief.
- Use a binary heap to quickly get the item with the lowest f-score. This is a tremendous improvement over looping over arrays.
- Use objects to store lists for quick lookup. Again, much faster than looping over arrays.
- Stored the image data in an array instead of looking up pixel values with getImageData
- The binary heap methods should track item indexes whenever items are switched around. This keeps us from using expensive array lookups when items need to be updated
- Use the Firebug profiler to see which functions are taking too long, and focus improvements on those
- The canvas element throws a security error if the image is loaded from another domain. This limits loading images from web map services. Any way around this?
- If you start in different points in neighborhood A and end in any point in neighborhood B, looks like the trails merge and share a path for much of those hikes. What defines these neighborhoods? How do you find their boundaries?
- Running the algorithm on the same picture scaled down, is much faster and the results are remarkably similar. How much are we losing by using lower resolution data? Is running this on the original TIFF going to give the same results as running on the reduced resolution PNG?
- The heuristic is your best guess about the direction of the path. In this case, I'm just using a simple Manhattan distance. Can the heuristic be improved by using the results from a lower resolution run?
- Can we predict the location of existing or historical trails? W.G. Rees isn't too hopeful in "Least-cost paths in mountainous terrain" Computers & Geosciences 30 (2004) 203-209.
- In "Modeling slope as a contributor to route selection in mountainous areas" Thomas Pingel notes that people overestimate slopes and are prone to making sub-optimal decisions. Also going downhill on a steep slope is harder than going uphill the same way. How do you account for that in the prediction?
- Patrick Lester. "A* Pathfinding for Beginners"
- Patrick Lester. "Using Binary Heaps in A* Pathfinding"