a* pathfinding implementation in swift

main.swift
func aStar(start: Node, goal: Node) -> [Node] {
    var openList = [start]
    var closedList = [Node]()
    
    // dictionary to store the Gscore of each node
    var gScore = [start: 0]
    
    // dictionary to store the Fscore of each node
    var fScore = [start: heuristic(start, goal)]
    
    // dictionary to store the parent of each node
    var parent = [Node: Node]()
    
    while !openList.isEmpty {
        // sort openList by ascending Fscore
        openList.sort { fScore[$0]! < fScore[$1]! }
        
        let current = openList.removeFirst()
        closedList.append(current)
        
        // reached goal node
        if current == goal {
            return reconstructPath(parent, goal)
        }
        
        // loop through each neighbor of current node
        for neighbor in current.neighbors {
            // exclude nodes in the closedList
            if closedList.contains(neighbor) {
                continue
            }
            
            // calculate tentative Gscore
            let tentativeGscore = gScore[current]! + current.distances[neighbor]!
            
            // add neighbor node to openList if it's not already there
            if !openList.contains(neighbor) {
                openList.append(neighbor)
            }
            
            // if the tentative Gscore is worse than existing, skip to next neighbor
            if tentativeGscore > (gScore[neighbor] ?? Int.max) {
                continue
            }
            
            // this path is the best until now, record it!
            parent[neighbor] = current
            gScore[neighbor] = tentativeGscore
            fScore[neighbor] = tentativeGscore + heuristic(neighbor, goal)
        }
    }
    
    // no valid path found
    return []
}

// helper function to reconstruct path from start to goal node
func reconstructPath(_ parent: [Node: Node], _ current: Node) -> [Node] {
    var path = [current]
    var backtrackNode = current
    
    while parent.keys.contains(backtrackNode) {
        backtrackNode = parent[backtrackNode]!
        path.append(backtrackNode)
    }
    
    return path.reversed()
}

// heuristic function to estimate distance between two nodes
func heuristic(_ a: Node, _ b: Node) -> Int {
    return abs(a.x - b.x) + abs(a.y - b.y)
}
2314 chars
74 lines