Another possibility is to add an additional dimension, exhaustion, for each node. Say exhaustion can have values 0, 1 or 2. Any uphill path goes up a level of exhaustion (capped at 2). Any downhill path goes down a level of exhaustion (capped at 0). Any flat path... not sure. Stay the same? Or maybe have values 0,1,2,3,4,5 and up = +2, down = -2, flat = -1?

In any case, depending upon the exhaustion level you could modify the outgoing costs, e.g. triple if very exhausted. This would not be an NP-hard problem, just a problem with an x times bigger search space.

Another possibility is to add an additional dimension, exhaustion, for each node. Say exhaustion can have values 0, 1 or 2. Any uphill path goes up a level of exhaustion (capped at 2). Any downhill path goes down a level of exhaustion (capped at 0). Any flat path... not sure. Stay the same? Or maybe have values 0,1,2,3,4,5 and up = +2, down = -2, flat = -1?

In any case, depending upon the exhaustion level you could modify the outgoing costs, e.g. triple if very exhausted. This would not be an NP-hard problem, just a problem with an x times bigger search space.

How is that another possibility? That's exactly what I suggested...

How is that another possibility? That's exactly what I suggested...

The way I read your suggestion was exponentially branching based on the full search history. My suggestion is that the exact path is likely not to matter, only how tired you are at a given node. This means you can have different costs from node D to E for each of a fixed number of tiredness values without the need to stretch it into NP territory. Rather like an earlier thread about pathfinding for vehicles with momentum.

I looked back at the posts one more time, I see where you mention a similar scheme. I'm not sure whether I read your post before you edited it, or perhaps I dismissed the post the moment it mentioned NP.

I looked back at the posts one more time, I see where you mention a similar scheme. I'm not sure whether I read your post before you edited it, or perhaps I dismissed the post the moment it mentioned NP.

Yeah, I guess I shouldn't have said two separate things in one paragraph. Plus, you probably expressed the idea better.

Anyway, that's probably the way to go.

I'm struggling to follow your reasoning as to why you have to look backwards to determine the cost of the path going forwards. If your weights are done correctly, getting to node D includes the cost of getting to any of the previous nodes that made up the path. Unless your movement along the terrain can cause a landslide that affects the path ahead I don't follow your line of thinking.

Correct. Yeah, if say using squared RMS (square of euclidean distance), you really pay for doing large uphills in the first place, so even something simple like that should take care of things like the one large hill + one small hill is worse than two medium size hills of the same distance problem. I was just trying to extend the problem in a different way to see where I could go with it he he he.

So in general, after reading the research on these types of problems, I've accepted that you should never break Bellman's Principle unless you absolutely have to. It's fun stuff though... there are some really interesting problems that break Bellman's Principle (mainly time-based things like traffic and music performance).