Finding lowest "pass" between two points on a map?

Question

(I expect that the hard part of this question is getting the right language for the problem. My attempts at searching for an answer didn't get anything useful, which suggests to me that whatever they are, I'm not using them!)

Consider a map where each x,y coordinate has an associated "height" value. If we have two points (each of which is at a local minimum height) on this map, we can consider the set of all possible paths between those two points. Each path has a maximum height along the path; call this the "pass height" of the path. I'm interested in the minimum value of the pass height over the set of possible paths.

I'm calling this a "lowest pass", because in real maps, these paths with minimum height are the passes through the mountains.

What is an algorithm that will allow me to determine this minimum pass height? I'd be happy either with an algorithm that assumes a discrete grid of finitely-spaced points, or an algorithm that approximates the solution on a continuous surface with numerical iteration of some sort.

I'd also particularly like a solution that will work in a high-dimensional space, but one in 2-space would be a good start.

Answer 1

A simple solution to this would be to implement it as any normal pathfinding algorithm (say, A*), but then render in your map any height over a threshold as impassable, and any height under the threshold as passable, and then continuously run the pathfinding algorithm for threshold heights between the minimum cell height and the maximum cell height. The first time you can path from start to end is the lowest possible height.

This has some performance implications for maps with a large difference between highest and lowest points, but you use a search algorithm other than a linear search to find the upper and lower bounds and close in on the boundary.

Many pathfinding algorithms are already generalised to n-dimensions, so to generalise this is simply the case of picking the correct dimension to use as the varying threshold. Essentially, for a map of n dimensions (say, a 2D map + height), you path find in that many dimensions with the height being made into a passable/impassable cost.