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.
8 * Possible further work:
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
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.
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,
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. */
73 static game_params *default_params(void)
75 game_params *ret = snew(game_params);
85 struct game_params preset;
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
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"},
104 static int game_fetch_preset(int i, char **name, game_params **params)
108 if (i < 0 || i >= lenof(flood_presets))
111 ret = snew(game_params);
112 *ret = flood_presets[i].preset;
113 *name = dupstr(flood_presets[i].name);
118 static void free_params(game_params *params)
123 static game_params *dup_params(const game_params *params)
125 game_params *ret = snew(game_params);
126 *ret = *params; /* structure copy */
130 static void decode_params(game_params *ret, char const *string)
132 ret->w = ret->h = atoi(string);
133 while (*string && isdigit((unsigned char)*string)) string++;
134 if (*string == 'x') {
136 ret->h = atoi(string);
137 while (*string && isdigit((unsigned char)*string)) string++;
140 if (*string == 'c') {
142 ret->colours = atoi(string);
143 while (string[1] && isdigit((unsigned char)string[1])) string++;
144 } else if (*string == 'm') {
146 ret->leniency = atoi(string);
147 while (string[1] && isdigit((unsigned char)string[1])) string++;
153 static char *encode_params(const game_params *params, int full)
156 sprintf(buf, "%dx%d", params->w, params->h);
158 sprintf(buf + strlen(buf), "c%dm%d",
159 params->colours, params->leniency);
163 static config_item *game_configure(const game_params *params)
168 ret = snewn(5, config_item);
170 ret[0].name = "Width";
171 ret[0].type = C_STRING;
172 sprintf(buf, "%d", params->w);
173 ret[0].sval = dupstr(buf);
176 ret[1].name = "Height";
177 ret[1].type = C_STRING;
178 sprintf(buf, "%d", params->h);
179 ret[1].sval = dupstr(buf);
182 ret[2].name = "Colours";
183 ret[2].type = C_STRING;
184 sprintf(buf, "%d", params->colours);
185 ret[2].sval = dupstr(buf);
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);
202 static game_params *custom_params(const config_item *cfg)
204 game_params *ret = snew(game_params);
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);
214 static char *validate_params(const game_params *params, int full)
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";
227 * Bodge to permit varying the recursion depth for testing purposes.
229 To test two Floods against each other:
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
233 and then run gnuplot and plot "z".
236 static int rdepth = 0;
237 #define RECURSION_DEPTH (rdepth)
238 void check_recursion_depth(void)
241 const char *depthstr = getenv("FLOOD_DEPTH");
242 rdepth = depthstr ? atoi(depthstr) : 1;
243 rdepth = rdepth > 0 ? rdepth : 1;
248 * Last time I empirically checked this, depth 3 was a noticeable
249 * improvement on 2, but 4 only negligibly better than 3.
251 #define RECURSION_DEPTH 3
252 #define check_recursion_depth() (void)0
255 struct solver_scratch {
262 static struct solver_scratch *new_scratch(int w, int 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);
276 static void free_scratch(struct solver_scratch *scratch)
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);
288 /* Diagnostic routines you can uncomment if you need them */
289 void dump_grid(int w, int h, const char *grid, const char *titlefmt, ...)
294 va_start(ap, titlefmt);
295 vprintf(titlefmt, ap);
301 for (y = 0; y < h; y++) {
303 for (x = 0; x < w; x++) {
304 printf("%1x", grid[y*w+x]);
310 void dump_dist(int w, int h, const int *dists, const char *titlefmt, ...)
315 va_start(ap, titlefmt);
316 vprintf(titlefmt, ap);
320 printf("Distances:\n");
322 for (y = 0; y < h; y++) {
324 for (x = 0; x < w; x++) {
325 printf("%3d", dists[y*w+x]);
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).
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)
342 int i, qcurr, qhead, qtail, qnext, currdist, remaining;
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;
357 if (qtail == qhead) {
362 qcurr ^= 1; /* switch queues */
367 printf("switch queue, new dist %d, queue %d\n", currdist, qhead);
369 } else if (remaining == 0 && qnext == 0) {
372 int pos = scratch->queue[qcurr][qtail++];
376 printf("checking neighbours of %d,%d\n", x, y);
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) {
385 printf("trying %d,%d: colours %d-%d dist %d\n", x1, y1,
386 grid[pos], grid[pos1], scratch->dist[pos]);
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))) {
394 printf("marking %d,%d dist %d\n", x1, y1, currdist);
396 scratch->queue[qcurr][qhead++] = pos1;
397 scratch->queue[qcurr^1][qnext++] = pos1;
398 scratch->dist[pos1] = currdist;
413 * Enact a flood-fill move on a grid.
415 static void fill(int w, int h, char *grid, int x0, int y0, char newcolour,
421 oldcolour = grid[y0*w+x0];
422 assert(oldcolour != newcolour);
423 grid[y0*w+x0] = newcolour;
428 while (qtail < qhead) {
429 int pos = queue[qtail++];
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) {
438 if (grid[pos1] == oldcolour) {
439 grid[pos1] = newcolour;
440 queue[qhead++] = pos1;
448 * Detect a completed grid.
450 static int completed(int w, int h, char *grid)
455 for (i = 1; i < wh; i++)
456 if (grid[i] != grid[0])
463 * Try out every possible move on a grid, and choose whichever one
464 * reduced the result of search() by the most.
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)
472 int dist, number, control, bestdist, bestnumber, bestcontrol;
475 assert(0 <= depth && depth < RECURSION_DEPTH);
476 tmpgrid = scratch->rgrids + depth*wh;
484 dump_grid(w, h, grid, "before choosemove_recurse %d", depth);
486 for (move = 0; move < maxmove; move++) {
487 if (grid[y0*w+x0] == move)
489 memcpy(tmpgrid, grid, wh * sizeof(*grid));
490 fill(w, h, tmpgrid, x0, y0, move, scratch->queue[0]);
491 if (completed(w, h, tmpgrid)) {
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.
499 *rbestnumber = depth;
503 if (depth < RECURSION_DEPTH-1) {
504 choosemove_recurse(w, h, tmpgrid, x0, y0, maxmove, scratch,
505 depth+1, &dist, &number, &control);
508 dump_grid(w, h, tmpgrid, "after move %d at depth %d",
511 search(w, h, tmpgrid, x0, y0, scratch, &dist, &number, &control);
513 dump_dist(w, h, scratch->dist, "after move %d at depth %d",
515 printf("move %d at depth %d: %d at %d\n",
516 depth, move, number, dist);
519 if (dist < bestdist ||
521 (number < bestnumber ||
522 (number == bestnumber &&
523 (control > bestcontrol))))) {
526 bestcontrol = control;
531 printf("best at depth %d was %d (%d at %d, %d controlled)\n",
532 depth, bestmove, bestnumber, bestdist, bestcontrol);
535 *rbestdist = bestdist;
536 *rbestnumber = bestnumber;
537 *rbestcontrol = bestcontrol;
540 static char choosemove(int w, int h, char *grid, int x0, int y0,
541 int maxmove, struct solver_scratch *scratch)
543 int tmp0, tmp1, tmp2;
544 return choosemove_recurse(w, h, grid, x0, y0, maxmove, scratch,
545 0, &tmp0, &tmp1, &tmp2);
548 static char *new_game_desc(const game_params *params, random_state *rs,
549 char **aux, int interactive)
551 int w = params->w, h = params->h, wh = w*h;
554 struct solver_scratch *scratch;
556 scratch = new_scratch(w, h);
559 * Invent a random grid.
561 for (i = 0; i < wh; i++)
562 scratch->grid[i] = random_upto(rs, params->colours);
565 * Run the solver, and count how many moves it uses.
567 memcpy(scratch->grid2, scratch->grid, wh * sizeof(*scratch->grid2));
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]);
578 * Adjust for difficulty.
580 moves += params->leniency;
583 * Encode the game id.
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;
591 sprintf(desc+i, ",%d", moves);
593 free_scratch(scratch);
598 static char *validate_desc(const game_params *params, const char *desc)
600 int w = params->w, h = params->h, wh = w*h;
602 for (i = 0; i < wh; i++) {
605 return "Not enough data in grid description";
606 if (c >= '0' && c <= '9')
608 else if (c >= 'A' && c <= 'Z')
611 return "Bad character in grid description";
612 if ((unsigned)c >= params->colours)
613 return "Colour out of range in grid description";
616 return "Expected ',' after grid description";
618 if (desc[strspn(desc, "0123456789")])
619 return "Badly formatted move limit after grid description";
623 static game_state *new_game(midend *me, const game_params *params,
626 int w = params->w, h = params->h, wh = w*h;
627 game_state *state = snew(game_state);
632 state->colours = params->colours;
634 state->grid = snewn(wh, char);
636 for (i = 0; i < wh; i++) {
639 if (c >= '0' && c <= '9')
641 else if (c >= 'A' && c <= 'Z')
644 assert(!"bad colour");
647 assert(*desc == ',');
650 state->movelimit = atoi(desc);
651 state->complete = FALSE;
652 state->cheated = FALSE;
659 static game_state *dup_game(const game_state *state)
661 game_state *ret = snew(game_state);
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));
672 ret->cheated = state->cheated;
673 ret->soln = state->soln;
675 ret->soln->refcount++;
676 ret->solnpos = state->solnpos;
681 static void free_game(game_state *state)
683 if (state->soln && --state->soln->refcount == 0) {
684 sfree(state->soln->moves);
691 static char *solve_game(const game_state *state, const game_state *currstate,
692 const char *aux, char **error)
694 int w = state->w, h = state->h, wh = w*h;
695 char *moves, *ret, *p;
698 struct solver_scratch *scratch;
700 if (currstate->complete)
704 * Find the best solution our solver can give.
706 moves = snewn(wh, char); /* sure to be enough */
708 scratch = new_scratch(w, h);
709 memcpy(scratch->grid2, currstate->grid, wh * sizeof(*scratch->grid2));
710 check_recursion_depth();
711 while (!completed(w, h, scratch->grid2)) {
712 char move = choosemove(w, h, scratch->grid2, FILLX, FILLY,
713 currstate->colours, scratch);
714 fill(w, h, scratch->grid2, FILLX, FILLY, move, scratch->queue[0]);
716 moves[nmoves++] = move;
718 free_scratch(scratch);
721 * Encode it as a move string.
723 len = 1; /* trailing NUL */
724 for (i = 0; i < nmoves; i++)
725 len += sprintf(buf, ",%d", moves[i]);
726 ret = snewn(len, char);
728 for (i = 0; i < nmoves; i++)
729 p += sprintf(p, "%c%d", (i==0 ? 'S' : ','), moves[i]);
730 assert(p - ret == len - 1);
736 static int game_can_format_as_text_now(const game_params *params)
741 static char *game_text_format(const game_state *state)
743 int w = state->w, h = state->h;
747 len = h * (w+1); /* +1 for newline after each row */
748 ret = snewn(len+1, char); /* and +1 for terminating \0 */
751 for (y = 0; y < h; y++) {
752 for (x = 0; x < w; x++) {
753 char colour = state->grid[y*w+x];
754 char textcolour = (colour > 9 ? 'A' : '0') + colour;
760 assert(p - ret == len);
769 enum { VICTORY, DEFEAT } flash_type;
772 static game_ui *new_ui(const game_state *state)
774 struct game_ui *ui = snew(struct game_ui);
775 ui->cursor_visible = FALSE;
781 static void free_ui(game_ui *ui)
786 static char *encode_ui(const game_ui *ui)
791 static void decode_ui(game_ui *ui, const char *encoding)
795 static void game_changed_state(game_ui *ui, const game_state *oldstate,
796 const game_state *newstate)
800 struct game_drawstate {
806 #define TILESIZE (ds->tilesize)
807 #define PREFERRED_TILESIZE 32
808 #define BORDER (TILESIZE / 2)
809 #define SEP_WIDTH (TILESIZE / 32)
810 #define CURSOR_INSET (TILESIZE / 8)
811 #define HIGHLIGHT_WIDTH (TILESIZE / 10)
812 #define COORD(x) ( (x) * TILESIZE + BORDER )
813 #define FROMCOORD(x) ( ((x) - BORDER + TILESIZE) / TILESIZE - 1 )
814 #define VICTORY_FLASH_FRAME 0.03F
815 #define DEFEAT_FLASH_FRAME 0.10F
817 static char *interpret_move(const game_state *state, game_ui *ui,
818 const game_drawstate *ds,
819 int x, int y, int button)
821 int w = state->w, h = state->h;
822 int tx = -1, ty = -1, move = -1;
824 if (button == LEFT_BUTTON) {
827 ui->cursor_visible = FALSE;
828 } else if (button == CURSOR_LEFT && ui->cx > 0) {
830 ui->cursor_visible = TRUE;
832 } else if (button == CURSOR_RIGHT && ui->cx+1 < w) {
834 ui->cursor_visible = TRUE;
836 } else if (button == CURSOR_UP && ui->cy > 0) {
838 ui->cursor_visible = TRUE;
840 } else if (button == CURSOR_DOWN && ui->cy+1 < h) {
842 ui->cursor_visible = TRUE;
844 } else if (button == CURSOR_SELECT) {
847 } else if (button == CURSOR_SELECT2 &&
848 state->soln && state->solnpos < state->soln->nmoves) {
849 move = state->soln->moves[state->solnpos];
854 if (tx >= 0 && tx < w && ty >= 0 && ty < h &&
855 state->grid[0] != state->grid[ty*w+tx])
856 move = state->grid[ty*w+tx];
858 if (move >= 0 && !state->complete) {
860 sprintf(buf, "M%d", move);
867 static game_state *execute_move(const game_state *state, const char *move)
872 if (move[0] == 'M' &&
873 sscanf(move+1, "%d", &c) == 1 &&
876 int *queue = snewn(state->w * state->h, int);
877 ret = dup_game(state);
878 fill(ret->w, ret->h, ret->grid, FILLX, FILLY, c, queue);
880 ret->complete = completed(ret->w, ret->h, ret->grid);
884 * If this move is the correct next one in the stored
885 * solution path, advance solnpos.
887 if (c == ret->soln->moves[ret->solnpos] &&
888 ret->solnpos+1 < ret->soln->nmoves) {
892 * Otherwise, the user has strayed from the path or
893 * else the path has come to an end; either way, the
894 * path is no longer valid.
896 ret->soln->refcount--;
897 assert(ret->soln->refcount > 0);/* `state' at least still exists */
905 } else if (*move == 'S') {
911 * This is a solve move, so we don't actually _change_ the
912 * grid but merely set up a stored solution path.
918 for (p = move; *p; p++) {
923 sol->moves = snewn(sol->nmoves, char);
924 for (i = 0, p = move; i < sol->nmoves; i++) {
926 sol->moves[i] = atoi(p);
927 p += strspn(p, "0123456789");
934 ret = dup_game(state);
936 if (ret->soln && --ret->soln->refcount == 0) {
937 sfree(ret->soln->moves);
949 /* ----------------------------------------------------------------------
953 static void game_compute_size(const game_params *params, int tilesize,
956 /* Ick: fake up `ds->tilesize' for macro expansion purposes */
957 struct { int tilesize; } ads, *ds = &ads;
958 ads.tilesize = tilesize;
960 *x = BORDER * 2 + TILESIZE * params->w;
961 *y = BORDER * 2 + TILESIZE * params->h;
964 static void game_set_size(drawing *dr, game_drawstate *ds,
965 const game_params *params, int tilesize)
967 ds->tilesize = tilesize;
970 static float *game_colours(frontend *fe, int *ncolours)
972 float *ret = snewn(3 * NCOLOURS, float);
974 game_mkhighlight(fe, ret, COL_BACKGROUND, COL_HIGHLIGHT, COL_LOWLIGHT);
976 ret[COL_SEPARATOR * 3 + 0] = 0.0F;
977 ret[COL_SEPARATOR * 3 + 1] = 0.0F;
978 ret[COL_SEPARATOR * 3 + 2] = 0.0F;
981 ret[COL_1 * 3 + 0] = 1.0F;
982 ret[COL_1 * 3 + 1] = 0.0F;
983 ret[COL_1 * 3 + 2] = 0.0F;
986 ret[COL_2 * 3 + 0] = 1.0F;
987 ret[COL_2 * 3 + 1] = 1.0F;
988 ret[COL_2 * 3 + 2] = 0.0F;
991 ret[COL_3 * 3 + 0] = 0.0F;
992 ret[COL_3 * 3 + 1] = 1.0F;
993 ret[COL_3 * 3 + 2] = 0.0F;
996 ret[COL_4 * 3 + 0] = 0.2F;
997 ret[COL_4 * 3 + 1] = 0.3F;
998 ret[COL_4 * 3 + 2] = 1.0F;
1001 ret[COL_5 * 3 + 0] = 1.0F;
1002 ret[COL_5 * 3 + 1] = 0.5F;
1003 ret[COL_5 * 3 + 2] = 0.0F;
1006 ret[COL_6 * 3 + 0] = 0.5F;
1007 ret[COL_6 * 3 + 1] = 0.0F;
1008 ret[COL_6 * 3 + 2] = 0.7F;
1011 ret[COL_7 * 3 + 0] = 0.5F;
1012 ret[COL_7 * 3 + 1] = 0.3F;
1013 ret[COL_7 * 3 + 2] = 0.3F;
1016 ret[COL_8 * 3 + 0] = 0.4F;
1017 ret[COL_8 * 3 + 1] = 0.8F;
1018 ret[COL_8 * 3 + 2] = 1.0F;
1021 ret[COL_9 * 3 + 0] = 0.7F;
1022 ret[COL_9 * 3 + 1] = 1.0F;
1023 ret[COL_9 * 3 + 2] = 0.7F;
1026 ret[COL_10 * 3 + 0] = 1.0F;
1027 ret[COL_10 * 3 + 1] = 0.6F;
1028 ret[COL_10 * 3 + 2] = 1.0F;
1030 *ncolours = NCOLOURS;
1034 static game_drawstate *game_new_drawstate(drawing *dr, const game_state *state)
1036 struct game_drawstate *ds = snew(struct game_drawstate);
1037 int w = state->w, h = state->h, wh = w*h;
1040 ds->started = FALSE;
1042 ds->grid = snewn(wh, int);
1043 for (i = 0; i < wh; i++)
1049 static void game_free_drawstate(drawing *dr, game_drawstate *ds)
1055 #define BORDER_L 0x001
1056 #define BORDER_R 0x002
1057 #define BORDER_U 0x004
1058 #define BORDER_D 0x008
1059 #define CORNER_UL 0x010
1060 #define CORNER_UR 0x020
1061 #define CORNER_DL 0x040
1062 #define CORNER_DR 0x080
1063 #define CURSOR 0x100
1064 #define BADFLASH 0x200
1065 #define SOLNNEXT 0x400
1066 #define COLOUR_SHIFT 11
1068 static void draw_tile(drawing *dr, game_drawstate *ds,
1069 int x, int y, int tile)
1072 int tx = COORD(x), ty = COORD(y);
1074 colour = tile >> COLOUR_SHIFT;
1075 if (tile & BADFLASH)
1076 colour = COL_SEPARATOR;
1079 draw_rect(dr, tx, ty, TILESIZE, TILESIZE, colour);
1081 if (tile & BORDER_L)
1082 draw_rect(dr, tx, ty,
1083 SEP_WIDTH, TILESIZE, COL_SEPARATOR);
1084 if (tile & BORDER_R)
1085 draw_rect(dr, tx + TILESIZE - SEP_WIDTH, ty,
1086 SEP_WIDTH, TILESIZE, COL_SEPARATOR);
1087 if (tile & BORDER_U)
1088 draw_rect(dr, tx, ty,
1089 TILESIZE, SEP_WIDTH, COL_SEPARATOR);
1090 if (tile & BORDER_D)
1091 draw_rect(dr, tx, ty + TILESIZE - SEP_WIDTH,
1092 TILESIZE, SEP_WIDTH, COL_SEPARATOR);
1094 if (tile & CORNER_UL)
1095 draw_rect(dr, tx, ty,
1096 SEP_WIDTH, SEP_WIDTH, COL_SEPARATOR);
1097 if (tile & CORNER_UR)
1098 draw_rect(dr, tx + TILESIZE - SEP_WIDTH, ty,
1099 SEP_WIDTH, SEP_WIDTH, COL_SEPARATOR);
1100 if (tile & CORNER_DL)
1101 draw_rect(dr, tx, ty + TILESIZE - SEP_WIDTH,
1102 SEP_WIDTH, SEP_WIDTH, COL_SEPARATOR);
1103 if (tile & CORNER_DR)
1104 draw_rect(dr, tx + TILESIZE - SEP_WIDTH, ty + TILESIZE - SEP_WIDTH,
1105 SEP_WIDTH, SEP_WIDTH, COL_SEPARATOR);
1108 draw_rect_outline(dr, tx + CURSOR_INSET, ty + CURSOR_INSET,
1109 TILESIZE - 1 - CURSOR_INSET * 2,
1110 TILESIZE - 1 - CURSOR_INSET * 2,
1113 if (tile & SOLNNEXT) {
1114 draw_circle(dr, tx + TILESIZE/2, ty + TILESIZE/2, TILESIZE/6,
1115 COL_SEPARATOR, COL_SEPARATOR);
1118 draw_update(dr, tx, ty, TILESIZE, TILESIZE);
1121 static void game_redraw(drawing *dr, game_drawstate *ds,
1122 const game_state *oldstate, const game_state *state,
1123 int dir, const game_ui *ui,
1124 float animtime, float flashtime)
1126 int w = state->w, h = state->h, wh = w*h;
1127 int x, y, flashframe, solnmove;
1130 /* This was entirely cloned from fifteen.c; it should probably be
1131 * moved into some generic 'draw-recessed-rectangle' utility fn. */
1136 TILESIZE * w + 2 * BORDER,
1137 TILESIZE * h + 2 * BORDER, COL_BACKGROUND);
1138 draw_update(dr, 0, 0,
1139 TILESIZE * w + 2 * BORDER,
1140 TILESIZE * h + 2 * BORDER);
1143 * Recessed area containing the whole puzzle.
1145 coords[0] = COORD(w) + HIGHLIGHT_WIDTH - 1;
1146 coords[1] = COORD(h) + HIGHLIGHT_WIDTH - 1;
1147 coords[2] = COORD(w) + HIGHLIGHT_WIDTH - 1;
1148 coords[3] = COORD(0) - HIGHLIGHT_WIDTH;
1149 coords[4] = coords[2] - TILESIZE;
1150 coords[5] = coords[3] + TILESIZE;
1151 coords[8] = COORD(0) - HIGHLIGHT_WIDTH;
1152 coords[9] = COORD(h) + HIGHLIGHT_WIDTH - 1;
1153 coords[6] = coords[8] + TILESIZE;
1154 coords[7] = coords[9] - TILESIZE;
1155 draw_polygon(dr, coords, 5, COL_HIGHLIGHT, COL_HIGHLIGHT);
1157 coords[1] = COORD(0) - HIGHLIGHT_WIDTH;
1158 coords[0] = COORD(0) - HIGHLIGHT_WIDTH;
1159 draw_polygon(dr, coords, 5, COL_LOWLIGHT, COL_LOWLIGHT);
1161 draw_rect(dr, COORD(0) - SEP_WIDTH, COORD(0) - SEP_WIDTH,
1162 TILESIZE * w + 2 * SEP_WIDTH, TILESIZE * h + 2 * SEP_WIDTH,
1168 if (flashtime > 0) {
1169 float frame = (ui->flash_type == VICTORY ?
1170 VICTORY_FLASH_FRAME : DEFEAT_FLASH_FRAME);
1171 flashframe = (int)(flashtime / frame);
1176 grid = snewn(wh, char);
1177 memcpy(grid, state->grid, wh * sizeof(*grid));
1179 if (state->soln && state->solnpos < state->soln->nmoves) {
1183 * Highlight as 'next auto-solver move' every square of the
1184 * target colour which is adjacent to the currently controlled
1185 * region. We do this by first enacting the actual move, then
1186 * flood-filling again in a nonexistent colour, and finally
1187 * reverting to the original grid anything in the new colour
1188 * that was part of the original controlled region. Then
1189 * regions coloured in the dummy colour should be displayed as
1190 * soln_move with the SOLNNEXT flag.
1192 solnmove = state->soln->moves[state->solnpos];
1194 queue = snewn(wh, int);
1195 fill(w, h, grid, FILLX, FILLY, solnmove, queue);
1196 fill(w, h, grid, FILLX, FILLY, state->colours, queue);
1199 for (i = 0; i < wh; i++)
1200 if (grid[i] == state->colours && state->grid[i] != solnmove)
1201 grid[i] = state->grid[i];
1203 solnmove = 0; /* placate optimiser */
1206 if (flashframe >= 0 && ui->flash_type == VICTORY) {
1208 * Modify the display grid by superimposing our rainbow flash
1211 for (x = 0; x < w; x++) {
1212 for (y = 0; y < h; y++) {
1213 int flashpos = flashframe - (abs(x - FILLX) + abs(y - FILLY));
1214 if (flashpos >= 0 && flashpos < state->colours)
1215 grid[y*w+x] = flashpos;
1220 for (x = 0; x < w; x++) {
1221 for (y = 0; y < h; y++) {
1225 if (grid[pos] == state->colours) {
1226 tile = (solnmove << COLOUR_SHIFT) | SOLNNEXT;
1228 tile = (int)grid[pos] << COLOUR_SHIFT;
1231 if (x == 0 || grid[pos-1] != grid[pos])
1233 if (x==w-1 || grid[pos+1] != grid[pos])
1235 if (y == 0 || grid[pos-w] != grid[pos])
1237 if (y==h-1 || grid[pos+w] != grid[pos])
1239 if (x == 0 || y == 0 || grid[pos-w-1] != grid[pos])
1241 if (x==w-1 || y == 0 || grid[pos-w+1] != grid[pos])
1243 if (x == 0 || y==h-1 || grid[pos+w-1] != grid[pos])
1245 if (x==w-1 || y==h-1 || grid[pos+w+1] != grid[pos])
1247 if (ui->cursor_visible && ui->cx == x && ui->cy == y)
1250 if (flashframe >= 0 && ui->flash_type == DEFEAT && flashframe != 1)
1253 if (ds->grid[pos] != tile) {
1254 draw_tile(dr, ds, x, y, tile);
1255 ds->grid[pos] = tile;
1265 sprintf(status, "%s%d / %d moves",
1266 (state->complete && state->moves <= state->movelimit ?
1267 (state->cheated ? "Auto-solved. " : "COMPLETED! ") :
1268 state->moves >= state->movelimit ? "FAILED! " :
1269 state->cheated ? "Auto-solver used. " :
1274 status_bar(dr, status);
1278 static float game_anim_length(const game_state *oldstate,
1279 const game_state *newstate, int dir, game_ui *ui)
1284 static int game_status(const game_state *state)
1286 if (state->complete && state->moves <= state->movelimit) {
1287 return +1; /* victory! */
1288 } else if (state->moves >= state->movelimit) {
1289 return -1; /* defeat */
1291 return 0; /* still playing */
1295 static float game_flash_length(const game_state *oldstate,
1296 const game_state *newstate, int dir, game_ui *ui)
1299 int old_status = game_status(oldstate);
1300 int new_status = game_status(newstate);
1301 if (old_status != new_status) {
1302 assert(old_status == 0);
1304 if (new_status == +1) {
1305 int frames = newstate->w + newstate->h + newstate->colours - 2;
1306 ui->flash_type = VICTORY;
1307 return VICTORY_FLASH_FRAME * frames;
1309 ui->flash_type = DEFEAT;
1310 return DEFEAT_FLASH_FRAME * 3;
1317 static int game_timing_state(const game_state *state, game_ui *ui)
1322 static void game_print_size(const game_params *params, float *x, float *y)
1326 static void game_print(drawing *dr, const game_state *state, int tilesize)
1331 #define thegame flood
1334 const struct game thegame = {
1335 "Flood", "games.flood", "flood",
1342 TRUE, game_configure, custom_params,
1350 TRUE, game_can_format_as_text_now, game_text_format,
1358 PREFERRED_TILESIZE, game_compute_size, game_set_size,
1361 game_free_drawstate,
1366 FALSE, FALSE, game_print_size, game_print,
1367 TRUE, /* wants_statusbar */
1368 FALSE, game_timing_state,