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/road-surface.ts
import * as THREE from 'three';
import { Clipper, FillRule, Path64, Paths64, PointInPolygonResult, type Point64 } from 'clipper2-js';

/**
 * Road surfaces as shapes rather than strips: every road's outline merged into one shape
 * (Clipper2) and triangulated (earcut, via three's ShapeUtils) into one surface. Where roads
 * cross or join at any angle there's a single clean piece of asphalt: no overlaps, no
 * slivers, no gaps showing the ground.
 *
 * The outlines are sorted into square tiles first and each tile merged and triangulated on
 * its own: small simple shapes, which earcut always gets right (one shape for the whole
 * city's streets, with hundreds of holes, it doesn't), and quick. Each tile's triangles are
 * checked against its area; if they don't add up, the tile falls back on its outlines
 * drawn as they are.
 */

/** Clipper works in whole numbers: centimetres (decimetres left hairline cracks between neighbouring pieces). */
const S = 100;
const TILE = 100;

export type Ring = { x: number; z: number }[];
type Emit = (a: [number, number], b: [number, number], c: [number, number]) => void;

/** The outline of a road hw either side of a centre line. */
export function ribbon(pts: { x: number; z: number }[], hw: number): Ring {
  const n = pts.length;
  const left: Ring = [];
  const right: Ring = [];
  for (let i = 0; i < n; i++) {
    const a = pts[Math.max(0, i - 1)]!;
    const b = pts[Math.min(n - 1, i + 1)]!;
    const l = Math.hypot(b.x - a.x, b.z - a.z) || 1;
    const nx = -(b.z - a.z) / l;
    const nz = (b.x - a.x) / l;
    left.push({ x: pts[i]!.x + nx * hw, z: pts[i]!.z + nz * hw });
    right.push({ x: pts[i]!.x - nx * hw, z: pts[i]!.z - nz * hw });
  }
  return [...left, ...right.reverse()];
}

/** A circle of radius r round (x, z). */
export function disc(x: number, z: number, r: number, n = 20): Ring {
  return Array.from({ length: n }, (_, k) => ({ x: x + Math.cos((k / n) * Math.PI * 2) * r, z: z + Math.sin((k / n) * Math.PI * 2) * r }));
}

/** A rectangle. */
export function rect(x0: number, z0: number, x1: number, z1: number): Ring {
  return [
    { x: x0, z: z0 },
    { x: x1, z: z0 },
    { x: x1, z: z1 },
    { x: x0, z: z1 },
  ];
}

function toPath(r: Ring): Path64 {
  const p = new Path64();
  for (const q of r) p.push({ x: Math.round(q.x * S), y: Math.round(q.z * S) });
  return p;
}

function paths(rings: Ring[]): Paths64 {
  const out = new Paths64();
  for (const r of rings) {
    if (r.length < 3) continue;
    // All the same way round: where two outlines overlap, one going each way would cancel
    // out (a hole in the road) rather than add up.
    const p = toPath(r);
    out.push(Clipper.area(p) < 0 ? Clipper.reversePath(p) : p);
  }
  return out;
}

/** Each ring into the tiles its bounds overlap. */
function bucket(rings: Ring[]): Map<string, Ring[]> {
  const out = new Map<string, Ring[]>();
  for (const r of rings) {
    let x0 = Infinity;
    let x1 = -Infinity;
    let z0 = Infinity;
    let z1 = -Infinity;
    for (const q of r) {
      x0 = Math.min(x0, q.x);
      x1 = Math.max(x1, q.x);
      z0 = Math.min(z0, q.z);
      z1 = Math.max(z1, q.z);
    }
    for (let tx = Math.floor(x0 / TILE); tx <= Math.floor(x1 / TILE); tx++)
      for (let tz = Math.floor(z0 / TILE); tz <= Math.floor(z1 / TILE); tz++) {
        const k = `${tx},${tz}`;
        let list = out.get(k);
        if (!list) out.set(k, (list = []));
        list.push(r);
      }
  }
  return out;
}

/** A shape's pieces as triangles; false if they don't cover exactly its area (earcut got it wrong). */
function fill(shape: Paths64, emit: Emit): boolean {
  const outers: Path64[] = [];
  const holes: Path64[] = [];
  for (const p of shape) if (p.length >= 3) (Clipper.area(p) > 0 ? outers : holes).push(p);
  const areas = outers.map((p) => Clipper.area(p));
  const kids: Path64[][] = outers.map(() => []);
  for (const h of holes) {
    let best = -1;
    outers.forEach((o, i) => {
      if (Clipper.pointInPolygon(h[0] as Point64, o) === PointInPolygonResult.IsOutside) return;
      if (best < 0 || areas[i]! < areas[best]!) best = i;
    });
    if (best >= 0) kids[best]!.push(h);
  }
  const v = (p: Path64) => p.map((q) => new THREE.Vector2(q.x / S, q.y / S));
  const out: [number, number][][] = [];
  let ok = true;
  outers.forEach((o, i) => {
    const contour = v(o);
    const hs = kids[i]!.map(v);
    const all = [...contour, ...hs.flat()];
    let got = 0;
    for (const [a, b, c] of THREE.ShapeUtils.triangulateShape(contour, hs)) {
      const p = all[a!]!;
      const q = all[b!]!;
      const r = all[c!]!;
      got += Math.abs((q.x - p.x) * (r.y - p.y) - (q.y - p.y) * (r.x - p.x)) / 2;
      out.push([
        [p.x, p.y],
        [q.x, q.y],
        [r.x, r.y],
      ]);
    }
    const want = (areas[i]! + kids[i]!.reduce((s, h) => s + Clipper.area(h), 0)) / (S * S);
    if (Math.abs(got - want) > 0.5 + want * 0.001) ok = false;
  });
  if (ok) for (const t of out) emit(t[0]!, t[1]!, t[2]!);
  return ok;
}

/**
 * The rings merged (less any of `minus`, and within `within` if given) and triangulated,
 * a tile at a time. Returns how many tiles had to fall back on their raw outlines.
 */
export function surface(rings: Ring[], emit: Emit, opts: { minus?: Ring[]; within?: Ring } = {}): number {
  const tiles = bucket(rings);
  const cut = opts.minus ? bucket(opts.minus) : null;
  let fallbacks = 0;
  const w = new Paths64();
  if (opts.within) w.push(toPath(opts.within));
  // A square: merged and triangulated; if earcut gets it wrong, in quarters, down to 12.5 m.
  const square = (x0: number, z0: number, size: number, list: Ring[], minus: Ring[] | undefined): void => {
    const box = new Paths64();
    box.push(toPath(rect(x0, z0, x0 + size, z0 + size)));
    let shape = Clipper.Intersect(Clipper.Union(paths(list), undefined, FillRule.NonZero), box, FillRule.NonZero);
    if (minus) shape = Clipper.Difference(shape, paths(minus), FillRule.NonZero);
    if (opts.within) shape = Clipper.Intersect(shape, w, FillRule.NonZero);
    if (!shape.length || fill(shape, emit)) return;
    if (size > TILE / 8) {
      const h = size / 2;
      for (const [dx, dz] of [[0, 0], [h, 0], [0, h], [h, h]] as const) square(x0 + dx, z0 + dz, h, list, minus);
      return;
    }
    fallbacks++;
    // Drawn as they are instead (overlapping, but never wrong).
    for (const r of list) fill(Clipper.Intersect(paths([r]), box, FillRule.NonZero), emit);
  };
  for (const [k, list] of tiles) {
    const [tx, tz] = k.split(',').map(Number) as [number, number];
    square(tx * TILE, tz * TILE, TILE, list, cut?.get(k));
  }
  return fallbacks;
}

/**
 * A ring less some others, cut exactly (along their edges, at whatever angle), and
 * triangulated; returns the outlines of what's left (for kerbs along them).
 */
export function cutOut(base: Ring, minus: Ring[], emit: Emit): Ring[] {
  const sub = minus.length ? paths(minus) : null;
  const cut = (ring: Paths64) => (sub ? Clipper.Difference(ring, sub, FillRule.NonZero) : ring);
  const shape = cut(paths([base]));
  // Earcut slips up now and then: then the piece is filled a quarter at a time (down to
  // squares of a metre or so), each cut the same way.
  const square = (x0: number, z0: number, x1: number, z1: number, piece: Paths64, depth: number): void => {
    if (!piece.length || fill(piece, emit) || depth > 5) return;
    const xm = (x0 + x1) / 2;
    const zm = (z0 + z1) / 2;
    for (const [a, b, c, d] of [
      [x0, z0, xm, zm],
      [xm, z0, x1, zm],
      [x0, zm, xm, z1],
      [xm, zm, x1, z1],
    ] as const) {
      const q = new Paths64();
      q.push(toPath(rect(a, b, c, d)));
      square(a, b, c, d, Clipper.Intersect(shape, q, FillRule.NonZero), depth + 1);
    }
  };
  const xs = base.map((p) => p.x);
  const zs = base.map((p) => p.z);
  square(Math.min(...xs), Math.min(...zs), Math.max(...xs), Math.max(...zs), shape, 0);
  return shape.map((p) => p.map((q) => ({ x: q.x / S, z: q.y / S })));
}