#0014 · 2026-08-08 · accepted · physics

Cap max_entities rather than build broad-phase collision culling

performancecollisionpegame-loop

Context

development-plan.md section 8 explicitly deferred broad-phase collision culling until O(n^2) pairwise collision checks are demonstrably the actual bottleneck, not speculatively. glemy/game.gleam's click-to-spawn (decision 0010) has no limit on how many entities a sustained click-and-hold can add -- one per completed simulation tick, for as long as the mouse stays down. Investigated whether ordinary use (holding the mouse for several seconds, not an adversarial stress test) actually reaches that trigger condition.

Options considered

Do nothing (leave spawning unbounded, matches original click-to-spawn design) — rejected: Measured directly using tools/browser_check.ts's harness, extended to hold the mouse for 12s and count real simulation ticks (via monkey-patching CanvasRenderingContext2D.putImageData, called exactly once per completed pe.tick+render cycle): entity count grows past 500-700 within 12 seconds of ordinary held-click interaction, and simulation tick rate measurably degrades roughly 3x (from ~94-100 ticks/sec down to ~29-34 ticks/sec) over that time. This is a real, easily user-reachable robustness gap in the shipped demo, not a hypothetical.
Assume render's per-entity GPU buffer/bind-group allocation (render_ffi.mjs creates 2 new uniform buffers + 1 bind group per entity, every frame, no pooling) is the bottleneck, optimize that instead — rejected: Tested directly, not assumed: temporarily capped render_ffi.mjs's draw loop to the first 1 and first 20 entities (editing only the built .mjs copy, restored from source afterward -- no source change) while leaving pe's entity count and collision sweep untouched. Total ticks over the same 12s window barely changed (601 uncapped-render vs 701-711 with render capped to 1-20 draws), and the same degradation curve persisted. This rules out render's per-entity allocation as the dominant cost and points at pe's O(n^2) collision sweep (`resolve_all_collisions`/`resolve_against_rest` in pe.gleam) instead.
Implement broad-phase collision culling (spatial hash/grid) now, per development-plan.md section 8's original plan for when O(n^2) becomes a real bottleneck — rejected: The trigger condition (O(n^2) collision genuinely being the bottleneck) is met, but only because of unbounded spawning in a demo scene with no real game design driving actual entity-count requirements yet. Building spatial-partitioning infrastructure now would be designing for a hypothetical (what entity counts will the eventual game actually need?) rather than the concretely observed problem (a demo feature has no cap). Revisit if/when a real game design needs sustained large entity counts by choice, not as a side effect of one input handler having no limit.
Cap pe.tick's click-to-spawn at a fixed max_entities, leave collision O(n^2) — chosen: Directly fixes the measured problem at its actual source (unbounded spawning), is a 2-line change in the exact layer (`pe.tick`) that already owns the click-to-spawn policy, and is self-consistently correct against the roadmap's own gate: with entity count bounded at 150, O(n^2) collision is no longer, and cannot become, the bottleneck -- so broad-phase remains correctly deferred, not built speculatively. 150 was chosen from the measured curve (rate stayed near its unthrottled ceiling through roughly the first 100-150 spawned entities before visible degradation began).

Decision

Added pe.max_entities (150) and changed pe.tick to silently skip spawning (but still run the rest of the physics step normally) once model.entities is already at or above that count. update/resolve_all_collisions/collision.resolve are unchanged -- still O(n^2), now just always operating on a bounded n.

Verification

Re-ran the exact same 12-second held-click measurement after the fix: simulation tick rate held steady at 57-61 ticks/sec for the full 12 seconds (no degradation), versus 94-to-29 ticks/sec (decaying) before. Total ticks over the window went up, not down (750 vs 601), despite -- because of -- no longer bogging down. Added two new unit tests (pe_test.gleam): spawning is silently dropped at exactly max_entities while the rest of tick's physics still runs normally on existing entities, and spawning still succeeds one entity below the cap. gleam test passes on both targets (84 Erlang / 108 JavaScript). tools/browser_check.ts (the committed real-browser regression check) still passes after the change.

Consequences