Pathfinding - A* with least turns

Question

Is it possible to modify A* to return the shortest path with the least number of turns?

One complication: Nodes can no longer be distinguished solely by their location, because their parent node is relevant in determining future turns, so they have to have a direction associated with them as well.

But the main problem I'm having, is how to work number of turns into the partial path cost (g). If I multiply g by the number of turns taken (t), weird things are happening like: A longer path with N turns near the end is favored over a shorter path with N turns near the beginning.

Another less optimal solution I'm considering is: After calculating the shortest path, I could run a second A* iteration (with a different path cost formula), this time bounded within the x/y range of the shortest path, and return the path with the least turns. Any other ideas?

Answer 1

The current "state" of the search is actually represented by two things: The node you're in, and the direction you're facing. What you want is to separate each of those states into different nodes.

So, for each node in the initial graph, split it into E separate nodes, where E is the number of incoming edges. Each of these new nodes represents the old node, but facing in different directions. The outgoing edges of these new nodes will all be the same as the old outgoing edges, but with a different weight. If the old weight was w, then...

• If the edge doesn't represent a turn, make the new weight w as well
• If the edge does represent a turn, make the new weight w + ε, where ε is some number significantly smaller than the smallest weight.

Then just do a normal A* search. Since none of the weights have decreased, your heuristic will still be admissible, so you can still use the same heuristic.

Answer 2

If you really want to minimize the number of turns (as opposed to finding a nice tradeoff between turns and path length), why not transform your problem space by adding an edge for every pair of nodes connected by an unobstructed straight line; these are the pairs you can travel between without a turn. There are O(n) such edges per node, so the new graph is O(n³) in terms of edges. That makes A* solutions as much as O(n³) in terms of time.

Manhattan distance might be a good heuristic for A*.

Answer 3

Is it possible to modify A* to return the shortest path with the least number of turns?

It is most likely not possible. The reason being that it is an example of the weight-constrained shortest path problem. It is therefore NP-Complete and cannot be solved efficiently.

You can find papers that discuss solving this problem e.g. http://web.stanford.edu/~shushman/math15_report.pdf