There's a duplicate question with an answer that I've tried to implement here and having difficulty. How to do pathfinding when a unit has inertia?
I've a grid with obstacles where the computer can move in the four cardinal directions, and implemented pathfinding using the A-star or Djikstra algorithm.
But then I also wanted to add in "velocity", so instead of the neighbours being move left, move right, move up, move down, it's accelerate left, accelerate right, accelerate up, accelerate down, do nothing. On each move, the velocity from the previous move is preserved, and the delta from the acceleration is added. Accelerate <dir> costs 0, while Do nothing costs 1.
I've tried to implement this with A-star on a one-dimensional basis, getting it to find a path to move from (X=0, velocity=0) to (X=100, velocity=0). The choice available are always (Accelerate Cost=0, Decelerate Cost=0, Wait Cost=1).
It finds a sub-optimal path to complete the task that successfully. Accelerating only twice, and then waiting 49 times, decelerates once, then waits 2 more times, and one more deceleration to land at (X=100, velocity=0).
The optimal path is: Accelerate 100 times, wait once, Decelerates 100 times.
It looks like A star can handle pathfinding in an (X, Y) grid well, where X and Y are independent, but cannot handle (X, Y) grid where Y is also dependent on X.
Any ideas on how to modify A* or Djikstra or is there an alternative pathfinding algorithm I could use involving inertia?
You can look at my code at https://gist.github.com/meric/93540d1cff502684aac2
Uncommenting line 120 filter = function(current) return current.v > 99 end, generates the optimal path because it would hide the "wait" option until velocity is 100.
Run using lua a-star-velocity-demo.lua.
