2016-12-29

Transparency in SZLib

One of the neat features in early Woopsi was screen dimming. The class responsible read each overlapped pixel from the framebuffer, adjusted its brightness, and wrote it back. I eventually had to kill the feature when I changed how the rendering system worked and broke any support for transparency.

Woopsi’s drawing algorithm (essentially a reversed painter’s algorithm) looks like this:

  • Pass in a rect that describes the area to be redrawn;
  • For each layer in the layer hierarchy, from the topmost down:
    • Draw the parts of the layer that intersect with the rect;
    • Subtract the drawn parts from the rect.

Each layer is expected to own all pixels within its rectangular region. To support transparency, there would need to be a way for layers to opt out of subtracting themselves from the redraw rect so that lower layers could draw into the same area. Even if there were a way to achieve that, we’re traversing the hierarchy the wrong way. Transparent views need to render over the top of existing framebuffer data. We need to draw from the bottom up.

The CanvasLayers JavaScript library has a workaround but it’s really inefficient. When setting the library up, it includes the option to support transparency. With that enabled, this is the algorithhm:

  • Pass in a rect that describes the area to be redrawn;
  • For each layer in the layer hierarchy, from the bottommost up:
    • Draw the parts of the layer that intersect the rect.

It’s just the painter’s algorithm. Its awfulness is slightly mitigated by all of the dirty rectangle work that the library does, but we’re still pointlessly drawing a bunch of stuff below opaque layers. We’re also forced to maintain two algorithms to do the same work.

SZLib needed to support transparency in order for overlapping objects in Hanky Alien and Chuckie Egg to work, so I put some thought into the problem and arrived at the obvious (with hindsight) solution: a two-pass algorithm. In pass 1, we iterate over the layers from top-down to figure out which layer will be responsible for drawing what. In pass 2, we iterate over pass 1’s results from bottom-up and perform the drawing.

Pass 1 looks like this:

  • Pass in a rect that describes the area to be redrawn;
  • Create an array of layer/rect tuples;
  • For each layer in the layer hierarchy, from the topmost down:
    • Find the intersection of the layer with the rect;
    • Create a tuple containing the intersection and the layer;
    • If the layer is opaque, remove the intersection from the rect.

Note that we don’t consider an intersection to be “used” if the layer is transparent, which allows lower layers to create their own tuple in subsequent iterations.

In pass 2, we iterate backwards over the tuple array and redraw each tuple. Pass 1 gave us an array ordered by z-index from high to low; by iterating backwards we therefore redraw from the bottom up. Lower opaque layers are drawn before higher transparent layers.

This new algorithm supports transparency with the minimum amount of redundant drawing.

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.

2012-11-06

Yet Another iOS JSON Date Parser

Here’s yet another fix for my JSON date parser for Objective-C. This version includes support for dates with a timezone offset, which Jeff requested a while ago and which I’ve finally run into (Grumpydev updated Nancy to produce this date format back in April).

#import <Foundation/Foundation.h>

@interface SZJSONDate : NSObject

+ (NSObject *)dateToJson:(NSDate *)date;
+ (NSDate *)jsonStringToNSDate:(NSString *)string;

@end


#import "SZJSONDate.h"

@implementation SZJSONDate

+ (NSObject *)dateToJson:(NSDate *)date {
    if (date == nil) return [NSNull null];

    NSString *value = [NSNumberFormatter localizedStringFromNumber:[NSNumber numberWithDouble:date.    timeIntervalSince1970 * 1000] numberStyle:NSNumberFormatterNoStyle];

    return [NSString stringWithFormat:@"/Date(%@)/", value];
}

+ (NSDate *)jsonStringToNSDate:(NSString *)string {

    if (string == nil) return nil;

    // Extract the numeric part of the date.  Dates should be in the format
    // "/Date(x)/", where x is a number.  This format is supplied automatically
    // by JSON serialisers in .NET.  Alternatively, dates can be supplied with
    // the time zone suffixed after x as a 5 character timezone offset,
    // consisting of a positive/negative indicator ('+' or '-'), two digit hour
    // offset, and two digit minute offset (ie. '-0700' for MST).
    NSRange range = NSMakeRange(6, [string length] - 8);
    NSString* substring = [string substringWithRange:range];

    NSTimeInterval seconds;

    NSNumberFormatter* formatter = [[NSNumberFormatter alloc] init];

    // We need to parse out the date portion and the timezone portion
    // separately.  It's possible that we won't have a timezone and the date is
    // negative, so we have to be more specific when searching for the 
    // separator.
    unichar timezoneSeparator = [substring characterAtIndex:substring.length - 5];

    NSString *date = nil;

    if (timezoneSeparator == '+' || timezoneSeparator == '-') {

        date = [substring substringToIndex:substring.length - 5];

        NSString *timeZone = [substring substringFromIndex:substring.length - 4];
        NSString *timeZoneHours = [timeZone substringToIndex:2];
        NSString *timeZoneMinutes = [timeZone substringFromIndex:2];

        NSNumber* milliseconds = [formatter numberFromString:date];

        int hours = [[formatter numberFromString:timeZoneHours] intValue];
        int minutes = [[formatter numberFromString:timeZoneMinutes] intValue];
        int offset = (minutes + (hours * 60)) * 60;

        // NSTimeInterval is specified in seconds, with milliseconds as
        // fractions.  The value we get back from the web service is specified
        // in milliseconds.  Both values are since 1st Jan 1970 (epoch).
        seconds = [milliseconds longLongValue] / 1000.0;

        if (timezoneSeparator == '+') {
            seconds += offset;
        } else {
            seconds -= offset;
        }
    } else {

        date = substring;

        NSNumber* milliseconds = [formatter numberFromString:date];
        seconds = [milliseconds longLongValue] / 1000.0;
    }

    [formatter release];

    // If we've encountered .NET's minimum date value we treat it as nil.
    if ([date isEqualToString:@"-59011459200000"]) return nil;

    return [NSDate dateWithTimeIntervalSince1970:seconds];
}

@end

2011-05-10

Earth Shaker DS Released

One of my favourite ZX Spectrum games from back in the mists of time was Earth Shaker. It’s a fantastic Boulderdash clone that featured, relatively speaking, great graphics and sound, and fast but puzzle-based action.

I recently decided to see if Woopsi would be fast enough to run a full-screen, bitmap-based game. Boulderdash seemed to be a pretty simple game to write, so I set about it. Not long into the process I realised that the game was looking more and more like Earth Shaker, so I set about turning it into a full-blown port of the original game.

A week or so into development it became obvious that Woopsi isn’t really up to the task of running a full-screen game at 60fps. It flickered just a little bit too much. 10 minutes later I had it ported to the much lighter-weight WoopsiGfx library instead, which has proven itself invaluable when knocking up little games like this in no time at all. The total development time so far has been a little over two weeks, which includes the time it took to grab all of the graphics from the original game and figure out how its algorithms worked.

I’ve entered the port into the GBATemp Homebrew Bounty competition. It’s not quite finished yet - no sound and missing levels - but it is perfectly playable in its current silent, shortened form. Inicidentally, if anyone can help getting the makefile modified to support maxmod and convert a directory into a soundbank, please let me know.

The source is available from BitBucket under the MIT/X11 licence that I’ve come to favour lately. I’d initially intended to release it under the GPL v3, but got bored before I’d read the pages and pages of text that comprise the latest version. The copyright for the game’s assets - graphics and level designs - is held by the original author. He has kindly given me permission to use them in this port, but anyone else who wants to use this code will either need to negotiate with him for the right to redistribute his assets, or will need to make their own replacements.

Many thanks to Michael Batty, the original coder, for his approval!

You can download the game here:

The sourcecode is here:

EDIT: In the time it took me to write this blog post, the guys over at Nintendo Max managed to get a YouTube video up. Fast work, guys! Watching this reminded me - press the L and R shoulder buttons simultaneously to commit suicide if you screw up the level and get stuck.

Here are a few screenshots:

2011-04-06

Woopsi 1.2 Released

Another version of Woopsi is out. Get it from the Woopsi website:

In my last Woopsi post I discussed the removal of the AmigaWindow and AmigaScreen-specific flags. I’ve decided to get rid of all gadget flags supplied as constructor arguments. This was the old way of creating draggable, borderless windows (ignore for a moment the impossibility of such a window):

AmigaWindow* window = new AmigaWindow(0, 0, 100, 100, "My Window", Gadget::GADGET_BORDERLESS | Gadget::GADGET_DRAGGABLE, true, true);

This is the new way:

AmigaWindow* window = new AmigaWindow(0, 0, 100, 100, "My Window", true, true);
window->setBorderless(true);

There were multiple problems with the gadget flags idea:

  • Most gadgets weren’t set up to receive the flags in their constructors;
  • Gadget::GADGET_TOO_MUCH_POINTLESS_TYPING;
  • Impossible for the compiler to check for any errors;
  • Discovering which options were available for a given gadget was very difficult;
  • Annoying to have to constantly set the same options every time a gadget was created (windows are more often draggable than not, for example).

Instead, I’ve chosen sensible defaults that are set automatically in gadget constructors. If these need to be changed, they can be via the usual getters and setters available in all gadgets. The change leads to:

  • Less code;
  • Easier to create gadgets;
  • Fewer bugs that the compiler can’t catch;
  • A more consistent API.

This is another breaking change.

Let’s see what other bugs are in this changelog… (Rummages around the hard disk.) As mentioned previously, the Woopsi gadget creates a couple of background screens at startup to ensure that the background is always grey. These are now passed the Woopsi gadget’s style object, so if the colours have been changed by a developer the background will change to match. The ProgressBar gadget also accepts a style object in its constructor.

Disabling or enabling the border around a Label gadget now repositions its text to match. Getting rid of the flags system let me spot this one. Related to that, the Gadget class’ setBorderless() method is now virtual so that subclasses can react to changes in their border state.

One of the improvements I hoped to get in after implementing the damaged rect redraw system was to reduce the amount of redrawing done by textboxes. This is now in place. It’s not as efficient as I’d hoped because I’d previously opted for a design that eliminated code repetition. Whenever the text in a textbox is changed, an “onTextChanged()” method is called. Unfortunately, the method doesn’t know what the text was before it was called, so it can’t make informed decisions about how much of the gadget to redraw. For example, if the width of the text has shrunk, it needs to redraw the region covered by the original text. If the text has grown wider, it needs to redraw the region covered by the new text. I considered the benefits of redesigning this to be more efficient against the downside of increasing the complexity of the class, and decided to just stick with the current design.

What I did do was change the redrawing system so that it just redraws the total area within the gadget that could conceivably be covered by any text for the current font, which should save exponentially larger amounts of redrawing as the size of a textbox increases relative to its font size. The same thing happens when the cursor moves.

The Gadget class included a lot of methods for working with subgadgets, such as “addGadget()”, “raiseGadgetToTop()” and “lowerGadgetToBottom()”. It also included other methods for working with subgadgets such as “closeChild()”, removeChild()” and “shelveChild()”. The obvious inconsistency in the naming convention is now fixed, and all methods that previously referred to “child” now refer to “gadget”.

Lastly, the Bitmap class has a couple of new features. It has a real copy constructor, so it is now possible to create a duplicate of any bitmap that inherits from BitmapBase with no effort. It also has a “setDimensions()” method that will resize the bitmap in the same way that PhotoShop resizes a canvas. It doesn’t feature any clever scaling algorithms; it just increases or decreases the space available to draw on. Any existing data is preserved unless the bitmap is reduced in size, in which case data on the right and at the bottom is cropped out.

Instead of hosting the downloadable files on this website, I’m storing them on BitBucket. This is mainly just so I can easily see how often Woopsi is downloaded (uncannily-accurate prediction: not many).

The Woopsi todo list is growing increasingly short. In fact, there are less than half a dozen items left:

  • Create a tree gadget;
  • Create tab/tab group gadgets
  • Add a “Parent” button to the FileRequester and get rid of the “..” entry;
  • Add a file type filter to the FileRequester;
  • Rethink the appearance of the GUI - can I come up with something that looks better than the current Amiga-inspired design?

This last item is tricky. The more complex the GUI design gets, the more visually interesting it becomes; it also becomes more demanding on the DS. Is it worth trying to make the appearance more modern if it potentially causes slower performance?

As for the other items in the list, the FileRequester changes are fairly trivial (especially as the WoopsiString is now set up to make the file filtering task easier), and I’m not in any hurry to get the tabs or tree gadgets written. Other than that, there are a few things that I won’t implement that I’ll have to describe in a future blog post.

2011-04-03

Bug Hunting and Refactoring

I’ve had some time to blast through some Woopsi coding over the last week, so there’s quite a bit to write up here. There’s a mix of new features, bugfixes, refactoring and breaking changes.

First up, attempting to flip a screen from one display to the other, or re-organise the depths of screens in the screen stack, is no longer allowed if there is only one screen in existence. Allowing this to occur was a bug introduced in v0.45 when I added a couple of background screens to the Woopsi gadget by default, to ensure the background was always grey and redrawn correctly.

The font class no longer includes a colour member, nor does it distinguish between full-colour and monochrome fonts. It makes no sense for a font to have a state. When trying to draw text, I want to draw text in colour X using font Y. I don’t want to get font Y, make it colour X, then draw with it. Implementing this has involved making changes throughout Woopsi. Text rendering commands now expect to be given a colour to render with. Related to this, the GadgetStyle class now includes a text colour property, whilst the Gadget class has new getTextColour() and setTextColour() methods.

In addition to removing the colour member from the FontBase class, I’ve removed all other members. The FontBase is now a legitimate, data-free interface. All members that are still required, such as height, have been moved into other classes. This will reduce the amount of redundant data inherited by subclasses, such as Lakedaemon’s libfreetype wrappers.

The font change was so successful that I replicated it with bitmaps. BitmapBase no longer includes any data either. Members have been moved into subclasses.

The overload of Gadget::checkCollision() that checks for collisions with other gadgets will not detect collisions with hidden gadgets. I’ve modified it so that it expects to be passed a const gadget pointer instead of a plain gadget pointer. I’ve also added a shortcircuit to the function so that it detects attempts to check for collisions between a gadget and itself and exits early.

I’ve rewritten the Gadget::swapDepth() method. This is used by screens and windows when their depth gadgets are clicked. If swapDepth() is called on a gadget that is not at the front of the subset of sibling gadgets that it collides with, the gadget will be moved to the front of that subset. If the gadget is at the front, it will be sent to the back of the subset.

Previously, the way the method worked was confusing. Most of the logic for the method was actually contained by the parent gadget in its swapGadgetDepth() method. The swapDepth() method just called the parent method to perform the swap. This had some downsides:

  • Children couldn’t determine how they would swap; it was decided by parents, so it was impossible for a new gadget subclass to swap in a different way to (for example) a window.
  • The Gadget, Screen and Woopsi classes all had their own implementations of the swapGadgetDepth() method that were subtly different but basically achieved the same effect.

I’ve renamed swapGadgetDepth() to changeGadgetDepth() and made it considerably more generic - it will now just move a gadget from one index in the child array to another, ensuring the gadget gets erased and redrawn correctly. The swapGadget() method in the child gadget determines which index the child will swap to, so each gadget can decide how it will depth swap. I’ve also added Gadget::getHighestCollidingGadgetIndex() and Gadget::getLowestCollidingGadgetIndex() to help determine these indices. The swapGadgetDepth() overrides in the Screen and Woopsi classes no longer exist.

Gadget::_decorationCount is an s32 instead of a u8. I don’t know why I’d got that set as a u8, especially when the getters/setters were working with s32s.

The RectCache::markRectDamaged() method had a nasty, obscure bug that could lead to the method getting into an infinite loop. It has a couple of nested loops and it seems I’d got the iterator variables confused at some point, and was using the variable from the first loop to index into the iterated-over array of the second loop. Ooops. Thanks to carpfish for spotting the crash and putting together a test so that I could track down the cause.

The todo list that I put together long before Woopsi v1.0 was released included a question: “Is there a bug in the floodfill?” I noticed that there seemed to be a couple of pixels that weren’t filled in the test I wrote for the WoopsiGfx library. Well, there was a bug in the floodfill - it wasn’t filling upwards correctly due to some utterly bizarre typos in the method. Don’t quite know what I thought I was doing when I wrote that function. It’s fixed now.

Related to the floodfill, the stack functions in the Graphics class that it relies on now expect to be passed a reference to a stack object to work with rather than a pointer.

For some reason, three members of the Woopsi class (the vertical blank count that stores the number of frames elapsed since the app started running, the deleted gadget list and another one that I can’t presently remember) were static. This made no sense, so they are no longer static.

I’ve tested empty ListBox gadgets for the first time and encountered a couple of problems. First of all, the scrollbar went crazy and suggested that there were hundreds of options to choose from; that’s fixed. Clicking the empty space within the ListBox caused it to try to locate a non-existent option in its option list and dereference a null pointer. That’s fixed too.

I’ve stripped out some redundant code. The GadgetFlags enum included a “GADGET_NO_RAISE_EVENTS” flag that wasn’t used anywhere; it’s now been removed. I’ve also removed the Woopsi::goModal() method that only existed because the Woopsi::handleClick() method was badly designed. Redesigning that let me get rid of the goModal() override.

Gadgets included a concept of “close type” which existed solely to allow the close gadgets on windows to close, hide or shelve the window as appropriate. It wasn’t useful in any other situation and wasn’t really useful for windows either, so it’s gone too.

Another pair of useless features were the AmigaScreenFlags and AmigaWindowFlags enums. They were used to send gadget-specific flags to the AmigaScreen and AmigaWindow constructors. However, as there were only two flags in each enum, and as typing the enum value names took longer than just passing true or false a couple of times, I’ve stripped them out and replaced them with booleans instead. This change will break user code, but fixing it just a matter of changing a couple of values when creating AmigaScreen and AmigaWindow objects.