Waypoint graphs

A grid answers “which cells may I stand on”. That is the whole question in a top-down world and almost none of it in a sidescroller, where getting from one platform to the next is a jump with an impulse, a fall off a ledge, or a ladder — none of which is a property of a cell.

WaypointGraph models that directly: nodes you place, edges you type, and a path that tells you which kind of move each step was.

Nodes and typed edges

interface Move {
  readonly impulse: number;
}

const graph = new WaypointGraph<Move>();

const ledge = graph.addNode(120, 400);
const gap = graph.addNode(240, 400);
const platform = graph.addNode(420, 260);

graph.connect(ledge, gap); // cost defaults to the straight-line distance
graph.addEdge(gap, platform, { kind: 'jump', cost: 90, data: { impulse: 520 } });
graph.addEdge(platform, gap, { kind: 'fall', cost: 30 });

Edges are directed: falling off a platform is not the same move as jumping onto it, and connect is the shorthand for the cases where it is. An edge’s cost defaults to the straight-line distance between its nodes, which is the right default for a walk and the wrong one for a jump — price those yourself.

kind is a free-form string and data is whatever your movement controller needs. Both come back on the path:

const route = new Pathfinder().findPath(graph, ledge, platform);

for (let index = 0; index < route.edges.length; index++) {
  const step = route.edges[index]!;
  const arrival = route.points[index + 1]!;

  if (step.kind === 'jump' && step.data !== null) controller.jump(step.data.impulse);
  else controller.walkTo(arrival.x, arrival.y);
}

WaypointGraph<Move> carries the payload type through to result.edges[i].data, so the controller reads a typed value rather than casting one.

Graphs without geometry

Positions are optional. Leave them out and the heuristic drops to zero, which turns the same A* into plain Dijkstra over an abstract graph — a dialogue tree, a quest dependency, a routing problem in an application that never draws a tile:

// No positions: the heuristic is zero and the same search is plain Dijkstra
// over an abstract graph.
const routing = new WaypointGraph();
const cache = routing.addNode();
const origin = routing.addNode();

routing.connect(origin, cache, { cost: 12 });

A single positionless node is enough to switch the whole graph into that mode, because a geometric estimate stops being meaningful as soon as one node has no place in the world.

Pricing an edge below its length

An edge cheaper than the straight line between its ends — a zipline, a teleporter — would make a distance heuristic overestimate, and an overestimating heuristic costs the search its optimality. The graph handles this by scaling its heuristic down to the cheapest ratio any edge has, rather than by forbidding the edge. You pay a slightly weaker heuristic on that graph, and you keep optimal paths.

Your own space

Both built-in spaces implement one interface, NavigationSpace, and so can your own — a room graph, a hex grid, a navmesh. Everything in the package works against it unchanged.

/** A room graph: one node per room, cost in seconds of travel. */
class RoomSpace implements NavigationSpace {
  public readonly maxDegree = 6;
  public readonly revision = 0;

  public get nodeCapacity(): number {
    return rooms.length;
  }

  // The buffers belong to the pathfinder and are reused, so a custom space is
  // allocation-free on the same terms as the built-in ones.
  public neighbors(node: number, _agentSize: number, outNodes: Int32Array, outCosts: Float64Array): number {
    const { exits } = rooms[node]!;

    for (let index = 0; index < exits.length; index++) {
      outNodes[index] = exits[index]!;
      outCosts[index] = rooms[exits[index]!]!.travelTime;
    }

    return exits.length;
  }

  // Must never overestimate. Returning 0 is always safe and turns the search
  // into Dijkstra.
  public heuristic(): number {
    return 0;
  }

  public nodeToPoint(node: number, out: Vector): void {
    out.set(rooms[node]!.x, rooms[node]!.y);
  }

  public pointToNode(): number {
    return -1;
  }
}

Two contracts matter:

• neighbors writes into the buffers it is handed rather than returning an array. They belong to the pathfinder and are reused across nodes and searches, so do not retain them — and in exchange your space is allocation-free on the same terms as the built-in ones.
• heuristic must never overestimate the remaining cost. Returning 0 is always safe and turns the search into Dijkstra; anything else has to be a genuine lower bound, or paths stop being optimal in ways that are very hard to notice.

nodeToPoint, pointToNode, nearestNode, describeEdge, smoothPath and pruning are the optional extras: implement the ones your world can answer, and the queries that need the rest degrade rather than break.