From 881746789a489fad85aae8317555f73dbe261556 Mon Sep 17 00:00:00 2001 From: Franklin Wei Date: Sat, 29 Apr 2017 18:21:56 -0400 Subject: puzzles: refactor and resync with upstream This brings puzzles up-to-date with upstream revision 2d333750272c3967cfd5cd3677572cddeaad5932, though certain changes made by me, including cursor-only Untangle and some compilation fixes remain. Upstream code has been moved to its separate subdirectory and future syncs can be done by simply copying over the new sources. Change-Id: Ia6506ca5f78c3627165ea6791d38db414ace0804 --- apps/plugins/puzzles/src/mines.c | 3250 ++++++++++++++++++++++++++++++++++++++ 1 file changed, 3250 insertions(+) create mode 100644 apps/plugins/puzzles/src/mines.c (limited to 'apps/plugins/puzzles/src/mines.c') diff --git a/apps/plugins/puzzles/src/mines.c b/apps/plugins/puzzles/src/mines.c new file mode 100644 index 0000000000..6a5ce029a0 --- /dev/null +++ b/apps/plugins/puzzles/src/mines.c @@ -0,0 +1,3250 @@ +/* + * mines.c: Minesweeper clone with sophisticated grid generation. + * + * Still TODO: + * + * - think about configurably supporting question marks. Once, + * that is, we've thought about configurability in general! + */ + +#include +#include +#include +#include +#include +#include + +#include "tree234.h" +#include "puzzles.h" + +enum { + 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, + COL_WRONGNUMBER, + COL_CURSOR, + NCOLOURS +}; + +#define PREFERRED_TILE_SIZE 20 +#define TILE_SIZE (ds->tilesize) +#ifdef SMALL_SCREEN +#define BORDER 8 +#else +#define BORDER (TILE_SIZE * 3 / 2) +#endif +#define HIGHLIGHT_WIDTH (TILE_SIZE / 10) +#define OUTER_HIGHLIGHT_WIDTH (BORDER / 10) +#define COORD(x) ( (x) * TILE_SIZE + BORDER ) +#define FROMCOORD(x) ( ((x) - BORDER + TILE_SIZE) / TILE_SIZE - 1 ) + +#define FLASH_FRAME 0.13F + +struct game_params { + int w, h, n; + 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 *me; /* to give back the new game desc */ +}; + +struct game_state { + int w, h, n, dead, won; + int 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: + * + * - 0 to 8 mean the square is open and has a surrounding mine + * count. + * + * - -1 means the square is marked as a mine. + * + * - -2 means the square is unknown. + * + * - -3 means the square is marked with a question mark + * (FIXME: do we even want to bother with this?). + * + * - 64 means the square has had a mine revealed when the game + * was lost. + * + * - 65 means the square had a mine revealed and this was the + * one the player hits. + * + * - 66 means the square has a crossed-out mine because the + * player had incorrectly marked it. + */ +}; + +static game_params *default_params(void) +{ + game_params *ret = snew(game_params); + + ret->w = ret->h = 9; + ret->n = 10; + ret->unique = TRUE; + + return ret; +} + +static const struct game_params mines_presets[] = { + {9, 9, 10, TRUE}, + {9, 9, 35, TRUE}, + {16, 16, 40, TRUE}, + {16, 16, 99, TRUE}, +#ifndef SMALL_SCREEN + {30, 16, 99, TRUE}, + {30, 16, 170, TRUE}, +#endif +}; + +static int game_fetch_preset(int i, char **name, game_params **params) +{ + game_params *ret; + char str[80]; + + if (i < 0 || i >= lenof(mines_presets)) + return FALSE; + + ret = snew(game_params); + *ret = mines_presets[i]; + + sprintf(str, "%dx%d, %d mines", ret->w, ret->h, ret->n); + + *name = dupstr(str); + *params = ret; + return TRUE; +} + +static void free_params(game_params *params) +{ + sfree(params); +} + +static game_params *dup_params(const game_params *params) +{ + game_params *ret = snew(game_params); + *ret = *params; /* structure copy */ + return ret; +} + +static void decode_params(game_params *params, char const *string) +{ + char const *p = string; + + params->w = atoi(p); + while (*p && isdigit((unsigned char)*p)) p++; + if (*p == 'x') { + p++; + params->h = atoi(p); + while (*p && isdigit((unsigned char)*p)) p++; + } else { + params->h = params->w; + } + if (*p == 'n') { + p++; + params->n = atoi(p); + while (*p && (*p == '.' || isdigit((unsigned char)*p))) p++; + } else { + params->n = params->w * params->h / 10; + } + + while (*p) { + if (*p == 'a') { + p++; + params->unique = FALSE; + } else + p++; /* skip any other gunk */ + } +} + +static char *encode_params(const game_params *params, int full) +{ + char ret[400]; + int len; + + len = sprintf(ret, "%dx%d", params->w, params->h); + /* + * Mine count is a generation-time parameter, since it can be + * deduced from the mine bitmap! + */ + if (full) + len += sprintf(ret+len, "n%d", params->n); + if (full && !params->unique) + ret[len++] = 'a'; + assert(len < lenof(ret)); + ret[len] = '\0'; + + return dupstr(ret); +} + +static config_item *game_configure(const game_params *params) +{ + config_item *ret; + char buf[80]; + + ret = snewn(5, config_item); + + ret[0].name = "Width"; + ret[0].type = C_STRING; + sprintf(buf, "%d", params->w); + ret[0].sval = dupstr(buf); + ret[0].ival = 0; + + ret[1].name = "Height"; + ret[1].type = C_STRING; + sprintf(buf, "%d", params->h); + ret[1].sval = dupstr(buf); + ret[1].ival = 0; + + ret[2].name = "Mines"; + ret[2].type = C_STRING; + sprintf(buf, "%d", params->n); + ret[2].sval = dupstr(buf); + ret[2].ival = 0; + + ret[3].name = "Ensure solubility"; + ret[3].type = C_BOOLEAN; + ret[3].sval = NULL; + ret[3].ival = params->unique; + + ret[4].name = NULL; + ret[4].type = C_END; + ret[4].sval = NULL; + ret[4].ival = 0; + + return ret; +} + +static game_params *custom_params(const config_item *cfg) +{ + game_params *ret = snew(game_params); + + 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; +} + +static char *validate_params(const game_params *params, int full) +{ + /* + * Lower limit on grid size: each dimension must be at least 3. + * 1 is theoretically workable if rather boring, but 2 is a + * real problem: there is often _no_ way to generate a uniquely + * solvable 2xn Mines grid. You either run into two mines + * blocking the way and no idea what's behind them, or one mine + * and no way to know which of the two rows it's in. If the + * mine count is even you can create a soluble grid by packing + * all the mines at one end (so what when you hit a two-mine + * wall there are only as many covered squares left as there + * are mines); but if it's odd, you are doomed, because you + * _have_ to have a gap somewhere which you can't determine the + * position of. + */ + if (full && params->unique && (params->w <= 2 || params->h <= 2)) + return "Width and height must both be greater than two"; + if (params->n > params->w * params->h - 9) + return "Too many mines for grid size"; + + /* + * FIXME: Need more constraints here. Not sure what the + * sensible limits for Minesweeper actually are. The limits + * probably ought to change, however, depending on uniqueness. + */ + + return NULL; +} + +/* ---------------------------------------------------------------------- + * Minesweeper solver, used to ensure the generated grids are + * solvable without having to take risks. + */ + +/* + * Count the bits in a word. Only needs to cope with 16 bits. + */ +static int bitcount16(int inword) +{ + unsigned int word = inword; + + word = ((word & 0xAAAA) >> 1) + (word & 0x5555); + word = ((word & 0xCCCC) >> 2) + (word & 0x3333); + word = ((word & 0xF0F0) >> 4) + (word & 0x0F0F); + word = ((word & 0xFF00) >> 8) + (word & 0x00FF); + + return (int)word; +} + +/* + * We use a tree234 to store a large number of small localised + * sets, each with a mine count. We also keep some of those sets + * linked together into a to-do list. + */ +struct set { + short x, y, mask, mines; + int todo; + struct set *prev, *next; +}; + +static int setcmp(void *av, void *bv) +{ + struct set *a = (struct set *)av; + struct set *b = (struct set *)bv; + + if (a->y < b->y) + return -1; + else if (a->y > b->y) + return +1; + else if (a->x < b->x) + return -1; + else if (a->x > b->x) + return +1; + else if (a->mask < b->mask) + return -1; + else if (a->mask > b->mask) + return +1; + else + return 0; +} + +struct setstore { + tree234 *sets; + struct set *todo_head, *todo_tail; +}; + +static struct setstore *ss_new(void) +{ + struct setstore *ss = snew(struct setstore); + ss->sets = newtree234(setcmp); + ss->todo_head = ss->todo_tail = NULL; + return ss; +} + +/* + * Take two input sets, in the form (x,y,mask). Munge the first by + * taking either its intersection with the second or its difference + * with the second. Return the new mask part of the first set. + */ +static int setmunge(int x1, int y1, int mask1, int x2, int y2, int mask2, + int diff) +{ + /* + * Adjust the second set so that it has the same x,y + * coordinates as the first. + */ + if (abs(x2-x1) >= 3 || abs(y2-y1) >= 3) { + mask2 = 0; + } else { + while (x2 > x1) { + mask2 &= ~(4|32|256); + mask2 <<= 1; + x2--; + } + while (x2 < x1) { + mask2 &= ~(1|8|64); + mask2 >>= 1; + x2++; + } + while (y2 > y1) { + mask2 &= ~(64|128|256); + mask2 <<= 3; + y2--; + } + while (y2 < y1) { + mask2 &= ~(1|2|4); + mask2 >>= 3; + y2++; + } + } + + /* + * Invert the second set if `diff' is set (we're after A &~ B + * rather than A & B). + */ + if (diff) + mask2 ^= 511; + + /* + * Now all that's left is a logical AND. + */ + return mask1 & mask2; +} + +static void ss_add_todo(struct setstore *ss, struct set *s) +{ + if (s->todo) + return; /* already on it */ + +#ifdef SOLVER_DIAGNOSTICS + printf("adding set on todo list: %d,%d %03x %d\n", + s->x, s->y, s->mask, s->mines); +#endif + + s->prev = ss->todo_tail; + if (s->prev) + s->prev->next = s; + else + ss->todo_head = s; + ss->todo_tail = s; + s->next = NULL; + s->todo = TRUE; +} + +static void ss_add(struct setstore *ss, int x, int y, int mask, int mines) +{ + struct set *s; + + assert(mask != 0); + + /* + * Normalise so that x and y are genuinely the bounding + * rectangle. + */ + while (!(mask & (1|8|64))) + mask >>= 1, x++; + while (!(mask & (1|2|4))) + mask >>= 3, y++; + + /* + * Create a set structure and add it to the tree. + */ + s = snew(struct set); + s->x = x; + s->y = y; + s->mask = mask; + s->mines = mines; + s->todo = FALSE; + if (add234(ss->sets, s) != s) { + /* + * This set already existed! Free it and return. + */ + sfree(s); + return; + } + + /* + * We've added a new set to the tree, so put it on the todo + * list. + */ + ss_add_todo(ss, s); +} + +static void ss_remove(struct setstore *ss, struct set *s) +{ + struct set *next = s->next, *prev = s->prev; + +#ifdef SOLVER_DIAGNOSTICS + printf("removing set %d,%d %03x\n", s->x, s->y, s->mask); +#endif + /* + * Remove s from the todo list. + */ + if (prev) + prev->next = next; + else if (s == ss->todo_head) + ss->todo_head = next; + + if (next) + next->prev = prev; + else if (s == ss->todo_tail) + ss->todo_tail = prev; + + s->todo = FALSE; + + /* + * Remove s from the tree. + */ + del234(ss->sets, s); + + /* + * Destroy the actual set structure. + */ + sfree(s); +} + +/* + * Return a dynamically allocated list of all the sets which + * overlap a provided input set. + */ +static struct set **ss_overlap(struct setstore *ss, int x, int y, int mask) +{ + struct set **ret = NULL; + int nret = 0, retsize = 0; + int xx, yy; + + for (xx = x-3; xx < x+3; xx++) + for (yy = y-3; yy < y+3; yy++) { + struct set stmp, *s; + int pos; + + /* + * Find the first set with these top left coordinates. + */ + stmp.x = xx; + stmp.y = yy; + stmp.mask = 0; + + if (findrelpos234(ss->sets, &stmp, NULL, REL234_GE, &pos)) { + while ((s = index234(ss->sets, pos)) != NULL && + s->x == xx && s->y == yy) { + /* + * This set potentially overlaps the input one. + * Compute the intersection to see if they + * really overlap, and add it to the list if + * so. + */ + if (setmunge(x, y, mask, s->x, s->y, s->mask, FALSE)) { + /* + * There's an overlap. + */ + if (nret >= retsize) { + retsize = nret + 32; + ret = sresize(ret, retsize, struct set *); + } + ret[nret++] = s; + } + + pos++; + } + } + } + + ret = sresize(ret, nret+1, struct set *); + ret[nret] = NULL; + + return ret; +} + +/* + * Get an element from the head of the set todo list. + */ +static struct set *ss_todo(struct setstore *ss) +{ + if (ss->todo_head) { + struct set *ret = ss->todo_head; + ss->todo_head = ret->next; + if (ss->todo_head) + ss->todo_head->prev = NULL; + else + ss->todo_tail = NULL; + ret->next = ret->prev = NULL; + ret->todo = FALSE; + return ret; + } else { + return NULL; + } +} + +struct squaretodo { + int *next; + int head, tail; +}; + +static void std_add(struct squaretodo *std, int i) +{ + if (std->tail >= 0) + std->next[std->tail] = i; + else + std->head = i; + std->tail = i; + std->next[i] = -1; +} + +typedef int (*open_cb)(void *, int, int); + +static void known_squares(int w, int h, struct squaretodo *std, + signed char *grid, + open_cb open, void *openctx, + int x, int y, int mask, int mine) +{ + int xx, yy, bit; + + bit = 1; + + for (yy = 0; yy < 3; yy++) + for (xx = 0; xx < 3; xx++) { + if (mask & bit) { + int i = (y + yy) * w + (x + xx); + + /* + * It's possible that this square is _already_ + * known, in which case we don't try to add it to + * the list twice. + */ + if (grid[i] == -2) { + + if (mine) { + grid[i] = -1; /* and don't open it! */ + } else { + grid[i] = open(openctx, x + xx, y + yy); + assert(grid[i] != -1); /* *bang* */ + } + std_add(std, i); + + } + } + bit <<= 1; + } +} + +/* + * This is data returned from the `perturb' function. It details + * which squares have become mines and which have become clear. The + * solver is (of course) expected to honourably not use that + * knowledge directly, but to efficently adjust its internal data + * structures and proceed based on only the information it + * legitimately has. + */ +struct perturbation { + int x, y; + int delta; /* +1 == become a mine; -1 == cleared */ +}; +struct perturbations { + int n; + struct perturbation *changes; +}; + +/* + * Main solver entry point. You give it a grid of existing + * knowledge (-1 for a square known to be a mine, 0-8 for empty + * squares with a given number of neighbours, -2 for completely + * unknown), plus a function which you can call to open new squares + * once you're confident of them. It fills in as much more of the + * grid as it can. + * + * Return value is: + * + * - -1 means deduction stalled and nothing could be done + * - 0 means deduction succeeded fully + * - >0 means deduction succeeded but some number of perturbation + * steps were required; the exact return value is the number of + * perturb calls. + */ + +typedef struct perturbations *(*perturb_cb) (void *, signed char *, int, int, int); + +static int minesolve(int w, int h, int n, signed char *grid, + open_cb open, + perturb_cb perturb, + void *ctx, random_state *rs) +{ + struct setstore *ss = ss_new(); + struct set **list; + struct squaretodo astd, *std = &astd; + int x, y, i, j; + int nperturbs = 0; + + /* + * Set up a linked list of squares with known contents, so that + * we can process them one by one. + */ + std->next = snewn(w*h, int); + std->head = std->tail = -1; + + /* + * Initialise that list with all known squares in the input + * grid. + */ + for (y = 0; y < h; y++) { + for (x = 0; x < w; x++) { + i = y*w+x; + if (grid[i] != -2) + std_add(std, i); + } + } + + /* + * Main deductive loop. + */ + while (1) { + int done_something = FALSE; + struct set *s; + + /* + * If there are any known squares on the todo list, process + * them and construct a set for each. + */ + while (std->head != -1) { + i = std->head; +#ifdef SOLVER_DIAGNOSTICS + printf("known square at %d,%d [%d]\n", i%w, i/w, grid[i]); +#endif + std->head = std->next[i]; + if (std->head == -1) + std->tail = -1; + + x = i % w; + y = i / w; + + if (grid[i] >= 0) { + int dx, dy, mines, bit, val; +#ifdef SOLVER_DIAGNOSTICS + printf("creating set around this square\n"); +#endif + /* + * Empty square. Construct the set of non-known squares + * around this one, and determine its mine count. + */ + mines = grid[i]; + bit = 1; + val = 0; + for (dy = -1; dy <= +1; dy++) { + for (dx = -1; dx <= +1; dx++) { +#ifdef SOLVER_DIAGNOSTICS + printf("grid %d,%d = %d\n", x+dx, y+dy, grid[i+dy*w+dx]); +#endif + if (x+dx < 0 || x+dx >= w || y+dy < 0 || y+dy >= h) + /* ignore this one */; + else if (grid[i+dy*w+dx] == -1) + mines--; + else if (grid[i+dy*w+dx] == -2) + val |= bit; + bit <<= 1; + } + } + if (val) + ss_add(ss, x-1, y-1, val, mines); + } + + /* + * Now, whether the square is empty or full, we must + * find any set which contains it and replace it with + * one which does not. + */ + { +#ifdef SOLVER_DIAGNOSTICS + printf("finding sets containing known square %d,%d\n", x, y); +#endif + list = ss_overlap(ss, x, y, 1); + + for (j = 0; list[j]; j++) { + int newmask, newmines; + + s = list[j]; + + /* + * Compute the mask for this set minus the + * newly known square. + */ + newmask = setmunge(s->x, s->y, s->mask, x, y, 1, TRUE); + + /* + * Compute the new mine count. + */ + newmines = s->mines - (grid[i] == -1); + + /* + * Insert the new set into the collection, + * unless it's been whittled right down to + * nothing. + */ + if (newmask) + ss_add(ss, s->x, s->y, newmask, newmines); + + /* + * Destroy the old one; it is actually obsolete. + */ + ss_remove(ss, s); + } + + sfree(list); + } + + /* + * Marking a fresh square as known certainly counts as + * doing something. + */ + done_something = TRUE; + } + + /* + * Now pick a set off the to-do list and attempt deductions + * based on it. + */ + if ((s = ss_todo(ss)) != NULL) { + +#ifdef SOLVER_DIAGNOSTICS + printf("set to do: %d,%d %03x %d\n", s->x, s->y, s->mask, s->mines); +#endif + /* + * Firstly, see if this set has a mine count of zero or + * of its own cardinality. + */ + if (s->mines == 0 || s->mines == bitcount16(s->mask)) { + /* + * If so, we can immediately mark all the squares + * in the set as known. + */ +#ifdef SOLVER_DIAGNOSTICS + printf("easy\n"); +#endif + known_squares(w, h, std, grid, open, ctx, + s->x, s->y, s->mask, (s->mines != 0)); + + /* + * Having done that, we need do nothing further + * with this set; marking all the squares in it as + * known will eventually eliminate it, and will + * also permit further deductions about anything + * that overlaps it. + */ + continue; + } + + /* + * Failing that, we now search through all the sets + * which overlap this one. + */ + list = ss_overlap(ss, s->x, s->y, s->mask); + + for (j = 0; list[j]; j++) { + struct set *s2 = list[j]; + int swing, s2wing, swc, s2wc; + + /* + * Find the non-overlapping parts s2-s and s-s2, + * and their cardinalities. + * + * I'm going to refer to these parts as `wings' + * surrounding the central part common to both + * sets. The `s wing' is s-s2; the `s2 wing' is + * s2-s. + */ + swing = setmunge(s->x, s->y, s->mask, s2->x, s2->y, s2->mask, + TRUE); + s2wing = setmunge(s2->x, s2->y, s2->mask, s->x, s->y, s->mask, + TRUE); + swc = bitcount16(swing); + s2wc = bitcount16(s2wing); + + /* + * If one set has more mines than the other, and + * the number of extra mines is equal to the + * cardinality of that set's wing, then we can mark + * every square in the wing as a known mine, and + * every square in the other wing as known clear. + */ + if (swc == s->mines - s2->mines || + s2wc == s2->mines - s->mines) { + known_squares(w, h, std, grid, open, ctx, + s->x, s->y, swing, + (swc == s->mines - s2->mines)); + known_squares(w, h, std, grid, open, ctx, + s2->x, s2->y, s2wing, + (s2wc == s2->mines - s->mines)); + continue; + } + + /* + * Failing that, see if one set is a subset of the + * other. If so, we can divide up the mine count of + * the larger set between the smaller set and its + * complement, even if neither smaller set ends up + * being immediately clearable. + */ + if (swc == 0 && s2wc != 0) { + /* s is a subset of s2. */ + assert(s2->mines > s->mines); + ss_add(ss, s2->x, s2->y, s2wing, s2->mines - s->mines); + } else if (s2wc == 0 && swc != 0) { + /* s2 is a subset of s. */ + assert(s->mines > s2->mines); + ss_add(ss, s->x, s->y, swing, s->mines - s2->mines); + } + } + + sfree(list); + + /* + * In this situation we have definitely done + * _something_, even if it's only reducing the size of + * our to-do list. + */ + done_something = TRUE; + } else if (n >= 0) { + /* + * We have nothing left on our todo list, which means + * all localised deductions have failed. Our next step + * is to resort to global deduction based on the total + * mine count. This is computationally expensive + * compared to any of the above deductions, which is + * why we only ever do it when all else fails, so that + * hopefully it won't have to happen too often. + * + * If you pass n<0 into this solver, that informs it + * that you do not know the total mine count, so it + * won't even attempt these deductions. + */ + + int minesleft, squaresleft; + int nsets, setused[10], cursor; + + /* + * Start by scanning the current grid state to work out + * how many unknown squares we still have, and how many + * mines are to be placed in them. + */ + squaresleft = 0; + minesleft = n; + for (i = 0; i < w*h; i++) { + if (grid[i] == -1) + minesleft--; + else if (grid[i] == -2) + squaresleft++; + } + +#ifdef SOLVER_DIAGNOSTICS + printf("global deduction time: squaresleft=%d minesleft=%d\n", + squaresleft, minesleft); + for (y = 0; y < h; y++) { + for (x = 0; x < w; x++) { + int v = grid[y*w+x]; + if (v == -1) + putchar('*'); + else if (v == -2) + putchar('?'); + else if (v == 0) + putchar('-'); + else + putchar('0' + v); + } + putchar('\n'); + } +#endif + + /* + * If there _are_ no unknown squares, we have actually + * finished. + */ + if (squaresleft == 0) { + assert(minesleft == 0); + break; + } + + /* + * First really simple case: if there are no more mines + * left, or if there are exactly as many mines left as + * squares to play them in, then it's all easy. + */ + if (minesleft == 0 || minesleft == squaresleft) { + for (i = 0; i < w*h; i++) + if (grid[i] == -2) + known_squares(w, h, std, grid, open, ctx, + i % w, i / w, 1, minesleft != 0); + continue; /* now go back to main deductive loop */ + } + + /* + * Failing that, we have to do some _real_ work. + * Ideally what we do here is to try every single + * combination of the currently available sets, in an + * attempt to find a disjoint union (i.e. a set of + * squares with a known mine count between them) such + * that the remaining unknown squares _not_ contained + * in that union either contain no mines or are all + * mines. + * + * Actually enumerating all 2^n possibilities will get + * a bit slow for large n, so I artificially cap this + * recursion at n=10 to avoid too much pain. + */ + nsets = count234(ss->sets); + if (nsets <= lenof(setused)) { + /* + * Doing this with actual recursive function calls + * would get fiddly because a load of local + * variables from this function would have to be + * passed down through the recursion. So instead + * I'm going to use a virtual recursion within this + * function. The way this works is: + * + * - we have an array `setused', such that + * setused[n] is 0 or 1 depending on whether set + * n is currently in the union we are + * considering. + * + * - we have a value `cursor' which indicates how + * much of `setused' we have so far filled in. + * It's conceptually the recursion depth. + * + * We begin by setting `cursor' to zero. Then: + * + * - if cursor can advance, we advance it by one. + * We set the value in `setused' that it went + * past to 1 if that set is disjoint from + * anything else currently in `setused', or to 0 + * otherwise. + * + * - If cursor cannot advance because it has + * reached the end of the setused list, then we + * have a maximal disjoint union. Check to see + * whether its mine count has any useful + * properties. If so, mark all the squares not + * in the union as known and terminate. + * + * - If cursor has reached the end of setused and + * the algorithm _hasn't_ terminated, back + * cursor up to the nearest 1, turn it into a 0 + * and advance cursor just past it. + * + * - If we attempt to back up to the nearest 1 and + * there isn't one at all, then we have gone + * through all disjoint unions of sets in the + * list and none of them has been helpful, so we + * give up. + */ + struct set *sets[lenof(setused)]; + for (i = 0; i < nsets; i++) + sets[i] = index234(ss->sets, i); + + cursor = 0; + while (1) { + + if (cursor < nsets) { + int ok = TRUE; + + /* See if any existing set overlaps this one. */ + for (i = 0; i < cursor; i++) + if (setused[i] && + setmunge(sets[cursor]->x, + sets[cursor]->y, + sets[cursor]->mask, + sets[i]->x, sets[i]->y, sets[i]->mask, + FALSE)) { + ok = FALSE; + break; + } + + if (ok) { + /* + * We're adding this set to our union, + * so adjust minesleft and squaresleft + * appropriately. + */ + minesleft -= sets[cursor]->mines; + squaresleft -= bitcount16(sets[cursor]->mask); + } + + setused[cursor++] = ok; + } else { +#ifdef SOLVER_DIAGNOSTICS + printf("trying a set combination with %d %d\n", + squaresleft, minesleft); +#endif /* SOLVER_DIAGNOSTICS */ + + /* + * We've reached the end. See if we've got + * anything interesting. + */ + if (squaresleft > 0 && + (minesleft == 0 || minesleft == squaresleft)) { + /* + * We have! There is at least one + * square not contained within the set + * union we've just found, and we can + * deduce that either all such squares + * are mines or all are not (depending + * on whether minesleft==0). So now all + * we have to do is actually go through + * the grid, find those squares, and + * mark them. + */ + for (i = 0; i < w*h; i++) + if (grid[i] == -2) { + int outside = TRUE; + y = i / w; + x = i % w; + for (j = 0; j < nsets; j++) + if (setused[j] && + setmunge(sets[j]->x, sets[j]->y, + sets[j]->mask, x, y, 1, + FALSE)) { + outside = FALSE; + break; + } + if (outside) + known_squares(w, h, std, grid, + open, ctx, + x, y, 1, minesleft != 0); + } + + done_something = TRUE; + break; /* return to main deductive loop */ + } + + /* + * If we reach here, then this union hasn't + * done us any good, so move on to the + * next. Backtrack cursor to the nearest 1, + * change it to a 0 and continue. + */ + while (--cursor >= 0 && !setused[cursor]); + if (cursor >= 0) { + assert(setused[cursor]); + + /* + * We're removing this set from our + * union, so re-increment minesleft and + * squaresleft. + */ + minesleft += sets[cursor]->mines; + squaresleft += bitcount16(sets[cursor]->mask); + + setused[cursor++] = 0; + } else { + /* + * We've backtracked all the way to the + * start without finding a single 1, + * which means that our virtual + * recursion is complete and nothing + * helped. + */ + break; + } + } + + } + + } + } + + if (done_something) + continue; + +#ifdef SOLVER_DIAGNOSTICS + /* + * Dump the current known state of the grid. + */ + printf("solver ran out of steam, ret=%d, grid:\n", nperturbs); + for (y = 0; y < h; y++) { + for (x = 0; x < w; x++) { + int v = grid[y*w+x]; + if (v == -1) + putchar('*'); + else if (v == -2) + putchar('?'); + else if (v == 0) + putchar('-'); + else + putchar('0' + v); + } + putchar('\n'); + } + + { + struct set *s; + + for (i = 0; (s = index234(ss->sets, i)) != NULL; i++) + printf("remaining set: %d,%d %03x %d\n", s->x, s->y, s->mask, s->mines); + } +#endif + + /* + * Now we really are at our wits' end as far as solving + * this grid goes. Our only remaining option is to call + * a perturb function and ask it to modify the grid to + * make it easier. + */ + if (perturb) { + struct perturbations *ret; + struct set *s; + + nperturbs++; + + /* + * Choose a set at random from the current selection, + * and ask the perturb function to either fill or empty + * it. + * + * If we have no sets at all, we must give up. + */ + 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); +#endif + ret = perturb(ctx, grid, s->x, s->y, s->mask); + } + + if (ret) { + assert(ret->n > 0); /* otherwise should have been NULL */ + + /* + * A number of squares have been fiddled with, and + * 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++) { +#ifdef SOLVER_DIAGNOSTICS + printf("perturbation %s mine at %d,%d\n", + ret->changes[i].delta > 0 ? "added" : "removed", + 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); + + for (j = 0; list[j]; j++) { + list[j]->mines += ret->changes[i].delta; + ss_add_todo(ss, list[j]); + } + + sfree(list); + } + + /* + * Now free the returned data. + */ + sfree(ret->changes); + sfree(ret); + +#ifdef SOLVER_DIAGNOSTICS + /* + * Dump the current known state of the grid. + */ + printf("state after perturbation:\n"); + for (y = 0; y < h; y++) { + for (x = 0; x < w; x++) { + int v = grid[y*w+x]; + if (v == -1) + putchar('*'); + else if (v == -2) + putchar('?'); + else if (v == 0) + putchar('-'); + else + putchar('0' + v); + } + putchar('\n'); + } + + { + struct set *s; + + for (i = 0; (s = index234(ss->sets, i)) != NULL; i++) + printf("remaining set: %d,%d %03x %d\n", s->x, s->y, s->mask, s->mines); + } +#endif + + /* + * And now we can go back round the deductive loop. + */ + continue; + } + } + + /* + * If we get here, even that didn't work (either we didn't + * have a perturb function or it returned failure), so we + * give up entirely. + */ + break; + } + + /* + * See if we've got any unknown squares left. + */ + for (y = 0; y < h; y++) + for (x = 0; x < w; x++) + if (grid[y*w+x] == -2) { + nperturbs = -1; /* failed to complete */ + break; + } + + /* + * Free the set list and square-todo list. + */ + { + struct set *s; + while ((s = delpos234(ss->sets, 0)) != NULL) + sfree(s); + freetree234(ss->sets); + sfree(ss); + sfree(std->next); + } + + return nperturbs; +} + +/* ---------------------------------------------------------------------- + * Grid generator which uses the above solver. + */ + +struct minectx { + char *grid; + int w, h; + int sx, sy; + int allow_big_perturbs; + random_state *rs; +}; + +static int mineopen(void *vctx, int x, int y) +{ + struct minectx *ctx = (struct minectx *)vctx; + int i, j, n; + + assert(x >= 0 && x < ctx->w && y >= 0 && y < ctx->h); + if (ctx->grid[y * ctx->w + x]) + return -1; /* *bang* */ + + n = 0; + for (i = -1; i <= +1; i++) { + if (x + i < 0 || x + i >= ctx->w) + continue; + for (j = -1; j <= +1; j++) { + if (y + j < 0 || y + j >= ctx->h) + continue; + if (i == 0 && j == 0) + continue; + if (ctx->grid[(y+j) * ctx->w + (x+i)]) + n++; + } + } + + return n; +} + +/* Structure used internally to mineperturb(). */ +struct square { + int x, y, type, random; +}; +static int squarecmp(const void *av, const void *bv) +{ + const struct square *a = (const struct square *)av; + const struct square *b = (const struct square *)bv; + if (a->type < b->type) + return -1; + else if (a->type > b->type) + return +1; + else if (a->random < b->random) + return -1; + else if (a->random > b->random) + return +1; + else if (a->y < b->y) + return -1; + else if (a->y > b->y) + return +1; + else if (a->x < b->x) + return -1; + else if (a->x > b->x) + return +1; + return 0; +} + +/* + * 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, **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 + * possibly use. This list should be in preference order, which + * means + * + * - first, unknown squares on the boundary of known space + * - next, unknown squares beyond that boundary + * - as a very last resort, known squares, but not within one + * square of the starting position. + * + * Each of these sections needs to be shuffled independently. + * We do this by preparing list of all squares and then sorting + * it with a random secondary key. + */ + sqlist = snewn(ctx->w * ctx->h, struct square); + n = 0; + for (y = 0; y < ctx->h; y++) + for (x = 0; x < ctx->w; x++) { + /* + * If this square is too near the starting position, + * don't put it on the list at all. + */ + if (abs(y - ctx->sy) <= 1 && abs(x - ctx->sx) <= 1) + continue; + + /* + * If this square is in the input set, also don't put + * it on the list! + */ + 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; + sqlist[n].y = y; + + if (grid[y*ctx->w+x] != -2) { + sqlist[n].type = 3; /* known square */ + } else { + /* + * Unknown square. Examine everything around it and + * see if it borders on any known squares. If it + * does, it's class 1, otherwise it's 2. + */ + + sqlist[n].type = 2; + + for (dy = -1; dy <= +1; dy++) + for (dx = -1; dx <= +1; dx++) + if (x+dx >= 0 && x+dx < ctx->w && + y+dy >= 0 && y+dy < ctx->h && + grid[(y+dy)*ctx->w+(x+dx)] != -2) { + sqlist[n].type = 1; + break; + } + } + + /* + * Finally, a random number to cause qsort to + * shuffle within each group. + */ + sqlist[n].random = random_bits(ctx->rs, 31); + + n++; + } + + qsort(sqlist, n, sizeof(struct square), squarecmp); + + /* + * Now count up the number of full and empty squares in the set + * we've been provided. + */ + nfull = nempty = 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)]) + 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' + * empty squares, or `nempty' full squares; these will be + * swapped with the appropriate squares in the set to either + * fill or empty the set while keeping the same number of mines + * 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]) + toempty[ntoempty++] = sq; + else + tofill[ntofill++] = sq; + if (ntofill == nfull || ntoempty == nempty) + break; + } + + /* + * 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) { + 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 + * (a) put a mine in each of the empty squares in the set, and + * take one out of each square in `toempty' + * (b) take a mine out of each of the full squares in the set, + * and put one in each square in `tofill' + * depending on which one we've found enough squares to do. + * + * So we start by constructing our list of changes to return to + * the solver, so that it can update its data structures + * efficiently rather than having to rescan the whole grid. + */ + ret = snew(struct perturbations); + if (ntofill == nfull) { + todo = tofill; + 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); + for (i = 0; i < ntodo; i++) { + ret->changes[i].x = todo[i]->x; + ret->changes[i].y = todo[i]->y; + ret->changes[i].delta = dtodo; + } + /* now i == ntodo */ + 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 + * make, we now simply make them and return. + */ + for (i = 0; i < ret->n; i++) { + int delta; + + x = ret->changes[i].x; + y = ret->changes[i].y; + delta = ret->changes[i].delta; + + /* + * Check we're not trying to add an existing mine or remove + * an absent one. + */ + assert((delta < 0) ^ (ctx->grid[y*ctx->w+x] == 0)); + + /* + * Actually make the change. + */ + ctx->grid[y*ctx->w+x] = (delta > 0); + + /* + * Update any numbers already present in the grid. + */ + for (dy = -1; dy <= +1; dy++) + for (dx = -1; dx <= +1; dx++) + if (x+dx >= 0 && x+dx < ctx->w && + y+dy >= 0 && y+dy < ctx->h && + grid[(y+dy)*ctx->w+(x+dx)] != -2) { + if (dx == 0 && dy == 0) { + /* + * The square itself is marked as known in + * the grid. Mark it as a mine if it's a + * mine, or else work out its number. + */ + if (delta > 0) { + grid[y*ctx->w+x] = -1; + } else { + int dx2, dy2, minecount = 0; + for (dy2 = -1; dy2 <= +1; dy2++) + for (dx2 = -1; dx2 <= +1; dx2++) + if (x+dx2 >= 0 && x+dx2 < ctx->w && + y+dy2 >= 0 && y+dy2 < ctx->h && + ctx->grid[(y+dy2)*ctx->w+(x+dx2)]) + minecount++; + grid[y*ctx->w+x] = minecount; + } + } else { + if (grid[(y+dy)*ctx->w+(x+dx)] >= 0) + grid[(y+dy)*ctx->w+(x+dx)] += delta; + } + } + } + +#ifdef GENERATION_DIAGNOSTICS + { + int yy, xx; + printf("grid after perturbing:\n"); + for (yy = 0; yy < ctx->h; yy++) { + for (xx = 0; xx < ctx->w; xx++) { + int v = ctx->grid[yy*ctx->w+xx]; + if (yy == ctx->sy && xx == ctx->sx) { + assert(!v); + putchar('S'); + } else if (v) { + putchar('*'); + } else { + putchar('-'); + } + } + putchar('\n'); + } + printf("\n"); + } +#endif + + return ret; +} + +static char *minegen(int w, int h, int n, int x, int y, int unique, + random_state *rs) +{ + char *ret = snewn(w*h, char); + int success; + int ntries = 0; + + do { + success = FALSE; + ntries++; + + memset(ret, 0, w*h); + + /* + * Start by placing n mines, none of which is at x,y or within + * one square of it. + */ + { + int *tmp = snewn(w*h, int); + int i, j, k, nn; + + /* + * Write down the list of possible mine locations. + */ + k = 0; + for (i = 0; i < h; i++) + for (j = 0; j < w; j++) + if (abs(i - y) > 1 || abs(j - x) > 1) + tmp[k++] = i*w+j; + + /* + * Now pick n off the list at random. + */ + nn = n; + while (nn-- > 0) { + i = random_upto(rs, k); + ret[tmp[i]] = 1; + tmp[i] = tmp[--k]; + } + + sfree(tmp); + } + +#ifdef GENERATION_DIAGNOSTICS + { + int yy, xx; + printf("grid after initial generation:\n"); + for (yy = 0; yy < h; yy++) { + for (xx = 0; xx < w; xx++) { + int v = ret[yy*w+xx]; + if (yy == y && xx == x) { + assert(!v); + putchar('S'); + } else if (v) { + putchar('*'); + } else { + putchar('-'); + } + } + putchar('\n'); + } + printf("\n"); + } +#endif + + /* + * Now set up a results grid to run the solver in, and a + * context for the solver to open squares. Then run the solver + * repeatedly; if the number of perturb steps ever goes up or + * it ever returns -1, give up completely. + * + * We bypass this bit if we're not after a unique grid. + */ + if (unique) { + signed char *solvegrid = snewn(w*h, signed char); + struct minectx actx, *ctx = &actx; + int solveret, prevret = -2; + + ctx->grid = ret; + ctx->w = w; + ctx->h = h; + ctx->sx = x; + ctx->sy = y; + ctx->rs = rs; + ctx->allow_big_perturbs = (ntries > 100); + + while (1) { + memset(solvegrid, -2, w*h); + solvegrid[y*w+x] = mineopen(ctx, x, y); + assert(solvegrid[y*w+x] == 0); /* by deliberate arrangement */ + + solveret = + minesolve(w, h, n, solvegrid, mineopen, mineperturb, ctx, rs); + if (solveret < 0 || (prevret >= 0 && solveret >= prevret)) { + success = FALSE; + break; + } else if (solveret == 0) { + success = TRUE; + break; + } + } + + sfree(solvegrid); + } else { + success = TRUE; + } + + } while (!success); + + return ret; +} + +static char *describe_layout(char *grid, int area, int x, int y, + int obfuscate) +{ + char *ret, *p; + unsigned char *bmp; + int i; + + /* + * Set up the mine bitmap and obfuscate it. + */ + 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); + } + if (obfuscate) + 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,%s", x, y, + obfuscate ? "m" : "u"); /* '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); + + return ret; +} + +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; + +#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(w, h, n, x, y, unique, rs); + + if (game_desc) + *game_desc = describe_layout(grid, w * h, x, y, TRUE); + + return grid; +} + +static char *new_game_desc(const game_params *params, random_state *rs, + char **aux, int interactive) +{ + /* + * We generate the coordinates of an initial click even if they + * aren't actually used. This has the effect of harmonising the + * random number usage between interactive and batch use: if + * you use `mines --generate' with an explicit random seed, you + * should get exactly the same results as if you type the same + * random seed into the interactive game and click in the same + * initial location. (Of course you won't get the same grid if + * you click in a _different_ initial location, but there's + * nothing to be done about that.) + */ + int x = random_upto(rs, params->w); + int y = random_upto(rs, params->h); + + if (!interactive) { + /* + * For batch-generated grids, pre-open one square. + */ + 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, (char)(params->unique ? 'u' : 'a'), rsdesc); + sfree(rsdesc); + return desc; + } +} + +static char *validate_desc(const game_params *params, const char *desc) +{ + int wh = params->w * params->h; + int x, y; + + if (*desc == 'r') { + desc++; + 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++; + 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)) { + 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' for `masked' or `u' for `unmasked', if present */ + if (*desc == 'm' || *desc == 'u') + desc++; + /* now just check length of remainder */ + if (strlen(desc) != (wh+3)/4) + return "Game description is wrong length"; + } + + return NULL; +} + +static int open_square(game_state *state, int x, int y) +{ + int w = state->w, h = state->h; + int xx, yy, nmines, ncovered; + + 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, *privdesc; + state->layout->mines = new_mine_layout(w, h, state->layout->n, + x, y, state->layout->unique, + state->layout->rs, + &desc); + /* + * Find the trailing substring of the game description + * corresponding to just the mine layout; we will use this + * as our second `private' game ID for serialisation. + */ + privdesc = desc; + while (*privdesc && isdigit((unsigned char)*privdesc)) privdesc++; + if (*privdesc == ',') privdesc++; + while (*privdesc && isdigit((unsigned char)*privdesc)) privdesc++; + if (*privdesc == ',') privdesc++; + assert(*privdesc == 'm'); + midend_supersede_game_desc(state->layout->me, desc, privdesc); + 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 the + * mine that killed them, but not the rest (in case they + * want to Undo and carry on playing). + */ + state->dead = TRUE; + state->grid[y*w+x] = 65; + return -1; + } + + /* + * Otherwise, the player has opened a safe square. Mark it to-do. + */ + state->grid[y*w+x] = -10; /* `todo' value internal to this func */ + + /* + * Now go through the grid finding all `todo' values and + * opening them. Every time one of them turns out to have no + * neighbouring mines, we add all its unopened neighbours to + * the list as well. + * + * FIXME: We really ought to be able to do this better than + * using repeated N^2 scans of the grid. + */ + while (1) { + int done_something = FALSE; + + for (yy = 0; yy < h; yy++) + for (xx = 0; xx < w; xx++) + if (state->grid[yy*w+xx] == -10) { + int dx, dy, v; + + assert(!state->layout->mines[yy*w+xx]); + + v = 0; + + for (dx = -1; dx <= +1; dx++) + for (dy = -1; dy <= +1; dy++) + if (xx+dx >= 0 && xx+dx < state->w && + yy+dy >= 0 && yy+dy < state->h && + state->layout->mines[(yy+dy)*w+(xx+dx)]) + v++; + + state->grid[yy*w+xx] = v; + + if (v == 0) { + for (dx = -1; dx <= +1; dx++) + for (dy = -1; dy <= +1; dy++) + if (xx+dx >= 0 && xx+dx < state->w && + yy+dy >= 0 && yy+dy < state->h && + state->grid[(yy+dy)*w+(xx+dx)] == -2) + state->grid[(yy+dy)*w+(xx+dx)] = -10; + } + + done_something = TRUE; + } + + if (!done_something) + break; + } + + /* + * Finally, scan the grid and see if exactly as many squares + * are still covered as there are mines. If so, set the `won' + * flag and fill in mine markers on all covered squares. + */ + nmines = ncovered = 0; + for (yy = 0; yy < h; yy++) + for (xx = 0; xx < w; xx++) { + if (state->grid[yy*w+xx] < 0) + ncovered++; + if (state->layout->mines[yy*w+xx]) + nmines++; + } + assert(ncovered >= nmines); + if (ncovered == nmines) { + for (yy = 0; yy < h; yy++) + for (xx = 0; xx < w; xx++) { + if (state->grid[yy*w+xx] < 0) + state->grid[yy*w+xx] = -1; + } + state->won = TRUE; + } + + return 0; +} + +static game_state *new_game(midend *me, const game_params *params, + const char *desc) +{ + game_state *state = snew(game_state); + int i, wh, x, y, masked; + unsigned char *bmp; + + state->w = params->w; + state->h = params->h; + state->n = params->n; + state->dead = state->won = FALSE; + state->used_solve = FALSE; + + wh = state->w * state->h; + + state->layout = snew(struct mine_layout); + memset(state->layout, 0, sizeof(struct mine_layout)); + state->layout->refcount = 1; + + state->grid = snewn(wh, signed 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 { + state->layout->rs = NULL; + state->layout->me = NULL; + state->layout->mines = snewn(wh, char); + + if (*desc && isdigit((unsigned char)*desc)) { + 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 */ + } else { + x = y = -1; + } + + if (*desc == 'm') { + masked = TRUE; + desc++; + } else { + if (*desc == 'u') + desc++; + /* + * 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; + else + v = 0; + + bmp[i / 2] |= v << (4 * (1 - (i % 2))); + } + + if (masked) + obfuscate_bitmap(bmp, wh, TRUE); + + memset(state->layout->mines, 0, wh); + for (i = 0; i < wh; i++) { + if (bmp[i / 8] & (0x80 >> (i % 8))) + state->layout->mines[i] = 1; + } + + if (x >= 0 && y >= 0) + open_square(state, x, y); + sfree(bmp); + } + + return state; +} + +static game_state *dup_game(const game_state *state) +{ + game_state *ret = snew(game_state); + + ret->w = state->w; + ret->h = state->h; + ret->n = state->n; + ret->dead = state->dead; + ret->won = state->won; + ret->used_solve = state->used_solve; + ret->layout = state->layout; + ret->layout->refcount++; + ret->grid = snewn(ret->w * ret->h, signed char); + memcpy(ret->grid, state->grid, ret->w * ret->h); + + return ret; +} + +static void free_game(game_state *state) +{ + 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 char *solve_game(const game_state *state, const game_state *currstate, + const char *aux, char **error) +{ + if (!state->layout->mines) { + *error = "Game has not been started yet"; + return NULL; + } + + return dupstr("S"); +} + +static int game_can_format_as_text_now(const game_params *params) +{ + return TRUE; +} + +static char *game_text_format(const game_state *state) +{ + 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 validradius; + int flash_is_death; + int deaths, completed; + int cur_x, cur_y, cur_visible; +}; + +static game_ui *new_ui(const game_state *state) +{ + game_ui *ui = snew(game_ui); + ui->hx = ui->hy = -1; + ui->hradius = ui->validradius = 0; + ui->deaths = 0; + ui->completed = FALSE; + ui->flash_is_death = FALSE; /* *shrug* */ + ui->cur_x = ui->cur_y = ui->cur_visible = 0; + return ui; +} + +static void free_ui(game_ui *ui) +{ + sfree(ui); +} + +static char *encode_ui(const game_ui *ui) +{ + char buf[80]; + /* + * The deaths counter and completion status need preserving + * across a serialisation. + */ + sprintf(buf, "D%d", ui->deaths); + if (ui->completed) + strcat(buf, "C"); + return dupstr(buf); +} + +static void decode_ui(game_ui *ui, const char *encoding) +{ + int p= 0; + sscanf(encoding, "D%d%n", &ui->deaths, &p); + if (encoding[p] == 'C') + ui->completed = TRUE; +} + +static void game_changed_state(game_ui *ui, const game_state *oldstate, + const game_state *newstate) +{ + if (newstate->won) + ui->completed = TRUE; +} + +struct game_drawstate { + int w, h, started, tilesize, bg; + signed char *grid; + /* + * Items in this `grid' array have all the same values as in + * the game_state grid, and in addition: + * + * - -10 means the tile was drawn `specially' as a result of a + * flash, so it will always need redrawing. + * + * - -22 and -23 mean the tile is highlighted for a possible + * click. + */ + int cur_x, cur_y; /* -1, -1 for no cursor displayed. */ +}; + +static char *interpret_move(const game_state *from, game_ui *ui, + const game_drawstate *ds, + int x, int y, int button) +{ + int cx, cy; + char buf[256]; + + if (from->dead || from->won) + return NULL; /* no further moves permitted */ + + cx = FROMCOORD(x); + cy = FROMCOORD(y); + + if (IS_CURSOR_MOVE(button)) { + move_cursor(button, &ui->cur_x, &ui->cur_y, from->w, from->h, 0); + ui->cur_visible = 1; + return ""; + } + if (IS_CURSOR_SELECT(button)) { + int v = from->grid[ui->cur_y * from->w + ui->cur_x]; + + if (!ui->cur_visible) { + ui->cur_visible = 1; + return ""; + } + if (button == CURSOR_SELECT2) { + /* As for RIGHT_BUTTON; only works on covered square. */ + if (v != -2 && v != -1) + return NULL; + sprintf(buf, "F%d,%d", ui->cur_x, ui->cur_y); + return dupstr(buf); + } + /* Otherwise, treat as LEFT_BUTTON, for a single square. */ + if (v == -2 || v == -3) { + if (from->layout->mines && + from->layout->mines[ui->cur_y * from->w + ui->cur_x]) + ui->deaths++; + + sprintf(buf, "O%d,%d", ui->cur_x, ui->cur_y); + return dupstr(buf); + } + cx = ui->cur_x; cy = ui->cur_y; + ui->validradius = 1; + goto uncover; + } + + if (button == LEFT_BUTTON || button == LEFT_DRAG || + button == MIDDLE_BUTTON || button == MIDDLE_DRAG) { + if (cx < 0 || cx >= from->w || cy < 0 || cy >= from->h) + return NULL; + + /* + * Mouse-downs and mouse-drags just cause highlighting + * updates. + */ + ui->hx = cx; + ui->hy = cy; + ui->hradius = (from->grid[cy*from->w+cx] >= 0 ? 1 : 0); + if (button == LEFT_BUTTON) + ui->validradius = ui->hradius; + else if (button == MIDDLE_BUTTON) + ui->validradius = 1; + ui->cur_visible = 0; + return ""; + } + + if (button == RIGHT_BUTTON) { + if (cx < 0 || cx >= from->w || cy < 0 || cy >= from->h) + return NULL; + + /* + * Right-clicking only works on a covered square, and it + * toggles between -1 (marked as mine) and -2 (not marked + * as mine). + * + * FIXME: question marks. + */ + if (from->grid[cy * from->w + cx] != -2 && + from->grid[cy * from->w + cx] != -1) + return NULL; + + sprintf(buf, "F%d,%d", cx, cy); + return dupstr(buf); + } + + if (button == LEFT_RELEASE || button == MIDDLE_RELEASE) { + ui->hx = ui->hy = -1; + ui->hradius = 0; + + /* + * At this stage we must never return NULL: we have adjusted + * the ui, so at worst we return "". + */ + if (cx < 0 || cx >= from->w || cy < 0 || cy >= from->h) + return ""; + + /* + * Left-clicking on a covered square opens a tile. Not + * permitted if the tile is marked as a mine, for safety. + * (Unmark it and _then_ open it.) + */ + if (button == LEFT_RELEASE && + (from->grid[cy * from->w + cx] == -2 || + from->grid[cy * from->w + cx] == -3) && + ui->validradius == 0) { + /* Check if you've killed yourself. */ + if (from->layout->mines && from->layout->mines[cy * from->w + cx]) + ui->deaths++; + + sprintf(buf, "O%d,%d", cx, cy); + return dupstr(buf); + } + goto uncover; + } + return NULL; + +uncover: + { + /* + * 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 && ui->validradius == 1) { + int dy, dx, n; + + /* Count mine markers. */ + n = 0; + for (dy = -1; dy <= +1; dy++) + for (dx = -1; dx <= +1; dx++) + if (cx+dx >= 0 && cx+dx < from->w && + cy+dy >= 0 && cy+dy < from->h) { + if (from->grid[(cy+dy)*from->w+(cx+dx)] == -1) + n++; + } + + if (n == from->grid[cy * from->w + cx]) { + + /* + * Now see if any of the squares we're clearing + * contains a mine (which will happen iff you've + * incorrectly marked the mines around the clicked + * square). If so, we open _just_ those squares, to + * reveal as little additional information as we + * can. + */ + char *p = buf; + char *sep = ""; + + for (dy = -1; dy <= +1; dy++) + for (dx = -1; dx <= +1; dx++) + if (cx+dx >= 0 && cx+dx < from->w && + cy+dy >= 0 && cy+dy < from->h) { + if (from->grid[(cy+dy)*from->w+(cx+dx)] != -1 && + from->layout->mines && + from->layout->mines[(cy+dy)*from->w+(cx+dx)]) { + p += sprintf(p, "%sO%d,%d", sep, cx+dx, cy+dy); + sep = ";"; + } + } + + if (p > buf) { + ui->deaths++; + } else { + sprintf(buf, "C%d,%d", cx, cy); + } + + return dupstr(buf); + } + } + + return ""; + } +} + +static game_state *execute_move(const game_state *from, const char *move) +{ + int cy, cx; + game_state *ret; + + if (!strcmp(move, "S")) { + int yy, xx; + + ret = dup_game(from); + if (!ret->dead) { + /* + * If the player is still alive at the moment of pressing + * Solve, expose the entire grid as if it were a completed + * solution. + */ + 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; + } + } + } else { + /* + * If the player pressed Solve _after dying_, show a full + * corrections grid in the style of standard Minesweeper. + * Players who don't like Mines's behaviour on death of + * only showing the mine that killed you (so that in case + * of a typo you can undo and carry on without the rest of + * the grid being spoiled) can use this to get the display + * that ordinary Minesweeper would have given them. + */ + for (yy = 0; yy < ret->h; yy++) + for (xx = 0; xx < ret->w; xx++) { + int pos = yy*ret->w+xx; + if ((ret->grid[pos] == -2 || ret->grid[pos] == -3) && + ret->layout->mines[pos]) { + ret->grid[pos] = 64; + } else if (ret->grid[pos] == -1 && + !ret->layout->mines[pos]) { + ret->grid[pos] = 66; + } + } + } + ret->used_solve = TRUE; + + return ret; + } else { + ret = dup_game(from); + + while (*move) { + if (move[0] == 'F' && + sscanf(move+1, "%d,%d", &cx, &cy) == 2 && + cx >= 0 && cx < from->w && cy >= 0 && cy < from->h) { + ret->grid[cy * from->w + cx] ^= (-2 ^ -1); + } else if (move[0] == 'O' && + sscanf(move+1, "%d,%d", &cx, &cy) == 2 && + cx >= 0 && cx < from->w && cy >= 0 && cy < from->h) { + open_square(ret, cx, cy); + } else if (move[0] == 'C' && + sscanf(move+1, "%d,%d", &cx, &cy) == 2 && + cx >= 0 && cx < from->w && cy >= 0 && cy < from->h) { + int dx, dy; + + for (dy = -1; dy <= +1; dy++) + for (dx = -1; dx <= +1; dx++) + if (cx+dx >= 0 && cx+dx < ret->w && + cy+dy >= 0 && cy+dy < ret->h && + (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); + } else { + free_game(ret); + return NULL; + } + + while (*move && *move != ';') move++; + if (*move) move++; + } + + return ret; + } +} + +/* ---------------------------------------------------------------------- + * Drawing routines. + */ + +static void game_compute_size(const game_params *params, int tilesize, + int *x, int *y) +{ + /* Ick: fake up `ds->tilesize' for macro expansion purposes */ + struct { int tilesize; } ads, *ds = &ads; + ads.tilesize = tilesize; + + *x = BORDER * 2 + TILE_SIZE * params->w; + *y = BORDER * 2 + TILE_SIZE * params->h; +} + +static void game_set_size(drawing *dr, game_drawstate *ds, + const game_params *params, int tilesize) +{ + ds->tilesize = tilesize; +} + +static float *game_colours(frontend *fe, int *ncolours) +{ + float *ret = snewn(3 * NCOLOURS, float); + + frontend_default_colour(fe, &ret[COL_BACKGROUND * 3]); + + ret[COL_BACKGROUND2 * 3 + 0] = ret[COL_BACKGROUND * 3 + 0] * 19.0F / 20.0F; + ret[COL_BACKGROUND2 * 3 + 1] = ret[COL_BACKGROUND * 3 + 1] * 19.0F / 20.0F; + ret[COL_BACKGROUND2 * 3 + 2] = ret[COL_BACKGROUND * 3 + 2] * 19.0F / 20.0F; + + ret[COL_1 * 3 + 0] = 0.0F; + ret[COL_1 * 3 + 1] = 0.0F; + ret[COL_1 * 3 + 2] = 1.0F; + + ret[COL_2 * 3 + 0] = 0.0F; + ret[COL_2 * 3 + 1] = 0.5F; + ret[COL_2 * 3 + 2] = 0.0F; + + ret[COL_3 * 3 + 0] = 1.0F; + ret[COL_3 * 3 + 1] = 0.0F; + ret[COL_3 * 3 + 2] = 0.0F; + + ret[COL_4 * 3 + 0] = 0.0F; + ret[COL_4 * 3 + 1] = 0.0F; + ret[COL_4 * 3 + 2] = 0.5F; + + ret[COL_5 * 3 + 0] = 0.5F; + ret[COL_5 * 3 + 1] = 0.0F; + ret[COL_5 * 3 + 2] = 0.0F; + + ret[COL_6 * 3 + 0] = 0.0F; + ret[COL_6 * 3 + 1] = 0.5F; + ret[COL_6 * 3 + 2] = 0.5F; + + ret[COL_7 * 3 + 0] = 0.0F; + ret[COL_7 * 3 + 1] = 0.0F; + ret[COL_7 * 3 + 2] = 0.0F; + + ret[COL_8 * 3 + 0] = 0.5F; + ret[COL_8 * 3 + 1] = 0.5F; + ret[COL_8 * 3 + 2] = 0.5F; + + ret[COL_MINE * 3 + 0] = 0.0F; + ret[COL_MINE * 3 + 1] = 0.0F; + ret[COL_MINE * 3 + 2] = 0.0F; + + ret[COL_BANG * 3 + 0] = 1.0F; + ret[COL_BANG * 3 + 1] = 0.0F; + ret[COL_BANG * 3 + 2] = 0.0F; + + ret[COL_CROSS * 3 + 0] = 1.0F; + ret[COL_CROSS * 3 + 1] = 0.0F; + ret[COL_CROSS * 3 + 2] = 0.0F; + + ret[COL_FLAG * 3 + 0] = 1.0F; + ret[COL_FLAG * 3 + 1] = 0.0F; + ret[COL_FLAG * 3 + 2] = 0.0F; + + ret[COL_FLAGBASE * 3 + 0] = 0.0F; + ret[COL_FLAGBASE * 3 + 1] = 0.0F; + ret[COL_FLAGBASE * 3 + 2] = 0.0F; + + ret[COL_QUERY * 3 + 0] = 0.0F; + ret[COL_QUERY * 3 + 1] = 0.0F; + ret[COL_QUERY * 3 + 2] = 0.0F; + + ret[COL_HIGHLIGHT * 3 + 0] = 1.0F; + ret[COL_HIGHLIGHT * 3 + 1] = 1.0F; + ret[COL_HIGHLIGHT * 3 + 2] = 1.0F; + + ret[COL_LOWLIGHT * 3 + 0] = ret[COL_BACKGROUND * 3 + 0] * 2.0F / 3.0F; + ret[COL_LOWLIGHT * 3 + 1] = ret[COL_BACKGROUND * 3 + 1] * 2.0F / 3.0F; + ret[COL_LOWLIGHT * 3 + 2] = ret[COL_BACKGROUND * 3 + 2] * 2.0F / 3.0F; + + ret[COL_WRONGNUMBER * 3 + 0] = 1.0F; + ret[COL_WRONGNUMBER * 3 + 1] = 0.6F; + ret[COL_WRONGNUMBER * 3 + 2] = 0.6F; + + /* Red tinge to a light colour, for the cursor. */ + ret[COL_CURSOR * 3 + 0] = ret[COL_HIGHLIGHT * 3 + 0]; + ret[COL_CURSOR * 3 + 1] = ret[COL_HIGHLIGHT * 3 + 0] / 2.0F; + ret[COL_CURSOR * 3 + 2] = ret[COL_HIGHLIGHT * 3 + 0] / 2.0F; + + *ncolours = NCOLOURS; + return ret; +} + +static game_drawstate *game_new_drawstate(drawing *dr, const game_state *state) +{ + struct game_drawstate *ds = snew(struct game_drawstate); + + ds->w = state->w; + ds->h = state->h; + ds->started = FALSE; + ds->tilesize = 0; /* not decided yet */ + ds->grid = snewn(ds->w * ds->h, signed char); + ds->bg = -1; + ds->cur_x = ds->cur_y = -1; + + memset(ds->grid, -99, ds->w * ds->h); + + return ds; +} + +static void game_free_drawstate(drawing *dr, game_drawstate *ds) +{ + sfree(ds->grid); + sfree(ds); +} + +static void draw_tile(drawing *dr, game_drawstate *ds, + int x, int y, int v, int bg) +{ + if (v < 0) { + int coords[12]; + int hl = 0; + + if (v == -22 || v == -23) { + v += 20; + + /* + * Omit the highlights in this case. + */ + draw_rect(dr, x, y, TILE_SIZE, TILE_SIZE, + bg == COL_BACKGROUND ? COL_BACKGROUND2 : bg); + draw_line(dr, x, y, x + TILE_SIZE - 1, y, COL_LOWLIGHT); + draw_line(dr, x, y, x, y + TILE_SIZE - 1, COL_LOWLIGHT); + } else { + /* + * Draw highlights to indicate the square is covered. + */ + coords[0] = x + TILE_SIZE - 1; + coords[1] = y + TILE_SIZE - 1; + coords[2] = x + TILE_SIZE - 1; + coords[3] = y; + coords[4] = x; + coords[5] = y + TILE_SIZE - 1; + draw_polygon(dr, coords, 3, COL_LOWLIGHT ^ hl, COL_LOWLIGHT ^ hl); + + coords[0] = x; + coords[1] = y; + draw_polygon(dr, coords, 3, COL_HIGHLIGHT ^ hl, + COL_HIGHLIGHT ^ hl); + + draw_rect(dr, x + HIGHLIGHT_WIDTH, y + HIGHLIGHT_WIDTH, + TILE_SIZE - 2*HIGHLIGHT_WIDTH, TILE_SIZE - 2*HIGHLIGHT_WIDTH, + bg); + } + + if (v == -1) { + /* + * Draw a flag. + */ +#define SETCOORD(n, dx, dy) do { \ + coords[(n)*2+0] = x + (int)(TILE_SIZE * (dx)); \ + coords[(n)*2+1] = y + (int)(TILE_SIZE * (dy)); \ +} while (0) + SETCOORD(0, 0.6F, 0.35F); + SETCOORD(1, 0.6F, 0.7F); + SETCOORD(2, 0.8F, 0.8F); + SETCOORD(3, 0.25F, 0.8F); + SETCOORD(4, 0.55F, 0.7F); + SETCOORD(5, 0.55F, 0.35F); + draw_polygon(dr, coords, 6, COL_FLAGBASE, COL_FLAGBASE); + + SETCOORD(0, 0.6F, 0.2F); + SETCOORD(1, 0.6F, 0.5F); + SETCOORD(2, 0.2F, 0.35F); + draw_polygon(dr, coords, 3, COL_FLAG, COL_FLAG); +#undef SETCOORD + + } else if (v == -3) { + /* + * Draw a question mark. + */ + draw_text(dr, x + TILE_SIZE / 2, y + TILE_SIZE / 2, + FONT_VARIABLE, TILE_SIZE * 6 / 8, + ALIGN_VCENTRE | ALIGN_HCENTRE, + COL_QUERY, "?"); + } + } else { + /* + * Clear the square to the background colour, and draw thin + * grid lines along the top and left. + * + * Exception is that for value 65 (mine we've just trodden + * on), we clear the square to COL_BANG. + */ + if (v & 32) { + bg = COL_WRONGNUMBER; + v &= ~32; + } + draw_rect(dr, x, y, TILE_SIZE, TILE_SIZE, + (v == 65 ? COL_BANG : + bg == COL_BACKGROUND ? COL_BACKGROUND2 : bg)); + draw_line(dr, x, y, x + TILE_SIZE - 1, y, COL_LOWLIGHT); + draw_line(dr, x, y, x, y + TILE_SIZE - 1, COL_LOWLIGHT); + + if (v > 0 && v <= 8) { + /* + * Mark a number. + */ + char str[2]; + str[0] = v + '0'; + str[1] = '\0'; + draw_text(dr, x + TILE_SIZE / 2, y + TILE_SIZE / 2, + FONT_VARIABLE, TILE_SIZE * 7 / 8, + ALIGN_VCENTRE | ALIGN_HCENTRE, + (COL_1 - 1) + v, str); + + } else if (v >= 64) { + /* + * Mark a mine. + */ + { + int cx = x + TILE_SIZE / 2; + int cy = y + TILE_SIZE / 2; + int r = TILE_SIZE / 2 - 3; + + draw_circle(dr, cx, cy, 5*r/6, COL_MINE, COL_MINE); + draw_rect(dr, cx - r/6, cy - r, 2*(r/6)+1, 2*r+1, COL_MINE); + draw_rect(dr, cx - r, cy - r/6, 2*r+1, 2*(r/6)+1, COL_MINE); + draw_rect(dr, cx-r/3, cy-r/3, r/3, r/4, COL_HIGHLIGHT); + } + + if (v == 66) { + /* + * Cross through the mine. + */ + int dx; + for (dx = -1; dx <= +1; dx++) { + draw_line(dr, x + 3 + dx, y + 2, + x + TILE_SIZE - 3 + dx, + y + TILE_SIZE - 2, COL_CROSS); + draw_line(dr, x + TILE_SIZE - 3 + dx, y + 2, + x + 3 + dx, y + TILE_SIZE - 2, + COL_CROSS); + } + } + } + } + + draw_update(dr, x, y, TILE_SIZE, TILE_SIZE); +} + +static void game_redraw(drawing *dr, game_drawstate *ds, + const game_state *oldstate, const game_state *state, + int dir, const game_ui *ui, + float animtime, float flashtime) +{ + int x, y; + int mines, markers, bg; + int cx = -1, cy = -1, cmoved; + + if (flashtime) { + int frame = (int)(flashtime / FLASH_FRAME); + if (frame % 2) + bg = (ui->flash_is_death ? COL_BACKGROUND : COL_LOWLIGHT); + else + bg = (ui->flash_is_death ? COL_BANG : COL_HIGHLIGHT); + } else + bg = COL_BACKGROUND; + + if (!ds->started) { + int coords[10]; + + draw_rect(dr, 0, 0, + TILE_SIZE * state->w + 2 * BORDER, + TILE_SIZE * state->h + 2 * BORDER, COL_BACKGROUND); + draw_update(dr, 0, 0, + TILE_SIZE * state->w + 2 * BORDER, + TILE_SIZE * state->h + 2 * BORDER); + + /* + * Recessed area containing the whole puzzle. + */ + coords[0] = COORD(state->w) + OUTER_HIGHLIGHT_WIDTH - 1; + coords[1] = COORD(state->h) + OUTER_HIGHLIGHT_WIDTH - 1; + coords[2] = COORD(state->w) + OUTER_HIGHLIGHT_WIDTH - 1; + coords[3] = COORD(0) - OUTER_HIGHLIGHT_WIDTH; + coords[4] = coords[2] - TILE_SIZE; + coords[5] = coords[3] + TILE_SIZE; + coords[8] = COORD(0) - OUTER_HIGHLIGHT_WIDTH; + coords[9] = COORD(state->h) + OUTER_HIGHLIGHT_WIDTH - 1; + coords[6] = coords[8] + TILE_SIZE; + coords[7] = coords[9] - TILE_SIZE; + draw_polygon(dr, coords, 5, COL_HIGHLIGHT, COL_HIGHLIGHT); + + coords[1] = COORD(0) - OUTER_HIGHLIGHT_WIDTH; + coords[0] = COORD(0) - OUTER_HIGHLIGHT_WIDTH; + draw_polygon(dr, coords, 5, COL_LOWLIGHT, COL_LOWLIGHT); + + ds->started = TRUE; + } + + if (ui->cur_visible) cx = ui->cur_x; + if (ui->cur_visible) cy = ui->cur_y; + cmoved = (cx != ds->cur_x || cy != ds->cur_y); + + /* + * Now draw the tiles. Also in this loop, count up the number + * of mines and mine markers. + */ + mines = markers = 0; + for (y = 0; y < ds->h; y++) + for (x = 0; x < ds->w; x++) { + int v = state->grid[y*ds->w+x], cc = 0; + + if (v == -1) + markers++; + if (state->layout->mines && state->layout->mines[y*ds->w+x]) + mines++; + + if (v >= 0 && v <= 8) { + /* + * Count up the flags around this tile, and if + * there are too _many_, highlight the tile. + */ + int dx, dy, flags = 0; + + for (dy = -1; dy <= +1; dy++) + for (dx = -1; dx <= +1; dx++) { + int nx = x+dx, ny = y+dy; + if (nx >= 0 && nx < ds->w && + ny >= 0 && ny < ds->h && + state->grid[ny*ds->w+nx] == -1) + flags++; + } + + if (flags > v) + v |= 32; + } + + if ((v == -2 || v == -3) && + (abs(x-ui->hx) <= ui->hradius && abs(y-ui->hy) <= ui->hradius)) + v -= 20; + + if (cmoved && /* if cursor has moved, force redraw of curr and prev pos */ + ((x == cx && y == cy) || (x == ds->cur_x && y == ds->cur_y))) + cc = 1; + + if (ds->grid[y*ds->w+x] != v || bg != ds->bg || cc) { + draw_tile(dr, ds, COORD(x), COORD(y), v, + (x == cx && y == cy) ? COL_CURSOR : bg); + ds->grid[y*ds->w+x] = v; + } + } + ds->bg = bg; + ds->cur_x = cx; ds->cur_y = cy; + + if (!state->layout->mines) + mines = state->layout->n; + + /* + * Update the status bar. + */ + { + char statusbar[512]; + if (state->dead) { + sprintf(statusbar, "DEAD!"); + } else if (state->won) { + if (state->used_solve) + sprintf(statusbar, "Auto-solved."); + else + sprintf(statusbar, "COMPLETED!"); + } else { + sprintf(statusbar, "Marked: %d / %d", markers, mines); + } + if (ui->deaths) + sprintf(statusbar + strlen(statusbar), + " Deaths: %d", ui->deaths); + status_bar(dr, statusbar); + } +} + +static float game_anim_length(const game_state *oldstate, + const game_state *newstate, int dir, game_ui *ui) +{ + return 0.0F; +} + +static float game_flash_length(const game_state *oldstate, + const 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 3 * FLASH_FRAME; + } + if (newstate->won) { + ui->flash_is_death = FALSE; + return 2 * FLASH_FRAME; + } + } + return 0.0F; +} + +static int game_status(const game_state *state) +{ + /* + * We report the game as lost only if the player has used the + * Solve function to reveal all the mines. Otherwise, we assume + * they'll undo and continue play. + */ + return state->won ? (state->used_solve ? -1 : +1) : 0; +} + +static int game_timing_state(const game_state *state, game_ui *ui) +{ + if (state->dead || state->won || ui->completed || !state->layout->mines) + return FALSE; + return TRUE; +} + +static void game_print_size(const game_params *params, float *x, float *y) +{ +} + +static void game_print(drawing *dr, const game_state *state, int tilesize) +{ +} + +#ifdef COMBINED +#define thegame mines +#endif + +const struct game thegame = { + "Mines", "games.mines", "mines", + default_params, + game_fetch_preset, NULL, + decode_params, + encode_params, + free_params, + dup_params, + TRUE, game_configure, custom_params, + validate_params, + new_game_desc, + validate_desc, + new_game, + dup_game, + free_game, + TRUE, solve_game, + TRUE, game_can_format_as_text_now, game_text_format, + new_ui, + free_ui, + encode_ui, + decode_ui, + game_changed_state, + interpret_move, + execute_move, + PREFERRED_TILE_SIZE, game_compute_size, game_set_size, + game_colours, + game_new_drawstate, + game_free_drawstate, + game_redraw, + game_anim_length, + game_flash_length, + game_status, + FALSE, FALSE, game_print_size, game_print, + TRUE, /* wants_statusbar */ + TRUE, game_timing_state, + BUTTON_BEATS(LEFT_BUTTON, RIGHT_BUTTON) | REQUIRE_RBUTTON, +}; + +#ifdef STANDALONE_OBFUSCATOR + +/* + * Vaguely useful stand-alone program which translates between + * obfuscated and clear Mines game descriptions. Pass in a game + * description on the command line, and if it's clear it will be + * obfuscated and vice versa. The output text should also be a + * valid game ID describing the same game. Like this: + * + * $ ./mineobfusc 9x9:4,4,mb071b49fbd1cb6a0d5868 + * 9x9:4,4,004000007c00010022080 + * $ ./mineobfusc 9x9:4,4,004000007c00010022080 + * 9x9:4,4,mb071b49fbd1cb6a0d5868 + */ + +int main(int argc, char **argv) +{ + game_params *p; + game_state *s; + char *id = NULL, *desc, *err; + int y, x; + + while (--argc > 0) { + char *p = *++argv; + if (*p == '-') { + fprintf(stderr, "%s: unrecognised option `%s'\n", argv[0], p); + return 1; + } else { + id = p; + } + } + + if (!id) { + fprintf(stderr, "usage: %s \n", argv[0]); + return 1; + } + + desc = strchr(id, ':'); + if (!desc) { + fprintf(stderr, "%s: game id expects a colon in it\n", argv[0]); + return 1; + } + *desc++ = '\0'; + + p = default_params(); + decode_params(p, id); + err = validate_desc(p, desc); + if (err) { + fprintf(stderr, "%s: %s\n", argv[0], err); + return 1; + } + s = new_game(NULL, p, desc); + + x = atoi(desc); + while (*desc && *desc != ',') desc++; + if (*desc) desc++; + y = atoi(desc); + while (*desc && *desc != ',') desc++; + if (*desc) desc++; + + printf("%s:%s\n", id, describe_layout(s->layout->mines, + p->w * p->h, + x, y, + (*desc != 'm'))); + + return 0; +} + +#endif + +/* vim: set shiftwidth=4 tabstop=8: */ -- cgit v1.2.3