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