Flow mark

/**
 * flow-mark
 *
 * A drawing made by a program, once, in the build: evenly spaced lines
 * that follow a field, as one SVG path. On the page it is a picture:
 * no script, no frames, no GPU, sharp at any size, printable. The
 * same seed gives the same bytes every time, so a project's route slug
 * can give it a mark of its own that both language versions share.
 *
 * Copy this file. It imports nothing.
 *
 * In a build (an Astro component script, a Node script):
 *
 *     import { generate, hashSeed } from './flow-mark';
 *     const svg = generate(hashSeed(slug), { width: 240, height: 240, shape: 1 });
 *
 * In a browser, which is for a lab page and not for a reader's page
 * (the generator costs a hundred milliseconds of main thread that a
 * build pays once):
 *
 *     import { mount } from './flow-mark';
 *     mount(document.querySelector('.emblem'), { seed: hashSeed(slug) });
 *
 * The lines are Jobard and Lefer's evenly spaced streamlines: a line
 * grows from a seed until it comes too close to another, and new seeds
 * are tried one spacing to either side of every line already drawn.
 * Every algorithm here was written from its published description.
 */

export interface Options {
  /** Which mark of the family: any whole number. A consumer passes hashSeed(slug), so both languages of a page share one mark. */
  seed: number;
  /** The mark's width in units, which are CSS px at the size it is shown. 0 is the element's own box at mount, or 600 from generate(). */
  width: number;
  /** The mark's height in units. 0 is the element's own box at mount, or 400 from generate(). */
  height: number;
  /** Distance between lines, in units. Under about 6 the lines stop reading as lines; over 24 a few stray lines read as unfinished. */
  spacing: number;
  /** How close a line may come to another before it stops, as a share of spacing. Low: long lines that pinch together; high: short broken lines with gaps. */
  test: number;
  /** Integration step, as a share of spacing. Low: slower, no visible gain; high: lines slip past each other. */
  step: number;
  /** Cycles of the field across the width. Low: one broad sweep; high: busy curls and many short lines. */
  frequency: number;
  /** Full turns the angle makes across the noise range. Low: nearly parallel, combed; high: tight whorls where lines crowd. */
  turns: number;
  /** Noise octaves summed: 1 very smooth, 3 wobbling lines. */
  octaves: number;
  /** The field: 0 noise, 1 a vortex blended in around a centre the seed picks, 2 the angle rounded to 45 degrees (traces), 3 rounded to 60. */
  field: number;
  /** A line whose box is smaller than this many spacings is dropped: stubble at 1, holes where short lines were at 6. */
  extent: number;
  /** Stroke width in units. Under 0.75 it disappears on a 1x screen; over 1.5 it stops reading as a pen. */
  stroke: number;
  /** Simplification tolerance in units: a point this close to the straight line between its neighbours is dropped. Larger: a smaller file, then visible corners. */
  tolerance: number;
  /** The frame: 0 the whole box, 1 a disc inscribed in it. */
  shape: number;
  /** Clear space inside the edge, as a share of the shorter side, so the mark floats on the paper instead of bleeding off it. */
  margin: number;
  /** The seed also moves frequency, turns and spacing around the values set, and may add a vortex or traces: marks then differ in kind, not only in noise. */
  vary: boolean;
}

export const DEFAULTS: Options = {
  seed: 1,
  width: 0,
  height: 0,
  spacing: 10,
  test: 0.5,
  step: 0.25,
  frequency: 1.2,
  turns: 1,
  octaves: 2,
  field: 0,
  extent: 2,
  stroke: 1,
  tolerance: 0.25,
  shape: 0,
  margin: 0,
  vary: true,
};

/**
 * Named marks. The first is the defaults. `generate(seed, PRESETS.Whorl)`.
 */
export const PRESETS: Record<string, Partial<Options>> = {
  Sweep: {},
  Combed: { turns: 0.4, frequency: 0.8 },
  Whorl: { field: 1, turns: 1.6 },
  Traces: { field: 2, spacing: 8 },
  Sparse: { spacing: 18, extent: 3, margin: 0.06 },
};

export interface Handle {
  update(options: Partial<Options>): void;
  destroy(): void;
}

type Point = [number, number];
type Line = Point[];

const NOOP: Handle = { update() {}, destroy() {} };
const mounted = new WeakMap<HTMLElement, Handle>();
const FALLBACK: Point = [600, 400];
/** Every dial's floor and ceiling: a mark can be ugly but a build can never hang. */
const LIMITS: Record<string, [number, number]> = {
  seed: [0, 4294967295],
  width: [0, 2400],
  height: [0, 2400],
  spacing: [3, 200],
  test: [0.2, 0.95],
  step: [0.1, 0.5],
  frequency: [0.1, 6],
  turns: [0.1, 4],
  octaves: [1, 3],
  field: [0, 3],
  extent: [0, 10],
  stroke: [0.25, 4],
  tolerance: [0.05, 2],
  shape: [0, 1],
  margin: [0, 0.3],
};
const WHOLE = new Set(['seed', 'octaves', 'field', 'shape']);
const CEILING = 40000;

/** Options clamped to their limits; anything that is not a finite number falls back to the base. */
export function mergeOptions(base: Options, partial: Partial<Options>): Options {
  const merged = { ...base, ...partial } as Options;
  const out: Record<string, number | boolean> = { ...merged };
  for (const key of Object.keys(LIMITS)) {
    const [low, high] = LIMITS[key] ?? [0, 0];
    const given = merged[key as keyof Options];
    let value = typeof given === 'number' && Number.isFinite(given) ? given : (base[key as keyof Options] as number);
    value = Math.min(high, Math.max(low, value));
    out[key] = WHOLE.has(key) ? Math.floor(value) : value;
  }
  out.vary = typeof merged.vary === 'boolean' ? merged.vary : base.vary;
  return out as unknown as Options;
}

/** FNV-1a over the string's code units: a slug to a 32-bit seed. */
export function hashSeed(text: string): number {
  let h = 0x811c9dc5;
  for (let i = 0; i < text.length; i += 1) h = Math.imul(h ^ text.charCodeAt(i), 0x01000193);
  return h >>> 0;
}

/** Xorshift32, warmed eight rounds: without the warm-up, seeds 1 to 8 open on eight nearly equal numbers. */
export function makeRandom(seed: number): () => number {
  let s = seed >>> 0 || 0x9e3779b9;
  const next = (): number => {
    s ^= s << 13;
    s ^= s >>> 17;
    s ^= s << 5;
    s >>>= 0;
    return s / 4294967296;
  };
  for (let i = 0; i < 8; i += 1) next();
  return next;
}

/** Gradient noise: seeded unit vectors on an integer lattice, blended with a quintic fade. About [-1, 1], 0 on the lattice. */
export function makeNoise(random: () => number): (x: number, y: number) => number {
  const perm: number[] = [];
  const grads: Point[] = [];
  for (let i = 0; i < 256; i += 1) {
    perm.push(i);
    const a = random() * Math.PI * 2;
    grads.push([Math.cos(a), Math.sin(a)]);
  }
  for (let i = 255; i > 0; i -= 1) {
    const j = Math.floor(random() * (i + 1));
    const t = perm[i] ?? 0;
    perm[i] = perm[j] ?? 0;
    perm[j] = t;
  }
  const fade = (t: number): number => t * t * t * (t * (t * 6 - 15) + 10);
  const dot = (ix: number, iy: number, dx: number, dy: number): number => {
    const g = grads[((perm[ix & 255] ?? 0) + iy) & 255] ?? [0, 0];
    return g[0] * dx + g[1] * dy;
  };
  return (x, y) => {
    const x0 = Math.floor(x);
    const y0 = Math.floor(y);
    const fx = x - x0;
    const fy = y - y0;
    const u = fade(fx);
    const v = fade(fy);
    const a = dot(x0, y0, fx, fy) + (dot(x0 + 1, y0, fx - 1, fy) - dot(x0, y0, fx, fy)) * u;
    const b = dot(x0, y0 + 1, fx, fy - 1) + (dot(x0 + 1, y0 + 1, fx - 1, fy - 1) - dot(x0, y0 + 1, fx, fy - 1)) * u;
    return Math.max(-1, Math.min(1, (a + (b - a) * v) * 1.4));
  };
}

/** Ramer-Douglas-Peucker: keep the ends, keep the farthest point if it is farther than the tolerance, recurse on both halves. */
export function simplify(points: Line, tolerance: number): Line {
  if (points.length < 3) return points;
  const keep = new Uint8Array(points.length);
  keep[0] = 1;
  keep[points.length - 1] = 1;
  const stack: Point[] = [[0, points.length - 1]];
  while (stack.length > 0) {
    const [first, last] = stack.pop() as Point;
    const [ax, ay] = points[first] as Point;
    const [bx, by] = points[last] as Point;
    const dx = bx - ax;
    const dy = by - ay;
    const length = Math.hypot(dx, dy) || 1;
    let farthest = 0;
    let at = -1;
    for (let i = first + 1; i < last; i += 1) {
      const [px, py] = points[i] as Point;
      const distance = Math.abs(dx * (ay - py) - dy * (ax - px)) / length;
      if (distance > farthest) {
        farthest = distance;
        at = i;
      }
    }
    if (farthest > tolerance && at > 0) {
      keep[at] = 1;
      stack.push([first, at], [at, last]);
    }
  }
  return points.filter((_, i) => keep[i] === 1);
}

const round = (value: number): number => Math.round(value * 10) / 10;
const digits = (value: number): string => String(round(value));
/** Path tokens joined with a space only where the next one does not start with a minus. */
const join = (tokens: string[]): string => tokens.reduce((d, token) => d + (/[\d.]$/.test(d) && !token.startsWith('-') && !/^[A-Za-z]/.test(token) ? ' ' : '') + token, '');

/** One subpath per line: an absolute move, then relative segments between rounded points, one decimal, so nothing drifts. */
export function pathData(lines: Line[]): string {
  let d = '';
  for (const line of lines) {
    if (line.length < 2) continue;
    let [x, y] = [round(line[0]?.[0] ?? 0), round(line[0]?.[1] ?? 0)];
    const tokens = [`M${digits(x)}`, digits(y), 'l'];
    for (let i = 1; i < line.length; i += 1) {
      const nx = round(line[i]?.[0] ?? 0);
      const ny = round(line[i]?.[1] ?? 0);
      tokens.push(digits(nx - x), digits(ny - y));
      x = nx;
      y = ny;
    }
    d += join(tokens);
  }
  return d;
}

export interface Walk {
  width: number;
  height: number;
  spacing: number;
  test: number;
  step: number;
  extent: number;
  ceiling: number;
}

/**
 * Jobard and Lefer's evenly spaced streamlines. `direction` gives the
 * field's angle at a point, `inside` says whether a point is in the
 * frame. A collision grid of cells one spacing wide keeps every test to
 * nine cells. A line's own points count too, except the most recent
 * spacing's worth, so a line cannot spiral into a sink for ever.
 */
export function streamlines(walk: Walk, direction: (x: number, y: number) => number, inside: (x: number, y: number) => boolean): Line[] {
  const { width, height, spacing } = walk;
  const dTest = spacing * walk.test;
  const ds = spacing * walk.step;
  const skip = Math.ceil(spacing / ds);
  const columns = Math.ceil(width / spacing) + 2;
  const rows = Math.ceil(height / spacing) + 2;
  const cells: number[][][] = Array.from({ length: columns * rows }, () => []);
  const cellOf = (x: number, y: number): number => Math.min(columns - 1, Math.max(0, Math.floor(x / spacing))) + columns * Math.min(rows - 1, Math.max(0, Math.floor(y / spacing)));
  const near = (x: number, y: number, within: number, line: number, k: number): boolean => {
    const cell = cellOf(x, y);
    const cx = cell % columns;
    const cy = (cell - cx) / columns;
    for (let j = Math.max(0, cy - 1); j <= Math.min(rows - 1, cy + 1); j += 1) {
      for (let i = Math.max(0, cx - 1); i <= Math.min(columns - 1, cx + 1); i += 1) {
        for (const p of cells[i + j * columns] ?? []) {
          if (p[2] === line && Math.abs((p[3] ?? 0) - k) <= skip) continue;
          if (((p[0] ?? 0) - x) ** 2 + ((p[1] ?? 0) - y) ** 2 < within * within) return true;
        }
      }
    }
    return false;
  };
  const lines: Line[] = [];
  let total = 0;
  const trace = (sx: number, sy: number): Line | null => {
    const id = lines.length;
    const touched: number[] = [];
    const put = (x: number, y: number, k: number): void => {
      const cell = cellOf(x, y);
      cells[cell]?.push([x, y, id, k]);
      touched.push(cell);
    };
    put(sx, sy, 0);
    const grow = (sign: number): Line => {
      const out: Line = [];
      let x = sx;
      let y = sy;
      const most = Math.ceil((2 * (width + height)) / ds);
      for (let k = 1; k <= most; k += 1) {
        const a = direction(x, y);
        const mx = x + sign * Math.cos(a) * ds * 0.5;
        const my = y + sign * Math.sin(a) * ds * 0.5;
        const b = direction(mx, my);
        const nx = x + sign * Math.cos(b) * ds;
        const ny = y + sign * Math.sin(b) * ds;
        if (!inside(nx, ny) || near(nx, ny, dTest, id, k * sign)) break;
        out.push([nx, ny]);
        put(nx, ny, k * sign);
        x = nx;
        y = ny;
      }
      return out;
    };
    const forward = grow(1);
    const backward = grow(-1);
    const line: Line = [...backward.reverse(), [sx, sy], ...forward];
    let minX = Infinity;
    let maxX = -Infinity;
    let minY = Infinity;
    let maxY = -Infinity;
    for (const [x, y] of line) {
      minX = Math.min(minX, x);
      maxX = Math.max(maxX, x);
      minY = Math.min(minY, y);
      maxY = Math.max(maxY, y);
    }
    if (Math.max(maxX - minX, maxY - minY) < walk.extent * spacing) {
      for (const cell of touched) cells[cell] = (cells[cell] ?? []).filter((p) => p[2] !== id);
      return null;
    }
    lines.push(line);
    total += line.length;
    return line;
  };
  // The first seed is the centre; if the line there is too short, a
  // coarse grid of other starts is tried, so a mark is never empty for
  // the sake of one sink.
  let first: Line | null = null;
  for (let i = 0; i < 25 && !first; i += 1) {
    const x = (width * (1 + 2 * (i % 5))) / 10;
    const y = (height * (1 + 2 * Math.floor(i / 5))) / 10;
    if (inside(x, y)) first = trace(i === 0 ? width / 2 : x, i === 0 ? height / 2 : y);
  }
  if (!first) return lines;
  const queue: Line[] = [first];
  for (let q = 0; q < queue.length && total < walk.ceiling; q += 1) {
    for (const [x, y] of queue[q] ?? []) {
      const a = direction(x, y);
      for (const side of [1, -1]) {
        const cx = x - side * Math.sin(a) * spacing;
        const cy = y + side * Math.cos(a) * spacing;
        if (!inside(cx, cy) || near(cx, cy, spacing - 1e-6, -1, 0)) continue;
        const made = trace(cx, cy);
        if (made) queue.push(made);
        if (total >= walk.ceiling) break;
      }
      if (total >= walk.ceiling) break;
    }
  }
  return lines;
}

const QUANTA = [0, 0, Math.PI / 4, Math.PI / 3];

/** What a mark is made of, before it is written: the frame, the stroke, the path data and the longest line. */
export interface Mark {
  seed: number;
  width: number;
  height: number;
  stroke: number;
  d: string;
  longest: number;
}

/** The mark as numbers and path data. `generate` writes it as a string; `mount` builds it as elements. */
export function build(seed: number | string, options: Partial<Options> = {}): Mark {
  const o = mergeOptions(DEFAULTS, { ...options, seed: typeof seed === 'string' ? hashSeed(seed) : seed });
  const width = o.width || FALLBACK[0];
  const height = o.height || FALLBACK[1];
  const random = makeRandom(o.seed);
  const noise = makeNoise(random);
  let { frequency, turns, spacing, field } = o;
  if (o.vary) {
    frequency *= 0.6 * (1.7 / 0.6) ** random();
    turns *= 0.5 * (1.6 / 0.5) ** random();
    spacing *= [0.8, 1, 1.25][Math.floor(random() * 3)] ?? 1;
    const kind = random();
    if (field === 0) field = kind < 0.3 ? 1 : kind < 0.4 ? 2 : 0;
  }
  const centre: Point = [width * (0.25 + 0.5 * random()), height * (0.25 + 0.5 * random())];
  const f = frequency / width;
  const quantum = QUANTA[field] ?? 0;
  const direction = (x: number, y: number): number => {
    let sum = 0;
    let weight = 0;
    for (let k = 0; k < o.octaves; k += 1) {
      const amp = 0.5 ** k;
      sum += amp * noise(x * f * 2 ** k + 7.3 * k, y * f * 2 ** k + 3.1 * k);
      weight += amp;
    }
    let angle = (sum / weight) * Math.PI * turns;
    if (field === 1) {
      // The pull of the vortex fades with distance, so the mark has a
      // centre and is not a fingerprint from edge to edge.
      const dx = x - centre[0];
      const dy = y - centre[1];
      const pull = 0.9 * Math.exp(-(dx * dx + dy * dy) / (0.35 * Math.min(width, height)) ** 2);
      const tangent = Math.atan2(dy, dx) + Math.PI / 2;
      angle = Math.atan2((1 - pull) * Math.sin(angle) + pull * Math.sin(tangent), (1 - pull) * Math.cos(angle) + pull * Math.cos(tangent));
    }
    return quantum ? Math.round(angle / quantum) * quantum : angle;
  };
  const inset = o.margin * Math.min(width, height);
  const radius = Math.min(width, height) / 2 - inset;
  const inside =
    o.shape === 1
      ? (x: number, y: number): boolean => (x - width / 2) ** 2 + (y - height / 2) ** 2 <= radius * radius
      : (x: number, y: number): boolean => x >= inset && x <= width - inset && y >= inset && y <= height - inset;
  const lines = streamlines({ width, height, spacing, test: o.test, step: o.step, extent: o.extent, ceiling: CEILING }, direction, inside).map((line) =>
    simplify(line, o.tolerance),
  );
  let longest = 0;
  for (const line of lines) {
    let length = 0;
    for (let i = 1; i < line.length; i += 1) length += Math.hypot((line[i]?.[0] ?? 0) - (line[i - 1]?.[0] ?? 0), (line[i]?.[1] ?? 0) - (line[i - 1]?.[1] ?? 0));
    longest = Math.max(longest, length);
  }
  return { seed: o.seed, width, height, stroke: o.stroke, d: pathData(lines), longest: round(longest) };
}

const SVG = 'http://www.w3.org/2000/svg';
/** The root's attributes: it takes the colour of the text around it and says nothing to a reader. */
const rootAttributes = (mark: Mark): [string, string][] => [
  ['viewBox', `0 0 ${mark.width} ${mark.height}`],
  ['fill', 'none'],
  ['stroke', 'currentColor'],
  ['stroke-width', String(mark.stroke)],
  ['stroke-linecap', 'round'],
  ['stroke-linejoin', 'round'],
  ['aria-hidden', 'true'],
  ['data-mark', 'flow'],
  ['data-seed', String(mark.seed)],
];

/** The SVG of one mark, as a string, for a build to inline. The seed may be a slug. */
export function generate(seed: number | string, options: Partial<Options> = {}): string {
  const mark = build(seed, options);
  const attributes = rootAttributes(mark).map(([name, value]) => ` ${name}="${value}"`).join('');
  return `<svg xmlns="${SVG}"${attributes}><path d="${mark.d}" data-longest="${mark.longest}"/></svg>`;
}

/** The same mark as elements, for a page that already exists. */
function elementOf(document: Document, mark: Mark): SVGSVGElement {
  const svg = document.createElementNS(SVG, 'svg');
  for (const [name, value] of rootAttributes(mark)) svg.setAttribute(name, value);
  const path = document.createElementNS(SVG, 'path');
  path.setAttribute('d', mark.d);
  path.setAttribute('data-longest', String(mark.longest));
  svg.append(path);
  svg.setAttribute('style', 'display:block;width:100%;height:100%');
  return svg;
}

/**
 * The thin end of the generator, for a lab page: the mark is made in
 * the browser and put into the element, sized by the element's box
 * unless `width` and `height` say otherwise. It hides nothing and
 * animates nothing; `destroy()` removes the one thing it added.
 */
export function mount(element: HTMLElement, options: Partial<Options> = {}): Handle {
  if (!element || typeof element.append !== 'function' || !element.ownerDocument) return NOOP;
  mounted.get(element)?.destroy();
  let current: Partial<Options> = { ...options };
  let svg: Element | null = null;
  const draw = (): void => {
    const width = current.width || element.clientWidth || 0;
    const height = current.height || element.clientHeight || 0;
    const next = elementOf(element.ownerDocument, build(current.seed ?? DEFAULTS.seed, { ...current, width, height }));
    if (svg) svg.replaceWith(next);
    else element.append(next);
    svg = next;
  };
  const handle: Handle = {
    update(next) {
      current = { ...current, ...next };
      try {
        draw();
      } catch {
        /* a mark that cannot be made leaves the page as it was */
      }
    },
    destroy() {
      svg?.remove();
      svg = null;
      mounted.delete(element);
    },
  };
  mounted.set(element, handle);
  handle.update({});
  return handle;
}