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 const 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 const 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, const 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, buf[80];
1112     const char *sep;
1113     int retlen, retsize;
1114
1115     retsize = 256;
1116     ret = snewn(retsize, char);
1117     retlen = 0;
1118     ret[retlen++] = 'M';
1119     sep = "";
1120
1121     for (i = 0; i < state->n; i++) {
1122         if (ui->tiles[i] & TILE_SELECTED) {
1123             sprintf(buf, "%s%d", sep, i);
1124             sep = ",";
1125             if (retlen + (int)strlen(buf) >= retsize) {
1126                 retsize = retlen + strlen(buf) + 256;
1127                 ret = sresize(ret, retsize, char);
1128             }
1129             strcpy(ret + retlen, buf);
1130             retlen += strlen(buf);
1131
1132             ui->tiles[i] &= ~TILE_SELECTED;
1133         }
1134     }
1135     ui->nselected = 0;
1136
1137     assert(retlen < retsize);
1138     ret[retlen++] = '\0';
1139     return sresize(ret, retlen, char);
1140 }
1141
1142 static void sel_expand(game_ui *ui, const game_state *state, int tx, int ty)
1143 {
1144     int ns = 1, nadded, x, y, c;
1145
1146     TILE(ui,tx,ty) |= TILE_SELECTED;
1147     do {
1148         nadded = 0;
1149
1150         for (x = 0; x < state->params.w; x++) {
1151             for (y = 0; y < state->params.h; y++) {
1152                 if (x == tx && y == ty) continue;
1153                 if (ISSEL(ui,x,y)) continue;
1154
1155                 c = COL(state,x,y);
1156                 if ((x > 0) &&
1157                     ISSEL(ui,x-1,y) && COL(state,x-1,y) == c) {
1158                     TILE(ui,x,y) |= TILE_SELECTED;
1159                     nadded++;
1160                     continue;
1161                 }
1162
1163                 if ((x+1 < state->params.w) &&
1164                     ISSEL(ui,x+1,y) && COL(state,x+1,y) == c) {
1165                     TILE(ui,x,y) |= TILE_SELECTED;
1166                     nadded++;
1167                     continue;
1168                 }
1169
1170                 if ((y > 0) &&
1171                     ISSEL(ui,x,y-1) && COL(state,x,y-1) == c) {
1172                     TILE(ui,x,y) |= TILE_SELECTED;
1173                     nadded++;
1174                     continue;
1175                 }
1176
1177                 if ((y+1 < state->params.h) &&
1178                     ISSEL(ui,x,y+1) && COL(state,x,y+1) == c) {
1179                     TILE(ui,x,y) |= TILE_SELECTED;
1180                     nadded++;
1181                     continue;
1182                 }
1183             }
1184         }
1185         ns += nadded;
1186     } while (nadded > 0);
1187
1188     if (ns > 1) {
1189         ui->nselected = ns;
1190     } else {
1191         sel_clear(ui, state);
1192     }
1193 }
1194
1195 static int sg_emptycol(game_state *ret, int x)
1196 {
1197     int y;
1198     for (y = 0; y < ret->params.h; y++) {
1199         if (COL(ret,x,y)) return 0;
1200     }
1201     return 1;
1202 }
1203
1204
1205 static void sg_snuggle(game_state *ret)
1206 {
1207     int x,y, ndone;
1208
1209     /* make all unsupported tiles fall down. */
1210     do {
1211         ndone = 0;
1212         for (x = 0; x < ret->params.w; x++) {
1213             for (y = ret->params.h-1; y > 0; y--) {
1214                 if (COL(ret,x,y) != 0) continue;
1215                 if (COL(ret,x,y-1) != 0) {
1216                     SWAPTILE(ret,x,y,x,y-1);
1217                     ndone++;
1218                 }
1219             }
1220         }
1221     } while (ndone);
1222
1223     /* shuffle all columns as far left as they can go. */
1224     do {
1225         ndone = 0;
1226         for (x = 0; x < ret->params.w-1; x++) {
1227             if (sg_emptycol(ret,x) && !sg_emptycol(ret,x+1)) {
1228                 ndone++;
1229                 for (y = 0; y < ret->params.h; y++) {
1230                     SWAPTILE(ret,x,y,x+1,y);
1231                 }
1232             }
1233         }
1234     } while (ndone);
1235 }
1236
1237 static void sg_check(game_state *ret)
1238 {
1239     int x,y, complete = 1, impossible = 1;
1240
1241     for (x = 0; x < ret->params.w; x++) {
1242         for (y = 0; y < ret->params.h; y++) {
1243             if (COL(ret,x,y) == 0)
1244                 continue;
1245             complete = 0;
1246             if (x+1 < ret->params.w) {
1247                 if (COL(ret,x,y) == COL(ret,x+1,y))
1248                     impossible = 0;
1249             }
1250             if (y+1 < ret->params.h) {
1251                 if (COL(ret,x,y) == COL(ret,x,y+1))
1252                     impossible = 0;
1253             }
1254         }
1255     }
1256     ret->complete = complete;
1257     ret->impossible = impossible;
1258 }
1259
1260 struct game_drawstate {
1261     int started, bgcolour;
1262     int tileinner, tilegap;
1263     int *tiles; /* contains colour and SELECTED. */
1264 };
1265
1266 static char *interpret_move(const game_state *state, game_ui *ui,
1267                             const game_drawstate *ds,
1268                             int x, int y, int button)
1269 {
1270     int tx, ty;
1271     char *ret = UI_UPDATE;
1272
1273     ui->displaysel = 0;
1274
1275     if (button == RIGHT_BUTTON || button == LEFT_BUTTON) {
1276         tx = FROMCOORD(x); ty= FROMCOORD(y);
1277     } else if (IS_CURSOR_MOVE(button)) {
1278         int dx = 0, dy = 0;
1279         ui->displaysel = 1;
1280         dx = (button == CURSOR_LEFT) ? -1 : ((button == CURSOR_RIGHT) ? +1 : 0);
1281         dy = (button == CURSOR_DOWN) ? +1 : ((button == CURSOR_UP)    ? -1 : 0);
1282         ui->xsel = (ui->xsel + state->params.w + dx) % state->params.w;
1283         ui->ysel = (ui->ysel + state->params.h + dy) % state->params.h;
1284         return ret;
1285     } else if (IS_CURSOR_SELECT(button)) {
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 || button == CURSOR_SELECT2)
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(const game_state *from, const 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(drawing *dr, game_drawstate *ds,
1348                           const game_params *params, int tilesize)
1349 {
1350     ds->tilegap = 2;
1351     ds->tileinner = tilesize - ds->tilegap;
1352 }
1353
1354 static void game_compute_size(const 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(NULL, 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, 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.0F / 3.0F;
1420     ret[COL_LOWLIGHT * 3 + 1] = ret[COL_BACKGROUND * 3 + 1] * 2.0F / 3.0F;
1421     ret[COL_LOWLIGHT * 3 + 2] = ret[COL_BACKGROUND * 3 + 2] * 2.0F / 3.0F;
1422
1423     *ncolours = NCOLOURS;
1424     return ret;
1425 }
1426
1427 static game_drawstate *game_new_drawstate(drawing *dr, const 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     ds->bgcolour = -1;
1436     for (i = 0; i < state->n; i++)
1437         ds->tiles[i] = -1;
1438
1439     return ds;
1440 }
1441
1442 static void game_free_drawstate(drawing *dr, game_drawstate *ds)
1443 {
1444     sfree(ds->tiles);
1445     sfree(ds);
1446 }
1447
1448 /* Drawing routing for the tile at (x,y) is responsible for drawing
1449  * itself and the gaps to its right and below. If we're the same colour
1450  * as the tile to our right, then we fill in the gap; ditto below, and if
1451  * both then we fill the teeny tiny square in the corner as well.
1452  */
1453
1454 static void tile_redraw(drawing *dr, game_drawstate *ds,
1455                         int x, int y, int dright, int dbelow,
1456                         int tile, int bgcolour)
1457 {
1458     int outer = bgcolour, inner = outer, col = tile & TILE_COLMASK;
1459
1460     if (col) {
1461         if (tile & TILE_IMPOSSIBLE) {
1462             outer = col;
1463             inner = COL_IMPOSSIBLE;
1464         } else if (tile & TILE_SELECTED) {
1465             outer = COL_SEL;
1466             inner = col;
1467         } else {
1468             outer = inner = col;
1469         }
1470     }
1471     draw_rect(dr, COORD(x), COORD(y), TILE_INNER, TILE_INNER, outer);
1472     draw_rect(dr, COORD(x)+TILE_INNER/4, COORD(y)+TILE_INNER/4,
1473               TILE_INNER/2, TILE_INNER/2, inner);
1474
1475     if (dright)
1476         draw_rect(dr, COORD(x)+TILE_INNER, COORD(y), TILE_GAP, TILE_INNER,
1477                   (tile & TILE_JOINRIGHT) ? outer : bgcolour);
1478     if (dbelow)
1479         draw_rect(dr, COORD(x), COORD(y)+TILE_INNER, TILE_INNER, TILE_GAP,
1480                   (tile & TILE_JOINDOWN) ? outer : bgcolour);
1481     if (dright && dbelow)
1482         draw_rect(dr, COORD(x)+TILE_INNER, COORD(y)+TILE_INNER, TILE_GAP, TILE_GAP,
1483                   (tile & TILE_JOINDIAG) ? outer : bgcolour);
1484
1485     if (tile & TILE_HASSEL) {
1486         int sx = COORD(x)+2, sy = COORD(y)+2, ssz = TILE_INNER-5;
1487         int scol = (outer == COL_SEL) ? COL_LOWLIGHT : COL_HIGHLIGHT;
1488         draw_line(dr, sx,     sy,     sx+ssz, sy,     scol);
1489         draw_line(dr, sx+ssz, sy,     sx+ssz, sy+ssz, scol);
1490         draw_line(dr, sx+ssz, sy+ssz, sx,     sy+ssz, scol);
1491         draw_line(dr, sx,     sy+ssz, sx,     sy,     scol);
1492     }
1493
1494     draw_update(dr, COORD(x), COORD(y), TILE_SIZE, TILE_SIZE);
1495 }
1496
1497 static void game_redraw(drawing *dr, game_drawstate *ds,
1498                         const game_state *oldstate, const game_state *state,
1499                         int dir, const game_ui *ui,
1500                         float animtime, float flashtime)
1501 {
1502     int bgcolour, x, y;
1503
1504     /* This was entirely cloned from fifteen.c; it should probably be
1505      * moved into some generic 'draw-recessed-rectangle' utility fn. */
1506     if (!ds->started) {
1507         int coords[10];
1508
1509         draw_rect(dr, 0, 0,
1510                   TILE_SIZE * state->params.w + 2 * BORDER,
1511                   TILE_SIZE * state->params.h + 2 * BORDER, COL_BACKGROUND);
1512         draw_update(dr, 0, 0,
1513                     TILE_SIZE * state->params.w + 2 * BORDER,
1514                     TILE_SIZE * state->params.h + 2 * BORDER);
1515
1516         /*
1517          * Recessed area containing the whole puzzle.
1518          */
1519         coords[0] = COORD(state->params.w) + HIGHLIGHT_WIDTH - 1 - TILE_GAP;
1520         coords[1] = COORD(state->params.h) + HIGHLIGHT_WIDTH - 1 - TILE_GAP;
1521         coords[2] = COORD(state->params.w) + HIGHLIGHT_WIDTH - 1 - TILE_GAP;
1522         coords[3] = COORD(0) - HIGHLIGHT_WIDTH;
1523         coords[4] = coords[2] - TILE_SIZE;
1524         coords[5] = coords[3] + TILE_SIZE;
1525         coords[8] = COORD(0) - HIGHLIGHT_WIDTH;
1526         coords[9] = COORD(state->params.h) + HIGHLIGHT_WIDTH - 1 - TILE_GAP;
1527         coords[6] = coords[8] + TILE_SIZE;
1528         coords[7] = coords[9] - TILE_SIZE;
1529         draw_polygon(dr, coords, 5, COL_HIGHLIGHT, COL_HIGHLIGHT);
1530
1531         coords[1] = COORD(0) - HIGHLIGHT_WIDTH;
1532         coords[0] = COORD(0) - HIGHLIGHT_WIDTH;
1533         draw_polygon(dr, coords, 5, COL_LOWLIGHT, COL_LOWLIGHT);
1534
1535         ds->started = 1;
1536     }
1537
1538     if (flashtime > 0.0) {
1539         int frame = (int)(flashtime / FLASH_FRAME);
1540         bgcolour = (frame % 2 ? COL_LOWLIGHT : COL_HIGHLIGHT);
1541     } else
1542         bgcolour = COL_BACKGROUND;
1543
1544     for (x = 0; x < state->params.w; x++) {
1545         for (y = 0; y < state->params.h; y++) {
1546             int i = (state->params.w * y) + x;
1547             int col = COL(state,x,y), tile = col;
1548             int dright = (x+1 < state->params.w);
1549             int dbelow = (y+1 < state->params.h);
1550
1551             tile |= ISSEL(ui,x,y);
1552             if (state->impossible)
1553                 tile |= TILE_IMPOSSIBLE;
1554             if (dright && COL(state,x+1,y) == col)
1555                 tile |= TILE_JOINRIGHT;
1556             if (dbelow && COL(state,x,y+1) == col)
1557                 tile |= TILE_JOINDOWN;
1558             if ((tile & TILE_JOINRIGHT) && (tile & TILE_JOINDOWN) &&
1559                 COL(state,x+1,y+1) == col)
1560                 tile |= TILE_JOINDIAG;
1561
1562             if (ui->displaysel && ui->xsel == x && ui->ysel == y)
1563                 tile |= TILE_HASSEL;
1564
1565             /* For now we're never expecting oldstate at all (because we have
1566              * no animation); when we do we might well want to be looking
1567              * at the tile colours from oldstate, not state. */
1568             if ((oldstate && COL(oldstate,x,y) != col) ||
1569                 (ds->bgcolour != bgcolour) ||
1570                 (tile != ds->tiles[i])) {
1571                 tile_redraw(dr, ds, x, y, dright, dbelow, tile, bgcolour);
1572                 ds->tiles[i] = tile;
1573             }
1574         }
1575     }
1576     ds->bgcolour = bgcolour;
1577
1578     {
1579         char status[255], score[80];
1580
1581         sprintf(score, "Score: %d", state->score);
1582
1583         if (state->complete)
1584             sprintf(status, "COMPLETE! %s", score);
1585         else if (state->impossible)
1586             sprintf(status, "Cannot move! %s", score);
1587         else if (ui->nselected)
1588             sprintf(status, "%s  Selected: %d (%d)",
1589                     score, ui->nselected, npoints(&state->params, ui->nselected));
1590         else
1591             sprintf(status, "%s", score);
1592         status_bar(dr, status);
1593     }
1594 }
1595
1596 static float game_anim_length(const game_state *oldstate,
1597                               const game_state *newstate, int dir, game_ui *ui)
1598 {
1599     return 0.0F;
1600 }
1601
1602 static float game_flash_length(const game_state *oldstate,
1603                                const game_state *newstate, int dir, game_ui *ui)
1604 {
1605     if ((!oldstate->complete && newstate->complete) ||
1606         (!oldstate->impossible && newstate->impossible))
1607         return 2 * FLASH_FRAME;
1608     else
1609         return 0.0F;
1610 }
1611
1612 static int game_status(const game_state *state)
1613 {
1614     /*
1615      * Dead-end situations are assumed to be rescuable by Undo, so we
1616      * don't bother to identify them and return -1.
1617      */
1618     return state->complete ? +1 : 0;
1619 }
1620
1621 static int game_timing_state(const game_state *state, game_ui *ui)
1622 {
1623     return TRUE;
1624 }
1625
1626 static void game_print_size(const game_params *params, float *x, float *y)
1627 {
1628 }
1629
1630 static void game_print(drawing *dr, const game_state *state, int tilesize)
1631 {
1632 }
1633
1634 #ifdef COMBINED
1635 #define thegame samegame
1636 #endif
1637
1638 const struct game thegame = {
1639     "Same Game", "games.samegame", "samegame",
1640     default_params,
1641     game_fetch_preset, NULL,
1642     decode_params,
1643     encode_params,
1644     free_params,
1645     dup_params,
1646     TRUE, game_configure, custom_params,
1647     validate_params,
1648     new_game_desc,
1649     validate_desc,
1650     new_game,
1651     dup_game,
1652     free_game,
1653     FALSE, solve_game,
1654     TRUE, game_can_format_as_text_now, game_text_format,
1655     new_ui,
1656     free_ui,
1657     encode_ui,
1658     decode_ui,
1659     game_changed_state,
1660     interpret_move,
1661     execute_move,
1662     PREFERRED_TILE_SIZE, game_compute_size, game_set_size,
1663     game_colours,
1664     game_new_drawstate,
1665     game_free_drawstate,
1666     game_redraw,
1667     game_anim_length,
1668     game_flash_length,
1669     game_status,
1670     FALSE, FALSE, game_print_size, game_print,
1671     TRUE,                              /* wants_statusbar */
1672     FALSE, game_timing_state,
1673     0,                                 /* flags */
1674 };