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         *error = "Puzzle is already solved";
 702         return NULL;
 703     }
 704
 705     /*
 706      * Find the best solution our solver can give.
 707      */
 708     moves = snewn(wh, char);           /* sure to be enough */
 709     nmoves = 0;
 710     scratch = new_scratch(w, h);
 711     memcpy(scratch->grid2, currstate->grid, wh * sizeof(*scratch->grid2));
 712     check_recursion_depth();
 713     while (!completed(w, h, scratch->grid2)) {
 714         char move = choosemove(w, h, scratch->grid2, FILLX, FILLY,
 715                                currstate->colours, scratch);
 716         fill(w, h, scratch->grid2, FILLX, FILLY, move, scratch->queue[0]);
 717         assert(nmoves < wh);
 718         moves[nmoves++] = move;
 719     }
 720     free_scratch(scratch);
 721
 722     /*
 723      * Encode it as a move string.
 724      */
 725     len = 1;                           /* trailing NUL */
 726     for (i = 0; i < nmoves; i++)
 727         len += sprintf(buf, ",%d", moves[i]);
 728     ret = snewn(len, char);
 729     p = ret;
 730     for (i = 0; i < nmoves; i++)
 731         p += sprintf(p, "%c%d", (i==0 ? 'S' : ','), moves[i]);
 732     assert(p - ret == len - 1);
 733
 734     sfree(moves);
 735     return ret;
 736 }
 737
 738 static int game_can_format_as_text_now(const game_params *params)
 739 {
 740     return TRUE;
 741 }
 742
 743 static char *game_text_format(const game_state *state)
 744 {
 745     int w = state->w, h = state->h;
 746     char *ret, *p;
 747     int x, y, len;
 748
 749     len = h * (w+1);                   /* +1 for newline after each row */
 750     ret = snewn(len+1, char);          /* and +1 for terminating \0 */
 751     p = ret;
 752
 753     for (y = 0; y < h; y++) {
 754         for (x = 0; x < w; x++) {
 755             char colour = state->grid[y*w+x];
 756             char textcolour = (colour > 9 ? 'A' : '0') + colour;
 757             *p++ = textcolour;
 758         }
 759         *p++ = '\n';
 760     }
 761
 762     assert(p - ret == len);
 763     *p = '\0';
 764
 765     return ret;
 766 }
 767
 768 struct game_ui {
 769     int cursor_visible;
 770     int cx, cy;
 771     enum { VICTORY, DEFEAT } flash_type;
 772 };
 773
 774 static game_ui *new_ui(const game_state *state)
 775 {
 776     struct game_ui *ui = snew(struct game_ui);
 777     ui->cursor_visible = FALSE;
 778     ui->cx = FILLX;
 779     ui->cy = FILLY;
 780     return ui;
 781 }
 782
 783 static void free_ui(game_ui *ui)
 784 {
 785     sfree(ui);
 786 }
 787
 788 static char *encode_ui(const game_ui *ui)
 789 {
 790     return NULL;
 791 }
 792
 793 static void decode_ui(game_ui *ui, const char *encoding)
 794 {
 795 }
 796
 797 static void game_changed_state(game_ui *ui, const game_state *oldstate,
 798                                const game_state *newstate)
 799 {
 800 }
 801
 802 struct game_drawstate {
 803     int started;
 804     int tilesize;
 805     int *grid;
 806 };
 807
 808 #define TILESIZE (ds->tilesize)
 809 #define PREFERRED_TILESIZE 32
 810 #define BORDER (TILESIZE / 2)
 811 #define SEP_WIDTH (TILESIZE / 32)
 812 #define CURSOR_INSET (TILESIZE / 8)
 813 #define HIGHLIGHT_WIDTH (TILESIZE / 10)
 814 #define COORD(x)  ( (x) * TILESIZE + BORDER )
 815 #define FROMCOORD(x)  ( ((x) - BORDER + TILESIZE) / TILESIZE - 1 )
 816 #define VICTORY_FLASH_FRAME 0.03F
 817 #define DEFEAT_FLASH_FRAME 0.10F
 818
 819 static char *interpret_move(const game_state *state, game_ui *ui,
 820                             const game_drawstate *ds,
 821                             int x, int y, int button)
 822 {
 823     int w = state->w, h = state->h;
 824     int tx = -1, ty = -1, move = -1;
 825
 826     if (button == LEFT_BUTTON) {
 827         tx = FROMCOORD(x);
 828         ty = FROMCOORD(y);
 829         ui->cursor_visible = FALSE;
 830     } else if (button == CURSOR_LEFT && ui->cx > 0) {
 831         ui->cx--;
 832         ui->cursor_visible = TRUE;
 833         return "";
 834     } else if (button == CURSOR_RIGHT && ui->cx+1 < w) {
 835         ui->cx++;
 836         ui->cursor_visible = TRUE;
 837         return "";
 838     } else if (button == CURSOR_UP && ui->cy > 0) {
 839         ui->cy--;
 840         ui->cursor_visible = TRUE;
 841         return "";
 842     } else if (button == CURSOR_DOWN && ui->cy+1 < h) {
 843         ui->cy++;
 844         ui->cursor_visible = TRUE;
 845         return "";
 846     } else if (button == CURSOR_SELECT) {
 847         tx = ui->cx;
 848         ty = ui->cy;
 849     } else if (button == CURSOR_SELECT2 &&
 850                state->soln && state->solnpos < state->soln->nmoves) {
 851         move = state->soln->moves[state->solnpos];
 852     } else {
 853         return NULL;
 854     }
 855
 856     if (tx >= 0 && tx < w && ty >= 0 && ty < h &&
 857         state->grid[0] != state->grid[ty*w+tx])
 858         move = state->grid[ty*w+tx];
 859
 860     if (move >= 0 && !state->complete) {
 861         char buf[256];
 862         sprintf(buf, "M%d", move);
 863         return dupstr(buf);
 864     }
 865
 866     return NULL;
 867 }
 868
 869 static game_state *execute_move(const game_state *state, const char *move)
 870 {
 871     game_state *ret;
 872     int c;
 873
 874     if (move[0] == 'M' &&
 875         sscanf(move+1, "%d", &c) == 1 &&
 876         c >= 0 &&
 877         !state->complete) {
 878         int *queue = snewn(state->w * state->h, int);
 879         ret = dup_game(state);
 880         fill(ret->w, ret->h, ret->grid, FILLX, FILLY, c, queue);
 881         ret->moves++;
 882         ret->complete = completed(ret->w, ret->h, ret->grid);
 883
 884         if (ret->soln) {
 885             /*
 886              * If this move is the correct next one in the stored
 887              * solution path, advance solnpos.
 888              */
 889             if (c == ret->soln->moves[ret->solnpos] &&
 890                 ret->solnpos+1 < ret->soln->nmoves) {
 891                 ret->solnpos++;
 892             } else {
 893                 /*
 894                  * Otherwise, the user has strayed from the path or
 895                  * else the path has come to an end; either way, the
 896                  * path is no longer valid.
 897                  */
 898                 ret->soln->refcount--;
 899                 assert(ret->soln->refcount > 0);/* `state' at least still exists */
 900                 ret->soln = NULL;
 901                 ret->solnpos = 0;
 902             }
 903         }
 904
 905         sfree(queue);
 906         return ret;
 907     } else if (*move == 'S') {
 908         soln *sol;
 909         const char *p;
 910         int i;
 911
 912         /*
 913          * This is a solve move, so we don't actually _change_ the
 914          * grid but merely set up a stored solution path.
 915          */
 916         move++;
 917         sol = snew(soln);
 918
 919         sol->nmoves = 1;
 920         for (p = move; *p; p++) {
 921             if (*p == ',')
 922                 sol->nmoves++;
 923         }
 924
 925         sol->moves = snewn(sol->nmoves, char);
 926         for (i = 0, p = move; i < sol->nmoves; i++) {
 927             assert(*p);
 928             sol->moves[i] = atoi(p);
 929             p += strspn(p, "0123456789");
 930             if (*p) {
 931                 assert(*p == ',');
 932                 p++;
 933             }
 934         }
 935
 936         ret = dup_game(state);
 937         ret->cheated = TRUE;
 938         if (ret->soln && --ret->soln->refcount == 0) {
 939             sfree(ret->soln->moves);
 940             sfree(ret->soln);
 941         }
 942         ret->soln = sol;
 943         ret->solnpos = 0;
 944         sol->refcount = 1;
 945         return ret;
 946     }
 947
 948     return NULL;
 949 }
 950
 951 /* ----------------------------------------------------------------------
 952  * Drawing routines.
 953  */
 954
 955 static void game_compute_size(const game_params *params, int tilesize,
 956                               int *x, int *y)
 957 {
 958     /* Ick: fake up `ds->tilesize' for macro expansion purposes */
 959     struct { int tilesize; } ads, *ds = &ads;
 960     ads.tilesize = tilesize;
 961
 962     *x = BORDER * 2 + TILESIZE * params->w;
 963     *y = BORDER * 2 + TILESIZE * params->h;
 964 }
 965
 966 static void game_set_size(drawing *dr, game_drawstate *ds,
 967                           const game_params *params, int tilesize)
 968 {
 969     ds->tilesize = tilesize;
 970 }
 971
 972 static float *game_colours(frontend *fe, int *ncolours)
 973 {
 974     float *ret = snewn(3 * NCOLOURS, float);
 975
 976     game_mkhighlight(fe, ret, COL_BACKGROUND, COL_HIGHLIGHT, COL_LOWLIGHT);
 977
 978     ret[COL_SEPARATOR * 3 + 0] = 0.0F;
 979     ret[COL_SEPARATOR * 3 + 1] = 0.0F;
 980     ret[COL_SEPARATOR * 3 + 2] = 0.0F;
 981
 982     /* red */
 983     ret[COL_1 * 3 + 0] = 1.0F;
 984     ret[COL_1 * 3 + 1] = 0.0F;
 985     ret[COL_1 * 3 + 2] = 0.0F;
 986
 987     /* yellow */
 988     ret[COL_2 * 3 + 0] = 1.0F;
 989     ret[COL_2 * 3 + 1] = 1.0F;
 990     ret[COL_2 * 3 + 2] = 0.0F;
 991
 992     /* green */
 993     ret[COL_3 * 3 + 0] = 0.0F;
 994     ret[COL_3 * 3 + 1] = 1.0F;
 995     ret[COL_3 * 3 + 2] = 0.0F;
 996
 997     /* blue */
 998     ret[COL_4 * 3 + 0] = 0.2F;
 999     ret[COL_4 * 3 + 1] = 0.3F;
1000     ret[COL_4 * 3 + 2] = 1.0F;
1001
1002     /* orange */
1003     ret[COL_5 * 3 + 0] = 1.0F;
1004     ret[COL_5 * 3 + 1] = 0.5F;
1005     ret[COL_5 * 3 + 2] = 0.0F;
1006
1007     /* purple */
1008     ret[COL_6 * 3 + 0] = 0.5F;
1009     ret[COL_6 * 3 + 1] = 0.0F;
1010     ret[COL_6 * 3 + 2] = 0.7F;
1011
1012     /* brown */
1013     ret[COL_7 * 3 + 0] = 0.5F;
1014     ret[COL_7 * 3 + 1] = 0.3F;
1015     ret[COL_7 * 3 + 2] = 0.3F;
1016
1017     /* light blue */
1018     ret[COL_8 * 3 + 0] = 0.4F;
1019     ret[COL_8 * 3 + 1] = 0.8F;
1020     ret[COL_8 * 3 + 2] = 1.0F;
1021
1022     /* light green */
1023     ret[COL_9 * 3 + 0] = 0.7F;
1024     ret[COL_9 * 3 + 1] = 1.0F;
1025     ret[COL_9 * 3 + 2] = 0.7F;
1026
1027     /* pink */
1028     ret[COL_10 * 3 + 0] = 1.0F;
1029     ret[COL_10 * 3 + 1] = 0.6F;
1030     ret[COL_10 * 3 + 2] = 1.0F;
1031
1032     *ncolours = NCOLOURS;
1033     return ret;
1034 }
1035
1036 static game_drawstate *game_new_drawstate(drawing *dr, const game_state *state)
1037 {
1038     struct game_drawstate *ds = snew(struct game_drawstate);
1039     int w = state->w, h = state->h, wh = w*h;
1040     int i;
1041
1042     ds->started = FALSE;
1043     ds->tilesize = 0;
1044     ds->grid = snewn(wh, int);
1045     for (i = 0; i < wh; i++)
1046         ds->grid[i] = -1;
1047
1048     return ds;
1049 }
1050
1051 static void game_free_drawstate(drawing *dr, game_drawstate *ds)
1052 {
1053     sfree(ds->grid);
1054     sfree(ds);
1055 }
1056
1057 #define BORDER_L  0x001
1058 #define BORDER_R  0x002
1059 #define BORDER_U  0x004
1060 #define BORDER_D  0x008
1061 #define CORNER_UL 0x010
1062 #define CORNER_UR 0x020
1063 #define CORNER_DL 0x040
1064 #define CORNER_DR 0x080
1065 #define CURSOR    0x100
1066 #define BADFLASH  0x200
1067 #define SOLNNEXT  0x400
1068 #define COLOUR_SHIFT 11
1069
1070 static void draw_tile(drawing *dr, game_drawstate *ds,
1071                       int x, int y, int tile)
1072 {
1073     int colour;
1074     int tx = COORD(x), ty = COORD(y);
1075
1076     colour = tile >> COLOUR_SHIFT;
1077     if (tile & BADFLASH)
1078         colour = COL_SEPARATOR;
1079     else
1080         colour += COL_1;
1081     draw_rect(dr, tx, ty, TILESIZE, TILESIZE, colour);
1082
1083     if (tile & BORDER_L)
1084         draw_rect(dr, tx, ty,
1085                   SEP_WIDTH, TILESIZE, COL_SEPARATOR);
1086     if (tile & BORDER_R)
1087         draw_rect(dr, tx + TILESIZE - SEP_WIDTH, ty,
1088                   SEP_WIDTH, TILESIZE, COL_SEPARATOR);
1089     if (tile & BORDER_U)
1090         draw_rect(dr, tx, ty,
1091                   TILESIZE, SEP_WIDTH, COL_SEPARATOR);
1092     if (tile & BORDER_D)
1093         draw_rect(dr, tx, ty + TILESIZE - SEP_WIDTH,
1094                   TILESIZE, SEP_WIDTH, COL_SEPARATOR);
1095
1096     if (tile & CORNER_UL)
1097         draw_rect(dr, tx, ty,
1098                   SEP_WIDTH, SEP_WIDTH, COL_SEPARATOR);
1099     if (tile & CORNER_UR)
1100         draw_rect(dr, tx + TILESIZE - SEP_WIDTH, ty,
1101                   SEP_WIDTH, SEP_WIDTH, COL_SEPARATOR);
1102     if (tile & CORNER_DL)
1103         draw_rect(dr, tx, ty + TILESIZE - SEP_WIDTH,
1104                   SEP_WIDTH, SEP_WIDTH, COL_SEPARATOR);
1105     if (tile & CORNER_DR)
1106         draw_rect(dr, tx + TILESIZE - SEP_WIDTH, ty + TILESIZE - SEP_WIDTH,
1107                   SEP_WIDTH, SEP_WIDTH, COL_SEPARATOR);
1108
1109     if (tile & CURSOR)
1110         draw_rect_outline(dr, tx + CURSOR_INSET, ty + CURSOR_INSET,
1111                           TILESIZE - 1 - CURSOR_INSET * 2,
1112                           TILESIZE - 1 - CURSOR_INSET * 2,
1113                           COL_SEPARATOR);
1114
1115     if (tile & SOLNNEXT) {
1116         draw_circle(dr, tx + TILESIZE/2, ty + TILESIZE/2, TILESIZE/6,
1117                     COL_SEPARATOR, COL_SEPARATOR);
1118     }
1119
1120     draw_update(dr, tx, ty, TILESIZE, TILESIZE);
1121 }
1122
1123 static void game_redraw(drawing *dr, game_drawstate *ds,
1124                         const game_state *oldstate, const game_state *state,
1125                         int dir, const game_ui *ui,
1126                         float animtime, float flashtime)
1127 {
1128     int w = state->w, h = state->h, wh = w*h;
1129     int x, y, flashframe, solnmove;
1130     char *grid;
1131
1132     /* This was entirely cloned from fifteen.c; it should probably be
1133      * moved into some generic 'draw-recessed-rectangle' utility fn. */
1134     if (!ds->started) {
1135         int coords[10];
1136
1137         draw_rect(dr, 0, 0,
1138                   TILESIZE * w + 2 * BORDER,
1139                   TILESIZE * h + 2 * BORDER, COL_BACKGROUND);
1140         draw_update(dr, 0, 0,
1141                     TILESIZE * w + 2 * BORDER,
1142                     TILESIZE * h + 2 * BORDER);
1143
1144         /*
1145          * Recessed area containing the whole puzzle.
1146          */
1147         coords[0] = COORD(w) + HIGHLIGHT_WIDTH - 1;
1148         coords[1] = COORD(h) + HIGHLIGHT_WIDTH - 1;
1149         coords[2] = COORD(w) + HIGHLIGHT_WIDTH - 1;
1150         coords[3] = COORD(0) - HIGHLIGHT_WIDTH;
1151         coords[4] = coords[2] - TILESIZE;
1152         coords[5] = coords[3] + TILESIZE;
1153         coords[8] = COORD(0) - HIGHLIGHT_WIDTH;
1154         coords[9] = COORD(h) + HIGHLIGHT_WIDTH - 1;
1155         coords[6] = coords[8] + TILESIZE;
1156         coords[7] = coords[9] - TILESIZE;
1157         draw_polygon(dr, coords, 5, COL_HIGHLIGHT, COL_HIGHLIGHT);
1158
1159         coords[1] = COORD(0) - HIGHLIGHT_WIDTH;
1160         coords[0] = COORD(0) - HIGHLIGHT_WIDTH;
1161         draw_polygon(dr, coords, 5, COL_LOWLIGHT, COL_LOWLIGHT);
1162
1163         draw_rect(dr, COORD(0) - SEP_WIDTH, COORD(0) - SEP_WIDTH,
1164                   TILESIZE * w + 2 * SEP_WIDTH, TILESIZE * h + 2 * SEP_WIDTH,
1165                   COL_SEPARATOR);
1166
1167         ds->started = 1;
1168     }
1169
1170     if (flashtime > 0) {
1171         float frame = (ui->flash_type == VICTORY ?
1172                        VICTORY_FLASH_FRAME : DEFEAT_FLASH_FRAME);
1173         flashframe = (int)(flashtime / frame);
1174     } else {
1175         flashframe = -1;
1176     }
1177
1178     grid = snewn(wh, char);
1179     memcpy(grid, state->grid, wh * sizeof(*grid));
1180
1181     if (state->soln && state->solnpos < state->soln->nmoves) {
1182         int i, *queue;
1183
1184         /*
1185          * Highlight as 'next auto-solver move' every square of the
1186          * target colour which is adjacent to the currently controlled
1187          * region. We do this by first enacting the actual move, then
1188          * flood-filling again in a nonexistent colour, and finally
1189          * reverting to the original grid anything in the new colour
1190          * that was part of the original controlled region. Then
1191          * regions coloured in the dummy colour should be displayed as
1192          * soln_move with the SOLNNEXT flag.
1193          */
1194         solnmove = state->soln->moves[state->solnpos];
1195
1196         queue = snewn(wh, int);
1197         fill(w, h, grid, FILLX, FILLY, solnmove, queue);
1198         fill(w, h, grid, FILLX, FILLY, state->colours, queue);
1199         sfree(queue);
1200
1201         for (i = 0; i < wh; i++)
1202             if (grid[i] == state->colours && state->grid[i] != solnmove)
1203                 grid[i] = state->grid[i];
1204     } else {
1205         solnmove = 0;                  /* placate optimiser */
1206     }
1207
1208     if (flashframe >= 0 && ui->flash_type == VICTORY) {
1209         /*
1210          * Modify the display grid by superimposing our rainbow flash
1211          * on it.
1212          */
1213         for (x = 0; x < w; x++) {
1214             for (y = 0; y < h; y++) {
1215                 int flashpos = flashframe - (abs(x - FILLX) + abs(y - FILLY));
1216                 if (flashpos >= 0 && flashpos < state->colours)
1217                     grid[y*w+x] = flashpos;
1218             }
1219         }
1220     }
1221
1222     for (x = 0; x < w; x++) {
1223         for (y = 0; y < h; y++) {
1224             int pos = y*w+x;
1225             int tile;
1226
1227             if (grid[pos] == state->colours) {
1228                 tile = (solnmove << COLOUR_SHIFT) | SOLNNEXT;
1229             } else {
1230                 tile = (int)grid[pos] << COLOUR_SHIFT;
1231             }
1232
1233             if (x == 0 || grid[pos-1] != grid[pos])
1234                 tile |= BORDER_L;
1235             if (x==w-1 || grid[pos+1] != grid[pos])
1236                 tile |= BORDER_R;
1237             if (y == 0 || grid[pos-w] != grid[pos])
1238                 tile |= BORDER_U;
1239             if (y==h-1 || grid[pos+w] != grid[pos])
1240                 tile |= BORDER_D;
1241             if (x == 0 || y == 0 || grid[pos-w-1] != grid[pos])
1242                 tile |= CORNER_UL;
1243             if (x==w-1 || y == 0 || grid[pos-w+1] != grid[pos])
1244                 tile |= CORNER_UR;
1245             if (x == 0 || y==h-1 || grid[pos+w-1] != grid[pos])
1246                 tile |= CORNER_DL;
1247             if (x==w-1 || y==h-1 || grid[pos+w+1] != grid[pos])
1248                 tile |= CORNER_DR;
1249             if (ui->cursor_visible && ui->cx == x && ui->cy == y)
1250                 tile |= CURSOR;
1251
1252             if (flashframe >= 0 && ui->flash_type == DEFEAT && flashframe != 1)
1253                 tile |= BADFLASH;
1254
1255             if (ds->grid[pos] != tile) {
1256                 draw_tile(dr, ds, x, y, tile);
1257                 ds->grid[pos] = tile;
1258             }
1259         }
1260     }
1261
1262     sfree(grid);
1263
1264     {
1265         char status[255];
1266
1267         sprintf(status, "%s%d / %d moves",
1268                 (state->complete && state->moves <= state->movelimit ?
1269                  (state->cheated ? "Auto-solved. " : "COMPLETED! ") :
1270                  state->moves >= state->movelimit ? "FAILED! " :
1271                  state->cheated ? "Auto-solver used. " :
1272                  ""),
1273                 state->moves,
1274                 state->movelimit);
1275
1276         status_bar(dr, status);
1277     }
1278 }
1279
1280 static float game_anim_length(const game_state *oldstate,
1281                               const game_state *newstate, int dir, game_ui *ui)
1282 {
1283     return 0.0F;
1284 }
1285
1286 static int game_status(const game_state *state)
1287 {
1288     if (state->complete && state->moves <= state->movelimit) {
1289         return +1;                     /* victory! */
1290     } else if (state->moves >= state->movelimit) {
1291         return -1;                     /* defeat */
1292     } else {
1293         return 0;                      /* still playing */
1294     }
1295 }
1296
1297 static float game_flash_length(const game_state *oldstate,
1298                                const game_state *newstate, int dir, game_ui *ui)
1299 {
1300     if (dir == +1) {
1301         int old_status = game_status(oldstate);
1302         int new_status = game_status(newstate);
1303         if (old_status != new_status) {
1304             assert(old_status == 0);
1305
1306             if (new_status == +1) {
1307                 int frames = newstate->w + newstate->h + newstate->colours - 2;
1308                 ui->flash_type = VICTORY;
1309                 return VICTORY_FLASH_FRAME * frames;
1310             } else {
1311                 ui->flash_type = DEFEAT;
1312                 return DEFEAT_FLASH_FRAME * 3;
1313             }
1314         }
1315     }
1316     return 0.0F;
1317 }
1318
1319 static int game_timing_state(const game_state *state, game_ui *ui)
1320 {
1321     return TRUE;
1322 }
1323
1324 static void game_print_size(const game_params *params, float *x, float *y)
1325 {
1326 }
1327
1328 static void game_print(drawing *dr, const game_state *state, int tilesize)
1329 {
1330 }
1331
1332 #ifdef COMBINED
1333 #define thegame flood
1334 #endif
1335
1336 const struct game thegame = {
1337     "Flood", "games.flood", "flood",
1338     default_params,
1339     game_fetch_preset, NULL,
1340     decode_params,
1341     encode_params,
1342     free_params,
1343     dup_params,
1344     TRUE, game_configure, custom_params,
1345     validate_params,
1346     new_game_desc,
1347     validate_desc,
1348     new_game,
1349     dup_game,
1350     free_game,
1351     TRUE, solve_game,
1352     TRUE, game_can_format_as_text_now, game_text_format,
1353     new_ui,
1354     free_ui,
1355     encode_ui,
1356     decode_ui,
1357     game_changed_state,
1358     interpret_move,
1359     execute_move,
1360     PREFERRED_TILESIZE, game_compute_size, game_set_size,
1361     game_colours,
1362     game_new_drawstate,
1363     game_free_drawstate,
1364     game_redraw,
1365     game_anim_length,
1366     game_flash_length,
1367     game_status,
1368     FALSE, FALSE, game_print_size, game_print,
1369     TRUE,                              /* wants_statusbar */
1370     FALSE, game_timing_state,
1371     0,                                 /* flags */
1372 };