Flow field pathfinding in C# · onepath cookbook

When many units head for the same place, compute one flow field instead of a path per unit. CreateFlowField(goal) finds the cheapest way to the goal from every cell once; each unit then asks for its next step. The program below builds a field on a small map and draws the direction it gives in every cell.

Terminal

dotnet new console -o FlowField && cd FlowField
dotnet add package RecursiveAI.OnePath --version 1.1.0

Put this in Program.cs and run dotnet run:

using RecursiveAI.OnePath;
 
string[] rows =
[
    "................",
    "..#######.......",
    "........#..###..",
    "........#....#..",
    "..####..#....#..",
    "................",
];
var map = Grid.FromText(string.Join("\n", rows));
Cell goal = new(12, 4);
 
using GridFlowField field = map.CreateFlowField(goal);
 
// Every open cell points at its next step towards the goal.
foreach (var (row, y) in rows.Select((r, y) => (r, y)))
{
    var line = new char[row.Length];
    for (int x = 0; x < row.Length; x++)
    {
        var cell = new Cell(x, y);
        line[x] = row[x] == '#' ? '#'
                : cell == goal ? 'G'
                : field.TryGetNext(cell, out Cell next) ? Arrow(next.X - x, next.Y - y)
                : '?';
    }
    Console.WriteLine(new string(line));
}
 
// Any number of units: one lookup each.
foreach (Cell unit in new Cell[] { new(0, 0), new(0, 5), new(15, 0) })
{
    field.TryGetNext(unit, out Cell next);
    Console.WriteLine($"unit at ({unit.X},{unit.Y}): cost {field.GetCost(unit):F3}, "
        + $"next ({next.X},{next.Y})");
}
 
static char Arrow(int dx, int dy) => (dx, dy) switch
{
    (1, 0) => '>', (-1, 0) => '<', (0, 1) => 'v', (0, -1) => '^',
    (1, 1) or (-1, -1) => '\\', _ => '/',   // diagonals
};

Text

>>>>>>>>>vv/<<vv
\v#######vv<<<vv
>>>>>\vv#\v###vv
>>>>>>vv#>>\v#vv
\v####\v#>>>G#v/
>>>>>>>>>>>/^<<<
unit at (0,0): cost 14.828, next (1,0)
unit at (0,5): cost 12.414, next (1,5)
unit at (15,0): cost 8.414, next (15,1)

Rows grow downward, so v points to +y; \ and / are the diagonal steps. A unit moves to next, asks again, and arrives along a shortest path; units anywhere on the map pay one lookup per step, however many there are.

Using it

Several goals: CreateFlowField(goals) takes a span of cells, and each cell then points to its nearest goal: exits, resources, any of the doors.
The map changes: the field hears about edits to the grid it came from and repairs only the affected region.
Costs and moves: pass the same GridOptions as FindPath (area costs, four- or eight-connected moves, agent size).
State: the field is IDisposable, and its state saves to bytes and restores exactly, like grids and searches; see saved search state.

Limits

One field per goal set. Many units with many different goals are better served by A* paths per unit.
It covers the whole grid, so its memory and build time grow with the map, not with the number of units.
Units don’t avoid each other. A field says where to go; for steering that keeps units apart, see Deterministic crowd simulation.

When one unit’s path has to follow a changing map, see Replan a path when the map changes.