Area-based spatial queries

By Robin Dowling · 4 months ago

In the simulation, organisms need to know what's nearby: finding food, detecting threats, locating mates. Early on, I stored entity positions individually and queried them one by one. For an organism checking its surroundings within a distance of 3 positions, that meant iterating through roughly 7 positions. At distance 10, that became 49 positions. At distance 20, over 400 positions. The cost grew quadratically.

This worked fine during development, but it didn't scale. Checking many positions sequentially, especially with thousands of organisms doing this every tick, became a significant bottleneck.

The fix was to restructure how positions are stored. Instead of mapping every individual position to the entities occupying it, I grouped positions into 25×25 area buckets. Now, querying nearby entities means identifying which 1-4 area buckets overlap with the organism's observation range, then filtering by actual distance, essentially a simplified quad-tree.

The performance improvement was dramatic. Benchmarking showed queries became 10 to 113 times faster depending on observation distance. More importantly, query time became essentially constant—checking distance 3 takes the same time as checking distance 20, both hovering around 0.001 to 0.002 milliseconds.

The change was entirely internal to the state management layer. The API shifted slightly, queries now return entity-to-position mappings instead of simple entity sets. No breaking changes leaked out to the simulation logic.

With this in place, I can safely increase observation distance from 3 to 10 or even 20 without worrying about performance degradation. The simulation feels more reactive and spatially aware, without the cost.