14 Apr 2013

Oliver P. asked me about diagonal distances in grids, and why there are several different formulas for them:

PolicyAlmanac’s code

From here:

Manhattan = 10
Diagonal = sqrt(Manhattan_Squared + Manhattan_Squared)

If NE, NW, SE or SW
    G = ParentG + Diagonal
Else
    G = ParentG + Manhattan

If Xdistance > Ydistance
    H = (Ydistance * diagonal) + ((Xdistance - Ydistance) * Manhattan)
Else
    H = (Xdistance * diagonal) + ((Ydistance - Xdistance) * Manhattan)

My code, from my pathfinding pages

h_diagonal(n) = min(abs(n.x-goal.x), abs(n.y-goal.y))
h_straight(n) = (abs(n.x-goal.x) + abs(n.y-goal.y))
h(n) = D2 * h_diagonal(n) + D * (h_straight(n) - 2*h_diagonal(n)))

My code, from an email

This code has a bug!!

D * (XDistance + YDistance) - (D - D2) * MIN(XDistance, YDistance)

Here’s the corrected code:

D * (XDistance + YDistance) - (2 * D - D2) * MIN(XDistance, YDistance)