Minesweeper (Part 2)

Today, we take a first look at rendering our playfield. We find that a naive, UIView-based approach is unsatisfactory, and take a detour into the exciting world of vector graphics.

Slow!

When I turned to the question of how to render the Minesweeper playfield, my first thought was to tile my UIScrollView with a 2-D array of (let’s say) 32×32 UIViews. The performance of this approach was unsatisfactory on the device (iPhone 3G).

It might then have been prudent to deploy some diagnostics in an attempt to figure out why this approach was slow. I chose not to, as (a.) the simplicity of my test case led me to conclude that the slowdown must be buried in the framework, and (b.) previous experience with large numbers of on-screen UIKit objects (130 in this case) had conditioned me to expect this behavior.

Therefore, I decided to turn to vector graphics, drawn through the Quartz interface. Aside from being interesting, this approach seems inherently lighter-weight (and therefore faster) than the UIView strategy, and its lower-level and more granular nature should afford us greater opportunities for analysis and tuning.

Return to Zoom

Let’s return to the zooming scroll view of two weeks ago. In that demo, I used plain UIViews to tile the scroll view. Since these were 320×460 views, and at most 9 were onscreen at any one time, they did not suffer from the performance problems discussed above. These views also didn’t do anything interesting. Today we’ll fix that. (The complete source code for today’s demo can be downloaded here.)

Tiles

Let’s define a tile class (and a tile delegate, the purpose of which we’ll see in a bit):

@class TileView;

@protocol TileViewDelegate

- (CGAffineTransform)transformForTileView:(TileView*)tileView;
- (NSArray*)pathGroupsForTileView:(TileView*)tileView;

@end


@interface TileView : UIView
{
	id<TileViewDelegate>	delegate;
}

@property (nonatomic, assign) id<TileViewDelegate> delegate;

@end

The only interesting method of TileView is drawRect:, shown below:

- (void)drawRect:(CGRect)rect
{
	CGContextRef context = UIGraphicsGetCurrentContext();

	// Rendering the paths
	CGContextConcatCTM(context, [self.delegate transformForTileView:self]);

	NSArray* pathGroups = [self.delegate pathGroupsForTileView:self];
	for (PathGroup* pg in pathGroups)
	{
		CGContextSaveGState(context);
		
		CGContextConcatCTM(context, pg.modelTransform);
		
		for (Path* p in pg.paths)
		{
			[p renderToContext:context];
		}
		
		CGContextRestoreGState(context);
	}
}

Okay – what about those Paths and PathGroups?

Paths

Paths wrap a CGPathRef and associated graphics state information:

@interface Path : NSObject
{
	CGPathDrawingMode	drawMode;
	CGFloat			strokeWidth;
	UIColor*		color;
	CGPathRef		path;
}

@property (nonatomic, assign) CGPathDrawingMode drawMode;
@property (nonatomic, assign) CGFloat strokeWidth;
@property (nonatomic, retain) UIColor* color;

- (CGPathRef)path;
- (void)setPath:(CGPathRef)newPath;

- (void)renderToContext:(CGContextRef)context;

@end

The Path implementation is pretty much as you might imagine. Points of interest are the custom path accessors, the defaults set in init, and the (perhaps) surprisingly simple renderToContext: method:

@implementation Path

@synthesize drawMode;
@synthesize strokeWidth;
@synthesize color;

- (CGPathRef)path
{
	return path;
}

- (void)setPath:(CGPathRef)newPath
{
	if (path != newPath)
	{
		CGPathRelease(path);
		path = CGPathRetain(newPath);
	}
}


- (id)init
{
    	if (self = [super init])
	{
		self.drawMode		= kCGPathStroke;
		self.strokeWidth	= 10;
		self.color		= [UIColor blackColor];
	}
	return self;
}


- (void)renderToContext:(CGContextRef)context
{
	if (!path) return;
	
	CGContextAddPath(context, path);
	[color set];
	CGContextSetLineWidth(context, strokeWidth);
	CGContextDrawPath(context, drawMode);
}


- (void)dealloc
{
	[color release];
	CGPathRelease(path);
	[super dealloc];
}

@end

PathGroups are simpler, but arguably more critical; they tie together a group of Paths with a CGAffineTransform, and it is this transform that moves the path from model to world space:

@interface PathGroup : NSObject
{
	NSMutableArray*		paths;
	CGAffineTransform	modelTransform;
}

@property (nonatomic, retain) NSMutableArray* paths;
@property (nonatomic, assign) CGAffineTransform	modelTransform;

@end

The PathGroup implementation is unremarkable, aside from some defaults:

@implementation PathGroup

@synthesize paths;
@synthesize modelTransform;

- (NSMutableArray*)paths
{
	if (!paths)
	{
		paths = [[NSMutableArray alloc] initWithCapacity:1];
	}
	return paths;
}


- (id)init
{
	if (self = [super init])
	{
		modelTransform = CGAffineTransformMakeScale(1.0, 1.0);
	}
	return self;
}


- (void)dealloc
{
	[paths release];
	[super dealloc];
}

@end

Integration

To use all this shiny new code, our main view controller must:

• Create TileViews in lieu of ordinary UIViews
• Adopt the TileViewDelegate protocol, and set itself as the delegate of the UIViews that it creates
• Return something interesting and appropriate for:
  • transformForTileView:
  • pathGroupsForTileView:

The first of these requirements implies a simple change to addTileForFrame:, as shown below:

- (UIView*)addTileForFrame:(CGRect)frame
{
	TileView* tv = [extraTiles anyObject];
	if (tv)
	{
		// tv also retained by tiles
		[extraTiles removeObject:tv];
	}
	else
	{
		tv = [[TileView new] autorelease];
		tv.clearsContextBeforeDrawing = NO;
		tv.backgroundColor = [UIColor grayColor];
		tv.delegate = self;
		[tiles addObject:tv];
		
		UILabel* label = [[[UILabel alloc] initWithFrame:CGRectMake(0, 0, tileSize.width, 18)] autorelease];
		label.backgroundColor = [UIColor clearColor];
		label.font = [UIFont systemFontOfSize:18];
		label.tag = labelTag;
		[tv addSubview:label];
	}
	
	[self.content addSubview:tv];
	tv.frame = frame;
	[tv setNeedsDisplay];
	return tv;
}

The latter requirements involve the delegate methods. Of these, transformForTileView is simpler, and the implementation shown here is generally applicable:

- (CGAffineTransform)transformForTileView:(TileView*)tileView
{
	CGPoint o = tileView.frame.origin;
	CGAffineTransform s = CGAffineTransformMakeScale(scale, scale);
	CGAffineTransform t = CGAffineTransformMakeTranslation(-o.x, -o.y);
	return CGAffineTransformConcat(s, t);
}

On the other hand, pathGroupsForTileView: is highly application-specific. As its name implies, it’s supposed to return the set of PathGroups that overlap a particular tile. For the purposes of this demo, I’ve written a very simple function that always returns the same PathGroup; it will be clipped out of tiles it does not overlap during rendering. (That’s not what you’d want to do in production, though!)

- (NSArray*)pathGroupsForTileView:(TileView*)tileView
{
	CGMutablePathRef	p;
	Path*			path;
	PathGroup*		pg = [[PathGroup new] autorelease];

	// Path 1
	path = [[Path new] autorelease];
	p = CGPathCreateMutable();
	CGPathAddEllipseInRect(p, NULL, CGRectMake(-95, -95, 190, 190));
	path.path = p;
	path.strokeWidth = 10;
	CGPathRelease(p);
	[pg.paths addObject:path];
	// Path 2
	path = [[Path new] autorelease];
	p = CGPathCreateMutable();
	CGPathAddRect(p, NULL, CGRectMake(-69.5, -51.5, 139, 103));
	path.path = p;
	path.strokeWidth = 5;
	CGPathRelease(p);
	[pg.paths addObject:path];

	// Center it, at some reasonable fraction of the world size
	// (The bounding box of the preceeding model is 200x200, centered about 0)
	CGFloat scaleToFit = world.width*.25/200.0;
	CGAffineTransform s = CGAffineTransformMakeScale(scaleToFit, scaleToFit);
	CGAffineTransform t = CGAffineTransformMakeTranslation(world.width/2.0, world.height/2.0);
	pg.modelTransform =  CGAffineTransformConcat(s, t);

	return [NSArray arrayWithObject:pg];
}

Performance

Although we embarked on this discussion of vector graphics with performance in mind, this demo is not optimized for performance. Once we use this stuff to render a Minesweeper playfield, then it will be the time to start thinking about tuning. If necessary.

Motivation

I haven’t done a very good job of explaining the logic behind all these affine transformations. Very briefly, here’s what’s going on.

Paths represent shapes in 2D space, relative to a local origin (i.e. in “model space”). The modelTransform of a PathGroup moves these shapes into “world space”, and the transform returned by transformForTileView: moves them into the local co-ordinate system of a tile. The transforms aren’t applied explicitly; instead, they’re concatenated with a CGContextRef‘s Current Transformation Matrix, which is applied implicitly to most Core Graphics/Quartz operations.

It it helps at all, here are my internal notes on the various spaces involved in this demo:

//Spaces:
//  * Model space (The basic space in which a model's shape is defined)
//  * World space (Model spaces are scaled and rotated, then shifted to overlay world space)
//  * View space (World space is scaled to overlay view space)
//	. View space is identical with the content view's client space
//  * Tiled space (View space is scaled to overlay tiled space)
//	. Used to determine visible tiles
//  * Tile space (View space is shifted to overlay a particular tile space)
//	. A tile space is identical with a tile's client space
//  * Content space (Content view/view space is scaled and shifted to overlay content space)
//	. Content space is identical with the scroll view's client space
//  * Screen space (Content space is subjected to the normal view->screen transforms)

Coming Up

We’ll pick this up on Monday; Saturday will be something else, and on Sunday I’m going to pick on Seth Godin. Again.