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 starting 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

The main cause of the problem here is that there are many paths with the same costs. There is a term called Tie-breaker which you need to add to your heuristic function. 

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). You may want to adjust the 0.001 to make sure the heuristic can't climb past another, shorter but uglier path in the ranks. This might produce some interesting and beautiful though suboptimal paths.

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

You can also refer to the following link, which is an excellent tutorial about A*:

http://theory.stanford.edu/~amitp/GameProgramming/Heuristics.html#S12

If you are looking to learn more about Artificial Intelligence then you visit Artificial Intelligence(AI) Tutorial. Also, if you are appearing for job profiles of AI Engineer or AI Expert then you can prepare for the interviews on Artificial Intelligence Interview Questions.