![graph1.jpg](http://i73.photobucket.com/albums/i206/yadango/graph1.jpg)
However, the problem I have is like the following.
![graph2.jpg](http://i73.photobucket.com/albums/i206/yadango/graph2.jpg)
Think of it like this... because A -> D is downhill and D -> E is uphill, the weight for D -> E is 1.
Because B -> D is flat and D -> E is uphill, the weight for D -> E is a little larger, 5.
Because C -> D is uphill and D -> E is uphill, consecutive uphill are a doozy for the enemy and so he has a weight of 9.
In other words, any weight along the path doesn't just depend on where you were previously, but where you were before that too. It can even extend farther back several levels like going uphill 3 times in a row is a real doozy and you must pay an extra penalty for that too.
I've thought of a bunch of stuff, but backtracking requires a lot of memory especially when the graph gets large and so far the only solution I've come up with is to just test all possible paths (since enemies are usually close to the player the graph doesn't get too large but for even small graphs testing all possible paths takes too much time).
Has anyone seen a problem like this before? Is there an algorithm for it? Algorithms like Dijkstra, Viterbi, etc. don't work because they assume only one weight per edge.
Thanks!