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