How Matter.Grid Uses Spatial Hashing in Matter.js

This article explains how the Matter.Grid module in Matter.js uses spatial hashing to accelerate broad-phase collision detection. By partitioning 2D space into uniform grid cells (hash buckets), the physics engine maps rigid bodies to localized spatial regions based on their axis-aligned bounding boxes (AABBs). This approach drastically minimizes the number of pairwise checks required per frame, reducing the computational complexity from a brute-force \(O(n^2)\) down to roughly \(O(n)\) in typical simulations.

The Role of Broad-Phase Detection

Physics engines divide collision detection into two primary stages: broad-phase and narrow-phase.

The narrow-phase performs precise geometric calculations (such as the Separating Axis Theorem) to determine exact points of contact, penetration depth, and collision normals. Because these calculations are computationally expensive, testing every body against every other body in a scene with \(n\) objects requires \(\frac{n(n - 1)}{2}\) operations.

The broad-phase eliminates impossible collisions early by quickly identifying which bodies are close enough to warrant narrow-phase evaluation. Matter.Grid provides this optimization through spatial partitioning.

Subdividing Space into Uniform Cells

Matter.Grid divides the continuous 2D coordinate plane into a discrete, uniform grid. The grid configuration relies on two parameters:

• bucketWidth: The horizontal size of each grid cell.
• bucketHeight: The vertical size of each grid cell.

Instead of maintaining a massive two-dimensional array representing the entire infinite coordinate space, Matter.Grid uses a hash map (an object or dictionary) where keys represent active grid coordinates, and values are arrays (buckets) containing references to the bodies residing within those coordinates.

Mapping Bodies to Hash Buckets

During each update cycle, Matter.Grid updates the spatial mapping of all active bodies through the following steps:

1. AABB Extraction: The engine takes the axis-aligned bounding box (AABB) of each body, defined by minimum and maximum bounds: (min.x, min.y) and (max.x, max.y).
2. Cell Coordinate Computation: The engine determines the range of grid indices covered by the body's AABB by performing integer division on the bounds:
   • startCol = Math.floor(bounds.min.x / bucketWidth)
   • endCol = Math.floor(bounds.max.x / bucketWidth)
   • startRow = Math.floor(bounds.min.y / bucketHeight)
   • endRow = Math.floor(bounds.max.y / bucketHeight)
3. Hash Key Generation: For every cell intersecting the body's AABB from startCol to endCol and startRow to endRow, a string-based hash key is generated (e.g., "C" + col + "R" + row).
4. Bucket Insertion: The body reference is pushed into the bucket associated with each generated key. If an object spans the boundary between cells, it is inserted into multiple buckets simultaneously.

Generating Potential Collision Pairs

Once all active bodies are registered into their respective buckets, the grid generates candidate collision pairs:

1. Iterating Active Buckets: The engine loops through only the buckets that contain two or more bodies. Completely empty buckets or buckets with a single object are skipped immediately.
2. Local Pairwise Checks: Within each multi-body bucket, the engine pairs the bodies together for broad-phase verification.
3. Duplicate Elimination: Because a single body can overlap multiple grid cells, the same pair of bodies might appear in multiple buckets. Matter.Grid prevents redundant checks by assigning each potential pair a unique identifier (derived from their individual IDs, such as bodyA.id < bodyB.id ? bodyA.id + '_' + bodyB.id : bodyB.id + '_' + bodyA.id) and tracking processed pairs in an active table.

The resulting deduplicated list of candidate pairs is then forwarded directly to the narrow-phase pipeline for exact collision resolution.

Performance Tuning and Bucket Size

The efficiency of Matter.Grid depends heavily on the chosen bucket dimensions relative to the scale of the objects in the world:

• Buckets Too Small: If the cell size is significantly smaller than average bodies, each body will span a large number of buckets. This increases memory overhead, hashing time, and duplicate pair resolution costs.
• Buckets Too Large: If the cell size is too large, too many bodies cluster into the same bucket. In extreme cases, this degrades performance back toward the unoptimized \(O(n^2)\) state.

For optimal performance, bucketWidth and bucketHeight are typically configured to be roughly 1.5 to 2 times the size of the average rigid body in the simulation.