@bendyline/molen-pathfinding

Molen pathfinding: grid flow fields for many-unit (RTS) movement.

import { /* … */ } from '@bendyline/molen-pathfinding';

Classes

FlowField

A flow field: per-cell cost-to-goal and a unit direction toward the goal.

Constructors

Constructor

new FlowField(
   grid, 
   cost, 
   dirX, 
   dirZ
): FlowField;

Parameters

grid

Grid

cost

Float32Array

dirX

Float32Array

dirZ

Float32Array

Returns

FlowField

Properties

cost

readonly cost: Float32Array;

dirX

readonly dirX: Float32Array;

dirZ

readonly dirZ: Float32Array;

Methods

directionAt()

directionAt(x, z): [number, number];

Direction toward the goal at a world position (zero if blocked/unreachable).

Parameters

x

number

z

number

Returns

[number, number]

reachable()

reachable(cx, cz): boolean;

Parameters

cx

number

cz

number

Returns

boolean

---

Grid

A uniform grid mapping world XZ to cells, with per-cell blocked flags.

Cell count is capped (GridOptions.maxCells, default DEFAULT_MAX_CELLS) because the grid itself is the cheap part: the Uint8Array of blocked flags is 1 byte per cell, while each flow-field query over it costs about 13 bytes per cell and a full Dijkstra sweep.

Constructors

Constructor

new Grid(opts): Grid;

Parameters

opts

GridOptions

Returns

Grid

Properties

cellSize

readonly cellSize: number;

cols

readonly cols: number;

maxCells

readonly maxCells: number;

The cell-count ceiling this grid was built under (see GridOptions.maxCells).

origin

readonly origin: [number, number];

rows

readonly rows: number;

Methods

cellToWorld()

cellToWorld(cx, cz): [number, number];

Cell center in world XZ.

Parameters

cx

number

cz

number

Returns

[number, number]

inBounds()

inBounds(cx, cz): boolean;

Parameters

cx

number

cz

number

Returns

boolean

index()

index(cx, cz): number;

Parameters

cx

number

cz

number

Returns

number

isBlocked()

isBlocked(cx, cz): boolean;

Parameters

cx

number

cz

number

Returns

boolean

setBlocked()

setBlocked(
   cx, 
   cz, 
   value?
): void;

Parameters

cx

number

cz

number

value?

boolean

Returns

void

worldToCell()

worldToCell(x, z): [number, number];

World XZ → cell coordinates (floored).

Parameters

x

number

z

number

Returns

[number, number]

Interfaces

GridOptions

Properties

cellSize

cellSize: number;

World size of one cell (square).

cols

cols: number;

maxCells?

optional maxCells?: number;

Opt-in ceiling on cols * rows (default DEFAULT_MAX_CELLS = 4,000,000). Raise it only after measuring: every computeFlowField call costs about 13 bytes per cell and a full Dijkstra sweep over the grid, so a 10,000x10,000 grid is ~1.3 GB and minutes of blocked worker per query. Prefer a coarser cellSize over a bigger grid.

origin?

optional origin?: [number, number];

World XZ of the (0,0) cell's corner.

rows

rows: number;

Variables

DEFAULT_MAX_CELLS

const DEFAULT_MAX_CELLS: 4000000 = 4e6;

Default ceiling on cols * rows (a 2000x2000 grid). Sized off the per-query cost, not off what fits in memory: one computeFlowField allocates three Float32Arrays over every cell (plus heap entries) — about 13 bytes per cell — and runs a full Dijkstra sweep, so 4M cells is roughly 52 MB and a couple of seconds per query on a worker thread.

Functions

computeFlowField()

function computeFlowField(grid, goal): FlowField;

Compute a flow field over the grid toward a goal world position (Dijkstra integration).

Cost scales with the whole grid, not with the distance walked: three Float32Arrays over every cell plus heap entries — about 13 bytes per cell — and one Dijkstra sweep of every passable cell. Budget roughly 12 MB and ~1 s per query per million cells, and reuse one field for every agent heading to the same goal (that is the point of a flow field).

Parameters

grid

Grid

goal

[number, number]

Returns

FlowField