Minesweeper (Part 1)

Let’s do a multi-day project: Let’s build Minesweeper for the iPhone. This should be pretty straight-forward, especially if we cut out a bell or whistle here and there. Let’s get started with some data structures.

Quick Design

As we move forward, we’ll need to make design choices specific to our platform, but for now we can simply take the Windows version of Minesweeper as a reference. This is sufficient to design our puzzle data structure.

Our app will allow the player to create, play, and review any number of minesweeper puzzles. A puzzle is defined by these data:

• Dimensions (width and height)
• Mine count and position
• Position of uncovered squares

Simplicity

After a fair bit of mucking about with object models, I decided to model a puzzle (largely) with a simple array of bytes. The coding is pretty simple:

• The cell at (x,y) is represented by a byte at offset width*y+x
• Bits 0-3 store the number of mines neighboring the cell (0-8)
• Bit 4 is set iff the cell is mined
• Bit 5 is set iff the cell has been revealed

The rationale behind the choice of a byte array is that if we hold puzzle density fixed, the relationship between the memory use of a dense representation and a sparse representation will be a constant factor for any puzzle size. Since puzzle density is likely to remain relatively constant (due to playability considerations), and since the memory use of a dense representation compares favorably to that of a sparse representation at the 15%-20% densities we’re likely to see in practice, there’s no real advantage to a sparse representation. And a dense representation is much easier to work with.

Code

If you’d like to see them, you can download the complete Puzzle header and implementation files.

The class declaration is pretty simple:

@interface Puzzle : NSObject
{
	NSUInteger		w;
	NSUInteger		h;
	NSUInteger		m;
	
	char*			cells;
}

@property (nonatomic, assign, readonly) NSUInteger w;
@property (nonatomic, assign, readonly) NSUInteger h;
@property (nonatomic, assign, readonly) NSUInteger m;

- (id)initWithWidth:(NSUInteger)w height:(NSUInteger)h mines:(NSUInteger)m;

- (void)generate;
- (BOOL)isMinedAtX:(NSUInteger)x andY:(NSUInteger)y;
- (NSUInteger)neighborsAtX:(NSUInteger)x andY:(NSUInteger)y;

@end

In the implementation file, we begin with some constants:

const static NSUInteger MAX_EDGE_SIZE	= 500;
const static char BIT_REVEALED		= (1<<5);
const static char BIT_MINED		= (1<<4);
const static char NEIGHBOR_MASK		= 0xf;

We then add some helper functions:

static inline char get_record(char* d, int w, int h, int x, int y)
{
	return ((x>=0)&&(x<w)&&(y>=0)&&(y<h))?d[w*y+x]:0;
}

static inline char is_mined(char* d, int w, int h, int x, int y)
{
	return (get_record(d, w, h, x, y)&BIT_MINED)?1:0;
}

We define a lazy getter for our internal data storage:

- (char*)cells
{
	if (!cells)
	{
		cells = (char*) malloc(w*h);
	}
	return cells;
}

and methods for initialization:

- (id)initWithWidth:(NSUInteger)iw height:(NSUInteger)ih mines:(NSUInteger)im
{
	if (self = [super init])
	{
		w = MIN(MAX(iw, 2), MAX_EDGE_SIZE);
		h = MIN(MAX(ih, 2), MAX_EDGE_SIZE);
		m = MIN(im, (w-1)*(h-1));
	}
	return self;
}

… debugging:

- (NSString*)description
{
	char symbols[2*w+1];
	memset(symbols, ' ', 2*w+1);
	symbols[0] = '\n';
	symbols[2*w] = '\0';
	NSMutableArray* a = [NSMutableArray arrayWithCapacity:h];

	char* d = self.cells;
	for (int y = 0; y < h; y++)
	{
		for (int x = 0; x < w; x++)
		{
			char cell = d[w*y+x];
			symbols[2*x+1] = (cell&BIT_MINED)?'X':('0'+(cell&NEIGHBOR_MASK));
		}
		[a addObject:[NSString stringWithCString:symbols encoding:NSASCIIStringEncoding]];
	}
	return [a componentsJoinedByString:@""];
}

… puzzle generation:

- (void)generate
{
	char* d = self.cells;
	int size = w*h;
	
	// To keep things reasonable, add or remove cells depending on density
	if (m > size/2)
	{
		// More than 50% mined: remove mines
		memset(d, BIT_MINED, size);
		for (int nmines=size; nmines>m;)
		{
			int idx = rand()%size;
			if (d[idx] & BIT_MINED)
			{
				nmines--;
				d[idx] &= ~BIT_MINED;
			}
		}
	}
	else
	{
		// Less than 50% mined: add mines
		memset(d, 0, size);
		for (int nmines=0; nmines<m;)
		{
			int idx = rand()%size;
			if (!(d[idx] & BIT_MINED))
			{
				nmines++;
				d[idx] |= BIT_MINED;
			}
		}
	}
	
	// Calculate neighbors
	for (int x = w-1; x >= 0; x--)
	{
		for (int y = h-1; y >= 0; y--)
		{
			d[w*y+x] |= (is_mined(d,w,h,x-1,y-1) +
				     is_mined(d,w,h,x+0,y-1) +
				     is_mined(d,w,h,x+1,y-1) +
				     is_mined(d,w,h,x-1,y+0) +
				     is_mined(d,w,h,x+1,y+0) +
				     is_mined(d,w,h,x-1,y+1) +
				     is_mined(d,w,h,x+0,y+1) +
				     is_mined(d,w,h,x+1,y+1) );
		}
	}
}

… and a public interface:

- (BOOL)isMinedAtX:(NSUInteger)x andY:(NSUInteger)y
{
	return is_mined(self.cells, w, h, x, y);
}


- (NSUInteger)neighborsAtX:(NSUInteger)x andY:(NSUInteger)y
{
	return get_record(self.cells, w, h, x, y)&NEIGHBOR_MASK;
}

Finally, I clean up:

- (void)dealloc
{
	if (cells) free(cells);
	[super dealloc];
}