CODEWITHSUNDEEP
algorithmmethodspath-findinga-starheuristics
user2045279
user2045279

Reputation: 711

Extension to Pathfinding - Path of fewest turns

I've used A* (and Dijkstra's algorithm) in many applications, but I'm stuck finding the path with the fewest number of turns, while path length is irrelevant. I am working with an up-down-left-right grid, no diagonals.

A* defines Cost = DistanceFromStart + Heuristic(Manhattan), and I've tried to extend it by adding a numTurns cost. This works perfectly until I get to a case like this:

| 0 0 0 0 0 * 0 0
| 0 0 1' 2' + 0 0 E
| 0 0 S 1 2 * 0 0
| 0 0 0 0 0 * 0 0
| 0 0 0 0 0 * 0 0 (*=wall, 0=empty, S=start, E=end)

You will find that the path S->1->2->+ will give the same cost as s->1'->2'->+. They both have one turn so far, same distance from S, and same Manhattan. However from the +, if we took the prime ' route, we don't have to turn. But if we took the 1 2 route, we have to turn right (+1 cost). Thus, even though we may arrive there first with 1 2, it is not the path of least turns.

I have tried adjustments such as letting multiple of the same square be in the priority queue at once such that they both get a chance (if their values are minimal in the heap) and other "hacky" solutions, but keep getting cases that aren't covered. Is there an intuitive way to do this?

Thanks!

Upvotes: 4

Views: 1910

Answers (2)

ElKamina
ElKamina

Reputation: 7817

Create a new distance matrix. For locations i and j, if they are in a straight line (no turns), set distance(i,j)=1. For the rest of the elements set to infinity. Now run any shortest distance algorithm over it.

Upvotes: 3

AndyG
AndyG

Reputation: 41220

I think you need to incorporate a 'direction' into your state. When you arrive at '+' from 1->2->+ you are facing 'up', and when you arrive at '+' from 1'->2'->+ you are facing 'right'.

You can then incorporate the cost of changing direction into your 'cost-to-go'. That is, the cost of travelling from one state to the other. Now, going 1->2->+, when estimating a move to the right, will factor in the cost of changing direction, while 1'->2'->+ will not.

When you get to the 'generate children' phase of your A*, you are probably only incrementing the 'cost-so-far' by 1, the number of gridcells it took to move to a neighbor. You also need to add 1 if the neighbor's direction to your current position is != to your current direction.

For the start, you can use some special facing direction like OMNIDIRECTIONAL, so that moving to any square from the start position doesn't incur a cost.

Upvotes: 0

Related Questions