Choosing the right broadphase for your game can have performance benefits.
Versions used below
2D collision detection primer
2D collision detection is typically broken down into two main steps: broadphase and narrowphase. Broadphase happens first in execution but its usefulness is more apparent after talking about narrowphase, so I’ll cover narrowphase first.
Narrowphase is where body vs body collision checks are done. This involves some fairly expensive math depending on what shapes the bodies have.
If there is a cheaper check to determine that two shapes definitely aren’t colliding, we can skip the narrowphase check and get a performance win.
The broadphase is where that cheaper check is done.
The broadphase determines what pairs could be colliding. The definition of could differs by implementation.
Various implementations scale better than others and some are best suited for certain arrangements of game objects. It’s easy to swap them out since they follow the same interface.
Simplified collision detection overview
Broadphase is cheap but imprecise. Narrowphase is precise but expensive.
Here’s how they work together:
- Start with a list of bodies. These are the physics objects in the game.
- Broadphase determines what pairs of bodies are worth a closer look. These pairs are passed on to narrowphase.
- Given pairs from step 2, narrowphase does body vs body collision checks.
- Apply physics and run game logic based on collisions.
Picking the right broadphase for a game is mostly about which one makes the physics engine run fastest.
Worlds have a profiling flag which is off by default. When enabled, p2 will record how long the previous step took in milliseconds.
A handler for World’s
postStep event is a good place to check
From here you can print, find average, find median, etc. Lower is better.
That’s a decent way to compare implementations. Here are the broadphase options that p2 has out of the box.
Broadphase implementations in p2
NaiveBroadphase is as simple as it gets. It considers every body to be a potential collider with every other body. This results in the maximum number of narrowphase checks (n2).
If your game is simple enough this may work the best because the overhead of the other broadphase implementations won’t be worth it.
Sweep and Prune
SAPBroadphase sorts bodies along an axis and then moves down that list finding pairs by looking at body size and position of the next bodies.
Control what axis to sort along by setting the
If game objects are spread out along the x axis, like in a sidescroller,
axisIndex = 0 would be better. If game objects are spread out along the y axis,
axisIndex = 1 is better.
This is the default broadphase in p2 (with
axisIndex = 0).
Note: As of version 0.7.0 GridBroadphase is no longer in p2.js
GridBroadphase divides space into a grid of cells. Bodies are placed into the cells they overlap and bodies in the same cell are paired.
GridBroadphase needs to know the size of the space ahead of time so the game must have predetermined bounds.
Cell width will be
(xmax - xmin) / nx and cell height will be
(ymax - ymin) / ny.
Ratio between cell size and the average size of game objects is important when trying to tune performance. I typically find that having cells 1-4 times the size of my game objects gives the best performance.
Every game is different so don’t take my word for it. Run benchmarks.
Another thing to tweak
When approximating a body’s size, the p2 broadphase implementations use a bounding shape which can be simpler than the body’s actual shape.
Maybe if your bodies are mostly circles
BOUNDING_CIRCLE performs better?
Rules I follow when selecting a broadphase are
- Start with the simplest broadphase and change it when it’s not performing well enough.
- Run benchmarks relevant to your game to compare broadphase implementations.