If the A* search with the Euclidean Distance heuristic allowed diagonal moves, would it still be optimal?

Question

So if I've got the A* search on a 10x10 maze with 10 obstacles and I allowed diagonal moves within this, would it still be optimal?

My answer is that it would still be optimal, and this is because the Euclidean Distance calculates the straight line distance between two points already, so it kind of goes over the search space diagonally anyway, so I don't think it would make a difference, or it may even make it better? Not sure if i'm thinking correctly.

Answer 1

It depends on the cost of diagonal moves.

Consider the uniform cost situation: the cost of diagonal movement is the same as the cost of non-diagonal (Chebyshev distance).

In this case the distance between the green and the red point is 6. In general:

def chebyshev_distance(node):
    dx = abs(node.x - goal.x)
    dy = abs(node.y - goal.y)
    return max(dx, dy)

whereas the Euclidean distance heuristic:

def heuristic(node):
    dx = abs(node.x - goal.x)
    dy = abs(node.y - goal.y)
    return sqrt(dx * dx + dy * dy)

gives heuristic ≅ 6.71 and overestimates the cost of the path, resulting in a inadmissible heuristic (may not find the optimal path).

In general:

max(|d_x|,|d_y|) = |Max| = sqrt(Max²) ≤ sqrt(Max² + min²) = sqrt(d_x² + d_y²)