@spec a_star(keyword()) :: path_result()

Find shortest path using A* with keyword options.

Options

• :in - The graph to search
• :from - Starting node
• :to - Target node
• :zero - Identity value for the weight type
• :add - Function to add two weights
• :compare - Function to compare weights (:lt, :eq, :gt)
• :heuristic - Function estimating cost to goal: fn(node) -> cost

Examples

Yog.Pathfinding.AStar.a_star(
  in: graph,
  from: :a,
  to: :c,
  zero: 0,
  add: &(&1 + &2),
  compare: &Integer.compare/2,
  heuristic: fn node -> estimate_to_goal(node) end
)

@spec a_star(
  Yog.graph(),
  Yog.node_id(),
  Yog.node_id(),
  (Yog.node_id(), Yog.node_id() -> weight),
  weight,
  (weight, weight -> weight),
  (weight, weight -> :lt | :eq | :gt)
) :: path_result()
when weight: var

Find the shortest path using A* with a heuristic function.

Parameters

• graph - The graph to search
• from - Starting node
• to - Target node
• zero - Identity value for the weight type
• add - Function to add two weights
• compare - Function to compare weights (:lt, :eq, :gt)
• heuristic - Function fn(node, goal) -> cost estimating cost to goal

Returns

• {:ok, path} - A Path struct containing the nodes and total weight
• :error - No path exists between the nodes

Examples

iex> graph = Yog.directed()
...> |> Yog.add_node(:a, nil)
...> |> Yog.add_node(:b, nil)
...> |> Yog.add_node(:c, nil)
...> |> Yog.add_edge!(:a, :b, 4)
...> |> Yog.add_edge!(:b, :c, 1)
iex> # Admissible heuristic (never overestimates)
iex> h = fn _, _ -> 0 end  # Zero heuristic = Dijkstra
iex> compare = &Yog.Utils.compare/2
iex> {:ok, path} = Yog.Pathfinding.AStar.a_star(graph, :a, :c, h, 0, &(&1 + &2), compare)
iex> path.nodes
[:a, :b, :c]
iex> path.weight
5

iex> # Grid with Manhattan distance heuristic
iex> grid = Yog.directed()
...> |> Yog.add_edge!({0,0}, {1,0}, 1)
...> |> Yog.add_edge!({1,0}, {2,0}, 1)
iex> manhattan = fn {x1, y1}, {x2, y2} -> abs(x1-x2) + abs(y1-y2) end
iex> compare = &Yog.Utils.compare/2
iex> {:ok, path} = Yog.Pathfinding.AStar.a_star(grid, {0,0}, {2,0}, manhattan, 0, &(&1+&2), compare)
iex> path.nodes
[{0,0}, {1,0}, {2,0}]
iex> path.weight
2

@spec implicit_a_star(keyword()) :: {:ok, any()} | :error

Implicit A* using keyword options.

Options

• :from - Starting state
• :successors_with_cost - Function returning neighbors with costs
• :is_goal - Function to check if a state is the goal
• :zero - Identity value for the weight type
• :add - Function to add two weights
• :compare - Function to compare weights
• :heuristic - Function estimating cost to goal: fn(state) -> cost

Examples

Yog.Pathfinding.AStar.implicit_a_star(
  from: 1,
  successors_with_cost: fn n -> [{n+1, 1}] end,
  is_goal: fn n -> n == 10 end,
  zero: 0,
  add: &(&1 + &2),
  compare: &Integer.compare/2,
  heuristic: fn n -> 10 - n end
)

@spec implicit_a_star(
  state,
  (state -> [{state, cost}]),
  (state -> boolean()),
  (state -> cost),
  cost,
  (cost, cost -> cost),
  (cost, cost -> :lt | :eq | :gt)
) :: {:ok, cost} | :error
when state: var, cost: var

Run A* on an implicit (generated) graph.

Similar to implicit Dijkstra, but uses a heuristic to guide search toward the goal.

Parameters

• from - Starting state
• successors - Function state -> [{neighbor, cost}]
• is_goal - Function state -> boolean to check if goal reached
• zero - Identity value for the weight type
• add - Function to add two weights
• compare - Function to compare weights
• heuristic - Function fn(state) -> cost estimating cost to goal

Returns

• {:ok, cost} - Minimum cost to reach goal
• :error - Goal is unreachable

Examples

# Search with heuristic guidance
iex> successors = fn
...>   1 -> [{2, 1}]
...>   2 -> [{3, 2}]
...>   3 -> [{4, 3}]
...>   4 -> []
...> end
iex> # Heuristic: distance to goal (node 4)
iex> h = fn n -> 4 - n end
iex> compare = &Yog.Utils.compare/2
iex> {:ok, cost} = Yog.Pathfinding.AStar.implicit_a_star(
...>   1, successors, fn x -> x == 4 end, h,
...>   0, &(&1 + &2), compare
...> )
iex> cost
6

@spec implicit_a_star_by(keyword()) :: {:ok, any()} | :error

Implicit A* with key function using keyword options.

Options

• :from - Starting state
• :successors_with_cost - Function returning neighbors with costs
• :visited_by - Function to extract a key for visited tracking
• :is_goal - Function to check if a state is the goal
• :zero - Identity value for the weight type
• :add - Function to add two weights
• :compare - Function to compare weights
• :heuristic - Function estimating cost to goal: fn(state) -> cost

@spec implicit_a_star_by(
  state,
  (state -> [{state, cost}]),
  (state -> term()),
  (state -> boolean()),
  (state -> cost),
  cost,
  (cost, cost -> cost),
  (cost, cost -> :lt | :eq | :gt)
) :: {:ok, cost} | :error
when state: var, cost: var

Implicit A* with a key function for visited state tracking.

Similar to implicit_a_star/7, but uses a key function for visited tracking.

Parameters

• from - Starting state
• successors - Function state -> [{neighbor, cost}]
• key_fn - Function state -> key for visited tracking
• is_goal - Function state -> boolean to check if goal reached
• zero - Identity value for the weight type
• add - Function to add two weights
• compare - Function to compare weights
• heuristic - Function fn(state) -> cost estimating cost to goal

Examples

iex> _successors = fn {x, y, _dir} -> [{{x + 1, y, :east}, 1}, {{x, y + 1, :south}, 1}] end
iex> _key_fn = fn {x, y, _dir} -> {x, y} end
iex> _h = fn {x, y, _} -> (10 - x) + (10 - y) end
iex> _goal_fn = fn {x, y, _} -> x == 10 and y == 10 end
iex> _compare = &Yog.Utils.compare/2
iex> #Yog.Pathfinding.AStar.implicit_a_star_by(
...> #  {0, 0, :north}, _successors, _key_fn,
...> #  _goal_fn, 0, &(&1 + &2), _compare, _h
...> #)
...> # {:some, 20}