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