@shapeshift-labs/frontier-pathfinding

v0.1.0

Published

a month ago

Patch-native grid and graph pathfinding primitives for Frontier game, scene, and automation stacks.

0High
0Medium
0Low

shapeshift-labs

frontier pathfinding astar grid game navigation

@shapeshift-labs/frontier-pathfinding

Patch-native pathfinding primitives for Frontier game, scene, automation, and AI stacks. The package stores navigation state as JSON, accepts Frontier patch tuples for mutation, and keeps hot grid search state in typed-array caches.

API Shape

import {
  createGridPathfinder,
  gridFromStrings,
  schedulePathfind,
  setCellPatch
} from '@shapeshift-labs/frontier-pathfinding';

const nav = createGridPathfinder(gridFromStrings([
  '..........',
  '..###.....',
  '..#.......',
  '..#..###..',
  '..........'
]));

const path = nav.findPath(
  { x: 0, y: 0 },
  { x: 9, y: 4 },
  { diagonal: 'ifNoObstacles', smooth: true }
);

nav.commit(setCellPatch(nav.width, 4, 2, 0), {
  origin: { actionId: 'terrain.block', causeId: 'door.closed' }
});

const flow = nav.flowField({ x: 9, y: 4 });
const components = nav.connectedComponents();

schedulePathfind(scheduler, nav, {
  start: { x: 0, y: 0 },
  goal: { x: 9, y: 4 },
  diagonal: 'never'
});

Design Notes

frontier-pathfinding deliberately does not own a renderer, game loop, scene graph, or scheduler. DOM, Canvas, WebGL, WebGPU, Playwright agents, and game engines can all consume the same serialized grid snapshot and patch stream.

The internal model follows the rest of Frontier:

JSON snapshot is the durable navigation state.
Frontier patch tuples are the mutation format.
Cell-cost changes update typed caches by exact dirty cell index.
A* and Dijkstra-style search share a reusable typed-array search context.
Diagonal movement follows PathFinding.js-style policies: never, always, ifNoObstacles, and onlyWhenNoObstacles.
Flow fields provide one-to-many navigation for groups of agents.
Connected components expose cheap reachability regions for AI/game code.
Line-of-sight smoothing gives a Theta*-style post-process without making any-angle search the only mode.
Scheduler integration is structural, so frontier-scheduler can queue path work without becoming a dependency.
Snapshots, flow fields, components, paths, patches, and commit origins are JSON-shaped for replay, logging, persistence, and AI inspection.

Related Packages

The published Frontier package family is generated from one shared package catalog so READMEs stay in sync across packages:

@shapeshift-labs/frontier: Core JSON diff/apply, compact patch tuples, JSON Pointer, equality, clone, validation, Unicode helpers, and tiny dependency-free runtime budget/scheduler primitives.
@shapeshift-labs/frontier-query: Shared query-key, selector path, condition, entity identity, and table-shape primitives.
@shapeshift-labs/frontier-codec: Patch serialization, binary frames, canonical JSON, and patch-history codecs.
@shapeshift-labs/frontier-engine: Stateful planned diff engine, adaptive profiles, schema plans, and engine-level history helpers.
@shapeshift-labs/frontier-state: Patch-routed app-state subscriptions, owned commits, maintained views, and path mapping.
@shapeshift-labs/frontier-state-cache: Normalized query-result cache with entity/query watchers, persistence, change logs, optimistic layers, scheduled persistence, and mutation bridge.
@shapeshift-labs/frontier-state-cache-idb: IndexedDB persistence adapter for Frontier state-cache snapshots and durable change logs.
@shapeshift-labs/frontier-state-cache-file: Structured file persistence adapter for Frontier state-cache snapshots and change logs.
@shapeshift-labs/frontier-state-cache-sql: SQL persistence adapter for Frontier state-cache snapshots and change logs.
@shapeshift-labs/frontier-schema: JSON Schema validation, Frontier profile generation, CloudEvent envelopes, and query/table schema helpers.
@shapeshift-labs/frontier-event-log: Bounded event logs, replay cursors, consumer acknowledgements, keyed compaction, checkpoints, and Frontier patch event records.
@shapeshift-labs/frontier-scheduler: Deterministic work scheduling, lanes, cancellation, backpressure, frame policies, replay snapshots, and work graphs.
@shapeshift-labs/frontier-logging: Opt-in structured logging, browser telemetry, scheduled sinks, file sinks, exporters, benchmark traces, and Frontier patch/update summaries.
@shapeshift-labs/frontier-mutation: Explicit mutation and selector plans compiled to Frontier patches or CRDT operations.
@shapeshift-labs/frontier-virtual: DOM-neutral virtualization, layout providers, range materialization, grids, spatial/frustum indexes, patch invalidation, camera anchors, and serializable layout state.
@shapeshift-labs/frontier-scene: Patch-native 2D/3D scene graph, transform propagation, bounds queries, virtual/culling adapters, spatial invalidation, and camera/frustum materialization.
@shapeshift-labs/frontier-dom: Patch-native DOM and host renderer bindings, manifest hydration, JSX runtime/compiler helpers, SSR, devtools, and logging bridges.
@shapeshift-labs/frontier-playwright: Playwright/headless automation probes for Frontier state, DOM, devtools, marks, and timeline queries.
@shapeshift-labs/frontier-crdt: Native CRDT documents, update tooling, awareness, branches, conflict introspection, version frames, and undo.
@shapeshift-labs/frontier-crdt-sync: CRDT sync endpoints, repo/storage/provider contracts, scheduled sync work, document URLs, local networks, model checking, forensics, and text binding contracts.
@shapeshift-labs/frontier-crdt-websocket: WebSocket client/server transports for Frontier CRDT sync providers.
@shapeshift-labs/frontier-react: React external-store hooks and adapters for Frontier state, cache, and CRDT surfaces.
@shapeshift-labs/frontier-richtext: Rich text Delta normalization/application, marks, embeds, ranges, and cursor/selection transforms for local editor integrations.
@shapeshift-labs/frontier-realtime: Shared realtime command, tick, snapshot, prediction, reconciliation, interpolation, rollback, message, and delta primitives.
@shapeshift-labs/frontier-realtime-server: Authoritative realtime room, tick, command validation, rate-limit, session, and snapshot-history runtime.
@shapeshift-labs/frontier-realtime-websocket: WebSocket client, wire, and Node room-server transport for Frontier realtime.
@shapeshift-labs/frontier-game: Game-facing entity, component, player, room, ownership, spatial interest, rollback, physics, and replication helpers above realtime.

Package source repositories:

Install

npm install @shapeshift-labs/frontier-pathfinding

Benchmarks

These are Frontier-only package measurements, not competitor comparisons.

Run package-local measurements:

npm run bench

The benchmark covers A*, smoothed A*, zero-heuristic Dijkstra-style search, flow-field generation, and patch-routed cell updates over a synthetic weighted grid.

Latest local package benchmark on Node v26.1.0, darwin arm64, 96x96 grid and 40 rounds:

| Fixture | Median | p95 | | --- | ---: | ---: | | astar-grid-96x96 | 284.42 us | 518.58 us | | astar-smooth-96x96 | 245.83 us | 947.08 us | | dijkstra-zero-heuristic-96x96 | 1.14 ms | 2.49 ms | | flow-field-96x96 | 1.18 ms | 1.68 ms | | patch-cell-update-96x96 | 0.79 us | 9.54 us |

Published

Vulnerabilities

Links

Maintainers

Keywords

Readme

@shapeshift-labs/frontier-pathfinding

API Shape

Design Notes

Related Packages

Install

Benchmarks