Happy Holidays everyone!

Couldn’t think of a better title right now 😉

I’m enjoying a week break from work, nothing fancy, just family time and catching up on my projects. And fixing my computer that chose the right time to break.

I’ve got a couple of ideas for NSN that I will try to implement this week, or at least document well enough to be able to do it later. I’ve listed last week the things to do before public release, as I wanted to figure out precisely how much work was left and how much external help I needed. I might post that list here later. Anyway, once the list was done, I went through some of the items, and got ideas coming.

And I’ve decided to publicize some of my projects, both to get some help and to provide me with the motivation boost I need to complete them. So hello TIGSourcers! 😉

Project on hold

As might be obvious with the lack of updates, NSN is currently on hold.

Since I’ve taken up a new job, I have too much to do and not enough spare time, so I must make choices. This is a project I’m deeply involved with, I really want to publish it someday, maybe on the XBox360, maybe elsewhere.

If somebody were to offer me help to complete the project, by providing content, or new ways to fix the AI, I would make it my priority. In the mean time, I’ll still give it a thought from time to time, maybe implement things when inspiration strikes, but no more than that.

Savegame system: complete!

After some hard work, quite a lot of refactoring, and new code pumped into the game, I’ve finished the save game system.

To be more precise, I’ve brought it to a ‘beta’ state, it now needs lots of testing, more safeties added, etc. But I’ve nailed the very difficult parts: restoring links between entities, or dependencies. For instance, let’s say I have a mission for the player, which involves attacking an enemy. I need to save the mission with some kind of reference to the enemy, then when loading, I need to work out what that reference means and find the re-loaded enemy. This has several difficulties to it, like setting a unique identifier, managing load order dependencies, etc. And this kind of link is quite everywhere in NSN: missions, AI, A-Life, etc.

The other major change I’ve made to the savegame system is using built-in GZIP compression from the .NET Framework. See MSDN page on GZipStream. It’s not a huge compression, but it’s good enough. I must make more tests on the XBox360 of course, but it gave me a factor 3 to 15 compression (guessing from usual file sizes, they vary a lot, see my PGC posts for the reasons).

The compression make me discover it wasn’t only the ‘save to disk’ part that caused a pause in gameplay when triggering a save. That means I can’t do the autosave feature currently without threading or pausing the game. Well, that’s for later. Now I have some gameplay improvements to make, some more visual enhancements and I will be ready to hit play test.

Savegame system back online

After some hard work, I’ve re-added the savegame system, then fixed it so doesn’t crash when saving/loading. I’ve also created some support code that enables a massive file size reduction, while still keeping the existing XML based system. And I’ve started filling the gaps in the savegame. It’s not complete yet, but it’s getting closer now.

I had to disable it sometime before the DBP deadline when I saw the amount of work remaining. I had to choose between saving/reloading and doing a thousand other things, like content and polish. I picked up content over saving, and so limited the ‘campaign’ to a shorter demo that I was intending at first.

This taught me a good lesson: never put the savegame system as a low priority ‘to be done at the end’ task. Of course, if you’re only saving the high scores and sound volume preferences, that’s no big deal. But for a game with progress saving, it is a big task, all entities should be designed with save/load support in mind, maybe automatic serialization, if possible.

In my case, automatic serialization isn’t practical, due to huge file size and multiple dependencies (OK, the dependencies could be fixed). So I’m writing it all by hand. For instance, take a good care at how things are setup, how the data is loaded, what kind of loading order dependencies there are, etc. I’ve made mistakes with some classes that can’t be instantiated with default values, then setup, then their content loaded.

Anyway, enough technical discussion! What this means is: the project is getting nearer release! The savegame system is the last major feature I need to have working before release. After that, there is only polish and content to be done. Which isn’t easy and quick either, but it doesn’t feel like a huge wall in front of me. And it will enable adding much more story missions, as testing them would become practical again, not having to play through the whole game each time I want to test one 😉

Optimizing

I spent quite a lot of time profiling and optimizing NSN this past week.

It’s a very tedious process, but it’s also quite rewarding, as I went from unplayable in heavy situations to slight slowdown. All this is only on XBoxx360, the PC version fares much better, at least on my own PC. Here are some details.

Once again, I was surprised to see some hidden allocations in an official sample. The particles engine is allocating new Queue<T> instance when it pleases. Which is very often if you use it, each time an effect is spawned, the whole chain is either Initialized (unsurprisingly allocating memory) or Reset (*surprisingly* allocating this Queue instance). Well, no more of that, I’ve replaced the ParticleCache class by my own generic pool implementation, et voila!

But while I was tearing my hair over CLR Profiler‘s output, I made a break to check the XBox360 performance after my optimizations. It was a bit better, but not that much. What is much more important, I realized, looking at the Remote Performance Tool, that memory wasn’t the major issue. In fact, the GC wasn’t kicking in during the major slowdowns I was experiencing.

So I went back to my PC and changed tool. Instead of profiling memory allocations, I started checking CPU performance. I’m using NProf for that, it’s a statistical profiler for .NET which does the job in a quick and non-intrusive way. It gave me a new culprit: the sound management, and especially, the 3D positioning updates. Removing some of it, and simplifying some more related code gave me a very nice performance boost. So I will ditch the AI ships’ engine sound, it was barely audible, more annoying than anything else, and VERY costly, due to frequent start/stop (the AI behavior in combat is causing this) + computing 3D positioning relative to player.

Now I can go back to finishing the game, knowing that it runs or will run fine on XBox360. I’ve done some minor improvements and bug fixes already, but nothing like the amount of work left before publishing. Anyway, back to the topic!

I’m currently considering the use of an internal profiler, to help me locate remaining bottlenecks on the XBox360. NProf is good at what it does, but that’s on PC, and my PC isn’t a XBox360, CPU, GPU and whole architecture are different, some insignificant code for the PC might be a major block for the XBox360. I’ve got an article by Shawn Hargreaves handy for tips and good advice (especially, use NProf + the internal tool, not just the internal tool), it doesn’t sound like too much work, so I think I will do it.

Procedurally Generated Content

Introduction

Procedurally Generated Content (or PGC for short) is a very pompous name for something that can range from pure random generation to wizardry. It means that Content is created by programming a Generator inside the game (often done at loading time, can be real time also), instead of designed using external tools. Any kind of content can be PGC. A very well known example, with a good execution of the idea, is the levels of Worms.

Now, how does that fit into NSN?

Basic example

The starfield component I’m using for backdrops is PGC. It uses a bitmap (grayscale) to generate a cloudy background, looking like nebulae, and it generates some random ‘stars’ at varying depths, moving with a classic parallax effect. This is PGC because the final result isn’t visible by looking at the data. It uses a shader that takes some data as input, but the final render looks nothing like the grayscale texture. And the stars simply don’t exist in data, their texture and positions are code-generated at load time. For those interested, the C# and HLSL code and texture where taken originally from the Net Rumble sample, then heavily customized for my game (including a partial rewrite of the shader to enable hue variations).

The real thing

But that is not by far the most exciting use of PGC in Next Stop: Nowhere! It is also featured in universe generation.

The current (maybe not final) algorithm is combining some human input with random generation to make a playable universe. The whole process goes something like this:

Design time:

• Design a sketch of a level using Paint.NET. I make sure it features interesting locations to place missions and random encounters.
• Redraw that sketch using zones instead of point/fixed locations.
• Convert that to usable data for input into the generation algorithm. It’s currently done by hand (set up into arrays), could be automatized.
• Decide the size (N) of the universe. In the version submitted for DBP, it was 3×3, it should be much greater in final version, thanks to optimizations.

Loading time:

• Prepare N levels (dubbed ‘Quadrants’ in game). Those are squared areas in which the player can freely move without loading or transition.
• Choose a template from the available list.
• Create each item in the template (stations, asteroid fields, etc…).
• Position and size are randomly picked in the range defined at design time.
• Setup level background (non colliding asteroids, tint, etc…).
• Ensure level validity and proceed to next one.

Playing time:

• Set the player on his starting location.
• While player stays in same level, nothing to do.
• When player changes level, activate the area, disable the previous one (this may change before final version).

Conclusion

That’s it! With a limited design work, I obtain a vast playfield, and different on each play.

I’ve found a downside to that approach while deadline was coming near: the amount of data in the save file is BIG! It requires some subtlety that was really lacking in my ‘dump everything in XML’ approach. So, I’ve disabled it, for lack of time to fully support save and the QA risks associated with this. And I kept the ‘adventure’ short. Only a few missions to give a nice taste of the game, but not a full fledged scenario yet, as it wouldn’t be playable in one single session.

On the contrary, this approach gives me a great flexibility in data. It enables the creation of levels with known ‘landmarks’, for instance an ambush area for pirates over merchants, that can be used in scenario missions with placeholder, or limited initial data. Then I can gradually improve diversity of props, change rendering from 2D texture to animated sprite or 3D model without throwing my level design out.

NSN features

Game thumbnail

As the game isn’t yet available, I thought I’d make a virtual tour of NSN, to build interest and gain feedback.

Simply put, Next Stop: Nowhere! is a 2D space roaming shooter with depth. It is a space shooter, no denying it: you’re in control of a spaceship and you blast other ships (and props). But it has a lot more to offer.

Firstly, it’s not a side or vertical scroller. You get to go wherever you want in a top-down viewed universe (well, I know ‘top-down’ doesn’t make ANY sense in a ‘universe’, but it’s a game, mmm? 🙂 And the universe is flat, everyone knows that anyway! ;-)). I very much wanted to give a sensation of space, of freedom and use it to create interesting events and settings (ambushes, patrols, etc).

One important key feature also is that the universe is procedurally generated. What does this mean for the player? Discovery and replayability. Creating it programatically as opposed to fully level designed allows me to have a much bigger universe, a little more chaotic than I would have made it by hand. I will explain the system in details in another blog entry.

Now the depth. This is not a mindless shooter, like, not at all. It’s much more a sandbox-style game. If you go an a rampage against law-abiding space citizens, you’ll have to avoid military controlled space. On the other hand, if you hunt pirates, you’d be more popular with the police, but shot on sight by outlaws. Then there is trade. You can upgrade your ship, buy a better one and so on, but not only. You can also buy and sell various items, raw minerals and precious gems, that you might obtain in several ways: buying from a merchant on a station, mining from asteroids (obviously you will get only raw stuff from asteroids), looting from destroyed ships or sometimes when completing missions. Which leads me to…

Missions. Yes there are missions. There are ALWAYS missions. Wherever you go, each time you find a space station, there will be something to do. Whether it’s a dull, uneventful patrol around the station or a raid against neighbors or playing babysitter for frightened roaming merchants wanting to cross pirate-controlled space or a request that you go explore an uncharted area of the galaxy will depend on the moment and the location and type of the station. And there is another kind of missions, those advancing the story line. You will be lead to discover the galaxy, and its numerous denizens and their plots, if you choose to play these. Some will change the face of the universe, no kidding.

A-life (short for Artificial Life) is the last feature I’ll talk about now. That was always a favorite of mine and it features prominently in this game. I’ve already mentioned the missions, they’re a part of the A-life system. Many things are constantly generated to populate the universe in the most convincing way possible. Apart from missions, there are rumors which you can pick up in stations, patrollers, pirates, merchants and miners that you can see flying around doing their job, and attacking or fleeing you. There is a market system, which governs prices based on offer/demand, so your actions have an impact: if you disrupt trade or help it, prices will go up or down; if you find a large deposit of mineral when mining and bring it back, prices will drop, etc… And of course, there is the combat AI, which is not wave based or pattern based like in most shoot’em up/scrollers. The AI ships follow the same dynamics rules as the player’s, so the AI is really thrusting and steering as the player is doing. This is all to make them feel more ‘alive’ or ‘lifelike’ and less like painted targets. They have rules of engagement, which means they will attack you on their own if you fly nearby and are hostile, or they will flee you if they feel overpowered and in danger.

Well, that’s all for this entry!

Garbage’s out, Pools are in!

I’ve nearly completed my first major optimization pass: removing runtime memory allocations. I’ve removed string allocations, then I found all the sources of boxing garbage and removed them too. Here are some examples, they might benefit others.

I’ve made custom generic containers to handle game entities. I was iterating over them using the nice foreach construct. That’s cool, but, you guessed it, it was generating garbage. Why? Because I was implementing IEnumerable<T>.

public class AutoList<T> : IEnumerable<T>
{
    private List<T> m_List;

    public IEnumerator<T> GetEnumerator()
    {
        return m_List.GetEnumerator();
    }
}

The problem here is returning a IEnumerator<T>. This causes boxing (conversion to an interface). Disassembly in Reflector make this obvious. So what’s the solution?

I haven’t found a perfect solution, but simply removing the IEnumerator<T> implementation and returning List<T>.Enumerator for GetEnumerator still allows foreach and is garbage free.

public class AutoList<T>
{
    private List<T> m_List;

    public List<T>.Enumerator GetEnumerator()
    {
        return m_List.GetEnumerator();
    }
}

I’ve found other sources of garbage, and dealt with them the fastest way. In the Primitives3D sample:

foreach (EffectPass effectPass in effect.CurrentTechnique.Passes)

Replaced by

int passesCount = effect.CurrentTechnique.Passes.Count;
for (int pass = 0; pass != passesCount; pass++)
    EffectPass effectPass = effect.CurrentTechnique.Passes[pass];

Maybe not so elegant, but efficient.

Using Nick Gravelyn’s excellent advice (I’d suggest reading his blog here, see forum thread), I’ve improved the garbage removal from my input wrapper (Dictionary) by implementing a IEqualityComparer class for my enum type. That enables still using enum without casting to ints, and also without boxing. It’s a bit tedious to write such trivial classes, but there are good .NET reasons below, the enum type providing nice facilities for that price.

Finally, I’ve started removing the sources of garbage collection really caused by my code. By really I mean: where I’m using new on reference types, really allocating memory on the garbage collector’s heap. And so I’ve created two generic Pool classes, one which is enumerable (as shown above of course), and the other not (pure pool). I can detail them if people are interested, for now I’d just paste the header, which contain an interesting use of C#’s generics, to ensure type is usable by Pool class:

public class BasicPool where T: class, new()

There is a lot of A-Life in NSN, so there were lots of allocations, the three more common being AI ships, missions and rumors. The ships are now using a pure pool, the missions and rumors shall use the enumerable version.

And that’s all for this very technical post. I will later write more general stuff, to avoid boring non-programmers 🙂

DBP Media

Below are the screenshots I’ve uploaded for the DBP entry. They are untouched Windows screengrabs (click for full size). Which was wrong, since the format requested wasn’t full 720p (1280×720) but 1000×562, well, my entry has been accepted, even if the screenshots won’t display properly in the official gallery.

Oh, and the required video on YouTube:
First gameplay trailer

Enjoy!

Blow up stuff!

Escort a merchant

Mining

PS: can you spot the bug shown briefly in the video? 🙂

GC hunt

Yesterday I started a big GC hunt, but before I relate this, some history…

Just before the final submission deadline, I did some testing on XBox360 that I hadn’t done for weeks. Of course, this was a terrible mistake, but time was really too short for me, so priorities were features first, test later. Well, as I’d half expected, it was incredibly bad. The game was just unplayable in its state, which was bad, since I had only 2 or 3 days left.

First I thought I had been too ambitious, with too much entities, and that the CPU just couldn’t keep up (no threading at all btw). So I reduced the load, not updating all levels but just the active one, reducing background entity count, etc. It did improve the situation, but not much.

Then I checked the forums and blogs about garbage collector issues. I finally ended on Shawn Hargreaves’ excellent double blog post on the issue : first and second. This lead me to proper use of the XNA Framework Remote Performance Monitor, which showed me terrible GC state (I remember seeing 3 whole seconds of GC over only a couple minutes stuttered gameplay).

But I hadn’t enough time at the moment to do more than plug the biggest holes, and attempt to ‘improve’ the situation by some choice calls to GC.Collect().

Now that the deadline is past, I’ve come back to do some cleanup. And I’ve discovered some things along the way.

• You can display strings using XNA without creating garbage. StringBuilder versions of required methods exists.
• StringBuilder is not the friend you’d wish for. sb.Append(int) generates garbage. So I’ve done my own itoa() method. See XNA Forum thread for discussion and solutions.
• Don’t trust too much official samples. I’ve been using input wrapper from a sample (can’t remember which right now, maybe Spacewar), which is generating an awful lot of boxing (48 per update in my case, that’s ~2800 / second) since it uses a Dictionary<enum, list> to store key mappings. Same goes for Particle sample (2D using XML loader), but it isn’t generating near the same amount of garbage).

I’m not GC free right now, but stutter on XBox has reduced to barely noticeable, so I’m on the right track!

More on that as it comes 😉