Indeed. This seems similar to my problem. I started thinking about the streetlight problem decades ago in Portland, which has a grid in the city center. The sp

Indeed. This seems similar to my problem. I started thinking about the streetlight problem decades ago in Portland, which has a grid in the city center. The specific question was what if I just always went with the green light to cross the grid? In the streetlight case this clearly leads to bad outcomes if the length of the red light time is unbounded. Your conditions would seem to limit the cost of a bad decision to the number of nodes you cross times the maximum height difference between west and east ends of the grid. However, if you don't somehow limit the number of ups and downs between nodes, then the "take the downhill" algorithm seems to have the same issue as walking through streetlights. All you have to do is assume a large number of ups and downs within a block. In both cases it seems that to bound the "sub-optimality" of solutions there must be a bound on the cost of moving between nodes in the grid.