---
title: "A* pathfinding on a grid in C#"
url: https://recursiveai.org/onegame/cookbook/pathfinding/
description: "A* pathfinding on a grid in a C# game: a NavGrid from text, a one-shot FindPath, and a unit that searches a few iterations a tick and walks the path, the same on every machine. Runnable, with onegame."
version: "1.15.2"
---

# A* pathfinding on a grid in C#

Add `RecursiveAI.OneGame.Navigation`, build a `NavGrid` from a text map, and call `FindPath` for a one-shot answer, or give a unit a synced `NavState` that searches a few iterations each tick and then follows the path. Positions are fixed-point, so every machine finds the same path, and saves, replays and replicas carry a unit’s navigation. The program below is a scout walking across a 12 by 7 level.

```shell
dotnet tool install -g RecursiveAI.OneGame.Cli --version 1.15.2
onegame new trail && cd trail
rm -r art scenarios/*
dotnet add package RecursiveAI.OneGame.Navigation --version 1.15.2
```

You need the .NET 10 SDK. The package isn’t part of the game template; the OnePath search library comes with it. Replace `Game.cs` with:

```csharp
using System;
using System.Numerics;
using OneGame.Core;
using OneGame.Host;
using OneGame.Navigation;
using OneGame.UI;

namespace Trail;

/// <summary>The level: 12 by 7 cells of 16 world units, centered on the origin. Level data, built the same way on every node.</summary>
public static class Level
{
    public static readonly NavGrid Map = NavGrid.FromText("""
        ............
        .#####..###.
        .....#....#.
        .###.#.##.#.
        ...#.#..#...
        .#.#.####.#.
        .#........#.
        """, new NavSpace(new FVec2(-96, -56), Fixed.FromInt(16)));   // top-left corner, cell size
}

[Entity]
public partial class Scout : Entity, IView2D
{
    [Synced] public partial FVec2 Position { get; private set; }
    [Synced] public partial NavState Nav { get; private set; }

    // A cache, not state: a restored or replicated scout rebuilds its search from Nav.
    private readonly NavSearcher _searcher = new();
    private readonly NavDebugShapes _shapes = new();

    [Command]
    public void Place(int x, int y) => (Position, Nav) = (Level.Map.CellCenter(new NavCell(x, y)), default);

    [Command]
    public void GoTo(int x, int y) =>
        Nav = _searcher.Begin(Level.Map, Position, Level.Map.CellCenter(new NavCell(x, y)), NavOptions.Default);

    protected override void OnTick()
    {
        var nav = Nav;
        if (_searcher.Advance(ref nav, Level.Map, budget: 8)) { Nav = nav; }   // 8 search iterations a tick
        if (nav.Status == NavStatus.Found)
        {
            var p = Position;
            Nav = nav.Follow(Level.Map, ref p, Fixed.FromInt(2));              // 2 units a tick; Arrived at the goal
            Position = p;
        }
    }

    [View]
    public void Draw(Draw2D d)
    {
        var map = Level.Map;
        for (var y = 0; y < map.Height; y++)
        {
            for (var x = 0; x < map.Width; x++)
            {
                var corner = map.CellCenter(new NavCell(x, y));
                d.FillRect(new Rect(corner.X.ToSingle() - 8, corner.Y.ToSingle() - 8, 16, 16),
                    map.IsBlocked(x, y) ? Color.Rgb(0x5B6B7C) : Color.Rgb(0x1D2733), 0, -1);
            }
        }

        _shapes.Clear();
        _shapes.AddPath(map, Nav);   // the path: walked part gray, the rest green
        foreach (var l in _shapes.Lines) { d.Line(l.From, l.To, Color.Rgba(l.Rgba), l.Width, 1); }
        foreach (var r in _shapes.Rects) { d.FillRect(new Rect(r.Position.X, r.Position.Y, r.Size.X, r.Size.Y), Color.Rgba(r.Rgba), 0, 1); }
        d.FillRect(new Rect(Position.X.ToSingle() - 5, Position.Y.ToSingle() - 5, 10, 10), Color.Rgb(0xF2C14E), 0, 2);
    }
}

public sealed class TrailGame : GameDefinition
{
    public override string Name => "trail";

    public override void RegisterEntities(EntityRegistry registry) =>
        OneGame.Generated.Trail.EntityTypes.Register(registry);

    public override void Setup(World world)
    {
        // A one-shot search as a level check: the far corner must be reachable from the near one.
        var route = Level.Map.FindPath(new NavCell(0, 0), new NavCell(11, 6), NavOptions.Default);
        if (!route.Found) { throw new InvalidOperationException($"level check: no way across ({route.Status})"); }
        world.Add(new Scout());
    }

    public override void DefineScreens(ScreenSet screens) => screens.Add("main", game =>
        Ui.Label(() => ((Scout)game.World.Entities[0]).Nav.Status.ToString()).Named("status").Padding(Length.Px(8)).TextColor(Color.White));
}
```

- **`NavGrid.FromText`** reads `.` as open, `#` as a wall and `1` to `9` as costed areas. `NavSpace` places it in the world, and `CellCenter` is exact integer arithmetic.
- **`FindPath`** runs a whole search in the call and returns a `NavPath` with `Status`, `Cost` and `Cells`. Use it for tools and level checks, not for units every tick.
- **`NavState`** is a synced value: the start, the goal, how far the search got, and the path. `NavSearcher.Begin` starts a search, `Advance` spends at most `budget` iterations of it per tick, and `Follow` walks the path and turns at each waypoint. A search spends counted iterations, never time, so it is deterministic.
- `_searcher` is a plain field. It holds no state the world needs.

## Check where it arrives

Save this as `scenarios/cross.yaml`:

```yaml
name: cross
description: The scout searches a few iterations a tick, then walks round the walls and arrives at the far corner.
steps:
  - command: { entity: Scout, name: Place, args: [0, 0] }
  - command: { entity: Scout, name: GoTo, args: [11, 6] }
  - step: 2
  - expect:
      state: { entity: Scout, property: Nav.status, equals: Searching }
  - step: 10
  - expect:
      state: { entity: Scout, property: Nav.path.count, equals: 17 }
  - step: 400
expect:
  - state: { entity: Scout, property: Nav.status, equals: Arrived }
  - state: { entity: Scout, property: "Position[0]", equals: 88 }
  - state: { entity: Scout, property: "Position[1]", equals: 48 }
  - ui: { id: status, text: Arrived }
```

```shell
onegame test
onegame test
```

```text
PASS cross (38 ms, tick 412, hash d28f9866dc5c11a2)
1 passed, 0 failed
PASS cross (39 ms, tick 412, hash d28f9866dc5c11a2)
1 passed, 0 failed
```

The same hash on every run. The search is part of the world, so a [replay](https://recursiveai.org/onegame/cookbook/record-and-replay/) or a replica gets the same answer.

## The level check

Close the gap next to the goal, making row 5 `.#.#.####.##`, and start the game:

```shell
onegame run --headless --frames 1
```

```text
error: level check: no way across (NoPath)
```

It exits 4. Put the row back.

## Limits and notes

- The budget changes when the path arrives, never which path it is. With `budget: 200` the search finished within two ticks, and the scenario’s first check failed with “Scout.Nav.status is Found, expected Searching”.
- When the map changes, a unit notices on its next tick: `NavState` remembers the grid’s content hash, and a stale state searches again from where the unit stands. Edit the map only from sim code, the same way on every node. The upstream `examples/pathing` owns its map in a `Terrain` entity with a synced list of walls.
- `NavOptions` sets the moves (`Eight` without corner cutting, `Four`, `EightNoSqueeze`), the unit’s width in cells, and for one-shot searches `AStar`, `Jps` or `ThetaStar`.
- Positions must stay within ±2,097,152 world units. Outside that range the package throws `NavRangeException` rather than rounding.
- For many units walking at once, `NavCrowd` steers a crowd round walls and each other, stepped once per tick as a table of the world.

More in [Navigation](https://recursiveai.org/onegame/docs/navigation/).