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