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
associatedtype Node : Hashable
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.
estimatedCostnever overestimates the actual cost, the
findPath(from:to:)method will find the optimal path.
estimatedCostis 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 (
the starting point of the path who’s cost is to be estimated
the end point of the path who’s cost is to be estimated
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.
the start node of the pathfinding attempt
the goal node of the pathfinding attempt
An optimal path between start and goal if it exists, otherwise an empty array.