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].sval = dupstr(buf);
 174     ret[0].ival = 0;
 175
 176     ret[1].name = "Height";
 177     ret[1].type = C_STRING;
 178     sprintf(buf, "%d", params->h);
 179     ret[1].sval = dupstr(buf);
 180     ret[1].ival = 0;
 181
 182     ret[2].name = "Colours";
 183     ret[2].type = C_STRING;
 184     sprintf(buf, "%d", params->colours);
 185     ret[2].sval = dupstr(buf);
 186     ret[2].ival = 0;
 187
 188     ret[3].name = "Extra moves permitted";
 189     ret[3].type = C_STRING;
 190     sprintf(buf, "%d", params->leniency);
 191     ret[3].sval = dupstr(buf);
 192     ret[3].ival = 0;
 193
 194     ret[4].name = NULL;
 195     ret[4].type = C_END;
 196     ret[4].sval = NULL;
 197     ret[4].ival = 0;
 198
 199     return ret;
 200 }
 201
 202 static game_params *custom_params(const config_item *cfg)
 203 {
 204     game_params *ret = snew(game_params);
 205
 206     ret->w = atoi(cfg[0].sval);
 207     ret->h = atoi(cfg[1].sval);
 208     ret->colours = atoi(cfg[2].sval);
 209     ret->leniency = atoi(cfg[3].sval);
 210
 211     return ret;
 212 }
 213
 214 static char *validate_params(const game_params *params, int full)
 215 {
 216     if (params->w < 2 && params->h < 2)
 217         return "Grid must contain at least two squares";
 218     if (params->colours < 3 || params->colours > 10)
 219         return "Must have between 3 and 10 colours";
 220     if (params->leniency < 0)
 221         return "Leniency must be non-negative";
 222     return NULL;
 223 }
 224
 225 #if 0
 226 /*
 227  * Bodge to permit varying the recursion depth for testing purposes.
 228
 229 To test two Floods against each other:
 230
 231 paste <(./flood.1 --generate 100 12x12c6m0#12345 | cut -f2 -d,) <(./flood.2 --generate 100 12x12c6m0#12345 | cut -f2 -d,) | awk '{print $2-$1}' | sort -n | uniq -c | awk '{print $2,$1}' | tee z
 232
 233 and then run gnuplot and plot "z".
 234
 235  */
 236 static int rdepth = 0;
 237 #define RECURSION_DEPTH (rdepth)
 238 void check_recursion_depth(void)
 239 {
 240     if (!rdepth) {
 241         const char *depthstr = getenv("FLOOD_DEPTH");
 242         rdepth = depthstr ? atoi(depthstr) : 1;
 243         rdepth = rdepth > 0 ? rdepth : 1;
 244     }
 245 }
 246 #else
 247 /*
 248  * Last time I empirically checked this, depth 3 was a noticeable
 249  * improvement on 2, but 4 only negligibly better than 3.
 250  */
 251 #define RECURSION_DEPTH 3
 252 #define check_recursion_depth() (void)0
 253 #endif
 254
 255 struct solver_scratch {
 256     int *queue[2];
 257     int *dist;
 258     char *grid, *grid2;
 259     char *rgrids;
 260 };
 261
 262 static struct solver_scratch *new_scratch(int w, int h)
 263 {
 264     int wh = w*h;
 265     struct solver_scratch *scratch = snew(struct solver_scratch);
 266     check_recursion_depth();
 267     scratch->queue[0] = snewn(wh, int);
 268     scratch->queue[1] = snewn(wh, int);
 269     scratch->dist = snewn(wh, int);
 270     scratch->grid = snewn(wh, char);
 271     scratch->grid2 = snewn(wh, char);
 272     scratch->rgrids = snewn(wh * RECURSION_DEPTH, char);
 273     return scratch;
 274 }
 275
 276 static void free_scratch(struct solver_scratch *scratch)
 277 {
 278     sfree(scratch->queue[0]);
 279     sfree(scratch->queue[1]);
 280     sfree(scratch->dist);
 281     sfree(scratch->grid);
 282     sfree(scratch->grid2);
 283     sfree(scratch->rgrids);
 284     sfree(scratch);
 285 }
 286
 287 #if 0
 288 /* Diagnostic routines you can uncomment if you need them */
 289 void dump_grid(int w, int h, const char *grid, const char *titlefmt, ...)
 290 {
 291     int x, y;
 292     if (titlefmt) {
 293         va_list ap;
 294         va_start(ap, titlefmt);
 295         vprintf(titlefmt, ap);
 296         va_end(ap);
 297         printf(":\n");
 298     } else {
 299         printf("Grid:\n");
 300     }
 301     for (y = 0; y < h; y++) {
 302         printf("  ");
 303         for (x = 0; x < w; x++) {
 304             printf("%1x", grid[y*w+x]);
 305         }
 306         printf("\n");
 307     }
 308 }
 309
 310 void dump_dist(int w, int h, const int *dists, const char *titlefmt, ...)
 311 {
 312     int x, y;
 313     if (titlefmt) {
 314         va_list ap;
 315         va_start(ap, titlefmt);
 316         vprintf(titlefmt, ap);
 317         va_end(ap);
 318         printf(":\n");
 319     } else {
 320         printf("Distances:\n");
 321     }
 322     for (y = 0; y < h; y++) {
 323         printf("  ");
 324         for (x = 0; x < w; x++) {
 325             printf("%3d", dists[y*w+x]);
 326         }
 327         printf("\n");
 328     }
 329 }
 330 #endif
 331
 332 /*
 333  * Search a grid to find the most distant square(s). Return their
 334  * distance and the number of them, and also the number of squares in
 335  * the current controlled set (i.e. at distance zero).
 336  */
 337 static void search(int w, int h, char *grid, int x0, int y0,
 338                    struct solver_scratch *scratch,
 339                    int *rdist, int *rnumber, int *rcontrol)
 340 {
 341     int wh = w*h;
 342     int i, qcurr, qhead, qtail, qnext, currdist, remaining;
 343
 344     for (i = 0; i < wh; i++)
 345         scratch->dist[i] = -1;
 346     scratch->queue[0][0] = y0*w+x0;
 347     scratch->queue[1][0] = y0*w+x0;
 348     scratch->dist[y0*w+x0] = 0;
 349     currdist = 0;
 350     qcurr = 0;
 351     qtail = 0;
 352     qhead = 1;
 353     qnext = 1;
 354     remaining = wh - 1;
 355
 356     while (1) {
 357         if (qtail == qhead) {
 358             /* Switch queues. */
 359             if (currdist == 0)
 360                 *rcontrol = qhead;
 361             currdist++;
 362             qcurr ^= 1;                    /* switch queues */
 363             qhead = qnext;
 364             qtail = 0;
 365             qnext = 0;
 366 #if 0
 367             printf("switch queue, new dist %d, queue %d\n", currdist, qhead);
 368 #endif
 369         } else if (remaining == 0 && qnext == 0) {
 370             break;
 371         } else {
 372             int pos = scratch->queue[qcurr][qtail++];
 373             int y = pos / w;
 374             int x = pos % w;
 375 #if 0
 376             printf("checking neighbours of %d,%d\n", x, y);
 377 #endif
 378             int dir;
 379             for (dir = 0; dir < 4; dir++) {
 380                 int y1 = y + (dir == 1 ? 1 : dir == 3 ? -1 : 0);
 381                 int x1 = x + (dir == 0 ? 1 : dir == 2 ? -1 : 0);
 382                 if (0 <= x1 && x1 < w && 0 <= y1 && y1 < h) {
 383                     int pos1 = y1*w+x1;
 384 #if 0
 385                     printf("trying %d,%d: colours %d-%d dist %d\n", x1, y1,
 386                            grid[pos], grid[pos1], scratch->dist[pos]);
 387 #endif
 388                     if (scratch->dist[pos1] == -1 &&
 389                         ((grid[pos1] == grid[pos] &&
 390                           scratch->dist[pos] == currdist) ||
 391                          (grid[pos1] != grid[pos] &&
 392                           scratch->dist[pos] == currdist - 1))) {
 393 #if 0
 394                         printf("marking %d,%d dist %d\n", x1, y1, currdist);
 395 #endif
 396                         scratch->queue[qcurr][qhead++] = pos1;
 397                         scratch->queue[qcurr^1][qnext++] = pos1;
 398                         scratch->dist[pos1] = currdist;
 399                         remaining--;
 400                     }
 401                 }
 402             }
 403         }
 404     }
 405
 406     *rdist = currdist;
 407     *rnumber = qhead;
 408     if (currdist == 0)
 409         *rcontrol = qhead;
 410 }
 411
 412 /*
 413  * Enact a flood-fill move on a grid.
 414  */
 415 static void fill(int w, int h, char *grid, int x0, int y0, char newcolour,
 416                  int *queue)
 417 {
 418     char oldcolour;
 419     int qhead, qtail;
 420
 421     oldcolour = grid[y0*w+x0];
 422     assert(oldcolour != newcolour);
 423     grid[y0*w+x0] = newcolour;
 424     queue[0] = y0*w+x0;
 425     qtail = 0;
 426     qhead = 1;
 427
 428     while (qtail < qhead) {
 429         int pos = queue[qtail++];
 430         int y = pos / w;
 431         int x = pos % w;
 432         int dir;
 433         for (dir = 0; dir < 4; dir++) {
 434             int y1 = y + (dir == 1 ? 1 : dir == 3 ? -1 : 0);
 435             int x1 = x + (dir == 0 ? 1 : dir == 2 ? -1 : 0);
 436             if (0 <= x1 && x1 < w && 0 <= y1 && y1 < h) {
 437                 int pos1 = y1*w+x1;
 438                 if (grid[pos1] == oldcolour) {
 439                     grid[pos1] = newcolour;
 440                     queue[qhead++] = pos1;
 441                 }
 442             }
 443         }
 444     }
 445 }
 446
 447 /*
 448  * Detect a completed grid.
 449  */
 450 static int completed(int w, int h, char *grid)
 451 {
 452     int wh = w*h;
 453     int i;
 454
 455     for (i = 1; i < wh; i++)
 456         if (grid[i] != grid[0])
 457             return FALSE;
 458
 459     return TRUE;
 460 }
 461
 462 /*
 463  * Try out every possible move on a grid, and choose whichever one
 464  * reduced the result of search() by the most.
 465  */
 466 static char choosemove_recurse(int w, int h, char *grid, int x0, int y0,
 467                                int maxmove, struct solver_scratch *scratch,
 468                                int depth, int *rbestdist, int *rbestnumber, int *rbestcontrol)
 469 {
 470     int wh = w*h;
 471     char move, bestmove;
 472     int dist, number, control, bestdist, bestnumber, bestcontrol;
 473     char *tmpgrid;
 474
 475     assert(0 <= depth && depth < RECURSION_DEPTH);
 476     tmpgrid = scratch->rgrids + depth*wh;
 477
 478     bestdist = wh + 1;
 479     bestnumber = 0;
 480     bestcontrol = 0;
 481     bestmove = -1;
 482
 483 #if 0
 484     dump_grid(w, h, grid, "before choosemove_recurse %d", depth);
 485 #endif
 486     for (move = 0; move < maxmove; move++) {
 487         if (grid[y0*w+x0] == move)
 488             continue;
 489         memcpy(tmpgrid, grid, wh * sizeof(*grid));
 490         fill(w, h, tmpgrid, x0, y0, move, scratch->queue[0]);
 491         if (completed(w, h, tmpgrid)) {
 492             /*
 493              * A move that wins is immediately the best, so stop
 494              * searching. Record what depth of recursion that happened
 495              * at, so that higher levels will choose a move that gets
 496              * to a winning position sooner.
 497              */
 498             *rbestdist = -1;
 499             *rbestnumber = depth;
 500             *rbestcontrol = wh;
 501             return move;
 502         }
 503         if (depth < RECURSION_DEPTH-1) {
 504             choosemove_recurse(w, h, tmpgrid, x0, y0, maxmove, scratch,
 505                                depth+1, &dist, &number, &control);
 506         } else {
 507 #if 0
 508             dump_grid(w, h, tmpgrid, "after move %d at depth %d",
 509                       move, depth);
 510 #endif
 511             search(w, h, tmpgrid, x0, y0, scratch, &dist, &number, &control);
 512 #if 0
 513             dump_dist(w, h, scratch->dist, "after move %d at depth %d",
 514                       move, depth);
 515             printf("move %d at depth %d: %d at %d\n",
 516                    depth, move, number, dist);
 517 #endif
 518         }
 519         if (dist < bestdist ||
 520             (dist == bestdist &&
 521              (number < bestnumber ||
 522               (number == bestnumber &&
 523                (control > bestcontrol))))) {
 524             bestdist = dist;
 525             bestnumber = number;
 526             bestcontrol = control;
 527             bestmove = move;
 528         }
 529     }
 530 #if 0
 531     printf("best at depth %d was %d (%d at %d, %d controlled)\n",
 532            depth, bestmove, bestnumber, bestdist, bestcontrol);
 533 #endif
 534
 535     *rbestdist = bestdist;
 536     *rbestnumber = bestnumber;
 537     *rbestcontrol = bestcontrol;
 538     return bestmove;
 539 }
 540 static char choosemove(int w, int h, char *grid, int x0, int y0,
 541                        int maxmove, struct solver_scratch *scratch)
 542 {
 543     int tmp0, tmp1, tmp2;
 544     return choosemove_recurse(w, h, grid, x0, y0, maxmove, scratch,
 545                               0, &tmp0, &tmp1, &tmp2);
 546 }
 547
 548 static char *new_game_desc(const game_params *params, random_state *rs,
 549                            char **aux, int interactive)
 550 {
 551     int w = params->w, h = params->h, wh = w*h;
 552     int i, moves;
 553     char *desc;
 554     struct solver_scratch *scratch;
 555
 556     scratch = new_scratch(w, h);
 557
 558     /*
 559      * Invent a random grid.
 560      */
 561     for (i = 0; i < wh; i++)
 562         scratch->grid[i] = random_upto(rs, params->colours);
 563
 564     /*
 565      * Run the solver, and count how many moves it uses.
 566      */
 567     memcpy(scratch->grid2, scratch->grid, wh * sizeof(*scratch->grid2));
 568     moves = 0;
 569     check_recursion_depth();
 570     while (!completed(w, h, scratch->grid2)) {
 571         char move = choosemove(w, h, scratch->grid2, FILLX, FILLY,
 572                                params->colours, scratch);
 573         fill(w, h, scratch->grid2, FILLX, FILLY, move, scratch->queue[0]);
 574         moves++;
 575     }
 576
 577     /*
 578      * Adjust for difficulty.
 579      */
 580     moves += params->leniency;
 581
 582     /*
 583      * Encode the game id.
 584      */
 585     desc = snewn(wh + 40, char);
 586     for (i = 0; i < wh; i++) {
 587         char colour = scratch->grid[i];
 588         char textcolour = (colour > 9 ? 'A' : '0') + colour;
 589         desc[i] = textcolour;
 590     }
 591     sprintf(desc+i, ",%d", moves);
 592
 593     free_scratch(scratch);
 594
 595     return desc;
 596 }
 597
 598 static char *validate_desc(const game_params *params, const char *desc)
 599 {
 600     int w = params->w, h = params->h, wh = w*h;
 601     int i;
 602     for (i = 0; i < wh; i++) {
 603         char c = *desc++;
 604         if (c == 0)
 605             return "Not enough data in grid description";
 606         if (c >= '0' && c <= '9')
 607             c -= '0';
 608         else if (c >= 'A' && c <= 'Z')
 609             c = 10 + (c - 'A');
 610         else
 611             return "Bad character in grid description";
 612         if ((unsigned)c >= params->colours)
 613             return "Colour out of range in grid description";
 614     }
 615     if (*desc != ',')
 616         return "Expected ',' after grid description";
 617     desc++;
 618     if (desc[strspn(desc, "0123456789")])
 619         return "Badly formatted move limit after grid description";
 620     return NULL;
 621 }
 622
 623 static game_state *new_game(midend *me, const game_params *params,
 624                             const char *desc)
 625 {
 626     int w = params->w, h = params->h, wh = w*h;
 627     game_state *state = snew(game_state);
 628     int i;
 629
 630     state->w = w;
 631     state->h = h;
 632     state->colours = params->colours;
 633     state->moves = 0;
 634     state->grid = snewn(wh, char);
 635
 636     for (i = 0; i < wh; i++) {
 637         char c = *desc++;
 638         assert(c);
 639         if (c >= '0' && c <= '9')
 640             c -= '0';
 641         else if (c >= 'A' && c <= 'Z')
 642             c = 10 + (c - 'A');
 643         else
 644             assert(!"bad colour");
 645         state->grid[i] = c;
 646     }
 647     assert(*desc == ',');
 648     desc++;
 649
 650     state->movelimit = atoi(desc);
 651     state->complete = FALSE;
 652     state->cheated = FALSE;
 653     state->solnpos = 0;
 654     state->soln = NULL;
 655
 656     return state;
 657 }
 658
 659 static game_state *dup_game(const game_state *state)
 660 {
 661     game_state *ret = snew(game_state);
 662
 663     ret->w = state->w;
 664     ret->h = state->h;
 665     ret->colours = state->colours;
 666     ret->moves = state->moves;
 667     ret->movelimit = state->movelimit;
 668     ret->complete = state->complete;
 669     ret->grid = snewn(state->w * state->h, char);
 670     memcpy(ret->grid, state->grid, state->w * state->h * sizeof(*ret->grid));
 671
 672     ret->cheated = state->cheated;
 673     ret->soln = state->soln;
 674     if (ret->soln)
 675         ret->soln->refcount++;
 676     ret->solnpos = state->solnpos;
 677
 678     return ret;
 679 }
 680
 681 static void free_game(game_state *state)
 682 {
 683     if (state->soln && --state->soln->refcount == 0) {
 684         sfree(state->soln->moves);
 685         sfree(state->soln);
 686     }
 687     sfree(state->grid);
 688     sfree(state);
 689 }
 690
 691 static char *solve_game(const game_state *state, const game_state *currstate,
 692                         const char *aux, char **error)
 693 {
 694     int w = state->w, h = state->h, wh = w*h;
 695     char *moves, *ret, *p;
 696     int i, len, nmoves;
 697     char buf[256];
 698     struct solver_scratch *scratch;
 699
 700     if (currstate->complete)
 701         return NULL;
 702
 703     /*
 704      * Find the best solution our solver can give.
 705      */
 706     moves = snewn(wh, char);           /* sure to be enough */
 707     nmoves = 0;
 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]);
 715         assert(nmoves < wh);
 716         moves[nmoves++] = move;
 717     }
 718     free_scratch(scratch);
 719
 720     /*
 721      * Encode it as a move string.
 722      */
 723     len = 1;                           /* trailing NUL */
 724     for (i = 0; i < nmoves; i++)
 725         len += sprintf(buf, ",%d", moves[i]);
 726     ret = snewn(len, char);
 727     p = ret;
 728     for (i = 0; i < nmoves; i++)
 729         p += sprintf(p, "%c%d", (i==0 ? 'S' : ','), moves[i]);
 730     assert(p - ret == len - 1);
 731
 732     sfree(moves);
 733     return ret;
 734 }
 735
 736 static int game_can_format_as_text_now(const game_params *params)
 737 {
 738     return TRUE;
 739 }
 740
 741 static char *game_text_format(const game_state *state)
 742 {
 743     int w = state->w, h = state->h;
 744     char *ret, *p;
 745     int x, y, len;
 746
 747     len = h * (w+1);                   /* +1 for newline after each row */
 748     ret = snewn(len+1, char);          /* and +1 for terminating \0 */
 749     p = ret;
 750
 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;
 755             *p++ = textcolour;
 756         }
 757         *p++ = '\n';
 758     }
 759
 760     assert(p - ret == len);
 761     *p = '\0';
 762
 763     return ret;
 764 }
 765
 766 struct game_ui {
 767     int cursor_visible;
 768     int cx, cy;
 769     enum { VICTORY, DEFEAT } flash_type;
 770 };
 771
 772 static game_ui *new_ui(const game_state *state)
 773 {
 774     struct game_ui *ui = snew(struct game_ui);
 775     ui->cursor_visible = FALSE;
 776     ui->cx = FILLX;
 777     ui->cy = FILLY;
 778     return ui;
 779 }
 780
 781 static void free_ui(game_ui *ui)
 782 {
 783     sfree(ui);
 784 }
 785
 786 static char *encode_ui(const game_ui *ui)
 787 {
 788     return NULL;
 789 }
 790
 791 static void decode_ui(game_ui *ui, const char *encoding)
 792 {
 793 }
 794
 795 static void game_changed_state(game_ui *ui, const game_state *oldstate,
 796                                const game_state *newstate)
 797 {
 798 }
 799
 800 struct game_drawstate {
 801     int started;
 802     int tilesize;
 803     int *grid;
 804 };
 805
 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
 816
 817 static char *interpret_move(const game_state *state, game_ui *ui,
 818                             const game_drawstate *ds,
 819                             int x, int y, int button)
 820 {
 821     int w = state->w, h = state->h;
 822     int tx = -1, ty = -1, move = -1;
 823
 824     if (button == LEFT_BUTTON) {
 825         tx = FROMCOORD(x);
 826         ty = FROMCOORD(y);
 827         ui->cursor_visible = FALSE;
 828     } else if (button == CURSOR_LEFT && ui->cx > 0) {
 829         ui->cx--;
 830         ui->cursor_visible = TRUE;
 831         return "";
 832     } else if (button == CURSOR_RIGHT && ui->cx+1 < w) {
 833         ui->cx++;
 834         ui->cursor_visible = TRUE;
 835         return "";
 836     } else if (button == CURSOR_UP && ui->cy > 0) {
 837         ui->cy--;
 838         ui->cursor_visible = TRUE;
 839         return "";
 840     } else if (button == CURSOR_DOWN && ui->cy+1 < h) {
 841         ui->cy++;
 842         ui->cursor_visible = TRUE;
 843         return "";
 844     } else if (button == CURSOR_SELECT) {
 845         tx = ui->cx;
 846         ty = ui->cy;
 847     } else if (button == CURSOR_SELECT2 &&
 848                state->soln && state->solnpos < state->soln->nmoves) {
 849         move = state->soln->moves[state->solnpos];
 850     } else {
 851         return NULL;
 852     }
 853
 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];
 857
 858     if (move >= 0 && !state->complete) {
 859         char buf[256];
 860         sprintf(buf, "M%d", move);
 861         return dupstr(buf);
 862     }
 863
 864     return NULL;
 865 }
 866
 867 static game_state *execute_move(const game_state *state, const char *move)
 868 {
 869     game_state *ret;
 870     int c;
 871
 872     if (move[0] == 'M' &&
 873         sscanf(move+1, "%d", &c) == 1 &&
 874         c >= 0 &&
 875         !state->complete) {
 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);
 879         ret->moves++;
 880         ret->complete = completed(ret->w, ret->h, ret->grid);
 881
 882         if (ret->soln) {
 883             /*
 884              * If this move is the correct next one in the stored
 885              * solution path, advance solnpos.
 886              */
 887             if (c == ret->soln->moves[ret->solnpos] &&
 888                 ret->solnpos+1 < ret->soln->nmoves) {
 889                 ret->solnpos++;
 890             } else {
 891                 /*
 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.
 895                  */
 896                 ret->soln->refcount--;
 897                 assert(ret->soln->refcount > 0);/* `state' at least still exists */
 898                 ret->soln = NULL;
 899                 ret->solnpos = 0;
 900             }
 901         }
 902
 903         sfree(queue);
 904         return ret;
 905     } else if (*move == 'S') {
 906         soln *sol;
 907         const char *p;
 908         int i;
 909
 910         /*
 911          * This is a solve move, so we don't actually _change_ the
 912          * grid but merely set up a stored solution path.
 913          */
 914         move++;
 915         sol = snew(soln);
 916
 917         sol->nmoves = 1;
 918         for (p = move; *p; p++) {
 919             if (*p == ',')
 920                 sol->nmoves++;
 921         }
 922
 923         sol->moves = snewn(sol->nmoves, char);
 924         for (i = 0, p = move; i < sol->nmoves; i++) {
 925             assert(*p);
 926             sol->moves[i] = atoi(p);
 927             p += strspn(p, "0123456789");
 928             if (*p) {
 929                 assert(*p == ',');
 930                 p++;
 931             }
 932         }
 933
 934         ret = dup_game(state);
 935         ret->cheated = TRUE;
 936         if (ret->soln && --ret->soln->refcount == 0) {
 937             sfree(ret->soln->moves);
 938             sfree(ret->soln);
 939         }
 940         ret->soln = sol;
 941         ret->solnpos = 0;
 942         sol->refcount = 1;
 943         return ret;
 944     }
 945
 946     return NULL;
 947 }
 948
 949 /* ----------------------------------------------------------------------
 950  * Drawing routines.
 951  */
 952
 953 static void game_compute_size(const game_params *params, int tilesize,
 954                               int *x, int *y)
 955 {
 956     /* Ick: fake up `ds->tilesize' for macro expansion purposes */
 957     struct { int tilesize; } ads, *ds = &ads;
 958     ads.tilesize = tilesize;
 959
 960     *x = BORDER * 2 + TILESIZE * params->w;
 961     *y = BORDER * 2 + TILESIZE * params->h;
 962 }
 963
 964 static void game_set_size(drawing *dr, game_drawstate *ds,
 965                           const game_params *params, int tilesize)
 966 {
 967     ds->tilesize = tilesize;
 968 }
 969
 970 static float *game_colours(frontend *fe, int *ncolours)
 971 {
 972     float *ret = snewn(3 * NCOLOURS, float);
 973
 974     game_mkhighlight(fe, ret, COL_BACKGROUND, COL_HIGHLIGHT, COL_LOWLIGHT);
 975
 976     ret[COL_SEPARATOR * 3 + 0] = 0.0F;
 977     ret[COL_SEPARATOR * 3 + 1] = 0.0F;
 978     ret[COL_SEPARATOR * 3 + 2] = 0.0F;
 979
 980     /* red */
 981     ret[COL_1 * 3 + 0] = 1.0F;
 982     ret[COL_1 * 3 + 1] = 0.0F;
 983     ret[COL_1 * 3 + 2] = 0.0F;
 984
 985     /* yellow */
 986     ret[COL_2 * 3 + 0] = 1.0F;
 987     ret[COL_2 * 3 + 1] = 1.0F;
 988     ret[COL_2 * 3 + 2] = 0.0F;
 989
 990     /* green */
 991     ret[COL_3 * 3 + 0] = 0.0F;
 992     ret[COL_3 * 3 + 1] = 1.0F;
 993     ret[COL_3 * 3 + 2] = 0.0F;
 994
 995     /* blue */
 996     ret[COL_4 * 3 + 0] = 0.2F;
 997     ret[COL_4 * 3 + 1] = 0.3F;
 998     ret[COL_4 * 3 + 2] = 1.0F;
 999
1000     /* orange */
1001     ret[COL_5 * 3 + 0] = 1.0F;
1002     ret[COL_5 * 3 + 1] = 0.5F;
1003     ret[COL_5 * 3 + 2] = 0.0F;
1004
1005     /* purple */
1006     ret[COL_6 * 3 + 0] = 0.5F;
1007     ret[COL_6 * 3 + 1] = 0.0F;
1008     ret[COL_6 * 3 + 2] = 0.7F;
1009
1010     /* brown */
1011     ret[COL_7 * 3 + 0] = 0.5F;
1012     ret[COL_7 * 3 + 1] = 0.3F;
1013     ret[COL_7 * 3 + 2] = 0.3F;
1014
1015     /* light blue */
1016     ret[COL_8 * 3 + 0] = 0.4F;
1017     ret[COL_8 * 3 + 1] = 0.8F;
1018     ret[COL_8 * 3 + 2] = 1.0F;
1019
1020     /* light green */
1021     ret[COL_9 * 3 + 0] = 0.7F;
1022     ret[COL_9 * 3 + 1] = 1.0F;
1023     ret[COL_9 * 3 + 2] = 0.7F;
1024
1025     /* pink */
1026     ret[COL_10 * 3 + 0] = 1.0F;
1027     ret[COL_10 * 3 + 1] = 0.6F;
1028     ret[COL_10 * 3 + 2] = 1.0F;
1029
1030     *ncolours = NCOLOURS;
1031     return ret;
1032 }
1033
1034 static game_drawstate *game_new_drawstate(drawing *dr, const game_state *state)
1035 {
1036     struct game_drawstate *ds = snew(struct game_drawstate);
1037     int w = state->w, h = state->h, wh = w*h;
1038     int i;
1039
1040     ds->started = FALSE;
1041     ds->tilesize = 0;
1042     ds->grid = snewn(wh, int);
1043     for (i = 0; i < wh; i++)
1044         ds->grid[i] = -1;
1045
1046     return ds;
1047 }
1048
1049 static void game_free_drawstate(drawing *dr, game_drawstate *ds)
1050 {
1051     sfree(ds->grid);
1052     sfree(ds);
1053 }
1054
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
1067
1068 static void draw_tile(drawing *dr, game_drawstate *ds,
1069                       int x, int y, int tile)
1070 {
1071     int colour;
1072     int tx = COORD(x), ty = COORD(y);
1073
1074     colour = tile >> COLOUR_SHIFT;
1075     if (tile & BADFLASH)
1076         colour = COL_SEPARATOR;
1077     else
1078         colour += COL_1;
1079     draw_rect(dr, tx, ty, TILESIZE, TILESIZE, colour);
1080
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);
1093
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);
1106
1107     if (tile & CURSOR)
1108         draw_rect_outline(dr, tx + CURSOR_INSET, ty + CURSOR_INSET,
1109                           TILESIZE - 1 - CURSOR_INSET * 2,
1110                           TILESIZE - 1 - CURSOR_INSET * 2,
1111                           COL_SEPARATOR);
1112
1113     if (tile & SOLNNEXT) {
1114         draw_circle(dr, tx + TILESIZE/2, ty + TILESIZE/2, TILESIZE/6,
1115                     COL_SEPARATOR, COL_SEPARATOR);
1116     }
1117
1118     draw_update(dr, tx, ty, TILESIZE, TILESIZE);
1119 }
1120
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)
1125 {
1126     int w = state->w, h = state->h, wh = w*h;
1127     int x, y, flashframe, solnmove;
1128     char *grid;
1129
1130     /* This was entirely cloned from fifteen.c; it should probably be
1131      * moved into some generic 'draw-recessed-rectangle' utility fn. */
1132     if (!ds->started) {
1133         int coords[10];
1134
1135         draw_rect(dr, 0, 0,
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);
1141
1142         /*
1143          * Recessed area containing the whole puzzle.
1144          */
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);
1156
1157         coords[1] = COORD(0) - HIGHLIGHT_WIDTH;
1158         coords[0] = COORD(0) - HIGHLIGHT_WIDTH;
1159         draw_polygon(dr, coords, 5, COL_LOWLIGHT, COL_LOWLIGHT);
1160
1161         draw_rect(dr, COORD(0) - SEP_WIDTH, COORD(0) - SEP_WIDTH,
1162                   TILESIZE * w + 2 * SEP_WIDTH, TILESIZE * h + 2 * SEP_WIDTH,
1163                   COL_SEPARATOR);
1164
1165         ds->started = 1;
1166     }
1167
1168     if (flashtime > 0) {
1169         float frame = (ui->flash_type == VICTORY ?
1170                        VICTORY_FLASH_FRAME : DEFEAT_FLASH_FRAME);
1171         flashframe = (int)(flashtime / frame);
1172     } else {
1173         flashframe = -1;
1174     }
1175
1176     grid = snewn(wh, char);
1177     memcpy(grid, state->grid, wh * sizeof(*grid));
1178
1179     if (state->soln && state->solnpos < state->soln->nmoves) {
1180         int i, *queue;
1181
1182         /*
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.
1191          */
1192         solnmove = state->soln->moves[state->solnpos];
1193
1194         queue = snewn(wh, int);
1195         fill(w, h, grid, FILLX, FILLY, solnmove, queue);
1196         fill(w, h, grid, FILLX, FILLY, state->colours, queue);
1197         sfree(queue);
1198
1199         for (i = 0; i < wh; i++)
1200             if (grid[i] == state->colours && state->grid[i] != solnmove)
1201                 grid[i] = state->grid[i];
1202     } else {
1203         solnmove = 0;                  /* placate optimiser */
1204     }
1205
1206     if (flashframe >= 0 && ui->flash_type == VICTORY) {
1207         /*
1208          * Modify the display grid by superimposing our rainbow flash
1209          * on it.
1210          */
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;
1216             }
1217         }
1218     }
1219
1220     for (x = 0; x < w; x++) {
1221         for (y = 0; y < h; y++) {
1222             int pos = y*w+x;
1223             int tile;
1224
1225             if (grid[pos] == state->colours) {
1226                 tile = (solnmove << COLOUR_SHIFT) | SOLNNEXT;
1227             } else {
1228                 tile = (int)grid[pos] << COLOUR_SHIFT;
1229             }
1230
1231             if (x == 0 || grid[pos-1] != grid[pos])
1232                 tile |= BORDER_L;
1233             if (x==w-1 || grid[pos+1] != grid[pos])
1234                 tile |= BORDER_R;
1235             if (y == 0 || grid[pos-w] != grid[pos])
1236                 tile |= BORDER_U;
1237             if (y==h-1 || grid[pos+w] != grid[pos])
1238                 tile |= BORDER_D;
1239             if (x == 0 || y == 0 || grid[pos-w-1] != grid[pos])
1240                 tile |= CORNER_UL;
1241             if (x==w-1 || y == 0 || grid[pos-w+1] != grid[pos])
1242                 tile |= CORNER_UR;
1243             if (x == 0 || y==h-1 || grid[pos+w-1] != grid[pos])
1244                 tile |= CORNER_DL;
1245             if (x==w-1 || y==h-1 || grid[pos+w+1] != grid[pos])
1246                 tile |= CORNER_DR;
1247             if (ui->cursor_visible && ui->cx == x && ui->cy == y)
1248                 tile |= CURSOR;
1249
1250             if (flashframe >= 0 && ui->flash_type == DEFEAT && flashframe != 1)
1251                 tile |= BADFLASH;
1252
1253             if (ds->grid[pos] != tile) {
1254                 draw_tile(dr, ds, x, y, tile);
1255                 ds->grid[pos] = tile;
1256             }
1257         }
1258     }
1259
1260     sfree(grid);
1261
1262     {
1263         char status[255];
1264
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. " :
1270                  ""),
1271                 state->moves,
1272                 state->movelimit);
1273
1274         status_bar(dr, status);
1275     }
1276 }
1277
1278 static float game_anim_length(const game_state *oldstate,
1279                               const game_state *newstate, int dir, game_ui *ui)
1280 {
1281     return 0.0F;
1282 }
1283
1284 static int game_status(const game_state *state)
1285 {
1286     if (state->complete && state->moves <= state->movelimit) {
1287         return +1;                     /* victory! */
1288     } else if (state->moves >= state->movelimit) {
1289         return -1;                     /* defeat */
1290     } else {
1291         return 0;                      /* still playing */
1292     }
1293 }
1294
1295 static float game_flash_length(const game_state *oldstate,
1296                                const game_state *newstate, int dir, game_ui *ui)
1297 {
1298     if (dir == +1) {
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);
1303
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;
1308             } else {
1309                 ui->flash_type = DEFEAT;
1310                 return DEFEAT_FLASH_FRAME * 3;
1311             }
1312         }
1313     }
1314     return 0.0F;
1315 }
1316
1317 static int game_timing_state(const game_state *state, game_ui *ui)
1318 {
1319     return TRUE;
1320 }
1321
1322 static void game_print_size(const game_params *params, float *x, float *y)
1323 {
1324 }
1325
1326 static void game_print(drawing *dr, const game_state *state, int tilesize)
1327 {
1328 }
1329
1330 #ifdef COMBINED
1331 #define thegame flood
1332 #endif
1333
1334 const struct game thegame = {
1335     "Flood", "games.flood", "flood",
1336     default_params,
1337     game_fetch_preset,
1338     decode_params,
1339     encode_params,
1340     free_params,
1341     dup_params,
1342     TRUE, game_configure, custom_params,
1343     validate_params,
1344     new_game_desc,
1345     validate_desc,
1346     new_game,
1347     dup_game,
1348     free_game,
1349     TRUE, solve_game,
1350     TRUE, game_can_format_as_text_now, game_text_format,
1351     new_ui,
1352     free_ui,
1353     encode_ui,
1354     decode_ui,
1355     game_changed_state,
1356     interpret_move,
1357     execute_move,
1358     PREFERRED_TILESIZE, game_compute_size, game_set_size,
1359     game_colours,
1360     game_new_drawstate,
1361     game_free_drawstate,
1362     game_redraw,
1363     game_anim_length,
1364     game_flash_length,
1365     game_status,
1366     FALSE, FALSE, game_print_size, game_print,
1367     TRUE,                              /* wants_statusbar */
1368     FALSE, game_timing_state,
1369     0,                                 /* flags */
1370 };