Kyle Schouviller

Because Mykre couldn’t wait to see it, here’s the source code for the wisp demo I recently made. I cleaned up the code a bit and added pretty liberal comments so you can really tell what’s going on. Let me know what you think!

Download the Source Code

A quick note about time control, with code.

XNA makes time relatively simple - a GameTime object is managed automatically and given to you every frame. This makes calculations involving time relatively simple. However, what happens when you want to slow down time?

You could just use a variable to set the time speed, and then multiply your elapsed time by that every frame. However, if you try this trick on total times, you better not change the time speed, because your numbers will be way off when you change speeds.

My team ran into this problem on our DBP project, and I suggested that we use a time controller to manage game time. Basically, the time controller maintains its own time variables, which it updates every frame based on the current time speed (adding to total modified time every frame). Then, when updating objects, the time controller’s time is used (be it real or modified time).

You can download the code below - it’s part of a library I’ve been working on for my own projects, but since it seems like it’d be useful to others, I figured I’d post it. Let me know if you find it useful.

Get the code!

ps: I’m obviously not dead - just been really busy lately…hopefully will be able to share what I’m working on in a couple weeks.

With the Dream Build Play competition nearing a close, I’m sure everyone is busy with tweaking their game to make it as fun as possible. Of course, this can be quite the monumental task if you’ve got a large code base with “magic numbers” all over the place.

What’s a magic number, you ask? A magic number is any number in your code that doesn’t have a concrete reason for being that number, and could be changed without changing the meaning of that number. For example, your character’s velocity equation might have something like this:

Velocity += 9.81f * Vector3.Down * elapsedSeconds;

That’s obviously an equation to add gravity to your velocity. Who’s to say that gravity is 9.81 though? Your world will most likely have different units, you might change these units over time, or, worst-case, you might want to change your world’s gravity late in production and have to track down all of the places where 9.81 is used. Now, you could search through your entire project for this number and change each instance…but then what happens when you need to change your overall fade speeds? How about the delay after enemy attacks?

One solution I’ve found (and enforced on my team’s DBP entry) was to have a static constants class. This class is very simple - it just contains a bunch of constants. You can even organize them by placing more static classes within that class (or by using namespaces). For example, I ight have something like this:

Then, whenever I need to make use of gravity, I can just reference the Constants.World.Gravity variable. That way, if I need to make changes, I can do it very easily.

This is especially helpful when playtesting. If you have a good tester (and especially if you have another screen/machine to test on), you can sit them down to play and have them comment on anything that doesn’t feel right. Maybe the attack isn’t firing fast enough, perhaps the enemies are getting too strong too fast. You can stop their game, change the AttackDelay and DifficultyRampFactor variables, recompile and have them playing again in just a couple minutes.

As an extension of this, you can have all of your constants stored in a file, and load them all upon starting your game. Then you don’t even have to recompile between tests!

It’s about time I release the engine I created last fall in XNA. This engine is purely academic, and should be treated as such (i.e. don’t go trying to make your own games with it unless you want to retouch most of the engine). However, it’s fully commented, and I believe the code is both an excellent example of something I’ve done in the past, and of how to tackle a ton of different common game programming tasks.

This engine accomplishes many things - input management, 3D-rendering of 2D sprites, animation, text rendering (it was made before the refresh release), Quadtree, Separating Axis Theorem (oh boy!), and of course, object management. It’s not perfect, since I had to code it in a couple weeks so my team could actually do their assignments (see the WSUXNA page for more). However, with as many problems as it tackles, I think the code could be useful to look through for an aspiring game programmer.

Along with the engine code I’ve provided the engine test project I used while developing as a small example of how the engine is used. It’s a bunch of different shapes bouncing around in a box. Each shape also has debug outlines showing the underlying polygon used for collision detection (separating axis theorem allows for any convex polygon to be used!). The bouncing is just based on object centers and current velocities - so it’ll look a little odd. You can switch between objects with up/down (on dpad or keyboard) and rotate them with left/right (dpad or keyboard, again).

Get the code

Or just the engine demo

Enjoy!

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?

I admit, I used to hate commenting code. It took so much time, and I was constantly changing the code anyway. Every time I’d code something, I said “I’ll comment it once it’s done.” Every time I finished something, I’d immediately start working on the next piece. After all, it took a lot of time to comment things, the comments weren’t even that easy to read, and I had better things to be doing.

Then, about a year and a half ago, I started using C# and discovered the joy of commenting in Visual Studio 2005 (and the express editions). It’s still not a blast to comment things, but it is much easier, and your comments can actually be useful (besides the obvious usefulness of being able to figure out what you meant to do last Wednesday at 4:00 AM!). This ease and usefulness are all wrapped up in the triple-slash, ///.

Go ahead, open Visual Studio and create a new enumeration. Then, click on the blank line above that enumeration, and type three forward slashes, ///. See what Visual Studio did for you? The Visual Studio IDE will create a comment block that outlines the information for whatever is on the line following the triple slash. This can be as simple as a summary block or as complex as detailing all the fields of a method.

It’s easy to add more information, too. Just add another triple-slash line below the current block and type a less-than symbol (<), and check out the list of things you can add. You can add samples, remarks, seealsos, and much more!

So it’s really easy to comment chunks of code now. So what? Having three lines of comments for a simple enumeration doesn’t seem like an improvement. What’s with all the XML stuff anyways?

Well, triple-slash comments are XML comments, and they are used to generate documentation. This includes both intellisense documentation and XML output documentation (more on this in a bit). You know how the intellisense information will usually include a little sentence about what the class or method does? For example, it tells us that a String “represents text as a series of Unicode characters.” Well, you can do that with your own classes, methods, enumerations, etc. Look at what happens when I try to use the enumeration I made earlier:

It also helps me make better use of my methods. Not only does intellisense tell me what a method does, it’ll also tell me what sorts of things I should use for that method’s parameters:

See how useful that can be? You can even export all of your documentation to an XML file, which you can then include with your code, or even post on a website. In fact, with a nice XSLT file to accompany your XML, you could have some pretty nice online documentation for your code.

To generate documentation, go to the Build tab of the project properties dialog (right click on the project in the solution explorer and select “Properties”), then check the “XML documentation file” checkbox in the Output section. Now, whenever your project builds, it will generate a nice XML file with all of your documentation. If you’re making a library for others to use - especially if you’re just releasing it as a pre-compiled dll - this is extremely useful!

Finally, you may notice that when you generate XML documentation you end up with a ton of warnings in the error list when you build your project. If not, congratulations, you’re a great commenter! Visual Studio will let you know when you haven’t commented something (in most cases) by giving you a warning during building. This won’t stop you from running your project, but it will help you find places you need to comment so you can output effective documentation.

So please, use the triple-slash to comment your code - and comment as you go. It makes life easier on everyone who touches or uses your code in the future - whether it’s you, your team, your coworkers or someone who’s using your components.

Do you find yourself typing the same thing over and over again? Maybe it’s the code to draw an effect (begin, end and the pass loop) or maybe you keep having to resolving a render target to a texture. Wouldn’t it be nice if you didn’t have to type all that code every time?

Enter code snippets! Visual Studio has a nice feature that will insert small bits of code for you, even allowing you to specify different fields within that code. For example, the “prop” snippet will insert the following code for you:

It’ll let you specify the type of the variable “int”, the name of the variable “myVar” and the name of the property “MyProperty” just by tabbing between the fields too. Go ahead, try it - open Visual Studio and type “prop”, then press enter in the intellisense popup and then enter the values you want.

I could easily change it to a Vector3 type variable called position with a property name of Position.

“That’s great,” you may say, “but it doesn’t help me set up my drawing code any faster.” Fortunately, that’s not entirely true. While there isn’t a “SetUpMyDrawingCode” code snippet, you can make one! Code snippets are just XML files that define the code to insert, the variables to allow the user to edit, and a few extra things about what namespaces might need to be included and who created the snippet. You just drop these in your “Visual Studio 2005\Code Snippets\Visual C#\My Code Snippets” (probably in your My Documents directory) and then reload Visual Studio (or add them manually via Tools -> Code Snippets Manager).

There’s plenty of information on the internet on how to create your own code snippets. There’s a nice article written by Anand Kumar at dotnetjunkies that can walk you through creating a simple code snippet. You can find it here. I’d also suggest reading the Code Snippets Documentation on MSDN. It provides a lot more information about the little nuances that you might want to explore with more complex code snippets.

I’ve written some simple XNA code snippets and put them up for download here. You can install them by unzipping them to your “Visual Studio 2005\Code Snippets\Visual C#\My Code Snippets” and then loading Visual Studio (and if they don’t load, add the folder manually using Tools -> Code Snippets Manager in Visual Studio). This includes the following snippets:

• DrawEffect - Sets up the effect drawing code, including the “forall passes” loop.
• PlatformVariable - Creates a platform-dependent variable, using the method discussed in my previous post on sharing code between platforms.
• ResolveRenderTarget - Resolves the specified render target, stores its contents in a texture, and then sets an effect parameter to the value of that texture.
• ThreadStarter - Sets up and starts a thread containing user-defined code.

I made these pretty quick, so they don’t contain the best code in the world and they’ll probably need some references resolved for proper use, but I hope they make a good starting point for you to make your own code snippets.

One word of advice: make sure you have an XML syntax validator. Incorrectly formatted snippets won’t load at all, and there’ll be no error message telling you what’s wrong. I personally use Notepad++ with the XML Tools plugin for all of my XML editing needs. It’ll even format my XML files for me so they look nice. Visual Studio has a pretty nice XML editor too though, so use whatever you’re comfortable with.

Post some of your own code snippets here to let me know what you come up with.

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.