Sunday, February 16, 2014

Porting my Chaos remake to the web

Today I've uploaded a new version of Chaos to the Android Play store, updated the Game Boy Advance and Nintendo ports and also managed to make Chaos run in your browser. Here's a bit of waffle on how I went about that last part.

Over the years the remake I made of the ZX Spectrum classic Chaos has undergone about 3 rewrites.
  • the first version I wrote for the Game Boy Advance from scratch. The Speccy version was inspiration, but it wasn't an accurate remake.
  • the next version was a lot closer to the original, created by carefully reading through the Z80 code to get all the gameplay spot on
  • I rewrote the game for the Nintendo DS as an independent code base in C++, which also compiled against the SDL library so I could test on a PC
  • for the Android port I went back to the 2nd version's C code, making sure that this time the same codebase compiled for the GBA, DS, SDL and Android NDK without tons of #ifdef statements
All this means that the code is portable, or at least it has had its most unportable edges smushed off, currently compiling and running on 4 different platforms (GBA, DS, Android, SDL). It uses GNU autotools as the build system. This is not pleasant, but autotools has more working features than any other build system, and it makes it possible to cross-compile the code.

For the last year or two I've been keeping an eye on the emscripten project too. Emscripten uses the Clang compiler to compile C or C++ code to JavaScript. This can then run in any modern web browser. I thought that it would be fun to get Chaos cross-compiled to JavaScript.

Emscripten even has some SDL support for graphics and sound. This it achieves by cleverly translating SDL function calls to the equivalent HTML5 canvas calls and wrapping the web audio API. I assumed this all meant it would be easy to get the job done. Sadly my lack of game design chops meant it was a lot more work than I initially expected.

Let's see how I made my life difficult.



On the GBA you have complete control over the hardware your program is running on. As only one program can run at a time, and the GBA has no operating system to keep track of things, you can use 100% of the CPU. In fact if you aren't careful you can waste the battery by "spin-waiting" when you need to wait for input from the user or when your game isn't doing much. Spin-waiting means code that just loops on the same instructions over and over until a condition changes. It is easy to understand, but inefficient as it still executes instructions.



The GBA has a way to say "OK, I'm not doing anything for a while, please turn off the processor and wait for the next video frame to tick by". In this special low-power waiting mode the GBA uses less battery, so using this technique is a good idea.

On the GBA I had full control for Chaos, and I had to add these waits in when the game wasn't doing much or was waiting for user input. I wrote code that stopped wherever it was to hang around and wait for the next thing to do.

Now back to game design. A classic game loop has 3 jobs - running the game logic, drawing the graphics and going neither too fast nor too slow.

while (true) {
        do_stuff();
        render_screen();
        wait_a_bit();
}

Things can get complicated - wait_a_bit in particular goes off the deep end when do_stuff contains complex physics models - but that's the basic idea, and for Chaos it would be more than enough. What turned out to be the problem with my code was that as well as the main loop, which was similar to the above snippet, I also had lots of mini-game-loops scattered throughout the code.

Imagine what happens when you want to move a wizard off a horse or centaur.




In Chaos the game stops to ask you if you want to dismount. This stopping-to-ask was another game loop stuck right in the middle of the code for selecting a creature to move. On the GBA, DS, SDL, and Android ports this wasn't much of a problem. On the GBA and DS I have full control of what's going on. For the Android/SDL ports I use threads, mutexes and signals to coordinate things, essentially emulating the way the GBA behaves anyway.

When it came to a JavaScript port this just didn't cut it. JavaScript requires that the browser controls the "wait a bit" part of the game loop, and it has no C-style threads with shared state. When you compile C code with emscripten, instead of the while loop posted above you need something more like this:

void one_frame(void)
{
        do_stuff();
        render_screen();
}

int main(void)
{
        emscripten_set_main_loop(one_frame, 00);
}

Here emscripten_set_main_loop makes sure it calls your one_frame function once for each game loop at the rate you ask it. The rate here is 0, 0 - which possibly means "whenever you like".

When the game is deep in the "do stuff" part of the main loop, and it needs to do the "wait for a bit" thing… well, in JavaScript you can't do that. The code would have to return all the way back to the main loop, pass control back to the browser, then carry on where it was when the browser returns control.

Being a lazy sod, I didn't want to have to rewrite everything. In fact, at first I couldn't see how I could rewrite anything to make the game work with in this environment.

Then I thought about that previous phrase - the code would have to return all the way back to the main loop … then carry on where it was when the browser returns control - and I realised that what I needed here were coroutines.

What a coroutine lets you do is yield control from the middle of a function, but when the program calls the function again instead of starting from the start of the function, it continues on from where it yielded last time. A language such as Lua has this built in with the yield keyword, making it trivial to do. In C, everyone who needs coroutines uses Simon Tatham's coroutine macros.

I still had to come up with a way to call any routine that needed to wait again, and it still needed a bunch of changes. But the basics were there, and I wouldn't need to rewrite everything all at once.
I came up with fake asynchronous functions - these were not really asynchronous, but the code adds each function to a list that the program would later call one by one from the main loop when this loop was ready. If the function returns 1 it means that the main loop needs to call the function again, but if it returns 0 then the function has finished and the program should take this function off the list of pending items.

Coupling this with the coroutines meant I could have fake thread-like behaviour on a single main loop. I had to be a bit careful since, as with regular threads, the code could have "race conditions". If the code changed a variable after adding an asynchronous function to the pending queue, but before the main loop calls the function, then it might not do what I expected. But at least the race conditions were deterministic here, unlike regular threads which can have subtle timing problems.

Another change I had to make was to switch from using SDL sound mixed in a buffer using the older API, to use the SDL_mixer library. This cut down on code, so for that alone it was a good idea, and made sound effects in the browser work without further changes! The sounds are OGG files, converted from the WAV file originals. I didn't need to change the build system much for this as I was already generating OGG files for the Android version.

The emscripten C compiler/linker has a flag --preload-file that creates the equivalent of a virtual drive with the contents of a directory. I have emscripten generate chaos.js, and using --preload-file sfx/ for the sfx directory creates a chaos.data file with all the generated OGG files encrusted in it. From there, using the bog standard SDL mixer API just works. Incredible.

Saving and loading was a little bit trickier. I wanted the game to save and load its options and game state using native JavaScript calls to DOM Storage. The emscripten wiki shows a simple example of how to call a pointless my_js function from C code. This example doesn't accept arguments or return values, but it was a start.

I wanted functions in C that had the following prototypes:

void js_save(const char *key, const char *data);
char *js_load(const char *key);

And in JavaScript would use the localStorate API in the following way:

js_save = function(key, data) { window.localStorage.setItem(key, data); }
js_load = function(key) { return window.localStorage.getItem(key); }

Simply declaring those C prototypes meant I could call out to JavaScript from C. I still had to declare the JS code somewhere. The pieces to do that are "emscripten libraries" and the --js-library compiler switch. After digging into the test suite, I came up with this first go:

mergeInto(LibraryManager.library, {
    js_save: function(key, data) {
        window.localStorage.setItem(key, data);
    }
    js_load: function(key) {
        return window.localStorage.getItem(key);
    }
});

I placed that in a file library.js and added it to the emcc line to create the final JavaScript: emcc -o chaos.js --js-library library.js.

Unfortunately - and I probably should have expected this - the char *key and char *data arguments that arrive at those JavaScript functions from the C-side are not JavaScript-strings. They are JavaScript numbers, indices (or "pointers") into the array of data that emscripten uses for memory declared in the land of C. To get a JavaScript string from the pointer, I used the aptly-named emscripten function Pointer_stringify. Similarly, to return a JavaScript string back into a C function you need to convert it into a pointer. The way to do this seems to be using allocate together with intArrayFromString. After reading emscripten's built-in SDL library wrapper, I came up with this final save/load code:

mergeInto(LibraryManager.library, {
    js_save: function(key_, data_) {
        var key = Pointer_stringify(key_);
        var data = Pointer_stringify(data_);
        window.localStorage.setItem(key, data);
    },
    js_load: function(key_) {
        var key = Pointer_stringify(key_);
        var result_ = window.localStorage.getItem(key);
        var result = allocate(intArrayFromString(result_), 'i8', ALLOC_NORMAL);
        return result;
    },
});

During the porting, one of the issues I had was fading-out the screen. Fading out to black is a classic effect that a lot of old 16-bit games used. While the screen is in its faded out state you can set up the layout without having half-drawn graphics show up. On the GBA, there are hardware registers to fade between layers and this is fast and efficient. With the SDL version I did a brute-force palette change that required updating all the pixels on the screen for each level of fading. While it worked OK in the native build, it turned out to be annoyingly slow when compiled to JavaScript. The fade effect would take around 5 seconds to complete, instead of less than a quarter of a second. I changed to use SDL_SetAlpha to alpha-blend a black rectangle over the current screen. This worked well in the native SDL build, but did not do anything in the JavaScript SDL canvas.

After a bit of searching and grepping, I figured out how to add this feature in, since the SDL library in emscripten almost had it right. With that SDL_SetAlpha worked and didn't slow the fading transition down to a crawl. The maintainers have since merged this change into the stable version of emscripten too. Karma++.

So here it is: Chaos in your browser :-)

The same code compiles and runs more-or-less identically on the GBA, Nintendo DS, Android, SDL, and now (thanks to emscripten) in the browser.

I've tested this in Firefox 24+ and Chromium ~32 on Ubuntu and Debian. It also runs on Firefox and Chrome for Android, though Chrome does not play the sound effects for some reason. It surprised me to see that the game seems to run slightly smoother on Chrome compared to Firefox, despite the advantages of asm.js. I think that this must be due to the HTML5 canvas methods performing better on Chrome/ium, as there's not a lot of CPU intensive stuff going on here.

New features in this release compared to the last are a Spanish translation (a family effort with my son helping out), a better random spell selection by using the more balanced "shuffle bag" approach, and a cleverer AI that can go around obstacles. The last 2 ideas were inspired by a comment on the Play store. It was very annoying to get 3 Magic Swords in one game, and to see creatures fail to traverse a wall or span of gooey blob. A shuffle bag means that spells are not as totally random - each has a weighting of how often it will appear now so there is more balance, and certain spells cannot appear more than once. The AI now uses that old standby A*. Despite play testing this for a while now, I expect a flurry of bug reports and another release next week ;-)