Physics Grid

Broadphase Collision Detection

I'm working on a flying game inspired by Pirates and Crimson Skies. One design goal for the game is to have a lot of things on screen. I want to avoid dead air and provide as many things to do moment to moment as possible. So I knew starting out on this game that I'd need to put some work into the physics of my game engine. Game design and programming, even engine programming, are entwined, and when you know the needs of your game you can steer the tech towards solving those particular problems.

So first things first: we need to detect collisions between rigid bodies. The naive approach is to simply compare every body against every other body. For N bodies this would result in (N * (N - 1)) / 2 tests. That number gets very big very quickly (in computer science this would use big-o notation to describe this as an O(N^2) algorithm). For just 1000 bodies (totally reasonable when you factor in projectiles and level geometry) that's 1000000 tests!

The goal is to somehow eliminate as many potential collisions as possible. This phase is often referred to as the "broadphase". A simple approach is to divide the world up using a grid. Then every frame you find out what cell a body is in, and then you only need to test it against other bodies in that cell. So what you do is keep track of a list of bodies in each cell, then loop over all the cells and run the collision tests.

One nice thing about this approach is the simplicity of the geometry. The cells are all uniformly sized boxes, and we can also use bounding boxes for each of our rigid bodies as a coarser level collision test. The idea is that a rigidbody might be any geometry (a sphere, capsule, mesh, etc), but in the initial test you can use a box, specifically an Axis Aligned Bounding Box. So before we know if two meshes intersect each other we just need to know if their boxes overlap. We can use this box representation when determing which cells are body is in.

struct BroadphaseData {
  RigidBodyHandle handleA;
  RigidBodyHandle handleB;
  AABB aabbA;
  AABB aabbB;
};
struct Cell {
   Array<BroadphaseData> bodies;
};
struct Grid {
   Array<Cell> cells;
};

Note that I'm not storing the bodies themselves, I'm storing an intermediate representation called Broadphase data. That's because I want the loop comparing bodies within a cell to be as fast as possible, so to avoid cache misses I only want to store the data that I need.

Now there's one problem with our approach as I've listed it: we assume that a body exists only in one cell. But as this image shows that's not always the case.

You don't want to check these against each other twice (it's work you don't need to do, and it can produce weird results when you are trying to resolve the same collision twice). So you want some way to know if a potential pair is unique or not. Again, the naive solution works but is unreasonable. We could just keep track of a list of pairs, and before doing any test search thru that list for a matching entry.

So we don't want to search thru a list, what if we just a bool for every potential pair. As we already saw there's a lot of potential pairs: (N * (N - 1)) / 2. That can be a lot of data. Above I suggested a reasonable 1000 rigidbodies which produces a million unique pairs. So if you stored as booleans that's a whole megabyte of data (this isn't a lot compared to many other types of data, but it can quickly get out of hand). But we don't really need a whole byte (the size of a bool) for each pair. We only need one bit. So we can use a bitfield to store each potential pair.

Bitfields

The idea of a bitfield is actually simple (tho the syntax can look a bit hairy). Let's say you have a single byte of data. Let's look at the values of that byte where only one of the bits is set to 1.

0000 0001 = 1
0000 0010 = 2
0000 0100 = 4
0000 1000 = 8
0001 0000 = 16
0010 0000 = 32
0100 0000 = 64
1000 0000 = 128

That gives us 8 unique values, exactly what we'd expect from a byte. We can use bit arithmetic to set these values. The "left shift operator" let's us take a value and shift the bits N places to the left. So if we take 1 and left shift it once we get

1 << 1 = 2
0000 0001 -> 0000 0010
Let's look at some other examples:
1 << 4 = 16
0000 0001 -> 0001 0000
1 << 7 = 128
0000 0001 -> 1000 0000

Now to set a bit we can take our value and do a bitwise-or. For example let's start with a bitfield of 0, then I want to set the first bit and the last bit.

uint8 bitfield = 0;
bitfield |= (1 << 1);
bitfield |= (1 << 7);
//Looking at the binary representation.
0000 0000 | 0000 0001 -> 0000 0001
0000 0001 | 1000 0000 -> 1000 0001

Now the only thing we need to know is how to check a certain bit. We can do a bitwise-and between our bitfield and the bit we want set; if we get back a non-zero value then we know that bit was set. Starting from our last example:

if (bitfield & (1 << 1) != 0) {
  // bit was set
}
1000 0001 & 0000 0001 -> 0000 0001

But we need a lot more than a byte obviously, so we can just store a buffer of integers (ints are a bit wasteful because if we have 33 bodies we need 2 32-bit integers, but this is not a concern). Now we have two steps to set a bit: find which element it is in the buffer, then find it's index relative to that. We compute it like this:

int32 bitIndex = ...;
int32 elementIndex = bitIndex / 32;
int32 relativeIndex = bitIndex % 32;
// I define some macros to simplify this process:
#define SetBit(bitfield, nth) (((bitfield)[nth / 32]) |= (1 << (nth % 32)))
#define ClearBit(bitfield, nth) (((bitfield)[nth / 32]) &= ~(1 << (nth % 32)))
#define TestBit(bitfield, nth) (((bitfield)[nth / 32]) & (1 << (nth % 32)))

Back to Cells

The question now is how to know which element in the bitfield represents the collision of a pair of bodies. We simply give each rigidbody a unique ID and use a freelist to make sure the IDs are stable. So now when performing the broadphase test I look at the IDs of the two bodies

int32 GetContactPairElementIndex(int32 aIndex, int32 bIndex) {
    int32 elementIndex = -1;
    if (aIndex != bIndex) {
        // bIndex must always be bigger, otherwise (bIndex - 1) would yield a negative result
        if (aIndex > bIndex) {
            int32 temp = aIndex;
            aIndex = bIndex;
            bIndex = temp;
        }
        int32 rowOffset = (bIndex - 1) * bIndex / 2;
        elementIndex = rowOffset + aIndex;
    }
    return elementIndex;
}

Now we know which cells are occupied and we know if a pair of bodies have already been tested. There's a problem tho: we have a lot of cells. The method described so far is pretty much what I've done in every 3D game I've worked on, but those games always took place in relatively small spaces, and had relatively few rigidbodies.

Well, if we have too many cells why not just make them bigger? Because then we'd reduce the amount of culling they do in the broadphase. There's a tension between making it smaller to maximally cull potential collisions and making it large to reduce data footprint. My grid had 80K cells, which is several megabytes of data! And even with that large data footprint my cells were very big (about 50 times the size of the player, so it's not culling as many pairs as it could be).

Given all this it was clearly better to make the cells implicit, I only need to store data for the cells that have a body in them. So every frame I iterate over the dynamic bodies and compute the "spatialID" of the cell they're in. I then look that up in a hashtable, if it doesn't exist I create a new cell along with an entry into the hashtable, and if it does I simply add the body into that cell's list.

We go from 80K cells to around 200 on a heavy frame.

For the static bodies I don't want to rebuild the list of cells for a couple reasons. 1) There are likely going to be many more static bodies than dynamic 2) static bodies can be much bigger, meaning they need to get inserted into many more cells, resulting in more AABB tests. So I just create the static grid when the level is loaded, and when running the broadphase for a given cell I look up the dynamic and the static version. Then I just compare all the bodies in the dynamic against themselves, and then against the static bodies.

In the narrowphase we actually test the real geometry of two shapes, and these checks can get expensive. So we also keep a bitfield of narrowphase tests and only run them again if there's been a certain amount of drift in the position. This likely doesn't matter in a flying game like this because things are not very often at rest, but I know from past experience that it can be helpful, and I assume I'll use this code in future games anyway.

As I was writing this I realized I made a funky decision, which felt clever at the time, but turns out to be totally uneccesary. But when I made that decision I felt like it illustrated a good design principle which I think still stands.

Originally I was building the broadphasePairMap every frame, since the number of dynamic bodies is constantly changing. So each frame I gave every piece of BroadphaseData its own ID, and then used that in the map (which did not need to be persistent between frames). However, as described above, I didn't want to insert the static bodies every frame, which means that I needed part of the ID range to remain stable between frames. This is as simple as just determining the maximum number of static bodies, and then using that as the starting point of the ID range when building up the cells for dynamic bodies. Which led me to this explication:

Picking a uniform size is often better than dynamically resizing. It allows you to make more assumptions. Often we think of assumptions as bad because they'll inevitably be proven false. But having a maximum number of rigidbodies is not an assumption that will ever be false because we will never have infinite RAM, so if you can leverage that assumption it adds a parameter to your design.