View Source Scurry.Astar (Scurry v2.0.1)
Implementation of A-star search algorithm to find the shortest path in 2D polygon maps.
The basic usage is;
# computes the heuristic cost between two nodes
def heur_fun(node_a, node_b) do
...
end
# Define a graph
graph = %{
node_1 => [
{node_2, cost_1_2}, {node_3, cost_1_3},
],
node_2 => [
{node_3, cost_2_3}, {node_4, cost_2_4},
],
...
}
# Do A-star search
state = Astar.search(graph, node_1, node_z, &heur_fun/2)
# Extract path
path = Astart.path(state)
[node1, ..., node_z]
Summary
Functions
Get the path from the state returned by search/4.
Params
statethe a-star state returned bysearch/4
Returns the path.
Find shortest path in graph from start to stop.
Params
grapha map of node to a list of nodes and cost tuples.startthe node from which to startstopthe node at which to endheur_funthe heuristic function used to estimate cost from a node ingraphtostop. It takes two nodes and returns a cost that should be comparable with itself for ordering.node, node :: term.
Returns the algorithms internal state which can be passed to path/1 to
obtain the actual path.