Routes on graphs · onepath cookbook

Find routes on a weighted graph with OnePath, speed up repeated queries with landmarks, and link nearby points into a point graph.

using RecursiveAI.OnePath;
 
// A small road network: node ids, and edges with travel times in minutes.
var roads = Graph.From(new[]
{
    new GraphEdge(0, 1, 4.0), new GraphEdge(1, 2, 1.5), new GraphEdge(0, 2, 7.0),
    new GraphEdge(2, 3, 2.0), new GraphEdge(1, 3, 6.0), new GraphEdge(3, 4, 3.0),
});
GraphPath route = roads.FindPath(0, 4);
Console.WriteLine($"0 -> 4: {string.Join(" -> ", route.Nodes.ToArray())}, {route.Cost} minutes");
 
// Landmarks (ALT) speed up repeated queries on the same graph; the answer is the same.
Landmarks landmarks = roads.BuildLandmarks();
GraphPath fast = roads.FindPath(0, 4, GraphOptions.WithLandmarks(landmarks));
Console.WriteLine($"with landmarks: {string.Join(" -> ", fast.Nodes.ToArray())}, {fast.Cost} minutes");
 
// A point graph links points closer than MaxDistance.
var points = PointGraph.From(new[] { new Point3(0, 0), new Point3(1, 0), new Point3(2, 0), new Point3(2, 1) },
                             new PointGraphOptions { MaxDistance = 1.1 });
GraphPath walk = points.FindPath(new Point3(0, 0), new Point3(2, 1));
Console.WriteLine($"point graph: {walk.Nodes.Length} nodes, cost {walk.Cost}");

Text

0 -> 4: 0 -> 1 -> 2 -> 3 -> 4, 10.5 minutes
with landmarks: 0 -> 1 -> 2 -> 3 -> 4, 10.5 minutes
point graph: 4 nodes, cost 3

Good to know

Graph.From(edges) builds a weighted graph from GraphEdge(from, to, weight) values, each added in both directions unless you pass directed: true. FindPath returns Nodes and Cost; bidirectional search is an option.
Landmarks (ALT) precompute distances to a few nodes once, which tightens the heuristic for every later query on the same graph. The path is the same; the search is shorter on large road networks. Landmarks serialize, so you can build them offline.
PointGraph.From(points, options) links every pair of points closer than MaxDistance, for waypoints, cover points or a coarse network over open terrain.

Graphs, bidirectional search and the landmark format are in graphs.