Choosing a Broad-Phase Structure for Dense Combat Scenes

A combat scene with bullets, enemies, pickups, and level geometry does not need every possible pair sent to narrow-phase collision tests. The useful question is not whether a grid or a tree is universally faster. It is which structure keeps the candidate workload observable for this scene's object distribution, movement, and query mix.

Start by separating broad phase from narrow phase. Broad phase proposes pairs or query candidates; narrow phase decides actual overlap, hit, or line-of-sight results. This boundary prevents a spatial index from being mistaken for a collision-accuracy guarantee.

Implementation

1. Build a repeatable combat sample: the same spawn pattern, projectile lifetime, enemy movement, and map geometry for every comparison.
2. Instrument the baseline before replacing it. Record active proxies, broad-phase update time, candidate pairs, narrow-phase time, and query visits.
3. Try a uniform spatial hash when objects are spread through predictable cells. Choose an initial cell size from representative interaction ranges, then profile both oversized cells (crowded buckets) and undersized cells (many cells per object).
4. Try a dynamic AABB tree when the workload is dominated by overlap, ray, or shape queries across unevenly distributed objects. Treat insertions, removals, proxy moves, and refits as part of the cost.
5. Keep one narrow-phase implementation while comparing indexes. Otherwise an apparent index win can really be a changed hit test.

For a grid, expose bucket occupancy and the number of candidate pairs emitted per frame. For a tree, expose proxy count, update operations, and query node and leaf visits. Box2D's dynamic-tree API is one concrete example of the latter measurements; a custom index can report equivalent counters.

Tradeoffs

A spatial hash is straightforward to rebuild and inspect, but its cell size couples directly to bucket occupancy and how many cells large objects touch. It works best as a measured choice, not a magic constant.

A dynamic AABB tree can reject entire groups before reaching leaves and supports query-oriented workloads, but motion and churn shift cost into tree maintenance. A tree is also more stateful to debug: stale proxies, incorrect bounds, or missed removals can produce both wasted work and missing candidates.

Use the structure with the better profile for the representative scene. Do not carry a result from deformable-mesh research or a specific physics library into a different game as a frame-time promise.

Failure modes

• Treating broad phase as final collision detection: candidates still require the appropriate narrow-phase test.
• Tuning only for a calm scene: a burst of projectiles or clustered enemies can turn a sparse-grid result into overloaded buckets.
• Rebuilding a tree or moving proxies without updating all affected bounds: queries can miss objects or visit excessive nodes.
• Comparing different scenes, hit shapes, or query counts: the measurement no longer isolates the spatial structure.
• Keeping only average timings: record high-percentile frames and peak candidate counts, because combat spikes are usually the design constraint.

Testing

Create a deterministic test scene with fixed random seeds and run it through the existing broad phase and the candidate replacement. Assert that both paths deliver the same accepted narrow-phase hits for a bounded set of frames.

Then capture a small table for idle, normal combat, and peak combat: active objects, broad-phase update time, candidate pairs, narrow-phase time, and query visits. Investigate a mismatch before optimizing it; missing candidates are a correctness defect, while surplus candidates are a performance signal.

Production considerations

Ship the counters behind the project's existing development telemetry or debug overlay, with sampling rather than per-object logs in busy builds. Keep the cell size or tree maintenance policy configurable in development builds so designers can validate representative encounters without a code rewrite.

Re-profile after changing projectile speed, enemy density, map streaming, collision layers, or query types. Those changes alter the workload that justified the original choice. The production goal is a diagnosable broad phase with known limits, not a permanent winner between two data structures.

Sources

• Teschner et al., Optimized Spatial Hashing for Collision Detection of Deformable Objects - supports the spatial-hash cell assignment and the need to measure cell size, table size, and hash collisions within that research scope.
• Erin Catto, Dynamic AABB Trees - supports BVH group rejection, dynamic-tree workloads, leaf insertion, and AABB refitting.
• Box2D Dynamic Tree documentation - supports the documented proxy operations, query forms, and node/leaf visit statistics.