tsiry-sandratraina.com
A modern Music Player Daemon based on Rockbox open source high quality audio player
libadwaita
audio
rust
zig
deno
mpris
rockbox
mpd
1/*
2 * mines.c: Minesweeper clone with sophisticated grid generation.
3 *
4 * Still TODO:
5 *
6 * - think about configurably supporting question marks.
7 */
8
9#include <stdio.h>
10#include <stdlib.h>
11#include <string.h>
12#include <assert.h>
13#include <ctype.h>
14#include <limits.h>
15#ifdef NO_TGMATH_H
16# include <math.h>
17#else
18# include <tgmath.h>
19#endif
20
21#include "tree234.h"
22#include "puzzles.h"
23
24enum {
25 COL_BACKGROUND, COL_BACKGROUND2,
26 COL_1, COL_2, COL_3, COL_4, COL_5, COL_6, COL_7, COL_8,
27 COL_MINE, COL_BANG, COL_CROSS, COL_FLAG, COL_FLAGBASE, COL_QUERY,
28 COL_HIGHLIGHT, COL_LOWLIGHT,
29 COL_WRONGNUMBER,
30 COL_CURSOR,
31 NCOLOURS
32};
33
34#define PREFERRED_TILE_SIZE 20
35#define TILE_SIZE (ds->tilesize)
36#ifdef SMALL_SCREEN
37#define BORDER 8
38#else
39#define BORDER (TILE_SIZE * 3 / 2)
40#endif
41#define HIGHLIGHT_WIDTH (TILE_SIZE / 10 ? TILE_SIZE / 10 : 1)
42#define OUTER_HIGHLIGHT_WIDTH (BORDER / 10 ? BORDER / 10 : 1)
43#define COORD(x) ( (x) * TILE_SIZE + BORDER )
44#define FROMCOORD(x) ( ((x) - BORDER + TILE_SIZE) / TILE_SIZE - 1 )
45
46#define FLASH_FRAME 0.13F
47
48struct game_params {
49 int w, h, n;
50 bool unique;
51
52 /* For non-interactive generation, you can set these to override
53 * the randomised first-click location. */
54 int first_click_x, first_click_y;
55};
56
57struct mine_layout {
58 /*
59 * This structure is shared between all the game_states for a
60 * given instance of the puzzle, so we reference-count it.
61 */
62 int refcount;
63 bool *mines;
64 /*
65 * If we haven't yet actually generated the mine layout, here's
66 * all the data we will need to do so.
67 */
68 int n;
69 bool unique;
70 random_state *rs;
71 midend *me; /* to give back the new game desc */
72};
73
74struct game_state {
75 int w, h, n;
76 bool dead, won, used_solve;
77 struct mine_layout *layout; /* real mine positions */
78 signed char *grid; /* player knowledge */
79 /*
80 * Each item in the `grid' array is one of the following values:
81 *
82 * - 0 to 8 mean the square is open and has a surrounding mine
83 * count.
84 *
85 * - -1 means the square is marked as a mine.
86 *
87 * - -2 means the square is unknown.
88 *
89 * - -3 means the square is marked with a question mark
90 * (FIXME: do we even want to bother with this?).
91 *
92 * - 64 means the square has had a mine revealed when the game
93 * was lost.
94 *
95 * - 65 means the square had a mine revealed and this was the
96 * one the player hits.
97 *
98 * - 66 means the square has a crossed-out mine because the
99 * player had incorrectly marked it.
100 */
101};
102
103static game_params *default_params(void)
104{
105 game_params *ret = snew(game_params);
106
107 ret->w = ret->h = 9;
108 ret->n = 10;
109 ret->unique = true;
110 ret->first_click_x = ret->first_click_y = -1;
111
112 return ret;
113}
114
115static const struct game_params mines_presets[] = {
116 {9, 9, 10, true, -1, -1},
117 {9, 9, 35, true, -1, -1},
118 {16, 16, 40, true, -1, -1},
119 {16, 16, 99, true, -1, -1},
120#ifndef SMALL_SCREEN
121 {30, 16, 99, true, -1, -1},
122 {30, 16, 170, true, -1, -1},
123#endif
124};
125
126static bool game_fetch_preset(int i, char **name, game_params **params)
127{
128 game_params *ret;
129 char str[80];
130
131 if (i < 0 || i >= lenof(mines_presets))
132 return false;
133
134 ret = snew(game_params);
135 *ret = mines_presets[i];
136
137 sprintf(str, "%dx%d, %d mines", ret->w, ret->h, ret->n);
138
139 *name = dupstr(str);
140 *params = ret;
141 return true;
142}
143
144static void free_params(game_params *params)
145{
146 sfree(params);
147}
148
149static game_params *dup_params(const game_params *params)
150{
151 game_params *ret = snew(game_params);
152 *ret = *params; /* structure copy */
153 return ret;
154}
155
156static void decode_params(game_params *params, char const *string)
157{
158 char const *p = string;
159
160 params->w = atoi(p);
161 while (*p && isdigit((unsigned char)*p)) p++;
162 if (*p == 'x') {
163 p++;
164 params->h = atoi(p);
165 while (*p && isdigit((unsigned char)*p)) p++;
166 } else {
167 params->h = params->w;
168 }
169 if (*p == 'n') {
170 p++;
171 params->n = atoi(p);
172 while (*p && (*p == '.' || isdigit((unsigned char)*p))) p++;
173 } else {
174 if (params->h > 0 && params->w > 0 &&
175 params->w <= INT_MAX / params->h)
176 params->n = params->w * params->h / 10;
177 }
178
179 while (*p) {
180 if (*p == 'a') {
181 p++;
182 params->unique = false;
183 } else if (*p == 'X') {
184 p++;
185 params->first_click_x = atoi(p);
186 while (*p && isdigit((unsigned char)*p)) p++;
187 } else if (*p == 'Y') {
188 p++;
189 params->first_click_y = atoi(p);
190 while (*p && isdigit((unsigned char)*p)) p++;
191 } else
192 p++; /* skip any other gunk */
193 }
194}
195
196static char *encode_params(const game_params *params, bool full)
197{
198 char ret[400];
199 int len;
200
201 len = sprintf(ret, "%dx%d", params->w, params->h);
202 /*
203 * Mine count is a generation-time parameter, since it can be
204 * deduced from the mine bitmap!
205 */
206 if (full)
207 len += sprintf(ret+len, "n%d", params->n);
208 if (full && !params->unique)
209 ret[len++] = 'a';
210 if (full && params->first_click_x >= 0)
211 len += sprintf(ret+len, "X%d", params->first_click_x);
212 if (full && params->first_click_y >= 0)
213 len += sprintf(ret+len, "Y%d", params->first_click_y);
214 assert(len < lenof(ret));
215 ret[len] = '\0';
216
217 return dupstr(ret);
218}
219
220static config_item *game_configure(const game_params *params)
221{
222 config_item *ret;
223 char buf[80];
224
225 ret = snewn(5, config_item);
226
227 ret[0].name = "Width";
228 ret[0].type = C_STRING;
229 sprintf(buf, "%d", params->w);
230 ret[0].u.string.sval = dupstr(buf);
231
232 ret[1].name = "Height";
233 ret[1].type = C_STRING;
234 sprintf(buf, "%d", params->h);
235 ret[1].u.string.sval = dupstr(buf);
236
237 ret[2].name = "Mines";
238 ret[2].type = C_STRING;
239 sprintf(buf, "%d", params->n);
240 ret[2].u.string.sval = dupstr(buf);
241
242 ret[3].name = "Ensure solubility";
243 ret[3].type = C_BOOLEAN;
244 ret[3].u.boolean.bval = params->unique;
245
246 ret[4].name = NULL;
247 ret[4].type = C_END;
248
249 return ret;
250}
251
252static game_params *custom_params(const config_item *cfg)
253{
254 game_params *ret = snew(game_params);
255
256 ret->w = atoi(cfg[0].u.string.sval);
257 ret->h = atoi(cfg[1].u.string.sval);
258 ret->n = atoi(cfg[2].u.string.sval);
259 if (strchr(cfg[2].u.string.sval, '%'))
260 ret->n = ret->n * (ret->w * ret->h) / 100;
261 ret->unique = cfg[3].u.boolean.bval;
262 ret->first_click_x = ret->first_click_y = -1;
263
264 return ret;
265}
266
267static const char *validate_params(const game_params *params, bool full)
268{
269 /*
270 * Lower limit on grid size: each dimension must be at least 3.
271 * 1 is theoretically workable if rather boring, but 2 is a
272 * real problem: there is often _no_ way to generate a uniquely
273 * solvable 2xn Mines grid. You either run into two mines
274 * blocking the way and no idea what's behind them, or one mine
275 * and no way to know which of the two rows it's in. If the
276 * mine count is even you can create a soluble grid by packing
277 * all the mines at one end (so that when you hit a two-mine
278 * wall there are only as many covered squares left as there
279 * are mines); but if it's odd, you are doomed, because you
280 * _have_ to have a gap somewhere which you can't determine the
281 * position of.
282 */
283 if (full && params->unique && (params->w <= 2 || params->h <= 2))
284 return "Width and height must both be greater than two";
285 if (params->w < 1 || params->h < 1)
286 return "Width and height must both be at least one";
287 if (params->w > SHRT_MAX || params->h > SHRT_MAX)
288 return "Neither width nor height may be unreasonably large";
289 /*
290 * We use random_upto() to place mines, and its maximum limit is 2^28-1.
291 */
292#if (1<<28)-1 < INT_MAX
293 if (params->w > ((1<<28)-1) / params->h)
294#else
295 if (params->w > INT_MAX / params->h)
296#endif
297 return "Width times height must not be unreasonably large";
298 if (params->n < 0)
299 return "Mine count may not be negative";
300 if (params->n < 1)
301 return "Number of mines must be greater than zero";
302 if (params->n > params->w * params->h - 9)
303 return "Too many mines for grid size";
304 if (params->first_click_x >= params->w)
305 return "First-click x coordinate must be inside the grid";
306 if (params->first_click_y >= params->h)
307 return "First-click y coordinate must be inside the grid";
308
309 /*
310 * FIXME: Need more constraints here. Not sure what the
311 * sensible limits for Minesweeper actually are. The limits
312 * probably ought to change, however, depending on uniqueness.
313 */
314
315 return NULL;
316}
317
318/* ----------------------------------------------------------------------
319 * Minesweeper solver, used to ensure the generated grids are
320 * solvable without having to take risks.
321 */
322
323/*
324 * Count the bits in a word. Only needs to cope with 16 bits.
325 */
326static int bitcount16(int inword)
327{
328 unsigned int word = inword;
329
330 word = ((word & 0xAAAA) >> 1) + (word & 0x5555);
331 word = ((word & 0xCCCC) >> 2) + (word & 0x3333);
332 word = ((word & 0xF0F0) >> 4) + (word & 0x0F0F);
333 word = ((word & 0xFF00) >> 8) + (word & 0x00FF);
334
335 return (int)word;
336}
337
338/*
339 * We use a tree234 to store a large number of small localised
340 * sets, each with a mine count. We also keep some of those sets
341 * linked together into a to-do list.
342 */
343struct set {
344 short x, y, mask, mines;
345 bool todo;
346 struct set *prev, *next;
347};
348
349static int setcmp(void *av, void *bv)
350{
351 struct set *a = (struct set *)av;
352 struct set *b = (struct set *)bv;
353
354 if (a->y < b->y)
355 return -1;
356 else if (a->y > b->y)
357 return +1;
358 else if (a->x < b->x)
359 return -1;
360 else if (a->x > b->x)
361 return +1;
362 else if (a->mask < b->mask)
363 return -1;
364 else if (a->mask > b->mask)
365 return +1;
366 else
367 return 0;
368}
369
370struct setstore {
371 tree234 *sets;
372 struct set *todo_head, *todo_tail;
373};
374
375static struct setstore *ss_new(void)
376{
377 struct setstore *ss = snew(struct setstore);
378 ss->sets = newtree234(setcmp);
379 ss->todo_head = ss->todo_tail = NULL;
380 return ss;
381}
382
383/*
384 * Take two input sets, in the form (x,y,mask). Munge the first by
385 * taking either its intersection with the second or its difference
386 * with the second. Return the new mask part of the first set.
387 */
388static int setmunge(int x1, int y1, int mask1, int x2, int y2, int mask2,
389 bool diff)
390{
391 /*
392 * Adjust the second set so that it has the same x,y
393 * coordinates as the first.
394 */
395 if (abs(x2-x1) >= 3 || abs(y2-y1) >= 3) {
396 mask2 = 0;
397 } else {
398 while (x2 > x1) {
399 mask2 &= ~(4|32|256);
400 mask2 <<= 1;
401 x2--;
402 }
403 while (x2 < x1) {
404 mask2 &= ~(1|8|64);
405 mask2 >>= 1;
406 x2++;
407 }
408 while (y2 > y1) {
409 mask2 &= ~(64|128|256);
410 mask2 <<= 3;
411 y2--;
412 }
413 while (y2 < y1) {
414 mask2 &= ~(1|2|4);
415 mask2 >>= 3;
416 y2++;
417 }
418 }
419
420 /*
421 * Invert the second set if `diff' is set (we're after A &~ B
422 * rather than A & B).
423 */
424 if (diff)
425 mask2 ^= 511;
426
427 /*
428 * Now all that's left is a logical AND.
429 */
430 return mask1 & mask2;
431}
432
433static void ss_add_todo(struct setstore *ss, struct set *s)
434{
435 if (s->todo)
436 return; /* already on it */
437
438#ifdef SOLVER_DIAGNOSTICS
439 printf("adding set on todo list: %d,%d %03x %d\n",
440 s->x, s->y, s->mask, s->mines);
441#endif
442
443 s->prev = ss->todo_tail;
444 if (s->prev)
445 s->prev->next = s;
446 else
447 ss->todo_head = s;
448 ss->todo_tail = s;
449 s->next = NULL;
450 s->todo = true;
451}
452
453static void ss_add(struct setstore *ss, int x, int y, int mask, int mines)
454{
455 struct set *s;
456
457 assert(mask != 0);
458
459 /*
460 * Normalise so that x and y are genuinely the bounding
461 * rectangle.
462 */
463 while (!(mask & (1|8|64)))
464 mask >>= 1, x++;
465 while (!(mask & (1|2|4)))
466 mask >>= 3, y++;
467
468 /*
469 * Create a set structure and add it to the tree.
470 */
471 s = snew(struct set);
472 assert(SHRT_MIN <= x && x <= SHRT_MAX);
473 s->x = x;
474 assert(SHRT_MIN <= y && y <= SHRT_MAX);
475 s->y = y;
476 s->mask = mask;
477 s->mines = mines;
478 s->todo = false;
479 if (add234(ss->sets, s) != s) {
480 /*
481 * This set already existed! Free it and return.
482 */
483 sfree(s);
484 return;
485 }
486
487 /*
488 * We've added a new set to the tree, so put it on the todo
489 * list.
490 */
491 ss_add_todo(ss, s);
492}
493
494static void ss_remove(struct setstore *ss, struct set *s)
495{
496 struct set *next = s->next, *prev = s->prev;
497
498#ifdef SOLVER_DIAGNOSTICS
499 printf("removing set %d,%d %03x\n", s->x, s->y, s->mask);
500#endif
501 /*
502 * Remove s from the todo list.
503 */
504 if (prev)
505 prev->next = next;
506 else if (s == ss->todo_head)
507 ss->todo_head = next;
508
509 if (next)
510 next->prev = prev;
511 else if (s == ss->todo_tail)
512 ss->todo_tail = prev;
513
514 s->todo = false;
515
516 /*
517 * Remove s from the tree.
518 */
519 del234(ss->sets, s);
520
521 /*
522 * Destroy the actual set structure.
523 */
524 sfree(s);
525}
526
527/*
528 * Return a dynamically allocated list of all the sets which
529 * overlap a provided input set.
530 */
531static struct set **ss_overlap(struct setstore *ss, int x, int y, int mask)
532{
533 struct set **ret = NULL;
534 int nret = 0, retsize = 0;
535 int xx, yy;
536
537 for (xx = x-3; xx < x+3; xx++)
538 for (yy = y-3; yy < y+3; yy++) {
539 struct set stmp, *s;
540 int pos;
541
542 /*
543 * Find the first set with these top left coordinates.
544 */
545 assert(SHRT_MIN <= xx && xx <= SHRT_MAX);
546 stmp.x = xx;
547 assert(SHRT_MIN <= yy && yy <= SHRT_MAX);
548 stmp.y = yy;
549 stmp.mask = 0;
550
551 if (findrelpos234(ss->sets, &stmp, NULL, REL234_GE, &pos)) {
552 while ((s = index234(ss->sets, pos)) != NULL &&
553 s->x == xx && s->y == yy) {
554 /*
555 * This set potentially overlaps the input one.
556 * Compute the intersection to see if they
557 * really overlap, and add it to the list if
558 * so.
559 */
560 if (setmunge(x, y, mask, s->x, s->y, s->mask, false)) {
561 /*
562 * There's an overlap.
563 */
564 if (nret >= retsize) {
565 retsize = nret + 32;
566 ret = sresize(ret, retsize, struct set *);
567 }
568 ret[nret++] = s;
569 }
570
571 pos++;
572 }
573 }
574 }
575
576 ret = sresize(ret, nret+1, struct set *);
577 ret[nret] = NULL;
578
579 return ret;
580}
581
582/*
583 * Get an element from the head of the set todo list.
584 */
585static struct set *ss_todo(struct setstore *ss)
586{
587 if (ss->todo_head) {
588 struct set *ret = ss->todo_head;
589 ss->todo_head = ret->next;
590 if (ss->todo_head)
591 ss->todo_head->prev = NULL;
592 else
593 ss->todo_tail = NULL;
594 ret->next = ret->prev = NULL;
595 ret->todo = false;
596 return ret;
597 } else {
598 return NULL;
599 }
600}
601
602struct squaretodo {
603 int *next;
604 int head, tail;
605};
606
607static void std_add(struct squaretodo *std, int i)
608{
609 if (std->tail >= 0)
610 std->next[std->tail] = i;
611 else
612 std->head = i;
613 std->tail = i;
614 std->next[i] = -1;
615}
616
617typedef int (*open_cb)(void *, int, int);
618
619static void known_squares(int w, int h, struct squaretodo *std,
620 signed char *grid,
621 open_cb open, void *openctx,
622 int x, int y, int mask, bool mine)
623{
624 int xx, yy, bit;
625
626 bit = 1;
627
628 for (yy = 0; yy < 3; yy++)
629 for (xx = 0; xx < 3; xx++) {
630 if (mask & bit) {
631 int i = (y + yy) * w + (x + xx);
632
633 /*
634 * It's possible that this square is _already_
635 * known, in which case we don't try to add it to
636 * the list twice.
637 */
638 if (grid[i] == -2) {
639
640 if (mine) {
641 grid[i] = -1; /* and don't open it! */
642 } else {
643 grid[i] = open(openctx, x + xx, y + yy);
644 assert(grid[i] != -1); /* *bang* */
645 }
646 std_add(std, i);
647
648 }
649 }
650 bit <<= 1;
651 }
652}
653
654/*
655 * This is data returned from the `perturb' function. It details
656 * which squares have become mines and which have become clear. The
657 * solver is (of course) expected to honourably not use that
658 * knowledge directly, but to efficently adjust its internal data
659 * structures and proceed based on only the information it
660 * legitimately has.
661 */
662struct perturbation {
663 int x, y;
664 int delta; /* +1 == become a mine; -1 == cleared */
665};
666struct perturbations {
667 int n;
668 struct perturbation *changes;
669};
670
671/*
672 * Main solver entry point. You give it a grid of existing
673 * knowledge (-1 for a square known to be a mine, 0-8 for empty
674 * squares with a given number of neighbours, -2 for completely
675 * unknown), plus a function which you can call to open new squares
676 * once you're confident of them. It fills in as much more of the
677 * grid as it can.
678 *
679 * Return value is:
680 *
681 * - -1 means deduction stalled and nothing could be done
682 * - 0 means deduction succeeded fully
683 * - >0 means deduction succeeded but some number of perturbation
684 * steps were required; the exact return value is the number of
685 * perturb calls.
686 */
687
688typedef struct perturbations *(*perturb_cb) (void *, signed char *, int, int, int);
689
690static int minesolve(int w, int h, int n, signed char *grid,
691 open_cb open,
692 perturb_cb perturb,
693 void *ctx, random_state *rs)
694{
695 struct setstore *ss = ss_new();
696 struct set **list;
697 struct squaretodo astd, *std = &astd;
698 int x, y, i, j;
699 int nperturbs = 0;
700
701 /*
702 * Set up a linked list of squares with known contents, so that
703 * we can process them one by one.
704 */
705 std->next = snewn(w*h, int);
706 std->head = std->tail = -1;
707
708 /*
709 * Initialise that list with all known squares in the input
710 * grid.
711 */
712 for (y = 0; y < h; y++) {
713 for (x = 0; x < w; x++) {
714 i = y*w+x;
715 if (grid[i] != -2)
716 std_add(std, i);
717 }
718 }
719
720 /*
721 * Main deductive loop.
722 */
723 while (1) {
724 bool done_something = false;
725 struct set *s;
726
727 /*
728 * If there are any known squares on the todo list, process
729 * them and construct a set for each.
730 */
731 while (std->head != -1) {
732 i = std->head;
733#ifdef SOLVER_DIAGNOSTICS
734 printf("known square at %d,%d [%d]\n", i%w, i/w, grid[i]);
735#endif
736 std->head = std->next[i];
737 if (std->head == -1)
738 std->tail = -1;
739
740 x = i % w;
741 y = i / w;
742
743 if (grid[i] >= 0) {
744 int dx, dy, mines, bit, val;
745#ifdef SOLVER_DIAGNOSTICS
746 printf("creating set around this square\n");
747#endif
748 /*
749 * Empty square. Construct the set of non-known squares
750 * around this one, and determine its mine count.
751 */
752 mines = grid[i];
753 bit = 1;
754 val = 0;
755 for (dy = -1; dy <= +1; dy++) {
756 for (dx = -1; dx <= +1; dx++) {
757 if (x+dx < 0 || x+dx >= w || y+dy < 0 || y+dy >= h) {
758 /* ignore this one */;
759 } else {
760#ifdef SOLVER_DIAGNOSTICS
761 printf("grid %d,%d = %d\n", x+dx, y+dy, grid[i+dy*w+dx]);
762#endif
763 if (grid[i+dy*w+dx] == -1)
764 mines--;
765 else if (grid[i+dy*w+dx] == -2)
766 val |= bit;
767 }
768 bit <<= 1;
769 }
770 }
771 if (val)
772 ss_add(ss, x-1, y-1, val, mines);
773 }
774
775 /*
776 * Now, whether the square is empty or full, we must
777 * find any set which contains it and replace it with
778 * one which does not.
779 */
780 {
781#ifdef SOLVER_DIAGNOSTICS
782 printf("finding sets containing known square %d,%d\n", x, y);
783#endif
784 list = ss_overlap(ss, x, y, 1);
785
786 for (j = 0; list[j]; j++) {
787 int newmask, newmines;
788
789 s = list[j];
790
791 /*
792 * Compute the mask for this set minus the
793 * newly known square.
794 */
795 newmask = setmunge(s->x, s->y, s->mask, x, y, 1, true);
796
797 /*
798 * Compute the new mine count.
799 */
800 newmines = s->mines - (grid[i] == -1);
801
802 /*
803 * Insert the new set into the collection,
804 * unless it's been whittled right down to
805 * nothing.
806 */
807 if (newmask)
808 ss_add(ss, s->x, s->y, newmask, newmines);
809
810 /*
811 * Destroy the old one; it is actually obsolete.
812 */
813 ss_remove(ss, s);
814 }
815
816 sfree(list);
817 }
818
819 /*
820 * Marking a fresh square as known certainly counts as
821 * doing something.
822 */
823 done_something = true;
824 }
825
826 /*
827 * Now pick a set off the to-do list and attempt deductions
828 * based on it.
829 */
830 if ((s = ss_todo(ss)) != NULL) {
831
832#ifdef SOLVER_DIAGNOSTICS
833 printf("set to do: %d,%d %03x %d\n", s->x, s->y, s->mask, s->mines);
834#endif
835 /*
836 * Firstly, see if this set has a mine count of zero or
837 * of its own cardinality.
838 */
839 if (s->mines == 0 || s->mines == bitcount16(s->mask)) {
840 /*
841 * If so, we can immediately mark all the squares
842 * in the set as known.
843 */
844#ifdef SOLVER_DIAGNOSTICS
845 printf("easy\n");
846#endif
847 known_squares(w, h, std, grid, open, ctx,
848 s->x, s->y, s->mask, (s->mines != 0));
849
850 /*
851 * Having done that, we need do nothing further
852 * with this set; marking all the squares in it as
853 * known will eventually eliminate it, and will
854 * also permit further deductions about anything
855 * that overlaps it.
856 */
857 continue;
858 }
859
860 /*
861 * Failing that, we now search through all the sets
862 * which overlap this one.
863 */
864 list = ss_overlap(ss, s->x, s->y, s->mask);
865
866 for (j = 0; list[j]; j++) {
867 struct set *s2 = list[j];
868 int swing, s2wing, swc, s2wc;
869
870 /*
871 * Find the non-overlapping parts s2-s and s-s2,
872 * and their cardinalities.
873 *
874 * I'm going to refer to these parts as `wings'
875 * surrounding the central part common to both
876 * sets. The `s wing' is s-s2; the `s2 wing' is
877 * s2-s.
878 */
879 swing = setmunge(s->x, s->y, s->mask, s2->x, s2->y, s2->mask,
880 true);
881 s2wing = setmunge(s2->x, s2->y, s2->mask, s->x, s->y, s->mask,
882 true);
883 swc = bitcount16(swing);
884 s2wc = bitcount16(s2wing);
885
886 /*
887 * If one set has more mines than the other, and
888 * the number of extra mines is equal to the
889 * cardinality of that set's wing, then we can mark
890 * every square in the wing as a known mine, and
891 * every square in the other wing as known clear.
892 */
893 if (swc == s->mines - s2->mines ||
894 s2wc == s2->mines - s->mines) {
895 known_squares(w, h, std, grid, open, ctx,
896 s->x, s->y, swing,
897 (swc == s->mines - s2->mines));
898 known_squares(w, h, std, grid, open, ctx,
899 s2->x, s2->y, s2wing,
900 (s2wc == s2->mines - s->mines));
901 continue;
902 }
903
904 /*
905 * Failing that, see if one set is a subset of the
906 * other. If so, we can divide up the mine count of
907 * the larger set between the smaller set and its
908 * complement, even if neither smaller set ends up
909 * being immediately clearable.
910 */
911 if (swc == 0 && s2wc != 0) {
912 /* s is a subset of s2. */
913 assert(s2->mines > s->mines);
914 ss_add(ss, s2->x, s2->y, s2wing, s2->mines - s->mines);
915 } else if (s2wc == 0 && swc != 0) {
916 /* s2 is a subset of s. */
917 assert(s->mines > s2->mines);
918 ss_add(ss, s->x, s->y, swing, s->mines - s2->mines);
919 }
920 }
921
922 sfree(list);
923
924 /*
925 * In this situation we have definitely done
926 * _something_, even if it's only reducing the size of
927 * our to-do list.
928 */
929 done_something = true;
930 } else if (n >= 0) {
931 /*
932 * We have nothing left on our todo list, which means
933 * all localised deductions have failed. Our next step
934 * is to resort to global deduction based on the total
935 * mine count. This is computationally expensive
936 * compared to any of the above deductions, which is
937 * why we only ever do it when all else fails, so that
938 * hopefully it won't have to happen too often.
939 *
940 * If you pass n<0 into this solver, that informs it
941 * that you do not know the total mine count, so it
942 * won't even attempt these deductions.
943 */
944
945 int minesleft, squaresleft;
946 int nsets, cursor;
947 bool setused[10];
948
949 /*
950 * Start by scanning the current grid state to work out
951 * how many unknown squares we still have, and how many
952 * mines are to be placed in them.
953 */
954 squaresleft = 0;
955 minesleft = n;
956 for (i = 0; i < w*h; i++) {
957 if (grid[i] == -1)
958 minesleft--;
959 else if (grid[i] == -2)
960 squaresleft++;
961 }
962
963#ifdef SOLVER_DIAGNOSTICS
964 printf("global deduction time: squaresleft=%d minesleft=%d\n",
965 squaresleft, minesleft);
966 for (y = 0; y < h; y++) {
967 for (x = 0; x < w; x++) {
968 int v = grid[y*w+x];
969 if (v == -1)
970 putchar('*');
971 else if (v == -2)
972 putchar('?');
973 else if (v == 0)
974 putchar('-');
975 else
976 putchar('0' + v);
977 }
978 putchar('\n');
979 }
980#endif
981
982 /*
983 * If there _are_ no unknown squares, we have actually
984 * finished.
985 */
986 if (squaresleft == 0) {
987 assert(minesleft == 0);
988 break;
989 }
990
991 /*
992 * First really simple case: if there are no more mines
993 * left, or if there are exactly as many mines left as
994 * squares to play them in, then it's all easy.
995 */
996 if (minesleft == 0 || minesleft == squaresleft) {
997 for (i = 0; i < w*h; i++)
998 if (grid[i] == -2)
999 known_squares(w, h, std, grid, open, ctx,
1000 i % w, i / w, 1, minesleft != 0);
1001 continue; /* now go back to main deductive loop */
1002 }
1003
1004 /*
1005 * Failing that, we have to do some _real_ work.
1006 * Ideally what we do here is to try every single
1007 * combination of the currently available sets, in an
1008 * attempt to find a disjoint union (i.e. a set of
1009 * squares with a known mine count between them) such
1010 * that the remaining unknown squares _not_ contained
1011 * in that union either contain no mines or are all
1012 * mines.
1013 *
1014 * Actually enumerating all 2^n possibilities will get
1015 * a bit slow for large n, so I artificially cap this
1016 * recursion at n=10 to avoid too much pain.
1017 */
1018 nsets = count234(ss->sets);
1019 if (nsets <= lenof(setused)) {
1020 /*
1021 * Doing this with actual recursive function calls
1022 * would get fiddly because a load of local
1023 * variables from this function would have to be
1024 * passed down through the recursion. So instead
1025 * I'm going to use a virtual recursion within this
1026 * function. The way this works is:
1027 *
1028 * - we have an array `setused', such that setused[n]
1029 * is true if set n is currently in the union we
1030 * are considering.
1031 *
1032 * - we have a value `cursor' which indicates how
1033 * much of `setused' we have so far filled in.
1034 * It's conceptually the recursion depth.
1035 *
1036 * We begin by setting `cursor' to zero. Then:
1037 *
1038 * - if cursor can advance, we advance it by one. We
1039 * set the value in `setused' that it went past to
1040 * true if that set is disjoint from anything else
1041 * currently in `setused', or to false otherwise.
1042 *
1043 * - If cursor cannot advance because it has
1044 * reached the end of the setused list, then we
1045 * have a maximal disjoint union. Check to see
1046 * whether its mine count has any useful
1047 * properties. If so, mark all the squares not
1048 * in the union as known and terminate.
1049 *
1050 * - If cursor has reached the end of setused and the
1051 * algorithm _hasn't_ terminated, back cursor up to
1052 * the nearest true entry, reset it to false, and
1053 * advance cursor just past it.
1054 *
1055 * - If we attempt to back up to the nearest 1 and
1056 * there isn't one at all, then we have gone
1057 * through all disjoint unions of sets in the
1058 * list and none of them has been helpful, so we
1059 * give up.
1060 */
1061 struct set *sets[lenof(setused)];
1062 for (i = 0; i < nsets; i++)
1063 sets[i] = index234(ss->sets, i);
1064
1065 cursor = 0;
1066 while (1) {
1067
1068 if (cursor < nsets) {
1069 bool ok = true;
1070
1071 /* See if any existing set overlaps this one. */
1072 for (i = 0; i < cursor; i++)
1073 if (setused[i] &&
1074 setmunge(sets[cursor]->x,
1075 sets[cursor]->y,
1076 sets[cursor]->mask,
1077 sets[i]->x, sets[i]->y, sets[i]->mask,
1078 false)) {
1079 ok = false;
1080 break;
1081 }
1082
1083 if (ok) {
1084 /*
1085 * We're adding this set to our union,
1086 * so adjust minesleft and squaresleft
1087 * appropriately.
1088 */
1089 minesleft -= sets[cursor]->mines;
1090 squaresleft -= bitcount16(sets[cursor]->mask);
1091 }
1092
1093 setused[cursor++] = ok;
1094 } else {
1095#ifdef SOLVER_DIAGNOSTICS
1096 printf("trying a set combination with %d %d\n",
1097 squaresleft, minesleft);
1098#endif /* SOLVER_DIAGNOSTICS */
1099
1100 /*
1101 * We've reached the end. See if we've got
1102 * anything interesting.
1103 */
1104 if (squaresleft > 0 &&
1105 (minesleft == 0 || minesleft == squaresleft)) {
1106 /*
1107 * We have! There is at least one
1108 * square not contained within the set
1109 * union we've just found, and we can
1110 * deduce that either all such squares
1111 * are mines or all are not (depending
1112 * on whether minesleft==0). So now all
1113 * we have to do is actually go through
1114 * the grid, find those squares, and
1115 * mark them.
1116 */
1117 for (i = 0; i < w*h; i++)
1118 if (grid[i] == -2) {
1119 bool outside = true;
1120 y = i / w;
1121 x = i % w;
1122 for (j = 0; j < nsets; j++)
1123 if (setused[j] &&
1124 setmunge(sets[j]->x, sets[j]->y,
1125 sets[j]->mask, x, y, 1,
1126 false)) {
1127 outside = false;
1128 break;
1129 }
1130 if (outside)
1131 known_squares(w, h, std, grid,
1132 open, ctx,
1133 x, y, 1, minesleft != 0);
1134 }
1135
1136 done_something = true;
1137 break; /* return to main deductive loop */
1138 }
1139
1140 /*
1141 * If we reach here, then this union hasn't
1142 * done us any good, so move on to the
1143 * next. Backtrack cursor to the nearest 1,
1144 * change it to a 0 and continue.
1145 */
1146 while (--cursor >= 0 && !setused[cursor]);
1147 if (cursor >= 0) {
1148 assert(setused[cursor]);
1149
1150 /*
1151 * We're removing this set from our
1152 * union, so re-increment minesleft and
1153 * squaresleft.
1154 */
1155 minesleft += sets[cursor]->mines;
1156 squaresleft += bitcount16(sets[cursor]->mask);
1157
1158 setused[cursor++] = false;
1159 } else {
1160 /*
1161 * We've backtracked all the way to the
1162 * start without finding a single 1,
1163 * which means that our virtual
1164 * recursion is complete and nothing
1165 * helped.
1166 */
1167 break;
1168 }
1169 }
1170
1171 }
1172
1173 }
1174 }
1175
1176 if (done_something)
1177 continue;
1178
1179#ifdef SOLVER_DIAGNOSTICS
1180 /*
1181 * Dump the current known state of the grid.
1182 */
1183 printf("solver ran out of steam, ret=%d, grid:\n", nperturbs);
1184 for (y = 0; y < h; y++) {
1185 for (x = 0; x < w; x++) {
1186 int v = grid[y*w+x];
1187 if (v == -1)
1188 putchar('*');
1189 else if (v == -2)
1190 putchar('?');
1191 else if (v == 0)
1192 putchar('-');
1193 else
1194 putchar('0' + v);
1195 }
1196 putchar('\n');
1197 }
1198
1199 {
1200 struct set *s;
1201
1202 for (i = 0; (s = index234(ss->sets, i)) != NULL; i++)
1203 printf("remaining set: %d,%d %03x %d\n", s->x, s->y, s->mask, s->mines);
1204 }
1205#endif
1206
1207 /*
1208 * Now we really are at our wits' end as far as solving
1209 * this grid goes. Our only remaining option is to call
1210 * a perturb function and ask it to modify the grid to
1211 * make it easier.
1212 */
1213 if (perturb) {
1214 struct perturbations *ret;
1215 struct set *s;
1216
1217 nperturbs++;
1218
1219 /*
1220 * Choose a set at random from the current selection,
1221 * and ask the perturb function to either fill or empty
1222 * it.
1223 *
1224 * If we have no sets at all, we must give up.
1225 */
1226 if (count234(ss->sets) == 0) {
1227#ifdef SOLVER_DIAGNOSTICS
1228 printf("perturbing on entire unknown set\n");
1229#endif
1230 ret = perturb(ctx, grid, 0, 0, 0);
1231 } else {
1232 s = index234(ss->sets, random_upto(rs, count234(ss->sets)));
1233#ifdef SOLVER_DIAGNOSTICS
1234 printf("perturbing on set %d,%d %03x\n", s->x, s->y, s->mask);
1235#endif
1236 ret = perturb(ctx, grid, s->x, s->y, s->mask);
1237 }
1238
1239 if (ret) {
1240 assert(ret->n > 0); /* otherwise should have been NULL */
1241
1242 /*
1243 * A number of squares have been fiddled with, and
1244 * the returned structure tells us which. Adjust
1245 * the mine count in any set which overlaps one of
1246 * those squares, and put them back on the to-do
1247 * list. Also, if the square itself is marked as a
1248 * known non-mine, put it back on the squares-to-do
1249 * list.
1250 */
1251 for (i = 0; i < ret->n; i++) {
1252#ifdef SOLVER_DIAGNOSTICS
1253 printf("perturbation %s mine at %d,%d\n",
1254 ret->changes[i].delta > 0 ? "added" : "removed",
1255 ret->changes[i].x, ret->changes[i].y);
1256#endif
1257
1258 if (ret->changes[i].delta < 0 &&
1259 grid[ret->changes[i].y*w+ret->changes[i].x] != -2) {
1260 std_add(std, ret->changes[i].y*w+ret->changes[i].x);
1261 }
1262
1263 list = ss_overlap(ss,
1264 ret->changes[i].x, ret->changes[i].y, 1);
1265
1266 for (j = 0; list[j]; j++) {
1267 list[j]->mines += ret->changes[i].delta;
1268 ss_add_todo(ss, list[j]);
1269 }
1270
1271 sfree(list);
1272 }
1273
1274 /*
1275 * Now free the returned data.
1276 */
1277 sfree(ret->changes);
1278 sfree(ret);
1279
1280#ifdef SOLVER_DIAGNOSTICS
1281 /*
1282 * Dump the current known state of the grid.
1283 */
1284 printf("state after perturbation:\n");
1285 for (y = 0; y < h; y++) {
1286 for (x = 0; x < w; x++) {
1287 int v = grid[y*w+x];
1288 if (v == -1)
1289 putchar('*');
1290 else if (v == -2)
1291 putchar('?');
1292 else if (v == 0)
1293 putchar('-');
1294 else
1295 putchar('0' + v);
1296 }
1297 putchar('\n');
1298 }
1299
1300 {
1301 struct set *s;
1302
1303 for (i = 0; (s = index234(ss->sets, i)) != NULL; i++)
1304 printf("remaining set: %d,%d %03x %d\n", s->x, s->y, s->mask, s->mines);
1305 }
1306#endif
1307
1308 /*
1309 * And now we can go back round the deductive loop.
1310 */
1311 continue;
1312 }
1313 }
1314
1315 /*
1316 * If we get here, even that didn't work (either we didn't
1317 * have a perturb function or it returned failure), so we
1318 * give up entirely.
1319 */
1320 break;
1321 }
1322
1323 /*
1324 * See if we've got any unknown squares left.
1325 */
1326 for (y = 0; y < h; y++)
1327 for (x = 0; x < w; x++)
1328 if (grid[y*w+x] == -2) {
1329 nperturbs = -1; /* failed to complete */
1330 break;
1331 }
1332
1333 /*
1334 * Free the set list and square-todo list.
1335 */
1336 {
1337 struct set *s;
1338 while ((s = delpos234(ss->sets, 0)) != NULL)
1339 sfree(s);
1340 freetree234(ss->sets);
1341 sfree(ss);
1342 sfree(std->next);
1343 }
1344
1345 return nperturbs;
1346}
1347
1348/* ----------------------------------------------------------------------
1349 * Grid generator which uses the above solver.
1350 */
1351
1352struct minectx {
1353 bool *grid, *opened;
1354 int w, h;
1355 int sx, sy;
1356 bool allow_big_perturbs;
1357 int nperturbs_since_last_new_open;
1358 random_state *rs;
1359};
1360
1361static int mineopen(void *vctx, int x, int y)
1362{
1363 struct minectx *ctx = (struct minectx *)vctx;
1364 int i, j, n;
1365
1366 assert(x >= 0 && x < ctx->w && y >= 0 && y < ctx->h);
1367 if (ctx->grid[y * ctx->w + x])
1368 return -1; /* *bang* */
1369
1370 if (!ctx->opened[y * ctx->w + x]) {
1371 ctx->opened[y * ctx->w + x] = true;
1372 ctx->nperturbs_since_last_new_open = 0;
1373 }
1374
1375 n = 0;
1376 for (i = -1; i <= +1; i++) {
1377 if (x + i < 0 || x + i >= ctx->w)
1378 continue;
1379 for (j = -1; j <= +1; j++) {
1380 if (y + j < 0 || y + j >= ctx->h)
1381 continue;
1382 if (i == 0 && j == 0)
1383 continue;
1384 if (ctx->grid[(y+j) * ctx->w + (x+i)])
1385 n++;
1386 }
1387 }
1388
1389 return n;
1390}
1391
1392/* Structure used internally to mineperturb(). */
1393struct square {
1394 int x, y, type, random;
1395};
1396static int squarecmp(const void *av, const void *bv)
1397{
1398 const struct square *a = (const struct square *)av;
1399 const struct square *b = (const struct square *)bv;
1400 if (a->type < b->type)
1401 return -1;
1402 else if (a->type > b->type)
1403 return +1;
1404 else if (a->random < b->random)
1405 return -1;
1406 else if (a->random > b->random)
1407 return +1;
1408 else if (a->y < b->y)
1409 return -1;
1410 else if (a->y > b->y)
1411 return +1;
1412 else if (a->x < b->x)
1413 return -1;
1414 else if (a->x > b->x)
1415 return +1;
1416 return 0;
1417}
1418
1419/*
1420 * Normally this function is passed an (x,y,mask) set description.
1421 * On occasions, though, there is no _localised_ set being used,
1422 * and the set being perturbed is supposed to be the entirety of
1423 * the unreachable area. This is signified by the special case
1424 * mask==0: in this case, anything labelled -2 in the grid is part
1425 * of the set.
1426 *
1427 * Allowing perturbation in this special case appears to make it
1428 * guaranteeably possible to generate a workable grid for any mine
1429 * density, but they tend to be a bit boring, with mines packed
1430 * densely into far corners of the grid and the remainder being
1431 * less dense than one might like. Therefore, to improve overall
1432 * grid quality I disable this feature for the first few attempts,
1433 * and fall back to it after no useful grid has been generated.
1434 */
1435static struct perturbations *mineperturb(void *vctx, signed char *grid,
1436 int setx, int sety, int mask)
1437{
1438 struct minectx *ctx = (struct minectx *)vctx;
1439 struct square *sqlist;
1440 int x, y, dx, dy, i, n, nfull, nempty;
1441 struct square **tofill, **toempty, **todo;
1442 int ntofill, ntoempty, ntodo, dtodo, dset;
1443 struct perturbations *ret;
1444 int *setlist;
1445
1446 if (!mask && !ctx->allow_big_perturbs) {
1447#ifdef GENERATION_DIAGNOSTICS
1448 printf("big perturbs forbidden on this run\n");
1449#endif
1450 return NULL;
1451 }
1452
1453 if (ctx->nperturbs_since_last_new_open++ > ctx->w ||
1454 ctx->nperturbs_since_last_new_open++ > ctx->h) {
1455#ifdef GENERATION_DIAGNOSTICS
1456 printf("too many perturb attempts without opening a new square\n");
1457#endif
1458 return NULL;
1459 }
1460
1461#ifdef GENERATION_DIAGNOSTICS
1462 {
1463 int yy, xx;
1464 printf("grid before perturbing:\n");
1465 for (yy = 0; yy < ctx->h; yy++) {
1466 for (xx = 0; xx < ctx->w; xx++) {
1467 int v = ctx->grid[yy*ctx->w+xx];
1468 if (yy == ctx->sy && xx == ctx->sx) {
1469 assert(!v);
1470 putchar('S');
1471 } else if (v) {
1472 putchar('*');
1473 } else {
1474 putchar('-');
1475 }
1476 }
1477 putchar('\n');
1478 }
1479 printf("\n");
1480 }
1481#endif
1482
1483 /*
1484 * Make a list of all the squares in the grid which we can
1485 * possibly use. This list should be in preference order, which
1486 * means
1487 *
1488 * - first, unknown squares on the boundary of known space
1489 * - next, unknown squares beyond that boundary
1490 * - as a very last resort, known squares, but not within one
1491 * square of the starting position.
1492 *
1493 * Each of these sections needs to be shuffled independently.
1494 * We do this by preparing list of all squares and then sorting
1495 * it with a random secondary key.
1496 */
1497 sqlist = snewn(ctx->w * ctx->h, struct square);
1498 n = 0;
1499 for (y = 0; y < ctx->h; y++)
1500 for (x = 0; x < ctx->w; x++) {
1501 /*
1502 * If this square is too near the starting position,
1503 * don't put it on the list at all.
1504 */
1505 if (abs(y - ctx->sy) <= 1 && abs(x - ctx->sx) <= 1)
1506 continue;
1507
1508 /*
1509 * If this square is in the input set, also don't put
1510 * it on the list!
1511 */
1512 if ((mask == 0 && grid[y*ctx->w+x] == -2) ||
1513 (x >= setx && x < setx + 3 &&
1514 y >= sety && y < sety + 3 &&
1515 mask & (1 << ((y-sety)*3+(x-setx)))))
1516 continue;
1517
1518 sqlist[n].x = x;
1519 sqlist[n].y = y;
1520
1521 if (grid[y*ctx->w+x] != -2) {
1522 sqlist[n].type = 3; /* known square */
1523 } else {
1524 /*
1525 * Unknown square. Examine everything around it and
1526 * see if it borders on any known squares. If it
1527 * does, it's class 1, otherwise it's 2.
1528 */
1529
1530 sqlist[n].type = 2;
1531
1532 for (dy = -1; dy <= +1; dy++)
1533 for (dx = -1; dx <= +1; dx++)
1534 if (x+dx >= 0 && x+dx < ctx->w &&
1535 y+dy >= 0 && y+dy < ctx->h &&
1536 grid[(y+dy)*ctx->w+(x+dx)] != -2) {
1537 sqlist[n].type = 1;
1538 break;
1539 }
1540 }
1541
1542 /*
1543 * Finally, a random number to cause qsort to
1544 * shuffle within each group.
1545 */
1546 sqlist[n].random = random_bits(ctx->rs, 31);
1547
1548 n++;
1549 }
1550
1551 qsort(sqlist, n, sizeof(struct square), squarecmp);
1552
1553 /*
1554 * Now count up the number of full and empty squares in the set
1555 * we've been provided.
1556 */
1557#ifdef GENERATION_DIAGNOSTICS
1558 printf("perturb wants to fill or empty these squares:");
1559#endif
1560 nfull = nempty = 0;
1561 if (mask) {
1562 for (dy = 0; dy < 3; dy++)
1563 for (dx = 0; dx < 3; dx++)
1564 if (mask & (1 << (dy*3+dx))) {
1565#ifdef GENERATION_DIAGNOSTICS
1566 printf(" (%d,%d)", setx+dx, sety+dy);
1567#endif
1568 assert(setx+dx <= ctx->w);
1569 assert(sety+dy <= ctx->h);
1570 if (ctx->grid[(sety+dy)*ctx->w+(setx+dx)])
1571 nfull++;
1572 else
1573 nempty++;
1574 }
1575 } else {
1576 for (y = 0; y < ctx->h; y++)
1577 for (x = 0; x < ctx->w; x++)
1578 if (grid[y*ctx->w+x] == -2) {
1579#ifdef GENERATION_DIAGNOSTICS
1580 printf(" (%d,%d)", x, y);
1581#endif
1582 if (ctx->grid[y*ctx->w+x])
1583 nfull++;
1584 else
1585 nempty++;
1586 }
1587 }
1588
1589#ifdef GENERATION_DIAGNOSTICS
1590 {
1591 int i;
1592 printf("\nperturb set includes %d full, %d empty\n", nfull, nempty);
1593 printf("source squares in preference order:");
1594 for (i = 0; i < n; i++)
1595 printf(" (%d,%d)", sqlist[i].x, sqlist[i].y);
1596 printf("\n");
1597 }
1598#endif
1599
1600 /*
1601 * Now go through our sorted list until we find either `nfull'
1602 * empty squares, or `nempty' full squares; these will be
1603 * swapped with the appropriate squares in the set to either
1604 * fill or empty the set while keeping the same number of mines
1605 * overall.
1606 */
1607 ntofill = ntoempty = 0;
1608 if (mask) {
1609 tofill = snewn(9, struct square *);
1610 toempty = snewn(9, struct square *);
1611 } else {
1612 tofill = snewn(ctx->w * ctx->h, struct square *);
1613 toempty = snewn(ctx->w * ctx->h, struct square *);
1614 }
1615 for (i = 0; i < n; i++) {
1616 struct square *sq = &sqlist[i];
1617 if (ctx->grid[sq->y * ctx->w + sq->x])
1618 toempty[ntoempty++] = sq;
1619 else
1620 tofill[ntofill++] = sq;
1621 if (ntofill == nfull || ntoempty == nempty)
1622 break;
1623 }
1624
1625#ifdef GENERATION_DIAGNOSTICS
1626 printf("can fill %d (of %d) or empty %d (of %d)\n",
1627 ntofill, nfull, ntoempty, nempty);
1628#endif
1629
1630 /*
1631 * If we haven't found enough empty squares outside the set to
1632 * empty it into _or_ enough full squares outside it to fill it
1633 * up with, we'll have to settle for doing only a partial job.
1634 * In this case we choose to always _fill_ the set (because
1635 * this case will tend to crop up when we're working with very
1636 * high mine densities and the only way to get a solvable grid
1637 * is going to be to pack most of the mines solidly around the
1638 * edges). So now our job is to make a list of the empty
1639 * squares in the set, and shuffle that list so that we fill a
1640 * random selection of them.
1641 */
1642 if (ntofill != nfull && ntoempty != nempty) {
1643 int k;
1644
1645 assert(ntoempty != 0);
1646
1647 setlist = snewn(ctx->w * ctx->h, int);
1648 i = 0;
1649 if (mask) {
1650 for (dy = 0; dy < 3; dy++)
1651 for (dx = 0; dx < 3; dx++)
1652 if (mask & (1 << (dy*3+dx))) {
1653 assert(setx+dx <= ctx->w);
1654 assert(sety+dy <= ctx->h);
1655 if (!ctx->grid[(sety+dy)*ctx->w+(setx+dx)])
1656 setlist[i++] = (sety+dy)*ctx->w+(setx+dx);
1657 }
1658 } else {
1659 for (y = 0; y < ctx->h; y++)
1660 for (x = 0; x < ctx->w; x++)
1661 if (grid[y*ctx->w+x] == -2) {
1662 if (!ctx->grid[y*ctx->w+x])
1663 setlist[i++] = y*ctx->w+x;
1664 }
1665 }
1666 assert(i > ntoempty);
1667 /*
1668 * Now pick `ntoempty' items at random from the list.
1669 */
1670#ifdef GENERATION_DIAGNOSTICS
1671 printf("doing a partial fill:");
1672#endif
1673
1674 for (k = 0; k < ntoempty; k++) {
1675 int index = k + random_upto(ctx->rs, i - k);
1676 int tmp;
1677
1678 tmp = setlist[k];
1679 setlist[k] = setlist[index];
1680 setlist[index] = tmp;
1681
1682#ifdef GENERATION_DIAGNOSTICS
1683 printf(" (%d,%d)", setlist[index] % ctx->w,
1684 setlist[index] / ctx->w);
1685#endif
1686 }
1687#ifdef GENERATION_DIAGNOSTICS
1688 printf("\n");
1689#endif
1690 } else
1691 setlist = NULL;
1692
1693 /*
1694 * Now we're pretty much there. We need to either
1695 * (a) put a mine in each of the empty squares in the set, and
1696 * take one out of each square in `toempty'
1697 * (b) take a mine out of each of the full squares in the set,
1698 * and put one in each square in `tofill'
1699 * depending on which one we've found enough squares to do.
1700 *
1701 * So we start by constructing our list of changes to return to
1702 * the solver, so that it can update its data structures
1703 * efficiently rather than having to rescan the whole grid.
1704 */
1705 ret = snew(struct perturbations);
1706 if (ntofill == nfull) {
1707 todo = tofill;
1708 ntodo = ntofill;
1709 dtodo = +1;
1710 dset = -1;
1711 sfree(toempty);
1712 } else {
1713 /*
1714 * (We also fall into this case if we've constructed a
1715 * setlist.)
1716 */
1717 todo = toempty;
1718 ntodo = ntoempty;
1719 dtodo = -1;
1720 dset = +1;
1721 sfree(tofill);
1722 }
1723 ret->n = 2 * ntodo;
1724 ret->changes = snewn(ret->n, struct perturbation);
1725 for (i = 0; i < ntodo; i++) {
1726 ret->changes[i].x = todo[i]->x;
1727 ret->changes[i].y = todo[i]->y;
1728 ret->changes[i].delta = dtodo;
1729 }
1730 /* now i == ntodo */
1731 if (setlist) {
1732 int j;
1733 assert(todo == toempty);
1734 for (j = 0; j < ntoempty; j++) {
1735 ret->changes[i].x = setlist[j] % ctx->w;
1736 ret->changes[i].y = setlist[j] / ctx->w;
1737 ret->changes[i].delta = dset;
1738 i++;
1739 }
1740 sfree(setlist);
1741 } else if (mask) {
1742 for (dy = 0; dy < 3; dy++)
1743 for (dx = 0; dx < 3; dx++)
1744 if (mask & (1 << (dy*3+dx))) {
1745 int currval = (ctx->grid[(sety+dy)*ctx->w+(setx+dx)] ? +1 : -1);
1746 if (dset == -currval) {
1747 ret->changes[i].x = setx + dx;
1748 ret->changes[i].y = sety + dy;
1749 ret->changes[i].delta = dset;
1750 i++;
1751 }
1752 }
1753 } else {
1754 for (y = 0; y < ctx->h; y++)
1755 for (x = 0; x < ctx->w; x++)
1756 if (grid[y*ctx->w+x] == -2) {
1757 int currval = (ctx->grid[y*ctx->w+x] ? +1 : -1);
1758 if (dset == -currval) {
1759 ret->changes[i].x = x;
1760 ret->changes[i].y = y;
1761 ret->changes[i].delta = dset;
1762 i++;
1763 }
1764 }
1765 }
1766 assert(i == ret->n);
1767
1768 sfree(sqlist);
1769 sfree(todo);
1770
1771 /*
1772 * Having set up the precise list of changes we're going to
1773 * make, we now simply make them and return.
1774 */
1775 for (i = 0; i < ret->n; i++) {
1776 int delta;
1777
1778 x = ret->changes[i].x;
1779 y = ret->changes[i].y;
1780 delta = ret->changes[i].delta;
1781
1782 /*
1783 * Check we're not trying to add an existing mine or remove
1784 * an absent one.
1785 */
1786 assert((delta < 0) ^ (ctx->grid[y*ctx->w+x] == 0));
1787
1788 /*
1789 * Actually make the change.
1790 */
1791 ctx->grid[y*ctx->w+x] = (delta > 0);
1792
1793 /*
1794 * Update any numbers already present in the grid.
1795 */
1796 for (dy = -1; dy <= +1; dy++)
1797 for (dx = -1; dx <= +1; dx++)
1798 if (x+dx >= 0 && x+dx < ctx->w &&
1799 y+dy >= 0 && y+dy < ctx->h &&
1800 grid[(y+dy)*ctx->w+(x+dx)] != -2) {
1801 if (dx == 0 && dy == 0) {
1802 /*
1803 * The square itself is marked as known in
1804 * the grid. Mark it as a mine if it's a
1805 * mine, or else work out its number.
1806 */
1807 if (delta > 0) {
1808 grid[y*ctx->w+x] = -1;
1809 } else {
1810 int dx2, dy2, minecount = 0;
1811 for (dy2 = -1; dy2 <= +1; dy2++)
1812 for (dx2 = -1; dx2 <= +1; dx2++)
1813 if (x+dx2 >= 0 && x+dx2 < ctx->w &&
1814 y+dy2 >= 0 && y+dy2 < ctx->h &&
1815 ctx->grid[(y+dy2)*ctx->w+(x+dx2)])
1816 minecount++;
1817 grid[y*ctx->w+x] = minecount;
1818 }
1819 } else {
1820 if (grid[(y+dy)*ctx->w+(x+dx)] >= 0)
1821 grid[(y+dy)*ctx->w+(x+dx)] += delta;
1822 }
1823 }
1824 }
1825
1826#ifdef GENERATION_DIAGNOSTICS
1827 {
1828 int yy, xx;
1829 printf("grid after perturbing:\n");
1830 for (yy = 0; yy < ctx->h; yy++) {
1831 for (xx = 0; xx < ctx->w; xx++) {
1832 int v = ctx->grid[yy*ctx->w+xx];
1833 if (yy == ctx->sy && xx == ctx->sx) {
1834 assert(!v);
1835 putchar('S');
1836 } else if (v) {
1837 putchar('*');
1838 } else {
1839 putchar('-');
1840 }
1841 }
1842 putchar('\n');
1843 }
1844 printf("\n");
1845 }
1846#endif
1847
1848 return ret;
1849}
1850
1851static bool *minegen(int w, int h, int n, int x, int y, bool unique,
1852 random_state *rs)
1853{
1854 bool *ret = snewn(w*h, bool);
1855 bool success;
1856 int ntries = 0;
1857
1858 do {
1859 success = false;
1860 ntries++;
1861
1862 memset(ret, 0, w*h);
1863
1864 /*
1865 * Start by placing n mines, none of which is at x,y or within
1866 * one square of it.
1867 */
1868 {
1869 int *tmp = snewn(w*h, int);
1870 int i, j, k, nn;
1871
1872 /*
1873 * Write down the list of possible mine locations.
1874 */
1875 k = 0;
1876 for (i = 0; i < h; i++)
1877 for (j = 0; j < w; j++)
1878 if (abs(i - y) > 1 || abs(j - x) > 1)
1879 tmp[k++] = i*w+j;
1880
1881 /*
1882 * Now pick n off the list at random.
1883 */
1884 nn = n;
1885 while (nn-- > 0) {
1886 i = random_upto(rs, k);
1887 ret[tmp[i]] = true;
1888 tmp[i] = tmp[--k];
1889 }
1890
1891 sfree(tmp);
1892 }
1893
1894#ifdef GENERATION_DIAGNOSTICS
1895 {
1896 int yy, xx;
1897 printf("grid after initial generation:\n");
1898 for (yy = 0; yy < h; yy++) {
1899 for (xx = 0; xx < w; xx++) {
1900 int v = ret[yy*w+xx];
1901 if (yy == y && xx == x) {
1902 assert(!v);
1903 putchar('S');
1904 } else if (v) {
1905 putchar('*');
1906 } else {
1907 putchar('-');
1908 }
1909 }
1910 putchar('\n');
1911 }
1912 printf("\n");
1913 }
1914#endif
1915
1916 /*
1917 * Now set up a results grid to run the solver in, and a
1918 * context for the solver to open squares. Then run the solver
1919 * repeatedly; if the number of perturb steps ever goes up or
1920 * it ever returns -1, give up completely.
1921 *
1922 * We bypass this bit if we're not after a unique grid.
1923 */
1924 if (unique) {
1925 signed char *solvegrid = snewn(w*h, signed char);
1926 bool *opened = snewn(w*h, bool);
1927 struct minectx actx, *ctx = &actx;
1928 int solveret, prevret = -2;
1929
1930 memset(opened, 0, w*h * sizeof(bool));
1931
1932 ctx->grid = ret;
1933 ctx->opened = opened;
1934 ctx->w = w;
1935 ctx->h = h;
1936 ctx->sx = x;
1937 ctx->sy = y;
1938 ctx->rs = rs;
1939 ctx->allow_big_perturbs = (ntries > 100);
1940 ctx->nperturbs_since_last_new_open = 0;
1941
1942 while (1) {
1943 memset(solvegrid, -2, w*h);
1944 solvegrid[y*w+x] = mineopen(ctx, x, y);
1945 assert(solvegrid[y*w+x] == 0); /* by deliberate arrangement */
1946
1947 solveret =
1948 minesolve(w, h, n, solvegrid, mineopen, mineperturb, ctx, rs);
1949 if (solveret < 0 || (prevret >= 0 && solveret >= prevret)) {
1950 success = false;
1951 break;
1952 } else if (solveret == 0) {
1953 success = true;
1954 break;
1955 }
1956 }
1957
1958 sfree(solvegrid);
1959 sfree(opened);
1960 } else {
1961 success = true;
1962 }
1963
1964 } while (!success);
1965
1966 return ret;
1967}
1968
1969static char *describe_layout(bool *grid, int area, int x, int y,
1970 bool obfuscate)
1971{
1972 char *ret, *p;
1973 unsigned char *bmp;
1974 int i;
1975
1976 /*
1977 * Set up the mine bitmap and obfuscate it.
1978 */
1979 bmp = snewn((area + 7) / 8, unsigned char);
1980 memset(bmp, 0, (area + 7) / 8);
1981 for (i = 0; i < area; i++) {
1982 if (grid[i])
1983 bmp[i / 8] |= 0x80 >> (i % 8);
1984 }
1985 if (obfuscate)
1986 obfuscate_bitmap(bmp, area, false);
1987
1988 /*
1989 * Now encode the resulting bitmap in hex. We can work to
1990 * nibble rather than byte granularity, since the obfuscation
1991 * function guarantees to return a bit string of the same
1992 * length as its input.
1993 */
1994 ret = snewn((area+3)/4 + 100, char);
1995 p = ret + sprintf(ret, "%d,%d,%s", x, y,
1996 obfuscate ? "m" : "u"); /* 'm' == masked */
1997 for (i = 0; i < (area+3)/4; i++) {
1998 int v = bmp[i/2];
1999 if (i % 2 == 0)
2000 v >>= 4;
2001 *p++ = "0123456789abcdef"[v & 0xF];
2002 }
2003 *p = '\0';
2004
2005 sfree(bmp);
2006
2007 return ret;
2008}
2009
2010static bool *new_mine_layout(int w, int h, int n, int x, int y, bool unique,
2011 random_state *rs, char **game_desc)
2012{
2013 bool *grid = minegen(w, h, n, x, y, unique, rs);
2014
2015 if (game_desc)
2016 *game_desc = describe_layout(grid, w * h, x, y, true);
2017
2018 return grid;
2019}
2020
2021static char *new_game_desc(const game_params *params, random_state *rs,
2022 char **aux, bool interactive)
2023{
2024 /*
2025 * We generate the coordinates of an initial click even if they
2026 * aren't actually used. This has the effect of harmonising the
2027 * random number usage between interactive and batch use: if
2028 * you use `mines --generate' with an explicit random seed, you
2029 * should get exactly the same results as if you type the same
2030 * random seed into the interactive game and click in the same
2031 * initial location. (Of course you won't get the same grid if
2032 * you click in a _different_ initial location, but there's
2033 * nothing to be done about that.)
2034 */
2035 int x = random_upto(rs, params->w);
2036 int y = random_upto(rs, params->h);
2037
2038 /*
2039 * Override with params->first_click_[xy] if those are set. (For
2040 * the same reason, we still generated the random numbers first.)
2041 */
2042 if (params->first_click_x >= 0)
2043 x = params->first_click_x;
2044 if (params->first_click_y >= 0)
2045 y = params->first_click_y;
2046
2047 if (!interactive) {
2048 /*
2049 * For batch-generated grids, pre-open one square.
2050 */
2051 bool *grid;
2052 char *desc;
2053
2054 grid = new_mine_layout(params->w, params->h, params->n,
2055 x, y, params->unique, rs, &desc);
2056 sfree(grid);
2057 return desc;
2058 } else {
2059 char *rsdesc, *desc;
2060
2061 rsdesc = random_state_encode(rs);
2062 desc = snewn(strlen(rsdesc) + 100, char);
2063 sprintf(desc, "r%d,%c,%s", params->n, (char)(params->unique ? 'u' : 'a'), rsdesc);
2064 sfree(rsdesc);
2065 return desc;
2066 }
2067}
2068
2069static const char *validate_desc(const game_params *params, const char *desc)
2070{
2071 int wh = params->w * params->h;
2072 int x, y;
2073
2074 if (*desc == 'r') {
2075 desc++;
2076 if (!*desc || !isdigit((unsigned char)*desc))
2077 return "No initial mine count in game description";
2078 if (atoi(desc) > wh - 9)
2079 return "Too many mines for grid size";
2080 while (*desc && isdigit((unsigned char)*desc))
2081 desc++; /* skip over mine count */
2082 if (*desc != ',')
2083 return "No ',' after initial x-coordinate in game description";
2084 desc++;
2085 if (*desc != 'u' && *desc != 'a')
2086 return "No uniqueness specifier in game description";
2087 desc++;
2088 if (*desc != ',')
2089 return "No ',' after uniqueness specifier in game description";
2090 /* now ignore the rest */
2091 } else {
2092 if (*desc && isdigit((unsigned char)*desc)) {
2093 x = atoi(desc);
2094 if (x < 0 || x >= params->w)
2095 return "Initial x-coordinate was out of range";
2096 while (*desc && isdigit((unsigned char)*desc))
2097 desc++; /* skip over x coordinate */
2098 if (*desc != ',')
2099 return "No ',' after initial x-coordinate in game description";
2100 desc++; /* eat comma */
2101 if (!*desc || !isdigit((unsigned char)*desc))
2102 return "No initial y-coordinate in game description";
2103 y = atoi(desc);
2104 if (y < 0 || y >= params->h)
2105 return "Initial y-coordinate was out of range";
2106 while (*desc && isdigit((unsigned char)*desc))
2107 desc++; /* skip over y coordinate */
2108 if (*desc != ',')
2109 return "No ',' after initial y-coordinate in game description";
2110 desc++; /* eat comma */
2111 }
2112 /* eat `m' for `masked' or `u' for `unmasked', if present */
2113 if (*desc == 'm' || *desc == 'u')
2114 desc++;
2115 /* now just check length of remainder */
2116 if (strlen(desc) != (wh+3)/4)
2117 return "Game description is wrong length";
2118 }
2119
2120 return NULL;
2121}
2122
2123static int open_square(game_state *state, int x, int y)
2124{
2125 int w = state->w, h = state->h;
2126 int xx, yy, nmines, ncovered;
2127
2128 if (!state->layout->mines) {
2129 /*
2130 * We have a preliminary game in which the mine layout
2131 * hasn't been generated yet. Generate it based on the
2132 * initial click location.
2133 */
2134 char *desc, *privdesc;
2135 state->layout->mines = new_mine_layout(w, h, state->layout->n,
2136 x, y, state->layout->unique,
2137 state->layout->rs,
2138 &desc);
2139 /*
2140 * Find the trailing substring of the game description
2141 * corresponding to just the mine layout; we will use this
2142 * as our second `private' game ID for serialisation.
2143 */
2144 privdesc = desc;
2145 while (*privdesc && isdigit((unsigned char)*privdesc)) privdesc++;
2146 if (*privdesc == ',') privdesc++;
2147 while (*privdesc && isdigit((unsigned char)*privdesc)) privdesc++;
2148 if (*privdesc == ',') privdesc++;
2149 assert(*privdesc == 'm');
2150 midend_supersede_game_desc(state->layout->me, desc, privdesc);
2151 sfree(desc);
2152 random_free(state->layout->rs);
2153 state->layout->rs = NULL;
2154 }
2155
2156 if (state->layout->mines[y*w+x]) {
2157 /*
2158 * The player has landed on a mine. Bad luck. Expose the
2159 * mine that killed them, but not the rest (in case they
2160 * want to Undo and carry on playing).
2161 */
2162 state->dead = true;
2163 state->grid[y*w+x] = 65;
2164 return -1;
2165 }
2166
2167 /*
2168 * Otherwise, the player has opened a safe square. Mark it to-do.
2169 */
2170 state->grid[y*w+x] = -10; /* `todo' value internal to this func */
2171
2172 /*
2173 * Now go through the grid finding all `todo' values and
2174 * opening them. Every time one of them turns out to have no
2175 * neighbouring mines, we add all its unopened neighbours to
2176 * the list as well.
2177 *
2178 * FIXME: We really ought to be able to do this better than
2179 * using repeated N^2 scans of the grid.
2180 */
2181 while (1) {
2182 bool done_something = false;
2183
2184 for (yy = 0; yy < h; yy++)
2185 for (xx = 0; xx < w; xx++)
2186 if (state->grid[yy*w+xx] == -10) {
2187 int dx, dy, v;
2188
2189 assert(!state->layout->mines[yy*w+xx]);
2190
2191 v = 0;
2192
2193 for (dx = -1; dx <= +1; dx++)
2194 for (dy = -1; dy <= +1; dy++)
2195 if (xx+dx >= 0 && xx+dx < state->w &&
2196 yy+dy >= 0 && yy+dy < state->h &&
2197 state->layout->mines[(yy+dy)*w+(xx+dx)])
2198 v++;
2199
2200 state->grid[yy*w+xx] = v;
2201
2202 if (v == 0) {
2203 for (dx = -1; dx <= +1; dx++)
2204 for (dy = -1; dy <= +1; dy++)
2205 if (xx+dx >= 0 && xx+dx < state->w &&
2206 yy+dy >= 0 && yy+dy < state->h &&
2207 state->grid[(yy+dy)*w+(xx+dx)] == -2)
2208 state->grid[(yy+dy)*w+(xx+dx)] = -10;
2209 }
2210
2211 done_something = true;
2212 }
2213
2214 if (!done_something)
2215 break;
2216 }
2217
2218 /* If the player has already lost, don't let them win as well. */
2219 if (state->dead) return 0;
2220 /*
2221 * Finally, scan the grid and see if exactly as many squares
2222 * are still covered as there are mines. If so, set the `won'
2223 * flag and fill in mine markers on all covered squares.
2224 */
2225 nmines = ncovered = 0;
2226 for (yy = 0; yy < h; yy++)
2227 for (xx = 0; xx < w; xx++) {
2228 if (state->grid[yy*w+xx] < 0)
2229 ncovered++;
2230 if (state->layout->mines[yy*w+xx])
2231 nmines++;
2232 }
2233 assert(ncovered >= nmines);
2234 if (ncovered == nmines) {
2235 for (yy = 0; yy < h; yy++)
2236 for (xx = 0; xx < w; xx++) {
2237 if (state->grid[yy*w+xx] < 0)
2238 state->grid[yy*w+xx] = -1;
2239 }
2240 state->won = true;
2241 }
2242
2243 return 0;
2244}
2245
2246static game_state *new_game(midend *me, const game_params *params,
2247 const char *desc)
2248{
2249 game_state *state = snew(game_state);
2250 int i, wh, x, y;
2251 bool masked;
2252 unsigned char *bmp;
2253
2254 state->w = params->w;
2255 state->h = params->h;
2256 state->n = params->n;
2257 state->dead = state->won = false;
2258 state->used_solve = false;
2259
2260 wh = state->w * state->h;
2261
2262 state->layout = snew(struct mine_layout);
2263 memset(state->layout, 0, sizeof(struct mine_layout));
2264 state->layout->refcount = 1;
2265
2266 state->grid = snewn(wh, signed char);
2267 memset(state->grid, -2, wh);
2268
2269 if (*desc == 'r') {
2270 desc++;
2271 state->layout->n = atoi(desc);
2272 while (*desc && isdigit((unsigned char)*desc))
2273 desc++; /* skip over mine count */
2274 if (*desc) desc++; /* eat comma */
2275 if (*desc == 'a')
2276 state->layout->unique = false;
2277 else
2278 state->layout->unique = true;
2279 desc++;
2280 if (*desc) desc++; /* eat comma */
2281
2282 state->layout->mines = NULL;
2283 state->layout->rs = random_state_decode(desc);
2284 state->layout->me = me;
2285
2286 } else {
2287 state->layout->rs = NULL;
2288 state->layout->me = NULL;
2289 state->layout->mines = snewn(wh, bool);
2290
2291 if (*desc && isdigit((unsigned char)*desc)) {
2292 x = atoi(desc);
2293 while (*desc && isdigit((unsigned char)*desc))
2294 desc++; /* skip over x coordinate */
2295 if (*desc) desc++; /* eat comma */
2296 y = atoi(desc);
2297 while (*desc && isdigit((unsigned char)*desc))
2298 desc++; /* skip over y coordinate */
2299 if (*desc) desc++; /* eat comma */
2300 } else {
2301 x = y = -1;
2302 }
2303
2304 if (*desc == 'm') {
2305 masked = true;
2306 desc++;
2307 } else {
2308 if (*desc == 'u')
2309 desc++;
2310 /*
2311 * We permit game IDs to be entered by hand without the
2312 * masking transformation.
2313 */
2314 masked = false;
2315 }
2316
2317 bmp = snewn((wh + 7) / 8, unsigned char);
2318 memset(bmp, 0, (wh + 7) / 8);
2319 for (i = 0; i < (wh+3)/4; i++) {
2320 int c = desc[i];
2321 int v;
2322
2323 assert(c != 0); /* validate_desc should have caught */
2324 if (c >= '0' && c <= '9')
2325 v = c - '0';
2326 else if (c >= 'a' && c <= 'f')
2327 v = c - 'a' + 10;
2328 else if (c >= 'A' && c <= 'F')
2329 v = c - 'A' + 10;
2330 else
2331 v = 0;
2332
2333 bmp[i / 2] |= v << (4 * (1 - (i % 2)));
2334 }
2335
2336 if (masked)
2337 obfuscate_bitmap(bmp, wh, true);
2338
2339 memset(state->layout->mines, 0, wh * sizeof(bool));
2340 for (i = 0; i < wh; i++) {
2341 if (bmp[i / 8] & (0x80 >> (i % 8)))
2342 state->layout->mines[i] = true;
2343 }
2344
2345 if (x >= 0 && y >= 0)
2346 open_square(state, x, y);
2347 sfree(bmp);
2348 }
2349
2350 return state;
2351}
2352
2353static game_state *dup_game(const game_state *state)
2354{
2355 game_state *ret = snew(game_state);
2356
2357 ret->w = state->w;
2358 ret->h = state->h;
2359 ret->n = state->n;
2360 ret->dead = state->dead;
2361 ret->won = state->won;
2362 ret->used_solve = state->used_solve;
2363 ret->layout = state->layout;
2364 ret->layout->refcount++;
2365 ret->grid = snewn(ret->w * ret->h, signed char);
2366 memcpy(ret->grid, state->grid, ret->w * ret->h);
2367
2368 return ret;
2369}
2370
2371static void free_game(game_state *state)
2372{
2373 if (--state->layout->refcount <= 0) {
2374 sfree(state->layout->mines);
2375 if (state->layout->rs)
2376 random_free(state->layout->rs);
2377 sfree(state->layout);
2378 }
2379 sfree(state->grid);
2380 sfree(state);
2381}
2382
2383static char *solve_game(const game_state *state, const game_state *currstate,
2384 const char *aux, const char **error)
2385{
2386 if (!state->layout->mines) {
2387 *error = "Game has not been started yet";
2388 return NULL;
2389 }
2390
2391 return dupstr("S");
2392}
2393
2394static bool game_can_format_as_text_now(const game_params *params)
2395{
2396 return true;
2397}
2398
2399static char *game_text_format(const game_state *state)
2400{
2401 char *ret;
2402 int x, y;
2403
2404 ret = snewn((state->w + 1) * state->h + 1, char);
2405 for (y = 0; y < state->h; y++) {
2406 for (x = 0; x < state->w; x++) {
2407 int v = state->grid[y*state->w+x];
2408 if (v == 0)
2409 v = '-';
2410 else if (v >= 1 && v <= 8)
2411 v = '0' + v;
2412 else if (v == -1)
2413 v = '*';
2414 else if (v == -2 || v == -3)
2415 v = '?';
2416 else if (v >= 64)
2417 v = '!';
2418 ret[y * (state->w+1) + x] = v;
2419 }
2420 ret[y * (state->w+1) + state->w] = '\n';
2421 }
2422 ret[(state->w + 1) * state->h] = '\0';
2423
2424 return ret;
2425}
2426
2427struct game_ui {
2428 int hx, hy, hradius; /* for mouse-down highlights */
2429 int validradius;
2430 bool flash_is_death;
2431 int deaths;
2432 bool completed;
2433 int cur_x, cur_y;
2434 bool cur_visible;
2435};
2436
2437static game_ui *new_ui(const game_state *state)
2438{
2439 game_ui *ui = snew(game_ui);
2440 ui->hx = ui->hy = -1;
2441 ui->hradius = ui->validradius = 0;
2442 ui->deaths = 0;
2443 ui->completed = false;
2444 ui->flash_is_death = false; /* *shrug* */
2445 ui->cur_x = ui->cur_y = 0;
2446 ui->cur_visible = getenv_bool("PUZZLES_SHOW_CURSOR", false);
2447 return ui;
2448}
2449
2450static void free_ui(game_ui *ui)
2451{
2452 sfree(ui);
2453}
2454
2455static char *encode_ui(const game_ui *ui)
2456{
2457 char buf[80];
2458 /*
2459 * The deaths counter and completion status need preserving
2460 * across a serialisation.
2461 */
2462 sprintf(buf, "D%d", ui->deaths);
2463 if (ui->completed)
2464 strcat(buf, "C");
2465 return dupstr(buf);
2466}
2467
2468static void decode_ui(game_ui *ui, const char *encoding,
2469 const game_state *state)
2470{
2471 int p= 0;
2472 sscanf(encoding, "D%d%n", &ui->deaths, &p);
2473 if (encoding[p] == 'C')
2474 ui->completed = true;
2475}
2476
2477static void game_changed_state(game_ui *ui, const game_state *oldstate,
2478 const game_state *newstate)
2479{
2480 if (newstate->won)
2481 ui->completed = true;
2482}
2483
2484static const char *current_key_label(const game_ui *ui,
2485 const game_state *state, int button)
2486{
2487 int cx = ui->cur_x, cy = ui->cur_y;
2488 int v = state->grid[cy * state->w + cx];
2489
2490 if (state->dead || state->won || !ui->cur_visible) return "";
2491 if (button == CURSOR_SELECT2) {
2492 if (v == -2) return "Mark";
2493 if (v == -1) return "Unmark";
2494 return "";
2495 }
2496 if (button == CURSOR_SELECT) {
2497 int dy, dx, n = 0;
2498 if (v == -2 || v == -3) return "Uncover";
2499 if (v == 0) return "";
2500 /* Count mine markers. */
2501 for (dy = -1; dy <= +1; dy++)
2502 for (dx = -1; dx <= +1; dx++)
2503 if (cx+dx >= 0 && cx+dx < state->w &&
2504 cy+dy >= 0 && cy+dy < state->h) {
2505 if (state->grid[(cy+dy)*state->w+(cx+dx)] == -1)
2506 n++;
2507 }
2508 if (n == v) return "Clear";
2509 }
2510 return "";
2511}
2512
2513struct game_drawstate {
2514 int w, h, tilesize, bg;
2515 bool started;
2516 signed char *grid;
2517 /*
2518 * Items in this `grid' array have all the same values as in
2519 * the game_state grid, and in addition:
2520 *
2521 * - -10 means the tile was drawn `specially' as a result of a
2522 * flash, so it will always need redrawing.
2523 *
2524 * - -22 and -23 mean the tile is highlighted for a possible
2525 * click.
2526 */
2527 int cur_x, cur_y; /* -1, -1 for no cursor displayed. */
2528};
2529
2530static char *interpret_move(const game_state *from, game_ui *ui,
2531 const game_drawstate *ds,
2532 int x, int y, int button)
2533{
2534 int cx, cy;
2535 char buf[256];
2536
2537 if (from->dead || from->won)
2538 return NULL; /* no further moves permitted */
2539
2540 cx = FROMCOORD(x);
2541 cy = FROMCOORD(y);
2542
2543 if (IS_CURSOR_MOVE(button))
2544 return move_cursor(button, &ui->cur_x, &ui->cur_y, from->w, from->h,
2545 false, &ui->cur_visible);
2546 if (IS_CURSOR_SELECT(button)) {
2547 int v = from->grid[ui->cur_y * from->w + ui->cur_x];
2548
2549 if (!ui->cur_visible) {
2550 ui->cur_visible = true;
2551 return MOVE_UI_UPDATE;
2552 }
2553 if (button == CURSOR_SELECT2) {
2554 /* As for RIGHT_BUTTON; only works on covered square. */
2555 if (v != -2 && v != -1)
2556 return MOVE_NO_EFFECT;
2557 sprintf(buf, "F%d,%d", ui->cur_x, ui->cur_y);
2558 return dupstr(buf);
2559 }
2560 /* Otherwise, treat as LEFT_BUTTON, for a single square. */
2561 if (v == -2 || v == -3) {
2562 if (from->layout->mines &&
2563 from->layout->mines[ui->cur_y * from->w + ui->cur_x])
2564 ui->deaths++;
2565
2566 sprintf(buf, "O%d,%d", ui->cur_x, ui->cur_y);
2567 return dupstr(buf);
2568 }
2569 cx = ui->cur_x; cy = ui->cur_y;
2570 ui->validradius = 1;
2571 goto uncover;
2572 }
2573
2574 if (button == LEFT_BUTTON || button == LEFT_DRAG ||
2575 button == MIDDLE_BUTTON || button == MIDDLE_DRAG) {
2576 if (cx < 0 || cx >= from->w || cy < 0 || cy >= from->h)
2577 return MOVE_UNUSED;
2578
2579 /*
2580 * Mouse-downs and mouse-drags just cause highlighting
2581 * updates.
2582 */
2583 ui->hx = cx;
2584 ui->hy = cy;
2585 ui->hradius = (from->grid[cy*from->w+cx] >= 0 ? 1 : 0);
2586 if (button == LEFT_BUTTON)
2587 ui->validradius = ui->hradius;
2588 else if (button == MIDDLE_BUTTON)
2589 ui->validradius = 1;
2590 ui->cur_visible = false;
2591 return MOVE_UI_UPDATE;
2592 }
2593
2594 if (button == RIGHT_BUTTON) {
2595 if (cx < 0 || cx >= from->w || cy < 0 || cy >= from->h)
2596 return MOVE_UNUSED;
2597
2598 /*
2599 * Right-clicking only works on a covered square, and it
2600 * toggles between -1 (marked as mine) and -2 (not marked
2601 * as mine).
2602 *
2603 * FIXME: question marks.
2604 */
2605 if (from->grid[cy * from->w + cx] != -2 &&
2606 from->grid[cy * from->w + cx] != -1)
2607 return MOVE_NO_EFFECT;
2608
2609 sprintf(buf, "F%d,%d", cx, cy);
2610 return dupstr(buf);
2611 }
2612
2613 if (button == LEFT_RELEASE || button == MIDDLE_RELEASE) {
2614 ui->hx = ui->hy = -1;
2615 ui->hradius = 0;
2616
2617 /*
2618 * At this stage we must never return MOVE_UNUSED or
2619 * MOVE_NO_EFFECT: we have adjusted the ui, so at worst we
2620 * return MOVE_UI_UPDATE.
2621 */
2622 if (cx < 0 || cx >= from->w || cy < 0 || cy >= from->h)
2623 return MOVE_UI_UPDATE;
2624
2625 /*
2626 * Left-clicking on a covered square opens a tile. Not
2627 * permitted if the tile is marked as a mine, for safety.
2628 * (Unmark it and _then_ open it.)
2629 */
2630 if (button == LEFT_RELEASE &&
2631 (from->grid[cy * from->w + cx] == -2 ||
2632 from->grid[cy * from->w + cx] == -3) &&
2633 ui->validradius == 0) {
2634 /* Check if you've killed yourself. */
2635 if (from->layout->mines && from->layout->mines[cy * from->w + cx])
2636 ui->deaths++;
2637
2638 sprintf(buf, "O%d,%d", cx, cy);
2639 return dupstr(buf);
2640 }
2641 goto uncover;
2642 }
2643 return MOVE_UNUSED;
2644
2645uncover:
2646 {
2647 /*
2648 * Left-clicking or middle-clicking on an uncovered tile:
2649 * first we check to see if the number of mine markers
2650 * surrounding the tile is equal to its mine count, and if
2651 * so then we open all other surrounding squares.
2652 */
2653 if (from->grid[cy * from->w + cx] > 0 && ui->validradius == 1) {
2654 int dy, dx, n;
2655
2656 /* Count mine markers. */
2657 n = 0;
2658 for (dy = -1; dy <= +1; dy++)
2659 for (dx = -1; dx <= +1; dx++)
2660 if (cx+dx >= 0 && cx+dx < from->w &&
2661 cy+dy >= 0 && cy+dy < from->h) {
2662 if (from->grid[(cy+dy)*from->w+(cx+dx)] == -1)
2663 n++;
2664 }
2665
2666 if (n == from->grid[cy * from->w + cx]) {
2667
2668 /*
2669 * Now see if any of the squares we're clearing
2670 * contains a mine (which will happen iff you've
2671 * incorrectly marked the mines around the clicked
2672 * square). If so, we open _just_ those squares, to
2673 * reveal as little additional information as we
2674 * can.
2675 */
2676 char *p = buf;
2677 const char *sep = "";
2678
2679 for (dy = -1; dy <= +1; dy++)
2680 for (dx = -1; dx <= +1; dx++)
2681 if (cx+dx >= 0 && cx+dx < from->w &&
2682 cy+dy >= 0 && cy+dy < from->h) {
2683 if (from->grid[(cy+dy)*from->w+(cx+dx)] != -1 &&
2684 from->layout->mines &&
2685 from->layout->mines[(cy+dy)*from->w+(cx+dx)]) {
2686 p += sprintf(p, "%sO%d,%d", sep, cx+dx, cy+dy);
2687 sep = ";";
2688 }
2689 }
2690
2691 if (p > buf) {
2692 ui->deaths++;
2693 } else {
2694 sprintf(buf, "C%d,%d", cx, cy);
2695 }
2696
2697 return dupstr(buf);
2698 }
2699 }
2700
2701 return MOVE_UI_UPDATE;
2702 }
2703}
2704
2705static game_state *execute_move(const game_state *from, const char *move)
2706{
2707 int cy, cx;
2708 game_state *ret;
2709
2710 if (!strcmp(move, "S")) {
2711 int yy, xx;
2712
2713 if (!from->layout->mines) return NULL; /* Game not started. */
2714 ret = dup_game(from);
2715 if (!ret->dead) {
2716 /*
2717 * If the player is still alive at the moment of pressing
2718 * Solve, expose the entire grid as if it were a completed
2719 * solution.
2720 */
2721 for (yy = 0; yy < ret->h; yy++)
2722 for (xx = 0; xx < ret->w; xx++) {
2723
2724 if (ret->layout->mines[yy*ret->w+xx]) {
2725 ret->grid[yy*ret->w+xx] = -1;
2726 } else {
2727 int dx, dy, v;
2728
2729 v = 0;
2730
2731 for (dx = -1; dx <= +1; dx++)
2732 for (dy = -1; dy <= +1; dy++)
2733 if (xx+dx >= 0 && xx+dx < ret->w &&
2734 yy+dy >= 0 && yy+dy < ret->h &&
2735 ret->layout->mines[(yy+dy)*ret->w+(xx+dx)])
2736 v++;
2737
2738 ret->grid[yy*ret->w+xx] = v;
2739 }
2740 }
2741 } else {
2742 /*
2743 * If the player pressed Solve _after dying_, show a full
2744 * corrections grid in the style of standard Minesweeper.
2745 * Players who don't like Mines's behaviour on death of
2746 * only showing the mine that killed you (so that in case
2747 * of a typo you can undo and carry on without the rest of
2748 * the grid being spoiled) can use this to get the display
2749 * that ordinary Minesweeper would have given them.
2750 */
2751 for (yy = 0; yy < ret->h; yy++)
2752 for (xx = 0; xx < ret->w; xx++) {
2753 int pos = yy*ret->w+xx;
2754 if ((ret->grid[pos] == -2 || ret->grid[pos] == -3) &&
2755 ret->layout->mines[pos]) {
2756 ret->grid[pos] = 64;
2757 } else if (ret->grid[pos] == -1 &&
2758 !ret->layout->mines[pos]) {
2759 ret->grid[pos] = 66;
2760 }
2761 }
2762 }
2763 ret->used_solve = true;
2764
2765 return ret;
2766 } else {
2767 /* Dead players should stop trying to move. */
2768 if (from->dead)
2769 return NULL;
2770 ret = dup_game(from);
2771
2772 while (*move) {
2773 if (move[0] == 'F' &&
2774 sscanf(move+1, "%d,%d", &cx, &cy) == 2 &&
2775 cx >= 0 && cx < from->w && cy >= 0 && cy < from->h &&
2776 (ret->grid[cy * from->w + cx] == -1 ||
2777 ret->grid[cy * from->w + cx] == -2)) {
2778 ret->grid[cy * from->w + cx] ^= (-2 ^ -1);
2779 } else if (move[0] == 'O' &&
2780 sscanf(move+1, "%d,%d", &cx, &cy) == 2 &&
2781 cx >= 0 && cx < from->w && cy >= 0 && cy < from->h) {
2782 open_square(ret, cx, cy);
2783 } else if (move[0] == 'C' &&
2784 sscanf(move+1, "%d,%d", &cx, &cy) == 2 &&
2785 cx >= 0 && cx < from->w && cy >= 0 && cy < from->h) {
2786 int dx, dy;
2787
2788 for (dy = -1; dy <= +1; dy++)
2789 for (dx = -1; dx <= +1; dx++)
2790 if (cx+dx >= 0 && cx+dx < ret->w &&
2791 cy+dy >= 0 && cy+dy < ret->h &&
2792 (ret->grid[(cy+dy)*ret->w+(cx+dx)] == -2 ||
2793 ret->grid[(cy+dy)*ret->w+(cx+dx)] == -3))
2794 open_square(ret, cx+dx, cy+dy);
2795 } else {
2796 free_game(ret);
2797 return NULL;
2798 }
2799
2800 while (*move && *move != ';') move++;
2801 if (*move) move++;
2802 }
2803
2804 return ret;
2805 }
2806}
2807
2808/* ----------------------------------------------------------------------
2809 * Drawing routines.
2810 */
2811
2812static void game_compute_size(const game_params *params, int tilesize,
2813 const game_ui *ui, int *x, int *y)
2814{
2815 /* Ick: fake up `ds->tilesize' for macro expansion purposes */
2816 struct { int tilesize; } ads, *ds = &ads;
2817 ads.tilesize = tilesize;
2818
2819 *x = BORDER * 2 + TILE_SIZE * params->w;
2820 *y = BORDER * 2 + TILE_SIZE * params->h;
2821}
2822
2823static void game_set_size(drawing *dr, game_drawstate *ds,
2824 const game_params *params, int tilesize)
2825{
2826 ds->tilesize = tilesize;
2827}
2828
2829static float *game_colours(frontend *fe, int *ncolours)
2830{
2831 float *ret = snewn(3 * NCOLOURS, float);
2832
2833 frontend_default_colour(fe, &ret[COL_BACKGROUND * 3]);
2834
2835 ret[COL_BACKGROUND2 * 3 + 0] = ret[COL_BACKGROUND * 3 + 0] * 19.0F / 20.0F;
2836 ret[COL_BACKGROUND2 * 3 + 1] = ret[COL_BACKGROUND * 3 + 1] * 19.0F / 20.0F;
2837 ret[COL_BACKGROUND2 * 3 + 2] = ret[COL_BACKGROUND * 3 + 2] * 19.0F / 20.0F;
2838
2839 ret[COL_1 * 3 + 0] = 0.0F;
2840 ret[COL_1 * 3 + 1] = 0.0F;
2841 ret[COL_1 * 3 + 2] = 1.0F;
2842
2843 ret[COL_2 * 3 + 0] = 0.0F;
2844 ret[COL_2 * 3 + 1] = 0.5F;
2845 ret[COL_2 * 3 + 2] = 0.0F;
2846
2847 ret[COL_3 * 3 + 0] = 1.0F;
2848 ret[COL_3 * 3 + 1] = 0.0F;
2849 ret[COL_3 * 3 + 2] = 0.0F;
2850
2851 ret[COL_4 * 3 + 0] = 0.0F;
2852 ret[COL_4 * 3 + 1] = 0.0F;
2853 ret[COL_4 * 3 + 2] = 0.5F;
2854
2855 ret[COL_5 * 3 + 0] = 0.5F;
2856 ret[COL_5 * 3 + 1] = 0.0F;
2857 ret[COL_5 * 3 + 2] = 0.0F;
2858
2859 ret[COL_6 * 3 + 0] = 0.0F;
2860 ret[COL_6 * 3 + 1] = 0.5F;
2861 ret[COL_6 * 3 + 2] = 0.5F;
2862
2863 ret[COL_7 * 3 + 0] = 0.0F;
2864 ret[COL_7 * 3 + 1] = 0.0F;
2865 ret[COL_7 * 3 + 2] = 0.0F;
2866
2867 ret[COL_8 * 3 + 0] = 0.5F;
2868 ret[COL_8 * 3 + 1] = 0.5F;
2869 ret[COL_8 * 3 + 2] = 0.5F;
2870
2871 ret[COL_MINE * 3 + 0] = 0.0F;
2872 ret[COL_MINE * 3 + 1] = 0.0F;
2873 ret[COL_MINE * 3 + 2] = 0.0F;
2874
2875 ret[COL_BANG * 3 + 0] = 1.0F;
2876 ret[COL_BANG * 3 + 1] = 0.0F;
2877 ret[COL_BANG * 3 + 2] = 0.0F;
2878
2879 ret[COL_CROSS * 3 + 0] = 1.0F;
2880 ret[COL_CROSS * 3 + 1] = 0.0F;
2881 ret[COL_CROSS * 3 + 2] = 0.0F;
2882
2883 ret[COL_FLAG * 3 + 0] = 1.0F;
2884 ret[COL_FLAG * 3 + 1] = 0.0F;
2885 ret[COL_FLAG * 3 + 2] = 0.0F;
2886
2887 ret[COL_FLAGBASE * 3 + 0] = 0.0F;
2888 ret[COL_FLAGBASE * 3 + 1] = 0.0F;
2889 ret[COL_FLAGBASE * 3 + 2] = 0.0F;
2890
2891 ret[COL_QUERY * 3 + 0] = 0.0F;
2892 ret[COL_QUERY * 3 + 1] = 0.0F;
2893 ret[COL_QUERY * 3 + 2] = 0.0F;
2894
2895 ret[COL_HIGHLIGHT * 3 + 0] = 1.0F;
2896 ret[COL_HIGHLIGHT * 3 + 1] = 1.0F;
2897 ret[COL_HIGHLIGHT * 3 + 2] = 1.0F;
2898
2899 ret[COL_LOWLIGHT * 3 + 0] = ret[COL_BACKGROUND * 3 + 0] * 2.0F / 3.0F;
2900 ret[COL_LOWLIGHT * 3 + 1] = ret[COL_BACKGROUND * 3 + 1] * 2.0F / 3.0F;
2901 ret[COL_LOWLIGHT * 3 + 2] = ret[COL_BACKGROUND * 3 + 2] * 2.0F / 3.0F;
2902
2903 ret[COL_WRONGNUMBER * 3 + 0] = 1.0F;
2904 ret[COL_WRONGNUMBER * 3 + 1] = 0.6F;
2905 ret[COL_WRONGNUMBER * 3 + 2] = 0.6F;
2906
2907 /* Red tinge to a light colour, for the cursor. */
2908 ret[COL_CURSOR * 3 + 0] = ret[COL_HIGHLIGHT * 3 + 0];
2909 ret[COL_CURSOR * 3 + 1] = ret[COL_HIGHLIGHT * 3 + 0] / 2.0F;
2910 ret[COL_CURSOR * 3 + 2] = ret[COL_HIGHLIGHT * 3 + 0] / 2.0F;
2911
2912 *ncolours = NCOLOURS;
2913 return ret;
2914}
2915
2916static game_drawstate *game_new_drawstate(drawing *dr, const game_state *state)
2917{
2918 struct game_drawstate *ds = snew(struct game_drawstate);
2919
2920 ds->w = state->w;
2921 ds->h = state->h;
2922 ds->started = false;
2923 ds->tilesize = 0; /* not decided yet */
2924 ds->grid = snewn(ds->w * ds->h, signed char);
2925 ds->bg = -1;
2926 ds->cur_x = ds->cur_y = -1;
2927
2928 memset(ds->grid, -99, ds->w * ds->h);
2929
2930 return ds;
2931}
2932
2933static void game_free_drawstate(drawing *dr, game_drawstate *ds)
2934{
2935 sfree(ds->grid);
2936 sfree(ds);
2937}
2938
2939static void draw_tile(drawing *dr, game_drawstate *ds,
2940 int x, int y, int v, int bg)
2941{
2942 if (v < 0) {
2943 int coords[12];
2944 int hl = 0;
2945
2946 if (v == -22 || v == -23) {
2947 v += 20;
2948
2949 /*
2950 * Omit the highlights in this case.
2951 */
2952 draw_rect(dr, x, y, TILE_SIZE, TILE_SIZE,
2953 bg == COL_BACKGROUND ? COL_BACKGROUND2 : bg);
2954 draw_line(dr, x, y, x + TILE_SIZE - 1, y, COL_LOWLIGHT);
2955 draw_line(dr, x, y, x, y + TILE_SIZE - 1, COL_LOWLIGHT);
2956 } else {
2957 /*
2958 * Draw highlights to indicate the square is covered.
2959 */
2960 coords[0] = x + TILE_SIZE - 1;
2961 coords[1] = y + TILE_SIZE - 1;
2962 coords[2] = x + TILE_SIZE - 1;
2963 coords[3] = y;
2964 coords[4] = x;
2965 coords[5] = y + TILE_SIZE - 1;
2966 draw_polygon(dr, coords, 3, COL_LOWLIGHT ^ hl, COL_LOWLIGHT ^ hl);
2967
2968 coords[0] = x;
2969 coords[1] = y;
2970 draw_polygon(dr, coords, 3, COL_HIGHLIGHT ^ hl,
2971 COL_HIGHLIGHT ^ hl);
2972
2973 draw_rect(dr, x + HIGHLIGHT_WIDTH, y + HIGHLIGHT_WIDTH,
2974 TILE_SIZE - 2*HIGHLIGHT_WIDTH, TILE_SIZE - 2*HIGHLIGHT_WIDTH,
2975 bg);
2976 }
2977
2978 if (v == -1) {
2979 /*
2980 * Draw a flag.
2981 */
2982#define SETCOORD(n, dx, dy) do { \
2983 coords[(n)*2+0] = x + (int)(TILE_SIZE * (dx)); \
2984 coords[(n)*2+1] = y + (int)(TILE_SIZE * (dy)); \
2985} while (0)
2986 SETCOORD(0, 0.6F, 0.35F);
2987 SETCOORD(1, 0.6F, 0.7F);
2988 SETCOORD(2, 0.8F, 0.8F);
2989 SETCOORD(3, 0.25F, 0.8F);
2990 SETCOORD(4, 0.55F, 0.7F);
2991 SETCOORD(5, 0.55F, 0.35F);
2992 draw_polygon(dr, coords, 6, COL_FLAGBASE, COL_FLAGBASE);
2993
2994 SETCOORD(0, 0.6F, 0.2F);
2995 SETCOORD(1, 0.6F, 0.5F);
2996 SETCOORD(2, 0.2F, 0.35F);
2997 draw_polygon(dr, coords, 3, COL_FLAG, COL_FLAG);
2998#undef SETCOORD
2999
3000 } else if (v == -3) {
3001 /*
3002 * Draw a question mark.
3003 */
3004 draw_text(dr, x + TILE_SIZE / 2, y + TILE_SIZE / 2,
3005 FONT_VARIABLE, TILE_SIZE * 6 / 8,
3006 ALIGN_VCENTRE | ALIGN_HCENTRE,
3007 COL_QUERY, "?");
3008 }
3009 } else {
3010 /*
3011 * Clear the square to the background colour, and draw thin
3012 * grid lines along the top and left.
3013 *
3014 * Exception is that for value 65 (mine we've just trodden
3015 * on), we clear the square to COL_BANG.
3016 */
3017 if (v & 32) {
3018 bg = COL_WRONGNUMBER;
3019 v &= ~32;
3020 }
3021 draw_rect(dr, x, y, TILE_SIZE, TILE_SIZE,
3022 (v == 65 ? COL_BANG :
3023 bg == COL_BACKGROUND ? COL_BACKGROUND2 : bg));
3024 draw_line(dr, x, y, x + TILE_SIZE - 1, y, COL_LOWLIGHT);
3025 draw_line(dr, x, y, x, y + TILE_SIZE - 1, COL_LOWLIGHT);
3026
3027 if (v > 0 && v <= 8) {
3028 /*
3029 * Mark a number.
3030 */
3031 char str[2];
3032 str[0] = v + '0';
3033 str[1] = '\0';
3034 draw_text(dr, x + TILE_SIZE / 2, y + TILE_SIZE / 2,
3035 FONT_VARIABLE, TILE_SIZE * 7 / 8,
3036 ALIGN_VCENTRE | ALIGN_HCENTRE,
3037 (COL_1 - 1) + v, str);
3038
3039 } else if (v >= 64) {
3040 /*
3041 * Mark a mine.
3042 */
3043 {
3044 int cx = x + TILE_SIZE / 2;
3045 int cy = y + TILE_SIZE / 2;
3046 int r = TILE_SIZE / 2 - 3;
3047
3048 draw_circle(dr, cx, cy, 5*r/6, COL_MINE, COL_MINE);
3049 draw_rect(dr, cx - r/6, cy - r, 2*(r/6)+1, 2*r+1, COL_MINE);
3050 draw_rect(dr, cx - r, cy - r/6, 2*r+1, 2*(r/6)+1, COL_MINE);
3051 draw_rect(dr, cx-r/3, cy-r/3, r/3, r/4, COL_HIGHLIGHT);
3052 }
3053
3054 if (v == 66) {
3055 /*
3056 * Cross through the mine.
3057 */
3058 int dx;
3059 for (dx = -1; dx <= +1; dx++) {
3060 draw_line(dr, x + 3 + dx, y + 2,
3061 x + TILE_SIZE - 3 + dx,
3062 y + TILE_SIZE - 2, COL_CROSS);
3063 draw_line(dr, x + TILE_SIZE - 3 + dx, y + 2,
3064 x + 3 + dx, y + TILE_SIZE - 2,
3065 COL_CROSS);
3066 }
3067 }
3068 }
3069 }
3070
3071 draw_update(dr, x, y, TILE_SIZE, TILE_SIZE);
3072}
3073
3074static void game_redraw(drawing *dr, game_drawstate *ds,
3075 const game_state *oldstate, const game_state *state,
3076 int dir, const game_ui *ui,
3077 float animtime, float flashtime)
3078{
3079 int x, y;
3080 int mines, markers, closed, bg;
3081 int cx = -1, cy = -1;
3082 bool cmoved;
3083
3084 if (flashtime) {
3085 int frame = (int)(flashtime / FLASH_FRAME);
3086 if (frame % 2)
3087 bg = (ui->flash_is_death ? COL_BACKGROUND : COL_LOWLIGHT);
3088 else
3089 bg = (ui->flash_is_death ? COL_BANG : COL_HIGHLIGHT);
3090 } else
3091 bg = COL_BACKGROUND;
3092
3093 if (!ds->started) {
3094 int coords[10];
3095
3096 /*
3097 * Recessed area containing the whole puzzle.
3098 */
3099 coords[0] = COORD(state->w) + OUTER_HIGHLIGHT_WIDTH - 1;
3100 coords[1] = COORD(state->h) + OUTER_HIGHLIGHT_WIDTH - 1;
3101 coords[2] = COORD(state->w) + OUTER_HIGHLIGHT_WIDTH - 1;
3102 coords[3] = COORD(0) - OUTER_HIGHLIGHT_WIDTH;
3103 coords[4] = coords[2] - TILE_SIZE;
3104 coords[5] = coords[3] + TILE_SIZE;
3105 coords[8] = COORD(0) - OUTER_HIGHLIGHT_WIDTH;
3106 coords[9] = COORD(state->h) + OUTER_HIGHLIGHT_WIDTH - 1;
3107 coords[6] = coords[8] + TILE_SIZE;
3108 coords[7] = coords[9] - TILE_SIZE;
3109 draw_polygon(dr, coords, 5, COL_HIGHLIGHT, COL_HIGHLIGHT);
3110
3111 coords[1] = COORD(0) - OUTER_HIGHLIGHT_WIDTH;
3112 coords[0] = COORD(0) - OUTER_HIGHLIGHT_WIDTH;
3113 draw_polygon(dr, coords, 5, COL_LOWLIGHT, COL_LOWLIGHT);
3114
3115 ds->started = true;
3116 }
3117
3118 if (ui->cur_visible) cx = ui->cur_x;
3119 if (ui->cur_visible) cy = ui->cur_y;
3120 cmoved = (cx != ds->cur_x || cy != ds->cur_y);
3121
3122 /*
3123 * Now draw the tiles. Also in this loop, count up the number
3124 * of mines, mine markers, and closed squares.
3125 */
3126 mines = markers = closed = 0;
3127 for (y = 0; y < ds->h; y++)
3128 for (x = 0; x < ds->w; x++) {
3129 int v = state->grid[y*ds->w+x];
3130 bool cc = false;
3131
3132 if (v < 0)
3133 closed++;
3134 if (v == -1)
3135 markers++;
3136 if (state->layout->mines && state->layout->mines[y*ds->w+x])
3137 mines++;
3138
3139 if (v >= 0 && v <= 8) {
3140 /*
3141 * Count up the flags around this tile, and if
3142 * there are too _many_, highlight the tile.
3143 */
3144 int dx, dy, flags = 0;
3145
3146 for (dy = -1; dy <= +1; dy++)
3147 for (dx = -1; dx <= +1; dx++) {
3148 int nx = x+dx, ny = y+dy;
3149 if (nx >= 0 && nx < ds->w &&
3150 ny >= 0 && ny < ds->h &&
3151 state->grid[ny*ds->w+nx] == -1)
3152 flags++;
3153 }
3154
3155 if (flags > v)
3156 v |= 32;
3157 }
3158
3159 if ((v == -2 || v == -3) &&
3160 (abs(x-ui->hx) <= ui->hradius && abs(y-ui->hy) <= ui->hradius))
3161 v -= 20;
3162
3163 if (cmoved && /* if cursor has moved, force redraw of curr and prev pos */
3164 ((x == cx && y == cy) || (x == ds->cur_x && y == ds->cur_y)))
3165 cc = true;
3166
3167 if (ds->grid[y*ds->w+x] != v || bg != ds->bg || cc) {
3168 draw_tile(dr, ds, COORD(x), COORD(y), v,
3169 (x == cx && y == cy) ? COL_CURSOR : bg);
3170 ds->grid[y*ds->w+x] = v;
3171 }
3172 }
3173 ds->bg = bg;
3174 ds->cur_x = cx; ds->cur_y = cy;
3175
3176 if (!state->layout->mines)
3177 mines = state->layout->n;
3178
3179 /*
3180 * Update the status bar.
3181 */
3182 {
3183 char statusbar[512];
3184 if (state->dead) {
3185 sprintf(statusbar, "DEAD!");
3186 } else if (state->won) {
3187 if (state->used_solve)
3188 sprintf(statusbar, "Auto-solved.");
3189 else
3190 sprintf(statusbar, "COMPLETED!");
3191 } else {
3192 int safe_closed = closed - mines;
3193 sprintf(statusbar, "Marked: %d / %d", markers, mines);
3194 if (safe_closed > 0 && safe_closed <= 9) {
3195 /*
3196 * In the situation where there's a very small number
3197 * of _non_-mine squares left unopened, it's helpful
3198 * to mention that number in the status line, to save
3199 * the player from having to count it up
3200 * painstakingly. This is particularly important if
3201 * the player has turned up the mine density to the
3202 * point where game generation resorts to its weird
3203 * pathological fallback of a very dense mine area
3204 * with a clearing in the middle, because that often
3205 * leads to a deduction you can only make by knowing
3206 * that there is (say) exactly one non-mine square to
3207 * find, and it's a real pain to have to count up two
3208 * large numbers of squares and subtract them to get
3209 * that value of 1.
3210 *
3211 * The threshold value of 8 for displaying this
3212 * information is because that's the largest number of
3213 * non-mine squares that might conceivably fit around
3214 * a single central square, and the most likely way to
3215 * _use_ this information is to observe that if all
3216 * the remaining safe squares are adjacent to _this_
3217 * square then everything else can be immediately
3218 * flagged as a mine.
3219 */
3220 if (safe_closed == 1) {
3221 sprintf(statusbar + strlen(statusbar),
3222 " (1 safe square remains)");
3223 } else {
3224 sprintf(statusbar + strlen(statusbar),
3225 " (%d safe squares remain)", safe_closed);
3226 }
3227 }
3228 }
3229 if (ui->deaths)
3230 sprintf(statusbar + strlen(statusbar),
3231 " Deaths: %d", ui->deaths);
3232 status_bar(dr, statusbar);
3233 }
3234}
3235
3236static float game_anim_length(const game_state *oldstate,
3237 const game_state *newstate, int dir, game_ui *ui)
3238{
3239 return 0.0F;
3240}
3241
3242static float game_flash_length(const game_state *oldstate,
3243 const game_state *newstate, int dir, game_ui *ui)
3244{
3245 if (oldstate->used_solve || newstate->used_solve)
3246 return 0.0F;
3247
3248 if (dir > 0 && !oldstate->dead && !oldstate->won) {
3249 if (newstate->dead) {
3250 ui->flash_is_death = true;
3251 return 3 * FLASH_FRAME;
3252 }
3253 if (newstate->won) {
3254 ui->flash_is_death = false;
3255 return 2 * FLASH_FRAME;
3256 }
3257 }
3258 return 0.0F;
3259}
3260
3261static void game_get_cursor_location(const game_ui *ui,
3262 const game_drawstate *ds,
3263 const game_state *state,
3264 const game_params *params,
3265 int *x, int *y, int *w, int *h)
3266{
3267 if(ui->cur_visible) {
3268 *x = COORD(ui->cur_x);
3269 *y = COORD(ui->cur_y);
3270 *w = *h = TILE_SIZE;
3271 }
3272}
3273
3274static int game_status(const game_state *state)
3275{
3276 /*
3277 * We report the game as lost only if the player has used the
3278 * Solve function to reveal all the mines. Otherwise, we assume
3279 * they'll undo and continue play.
3280 */
3281 return state->won ? (state->used_solve ? -1 : +1) : 0;
3282}
3283
3284static bool game_timing_state(const game_state *state, game_ui *ui)
3285{
3286 if (state->dead || state->won || ui->completed || !state->layout->mines)
3287 return false;
3288 return true;
3289}
3290
3291#ifdef COMBINED
3292#define thegame mines
3293#endif
3294
3295const struct game thegame = {
3296 "Mines", "games.mines", "mines",
3297 default_params,
3298 game_fetch_preset, NULL,
3299 decode_params,
3300 encode_params,
3301 free_params,
3302 dup_params,
3303 true, game_configure, custom_params,
3304 validate_params,
3305 new_game_desc,
3306 validate_desc,
3307 new_game,
3308 dup_game,
3309 free_game,
3310 true, solve_game,
3311 true, game_can_format_as_text_now, game_text_format,
3312 NULL, NULL, /* get_prefs, set_prefs */
3313 new_ui,
3314 free_ui,
3315 encode_ui,
3316 decode_ui,
3317 NULL, /* game_request_keys */
3318 game_changed_state,
3319 current_key_label,
3320 interpret_move,
3321 execute_move,
3322 PREFERRED_TILE_SIZE, game_compute_size, game_set_size,
3323 game_colours,
3324 game_new_drawstate,
3325 game_free_drawstate,
3326 game_redraw,
3327 game_anim_length,
3328 game_flash_length,
3329 game_get_cursor_location,
3330 game_status,
3331 false, false, NULL, NULL, /* print_size, print */
3332 true, /* wants_statusbar */
3333 true, game_timing_state,
3334 BUTTON_BEATS(LEFT_BUTTON, RIGHT_BUTTON) | REQUIRE_RBUTTON,
3335};
3336
3337#ifdef STANDALONE_OBFUSCATOR
3338
3339/*
3340 * Vaguely useful stand-alone program which translates between
3341 * obfuscated and clear Mines game descriptions. Pass in a game
3342 * description on the command line, and if it's clear it will be
3343 * obfuscated and vice versa. The output text should also be a
3344 * valid game ID describing the same game. Like this:
3345 *
3346 * $ ./mineobfusc 9x9:4,4,mb071b49fbd1cb6a0d5868
3347 * 9x9:4,4,004000007c00010022080
3348 * $ ./mineobfusc 9x9:4,4,004000007c00010022080
3349 * 9x9:4,4,mb071b49fbd1cb6a0d5868
3350 */
3351
3352int main(int argc, char **argv)
3353{
3354 game_params *p;
3355 game_state *s;
3356 char *id = NULL, *desc;
3357 const char *err;
3358 int y, x;
3359
3360 while (--argc > 0) {
3361 char *p = *++argv;
3362 if (*p == '-') {
3363 fprintf(stderr, "%s: unrecognised option `%s'\n", argv[0], p);
3364 return 1;
3365 } else {
3366 id = p;
3367 }
3368 }
3369
3370 if (!id) {
3371 fprintf(stderr, "usage: %s <game_id>\n", argv[0]);
3372 return 1;
3373 }
3374
3375 desc = strchr(id, ':');
3376 if (!desc) {
3377 fprintf(stderr, "%s: game id expects a colon in it\n", argv[0]);
3378 return 1;
3379 }
3380 *desc++ = '\0';
3381
3382 p = default_params();
3383 decode_params(p, id);
3384 err = validate_desc(p, desc);
3385 if (err) {
3386 fprintf(stderr, "%s: %s\n", argv[0], err);
3387 return 1;
3388 }
3389 s = new_game(NULL, p, desc);
3390
3391 x = atoi(desc);
3392 while (*desc && *desc != ',') desc++;
3393 if (*desc) desc++;
3394 y = atoi(desc);
3395 while (*desc && *desc != ',') desc++;
3396 if (*desc) desc++;
3397
3398 printf("%s:%s\n", id, describe_layout(s->layout->mines,
3399 p->w * p->h,
3400 x, y,
3401 (*desc != 'm')));
3402
3403 return 0;
3404}
3405
3406#endif
3407
3408/* vim: set shiftwidth=4 tabstop=8: */