Graph

public protocol Graph

This protocol declares the requirements for optimal pathfinding in a directed graph of nodes and implements the A* algorithm via an extension.

  • The type for the nodes or points in the graph

    Declaration

    Swift

    associatedtype Node : Hashable
    Show on GitHub

Optimal pathfinding requirements

  • The endpoints of all edges that start from a certain reference node

    Declaration

    Swift

    func nodesAdjacent(to node: Node) -> Set<Node>

    Parameters

    node

    The reference node
    Show on GitHub

  • The estimated/heuristic cost to reach the indicated end node from a given start node

    The way you implement the estimation of the cost will impact the efficiency of the path finding algorithm.

    Admissibility:

    When the estimatedCost never overestimates the actual cost, the findPath(from:to:) method will find the optimal path.

    Monotonicity

    When the estimatedCost is a monotone decreasing funciton, the findPath(from:to:) method is guaranteed to find an optimal path without processing any node more than once. The function is said to be monotone decreasing when estimatedCost(from: start, to: end) <= cost(from: start, to: intermediate) + estimatedCost(from: intermediate, to: end) for every edge (start, intermediate).

    Declaration

    Swift

    func estimatedCost(from start: Node, to end: Node) -> Float

    Parameters

    start

    the starting point of the path who’s cost is to be estimated
    end

    the end point of the path who’s cost is to be estimated
    Show on GitHub

  • The actual cost to reach the indicated end node from a given start node

    Declaration

    Swift

    func cost(from start: Node, to end: Node) -> Float

    Parameters

    start

    the starting point of the path who’s cost is to be estimated
    end

    the end point of the path who’s cost is to be estimated
    Show on GitHub

A* Implementation

  • findPath(from:to:) Extension method

    Attempts to find the optimal path from a reference node to the indicated goal node. If such a path exists, it is returned in start to end order. If it doesn’t exist, the returned array will be empty.

    Declaration

    Swift

    public func findPath(from startNode: Node, to goalNode: Node) -> [Node]

    Parameters

    startNode

    the start node of the pathfinding attempt
    goalNode

    the goal node of the pathfinding attempt

    Return Value

    An optimal path between start and goal if it exists, otherwise an empty array.

    Show on GitHub