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 ;-)

Sunday, December 15, 2013

The Lords of Midnight: 8 bit remake returns

I have some good news regarding my old remake of The Lords of Midnight on Android.

First a reminder of the context. You may recall that Chris Wild and Mike Singleton worked together on an update of the Midnight saga with a planned release on iPhone and iPad. That was before we all learned the sad news that Mike had passed away last year.

After that, Chris finished off the game - albeit at an understandably reduced scope - and he released it on iOS and then later on other platforms.

This new game is available at http://thelordsofmidnight.com, and is a much more ambitious update than my 8-bit-style nostalgic remake. You really ought to check it out :-)

Before this all happened, I had created an unofficial remake of LOM on the Game Boy Advance and then later ported it to Android. It was pretty naïve of me, and Mike asked me nicely to remove these as they were using his copyrighted stuff, and would cause confusion for the upcoming official versions. This I did, and these ports have remained unavailable since.

Then a couple of weeks ago Chris got in touch with me. In a rather generous move, Mike's sons have given me permission to re-release the Android port. They feel it is important for as many people as possible to play the games their dad made. Because of this, "The Lords of Midnight: 8 bit" - as it is now known - is available now on the Google Play store!

If you had installed the previous incarnation you may have noticed an update. Apart from the usual Android build system updates and associated yak-shaving, the name has been changed to reflect this new deal. I also fixed some graphical hiccups that were more obvious on my 7" tablet test device, as well as adding the obligatory higher resolution icons. The other noticeable change is that there is now an extra splash screen that says that this port is released under licence (from the Singleton family) with the address of the official website at www.thelordsofmidnight.com.

I ought to state that this does not indicate a free for all on Mike Singleton's games. The copyright and trademarks are still the property of the Singleton estate. While I have been granted permission for the release of this one port, it is under licence with the understanding that the game remains free and that I "do no evil", so to speak.

What a nice and unexpected early Christmas present, eh folks?


Saturday, December 07, 2013

Blogger Themes That Break With NoScript

Blogger Themes That Break With NoScript TL;DR: here's a Blogger Feed bookmarklet to fix some blogger blogs that fail to load if you're using the Firefox add-on NoScript. Read on for the usual waffle.

I use NoScript with Firefox, and occasionally I'll find a link to a blog that just shows the NoScript icon and a handful of broken links. For example, a recent post on hacker news linked to a security blog post describing a technique to avoid using dangerous C functions with GCC. With NoScript, all I saw was the following:



This is because a new-ish Blogger theme is a big JavaScript application monstrosity that loads the text of the article via an asyncronous call, but does not gracefully degrade for those of us without scripts enabled. The owner of this particular blog has since switched from Blogger to Wordpress, so it's moot in this case.

A poster on HN wrote a bash shell script that downloads the blog, gets the corresponding feed and spits it out in HTML. This is a good idea. However I think that copying the blog link over to a terminal, running the script and then opening the resulting HTML page in the browser is a bit of a pain. Even for me.

Enter some 90s technology - the bookmarklet!

Simply drag the Blogger Feed bookmarklet onto your bookmark toolbar, or right click it and save as a bookmark. Next time you are faced with a NoBlog you just click the button or bookmark and it'll take you straight to the blog's JavaScript-free RSS feed version of the post. I imagine that this will work until Google shuts down Blogger and tries to force us all onto Google+.

In addition, if you want to have an icon for the bookmarklet, here's a tip cribbed from this superuser post:
  1. Find a regular link (without JavaScript) for the website with the favicon you want.
  2. Add that link to your bookmarks toolbar as a regular bookmark.
  3. Finally, change the properties of the bookmark you just added and change the location to be the actual JavaScript bookmarklet you want (you want the location from the bookmarklet that doesn't have the favicon).
These steps turn the bookmark from step 2 into a bookmarklet with the desired favicon and JavaScript. Here's a capture of the bookmarklet with the Blogger icon that I use:




Sadly, if the Blogger blog uses a Feedburner RSS redirect, then this trick doesn't work. However if that's the case then you're probably better off not reading their particular brand of propaganda anyway.

Sunday, September 29, 2013

Unlocking an HTC Magic: 2009 called, they want their unlocking guide updated

The HTC Magic running Android 2.2 has a locked bootloader. This means that you can't install any other operating system, only the official one.

Last year HTC had a change of heart about locking the bootloader and provide a way on their website to unlock your phone. Unfortunately, the HTC Magic ships with software that is too old to recognise the unlock command the website uses. You need to first update this software (the "HBOOT") to a version that is unlockable by HTC.

Go to HTC Dev and create an account. Select HTC Magic and click the unlock button.
HTC Dev

As shown on that screenshot, you are warned that the HBOOT will need to be updated.

This takes you to the section to download the software, called RUU, that updates the phone's HBOOT. RUU probably stands for ROM Unlocking Updater, who knows. Select the RUU corresponding to your model of Magic. I used the one marked Vodafone (AU/FR/DE/IT/NL/NZ/ES/UK/ RO/PTG/CH-GER/Mobilkom).

This RUU software is a Microsoft Windows executable file. In theory you have to use Windows to proceed. However, I don't have a Windows machine available. I got creative. You could probably use this technique on Windows if you have problems, since it sounds like the RUU requires HTC Sync, drivers and other gubbins. If you can run the RUU on Windows, run that and it should update the HBOOT. Follow the HTC Dev instructions, you're almost done. If not, here is what you could do...

According to this xda-developers post the executable unpacks a zip file as part of the process. I figured that if I ran the executable with wine it might extract the file too. The EXE didn't run to the first step though, but did show a progress bar before crashing out.

RUU under Wine on Debian "wheezy"
I paused wine just before the program crashed by hitting ctrl-z, ran find ~/.wine -name rom.zip and bingo! There was the rom.zip I neeed.

Copy this rom.zip file to an SD card. The file must be named exactly SAPPIMG.zip. The file name is case sensitive.

You have to format the SD card as fat32. Fat16 will not work. I should know, as originally I had the card as fat16. I used gparted to format a 1Gb card to fat32.

Start the phone in "HBOOT mode" - which you do by holding down the power and volume down buttons when switching it on. HBOOT mode boots very quickly. All being well, after approximately 5 seconds the blue light will go off and the screen will show some green text (checking SAPPIMG.zip, more or less).

It will ask if you want to continue, hit action (the trackball) to confirm, and then the phone reboots.
Now use the fastboot executable from the htcdev website to extract a token unique to your phone. In Debian I had to use root to do this or it just hung waiting for find devices, so that's sudo ./fastboot oem get_identifier_token

This spat out the following:
/tmp$ sudo ./fastboot oem get_identifier_token
... INFO
INFO< Please cut following message >
INFO<<<< Identifier Token Start >>>>
INFO41BF2ABF132C78CC414238FC47D43442
INFO898C7C87E0CEB4D1C5D55FCDC17647E2
...
INFOBCF34E9487BE0F794BCAEA48646A3870
INFO2946D797752D6167278226973D86BE33
INFO<<<<< Identifier Token End >>>>>
OKAY

Copy this chunk:
<<<< Identifier Token Start >>>>
41BF2ABF132C78CC414238FC47D43442
898C7C87E0CEB4D1C5D55FCDC17647E2
...
BCF34E9487BE0F794BCAEA48646A3870
2946D797752D6167278226973D86BE33
<<<<< Identifier Token End >>>>>

Be careful not to include INFO or have trailing newlines. Paste it into the form on the page on the HTC website. I have no idea of the security implications, so I've not included all of the token here - you get the idea hopefully. You need all the random numbers and letters and the << >>> lines.


HTC will email you a binary file, which you flash to the phone:

sudo ./fastboot flash unlocktoken Unlock_code.bin

The following image shows the unlock screen. It's taken with a Nintendo 3DS in low light, hence the terrible quality.



Press Volume UP to take the red pill, er, I mean unlock the bootloader... then press the power button. The phone will wipe all of your data. Oh no.

That is all. You have unlocked the phone. If you boot into HBOOT again (power, volume down) it should now display UNLOCKED against a fetching fuchsia background.