Finding optimal routes across variable terrain
2026-02-27
The Trans Mountain Pipeline expansion, approved in 2019 and completed in 2024, required routing 1,150 km of new pipeline from Edmonton to Burnaby through some of the most topographically complex terrain in North America. The route had to balance multiple competing cost surfaces: slope (steep terrain means expensive construction and higher risk), proximity to existing infrastructure (cheaper where right-of-way already exists), geological hazards (landslide-prone slopes, river crossings), and environmental sensitivities (avoiding wetlands, fish-bearing streams, and protected areas). The final route is not a straight line — it is the minimum-cost path through a multidimensional cost surface, exactly the problem that Dijkstra’s algorithm was designed to solve.
Cost-distance analysis extends the simple Euclidean distance buffer by replacing distance with a generalised cost that varies across the landscape. Instead of asking “how far is it?”, it asks “how expensive or difficult is it to reach?” — where the cost per unit distance varies by terrain steepness, land cover, regulatory restriction, or any combination of factors that can be encoded in a raster. The accumulated cost surface assigns a total cost to each cell: the minimum cost of reaching that cell from the source. From the cost surface, the least-cost path — the route that minimises total cost from source to destination — is found by tracing the steepest descent on the cost surface back to the source. The underlying algorithm is Dijkstra’s shortest-path algorithm on a grid graph, one of the most important and widely implemented algorithms in computational geography.
What’s the easiest hiking route from the trailhead to the summit?
Euclidean distance doesn’t account for terrain difficulty: - Steep slopes are harder to traverse - Roads are easier than off-trail - Rivers may be impassable
Cost-distance accumulates travel cost across a surface:
Applications: - Hiking trails: Minimize elevation gain and distance - Wildlife corridors: Connect habitats through suitable terrain - Pipelines: Minimize construction cost (avoid wetlands, steep slopes) - Power lines: Balance distance vs. terrain difficulty - Emergency response: Fastest route considering traffic and terrain
The mathematical question: Given a cost surface (where each cell has a traversal cost), find the minimum accumulated cost to reach any location, and trace the optimal path.
Cost raster: Each cell has a value representing difficulty/cost of traversal.
Examples:
Slope-based cost:
\text{cost} = e^{3.5 \times |\tan(\text{slope}) + 0.05|}
(Tobler’s hiking function—models walking speed on slopes)
Land cover cost:
| Type | Cost |
|---|---|
| Road | 1 |
| Grass | 5 |
| Forest | 10 |
| Wetland | 50 |
| Water | ∞ (impassable) |
Combined cost:
\text{cost}_{\text{total}} = w_1 \times \text{cost}_{\text{slope}} + w_2 \times \text{cost}_{\text{landcover}}
For each cell: Minimum total cost to reach it from source.
Initialization: - Source cell: cost = 0 - All others: cost = ∞
Propagation: Iteratively update neighbors, choosing minimum cost path.
Result: Raster where value = minimum accumulated cost from source.
Trace route from destination back to source following steepest descent in cost surface.
Backtracking: - Start at destination - Move to neighbor with lowest accumulated cost - Repeat until reaching source
Result: Polyline representing optimal route.
Raster as graph: - Nodes: Grid cells - Edges: Connections to neighbors (4-neighbor or 8-neighbor) - Edge weights: Cost to traverse from cell to neighbor
Edge cost from cell i to neighbor j:
c_{ij} = \text{distance}_{ij} \times \frac{\text{cost}_i + \text{cost}_j}{2}
Distance: - Cardinal neighbors (N, S, E, W): distance = 1 (cell size) - Diagonal neighbors: distance = \sqrt{2} (cell size)
Average cost: Use mean of source and destination cell costs.
Classic shortest-path algorithm (Edsger Dijkstra, 1956).
Data structures: - dist[v]: Minimum distance from source to node v - visited: Set of nodes with finalized distances - priority_queue: Nodes to process, ordered by distance
Algorithm:
function dijkstra(graph, source):
dist[source] = 0
dist[all others] = ∞
priority_queue = {source: 0}
while priority_queue not empty:
u = node with minimum dist in queue
remove u from queue
add u to visited
for each neighbor v of u:
if v not in visited:
new_dist = dist[u] + edge_cost(u, v)
if new_dist < dist[v]:
dist[v] = new_dist
parent[v] = u
add/update v in queue
return dist, parentComplexity: O((V + E) \log V) with priority queue
Where V = cells, E = edges (typically 8V for 8-neighbor grid)
For n \times n grid: O(n^2 \log n)
After Dijkstra’s, trace back using parent pointers:
function reconstruct_path(parent, source, destination):
path = []
current = destination
while current != source:
path.append(current)
current = parent[current]
path.append(source)
return reverse(path)Result: Sequence of cells from source to destination.
Cost may vary by direction:
Uphill vs. downhill:
\text{cost}_{\text{uphill}} = \text{base} \times e^{k \times \text{slope}} \text{cost}_{\text{downhill}} = \text{base} \times e^{-k \times \text{slope}}
Wind resistance:
\text{cost}_{\text{headwind}} > \text{cost}_{\text{tailwind}}
Implementation: Edge cost depends on both source and destination cells plus direction.
Problem: Find least-cost path from (0,0) to (3,3) in this cost grid.
Cost surface:
j=0 j=1 j=2 j=3
i=0 1 5 10 5
i=1 1 1 5 10
i=2 5 1 1 5
i=3 10 5 1 1Use 4-neighbor connectivity (N, S, E, W only).
Initialization:
dist[0,0] = 0
dist[all others] = ∞Iteration 1: Process (0,0), cost = 0
Neighbors: (0,1) and (1,0)
Update (0,1): - Edge cost = $1 = 3$ - dist[0,1] = 0 + 3 = 3
Update (1,0): - Edge cost = $1 = 1$ - dist[1,0] = 0 + 1 = 1
Iteration 2: Process (1,0), cost = 1 (minimum unvisited)
Neighbors: (0,0) [visited], (1,1), (2,0)
Update (1,1): - Edge cost = $1 = 1$ - dist[1,1] = 1 + 1 = 2
Update (2,0): - Edge cost = $1 = 3$ - dist[2,0] = 1 + 3 = 4
Continue…
After full algorithm:
Accumulated cost:
j=0 j=1 j=2 j=3
i=0 0 3 8 11
i=1 1 2 4 9
i=2 4 3 3 5
i=3 9 6 4 4Least-cost path from (0,0) to (3,3):
Trace back from (3,3): - (3,3) cost=4, parent=(3,2) - (3,2) cost=4, parent=(2,2) - (2,2) cost=3, parent=(2,1) - (2,1) cost=3, parent=(1,1) - (1,1) cost=2, parent=(1,0) - (1,0) cost=1, parent=(0,0) - (0,0) source
Path: (0,0) → (1,0) → (1,1) → (2,1) → (2,2) → (3,2) → (3,3)
Total cost: 4 units
Path avoids high-cost cells in top-right and bottom-left corners.
Below is an interactive cost-distance path finder.
<label>
Cost type:
<select id="cost-type">
<option value="slope" selected>Slope-based</option>
<option value="landcover">Land Cover</option>
<option value="random">Random Terrain</option>
</select>
</label>
<label>
Connectivity:
<select id="connectivity">
<option value="4">4-neighbor</option>
<option value="8" selected>8-neighbor</option>
</select>
</label>
<label>
Show cost surface:
<input type="checkbox" id="show-cost" checked>
</label>
<label>
Show accumulated cost:
<input type="checkbox" id="show-accum">
</label>
<div class="path-info">
<p><strong>Path length:</strong> <span id="path-length">--</span> cells</p>
<p><strong>Total cost:</strong> <span id="total-cost">--</span></p>
<p><strong>Avg cost/cell:</strong> <span id="avg-cost">--</span></p>
</div><canvas id="costpath-canvas" width="600" height="600" style="border: 1px solid #ddd; cursor: crosshair;"></canvas><p><em>Click to set start (green) and end (red) points, then path will compute automatically.</em></p>Try this: - Click to set start (green) and end (red) - path computes automatically - Slope-based: Path avoids steep center (darker = higher cost) - Land cover: Path finds low-cost patches - 8-neighbor vs 4-neighbor: Diagonal moves allowed vs cardinal only - Show accumulated cost: Blue (near start) to red (far) - distance from source - Path (orange): Follows minimum cost, not straight line - Notice: Path curves around high-cost areas even if that means longer distance!
Key insight: Optimal path balances distance vs. terrain cost—sometimes the long way is easier!
Problem: Connect two habitat patches for animal movement.
Approach: 1. Create cost surface from habitat suitability - Low cost: Forest, grassland - High cost: Urban, agricultural - Infinite: Highways (impassable) 2. Compute accumulated cost from source habitat 3. Find least-cost path to destination habitat 4. Widen path to create corridor (buffer)
Result: Protected corridor enabling wildlife movement.
Example: Mountain lion corridors in Southern California.
Cost factors: - Slope (steep = expensive construction) - Land ownership (private > public) - Environmental sensitivity (wetlands = regulatory cost) - Crossings (rivers, roads = high cost)
Optimization:
\text{cost} = w_1 \times \text{construction} + w_2 \times \text{permits} + w_3 \times \text{maintenance}
Least-cost path minimizes total project cost.
Tobler’s hiking function (optimal walking speed vs. slope):
v = 6 e^{-3.5|\tan(\text{slope}) + 0.05|}
Where v is speed in km/h.
Travel time:
t = \frac{d}{v}
Trail routing: - Minimize total time - Avoid slopes > 15% (too steep) - Stay near scenic viewpoints (negative cost)
Result: Enjoyable, efficient trail.
Greedy algorithms can get stuck:
High cost barrier surrounds low-cost destination
Greedy descent stops at barrier (local minimum)
Never finds global optimum (go around barrier)Dijkstra avoids this by exploring all possibilities.
In 4-neighbor grid:
Diagonal moves unavailable → Manhattan distance artifacts
In 8-neighbor grid:
Diagonal cost = \sqrt{2} \approx 1.41 but often approximated as 1.5 or 1
Bias: Paths may zigzag when straight diagonal is optimal
Solution: Use correct \sqrt{2} weight for diagonals
Coarse DEM misses fine-scale barriers: - Small cliffs - Narrow canyons
- Local hazards
10m DEM: Can route through 5m cliff (invisible at this resolution)
Solution: Use finest available resolution for critical applications
Large grids require huge memory:
10,000 × 10,000 grid = 100 million cells
Each cell needs: - Distance value (8 bytes) - Parent pointer (8 bytes) - Priority queue entry (variable)
Total: ~2 GB minimum
Solution: - Process in tiles - Use sparse data structures - Hierarchical pathfinding (coarse → fine)
A* improves Dijkstra with heuristic guidance.
Heuristic: Estimated cost from node to goal.
For spatial grids: Euclidean distance to goal
h(n) = \sqrt{(x_n - x_{\text{goal}})^2 + (y_n - y_{\text{goal}})^2}
Priority: f(n) = g(n) + h(n)
Where: - g(n) = actual cost from start to n - h(n) = estimated cost from n to goal - f(n) = estimated total cost
Advantage: Explores toward goal → faster than Dijkstra
Requirement: Heuristic must be admissible (never overestimate)
For grid: Euclidean distance is admissible (straight line is shortest)
Speedup: 2-10× faster for long paths
Priority queue: Data structure supporting: - insert(item, priority): Add item with priority - extract_min(): Remove and return item with minimum priority - decrease_priority(item, new_priority): Update priority
Array (unsorted): - Insert: O(1) - Extract min: O(n) (must scan)
Array (sorted): - Insert: O(n) (maintain order) - Extract min: O(1) (first element)
Binary heap: - Insert: O(\log n) - Extract min: O(\log n) - Best for Dijkstra
Fibonacci heap: - Decrease priority: O(1) amortized - Theoretical improvement for Dijkstra - Complex implementation, rarely used in practice
dist[source] = 0
pq.insert(source, 0)
while pq not empty:
u = pq.extract_min()
for each neighbor v:
alt = dist[u] + cost(u, v)
if alt < dist[v]:
dist[v] = alt
if v in pq:
pq.decrease_priority(v, alt)
else:
pq.insert(v, alt)Complexity: O((V + E) \log V) with binary heap