How to limit elevation over distance using the A* search algorithm?

Question

My application finds or constructs routes that are shortest for trekkers in a hilly/mountain terrain using the A* search algorithm. Input files are .dem (Digital Elevation Model) and a roadmap file that contains existing routes. Code is in Python, libraries used are pygdal, NumPy and PyQGIS.

The routes provided by the algorithm are very steep. I want my route to follow the gradient guidelines, for every 30m only 1m of elevation. A* finds the shortest route from peak to valley in a straight line, which is not practical. Output should descend from one contour line to another at less than 1.91 degrees.

Answer 1

All-Paths ( practical alternative to A* )

Your question has so few details, it is impossible to give a detailed or complete answer.

I will assume that you are trying to minimize the distance walked AND the "steepness".

The distance is straightforward.

The "steepness" measure needs to be clarified. Do you want to minimize the total change of elevation during a walk? Minimize the maximum rate of elevation change? Minimize the average rate of elevation change? Or some other statistic?

Finally, you have to decide what is the trade off between distance walked and "steepness"

Let:

D be the total distance
S be the "steepness" statistic you have chosen
t be the amount of "steepness" you will accept to reduce D by one unit

then you want

minimum C = D + t * S       Eq 1

The algorithm goes:

- Construct a graph of the possible routes from the roadmap
- Use standard graph algorithm to find all paths between start and destination
- Apply Eq 1 to paths as they are found.
- Select path with smallest C value so far

FYI you can have look at the C++ code implementing a simple version of this at https://github.com/JamesBremner/LazyHillWalker

Performance

Run time for running the All Paths algorithm to find all the paths between two randomly selected vertices on large graphs downloaded from https://dyngraphlab.github.io/. Longest result from 3 runs using the graphex application.

Vertex Count	Edge Count	Run time ( secs )
4,700	27,000	20

Complete application details at https://github.com/JamesBremner/PathFinder/wiki/All-Paths#performance

A* Snags

The OP has proposed using the A* algorithm. I consider A* suitable only for small, simple problems for two reasons.

1. A* is very expensive in memory. So not very practical for large, real world problems ( > 10,000 nodes ) "One major practical drawback is the A*'s O(b^d) space complexity, as it stores all generated nodes in memory" https://en.wikipedia.org/wiki/A*_search_algorithm

2. A* is concerned only with individual links from the start to the current node and from the current node to the goal. If the steepness statistic is chosen as a measure based on the entire path ( e.g. maximum or average elevation change per unit distance ) then formulating the A* helper functions ( a heuristic to estimate the cost of the remaining path from current vertex, and a true measure of the cost of the cheapest path to the current vertex. ) will be a challenge.

---

Missing details from question:

• Do you want to select the optimum possible path, or do you want to get all the paths that meet a strict limit? Please answer 'yes' or 'no'

• Do you want to minimize a combination of distance and steepness. Please answer 'yes' or 'no'

• Please clarify how you calculate steepness. Please answer by giving an example of a short path and show hoy you calculate its distance

• How large is your input graph. Please answer with vertex and edge counts.

Answer 2

I want the output should descent from one contour line to another at less that a particular angle so that the descent is not so steep. In this case the recommended gradient descent is 1.91 degrees.

• Create graph from map
• Remove all links that are steeper than 1.91 degrees
• Find path through graph in usual way