State machines

Pausestartleurgency

0.45

Drag urgency through 4.2 to 5.2 m/s to see horses keep their gait, or startle all states except bolting. Dots show forty horses by pace and state, arrows mark transitions, and urgency below 0.3 lets them stop to graze.

A horse may walk, gallop, graze or bolt. Tracking this by hand requires a state field, a start time and transition checks each step. Weighted choices need cumulative probabilities, and gait changes need separate speed thresholds to prevent flicker. A state machine defines the states and their transitions. Run it per GPU row with machines.create or on the CPU with machines.run.

import { machines } from '@typegpu/kit';

const faster = (speed: number) => (i: number) => {
  'use gpu';
  return paceOf(i) > speed;
};
const slower = (speed: number) => (i: number) => {
  'use gpu';
  return paceOf(i) < speed;
};
const startled = { to: 'bolting', on: 'startle' } as const;

export const Gait = machines.define('Gait', {
  events: ['startle'],
  states: {
    walking: {
      next: [
        startled,
        { to: 'galloping', when: faster(5.2) },
        { to: 'grazing', when: calm, rate: 0.03 },
      ],
    },
    galloping: { next: [startled, { to: 'walking', when: slower(4.2) }] },
    grazing: { next: [startled, { to: 'walking', after: 4, rate: 1 / 3 }] },
    bolting: { next: [{ to: 'galloping', after: 2 }] },
  },
});

const gaits = machines.create(root, Gait, { capacity: 8192, step: sim.step }).pipe(herd.inject());

• A transition requires all its conditions to hold. on checks an event, after checks time in the state, and chance or rate checks a random roll. when, a shader function of the row, runs last. The first matching transition runs, at most once per step.
• Machines start in the first state. A state is a number, a literal in WGSL: Gait.galloping is 1.
• galloping leaves below 4.2 m/s and walking above 5.2, so a horse between them keeps its gait instead of flickering.
• Chance transitions take consecutive shares of one roll per step. Values of 0.05, 0.15 and 0.3 take 5, 15 and 30 % of the rolls. Later transitions get the remaining rolls. If none match, the state rolls again next step.
• A rate matches once per 1 / rate seconds on average, independent of step length. A calm walking horse starts grazing every 33 s on average. A grazing horse waits at least 4 s, then resumes walking after another 3 s on average.
• A transition declared outside the definition, like startled, needs as const so its target stays a name.
• The definition needs no root, so it lives at module scope beside the shaders that read it.
• TypeScript rejects a target or an event the definition doesn’t declare, and a state named like a number or one of the definition’s members, such as state or start. define throws for those too, and for a negative delay, chances past 1, or a chance and a rate on one transition.

Every step

In pipelines piped with gaits.inject(), shaders read a row’s state with Gait.state(i) and its seconds in it with Gait.since(i), and compute shaders send an event with Gait.send.startle(i).

const move = tgpu.computeFn({ workgroupSize: [64], in: { gid: d.builtin.globalInvocationId } })(({
  gid,
}) => {
  'use gpu';
  const i = gid.x;
  if (i >= COUNT) return;

  let wanted = cruise.$;
  if (Gait.state(i) === Gait.grazing) wanted = 0;
  if (Gait.state(i) === Gait.bolting) wanted = 15.5;
  // ... ease the horse's pace towards wanted, and move it
  if (std.distance(placeOf(i), thunder.$) < 30) Gait.send.startle(i);
});
const movement = root
  .pipe(herd.inject())
  .pipe(gaits.inject())
  .createComputePipeline({ compute: move });

frames.create(root, (frame) => {
  const pass = frame.encoder.beginComputePass();
  for (let s = sim.advance(frame.dt); s > 0; s--) {
    pass.setPipeline(movement);
    pass.dispatchWorkgroups(COUNT / 64);
    gaits.step(pass);
  }
  pass.end();
});

step(pass) updates every live row once. A newly started row runs only its state’s enter. Other rows advance their time by one step and check transitions. A transition runs the old state’s exit, changes the state and runs its enter. Both hooks are shader functions of the row. Put ongoing state work in your own kernels, as move does by branching on Gait.state(i).

The skeletons run 300 machines this way. Each enter rolls the next action’s length or destination, writes its motion to the skeleton’s row and starts its clip with the poses verbs. An attacker’s enter walks a neighbour grid to turn on the nearest skeleton.

• Gait.state(i) reads the old state in exit and the new one in enter. A transition to the state it leaves runs both and starts since from 0.
• In a guard, Gait.since(i) reads time before this step. after compares against time including this step.
• An event lasts until the row’s next step, which handles or drops it. Events sent after a frame’s last step wait for the next frame. A hook’s event to its own row reaches the next step. An event to another row may reach this step or the next.
• A guard or hook that reads another row’s state reads it before or after that row’s step.
• after rounds delays up to whole steps. A 4 s delay at 1/60 s takes 240 steps. Use after: (i) => … for a per-row delay in seconds, evaluated every step.
• A state with chances or rates rolls once a step from randf, seeded by row and step. Pass roll(i, tick) to draw it another way, such as from a blue-noise texture.
• Gait.roll(i) draws a number in [0, 1) from roll in guards, hooks and after functions. An after function runs every step, so a delay rolled there changes each step. For a fixed random delay, roll in enter, store the result in a field and read it from after.
• pipe(fill) fills resources read by guards, hooks, alive and roll, such as the herd’s buffers. These functions share the step’s pipeline. alive and roll can use its fills or carry their own.
• alive skips the slots without a row. A table gives it with its capacity and span, so a step runs no thread above the span: machines.create(root, Gait, { ...horses.live(), step: sim.step }).
• rows is the buffer of each row’s state and steps in it, for a readback or a test.

Work in one state

move runs for every horse and branches on its state. A group of 32 lanes executes a state’s branch whenever any of its rows uses that state. Scattered bolting horses therefore make nearly every group execute the bolt branch. Pass lists to collect rows by state each step. each runs work only on one listed state’s rows.

const gaits = machines.create(root, Gait, {
  capacity: COUNT,
  step: sim.step,
  lists: [Gait.bolting],
});
const bolt = gaits
  .each(Gait.bolting, (i) => {
    'use gpu';
    flee(i); // ... away from the thunder
  })
  .pipe(herd.inject());

frames.create(root, (frame) => {
  const pass = frame.encoder.beginComputePass();
  for (let s = sim.advance(frame.dt); s > 0; s--) {
    gaits.step(pass);
    bolt.dispatch(pass);
  }
  pass.end();
});

• Each step fills lists with the live rows in the states they end the step in, in no order. dispatch uses the lists from the most recent step.
• The work pipeline inherits the machine’s fills, including those for Gait.state(i) and Gait.since(i). Pipe in fills for any other resources it reads.
• Each list uses one word per row. At most 256 states can have lists.
• gaits.listed holds the lists as live lists, group k for lists[k]. Read a row with gaits.listed.slot(k, i) in a kernel of your own and run it with listed.dispatch.

Starting rows

Rows sit in the first state without running its enter. start(slot, state?) puts a row in a state as you add it, and its enter runs at the next step. The stampede starts its whole herd galloping this way.

• A start skips the old state’s exit and drops the row’s waiting events, from the CPU or from kernels.
• send.startle(slot) sends an event from the CPU.
• The next step uploads starts and events with queue.writeBuffer. Consecutive started slots use one write. Call flush() before the frame’s steps when a frame may draw without stepping.
• With kernelStarts: true, compute shaders can start rows with Gait.start(i, Gait.bolting). The row applies the start at its next step. A kernel start takes precedence over a CPU start in the same step.

On the CPU

A definition with plain functions for guards and hooks runs on the CPU with machines.run. The horses in the figure above run this way, and a step allocates nothing.

const lasted = (i: number) => actors[i]!.lasts; // seconds, set as each state starts
const stood = [
  { to: 'walking', after: lasted, chance: 0.7 },
  { to: 'idling', after: lasted },
] as const;

const Doing = machines.define('Doing', {
  states: {
    waking: { next: stood },
    idling: { enter: idle, next: stood },
    walking: {
      enter: wander,
      next: [
        { to: 'taunting', after: lasted, chance: 0.15 },
        { to: 'attacking', after: lasted, chance: 0.3 },
        { to: 'idling', after: lasted },
      ],
    },
    taunting: { enter: (i) => play(i, 'taunt'), next: stood },
    attacking: { enter: (i) => play(i, 'attack'), next: stood },
  },
});

const doing = machines.run(Doing, { count: 300 });
frames.create(root, (frame) => doing.step(frame.dt));

• state(i) and since(i) read machine i, send.<event>(i) sends it an event, and start(i, state?) puts it in a state at once. Its enter runs at the next step, or at the one after when a hook calls start.
• An event sent from a hook reaches the step after.
• A delay matches at the first step that reaches it. The next state counts time from that step, so each timed transition can add up to one step of delay.
• subscribe(listener) calls back after a step that changed a state and after a start, for a game’s flow in React: useSyncExternalStore(flow.subscribe, () => flow.state()).
• random draws the rolls, Math.random by default. Pass a seeded one for tests that repeat.

On the GPU and on the CPU

	machines.create	machines.run
Machines	a row a slot, capacity of them; alive skips some	count, which all step
Guards, hooks, after functions	'use gpu' functions of the slot	plain functions of the index
Time in a state	whole steps of the step given to create	the seconds each step(dt) adds
The first state	rows sit in it without its enter	its enter runs at the first step
Rolls	randf or your roll(i, tick), from a tick random() starts; Gait.roll(i) in guards and hooks	random()
State and time	Gait.state(i), Gait.since(i) in shaders	state(i), since(i)
Events	send on the CPU, Gait.send in compute shaders	send
Starts	start(slot) on the CPU, read once the next step or flush() uploads it; Gait.start(i, state) in compute shaders, read from the next step	start(i), read at once, telling subscribe

Limits

• A definition is flat, with no nested states, concurrent regions or history states.
• One transition a step, so a chain of three takes three steps.
• At most 31 events a definition; a row holds them as bits until its next step.
• On the GPU, after and since count steps of the step the rows were created with, compiled into the transitions. Steps recorded at another length read wrong.
• On the GPU, a slot keeps its row’s last state when the row dies. Start the slot again for the next row in it, from the CPU or a kernel.
• On the GPU, rows started from the CPU begin their rolls at a tick random draws, Math.random by default, so two runs roll alike only with a seeded one.
• A pipeline reads one machines.create instance per definition. If two are piped in, the last fills Gait’s functions.
• The step pipeline uses 2 to 7 storage buffers and at most one uniform. These hold the rows and the CPU’s starts and events, and as needed the kernels’ events and starts, the roll ticks, and the lists and their counts. Of the 8 storage bindings WebGPU guarantees per stage, this leaves 1 to 6 for guards and hooks.