flip.c

   1 /*
   2  * flip.c: Puzzle involving lighting up all the squares on a grid,
   3  * where each click toggles an overlapping set of lights.
   4  */
   5
   6 /*
   7  * TODO:
   8  *
   9  *  - `Solve' could mark the squares you must click to solve
  10  *     + infrastructure change: this would mean the Solve operation
  11  *       must receive the current game_state as well as the initial
  12  *       one, which I've been wondering about for a while
  13  */
  14
  15 #include <stdio.h>
  16 #include <stdlib.h>
  17 #include <string.h>
  18 #include <assert.h>
  19 #include <ctype.h>
  20 #include <math.h>
  21
  22 #include "puzzles.h"
  23 #include "tree234.h"
  24
  25 enum {
  26     COL_BACKGROUND,
  27     COL_WRONG,
  28     COL_RIGHT,
  29     COL_GRID,
  30     COL_DIAG,
  31     NCOLOURS
  32 };
  33
  34 #define PREFERRED_TILE_SIZE 48
  35 #define TILE_SIZE (ds->tilesize)
  36 #define BORDER    (TILE_SIZE / 2)
  37 #define COORD(x)  ( (x) * TILE_SIZE + BORDER )
  38 #define FROMCOORD(x)  ( ((x) - BORDER + TILE_SIZE) / TILE_SIZE - 1 )
  39
  40 #define ANIM_TIME 0.25F
  41 #define FLASH_FRAME 0.07F
  42
  43 /*
  44  * Possible ways to decide which lights are toggled by each click.
  45  * Essentially, each of these describes a means of inventing a
  46  * matrix over GF(2).
  47  */
  48 enum {
  49     CROSSES, RANDOM
  50 };
  51
  52 struct game_params {
  53     int w, h;
  54     int matrix_type;
  55 };
  56
  57 /*
  58  * This structure is shared between all the game_states describing
  59  * a particular game, so it's reference-counted.
  60  */
  61 struct matrix {
  62     int refcount;
  63     unsigned char *matrix;             /* array of (w*h) by (w*h) */
  64 };
  65
  66 struct game_state {
  67     int w, h;
  68     int moves, completed;
  69     unsigned char *grid;               /* array of w*h */
  70     struct matrix *matrix;
  71 };
  72
  73 static game_params *default_params(void)
  74 {
  75     game_params *ret = snew(game_params);
  76
  77     ret->w = ret->h = 5;
  78     ret->matrix_type = CROSSES;
  79
  80     return ret;
  81 }
  82
  83 static const struct game_params flip_presets[] = {
  84     {3, 3, CROSSES},
  85     {4, 4, CROSSES},
  86     {5, 5, CROSSES},
  87     {3, 3, RANDOM},
  88     {4, 4, RANDOM},
  89     {5, 5, RANDOM},
  90 };
  91
  92 static int game_fetch_preset(int i, char **name, game_params **params)
  93 {
  94     game_params *ret;
  95     char str[80];
  96
  97     if (i < 0 || i >= lenof(flip_presets))
  98         return FALSE;
  99
 100     ret = snew(game_params);
 101     *ret = flip_presets[i];
 102
 103     sprintf(str, "%dx%d %s", ret->w, ret->h,
 104             ret->matrix_type == CROSSES ? "Crosses" : "Random");
 105
 106     *name = dupstr(str);
 107     *params = ret;
 108     return TRUE;
 109 }
 110
 111 static void free_params(game_params *params)
 112 {
 113     sfree(params);
 114 }
 115
 116 static game_params *dup_params(game_params *params)
 117 {
 118     game_params *ret = snew(game_params);
 119     *ret = *params;                    /* structure copy */
 120     return ret;
 121 }
 122
 123 static void decode_params(game_params *ret, char const *string)
 124 {
 125     ret->w = ret->h = atoi(string);
 126     while (*string && isdigit(*string)) string++;
 127     if (*string == 'x') {
 128         string++;
 129         ret->h = atoi(string);
 130         while (*string && isdigit(*string)) string++;
 131     }
 132     if (*string == 'r') {
 133         string++;
 134         ret->matrix_type = RANDOM;
 135     } else if (*string == 'c') {
 136         string++;
 137         ret->matrix_type = CROSSES;
 138     }
 139 }
 140
 141 static char *encode_params(game_params *params, int full)
 142 {
 143     char data[256];
 144
 145     sprintf(data, "%dx%d%s", params->w, params->h,
 146             !full ? "" : params->matrix_type == CROSSES ? "c" : "r");
 147
 148     return dupstr(data);
 149 }
 150
 151 static config_item *game_configure(game_params *params)
 152 {
 153     config_item *ret = snewn(4, config_item);
 154     char buf[80];
 155
 156     ret[0].name = "Width";
 157     ret[0].type = C_STRING;
 158     sprintf(buf, "%d", params->w);
 159     ret[0].sval = dupstr(buf);
 160     ret[0].ival = 0;
 161
 162     ret[1].name = "Height";
 163     ret[1].type = C_STRING;
 164     sprintf(buf, "%d", params->h);
 165     ret[1].sval = dupstr(buf);
 166     ret[1].ival = 0;
 167
 168     ret[2].name = "Shape type";
 169     ret[2].type = C_CHOICES;
 170     ret[2].sval = ":Crosses:Random";
 171     ret[2].ival = params->matrix_type;
 172
 173     ret[3].name = NULL;
 174     ret[3].type = C_END;
 175     ret[3].sval = NULL;
 176     ret[3].ival = 0;
 177
 178     return ret;
 179 }
 180
 181 static game_params *custom_params(config_item *cfg)
 182 {
 183     game_params *ret = snew(game_params);
 184
 185     ret->w = atoi(cfg[0].sval);
 186     ret->h = atoi(cfg[1].sval);
 187     ret->matrix_type = cfg[2].ival;
 188
 189     return ret;
 190 }
 191
 192 static char *validate_params(game_params *params)
 193 {
 194     if (params->w <= 0 || params->h <= 0)
 195         return "Width and height must both be greater than zero";
 196     return NULL;
 197 }
 198
 199 static char *encode_bitmap(unsigned char *bmp, int len)
 200 {
 201     int slen = (len + 3) / 4;
 202     char *ret;
 203     int i;
 204
 205     ret = snewn(slen + 1, char);
 206     for (i = 0; i < slen; i++) {
 207         int j, v;
 208         v = 0;
 209         for (j = 0; j < 4; j++)
 210             if (i*4+j < len && bmp[i*4+j])
 211                 v |= 8 >> j;
 212         ret[i] = "0123456789abcdef"[v];
 213     }
 214     ret[slen] = '\0';
 215     return ret;
 216 }
 217
 218 static void decode_bitmap(unsigned char *bmp, int len, char *hex)
 219 {
 220     int slen = (len + 3) / 4;
 221     int i;
 222
 223     for (i = 0; i < slen; i++) {
 224         int j, v, c = hex[i];
 225         if (c >= '0' && c <= '9')
 226             v = c - '0';
 227         else if (c >= 'A' && c <= 'F')
 228             v = c - 'A' + 10;
 229         else if (c >= 'a' && c <= 'f')
 230             v = c - 'a' + 10;
 231         else
 232             v = 0;                     /* shouldn't happen */
 233         for (j = 0; j < 4; j++) {
 234             if (i*4+j < len) {
 235                 if (v & (8 >> j))
 236                     bmp[i*4+j] = 1;
 237                 else
 238                     bmp[i*4+j] = 0;
 239             }
 240         }
 241     }
 242 }
 243
 244 /*
 245  * Structure used during random matrix generation, and a compare
 246  * function to permit storage in a tree234.
 247  */
 248 struct sq {
 249     int cx, cy;                        /* coords of click square */
 250     int x, y;                          /* coords of output square */
 251     /*
 252      * Number of click squares which currently affect this output
 253      * square.
 254      */
 255     int coverage;
 256     /*
 257      * Number of output squares currently affected by this click
 258      * square.
 259      */
 260     int ominosize;
 261 };
 262 #define SORT(field) do { \
 263     if (a->field < b->field) \
 264         return -1; \
 265     else if (a->field > b->field) \
 266         return +1; \
 267 } while (0)
 268 /*
 269  * Compare function for choosing the next square to add. We must
 270  * sort by coverage, then by omino size, then everything else.
 271  */
 272 static int sqcmp_pick(void *av, void *bv)
 273 {
 274     struct sq *a = (struct sq *)av;
 275     struct sq *b = (struct sq *)bv;
 276     SORT(coverage);
 277     SORT(ominosize);
 278     SORT(cy);
 279     SORT(cx);
 280     SORT(y);
 281     SORT(x);
 282     return 0;
 283 }
 284 /*
 285  * Compare function for adjusting the coverage figures after a
 286  * change. We sort first by coverage and output square, then by
 287  * everything else.
 288  */
 289 static int sqcmp_cov(void *av, void *bv)
 290 {
 291     struct sq *a = (struct sq *)av;
 292     struct sq *b = (struct sq *)bv;
 293     SORT(coverage);
 294     SORT(y);
 295     SORT(x);
 296     SORT(ominosize);
 297     SORT(cy);
 298     SORT(cx);
 299     return 0;
 300 }
 301 /*
 302  * Compare function for adjusting the omino sizes after a change.
 303  * We sort first by omino size and input square, then by everything
 304  * else.
 305  */
 306 static int sqcmp_osize(void *av, void *bv)
 307 {
 308     struct sq *a = (struct sq *)av;
 309     struct sq *b = (struct sq *)bv;
 310     SORT(ominosize);
 311     SORT(cy);
 312     SORT(cx);
 313     SORT(coverage);
 314     SORT(y);
 315     SORT(x);
 316     return 0;
 317 }
 318 static void addsq(tree234 *t, int w, int h, int cx, int cy,
 319                   int x, int y, unsigned char *matrix)
 320 {
 321     int wh = w * h;
 322     struct sq *sq;
 323     int i;
 324
 325     if (x < 0 || x >= w || y < 0 || y >= h)
 326         return;
 327     if (abs(x-cx) > 1 || abs(y-cy) > 1)
 328         return;
 329     if (matrix[(cy*w+cx) * wh + y*w+x])
 330         return;
 331
 332     sq = snew(struct sq);
 333     sq->cx = cx;
 334     sq->cy = cy;
 335     sq->x = x;
 336     sq->y = y;
 337     sq->coverage = sq->ominosize = 0;
 338     for (i = 0; i < wh; i++) {
 339         if (matrix[i * wh + y*w+x])
 340             sq->coverage++;
 341         if (matrix[(cy*w+cx) * wh + i])
 342             sq->ominosize++;
 343     }
 344
 345     if (add234(t, sq) != sq)
 346         sfree(sq);                     /* already there */
 347 }
 348 static void addneighbours(tree234 *t, int w, int h, int cx, int cy,
 349                           int x, int y, unsigned char *matrix)
 350 {
 351     addsq(t, w, h, cx, cy, x-1, y, matrix);
 352     addsq(t, w, h, cx, cy, x+1, y, matrix);
 353     addsq(t, w, h, cx, cy, x, y-1, matrix);
 354     addsq(t, w, h, cx, cy, x, y+1, matrix);
 355 }
 356
 357 static char *new_game_desc(game_params *params, random_state *rs,
 358                            game_aux_info **aux, int interactive)
 359 {
 360     int w = params->w, h = params->h, wh = w * h;
 361     int i, j;
 362     unsigned char *matrix, *grid;
 363     char *mbmp, *gbmp, *ret;
 364
 365     matrix = snewn(wh * wh, unsigned char);
 366     grid = snewn(wh, unsigned char);
 367
 368     /*
 369      * First set up the matrix.
 370      */
 371     switch (params->matrix_type) {
 372       case CROSSES:
 373         for (i = 0; i < wh; i++) {
 374             int ix = i % w, iy = i / w;
 375             for (j = 0; j < wh; j++) {
 376                 int jx = j % w, jy = j / w;
 377                 if (abs(jx - ix) + abs(jy - iy) <= 1)
 378                     matrix[i*wh+j] = 1;
 379                 else
 380                     matrix[i*wh+j] = 0;
 381             }
 382         }
 383         break;
 384       case RANDOM:
 385         while (1) {
 386             tree234 *pick, *cov, *osize;
 387             int limit;
 388
 389             pick = newtree234(sqcmp_pick);
 390             cov = newtree234(sqcmp_cov);
 391             osize = newtree234(sqcmp_osize);
 392
 393             memset(matrix, 0, wh * wh);
 394             for (i = 0; i < wh; i++) {
 395                 matrix[i*wh+i] = 1;
 396             }
 397
 398             for (i = 0; i < wh; i++) {
 399                 int ix = i % w, iy = i / w;
 400                 addneighbours(pick, w, h, ix, iy, ix, iy, matrix);
 401                 addneighbours(cov, w, h, ix, iy, ix, iy, matrix);
 402                 addneighbours(osize, w, h, ix, iy, ix, iy, matrix);
 403             }
 404
 405             /*
 406              * Repeatedly choose a square to add to the matrix,
 407              * until we have enough. I'll arbitrarily choose our
 408              * limit to be the same as the total number of set bits
 409              * in the crosses matrix.
 410              */
 411             limit = 4*wh - 2*(w+h);    /* centre squares already present */
 412
 413             while (limit-- > 0) {
 414                 struct sq *sq, *sq2, sqlocal;
 415                 int k;
 416
 417                 /*
 418                  * Find the lowest element in the pick tree.
 419                  */
 420                 sq = index234(pick, 0);
 421
 422                 /*
 423                  * Find the highest element with the same coverage
 424                  * and omino size, by setting all other elements to
 425                  * lots.
 426                  */
 427                 sqlocal = *sq;
 428                 sqlocal.cx = sqlocal.cy = sqlocal.x = sqlocal.y = wh;
 429                 sq = findrelpos234(pick, &sqlocal, NULL, REL234_LT, &k);
 430                 assert(sq != 0);
 431
 432                 /*
 433                  * Pick at random from all elements up to k of the
 434                  * pick tree.
 435                  */
 436                 k = random_upto(rs, k+1);
 437                 sq = delpos234(pick, k);
 438                 del234(cov, sq);
 439                 del234(osize, sq);
 440
 441                 /*
 442                  * Add this square to the matrix.
 443                  */
 444                 matrix[(sq->cy * w + sq->cx) * wh + (sq->y * w + sq->x)] = 1;
 445
 446                 /*
 447                  * Correct the matrix coverage field of any sq
 448                  * which points at this output square.
 449                  */
 450                 sqlocal = *sq;
 451                 sqlocal.cx = sqlocal.cy = sqlocal.ominosize = -1;
 452                 while ((sq2 = findrel234(cov, &sqlocal, NULL,
 453                                          REL234_GT)) != NULL &&
 454                        sq2->coverage == sq->coverage &&
 455                        sq2->x == sq->x && sq2->y == sq->y) {
 456                     del234(pick, sq2);
 457                     del234(cov, sq2);
 458                     del234(osize, sq2);
 459                     sq2->coverage++;
 460                     add234(pick, sq2);
 461                     add234(cov, sq2);
 462                     add234(osize, sq2);
 463                 }
 464
 465                 /*
 466                  * Correct the omino size field of any sq which
 467                  * points at this input square.
 468                  */
 469                 sqlocal = *sq;
 470                 sqlocal.x = sqlocal.y = sqlocal.coverage = -1;
 471                 while ((sq2 = findrel234(osize, &sqlocal, NULL,
 472                                          REL234_GT)) != NULL &&
 473                        sq2->ominosize == sq->ominosize &&
 474                        sq2->cx == sq->cx && sq2->cy == sq->cy) {
 475                     del234(pick, sq2);
 476                     del234(cov, sq2);
 477                     del234(osize, sq2);
 478                     sq2->ominosize++;
 479                     add234(pick, sq2);
 480                     add234(cov, sq2);
 481                     add234(osize, sq2);
 482                 }
 483
 484                 /*
 485                  * The sq we actually picked out of the tree is
 486                  * finished with; but its neighbours now need to
 487                  * appear.
 488                  */
 489                 addneighbours(pick, w,h, sq->cx,sq->cy, sq->x,sq->y, matrix);
 490                 addneighbours(cov, w,h, sq->cx,sq->cy, sq->x,sq->y, matrix);
 491                 addneighbours(osize, w,h, sq->cx,sq->cy, sq->x,sq->y, matrix);
 492                 sfree(sq);
 493             }
 494
 495             /*
 496              * Free all remaining sq structures.
 497              */
 498             {
 499                 struct sq *sq;
 500                 while ((sq = delpos234(pick, 0)) != NULL)
 501                     sfree(sq);
 502             }
 503             freetree234(pick);
 504             freetree234(cov);
 505             freetree234(osize);
 506
 507             /*
 508              * Finally, check to see if any two matrix rows are
 509              * exactly identical. If so, this is not an acceptable
 510              * matrix, and we give up and go round again.
 511              *
 512              * I haven't been immediately able to think of a
 513              * plausible means of algorithmically avoiding this
 514              * situation (by, say, making a small perturbation to
 515              * an offending matrix), so for the moment I'm just
 516              * going to deal with it by throwing the whole thing
 517              * away. I suspect this will lead to scalability
 518              * problems (since most of the things happening in
 519              * these matrices are local, the chance of _some_
 520              * neighbourhood having two identical regions will
 521              * increase with the grid area), but so far this puzzle
 522              * seems to be really hard at large sizes so I'm not
 523              * massively worried yet. Anyone needs this done
 524              * better, they're welcome to submit a patch.
 525              */
 526             for (i = 0; i < wh; i++) {
 527                 for (j = 0; j < wh; j++)
 528                     if (i != j &&
 529                         !memcmp(matrix + i * wh, matrix + j * wh, wh))
 530                         break;
 531                 if (j < wh)
 532                     break;
 533             }
 534             if (i == wh)
 535                 break;                 /* no matches found */
 536         }
 537         break;
 538     }
 539
 540     /*
 541      * Now invent a random initial set of lights.
 542      *
 543      * At first glance it looks as if it might be quite difficult
 544      * to choose equiprobably from all soluble light sets. After
 545      * all, soluble light sets are those in the image space of the
 546      * transformation matrix; so first we'd have to identify that
 547      * space and its dimension, then pick a random coordinate for
 548      * each basis vector and recombine. Lot of fiddly matrix
 549      * algebra there.
 550      *
 551      * However, vector spaces are nicely orthogonal and relieve us
 552      * of all that difficulty. For every point in the image space,
 553      * there are precisely as many points in the input space that
 554      * map to it as there are elements in the kernel of the
 555      * transformation matrix (because adding any kernel element to
 556      * the input does not change the output, and because any two
 557      * inputs mapping to the same output must differ by an element
 558      * of the kernel because that's what the kernel _is_); and
 559      * these cosets are all disjoint (obviously, since no input
 560      * point can map to more than one output point) and cover the
 561      * whole space (equally obviously, because no input point can
 562      * map to fewer than one output point!).
 563      *
 564      * So the input space contains the same number of points for
 565      * each point in the output space; thus, we can simply choose
 566      * equiprobably from elements of the _input_ space, and filter
 567      * the result through the transformation matrix in the obvious
 568      * way, and we thereby guarantee to choose equiprobably from
 569      * all the output points. Phew!
 570      */
 571     while (1) {
 572         memset(grid, 0, wh);
 573         for (i = 0; i < wh; i++) {
 574             int v = random_upto(rs, 2);
 575             if (v) {
 576                 for (j = 0; j < wh; j++)
 577                     grid[j] ^= matrix[i*wh+j];
 578             }
 579         }
 580         /*
 581          * Ensure we don't have the starting state already!
 582          */
 583         for (i = 0; i < wh; i++)
 584             if (grid[i])
 585                 break;
 586         if (i < wh)
 587             break;
 588     }
 589
 590     /*
 591      * Now encode the matrix and the starting grid as a game
 592      * description. We'll do this by concatenating two great big
 593      * hex bitmaps.
 594      */
 595     mbmp = encode_bitmap(matrix, wh*wh);
 596     gbmp = encode_bitmap(grid, wh);
 597     ret = snewn(strlen(mbmp) + strlen(gbmp) + 2, char);
 598     sprintf(ret, "%s,%s", mbmp, gbmp);
 599     sfree(mbmp);
 600     sfree(gbmp);
 601     return ret;
 602 }
 603
 604 static void game_free_aux_info(game_aux_info *aux)
 605 {
 606     assert(!"Shouldn't happen");
 607 }
 608
 609 static char *validate_desc(game_params *params, char *desc)
 610 {
 611     int w = params->w, h = params->h, wh = w * h;
 612     int mlen = (wh*wh+3)/4, glen = (wh+3)/4;
 613
 614     if (strspn(desc, "0123456789abcdefABCDEF") != mlen)
 615         return "Matrix description is wrong length";
 616     if (desc[mlen] != ',')
 617         return "Expected comma after matrix description";
 618     if (strspn(desc+mlen+1, "0123456789abcdefABCDEF") != glen)
 619         return "Grid description is wrong length";
 620     if (desc[mlen+1+glen])
 621         return "Unexpected data after grid description";
 622
 623     return NULL;
 624 }
 625
 626 static game_state *new_game(midend_data *me, game_params *params, char *desc)
 627 {
 628     int w = params->w, h = params->h, wh = w * h;
 629     int mlen = (wh*wh+3)/4;
 630
 631     game_state *state = snew(game_state);
 632
 633     state->w = w;
 634     state->h = h;
 635     state->completed = FALSE;
 636     state->moves = 0;
 637     state->matrix = snew(struct matrix);
 638     state->matrix->refcount = 1;
 639     state->matrix->matrix = snewn(wh*wh, unsigned char);
 640     decode_bitmap(state->matrix->matrix, wh*wh, desc);
 641     state->grid = snewn(wh, unsigned char);
 642     decode_bitmap(state->grid, wh, desc + mlen + 1);
 643
 644     return state;
 645 }
 646
 647 static game_state *dup_game(game_state *state)
 648 {
 649     game_state *ret = snew(game_state);
 650
 651     ret->w = state->w;
 652     ret->h = state->h;
 653     ret->completed = state->completed;
 654     ret->moves = state->moves;
 655     ret->matrix = state->matrix;
 656     state->matrix->refcount++;
 657     ret->grid = snewn(ret->w * ret->h, unsigned char);
 658     memcpy(ret->grid, state->grid, ret->w * ret->h);
 659
 660     return ret;
 661 }
 662
 663 static void free_game(game_state *state)
 664 {
 665     sfree(state->grid);
 666     if (--state->matrix->refcount <= 0) {
 667         sfree(state->matrix->matrix);
 668         sfree(state->matrix);
 669     }
 670     sfree(state);
 671 }
 672
 673 static game_state *solve_game(game_state *state, game_aux_info *aux,
 674                               char **error)
 675 {
 676     return NULL;
 677 }
 678
 679 static char *game_text_format(game_state *state)
 680 {
 681     return NULL;
 682 }
 683
 684 static game_ui *new_ui(game_state *state)
 685 {
 686     return NULL;
 687 }
 688
 689 static void free_ui(game_ui *ui)
 690 {
 691 }
 692
 693 static void game_changed_state(game_ui *ui, game_state *oldstate,
 694                                game_state *newstate)
 695 {
 696 }
 697
 698 struct game_drawstate {
 699     int w, h, started;
 700     unsigned char *tiles;
 701     int tilesize;
 702 };
 703
 704 static game_state *make_move(game_state *from, game_ui *ui, game_drawstate *ds,
 705                              int x, int y, int button)
 706 {
 707     int w = from->w, h = from->h, wh = w * h;
 708     game_state *ret;
 709
 710     if (button == LEFT_BUTTON) {
 711         int tx = FROMCOORD(x), ty = FROMCOORD(y);
 712         if (tx >= 0 && tx < w && ty >= 0 && ty < h) {
 713             int i, j, done;
 714
 715             ret = dup_game(from);
 716
 717             if (!ret->completed)
 718                 ret->moves++;
 719
 720             i = ty * w + tx;
 721
 722             done = TRUE;
 723             for (j = 0; j < wh; j++) {
 724                 ret->grid[j] ^= ret->matrix->matrix[i*wh+j];
 725                 if (ret->grid[j] & 1)
 726                     done = FALSE;
 727             }
 728             if (done)
 729                 ret->completed = TRUE;
 730
 731             return ret;
 732         }
 733     }
 734
 735     return NULL;
 736 }
 737
 738 /* ----------------------------------------------------------------------
 739  * Drawing routines.
 740  */
 741
 742 static void game_size(game_params *params, game_drawstate *ds,
 743                       int *x, int *y, int expand)
 744 {
 745     int tsx, tsy, ts;
 746     /*
 747      * Each window dimension equals the tile size times one more
 748      * than the grid dimension (the border is half the width of the
 749      * tiles).
 750      */
 751     tsx = *x / (params->w + 1);
 752     tsy = *y / (params->h + 1);
 753     ts = min(tsx, tsy);
 754     if (expand)
 755         ds->tilesize = ts;
 756     else
 757         ds->tilesize = min(ts, PREFERRED_TILE_SIZE);
 758
 759     *x = TILE_SIZE * params->w + 2 * BORDER;
 760     *y = TILE_SIZE * params->h + 2 * BORDER;
 761 }
 762
 763 static float *game_colours(frontend *fe, game_state *state, int *ncolours)
 764 {
 765     float *ret = snewn(3 * NCOLOURS, float);
 766
 767     frontend_default_colour(fe, &ret[COL_BACKGROUND * 3]);
 768
 769     ret[COL_WRONG * 3 + 0] = ret[COL_BACKGROUND * 3 + 0] / 3;
 770     ret[COL_WRONG * 3 + 1] = ret[COL_BACKGROUND * 3 + 1] / 3;
 771     ret[COL_WRONG * 3 + 2] = ret[COL_BACKGROUND * 3 + 2] / 3;
 772
 773     ret[COL_RIGHT * 3 + 0] = 1.0F;
 774     ret[COL_RIGHT * 3 + 1] = 1.0F;
 775     ret[COL_RIGHT * 3 + 2] = 1.0F;
 776
 777     ret[COL_GRID * 3 + 0] = ret[COL_BACKGROUND * 3 + 0] / 1.5F;
 778     ret[COL_GRID * 3 + 1] = ret[COL_BACKGROUND * 3 + 1] / 1.5F;
 779     ret[COL_GRID * 3 + 2] = ret[COL_BACKGROUND * 3 + 2] / 1.5F;
 780
 781     ret[COL_DIAG * 3 + 0] = ret[COL_GRID * 3 + 0];
 782     ret[COL_DIAG * 3 + 1] = ret[COL_GRID * 3 + 1];
 783     ret[COL_DIAG * 3 + 2] = ret[COL_GRID * 3 + 2];
 784
 785     *ncolours = NCOLOURS;
 786     return ret;
 787 }
 788
 789 static game_drawstate *game_new_drawstate(game_state *state)
 790 {
 791     struct game_drawstate *ds = snew(struct game_drawstate);
 792     int i;
 793
 794     ds->started = FALSE;
 795     ds->w = state->w;
 796     ds->h = state->h;
 797     ds->tiles = snewn(ds->w*ds->h, unsigned char);
 798     ds->tilesize = 0;                  /* haven't decided yet */
 799     for (i = 0; i < ds->w*ds->h; i++)
 800         ds->tiles[i] = -1;
 801
 802     return ds;
 803 }
 804
 805 static void game_free_drawstate(game_drawstate *ds)
 806 {
 807     sfree(ds->tiles);
 808     sfree(ds);
 809 }
 810
 811 static void draw_tile(frontend *fe, game_drawstate *ds,
 812                       game_state *state, int x, int y, int tile, int anim,
 813                       float animtime)
 814 {
 815     int w = ds->w, h = ds->h, wh = w * h;
 816     int bx = x * TILE_SIZE + BORDER, by = y * TILE_SIZE + BORDER;
 817     int i, j;
 818
 819     clip(fe, bx+1, by+1, TILE_SIZE-1, TILE_SIZE-1);
 820
 821     draw_rect(fe, bx+1, by+1, TILE_SIZE-1, TILE_SIZE-1,
 822               anim ? COL_BACKGROUND : tile & 1 ? COL_WRONG : COL_RIGHT);
 823     if (anim) {
 824         /*
 825          * Draw a polygon indicating that the square is diagonally
 826          * flipping over.
 827          */
 828         int coords[8], colour;
 829
 830         coords[0] = bx + TILE_SIZE;
 831         coords[1] = by;
 832         coords[2] = bx + TILE_SIZE * animtime;
 833         coords[3] = by + TILE_SIZE * animtime;
 834         coords[4] = bx;
 835         coords[5] = by + TILE_SIZE;
 836         coords[6] = bx + TILE_SIZE - TILE_SIZE * animtime;
 837         coords[7] = by + TILE_SIZE - TILE_SIZE * animtime;
 838
 839         colour = (tile & 1 ? COL_WRONG : COL_RIGHT);
 840         if (animtime < 0.5)
 841             colour = COL_WRONG + COL_RIGHT - colour;
 842
 843         draw_polygon(fe, coords, 4, TRUE, colour);
 844         draw_polygon(fe, coords, 4, FALSE, COL_GRID);
 845     }
 846
 847     /*
 848      * Draw a little diagram in the tile which indicates which
 849      * surrounding tiles flip when this one is clicked.
 850      */
 851     for (i = 0; i < h; i++)
 852         for (j = 0; j < w; j++)
 853             if (state->matrix->matrix[(y*w+x)*wh + i*w+j]) {
 854                 int ox = j - x, oy = i - y;
 855                 int td = TILE_SIZE / 16;
 856                 int cx = (bx + TILE_SIZE/2) + (2 * ox - 1) * td;
 857                 int cy = (by + TILE_SIZE/2) + (2 * oy - 1) * td;
 858                 if (ox == 0 && oy == 0)
 859                     draw_rect(fe, cx, cy, 2*td+1, 2*td+1, COL_DIAG);
 860                 else {
 861                     draw_line(fe, cx, cy, cx+2*td, cy, COL_DIAG);
 862                     draw_line(fe, cx, cy+2*td, cx+2*td, cy+2*td, COL_DIAG);
 863                     draw_line(fe, cx, cy, cx, cy+2*td, COL_DIAG);
 864                     draw_line(fe, cx+2*td, cy, cx+2*td, cy+2*td, COL_DIAG);
 865                 }
 866             }
 867
 868     unclip(fe);
 869
 870     draw_update(fe, bx+1, by+1, TILE_SIZE-1, TILE_SIZE-1);
 871 }
 872
 873 static void game_redraw(frontend *fe, game_drawstate *ds, game_state *oldstate,
 874                         game_state *state, int dir, game_ui *ui,
 875                         float animtime, float flashtime)
 876 {
 877     int w = ds->w, h = ds->h, wh = w * h;
 878     int i, flashframe;
 879
 880     if (!ds->started) {
 881         draw_rect(fe, 0, 0, TILE_SIZE * w + 2 * BORDER,
 882                   TILE_SIZE * h + 2 * BORDER, COL_BACKGROUND);
 883
 884         /*
 885          * Draw the grid lines.
 886          */
 887         for (i = 0; i <= w; i++)
 888             draw_line(fe, i * TILE_SIZE + BORDER, BORDER,
 889                       i * TILE_SIZE + BORDER, h * TILE_SIZE + BORDER,
 890                       COL_GRID);
 891         for (i = 0; i <= h; i++)
 892             draw_line(fe, BORDER, i * TILE_SIZE + BORDER,
 893                       w * TILE_SIZE + BORDER, i * TILE_SIZE + BORDER,
 894                       COL_GRID);
 895
 896         draw_update(fe, 0, 0, TILE_SIZE * w + 2 * BORDER,
 897                     TILE_SIZE * h + 2 * BORDER);
 898
 899         ds->started = TRUE;
 900     }
 901
 902     if (flashtime)
 903         flashframe = flashtime / FLASH_FRAME;
 904     else
 905         flashframe = -1;
 906
 907     animtime /= ANIM_TIME;             /* scale it so it goes from 0 to 1 */
 908
 909     for (i = 0; i < wh; i++) {
 910         int x = i % w, y = i / w;
 911         int fx, fy, fd;
 912         int v = state->grid[i];
 913         int vv;
 914
 915         if (flashframe >= 0) {
 916             fx = (w+1)/2 - min(x+1, w-x);
 917             fy = (h+1)/2 - min(y+1, h-y);
 918             fd = max(fx, fy);
 919             if (fd == flashframe)
 920                 v |= 1;
 921             else if (fd == flashframe - 1)
 922                 v &= ~1;
 923         }
 924
 925         if (oldstate && state->grid[i] != oldstate->grid[i])
 926             vv = 255;                  /* means `animated' */
 927         else
 928             vv = v;
 929
 930         if (ds->tiles[i] == 255 || vv == 255 || ds->tiles[i] != vv) {
 931             draw_tile(fe, ds, state, x, y, v, vv == 255, animtime);
 932             ds->tiles[i] = vv;
 933         }
 934     }
 935
 936     {
 937         char buf[256];
 938
 939         sprintf(buf, "%sMoves: %d", state->completed ? "COMPLETED! " : "",
 940                 state->moves);
 941
 942         status_bar(fe, buf);
 943     }
 944 }
 945
 946 static float game_anim_length(game_state *oldstate, game_state *newstate,
 947                               int dir, game_ui *ui)
 948 {
 949     return ANIM_TIME;
 950 }
 951
 952 static float game_flash_length(game_state *oldstate, game_state *newstate,
 953                                int dir, game_ui *ui)
 954 {
 955     if (!oldstate->completed && newstate->completed)
 956         return FLASH_FRAME * (max((newstate->w+1)/2, (newstate->h+1)/2)+1);
 957
 958     return 0.0F;
 959 }
 960
 961 static int game_wants_statusbar(void)
 962 {
 963     return TRUE;
 964 }
 965
 966 static int game_timing_state(game_state *state)
 967 {
 968     return TRUE;
 969 }
 970
 971 #ifdef COMBINED
 972 #define thegame flip
 973 #endif
 974
 975 const struct game thegame = {
 976     "Flip", NULL,
 977     default_params,
 978     game_fetch_preset,
 979     decode_params,
 980     encode_params,
 981     free_params,
 982     dup_params,
 983     TRUE, game_configure, custom_params,
 984     validate_params,
 985     new_game_desc,
 986     game_free_aux_info,
 987     validate_desc,
 988     new_game,
 989     dup_game,
 990     free_game,
 991     FALSE, solve_game,
 992     FALSE, game_text_format,
 993     new_ui,
 994     free_ui,
 995     game_changed_state,
 996     make_move,
 997     game_size,
 998     game_colours,
 999     game_new_drawstate,
1000     game_free_drawstate,
1001     game_redraw,
1002     game_anim_length,
1003     game_flash_length,
1004     game_wants_statusbar,
1005     FALSE, game_timing_state,
1006     0,                                 /* mouse_priorities */
1007 };