Shroomania: SDF SVG heatmap

sdf-svg-heatmap.ts

import { DisjointSet } from "@thi.ng/adjacency";
import { cosineColor, GRADIENTS } from "@thi.ng/color";
import { identity, partial } from "@thi.ng/compose";
import { serialize } from "@thi.ng/hiccup";
import { rect, svg, text } from "@thi.ng/hiccup-svg";
import { fitClamped, wrap } from "@thi.ng/math";
import { IRandom, Smush32 } from "@thi.ng/random";
import {
    buildKernel2d,
    comp,
    ConvolutionKernel2D,
    convolve2d,
    filter,
    iterator,
    last,
    map,
    mapcat,
    mapIndexed,
    matchFirst,
    multiplexObj,
    push,
    range,
    range2d,
    reduce,
    reducer,
    trace,
    transduce
} from "@thi.ng/transducers";
import { randomBits } from "@thi.ng/transducers-binary";
import { add2, ReadonlyVec } from "@thi.ng/vectors";
import { writeFileSync } from "fs";

///////////////////// types

interface CAOpts {
    width: number;
    height: number;
    rnd?: IRandom;
    seedProb?: number;
    iter?: number;
}

interface GenerationOpts extends CAOpts {
    thresh: number;
    maxTrials?: number;
}

type Edge = [number, number];

///////////////////// constants

const rules = [0, 0, 0, 0, 0, 1, 1, 1, 1, 0, 0, 0, 0, 1, 1, 1, 1, 1];
const kernel = buildKernel2d([1, 1, 1, 1, 0, 1, 1, 1, 1], 3, 3);
const von_neumann = [[-1, 0], [0, -1], [1, 0], [0, 1]];

///////////////////// CA generation

const randomizeGrid = (
    width: number,
    height: number,
    rnd?: IRandom,
    prob = 0.5
) => [...randomBits(prob, width * height, rnd)];

const convolve = (
    src: number[],
    kernel: ConvolutionKernel2D,
    rules: number[],
    width: number,
    height: number,
    rstride = kernel.length,
    wrap = true
) =>
    transduce(
        comp(
            convolve2d({ src, width, height, kernel, wrap }),
            mapIndexed((i, x) => rules[x + src[i] * rstride])
        ),
        push(),
        range2d(width, height)
    );

const computeCA = ({ width, height, rnd, seedProb, iter }: CAOpts) =>
    reduce(
        reducer(
            () => randomizeGrid(width, height, rnd, seedProb),
            (acc) => convolve(acc, kernel, rules, width, height)
        ),
        range(iter || 20)
    );

///////////////////// SDF / elevation

const cellElevation = (
    src: number[],
    width: number,
    height: number,
    [x, y]: ReadonlyVec
) => {
    const yy = y * width;
    const e = src[yy + x] ? 0 : 1;
    let d: number = 1;
    const maxd = Math.min(width, height);
    for (
        let l = x - 1, r = x + 1, t = y - 1, b = y + 1;
        d < maxd;
        d++, l--, b++, r++, t--
    ) {
        l = wrap(l, 0, width);
        r = wrap(r, 0, width);
        t = wrap(t, 0, height);
        b = wrap(b, 0, height);
        const yt = t * width;
        const yb = b * width;
        if (
            src[yy + r] === e ||
            src[yy + l] === e ||
            src[yt + r] === e ||
            src[yt + x] === e ||
            src[yt + l] === e ||
            src[yb + r] === e ||
            src[yb + x] === e ||
            src[yb + l] === e
        ) {
            break;
        }
    }
    return e ? -d : d;
};

const computeElevation = (src: number[], width: number, height: number) =>
    transduce(
        map(partial(cellElevation, src, width, height)),
        push(),
        range2d(width, height)
    );

///////////////////// graph analysis

const neighbors = (src: number[], width: number, height: number, i: number) => {
    const x = i % width;
    const y = (i / width) | 0;
    return iterator<number[], Edge>(
        comp(
            filter(
                ([kx, ky]) => !src[wrappedIndex(x + kx, y + ky, width, height)]
            ),
            map((k) => [i, wrappedIndex(x + k[0], y + k[1], width, height)])
        ),
        von_neumann
    );
};

const walkableEdges = (src: number[], width: number, height: number) =>
    iterator<number, Edge>(
        comp(
            filter((i) => src[i] === 0),
            mapcat((i) => neighbors(src, width, height, i))
        ),
        range(src.length)
    );

const unify = (width: number, height: number) =>
    reducer<DisjointSet, Edge>(
        () => new DisjointSet(width * height),
        (acc, e) => (acc.union(e[0], e[1]), acc)
    );

const walkableComponents = (
    edges: Iterable<Edge>,
    width: number,
    height: number
) =>
    [
        ...reduce(unify(width, height), edges)
            .subsets()
            .values()
    ].sort((a, b) => b.length - a.length);

///////////////////// full terrain generation

const generateWalkable = (opts: GenerationOpts) =>
    transduce<number, any, any>(
        comp(
            trace("generation #"),
            map(() => computeCA(opts)),
            multiplexObj({
                raw: map(identity),
                comps: map((raw) =>
                    walkableComponents(
                        walkableEdges(raw, opts.width, opts.height),
                        opts.width,
                        opts.height
                    )
                )
            }),
            matchFirst(
                ({ raw, comps }) => comps[0].length / raw.length >= opts.thresh
            )
        ),
        last(),
        range(opts.maxTrials)
    );

const wrappedIndex = (x: number, y: number, width: number, height: number) =>
    wrap(y, 0, height) * width + wrap(x, 0, width);

///////////////////// main example & SVG output

const width = 64;
const height = 32;
const scale = 32;
const labelOffset = [scale * 0.5, scale * 0.5];
const gradient = GRADIENTS["orange-blue"];

const { raw } = generateWalkable({
    width,
    height,
    thresh: 1 / 3,
    rnd: new Smush32(0xc377babf)
});

const regions = walkableComponents(
    walkableEdges(raw, width, height),
    width,
    height
);

const elevation = computeElevation(raw, width, height);

const tonemap = (x: number) =>
    cosineColor(gradient, fitClamped(x, -5, 5, 1, 0));

const cellLabel = (id: number) =>
    elevation[id] < 0
        ? String.fromCharCode(
              0x41 +
                  matchFirst(
                      (r: number) => regions[r].includes(id),
                      range(regions.length)
                  )
          )
        : String(elevation[id]);

const sdfCell = (i: number, pos: number[]) => [
    rect(pos, scale - 2, scale - 2, { fill: tonemap(elevation[i]) }),
    text(add2([], pos, labelOffset), cellLabel(i), {
        fill: "#000",
        "alignment-baseline": "middle"
    })
];

// define SVG document in hiccup format
const doc = svg(
    {
        width: width * scale,
        height: height * scale,
        "text-anchor": "middle",
        "font-family": "Menlo, monospace",
        "font-size": "24px"
    },
    mapIndexed(
        sdfCell,
        range2d(0, width * scale, 0, height * scale, scale, scale)
    )
);

writeFileSync("ca-sdf.svg", serialize(doc));