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)