2 * mines.c: Minesweeper clone with sophisticated grid generation.
6 * - think about configurably supporting question marks. Once,
7 * that is, we've thought about configurability in general!
21 COL_BACKGROUND, COL_BACKGROUND2,
22 COL_1, COL_2, COL_3, COL_4, COL_5, COL_6, COL_7, COL_8,
23 COL_MINE, COL_BANG, COL_CROSS, COL_FLAG, COL_FLAGBASE, COL_QUERY,
24 COL_HIGHLIGHT, COL_LOWLIGHT,
30 #define PREFERRED_TILE_SIZE 20
31 #define TILE_SIZE (ds->tilesize)
35 #define BORDER (TILE_SIZE * 3 / 2)
37 #define HIGHLIGHT_WIDTH (TILE_SIZE / 10)
38 #define OUTER_HIGHLIGHT_WIDTH (BORDER / 10)
39 #define COORD(x) ( (x) * TILE_SIZE + BORDER )
40 #define FROMCOORD(x) ( ((x) - BORDER + TILE_SIZE) / TILE_SIZE - 1 )
42 #define FLASH_FRAME 0.13F
51 * This structure is shared between all the game_states for a
52 * given instance of the puzzle, so we reference-count it.
57 * If we haven't yet actually generated the mine layout, here's
58 * all the data we will need to do so.
62 midend *me; /* to give back the new game desc */
66 int w, h, n, dead, won;
68 struct mine_layout *layout; /* real mine positions */
69 signed char *grid; /* player knowledge */
71 * Each item in the `grid' array is one of the following values:
73 * - 0 to 8 mean the square is open and has a surrounding mine
76 * - -1 means the square is marked as a mine.
78 * - -2 means the square is unknown.
80 * - -3 means the square is marked with a question mark
81 * (FIXME: do we even want to bother with this?).
83 * - 64 means the square has had a mine revealed when the game
86 * - 65 means the square had a mine revealed and this was the
87 * one the player hits.
89 * - 66 means the square has a crossed-out mine because the
90 * player had incorrectly marked it.
94 static game_params *default_params(void)
96 game_params *ret = snew(game_params);
105 static const struct game_params mines_presets[] = {
116 static int game_fetch_preset(int i, char **name, game_params **params)
121 if (i < 0 || i >= lenof(mines_presets))
124 ret = snew(game_params);
125 *ret = mines_presets[i];
127 sprintf(str, "%dx%d, %d mines", ret->w, ret->h, ret->n);
134 static void free_params(game_params *params)
139 static game_params *dup_params(const game_params *params)
141 game_params *ret = snew(game_params);
142 *ret = *params; /* structure copy */
146 static void decode_params(game_params *params, char const *string)
148 char const *p = string;
151 while (*p && isdigit((unsigned char)*p)) p++;
155 while (*p && isdigit((unsigned char)*p)) p++;
157 params->h = params->w;
162 while (*p && (*p == '.' || isdigit((unsigned char)*p))) p++;
164 params->n = params->w * params->h / 10;
170 params->unique = FALSE;
172 p++; /* skip any other gunk */
176 static char *encode_params(const game_params *params, int full)
181 len = sprintf(ret, "%dx%d", params->w, params->h);
183 * Mine count is a generation-time parameter, since it can be
184 * deduced from the mine bitmap!
187 len += sprintf(ret+len, "n%d", params->n);
188 if (full && !params->unique)
190 assert(len < lenof(ret));
196 static config_item *game_configure(const game_params *params)
201 ret = snewn(5, config_item);
203 ret[0].name = "Width";
204 ret[0].type = C_STRING;
205 sprintf(buf, "%d", params->w);
206 ret[0].u.string.sval = dupstr(buf);
208 ret[1].name = "Height";
209 ret[1].type = C_STRING;
210 sprintf(buf, "%d", params->h);
211 ret[1].u.string.sval = dupstr(buf);
213 ret[2].name = "Mines";
214 ret[2].type = C_STRING;
215 sprintf(buf, "%d", params->n);
216 ret[2].u.string.sval = dupstr(buf);
218 ret[3].name = "Ensure solubility";
219 ret[3].type = C_BOOLEAN;
220 ret[3].u.boolean.bval = params->unique;
228 static game_params *custom_params(const config_item *cfg)
230 game_params *ret = snew(game_params);
232 ret->w = atoi(cfg[0].u.string.sval);
233 ret->h = atoi(cfg[1].u.string.sval);
234 ret->n = atoi(cfg[2].u.string.sval);
235 if (strchr(cfg[2].u.string.sval, '%'))
236 ret->n = ret->n * (ret->w * ret->h) / 100;
237 ret->unique = cfg[3].u.boolean.bval;
242 static const char *validate_params(const game_params *params, int full)
245 * Lower limit on grid size: each dimension must be at least 3.
246 * 1 is theoretically workable if rather boring, but 2 is a
247 * real problem: there is often _no_ way to generate a uniquely
248 * solvable 2xn Mines grid. You either run into two mines
249 * blocking the way and no idea what's behind them, or one mine
250 * and no way to know which of the two rows it's in. If the
251 * mine count is even you can create a soluble grid by packing
252 * all the mines at one end (so what when you hit a two-mine
253 * wall there are only as many covered squares left as there
254 * are mines); but if it's odd, you are doomed, because you
255 * _have_ to have a gap somewhere which you can't determine the
258 if (full && params->unique && (params->w <= 2 || params->h <= 2))
259 return "Width and height must both be greater than two";
260 if (params->n > params->w * params->h - 9)
261 return "Too many mines for grid size";
264 * FIXME: Need more constraints here. Not sure what the
265 * sensible limits for Minesweeper actually are. The limits
266 * probably ought to change, however, depending on uniqueness.
272 /* ----------------------------------------------------------------------
273 * Minesweeper solver, used to ensure the generated grids are
274 * solvable without having to take risks.
278 * Count the bits in a word. Only needs to cope with 16 bits.
280 static int bitcount16(int inword)
282 unsigned int word = inword;
284 word = ((word & 0xAAAA) >> 1) + (word & 0x5555);
285 word = ((word & 0xCCCC) >> 2) + (word & 0x3333);
286 word = ((word & 0xF0F0) >> 4) + (word & 0x0F0F);
287 word = ((word & 0xFF00) >> 8) + (word & 0x00FF);
293 * We use a tree234 to store a large number of small localised
294 * sets, each with a mine count. We also keep some of those sets
295 * linked together into a to-do list.
298 short x, y, mask, mines;
300 struct set *prev, *next;
303 static int setcmp(void *av, void *bv)
305 struct set *a = (struct set *)av;
306 struct set *b = (struct set *)bv;
310 else if (a->y > b->y)
312 else if (a->x < b->x)
314 else if (a->x > b->x)
316 else if (a->mask < b->mask)
318 else if (a->mask > b->mask)
326 struct set *todo_head, *todo_tail;
329 static struct setstore *ss_new(void)
331 struct setstore *ss = snew(struct setstore);
332 ss->sets = newtree234(setcmp);
333 ss->todo_head = ss->todo_tail = NULL;
338 * Take two input sets, in the form (x,y,mask). Munge the first by
339 * taking either its intersection with the second or its difference
340 * with the second. Return the new mask part of the first set.
342 static int setmunge(int x1, int y1, int mask1, int x2, int y2, int mask2,
346 * Adjust the second set so that it has the same x,y
347 * coordinates as the first.
349 if (abs(x2-x1) >= 3 || abs(y2-y1) >= 3) {
353 mask2 &= ~(4|32|256);
363 mask2 &= ~(64|128|256);
375 * Invert the second set if `diff' is set (we're after A &~ B
376 * rather than A & B).
382 * Now all that's left is a logical AND.
384 return mask1 & mask2;
387 static void ss_add_todo(struct setstore *ss, struct set *s)
390 return; /* already on it */
392 #ifdef SOLVER_DIAGNOSTICS
393 printf("adding set on todo list: %d,%d %03x %d\n",
394 s->x, s->y, s->mask, s->mines);
397 s->prev = ss->todo_tail;
407 static void ss_add(struct setstore *ss, int x, int y, int mask, int mines)
414 * Normalise so that x and y are genuinely the bounding
417 while (!(mask & (1|8|64)))
419 while (!(mask & (1|2|4)))
423 * Create a set structure and add it to the tree.
425 s = snew(struct set);
431 if (add234(ss->sets, s) != s) {
433 * This set already existed! Free it and return.
440 * We've added a new set to the tree, so put it on the todo
446 static void ss_remove(struct setstore *ss, struct set *s)
448 struct set *next = s->next, *prev = s->prev;
450 #ifdef SOLVER_DIAGNOSTICS
451 printf("removing set %d,%d %03x\n", s->x, s->y, s->mask);
454 * Remove s from the todo list.
458 else if (s == ss->todo_head)
459 ss->todo_head = next;
463 else if (s == ss->todo_tail)
464 ss->todo_tail = prev;
469 * Remove s from the tree.
474 * Destroy the actual set structure.
480 * Return a dynamically allocated list of all the sets which
481 * overlap a provided input set.
483 static struct set **ss_overlap(struct setstore *ss, int x, int y, int mask)
485 struct set **ret = NULL;
486 int nret = 0, retsize = 0;
489 for (xx = x-3; xx < x+3; xx++)
490 for (yy = y-3; yy < y+3; yy++) {
495 * Find the first set with these top left coordinates.
501 if (findrelpos234(ss->sets, &stmp, NULL, REL234_GE, &pos)) {
502 while ((s = index234(ss->sets, pos)) != NULL &&
503 s->x == xx && s->y == yy) {
505 * This set potentially overlaps the input one.
506 * Compute the intersection to see if they
507 * really overlap, and add it to the list if
510 if (setmunge(x, y, mask, s->x, s->y, s->mask, FALSE)) {
512 * There's an overlap.
514 if (nret >= retsize) {
516 ret = sresize(ret, retsize, struct set *);
526 ret = sresize(ret, nret+1, struct set *);
533 * Get an element from the head of the set todo list.
535 static struct set *ss_todo(struct setstore *ss)
538 struct set *ret = ss->todo_head;
539 ss->todo_head = ret->next;
541 ss->todo_head->prev = NULL;
543 ss->todo_tail = NULL;
544 ret->next = ret->prev = NULL;
557 static void std_add(struct squaretodo *std, int i)
560 std->next[std->tail] = i;
567 typedef int (*open_cb)(void *, int, int);
569 static void known_squares(int w, int h, struct squaretodo *std,
571 open_cb open, void *openctx,
572 int x, int y, int mask, int mine)
578 for (yy = 0; yy < 3; yy++)
579 for (xx = 0; xx < 3; xx++) {
581 int i = (y + yy) * w + (x + xx);
584 * It's possible that this square is _already_
585 * known, in which case we don't try to add it to
591 grid[i] = -1; /* and don't open it! */
593 grid[i] = open(openctx, x + xx, y + yy);
594 assert(grid[i] != -1); /* *bang* */
605 * This is data returned from the `perturb' function. It details
606 * which squares have become mines and which have become clear. The
607 * solver is (of course) expected to honourably not use that
608 * knowledge directly, but to efficently adjust its internal data
609 * structures and proceed based on only the information it
612 struct perturbation {
614 int delta; /* +1 == become a mine; -1 == cleared */
616 struct perturbations {
618 struct perturbation *changes;
622 * Main solver entry point. You give it a grid of existing
623 * knowledge (-1 for a square known to be a mine, 0-8 for empty
624 * squares with a given number of neighbours, -2 for completely
625 * unknown), plus a function which you can call to open new squares
626 * once you're confident of them. It fills in as much more of the
631 * - -1 means deduction stalled and nothing could be done
632 * - 0 means deduction succeeded fully
633 * - >0 means deduction succeeded but some number of perturbation
634 * steps were required; the exact return value is the number of
638 typedef struct perturbations *(*perturb_cb) (void *, signed char *, int, int, int);
640 static int minesolve(int w, int h, int n, signed char *grid,
643 void *ctx, random_state *rs)
645 struct setstore *ss = ss_new();
647 struct squaretodo astd, *std = &astd;
652 * Set up a linked list of squares with known contents, so that
653 * we can process them one by one.
655 std->next = snewn(w*h, int);
656 std->head = std->tail = -1;
659 * Initialise that list with all known squares in the input
662 for (y = 0; y < h; y++) {
663 for (x = 0; x < w; x++) {
671 * Main deductive loop.
674 int done_something = FALSE;
678 * If there are any known squares on the todo list, process
679 * them and construct a set for each.
681 while (std->head != -1) {
683 #ifdef SOLVER_DIAGNOSTICS
684 printf("known square at %d,%d [%d]\n", i%w, i/w, grid[i]);
686 std->head = std->next[i];
694 int dx, dy, mines, bit, val;
695 #ifdef SOLVER_DIAGNOSTICS
696 printf("creating set around this square\n");
699 * Empty square. Construct the set of non-known squares
700 * around this one, and determine its mine count.
705 for (dy = -1; dy <= +1; dy++) {
706 for (dx = -1; dx <= +1; dx++) {
707 #ifdef SOLVER_DIAGNOSTICS
708 printf("grid %d,%d = %d\n", x+dx, y+dy, grid[i+dy*w+dx]);
710 if (x+dx < 0 || x+dx >= w || y+dy < 0 || y+dy >= h)
711 /* ignore this one */;
712 else if (grid[i+dy*w+dx] == -1)
714 else if (grid[i+dy*w+dx] == -2)
720 ss_add(ss, x-1, y-1, val, mines);
724 * Now, whether the square is empty or full, we must
725 * find any set which contains it and replace it with
726 * one which does not.
729 #ifdef SOLVER_DIAGNOSTICS
730 printf("finding sets containing known square %d,%d\n", x, y);
732 list = ss_overlap(ss, x, y, 1);
734 for (j = 0; list[j]; j++) {
735 int newmask, newmines;
740 * Compute the mask for this set minus the
741 * newly known square.
743 newmask = setmunge(s->x, s->y, s->mask, x, y, 1, TRUE);
746 * Compute the new mine count.
748 newmines = s->mines - (grid[i] == -1);
751 * Insert the new set into the collection,
752 * unless it's been whittled right down to
756 ss_add(ss, s->x, s->y, newmask, newmines);
759 * Destroy the old one; it is actually obsolete.
768 * Marking a fresh square as known certainly counts as
771 done_something = TRUE;
775 * Now pick a set off the to-do list and attempt deductions
778 if ((s = ss_todo(ss)) != NULL) {
780 #ifdef SOLVER_DIAGNOSTICS
781 printf("set to do: %d,%d %03x %d\n", s->x, s->y, s->mask, s->mines);
784 * Firstly, see if this set has a mine count of zero or
785 * of its own cardinality.
787 if (s->mines == 0 || s->mines == bitcount16(s->mask)) {
789 * If so, we can immediately mark all the squares
790 * in the set as known.
792 #ifdef SOLVER_DIAGNOSTICS
795 known_squares(w, h, std, grid, open, ctx,
796 s->x, s->y, s->mask, (s->mines != 0));
799 * Having done that, we need do nothing further
800 * with this set; marking all the squares in it as
801 * known will eventually eliminate it, and will
802 * also permit further deductions about anything
809 * Failing that, we now search through all the sets
810 * which overlap this one.
812 list = ss_overlap(ss, s->x, s->y, s->mask);
814 for (j = 0; list[j]; j++) {
815 struct set *s2 = list[j];
816 int swing, s2wing, swc, s2wc;
819 * Find the non-overlapping parts s2-s and s-s2,
820 * and their cardinalities.
822 * I'm going to refer to these parts as `wings'
823 * surrounding the central part common to both
824 * sets. The `s wing' is s-s2; the `s2 wing' is
827 swing = setmunge(s->x, s->y, s->mask, s2->x, s2->y, s2->mask,
829 s2wing = setmunge(s2->x, s2->y, s2->mask, s->x, s->y, s->mask,
831 swc = bitcount16(swing);
832 s2wc = bitcount16(s2wing);
835 * If one set has more mines than the other, and
836 * the number of extra mines is equal to the
837 * cardinality of that set's wing, then we can mark
838 * every square in the wing as a known mine, and
839 * every square in the other wing as known clear.
841 if (swc == s->mines - s2->mines ||
842 s2wc == s2->mines - s->mines) {
843 known_squares(w, h, std, grid, open, ctx,
845 (swc == s->mines - s2->mines));
846 known_squares(w, h, std, grid, open, ctx,
847 s2->x, s2->y, s2wing,
848 (s2wc == s2->mines - s->mines));
853 * Failing that, see if one set is a subset of the
854 * other. If so, we can divide up the mine count of
855 * the larger set between the smaller set and its
856 * complement, even if neither smaller set ends up
857 * being immediately clearable.
859 if (swc == 0 && s2wc != 0) {
860 /* s is a subset of s2. */
861 assert(s2->mines > s->mines);
862 ss_add(ss, s2->x, s2->y, s2wing, s2->mines - s->mines);
863 } else if (s2wc == 0 && swc != 0) {
864 /* s2 is a subset of s. */
865 assert(s->mines > s2->mines);
866 ss_add(ss, s->x, s->y, swing, s->mines - s2->mines);
873 * In this situation we have definitely done
874 * _something_, even if it's only reducing the size of
877 done_something = TRUE;
880 * We have nothing left on our todo list, which means
881 * all localised deductions have failed. Our next step
882 * is to resort to global deduction based on the total
883 * mine count. This is computationally expensive
884 * compared to any of the above deductions, which is
885 * why we only ever do it when all else fails, so that
886 * hopefully it won't have to happen too often.
888 * If you pass n<0 into this solver, that informs it
889 * that you do not know the total mine count, so it
890 * won't even attempt these deductions.
893 int minesleft, squaresleft;
894 int nsets, setused[10], cursor;
897 * Start by scanning the current grid state to work out
898 * how many unknown squares we still have, and how many
899 * mines are to be placed in them.
903 for (i = 0; i < w*h; i++) {
906 else if (grid[i] == -2)
910 #ifdef SOLVER_DIAGNOSTICS
911 printf("global deduction time: squaresleft=%d minesleft=%d\n",
912 squaresleft, minesleft);
913 for (y = 0; y < h; y++) {
914 for (x = 0; x < w; x++) {
930 * If there _are_ no unknown squares, we have actually
933 if (squaresleft == 0) {
934 assert(minesleft == 0);
939 * First really simple case: if there are no more mines
940 * left, or if there are exactly as many mines left as
941 * squares to play them in, then it's all easy.
943 if (minesleft == 0 || minesleft == squaresleft) {
944 for (i = 0; i < w*h; i++)
946 known_squares(w, h, std, grid, open, ctx,
947 i % w, i / w, 1, minesleft != 0);
948 continue; /* now go back to main deductive loop */
952 * Failing that, we have to do some _real_ work.
953 * Ideally what we do here is to try every single
954 * combination of the currently available sets, in an
955 * attempt to find a disjoint union (i.e. a set of
956 * squares with a known mine count between them) such
957 * that the remaining unknown squares _not_ contained
958 * in that union either contain no mines or are all
961 * Actually enumerating all 2^n possibilities will get
962 * a bit slow for large n, so I artificially cap this
963 * recursion at n=10 to avoid too much pain.
965 nsets = count234(ss->sets);
966 if (nsets <= lenof(setused)) {
968 * Doing this with actual recursive function calls
969 * would get fiddly because a load of local
970 * variables from this function would have to be
971 * passed down through the recursion. So instead
972 * I'm going to use a virtual recursion within this
973 * function. The way this works is:
975 * - we have an array `setused', such that
976 * setused[n] is 0 or 1 depending on whether set
977 * n is currently in the union we are
980 * - we have a value `cursor' which indicates how
981 * much of `setused' we have so far filled in.
982 * It's conceptually the recursion depth.
984 * We begin by setting `cursor' to zero. Then:
986 * - if cursor can advance, we advance it by one.
987 * We set the value in `setused' that it went
988 * past to 1 if that set is disjoint from
989 * anything else currently in `setused', or to 0
992 * - If cursor cannot advance because it has
993 * reached the end of the setused list, then we
994 * have a maximal disjoint union. Check to see
995 * whether its mine count has any useful
996 * properties. If so, mark all the squares not
997 * in the union as known and terminate.
999 * - If cursor has reached the end of setused and
1000 * the algorithm _hasn't_ terminated, back
1001 * cursor up to the nearest 1, turn it into a 0
1002 * and advance cursor just past it.
1004 * - If we attempt to back up to the nearest 1 and
1005 * there isn't one at all, then we have gone
1006 * through all disjoint unions of sets in the
1007 * list and none of them has been helpful, so we
1010 struct set *sets[lenof(setused)];
1011 for (i = 0; i < nsets; i++)
1012 sets[i] = index234(ss->sets, i);
1017 if (cursor < nsets) {
1020 /* See if any existing set overlaps this one. */
1021 for (i = 0; i < cursor; i++)
1023 setmunge(sets[cursor]->x,
1026 sets[i]->x, sets[i]->y, sets[i]->mask,
1034 * We're adding this set to our union,
1035 * so adjust minesleft and squaresleft
1038 minesleft -= sets[cursor]->mines;
1039 squaresleft -= bitcount16(sets[cursor]->mask);
1042 setused[cursor++] = ok;
1044 #ifdef SOLVER_DIAGNOSTICS
1045 printf("trying a set combination with %d %d\n",
1046 squaresleft, minesleft);
1047 #endif /* SOLVER_DIAGNOSTICS */
1050 * We've reached the end. See if we've got
1051 * anything interesting.
1053 if (squaresleft > 0 &&
1054 (minesleft == 0 || minesleft == squaresleft)) {
1056 * We have! There is at least one
1057 * square not contained within the set
1058 * union we've just found, and we can
1059 * deduce that either all such squares
1060 * are mines or all are not (depending
1061 * on whether minesleft==0). So now all
1062 * we have to do is actually go through
1063 * the grid, find those squares, and
1066 for (i = 0; i < w*h; i++)
1067 if (grid[i] == -2) {
1071 for (j = 0; j < nsets; j++)
1073 setmunge(sets[j]->x, sets[j]->y,
1074 sets[j]->mask, x, y, 1,
1080 known_squares(w, h, std, grid,
1082 x, y, 1, minesleft != 0);
1085 done_something = TRUE;
1086 break; /* return to main deductive loop */
1090 * If we reach here, then this union hasn't
1091 * done us any good, so move on to the
1092 * next. Backtrack cursor to the nearest 1,
1093 * change it to a 0 and continue.
1095 while (--cursor >= 0 && !setused[cursor]);
1097 assert(setused[cursor]);
1100 * We're removing this set from our
1101 * union, so re-increment minesleft and
1104 minesleft += sets[cursor]->mines;
1105 squaresleft += bitcount16(sets[cursor]->mask);
1107 setused[cursor++] = 0;
1110 * We've backtracked all the way to the
1111 * start without finding a single 1,
1112 * which means that our virtual
1113 * recursion is complete and nothing
1128 #ifdef SOLVER_DIAGNOSTICS
1130 * Dump the current known state of the grid.
1132 printf("solver ran out of steam, ret=%d, grid:\n", nperturbs);
1133 for (y = 0; y < h; y++) {
1134 for (x = 0; x < w; x++) {
1135 int v = grid[y*w+x];
1151 for (i = 0; (s = index234(ss->sets, i)) != NULL; i++)
1152 printf("remaining set: %d,%d %03x %d\n", s->x, s->y, s->mask, s->mines);
1157 * Now we really are at our wits' end as far as solving
1158 * this grid goes. Our only remaining option is to call
1159 * a perturb function and ask it to modify the grid to
1163 struct perturbations *ret;
1169 * Choose a set at random from the current selection,
1170 * and ask the perturb function to either fill or empty
1173 * If we have no sets at all, we must give up.
1175 if (count234(ss->sets) == 0) {
1176 #ifdef SOLVER_DIAGNOSTICS
1177 printf("perturbing on entire unknown set\n");
1179 ret = perturb(ctx, grid, 0, 0, 0);
1181 s = index234(ss->sets, random_upto(rs, count234(ss->sets)));
1182 #ifdef SOLVER_DIAGNOSTICS
1183 printf("perturbing on set %d,%d %03x\n", s->x, s->y, s->mask);
1185 ret = perturb(ctx, grid, s->x, s->y, s->mask);
1189 assert(ret->n > 0); /* otherwise should have been NULL */
1192 * A number of squares have been fiddled with, and
1193 * the returned structure tells us which. Adjust
1194 * the mine count in any set which overlaps one of
1195 * those squares, and put them back on the to-do
1196 * list. Also, if the square itself is marked as a
1197 * known non-mine, put it back on the squares-to-do
1200 for (i = 0; i < ret->n; i++) {
1201 #ifdef SOLVER_DIAGNOSTICS
1202 printf("perturbation %s mine at %d,%d\n",
1203 ret->changes[i].delta > 0 ? "added" : "removed",
1204 ret->changes[i].x, ret->changes[i].y);
1207 if (ret->changes[i].delta < 0 &&
1208 grid[ret->changes[i].y*w+ret->changes[i].x] != -2) {
1209 std_add(std, ret->changes[i].y*w+ret->changes[i].x);
1212 list = ss_overlap(ss,
1213 ret->changes[i].x, ret->changes[i].y, 1);
1215 for (j = 0; list[j]; j++) {
1216 list[j]->mines += ret->changes[i].delta;
1217 ss_add_todo(ss, list[j]);
1224 * Now free the returned data.
1226 sfree(ret->changes);
1229 #ifdef SOLVER_DIAGNOSTICS
1231 * Dump the current known state of the grid.
1233 printf("state after perturbation:\n");
1234 for (y = 0; y < h; y++) {
1235 for (x = 0; x < w; x++) {
1236 int v = grid[y*w+x];
1252 for (i = 0; (s = index234(ss->sets, i)) != NULL; i++)
1253 printf("remaining set: %d,%d %03x %d\n", s->x, s->y, s->mask, s->mines);
1258 * And now we can go back round the deductive loop.
1265 * If we get here, even that didn't work (either we didn't
1266 * have a perturb function or it returned failure), so we
1273 * See if we've got any unknown squares left.
1275 for (y = 0; y < h; y++)
1276 for (x = 0; x < w; x++)
1277 if (grid[y*w+x] == -2) {
1278 nperturbs = -1; /* failed to complete */
1283 * Free the set list and square-todo list.
1287 while ((s = delpos234(ss->sets, 0)) != NULL)
1289 freetree234(ss->sets);
1297 /* ----------------------------------------------------------------------
1298 * Grid generator which uses the above solver.
1305 int allow_big_perturbs;
1309 static int mineopen(void *vctx, int x, int y)
1311 struct minectx *ctx = (struct minectx *)vctx;
1314 assert(x >= 0 && x < ctx->w && y >= 0 && y < ctx->h);
1315 if (ctx->grid[y * ctx->w + x])
1316 return -1; /* *bang* */
1319 for (i = -1; i <= +1; i++) {
1320 if (x + i < 0 || x + i >= ctx->w)
1322 for (j = -1; j <= +1; j++) {
1323 if (y + j < 0 || y + j >= ctx->h)
1325 if (i == 0 && j == 0)
1327 if (ctx->grid[(y+j) * ctx->w + (x+i)])
1335 /* Structure used internally to mineperturb(). */
1337 int x, y, type, random;
1339 static int squarecmp(const void *av, const void *bv)
1341 const struct square *a = (const struct square *)av;
1342 const struct square *b = (const struct square *)bv;
1343 if (a->type < b->type)
1345 else if (a->type > b->type)
1347 else if (a->random < b->random)
1349 else if (a->random > b->random)
1351 else if (a->y < b->y)
1353 else if (a->y > b->y)
1355 else if (a->x < b->x)
1357 else if (a->x > b->x)
1363 * Normally this function is passed an (x,y,mask) set description.
1364 * On occasions, though, there is no _localised_ set being used,
1365 * and the set being perturbed is supposed to be the entirety of
1366 * the unreachable area. This is signified by the special case
1367 * mask==0: in this case, anything labelled -2 in the grid is part
1370 * Allowing perturbation in this special case appears to make it
1371 * guaranteeably possible to generate a workable grid for any mine
1372 * density, but they tend to be a bit boring, with mines packed
1373 * densely into far corners of the grid and the remainder being
1374 * less dense than one might like. Therefore, to improve overall
1375 * grid quality I disable this feature for the first few attempts,
1376 * and fall back to it after no useful grid has been generated.
1378 static struct perturbations *mineperturb(void *vctx, signed char *grid,
1379 int setx, int sety, int mask)
1381 struct minectx *ctx = (struct minectx *)vctx;
1382 struct square *sqlist;
1383 int x, y, dx, dy, i, n, nfull, nempty;
1384 struct square **tofill, **toempty, **todo;
1385 int ntofill, ntoempty, ntodo, dtodo, dset;
1386 struct perturbations *ret;
1389 if (!mask && !ctx->allow_big_perturbs)
1393 * Make a list of all the squares in the grid which we can
1394 * possibly use. This list should be in preference order, which
1397 * - first, unknown squares on the boundary of known space
1398 * - next, unknown squares beyond that boundary
1399 * - as a very last resort, known squares, but not within one
1400 * square of the starting position.
1402 * Each of these sections needs to be shuffled independently.
1403 * We do this by preparing list of all squares and then sorting
1404 * it with a random secondary key.
1406 sqlist = snewn(ctx->w * ctx->h, struct square);
1408 for (y = 0; y < ctx->h; y++)
1409 for (x = 0; x < ctx->w; x++) {
1411 * If this square is too near the starting position,
1412 * don't put it on the list at all.
1414 if (abs(y - ctx->sy) <= 1 && abs(x - ctx->sx) <= 1)
1418 * If this square is in the input set, also don't put
1421 if ((mask == 0 && grid[y*ctx->w+x] == -2) ||
1422 (x >= setx && x < setx + 3 &&
1423 y >= sety && y < sety + 3 &&
1424 mask & (1 << ((y-sety)*3+(x-setx)))))
1430 if (grid[y*ctx->w+x] != -2) {
1431 sqlist[n].type = 3; /* known square */
1434 * Unknown square. Examine everything around it and
1435 * see if it borders on any known squares. If it
1436 * does, it's class 1, otherwise it's 2.
1441 for (dy = -1; dy <= +1; dy++)
1442 for (dx = -1; dx <= +1; dx++)
1443 if (x+dx >= 0 && x+dx < ctx->w &&
1444 y+dy >= 0 && y+dy < ctx->h &&
1445 grid[(y+dy)*ctx->w+(x+dx)] != -2) {
1452 * Finally, a random number to cause qsort to
1453 * shuffle within each group.
1455 sqlist[n].random = random_bits(ctx->rs, 31);
1460 qsort(sqlist, n, sizeof(struct square), squarecmp);
1463 * Now count up the number of full and empty squares in the set
1464 * we've been provided.
1468 for (dy = 0; dy < 3; dy++)
1469 for (dx = 0; dx < 3; dx++)
1470 if (mask & (1 << (dy*3+dx))) {
1471 assert(setx+dx <= ctx->w);
1472 assert(sety+dy <= ctx->h);
1473 if (ctx->grid[(sety+dy)*ctx->w+(setx+dx)])
1479 for (y = 0; y < ctx->h; y++)
1480 for (x = 0; x < ctx->w; x++)
1481 if (grid[y*ctx->w+x] == -2) {
1482 if (ctx->grid[y*ctx->w+x])
1490 * Now go through our sorted list until we find either `nfull'
1491 * empty squares, or `nempty' full squares; these will be
1492 * swapped with the appropriate squares in the set to either
1493 * fill or empty the set while keeping the same number of mines
1496 ntofill = ntoempty = 0;
1498 tofill = snewn(9, struct square *);
1499 toempty = snewn(9, struct square *);
1501 tofill = snewn(ctx->w * ctx->h, struct square *);
1502 toempty = snewn(ctx->w * ctx->h, struct square *);
1504 for (i = 0; i < n; i++) {
1505 struct square *sq = &sqlist[i];
1506 if (ctx->grid[sq->y * ctx->w + sq->x])
1507 toempty[ntoempty++] = sq;
1509 tofill[ntofill++] = sq;
1510 if (ntofill == nfull || ntoempty == nempty)
1515 * If we haven't found enough empty squares outside the set to
1516 * empty it into _or_ enough full squares outside it to fill it
1517 * up with, we'll have to settle for doing only a partial job.
1518 * In this case we choose to always _fill_ the set (because
1519 * this case will tend to crop up when we're working with very
1520 * high mine densities and the only way to get a solvable grid
1521 * is going to be to pack most of the mines solidly around the
1522 * edges). So now our job is to make a list of the empty
1523 * squares in the set, and shuffle that list so that we fill a
1524 * random selection of them.
1526 if (ntofill != nfull && ntoempty != nempty) {
1529 assert(ntoempty != 0);
1531 setlist = snewn(ctx->w * ctx->h, int);
1534 for (dy = 0; dy < 3; dy++)
1535 for (dx = 0; dx < 3; dx++)
1536 if (mask & (1 << (dy*3+dx))) {
1537 assert(setx+dx <= ctx->w);
1538 assert(sety+dy <= ctx->h);
1539 if (!ctx->grid[(sety+dy)*ctx->w+(setx+dx)])
1540 setlist[i++] = (sety+dy)*ctx->w+(setx+dx);
1543 for (y = 0; y < ctx->h; y++)
1544 for (x = 0; x < ctx->w; x++)
1545 if (grid[y*ctx->w+x] == -2) {
1546 if (!ctx->grid[y*ctx->w+x])
1547 setlist[i++] = y*ctx->w+x;
1550 assert(i > ntoempty);
1552 * Now pick `ntoempty' items at random from the list.
1554 for (k = 0; k < ntoempty; k++) {
1555 int index = k + random_upto(ctx->rs, i - k);
1559 setlist[k] = setlist[index];
1560 setlist[index] = tmp;
1566 * Now we're pretty much there. We need to either
1567 * (a) put a mine in each of the empty squares in the set, and
1568 * take one out of each square in `toempty'
1569 * (b) take a mine out of each of the full squares in the set,
1570 * and put one in each square in `tofill'
1571 * depending on which one we've found enough squares to do.
1573 * So we start by constructing our list of changes to return to
1574 * the solver, so that it can update its data structures
1575 * efficiently rather than having to rescan the whole grid.
1577 ret = snew(struct perturbations);
1578 if (ntofill == nfull) {
1586 * (We also fall into this case if we've constructed a
1596 ret->changes = snewn(ret->n, struct perturbation);
1597 for (i = 0; i < ntodo; i++) {
1598 ret->changes[i].x = todo[i]->x;
1599 ret->changes[i].y = todo[i]->y;
1600 ret->changes[i].delta = dtodo;
1602 /* now i == ntodo */
1605 assert(todo == toempty);
1606 for (j = 0; j < ntoempty; j++) {
1607 ret->changes[i].x = setlist[j] % ctx->w;
1608 ret->changes[i].y = setlist[j] / ctx->w;
1609 ret->changes[i].delta = dset;
1614 for (dy = 0; dy < 3; dy++)
1615 for (dx = 0; dx < 3; dx++)
1616 if (mask & (1 << (dy*3+dx))) {
1617 int currval = (ctx->grid[(sety+dy)*ctx->w+(setx+dx)] ? +1 : -1);
1618 if (dset == -currval) {
1619 ret->changes[i].x = setx + dx;
1620 ret->changes[i].y = sety + dy;
1621 ret->changes[i].delta = dset;
1626 for (y = 0; y < ctx->h; y++)
1627 for (x = 0; x < ctx->w; x++)
1628 if (grid[y*ctx->w+x] == -2) {
1629 int currval = (ctx->grid[y*ctx->w+x] ? +1 : -1);
1630 if (dset == -currval) {
1631 ret->changes[i].x = x;
1632 ret->changes[i].y = y;
1633 ret->changes[i].delta = dset;
1638 assert(i == ret->n);
1644 * Having set up the precise list of changes we're going to
1645 * make, we now simply make them and return.
1647 for (i = 0; i < ret->n; i++) {
1650 x = ret->changes[i].x;
1651 y = ret->changes[i].y;
1652 delta = ret->changes[i].delta;
1655 * Check we're not trying to add an existing mine or remove
1658 assert((delta < 0) ^ (ctx->grid[y*ctx->w+x] == 0));
1661 * Actually make the change.
1663 ctx->grid[y*ctx->w+x] = (delta > 0);
1666 * Update any numbers already present in the grid.
1668 for (dy = -1; dy <= +1; dy++)
1669 for (dx = -1; dx <= +1; dx++)
1670 if (x+dx >= 0 && x+dx < ctx->w &&
1671 y+dy >= 0 && y+dy < ctx->h &&
1672 grid[(y+dy)*ctx->w+(x+dx)] != -2) {
1673 if (dx == 0 && dy == 0) {
1675 * The square itself is marked as known in
1676 * the grid. Mark it as a mine if it's a
1677 * mine, or else work out its number.
1680 grid[y*ctx->w+x] = -1;
1682 int dx2, dy2, minecount = 0;
1683 for (dy2 = -1; dy2 <= +1; dy2++)
1684 for (dx2 = -1; dx2 <= +1; dx2++)
1685 if (x+dx2 >= 0 && x+dx2 < ctx->w &&
1686 y+dy2 >= 0 && y+dy2 < ctx->h &&
1687 ctx->grid[(y+dy2)*ctx->w+(x+dx2)])
1689 grid[y*ctx->w+x] = minecount;
1692 if (grid[(y+dy)*ctx->w+(x+dx)] >= 0)
1693 grid[(y+dy)*ctx->w+(x+dx)] += delta;
1698 #ifdef GENERATION_DIAGNOSTICS
1701 printf("grid after perturbing:\n");
1702 for (yy = 0; yy < ctx->h; yy++) {
1703 for (xx = 0; xx < ctx->w; xx++) {
1704 int v = ctx->grid[yy*ctx->w+xx];
1705 if (yy == ctx->sy && xx == ctx->sx) {
1723 static char *minegen(int w, int h, int n, int x, int y, int unique,
1726 char *ret = snewn(w*h, char);
1734 memset(ret, 0, w*h);
1737 * Start by placing n mines, none of which is at x,y or within
1741 int *tmp = snewn(w*h, int);
1745 * Write down the list of possible mine locations.
1748 for (i = 0; i < h; i++)
1749 for (j = 0; j < w; j++)
1750 if (abs(i - y) > 1 || abs(j - x) > 1)
1754 * Now pick n off the list at random.
1758 i = random_upto(rs, k);
1766 #ifdef GENERATION_DIAGNOSTICS
1769 printf("grid after initial generation:\n");
1770 for (yy = 0; yy < h; yy++) {
1771 for (xx = 0; xx < w; xx++) {
1772 int v = ret[yy*w+xx];
1773 if (yy == y && xx == x) {
1789 * Now set up a results grid to run the solver in, and a
1790 * context for the solver to open squares. Then run the solver
1791 * repeatedly; if the number of perturb steps ever goes up or
1792 * it ever returns -1, give up completely.
1794 * We bypass this bit if we're not after a unique grid.
1797 signed char *solvegrid = snewn(w*h, signed char);
1798 struct minectx actx, *ctx = &actx;
1799 int solveret, prevret = -2;
1807 ctx->allow_big_perturbs = (ntries > 100);
1810 memset(solvegrid, -2, w*h);
1811 solvegrid[y*w+x] = mineopen(ctx, x, y);
1812 assert(solvegrid[y*w+x] == 0); /* by deliberate arrangement */
1815 minesolve(w, h, n, solvegrid, mineopen, mineperturb, ctx, rs);
1816 if (solveret < 0 || (prevret >= 0 && solveret >= prevret)) {
1819 } else if (solveret == 0) {
1835 static char *describe_layout(char *grid, int area, int x, int y,
1843 * Set up the mine bitmap and obfuscate it.
1845 bmp = snewn((area + 7) / 8, unsigned char);
1846 memset(bmp, 0, (area + 7) / 8);
1847 for (i = 0; i < area; i++) {
1849 bmp[i / 8] |= 0x80 >> (i % 8);
1852 obfuscate_bitmap(bmp, area, FALSE);
1855 * Now encode the resulting bitmap in hex. We can work to
1856 * nibble rather than byte granularity, since the obfuscation
1857 * function guarantees to return a bit string of the same
1858 * length as its input.
1860 ret = snewn((area+3)/4 + 100, char);
1861 p = ret + sprintf(ret, "%d,%d,%s", x, y,
1862 obfuscate ? "m" : "u"); /* 'm' == masked */
1863 for (i = 0; i < (area+3)/4; i++) {
1867 *p++ = "0123456789abcdef"[v & 0xF];
1876 static char *new_mine_layout(int w, int h, int n, int x, int y, int unique,
1877 random_state *rs, char **game_desc)
1881 #ifdef TEST_OBFUSCATION
1882 static int tested_obfuscation = FALSE;
1883 if (!tested_obfuscation) {
1885 * A few simple test vectors for the obfuscator.
1887 * First test: the 28-bit stream 1234567. This divides up
1888 * into 1234 and 567[0]. The SHA of 56 70 30 (appending
1889 * "0") is 15ce8ab946640340bbb99f3f48fd2c45d1a31d30. Thus,
1890 * we XOR the 16-bit string 15CE into the input 1234 to get
1891 * 07FA. Next, we SHA that with "0": the SHA of 07 FA 30 is
1892 * 3370135c5e3da4fed937adc004a79533962b6391. So we XOR the
1893 * 12-bit string 337 into the input 567 to get 650. Thus
1894 * our output is 07FA650.
1897 unsigned char bmp1[] = "\x12\x34\x56\x70";
1898 obfuscate_bitmap(bmp1, 28, FALSE);
1899 printf("test 1 encode: %s\n",
1900 memcmp(bmp1, "\x07\xfa\x65\x00", 4) ? "failed" : "passed");
1901 obfuscate_bitmap(bmp1, 28, TRUE);
1902 printf("test 1 decode: %s\n",
1903 memcmp(bmp1, "\x12\x34\x56\x70", 4) ? "failed" : "passed");
1906 * Second test: a long string to make sure we switch from
1907 * one SHA to the next correctly. My input string this time
1908 * is simply fifty bytes of zeroes.
1911 unsigned char bmp2[50];
1912 unsigned char bmp2a[50];
1913 memset(bmp2, 0, 50);
1914 memset(bmp2a, 0, 50);
1915 obfuscate_bitmap(bmp2, 50 * 8, FALSE);
1917 * SHA of twenty-five zero bytes plus "0" is
1918 * b202c07b990c01f6ff2d544707f60e506019b671. SHA of
1919 * twenty-five zero bytes plus "1" is
1920 * fcb1d8b5a2f6b592fe6780b36aa9d65dd7aa6db9. Thus our
1921 * first half becomes
1922 * b202c07b990c01f6ff2d544707f60e506019b671fcb1d8b5a2.
1924 * SHA of that lot plus "0" is
1925 * 10b0af913db85d37ca27f52a9f78bba3a80030db. SHA of the
1926 * same string plus "1" is
1927 * 3d01d8df78e76d382b8106f480135a1bc751d725. So the
1928 * second half becomes
1929 * 10b0af913db85d37ca27f52a9f78bba3a80030db3d01d8df78.
1931 printf("test 2 encode: %s\n",
1932 memcmp(bmp2, "\xb2\x02\xc0\x7b\x99\x0c\x01\xf6\xff\x2d\x54"
1933 "\x47\x07\xf6\x0e\x50\x60\x19\xb6\x71\xfc\xb1\xd8"
1934 "\xb5\xa2\x10\xb0\xaf\x91\x3d\xb8\x5d\x37\xca\x27"
1935 "\xf5\x2a\x9f\x78\xbb\xa3\xa8\x00\x30\xdb\x3d\x01"
1936 "\xd8\xdf\x78", 50) ? "failed" : "passed");
1937 obfuscate_bitmap(bmp2, 50 * 8, TRUE);
1938 printf("test 2 decode: %s\n",
1939 memcmp(bmp2, bmp2a, 50) ? "failed" : "passed");
1944 grid = minegen(w, h, n, x, y, unique, rs);
1947 *game_desc = describe_layout(grid, w * h, x, y, TRUE);
1952 static char *new_game_desc(const game_params *params, random_state *rs,
1953 char **aux, int interactive)
1956 * We generate the coordinates of an initial click even if they
1957 * aren't actually used. This has the effect of harmonising the
1958 * random number usage between interactive and batch use: if
1959 * you use `mines --generate' with an explicit random seed, you
1960 * should get exactly the same results as if you type the same
1961 * random seed into the interactive game and click in the same
1962 * initial location. (Of course you won't get the same grid if
1963 * you click in a _different_ initial location, but there's
1964 * nothing to be done about that.)
1966 int x = random_upto(rs, params->w);
1967 int y = random_upto(rs, params->h);
1971 * For batch-generated grids, pre-open one square.
1976 grid = new_mine_layout(params->w, params->h, params->n,
1977 x, y, params->unique, rs, &desc);
1981 char *rsdesc, *desc;
1983 rsdesc = random_state_encode(rs);
1984 desc = snewn(strlen(rsdesc) + 100, char);
1985 sprintf(desc, "r%d,%c,%s", params->n, (char)(params->unique ? 'u' : 'a'), rsdesc);
1991 static const char *validate_desc(const game_params *params, const char *desc)
1993 int wh = params->w * params->h;
1998 if (!*desc || !isdigit((unsigned char)*desc))
1999 return "No initial mine count in game description";
2000 while (*desc && isdigit((unsigned char)*desc))
2001 desc++; /* skip over mine count */
2003 return "No ',' after initial x-coordinate in game description";
2005 if (*desc != 'u' && *desc != 'a')
2006 return "No uniqueness specifier in game description";
2009 return "No ',' after uniqueness specifier in game description";
2010 /* now ignore the rest */
2012 if (*desc && isdigit((unsigned char)*desc)) {
2014 if (x < 0 || x >= params->w)
2015 return "Initial x-coordinate was out of range";
2016 while (*desc && isdigit((unsigned char)*desc))
2017 desc++; /* skip over x coordinate */
2019 return "No ',' after initial x-coordinate in game description";
2020 desc++; /* eat comma */
2021 if (!*desc || !isdigit((unsigned char)*desc))
2022 return "No initial y-coordinate in game description";
2024 if (y < 0 || y >= params->h)
2025 return "Initial y-coordinate was out of range";
2026 while (*desc && isdigit((unsigned char)*desc))
2027 desc++; /* skip over y coordinate */
2029 return "No ',' after initial y-coordinate in game description";
2030 desc++; /* eat comma */
2032 /* eat `m' for `masked' or `u' for `unmasked', if present */
2033 if (*desc == 'm' || *desc == 'u')
2035 /* now just check length of remainder */
2036 if (strlen(desc) != (wh+3)/4)
2037 return "Game description is wrong length";
2043 static int open_square(game_state *state, int x, int y)
2045 int w = state->w, h = state->h;
2046 int xx, yy, nmines, ncovered;
2048 if (!state->layout->mines) {
2050 * We have a preliminary game in which the mine layout
2051 * hasn't been generated yet. Generate it based on the
2052 * initial click location.
2054 char *desc, *privdesc;
2055 state->layout->mines = new_mine_layout(w, h, state->layout->n,
2056 x, y, state->layout->unique,
2060 * Find the trailing substring of the game description
2061 * corresponding to just the mine layout; we will use this
2062 * as our second `private' game ID for serialisation.
2065 while (*privdesc && isdigit((unsigned char)*privdesc)) privdesc++;
2066 if (*privdesc == ',') privdesc++;
2067 while (*privdesc && isdigit((unsigned char)*privdesc)) privdesc++;
2068 if (*privdesc == ',') privdesc++;
2069 assert(*privdesc == 'm');
2070 midend_supersede_game_desc(state->layout->me, desc, privdesc);
2072 random_free(state->layout->rs);
2073 state->layout->rs = NULL;
2076 if (state->layout->mines[y*w+x]) {
2078 * The player has landed on a mine. Bad luck. Expose the
2079 * mine that killed them, but not the rest (in case they
2080 * want to Undo and carry on playing).
2083 state->grid[y*w+x] = 65;
2088 * Otherwise, the player has opened a safe square. Mark it to-do.
2090 state->grid[y*w+x] = -10; /* `todo' value internal to this func */
2093 * Now go through the grid finding all `todo' values and
2094 * opening them. Every time one of them turns out to have no
2095 * neighbouring mines, we add all its unopened neighbours to
2098 * FIXME: We really ought to be able to do this better than
2099 * using repeated N^2 scans of the grid.
2102 int done_something = FALSE;
2104 for (yy = 0; yy < h; yy++)
2105 for (xx = 0; xx < w; xx++)
2106 if (state->grid[yy*w+xx] == -10) {
2109 assert(!state->layout->mines[yy*w+xx]);
2113 for (dx = -1; dx <= +1; dx++)
2114 for (dy = -1; dy <= +1; dy++)
2115 if (xx+dx >= 0 && xx+dx < state->w &&
2116 yy+dy >= 0 && yy+dy < state->h &&
2117 state->layout->mines[(yy+dy)*w+(xx+dx)])
2120 state->grid[yy*w+xx] = v;
2123 for (dx = -1; dx <= +1; dx++)
2124 for (dy = -1; dy <= +1; dy++)
2125 if (xx+dx >= 0 && xx+dx < state->w &&
2126 yy+dy >= 0 && yy+dy < state->h &&
2127 state->grid[(yy+dy)*w+(xx+dx)] == -2)
2128 state->grid[(yy+dy)*w+(xx+dx)] = -10;
2131 done_something = TRUE;
2134 if (!done_something)
2139 * Finally, scan the grid and see if exactly as many squares
2140 * are still covered as there are mines. If so, set the `won'
2141 * flag and fill in mine markers on all covered squares.
2143 nmines = ncovered = 0;
2144 for (yy = 0; yy < h; yy++)
2145 for (xx = 0; xx < w; xx++) {
2146 if (state->grid[yy*w+xx] < 0)
2148 if (state->layout->mines[yy*w+xx])
2151 assert(ncovered >= nmines);
2152 if (ncovered == nmines) {
2153 for (yy = 0; yy < h; yy++)
2154 for (xx = 0; xx < w; xx++) {
2155 if (state->grid[yy*w+xx] < 0)
2156 state->grid[yy*w+xx] = -1;
2164 static game_state *new_game(midend *me, const game_params *params,
2167 game_state *state = snew(game_state);
2168 int i, wh, x, y, masked;
2171 state->w = params->w;
2172 state->h = params->h;
2173 state->n = params->n;
2174 state->dead = state->won = FALSE;
2175 state->used_solve = FALSE;
2177 wh = state->w * state->h;
2179 state->layout = snew(struct mine_layout);
2180 memset(state->layout, 0, sizeof(struct mine_layout));
2181 state->layout->refcount = 1;
2183 state->grid = snewn(wh, signed char);
2184 memset(state->grid, -2, wh);
2188 state->layout->n = atoi(desc);
2189 while (*desc && isdigit((unsigned char)*desc))
2190 desc++; /* skip over mine count */
2191 if (*desc) desc++; /* eat comma */
2193 state->layout->unique = FALSE;
2195 state->layout->unique = TRUE;
2197 if (*desc) desc++; /* eat comma */
2199 state->layout->mines = NULL;
2200 state->layout->rs = random_state_decode(desc);
2201 state->layout->me = me;
2204 state->layout->rs = NULL;
2205 state->layout->me = NULL;
2206 state->layout->mines = snewn(wh, char);
2208 if (*desc && isdigit((unsigned char)*desc)) {
2210 while (*desc && isdigit((unsigned char)*desc))
2211 desc++; /* skip over x coordinate */
2212 if (*desc) desc++; /* eat comma */
2214 while (*desc && isdigit((unsigned char)*desc))
2215 desc++; /* skip over y coordinate */
2216 if (*desc) desc++; /* eat comma */
2228 * We permit game IDs to be entered by hand without the
2229 * masking transformation.
2234 bmp = snewn((wh + 7) / 8, unsigned char);
2235 memset(bmp, 0, (wh + 7) / 8);
2236 for (i = 0; i < (wh+3)/4; i++) {
2240 assert(c != 0); /* validate_desc should have caught */
2241 if (c >= '0' && c <= '9')
2243 else if (c >= 'a' && c <= 'f')
2245 else if (c >= 'A' && c <= 'F')
2250 bmp[i / 2] |= v << (4 * (1 - (i % 2)));
2254 obfuscate_bitmap(bmp, wh, TRUE);
2256 memset(state->layout->mines, 0, wh);
2257 for (i = 0; i < wh; i++) {
2258 if (bmp[i / 8] & (0x80 >> (i % 8)))
2259 state->layout->mines[i] = 1;
2262 if (x >= 0 && y >= 0)
2263 open_square(state, x, y);
2270 static game_state *dup_game(const game_state *state)
2272 game_state *ret = snew(game_state);
2277 ret->dead = state->dead;
2278 ret->won = state->won;
2279 ret->used_solve = state->used_solve;
2280 ret->layout = state->layout;
2281 ret->layout->refcount++;
2282 ret->grid = snewn(ret->w * ret->h, signed char);
2283 memcpy(ret->grid, state->grid, ret->w * ret->h);
2288 static void free_game(game_state *state)
2290 if (--state->layout->refcount <= 0) {
2291 sfree(state->layout->mines);
2292 if (state->layout->rs)
2293 random_free(state->layout->rs);
2294 sfree(state->layout);
2300 static char *solve_game(const game_state *state, const game_state *currstate,
2301 const char *aux, const char **error)
2303 if (!state->layout->mines) {
2304 *error = "Game has not been started yet";
2311 static int game_can_format_as_text_now(const game_params *params)
2316 static char *game_text_format(const game_state *state)
2321 ret = snewn((state->w + 1) * state->h + 1, char);
2322 for (y = 0; y < state->h; y++) {
2323 for (x = 0; x < state->w; x++) {
2324 int v = state->grid[y*state->w+x];
2327 else if (v >= 1 && v <= 8)
2331 else if (v == -2 || v == -3)
2335 ret[y * (state->w+1) + x] = v;
2337 ret[y * (state->w+1) + state->w] = '\n';
2339 ret[(state->w + 1) * state->h] = '\0';
2345 int hx, hy, hradius; /* for mouse-down highlights */
2348 int deaths, completed;
2349 int cur_x, cur_y, cur_visible;
2352 static game_ui *new_ui(const game_state *state)
2354 game_ui *ui = snew(game_ui);
2355 ui->hx = ui->hy = -1;
2356 ui->hradius = ui->validradius = 0;
2358 ui->completed = FALSE;
2359 ui->flash_is_death = FALSE; /* *shrug* */
2360 ui->cur_x = ui->cur_y = ui->cur_visible = 0;
2364 static void free_ui(game_ui *ui)
2369 static char *encode_ui(const game_ui *ui)
2373 * The deaths counter and completion status need preserving
2374 * across a serialisation.
2376 sprintf(buf, "D%d", ui->deaths);
2382 static void decode_ui(game_ui *ui, const char *encoding)
2385 sscanf(encoding, "D%d%n", &ui->deaths, &p);
2386 if (encoding[p] == 'C')
2387 ui->completed = TRUE;
2390 static void game_changed_state(game_ui *ui, const game_state *oldstate,
2391 const game_state *newstate)
2394 ui->completed = TRUE;
2397 struct game_drawstate {
2398 int w, h, started, tilesize, bg;
2401 * Items in this `grid' array have all the same values as in
2402 * the game_state grid, and in addition:
2404 * - -10 means the tile was drawn `specially' as a result of a
2405 * flash, so it will always need redrawing.
2407 * - -22 and -23 mean the tile is highlighted for a possible
2410 int cur_x, cur_y; /* -1, -1 for no cursor displayed. */
2413 static char *interpret_move(const game_state *from, game_ui *ui,
2414 const game_drawstate *ds,
2415 int x, int y, int button)
2420 if (from->dead || from->won)
2421 return NULL; /* no further moves permitted */
2426 if (IS_CURSOR_MOVE(button)) {
2427 move_cursor(button, &ui->cur_x, &ui->cur_y, from->w, from->h, 0);
2428 ui->cur_visible = 1;
2431 if (IS_CURSOR_SELECT(button)) {
2432 int v = from->grid[ui->cur_y * from->w + ui->cur_x];
2434 if (!ui->cur_visible) {
2435 ui->cur_visible = 1;
2438 if (button == CURSOR_SELECT2) {
2439 /* As for RIGHT_BUTTON; only works on covered square. */
2440 if (v != -2 && v != -1)
2442 sprintf(buf, "F%d,%d", ui->cur_x, ui->cur_y);
2445 /* Otherwise, treat as LEFT_BUTTON, for a single square. */
2446 if (v == -2 || v == -3) {
2447 if (from->layout->mines &&
2448 from->layout->mines[ui->cur_y * from->w + ui->cur_x])
2451 sprintf(buf, "O%d,%d", ui->cur_x, ui->cur_y);
2454 cx = ui->cur_x; cy = ui->cur_y;
2455 ui->validradius = 1;
2459 if (button == LEFT_BUTTON || button == LEFT_DRAG ||
2460 button == MIDDLE_BUTTON || button == MIDDLE_DRAG) {
2461 if (cx < 0 || cx >= from->w || cy < 0 || cy >= from->h)
2465 * Mouse-downs and mouse-drags just cause highlighting
2470 ui->hradius = (from->grid[cy*from->w+cx] >= 0 ? 1 : 0);
2471 if (button == LEFT_BUTTON)
2472 ui->validradius = ui->hradius;
2473 else if (button == MIDDLE_BUTTON)
2474 ui->validradius = 1;
2475 ui->cur_visible = 0;
2479 if (button == RIGHT_BUTTON) {
2480 if (cx < 0 || cx >= from->w || cy < 0 || cy >= from->h)
2484 * Right-clicking only works on a covered square, and it
2485 * toggles between -1 (marked as mine) and -2 (not marked
2488 * FIXME: question marks.
2490 if (from->grid[cy * from->w + cx] != -2 &&
2491 from->grid[cy * from->w + cx] != -1)
2494 sprintf(buf, "F%d,%d", cx, cy);
2498 if (button == LEFT_RELEASE || button == MIDDLE_RELEASE) {
2499 ui->hx = ui->hy = -1;
2503 * At this stage we must never return NULL: we have adjusted
2504 * the ui, so at worst we return UI_UPDATE.
2506 if (cx < 0 || cx >= from->w || cy < 0 || cy >= from->h)
2510 * Left-clicking on a covered square opens a tile. Not
2511 * permitted if the tile is marked as a mine, for safety.
2512 * (Unmark it and _then_ open it.)
2514 if (button == LEFT_RELEASE &&
2515 (from->grid[cy * from->w + cx] == -2 ||
2516 from->grid[cy * from->w + cx] == -3) &&
2517 ui->validradius == 0) {
2518 /* Check if you've killed yourself. */
2519 if (from->layout->mines && from->layout->mines[cy * from->w + cx])
2522 sprintf(buf, "O%d,%d", cx, cy);
2532 * Left-clicking or middle-clicking on an uncovered tile:
2533 * first we check to see if the number of mine markers
2534 * surrounding the tile is equal to its mine count, and if
2535 * so then we open all other surrounding squares.
2537 if (from->grid[cy * from->w + cx] > 0 && ui->validradius == 1) {
2540 /* Count mine markers. */
2542 for (dy = -1; dy <= +1; dy++)
2543 for (dx = -1; dx <= +1; dx++)
2544 if (cx+dx >= 0 && cx+dx < from->w &&
2545 cy+dy >= 0 && cy+dy < from->h) {
2546 if (from->grid[(cy+dy)*from->w+(cx+dx)] == -1)
2550 if (n == from->grid[cy * from->w + cx]) {
2553 * Now see if any of the squares we're clearing
2554 * contains a mine (which will happen iff you've
2555 * incorrectly marked the mines around the clicked
2556 * square). If so, we open _just_ those squares, to
2557 * reveal as little additional information as we
2561 const char *sep = "";
2563 for (dy = -1; dy <= +1; dy++)
2564 for (dx = -1; dx <= +1; dx++)
2565 if (cx+dx >= 0 && cx+dx < from->w &&
2566 cy+dy >= 0 && cy+dy < from->h) {
2567 if (from->grid[(cy+dy)*from->w+(cx+dx)] != -1 &&
2568 from->layout->mines &&
2569 from->layout->mines[(cy+dy)*from->w+(cx+dx)]) {
2570 p += sprintf(p, "%sO%d,%d", sep, cx+dx, cy+dy);
2578 sprintf(buf, "C%d,%d", cx, cy);
2589 static game_state *execute_move(const game_state *from, const char *move)
2594 if (!strcmp(move, "S")) {
2597 ret = dup_game(from);
2600 * If the player is still alive at the moment of pressing
2601 * Solve, expose the entire grid as if it were a completed
2604 for (yy = 0; yy < ret->h; yy++)
2605 for (xx = 0; xx < ret->w; xx++) {
2607 if (ret->layout->mines[yy*ret->w+xx]) {
2608 ret->grid[yy*ret->w+xx] = -1;
2614 for (dx = -1; dx <= +1; dx++)
2615 for (dy = -1; dy <= +1; dy++)
2616 if (xx+dx >= 0 && xx+dx < ret->w &&
2617 yy+dy >= 0 && yy+dy < ret->h &&
2618 ret->layout->mines[(yy+dy)*ret->w+(xx+dx)])
2621 ret->grid[yy*ret->w+xx] = v;
2626 * If the player pressed Solve _after dying_, show a full
2627 * corrections grid in the style of standard Minesweeper.
2628 * Players who don't like Mines's behaviour on death of
2629 * only showing the mine that killed you (so that in case
2630 * of a typo you can undo and carry on without the rest of
2631 * the grid being spoiled) can use this to get the display
2632 * that ordinary Minesweeper would have given them.
2634 for (yy = 0; yy < ret->h; yy++)
2635 for (xx = 0; xx < ret->w; xx++) {
2636 int pos = yy*ret->w+xx;
2637 if ((ret->grid[pos] == -2 || ret->grid[pos] == -3) &&
2638 ret->layout->mines[pos]) {
2639 ret->grid[pos] = 64;
2640 } else if (ret->grid[pos] == -1 &&
2641 !ret->layout->mines[pos]) {
2642 ret->grid[pos] = 66;
2646 ret->used_solve = TRUE;
2650 ret = dup_game(from);
2653 if (move[0] == 'F' &&
2654 sscanf(move+1, "%d,%d", &cx, &cy) == 2 &&
2655 cx >= 0 && cx < from->w && cy >= 0 && cy < from->h) {
2656 ret->grid[cy * from->w + cx] ^= (-2 ^ -1);
2657 } else if (move[0] == 'O' &&
2658 sscanf(move+1, "%d,%d", &cx, &cy) == 2 &&
2659 cx >= 0 && cx < from->w && cy >= 0 && cy < from->h) {
2660 open_square(ret, cx, cy);
2661 } else if (move[0] == 'C' &&
2662 sscanf(move+1, "%d,%d", &cx, &cy) == 2 &&
2663 cx >= 0 && cx < from->w && cy >= 0 && cy < from->h) {
2666 for (dy = -1; dy <= +1; dy++)
2667 for (dx = -1; dx <= +1; dx++)
2668 if (cx+dx >= 0 && cx+dx < ret->w &&
2669 cy+dy >= 0 && cy+dy < ret->h &&
2670 (ret->grid[(cy+dy)*ret->w+(cx+dx)] == -2 ||
2671 ret->grid[(cy+dy)*ret->w+(cx+dx)] == -3))
2672 open_square(ret, cx+dx, cy+dy);
2678 while (*move && *move != ';') move++;
2686 /* ----------------------------------------------------------------------
2690 static void game_compute_size(const game_params *params, int tilesize,
2693 /* Ick: fake up `ds->tilesize' for macro expansion purposes */
2694 struct { int tilesize; } ads, *ds = &ads;
2695 ads.tilesize = tilesize;
2697 *x = BORDER * 2 + TILE_SIZE * params->w;
2698 *y = BORDER * 2 + TILE_SIZE * params->h;
2701 static void game_set_size(drawing *dr, game_drawstate *ds,
2702 const game_params *params, int tilesize)
2704 ds->tilesize = tilesize;
2707 static float *game_colours(frontend *fe, int *ncolours)
2709 float *ret = snewn(3 * NCOLOURS, float);
2711 frontend_default_colour(fe, &ret[COL_BACKGROUND * 3]);
2713 ret[COL_BACKGROUND2 * 3 + 0] = ret[COL_BACKGROUND * 3 + 0] * 19.0F / 20.0F;
2714 ret[COL_BACKGROUND2 * 3 + 1] = ret[COL_BACKGROUND * 3 + 1] * 19.0F / 20.0F;
2715 ret[COL_BACKGROUND2 * 3 + 2] = ret[COL_BACKGROUND * 3 + 2] * 19.0F / 20.0F;
2717 ret[COL_1 * 3 + 0] = 0.0F;
2718 ret[COL_1 * 3 + 1] = 0.0F;
2719 ret[COL_1 * 3 + 2] = 1.0F;
2721 ret[COL_2 * 3 + 0] = 0.0F;
2722 ret[COL_2 * 3 + 1] = 0.5F;
2723 ret[COL_2 * 3 + 2] = 0.0F;
2725 ret[COL_3 * 3 + 0] = 1.0F;
2726 ret[COL_3 * 3 + 1] = 0.0F;
2727 ret[COL_3 * 3 + 2] = 0.0F;
2729 ret[COL_4 * 3 + 0] = 0.0F;
2730 ret[COL_4 * 3 + 1] = 0.0F;
2731 ret[COL_4 * 3 + 2] = 0.5F;
2733 ret[COL_5 * 3 + 0] = 0.5F;
2734 ret[COL_5 * 3 + 1] = 0.0F;
2735 ret[COL_5 * 3 + 2] = 0.0F;
2737 ret[COL_6 * 3 + 0] = 0.0F;
2738 ret[COL_6 * 3 + 1] = 0.5F;
2739 ret[COL_6 * 3 + 2] = 0.5F;
2741 ret[COL_7 * 3 + 0] = 0.0F;
2742 ret[COL_7 * 3 + 1] = 0.0F;
2743 ret[COL_7 * 3 + 2] = 0.0F;
2745 ret[COL_8 * 3 + 0] = 0.5F;
2746 ret[COL_8 * 3 + 1] = 0.5F;
2747 ret[COL_8 * 3 + 2] = 0.5F;
2749 ret[COL_MINE * 3 + 0] = 0.0F;
2750 ret[COL_MINE * 3 + 1] = 0.0F;
2751 ret[COL_MINE * 3 + 2] = 0.0F;
2753 ret[COL_BANG * 3 + 0] = 1.0F;
2754 ret[COL_BANG * 3 + 1] = 0.0F;
2755 ret[COL_BANG * 3 + 2] = 0.0F;
2757 ret[COL_CROSS * 3 + 0] = 1.0F;
2758 ret[COL_CROSS * 3 + 1] = 0.0F;
2759 ret[COL_CROSS * 3 + 2] = 0.0F;
2761 ret[COL_FLAG * 3 + 0] = 1.0F;
2762 ret[COL_FLAG * 3 + 1] = 0.0F;
2763 ret[COL_FLAG * 3 + 2] = 0.0F;
2765 ret[COL_FLAGBASE * 3 + 0] = 0.0F;
2766 ret[COL_FLAGBASE * 3 + 1] = 0.0F;
2767 ret[COL_FLAGBASE * 3 + 2] = 0.0F;
2769 ret[COL_QUERY * 3 + 0] = 0.0F;
2770 ret[COL_QUERY * 3 + 1] = 0.0F;
2771 ret[COL_QUERY * 3 + 2] = 0.0F;
2773 ret[COL_HIGHLIGHT * 3 + 0] = 1.0F;
2774 ret[COL_HIGHLIGHT * 3 + 1] = 1.0F;
2775 ret[COL_HIGHLIGHT * 3 + 2] = 1.0F;
2777 ret[COL_LOWLIGHT * 3 + 0] = ret[COL_BACKGROUND * 3 + 0] * 2.0F / 3.0F;
2778 ret[COL_LOWLIGHT * 3 + 1] = ret[COL_BACKGROUND * 3 + 1] * 2.0F / 3.0F;
2779 ret[COL_LOWLIGHT * 3 + 2] = ret[COL_BACKGROUND * 3 + 2] * 2.0F / 3.0F;
2781 ret[COL_WRONGNUMBER * 3 + 0] = 1.0F;
2782 ret[COL_WRONGNUMBER * 3 + 1] = 0.6F;
2783 ret[COL_WRONGNUMBER * 3 + 2] = 0.6F;
2785 /* Red tinge to a light colour, for the cursor. */
2786 ret[COL_CURSOR * 3 + 0] = ret[COL_HIGHLIGHT * 3 + 0];
2787 ret[COL_CURSOR * 3 + 1] = ret[COL_HIGHLIGHT * 3 + 0] / 2.0F;
2788 ret[COL_CURSOR * 3 + 2] = ret[COL_HIGHLIGHT * 3 + 0] / 2.0F;
2790 *ncolours = NCOLOURS;
2794 static game_drawstate *game_new_drawstate(drawing *dr, const game_state *state)
2796 struct game_drawstate *ds = snew(struct game_drawstate);
2800 ds->started = FALSE;
2801 ds->tilesize = 0; /* not decided yet */
2802 ds->grid = snewn(ds->w * ds->h, signed char);
2804 ds->cur_x = ds->cur_y = -1;
2806 memset(ds->grid, -99, ds->w * ds->h);
2811 static void game_free_drawstate(drawing *dr, game_drawstate *ds)
2817 static void draw_tile(drawing *dr, game_drawstate *ds,
2818 int x, int y, int v, int bg)
2824 if (v == -22 || v == -23) {
2828 * Omit the highlights in this case.
2830 draw_rect(dr, x, y, TILE_SIZE, TILE_SIZE,
2831 bg == COL_BACKGROUND ? COL_BACKGROUND2 : bg);
2832 draw_line(dr, x, y, x + TILE_SIZE - 1, y, COL_LOWLIGHT);
2833 draw_line(dr, x, y, x, y + TILE_SIZE - 1, COL_LOWLIGHT);
2836 * Draw highlights to indicate the square is covered.
2838 coords[0] = x + TILE_SIZE - 1;
2839 coords[1] = y + TILE_SIZE - 1;
2840 coords[2] = x + TILE_SIZE - 1;
2843 coords[5] = y + TILE_SIZE - 1;
2844 draw_polygon(dr, coords, 3, COL_LOWLIGHT ^ hl, COL_LOWLIGHT ^ hl);
2848 draw_polygon(dr, coords, 3, COL_HIGHLIGHT ^ hl,
2849 COL_HIGHLIGHT ^ hl);
2851 draw_rect(dr, x + HIGHLIGHT_WIDTH, y + HIGHLIGHT_WIDTH,
2852 TILE_SIZE - 2*HIGHLIGHT_WIDTH, TILE_SIZE - 2*HIGHLIGHT_WIDTH,
2860 #define SETCOORD(n, dx, dy) do { \
2861 coords[(n)*2+0] = x + (int)(TILE_SIZE * (dx)); \
2862 coords[(n)*2+1] = y + (int)(TILE_SIZE * (dy)); \
2864 SETCOORD(0, 0.6F, 0.35F);
2865 SETCOORD(1, 0.6F, 0.7F);
2866 SETCOORD(2, 0.8F, 0.8F);
2867 SETCOORD(3, 0.25F, 0.8F);
2868 SETCOORD(4, 0.55F, 0.7F);
2869 SETCOORD(5, 0.55F, 0.35F);
2870 draw_polygon(dr, coords, 6, COL_FLAGBASE, COL_FLAGBASE);
2872 SETCOORD(0, 0.6F, 0.2F);
2873 SETCOORD(1, 0.6F, 0.5F);
2874 SETCOORD(2, 0.2F, 0.35F);
2875 draw_polygon(dr, coords, 3, COL_FLAG, COL_FLAG);
2878 } else if (v == -3) {
2880 * Draw a question mark.
2882 draw_text(dr, x + TILE_SIZE / 2, y + TILE_SIZE / 2,
2883 FONT_VARIABLE, TILE_SIZE * 6 / 8,
2884 ALIGN_VCENTRE | ALIGN_HCENTRE,
2889 * Clear the square to the background colour, and draw thin
2890 * grid lines along the top and left.
2892 * Exception is that for value 65 (mine we've just trodden
2893 * on), we clear the square to COL_BANG.
2896 bg = COL_WRONGNUMBER;
2899 draw_rect(dr, x, y, TILE_SIZE, TILE_SIZE,
2900 (v == 65 ? COL_BANG :
2901 bg == COL_BACKGROUND ? COL_BACKGROUND2 : bg));
2902 draw_line(dr, x, y, x + TILE_SIZE - 1, y, COL_LOWLIGHT);
2903 draw_line(dr, x, y, x, y + TILE_SIZE - 1, COL_LOWLIGHT);
2905 if (v > 0 && v <= 8) {
2912 draw_text(dr, x + TILE_SIZE / 2, y + TILE_SIZE / 2,
2913 FONT_VARIABLE, TILE_SIZE * 7 / 8,
2914 ALIGN_VCENTRE | ALIGN_HCENTRE,
2915 (COL_1 - 1) + v, str);
2917 } else if (v >= 64) {
2922 int cx = x + TILE_SIZE / 2;
2923 int cy = y + TILE_SIZE / 2;
2924 int r = TILE_SIZE / 2 - 3;
2926 draw_circle(dr, cx, cy, 5*r/6, COL_MINE, COL_MINE);
2927 draw_rect(dr, cx - r/6, cy - r, 2*(r/6)+1, 2*r+1, COL_MINE);
2928 draw_rect(dr, cx - r, cy - r/6, 2*r+1, 2*(r/6)+1, COL_MINE);
2929 draw_rect(dr, cx-r/3, cy-r/3, r/3, r/4, COL_HIGHLIGHT);
2934 * Cross through the mine.
2937 for (dx = -1; dx <= +1; dx++) {
2938 draw_line(dr, x + 3 + dx, y + 2,
2939 x + TILE_SIZE - 3 + dx,
2940 y + TILE_SIZE - 2, COL_CROSS);
2941 draw_line(dr, x + TILE_SIZE - 3 + dx, y + 2,
2942 x + 3 + dx, y + TILE_SIZE - 2,
2949 draw_update(dr, x, y, TILE_SIZE, TILE_SIZE);
2952 static void game_redraw(drawing *dr, game_drawstate *ds,
2953 const game_state *oldstate, const game_state *state,
2954 int dir, const game_ui *ui,
2955 float animtime, float flashtime)
2958 int mines, markers, closed, bg;
2959 int cx = -1, cy = -1, cmoved;
2962 int frame = (int)(flashtime / FLASH_FRAME);
2964 bg = (ui->flash_is_death ? COL_BACKGROUND : COL_LOWLIGHT);
2966 bg = (ui->flash_is_death ? COL_BANG : COL_HIGHLIGHT);
2968 bg = COL_BACKGROUND;
2974 TILE_SIZE * state->w + 2 * BORDER,
2975 TILE_SIZE * state->h + 2 * BORDER, COL_BACKGROUND);
2976 draw_update(dr, 0, 0,
2977 TILE_SIZE * state->w + 2 * BORDER,
2978 TILE_SIZE * state->h + 2 * BORDER);
2981 * Recessed area containing the whole puzzle.
2983 coords[0] = COORD(state->w) + OUTER_HIGHLIGHT_WIDTH - 1;
2984 coords[1] = COORD(state->h) + OUTER_HIGHLIGHT_WIDTH - 1;
2985 coords[2] = COORD(state->w) + OUTER_HIGHLIGHT_WIDTH - 1;
2986 coords[3] = COORD(0) - OUTER_HIGHLIGHT_WIDTH;
2987 coords[4] = coords[2] - TILE_SIZE;
2988 coords[5] = coords[3] + TILE_SIZE;
2989 coords[8] = COORD(0) - OUTER_HIGHLIGHT_WIDTH;
2990 coords[9] = COORD(state->h) + OUTER_HIGHLIGHT_WIDTH - 1;
2991 coords[6] = coords[8] + TILE_SIZE;
2992 coords[7] = coords[9] - TILE_SIZE;
2993 draw_polygon(dr, coords, 5, COL_HIGHLIGHT, COL_HIGHLIGHT);
2995 coords[1] = COORD(0) - OUTER_HIGHLIGHT_WIDTH;
2996 coords[0] = COORD(0) - OUTER_HIGHLIGHT_WIDTH;
2997 draw_polygon(dr, coords, 5, COL_LOWLIGHT, COL_LOWLIGHT);
3002 if (ui->cur_visible) cx = ui->cur_x;
3003 if (ui->cur_visible) cy = ui->cur_y;
3004 cmoved = (cx != ds->cur_x || cy != ds->cur_y);
3007 * Now draw the tiles. Also in this loop, count up the number
3008 * of mines, mine markers, and closed squares.
3010 mines = markers = closed = 0;
3011 for (y = 0; y < ds->h; y++)
3012 for (x = 0; x < ds->w; x++) {
3013 int v = state->grid[y*ds->w+x], cc = 0;
3019 if (state->layout->mines && state->layout->mines[y*ds->w+x])
3022 if (v >= 0 && v <= 8) {
3024 * Count up the flags around this tile, and if
3025 * there are too _many_, highlight the tile.
3027 int dx, dy, flags = 0;
3029 for (dy = -1; dy <= +1; dy++)
3030 for (dx = -1; dx <= +1; dx++) {
3031 int nx = x+dx, ny = y+dy;
3032 if (nx >= 0 && nx < ds->w &&
3033 ny >= 0 && ny < ds->h &&
3034 state->grid[ny*ds->w+nx] == -1)
3042 if ((v == -2 || v == -3) &&
3043 (abs(x-ui->hx) <= ui->hradius && abs(y-ui->hy) <= ui->hradius))
3046 if (cmoved && /* if cursor has moved, force redraw of curr and prev pos */
3047 ((x == cx && y == cy) || (x == ds->cur_x && y == ds->cur_y)))
3050 if (ds->grid[y*ds->w+x] != v || bg != ds->bg || cc) {
3051 draw_tile(dr, ds, COORD(x), COORD(y), v,
3052 (x == cx && y == cy) ? COL_CURSOR : bg);
3053 ds->grid[y*ds->w+x] = v;
3057 ds->cur_x = cx; ds->cur_y = cy;
3059 if (!state->layout->mines)
3060 mines = state->layout->n;
3063 * Update the status bar.
3066 char statusbar[512];
3068 sprintf(statusbar, "DEAD!");
3069 } else if (state->won) {
3070 if (state->used_solve)
3071 sprintf(statusbar, "Auto-solved.");
3073 sprintf(statusbar, "COMPLETED!");
3075 int safe_closed = closed - mines;
3076 sprintf(statusbar, "Marked: %d / %d", markers, mines);
3077 if (safe_closed > 0 && safe_closed <= 9) {
3079 * In the situation where there's a very small number
3080 * of _non_-mine squares left unopened, it's helpful
3081 * to mention that number in the status line, to save
3082 * the player from having to count it up
3083 * painstakingly. This is particularly important if
3084 * the player has turned up the mine density to the
3085 * point where game generation resorts to its weird
3086 * pathological fallback of a very dense mine area
3087 * with a clearing in the middle, because that often
3088 * leads to a deduction you can only make by knowing
3089 * that there is (say) exactly one non-mine square to
3090 * find, and it's a real pain to have to count up two
3091 * large numbers of squares and subtract them to get
3094 * The threshold value of 8 for displaying this
3095 * information is because that's the largest number of
3096 * non-mine squares that might conceivably fit around
3097 * a single central square, and the most likely way to
3098 * _use_ this information is to observe that if all
3099 * the remaining safe squares are adjacent to _this_
3100 * square then everything else can be immediately
3101 * flagged as a mine.
3103 if (safe_closed == 1) {
3104 sprintf(statusbar + strlen(statusbar),
3105 " (1 safe square remains)");
3107 sprintf(statusbar + strlen(statusbar),
3108 " (%d safe squares remain)", safe_closed);
3113 sprintf(statusbar + strlen(statusbar),
3114 " Deaths: %d", ui->deaths);
3115 status_bar(dr, statusbar);
3119 static float game_anim_length(const game_state *oldstate,
3120 const game_state *newstate, int dir, game_ui *ui)
3125 static float game_flash_length(const game_state *oldstate,
3126 const game_state *newstate, int dir, game_ui *ui)
3128 if (oldstate->used_solve || newstate->used_solve)
3131 if (dir > 0 && !oldstate->dead && !oldstate->won) {
3132 if (newstate->dead) {
3133 ui->flash_is_death = TRUE;
3134 return 3 * FLASH_FRAME;
3136 if (newstate->won) {
3137 ui->flash_is_death = FALSE;
3138 return 2 * FLASH_FRAME;
3144 static int game_status(const game_state *state)
3147 * We report the game as lost only if the player has used the
3148 * Solve function to reveal all the mines. Otherwise, we assume
3149 * they'll undo and continue play.
3151 return state->won ? (state->used_solve ? -1 : +1) : 0;
3154 static int game_timing_state(const game_state *state, game_ui *ui)
3156 if (state->dead || state->won || ui->completed || !state->layout->mines)
3161 static void game_print_size(const game_params *params, float *x, float *y)
3165 static void game_print(drawing *dr, const game_state *state, int tilesize)
3170 #define thegame mines
3173 const struct game thegame = {
3174 "Mines", "games.mines", "mines",
3176 game_fetch_preset, NULL,
3181 TRUE, game_configure, custom_params,
3189 TRUE, game_can_format_as_text_now, game_text_format,
3197 PREFERRED_TILE_SIZE, game_compute_size, game_set_size,
3200 game_free_drawstate,
3205 FALSE, FALSE, game_print_size, game_print,
3206 TRUE, /* wants_statusbar */
3207 TRUE, game_timing_state,
3208 BUTTON_BEATS(LEFT_BUTTON, RIGHT_BUTTON) | REQUIRE_RBUTTON,
3211 #ifdef STANDALONE_OBFUSCATOR
3214 * Vaguely useful stand-alone program which translates between
3215 * obfuscated and clear Mines game descriptions. Pass in a game
3216 * description on the command line, and if it's clear it will be
3217 * obfuscated and vice versa. The output text should also be a
3218 * valid game ID describing the same game. Like this:
3220 * $ ./mineobfusc 9x9:4,4,mb071b49fbd1cb6a0d5868
3221 * 9x9:4,4,004000007c00010022080
3222 * $ ./mineobfusc 9x9:4,4,004000007c00010022080
3223 * 9x9:4,4,mb071b49fbd1cb6a0d5868
3226 int main(int argc, char **argv)
3230 char *id = NULL, *desc;
3234 while (--argc > 0) {
3237 fprintf(stderr, "%s: unrecognised option `%s'\n", argv[0], p);
3245 fprintf(stderr, "usage: %s <game_id>\n", argv[0]);
3249 desc = strchr(id, ':');
3251 fprintf(stderr, "%s: game id expects a colon in it\n", argv[0]);
3256 p = default_params();
3257 decode_params(p, id);
3258 err = validate_desc(p, desc);
3260 fprintf(stderr, "%s: %s\n", argv[0], err);
3263 s = new_game(NULL, p, desc);
3266 while (*desc && *desc != ',') desc++;
3269 while (*desc && *desc != ',') desc++;
3272 printf("%s:%s\n", id, describe_layout(s->layout->mines,
3282 /* vim: set shiftwidth=4 tabstop=8: */