Breadth-first search finds a shortest maze path by exploring states layer by layer, but those layers can be costly to search. A* also seeks a shortest path while using an estimate of the remaining distance to choose which state to explore next. section 2.2
For a state n, g(n) is the cost of reaching it, h(n) estimates the cost from it to the goal, and f(n) = g(n) + h(n). A* takes the state with the lowest f(n) from its frontier. If h never overestimates the remaining cost—an admissible heuristic—the path found is optimal. section 2.2
Choosing a maze heuristic
In a grid maze, g counts steps taken. Straight-line, or Euclidean, distance estimates the distance left. If movement is limited to up, down, left, and right, Manhattan distance adds the horizontal and vertical distances to the goal. Walls can force a longer route; the estimate need not predict the exact path. section 2.2
func astar<StateType:
Hashable>(initialState: StateType, goalTestFn: (StateType)
-> Bool, successorFn: (StateType) -> [StateType],
heuristicFn: (StateType) -> Float) -> Node<StateType>? {
// frontier is where we've yet to go
var frontier: PriorityQueue<Node<StateType>> =
PriorityQueue<Node<StateType>>(ascending:
true, startingValues: [Node(state: initialState, parent:
nil, cost: 0, heuristic: heuristicFn(initialState))])
// explored is where we've been
var explored = Dictionary<StateType, Float>()
explored[initialState] = 0
// keep going while there is more to explore
while let currentNode = frontier.pop() {
let currentState = currentNode.state
// if we found the goal, we're done
if goalTestFn(currentState) { return currentNode }
// check where we can go next and haven't explored
for child in successorFn(currentState) {
let newcost = currentNode.cost + 1 //1 assumes a grid, there
should be a cost function for more sophisticated applications
if (explored[child] == nil) || (explored[child]! > newcost) {
explored[child] = newcost
frontier.push(Node(state: child, parent: currentNode,
cost: newcost, heuristic: heuristicFn(child)))
}
}
}
return nil // never found the goal
}
The generic Swift implementation takes goal-test, successor, and heuristic functions. Its frontier is a priority queue of nodes, and a dictionary records costs for explored states. section 2.2
A* is useful beyond mazes, including route planning and game-character pathfinding. Breadth-first search may suffice for a small graph; when a larger graph has a good heuristic, A* offers a way to focus the search. section 2.4
