How do I find the most “Naturally" direct route using A-star (A*)

Question

I have implemented the A* algorithm in AS3 and it works great except for one thing. Often the resulting path does not take the most “natural” or smooth route to the target. In my environment the object can move diagonally as inexpensively as it can move horizontally or vertically. Here is a very simple example; the start point is marked by the S, and the end (or finish) point by the F.

 | | | | | | | | | |
 |S| | | | | | | | |
x| | | | | | | | | |
x| | | | | | | | | |
x| | | | | | | | | |
x| | | | | | | | | |
x| | | | | | | | | |
 |F| | | | | | | | |
 | | | | | | | | | |
 | | | | | | | | | |

As you can see, during the 1st round of finding, nodes [0,2], [1,2], [2,2] will all be added to the list of possible node as they all have a score of N. The issue I’m having comes at the next point when I’m trying to decide which node to proceed with. In the example above I am using possibleNodes[0] to choose the next node. If I change this to possibleNodes[possibleNodes.length-1] I get the following path.

 | | | | | | | | | |
 |S| | | | | | | | |
 | |x| | | | | | | |
 | | |x| | | | | | |
 | | | |x| | | | | |
 | | |x| | | | | | |
 | |x| | | | | | | |
 |F| | | | | | | | |
 | | | | | | | | | |
 | | | | | | | | | |

And then with possibleNextNodes[Math.round(possibleNextNodes.length / 2)-1]

 | | | | | | | | | |
 |S| | | | | | | | |
 |x| | | | | | | | |
x| | | | | | | | | |
x| | | | | | | | | |
x| | | | | | | | | |
x| | | | | | | | | |
 |F| | | | | | | | |
 | | | | | | | | | |
 | | | | | | | | | |

All these paths have the same cost as they all contain the same number of steps but, in this situation, the most sensible path would be as follows...

 | | | | | | | | | |
 |S| | | | | | | | |
 |x| | | | | | | | |
 |x| | | | | | | | |
 |x| | | | | | | | |
 |x| | | | | | | | |
 |x| | | | | | | | |
 |F| | | | | | | | |
 | | | | | | | | | |
 | | | | | | | | | |

Is there a formally accepted method of making the path appear more sensible rather than just mathematically correct?

Answer 1

You need to add a Tie-breaker to your heuristic function. The problem here is that there are many paths with the same costs.

For a simple Tie-breaker that favors the direct route you can use the cross-product. I.e. if S is the start and E is the end, and X is the current position in the algorithm, you could calculate the cross-products of S-E and X-E and add a penalty to the heuristic the further it deviates from 0 (= the direct route).

In code:

 dx1 = current.x - goal.x
 dy1 = current.y - goal.y
 dx2 = start.x - goal.x
 dy2 = start.y - goal.y
 cross = abs(dx1*dy2 - dx2*dy1)
 heuristic += cross*0.001

See also http://theory.stanford.edu/~amitp/GameProgramming/Heuristics.html#S12, which is an excellent tutorial about A* in general.