flood.c

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