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
64 int w
, h
, n
, dead
, won
;
65 char *mines
; /* real mine positions */
66 char *grid
; /* player knowledge */
68 * Each item in the `grid' array is one of the following values:
70 * - 0 to 8 mean the square is open and has a surrounding mine
73 * - -1 means the square is marked as a mine.
75 * - -2 means the square is unknown.
77 * - -3 means the square is marked with a question mark
78 * (FIXME: do we even want to bother with this?).
80 * - 64 means the square has had a mine revealed when the game
83 * - 65 means the square had a mine revealed and this was the
84 * one the player hits.
86 * - 66 means the square has a crossed-out mine because the
87 * player had incorrectly marked it.
91 static game_params
*default_params(void)
93 game_params
*ret
= snew(game_params
);
102 static int game_fetch_preset(int i
, char **name
, game_params
**params
)
106 static const struct { int w
, h
, n
; } values
[] = {
112 if (i
< 0 || i
>= lenof(values
))
115 ret
= snew(game_params
);
116 ret
->w
= values
[i
].w
;
117 ret
->h
= values
[i
].h
;
118 ret
->n
= values
[i
].n
;
121 sprintf(str
, "%dx%d, %d mines", ret
->w
, ret
->h
, ret
->n
);
128 static void free_params(game_params
*params
)
133 static game_params
*dup_params(game_params
*params
)
135 game_params
*ret
= snew(game_params
);
136 *ret
= *params
; /* structure copy */
140 static void decode_params(game_params
*params
, char const *string
)
142 char const *p
= string
;
145 while (*p
&& isdigit((unsigned char)*p
)) p
++;
149 while (*p
&& isdigit((unsigned char)*p
)) p
++;
151 params
->h
= params
->w
;
156 while (*p
&& (*p
== '.' || isdigit((unsigned char)*p
))) p
++;
158 params
->n
= params
->w
* params
->h
/ 10;
164 params
->unique
= FALSE
;
166 p
++; /* skip any other gunk */
170 static char *encode_params(game_params
*params
, int full
)
175 len
= sprintf(ret
, "%dx%d", params
->w
, params
->h
);
177 * Mine count is a generation-time parameter, since it can be
178 * deduced from the mine bitmap!
181 len
+= sprintf(ret
+len
, "n%d", params
->n
);
182 if (full
&& !params
->unique
)
184 assert(len
< lenof(ret
));
190 static config_item
*game_configure(game_params
*params
)
195 ret
= snewn(5, config_item
);
197 ret
[0].name
= "Width";
198 ret
[0].type
= C_STRING
;
199 sprintf(buf
, "%d", params
->w
);
200 ret
[0].sval
= dupstr(buf
);
203 ret
[1].name
= "Height";
204 ret
[1].type
= C_STRING
;
205 sprintf(buf
, "%d", params
->h
);
206 ret
[1].sval
= dupstr(buf
);
209 ret
[2].name
= "Mines";
210 ret
[2].type
= C_STRING
;
211 sprintf(buf
, "%d", params
->n
);
212 ret
[2].sval
= dupstr(buf
);
215 ret
[3].name
= "Ensure solubility";
216 ret
[3].type
= C_BOOLEAN
;
218 ret
[3].ival
= params
->unique
;
228 static game_params
*custom_params(config_item
*cfg
)
230 game_params
*ret
= snew(game_params
);
232 ret
->w
= atoi(cfg
[0].sval
);
233 ret
->h
= atoi(cfg
[1].sval
);
234 ret
->n
= atoi(cfg
[2].sval
);
235 if (strchr(cfg
[2].sval
, '%'))
236 ret
->n
= ret
->n
* (ret
->w
* ret
->h
) / 100;
237 ret
->unique
= cfg
[3].ival
;
242 static char *validate_params(game_params
*params
)
244 if (params
->w
<= 0 && params
->h
<= 0)
245 return "Width and height must both be greater than zero";
247 return "Width must be greater than zero";
249 return "Height must be greater than zero";
252 * FIXME: Need more constraints here. Not sure what the
253 * sensible limits for Minesweeper actually are. The limits
254 * probably ought to change, however, depending on uniqueness.
260 /* ----------------------------------------------------------------------
261 * Minesweeper solver, used to ensure the generated grids are
262 * solvable without having to take risks.
266 * Count the bits in a word. Only needs to cope with 16 bits.
268 static int bitcount16(int word
)
270 word
= ((word
& 0xAAAA) >> 1) + (word
& 0x5555);
271 word
= ((word
& 0xCCCC) >> 2) + (word
& 0x3333);
272 word
= ((word
& 0xF0F0) >> 4) + (word
& 0x0F0F);
273 word
= ((word
& 0xFF00) >> 8) + (word
& 0x00FF);
279 * We use a tree234 to store a large number of small localised
280 * sets, each with a mine count. We also keep some of those sets
281 * linked together into a to-do list.
284 short x
, y
, mask
, mines
;
286 struct set
*prev
, *next
;
289 static int setcmp(void *av
, void *bv
)
291 struct set
*a
= (struct set
*)av
;
292 struct set
*b
= (struct set
*)bv
;
296 else if (a
->y
> b
->y
)
298 else if (a
->x
< b
->x
)
300 else if (a
->x
> b
->x
)
302 else if (a
->mask
< b
->mask
)
304 else if (a
->mask
> b
->mask
)
312 struct set
*todo_head
, *todo_tail
;
315 static struct setstore
*ss_new(void)
317 struct setstore
*ss
= snew(struct setstore
);
318 ss
->sets
= newtree234(setcmp
);
319 ss
->todo_head
= ss
->todo_tail
= NULL
;
324 * Take two input sets, in the form (x,y,mask). Munge the first by
325 * taking either its intersection with the second or its difference
326 * with the second. Return the new mask part of the first set.
328 static int setmunge(int x1
, int y1
, int mask1
, int x2
, int y2
, int mask2
,
332 * Adjust the second set so that it has the same x,y
333 * coordinates as the first.
335 if (abs(x2
-x1
) >= 3 || abs(y2
-y1
) >= 3) {
339 mask2
&= ~(4|32|256);
349 mask2
&= ~(64|128|256);
361 * Invert the second set if `diff' is set (we're after A &~ B
362 * rather than A & B).
368 * Now all that's left is a logical AND.
370 return mask1
& mask2
;
373 static void ss_add_todo(struct setstore
*ss
, struct set
*s
)
376 return; /* already on it */
378 #ifdef SOLVER_DIAGNOSTICS
379 printf("adding set on todo list: %d,%d %03x %d\n",
380 s
->x
, s
->y
, s
->mask
, s
->mines
);
383 s
->prev
= ss
->todo_tail
;
393 static void ss_add(struct setstore
*ss
, int x
, int y
, int mask
, int mines
)
400 * Normalise so that x and y are genuinely the bounding
403 while (!(mask
& (1|8|64)))
405 while (!(mask
& (1|2|4)))
409 * Create a set structure and add it to the tree.
411 s
= snew(struct set
);
417 if (add234(ss
->sets
, s
) != s
) {
419 * This set already existed! Free it and return.
426 * We've added a new set to the tree, so put it on the todo
432 static void ss_remove(struct setstore
*ss
, struct set
*s
)
434 struct set
*next
= s
->next
, *prev
= s
->prev
;
436 #ifdef SOLVER_DIAGNOSTICS
437 printf("removing set %d,%d %03x\n", s
->x
, s
->y
, s
->mask
);
440 * Remove s from the todo list.
444 else if (s
== ss
->todo_head
)
445 ss
->todo_head
= next
;
449 else if (s
== ss
->todo_tail
)
450 ss
->todo_tail
= prev
;
455 * Remove s from the tree.
460 * Destroy the actual set structure.
466 * Return a dynamically allocated list of all the sets which
467 * overlap a provided input set.
469 static struct set
**ss_overlap(struct setstore
*ss
, int x
, int y
, int mask
)
471 struct set
**ret
= NULL
;
472 int nret
= 0, retsize
= 0;
475 for (xx
= x
-3; xx
< x
+3; xx
++)
476 for (yy
= y
-3; yy
< y
+3; yy
++) {
481 * Find the first set with these top left coordinates.
487 if (findrelpos234(ss
->sets
, &stmp
, NULL
, REL234_GE
, &pos
)) {
488 while ((s
= index234(ss
->sets
, pos
)) != NULL
&&
489 s
->x
== xx
&& s
->y
== yy
) {
491 * This set potentially overlaps the input one.
492 * Compute the intersection to see if they
493 * really overlap, and add it to the list if
496 if (setmunge(x
, y
, mask
, s
->x
, s
->y
, s
->mask
, FALSE
)) {
498 * There's an overlap.
500 if (nret
>= retsize
) {
502 ret
= sresize(ret
, retsize
, struct set
*);
512 ret
= sresize(ret
, nret
+1, struct set
*);
519 * Get an element from the head of the set todo list.
521 static struct set
*ss_todo(struct setstore
*ss
)
524 struct set
*ret
= ss
->todo_head
;
525 ss
->todo_head
= ret
->next
;
527 ss
->todo_head
->prev
= NULL
;
529 ss
->todo_tail
= NULL
;
530 ret
->next
= ret
->prev
= NULL
;
543 static void std_add(struct squaretodo
*std
, int i
)
546 std
->next
[std
->tail
] = i
;
553 static void known_squares(int w
, int h
, struct squaretodo
*std
, char *grid
,
554 int (*open
)(void *ctx
, int x
, int y
), void *openctx
,
555 int x
, int y
, int mask
, int mine
)
561 for (yy
= 0; yy
< 3; yy
++)
562 for (xx
= 0; xx
< 3; xx
++) {
564 int i
= (y
+ yy
) * w
+ (x
+ xx
);
567 * It's possible that this square is _already_
568 * known, in which case we don't try to add it to
574 grid
[i
] = -1; /* and don't open it! */
576 grid
[i
] = open(openctx
, x
+ xx
, y
+ yy
);
577 assert(grid
[i
] != -1); /* *bang* */
588 * This is data returned from the `perturb' function. It details
589 * which squares have become mines and which have become clear. The
590 * solver is (of course) expected to honourably not use that
591 * knowledge directly, but to efficently adjust its internal data
592 * structures and proceed based on only the information it
595 struct perturbation
{
597 int delta
; /* +1 == become a mine; -1 == cleared */
599 struct perturbations
{
601 struct perturbation
*changes
;
605 * Main solver entry point. You give it a grid of existing
606 * knowledge (-1 for a square known to be a mine, 0-8 for empty
607 * squares with a given number of neighbours, -2 for completely
608 * unknown), plus a function which you can call to open new squares
609 * once you're confident of them. It fills in as much more of the
614 * - -1 means deduction stalled and nothing could be done
615 * - 0 means deduction succeeded fully
616 * - >0 means deduction succeeded but some number of perturbation
617 * steps were required; the exact return value is the number of
620 static int minesolve(int w
, int h
, int n
, char *grid
,
621 int (*open
)(void *ctx
, int x
, int y
),
622 struct perturbations
*(*perturb
)(void *ctx
, char *grid
,
623 int x
, int y
, int mask
),
624 void *ctx
, random_state
*rs
)
626 struct setstore
*ss
= ss_new();
628 struct squaretodo astd
, *std
= &astd
;
633 * Set up a linked list of squares with known contents, so that
634 * we can process them one by one.
636 std
->next
= snewn(w
*h
, int);
637 std
->head
= std
->tail
= -1;
640 * Initialise that list with all known squares in the input
643 for (y
= 0; y
< h
; y
++) {
644 for (x
= 0; x
< w
; x
++) {
652 * Main deductive loop.
655 int done_something
= FALSE
;
659 * If there are any known squares on the todo list, process
660 * them and construct a set for each.
662 while (std
->head
!= -1) {
664 #ifdef SOLVER_DIAGNOSTICS
665 printf("known square at %d,%d [%d]\n", i
%w
, i
/w
, grid
[i
]);
667 std
->head
= std
->next
[i
];
675 int dx
, dy
, mines
, bit
, val
;
676 #ifdef SOLVER_DIAGNOSTICS
677 printf("creating set around this square\n");
680 * Empty square. Construct the set of non-known squares
681 * around this one, and determine its mine count.
686 for (dy
= -1; dy
<= +1; dy
++) {
687 for (dx
= -1; dx
<= +1; dx
++) {
688 #ifdef SOLVER_DIAGNOSTICS
689 printf("grid %d,%d = %d\n", x
+dx
, y
+dy
, grid
[i
+dy
*w
+dx
]);
691 if (x
+dx
< 0 || x
+dx
>= w
|| y
+dy
< 0 || y
+dy
>= h
)
692 /* ignore this one */;
693 else if (grid
[i
+dy
*w
+dx
] == -1)
695 else if (grid
[i
+dy
*w
+dx
] == -2)
701 ss_add(ss
, x
-1, y
-1, val
, mines
);
705 * Now, whether the square is empty or full, we must
706 * find any set which contains it and replace it with
707 * one which does not.
710 #ifdef SOLVER_DIAGNOSTICS
711 printf("finding sets containing known square %d,%d\n", x
, y
);
713 list
= ss_overlap(ss
, x
, y
, 1);
715 for (j
= 0; list
[j
]; j
++) {
716 int newmask
, newmines
;
721 * Compute the mask for this set minus the
722 * newly known square.
724 newmask
= setmunge(s
->x
, s
->y
, s
->mask
, x
, y
, 1, TRUE
);
727 * Compute the new mine count.
729 newmines
= s
->mines
- (grid
[i
] == -1);
732 * Insert the new set into the collection,
733 * unless it's been whittled right down to
737 ss_add(ss
, s
->x
, s
->y
, newmask
, newmines
);
740 * Destroy the old one; it is actually obsolete.
749 * Marking a fresh square as known certainly counts as
752 done_something
= TRUE
;
756 * Now pick a set off the to-do list and attempt deductions
759 if ((s
= ss_todo(ss
)) != NULL
) {
761 #ifdef SOLVER_DIAGNOSTICS
762 printf("set to do: %d,%d %03x %d\n", s
->x
, s
->y
, s
->mask
, s
->mines
);
765 * Firstly, see if this set has a mine count of zero or
766 * of its own cardinality.
768 if (s
->mines
== 0 || s
->mines
== bitcount16(s
->mask
)) {
770 * If so, we can immediately mark all the squares
771 * in the set as known.
773 #ifdef SOLVER_DIAGNOSTICS
776 known_squares(w
, h
, std
, grid
, open
, ctx
,
777 s
->x
, s
->y
, s
->mask
, (s
->mines
!= 0));
780 * Having done that, we need do nothing further
781 * with this set; marking all the squares in it as
782 * known will eventually eliminate it, and will
783 * also permit further deductions about anything
790 * Failing that, we now search through all the sets
791 * which overlap this one.
793 list
= ss_overlap(ss
, s
->x
, s
->y
, s
->mask
);
795 for (j
= 0; list
[j
]; j
++) {
796 struct set
*s2
= list
[j
];
797 int swing
, s2wing
, swc
, s2wc
;
800 * Find the non-overlapping parts s2-s and s-s2,
801 * and their cardinalities.
803 * I'm going to refer to these parts as `wings'
804 * surrounding the central part common to both
805 * sets. The `s wing' is s-s2; the `s2 wing' is
808 swing
= setmunge(s
->x
, s
->y
, s
->mask
, s2
->x
, s2
->y
, s2
->mask
,
810 s2wing
= setmunge(s2
->x
, s2
->y
, s2
->mask
, s
->x
, s
->y
, s
->mask
,
812 swc
= bitcount16(swing
);
813 s2wc
= bitcount16(s2wing
);
816 * If one set has more mines than the other, and
817 * the number of extra mines is equal to the
818 * cardinality of that set's wing, then we can mark
819 * every square in the wing as a known mine, and
820 * every square in the other wing as known clear.
822 if (swc
== s
->mines
- s2
->mines
||
823 s2wc
== s2
->mines
- s
->mines
) {
824 known_squares(w
, h
, std
, grid
, open
, ctx
,
826 (swc
== s
->mines
- s2
->mines
));
827 known_squares(w
, h
, std
, grid
, open
, ctx
,
828 s2
->x
, s2
->y
, s2wing
,
829 (s2wc
== s2
->mines
- s
->mines
));
834 * Failing that, see if one set is a subset of the
835 * other. If so, we can divide up the mine count of
836 * the larger set between the smaller set and its
837 * complement, even if neither smaller set ends up
838 * being immediately clearable.
840 if (swc
== 0 && s2wc
!= 0) {
841 /* s is a subset of s2. */
842 assert(s2
->mines
> s
->mines
);
843 ss_add(ss
, s2
->x
, s2
->y
, s2wing
, s2
->mines
- s
->mines
);
844 } else if (s2wc
== 0 && swc
!= 0) {
845 /* s2 is a subset of s. */
846 assert(s
->mines
> s2
->mines
);
847 ss_add(ss
, s
->x
, s
->y
, swing
, s
->mines
- s2
->mines
);
854 * In this situation we have definitely done
855 * _something_, even if it's only reducing the size of
858 done_something
= TRUE
;
861 * We have nothing left on our todo list, which means
862 * all localised deductions have failed. Our next step
863 * is to resort to global deduction based on the total
864 * mine count. This is computationally expensive
865 * compared to any of the above deductions, which is
866 * why we only ever do it when all else fails, so that
867 * hopefully it won't have to happen too often.
869 * If you pass n<0 into this solver, that informs it
870 * that you do not know the total mine count, so it
871 * won't even attempt these deductions.
874 int minesleft
, squaresleft
;
875 int nsets
, setused
[10], cursor
;
878 * Start by scanning the current grid state to work out
879 * how many unknown squares we still have, and how many
880 * mines are to be placed in them.
884 for (i
= 0; i
< w
*h
; i
++) {
887 else if (grid
[i
] == -2)
891 #ifdef SOLVER_DIAGNOSTICS
892 printf("global deduction time: squaresleft=%d minesleft=%d\n",
893 squaresleft
, minesleft
);
894 for (y
= 0; y
< h
; y
++) {
895 for (x
= 0; x
< w
; x
++) {
911 * If there _are_ no unknown squares, we have actually
914 if (squaresleft
== 0) {
915 assert(minesleft
== 0);
920 * First really simple case: if there are no more mines
921 * left, or if there are exactly as many mines left as
922 * squares to play them in, then it's all easy.
924 if (minesleft
== 0 || minesleft
== squaresleft
) {
925 for (i
= 0; i
< w
*h
; i
++)
927 known_squares(w
, h
, std
, grid
, open
, ctx
,
928 i
% w
, i
/ w
, 1, minesleft
!= 0);
929 continue; /* now go back to main deductive loop */
933 * Failing that, we have to do some _real_ work.
934 * Ideally what we do here is to try every single
935 * combination of the currently available sets, in an
936 * attempt to find a disjoint union (i.e. a set of
937 * squares with a known mine count between them) such
938 * that the remaining unknown squares _not_ contained
939 * in that union either contain no mines or are all
942 * Actually enumerating all 2^n possibilities will get
943 * a bit slow for large n, so I artificially cap this
944 * recursion at n=10 to avoid too much pain.
946 nsets
= count234(ss
->sets
);
947 if (nsets
<= lenof(setused
)) {
949 * Doing this with actual recursive function calls
950 * would get fiddly because a load of local
951 * variables from this function would have to be
952 * passed down through the recursion. So instead
953 * I'm going to use a virtual recursion within this
954 * function. The way this works is:
956 * - we have an array `setused', such that
957 * setused[n] is 0 or 1 depending on whether set
958 * n is currently in the union we are
961 * - we have a value `cursor' which indicates how
962 * much of `setused' we have so far filled in.
963 * It's conceptually the recursion depth.
965 * We begin by setting `cursor' to zero. Then:
967 * - if cursor can advance, we advance it by one.
968 * We set the value in `setused' that it went
969 * past to 1 if that set is disjoint from
970 * anything else currently in `setused', or to 0
973 * - If cursor cannot advance because it has
974 * reached the end of the setused list, then we
975 * have a maximal disjoint union. Check to see
976 * whether its mine count has any useful
977 * properties. If so, mark all the squares not
978 * in the union as known and terminate.
980 * - If cursor has reached the end of setused and
981 * the algorithm _hasn't_ terminated, back
982 * cursor up to the nearest 1, turn it into a 0
983 * and advance cursor just past it.
985 * - If we attempt to back up to the nearest 1 and
986 * there isn't one at all, then we have gone
987 * through all disjoint unions of sets in the
988 * list and none of them has been helpful, so we
991 struct set
*sets
[lenof(setused
)];
992 for (i
= 0; i
< nsets
; i
++)
993 sets
[i
] = index234(ss
->sets
, i
);
998 if (cursor
< nsets
) {
1001 /* See if any existing set overlaps this one. */
1002 for (i
= 0; i
< cursor
; i
++)
1004 setmunge(sets
[cursor
]->x
,
1007 sets
[i
]->x
, sets
[i
]->y
, sets
[i
]->mask
,
1015 * We're adding this set to our union,
1016 * so adjust minesleft and squaresleft
1019 minesleft
-= sets
[cursor
]->mines
;
1020 squaresleft
-= bitcount16(sets
[cursor
]->mask
);
1023 setused
[cursor
++] = ok
;
1025 #ifdef SOLVER_DIAGNOSTICS
1026 printf("trying a set combination with %d %d\n",
1027 squaresleft
, minesleft
);
1028 #endif /* SOLVER_DIAGNOSTICS */
1031 * We've reached the end. See if we've got
1032 * anything interesting.
1034 if (squaresleft
> 0 &&
1035 (minesleft
== 0 || minesleft
== squaresleft
)) {
1037 * We have! There is at least one
1038 * square not contained within the set
1039 * union we've just found, and we can
1040 * deduce that either all such squares
1041 * are mines or all are not (depending
1042 * on whether minesleft==0). So now all
1043 * we have to do is actually go through
1044 * the grid, find those squares, and
1047 for (i
= 0; i
< w
*h
; i
++)
1048 if (grid
[i
] == -2) {
1052 for (j
= 0; j
< nsets
; j
++)
1054 setmunge(sets
[j
]->x
, sets
[j
]->y
,
1055 sets
[j
]->mask
, x
, y
, 1,
1061 known_squares(w
, h
, std
, grid
,
1063 x
, y
, 1, minesleft
!= 0);
1066 done_something
= TRUE
;
1067 break; /* return to main deductive loop */
1071 * If we reach here, then this union hasn't
1072 * done us any good, so move on to the
1073 * next. Backtrack cursor to the nearest 1,
1074 * change it to a 0 and continue.
1076 while (cursor
-- >= 0 && !setused
[cursor
]);
1078 assert(setused
[cursor
]);
1081 * We're removing this set from our
1082 * union, so re-increment minesleft and
1085 minesleft
+= sets
[cursor
]->mines
;
1086 squaresleft
+= bitcount16(sets
[cursor
]->mask
);
1088 setused
[cursor
++] = 0;
1091 * We've backtracked all the way to the
1092 * start without finding a single 1,
1093 * which means that our virtual
1094 * recursion is complete and nothing
1109 #ifdef SOLVER_DIAGNOSTICS
1111 * Dump the current known state of the grid.
1113 printf("solver ran out of steam, ret=%d, grid:\n", nperturbs
);
1114 for (y
= 0; y
< h
; y
++) {
1115 for (x
= 0; x
< w
; x
++) {
1116 int v
= grid
[y
*w
+x
];
1132 for (i
= 0; (s
= index234(ss
->sets
, i
)) != NULL
; i
++)
1133 printf("remaining set: %d,%d %03x %d\n", s
->x
, s
->y
, s
->mask
, s
->mines
);
1138 * Now we really are at our wits' end as far as solving
1139 * this grid goes. Our only remaining option is to call
1140 * a perturb function and ask it to modify the grid to
1144 struct perturbations
*ret
;
1150 * Choose a set at random from the current selection,
1151 * and ask the perturb function to either fill or empty
1154 * If we have no sets at all, we must give up.
1156 if (count234(ss
->sets
) == 0)
1158 s
= index234(ss
->sets
, random_upto(rs
, count234(ss
->sets
)));
1159 #ifdef SOLVER_DIAGNOSTICS
1160 printf("perturbing on set %d,%d %03x\n", s
->x
, s
->y
, s
->mask
);
1162 ret
= perturb(ctx
, grid
, s
->x
, s
->y
, s
->mask
);
1165 assert(ret
->n
> 0); /* otherwise should have been NULL */
1168 * A number of squares have been fiddled with, and
1169 * the returned structure tells us which. Adjust
1170 * the mine count in any set which overlaps one of
1171 * those squares, and put them back on the to-do
1174 for (i
= 0; i
< ret
->n
; i
++) {
1175 #ifdef SOLVER_DIAGNOSTICS
1176 printf("perturbation %s mine at %d,%d\n",
1177 ret
->changes
[i
].delta
> 0 ?
"added" : "removed",
1178 ret
->changes
[i
].x
, ret
->changes
[i
].y
);
1181 list
= ss_overlap(ss
,
1182 ret
->changes
[i
].x
, ret
->changes
[i
].y
, 1);
1184 for (j
= 0; list
[j
]; j
++) {
1185 list
[j
]->mines
+= ret
->changes
[i
].delta
;
1186 ss_add_todo(ss
, list
[j
]);
1193 * Now free the returned data.
1195 sfree(ret
->changes
);
1198 #ifdef SOLVER_DIAGNOSTICS
1200 * Dump the current known state of the grid.
1202 printf("state after perturbation:\n", nperturbs
);
1203 for (y
= 0; y
< h
; y
++) {
1204 for (x
= 0; x
< w
; x
++) {
1205 int v
= grid
[y
*w
+x
];
1221 for (i
= 0; (s
= index234(ss
->sets
, i
)) != NULL
; i
++)
1222 printf("remaining set: %d,%d %03x %d\n", s
->x
, s
->y
, s
->mask
, s
->mines
);
1227 * And now we can go back round the deductive loop.
1234 * If we get here, even that didn't work (either we didn't
1235 * have a perturb function or it returned failure), so we
1242 * See if we've got any unknown squares left.
1244 for (y
= 0; y
< h
; y
++)
1245 for (x
= 0; x
< w
; x
++)
1246 if (grid
[y
*w
+x
] == -2) {
1247 nperturbs
= -1; /* failed to complete */
1252 * Free the set list and square-todo list.
1256 while ((s
= delpos234(ss
->sets
, 0)) != NULL
)
1258 freetree234(ss
->sets
);
1266 /* ----------------------------------------------------------------------
1267 * Grid generator which uses the above solver.
1277 static int mineopen(void *vctx
, int x
, int y
)
1279 struct minectx
*ctx
= (struct minectx
*)vctx
;
1282 assert(x
>= 0 && x
< ctx
->w
&& y
>= 0 && y
< ctx
->h
);
1283 if (ctx
->grid
[y
* ctx
->w
+ x
])
1284 return -1; /* *bang* */
1287 for (i
= -1; i
<= +1; i
++) {
1288 if (x
+ i
< 0 || x
+ i
>= ctx
->w
)
1290 for (j
= -1; j
<= +1; j
++) {
1291 if (y
+ j
< 0 || y
+ j
>= ctx
->h
)
1293 if (i
== 0 && j
== 0)
1295 if (ctx
->grid
[(y
+j
) * ctx
->w
+ (x
+i
)])
1303 /* Structure used internally to mineperturb(). */
1305 int x
, y
, type
, random
;
1307 static int squarecmp(const void *av
, const void *bv
)
1309 const struct square
*a
= (const struct square
*)av
;
1310 const struct square
*b
= (const struct square
*)bv
;
1311 if (a
->type
< b
->type
)
1313 else if (a
->type
> b
->type
)
1315 else if (a
->random
< b
->random
)
1317 else if (a
->random
> b
->random
)
1319 else if (a
->y
< b
->y
)
1321 else if (a
->y
> b
->y
)
1323 else if (a
->x
< b
->x
)
1325 else if (a
->x
> b
->x
)
1330 static struct perturbations
*mineperturb(void *vctx
, char *grid
,
1331 int setx
, int sety
, int mask
)
1333 struct minectx
*ctx
= (struct minectx
*)vctx
;
1334 struct square
*sqlist
;
1335 int x
, y
, dx
, dy
, i
, n
, nfull
, nempty
;
1336 struct square
*tofill
[9], *toempty
[9], **todo
;
1337 int ntofill
, ntoempty
, ntodo
, dtodo
, dset
;
1338 struct perturbations
*ret
;
1341 * Make a list of all the squares in the grid which we can
1342 * possibly use. This list should be in preference order, which
1345 * - first, unknown squares on the boundary of known space
1346 * - next, unknown squares beyond that boundary
1347 * - as a very last resort, known squares, but not within one
1348 * square of the starting position.
1350 * Each of these sections needs to be shuffled independently.
1351 * We do this by preparing list of all squares and then sorting
1352 * it with a random secondary key.
1354 sqlist
= snewn(ctx
->w
* ctx
->h
, struct square
);
1356 for (y
= 0; y
< ctx
->h
; y
++)
1357 for (x
= 0; x
< ctx
->w
; x
++) {
1359 * If this square is too near the starting position,
1360 * don't put it on the list at all.
1362 if (abs(y
- ctx
->sy
) <= 1 && abs(x
- ctx
->sx
) <= 1)
1366 * If this square is in the input set, also don't put
1369 if (x
>= setx
&& x
< setx
+ 3 &&
1370 y
>= sety
&& y
< sety
+ 3 &&
1371 mask
& (1 << ((y
-sety
)*3+(x
-setx
))))
1377 if (grid
[y
*ctx
->w
+x
] != -2) {
1378 sqlist
[n
].type
= 3; /* known square */
1381 * Unknown square. Examine everything around it and
1382 * see if it borders on any known squares. If it
1383 * does, it's class 1, otherwise it's 2.
1388 for (dy
= -1; dy
<= +1; dy
++)
1389 for (dx
= -1; dx
<= +1; dx
++)
1390 if (x
+dx
>= 0 && x
+dx
< ctx
->w
&&
1391 y
+dy
>= 0 && y
+dy
< ctx
->h
&&
1392 grid
[(y
+dy
)*ctx
->w
+(x
+dx
)] != -2) {
1399 * Finally, a random number to cause qsort to
1400 * shuffle within each group.
1402 sqlist
[n
].random
= random_bits(ctx
->rs
, 31);
1407 qsort(sqlist
, n
, sizeof(struct square
), squarecmp
);
1410 * Now count up the number of full and empty squares in the set
1411 * we've been provided.
1414 for (dy
= 0; dy
< 3; dy
++)
1415 for (dx
= 0; dx
< 3; dx
++)
1416 if (mask
& (1 << (dy
*3+dx
))) {
1417 assert(setx
+dx
<= ctx
->w
);
1418 assert(sety
+dy
<= ctx
->h
);
1419 if (ctx
->grid
[(sety
+dy
)*ctx
->w
+(setx
+dx
)])
1426 * Now go through our sorted list until we find either `nfull'
1427 * empty squares, or `nempty' full squares; these will be
1428 * swapped with the appropriate squares in the set to either
1429 * fill or empty the set while keeping the same number of mines
1432 ntofill
= ntoempty
= 0;
1433 for (i
= 0; i
< n
; i
++) {
1434 struct square
*sq
= &sqlist
[i
];
1435 if (ctx
->grid
[sq
->y
* ctx
->w
+ sq
->x
])
1436 toempty
[ntoempty
++] = sq
;
1438 tofill
[ntofill
++] = sq
;
1439 if (ntofill
== nfull
|| ntoempty
== nempty
)
1444 * If this didn't work at all, I think we just give up.
1446 if (ntofill
!= nfull
&& ntoempty
!= nempty
) {
1452 * Now we're pretty much there. We need to either
1453 * (a) put a mine in each of the empty squares in the set, and
1454 * take one out of each square in `toempty'
1455 * (b) take a mine out of each of the full squares in the set,
1456 * and put one in each square in `tofill'
1457 * depending on which one we've found enough squares to do.
1459 * So we start by constructing our list of changes to return to
1460 * the solver, so that it can update its data structures
1461 * efficiently rather than having to rescan the whole grid.
1463 ret
= snew(struct perturbations
);
1464 if (ntofill
== nfull
) {
1476 ret
->changes
= snewn(ret
->n
, struct perturbation
);
1477 for (i
= 0; i
< ntodo
; i
++) {
1478 ret
->changes
[i
].x
= todo
[i
]->x
;
1479 ret
->changes
[i
].y
= todo
[i
]->y
;
1480 ret
->changes
[i
].delta
= dtodo
;
1482 /* now i == ntodo */
1483 for (dy
= 0; dy
< 3; dy
++)
1484 for (dx
= 0; dx
< 3; dx
++)
1485 if (mask
& (1 << (dy
*3+dx
))) {
1486 int currval
= (ctx
->grid
[(sety
+dy
)*ctx
->w
+(setx
+dx
)] ?
+1 : -1);
1487 if (dset
== -currval
) {
1488 ret
->changes
[i
].x
= setx
+ dx
;
1489 ret
->changes
[i
].y
= sety
+ dy
;
1490 ret
->changes
[i
].delta
= dset
;
1494 assert(i
== ret
->n
);
1499 * Having set up the precise list of changes we're going to
1500 * make, we now simply make them and return.
1502 for (i
= 0; i
< ret
->n
; i
++) {
1505 x
= ret
->changes
[i
].x
;
1506 y
= ret
->changes
[i
].y
;
1507 delta
= ret
->changes
[i
].delta
;
1510 * Check we're not trying to add an existing mine or remove
1513 assert((delta
< 0) ^ (ctx
->grid
[y
*ctx
->w
+x
] == 0));
1516 * Actually make the change.
1518 ctx
->grid
[y
*ctx
->w
+x
] = (delta
> 0);
1521 * Update any numbers already present in the grid.
1523 for (dy
= -1; dy
<= +1; dy
++)
1524 for (dx
= -1; dx
<= +1; dx
++)
1525 if (x
+dx
>= 0 && x
+dx
< ctx
->w
&&
1526 y
+dy
>= 0 && y
+dy
< ctx
->h
&&
1527 grid
[(y
+dy
)*ctx
->w
+(x
+dx
)] != -2) {
1528 if (dx
== 0 && dy
== 0) {
1530 * The square itself is marked as known in
1531 * the grid. Mark it as a mine if it's a
1532 * mine, or else work out its number.
1535 grid
[y
*ctx
->w
+x
] = -1;
1537 int dx2
, dy2
, minecount
= 0;
1538 for (dy2
= -1; dy2
<= +1; dy2
++)
1539 for (dx2
= -1; dx2
<= +1; dx2
++)
1540 if (x
+dx2
>= 0 && x
+dx2
< ctx
->w
&&
1541 y
+dy2
>= 0 && y
+dy2
< ctx
->h
&&
1542 ctx
->grid
[(y
+dy2
)*ctx
->w
+(x
+dx2
)])
1544 grid
[y
*ctx
->w
+x
] = minecount
;
1547 if (grid
[(y
+dy
)*ctx
->w
+(x
+dx
)] >= 0)
1548 grid
[(y
+dy
)*ctx
->w
+(x
+dx
)] += delta
;
1553 #ifdef GENERATION_DIAGNOSTICS
1556 printf("grid after perturbing:\n");
1557 for (yy
= 0; yy
< ctx
->h
; yy
++) {
1558 for (xx
= 0; xx
< ctx
->w
; xx
++) {
1559 int v
= ctx
->grid
[yy
*ctx
->w
+xx
];
1560 if (yy
== ctx
->sy
&& xx
== ctx
->sx
) {
1578 static char *minegen(int w
, int h
, int n
, int x
, int y
, int unique
,
1581 char *ret
= snewn(w
*h
, char);
1587 memset(ret
, 0, w
*h
);
1590 * Start by placing n mines, none of which is at x,y or within
1594 int *tmp
= snewn(w
*h
, int);
1598 * Write down the list of possible mine locations.
1601 for (i
= 0; i
< h
; i
++)
1602 for (j
= 0; j
< w
; j
++)
1603 if (abs(i
- y
) > 1 || abs(j
- x
) > 1)
1607 * Now pick n off the list at random.
1611 i
= random_upto(rs
, k
);
1619 #ifdef GENERATION_DIAGNOSTICS
1622 printf("grid after initial generation:\n");
1623 for (yy
= 0; yy
< h
; yy
++) {
1624 for (xx
= 0; xx
< w
; xx
++) {
1625 int v
= ret
[yy
*w
+xx
];
1626 if (yy
== y
&& xx
== x
) {
1642 * Now set up a results grid to run the solver in, and a
1643 * context for the solver to open squares. Then run the solver
1644 * repeatedly; if the number of perturb steps ever goes up or
1645 * it ever returns -1, give up completely.
1647 * We bypass this bit if we're not after a unique grid.
1650 char *solvegrid
= snewn(w
*h
, char);
1651 struct minectx actx
, *ctx
= &actx
;
1652 int solveret
, prevret
= -2;
1662 memset(solvegrid
, -2, w
*h
);
1663 solvegrid
[y
*w
+x
] = mineopen(ctx
, x
, y
);
1664 assert(solvegrid
[y
*w
+x
] == 0); /* by deliberate arrangement */
1667 minesolve(w
, h
, n
, solvegrid
, mineopen
, mineperturb
, ctx
, rs
);
1668 if (solveret
< 0 || (prevret
>= 0 && solveret
>= prevret
)) {
1671 } else if (solveret
== 0) {
1688 * The Mines game descriptions contain the location of every mine,
1689 * and can therefore be used to cheat.
1691 * It would be pointless to attempt to _prevent_ this form of
1692 * cheating by encrypting the description, since Mines is
1693 * open-source so anyone can find out the encryption key. However,
1694 * I think it is worth doing a bit of gentle obfuscation to prevent
1695 * _accidental_ spoilers: if you happened to note that the game ID
1696 * starts with an F, for example, you might be unable to put the
1697 * knowledge of those mines out of your mind while playing. So,
1698 * just as discussions of film endings are rot13ed to avoid
1699 * spoiling it for people who don't want to be told, we apply a
1700 * keyless, reversible, but visually completely obfuscatory masking
1701 * function to the mine bitmap.
1703 static void obfuscate_bitmap(unsigned char *bmp
, int bits
, int decode
)
1705 int bytes
, firsthalf
, secondhalf
;
1707 unsigned char *seedstart
;
1709 unsigned char *targetstart
;
1715 * My obfuscation algorithm is similar in concept to the OAEP
1716 * encoding used in some forms of RSA. Here's a specification
1719 * + We have a `masking function' which constructs a stream of
1720 * pseudorandom bytes from a seed of some number of input
1723 * + We pad out our input bit stream to a whole number of
1724 * bytes by adding up to 7 zero bits on the end. (In fact
1725 * the bitmap passed as input to this function will already
1726 * have had this done in practice.)
1728 * + We divide the _byte_ stream exactly in half, rounding the
1729 * half-way position _down_. So an 81-bit input string, for
1730 * example, rounds up to 88 bits or 11 bytes, and then
1731 * dividing by two gives 5 bytes in the first half and 6 in
1734 * + We generate a mask from the second half of the bytes, and
1735 * XOR it over the first half.
1737 * + We generate a mask from the (encoded) first half of the
1738 * bytes, and XOR it over the second half. Any null bits at
1739 * the end which were added as padding are cleared back to
1740 * zero even if this operation would have made them nonzero.
1742 * To de-obfuscate, the steps are precisely the same except
1743 * that the final two are reversed.
1745 * Finally, our masking function. Given an input seed string of
1746 * bytes, the output mask consists of concatenating the SHA-1
1747 * hashes of the seed string and successive decimal integers,
1751 bytes
= (bits
+ 7) / 8;
1752 firsthalf
= bytes
/ 2;
1753 secondhalf
= bytes
- firsthalf
;
1755 steps
[decode ?
1 : 0].seedstart
= bmp
+ firsthalf
;
1756 steps
[decode ?
1 : 0].seedlen
= secondhalf
;
1757 steps
[decode ?
1 : 0].targetstart
= bmp
;
1758 steps
[decode ?
1 : 0].targetlen
= firsthalf
;
1760 steps
[decode ?
0 : 1].seedstart
= bmp
;
1761 steps
[decode ?
0 : 1].seedlen
= firsthalf
;
1762 steps
[decode ?
0 : 1].targetstart
= bmp
+ firsthalf
;
1763 steps
[decode ?
0 : 1].targetlen
= secondhalf
;
1765 for (i
= 0; i
< 2; i
++) {
1766 SHA_State base
, final
;
1767 unsigned char digest
[20];
1769 int digestpos
= 20, counter
= 0;
1772 SHA_Bytes(&base
, steps
[i
].seedstart
, steps
[i
].seedlen
);
1774 for (j
= 0; j
< steps
[i
].targetlen
; j
++) {
1775 if (digestpos
>= 20) {
1776 sprintf(numberbuf
, "%d", counter
++);
1778 SHA_Bytes(&final
, numberbuf
, strlen(numberbuf
));
1779 SHA_Final(&final
, digest
);
1782 steps
[i
].targetstart
[j
] ^= digest
[digestpos
]++;
1786 * Mask off the pad bits in the final byte after both steps.
1789 bmp
[bits
/ 8] &= 0xFF & (0xFF00 >> (bits
% 8));
1793 static char *new_game_desc(game_params
*params
, random_state
*rs
,
1794 game_aux_info
**aux
)
1796 char *grid
, *ret
, *p
;
1801 * FIXME: allow user to specify initial open square.
1803 x
= random_upto(rs
, params
->w
);
1804 y
= random_upto(rs
, params
->h
);
1806 grid
= minegen(params
->w
, params
->h
, params
->n
, x
, y
, params
->unique
, rs
);
1809 * Set up the mine bitmap and obfuscate it.
1811 area
= params
->w
* params
->h
;
1812 bmp
= snewn((area
+ 7) / 8, unsigned char);
1813 memset(bmp
, 0, (area
+ 7) / 8);
1814 for (i
= 0; i
< area
; i
++) {
1816 bmp
[i
/ 8] |= 0x80 >> (i
% 8);
1818 obfuscate_bitmap(bmp
, area
, FALSE
);
1821 * Now encode the resulting bitmap in hex. We can work to
1822 * nibble rather than byte granularity, since the obfuscation
1823 * function guarantees to return a bit string of the same
1824 * length as its input.
1826 ret
= snewn((area
+3)/4 + 100, char);
1827 p
= ret
+ sprintf(ret
, "%d,%d,m", x
, y
); /* 'm' == masked */
1828 for (i
= 0; i
< (area
+3)/4; i
++) {
1832 *p
++ = "0123456789abcdef"[v
& 0xF];
1841 static void game_free_aux_info(game_aux_info
*aux
)
1843 assert(!"Shouldn't happen");
1846 static char *validate_desc(game_params
*params
, char *desc
)
1848 int wh
= params
->w
* params
->h
;
1851 if (!*desc
|| !isdigit((unsigned char)*desc
))
1852 return "No initial x-coordinate in game description";
1854 if (x
< 0 || x
>= params
->w
)
1855 return "Initial x-coordinate was out of range";
1856 while (*desc
&& isdigit((unsigned char)*desc
))
1857 desc
++; /* skip over x coordinate */
1859 return "No ',' after initial x-coordinate in game description";
1860 desc
++; /* eat comma */
1861 if (!*desc
|| !isdigit((unsigned char)*desc
))
1862 return "No initial y-coordinate in game description";
1864 if (y
< 0 || y
>= params
->h
)
1865 return "Initial y-coordinate was out of range";
1866 while (*desc
&& isdigit((unsigned char)*desc
))
1867 desc
++; /* skip over y coordinate */
1869 return "No ',' after initial y-coordinate in game description";
1870 desc
++; /* eat comma */
1871 /* eat `m', meaning `masked', if present */
1874 /* now just check length of remainder */
1875 if (strlen(desc
) != (wh
+3)/4)
1876 return "Game description is wrong length";
1881 static int open_square(game_state
*state
, int x
, int y
)
1883 int w
= state
->w
, h
= state
->h
;
1884 int xx
, yy
, nmines
, ncovered
;
1886 if (state
->mines
[y
*w
+x
]) {
1888 * The player has landed on a mine. Bad luck. Expose all
1892 for (yy
= 0; yy
< h
; yy
++)
1893 for (xx
= 0; xx
< w
; xx
++) {
1894 if (state
->mines
[yy
*w
+xx
] &&
1895 (state
->grid
[yy
*w
+xx
] == -2 ||
1896 state
->grid
[yy
*w
+xx
] == -3)) {
1897 state
->grid
[yy
*w
+xx
] = 64;
1899 if (!state
->mines
[yy
*w
+xx
] &&
1900 state
->grid
[yy
*w
+xx
] == -1) {
1901 state
->grid
[yy
*w
+xx
] = 66;
1904 state
->grid
[y
*w
+x
] = 65;
1909 * Otherwise, the player has opened a safe square. Mark it to-do.
1911 state
->grid
[y
*w
+x
] = -10; /* `todo' value internal to this func */
1914 * Now go through the grid finding all `todo' values and
1915 * opening them. Every time one of them turns out to have no
1916 * neighbouring mines, we add all its unopened neighbours to
1919 * FIXME: We really ought to be able to do this better than
1920 * using repeated N^2 scans of the grid.
1923 int done_something
= FALSE
;
1925 for (yy
= 0; yy
< h
; yy
++)
1926 for (xx
= 0; xx
< w
; xx
++)
1927 if (state
->grid
[yy
*w
+xx
] == -10) {
1930 assert(!state
->mines
[yy
*w
+xx
]);
1934 for (dx
= -1; dx
<= +1; dx
++)
1935 for (dy
= -1; dy
<= +1; dy
++)
1936 if (xx
+dx
>= 0 && xx
+dx
< state
->w
&&
1937 yy
+dy
>= 0 && yy
+dy
< state
->h
&&
1938 state
->mines
[(yy
+dy
)*w
+(xx
+dx
)])
1941 state
->grid
[yy
*w
+xx
] = v
;
1944 for (dx
= -1; dx
<= +1; dx
++)
1945 for (dy
= -1; dy
<= +1; dy
++)
1946 if (xx
+dx
>= 0 && xx
+dx
< state
->w
&&
1947 yy
+dy
>= 0 && yy
+dy
< state
->h
&&
1948 state
->grid
[(yy
+dy
)*w
+(xx
+dx
)] == -2)
1949 state
->grid
[(yy
+dy
)*w
+(xx
+dx
)] = -10;
1952 done_something
= TRUE
;
1955 if (!done_something
)
1960 * Finally, scan the grid and see if exactly as many squares
1961 * are still covered as there are mines. If so, set the `won'
1962 * flag and fill in mine markers on all covered squares.
1964 nmines
= ncovered
= 0;
1965 for (yy
= 0; yy
< h
; yy
++)
1966 for (xx
= 0; xx
< w
; xx
++) {
1967 if (state
->grid
[yy
*w
+xx
] < 0)
1969 if (state
->mines
[yy
*w
+xx
])
1972 assert(ncovered
>= nmines
);
1973 if (ncovered
== nmines
) {
1974 for (yy
= 0; yy
< h
; yy
++)
1975 for (xx
= 0; xx
< w
; xx
++) {
1976 if (state
->grid
[yy
*w
+xx
] < 0)
1977 state
->grid
[yy
*w
+xx
] = -1;
1985 static game_state
*new_game(game_params
*params
, char *desc
)
1987 game_state
*state
= snew(game_state
);
1988 int i
, wh
, x
, y
, ret
, masked
;
1991 state
->w
= params
->w
;
1992 state
->h
= params
->h
;
1993 state
->n
= params
->n
;
1994 state
->dead
= state
->won
= FALSE
;
1996 wh
= state
->w
* state
->h
;
1997 state
->mines
= snewn(wh
, char);
2000 while (*desc
&& isdigit((unsigned char)*desc
))
2001 desc
++; /* skip over x coordinate */
2002 if (*desc
) desc
++; /* eat comma */
2004 while (*desc
&& isdigit((unsigned char)*desc
))
2005 desc
++; /* skip over y coordinate */
2006 if (*desc
) desc
++; /* eat comma */
2013 * We permit game IDs to be entered by hand without the
2014 * masking transformation.
2019 bmp
= snewn((wh
+ 7) / 8, unsigned char);
2020 memset(bmp
, 0, (wh
+ 7) / 8);
2021 for (i
= 0; i
< (wh
+3)/4; i
++) {
2025 assert(c
!= 0); /* validate_desc should have caught */
2026 if (c
>= '0' && c
<= '9')
2028 else if (c
>= 'a' && c
<= 'f')
2030 else if (c
>= 'A' && c
<= 'F')
2035 bmp
[i
/ 2] |= v
<< (4 * (1 - (i
% 2)));
2039 obfuscate_bitmap(bmp
, wh
, TRUE
);
2041 memset(state
->mines
, 0, wh
);
2042 for (i
= 0; i
< wh
; i
++) {
2043 if (bmp
[i
/ 8] & (0x80 >> (i
% 8)))
2044 state
->mines
[i
] = 1;
2047 state
->grid
= snewn(wh
, char);
2048 memset(state
->grid
, -2, wh
);
2050 ret
= open_square(state
, x
, y
);
2052 * FIXME: This shouldn't be an assert. Perhaps we actually
2053 * ought to check it in validate_params! Alternatively, we can
2054 * remove the assert completely and actually permit a game
2055 * description to start you off dead.
2062 static game_state
*dup_game(game_state
*state
)
2064 game_state
*ret
= snew(game_state
);
2069 ret
->dead
= state
->dead
;
2070 ret
->won
= state
->won
;
2071 ret
->mines
= snewn(ret
->w
* ret
->h
, char);
2072 memcpy(ret
->mines
, state
->mines
, ret
->w
* ret
->h
);
2073 ret
->grid
= snewn(ret
->w
* ret
->h
, char);
2074 memcpy(ret
->grid
, state
->grid
, ret
->w
* ret
->h
);
2079 static void free_game(game_state
*state
)
2081 sfree(state
->mines
);
2086 static game_state
*solve_game(game_state
*state
, game_aux_info
*aux
,
2092 static char *game_text_format(game_state
*state
)
2098 int hx
, hy
, hradius
; /* for mouse-down highlights */
2102 static game_ui
*new_ui(game_state
*state
)
2104 game_ui
*ui
= snew(game_ui
);
2105 ui
->hx
= ui
->hy
= -1;
2107 ui
->flash_is_death
= FALSE
; /* *shrug* */
2111 static void free_ui(game_ui
*ui
)
2116 static game_state
*make_move(game_state
*from
, game_ui
*ui
, int x
, int y
,
2122 if (from
->dead
|| from
->won
)
2123 return NULL
; /* no further moves permitted */
2125 if (!IS_MOUSE_DOWN(button
) && !IS_MOUSE_DRAG(button
) &&
2126 !IS_MOUSE_RELEASE(button
))
2131 if (cx
< 0 || cx
>= from
->w
|| cy
< 0 || cy
> from
->h
)
2134 if (button
== LEFT_BUTTON
|| button
== LEFT_DRAG
) {
2136 * Mouse-downs and mouse-drags just cause highlighting
2141 ui
->hradius
= (from
->grid
[cy
*from
->w
+cx
] >= 0 ?
1 : 0);
2145 if (button
== RIGHT_BUTTON
) {
2147 * Right-clicking only works on a covered square, and it
2148 * toggles between -1 (marked as mine) and -2 (not marked
2151 * FIXME: question marks.
2153 if (from
->grid
[cy
* from
->w
+ cx
] != -2 &&
2154 from
->grid
[cy
* from
->w
+ cx
] != -1)
2157 ret
= dup_game(from
);
2158 ret
->grid
[cy
* from
->w
+ cx
] ^= (-2 ^ -1);
2163 if (button
== LEFT_RELEASE
) {
2164 ui
->hx
= ui
->hy
= -1;
2168 * At this stage we must never return NULL: we have adjusted
2169 * the ui, so at worst we return `from'.
2173 * Left-clicking on a covered square opens a tile. Not
2174 * permitted if the tile is marked as a mine, for safety.
2175 * (Unmark it and _then_ open it.)
2177 if (from
->grid
[cy
* from
->w
+ cx
] == -2 ||
2178 from
->grid
[cy
* from
->w
+ cx
] == -3) {
2179 ret
= dup_game(from
);
2180 open_square(ret
, cx
, cy
);
2185 * Left-clicking on an uncovered tile: first we check to see if
2186 * the number of mine markers surrounding the tile is equal to
2187 * its mine count, and if so then we open all other surrounding
2190 if (from
->grid
[cy
* from
->w
+ cx
] > 0) {
2193 /* Count mine markers. */
2195 for (dy
= -1; dy
<= +1; dy
++)
2196 for (dx
= -1; dx
<= +1; dx
++)
2197 if (cx
+dx
>= 0 && cx
+dx
< from
->w
&&
2198 cy
+dy
>= 0 && cy
+dy
< from
->h
) {
2199 if (from
->grid
[(cy
+dy
)*from
->w
+(cx
+dx
)] == -1)
2203 if (n
== from
->grid
[cy
* from
->w
+ cx
]) {
2204 ret
= dup_game(from
);
2205 for (dy
= -1; dy
<= +1; dy
++)
2206 for (dx
= -1; dx
<= +1; dx
++)
2207 if (cx
+dx
>= 0 && cx
+dx
< ret
->w
&&
2208 cy
+dy
>= 0 && cy
+dy
< ret
->h
&&
2209 (ret
->grid
[(cy
+dy
)*ret
->w
+(cx
+dx
)] == -2 ||
2210 ret
->grid
[(cy
+dy
)*ret
->w
+(cx
+dx
)] == -3))
2211 open_square(ret
, cx
+dx
, cy
+dy
);
2222 /* ----------------------------------------------------------------------
2226 struct game_drawstate
{
2230 * Items in this `grid' array have all the same values as in
2231 * the game_state grid, and in addition:
2233 * - -10 means the tile was drawn `specially' as a result of a
2234 * flash, so it will always need redrawing.
2236 * - -22 and -23 mean the tile is highlighted for a possible
2241 static void game_size(game_params
*params
, int *x
, int *y
)
2243 *x
= BORDER
* 2 + TILE_SIZE
* params
->w
;
2244 *y
= BORDER
* 2 + TILE_SIZE
* params
->h
;
2247 static float *game_colours(frontend
*fe
, game_state
*state
, int *ncolours
)
2249 float *ret
= snewn(3 * NCOLOURS
, float);
2251 frontend_default_colour(fe
, &ret
[COL_BACKGROUND
* 3]);
2253 ret
[COL_1
* 3 + 0] = 0.0F
;
2254 ret
[COL_1
* 3 + 1] = 0.0F
;
2255 ret
[COL_1
* 3 + 2] = 1.0F
;
2257 ret
[COL_2
* 3 + 0] = 0.0F
;
2258 ret
[COL_2
* 3 + 1] = 0.5F
;
2259 ret
[COL_2
* 3 + 2] = 0.0F
;
2261 ret
[COL_3
* 3 + 0] = 1.0F
;
2262 ret
[COL_3
* 3 + 1] = 0.0F
;
2263 ret
[COL_3
* 3 + 2] = 0.0F
;
2265 ret
[COL_4
* 3 + 0] = 0.0F
;
2266 ret
[COL_4
* 3 + 1] = 0.0F
;
2267 ret
[COL_4
* 3 + 2] = 0.5F
;
2269 ret
[COL_5
* 3 + 0] = 0.5F
;
2270 ret
[COL_5
* 3 + 1] = 0.0F
;
2271 ret
[COL_5
* 3 + 2] = 0.0F
;
2273 ret
[COL_6
* 3 + 0] = 0.0F
;
2274 ret
[COL_6
* 3 + 1] = 0.5F
;
2275 ret
[COL_6
* 3 + 2] = 0.5F
;
2277 ret
[COL_7
* 3 + 0] = 0.0F
;
2278 ret
[COL_7
* 3 + 1] = 0.0F
;
2279 ret
[COL_7
* 3 + 2] = 0.0F
;
2281 ret
[COL_8
* 3 + 0] = 0.5F
;
2282 ret
[COL_8
* 3 + 1] = 0.5F
;
2283 ret
[COL_8
* 3 + 2] = 0.5F
;
2285 ret
[COL_MINE
* 3 + 0] = 0.0F
;
2286 ret
[COL_MINE
* 3 + 1] = 0.0F
;
2287 ret
[COL_MINE
* 3 + 2] = 0.0F
;
2289 ret
[COL_BANG
* 3 + 0] = 1.0F
;
2290 ret
[COL_BANG
* 3 + 1] = 0.0F
;
2291 ret
[COL_BANG
* 3 + 2] = 0.0F
;
2293 ret
[COL_CROSS
* 3 + 0] = 1.0F
;
2294 ret
[COL_CROSS
* 3 + 1] = 0.0F
;
2295 ret
[COL_CROSS
* 3 + 2] = 0.0F
;
2297 ret
[COL_FLAG
* 3 + 0] = 1.0F
;
2298 ret
[COL_FLAG
* 3 + 1] = 0.0F
;
2299 ret
[COL_FLAG
* 3 + 2] = 0.0F
;
2301 ret
[COL_FLAGBASE
* 3 + 0] = 0.0F
;
2302 ret
[COL_FLAGBASE
* 3 + 1] = 0.0F
;
2303 ret
[COL_FLAGBASE
* 3 + 2] = 0.0F
;
2305 ret
[COL_QUERY
* 3 + 0] = 0.0F
;
2306 ret
[COL_QUERY
* 3 + 1] = 0.0F
;
2307 ret
[COL_QUERY
* 3 + 2] = 0.0F
;
2309 ret
[COL_HIGHLIGHT
* 3 + 0] = 1.0F
;
2310 ret
[COL_HIGHLIGHT
* 3 + 1] = 1.0F
;
2311 ret
[COL_HIGHLIGHT
* 3 + 2] = 1.0F
;
2313 ret
[COL_LOWLIGHT
* 3 + 0] = ret
[COL_BACKGROUND
* 3 + 0] * 2.0 / 3.0;
2314 ret
[COL_LOWLIGHT
* 3 + 1] = ret
[COL_BACKGROUND
* 3 + 1] * 2.0 / 3.0;
2315 ret
[COL_LOWLIGHT
* 3 + 2] = ret
[COL_BACKGROUND
* 3 + 2] * 2.0 / 3.0;
2317 *ncolours
= NCOLOURS
;
2321 static game_drawstate
*game_new_drawstate(game_state
*state
)
2323 struct game_drawstate
*ds
= snew(struct game_drawstate
);
2327 ds
->started
= FALSE
;
2328 ds
->grid
= snewn(ds
->w
* ds
->h
, char);
2330 memset(ds
->grid
, -99, ds
->w
* ds
->h
);
2335 static void game_free_drawstate(game_drawstate
*ds
)
2341 static void draw_tile(frontend
*fe
, int x
, int y
, int v
, int bg
)
2347 if (v
== -22 || v
== -23) {
2351 * Omit the highlights in this case.
2353 draw_rect(fe
, x
, y
, TILE_SIZE
, TILE_SIZE
, bg
);
2354 draw_line(fe
, x
, y
, x
+ TILE_SIZE
- 1, y
, COL_LOWLIGHT
);
2355 draw_line(fe
, x
, y
, x
, y
+ TILE_SIZE
- 1, COL_LOWLIGHT
);
2358 * Draw highlights to indicate the square is covered.
2360 coords
[0] = x
+ TILE_SIZE
- 1;
2361 coords
[1] = y
+ TILE_SIZE
- 1;
2362 coords
[2] = x
+ TILE_SIZE
- 1;
2365 coords
[5] = y
+ TILE_SIZE
- 1;
2366 draw_polygon(fe
, coords
, 3, TRUE
, COL_LOWLIGHT
^ hl
);
2367 draw_polygon(fe
, coords
, 3, FALSE
, COL_LOWLIGHT
^ hl
);
2371 draw_polygon(fe
, coords
, 3, TRUE
, COL_HIGHLIGHT
^ hl
);
2372 draw_polygon(fe
, coords
, 3, FALSE
, COL_HIGHLIGHT
^ hl
);
2374 draw_rect(fe
, x
+ HIGHLIGHT_WIDTH
, y
+ HIGHLIGHT_WIDTH
,
2375 TILE_SIZE
- 2*HIGHLIGHT_WIDTH
, TILE_SIZE
- 2*HIGHLIGHT_WIDTH
,
2383 #define SETCOORD(n, dx, dy) do { \
2384 coords[(n)*2+0] = x + TILE_SIZE * (dx); \
2385 coords[(n)*2+1] = y + TILE_SIZE * (dy); \
2387 SETCOORD(0, 0.6, 0.35);
2388 SETCOORD(1, 0.6, 0.7);
2389 SETCOORD(2, 0.8, 0.8);
2390 SETCOORD(3, 0.25, 0.8);
2391 SETCOORD(4, 0.55, 0.7);
2392 SETCOORD(5, 0.55, 0.35);
2393 draw_polygon(fe
, coords
, 6, TRUE
, COL_FLAGBASE
);
2394 draw_polygon(fe
, coords
, 6, FALSE
, COL_FLAGBASE
);
2396 SETCOORD(0, 0.6, 0.2);
2397 SETCOORD(1, 0.6, 0.5);
2398 SETCOORD(2, 0.2, 0.35);
2399 draw_polygon(fe
, coords
, 3, TRUE
, COL_FLAG
);
2400 draw_polygon(fe
, coords
, 3, FALSE
, COL_FLAG
);
2403 } else if (v
== -3) {
2405 * Draw a question mark.
2407 draw_text(fe
, x
+ TILE_SIZE
/ 2, y
+ TILE_SIZE
/ 2,
2408 FONT_VARIABLE
, TILE_SIZE
* 6 / 8,
2409 ALIGN_VCENTRE
| ALIGN_HCENTRE
,
2414 * Clear the square to the background colour, and draw thin
2415 * grid lines along the top and left.
2417 * Exception is that for value 65 (mine we've just trodden
2418 * on), we clear the square to COL_BANG.
2420 draw_rect(fe
, x
, y
, TILE_SIZE
, TILE_SIZE
,
2421 (v
== 65 ? COL_BANG
: bg
));
2422 draw_line(fe
, x
, y
, x
+ TILE_SIZE
- 1, y
, COL_LOWLIGHT
);
2423 draw_line(fe
, x
, y
, x
, y
+ TILE_SIZE
- 1, COL_LOWLIGHT
);
2425 if (v
> 0 && v
<= 8) {
2432 draw_text(fe
, x
+ TILE_SIZE
/ 2, y
+ TILE_SIZE
/ 2,
2433 FONT_VARIABLE
, TILE_SIZE
* 7 / 8,
2434 ALIGN_VCENTRE
| ALIGN_HCENTRE
,
2435 (COL_1
- 1) + v
, str
);
2437 } else if (v
>= 64) {
2441 * FIXME: this could be done better!
2444 draw_text(fe
, x
+ TILE_SIZE
/ 2, y
+ TILE_SIZE
/ 2,
2445 FONT_VARIABLE
, TILE_SIZE
* 7 / 8,
2446 ALIGN_VCENTRE
| ALIGN_HCENTRE
,
2450 int cx
= x
+ TILE_SIZE
/ 2;
2451 int cy
= y
+ TILE_SIZE
/ 2;
2452 int r
= TILE_SIZE
/ 2 - 3;
2454 int xdx
= 1, xdy
= 0, ydx
= 0, ydy
= 1;
2457 for (i
= 0; i
< 4*5*2; i
+= 5*2) {
2458 coords
[i
+2*0+0] = cx
- r
/6*xdx
+ r
*4/5*ydx
;
2459 coords
[i
+2*0+1] = cy
- r
/6*xdy
+ r
*4/5*ydy
;
2460 coords
[i
+2*1+0] = cx
- r
/6*xdx
+ r
*ydx
;
2461 coords
[i
+2*1+1] = cy
- r
/6*xdy
+ r
*ydy
;
2462 coords
[i
+2*2+0] = cx
+ r
/6*xdx
+ r
*ydx
;
2463 coords
[i
+2*2+1] = cy
+ r
/6*xdy
+ r
*ydy
;
2464 coords
[i
+2*3+0] = cx
+ r
/6*xdx
+ r
*4/5*ydx
;
2465 coords
[i
+2*3+1] = cy
+ r
/6*xdy
+ r
*4/5*ydy
;
2466 coords
[i
+2*4+0] = cx
+ r
*3/5*xdx
+ r
*3/5*ydx
;
2467 coords
[i
+2*4+1] = cy
+ r
*3/5*xdy
+ r
*3/5*ydy
;
2477 draw_polygon(fe
, coords
, 5*4, TRUE
, COL_MINE
);
2478 draw_polygon(fe
, coords
, 5*4, FALSE
, COL_MINE
);
2480 draw_rect(fe
, cx
-r
/3, cy
-r
/3, r
/3, r
/4, COL_HIGHLIGHT
);
2486 * Cross through the mine.
2489 for (dx
= -1; dx
<= +1; dx
++) {
2490 draw_line(fe
, x
+ 3 + dx
, y
+ 2,
2491 x
+ TILE_SIZE
- 3 + dx
,
2492 y
+ TILE_SIZE
- 2, COL_CROSS
);
2493 draw_line(fe
, x
+ TILE_SIZE
- 3 + dx
, y
+ 2,
2494 x
+ 3 + dx
, y
+ TILE_SIZE
- 2,
2501 draw_update(fe
, x
, y
, TILE_SIZE
, TILE_SIZE
);
2504 static void game_redraw(frontend
*fe
, game_drawstate
*ds
, game_state
*oldstate
,
2505 game_state
*state
, int dir
, game_ui
*ui
,
2506 float animtime
, float flashtime
)
2509 int mines
, markers
, bg
;
2512 int frame
= (flashtime
/ FLASH_FRAME
);
2514 bg
= (ui
->flash_is_death ? COL_BACKGROUND
: COL_LOWLIGHT
);
2516 bg
= (ui
->flash_is_death ? COL_BANG
: COL_HIGHLIGHT
);
2518 bg
= COL_BACKGROUND
;
2524 TILE_SIZE
* state
->w
+ 2 * BORDER
,
2525 TILE_SIZE
* state
->h
+ 2 * BORDER
, COL_BACKGROUND
);
2526 draw_update(fe
, 0, 0,
2527 TILE_SIZE
* state
->w
+ 2 * BORDER
,
2528 TILE_SIZE
* state
->h
+ 2 * BORDER
);
2531 * Recessed area containing the whole puzzle.
2533 coords
[0] = COORD(state
->w
) + OUTER_HIGHLIGHT_WIDTH
- 1;
2534 coords
[1] = COORD(state
->h
) + OUTER_HIGHLIGHT_WIDTH
- 1;
2535 coords
[2] = COORD(state
->w
) + OUTER_HIGHLIGHT_WIDTH
- 1;
2536 coords
[3] = COORD(0) - OUTER_HIGHLIGHT_WIDTH
;
2537 coords
[4] = COORD(0) - OUTER_HIGHLIGHT_WIDTH
;
2538 coords
[5] = COORD(state
->h
) + OUTER_HIGHLIGHT_WIDTH
- 1;
2539 draw_polygon(fe
, coords
, 3, TRUE
, COL_HIGHLIGHT
);
2540 draw_polygon(fe
, coords
, 3, FALSE
, COL_HIGHLIGHT
);
2542 coords
[1] = COORD(0) - OUTER_HIGHLIGHT_WIDTH
;
2543 coords
[0] = COORD(0) - OUTER_HIGHLIGHT_WIDTH
;
2544 draw_polygon(fe
, coords
, 3, TRUE
, COL_LOWLIGHT
);
2545 draw_polygon(fe
, coords
, 3, FALSE
, COL_LOWLIGHT
);
2551 * Now draw the tiles. Also in this loop, count up the number
2552 * of mines and mine markers.
2554 mines
= markers
= 0;
2555 for (y
= 0; y
< ds
->h
; y
++)
2556 for (x
= 0; x
< ds
->w
; x
++) {
2557 int v
= state
->grid
[y
*ds
->w
+x
];
2561 if (state
->mines
[y
*ds
->w
+x
])
2564 if ((v
== -2 || v
== -3) &&
2565 (abs(x
-ui
->hx
) <= ui
->hradius
&& abs(y
-ui
->hy
) <= ui
->hradius
))
2568 if (ds
->grid
[y
*ds
->w
+x
] != v
|| bg
!= COL_BACKGROUND
) {
2569 draw_tile(fe
, COORD(x
), COORD(y
), v
, bg
);
2570 ds
->grid
[y
*ds
->w
+x
] = (bg
== COL_BACKGROUND ? v
: -10);
2575 * Update the status bar.
2578 char statusbar
[512];
2580 sprintf(statusbar
, "GAME OVER!");
2581 } else if (state
->won
) {
2582 sprintf(statusbar
, "COMPLETED!");
2584 sprintf(statusbar
, "Mines marked: %d / %d", markers
, mines
);
2586 status_bar(fe
, statusbar
);
2590 static float game_anim_length(game_state
*oldstate
, game_state
*newstate
,
2591 int dir
, game_ui
*ui
)
2596 static float game_flash_length(game_state
*oldstate
, game_state
*newstate
,
2597 int dir
, game_ui
*ui
)
2599 if (dir
> 0 && !oldstate
->dead
&& !oldstate
->won
) {
2600 if (newstate
->dead
) {
2601 ui
->flash_is_death
= TRUE
;
2602 return 3 * FLASH_FRAME
;
2604 if (newstate
->won
) {
2605 ui
->flash_is_death
= FALSE
;
2606 return 2 * FLASH_FRAME
;
2612 static int game_wants_statusbar(void)
2618 #define thegame mines
2621 const struct game thegame
= {
2622 "Mines", "games.mines",
2629 TRUE
, game_configure
, custom_params
,
2638 FALSE
, game_text_format
,
2645 game_free_drawstate
,
2649 game_wants_statusbar
,