yog - v3.0.0

yog/pathfinding/a_star

A* search algorithm with heuristic guidance.

Values

a_star

</> 
pub fn a_star(
  in graph: model.Graph(n, e),
  from start: Int,
  to goal: Int,
  with_zero zero: e,
  with_add add: fn(e, e) -> e,
  with_compare compare: fn(e, e) -> order.Order,
  heuristic h: fn(Int, Int) -> e,
) -> option.Option(utils.Path(e))

Finds the shortest path using A* search with a heuristic function.

A* is more efficient than Dijkstra when you have a good heuristic estimate of the remaining distance to the goal.

Time Complexity: O((V + E) log V)

Parameters

  • heuristic: A function that estimates distance from any node to the goal. Must be admissible (h(n) ≤ actual distance).

a_star_float

</> 
pub fn a_star_float(
  in graph: model.Graph(n, Float),
  from start: Int,
  to goal: Int,
  heuristic h: fn(Int, Int) -> Float,
) -> option.Option(utils.Path(Float))

Finds the shortest path using A* with float weights.

This is a convenience wrapper around a_star that uses:

  • 0.0 as the zero element
  • float.add for addition
  • float.compare for comparison

You still need to provide a heuristic function.

a_star_int

</> 
pub fn a_star_int(
  in graph: model.Graph(n, Int),
  from start: Int,
  to goal: Int,
  heuristic h: fn(Int, Int) -> Int,
) -> option.Option(utils.Path(Int))

Finds the shortest path using A* with integer weights.

This is a convenience wrapper around a_star that uses:

  • 0 as the zero element
  • int.add for addition
  • int.compare for comparison

You still need to provide a heuristic function.

Example

// Grid distance heuristic (Manhattan distance)
let heuristic = fn(from, to) {
  let dx = int.absolute_value(from.x - to.x)
  let dy = int.absolute_value(from.y - to.y)
  dx + dy
}

a_star.a_star_int(graph, from: start, to: goal, heuristic: heuristic)

implicit_a_star

</> 
pub fn implicit_a_star(
  from start: state,
  successors_with_cost successors: fn(state) -> List(
    #(state, cost),
  ),
  is_goal is_goal: fn(state) -> Bool,
  heuristic h: fn(state) -> cost,
  with_zero zero: cost,
  with_add add: fn(cost, cost) -> cost,
  with_compare compare: fn(cost, cost) -> order.Order,
) -> option.Option(cost)

Finds the shortest path in an implicit graph using A* search with a heuristic.

Time Complexity: O((V + E) log V)

Parameters

  • heuristic: Function that estimates remaining cost from any state to goal. Must be admissible.

implicit_a_star_by

</> 
pub fn implicit_a_star_by(
  from start: state,
  successors_with_cost successors: fn(state) -> List(
    #(state, cost),
  ),
  visited_by key_fn: fn(state) -> key,
  is_goal is_goal: fn(state) -> Bool,
  heuristic h: fn(state) -> cost,
  with_zero zero: cost,
  with_add add: fn(cost, cost) -> cost,
  with_compare compare: fn(cost, cost) -> order.Order,
) -> option.Option(cost)

Like implicit_a_star, but deduplicates visited states by a custom key.

Time Complexity: O((V + E) log V) where V and E are measured in unique keys

✨ Search Document