Jump to content
Posted 27 September 2012 - 12:50 AM
Posted 27 September 2012 - 01:16 AM
Edited by Ashaman73, 27 September 2012 - 01:17 AM.
Posted 27 September 2012 - 01:32 AM
Posted 27 September 2012 - 02:03 AM
Posted 27 September 2012 - 02:27 AM
Was my first thought too, but then you need to split E and after that, the following nodes ...
You can split node "D" into "D from A", "D from B" and "D from C", because those seem to actually be different states. Then Dijkstra will work again.
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.
Edited by Ashaman73, 27 September 2012 - 02:28 AM.
Posted 27 September 2012 - 03:20 AM
Edited by yadango, 27 September 2012 - 04:03 AM.
Posted 27 September 2012 - 07:02 AM
Edited by alvaro, 27 September 2012 - 11:33 AM.
Posted 27 September 2012 - 11:39 AM
Edited by yadango, 27 September 2012 - 11:53 AM.
Posted 27 September 2012 - 08:38 PM
Posted 27 September 2012 - 09:26 PM
Posted 27 September 2012 - 09:55 PM
Professional consultant on game AI, mathematical modeling, simulation modeling
Co-advisor of the GDC AI Summit
Co-founder of the AI Game Programmers Guild
Author of the book, Behavioral Mathematics for Game AI
Posted 28 September 2012 - 04:21 AM
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.
Posted 28 September 2012 - 05:20 AM
How is that another possibility? That's exactly what I suggested...
Posted 28 September 2012 - 05:26 AM
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.
Posted 28 September 2012 - 06:45 PM
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.
Edited by yadango, 28 September 2012 - 06:54 PM.