AStar (yog-fsharp) | Yog.FSharp

AStar Module

Namespace: Yog.Pathfinding
Assembly: Yog.FSharp.dll

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	aStar	O((V + E) log V)	Pathfinding with good heuristics
Implicit A*	implicitAStar	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

Functions and values

Function or value	Description
`aStar zero add compare heuristic start goal graph` Full Usage: `aStar zero add compare heuristic start goal graph` Parameters: zero : `'e` add : `'e -> 'e -> 'e` compare : `'e -> 'e -> int` heuristic : `NodeId -> NodeId -> 'e` start : `NodeId` goal : `NodeId` graph : `Graph<'n, 'e>` Returns: `Path<'e> option`	Finds the shortest path using A* search with a heuristic function. Time Complexity: O((V + E) log V) zero : `'e` add : `'e -> 'e -> 'e` compare : `'e -> 'e -> int` heuristic : `NodeId -> NodeId -> 'e` start : `NodeId` goal : `NodeId` graph : `Graph<'n, 'e>` Returns: `Path<'e> option`
`aStarFloat heuristic start goal graph` Full Usage: `aStarFloat heuristic start goal graph` Parameters: heuristic : `NodeId -> NodeId -> float` start : `NodeId` goal : `NodeId` graph : `Graph<'n, float>` Returns: `Path<float> option`	Finds the shortest path using A* with float weights. heuristic : `NodeId -> NodeId -> float` start : `NodeId` goal : `NodeId` graph : `Graph<'n, float>` Returns: `Path<float> option`
`aStarInt heuristic start goal graph` Full Usage: `aStarInt heuristic start goal graph` Parameters: heuristic : `NodeId -> NodeId -> int` start : `NodeId` goal : `NodeId` graph : `Graph<'n, int>` Returns: `Path<int> option`	Finds the shortest path using A* with integer weights. heuristic : `NodeId -> NodeId -> int` start : `NodeId` goal : `NodeId` graph : `Graph<'n, int>` Returns: `Path<int> option`
`implicitAStar zero add compare heuristic successors isGoal start` Full Usage: `implicitAStar zero add compare heuristic successors isGoal start` Parameters: zero : `'cost` add : `'cost -> 'cost -> 'cost` compare : `'cost -> 'cost -> int` heuristic : `'state -> 'cost` successors : `'state -> ('state * 'cost) list` isGoal : `'state -> bool` start : `'state` Returns: `'cost option`	Finds the shortest path in an implicit graph using A* search with a heuristic. zero : `'cost` add : `'cost -> 'cost -> 'cost` compare : `'cost -> 'cost -> int` heuristic : `'state -> 'cost` successors : `'state -> ('state * 'cost) list` isGoal : `'state -> bool` start : `'state` Returns: `'cost option`
`implicitAStarBy zero add compare heuristic successors keyFn isGoal start` Full Usage: `implicitAStarBy zero add compare heuristic successors keyFn isGoal start` Parameters: zero : `'cost` add : `'cost -> 'cost -> 'cost` compare : `'cost -> 'cost -> int` heuristic : `'state -> 'cost` successors : `'state -> ('state * 'cost) list` keyFn : `'state -> 'key` isGoal : `'state -> bool` start : `'state` Returns: `'cost option`	Like `implicitAStar`, but deduplicates visited states by a custom key. zero : `'cost` add : `'cost -> 'cost -> 'cost` compare : `'cost -> 'cost -> int` heuristic : `'state -> 'cost` successors : `'state -> ('state * 'cost) list` keyFn : `'state -> 'key` isGoal : `'state -> bool` start : `'state` Returns: `'cost option`