A* search finds a path through a maze by combining accumulated path cost with a heuristic estimate of the remaining distance. It resembles BFS, but replaces its queue with a priority queue ordered by f(n) = g(n) + h(n). section 2.2
The Swift implementation changes the generic search machinery in several focused ways:
- Stores frontier nodes in an ascending priority queue, so the lowest f(n) is selected next. section 2.2
- Tracks each explored state's lowest known g(n) in a dictionary, allowing a cheaper route to replace an earlier one. section 2.2
- Assigns every maze hop a cost of 1 and receives the heuristic through heuristicFn(). section 2.2
- Uses Manhattan distance for four-direction movement, while Euclidean distance provides an alternative estimate. section 2.2
Searching a generated maze
Generate a 10-by-10 maze, then call astar(initialState: start, goalTestFn: goalTest, successorFn: successorsForMaze(maze3), heuristicFn: manhattanDistance). Convert the returned node with nodeToPath, mark the path, and print the maze. section 2.2
// A Cell represents the status of a grid location in the maze
enum Cell: Character {
case Empty = "O"
case Blocked = "X"
case Start = "S"
case Goal = "G"
case Path = "P"
}
typealias Maze = [[Cell]]
Use the Cell enum and Maze type to represent empty, blocked, start, goal, and path locations in the grid. section 2.2
