2 * mines.c: Minesweeper clone with sophisticated grid generation.
6 * - possibly disable undo? Or alternatively mark game states as
7 * `cheated', although that's horrid.
8 * + OK. Rather than _disabling_ undo, we have a hook callable
9 * in the game backend which is called before we do an undo.
10 * That hook can talk to the game_ui and set the cheated flag,
11 * and then make_move can avoid setting the `won' flag after that.
13 * - question marks (arrgh, preferences?)
15 * - sensible parameter constraints
16 * + 30x16: 191 mines just about works if rather slowly, 192 is
17 * just about doom (the latter corresponding to a density of
19 * + 9x9: 45 mines works - over 1 in 2! 50 seems a bit slow.
20 * + it might not be feasible to work out the exact limit
35 COL_1, COL_2, COL_3, COL_4, COL_5, COL_6, COL_7, COL_8,
36 COL_MINE, COL_BANG, COL_CROSS, COL_FLAG, COL_FLAGBASE, COL_QUERY,
37 COL_HIGHLIGHT, COL_LOWLIGHT,
42 #define BORDER (TILE_SIZE * 3 / 2)
43 #define HIGHLIGHT_WIDTH 2
44 #define OUTER_HIGHLIGHT_WIDTH 3
45 #define COORD(x) ( (x) * TILE_SIZE + BORDER )
46 #define FROMCOORD(x) ( ((x) - BORDER + TILE_SIZE) / TILE_SIZE - 1 )
48 #define FLASH_FRAME 0.13F
57 * This structure is shared between all the game_states for a
58 * given instance of the puzzle, so we reference-count it.
63 * If we haven't yet actually generated the mine layout, here's
64 * all the data we will need to do so.
68 midend_data *me; /* to give back the new game desc */
72 int w, h, n, dead, won;
73 struct mine_layout *layout; /* real mine positions */
74 char *grid; /* player knowledge */
76 * Each item in the `grid' array is one of the following values:
78 * - 0 to 8 mean the square is open and has a surrounding mine
81 * - -1 means the square is marked as a mine.
83 * - -2 means the square is unknown.
85 * - -3 means the square is marked with a question mark
86 * (FIXME: do we even want to bother with this?).
88 * - 64 means the square has had a mine revealed when the game
91 * - 65 means the square had a mine revealed and this was the
92 * one the player hits.
94 * - 66 means the square has a crossed-out mine because the
95 * player had incorrectly marked it.
99 static game_params *default_params(void)
101 game_params *ret = snew(game_params);
110 static int game_fetch_preset(int i, char **name, game_params **params)
114 static const struct { int w, h, n; } values[] = {
120 if (i < 0 || i >= lenof(values))
123 ret = snew(game_params);
124 ret->w = values[i].w;
125 ret->h = values[i].h;
126 ret->n = values[i].n;
129 sprintf(str, "%dx%d, %d mines", ret->w, ret->h, ret->n);
136 static void free_params(game_params *params)
141 static game_params *dup_params(game_params *params)
143 game_params *ret = snew(game_params);
144 *ret = *params; /* structure copy */
148 static void decode_params(game_params *params, char const *string)
150 char const *p = string;
153 while (*p && isdigit((unsigned char)*p)) p++;
157 while (*p && isdigit((unsigned char)*p)) p++;
159 params->h = params->w;
164 while (*p && (*p == '.' || isdigit((unsigned char)*p))) p++;
166 params->n = params->w * params->h / 10;
172 params->unique = FALSE;
174 p++; /* skip any other gunk */
178 static char *encode_params(game_params *params, int full)
183 len = sprintf(ret, "%dx%d", params->w, params->h);
185 * Mine count is a generation-time parameter, since it can be
186 * deduced from the mine bitmap!
189 len += sprintf(ret+len, "n%d", params->n);
190 if (full && !params->unique)
192 assert(len < lenof(ret));
198 static config_item *game_configure(game_params *params)
203 ret = snewn(5, config_item);
205 ret[0].name = "Width";
206 ret[0].type = C_STRING;
207 sprintf(buf, "%d", params->w);
208 ret[0].sval = dupstr(buf);
211 ret[1].name = "Height";
212 ret[1].type = C_STRING;
213 sprintf(buf, "%d", params->h);
214 ret[1].sval = dupstr(buf);
217 ret[2].name = "Mines";
218 ret[2].type = C_STRING;
219 sprintf(buf, "%d", params->n);
220 ret[2].sval = dupstr(buf);
223 ret[3].name = "Ensure solubility";
224 ret[3].type = C_BOOLEAN;
226 ret[3].ival = params->unique;
236 static game_params *custom_params(config_item *cfg)
238 game_params *ret = snew(game_params);
240 ret->w = atoi(cfg[0].sval);
241 ret->h = atoi(cfg[1].sval);
242 ret->n = atoi(cfg[2].sval);
243 if (strchr(cfg[2].sval, '%'))
244 ret->n = ret->n * (ret->w * ret->h) / 100;
245 ret->unique = cfg[3].ival;
250 static char *validate_params(game_params *params)
252 if (params->w <= 0 && params->h <= 0)
253 return "Width and height must both be greater than zero";
255 return "Width must be greater than zero";
257 return "Height must be greater than zero";
258 if (params->n > params->w * params->h - 9)
259 return "Too many mines for grid size";
262 * FIXME: Need more constraints here. Not sure what the
263 * sensible limits for Minesweeper actually are. The limits
264 * probably ought to change, however, depending on uniqueness.
270 /* ----------------------------------------------------------------------
271 * Minesweeper solver, used to ensure the generated grids are
272 * solvable without having to take risks.
276 * Count the bits in a word. Only needs to cope with 16 bits.
278 static int bitcount16(int word)
280 word = ((word & 0xAAAA) >> 1) + (word & 0x5555);
281 word = ((word & 0xCCCC) >> 2) + (word & 0x3333);
282 word = ((word & 0xF0F0) >> 4) + (word & 0x0F0F);
283 word = ((word & 0xFF00) >> 8) + (word & 0x00FF);
289 * We use a tree234 to store a large number of small localised
290 * sets, each with a mine count. We also keep some of those sets
291 * linked together into a to-do list.
294 short x, y, mask, mines;
296 struct set *prev, *next;
299 static int setcmp(void *av, void *bv)
301 struct set *a = (struct set *)av;
302 struct set *b = (struct set *)bv;
306 else if (a->y > b->y)
308 else if (a->x < b->x)
310 else if (a->x > b->x)
312 else if (a->mask < b->mask)
314 else if (a->mask > b->mask)
322 struct set *todo_head, *todo_tail;
325 static struct setstore *ss_new(void)
327 struct setstore *ss = snew(struct setstore);
328 ss->sets = newtree234(setcmp);
329 ss->todo_head = ss->todo_tail = NULL;
334 * Take two input sets, in the form (x,y,mask). Munge the first by
335 * taking either its intersection with the second or its difference
336 * with the second. Return the new mask part of the first set.
338 static int setmunge(int x1, int y1, int mask1, int x2, int y2, int mask2,
342 * Adjust the second set so that it has the same x,y
343 * coordinates as the first.
345 if (abs(x2-x1) >= 3 || abs(y2-y1) >= 3) {
349 mask2 &= ~(4|32|256);
359 mask2 &= ~(64|128|256);
371 * Invert the second set if `diff' is set (we're after A &~ B
372 * rather than A & B).
378 * Now all that's left is a logical AND.
380 return mask1 & mask2;
383 static void ss_add_todo(struct setstore *ss, struct set *s)
386 return; /* already on it */
388 #ifdef SOLVER_DIAGNOSTICS
389 printf("adding set on todo list: %d,%d %03x %d\n",
390 s->x, s->y, s->mask, s->mines);
393 s->prev = ss->todo_tail;
403 static void ss_add(struct setstore *ss, int x, int y, int mask, int mines)
410 * Normalise so that x and y are genuinely the bounding
413 while (!(mask & (1|8|64)))
415 while (!(mask & (1|2|4)))
419 * Create a set structure and add it to the tree.
421 s = snew(struct set);
427 if (add234(ss->sets, s) != s) {
429 * This set already existed! Free it and return.
436 * We've added a new set to the tree, so put it on the todo
442 static void ss_remove(struct setstore *ss, struct set *s)
444 struct set *next = s->next, *prev = s->prev;
446 #ifdef SOLVER_DIAGNOSTICS
447 printf("removing set %d,%d %03x\n", s->x, s->y, s->mask);
450 * Remove s from the todo list.
454 else if (s == ss->todo_head)
455 ss->todo_head = next;
459 else if (s == ss->todo_tail)
460 ss->todo_tail = prev;
465 * Remove s from the tree.
470 * Destroy the actual set structure.
476 * Return a dynamically allocated list of all the sets which
477 * overlap a provided input set.
479 static struct set **ss_overlap(struct setstore *ss, int x, int y, int mask)
481 struct set **ret = NULL;
482 int nret = 0, retsize = 0;
485 for (xx = x-3; xx < x+3; xx++)
486 for (yy = y-3; yy < y+3; yy++) {
491 * Find the first set with these top left coordinates.
497 if (findrelpos234(ss->sets, &stmp, NULL, REL234_GE, &pos)) {
498 while ((s = index234(ss->sets, pos)) != NULL &&
499 s->x == xx && s->y == yy) {
501 * This set potentially overlaps the input one.
502 * Compute the intersection to see if they
503 * really overlap, and add it to the list if
506 if (setmunge(x, y, mask, s->x, s->y, s->mask, FALSE)) {
508 * There's an overlap.
510 if (nret >= retsize) {
512 ret = sresize(ret, retsize, struct set *);
522 ret = sresize(ret, nret+1, struct set *);
529 * Get an element from the head of the set todo list.
531 static struct set *ss_todo(struct setstore *ss)
534 struct set *ret = ss->todo_head;
535 ss->todo_head = ret->next;
537 ss->todo_head->prev = NULL;
539 ss->todo_tail = NULL;
540 ret->next = ret->prev = NULL;
553 static void std_add(struct squaretodo *std, int i)
556 std->next[std->tail] = i;
563 static void known_squares(int w, int h, struct squaretodo *std, char *grid,
564 int (*open)(void *ctx, int x, int y), void *openctx,
565 int x, int y, int mask, int mine)
571 for (yy = 0; yy < 3; yy++)
572 for (xx = 0; xx < 3; xx++) {
574 int i = (y + yy) * w + (x + xx);
577 * It's possible that this square is _already_
578 * known, in which case we don't try to add it to
584 grid[i] = -1; /* and don't open it! */
586 grid[i] = open(openctx, x + xx, y + yy);
587 assert(grid[i] != -1); /* *bang* */
598 * This is data returned from the `perturb' function. It details
599 * which squares have become mines and which have become clear. The
600 * solver is (of course) expected to honourably not use that
601 * knowledge directly, but to efficently adjust its internal data
602 * structures and proceed based on only the information it
605 struct perturbation {
607 int delta; /* +1 == become a mine; -1 == cleared */
609 struct perturbations {
611 struct perturbation *changes;
615 * Main solver entry point. You give it a grid of existing
616 * knowledge (-1 for a square known to be a mine, 0-8 for empty
617 * squares with a given number of neighbours, -2 for completely
618 * unknown), plus a function which you can call to open new squares
619 * once you're confident of them. It fills in as much more of the
624 * - -1 means deduction stalled and nothing could be done
625 * - 0 means deduction succeeded fully
626 * - >0 means deduction succeeded but some number of perturbation
627 * steps were required; the exact return value is the number of
630 static int minesolve(int w, int h, int n, char *grid,
631 int (*open)(void *ctx, int x, int y),
632 struct perturbations *(*perturb)(void *ctx, char *grid,
633 int x, int y, int mask),
634 void *ctx, random_state *rs)
636 struct setstore *ss = ss_new();
638 struct squaretodo astd, *std = &astd;
643 * Set up a linked list of squares with known contents, so that
644 * we can process them one by one.
646 std->next = snewn(w*h, int);
647 std->head = std->tail = -1;
650 * Initialise that list with all known squares in the input
653 for (y = 0; y < h; y++) {
654 for (x = 0; x < w; x++) {
662 * Main deductive loop.
665 int done_something = FALSE;
669 * If there are any known squares on the todo list, process
670 * them and construct a set for each.
672 while (std->head != -1) {
674 #ifdef SOLVER_DIAGNOSTICS
675 printf("known square at %d,%d [%d]\n", i%w, i/w, grid[i]);
677 std->head = std->next[i];
685 int dx, dy, mines, bit, val;
686 #ifdef SOLVER_DIAGNOSTICS
687 printf("creating set around this square\n");
690 * Empty square. Construct the set of non-known squares
691 * around this one, and determine its mine count.
696 for (dy = -1; dy <= +1; dy++) {
697 for (dx = -1; dx <= +1; dx++) {
698 #ifdef SOLVER_DIAGNOSTICS
699 printf("grid %d,%d = %d\n", x+dx, y+dy, grid[i+dy*w+dx]);
701 if (x+dx < 0 || x+dx >= w || y+dy < 0 || y+dy >= h)
702 /* ignore this one */;
703 else if (grid[i+dy*w+dx] == -1)
705 else if (grid[i+dy*w+dx] == -2)
711 ss_add(ss, x-1, y-1, val, mines);
715 * Now, whether the square is empty or full, we must
716 * find any set which contains it and replace it with
717 * one which does not.
720 #ifdef SOLVER_DIAGNOSTICS
721 printf("finding sets containing known square %d,%d\n", x, y);
723 list = ss_overlap(ss, x, y, 1);
725 for (j = 0; list[j]; j++) {
726 int newmask, newmines;
731 * Compute the mask for this set minus the
732 * newly known square.
734 newmask = setmunge(s->x, s->y, s->mask, x, y, 1, TRUE);
737 * Compute the new mine count.
739 newmines = s->mines - (grid[i] == -1);
742 * Insert the new set into the collection,
743 * unless it's been whittled right down to
747 ss_add(ss, s->x, s->y, newmask, newmines);
750 * Destroy the old one; it is actually obsolete.
759 * Marking a fresh square as known certainly counts as
762 done_something = TRUE;
766 * Now pick a set off the to-do list and attempt deductions
769 if ((s = ss_todo(ss)) != NULL) {
771 #ifdef SOLVER_DIAGNOSTICS
772 printf("set to do: %d,%d %03x %d\n", s->x, s->y, s->mask, s->mines);
775 * Firstly, see if this set has a mine count of zero or
776 * of its own cardinality.
778 if (s->mines == 0 || s->mines == bitcount16(s->mask)) {
780 * If so, we can immediately mark all the squares
781 * in the set as known.
783 #ifdef SOLVER_DIAGNOSTICS
786 known_squares(w, h, std, grid, open, ctx,
787 s->x, s->y, s->mask, (s->mines != 0));
790 * Having done that, we need do nothing further
791 * with this set; marking all the squares in it as
792 * known will eventually eliminate it, and will
793 * also permit further deductions about anything
800 * Failing that, we now search through all the sets
801 * which overlap this one.
803 list = ss_overlap(ss, s->x, s->y, s->mask);
805 for (j = 0; list[j]; j++) {
806 struct set *s2 = list[j];
807 int swing, s2wing, swc, s2wc;
810 * Find the non-overlapping parts s2-s and s-s2,
811 * and their cardinalities.
813 * I'm going to refer to these parts as `wings'
814 * surrounding the central part common to both
815 * sets. The `s wing' is s-s2; the `s2 wing' is
818 swing = setmunge(s->x, s->y, s->mask, s2->x, s2->y, s2->mask,
820 s2wing = setmunge(s2->x, s2->y, s2->mask, s->x, s->y, s->mask,
822 swc = bitcount16(swing);
823 s2wc = bitcount16(s2wing);
826 * If one set has more mines than the other, and
827 * the number of extra mines is equal to the
828 * cardinality of that set's wing, then we can mark
829 * every square in the wing as a known mine, and
830 * every square in the other wing as known clear.
832 if (swc == s->mines - s2->mines ||
833 s2wc == s2->mines - s->mines) {
834 known_squares(w, h, std, grid, open, ctx,
836 (swc == s->mines - s2->mines));
837 known_squares(w, h, std, grid, open, ctx,
838 s2->x, s2->y, s2wing,
839 (s2wc == s2->mines - s->mines));
844 * Failing that, see if one set is a subset of the
845 * other. If so, we can divide up the mine count of
846 * the larger set between the smaller set and its
847 * complement, even if neither smaller set ends up
848 * being immediately clearable.
850 if (swc == 0 && s2wc != 0) {
851 /* s is a subset of s2. */
852 assert(s2->mines > s->mines);
853 ss_add(ss, s2->x, s2->y, s2wing, s2->mines - s->mines);
854 } else if (s2wc == 0 && swc != 0) {
855 /* s2 is a subset of s. */
856 assert(s->mines > s2->mines);
857 ss_add(ss, s->x, s->y, swing, s->mines - s2->mines);
864 * In this situation we have definitely done
865 * _something_, even if it's only reducing the size of
868 done_something = TRUE;
871 * We have nothing left on our todo list, which means
872 * all localised deductions have failed. Our next step
873 * is to resort to global deduction based on the total
874 * mine count. This is computationally expensive
875 * compared to any of the above deductions, which is
876 * why we only ever do it when all else fails, so that
877 * hopefully it won't have to happen too often.
879 * If you pass n<0 into this solver, that informs it
880 * that you do not know the total mine count, so it
881 * won't even attempt these deductions.
884 int minesleft, squaresleft;
885 int nsets, setused[10], cursor;
888 * Start by scanning the current grid state to work out
889 * how many unknown squares we still have, and how many
890 * mines are to be placed in them.
894 for (i = 0; i < w*h; i++) {
897 else if (grid[i] == -2)
901 #ifdef SOLVER_DIAGNOSTICS
902 printf("global deduction time: squaresleft=%d minesleft=%d\n",
903 squaresleft, minesleft);
904 for (y = 0; y < h; y++) {
905 for (x = 0; x < w; x++) {
921 * If there _are_ no unknown squares, we have actually
924 if (squaresleft == 0) {
925 assert(minesleft == 0);
930 * First really simple case: if there are no more mines
931 * left, or if there are exactly as many mines left as
932 * squares to play them in, then it's all easy.
934 if (minesleft == 0 || minesleft == squaresleft) {
935 for (i = 0; i < w*h; i++)
937 known_squares(w, h, std, grid, open, ctx,
938 i % w, i / w, 1, minesleft != 0);
939 continue; /* now go back to main deductive loop */
943 * Failing that, we have to do some _real_ work.
944 * Ideally what we do here is to try every single
945 * combination of the currently available sets, in an
946 * attempt to find a disjoint union (i.e. a set of
947 * squares with a known mine count between them) such
948 * that the remaining unknown squares _not_ contained
949 * in that union either contain no mines or are all
952 * Actually enumerating all 2^n possibilities will get
953 * a bit slow for large n, so I artificially cap this
954 * recursion at n=10 to avoid too much pain.
956 nsets = count234(ss->sets);
957 if (nsets <= lenof(setused)) {
959 * Doing this with actual recursive function calls
960 * would get fiddly because a load of local
961 * variables from this function would have to be
962 * passed down through the recursion. So instead
963 * I'm going to use a virtual recursion within this
964 * function. The way this works is:
966 * - we have an array `setused', such that
967 * setused[n] is 0 or 1 depending on whether set
968 * n is currently in the union we are
971 * - we have a value `cursor' which indicates how
972 * much of `setused' we have so far filled in.
973 * It's conceptually the recursion depth.
975 * We begin by setting `cursor' to zero. Then:
977 * - if cursor can advance, we advance it by one.
978 * We set the value in `setused' that it went
979 * past to 1 if that set is disjoint from
980 * anything else currently in `setused', or to 0
983 * - If cursor cannot advance because it has
984 * reached the end of the setused list, then we
985 * have a maximal disjoint union. Check to see
986 * whether its mine count has any useful
987 * properties. If so, mark all the squares not
988 * in the union as known and terminate.
990 * - If cursor has reached the end of setused and
991 * the algorithm _hasn't_ terminated, back
992 * cursor up to the nearest 1, turn it into a 0
993 * and advance cursor just past it.
995 * - If we attempt to back up to the nearest 1 and
996 * there isn't one at all, then we have gone
997 * through all disjoint unions of sets in the
998 * list and none of them has been helpful, so we
1001 struct set *sets[lenof(setused)];
1002 for (i = 0; i < nsets; i++)
1003 sets[i] = index234(ss->sets, i);
1008 if (cursor < nsets) {
1011 /* See if any existing set overlaps this one. */
1012 for (i = 0; i < cursor; i++)
1014 setmunge(sets[cursor]->x,
1017 sets[i]->x, sets[i]->y, sets[i]->mask,
1025 * We're adding this set to our union,
1026 * so adjust minesleft and squaresleft
1029 minesleft -= sets[cursor]->mines;
1030 squaresleft -= bitcount16(sets[cursor]->mask);
1033 setused[cursor++] = ok;
1035 #ifdef SOLVER_DIAGNOSTICS
1036 printf("trying a set combination with %d %d\n",
1037 squaresleft, minesleft);
1038 #endif /* SOLVER_DIAGNOSTICS */
1041 * We've reached the end. See if we've got
1042 * anything interesting.
1044 if (squaresleft > 0 &&
1045 (minesleft == 0 || minesleft == squaresleft)) {
1047 * We have! There is at least one
1048 * square not contained within the set
1049 * union we've just found, and we can
1050 * deduce that either all such squares
1051 * are mines or all are not (depending
1052 * on whether minesleft==0). So now all
1053 * we have to do is actually go through
1054 * the grid, find those squares, and
1057 for (i = 0; i < w*h; i++)
1058 if (grid[i] == -2) {
1062 for (j = 0; j < nsets; j++)
1064 setmunge(sets[j]->x, sets[j]->y,
1065 sets[j]->mask, x, y, 1,
1071 known_squares(w, h, std, grid,
1073 x, y, 1, minesleft != 0);
1076 done_something = TRUE;
1077 break; /* return to main deductive loop */
1081 * If we reach here, then this union hasn't
1082 * done us any good, so move on to the
1083 * next. Backtrack cursor to the nearest 1,
1084 * change it to a 0 and continue.
1086 while (cursor-- >= 0 && !setused[cursor]);
1088 assert(setused[cursor]);
1091 * We're removing this set from our
1092 * union, so re-increment minesleft and
1095 minesleft += sets[cursor]->mines;
1096 squaresleft += bitcount16(sets[cursor]->mask);
1098 setused[cursor++] = 0;
1101 * We've backtracked all the way to the
1102 * start without finding a single 1,
1103 * which means that our virtual
1104 * recursion is complete and nothing
1119 #ifdef SOLVER_DIAGNOSTICS
1121 * Dump the current known state of the grid.
1123 printf("solver ran out of steam, ret=%d, grid:\n", nperturbs);
1124 for (y = 0; y < h; y++) {
1125 for (x = 0; x < w; x++) {
1126 int v = grid[y*w+x];
1142 for (i = 0; (s = index234(ss->sets, i)) != NULL; i++)
1143 printf("remaining set: %d,%d %03x %d\n", s->x, s->y, s->mask, s->mines);
1148 * Now we really are at our wits' end as far as solving
1149 * this grid goes. Our only remaining option is to call
1150 * a perturb function and ask it to modify the grid to
1154 struct perturbations *ret;
1160 * Choose a set at random from the current selection,
1161 * and ask the perturb function to either fill or empty
1164 * If we have no sets at all, we must give up.
1166 if (count234(ss->sets) == 0)
1168 s = index234(ss->sets, random_upto(rs, count234(ss->sets)));
1169 #ifdef SOLVER_DIAGNOSTICS
1170 printf("perturbing on set %d,%d %03x\n", s->x, s->y, s->mask);
1172 ret = perturb(ctx, grid, s->x, s->y, s->mask);
1175 assert(ret->n > 0); /* otherwise should have been NULL */
1178 * A number of squares have been fiddled with, and
1179 * the returned structure tells us which. Adjust
1180 * the mine count in any set which overlaps one of
1181 * those squares, and put them back on the to-do
1184 for (i = 0; i < ret->n; i++) {
1185 #ifdef SOLVER_DIAGNOSTICS
1186 printf("perturbation %s mine at %d,%d\n",
1187 ret->changes[i].delta > 0 ? "added" : "removed",
1188 ret->changes[i].x, ret->changes[i].y);
1191 list = ss_overlap(ss,
1192 ret->changes[i].x, ret->changes[i].y, 1);
1194 for (j = 0; list[j]; j++) {
1195 list[j]->mines += ret->changes[i].delta;
1196 ss_add_todo(ss, list[j]);
1203 * Now free the returned data.
1205 sfree(ret->changes);
1208 #ifdef SOLVER_DIAGNOSTICS
1210 * Dump the current known state of the grid.
1212 printf("state after perturbation:\n", nperturbs);
1213 for (y = 0; y < h; y++) {
1214 for (x = 0; x < w; x++) {
1215 int v = grid[y*w+x];
1231 for (i = 0; (s = index234(ss->sets, i)) != NULL; i++)
1232 printf("remaining set: %d,%d %03x %d\n", s->x, s->y, s->mask, s->mines);
1237 * And now we can go back round the deductive loop.
1244 * If we get here, even that didn't work (either we didn't
1245 * have a perturb function or it returned failure), so we
1252 * See if we've got any unknown squares left.
1254 for (y = 0; y < h; y++)
1255 for (x = 0; x < w; x++)
1256 if (grid[y*w+x] == -2) {
1257 nperturbs = -1; /* failed to complete */
1262 * Free the set list and square-todo list.
1266 while ((s = delpos234(ss->sets, 0)) != NULL)
1268 freetree234(ss->sets);
1276 /* ----------------------------------------------------------------------
1277 * Grid generator which uses the above solver.
1287 static int mineopen(void *vctx, int x, int y)
1289 struct minectx *ctx = (struct minectx *)vctx;
1292 assert(x >= 0 && x < ctx->w && y >= 0 && y < ctx->h);
1293 if (ctx->grid[y * ctx->w + x])
1294 return -1; /* *bang* */
1297 for (i = -1; i <= +1; i++) {
1298 if (x + i < 0 || x + i >= ctx->w)
1300 for (j = -1; j <= +1; j++) {
1301 if (y + j < 0 || y + j >= ctx->h)
1303 if (i == 0 && j == 0)
1305 if (ctx->grid[(y+j) * ctx->w + (x+i)])
1313 /* Structure used internally to mineperturb(). */
1315 int x, y, type, random;
1317 static int squarecmp(const void *av, const void *bv)
1319 const struct square *a = (const struct square *)av;
1320 const struct square *b = (const struct square *)bv;
1321 if (a->type < b->type)
1323 else if (a->type > b->type)
1325 else if (a->random < b->random)
1327 else if (a->random > b->random)
1329 else if (a->y < b->y)
1331 else if (a->y > b->y)
1333 else if (a->x < b->x)
1335 else if (a->x > b->x)
1340 static struct perturbations *mineperturb(void *vctx, char *grid,
1341 int setx, int sety, int mask)
1343 struct minectx *ctx = (struct minectx *)vctx;
1344 struct square *sqlist;
1345 int x, y, dx, dy, i, n, nfull, nempty;
1346 struct square *tofill[9], *toempty[9], **todo;
1347 int ntofill, ntoempty, ntodo, dtodo, dset;
1348 struct perturbations *ret;
1351 * Make a list of all the squares in the grid which we can
1352 * possibly use. This list should be in preference order, which
1355 * - first, unknown squares on the boundary of known space
1356 * - next, unknown squares beyond that boundary
1357 * - as a very last resort, known squares, but not within one
1358 * square of the starting position.
1360 * Each of these sections needs to be shuffled independently.
1361 * We do this by preparing list of all squares and then sorting
1362 * it with a random secondary key.
1364 sqlist = snewn(ctx->w * ctx->h, struct square);
1366 for (y = 0; y < ctx->h; y++)
1367 for (x = 0; x < ctx->w; x++) {
1369 * If this square is too near the starting position,
1370 * don't put it on the list at all.
1372 if (abs(y - ctx->sy) <= 1 && abs(x - ctx->sx) <= 1)
1376 * If this square is in the input set, also don't put
1379 if (x >= setx && x < setx + 3 &&
1380 y >= sety && y < sety + 3 &&
1381 mask & (1 << ((y-sety)*3+(x-setx))))
1387 if (grid[y*ctx->w+x] != -2) {
1388 sqlist[n].type = 3; /* known square */
1391 * Unknown square. Examine everything around it and
1392 * see if it borders on any known squares. If it
1393 * does, it's class 1, otherwise it's 2.
1398 for (dy = -1; dy <= +1; dy++)
1399 for (dx = -1; dx <= +1; dx++)
1400 if (x+dx >= 0 && x+dx < ctx->w &&
1401 y+dy >= 0 && y+dy < ctx->h &&
1402 grid[(y+dy)*ctx->w+(x+dx)] != -2) {
1409 * Finally, a random number to cause qsort to
1410 * shuffle within each group.
1412 sqlist[n].random = random_bits(ctx->rs, 31);
1417 qsort(sqlist, n, sizeof(struct square), squarecmp);
1420 * Now count up the number of full and empty squares in the set
1421 * we've been provided.
1424 for (dy = 0; dy < 3; dy++)
1425 for (dx = 0; dx < 3; dx++)
1426 if (mask & (1 << (dy*3+dx))) {
1427 assert(setx+dx <= ctx->w);
1428 assert(sety+dy <= ctx->h);
1429 if (ctx->grid[(sety+dy)*ctx->w+(setx+dx)])
1436 * Now go through our sorted list until we find either `nfull'
1437 * empty squares, or `nempty' full squares; these will be
1438 * swapped with the appropriate squares in the set to either
1439 * fill or empty the set while keeping the same number of mines
1442 ntofill = ntoempty = 0;
1443 for (i = 0; i < n; i++) {
1444 struct square *sq = &sqlist[i];
1445 if (ctx->grid[sq->y * ctx->w + sq->x])
1446 toempty[ntoempty++] = sq;
1448 tofill[ntofill++] = sq;
1449 if (ntofill == nfull || ntoempty == nempty)
1454 * If this didn't work at all, I think we just give up.
1456 if (ntofill != nfull && ntoempty != nempty) {
1462 * Now we're pretty much there. We need to either
1463 * (a) put a mine in each of the empty squares in the set, and
1464 * take one out of each square in `toempty'
1465 * (b) take a mine out of each of the full squares in the set,
1466 * and put one in each square in `tofill'
1467 * depending on which one we've found enough squares to do.
1469 * So we start by constructing our list of changes to return to
1470 * the solver, so that it can update its data structures
1471 * efficiently rather than having to rescan the whole grid.
1473 ret = snew(struct perturbations);
1474 if (ntofill == nfull) {
1486 ret->changes = snewn(ret->n, struct perturbation);
1487 for (i = 0; i < ntodo; i++) {
1488 ret->changes[i].x = todo[i]->x;
1489 ret->changes[i].y = todo[i]->y;
1490 ret->changes[i].delta = dtodo;
1492 /* now i == ntodo */
1493 for (dy = 0; dy < 3; dy++)
1494 for (dx = 0; dx < 3; dx++)
1495 if (mask & (1 << (dy*3+dx))) {
1496 int currval = (ctx->grid[(sety+dy)*ctx->w+(setx+dx)] ? +1 : -1);
1497 if (dset == -currval) {
1498 ret->changes[i].x = setx + dx;
1499 ret->changes[i].y = sety + dy;
1500 ret->changes[i].delta = dset;
1504 assert(i == ret->n);
1509 * Having set up the precise list of changes we're going to
1510 * make, we now simply make them and return.
1512 for (i = 0; i < ret->n; i++) {
1515 x = ret->changes[i].x;
1516 y = ret->changes[i].y;
1517 delta = ret->changes[i].delta;
1520 * Check we're not trying to add an existing mine or remove
1523 assert((delta < 0) ^ (ctx->grid[y*ctx->w+x] == 0));
1526 * Actually make the change.
1528 ctx->grid[y*ctx->w+x] = (delta > 0);
1531 * Update any numbers already present in the grid.
1533 for (dy = -1; dy <= +1; dy++)
1534 for (dx = -1; dx <= +1; dx++)
1535 if (x+dx >= 0 && x+dx < ctx->w &&
1536 y+dy >= 0 && y+dy < ctx->h &&
1537 grid[(y+dy)*ctx->w+(x+dx)] != -2) {
1538 if (dx == 0 && dy == 0) {
1540 * The square itself is marked as known in
1541 * the grid. Mark it as a mine if it's a
1542 * mine, or else work out its number.
1545 grid[y*ctx->w+x] = -1;
1547 int dx2, dy2, minecount = 0;
1548 for (dy2 = -1; dy2 <= +1; dy2++)
1549 for (dx2 = -1; dx2 <= +1; dx2++)
1550 if (x+dx2 >= 0 && x+dx2 < ctx->w &&
1551 y+dy2 >= 0 && y+dy2 < ctx->h &&
1552 ctx->grid[(y+dy2)*ctx->w+(x+dx2)])
1554 grid[y*ctx->w+x] = minecount;
1557 if (grid[(y+dy)*ctx->w+(x+dx)] >= 0)
1558 grid[(y+dy)*ctx->w+(x+dx)] += delta;
1563 #ifdef GENERATION_DIAGNOSTICS
1566 printf("grid after perturbing:\n");
1567 for (yy = 0; yy < ctx->h; yy++) {
1568 for (xx = 0; xx < ctx->w; xx++) {
1569 int v = ctx->grid[yy*ctx->w+xx];
1570 if (yy == ctx->sy && xx == ctx->sx) {
1588 static char *minegen(int w, int h, int n, int x, int y, int unique,
1591 char *ret = snewn(w*h, char);
1597 memset(ret, 0, w*h);
1600 * Start by placing n mines, none of which is at x,y or within
1604 int *tmp = snewn(w*h, int);
1608 * Write down the list of possible mine locations.
1611 for (i = 0; i < h; i++)
1612 for (j = 0; j < w; j++)
1613 if (abs(i - y) > 1 || abs(j - x) > 1)
1617 * Now pick n off the list at random.
1621 i = random_upto(rs, k);
1629 #ifdef GENERATION_DIAGNOSTICS
1632 printf("grid after initial generation:\n");
1633 for (yy = 0; yy < h; yy++) {
1634 for (xx = 0; xx < w; xx++) {
1635 int v = ret[yy*w+xx];
1636 if (yy == y && xx == x) {
1652 * Now set up a results grid to run the solver in, and a
1653 * context for the solver to open squares. Then run the solver
1654 * repeatedly; if the number of perturb steps ever goes up or
1655 * it ever returns -1, give up completely.
1657 * We bypass this bit if we're not after a unique grid.
1660 char *solvegrid = snewn(w*h, char);
1661 struct minectx actx, *ctx = &actx;
1662 int solveret, prevret = -2;
1672 memset(solvegrid, -2, w*h);
1673 solvegrid[y*w+x] = mineopen(ctx, x, y);
1674 assert(solvegrid[y*w+x] == 0); /* by deliberate arrangement */
1677 minesolve(w, h, n, solvegrid, mineopen, mineperturb, ctx, rs);
1678 if (solveret < 0 || (prevret >= 0 && solveret >= prevret)) {
1681 } else if (solveret == 0) {
1698 * The Mines game descriptions contain the location of every mine,
1699 * and can therefore be used to cheat.
1701 * It would be pointless to attempt to _prevent_ this form of
1702 * cheating by encrypting the description, since Mines is
1703 * open-source so anyone can find out the encryption key. However,
1704 * I think it is worth doing a bit of gentle obfuscation to prevent
1705 * _accidental_ spoilers: if you happened to note that the game ID
1706 * starts with an F, for example, you might be unable to put the
1707 * knowledge of those mines out of your mind while playing. So,
1708 * just as discussions of film endings are rot13ed to avoid
1709 * spoiling it for people who don't want to be told, we apply a
1710 * keyless, reversible, but visually completely obfuscatory masking
1711 * function to the mine bitmap.
1713 static void obfuscate_bitmap(unsigned char *bmp, int bits, int decode)
1715 int bytes, firsthalf, secondhalf;
1717 unsigned char *seedstart;
1719 unsigned char *targetstart;
1725 * My obfuscation algorithm is similar in concept to the OAEP
1726 * encoding used in some forms of RSA. Here's a specification
1729 * + We have a `masking function' which constructs a stream of
1730 * pseudorandom bytes from a seed of some number of input
1733 * + We pad out our input bit stream to a whole number of
1734 * bytes by adding up to 7 zero bits on the end. (In fact
1735 * the bitmap passed as input to this function will already
1736 * have had this done in practice.)
1738 * + We divide the _byte_ stream exactly in half, rounding the
1739 * half-way position _down_. So an 81-bit input string, for
1740 * example, rounds up to 88 bits or 11 bytes, and then
1741 * dividing by two gives 5 bytes in the first half and 6 in
1744 * + We generate a mask from the second half of the bytes, and
1745 * XOR it over the first half.
1747 * + We generate a mask from the (encoded) first half of the
1748 * bytes, and XOR it over the second half. Any null bits at
1749 * the end which were added as padding are cleared back to
1750 * zero even if this operation would have made them nonzero.
1752 * To de-obfuscate, the steps are precisely the same except
1753 * that the final two are reversed.
1755 * Finally, our masking function. Given an input seed string of
1756 * bytes, the output mask consists of concatenating the SHA-1
1757 * hashes of the seed string and successive decimal integers,
1761 bytes = (bits + 7) / 8;
1762 firsthalf = bytes / 2;
1763 secondhalf = bytes - firsthalf;
1765 steps[decode ? 1 : 0].seedstart = bmp + firsthalf;
1766 steps[decode ? 1 : 0].seedlen = secondhalf;
1767 steps[decode ? 1 : 0].targetstart = bmp;
1768 steps[decode ? 1 : 0].targetlen = firsthalf;
1770 steps[decode ? 0 : 1].seedstart = bmp;
1771 steps[decode ? 0 : 1].seedlen = firsthalf;
1772 steps[decode ? 0 : 1].targetstart = bmp + firsthalf;
1773 steps[decode ? 0 : 1].targetlen = secondhalf;
1775 for (i = 0; i < 2; i++) {
1776 SHA_State base, final;
1777 unsigned char digest[20];
1779 int digestpos = 20, counter = 0;
1782 SHA_Bytes(&base, steps[i].seedstart, steps[i].seedlen);
1784 for (j = 0; j < steps[i].targetlen; j++) {
1785 if (digestpos >= 20) {
1786 sprintf(numberbuf, "%d", counter++);
1788 SHA_Bytes(&final, numberbuf, strlen(numberbuf));
1789 SHA_Final(&final, digest);
1792 steps[i].targetstart[j] ^= digest[digestpos]++;
1796 * Mask off the pad bits in the final byte after both steps.
1799 bmp[bits / 8] &= 0xFF & (0xFF00 >> (bits % 8));
1803 static char *new_mine_layout(int w, int h, int n, int x, int y, int unique,
1804 random_state *rs, char **game_desc)
1806 char *grid, *ret, *p;
1810 grid = minegen(w, h, n, x, y, unique, rs);
1814 * Set up the mine bitmap and obfuscate it.
1817 bmp = snewn((area + 7) / 8, unsigned char);
1818 memset(bmp, 0, (area + 7) / 8);
1819 for (i = 0; i < area; i++) {
1821 bmp[i / 8] |= 0x80 >> (i % 8);
1823 obfuscate_bitmap(bmp, area, FALSE);
1826 * Now encode the resulting bitmap in hex. We can work to
1827 * nibble rather than byte granularity, since the obfuscation
1828 * function guarantees to return a bit string of the same
1829 * length as its input.
1831 ret = snewn((area+3)/4 + 100, char);
1832 p = ret + sprintf(ret, "%d,%d,m", x, y); /* 'm' == masked */
1833 for (i = 0; i < (area+3)/4; i++) {
1837 *p++ = "0123456789abcdef"[v & 0xF];
1849 static char *new_game_desc(game_params *params, random_state *rs,
1850 game_aux_info **aux)
1853 int x = random_upto(rs, params->w);
1854 int y = random_upto(rs, params->h);
1857 grid = new_mine_layout(params->w, params->h, params->n,
1858 x, y, params->unique, rs);
1860 char *rsdesc, *desc;
1862 rsdesc = random_state_encode(rs);
1863 desc = snewn(strlen(rsdesc) + 100, char);
1864 sprintf(desc, "r%d,%c,%s", params->n, params->unique ? 'u' : 'a', rsdesc);
1870 static void game_free_aux_info(game_aux_info *aux)
1872 assert(!"Shouldn't happen");
1875 static char *validate_desc(game_params *params, char *desc)
1877 int wh = params->w * params->h;
1881 if (!*desc || !isdigit((unsigned char)*desc))
1882 return "No initial mine count in game description";
1883 while (*desc && isdigit((unsigned char)*desc))
1884 desc++; /* skip over mine count */
1886 return "No ',' after initial x-coordinate in game description";
1888 if (*desc != 'u' && *desc != 'a')
1889 return "No uniqueness specifier in game description";
1892 return "No ',' after uniqueness specifier in game description";
1893 /* now ignore the rest */
1895 if (!*desc || !isdigit((unsigned char)*desc))
1896 return "No initial x-coordinate in game description";
1898 if (x < 0 || x >= params->w)
1899 return "Initial x-coordinate was out of range";
1900 while (*desc && isdigit((unsigned char)*desc))
1901 desc++; /* skip over x coordinate */
1903 return "No ',' after initial x-coordinate in game description";
1904 desc++; /* eat comma */
1905 if (!*desc || !isdigit((unsigned char)*desc))
1906 return "No initial y-coordinate in game description";
1908 if (y < 0 || y >= params->h)
1909 return "Initial y-coordinate was out of range";
1910 while (*desc && isdigit((unsigned char)*desc))
1911 desc++; /* skip over y coordinate */
1913 return "No ',' after initial y-coordinate in game description";
1914 desc++; /* eat comma */
1915 /* eat `m', meaning `masked', if present */
1918 /* now just check length of remainder */
1919 if (strlen(desc) != (wh+3)/4)
1920 return "Game description is wrong length";
1926 static int open_square(game_state *state, int x, int y)
1928 int w = state->w, h = state->h;
1929 int xx, yy, nmines, ncovered;
1931 if (!state->layout->mines) {
1933 * We have a preliminary game in which the mine layout
1934 * hasn't been generated yet. Generate it based on the
1935 * initial click location.
1938 state->layout->mines = new_mine_layout(w, h, state->layout->n,
1939 x, y, state->layout->unique,
1942 midend_supersede_game_desc(state->layout->me, desc);
1944 random_free(state->layout->rs);
1945 state->layout->rs = NULL;
1948 if (state->layout->mines[y*w+x]) {
1950 * The player has landed on a mine. Bad luck. Expose all
1954 for (yy = 0; yy < h; yy++)
1955 for (xx = 0; xx < w; xx++) {
1956 if (state->layout->mines[yy*w+xx] &&
1957 (state->grid[yy*w+xx] == -2 ||
1958 state->grid[yy*w+xx] == -3)) {
1959 state->grid[yy*w+xx] = 64;
1961 if (!state->layout->mines[yy*w+xx] &&
1962 state->grid[yy*w+xx] == -1) {
1963 state->grid[yy*w+xx] = 66;
1966 state->grid[y*w+x] = 65;
1971 * Otherwise, the player has opened a safe square. Mark it to-do.
1973 state->grid[y*w+x] = -10; /* `todo' value internal to this func */
1976 * Now go through the grid finding all `todo' values and
1977 * opening them. Every time one of them turns out to have no
1978 * neighbouring mines, we add all its unopened neighbours to
1981 * FIXME: We really ought to be able to do this better than
1982 * using repeated N^2 scans of the grid.
1985 int done_something = FALSE;
1987 for (yy = 0; yy < h; yy++)
1988 for (xx = 0; xx < w; xx++)
1989 if (state->grid[yy*w+xx] == -10) {
1992 assert(!state->layout->mines[yy*w+xx]);
1996 for (dx = -1; dx <= +1; dx++)
1997 for (dy = -1; dy <= +1; dy++)
1998 if (xx+dx >= 0 && xx+dx < state->w &&
1999 yy+dy >= 0 && yy+dy < state->h &&
2000 state->layout->mines[(yy+dy)*w+(xx+dx)])
2003 state->grid[yy*w+xx] = v;
2006 for (dx = -1; dx <= +1; dx++)
2007 for (dy = -1; dy <= +1; dy++)
2008 if (xx+dx >= 0 && xx+dx < state->w &&
2009 yy+dy >= 0 && yy+dy < state->h &&
2010 state->grid[(yy+dy)*w+(xx+dx)] == -2)
2011 state->grid[(yy+dy)*w+(xx+dx)] = -10;
2014 done_something = TRUE;
2017 if (!done_something)
2022 * Finally, scan the grid and see if exactly as many squares
2023 * are still covered as there are mines. If so, set the `won'
2024 * flag and fill in mine markers on all covered squares.
2026 nmines = ncovered = 0;
2027 for (yy = 0; yy < h; yy++)
2028 for (xx = 0; xx < w; xx++) {
2029 if (state->grid[yy*w+xx] < 0)
2031 if (state->layout->mines[yy*w+xx])
2034 assert(ncovered >= nmines);
2035 if (ncovered == nmines) {
2036 for (yy = 0; yy < h; yy++)
2037 for (xx = 0; xx < w; xx++) {
2038 if (state->grid[yy*w+xx] < 0)
2039 state->grid[yy*w+xx] = -1;
2047 static game_state *new_game(midend_data *me, game_params *params, char *desc)
2049 game_state *state = snew(game_state);
2050 int i, wh, x, y, ret, masked;
2053 state->w = params->w;
2054 state->h = params->h;
2055 state->n = params->n;
2056 state->dead = state->won = FALSE;
2058 wh = state->w * state->h;
2060 state->layout = snew(struct mine_layout);
2061 state->layout->refcount = 1;
2063 state->grid = snewn(wh, char);
2064 memset(state->grid, -2, wh);
2068 state->layout->n = atoi(desc);
2069 while (*desc && isdigit((unsigned char)*desc))
2070 desc++; /* skip over mine count */
2071 if (*desc) desc++; /* eat comma */
2073 state->layout->unique = FALSE;
2075 state->layout->unique = TRUE;
2077 if (*desc) desc++; /* eat comma */
2079 state->layout->mines = NULL;
2080 state->layout->rs = random_state_decode(desc);
2081 state->layout->me = me;
2085 state->layout->mines = snewn(wh, char);
2087 while (*desc && isdigit((unsigned char)*desc))
2088 desc++; /* skip over x coordinate */
2089 if (*desc) desc++; /* eat comma */
2091 while (*desc && isdigit((unsigned char)*desc))
2092 desc++; /* skip over y coordinate */
2093 if (*desc) desc++; /* eat comma */
2100 * We permit game IDs to be entered by hand without the
2101 * masking transformation.
2106 bmp = snewn((wh + 7) / 8, unsigned char);
2107 memset(bmp, 0, (wh + 7) / 8);
2108 for (i = 0; i < (wh+3)/4; i++) {
2112 assert(c != 0); /* validate_desc should have caught */
2113 if (c >= '0' && c <= '9')
2115 else if (c >= 'a' && c <= 'f')
2117 else if (c >= 'A' && c <= 'F')
2122 bmp[i / 2] |= v << (4 * (1 - (i % 2)));
2126 obfuscate_bitmap(bmp, wh, TRUE);
2128 memset(state->layout->mines, 0, wh);
2129 for (i = 0; i < wh; i++) {
2130 if (bmp[i / 8] & (0x80 >> (i % 8)))
2131 state->layout->mines[i] = 1;
2134 ret = open_square(state, x, y);
2140 static game_state *dup_game(game_state *state)
2142 game_state *ret = snew(game_state);
2147 ret->dead = state->dead;
2148 ret->won = state->won;
2149 ret->layout = state->layout;
2150 ret->layout->refcount++;
2151 ret->grid = snewn(ret->w * ret->h, char);
2152 memcpy(ret->grid, state->grid, ret->w * ret->h);
2157 static void free_game(game_state *state)
2159 if (--state->layout->refcount <= 0) {
2160 sfree(state->layout->mines);
2161 if (state->layout->rs)
2162 random_free(state->layout->rs);
2163 sfree(state->layout);
2169 static game_state *solve_game(game_state *state, game_aux_info *aux,
2175 static char *game_text_format(game_state *state)
2181 int hx, hy, hradius; /* for mouse-down highlights */
2185 static game_ui *new_ui(game_state *state)
2187 game_ui *ui = snew(game_ui);
2188 ui->hx = ui->hy = -1;
2190 ui->flash_is_death = FALSE; /* *shrug* */
2194 static void free_ui(game_ui *ui)
2199 static game_state *make_move(game_state *from, game_ui *ui, int x, int y,
2205 if (from->dead || from->won)
2206 return NULL; /* no further moves permitted */
2208 if (!IS_MOUSE_DOWN(button) && !IS_MOUSE_DRAG(button) &&
2209 !IS_MOUSE_RELEASE(button))
2214 if (cx < 0 || cx >= from->w || cy < 0 || cy > from->h)
2217 if (button == LEFT_BUTTON || button == LEFT_DRAG) {
2219 * Mouse-downs and mouse-drags just cause highlighting
2224 ui->hradius = (from->grid[cy*from->w+cx] >= 0 ? 1 : 0);
2228 if (button == RIGHT_BUTTON) {
2230 * Right-clicking only works on a covered square, and it
2231 * toggles between -1 (marked as mine) and -2 (not marked
2234 * FIXME: question marks.
2236 if (from->grid[cy * from->w + cx] != -2 &&
2237 from->grid[cy * from->w + cx] != -1)
2240 ret = dup_game(from);
2241 ret->grid[cy * from->w + cx] ^= (-2 ^ -1);
2246 if (button == LEFT_RELEASE) {
2247 ui->hx = ui->hy = -1;
2251 * At this stage we must never return NULL: we have adjusted
2252 * the ui, so at worst we return `from'.
2256 * Left-clicking on a covered square opens a tile. Not
2257 * permitted if the tile is marked as a mine, for safety.
2258 * (Unmark it and _then_ open it.)
2260 if (from->grid[cy * from->w + cx] == -2 ||
2261 from->grid[cy * from->w + cx] == -3) {
2262 ret = dup_game(from);
2263 open_square(ret, cx, cy);
2268 * Left-clicking on an uncovered tile: first we check to see if
2269 * the number of mine markers surrounding the tile is equal to
2270 * its mine count, and if so then we open all other surrounding
2273 if (from->grid[cy * from->w + cx] > 0) {
2276 /* Count mine markers. */
2278 for (dy = -1; dy <= +1; dy++)
2279 for (dx = -1; dx <= +1; dx++)
2280 if (cx+dx >= 0 && cx+dx < from->w &&
2281 cy+dy >= 0 && cy+dy < from->h) {
2282 if (from->grid[(cy+dy)*from->w+(cx+dx)] == -1)
2286 if (n == from->grid[cy * from->w + cx]) {
2287 ret = dup_game(from);
2288 for (dy = -1; dy <= +1; dy++)
2289 for (dx = -1; dx <= +1; dx++)
2290 if (cx+dx >= 0 && cx+dx < ret->w &&
2291 cy+dy >= 0 && cy+dy < ret->h &&
2292 (ret->grid[(cy+dy)*ret->w+(cx+dx)] == -2 ||
2293 ret->grid[(cy+dy)*ret->w+(cx+dx)] == -3))
2294 open_square(ret, cx+dx, cy+dy);
2305 /* ----------------------------------------------------------------------
2309 struct game_drawstate {
2313 * Items in this `grid' array have all the same values as in
2314 * the game_state grid, and in addition:
2316 * - -10 means the tile was drawn `specially' as a result of a
2317 * flash, so it will always need redrawing.
2319 * - -22 and -23 mean the tile is highlighted for a possible
2324 static void game_size(game_params *params, int *x, int *y)
2326 *x = BORDER * 2 + TILE_SIZE * params->w;
2327 *y = BORDER * 2 + TILE_SIZE * params->h;
2330 static float *game_colours(frontend *fe, game_state *state, int *ncolours)
2332 float *ret = snewn(3 * NCOLOURS, float);
2334 frontend_default_colour(fe, &ret[COL_BACKGROUND * 3]);
2336 ret[COL_1 * 3 + 0] = 0.0F;
2337 ret[COL_1 * 3 + 1] = 0.0F;
2338 ret[COL_1 * 3 + 2] = 1.0F;
2340 ret[COL_2 * 3 + 0] = 0.0F;
2341 ret[COL_2 * 3 + 1] = 0.5F;
2342 ret[COL_2 * 3 + 2] = 0.0F;
2344 ret[COL_3 * 3 + 0] = 1.0F;
2345 ret[COL_3 * 3 + 1] = 0.0F;
2346 ret[COL_3 * 3 + 2] = 0.0F;
2348 ret[COL_4 * 3 + 0] = 0.0F;
2349 ret[COL_4 * 3 + 1] = 0.0F;
2350 ret[COL_4 * 3 + 2] = 0.5F;
2352 ret[COL_5 * 3 + 0] = 0.5F;
2353 ret[COL_5 * 3 + 1] = 0.0F;
2354 ret[COL_5 * 3 + 2] = 0.0F;
2356 ret[COL_6 * 3 + 0] = 0.0F;
2357 ret[COL_6 * 3 + 1] = 0.5F;
2358 ret[COL_6 * 3 + 2] = 0.5F;
2360 ret[COL_7 * 3 + 0] = 0.0F;
2361 ret[COL_7 * 3 + 1] = 0.0F;
2362 ret[COL_7 * 3 + 2] = 0.0F;
2364 ret[COL_8 * 3 + 0] = 0.5F;
2365 ret[COL_8 * 3 + 1] = 0.5F;
2366 ret[COL_8 * 3 + 2] = 0.5F;
2368 ret[COL_MINE * 3 + 0] = 0.0F;
2369 ret[COL_MINE * 3 + 1] = 0.0F;
2370 ret[COL_MINE * 3 + 2] = 0.0F;
2372 ret[COL_BANG * 3 + 0] = 1.0F;
2373 ret[COL_BANG * 3 + 1] = 0.0F;
2374 ret[COL_BANG * 3 + 2] = 0.0F;
2376 ret[COL_CROSS * 3 + 0] = 1.0F;
2377 ret[COL_CROSS * 3 + 1] = 0.0F;
2378 ret[COL_CROSS * 3 + 2] = 0.0F;
2380 ret[COL_FLAG * 3 + 0] = 1.0F;
2381 ret[COL_FLAG * 3 + 1] = 0.0F;
2382 ret[COL_FLAG * 3 + 2] = 0.0F;
2384 ret[COL_FLAGBASE * 3 + 0] = 0.0F;
2385 ret[COL_FLAGBASE * 3 + 1] = 0.0F;
2386 ret[COL_FLAGBASE * 3 + 2] = 0.0F;
2388 ret[COL_QUERY * 3 + 0] = 0.0F;
2389 ret[COL_QUERY * 3 + 1] = 0.0F;
2390 ret[COL_QUERY * 3 + 2] = 0.0F;
2392 ret[COL_HIGHLIGHT * 3 + 0] = 1.0F;
2393 ret[COL_HIGHLIGHT * 3 + 1] = 1.0F;
2394 ret[COL_HIGHLIGHT * 3 + 2] = 1.0F;
2396 ret[COL_LOWLIGHT * 3 + 0] = ret[COL_BACKGROUND * 3 + 0] * 2.0 / 3.0;
2397 ret[COL_LOWLIGHT * 3 + 1] = ret[COL_BACKGROUND * 3 + 1] * 2.0 / 3.0;
2398 ret[COL_LOWLIGHT * 3 + 2] = ret[COL_BACKGROUND * 3 + 2] * 2.0 / 3.0;
2400 *ncolours = NCOLOURS;
2404 static game_drawstate *game_new_drawstate(game_state *state)
2406 struct game_drawstate *ds = snew(struct game_drawstate);
2410 ds->started = FALSE;
2411 ds->grid = snewn(ds->w * ds->h, char);
2413 memset(ds->grid, -99, ds->w * ds->h);
2418 static void game_free_drawstate(game_drawstate *ds)
2424 static void draw_tile(frontend *fe, int x, int y, int v, int bg)
2430 if (v == -22 || v == -23) {
2434 * Omit the highlights in this case.
2436 draw_rect(fe, x, y, TILE_SIZE, TILE_SIZE, bg);
2437 draw_line(fe, x, y, x + TILE_SIZE - 1, y, COL_LOWLIGHT);
2438 draw_line(fe, x, y, x, y + TILE_SIZE - 1, COL_LOWLIGHT);
2441 * Draw highlights to indicate the square is covered.
2443 coords[0] = x + TILE_SIZE - 1;
2444 coords[1] = y + TILE_SIZE - 1;
2445 coords[2] = x + TILE_SIZE - 1;
2448 coords[5] = y + TILE_SIZE - 1;
2449 draw_polygon(fe, coords, 3, TRUE, COL_LOWLIGHT ^ hl);
2450 draw_polygon(fe, coords, 3, FALSE, COL_LOWLIGHT ^ hl);
2454 draw_polygon(fe, coords, 3, TRUE, COL_HIGHLIGHT ^ hl);
2455 draw_polygon(fe, coords, 3, FALSE, COL_HIGHLIGHT ^ hl);
2457 draw_rect(fe, x + HIGHLIGHT_WIDTH, y + HIGHLIGHT_WIDTH,
2458 TILE_SIZE - 2*HIGHLIGHT_WIDTH, TILE_SIZE - 2*HIGHLIGHT_WIDTH,
2466 #define SETCOORD(n, dx, dy) do { \
2467 coords[(n)*2+0] = x + TILE_SIZE * (dx); \
2468 coords[(n)*2+1] = y + TILE_SIZE * (dy); \
2470 SETCOORD(0, 0.6, 0.35);
2471 SETCOORD(1, 0.6, 0.7);
2472 SETCOORD(2, 0.8, 0.8);
2473 SETCOORD(3, 0.25, 0.8);
2474 SETCOORD(4, 0.55, 0.7);
2475 SETCOORD(5, 0.55, 0.35);
2476 draw_polygon(fe, coords, 6, TRUE, COL_FLAGBASE);
2477 draw_polygon(fe, coords, 6, FALSE, COL_FLAGBASE);
2479 SETCOORD(0, 0.6, 0.2);
2480 SETCOORD(1, 0.6, 0.5);
2481 SETCOORD(2, 0.2, 0.35);
2482 draw_polygon(fe, coords, 3, TRUE, COL_FLAG);
2483 draw_polygon(fe, coords, 3, FALSE, COL_FLAG);
2486 } else if (v == -3) {
2488 * Draw a question mark.
2490 draw_text(fe, x + TILE_SIZE / 2, y + TILE_SIZE / 2,
2491 FONT_VARIABLE, TILE_SIZE * 6 / 8,
2492 ALIGN_VCENTRE | ALIGN_HCENTRE,
2497 * Clear the square to the background colour, and draw thin
2498 * grid lines along the top and left.
2500 * Exception is that for value 65 (mine we've just trodden
2501 * on), we clear the square to COL_BANG.
2503 draw_rect(fe, x, y, TILE_SIZE, TILE_SIZE,
2504 (v == 65 ? COL_BANG : bg));
2505 draw_line(fe, x, y, x + TILE_SIZE - 1, y, COL_LOWLIGHT);
2506 draw_line(fe, x, y, x, y + TILE_SIZE - 1, COL_LOWLIGHT);
2508 if (v > 0 && v <= 8) {
2515 draw_text(fe, x + TILE_SIZE / 2, y + TILE_SIZE / 2,
2516 FONT_VARIABLE, TILE_SIZE * 7 / 8,
2517 ALIGN_VCENTRE | ALIGN_HCENTRE,
2518 (COL_1 - 1) + v, str);
2520 } else if (v >= 64) {
2524 * FIXME: this could be done better!
2527 draw_text(fe, x + TILE_SIZE / 2, y + TILE_SIZE / 2,
2528 FONT_VARIABLE, TILE_SIZE * 7 / 8,
2529 ALIGN_VCENTRE | ALIGN_HCENTRE,
2533 int cx = x + TILE_SIZE / 2;
2534 int cy = y + TILE_SIZE / 2;
2535 int r = TILE_SIZE / 2 - 3;
2537 int xdx = 1, xdy = 0, ydx = 0, ydy = 1;
2540 for (i = 0; i < 4*5*2; i += 5*2) {
2541 coords[i+2*0+0] = cx - r/6*xdx + r*4/5*ydx;
2542 coords[i+2*0+1] = cy - r/6*xdy + r*4/5*ydy;
2543 coords[i+2*1+0] = cx - r/6*xdx + r*ydx;
2544 coords[i+2*1+1] = cy - r/6*xdy + r*ydy;
2545 coords[i+2*2+0] = cx + r/6*xdx + r*ydx;
2546 coords[i+2*2+1] = cy + r/6*xdy + r*ydy;
2547 coords[i+2*3+0] = cx + r/6*xdx + r*4/5*ydx;
2548 coords[i+2*3+1] = cy + r/6*xdy + r*4/5*ydy;
2549 coords[i+2*4+0] = cx + r*3/5*xdx + r*3/5*ydx;
2550 coords[i+2*4+1] = cy + r*3/5*xdy + r*3/5*ydy;
2560 draw_polygon(fe, coords, 5*4, TRUE, COL_MINE);
2561 draw_polygon(fe, coords, 5*4, FALSE, COL_MINE);
2563 draw_rect(fe, cx-r/3, cy-r/3, r/3, r/4, COL_HIGHLIGHT);
2569 * Cross through the mine.
2572 for (dx = -1; dx <= +1; dx++) {
2573 draw_line(fe, x + 3 + dx, y + 2,
2574 x + TILE_SIZE - 3 + dx,
2575 y + TILE_SIZE - 2, COL_CROSS);
2576 draw_line(fe, x + TILE_SIZE - 3 + dx, y + 2,
2577 x + 3 + dx, y + TILE_SIZE - 2,
2584 draw_update(fe, x, y, TILE_SIZE, TILE_SIZE);
2587 static void game_redraw(frontend *fe, game_drawstate *ds, game_state *oldstate,
2588 game_state *state, int dir, game_ui *ui,
2589 float animtime, float flashtime)
2592 int mines, markers, bg;
2595 int frame = (flashtime / FLASH_FRAME);
2597 bg = (ui->flash_is_death ? COL_BACKGROUND : COL_LOWLIGHT);
2599 bg = (ui->flash_is_death ? COL_BANG : COL_HIGHLIGHT);
2601 bg = COL_BACKGROUND;
2607 TILE_SIZE * state->w + 2 * BORDER,
2608 TILE_SIZE * state->h + 2 * BORDER, COL_BACKGROUND);
2609 draw_update(fe, 0, 0,
2610 TILE_SIZE * state->w + 2 * BORDER,
2611 TILE_SIZE * state->h + 2 * BORDER);
2614 * Recessed area containing the whole puzzle.
2616 coords[0] = COORD(state->w) + OUTER_HIGHLIGHT_WIDTH - 1;
2617 coords[1] = COORD(state->h) + OUTER_HIGHLIGHT_WIDTH - 1;
2618 coords[2] = COORD(state->w) + OUTER_HIGHLIGHT_WIDTH - 1;
2619 coords[3] = COORD(0) - OUTER_HIGHLIGHT_WIDTH;
2620 coords[4] = COORD(0) - OUTER_HIGHLIGHT_WIDTH;
2621 coords[5] = COORD(state->h) + OUTER_HIGHLIGHT_WIDTH - 1;
2622 draw_polygon(fe, coords, 3, TRUE, COL_HIGHLIGHT);
2623 draw_polygon(fe, coords, 3, FALSE, COL_HIGHLIGHT);
2625 coords[1] = COORD(0) - OUTER_HIGHLIGHT_WIDTH;
2626 coords[0] = COORD(0) - OUTER_HIGHLIGHT_WIDTH;
2627 draw_polygon(fe, coords, 3, TRUE, COL_LOWLIGHT);
2628 draw_polygon(fe, coords, 3, FALSE, COL_LOWLIGHT);
2634 * Now draw the tiles. Also in this loop, count up the number
2635 * of mines and mine markers.
2637 mines = markers = 0;
2638 for (y = 0; y < ds->h; y++)
2639 for (x = 0; x < ds->w; x++) {
2640 int v = state->grid[y*ds->w+x];
2644 if (state->layout->mines && state->layout->mines[y*ds->w+x])
2647 if ((v == -2 || v == -3) &&
2648 (abs(x-ui->hx) <= ui->hradius && abs(y-ui->hy) <= ui->hradius))
2651 if (ds->grid[y*ds->w+x] != v || bg != COL_BACKGROUND) {
2652 draw_tile(fe, COORD(x), COORD(y), v, bg);
2653 ds->grid[y*ds->w+x] = (bg == COL_BACKGROUND ? v : -10);
2657 if (!state->layout->mines)
2658 mines = state->layout->n;
2661 * Update the status bar.
2664 char statusbar[512];
2666 sprintf(statusbar, "GAME OVER!");
2667 } else if (state->won) {
2668 sprintf(statusbar, "COMPLETED!");
2670 sprintf(statusbar, "Mines marked: %d / %d", markers, mines);
2672 status_bar(fe, statusbar);
2676 static float game_anim_length(game_state *oldstate, game_state *newstate,
2677 int dir, game_ui *ui)
2682 static float game_flash_length(game_state *oldstate, game_state *newstate,
2683 int dir, game_ui *ui)
2685 if (dir > 0 && !oldstate->dead && !oldstate->won) {
2686 if (newstate->dead) {
2687 ui->flash_is_death = TRUE;
2688 return 3 * FLASH_FRAME;
2690 if (newstate->won) {
2691 ui->flash_is_death = FALSE;
2692 return 2 * FLASH_FRAME;
2698 static int game_wants_statusbar(void)
2703 static int game_timing_state(game_state *state)
2705 if (state->dead || state->won || !state->layout->mines)
2711 #define thegame mines
2714 const struct game thegame = {
2715 "Mines", "games.mines",
2722 TRUE, game_configure, custom_params,
2731 FALSE, game_text_format,
2738 game_free_drawstate,
2742 game_wants_statusbar,
2743 TRUE, game_timing_state,