Search code examples
javapath-findinga-starheuristics

Weird behavior in A* algorithm with diagonal heuristic

I'm playing with the A* algorithm, so I can take a picture of a maze with a webcam and have a program solve it. Here are the results: https://i.sstatic.net/lbmKg.png

When I use h = 0, I get a nice solution. Using manhattan distance also gives a good solution. However, diagonal distance does some weird things, like the pattern that I circled in green. Or even more weird is this one, from a different maze:

https://i.sstatic.net/dTzyr.png

Did I wrongly implement the diagonal distance?

public void findHeuristic()
{
    int dx = Math.abs(x - MazeBot.goal.x);
    int dy = Math.abs(y - MazeBot.goal.y);

    h = 10 * (dx + dy) - 6 * Math.min(dx, dy); //diagonal distance
}
Solution

  • I haven't heard the term "diagonal distance" before, but I think I see what you're getting at -- you're measuring how many "jumps" it would take where you can jump vertically, horizontally, or diagonally. What I can't figure out is why where your coefficients are coming from, unless you're wanting to weight the jumps by the length of the move. In which case, you're just starting to approximate a Euclidean metric.

    So, assuming every 'jump' is the same size: dx + dy - Math.min(dx, dy)

    However, noting that diagonal jobs are actually sqrt(2) length, you'd end up with (dx + dy) - (2 - Math.sqrt(2)) * Math.min(dx, dy). That's about (dx + dy) - 0.5857 * Math.min(dx, dy). I assume you're wanting to keep to integers and no division for speed and efficiency, and since if the output is scaled by a positive constant it won't change the utility of your heuristic, you just chose some very close coefficients by multiplying everything by 10: 10 * (dx + dy) - 5.857 * Math.min(dx, dy) is about 10 * (dx + dy) - 6 * Math.min(dx, dy)'. (What you have now.)

    Since you've created a finer approximation of the Euclidean metric, your paths will tend to necessarily assume more direct lines to the goal(s). However, since your approximation is in fact an approximation of an approximation, you're going to end up with some strange results:

    The greater your Math.min(dx, dy) the greater your error since 6 > 5.857 you're effectively making the diagonal paths less costly that it should be, but as you get closer to them non-diagonal paths start to measure relatively better. This isn't leading to a truly less optimal path, per se, but I'd expect it to create some difficult-to-predict strangeness in your traversal.