Imagine crossing a city grid without diagonal streets: reaching a destination takes horizontal blocks plus vertical blocks. For two maze locations, Manhattan distance adds the absolute difference in their columns to the absolute difference in their rows. section 2.2
Count the required moves
From row 2, column 3 to row 5, column 7, the distance is |5 − 2| + |7 − 3| = 7 moves. Walls may force a longer route, but they cannot make this four-direction trip shorter. section 2.2
func manhattanDistance(ml: MazeLocation) -> Float {
let xdist = abs(ml.col - goal.col)
let ydist = abs(ml.row - goal.row)
return Float(xdist + ydist)
}
The Swift function computes those two absolute differences and returns their sum as a heuristic estimate to the goal. section 2.2
For a maze allowing only horizontal and vertical moves, this estimate never exceeds the actual remaining path length. A* can therefore use it while retaining an optimal solution; it follows the allowed movement more closely than straight-line Euclidean distance. section 2.2
