2015-09-07

HankyAlien - A New DS Game

HankyAlien Title HankyAlien Game

Here’s a new homebrew game for the Nintendo DS. You should be able to tell exactly what the game is from the screenshots. Download it here:

Diary of a Game

It occurred to me that I’d never written a large project exclusively in C. I’ve written little utilities and libraries in C, and used it occasionally in C++ and Objective-C programs, but a whole project that’s just C? Nope. I’d promised myself I was done with remakes and DS programming, so why not try writing a new remake for the DS in C?

The first thing I needed to do was write my own core libraries from scratch, because that’s always the interesting part. Abstract away some of the C nastiness. First of all, I wanted to use reference counting everywhere. The model used in Woopsi, in which the framework tries to own everything, is efficient for the CPU but eventually results in some really nasty problems for the programmer. I still have no idea who owns a Woopsi font object.

SZLib

Reference counting is very easy to implement (it is the way I implemented it, anyway). Start off with a basic object that looks something like this:

typedef struct __SZObject {
    unsigned int refCount;
} SZObject;

Next, add a few functions to create/retain/release them:

SZObject *SZObjectCreate() {
    SZObject *ref = malloc(sizeof(SZObject));
    ref->refCount = 1;

    return ref;
}

void SZObjectRetain(void *ref) {
    SZObject *object = (SZObject *)ref;
    ++object->refCount;
}

void SZObjectRelease(void *ref) {
    SZObject *object = (SZObject *)ref;
    assert(object->refCount > 0);

    --object->refCount;

    if (object->refCount == 0) {
        free(object);
    }
}

It’s easy to embed reference counts into any object by taking advantage of a feature of C’s layout of structs in memory:

typedef struct __SZThing {
    SZObject object;
    char *data;
} SZThing;

I can cast a variable of type SZThing* to an SZObject* and treat it as though the former is an instance of the latter. The SZThing struct has all of the properties of the SZObject since the first field in the struct is an SZObject. Neat.

There’s a little more to it than this, of course. If the constructor function for the SZThing object mallocs its data property, then the release function needs to free that memory. This is all done with a callback struct that looks something like this:

typedef struct __SZObjectCallbacks {
    int (*equals)(const void *, const void *);
    int (*compare)(const void *, const void *);
    unsigned long (*hash)(const void *);
    void *(*copy)(const void*);
    void (*dealloc)(void *);
} SZObjectCallbacks;

Whenever an object includes an SZObject in its struct it is expected to create and populate one of these structs. The function pointers are called at the appropriate times if they are not NULL (dealloc is called by the SZObjectRelease() function, for example) and this sets us up for a bunch of exciting functionality: copying, comparisons, and hashing, in addition to worry-free memory management (not thought-free; there’s still a requirement to retain and release, but there’s no agonising over whether a given piece of code should free a block of memory or not).

With reference counting in place, the next thing to do is write a bunch of collection classes that take advantage of this functionality. I call them “classes”, even though C doesn’t support classes, because the idea is similar: a group of associated data that can only be accessed via a well-defined set of functions. Achieving this requires “opaque types”, which are basically structs with hidden definitions. An opaque type is created by adding a typedef to a header file and a struct definition to a .c file. Here’s a snippet of the header file:

typedef struct __SZHashMap *SZHashMapRef;

int SZHashMapCount(SZHashMapRef hashmap);

Here’s part of the .c file:

typedef struct __SZHashMap {
   SZObject object;
   void **data;
   int size;
   int reservedSize;
 SZHashMap;

int SZHashMapCount(SZHashMapRef hashmap) {
    return hashmap->size;
}

It seems to me to be extremely counter-intuitive that the compiler doesn’t go nuts when it encounters a typedef for something that doesn’t exist yet, but it works. The code to create and use one of these hashmaps looks like this:

SZHashMapRef hashmap = SZHashMapCreate();
printf("%d", SZHashMapCount(hashmap));
SZObjectRelease(hashmap);

Outside of the hashmap’s .c file there’s no way to create a plain SZHashMap struct or poke at its internals (short of looking through the raw bytes in RAM).

Other than a hashmap (which I didn’t need to use) the base library includes a bunch of other things I didn’t really need or use: a set (which is currently backed by a binary tree that can quickly become unbalanced, so it needs to be replaced with a self-balancing tree structure), a linked list, an autorelease pool, a number wrapper (like a boxed int/float/double in Java), a value wrapper (slightly more versatile than a number) and a data wrapper (wraps a byte array; essentially just a very versatile value). Things I wrote and then did use were a string (ASCII only), a range (a struct containing a start and a length) and an array.

SZGeometry

Once the core library was done I could move onto slightly more interesting things: a geometry library. This is mostly based on WoopsiGfx, and includes code for managing points, sizes, rects, lines and circles.

The most interesting features are the circle and line point enumerator functions. In modern languages with new-fangled features like closures it would be possible to do something like this:

SZRect rect = SZRectMake(0, 0, 10, 10);
[SZCircle enumeratePointsInRect:rect block:^(SZPoint point) {
    // Do stuff with point here
}];

In C that’s not possible, so we’re forced to use function pointers and a context object to simulate closures instead:

void enumerate() {}
    SZRect rect = SZRectMake(0, 0, 10, 10);
    SZCircleEnumeratePoints(rect, NULL, __callback);
}

void __callback(const void *context, SZPoint point) {
    // Do stuff with point here
}

It achieves the same thing, but it’s less elegant. Closures are probably the feature I’ve missed most when coding C. In either case, we’ve split up enumerating the points of a circle from rendering the circle (in WoopsiGfx they were part of the same operation), so we can do more interesting things with the circle’s description now.

SZGraphics

With the geometry library in place, we can add a graphics library. Again, this is all back-ported from the C++ WoopsiGfx library (with the occasional bugfix). It includes a few different types of bitmap, a font class, and a graphics class for drawing to those bitmaps.

Achieving different types of bitmap without inheritance was tricky. The library uses a kind of base class that all of the other bitmaps include as the first field in their structs:

typedef struct __SZBitmap {
    SZObject object;
    SZSize size;
    SZBitmapCallbacks callbacks;
} SZBitmap;

typedef struct __SZMutableBitmapWithInternalBuffer {
    SZBitmap object;
    SZColor *bitmap __attribute__ ((aligned (4)));
} SZMutableBitmapWithInternalBuffer;

We’re starting to nest structs: the mutable bitmap contains a bitmap, and the bitmap contains an SZObject. I can therefore treat a mutable bitmap as a bitmap and as an SZObject and get all of the functionality of the combined set of 3 objects.

A very truncated version of the SZBitmapCallbacks struct looks like this:

typedef struct __SZBitmapCallbacks {
    SZColor (*pixelAtCoordinates)(SZBitmapRef, SZPoint);
} SZBitmapCallbacks;

Meanwhile, SZBitmap offers a function that does this:

SZColor SZBitmapPixelAtCoordinates(SZBitmapRef bitmap, SZPoint point) {
    return bitmap->callbacks.pixelAtCoordinates(bitmap, point);
}

Therefore, all a “subclass” of SZBitmap has to do is fill out its SZBitmap’s callback struct and, even if it has some wildly crazy internal representation of a bitmap, it can be treated like any other SZBitmap. All of the standard functions will work.

Making this subclassing scheme possible means working around the opaque types idea, unfortuntely, since each subclass needs to include an SZBitmap (the struct, not a pointer to a struct) in its own struct. I got around this by moving the struct definition to a “private” header file (you can tell it’s supposed to be private; its filename is suffixed with “_private”).

Fonts are based on Jeff Laing’s monochrome packed fonts from Woopsi, with one significant change. Rather than the SZFont being responsible for rendering itself to a bitmap, the font has a function for testing if the point at a given set of co-ordinates within a character glyph is set (1) or unset (0). The graphics class uses that information to render to a bitmap. This way all of the rendering logic is in one place and there’s no coupling between SZFont and SZBitmap. I haven’t bothered with multiple types of font or unicode because they’re two more things I won’t use.

The final piece of the graphics library is the class that does all of the drawing work. It includes the usual set of drawing functions: lines, text, rectangles, circles, flood fill, etc. The API is a vast improvement over WoopsiGfx because it takes advantage of all of the available primitives created in the lower-level libraries like rects and points, greatly reducing the number of arguments passed to each function. All of the functions accept a graphics context struct that includes a bitmap to draw to and a clipping rect, meaning all of the drawing functions are clipped. The clipping code is much saner in the new library.

SZHAL

The last library is a hardware abstraction library. It includes a framebuffer class, a couple of functions for doing DMA-boosted memset() and memfill(), and code for interacting with the stylus, buttons, vblanks, and hardware setup and teardown. The library uses #ifdefs to switch between DS and SDL implementations where necessary. I started abstracting out the DS’ sprite system but quickly abandoned it when I realized how awkward it would be to get the graphics working in SDL.

The Game

The downside to completely ignoring the capabilities of the DS hardware and doing all of the graphics work with just the CPU and a framebuffer is that it is insanely expensive. Early on it looked like HankyAlien wouldn’t work because drawing all of the aliens at 60fps wasn’t possible. Then I realised that the original game moved one alien at a time, so I’d only ever need to draw one alien at once.

Although the game’s background is black, in theory it would be trivial to drop a background image in with no meaningful drop in performance. Every time a sprite is drawn to the screen the game pushes a rect that describes the sprite onto a dirty rects array. Each time the game iterates it erases all of the dirty rects and flushes out the array. To get a background working, we’d just need to perform a bitmap copy for that rect from the background image to the framebuffer instead of drawing a black rect.

The code was starting to get a little unwieldy and I found myself wishing that I could somehow implement the delegate pattern to tidy it up. After some thought, I figured out that delegates are very easy to implement in C. First of all we have to define a delegate struct:

typedef struct __SZGameSpriteDelegate {
    void *delegate;
    void (*spriteDidFinishExploding)(void *, SZGameSpriteRef);
} SZGameSpriteDelegate;

We can create one of these structs like so:

SZGameSpriteDelegate delegate;
delegate.delegate = game;
delegate.spriteDidFinishExploding = __SZGameSpriteDidFinishExploding;

In this snippet, __SZGameSpriteDidFinishExploding is a static function within the SZGame class that we want to call when the sprite explosion animation ends. The game variable is a pointer to the SZGame instance that wants to receive the callback. We call it like this:

void SZGameSpriteFinishExploding(SZGameSpriteRef sprite) {
    if (sprite->delegate.delegate && sprite->delegate.spriteDidFinishExploding) {
        sprite->delegate.spriteDidFinishExploding(sprite->delegate.delegate, sprite);
    }
}

The function in SZGame looks like this:

static void __SZGameSpriteDidFinishExploding(void *game, SZGameSpriteRef sprite) {
    SZGameRef gameRef = (SZGameRef)game;

    // Do stuff with gameRef
}

Therefore, the SZGameSpriteDelegate struct holds two pieces of information: the object that wants to respond to callbacks, which we pass as the first argument to the callback functions, and the set of optional functions that the delegate can respond to.

The shields are only drawn once per game. The game maintains a bitmap representation of each shield and does two-stage collision detection with other sprites: do the sprites intersect, and if so, do any pixels overlap? If there’s a collision it erases the other sprite’s rect from the shield bitmap. We erase the other sprite from the screen and the two representations are therefore kept in sync.

2014-12-18

Super Foul Egg iOS Retires

Good news, everyone! Super Foul Egg for iOS is now unavailable. I’ve been considering pulling it down for a while, mainly because I have no time to maintain it or fix any of the bugs in the game. They are only minor - the app icons are wrong and one of the menu screen bitmaps is the wrong size on retina iPads - but they irk me every time I pick up my iPad. That this is only my eighth post this year should be a good indicator of how much free time I have. In the 18 months that the iOS version was available, at the wallet-busting price of “free”, it managed to attract a grand total of 370 punters. Clearly very few people will be inconvenienced by the game’s retirement.

What finally prompted me to retire the game was a very friendly email from the original game’s author asking me to pull my version from the store to make way for an upcoming release of his own. This is fantastic, partly because I no longer have to feel guilty for not releasing updates, but mostly because I am terribly excited to play an official remake. I’ll post a link up here as soon as it appears in the app store.

The 370 folks who enjoyed Super Foul Egg can still find the OSX version at superfoulegg.com, and the source code for the OSX and iOS versions is hosted on GitHub:

2014-10-23

Generating a Meandering Line Between Two Points

I had an interesting problem to solve recently for a project I’m trying to revive. Given two points, create a meandering line between them that such that the y co-ordinate of each intermediate point is no more than 1 pixel higher or lower than its neighbouring pixels.

Here’s an example. We’re trying to draw a line from point A to point B:

+-+-+-+-+-+-+-+
| | | | | | |B|
+-+-+-+-+-+-+-+
| | | | | | | |
+-+-+-+-+-+-+-+
|A| | | | | | |
+-+-+-+-+-+-+-+
| | | | | | | |
+-+-+-+-+-+-+-+

This is a valid line:

+-+-+-+-+-+-+-+
| | | | | |x|B|
+-+-+-+-+-+-+-+
| |x| | |x| | |
+-+-+-+-+-+-+-+
|A| |x|x| | | |
+-+-+-+-+-+-+-+
| | | | | | | |
+-+-+-+-+-+-+-+

This is an invalid line:

+-+-+-+-+-+-+-+
| |x| | | | |B|
+-+-+-+-+-+-+-+
| | |x|x| |x| |
+-+-+-+-+-+-+-+
|A| | | | | | |
+-+-+-+-+-+-+-+
| | | | |x| | |
+-+-+-+-+-+-+-+

The problem becomes obvious if you start at point A and start generating arbitrary y values that adhere to the rules. Starting out is easy, but how do you ensure that you can meet up with point B?

Here’s the recursive, divide-and-conquer algorithm I came up with:

  • Find the x co-ordinate of the point exactly in the middle of the start and end points.
  • Find the maximum possible y co-ordinate for the mid point:
    • Assume that y increases by 1 point each time x increases.
    • Find the x distance from the start point to the mid point.
    • Add that to the starting point’s y co-ordinate.
    • Do the same for the end point, but work backwards towards the mid point.
    • Find the smaller of the two values.
  • Find the minimum possible y co-ordinate for the mid point:
    • Assume that y decreases by 1 point each time x increases.
    • Find the x distance from the start point to the mid point.
    • Subtract that from the starting point’s y co-ordinate.
    • Do the same for the end point, but work backwards towards the mid point.
    • Find the larger of the two values.
  • Assign the midpoint a random y value that lies between the calculated maximum and minimum y co-ordinates.
  • Use the start and mid points as the new start and end points and recurse.
  • Use the mid and end points as the new start and end points and recurse.

2014-09-08

Super Foul Egg Moved

Super Foul Egg will soon disappear from the Mac App Store as I’m not renewing my developer subscription. It is now available from this new and hastily created website:

superfoulegg.com

The latest version is 1.4, which matches the build in the App Store.

2014-05-10

Gobble Developments

I’ve just pushed some new changes to the master branch of the Gobble git repository. Mostly I’ve been refactoring the code to be tidier and take advantage of features of the Go language, but I’ve also made some more interesting changes.

As a result of experimenting with closures, Gobble’s list of static files is now user-definable. Previously, only two files could be served from the root of a Gobble blog: robots.txt and favicon.ico. It seems that a single favicon is no longer sufficient, so the config file can now include a dictionary of static file definitions.

For example, this blog includes the following in its config file:

"staticFiles": {
    "/favicon.ico": "favicon.ico",
    "/robots.txt": "robots.txt"
}

The key is the URL of the file relative to the root URL of the blog; the value is its path on the local filesystem, relative to a new staticFilePath setting.

Gobble has a new syntax highlighting library: Rainbow is out and highlight.js is in. The new library features automatic language detection, which makes marking up code easier. Now it’s possible to just use Markdown-style indenting to indicate a code block instead of including pre and code tags with a data-language attribute.

The correct “Leave a comment” text is shown for all situations: singular, plural, no comments, and comments disabled. Until now Gobble only handled the “no comments” and “plural comments” situation. I couldn’t figure out why I hadn’t fixed that problem before now - other than the awful, awful template docs and the useless errors that the templates spit out if there’s a bug, that is - until I installed the changes on this server and took the whole blog down. It seems the fix relies on features on Go 1.2, so I had to use godeb to get the latest version of the language installed.

Posts and comments are now stored in RAM in both HTML and plain text formats. The plain text versions are searched instead of the HTML versions.

2014-04-05

Dropbox Synced Blog

Updating a Gobble blog is now much faster due to the addition of the fsnotify library. The library watches a blog’s “posts” directory and, when anything changes, causes Gobble to refresh its post and comment cache. New posts, edits and deletions now occur instantly. The old 10 minute wait for the timer to expire has gone.

In related news, the content of Simian Zombie now gets synced to the server by Dropbox. The old workflow looked like this:

  • Write a post;
  • Commit to Git;
  • Push to BitBucket;
  • Connect to server;
  • Pull from BitBucket;
  • Restart Gobble to force a refresh.

The new workflow looks like this, thanks to fsnotify and Dropbox:

  • Write a post.

Much nicer. I can even edit posts on my phone without having to use SSH and Vim.

I had a few false starts. The initial idea was to use BitTorrent Sync, not Dropbox, as I thought it would be easier to set up. Unfortunately, the documentation for CLI-only installs is half-baked and, after an hour or so of tinkering, I switched to Dropbox instead. Dropbox had its own share of issues, the most annoying of which was a segfault at startup in the current version. Switching to the latest beta fixed that.

2014-01-26

Sparky 1.0 - A New DS Game

A new Nintendo DS game!

Sparky

This is a little version of the hacking subgame from the original Bioshock game. I started it waaay back in 2010 but got sick of trying to imitate the pipe filling graphics using nothing but Woopsi’s drawing primitives. The completed version uses a spark that travels along a line instead. Much easier to code.

I’d intended to improve on the original by only producing levels that were possible to complete. However, the recursive algorithm I wrote didn’t like the DS (probably a stack overflow issue) so that feature didn’t make the cut.

2014-01-07

Woopsi Tabs

Tabs are done. They work in more or less the same way as radio button groups: create the group, then use its built-in newTab() method to add new tabs. The tab group will automatically resize all added tabs so that they fill up the available space.

Woopsi Tabs

2014-01-03

Relocation and SDL2

Things have been a little quiet here recently. I am pushing ever westward; this time I moved from sunny Littleton, Colorado, to the equally-sunny Mountain View, California. I’m close enough to Google’s headquarters to be able to see their city-wide free wifi on my laptop, but far enough away that I can’t use it.

Relocation is something of a theme. The little coding time I’ve had has mainly been spent moving repositories from Mercurial/BitBucket to Git/GitHub so that I can hang out with the cool kids. Actually, I’ve been using Git exclusively for about five months and find that, when I do need to use Mercurial, I can’t remember how it works. Within the repositories, I’ve done some relocating too: consolidating DS and SDL code.

SDL2 was released not too long ago and I thought I’d have a play and see if it offered anything new. It seems the most important change for my SDL projects was the inclusion of automatic texture format conversion within the library itself, meaning it has built-in support for converting and displaying bitmaps in ARGB1555 format. This means that all of my DS projects no longer need to keep track of two bitmaps - one in ARGB8888 and one in ARGB1555 format - when in SDL mode.

Upgrading to SDL2 has allowed me to merge the SDL and DS codebases together, meaning I now have a single repository that will build for the DS and OSX out of the box. Getting them to build in Windows and Linux should be trivial. Additionally, the makefiles for the DS versions all work with the latest devkitARM. Something must have changed in the build system as all of the makefiles were broken.

In other news, I’ve been tinkering with Woopsi again. The complex, C#-inspired EventArgs system is out and I replaced it with the set of arguments that are relevant to each event. Gadgets no longer support multiple event handlers; each can now have just a single handler. Much tidier.