Preface

I wrote this article for a contest on http://www.ziggyware.com/ - I'm very happy with the results which ended up being an intro-to-beginner description of broadphase collision/interference detection. It skips over many possible rabbit holes and generally glazes over the more troublsome topics, but that is exactly the tone I intended to set with the Ziggyware audience. For the purposes of this Wiki, and the reader which might be more interested in the details, I provide the following notes:

Original: http://www.ziggyware.com/readarticle.php?article_id=128

Code

Notes

  • Your choice of language and hardware will always affect your implementation, my implementation would be much simpler in psuedo-code than it is in C# because of the optimizations I've added
  • The 'borders void' flag I mention might be better thought of as a Marker, which I've called it in my code
    • Marker flags prevent excess scanning of the delimiter array, and are a very good optimization
  • In my code I use 'ref' modifiers on value types and expose enumerators using the internal enumerator struct, but I also provide overloads without 'ref' and using IEnumerable<> instead; production code will almost always want to use the ref/non-boxed methods unless performance isn't a problem
  • I make some pretty basesless claims about using the C# enumerator pattern setting you up better for multi-core programming. Here are the caveats:
    • In my implementation, array sorting must still be done on one thread, oh well..
    • It also limits how you can work with bodies; they must be modified by one thread only, which means 2x narrowphase (once per colliding body)
    • Per my implementation, it's possible that a single-core machine is actually slower than other algorithms, a dual core is similar in speed, and beyond two cores you get significant speed due to parallelism (Xbox and future PCs)
    • It's still possible to run multiple threads on each core and get some speed benefits, so don't be misled by the above bullet point
    • I haven't posted my benchmarks yet; so the above is heresay until I can prove otherwise

Terms

I introduce a number of terms as I go without fully qualifying what I mean; thus re-reading the article might be needed. Here is a little more information about anything non-basic in the article:
  • Broadphase - aka Spatial partitioning; collision detection that is faster than it is accurate
  • Big-O Notation - A way of defining algorithm complexity, and therefore performance; Arranged from least to most complex: O(1), O(n), O(n^2), etc..
  • Heap - Storage place for reference objects in .NET; excessive use frowned upon in .NET code
  • Stack - Storage place for value types in .NET
  • Boxing - Refering to value types as objects; in .NET this causes garbage
  • Garbage - Old heap-based objects the .NET runtime must remove for you
  • Interference - A possible collision
  • Collision - When two bodies touch

Broadphase Collision Detection

By John Wells, 2007

What is broadphase collision detection?

Simply put, broadphase collision detection is a method of eliminating costly collision tests, avoid redundant tests, and just not testing most of your objects anyways.

"Rubbish!", you say, "How can you determine to objects are not colliding if you never test them together?"

Good question. Well, it turns out the easiest way to figure to out something is not colliding is to create a situation where you know, that the object (and potentially 1000s of others) could never collide with something in the first place!

Can I make Grand Theft Halo 2 with it?

Well, sort of. The broadphase method is just a part of the puzzle; but an enabler of complex games? Sure. The classic problem arises where in making a game; you have two objects, a player and the ground. Testing them for collision becomes easy, and you can use the results to render properly, do physics, or play sound effects. After a while, you've added barrels, trees, and goblins to your game and suddenly testing each object against each other object is getting very difficult.

Big O notation would describe this as an O(n²) problem, which means as your game grows, the performance is dropping exponentially because of all the collision checks. We need to find a method to drop this O notation to a much more linear (or better) performance curve. We may never get to O(1) performance, but with even mildly complex games, we'll certainly have to do something if we want any amount of detail.

Spatial partitioning

Broadphase collision detection is accomplished through a spatial partitioning algorithm, of which there are many known varieties. The two main branches of widely used algorithms either form some sort of grid or bucket system, or use a sorting algorithm. As with any algorithmic choice, no answer is one-size fits all, and there are several pluses and minuses to each method. For my purposes, I need an algorithm that has the following features:
  • Creates no heap-based objects during runtime (The 360 hates that!)
  • Can take advantage of multiple processors/cores
  • Runs quickly, but does not take long to add/remove objects
  • Does not limit the world size and works with disparate sized objects

Sort-and-Sweep

Of course no such algorithm exists, but for my purposes, the best choice was a sort-and-sweep algorithm. Also known as sweep-and-prune, this is considered by many to be the naive algorithm to implement, but it can still be very effective when used properly. The idea behind any spatial sorting algorithm is to break the problem of interference detection into a 'greater than' or 'less than' or 'equal to' problem. Implementing this algorithm with a simple array and an IComparer<> instance is actually quite easy and should scale well to many types of games you might think would be unfit for a '1D' implementation. For instance, Grand Theft Halo 2 would be a good candidate, as would any 2D-Platformer, because the action in these games generally takes place on one or two axes. A space shooter, where objects exist (bountifully) on three axes would not be a great choice for this algorithm.

Although it's not intuitive, follow me on this one. To implement this algorithm, take every object in your world, consider where they begin and end on one arbitrary axis, and sort that list. Say we're sorting on the X axis; objects with a bounding box minimum value of 8 sort before an object with a bounding box minimum of 15. We've effectively broken a 3D problem down to 1D - the interesting thing is that as long as your objects are not highly clustered, performance can be amazing.

Delimiters

When breaking the 3D problem down to 1D, we need to keep track of only two things in our array, for each object: where it starts on that axis, and where it ends. Consider the following structure used to represent a delimiter:
struct Delimiter
{
    public BoundaryType Boundary;
    public MyGameObject Body;
}

enum BoundaryType
{
    Begin, End
}

class MyGameObject
{
    public BoundingBox Bounds;
        
    //... health, status, etc ...
}


So, for a moment, consider a 1D array, and imagine putting delimiters from every object in our game into the array, and then sorting that array. The only thing we need to ensure is that the 'Body' value has some sort of bounding volume such as an XNA BoundingBox or BoundingSphere. Suddenly, our world can be enumerated in 1D fashion, and in a bit I'll show you how finding objects can be optimized for speed.

Delimiter Comparison

The heart of a sorting algorithm is the comparer, and luckily the .NET Framework already has a standard pattern that will work fine for our needs, plus, by implementing a generic IComparer<Delimiter> class, we get loads of built-in functionality from the System.Array class static methods. Consider the following comparer, which for the purposes of example only compares on the X axis:

class DelimiterComparer : IComparer<Delimiter>
{
    public int Compare(Delimiter a, Delimiter b)
    {
        if  (a.Boundary == BoundaryType.Begin && b.Boundary == BoundaryType.Begin)
            return a.Body.Bounds.Min.X.CompareTo(b.Body.Bounds.Min.X);
        else if (a.Boundary == BoundaryType.Begin && b.Boundary == BoundaryType.End)
            return a.Body.Bounds.Min.X.CompareTo(b.Body.Bounds.Max.X);
        else if (a.Boundary == BoundaryType.End && b.Boundary == BoundaryType.Begin)
            return a.Body.Bounds.Max.X.CompareTo(b.Body.Bounds.Min.X);
        else
            return a.Body.Bounds.Max.X.CompareTo(b.Body.Bounds.Max.X);
    }
}


"Oh gosh," you say, "You've lost me!" Okay, lets try pictures; this concept sounds simple but can get confusing quickly without some visual aid. Consider a small collection of objects, now figure we've scattered them about our world and are arranging them based upon their X axis values only. In the picture below, I've labeled the 'Begin' (as '<') and 'End' (as '>') of the objects near the axis. Note that the Y and Z axis arrangement of these objects isn't shown below, in fact, the entire point is that at this point we don't care.
Objects.jpg

Now consider taking the objects above, and sorting them into our array of delimiters. Here's the array:
Array.jpg

Filling the array with delimiters for the beginning and end of each object is pretty simple. The Array.Sort() method takes our array, in un-sorted form, and an instance of our comparer class, and creates a sorted array like this one: (The #'s above the array elements show you which begin/end delimiter points to which body)
Sorted.jpg

Finding Interference

Wow, with very little theory, we're at the point where we can begin to detect collisions! Almost, we're actually ready to detect what is called interference, a 1D collision. Going from interference to collision is simple, however, because we can test 'interfering' objects' bounding volumes to determine collision. For rendering purposes, this is almost always enough. In a physics engine, however, we may need to go one step further and find out if the actual objects within the bounding volumes intersect.

There are two approaches to finding interference, first, you could ask the broadphase algorithm to send you each pair of interfering objects, and second you could ask it "Which objects interfere with this one?" If you use the second bit of logic you will be better suited to multiple core execution and can use the .NET IEnumerable<> pattern.

Either way you go, the algorithm is very simple to implement:
  • Create the 'Begin' delimiter for an object.
  • Use Array.BinarySearch<> to find the index of that delimiter within your array.
  • Enumerate through the array from that index on, following rules 4-6.
  • If you hit the end of the array, you're done.
  • If you hit another 'Begin' delimiter, you've found interference.
  • If you pass the 'End' delimiter for the original object, start ignoring rule 5.
  • If you hit an 'End' delimiter, construct the 'Begin' delimiter for it and compare to the delimiter at the index from rule 1. When greater than or equal to zero, ignore this delimiter. When less than zero, you've found interference.

Optimizations

The first thing you might notice is that rule 4, above, indicates you might be searching through much of the array looking for interfering objects. A simple optimization is to keep track of which delimiters border void space. This is simple figure out, because each update we have to sort the array, and in that time we can walk through it and mark some delimiters as 'touches void'. In the below diagram, I've started a stack, indicated in text below the array. Every time I hit a 'Begin', I add one, every time I hit an 'End' I remove one. Thus, every time the stack is zero, I know that there are no more objects in that space. I can then amend rule 4, above, to say "Also stop when you hit a delimiter that borders the void." The dotted lines below represent the placement of the 'Touches Void' flags.
Markers.jpg

When working with the .NET Framework, and especially with the .NET Compact Framework on the Xbox 360, avoiding garbage is a must. Two things we must be aware of are that we don't create new arrays or resize arrays dynamically where possible, and that we don't box values. Boxing is easy to do, for instance if you opt for the IEnumerable<> pattern, you might create the following structure:

struct MyEnumerator : IEnumerable<MyGameObject>, IEnumerator<MyGameObject>
{
    //... implementation ...
}


In doing so, you avoid the garbage created by using the yield return keyword, but you will cause boxing (and thus garbage) unless you specifically reference your enumerator type as MyEnumerator, and not through the interfaces it implements. This one can be tricky, and certainly obfuscate your code, so take it with a grain of salt.

To avoid resizing arrays and having portions stored non-contiguously in memory, you might consider using a default large array and keeping track of how many items in the array are 'in use.' Do avoid, however, leaving references to MyGameObject in the unused portion of the array, and consider growing when needed, too. You might be tempted to use List<Delimiter>, which has a .ToArray() method; but watch out, that's a new array you're playing with!

Every so often, you should evaluate the clustering of the sorted array, and potentially decide to start sorting on another axis. This axis, of course, does not have to be a cardinal axis, but picking X, Y, or Z is usually most straight forward. The best candidate axis could be either fixed, or better yet, the axis where values vary the most. For my Grand Theft Halo 2 example, for instance, this axis would not be the Y axis, because most objects usually cluster on the ground in those kind of games. Less axial clustering means more 'Touches Void' flags, means fewer array enumerations.

Last edited Oct 24, 2007 at 6:48 PM by Johnnylightbulb, version 2

Comments

No comments yet.