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/flood.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/flood.c')
-rw-r--r-- | apps/plugins/puzzles/src/flood.c | 1372 |
1 files changed, 1372 insertions, 0 deletions
diff --git a/apps/plugins/puzzles/src/flood.c b/apps/plugins/puzzles/src/flood.c new file mode 100644 index 0000000000..1262be8175 --- /dev/null +++ b/apps/plugins/puzzles/src/flood.c | |||
@@ -0,0 +1,1372 @@ | |||
1 | /* | ||
2 | * flood.c: puzzle in which you make a grid all the same colour by | ||
3 | * repeatedly flood-filling the top left corner, and try to do so in | ||
4 | * as few moves as possible. | ||
5 | */ | ||
6 | |||
7 | /* | ||
8 | * Possible further work: | ||
9 | * | ||
10 | * - UI: perhaps we should only permit clicking on regions that can | ||
11 | * actually be reached by the next flood-fill - i.e. a click is | ||
12 | * only interpreted as a move if it would cause the clicked-on | ||
13 | * square to become part of the controlled area. This provides a | ||
14 | * hint in cases where you mistakenly thought that would happen, | ||
15 | * and protects you against typos in cases where you just | ||
16 | * mis-aimed. | ||
17 | * | ||
18 | * - UI: perhaps mark the fill square in some way? Or even mark the | ||
19 | * whole connected component _containing_ the fill square. Pro: | ||
20 | * that would make it easier to tell apart cases where almost all | ||
21 | * the yellow squares in the grid are part of the target component | ||
22 | * (hence, yellow is _done_ and you never have to fill in that | ||
23 | * colour again) from cases where there's still one yellow square | ||
24 | * that's only diagonally adjacent and hence will need coming back | ||
25 | * to. Con: but it would almost certainly be ugly. | ||
26 | */ | ||
27 | |||
28 | #include <stdio.h> | ||
29 | #include <stdlib.h> | ||
30 | #include <stdarg.h> | ||
31 | #include <string.h> | ||
32 | #include <assert.h> | ||
33 | #include <ctype.h> | ||
34 | #include <math.h> | ||
35 | |||
36 | #include "puzzles.h" | ||
37 | |||
38 | enum { | ||
39 | COL_BACKGROUND, COL_SEPARATOR, | ||
40 | COL_1, COL_2, COL_3, COL_4, COL_5, COL_6, COL_7, COL_8, COL_9, COL_10, | ||
41 | COL_HIGHLIGHT, COL_LOWLIGHT, | ||
42 | NCOLOURS | ||
43 | }; | ||
44 | |||
45 | struct game_params { | ||
46 | int w, h; | ||
47 | int colours; | ||
48 | int leniency; | ||
49 | }; | ||
50 | |||
51 | /* Just in case I want to make this changeable later, I'll put the | ||
52 | * coordinates of the flood-fill point here so that it'll be easy to | ||
53 | * find everywhere later that has to change. */ | ||
54 | #define FILLX 0 | ||
55 | #define FILLY 0 | ||
56 | |||
57 | typedef struct soln { | ||
58 | int refcount; | ||
59 | int nmoves; | ||
60 | char *moves; | ||
61 | } soln; | ||
62 | |||
63 | struct game_state { | ||
64 | int w, h, colours; | ||
65 | int moves, movelimit; | ||
66 | int complete; | ||
67 | char *grid; | ||
68 | int cheated; | ||
69 | int solnpos; | ||
70 | soln *soln; | ||
71 | }; | ||
72 | |||
73 | static game_params *default_params(void) | ||
74 | { | ||
75 | game_params *ret = snew(game_params); | ||
76 | |||
77 | ret->w = ret->h = 12; | ||
78 | ret->colours = 6; | ||
79 | ret->leniency = 5; | ||
80 | |||
81 | return ret; | ||
82 | } | ||
83 | |||
84 | static const struct { | ||
85 | struct game_params preset; | ||
86 | const char *name; | ||
87 | } flood_presets[] = { | ||
88 | /* Default 12x12 size, three difficulty levels. */ | ||
89 | {{12, 12, 6, 5}, "12x12 Easy"}, | ||
90 | {{12, 12, 6, 2}, "12x12 Medium"}, | ||
91 | {{12, 12, 6, 0}, "12x12 Hard"}, | ||
92 | /* Larger puzzles, leaving off Easy in the expectation that people | ||
93 | * wanting a bigger grid will have played it enough to find Easy | ||
94 | * easy. */ | ||
95 | {{16, 16, 6, 2}, "16x16 Medium"}, | ||
96 | {{16, 16, 6, 0}, "16x16 Hard"}, | ||
97 | /* A couple of different colour counts. It seems generally not too | ||
98 | * hard with fewer colours (probably because fewer choices), so no | ||
99 | * extra moves for these modes. */ | ||
100 | {{12, 12, 3, 0}, "12x12, 3 colours"}, | ||
101 | {{12, 12, 4, 0}, "12x12, 4 colours"}, | ||
102 | }; | ||
103 | |||
104 | static int game_fetch_preset(int i, char **name, game_params **params) | ||
105 | { | ||
106 | game_params *ret; | ||
107 | |||
108 | if (i < 0 || i >= lenof(flood_presets)) | ||
109 | return FALSE; | ||
110 | |||
111 | ret = snew(game_params); | ||
112 | *ret = flood_presets[i].preset; | ||
113 | *name = dupstr(flood_presets[i].name); | ||
114 | *params = ret; | ||
115 | return TRUE; | ||
116 | } | ||
117 | |||
118 | static void free_params(game_params *params) | ||
119 | { | ||
120 | sfree(params); | ||
121 | } | ||
122 | |||
123 | static game_params *dup_params(const game_params *params) | ||
124 | { | ||
125 | game_params *ret = snew(game_params); | ||
126 | *ret = *params; /* structure copy */ | ||
127 | return ret; | ||
128 | } | ||
129 | |||
130 | static void decode_params(game_params *ret, char const *string) | ||
131 | { | ||
132 | ret->w = ret->h = atoi(string); | ||
133 | while (*string && isdigit((unsigned char)*string)) string++; | ||
134 | if (*string == 'x') { | ||
135 | string++; | ||
136 | ret->h = atoi(string); | ||
137 | while (*string && isdigit((unsigned char)*string)) string++; | ||
138 | } | ||
139 | while (*string) { | ||
140 | if (*string == 'c') { | ||
141 | string++; | ||
142 | ret->colours = atoi(string); | ||
143 | while (string[1] && isdigit((unsigned char)string[1])) string++; | ||
144 | } else if (*string == 'm') { | ||
145 | string++; | ||
146 | ret->leniency = atoi(string); | ||
147 | while (string[1] && isdigit((unsigned char)string[1])) string++; | ||
148 | } | ||
149 | string++; | ||
150 | } | ||
151 | } | ||
152 | |||
153 | static char *encode_params(const game_params *params, int full) | ||
154 | { | ||
155 | char buf[256]; | ||
156 | sprintf(buf, "%dx%d", params->w, params->h); | ||
157 | if (full) | ||
158 | sprintf(buf + strlen(buf), "c%dm%d", | ||
159 | params->colours, params->leniency); | ||
160 | return dupstr(buf); | ||
161 | } | ||
162 | |||
163 | static config_item *game_configure(const game_params *params) | ||
164 | { | ||
165 | config_item *ret; | ||
166 | char buf[80]; | ||
167 | |||
168 | ret = snewn(5, config_item); | ||
169 | |||
170 | ret[0].name = "Width"; | ||
171 | ret[0].type = C_STRING; | ||
172 | sprintf(buf, "%d", params->w); | ||
173 | ret[0].sval = dupstr(buf); | ||
174 | ret[0].ival = 0; | ||
175 | |||
176 | ret[1].name = "Height"; | ||
177 | ret[1].type = C_STRING; | ||
178 | sprintf(buf, "%d", params->h); | ||
179 | ret[1].sval = dupstr(buf); | ||
180 | ret[1].ival = 0; | ||
181 | |||
182 | ret[2].name = "Colours"; | ||
183 | ret[2].type = C_STRING; | ||
184 | sprintf(buf, "%d", params->colours); | ||
185 | ret[2].sval = dupstr(buf); | ||
186 | ret[2].ival = 0; | ||
187 | |||
188 | ret[3].name = "Extra moves permitted"; | ||
189 | ret[3].type = C_STRING; | ||
190 | sprintf(buf, "%d", params->leniency); | ||
191 | ret[3].sval = dupstr(buf); | ||
192 | ret[3].ival = 0; | ||
193 | |||
194 | ret[4].name = NULL; | ||
195 | ret[4].type = C_END; | ||
196 | ret[4].sval = NULL; | ||
197 | ret[4].ival = 0; | ||
198 | |||
199 | return ret; | ||
200 | } | ||
201 | |||
202 | static game_params *custom_params(const config_item *cfg) | ||
203 | { | ||
204 | game_params *ret = snew(game_params); | ||
205 | |||
206 | ret->w = atoi(cfg[0].sval); | ||
207 | ret->h = atoi(cfg[1].sval); | ||
208 | ret->colours = atoi(cfg[2].sval); | ||
209 | ret->leniency = atoi(cfg[3].sval); | ||
210 | |||
211 | return ret; | ||
212 | } | ||
213 | |||
214 | static char *validate_params(const game_params *params, int full) | ||
215 | { | ||
216 | if (params->w < 2 && params->h < 2) | ||
217 | return "Grid must contain at least two squares"; | ||
218 | if (params->colours < 3 || params->colours > 10) | ||
219 | return "Must have between 3 and 10 colours"; | ||
220 | if (params->leniency < 0) | ||
221 | return "Leniency must be non-negative"; | ||
222 | return NULL; | ||
223 | } | ||
224 | |||
225 | #if 0 | ||
226 | /* | ||
227 | * Bodge to permit varying the recursion depth for testing purposes. | ||
228 | |||
229 | To test two Floods against each other: | ||
230 | |||
231 | paste <(./flood.1 --generate 100 12x12c6m0#12345 | cut -f2 -d,) <(./flood.2 --generate 100 12x12c6m0#12345 | cut -f2 -d,) | awk '{print $2-$1}' | sort -n | uniq -c | awk '{print $2,$1}' | tee z | ||
232 | |||
233 | and then run gnuplot and plot "z". | ||
234 | |||
235 | */ | ||
236 | static int rdepth = 0; | ||
237 | #define RECURSION_DEPTH (rdepth) | ||
238 | void check_recursion_depth(void) | ||
239 | { | ||
240 | if (!rdepth) { | ||
241 | const char *depthstr = getenv("FLOOD_DEPTH"); | ||
242 | rdepth = depthstr ? atoi(depthstr) : 1; | ||
243 | rdepth = rdepth > 0 ? rdepth : 1; | ||
244 | } | ||
245 | } | ||
246 | #else | ||
247 | /* | ||
248 | * Last time I empirically checked this, depth 3 was a noticeable | ||
249 | * improvement on 2, but 4 only negligibly better than 3. | ||
250 | */ | ||
251 | #define RECURSION_DEPTH 3 | ||
252 | #define check_recursion_depth() (void)0 | ||
253 | #endif | ||
254 | |||
255 | struct solver_scratch { | ||
256 | int *queue[2]; | ||
257 | int *dist; | ||
258 | char *grid, *grid2; | ||
259 | char *rgrids; | ||
260 | }; | ||
261 | |||
262 | static struct solver_scratch *new_scratch(int w, int h) | ||
263 | { | ||
264 | int wh = w*h; | ||
265 | struct solver_scratch *scratch = snew(struct solver_scratch); | ||
266 | check_recursion_depth(); | ||
267 | scratch->queue[0] = snewn(wh, int); | ||
268 | scratch->queue[1] = snewn(wh, int); | ||
269 | scratch->dist = snewn(wh, int); | ||
270 | scratch->grid = snewn(wh, char); | ||
271 | scratch->grid2 = snewn(wh, char); | ||
272 | scratch->rgrids = snewn(wh * RECURSION_DEPTH, char); | ||
273 | return scratch; | ||
274 | } | ||
275 | |||
276 | static void free_scratch(struct solver_scratch *scratch) | ||
277 | { | ||
278 | sfree(scratch->queue[0]); | ||
279 | sfree(scratch->queue[1]); | ||
280 | sfree(scratch->dist); | ||
281 | sfree(scratch->grid); | ||
282 | sfree(scratch->grid2); | ||
283 | sfree(scratch->rgrids); | ||
284 | sfree(scratch); | ||
285 | } | ||
286 | |||
287 | #if 0 | ||
288 | /* Diagnostic routines you can uncomment if you need them */ | ||
289 | void dump_grid(int w, int h, const char *grid, const char *titlefmt, ...) | ||
290 | { | ||
291 | int x, y; | ||
292 | if (titlefmt) { | ||
293 | va_list ap; | ||
294 | va_start(ap, titlefmt); | ||
295 | vprintf(titlefmt, ap); | ||
296 | va_end(ap); | ||
297 | printf(":\n"); | ||
298 | } else { | ||
299 | printf("Grid:\n"); | ||
300 | } | ||
301 | for (y = 0; y < h; y++) { | ||
302 | printf(" "); | ||
303 | for (x = 0; x < w; x++) { | ||
304 | printf("%1x", grid[y*w+x]); | ||
305 | } | ||
306 | printf("\n"); | ||
307 | } | ||
308 | } | ||
309 | |||
310 | void dump_dist(int w, int h, const int *dists, const char *titlefmt, ...) | ||
311 | { | ||
312 | int x, y; | ||
313 | if (titlefmt) { | ||
314 | va_list ap; | ||
315 | va_start(ap, titlefmt); | ||
316 | vprintf(titlefmt, ap); | ||
317 | va_end(ap); | ||
318 | printf(":\n"); | ||
319 | } else { | ||
320 | printf("Distances:\n"); | ||
321 | } | ||
322 | for (y = 0; y < h; y++) { | ||
323 | printf(" "); | ||
324 | for (x = 0; x < w; x++) { | ||
325 | printf("%3d", dists[y*w+x]); | ||
326 | } | ||
327 | printf("\n"); | ||
328 | } | ||
329 | } | ||
330 | #endif | ||
331 | |||
332 | /* | ||
333 | * Search a grid to find the most distant square(s). Return their | ||
334 | * distance and the number of them, and also the number of squares in | ||
335 | * the current controlled set (i.e. at distance zero). | ||
336 | */ | ||
337 | static void search(int w, int h, char *grid, int x0, int y0, | ||
338 | struct solver_scratch *scratch, | ||
339 | int *rdist, int *rnumber, int *rcontrol) | ||
340 | { | ||
341 | int wh = w*h; | ||
342 | int i, qcurr, qhead, qtail, qnext, currdist, remaining; | ||
343 | |||
344 | for (i = 0; i < wh; i++) | ||
345 | scratch->dist[i] = -1; | ||
346 | scratch->queue[0][0] = y0*w+x0; | ||
347 | scratch->queue[1][0] = y0*w+x0; | ||
348 | scratch->dist[y0*w+x0] = 0; | ||
349 | currdist = 0; | ||
350 | qcurr = 0; | ||
351 | qtail = 0; | ||
352 | qhead = 1; | ||
353 | qnext = 1; | ||
354 | remaining = wh - 1; | ||
355 | |||
356 | while (1) { | ||
357 | if (qtail == qhead) { | ||
358 | /* Switch queues. */ | ||
359 | if (currdist == 0) | ||
360 | *rcontrol = qhead; | ||
361 | currdist++; | ||
362 | qcurr ^= 1; /* switch queues */ | ||
363 | qhead = qnext; | ||
364 | qtail = 0; | ||
365 | qnext = 0; | ||
366 | #if 0 | ||
367 | printf("switch queue, new dist %d, queue %d\n", currdist, qhead); | ||
368 | #endif | ||
369 | } else if (remaining == 0 && qnext == 0) { | ||
370 | break; | ||
371 | } else { | ||
372 | int pos = scratch->queue[qcurr][qtail++]; | ||
373 | int y = pos / w; | ||
374 | int x = pos % w; | ||
375 | #if 0 | ||
376 | printf("checking neighbours of %d,%d\n", x, y); | ||
377 | #endif | ||
378 | int dir; | ||
379 | for (dir = 0; dir < 4; dir++) { | ||
380 | int y1 = y + (dir == 1 ? 1 : dir == 3 ? -1 : 0); | ||
381 | int x1 = x + (dir == 0 ? 1 : dir == 2 ? -1 : 0); | ||
382 | if (0 <= x1 && x1 < w && 0 <= y1 && y1 < h) { | ||
383 | int pos1 = y1*w+x1; | ||
384 | #if 0 | ||
385 | printf("trying %d,%d: colours %d-%d dist %d\n", x1, y1, | ||
386 | grid[pos], grid[pos1], scratch->dist[pos]); | ||
387 | #endif | ||
388 | if (scratch->dist[pos1] == -1 && | ||
389 | ((grid[pos1] == grid[pos] && | ||
390 | scratch->dist[pos] == currdist) || | ||
391 | (grid[pos1] != grid[pos] && | ||
392 | scratch->dist[pos] == currdist - 1))) { | ||
393 | #if 0 | ||
394 | printf("marking %d,%d dist %d\n", x1, y1, currdist); | ||
395 | #endif | ||
396 | scratch->queue[qcurr][qhead++] = pos1; | ||
397 | scratch->queue[qcurr^1][qnext++] = pos1; | ||
398 | scratch->dist[pos1] = currdist; | ||
399 | remaining--; | ||
400 | } | ||
401 | } | ||
402 | } | ||
403 | } | ||
404 | } | ||
405 | |||
406 | *rdist = currdist; | ||
407 | *rnumber = qhead; | ||
408 | if (currdist == 0) | ||
409 | *rcontrol = qhead; | ||
410 | } | ||
411 | |||
412 | /* | ||
413 | * Enact a flood-fill move on a grid. | ||
414 | */ | ||
415 | static void fill(int w, int h, char *grid, int x0, int y0, char newcolour, | ||
416 | int *queue) | ||
417 | { | ||
418 | char oldcolour; | ||
419 | int qhead, qtail; | ||
420 | |||
421 | oldcolour = grid[y0*w+x0]; | ||
422 | assert(oldcolour != newcolour); | ||
423 | grid[y0*w+x0] = newcolour; | ||
424 | queue[0] = y0*w+x0; | ||
425 | qtail = 0; | ||
426 | qhead = 1; | ||
427 | |||
428 | while (qtail < qhead) { | ||
429 | int pos = queue[qtail++]; | ||
430 | int y = pos / w; | ||
431 | int x = pos % w; | ||
432 | int dir; | ||
433 | for (dir = 0; dir < 4; dir++) { | ||
434 | int y1 = y + (dir == 1 ? 1 : dir == 3 ? -1 : 0); | ||
435 | int x1 = x + (dir == 0 ? 1 : dir == 2 ? -1 : 0); | ||
436 | if (0 <= x1 && x1 < w && 0 <= y1 && y1 < h) { | ||
437 | int pos1 = y1*w+x1; | ||
438 | if (grid[pos1] == oldcolour) { | ||
439 | grid[pos1] = newcolour; | ||
440 | queue[qhead++] = pos1; | ||
441 | } | ||
442 | } | ||
443 | } | ||
444 | } | ||
445 | } | ||
446 | |||
447 | /* | ||
448 | * Detect a completed grid. | ||
449 | */ | ||
450 | static int completed(int w, int h, char *grid) | ||
451 | { | ||
452 | int wh = w*h; | ||
453 | int i; | ||
454 | |||
455 | for (i = 1; i < wh; i++) | ||
456 | if (grid[i] != grid[0]) | ||
457 | return FALSE; | ||
458 | |||
459 | return TRUE; | ||
460 | } | ||
461 | |||
462 | /* | ||
463 | * Try out every possible move on a grid, and choose whichever one | ||
464 | * reduced the result of search() by the most. | ||
465 | */ | ||
466 | static char choosemove_recurse(int w, int h, char *grid, int x0, int y0, | ||
467 | int maxmove, struct solver_scratch *scratch, | ||
468 | int depth, int *rbestdist, int *rbestnumber, int *rbestcontrol) | ||
469 | { | ||
470 | int wh = w*h; | ||
471 | char move, bestmove; | ||
472 | int dist, number, control, bestdist, bestnumber, bestcontrol; | ||
473 | char *tmpgrid; | ||
474 | |||
475 | assert(0 <= depth && depth < RECURSION_DEPTH); | ||
476 | tmpgrid = scratch->rgrids + depth*wh; | ||
477 | |||
478 | bestdist = wh + 1; | ||
479 | bestnumber = 0; | ||
480 | bestcontrol = 0; | ||
481 | bestmove = -1; | ||
482 | |||
483 | #if 0 | ||
484 | dump_grid(w, h, grid, "before choosemove_recurse %d", depth); | ||
485 | #endif | ||
486 | for (move = 0; move < maxmove; move++) { | ||
487 | if (grid[y0*w+x0] == move) | ||
488 | continue; | ||
489 | memcpy(tmpgrid, grid, wh * sizeof(*grid)); | ||
490 | fill(w, h, tmpgrid, x0, y0, move, scratch->queue[0]); | ||
491 | if (completed(w, h, tmpgrid)) { | ||
492 | /* | ||
493 | * A move that wins is immediately the best, so stop | ||
494 | * searching. Record what depth of recursion that happened | ||
495 | * at, so that higher levels will choose a move that gets | ||
496 | * to a winning position sooner. | ||
497 | */ | ||
498 | *rbestdist = -1; | ||
499 | *rbestnumber = depth; | ||
500 | *rbestcontrol = wh; | ||
501 | return move; | ||
502 | } | ||
503 | if (depth < RECURSION_DEPTH-1) { | ||
504 | choosemove_recurse(w, h, tmpgrid, x0, y0, maxmove, scratch, | ||
505 | depth+1, &dist, &number, &control); | ||
506 | } else { | ||
507 | #if 0 | ||
508 | dump_grid(w, h, tmpgrid, "after move %d at depth %d", | ||
509 | move, depth); | ||
510 | #endif | ||
511 | search(w, h, tmpgrid, x0, y0, scratch, &dist, &number, &control); | ||
512 | #if 0 | ||
513 | dump_dist(w, h, scratch->dist, "after move %d at depth %d", | ||
514 | move, depth); | ||
515 | printf("move %d at depth %d: %d at %d\n", | ||
516 | depth, move, number, dist); | ||
517 | #endif | ||
518 | } | ||
519 | if (dist < bestdist || | ||
520 | (dist == bestdist && | ||
521 | (number < bestnumber || | ||
522 | (number == bestnumber && | ||
523 | (control > bestcontrol))))) { | ||
524 | bestdist = dist; | ||
525 | bestnumber = number; | ||
526 | bestcontrol = control; | ||
527 | bestmove = move; | ||
528 | } | ||
529 | } | ||
530 | #if 0 | ||
531 | printf("best at depth %d was %d (%d at %d, %d controlled)\n", | ||
532 | depth, bestmove, bestnumber, bestdist, bestcontrol); | ||
533 | #endif | ||
534 | |||
535 | *rbestdist = bestdist; | ||
536 | *rbestnumber = bestnumber; | ||
537 | *rbestcontrol = bestcontrol; | ||
538 | return bestmove; | ||
539 | } | ||
540 | static char choosemove(int w, int h, char *grid, int x0, int y0, | ||
541 | int maxmove, struct solver_scratch *scratch) | ||
542 | { | ||
543 | int tmp0, tmp1, tmp2; | ||
544 | return choosemove_recurse(w, h, grid, x0, y0, maxmove, scratch, | ||
545 | 0, &tmp0, &tmp1, &tmp2); | ||
546 | } | ||
547 | |||
548 | static char *new_game_desc(const game_params *params, random_state *rs, | ||
549 | char **aux, int interactive) | ||
550 | { | ||
551 | int w = params->w, h = params->h, wh = w*h; | ||
552 | int i, moves; | ||
553 | char *desc; | ||
554 | struct solver_scratch *scratch; | ||
555 | |||
556 | scratch = new_scratch(w, h); | ||
557 | |||
558 | /* | ||
559 | * Invent a random grid. | ||
560 | */ | ||
561 | for (i = 0; i < wh; i++) | ||
562 | scratch->grid[i] = random_upto(rs, params->colours); | ||
563 | |||
564 | /* | ||
565 | * Run the solver, and count how many moves it uses. | ||
566 | */ | ||
567 | memcpy(scratch->grid2, scratch->grid, wh * sizeof(*scratch->grid2)); | ||
568 | moves = 0; | ||
569 | check_recursion_depth(); | ||
570 | while (!completed(w, h, scratch->grid2)) { | ||
571 | char move = choosemove(w, h, scratch->grid2, FILLX, FILLY, | ||
572 | params->colours, scratch); | ||
573 | fill(w, h, scratch->grid2, FILLX, FILLY, move, scratch->queue[0]); | ||
574 | moves++; | ||
575 | } | ||
576 | |||
577 | /* | ||
578 | * Adjust for difficulty. | ||
579 | */ | ||
580 | moves += params->leniency; | ||
581 | |||
582 | /* | ||
583 | * Encode the game id. | ||
584 | */ | ||
585 | desc = snewn(wh + 40, char); | ||
586 | for (i = 0; i < wh; i++) { | ||
587 | char colour = scratch->grid[i]; | ||
588 | char textcolour = (colour > 9 ? 'A' : '0') + colour; | ||
589 | desc[i] = textcolour; | ||
590 | } | ||
591 | sprintf(desc+i, ",%d", moves); | ||
592 | |||
593 | free_scratch(scratch); | ||
594 | |||
595 | return desc; | ||
596 | } | ||
597 | |||
598 | static char *validate_desc(const game_params *params, const char *desc) | ||
599 | { | ||
600 | int w = params->w, h = params->h, wh = w*h; | ||
601 | int i; | ||
602 | for (i = 0; i < wh; i++) { | ||
603 | char c = *desc++; | ||
604 | if (c == 0) | ||
605 | return "Not enough data in grid description"; | ||
606 | if (c >= '0' && c <= '9') | ||
607 | c -= '0'; | ||
608 | else if (c >= 'A' && c <= 'Z') | ||
609 | c = 10 + (c - 'A'); | ||
610 | else | ||
611 | return "Bad character in grid description"; | ||
612 | if ((unsigned)c >= params->colours) | ||
613 | return "Colour out of range in grid description"; | ||
614 | } | ||
615 | if (*desc != ',') | ||
616 | return "Expected ',' after grid description"; | ||
617 | desc++; | ||
618 | if (desc[strspn(desc, "0123456789")]) | ||
619 | return "Badly formatted move limit after grid description"; | ||
620 | return NULL; | ||
621 | } | ||
622 | |||
623 | static game_state *new_game(midend *me, const game_params *params, | ||
624 | const char *desc) | ||
625 | { | ||
626 | int w = params->w, h = params->h, wh = w*h; | ||
627 | game_state *state = snew(game_state); | ||
628 | int i; | ||
629 | |||
630 | state->w = w; | ||
631 | state->h = h; | ||
632 | state->colours = params->colours; | ||
633 | state->moves = 0; | ||
634 | state->grid = snewn(wh, char); | ||
635 | |||
636 | for (i = 0; i < wh; i++) { | ||
637 | char c = *desc++; | ||
638 | assert(c); | ||
639 | if (c >= '0' && c <= '9') | ||
640 | c -= '0'; | ||
641 | else if (c >= 'A' && c <= 'Z') | ||
642 | c = 10 + (c - 'A'); | ||
643 | else | ||
644 | assert(!"bad colour"); | ||
645 | state->grid[i] = c; | ||
646 | } | ||
647 | assert(*desc == ','); | ||
648 | desc++; | ||
649 | |||
650 | state->movelimit = atoi(desc); | ||
651 | state->complete = FALSE; | ||
652 | state->cheated = FALSE; | ||
653 | state->solnpos = 0; | ||
654 | state->soln = NULL; | ||
655 | |||
656 | return state; | ||
657 | } | ||
658 | |||
659 | static game_state *dup_game(const game_state *state) | ||
660 | { | ||
661 | game_state *ret = snew(game_state); | ||
662 | |||
663 | ret->w = state->w; | ||
664 | ret->h = state->h; | ||
665 | ret->colours = state->colours; | ||
666 | ret->moves = state->moves; | ||
667 | ret->movelimit = state->movelimit; | ||
668 | ret->complete = state->complete; | ||
669 | ret->grid = snewn(state->w * state->h, char); | ||
670 | memcpy(ret->grid, state->grid, state->w * state->h * sizeof(*ret->grid)); | ||
671 | |||
672 | ret->cheated = state->cheated; | ||
673 | ret->soln = state->soln; | ||
674 | if (ret->soln) | ||
675 | ret->soln->refcount++; | ||
676 | ret->solnpos = state->solnpos; | ||
677 | |||
678 | return ret; | ||
679 | } | ||
680 | |||
681 | static void free_game(game_state *state) | ||
682 | { | ||
683 | if (state->soln && --state->soln->refcount == 0) { | ||
684 | sfree(state->soln->moves); | ||
685 | sfree(state->soln); | ||
686 | } | ||
687 | sfree(state->grid); | ||
688 | sfree(state); | ||
689 | } | ||
690 | |||
691 | static char *solve_game(const game_state *state, const game_state *currstate, | ||
692 | const char *aux, char **error) | ||
693 | { | ||
694 | int w = state->w, h = state->h, wh = w*h; | ||
695 | char *moves, *ret, *p; | ||
696 | int i, len, nmoves; | ||
697 | char buf[256]; | ||
698 | struct solver_scratch *scratch; | ||
699 | |||
700 | if (currstate->complete) { | ||
701 | *error = "Puzzle is already solved"; | ||
702 | return NULL; | ||
703 | } | ||
704 | |||
705 | /* | ||
706 | * Find the best solution our solver can give. | ||
707 | */ | ||
708 | moves = snewn(wh, char); /* sure to be enough */ | ||
709 | nmoves = 0; | ||
710 | scratch = new_scratch(w, h); | ||
711 | memcpy(scratch->grid2, currstate->grid, wh * sizeof(*scratch->grid2)); | ||
712 | check_recursion_depth(); | ||
713 | while (!completed(w, h, scratch->grid2)) { | ||
714 | char move = choosemove(w, h, scratch->grid2, FILLX, FILLY, | ||
715 | currstate->colours, scratch); | ||
716 | fill(w, h, scratch->grid2, FILLX, FILLY, move, scratch->queue[0]); | ||
717 | assert(nmoves < wh); | ||
718 | moves[nmoves++] = move; | ||
719 | } | ||
720 | free_scratch(scratch); | ||
721 | |||
722 | /* | ||
723 | * Encode it as a move string. | ||
724 | */ | ||
725 | len = 1; /* trailing NUL */ | ||
726 | for (i = 0; i < nmoves; i++) | ||
727 | len += sprintf(buf, ",%d", moves[i]); | ||
728 | ret = snewn(len, char); | ||
729 | p = ret; | ||
730 | for (i = 0; i < nmoves; i++) | ||
731 | p += sprintf(p, "%c%d", (i==0 ? 'S' : ','), moves[i]); | ||
732 | assert(p - ret == len - 1); | ||
733 | |||
734 | sfree(moves); | ||
735 | return ret; | ||
736 | } | ||
737 | |||
738 | static int game_can_format_as_text_now(const game_params *params) | ||
739 | { | ||
740 | return TRUE; | ||
741 | } | ||
742 | |||
743 | static char *game_text_format(const game_state *state) | ||
744 | { | ||
745 | int w = state->w, h = state->h; | ||
746 | char *ret, *p; | ||
747 | int x, y, len; | ||
748 | |||
749 | len = h * (w+1); /* +1 for newline after each row */ | ||
750 | ret = snewn(len+1, char); /* and +1 for terminating \0 */ | ||
751 | p = ret; | ||
752 | |||
753 | for (y = 0; y < h; y++) { | ||
754 | for (x = 0; x < w; x++) { | ||
755 | char colour = state->grid[y*w+x]; | ||
756 | char textcolour = (colour > 9 ? 'A' : '0') + colour; | ||
757 | *p++ = textcolour; | ||
758 | } | ||
759 | *p++ = '\n'; | ||
760 | } | ||
761 | |||
762 | assert(p - ret == len); | ||
763 | *p = '\0'; | ||
764 | |||
765 | return ret; | ||
766 | } | ||
767 | |||
768 | struct game_ui { | ||
769 | int cursor_visible; | ||
770 | int cx, cy; | ||
771 | enum { VICTORY, DEFEAT } flash_type; | ||
772 | }; | ||
773 | |||
774 | static game_ui *new_ui(const game_state *state) | ||
775 | { | ||
776 | struct game_ui *ui = snew(struct game_ui); | ||
777 | ui->cursor_visible = FALSE; | ||
778 | ui->cx = FILLX; | ||
779 | ui->cy = FILLY; | ||
780 | return ui; | ||
781 | } | ||
782 | |||
783 | static void free_ui(game_ui *ui) | ||
784 | { | ||
785 | sfree(ui); | ||
786 | } | ||
787 | |||
788 | static char *encode_ui(const game_ui *ui) | ||
789 | { | ||
790 | return NULL; | ||
791 | } | ||
792 | |||
793 | static void decode_ui(game_ui *ui, const char *encoding) | ||
794 | { | ||
795 | } | ||
796 | |||
797 | static void game_changed_state(game_ui *ui, const game_state *oldstate, | ||
798 | const game_state *newstate) | ||
799 | { | ||
800 | } | ||
801 | |||
802 | struct game_drawstate { | ||
803 | int started; | ||
804 | int tilesize; | ||
805 | int *grid; | ||
806 | }; | ||
807 | |||
808 | #define TILESIZE (ds->tilesize) | ||
809 | #define PREFERRED_TILESIZE 32 | ||
810 | #define BORDER (TILESIZE / 2) | ||
811 | #define SEP_WIDTH (TILESIZE / 32) | ||
812 | #define CURSOR_INSET (TILESIZE / 8) | ||
813 | #define HIGHLIGHT_WIDTH (TILESIZE / 10) | ||
814 | #define COORD(x) ( (x) * TILESIZE + BORDER ) | ||
815 | #define FROMCOORD(x) ( ((x) - BORDER + TILESIZE) / TILESIZE - 1 ) | ||
816 | #define VICTORY_FLASH_FRAME 0.03F | ||
817 | #define DEFEAT_FLASH_FRAME 0.10F | ||
818 | |||
819 | static char *interpret_move(const game_state *state, game_ui *ui, | ||
820 | const game_drawstate *ds, | ||
821 | int x, int y, int button) | ||
822 | { | ||
823 | int w = state->w, h = state->h; | ||
824 | int tx = -1, ty = -1, move = -1; | ||
825 | |||
826 | if (button == LEFT_BUTTON) { | ||
827 | tx = FROMCOORD(x); | ||
828 | ty = FROMCOORD(y); | ||
829 | ui->cursor_visible = FALSE; | ||
830 | } else if (button == CURSOR_LEFT && ui->cx > 0) { | ||
831 | ui->cx--; | ||
832 | ui->cursor_visible = TRUE; | ||
833 | return ""; | ||
834 | } else if (button == CURSOR_RIGHT && ui->cx+1 < w) { | ||
835 | ui->cx++; | ||
836 | ui->cursor_visible = TRUE; | ||
837 | return ""; | ||
838 | } else if (button == CURSOR_UP && ui->cy > 0) { | ||
839 | ui->cy--; | ||
840 | ui->cursor_visible = TRUE; | ||
841 | return ""; | ||
842 | } else if (button == CURSOR_DOWN && ui->cy+1 < h) { | ||
843 | ui->cy++; | ||
844 | ui->cursor_visible = TRUE; | ||
845 | return ""; | ||
846 | } else if (button == CURSOR_SELECT) { | ||
847 | tx = ui->cx; | ||
848 | ty = ui->cy; | ||
849 | } else if (button == CURSOR_SELECT2 && | ||
850 | state->soln && state->solnpos < state->soln->nmoves) { | ||
851 | move = state->soln->moves[state->solnpos]; | ||
852 | } else { | ||
853 | return NULL; | ||
854 | } | ||
855 | |||
856 | if (tx >= 0 && tx < w && ty >= 0 && ty < h && | ||
857 | state->grid[0] != state->grid[ty*w+tx]) | ||
858 | move = state->grid[ty*w+tx]; | ||
859 | |||
860 | if (move >= 0 && !state->complete) { | ||
861 | char buf[256]; | ||
862 | sprintf(buf, "M%d", move); | ||
863 | return dupstr(buf); | ||
864 | } | ||
865 | |||
866 | return NULL; | ||
867 | } | ||
868 | |||
869 | static game_state *execute_move(const game_state *state, const char *move) | ||
870 | { | ||
871 | game_state *ret; | ||
872 | int c; | ||
873 | |||
874 | if (move[0] == 'M' && | ||
875 | sscanf(move+1, "%d", &c) == 1 && | ||
876 | c >= 0 && | ||
877 | !state->complete) { | ||
878 | int *queue = snewn(state->w * state->h, int); | ||
879 | ret = dup_game(state); | ||
880 | fill(ret->w, ret->h, ret->grid, FILLX, FILLY, c, queue); | ||
881 | ret->moves++; | ||
882 | ret->complete = completed(ret->w, ret->h, ret->grid); | ||
883 | |||
884 | if (ret->soln) { | ||
885 | /* | ||
886 | * If this move is the correct next one in the stored | ||
887 | * solution path, advance solnpos. | ||
888 | */ | ||
889 | if (c == ret->soln->moves[ret->solnpos] && | ||
890 | ret->solnpos+1 < ret->soln->nmoves) { | ||
891 | ret->solnpos++; | ||
892 | } else { | ||
893 | /* | ||
894 | * Otherwise, the user has strayed from the path or | ||
895 | * else the path has come to an end; either way, the | ||
896 | * path is no longer valid. | ||
897 | */ | ||
898 | ret->soln->refcount--; | ||
899 | assert(ret->soln->refcount > 0);/* `state' at least still exists */ | ||
900 | ret->soln = NULL; | ||
901 | ret->solnpos = 0; | ||
902 | } | ||
903 | } | ||
904 | |||
905 | sfree(queue); | ||
906 | return ret; | ||
907 | } else if (*move == 'S') { | ||
908 | soln *sol; | ||
909 | const char *p; | ||
910 | int i; | ||
911 | |||
912 | /* | ||
913 | * This is a solve move, so we don't actually _change_ the | ||
914 | * grid but merely set up a stored solution path. | ||
915 | */ | ||
916 | move++; | ||
917 | sol = snew(soln); | ||
918 | |||
919 | sol->nmoves = 1; | ||
920 | for (p = move; *p; p++) { | ||
921 | if (*p == ',') | ||
922 | sol->nmoves++; | ||
923 | } | ||
924 | |||
925 | sol->moves = snewn(sol->nmoves, char); | ||
926 | for (i = 0, p = move; i < sol->nmoves; i++) { | ||
927 | assert(*p); | ||
928 | sol->moves[i] = atoi(p); | ||
929 | p += strspn(p, "0123456789"); | ||
930 | if (*p) { | ||
931 | assert(*p == ','); | ||
932 | p++; | ||
933 | } | ||
934 | } | ||
935 | |||
936 | ret = dup_game(state); | ||
937 | ret->cheated = TRUE; | ||
938 | if (ret->soln && --ret->soln->refcount == 0) { | ||
939 | sfree(ret->soln->moves); | ||
940 | sfree(ret->soln); | ||
941 | } | ||
942 | ret->soln = sol; | ||
943 | ret->solnpos = 0; | ||
944 | sol->refcount = 1; | ||
945 | return ret; | ||
946 | } | ||
947 | |||
948 | return NULL; | ||
949 | } | ||
950 | |||
951 | /* ---------------------------------------------------------------------- | ||
952 | * Drawing routines. | ||
953 | */ | ||
954 | |||
955 | static void game_compute_size(const game_params *params, int tilesize, | ||
956 | int *x, int *y) | ||
957 | { | ||
958 | /* Ick: fake up `ds->tilesize' for macro expansion purposes */ | ||
959 | struct { int tilesize; } ads, *ds = &ads; | ||
960 | ads.tilesize = tilesize; | ||
961 | |||
962 | *x = BORDER * 2 + TILESIZE * params->w; | ||
963 | *y = BORDER * 2 + TILESIZE * params->h; | ||
964 | } | ||
965 | |||
966 | static void game_set_size(drawing *dr, game_drawstate *ds, | ||
967 | const game_params *params, int tilesize) | ||
968 | { | ||
969 | ds->tilesize = tilesize; | ||
970 | } | ||
971 | |||
972 | static float *game_colours(frontend *fe, int *ncolours) | ||
973 | { | ||
974 | float *ret = snewn(3 * NCOLOURS, float); | ||
975 | |||
976 | game_mkhighlight(fe, ret, COL_BACKGROUND, COL_HIGHLIGHT, COL_LOWLIGHT); | ||
977 | |||
978 | ret[COL_SEPARATOR * 3 + 0] = 0.0F; | ||
979 | ret[COL_SEPARATOR * 3 + 1] = 0.0F; | ||
980 | ret[COL_SEPARATOR * 3 + 2] = 0.0F; | ||
981 | |||
982 | /* red */ | ||
983 | ret[COL_1 * 3 + 0] = 1.0F; | ||
984 | ret[COL_1 * 3 + 1] = 0.0F; | ||
985 | ret[COL_1 * 3 + 2] = 0.0F; | ||
986 | |||
987 | /* yellow */ | ||
988 | ret[COL_2 * 3 + 0] = 1.0F; | ||
989 | ret[COL_2 * 3 + 1] = 1.0F; | ||
990 | ret[COL_2 * 3 + 2] = 0.0F; | ||
991 | |||
992 | /* green */ | ||
993 | ret[COL_3 * 3 + 0] = 0.0F; | ||
994 | ret[COL_3 * 3 + 1] = 1.0F; | ||
995 | ret[COL_3 * 3 + 2] = 0.0F; | ||
996 | |||
997 | /* blue */ | ||
998 | ret[COL_4 * 3 + 0] = 0.2F; | ||
999 | ret[COL_4 * 3 + 1] = 0.3F; | ||
1000 | ret[COL_4 * 3 + 2] = 1.0F; | ||
1001 | |||
1002 | /* orange */ | ||
1003 | ret[COL_5 * 3 + 0] = 1.0F; | ||
1004 | ret[COL_5 * 3 + 1] = 0.5F; | ||
1005 | ret[COL_5 * 3 + 2] = 0.0F; | ||
1006 | |||
1007 | /* purple */ | ||
1008 | ret[COL_6 * 3 + 0] = 0.5F; | ||
1009 | ret[COL_6 * 3 + 1] = 0.0F; | ||
1010 | ret[COL_6 * 3 + 2] = 0.7F; | ||
1011 | |||
1012 | /* brown */ | ||
1013 | ret[COL_7 * 3 + 0] = 0.5F; | ||
1014 | ret[COL_7 * 3 + 1] = 0.3F; | ||
1015 | ret[COL_7 * 3 + 2] = 0.3F; | ||
1016 | |||
1017 | /* light blue */ | ||
1018 | ret[COL_8 * 3 + 0] = 0.4F; | ||
1019 | ret[COL_8 * 3 + 1] = 0.8F; | ||
1020 | ret[COL_8 * 3 + 2] = 1.0F; | ||
1021 | |||
1022 | /* light green */ | ||
1023 | ret[COL_9 * 3 + 0] = 0.7F; | ||
1024 | ret[COL_9 * 3 + 1] = 1.0F; | ||
1025 | ret[COL_9 * 3 + 2] = 0.7F; | ||
1026 | |||
1027 | /* pink */ | ||
1028 | ret[COL_10 * 3 + 0] = 1.0F; | ||
1029 | ret[COL_10 * 3 + 1] = 0.6F; | ||
1030 | ret[COL_10 * 3 + 2] = 1.0F; | ||
1031 | |||
1032 | *ncolours = NCOLOURS; | ||
1033 | return ret; | ||
1034 | } | ||
1035 | |||
1036 | static game_drawstate *game_new_drawstate(drawing *dr, const game_state *state) | ||
1037 | { | ||
1038 | struct game_drawstate *ds = snew(struct game_drawstate); | ||
1039 | int w = state->w, h = state->h, wh = w*h; | ||
1040 | int i; | ||
1041 | |||
1042 | ds->started = FALSE; | ||
1043 | ds->tilesize = 0; | ||
1044 | ds->grid = snewn(wh, int); | ||
1045 | for (i = 0; i < wh; i++) | ||
1046 | ds->grid[i] = -1; | ||
1047 | |||
1048 | return ds; | ||
1049 | } | ||
1050 | |||
1051 | static void game_free_drawstate(drawing *dr, game_drawstate *ds) | ||
1052 | { | ||
1053 | sfree(ds->grid); | ||
1054 | sfree(ds); | ||
1055 | } | ||
1056 | |||
1057 | #define BORDER_L 0x001 | ||
1058 | #define BORDER_R 0x002 | ||
1059 | #define BORDER_U 0x004 | ||
1060 | #define BORDER_D 0x008 | ||
1061 | #define CORNER_UL 0x010 | ||
1062 | #define CORNER_UR 0x020 | ||
1063 | #define CORNER_DL 0x040 | ||
1064 | #define CORNER_DR 0x080 | ||
1065 | #define CURSOR 0x100 | ||
1066 | #define BADFLASH 0x200 | ||
1067 | #define SOLNNEXT 0x400 | ||
1068 | #define COLOUR_SHIFT 11 | ||
1069 | |||
1070 | static void draw_tile(drawing *dr, game_drawstate *ds, | ||
1071 | int x, int y, int tile) | ||
1072 | { | ||
1073 | int colour; | ||
1074 | int tx = COORD(x), ty = COORD(y); | ||
1075 | |||
1076 | colour = tile >> COLOUR_SHIFT; | ||
1077 | if (tile & BADFLASH) | ||
1078 | colour = COL_SEPARATOR; | ||
1079 | else | ||
1080 | colour += COL_1; | ||
1081 | draw_rect(dr, tx, ty, TILESIZE, TILESIZE, colour); | ||
1082 | |||
1083 | if (tile & BORDER_L) | ||
1084 | draw_rect(dr, tx, ty, | ||
1085 | SEP_WIDTH, TILESIZE, COL_SEPARATOR); | ||
1086 | if (tile & BORDER_R) | ||
1087 | draw_rect(dr, tx + TILESIZE - SEP_WIDTH, ty, | ||
1088 | SEP_WIDTH, TILESIZE, COL_SEPARATOR); | ||
1089 | if (tile & BORDER_U) | ||
1090 | draw_rect(dr, tx, ty, | ||
1091 | TILESIZE, SEP_WIDTH, COL_SEPARATOR); | ||
1092 | if (tile & BORDER_D) | ||
1093 | draw_rect(dr, tx, ty + TILESIZE - SEP_WIDTH, | ||
1094 | TILESIZE, SEP_WIDTH, COL_SEPARATOR); | ||
1095 | |||
1096 | if (tile & CORNER_UL) | ||
1097 | draw_rect(dr, tx, ty, | ||
1098 | SEP_WIDTH, SEP_WIDTH, COL_SEPARATOR); | ||
1099 | if (tile & CORNER_UR) | ||
1100 | draw_rect(dr, tx + TILESIZE - SEP_WIDTH, ty, | ||
1101 | SEP_WIDTH, SEP_WIDTH, COL_SEPARATOR); | ||
1102 | if (tile & CORNER_DL) | ||
1103 | draw_rect(dr, tx, ty + TILESIZE - SEP_WIDTH, | ||
1104 | SEP_WIDTH, SEP_WIDTH, COL_SEPARATOR); | ||
1105 | if (tile & CORNER_DR) | ||
1106 | draw_rect(dr, tx + TILESIZE - SEP_WIDTH, ty + TILESIZE - SEP_WIDTH, | ||
1107 | SEP_WIDTH, SEP_WIDTH, COL_SEPARATOR); | ||
1108 | |||
1109 | if (tile & CURSOR) | ||
1110 | draw_rect_outline(dr, tx + CURSOR_INSET, ty + CURSOR_INSET, | ||
1111 | TILESIZE - 1 - CURSOR_INSET * 2, | ||
1112 | TILESIZE - 1 - CURSOR_INSET * 2, | ||
1113 | COL_SEPARATOR); | ||
1114 | |||
1115 | if (tile & SOLNNEXT) { | ||
1116 | draw_circle(dr, tx + TILESIZE/2, ty + TILESIZE/2, TILESIZE/6, | ||
1117 | COL_SEPARATOR, COL_SEPARATOR); | ||
1118 | } | ||
1119 | |||
1120 | draw_update(dr, tx, ty, TILESIZE, TILESIZE); | ||
1121 | } | ||
1122 | |||
1123 | static void game_redraw(drawing *dr, game_drawstate *ds, | ||
1124 | const game_state *oldstate, const game_state *state, | ||
1125 | int dir, const game_ui *ui, | ||
1126 | float animtime, float flashtime) | ||
1127 | { | ||
1128 | int w = state->w, h = state->h, wh = w*h; | ||
1129 | int x, y, flashframe, solnmove; | ||
1130 | char *grid; | ||
1131 | |||
1132 | /* This was entirely cloned from fifteen.c; it should probably be | ||
1133 | * moved into some generic 'draw-recessed-rectangle' utility fn. */ | ||
1134 | if (!ds->started) { | ||
1135 | int coords[10]; | ||
1136 | |||
1137 | draw_rect(dr, 0, 0, | ||
1138 | TILESIZE * w + 2 * BORDER, | ||
1139 | TILESIZE * h + 2 * BORDER, COL_BACKGROUND); | ||
1140 | draw_update(dr, 0, 0, | ||
1141 | TILESIZE * w + 2 * BORDER, | ||
1142 | TILESIZE * h + 2 * BORDER); | ||
1143 | |||
1144 | /* | ||
1145 | * Recessed area containing the whole puzzle. | ||
1146 | */ | ||
1147 | coords[0] = COORD(w) + HIGHLIGHT_WIDTH - 1; | ||
1148 | coords[1] = COORD(h) + HIGHLIGHT_WIDTH - 1; | ||
1149 | coords[2] = COORD(w) + HIGHLIGHT_WIDTH - 1; | ||
1150 | coords[3] = COORD(0) - HIGHLIGHT_WIDTH; | ||
1151 | coords[4] = coords[2] - TILESIZE; | ||
1152 | coords[5] = coords[3] + TILESIZE; | ||
1153 | coords[8] = COORD(0) - HIGHLIGHT_WIDTH; | ||
1154 | coords[9] = COORD(h) + HIGHLIGHT_WIDTH - 1; | ||
1155 | coords[6] = coords[8] + TILESIZE; | ||
1156 | coords[7] = coords[9] - TILESIZE; | ||
1157 | draw_polygon(dr, coords, 5, COL_HIGHLIGHT, COL_HIGHLIGHT); | ||
1158 | |||
1159 | coords[1] = COORD(0) - HIGHLIGHT_WIDTH; | ||
1160 | coords[0] = COORD(0) - HIGHLIGHT_WIDTH; | ||
1161 | draw_polygon(dr, coords, 5, COL_LOWLIGHT, COL_LOWLIGHT); | ||
1162 | |||
1163 | draw_rect(dr, COORD(0) - SEP_WIDTH, COORD(0) - SEP_WIDTH, | ||
1164 | TILESIZE * w + 2 * SEP_WIDTH, TILESIZE * h + 2 * SEP_WIDTH, | ||
1165 | COL_SEPARATOR); | ||
1166 | |||
1167 | ds->started = 1; | ||
1168 | } | ||
1169 | |||
1170 | if (flashtime > 0) { | ||
1171 | float frame = (ui->flash_type == VICTORY ? | ||
1172 | VICTORY_FLASH_FRAME : DEFEAT_FLASH_FRAME); | ||
1173 | flashframe = (int)(flashtime / frame); | ||
1174 | } else { | ||
1175 | flashframe = -1; | ||
1176 | } | ||
1177 | |||
1178 | grid = snewn(wh, char); | ||
1179 | memcpy(grid, state->grid, wh * sizeof(*grid)); | ||
1180 | |||
1181 | if (state->soln && state->solnpos < state->soln->nmoves) { | ||
1182 | int i, *queue; | ||
1183 | |||
1184 | /* | ||
1185 | * Highlight as 'next auto-solver move' every square of the | ||
1186 | * target colour which is adjacent to the currently controlled | ||
1187 | * region. We do this by first enacting the actual move, then | ||
1188 | * flood-filling again in a nonexistent colour, and finally | ||
1189 | * reverting to the original grid anything in the new colour | ||
1190 | * that was part of the original controlled region. Then | ||
1191 | * regions coloured in the dummy colour should be displayed as | ||
1192 | * soln_move with the SOLNNEXT flag. | ||
1193 | */ | ||
1194 | solnmove = state->soln->moves[state->solnpos]; | ||
1195 | |||
1196 | queue = snewn(wh, int); | ||
1197 | fill(w, h, grid, FILLX, FILLY, solnmove, queue); | ||
1198 | fill(w, h, grid, FILLX, FILLY, state->colours, queue); | ||
1199 | sfree(queue); | ||
1200 | |||
1201 | for (i = 0; i < wh; i++) | ||
1202 | if (grid[i] == state->colours && state->grid[i] != solnmove) | ||
1203 | grid[i] = state->grid[i]; | ||
1204 | } else { | ||
1205 | solnmove = 0; /* placate optimiser */ | ||
1206 | } | ||
1207 | |||
1208 | if (flashframe >= 0 && ui->flash_type == VICTORY) { | ||
1209 | /* | ||
1210 | * Modify the display grid by superimposing our rainbow flash | ||
1211 | * on it. | ||
1212 | */ | ||
1213 | for (x = 0; x < w; x++) { | ||
1214 | for (y = 0; y < h; y++) { | ||
1215 | int flashpos = flashframe - (abs(x - FILLX) + abs(y - FILLY)); | ||
1216 | if (flashpos >= 0 && flashpos < state->colours) | ||
1217 | grid[y*w+x] = flashpos; | ||
1218 | } | ||
1219 | } | ||
1220 | } | ||
1221 | |||
1222 | for (x = 0; x < w; x++) { | ||
1223 | for (y = 0; y < h; y++) { | ||
1224 | int pos = y*w+x; | ||
1225 | int tile; | ||
1226 | |||
1227 | if (grid[pos] == state->colours) { | ||
1228 | tile = (solnmove << COLOUR_SHIFT) | SOLNNEXT; | ||
1229 | } else { | ||
1230 | tile = (int)grid[pos] << COLOUR_SHIFT; | ||
1231 | } | ||
1232 | |||
1233 | if (x == 0 || grid[pos-1] != grid[pos]) | ||
1234 | tile |= BORDER_L; | ||
1235 | if (x==w-1 || grid[pos+1] != grid[pos]) | ||
1236 | tile |= BORDER_R; | ||
1237 | if (y == 0 || grid[pos-w] != grid[pos]) | ||
1238 | tile |= BORDER_U; | ||
1239 | if (y==h-1 || grid[pos+w] != grid[pos]) | ||
1240 | tile |= BORDER_D; | ||
1241 | if (x == 0 || y == 0 || grid[pos-w-1] != grid[pos]) | ||
1242 | tile |= CORNER_UL; | ||
1243 | if (x==w-1 || y == 0 || grid[pos-w+1] != grid[pos]) | ||
1244 | tile |= CORNER_UR; | ||
1245 | if (x == 0 || y==h-1 || grid[pos+w-1] != grid[pos]) | ||
1246 | tile |= CORNER_DL; | ||
1247 | if (x==w-1 || y==h-1 || grid[pos+w+1] != grid[pos]) | ||
1248 | tile |= CORNER_DR; | ||
1249 | if (ui->cursor_visible && ui->cx == x && ui->cy == y) | ||
1250 | tile |= CURSOR; | ||
1251 | |||
1252 | if (flashframe >= 0 && ui->flash_type == DEFEAT && flashframe != 1) | ||
1253 | tile |= BADFLASH; | ||
1254 | |||
1255 | if (ds->grid[pos] != tile) { | ||
1256 | draw_tile(dr, ds, x, y, tile); | ||
1257 | ds->grid[pos] = tile; | ||
1258 | } | ||
1259 | } | ||
1260 | } | ||
1261 | |||
1262 | sfree(grid); | ||
1263 | |||
1264 | { | ||
1265 | char status[255]; | ||
1266 | |||
1267 | sprintf(status, "%s%d / %d moves", | ||
1268 | (state->complete && state->moves <= state->movelimit ? | ||
1269 | (state->cheated ? "Auto-solved. " : "COMPLETED! ") : | ||
1270 | state->moves >= state->movelimit ? "FAILED! " : | ||
1271 | state->cheated ? "Auto-solver used. " : | ||
1272 | ""), | ||
1273 | state->moves, | ||
1274 | state->movelimit); | ||
1275 | |||
1276 | status_bar(dr, status); | ||
1277 | } | ||
1278 | } | ||
1279 | |||
1280 | static float game_anim_length(const game_state *oldstate, | ||
1281 | const game_state *newstate, int dir, game_ui *ui) | ||
1282 | { | ||
1283 | return 0.0F; | ||
1284 | } | ||
1285 | |||
1286 | static int game_status(const game_state *state) | ||
1287 | { | ||
1288 | if (state->complete && state->moves <= state->movelimit) { | ||
1289 | return +1; /* victory! */ | ||
1290 | } else if (state->moves >= state->movelimit) { | ||
1291 | return -1; /* defeat */ | ||
1292 | } else { | ||
1293 | return 0; /* still playing */ | ||
1294 | } | ||
1295 | } | ||
1296 | |||
1297 | static float game_flash_length(const game_state *oldstate, | ||
1298 | const game_state *newstate, int dir, game_ui *ui) | ||
1299 | { | ||
1300 | if (dir == +1) { | ||
1301 | int old_status = game_status(oldstate); | ||
1302 | int new_status = game_status(newstate); | ||
1303 | if (old_status != new_status) { | ||
1304 | assert(old_status == 0); | ||
1305 | |||
1306 | if (new_status == +1) { | ||
1307 | int frames = newstate->w + newstate->h + newstate->colours - 2; | ||
1308 | ui->flash_type = VICTORY; | ||
1309 | return VICTORY_FLASH_FRAME * frames; | ||
1310 | } else { | ||
1311 | ui->flash_type = DEFEAT; | ||
1312 | return DEFEAT_FLASH_FRAME * 3; | ||
1313 | } | ||
1314 | } | ||
1315 | } | ||
1316 | return 0.0F; | ||
1317 | } | ||
1318 | |||
1319 | static int game_timing_state(const game_state *state, game_ui *ui) | ||
1320 | { | ||
1321 | return TRUE; | ||
1322 | } | ||
1323 | |||
1324 | static void game_print_size(const game_params *params, float *x, float *y) | ||
1325 | { | ||
1326 | } | ||
1327 | |||
1328 | static void game_print(drawing *dr, const game_state *state, int tilesize) | ||
1329 | { | ||
1330 | } | ||
1331 | |||
1332 | #ifdef COMBINED | ||
1333 | #define thegame flood | ||
1334 | #endif | ||
1335 | |||
1336 | const struct game thegame = { | ||
1337 | "Flood", "games.flood", "flood", | ||
1338 | default_params, | ||
1339 | game_fetch_preset, NULL, | ||
1340 | decode_params, | ||
1341 | encode_params, | ||
1342 | free_params, | ||
1343 | dup_params, | ||
1344 | TRUE, game_configure, custom_params, | ||
1345 | validate_params, | ||
1346 | new_game_desc, | ||
1347 | validate_desc, | ||
1348 | new_game, | ||
1349 | dup_game, | ||
1350 | free_game, | ||
1351 | TRUE, solve_game, | ||
1352 | TRUE, game_can_format_as_text_now, game_text_format, | ||
1353 | new_ui, | ||
1354 | free_ui, | ||
1355 | encode_ui, | ||
1356 | decode_ui, | ||
1357 | game_changed_state, | ||
1358 | interpret_move, | ||
1359 | execute_move, | ||
1360 | PREFERRED_TILESIZE, game_compute_size, game_set_size, | ||
1361 | game_colours, | ||
1362 | game_new_drawstate, | ||
1363 | game_free_drawstate, | ||
1364 | game_redraw, | ||
1365 | game_anim_length, | ||
1366 | game_flash_length, | ||
1367 | game_status, | ||
1368 | FALSE, FALSE, game_print_size, game_print, | ||
1369 | TRUE, /* wants_statusbar */ | ||
1370 | FALSE, game_timing_state, | ||
1371 | 0, /* flags */ | ||
1372 | }; | ||