title: Pathfinding, A-star and velocity inertia
body: <p>There's a duplicate question with an answer that I've tried to implement here and having difficulty. <a href="https://stackoverflow.com/questions/30720120/how-to-do-pathfinding-when-a-unit-has-inertia">How to do pathfinding when a unit has inertia?</a></p>
  
  <p>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.</p>
  
  <p>But then I also wanted to add in "velocity", so instead of the neighbours being <code>move left</code>, <code>move right</code>, <code>move up</code>, <code>move down</code>, it's <code>accelerate left</code>, <code>accelerate right</code>, <code>accelerate up</code>, <code>accelerate down</code>, <code>do nothing</code>. On each move, the velocity from the previous move is preserved, and the delta from the acceleration is added. <code>Accelerate &lt;dir&gt;</code> costs 0, while <code>Do nothing</code> costs 1.</p>
  
  <p>I've tried to implement this with A-star on a one-dimensional basis, getting it to find a path to move from <code>(X=0, velocity=0)</code> to <code>(X=100, velocity=0)</code>. The choice available are always <code>(Accelerate Cost=0, Decelerate Cost=0, Wait Cost=1)</code>.</p>
  
  <p>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 (<code>X=100, velocity=0)</code>.</p>
  
  <p>The optimal path is: Accelerate 100 times, wait once, Decelerates 100 times.</p>
  
  <p>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.</p>
  
  <p>Any ideas on how to modify A* or Djikstra or is there an alternative pathfinding algorithm I could use involving inertia?</p>
  
  <p>You can look at my code at <a href="https://gist.github.com/meric/93540d1cff502684aac2" rel="nofollow noreferrer">https://gist.github.com/meric/93540d1cff502684aac2</a></p>
  
  <p>Uncommenting line 120 <code>filter = function(current) return current.v &gt; 99 end,</code> generates the optimal path because it would hide the "wait" option until velocity is 100.</p>
  
  <p>Run using <code>lua a-star-velocity-demo.lua</code>.</p>