Minesweeper (Part 3)

App IconToday we implement a simple vector graphics renderer for Minesweeper. While it works, and runs reasonably quickly, it causes some highly undesirable stutter on the device. Since this approach isn’t final, I’m only going to cover some of its highlights, as opposed to presenting a complete demo.

Glyphs

I’m going to generalize the code we saw on Friday, and make Path a subclass of a more general Glyph class, from which a new Text class will also inherit.

Here’s the new Text class’ declaration:

@interface Text : Glyph
{
	CGTextDrawingMode	drawMode;
	CGFloat			strokeWidth;
	UIFont*			font;
	UIColor*		color;
	CGPoint			offset;
	NSString*		string;
}

@property (nonatomic, assign) CGTextDrawingMode drawMode;
@property (nonatomic, assign) CGFloat strokeWidth;
@property (nonatomic, retain) UIFont* font;
@property (nonatomic, retain) UIColor* color;
@property (nonatomic, assign) CGPoint offset;
@property (nonatomic, retain) NSString* string;

@end

… and implementation:

@implementation Text

@synthesize drawMode;
@synthesize strokeWidth;
@synthesize font;
@synthesize color;
@synthesize offset;
@synthesize string;


- (void)renderToContext:(CGContextRef)context
{
	CGContextSetTextDrawingMode(context, drawMode);
	CGContextSetLineWidth(context, strokeWidth);
	CGContextSelectFont(context, [[font fontName] cStringUsingEncoding:NSASCIIStringEncoding], [font pointSize], kCGEncodingMacRoman);
	[color set];
	
	CGContextShowTextAtPoint(context,
				 offset.x,
				 offset.y + [font pointSize],
				 [string cStringUsingEncoding:NSMacOSRomanStringEncoding],
				 [string lengthOfBytesUsingEncoding:NSMacOSRomanStringEncoding]);
}


- (void)dealloc
{
	[font release];
	[color release];
	[string release];
	[super dealloc];
}

@end

Tiles

Most of the changes to the TileView render function are minor, related to changing the word “Path” to the word “Glyph”. There is one exception to this: The “text matrix” must be set up to flip the Y coordinate:

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

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

	NSArray* glyphGroups = [self.delegate glyphGroupsForTileView:self];
	for (GlyphGroup* gg in glyphGroups)
	{
		CGContextSaveGState(context);
		
		CGContextConcatCTM(context, gg.modelTransform);
		
		for (Glyph* g in gg.glyphs)
		{
			[g renderToContext:context];
		}
		
		CGContextRestoreGState(context);
	}
}

The reason for this text matrix fiddling can be found in the two co-ordinate systems in play on the iPhone: Most UIKit stuff places the origin of a space in the upper-left-hard corner of the screen/view/etc, while most Core Graphics/Quartz stuff places the origin in the lower-left-hand corner. The framework tries to paper over this difference by converting one system to the other. For instance, the context returned by UIGraphicsGetCurrentContext() (when called in a drawRect: method) has its Current Transformation Matrix configured to transform the UIKit convention into the Quartz convention. Unfortunately, this conversion isn’t quite seamless, and additional workarounds, such as the text matrix adjustment seen above, are sometimes necessary.

Controller

The most significant changes take place in our main view controller, which is now presumed to have a puzzle member describing the puzzle to be drawn. At this point we’re just experimenting with drawing the fully-revealed puzzle, so this is our new glyphs-for-tile method:

- (NSArray*)glyphGroupsForTileView:(TileView*)tileView
{
	CGRect cellBox = CGRectIntegral(CGRectApplyAffineTransform(CGRectApplyAffineTransform(tileView.bounds,
											      CGAffineTransformInvert([self transformForTileView:tileView])),
								   CGAffineTransformMakeScale(1/cellSize.width, 1/cellSize.height)));

	NSMutableArray* glyphGroups = [NSMutableArray arrayWithCapacity:cellBox.size.width*cellBox.size.height];
	for (int bw = cellBox.size.width, n = bw*cellBox.size.height-1; n >= 0; n--)
	{
		NSInteger x = cellBox.origin.x + n % bw;
		NSInteger y = cellBox.origin.y + n / bw;
		
		Text* t;
		if ([puzzle isMinedAtX:x andY:y])
		{
			t = [self.symbols objectAtIndex:9];
		}
		else
		{
			t = [self.symbols objectAtIndex:[puzzle neighborsAtX:x andY:y]];
		}
		
		GlyphGroup* gg = [[GlyphGroup new] autorelease];
		[gg.glyphs addObjectsFromArray:self.box];
		[gg.glyphs addObject:t];
		gg.modelTransform = CGAffineTransformMakeTranslation(x*cellSize.width, y*cellSize.height);
		[glyphGroups addObject:gg];
	}
	return glyphGroups;
}

It might not be completely obvious how I’m calculating the set of cells covered by the tile. I’m using an inverse of the world space->tile space matrix to transform the tile’s bounds rectangle from tile space into world space, then scaling that projection by the inverse of the (world-space) cell size, and snapping the resulting rectangle to integral boundaries. The origin and dimensions of the resulting cellBox are in cell indices, which can be looked up in the puzzle data structure.

The other significant change to the controller (aside from two new accessors, discussed below) involves its viewDidLoad method, in which we set up the puzzle and the world.

- (void)viewDidLoad
{
	[super viewDidLoad];
	
	puzzle = [[Puzzle alloc] initWithWidth:30 height:16 mines:99];
	[puzzle generate];
	NSLog(@"%@",puzzle);
	
	world = CGSizeMake(cellSize.width*puzzle.w, cellSize.height*puzzle.h);
	scale = 1.0;
	
	[self createTiles];
	tileBox = CGRectZero;
	
	[self sizeContent];
	self.scrollView.contentOffset = CGPointMake(-.05*self.scrollView.frame.size.width,
						    -.05*self.scrollView.frame.size.height);
	[self.scrollView flashScrollIndicators];
}

Please note that cellSize is declared as a const static CGSize, and set equal to 64×64.

Pre-Calculation

Since we’ll be using the same few graphics primitives over and over again, I precalculated a box image and a set of symbols. These are referenced with calls to the self.box and self.symbols accessors in the code above.

- (NSArray*)symbols
{
	if (!symbols)
	{
		char* codes = "012345678X"; int n = strlen(codes);

		symbols = [[NSMutableArray alloc] initWithCapacity:n];
		NSMutableArray* mySymbols = (NSMutableArray*) symbols;
		
		for (int i = 0; i < n; i++)
		{
			Text* t = [[Text new] autorelease];
			t.drawMode = kCGTextFillStroke;
			t.strokeWidth = 1.0;
			t.font = [UIFont systemFontOfSize:18];
			t.color = [UIColor blackColor];
			t.offset = CGPointMake(.5*cellSize.width-7, .5*cellSize.height-10);
			t.string = [NSString stringWithFormat:@"%c",codes[i]];
			[mySymbols addObject:t];
		}
	}
	return symbols;
}
- (NSArray*)box
{
	if (!box)
	{
		// Basic (top) trapezoid
		CGFloat w = 5;
		CGPoint points[4]  = {CGPointMake(0, 0), CGPointMake(cellSize.width, 0), CGPointMake(cellSize.width-w, w), CGPointMake(w, w)};

		// Paths
		CGMutablePathRef p;
		CGAffineTransform m;
		// Top
		m = CGAffineTransformMakeScale(1.0, 1.0);
		Path* t = [[Path new] autorelease];
		p = CGPathCreateMutable();
		CGPathAddLines(p, &m, points, 4);
		t.path = p;
		t.color = [UIColor colorWithWhite:.7 alpha:1.0];
		t.drawMode = kCGPathFill;
		CGPathRelease(p);
		// Bottom
		m = CGAffineTransformConcat(CGAffineTransformMakeScale(1.0, -1.0),
					    CGAffineTransformMakeTranslation(0, cellSize.height));
		Path* b = [[Path new] autorelease];
		p = CGPathCreateMutable();
		CGPathAddLines(p, &m, points, 4);
		b.path = p;
		b.color = [UIColor colorWithWhite:.2 alpha:1.0];
		b.drawMode = kCGPathFill;
		CGPathRelease(p);
		// Left
		m = CGAffineTransformConcat(CGAffineTransformMakeRotation(M_PI/2),
					    CGAffineTransformMakeScale(-1.0, 1.0));
		Path* l = [[Path new] autorelease];
		p = CGPathCreateMutable();
		CGPathAddLines(p, &m, points, 4);
		l.path = p;
		l.color = [UIColor colorWithWhite:.6 alpha:1.0];
		l.drawMode = kCGPathFill;
		CGPathRelease(p);
		// Right
		m = CGAffineTransformConcat(CGAffineTransformMakeRotation(M_PI/2),
					    CGAffineTransformMakeTranslation(cellSize.width, 0));
		Path* r = [[Path new] autorelease];
		p = CGPathCreateMutable();
		CGPathAddLines(p, &m, points, 4);
		r.path = p;
		r.color = [UIColor colorWithWhite:.1 alpha:1.0];
		r.drawMode = kCGPathFill;
		CGPathRelease(p);
		
		box = [[NSArray alloc] initWithObjects:t,b,l,r,nil];
	}
	return box;
}

Rotation

If you look very, very closely at the box code, you'll notice something odd. The left and right edges of the box are derived from a 90 degree clockwise rotation of the top edge. However, the angle passed to CGAffineTransformMakeRotation() is positive. This is an apparent contradiction of the documentation, which states: "In iPhone OS, a positive value specifies counterclockwise rotation …".

The resolution of this conflict lies, again, with the two co-ordinate systems on the iPhone, and the framework's attempts to convert between them. To convert from an UL to a BL convention, you need to invert the Y-axis. Such an inversion changes the direction of rotations: CCW becomes CW, and vice-versa. So, the documentation is correct: On the iPhone, a positive angle does specify a CCW rotation. However, that rotation is (ultimately) being prepended to another transform which inverts the Y-axis, which changes the perceived direction of rotation.

Performance

The performance of this code is not so good. It usually takes 0.1s to 0.2s to render a tile on the device, which in the normal run of things would be not too bad. Unfortunately, this delay happens on the same thread that's handling scrolling, and it causes horrendous stutter. In order to get a sense of how much we'd need to speed things up, I conducted a simple "acceleration" experiment in which I skipped more and more rendering until performance became reasonable. I found that even at .03s/tile, the interface still seemed jerky and lame. I don't think it's worth trying to find a 10x speedup in this code in order to get sort-of-acceptable performance; we'll have to try another tactic.

We could change approaches yet again, and move to OpenGL. I want to try something else: Pre-calculated and multi-threaded rendering. On Thursday, I'll have an update on how that's going.

Share and Enjoy:
  • Twitter
  • Facebook
  • Digg
  • Reddit
  • HackerNews
  • del.icio.us
  • Google Bookmarks
  • Slashdot
This entry was posted in iPhone, Projects. Bookmark the permalink.

Comments are closed.