* mines.c: Minesweeper clone with sophisticated grid generation.
*
* Still TODO:
- *
- * - possibly disable undo? Or alternatively mark game states as
- * `cheated', although that's horrid.
- * + OK. Rather than _disabling_ undo, we have a hook callable
- * in the game backend which is called before we do an undo.
- * That hook can talk to the game_ui and set the cheated flag,
- * and then make_move can avoid setting the `won' flag after that.
*
- * - delay game description generation until first click
- * + do we actually _need_ to do this? Hmm.
- * + it's a perfectly good puzzle game without
- * + but it might be useful when we start timing, since it
- * ensures the user is really paying attention.
- *
- * - timer
- *
- * - question marks (arrgh, preferences?)
- *
- * - sensible parameter constraints
- * + 30x16: 191 mines just about works if rather slowly, 192 is
- * just about doom (the latter corresponding to a density of
- * exactly 1 in 2.5)
- * + 9x9: 45 mines works - over 1 in 2! 50 seems a bit slow.
- * + it might not be feasible to work out the exact limit
+ * - think about configurably supporting question marks. Once,
+ * that is, we've thought about configurability in general!
*/
#include <stdio.h>
#include "puzzles.h"
enum {
- COL_BACKGROUND,
+ COL_BACKGROUND, COL_BACKGROUND2,
COL_1, COL_2, COL_3, COL_4, COL_5, COL_6, COL_7, COL_8,
COL_MINE, COL_BANG, COL_CROSS, COL_FLAG, COL_FLAGBASE, COL_QUERY,
COL_HIGHLIGHT, COL_LOWLIGHT,
int unique;
};
+struct mine_layout {
+ /*
+ * This structure is shared between all the game_states for a
+ * given instance of the puzzle, so we reference-count it.
+ */
+ int refcount;
+ char *mines;
+ /*
+ * If we haven't yet actually generated the mine layout, here's
+ * all the data we will need to do so.
+ */
+ int n, unique;
+ random_state *rs;
+ midend_data *me; /* to give back the new game desc */
+};
+
struct game_state {
int w, h, n, dead, won;
- char *mines; /* real mine positions */
- char *grid; /* player knowledge */
+ int used_solve, just_used_solve;
+ struct mine_layout *layout; /* real mine positions */
+ signed char *grid; /* player knowledge */
/*
* Each item in the `grid' array is one of the following values:
*
ret->w = atoi(cfg[0].sval);
ret->h = atoi(cfg[1].sval);
ret->n = atoi(cfg[2].sval);
+ if (strchr(cfg[2].sval, '%'))
+ ret->n = ret->n * (ret->w * ret->h) / 100;
ret->unique = cfg[3].ival;
return ret;
return "Width must be greater than zero";
if (params->h <= 0)
return "Height must be greater than zero";
+ if (params->n > params->w * params->h - 9)
+ return "Too many mines for grid size";
/*
* FIXME: Need more constraints here. Not sure what the
std->next[i] = -1;
}
-static void known_squares(int w, int h, struct squaretodo *std, char *grid,
+static void known_squares(int w, int h, struct squaretodo *std,
+ signed char *grid,
int (*open)(void *ctx, int x, int y), void *openctx,
int x, int y, int mask, int mine)
{
* steps were required; the exact return value is the number of
* perturb calls.
*/
-static int minesolve(int w, int h, int n, char *grid,
+static int minesolve(int w, int h, int n, signed char *grid,
int (*open)(void *ctx, int x, int y),
- struct perturbations *(*perturb)(void *ctx, char *grid,
+ struct perturbations *(*perturb)(void *ctx,
+ signed char *grid,
int x, int y, int mask),
void *ctx, random_state *rs)
{
* next. Backtrack cursor to the nearest 1,
* change it to a 0 and continue.
*/
- while (cursor-- >= 0 && !setused[cursor]);
+ while (--cursor >= 0 && !setused[cursor]);
if (cursor >= 0) {
assert(setused[cursor]);
*
* If we have no sets at all, we must give up.
*/
- if (count234(ss->sets) == 0)
- break;
- s = index234(ss->sets, random_upto(rs, count234(ss->sets)));
+ if (count234(ss->sets) == 0) {
+#ifdef SOLVER_DIAGNOSTICS
+ printf("perturbing on entire unknown set\n");
+#endif
+ ret = perturb(ctx, grid, 0, 0, 0);
+ } else {
+ s = index234(ss->sets, random_upto(rs, count234(ss->sets)));
#ifdef SOLVER_DIAGNOSTICS
- printf("perturbing on set %d,%d %03x\n", s->x, s->y, s->mask);
+ printf("perturbing on set %d,%d %03x\n", s->x, s->y, s->mask);
#endif
- ret = perturb(ctx, grid, s->x, s->y, s->mask);
+ ret = perturb(ctx, grid, s->x, s->y, s->mask);
+ }
if (ret) {
assert(ret->n > 0); /* otherwise should have been NULL */
* the returned structure tells us which. Adjust
* the mine count in any set which overlaps one of
* those squares, and put them back on the to-do
+ * list. Also, if the square itself is marked as a
+ * known non-mine, put it back on the squares-to-do
* list.
*/
for (i = 0; i < ret->n; i++) {
ret->changes[i].x, ret->changes[i].y);
#endif
+ if (ret->changes[i].delta < 0 &&
+ grid[ret->changes[i].y*w+ret->changes[i].x] != -2) {
+ std_add(std, ret->changes[i].y*w+ret->changes[i].x);
+ }
+
list = ss_overlap(ss,
ret->changes[i].x, ret->changes[i].y, 1);
/*
* Dump the current known state of the grid.
*/
- printf("state after perturbation:\n", nperturbs);
+ printf("state after perturbation:\n");
for (y = 0; y < h; y++) {
for (x = 0; x < w; x++) {
int v = grid[y*w+x];
*/
struct minectx {
- char *grid;
+ signed char *grid;
int w, h;
int sx, sy;
+ int allow_big_perturbs;
random_state *rs;
};
return 0;
}
-static struct perturbations *mineperturb(void *vctx, char *grid,
+/*
+ * Normally this function is passed an (x,y,mask) set description.
+ * On occasions, though, there is no _localised_ set being used,
+ * and the set being perturbed is supposed to be the entirety of
+ * the unreachable area. This is signified by the special case
+ * mask==0: in this case, anything labelled -2 in the grid is part
+ * of the set.
+ *
+ * Allowing perturbation in this special case appears to make it
+ * guaranteeably possible to generate a workable grid for any mine
+ * density, but they tend to be a bit boring, with mines packed
+ * densely into far corners of the grid and the remainder being
+ * less dense than one might like. Therefore, to improve overall
+ * grid quality I disable this feature for the first few attempts,
+ * and fall back to it after no useful grid has been generated.
+ */
+static struct perturbations *mineperturb(void *vctx, signed char *grid,
int setx, int sety, int mask)
{
struct minectx *ctx = (struct minectx *)vctx;
struct square *sqlist;
int x, y, dx, dy, i, n, nfull, nempty;
- struct square *tofill[9], *toempty[9], **todo;
+ struct square **tofill, **toempty, **todo;
int ntofill, ntoempty, ntodo, dtodo, dset;
struct perturbations *ret;
+ int *setlist;
+
+ if (!mask && !ctx->allow_big_perturbs)
+ return NULL;
/*
* Make a list of all the squares in the grid which we can
* If this square is in the input set, also don't put
* it on the list!
*/
- if (x >= setx && x < setx + 3 &&
- y >= sety && y < sety + 3 &&
- mask & (1 << ((y-sety)*3+(x-setx))))
+ if ((mask == 0 && grid[y*ctx->w+x] == -2) ||
+ (x >= setx && x < setx + 3 &&
+ y >= sety && y < sety + 3 &&
+ mask & (1 << ((y-sety)*3+(x-setx)))))
continue;
sqlist[n].x = x;
* we've been provided.
*/
nfull = nempty = 0;
- for (dy = 0; dy < 3; dy++)
- for (dx = 0; dx < 3; dx++)
- if (mask & (1 << (dy*3+dx))) {
- assert(setx+dx <= ctx->w);
- assert(sety+dy <= ctx->h);
- if (ctx->grid[(sety+dy)*ctx->w+(setx+dx)])
- nfull++;
- else
- nempty++;
- }
+ if (mask) {
+ for (dy = 0; dy < 3; dy++)
+ for (dx = 0; dx < 3; dx++)
+ if (mask & (1 << (dy*3+dx))) {
+ assert(setx+dx <= ctx->w);
+ assert(sety+dy <= ctx->h);
+ if (ctx->grid[(sety+dy)*ctx->w+(setx+dx)])
+ nfull++;
+ else
+ nempty++;
+ }
+ } else {
+ for (y = 0; y < ctx->h; y++)
+ for (x = 0; x < ctx->w; x++)
+ if (grid[y*ctx->w+x] == -2) {
+ if (ctx->grid[y*ctx->w+x])
+ nfull++;
+ else
+ nempty++;
+ }
+ }
/*
* Now go through our sorted list until we find either `nfull'
* overall.
*/
ntofill = ntoempty = 0;
+ if (mask) {
+ tofill = snewn(9, struct square *);
+ toempty = snewn(9, struct square *);
+ } else {
+ tofill = snewn(ctx->w * ctx->h, struct square *);
+ toempty = snewn(ctx->w * ctx->h, struct square *);
+ }
for (i = 0; i < n; i++) {
struct square *sq = &sqlist[i];
if (ctx->grid[sq->y * ctx->w + sq->x])
}
/*
- * If this didn't work at all, I think we just give up.
+ * If we haven't found enough empty squares outside the set to
+ * empty it into _or_ enough full squares outside it to fill it
+ * up with, we'll have to settle for doing only a partial job.
+ * In this case we choose to always _fill_ the set (because
+ * this case will tend to crop up when we're working with very
+ * high mine densities and the only way to get a solvable grid
+ * is going to be to pack most of the mines solidly around the
+ * edges). So now our job is to make a list of the empty
+ * squares in the set, and shuffle that list so that we fill a
+ * random selection of them.
*/
if (ntofill != nfull && ntoempty != nempty) {
- sfree(sqlist);
- return NULL;
- }
+ int k;
+
+ assert(ntoempty != 0);
+
+ setlist = snewn(ctx->w * ctx->h, int);
+ i = 0;
+ if (mask) {
+ for (dy = 0; dy < 3; dy++)
+ for (dx = 0; dx < 3; dx++)
+ if (mask & (1 << (dy*3+dx))) {
+ assert(setx+dx <= ctx->w);
+ assert(sety+dy <= ctx->h);
+ if (!ctx->grid[(sety+dy)*ctx->w+(setx+dx)])
+ setlist[i++] = (sety+dy)*ctx->w+(setx+dx);
+ }
+ } else {
+ for (y = 0; y < ctx->h; y++)
+ for (x = 0; x < ctx->w; x++)
+ if (grid[y*ctx->w+x] == -2) {
+ if (!ctx->grid[y*ctx->w+x])
+ setlist[i++] = y*ctx->w+x;
+ }
+ }
+ assert(i > ntoempty);
+ /*
+ * Now pick `ntoempty' items at random from the list.
+ */
+ for (k = 0; k < ntoempty; k++) {
+ int index = k + random_upto(ctx->rs, i - k);
+ int tmp;
+
+ tmp = setlist[k];
+ setlist[k] = setlist[index];
+ setlist[index] = tmp;
+ }
+ } else
+ setlist = NULL;
/*
* Now we're pretty much there. We need to either
ntodo = ntofill;
dtodo = +1;
dset = -1;
+ sfree(toempty);
} else {
+ /*
+ * (We also fall into this case if we've constructed a
+ * setlist.)
+ */
todo = toempty;
ntodo = ntoempty;
dtodo = -1;
dset = +1;
+ sfree(tofill);
}
ret->n = 2 * ntodo;
ret->changes = snewn(ret->n, struct perturbation);
ret->changes[i].delta = dtodo;
}
/* now i == ntodo */
- for (dy = 0; dy < 3; dy++)
- for (dx = 0; dx < 3; dx++)
- if (mask & (1 << (dy*3+dx))) {
- int currval = (ctx->grid[(sety+dy)*ctx->w+(setx+dx)] ? +1 : -1);
- if (dset == -currval) {
- ret->changes[i].x = setx + dx;
- ret->changes[i].y = sety + dy;
- ret->changes[i].delta = dset;
- i++;
+ if (setlist) {
+ int j;
+ assert(todo == toempty);
+ for (j = 0; j < ntoempty; j++) {
+ ret->changes[i].x = setlist[j] % ctx->w;
+ ret->changes[i].y = setlist[j] / ctx->w;
+ ret->changes[i].delta = dset;
+ i++;
+ }
+ sfree(setlist);
+ } else if (mask) {
+ for (dy = 0; dy < 3; dy++)
+ for (dx = 0; dx < 3; dx++)
+ if (mask & (1 << (dy*3+dx))) {
+ int currval = (ctx->grid[(sety+dy)*ctx->w+(setx+dx)] ? +1 : -1);
+ if (dset == -currval) {
+ ret->changes[i].x = setx + dx;
+ ret->changes[i].y = sety + dy;
+ ret->changes[i].delta = dset;
+ i++;
+ }
}
- }
+ } else {
+ for (y = 0; y < ctx->h; y++)
+ for (x = 0; x < ctx->w; x++)
+ if (grid[y*ctx->w+x] == -2) {
+ int currval = (ctx->grid[y*ctx->w+x] ? +1 : -1);
+ if (dset == -currval) {
+ ret->changes[i].x = x;
+ ret->changes[i].y = y;
+ ret->changes[i].delta = dset;
+ i++;
+ }
+ }
+ }
assert(i == ret->n);
sfree(sqlist);
+ sfree(todo);
/*
* Having set up the precise list of changes we're going to
{
char *ret = snewn(w*h, char);
int success;
+ int ntries = 0;
do {
success = FALSE;
+ ntries++;
memset(ret, 0, w*h);
* We bypass this bit if we're not after a unique grid.
*/
if (unique) {
- char *solvegrid = snewn(w*h, char);
+ signed char *solvegrid = snewn(w*h, char);
struct minectx actx, *ctx = &actx;
int solveret, prevret = -2;
ctx->sx = x;
ctx->sy = y;
ctx->rs = rs;
+ ctx->allow_big_perturbs = (ntries > 100);
while (1) {
memset(solvegrid, -2, w*h);
SHA_Final(&final, digest);
digestpos = 0;
}
- steps[i].targetstart[j] ^= digest[digestpos]++;
+ steps[i].targetstart[j] ^= digest[digestpos++];
}
/*
}
}
-static char *new_game_desc(game_params *params, random_state *rs,
- game_aux_info **aux)
+static char *new_mine_layout(int w, int h, int n, int x, int y, int unique,
+ random_state *rs, char **game_desc)
{
- char *grid, *ret, *p;
+ signed char *grid, *ret, *p;
unsigned char *bmp;
- int x, y, i, area;
+ int i, area;
- /*
- * FIXME: allow user to specify initial open square.
- */
- x = random_upto(rs, params->w);
- y = random_upto(rs, params->h);
+#ifdef TEST_OBFUSCATION
+ static int tested_obfuscation = FALSE;
+ if (!tested_obfuscation) {
+ /*
+ * A few simple test vectors for the obfuscator.
+ *
+ * First test: the 28-bit stream 1234567. This divides up
+ * into 1234 and 567[0]. The SHA of 56 70 30 (appending
+ * "0") is 15ce8ab946640340bbb99f3f48fd2c45d1a31d30. Thus,
+ * we XOR the 16-bit string 15CE into the input 1234 to get
+ * 07FA. Next, we SHA that with "0": the SHA of 07 FA 30 is
+ * 3370135c5e3da4fed937adc004a79533962b6391. So we XOR the
+ * 12-bit string 337 into the input 567 to get 650. Thus
+ * our output is 07FA650.
+ */
+ {
+ unsigned char bmp1[] = "\x12\x34\x56\x70";
+ obfuscate_bitmap(bmp1, 28, FALSE);
+ printf("test 1 encode: %s\n",
+ memcmp(bmp1, "\x07\xfa\x65\x00", 4) ? "failed" : "passed");
+ obfuscate_bitmap(bmp1, 28, TRUE);
+ printf("test 1 decode: %s\n",
+ memcmp(bmp1, "\x12\x34\x56\x70", 4) ? "failed" : "passed");
+ }
+ /*
+ * Second test: a long string to make sure we switch from
+ * one SHA to the next correctly. My input string this time
+ * is simply fifty bytes of zeroes.
+ */
+ {
+ unsigned char bmp2[50];
+ unsigned char bmp2a[50];
+ memset(bmp2, 0, 50);
+ memset(bmp2a, 0, 50);
+ obfuscate_bitmap(bmp2, 50 * 8, FALSE);
+ /*
+ * SHA of twenty-five zero bytes plus "0" is
+ * b202c07b990c01f6ff2d544707f60e506019b671. SHA of
+ * twenty-five zero bytes plus "1" is
+ * fcb1d8b5a2f6b592fe6780b36aa9d65dd7aa6db9. Thus our
+ * first half becomes
+ * b202c07b990c01f6ff2d544707f60e506019b671fcb1d8b5a2.
+ *
+ * SHA of that lot plus "0" is
+ * 10b0af913db85d37ca27f52a9f78bba3a80030db. SHA of the
+ * same string plus "1" is
+ * 3d01d8df78e76d382b8106f480135a1bc751d725. So the
+ * second half becomes
+ * 10b0af913db85d37ca27f52a9f78bba3a80030db3d01d8df78.
+ */
+ printf("test 2 encode: %s\n",
+ memcmp(bmp2, "\xb2\x02\xc0\x7b\x99\x0c\x01\xf6\xff\x2d\x54"
+ "\x47\x07\xf6\x0e\x50\x60\x19\xb6\x71\xfc\xb1\xd8"
+ "\xb5\xa2\x10\xb0\xaf\x91\x3d\xb8\x5d\x37\xca\x27"
+ "\xf5\x2a\x9f\x78\xbb\xa3\xa8\x00\x30\xdb\x3d\x01"
+ "\xd8\xdf\x78", 50) ? "failed" : "passed");
+ obfuscate_bitmap(bmp2, 50 * 8, TRUE);
+ printf("test 2 decode: %s\n",
+ memcmp(bmp2, bmp2a, 50) ? "failed" : "passed");
+ }
+ }
+#endif
- grid = minegen(params->w, params->h, params->n, x, y, params->unique, rs);
+ grid = minegen(w, h, n, x, y, unique, rs);
- /*
- * Set up the mine bitmap and obfuscate it.
- */
- area = params->w * params->h;
- bmp = snewn((area + 7) / 8, unsigned char);
- memset(bmp, 0, (area + 7) / 8);
- for (i = 0; i < area; i++) {
- if (grid[i])
- bmp[i / 8] |= 0x80 >> (i % 8);
- }
- obfuscate_bitmap(bmp, area, FALSE);
+ if (game_desc) {
+ /*
+ * Set up the mine bitmap and obfuscate it.
+ */
+ area = w * h;
+ bmp = snewn((area + 7) / 8, unsigned char);
+ memset(bmp, 0, (area + 7) / 8);
+ for (i = 0; i < area; i++) {
+ if (grid[i])
+ bmp[i / 8] |= 0x80 >> (i % 8);
+ }
+ obfuscate_bitmap(bmp, area, FALSE);
- /*
- * Now encode the resulting bitmap in hex. We can work to
- * nibble rather than byte granularity, since the obfuscation
- * function guarantees to return a bit string of the same
- * length as its input.
- */
- ret = snewn((area+3)/4 + 100, char);
- p = ret + sprintf(ret, "%d,%d,m", x, y); /* 'm' == masked */
- for (i = 0; i < (area+3)/4; i++) {
- int v = bmp[i/2];
- if (i % 2 == 0)
- v >>= 4;
- *p++ = "0123456789abcdef"[v & 0xF];
- }
- *p = '\0';
+ /*
+ * Now encode the resulting bitmap in hex. We can work to
+ * nibble rather than byte granularity, since the obfuscation
+ * function guarantees to return a bit string of the same
+ * length as its input.
+ */
+ ret = snewn((area+3)/4 + 100, char);
+ p = ret + sprintf(ret, "%d,%d,m", x, y); /* 'm' == masked */
+ for (i = 0; i < (area+3)/4; i++) {
+ int v = bmp[i/2];
+ if (i % 2 == 0)
+ v >>= 4;
+ *p++ = "0123456789abcdef"[v & 0xF];
+ }
+ *p = '\0';
- sfree(bmp);
+ sfree(bmp);
- return ret;
+ *game_desc = ret;
+ }
+
+ return grid;
+}
+
+static char *new_game_desc(game_params *params, random_state *rs,
+ game_aux_info **aux, int interactive)
+{
+ if (!interactive) {
+ /*
+ * For batch-generated grids, pre-open one square.
+ */
+ int x = random_upto(rs, params->w);
+ int y = random_upto(rs, params->h);
+ signed char *grid;
+ char *desc;
+
+ grid = new_mine_layout(params->w, params->h, params->n,
+ x, y, params->unique, rs, &desc);
+ sfree(grid);
+ return desc;
+ } else {
+ char *rsdesc, *desc;
+
+ rsdesc = random_state_encode(rs);
+ desc = snewn(strlen(rsdesc) + 100, char);
+ sprintf(desc, "r%d,%c,%s", params->n, params->unique ? 'u' : 'a', rsdesc);
+ sfree(rsdesc);
+ return desc;
+ }
}
static void game_free_aux_info(game_aux_info *aux)
int wh = params->w * params->h;
int x, y;
- if (!*desc || !isdigit((unsigned char)*desc))
- return "No initial x-coordinate in game description";
- x = atoi(desc);
- if (x < 0 || x >= params->w)
- return "Initial x-coordinate was out of range";
- while (*desc && isdigit((unsigned char)*desc))
- desc++; /* skip over x coordinate */
- if (*desc != ',')
- return "No ',' after initial x-coordinate in game description";
- desc++; /* eat comma */
- if (!*desc || !isdigit((unsigned char)*desc))
- return "No initial y-coordinate in game description";
- y = atoi(desc);
- if (y < 0 || y >= params->h)
- return "Initial y-coordinate was out of range";
- while (*desc && isdigit((unsigned char)*desc))
- desc++; /* skip over y coordinate */
- if (*desc != ',')
- return "No ',' after initial y-coordinate in game description";
- desc++; /* eat comma */
- /* eat `m', meaning `masked', if present */
- if (*desc == 'm')
+ if (*desc == 'r') {
+ if (!*desc || !isdigit((unsigned char)*desc))
+ return "No initial mine count in game description";
+ while (*desc && isdigit((unsigned char)*desc))
+ desc++; /* skip over mine count */
+ if (*desc != ',')
+ return "No ',' after initial x-coordinate in game description";
desc++;
- /* now just check length of remainder */
- if (strlen(desc) != (wh+3)/4)
- return "Game description is wrong length";
+ if (*desc != 'u' && *desc != 'a')
+ return "No uniqueness specifier in game description";
+ desc++;
+ if (*desc != ',')
+ return "No ',' after uniqueness specifier in game description";
+ /* now ignore the rest */
+ } else {
+ if (!*desc || !isdigit((unsigned char)*desc))
+ return "No initial x-coordinate in game description";
+ x = atoi(desc);
+ if (x < 0 || x >= params->w)
+ return "Initial x-coordinate was out of range";
+ while (*desc && isdigit((unsigned char)*desc))
+ desc++; /* skip over x coordinate */
+ if (*desc != ',')
+ return "No ',' after initial x-coordinate in game description";
+ desc++; /* eat comma */
+ if (!*desc || !isdigit((unsigned char)*desc))
+ return "No initial y-coordinate in game description";
+ y = atoi(desc);
+ if (y < 0 || y >= params->h)
+ return "Initial y-coordinate was out of range";
+ while (*desc && isdigit((unsigned char)*desc))
+ desc++; /* skip over y coordinate */
+ if (*desc != ',')
+ return "No ',' after initial y-coordinate in game description";
+ desc++; /* eat comma */
+ /* eat `m', meaning `masked', if present */
+ if (*desc == 'm')
+ desc++;
+ /* now just check length of remainder */
+ if (strlen(desc) != (wh+3)/4)
+ return "Game description is wrong length";
+ }
return NULL;
}
int w = state->w, h = state->h;
int xx, yy, nmines, ncovered;
- if (state->mines[y*w+x]) {
+ if (!state->layout->mines) {
+ /*
+ * We have a preliminary game in which the mine layout
+ * hasn't been generated yet. Generate it based on the
+ * initial click location.
+ */
+ char *desc;
+ state->layout->mines = new_mine_layout(w, h, state->layout->n,
+ x, y, state->layout->unique,
+ state->layout->rs,
+ &desc);
+ midend_supersede_game_desc(state->layout->me, desc);
+ sfree(desc);
+ random_free(state->layout->rs);
+ state->layout->rs = NULL;
+ }
+
+ if (state->layout->mines[y*w+x]) {
/*
- * The player has landed on a mine. Bad luck. Expose all
- * the mines.
+ * The player has landed on a mine. Bad luck. Expose the
+ * mine that killed them, but not the rest (in case they
+ * want to Undo and carry on playing).
*/
state->dead = TRUE;
- for (yy = 0; yy < h; yy++)
- for (xx = 0; xx < w; xx++) {
- if (state->mines[yy*w+xx] &&
- (state->grid[yy*w+xx] == -2 ||
- state->grid[yy*w+xx] == -3)) {
- state->grid[yy*w+xx] = 64;
- }
- if (!state->mines[yy*w+xx] &&
- state->grid[yy*w+xx] == -1) {
- state->grid[yy*w+xx] = 66;
- }
- }
state->grid[y*w+x] = 65;
return -1;
}
if (state->grid[yy*w+xx] == -10) {
int dx, dy, v;
- assert(!state->mines[yy*w+xx]);
+ assert(!state->layout->mines[yy*w+xx]);
v = 0;
for (dy = -1; dy <= +1; dy++)
if (xx+dx >= 0 && xx+dx < state->w &&
yy+dy >= 0 && yy+dy < state->h &&
- state->mines[(yy+dy)*w+(xx+dx)])
+ state->layout->mines[(yy+dy)*w+(xx+dx)])
v++;
state->grid[yy*w+xx] = v;
for (xx = 0; xx < w; xx++) {
if (state->grid[yy*w+xx] < 0)
ncovered++;
- if (state->mines[yy*w+xx])
+ if (state->layout->mines[yy*w+xx])
nmines++;
}
assert(ncovered >= nmines);
return 0;
}
-static game_state *new_game(game_params *params, char *desc)
+static game_state *new_game(midend_data *me, game_params *params, char *desc)
{
game_state *state = snew(game_state);
int i, wh, x, y, ret, masked;
state->h = params->h;
state->n = params->n;
state->dead = state->won = FALSE;
+ state->used_solve = state->just_used_solve = FALSE;
wh = state->w * state->h;
- state->mines = snewn(wh, char);
-
- x = atoi(desc);
- while (*desc && isdigit((unsigned char)*desc))
- desc++; /* skip over x coordinate */
- if (*desc) desc++; /* eat comma */
- y = atoi(desc);
- while (*desc && isdigit((unsigned char)*desc))
- desc++; /* skip over y coordinate */
- if (*desc) desc++; /* eat comma */
-
- if (*desc == 'm') {
- masked = TRUE;
- desc++;
- } else {
- /*
- * We permit game IDs to be entered by hand without the
- * masking transformation.
- */
- masked = FALSE;
- }
- bmp = snewn((wh + 7) / 8, unsigned char);
- memset(bmp, 0, (wh + 7) / 8);
- for (i = 0; i < (wh+3)/4; i++) {
- int c = desc[i];
- int v;
-
- assert(c != 0); /* validate_desc should have caught */
- if (c >= '0' && c <= '9')
- v = c - '0';
- else if (c >= 'a' && c <= 'f')
- v = c - 'a' + 10;
- else if (c >= 'A' && c <= 'F')
- v = c - 'A' + 10;
+ state->layout = snew(struct mine_layout);
+ state->layout->refcount = 1;
+
+ state->grid = snewn(wh, char);
+ memset(state->grid, -2, wh);
+
+ if (*desc == 'r') {
+ desc++;
+ state->layout->n = atoi(desc);
+ while (*desc && isdigit((unsigned char)*desc))
+ desc++; /* skip over mine count */
+ if (*desc) desc++; /* eat comma */
+ if (*desc == 'a')
+ state->layout->unique = FALSE;
else
- v = 0;
+ state->layout->unique = TRUE;
+ desc++;
+ if (*desc) desc++; /* eat comma */
- bmp[i / 2] |= v << (4 * (1 - (i % 2)));
- }
+ state->layout->mines = NULL;
+ state->layout->rs = random_state_decode(desc);
+ state->layout->me = me;
- if (masked)
- obfuscate_bitmap(bmp, wh, TRUE);
+ } else {
+ state->layout->rs = NULL;
+ state->layout->me = NULL;
+
+ state->layout->mines = snewn(wh, char);
+ x = atoi(desc);
+ while (*desc && isdigit((unsigned char)*desc))
+ desc++; /* skip over x coordinate */
+ if (*desc) desc++; /* eat comma */
+ y = atoi(desc);
+ while (*desc && isdigit((unsigned char)*desc))
+ desc++; /* skip over y coordinate */
+ if (*desc) desc++; /* eat comma */
+
+ if (*desc == 'm') {
+ masked = TRUE;
+ desc++;
+ } else {
+ /*
+ * We permit game IDs to be entered by hand without the
+ * masking transformation.
+ */
+ masked = FALSE;
+ }
- memset(state->mines, 0, wh);
- for (i = 0; i < wh; i++) {
- if (bmp[i / 8] & (0x80 >> (i % 8)))
- state->mines[i] = 1;
- }
+ bmp = snewn((wh + 7) / 8, unsigned char);
+ memset(bmp, 0, (wh + 7) / 8);
+ for (i = 0; i < (wh+3)/4; i++) {
+ int c = desc[i];
+ int v;
+
+ assert(c != 0); /* validate_desc should have caught */
+ if (c >= '0' && c <= '9')
+ v = c - '0';
+ else if (c >= 'a' && c <= 'f')
+ v = c - 'a' + 10;
+ else if (c >= 'A' && c <= 'F')
+ v = c - 'A' + 10;
+ else
+ v = 0;
+
+ bmp[i / 2] |= v << (4 * (1 - (i % 2)));
+ }
- state->grid = snewn(wh, char);
- memset(state->grid, -2, wh);
+ if (masked)
+ obfuscate_bitmap(bmp, wh, TRUE);
- ret = open_square(state, x, y);
- /*
- * FIXME: This shouldn't be an assert. Perhaps we actually
- * ought to check it in validate_params! Alternatively, we can
- * remove the assert completely and actually permit a game
- * description to start you off dead.
- */
- assert(ret != -1);
+ memset(state->layout->mines, 0, wh);
+ for (i = 0; i < wh; i++) {
+ if (bmp[i / 8] & (0x80 >> (i % 8)))
+ state->layout->mines[i] = 1;
+ }
+
+ ret = open_square(state, x, y);
+ }
return state;
}
ret->n = state->n;
ret->dead = state->dead;
ret->won = state->won;
- ret->mines = snewn(ret->w * ret->h, char);
- memcpy(ret->mines, state->mines, ret->w * ret->h);
+ ret->used_solve = state->used_solve;
+ ret->just_used_solve = state->just_used_solve;
+ ret->layout = state->layout;
+ ret->layout->refcount++;
ret->grid = snewn(ret->w * ret->h, char);
memcpy(ret->grid, state->grid, ret->w * ret->h);
static void free_game(game_state *state)
{
- sfree(state->mines);
+ if (--state->layout->refcount <= 0) {
+ sfree(state->layout->mines);
+ if (state->layout->rs)
+ random_free(state->layout->rs);
+ sfree(state->layout);
+ }
sfree(state->grid);
sfree(state);
}
static game_state *solve_game(game_state *state, game_aux_info *aux,
char **error)
{
- return NULL;
+ /*
+ * Simply expose the entire grid as if it were a completed
+ * solution.
+ */
+ game_state *ret;
+ int yy, xx;
+
+ if (!state->layout->mines) {
+ *error = "Game has not been started yet";
+ return NULL;
+ }
+
+ ret = dup_game(state);
+ for (yy = 0; yy < ret->h; yy++)
+ for (xx = 0; xx < ret->w; xx++) {
+
+ if (ret->layout->mines[yy*ret->w+xx]) {
+ ret->grid[yy*ret->w+xx] = -1;
+ } else {
+ int dx, dy, v;
+
+ v = 0;
+
+ for (dx = -1; dx <= +1; dx++)
+ for (dy = -1; dy <= +1; dy++)
+ if (xx+dx >= 0 && xx+dx < ret->w &&
+ yy+dy >= 0 && yy+dy < ret->h &&
+ ret->layout->mines[(yy+dy)*ret->w+(xx+dx)])
+ v++;
+
+ ret->grid[yy*ret->w+xx] = v;
+ }
+ }
+ ret->used_solve = ret->just_used_solve = TRUE;
+ ret->won = TRUE;
+
+ return ret;
}
static char *game_text_format(game_state *state)
{
- return NULL;
+ char *ret;
+ int x, y;
+
+ ret = snewn((state->w + 1) * state->h + 1, char);
+ for (y = 0; y < state->h; y++) {
+ for (x = 0; x < state->w; x++) {
+ int v = state->grid[y*state->w+x];
+ if (v == 0)
+ v = '-';
+ else if (v >= 1 && v <= 8)
+ v = '0' + v;
+ else if (v == -1)
+ v = '*';
+ else if (v == -2 || v == -3)
+ v = '?';
+ else if (v >= 64)
+ v = '!';
+ ret[y * (state->w+1) + x] = v;
+ }
+ ret[y * (state->w+1) + state->w] = '\n';
+ }
+ ret[(state->w + 1) * state->h] = '\0';
+
+ return ret;
}
struct game_ui {
int hx, hy, hradius; /* for mouse-down highlights */
int flash_is_death;
+ int deaths;
};
static game_ui *new_ui(game_state *state)
game_ui *ui = snew(game_ui);
ui->hx = ui->hy = -1;
ui->hradius = 0;
+ ui->deaths = 0;
ui->flash_is_death = FALSE; /* *shrug* */
return ui;
}
sfree(ui);
}
-static game_state *make_move(game_state *from, game_ui *ui, int x, int y,
- int button)
+static game_state *make_move(game_state *from, game_ui *ui, game_drawstate *ds,
+ int x, int y, int button)
{
game_state *ret;
int cx, cy;
cx = FROMCOORD(x);
cy = FROMCOORD(y);
- if (cx < 0 || cx >= from->w || cy < 0 || cy > from->h)
+ if (cx < 0 || cx >= from->w || cy < 0 || cy >= from->h)
return NULL;
- if (button == LEFT_BUTTON || button == LEFT_DRAG) {
+ if (button == LEFT_BUTTON || button == LEFT_DRAG ||
+ button == MIDDLE_BUTTON || button == MIDDLE_DRAG) {
/*
* Mouse-downs and mouse-drags just cause highlighting
* updates.
return NULL;
ret = dup_game(from);
+ ret->just_used_solve = FALSE;
ret->grid[cy * from->w + cx] ^= (-2 ^ -1);
return ret;
}
- if (button == LEFT_RELEASE) {
+ if (button == LEFT_RELEASE || button == MIDDLE_RELEASE) {
ui->hx = ui->hy = -1;
ui->hradius = 0;
* permitted if the tile is marked as a mine, for safety.
* (Unmark it and _then_ open it.)
*/
- if (from->grid[cy * from->w + cx] == -2 ||
- from->grid[cy * from->w + cx] == -3) {
+ if (button == LEFT_RELEASE &&
+ (from->grid[cy * from->w + cx] == -2 ||
+ from->grid[cy * from->w + cx] == -3)) {
ret = dup_game(from);
+ ret->just_used_solve = FALSE;
open_square(ret, cx, cy);
+ if (ret->dead)
+ ui->deaths++;
return ret;
}
/*
- * Left-clicking on an uncovered tile: first we check to see if
- * the number of mine markers surrounding the tile is equal to
- * its mine count, and if so then we open all other surrounding
- * squares.
+ * Left-clicking or middle-clicking on an uncovered tile:
+ * first we check to see if the number of mine markers
+ * surrounding the tile is equal to its mine count, and if
+ * so then we open all other surrounding squares.
*/
if (from->grid[cy * from->w + cx] > 0) {
int dy, dx, n;
if (n == from->grid[cy * from->w + cx]) {
ret = dup_game(from);
+ ret->just_used_solve = FALSE;
for (dy = -1; dy <= +1; dy++)
for (dx = -1; dx <= +1; dx++)
if (cx+dx >= 0 && cx+dx < ret->w &&
(ret->grid[(cy+dy)*ret->w+(cx+dx)] == -2 ||
ret->grid[(cy+dy)*ret->w+(cx+dx)] == -3))
open_square(ret, cx+dx, cy+dy);
+ if (ret->dead)
+ ui->deaths++;
return ret;
}
}
struct game_drawstate {
int w, h, started;
- char *grid;
+ signed char *grid;
/*
* Items in this `grid' array have all the same values as in
* the game_state grid, and in addition:
frontend_default_colour(fe, &ret[COL_BACKGROUND * 3]);
+ ret[COL_BACKGROUND2 * 3 + 0] = ret[COL_BACKGROUND * 3 + 0] * 19.0 / 20.0;
+ ret[COL_BACKGROUND2 * 3 + 1] = ret[COL_BACKGROUND * 3 + 1] * 19.0 / 20.0;
+ ret[COL_BACKGROUND2 * 3 + 2] = ret[COL_BACKGROUND * 3 + 2] * 19.0 / 20.0;
+
ret[COL_1 * 3 + 0] = 0.0F;
ret[COL_1 * 3 + 1] = 0.0F;
ret[COL_1 * 3 + 2] = 1.0F;
/*
* Omit the highlights in this case.
*/
- draw_rect(fe, x, y, TILE_SIZE, TILE_SIZE, bg);
+ draw_rect(fe, x, y, TILE_SIZE, TILE_SIZE,
+ bg == COL_BACKGROUND ? COL_BACKGROUND2 : bg);
draw_line(fe, x, y, x + TILE_SIZE - 1, y, COL_LOWLIGHT);
draw_line(fe, x, y, x, y + TILE_SIZE - 1, COL_LOWLIGHT);
} else {
* on), we clear the square to COL_BANG.
*/
draw_rect(fe, x, y, TILE_SIZE, TILE_SIZE,
- (v == 65 ? COL_BANG : bg));
+ (v == 65 ? COL_BANG :
+ bg == COL_BACKGROUND ? COL_BACKGROUND2 : bg));
draw_line(fe, x, y, x + TILE_SIZE - 1, y, COL_LOWLIGHT);
draw_line(fe, x, y, x, y + TILE_SIZE - 1, COL_LOWLIGHT);
if (v == -1)
markers++;
- if (state->mines[y*ds->w+x])
+ if (state->layout->mines && state->layout->mines[y*ds->w+x])
mines++;
if ((v == -2 || v == -3) &&
}
}
+ if (!state->layout->mines)
+ mines = state->layout->n;
+
/*
* Update the status bar.
*/
{
char statusbar[512];
if (state->dead) {
- sprintf(statusbar, "GAME OVER!");
+ sprintf(statusbar, "DEAD!");
} else if (state->won) {
- sprintf(statusbar, "COMPLETED!");
+ if (state->used_solve)
+ sprintf(statusbar, "Auto-solved.");
+ else
+ sprintf(statusbar, "COMPLETED!");
} else {
- sprintf(statusbar, "Mines marked: %d / %d", markers, mines);
+ sprintf(statusbar, "Marked: %d / %d", markers, mines);
}
+ if (ui->deaths)
+ sprintf(statusbar + strlen(statusbar),
+ " Deaths: %d", ui->deaths);
status_bar(fe, statusbar);
}
}
static float game_flash_length(game_state *oldstate, game_state *newstate,
int dir, game_ui *ui)
{
+ if (oldstate->used_solve || newstate->used_solve)
+ return 0.0F;
+
if (dir > 0 && !oldstate->dead && !oldstate->won) {
if (newstate->dead) {
ui->flash_is_death = TRUE;
return TRUE;
}
+static int game_timing_state(game_state *state)
+{
+ if (state->dead || state->won || !state->layout->mines)
+ return FALSE;
+ return TRUE;
+}
+
#ifdef COMBINED
#define thegame mines
#endif
new_game,
dup_game,
free_game,
- FALSE, solve_game,
- FALSE, game_text_format,
+ TRUE, solve_game,
+ TRUE, game_text_format,
new_ui,
free_ui,
make_move,
game_anim_length,
game_flash_length,
game_wants_statusbar,
+ TRUE, game_timing_state,
+ BUTTON_BEATS(LEFT_BUTTON, RIGHT_BUTTON),
};
~mdw / sgt / puzzles / blobdiff