Kyle Schouviller

About two weeks ago I thought, “hey, it’d be cool to make a game in 24 hours.” That of course meaning 24 hours total, not one day. So I made up a design for what should be a small game, and started off. Then the design grew (as these things do), and the number of players grew (because competition is fun!), and I even added a velociraptor. However, I also had a lot of stuff come up over the last couple weeks, which made me lose track of my time entirely - so I’m probably somewhere between 24 and 48 hours for this so far.

So I wanted to give all you readers a preview of the public alpha I’ll be releasing by the end of the day (assuming I don’t get loaded down with real life priorities between now and then). It runs on Windows and Xbox, supports up to four players, supports mouse and gamepad control (and keyboard if it makes it in), and is pretty entertaining. I just need to stamp out a few bugs, clean up some more interface stuff, and work on the initial difficulty curve before I’m ready to put this up as a public alpha.

The art is almost entirely by Pablo Poffald, a wonderfully keen artist I’ve had the pleasure of working with in the past. I added a few things here and there (and wrote a shader to emulate some Photoshop effects - look for a tutorial on that in a few weeks).

So if everything goes well, I’ll be putting up an Alpha of this later today, for both Windows and Xbox. I’ll of course appreciate any feedback and bug reports.

A little while ago I read through the engineering publications from Bungie. Some of the AI papers discuss one of the worst problems in game AI: recognizing the player’s intention. The next time I played on Xbox Live, I picked up my controller, put on my headset, and had an idea: why not use voice to help AI figure out what you’re thinking?

For example, if you say “fall back,” the AI could recognize that and do it. If you have the thermal vision of the group and you see enemies around a corner, you might say “enemies around that corner.” Even though you didn’t tell the AI which corner you meant, they could either guess, or - since they’re controlled by the game system - use information in the system to figure out which corner you mean. It’s cheating, but it improves the user experience, so it works.

So why isn’t this in games already? Aside from localization issues there really aren’t any barriers. Speech recognition works pretty well - it’s a bit slow and not always accurate - but that’s good enough to provide help to an AI in a game (not to entirely guide it - I’m talking about a layer on top of the normal AI you’d find in a game). The only other issue would be that not everyone has a headset. But if you only use voice to assist AI, you can still provide a quality experience otherwise. We should at least be seeing this sort of thing in top-tier games.

In fact, to demonstrate how easy it is to get some very rudimentary speech-driven AI working, I decided to code a little test tonight. I set aside some time for it and went to work. 15 minutes later I was done. Turns out .NET 3.0 has speech recognition built into the System.Speech.Recognition namespace. The result is this:

Download it here
(requires .NET 3.0 and XNA 2.0)

You say some variation of top, bottom, left, right or center to move the ball to that position on the screen. It’d be trivial to translate that into a 3D space based on a first-person perspective (though “front” might be a good word). It could also be more context-sensitive - e.g. maybe “on the left” after “the door” would refer to the left side of the hall instead of the player’s current “left”.

So what are your thoughts? Why aren’t we seeing this in games already? Are there games that do something like this? I know there are games that use sound recognition, but why wouldn’t the more popular games use voice recognition? I looked for patents, and there are a couple, but they seem very specific, and not really applicable to the first-person genre. Other than taking system resources (which with more powerful systems should be less of an issue), what reasons are there for this not being in games already?

I thought I’d post a quick note to post this, a demo of animation blending using FlatRedBall (along with some other nice tricks). This only took a day to put together, and most of that was finding the assets and debugging the movement code (since I wanted to show the blending).

The demo program can be downloaded from my portfolio page, and runs in 720p. The audio is a little weird, but it’s probably because I messed a lot with the sound processing in XACT. Enjoy!

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.

Zedox interviewed me today about my team’s Dream Build Play entry, Dream Sower. Check it out at Ziggyware!

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!

I’ve been pretty silent lately because I’ve been pushing hard to finish my team’s Dream Build Play entry. I was lucky to get to work with Rockstar, Catalin and Greg on a game we’ve called Dream Sower (formerly Mind Tap).

Dream Sower is a pretty simple game. You’re in control of a Dream Sower - a small robot that is inside a dreamscape. Your goal is to fight off Nightmares and to keep the dream interesting by planting dream seeds. These seeds will alter the landscape, grow trees and refresh the land, all to keep it interesting for the dreamer (who will become bored if you don’t constantly entertain him).

The game has gone through several phases of development, lots of last-minute design changes, and some great testing. In fact, I had such good playtesting experiences that I might just have to write an article on it in the future.

We finished the yesterday (just in time to hear about the extension), and I prepared and uploaded an Xbox 360 version of the game for your enjoyment. I’ll be putting up a PC version and an updated Xbox 360 version later in the week, after I clean out a couple cobwebs in the code.

As always, comments are appreciated.

Download the Xbox 360 ccgame
Download the Windows Installer

(please let me know if either of these has any problems working)

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!

A short, post-final follow-up to my previous article about Quadtrees. Includes a nice animation showing how the nodes are structured.

I’ve had some questions about my explanation of Quadtrees, and I must admit, the first time I made one, it was quite an undertaking. However, since I’ve been through 99% of a Computer Science degree, I’ve done a lot of work with data structures. So when I first read about Quadtrees, I noticed that they were very similar to an uneven binary tree. Each node can contain a certain number of items before splitting, items are arranged according to positional value (roughly), and the search time for any item is logarithmic.

The node tree

Before I explain the classes, a picture of how the node tree is constructed in a Quadtree as objects are added and move through the tree (individual frames on click-through):

You can see how the tree evolves as objects are added to the tree, and as an object moves through the tree. You can even see one case where two objects exist in one node since neither can be pushed down.

If you look at the Quadtree I’ve coded, you’ll see that it’s made up of three classes - QuadTree, QuadTreeNode and QuadTreePositionItem. This is pretty standard design for a tree structure (a wrapper class for the tree and then a bunch of nodes) - the only deviation being that I implemented a positional class as well since that data is required for a Quadtree (and since I need to be updated on object movements). Each of these classes contains groups of methods, which I’ll discuss below.

QuadTree

• Constructors - Initializes the head node and stores a little bit of information about the tree.
• Insert - Inserts an item in the head node.
• Query - Labelled “get…” in my methods, these perform queries on the head node and return the result.

QuadTreeNode

• Constructors - Initializes a node.
• Insert - Inserts an item in the node.
• Query - Labelled “get…” in my methods, these query the node.
• Partition - Partitions a node, initializing four child nodes.
• PushItemDown - Pushes an item in the tree down to the proper child node, returning success of the push. Used when item moves.
• PushItemUp - Pushes an item up to the parent node. Used when item goes out of range.
• Remove - Removes an item from the node (cleans up references to items).
• ItemMove / ItemDestroy - Methods called when an item in the node moves or is destroyed.

QuadTreePositionItem
Positional and Size information, all properties.

You might notice that the QuadTree class is really just an interface to the QuadTreeNode class. In fact, if you wanted to, you could just initialize a QuadTreeNode as a head node and perform all of your operations on that. I chose to implement a wrapper class so I could do a few extra things from the top that only the head node needs to do (such as destroy or resize the entire tree), without having all of that extra logic hanging around in child nodes.

Make sure it fits your design

I think the biggest issue in understanding a Quadtree is that there isn’t just a single way to make a Quadtree. There are many variations, and which variation you chose really depends on what your needs are.

If you’re using a Quadtree for a landscape, you’ll probably just be using it for visibility culling. In this case, you won’t care as much about how things move around in the Quadtree, since all of the objects will be set up during initialization. What you’ll want to optimize is searching, so you’re doing it as efficiently as possible every frame.

If you have a lot of balls moving around in a Quadtree, you’re probably going to have a lot of restructuring operations in your Quadtree as balls simultaneously occupy the same spaces. In this case, you might benefit from pre-partioning the Quadtree so it’s all ready to go when you start. You might also benefit from enforcing a maximum object depth, so objects pile up in a node once they reach that depth (so your Quadtree doesn’t grow huge). You could also push items into the top node, and only push them down if the node fills up (as opposed to my tree design, where I push them down automatically).

If you only have a single object moving around and everything else is static, you could do fine with my design. You may also want to keep items at the top level until the level fills up, so you can move items around faster (less pushes means less processing and function jumps).

You might notice that after I query a node for objects I make sure that object is intersecting the query box - this isn’t standard for a Quadtree, but in my case it was more efficient, since I could eliminate more objects with a simple box check and then be sure that all objects returned are at least bounding-box colliding with the query rectangle.

Overall, just make sure that the design fits your needs. If it doesn’t, look for ways you could modify it to fit into your design.

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