GPU-accelerated spatial hashing for collision broadphase

[obiot]

Summary

Explore GPU-based spatial hashing as an alternative to the current CPU-based QuadTree for collision broadphase detection. For games with thousands of entities, the QuadTree rebuild and query cost becomes a bottleneck. GPU compute shaders (via WebGPU) could parallelize spatial hashing and pair detection.

Current State

• `QuadTree` in `src/physics/quadtree.js` rebuilds every frame by inserting all non-kinematic entities
• `World.update()` calls `quadTree.insertContainer()` then queries for collision pairs
• CPU-bound: O(n log n) insert, O(n × k) query where k = average neighbors per cell
• Sufficient for typical 2D game entity counts (< 500) but limits large-scale simulations

Potential Approach

• Spatial hash grid: divide the world into fixed-size cells, assign each entity to cells based on its bounds
• GPU compute: use WebGPU compute shaders to sort entities into grid cells and detect overlapping pairs
• Readback: read collision pairs back to CPU for response (or keep on GPU if physics is also GPU-driven)
• Fallback: keep the existing QuadTree for WebGL/Canvas renderers or when entity count is below a threshold

Considerations

• WebGPU is not yet widely supported — this would be experimental/opt-in
• Readback latency (GPU → CPU) could negate gains unless physics response is also GPU-side
• May be overkill for most 2D games — best suited for bullet hell, particle physics, large crowds
• Could start with a CPU-side spatial hash grid as a first step (simpler than QuadTree, cache-friendlier)

References

• `QuadTree`: `src/physics/quadtree.js`
• `World.update()`: `src/physics/world.js`
• WebGPU compute shaders: https://gpuweb.github.io/gpuweb/#compute-pipeline