samegame.c

   1 /*
   2  * 'same game' -- try to remove all the coloured squares by
   3  *                selecting regions of contiguous colours.
   4  */
   5
   6 /*
   7  * TODO on grid generation:
   8  *
   9  *  - Generation speed could still be improved.
  10  *     * 15x10c3 is the only really difficult one of the existing
  11  *       presets. The others are all either small enough, or have
  12  *       the great flexibility given by four colours, that they
  13  *       don't take long at all.
  14  *     * I still suspect many problems arise from separate
  15  *       subareas. I wonder if we can also somehow prioritise left-
  16  *       or rightmost insertions so as to avoid area splitting at
  17  *       all where feasible? It's not easy, though, because the
  18  *       current shuffle-then-try-all-options approach to move
  19  *       choice doesn't leave room for `soft' probabilistic
  20  *       prioritisation: we either try all class A moves before any
  21  *       class B ones, or we don't.
  22  *
  23  *  - The current generation algorithm inserts exactly two squares
  24  *    at a time, with a single exception at the beginning of
  25  *    generation for grids of odd overall size. An obvious
  26  *    extension would be to permit larger inverse moves during
  27  *    generation.
  28  *     * this might reduce the number of failed generations by
  29  *       making the insertion algorithm more flexible
  30  *     * on the other hand, it would be significantly more complex
  31  *     * if I do this I'll need to take out the odd-subarea
  32  *       avoidance
  33  *     * a nice feature of the current algorithm is that the
  34  *       computer's `intended' solution always receives the minimum
  35  *       possible score, so that pretty much the player's entire
  36  *       score represents how much better they did than the
  37  *       computer.
  38  *
  39  *  - Is it possible we can _temporarily_ tolerate neighbouring
  40  *    squares of the same colour, until we've finished setting up
  41  *    our inverse move?
  42  *     * or perhaps even not choose the colour of our inserted
  43  *       region until we have finished placing it, and _then_ look
  44  *       at what colours border on it?
  45  *     * I don't think this is currently meaningful unless we're
  46  *       placing more than a domino at a time.
  47  *
  48  *  - possibly write out a full solution so that Solve can somehow
  49  *    show it step by step?
  50  *     * aux_info would have to encode the click points
  51  *     * solve_game() would have to encode not only those click
  52  *       points but also give a move string which reconstructed the
  53  *       initial state
  54  *     * the game_state would include a pointer to a solution move
  55  *       list, plus an index into that list
  56  *     * game_changed_state would auto-select the next move if
  57  *       handed a new state which had a solution move list active
  58  *     * execute_move, if passed such a state as input, would check
  59  *       to see whether the move being made was the same as the one
  60  *       stated by the solution, and if so would advance the move
  61  *       index. Failing that it would return a game_state without a
  62  *       solution move list active at all.
  63  */
  64
  65 #include <stdio.h>
  66 #include <stdlib.h>
  67 #include <string.h>
  68 #include <assert.h>
  69 #include <ctype.h>
  70 #include <math.h>
  71
  72 #include "puzzles.h"
  73
  74 #define TILE_INNER (ds->tileinner)
  75 #define TILE_GAP (ds->tilegap)
  76 #define TILE_SIZE (TILE_INNER + TILE_GAP)
  77 #define PREFERRED_TILE_SIZE 32
  78 #define BORDER (TILE_SIZE / 2)
  79 #define HIGHLIGHT_WIDTH 2
  80
  81 #define FLASH_FRAME 0.13F
  82
  83 #define COORD(x)  ( (x) * TILE_SIZE + BORDER )
  84 #define FROMCOORD(x)  ( ((x) - BORDER + TILE_SIZE) / TILE_SIZE - 1 )
  85
  86 #define X(state, i) ( (i) % (state)->params.w )
  87 #define Y(state, i) ( (i) / (state)->params.w )
  88 #define C(state, x, y) ( (y) * (state)->w + (x) )
  89
  90 enum {
  91     COL_BACKGROUND,
  92     COL_1, COL_2, COL_3, COL_4, COL_5, COL_6, COL_7, COL_8, COL_9,
  93     COL_IMPOSSIBLE, COL_SEL, COL_HIGHLIGHT, COL_LOWLIGHT,
  94     NCOLOURS
  95 };
  96
  97 /* scoresub is 1 or 2 (for (n-1)^2 or (n-2)^2) */
  98 struct game_params {
  99     int w, h, ncols, scoresub;
 100     int soluble;                       /* choose generation algorithm */
 101 };
 102
 103 /* These flags must be unique across all uses; in the game_state,
 104  * the game_ui, and the drawstate (as they all get combined in the
 105  * drawstate). */
 106 #define TILE_COLMASK    0x00ff
 107 #define TILE_SELECTED   0x0100 /* used in ui and drawstate */
 108 #define TILE_JOINRIGHT  0x0200 /* used in drawstate */
 109 #define TILE_JOINDOWN   0x0400 /* used in drawstate */
 110 #define TILE_JOINDIAG   0x0800 /* used in drawstate */
 111 #define TILE_HASSEL     0x1000 /* used in drawstate */
 112 #define TILE_IMPOSSIBLE 0x2000 /* used in drawstate */
 113
 114 #define TILE(gs,x,y) ((gs)->tiles[(gs)->params.w*(y)+(x)])
 115 #define COL(gs,x,y) (TILE(gs,x,y) & TILE_COLMASK)
 116 #define ISSEL(gs,x,y) (TILE(gs,x,y) & TILE_SELECTED)
 117
 118 #define SWAPTILE(gs,x1,y1,x2,y2) do {   \
 119     int t = TILE(gs,x1,y1);               \
 120     TILE(gs,x1,y1) = TILE(gs,x2,y2);      \
 121     TILE(gs,x2,y2) = t;                   \
 122 } while (0)
 123
 124 static int npoints(const game_params *params, int nsel)
 125 {
 126     int sdiff = nsel - params->scoresub;
 127     return (sdiff > 0) ? sdiff * sdiff : 0;
 128 }
 129
 130 struct game_state {
 131     struct game_params params;
 132     int n;
 133     int *tiles; /* colour only */
 134     int score;
 135     int complete, impossible;
 136 };
 137
 138 static game_params *default_params(void)
 139 {
 140     game_params *ret = snew(game_params);
 141     ret->w = 5;
 142     ret->h = 5;
 143     ret->ncols = 3;
 144     ret->scoresub = 2;
 145     ret->soluble = TRUE;
 146     return ret;
 147 }
 148
 149 static const struct game_params samegame_presets[] = {
 150     { 5, 5, 3, 2, TRUE },
 151     { 10, 5, 3, 2, TRUE },
 152 #ifdef SLOW_SYSTEM
 153     { 10, 10, 3, 2, TRUE },
 154 #else
 155     { 15, 10, 3, 2, TRUE },
 156 #endif
 157     { 15, 10, 4, 2, TRUE },
 158     { 20, 15, 4, 2, TRUE }
 159 };
 160
 161 static int game_fetch_preset(int i, char **name, game_params **params)
 162 {
 163     game_params *ret;
 164     char str[80];
 165
 166     if (i < 0 || i >= lenof(samegame_presets))
 167         return FALSE;
 168
 169     ret = snew(game_params);
 170     *ret = samegame_presets[i];
 171
 172     sprintf(str, "%dx%d, %d colours", ret->w, ret->h, ret->ncols);
 173
 174     *name = dupstr(str);
 175     *params = ret;
 176     return TRUE;
 177 }
 178
 179 static void free_params(game_params *params)
 180 {
 181     sfree(params);
 182 }
 183
 184 static game_params *dup_params(const game_params *params)
 185 {
 186     game_params *ret = snew(game_params);
 187     *ret = *params;                    /* structure copy */
 188     return ret;
 189 }
 190
 191 static void decode_params(game_params *params, char const *string)
 192 {
 193     char const *p = string;
 194
 195     params->w = atoi(p);
 196     while (*p && isdigit((unsigned char)*p)) p++;
 197     if (*p == 'x') {
 198         p++;
 199         params->h = atoi(p);
 200         while (*p && isdigit((unsigned char)*p)) p++;
 201     } else {
 202         params->h = params->w;
 203     }
 204     if (*p == 'c') {
 205         p++;
 206         params->ncols = atoi(p);
 207         while (*p && isdigit((unsigned char)*p)) p++;
 208     } else {
 209         params->ncols = 3;
 210     }
 211     if (*p == 's') {
 212         p++;
 213         params->scoresub = atoi(p);
 214         while (*p && isdigit((unsigned char)*p)) p++;
 215     } else {
 216         params->scoresub = 2;
 217     }
 218     if (*p == 'r') {
 219         p++;
 220         params->soluble = FALSE;
 221     }
 222 }
 223
 224 static char *encode_params(const game_params *params, int full)
 225 {
 226     char ret[80];
 227
 228     sprintf(ret, "%dx%dc%ds%d%s",
 229             params->w, params->h, params->ncols, params->scoresub,
 230             full && !params->soluble ? "r" : "");
 231     return dupstr(ret);
 232 }
 233
 234 static config_item *game_configure(const game_params *params)
 235 {
 236     config_item *ret;
 237     char buf[80];
 238
 239     ret = snewn(6, config_item);
 240
 241     ret[0].name = "Width";
 242     ret[0].type = C_STRING;
 243     sprintf(buf, "%d", params->w);
 244     ret[0].sval = dupstr(buf);
 245     ret[0].ival = 0;
 246
 247     ret[1].name = "Height";
 248     ret[1].type = C_STRING;
 249     sprintf(buf, "%d", params->h);
 250     ret[1].sval = dupstr(buf);
 251     ret[1].ival = 0;
 252
 253     ret[2].name = "No. of colours";
 254     ret[2].type = C_STRING;
 255     sprintf(buf, "%d", params->ncols);
 256     ret[2].sval = dupstr(buf);
 257     ret[2].ival = 0;
 258
 259     ret[3].name = "Scoring system";
 260     ret[3].type = C_CHOICES;
 261     ret[3].sval = ":(n-1)^2:(n-2)^2";
 262     ret[3].ival = params->scoresub-1;
 263
 264     ret[4].name = "Ensure solubility";
 265     ret[4].type = C_BOOLEAN;
 266     ret[4].sval = NULL;
 267     ret[4].ival = params->soluble;
 268
 269     ret[5].name = NULL;
 270     ret[5].type = C_END;
 271     ret[5].sval = NULL;
 272     ret[5].ival = 0;
 273
 274     return ret;
 275 }
 276
 277 static game_params *custom_params(const config_item *cfg)
 278 {
 279     game_params *ret = snew(game_params);
 280
 281     ret->w = atoi(cfg[0].sval);
 282     ret->h = atoi(cfg[1].sval);
 283     ret->ncols = atoi(cfg[2].sval);
 284     ret->scoresub = cfg[3].ival + 1;
 285     ret->soluble = cfg[4].ival;
 286
 287     return ret;
 288 }
 289
 290 static char *validate_params(const game_params *params, int full)
 291 {
 292     if (params->w < 1 || params->h < 1)
 293         return "Width and height must both be positive";
 294
 295     if (params->ncols > 9)
 296         return "Maximum of 9 colours";
 297
 298     if (params->soluble) {
 299         if (params->ncols < 3)
 300             return "Number of colours must be at least three";
 301         if (params->w * params->h <= 1)
 302             return "Grid area must be greater than 1";
 303     } else {
 304         if (params->ncols < 2)
 305             return "Number of colours must be at least three";
 306         /* ...and we must make sure we can generate at least 2 squares
 307          * of each colour so it's theoretically soluble. */
 308         if ((params->w * params->h) < (params->ncols * 2))
 309             return "Too many colours makes given grid size impossible";
 310     }
 311
 312     if ((params->scoresub < 1) || (params->scoresub > 2))
 313         return "Scoring system not recognised";
 314
 315     return NULL;
 316 }
 317
 318 /*
 319  * Guaranteed-soluble grid generator.
 320  */
 321 static void gen_grid(int w, int h, int nc, int *grid, random_state *rs)
 322 {
 323     int wh = w*h, tc = nc+1;
 324     int i, j, k, c, x, y, pos, n;
 325     int *list, *grid2;
 326     int ok, failures = 0;
 327
 328     /*
 329      * We'll use `list' to track the possible places to put our
 330      * next insertion. There are up to h places to insert in each
 331      * column: in a column of height n there are n+1 places because
 332      * we can insert at the very bottom or the very top, but a
 333      * column of height h can't have anything at all inserted in it
 334      * so we have up to h in each column. Likewise, with n columns
 335      * present there are n+1 places to fit a new one in between but
 336      * we can't insert a column if there are already w; so there
 337      * are a maximum of w new columns too. Total is wh + w.
 338      */
 339     list = snewn(wh + w, int);
 340     grid2 = snewn(wh, int);
 341
 342     do {
 343         /*
 344          * Start with two or three squares - depending on parity of w*h
 345          * - of a random colour.
 346          */
 347         for (i = 0; i < wh; i++)
 348             grid[i] = 0;
 349         j = 2 + (wh % 2);
 350         c = 1 + random_upto(rs, nc);
 351         if (j <= w) {
 352             for (i = 0; i < j; i++)
 353                 grid[(h-1)*w+i] = c;
 354         } else {
 355             assert(j <= h);
 356             for (i = 0; i < j; i++)
 357                 grid[(h-1-i)*w] = c;
 358         }
 359
 360         /*
 361          * Now repeatedly insert a two-square blob in the grid, of
 362          * whatever colour will go at the position we chose.
 363          */
 364         while (1) {
 365             n = 0;
 366
 367             /*
 368              * Build up a list of insertion points. Each point is
 369              * encoded as y*w+x; insertion points between columns are
 370              * encoded as h*w+x.
 371              */
 372
 373             if (grid[wh - 1] == 0) {
 374                 /*
 375                  * The final column is empty, so we can insert new
 376                  * columns.
 377                  */
 378                 for (i = 0; i < w; i++) {
 379                     list[n++] = wh + i;
 380                     if (grid[(h-1)*w + i] == 0)
 381                         break;
 382                 }
 383             }
 384
 385             /*
 386              * Now look for places to insert within columns.
 387              */
 388             for (i = 0; i < w; i++) {
 389                 if (grid[(h-1)*w+i] == 0)
 390                     break;                     /* no more columns */
 391
 392                 if (grid[i] != 0)
 393                     continue;          /* this column is full */
 394
 395                 for (j = h; j-- > 0 ;) {
 396                     list[n++] = j*w+i;
 397                     if (grid[j*w+i] == 0)
 398                         break;         /* this column is exhausted */
 399                 }
 400             }
 401
 402             if (n == 0)
 403                 break;                 /* we're done */
 404
 405 #ifdef GENERATION_DIAGNOSTICS
 406             printf("initial grid:\n");
 407             {
 408                 int x,y;
 409                 for (y = 0; y < h; y++) {
 410                     for (x = 0; x < w; x++) {
 411                         if (grid[y*w+x] == 0)
 412                             printf("-");
 413                         else
 414                             printf("%d", grid[y*w+x]);
 415                     }
 416                     printf("\n");
 417                 }
 418             }
 419 #endif
 420
 421             /*
 422              * Now go through the list one element at a time in
 423              * random order, and actually attempt to insert
 424              * something there.
 425              */
 426             while (n-- > 0) {
 427                 int dirs[4], ndirs, dir;
 428
 429                 i = random_upto(rs, n+1);
 430                 pos = list[i];
 431                 list[i] = list[n];
 432
 433                 x = pos % w;
 434                 y = pos / w;
 435
 436                 memcpy(grid2, grid, wh * sizeof(int));
 437
 438                 if (y == h) {
 439                     /*
 440                      * Insert a column at position x.
 441                      */
 442                     for (i = w-1; i > x; i--)
 443                         for (j = 0; j < h; j++)
 444                             grid2[j*w+i] = grid2[j*w+(i-1)];
 445                     /*
 446                      * Clear the new column.
 447                      */
 448                     for (j = 0; j < h; j++)
 449                         grid2[j*w+x] = 0;
 450                     /*
 451                      * Decrement y so that our first square is actually
 452                      * inserted _in_ the grid rather than just below it.
 453                      */
 454                     y--;
 455                 }
 456
 457                 /*
 458                  * Insert a square within column x at position y.
 459                  */
 460                 for (i = 0; i+1 <= y; i++)
 461                     grid2[i*w+x] = grid2[(i+1)*w+x];
 462
 463 #ifdef GENERATION_DIAGNOSTICS
 464                 printf("trying at n=%d (%d,%d)\n", n, x, y);
 465                 grid2[y*w+x] = tc;
 466                 {
 467                     int x,y;
 468                     for (y = 0; y < h; y++) {
 469                         for (x = 0; x < w; x++) {
 470                             if (grid2[y*w+x] == 0)
 471                                 printf("-");
 472                             else if (grid2[y*w+x] <= nc)
 473                                 printf("%d", grid2[y*w+x]);
 474                             else
 475                                 printf("*");
 476                         }
 477                         printf("\n");
 478                     }
 479                 }
 480 #endif
 481
 482                 /*
 483                  * Pick our square colour so that it doesn't match any
 484                  * of its neighbours.
 485                  */
 486                 {
 487                     int wrongcol[4], nwrong = 0;
 488
 489                     /*
 490                      * List the neighbouring colours.
 491                      */
 492                     if (x > 0)
 493                         wrongcol[nwrong++] = grid2[y*w+(x-1)];
 494                     if (x+1 < w)
 495                         wrongcol[nwrong++] = grid2[y*w+(x+1)];
 496                     if (y > 0)
 497                         wrongcol[nwrong++] = grid2[(y-1)*w+x];
 498                     if (y+1 < h)
 499                         wrongcol[nwrong++] = grid2[(y+1)*w+x];
 500
 501                     /*
 502                      * Eliminate duplicates. We can afford a shoddy
 503                      * algorithm here because the problem size is
 504                      * bounded.
 505                      */
 506                     for (i = j = 0 ;; i++) {
 507                         int pos = -1, min = 0;
 508                         if (j > 0)
 509                             min = wrongcol[j-1];
 510                         for (k = i; k < nwrong; k++)
 511                             if (wrongcol[k] > min &&
 512                                 (pos == -1 || wrongcol[k] < wrongcol[pos]))
 513                                 pos = k;
 514                         if (pos >= 0) {
 515                             int v = wrongcol[pos];
 516                             wrongcol[pos] = wrongcol[j];
 517                             wrongcol[j++] = v;
 518                         } else
 519                             break;
 520                     }
 521                     nwrong = j;
 522
 523                     /*
 524                      * If no colour will go here, stop trying.
 525                      */
 526                     if (nwrong == nc)
 527                         continue;
 528
 529                     /*
 530                      * Otherwise, pick a colour from the remaining
 531                      * ones.
 532                      */
 533                     c = 1 + random_upto(rs, nc - nwrong);
 534                     for (i = 0; i < nwrong; i++) {
 535                         if (c >= wrongcol[i])
 536                             c++;
 537                         else
 538                             break;
 539                     }
 540                 }
 541
 542                 /*
 543                  * Place the new square.
 544                  *
 545                  * Although I've _chosen_ the new region's colour
 546                  * (so that we can check adjacency), I'm going to
 547                  * actually place it as an invalid colour (tc)
 548                  * until I'm sure it's viable. This is so that I
 549                  * can conveniently check that I really have made a
 550                  * _valid_ inverse move later on.
 551                  */
 552 #ifdef GENERATION_DIAGNOSTICS
 553                 printf("picked colour %d\n", c);
 554 #endif
 555                 grid2[y*w+x] = tc;
 556
 557                 /*
 558                  * Now attempt to extend it in one of three ways: left,
 559                  * right or up.
 560                  */
 561                 ndirs = 0;
 562                 if (x > 0 &&
 563                     grid2[y*w+(x-1)] != c &&
 564                     grid2[x-1] == 0 &&
 565                     (y+1 >= h || grid2[(y+1)*w+(x-1)] != c) &&
 566                     (y+1 >= h || grid2[(y+1)*w+(x-1)] != 0) &&
 567                     (x <= 1 || grid2[y*w+(x-2)] != c))
 568                     dirs[ndirs++] = -1;    /* left */
 569                 if (x+1 < w &&
 570                     grid2[y*w+(x+1)] != c &&
 571                     grid2[x+1] == 0 &&
 572                     (y+1 >= h || grid2[(y+1)*w+(x+1)] != c) &&
 573                     (y+1 >= h || grid2[(y+1)*w+(x+1)] != 0) &&
 574                     (x+2 >= w || grid2[y*w+(x+2)] != c))
 575                     dirs[ndirs++] = +1;    /* right */
 576                 if (y > 0 &&
 577                     grid2[x] == 0 &&
 578                     (x <= 0 || grid2[(y-1)*w+(x-1)] != c) &&
 579                     (x+1 >= w || grid2[(y-1)*w+(x+1)] != c)) {
 580                     /*
 581                      * We add this possibility _twice_, so that the
 582                      * probability of placing a vertical domino is
 583                      * about the same as that of a horizontal. This
 584                      * should yield less bias in the generated
 585                      * grids.
 586                      */
 587                     dirs[ndirs++] = 0;     /* up */
 588                     dirs[ndirs++] = 0;     /* up */
 589                 }
 590
 591                 if (ndirs == 0)
 592                     continue;
 593
 594                 dir = dirs[random_upto(rs, ndirs)];
 595
 596 #ifdef GENERATION_DIAGNOSTICS
 597                 printf("picked dir %d\n", dir);
 598 #endif
 599
 600                 /*
 601                  * Insert a square within column (x+dir) at position y.
 602                  */
 603                 for (i = 0; i+1 <= y; i++)
 604                     grid2[i*w+x+dir] = grid2[(i+1)*w+x+dir];
 605                 grid2[y*w+x+dir] = tc;
 606
 607                 /*
 608                  * See if we've divided the remaining grid squares
 609                  * into sub-areas. If so, we need every sub-area to
 610                  * have an even area or we won't be able to
 611                  * complete generation.
 612                  *
 613                  * If the height is odd and not all columns are
 614                  * present, we can increase the area of a subarea
 615                  * by adding a new column in it, so in that
 616                  * situation we don't mind having as many odd
 617                  * subareas as there are spare columns.
 618                  *
 619                  * If the height is even, we can't fix it at all.
 620                  */
 621                 {
 622                     int nerrs = 0, nfix = 0;
 623                     k = 0;             /* current subarea size */
 624                     for (i = 0; i < w; i++) {
 625                         if (grid2[(h-1)*w+i] == 0) {
 626                             if (h % 2)
 627                                 nfix++;
 628                             continue;
 629                         }
 630                         for (j = 0; j < h && grid2[j*w+i] == 0; j++);
 631                         assert(j < h);
 632                         if (j == 0) {
 633                             /*
 634                              * End of previous subarea.
 635                              */
 636                             if (k % 2)
 637                                 nerrs++;
 638                             k = 0;
 639                         } else {
 640                             k += j;
 641                         }
 642                     }
 643                     if (k % 2)
 644                         nerrs++;
 645                     if (nerrs > nfix)
 646                         continue;      /* try a different placement */
 647                 }
 648
 649                 /*
 650                  * We've made a move. Verify that it is a valid
 651                  * move and that if made it would indeed yield the
 652                  * previous grid state. The criteria are:
 653                  *
 654                  *  (a) removing all the squares of colour tc (and
 655                  *      shuffling the columns up etc) from grid2
 656                  *      would yield grid
 657                  *  (b) no square of colour tc is adjacent to one
 658                  *      of colour c
 659                  *  (c) all the squares of colour tc form a single
 660                  *      connected component
 661                  *
 662                  * We verify the latter property at the same time
 663                  * as checking that removing all the tc squares
 664                  * would yield the previous grid. Then we colour
 665                  * the tc squares in colour c by breadth-first
 666                  * search, which conveniently permits us to test
 667                  * that they're all connected.
 668                  */
 669                 {
 670                     int x1, x2, y1, y2;
 671                     int ok = TRUE;
 672                     int fillstart = -1, ntc = 0;
 673
 674 #ifdef GENERATION_DIAGNOSTICS
 675                     {
 676                         int x,y;
 677                         printf("testing move (new, old):\n");
 678                         for (y = 0; y < h; y++) {
 679                             for (x = 0; x < w; x++) {
 680                                 if (grid2[y*w+x] == 0)
 681                                     printf("-");
 682                                 else if (grid2[y*w+x] <= nc)
 683                                     printf("%d", grid2[y*w+x]);
 684                                 else
 685                                     printf("*");
 686                             }
 687                             printf("   ");
 688                             for (x = 0; x < w; x++) {
 689                                 if (grid[y*w+x] == 0)
 690                                     printf("-");
 691                                 else
 692                                     printf("%d", grid[y*w+x]);
 693                             }
 694                             printf("\n");
 695                         }
 696                     }
 697 #endif
 698
 699                     for (x1 = x2 = 0; x2 < w; x2++) {
 700                         int usedcol = FALSE;
 701
 702                         for (y1 = y2 = h-1; y2 >= 0; y2--) {
 703                             if (grid2[y2*w+x2] == tc) {
 704                                 ntc++;
 705                                 if (fillstart == -1)
 706                                     fillstart = y2*w+x2;
 707                                 if ((y2+1 < h && grid2[(y2+1)*w+x2] == c) ||
 708                                     (y2-1 >= 0 && grid2[(y2-1)*w+x2] == c) ||
 709                                     (x2+1 < w && grid2[y2*w+x2+1] == c) ||
 710                                     (x2-1 >= 0 && grid2[y2*w+x2-1] == c)) {
 711 #ifdef GENERATION_DIAGNOSTICS
 712                                     printf("adjacency failure at %d,%d\n",
 713                                            x2, y2);
 714 #endif
 715                                     ok = FALSE;
 716                                 }
 717                                 continue;
 718                             }
 719                             if (grid2[y2*w+x2] == 0)
 720                                 break;
 721                             usedcol = TRUE;
 722                             if (grid2[y2*w+x2] != grid[y1*w+x1]) {
 723 #ifdef GENERATION_DIAGNOSTICS
 724                                 printf("matching failure at %d,%d vs %d,%d\n",
 725                                        x2, y2, x1, y1);
 726 #endif
 727                                 ok = FALSE;
 728                             }
 729                             y1--;
 730                         }
 731
 732                         /*
 733                          * If we've reached the top of the column
 734                          * in grid2, verify that we've also reached
 735                          * the top of the column in `grid'.
 736                          */
 737                         if (usedcol) {
 738                             while (y1 >= 0) {
 739                                 if (grid[y1*w+x1] != 0) {
 740 #ifdef GENERATION_DIAGNOSTICS
 741                                     printf("junk at column top (%d,%d)\n",
 742                                            x1, y1);
 743 #endif
 744                                     ok = FALSE;
 745                                 }
 746                                 y1--;
 747                             }
 748                         }
 749
 750                         if (!ok)
 751                             break;
 752
 753                         if (usedcol)
 754                             x1++;
 755                     }
 756
 757                     if (!ok) {
 758                         assert(!"This should never happen");
 759
 760                         /*
 761                          * If this game is compiled NDEBUG so that
 762                          * the assertion doesn't bring it to a
 763                          * crashing halt, the only thing we can do
 764                          * is to give up, loop round again, and
 765                          * hope to randomly avoid making whatever
 766                          * type of move just caused this failure.
 767                          */
 768                         continue;
 769                     }
 770
 771                     /*
 772                      * Now use bfs to fill in the tc section as
 773                      * colour c. We use `list' to store the set of
 774                      * squares we have to process.
 775                      */
 776                     i = j = 0;
 777                     assert(fillstart >= 0);
 778                     list[i++] = fillstart;
 779 #ifdef OUTPUT_SOLUTION
 780                     printf("M");
 781 #endif
 782                     while (j < i) {
 783                         k = list[j];
 784                         x = k % w;
 785                         y = k / w;
 786 #ifdef OUTPUT_SOLUTION
 787                         printf("%s%d", j ? "," : "", k);
 788 #endif
 789                         j++;
 790
 791                         assert(grid2[k] == tc);
 792                         grid2[k] = c;
 793
 794                         if (x > 0 && grid2[k-1] == tc)
 795                             list[i++] = k-1;
 796                         if (x+1 < w && grid2[k+1] == tc)
 797                             list[i++] = k+1;
 798                         if (y > 0 && grid2[k-w] == tc)
 799                             list[i++] = k-w;
 800                         if (y+1 < h && grid2[k+w] == tc)
 801                             list[i++] = k+w;
 802                     }
 803 #ifdef OUTPUT_SOLUTION
 804                     printf("\n");
 805 #endif
 806
 807                     /*
 808                      * Check that we've filled the same number of
 809                      * tc squares as we originally found.
 810                      */
 811                     assert(j == ntc);
 812                 }
 813
 814                 memcpy(grid, grid2, wh * sizeof(int));
 815
 816                 break;                 /* done it! */
 817             }
 818
 819 #ifdef GENERATION_DIAGNOSTICS
 820             {
 821                 int x,y;
 822                 printf("n=%d\n", n);
 823                 for (y = 0; y < h; y++) {
 824                     for (x = 0; x < w; x++) {
 825                         if (grid[y*w+x] == 0)
 826                             printf("-");
 827                         else
 828                             printf("%d", grid[y*w+x]);
 829                     }
 830                     printf("\n");
 831                 }
 832             }
 833 #endif
 834
 835             if (n < 0)
 836                 break;
 837         }
 838
 839         ok = TRUE;
 840         for (i = 0; i < wh; i++)
 841             if (grid[i] == 0) {
 842                 ok = FALSE;
 843                 failures++;
 844 #if defined GENERATION_DIAGNOSTICS || defined SHOW_INCOMPLETE
 845                 {
 846                     int x,y;
 847                     printf("incomplete grid:\n");
 848                     for (y = 0; y < h; y++) {
 849                         for (x = 0; x < w; x++) {
 850                             if (grid[y*w+x] == 0)
 851                                 printf("-");
 852                             else
 853                                 printf("%d", grid[y*w+x]);
 854                         }
 855                         printf("\n");
 856                     }
 857                 }
 858 #endif
 859                 break;
 860             }
 861
 862     } while (!ok);
 863
 864 #if defined GENERATION_DIAGNOSTICS || defined COUNT_FAILURES
 865     printf("%d failures\n", failures);
 866 #endif
 867 #ifdef GENERATION_DIAGNOSTICS
 868     {
 869         int x,y;
 870         printf("final grid:\n");
 871         for (y = 0; y < h; y++) {
 872             for (x = 0; x < w; x++) {
 873                 printf("%d", grid[y*w+x]);
 874             }
 875             printf("\n");
 876         }
 877     }
 878 #endif
 879
 880     sfree(grid2);
 881     sfree(list);
 882 }
 883
 884 /*
 885  * Not-guaranteed-soluble grid generator; kept as a legacy, and in
 886  * case someone finds the slightly odd quality of the guaranteed-
 887  * soluble grids to be aesthetically displeasing or finds its CPU
 888  * utilisation to be excessive.
 889  */
 890 static void gen_grid_random(int w, int h, int nc, int *grid, random_state *rs)
 891 {
 892     int i, j, c;
 893     int n = w * h;
 894
 895     for (i = 0; i < n; i++)
 896         grid[i] = 0;
 897
 898     /*
 899      * Our sole concession to not gratuitously generating insoluble
 900      * grids is to ensure we have at least two of every colour.
 901      */
 902     for (c = 1; c <= nc; c++) {
 903         for (j = 0; j < 2; j++) {
 904             do {
 905                 i = (int)random_upto(rs, n);
 906             } while (grid[i] != 0);
 907             grid[i] = c;
 908         }
 909     }
 910
 911     /*
 912      * Fill in the rest of the grid at random.
 913      */
 914     for (i = 0; i < n; i++) {
 915         if (grid[i] == 0)
 916             grid[i] = (int)random_upto(rs, nc)+1;
 917     }
 918 }
 919
 920 static char *new_game_desc(const game_params *params, random_state *rs,
 921                            char **aux, int interactive)
 922 {
 923     char *ret;
 924     int n, i, retlen, *tiles;
 925
 926     n = params->w * params->h;
 927     tiles = snewn(n, int);
 928
 929     if (params->soluble)
 930         gen_grid(params->w, params->h, params->ncols, tiles, rs);
 931     else
 932         gen_grid_random(params->w, params->h, params->ncols, tiles, rs);
 933
 934     ret = NULL;
 935     retlen = 0;
 936     for (i = 0; i < n; i++) {
 937         char buf[80];
 938         int k;
 939
 940         k = sprintf(buf, "%d,", tiles[i]);
 941         ret = sresize(ret, retlen + k + 1, char);
 942         strcpy(ret + retlen, buf);
 943         retlen += k;
 944     }
 945     ret[retlen-1] = '\0'; /* delete last comma */
 946
 947     sfree(tiles);
 948     return ret;
 949 }
 950
 951 static char *validate_desc(const game_params *params, const char *desc)
 952 {
 953     int area = params->w * params->h, i;
 954     const char *p = desc;
 955
 956     for (i = 0; i < area; i++) {
 957         const char *q = p;
 958         int n;
 959
 960         if (!isdigit((unsigned char)*p))
 961             return "Not enough numbers in string";
 962         while (isdigit((unsigned char)*p)) p++;
 963
 964         if (i < area-1 && *p != ',')
 965             return "Expected comma after number";
 966         else if (i == area-1 && *p)
 967             return "Excess junk at end of string";
 968
 969         n = atoi(q);
 970         if (n < 0 || n > params->ncols)
 971             return "Colour out of range";
 972
 973         if (*p) p++; /* eat comma */
 974     }
 975     return NULL;
 976 }
 977
 978 static game_state *new_game(midend *me, const game_params *params,
 979                             const char *desc)
 980 {
 981     game_state *state = snew(game_state);
 982     const char *p = desc;
 983     int i;
 984
 985     state->params = *params; /* struct copy */
 986     state->n = state->params.w * state->params.h;
 987     state->tiles = snewn(state->n, int);
 988
 989     for (i = 0; i < state->n; i++) {
 990         assert(*p);
 991         state->tiles[i] = atoi(p);
 992         while (*p && *p != ',')
 993             p++;
 994         if (*p) p++;                   /* eat comma */
 995     }
 996     state->complete = state->impossible = 0;
 997     state->score = 0;
 998
 999     return state;
1000 }
1001
1002 static game_state *dup_game(const game_state *state)
1003 {
1004     game_state *ret = snew(game_state);
1005
1006     *ret = *state; /* structure copy, except... */
1007
1008     ret->tiles = snewn(state->n, int);
1009     memcpy(ret->tiles, state->tiles, state->n * sizeof(int));
1010
1011     return ret;
1012 }
1013
1014 static void free_game(game_state *state)
1015 {
1016     sfree(state->tiles);
1017     sfree(state);
1018 }
1019
1020 static char *solve_game(const game_state *state, const game_state *currstate,
1021                         const char *aux, char **error)
1022 {
1023     return NULL;
1024 }
1025
1026 static int game_can_format_as_text_now(const game_params *params)
1027 {
1028     return TRUE;
1029 }
1030
1031 static char *game_text_format(const game_state *state)
1032 {
1033     char *ret, *p;
1034     int x, y, maxlen;
1035
1036     maxlen = state->params.h * (state->params.w + 1);
1037     ret = snewn(maxlen+1, char);
1038     p = ret;
1039
1040     for (y = 0; y < state->params.h; y++) {
1041         for (x = 0; x < state->params.w; x++) {
1042             int t = TILE(state,x,y);
1043             if (t <= 0)      *p++ = ' ';
1044             else if (t < 10) *p++ = '0'+t;
1045             else             *p++ = 'a'+(t-10);
1046         }
1047         *p++ = '\n';
1048     }
1049     assert(p - ret == maxlen);
1050     *p = '\0';
1051     return ret;
1052 }
1053
1054 struct game_ui {
1055     struct game_params params;
1056     int *tiles; /* selected-ness only */
1057     int nselected;
1058     int xsel, ysel, displaysel;
1059 };
1060
1061 static game_ui *new_ui(const game_state *state)
1062 {
1063     game_ui *ui = snew(game_ui);
1064
1065     ui->params = state->params; /* structure copy */
1066     ui->tiles = snewn(state->n, int);
1067     memset(ui->tiles, 0, state->n*sizeof(int));
1068     ui->nselected = 0;
1069
1070     ui->xsel = ui->ysel = ui->displaysel = 0;
1071
1072     return ui;
1073 }
1074
1075 static void free_ui(game_ui *ui)
1076 {
1077     sfree(ui->tiles);
1078     sfree(ui);
1079 }
1080
1081 static char *encode_ui(const game_ui *ui)
1082 {
1083     return NULL;
1084 }
1085
1086 static void decode_ui(game_ui *ui, const char *encoding)
1087 {
1088 }
1089
1090 static void sel_clear(game_ui *ui, const game_state *state)
1091 {
1092     int i;
1093
1094     for (i = 0; i < state->n; i++)
1095         ui->tiles[i] &= ~TILE_SELECTED;
1096     ui->nselected = 0;
1097 }
1098
1099
1100 static void game_changed_state(game_ui *ui, const game_state *oldstate,
1101                                const game_state *newstate)
1102 {
1103     sel_clear(ui, newstate);
1104
1105     /*
1106      * If the game state has just changed into an unplayable one
1107      * (either completed or impossible), we vanish the keyboard-
1108      * control cursor.
1109      */
1110     if (newstate->complete || newstate->impossible)
1111         ui->displaysel = 0;
1112 }
1113
1114 static char *sel_movedesc(game_ui *ui, const game_state *state)
1115 {
1116     int i;
1117     char *ret, *sep, buf[80];
1118     int retlen, retsize;
1119
1120     retsize = 256;
1121     ret = snewn(retsize, char);
1122     retlen = 0;
1123     ret[retlen++] = 'M';
1124     sep = "";
1125
1126     for (i = 0; i < state->n; i++) {
1127         if (ui->tiles[i] & TILE_SELECTED) {
1128             sprintf(buf, "%s%d", sep, i);
1129             sep = ",";
1130             if (retlen + (int)strlen(buf) >= retsize) {
1131                 retsize = retlen + strlen(buf) + 256;
1132                 ret = sresize(ret, retsize, char);
1133             }
1134             strcpy(ret + retlen, buf);
1135             retlen += strlen(buf);
1136
1137             ui->tiles[i] &= ~TILE_SELECTED;
1138         }
1139     }
1140     ui->nselected = 0;
1141
1142     assert(retlen < retsize);
1143     ret[retlen++] = '\0';
1144     return sresize(ret, retlen, char);
1145 }
1146
1147 static void sel_expand(game_ui *ui, const game_state *state, int tx, int ty)
1148 {
1149     int ns = 1, nadded, x, y, c;
1150
1151     TILE(ui,tx,ty) |= TILE_SELECTED;
1152     do {
1153         nadded = 0;
1154
1155         for (x = 0; x < state->params.w; x++) {
1156             for (y = 0; y < state->params.h; y++) {
1157                 if (x == tx && y == ty) continue;
1158                 if (ISSEL(ui,x,y)) continue;
1159
1160                 c = COL(state,x,y);
1161                 if ((x > 0) &&
1162                     ISSEL(ui,x-1,y) && COL(state,x-1,y) == c) {
1163                     TILE(ui,x,y) |= TILE_SELECTED;
1164                     nadded++;
1165                     continue;
1166                 }
1167
1168                 if ((x+1 < state->params.w) &&
1169                     ISSEL(ui,x+1,y) && COL(state,x+1,y) == c) {
1170                     TILE(ui,x,y) |= TILE_SELECTED;
1171                     nadded++;
1172                     continue;
1173                 }
1174
1175                 if ((y > 0) &&
1176                     ISSEL(ui,x,y-1) && COL(state,x,y-1) == c) {
1177                     TILE(ui,x,y) |= TILE_SELECTED;
1178                     nadded++;
1179                     continue;
1180                 }
1181
1182                 if ((y+1 < state->params.h) &&
1183                     ISSEL(ui,x,y+1) && COL(state,x,y+1) == c) {
1184                     TILE(ui,x,y) |= TILE_SELECTED;
1185                     nadded++;
1186                     continue;
1187                 }
1188             }
1189         }
1190         ns += nadded;
1191     } while (nadded > 0);
1192
1193     if (ns > 1) {
1194         ui->nselected = ns;
1195     } else {
1196         sel_clear(ui, state);
1197     }
1198 }
1199
1200 static int sg_emptycol(game_state *ret, int x)
1201 {
1202     int y;
1203     for (y = 0; y < ret->params.h; y++) {
1204         if (COL(ret,x,y)) return 0;
1205     }
1206     return 1;
1207 }
1208
1209
1210 static void sg_snuggle(game_state *ret)
1211 {
1212     int x,y, ndone;
1213
1214     /* make all unsupported tiles fall down. */
1215     do {
1216         ndone = 0;
1217         for (x = 0; x < ret->params.w; x++) {
1218             for (y = ret->params.h-1; y > 0; y--) {
1219                 if (COL(ret,x,y) != 0) continue;
1220                 if (COL(ret,x,y-1) != 0) {
1221                     SWAPTILE(ret,x,y,x,y-1);
1222                     ndone++;
1223                 }
1224             }
1225         }
1226     } while (ndone);
1227
1228     /* shuffle all columns as far left as they can go. */
1229     do {
1230         ndone = 0;
1231         for (x = 0; x < ret->params.w-1; x++) {
1232             if (sg_emptycol(ret,x) && !sg_emptycol(ret,x+1)) {
1233                 ndone++;
1234                 for (y = 0; y < ret->params.h; y++) {
1235                     SWAPTILE(ret,x,y,x+1,y);
1236                 }
1237             }
1238         }
1239     } while (ndone);
1240 }
1241
1242 static void sg_check(game_state *ret)
1243 {
1244     int x,y, complete = 1, impossible = 1;
1245
1246     for (x = 0; x < ret->params.w; x++) {
1247         for (y = 0; y < ret->params.h; y++) {
1248             if (COL(ret,x,y) == 0)
1249                 continue;
1250             complete = 0;
1251             if (x+1 < ret->params.w) {
1252                 if (COL(ret,x,y) == COL(ret,x+1,y))
1253                     impossible = 0;
1254             }
1255             if (y+1 < ret->params.h) {
1256                 if (COL(ret,x,y) == COL(ret,x,y+1))
1257                     impossible = 0;
1258             }
1259         }
1260     }
1261     ret->complete = complete;
1262     ret->impossible = impossible;
1263 }
1264
1265 struct game_drawstate {
1266     int started, bgcolour;
1267     int tileinner, tilegap;
1268     int *tiles; /* contains colour and SELECTED. */
1269 };
1270
1271 static char *interpret_move(const game_state *state, game_ui *ui,
1272                             const game_drawstate *ds,
1273                             int x, int y, int button)
1274 {
1275     int tx, ty;
1276     char *ret = "";
1277
1278     ui->displaysel = 0;
1279
1280     if (button == RIGHT_BUTTON || button == LEFT_BUTTON) {
1281         tx = FROMCOORD(x); ty= FROMCOORD(y);
1282     } else if (IS_CURSOR_MOVE(button)) {
1283         int dx = 0, dy = 0;
1284         ui->displaysel = 1;
1285         dx = (button == CURSOR_LEFT) ? -1 : ((button == CURSOR_RIGHT) ? +1 : 0);
1286         dy = (button == CURSOR_DOWN) ? +1 : ((button == CURSOR_UP)    ? -1 : 0);
1287         ui->xsel = (ui->xsel + state->params.w + dx) % state->params.w;
1288         ui->ysel = (ui->ysel + state->params.h + dy) % state->params.h;
1289         return ret;
1290     } else if (IS_CURSOR_SELECT(button)) {
1291         ui->displaysel = 1;
1292         tx = ui->xsel;
1293         ty = ui->ysel;
1294     } else
1295         return NULL;
1296
1297     if (tx < 0 || tx >= state->params.w || ty < 0 || ty >= state->params.h)
1298         return NULL;
1299     if (COL(state, tx, ty) == 0) return NULL;
1300
1301     if (ISSEL(ui,tx,ty)) {
1302         if (button == RIGHT_BUTTON || button == CURSOR_SELECT2)
1303             sel_clear(ui, state);
1304         else
1305             ret = sel_movedesc(ui, state);
1306     } else {
1307         sel_clear(ui, state); /* might be no-op */
1308         sel_expand(ui, state, tx, ty);
1309     }
1310
1311     return ret;
1312 }
1313
1314 static game_state *execute_move(const game_state *from, const char *move)
1315 {
1316     int i, n;
1317     game_state *ret;
1318
1319     if (move[0] == 'M') {
1320         ret = dup_game(from);
1321
1322         n = 0;
1323         move++;
1324
1325         while (*move) {
1326             i = atoi(move);
1327             if (i < 0 || i >= ret->n) {
1328                 free_game(ret);
1329                 return NULL;
1330             }
1331             n++;
1332             ret->tiles[i] = 0;
1333
1334             while (*move && isdigit((unsigned char)*move)) move++;
1335             if (*move == ',') move++;
1336         }
1337
1338         ret->score += npoints(&ret->params, n);
1339
1340         sg_snuggle(ret); /* shifts blanks down and to the left */
1341         sg_check(ret);   /* checks for completeness or impossibility */
1342
1343         return ret;
1344     } else
1345         return NULL;                   /* couldn't parse move string */
1346 }
1347
1348 /* ----------------------------------------------------------------------
1349  * Drawing routines.
1350  */
1351
1352 static void game_set_size(drawing *dr, game_drawstate *ds,
1353                           const game_params *params, int tilesize)
1354 {
1355     ds->tilegap = 2;
1356     ds->tileinner = tilesize - ds->tilegap;
1357 }
1358
1359 static void game_compute_size(const game_params *params, int tilesize,
1360                               int *x, int *y)
1361 {
1362     /* Ick: fake up tile size variables for macro expansion purposes */
1363     game_drawstate ads, *ds = &ads;
1364     game_set_size(NULL, ds, params, tilesize);
1365
1366     *x = TILE_SIZE * params->w + 2 * BORDER - TILE_GAP;
1367     *y = TILE_SIZE * params->h + 2 * BORDER - TILE_GAP;
1368 }
1369
1370 static float *game_colours(frontend *fe, int *ncolours)
1371 {
1372     float *ret = snewn(3 * NCOLOURS, float);
1373
1374     frontend_default_colour(fe, &ret[COL_BACKGROUND * 3]);
1375
1376     ret[COL_1 * 3 + 0] = 0.0F;
1377     ret[COL_1 * 3 + 1] = 0.0F;
1378     ret[COL_1 * 3 + 2] = 1.0F;
1379
1380     ret[COL_2 * 3 + 0] = 0.0F;
1381     ret[COL_2 * 3 + 1] = 0.5F;
1382     ret[COL_2 * 3 + 2] = 0.0F;
1383
1384     ret[COL_3 * 3 + 0] = 1.0F;
1385     ret[COL_3 * 3 + 1] = 0.0F;
1386     ret[COL_3 * 3 + 2] = 0.0F;
1387
1388     ret[COL_4 * 3 + 0] = 1.0F;
1389     ret[COL_4 * 3 + 1] = 1.0F;
1390     ret[COL_4 * 3 + 2] = 0.0F;
1391
1392     ret[COL_5 * 3 + 0] = 1.0F;
1393     ret[COL_5 * 3 + 1] = 0.0F;
1394     ret[COL_5 * 3 + 2] = 1.0F;
1395
1396     ret[COL_6 * 3 + 0] = 0.0F;
1397     ret[COL_6 * 3 + 1] = 1.0F;
1398     ret[COL_6 * 3 + 2] = 1.0F;
1399
1400     ret[COL_7 * 3 + 0] = 0.5F;
1401     ret[COL_7 * 3 + 1] = 0.5F;
1402     ret[COL_7 * 3 + 2] = 1.0F;
1403
1404     ret[COL_8 * 3 + 0] = 0.5F;
1405     ret[COL_8 * 3 + 1] = 1.0F;
1406     ret[COL_8 * 3 + 2] = 0.5F;
1407
1408     ret[COL_9 * 3 + 0] = 1.0F;
1409     ret[COL_9 * 3 + 1] = 0.5F;
1410     ret[COL_9 * 3 + 2] = 0.5F;
1411
1412     ret[COL_IMPOSSIBLE * 3 + 0] = 0.0F;
1413     ret[COL_IMPOSSIBLE * 3 + 1] = 0.0F;
1414     ret[COL_IMPOSSIBLE * 3 + 2] = 0.0F;
1415
1416     ret[COL_SEL * 3 + 0] = 1.0F;
1417     ret[COL_SEL * 3 + 1] = 1.0F;
1418     ret[COL_SEL * 3 + 2] = 1.0F;
1419
1420     ret[COL_HIGHLIGHT * 3 + 0] = 1.0F;
1421     ret[COL_HIGHLIGHT * 3 + 1] = 1.0F;
1422     ret[COL_HIGHLIGHT * 3 + 2] = 1.0F;
1423
1424     ret[COL_LOWLIGHT * 3 + 0] = ret[COL_BACKGROUND * 3 + 0] * 2.0F / 3.0F;
1425     ret[COL_LOWLIGHT * 3 + 1] = ret[COL_BACKGROUND * 3 + 1] * 2.0F / 3.0F;
1426     ret[COL_LOWLIGHT * 3 + 2] = ret[COL_BACKGROUND * 3 + 2] * 2.0F / 3.0F;
1427
1428     *ncolours = NCOLOURS;
1429     return ret;
1430 }
1431
1432 static game_drawstate *game_new_drawstate(drawing *dr, const game_state *state)
1433 {
1434     struct game_drawstate *ds = snew(struct game_drawstate);
1435     int i;
1436
1437     ds->started = 0;
1438     ds->tileinner = ds->tilegap = 0;   /* not decided yet */
1439     ds->tiles = snewn(state->n, int);
1440     ds->bgcolour = -1;
1441     for (i = 0; i < state->n; i++)
1442         ds->tiles[i] = -1;
1443
1444     return ds;
1445 }
1446
1447 static void game_free_drawstate(drawing *dr, game_drawstate *ds)
1448 {
1449     sfree(ds->tiles);
1450     sfree(ds);
1451 }
1452
1453 /* Drawing routing for the tile at (x,y) is responsible for drawing
1454  * itself and the gaps to its right and below. If we're the same colour
1455  * as the tile to our right, then we fill in the gap; ditto below, and if
1456  * both then we fill the teeny tiny square in the corner as well.
1457  */
1458
1459 static void tile_redraw(drawing *dr, game_drawstate *ds,
1460                         int x, int y, int dright, int dbelow,
1461                         int tile, int bgcolour)
1462 {
1463     int outer = bgcolour, inner = outer, col = tile & TILE_COLMASK;
1464
1465     if (col) {
1466         if (tile & TILE_IMPOSSIBLE) {
1467             outer = col;
1468             inner = COL_IMPOSSIBLE;
1469         } else if (tile & TILE_SELECTED) {
1470             outer = COL_SEL;
1471             inner = col;
1472         } else {
1473             outer = inner = col;
1474         }
1475     }
1476     draw_rect(dr, COORD(x), COORD(y), TILE_INNER, TILE_INNER, outer);
1477     draw_rect(dr, COORD(x)+TILE_INNER/4, COORD(y)+TILE_INNER/4,
1478               TILE_INNER/2, TILE_INNER/2, inner);
1479
1480     if (dright)
1481         draw_rect(dr, COORD(x)+TILE_INNER, COORD(y), TILE_GAP, TILE_INNER,
1482                   (tile & TILE_JOINRIGHT) ? outer : bgcolour);
1483     if (dbelow)
1484         draw_rect(dr, COORD(x), COORD(y)+TILE_INNER, TILE_INNER, TILE_GAP,
1485                   (tile & TILE_JOINDOWN) ? outer : bgcolour);
1486     if (dright && dbelow)
1487         draw_rect(dr, COORD(x)+TILE_INNER, COORD(y)+TILE_INNER, TILE_GAP, TILE_GAP,
1488                   (tile & TILE_JOINDIAG) ? outer : bgcolour);
1489
1490     if (tile & TILE_HASSEL) {
1491         int sx = COORD(x)+2, sy = COORD(y)+2, ssz = TILE_INNER-5;
1492         int scol = (outer == COL_SEL) ? COL_LOWLIGHT : COL_HIGHLIGHT;
1493         draw_line(dr, sx,     sy,     sx+ssz, sy,     scol);
1494         draw_line(dr, sx+ssz, sy,     sx+ssz, sy+ssz, scol);
1495         draw_line(dr, sx+ssz, sy+ssz, sx,     sy+ssz, scol);
1496         draw_line(dr, sx,     sy+ssz, sx,     sy,     scol);
1497     }
1498
1499     draw_update(dr, COORD(x), COORD(y), TILE_SIZE, TILE_SIZE);
1500 }
1501
1502 static void game_redraw(drawing *dr, game_drawstate *ds,
1503                         const game_state *oldstate, const game_state *state,
1504                         int dir, const game_ui *ui,
1505                         float animtime, float flashtime)
1506 {
1507     int bgcolour, x, y;
1508
1509     /* This was entirely cloned from fifteen.c; it should probably be
1510      * moved into some generic 'draw-recessed-rectangle' utility fn. */
1511     if (!ds->started) {
1512         int coords[10];
1513
1514         draw_rect(dr, 0, 0,
1515                   TILE_SIZE * state->params.w + 2 * BORDER,
1516                   TILE_SIZE * state->params.h + 2 * BORDER, COL_BACKGROUND);
1517         draw_update(dr, 0, 0,
1518                     TILE_SIZE * state->params.w + 2 * BORDER,
1519                     TILE_SIZE * state->params.h + 2 * BORDER);
1520
1521         /*
1522          * Recessed area containing the whole puzzle.
1523          */
1524         coords[0] = COORD(state->params.w) + HIGHLIGHT_WIDTH - 1 - TILE_GAP;
1525         coords[1] = COORD(state->params.h) + HIGHLIGHT_WIDTH - 1 - TILE_GAP;
1526         coords[2] = COORD(state->params.w) + HIGHLIGHT_WIDTH - 1 - TILE_GAP;
1527         coords[3] = COORD(0) - HIGHLIGHT_WIDTH;
1528         coords[4] = coords[2] - TILE_SIZE;
1529         coords[5] = coords[3] + TILE_SIZE;
1530         coords[8] = COORD(0) - HIGHLIGHT_WIDTH;
1531         coords[9] = COORD(state->params.h) + HIGHLIGHT_WIDTH - 1 - TILE_GAP;
1532         coords[6] = coords[8] + TILE_SIZE;
1533         coords[7] = coords[9] - TILE_SIZE;
1534         draw_polygon(dr, coords, 5, COL_HIGHLIGHT, COL_HIGHLIGHT);
1535
1536         coords[1] = COORD(0) - HIGHLIGHT_WIDTH;
1537         coords[0] = COORD(0) - HIGHLIGHT_WIDTH;
1538         draw_polygon(dr, coords, 5, COL_LOWLIGHT, COL_LOWLIGHT);
1539
1540         ds->started = 1;
1541     }
1542
1543     if (flashtime > 0.0) {
1544         int frame = (int)(flashtime / FLASH_FRAME);
1545         bgcolour = (frame % 2 ? COL_LOWLIGHT : COL_HIGHLIGHT);
1546     } else
1547         bgcolour = COL_BACKGROUND;
1548
1549     for (x = 0; x < state->params.w; x++) {
1550         for (y = 0; y < state->params.h; y++) {
1551             int i = (state->params.w * y) + x;
1552             int col = COL(state,x,y), tile = col;
1553             int dright = (x+1 < state->params.w);
1554             int dbelow = (y+1 < state->params.h);
1555
1556             tile |= ISSEL(ui,x,y);
1557             if (state->impossible)
1558                 tile |= TILE_IMPOSSIBLE;
1559             if (dright && COL(state,x+1,y) == col)
1560                 tile |= TILE_JOINRIGHT;
1561             if (dbelow && COL(state,x,y+1) == col)
1562                 tile |= TILE_JOINDOWN;
1563             if ((tile & TILE_JOINRIGHT) && (tile & TILE_JOINDOWN) &&
1564                 COL(state,x+1,y+1) == col)
1565                 tile |= TILE_JOINDIAG;
1566
1567             if (ui->displaysel && ui->xsel == x && ui->ysel == y)
1568                 tile |= TILE_HASSEL;
1569
1570             /* For now we're never expecting oldstate at all (because we have
1571              * no animation); when we do we might well want to be looking
1572              * at the tile colours from oldstate, not state. */
1573             if ((oldstate && COL(oldstate,x,y) != col) ||
1574                 (ds->bgcolour != bgcolour) ||
1575                 (tile != ds->tiles[i])) {
1576                 tile_redraw(dr, ds, x, y, dright, dbelow, tile, bgcolour);
1577                 ds->tiles[i] = tile;
1578             }
1579         }
1580     }
1581     ds->bgcolour = bgcolour;
1582
1583     {
1584         char status[255], score[80];
1585
1586         sprintf(score, "Score: %d", state->score);
1587
1588         if (state->complete)
1589             sprintf(status, "COMPLETE! %s", score);
1590         else if (state->impossible)
1591             sprintf(status, "Cannot move! %s", score);
1592         else if (ui->nselected)
1593             sprintf(status, "%s  Selected: %d (%d)",
1594                     score, ui->nselected, npoints(&state->params, ui->nselected));
1595         else
1596             sprintf(status, "%s", score);
1597         status_bar(dr, status);
1598     }
1599 }
1600
1601 static float game_anim_length(const game_state *oldstate,
1602                               const game_state *newstate, int dir, game_ui *ui)
1603 {
1604     return 0.0F;
1605 }
1606
1607 static float game_flash_length(const game_state *oldstate,
1608                                const game_state *newstate, int dir, game_ui *ui)
1609 {
1610     if ((!oldstate->complete && newstate->complete) ||
1611         (!oldstate->impossible && newstate->impossible))
1612         return 2 * FLASH_FRAME;
1613     else
1614         return 0.0F;
1615 }
1616
1617 static int game_status(const game_state *state)
1618 {
1619     /*
1620      * Dead-end situations are assumed to be rescuable by Undo, so we
1621      * don't bother to identify them and return -1.
1622      */
1623     return state->complete ? +1 : 0;
1624 }
1625
1626 static int game_timing_state(const game_state *state, game_ui *ui)
1627 {
1628     return TRUE;
1629 }
1630
1631 static void game_print_size(const game_params *params, float *x, float *y)
1632 {
1633 }
1634
1635 static void game_print(drawing *dr, const game_state *state, int tilesize)
1636 {
1637 }
1638
1639 #ifdef COMBINED
1640 #define thegame samegame
1641 #endif
1642
1643 const struct game thegame = {
1644     "Same Game", "games.samegame", "samegame",
1645     default_params,
1646     game_fetch_preset,
1647     decode_params,
1648     encode_params,
1649     free_params,
1650     dup_params,
1651     TRUE, game_configure, custom_params,
1652     validate_params,
1653     new_game_desc,
1654     validate_desc,
1655     new_game,
1656     dup_game,
1657     free_game,
1658     FALSE, solve_game,
1659     TRUE, game_can_format_as_text_now, game_text_format,
1660     new_ui,
1661     free_ui,
1662     encode_ui,
1663     decode_ui,
1664     game_changed_state,
1665     interpret_move,
1666     execute_move,
1667     PREFERRED_TILE_SIZE, game_compute_size, game_set_size,
1668     game_colours,
1669     game_new_drawstate,
1670     game_free_drawstate,
1671     game_redraw,
1672     game_anim_length,
1673     game_flash_length,
1674     game_status,
1675     FALSE, FALSE, game_print_size, game_print,
1676     TRUE,                              /* wants_statusbar */
1677     FALSE, game_timing_state,
1678     0,                                 /* flags */
1679 };