Today we bring our Minesweeper project almost to the point of completion. The latest version (you can download the Xcode project here) adds puzzle setup, high-score tracking, and auto-clear, along with an assortment of odds and ends needed to get the code ready for release.
Auto-Clear
I implemented auto-clear in this release. This conceptually simple feature turned out to be a little problematic, because my design permits puzzles up to 500×500 cells. When I ran my first (recursive) auto-clear algorithm on the device, against a 500×500/10000 puzzle, I noticed two problems:
- The algorithm ran very slowly
- The algorithm crashed after ~8000 recursions
(Full disclosure: I think it was ~8,000, but didn’t look carefully. It might have been ~80,000. Whatever it was, it was too many.)
Clearly, recursion was a non-starter. I recoded the algorithm to run iteratively. This solved the crashing problem, but performance was still disappointing on the device. I embarked on a tuning program, and eventually reduced the auto-clear run-time on my 500×500/10000 testcase (which cleared ~245K cells) from 6.1s to .24s: a 25x improvement, and just-about-acceptable final performance. That’ll teach me to allow ridiculously large input values.
Here’s the core code for the auto-clear algorithm. It’s got a fair bit of cutesy stuff in it: E.g., I avoid all references to object members in the inner loop, I rely on unsigned int wrapping to detect “negative” numbers, I pack x,y pairs into 32-bit ints, and so on. I don’t normally like this stuff, but it was necessary to get the inner loop down to a reasonable time.
- (NSData*)revealCascadeAt:(CGPoint)pos withCellBox:(CGRect)cellBox
{
NSMutableData* rv = [NSMutableData data];
unsigned int myW = w;
unsigned int myH = h;
int myUncovered = nUncovered;
char* myCells = self.cells;
unsigned int minX = cellBox.origin.x;
unsigned int minY = cellBox.origin.y;
unsigned int maxX = cellBox.origin.x + cellBox.size.width;
unsigned int maxY = cellBox.origin.y + cellBox.size.height;
NSInteger ql = 1;
unsigned int* q = (unsigned int*) malloc(w*h*sizeof(unsigned int));
q[0] = (((unsigned int) pos.y) << 16) | ((unsigned int) pos.x);
unsigned int offsets[8][2] = {-1, -1, -1, +0, -1, +1, +0, -1, +0, +1, +1, -1, +1, +0, +1, +1};
for (NSInteger i = 0; i < ql; i++)
{
unsigned int ox = q[i]&0xffff;
unsigned int oy = q[i]>>16;
for (int j = 0; j < 8; j++)
{
unsigned int x = ox + offsets[j][1];
unsigned int y = oy + offsets[j][0];
unsigned int n = myW*y+x;
if ((x >= myW) || (y >= myH) || (myCells[n] & (BIT_REVEALED|BIT_FLAGGED)))
{
continue;
}
myCells[n] |= BIT_REVEALED;
myUncovered++;
if ((x >= minX) && (x < maxX) && (y >= minY) && (y < maxY))
{
pos = CGPointMake(x, y);
[rv appendBytes:&pos length:sizeof(CGPoint)];
}
if ((myCells[n]&NEIGHBOR_MASK) == 0)
{
q[ql++] = (y<<16)|x;
}
}
}
free(q);
nUncovered = myUncovered;
return rv;
}
Please note that the NSData appendBytes:length: method might be called 30 – 40 times over the course of more than a million iterations through the inner loop; for all practical purposes it doesn’t participate, which is why it hasn’t been optimized out. As for what that particular code does: It keeps track of which visible cells were cleared by the process, so I know which ones to re-draw. (Upon reflection, it might have made more sense to ditch this idea, and just redraw the entire screen whenever I performed an auto-clear cascade. Ah well.)
Puzzle Setup
The second major feature I added was puzzle setup; the user can now actually specify what puzzle size he wants to solve. (Bonus feature: I made the puzzles properly random by replacing rand() with arc4random().) Puzzle setup was pretty straightforward – my Shiny Red Buttons came in handy once again – but there was one frustrating snag: The iPhone’s numeric keyboard doesn’t have an enter key.
Without getting into the details, the no-enter-key thing scuppered my plans to build a one-screen puzzle-creation interface. I ended up splitting the task across two screens: One just presents the user with 4 options (“Beginner”, “Intermediate”, “Expert”, and “Custom”), while the second is devoted to the input of custom parameters.
Incidentally, if you want to hack an enter key (or done key, or equivalent) into the keypad, this article explains how to do it. It’s a neat trick, but not an idea I have too much enthusiasm for; that sort of thing can become a real nuisance to keep updated and working properly across different versions of the OS.
High Scores
I created a new Entity to track high scores. 
The only bit of lily-gilding I engaged in was to add a key field, enabling one-field, indexed lookup of high scores. This was unnecessary; there will be very few high score records in practice, and a table scan for a three-term predicate would cause no perceptible delay. Still, there it is.
High scores are set in the willSave method of ManagedPuzzles:
- (void)willSave
{
// Don't bother unless we've won
if ([self.status integerValue] != PuzzleStatusSolved) return;
// This puzzle's HS key
NSString* key = [NSString stringWithFormat:@"%@.%@.%@",self.w,self.h,self.nMines];
// Find the HS record (if any) for this key
NSError* err;
NSFetchRequest* request = [[NSFetchRequest alloc] init];
request.entity = [NSEntityDescription entityForName:@"HighScore" inManagedObjectContext:self.managedObjectContext];
request.predicate = [NSPredicate predicateWithFormat:@"key = %@",key];
NSArray* highScores = [self.managedObjectContext executeFetchRequest:request error:&err];
[request release];
// Get a HS record
HighScore* hs;
if ([highScores count])
{
hs = [highScores objectAtIndex:0];
if ([self.elapsedTime doubleValue] < [hs.best doubleValue])
{
hs.best = self.elapsedTime;
}
}
else
{
hs = [NSEntityDescription insertNewObjectForEntityForName:@"HighScore" inManagedObjectContext:self.managedObjectContext];
hs.width = self.w;
hs.height = self.h;
hs.mines = self.nMines;
hs.key = key;
hs.best = self.elapsedTime;
}
}Last minute addenda: I really should call [super willSave] in this method. I don’t want to re-do the downloadable code, or get the post and code out of sync, so I’ll just note that here for now.
High score display is driven by a simple subclass of UITableViewController. This subclass is much like that provided by Xcode’s Navigation-based Application project template (when you opt to use Core Data for storage).
To Do
I think there’s only one bit of code to add before release: in-app purchases. Of course, we’ll need to pull together a logo, do screenshots, and write ad copy – and those things are not to be overlooked – but purchases look to be the last thing to develop. I hope to have a post written on that topic for Friday; in any event, I’ll let you know how it’s going.
