Recursive AI

Use ALT landmarks for graph pathfinding in C#

OnePath is a free, open-source pathfinding library for .NET from Recursive AI. MIT or Apache-2.0, no native dependencies.

ALT landmarks store distances to selected graph nodes so A* can estimate the remaining route cost.

Terminal
dotnet add package RecursiveAI.OnePath

Requires .NET 10 (net10.0); .NET 9 and earlier aren’t supported.

C#
using RecursiveAI.OnePath;
 
var graph = Graph.From(new[] {
    new GraphEdge(0,1,2), new GraphEdge(1,2,3),
    new GraphEdge(0,2,9), new GraphEdge(2,3,1)
});
var landmarks = graph.BuildLandmarks(
    new() { Count = 2 });
var route = graph.FindPath(0, 3,
    new GraphOptions { Landmarks = landmarks });
Console.WriteLine($"Cost: {route.Cost}");
Text
Cost: 6

Unzip the example, then dotnet run.

The full program

The graph below has four nodes and undirected edges with integer costs. The program serializes the landmark table, reloads it against the compiled graph and compares three routes with Dijkstra.

C#
using RecursiveAI.OnePath;
 
var graph = Graph.From(new[] {
    new GraphEdge(0,1,2), new GraphEdge(1,2,3),
    new GraphEdge(0,2,9), new GraphEdge(2,3,1) });
var landmarks = graph.BuildLandmarks(new() { Count = 2 });
byte[] saved = landmarks.Serialize();
var loaded = Landmarks.Deserialize(saved, graph.Compile());
Console.WriteLine($"Landmarks: {loaded.Count}");
foreach (var (start, goal) in new[] { (0,3), (3,0), (1,3) })
{
    var alt = graph.FindPath(start, goal, new GraphOptions { Landmarks = loaded });
    var reference = graph.FindPath(start, goal,
        new GraphOptions { Algorithm = GraphAlgorithm.Dijkstra });
    Console.WriteLine($"{start}->{goal}: ALT {alt.Cost}, Dijkstra {reference.Cost}, equal {alt.Cost == reference.Cost}");
}

dotnet run prints:

Text
Landmarks: 2
0->3: ALT 6, Dijkstra 6, equal True
3->0: ALT 6, Dijkstra 6, equal True
1->3: ALT 4, Dijkstra 4, equal True

Queries reject a landmark table from a changed graph with InvalidOperationException; rebuild the table after editing edges or weights.

Variations

Choose farthest landmarks with an explicit seed. Replace the BuildLandmarks line in the full program.

C#
var landmarks = graph.BuildLandmarks(new() {
    Count = 2, Selection = LandmarkSelection.Farthest, Seed = 7 });
Text
Landmarks: 2
0->3: ALT 6, Dijkstra 6, equal True
3->0: ALT 6, Dijkstra 6, equal True
1->3: ALT 4, Dijkstra 4, equal True

The short answer

Call graph.BuildLandmarks once, then pass the returned table through GraphOptions.Landmarks for repeated routes on that graph. ALT means A* with landmarks and the triangle inequality: precomputed distances supply a lower bound for the remaining route cost. The example saves and reloads the table in memory, then checks three queries against Dijkstra using integer edge weights.

This page demonstrates reusable preprocessing and matching costs, not a timing result. The graph is deliberately small enough to read in full. Whether preprocessing is worth keeping depends on your graph, how many queries you make and how often its edges change.

Is Dijkstra and A* the same?

In OnePath, graph A* with a zero estimate runs as Dijkstra. Without landmarks, a custom heuristic or point-graph distances, automatic algorithm selection has no estimate and chooses Dijkstra. Supplying landmarks gives A* a distance lower bound; it does not change the meaning of the edge weights.

A graph edge is directed, with a finite, nonnegative weight. Graph.From adds reverse edges by default, so the example is an undirected graph. Its direct 0-to-2 edge costs 9, while going through node 1 costs 5. The route to node 3 costs 6. Both search configurations return that cost; the reverse query also costs 6 because reverse edges were added.

With multiple estimates, OnePath uses their maximum. Each estimate must remain a valid lower bound for optimal routing. A custom estimate that overstates the remaining cost is not corrected merely by also supplying landmarks. See the graph search and heuristic rules.

What is the A* path algorithm?

A* orders pending nodes using the cost already traveled plus an estimate of the cost still to go. A useful estimate points the search toward the goal without overstating the remaining distance. OnePath’s graph search resolves priority ties deterministically using its documented ordering; equal-cost alternatives keep the first parent found.

ALT builds forward and backward distance tables for each landmark. The forward table contains distances from a landmark to every node; the backward table contains distances to that landmark. Combining these distances through the triangle inequality gives a bound that also works on directed graphs. Unreachable distances are represented by positive infinity. The published ALT description specifies the bound, landmark selection and table layout.

The default selection is Avoid. The variation switches to Farthest and sets a seed so the selection is reproducible. The requested count is capped at the number of nodes, and landmarks are distinct. Increasing the count stores more distances and uses more bounds per query; it is not a promise of a shorter execution time.

How do I use ALT landmarks in C#?

Keep the table beside the graph version it describes. Serialization records the graph fingerprint, landmark IDs and distance tables. Deserialization requires the compiled graph and rejects mismatched or malformed data with GraphStateException. A query also checks whether its landmark table matches the graph, throwing InvalidOperationException after an incompatible graph edit. Rebuild preprocessing when the graph changes.

Cost hooks need separate care. A hook that lowers an edge cost below the stored weight voids the documented bound guarantee, even if the graph itself has not changed. Rebuild against the actual routing weights or omit the landmarks for that query. The sample uses integer weights and checks exact equality; the docs describe rounding differences of a few ulps for fractional weights in bidirectional search. It does not establish bit-for-bit cost equality for every graph and algorithm combination.

All onepath recipes