2 * mines.c: Minesweeper clone with sophisticated grid generation.
6 * - think about configurably supporting question marks. Once,
7 * that is, we've thought about configurability in general!
21 COL_BACKGROUND
, COL_BACKGROUND2
,
22 COL_1
, COL_2
, COL_3
, COL_4
, COL_5
, COL_6
, COL_7
, COL_8
,
23 COL_MINE
, COL_BANG
, COL_CROSS
, COL_FLAG
, COL_FLAGBASE
, COL_QUERY
,
24 COL_HIGHLIGHT
, COL_LOWLIGHT
,
29 #define PREFERRED_TILE_SIZE 20
30 #define TILE_SIZE (ds->tilesize)
31 #define BORDER (TILE_SIZE * 3 / 2)
32 #define HIGHLIGHT_WIDTH (TILE_SIZE / 10)
33 #define OUTER_HIGHLIGHT_WIDTH (BORDER / 10)
34 #define COORD(x) ( (x) * TILE_SIZE + BORDER )
35 #define FROMCOORD(x) ( ((x) - BORDER + TILE_SIZE) / TILE_SIZE - 1 )
37 #define FLASH_FRAME 0.13F
46 * This structure is shared between all the game_states for a
47 * given instance of the puzzle, so we reference-count it.
52 * If we haven't yet actually generated the mine layout, here's
53 * all the data we will need to do so.
57 midend
*me
; /* to give back the new game desc */
61 int w
, h
, n
, dead
, won
;
63 struct mine_layout
*layout
; /* real mine positions */
64 signed char *grid
; /* player knowledge */
66 * Each item in the `grid' array is one of the following values:
68 * - 0 to 8 mean the square is open and has a surrounding mine
71 * - -1 means the square is marked as a mine.
73 * - -2 means the square is unknown.
75 * - -3 means the square is marked with a question mark
76 * (FIXME: do we even want to bother with this?).
78 * - 64 means the square has had a mine revealed when the game
81 * - 65 means the square had a mine revealed and this was the
82 * one the player hits.
84 * - 66 means the square has a crossed-out mine because the
85 * player had incorrectly marked it.
89 static game_params
*default_params(void)
91 game_params
*ret
= snew(game_params
);
100 static const struct game_params mines_presets
[] = {
109 static int game_fetch_preset(int i
, char **name
, game_params
**params
)
114 if (i
< 0 || i
>= lenof(mines_presets
))
117 ret
= snew(game_params
);
118 *ret
= mines_presets
[i
];
120 sprintf(str
, "%dx%d, %d mines", ret
->w
, ret
->h
, ret
->n
);
127 static void free_params(game_params
*params
)
132 static game_params
*dup_params(game_params
*params
)
134 game_params
*ret
= snew(game_params
);
135 *ret
= *params
; /* structure copy */
139 static void decode_params(game_params
*params
, char const *string
)
141 char const *p
= string
;
144 while (*p
&& isdigit((unsigned char)*p
)) p
++;
148 while (*p
&& isdigit((unsigned char)*p
)) p
++;
150 params
->h
= params
->w
;
155 while (*p
&& (*p
== '.' || isdigit((unsigned char)*p
))) p
++;
157 params
->n
= params
->w
* params
->h
/ 10;
163 params
->unique
= FALSE
;
165 p
++; /* skip any other gunk */
169 static char *encode_params(game_params
*params
, int full
)
174 len
= sprintf(ret
, "%dx%d", params
->w
, params
->h
);
176 * Mine count is a generation-time parameter, since it can be
177 * deduced from the mine bitmap!
180 len
+= sprintf(ret
+len
, "n%d", params
->n
);
181 if (full
&& !params
->unique
)
183 assert(len
< lenof(ret
));
189 static config_item
*game_configure(game_params
*params
)
194 ret
= snewn(5, config_item
);
196 ret
[0].name
= "Width";
197 ret
[0].type
= C_STRING
;
198 sprintf(buf
, "%d", params
->w
);
199 ret
[0].sval
= dupstr(buf
);
202 ret
[1].name
= "Height";
203 ret
[1].type
= C_STRING
;
204 sprintf(buf
, "%d", params
->h
);
205 ret
[1].sval
= dupstr(buf
);
208 ret
[2].name
= "Mines";
209 ret
[2].type
= C_STRING
;
210 sprintf(buf
, "%d", params
->n
);
211 ret
[2].sval
= dupstr(buf
);
214 ret
[3].name
= "Ensure solubility";
215 ret
[3].type
= C_BOOLEAN
;
217 ret
[3].ival
= params
->unique
;
227 static game_params
*custom_params(config_item
*cfg
)
229 game_params
*ret
= snew(game_params
);
231 ret
->w
= atoi(cfg
[0].sval
);
232 ret
->h
= atoi(cfg
[1].sval
);
233 ret
->n
= atoi(cfg
[2].sval
);
234 if (strchr(cfg
[2].sval
, '%'))
235 ret
->n
= ret
->n
* (ret
->w
* ret
->h
) / 100;
236 ret
->unique
= cfg
[3].ival
;
241 static char *validate_params(game_params
*params
, int full
)
244 * Lower limit on grid size: each dimension must be at least 3.
245 * 1 is theoretically workable if rather boring, but 2 is a
246 * real problem: there is often _no_ way to generate a uniquely
247 * solvable 2xn Mines grid. You either run into two mines
248 * blocking the way and no idea what's behind them, or one mine
249 * and no way to know which of the two rows it's in. If the
250 * mine count is even you can create a soluble grid by packing
251 * all the mines at one end (so what when you hit a two-mine
252 * wall there are only as many covered squares left as there
253 * are mines); but if it's odd, you are doomed, because you
254 * _have_ to have a gap somewhere which you can't determine the
257 if (full
&& params
->unique
&& (params
->w
<= 2 || params
->h
<= 2))
258 return "Width and height must both be greater than two";
259 if (params
->n
> params
->w
* params
->h
- 9)
260 return "Too many mines for grid size";
263 * FIXME: Need more constraints here. Not sure what the
264 * sensible limits for Minesweeper actually are. The limits
265 * probably ought to change, however, depending on uniqueness.
271 /* ----------------------------------------------------------------------
272 * Minesweeper solver, used to ensure the generated grids are
273 * solvable without having to take risks.
277 * Count the bits in a word. Only needs to cope with 16 bits.
279 static int bitcount16(int inword
)
281 unsigned int word
= inword
;
283 word
= ((word
& 0xAAAA) >> 1) + (word
& 0x5555);
284 word
= ((word
& 0xCCCC) >> 2) + (word
& 0x3333);
285 word
= ((word
& 0xF0F0) >> 4) + (word
& 0x0F0F);
286 word
= ((word
& 0xFF00) >> 8) + (word
& 0x00FF);
292 * We use a tree234 to store a large number of small localised
293 * sets, each with a mine count. We also keep some of those sets
294 * linked together into a to-do list.
297 short x
, y
, mask
, mines
;
299 struct set
*prev
, *next
;
302 static int setcmp(void *av
, void *bv
)
304 struct set
*a
= (struct set
*)av
;
305 struct set
*b
= (struct set
*)bv
;
309 else if (a
->y
> b
->y
)
311 else if (a
->x
< b
->x
)
313 else if (a
->x
> b
->x
)
315 else if (a
->mask
< b
->mask
)
317 else if (a
->mask
> b
->mask
)
325 struct set
*todo_head
, *todo_tail
;
328 static struct setstore
*ss_new(void)
330 struct setstore
*ss
= snew(struct setstore
);
331 ss
->sets
= newtree234(setcmp
);
332 ss
->todo_head
= ss
->todo_tail
= NULL
;
337 * Take two input sets, in the form (x,y,mask). Munge the first by
338 * taking either its intersection with the second or its difference
339 * with the second. Return the new mask part of the first set.
341 static int setmunge(int x1
, int y1
, int mask1
, int x2
, int y2
, int mask2
,
345 * Adjust the second set so that it has the same x,y
346 * coordinates as the first.
348 if (abs(x2
-x1
) >= 3 || abs(y2
-y1
) >= 3) {
352 mask2
&= ~(4|32|256);
362 mask2
&= ~(64|128|256);
374 * Invert the second set if `diff' is set (we're after A &~ B
375 * rather than A & B).
381 * Now all that's left is a logical AND.
383 return mask1
& mask2
;
386 static void ss_add_todo(struct setstore
*ss
, struct set
*s
)
389 return; /* already on it */
391 #ifdef SOLVER_DIAGNOSTICS
392 printf("adding set on todo list: %d,%d %03x %d\n",
393 s
->x
, s
->y
, s
->mask
, s
->mines
);
396 s
->prev
= ss
->todo_tail
;
406 static void ss_add(struct setstore
*ss
, int x
, int y
, int mask
, int mines
)
413 * Normalise so that x and y are genuinely the bounding
416 while (!(mask
& (1|8|64)))
418 while (!(mask
& (1|2|4)))
422 * Create a set structure and add it to the tree.
424 s
= snew(struct set
);
430 if (add234(ss
->sets
, s
) != s
) {
432 * This set already existed! Free it and return.
439 * We've added a new set to the tree, so put it on the todo
445 static void ss_remove(struct setstore
*ss
, struct set
*s
)
447 struct set
*next
= s
->next
, *prev
= s
->prev
;
449 #ifdef SOLVER_DIAGNOSTICS
450 printf("removing set %d,%d %03x\n", s
->x
, s
->y
, s
->mask
);
453 * Remove s from the todo list.
457 else if (s
== ss
->todo_head
)
458 ss
->todo_head
= next
;
462 else if (s
== ss
->todo_tail
)
463 ss
->todo_tail
= prev
;
468 * Remove s from the tree.
473 * Destroy the actual set structure.
479 * Return a dynamically allocated list of all the sets which
480 * overlap a provided input set.
482 static struct set
**ss_overlap(struct setstore
*ss
, int x
, int y
, int mask
)
484 struct set
**ret
= NULL
;
485 int nret
= 0, retsize
= 0;
488 for (xx
= x
-3; xx
< x
+3; xx
++)
489 for (yy
= y
-3; yy
< y
+3; yy
++) {
494 * Find the first set with these top left coordinates.
500 if (findrelpos234(ss
->sets
, &stmp
, NULL
, REL234_GE
, &pos
)) {
501 while ((s
= index234(ss
->sets
, pos
)) != NULL
&&
502 s
->x
== xx
&& s
->y
== yy
) {
504 * This set potentially overlaps the input one.
505 * Compute the intersection to see if they
506 * really overlap, and add it to the list if
509 if (setmunge(x
, y
, mask
, s
->x
, s
->y
, s
->mask
, FALSE
)) {
511 * There's an overlap.
513 if (nret
>= retsize
) {
515 ret
= sresize(ret
, retsize
, struct set
*);
525 ret
= sresize(ret
, nret
+1, struct set
*);
532 * Get an element from the head of the set todo list.
534 static struct set
*ss_todo(struct setstore
*ss
)
537 struct set
*ret
= ss
->todo_head
;
538 ss
->todo_head
= ret
->next
;
540 ss
->todo_head
->prev
= NULL
;
542 ss
->todo_tail
= NULL
;
543 ret
->next
= ret
->prev
= NULL
;
556 static void std_add(struct squaretodo
*std
, int i
)
559 std
->next
[std
->tail
] = i
;
566 typedef int (*open_cb
)(void *, int, int);
568 static void known_squares(int w
, int h
, struct squaretodo
*std
,
570 open_cb open
, 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
637 typedef struct perturbations
*(*perturb_cb
) (void *, signed char *, int, int, int);
639 static int minesolve(int w
, int h
, int n
, signed char *grid
,
642 void *ctx
, random_state
*rs
)
644 struct setstore
*ss
= ss_new();
646 struct squaretodo astd
, *std
= &astd
;
651 * Set up a linked list of squares with known contents, so that
652 * we can process them one by one.
654 std
->next
= snewn(w
*h
, int);
655 std
->head
= std
->tail
= -1;
658 * Initialise that list with all known squares in the input
661 for (y
= 0; y
< h
; y
++) {
662 for (x
= 0; x
< w
; x
++) {
670 * Main deductive loop.
673 int done_something
= FALSE
;
677 * If there are any known squares on the todo list, process
678 * them and construct a set for each.
680 while (std
->head
!= -1) {
682 #ifdef SOLVER_DIAGNOSTICS
683 printf("known square at %d,%d [%d]\n", i
%w
, i
/w
, grid
[i
]);
685 std
->head
= std
->next
[i
];
693 int dx
, dy
, mines
, bit
, val
;
694 #ifdef SOLVER_DIAGNOSTICS
695 printf("creating set around this square\n");
698 * Empty square. Construct the set of non-known squares
699 * around this one, and determine its mine count.
704 for (dy
= -1; dy
<= +1; dy
++) {
705 for (dx
= -1; dx
<= +1; dx
++) {
706 #ifdef SOLVER_DIAGNOSTICS
707 printf("grid %d,%d = %d\n", x
+dx
, y
+dy
, grid
[i
+dy
*w
+dx
]);
709 if (x
+dx
< 0 || x
+dx
>= w
|| y
+dy
< 0 || y
+dy
>= h
)
710 /* ignore this one */;
711 else if (grid
[i
+dy
*w
+dx
] == -1)
713 else if (grid
[i
+dy
*w
+dx
] == -2)
719 ss_add(ss
, x
-1, y
-1, val
, mines
);
723 * Now, whether the square is empty or full, we must
724 * find any set which contains it and replace it with
725 * one which does not.
728 #ifdef SOLVER_DIAGNOSTICS
729 printf("finding sets containing known square %d,%d\n", x
, y
);
731 list
= ss_overlap(ss
, x
, y
, 1);
733 for (j
= 0; list
[j
]; j
++) {
734 int newmask
, newmines
;
739 * Compute the mask for this set minus the
740 * newly known square.
742 newmask
= setmunge(s
->x
, s
->y
, s
->mask
, x
, y
, 1, TRUE
);
745 * Compute the new mine count.
747 newmines
= s
->mines
- (grid
[i
] == -1);
750 * Insert the new set into the collection,
751 * unless it's been whittled right down to
755 ss_add(ss
, s
->x
, s
->y
, newmask
, newmines
);
758 * Destroy the old one; it is actually obsolete.
767 * Marking a fresh square as known certainly counts as
770 done_something
= TRUE
;
774 * Now pick a set off the to-do list and attempt deductions
777 if ((s
= ss_todo(ss
)) != NULL
) {
779 #ifdef SOLVER_DIAGNOSTICS
780 printf("set to do: %d,%d %03x %d\n", s
->x
, s
->y
, s
->mask
, s
->mines
);
783 * Firstly, see if this set has a mine count of zero or
784 * of its own cardinality.
786 if (s
->mines
== 0 || s
->mines
== bitcount16(s
->mask
)) {
788 * If so, we can immediately mark all the squares
789 * in the set as known.
791 #ifdef SOLVER_DIAGNOSTICS
794 known_squares(w
, h
, std
, grid
, open
, ctx
,
795 s
->x
, s
->y
, s
->mask
, (s
->mines
!= 0));
798 * Having done that, we need do nothing further
799 * with this set; marking all the squares in it as
800 * known will eventually eliminate it, and will
801 * also permit further deductions about anything
808 * Failing that, we now search through all the sets
809 * which overlap this one.
811 list
= ss_overlap(ss
, s
->x
, s
->y
, s
->mask
);
813 for (j
= 0; list
[j
]; j
++) {
814 struct set
*s2
= list
[j
];
815 int swing
, s2wing
, swc
, s2wc
;
818 * Find the non-overlapping parts s2-s and s-s2,
819 * and their cardinalities.
821 * I'm going to refer to these parts as `wings'
822 * surrounding the central part common to both
823 * sets. The `s wing' is s-s2; the `s2 wing' is
826 swing
= setmunge(s
->x
, s
->y
, s
->mask
, s2
->x
, s2
->y
, s2
->mask
,
828 s2wing
= setmunge(s2
->x
, s2
->y
, s2
->mask
, s
->x
, s
->y
, s
->mask
,
830 swc
= bitcount16(swing
);
831 s2wc
= bitcount16(s2wing
);
834 * If one set has more mines than the other, and
835 * the number of extra mines is equal to the
836 * cardinality of that set's wing, then we can mark
837 * every square in the wing as a known mine, and
838 * every square in the other wing as known clear.
840 if (swc
== s
->mines
- s2
->mines
||
841 s2wc
== s2
->mines
- s
->mines
) {
842 known_squares(w
, h
, std
, grid
, open
, ctx
,
844 (swc
== s
->mines
- s2
->mines
));
845 known_squares(w
, h
, std
, grid
, open
, ctx
,
846 s2
->x
, s2
->y
, s2wing
,
847 (s2wc
== s2
->mines
- s
->mines
));
852 * Failing that, see if one set is a subset of the
853 * other. If so, we can divide up the mine count of
854 * the larger set between the smaller set and its
855 * complement, even if neither smaller set ends up
856 * being immediately clearable.
858 if (swc
== 0 && s2wc
!= 0) {
859 /* s is a subset of s2. */
860 assert(s2
->mines
> s
->mines
);
861 ss_add(ss
, s2
->x
, s2
->y
, s2wing
, s2
->mines
- s
->mines
);
862 } else if (s2wc
== 0 && swc
!= 0) {
863 /* s2 is a subset of s. */
864 assert(s
->mines
> s2
->mines
);
865 ss_add(ss
, s
->x
, s
->y
, swing
, s
->mines
- s2
->mines
);
872 * In this situation we have definitely done
873 * _something_, even if it's only reducing the size of
876 done_something
= TRUE
;
879 * We have nothing left on our todo list, which means
880 * all localised deductions have failed. Our next step
881 * is to resort to global deduction based on the total
882 * mine count. This is computationally expensive
883 * compared to any of the above deductions, which is
884 * why we only ever do it when all else fails, so that
885 * hopefully it won't have to happen too often.
887 * If you pass n<0 into this solver, that informs it
888 * that you do not know the total mine count, so it
889 * won't even attempt these deductions.
892 int minesleft
, squaresleft
;
893 int nsets
, setused
[10], cursor
;
896 * Start by scanning the current grid state to work out
897 * how many unknown squares we still have, and how many
898 * mines are to be placed in them.
902 for (i
= 0; i
< w
*h
; i
++) {
905 else if (grid
[i
] == -2)
909 #ifdef SOLVER_DIAGNOSTICS
910 printf("global deduction time: squaresleft=%d minesleft=%d\n",
911 squaresleft
, minesleft
);
912 for (y
= 0; y
< h
; y
++) {
913 for (x
= 0; x
< w
; x
++) {
929 * If there _are_ no unknown squares, we have actually
932 if (squaresleft
== 0) {
933 assert(minesleft
== 0);
938 * First really simple case: if there are no more mines
939 * left, or if there are exactly as many mines left as
940 * squares to play them in, then it's all easy.
942 if (minesleft
== 0 || minesleft
== squaresleft
) {
943 for (i
= 0; i
< w
*h
; i
++)
945 known_squares(w
, h
, std
, grid
, open
, ctx
,
946 i
% w
, i
/ w
, 1, minesleft
!= 0);
947 continue; /* now go back to main deductive loop */
951 * Failing that, we have to do some _real_ work.
952 * Ideally what we do here is to try every single
953 * combination of the currently available sets, in an
954 * attempt to find a disjoint union (i.e. a set of
955 * squares with a known mine count between them) such
956 * that the remaining unknown squares _not_ contained
957 * in that union either contain no mines or are all
960 * Actually enumerating all 2^n possibilities will get
961 * a bit slow for large n, so I artificially cap this
962 * recursion at n=10 to avoid too much pain.
964 nsets
= count234(ss
->sets
);
965 if (nsets
<= lenof(setused
)) {
967 * Doing this with actual recursive function calls
968 * would get fiddly because a load of local
969 * variables from this function would have to be
970 * passed down through the recursion. So instead
971 * I'm going to use a virtual recursion within this
972 * function. The way this works is:
974 * - we have an array `setused', such that
975 * setused[n] is 0 or 1 depending on whether set
976 * n is currently in the union we are
979 * - we have a value `cursor' which indicates how
980 * much of `setused' we have so far filled in.
981 * It's conceptually the recursion depth.
983 * We begin by setting `cursor' to zero. Then:
985 * - if cursor can advance, we advance it by one.
986 * We set the value in `setused' that it went
987 * past to 1 if that set is disjoint from
988 * anything else currently in `setused', or to 0
991 * - If cursor cannot advance because it has
992 * reached the end of the setused list, then we
993 * have a maximal disjoint union. Check to see
994 * whether its mine count has any useful
995 * properties. If so, mark all the squares not
996 * in the union as known and terminate.
998 * - If cursor has reached the end of setused and
999 * the algorithm _hasn't_ terminated, back
1000 * cursor up to the nearest 1, turn it into a 0
1001 * and advance cursor just past it.
1003 * - If we attempt to back up to the nearest 1 and
1004 * there isn't one at all, then we have gone
1005 * through all disjoint unions of sets in the
1006 * list and none of them has been helpful, so we
1009 struct set
*sets
[lenof(setused
)];
1010 for (i
= 0; i
< nsets
; i
++)
1011 sets
[i
] = index234(ss
->sets
, i
);
1016 if (cursor
< nsets
) {
1019 /* See if any existing set overlaps this one. */
1020 for (i
= 0; i
< cursor
; i
++)
1022 setmunge(sets
[cursor
]->x
,
1025 sets
[i
]->x
, sets
[i
]->y
, sets
[i
]->mask
,
1033 * We're adding this set to our union,
1034 * so adjust minesleft and squaresleft
1037 minesleft
-= sets
[cursor
]->mines
;
1038 squaresleft
-= bitcount16(sets
[cursor
]->mask
);
1041 setused
[cursor
++] = ok
;
1043 #ifdef SOLVER_DIAGNOSTICS
1044 printf("trying a set combination with %d %d\n",
1045 squaresleft
, minesleft
);
1046 #endif /* SOLVER_DIAGNOSTICS */
1049 * We've reached the end. See if we've got
1050 * anything interesting.
1052 if (squaresleft
> 0 &&
1053 (minesleft
== 0 || minesleft
== squaresleft
)) {
1055 * We have! There is at least one
1056 * square not contained within the set
1057 * union we've just found, and we can
1058 * deduce that either all such squares
1059 * are mines or all are not (depending
1060 * on whether minesleft==0). So now all
1061 * we have to do is actually go through
1062 * the grid, find those squares, and
1065 for (i
= 0; i
< w
*h
; i
++)
1066 if (grid
[i
] == -2) {
1070 for (j
= 0; j
< nsets
; j
++)
1072 setmunge(sets
[j
]->x
, sets
[j
]->y
,
1073 sets
[j
]->mask
, x
, y
, 1,
1079 known_squares(w
, h
, std
, grid
,
1081 x
, y
, 1, minesleft
!= 0);
1084 done_something
= TRUE
;
1085 break; /* return to main deductive loop */
1089 * If we reach here, then this union hasn't
1090 * done us any good, so move on to the
1091 * next. Backtrack cursor to the nearest 1,
1092 * change it to a 0 and continue.
1094 while (--cursor
>= 0 && !setused
[cursor
]);
1096 assert(setused
[cursor
]);
1099 * We're removing this set from our
1100 * union, so re-increment minesleft and
1103 minesleft
+= sets
[cursor
]->mines
;
1104 squaresleft
+= bitcount16(sets
[cursor
]->mask
);
1106 setused
[cursor
++] = 0;
1109 * We've backtracked all the way to the
1110 * start without finding a single 1,
1111 * which means that our virtual
1112 * recursion is complete and nothing
1127 #ifdef SOLVER_DIAGNOSTICS
1129 * Dump the current known state of the grid.
1131 printf("solver ran out of steam, ret=%d, grid:\n", nperturbs
);
1132 for (y
= 0; y
< h
; y
++) {
1133 for (x
= 0; x
< w
; x
++) {
1134 int v
= grid
[y
*w
+x
];
1150 for (i
= 0; (s
= index234(ss
->sets
, i
)) != NULL
; i
++)
1151 printf("remaining set: %d,%d %03x %d\n", s
->x
, s
->y
, s
->mask
, s
->mines
);
1156 * Now we really are at our wits' end as far as solving
1157 * this grid goes. Our only remaining option is to call
1158 * a perturb function and ask it to modify the grid to
1162 struct perturbations
*ret
;
1168 * Choose a set at random from the current selection,
1169 * and ask the perturb function to either fill or empty
1172 * If we have no sets at all, we must give up.
1174 if (count234(ss
->sets
) == 0) {
1175 #ifdef SOLVER_DIAGNOSTICS
1176 printf("perturbing on entire unknown set\n");
1178 ret
= perturb(ctx
, grid
, 0, 0, 0);
1180 s
= index234(ss
->sets
, random_upto(rs
, count234(ss
->sets
)));
1181 #ifdef SOLVER_DIAGNOSTICS
1182 printf("perturbing on set %d,%d %03x\n", s
->x
, s
->y
, s
->mask
);
1184 ret
= perturb(ctx
, grid
, s
->x
, s
->y
, s
->mask
);
1188 assert(ret
->n
> 0); /* otherwise should have been NULL */
1191 * A number of squares have been fiddled with, and
1192 * the returned structure tells us which. Adjust
1193 * the mine count in any set which overlaps one of
1194 * those squares, and put them back on the to-do
1195 * list. Also, if the square itself is marked as a
1196 * known non-mine, put it back on the squares-to-do
1199 for (i
= 0; i
< ret
->n
; i
++) {
1200 #ifdef SOLVER_DIAGNOSTICS
1201 printf("perturbation %s mine at %d,%d\n",
1202 ret
->changes
[i
].delta
> 0 ?
"added" : "removed",
1203 ret
->changes
[i
].x
, ret
->changes
[i
].y
);
1206 if (ret
->changes
[i
].delta
< 0 &&
1207 grid
[ret
->changes
[i
].y
*w
+ret
->changes
[i
].x
] != -2) {
1208 std_add(std
, ret
->changes
[i
].y
*w
+ret
->changes
[i
].x
);
1211 list
= ss_overlap(ss
,
1212 ret
->changes
[i
].x
, ret
->changes
[i
].y
, 1);
1214 for (j
= 0; list
[j
]; j
++) {
1215 list
[j
]->mines
+= ret
->changes
[i
].delta
;
1216 ss_add_todo(ss
, list
[j
]);
1223 * Now free the returned data.
1225 sfree(ret
->changes
);
1228 #ifdef SOLVER_DIAGNOSTICS
1230 * Dump the current known state of the grid.
1232 printf("state after perturbation:\n");
1233 for (y
= 0; y
< h
; y
++) {
1234 for (x
= 0; x
< w
; x
++) {
1235 int v
= grid
[y
*w
+x
];
1251 for (i
= 0; (s
= index234(ss
->sets
, i
)) != NULL
; i
++)
1252 printf("remaining set: %d,%d %03x %d\n", s
->x
, s
->y
, s
->mask
, s
->mines
);
1257 * And now we can go back round the deductive loop.
1264 * If we get here, even that didn't work (either we didn't
1265 * have a perturb function or it returned failure), so we
1272 * See if we've got any unknown squares left.
1274 for (y
= 0; y
< h
; y
++)
1275 for (x
= 0; x
< w
; x
++)
1276 if (grid
[y
*w
+x
] == -2) {
1277 nperturbs
= -1; /* failed to complete */
1282 * Free the set list and square-todo list.
1286 while ((s
= delpos234(ss
->sets
, 0)) != NULL
)
1288 freetree234(ss
->sets
);
1296 /* ----------------------------------------------------------------------
1297 * Grid generator which uses the above solver.
1304 int allow_big_perturbs
;
1308 static int mineopen(void *vctx
, int x
, int y
)
1310 struct minectx
*ctx
= (struct minectx
*)vctx
;
1313 assert(x
>= 0 && x
< ctx
->w
&& y
>= 0 && y
< ctx
->h
);
1314 if (ctx
->grid
[y
* ctx
->w
+ x
])
1315 return -1; /* *bang* */
1318 for (i
= -1; i
<= +1; i
++) {
1319 if (x
+ i
< 0 || x
+ i
>= ctx
->w
)
1321 for (j
= -1; j
<= +1; j
++) {
1322 if (y
+ j
< 0 || y
+ j
>= ctx
->h
)
1324 if (i
== 0 && j
== 0)
1326 if (ctx
->grid
[(y
+j
) * ctx
->w
+ (x
+i
)])
1334 /* Structure used internally to mineperturb(). */
1336 int x
, y
, type
, random
;
1338 static int squarecmp(const void *av
, const void *bv
)
1340 const struct square
*a
= (const struct square
*)av
;
1341 const struct square
*b
= (const struct square
*)bv
;
1342 if (a
->type
< b
->type
)
1344 else if (a
->type
> b
->type
)
1346 else if (a
->random
< b
->random
)
1348 else if (a
->random
> b
->random
)
1350 else if (a
->y
< b
->y
)
1352 else if (a
->y
> b
->y
)
1354 else if (a
->x
< b
->x
)
1356 else if (a
->x
> b
->x
)
1362 * Normally this function is passed an (x,y,mask) set description.
1363 * On occasions, though, there is no _localised_ set being used,
1364 * and the set being perturbed is supposed to be the entirety of
1365 * the unreachable area. This is signified by the special case
1366 * mask==0: in this case, anything labelled -2 in the grid is part
1369 * Allowing perturbation in this special case appears to make it
1370 * guaranteeably possible to generate a workable grid for any mine
1371 * density, but they tend to be a bit boring, with mines packed
1372 * densely into far corners of the grid and the remainder being
1373 * less dense than one might like. Therefore, to improve overall
1374 * grid quality I disable this feature for the first few attempts,
1375 * and fall back to it after no useful grid has been generated.
1377 static struct perturbations
*mineperturb(void *vctx
, signed char *grid
,
1378 int setx
, int sety
, int mask
)
1380 struct minectx
*ctx
= (struct minectx
*)vctx
;
1381 struct square
*sqlist
;
1382 int x
, y
, dx
, dy
, i
, n
, nfull
, nempty
;
1383 struct square
**tofill
, **toempty
, **todo
;
1384 int ntofill
, ntoempty
, ntodo
, dtodo
, dset
;
1385 struct perturbations
*ret
;
1388 if (!mask
&& !ctx
->allow_big_perturbs
)
1392 * Make a list of all the squares in the grid which we can
1393 * possibly use. This list should be in preference order, which
1396 * - first, unknown squares on the boundary of known space
1397 * - next, unknown squares beyond that boundary
1398 * - as a very last resort, known squares, but not within one
1399 * square of the starting position.
1401 * Each of these sections needs to be shuffled independently.
1402 * We do this by preparing list of all squares and then sorting
1403 * it with a random secondary key.
1405 sqlist
= snewn(ctx
->w
* ctx
->h
, struct square
);
1407 for (y
= 0; y
< ctx
->h
; y
++)
1408 for (x
= 0; x
< ctx
->w
; x
++) {
1410 * If this square is too near the starting position,
1411 * don't put it on the list at all.
1413 if (abs(y
- ctx
->sy
) <= 1 && abs(x
- ctx
->sx
) <= 1)
1417 * If this square is in the input set, also don't put
1420 if ((mask
== 0 && grid
[y
*ctx
->w
+x
] == -2) ||
1421 (x
>= setx
&& x
< setx
+ 3 &&
1422 y
>= sety
&& y
< sety
+ 3 &&
1423 mask
& (1 << ((y
-sety
)*3+(x
-setx
)))))
1429 if (grid
[y
*ctx
->w
+x
] != -2) {
1430 sqlist
[n
].type
= 3; /* known square */
1433 * Unknown square. Examine everything around it and
1434 * see if it borders on any known squares. If it
1435 * does, it's class 1, otherwise it's 2.
1440 for (dy
= -1; dy
<= +1; dy
++)
1441 for (dx
= -1; dx
<= +1; dx
++)
1442 if (x
+dx
>= 0 && x
+dx
< ctx
->w
&&
1443 y
+dy
>= 0 && y
+dy
< ctx
->h
&&
1444 grid
[(y
+dy
)*ctx
->w
+(x
+dx
)] != -2) {
1451 * Finally, a random number to cause qsort to
1452 * shuffle within each group.
1454 sqlist
[n
].random
= random_bits(ctx
->rs
, 31);
1459 qsort(sqlist
, n
, sizeof(struct square
), squarecmp
);
1462 * Now count up the number of full and empty squares in the set
1463 * we've been provided.
1467 for (dy
= 0; dy
< 3; dy
++)
1468 for (dx
= 0; dx
< 3; dx
++)
1469 if (mask
& (1 << (dy
*3+dx
))) {
1470 assert(setx
+dx
<= ctx
->w
);
1471 assert(sety
+dy
<= ctx
->h
);
1472 if (ctx
->grid
[(sety
+dy
)*ctx
->w
+(setx
+dx
)])
1478 for (y
= 0; y
< ctx
->h
; y
++)
1479 for (x
= 0; x
< ctx
->w
; x
++)
1480 if (grid
[y
*ctx
->w
+x
] == -2) {
1481 if (ctx
->grid
[y
*ctx
->w
+x
])
1489 * Now go through our sorted list until we find either `nfull'
1490 * empty squares, or `nempty' full squares; these will be
1491 * swapped with the appropriate squares in the set to either
1492 * fill or empty the set while keeping the same number of mines
1495 ntofill
= ntoempty
= 0;
1497 tofill
= snewn(9, struct square
*);
1498 toempty
= snewn(9, struct square
*);
1500 tofill
= snewn(ctx
->w
* ctx
->h
, struct square
*);
1501 toempty
= snewn(ctx
->w
* ctx
->h
, struct square
*);
1503 for (i
= 0; i
< n
; i
++) {
1504 struct square
*sq
= &sqlist
[i
];
1505 if (ctx
->grid
[sq
->y
* ctx
->w
+ sq
->x
])
1506 toempty
[ntoempty
++] = sq
;
1508 tofill
[ntofill
++] = sq
;
1509 if (ntofill
== nfull
|| ntoempty
== nempty
)
1514 * If we haven't found enough empty squares outside the set to
1515 * empty it into _or_ enough full squares outside it to fill it
1516 * up with, we'll have to settle for doing only a partial job.
1517 * In this case we choose to always _fill_ the set (because
1518 * this case will tend to crop up when we're working with very
1519 * high mine densities and the only way to get a solvable grid
1520 * is going to be to pack most of the mines solidly around the
1521 * edges). So now our job is to make a list of the empty
1522 * squares in the set, and shuffle that list so that we fill a
1523 * random selection of them.
1525 if (ntofill
!= nfull
&& ntoempty
!= nempty
) {
1528 assert(ntoempty
!= 0);
1530 setlist
= snewn(ctx
->w
* ctx
->h
, int);
1533 for (dy
= 0; dy
< 3; dy
++)
1534 for (dx
= 0; dx
< 3; dx
++)
1535 if (mask
& (1 << (dy
*3+dx
))) {
1536 assert(setx
+dx
<= ctx
->w
);
1537 assert(sety
+dy
<= ctx
->h
);
1538 if (!ctx
->grid
[(sety
+dy
)*ctx
->w
+(setx
+dx
)])
1539 setlist
[i
++] = (sety
+dy
)*ctx
->w
+(setx
+dx
);
1542 for (y
= 0; y
< ctx
->h
; y
++)
1543 for (x
= 0; x
< ctx
->w
; x
++)
1544 if (grid
[y
*ctx
->w
+x
] == -2) {
1545 if (!ctx
->grid
[y
*ctx
->w
+x
])
1546 setlist
[i
++] = y
*ctx
->w
+x
;
1549 assert(i
> ntoempty
);
1551 * Now pick `ntoempty' items at random from the list.
1553 for (k
= 0; k
< ntoempty
; k
++) {
1554 int index
= k
+ random_upto(ctx
->rs
, i
- k
);
1558 setlist
[k
] = setlist
[index
];
1559 setlist
[index
] = tmp
;
1565 * Now we're pretty much there. We need to either
1566 * (a) put a mine in each of the empty squares in the set, and
1567 * take one out of each square in `toempty'
1568 * (b) take a mine out of each of the full squares in the set,
1569 * and put one in each square in `tofill'
1570 * depending on which one we've found enough squares to do.
1572 * So we start by constructing our list of changes to return to
1573 * the solver, so that it can update its data structures
1574 * efficiently rather than having to rescan the whole grid.
1576 ret
= snew(struct perturbations
);
1577 if (ntofill
== nfull
) {
1585 * (We also fall into this case if we've constructed a
1595 ret
->changes
= snewn(ret
->n
, struct perturbation
);
1596 for (i
= 0; i
< ntodo
; i
++) {
1597 ret
->changes
[i
].x
= todo
[i
]->x
;
1598 ret
->changes
[i
].y
= todo
[i
]->y
;
1599 ret
->changes
[i
].delta
= dtodo
;
1601 /* now i == ntodo */
1604 assert(todo
== toempty
);
1605 for (j
= 0; j
< ntoempty
; j
++) {
1606 ret
->changes
[i
].x
= setlist
[j
] % ctx
->w
;
1607 ret
->changes
[i
].y
= setlist
[j
] / ctx
->w
;
1608 ret
->changes
[i
].delta
= dset
;
1613 for (dy
= 0; dy
< 3; dy
++)
1614 for (dx
= 0; dx
< 3; dx
++)
1615 if (mask
& (1 << (dy
*3+dx
))) {
1616 int currval
= (ctx
->grid
[(sety
+dy
)*ctx
->w
+(setx
+dx
)] ?
+1 : -1);
1617 if (dset
== -currval
) {
1618 ret
->changes
[i
].x
= setx
+ dx
;
1619 ret
->changes
[i
].y
= sety
+ dy
;
1620 ret
->changes
[i
].delta
= dset
;
1625 for (y
= 0; y
< ctx
->h
; y
++)
1626 for (x
= 0; x
< ctx
->w
; x
++)
1627 if (grid
[y
*ctx
->w
+x
] == -2) {
1628 int currval
= (ctx
->grid
[y
*ctx
->w
+x
] ?
+1 : -1);
1629 if (dset
== -currval
) {
1630 ret
->changes
[i
].x
= x
;
1631 ret
->changes
[i
].y
= y
;
1632 ret
->changes
[i
].delta
= dset
;
1637 assert(i
== ret
->n
);
1643 * Having set up the precise list of changes we're going to
1644 * make, we now simply make them and return.
1646 for (i
= 0; i
< ret
->n
; i
++) {
1649 x
= ret
->changes
[i
].x
;
1650 y
= ret
->changes
[i
].y
;
1651 delta
= ret
->changes
[i
].delta
;
1654 * Check we're not trying to add an existing mine or remove
1657 assert((delta
< 0) ^ (ctx
->grid
[y
*ctx
->w
+x
] == 0));
1660 * Actually make the change.
1662 ctx
->grid
[y
*ctx
->w
+x
] = (delta
> 0);
1665 * Update any numbers already present in the grid.
1667 for (dy
= -1; dy
<= +1; dy
++)
1668 for (dx
= -1; dx
<= +1; dx
++)
1669 if (x
+dx
>= 0 && x
+dx
< ctx
->w
&&
1670 y
+dy
>= 0 && y
+dy
< ctx
->h
&&
1671 grid
[(y
+dy
)*ctx
->w
+(x
+dx
)] != -2) {
1672 if (dx
== 0 && dy
== 0) {
1674 * The square itself is marked as known in
1675 * the grid. Mark it as a mine if it's a
1676 * mine, or else work out its number.
1679 grid
[y
*ctx
->w
+x
] = -1;
1681 int dx2
, dy2
, minecount
= 0;
1682 for (dy2
= -1; dy2
<= +1; dy2
++)
1683 for (dx2
= -1; dx2
<= +1; dx2
++)
1684 if (x
+dx2
>= 0 && x
+dx2
< ctx
->w
&&
1685 y
+dy2
>= 0 && y
+dy2
< ctx
->h
&&
1686 ctx
->grid
[(y
+dy2
)*ctx
->w
+(x
+dx2
)])
1688 grid
[y
*ctx
->w
+x
] = minecount
;
1691 if (grid
[(y
+dy
)*ctx
->w
+(x
+dx
)] >= 0)
1692 grid
[(y
+dy
)*ctx
->w
+(x
+dx
)] += delta
;
1697 #ifdef GENERATION_DIAGNOSTICS
1700 printf("grid after perturbing:\n");
1701 for (yy
= 0; yy
< ctx
->h
; yy
++) {
1702 for (xx
= 0; xx
< ctx
->w
; xx
++) {
1703 int v
= ctx
->grid
[yy
*ctx
->w
+xx
];
1704 if (yy
== ctx
->sy
&& xx
== ctx
->sx
) {
1722 static char *minegen(int w
, int h
, int n
, int x
, int y
, int unique
,
1725 char *ret
= snewn(w
*h
, char);
1733 memset(ret
, 0, w
*h
);
1736 * Start by placing n mines, none of which is at x,y or within
1740 int *tmp
= snewn(w
*h
, int);
1744 * Write down the list of possible mine locations.
1747 for (i
= 0; i
< h
; i
++)
1748 for (j
= 0; j
< w
; j
++)
1749 if (abs(i
- y
) > 1 || abs(j
- x
) > 1)
1753 * Now pick n off the list at random.
1757 i
= random_upto(rs
, k
);
1765 #ifdef GENERATION_DIAGNOSTICS
1768 printf("grid after initial generation:\n");
1769 for (yy
= 0; yy
< h
; yy
++) {
1770 for (xx
= 0; xx
< w
; xx
++) {
1771 int v
= ret
[yy
*w
+xx
];
1772 if (yy
== y
&& xx
== x
) {
1788 * Now set up a results grid to run the solver in, and a
1789 * context for the solver to open squares. Then run the solver
1790 * repeatedly; if the number of perturb steps ever goes up or
1791 * it ever returns -1, give up completely.
1793 * We bypass this bit if we're not after a unique grid.
1796 signed char *solvegrid
= snewn(w
*h
, signed char);
1797 struct minectx actx
, *ctx
= &actx
;
1798 int solveret
, prevret
= -2;
1806 ctx
->allow_big_perturbs
= (ntries
> 100);
1809 memset(solvegrid
, -2, w
*h
);
1810 solvegrid
[y
*w
+x
] = mineopen(ctx
, x
, y
);
1811 assert(solvegrid
[y
*w
+x
] == 0); /* by deliberate arrangement */
1814 minesolve(w
, h
, n
, solvegrid
, mineopen
, mineperturb
, ctx
, rs
);
1815 if (solveret
< 0 || (prevret
>= 0 && solveret
>= prevret
)) {
1818 } else if (solveret
== 0) {
1834 static char *describe_layout(char *grid
, int area
, int x
, int y
,
1842 * Set up the mine bitmap and obfuscate it.
1844 bmp
= snewn((area
+ 7) / 8, unsigned char);
1845 memset(bmp
, 0, (area
+ 7) / 8);
1846 for (i
= 0; i
< area
; i
++) {
1848 bmp
[i
/ 8] |= 0x80 >> (i
% 8);
1851 obfuscate_bitmap(bmp
, area
, FALSE
);
1854 * Now encode the resulting bitmap in hex. We can work to
1855 * nibble rather than byte granularity, since the obfuscation
1856 * function guarantees to return a bit string of the same
1857 * length as its input.
1859 ret
= snewn((area
+3)/4 + 100, char);
1860 p
= ret
+ sprintf(ret
, "%d,%d,%s", x
, y
,
1861 obfuscate ?
"m" : "u"); /* 'm' == masked */
1862 for (i
= 0; i
< (area
+3)/4; i
++) {
1866 *p
++ = "0123456789abcdef"[v
& 0xF];
1875 static char *new_mine_layout(int w
, int h
, int n
, int x
, int y
, int unique
,
1876 random_state
*rs
, char **game_desc
)
1880 #ifdef TEST_OBFUSCATION
1881 static int tested_obfuscation
= FALSE
;
1882 if (!tested_obfuscation
) {
1884 * A few simple test vectors for the obfuscator.
1886 * First test: the 28-bit stream 1234567. This divides up
1887 * into 1234 and 567[0]. The SHA of 56 70 30 (appending
1888 * "0") is 15ce8ab946640340bbb99f3f48fd2c45d1a31d30. Thus,
1889 * we XOR the 16-bit string 15CE into the input 1234 to get
1890 * 07FA. Next, we SHA that with "0": the SHA of 07 FA 30 is
1891 * 3370135c5e3da4fed937adc004a79533962b6391. So we XOR the
1892 * 12-bit string 337 into the input 567 to get 650. Thus
1893 * our output is 07FA650.
1896 unsigned char bmp1
[] = "\x12\x34\x56\x70";
1897 obfuscate_bitmap(bmp1
, 28, FALSE
);
1898 printf("test 1 encode: %s\n",
1899 memcmp(bmp1
, "\x07\xfa\x65\x00", 4) ?
"failed" : "passed");
1900 obfuscate_bitmap(bmp1
, 28, TRUE
);
1901 printf("test 1 decode: %s\n",
1902 memcmp(bmp1
, "\x12\x34\x56\x70", 4) ?
"failed" : "passed");
1905 * Second test: a long string to make sure we switch from
1906 * one SHA to the next correctly. My input string this time
1907 * is simply fifty bytes of zeroes.
1910 unsigned char bmp2
[50];
1911 unsigned char bmp2a
[50];
1912 memset(bmp2
, 0, 50);
1913 memset(bmp2a
, 0, 50);
1914 obfuscate_bitmap(bmp2
, 50 * 8, FALSE
);
1916 * SHA of twenty-five zero bytes plus "0" is
1917 * b202c07b990c01f6ff2d544707f60e506019b671. SHA of
1918 * twenty-five zero bytes plus "1" is
1919 * fcb1d8b5a2f6b592fe6780b36aa9d65dd7aa6db9. Thus our
1920 * first half becomes
1921 * b202c07b990c01f6ff2d544707f60e506019b671fcb1d8b5a2.
1923 * SHA of that lot plus "0" is
1924 * 10b0af913db85d37ca27f52a9f78bba3a80030db. SHA of the
1925 * same string plus "1" is
1926 * 3d01d8df78e76d382b8106f480135a1bc751d725. So the
1927 * second half becomes
1928 * 10b0af913db85d37ca27f52a9f78bba3a80030db3d01d8df78.
1930 printf("test 2 encode: %s\n",
1931 memcmp(bmp2
, "\xb2\x02\xc0\x7b\x99\x0c\x01\xf6\xff\x2d\x54"
1932 "\x47\x07\xf6\x0e\x50\x60\x19\xb6\x71\xfc\xb1\xd8"
1933 "\xb5\xa2\x10\xb0\xaf\x91\x3d\xb8\x5d\x37\xca\x27"
1934 "\xf5\x2a\x9f\x78\xbb\xa3\xa8\x00\x30\xdb\x3d\x01"
1935 "\xd8\xdf\x78", 50) ?
"failed" : "passed");
1936 obfuscate_bitmap(bmp2
, 50 * 8, TRUE
);
1937 printf("test 2 decode: %s\n",
1938 memcmp(bmp2
, bmp2a
, 50) ?
"failed" : "passed");
1943 grid
= minegen(w
, h
, n
, x
, y
, unique
, rs
);
1946 *game_desc
= describe_layout(grid
, w
* h
, x
, y
, TRUE
);
1951 static char *new_game_desc(game_params
*params
, random_state
*rs
,
1952 char **aux
, int interactive
)
1955 * We generate the coordinates of an initial click even if they
1956 * aren't actually used. This has the effect of harmonising the
1957 * random number usage between interactive and batch use: if
1958 * you use `mines --generate' with an explicit random seed, you
1959 * should get exactly the same results as if you type the same
1960 * random seed into the interactive game and click in the same
1961 * initial location. (Of course you won't get the same grid if
1962 * you click in a _different_ initial location, but there's
1963 * nothing to be done about that.)
1965 int x
= random_upto(rs
, params
->w
);
1966 int y
= random_upto(rs
, params
->h
);
1970 * For batch-generated grids, pre-open one square.
1975 grid
= new_mine_layout(params
->w
, params
->h
, params
->n
,
1976 x
, y
, params
->unique
, rs
, &desc
);
1980 char *rsdesc
, *desc
;
1982 rsdesc
= random_state_encode(rs
);
1983 desc
= snewn(strlen(rsdesc
) + 100, char);
1984 sprintf(desc
, "r%d,%c,%s", params
->n
, (char)(params
->unique ?
'u' : 'a'), rsdesc
);
1990 static char *validate_desc(game_params
*params
, char *desc
)
1992 int wh
= params
->w
* params
->h
;
1997 if (!*desc
|| !isdigit((unsigned char)*desc
))
1998 return "No initial mine count in game description";
1999 while (*desc
&& isdigit((unsigned char)*desc
))
2000 desc
++; /* skip over mine count */
2002 return "No ',' after initial x-coordinate in game description";
2004 if (*desc
!= 'u' && *desc
!= 'a')
2005 return "No uniqueness specifier in game description";
2008 return "No ',' after uniqueness specifier in game description";
2009 /* now ignore the rest */
2011 if (*desc
&& isdigit((unsigned char)*desc
)) {
2013 if (x
< 0 || x
>= params
->w
)
2014 return "Initial x-coordinate was out of range";
2015 while (*desc
&& isdigit((unsigned char)*desc
))
2016 desc
++; /* skip over x coordinate */
2018 return "No ',' after initial x-coordinate in game description";
2019 desc
++; /* eat comma */
2020 if (!*desc
|| !isdigit((unsigned char)*desc
))
2021 return "No initial y-coordinate in game description";
2023 if (y
< 0 || y
>= params
->h
)
2024 return "Initial y-coordinate was out of range";
2025 while (*desc
&& isdigit((unsigned char)*desc
))
2026 desc
++; /* skip over y coordinate */
2028 return "No ',' after initial y-coordinate in game description";
2029 desc
++; /* eat comma */
2031 /* eat `m' for `masked' or `u' for `unmasked', if present */
2032 if (*desc
== 'm' || *desc
== 'u')
2034 /* now just check length of remainder */
2035 if (strlen(desc
) != (wh
+3)/4)
2036 return "Game description is wrong length";
2042 static int open_square(game_state
*state
, int x
, int y
)
2044 int w
= state
->w
, h
= state
->h
;
2045 int xx
, yy
, nmines
, ncovered
;
2047 if (!state
->layout
->mines
) {
2049 * We have a preliminary game in which the mine layout
2050 * hasn't been generated yet. Generate it based on the
2051 * initial click location.
2053 char *desc
, *privdesc
;
2054 state
->layout
->mines
= new_mine_layout(w
, h
, state
->layout
->n
,
2055 x
, y
, state
->layout
->unique
,
2059 * Find the trailing substring of the game description
2060 * corresponding to just the mine layout; we will use this
2061 * as our second `private' game ID for serialisation.
2064 while (*privdesc
&& isdigit((unsigned char)*privdesc
)) privdesc
++;
2065 if (*privdesc
== ',') privdesc
++;
2066 while (*privdesc
&& isdigit((unsigned char)*privdesc
)) privdesc
++;
2067 if (*privdesc
== ',') privdesc
++;
2068 assert(*privdesc
== 'm');
2069 midend_supersede_game_desc(state
->layout
->me
, desc
, privdesc
);
2071 random_free(state
->layout
->rs
);
2072 state
->layout
->rs
= NULL
;
2075 if (state
->layout
->mines
[y
*w
+x
]) {
2077 * The player has landed on a mine. Bad luck. Expose the
2078 * mine that killed them, but not the rest (in case they
2079 * want to Undo and carry on playing).
2082 state
->grid
[y
*w
+x
] = 65;
2087 * Otherwise, the player has opened a safe square. Mark it to-do.
2089 state
->grid
[y
*w
+x
] = -10; /* `todo' value internal to this func */
2092 * Now go through the grid finding all `todo' values and
2093 * opening them. Every time one of them turns out to have no
2094 * neighbouring mines, we add all its unopened neighbours to
2097 * FIXME: We really ought to be able to do this better than
2098 * using repeated N^2 scans of the grid.
2101 int done_something
= FALSE
;
2103 for (yy
= 0; yy
< h
; yy
++)
2104 for (xx
= 0; xx
< w
; xx
++)
2105 if (state
->grid
[yy
*w
+xx
] == -10) {
2108 assert(!state
->layout
->mines
[yy
*w
+xx
]);
2112 for (dx
= -1; dx
<= +1; dx
++)
2113 for (dy
= -1; dy
<= +1; dy
++)
2114 if (xx
+dx
>= 0 && xx
+dx
< state
->w
&&
2115 yy
+dy
>= 0 && yy
+dy
< state
->h
&&
2116 state
->layout
->mines
[(yy
+dy
)*w
+(xx
+dx
)])
2119 state
->grid
[yy
*w
+xx
] = v
;
2122 for (dx
= -1; dx
<= +1; dx
++)
2123 for (dy
= -1; dy
<= +1; dy
++)
2124 if (xx
+dx
>= 0 && xx
+dx
< state
->w
&&
2125 yy
+dy
>= 0 && yy
+dy
< state
->h
&&
2126 state
->grid
[(yy
+dy
)*w
+(xx
+dx
)] == -2)
2127 state
->grid
[(yy
+dy
)*w
+(xx
+dx
)] = -10;
2130 done_something
= TRUE
;
2133 if (!done_something
)
2138 * Finally, scan the grid and see if exactly as many squares
2139 * are still covered as there are mines. If so, set the `won'
2140 * flag and fill in mine markers on all covered squares.
2142 nmines
= ncovered
= 0;
2143 for (yy
= 0; yy
< h
; yy
++)
2144 for (xx
= 0; xx
< w
; xx
++) {
2145 if (state
->grid
[yy
*w
+xx
] < 0)
2147 if (state
->layout
->mines
[yy
*w
+xx
])
2150 assert(ncovered
>= nmines
);
2151 if (ncovered
== nmines
) {
2152 for (yy
= 0; yy
< h
; yy
++)
2153 for (xx
= 0; xx
< w
; xx
++) {
2154 if (state
->grid
[yy
*w
+xx
] < 0)
2155 state
->grid
[yy
*w
+xx
] = -1;
2163 static game_state
*new_game(midend
*me
, game_params
*params
, char *desc
)
2165 game_state
*state
= snew(game_state
);
2166 int i
, wh
, x
, y
, ret
, masked
;
2169 state
->w
= params
->w
;
2170 state
->h
= params
->h
;
2171 state
->n
= params
->n
;
2172 state
->dead
= state
->won
= FALSE
;
2173 state
->used_solve
= FALSE
;
2175 wh
= state
->w
* state
->h
;
2177 state
->layout
= snew(struct mine_layout
);
2178 memset(state
->layout
, 0, sizeof(struct mine_layout
));
2179 state
->layout
->refcount
= 1;
2181 state
->grid
= snewn(wh
, signed char);
2182 memset(state
->grid
, -2, wh
);
2186 state
->layout
->n
= atoi(desc
);
2187 while (*desc
&& isdigit((unsigned char)*desc
))
2188 desc
++; /* skip over mine count */
2189 if (*desc
) desc
++; /* eat comma */
2191 state
->layout
->unique
= FALSE
;
2193 state
->layout
->unique
= TRUE
;
2195 if (*desc
) desc
++; /* eat comma */
2197 state
->layout
->mines
= NULL
;
2198 state
->layout
->rs
= random_state_decode(desc
);
2199 state
->layout
->me
= me
;
2202 state
->layout
->rs
= NULL
;
2203 state
->layout
->me
= NULL
;
2204 state
->layout
->mines
= snewn(wh
, char);
2206 if (*desc
&& isdigit((unsigned char)*desc
)) {
2208 while (*desc
&& isdigit((unsigned char)*desc
))
2209 desc
++; /* skip over x coordinate */
2210 if (*desc
) desc
++; /* eat comma */
2212 while (*desc
&& isdigit((unsigned char)*desc
))
2213 desc
++; /* skip over y coordinate */
2214 if (*desc
) desc
++; /* eat comma */
2226 * We permit game IDs to be entered by hand without the
2227 * masking transformation.
2232 bmp
= snewn((wh
+ 7) / 8, unsigned char);
2233 memset(bmp
, 0, (wh
+ 7) / 8);
2234 for (i
= 0; i
< (wh
+3)/4; i
++) {
2238 assert(c
!= 0); /* validate_desc should have caught */
2239 if (c
>= '0' && c
<= '9')
2241 else if (c
>= 'a' && c
<= 'f')
2243 else if (c
>= 'A' && c
<= 'F')
2248 bmp
[i
/ 2] |= v
<< (4 * (1 - (i
% 2)));
2252 obfuscate_bitmap(bmp
, wh
, TRUE
);
2254 memset(state
->layout
->mines
, 0, wh
);
2255 for (i
= 0; i
< wh
; i
++) {
2256 if (bmp
[i
/ 8] & (0x80 >> (i
% 8)))
2257 state
->layout
->mines
[i
] = 1;
2260 if (x
>= 0 && y
>= 0)
2261 ret
= open_square(state
, x
, y
);
2268 static game_state
*dup_game(game_state
*state
)
2270 game_state
*ret
= snew(game_state
);
2275 ret
->dead
= state
->dead
;
2276 ret
->won
= state
->won
;
2277 ret
->used_solve
= state
->used_solve
;
2278 ret
->layout
= state
->layout
;
2279 ret
->layout
->refcount
++;
2280 ret
->grid
= snewn(ret
->w
* ret
->h
, signed char);
2281 memcpy(ret
->grid
, state
->grid
, ret
->w
* ret
->h
);
2286 static void free_game(game_state
*state
)
2288 if (--state
->layout
->refcount
<= 0) {
2289 sfree(state
->layout
->mines
);
2290 if (state
->layout
->rs
)
2291 random_free(state
->layout
->rs
);
2292 sfree(state
->layout
);
2298 static char *solve_game(game_state
*state
, game_state
*currstate
,
2299 char *aux
, char **error
)
2301 if (!state
->layout
->mines
) {
2302 *error
= "Game has not been started yet";
2309 static char *game_text_format(game_state
*state
)
2314 ret
= snewn((state
->w
+ 1) * state
->h
+ 1, char);
2315 for (y
= 0; y
< state
->h
; y
++) {
2316 for (x
= 0; x
< state
->w
; x
++) {
2317 int v
= state
->grid
[y
*state
->w
+x
];
2320 else if (v
>= 1 && v
<= 8)
2324 else if (v
== -2 || v
== -3)
2328 ret
[y
* (state
->w
+1) + x
] = v
;
2330 ret
[y
* (state
->w
+1) + state
->w
] = '\n';
2332 ret
[(state
->w
+ 1) * state
->h
] = '\0';
2338 int hx
, hy
, hradius
; /* for mouse-down highlights */
2341 int deaths
, completed
;
2344 static game_ui
*new_ui(game_state
*state
)
2346 game_ui
*ui
= snew(game_ui
);
2347 ui
->hx
= ui
->hy
= -1;
2348 ui
->hradius
= ui
->validradius
= 0;
2350 ui
->completed
= FALSE
;
2351 ui
->flash_is_death
= FALSE
; /* *shrug* */
2355 static void free_ui(game_ui
*ui
)
2360 static char *encode_ui(game_ui
*ui
)
2364 * The deaths counter and completion status need preserving
2365 * across a serialisation.
2367 sprintf(buf
, "D%d", ui
->deaths
);
2373 static void decode_ui(game_ui
*ui
, char *encoding
)
2376 sscanf(encoding
, "D%d%n", &ui
->deaths
, &p
);
2377 if (encoding
[p
] == 'C')
2378 ui
->completed
= TRUE
;
2381 static void game_changed_state(game_ui
*ui
, game_state
*oldstate
,
2382 game_state
*newstate
)
2385 ui
->completed
= TRUE
;
2388 struct game_drawstate
{
2389 int w
, h
, started
, tilesize
, bg
;
2392 * Items in this `grid' array have all the same values as in
2393 * the game_state grid, and in addition:
2395 * - -10 means the tile was drawn `specially' as a result of a
2396 * flash, so it will always need redrawing.
2398 * - -22 and -23 mean the tile is highlighted for a possible
2403 static char *interpret_move(game_state
*from
, game_ui
*ui
, game_drawstate
*ds
,
2404 int x
, int y
, int button
)
2409 if (from
->dead
|| from
->won
)
2410 return NULL
; /* no further moves permitted */
2412 if (!IS_MOUSE_DOWN(button
) && !IS_MOUSE_DRAG(button
) &&
2413 !IS_MOUSE_RELEASE(button
))
2419 if (button
== LEFT_BUTTON
|| button
== LEFT_DRAG
||
2420 button
== MIDDLE_BUTTON
|| button
== MIDDLE_DRAG
) {
2421 if (cx
< 0 || cx
>= from
->w
|| cy
< 0 || cy
>= from
->h
)
2425 * Mouse-downs and mouse-drags just cause highlighting
2430 ui
->hradius
= (from
->grid
[cy
*from
->w
+cx
] >= 0 ?
1 : 0);
2431 if (button
== LEFT_BUTTON
)
2432 ui
->validradius
= ui
->hradius
;
2433 else if (button
== MIDDLE_BUTTON
)
2434 ui
->validradius
= 1;
2438 if (button
== RIGHT_BUTTON
) {
2439 if (cx
< 0 || cx
>= from
->w
|| cy
< 0 || cy
>= from
->h
)
2443 * Right-clicking only works on a covered square, and it
2444 * toggles between -1 (marked as mine) and -2 (not marked
2447 * FIXME: question marks.
2449 if (from
->grid
[cy
* from
->w
+ cx
] != -2 &&
2450 from
->grid
[cy
* from
->w
+ cx
] != -1)
2453 sprintf(buf
, "F%d,%d", cx
, cy
);
2457 if (button
== LEFT_RELEASE
|| button
== MIDDLE_RELEASE
) {
2458 ui
->hx
= ui
->hy
= -1;
2462 * At this stage we must never return NULL: we have adjusted
2463 * the ui, so at worst we return "".
2465 if (cx
< 0 || cx
>= from
->w
|| cy
< 0 || cy
>= from
->h
)
2469 * Left-clicking on a covered square opens a tile. Not
2470 * permitted if the tile is marked as a mine, for safety.
2471 * (Unmark it and _then_ open it.)
2473 if (button
== LEFT_RELEASE
&&
2474 (from
->grid
[cy
* from
->w
+ cx
] == -2 ||
2475 from
->grid
[cy
* from
->w
+ cx
] == -3) &&
2476 ui
->validradius
== 0) {
2477 /* Check if you've killed yourself. */
2478 if (from
->layout
->mines
&& from
->layout
->mines
[cy
* from
->w
+ cx
])
2481 sprintf(buf
, "O%d,%d", cx
, cy
);
2486 * Left-clicking or middle-clicking on an uncovered tile:
2487 * first we check to see if the number of mine markers
2488 * surrounding the tile is equal to its mine count, and if
2489 * so then we open all other surrounding squares.
2491 if (from
->grid
[cy
* from
->w
+ cx
] > 0 && ui
->validradius
== 1) {
2494 /* Count mine markers. */
2496 for (dy
= -1; dy
<= +1; dy
++)
2497 for (dx
= -1; dx
<= +1; dx
++)
2498 if (cx
+dx
>= 0 && cx
+dx
< from
->w
&&
2499 cy
+dy
>= 0 && cy
+dy
< from
->h
) {
2500 if (from
->grid
[(cy
+dy
)*from
->w
+(cx
+dx
)] == -1)
2504 if (n
== from
->grid
[cy
* from
->w
+ cx
]) {
2507 * Now see if any of the squares we're clearing
2508 * contains a mine (which will happen iff you've
2509 * incorrectly marked the mines around the clicked
2510 * square). If so, we open _just_ those squares, to
2511 * reveal as little additional information as we
2517 for (dy
= -1; dy
<= +1; dy
++)
2518 for (dx
= -1; dx
<= +1; dx
++)
2519 if (cx
+dx
>= 0 && cx
+dx
< from
->w
&&
2520 cy
+dy
>= 0 && cy
+dy
< from
->h
) {
2521 if (from
->grid
[(cy
+dy
)*from
->w
+(cx
+dx
)] != -1 &&
2522 from
->layout
->mines
&&
2523 from
->layout
->mines
[(cy
+dy
)*from
->w
+(cx
+dx
)]) {
2524 p
+= sprintf(p
, "%sO%d,%d", sep
, cx
+dx
, cy
+dy
);
2532 sprintf(buf
, "C%d,%d", cx
, cy
);
2545 static game_state
*execute_move(game_state
*from
, char *move
)
2550 if (!strcmp(move
, "S")) {
2552 * Simply expose the entire grid as if it were a completed
2557 ret
= dup_game(from
);
2558 for (yy
= 0; yy
< ret
->h
; yy
++)
2559 for (xx
= 0; xx
< ret
->w
; xx
++) {
2561 if (ret
->layout
->mines
[yy
*ret
->w
+xx
]) {
2562 ret
->grid
[yy
*ret
->w
+xx
] = -1;
2568 for (dx
= -1; dx
<= +1; dx
++)
2569 for (dy
= -1; dy
<= +1; dy
++)
2570 if (xx
+dx
>= 0 && xx
+dx
< ret
->w
&&
2571 yy
+dy
>= 0 && yy
+dy
< ret
->h
&&
2572 ret
->layout
->mines
[(yy
+dy
)*ret
->w
+(xx
+dx
)])
2575 ret
->grid
[yy
*ret
->w
+xx
] = v
;
2578 ret
->used_solve
= TRUE
;
2583 ret
= dup_game(from
);
2586 if (move
[0] == 'F' &&
2587 sscanf(move
+1, "%d,%d", &cx
, &cy
) == 2 &&
2588 cx
>= 0 && cx
< from
->w
&& cy
>= 0 && cy
< from
->h
) {
2589 ret
->grid
[cy
* from
->w
+ cx
] ^= (-2 ^ -1);
2590 } else if (move
[0] == 'O' &&
2591 sscanf(move
+1, "%d,%d", &cx
, &cy
) == 2 &&
2592 cx
>= 0 && cx
< from
->w
&& cy
>= 0 && cy
< from
->h
) {
2593 open_square(ret
, cx
, cy
);
2594 } else if (move
[0] == 'C' &&
2595 sscanf(move
+1, "%d,%d", &cx
, &cy
) == 2 &&
2596 cx
>= 0 && cx
< from
->w
&& cy
>= 0 && cy
< from
->h
) {
2599 for (dy
= -1; dy
<= +1; dy
++)
2600 for (dx
= -1; dx
<= +1; dx
++)
2601 if (cx
+dx
>= 0 && cx
+dx
< ret
->w
&&
2602 cy
+dy
>= 0 && cy
+dy
< ret
->h
&&
2603 (ret
->grid
[(cy
+dy
)*ret
->w
+(cx
+dx
)] == -2 ||
2604 ret
->grid
[(cy
+dy
)*ret
->w
+(cx
+dx
)] == -3))
2605 open_square(ret
, cx
+dx
, cy
+dy
);
2611 while (*move
&& *move
!= ';') move
++;
2619 /* ----------------------------------------------------------------------
2623 static void game_compute_size(game_params
*params
, int tilesize
,
2626 /* Ick: fake up `ds->tilesize' for macro expansion purposes */
2627 struct { int tilesize
; } ads
, *ds
= &ads
;
2628 ads
.tilesize
= tilesize
;
2630 *x
= BORDER
* 2 + TILE_SIZE
* params
->w
;
2631 *y
= BORDER
* 2 + TILE_SIZE
* params
->h
;
2634 static void game_set_size(drawing
*dr
, game_drawstate
*ds
,
2635 game_params
*params
, int tilesize
)
2637 ds
->tilesize
= tilesize
;
2640 static float *game_colours(frontend
*fe
, int *ncolours
)
2642 float *ret
= snewn(3 * NCOLOURS
, float);
2644 frontend_default_colour(fe
, &ret
[COL_BACKGROUND
* 3]);
2646 ret
[COL_BACKGROUND2
* 3 + 0] = ret
[COL_BACKGROUND
* 3 + 0] * 19.0 / 20.0;
2647 ret
[COL_BACKGROUND2
* 3 + 1] = ret
[COL_BACKGROUND
* 3 + 1] * 19.0 / 20.0;
2648 ret
[COL_BACKGROUND2
* 3 + 2] = ret
[COL_BACKGROUND
* 3 + 2] * 19.0 / 20.0;
2650 ret
[COL_1
* 3 + 0] = 0.0F
;
2651 ret
[COL_1
* 3 + 1] = 0.0F
;
2652 ret
[COL_1
* 3 + 2] = 1.0F
;
2654 ret
[COL_2
* 3 + 0] = 0.0F
;
2655 ret
[COL_2
* 3 + 1] = 0.5F
;
2656 ret
[COL_2
* 3 + 2] = 0.0F
;
2658 ret
[COL_3
* 3 + 0] = 1.0F
;
2659 ret
[COL_3
* 3 + 1] = 0.0F
;
2660 ret
[COL_3
* 3 + 2] = 0.0F
;
2662 ret
[COL_4
* 3 + 0] = 0.0F
;
2663 ret
[COL_4
* 3 + 1] = 0.0F
;
2664 ret
[COL_4
* 3 + 2] = 0.5F
;
2666 ret
[COL_5
* 3 + 0] = 0.5F
;
2667 ret
[COL_5
* 3 + 1] = 0.0F
;
2668 ret
[COL_5
* 3 + 2] = 0.0F
;
2670 ret
[COL_6
* 3 + 0] = 0.0F
;
2671 ret
[COL_6
* 3 + 1] = 0.5F
;
2672 ret
[COL_6
* 3 + 2] = 0.5F
;
2674 ret
[COL_7
* 3 + 0] = 0.0F
;
2675 ret
[COL_7
* 3 + 1] = 0.0F
;
2676 ret
[COL_7
* 3 + 2] = 0.0F
;
2678 ret
[COL_8
* 3 + 0] = 0.5F
;
2679 ret
[COL_8
* 3 + 1] = 0.5F
;
2680 ret
[COL_8
* 3 + 2] = 0.5F
;
2682 ret
[COL_MINE
* 3 + 0] = 0.0F
;
2683 ret
[COL_MINE
* 3 + 1] = 0.0F
;
2684 ret
[COL_MINE
* 3 + 2] = 0.0F
;
2686 ret
[COL_BANG
* 3 + 0] = 1.0F
;
2687 ret
[COL_BANG
* 3 + 1] = 0.0F
;
2688 ret
[COL_BANG
* 3 + 2] = 0.0F
;
2690 ret
[COL_CROSS
* 3 + 0] = 1.0F
;
2691 ret
[COL_CROSS
* 3 + 1] = 0.0F
;
2692 ret
[COL_CROSS
* 3 + 2] = 0.0F
;
2694 ret
[COL_FLAG
* 3 + 0] = 1.0F
;
2695 ret
[COL_FLAG
* 3 + 1] = 0.0F
;
2696 ret
[COL_FLAG
* 3 + 2] = 0.0F
;
2698 ret
[COL_FLAGBASE
* 3 + 0] = 0.0F
;
2699 ret
[COL_FLAGBASE
* 3 + 1] = 0.0F
;
2700 ret
[COL_FLAGBASE
* 3 + 2] = 0.0F
;
2702 ret
[COL_QUERY
* 3 + 0] = 0.0F
;
2703 ret
[COL_QUERY
* 3 + 1] = 0.0F
;
2704 ret
[COL_QUERY
* 3 + 2] = 0.0F
;
2706 ret
[COL_HIGHLIGHT
* 3 + 0] = 1.0F
;
2707 ret
[COL_HIGHLIGHT
* 3 + 1] = 1.0F
;
2708 ret
[COL_HIGHLIGHT
* 3 + 2] = 1.0F
;
2710 ret
[COL_LOWLIGHT
* 3 + 0] = ret
[COL_BACKGROUND
* 3 + 0] * 2.0 / 3.0;
2711 ret
[COL_LOWLIGHT
* 3 + 1] = ret
[COL_BACKGROUND
* 3 + 1] * 2.0 / 3.0;
2712 ret
[COL_LOWLIGHT
* 3 + 2] = ret
[COL_BACKGROUND
* 3 + 2] * 2.0 / 3.0;
2714 ret
[COL_WRONGNUMBER
* 3 + 0] = 1.0F
;
2715 ret
[COL_WRONGNUMBER
* 3 + 1] = 0.6F
;
2716 ret
[COL_WRONGNUMBER
* 3 + 2] = 0.6F
;
2718 *ncolours
= NCOLOURS
;
2722 static game_drawstate
*game_new_drawstate(drawing
*dr
, game_state
*state
)
2724 struct game_drawstate
*ds
= snew(struct game_drawstate
);
2728 ds
->started
= FALSE
;
2729 ds
->tilesize
= 0; /* not decided yet */
2730 ds
->grid
= snewn(ds
->w
* ds
->h
, signed char);
2733 memset(ds
->grid
, -99, ds
->w
* ds
->h
);
2738 static void game_free_drawstate(drawing
*dr
, game_drawstate
*ds
)
2744 static void draw_tile(drawing
*dr
, game_drawstate
*ds
,
2745 int x
, int y
, int v
, int bg
)
2751 if (v
== -22 || v
== -23) {
2755 * Omit the highlights in this case.
2757 draw_rect(dr
, x
, y
, TILE_SIZE
, TILE_SIZE
,
2758 bg
== COL_BACKGROUND ? COL_BACKGROUND2
: bg
);
2759 draw_line(dr
, x
, y
, x
+ TILE_SIZE
- 1, y
, COL_LOWLIGHT
);
2760 draw_line(dr
, x
, y
, x
, y
+ TILE_SIZE
- 1, COL_LOWLIGHT
);
2763 * Draw highlights to indicate the square is covered.
2765 coords
[0] = x
+ TILE_SIZE
- 1;
2766 coords
[1] = y
+ TILE_SIZE
- 1;
2767 coords
[2] = x
+ TILE_SIZE
- 1;
2770 coords
[5] = y
+ TILE_SIZE
- 1;
2771 draw_polygon(dr
, coords
, 3, COL_LOWLIGHT
^ hl
, COL_LOWLIGHT
^ hl
);
2775 draw_polygon(dr
, coords
, 3, COL_HIGHLIGHT
^ hl
,
2776 COL_HIGHLIGHT
^ hl
);
2778 draw_rect(dr
, x
+ HIGHLIGHT_WIDTH
, y
+ HIGHLIGHT_WIDTH
,
2779 TILE_SIZE
- 2*HIGHLIGHT_WIDTH
, TILE_SIZE
- 2*HIGHLIGHT_WIDTH
,
2787 #define SETCOORD(n, dx, dy) do { \
2788 coords[(n)*2+0] = x + TILE_SIZE * (dx); \
2789 coords[(n)*2+1] = y + TILE_SIZE * (dy); \
2791 SETCOORD(0, 0.6, 0.35);
2792 SETCOORD(1, 0.6, 0.7);
2793 SETCOORD(2, 0.8, 0.8);
2794 SETCOORD(3, 0.25, 0.8);
2795 SETCOORD(4, 0.55, 0.7);
2796 SETCOORD(5, 0.55, 0.35);
2797 draw_polygon(dr
, coords
, 6, COL_FLAGBASE
, COL_FLAGBASE
);
2799 SETCOORD(0, 0.6, 0.2);
2800 SETCOORD(1, 0.6, 0.5);
2801 SETCOORD(2, 0.2, 0.35);
2802 draw_polygon(dr
, coords
, 3, COL_FLAG
, COL_FLAG
);
2805 } else if (v
== -3) {
2807 * Draw a question mark.
2809 draw_text(dr
, x
+ TILE_SIZE
/ 2, y
+ TILE_SIZE
/ 2,
2810 FONT_VARIABLE
, TILE_SIZE
* 6 / 8,
2811 ALIGN_VCENTRE
| ALIGN_HCENTRE
,
2816 * Clear the square to the background colour, and draw thin
2817 * grid lines along the top and left.
2819 * Exception is that for value 65 (mine we've just trodden
2820 * on), we clear the square to COL_BANG.
2823 bg
= COL_WRONGNUMBER
;
2826 draw_rect(dr
, x
, y
, TILE_SIZE
, TILE_SIZE
,
2827 (v
== 65 ? COL_BANG
:
2828 bg
== COL_BACKGROUND ? COL_BACKGROUND2
: bg
));
2829 draw_line(dr
, x
, y
, x
+ TILE_SIZE
- 1, y
, COL_LOWLIGHT
);
2830 draw_line(dr
, x
, y
, x
, y
+ TILE_SIZE
- 1, COL_LOWLIGHT
);
2832 if (v
> 0 && v
<= 8) {
2839 draw_text(dr
, x
+ TILE_SIZE
/ 2, y
+ TILE_SIZE
/ 2,
2840 FONT_VARIABLE
, TILE_SIZE
* 7 / 8,
2841 ALIGN_VCENTRE
| ALIGN_HCENTRE
,
2842 (COL_1
- 1) + v
, str
);
2844 } else if (v
>= 64) {
2848 * FIXME: this could be done better!
2851 draw_text(dr
, x
+ TILE_SIZE
/ 2, y
+ TILE_SIZE
/ 2,
2852 FONT_VARIABLE
, TILE_SIZE
* 7 / 8,
2853 ALIGN_VCENTRE
| ALIGN_HCENTRE
,
2857 int cx
= x
+ TILE_SIZE
/ 2;
2858 int cy
= y
+ TILE_SIZE
/ 2;
2859 int r
= TILE_SIZE
/ 2 - 3;
2861 int xdx
= 1, xdy
= 0, ydx
= 0, ydy
= 1;
2864 for (i
= 0; i
< 4*5*2; i
+= 5*2) {
2865 coords
[i
+2*0+0] = cx
- r
/6*xdx
+ r
*4/5*ydx
;
2866 coords
[i
+2*0+1] = cy
- r
/6*xdy
+ r
*4/5*ydy
;
2867 coords
[i
+2*1+0] = cx
- r
/6*xdx
+ r
*ydx
;
2868 coords
[i
+2*1+1] = cy
- r
/6*xdy
+ r
*ydy
;
2869 coords
[i
+2*2+0] = cx
+ r
/6*xdx
+ r
*ydx
;
2870 coords
[i
+2*2+1] = cy
+ r
/6*xdy
+ r
*ydy
;
2871 coords
[i
+2*3+0] = cx
+ r
/6*xdx
+ r
*4/5*ydx
;
2872 coords
[i
+2*3+1] = cy
+ r
/6*xdy
+ r
*4/5*ydy
;
2873 coords
[i
+2*4+0] = cx
+ r
*3/5*xdx
+ r
*3/5*ydx
;
2874 coords
[i
+2*4+1] = cy
+ r
*3/5*xdy
+ r
*3/5*ydy
;
2884 draw_polygon(dr
, coords
, 5*4, COL_MINE
, COL_MINE
);
2886 draw_rect(dr
, cx
-r
/3, cy
-r
/3, r
/3, r
/4, COL_HIGHLIGHT
);
2892 * Cross through the mine.
2895 for (dx
= -1; dx
<= +1; dx
++) {
2896 draw_line(dr
, x
+ 3 + dx
, y
+ 2,
2897 x
+ TILE_SIZE
- 3 + dx
,
2898 y
+ TILE_SIZE
- 2, COL_CROSS
);
2899 draw_line(dr
, x
+ TILE_SIZE
- 3 + dx
, y
+ 2,
2900 x
+ 3 + dx
, y
+ TILE_SIZE
- 2,
2907 draw_update(dr
, x
, y
, TILE_SIZE
, TILE_SIZE
);
2910 static void game_redraw(drawing
*dr
, game_drawstate
*ds
, game_state
*oldstate
,
2911 game_state
*state
, int dir
, game_ui
*ui
,
2912 float animtime
, float flashtime
)
2915 int mines
, markers
, bg
;
2918 int frame
= (flashtime
/ FLASH_FRAME
);
2920 bg
= (ui
->flash_is_death ? COL_BACKGROUND
: COL_LOWLIGHT
);
2922 bg
= (ui
->flash_is_death ? COL_BANG
: COL_HIGHLIGHT
);
2924 bg
= COL_BACKGROUND
;
2930 TILE_SIZE
* state
->w
+ 2 * BORDER
,
2931 TILE_SIZE
* state
->h
+ 2 * BORDER
, COL_BACKGROUND
);
2932 draw_update(dr
, 0, 0,
2933 TILE_SIZE
* state
->w
+ 2 * BORDER
,
2934 TILE_SIZE
* state
->h
+ 2 * BORDER
);
2937 * Recessed area containing the whole puzzle.
2939 coords
[0] = COORD(state
->w
) + OUTER_HIGHLIGHT_WIDTH
- 1;
2940 coords
[1] = COORD(state
->h
) + OUTER_HIGHLIGHT_WIDTH
- 1;
2941 coords
[2] = COORD(state
->w
) + OUTER_HIGHLIGHT_WIDTH
- 1;
2942 coords
[3] = COORD(0) - OUTER_HIGHLIGHT_WIDTH
;
2943 coords
[4] = coords
[2] - TILE_SIZE
;
2944 coords
[5] = coords
[3] + TILE_SIZE
;
2945 coords
[8] = COORD(0) - OUTER_HIGHLIGHT_WIDTH
;
2946 coords
[9] = COORD(state
->h
) + OUTER_HIGHLIGHT_WIDTH
- 1;
2947 coords
[6] = coords
[8] + TILE_SIZE
;
2948 coords
[7] = coords
[9] - TILE_SIZE
;
2949 draw_polygon(dr
, coords
, 5, COL_HIGHLIGHT
, COL_HIGHLIGHT
);
2951 coords
[1] = COORD(0) - OUTER_HIGHLIGHT_WIDTH
;
2952 coords
[0] = COORD(0) - OUTER_HIGHLIGHT_WIDTH
;
2953 draw_polygon(dr
, coords
, 5, COL_LOWLIGHT
, COL_LOWLIGHT
);
2959 * Now draw the tiles. Also in this loop, count up the number
2960 * of mines and mine markers.
2962 mines
= markers
= 0;
2963 for (y
= 0; y
< ds
->h
; y
++)
2964 for (x
= 0; x
< ds
->w
; x
++) {
2965 int v
= state
->grid
[y
*ds
->w
+x
];
2969 if (state
->layout
->mines
&& state
->layout
->mines
[y
*ds
->w
+x
])
2972 if (v
>= 0 && v
<= 8) {
2974 * Count up the flags around this tile, and if
2975 * there are too _many_, highlight the tile.
2977 int dx
, dy
, flags
= 0;
2979 for (dy
= -1; dy
<= +1; dy
++)
2980 for (dx
= -1; dx
<= +1; dx
++) {
2981 int nx
= x
+dx
, ny
= y
+dy
;
2982 if (nx
>= 0 && nx
< ds
->w
&&
2983 ny
>= 0 && ny
< ds
->h
&&
2984 state
->grid
[ny
*ds
->w
+nx
] == -1)
2992 if ((v
== -2 || v
== -3) &&
2993 (abs(x
-ui
->hx
) <= ui
->hradius
&& abs(y
-ui
->hy
) <= ui
->hradius
))
2996 if (ds
->grid
[y
*ds
->w
+x
] != v
|| bg
!= ds
->bg
) {
2997 draw_tile(dr
, ds
, COORD(x
), COORD(y
), v
, bg
);
2998 ds
->grid
[y
*ds
->w
+x
] = v
;
3003 if (!state
->layout
->mines
)
3004 mines
= state
->layout
->n
;
3007 * Update the status bar.
3010 char statusbar
[512];
3012 sprintf(statusbar
, "DEAD!");
3013 } else if (state
->won
) {
3014 if (state
->used_solve
)
3015 sprintf(statusbar
, "Auto-solved.");
3017 sprintf(statusbar
, "COMPLETED!");
3019 sprintf(statusbar
, "Marked: %d / %d", markers
, mines
);
3022 sprintf(statusbar
+ strlen(statusbar
),
3023 " Deaths: %d", ui
->deaths
);
3024 status_bar(dr
, statusbar
);
3028 static float game_anim_length(game_state
*oldstate
, game_state
*newstate
,
3029 int dir
, game_ui
*ui
)
3034 static float game_flash_length(game_state
*oldstate
, game_state
*newstate
,
3035 int dir
, game_ui
*ui
)
3037 if (oldstate
->used_solve
|| newstate
->used_solve
)
3040 if (dir
> 0 && !oldstate
->dead
&& !oldstate
->won
) {
3041 if (newstate
->dead
) {
3042 ui
->flash_is_death
= TRUE
;
3043 return 3 * FLASH_FRAME
;
3045 if (newstate
->won
) {
3046 ui
->flash_is_death
= FALSE
;
3047 return 2 * FLASH_FRAME
;
3053 static int game_timing_state(game_state
*state
, game_ui
*ui
)
3055 if (state
->dead
|| state
->won
|| ui
->completed
|| !state
->layout
->mines
)
3060 static void game_print_size(game_params
*params
, float *x
, float *y
)
3064 static void game_print(drawing
*dr
, game_state
*state
, int tilesize
)
3069 #define thegame mines
3072 const struct game thegame
= {
3073 "Mines", "games.mines", "mines",
3080 TRUE
, game_configure
, custom_params
,
3088 TRUE
, game_text_format
,
3096 PREFERRED_TILE_SIZE
, game_compute_size
, game_set_size
,
3099 game_free_drawstate
,
3103 FALSE
, FALSE
, game_print_size
, game_print
,
3104 TRUE
, /* wants_statusbar */
3105 TRUE
, game_timing_state
,
3106 BUTTON_BEATS(LEFT_BUTTON
, RIGHT_BUTTON
),
3109 #ifdef STANDALONE_OBFUSCATOR
3112 * Vaguely useful stand-alone program which translates between
3113 * obfuscated and clear Mines game descriptions. Pass in a game
3114 * description on the command line, and if it's clear it will be
3115 * obfuscated and vice versa. The output text should also be a
3116 * valid game ID describing the same game. Like this:
3118 * $ ./mineobfusc 9x9:4,4,mb071b49fbd1cb6a0d5868
3119 * 9x9:4,4,004000007c00010022080
3120 * $ ./mineobfusc 9x9:4,4,004000007c00010022080
3121 * 9x9:4,4,mb071b49fbd1cb6a0d5868
3124 int main(int argc
, char **argv
)
3128 char *id
= NULL
, *desc
, *err
;
3131 while (--argc
> 0) {
3134 fprintf(stderr
, "%s: unrecognised option `%s'\n", argv
[0], p
);
3142 fprintf(stderr
, "usage: %s <game_id>\n", argv
[0]);
3146 desc
= strchr(id
, ':');
3148 fprintf(stderr
, "%s: game id expects a colon in it\n", argv
[0]);
3153 p
= default_params();
3154 decode_params(p
, id
);
3155 err
= validate_desc(p
, desc
);
3157 fprintf(stderr
, "%s: %s\n", argv
[0], err
);
3160 s
= new_game(NULL
, p
, desc
);
3163 while (*desc
&& *desc
!= ',') desc
++;
3166 while (*desc
&& *desc
!= ',') desc
++;
3169 printf("%s:%s\n", id
, describe_layout(s
->layout
->mines
,