growth.js
224 lines · in natura-src-1.0.0.zip as natura/growth.js · a module · its entry in the module reference · its test: growth-test.js
// growth.js -- procedural BRANCHING GROWTH: grow a whole form from one seed by a recursive branch rule. Render-free
// and deterministic (all randomness drawn from a seeded rng, never Math.random). UNIVERSAL -- the same rule grows a
// tree, a river network, a lung, a lightning bolt, a root, a blood vessel, a coral: one seed, one branch rule, a
// whole branching form. Single concern: the TOPOLOGY of branching (a graph of segments + tips), NOT how it is drawn
// or unfurled over time -- a renderer reveals it, a sim may grow on it. The per-FORM character (a spire reaching
// vertical, a willow drooping, how many children a node throws) is supplied by the caller as strategies (bias +
// splits), so this stays one generator instead of one-per-tree-shape. Prototyped in "The Seed Dreaming Under Snow".
// Future members of this module (same branch-graph output): space-colonization (grow toward attractors) and
// differential-growth (a relaxing filament). UMD (node / window.Growth).
(function (root, factory) {
if (typeof module !== 'undefined' && module.exports) module.exports = factory();
else root.Growth = factory();
})(typeof self !== 'undefined' ? self : this, function () {
'use strict';
const TAU = Math.PI * 2;
// branch(rng, opts) -> { segments, nodes, tips, leaves }
// rng() -> [0,1) seeded generator (deterministic: same seed -> same form).
// opts (all optional):
// x0,y0 seed position (default 0,0)
// angle0 initial growth direction, radians (default -PI/2, i.e. "up" in screen coords)
// length0 trunk segment length (default 1)
// depthMax recursion depth -- the form's order (default 8)
// decay:[a,b] each child's length = parent * (a + rng()*b) (default [0.7,0.1] -> children ~0.7-0.8x)
// spread:[a,b] fork half-angle, radians, drawn per node (default [0.3,0.6])
// jitter uniform angle noise added per child, radians (default 0.28)
// minLength stop branching a segment shorter than this (default 0 = depth-limited only)
// maxSegments hard safety cap so recursion can never explode (default 4000)
// splits(depth,rng) -> child count for a node (default: always 2 -- a binary fork)
// bias(angle,depth,frac) -> adjusted angle; frac = depth/depthMax. The per-FORM steering hook
// (spire: pull tips toward vertical; willow: droop; default: none)
// width(depth) -> stroke width hint for the renderer (default: thick trunk -> thin tips)
function branch(rng, opts) {
opts = opts || {};
if (typeof rng !== 'function') throw new Error('growth.branch: rng must be a seeded function');
const x0 = num(opts.x0, 0), y0 = num(opts.y0, 0);
const angle0 = num(opts.angle0, -Math.PI / 2), length0 = num(opts.length0, 1);
const depthMax = num(opts.depthMax, 8);
const decay = opts.decay || [0.7, 0.1], spread = opts.spread || [0.3, 0.6];
const jitter = num(opts.jitter, 0.28), minLength = num(opts.minLength, 0);
const maxSegments = num(opts.maxSegments, 4000);
const splits = opts.splits || (() => 2);
const bias = opts.bias || null;
const trop = opts.tropism || null; // {x,y,strength}: a growth-bending FIELD -- up=light, down=gravity, sideways=wind
const thickenByFlow = !!opts.thickenByFlow; // true: trunk width from subtree FEED (Murray's law), not raw depth
const widthOf = opts.width || (d => Math.max(0.7, (depthMax - d) * 0.85 + 0.7));
const segments = [], nodes = [], leaves = [], segNode = [];
function rec(x, y, ang, len, depth, parent) {
if (segments.length >= maxSegments) return;
const x1 = x + Math.cos(ang) * len, y1 = y + Math.sin(ang) * len, ni = nodes.length;
segments.push({ x0: x, y0: y, x1: x1, y1: y1, depth: depth, width: widthOf(depth) }); segNode.push(ni);
nodes.push({ x: x1, y: y1, depth: depth, ang: ang, parent: parent });
if (depth >= depthMax || len <= minLength) { leaves.push({ x: x1, y: y1, depth: depth }); return; }
const n = Math.max(1, splits(depth, rng) | 0);
const sp = spread[0] + rng() * (spread[1] - spread[0]);
for (let i = 0; i < n; i++) {
const f = n === 1 ? 0 : (i / (n - 1) - 0.5); // spread children symmetrically about the parent angle
let na = ang + f * sp * 2 + (rng() - 0.5) * jitter;
if (bias) na = bias(na, depth, depthMax > 0 ? depth / depthMax : 0);
if (trop && trop.strength) { const cx = Math.cos(na) + trop.x * trop.strength, cy = Math.sin(na) + trop.y * trop.strength; na = Math.atan2(cy, cx); } // bend toward the field each step -> distal branches curve
rec(x1, y1, na, len * (decay[0] + rng() * decay[1]), depth + 1, ni);
}
}
rec(x0, y0, angle0, length0, 0, -1);
if (thickenByFlow) { // Murray-ish: every tip feeds one unit of flow down to the root
const flow = new Array(nodes.length).fill(0);
for (let i = nodes.length - 1; i >= 0; i--) { flow[i] += 1; const p = nodes[i].parent; if (p >= 0) flow[p] += flow[i]; }
const fw = opts.flowWidth || (v => 0.6 + 0.9 * Math.sqrt(v));
for (let k = 0; k < segments.length; k++) segments[k].width = fw(flow[segNode[k]]);
}
return { segments: segments, nodes: nodes, leaves: leaves, tips: leaves };
}
// FORMS: ready-made bias strategies for common tree characters (pass as opts.bias). Universal knobs, not hardcoded.
const FORMS = {
// a spire/conifer: tips increasingly reach toward vertical (up) with depth
spire: (up) => (ang, depth, frac) => ang + (( (up != null ? up : -Math.PI / 2) - ang) * 0.5 * frac),
// a willow: tips increasingly droop toward down with depth (steeper near the tips via frac^1.4)
willow: (down) => (ang, depth, frac) => ang + (((down != null ? down : Math.PI / 2) - ang) * 0.6 * Math.pow(frac, 1.4)),
// a plain fork: no steering (the natural spread + jitter only)
open: () => (ang) => ang,
};
// colonize(rng, opts) -> { segments, nodes } -- SPACE-COLONIZATION growth (Runions/Lindenmayer 2007): grow a
// network from a seed TOWARD a cloud of ATTRACTOR points, so the form fills a given SHAPE. Where branch() forks
// blindly, this reaches for something -- a crown filling its silhouette, roots seeking water, veins reaching a
// leaf margin, a bolt racing to a target. Same branch-graph output, and trunks THICKEN by how much they feed.
// opts:
// attractors:[{x,y}] the cloud/shape to fill (required; see Growth.cloud for ready-made shapes)
// x0,y0 seed/root (default: bottom-centre of the cloud, so a tree grows UP into it)
// step growth step per iteration (default: 3% of the cloud's span)
// influence an attractor pulls its single nearest node within this radius (default step*8)
// kill an attractor is consumed once a node comes this close (default step*2)
// jitter small angle noise on each growth step (default 0)
// maxIter,maxNodes safety caps (default 400 / 6000)
// width(flow) stroke width from a node's subtree feed-count (default: base + k*sqrt(flow))
function colonize(rng, opts) {
opts = opts || {};
if (typeof rng !== 'function') throw new Error('growth.colonize: rng must be a seeded function');
const atr = (opts.attractors || []).map(a => ({ x: a.x, y: a.y, dead: false }));
if (!atr.length) return { segments: [], nodes: [] };
let minx = Infinity, miny = Infinity, maxx = -Infinity, maxy = -Infinity;
for (const a of atr) { if (a.x < minx) minx = a.x; if (a.x > maxx) maxx = a.x; if (a.y < miny) miny = a.y; if (a.y > maxy) maxy = a.y; }
const span = Math.max(maxx - minx, maxy - miny) || 1;
const step = num(opts.step, span * 0.03);
const infl2 = Math.pow(num(opts.influence, step * 8), 2), kill2 = Math.pow(num(opts.kill, step * 2), 2);
const maxIter = num(opts.maxIter, 400), maxNodes = num(opts.maxNodes, 6000), jitter = num(opts.jitter, 0);
const widthOf = opts.width || (flow => 0.6 + 1.5 * Math.sqrt(flow));
const trop = opts.tropism || null; // {x,y,strength}: a field that ALSO bends growth (roots seek water AND sink)
const nodes = [{ x: num(opts.x0, (minx + maxx) / 2), y: num(opts.y0, maxy), parent: -1, depth: 0 }];
const segChild = [], segments = [];
let alive = atr.length, iter = 0;
while (alive > 0 && iter++ < maxIter && nodes.length < maxNodes) {
const pull = new Map(); // nodeIndex -> {dx,dy,n} accumulated attractor pull
for (const a of atr) {
if (a.dead) continue;
let best = -1, bd = infl2;
for (let i = 0; i < nodes.length; i++) { const dx = a.x - nodes[i].x, dy = a.y - nodes[i].y, d2 = dx * dx + dy * dy; if (d2 < bd) { bd = d2; best = i; } }
if (best >= 0) { const dx = a.x - nodes[best].x, dy = a.y - nodes[best].y, d = Math.sqrt(dx * dx + dy * dy) || 1;
const p = pull.get(best) || { dx: 0, dy: 0, n: 0 }; p.dx += dx / d; p.dy += dy / d; p.n++; pull.set(best, p); }
}
if (!pull.size) break; // nothing in reach -> the growth has stalled
for (const entry of pull) {
const ni = entry[0], p = entry[1]; let dx = p.dx / p.n, dy = p.dy / p.n; const m = Math.hypot(dx, dy) || 1; dx /= m; dy /= m;
if (trop && trop.strength) { dx += trop.x * trop.strength; dy += trop.y * trop.strength; const mm = Math.hypot(dx, dy) || 1; dx /= mm; dy /= mm; } // attractor pull + field bias
if (jitter) { const a = (rng() - 0.5) * jitter, c = Math.cos(a), s = Math.sin(a), nx = dx * c - dy * s, ny = dx * s + dy * c; dx = nx; dy = ny; }
const par = nodes[ni], x1 = par.x + dx * step, y1 = par.y + dy * step, idx = nodes.length;
nodes.push({ x: x1, y: y1, parent: ni, depth: par.depth + 1 });
segments.push({ x0: par.x, y0: par.y, x1: x1, y1: y1, depth: par.depth + 1, width: 1 }); segChild.push(idx);
}
for (const a of atr) { if (a.dead) continue; for (let i = 0; i < nodes.length; i++) { const dx = a.x - nodes[i].x, dy = a.y - nodes[i].y; if (dx * dx + dy * dy < kill2) { a.dead = true; alive--; break; } } }
}
// THICKNESS by feed: every tip sends one unit of flow down to the root (Murray-ish), so a trunk that feeds a
// whole crown is thick and a twig is thin. Nodes were appended in growth order, so a child's index > its parent's
// -> a reverse sweep accumulates children into parents in one pass.
const flow = new Array(nodes.length).fill(0);
for (let i = nodes.length - 1; i >= 0; i--) { flow[i] += 1; const par = nodes[i].parent; if (par >= 0) flow[par] += flow[i]; }
for (let k = 0; k < segments.length; k++) segments[k].width = widthOf(flow[segChild[k]]);
return { segments: segments, nodes: nodes };
}
// differentiate(rng, opts) -> { points, segments, closed } -- DIFFERENTIAL GROWTH: a chain that lengthens faster
// than its space, so it FOLDS. Each node is pulled toward its two neighbours (stay a smooth strand) and pushed off
// every nearby node (self-avoid), and the chain INSERTS nodes where it stretches (growth) -- so it convolutes to
// fill space. This is the FOLDING counterpart to the branching TREE that branch()/colonize() grow: brain coral,
// cortical folds, cactus ribs, an undulating membrane, the crinkle of a leaf margin, Rodin/Runions differential
// growth. Returns the ordered curve (points) + its edges (segments).
// opts:
// points | n+radius the seed strand (default: a small closed ring of n points, tiny jitter to break symmetry)
// closed a loop vs an open strand (default true)
// iterations growth steps (default 80)
// segLen target edge length; edges past ~1.6x split (that split IS the growth) (default: seed spacing)
// attract neighbour-smoothing pull (default 0.45)
// repel self-avoidance push (default 0.5)
// repelRadius self-avoid range (default segLen*2.4)
// maxPoints cap so it cannot run away (default 2400)
function differentiate(rng, opts) {
opts = opts || {};
if (typeof rng !== 'function') throw new Error('growth.differentiate: rng must be a seeded function');
const closed = opts.closed !== false, iterations = num(opts.iterations, 80);
const attract = num(opts.attract, 0.45), repel = num(opts.repel, 0.5), maxPoints = num(opts.maxPoints, 2400);
let pts;
if (opts.points && opts.points.length) pts = opts.points.map(p => ({ x: p.x, y: p.y }));
else { const n = num(opts.n, 26), R = num(opts.radius, 20); pts = []; for (let i = 0; i < n; i++) { const a = i / n * TAU; pts.push({ x: Math.cos(a) * R + (rng() - 0.5) * R * 0.03, y: Math.sin(a) * R + (rng() - 0.5) * R * 0.03 }); } }
let segLen = opts.segLen;
if (segLen == null) { let s = 0, c = 0; for (let i = 0; i < pts.length - (closed ? 0 : 1); i++) { const j = (i + 1) % pts.length; s += Math.hypot(pts[j].x - pts[i].x, pts[j].y - pts[i].y); c++; } segLen = c ? s / c : 1; }
const repelR = num(opts.repelRadius, segLen * 2.4), repelR2 = repelR * repelR;
const growthRate = num(opts.growthRate, 0.06), smooth = num(opts.smooth, 0.12);
for (let it = 0; it < iterations && pts.length < maxPoints; it++) {
const N = pts.length, mvx = new Array(N).fill(0), mvy = new Array(N).fill(0);
for (let i = 0; i < N; i++) {
const p = pts[i];
const a = pts[closed ? (i - 1 + N) % N : Math.max(0, i - 1)], b = pts[closed ? (i + 1) % N : Math.min(N - 1, i + 1)];
// rest-length SPRINGS to both neighbours (hold the spacing without collapsing the curve) + a touch of smoothing
for (let k = 0; k < 2; k++) { const q = k ? b : a, dx = q.x - p.x, dy = q.y - p.y, d = Math.hypot(dx, dy) || 1e-6, f = (d - segLen) / d * 0.5 * attract; mvx[i] += dx * f; mvy[i] += dy * f; }
mvx[i] += ((a.x + b.x) / 2 - p.x) * smooth; mvy[i] += ((a.y + b.y) / 2 - p.y) * smooth;
// self-avoidance: push off every nearby node
let rx = 0, ry = 0;
for (let j = 0; j < N; j++) { if (j === i) continue; const dx = p.x - pts[j].x, dy = p.y - pts[j].y, d2 = dx * dx + dy * dy; if (d2 > 1e-9 && d2 < repelR2) { const d = Math.sqrt(d2); rx += (dx / d) * (1 - d / repelR); ry += (dy / d) * (1 - d / repelR); } }
mvx[i] += rx * repel * segLen * 0.5; mvy[i] += ry * repel * segLen * 0.5;
}
for (let i = 0; i < N; i++) { pts[i].x += mvx[i]; pts[i].y += mvy[i]; }
// GROWTH at a steady rate: split the longest edges, so the perimeter outgrows its space and must FOLD to fit
const M = pts.length, nSplit = Math.max(1, Math.round(M * growthRate)), order = [];
for (let i = 0; i < M - (closed ? 0 : 1); i++) { const j = (i + 1) % M; order.push([i, (pts[j].x - pts[i].x) * (pts[j].x - pts[i].x) + (pts[j].y - pts[i].y) * (pts[j].y - pts[i].y)]); }
order.sort((u, v) => v[1] - u[1]);
const split = new Set(); for (let k = 0; k < nSplit && k < order.length; k++) split.add(order[k][0]);
const out = [];
for (let i = 0; i < M; i++) { out.push(pts[i]); if (split.has(i) && out.length < maxPoints) { const j = (i + 1) % M; out.push({ x: (pts[i].x + pts[j].x) / 2, y: (pts[i].y + pts[j].y) / 2 }); } }
pts = out;
}
const segments = [];
for (let i = 0; i < pts.length - (closed ? 0 : 1); i++) { const j = (i + 1) % pts.length; segments.push({ x0: pts[i].x, y0: pts[i].y, x1: pts[j].x, y1: pts[j].y, depth: 0, width: 1 }); }
return { points: pts, segments: segments, closed: closed };
}
// cloud: ready-made attractor SHAPES to hand colonize() -- the silhouette a form grows to fill. Deterministic (rng).
const cloud = {
disk: (rng, o) => { o = o || {}; const cx = num(o.cx, 0), cy = num(o.cy, 0), r = num(o.r, 1), n = num(o.n, 200); const out = []; for (let i = 0; i < n; i++) { const a = rng() * TAU, rr = r * Math.sqrt(rng()); out.push({ x: cx + Math.cos(a) * rr, y: cy + Math.sin(a) * rr }); } return out; },
rect: (rng, o) => { o = o || {}; const x = num(o.x, 0), y = num(o.y, 0), w = num(o.w, 1), h = num(o.h, 1), n = num(o.n, 200); const out = []; for (let i = 0; i < n; i++) out.push({ x: x + rng() * w, y: y + rng() * h }); return out; },
ring: (rng, o) => { o = o || {}; const cx = num(o.cx, 0), cy = num(o.cy, 0), r = num(o.r, 1), r0 = num(o.r0, r * 0.5), n = num(o.n, 200); const out = []; for (let i = 0; i < n; i++) { const a = rng() * TAU, rr = Math.sqrt(r0 * r0 + rng() * (r * r - r0 * r0)); out.push({ x: cx + Math.cos(a) * rr, y: cy + Math.sin(a) * rr }); } return out; },
// polygon: fill ANY silhouette -- rejection-sample n points inside the outline (a heart, a letter, a coastline).
// So colonize can grow a vein-network to fill a shape, not just a disk. points = [{x,y},...] (>=3, in order).
polygon: (rng, o) => {
o = o || {}; const pts = o.points || []; const n = num(o.n, 200); if (pts.length < 3) return [];
let minx = Infinity, miny = Infinity, maxx = -Infinity, maxy = -Infinity;
for (const p of pts) { if (p.x < minx) minx = p.x; if (p.x > maxx) maxx = p.x; if (p.y < miny) miny = p.y; if (p.y > maxy) maxy = p.y; }
const inside = (x, y) => { let c = false; for (let i = 0, j = pts.length - 1; i < pts.length; j = i++) { const xi = pts[i].x, yi = pts[i].y, xj = pts[j].x, yj = pts[j].y; if (((yi > y) !== (yj > y)) && (x < (xj - xi) * (y - yi) / (yj - yi) + xi)) c = !c; } return c; };
const out = []; let guard = 0; const cap = n * 80;
while (out.length < n && guard++ < cap) { const x = minx + rng() * (maxx - minx), y = miny + rng() * (maxy - miny); if (inside(x, y)) out.push({ x: x, y: y }); }
return out;
},
// leaf: a pointed-oval leaf silhouette (tip at top, widest below middle), for growing a real leaf VENATION network.
leaf: (rng, o) => {
o = o || {}; const cx = num(o.cx, 0), cy = num(o.cy, 0), w = num(o.w, 20), h = num(o.h, 60), n = num(o.n, 200); const out = [];
for (let i = 0; i < n; i++) { const t = rng(); const half = w * Math.pow(Math.sin(Math.PI * t), 0.7); out.push({ x: cx + (rng() * 2 - 1) * half, y: cy - h / 2 + t * h }); } // t: base(0)->tip(1) along the midrib; half-width widest mid-low
return out;
},
};
function num(v, d) { return v != null ? v : d; }
return { branch: branch, colonize: colonize, differentiate: differentiate, cloud: cloud, FORMS: FORMS, TAU: TAU };
});