Recursive AI

Resume a path search across ticks in C#

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

Split a path search into small pieces of work without restarting it. The budget counts iterations, not milliseconds.

Terminal
dotnet add package RecursiveAI.OnePath

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

C#
using RecursiveAI.OnePath;
 
var search = new Grid(8, 8).CreateSearch();
search.Begin(new Cell(0, 0), new Cell(7, 7));
while (search.Status == PathStatus.InProgress)
    search.Step(2); // once per tick in a game
Console.WriteLine(search.Status);

Prints:

Text
Found

Unzip the example, then dotnet run.

The loop finishes the search for a console demo. In a game, keep search between updates and call Step(2) once per tick instead of running the loop within one tick.

Full program

This creates an open square grid in memory and prints progress after every slice, followed by the completed route.

C#
using RecursiveAI.OnePath;
 
var grid = new Grid(8, 8);
var search = grid.CreateSearch();
search.Begin(new Cell(0, 0), new Cell(7, 7));
int tick = 0;
while (search.Status == PathStatus.InProgress)
{
    search.Step(2);
    Console.WriteLine($"Tick {++tick}: {search.Status}, iterations {search.Iterations}");
}
if (search.Status == PathStatus.Found)
{
    var cells = new Cell[search.PathLength];
    search.CopyPath(cells);
    Console.WriteLine(string.Join(" -> ", cells.Select(c => $"({c.X},{c.Y})")));
    Console.WriteLine(FormattableString.Invariant($"Cost: {search.PathCost:F3}"));
}

dotnet run prints:

Text
Tick 1: InProgress, iterations 2
Tick 2: InProgress, iterations 4
Tick 3: InProgress, iterations 6
Tick 4: Found, iterations 8
(0,0) -> (1,1) -> (2,2) -> (3,3) -> (4,4) -> (5,5) -> (6,6) -> (7,7)
Cost: 9.899

Do not edit the grid during a search: Step throws InvalidOperationException if it changed after Begin.

Variations

Use a wall-clock budget per tick. This complete replacement program checks a 2 ms budget between batches of eight iterations. Each outer-loop pass represents one tick; in a game, keep the search and clock between updates and run only the inner loop per update. A batch already running cannot be interrupted, so this is a soft budget, not a strict deadline. The search can also finish before the budget runs out.

C#
using System.Diagnostics;
using RecursiveAI.OnePath;
 
var search = new Grid(256, 256).CreateSearch();
search.Begin(new Cell(0, 0), new Cell(255, 255));
var clock = new Stopwatch();
const double budgetMs = 2;
while (search.Status == PathStatus.InProgress)
{
    // One update: return to your game loop after this slice.
    clock.Restart();
    while (search.Status == PathStatus.InProgress &&
           clock.Elapsed.TotalMilliseconds < budgetMs)
        search.Step(8);
}
Console.WriteLine(search.Status);
Console.WriteLine($"Path cells: {search.PathLength}");
Text
Found
Path cells: 256

Save an unfinished search and resume it. This complete replacement program saves after two iterations and restores against the same unchanged grid with matching options.

C#
using RecursiveAI.OnePath;
 
var grid = new Grid(8, 8);
var search = grid.CreateSearch();
search.Begin(new Cell(0, 0), new Cell(7, 7));
search.Step(2);
byte[] state = search.SaveState();
var resumed = grid.CreateSearch();
resumed.RestoreState(state);
while (resumed.Status == PathStatus.InProgress)
    resumed.Step(2);
Console.WriteLine(resumed.Status);
Console.WriteLine(resumed.Iterations);
Text
Found
8

The short answer

Create a GridSearch once, begin one request, and call Step(iterations) on successive ticks while its status is InProgress. Only copy the route after Found. This keeps the cells still to explore and the route back to the start across updates. Calling FindPath again every frame starts another query instead of continuing this one.

OnePath’s budget is deliberately not a wall-clock deadline. Step(2) permits at most two search iterations, irrespective of the machine’s speed or what other work that frame performs. The console program uses small slices so progress is visible; choose the budget for your own update loop rather than treating that value as a recommended frame budget.

How do I spread pathfinding over multiple frames?

Keep the grid and its search handle alive between frames. Begin when a new request arrives, step only while the request remains in progress, then consume its final status. The full program shows the entire lifecycle, including allocating a destination array of PathLength and filling it with CopyPath.

A slice ending with InProgress is not a failed path. The search still has work. NoPath is a completed search that could not reach the goal. Validate your request with TryBegin if invalid endpoints are expected user input; Begin is the throwing convenience form. Avoid publishing an unfinished route as though it reached the destination.

Slicing is also distinct from replanning. This handle continues a search over an unchanged map. If a door closes while it is running, finish or replace the request according to your application’s rules; do not mutate the map under the active handle and expect it to repair itself. The saved-search documentation describes state and restore requirements.

Can I give incremental pathfinding a time budget?

The API accepts an iteration budget. To use a millisecond budget, check a Stopwatch between small calls to Step, as in the variation above. This limits work only between batches: a batch may take you past the deadline. For A*, an iteration selects a cell to explore and checks its neighbors. JPS and JPS+ instead select a key cell where the route may need to turn; the work scanning along rows and diagonals to find those cells is not counted. Equal iteration counts therefore do not promise equal elapsed time across algorithms or maps.

Do not confuse a per-call slice with GridOptions.IterationBudget on a one-shot query. The latter ends that query with BudgetExhausted; it is not a handle you can step later. For explicitly scheduled work, use GridSearch.Step as shown above. For cooperative asynchronous square-grid queries, FindPathAsync yields between iteration slices, but it is not a background-thread or frame-deadline guarantee.

The search rules specify that slicing preserves expansion order, path and cost. Changing the slice size changes when the result becomes available, not which route wins. Saving the unfinished handle is useful when the host needs to retain that exact computation, rather than starting another search from the same endpoints.

All onepath recipes