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.
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.
> 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.