A* pathfinding in C#

Build a Grid, call FindPath with a start and a goal, and read back the cells of the shortest path. The program below draws a small map as text, finds a path from S to G with A*, and prints the map with the path marked.

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

Put this in Program.cs and run dotnet run:

using RecursiveAI.OnePath;
 
// '.' is open ground, '#' is a wall. Row 0 is the first line.
string[] rows =
[
    "....................",
    "..######............",
    ".......#....######..",
    ".......#.........#..",
    "..######..####...#..",
    ".........#.......#..",
    ".........#..######..",
    "....................",
];
var map = Grid.FromText(string.Join("\n", rows));
 
Cell start = new(1, 2), goal = new(15, 5);
var options = new GridOptions { Algorithm = GridAlgorithm.AStar };
GridPath path = map.FindPath(start, goal, options);
 
Console.WriteLine($"{path.Status}: {path.Cells.Length} cells, cost {path.Cost:F3}, "
    + $"{path.ExpandedCount} cells expanded");
 
// Draw the map with the path on it.
char[][] picture = rows.Select(r => r.ToCharArray()).ToArray();
foreach (Cell c in path.Cells.ToArray()) picture[c.Y][c.X] = '*';
picture[start.Y][start.X] = 'S';
picture[goal.Y][goal.X] = 'G';
foreach (char[] row in picture) Console.WriteLine(new string(row));

Found: 18 cells, cost 18.657, 57 cells expanded
.********...........
.*######.*..........
.S.....#..*.######..
.......#...****..#..
..######..####.*.#..
.........#.....G.#..
.........#..######..
....................

Moves are eight-connected by default: straight steps cost 1 and diagonal steps √2, and a diagonal can’t cut the corner of a wall. With its default distance estimate (weight 1), A* returns a shortest path under those costs. Status is Found, NoPath (the goal can’t be reached), StartInvalid or GoalInvalid (a wall or off the map).

Your own map

• From your data: Grid.From(bool[,]) or new Grid(width, height) with SetWalkable(x, y, false) and SetRect for blocks of cells.
• Terrain costs: digits 1 to 9 in the text (or SetArea) mark areas, and map.Areas[2] = 3.0 makes area 2 cost three times as much to cross, so the path goes around a swamp when that is cheaper.
• World coordinates: FindPath also takes WorldPoints, and CellCenter turns a cell back into a position.
• Larger units: GridOptions.ForAgentSize(3) plans for a unit three cells wide.

Limits

• A* expands many cells on big open maps. Jump point search and HPA* find the same or nearly the same path with far fewer: see Faster grid pathfinding. A grid holds up to 2^28 cells.
• A path is a list of cells. It hugs walls and turns in 45° steps; Theta* gives smooth any-angle paths.
• The map is fixed during a search. When it changes often, replan incrementally: see Replan a path when the map changes.

Shortest paths on a road network or any graph of nodes and edges: Dijkstra shortest path in C#. Everything else starts in getting started.