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