[geminigemino]

Yes, some parts are inherently O(n²) (mate finding, crowd density, predator/prey proximity, pathogen spread). Ecology needs pairwise relationships.

To keep it sane, I don’t do naive all-vs-all. I use:

Zone-based spatial indexing so most checks only run against local neighbors (roughly n/16 instead of n). Temporal caching of indices so they’re not rebuilt every tick. Statistical sampling for crowd density at high population (estimate from a fixed-size sample instead of full scans).

So in practice it’s closer to O(n² / k), with k ≈ 16–50 depending on zone layout and population. You still see spikes during blooms, but it’s usually 10–30× faster than naive pairwise checks.

[karmakurtisaani]

> Yes, some parts are inherently O(n²) (mate finding, crowd density, predator/prey proximity, pathogen spread). Ecology needs pairwise relationships.

You might be able to do a bit better for some of these, check this out https://en.wikipedia.org/wiki/N-body_simulation

Essentially the idea in some optimizations is to divide the space into cells, and so you can discard relations with elements in far away cells.

[senfiaj]

Could use quad trees, or similar bucketing. But I think he already stated that he tried to avoid the processing of long distance pairs. So probably he does some localized bucketing. Personally, I don't even fully understand what his simulation is doing. There are tradeoffs between accuracy / performance, depending on the specific problem. So hard to judge here.

[geminigemino]

Thanks for the feedback. There are some O(n²) components (mate finding, pathogen spread, proximity), but they’re mitigated with zone-based spatial hashing and throttling, so it’s not naive all-vs-all.

One big recent win was actually on the rendering side: I was rebuilding complex morphology geometry every frame for large organisms. I’ve added caching for that, which significantly reduced spikes during population blooms.

At very high populations the sim tick itself becomes the bottleneck, even for mostly O(n) logic per organism. When populations crash (which they usually do ecologically), performance recovers.

Quad trees / more adaptive structures are on my radar, but I’m trying to balance complexity vs predictability for now.