Kyle Schouviller

Enjoy this tutorial on Quadtrees, explaining how they work and why they’re useful for collision detection. Includes pictures and source code. Comments are highly appreciated.

A Quadtree’s Purpouse

Your collision detection solution should operate at successively more accurate levels to be effective. Since each successive level is more accurate, deeper levels require more processing time. Therefore, the rule at each level is to perform as few collision detections as possible. We do this by eliminating unnecessary checks at higher levels. Let me explain with an example.

Imagine a game like Pong, except with a rotating triangular ball. This ball needs to have perfect collision detection with the paddles, which means if any part of the triangle intersects with the paddle, there is a collision. You can’t just do simple radial collision detection, nor can you do rectangle collision detection, because the triangle might not actually be colliding for some collisions detected in those cases. However, performing the triangle-to-paddle collision detection can be expensive to do every frame (I know, not that expensive – but imagine 200 balls with 30 players around a big field with balls also colliding with each other, or something like that). So what are you to do?

The solution is to do several levels of collision detection. First, you’re going to check if the ball is even on the paddle’s side of the line. If it’s not, then obviously it doesn’t need to be checked for a collision. Then, if it is on the paddle’s side, you’ll check if the ball is in the same vertical half of the screen as the paddle. Again, if it’s not, you’re done. You might do this a couple more times, and if you could still be colliding, that’s when you actually perform the expensive detection. With just the two checks, you’ve just reduced 75% of the expensive collision detections to a simple positional check (e.g. Position.X < ScreenMiddle.X).

How a Quadtree Divides Space

The Quadtree is your first line of defense in the two-dimensional collision detection battle. It lets you know with pretty decent accuracy which objects could be colliding. It does this with rectangular bounds checks, which are simple to perform. Once you’ve found out which objects could be colliding, you can then pass those on to a more complex algorithm, like the Separating Axis Theorem, or a pixel-based collision detection algorithm.

A Quadtree works by dividing space into rectangles as objects enter that space. It does this by following a simple rule, which is:

For any node in the Quadtree, the node will be divided further if more than n objects are contained within the node at any time.

With n being a pretty low number, like 1 or 2. When a node divides, it divides into four different rectangles by splitting the node in half horizontally and vertically. Any objects that can fit entirely within one of these new nodes are pushed down (with objects that are on node edges remaining in the higher-level node). These pictures should explain the process.

One object in a Quadtree. The object is at level 2 of the tree (with level 1 being the entire box).

Note: Duncan points out in the comments that this image couldn’t exist unless there had previously been two objects in the Quadtree (since the level 1 box would never have been partitioned). The image is like this to demonstrate an object moving across nodes – which you’ll see in the next image. Look in the comments for further discussion.

Now the object is at level 1, because it can’t fit entirely within a lower-level node.

Two objects in a QuadTree. Note that they are in different nodes, so the space doesn’t need to be divided further.

Now three objects are in the QuadTree. Two objects were in the level 2 node at the top-left, so the node had to be split (since this is a tree with a maximum of one object per node). The objects fit entirely within the new level 3 nodes now.

This image shows the nodes created by an object moving across the space. Notice that as the object passes through the first level 3 node, it divides the space again. Then, as it passes through a level 2 node, it has to divide it twice to be able to satisfy the “only one object per node” rule. Also notice that the object actually passes through every level of Quadtree node in this image – try to figure out how.

So How Does This Help Me?

Well, when it comes time to figure out if some object is colliding with anything else, you’ll want to check the Quadtree to see what items it might be colliding with, so you can then perform a more complicated collision detection check later. You do this by querying the Quadtree with a query box. The Quadtree will then figure out which nodes contain any part of the box, and return a collection of all items within those nodes. So for a query box like this:

The following would happen:

1. The box collides with the level 1 node – but there are no objects in level 1.
2. The box collides with two level 2 nodes – but there are no objects in them either. However, their child nodes need to be checked now.
3. The box collides with four level 3 nodes, and there is one object in them, which is added to the return list. Note that there are no level 3 nodes in the top-right level 2 node, so it is not queried any further.
4. Finally, the box is colliding with six level 4 nodes, one of which contains another object. Note that the object we just returned was on an edge, so it was contained within the level 3 node instead of a level 4 node.

So, for this query, two objects would be returned. In this example, all of the returned objects are colliding with the box. However, if there was an object on the middle line on the left (at level 1), it would also be returned, though it clearly does not collide. However, in a world with hundreds of objects, this would be acceptable (as long as everything wasn’t on the line).

The Moral

If you query the tree with all n objects in the tree, with each query returning log n results, you have reduced the number of expensive collision detections from n-squared (checking every object against every other object) to n log n (the average number of objects returned from this sort of tree query). Sound like big-O notation?

Some Code?! Oh boy!

I updated the QuadTree used in my WSUXNA engine to work with the newest version of XNA, to be generic, and to be a little more efficient than its previous incarnation. It comes in two files – one containing the QuadTree and all related classes, and one containing a floating-point rectangle class, which I needed for this implementation. I’ve tried to comment it as fully as possible, so hopefully you shouldn’t have any problems reading through it – if you do, please, ask questions!

In my Quadtree, I’ve made the query methods take a List by reference, to cut down on the garbage generated by throwing new Lists around every frame. I also perform a simple box collision detection method on every object that might be returned, to reduce the edge-crossing objects problem.

There are three classes in the QuadTree file, two of which you will use. I’ll explain the useful ones:

• QuadTree – The Quadtree. Create a Quadtree with the generic type being the type of object you want to place in the Quadtree. You’ll need to specify your initial world size, which can be at whatever scale you’d like.
• QuadTreePositionItem – A long name for a position class. You’ll need to instantiate and store these in your objects and then add then to the QuadTree by using the QuadTree.Insert method. You can also just store the position item returned by the QuadTree.Insert overload method. To move an object in the QuadTree, just update the Position property in the position item class. The position item also contains a link to its Parent, which is the object that it’s being used by (yah yah, I can see you OO people cringing…but it’s easy to use and understand this way, and isn’t really that horrid). Finally, remember to Delete() the position item when you’re done with it and set your references to it to null – that’ll remove it from the Quadtree and make sure it gets picked up by the garbage collector.

Now, if you need to get a list of items that might be colliding with some item, just query the QuadTree class by using its GetItem methods.

Enjoy!

Get the source code!

Note: I may update this code later…I’ve tested it a bit, but I haven’t subjected it to really rigorous testing since I removed it from the engine, so it might have a couple bugs. There’s also a few things I’d like to do, like make the node class internal, and possibly extend the QuadTree to return a list of parents when you query it. Go ahead and explore that yourself though Also, comments are highly appreciated, as I’d like this article to be as helpful as possible to everyone who runs across it.

Read the followup article

Last Fall I took a game design class at my University. Far from design, the class mainly consisted of game programming, with some lectures on design. As part of the class, we were required to program several games, the last game being a large group project. The professor supplied us with two separate engines to use for our games – one using C++ and the other Java. We decided to roll our own.

Thus began work on the WSUXNA engine – a simple 2D game engine built using Microsoft’s XNA Game Studio Express Beta 1 (which was released in the middle of our first project) – and later XNA Beta 2. I did most of the engine coding for the Beta 1 engine (a three-day effort), and recoded the whole thing for Beta 2. It was a huge amount of code (thousands of lines), and by the end of Beta 2, a fully-commented and working engine.

Building on Common Ground

You may recognize this pattern, though not in this format. This is the subject-observer design pattern from the Gang of Four. It’s also pretty much a simplified version of the Event model in the .NET framework. This is one of the basic components of the WSUXNA engine – it allows the engine to maintain a hierarchical architecture (nothing can directly touch anything above it in the architecture).

The purpose of this design pattern is to let components that are lower in the hierarchy notify components above themselves about some event, such as the death of a component (so it can be removed from a collection), or perhaps that a component has moved by the movement manager (and its visual position should be updated as well). When a component is created by a manager (more on those later), the component inherits the Subject class and the Manager implements the IObserver interface. You can see what these contain above.

When a subject is created, the manager will register events with the component through the AttachNotifier method. This will register a delegate (pointing to the manager’s implementation of the Notify method) with the subject, to be called when an event (e.g. “die”) is raised. The subject places this delegate in a dictionary that contains a list of delegates to call whenever a certain event is raised (e.g. “die”, again). Later, the manager can detach the notifier if it wishes by using the DetachNotifier method of the subject.

So, for example, the entity manager might be called upon to create a brick in a Breakout game. The entity manager will need to know when the brick has been destroyed, so it can be removed from the entity manager’s list of items needing updating. The game manager will also need to know when the brick has been destroyed so it can add points to the game state. Both will register a “die” notifier with the brick so that when it is destroyed (i.e. when it “die”s), it will notify them both before removing itself.

Like I said, this is basically a simple implementation of the Event handling capabilities of the .NET framework. If you chose to use something like this in your own designs, I’d suggest exploring the Event handling already present in C#. At the time, I overlooked Events – but by doing so I gained better understanding of them and was able to have more control over how my engine worked.

Next: The rest of the basics – Managers and Components.

Note: Do you like the class diagram above? It was created by importing my code into Visual Studio 2005 Professional and creating a class diagram from the code. They’re a really awesome way to design code, and I’d like to see them included in XNA Game Studio Express. Shall we campaign for them?

Use the Separating Axis Theorem. Use a space-division scheme, like a Quadtree. Use multiple levels of collision detection to avoid unnecessary testing. Use a common bounding structure for all objects so they can interact generically. Those are things I learned when I did it. Here’s what I suggest for trying it yourself:

1) Use a common data structure for object bounds information. This structure should store a convex polygon with an arbitrary number of sides, a rotation value, a scaling factor, and position information (and more, if you’re doing crazy warping or something). You should also provide a method that can find a world-aligned bounding box that contains all vertices in your object bounds.

2) Learn how to make and use a Quadtree. This will reduce the number of collision detection checks you make each time you run your algorithm. For n objects, you can reduce a simple n-squared loop to n log n if you do things right. The Quadtree does this by splitting up your world’s space into four spaces (one in each corner), which are then split up into four spaces, and so on, so that there are a maximum of 2 or 3 or however many objects in each lower-level space. Then, when you need to check for collisions with an object, it only needs to check for collisions with objects that are in the same cell as it (or higher-level cells…because of objects on cell boundaries…but you’ll learn all about that when you learn about Quadtrees).

Your Quadtree needs to manage itself properly as well, which means you need to clean up the tree now and then and move items around properly (you can’t just rebuild the tree when partitioning a node – that gets slow fast – I’ve tried it). You’ll also need a couple efficient ways to query the tree for items – I suggest providing query methods that take a bounding box and a point.

There used to be a really good tutorial on Quadtrees – directed towards the XNA crowd if I remember right. The site it was on has died though, so either I’ll need to find out where it moved or write my own tutorial.

3) Do simple collision detection first. Most of the time, your objects probably aren’t colliding. A good deal of the time, even if they’re close to each other, they aren’t colliding. The Quadtree will let you know when objects are close to each other – but a simple collision detection test will let you know if they’re close enough. Since you’re already using bounding boxes for your Quadtree (which is why you have a method to provide a bounding box in your common data structure) you can just do a simple test with these bounding boxes. Check if they’re lined up both axis. If they are, continue testing. If they’re not, they’re too far away from each other, and you’re just saved the program a lot of icky math. It’s better to do a few simple operations now when most of the time you’ll save the program from doing a ton of icky operations later.

4) Learn the separating axis theorem. This is probably the hardest part. It may not be necessary, depending on what you’re doing (bouncing balls don’t need more than a radial check), but if you have a lot of differently shaped objects, you can’t beat this method for its accuracy. I’d explain it, but there’s a much better and more complete tutorial written up at Metanet Software (the people who made N). It’s even got some demonstrations that you can play with to see how things work. Go check it out.

Like I said, I’ve done this before, but it was in XNA beta1 – beta2, and I haven’t updated the code since. I also wasn’t worried about performance at the time, so it probably wouldn’t perform too well on the Xbox (though it runs really well on Windows, mostly because you have to deal with performance issues at some level when working with collision detection). If anyone’s wildly interested, let me know, and I’ll throw up the code (I might even clean it up a bit, too).

This is (sort of) possible! It seems that the GSE team worked on implementing this feature for the 1.0 release, but had other priorities and weren’t able to complete it. Leaf came up with a project template that will allow you to build for multiple platforms (i.e. the Xbox 360 and Windows) in one project. You should have a good deal of experience with programming for both platforms before doing this though, as the feature isn’t officially supported, and you might run into problems that will be extremely difficult to diagnose. In other words, you’ll have problems with intellisense, references and more.

There is a forum thread on this topic on the XNA Forums in which Stephen Styrchak discusses why this wasn’t included as a feature in the first release of XNA GSE. Basically, there wasn’t enough time to properly implement it and they felt it was more of an advanced feature (i.e. they expected more beginners to be using XNA GSE, and didn’t want to cause them headaches).

The safest way to do this continues to be by adding your source files as links. To do this, set up your project for one platform, then add a new project for the other platform. Create a directory structure in the new project that mirrors the old project (e.g. if you have Effects, Resources and Classes directories in the first project, create those in the second project, with the same names). Then right click on the folder you want to copy the files to (or the project, if you want to copy to the base directory), and select “Add -> Existing Item.” Then, in the “Add Existing Item” dialog box, find the file you want to add. click on the file, then click the arrow by the “Add” button, and select “Add As Link.” This way, you’ll only have one copy of the file hanging around, and you won’t have to keep copying it every time you make a change.

I’ve started a topic on Microsoft Connect about this issue. If you’d like to see this officially supported in the next version of XNA Game Studio Pro/Express, go vote on it here.

C# is a really nice language – it takes care of a lot of the little things for you, letting you focus on the bigger issues in your program. However, it can’t do everything – and even things it will do, it won’t necessarily do well, or when you need them. Garbage collection is the classic example. It’s nice that you don’t have to keep track of your things and clean up after yourself. The garbage collector isn’t there to take care of you though, and it’s not going to make sure your code runs nicely.

This is especially important on the Xbox 360, where creating objects is costly. The .NET Compact Framework team put together a set of pages back in December that are a must-read for anyone writing high-performance code for the Xbox 360 using XNA. They cover floating point performance, manual inlining, making the most of the multiple cores and lots on garbage collection. Unfortunately they don’t cover graphics performance, though they do mention that XNA has pretty much direct access to the graphics hardware. Go read them here and here.

Now I just need to reduce the amount of time my data-loader takes. Can anyone suggest any effective techniques for processing ~50mb of data on a per-byte basis? I’m already blocking data so it’s processed faster and I’m using value types so the heap doesn’t get nasty – any ideas?

I ran into this problem recently, and I thought it would be a good point to note, especially for anyone who doesn’t have access to an Xbox but would like their code to work on one.

When writing shaders, remember that the Xbox is more strict than a PC. Make sure your input parameters match the vertex definition (and likewise, the other way around). So if you’re using a VertexPositionColor, make sure you’re looking for something like this:

VertexToPixel myVertexShader(float4 inPos : POSITION, float4 inColor : COLOR0)

Likewise, if you’re looking for a texture coordinate, don’t use the COLOR semantic, even if that’s what you’re going to be using it for. e.g., if you’re passing a VertexPositionTexture3 (a 3D texture coordinate you may have defined) but your vertex shader looks like this:

VertexToPixel myVertexShader(float4 inPos : POSITION, float3 inColor : COLOR0)

It’s not going to work…and worse yet, it’s not going to tell you why. This can be particularly troublesome if you’re developing without an Xbox on hand. Make sure your shader takes the correct parameters instead:

VertexToPixel myVertexShader(float4 inPos : POSITION, float3 inTex : TEXCOORD0)

While the former may work on a PC, it won’t work on the Xbox 360.

Preprocessor directives!

These enable you to define what code will or won’t be compiled, throw errors or warnings during compilation and mark regions of code for better organization. Here’s a short example of what I’m talking about:

#if XBOX
myRenderTarget = new RenderTarget2D(device, width, height, 1, SurfaceFormat.Color);
#else
myRenderTarget = new RenderTarget2D(device, width, height, 1, SurfaceFormat.Vector4);
#endif

The code above will compile differently when built for the Xbox or the PC. In this example, when building for the PC, we want to use the Vector4 surface format, because of the extra precision it gives us. However, since the Xbox doesn’t support the Vector4 surface format, we will use the Color format when compiling for the Xbox. Now we can just copy this code file into our two separate projects, and everything will compile just fine for both.

The XBOX and XBOX360 symbols are defined by default in Xbox 360 projects in XNA Game Studio Express.

You can add symbols using the project properties box by right-clicking on your project and choosing “Properties” and then selecting the “Build” tab. You can also add different symbols for different project configurations, allowing you to build different code in release and debug versions, or even make your own special configurations.

#if (DEBUG && !XBOX)
Console.WriteLine(“There are {0} enemies attacking the base.”, nEnemies);
#endif

Here, I’ve specified that if I’m building in debug mode for the PC, I want the number of enemies attacking to be written to the console. You can use most of the standard conditional operators (e.g. &&, ||, ==, !=, etc.) in preprocessor directives.

You can also define your own symbols using the #define directive, and undefine symbols using the #undef directive (which will undefine the symbol for the rest of the file, or until you define it again).

#undef XBOX
#if (DEBUG && !XBOX)
WriteToMyDebug(“The target platform doesn’t matter here! I might actually be running on an Xbox!”);
#endif

Finally, The #region and #endregion directives, which are my favorites. You’ve probably noticed that you can collapse a method by pressing the little “-” next to it, allowing you to hunt around your class a little easier (or just hide the parts you’re not working on). However, you still have variables hanging around, and even the method stubs for all those methods. It’d sure be nice to hide some of that stuff – especially if you’re fully commenting your code (an excellent habit to pick up).

#region Position

///

/// The horizontal position of this entity
///

private int x;

///

/// Gets or sets the horizontal position of this entity
///

public int X
{
get { return x; }
set { x = value; }
}

///

/// The vertical position of this entity
///

private int y;

///

/// Gets or sets the vertical position of this entity
///

public int Y
{
get { return y; }
set { y = value; }
}

#endregion

You can see that just two properties in a class can take a lot of room. However, if you put region directives around the section, you can then collapse it:

| Position |

This can make your code much easier to look at and work with. In fact, my standard game class looks like this:

///

/// The game class for Super Blaster (made that name up)
///

public class SuperBlasterGame : Microsoft.Xna.Framework.Game
{
| Variables and Properties |

| Initialization |

| Update Methods |

| Draw Methods |
}

Notice how easy it would be for someone to find a section they’re looking for? They could just expand “Variables and Properties” to add a variable to this class, or expand “Initialization” and then “Constructors” if they wanted to change how some variables are initialized.

For more reading on the subject, check out the MSDN Documentation or the tutorial at C# Help.

Update: I’ve written another post on building for the Xbox and Windows in the same project. Check it out here.

In my current project, I needed to make my own vertex format so I could pass more information to the shader. Reimer has a wonderful tutorial on the subject (and the rest of his stuff is great, too). Unfortunately, the tutorial doesn’t implement a vertex format that will work on the Xbox 360.

After some searching, I found that Ziggyware has a great tutorial on custom vertex formats. The most important thing to remember is to implement the entire interface.

I thought a video might be a little better for demonstrating my cloud.

Granted, it’s not the best quality, but it still shows what’s going on. You can see that the cloud maintains its shape as you move around and even through it. You can also see the subtle animation.

It’s not quite amazing yet, but it’s getting there. This is a completely volumetric cloud, rendering in real-time. I’m still working out the lighting equations for it (which are kind of hard to do when your hand it broken and you can’t draw the situation on a piece of paper) and then I’ll work on making it prettier. However, I’m pretty happy with how this looks so far.

My work is loosely based on Schpok et. al,, along with some other information I’ve found scattered about the internet. Most of it is old though, and doesn’t consider the capabilities of current graphics hardware or multi-core machines. Also, Swell, the demo for the algorithm proposed by Schpok et. al, doesn’t work on my machine because of a versioning problem with OpenGL 2+. I’m getting pretty close to what they’ve done though, so I don’t think I’ll be needing it.

I’ve got to say, I’m very happy with C# and the XNA Framework. They take a lot of the low-level details away without seriously hurting performance. I’m still able to do some pretty intensive stuff using managed code. I’m sure it’d probably be a bit faster in C++, but since XNA doesn’t work with unmanaged code, I’m pretty happy using C#.