How Matter.js Grid Broad-Phase Algorithm Works

In 2D physics engines, collision detection is divided into broad-phase and narrow-phase stages to maintain performance. This article explains how the grid-based broad-phase collision detection algorithm functions in Matter.js, breaking down how it partitions 2D space, assigns object bounding boxes to uniform cells, removes duplicate pairs, and optimizes processing before passing potential collisions to the narrow-phase solver.

The Purpose of Broad-Phase Detection

Directly testing every body against every other body using narrow-phase algorithms (such as the Separating Axis Theorem) results in an \(O(N^2)\) time complexity, which rapidly degrades frame rates as object counts grow. The broad-phase algorithm acts as an early culling filter. Its sole responsibility is to quickly discard pairs of objects that are too far apart to possibly collide, forwarding only a small list of candidate pairs to the narrow-phase.

Spatial Partitioning via Uniform Grids

Matter.js implements broad-phase collision detection using a spatial hash grid (Matter.Grid). The 2D world coordinate space is mathematically sliced into a uniform matrix of rectangular cells, or "buckets."

Each cell has a predefined width and height. Instead of storing exact geometric boundaries, the grid only tracks the presence of bodies within these spatial regions.

Step-by-Step Execution of the Grid Algorithm

1. Bounding Box Calculation (AABB)

Before interacting with the grid, Matter.js calculates an Axis-Aligned Bounding Box (AABB) for every active physics body. An AABB is a non-rotated rectangle defined simply by minimum and maximum coordinates: (min.x, min.y) and (max.x, max.y).

2. Cell Key Mapping

Using the AABB coordinates and the configured cell dimensions, the algorithm determines which grid coordinates the body spans:

• startCol = floor(aabb.min.x / cellWidth)
• endCol = floor(aabb.max.x / cellWidth)
• startRow = floor(aabb.min.y / cellHeight)
• endRow = floor(aabb.max.y / cellHeight)

3. Bucket Insertion

Matter.js iterates through the computed column and row ranges. The body reference is placed into the corresponding grid cells. If a body is small, it might reside in a single cell; if it is large or overlaps a boundary, it is inserted into multiple adjacent cells.

4. Pair Generation and Deduplication

Once all bodies are mapped to their respective cells, the engine iterates through each occupied cell to generate collision pairs:

• Objects that do not share at least one cell are immediately ignored.
• For objects sharing a cell, a collision pair is registered.
• Because a large body overlapping multiple cells might encounter the same neighbor across several adjacent buckets, Matter.js generates a unique identifier for each pair (typically combining the body IDs, e.g., idA_idB). A hash map or set tracks generated pairs, ensuring that duplicate checks are skipped.

5. Transition to Narrow-Phase

Once the grid traversal completes, the resulting unique set of candidate pairs is handed off to the narrow-phase algorithm. The narrow-phase then performs exact vertex, edge, and SAT calculations on this drastically reduced subset.

Dynamic Grid Updates

At each engine update step (tick):

• Bodies that have moved or rotated have their AABBs recalculated.
• The grid removes references to bodies from their previous cells and registers them in their new coordinates.
• Sleeping or static bodies remain indexed in their existing cells without incurring recalculation costs until an external force or collision wakes them.

Strengths and Limitations

• Strengths: The uniform grid runs in near \(O(N)\) time when bodies are uniformly distributed and similar in size to the grid cells. Adding and removing bodies is computationally inexpensive compared to rebalancing tree structures.
• Limitations: If bodies vary wildly in size, tuning cell dimensions becomes difficult. Cells that are too large contain too many bodies (degrading back toward \(O(N^2)\)), while cells that are too small force large bodies to register across dozens of cells, increasing memory usage and deduplication overhead.