2
$\begingroup$

(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.

$\endgroup$

1 Answer 1

3
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ Thanks! For my future reference, I note that this question looks like it has some useful suggestions for appropriate path-finding algorithms: cstheory.stackexchange.com/questions/11855/… $\endgroup$ Apr 25, 2017 at 1:21
  • $\begingroup$ Nice solution. You can also use binary search on the threshold value to find the smallest threshold value that allows you to find some path from start to end, which might speed this up. $\endgroup$
    – D.W.
    Apr 25, 2017 at 6:55

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.