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 *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 int game_can_format_as_text_now(game_params *params)
1026 {
1027     return TRUE;
1028 }
1029
1030 static char *game_text_format(game_state *state)
1031 {
1032     char *ret, *p;
1033     int x, y, maxlen;
1034
1035     maxlen = state->params.h * (state->params.w + 1);
1036     ret = snewn(maxlen+1, char);
1037     p = ret;
1038
1039     for (y = 0; y < state->params.h; y++) {
1040         for (x = 0; x < state->params.w; x++) {
1041             int t = TILE(state,x,y);
1042             if (t <= 0)      *p++ = ' ';
1043             else if (t < 10) *p++ = '0'+t;
1044             else             *p++ = 'a'+(t-10);
1045         }
1046         *p++ = '\n';
1047     }
1048     assert(p - ret == maxlen);
1049     *p = '\0';
1050     return ret;
1051 }
1052
1053 struct game_ui {
1054     struct game_params params;
1055     int *tiles; /* selected-ness only */
1056     int nselected;
1057     int xsel, ysel, displaysel;
1058 };
1059
1060 static game_ui *new_ui(game_state *state)
1061 {
1062     game_ui *ui = snew(game_ui);
1063
1064     ui->params = state->params; /* structure copy */
1065     ui->tiles = snewn(state->n, int);
1066     memset(ui->tiles, 0, state->n*sizeof(int));
1067     ui->nselected = 0;
1068
1069     ui->xsel = ui->ysel = ui->displaysel = 0;
1070
1071     return ui;
1072 }
1073
1074 static void free_ui(game_ui *ui)
1075 {
1076     sfree(ui->tiles);
1077     sfree(ui);
1078 }
1079
1080 static char *encode_ui(game_ui *ui)
1081 {
1082     return NULL;
1083 }
1084
1085 static void decode_ui(game_ui *ui, char *encoding)
1086 {
1087 }
1088
1089 static void sel_clear(game_ui *ui, game_state *state)
1090 {
1091     int i;
1092
1093     for (i = 0; i < state->n; i++)
1094         ui->tiles[i] &= ~TILE_SELECTED;
1095     ui->nselected = 0;
1096 }
1097
1098
1099 static void game_changed_state(game_ui *ui, game_state *oldstate,
1100                                game_state *newstate)
1101 {
1102     sel_clear(ui, newstate);
1103
1104     /*
1105      * If the game state has just changed into an unplayable one
1106      * (either completed or impossible), we vanish the keyboard-
1107      * control cursor.
1108      */
1109     if (newstate->complete || newstate->impossible)
1110         ui->displaysel = 0;
1111 }
1112
1113 static char *sel_movedesc(game_ui *ui, game_state *state)
1114 {
1115     int i;
1116     char *ret, *sep, buf[80];
1117     int retlen, retsize;
1118
1119     retsize = 256;
1120     ret = snewn(retsize, char);
1121     retlen = 0;
1122     ret[retlen++] = 'M';
1123     sep = "";
1124
1125     for (i = 0; i < state->n; i++) {
1126         if (ui->tiles[i] & TILE_SELECTED) {
1127             sprintf(buf, "%s%d", sep, i);
1128             sep = ",";
1129             if (retlen + (int)strlen(buf) >= retsize) {
1130                 retsize = retlen + strlen(buf) + 256;
1131                 ret = sresize(ret, retsize, char);
1132             }
1133             strcpy(ret + retlen, buf);
1134             retlen += strlen(buf);
1135
1136             ui->tiles[i] &= ~TILE_SELECTED;
1137         }
1138     }
1139     ui->nselected = 0;
1140
1141     assert(retlen < retsize);
1142     ret[retlen++] = '\0';
1143     return sresize(ret, retlen, char);
1144 }
1145
1146 static void sel_expand(game_ui *ui, game_state *state, int tx, int ty)
1147 {
1148     int ns = 1, nadded, x, y, c;
1149
1150     TILE(ui,tx,ty) |= TILE_SELECTED;
1151     do {
1152         nadded = 0;
1153
1154         for (x = 0; x < state->params.w; x++) {
1155             for (y = 0; y < state->params.h; y++) {
1156                 if (x == tx && y == ty) continue;
1157                 if (ISSEL(ui,x,y)) continue;
1158
1159                 c = COL(state,x,y);
1160                 if ((x > 0) &&
1161                     ISSEL(ui,x-1,y) && COL(state,x-1,y) == c) {
1162                     TILE(ui,x,y) |= TILE_SELECTED;
1163                     nadded++;
1164                     continue;
1165                 }
1166
1167                 if ((x+1 < state->params.w) &&
1168                     ISSEL(ui,x+1,y) && COL(state,x+1,y) == c) {
1169                     TILE(ui,x,y) |= TILE_SELECTED;
1170                     nadded++;
1171                     continue;
1172                 }
1173
1174                 if ((y > 0) &&
1175                     ISSEL(ui,x,y-1) && COL(state,x,y-1) == c) {
1176                     TILE(ui,x,y) |= TILE_SELECTED;
1177                     nadded++;
1178                     continue;
1179                 }
1180
1181                 if ((y+1 < state->params.h) &&
1182                     ISSEL(ui,x,y+1) && COL(state,x,y+1) == c) {
1183                     TILE(ui,x,y) |= TILE_SELECTED;
1184                     nadded++;
1185                     continue;
1186                 }
1187             }
1188         }
1189         ns += nadded;
1190     } while (nadded > 0);
1191
1192     if (ns > 1) {
1193         ui->nselected = ns;
1194     } else {
1195         sel_clear(ui, state);
1196     }
1197 }
1198
1199 static int sg_emptycol(game_state *ret, int x)
1200 {
1201     int y;
1202     for (y = 0; y < ret->params.h; y++) {
1203         if (COL(ret,x,y)) return 0;
1204     }
1205     return 1;
1206 }
1207
1208
1209 static void sg_snuggle(game_state *ret)
1210 {
1211     int x,y, ndone;
1212
1213     /* make all unsupported tiles fall down. */
1214     do {
1215         ndone = 0;
1216         for (x = 0; x < ret->params.w; x++) {
1217             for (y = ret->params.h-1; y > 0; y--) {
1218                 if (COL(ret,x,y) != 0) continue;
1219                 if (COL(ret,x,y-1) != 0) {
1220                     SWAPTILE(ret,x,y,x,y-1);
1221                     ndone++;
1222                 }
1223             }
1224         }
1225     } while (ndone);
1226
1227     /* shuffle all columns as far left as they can go. */
1228     do {
1229         ndone = 0;
1230         for (x = 0; x < ret->params.w-1; x++) {
1231             if (sg_emptycol(ret,x) && !sg_emptycol(ret,x+1)) {
1232                 ndone++;
1233                 for (y = 0; y < ret->params.h; y++) {
1234                     SWAPTILE(ret,x,y,x+1,y);
1235                 }
1236             }
1237         }
1238     } while (ndone);
1239 }
1240
1241 static void sg_check(game_state *ret)
1242 {
1243     int x,y, complete = 1, impossible = 1;
1244
1245     for (x = 0; x < ret->params.w; x++) {
1246         for (y = 0; y < ret->params.h; y++) {
1247             if (COL(ret,x,y) == 0)
1248                 continue;
1249             complete = 0;
1250             if (x+1 < ret->params.w) {
1251                 if (COL(ret,x,y) == COL(ret,x+1,y))
1252                     impossible = 0;
1253             }
1254             if (y+1 < ret->params.h) {
1255                 if (COL(ret,x,y) == COL(ret,x,y+1))
1256                     impossible = 0;
1257             }
1258         }
1259     }
1260     ret->complete = complete;
1261     ret->impossible = impossible;
1262 }
1263
1264 struct game_drawstate {
1265     int started, bgcolour;
1266     int tileinner, tilegap;
1267     int *tiles; /* contains colour and SELECTED. */
1268 };
1269
1270 static char *interpret_move(game_state *state, game_ui *ui, game_drawstate *ds,
1271                             int x, int y, int button)
1272 {
1273     int tx, ty;
1274     char *ret = "";
1275
1276     ui->displaysel = 0;
1277
1278     if (button == RIGHT_BUTTON || button == LEFT_BUTTON) {
1279         tx = FROMCOORD(x); ty= FROMCOORD(y);
1280     } else if (IS_CURSOR_MOVE(button)) {
1281         int dx = 0, dy = 0;
1282         ui->displaysel = 1;
1283         dx = (button == CURSOR_LEFT) ? -1 : ((button == CURSOR_RIGHT) ? +1 : 0);
1284         dy = (button == CURSOR_DOWN) ? +1 : ((button == CURSOR_UP)    ? -1 : 0);
1285         ui->xsel = (ui->xsel + state->params.w + dx) % state->params.w;
1286         ui->ysel = (ui->ysel + state->params.h + dy) % state->params.h;
1287         return ret;
1288     } else if (IS_CURSOR_SELECT(button)) {
1289         ui->displaysel = 1;
1290         tx = ui->xsel;
1291         ty = ui->ysel;
1292     } else
1293         return NULL;
1294
1295     if (tx < 0 || tx >= state->params.w || ty < 0 || ty >= state->params.h)
1296         return NULL;
1297     if (COL(state, tx, ty) == 0) return NULL;
1298
1299     if (ISSEL(ui,tx,ty)) {
1300         if (button == RIGHT_BUTTON || button == CURSOR_SELECT2)
1301             sel_clear(ui, state);
1302         else
1303             ret = sel_movedesc(ui, state);
1304     } else {
1305         sel_clear(ui, state); /* might be no-op */
1306         sel_expand(ui, state, tx, ty);
1307     }
1308
1309     return ret;
1310 }
1311
1312 static game_state *execute_move(game_state *from, char *move)
1313 {
1314     int i, n;
1315     game_state *ret;
1316
1317     if (move[0] == 'M') {
1318         ret = dup_game(from);
1319
1320         n = 0;
1321         move++;
1322
1323         while (*move) {
1324             i = atoi(move);
1325             if (i < 0 || i >= ret->n) {
1326                 free_game(ret);
1327                 return NULL;
1328             }
1329             n++;
1330             ret->tiles[i] = 0;
1331
1332             while (*move && isdigit((unsigned char)*move)) move++;
1333             if (*move == ',') move++;
1334         }
1335
1336         ret->score += npoints(&ret->params, n);
1337
1338         sg_snuggle(ret); /* shifts blanks down and to the left */
1339         sg_check(ret);   /* checks for completeness or impossibility */
1340
1341         return ret;
1342     } else
1343         return NULL;                   /* couldn't parse move string */
1344 }
1345
1346 /* ----------------------------------------------------------------------
1347  * Drawing routines.
1348  */
1349
1350 static void game_set_size(drawing *dr, game_drawstate *ds,
1351                           game_params *params, int tilesize)
1352 {
1353     ds->tilegap = 2;
1354     ds->tileinner = tilesize - ds->tilegap;
1355 }
1356
1357 static void game_compute_size(game_params *params, int tilesize,
1358                               int *x, int *y)
1359 {
1360     /* Ick: fake up tile size variables for macro expansion purposes */
1361     game_drawstate ads, *ds = &ads;
1362     game_set_size(NULL, ds, params, tilesize);
1363
1364     *x = TILE_SIZE * params->w + 2 * BORDER - TILE_GAP;
1365     *y = TILE_SIZE * params->h + 2 * BORDER - TILE_GAP;
1366 }
1367
1368 static float *game_colours(frontend *fe, int *ncolours)
1369 {
1370     float *ret = snewn(3 * NCOLOURS, float);
1371
1372     frontend_default_colour(fe, &ret[COL_BACKGROUND * 3]);
1373
1374     ret[COL_1 * 3 + 0] = 0.0F;
1375     ret[COL_1 * 3 + 1] = 0.0F;
1376     ret[COL_1 * 3 + 2] = 1.0F;
1377
1378     ret[COL_2 * 3 + 0] = 0.0F;
1379     ret[COL_2 * 3 + 1] = 0.5F;
1380     ret[COL_2 * 3 + 2] = 0.0F;
1381
1382     ret[COL_3 * 3 + 0] = 1.0F;
1383     ret[COL_3 * 3 + 1] = 0.0F;
1384     ret[COL_3 * 3 + 2] = 0.0F;
1385
1386     ret[COL_4 * 3 + 0] = 1.0F;
1387     ret[COL_4 * 3 + 1] = 1.0F;
1388     ret[COL_4 * 3 + 2] = 0.0F;
1389
1390     ret[COL_5 * 3 + 0] = 1.0F;
1391     ret[COL_5 * 3 + 1] = 0.0F;
1392     ret[COL_5 * 3 + 2] = 1.0F;
1393
1394     ret[COL_6 * 3 + 0] = 0.0F;
1395     ret[COL_6 * 3 + 1] = 1.0F;
1396     ret[COL_6 * 3 + 2] = 1.0F;
1397
1398     ret[COL_7 * 3 + 0] = 0.5F;
1399     ret[COL_7 * 3 + 1] = 0.5F;
1400     ret[COL_7 * 3 + 2] = 1.0F;
1401
1402     ret[COL_8 * 3 + 0] = 0.5F;
1403     ret[COL_8 * 3 + 1] = 1.0F;
1404     ret[COL_8 * 3 + 2] = 0.5F;
1405
1406     ret[COL_9 * 3 + 0] = 1.0F;
1407     ret[COL_9 * 3 + 1] = 0.5F;
1408     ret[COL_9 * 3 + 2] = 0.5F;
1409
1410     ret[COL_IMPOSSIBLE * 3 + 0] = 0.0F;
1411     ret[COL_IMPOSSIBLE * 3 + 1] = 0.0F;
1412     ret[COL_IMPOSSIBLE * 3 + 2] = 0.0F;
1413
1414     ret[COL_SEL * 3 + 0] = 1.0F;
1415     ret[COL_SEL * 3 + 1] = 1.0F;
1416     ret[COL_SEL * 3 + 2] = 1.0F;
1417
1418     ret[COL_HIGHLIGHT * 3 + 0] = 1.0F;
1419     ret[COL_HIGHLIGHT * 3 + 1] = 1.0F;
1420     ret[COL_HIGHLIGHT * 3 + 2] = 1.0F;
1421
1422     ret[COL_LOWLIGHT * 3 + 0] = ret[COL_BACKGROUND * 3 + 0] * 2.0F / 3.0F;
1423     ret[COL_LOWLIGHT * 3 + 1] = ret[COL_BACKGROUND * 3 + 1] * 2.0F / 3.0F;
1424     ret[COL_LOWLIGHT * 3 + 2] = ret[COL_BACKGROUND * 3 + 2] * 2.0F / 3.0F;
1425
1426     *ncolours = NCOLOURS;
1427     return ret;
1428 }
1429
1430 static game_drawstate *game_new_drawstate(drawing *dr, game_state *state)
1431 {
1432     struct game_drawstate *ds = snew(struct game_drawstate);
1433     int i;
1434
1435     ds->started = 0;
1436     ds->tileinner = ds->tilegap = 0;   /* not decided yet */
1437     ds->tiles = snewn(state->n, int);
1438     ds->bgcolour = -1;
1439     for (i = 0; i < state->n; i++)
1440         ds->tiles[i] = -1;
1441
1442     return ds;
1443 }
1444
1445 static void game_free_drawstate(drawing *dr, game_drawstate *ds)
1446 {
1447     sfree(ds->tiles);
1448     sfree(ds);
1449 }
1450
1451 /* Drawing routing for the tile at (x,y) is responsible for drawing
1452  * itself and the gaps to its right and below. If we're the same colour
1453  * as the tile to our right, then we fill in the gap; ditto below, and if
1454  * both then we fill the teeny tiny square in the corner as well.
1455  */
1456
1457 static void tile_redraw(drawing *dr, game_drawstate *ds,
1458                         int x, int y, int dright, int dbelow,
1459                         int tile, int bgcolour)
1460 {
1461     int outer = bgcolour, inner = outer, col = tile & TILE_COLMASK;
1462
1463     if (col) {
1464         if (tile & TILE_IMPOSSIBLE) {
1465             outer = col;
1466             inner = COL_IMPOSSIBLE;
1467         } else if (tile & TILE_SELECTED) {
1468             outer = COL_SEL;
1469             inner = col;
1470         } else {
1471             outer = inner = col;
1472         }
1473     }
1474     draw_rect(dr, COORD(x), COORD(y), TILE_INNER, TILE_INNER, outer);
1475     draw_rect(dr, COORD(x)+TILE_INNER/4, COORD(y)+TILE_INNER/4,
1476               TILE_INNER/2, TILE_INNER/2, inner);
1477
1478     if (dright)
1479         draw_rect(dr, COORD(x)+TILE_INNER, COORD(y), TILE_GAP, TILE_INNER,
1480                   (tile & TILE_JOINRIGHT) ? outer : bgcolour);
1481     if (dbelow)
1482         draw_rect(dr, COORD(x), COORD(y)+TILE_INNER, TILE_INNER, TILE_GAP,
1483                   (tile & TILE_JOINDOWN) ? outer : bgcolour);
1484     if (dright && dbelow)
1485         draw_rect(dr, COORD(x)+TILE_INNER, COORD(y)+TILE_INNER, TILE_GAP, TILE_GAP,
1486                   (tile & TILE_JOINDIAG) ? outer : bgcolour);
1487
1488     if (tile & TILE_HASSEL) {
1489         int sx = COORD(x)+2, sy = COORD(y)+2, ssz = TILE_INNER-5;
1490         int scol = (outer == COL_SEL) ? COL_LOWLIGHT : COL_HIGHLIGHT;
1491         draw_line(dr, sx,     sy,     sx+ssz, sy,     scol);
1492         draw_line(dr, sx+ssz, sy,     sx+ssz, sy+ssz, scol);
1493         draw_line(dr, sx+ssz, sy+ssz, sx,     sy+ssz, scol);
1494         draw_line(dr, sx,     sy+ssz, sx,     sy,     scol);
1495     }
1496
1497     draw_update(dr, COORD(x), COORD(y), TILE_SIZE, TILE_SIZE);
1498 }
1499
1500 static void game_redraw(drawing *dr, game_drawstate *ds, game_state *oldstate,
1501                         game_state *state, int dir, game_ui *ui,
1502                         float animtime, float flashtime)
1503 {
1504     int bgcolour, x, y;
1505
1506     /* This was entirely cloned from fifteen.c; it should probably be
1507      * moved into some generic 'draw-recessed-rectangle' utility fn. */
1508     if (!ds->started) {
1509         int coords[10];
1510
1511         draw_rect(dr, 0, 0,
1512                   TILE_SIZE * state->params.w + 2 * BORDER,
1513                   TILE_SIZE * state->params.h + 2 * BORDER, COL_BACKGROUND);
1514         draw_update(dr, 0, 0,
1515                     TILE_SIZE * state->params.w + 2 * BORDER,
1516                     TILE_SIZE * state->params.h + 2 * BORDER);
1517
1518         /*
1519          * Recessed area containing the whole puzzle.
1520          */
1521         coords[0] = COORD(state->params.w) + HIGHLIGHT_WIDTH - 1 - TILE_GAP;
1522         coords[1] = COORD(state->params.h) + HIGHLIGHT_WIDTH - 1 - TILE_GAP;
1523         coords[2] = COORD(state->params.w) + HIGHLIGHT_WIDTH - 1 - TILE_GAP;
1524         coords[3] = COORD(0) - HIGHLIGHT_WIDTH;
1525         coords[4] = coords[2] - TILE_SIZE;
1526         coords[5] = coords[3] + TILE_SIZE;
1527         coords[8] = COORD(0) - HIGHLIGHT_WIDTH;
1528         coords[9] = COORD(state->params.h) + HIGHLIGHT_WIDTH - 1 - TILE_GAP;
1529         coords[6] = coords[8] + TILE_SIZE;
1530         coords[7] = coords[9] - TILE_SIZE;
1531         draw_polygon(dr, coords, 5, COL_HIGHLIGHT, COL_HIGHLIGHT);
1532
1533         coords[1] = COORD(0) - HIGHLIGHT_WIDTH;
1534         coords[0] = COORD(0) - HIGHLIGHT_WIDTH;
1535         draw_polygon(dr, coords, 5, COL_LOWLIGHT, COL_LOWLIGHT);
1536
1537         ds->started = 1;
1538     }
1539
1540     if (flashtime > 0.0) {
1541         int frame = (int)(flashtime / FLASH_FRAME);
1542         bgcolour = (frame % 2 ? COL_LOWLIGHT : COL_HIGHLIGHT);
1543     } else
1544         bgcolour = COL_BACKGROUND;
1545
1546     for (x = 0; x < state->params.w; x++) {
1547         for (y = 0; y < state->params.h; y++) {
1548             int i = (state->params.w * y) + x;
1549             int col = COL(state,x,y), tile = col;
1550             int dright = (x+1 < state->params.w);
1551             int dbelow = (y+1 < state->params.h);
1552
1553             tile |= ISSEL(ui,x,y);
1554             if (state->impossible)
1555                 tile |= TILE_IMPOSSIBLE;
1556             if (dright && COL(state,x+1,y) == col)
1557                 tile |= TILE_JOINRIGHT;
1558             if (dbelow && COL(state,x,y+1) == col)
1559                 tile |= TILE_JOINDOWN;
1560             if ((tile & TILE_JOINRIGHT) && (tile & TILE_JOINDOWN) &&
1561                 COL(state,x+1,y+1) == col)
1562                 tile |= TILE_JOINDIAG;
1563
1564             if (ui->displaysel && ui->xsel == x && ui->ysel == y)
1565                 tile |= TILE_HASSEL;
1566
1567             /* For now we're never expecting oldstate at all (because we have
1568              * no animation); when we do we might well want to be looking
1569              * at the tile colours from oldstate, not state. */
1570             if ((oldstate && COL(oldstate,x,y) != col) ||
1571                 (ds->bgcolour != bgcolour) ||
1572                 (tile != ds->tiles[i])) {
1573                 tile_redraw(dr, ds, x, y, dright, dbelow, tile, bgcolour);
1574                 ds->tiles[i] = tile;
1575             }
1576         }
1577     }
1578     ds->bgcolour = bgcolour;
1579
1580     {
1581         char status[255], score[80];
1582
1583         sprintf(score, "Score: %d", state->score);
1584
1585         if (state->complete)
1586             sprintf(status, "COMPLETE! %s", score);
1587         else if (state->impossible)
1588             sprintf(status, "Cannot move! %s", score);
1589         else if (ui->nselected)
1590             sprintf(status, "%s  Selected: %d (%d)",
1591                     score, ui->nselected, npoints(&state->params, ui->nselected));
1592         else
1593             sprintf(status, "%s", score);
1594         status_bar(dr, status);
1595     }
1596 }
1597
1598 static float game_anim_length(game_state *oldstate, game_state *newstate,
1599                               int dir, game_ui *ui)
1600 {
1601     return 0.0F;
1602 }
1603
1604 static float game_flash_length(game_state *oldstate, game_state *newstate,
1605                                int dir, game_ui *ui)
1606 {
1607     if ((!oldstate->complete && newstate->complete) ||
1608         (!oldstate->impossible && newstate->impossible))
1609         return 2 * FLASH_FRAME;
1610     else
1611         return 0.0F;
1612 }
1613
1614 static int game_status(game_state *state)
1615 {
1616     /*
1617      * Dead-end situations are assumed to be rescuable by Undo, so we
1618      * don't bother to identify them and return -1.
1619      */
1620     return state->complete ? +1 : 0;
1621 }
1622
1623 static int game_timing_state(game_state *state, game_ui *ui)
1624 {
1625     return TRUE;
1626 }
1627
1628 static void game_print_size(game_params *params, float *x, float *y)
1629 {
1630 }
1631
1632 static void game_print(drawing *dr, game_state *state, int tilesize)
1633 {
1634 }
1635
1636 #ifdef COMBINED
1637 #define thegame samegame
1638 #endif
1639
1640 const struct game thegame = {
1641     "Same Game", "games.samegame", "samegame",
1642     default_params,
1643     game_fetch_preset,
1644     decode_params,
1645     encode_params,
1646     free_params,
1647     dup_params,
1648     TRUE, game_configure, custom_params,
1649     validate_params,
1650     new_game_desc,
1651     validate_desc,
1652     new_game,
1653     dup_game,
1654     free_game,
1655     FALSE, solve_game,
1656     TRUE, game_can_format_as_text_now, game_text_format,
1657     new_ui,
1658     free_ui,
1659     encode_ui,
1660     decode_ui,
1661     game_changed_state,
1662     interpret_move,
1663     execute_move,
1664     PREFERRED_TILE_SIZE, game_compute_size, game_set_size,
1665     game_colours,
1666     game_new_drawstate,
1667     game_free_drawstate,
1668     game_redraw,
1669     game_anim_length,
1670     game_flash_length,
1671     game_status,
1672     FALSE, FALSE, game_print_size, game_print,
1673     TRUE,                              /* wants_statusbar */
1674     FALSE, game_timing_state,
1675     0,                                 /* flags */
1676 };