Particles - Part Deux - The Sequel

The Movie - The Game - The... I'll stop now.

It's been another long hiatus since my last entry where I discussed a bunch of semi-boring crap about how stuff gets loaded in Space Combat Sim. Last week (that is the week ending on the 13th) I worked out the protocol for sending the initial game state from one player to another. That part is running somewhat nicely though I've got a bunch of other broken crap to fix before I can really give the details of what I'm doing.

This week, as you may guess, I'm going to talk about particle effects! Yay! Celebration!!! Peanut butter!

Ahem. Last part I discussed some basic theory on particle effects and had a pretty screenshot from an old project. Now I was hoping to talk about a clever method I had devised for making really versatile effects with relatively little shader code and some HLSL snippets. The idea was to store positional, colour and scaling data in the form of textures. Unfortunately this method turned out to be less than workable.

The idea originated when I was mulling over using cubics, or higher order functions to define the movement and other functions for particles. I figured this would result in a great deal of operations since the function would have to be completely integrated every time a particle gets rendered. At some point I began thinking about such functions in relation to producing complex colour gradients that the particles would run through as they did their thing. I got the idea that if I used a texture I could get a great deal of versatility. By using one texture co-ordinate to represent time and using a random value for the second I could have a particle effect with tens or hundreds of subtly different colour gradients with the hardware doing all of the hard interpolation work practically for free.

After a little more thought I figured this could be applied to particle positioning. Much in the way a normal map texture's colours represent vectors instead of actual colours I could have a texture whose colours represent a position in space. Depending on implementation this might add expense in the form of providing a normal, tangent and binormal to individual points sprites. Lots of floats but makes for very simple math in aiming a particle effect in a particular direction.

So, where did this go wrong? A few places. The first, and biggest, was that doing texture lookups in the vertex shader (which is where effects are applied to points sent to the graphics hardware) is apparently unsupported. If anyone knows a way of doing texture lookups in the vertex shader PLEASE TELL ME. This wasn't enough to prevent me from using the texture to provide fancy colour gradients however. Instead of looking up the colour in the vertex shader I'd simply pass the co-ordinates (time, and a random value) on to the pixel shader. So, it's not a complete loss.

I have yet to implement the gradient texture due to some stupidity on my part (I used a texture co-ordinate at first which the hardware happily interpolated for me utterly destroying my lookup values.) I can probably salvage it by passing the lookup in a colour semantic since those aren't interpolated. For now I am lerping between a randomly selected starting and ending colour.

What I have now is basically a stripped down version of Microsoft's Particle3D sample which I'm mutating into a setup that meets my needs. I'll leave you with a screenshot of my particle effect editor tool to finish.

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

Don't Worry, I'm Still Here

Sorry about missing last week.
I'm busy as hell working at the final (though it will probably change still at this stage) game startup sequence. I've got things working nicely now and will have a more detailed update soon. The load sequence is somewhat interesting and I think worthy of a couple paragraphs on this humble blog... later.

I'm also busy with revamping, and hopefully near-finalizing, the network protocol for the game. I'm giving particular attention to the sequence of events and data transfers that occurs when a player first joins the game.

If you remember in a previous entry I mentioned how this was the most time-consuming part of an earlier sprint. Given some further (and much briefer thought) I've created a much improved process and am throwing away pretty much all of my old network code in favour of a new solution which should support all of the events that may occur in the final game. All of this I'll write about, in more detail, tomorrow.

Off topic for a second...
I was visiting my parents earlier today for some delicious chicken and potatoes. I also got to see a bit of my brother's new score in gaming. He's picked up a copy of X3: Terran Conflict. This was a game that I've been moderately interested in acquiring myself. Unfortunately I only got to see a bit of a tutorial mission which was mildly, but irritatingly, broken. My brother was piloting an unarmed freight ship but the instructor, inexplicably, was telling him to blow up debris containers despite being unarmed. Needless to say he had to abort the tutorial at this point... going without any remaining information that could have been provided.

I hung around for a few more minutes. What I saw implied a large, freeform game universe. I'm strongly reminded of EVE Online, Freelancer and/or (what I've heard of) Privateer. Sadly, I didn't get to see much more since my brother seemed more interested in reading about bread factories than exploring the world.

However, based on what I've seen I'll definately look to pick up a copy for myself some time. The best part is I don't have to worry about Starforce, SecurROM (sp?) or any other bullshit DRM. I can either get it through Steam or pick up a DRM-free box somewhere. Even if the game turns out to be less cool than I'm thinking it will I'll still be more than happy to support a developer who's willing to not include pseudo-malware in their products.

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.

Another Late Entry

So here's yet another late entry. Once again, sorry for not keeping to my "at least once a week" schedule. This time I don't really have an excuse since school is finally over for Christmas and New Year.

What's happened? Well, lessee...

• Collision detection is finished
• Damage model is finished
• Demonstrated the project to the rest of the 3rd year class
• Wrote up some extra documentation for the faculty's benefit

I ended up ditching one of the collision test elimination methods I mentioned previously. Testing the objects in game, hierarchically (i.e. test a group to eliminate all related objects) added complexity that cost more than the benefit of eliminating a few collisions early on. Additionally a commonish edge case makes the algorithm design slightly hairier than my initial plan which was to use a breadth-first search. The AABB of each group of objects on a given level in the hierarchy would be tested, any non-overlapping branches would be eliminated from further testing. Collisions would then be fired for overlaps between objects at the lowest level of the hierarchy. Astute readers might see a potential problem here.

Collidable objects can be attached to other collidable objects objects across different levels in the entity hierarchy. Because of this collisions can occur at different levels of the hierarchy. In fact collisions can even occur across multiple levels in the entity hierarchy. For example, a fighter's gun can touch another fighters hull and the attached wing. This has to be taken into account. The additional complexity, during my testing, amounted to more CPU work than simply testing all object AABBs within a spatial hash bucket without grouping them.

A plausible compromise would be to use the grouping only as a first-pass (i.e. whole group) method of eliminating collisions. This would probably give the best bang for the buck since group parents are easy to find (removing the pain of implementing breadth-first with the current entity storage system, a giant array) and, in the case of capital ships, a LOT of collision tests can be eliminated at once. For now though, this solution doesn't exist. I'll probably add it when I have the time.

Speaking of time, the previous sprint (number three for those who care) finished seriously behind schedule with an estimated 50ish hours of work leftover. For comparison purposes, the faculty expects a bit less than that amount of work to be done per person per sprint.

I am now confronting the pile of unfinished work and attempting to catch up to where I originally wanted to be at the halfway point for the project. This particular sprint, currently set up to occupy my between-semester vacation time, I decided to focus on eye and ear candy in addition to the neglected work from sprint 3.

• Positional audio
• Particle effects (running on the GPU no less, though I got the original code/concept from Microsoft's sample code at the XNA Community site)
• Lighting, at least some basic global lights and hopefully an initial shadowing model
• Fixing an amusing, but mysterious, off-by-one-frame bug in the view (or world) matrix of some objects

I'll talk about my plans, and completed development, for positional audio and particle effects in the next couple days this week. Perhaps I'll have something screenshot worthy soon...

I'll also try to find some time to get another Content Pipeline series entry written up.