Pathfinding - A * with the lowest speed

Question

Is it possible to change A * to return the shortest path with the least number of revolutions ?

One complication: the nodes can no longer differ only in their location, because their parent node is important in determining future turns, so they must also have a direction associated with them.

But the main problem that I encountered is how to work the number of turns in the partial cost of the path (g). If you multiply g by the number of turns taken (t), strange things happen: a long way with N turns closer to the end is preferable to a shorter way with N turns at the beginning.

Another less optimal solution that I am considering is the following: after calculating the shortest path, I could start the second iteration A * (with a different formula for the path cost), this time limited in the x / y range of the shortest path, and return the path with the lowest speed . Any other ideas?

Answer 1

The current "state" of the search is actually represented by two things: the node you are in and the one you are facing. You want to split each of these states into different nodes.

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

• If the edge does not represent a turn, make a new weight w , and also
• If the edge represents a turn, create a new weight w + ε , where ε is a number significantly smaller than the smallest weight.

Then just do a normal A * search. Since no weight has been reduced, the heuristic will 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 good compromise between the turns and the path length), why not transform your problem space by adding an edge for each pair of nodes connected by an unobstructed straight line; these are couples with whom you can travel without turning. There are O (n) such edges on the node, so the new graph is O (n ³ ) along the edges. This makes A * solutions like O (n ³ ) in terms of time.

Manhattan distance can be a good heuristic for A *.