An admissible heuristic estimates the remaining cost to a goal without ever overestimating it. A* uses that estimate, h(n), alongside the cost already incurred, g(n), to explore the frontier state with the lowest f(n) = g(n) + h(n). With an admissible heuristic, the path A* finds is optimal. section 2.2
A four-direction maze
When movement has no diagonals, Manhattan distance adds the row and column distances to the goal. Walls may force a longer route, but cannot make that distance an overestimate. 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)
}
This Swift function computes the Manhattan-distance estimate from a maze location to the goal. section 2.2
