Self-Contained, Optimal Pathfinding on Roads and Over Terrain

Published 10/29/2017

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

http://wiki.openstreetmap.org/wiki/Overpass_API

https://asterweb.jpl.nasa.gov/gdem.asp

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