ref: 0186d78da9e83103eb80b3814d4de8031f29232f
dir: /mines.c/
/* * 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 <stdio.h> #include <stdlib.h> #include <string.h> #include <assert.h> #include <ctype.h> #include <limits.h> #include <math.h> #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 ? TILE_SIZE / 10 : 1) #define OUTER_HIGHLIGHT_WIDTH (BORDER / 10 ? BORDER / 10 : 1) #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; bool 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; bool *mines; /* * If we haven't yet actually generated the mine layout, here's * all the data we will need to do so. */ int n; bool unique; random_state *rs; midend *me; /* to give back the new game desc */ }; struct game_state { int w, h, n; bool dead, won, 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 bool 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 { if (params->h > 0 && params->w > 0 && params->w <= INT_MAX / params->h) 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, bool 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].u.string.sval = dupstr(buf); ret[1].name = "Height"; ret[1].type = C_STRING; sprintf(buf, "%d", params->h); ret[1].u.string.sval = dupstr(buf); ret[2].name = "Mines"; ret[2].type = C_STRING; sprintf(buf, "%d", params->n); ret[2].u.string.sval = dupstr(buf); ret[3].name = "Ensure solubility"; ret[3].type = C_BOOLEAN; ret[3].u.boolean.bval = params->unique; ret[4].name = NULL; ret[4].type = C_END; return ret; } static game_params *custom_params(const config_item *cfg) { game_params *ret = snew(game_params); ret->w = atoi(cfg[0].u.string.sval); ret->h = atoi(cfg[1].u.string.sval); ret->n = atoi(cfg[2].u.string.sval); if (strchr(cfg[2].u.string.sval, '%')) ret->n = ret->n * (ret->w * ret->h) / 100; ret->unique = cfg[3].u.boolean.bval; return ret; } static const char *validate_params(const game_params *params, bool 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 that 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->w < 1 || params->h < 1) return "Width and height must both be at least one"; if (params->w > SHRT_MAX || params->h > SHRT_MAX) return "Neither width nor height may be unreasonably large"; /* * We use random_upto() to place mines, and its maximum limit is 2^28-1. */ #if (1<<28)-1 < INT_MAX if (params->w > ((1<<28)-1) / params->h) #else if (params->w > INT_MAX / params->h) #endif return "Width times height must not be unreasonably large"; if (params->n < 0) return "Mine count may not be negative"; 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; bool 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, bool 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); assert(SHRT_MIN <= x && x <= SHRT_MAX); s->x = x; assert(SHRT_MIN <= y && y <= SHRT_MAX); 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. */ assert(SHRT_MIN <= xx && xx <= SHRT_MAX); stmp.x = xx; assert(SHRT_MIN <= yy && yy <= SHRT_MAX); 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, bool 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) { bool 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, cursor; bool setused[10]; /* * 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 true if 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 * true if that set is disjoint from anything else * currently in `setused', or to false 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 true entry, reset it to false, 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) { bool 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) { bool 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++] = false; } 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 { bool *grid; int w, h; int sx, sy; bool 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 bool *minegen(int w, int h, int n, int x, int y, bool unique, random_state *rs) { bool *ret = snewn(w*h, bool); bool 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]] = true; 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(bool *grid, int area, int x, int y, bool 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 bool *new_mine_layout(int w, int h, int n, int x, int y, bool unique, random_state *rs, char **game_desc) { bool *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, bool 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. */ bool *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 const 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"; if (atoi(desc) > wh - 9) return "Too many mines for grid size"; 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) { bool 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; } /* If the player has already lost, don't let them win as well. */ if (state->dead) return 0; /* * 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; bool 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, bool); 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 * sizeof(bool)); for (i = 0; i < wh; i++) { if (bmp[i / 8] & (0x80 >> (i % 8))) state->layout->mines[i] = true; } 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, const char **error) { if (!state->layout->mines) { *error = "Game has not been started yet"; return NULL; } return dupstr("S"); } static bool 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; bool flash_is_death; int deaths; bool completed; int cur_x, cur_y; bool 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 = 0; ui->cur_visible = false; 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; } static const char *current_key_label(const game_ui *ui, const game_state *state, int button) { int cx = ui->cur_x, cy = ui->cur_y; int v = state->grid[cy * state->w + cx]; if (state->dead || state->won || !ui->cur_visible) return ""; if (button == CURSOR_SELECT2) { if (v == -2) return "Mark"; if (v == -1) return "Unmark"; return ""; } if (button == CURSOR_SELECT) { int dy, dx, n = 0; if (v == -2 || v == -3) return "Uncover"; if (v == 0) return ""; /* Count mine markers. */ for (dy = -1; dy <= +1; dy++) for (dx = -1; dx <= +1; dx++) if (cx+dx >= 0 && cx+dx < state->w && cy+dy >= 0 && cy+dy < state->h) { if (state->grid[(cy+dy)*state->w+(cx+dx)] == -1) n++; } if (n == v) return "Clear"; } return ""; } struct game_drawstate { int w, h, tilesize, bg; bool started; 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, false); ui->cur_visible = true; return UI_UPDATE; } if (IS_CURSOR_SELECT(button)) { int v = from->grid[ui->cur_y * from->w + ui->cur_x]; if (!ui->cur_visible) { ui->cur_visible = true; return UI_UPDATE; } 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 = false; return UI_UPDATE; } 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 UI_UPDATE. */ if (cx < 0 || cx >= from->w || cy < 0 || cy >= from->h) return UI_UPDATE; /* * 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; const 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 UI_UPDATE; } } 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; if (!from->layout->mines) return NULL; /* Game not started. */ 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 { /* Dead players should stop trying to move. */ if (from->dead) return NULL; 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] == -1 || ret->grid[cy * from->w + cx] == -2)) { 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, closed, bg; int cx = -1, cy = -1; bool 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]; /* * 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, mine markers, and closed squares. */ mines = markers = closed = 0; for (y = 0; y < ds->h; y++) for (x = 0; x < ds->w; x++) { int v = state->grid[y*ds->w+x]; bool cc = false; if (v < 0) closed++; 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 = true; 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 { int safe_closed = closed - mines; sprintf(statusbar, "Marked: %d / %d", markers, mines); if (safe_closed > 0 && safe_closed <= 9) { /* * In the situation where there's a very small number * of _non_-mine squares left unopened, it's helpful * to mention that number in the status line, to save * the player from having to count it up * painstakingly. This is particularly important if * the player has turned up the mine density to the * point where game generation resorts to its weird * pathological fallback of a very dense mine area * with a clearing in the middle, because that often * leads to a deduction you can only make by knowing * that there is (say) exactly one non-mine square to * find, and it's a real pain to have to count up two * large numbers of squares and subtract them to get * that value of 1. * * The threshold value of 8 for displaying this * information is because that's the largest number of * non-mine squares that might conceivably fit around * a single central square, and the most likely way to * _use_ this information is to observe that if all * the remaining safe squares are adjacent to _this_ * square then everything else can be immediately * flagged as a mine. */ if (safe_closed == 1) { sprintf(statusbar + strlen(statusbar), " (1 safe square remains)"); } else { sprintf(statusbar + strlen(statusbar), " (%d safe squares remain)", safe_closed); } } } 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 void game_get_cursor_location(const game_ui *ui, const game_drawstate *ds, const game_state *state, const game_params *params, int *x, int *y, int *w, int *h) { if(ui->cur_visible) { *x = COORD(ui->cur_x); *y = COORD(ui->cur_y); *w = *h = TILE_SIZE; } } 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 bool game_timing_state(const game_state *state, game_ui *ui) { if (state->dead || state->won || ui->completed || !state->layout->mines) return false; return true; } #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, NULL, /* game_request_keys */ game_changed_state, current_key_label, 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_get_cursor_location, game_status, false, false, NULL, NULL, /* print_size, 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; const char *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 <game_id>\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: */