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