Loading and Networking

Soo... here's the blog I promised yesterday.

I'm not going to bother too much with background information in this entry. The main purpose of the loading sequence (aside from loading, obviously) is to separate the data needed for the player to set up a game (menu text and such) from the data needed to run the game. It also is meant to separate the initial synchronization sequence for players joining the game from the game's proper so the user need not deal with glitches as much.

In order to simplify content development I made the load sequence as intellegent as possible. When a player chooses a scenario (or a server to join) the game uses a custom content processor to read up data on stuff like team objectives, scoring, spawn points and such. Spawn points are defined such that they always spawn the same type of object. The object type is defined by an entity group type file, the custom content I'm writing about in my Custom Content Processor series, which is referenced in the spawn point. All of the scenario content data is wrapped in a single class.

With the scenario content loaded the game starts the loading sequence. First a function called GetDependentAssets, a member of the scenario content class, is called. This builds a set of all unique assets referenced by the scenario file. This set lives in the aptly named AssetCollection class.

Now, this initial list isn't the whole story. Entity groups in particular depend on other assets to render them in the game world. But I don't need to worry about that before loading assets because of some very simple magic built into the load function for entity Asset instances in AssetCollection. An Asset's Load method has access to the AssetCollection's Add function. If an asset in the collection depends on another asset it simply calls the Add function which will append the dependency to the AssetCollection if it's not already there.

This provides two advantages. First, I can rapidly develop scenarios since I don't have to alter the game's code to ensure all assets referenced by the scenario get loaded, second I have a very clean way of providing feedback to the user of how long the loading sequence will take. As I implied earlier each asset is loaded with an individual Load call. Once the load sequence runs out of assets that require a Load call the basic sequence is done.

Now what?
Well, if this is the player hosting the game we're good to go. Fire up the network session and let the player play. But if the player is joining an existing game the situation is a bit more hirsute.

Why? Because, as a joining player I know nothing about the game other than a few simple properties which can be expressed in a small set of 32 bit signed integers. Obviously this isn't much of use, especially since these properties don't really change after starting a game. (As far as I know anyway) I decided that I'll pack the initial scenario selection and its custom scoring/timing/whatever settings. This is enough for the joining player to run the load sequence above without further communication with the game's host.

After the load though there's a LOT the player needs to know before they can participate in a meaningful manner.

• What team is the player on
• Where/when will they spawn and as what
• Who's on the other team(s)
• What's the score, how much time is left etc.
• What objects exist in the game, where are they, what do they look like
• What objects belong to what players

So, this is where I am now. It's a fun problem to solve and I have a basic protocol thought up but it has yet to be tested. I'll update on it once I've had a chance to test things.

Later doodz

Non-Trivial Custom ContentProcessor - Part 3

So today I'm writing another exciting edition on how I built my custom ContentProcessor for loading game objects. If you've just started reading this series you might want to check out the Introduction, Part 1 and Part 2 first.

When I left off in Part 2 I provided a snippet of code to convert an XML document tree into a set of custom class instances which the game can work with easily. These classes describe how to create a group of in-game entities that make up a starship or other object. However the game makes some assumptions about the data these classes contain which can (and must) be verified by the ContentProcessor.

• The group has a root entity. Its parent entity is undefined
• There is only one root entity
• Entities within the group are only related to eachother, not other groups
• Entity properties are valid (notice valid here isn't defined yet, stay tuned :)

If we don't ensure these assumptions are valid then Space Combat Sim will crash when using the processed content. So, the next step that happens is validation and occurs immidiately after all the repeated process shown in Part 2 is finished.

bool foundParentEntity, foundTopEntity = false;
foreach (Entity entity in Entities)
{
    if (entity.ParentName == "")
    {
        foundTopEntity = true;
        continue;
    }

    foundParentEntity = false;
    foreach (Entity parent in Entities)
    {
        if (parent.Name == entity.ParentName)
        {
            foundParentEntity = true;
            break;
        }
    }

    if (!foundParentEntity)
    {
        throw new ContentLoadException("Entity " + entity.Name + " references non-existant parent " + entity.ParentName);
    }
}

if (!foundTopEntity)
{
    throw new ContentLoadException("Group has no top-level (blank parent) entity!");
}

So, what does this mess do? It verifies that two of the four conditions are true. The outer loop's main purpose is to locate and flag that there is one root entity in the group. The inner loop ensures that every entity (besides the root) has a parent. After the loops is a check to verify that the root was indeed found.

Astute readers might notice a bug in the code above. Circular relationships, e.g. entity A is a child of entity B which is a child of entity A, are not prevented by this procedure. There are a couple ways of dealing with this. The simplest, and most evil, would be to recusively search for the root entity from a given entity. This causes a circular relationship to blow the stack and throw an exception. This can be prevented by making the recursive algorithm build a list of each entity visited as we go up toward the root. If an entity appears in the list more than once then a circular relationship exists. There are also non-recursive ways of doing the same thing which I'll leave as an exercize for the reader.

I decided to omit this step from the game since such errors are rare and are caught in the entity creation tool which you can see in my article on collision detection. Currently by crashing horribly, I'll fix that in the future.

Another apparent bug is the lack of testing for non-unique names and for multiple roots. These are both handled earlier. If you remember Part 2 the last part of loading an individual entity block from XML was a call to AddChildEntity.

foreach (Entity entity in Entities)
{
    if (entity.ParentName.Length == 0 && parentName.Length == 0)
    {
        throw new ContentLoadException("Multiple top level (blank parent) entities found!");
    }
    if (entity.Name == name)
    {
        throw new ContentLoadException("Multiple instances of " + name + " found!");
    }
    if (entity.Name.Trim().Length == 0)
    {
        throw new ContentLoadException("Found nameless/whitespace named entity!");
    }
}

The actual adding part has been omitted since it isn't that interesting.

With all of this taken care of we still have one item left to validate. The entity's creation parameters. In fact, I have yet to show you how they're loaded. In fact, this is because the main tradeoff is made for thoroughness of validation versus speed and flexibility of coding is made here.

Entities represent a wide range of object types in the game with wildly different rules. Simple objects include stuff such as hull sections which can do little besides be blown up. Others, such as weapons, are much more complex. Parameters are needed to define stuff like timing, positions, orientations and references to other game data. What's worse is that, at the time I was coding this loader, many properties had yet to be determined, stuff like sound effects and so on.

With all of that in mind I decided to err on the side of flexibility. The loader will accept all parameters and ensure that the XML data is valid for the type that is being used to fill the parameter. It will not check if the parameter is used by the game and also won't check if the parameter's type is what is needed by the game. I'll show you how I implemented this validation without adding an excess of validation code to the game itself in Part 4.

Particle Systems - Part 1

The Basics

One of the most fundamental visual effects in games is the particle system. At their simplest a particle system is a collection of objects which can each be described with a single vector quantity. Their position.

Even these incredibly simple particles can be moderately versatile producing effects such as clouds, fog, plants and so on. Where particles really shine though is when they're allowed to change appearance over time. The simplest way of doing this is adding one more vector quantity to each particle's description, the particle's velocity. Once each frame we add the particle's velocity to its posision then draw it. This allows particles to simulate simple explosions, fires, smoke, bullets, sparks and so on. As well as clouds, fog and so on...

How? Just change the values that are assigned to position and velocity when the particles are created.

Several simple particle systems. From a previous game project of mine

In this example the blue bullets all launch from the same position but are assigned velocities that cause them to spray outward. The explosions are similar but the velocities point in all directions rather than just to the right. The smoke in the middle appars to drift behind the flame by being created slightly later and given a slower speed. This particular example has a few other variables for particles, namely colour and scale. This saves on art production since a the same clouds can be used for both smoke and fireballs.

For Space Combat Sim

Relatively modern 3D hardware supports drawing particles quickly via what is known as point sprites. Instead of drawing a particle using a billboard, which requires four vertices, each particle only requires one vertex. This is great since we can pump out more particles with less data going between main memory and video memory. However this only gets us as far as drawing the very simple particles I mentioned in the beginning. What's worse is as we add variables to particles we increase the amount of data that needs to be sent to the graphics hardware quite rapidly. This gets even worse when varying a particle's properties over time... at least if we do it all on the CPU.

Besides the CPU computers and game consoles also come with another extremely powerful processor capable of chugging through obscene numbers of operations rapidly, the GPU, on the video hardware. This requires some rethinking of how we do some operations like repositioning particles since programming on a GPU is quite different from a general purpose CPU. The GPU is amazingly fast at doing floating point math and vector operations BUT it adds the caveat that changing input data (i.e. changing the vertices that have been passed from the CPU) isn't feasible. I won't go into a huge explanation why but this will help. The gist of it is that vertices are processed in something like a water pipe. Data can only flow in one direction. You can change it as it flows from one process to another but you can't reverse the flow. (there are ways around this but they're painful and I'm not going to go into them)

So we can't apply velocity to a particle by simply adding to its position repeatedly. What can we do? If you remember your kinematic equations an object's position can be expressed in relation to time with the equasion P_t = P₀+V*t

Getting the initial position (P0) of a particle to the GPU is easy since that's simply the vertex position for the point sprite. Getting the time and velocity to the GPU are fairly simple but generally require a bit more thought since this is where the particle systems can be made extremely fast and flexible at the same time. I'll leave that for next time however since this entry is already getting rather long.

Abstracting XACT 3D Audio

Today I worked out the most of the major kinks of getting positional audio working in Space Combat Sim. Well, I guess it's yesterday now since it's 12:45 AM and I finished sound at about 6:00 PM, but I digress.

My main experience in audio middleware has been working with FMOD and FMOD Ex. Both versions of FMOD are extremely powerful yet very easy to use. If I were doing this project using C++ I would not hesitate to use them. But I'm not using C++. Instead I'm using XACT, Microsoft's Cross-platform Audio Creation Tool.

Overall XACT is somewhat less powerful (no module support, no enviornmental effects, less portable etc.) but it's still reasonably simple to work with and supports the features I'm interested in. Specifically I want to support panning and fading of sound based on the position of the object producing it and I want to support doppler shifting based on how fast the object is moving.

Despite XACT being simple it proved to not quite be simple enough to use directly with my game objects. Ideally what I'd want to do is be able to associate a sound with an object then start, stop and alter it without having to worry about stuff like which specific sounds should play and so on. Sounds kinda like FMOD Ex's method of dealing with channels and voices independently eh?

The system I have now is a step in that direction but isn't there yet. For now I'm sticking with it since it works and, for the most part, sounds in Space Combat Sim are really simple so I don't need anything more advanced. My audio class stores an array of some arbitrary number of so-called tracked sounds. Each of these contains a Cue which may or may not be playing, a magic number, and some additional state data.

When I wish to play a sound that will loop, (and therfore need to be stopped manually,) or that I just want to keep track of because it's long, I specify a flag in my PlaySound function that it should be added to the tracked sounds. PlaySound will then choose a slot in the tracked sound array and replace its cue with whatever I wish to play. The PlaySound function then returns a handle, made by mashing the sound's array index and magic number together. When I decide to stop or alter the sound I simply pass the handle to access it. The index and magic number are extracted and, if the magic number matches the one in the tracked sound, the operation is performed on the Cue object.

How does this help? Well, by using a handle with a magic number I can eliminate the possibility of accidently messing with a Cue instance that has been squelched due to a more important/louder sound starting. Howzat? The magic number. My audio class is implemented as a GameComponent and is updated every game tick. If it notices a tracked sound whos Cue has stopped for whatever reason it will increment the magic number and null the Cue reference. If an operation were to be attempted on the, now null, Cue nothing would happen since the magic number has been changed. The only requirement here is to keep the number of magic numbers high enough that numbers aren't recycled until after they're no longer in use, otherwise very hard to diagnose bugs could appear.

Of course now that I've had things working for a while I've learned better ways of doing this which I might try out later. Particularly removing the need to track handles and send position/velocity updates manually from the object playing the sound. But, for now, this is the way things work in the project.

Apologies for the delays

As you can see I just released Part 2 of my series on custom content in XNA Game Studio. I think you can also see that I haven't maintained my promised weekly schedule of blog updates.

It's now nearing the end of the semester and things have gotten quite hectic. The only major issue is that my deadlines are tending to arrive in bunches with assignments coming due all at once so I have to work like mad on non-project stuff then, work like mad on the project until the next wave of assignments hits.

So, what am I up to now? Glad you asked! I'm working on turning my game into something that actually resembles a game. This means adding the ability to target, shoot and kill other players as well as a small host of other features. How many?

1. Create teams
2. Assign players to teams
3. Create spawn points
4. Spawn players at spawn points
5. Timing for when players should spawn
6. Collision detection
7. Rules for damaging fighters
8. Weapon targeting
9. Kill scoring
10. Improved network code

I've finished 1-5 already. They're not thatinteresting to talk about at this point since they don't have much effect at this phase of the project. Most of the real work in getting team assignments, spawning etc. working well will happen in the next couple development phases. What I'm doing now though is feature number 6. And it's a bear of a feature.

Collision detection, in my case, is really about detecting when two objects overlap. A lot of effort is required to figure out whether or not two objects, of any shape or size, are touching or overlapping. So most of my efforts have gone into, first, minimizing the number of objects to be tested, and second, simplifying the math required to find overlaps.

I'm currently using two general tricks to eliminate objects for testing. First, objects are generally defined as groups. For example a fighter isn't just a fighter. It's a hull, wings, thrusters and guns. Capital ships are many pieces of hull and many many guns etc. This allows me to eliminate a large amount of tests very quickly by asking "are these objects close enough to have a chance of overlapping?"

Second is what's known as spatial hashing. This is a way of finding the answer to "are these objects close enough to have a chance of overlapping?" quickly. The basic idea is to take a point in space and assign it to a bucket based on its location. Each bucket represents an area of some size, let's say 50x50x50 units. So if you divide an object's position by 50, you now have the number you need to assign the object to a bucket. All objects that occupy the same bucket get tested for collisions.

Now that we have the objects to test we could just test every object against every other object. e.g. if a bucket has ten objects the result is every object being tested ten times or 100 tests. However what we're really doing is testing pairs of objects. We don't need to test if object A is hitting object B if we already checked object B against object A. We also don't need to test an object against itself. So what do we test?

1. Test the first object against the next nine
2. Test the second object against the next eight
We don't test aginst the first, it's already been tested in step 1
3. Test the third object against the next seven
The previous two steps tested this against the first and second objects
4. Etc.

This means we only need 9 + 8 + ... + 2 + 1, or 45 tests... which do what?

Yes, we're finally at the point of actually doing collision detection. There are two general choices here. First is doing perfect collision detection for the object. This involves a lot of tests for even relatively simple objects, so I'm not doing it. The second choice is to test simplified volumes for overlap. This is what I'm doing.

In my case I'm using two kinds of boxes. First is the axis-aligned box (AABB.) The AABB is useful since I can rapidly eliminate non-collisions by simple value comparisons. The AABB for an object contains the bounding box all objects that are attached as well as the object itself. This helps in eliminating many collisions at once.

This second box is shaped so that it covers the object volume as accurately as possible. This one is used for making the final decision of whether or not two objects are colliding. The math for doing, known as the separating axis theorem, this is somewhat more complex than that for the AABB but not by much. In fact the simple test for the AABB is a special case of the same theorem.

This picture shows all of the boxes involved in a collision test (it also shows a tool I created last week for the purpose of setting these boxes up XD) The AABB is orange and the actual collision volume is yellow.

Sorry about the vagueness of the fighter, it's a test model and I haven't set up lighting for the game yet.

Non-Trivial Custom ContentProcessor - Part 2

If you're reading this for the first time you might want to check out the Introduction and Part 1 first.

The next step taken by the XNA Content Pipeline is to process the data produced by the content importer. This is done by the aptly named ContentProcessor classes. These classes are responsible for pretty much anything that happens between the content being loaded (via ContentImporter or ContentReader which I'll discuss an a later article) and the content being used.

ContentProcessors are used to massage data into a format usable by an XNA project and/or to load additional content. For example a model processor will load textures and shaders that the model is rendered with. So processors usually run when importing content into a game project or when loading imported content as part of game execution.

As I mentioned in Part 1, my custom content importer simply converted the raw XML input into a nice tree that can be worked with by the processor (using the .NET System.Xml family of classes.) Now this XML has to be turned into something meaningful to the game. This obviously leaves a lot of work to the content processor.

As I mentioned before this is the structure of the XML:

• Group (document element)
• One or more entity elements. Each element defines how it's related to the others. In-game this is used to build an n-tree of entity objects with one entity as the root.
• One or more property elements for every entity. The meaning/use of these properties is dependent on the type of entity.

What we'll do in the processor is iterate through all "entity" elements in the document, read in the data we care about, and add each to a content data class called EntityGroupTypeContent. The code to do this is relatively straigtforward and uninteresting. I'm sure it can be improved but at the time I wrote it my main intention was for it to work.

outputGroup = new EntityGroupTypeContent();
XmlElement top = input.DocumentElement;
foreach (XmlElement entity in top.GetElementsByTagName("entity"))
{
    // Read in entity attributes (convert from string as needed)
    string name = entity.GetAttribute("name");
    string parentName = entity.GetAttribute("parent");
    string entityType = entity.GetAttribute("type");
    string renderObjectName = entity.GetAttribute("render-object");
    string[] rawPosition = entity.GetAttribute("position").Split(',');
    Vector3 position = new Vector3(Convert.ToSingle(rawPosition[0]),
                                   Convert.ToSingle(rawPosition[1]),
                                   Convert.ToSingle(rawPosition[2]));

    string[] rawOrientation = entity.GetAttribute("orientation").Split(',');
    Quaternion orientation = new Quaternion(Convert.ToSingle(rawOrientation[0]),
                                            Convert.ToSingle(rawOrientation[1]),
                                            Convert.ToSingle(rawOrientation[2]),
                                            Convert.ToSingle(rawOrientation[3]));

    // Read entity properties
    Dictionary properties = new Dictionary();
    foreach (XmlElement property in entity.GetElementsByTagName("property"))
    {
        string propertyName = property.GetAttribute("name");
        EntityGroupPropertyContent propertyData = new EntityGroupPropertyContent(property);
        properties.Add(propertyName, propertyData);
    }

    // Add the entity
    outputGroup.AddChildEntity(name, parentName, entityType, renderObjectName, position, orientation, properties);
}

Notice the lack of exception handlers on Convert.ToSingle. If something goes wrong here the exception percolates up to the content builder. When this happens the exception is recorded as a build error in Visual Studio. Also notice the EntityGroupPropertyContent instantiation. It's pretty important but talking about it brings up a lot of discussion irrelevant to this entry. I'll talk more about EntityGroupPropertyContent in Parts 3 and 4.

Next we have to validate the data that was loaded. The game expects the following conditions to be true:

• The group has a root entity. Its parent entity is undefined
• There is only one root entity.
• Entities within the group are only related to eachother, not other groups
• Entity properties are valid (notice valid here isn't defined yet, stay tuned :)

Since we didn't verify these conditions in the importer they have to be checked now. This way any errors in the content will be caught by the compiler and show up as build errors. Trying to catch these errors later would result in them crashing the game.

I'll get into validation with Part 3.

This week was umm.... productive?

So anybody reading this might recall me saying I might have more information on how the project is going by this week. The good news is that I did get some stuff, namely, guns actually firing bullets, working. The bad news is that's all I got done this week and that was waay back on Sunday/Monday.

This week has been rather nasty due to other coursework supersceding the main project. Worst was the database course. The project is fairly striaghtforward. Everyone is/was to work in groups of 3-4 people and produce three or four programs that interact with a database tracking the hours of some hypothetical consultants. Very straigtforward... also very boring. The main twists were the intentionally vague specifications and the fact that part of the data, namely the client information (people buying consulting services, not the technobabble meaning of client), had to be on a MySQL database while everything else had to be on SQL Server. That meant a modest amount of extra work. Three/four client applications plus two databases. A nice little chunk of work to disrupt the momentum I had built up for the main project.

While I was definately productive on the database project (finishing my parts, the server and two of the clients, with about three days of work) I got barely anything done on the main project.

The work I did do was to fix/improve object composition. That is I can now make an object in-game out of many smaller objects. For example, a fighter can be made of a hull, two wings and two guns. This is all working well now. The underlying code isn't all that interesting to talk about so I'll refrain from doing so.

As I said before I also got firing bullets working. This really only required the addition of an extra phase in updating the game's state, known as the spawning phase. Any objects that are to be created are placed in a queue. At the end of the update they're created and added to the game. What I want to do now is add a few more rules governing when they're fired. I also need to add the capacity to remove expired objects from the game. Otherwise it will get quickly bogged down by thousands of bullets screaming off into the infinity of deep space.

The Second Nastyish Problem

I now have the critical part of the batching portion working. Objects are decomposed to their smallest constituant parts which can then be rendered in groups. The actual grouping is still to be done but that's relatively straigtforward. I want to be able to measure how slow/fast I'm making my game's graphics before diving in to some hardcore algorithm hacking.

The next nasty problem for me to deal with is the issue of getting the game's controls working across multiple objects. For example, the player's fighter can be composed of a hull, a few guns and several thrusters. Input would need to be affect only relevant objects without causing weird side-effects in the others.

This problem is half solved currently. A single controller object, which is responsible for receiving and processing input from somewhere into actions. Any entity can attach itself to the controller and alter its state based on input from the controller.

A thruster, for example, can decide whether it should turn on based on whether the controller is saying "turn left" or not. This nicely addresses the issue of getting weapons firing in groups, thrusters firing appropriately and so on.

The second half of the problem isn't so easily resolved however. I also have to get state data from the enties that are attached to the controller back to the controller so that they can be sent to the network. My other option is to send complete object state data directly from each entity to/from the network, however that defeats the original purpose of the controller.

An additional problem I didn't quite want to solve this early, but have to, is getting the in-game physics working. This is due to my choice of controlling fighters via believable application of thrust and counter-thrust.

Plenty to mull over. I probably won't have a solution until the end of this week at earliest.