luminance

Programming and Game Development – Kevin Gadd's Blog

Posts Tagged csharp

Bytown Lumberjack HTML5: Behind the scenes

Apr 14

Posted by Kael in Code, Games | No Comments



I recently spent a couple days porting Owen Deery and Gabriel Verdon‘s recent XBLIG release, Bytown Lumberjack, to HTML5 using my .NET to JavaScript compiler, JSIL. This post will go into the process I used and give you some insight into the problems I had to solve to get the game working in-browser, and hopefully help you understand what might be involved in bringing XNA games of your own to the web.

You can play the HTML5 port of the game here.

To begin with, Owen generously gave me access to the source repository for the game, so I checked it out and made sure that it built and ran successfully in Visual Studio. After that, I copied the folder of one of my existing demos and made some minor changes to the HTML & CSS to make it appropriate for the new game – swapping out the title, adjusting the size of the canvas, updating the controls text at the bottom, etc. The next step was to create a configuration file for the game – again, I copied an existing configuration file and made minor adjustments to point it to the right location and adjust the settings for the XNA content processor. With that done, the final step was to actually feed the game to JSIL. To save myself some grief, I made a batch file to run JSILc on the game and its configuration file:

pushd C:\Users\Kevin\Documents\Projects\JSIL\bin
JSILc "C:\Users\Kevin\Documents\Projects\lumberjack\LumberjackPC.sln" "C:\Users\Kevin\Documents\Projects\JSIL\jsil.org\demos\Lumberjack\Lumberjack.jsilconfig"
popd

At this point the first issue revealed itself: The game used some XACT features that the open-source XACT parser I’m using, XapParse, didn’t support. I opened it up in VS and made the appropriate changes to support the features (none of them required significant code changes, just some tweaks to the parser), and then ran JSILc again. This time, the game successfully translated to JS and produced usable manifests.

Next, I edited the HTML to add the manifests that were generated by JSILc:

    <script src="Lumberjack.exe.manifest.js" type="text/javascript"></script>
    <script src="LumberjackContent.contentproj.manifest.js" type="text/javascript"></script>

This part requires a little human know-how since JSILc will often output manifests that you don’t need. For example, if your game has custom content processors, you’ll get a manifest for those, but you don’t need to include that manifest because the game itself will automatically pull in those DLLs.

I started a local web server for testing (python -m http.server to the rescue!) and pointed Chrome at it. (Normally IE is my starting point, since you can run it against file:// and it has a good debugger, but it has audio bugs that I knew would cause problems for Lumberjack.)

The game started and rendered part of the title screen, but I had lots and lots of missing external methods and properties to implement. I stopped the game and made a copy of the console output and started implementing all the missing methods.

My Valiant Battle With The Title Screen

One of the first obstacles was that I hadn’t implemented support for the XNA Effect class, and Lumberjack was using it to do a bloom filter on the game’s visuals. This ended up being easy to implement; all I needed to do was stub out the relevant methods/properties with dummy code. To get it working I also had to extend the XNA content processor in JSILc so that it could copy Effect XNB files to the game’s output directory, to make them available to load. I also stubbed out a handful of missing XACT and GamePad APIs. After this I started the game up and got a mostly complete rendering of the title screen, but the game immediately crashed after that and there were clearly things wrong with the rendering.

To fix the crash, I dug into the error and discovered that the game depended on a XNA behavior I hadn’t implemented. In XNA, when you add a GameComponent to the Game.Components collection, the component’s Initialize method will automatically be called if the game is already running. Because I wasn’t doing this, the component was then accessing uninitialized members containing useful things like textures and shader instances. Reproducing this behavior took a few lines of code and fixed the crash.

JSIL.ImplementExternals("Microsoft.Xna.Framework.GameComponentCollection", function ($) {
  $.RawMethod(false, "$internalCtor", function (game) {
    this._game = game;
    this._ctor();
  });

  $.RawMethod(false, "$OnItemAdded", function (item) {
    if (this._game.initialized) {
      if (typeof (item.Initialize) === "function")
        item.Initialize();
    }
  });
});

Starting the game up again meant it got a bit further and I hit a new crash, this one caused by an edge case in JSIL: The game was casting a nullable enumeration value directly to integer, and JSIL had no support for that. It turned out to be easy to fix, and once it was fixed the game got further in the title screen and I was able to identify more missing externals and stub them in to reduce the number of error messages being spammed to the console.

Another start of the game revealed that it relied on some math APIs that I hadn’t implemented like Math.Exp and MathHelper.Lerp, so I added those in along with some other APIs being used on the title screen.

Reading some of the code for the title screen revealed another JSIL bug: the combination of casting, enumerations and by-reference passing of values was causing JSIL’s support for ref/out parameters to break. This ended up being relatively simple to fix as well.

Wherein An Alpha Channel Is Premultiplied

At this point, the title screen was working, so I started digging into getting it to behave and look the way the actual game’s title screen did. The first thing I did was fix the support for mouse events in JSIL, so that I could interact with the menu using my mouse. I also noticed that the text being rendered on the main menu was badly misaligned, so I fixed that too. Next, I started digging into the rendering issues.

The rendering issues turned out to be caused by two specific problems: First, the game was making use of BlendStates other than AlphaBlend, and I hadn’t implemented any support for configuring blend modes. The second problem was that the Bloom implementation relied on particular pixel shaders, and as JSIL still used pure canvas, there wasn’t a way to implement those shaders. This resulted in the title screen looking blurry and brighter than it should have been.

Implementing BlendState ended up being pretty straightforward – I just had to update GraphicsDevice and SpriteBatch to track BlendStates and add a little bit of logic to apply them to the canvas (by setting globalCompositeOperation to copy, source-over or lighter appropriately).

I spent a bit trying to reproduce the bloom effect using canvas, but eventually it became clear that it would require pixel shaders, so I took the easy way out and entirely stubbed out the component responsible with a Proxy:

namespace Lumberjack.Proxies {
    [JSProxy(
        typeof(BloomPostprocess.BloomComponent),
    )]
    public class BloomComponentProxy {
        protected void LoadContent () {}
        protected void UnloadContent () {}

        public void BeginDraw() {}
        public void Draw (GameTime gameTime) {}
    }
}

And then I added the proxy library to the config file so that it would be applied to Lumberjack’s code during translation:

"Assemblies": {
    "Proxies": [
      "C:\\Users\\Kevin\\Documents\\Projects\\lumberjack\\Lumberjack\\Lumberjack\\bin\\x86\\Debug\\Proxies.dll"

Running the game through JSILc again produced a title screen without the broken bloom effect, and appropriately stubbed out code:

  /* Implementation from BloomPostprocess.BloomComponent */
  $.Method({Static:false, Public:true }, "BeginDraw",
    $sig.get(89342, null, [], []),
    function BeginDraw () {
    }
  );

Starting up the title screen and playing with it a little revealed that while it was mostly working, it looked a bit strange. One of the bugs responsible turned out to be my implementation of Color.Multiply – it turned out that Lumberjack was passing alpha values below 0 and larger than 1 to it, and I was producing positively strange looking colors in response. It was also using SpriteBatch‘s rotation parameter, so I implemented that as well.

Next, I noticed that while the title screen rendered correctly, the transition that played when the game loaded seemed broken compared to the real game. This turned out to be due to a problem with my framerate balancing code that caused the transition to go from beginning to end in a single frame.

Next, I tried opening the Options screen from the main menu, and immediately got a crash. This crash turned out to be caused by invoking GameComponent.Draw on a component without ever calling Update on it, which would happen if the game was running below 60fps due to framerate regulation.

XML: Is It Giving Your Children Cancer? News At Eleven

At this point the title screen was completely working, so I clicked ‘New Game’ and was greeted by a Loading screen followed immediately by a crash. This was a tough one: Lumberjack uses XmlSerializer for levels and saved games. I spent an hour or so fiddling with possible alternatives to XmlSerializer – XNA’s IntermediateSerializer turned out to not be an option because of piss-poor documentation and missing support for critical XmlSerializer features, while JSON wasn’t an option due to the amount of XML involved and the amount of functionality provided by XmlSerializer that I’d have to duplicate anyway.

Looking through the documentation and disassembled code for XmlSerializer didn’t give me much hope. In the past, I’d tangled with it and come away from the experience with little desire to use it again. After a few minutes of despair, however, inspiration struck: SGEN! SGEN is a Microsoft utility designed to improve the performance of XmlSerializer by producing compiled code that can convert each of the types in your application to/from XML. This has the awesome side effect of making the actual XmlSerializer implementation from the .NET runtime library entirely unnecessary and only needing XmlReader/XmlWriter to work.

I added a post-build event to the Lumberjack game project to run it through SGEN and generate code for the type that I cared about:

"C:\Program Files (x86)\Microsoft SDKs\Windows\v7.0A\Bin\NETFX 4.0 Tools\sgen.exe" lumberjack.exe /t:Lumberjack.Level /force

And then I updated the batch file to feed the output into JSILc:

JSILc "C:\Users\Kevin\Documents\Projects\lumberjack\LumberjackPC.sln" "C:\Users\Kevin\Documents\Projects\lumberjack\Lumberjack\Lumberjack\bin\x86\Debug\Lumberjack.XmlSerializers.dll" "C:\Users\Kevin\Documents\Projects\JSIL\jsil.org\demos\Lumberjack\Lumberjack.jsilconfig"

Another run of JSILc produced solid-looking JS output that seemed like it would be able to load levels once I implemented the necessary external methods, so I started by hacking up the generated JS for Lumberjack to make it directly invoke the code produced by SGEN. Attempting to start the game provided me with a long list of missing XmlReader APIs, and then the browser hung because of an infinite loop inside of XmlSerializer. That’s a start!

Now came the tough part: Implementing XmlReader. I set up a simple test harness to run XML test cases in C# and produce JS that I could run in the browser to compare my implementation, and started implementing features one or two at a time.

I spent a few hours hacking on XML, taking heavy advantage of the DOMParser class built into modern web browsers to do some of the heavy lifting for me, and periodically checking with Lumberjack to see whether the level loader would get further and hit more missing external methods. Eventually, I implemented the last few necessary methods and the game successfully loaded its first level. The little intro story sequence appeared, running very slowly, and I clicked through it… only to be greeted by another crash! :(

Gameplay: Do Your Games Really Need It? A Comparative Analysis

Luckily, the crash was a trivial one – my implementation of negation for Vectors was broken, so I fixed it. I hit a serious bug in JSIL that was breaking the game’s collision detection code as soon as the level began. The problem turned out to be that break statements were being omitted from nested switch statements. The fix turned out to be extremely trivial, and yet another example of me being simultaneously too clever and lazy for my own good. While digging through the JavaScript output to identify the switch statement problem, I noticed a few other issues and ended up cleaning up some problems in the JSIL type system to produce better code, because I’m easily distracted.

Wait, wasn’t I porting an XNA game? Oh right. Lots of XNA APIs were being used by the game once the level began, so I went through the painstaking process of implementing most of some of almost all of some of them. In particular, despite being a 2D game it made heavy use of 4×4 transformation matrices, so I had to expand my stubbed implementation of those to be closer to reality.

Distracting, poorly placed aside in an extremely long blog post

At this point I feel compelled to point out that when implementing stuff like XNA library functions, I am aided tremendously by a recently added JSIL feature called GenerateSkeletonsForStubbedAssemblies. If you turn this configuration flag on, any stubbed assemblies it translates will be generated as helpful skeletons, like so:

JSIL.ImplementExternals("Microsoft.Xna.Framework.Graphics.Texture2D", function ($) {
  $.Method({Static:false, Public:false}, ".ctor",
    (new JSIL.MethodSignature(null, [], [])),
    function _ctor () {
      throw new Error('Not implemented');
    }
  );

  $.Method({Static:false, Public:true }, ".ctor",
    (new JSIL.MethodSignature(null, [
          $asms[3].TypeRef("Microsoft.Xna.Framework.Graphics.GraphicsDevice"), $.Int32,
          $.Int32
        ], [])),
    function _ctor (graphicsDevice, width, height) {
      throw new Error('Not implemented');
    }
  );

The skeleton can basically be used as a template for your own implementation of the library – you can copy-paste individual methods or entire classes, and replace the throw statements with your own method implementations (or just a big ugly // FIXME comment). It is an understatement to call this feature a time-saver, just like having your very own undead minions to do hard work for you, but without the clacking of bones and the corpses.

Equally distracting end of distracting aside

Stuttering Turns Out To Be Kind Of Terrible In A Video Game

Shockingly, at this point, the game was working. I could move around the level and attack enemies and get attacked by enemies. I decided to take a short break and test out all the other JSIL test cases, to see if I had broken any of them. Unsurprisingly, I had, so I spent a bit fixing the issues I had introduced, and adding test cases where appropriate.

While the game worked, The problem was, it ran pretty slowly, and in particular, it stuttered really badly when certain things happened – the fades in the opening story sequence were very slow, and any time you hit an enemy or got hit by an enemy, the game would hang for nearly half a second. Some profiling in the Chrome developer tools revealed the culprit to be $jsilxna.getCachedMultipliedImage. I started by fiddling a bit with the code to make it slightly faster and skip calling it in spots where it was unnecessary, along with fixing some related rendering problems. This made the game run a bit faster, but it was still doing some fundamentally unacceptable stuff in order to render the scene. Brute-force optimization wasn’t going to cut it, so I spent a while and figured out a better way to implement that function.

And now, more than you ever wanted to know about GL_MULTIPLY

The purpose of $jsilxna.getCachedMultipliedImage is to simulate color multiplication in HTML5 canvas. Color multiplication is an extremely handy tool used very often in modern games – in OpenGL, it’s known as GL_MULTIPLY and in Direct3D it doesn’t even have a name anymore because you just put it in your pixel shader and forget about it. Typically, in 3D environments you achieve this by attaching a color to each vertex, and multiplying your texture colors by the vertex colors – hence the name MULTIPLY. As always, Canvas doesn’t have a feature like this – it doesn’t really have any features at all except, oddly, for the ability to render blurry drop shadows – so I have to emulate it with a terrible hack.

Up until this point, the hack JSIL used worked like this: Make a copy of the source image, and multiply all the pixels by the specified color, and then draw the copy instead of the source image. As you might expect, this is expensive. And slow. And also very unkind to your RAM. It had been sufficient for the occasional uses of color multiplication in my demos so far, but not for the extensive use of the feature in Lumberjack.

Eventually, I realized that I could implement this feature in Canvas with less significant memory use and lower CPU overhead by splitting it up into smaller pieces. Instead of creating a unique image for each multiplication color, I could create a single set of four images for each image I wanted to multiply, each one of the output images corresponding to a single color channel from the source image:

Once I had those four images, to render any given image multiplied by any given color:

  • First, render the black image (generated from the alpha channel) using the source-over blend mode, and using the color’s alpha as opacity. This produces the same results as if the source image were actually solid black with an alpha channel.
  • Next, for each color channel, render the image for that color channel using the lighter blend mode, and using that color channel as opacity. This means that I will be adding the contents of the red channel to the (now black) framebuffer, and multiplying the red channel by the amount of red in the multiply color.

Following these steps produces roughly the same result as color multiplication in Direct3D/OpenGL, and removes the need to generate a unique image for each unique color. It’s still slower than real 3D, but it’s dramatically faster and it reduces the memory usage significantly.

OK, enough about GL_MULTIPLY, seriously

The Hard Part Is Done! Now It’s Not Unplayable, Just Slow

With that optimization applied, the game ran pretty well – still some stuttering when it had to generate cached images for multiplication, but dramatically less stuttering. In Chrome, it ran at or close to 60FPS almost all of the time, the physics and audio worked, and I could kill enemies and complete levels! I spent a little time profiling it with the Chrome developer tools, but didn’t see anything in JSIL to fix, so I switched to testing it in other browsers and fixing miscellaneous bugs.

At last, after much procrastination, the time had come: Canvas was too slow and I was going to do something about it. I quickly and decisively located a library that somebody had written to solve this problem for me, and then painstakingly dropped it into the JSIL Libraries directory. Hey, look, the game runs faster now! Pleased with the results of my hard work, I hacked up webgl-2d to support some missing features and expose direct access to the equivalent of GL_MULTIPLY, so that I wouldn’t need to cache the channel images at all. With the channel images gone, almost all the stuttering was gone too! The only remaining performance issues were problems with the actual game code.

Thus, I decided to screw around with things that didn’t matter for my own amusement. Behold the fruits of my labour:

Thanks for reading! I hope this long, confusing post has given you some ideas on how to use JSIL and some insight into the challenges you might face. Feel free to comment, or email me with any questions!

You can play the HTML5 port of the game here.

Tags: , , , , ,

Performance Challenges in Compiling Code to JavaScript

Jun 18

Posted by Kael in AltDevBlogADay, Code | 6 Comments

The following post is cross-posted from AltDevBlogADay.

For the past few months, I’ve been working on a tool to compile .NET applications into JavaScript. While there’s a lot of work involved, a large chunk of that is caused by static language idioms that cannot easily be expressed in JavaScript. Even when coding by hand, some of these patterns are difficult to turn into JS that performs well, works correctly, and is easy to understand. In this post, I’ll begin describing some of the challenges involved.

Value Type Semantics

Value type semantics are a common feature in static languages. Most static languages allow you to define custom types that inherit the semantics of the language’s built in primitive value types, so that your struct (or whatever your language happens to call it) behaves much like a single int or float would when being manipulated. This feature makes it possible for custom numeric types (like a fixed-point value, for example) or even composite types like vectors and matrices to follow the same rules.

At first glance, the lack of this feature might not seem significant – especially if you’re used to object oriented programming, it would seem like translating code dependent on these semantics is not an intractable problem. While it’s certainly not impossible, it has a number of downsides that surprised me, especially once I started profiling real-world code in modern JavaScript implementations:

Algorithms designed for value types are slower without them

Those of you who’ve worked with Java are probably familiar with this particular problem already: If you take an algorithm designed around the presence of value types and port it to a language without them, while you can easily preserve behavior by inserting copies in the correct places, you may find that your performance has gone through the floor. The reason for this is simple: In many runtime environments, the cost of an instance of a reference type is significantly larger than the cost of an instance of a value type.

The reasons for this cost tend to vary, but one common trait is that these algorithms produce tremendous amounts of garbage when run in a garbage-collected environment. Some of the more sophisticated garbage collectors provide mechanisms to improve performance for this kind of code, like generational collection and escape analysis, but the sad fact is that even the most sophisticated collectors available still suffer from visible pauses when the collector runs. These pauses not only impair the overall performance of your application, but in games, they cause painful framerate hitching and can even impair the playability of your title.

Another common source of higher costs for instances of reference types is inheritance. In particular, virtual inheritance. Virtual inheritance as implemented in most languages requires every object instance to have a few bytes devoted to identifying its type, via vtable pointers or the like. In some cases compilers can optimize this overhead out, but the overhead is usually there regardless of whether you use it, and in some languages, the default is to make everything virtual – so suddenly even your Vector3 object has a vtable pointer.

A third source of overhead is indirection – reference types almost always live in the application heap, which means they are allocated in a chunk of space dedicated to that particular instance. Even if you allocate an array of your Vector3s, reference type semantics mean that it is probably necessary for the heap to contain an allocation for each one, so that if half of them are destroyed, those resources can be freed and reused by some other data types. Not only does this mean that the simple act of creating that array has become more expensive, but it means that an array of values is no longer guaranteed to be contiguous in memory. Sure, your Vector3[] is contiguous, but all it contains is object references. Hm, what’s that cache locality thing people were talking about again?

(Somewhat obvious pre-emptive nitpick: This last bit here doesn’t apply to C++. But you’re using C++, so you know this already, and you should probably go make sure MSVC hasn’t run out of memory while compiling that boost template instantiation. You know the one.)

Algorithms based on value types are fragile using reference types

Despite the above problems, Java developers are able to produce quality software (depending on who you ask, anyway). The same is true for JavaScript: These algorithms can, with effort, be made to work, and even work well. Unfortunately, there is a significant cost involved. You have to rework your code in order to reduce the amount of garbage it creates, and avoid patterns that naturally require the creation of garbage. For example, in a language like C++, your game probably relies on a math library, featuring structured value types with names like Vector3 and Matrix. If you’re one of those people who likes operator overloading, you’ve probably overloaded various operators for those structures, so that you can write things like this:

The above code is simple and self-explanatory to someone familiar with the basics of algebra (and those of you who abstain from operator overloading have probably written similar code using functions instead of operators). As mentioned above, the performance of such algorithms will suffer badly in a garbage collected environment, but that’s not the worst part. First of all, to correctly translate these algorithms, you must carefully locate all the implied copies contained within the code. As written, the above algorithm is correct even without value types. Let’s convert it to valid JavaScript:

Seems fine, right? But, the keen-eyed reader realizes that a copy is implied in the Add and Multiply operations, so for them to be correct, they must create and return new Vector3 instances. Let’s fix it so it doesn’t produce garbage.

Hm, we need a copy here. That sucks. We’ll just store an extra vector in the object so we don’t need to create garbage. All good, right?

A little ugly, perhaps, but not bad, right? The clarity suffers a little, but we could address that by naming variables more carefully, etc. Not horrible. But wait a second. We pulled the values position and velocity out of an object. If we just modified position and velocity, does that mean we’ve modified the state of the object it came from? Yes, yes it does. Well, we just need to emulate the semantics of value types, right?

Okay, there. It’s correct again now. But wait, garbage collection! Uh, crap. Okay, let’s remove the copies we don’t actually need… we’ll assume that the value of NextPosition isn’t being used, so we don’t need to copy it. And we’re not modifying Position so we don’t need that copy either…

Okay, life is good again. But a week later, you’re reading over commits (sneaky interns keep adding features behind your back, the nerve) and you see something that makes you spit up your coffee:

Luckily, as noted in the comment, the game isn’t using ZoomFactor yet, so it’s always 1. Nothing horrible has happened yet. But now you’re worried, and you’re starting to sweat a little: What other bugs has JDoe introduced that are just waiting to break your code once it hits production? Didn’t this guy develop payment processing systems at a bank? Are your savings in danger? Oh man, what if a bug in code he wrote allows Albanian hackers to steal that money you’ve been saving up for your little startup venture? You might be stuck working here for another 10 years!

Quality algorithms designed without value types are hard to find

So, let’s say you’ve calmed down a little bit after that panic attack earlier. JDoe’s not a bad guy, he’s just new at this. You’ll go through and review his code with him, make sure he understands what he did wrong, and then you’ll add another 5 pages to the company’s ever-growing coding standards document, right after you find a new bank. Life moves on, right?

While you’re doing the code review, though, you run across something that makes you pause. You notice that JDoe modified some code that was written by Chris Beardy, a wizardly programmer type who had already been working here for 8 years when you started out. Nobody really knows what happened to Beardy; one day he just stopped showing up. Until now, his code hadn’t been a problem, since most of it worked great, and the bits that stopped working you just threw out and rewrote (with variable names longer than two characters).

JDoe has done his best to modify the code, and while it seems to work, you realize you don’t know whether it’s correct. You could assume that JDoe messed up, but what if you’re wrong? How can you be sure the code is correct? You ask around the office to see if anyone has Beardy’s phone number, but nobody is even certain if he owned a phone. You try to contact his next of kin but all of their phone numbers bear international dialing codes and it’s 3am in Singapore. This is a problem.

After consulting with a respected colleague, you hit upon a solution: It may be true that neither of you know whether the code is correct, but you know what it was supposed to do. It turns out it’s based on some old academic paper, and the paper’s been cited a bunch of times, and other games use this same algorithm. You figure you can just read a couple of those papers and implement the algorithm yourself – hell, maybe you can find a good implementation out there on the internet that’s fit to use!

Soon after you begin reading the papers, panic begins to set in once again. You’re starting to wonder if that literature major was such a good idea, and trying to remember the stuff you learned in the few math classes you did take. You’re not entirely convinced that these symbols used for variable names exist in any alphabet, and not even your coworkers know what it means when the author writes them upside down. You abandon your paper-reading expedition, reminding yourself that code reuse is better anyway, and as a good engineer you should avoid Not Invented Here syndrome by adopting someone else’s battle-tested implementation…

Now the horror begins. You narrow down the few available implementations for your programming language, rule out the ones that depend on libraries you can’t possibly bundle in, and check with Legal to figure out which specific open-source licenses don’t cause them to flee in terror. You scan over some documentation and things don’t seem too bad. This one is enterprise ready, and you can get a support contract! This one is written using Inversion of Control and Dependency Injection, whatever those are – you think you might have heard someone say something good about them once. You’re feeling pretty okay about things until you pop open the source code. Why are half of the comments in Japanese? This class name is 50 characters long and you’re pretty sure all it’s responsible for is adding numbers. The constructor for one of the key objects creates no less than 8 abstract factories, and two of those only exist to create other abstract factories…

While you start updating your resume, you start to wonder whether you should consider another line of work…

(Now, let’s be completely fair: This one applies to pretty much any programming language, value types or not. But I’ve never been the type of person to let reality interrupt a good rant, so the disclaimer sits here at the end.)

In Conclusion

Now, if you’ve read all this you might be thinking, ‘hey, I’m really offended by that comment about Albanians. What’s wrong with this guy?’. And you’re right, that was kind of offensive. I’m sorry.

You also might be thinking: ‘Wow, this is a really negative perspective on things. Can life really be that bad writing JavaScript? I wrote a webpage once, and it was pretty okay. Google writes whole applications in it and they seem to be making tons of money’. You’re also right! Maybe not as right as that other guy, but hey. I said I’m sorry.

These problems are not insurmountable. In my particular case, since I’m writing a compiler, instead of porting by hand or writing JS from scratch, I can solve these problems using verifiable code, instead of trying to get it right in my head. Despite this, fixing some of these problems involves writing some pretty hairy code – and if you’re like me and your Computer Science background is a little – let’s be generous here and call it ‘weak’ – you may find things like performing escape analysis on functions containing goto statements a tiny bit daunting.

When I finally got my translator working on some real-world game demos after a month or two of hacking, I was really excited; the framerate was bad, but I hadn’t done any optimization, so that was to be expected. When I finally ran a demo through a profiler, though, my heart sank a little: Wait, I’m spending 35% of my CPU time in the garbage collector? And another 20% running the constructor for Vector3? I realized that while I had anticipated the challenges in translating working code into another language, I had not anticipated the challenges involved in translating performant code from one language into performant code in another language. So, I hope that these few examples I’ve provided might give you a little insight.

Tags: , , ,

Compiler-assisted Data Binding with LINQ

Apr 27

Posted by Kael in Code | 3 Comments

When trying to write reliable, maintainable software, it’s important to try and minimize duplication. When you find yourself writing the same magic number in multiple places, you move it into a named constant to eliminate the duplication. When you find yourself writing the same expression multiple times, you move it into a named function, or perhaps a property. Sometimes, you find yourself dealing with higher level duplication – entire concepts and patterns that you find yourself writing again and again. Many modern languages provide tools to help you eliminate this kind of duplication: class inheritance allows you to share common logic between classes by inheriting that logic from a parent class, and generic types allow you to apply a generic pattern to multiple individual types. Both of these tools work with the aid of the compiler, so they interact well with debugging tools and allow you to catch most errors at compile time. Sometimes, though, you run into duplication that can’t easily be eliminated, even with the aid of the compiler.

In many graphical applications, a common pattern is the need to remember user preferences or inputs. Modern languages provide useful tools that can make this task simpler – for example, both Java and C# provide ways to automatically serialize an entire data structure into XML, which eliminates the need to manually read/write your preference values. Unfortunately, even with the aid of these features, you still find yourself with a lot of duplication – even if the runtime can automatically serialize your data structure, you still have to fill the structure out with your preferences, or read them back in manually. I’m going to demonstrate how you can use a little-known aspect of the new LINQ feature in C# 3.5 to eliminate duplication with the aid of the compiler.

As an example, we’ll be using the simple application shown above. It’s a Windows Forms dialog box, with a few different controls, set up to remember user inputs between sessions. You can download the source code for this application below:

Preferences Example (v1)

If you run the application, input some values, and click OK, you’ll find that it stores your inputs in a JSON file in the %AppData%\PreferencesExample folder. If you run it again, you’ll see that it pulls your inputs back out of the JSON file to populate the UI.

Read the rest of this entry »

Tags: , , ,

A managed WebKit library: BerkeliumSharp

Feb 21

Posted by Kael in Code | 27 Comments

I spent the past day or so hacking together a managed wrapper for Sirikata’s Berkelium library. Berkelium allows you to easily embed a WebKit-based browser into games and other applications. It’s based on Chrome and it’s really easy to get up and running in a C++ application. Unfortunately, if you’re using C# or VB.net, you’re out of luck – no way to link directly against a C++ .lib file in those languages. The addition of my managed wrapper – BerkeliumSharp – means that you can use the library in managed applications, and integrate it with Windows Forms, XNA, or even WPF.

I’ve released the source under the BSD license (just like Berkelium) and included two simple examples (one for Windows Forms, one for XNA). It’s not a Chrome competitor but it’s surprisingly easy to get a lot of complicated things working – you can watch Hulu videos if you have Flash installed, and Flash games like Dino Run work in the Windows Forms example since it implements keyboard input.

You can download pre-built demos to test it out, or grab the source code over at Google Code.

Have fun!

P.S. If you try out the examples, be aware that content that opens pop-up windows doesn’t seem to work. I think this is a bug in Berkelium.
Edit: Figured out how to build Chromium and Berkelium myself and fixed the bug. Open source is awesome!

Tags: , , , , , , ,

Achievements and player data II

Sep 3

Posted by Kael in Gruedorf | 2 Comments

In my previous post I gave an introduction to achievements and player data collection. In this post, I’ll cover the remaining two significant pieces: Services and front-ends. Unfortunately neither of these will be quite as complete as the coverage in the previous post, since I haven’t completely finished implementing these parts of my achievement system. Whoops!

Services

Boy, that’s a generic heading. Anyway, so your game is collecting important data on gameplay events, and it’s reporting that data periodically to a web service on your server. Unfortunately, since you haven’t actually written that service yet, it doesn’t seem to be working. Odd how that goes, isn’t it?

The primary issue you have to deal with when building a service to recieve collected data from your game is storing the data. There are other incidental issues – security, performance, serialization, etc – but none of them are of any significance if you can’t find a way to reliably store and access the data. This isn’t a simple problem, but there are ways to handle it.

Essentially, the biggest issue you have to confront here is that you are going to have a lot of data. You may not have a lot of data now, but you will eventually. On one hand, you could spend weeks and weeks trying to design the perfect solution for storing all of this data – but doing that doesn’t actually get your game any closer to shipping, and doesn’t actually guarantee that you won’t have scalability issues down the road. On the other hand, if you completely ignore the problem, you risk losing some of the data you’ve already gathered by discovering significant design issues after you ship. In practice, you probably want to prioritize shipping over the longevity of your data, since (assuming you ship and your game isn’t terrible) you can always get more data.

As a starting point, I decided to build my services on Google App Engine, since it was relatively easy to get up and running and provides fairly generous quotas for free.

Read the rest of this entry »

Tags: , , , , ,

Achievements and player data I

Aug 28

Posted by Kael in Code, Gruedorf | 1 Comment

One of the things I’ve been working on lately is a way to collect and store data on play sessions, so I can track achievements for players and track where players spend the most time in a level, or where they die the most. There are lots of details to get right for a system like this, but I’ve at least gotten a prototype working and started experimenting with ways to visualize the data.

For a system like this you have a few important pieces:

  • Your game needs to collect data during play sessions – in my case, I track important events like player/creature death, and periodically sample the player’s position to get a general idea of where players are in a given level during their session.
  • You need a way for your game to periodically report collected data to a remote server. You have to handle lots of edge cases here – for example, it’s likely some people will play without an active internet connection or suffer temporary loss of connection, so you need to batch up events to report later in this case – you definitely don’t want the game to fall over and choke without access to the internet, and if possible you want to avoid losing data too.
  • You need to build a set of services to collect data from the game. This typically means you also need services to handle things like uniquely identifying individual play sessions and computers, so that you can track achievements for individual players and perform analysis on individual sessions instead of only on a player’s entire play history.
  • You need to build an in-game frontend, to expose collected data to a player. This means turning your event data into user-friendly statistics – like a kill counter, or an achievement for killing a particular boss. One interesting challenge here is that you probably want to expose this information online, too, so that players can share their profiles and achievements.

In this post, I’m going to cover the first two.

Read the rest of this entry »

Tags: , , , , ,

Updating Onscreen Objects / Profiling

Aug 20

Posted by Kael in Code, Gruedorf | 2 Comments

One of the problems I started to run into while polishing things up for my contest entry builds was that as my levels grew larger, the game’s CPU utilization on the 360 steadily grew with them. While PC builds of my game ran smooth on basically all the machines I had access to, on the 360 the cost of updating all the level’s objects and entities became quite significant – most likely due to the 360′s feeble floating-point performance and lack of out-of-order execution.

The solution to this was, at least to me, relatively obvious: My levels were much larger than the camera, so it didn’t really make sense to update the entire level every frame.

The first thing I tried to verify this theory was simply hacking it in: Do a check before updating each object to see if it was onscreen. Interestingly, this didn’t make the game any faster on the 360. Depending on your point of view, this either confirmed or denied my hypothesis: If the problem was simply the cost of all the floating point operations, the cost of doing the onscreen check for each object (since the camera and object bounds were both expressed in floating-point) could have been making the problem worse. Clearly, I didn’t have enough data to be sure about the right choice to make.

So, I spent a day or so rigging up the necessary infrastructure to be able to profile my game on the 360. Since you can’t use tools like CLR Profiler or NProf on the 360, I ended up building a very simple frame timing system, and adding an overlay to the game that would show timing data. This let me get a good idea of how much time each subsystem in the game was using, and then I could compare the costs of individual subsystems, and try making changes and seeing how the profile data changed.

Once I had the profiler up and running on the 360, a clear pattern emerged.

01

Updates were consuming a huge amount of CPU time on the 360. While on my desktop, updates basically accounted for no more than 1% of CPU time, on the 360 they actually accounted for more CPU time than rendering – this was actually a bit of a surprise to me since rendering was definitely the bottleneck at one point on the 360. It seems that at some point along the way, I solved my rendering performance issues on the 360, but didn’t notice because I had made updates so much more expensive – one mistake I plan not to repeat was that I went a week or two without testing the game on the 360, since my 360 was not hooked up at the time. During that span of time I made a lot of changes that drastically altered the game’s performance characteristics, so it was hard to tell what had caused things to degrade.

Read the rest of this entry »

Tags: , , , , ,

Supporting alternate keyboard layouts in XNA games

Aug 14

Posted by Kael in Code, Gruedorf | 3 Comments

If you support keyboard input in your XNA game, one issue you need to be aware of is alternate keyboard layouts. Due to the way the XNA Framework handles keyboard input, if you create your game while using the QWERTY keyboard layout, and a customer runs your game while using the DVORAK keyboard layout, he will have to press different keys on his keyboard. At first, this might seem logical – but consider the typical case:

A customer downloads and installs your game. He’s running it on a Windows PC. He has his keyboard layout set to DVORAK, because he heard it helps reduce wrist strain. His keyboard still has QWERTY labels printed on it, so he presses ‘S’ to type an ‘O’.

He starts your game up, and let’s say the splash screen says ‘Press S to continue’. He presses S on his keyboard.

Nothing happens.

This is because the OS is remapping the S keystroke into an O. For your XNA game to see an S keystroke, he will have to press the semicolon key (;:) instead.

While users with alternate keyboard layouts are a comparative minority compared to people using the QWERTY keyboard layout, that’s no excuse for ignoring them. As it turns out, the solution to this problem is pretty straightforward.

What you need to do is find a way to map a keystroke in your keyboard layout – let’s say QWERTY – to whatever keyboard layout your customer is running at the time. The Win32 API actually makes this quite simple, so as long as you’re willing to include some P/Invoke code in windows builds of your game, you can accomplish this in a couple dozen lines of code.

To accomplish this, I use the following helper struct:

uusing System;
using Microsoft.Xna.Framework.Input;
using System.Runtime.InteropServices;

namespace Labyrinth.Framework {
    public struct LocalizedKeyboardState {
        internal enum MAPVK : uint {
            VK_TO_VSC = 0,
            VSC_TO_VK = 1,
            VK_TO_CHAR = 2
        }

        [DllImport("user32.dll", CallingConvention = CallingConvention.Winapi, CharSet = CharSet.Auto, SetLastError = true)]
        internal extern static uint MapVirtualKeyEx (uint key, MAPVK mappingType, IntPtr keyboardLayout);
        [DllImport("user32.dll", CallingConvention = CallingConvention.Winapi, CharSet = CharSet.Auto, SetLastError = true)]
        internal extern static IntPtr LoadKeyboardLayout (string keyboardLayoutID, uint flags);
        [DllImport("user32.dll", CallingConvention = CallingConvention.Winapi, CharSet = CharSet.Auto, SetLastError = true)]
        internal extern static bool UnloadKeyboardLayout (IntPtr handle);
        [DllImport("user32.dll", CallingConvention = CallingConvention.Winapi, CharSet = CharSet.Auto, SetLastError = true)]
        internal extern static IntPtr GetKeyboardLayout (IntPtr threadId);

        internal const uint KLF_NOTELLSHELL = 0x00000080;

        public struct KeyboardLayout : IDisposable {
            public readonly IntPtr Handle;

            public KeyboardLayout (IntPtr handle) : this() {
                Handle = handle;
            }

            public KeyboardLayout (string keyboardLayoutID)
                : this(LoadKeyboardLayout(keyboardLayoutID, KLF_NOTELLSHELL)) {
            }

            public bool IsDisposed {
                get;
                private set;
            }

            public void Dispose () {
                if (IsDisposed)
                    return;

                UnloadKeyboardLayout(Handle);
                IsDisposed = true;
            }

            public static KeyboardLayout US_English = new KeyboardLayout("00000409");

            public static KeyboardLayout Active {
                get {
                    return new KeyboardLayout(GetKeyboardLayout(IntPtr.Zero));
                }
            }
        }

        public readonly KeyboardState Native;

        public LocalizedKeyboardState (KeyboardState keyboardState) {
            Native = keyboardState;
        }

        public bool IsKeyDown (Keys key, bool isLocalKey) {
            if (!isLocalKey)
                key = USEnglishToLocal(key);

            return Native.IsKeyDown(key);
        }

        public bool IsKeyUp (Keys key, bool isLocalKey) {
            if (!isLocalKey)
                key = USEnglishToLocal(key);

            return Native.IsKeyDown(key);
        }

        public bool IsKeyDown (Keys key) {
            return IsKeyDown(key, false);
        }

        public bool IsKeyUp (Keys key) {
            return IsKeyDown(key, false);
        }

        // Maps a localized character like 'S' to the virtual scan code
        //  for that key on the user's keyboard ('O' in dvorak, for example)
        public static Keys USEnglishToLocal (Keys key) {
            var activeScanCode = MapVirtualKeyEx((uint)key, MAPVK.VK_TO_VSC, KeyboardLayout.US_English.Handle);
            var nativeVirtualCode = MapVirtualKeyEx(activeScanCode, MAPVK.VSC_TO_VK, KeyboardLayout.Active.Handle);

            return (Keys)nativeVirtualCode;
        }
    }
}

Here’s how it works: First, at startup, we ask the Win32 API to load up a specific keyboard layout; US English QWERTY. From then on, we can ask the Win32 API to convert a ‘virtual key’ from that keyboard layout into a scan code. Once we have a scan code, we can then ask the Win32 API to convert that scan code into the equivalent virtual key for the end-user’s keyboard layout. Since the XNA Framework uses virtual keys (the Keys enumeration contains virtual key values), this allows us to apply this technique to existing keyboard input code without any significant changes.

So, with this helper struct, you can add support for alternate keyboard layouts like DVORAK with only a couple changes:

  • First, add the helper struct to your game code somewhere so you have access to it.
  • Replace any uses of the XNA KeyboardState struct with the LocalizedKeyboardState helper struct. If you use some of the more obscure KeyboardState helper methods, you may need to do some work to add them to LocalizedKeyboardState; it only provides IsKeyUp and IsKeyDown.
  • Figure out whether any of the keys you’re using should not be remapped based on the current keyboard layout. For example, it’s common practice for some kinds of games to expose a ‘console’ that allows the user to view log messages and enter commands. In a lot of games, you press the tilde (~) key to open the console. This is a convenient key since it’s near the top left corner of a QWERTY keyboard. However, if you allow the keystroke to be remapped to the current layout, non-QWERTY typists will find they have to press some random key on their keyboard to open the console. In this case, you’ll want to pass a value of true for the second, optional parameter to the IsKeyDown/IsKeyUp helper methods:
if (ks.IsKeyDown(Keys.OemTilde, true))
    ShowConsole();

Tags: , , ,

Constant Binding

Aug 13

Posted by Kael in Code, Gruedorf | No Comments

One of the changes I made in the weeks leading up to my contest deadlines was to pull some of the player-specific combat logic, like that for attack chains, combos, and flinching, out into their own objects. Doing this let me apply that same combat logic to monsters and other entities in the game world, which cut down on duplication considerably.

However, doing this made it clear that I had some architectural issues to tackle: All of these mechanics were heavily dependent on the tunable constants for the creature in question, which meant I couldn’t just pull methods and variables out of my entity classes into classes of their own.

To solve the problem of accessing an object’s constants, I came up with a solution based on reflection. I can define a helper object designed to handle an aspect of an entity’s mechanics – for example, a HealthPool object to manage the creature’s health, along with associated aspects like regeneration. The helper object can define instance variables for the constants it needs access to, like so:

public class HealthPool {
    public Constant<float> HealthMax = null;
    public Constant<float> HealthPassiveRegen = null;
    public Constant<float> HealthRegenDelayTime = null;
    public Constant<float> HealthRegenRampTime = null;
    public Constant<float> FlinchThreshold = null;
    public Constant<float> FlinchThresholdDecay = null;

    public readonly RuntimeEntity Entity;
    public readonly ITimeProvider TimeProvider;
    public float Health = 0.0f;

Note that these variables are the same name and type as the actual tunable constants – the difference is that instead of being static, they’re instance variables. Doing this allows me to pull a function out of an entity’s source code without needing to change the way it references particular constants, since the constants have the exact same names as before.

Of course, since these variables default to null, we need some way to fill them in with references to the actual tunable constants we want to use. To do that, we apply reflection:

public static void BindConstants (object destination, params Type[] sourceTypes) {
    var genericConstant = typeof(Constant<>);
    var destinationType = destination.GetType();
    var destinationFields = new Dictionary<string, FieldInfo>();

    foreach (var field in
        destinationType.GetFields(BindingFlags.Public | BindingFlags.NonPublic | BindingFlags.Instance | BindingFlags.FlattenHierarchy)
    ) {
        var fieldName = field.Name;
        var fieldType = field.FieldType;

        if (!fieldType.IsGenericType || fieldType.GetGenericTypeDefinition() != genericConstant)
            continue;

        destinationFields[fieldName] = field;
    }

    foreach (var sourceType in sourceTypes) {
        foreach (var field in
            sourceType.GetFields(BindingFlags.Public | BindingFlags.NonPublic | BindingFlags.Static | BindingFlags.FlattenHierarchy)
        ) {
            var fieldName = field.Name;
            var fieldType = field.FieldType;

            if (!fieldType.IsGenericType || fieldType.GetGenericTypeDefinition() != genericConstant)
                continue;

            FieldInfo destinationField = null;
            if (destinationFields.TryGetValue(fieldName, out destinationField)) {
                destinationField.SetValue(destination, field.GetValue(null));
                destinationFields.Remove(fieldName);
            }
        }
    }

    if (destinationFields.Count > 0) {
        var constants = String.Join(", ", (from key in destinationFields.Keys select key).ToArray());
        var types = String.Join(", ", (from type in sourceTypes select type.Name).ToArray());

        throw new InvalidDataException(String.Format("Type(s) {0} do not declare the following constants:\n{1}", types, constants));
    }
}

What we’re doing here is pretty simple: We accept a reference to an object that has constants requiring binding, and a list of source types to retrieve constants from. The function operates in two stages: First, we enumerate all the instance variables defined in the target object, and build a list of all the tunable constants it has that need to be bound. After that, we enumerate all the static fields of the provided source types, looking for constants that have names matching those of the instance variables on the target object, binding them where appropriate. After this, we can simply check to see if our list of constants is empty or not – if it’s empty, we successfully bound all our constants, and if it’s not, we know that one or more of the desired constants was missing.

We get a few useful things out of this: First, accepting a list of types allows us to do simple inheritance of constants. If we first check the most-derived type and then the base type of an entity, that allows us to define a ‘default value’ for a particular constant, like ‘Maximum Health’, in a base class, and then define a new constant with the same name in the derived type. This also allows us to create ‘global defaults’ for a given constant – for example, if we always put Game at the end of the type list, we can have global game-wide constants for things like physics parameters, and only override them in specific classes if necessary.

Finally, to wire things up, we just need to do a little work in the constructor for our helper object:

    public HealthPool (RuntimeEntity entity, ITimeProvider timeProvider) {
        Entity = entity;
        TimeProvider = timeProvider;

        ConstantManager.BindConstants(this, entity.GetType(), entity.Game.GetType());

        Health = HealthMax;
    }

In this case, we’re initializing the HealthPool using the constants defined in the entity, and falling back to any constants defined in the Game when the entity doesn’t specify them. If a necessary constant is missing, we’ll get an exception thrown when constructing our helper object. Once we’ve bound the constants, we can just use them like we would otherwise – in this case, the HealthPool automatically initializes itself based on the HealthMax constant.

This is definitely preferable to the approach I used to use for exposing an entity’s constants – previously, for important constants like an entity’s bounding box size, I’d define an abstract property in a base class, and override it in each derived type to return the value of the constant. Now, I don’t need to use any abstract members or interfaces; I can just bind to the constants once when I initialize my helper objects.

One thing of note is that since this technique uses reflection, you might run into performance issues if you’re binding constants repeatedly. This is pretty trivial to solve, however; you can just cache the results of a constant binding operation based on the destination and source types, since those aren’t going to change at runtime.

Tags: , , ,

Home stretch

Jul 30

Posted by Kael in Gruedorf | 2 Comments

In the next two weeks I have deadlines for two different contests coming up, so things are getting pretty hectic. Lots of things changed in the ~100 or so commits since the last blog post, so I’ll pick a few to describe.

Read the rest of this entry »

Tags: , , , ,