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,
29 #define BORDER (TILE_SIZE * 3 / 2)
30 #define HIGHLIGHT_WIDTH 2
31 #define OUTER_HIGHLIGHT_WIDTH 3
32 #define COORD(x) ( (x) * TILE_SIZE + BORDER )
33 #define FROMCOORD(x) ( ((x) - BORDER + TILE_SIZE) / TILE_SIZE - 1 )
35 #define FLASH_FRAME 0.13F
44 * This structure is shared between all the game_states for a
45 * given instance of the puzzle, so we reference-count it.
50 * If we haven't yet actually generated the mine layout, here's
51 * all the data we will need to do so.
55 midend_data *me; /* to give back the new game desc */
59 int w, h, n, dead, won;
60 int used_solve, just_used_solve;
61 struct mine_layout *layout; /* real mine positions */
62 signed char *grid; /* player knowledge */
64 * Each item in the `grid' array is one of the following values:
66 * - 0 to 8 mean the square is open and has a surrounding mine
69 * - -1 means the square is marked as a mine.
71 * - -2 means the square is unknown.
73 * - -3 means the square is marked with a question mark
74 * (FIXME: do we even want to bother with this?).
76 * - 64 means the square has had a mine revealed when the game
79 * - 65 means the square had a mine revealed and this was the
80 * one the player hits.
82 * - 66 means the square has a crossed-out mine because the
83 * player had incorrectly marked it.
87 static game_params *default_params(void)
89 game_params *ret = snew(game_params);
98 static const struct game_params mines_presets[] = {
107 static int game_fetch_preset(int i, char **name, game_params **params)
112 if (i < 0 || i >= lenof(mines_presets))
115 ret = snew(game_params);
116 *ret = mines_presets[i];
118 sprintf(str, "%dx%d, %d mines", ret->w, ret->h, ret->n);
125 static void free_params(game_params *params)
130 static game_params *dup_params(game_params *params)
132 game_params *ret = snew(game_params);
133 *ret = *params; /* structure copy */
137 static void decode_params(game_params *params, char const *string)
139 char const *p = string;
142 while (*p && isdigit((unsigned char)*p)) p++;
146 while (*p && isdigit((unsigned char)*p)) p++;
148 params->h = params->w;
153 while (*p && (*p == '.' || isdigit((unsigned char)*p))) p++;
155 params->n = params->w * params->h / 10;
161 params->unique = FALSE;
163 p++; /* skip any other gunk */
167 static char *encode_params(game_params *params, int full)
172 len = sprintf(ret, "%dx%d", params->w, params->h);
174 * Mine count is a generation-time parameter, since it can be
175 * deduced from the mine bitmap!
178 len += sprintf(ret+len, "n%d", params->n);
179 if (full && !params->unique)
181 assert(len < lenof(ret));
187 static config_item *game_configure(game_params *params)
192 ret = snewn(5, config_item);
194 ret[0].name = "Width";
195 ret[0].type = C_STRING;
196 sprintf(buf, "%d", params->w);
197 ret[0].sval = dupstr(buf);
200 ret[1].name = "Height";
201 ret[1].type = C_STRING;
202 sprintf(buf, "%d", params->h);
203 ret[1].sval = dupstr(buf);
206 ret[2].name = "Mines";
207 ret[2].type = C_STRING;
208 sprintf(buf, "%d", params->n);
209 ret[2].sval = dupstr(buf);
212 ret[3].name = "Ensure solubility";
213 ret[3].type = C_BOOLEAN;
215 ret[3].ival = params->unique;
225 static game_params *custom_params(config_item *cfg)
227 game_params *ret = snew(game_params);
229 ret->w = atoi(cfg[0].sval);
230 ret->h = atoi(cfg[1].sval);
231 ret->n = atoi(cfg[2].sval);
232 if (strchr(cfg[2].sval, '%'))
233 ret->n = ret->n * (ret->w * ret->h) / 100;
234 ret->unique = cfg[3].ival;
239 static char *validate_params(game_params *params)
242 * Lower limit on grid size: each dimension must be at least 3.
243 * 1 is theoretically workable if rather boring, but 2 is a
244 * real problem: there is often _no_ way to generate a uniquely
245 * solvable 2xn Mines grid. You either run into two mines
246 * blocking the way and no idea what's behind them, or one mine
247 * and no way to know which of the two rows it's in. If the
248 * mine count is even you can create a soluble grid by packing
249 * all the mines at one end (so what when you hit a two-mine
250 * wall there are only as many covered squares left as there
251 * are mines); but if it's odd, you are doomed, because you
252 * _have_ to have a gap somewhere which you can't determine the
255 if (params->w <= 2 || params->h <= 2)
256 return "Width and height must both be greater than two";
257 if (params->n > params->w * params->h - 9)
258 return "Too many mines for grid size";
261 * FIXME: Need more constraints here. Not sure what the
262 * sensible limits for Minesweeper actually are. The limits
263 * probably ought to change, however, depending on uniqueness.
269 /* ----------------------------------------------------------------------
270 * Minesweeper solver, used to ensure the generated grids are
271 * solvable without having to take risks.
275 * Count the bits in a word. Only needs to cope with 16 bits.
277 static int bitcount16(int word)
279 word = ((word & 0xAAAA) >> 1) + (word & 0x5555);
280 word = ((word & 0xCCCC) >> 2) + (word & 0x3333);
281 word = ((word & 0xF0F0) >> 4) + (word & 0x0F0F);
282 word = ((word & 0xFF00) >> 8) + (word & 0x00FF);
288 * We use a tree234 to store a large number of small localised
289 * sets, each with a mine count. We also keep some of those sets
290 * linked together into a to-do list.
293 short x, y, mask, mines;
295 struct set *prev, *next;
298 static int setcmp(void *av, void *bv)
300 struct set *a = (struct set *)av;
301 struct set *b = (struct set *)bv;
305 else if (a->y > b->y)
307 else if (a->x < b->x)
309 else if (a->x > b->x)
311 else if (a->mask < b->mask)
313 else if (a->mask > b->mask)
321 struct set *todo_head, *todo_tail;
324 static struct setstore *ss_new(void)
326 struct setstore *ss = snew(struct setstore);
327 ss->sets = newtree234(setcmp);
328 ss->todo_head = ss->todo_tail = NULL;
333 * Take two input sets, in the form (x,y,mask). Munge the first by
334 * taking either its intersection with the second or its difference
335 * with the second. Return the new mask part of the first set.
337 static int setmunge(int x1, int y1, int mask1, int x2, int y2, int mask2,
341 * Adjust the second set so that it has the same x,y
342 * coordinates as the first.
344 if (abs(x2-x1) >= 3 || abs(y2-y1) >= 3) {
348 mask2 &= ~(4|32|256);
358 mask2 &= ~(64|128|256);
370 * Invert the second set if `diff' is set (we're after A &~ B
371 * rather than A & B).
377 * Now all that's left is a logical AND.
379 return mask1 & mask2;
382 static void ss_add_todo(struct setstore *ss, struct set *s)
385 return; /* already on it */
387 #ifdef SOLVER_DIAGNOSTICS
388 printf("adding set on todo list: %d,%d %03x %d\n",
389 s->x, s->y, s->mask, s->mines);
392 s->prev = ss->todo_tail;
402 static void ss_add(struct setstore *ss, int x, int y, int mask, int mines)
409 * Normalise so that x and y are genuinely the bounding
412 while (!(mask & (1|8|64)))
414 while (!(mask & (1|2|4)))
418 * Create a set structure and add it to the tree.
420 s = snew(struct set);
426 if (add234(ss->sets, s) != s) {
428 * This set already existed! Free it and return.
435 * We've added a new set to the tree, so put it on the todo
441 static void ss_remove(struct setstore *ss, struct set *s)
443 struct set *next = s->next, *prev = s->prev;
445 #ifdef SOLVER_DIAGNOSTICS
446 printf("removing set %d,%d %03x\n", s->x, s->y, s->mask);
449 * Remove s from the todo list.
453 else if (s == ss->todo_head)
454 ss->todo_head = next;
458 else if (s == ss->todo_tail)
459 ss->todo_tail = prev;
464 * Remove s from the tree.
469 * Destroy the actual set structure.
475 * Return a dynamically allocated list of all the sets which
476 * overlap a provided input set.
478 static struct set **ss_overlap(struct setstore *ss, int x, int y, int mask)
480 struct set **ret = NULL;
481 int nret = 0, retsize = 0;
484 for (xx = x-3; xx < x+3; xx++)
485 for (yy = y-3; yy < y+3; yy++) {
490 * Find the first set with these top left coordinates.
496 if (findrelpos234(ss->sets, &stmp, NULL, REL234_GE, &pos)) {
497 while ((s = index234(ss->sets, pos)) != NULL &&
498 s->x == xx && s->y == yy) {
500 * This set potentially overlaps the input one.
501 * Compute the intersection to see if they
502 * really overlap, and add it to the list if
505 if (setmunge(x, y, mask, s->x, s->y, s->mask, FALSE)) {
507 * There's an overlap.
509 if (nret >= retsize) {
511 ret = sresize(ret, retsize, struct set *);
521 ret = sresize(ret, nret+1, struct set *);
528 * Get an element from the head of the set todo list.
530 static struct set *ss_todo(struct setstore *ss)
533 struct set *ret = ss->todo_head;
534 ss->todo_head = ret->next;
536 ss->todo_head->prev = NULL;
538 ss->todo_tail = NULL;
539 ret->next = ret->prev = NULL;
552 static void std_add(struct squaretodo *std, int i)
555 std->next[std->tail] = i;
562 typedef int (*open_cb)(void *, int, int);
564 static void known_squares(int w, int h, struct squaretodo *std,
566 open_cb open, void *openctx,
567 int x, int y, int mask, int mine)
573 for (yy = 0; yy < 3; yy++)
574 for (xx = 0; xx < 3; xx++) {
576 int i = (y + yy) * w + (x + xx);
579 * It's possible that this square is _already_
580 * known, in which case we don't try to add it to
586 grid[i] = -1; /* and don't open it! */
588 grid[i] = open(openctx, x + xx, y + yy);
589 assert(grid[i] != -1); /* *bang* */
600 * This is data returned from the `perturb' function. It details
601 * which squares have become mines and which have become clear. The
602 * solver is (of course) expected to honourably not use that
603 * knowledge directly, but to efficently adjust its internal data
604 * structures and proceed based on only the information it
607 struct perturbation {
609 int delta; /* +1 == become a mine; -1 == cleared */
611 struct perturbations {
613 struct perturbation *changes;
617 * Main solver entry point. You give it a grid of existing
618 * knowledge (-1 for a square known to be a mine, 0-8 for empty
619 * squares with a given number of neighbours, -2 for completely
620 * unknown), plus a function which you can call to open new squares
621 * once you're confident of them. It fills in as much more of the
626 * - -1 means deduction stalled and nothing could be done
627 * - 0 means deduction succeeded fully
628 * - >0 means deduction succeeded but some number of perturbation
629 * steps were required; the exact return value is the number of
633 typedef struct perturbations *(*perturb_cb) (void *, signed char *, int, int, int);
635 static int minesolve(int w, int h, int n, signed char *grid,
638 void *ctx, random_state *rs)
640 struct setstore *ss = ss_new();
642 struct squaretodo astd, *std = &astd;
647 * Set up a linked list of squares with known contents, so that
648 * we can process them one by one.
650 std->next = snewn(w*h, int);
651 std->head = std->tail = -1;
654 * Initialise that list with all known squares in the input
657 for (y = 0; y < h; y++) {
658 for (x = 0; x < w; x++) {
666 * Main deductive loop.
669 int done_something = FALSE;
673 * If there are any known squares on the todo list, process
674 * them and construct a set for each.
676 while (std->head != -1) {
678 #ifdef SOLVER_DIAGNOSTICS
679 printf("known square at %d,%d [%d]\n", i%w, i/w, grid[i]);
681 std->head = std->next[i];
689 int dx, dy, mines, bit, val;
690 #ifdef SOLVER_DIAGNOSTICS
691 printf("creating set around this square\n");
694 * Empty square. Construct the set of non-known squares
695 * around this one, and determine its mine count.
700 for (dy = -1; dy <= +1; dy++) {
701 for (dx = -1; dx <= +1; dx++) {
702 #ifdef SOLVER_DIAGNOSTICS
703 printf("grid %d,%d = %d\n", x+dx, y+dy, grid[i+dy*w+dx]);
705 if (x+dx < 0 || x+dx >= w || y+dy < 0 || y+dy >= h)
706 /* ignore this one */;
707 else if (grid[i+dy*w+dx] == -1)
709 else if (grid[i+dy*w+dx] == -2)
715 ss_add(ss, x-1, y-1, val, mines);
719 * Now, whether the square is empty or full, we must
720 * find any set which contains it and replace it with
721 * one which does not.
724 #ifdef SOLVER_DIAGNOSTICS
725 printf("finding sets containing known square %d,%d\n", x, y);
727 list = ss_overlap(ss, x, y, 1);
729 for (j = 0; list[j]; j++) {
730 int newmask, newmines;
735 * Compute the mask for this set minus the
736 * newly known square.
738 newmask = setmunge(s->x, s->y, s->mask, x, y, 1, TRUE);
741 * Compute the new mine count.
743 newmines = s->mines - (grid[i] == -1);
746 * Insert the new set into the collection,
747 * unless it's been whittled right down to
751 ss_add(ss, s->x, s->y, newmask, newmines);
754 * Destroy the old one; it is actually obsolete.
763 * Marking a fresh square as known certainly counts as
766 done_something = TRUE;
770 * Now pick a set off the to-do list and attempt deductions
773 if ((s = ss_todo(ss)) != NULL) {
775 #ifdef SOLVER_DIAGNOSTICS
776 printf("set to do: %d,%d %03x %d\n", s->x, s->y, s->mask, s->mines);
779 * Firstly, see if this set has a mine count of zero or
780 * of its own cardinality.
782 if (s->mines == 0 || s->mines == bitcount16(s->mask)) {
784 * If so, we can immediately mark all the squares
785 * in the set as known.
787 #ifdef SOLVER_DIAGNOSTICS
790 known_squares(w, h, std, grid, open, ctx,
791 s->x, s->y, s->mask, (s->mines != 0));
794 * Having done that, we need do nothing further
795 * with this set; marking all the squares in it as
796 * known will eventually eliminate it, and will
797 * also permit further deductions about anything
804 * Failing that, we now search through all the sets
805 * which overlap this one.
807 list = ss_overlap(ss, s->x, s->y, s->mask);
809 for (j = 0; list[j]; j++) {
810 struct set *s2 = list[j];
811 int swing, s2wing, swc, s2wc;
814 * Find the non-overlapping parts s2-s and s-s2,
815 * and their cardinalities.
817 * I'm going to refer to these parts as `wings'
818 * surrounding the central part common to both
819 * sets. The `s wing' is s-s2; the `s2 wing' is
822 swing = setmunge(s->x, s->y, s->mask, s2->x, s2->y, s2->mask,
824 s2wing = setmunge(s2->x, s2->y, s2->mask, s->x, s->y, s->mask,
826 swc = bitcount16(swing);
827 s2wc = bitcount16(s2wing);
830 * If one set has more mines than the other, and
831 * the number of extra mines is equal to the
832 * cardinality of that set's wing, then we can mark
833 * every square in the wing as a known mine, and
834 * every square in the other wing as known clear.
836 if (swc == s->mines - s2->mines ||
837 s2wc == s2->mines - s->mines) {
838 known_squares(w, h, std, grid, open, ctx,
840 (swc == s->mines - s2->mines));
841 known_squares(w, h, std, grid, open, ctx,
842 s2->x, s2->y, s2wing,
843 (s2wc == s2->mines - s->mines));
848 * Failing that, see if one set is a subset of the
849 * other. If so, we can divide up the mine count of
850 * the larger set between the smaller set and its
851 * complement, even if neither smaller set ends up
852 * being immediately clearable.
854 if (swc == 0 && s2wc != 0) {
855 /* s is a subset of s2. */
856 assert(s2->mines > s->mines);
857 ss_add(ss, s2->x, s2->y, s2wing, s2->mines - s->mines);
858 } else if (s2wc == 0 && swc != 0) {
859 /* s2 is a subset of s. */
860 assert(s->mines > s2->mines);
861 ss_add(ss, s->x, s->y, swing, s->mines - s2->mines);
868 * In this situation we have definitely done
869 * _something_, even if it's only reducing the size of
872 done_something = TRUE;
875 * We have nothing left on our todo list, which means
876 * all localised deductions have failed. Our next step
877 * is to resort to global deduction based on the total
878 * mine count. This is computationally expensive
879 * compared to any of the above deductions, which is
880 * why we only ever do it when all else fails, so that
881 * hopefully it won't have to happen too often.
883 * If you pass n<0 into this solver, that informs it
884 * that you do not know the total mine count, so it
885 * won't even attempt these deductions.
888 int minesleft, squaresleft;
889 int nsets, setused[10], cursor;
892 * Start by scanning the current grid state to work out
893 * how many unknown squares we still have, and how many
894 * mines are to be placed in them.
898 for (i = 0; i < w*h; i++) {
901 else if (grid[i] == -2)
905 #ifdef SOLVER_DIAGNOSTICS
906 printf("global deduction time: squaresleft=%d minesleft=%d\n",
907 squaresleft, minesleft);
908 for (y = 0; y < h; y++) {
909 for (x = 0; x < w; x++) {
925 * If there _are_ no unknown squares, we have actually
928 if (squaresleft == 0) {
929 assert(minesleft == 0);
934 * First really simple case: if there are no more mines
935 * left, or if there are exactly as many mines left as
936 * squares to play them in, then it's all easy.
938 if (minesleft == 0 || minesleft == squaresleft) {
939 for (i = 0; i < w*h; i++)
941 known_squares(w, h, std, grid, open, ctx,
942 i % w, i / w, 1, minesleft != 0);
943 continue; /* now go back to main deductive loop */
947 * Failing that, we have to do some _real_ work.
948 * Ideally what we do here is to try every single
949 * combination of the currently available sets, in an
950 * attempt to find a disjoint union (i.e. a set of
951 * squares with a known mine count between them) such
952 * that the remaining unknown squares _not_ contained
953 * in that union either contain no mines or are all
956 * Actually enumerating all 2^n possibilities will get
957 * a bit slow for large n, so I artificially cap this
958 * recursion at n=10 to avoid too much pain.
960 nsets = count234(ss->sets);
961 if (nsets <= lenof(setused)) {
963 * Doing this with actual recursive function calls
964 * would get fiddly because a load of local
965 * variables from this function would have to be
966 * passed down through the recursion. So instead
967 * I'm going to use a virtual recursion within this
968 * function. The way this works is:
970 * - we have an array `setused', such that
971 * setused[n] is 0 or 1 depending on whether set
972 * n is currently in the union we are
975 * - we have a value `cursor' which indicates how
976 * much of `setused' we have so far filled in.
977 * It's conceptually the recursion depth.
979 * We begin by setting `cursor' to zero. Then:
981 * - if cursor can advance, we advance it by one.
982 * We set the value in `setused' that it went
983 * past to 1 if that set is disjoint from
984 * anything else currently in `setused', or to 0
987 * - If cursor cannot advance because it has
988 * reached the end of the setused list, then we
989 * have a maximal disjoint union. Check to see
990 * whether its mine count has any useful
991 * properties. If so, mark all the squares not
992 * in the union as known and terminate.
994 * - If cursor has reached the end of setused and
995 * the algorithm _hasn't_ terminated, back
996 * cursor up to the nearest 1, turn it into a 0
997 * and advance cursor just past it.
999 * - If we attempt to back up to the nearest 1 and
1000 * there isn't one at all, then we have gone
1001 * through all disjoint unions of sets in the
1002 * list and none of them has been helpful, so we
1005 struct set *sets[lenof(setused)];
1006 for (i = 0; i < nsets; i++)
1007 sets[i] = index234(ss->sets, i);
1012 if (cursor < nsets) {
1015 /* See if any existing set overlaps this one. */
1016 for (i = 0; i < cursor; i++)
1018 setmunge(sets[cursor]->x,
1021 sets[i]->x, sets[i]->y, sets[i]->mask,
1029 * We're adding this set to our union,
1030 * so adjust minesleft and squaresleft
1033 minesleft -= sets[cursor]->mines;
1034 squaresleft -= bitcount16(sets[cursor]->mask);
1037 setused[cursor++] = ok;
1039 #ifdef SOLVER_DIAGNOSTICS
1040 printf("trying a set combination with %d %d\n",
1041 squaresleft, minesleft);
1042 #endif /* SOLVER_DIAGNOSTICS */
1045 * We've reached the end. See if we've got
1046 * anything interesting.
1048 if (squaresleft > 0 &&
1049 (minesleft == 0 || minesleft == squaresleft)) {
1051 * We have! There is at least one
1052 * square not contained within the set
1053 * union we've just found, and we can
1054 * deduce that either all such squares
1055 * are mines or all are not (depending
1056 * on whether minesleft==0). So now all
1057 * we have to do is actually go through
1058 * the grid, find those squares, and
1061 for (i = 0; i < w*h; i++)
1062 if (grid[i] == -2) {
1066 for (j = 0; j < nsets; j++)
1068 setmunge(sets[j]->x, sets[j]->y,
1069 sets[j]->mask, x, y, 1,
1075 known_squares(w, h, std, grid,
1077 x, y, 1, minesleft != 0);
1080 done_something = TRUE;
1081 break; /* return to main deductive loop */
1085 * If we reach here, then this union hasn't
1086 * done us any good, so move on to the
1087 * next. Backtrack cursor to the nearest 1,
1088 * change it to a 0 and continue.
1090 while (--cursor >= 0 && !setused[cursor]);
1092 assert(setused[cursor]);
1095 * We're removing this set from our
1096 * union, so re-increment minesleft and
1099 minesleft += sets[cursor]->mines;
1100 squaresleft += bitcount16(sets[cursor]->mask);
1102 setused[cursor++] = 0;
1105 * We've backtracked all the way to the
1106 * start without finding a single 1,
1107 * which means that our virtual
1108 * recursion is complete and nothing
1123 #ifdef SOLVER_DIAGNOSTICS
1125 * Dump the current known state of the grid.
1127 printf("solver ran out of steam, ret=%d, grid:\n", nperturbs);
1128 for (y = 0; y < h; y++) {
1129 for (x = 0; x < w; x++) {
1130 int v = grid[y*w+x];
1146 for (i = 0; (s = index234(ss->sets, i)) != NULL; i++)
1147 printf("remaining set: %d,%d %03x %d\n", s->x, s->y, s->mask, s->mines);
1152 * Now we really are at our wits' end as far as solving
1153 * this grid goes. Our only remaining option is to call
1154 * a perturb function and ask it to modify the grid to
1158 struct perturbations *ret;
1164 * Choose a set at random from the current selection,
1165 * and ask the perturb function to either fill or empty
1168 * If we have no sets at all, we must give up.
1170 if (count234(ss->sets) == 0) {
1171 #ifdef SOLVER_DIAGNOSTICS
1172 printf("perturbing on entire unknown set\n");
1174 ret = perturb(ctx, grid, 0, 0, 0);
1176 s = index234(ss->sets, random_upto(rs, count234(ss->sets)));
1177 #ifdef SOLVER_DIAGNOSTICS
1178 printf("perturbing on set %d,%d %03x\n", s->x, s->y, s->mask);
1180 ret = perturb(ctx, grid, s->x, s->y, s->mask);
1184 assert(ret->n > 0); /* otherwise should have been NULL */
1187 * A number of squares have been fiddled with, and
1188 * the returned structure tells us which. Adjust
1189 * the mine count in any set which overlaps one of
1190 * those squares, and put them back on the to-do
1191 * list. Also, if the square itself is marked as a
1192 * known non-mine, put it back on the squares-to-do
1195 for (i = 0; i < ret->n; i++) {
1196 #ifdef SOLVER_DIAGNOSTICS
1197 printf("perturbation %s mine at %d,%d\n",
1198 ret->changes[i].delta > 0 ? "added" : "removed",
1199 ret->changes[i].x, ret->changes[i].y);
1202 if (ret->changes[i].delta < 0 &&
1203 grid[ret->changes[i].y*w+ret->changes[i].x] != -2) {
1204 std_add(std, ret->changes[i].y*w+ret->changes[i].x);
1207 list = ss_overlap(ss,
1208 ret->changes[i].x, ret->changes[i].y, 1);
1210 for (j = 0; list[j]; j++) {
1211 list[j]->mines += ret->changes[i].delta;
1212 ss_add_todo(ss, list[j]);
1219 * Now free the returned data.
1221 sfree(ret->changes);
1224 #ifdef SOLVER_DIAGNOSTICS
1226 * Dump the current known state of the grid.
1228 printf("state after perturbation:\n");
1229 for (y = 0; y < h; y++) {
1230 for (x = 0; x < w; x++) {
1231 int v = grid[y*w+x];
1247 for (i = 0; (s = index234(ss->sets, i)) != NULL; i++)
1248 printf("remaining set: %d,%d %03x %d\n", s->x, s->y, s->mask, s->mines);
1253 * And now we can go back round the deductive loop.
1260 * If we get here, even that didn't work (either we didn't
1261 * have a perturb function or it returned failure), so we
1268 * See if we've got any unknown squares left.
1270 for (y = 0; y < h; y++)
1271 for (x = 0; x < w; x++)
1272 if (grid[y*w+x] == -2) {
1273 nperturbs = -1; /* failed to complete */
1278 * Free the set list and square-todo list.
1282 while ((s = delpos234(ss->sets, 0)) != NULL)
1284 freetree234(ss->sets);
1292 /* ----------------------------------------------------------------------
1293 * Grid generator which uses the above solver.
1300 int allow_big_perturbs;
1304 static int mineopen(void *vctx, int x, int y)
1306 struct minectx *ctx = (struct minectx *)vctx;
1309 assert(x >= 0 && x < ctx->w && y >= 0 && y < ctx->h);
1310 if (ctx->grid[y * ctx->w + x])
1311 return -1; /* *bang* */
1314 for (i = -1; i <= +1; i++) {
1315 if (x + i < 0 || x + i >= ctx->w)
1317 for (j = -1; j <= +1; j++) {
1318 if (y + j < 0 || y + j >= ctx->h)
1320 if (i == 0 && j == 0)
1322 if (ctx->grid[(y+j) * ctx->w + (x+i)])
1330 /* Structure used internally to mineperturb(). */
1332 int x, y, type, random;
1334 static int squarecmp(const void *av, const void *bv)
1336 const struct square *a = (const struct square *)av;
1337 const struct square *b = (const struct square *)bv;
1338 if (a->type < b->type)
1340 else if (a->type > b->type)
1342 else if (a->random < b->random)
1344 else if (a->random > b->random)
1346 else if (a->y < b->y)
1348 else if (a->y > b->y)
1350 else if (a->x < b->x)
1352 else if (a->x > b->x)
1358 * Normally this function is passed an (x,y,mask) set description.
1359 * On occasions, though, there is no _localised_ set being used,
1360 * and the set being perturbed is supposed to be the entirety of
1361 * the unreachable area. This is signified by the special case
1362 * mask==0: in this case, anything labelled -2 in the grid is part
1365 * Allowing perturbation in this special case appears to make it
1366 * guaranteeably possible to generate a workable grid for any mine
1367 * density, but they tend to be a bit boring, with mines packed
1368 * densely into far corners of the grid and the remainder being
1369 * less dense than one might like. Therefore, to improve overall
1370 * grid quality I disable this feature for the first few attempts,
1371 * and fall back to it after no useful grid has been generated.
1373 static struct perturbations *mineperturb(void *vctx, signed char *grid,
1374 int setx, int sety, int mask)
1376 struct minectx *ctx = (struct minectx *)vctx;
1377 struct square *sqlist;
1378 int x, y, dx, dy, i, n, nfull, nempty;
1379 struct square **tofill, **toempty, **todo;
1380 int ntofill, ntoempty, ntodo, dtodo, dset;
1381 struct perturbations *ret;
1384 if (!mask && !ctx->allow_big_perturbs)
1388 * Make a list of all the squares in the grid which we can
1389 * possibly use. This list should be in preference order, which
1392 * - first, unknown squares on the boundary of known space
1393 * - next, unknown squares beyond that boundary
1394 * - as a very last resort, known squares, but not within one
1395 * square of the starting position.
1397 * Each of these sections needs to be shuffled independently.
1398 * We do this by preparing list of all squares and then sorting
1399 * it with a random secondary key.
1401 sqlist = snewn(ctx->w * ctx->h, struct square);
1403 for (y = 0; y < ctx->h; y++)
1404 for (x = 0; x < ctx->w; x++) {
1406 * If this square is too near the starting position,
1407 * don't put it on the list at all.
1409 if (abs(y - ctx->sy) <= 1 && abs(x - ctx->sx) <= 1)
1413 * If this square is in the input set, also don't put
1416 if ((mask == 0 && grid[y*ctx->w+x] == -2) ||
1417 (x >= setx && x < setx + 3 &&
1418 y >= sety && y < sety + 3 &&
1419 mask & (1 << ((y-sety)*3+(x-setx)))))
1425 if (grid[y*ctx->w+x] != -2) {
1426 sqlist[n].type = 3; /* known square */
1429 * Unknown square. Examine everything around it and
1430 * see if it borders on any known squares. If it
1431 * does, it's class 1, otherwise it's 2.
1436 for (dy = -1; dy <= +1; dy++)
1437 for (dx = -1; dx <= +1; dx++)
1438 if (x+dx >= 0 && x+dx < ctx->w &&
1439 y+dy >= 0 && y+dy < ctx->h &&
1440 grid[(y+dy)*ctx->w+(x+dx)] != -2) {
1447 * Finally, a random number to cause qsort to
1448 * shuffle within each group.
1450 sqlist[n].random = random_bits(ctx->rs, 31);
1455 qsort(sqlist, n, sizeof(struct square), squarecmp);
1458 * Now count up the number of full and empty squares in the set
1459 * we've been provided.
1463 for (dy = 0; dy < 3; dy++)
1464 for (dx = 0; dx < 3; dx++)
1465 if (mask & (1 << (dy*3+dx))) {
1466 assert(setx+dx <= ctx->w);
1467 assert(sety+dy <= ctx->h);
1468 if (ctx->grid[(sety+dy)*ctx->w+(setx+dx)])
1474 for (y = 0; y < ctx->h; y++)
1475 for (x = 0; x < ctx->w; x++)
1476 if (grid[y*ctx->w+x] == -2) {
1477 if (ctx->grid[y*ctx->w+x])
1485 * Now go through our sorted list until we find either `nfull'
1486 * empty squares, or `nempty' full squares; these will be
1487 * swapped with the appropriate squares in the set to either
1488 * fill or empty the set while keeping the same number of mines
1491 ntofill = ntoempty = 0;
1493 tofill = snewn(9, struct square *);
1494 toempty = snewn(9, struct square *);
1496 tofill = snewn(ctx->w * ctx->h, struct square *);
1497 toempty = snewn(ctx->w * ctx->h, struct square *);
1499 for (i = 0; i < n; i++) {
1500 struct square *sq = &sqlist[i];
1501 if (ctx->grid[sq->y * ctx->w + sq->x])
1502 toempty[ntoempty++] = sq;
1504 tofill[ntofill++] = sq;
1505 if (ntofill == nfull || ntoempty == nempty)
1510 * If we haven't found enough empty squares outside the set to
1511 * empty it into _or_ enough full squares outside it to fill it
1512 * up with, we'll have to settle for doing only a partial job.
1513 * In this case we choose to always _fill_ the set (because
1514 * this case will tend to crop up when we're working with very
1515 * high mine densities and the only way to get a solvable grid
1516 * is going to be to pack most of the mines solidly around the
1517 * edges). So now our job is to make a list of the empty
1518 * squares in the set, and shuffle that list so that we fill a
1519 * random selection of them.
1521 if (ntofill != nfull && ntoempty != nempty) {
1524 assert(ntoempty != 0);
1526 setlist = snewn(ctx->w * ctx->h, int);
1529 for (dy = 0; dy < 3; dy++)
1530 for (dx = 0; dx < 3; dx++)
1531 if (mask & (1 << (dy*3+dx))) {
1532 assert(setx+dx <= ctx->w);
1533 assert(sety+dy <= ctx->h);
1534 if (!ctx->grid[(sety+dy)*ctx->w+(setx+dx)])
1535 setlist[i++] = (sety+dy)*ctx->w+(setx+dx);
1538 for (y = 0; y < ctx->h; y++)
1539 for (x = 0; x < ctx->w; x++)
1540 if (grid[y*ctx->w+x] == -2) {
1541 if (!ctx->grid[y*ctx->w+x])
1542 setlist[i++] = y*ctx->w+x;
1545 assert(i > ntoempty);
1547 * Now pick `ntoempty' items at random from the list.
1549 for (k = 0; k < ntoempty; k++) {
1550 int index = k + random_upto(ctx->rs, i - k);
1554 setlist[k] = setlist[index];
1555 setlist[index] = tmp;
1561 * Now we're pretty much there. We need to either
1562 * (a) put a mine in each of the empty squares in the set, and
1563 * take one out of each square in `toempty'
1564 * (b) take a mine out of each of the full squares in the set,
1565 * and put one in each square in `tofill'
1566 * depending on which one we've found enough squares to do.
1568 * So we start by constructing our list of changes to return to
1569 * the solver, so that it can update its data structures
1570 * efficiently rather than having to rescan the whole grid.
1572 ret = snew(struct perturbations);
1573 if (ntofill == nfull) {
1581 * (We also fall into this case if we've constructed a
1591 ret->changes = snewn(ret->n, struct perturbation);
1592 for (i = 0; i < ntodo; i++) {
1593 ret->changes[i].x = todo[i]->x;
1594 ret->changes[i].y = todo[i]->y;
1595 ret->changes[i].delta = dtodo;
1597 /* now i == ntodo */
1600 assert(todo == toempty);
1601 for (j = 0; j < ntoempty; j++) {
1602 ret->changes[i].x = setlist[j] % ctx->w;
1603 ret->changes[i].y = setlist[j] / ctx->w;
1604 ret->changes[i].delta = dset;
1609 for (dy = 0; dy < 3; dy++)
1610 for (dx = 0; dx < 3; dx++)
1611 if (mask & (1 << (dy*3+dx))) {
1612 int currval = (ctx->grid[(sety+dy)*ctx->w+(setx+dx)] ? +1 : -1);
1613 if (dset == -currval) {
1614 ret->changes[i].x = setx + dx;
1615 ret->changes[i].y = sety + dy;
1616 ret->changes[i].delta = dset;
1621 for (y = 0; y < ctx->h; y++)
1622 for (x = 0; x < ctx->w; x++)
1623 if (grid[y*ctx->w+x] == -2) {
1624 int currval = (ctx->grid[y*ctx->w+x] ? +1 : -1);
1625 if (dset == -currval) {
1626 ret->changes[i].x = x;
1627 ret->changes[i].y = y;
1628 ret->changes[i].delta = dset;
1633 assert(i == ret->n);
1639 * Having set up the precise list of changes we're going to
1640 * make, we now simply make them and return.
1642 for (i = 0; i < ret->n; i++) {
1645 x = ret->changes[i].x;
1646 y = ret->changes[i].y;
1647 delta = ret->changes[i].delta;
1650 * Check we're not trying to add an existing mine or remove
1653 assert((delta < 0) ^ (ctx->grid[y*ctx->w+x] == 0));
1656 * Actually make the change.
1658 ctx->grid[y*ctx->w+x] = (delta > 0);
1661 * Update any numbers already present in the grid.
1663 for (dy = -1; dy <= +1; dy++)
1664 for (dx = -1; dx <= +1; dx++)
1665 if (x+dx >= 0 && x+dx < ctx->w &&
1666 y+dy >= 0 && y+dy < ctx->h &&
1667 grid[(y+dy)*ctx->w+(x+dx)] != -2) {
1668 if (dx == 0 && dy == 0) {
1670 * The square itself is marked as known in
1671 * the grid. Mark it as a mine if it's a
1672 * mine, or else work out its number.
1675 grid[y*ctx->w+x] = -1;
1677 int dx2, dy2, minecount = 0;
1678 for (dy2 = -1; dy2 <= +1; dy2++)
1679 for (dx2 = -1; dx2 <= +1; dx2++)
1680 if (x+dx2 >= 0 && x+dx2 < ctx->w &&
1681 y+dy2 >= 0 && y+dy2 < ctx->h &&
1682 ctx->grid[(y+dy2)*ctx->w+(x+dx2)])
1684 grid[y*ctx->w+x] = minecount;
1687 if (grid[(y+dy)*ctx->w+(x+dx)] >= 0)
1688 grid[(y+dy)*ctx->w+(x+dx)] += delta;
1693 #ifdef GENERATION_DIAGNOSTICS
1696 printf("grid after perturbing:\n");
1697 for (yy = 0; yy < ctx->h; yy++) {
1698 for (xx = 0; xx < ctx->w; xx++) {
1699 int v = ctx->grid[yy*ctx->w+xx];
1700 if (yy == ctx->sy && xx == ctx->sx) {
1718 static char *minegen(int w, int h, int n, int x, int y, int unique,
1721 char *ret = snewn(w*h, char);
1729 memset(ret, 0, w*h);
1732 * Start by placing n mines, none of which is at x,y or within
1736 int *tmp = snewn(w*h, int);
1740 * Write down the list of possible mine locations.
1743 for (i = 0; i < h; i++)
1744 for (j = 0; j < w; j++)
1745 if (abs(i - y) > 1 || abs(j - x) > 1)
1749 * Now pick n off the list at random.
1753 i = random_upto(rs, k);
1761 #ifdef GENERATION_DIAGNOSTICS
1764 printf("grid after initial generation:\n");
1765 for (yy = 0; yy < h; yy++) {
1766 for (xx = 0; xx < w; xx++) {
1767 int v = ret[yy*w+xx];
1768 if (yy == y && xx == x) {
1784 * Now set up a results grid to run the solver in, and a
1785 * context for the solver to open squares. Then run the solver
1786 * repeatedly; if the number of perturb steps ever goes up or
1787 * it ever returns -1, give up completely.
1789 * We bypass this bit if we're not after a unique grid.
1792 signed char *solvegrid = snewn(w*h, signed char);
1793 struct minectx actx, *ctx = &actx;
1794 int solveret, prevret = -2;
1802 ctx->allow_big_perturbs = (ntries > 100);
1805 memset(solvegrid, -2, w*h);
1806 solvegrid[y*w+x] = mineopen(ctx, x, y);
1807 assert(solvegrid[y*w+x] == 0); /* by deliberate arrangement */
1810 minesolve(w, h, n, solvegrid, mineopen, mineperturb, ctx, rs);
1811 if (solveret < 0 || (prevret >= 0 && solveret >= prevret)) {
1814 } else if (solveret == 0) {
1831 * The Mines game descriptions contain the location of every mine,
1832 * and can therefore be used to cheat.
1834 * It would be pointless to attempt to _prevent_ this form of
1835 * cheating by encrypting the description, since Mines is
1836 * open-source so anyone can find out the encryption key. However,
1837 * I think it is worth doing a bit of gentle obfuscation to prevent
1838 * _accidental_ spoilers: if you happened to note that the game ID
1839 * starts with an F, for example, you might be unable to put the
1840 * knowledge of those mines out of your mind while playing. So,
1841 * just as discussions of film endings are rot13ed to avoid
1842 * spoiling it for people who don't want to be told, we apply a
1843 * keyless, reversible, but visually completely obfuscatory masking
1844 * function to the mine bitmap.
1846 static void obfuscate_bitmap(unsigned char *bmp, int bits, int decode)
1848 int bytes, firsthalf, secondhalf;
1850 unsigned char *seedstart;
1852 unsigned char *targetstart;
1858 * My obfuscation algorithm is similar in concept to the OAEP
1859 * encoding used in some forms of RSA. Here's a specification
1862 * + We have a `masking function' which constructs a stream of
1863 * pseudorandom bytes from a seed of some number of input
1866 * + We pad out our input bit stream to a whole number of
1867 * bytes by adding up to 7 zero bits on the end. (In fact
1868 * the bitmap passed as input to this function will already
1869 * have had this done in practice.)
1871 * + We divide the _byte_ stream exactly in half, rounding the
1872 * half-way position _down_. So an 81-bit input string, for
1873 * example, rounds up to 88 bits or 11 bytes, and then
1874 * dividing by two gives 5 bytes in the first half and 6 in
1877 * + We generate a mask from the second half of the bytes, and
1878 * XOR it over the first half.
1880 * + We generate a mask from the (encoded) first half of the
1881 * bytes, and XOR it over the second half. Any null bits at
1882 * the end which were added as padding are cleared back to
1883 * zero even if this operation would have made them nonzero.
1885 * To de-obfuscate, the steps are precisely the same except
1886 * that the final two are reversed.
1888 * Finally, our masking function. Given an input seed string of
1889 * bytes, the output mask consists of concatenating the SHA-1
1890 * hashes of the seed string and successive decimal integers,
1894 bytes = (bits + 7) / 8;
1895 firsthalf = bytes / 2;
1896 secondhalf = bytes - firsthalf;
1898 steps[decode ? 1 : 0].seedstart = bmp + firsthalf;
1899 steps[decode ? 1 : 0].seedlen = secondhalf;
1900 steps[decode ? 1 : 0].targetstart = bmp;
1901 steps[decode ? 1 : 0].targetlen = firsthalf;
1903 steps[decode ? 0 : 1].seedstart = bmp;
1904 steps[decode ? 0 : 1].seedlen = firsthalf;
1905 steps[decode ? 0 : 1].targetstart = bmp + firsthalf;
1906 steps[decode ? 0 : 1].targetlen = secondhalf;
1908 for (i = 0; i < 2; i++) {
1909 SHA_State base, final;
1910 unsigned char digest[20];
1912 int digestpos = 20, counter = 0;
1915 SHA_Bytes(&base, steps[i].seedstart, steps[i].seedlen);
1917 for (j = 0; j < steps[i].targetlen; j++) {
1918 if (digestpos >= 20) {
1919 sprintf(numberbuf, "%d", counter++);
1921 SHA_Bytes(&final, numberbuf, strlen(numberbuf));
1922 SHA_Final(&final, digest);
1925 steps[i].targetstart[j] ^= digest[digestpos++];
1929 * Mask off the pad bits in the final byte after both steps.
1932 bmp[bits / 8] &= 0xFF & (0xFF00 >> (bits % 8));
1936 static char *describe_layout(char *grid, int area, int x, int y,
1944 * Set up the mine bitmap and obfuscate it.
1946 bmp = snewn((area + 7) / 8, unsigned char);
1947 memset(bmp, 0, (area + 7) / 8);
1948 for (i = 0; i < area; i++) {
1950 bmp[i / 8] |= 0x80 >> (i % 8);
1953 obfuscate_bitmap(bmp, area, FALSE);
1956 * Now encode the resulting bitmap in hex. We can work to
1957 * nibble rather than byte granularity, since the obfuscation
1958 * function guarantees to return a bit string of the same
1959 * length as its input.
1961 ret = snewn((area+3)/4 + 100, char);
1962 p = ret + sprintf(ret, "%d,%d,%s", x, y,
1963 obfuscate ? "m" : ""); /* 'm' == masked */
1964 for (i = 0; i < (area+3)/4; i++) {
1968 *p++ = "0123456789abcdef"[v & 0xF];
1977 static char *new_mine_layout(int w, int h, int n, int x, int y, int unique,
1978 random_state *rs, char **game_desc)
1982 #ifdef TEST_OBFUSCATION
1983 static int tested_obfuscation = FALSE;
1984 if (!tested_obfuscation) {
1986 * A few simple test vectors for the obfuscator.
1988 * First test: the 28-bit stream 1234567. This divides up
1989 * into 1234 and 567[0]. The SHA of 56 70 30 (appending
1990 * "0") is 15ce8ab946640340bbb99f3f48fd2c45d1a31d30. Thus,
1991 * we XOR the 16-bit string 15CE into the input 1234 to get
1992 * 07FA. Next, we SHA that with "0": the SHA of 07 FA 30 is
1993 * 3370135c5e3da4fed937adc004a79533962b6391. So we XOR the
1994 * 12-bit string 337 into the input 567 to get 650. Thus
1995 * our output is 07FA650.
1998 unsigned char bmp1[] = "\x12\x34\x56\x70";
1999 obfuscate_bitmap(bmp1, 28, FALSE);
2000 printf("test 1 encode: %s\n",
2001 memcmp(bmp1, "\x07\xfa\x65\x00", 4) ? "failed" : "passed");
2002 obfuscate_bitmap(bmp1, 28, TRUE);
2003 printf("test 1 decode: %s\n",
2004 memcmp(bmp1, "\x12\x34\x56\x70", 4) ? "failed" : "passed");
2007 * Second test: a long string to make sure we switch from
2008 * one SHA to the next correctly. My input string this time
2009 * is simply fifty bytes of zeroes.
2012 unsigned char bmp2[50];
2013 unsigned char bmp2a[50];
2014 memset(bmp2, 0, 50);
2015 memset(bmp2a, 0, 50);
2016 obfuscate_bitmap(bmp2, 50 * 8, FALSE);
2018 * SHA of twenty-five zero bytes plus "0" is
2019 * b202c07b990c01f6ff2d544707f60e506019b671. SHA of
2020 * twenty-five zero bytes plus "1" is
2021 * fcb1d8b5a2f6b592fe6780b36aa9d65dd7aa6db9. Thus our
2022 * first half becomes
2023 * b202c07b990c01f6ff2d544707f60e506019b671fcb1d8b5a2.
2025 * SHA of that lot plus "0" is
2026 * 10b0af913db85d37ca27f52a9f78bba3a80030db. SHA of the
2027 * same string plus "1" is
2028 * 3d01d8df78e76d382b8106f480135a1bc751d725. So the
2029 * second half becomes
2030 * 10b0af913db85d37ca27f52a9f78bba3a80030db3d01d8df78.
2032 printf("test 2 encode: %s\n",
2033 memcmp(bmp2, "\xb2\x02\xc0\x7b\x99\x0c\x01\xf6\xff\x2d\x54"
2034 "\x47\x07\xf6\x0e\x50\x60\x19\xb6\x71\xfc\xb1\xd8"
2035 "\xb5\xa2\x10\xb0\xaf\x91\x3d\xb8\x5d\x37\xca\x27"
2036 "\xf5\x2a\x9f\x78\xbb\xa3\xa8\x00\x30\xdb\x3d\x01"
2037 "\xd8\xdf\x78", 50) ? "failed" : "passed");
2038 obfuscate_bitmap(bmp2, 50 * 8, TRUE);
2039 printf("test 2 decode: %s\n",
2040 memcmp(bmp2, bmp2a, 50) ? "failed" : "passed");
2045 grid = minegen(w, h, n, x, y, unique, rs);
2048 *game_desc = describe_layout(grid, w * h, x, y, TRUE);
2053 static char *new_game_desc(game_params *params, random_state *rs,
2054 game_aux_info **aux, int interactive)
2057 * We generate the coordinates of an initial click even if they
2058 * aren't actually used. This has the effect of harmonising the
2059 * random number usage between interactive and batch use: if
2060 * you use `mines --generate' with an explicit random seed, you
2061 * should get exactly the same results as if you type the same
2062 * random seed into the interactive game and click in the same
2063 * initial location. (Of course you won't get the same grid if
2064 * you click in a _different_ initial location, but there's
2065 * nothing to be done about that.)
2067 int x = random_upto(rs, params->w);
2068 int y = random_upto(rs, params->h);
2072 * For batch-generated grids, pre-open one square.
2077 grid = new_mine_layout(params->w, params->h, params->n,
2078 x, y, params->unique, rs, &desc);
2082 char *rsdesc, *desc;
2084 rsdesc = random_state_encode(rs);
2085 desc = snewn(strlen(rsdesc) + 100, char);
2086 sprintf(desc, "r%d,%c,%s", params->n, (char)(params->unique ? 'u' : 'a'), rsdesc);
2092 static void game_free_aux_info(game_aux_info *aux)
2094 assert(!"Shouldn't happen");
2097 static char *validate_desc(game_params *params, char *desc)
2099 int wh = params->w * params->h;
2103 if (!*desc || !isdigit((unsigned char)*desc))
2104 return "No initial mine count in game description";
2105 while (*desc && isdigit((unsigned char)*desc))
2106 desc++; /* skip over mine count */
2108 return "No ',' after initial x-coordinate in game description";
2110 if (*desc != 'u' && *desc != 'a')
2111 return "No uniqueness specifier in game description";
2114 return "No ',' after uniqueness specifier in game description";
2115 /* now ignore the rest */
2117 if (!*desc || !isdigit((unsigned char)*desc))
2118 return "No initial x-coordinate in game description";
2120 if (x < 0 || x >= params->w)
2121 return "Initial x-coordinate was out of range";
2122 while (*desc && isdigit((unsigned char)*desc))
2123 desc++; /* skip over x coordinate */
2125 return "No ',' after initial x-coordinate in game description";
2126 desc++; /* eat comma */
2127 if (!*desc || !isdigit((unsigned char)*desc))
2128 return "No initial y-coordinate in game description";
2130 if (y < 0 || y >= params->h)
2131 return "Initial y-coordinate was out of range";
2132 while (*desc && isdigit((unsigned char)*desc))
2133 desc++; /* skip over y coordinate */
2135 return "No ',' after initial y-coordinate in game description";
2136 desc++; /* eat comma */
2137 /* eat `m', meaning `masked', if present */
2140 /* now just check length of remainder */
2141 if (strlen(desc) != (wh+3)/4)
2142 return "Game description is wrong length";
2148 static int open_square(game_state *state, int x, int y)
2150 int w = state->w, h = state->h;
2151 int xx, yy, nmines, ncovered;
2153 if (!state->layout->mines) {
2155 * We have a preliminary game in which the mine layout
2156 * hasn't been generated yet. Generate it based on the
2157 * initial click location.
2160 state->layout->mines = new_mine_layout(w, h, state->layout->n,
2161 x, y, state->layout->unique,
2164 midend_supersede_game_desc(state->layout->me, desc);
2166 random_free(state->layout->rs);
2167 state->layout->rs = NULL;
2170 if (state->layout->mines[y*w+x]) {
2172 * The player has landed on a mine. Bad luck. Expose the
2173 * mine that killed them, but not the rest (in case they
2174 * want to Undo and carry on playing).
2177 state->grid[y*w+x] = 65;
2182 * Otherwise, the player has opened a safe square. Mark it to-do.
2184 state->grid[y*w+x] = -10; /* `todo' value internal to this func */
2187 * Now go through the grid finding all `todo' values and
2188 * opening them. Every time one of them turns out to have no
2189 * neighbouring mines, we add all its unopened neighbours to
2192 * FIXME: We really ought to be able to do this better than
2193 * using repeated N^2 scans of the grid.
2196 int done_something = FALSE;
2198 for (yy = 0; yy < h; yy++)
2199 for (xx = 0; xx < w; xx++)
2200 if (state->grid[yy*w+xx] == -10) {
2203 assert(!state->layout->mines[yy*w+xx]);
2207 for (dx = -1; dx <= +1; dx++)
2208 for (dy = -1; dy <= +1; dy++)
2209 if (xx+dx >= 0 && xx+dx < state->w &&
2210 yy+dy >= 0 && yy+dy < state->h &&
2211 state->layout->mines[(yy+dy)*w+(xx+dx)])
2214 state->grid[yy*w+xx] = v;
2217 for (dx = -1; dx <= +1; dx++)
2218 for (dy = -1; dy <= +1; dy++)
2219 if (xx+dx >= 0 && xx+dx < state->w &&
2220 yy+dy >= 0 && yy+dy < state->h &&
2221 state->grid[(yy+dy)*w+(xx+dx)] == -2)
2222 state->grid[(yy+dy)*w+(xx+dx)] = -10;
2225 done_something = TRUE;
2228 if (!done_something)
2233 * Finally, scan the grid and see if exactly as many squares
2234 * are still covered as there are mines. If so, set the `won'
2235 * flag and fill in mine markers on all covered squares.
2237 nmines = ncovered = 0;
2238 for (yy = 0; yy < h; yy++)
2239 for (xx = 0; xx < w; xx++) {
2240 if (state->grid[yy*w+xx] < 0)
2242 if (state->layout->mines[yy*w+xx])
2245 assert(ncovered >= nmines);
2246 if (ncovered == nmines) {
2247 for (yy = 0; yy < h; yy++)
2248 for (xx = 0; xx < w; xx++) {
2249 if (state->grid[yy*w+xx] < 0)
2250 state->grid[yy*w+xx] = -1;
2258 static game_state *new_game(midend_data *me, game_params *params, char *desc)
2260 game_state *state = snew(game_state);
2261 int i, wh, x, y, ret, masked;
2264 state->w = params->w;
2265 state->h = params->h;
2266 state->n = params->n;
2267 state->dead = state->won = FALSE;
2268 state->used_solve = state->just_used_solve = FALSE;
2270 wh = state->w * state->h;
2272 state->layout = snew(struct mine_layout);
2273 memset(state->layout, 0, sizeof(struct mine_layout));
2274 state->layout->refcount = 1;
2276 state->grid = snewn(wh, signed char);
2277 memset(state->grid, -2, wh);
2281 state->layout->n = atoi(desc);
2282 while (*desc && isdigit((unsigned char)*desc))
2283 desc++; /* skip over mine count */
2284 if (*desc) desc++; /* eat comma */
2286 state->layout->unique = FALSE;
2288 state->layout->unique = TRUE;
2290 if (*desc) desc++; /* eat comma */
2292 state->layout->mines = NULL;
2293 state->layout->rs = random_state_decode(desc);
2294 state->layout->me = me;
2297 state->layout->rs = NULL;
2298 state->layout->me = NULL;
2300 state->layout->mines = snewn(wh, char);
2302 while (*desc && isdigit((unsigned char)*desc))
2303 desc++; /* skip over x coordinate */
2304 if (*desc) desc++; /* eat comma */
2306 while (*desc && isdigit((unsigned char)*desc))
2307 desc++; /* skip over y coordinate */
2308 if (*desc) desc++; /* eat comma */
2315 * We permit game IDs to be entered by hand without the
2316 * masking transformation.
2321 bmp = snewn((wh + 7) / 8, unsigned char);
2322 memset(bmp, 0, (wh + 7) / 8);
2323 for (i = 0; i < (wh+3)/4; i++) {
2327 assert(c != 0); /* validate_desc should have caught */
2328 if (c >= '0' && c <= '9')
2330 else if (c >= 'a' && c <= 'f')
2332 else if (c >= 'A' && c <= 'F')
2337 bmp[i / 2] |= v << (4 * (1 - (i % 2)));
2341 obfuscate_bitmap(bmp, wh, TRUE);
2343 memset(state->layout->mines, 0, wh);
2344 for (i = 0; i < wh; i++) {
2345 if (bmp[i / 8] & (0x80 >> (i % 8)))
2346 state->layout->mines[i] = 1;
2349 ret = open_square(state, x, y);
2356 static game_state *dup_game(game_state *state)
2358 game_state *ret = snew(game_state);
2363 ret->dead = state->dead;
2364 ret->won = state->won;
2365 ret->used_solve = state->used_solve;
2366 ret->just_used_solve = state->just_used_solve;
2367 ret->layout = state->layout;
2368 ret->layout->refcount++;
2369 ret->grid = snewn(ret->w * ret->h, signed char);
2370 memcpy(ret->grid, state->grid, ret->w * ret->h);
2375 static void free_game(game_state *state)
2377 if (--state->layout->refcount <= 0) {
2378 sfree(state->layout->mines);
2379 if (state->layout->rs)
2380 random_free(state->layout->rs);
2381 sfree(state->layout);
2387 static game_state *solve_game(game_state *state, game_aux_info *aux,
2391 * Simply expose the entire grid as if it were a completed
2397 if (!state->layout->mines) {
2398 *error = "Game has not been started yet";
2402 ret = dup_game(state);
2403 for (yy = 0; yy < ret->h; yy++)
2404 for (xx = 0; xx < ret->w; xx++) {
2406 if (ret->layout->mines[yy*ret->w+xx]) {
2407 ret->grid[yy*ret->w+xx] = -1;
2413 for (dx = -1; dx <= +1; dx++)
2414 for (dy = -1; dy <= +1; dy++)
2415 if (xx+dx >= 0 && xx+dx < ret->w &&
2416 yy+dy >= 0 && yy+dy < ret->h &&
2417 ret->layout->mines[(yy+dy)*ret->w+(xx+dx)])
2420 ret->grid[yy*ret->w+xx] = v;
2423 ret->used_solve = ret->just_used_solve = TRUE;
2429 static char *game_text_format(game_state *state)
2434 ret = snewn((state->w + 1) * state->h + 1, char);
2435 for (y = 0; y < state->h; y++) {
2436 for (x = 0; x < state->w; x++) {
2437 int v = state->grid[y*state->w+x];
2440 else if (v >= 1 && v <= 8)
2444 else if (v == -2 || v == -3)
2448 ret[y * (state->w+1) + x] = v;
2450 ret[y * (state->w+1) + state->w] = '\n';
2452 ret[(state->w + 1) * state->h] = '\0';
2458 int hx, hy, hradius; /* for mouse-down highlights */
2463 static game_ui *new_ui(game_state *state)
2465 game_ui *ui = snew(game_ui);
2466 ui->hx = ui->hy = -1;
2469 ui->flash_is_death = FALSE; /* *shrug* */
2473 static void free_ui(game_ui *ui)
2478 static game_state *make_move(game_state *from, game_ui *ui, game_drawstate *ds,
2479 int x, int y, int button)
2484 if (from->dead || from->won)
2485 return NULL; /* no further moves permitted */
2487 if (!IS_MOUSE_DOWN(button) && !IS_MOUSE_DRAG(button) &&
2488 !IS_MOUSE_RELEASE(button))
2493 if (cx < 0 || cx >= from->w || cy < 0 || cy >= from->h)
2496 if (button == LEFT_BUTTON || button == LEFT_DRAG ||
2497 button == MIDDLE_BUTTON || button == MIDDLE_DRAG) {
2499 * Mouse-downs and mouse-drags just cause highlighting
2504 ui->hradius = (from->grid[cy*from->w+cx] >= 0 ? 1 : 0);
2508 if (button == RIGHT_BUTTON) {
2510 * Right-clicking only works on a covered square, and it
2511 * toggles between -1 (marked as mine) and -2 (not marked
2514 * FIXME: question marks.
2516 if (from->grid[cy * from->w + cx] != -2 &&
2517 from->grid[cy * from->w + cx] != -1)
2520 ret = dup_game(from);
2521 ret->just_used_solve = FALSE;
2522 ret->grid[cy * from->w + cx] ^= (-2 ^ -1);
2527 if (button == LEFT_RELEASE || button == MIDDLE_RELEASE) {
2528 ui->hx = ui->hy = -1;
2532 * At this stage we must never return NULL: we have adjusted
2533 * the ui, so at worst we return `from'.
2537 * Left-clicking on a covered square opens a tile. Not
2538 * permitted if the tile is marked as a mine, for safety.
2539 * (Unmark it and _then_ open it.)
2541 if (button == LEFT_RELEASE &&
2542 (from->grid[cy * from->w + cx] == -2 ||
2543 from->grid[cy * from->w + cx] == -3)) {
2544 ret = dup_game(from);
2545 ret->just_used_solve = FALSE;
2546 open_square(ret, cx, cy);
2553 * Left-clicking or middle-clicking on an uncovered tile:
2554 * first we check to see if the number of mine markers
2555 * surrounding the tile is equal to its mine count, and if
2556 * so then we open all other surrounding squares.
2558 if (from->grid[cy * from->w + cx] > 0) {
2561 /* Count mine markers. */
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)
2571 if (n == from->grid[cy * from->w + cx]) {
2572 ret = dup_game(from);
2573 ret->just_used_solve = FALSE;
2574 for (dy = -1; dy <= +1; dy++)
2575 for (dx = -1; dx <= +1; dx++)
2576 if (cx+dx >= 0 && cx+dx < ret->w &&
2577 cy+dy >= 0 && cy+dy < ret->h &&
2578 (ret->grid[(cy+dy)*ret->w+(cx+dx)] == -2 ||
2579 ret->grid[(cy+dy)*ret->w+(cx+dx)] == -3))
2580 open_square(ret, cx+dx, cy+dy);
2593 /* ----------------------------------------------------------------------
2597 struct game_drawstate {
2601 * Items in this `grid' array have all the same values as in
2602 * the game_state grid, and in addition:
2604 * - -10 means the tile was drawn `specially' as a result of a
2605 * flash, so it will always need redrawing.
2607 * - -22 and -23 mean the tile is highlighted for a possible
2612 static void game_size(game_params *params, int *x, int *y)
2614 *x = BORDER * 2 + TILE_SIZE * params->w;
2615 *y = BORDER * 2 + TILE_SIZE * params->h;
2618 static float *game_colours(frontend *fe, game_state *state, int *ncolours)
2620 float *ret = snewn(3 * NCOLOURS, float);
2622 frontend_default_colour(fe, &ret[COL_BACKGROUND * 3]);
2624 ret[COL_BACKGROUND2 * 3 + 0] = ret[COL_BACKGROUND * 3 + 0] * 19.0 / 20.0;
2625 ret[COL_BACKGROUND2 * 3 + 1] = ret[COL_BACKGROUND * 3 + 1] * 19.0 / 20.0;
2626 ret[COL_BACKGROUND2 * 3 + 2] = ret[COL_BACKGROUND * 3 + 2] * 19.0 / 20.0;
2628 ret[COL_1 * 3 + 0] = 0.0F;
2629 ret[COL_1 * 3 + 1] = 0.0F;
2630 ret[COL_1 * 3 + 2] = 1.0F;
2632 ret[COL_2 * 3 + 0] = 0.0F;
2633 ret[COL_2 * 3 + 1] = 0.5F;
2634 ret[COL_2 * 3 + 2] = 0.0F;
2636 ret[COL_3 * 3 + 0] = 1.0F;
2637 ret[COL_3 * 3 + 1] = 0.0F;
2638 ret[COL_3 * 3 + 2] = 0.0F;
2640 ret[COL_4 * 3 + 0] = 0.0F;
2641 ret[COL_4 * 3 + 1] = 0.0F;
2642 ret[COL_4 * 3 + 2] = 0.5F;
2644 ret[COL_5 * 3 + 0] = 0.5F;
2645 ret[COL_5 * 3 + 1] = 0.0F;
2646 ret[COL_5 * 3 + 2] = 0.0F;
2648 ret[COL_6 * 3 + 0] = 0.0F;
2649 ret[COL_6 * 3 + 1] = 0.5F;
2650 ret[COL_6 * 3 + 2] = 0.5F;
2652 ret[COL_7 * 3 + 0] = 0.0F;
2653 ret[COL_7 * 3 + 1] = 0.0F;
2654 ret[COL_7 * 3 + 2] = 0.0F;
2656 ret[COL_8 * 3 + 0] = 0.5F;
2657 ret[COL_8 * 3 + 1] = 0.5F;
2658 ret[COL_8 * 3 + 2] = 0.5F;
2660 ret[COL_MINE * 3 + 0] = 0.0F;
2661 ret[COL_MINE * 3 + 1] = 0.0F;
2662 ret[COL_MINE * 3 + 2] = 0.0F;
2664 ret[COL_BANG * 3 + 0] = 1.0F;
2665 ret[COL_BANG * 3 + 1] = 0.0F;
2666 ret[COL_BANG * 3 + 2] = 0.0F;
2668 ret[COL_CROSS * 3 + 0] = 1.0F;
2669 ret[COL_CROSS * 3 + 1] = 0.0F;
2670 ret[COL_CROSS * 3 + 2] = 0.0F;
2672 ret[COL_FLAG * 3 + 0] = 1.0F;
2673 ret[COL_FLAG * 3 + 1] = 0.0F;
2674 ret[COL_FLAG * 3 + 2] = 0.0F;
2676 ret[COL_FLAGBASE * 3 + 0] = 0.0F;
2677 ret[COL_FLAGBASE * 3 + 1] = 0.0F;
2678 ret[COL_FLAGBASE * 3 + 2] = 0.0F;
2680 ret[COL_QUERY * 3 + 0] = 0.0F;
2681 ret[COL_QUERY * 3 + 1] = 0.0F;
2682 ret[COL_QUERY * 3 + 2] = 0.0F;
2684 ret[COL_HIGHLIGHT * 3 + 0] = 1.0F;
2685 ret[COL_HIGHLIGHT * 3 + 1] = 1.0F;
2686 ret[COL_HIGHLIGHT * 3 + 2] = 1.0F;
2688 ret[COL_LOWLIGHT * 3 + 0] = ret[COL_BACKGROUND * 3 + 0] * 2.0 / 3.0;
2689 ret[COL_LOWLIGHT * 3 + 1] = ret[COL_BACKGROUND * 3 + 1] * 2.0 / 3.0;
2690 ret[COL_LOWLIGHT * 3 + 2] = ret[COL_BACKGROUND * 3 + 2] * 2.0 / 3.0;
2692 *ncolours = NCOLOURS;
2696 static game_drawstate *game_new_drawstate(game_state *state)
2698 struct game_drawstate *ds = snew(struct game_drawstate);
2702 ds->started = FALSE;
2703 ds->grid = snewn(ds->w * ds->h, signed char);
2705 memset(ds->grid, -99, ds->w * ds->h);
2710 static void game_free_drawstate(game_drawstate *ds)
2716 static void draw_tile(frontend *fe, int x, int y, int v, int bg)
2722 if (v == -22 || v == -23) {
2726 * Omit the highlights in this case.
2728 draw_rect(fe, x, y, TILE_SIZE, TILE_SIZE,
2729 bg == COL_BACKGROUND ? COL_BACKGROUND2 : bg);
2730 draw_line(fe, x, y, x + TILE_SIZE - 1, y, COL_LOWLIGHT);
2731 draw_line(fe, x, y, x, y + TILE_SIZE - 1, COL_LOWLIGHT);
2734 * Draw highlights to indicate the square is covered.
2736 coords[0] = x + TILE_SIZE - 1;
2737 coords[1] = y + TILE_SIZE - 1;
2738 coords[2] = x + TILE_SIZE - 1;
2741 coords[5] = y + TILE_SIZE - 1;
2742 draw_polygon(fe, coords, 3, TRUE, COL_LOWLIGHT ^ hl);
2743 draw_polygon(fe, coords, 3, FALSE, COL_LOWLIGHT ^ hl);
2747 draw_polygon(fe, coords, 3, TRUE, COL_HIGHLIGHT ^ hl);
2748 draw_polygon(fe, coords, 3, FALSE, COL_HIGHLIGHT ^ hl);
2750 draw_rect(fe, x + HIGHLIGHT_WIDTH, y + HIGHLIGHT_WIDTH,
2751 TILE_SIZE - 2*HIGHLIGHT_WIDTH, TILE_SIZE - 2*HIGHLIGHT_WIDTH,
2759 #define SETCOORD(n, dx, dy) do { \
2760 coords[(n)*2+0] = x + TILE_SIZE * (dx); \
2761 coords[(n)*2+1] = y + TILE_SIZE * (dy); \
2763 SETCOORD(0, 0.6, 0.35);
2764 SETCOORD(1, 0.6, 0.7);
2765 SETCOORD(2, 0.8, 0.8);
2766 SETCOORD(3, 0.25, 0.8);
2767 SETCOORD(4, 0.55, 0.7);
2768 SETCOORD(5, 0.55, 0.35);
2769 draw_polygon(fe, coords, 6, TRUE, COL_FLAGBASE);
2770 draw_polygon(fe, coords, 6, FALSE, COL_FLAGBASE);
2772 SETCOORD(0, 0.6, 0.2);
2773 SETCOORD(1, 0.6, 0.5);
2774 SETCOORD(2, 0.2, 0.35);
2775 draw_polygon(fe, coords, 3, TRUE, COL_FLAG);
2776 draw_polygon(fe, coords, 3, FALSE, COL_FLAG);
2779 } else if (v == -3) {
2781 * Draw a question mark.
2783 draw_text(fe, x + TILE_SIZE / 2, y + TILE_SIZE / 2,
2784 FONT_VARIABLE, TILE_SIZE * 6 / 8,
2785 ALIGN_VCENTRE | ALIGN_HCENTRE,
2790 * Clear the square to the background colour, and draw thin
2791 * grid lines along the top and left.
2793 * Exception is that for value 65 (mine we've just trodden
2794 * on), we clear the square to COL_BANG.
2796 draw_rect(fe, x, y, TILE_SIZE, TILE_SIZE,
2797 (v == 65 ? COL_BANG :
2798 bg == COL_BACKGROUND ? COL_BACKGROUND2 : bg));
2799 draw_line(fe, x, y, x + TILE_SIZE - 1, y, COL_LOWLIGHT);
2800 draw_line(fe, x, y, x, y + TILE_SIZE - 1, COL_LOWLIGHT);
2802 if (v > 0 && v <= 8) {
2809 draw_text(fe, x + TILE_SIZE / 2, y + TILE_SIZE / 2,
2810 FONT_VARIABLE, TILE_SIZE * 7 / 8,
2811 ALIGN_VCENTRE | ALIGN_HCENTRE,
2812 (COL_1 - 1) + v, str);
2814 } else if (v >= 64) {
2818 * FIXME: this could be done better!
2821 draw_text(fe, x + TILE_SIZE / 2, y + TILE_SIZE / 2,
2822 FONT_VARIABLE, TILE_SIZE * 7 / 8,
2823 ALIGN_VCENTRE | ALIGN_HCENTRE,
2827 int cx = x + TILE_SIZE / 2;
2828 int cy = y + TILE_SIZE / 2;
2829 int r = TILE_SIZE / 2 - 3;
2831 int xdx = 1, xdy = 0, ydx = 0, ydy = 1;
2834 for (i = 0; i < 4*5*2; i += 5*2) {
2835 coords[i+2*0+0] = cx - r/6*xdx + r*4/5*ydx;
2836 coords[i+2*0+1] = cy - r/6*xdy + r*4/5*ydy;
2837 coords[i+2*1+0] = cx - r/6*xdx + r*ydx;
2838 coords[i+2*1+1] = cy - r/6*xdy + r*ydy;
2839 coords[i+2*2+0] = cx + r/6*xdx + r*ydx;
2840 coords[i+2*2+1] = cy + r/6*xdy + r*ydy;
2841 coords[i+2*3+0] = cx + r/6*xdx + r*4/5*ydx;
2842 coords[i+2*3+1] = cy + r/6*xdy + r*4/5*ydy;
2843 coords[i+2*4+0] = cx + r*3/5*xdx + r*3/5*ydx;
2844 coords[i+2*4+1] = cy + r*3/5*xdy + r*3/5*ydy;
2854 draw_polygon(fe, coords, 5*4, TRUE, COL_MINE);
2855 draw_polygon(fe, coords, 5*4, FALSE, COL_MINE);
2857 draw_rect(fe, cx-r/3, cy-r/3, r/3, r/4, COL_HIGHLIGHT);
2863 * Cross through the mine.
2866 for (dx = -1; dx <= +1; dx++) {
2867 draw_line(fe, x + 3 + dx, y + 2,
2868 x + TILE_SIZE - 3 + dx,
2869 y + TILE_SIZE - 2, COL_CROSS);
2870 draw_line(fe, x + TILE_SIZE - 3 + dx, y + 2,
2871 x + 3 + dx, y + TILE_SIZE - 2,
2878 draw_update(fe, x, y, TILE_SIZE, TILE_SIZE);
2881 static void game_redraw(frontend *fe, game_drawstate *ds, game_state *oldstate,
2882 game_state *state, int dir, game_ui *ui,
2883 float animtime, float flashtime)
2886 int mines, markers, bg;
2889 int frame = (flashtime / FLASH_FRAME);
2891 bg = (ui->flash_is_death ? COL_BACKGROUND : COL_LOWLIGHT);
2893 bg = (ui->flash_is_death ? COL_BANG : COL_HIGHLIGHT);
2895 bg = COL_BACKGROUND;
2901 TILE_SIZE * state->w + 2 * BORDER,
2902 TILE_SIZE * state->h + 2 * BORDER, COL_BACKGROUND);
2903 draw_update(fe, 0, 0,
2904 TILE_SIZE * state->w + 2 * BORDER,
2905 TILE_SIZE * state->h + 2 * BORDER);
2908 * Recessed area containing the whole puzzle.
2910 coords[0] = COORD(state->w) + OUTER_HIGHLIGHT_WIDTH - 1;
2911 coords[1] = COORD(state->h) + OUTER_HIGHLIGHT_WIDTH - 1;
2912 coords[2] = COORD(state->w) + OUTER_HIGHLIGHT_WIDTH - 1;
2913 coords[3] = COORD(0) - OUTER_HIGHLIGHT_WIDTH;
2914 coords[4] = coords[2] - TILE_SIZE;
2915 coords[5] = coords[3] + TILE_SIZE;
2916 coords[8] = COORD(0) - OUTER_HIGHLIGHT_WIDTH;
2917 coords[9] = COORD(state->h) + OUTER_HIGHLIGHT_WIDTH - 1;
2918 coords[6] = coords[8] + TILE_SIZE;
2919 coords[7] = coords[9] - TILE_SIZE;
2920 draw_polygon(fe, coords, 5, TRUE, COL_HIGHLIGHT);
2921 draw_polygon(fe, coords, 5, FALSE, COL_HIGHLIGHT);
2923 coords[1] = COORD(0) - OUTER_HIGHLIGHT_WIDTH;
2924 coords[0] = COORD(0) - OUTER_HIGHLIGHT_WIDTH;
2925 draw_polygon(fe, coords, 5, TRUE, COL_LOWLIGHT);
2926 draw_polygon(fe, coords, 5, FALSE, COL_LOWLIGHT);
2932 * Now draw the tiles. Also in this loop, count up the number
2933 * of mines and mine markers.
2935 mines = markers = 0;
2936 for (y = 0; y < ds->h; y++)
2937 for (x = 0; x < ds->w; x++) {
2938 int v = state->grid[y*ds->w+x];
2942 if (state->layout->mines && state->layout->mines[y*ds->w+x])
2945 if ((v == -2 || v == -3) &&
2946 (abs(x-ui->hx) <= ui->hradius && abs(y-ui->hy) <= ui->hradius))
2949 if (ds->grid[y*ds->w+x] != v || bg != COL_BACKGROUND) {
2950 draw_tile(fe, COORD(x), COORD(y), v, bg);
2951 ds->grid[y*ds->w+x] = (bg == COL_BACKGROUND ? v : -10);
2955 if (!state->layout->mines)
2956 mines = state->layout->n;
2959 * Update the status bar.
2962 char statusbar[512];
2964 sprintf(statusbar, "DEAD!");
2965 } else if (state->won) {
2966 if (state->used_solve)
2967 sprintf(statusbar, "Auto-solved.");
2969 sprintf(statusbar, "COMPLETED!");
2971 sprintf(statusbar, "Marked: %d / %d", markers, mines);
2974 sprintf(statusbar + strlen(statusbar),
2975 " Deaths: %d", ui->deaths);
2976 status_bar(fe, statusbar);
2980 static float game_anim_length(game_state *oldstate, game_state *newstate,
2981 int dir, game_ui *ui)
2986 static float game_flash_length(game_state *oldstate, game_state *newstate,
2987 int dir, game_ui *ui)
2989 if (oldstate->used_solve || newstate->used_solve)
2992 if (dir > 0 && !oldstate->dead && !oldstate->won) {
2993 if (newstate->dead) {
2994 ui->flash_is_death = TRUE;
2995 return 3 * FLASH_FRAME;
2997 if (newstate->won) {
2998 ui->flash_is_death = FALSE;
2999 return 2 * FLASH_FRAME;
3005 static int game_wants_statusbar(void)
3010 static int game_timing_state(game_state *state)
3012 if (state->dead || state->won || !state->layout->mines)
3018 #define thegame mines
3021 const struct game thegame = {
3022 "Mines", "games.mines",
3029 TRUE, game_configure, custom_params,
3038 TRUE, game_text_format,
3045 game_free_drawstate,
3049 game_wants_statusbar,
3050 TRUE, game_timing_state,
3051 BUTTON_BEATS(LEFT_BUTTON, RIGHT_BUTTON),
3054 #ifdef STANDALONE_OBFUSCATOR
3057 * Vaguely useful stand-alone program which translates between
3058 * obfuscated and clear Mines game descriptions. Pass in a game
3059 * description on the command line, and if it's clear it will be
3060 * obfuscated and vice versa. The output text should also be a
3061 * valid game ID describing the same game. Like this:
3063 * $ ./mineobfusc 9x9:4,4,mb071b49fbd1cb6a0d5868
3064 * 9x9:4,4,004000007c00010022080
3065 * $ ./mineobfusc 9x9:4,4,004000007c00010022080
3066 * 9x9:4,4,mb071b49fbd1cb6a0d5868
3068 * gcc -DSTANDALONE_OBFUSCATOR -o mineobfusc mines.c malloc.c random.c tree234.c
3073 void frontend_default_colour(frontend *fe, float *output) {}
3074 void draw_text(frontend *fe, int x, int y, int fonttype, int fontsize,
3075 int align, int colour, char *text) {}
3076 void draw_rect(frontend *fe, int x, int y, int w, int h, int colour) {}
3077 void draw_line(frontend *fe, int x1, int y1, int x2, int y2, int colour) {}
3078 void draw_polygon(frontend *fe, int *coords, int npoints,
3079 int fill, int colour) {}
3080 void clip(frontend *fe, int x, int y, int w, int h) {}
3081 void unclip(frontend *fe) {}
3082 void start_draw(frontend *fe) {}
3083 void draw_update(frontend *fe, int x, int y, int w, int h) {}
3084 void end_draw(frontend *fe) {}
3085 void midend_supersede_game_desc(midend_data *me, char *desc) {}
3086 void status_bar(frontend *fe, char *text) {}
3088 void fatal(char *fmt, ...)
3092 fprintf(stderr, "fatal error: ");
3095 vfprintf(stderr, fmt, ap);
3098 fprintf(stderr, "\n");
3102 int main(int argc, char **argv)
3107 char *id = NULL, *desc, *err;
3111 while (--argc > 0) {
3114 fprintf(stderr, "%s: unrecognised option `%s'\n", argv[0]);
3122 fprintf(stderr, "usage: %s <game_id>\n", argv[0]);
3126 desc = strchr(id, ':');
3128 fprintf(stderr, "%s: game id expects a colon in it\n", argv[0]);
3133 p = default_params();
3134 decode_params(p, id);
3135 err = validate_desc(p, desc);
3137 fprintf(stderr, "%s: %s\n", argv[0], err);
3140 s = new_game(NULL, p, desc);
3143 while (*desc && *desc != ',') desc++;
3146 while (*desc && *desc != ',') desc++;
3149 printf("%s:%s\n", id, describe_layout(s->layout->mines,