The A* evaluation function ranks a search state by combining the cost already paid with an estimate of the remaining cost: f(n) = g(n) + h(n). A* explores the frontier state with the lowest f(n), distinguishing it from breadth-first and depth-first search. section 2.2
Use the three values this way:
- g(n) records the number of previous steps required to reach the state. section 2.2
- h(n) estimates the cost from the current state to the goal; an admissible heuristic never overestimates that cost. section 2.2
- A priority queue keeps frontier nodes ordered by lowest f(n), allowing the most promising state to be selected next. section 2.2
Maze search in Swift
For a grid maze without diagonal movement, Manhattan distance supplies h(n). A Node compares itself using cost + heuristic, and astar receives manhattanDistance as its heuristic function. section 2.2
