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.

Answer 2

If you want paths that look natural, you need to make sure that your costs correspond to the length on a cartesian coordinate system. That means the cost of moving diagonally should be sqrt(2) times the cost of moving vertically or horizontally.

Answer 3

You can add 'control effort' to the cost calculations for each square. The actor will try not to turn or change direction too much as that will add a cost to the path:

http://angryee.blogspot.com/2009/03/better-pathfinding.html

Answer 4

If I remember correctly, the trick to this is to add an extra parameter to the cost function (for every step between adjacent nodes, or squares in your case) that penalises turns slightly more than normal (for example, having a relative cost of greater than sqrt(2) for digonal moves). Now, there's probably a fine line between smoothing out the path and actually decreasing the optimality of the route (elongating it), however, and you're not going to be able to avoid this in any way. There's a certain trade-off you'll need to discover specific to your own application, and this can only really be achieved by testing.

There was an article on a game dev site, I believe, that detailed exactly how this could be done, but I can't seem to find it at the moment. Have a play around with your cost function anyway and see what results you get - I'm pretty sure that's the way to go.

Answer 5

What is more 'sensible'? Straighter? You need to quantify it properly if the algorithm is going to do anything about it.

Since moving diagonally is as inexpensive as moving horizontally/vertically, all the paths are equivalent according to all the criterion available to A*. If you want a more 'sensible' path, you need to tell the algorithm that some paths are more desirable than others, effectively weighting horizontal/vertical as 'better' than diagonal. As far as I can see, that would be altering the parameters of your environment.