In A* maze search, the frontier holds locations still to explore. A priority queue pops the most promising one first—not necessarily the one added first. Here, “highest priority” means the lowest estimated total cost, f(n) = g(n) + h(n): cost so far plus estimated cost to the goal. section 2.2
A* therefore uses a different frontier from depth-first search’s stack or breadth-first search’s queue. A priority queue usually uses a binary heap, giving O(log n) pushes and pops. In Swift, the example uses SwiftPriorityQueue rather than building one from scratch. section 2.2
class Node<T>: Comparable, Hashable {
let state: T
let parent: Node?
let cost: Float
let heuristic: Float
init(state: T, parent: Node?, cost: Float = 0.0, heuristic: Float = 0.0) {
self.state = state
self.parent = parent
self.cost = cost
self.heuristic = heuristic
}
var hashValue: Int { return Int(cost + heuristic) }
}
func < <T>(lhs: Node<T>, rhs: Node<T>) -> Bool {
return (lhs.cost + lhs.heuristic) < (rhs.cost + rhs.heuristic)
}
func == <T>(lhs: Node<T>, rhs: Node<T>) -> Bool {
return lhs === rhs
}
A search node implements Comparable by comparing cost + heuristic, so the queue can order nodes by f(n). section 2.2
