Applications that require pathfinding in an environment with little or no connectivity are required to maintain a store of relevant geographical information. By eliminating external dependencies for finding an optimal path the pathfinding program is self-contained and enables offline-first applications.
The presence of roads including various geological and landcover features affect the movement of a vehicle over terrain. Surveys of these features need to be compiled for the area of interest in order to create a memory initialization file that the pathfinder can reference for movement costs.
Requirements
- dimdal-pathfinder - An implementation of the pathfinding algorithm described by Dimdal / Jönsson, 1997.
Data source
Data processing
Memory Initialization
A static memory initialization file is used to store all nodes in the search graph. A memory initialization file must be generated for each region in which searches will be conducted.
To generate a memory initialization file first create a configuration file and run,
$ node tools/generate-mem-init.js test/config.json
The memory initialization file combines the following data types compiled from the Overpass API and a heightmap generated using ASTER Global Digital Elevation Model Version 2.
| Bolinas Lagoon | Data Type |
|---|---|
 | roads (Key:highway) |
 | terrain (Key:natural) |
 | combined |
 | Digital elevation model |
Pathfinding demo
Click on the map to set the start point and click again to set an end point, a path will be displayed on the map if a route is found between those points that avoids impassable terrain.
Source: index.common.js
Further reading
- Amit’s Thoughts on Pathfinding - Approachable introduction to pathfinding concepts
- Thematic Mapping Blog - Digital Terrain Modelling and Mapping
- Smartjava.org Blog - Three.js: render real world terrain from heightmap using open data
- Beej's Bit Bucket Blog - HTML5 canvas pixel manipulation
- Dimdal Pathfinder Paper - An optimal pathfinder for vehicles in real-world digital terrain maps