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