nav

import nav from "nav";

let g = nav.grid(cells, 64, 64, nav.Moves.Eight);      // a u8 per cell, 0 = wall
var s = nav.search();
let cost = s.grid_path(&g, g.cell(1, 1), g.cell(60, 50)) or { ... };
for (c in s.path()) { walk_to(g.pos(c)); }              // start .. goal

nav finds paths on grids of cost bytes and on graphs given as adjacency arrays. Besides one path from a start to a goal it builds distance fields: the cost from every cell to the nearest goal, and from any cell the next step toward it. One field steers any number of units, so a horde of half a million zombies costs one search, not half a million.

Costs are integers and ties are broken by fixed rules, so a query finds the same path every time, on every platform, in tape run and in a built program. nav is pure.

Grids

A grid is a view of your cells, row by row: cell (x, y) is index y * width + x. Each cell is a u8: nav.BLOCKED (0) is a wall, any other value is the cost of entering the cell.

//  S . # . .
//  . . # . .
//  . . # . G
//  . . . . .
let cells: [20]u8 = [1, 1, 0, 1, 1,
                     1, 1, 0, 1, 1,
                     1, 1, 0, 1, 1,
                     1, 1, 1, 1, 1];
let g = nav.grid(cells[0..20], 5, 4, nav.Moves.Four);

grid(cells, width, height, moves) traps when cells.len is not width * height. The grid keeps a view of cells: they must stay alive while you use it, and a change to them shows in the next search (a door opening is a byte changing).

A step costs 10 straight and 14 diagonal (nav.STRAIGHT, nav.DIAGONAL: 1 and √2 in integers), times the cost of the cell it enters. A path’s cost is the sum of its steps. Blocked cells are never entered or left.

let a = g.cell(0, 0);
let p = g.pos(g.cell(4, 2));                 // p.x == 4, p.y == 2
@assert(g.step_cost(a, g.cell(1, 0))! == 10);
@assert(g.step_cost(a, g.cell(1, 1)) == null);   // no diagonals on a Four grid
@assert(!g.is_open(g.cell(2, 0)));

Moves

nav.Moves says which cells are neighbours. A diagonal step passes the two cells beside both its ends; the eight-way moves differ in what they let it pass:

On the map above, from S to G costs 80 with Four, 68 with Eight and 62 with EightCorner or EightAny.

Heuristics and step costs

A* adds an estimate of the remaining cost to each cell’s; grid() picks Manhattan for Four and Octile otherwise, which are exact on an open grid. The fields heuristic, straight and diagonal can be changed:

var h = nav.grid(cells[0..20], 5, 4, nav.Moves.Eight);
h.heuristic = nav.Heuristic.Euclidean;   // never overestimates, a little slower
h.heuristic = nav.Heuristic.Zero;        // no estimate: Dijkstra's search
h.straight = 1;
h.diagonal = 1;                          // a diagonal as cheap as a straight step

Manhattan on an eight-way grid overestimates: the search is faster, but the path may not be the cheapest.

Searching

A Search holds a search’s arrays and reuses them: after the first queries on a grid of some size, a query allocates nothing. Keep one per thing that searches.

var s = nav.search();
let cost = s.grid_path(&g, g.cell(0, 0), g.cell(4, 2));    // ?i64: 80
let way = s.path();                       // []const i64: start first, goal last
let fewest = s.grid_steps(&g, g.cell(0, 0), g.cell(4, 2)); // 8: steps, costs ignored

A path from or to a blocked cell is null; from a cell to itself it costs 0 and is just that cell. Each new query replaces the last one’s results. Read them with:

The views path() and trace() give are valid until the next query. s.free() gives the memory back; the search can be used again.

When equal paths tie, the same one wins every time: the search prefers the entry nearer the goal, then the smaller index, and tries neighbours east, south, west, north, then the diagonals.

Fields

A field answers “which way to the goal?” for every cell at once:

var field = nav.search();
let goals: [2]i64 = [g.cell(4, 2), g.cell(4, 0)];
field.grid_field(&g, goals[0..2]);

for (z in zombies) {
    let step = field.next(z.cell) or { continue; };   // null at a goal or walled off
    z.cell = step;
}
let far = field.cost(g.cell(0, 0));       // ?i64: the cost to the nearest goal
let route = field.trace(g.cell(0, 0));    // the cells from there to it

next(c) is the cell to step to from c, and cost(c) what the rest of the way costs: the same as grid_path from c to the nearest goal. Rebuild the field when the goals or the map change, and keep it in a Search of its own while other searches run. Goals that are blocked are ignored; to send units at a wall, make the cells in front of it the goals.

Graphs

A graph is given as compact adjacency arrays (CSR): node n’s edges are offsets[n] up to offsets[n + 1], edge e going to targets[e] at cost costs[e]. Edges are one-way; an undirected edge is two.

// 0->1 7, 0->2 9, 0->5 14, 1->2 10, 1->3 15, 2->3 11, 2->5 2, 3->4 6, 5->4 9
let offsets: [7]i64 = [0, 3, 5, 7, 8, 8, 9];
let targets: [9]i64 = [1, 2, 5, 2, 3, 3, 5, 4, 4];
let costs: [9]i64 = [7, 9, 14, 10, 15, 11, 2, 6, 9];
var gr = nav.graph(offsets[0..7], targets[0..9], costs[0..9]);

var s = nav.search();
let c = s.graph_path(&gr, 0, 4);         // 20, s.path() is [0, 2, 5, 4]
let src: [1]i64 = [0];
s.graph_field(&gr, src[0..1]);           // s.cost(n) for every n: 0 7 9 20 20 11
let before4 = s.next(4);                 // 5: the node before 4 on the way from 0
let n = gr.nodes();                      // 6

graph traps when costs.len is not targets.len or the offsets don’t run from 0 to targets.len upward; a search traps on an edge with a negative cost or a target outside the graph. Without positions a graph search is Dijkstra’s. Give A* the nodes’ positions and the cost of a unit of distance, and it estimates the rest of the way:

gr.set_positions(points, 9.8);           // []const math3d.Vec3, one per node
let guess = gr.estimate(0, 4);           // floor(distance * 9.8)

The estimate must not exceed the real cost: every edge must cost at least scale times its length. For a field toward goals on an undirected graph, pass the goals as the sources.

Over several frames

Each query is a begin_ call and run. run(budget) expands at most budget nodes (0: no limit) and says where the query stands, so a long search can take a slice of every frame:

s.begin_grid_path(&g, start, goal);
// each frame:
if (s.run(500) == nav.Status.Found) { follow(s.path()); }

The others are begin_grid_steps, begin_grid_field, begin_grid_field_steps, begin_graph_path and begin_graph_field. While a query runs, the grid’s cells (or the graph’s arrays) must not change.

One-off paths

let p = nav.find_grid_path(&g, g.cell(0, 0), g.cell(4, 2)) or { return; };
io.println("{p.cost} over {p.nodes.len()} cells");   // a nav.Path: nodes, cost
let q = nav.find_graph_path(&gr, 0, 4);              // ?nav.Path

These make a search state for the call and copy the path out: fine now and then, wasteful every frame.

Last modified: 2026-10-31 22:08:39 UTC