Advanced programming tips, tricks and hacks for Mac development in C/Objective-C and Cocoa.

Using NSKeyedArchiver to archive a C linked-list

NSKeyedArchiver provides some support for archiving C primitive types but provides no support for pointers to C structs. I'll show you how you can archive a linked list of C structs, despite the lack of support in NSKeyedArchiver.

Standard C

Cocoa contains very little support for standard C data structures. The reason for this is pretty simple: introspection. An Objective-C object can report on what it is, its block size, its ivars and methods. Protocols can be implemented to provide further metadata about the object. With a pointer to an arbitrary block of standard C data, you have no information at all about the type and structure of the block.

While keeping all your data in Objective-C objects works well most of the time, sometimes you'll need to work with standard C data structures — for example when working with data produced by third party libraries.

To show how to use C data structures with libraries that expect Objective-C objects, I'll show you how to archive a linked-list of C structs using NSKeyedArchiver.

Metadata and wrappers

As I mentioned, the real problem with arbitrary C data is that it offers no introspection — we must be able to ask our data about its metadata. Specifically, we will need to know the size of the list node structs (we can copy the whole struct as a block of data) and the offsets within the struct of pointers to other list nodes.

In addition to metadata, we need a way to deal with pointers. NSKeyedArchiver provides no way to encode an arbitrary pointer.

To handle both these problems, the solution will use one Objective-C "wrapper" object to represent each struct, and one extra "context" object to encode data about the overall archive operation.

The context object will encode the size of the struct and byte offsets of each pointer within the struct (since this data is stored once, not per object, we assume that every node in the linked list is the same type).

The wrapper objects for each struct will serve two purposes: they will handle the encoding of each struct's data but they will also act as proxies for the pointers between structs — allowing us to encode pointers to objects (permitted by NSKeyedArchiver) instead of pointers to structs (not permitted).

To allow the wrapper objects to act as proxies for each pointer, we will also need a dictionary that stores the mapping from struct to associated proxy object — this mapping will be held in the context object.

Interface design

@interface BlockWrapper : NSObject <NSCoding>
{
    BlockContext *blockContext;
    void *blockPointer;
}

@property (readonly) void *blockPointer;

- (id)initWithBlockContext:(BlockContext *)aBlockContext
    blockPointer:(void *)aBlockPointer;

@end

The data for the wrapper object is very simple: a blockPointer that points to the data that the object will encode and blockContext which points to the context object for the archive operation.

I decided to name this class BlockWrapper instead of StructWrapper to properly reflect how the class handles the data it wraps — as an arbitrary block of bytes.

@interface BlockContext : NSObject <NSCoding>
{
    CFMutableDictionaryRef blockToBlockWrapperMappings;
    void *startingBlock;
    size_t blockSize;
    NSArray *pointerOffsets;
}

@property (readonly) size_t blockSize;
@property (readonly) void *startingBlock;
@property (readonly, retain, nonatomic) NSArray *pointerOffsets;

- (id)initWithStartingBlock:(void *)aStartingBlock
    blockSize:(size_t)aBlockSize
    pointerOffsets:(NSArray *)aPointerOffsets;
- (BlockWrapper *)wrapperForBlock:(void *)aBlock;

@end

The BlockContext class is fairly straightforward as well: it encodes all the previously discussed metadata about the block.

Since I wanted this code to work for any linked list node, I haven't hard-coded the number or location of pointers within each block — I store the offsets of each pointer as an array.

The wrapperForBlock: will be the correct way to find the BlockWrapper object for any of our list node pointers. This method will return the corresponding BlockWrapper from the blockToBlockWrapperMappings, creating a new BlockWrapper if one does not already exist for the given list node pointer.

Notice that I use a CFMutableDictionaryRef instead of an NSDictionary. This is because the keys in this dictionary will be the pointers to the blocks, not Objective-C objects, and NSDictionary requires that its keys be Objective-C objects. With CFMutableDictionaryRef, we can configure the dictionary to handle raw pointers.

Despite containing all this metadata during the encoding process, for its own encoding, the BlockContext only needs to save the startingBlock and pointerOffsets. The NSKeyedArchiver will implicitly store the blockSize for each encoded block and the mappings from BlockWrapper to pointer.

Encoding and decoding the BlockWrapper

- (void)encodeWithCoder:(NSCoder *)encoder
{
    [encoder encodeBytes:blockPointer length:[blockContext blockSize] forKey:@"block"];
    [encoder encodeObject:blockContext forKey:@"blockContext"];

    NSMutableArray *blockWrapperArray =
        [NSMutableArray arrayWithCapacity:[[blockContext pointerOffsets] count]];

    for (NSNumber *offsetNumber in [blockContext pointerOffsets])
    {
        NSUInteger offset = [offsetNumber integerValue];
        void *childBlock = *(void **)((NSUInteger)blockPointer + offset);
        if (!childBlock)
        {
            [blockWrapperArray addObject:[NSNull null]];
            continue;
        }

        BlockWrapper *childWrapper = [blockContext wrapperForBlock:childBlock];
        [blockWrapperArray addObject:childWrapper];
    }
    
    [encoder encodeObject:blockWrapperArray forKey:@"childBlocks"];
}

Encoding the block itself and storing a pointer to the BlockContext is simple. Most of the work in encoding relates to handling pointers to other nodes:

  • get each pointer offset
  • reading the value of the pointer from the block
  • map the pointer's value to a BlockWrapper object using the blockContext
  • encoding each referenced BlockWrapper in an NSArray using the childBlocks key

Notice that NULL pointers still require a NSNull object in the childBlocks array so that the indices in this array always correspond to the indices in the pointerOffsets array.

The decode process for BlockWrapper is mostly the same work in reverse: decode the block, decode the reference to the context object and then set all of the pointers according to the decoded childBlocks array.

- (id)initWithCoder:(NSCoder *)decoder
{
    self = [super init];
    if (self != nil)
    {
        NSUInteger blockSize;
        const void *bytes =
            [decoder decodeBytesForKey:@"block" returnedLength:&blockSize];
        blockPointer = malloc(blockSize);
        memcpy(blockPointer, bytes, blockSize);
        
        BlockContext *context = [decoder decodeObjectForKey:@"blockContext"];

        NSArray *childBlocks = [decoder decodeObjectForKey:@"childBlocks"];
        NSArray *pointerOffsets = [context pointerOffsets];
        NSInteger i;
        NSInteger count = [childBlocks count];
        
        NSAssert(count == [pointerOffsets count],
            @"Mismatch between childBlocks and pointerOffsets");
        
        for (i = 0; i < count; i++)
        {
            BlockWrapper *wrapperObject = [childBlocks objectAtIndex:i];
            NSNumber *offsetNumber = [pointerOffsets objectAtIndex:i];
            NSUInteger offset = [offsetNumber integerValue];
            
            void *childPointer = 0;
            if (![wrapperObject isEqual:[NSNull null]])
            {
                childPointer = [wrapperObject blockPointer];
            }
            
            *(void **)((NSUInteger)blockPointer + offset) = childPointer;
        }
    }
    return self;
}

The biggest difference between decoding and encoding is that in decoding, we need to malloc the memory for the list node (pointed to by blockPointer). When encoding, this memory was allocated externally before we began.

The result is that the code which unarchives the linked list is also responsible for free-ing it.

Conclusion

Download the complete solution (which includes a trivial sample program) LinkedListCoding.zip (48kB)

This solution will let you archive an arbitrary linked list of C structs using NSKeyedArchiver. The solution does make some assumptions — specifically, your list nodes must all be the same type and the only pointers must point to other list nodes or NULL. Other list arrangements would require changes to the solution.

Of course, this solution is not as elegant as avoiding linked lists altogether. If you have control over the code and it's simple enough, storing NSObject in an NSMutableArray is much better supported by Cocoa.

Recreating UITableViewController to increase code reuse

UITableViewController and UIViewController are the two most commonly implemented controllers on the iPhone. It may not always be clear what UITableViewController adds to its superclass. I'll show you what UITableViewController does by recreating its functionality on top of UIViewController and show you why doing this can provide a richer base controller class that you can use throughout your iPhone application.

This week, an iPhone app

In this post, I'll present a small iPhone application that displays the time in a table on the front screen, with detail screens for each component when the respective row is clicked.

timeintable.png

("second" shown on the right is the unit of time, not the 2nd row)

With this application, the code to monitor the time and update when it changes is in a base class common to both the UITableView's controller (left) and the UIView's controller (right).

If you followed the standard practice of using UITableViewController subclasses for UITableView-based screens and UIViewController subclasses for all other screens, keeping this code common would not be possible. I'll show how to make it possible by recreating the functionality of UITableViewController in your own UIViewController subclasses.

UITableViewController versus UIViewController

Between UITableView and navigation-based controllers, Apple did an excellent job of establishing a standard interaction paradigm for the iPhone. This established standard works so well that programmers use UITableViewController for most screens in their programs.

UITableViewController makes the simple, common case easier but it creates a problem if your program needs shared functionality between table view and views based on UIViewController (where self.view is not a UITableView). The problem is that common functionality for screens in your program must now be duplicated — once to include this functionality in your UIViewController subclass and once to include the functionality in your UITableViewController subclass.

My preferred solution to this problem is to create my own program-wide base class which is a subclass of UIViewController. I put my common code in the base class and when I need a controller for a UITableView, recreate the work done by UITableViewController in a subclass of my own base class which can then be the base class for all UITableView controllers in my program.

Recreating UITableViewController

To recreate it, we need to know what UITableViewController does. Given the class' ubiquity, it may be surprising to learn that it doesn't do very much.

As detailed in the API documentation, UITableViewController adds the following functionality:

  • A constructor (initWithStyle:) that sets the style for the default contructed table (if the table isn't constructed from a NIB file).
  • An implementation of loadView that creates the default table if the view controller is used without a NIB file.
  • Implementation of the tableView property.
  • Includes the UITableViewDelegate and UITableViewDataSource properties but doesn't provide any implementations of the methods.
  • Invokes setEditing:animated: on the UITableView when it is invoked on the controller.
  • Reloads the table data and clears the selection in viewWillAppear:.
  • Flashes the scroll indicators of the table in viewDidAppear:.
  • Scrolls the table so that selected cells are visible when the keyboard is shown.

I personally consider some of these "optional" and normally leave them out unless I need to use them. I normally leave out the reloading of table data altogether as I feel application logic can handle this more efficiently. What follows are the essential methods.

An implementation of loadView looks like this:

- (void)loadView
{
    if (self.nibName)
    {
        [super loadView];
        NSAssert(tableView != nil, @"NIB file did not set tableView property.");
        return;
    }
    
    UITableView *newTableView =
        [[[UITableView alloc]
            initWithFrame:CGRectZero
            style:UITableViewStylePlain]
        autorelease];
    self.view = newTableView;
    self.tableView = newTableView;
}

I've hard-coded the UITableViewStyle here instead of relying on a initWithStyle: constructor. Since this is my code, I'm happy to select the default value I want for my program here, I don't need to specify this value at initialization.

Notice that I set the self.view and the self.tableView separately. In UITableViewController, these two properties are always the same value. I like to keep a distinction between the two in my UITableView controller so that my controller can manage a wrapper view around the table view as well. Obviously in this default case, there is no wrapper, so both are set to be the same. If there were both the same, I wouldn't need the tableView ivar (see accessors below) I would use the same self.view storage for both.

The only other default code required are the tableView and setTableView: methods for the tableView property. The only important steps here are to set the table's delegate and dataSource to the controller.

- (UITableView *)tableView
{
    return tableView;
}

- (void)setTableView:(UITableView *)newTableView
{
    if ([tableView isEqual:newTableView])
    {
        return;
    }
    [tableView release];
    tableView = [newTableView retain];
    [tableView setDelegate:self];
    [tableView setDataSource:self];
}

Scrolling the table when the keyboard appears

Scrolling the table so that the current row is visible when the keyboard appears is another behavior that UITableViewController provides by default.

You can use the approach I gave in an earlier post to achieve this: Sliding UITextFields around to avoid the keyboard.

The time display application

In the sample app, my BaseViewController (a subclass of UIViewController) contains methods that start an NSTimer when the view appears and stop it when the view disappears.

This timer fires the following method:

- (void)timerUpdate:(NSTimer *)aTimer
{
    NSDate *date = [NSDate date];
    NSCalendar *calendar = [NSCalendar currentCalendar];
    
    const NSInteger unitFlags =
        NSHourCalendarUnit | NSMinuteCalendarUnit | NSSecondCalendarUnit;
    NSDateComponents *components =
        [calendar components:unitFlags fromDate:date];
    
    if (![components isEqual:lastComponents])
    {
        [lastComponents release];
        lastComponents = [components retain];
        [self updateWithDateComponents:components];
    }
}

The updateWithDateComponents: is empty but subclasses of BaseViewController can implement it to update themselves when the time changes. In this way, every screen in my application automatically receives per-second updates.

The TimeTableViewController in the application is then a subclass of BaseViewController which further adds UITableViewController-like functionality (as shown above) and combines the two to constantly update the time components in the table.

The DetailViewController (which is constructed when a row is clicked) is also a subclass of BaseViewController but when an updateWithDateComponents: message is received, only displays the component for which it is the "detail" view.

Conclusion

You can download the complete code for the RecreatingTableViewController application (29kB) discussed in this post.

UITableViewController exists to make working with simple tables slightly quicker, since they are the most common type of primary view on the iPhone.

However, this class is merely a convenience and if your design requires it you can avoid UITableViewController entirely — as in this post where the inheritance worked better without using UITableViewController.

Scripted window management in Xcode

Xcode's placement of windows and views has never entirely satisfied me. In this post, I'll show you a series of Applescripts that I use to create my own arrangement of Xcode windows so that I can choose where different kinds of documents are placed and reorganize the layout of windows with basic key commands.

Xcode's window layout options

To show multiple files in Xcode's "Default" or "All-in-one" you need to open a second window since Xcode's project window does not support two neat column panes in the project window [edit: Yes it does. See first the first comment.]. This bothers me because I like to keep my windows tidy, so I found myself manually positioning these external windows a lot.

Furthermore, if you have positioned your main project window to look pretty when showing an 80 to 120 character width text document, opening a fundamentally different kind of document in the window (like a Core Data .xcdatamodel) requires that you resize the project window to view the new document properly and resize back again when done.

I could use the "Condensed" layout that Xcode provides which puts everything in a separate window by default — but this doesn't solve the "manual repositioning" problem and puts extra columns into the tree-view of the project window which I find cluttering and unnecessary.

Choose your own layout

In an effort to address all the things I dislike about Xcode's default layouts, I decided to create a series of Applescripts that would position windows where I want them and could do so based on the type of window (source document, Find results, Build results, Core Data .xcdatamodel, etc). The result is a "virtual" all-in-one window where the panes are positioned according to my choices and I can shift documents from the left-column to the right column or to fullscreen with a basic key command.

Here's a screenshot of my layout showing two edit windows in columns and the project window on the left:

myxcodelayout.png

I clearly use a minimalist layout but the approach I will present could be used to put find and build results at the top of one column and reserve the second column for the debugger and console.

The Xcode layout required is the "Default" layout but I collapse the Project window down to just the tree-view by double-clicking the "double-vertical-bar-and-arrow" icon at the right of the tree-view header.

Keyboard shortcuts and working without the toolbar

The only two toolbar items I use are the "Build Configuration" and "Active SDK" popup menus. I use the standard set in the Debug Window but for building I consider it a waste of time. There are only a few keyboard shortcuts you need for Xcode and you really should know them:

  • ⌘Y — Build and Debug. This should be your most-used key command.
  • ⌘⇧D — Open a file by name. Much faster than using the Project Tree for large projects.
  • ⌘⇧Y — Show the Debug Window.
  • ⌘⇧F — Show the Find Window.
  • ⌘⇧R — Show the Run Console.
  • ⌘+option+W — Close all windows of the current type (fast way to close all source windows)
  • F10 (or Control + Dashboard button on new keyboards) — Show the current app's windows.

To this collection of keyboard shortcuts, I'll add the following:

  • ⌘1 —Position the front-most window in the first column.
  • ⌘2 —Position the front-most window in the second column.
  • ⌘3 —Position the front-most window filling the first and second columns.
  • ⌘4 —Reposition all windows based on type.

The positioning scripts

The following is the Xcode user script for positioning the front-most window in the first column:

#! /usr/bin/osascript

set screenWidth to 1680
set screenHeight to 1050
set dockBottomPadding to 73
set dockLeftPadding to 0
set dockRightPadding to 0

set projectWindowWidth to 300
set menubarHeight to 22

set docWidth to (screenWidth - dockLeftPadding - dockRightPadding - projectWindowWidth) / 2
set leftDocBounds to {dockLeftPadding + projectWindowWidth, dockBottomPadding, screenWidth - dockRightPadding - docWidth - 1, screenHeight - menubarHeight}

tell application "Xcode"
    set bounds of item 1 of windows to leftDocBounds
end tell

To make this work, add it to your Xcode User Scripts as Input=No Input, Directory=Selection, Output=Discard Output, Error=Display in Alert. I then set the shortcut to ⌘1. If you've never added an Xcode User Script before, I explain the process more thoroughly in an earlier post.

Since it is difficult to get the actual screen size using Applescript (see John Gruber's pain in trying) I've hardcoded my screen size into the script. Change the width and height if your screen is a different size and change the dock padding values if your dock is a different height or placement.

This much is fairly simple. Much more interesting is the "reposition everything" script:

Update 2009-10-19: changed to split strings using a specified delimiter so the extension is extracted consistently (not affected by locale settings).
#! /usr/bin/osascript

set screenWidth to 1680
set screenHeight to 1050
set dockBottomPadding to 73
set dockLeftPadding to 0
set dockRightPadding to 0

set projectWindowWidth to 300
set menubarHeight to 22

set docWidth to (screenWidth - dockLeftPadding - dockRightPadding - projectWindowWidth) / 2
set projectBounds to {dockLeftPadding, dockBottomPadding, projectWindowWidth + dockLeftPadding - 1, screenHeight - menubarHeight}
set leftDocBounds to {dockLeftPadding + projectWindowWidth, dockBottomPadding, screenWidth - dockRightPadding - docWidth - 1, screenHeight - menubarHeight}
set rightDocBounds to {screenWidth - dockRightPadding - docWidth, dockBottomPadding, screenWidth - dockRightPadding - 1, screenHeight - menubarHeight}
set fullDocBounds to {dockLeftPadding + projectWindowWidth, dockBottomPadding, screenWidth - dockRightPadding - 1, screenHeight - menubarHeight}

-- save delimiters to restore old settings
set oldDelimiters to AppleScript's text item delimiters
-- set delimiters to delimiter to be used
set AppleScript's text item delimiters to {".", " - "}

tell application "Xcode"
    set leftHalfScreenSuffixes to {"m", "c", "h", "mm", "cpp"}
    set rightHalfScreenSuffixes to {"Results", "Find", "Console"}
    set fullScreenSuffixes to {"xcdatamodel", "Debugger"}
    set processedWindows to {}
    repeat with doc in documents
        set docName to name of doc
        if (length of docName) is greater than 10 then
            set docNameMinusExtension to text 1 thru ((length of docName) - 10) of docName
        else
            set docNameMinusExtension to ""
        end if
        repeat with win in windows of doc
            set n to name of win
            try -- wrap in a try in case the window name is undefined
                set end of processedWindows to name of win
                if n is equal to docNameMinusExtension then
                    set bounds of win to projectBounds
                else
                    set extension to last item in text items of n
                    if extension is in leftHalfScreenSuffixes then
                        set bounds of win to leftDocBounds
                    else if extension is in rightHalfScreenSuffixes then
                        set bounds of win to rightDocBounds
                    else if extension is in fullScreenSuffixes then
                        set bounds of win to fullDocBounds
                    end if
                end if
            end try
        end repeat
    end repeat
    repeat with win in windows
        if not (processedWindows contains name of win) then
            set n to name of win
            try -- wrap in a try in case the window name is undefined
                set extension to last item in text items of n
                log extension
                if extension is in leftHalfScreenSuffixes then
                    set bounds of win to leftDocBounds
                else if extension is in rightHalfScreenSuffixes then
                    set bounds of win to rightDocBounds
                else if extension is in fullScreenSuffixes then
                    set bounds of win to fullDocBounds
                end if
            end try
        end if
    end repeat
end tell

set AppleScript's text item delimiters to oldDelimiters

This script iterates over the windows for each document, then over all windows not attached to a document to reach every window that Xcode has open. It then uses the window's title to decide where to place each window. Source code files are placed in the first column, results windows are placed in the second column and the Debugger is made dual column. This script also positions the Project window.

The "position in the second column" and "position filling first and second columns" scripts are just like the first script but with rightDocBounds and fullDocBounds from the second script respectively.

Conclusion

A few scripts to reposition your windows and connected to the shortcuts ⌘1 to ⌘4 is not a revolutionary idea but I don't think I was alone among Xcode programmers in continuously repositioning my windows as I opened and shut new documents and switched from debugging to editing to build results and back.

These scripts only save a few seconds at a time but they make Xcode feel much more magical as windows jump to exactly where I want them to be.

I doubt everyone will want to position their windows exactly as I have but these scripts should be easily adaptable to a range of different layouts — just tweak the calculated bounds and the sets of Window suffixes that are placed at each bounds.

An Asteroids-style game in CoreAnimation, Part Four.

Over the last three weeks, I presented a simple 2D game using CoreAnimation. For the final post in this series, I'll look at CATransactions and why I didn't use them in the game to handle animations and I'll look at the performance of CoreAnimation as numbers of CALayers and sizes of CALayers change.

Frame-based animation

The Quartzeroids2 game (download the complete code from the previous post) uses traditional frame-based updates to process, position and render all objects on screen. This works much like stop-motion animation as filmed with optical cameras: a frame is needed approximately every 30th of a second so the game moves all objects to their locations for this new frame (as determined by speed and trajectory) and the renderer takes a snapshot.

As with stop-motion animation, the only reason this process appears smooth to the eye is because the frames are frequent enough that they run together appearing like motion.

This is the traditional way that 2D games are implemented. Initially though, I wanted to handle the game in a different way. Frame-based animation has two main problems:

  1. The CPU must reprocess all game objects 30 times a second (or more) to place them on screen, creating a continuous burden on the CPU.
  2. Even at 30 frames a second, fast moving objects leave distinct gaps which can cause problems with collision detection.

The following diagram illustrates the second point:

framesversuscontinuous.png

The blue and red balls never touch during a keyframe but if they were moving continuously would clearly collide in the middle. Such collisions could be detected by significantly increasing the frame-rate but that isn't always technically possible and would certainly make the first problem (excessive CPU usage) worse.

Continuous animation using CATransactions

What I wanted to do instead of frame-based animation was to create a continuous game instead.

The idea would be: instead of the game engine reprocessing for each frame, just load the speeds and trajectories into CoreAnimation and let the animation run automatically until the next "event" (collision or user action). That way, the animation runs smoothly, the game engine performs the minimum amount of work and all collisions are mathematically perfect (since we calculate them in advance using trajectory equations instead of reading quantized data at frame update time).

Continuous animation would involve taking the basic line equation (y = mx + b) for the two bounding edges of each object's trajectory and colliding it with the bounding box of the screen and every other object's trajectory equations. Between now and that first collision each object could be animated using a CoreAnimation CAAnimation, with the animations for all objects tied together using a CATransaction.

The first downside to this was adding user involvement. When the user presses a key, they are changing the modelling for their player object which involves recalculating the next collision. This means that while the user is pressing a key, 30 recalculations per second may be required. On its own, this negative won't outweigh the positives. Recalculating in his manner isn't much more work than traditional frame-based collision detection which is always performed 30 frames-per-second or more — and these collisions would still be mathematically perfect.

Testing CATransactions

To see how the worst case of 30 updates per second would perform, you can add CATransaction-based animation to Quartzeroids2 by removing the actionForKey: method from "ImageLayer.m" in the program and replacing the following code in "GameObjectLayer.m":

self.imageName = gameObjectImageName;
self.bounds = CGRectMake(0, 0, width, height);
self.position = CGPointMake(x, y);
self.transform = CATransform3DMakeRotation(angle, 0, 0, 1.0);
self.hidden = !visible;

with the CATransaction based version:

double distance =
    sqrt((self.position.x - x) * (self.position.x - x) +
    (self.position.y - y) * (self.position.y - y));
BOOL wrapping = distance > gameHeight;

if (wrapping)
{
    [self removeAllAnimations];
}

[CATransaction begin];
[CATransaction
    setValue:[NSNumber numberWithDouble:GAME_UPDATE_DURATION]
    forKey:kCATransactionAnimationDuration];

if (wrapping)
{
    [CATransaction
        setValue:[NSNumber numberWithBool:YES]
        forKey:kCATransactionDisableActions];
}

self.imageName = gameObjectImageName;
self.bounds = CGRectMake(0, 0, width, height);
self.position = CGPointMake(x, y);
self.transform = CATransform3DMakeRotation(angle, 0, 0, 1.0);
self.hidden = !visible;

[CATransaction commit];
Performance-based failure

The following performance numbers are running on my 2 x 2Ghz PowerMac G5.

Number of CALayers animated using CATransactionFrames per second
50> 33
7510-25
100<10
150<2

I've given ranges since the frames per second varied significantly. This compares poorly with the CATransaction disabled version, where all tests ran faster than 30 frames per second.

Since each asteroid represents two separate objects and every shot fired is another object on screen, I decided that an inability to handle more than 50 objects smoothly was unacceptable and discarded the CATransaction-based approach.

Clearly, CATransaction-based animation has a significant amount of work to perform and this work increases more-than-linearly (greater than O(n)) with respect to the number of objects on screen. In CoreAnimation, you aren't expected to regenerate thousands of animations each second like this. I leave open the possibility that there's a modified approach that could still make this work but I didn't want to spend further time investigating.

Testing the render system in Quartzeroids2

To perform a series of performance tests on Quartzeroids2's rendering system, I removed the PlayerObject from the game, disabled the AsteroidLayerObject added for each asteroid by the GameController and used the ASTEROID_LARGE_SIZE and ASTEROID_BASE_NUM values to control the size and number of objects on the screen. I measured frame rates with the Quartz Debug frame meter.

Object size tests

The following test all involved 100 CALayers on screen. My graphics card is an ATI Radeon X800 with 256MB VRAM.

Width and Height of CALayer in pixelsFrames per second
110> 33
440> 33
660> 33
770> 33
880< 5

Once you exceed the available video memory in CoreAnimation, frame rate immediately plummets. Some new Macs have double the VRAM that I have but many still ship with 256MB VRAM as standard, so these numbers are probably indicative of the average among newer machines.

Object count tests

The following tests all involved 11 pixel by 11 pixel objects.

Number of CALayers on screenFrames per second
100> 33
200> 33
300> 33
40020
50018
60012
7009
800< 5

Profiling the 800 object version revealed CPU time was mostly spent in CALayer updating layer positions — so this would appear to be a basic CPU bound situation for CoreAnimation on the test machine. On newer Mac Pros, I wouldn't be surprised if object counts over 1000 were possible at 30 frames per second.

Other CALayer limitations

Depending on your graphics card, you may have a maximum texture size. On my ATI Radeon X800, that size is 2048 by 2048. Any texture bigger than 2048 in any CALayer with a native size bigger than 2048 in any direction will result in an empty white square when rendered, instead of the expected texture. CALayer does output an error when this occurs:

CoreAnimation: 2049 by 2049 image is too large for GPU, ignoring

Newer cards have maximum texture sizes of 4096 and even 8192 pixels. A hard limit here for your target systems could be difficult to know.

Conclusion

CoreAnimation is incredibly capable as a 2D renderer. I have spent this post discussing its limits but that is not because I consider its capabilities limiting but because I am impressed by how much it can do. With CoreAnimation layers, you can render hundreds of objects, each of which can be hundreds of pixels big, without paying any attention to performance — you can simply let CoreAnimation handle it.

Obviously, for the Quarteroids2 game I developed, most of this testing was irrelevant but it may prove useful to anyone looking to use CoreAnimation in a more ambitious manner.

An Asteroids-style game in CoreAnimation, Part Three.

How would you write an arcade-style 2D game in CoreAnimation? I'll show you how to write a resolution independent, high-speed, model-view-controller designed, Asteroids-style arcade game using CoreAnimation as the screen renderer. In this third of four parts, I add the logic for the game and game objects and present the finished code for the project.

From renderer to game

In the previous post, I presented a rendering system using CoreAnimation layers (CALayer). To complete the game, we now need to add the game logic.

For this Asteroids-style game, the game logic will be very simple but will need to include the following components:

  • User control of the ship
  • Shooting and shot/asteroid collision detection and destruction.
  • Player/asteroid collision and a finite number of player "lives"
  • Level logic, so that a new, harder level is started when the previous one is cleared.

With the game logic added, the code for the project will be complete.

quartzeroidspart3.png

A screenshot of the game with shots and asteroid destruction.

User control

Most games treat keyboard input in a different manner to applications. Instead of reading keyDown: messages, including the isARepeat messages (whose delay and frequency are specified in the System Preferences), games simply want the state of specific keys at a given time. e.g. "Is the 'thrust' key pressed?"

To provide the game with what it wants, I created a subclass of NSView to use as the contentView of the window. The sole purpose of this view subclass is to read key event messages passed to the window. When keyDown: messages are received, boolean values on the GameData object are set. When the keyUp: message is received, the boolean values are cleared. In this way, we store the keyboard state so we can read it in an asynchronous manner whenever it is needed.

The implementation of the keyDown: method follows.

- (void)keyDown:(NSEvent *)event
{
    NSString *characters = [event characters];
    if ([characters length] == 1 && ![event isARepeat])
    {
        const NSInteger ESCAPE_KEY_CODE = 27;
        
        unichar character = [characters characterAtIndex:0];
        if (character == NSLeftArrowFunctionKey)
        {
            [[GameData sharedGameData] setLeftKeyDown:YES];
        }
        else if (character == NSRightArrowFunctionKey)
        {
            [[GameData sharedGameData] setRightKeyDown:YES];
        }
        else if (character == NSUpArrowFunctionKey)
        {
            [[GameData sharedGameData] setUpKeyDown:YES];
        }
        else if (character == ' ')
        {
            [[GameData sharedGameData] setShootKeyDown:YES];
        }
        else if (character == ESCAPE_KEY_CODE)
        {
            [gameController togglePause:self];
        }
    }
}

Notice that Apple provide constants for higher level keys (like the arrow keys) but you are expected to handle ASCII codes (like the Escape key) yourself. You can get these from the ASCII manual page (man ascii in a terminal window). Be careful to avoid the octal set — I have no idea how it earned first position in this file.

To respond to these new keyboard flags, I will create a subclass of GameObject (the generic class representing an object in the game) named PlayerObject to handle the player's ship. The real purpose of this subclass will be to add game-logic related behaviors. The primary location for adding behaviors will be an override of the parent class' updateWithTimeInterval: that supplements the default behavior with player-specific movement and interaction.

Here is the code to handle the "thrust" key (the up arrow):

if ([GameData sharedGameData].upKeyDown)
{
    double scaledAcceleration = timeInterval * PLAYER_ACCELERATION;
    double dX = speed * cos(trajectory) + scaledAcceleration * cos(angle + M_PI_2);
    double dY = speed * sin(trajectory) + scaledAcceleration * sin(angle + M_PI_2);
    
    speed = sqrt(dX * dX + dY * dY);
    trajectory = acos(dX / speed);
    if (dY < 0)
    {
        trajectory *= -1;
    }
    
    if (speed > PLAYER_MAX_SPEED)
    {
        speed = PLAYER_MAX_SPEED;
    }
}

This code is some basic trigonometry to add the ship's current speed/trajectory vector to the new thrust vector, limiting the ship's maximum speed. The actual x and y of the ship is modified by invoking the super implementation (which applies this speed and trajectory).

Model-view-controller design note
This approach to key control is not typical of an application. In an application, a user-interface controller chooses the target object and sends the keyboard control directly to that object. In this game, the user-interface sets keyboard state in a game-accessible location and game objects choose whether to incorporate that state into their own. This behavior is good for a game because it allows the game objects to choose their own interaction logic but games represent a special case in this regard.

Firing shots

The other key aspect of user control in the game is the ability to fire shots.

Once again, I will use a GameObject subclass to handle the shots. These ShotObjects will be created in the PlayerObject's updateWithTimeInterval: method, since they will need to incorporate speed and trajectory information from the PlayerObject.

The following code fires a shot when the user presses the 'shoot' key (spacebar).

ShotObject *newShot =
    [[ShotObject alloc]
        initWithX:x + 0.5 * width * cos(angle + M_PI_2)
        y:y + 0.5 * height * sin(angle + M_PI_2)];
[[GameData sharedGameData]
    addGameObject:newShot
    forKey:[[GameData sharedGameData] keyForShotAtIndex:nextShotIndex]];

nextShotIndex = (nextShotIndex + 1) % PLAYER_MAX_SHOTS;
[[GameData sharedGameData]
    setGameDataObject:[NSNumber numberWithInteger:nextShotIndex]
    forKey:GAME_DATA_NEXT_SHOT_INDEX_KEY];

double dX = speed * cos(trajectory) + PLAYER_SHOT_SPEED * cos(angle + M_PI_2);
double dY = speed * sin(trajectory) + PLAYER_SHOT_SPEED * sin(angle + M_PI_2);
double shotSpeed = sqrt(dX * dX + dY * dY);
double shotTrajectory = acos(dX / shotSpeed);
if (dY < 0)
{
    shotTrajectory *= -1;
}
newShot.speed = shotSpeed;
newShot.trajectory = shotTrajectory;

shotCooldown = PLAYER_SHOT_COOLDOWN;

The initWithX:y: line creates the ShotObject.

The addGameObject:forKey: part adds it to the game. GameObjects are all stored by a single key in this game but I use the keyForShotAtIndex: to create this key from a prefix ("shot") and a suffix (the shot's index) so that I can extract information about the object from its key.

This is a lazy approach to organizing game objects and any larger game would want to store its objects in a more metadata rich storage system. Better organizations might include:

  • metadata methods on each game object so you can query each object about what it is
  • additionally storing game objects in dictionaries keyed by type or other essential category information
  • storing game objects in richly indexed system like an SQLite database (which is then accessible by any column)

The setGameDataObject:forKey: line sets the number of shots that the player has fired in the GameData's generic object storage. This will allow us to limit the number of shots fired by the player to PLAYER_MAX_SHOTS.

The next code is some more trigonometry to apply the ship's speed and trajectory to the shot. Then finally the shotCooldown value is set. This is a simple counter (decremented on each updateWithTimeInterval:) which will prevent another shot being fired while it is greater than zero (allowing us to set the minimum time between shots).

Collisions

Last week's code contained a very simple main update loop that called the updateWithInterval: method on all GameObjects. This time, we expand the update loop to the following:

- (void)updateLevel:(NSTimer *)aTimer
{
    if (lastUpdate)
    {
        frameDuration = [[NSDate date] timeIntervalSinceDate:lastUpdate];
        [lastUpdate release];
        lastUpdate = [[NSDate alloc] init];
    }
    else
    {
        frameDuration = GAME_UPDATE_DURATION;
    }
    
    NSArray *allKeys = [gameObjects allKeys];
    for (NSString *gameObjectKey in allKeys)
    {
        [gameObjects willChangeValueForKey:gameObjectKey];
        GameObject *gameObject = [gameObjects objectForKey:gameObjectKey];
    
        if ([gameObject collide])
        {
            [gameObjects removeObjectForKey:gameObjectKey];
        }
    }
    for (NSString *gameObjectKey in allKeys)
    {
        GameObject *gameObject = [gameObjects objectForKey:gameObjectKey];
        if (!gameObject)
        {
            [gameObjects didChangeValueForKey:gameObjectKey];
            continue;
        }
        
        if ([gameObject updateWithTimeInterval:frameDuration])
        {
            [gameObjects removeObjectForKey:gameObjectKey];
        }
        [gameObjects didChangeValueForKey:gameObjectKey];
    }
}

We time the duration between updates ourselves, even though we ask the NSTimer to invoke us every 0.03 seconds. This allows us to keep the animation as smooth as possible even if the timer is delayed or frames start taking longer than 0.03 seconds to complete.

After this, we iterate over all the GameObjects twice: once to process collisions and once to update positions. The reason for this separation is to ensure that all of the game objects are at the same moment in time when we process them for collisions — if we processed collisions during the update of positions then everything already updated for position would be 1 frame ahead of objects not yet processed when collisions are tested.

I chose to perform collisions before the update so that the collision applies to what the user can currently see (rather than what they will see after CoreAnimation updates).

Performing collisions is very simple — especially in this game since I'm only performing bounding box collisions. The collision code in ShotObject which tests for collisions between shots and asteroids follows.

- (BOOL)collide
{
    NSString *collision = [[[GameData sharedGameData]
            collideObjectsWithKeyPrefix:GAME_ASTEROID_KEY_BASE
            withObjectForKey:keyInGameData]
        anyObject];
    if (collision)
    {
        [AsteroidObject spawnNewAsteroidsReplacing:collision];
        return YES;
    }
    return NO;
}

Once again, I'm using the prefix metadata in my game object keys to select asteroids for collisions.

The collision code lives on the GameData class.

- (NSSet *)collideObjectsWithKeyPrefix:(NSString *)prefix withObjectForKey:(NSString *)testObjectKey
{
    GameObject *testObject = [gameObjects objectForKey:testObjectKey];
    NSMutableSet *result = [NSMutableSet set];
    
    NSRect testRect = NSMakeRect(
        testObject.x - 0.5 * testObject.width,
        testObject.y - 0.5 * testObject.height,
        testObject.width,
        testObject.height);
    
    for (NSString *gameObjectKey in gameObjects)
    {
        if ([gameObjectKey isEqualToString:testObjectKey] ||
            [gameObjectKey rangeOfString:prefix].location != 0)
        {
            continue;
        }
        
        GameObject *gameObject = [gameObjects objectForKey:gameObjectKey];
        NSRect gameRect = NSMakeRect(
            gameObject.x - 0.5 * gameObject.width,
            gameObject.y - 0.5 * gameObject.height,
            gameObject.width,
            gameObject.height);
        
        if (NSIntersectsRect(gameRect, testRect))
        {
            [result addObject:gameObjectKey];
        }
    }
    
    return result;
}

This code creates a bounding rectangle from the GameObject specified by the testObjectKey and collides it with all objects stored by keys starting with prefix that aren't the testObject itself.

This code returns the whole set of colliding objects — overkill since the game only ever uses one at a time — but functional and easily fast enough for our purposes.

Tying it all together

We can control the ship, shoot and hit asteroids. There's a bit more that's in the game that you can see if you want:

  • The shots animate through 5 frames and expire after a fixed amount of time. I chose to store the current animation frame in the game data and handle the animation there (instead of in the view like the asteroid animation was in the last post). I wanted to show that animation state could be part of the game data if it is data-related (this animation isn't really data-related so I have some regrets).
  • The asteroids start at random locations in a ring around the player for each level and spawn 3 smaller asteroids when shot, each of which travels in a random direction with a random rotation.

Instead of dwelling on that, I'll jump to the last part of the game logic: the game (including lives) and the levels.

I want the following behaviors in the game:

  • The player begins with 3 lives at level 1.
  • Each level starts with a "Prepare for level X..." message for a few seconds before displaying the contents of the level and starting normal play.
  • Every time the player loses a life (collides with an asteroid) the game displays an "X lives remaining..." message for a few seconds before positioning the player in the middle of the screen and starting normal play again.
  • When the number of lives hits zero, a "Game Over" message is displayed and the game is stopped.

The data containing the number of lives and the current level are just objects in the gameData dictionary. Creating a new level creates (3 + levelNumber) asteroids and places the player in the center. The messages are just a string, set using a specific GAME_DATA_MESSAGE_KEY, also on the gameData dictionary. These values are displayed by using bindings to connect them to ordinary NSTextFields in the window.

More interesting is that the game needs to change its underlying behavior when the player dies or a new level begins.

The solution I chose is to maintain two different update loops for the two basic behaviors. The updateLevel: method I've already shown is the "normal" update method. A second update method named readyCountdown: will be used to do nothing (not update the GameObjects) for a few seconds while a message is displayed, before returning to the regular update method.

Along with newGame, newLevel and endGame methods, the game now has the ability to transition between different gameplay states.

Conclusion

Download the complete, finished game Quartzeroids2.zip (239 kB).

With the window and design from the first part, the rendering and layers from the second part and now the game logic, the game is complete. Download it, build it, play it and be underwhelmed by its simplicity.

In the final part, I'll present analysis of CoreAnimation's utility as a game rendering engine. I'll look at some features of CoreAnimation that I didn't use, including features that impacted negatively on performance. I'll also look at how CoreAnimation performance changes as the number of render objects is increased.