ref: 0564c4c4d05cfadd6282153265e5a5e02d1938d0
parent: 7ff09fbba196e540a60a866c9a7c208b5edacfd8
author: Simon Tatham <anakin@pobox.com>
date: Mon May 30 09:10:37 EDT 2005
Mines now follows the conventional approach of offering a completely blank grid until you make the first click; to ensure solubility, it does not generate the mine layout until that click, and then ensures it is solvable starting from that position. This has involved three infrastructure changes: - random.c now offers functions to encode and decode an entire random_state as a string - each puzzle's new_game() is now passed a pointer to the midend itself, which most of them ignore - there's a function in the midend which a game can call back to _rewrite_ its current game description. So Mines now has two entirely separate forms of game ID. One contains the generation-time parameters (n and unique) plus an encoding of a random_state; the other actually encodes the grid once it's been generated, and also contains the initial click position. When called with the latter, new_game() does plausibly normal stuff. When called with the former, it notes down all the details and waits until the first square is opened, and _then_ does the grid generation and updates the game description in the midend. So if, _after_ your first click, you decide you want to share this particular puzzle with someone else, you can do that fine. Also in this checkin, the mine layout is no longer _copied_ between all the game_states on the undo chain. Instead, it's in a separate structure and all game_states share a pointer to it - and the structure is reference-counted to ensure deallocation. [originally from svn r5862]
--- a/cube.c
+++ b/cube.c
@@ -868,7 +868,7 @@
return NULL;
}
-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 area;
--- a/fifteen.c
+++ b/fifteen.c
@@ -322,7 +322,7 @@
return err;
}
-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;
--- a/midend.c
+++ b/midend.c
@@ -165,7 +165,8 @@
}
ensure(me);
- me->states[me->nstates].state = me->ourgame->new_game(me->params, me->desc);
+ me->states[me->nstates].state =
+ me->ourgame->new_game(me, me->params, me->desc);
me->states[me->nstates].special = TRUE;
me->nstates++;
me->statepos = 1;
@@ -495,7 +496,7 @@
if (me->nstates == 0) {game_aux_info *aux = NULL;
char *desc = me->ourgame->new_desc(me->params, me->random, &aux);
- state = me->ourgame->new_game(me->params, desc);
+ state = me->ourgame->new_game(me, me->params, desc);
sfree(desc);
if (aux)
me->ourgame->free_aux_info(aux);
@@ -624,6 +625,12 @@
int midend_wants_statusbar(midend_data *me)
{return me->ourgame->wants_statusbar();
+}
+
+void midend_supersede_game_desc(midend_data *me, char *desc)
+{+ sfree(me->desc);
+ me->desc = dupstr(desc);
}
config_item *midend_get_config(midend_data *me, int which, char **wintitle)
--- a/mines.c
+++ b/mines.c
@@ -60,9 +60,25 @@
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 */
+ struct mine_layout *layout; /* real mine positions */
char *grid; /* player knowledge */
/*
* Each item in the `grid' array is one of the following values:
@@ -1790,54 +1806,73 @@
}
}
-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;
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);
+ grid = minegen(w, h, n, x, y, unique, rs);
- grid = minegen(params->w, params->h, params->n, x, y, params->unique, rs);
+ 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);
- /*
- * 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);
+ /*
+ * 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);
+ *game_desc = ret;
+ }
- return ret;
+ return grid;
}
+static char *new_game_desc(game_params *params, random_state *rs,
+ game_aux_info **aux)
+{+#ifdef PREOPENED
+ int x = random_upto(rs, params->w);
+ int y = random_upto(rs, params->h);
+ char *grid, *desc;
+
+ grid = new_mine_layout(params->w, params->h, params->n,
+ x, y, params->unique, rs);
+#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;
+#endif
+}
+
static void game_free_aux_info(game_aux_info *aux)
{assert(!"Shouldn't happen");
@@ -1848,32 +1883,48 @@
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;
}
@@ -1883,8 +1934,25 @@
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.
*/
@@ -1891,12 +1959,12 @@
state->dead = TRUE;
for (yy = 0; yy < h; yy++)
for (xx = 0; xx < w; xx++) {- if (state->mines[yy*w+xx] &&
+ if (state->layout->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] &&
+ if (!state->layout->mines[yy*w+xx] &&
state->grid[yy*w+xx] == -1) {state->grid[yy*w+xx] = 66;
}
@@ -1927,7 +1995,7 @@
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;
@@ -1935,7 +2003,7 @@
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;
@@ -1966,7 +2034,7 @@
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);
@@ -1982,7 +2050,7 @@
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;
@@ -1994,68 +2062,84 @@
state->dead = state->won = 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 */
+ state->layout = snew(struct mine_layout);
+ state->layout->refcount = 1;
- if (*desc == 'm') {- masked = TRUE;
+ 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
+ state->layout->unique = TRUE;
+ desc++;
+ if (*desc) desc++; /* eat comma */
+
+ state->layout->mines = NULL;
+ state->layout->rs = random_state_decode(desc);
+ state->layout->me = me;
+
} 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;
+ 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 */
- 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;
+ if (*desc == 'm') {+ masked = TRUE;
+ desc++;
+ } else {+ /*
+ * We permit game IDs to be entered by hand without the
+ * masking transformation.
+ */
+ masked = FALSE;
+ }
- bmp[i / 2] |= v << (4 * (1 - (i % 2)));
- }
+ 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;
- if (masked)
- obfuscate_bitmap(bmp, wh, TRUE);
+ 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;
- memset(state->mines, 0, wh);
- for (i = 0; i < wh; i++) {- if (bmp[i / 8] & (0x80 >> (i % 8)))
- state->mines[i] = 1;
- }
+ 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;
}
@@ -2068,8 +2152,8 @@
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->layout = state->layout;
+ ret->layout->refcount++;
ret->grid = snewn(ret->w * ret->h, char);
memcpy(ret->grid, state->grid, ret->w * ret->h);
@@ -2078,7 +2162,12 @@
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);
}
@@ -2558,7 +2647,7 @@
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) &&
@@ -2570,6 +2659,9 @@
ds->grid[y*ds->w+x] = (bg == COL_BACKGROUND ? v : -10);
}
}
+
+ if (!state->layout->mines)
+ mines = state->layout->n;
/*
* Update the status bar.
--- a/net.c
+++ b/net.c
@@ -1558,7 +1558,7 @@
* Construct an initial game state, given a description and parameters.
*/
-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;
int w, h, x, y;
--- a/netslide.c
+++ b/netslide.c
@@ -738,7 +738,7 @@
* Construct an initial game state, given a description and parameters.
*/
-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;
int w, h, x, y;
--- a/nullgame.c
+++ b/nullgame.c
@@ -99,7 +99,7 @@
return NULL;
}
-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);
--- a/pattern.c
+++ b/pattern.c
@@ -601,7 +601,7 @@
return NULL;
}
-static game_state *new_game(game_params *params, char *desc)
+static game_state *new_game(midend_data *me, game_params *params, char *desc)
{int i;
char *p;
--- a/puzzles.h
+++ b/puzzles.h
@@ -144,6 +144,7 @@
char *midend_game_id(midend_data *me, char *id);
char *midend_text_format(midend_data *me);
char *midend_solve(midend_data *me);
+void midend_supersede_game_desc(midend_data *me, char *desc);
/*
* malloc.c
@@ -176,6 +177,8 @@
unsigned long random_bits(random_state *state, int bits);
unsigned long random_upto(random_state *state, unsigned long limit);
void random_free(random_state *state);
+char *random_state_encode(random_state *state);
+random_state *random_state_decode(char *input);
/* random.c also exports SHA, which occasionally comes in useful. */
typedef unsigned long uint32;
typedef struct {@@ -213,7 +216,7 @@
game_aux_info **aux);
void (*free_aux_info)(game_aux_info *aux);
char *(*validate_desc)(game_params *params, char *desc);
- game_state *(*new_game)(game_params *params, char *desc);
+ game_state *(*new_game)(midend_data *me, game_params *params, char *desc);
game_state *(*dup_game)(game_state *state);
void (*free_game)(game_state *state);
int can_solve;
--- a/random.c
+++ b/random.c
@@ -12,6 +12,7 @@
#include <assert.h>
#include <string.h>
+#include <stdio.h>
#include "puzzles.h"
@@ -277,4 +278,64 @@
void random_free(random_state *state)
{sfree(state);
+}
+
+char *random_state_encode(random_state *state)
+{+ char retbuf[256];
+ int len = 0, i;
+
+ for (i = 0; i < lenof(state->seedbuf); i++)
+ len += sprintf(retbuf+len, "%02x", state->seedbuf[i]);
+ for (i = 0; i < lenof(state->databuf); i++)
+ len += sprintf(retbuf+len, "%02x", state->databuf[i]);
+ len += sprintf(retbuf+len, "%02x", state->pos);
+
+ return dupstr(retbuf);
+}
+
+random_state *random_state_decode(char *input)
+{+ random_state *state;
+ int pos, byte, digits;
+
+ state = snew(random_state);
+
+ memset(state->seedbuf, 0, sizeof(state->seedbuf));
+ memset(state->databuf, 0, sizeof(state->databuf));
+ state->pos = 0;
+
+ byte = digits = 0;
+ pos = 0;
+ while (*input) {+ int v = *input++;
+
+ if (v >= '0' && v <= '9')
+ v = v - '0';
+ else if (v >= 'A' && v <= 'F')
+ v = v - 'A' + 10;
+ else if (v >= 'a' && v <= 'f')
+ v = v - 'a' + 10;
+ else
+ v = 0;
+
+ byte = (byte << 4) | v;
+ digits++;
+
+ if (digits == 2) {+ /*
+ * We have a byte. Put it somewhere.
+ */
+ if (pos < lenof(state->seedbuf))
+ state->seedbuf[pos++] = byte;
+ else if (pos < lenof(state->seedbuf) + lenof(state->databuf))
+ state->databuf[pos++ - lenof(state->seedbuf)] = byte;
+ else if (pos == lenof(state->seedbuf) + lenof(state->databuf) &&
+ byte <= lenof(state->databuf))
+ state->pos = byte;
+ byte = digits = 0;
+ }
+ }
+
+ return state;
}
--- a/rect.c
+++ b/rect.c
@@ -1691,7 +1691,7 @@
return NULL;
}
-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 x, y, i, area;
--- a/sixteen.c
+++ b/sixteen.c
@@ -442,7 +442,7 @@
return err;
}
-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;
--- a/solo.c
+++ b/solo.c
@@ -1620,7 +1620,7 @@
return NULL;
}
-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 c = params->c, r = params->r, cr = c*r, area = cr * cr;
--- a/twiddle.c
+++ b/twiddle.c
@@ -428,7 +428,7 @@
return NULL;
}
-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 w = params->w, h = params->h, n = params->n, wh = w*h;