# 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 = '\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];
}
}
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];
}``````
This entry was posted in iPhone, Projects. Bookmark the permalink.

### One Response to Minesweeper (Part 1)

1. Jordan says:

Wow! I like the concept and all of the bit math. Needed to study it a while. Great stuff, looking forward to reading the next two articles.