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(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(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(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(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(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(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(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(game_params *params, char *desc)
 952 {
 953     int area = params->w * params->h, i;
 954     char *p = desc;
 955
 956     for (i = 0; i < area; i++) {
 957         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_data *me, game_params *params, char *desc)
 979 {
 980     game_state *state = snew(game_state);
 981     char *p = desc;
 982     int i;
 983
 984     state->params = *params; /* struct copy */
 985     state->n = state->params.w * state->params.h;
 986     state->tiles = snewn(state->n, int);
 987
 988     for (i = 0; i < state->n; i++) {
 989         assert(*p);
 990         state->tiles[i] = atoi(p);
 991         while (*p && *p != ',')
 992             p++;
 993         if (*p) p++;                   /* eat comma */
 994     }
 995     state->complete = state->impossible = 0;
 996     state->score = 0;
 997
 998     return state;
 999 }
1000
1001 static game_state *dup_game(game_state *state)
1002 {
1003     game_state *ret = snew(game_state);
1004
1005     *ret = *state; /* structure copy, except... */
1006
1007     ret->tiles = snewn(state->n, int);
1008     memcpy(ret->tiles, state->tiles, state->n * sizeof(int));
1009
1010     return ret;
1011 }
1012
1013 static void free_game(game_state *state)
1014 {
1015     sfree(state->tiles);
1016     sfree(state);
1017 }
1018
1019 static char *solve_game(game_state *state, game_state *currstate,
1020                         char *aux, char **error)
1021 {
1022     return NULL;
1023 }
1024
1025 static char *game_text_format(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(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(game_ui *ui)
1076 {
1077     return NULL;
1078 }
1079
1080 static void decode_ui(game_ui *ui, char *encoding)
1081 {
1082 }
1083
1084 static void sel_clear(game_ui *ui, 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, game_state *oldstate,
1095                                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, 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 + 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, 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(game_state *state, game_ui *ui, game_drawstate *ds,
1266                             int x, int y, int button)
1267 {
1268     int tx, ty;
1269     char *ret = "";
1270
1271     ui->displaysel = 0;
1272
1273     if (button == RIGHT_BUTTON || button == LEFT_BUTTON) {
1274         tx = FROMCOORD(x); ty= FROMCOORD(y);
1275     } else if (button == CURSOR_UP || button == CURSOR_DOWN ||
1276                button == CURSOR_LEFT || button == CURSOR_RIGHT) {
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 (button == CURSOR_SELECT || button == ' ' || button == '\r' ||
1285                button == '\n') {
1286         ui->displaysel = 1;
1287         tx = ui->xsel;
1288         ty = ui->ysel;
1289     } else
1290         return NULL;
1291
1292     if (tx < 0 || tx >= state->params.w || ty < 0 || ty >= state->params.h)
1293         return NULL;
1294     if (COL(state, tx, ty) == 0) return NULL;
1295
1296     if (ISSEL(ui,tx,ty)) {
1297         if (button == RIGHT_BUTTON)
1298             sel_clear(ui, state);
1299         else
1300             ret = sel_movedesc(ui, state);
1301     } else {
1302         sel_clear(ui, state); /* might be no-op */
1303         sel_expand(ui, state, tx, ty);
1304     }
1305
1306     return ret;
1307 }
1308
1309 static game_state *execute_move(game_state *from, char *move)
1310 {
1311     int i, n;
1312     game_state *ret;
1313
1314     if (move[0] == 'M') {
1315         ret = dup_game(from);
1316
1317         n = 0;
1318         move++;
1319
1320         while (*move) {
1321             i = atoi(move);
1322             if (i < 0 || i >= ret->n) {
1323                 free_game(ret);
1324                 return NULL;
1325             }
1326             n++;
1327             ret->tiles[i] = 0;
1328
1329             while (*move && isdigit((unsigned char)*move)) move++;
1330             if (*move == ',') move++;
1331         }
1332
1333         ret->score += npoints(&ret->params, n);
1334
1335         sg_snuggle(ret); /* shifts blanks down and to the left */
1336         sg_check(ret);   /* checks for completeness or impossibility */
1337
1338         return ret;
1339     } else
1340         return NULL;                   /* couldn't parse move string */
1341 }
1342
1343 /* ----------------------------------------------------------------------
1344  * Drawing routines.
1345  */
1346
1347 static void game_set_size(game_drawstate *ds, game_params *params,
1348                           int tilesize)
1349 {
1350     ds->tilegap = 2;
1351     ds->tileinner = tilesize - ds->tilegap;
1352 }
1353
1354 static void game_compute_size(game_params *params, int tilesize,
1355                               int *x, int *y)
1356 {
1357     /* Ick: fake up tile size variables for macro expansion purposes */
1358     game_drawstate ads, *ds = &ads;
1359     game_set_size(ds, params, tilesize);
1360
1361     *x = TILE_SIZE * params->w + 2 * BORDER - TILE_GAP;
1362     *y = TILE_SIZE * params->h + 2 * BORDER - TILE_GAP;
1363 }
1364
1365 static float *game_colours(frontend *fe, game_state *state, int *ncolours)
1366 {
1367     float *ret = snewn(3 * NCOLOURS, float);
1368
1369     frontend_default_colour(fe, &ret[COL_BACKGROUND * 3]);
1370
1371     ret[COL_1 * 3 + 0] = 0.0F;
1372     ret[COL_1 * 3 + 1] = 0.0F;
1373     ret[COL_1 * 3 + 2] = 1.0F;
1374
1375     ret[COL_2 * 3 + 0] = 0.0F;
1376     ret[COL_2 * 3 + 1] = 0.5F;
1377     ret[COL_2 * 3 + 2] = 0.0F;
1378
1379     ret[COL_3 * 3 + 0] = 1.0F;
1380     ret[COL_3 * 3 + 1] = 0.0F;
1381     ret[COL_3 * 3 + 2] = 0.0F;
1382
1383     ret[COL_4 * 3 + 0] = 1.0F;
1384     ret[COL_4 * 3 + 1] = 1.0F;
1385     ret[COL_4 * 3 + 2] = 0.0F;
1386
1387     ret[COL_5 * 3 + 0] = 1.0F;
1388     ret[COL_5 * 3 + 1] = 0.0F;
1389     ret[COL_5 * 3 + 2] = 1.0F;
1390
1391     ret[COL_6 * 3 + 0] = 0.0F;
1392     ret[COL_6 * 3 + 1] = 1.0F;
1393     ret[COL_6 * 3 + 2] = 1.0F;
1394
1395     ret[COL_7 * 3 + 0] = 0.5F;
1396     ret[COL_7 * 3 + 1] = 0.5F;
1397     ret[COL_7 * 3 + 2] = 1.0F;
1398
1399     ret[COL_8 * 3 + 0] = 0.5F;
1400     ret[COL_8 * 3 + 1] = 1.0F;
1401     ret[COL_8 * 3 + 2] = 0.5F;
1402
1403     ret[COL_9 * 3 + 0] = 1.0F;
1404     ret[COL_9 * 3 + 1] = 0.5F;
1405     ret[COL_9 * 3 + 2] = 0.5F;
1406
1407     ret[COL_IMPOSSIBLE * 3 + 0] = 0.0F;
1408     ret[COL_IMPOSSIBLE * 3 + 1] = 0.0F;
1409     ret[COL_IMPOSSIBLE * 3 + 2] = 0.0F;
1410
1411     ret[COL_SEL * 3 + 0] = 1.0F;
1412     ret[COL_SEL * 3 + 1] = 1.0F;
1413     ret[COL_SEL * 3 + 2] = 1.0F;
1414
1415     ret[COL_HIGHLIGHT * 3 + 0] = 1.0F;
1416     ret[COL_HIGHLIGHT * 3 + 1] = 1.0F;
1417     ret[COL_HIGHLIGHT * 3 + 2] = 1.0F;
1418
1419     ret[COL_LOWLIGHT * 3 + 0] = ret[COL_BACKGROUND * 3 + 0] * 2.0 / 3.0;
1420     ret[COL_LOWLIGHT * 3 + 1] = ret[COL_BACKGROUND * 3 + 1] * 2.0 / 3.0;
1421     ret[COL_LOWLIGHT * 3 + 2] = ret[COL_BACKGROUND * 3 + 2] * 2.0 / 3.0;
1422
1423     *ncolours = NCOLOURS;
1424     return ret;
1425 }
1426
1427 static game_drawstate *game_new_drawstate(game_state *state)
1428 {
1429     struct game_drawstate *ds = snew(struct game_drawstate);
1430     int i;
1431
1432     ds->started = 0;
1433     ds->tileinner = ds->tilegap = 0;   /* not decided yet */
1434     ds->tiles = snewn(state->n, int);
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(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(frontend *fe, 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(fe, COORD(x), COORD(y), TILE_INNER, TILE_INNER, outer);
1471     draw_rect(fe, 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(fe, COORD(x)+TILE_INNER, COORD(y), TILE_GAP, TILE_INNER,
1476                   (tile & TILE_JOINRIGHT) ? outer : bgcolour);
1477     if (dbelow)
1478         draw_rect(fe, COORD(x), COORD(y)+TILE_INNER, TILE_INNER, TILE_GAP,
1479                   (tile & TILE_JOINDOWN) ? outer : bgcolour);
1480     if (dright && dbelow)
1481         draw_rect(fe, 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(fe, sx,     sy,     sx+ssz, sy,     scol);
1488         draw_line(fe, sx+ssz, sy,     sx+ssz, sy+ssz, scol);
1489         draw_line(fe, sx+ssz, sy+ssz, sx,     sy+ssz, scol);
1490         draw_line(fe, sx,     sy+ssz, sx,     sy,     scol);
1491     }
1492
1493     draw_update(fe, COORD(x), COORD(y), TILE_SIZE, TILE_SIZE);
1494 }
1495
1496 static void game_redraw(frontend *fe, game_drawstate *ds, game_state *oldstate,
1497                         game_state *state, int dir, game_ui *ui,
1498                         float animtime, float flashtime)
1499 {
1500     int bgcolour, x, y;
1501
1502     /* This was entirely cloned from fifteen.c; it should probably be
1503      * moved into some generic 'draw-recessed-rectangle' utility fn. */
1504     if (!ds->started) {
1505         int coords[10];
1506
1507         draw_rect(fe, 0, 0,
1508                   TILE_SIZE * state->params.w + 2 * BORDER,
1509                   TILE_SIZE * state->params.h + 2 * BORDER, COL_BACKGROUND);
1510         draw_update(fe, 0, 0,
1511                     TILE_SIZE * state->params.w + 2 * BORDER,
1512                     TILE_SIZE * state->params.h + 2 * BORDER);
1513
1514         /*
1515          * Recessed area containing the whole puzzle.
1516          */
1517         coords[0] = COORD(state->params.w) + HIGHLIGHT_WIDTH - 1 - TILE_GAP;
1518         coords[1] = COORD(state->params.h) + HIGHLIGHT_WIDTH - 1 - TILE_GAP;
1519         coords[2] = COORD(state->params.w) + HIGHLIGHT_WIDTH - 1 - TILE_GAP;
1520         coords[3] = COORD(0) - HIGHLIGHT_WIDTH;
1521         coords[4] = coords[2] - TILE_SIZE;
1522         coords[5] = coords[3] + TILE_SIZE;
1523         coords[8] = COORD(0) - HIGHLIGHT_WIDTH;
1524         coords[9] = COORD(state->params.h) + HIGHLIGHT_WIDTH - 1 - TILE_GAP;
1525         coords[6] = coords[8] + TILE_SIZE;
1526         coords[7] = coords[9] - TILE_SIZE;
1527         draw_polygon(fe, coords, 5, COL_HIGHLIGHT, COL_HIGHLIGHT);
1528
1529         coords[1] = COORD(0) - HIGHLIGHT_WIDTH;
1530         coords[0] = COORD(0) - HIGHLIGHT_WIDTH;
1531         draw_polygon(fe, coords, 5, COL_LOWLIGHT, COL_LOWLIGHT);
1532
1533         ds->started = 1;
1534     }
1535
1536     if (flashtime > 0.0) {
1537         int frame = (int)(flashtime / FLASH_FRAME);
1538         bgcolour = (frame % 2 ? COL_LOWLIGHT : COL_HIGHLIGHT);
1539     } else
1540         bgcolour = COL_BACKGROUND;
1541
1542     for (x = 0; x < state->params.w; x++) {
1543         for (y = 0; y < state->params.h; y++) {
1544             int i = (state->params.w * y) + x;
1545             int col = COL(state,x,y), tile = col;
1546             int dright = (x+1 < state->params.w);
1547             int dbelow = (y+1 < state->params.h);
1548
1549             tile |= ISSEL(ui,x,y);
1550             if (state->impossible)
1551                 tile |= TILE_IMPOSSIBLE;
1552             if (dright && COL(state,x+1,y) == col)
1553                 tile |= TILE_JOINRIGHT;
1554             if (dbelow && COL(state,x,y+1) == col)
1555                 tile |= TILE_JOINDOWN;
1556             if ((tile & TILE_JOINRIGHT) && (tile & TILE_JOINDOWN) &&
1557                 COL(state,x+1,y+1) == col)
1558                 tile |= TILE_JOINDIAG;
1559
1560             if (ui->displaysel && ui->xsel == x && ui->ysel == y)
1561                 tile |= TILE_HASSEL;
1562
1563             /* For now we're never expecting oldstate at all (because we have
1564              * no animation); when we do we might well want to be looking
1565              * at the tile colours from oldstate, not state. */
1566             if ((oldstate && COL(oldstate,x,y) != col) ||
1567                 (flashtime > 0.0) ||
1568                 (ds->bgcolour != bgcolour) ||
1569                 (tile != ds->tiles[i])) {
1570                 tile_redraw(fe, 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(fe, status);
1592     }
1593 }
1594
1595 static float game_anim_length(game_state *oldstate, game_state *newstate,
1596                               int dir, game_ui *ui)
1597 {
1598     return 0.0F;
1599 }
1600
1601 static float game_flash_length(game_state *oldstate, game_state *newstate,
1602                                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_wants_statusbar(void)
1612 {
1613     return TRUE;
1614 }
1615
1616 static int game_timing_state(game_state *state, game_ui *ui)
1617 {
1618     return TRUE;
1619 }
1620
1621 #ifdef COMBINED
1622 #define thegame samegame
1623 #endif
1624
1625 const struct game thegame = {
1626     "Same Game", "games.samegame",
1627     default_params,
1628     game_fetch_preset,
1629     decode_params,
1630     encode_params,
1631     free_params,
1632     dup_params,
1633     TRUE, game_configure, custom_params,
1634     validate_params,
1635     new_game_desc,
1636     validate_desc,
1637     new_game,
1638     dup_game,
1639     free_game,
1640     FALSE, solve_game,
1641     TRUE, game_text_format,
1642     new_ui,
1643     free_ui,
1644     encode_ui,
1645     decode_ui,
1646     game_changed_state,
1647     interpret_move,
1648     execute_move,
1649     PREFERRED_TILE_SIZE, game_compute_size, game_set_size,
1650     game_colours,
1651     game_new_drawstate,
1652     game_free_drawstate,
1653     game_redraw,
1654     game_anim_length,
1655     game_flash_length,
1656     game_wants_statusbar,
1657     FALSE, game_timing_state,
1658     0,                                 /* mouse_priorities */
1659 };