Pathfinding on a grid · onegame cookbook

Find paths for units in a C# game with onegame’s Navigation package: a NavGrid from text, a one-shot FindPath as a level check, and a unit whose NavState searches a few iterations a tick and then follows the path, checked from a scenario with the same hash every run.

RecursiveAI.OneGame.Navigation (new in 1.11.0, stable since 1.14.0) finds paths on a grid for positions that are Fixed numbers. It gives the same answer on every node, keeps a unit’s navigation in one synced value, so saves, replays and replicas carry it, and spreads long searches over ticks. Everything below ran on onegame 1.15.2 from NuGet.

Add the package

Create the game with onegame new trail, delete art/ and the scenarios, and add the package:

Terminal

dotnet add package RecursiveAI.OneGame.Navigation --version 1.15.2

It isn’t part of the game template. A game that wants paths adds it, and the OnePath search library comes with it.

The game

A 12 by 7 level and a scout that walks to the cell it is told. Replace Game.cs:

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.

Watch it search and walk

With the MCP client from Drive a running game over MCP, on onegame run --no-hot --headless -- --live /tmp/onegame/trail.sock:

Text

command_send {"entity": 1, "command": "Place", "args": [0, 0]} -> {"entity":"Scout#1","command":"Place","status":"Queued"}
command_send {"entity": 1, "command": "GoTo", "args": [11, 6]} -> {"entity":"Scout#1","command":"GoTo","status":"Queued"}
step {"frames": 2} -> {"frame":2,"tick":2,"hash":"4dafd82e9ffc033f"}
state_query {"entity": "Scout"} -> {"id":1,"type":"Scout","Position":[-88,-48],"Nav":{"status":"Searching","start":0,"goal":83,"spent":16,"next":0,"path":[]}}
step {"frames": 10} -> {"frame":12,"tick":12,"hash":"e572ffb3e3296b18"}
state_query {"entity": "Scout"} -> {"id":1,"type":"Scout","Position":[-72.000000008,-48],"Nav":{"status":"Found","start":0,"goal":83,"spent":0,"next":1,"path":[0,1,2,3,4,5,6,19,31,32,33,45,57,58,59,71,83]}}
step {"frames": 400} -> {"frame":412,"tick":412,"hash":"d28f9866dc5c11a2"}
state_query {"entity": "Scout"} -> {"id":1,"type":"Scout","Position":[88,48],"Nav":{"status":"Arrived","start":83,"goal":83,"spent":0,"next":17,"path":[0,1,2,3,4,5,6,19,31,32,33,45,57,58,59,71,83]}}

After two ticks the search had spent 16 iterations and was still going. By tick 12 it had found a 17-cell path, as cell indices (y * 12 + x), and the scout was walking. At tick 412 it stood on the center of cell (11, 6). A capture at tick 60 shows the walls in gray-blue, the walked part of the path in gray, the rest in green, and the scout as a yellow square going through the gap in the top wall.

Check where it arrives

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 }

Terminal

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 both times, and the same one the live session reached at tick 412. The search is part of the world, so a 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:

Terminal

onegame run --headless --frames 1

Text

error: level check: no way across (NoPath)

It exits 4. Put the row back.

Good to know

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.