Contour mark

/**
 * contour-mark
 *
 * The contour lines of a made-up terrain, made once in the build as
 * one SVG path: a seeded height field, sampled on a grid, and the
 * lines where it crosses each of a set of levels. On the page it is a
 * picture: no script, no frames, no GPU, sharp at any size. The same
 * seed gives the same bytes every time.
 *
 * Copy this file. It imports nothing.
 *
 *     import { generate, hashSeed } from './contour-mark';
 *     const svg = generate(hashSeed(slug), { width: 600, height: 400 });
 *
 * The contours come from marching squares, written from the published
 * description: sixteen cases a cell, the two ambiguous ones resolved
 * by the cell's centre. Segments are joined into lines by the grid
 * edge they sit on, which is an integer, so no coordinates are ever
 * compared.
 */

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;
  /** How many contour levels between the lowest and highest point. A few rings at 3; a dense map at 30. */
  levels: number;
  /** The sampling grid's cell, in units. Smaller follows the field more closely and costs time; larger shows the grid as flats without smoothing. */
  cell: number;
  /** Cycles of the field across the width. Low: one broad hill; high: many small ones. */
  frequency: number;
  /** Noise octaves summed: 1 smooth hills, 3 rough ground. */
  octaves: number;
  /** Write each line as curves through the midpoints, which hides the grid. Off, the flats show, a look of its own. */
  smooth: boolean;
  /** Every fifth contour heavier, as on a map. Off by default: varying stroke leaves the plotter taste. */
  index: boolean;
  /** 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. */
  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. */
  margin: number;
  /** The seed also moves frequency and octaves around the values set and raises a summit or sinks a basin somewhere of its own. */
  vary: boolean;
}

export const DEFAULTS: Options = {
  seed: 1,
  width: 0,
  height: 0,
  levels: 12,
  cell: 8,
  frequency: 1,
  octaves: 2,
  smooth: true,
  index: false,
  stroke: 1,
  tolerance: 0.25,
  shape: 0,
  margin: 0,
  vary: true,
};

/**
 * Named marks. The first is the defaults. `generate(seed, PRESETS.Map)`.
 */
export const PRESETS: Record<string, Partial<Options>> = {
  Terrain: {},
  Sparse: { levels: 6 },
  Fine: { levels: 24, cell: 5 },
  Map: { index: true },
  Faceted: { smooth: false, cell: 14 },
};

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],
  levels: [1, 60],
  cell: [3, 200],
  frequency: [0.1, 6],
  octaves: [1, 3],
  stroke: [0.25, 4],
  tolerance: [0.05, 2],
  shape: [0, 1],
  margin: [0, 0.3],
};
const WHOLE = new Set(['seed', 'levels', 'octaves', 'shape']);

/** 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;
  }
  for (const key of ['smooth', 'index', 'vary'] as const) out[key] = typeof merged[key] === 'boolean' ? merged[key] : base[key];
  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. */
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]. */
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 one is needed: between two numbers, the second not negative. */
const join = (tokens: string[]): string => tokens.reduce((d, token) => d + (/[\d.]$/.test(d) && !token.startsWith('-') && !/^[A-Za-z]/.test(token) ? ' ' : '') + token, '');

/**
 * One line as path data, relative, to one decimal, between rounded
 * points so nothing drifts. Smooth: quadratic curves with each point as
 * the control and the midpoints as the ends, which is the curve
 * corner-cutting converges to and needs no extra points. A closed line
 * starts on a midpoint and ends with z.
 */
export function smoothPath(line: Line, closed: boolean): string {
  const n = closed ? line.length - 1 : line.length;
  if (n < 2) return '';
  const at = (i: number): Point => [round(line[((i % n) + n) % n]?.[0] ?? 0), round(line[((i % n) + n) % n]?.[1] ?? 0)];
  const mid = (i: number): Point => {
    const [ax, ay] = at(i);
    const [bx, by] = at(i + 1);
    return [round((ax + bx) / 2), round((ay + by) / 2)];
  };
  let [x, y] = closed ? mid(0) : at(0);
  const tokens = [`M${digits(x)}`, digits(y)];
  const to = (command: string, ...points: Point[]): void => {
    tokens.push(command);
    for (const [px, py] of points) tokens.push(digits(px - x), digits(py - y));
    const last = points[points.length - 1] as Point;
    [x, y] = last;
  };
  if (closed) {
    for (let i = 1; i <= n; i += 1) to('q', at(i), mid(i));
    tokens.push('z');
  } else {
    for (let i = 1; i < n - 1; i += 1) to('q', at(i), mid(i));
    to('l', at(n - 1));
  }
  return join(tokens);
}

/** One line as straight segments, relative, one decimal. */
export function straightPath(line: Line, closed: boolean): string {
  if (line.length < 2) return '';
  let [x, y] = [round(line[0]?.[0] ?? 0), round(line[0]?.[1] ?? 0)];
  const tokens = [`M${digits(x)}`, digits(y), 'l'];
  const n = closed ? line.length - 1 : line.length;
  for (let i = 1; i < n; 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;
  }
  if (closed) tokens.push('z');
  return join(tokens);
}

/**
 * Marching squares for one level over a grid of `columns` by `rows`
 * cells, sampled at the corners. Each crossing sits on a grid edge,
 * which has an integer key, so segments that share an edge join without
 * comparing coordinates: open chains are walked from their free ends,
 * then what is left is walked as closed loops. Coordinates are in cells.
 */
export function marchingSquares(sample: (i: number, j: number) => number, columns: number, rows: number, level: number): Line[] {
  const stride = columns + 1;
  const points = new Map<number, Point>();
  const links = new Map<number, number[]>();
  const link = (a: number, b: number): void => {
    links.set(a, [...(links.get(a) ?? []), b]);
    links.set(b, [...(links.get(b) ?? []), a]);
  };
  const between = (a: number, b: number): number => (level - a) / (b - a);
  for (let j = 0; j < rows; j += 1) {
    for (let i = 0; i < columns; i += 1) {
      const a = sample(i, j);
      const b = sample(i + 1, j);
      const c = sample(i + 1, j + 1);
      const d = sample(i, j + 1);
      const index = (a > level ? 8 : 0) | (b > level ? 4 : 0) | (c > level ? 2 : 0) | (d > level ? 1 : 0);
      if (index === 0 || index === 15) continue;
      // The four edges by key: top and bottom are horizontal, left and right vertical.
      const edge = [2 * (i + j * stride), 2 * (i + 1 + j * stride) + 1, 2 * (i + (j + 1) * stride), 2 * (i + j * stride) + 1];
      const where: Point[] = [
        [i + between(a, b), j],
        [i + 1, j + between(b, c)],
        [i + between(d, c), j + 1],
        [i, j + between(a, d)],
      ];
      let pairs: number[][];
      const centreHigh = (a + b + c + d) / 4 > level;
      if (index === 5) pairs = centreHigh ? [[3, 0], [1, 2]] : [[0, 1], [3, 2]];
      else if (index === 10) pairs = centreHigh ? [[0, 1], [3, 2]] : [[0, 3], [1, 2]];
      else pairs = [CASES[index] as number[]];
      for (const [p, q] of pairs) {
        const kp = edge[p as number] as number;
        const kq = edge[q as number] as number;
        points.set(kp, where[p as number] as Point);
        points.set(kq, where[q as number] as Point);
        link(kp, kq);
      }
    }
  }
  const seen = new Set<number>();
  const lines: Line[] = [];
  const walk = (start: number): Line => {
    const line: Line = [];
    let at = start;
    let from = -1;
    while (!seen.has(at)) {
      seen.add(at);
      line.push(points.get(at) as Point);
      const next = (links.get(at) ?? []).find((k) => k !== from && !seen.has(k));
      if (next === undefined) break;
      from = at;
      at = next;
    }
    return line;
  };
  for (const [key, near] of links) if (near.length === 1 && !seen.has(key)) lines.push(walk(key));
  for (const key of links.keys()) {
    if (seen.has(key)) continue;
    const loop = walk(key);
    loop.push(loop[0] as Point);
    lines.push(loop);
  }
  return lines;
}

/** Which two edges a segment joins, by case; the ambiguous 5 and 10 are decided by the centre. */
const CASES: Record<number, number[]> = {
  1: [3, 2],
  2: [2, 1],
  3: [3, 1],
  4: [0, 1],
  6: [0, 2],
  7: [3, 0],
  8: [0, 3],
  9: [0, 2],
  11: [0, 1],
  12: [3, 1],
  13: [1, 2],
  14: [3, 2],
};

/** The parts of a line that are inside the frame, each ended on the edge by bisection. */
export function clip(line: Line, inside: (x: number, y: number) => boolean): Line[] {
  const parts: Line[] = [];
  let part: Line = [];
  const edge = (p: Point, q: Point): Point => {
    let [a, b] = [p, q];
    for (let i = 0; i < 18; i += 1) {
      const m: Point = [(a[0] + b[0]) / 2, (a[1] + b[1]) / 2];
      if (inside(m[0], m[1])) a = m;
      else b = m;
    }
    return a;
  };
  for (let i = 0; i < line.length; i += 1) {
    const p = line[i] as Point;
    const was = i > 0 && inside(line[i - 1]?.[0] ?? 0, line[i - 1]?.[1] ?? 0);
    const is = inside(p[0], p[1]);
    if (is) {
      if (i > 0 && !was) part.push(edge(p, line[i - 1] as Point));
      part.push(p);
    } else if (was) {
      part.push(edge(line[i - 1] as Point, p));
      parts.push(part);
      part = [];
    }
  }
  if (part.length > 1) parts.push(part);
  return parts;
}

/** What a mark is made of, before it is written. `heavy` holds the index contours. */
export interface Mark {
  seed: number;
  width: number;
  height: number;
  stroke: number;
  d: string;
  heavy: 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, octaves } = o;
  let bump = 0;
  if (o.vary) {
    frequency *= 0.6 * (1.7 / 0.6) ** random();
    octaves = Math.max(1, Math.min(3, octaves + Math.floor(random() * 3) - 1));
    bump = random() < 0.5 ? -0.55 : 0.55;
  }
  const centre: Point = [width * (0.2 + 0.6 * random()), height * (0.2 + 0.6 * random())];
  const reach = 0.3 * Math.min(width, height);
  const f = frequency / width;
  const columns = Math.max(1, Math.round(width / o.cell));
  const rows = Math.max(1, Math.round(height / o.cell));
  const cw = width / columns;
  const ch = height / rows;
  const field: number[] = [];
  let low = Infinity;
  let high = -Infinity;
  for (let j = 0; j <= rows; j += 1) {
    for (let i = 0; i <= columns; i += 1) {
      const x = i * cw;
      const y = j * ch;
      let sum = 0;
      let weight = 0;
      for (let k = 0; k < 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;
      }
      const value = sum / weight + bump * Math.exp(-((x - centre[0]) ** 2 + (y - centre[1]) ** 2) / (reach * reach));
      field.push(value);
      low = Math.min(low, value);
      high = Math.max(high, value);
    }
  }
  const sample = (i: number, j: number): number => field[i + j * (columns + 1)] ?? 0;
  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 whole = o.shape === 0 && inset === 0;
  let d = '';
  let heavy = '';
  let longest = 0;
  for (let k = 0; k < o.levels; k += 1) {
    const level = low + ((high - low) * (k + 0.5)) / o.levels;
    for (const raw of marchingSquares(sample, columns, rows, level)) {
      const scaled: Line = raw.map(([x, y]) => [x * cw, y * ch]);
      const closedRaw = scaled.length > 2 && scaled[0]?.[0] === scaled[scaled.length - 1]?.[0] && scaled[0]?.[1] === scaled[scaled.length - 1]?.[1];
      for (const part of whole ? [scaled] : clip(scaled, inside)) {
        const closed = closedRaw && part === scaled;
        const line = simplify(closed ? part.slice(0, -1) : part, o.tolerance);
        if (closed) line.push(line[0] as Point);
        if (line.length < (closed ? 4 : 2)) continue;
        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);
        const data = o.smooth ? smoothPath(line, closed) : straightPath(line, closed);
        if (o.index && k % 5 === 0) heavy += data;
        else d += data;
      }
    }
  }
  return { seed: o.seed, width, height, stroke: o.stroke, d, heavy, 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', 'contour'],
  ['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('');
  const index = mark.heavy ? `<path d="${mark.heavy}" stroke-width="${mark.stroke * 2}"/>` : '';
  return `<svg xmlns="${SVG}"${attributes}><path d="${mark.d}" data-longest="${mark.longest}"/>${index}</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);
  if (mark.heavy) {
    const index = document.createElementNS(SVG, 'path');
    index.setAttribute('d', mark.heavy);
    index.setAttribute('stroke-width', String(mark.stroke * 2));
    svg.append(index);
  }
  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;
}