nx_poisson_disk.nx

nx_poisson_disk.nx -- Bridson 2007 fast Poisson disk sampling. LAYER 2 of the procgen substrate (Perlin = layer 1). Genuinely modern algorithm (2007), patent-clean, O(N). Used by Townscaper- class procedural tools for building placement, Houdini's scatter SOP for prop distribution, agent-spawn placement in zombie-escape city games -- anywhere "looks random AND evenly spaced AND fast" matters more than uniform random scattering (which clumps). Honest deviation note vs canonical Bridson paper (PDF was not directly readable; spec verified from training data; v1 caveat): 1. Initial seed point: RANDOM (fixed in v1.1 -- previously center). 2. Annulus sample radius: drawn LINEARLY in [r, 2r] rather than area-uniform (canonical r' = sqrt(uniform * (4r^2 - r^2) + r^2) requires sqrt; queued for follow-up once nx_sqrt_q10 ships). Substrate still satisfies the min-distance invariant; the bias is a slight inner-ring density skew, not a correctness bug. Algorithm (Bridson 2007 SIGGRAPH sketch): 1. Background grid with cell size r / sqrt(n_dim). Each cell can hold at most one point (because two points within one cell would be < r apart). 2. Start: place one seed point, mark it active. 3. Loop while active non-empty: Pick random active point p. Try k = 30 candidates at distance [r, 2r] from p. For each candidate: - Check in-bounds. - Check no existing point within r (grid neighbors only -- this is what makes Bridson O(N)). - If valid, add point + mark active; break. If all 30 fail, remove p from active. 4. Return collected points. Why this beats Perlin-grid-scatter for city gen: Perlin scatter has clumping (high-noise spots get many points; low-noise spots none). Poisson disk guarantees minimum distance r AND fills space uniformly -- exactly what zombie-spawn / building-plot placement requires. Cross-modal: also gives n-gram-diverse sample selection from a