Recursive AI

Find a weighted grid path in C#

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

Give mud a higher cost so the route can go around it.

Terminal
dotnet add package RecursiveAI.OnePath

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

C#
using RecursiveAI.OnePath;
 
var map = new Grid(5, 3);
// SetRect(x, y, width, height, area ID)
map.SetRect(1, 1, 3, 1, 2);
map.Areas[2] = 5;
Cell start = new(0, 1), goal = new(4, 1);
var path = map.FindPath(start, goal,
    GridOptions.FourConnected);
int steps = path.Cells.Length - 1;
Console.WriteLine(
    $"{steps} steps, cost {path.Cost}");
Text
6 steps, cost 6

The direct route through the mud would cost 16.

Unzip the example, then dotnet run.

The full program

The program searches the same grid twice. First every area has cost multiplier 1. Then it sets mud (area 2) to 5 without changing which tiles are walkable or allowing diagonals.

C#
using RecursiveAI.OnePath;
 
var map = new Grid(5, 3);
map.SetRect(1, 1, 3, 1, 2);
Cell start = new(0, 1), goal = new(4, 1);
var options = GridOptions.FourConnected;
 
Print("Uniform", map.FindPath(start, goal, options));
map.Areas[2] = 5;
Print("Weighted", map.FindPath(start, goal, options));
 
static void Print(string label, GridPath path)
{
    Console.WriteLine($"{label}: {path.Cells.Length - 1} steps, cost {path.Cost}");
    Console.WriteLine(string.Join(" -> ", path.Cells.ToArray()
        .Select(cell => $"({cell.X},{cell.Y})")));
}

dotnet run prints:

Text
Uniform: 4 steps, cost 4
(0,1) -> (1,1) -> (2,1) -> (3,1) -> (4,1)
Weighted: 6 steps, cost 6
(0,1) -> (0,0) -> (1,0) -> (2,0) -> (3,0) -> (4,0) -> (4,1)

When no walkable route exists, FindPath returns NoPath. A multiplier must be positive and finite; use AreaCosts.Wall for a cell the route must never enter.

Variations

Make mud cost the same as open ground. Add this to the snippet at the top to restore the direct route.

C#
map.Areas[2] = 1;
var direct = map.FindPath(start, goal,
    GridOptions.FourConnected);
Console.WriteLine($"{direct.Cells.Length - 1} steps, cost {direct.Cost}");
Text
4 steps, cost 4

The short answer

Set the terrain’s area ID on its cells and assign a multiplier to that ID with map.Areas[id]. Run A* with FindPath. It minimizes the sum of the movement costs, so the resulting path can take more steps than a route that ignores terrain weights. An area ID is a label, not a cost: in the example the mud stays area 2 during both searches.

How does A* find the cheapest path on a weighted grid?

OnePath’s step cost is the step length times the average of the two cells’ multipliers. It is not just the cost of the cell you enter. With ground at 1 and mud at 5, a straight step entering or leaving mud costs 3. A step from one mud cell to the next costs 5. The direct route would therefore cost 3 + 5 + 5 + 3 = 16, even though it is only four steps long. The detour costs 6 because every step stays on ground with multiplier 1.

Four-way movement keeps every step length at 1 in this example. With eight-way movement, a diagonal has length √2, and the configured corner rule still applies. A terrain multiplier changes what an allowed move costs; it doesn’t make a forbidden diagonal legal.

How do you set movement costs for different kinds of terrain?

Give each kind of terrain an area ID from 0 to 254, then set one multiplier per ID. A multiplier of 1 is the default. Use a value above 1 to discourage a surface relative to ordinary ground, and keep a wall separate (area 255). Editing a multiplier affects every cell using that ID; changing a single tile means changing that tile’s area ID instead.

Keep the heuristic weight at its default of 1 when you need the cheapest path. The heuristic weight is a search setting, not a terrain multiplier. Use GridPath.Cost to compare the price of routes and Cells.Length - 1 on a successful path to count its moves. Those answer different questions as soon as the map has more than one movement cost.

All onepath recipes