CODEWITHSUNDEEP
algorithmsearchpath-findinga-star
Eric
Eric

Reputation: 1103

Pathfinding, A-star and velocity inertia

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.

Upvotes: 4

Views: 2065

Answers (1)

MrBrushy
MrBrushy

Reputation: 690

Dijkstra / A-Star are graph-base algorithm that are proven work on any graph.

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.

This is wrong, A-Star and Dijkstra do not care about grids. Grids are frequently used because of simplicity: the underlying graph is implicit (grids are nodes, there's a vertice between any two adjascent tile).

Graph representation

Wether or not it worked on your example only depends on wether you represented correctly your system as a graph, or not.

The first thing to note, is this:

I've tried to implement this with A-star on a one-dimensional basis

This cannot work. A ship at x=5, v=8 is not the same state as a ship at x=5, v=-5. Therefore, your state is represented by the couple (x, v). It is not a 1D problem.

The Second thing to note, is this:

Accelerate <dir> costs 0, while Do nothing costs 1.

You are giving no incentive to arriving 'soon', only on using Do nothing as little as possible. Therefore:

The optimal path is: Accelerate 100 times, wait once, Decelerates 100 times.

Is wrong for many reasons:

  • Given the inertia, one optimal (least costly) path is actually accelerate (10 times), decelerate (10 times) because 1+2+3+4+5+6+7+8+9+10+9+8+7+6+5+4+3+2+1 = 100 and the end is reached in 19 steps for a cost of zero
  • One other optimal path would be accelerate once, alternate (acc/decel) 49 times, decelerate. Then the end is reached in ~102 steps for a total cost of zero
  • There are many more similarly 'optimal' paths (zero-cost) that you do not want.

To fix this, simply give a non-zero penalty to spending time away from the objetive cell (a constant will do, or maybe euclidian distance?) regardless of action taken. (Quite the contrary, I would put a fixed 'fuel' penalty of 1 to applying thrust, to obtain the most energy-efficient path when several are available, but this is off-topic)

Fix your implementation

If your A-Star implementation gives a result with non-zero cost when we know there are paths of lower cost, then you have a bug that you need to fix.

Going X, Y

If you plan to navigate in a 2D grid with inertia, you'll need a 4D node representation (x, y, Vx, Vy).

Be wary of two things:

  • 4D space may become very memory-intensive. And since x and Vx are linked, you won't be able to use jump-point search to remedy this.
  • In 4D with obstacles, collision detections will be more complex than with traditional cell-base movement. To be sure you don't jump through walls, use naive raycast, or (better) poll the vertex movement using Bresenham's Line Algorithm.

Upvotes: 1

Related Questions