In games, spatial partitioning systems are a very useful tool to have in one's toolbox. They can be used for many things, but the most common is a physics "broad phase" - a way of accelerating a collision system in the average case.

This article will give you a crash course in bucket grids - a simple, easily implemented spatial partitioning method - and talk about their benefits and drawbacks. There's also MIT Licensed example code and an interactive demo!

For the purposes of this article, we'll be looking at comparisons within a single group of entities, so everything can be expressed in terms of the size of that group, N. What we're looking for is all pairs of objects that might collide - it's the collision detection algorithm's job to sort out which ones actually do collide.

Stages of collision resolution - Objects to be collided, candidate pairs collected, collision detection, collision resolution. Bucket grids can help with the second step.

To see when and how partitioning can help, lets look at the simple case.

No Broad Phase

Without a broad phase, we just assume all pairs might collide. Because of the naivety of this algorithm, it is not normally implemented as a separate step; instead we just loop over all the objects, considering each possible candidate pair in turn.

for (i = 0; i < objects.length; i++)
{
    a = object[i]
    for (j = i+1; j < objects.length; j++)
    {
        b = object[j]
        if(objects_collide(a,b))
        {
            resolve_collision(a,b)
        }
    }
}

This algorithm's time complexity scales with the square of N, in the best and worst case. That's bad news for big numbers of objects!

However, for small numbers of objects (sometimes up to a few hundred, but you should measure!) this can be perfectly adequate, and the implementation is very simple. I can't stress this enough - for a small set of objects, there's no sure win for using a broad phase. Often you can get away with, or even be better off with the naive approach!

In the cases where you can't, you're going to want to adopt a broad phase before you get down to the nitty-gritty of actually comparing your objects (the "narrow phase"). That's where a bucket grid might come in handy.

Bucket Grid

In simple terms, we divide space into "buckets" of a fixed size in each dimension.

To perform our broad phase, we:

• Insert all of our objects into all buckets that they overlap
• Then only consider possible collisions for the set of pairs of objects that lie within the same bucket.

Broad Phase with a Bucket Grid - Insertion to all overlapped buckets, gathering pairs from shared buckets. Objects that do not share a bucket need not be considered for collision resolution. Objects that don't reside in any shared buckets aren't considered further at all.

The reduction in pairs considered in the pictured example is from 15 to 3. For larger groups, the total number of possible pairs is much higher (4950 for a group of 100, for example), as are the potential gains of using a bucket grid.

Example Javascript Implementation

View the demo here! MIT Licensed source, for those interested.

The demo runs update ticks at a (target) 100fps, and renders at 60fps. You can toggle the broadphase on and off, try different grid sizes, and increase/decrease the number of bodies being simulated. The trade-offs can be pretty clearly visualised by checking the pairs count, approximate load count, and noting drops in performance. Enjoy!

This demo has been fairly hastily prepared - please let me know if you encounter any issues!

Considerations

What about objects that overlap more than one of the same bucket?

Objects that lie on a bucket boundary will overlap up to four buckets. Really big objects might occupy more! There are two approaches here: the first is to just live with extra possible comparision and resolution steps, but the better option is usually to build up a set of pairs and then iterate that at the end.

Isn't that a fair bit of memory to be allocating each frame?

"Maybe" - if you're doing things transiently, and you have enormous levels and fairly small buckets, allocating everything ahead of time is probably an unreasonable amount of overhead. You can however lazily allocate buckets, so that unused space doesn't have overhead. A persistent structure can also help with this.

How far should the grid extend?

There are 3 sensible answers here: either extend across your entire level, use wrapping coordinates, or continue infinitely.

• If you know your level size, limiting it to that is very easy to do and lets you do some nifty fine-tuning.
• Wrapping coordinates around a fixed-size grid can be a good middle ground that doesn't require any clever indexing schemes. You'll get some erroneous pairs for objects that are exact multiples of your chosen grid size, so make sure your collision algorithm isn't fazed by that.
• An infinite grid requires lazy allocation and some cleverness, but it is possibly the most robust for large, unpredictably sized worlds. The example code contains an infinite grid representation.

Complexity

Space required scales with the total area of the grid, measured in buckets. With lazy allocation, the space used is the amount of occupied buckets, bounded by the total area of the grid.

Time required scales with the density of the objects. If all objects are in the same bucket, then we're back to the N-squared worst case, with a bunch of bonus overhead for inserting everything into the grid and gathering pairs! Nasty.

However, if objects are spread out (they usually are), the complexity is proportional to the sum of the square of the number of objects in each bucket. It is important to tune our bucket grid for our specific case, and to consider if (for some reason) we might have a heap of objects crammed into a single bucket, and how we might want to deal with that.

There is also constant time overhead proportional to the number of objects and the average number of buckets they occupy, as all of them must be inserted into the bucket grid before we can use it.

It's worth noting that for the case where all objects are overlapping, there's no correct algorithm that can reduce the complexity beyond the N-squared worst case, because the number of overlapping pairs is proportional to N-squared: N(N-1)/2 to be precise. Cheating is the only way to do better.

Hints

I suggest you keep your data structure completely transient (construct it as needed, then throw it away), at least in the beginning. This may seem counter-intuitive at first, but it simplifies the implementation immensely - and should allow retro-fitting into an existing system without much work. Once you've got the transient case working, if you want/need further optimisation, then go persistent.

A good starting place for your bucket size is some small multiple of your average object size, especially if you're using lazy allocation. In the best case, every object gets its own single bucket, there are no pairs, and no further comparisions are required. In reality, if you make your buckets too small, more objects end up on bucket borders (or spanning multiple buckets), which results in the algorithm wasting a lot of time inserting objects into buckets rather than finding collision pairs. If you make your buckets too big, you run the risk of your buckets filling up more, and pair-finding becoming very expensive again.

Areas for Extension and Experimentation

There are lots of ways to go beyond the structure presented above; here are some ideas to get you started.

• Multiple Groups: You can store multiple groups in the same bucket, and then query for possible collisions between specific populations. This is really handy for speeding up player-vs-powerup or bullet-vs-enemy testing.
• Non-Square Grids: This can help when your objects tend to be of a particular aspect ratio, or when a persistent force (eg gravity) undermines the separation of objects in a specific dimension.
• Persistent Structure: cut down the overhead of setting up your broadphase by having a long-lived structure and just clearing it out before use.
• Static objects: You know where they're going to be - insert them once and then keep them around. You don't need to compare them with each other either.
• Fully Persistent: You can further optimise your broadphase by modifying it only when things are created and deleted, or move around. The hard part is making all the book-keeping involved with that convenient and performant. Can definitely be a win if most objects don't move most of the time, but in my experience often not worth the headache.
• Robustness vs Correctness Tradeoffs (aka "Cheating"): there's an example in the demo (allowing duplicate pairs, to avoid checking if a pair has already been added), but there are many more possible tradeoffs that might be a win for your application. You can impose a hard limit on bucket size, limiting the number of collisions that are "allowed" per-area. You can update the broadphase only every N ticks, or N objects every tick. There's lots of wiggle room for cheating, depending on how correct you (don't) need your physics.
• Single-Bucket Objects: @MythrunaGame on twitter pointed out that for some applications (particularly with sparse persistent grids full of small objects), a good approach involves having objects exist in only one bucket, and checking neighbour buckets when traversing the grid. This is an alternative to inserting an object into all buckets that it overlaps; it limits your object size (can't be bigger than 2 grid cells) but simplifies the insertion stage and is found quite often in the wild.
• Non-Physical Applications: Broadphase and spatial locality aren't only important for physics calculations. You can also use grids to accelerate "objects in area" queries, to quickly approximate the density of objects (for eg pathfinding around crowds), quickly cull offscreen graphics, and even to determine which clients might need to recieve a given network packet. See if you can think of other applications for your new tool!

Further Reading

There are many other forms of spatial partitioning - I chose bucket grids because they are the simplest to implement and understand, and have a great bang to buck ratio! However, knowing about other partitioning schemes and broadphase implementations lets you pick the one most appropriate for your application.

Hopefully I'll find some time to collect proper references, but until then, here are some terms to search:

• Quad Trees (Oct Trees in 3D)
• Sweep and Prune
• Binary Space Partitioning

That's it!

Whew, that ended up kinda long!

If you'd like clarification on anything presented above, or just want to say hi, I'm @1bardesign on twitter. Thanks for reading!

This article was written for NotGDC, a not-conference organised by Ben Porter/@eigenbom. Check the page for more dev musings, advice and implementation notes!

Back to Index