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].u.string.sval = dupstr(buf);
175 ret[1].name = "Height";
176 ret[1].type = C_STRING;
177 sprintf(buf, "%d", params->h);
178 ret[1].u.string.sval = dupstr(buf);
180 ret[2].name = "Colours";
181 ret[2].type = C_STRING;
182 sprintf(buf, "%d", params->colours);
183 ret[2].u.string.sval = dupstr(buf);
185 ret[3].name = "Extra moves permitted";
186 ret[3].type = C_STRING;
187 sprintf(buf, "%d", params->leniency);
188 ret[3].u.string.sval = dupstr(buf);
196 static game_params *custom_params(const config_item *cfg)
198 game_params *ret = snew(game_params);
200 ret->w = atoi(cfg[0].u.string.sval);
201 ret->h = atoi(cfg[1].u.string.sval);
202 ret->colours = atoi(cfg[2].u.string.sval);
203 ret->leniency = atoi(cfg[3].u.string.sval);
208 static char *validate_params(const game_params *params, int full)
210 if (params->w < 2 && params->h < 2)
211 return "Grid must contain at least two squares";
212 if (params->colours < 3 || params->colours > 10)
213 return "Must have between 3 and 10 colours";
214 if (params->leniency < 0)
215 return "Leniency must be non-negative";
221 * Bodge to permit varying the recursion depth for testing purposes.
223 To test two Floods against each other:
225 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
227 and then run gnuplot and plot "z".
230 static int rdepth = 0;
231 #define RECURSION_DEPTH (rdepth)
232 void check_recursion_depth(void)
235 const char *depthstr = getenv("FLOOD_DEPTH");
236 rdepth = depthstr ? atoi(depthstr) : 1;
237 rdepth = rdepth > 0 ? rdepth : 1;
242 * Last time I empirically checked this, depth 3 was a noticeable
243 * improvement on 2, but 4 only negligibly better than 3.
245 #define RECURSION_DEPTH 3
246 #define check_recursion_depth() (void)0
249 struct solver_scratch {
256 static struct solver_scratch *new_scratch(int w, int h)
259 struct solver_scratch *scratch = snew(struct solver_scratch);
260 check_recursion_depth();
261 scratch->queue[0] = snewn(wh, int);
262 scratch->queue[1] = snewn(wh, int);
263 scratch->dist = snewn(wh, int);
264 scratch->grid = snewn(wh, char);
265 scratch->grid2 = snewn(wh, char);
266 scratch->rgrids = snewn(wh * RECURSION_DEPTH, char);
270 static void free_scratch(struct solver_scratch *scratch)
272 sfree(scratch->queue[0]);
273 sfree(scratch->queue[1]);
274 sfree(scratch->dist);
275 sfree(scratch->grid);
276 sfree(scratch->grid2);
277 sfree(scratch->rgrids);
282 /* Diagnostic routines you can uncomment if you need them */
283 void dump_grid(int w, int h, const char *grid, const char *titlefmt, ...)
288 va_start(ap, titlefmt);
289 vprintf(titlefmt, ap);
295 for (y = 0; y < h; y++) {
297 for (x = 0; x < w; x++) {
298 printf("%1x", grid[y*w+x]);
304 void dump_dist(int w, int h, const int *dists, const char *titlefmt, ...)
309 va_start(ap, titlefmt);
310 vprintf(titlefmt, ap);
314 printf("Distances:\n");
316 for (y = 0; y < h; y++) {
318 for (x = 0; x < w; x++) {
319 printf("%3d", dists[y*w+x]);
327 * Search a grid to find the most distant square(s). Return their
328 * distance and the number of them, and also the number of squares in
329 * the current controlled set (i.e. at distance zero).
331 static void search(int w, int h, char *grid, int x0, int y0,
332 struct solver_scratch *scratch,
333 int *rdist, int *rnumber, int *rcontrol)
336 int i, qcurr, qhead, qtail, qnext, currdist, remaining;
338 for (i = 0; i < wh; i++)
339 scratch->dist[i] = -1;
340 scratch->queue[0][0] = y0*w+x0;
341 scratch->queue[1][0] = y0*w+x0;
342 scratch->dist[y0*w+x0] = 0;
351 if (qtail == qhead) {
356 qcurr ^= 1; /* switch queues */
361 printf("switch queue, new dist %d, queue %d\n", currdist, qhead);
363 } else if (remaining == 0 && qnext == 0) {
366 int pos = scratch->queue[qcurr][qtail++];
370 printf("checking neighbours of %d,%d\n", x, y);
373 for (dir = 0; dir < 4; dir++) {
374 int y1 = y + (dir == 1 ? 1 : dir == 3 ? -1 : 0);
375 int x1 = x + (dir == 0 ? 1 : dir == 2 ? -1 : 0);
376 if (0 <= x1 && x1 < w && 0 <= y1 && y1 < h) {
379 printf("trying %d,%d: colours %d-%d dist %d\n", x1, y1,
380 grid[pos], grid[pos1], scratch->dist[pos]);
382 if (scratch->dist[pos1] == -1 &&
383 ((grid[pos1] == grid[pos] &&
384 scratch->dist[pos] == currdist) ||
385 (grid[pos1] != grid[pos] &&
386 scratch->dist[pos] == currdist - 1))) {
388 printf("marking %d,%d dist %d\n", x1, y1, currdist);
390 scratch->queue[qcurr][qhead++] = pos1;
391 scratch->queue[qcurr^1][qnext++] = pos1;
392 scratch->dist[pos1] = currdist;
407 * Enact a flood-fill move on a grid.
409 static void fill(int w, int h, char *grid, int x0, int y0, char newcolour,
415 oldcolour = grid[y0*w+x0];
416 assert(oldcolour != newcolour);
417 grid[y0*w+x0] = newcolour;
422 while (qtail < qhead) {
423 int pos = queue[qtail++];
427 for (dir = 0; dir < 4; dir++) {
428 int y1 = y + (dir == 1 ? 1 : dir == 3 ? -1 : 0);
429 int x1 = x + (dir == 0 ? 1 : dir == 2 ? -1 : 0);
430 if (0 <= x1 && x1 < w && 0 <= y1 && y1 < h) {
432 if (grid[pos1] == oldcolour) {
433 grid[pos1] = newcolour;
434 queue[qhead++] = pos1;
442 * Detect a completed grid.
444 static int completed(int w, int h, char *grid)
449 for (i = 1; i < wh; i++)
450 if (grid[i] != grid[0])
457 * Try out every possible move on a grid, and choose whichever one
458 * reduced the result of search() by the most.
460 static char choosemove_recurse(int w, int h, char *grid, int x0, int y0,
461 int maxmove, struct solver_scratch *scratch,
462 int depth, int *rbestdist, int *rbestnumber, int *rbestcontrol)
466 int dist, number, control, bestdist, bestnumber, bestcontrol;
469 assert(0 <= depth && depth < RECURSION_DEPTH);
470 tmpgrid = scratch->rgrids + depth*wh;
478 dump_grid(w, h, grid, "before choosemove_recurse %d", depth);
480 for (move = 0; move < maxmove; move++) {
481 if (grid[y0*w+x0] == move)
483 memcpy(tmpgrid, grid, wh * sizeof(*grid));
484 fill(w, h, tmpgrid, x0, y0, move, scratch->queue[0]);
485 if (completed(w, h, tmpgrid)) {
487 * A move that wins is immediately the best, so stop
488 * searching. Record what depth of recursion that happened
489 * at, so that higher levels will choose a move that gets
490 * to a winning position sooner.
493 *rbestnumber = depth;
497 if (depth < RECURSION_DEPTH-1) {
498 choosemove_recurse(w, h, tmpgrid, x0, y0, maxmove, scratch,
499 depth+1, &dist, &number, &control);
502 dump_grid(w, h, tmpgrid, "after move %d at depth %d",
505 search(w, h, tmpgrid, x0, y0, scratch, &dist, &number, &control);
507 dump_dist(w, h, scratch->dist, "after move %d at depth %d",
509 printf("move %d at depth %d: %d at %d\n",
510 depth, move, number, dist);
513 if (dist < bestdist ||
515 (number < bestnumber ||
516 (number == bestnumber &&
517 (control > bestcontrol))))) {
520 bestcontrol = control;
525 printf("best at depth %d was %d (%d at %d, %d controlled)\n",
526 depth, bestmove, bestnumber, bestdist, bestcontrol);
529 *rbestdist = bestdist;
530 *rbestnumber = bestnumber;
531 *rbestcontrol = bestcontrol;
534 static char choosemove(int w, int h, char *grid, int x0, int y0,
535 int maxmove, struct solver_scratch *scratch)
537 int tmp0, tmp1, tmp2;
538 return choosemove_recurse(w, h, grid, x0, y0, maxmove, scratch,
539 0, &tmp0, &tmp1, &tmp2);
542 static char *new_game_desc(const game_params *params, random_state *rs,
543 char **aux, int interactive)
545 int w = params->w, h = params->h, wh = w*h;
548 struct solver_scratch *scratch;
550 scratch = new_scratch(w, h);
553 * Invent a random grid.
555 for (i = 0; i < wh; i++)
556 scratch->grid[i] = random_upto(rs, params->colours);
559 * Run the solver, and count how many moves it uses.
561 memcpy(scratch->grid2, scratch->grid, wh * sizeof(*scratch->grid2));
563 check_recursion_depth();
564 while (!completed(w, h, scratch->grid2)) {
565 char move = choosemove(w, h, scratch->grid2, FILLX, FILLY,
566 params->colours, scratch);
567 fill(w, h, scratch->grid2, FILLX, FILLY, move, scratch->queue[0]);
572 * Adjust for difficulty.
574 moves += params->leniency;
577 * Encode the game id.
579 desc = snewn(wh + 40, char);
580 for (i = 0; i < wh; i++) {
581 char colour = scratch->grid[i];
582 char textcolour = (colour > 9 ? 'A' : '0') + colour;
583 desc[i] = textcolour;
585 sprintf(desc+i, ",%d", moves);
587 free_scratch(scratch);
592 static char *validate_desc(const game_params *params, const char *desc)
594 int w = params->w, h = params->h, wh = w*h;
596 for (i = 0; i < wh; i++) {
599 return "Not enough data in grid description";
600 if (c >= '0' && c <= '9')
602 else if (c >= 'A' && c <= 'Z')
605 return "Bad character in grid description";
606 if ((unsigned)c >= params->colours)
607 return "Colour out of range in grid description";
610 return "Expected ',' after grid description";
612 if (desc[strspn(desc, "0123456789")])
613 return "Badly formatted move limit after grid description";
617 static game_state *new_game(midend *me, const game_params *params,
620 int w = params->w, h = params->h, wh = w*h;
621 game_state *state = snew(game_state);
626 state->colours = params->colours;
628 state->grid = snewn(wh, char);
630 for (i = 0; i < wh; i++) {
633 if (c >= '0' && c <= '9')
635 else if (c >= 'A' && c <= 'Z')
638 assert(!"bad colour");
641 assert(*desc == ',');
644 state->movelimit = atoi(desc);
645 state->complete = FALSE;
646 state->cheated = FALSE;
653 static game_state *dup_game(const game_state *state)
655 game_state *ret = snew(game_state);
659 ret->colours = state->colours;
660 ret->moves = state->moves;
661 ret->movelimit = state->movelimit;
662 ret->complete = state->complete;
663 ret->grid = snewn(state->w * state->h, char);
664 memcpy(ret->grid, state->grid, state->w * state->h * sizeof(*ret->grid));
666 ret->cheated = state->cheated;
667 ret->soln = state->soln;
669 ret->soln->refcount++;
670 ret->solnpos = state->solnpos;
675 static void free_game(game_state *state)
677 if (state->soln && --state->soln->refcount == 0) {
678 sfree(state->soln->moves);
685 static char *solve_game(const game_state *state, const game_state *currstate,
686 const char *aux, char **error)
688 int w = state->w, h = state->h, wh = w*h;
689 char *moves, *ret, *p;
692 struct solver_scratch *scratch;
694 if (currstate->complete) {
695 *error = "Puzzle is already solved";
700 * Find the best solution our solver can give.
702 moves = snewn(wh, char); /* sure to be enough */
704 scratch = new_scratch(w, h);
705 memcpy(scratch->grid2, currstate->grid, wh * sizeof(*scratch->grid2));
706 check_recursion_depth();
707 while (!completed(w, h, scratch->grid2)) {
708 char move = choosemove(w, h, scratch->grid2, FILLX, FILLY,
709 currstate->colours, scratch);
710 fill(w, h, scratch->grid2, FILLX, FILLY, move, scratch->queue[0]);
712 moves[nmoves++] = move;
714 free_scratch(scratch);
717 * Encode it as a move string.
719 len = 1; /* trailing NUL */
720 for (i = 0; i < nmoves; i++)
721 len += sprintf(buf, ",%d", moves[i]);
722 ret = snewn(len, char);
724 for (i = 0; i < nmoves; i++)
725 p += sprintf(p, "%c%d", (i==0 ? 'S' : ','), moves[i]);
726 assert(p - ret == len - 1);
732 static int game_can_format_as_text_now(const game_params *params)
737 static char *game_text_format(const game_state *state)
739 int w = state->w, h = state->h;
743 len = h * (w+1); /* +1 for newline after each row */
744 ret = snewn(len+1, char); /* and +1 for terminating \0 */
747 for (y = 0; y < h; y++) {
748 for (x = 0; x < w; x++) {
749 char colour = state->grid[y*w+x];
750 char textcolour = (colour > 9 ? 'A' : '0') + colour;
756 assert(p - ret == len);
765 enum { VICTORY, DEFEAT } flash_type;
768 static game_ui *new_ui(const game_state *state)
770 struct game_ui *ui = snew(struct game_ui);
771 ui->cursor_visible = FALSE;
777 static void free_ui(game_ui *ui)
782 static char *encode_ui(const game_ui *ui)
787 static void decode_ui(game_ui *ui, const char *encoding)
791 static void game_changed_state(game_ui *ui, const game_state *oldstate,
792 const game_state *newstate)
796 struct game_drawstate {
802 #define TILESIZE (ds->tilesize)
803 #define PREFERRED_TILESIZE 32
804 #define BORDER (TILESIZE / 2)
805 #define SEP_WIDTH (TILESIZE / 32)
806 #define CURSOR_INSET (TILESIZE / 8)
807 #define HIGHLIGHT_WIDTH (TILESIZE / 10)
808 #define COORD(x) ( (x) * TILESIZE + BORDER )
809 #define FROMCOORD(x) ( ((x) - BORDER + TILESIZE) / TILESIZE - 1 )
810 #define VICTORY_FLASH_FRAME 0.03F
811 #define DEFEAT_FLASH_FRAME 0.10F
813 static char *interpret_move(const game_state *state, game_ui *ui,
814 const game_drawstate *ds,
815 int x, int y, int button)
817 int w = state->w, h = state->h;
818 int tx = -1, ty = -1, move = -1;
820 if (button == LEFT_BUTTON) {
823 ui->cursor_visible = FALSE;
824 } else if (button == CURSOR_LEFT && ui->cx > 0) {
826 ui->cursor_visible = TRUE;
828 } else if (button == CURSOR_RIGHT && ui->cx+1 < w) {
830 ui->cursor_visible = TRUE;
832 } else if (button == CURSOR_UP && ui->cy > 0) {
834 ui->cursor_visible = TRUE;
836 } else if (button == CURSOR_DOWN && ui->cy+1 < h) {
838 ui->cursor_visible = TRUE;
840 } else if (button == CURSOR_SELECT) {
843 } else if (button == CURSOR_SELECT2 &&
844 state->soln && state->solnpos < state->soln->nmoves) {
845 move = state->soln->moves[state->solnpos];
850 if (tx >= 0 && tx < w && ty >= 0 && ty < h &&
851 state->grid[0] != state->grid[ty*w+tx])
852 move = state->grid[ty*w+tx];
854 if (move >= 0 && !state->complete) {
856 sprintf(buf, "M%d", move);
863 static game_state *execute_move(const game_state *state, const char *move)
868 if (move[0] == 'M' &&
869 sscanf(move+1, "%d", &c) == 1 &&
872 int *queue = snewn(state->w * state->h, int);
873 ret = dup_game(state);
874 fill(ret->w, ret->h, ret->grid, FILLX, FILLY, c, queue);
876 ret->complete = completed(ret->w, ret->h, ret->grid);
880 * If this move is the correct next one in the stored
881 * solution path, advance solnpos.
883 if (c == ret->soln->moves[ret->solnpos] &&
884 ret->solnpos+1 < ret->soln->nmoves) {
888 * Otherwise, the user has strayed from the path or
889 * else the path has come to an end; either way, the
890 * path is no longer valid.
892 ret->soln->refcount--;
893 assert(ret->soln->refcount > 0);/* `state' at least still exists */
901 } else if (*move == 'S') {
907 * This is a solve move, so we don't actually _change_ the
908 * grid but merely set up a stored solution path.
914 for (p = move; *p; p++) {
919 sol->moves = snewn(sol->nmoves, char);
920 for (i = 0, p = move; i < sol->nmoves; i++) {
922 sol->moves[i] = atoi(p);
923 p += strspn(p, "0123456789");
930 ret = dup_game(state);
932 if (ret->soln && --ret->soln->refcount == 0) {
933 sfree(ret->soln->moves);
945 /* ----------------------------------------------------------------------
949 static void game_compute_size(const game_params *params, int tilesize,
952 /* Ick: fake up `ds->tilesize' for macro expansion purposes */
953 struct { int tilesize; } ads, *ds = &ads;
954 ads.tilesize = tilesize;
956 *x = BORDER * 2 + TILESIZE * params->w;
957 *y = BORDER * 2 + TILESIZE * params->h;
960 static void game_set_size(drawing *dr, game_drawstate *ds,
961 const game_params *params, int tilesize)
963 ds->tilesize = tilesize;
966 static float *game_colours(frontend *fe, int *ncolours)
968 float *ret = snewn(3 * NCOLOURS, float);
970 game_mkhighlight(fe, ret, COL_BACKGROUND, COL_HIGHLIGHT, COL_LOWLIGHT);
972 ret[COL_SEPARATOR * 3 + 0] = 0.0F;
973 ret[COL_SEPARATOR * 3 + 1] = 0.0F;
974 ret[COL_SEPARATOR * 3 + 2] = 0.0F;
977 ret[COL_1 * 3 + 0] = 1.0F;
978 ret[COL_1 * 3 + 1] = 0.0F;
979 ret[COL_1 * 3 + 2] = 0.0F;
982 ret[COL_2 * 3 + 0] = 1.0F;
983 ret[COL_2 * 3 + 1] = 1.0F;
984 ret[COL_2 * 3 + 2] = 0.0F;
987 ret[COL_3 * 3 + 0] = 0.0F;
988 ret[COL_3 * 3 + 1] = 1.0F;
989 ret[COL_3 * 3 + 2] = 0.0F;
992 ret[COL_4 * 3 + 0] = 0.2F;
993 ret[COL_4 * 3 + 1] = 0.3F;
994 ret[COL_4 * 3 + 2] = 1.0F;
997 ret[COL_5 * 3 + 0] = 1.0F;
998 ret[COL_5 * 3 + 1] = 0.5F;
999 ret[COL_5 * 3 + 2] = 0.0F;
1002 ret[COL_6 * 3 + 0] = 0.5F;
1003 ret[COL_6 * 3 + 1] = 0.0F;
1004 ret[COL_6 * 3 + 2] = 0.7F;
1007 ret[COL_7 * 3 + 0] = 0.5F;
1008 ret[COL_7 * 3 + 1] = 0.3F;
1009 ret[COL_7 * 3 + 2] = 0.3F;
1012 ret[COL_8 * 3 + 0] = 0.4F;
1013 ret[COL_8 * 3 + 1] = 0.8F;
1014 ret[COL_8 * 3 + 2] = 1.0F;
1017 ret[COL_9 * 3 + 0] = 0.7F;
1018 ret[COL_9 * 3 + 1] = 1.0F;
1019 ret[COL_9 * 3 + 2] = 0.7F;
1022 ret[COL_10 * 3 + 0] = 1.0F;
1023 ret[COL_10 * 3 + 1] = 0.6F;
1024 ret[COL_10 * 3 + 2] = 1.0F;
1026 *ncolours = NCOLOURS;
1030 static game_drawstate *game_new_drawstate(drawing *dr, const game_state *state)
1032 struct game_drawstate *ds = snew(struct game_drawstate);
1033 int w = state->w, h = state->h, wh = w*h;
1036 ds->started = FALSE;
1038 ds->grid = snewn(wh, int);
1039 for (i = 0; i < wh; i++)
1045 static void game_free_drawstate(drawing *dr, game_drawstate *ds)
1051 #define BORDER_L 0x001
1052 #define BORDER_R 0x002
1053 #define BORDER_U 0x004
1054 #define BORDER_D 0x008
1055 #define CORNER_UL 0x010
1056 #define CORNER_UR 0x020
1057 #define CORNER_DL 0x040
1058 #define CORNER_DR 0x080
1059 #define CURSOR 0x100
1060 #define BADFLASH 0x200
1061 #define SOLNNEXT 0x400
1062 #define COLOUR_SHIFT 11
1064 static void draw_tile(drawing *dr, game_drawstate *ds,
1065 int x, int y, int tile)
1068 int tx = COORD(x), ty = COORD(y);
1070 colour = tile >> COLOUR_SHIFT;
1071 if (tile & BADFLASH)
1072 colour = COL_SEPARATOR;
1075 draw_rect(dr, tx, ty, TILESIZE, TILESIZE, colour);
1077 if (tile & BORDER_L)
1078 draw_rect(dr, tx, ty,
1079 SEP_WIDTH, TILESIZE, COL_SEPARATOR);
1080 if (tile & BORDER_R)
1081 draw_rect(dr, tx + TILESIZE - SEP_WIDTH, ty,
1082 SEP_WIDTH, TILESIZE, COL_SEPARATOR);
1083 if (tile & BORDER_U)
1084 draw_rect(dr, tx, ty,
1085 TILESIZE, SEP_WIDTH, COL_SEPARATOR);
1086 if (tile & BORDER_D)
1087 draw_rect(dr, tx, ty + TILESIZE - SEP_WIDTH,
1088 TILESIZE, SEP_WIDTH, COL_SEPARATOR);
1090 if (tile & CORNER_UL)
1091 draw_rect(dr, tx, ty,
1092 SEP_WIDTH, SEP_WIDTH, COL_SEPARATOR);
1093 if (tile & CORNER_UR)
1094 draw_rect(dr, tx + TILESIZE - SEP_WIDTH, ty,
1095 SEP_WIDTH, SEP_WIDTH, COL_SEPARATOR);
1096 if (tile & CORNER_DL)
1097 draw_rect(dr, tx, ty + TILESIZE - SEP_WIDTH,
1098 SEP_WIDTH, SEP_WIDTH, COL_SEPARATOR);
1099 if (tile & CORNER_DR)
1100 draw_rect(dr, tx + TILESIZE - SEP_WIDTH, ty + TILESIZE - SEP_WIDTH,
1101 SEP_WIDTH, SEP_WIDTH, COL_SEPARATOR);
1104 draw_rect_outline(dr, tx + CURSOR_INSET, ty + CURSOR_INSET,
1105 TILESIZE - 1 - CURSOR_INSET * 2,
1106 TILESIZE - 1 - CURSOR_INSET * 2,
1109 if (tile & SOLNNEXT) {
1110 draw_circle(dr, tx + TILESIZE/2, ty + TILESIZE/2, TILESIZE/6,
1111 COL_SEPARATOR, COL_SEPARATOR);
1114 draw_update(dr, tx, ty, TILESIZE, TILESIZE);
1117 static void game_redraw(drawing *dr, game_drawstate *ds,
1118 const game_state *oldstate, const game_state *state,
1119 int dir, const game_ui *ui,
1120 float animtime, float flashtime)
1122 int w = state->w, h = state->h, wh = w*h;
1123 int x, y, flashframe, solnmove;
1126 /* This was entirely cloned from fifteen.c; it should probably be
1127 * moved into some generic 'draw-recessed-rectangle' utility fn. */
1132 TILESIZE * w + 2 * BORDER,
1133 TILESIZE * h + 2 * BORDER, COL_BACKGROUND);
1134 draw_update(dr, 0, 0,
1135 TILESIZE * w + 2 * BORDER,
1136 TILESIZE * h + 2 * BORDER);
1139 * Recessed area containing the whole puzzle.
1141 coords[0] = COORD(w) + HIGHLIGHT_WIDTH - 1;
1142 coords[1] = COORD(h) + HIGHLIGHT_WIDTH - 1;
1143 coords[2] = COORD(w) + HIGHLIGHT_WIDTH - 1;
1144 coords[3] = COORD(0) - HIGHLIGHT_WIDTH;
1145 coords[4] = coords[2] - TILESIZE;
1146 coords[5] = coords[3] + TILESIZE;
1147 coords[8] = COORD(0) - HIGHLIGHT_WIDTH;
1148 coords[9] = COORD(h) + HIGHLIGHT_WIDTH - 1;
1149 coords[6] = coords[8] + TILESIZE;
1150 coords[7] = coords[9] - TILESIZE;
1151 draw_polygon(dr, coords, 5, COL_HIGHLIGHT, COL_HIGHLIGHT);
1153 coords[1] = COORD(0) - HIGHLIGHT_WIDTH;
1154 coords[0] = COORD(0) - HIGHLIGHT_WIDTH;
1155 draw_polygon(dr, coords, 5, COL_LOWLIGHT, COL_LOWLIGHT);
1157 draw_rect(dr, COORD(0) - SEP_WIDTH, COORD(0) - SEP_WIDTH,
1158 TILESIZE * w + 2 * SEP_WIDTH, TILESIZE * h + 2 * SEP_WIDTH,
1164 if (flashtime > 0) {
1165 float frame = (ui->flash_type == VICTORY ?
1166 VICTORY_FLASH_FRAME : DEFEAT_FLASH_FRAME);
1167 flashframe = (int)(flashtime / frame);
1172 grid = snewn(wh, char);
1173 memcpy(grid, state->grid, wh * sizeof(*grid));
1175 if (state->soln && state->solnpos < state->soln->nmoves) {
1179 * Highlight as 'next auto-solver move' every square of the
1180 * target colour which is adjacent to the currently controlled
1181 * region. We do this by first enacting the actual move, then
1182 * flood-filling again in a nonexistent colour, and finally
1183 * reverting to the original grid anything in the new colour
1184 * that was part of the original controlled region. Then
1185 * regions coloured in the dummy colour should be displayed as
1186 * soln_move with the SOLNNEXT flag.
1188 solnmove = state->soln->moves[state->solnpos];
1190 queue = snewn(wh, int);
1191 fill(w, h, grid, FILLX, FILLY, solnmove, queue);
1192 fill(w, h, grid, FILLX, FILLY, state->colours, queue);
1195 for (i = 0; i < wh; i++)
1196 if (grid[i] == state->colours && state->grid[i] != solnmove)
1197 grid[i] = state->grid[i];
1199 solnmove = 0; /* placate optimiser */
1202 if (flashframe >= 0 && ui->flash_type == VICTORY) {
1204 * Modify the display grid by superimposing our rainbow flash
1207 for (x = 0; x < w; x++) {
1208 for (y = 0; y < h; y++) {
1209 int flashpos = flashframe - (abs(x - FILLX) + abs(y - FILLY));
1210 if (flashpos >= 0 && flashpos < state->colours)
1211 grid[y*w+x] = flashpos;
1216 for (x = 0; x < w; x++) {
1217 for (y = 0; y < h; y++) {
1221 if (grid[pos] == state->colours) {
1222 tile = (solnmove << COLOUR_SHIFT) | SOLNNEXT;
1224 tile = (int)grid[pos] << COLOUR_SHIFT;
1227 if (x == 0 || grid[pos-1] != grid[pos])
1229 if (x==w-1 || grid[pos+1] != grid[pos])
1231 if (y == 0 || grid[pos-w] != grid[pos])
1233 if (y==h-1 || grid[pos+w] != grid[pos])
1235 if (x == 0 || y == 0 || grid[pos-w-1] != grid[pos])
1237 if (x==w-1 || y == 0 || grid[pos-w+1] != grid[pos])
1239 if (x == 0 || y==h-1 || grid[pos+w-1] != grid[pos])
1241 if (x==w-1 || y==h-1 || grid[pos+w+1] != grid[pos])
1243 if (ui->cursor_visible && ui->cx == x && ui->cy == y)
1246 if (flashframe >= 0 && ui->flash_type == DEFEAT && flashframe != 1)
1249 if (ds->grid[pos] != tile) {
1250 draw_tile(dr, ds, x, y, tile);
1251 ds->grid[pos] = tile;
1261 sprintf(status, "%s%d / %d moves",
1262 (state->complete && state->moves <= state->movelimit ?
1263 (state->cheated ? "Auto-solved. " : "COMPLETED! ") :
1264 state->moves >= state->movelimit ? "FAILED! " :
1265 state->cheated ? "Auto-solver used. " :
1270 status_bar(dr, status);
1274 static float game_anim_length(const game_state *oldstate,
1275 const game_state *newstate, int dir, game_ui *ui)
1280 static int game_status(const game_state *state)
1282 if (state->complete && state->moves <= state->movelimit) {
1283 return +1; /* victory! */
1284 } else if (state->moves >= state->movelimit) {
1285 return -1; /* defeat */
1287 return 0; /* still playing */
1291 static float game_flash_length(const game_state *oldstate,
1292 const game_state *newstate, int dir, game_ui *ui)
1295 int old_status = game_status(oldstate);
1296 int new_status = game_status(newstate);
1297 if (old_status != new_status) {
1298 assert(old_status == 0);
1300 if (new_status == +1) {
1301 int frames = newstate->w + newstate->h + newstate->colours - 2;
1302 ui->flash_type = VICTORY;
1303 return VICTORY_FLASH_FRAME * frames;
1305 ui->flash_type = DEFEAT;
1306 return DEFEAT_FLASH_FRAME * 3;
1313 static int game_timing_state(const game_state *state, game_ui *ui)
1318 static void game_print_size(const game_params *params, float *x, float *y)
1322 static void game_print(drawing *dr, const game_state *state, int tilesize)
1327 #define thegame flood
1330 const struct game thegame = {
1331 "Flood", "games.flood", "flood",
1333 game_fetch_preset, NULL,
1338 TRUE, game_configure, custom_params,
1346 TRUE, game_can_format_as_text_now, game_text_format,
1354 PREFERRED_TILESIZE, game_compute_size, game_set_size,
1357 game_free_drawstate,
1362 FALSE, FALSE, game_print_size, game_print,
1363 TRUE, /* wants_statusbar */
1364 FALSE, game_timing_state,