spatial hashing vs quadtrees for 2D broad-phase collision — which actually wins at scale?

Runtime profiling is the right call. One thing I'd add: optimal cell size can shift a lot depending on game state. Sparse early encounters and dense chokepoints are just different workloads. I ended up doing a slow rolling check every few seconds and snapping between three preset cell sizes based on measured entity distribution. Not something I'd recommend for every project, but if your entity density varies a lot across phases it pays off. Got about a 15% improvement in the densest scenario versus a fixed size tuned for average conditions.

Do you actually switch cell sizes at runtime, or profile during development and pick a fixed one? Genuinely curious, because switching mid-session means rebuilding the entire hash structure, and that rebuild is most expensive exactly when you least want a hitch (dense chokepoint, lots of occupied cells).

I ended up sidestepping the tuning problem differently: two parallel grids at different granularities. Projectiles go in the fine grid, large enemies in the coarse one. Query only the grid appropriate for each entity type. Probably more memory than necessary, but it killed the "what's the right cell size" question entirely and both grids stay fast for their specific workloads.

the clustering mitigation i use: don't iterate the whole grid. keep a separate set of which cells are actually occupied this frame and only touch those. when entities cluster you skip empty cells entirely and cache pressure drops fast. the overhead of maintaining the occupied-cell set is basically nothing compared to what you save when half your entities are stacked in one corner of the map.

for really tight clustering you can also bias your cell size slightly larger than optimal for the average-case and accept a few extra narrow-phase checks. the improved cache locality on the populated cells tends to more than pay for it.

I stopped trying to calculate the right cell size upfront and just profiled it at runtime. Same stress scenario, three cell sizes, 1x, 2x, 3x median entity radius, timed the broad phase each time. The sweet spot was obvious in about ten minutes. 2x median held in my case too, but when I had a real mix of tiny projectiles and large enemies I ended up running two separate grids rather than hunting for a single size that worked for both. Trying to fit wildly different entity scales into one grid is where the math stops cooperating and you're just guessing anyway.

I profile during development and ship with a fixed size. Rebuilding the entire hash structure mid-session, especially during a dense combat scenario when you actually need the broad phase working well, is almost always a worse tradeoff than whatever suboptimality you were trying to correct. My process: pick two or three representative scenarios (sparse exploration, peak entity density, worst-case encounter), try a handful of cell sizes, and commit to whatever performs best under the worst case. In practice the gap between a good cell size and a theoretically perfect one is maybe 5–10% at scale, and that doesn't justify the rebuild overhead or the extra code path to manage.

how did you actually land on the right cell size? that's the part that always trips me up. in theory it should be somewhere around 2x your largest entity's bounding radius, but when entity sizes vary a lot (tiny projectiles vs large enemies) any single value feels like a compromise. did you just benchmark a range and pick the winner, or is there a more principled way to approach it?