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