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 * - delay game description generation until first click
14 * + do we actually _need_ to do this? Hmm.
15 * + it's a perfectly good puzzle game without
16 * + but it might be useful when we start timing, since it
17 * ensures the user is really paying attention.
21 * - question marks (arrgh, preferences?)
23 * - sensible parameter constraints
24 * + 30x16: 191 mines just about works if rather slowly, 192 is
25 * just about doom (the latter corresponding to a density of
27 * + 9x9: 45 mines works - over 1 in 2! 50 seems a bit slow.
28 * + it might not be feasible to work out the exact limit
43 COL_1
, COL_2
, COL_3
, COL_4
, COL_5
, COL_6
, COL_7
, COL_8
,
44 COL_MINE
, COL_BANG
, COL_CROSS
, COL_FLAG
, COL_FLAGBASE
, COL_QUERY
,
45 COL_HIGHLIGHT
, COL_LOWLIGHT
,
50 #define BORDER (TILE_SIZE * 3 / 2)
51 #define HIGHLIGHT_WIDTH 2
52 #define OUTER_HIGHLIGHT_WIDTH 3
53 #define COORD(x) ( (x) * TILE_SIZE + BORDER )
54 #define FROMCOORD(x) ( ((x) - BORDER + TILE_SIZE) / TILE_SIZE - 1 )
56 #define FLASH_FRAME 0.13F
65 * This structure is shared between all the game_states for a
66 * given instance of the puzzle, so we reference-count it.
71 * If we haven't yet actually generated the mine layout, here's
72 * all the data we will need to do so.
76 midend_data
*me
; /* to give back the new game desc */
80 int w
, h
, n
, dead
, won
;
81 struct mine_layout
*layout
; /* real mine positions */
82 char *grid
; /* player knowledge */
84 * Each item in the `grid' array is one of the following values:
86 * - 0 to 8 mean the square is open and has a surrounding mine
89 * - -1 means the square is marked as a mine.
91 * - -2 means the square is unknown.
93 * - -3 means the square is marked with a question mark
94 * (FIXME: do we even want to bother with this?).
96 * - 64 means the square has had a mine revealed when the game
99 * - 65 means the square had a mine revealed and this was the
100 * one the player hits.
102 * - 66 means the square has a crossed-out mine because the
103 * player had incorrectly marked it.
107 static game_params
*default_params(void)
109 game_params
*ret
= snew(game_params
);
118 static int game_fetch_preset(int i
, char **name
, game_params
**params
)
122 static const struct { int w
, h
, n
; } values
[] = {
128 if (i
< 0 || i
>= lenof(values
))
131 ret
= snew(game_params
);
132 ret
->w
= values
[i
].w
;
133 ret
->h
= values
[i
].h
;
134 ret
->n
= values
[i
].n
;
137 sprintf(str
, "%dx%d, %d mines", ret
->w
, ret
->h
, ret
->n
);
144 static void free_params(game_params
*params
)
149 static game_params
*dup_params(game_params
*params
)
151 game_params
*ret
= snew(game_params
);
152 *ret
= *params
; /* structure copy */
156 static void decode_params(game_params
*params
, char const *string
)
158 char const *p
= string
;
161 while (*p
&& isdigit((unsigned char)*p
)) p
++;
165 while (*p
&& isdigit((unsigned char)*p
)) p
++;
167 params
->h
= params
->w
;
172 while (*p
&& (*p
== '.' || isdigit((unsigned char)*p
))) p
++;
174 params
->n
= params
->w
* params
->h
/ 10;
180 params
->unique
= FALSE
;
182 p
++; /* skip any other gunk */
186 static char *encode_params(game_params
*params
, int full
)
191 len
= sprintf(ret
, "%dx%d", params
->w
, params
->h
);
193 * Mine count is a generation-time parameter, since it can be
194 * deduced from the mine bitmap!
197 len
+= sprintf(ret
+len
, "n%d", params
->n
);
198 if (full
&& !params
->unique
)
200 assert(len
< lenof(ret
));
206 static config_item
*game_configure(game_params
*params
)
211 ret
= snewn(5, config_item
);
213 ret
[0].name
= "Width";
214 ret
[0].type
= C_STRING
;
215 sprintf(buf
, "%d", params
->w
);
216 ret
[0].sval
= dupstr(buf
);
219 ret
[1].name
= "Height";
220 ret
[1].type
= C_STRING
;
221 sprintf(buf
, "%d", params
->h
);
222 ret
[1].sval
= dupstr(buf
);
225 ret
[2].name
= "Mines";
226 ret
[2].type
= C_STRING
;
227 sprintf(buf
, "%d", params
->n
);
228 ret
[2].sval
= dupstr(buf
);
231 ret
[3].name
= "Ensure solubility";
232 ret
[3].type
= C_BOOLEAN
;
234 ret
[3].ival
= params
->unique
;
244 static game_params
*custom_params(config_item
*cfg
)
246 game_params
*ret
= snew(game_params
);
248 ret
->w
= atoi(cfg
[0].sval
);
249 ret
->h
= atoi(cfg
[1].sval
);
250 ret
->n
= atoi(cfg
[2].sval
);
251 if (strchr(cfg
[2].sval
, '%'))
252 ret
->n
= ret
->n
* (ret
->w
* ret
->h
) / 100;
253 ret
->unique
= cfg
[3].ival
;
258 static char *validate_params(game_params
*params
)
260 if (params
->w
<= 0 && params
->h
<= 0)
261 return "Width and height must both be greater than zero";
263 return "Width must be greater than zero";
265 return "Height must be greater than zero";
268 * FIXME: Need more constraints here. Not sure what the
269 * sensible limits for Minesweeper actually are. The limits
270 * probably ought to change, however, depending on uniqueness.
276 /* ----------------------------------------------------------------------
277 * Minesweeper solver, used to ensure the generated grids are
278 * solvable without having to take risks.
282 * Count the bits in a word. Only needs to cope with 16 bits.
284 static int bitcount16(int word
)
286 word
= ((word
& 0xAAAA) >> 1) + (word
& 0x5555);
287 word
= ((word
& 0xCCCC) >> 2) + (word
& 0x3333);
288 word
= ((word
& 0xF0F0) >> 4) + (word
& 0x0F0F);
289 word
= ((word
& 0xFF00) >> 8) + (word
& 0x00FF);
295 * We use a tree234 to store a large number of small localised
296 * sets, each with a mine count. We also keep some of those sets
297 * linked together into a to-do list.
300 short x
, y
, mask
, mines
;
302 struct set
*prev
, *next
;
305 static int setcmp(void *av
, void *bv
)
307 struct set
*a
= (struct set
*)av
;
308 struct set
*b
= (struct set
*)bv
;
312 else if (a
->y
> b
->y
)
314 else if (a
->x
< b
->x
)
316 else if (a
->x
> b
->x
)
318 else if (a
->mask
< b
->mask
)
320 else if (a
->mask
> b
->mask
)
328 struct set
*todo_head
, *todo_tail
;
331 static struct setstore
*ss_new(void)
333 struct setstore
*ss
= snew(struct setstore
);
334 ss
->sets
= newtree234(setcmp
);
335 ss
->todo_head
= ss
->todo_tail
= NULL
;
340 * Take two input sets, in the form (x,y,mask). Munge the first by
341 * taking either its intersection with the second or its difference
342 * with the second. Return the new mask part of the first set.
344 static int setmunge(int x1
, int y1
, int mask1
, int x2
, int y2
, int mask2
,
348 * Adjust the second set so that it has the same x,y
349 * coordinates as the first.
351 if (abs(x2
-x1
) >= 3 || abs(y2
-y1
) >= 3) {
355 mask2
&= ~(4|32|256);
365 mask2
&= ~(64|128|256);
377 * Invert the second set if `diff' is set (we're after A &~ B
378 * rather than A & B).
384 * Now all that's left is a logical AND.
386 return mask1
& mask2
;
389 static void ss_add_todo(struct setstore
*ss
, struct set
*s
)
392 return; /* already on it */
394 #ifdef SOLVER_DIAGNOSTICS
395 printf("adding set on todo list: %d,%d %03x %d\n",
396 s
->x
, s
->y
, s
->mask
, s
->mines
);
399 s
->prev
= ss
->todo_tail
;
409 static void ss_add(struct setstore
*ss
, int x
, int y
, int mask
, int mines
)
416 * Normalise so that x and y are genuinely the bounding
419 while (!(mask
& (1|8|64)))
421 while (!(mask
& (1|2|4)))
425 * Create a set structure and add it to the tree.
427 s
= snew(struct set
);
433 if (add234(ss
->sets
, s
) != s
) {
435 * This set already existed! Free it and return.
442 * We've added a new set to the tree, so put it on the todo
448 static void ss_remove(struct setstore
*ss
, struct set
*s
)
450 struct set
*next
= s
->next
, *prev
= s
->prev
;
452 #ifdef SOLVER_DIAGNOSTICS
453 printf("removing set %d,%d %03x\n", s
->x
, s
->y
, s
->mask
);
456 * Remove s from the todo list.
460 else if (s
== ss
->todo_head
)
461 ss
->todo_head
= next
;
465 else if (s
== ss
->todo_tail
)
466 ss
->todo_tail
= prev
;
471 * Remove s from the tree.
476 * Destroy the actual set structure.
482 * Return a dynamically allocated list of all the sets which
483 * overlap a provided input set.
485 static struct set
**ss_overlap(struct setstore
*ss
, int x
, int y
, int mask
)
487 struct set
**ret
= NULL
;
488 int nret
= 0, retsize
= 0;
491 for (xx
= x
-3; xx
< x
+3; xx
++)
492 for (yy
= y
-3; yy
< y
+3; yy
++) {
497 * Find the first set with these top left coordinates.
503 if (findrelpos234(ss
->sets
, &stmp
, NULL
, REL234_GE
, &pos
)) {
504 while ((s
= index234(ss
->sets
, pos
)) != NULL
&&
505 s
->x
== xx
&& s
->y
== yy
) {
507 * This set potentially overlaps the input one.
508 * Compute the intersection to see if they
509 * really overlap, and add it to the list if
512 if (setmunge(x
, y
, mask
, s
->x
, s
->y
, s
->mask
, FALSE
)) {
514 * There's an overlap.
516 if (nret
>= retsize
) {
518 ret
= sresize(ret
, retsize
, struct set
*);
528 ret
= sresize(ret
, nret
+1, struct set
*);
535 * Get an element from the head of the set todo list.
537 static struct set
*ss_todo(struct setstore
*ss
)
540 struct set
*ret
= ss
->todo_head
;
541 ss
->todo_head
= ret
->next
;
543 ss
->todo_head
->prev
= NULL
;
545 ss
->todo_tail
= NULL
;
546 ret
->next
= ret
->prev
= NULL
;
559 static void std_add(struct squaretodo
*std
, int i
)
562 std
->next
[std
->tail
] = i
;
569 static void known_squares(int w
, int h
, struct squaretodo
*std
, char *grid
,
570 int (*open
)(void *ctx
, int x
, int y
), void *openctx
,
571 int x
, int y
, int mask
, int mine
)
577 for (yy
= 0; yy
< 3; yy
++)
578 for (xx
= 0; xx
< 3; xx
++) {
580 int i
= (y
+ yy
) * w
+ (x
+ xx
);
583 * It's possible that this square is _already_
584 * known, in which case we don't try to add it to
590 grid
[i
] = -1; /* and don't open it! */
592 grid
[i
] = open(openctx
, x
+ xx
, y
+ yy
);
593 assert(grid
[i
] != -1); /* *bang* */
604 * This is data returned from the `perturb' function. It details
605 * which squares have become mines and which have become clear. The
606 * solver is (of course) expected to honourably not use that
607 * knowledge directly, but to efficently adjust its internal data
608 * structures and proceed based on only the information it
611 struct perturbation
{
613 int delta
; /* +1 == become a mine; -1 == cleared */
615 struct perturbations
{
617 struct perturbation
*changes
;
621 * Main solver entry point. You give it a grid of existing
622 * knowledge (-1 for a square known to be a mine, 0-8 for empty
623 * squares with a given number of neighbours, -2 for completely
624 * unknown), plus a function which you can call to open new squares
625 * once you're confident of them. It fills in as much more of the
630 * - -1 means deduction stalled and nothing could be done
631 * - 0 means deduction succeeded fully
632 * - >0 means deduction succeeded but some number of perturbation
633 * steps were required; the exact return value is the number of
636 static int minesolve(int w
, int h
, int n
, char *grid
,
637 int (*open
)(void *ctx
, int x
, int y
),
638 struct perturbations
*(*perturb
)(void *ctx
, char *grid
,
639 int x
, int y
, int mask
),
640 void *ctx
, random_state
*rs
)
642 struct setstore
*ss
= ss_new();
644 struct squaretodo astd
, *std
= &astd
;
649 * Set up a linked list of squares with known contents, so that
650 * we can process them one by one.
652 std
->next
= snewn(w
*h
, int);
653 std
->head
= std
->tail
= -1;
656 * Initialise that list with all known squares in the input
659 for (y
= 0; y
< h
; y
++) {
660 for (x
= 0; x
< w
; x
++) {
668 * Main deductive loop.
671 int done_something
= FALSE
;
675 * If there are any known squares on the todo list, process
676 * them and construct a set for each.
678 while (std
->head
!= -1) {
680 #ifdef SOLVER_DIAGNOSTICS
681 printf("known square at %d,%d [%d]\n", i
%w
, i
/w
, grid
[i
]);
683 std
->head
= std
->next
[i
];
691 int dx
, dy
, mines
, bit
, val
;
692 #ifdef SOLVER_DIAGNOSTICS
693 printf("creating set around this square\n");
696 * Empty square. Construct the set of non-known squares
697 * around this one, and determine its mine count.
702 for (dy
= -1; dy
<= +1; dy
++) {
703 for (dx
= -1; dx
<= +1; dx
++) {
704 #ifdef SOLVER_DIAGNOSTICS
705 printf("grid %d,%d = %d\n", x
+dx
, y
+dy
, grid
[i
+dy
*w
+dx
]);
707 if (x
+dx
< 0 || x
+dx
>= w
|| y
+dy
< 0 || y
+dy
>= h
)
708 /* ignore this one */;
709 else if (grid
[i
+dy
*w
+dx
] == -1)
711 else if (grid
[i
+dy
*w
+dx
] == -2)
717 ss_add(ss
, x
-1, y
-1, val
, mines
);
721 * Now, whether the square is empty or full, we must
722 * find any set which contains it and replace it with
723 * one which does not.
726 #ifdef SOLVER_DIAGNOSTICS
727 printf("finding sets containing known square %d,%d\n", x
, y
);
729 list
= ss_overlap(ss
, x
, y
, 1);
731 for (j
= 0; list
[j
]; j
++) {
732 int newmask
, newmines
;
737 * Compute the mask for this set minus the
738 * newly known square.
740 newmask
= setmunge(s
->x
, s
->y
, s
->mask
, x
, y
, 1, TRUE
);
743 * Compute the new mine count.
745 newmines
= s
->mines
- (grid
[i
] == -1);
748 * Insert the new set into the collection,
749 * unless it's been whittled right down to
753 ss_add(ss
, s
->x
, s
->y
, newmask
, newmines
);
756 * Destroy the old one; it is actually obsolete.
765 * Marking a fresh square as known certainly counts as
768 done_something
= TRUE
;
772 * Now pick a set off the to-do list and attempt deductions
775 if ((s
= ss_todo(ss
)) != NULL
) {
777 #ifdef SOLVER_DIAGNOSTICS
778 printf("set to do: %d,%d %03x %d\n", s
->x
, s
->y
, s
->mask
, s
->mines
);
781 * Firstly, see if this set has a mine count of zero or
782 * of its own cardinality.
784 if (s
->mines
== 0 || s
->mines
== bitcount16(s
->mask
)) {
786 * If so, we can immediately mark all the squares
787 * in the set as known.
789 #ifdef SOLVER_DIAGNOSTICS
792 known_squares(w
, h
, std
, grid
, open
, ctx
,
793 s
->x
, s
->y
, s
->mask
, (s
->mines
!= 0));
796 * Having done that, we need do nothing further
797 * with this set; marking all the squares in it as
798 * known will eventually eliminate it, and will
799 * also permit further deductions about anything
806 * Failing that, we now search through all the sets
807 * which overlap this one.
809 list
= ss_overlap(ss
, s
->x
, s
->y
, s
->mask
);
811 for (j
= 0; list
[j
]; j
++) {
812 struct set
*s2
= list
[j
];
813 int swing
, s2wing
, swc
, s2wc
;
816 * Find the non-overlapping parts s2-s and s-s2,
817 * and their cardinalities.
819 * I'm going to refer to these parts as `wings'
820 * surrounding the central part common to both
821 * sets. The `s wing' is s-s2; the `s2 wing' is
824 swing
= setmunge(s
->x
, s
->y
, s
->mask
, s2
->x
, s2
->y
, s2
->mask
,
826 s2wing
= setmunge(s2
->x
, s2
->y
, s2
->mask
, s
->x
, s
->y
, s
->mask
,
828 swc
= bitcount16(swing
);
829 s2wc
= bitcount16(s2wing
);
832 * If one set has more mines than the other, and
833 * the number of extra mines is equal to the
834 * cardinality of that set's wing, then we can mark
835 * every square in the wing as a known mine, and
836 * every square in the other wing as known clear.
838 if (swc
== s
->mines
- s2
->mines
||
839 s2wc
== s2
->mines
- s
->mines
) {
840 known_squares(w
, h
, std
, grid
, open
, ctx
,
842 (swc
== s
->mines
- s2
->mines
));
843 known_squares(w
, h
, std
, grid
, open
, ctx
,
844 s2
->x
, s2
->y
, s2wing
,
845 (s2wc
== s2
->mines
- s
->mines
));
850 * Failing that, see if one set is a subset of the
851 * other. If so, we can divide up the mine count of
852 * the larger set between the smaller set and its
853 * complement, even if neither smaller set ends up
854 * being immediately clearable.
856 if (swc
== 0 && s2wc
!= 0) {
857 /* s is a subset of s2. */
858 assert(s2
->mines
> s
->mines
);
859 ss_add(ss
, s2
->x
, s2
->y
, s2wing
, s2
->mines
- s
->mines
);
860 } else if (s2wc
== 0 && swc
!= 0) {
861 /* s2 is a subset of s. */
862 assert(s
->mines
> s2
->mines
);
863 ss_add(ss
, s
->x
, s
->y
, swing
, s
->mines
- s2
->mines
);
870 * In this situation we have definitely done
871 * _something_, even if it's only reducing the size of
874 done_something
= TRUE
;
877 * We have nothing left on our todo list, which means
878 * all localised deductions have failed. Our next step
879 * is to resort to global deduction based on the total
880 * mine count. This is computationally expensive
881 * compared to any of the above deductions, which is
882 * why we only ever do it when all else fails, so that
883 * hopefully it won't have to happen too often.
885 * If you pass n<0 into this solver, that informs it
886 * that you do not know the total mine count, so it
887 * won't even attempt these deductions.
890 int minesleft
, squaresleft
;
891 int nsets
, setused
[10], cursor
;
894 * Start by scanning the current grid state to work out
895 * how many unknown squares we still have, and how many
896 * mines are to be placed in them.
900 for (i
= 0; i
< w
*h
; i
++) {
903 else if (grid
[i
] == -2)
907 #ifdef SOLVER_DIAGNOSTICS
908 printf("global deduction time: squaresleft=%d minesleft=%d\n",
909 squaresleft
, minesleft
);
910 for (y
= 0; y
< h
; y
++) {
911 for (x
= 0; x
< w
; x
++) {
927 * If there _are_ no unknown squares, we have actually
930 if (squaresleft
== 0) {
931 assert(minesleft
== 0);
936 * First really simple case: if there are no more mines
937 * left, or if there are exactly as many mines left as
938 * squares to play them in, then it's all easy.
940 if (minesleft
== 0 || minesleft
== squaresleft
) {
941 for (i
= 0; i
< w
*h
; i
++)
943 known_squares(w
, h
, std
, grid
, open
, ctx
,
944 i
% w
, i
/ w
, 1, minesleft
!= 0);
945 continue; /* now go back to main deductive loop */
949 * Failing that, we have to do some _real_ work.
950 * Ideally what we do here is to try every single
951 * combination of the currently available sets, in an
952 * attempt to find a disjoint union (i.e. a set of
953 * squares with a known mine count between them) such
954 * that the remaining unknown squares _not_ contained
955 * in that union either contain no mines or are all
958 * Actually enumerating all 2^n possibilities will get
959 * a bit slow for large n, so I artificially cap this
960 * recursion at n=10 to avoid too much pain.
962 nsets
= count234(ss
->sets
);
963 if (nsets
<= lenof(setused
)) {
965 * Doing this with actual recursive function calls
966 * would get fiddly because a load of local
967 * variables from this function would have to be
968 * passed down through the recursion. So instead
969 * I'm going to use a virtual recursion within this
970 * function. The way this works is:
972 * - we have an array `setused', such that
973 * setused[n] is 0 or 1 depending on whether set
974 * n is currently in the union we are
977 * - we have a value `cursor' which indicates how
978 * much of `setused' we have so far filled in.
979 * It's conceptually the recursion depth.
981 * We begin by setting `cursor' to zero. Then:
983 * - if cursor can advance, we advance it by one.
984 * We set the value in `setused' that it went
985 * past to 1 if that set is disjoint from
986 * anything else currently in `setused', or to 0
989 * - If cursor cannot advance because it has
990 * reached the end of the setused list, then we
991 * have a maximal disjoint union. Check to see
992 * whether its mine count has any useful
993 * properties. If so, mark all the squares not
994 * in the union as known and terminate.
996 * - If cursor has reached the end of setused and
997 * the algorithm _hasn't_ terminated, back
998 * cursor up to the nearest 1, turn it into a 0
999 * and advance cursor just past it.
1001 * - If we attempt to back up to the nearest 1 and
1002 * there isn't one at all, then we have gone
1003 * through all disjoint unions of sets in the
1004 * list and none of them has been helpful, so we
1007 struct set
*sets
[lenof(setused
)];
1008 for (i
= 0; i
< nsets
; i
++)
1009 sets
[i
] = index234(ss
->sets
, i
);
1014 if (cursor
< nsets
) {
1017 /* See if any existing set overlaps this one. */
1018 for (i
= 0; i
< cursor
; i
++)
1020 setmunge(sets
[cursor
]->x
,
1023 sets
[i
]->x
, sets
[i
]->y
, sets
[i
]->mask
,
1031 * We're adding this set to our union,
1032 * so adjust minesleft and squaresleft
1035 minesleft
-= sets
[cursor
]->mines
;
1036 squaresleft
-= bitcount16(sets
[cursor
]->mask
);
1039 setused
[cursor
++] = ok
;
1041 #ifdef SOLVER_DIAGNOSTICS
1042 printf("trying a set combination with %d %d\n",
1043 squaresleft
, minesleft
);
1044 #endif /* SOLVER_DIAGNOSTICS */
1047 * We've reached the end. See if we've got
1048 * anything interesting.
1050 if (squaresleft
> 0 &&
1051 (minesleft
== 0 || minesleft
== squaresleft
)) {
1053 * We have! There is at least one
1054 * square not contained within the set
1055 * union we've just found, and we can
1056 * deduce that either all such squares
1057 * are mines or all are not (depending
1058 * on whether minesleft==0). So now all
1059 * we have to do is actually go through
1060 * the grid, find those squares, and
1063 for (i
= 0; i
< w
*h
; i
++)
1064 if (grid
[i
] == -2) {
1068 for (j
= 0; j
< nsets
; j
++)
1070 setmunge(sets
[j
]->x
, sets
[j
]->y
,
1071 sets
[j
]->mask
, x
, y
, 1,
1077 known_squares(w
, h
, std
, grid
,
1079 x
, y
, 1, minesleft
!= 0);
1082 done_something
= TRUE
;
1083 break; /* return to main deductive loop */
1087 * If we reach here, then this union hasn't
1088 * done us any good, so move on to the
1089 * next. Backtrack cursor to the nearest 1,
1090 * change it to a 0 and continue.
1092 while (cursor
-- >= 0 && !setused
[cursor
]);
1094 assert(setused
[cursor
]);
1097 * We're removing this set from our
1098 * union, so re-increment minesleft and
1101 minesleft
+= sets
[cursor
]->mines
;
1102 squaresleft
+= bitcount16(sets
[cursor
]->mask
);
1104 setused
[cursor
++] = 0;
1107 * We've backtracked all the way to the
1108 * start without finding a single 1,
1109 * which means that our virtual
1110 * recursion is complete and nothing
1125 #ifdef SOLVER_DIAGNOSTICS
1127 * Dump the current known state of the grid.
1129 printf("solver ran out of steam, ret=%d, grid:\n", nperturbs
);
1130 for (y
= 0; y
< h
; y
++) {
1131 for (x
= 0; x
< w
; x
++) {
1132 int v
= grid
[y
*w
+x
];
1148 for (i
= 0; (s
= index234(ss
->sets
, i
)) != NULL
; i
++)
1149 printf("remaining set: %d,%d %03x %d\n", s
->x
, s
->y
, s
->mask
, s
->mines
);
1154 * Now we really are at our wits' end as far as solving
1155 * this grid goes. Our only remaining option is to call
1156 * a perturb function and ask it to modify the grid to
1160 struct perturbations
*ret
;
1166 * Choose a set at random from the current selection,
1167 * and ask the perturb function to either fill or empty
1170 * If we have no sets at all, we must give up.
1172 if (count234(ss
->sets
) == 0)
1174 s
= index234(ss
->sets
, random_upto(rs
, count234(ss
->sets
)));
1175 #ifdef SOLVER_DIAGNOSTICS
1176 printf("perturbing on set %d,%d %03x\n", s
->x
, s
->y
, s
->mask
);
1178 ret
= perturb(ctx
, grid
, s
->x
, s
->y
, s
->mask
);
1181 assert(ret
->n
> 0); /* otherwise should have been NULL */
1184 * A number of squares have been fiddled with, and
1185 * the returned structure tells us which. Adjust
1186 * the mine count in any set which overlaps one of
1187 * those squares, and put them back on the to-do
1190 for (i
= 0; i
< ret
->n
; i
++) {
1191 #ifdef SOLVER_DIAGNOSTICS
1192 printf("perturbation %s mine at %d,%d\n",
1193 ret
->changes
[i
].delta
> 0 ?
"added" : "removed",
1194 ret
->changes
[i
].x
, ret
->changes
[i
].y
);
1197 list
= ss_overlap(ss
,
1198 ret
->changes
[i
].x
, ret
->changes
[i
].y
, 1);
1200 for (j
= 0; list
[j
]; j
++) {
1201 list
[j
]->mines
+= ret
->changes
[i
].delta
;
1202 ss_add_todo(ss
, list
[j
]);
1209 * Now free the returned data.
1211 sfree(ret
->changes
);
1214 #ifdef SOLVER_DIAGNOSTICS
1216 * Dump the current known state of the grid.
1218 printf("state after perturbation:\n", nperturbs
);
1219 for (y
= 0; y
< h
; y
++) {
1220 for (x
= 0; x
< w
; x
++) {
1221 int v
= grid
[y
*w
+x
];
1237 for (i
= 0; (s
= index234(ss
->sets
, i
)) != NULL
; i
++)
1238 printf("remaining set: %d,%d %03x %d\n", s
->x
, s
->y
, s
->mask
, s
->mines
);
1243 * And now we can go back round the deductive loop.
1250 * If we get here, even that didn't work (either we didn't
1251 * have a perturb function or it returned failure), so we
1258 * See if we've got any unknown squares left.
1260 for (y
= 0; y
< h
; y
++)
1261 for (x
= 0; x
< w
; x
++)
1262 if (grid
[y
*w
+x
] == -2) {
1263 nperturbs
= -1; /* failed to complete */
1268 * Free the set list and square-todo list.
1272 while ((s
= delpos234(ss
->sets
, 0)) != NULL
)
1274 freetree234(ss
->sets
);
1282 /* ----------------------------------------------------------------------
1283 * Grid generator which uses the above solver.
1293 static int mineopen(void *vctx
, int x
, int y
)
1295 struct minectx
*ctx
= (struct minectx
*)vctx
;
1298 assert(x
>= 0 && x
< ctx
->w
&& y
>= 0 && y
< ctx
->h
);
1299 if (ctx
->grid
[y
* ctx
->w
+ x
])
1300 return -1; /* *bang* */
1303 for (i
= -1; i
<= +1; i
++) {
1304 if (x
+ i
< 0 || x
+ i
>= ctx
->w
)
1306 for (j
= -1; j
<= +1; j
++) {
1307 if (y
+ j
< 0 || y
+ j
>= ctx
->h
)
1309 if (i
== 0 && j
== 0)
1311 if (ctx
->grid
[(y
+j
) * ctx
->w
+ (x
+i
)])
1319 /* Structure used internally to mineperturb(). */
1321 int x
, y
, type
, random
;
1323 static int squarecmp(const void *av
, const void *bv
)
1325 const struct square
*a
= (const struct square
*)av
;
1326 const struct square
*b
= (const struct square
*)bv
;
1327 if (a
->type
< b
->type
)
1329 else if (a
->type
> b
->type
)
1331 else if (a
->random
< b
->random
)
1333 else if (a
->random
> b
->random
)
1335 else if (a
->y
< b
->y
)
1337 else if (a
->y
> b
->y
)
1339 else if (a
->x
< b
->x
)
1341 else if (a
->x
> b
->x
)
1346 static struct perturbations
*mineperturb(void *vctx
, char *grid
,
1347 int setx
, int sety
, int mask
)
1349 struct minectx
*ctx
= (struct minectx
*)vctx
;
1350 struct square
*sqlist
;
1351 int x
, y
, dx
, dy
, i
, n
, nfull
, nempty
;
1352 struct square
*tofill
[9], *toempty
[9], **todo
;
1353 int ntofill
, ntoempty
, ntodo
, dtodo
, dset
;
1354 struct perturbations
*ret
;
1357 * Make a list of all the squares in the grid which we can
1358 * possibly use. This list should be in preference order, which
1361 * - first, unknown squares on the boundary of known space
1362 * - next, unknown squares beyond that boundary
1363 * - as a very last resort, known squares, but not within one
1364 * square of the starting position.
1366 * Each of these sections needs to be shuffled independently.
1367 * We do this by preparing list of all squares and then sorting
1368 * it with a random secondary key.
1370 sqlist
= snewn(ctx
->w
* ctx
->h
, struct square
);
1372 for (y
= 0; y
< ctx
->h
; y
++)
1373 for (x
= 0; x
< ctx
->w
; x
++) {
1375 * If this square is too near the starting position,
1376 * don't put it on the list at all.
1378 if (abs(y
- ctx
->sy
) <= 1 && abs(x
- ctx
->sx
) <= 1)
1382 * If this square is in the input set, also don't put
1385 if (x
>= setx
&& x
< setx
+ 3 &&
1386 y
>= sety
&& y
< sety
+ 3 &&
1387 mask
& (1 << ((y
-sety
)*3+(x
-setx
))))
1393 if (grid
[y
*ctx
->w
+x
] != -2) {
1394 sqlist
[n
].type
= 3; /* known square */
1397 * Unknown square. Examine everything around it and
1398 * see if it borders on any known squares. If it
1399 * does, it's class 1, otherwise it's 2.
1404 for (dy
= -1; dy
<= +1; dy
++)
1405 for (dx
= -1; dx
<= +1; dx
++)
1406 if (x
+dx
>= 0 && x
+dx
< ctx
->w
&&
1407 y
+dy
>= 0 && y
+dy
< ctx
->h
&&
1408 grid
[(y
+dy
)*ctx
->w
+(x
+dx
)] != -2) {
1415 * Finally, a random number to cause qsort to
1416 * shuffle within each group.
1418 sqlist
[n
].random
= random_bits(ctx
->rs
, 31);
1423 qsort(sqlist
, n
, sizeof(struct square
), squarecmp
);
1426 * Now count up the number of full and empty squares in the set
1427 * we've been provided.
1430 for (dy
= 0; dy
< 3; dy
++)
1431 for (dx
= 0; dx
< 3; dx
++)
1432 if (mask
& (1 << (dy
*3+dx
))) {
1433 assert(setx
+dx
<= ctx
->w
);
1434 assert(sety
+dy
<= ctx
->h
);
1435 if (ctx
->grid
[(sety
+dy
)*ctx
->w
+(setx
+dx
)])
1442 * Now go through our sorted list until we find either `nfull'
1443 * empty squares, or `nempty' full squares; these will be
1444 * swapped with the appropriate squares in the set to either
1445 * fill or empty the set while keeping the same number of mines
1448 ntofill
= ntoempty
= 0;
1449 for (i
= 0; i
< n
; i
++) {
1450 struct square
*sq
= &sqlist
[i
];
1451 if (ctx
->grid
[sq
->y
* ctx
->w
+ sq
->x
])
1452 toempty
[ntoempty
++] = sq
;
1454 tofill
[ntofill
++] = sq
;
1455 if (ntofill
== nfull
|| ntoempty
== nempty
)
1460 * If this didn't work at all, I think we just give up.
1462 if (ntofill
!= nfull
&& ntoempty
!= nempty
) {
1468 * Now we're pretty much there. We need to either
1469 * (a) put a mine in each of the empty squares in the set, and
1470 * take one out of each square in `toempty'
1471 * (b) take a mine out of each of the full squares in the set,
1472 * and put one in each square in `tofill'
1473 * depending on which one we've found enough squares to do.
1475 * So we start by constructing our list of changes to return to
1476 * the solver, so that it can update its data structures
1477 * efficiently rather than having to rescan the whole grid.
1479 ret
= snew(struct perturbations
);
1480 if (ntofill
== nfull
) {
1492 ret
->changes
= snewn(ret
->n
, struct perturbation
);
1493 for (i
= 0; i
< ntodo
; i
++) {
1494 ret
->changes
[i
].x
= todo
[i
]->x
;
1495 ret
->changes
[i
].y
= todo
[i
]->y
;
1496 ret
->changes
[i
].delta
= dtodo
;
1498 /* now i == ntodo */
1499 for (dy
= 0; dy
< 3; dy
++)
1500 for (dx
= 0; dx
< 3; dx
++)
1501 if (mask
& (1 << (dy
*3+dx
))) {
1502 int currval
= (ctx
->grid
[(sety
+dy
)*ctx
->w
+(setx
+dx
)] ?
+1 : -1);
1503 if (dset
== -currval
) {
1504 ret
->changes
[i
].x
= setx
+ dx
;
1505 ret
->changes
[i
].y
= sety
+ dy
;
1506 ret
->changes
[i
].delta
= dset
;
1510 assert(i
== ret
->n
);
1515 * Having set up the precise list of changes we're going to
1516 * make, we now simply make them and return.
1518 for (i
= 0; i
< ret
->n
; i
++) {
1521 x
= ret
->changes
[i
].x
;
1522 y
= ret
->changes
[i
].y
;
1523 delta
= ret
->changes
[i
].delta
;
1526 * Check we're not trying to add an existing mine or remove
1529 assert((delta
< 0) ^ (ctx
->grid
[y
*ctx
->w
+x
] == 0));
1532 * Actually make the change.
1534 ctx
->grid
[y
*ctx
->w
+x
] = (delta
> 0);
1537 * Update any numbers already present in the grid.
1539 for (dy
= -1; dy
<= +1; dy
++)
1540 for (dx
= -1; dx
<= +1; dx
++)
1541 if (x
+dx
>= 0 && x
+dx
< ctx
->w
&&
1542 y
+dy
>= 0 && y
+dy
< ctx
->h
&&
1543 grid
[(y
+dy
)*ctx
->w
+(x
+dx
)] != -2) {
1544 if (dx
== 0 && dy
== 0) {
1546 * The square itself is marked as known in
1547 * the grid. Mark it as a mine if it's a
1548 * mine, or else work out its number.
1551 grid
[y
*ctx
->w
+x
] = -1;
1553 int dx2
, dy2
, minecount
= 0;
1554 for (dy2
= -1; dy2
<= +1; dy2
++)
1555 for (dx2
= -1; dx2
<= +1; dx2
++)
1556 if (x
+dx2
>= 0 && x
+dx2
< ctx
->w
&&
1557 y
+dy2
>= 0 && y
+dy2
< ctx
->h
&&
1558 ctx
->grid
[(y
+dy2
)*ctx
->w
+(x
+dx2
)])
1560 grid
[y
*ctx
->w
+x
] = minecount
;
1563 if (grid
[(y
+dy
)*ctx
->w
+(x
+dx
)] >= 0)
1564 grid
[(y
+dy
)*ctx
->w
+(x
+dx
)] += delta
;
1569 #ifdef GENERATION_DIAGNOSTICS
1572 printf("grid after perturbing:\n");
1573 for (yy
= 0; yy
< ctx
->h
; yy
++) {
1574 for (xx
= 0; xx
< ctx
->w
; xx
++) {
1575 int v
= ctx
->grid
[yy
*ctx
->w
+xx
];
1576 if (yy
== ctx
->sy
&& xx
== ctx
->sx
) {
1594 static char *minegen(int w
, int h
, int n
, int x
, int y
, int unique
,
1597 char *ret
= snewn(w
*h
, char);
1603 memset(ret
, 0, w
*h
);
1606 * Start by placing n mines, none of which is at x,y or within
1610 int *tmp
= snewn(w
*h
, int);
1614 * Write down the list of possible mine locations.
1617 for (i
= 0; i
< h
; i
++)
1618 for (j
= 0; j
< w
; j
++)
1619 if (abs(i
- y
) > 1 || abs(j
- x
) > 1)
1623 * Now pick n off the list at random.
1627 i
= random_upto(rs
, k
);
1635 #ifdef GENERATION_DIAGNOSTICS
1638 printf("grid after initial generation:\n");
1639 for (yy
= 0; yy
< h
; yy
++) {
1640 for (xx
= 0; xx
< w
; xx
++) {
1641 int v
= ret
[yy
*w
+xx
];
1642 if (yy
== y
&& xx
== x
) {
1658 * Now set up a results grid to run the solver in, and a
1659 * context for the solver to open squares. Then run the solver
1660 * repeatedly; if the number of perturb steps ever goes up or
1661 * it ever returns -1, give up completely.
1663 * We bypass this bit if we're not after a unique grid.
1666 char *solvegrid
= snewn(w
*h
, char);
1667 struct minectx actx
, *ctx
= &actx
;
1668 int solveret
, prevret
= -2;
1678 memset(solvegrid
, -2, w
*h
);
1679 solvegrid
[y
*w
+x
] = mineopen(ctx
, x
, y
);
1680 assert(solvegrid
[y
*w
+x
] == 0); /* by deliberate arrangement */
1683 minesolve(w
, h
, n
, solvegrid
, mineopen
, mineperturb
, ctx
, rs
);
1684 if (solveret
< 0 || (prevret
>= 0 && solveret
>= prevret
)) {
1687 } else if (solveret
== 0) {
1704 * The Mines game descriptions contain the location of every mine,
1705 * and can therefore be used to cheat.
1707 * It would be pointless to attempt to _prevent_ this form of
1708 * cheating by encrypting the description, since Mines is
1709 * open-source so anyone can find out the encryption key. However,
1710 * I think it is worth doing a bit of gentle obfuscation to prevent
1711 * _accidental_ spoilers: if you happened to note that the game ID
1712 * starts with an F, for example, you might be unable to put the
1713 * knowledge of those mines out of your mind while playing. So,
1714 * just as discussions of film endings are rot13ed to avoid
1715 * spoiling it for people who don't want to be told, we apply a
1716 * keyless, reversible, but visually completely obfuscatory masking
1717 * function to the mine bitmap.
1719 static void obfuscate_bitmap(unsigned char *bmp
, int bits
, int decode
)
1721 int bytes
, firsthalf
, secondhalf
;
1723 unsigned char *seedstart
;
1725 unsigned char *targetstart
;
1731 * My obfuscation algorithm is similar in concept to the OAEP
1732 * encoding used in some forms of RSA. Here's a specification
1735 * + We have a `masking function' which constructs a stream of
1736 * pseudorandom bytes from a seed of some number of input
1739 * + We pad out our input bit stream to a whole number of
1740 * bytes by adding up to 7 zero bits on the end. (In fact
1741 * the bitmap passed as input to this function will already
1742 * have had this done in practice.)
1744 * + We divide the _byte_ stream exactly in half, rounding the
1745 * half-way position _down_. So an 81-bit input string, for
1746 * example, rounds up to 88 bits or 11 bytes, and then
1747 * dividing by two gives 5 bytes in the first half and 6 in
1750 * + We generate a mask from the second half of the bytes, and
1751 * XOR it over the first half.
1753 * + We generate a mask from the (encoded) first half of the
1754 * bytes, and XOR it over the second half. Any null bits at
1755 * the end which were added as padding are cleared back to
1756 * zero even if this operation would have made them nonzero.
1758 * To de-obfuscate, the steps are precisely the same except
1759 * that the final two are reversed.
1761 * Finally, our masking function. Given an input seed string of
1762 * bytes, the output mask consists of concatenating the SHA-1
1763 * hashes of the seed string and successive decimal integers,
1767 bytes
= (bits
+ 7) / 8;
1768 firsthalf
= bytes
/ 2;
1769 secondhalf
= bytes
- firsthalf
;
1771 steps
[decode ?
1 : 0].seedstart
= bmp
+ firsthalf
;
1772 steps
[decode ?
1 : 0].seedlen
= secondhalf
;
1773 steps
[decode ?
1 : 0].targetstart
= bmp
;
1774 steps
[decode ?
1 : 0].targetlen
= firsthalf
;
1776 steps
[decode ?
0 : 1].seedstart
= bmp
;
1777 steps
[decode ?
0 : 1].seedlen
= firsthalf
;
1778 steps
[decode ?
0 : 1].targetstart
= bmp
+ firsthalf
;
1779 steps
[decode ?
0 : 1].targetlen
= secondhalf
;
1781 for (i
= 0; i
< 2; i
++) {
1782 SHA_State base
, final
;
1783 unsigned char digest
[20];
1785 int digestpos
= 20, counter
= 0;
1788 SHA_Bytes(&base
, steps
[i
].seedstart
, steps
[i
].seedlen
);
1790 for (j
= 0; j
< steps
[i
].targetlen
; j
++) {
1791 if (digestpos
>= 20) {
1792 sprintf(numberbuf
, "%d", counter
++);
1794 SHA_Bytes(&final
, numberbuf
, strlen(numberbuf
));
1795 SHA_Final(&final
, digest
);
1798 steps
[i
].targetstart
[j
] ^= digest
[digestpos
]++;
1802 * Mask off the pad bits in the final byte after both steps.
1805 bmp
[bits
/ 8] &= 0xFF & (0xFF00 >> (bits
% 8));
1809 static char *new_mine_layout(int w
, int h
, int n
, int x
, int y
, int unique
,
1810 random_state
*rs
, char **game_desc
)
1812 char *grid
, *ret
, *p
;
1816 grid
= minegen(w
, h
, n
, x
, y
, unique
, rs
);
1820 * Set up the mine bitmap and obfuscate it.
1823 bmp
= snewn((area
+ 7) / 8, unsigned char);
1824 memset(bmp
, 0, (area
+ 7) / 8);
1825 for (i
= 0; i
< area
; i
++) {
1827 bmp
[i
/ 8] |= 0x80 >> (i
% 8);
1829 obfuscate_bitmap(bmp
, area
, FALSE
);
1832 * Now encode the resulting bitmap in hex. We can work to
1833 * nibble rather than byte granularity, since the obfuscation
1834 * function guarantees to return a bit string of the same
1835 * length as its input.
1837 ret
= snewn((area
+3)/4 + 100, char);
1838 p
= ret
+ sprintf(ret
, "%d,%d,m", x
, y
); /* 'm' == masked */
1839 for (i
= 0; i
< (area
+3)/4; i
++) {
1843 *p
++ = "0123456789abcdef"[v
& 0xF];
1855 static char *new_game_desc(game_params
*params
, random_state
*rs
,
1856 game_aux_info
**aux
)
1859 int x
= random_upto(rs
, params
->w
);
1860 int y
= random_upto(rs
, params
->h
);
1863 grid
= new_mine_layout(params
->w
, params
->h
, params
->n
,
1864 x
, y
, params
->unique
, rs
);
1866 char *rsdesc
, *desc
;
1868 rsdesc
= random_state_encode(rs
);
1869 desc
= snewn(strlen(rsdesc
) + 100, char);
1870 sprintf(desc
, "r%d,%c,%s", params
->n
, params
->unique ?
'u' : 'a', rsdesc
);
1876 static void game_free_aux_info(game_aux_info
*aux
)
1878 assert(!"Shouldn't happen");
1881 static char *validate_desc(game_params
*params
, char *desc
)
1883 int wh
= params
->w
* params
->h
;
1887 if (!*desc
|| !isdigit((unsigned char)*desc
))
1888 return "No initial mine count in game description";
1889 while (*desc
&& isdigit((unsigned char)*desc
))
1890 desc
++; /* skip over mine count */
1892 return "No ',' after initial x-coordinate in game description";
1894 if (*desc
!= 'u' && *desc
!= 'a')
1895 return "No uniqueness specifier in game description";
1898 return "No ',' after uniqueness specifier in game description";
1899 /* now ignore the rest */
1901 if (!*desc
|| !isdigit((unsigned char)*desc
))
1902 return "No initial x-coordinate in game description";
1904 if (x
< 0 || x
>= params
->w
)
1905 return "Initial x-coordinate was out of range";
1906 while (*desc
&& isdigit((unsigned char)*desc
))
1907 desc
++; /* skip over x coordinate */
1909 return "No ',' after initial x-coordinate in game description";
1910 desc
++; /* eat comma */
1911 if (!*desc
|| !isdigit((unsigned char)*desc
))
1912 return "No initial y-coordinate in game description";
1914 if (y
< 0 || y
>= params
->h
)
1915 return "Initial y-coordinate was out of range";
1916 while (*desc
&& isdigit((unsigned char)*desc
))
1917 desc
++; /* skip over y coordinate */
1919 return "No ',' after initial y-coordinate in game description";
1920 desc
++; /* eat comma */
1921 /* eat `m', meaning `masked', if present */
1924 /* now just check length of remainder */
1925 if (strlen(desc
) != (wh
+3)/4)
1926 return "Game description is wrong length";
1932 static int open_square(game_state
*state
, int x
, int y
)
1934 int w
= state
->w
, h
= state
->h
;
1935 int xx
, yy
, nmines
, ncovered
;
1937 if (!state
->layout
->mines
) {
1939 * We have a preliminary game in which the mine layout
1940 * hasn't been generated yet. Generate it based on the
1941 * initial click location.
1944 state
->layout
->mines
= new_mine_layout(w
, h
, state
->layout
->n
,
1945 x
, y
, state
->layout
->unique
,
1948 midend_supersede_game_desc(state
->layout
->me
, desc
);
1950 random_free(state
->layout
->rs
);
1951 state
->layout
->rs
= NULL
;
1954 if (state
->layout
->mines
[y
*w
+x
]) {
1956 * The player has landed on a mine. Bad luck. Expose all
1960 for (yy
= 0; yy
< h
; yy
++)
1961 for (xx
= 0; xx
< w
; xx
++) {
1962 if (state
->layout
->mines
[yy
*w
+xx
] &&
1963 (state
->grid
[yy
*w
+xx
] == -2 ||
1964 state
->grid
[yy
*w
+xx
] == -3)) {
1965 state
->grid
[yy
*w
+xx
] = 64;
1967 if (!state
->layout
->mines
[yy
*w
+xx
] &&
1968 state
->grid
[yy
*w
+xx
] == -1) {
1969 state
->grid
[yy
*w
+xx
] = 66;
1972 state
->grid
[y
*w
+x
] = 65;
1977 * Otherwise, the player has opened a safe square. Mark it to-do.
1979 state
->grid
[y
*w
+x
] = -10; /* `todo' value internal to this func */
1982 * Now go through the grid finding all `todo' values and
1983 * opening them. Every time one of them turns out to have no
1984 * neighbouring mines, we add all its unopened neighbours to
1987 * FIXME: We really ought to be able to do this better than
1988 * using repeated N^2 scans of the grid.
1991 int done_something
= FALSE
;
1993 for (yy
= 0; yy
< h
; yy
++)
1994 for (xx
= 0; xx
< w
; xx
++)
1995 if (state
->grid
[yy
*w
+xx
] == -10) {
1998 assert(!state
->layout
->mines
[yy
*w
+xx
]);
2002 for (dx
= -1; dx
<= +1; dx
++)
2003 for (dy
= -1; dy
<= +1; dy
++)
2004 if (xx
+dx
>= 0 && xx
+dx
< state
->w
&&
2005 yy
+dy
>= 0 && yy
+dy
< state
->h
&&
2006 state
->layout
->mines
[(yy
+dy
)*w
+(xx
+dx
)])
2009 state
->grid
[yy
*w
+xx
] = v
;
2012 for (dx
= -1; dx
<= +1; dx
++)
2013 for (dy
= -1; dy
<= +1; dy
++)
2014 if (xx
+dx
>= 0 && xx
+dx
< state
->w
&&
2015 yy
+dy
>= 0 && yy
+dy
< state
->h
&&
2016 state
->grid
[(yy
+dy
)*w
+(xx
+dx
)] == -2)
2017 state
->grid
[(yy
+dy
)*w
+(xx
+dx
)] = -10;
2020 done_something
= TRUE
;
2023 if (!done_something
)
2028 * Finally, scan the grid and see if exactly as many squares
2029 * are still covered as there are mines. If so, set the `won'
2030 * flag and fill in mine markers on all covered squares.
2032 nmines
= ncovered
= 0;
2033 for (yy
= 0; yy
< h
; yy
++)
2034 for (xx
= 0; xx
< w
; xx
++) {
2035 if (state
->grid
[yy
*w
+xx
] < 0)
2037 if (state
->layout
->mines
[yy
*w
+xx
])
2040 assert(ncovered
>= nmines
);
2041 if (ncovered
== nmines
) {
2042 for (yy
= 0; yy
< h
; yy
++)
2043 for (xx
= 0; xx
< w
; xx
++) {
2044 if (state
->grid
[yy
*w
+xx
] < 0)
2045 state
->grid
[yy
*w
+xx
] = -1;
2053 static game_state
*new_game(midend_data
*me
, game_params
*params
, char *desc
)
2055 game_state
*state
= snew(game_state
);
2056 int i
, wh
, x
, y
, ret
, masked
;
2059 state
->w
= params
->w
;
2060 state
->h
= params
->h
;
2061 state
->n
= params
->n
;
2062 state
->dead
= state
->won
= FALSE
;
2064 wh
= state
->w
* state
->h
;
2066 state
->layout
= snew(struct mine_layout
);
2067 state
->layout
->refcount
= 1;
2069 state
->grid
= snewn(wh
, char);
2070 memset(state
->grid
, -2, wh
);
2074 state
->layout
->n
= atoi(desc
);
2075 while (*desc
&& isdigit((unsigned char)*desc
))
2076 desc
++; /* skip over mine count */
2077 if (*desc
) desc
++; /* eat comma */
2079 state
->layout
->unique
= FALSE
;
2081 state
->layout
->unique
= TRUE
;
2083 if (*desc
) desc
++; /* eat comma */
2085 state
->layout
->mines
= NULL
;
2086 state
->layout
->rs
= random_state_decode(desc
);
2087 state
->layout
->me
= me
;
2091 state
->layout
->mines
= snewn(wh
, char);
2093 while (*desc
&& isdigit((unsigned char)*desc
))
2094 desc
++; /* skip over x coordinate */
2095 if (*desc
) desc
++; /* eat comma */
2097 while (*desc
&& isdigit((unsigned char)*desc
))
2098 desc
++; /* skip over y coordinate */
2099 if (*desc
) desc
++; /* eat comma */
2106 * We permit game IDs to be entered by hand without the
2107 * masking transformation.
2112 bmp
= snewn((wh
+ 7) / 8, unsigned char);
2113 memset(bmp
, 0, (wh
+ 7) / 8);
2114 for (i
= 0; i
< (wh
+3)/4; i
++) {
2118 assert(c
!= 0); /* validate_desc should have caught */
2119 if (c
>= '0' && c
<= '9')
2121 else if (c
>= 'a' && c
<= 'f')
2123 else if (c
>= 'A' && c
<= 'F')
2128 bmp
[i
/ 2] |= v
<< (4 * (1 - (i
% 2)));
2132 obfuscate_bitmap(bmp
, wh
, TRUE
);
2134 memset(state
->layout
->mines
, 0, wh
);
2135 for (i
= 0; i
< wh
; i
++) {
2136 if (bmp
[i
/ 8] & (0x80 >> (i
% 8)))
2137 state
->layout
->mines
[i
] = 1;
2140 ret
= open_square(state
, x
, y
);
2146 static game_state
*dup_game(game_state
*state
)
2148 game_state
*ret
= snew(game_state
);
2153 ret
->dead
= state
->dead
;
2154 ret
->won
= state
->won
;
2155 ret
->layout
= state
->layout
;
2156 ret
->layout
->refcount
++;
2157 ret
->grid
= snewn(ret
->w
* ret
->h
, char);
2158 memcpy(ret
->grid
, state
->grid
, ret
->w
* ret
->h
);
2163 static void free_game(game_state
*state
)
2165 if (--state
->layout
->refcount
<= 0) {
2166 sfree(state
->layout
->mines
);
2167 if (state
->layout
->rs
)
2168 random_free(state
->layout
->rs
);
2169 sfree(state
->layout
);
2175 static game_state
*solve_game(game_state
*state
, game_aux_info
*aux
,
2181 static char *game_text_format(game_state
*state
)
2187 int hx
, hy
, hradius
; /* for mouse-down highlights */
2191 static game_ui
*new_ui(game_state
*state
)
2193 game_ui
*ui
= snew(game_ui
);
2194 ui
->hx
= ui
->hy
= -1;
2196 ui
->flash_is_death
= FALSE
; /* *shrug* */
2200 static void free_ui(game_ui
*ui
)
2205 static game_state
*make_move(game_state
*from
, game_ui
*ui
, int x
, int y
,
2211 if (from
->dead
|| from
->won
)
2212 return NULL
; /* no further moves permitted */
2214 if (!IS_MOUSE_DOWN(button
) && !IS_MOUSE_DRAG(button
) &&
2215 !IS_MOUSE_RELEASE(button
))
2220 if (cx
< 0 || cx
>= from
->w
|| cy
< 0 || cy
> from
->h
)
2223 if (button
== LEFT_BUTTON
|| button
== LEFT_DRAG
) {
2225 * Mouse-downs and mouse-drags just cause highlighting
2230 ui
->hradius
= (from
->grid
[cy
*from
->w
+cx
] >= 0 ?
1 : 0);
2234 if (button
== RIGHT_BUTTON
) {
2236 * Right-clicking only works on a covered square, and it
2237 * toggles between -1 (marked as mine) and -2 (not marked
2240 * FIXME: question marks.
2242 if (from
->grid
[cy
* from
->w
+ cx
] != -2 &&
2243 from
->grid
[cy
* from
->w
+ cx
] != -1)
2246 ret
= dup_game(from
);
2247 ret
->grid
[cy
* from
->w
+ cx
] ^= (-2 ^ -1);
2252 if (button
== LEFT_RELEASE
) {
2253 ui
->hx
= ui
->hy
= -1;
2257 * At this stage we must never return NULL: we have adjusted
2258 * the ui, so at worst we return `from'.
2262 * Left-clicking on a covered square opens a tile. Not
2263 * permitted if the tile is marked as a mine, for safety.
2264 * (Unmark it and _then_ open it.)
2266 if (from
->grid
[cy
* from
->w
+ cx
] == -2 ||
2267 from
->grid
[cy
* from
->w
+ cx
] == -3) {
2268 ret
= dup_game(from
);
2269 open_square(ret
, cx
, cy
);
2274 * Left-clicking on an uncovered tile: first we check to see if
2275 * the number of mine markers surrounding the tile is equal to
2276 * its mine count, and if so then we open all other surrounding
2279 if (from
->grid
[cy
* from
->w
+ cx
] > 0) {
2282 /* Count mine markers. */
2284 for (dy
= -1; dy
<= +1; dy
++)
2285 for (dx
= -1; dx
<= +1; dx
++)
2286 if (cx
+dx
>= 0 && cx
+dx
< from
->w
&&
2287 cy
+dy
>= 0 && cy
+dy
< from
->h
) {
2288 if (from
->grid
[(cy
+dy
)*from
->w
+(cx
+dx
)] == -1)
2292 if (n
== from
->grid
[cy
* from
->w
+ cx
]) {
2293 ret
= dup_game(from
);
2294 for (dy
= -1; dy
<= +1; dy
++)
2295 for (dx
= -1; dx
<= +1; dx
++)
2296 if (cx
+dx
>= 0 && cx
+dx
< ret
->w
&&
2297 cy
+dy
>= 0 && cy
+dy
< ret
->h
&&
2298 (ret
->grid
[(cy
+dy
)*ret
->w
+(cx
+dx
)] == -2 ||
2299 ret
->grid
[(cy
+dy
)*ret
->w
+(cx
+dx
)] == -3))
2300 open_square(ret
, cx
+dx
, cy
+dy
);
2311 /* ----------------------------------------------------------------------
2315 struct game_drawstate
{
2319 * Items in this `grid' array have all the same values as in
2320 * the game_state grid, and in addition:
2322 * - -10 means the tile was drawn `specially' as a result of a
2323 * flash, so it will always need redrawing.
2325 * - -22 and -23 mean the tile is highlighted for a possible
2330 static void game_size(game_params
*params
, int *x
, int *y
)
2332 *x
= BORDER
* 2 + TILE_SIZE
* params
->w
;
2333 *y
= BORDER
* 2 + TILE_SIZE
* params
->h
;
2336 static float *game_colours(frontend
*fe
, game_state
*state
, int *ncolours
)
2338 float *ret
= snewn(3 * NCOLOURS
, float);
2340 frontend_default_colour(fe
, &ret
[COL_BACKGROUND
* 3]);
2342 ret
[COL_1
* 3 + 0] = 0.0F
;
2343 ret
[COL_1
* 3 + 1] = 0.0F
;
2344 ret
[COL_1
* 3 + 2] = 1.0F
;
2346 ret
[COL_2
* 3 + 0] = 0.0F
;
2347 ret
[COL_2
* 3 + 1] = 0.5F
;
2348 ret
[COL_2
* 3 + 2] = 0.0F
;
2350 ret
[COL_3
* 3 + 0] = 1.0F
;
2351 ret
[COL_3
* 3 + 1] = 0.0F
;
2352 ret
[COL_3
* 3 + 2] = 0.0F
;
2354 ret
[COL_4
* 3 + 0] = 0.0F
;
2355 ret
[COL_4
* 3 + 1] = 0.0F
;
2356 ret
[COL_4
* 3 + 2] = 0.5F
;
2358 ret
[COL_5
* 3 + 0] = 0.5F
;
2359 ret
[COL_5
* 3 + 1] = 0.0F
;
2360 ret
[COL_5
* 3 + 2] = 0.0F
;
2362 ret
[COL_6
* 3 + 0] = 0.0F
;
2363 ret
[COL_6
* 3 + 1] = 0.5F
;
2364 ret
[COL_6
* 3 + 2] = 0.5F
;
2366 ret
[COL_7
* 3 + 0] = 0.0F
;
2367 ret
[COL_7
* 3 + 1] = 0.0F
;
2368 ret
[COL_7
* 3 + 2] = 0.0F
;
2370 ret
[COL_8
* 3 + 0] = 0.5F
;
2371 ret
[COL_8
* 3 + 1] = 0.5F
;
2372 ret
[COL_8
* 3 + 2] = 0.5F
;
2374 ret
[COL_MINE
* 3 + 0] = 0.0F
;
2375 ret
[COL_MINE
* 3 + 1] = 0.0F
;
2376 ret
[COL_MINE
* 3 + 2] = 0.0F
;
2378 ret
[COL_BANG
* 3 + 0] = 1.0F
;
2379 ret
[COL_BANG
* 3 + 1] = 0.0F
;
2380 ret
[COL_BANG
* 3 + 2] = 0.0F
;
2382 ret
[COL_CROSS
* 3 + 0] = 1.0F
;
2383 ret
[COL_CROSS
* 3 + 1] = 0.0F
;
2384 ret
[COL_CROSS
* 3 + 2] = 0.0F
;
2386 ret
[COL_FLAG
* 3 + 0] = 1.0F
;
2387 ret
[COL_FLAG
* 3 + 1] = 0.0F
;
2388 ret
[COL_FLAG
* 3 + 2] = 0.0F
;
2390 ret
[COL_FLAGBASE
* 3 + 0] = 0.0F
;
2391 ret
[COL_FLAGBASE
* 3 + 1] = 0.0F
;
2392 ret
[COL_FLAGBASE
* 3 + 2] = 0.0F
;
2394 ret
[COL_QUERY
* 3 + 0] = 0.0F
;
2395 ret
[COL_QUERY
* 3 + 1] = 0.0F
;
2396 ret
[COL_QUERY
* 3 + 2] = 0.0F
;
2398 ret
[COL_HIGHLIGHT
* 3 + 0] = 1.0F
;
2399 ret
[COL_HIGHLIGHT
* 3 + 1] = 1.0F
;
2400 ret
[COL_HIGHLIGHT
* 3 + 2] = 1.0F
;
2402 ret
[COL_LOWLIGHT
* 3 + 0] = ret
[COL_BACKGROUND
* 3 + 0] * 2.0 / 3.0;
2403 ret
[COL_LOWLIGHT
* 3 + 1] = ret
[COL_BACKGROUND
* 3 + 1] * 2.0 / 3.0;
2404 ret
[COL_LOWLIGHT
* 3 + 2] = ret
[COL_BACKGROUND
* 3 + 2] * 2.0 / 3.0;
2406 *ncolours
= NCOLOURS
;
2410 static game_drawstate
*game_new_drawstate(game_state
*state
)
2412 struct game_drawstate
*ds
= snew(struct game_drawstate
);
2416 ds
->started
= FALSE
;
2417 ds
->grid
= snewn(ds
->w
* ds
->h
, char);
2419 memset(ds
->grid
, -99, ds
->w
* ds
->h
);
2424 static void game_free_drawstate(game_drawstate
*ds
)
2430 static void draw_tile(frontend
*fe
, int x
, int y
, int v
, int bg
)
2436 if (v
== -22 || v
== -23) {
2440 * Omit the highlights in this case.
2442 draw_rect(fe
, x
, y
, TILE_SIZE
, TILE_SIZE
, bg
);
2443 draw_line(fe
, x
, y
, x
+ TILE_SIZE
- 1, y
, COL_LOWLIGHT
);
2444 draw_line(fe
, x
, y
, x
, y
+ TILE_SIZE
- 1, COL_LOWLIGHT
);
2447 * Draw highlights to indicate the square is covered.
2449 coords
[0] = x
+ TILE_SIZE
- 1;
2450 coords
[1] = y
+ TILE_SIZE
- 1;
2451 coords
[2] = x
+ TILE_SIZE
- 1;
2454 coords
[5] = y
+ TILE_SIZE
- 1;
2455 draw_polygon(fe
, coords
, 3, TRUE
, COL_LOWLIGHT
^ hl
);
2456 draw_polygon(fe
, coords
, 3, FALSE
, COL_LOWLIGHT
^ hl
);
2460 draw_polygon(fe
, coords
, 3, TRUE
, COL_HIGHLIGHT
^ hl
);
2461 draw_polygon(fe
, coords
, 3, FALSE
, COL_HIGHLIGHT
^ hl
);
2463 draw_rect(fe
, x
+ HIGHLIGHT_WIDTH
, y
+ HIGHLIGHT_WIDTH
,
2464 TILE_SIZE
- 2*HIGHLIGHT_WIDTH
, TILE_SIZE
- 2*HIGHLIGHT_WIDTH
,
2472 #define SETCOORD(n, dx, dy) do { \
2473 coords[(n)*2+0] = x + TILE_SIZE * (dx); \
2474 coords[(n)*2+1] = y + TILE_SIZE * (dy); \
2476 SETCOORD(0, 0.6, 0.35);
2477 SETCOORD(1, 0.6, 0.7);
2478 SETCOORD(2, 0.8, 0.8);
2479 SETCOORD(3, 0.25, 0.8);
2480 SETCOORD(4, 0.55, 0.7);
2481 SETCOORD(5, 0.55, 0.35);
2482 draw_polygon(fe
, coords
, 6, TRUE
, COL_FLAGBASE
);
2483 draw_polygon(fe
, coords
, 6, FALSE
, COL_FLAGBASE
);
2485 SETCOORD(0, 0.6, 0.2);
2486 SETCOORD(1, 0.6, 0.5);
2487 SETCOORD(2, 0.2, 0.35);
2488 draw_polygon(fe
, coords
, 3, TRUE
, COL_FLAG
);
2489 draw_polygon(fe
, coords
, 3, FALSE
, COL_FLAG
);
2492 } else if (v
== -3) {
2494 * Draw a question mark.
2496 draw_text(fe
, x
+ TILE_SIZE
/ 2, y
+ TILE_SIZE
/ 2,
2497 FONT_VARIABLE
, TILE_SIZE
* 6 / 8,
2498 ALIGN_VCENTRE
| ALIGN_HCENTRE
,
2503 * Clear the square to the background colour, and draw thin
2504 * grid lines along the top and left.
2506 * Exception is that for value 65 (mine we've just trodden
2507 * on), we clear the square to COL_BANG.
2509 draw_rect(fe
, x
, y
, TILE_SIZE
, TILE_SIZE
,
2510 (v
== 65 ? COL_BANG
: bg
));
2511 draw_line(fe
, x
, y
, x
+ TILE_SIZE
- 1, y
, COL_LOWLIGHT
);
2512 draw_line(fe
, x
, y
, x
, y
+ TILE_SIZE
- 1, COL_LOWLIGHT
);
2514 if (v
> 0 && v
<= 8) {
2521 draw_text(fe
, x
+ TILE_SIZE
/ 2, y
+ TILE_SIZE
/ 2,
2522 FONT_VARIABLE
, TILE_SIZE
* 7 / 8,
2523 ALIGN_VCENTRE
| ALIGN_HCENTRE
,
2524 (COL_1
- 1) + v
, str
);
2526 } else if (v
>= 64) {
2530 * FIXME: this could be done better!
2533 draw_text(fe
, x
+ TILE_SIZE
/ 2, y
+ TILE_SIZE
/ 2,
2534 FONT_VARIABLE
, TILE_SIZE
* 7 / 8,
2535 ALIGN_VCENTRE
| ALIGN_HCENTRE
,
2539 int cx
= x
+ TILE_SIZE
/ 2;
2540 int cy
= y
+ TILE_SIZE
/ 2;
2541 int r
= TILE_SIZE
/ 2 - 3;
2543 int xdx
= 1, xdy
= 0, ydx
= 0, ydy
= 1;
2546 for (i
= 0; i
< 4*5*2; i
+= 5*2) {
2547 coords
[i
+2*0+0] = cx
- r
/6*xdx
+ r
*4/5*ydx
;
2548 coords
[i
+2*0+1] = cy
- r
/6*xdy
+ r
*4/5*ydy
;
2549 coords
[i
+2*1+0] = cx
- r
/6*xdx
+ r
*ydx
;
2550 coords
[i
+2*1+1] = cy
- r
/6*xdy
+ r
*ydy
;
2551 coords
[i
+2*2+0] = cx
+ r
/6*xdx
+ r
*ydx
;
2552 coords
[i
+2*2+1] = cy
+ r
/6*xdy
+ r
*ydy
;
2553 coords
[i
+2*3+0] = cx
+ r
/6*xdx
+ r
*4/5*ydx
;
2554 coords
[i
+2*3+1] = cy
+ r
/6*xdy
+ r
*4/5*ydy
;
2555 coords
[i
+2*4+0] = cx
+ r
*3/5*xdx
+ r
*3/5*ydx
;
2556 coords
[i
+2*4+1] = cy
+ r
*3/5*xdy
+ r
*3/5*ydy
;
2566 draw_polygon(fe
, coords
, 5*4, TRUE
, COL_MINE
);
2567 draw_polygon(fe
, coords
, 5*4, FALSE
, COL_MINE
);
2569 draw_rect(fe
, cx
-r
/3, cy
-r
/3, r
/3, r
/4, COL_HIGHLIGHT
);
2575 * Cross through the mine.
2578 for (dx
= -1; dx
<= +1; dx
++) {
2579 draw_line(fe
, x
+ 3 + dx
, y
+ 2,
2580 x
+ TILE_SIZE
- 3 + dx
,
2581 y
+ TILE_SIZE
- 2, COL_CROSS
);
2582 draw_line(fe
, x
+ TILE_SIZE
- 3 + dx
, y
+ 2,
2583 x
+ 3 + dx
, y
+ TILE_SIZE
- 2,
2590 draw_update(fe
, x
, y
, TILE_SIZE
, TILE_SIZE
);
2593 static void game_redraw(frontend
*fe
, game_drawstate
*ds
, game_state
*oldstate
,
2594 game_state
*state
, int dir
, game_ui
*ui
,
2595 float animtime
, float flashtime
)
2598 int mines
, markers
, bg
;
2601 int frame
= (flashtime
/ FLASH_FRAME
);
2603 bg
= (ui
->flash_is_death ? COL_BACKGROUND
: COL_LOWLIGHT
);
2605 bg
= (ui
->flash_is_death ? COL_BANG
: COL_HIGHLIGHT
);
2607 bg
= COL_BACKGROUND
;
2613 TILE_SIZE
* state
->w
+ 2 * BORDER
,
2614 TILE_SIZE
* state
->h
+ 2 * BORDER
, COL_BACKGROUND
);
2615 draw_update(fe
, 0, 0,
2616 TILE_SIZE
* state
->w
+ 2 * BORDER
,
2617 TILE_SIZE
* state
->h
+ 2 * BORDER
);
2620 * Recessed area containing the whole puzzle.
2622 coords
[0] = COORD(state
->w
) + OUTER_HIGHLIGHT_WIDTH
- 1;
2623 coords
[1] = COORD(state
->h
) + OUTER_HIGHLIGHT_WIDTH
- 1;
2624 coords
[2] = COORD(state
->w
) + OUTER_HIGHLIGHT_WIDTH
- 1;
2625 coords
[3] = COORD(0) - OUTER_HIGHLIGHT_WIDTH
;
2626 coords
[4] = COORD(0) - OUTER_HIGHLIGHT_WIDTH
;
2627 coords
[5] = COORD(state
->h
) + OUTER_HIGHLIGHT_WIDTH
- 1;
2628 draw_polygon(fe
, coords
, 3, TRUE
, COL_HIGHLIGHT
);
2629 draw_polygon(fe
, coords
, 3, FALSE
, COL_HIGHLIGHT
);
2631 coords
[1] = COORD(0) - OUTER_HIGHLIGHT_WIDTH
;
2632 coords
[0] = COORD(0) - OUTER_HIGHLIGHT_WIDTH
;
2633 draw_polygon(fe
, coords
, 3, TRUE
, COL_LOWLIGHT
);
2634 draw_polygon(fe
, coords
, 3, FALSE
, COL_LOWLIGHT
);
2640 * Now draw the tiles. Also in this loop, count up the number
2641 * of mines and mine markers.
2643 mines
= markers
= 0;
2644 for (y
= 0; y
< ds
->h
; y
++)
2645 for (x
= 0; x
< ds
->w
; x
++) {
2646 int v
= state
->grid
[y
*ds
->w
+x
];
2650 if (state
->layout
->mines
&& state
->layout
->mines
[y
*ds
->w
+x
])
2653 if ((v
== -2 || v
== -3) &&
2654 (abs(x
-ui
->hx
) <= ui
->hradius
&& abs(y
-ui
->hy
) <= ui
->hradius
))
2657 if (ds
->grid
[y
*ds
->w
+x
] != v
|| bg
!= COL_BACKGROUND
) {
2658 draw_tile(fe
, COORD(x
), COORD(y
), v
, bg
);
2659 ds
->grid
[y
*ds
->w
+x
] = (bg
== COL_BACKGROUND ? v
: -10);
2663 if (!state
->layout
->mines
)
2664 mines
= state
->layout
->n
;
2667 * Update the status bar.
2670 char statusbar
[512];
2672 sprintf(statusbar
, "GAME OVER!");
2673 } else if (state
->won
) {
2674 sprintf(statusbar
, "COMPLETED!");
2676 sprintf(statusbar
, "Mines marked: %d / %d", markers
, mines
);
2678 status_bar(fe
, statusbar
);
2682 static float game_anim_length(game_state
*oldstate
, game_state
*newstate
,
2683 int dir
, game_ui
*ui
)
2688 static float game_flash_length(game_state
*oldstate
, game_state
*newstate
,
2689 int dir
, game_ui
*ui
)
2691 if (dir
> 0 && !oldstate
->dead
&& !oldstate
->won
) {
2692 if (newstate
->dead
) {
2693 ui
->flash_is_death
= TRUE
;
2694 return 3 * FLASH_FRAME
;
2696 if (newstate
->won
) {
2697 ui
->flash_is_death
= FALSE
;
2698 return 2 * FLASH_FRAME
;
2704 static int game_wants_statusbar(void)
2710 #define thegame mines
2713 const struct game thegame
= {
2714 "Mines", "games.mines",
2721 TRUE
, game_configure
, custom_params
,
2730 FALSE
, game_text_format
,
2737 game_free_drawstate
,
2741 game_wants_statusbar
,