Back to Drift City
SOURCE / PINNED RELEASE

Made of little things.

Drift City

Release
098731aa0f0f…
Author-recorded commit
2822ea0a4f5b…
License
LICENSE
Author’s source reference
nostr://npub12lm3rxsva8kfempyjkxupt09e02n3fezurkyadyqfejdc5e0r2kscqty6r/wss%3A%2F%2Fgit.napplet.soy%2F/n-a4c0039c855

Archive hash verified: b3323e408235502b…. The source-to-build association is the author’s claim; it has not been independently rebuilt.

src/game/race.ts
import type { RoadGraph } from './traffic.js';

/**
 * Race routes: a line along the roads from a start to a finish (or round a circuit),
 * passing through the waypoints the player set on the map.
 *
 * Each waypoint is snapped onto the nearest road; between one and the next the route
 * takes the shortest way along the road network, so it follows the streets however the
 * points were placed. The result is one smooth polyline, resampled every few metres, with
 * how wide the road is at each point (for the rivals to use its width).
 */

/** A waypoint on a road: which edge, how far along it from its first end, and where that is. */
export interface RoutePoint {
  x: number;
  z: number;
  edge: number;
  t: number;
}

/** A place on the route, and the way it runs there. */
export interface RouteSample {
  x: number;
  z: number;
  tx: number;
  tz: number;
  /** Half the road's width there. */
  hw: number;
  /** The road's height there (up on the highway, or 0 on the ground). */
  y?: number;
  /** A one-way road there (the whole width is the race's, no oncoming half). */
  oneway?: boolean;
}

const SPACING = 4;
/** Where the start line is, along the route: the grid lines up behind it. */
export const START_S = 34;

/** Snap a point on the map to the nearest place on any road. */
export function snapToRoad(graph: RoadGraph, x: number, z: number): RoutePoint {
  const { cursor } = graph.nearest(x, z, 0);
  const e = graph.edges[cursor.edge]!;
  const t = cursor.dir > 0 ? cursor.s : e.len - cursor.s;
  const p = pointOnEdge(graph, cursor.edge, t);
  return { x: p.x, z: p.z, edge: cursor.edge, t };
}

function pointOnEdge(graph: RoadGraph, edge: number, t: number): { x: number; y: number; z: number } {
  const e = graph.edges[edge]!;
  const d = Math.max(0, Math.min(e.len, t));
  let i = 1;
  while (i < e.cum.length - 1 && e.cum[i]! < d) i++;
  const a = e.pts[i - 1]!;
  const b = e.pts[i]!;
  const f = (d - e.cum[i - 1]!) / (e.cum[i]! - e.cum[i - 1]! || 1);
  return { x: a.x + (b.x - a.x) * f, y: a.y + (b.y - a.y) * f, z: a.z + (b.z - a.z) * f };
}

/** The points of an edge from distance t0 to t1 along it (either way round), ends included. */
function slice(graph: RoadGraph, edge: number, t0: number, t1: number, out: Raw[]): void {
  const e = graph.edges[edge]!;
  const push = (p: { x: number; y: number; z: number }) => out.push({ x: p.x, y: p.y, z: p.z, hw: halfWidth(e), oneway: !!e.oneway });
  push(pointOnEdge(graph, edge, t0));
  if (t1 >= t0) {
    for (let i = 0; i < e.pts.length; i++) if (e.cum[i]! > t0 && e.cum[i]! < t1) push(e.pts[i]!);
  } else {
    for (let i = e.pts.length - 1; i >= 0; i--) if (e.cum[i]! < t0 && e.cum[i]! > t1) push(e.pts[i]!);
  }
  push(pointOnEdge(graph, edge, t1));
}

/** A point of a route as it's first laid along the roads. */
type Raw = { x: number; y: number; z: number; hw: number; oneway: boolean };

/** May traffic (and a race) go along edge e from its end a (dir 1) or its end b (dir -1)? */
function allowed(graph: RoadGraph, edge: number, dir: 1 | -1): boolean {
  const w = graph.edges[edge]!.oneway;
  return !w || w === dir;
}

/** Half the width a racer has on an edge: a street or the highway, a one-way curve of it, a ramp, a country road or lane. */
function halfWidth(e: { city: boolean; kind: string; oneway: number }): number {
  return e.kind === 'ramp' ? 3.2 : e.oneway ? 4.6 : e.city ? 7.4 : 5;
}

/** Shortest distances (and the way back) from a place on the roads to every junction. */
function dijkstra(graph: RoadGraph, from: RoutePoint): { dist: Float64Array; prevNode: Int32Array; prevEdge: Int32Array } {
  const n = graph.nodes.length;
  const dist = new Float64Array(n).fill(Infinity);
  const prevNode = new Int32Array(n).fill(-1);
  const prevEdge = new Int32Array(n).fill(-1);
  const done = new Uint8Array(n);
  const e0 = graph.edges[from.edge]!;
  // Leaving the start edge by either end (-2 marks "straight from the start point").
  if (allowed(graph, from.edge, -1)) {
    dist[e0.a] = from.t;
    prevNode[e0.a] = -2;
    prevEdge[e0.a] = from.edge;
  }
  if (allowed(graph, from.edge, 1) && e0.len - from.t < dist[e0.b]!) {
    dist[e0.b] = e0.len - from.t;
    prevNode[e0.b] = -2;
    prevEdge[e0.b] = from.edge;
  }
  for (;;) {
    let u = -1;
    for (let i = 0; i < n; i++) if (!done[i] && dist[i]! < Infinity && (u < 0 || dist[i]! < dist[u]!)) u = i;
    if (u < 0) break;
    done[u] = 1;
    for (const ei of graph.nodes[u]!.edges) {
      const e = graph.edges[ei]!;
      if (!allowed(graph, ei, e.a === u ? 1 : -1)) continue;
      const v = e.a === u ? e.b : e.a;
      const d = dist[u]! + e.len;
      if (d < dist[v]!) {
        dist[v] = d;
        prevNode[v] = u;
        prevEdge[v] = ei;
      }
    }
  }
  return { dist, prevNode, prevEdge };
}

/** The way along the roads from one waypoint to the next, as points (the first included). */
function leg(graph: RoadGraph, p: RoutePoint, q: RoutePoint, out: Raw[]): number {
  const eq = graph.edges[q.edge]!;
  // Along the same stretch of road, straight there.
  let direct = Infinity;
  if (p.edge === q.edge && allowed(graph, p.edge, q.t >= p.t ? 1 : -1)) direct = Math.abs(q.t - p.t);
  const { dist, prevNode, prevEdge } = dijkstra(graph, p);
  const viaA = allowed(graph, q.edge, 1) ? dist[eq.a]! + q.t : Infinity;
  const viaB = allowed(graph, q.edge, -1) ? dist[eq.b]! + (eq.len - q.t) : Infinity;
  const best = Math.min(direct, viaA, viaB);
  if (!isFinite(best)) return Infinity;
  if (best === direct) {
    slice(graph, p.edge, p.t, q.t, out);
    return best;
  }
  // Walk back from the junction it reaches q's road by, then lay the way out forwards.
  const end = viaA <= viaB ? eq.a : eq.b;
  const nodes: number[] = [];
  const edges: number[] = [];
  for (let u = end; u >= 0; u = prevNode[u]!) {
    nodes.unshift(u);
    edges.unshift(prevEdge[u]!);
    if (prevNode[u] === -2) break;
  }
  // The first edge is p's own, from p out to the first junction.
  const e0 = graph.edges[p.edge]!;
  slice(graph, p.edge, p.t, nodes[0] === e0.a ? 0 : e0.len, out);
  for (let i = 1; i < nodes.length; i++) {
    const e = graph.edges[edges[i]!]!;
    const fromA = e.a === nodes[i - 1];
    slice(graph, edges[i]!, fromA ? 0 : e.len, fromA ? e.len : 0, out);
  }
  slice(graph, q.edge, end === eq.a ? 0 : eq.len, q.t, out);
  return best;
}

/** A sensible first route: from near where the car starts to somewhere about 1.5 km away by road. */
export function defaultRoute(graph: RoadGraph, x: number, z: number): RoutePoint[] {
  const start = snapToRoad(graph, x, z);
  const { dist } = dijkstra(graph, start);
  let best = -1;
  for (let i = 0; i < dist.length; i++) if (isFinite(dist[i]!) && (best < 0 || Math.abs(dist[i]! - 1500) < Math.abs(dist[best]! - 1500))) best = i;
  const n = graph.nodes[Math.max(0, best)]!;
  return [start, snapToRoad(graph, n.x, n.z)];
}

export class RaceRoute {
  /** Evenly spaced points along the route, and how far along each one is. */
  readonly pts: RouteSample[] = [];
  readonly len: number;
  /** For each point, which leg (waypoint to waypoint) it's on: for the editor to insert waypoints. */
  readonly legOf: number[] = [];

  private constructor(
    raw: (Raw & { leg: number })[],
    readonly loop: boolean,
  ) {
    // Resample to even spacing, dropping repeats.
    const cum = [0];
    for (let i = 1; i < raw.length; i++) cum.push(cum[i - 1]! + Math.hypot(raw[i]!.x - raw[i - 1]!.x, raw[i]!.z - raw[i - 1]!.z));
    const total = cum[cum.length - 1]!;
    const n = Math.max(2, Math.round(total / SPACING));
    let j = 1;
    for (let k = 0; k <= n; k++) {
      const d = (k / n) * total;
      while (j < raw.length - 1 && cum[j]! < d) j++;
      const a = raw[j - 1]!;
      const b = raw[j]!;
      const f = (d - cum[j - 1]!) / (cum[j]! - cum[j - 1]! || 1);
      this.pts.push({ x: a.x + (b.x - a.x) * f, y: a.y + (b.y - a.y) * f, z: a.z + (b.z - a.z) * f, tx: 0, tz: 1, hw: Math.max(a.hw, b.hw), oneway: a.oneway && b.oneway });
      this.legOf.push(a.leg);
    }
    if (loop) {
      this.pts.pop();
      this.legOf.pop();
    }
    this.len = loop ? total : total;
    // Directions: smoothed over a few points so corners turn gradually.
    const m = this.pts.length;
    for (let i = 0; i < m; i++) {
      const pi = loop ? (i - 3 + m) % m : Math.max(0, i - 3);
      const ni = loop ? (i + 3) % m : Math.min(m - 1, i + 3);
      const dx = this.pts[ni]!.x - this.pts[pi]!.x;
      const dz = this.pts[ni]!.z - this.pts[pi]!.z;
      const l = Math.hypot(dx, dz) || 1;
      this.pts[i]!.tx = dx / l;
      this.pts[i]!.tz = dz / l;
    }
  }

  /** The route through these waypoints (round to the first again if loop), or null if they can't be joined. */
  static build(graph: RoadGraph, way: RoutePoint[], loop: boolean): RaceRoute | null {
    if (way.length < 2) return null;
    const raw: (Raw & { leg: number })[] = [];
    const stops = loop ? [...way, way[0]!] : way;
    for (let i = 0; i + 1 < stops.length; i++) {
      const part: Raw[] = [];
      if (!isFinite(leg(graph, stops[i]!, stops[i + 1]!, part))) return null;
      for (const p of part) {
        const last = raw[raw.length - 1];
        if (last && Math.hypot(last.x - p.x, last.z - p.z) < 0.3) continue;
        raw.push({ ...p, leg: i });
      }
    }
    if (raw.length < 2) return null;
    return new RaceRoute(raw, loop);
  }

  /** The route at distance s along it (wrapping round a circuit; clamped otherwise). */
  at(s: number, out: RouteSample): RouteSample {
    const m = this.pts.length;
    const step = this.loop ? this.len / m : this.len / (m - 1);
    let u = s / step;
    if (this.loop) u = ((u % m) + m) % m;
    else u = Math.max(0, Math.min(m - 1, u));
    const i = Math.floor(u);
    const f = u - i;
    const a = this.pts[i]!;
    const b = this.pts[this.loop ? (i + 1) % m : Math.min(m - 1, i + 1)]!;
    out.x = a.x + (b.x - a.x) * f;
    out.z = a.z + (b.z - a.z) * f;
    out.y = (a.y ?? 0) + ((b.y ?? 0) - (a.y ?? 0)) * f;
    const tx = a.tx + (b.tx - a.tx) * f;
    const tz = a.tz + (b.tz - a.tz) * f;
    const l = Math.hypot(tx, tz) || 1;
    out.tx = tx / l;
    out.tz = tz / l;
    out.hw = Math.min(a.hw, b.hw);
    out.oneway = !!(a.oneway && b.oneway);
    return out;
  }

  /**
   * Where (x, z) is along the route, searching from s - back to s + ahead (so a racer's
   * progress can't jump to a far part of the route that happens to pass close by), and how
   * far from the route's line it is. Where the route doubles back on itself (a U-turn at a
   * waypoint), both ways lie side by side: stick says how strongly to favour the place
   * nearest s, so progress carries on round the turn rather than jumping across.
   */
  project(x: number, z: number, s: number, back: number, ahead: number, stick = 0): { s: number; d: number } {
    let best = { s, d: Infinity };
    let bestScore = Infinity;
    const step = 2;
    let prev = this.at(s - back, _a);
    let px = prev.x;
    let pz = prev.z;
    for (let u = s - back + step; u <= s + ahead + 1e-6; u += step) {
      if (!this.loop && (u < 0 || u - step > this.len)) {
        prev = this.at(u, _a);
        px = prev.x;
        pz = prev.z;
        continue;
      }
      const q = this.at(u, _b);
      const vx = q.x - px;
      const vz = q.z - pz;
      const l2 = vx * vx + vz * vz || 1;
      const t = Math.max(0, Math.min(1, ((x - px) * vx + (z - pz) * vz) / l2));
      const d = Math.hypot(x - (px + vx * t), z - (pz + vz * t));
      const at = u - step + step * t;
      const score = d + stick * Math.abs(at - s);
      if (score < bestScore) {
        bestScore = score;
        best = { s: at, d };
      }
      px = q.x;
      pz = q.z;
    }
    return best;
  }
}

const _a: RouteSample = { x: 0, z: 0, tx: 0, tz: 1, hw: 4 };
const _b: RouteSample = { x: 0, z: 0, tx: 0, tz: 1, hw: 4 };

export type RaceEvent =
  | { type: 'count'; n: number }
  | { type: 'go' }
  | { type: 'checkpoint'; n: number; of: number; time: number }
  | { type: 'lap'; lap: number; of: number; time: number }
  | { type: 'finish'; position: number; of: number; time: number };

/** One line of the standings. */
export interface Standing {
  name: string;
  player: boolean;
  /** Seconds to the line, once over it. */
  time: number | null;
  out: boolean;
  /** Metres still to go (while racing). */
  toGo: number;
}

/** The race's state for the HUD. */
export interface RaceInfo {
  phase: 'countdown' | 'racing' | 'finished';
  countdown: number;
  position: number;
  of: number;
  lap: number;
  laps: number;
  time: number;
  /** Off the route: drive back to it (R puts you back). */
  offRoute: boolean;
  /** Metres left to the finish. */
  toGo: number;
}

const COUNTDOWN = 3.6;

/**
 * A race under way: the countdown, the clock, the player's progress along the route
 * (found near where they were, so it can't skip ahead by leaving the road), checkpoints,
 * laps, everyone's position, and the finish.
 */
export class RaceSession {
  phase: RaceInfo['phase'] = 'countdown';
  /** Seconds until the start (counting down), then the race clock. */
  clock = COUNTDOWN;
  time = 0;
  /** How far the player has come from the start line (negative on the grid). */
  prog: number;
  /** How far it is from the start line to the finish, laps and all. */
  readonly total: number;
  /** Progress at each checkpoint gate, and which is next. */
  readonly checkpoints: number[] = [];
  private next = 0;
  private lapsDone = 0;
  private lastCount = 4;
  offRoute = false;
  finishTime = 0;
  finishPosition = 0;
  standings: Standing[] = [];

  constructor(
    readonly route: RaceRoute,
    readonly laps: number,
    startProg: number,
  ) {
    this.prog = startProg;
    const lap = route.loop ? route.len : route.len - 25 - START_S;
    this.total = route.loop ? lap * laps : lap;
    // A checkpoint about every 350 m of each lap.
    const per = Math.max(1, Math.round(lap / 350));
    for (let k = 0; k < laps; k++) for (let c = 1; c < per; c++) this.checkpoints.push(k * lap + (lap * c) / per);
    if (route.loop) for (let k = 1; k < laps; k++) this.checkpoints.push(k * lap);
    this.checkpoints.sort((a, b) => a - b);
  }

  /** Where the finish line is, along the route. */
  get finishS(): number {
    return this.route.loop ? START_S : this.route.len - 25;
  }

  /** The lap length (or the whole route, point to point). */
  get lapLen(): number {
    return this.route.loop ? this.route.len : this.total;
  }

  /**
   * One step. rivals gives each rival's progress (from the start line) and state; it
   * returns what happened, and finished lists rivals who crossed the line this step.
   */
  update(dt: number, x: number, z: number, rivals: { name: string; prog: number; out: boolean; finished: number | null }[]): { events: RaceEvent[]; finished: string[] } {
    const events: RaceEvent[] = [];
    const finished: string[] = [];
    if (this.phase === 'countdown') {
      this.clock -= dt;
      const n = Math.ceil(this.clock);
      if (n < this.lastCount && n > 0) events.push({ type: 'count', n });
      this.lastCount = n;
      if (this.clock <= 0) {
        this.phase = 'racing';
        this.clock = 0;
        events.push({ type: 'go' });
      }
    } else this.time += dt;
    // The player's progress, searched for near where they were.
    if (this.phase !== 'finished') {
      const pr = this.route.project(x, z, START_S + this.prog, 25, 60, 0.1);
      const p = this.route.at(pr.s, _a);
      this.offRoute = pr.d > p.hw + 16;
      if (!this.offRoute && this.phase === 'racing') this.prog = Math.max(this.prog - 25, pr.s - START_S);
    }
    if (this.phase === 'racing') {
      while (this.next < this.checkpoints.length && this.prog >= this.checkpoints[this.next]!) {
        const at = this.checkpoints[this.next]!;
        this.next++;
        const lapAt = this.route.loop ? Math.round(at / this.lapLen) : 0;
        if (this.route.loop && Math.abs(at - lapAt * this.lapLen) < 1) {
          this.lapsDone = lapAt;
          events.push({ type: 'lap', lap: lapAt + 1, of: this.laps, time: this.time });
        } else events.push({ type: 'checkpoint', n: this.next, of: this.checkpoints.length, time: this.time });
      }
      for (const r of rivals) if (r.finished === null && !r.out && r.prog >= this.total) finished.push(r.name);
      if (this.prog >= this.total) {
        this.phase = 'finished';
        this.finishTime = this.time;
        this.rank(rivals, finished);
        this.finishPosition = this.standings.findIndex((s) => s.player) + 1;
        events.push({ type: 'finish', position: this.finishPosition, of: this.standings.length, time: this.time });
        return { events, finished };
      }
    }
    if (this.phase === 'finished')
      // The player's done; the rivals race on to the line, timed.
      for (const r of rivals) if (r.finished === null && !r.out && r.prog >= this.total) finished.push(r.name);
    this.rank(rivals, finished);
    return { events, finished };
  }

  /** Whether everyone's over the line (or out). */
  allIn(rivals: { finished: number | null; out?: boolean }[]): boolean {
    return this.phase === 'finished' && rivals.every((r) => r.finished !== null || r.out);
  }

  /** Everyone in order: over the line by time, then by how far along they are; wrecks last. */
  private rank(rivals: { name: string; prog: number; out: boolean; finished: number | null }[], justFinished: string[]): void {
    const all = [
      { name: 'You', player: true, prog: this.prog, out: false, time: this.phase === 'finished' ? this.finishTime : null },
      ...rivals.map((r) => ({ name: r.name, player: false, prog: r.prog, out: r.out, time: r.finished ?? (justFinished.includes(r.name) ? this.time : null) })),
    ];
    all.sort((a, b) => {
      if (a.out !== b.out) return a.out ? 1 : -1;
      if (a.time !== null || b.time !== null) {
        if (a.time === null) return 1;
        if (b.time === null) return -1;
        return a.time - b.time;
      }
      return b.prog - a.prog;
    });
    this.standings = all.map((a) => ({ name: a.name, player: a.player, time: a.time, out: a.out, toGo: Math.max(0, this.total - a.prog) }));
  }

  info(): RaceInfo {
    const position = this.standings.findIndex((s) => s.player) + 1 || this.standings.length;
    const lap = this.route.loop ? Math.min(this.laps, Math.floor(Math.max(0, this.prog) / this.lapLen) + 1) : 1;
    return {
      phase: this.phase,
      countdown: Math.ceil(this.clock),
      position,
      of: Math.max(1, this.standings.length),
      lap: this.phase === 'finished' ? this.laps : Math.max(lap, this.lapsDone + 1),
      laps: this.route.loop ? this.laps : 1,
      time: this.phase === 'finished' ? this.finishTime : this.time,
      offRoute: this.offRoute && this.phase === 'racing',
      toGo: Math.max(0, this.total - this.prog),
    };
  }
}

/** Race time as m:ss.cc. */
export function raceTime(t: number): string {
  const m = Math.floor(t / 60);
  const s = t - m * 60;
  return `${m}:${s.toFixed(2).padStart(5, '0')}`;
}

/** One stretch of a generated route: along an edge from distance t0 to t1 (t1 < t0 going backwards). */
interface Step {
  edge: number;
  t0: number;
  t1: number;
  /** The junction it comes into this edge from (-1 for the first). */
  from: number;
}

/**
 * A route about `length` metres long along the roads from `start`, using no road twice: a
 * finish flag that far along (point to point) or a loop back to the start (a circuit). The
 * search prefers carrying on more or less straight, varied by seed. Returns the waypoints
 * for the planner (as few as will pin the route to that way round), or null if no such
 * route was found.
 */
export function generateRoute(graph: RoadGraph, start: RoutePoint, length: number, loop: boolean, seed: number): RoutePoint[] | null {
  // As twisty as it can be while still the length asked for: if a route full of turns
  // runs out of roads first, a straighter one.
  let best: Step[] | null = null;
  let bestErr = Infinity;
  for (const twist of [1, 0.6, 0.25]) {
    const steps = loop ? searchLoop(graph, start, length, seed, twist) : searchLine(graph, start, length, seed, twist);
    if (!steps) continue;
    const got = steps.reduce((sum, st) => sum + Math.abs(st.t1 - st.t0), 0);
    const err = Math.abs(got - length) / length;
    if (err < bestErr) {
      best = steps;
      bestErr = err;
    }
    if (err < 0.08) break;
  }
  return best ? pin(graph, start, best, loop) : null;
}

function seeded(seed: number): () => number {
  let a = seed >>> 0 || 1;
  return () => {
    a = (a + 0x6d2b79f5) >>> 0;
    let t = a;
    t = Math.imul(t ^ (t >>> 15), t | 1);
    t ^= t + Math.imul(t ^ (t >>> 7), t | 61);
    return ((t ^ (t >>> 14)) >>> 0) / 4294967296;
  };
}

/** How far a route must run on after a turn before it favours turning again (m): corners with straights between, not a staircase. */
const STRAIGHT = 120;

/** The straight run after taking edge ei out of node: on from since if it carries straight on, from nothing if it turns. */
function runOn(graph: RoadGraph, ei: number, node: number, heading: { x: number; z: number }, since: number): number {
  const h = leave(graph, ei, node);
  const len = graph.edges[ei]!.len;
  return h.x * heading.x + h.z * heading.z > 0.75 ? since + len : len;
}

/** Heading leaving a junction along one of its roads (unit vector). */
function leave(graph: RoadGraph, edge: number, node: number): { x: number; z: number } {
  const e = graph.edges[edge]!;
  const p = pointOnEdge(graph, edge, e.a === node ? 0 : e.len);
  const q = pointOnEdge(graph, edge, e.a === node ? Math.min(8, e.len) : Math.max(0, e.len - 8));
  const l = Math.hypot(q.x - p.x, q.z - p.z) || 1;
  return { x: (q.x - p.x) / l, z: (q.z - p.z) / l };
}

/**
 * The ways on from a junction, best first: turning off left or right scores highest (races
 * are more fun with corners), carrying straight on less, doubling sharply back lowest, with
 * a random shake so different seeds give different routes.
 * near (optional) pulls towards a point (home, for a circuit).
 */
function options(graph: RoadGraph, node: number, inHeading: { x: number; z: number }, used: Set<number>, rand: () => number, twist: number, near?: { x: number; z: number; w: number }): number[] {
  const n = graph.nodes[node]!;
  const scored: [number, number][] = [];
  for (const ei of n.edges) {
    if (used.has(ei)) continue;
    const e = graph.edges[ei]!;
    if (e.dead && near) continue;
    if (!allowed(graph, ei, e.a === node ? 1 : -1)) continue;
    const h = leave(graph, ei, node);
    const ahead = h.x * inHeading.x + h.z * inHeading.z;
    // twist 1: turns first; less, the more it leans towards carrying straight on.
    // (twist below 0: just turned, so carrying straight on comes first.)
    let score = (ahead > -0.4 ? (twist >= 0 ? (1 - Math.abs(ahead)) * 2 * twist + ahead * 1.8 * (1 - twist) : ahead * 1.8) : -2) + rand() * 1.2;
    if (near) {
      const other = graph.nodes[e.a === node ? e.b : e.a]!;
      const before = Math.hypot(n.x - near.x, n.z - near.z);
      const after = Math.hypot(other.x - near.x, other.z - near.z);
      score += ((before - after) / Math.max(40, e.len)) * near.w;
    }
    scored.push([ei, score]);
  }
  return scored.sort((a, b) => b[1] - a[1]).map(([ei]) => ei);
}

/** Point to point: a path of edges from the start until `length` is used up, the finish part way along the last. */
function searchLine(graph: RoadGraph, start: RoutePoint, length: number, seed: number, twist: number): Step[] | null {
  const rand = seeded(seed);
  const e0 = graph.edges[start.edge]!;
  let budget = 40000;
  const used = new Set<number>([start.edge]);
  const steps: Step[] = [];
  const go = (node: number, heading: { x: number; z: number }, left: number, since: number): boolean => {
    if (--budget < 0) return false;
    for (const ei of options(graph, node, heading, used, rand, since < STRAIGHT ? -0.4 : twist)) {
      const e = graph.edges[ei]!;
      const fromA = e.a === node;
      // The finish falls on this stretch: not right at either end of it.
      if (left <= e.len - 12 && left >= Math.min(12, e.len / 2)) {
        steps.push({ edge: ei, t0: fromA ? 0 : e.len, t1: fromA ? left : e.len - left, from: node });
        return true;
      }
      if (left < e.len) continue;
      used.add(ei);
      steps.push({ edge: ei, t0: fromA ? 0 : e.len, t1: fromA ? e.len : 0, from: node });
      const other = fromA ? e.b : e.a;
      const h = leave(graph, ei, other);
      if (go(other, { x: -h.x, z: -h.z }, left - e.len, runOn(graph, ei, node, heading, since))) return true;
      steps.pop();
      used.delete(ei);
    }
    return false;
  };
  // Off either way along the start's own road, the longer way first.
  const ends = start.t > e0.len - start.t ? [e0.a, e0.b] : [e0.b, e0.a];
  for (const end of ends) {
    if (!allowed(graph, start.edge, end === e0.a ? -1 : 1)) continue;
    const run = end === e0.a ? start.t : e0.len - start.t;
    const t1 = end === e0.a ? 0 : e0.len;
    if (run >= length) return [{ edge: start.edge, t0: start.t, t1: end === e0.a ? start.t - length : start.t + length, from: -1 }];
    steps.length = 0;
    steps.push({ edge: start.edge, t0: start.t, t1, from: -1 });
    const into = leave(graph, start.edge, end);
    if (go(end, { x: -into.x, z: -into.z }, length - run, run)) return steps;
  }
  return null;
}

/** A circuit: out along the start's road one way, round, and back in along it from the other end. */
function searchLoop(graph: RoadGraph, start: RoutePoint, length: number, seed: number, twist: number): Step[] | null {
  const rand = seeded(seed);
  const e0 = graph.edges[start.edge]!;
  if (e0.a === e0.b || !allowed(graph, start.edge, 1)) return null;
  const home = graph.nodes[e0.a]!;
  const target = length - e0.len;
  const used = new Set<number>([start.edge]);
  const steps: Step[] = [];
  let best: Step[] | null = null;
  let bestErr = Infinity;
  let budget = 40000;
  const tol = Math.max(80, length * 0.06);
  const go = (node: number, heading: { x: number; z: number }, run: number, since: number): boolean => {
    if (--budget < 0) return true;
    if (node === e0.a) {
      const err = Math.abs(run - target);
      if (err < bestErr) {
        bestErr = err;
        best = steps.slice();
      }
      return err < tol;
    }
    // Too far out to get home in time.
    const nn = graph.nodes[node]!;
    if (run + Math.hypot(nn.x - home.x, nn.z - home.z) > target + tol) return false;
    const pull = run > target * 0.45 ? { x: home.x, z: home.z, w: 2.5 * (run / target) } : undefined;
    for (const ei of options(graph, node, heading, used, rand, since < STRAIGHT ? -0.4 : twist, pull)) {
      const e = graph.edges[ei]!;
      const fromA = e.a === node;
      used.add(ei);
      steps.push({ edge: ei, t0: fromA ? 0 : e.len, t1: fromA ? e.len : 0, from: node });
      const other = fromA ? e.b : e.a;
      const h = leave(graph, ei, other);
      if (go(other, { x: -h.x, z: -h.z }, run + e.len, runOn(graph, ei, node, heading, since))) return true;
      steps.pop();
      used.delete(ei);
    }
    return false;
  };
  const into = leave(graph, start.edge, e0.b);
  go(e0.b, { x: -into.x, z: -into.z }, 0, e0.len - start.t);
  const found = best as Step[] | null;
  if (!found || bestErr > length * 0.35) return null;
  return [{ edge: start.edge, t0: start.t, t1: e0.len, from: -1 }, ...found, { edge: start.edge, t0: 0, t1: start.t, from: e0.a }];
}

/**
 * Waypoints that pin the planner's route (the shortest way between each pair) to the
 * steps: from each waypoint, on as far along the steps as the shortest way still follows
 * them, then a waypoint there.
 */
function pin(graph: RoadGraph, start: RoutePoint, steps: Step[], loop: boolean): RoutePoint[] {
  const way: RoutePoint[] = [start];
  const last = steps.length - 1;
  // Candidate places: the middle of each whole stretch, and the finish.
  const at = (k: number): RoutePoint => {
    const st = steps[k]!;
    const t = k === last ? st.t1 : (st.t0 + st.t1) / 2;
    const p = pointOnEdge(graph, st.edge, t);
    return { x: p.x, z: p.z, edge: st.edge, t };
  };
  // (A circuit's last step ends back at the start, which closes the loop by itself.)
  const end = last;
  // The way the shortest path from w goes along step k's edge (does it come in by step k's junction, the right way?).
  const follows = (i: number, j: number, prevNode: Int32Array, prevEdge: Int32Array, dist: Float64Array): boolean => {
    const st = steps[j]!;
    const e = graph.edges[st.edge]!;
    const q = at(j);
    const viaA = dist[e.a]! + q.t;
    const viaB = dist[e.b]! + (e.len - q.t);
    if ((viaA <= viaB ? e.a : e.b) !== st.from) return false;
    // Back from there to the waypoint, edge by edge against the steps.
    let node = st.from;
    for (let k = j - 1; k > i; k--) {
      if (prevNode[node] === -2 || prevEdge[node] !== steps[k]!.edge) return false;
      node = prevNode[node]!;
    }
    return prevNode[node] === -2 && prevEdge[node] === steps[i]!.edge;
  };
  /** A place on step k, d metres in from where it starts. */
  const into = (k: number, d: number): RoutePoint => {
    const st = steps[k]!;
    const t = st.t0 + Math.sign(st.t1 - st.t0) * Math.min(d, Math.abs(st.t1 - st.t0));
    const p = pointOnEdge(graph, st.edge, t);
    return { x: p.x, z: p.z, edge: st.edge, t };
  };
  let i = 0;
  let done = false;
  while (i < end) {
    const { prevNode, prevEdge, dist } = dijkstra(graph, way[way.length - 1]!);
    let best = -1;
    for (let j = i + 1; j <= end; j++) {
      if (!follows(i, j, prevNode, prevEdge, dist)) break;
      best = j;
    }
    if (best < 0) {
      // Even the next stretch's middle is quicker reached some other way (a long road whose
      // far end is close by another): a waypoint just into it, then on along it.
      way.push(into(i + 1, 12));
      i++;
      continue;
    }
    if (loop && best === last) {
      done = true;
      break;
    }
    way.push(at(best));
    i = best;
    done = best === last;
  }
  // Still short of the finish, part way along its stretch: waypoints on along it, close
  // enough together that each next one is straight on along the road.
  if (!loop && !done) {
    const st = steps[last]!;
    const from = way[way.length - 1]!.edge === st.edge ? way[way.length - 1]!.t : st.t0;
    const run = Math.abs(st.t1 - from);
    const n = Math.floor(run / 120);
    for (let k = 1; k <= n; k++) {
      const t = from + Math.sign(st.t1 - from) * k * 120;
      const p = pointOnEdge(graph, st.edge, t);
      way.push({ x: p.x, z: p.z, edge: st.edge, t });
    }
    way.push(at(last));
  }
  // A circuit wants at least two waypoints after the start to make a loop of.
  if (loop && way.length < 3 && steps.length > 3) way.splice(1, 0, at(Math.floor(steps.length / 2)));
  return way;
}