There is a duplicate question with the answer that I tried to implement here and with difficulty. How to do a path search when the device has inertia?
I have a grid with obstacles where the computer can move in four main directions, and implemented a path search using the A-star or Jikstra algorithm.
But then I would also add "speed", so instead of neighbors move left, move right, move up, move down, this accelerate left, accelerate right, accelerate up, accelerate down, do nothing. At each turn, the speed from the previous turn is saved, and the delta from acceleration is added. Accelerate <dir>costs 0, but do nothingcosts 1.
I tried to implement this with A-star on a one-dimensional basis, to find a way to go from (X=0, velocity=0)to (X=100, velocity=0). Available choices always (Accelerate Cost=0, Decelerate Cost=0, Wait Cost=1).
He finds a suboptimal way to successfully complete the task. Speeding up only twice, and then waiting 49 times, slows down once, then waits 2 more times and another braking lands ( X=100, velocity=0).
The best way: speed up 100 times, wait once, stop 100 times.
It seems that the star can handle the search for the path in the grid (X, Y), where X and Y are independent, but cannot process the grid (X, Y), where Y also depends on X.
Any ideas on how to change A * or Djikstra, or is there an alternative path-finding algorithm that I could use using inertia?
https://gist.github.com/meric/93540d1cff502684aac2
Uncommenting line 120 filter = function(current) return current.v > 99 end, , , 100.
lua a-star-velocity-demo.lua.