a_star

A* (A-Star) search algorithm for optimal pathfinding with heuristic guidance.

A* is an informed search algorithm that finds the shortest path from a start node to a goal node using a heuristic function to guide exploration. It combines the completeness of Dijkstra’s algorithm with the efficiency of greedy best-first search.

Algorithm

Algorithm	Function	Complexity	Best For
A* Search	`a_star/7`	O((V + E) log V)	Pathfinding with good heuristics
Implicit A*	`implicit_a_star/7`	O((V + E) log V)	Large/infinite graphs generated on-demand

Key Concepts

Evaluation Function: f(n) = g(n) + h(n)
- g(n): Actual cost from start to node n
- h(n): Heuristic estimate from n to goal
- f(n): Estimated total cost through n
Admissible Heuristic: h(n) ≤ actual cost (never overestimates)
Consistent Heuristic: h(n) ≤ cost(n→n’) + h(n’) (triangle inequality)

When to Use A*

Use A when:*

You have a specific goal node (not single-source to all)
You can provide a good heuristic estimate
The heuristic is admissible (underestimates)

Use Dijkstra when:

No good heuristic available (h(n) = 0 reduces A* to Dijkstra)
You need shortest paths to all nodes from a source

Heuristic Examples

Domain	Heuristic	Admissible?
Grid (4-way)	Manhattan distance	Yes
Grid (8-way)	Chebyshev distance	Yes
Geospatial	Haversine/great-circle	Yes
Road networks	Precomputed landmarks	Yes

Use Cases

Video games: NPC pathfinding on game maps
GPS navigation: Route planning with distance estimates
Robotics: Motion planning with obstacle avoidance
Puzzle solving: Sliding puzzles, mazes, labyrinths

References

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,
  with_heuristic h: fn(Int, Int) -> e,
) -> option.Option(path.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

zero: The identity element for addition (e.g., 0 for integers)
add: Function to add two weights
compare: Function to compare two weights
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,
  with_heuristic h: fn(Int, Int) -> Float,
) -> option.Option(path.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,
  with_heuristic h: fn(Int, Int) -> Int,
) -> option.Option(path.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, with_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,
  with_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

zero: The identity element for addition (e.g., 0 for integers)
add: Function to add two costs
compare: Function to compare two costs
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,
  with_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.

Essential when your state carries extra data beyond what defines identity. The visited_by function extracts the deduplication key from each state.

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