fifteen.c

   1 /*
   2  * fifteen.c: standard 15-puzzle.
   3  */
   4
   5 #include <stdio.h>
   6 #include <stdlib.h>
   7 #include <string.h>
   8 #include <assert.h>
   9 #include <ctype.h>
  10 #include <math.h>
  11
  12 #include "puzzles.h"
  13
  14 #define PREFERRED_TILE_SIZE 48
  15 #define TILE_SIZE (ds->tilesize)
  16 #define BORDER    (TILE_SIZE / 2)
  17 #define HIGHLIGHT_WIDTH (TILE_SIZE / 20)
  18 #define COORD(x)  ( (x) * TILE_SIZE + BORDER )
  19 #define FROMCOORD(x)  ( ((x) - BORDER + TILE_SIZE) / TILE_SIZE - 1 )
  20
  21 #define ANIM_TIME 0.13F
  22 #define FLASH_FRAME 0.13F
  23
  24 #define X(state, i) ( (i) % (state)->w )
  25 #define Y(state, i) ( (i) / (state)->w )
  26 #define C(state, x, y) ( (y) * (state)->w + (x) )
  27
  28 enum {
  29     COL_BACKGROUND,
  30     COL_TEXT,
  31     COL_HIGHLIGHT,
  32     COL_LOWLIGHT,
  33     NCOLOURS
  34 };
  35
  36 struct game_params {
  37     int w, h;
  38 };
  39
  40 struct game_state {
  41     int w, h, n;
  42     int *tiles;
  43     int gap_pos;
  44     int completed;
  45     int used_solve;                    /* used to suppress completion flash */
  46     int movecount;
  47 };
  48
  49 static game_params *default_params(void)
  50 {
  51     game_params *ret = snew(game_params);
  52
  53     ret->w = ret->h = 4;
  54
  55     return ret;
  56 }
  57
  58 static int game_fetch_preset(int i, char **name, game_params **params)
  59 {
  60     if (i == 0) {
  61         *params = default_params();
  62         *name = dupstr("4x4");
  63         return TRUE;
  64     }
  65     return FALSE;
  66 }
  67
  68 static void free_params(game_params *params)
  69 {
  70     sfree(params);
  71 }
  72
  73 static game_params *dup_params(const game_params *params)
  74 {
  75     game_params *ret = snew(game_params);
  76     *ret = *params;                    /* structure copy */
  77     return ret;
  78 }
  79
  80 static void decode_params(game_params *ret, char const *string)
  81 {
  82     ret->w = ret->h = atoi(string);
  83     while (*string && isdigit((unsigned char)*string)) string++;
  84     if (*string == 'x') {
  85         string++;
  86         ret->h = atoi(string);
  87     }
  88 }
  89
  90 static char *encode_params(const game_params *params, int full)
  91 {
  92     char data[256];
  93
  94     sprintf(data, "%dx%d", params->w, params->h);
  95
  96     return dupstr(data);
  97 }
  98
  99 static config_item *game_configure(const game_params *params)
 100 {
 101     config_item *ret;
 102     char buf[80];
 103
 104     ret = snewn(3, config_item);
 105
 106     ret[0].name = "Width";
 107     ret[0].type = C_STRING;
 108     sprintf(buf, "%d", params->w);
 109     ret[0].sval = dupstr(buf);
 110     ret[0].ival = 0;
 111
 112     ret[1].name = "Height";
 113     ret[1].type = C_STRING;
 114     sprintf(buf, "%d", params->h);
 115     ret[1].sval = dupstr(buf);
 116     ret[1].ival = 0;
 117
 118     ret[2].name = NULL;
 119     ret[2].type = C_END;
 120     ret[2].sval = NULL;
 121     ret[2].ival = 0;
 122
 123     return ret;
 124 }
 125
 126 static game_params *custom_params(const config_item *cfg)
 127 {
 128     game_params *ret = snew(game_params);
 129
 130     ret->w = atoi(cfg[0].sval);
 131     ret->h = atoi(cfg[1].sval);
 132
 133     return ret;
 134 }
 135
 136 static char *validate_params(const game_params *params, int full)
 137 {
 138     if (params->w < 2 || params->h < 2)
 139         return "Width and height must both be at least two";
 140
 141     return NULL;
 142 }
 143
 144 static int perm_parity(int *perm, int n)
 145 {
 146     int i, j, ret;
 147
 148     ret = 0;
 149
 150     for (i = 0; i < n-1; i++)
 151         for (j = i+1; j < n; j++)
 152             if (perm[i] > perm[j])
 153                 ret = !ret;
 154
 155     return ret;
 156 }
 157
 158 static char *new_game_desc(const game_params *params, random_state *rs,
 159                            char **aux, int interactive)
 160 {
 161     int gap, n, i, x;
 162     int x1, x2, p1, p2, parity;
 163     int *tiles, *used;
 164     char *ret;
 165     int retlen;
 166
 167     n = params->w * params->h;
 168
 169     tiles = snewn(n, int);
 170     used = snewn(n, int);
 171
 172     for (i = 0; i < n; i++) {
 173         tiles[i] = -1;
 174         used[i] = FALSE;
 175     }
 176
 177     gap = random_upto(rs, n);
 178     tiles[gap] = 0;
 179     used[0] = TRUE;
 180
 181     /*
 182      * Place everything else except the last two tiles.
 183      */
 184     for (x = 0, i = n-1; i > 2; i--) {
 185         int k = random_upto(rs, i);
 186         int j;
 187
 188         for (j = 0; j < n; j++)
 189             if (!used[j] && (k-- == 0))
 190                 break;
 191
 192         assert(j < n && !used[j]);
 193         used[j] = TRUE;
 194
 195         while (tiles[x] >= 0)
 196             x++;
 197         assert(x < n);
 198         tiles[x] = j;
 199     }
 200
 201     /*
 202      * Find the last two locations, and the last two pieces.
 203      */
 204     while (tiles[x] >= 0)
 205         x++;
 206     assert(x < n);
 207     x1 = x;
 208     x++;
 209     while (tiles[x] >= 0)
 210         x++;
 211     assert(x < n);
 212     x2 = x;
 213
 214     for (i = 0; i < n; i++)
 215         if (!used[i])
 216             break;
 217     p1 = i;
 218     for (i = p1+1; i < n; i++)
 219         if (!used[i])
 220             break;
 221     p2 = i;
 222
 223     /*
 224      * Determine the required parity of the overall permutation.
 225      * This is the XOR of:
 226      *
 227      *  - The chessboard parity ((x^y)&1) of the gap square. The
 228      *    bottom right counts as even.
 229      *
 230      *  - The parity of n. (The target permutation is 1,...,n-1,0
 231      *    rather than 0,...,n-1; this is a cyclic permutation of
 232      *    the starting point and hence is odd iff n is even.)
 233      */
 234     parity = ((X(params, gap) - (params->w-1)) ^
 235               (Y(params, gap) - (params->h-1)) ^
 236               (n+1)) & 1;
 237
 238     /*
 239      * Try the last two tiles one way round. If that fails, swap
 240      * them.
 241      */
 242     tiles[x1] = p1;
 243     tiles[x2] = p2;
 244     if (perm_parity(tiles, n) != parity) {
 245         tiles[x1] = p2;
 246         tiles[x2] = p1;
 247         assert(perm_parity(tiles, n) == parity);
 248     }
 249
 250     /*
 251      * Now construct the game description, by describing the tile
 252      * array as a simple sequence of comma-separated integers.
 253      */
 254     ret = NULL;
 255     retlen = 0;
 256     for (i = 0; i < n; i++) {
 257         char buf[80];
 258         int k;
 259
 260         k = sprintf(buf, "%d,", tiles[i]);
 261
 262         ret = sresize(ret, retlen + k + 1, char);
 263         strcpy(ret + retlen, buf);
 264         retlen += k;
 265     }
 266     ret[retlen-1] = '\0';              /* delete last comma */
 267
 268     sfree(tiles);
 269     sfree(used);
 270
 271     return ret;
 272 }
 273
 274 static char *validate_desc(const game_params *params, const char *desc)
 275 {
 276     const char *p;
 277     char *err;
 278     int i, area;
 279     int *used;
 280
 281     area = params->w * params->h;
 282     p = desc;
 283     err = NULL;
 284
 285     used = snewn(area, int);
 286     for (i = 0; i < area; i++)
 287         used[i] = FALSE;
 288
 289     for (i = 0; i < area; i++) {
 290         const char *q = p;
 291         int n;
 292
 293         if (*p < '0' || *p > '9') {
 294             err = "Not enough numbers in string";
 295             goto leave;
 296         }
 297         while (*p >= '0' && *p <= '9')
 298             p++;
 299         if (i < area-1 && *p != ',') {
 300             err = "Expected comma after number";
 301             goto leave;
 302         }
 303         else if (i == area-1 && *p) {
 304             err = "Excess junk at end of string";
 305             goto leave;
 306         }
 307         n = atoi(q);
 308         if (n < 0 || n >= area) {
 309             err = "Number out of range";
 310             goto leave;
 311         }
 312         if (used[n]) {
 313             err = "Number used twice";
 314             goto leave;
 315         }
 316         used[n] = TRUE;
 317
 318         if (*p) p++;                   /* eat comma */
 319     }
 320
 321     leave:
 322     sfree(used);
 323     return err;
 324 }
 325
 326 static game_state *new_game(midend *me, const game_params *params,
 327                             const char *desc)
 328 {
 329     game_state *state = snew(game_state);
 330     int i;
 331     const char *p;
 332
 333     state->w = params->w;
 334     state->h = params->h;
 335     state->n = params->w * params->h;
 336     state->tiles = snewn(state->n, int);
 337
 338     state->gap_pos = 0;
 339     p = desc;
 340     i = 0;
 341     for (i = 0; i < state->n; i++) {
 342         assert(*p);
 343         state->tiles[i] = atoi(p);
 344         if (state->tiles[i] == 0)
 345             state->gap_pos = i;
 346         while (*p && *p != ',')
 347             p++;
 348         if (*p) p++;                   /* eat comma */
 349     }
 350     assert(!*p);
 351     assert(state->tiles[state->gap_pos] == 0);
 352
 353     state->completed = state->movecount = 0;
 354     state->used_solve = FALSE;
 355
 356     return state;
 357 }
 358
 359 static game_state *dup_game(const game_state *state)
 360 {
 361     game_state *ret = snew(game_state);
 362
 363     ret->w = state->w;
 364     ret->h = state->h;
 365     ret->n = state->n;
 366     ret->tiles = snewn(state->w * state->h, int);
 367     memcpy(ret->tiles, state->tiles, state->w * state->h * sizeof(int));
 368     ret->gap_pos = state->gap_pos;
 369     ret->completed = state->completed;
 370     ret->movecount = state->movecount;
 371     ret->used_solve = state->used_solve;
 372
 373     return ret;
 374 }
 375
 376 static void free_game(game_state *state)
 377 {
 378     sfree(state->tiles);
 379     sfree(state);
 380 }
 381
 382 static char *solve_game(const game_state *state, const game_state *currstate,
 383                         const char *aux, char **error)
 384 {
 385     return dupstr("S");
 386 }
 387
 388 static int game_can_format_as_text_now(const game_params *params)
 389 {
 390     return TRUE;
 391 }
 392
 393 static char *game_text_format(const game_state *state)
 394 {
 395     char *ret, *p, buf[80];
 396     int x, y, col, maxlen;
 397
 398     /*
 399      * First work out how many characters we need to display each
 400      * number.
 401      */
 402     col = sprintf(buf, "%d", state->n-1);
 403
 404     /*
 405      * Now we know the exact total size of the grid we're going to
 406      * produce: it's got h rows, each containing w lots of col, w-1
 407      * spaces and a trailing newline.
 408      */
 409     maxlen = state->h * state->w * (col+1);
 410
 411     ret = snewn(maxlen+1, char);
 412     p = ret;
 413
 414     for (y = 0; y < state->h; y++) {
 415         for (x = 0; x < state->w; x++) {
 416             int v = state->tiles[state->w*y+x];
 417             if (v == 0)
 418                 sprintf(buf, "%*s", col, "");
 419             else
 420                 sprintf(buf, "%*d", col, v);
 421             memcpy(p, buf, col);
 422             p += col;
 423             if (x+1 == state->w)
 424                 *p++ = '\n';
 425             else
 426                 *p++ = ' ';
 427         }
 428     }
 429
 430     assert(p - ret == maxlen);
 431     *p = '\0';
 432     return ret;
 433 }
 434
 435 static game_ui *new_ui(const game_state *state)
 436 {
 437     return NULL;
 438 }
 439
 440 static void free_ui(game_ui *ui)
 441 {
 442 }
 443
 444 static char *encode_ui(const game_ui *ui)
 445 {
 446     return NULL;
 447 }
 448
 449 static void decode_ui(game_ui *ui, const char *encoding)
 450 {
 451 }
 452
 453 static void game_changed_state(game_ui *ui, const game_state *oldstate,
 454                                const game_state *newstate)
 455 {
 456 }
 457
 458 struct game_drawstate {
 459     int started;
 460     int w, h, bgcolour;
 461     int *tiles;
 462     int tilesize;
 463 };
 464
 465 static int flip_cursor(int button)
 466 {
 467     switch (button) {
 468     case CURSOR_UP: return CURSOR_DOWN;
 469     case CURSOR_DOWN: return CURSOR_UP;
 470     case CURSOR_LEFT: return CURSOR_RIGHT;
 471     case CURSOR_RIGHT: return CURSOR_LEFT;
 472     }
 473     return 0;
 474 }
 475
 476 static void next_move_3x2(int ax, int ay, int bx, int by,
 477                           int gx, int gy, int *dx, int *dy)
 478 {
 479     /* When w = 3 and h = 2 and the tile going in the top left corner
 480      * is at (ax, ay) and the tile going in the bottom left corner is
 481      * at (bx, by) and the blank tile is at (gx, gy), how do you move? */
 482
 483     /* Hard-coded shortest solutions.  Sorry. */
 484     static const unsigned char move[120] = {
 485         1,2,0,1,2,2,
 486         2,0,0,2,0,0,
 487         0,0,2,0,2,0,
 488         0,0,0,2,0,2,
 489         2,0,0,0,2,0,
 490
 491         0,3,0,1,1,1,
 492         3,0,3,2,1,2,
 493         2,1,1,0,1,0,
 494         2,1,2,1,0,1,
 495         1,2,0,2,1,2,
 496
 497         0,1,3,1,3,0,
 498         1,3,1,3,0,3,
 499         0,0,3,3,0,0,
 500         0,0,0,1,2,1,
 501         3,0,0,1,1,1,
 502
 503         3,1,1,1,3,0,
 504         1,1,1,1,1,1,
 505         1,3,1,1,3,0,
 506         1,1,3,3,1,3,
 507         1,3,0,0,0,0
 508     };
 509     static const struct { int dx, dy; } d[4] = {{+1,0},{-1,0},{0,+1},{0,-1}};
 510
 511     int ea = 3*ay + ax, eb = 3*by + bx, eg = 3*gy + gx, v;
 512     if (eb > ea) --eb;
 513     if (eg > ea) --eg;
 514     if (eg > eb) --eg;
 515     v = move[ea + eb*6 + eg*5*6];
 516     *dx = d[v].dx;
 517     *dy = d[v].dy;
 518 }
 519
 520 static void next_move(int nx, int ny, int ox, int oy, int gx, int gy,
 521                       int tx, int ty, int w, int *dx, int *dy)
 522 {
 523     const int to_tile_x = (gx < nx ? +1 : -1);
 524     const int to_goal_x = (gx < tx ? +1 : -1);
 525     const int gap_x_on_goal_side = ((nx-tx) * (nx-gx) > 0);
 526
 527     assert (nx != tx || ny != ty); /* not already in place */
 528     assert (nx != gx || ny != gy); /* not placing the gap */
 529     assert (ty <= ny); /* because we're greedy (and flipping) */
 530     assert (ty <= gy); /* because we're greedy (and flipping) */
 531
 532     /* TODO: define a termination function.  Idea: 0 if solved, or
 533      * the number of moves to solve the next piece plus the number of
 534      * further unsolved pieces times an upper bound on the number of
 535      * moves required to solve any piece.  If such a function can be
 536      * found, we have (termination && (termination => correctness)).
 537      * The catch is our temporary disturbance of 2x3 corners. */
 538
 539     /* handles end-of-row, when 3 and 4 are in the top right 2x3 box */
 540     if (tx == w - 2 &&
 541         ny <= ty + 2 && (nx == tx || nx == tx + 1) &&
 542         oy <= ty + 2 && (ox == tx || ox == tx + 1) &&
 543         gy <= ty + 2 && (gx == tx || gx == tx + 1))
 544     {
 545         next_move_3x2(oy - ty, tx + 1 - ox,
 546                       ny - ty, tx + 1 - nx,
 547                       gy - ty, tx + 1 - gx, dy, dx);
 548         *dx *= -1;
 549         return;
 550     }
 551
 552     if (tx == w - 1) {
 553         if (ny <= ty + 2 && (nx == tx || nx == tx - 1) &&
 554             gy <= ty + 2 && (gx == tx || gx == tx - 1)) {
 555             next_move_3x2(ny - ty, tx - nx, 0, 1, gy - ty, tx - gx, dy, dx);
 556             *dx *= -1;
 557         } else if (gy == ty)
 558             *dy = +1;
 559         else if (nx != tx || ny != ty + 1) {
 560             next_move((w - 1) - nx, ny, -1, -1, (w - 1) - gx, gy,
 561                       0, ty + 1, -1, dx, dy);
 562             *dx *= -1;
 563         } else if (gx == nx)
 564             *dy = -1;
 565         else
 566             *dx = +1;
 567         return;
 568     }
 569
 570     /* note that *dy = -1 is unsafe when gy = ty + 1 and gx < tx */
 571     if (gy < ny)
 572         if (nx == gx || (gy == ty && gx == tx))
 573             *dy = +1;
 574         else if (!gap_x_on_goal_side)
 575             *dx = to_tile_x;
 576         else if (ny - ty > abs(nx - tx))
 577             *dx = to_tile_x;
 578         else *dy = +1;
 579
 580     else if (gy == ny)
 581         if (nx == tx) /* then we know ny > ty */
 582             if (gx > nx || ny > ty + 1)
 583                 *dy = -1; /* ... so this is safe */
 584             else
 585                 *dy = +1;
 586         else if (gap_x_on_goal_side)
 587             *dx = to_tile_x;
 588         else if (gy == ty || (gy == ty + 1 && gx < tx))
 589             *dy = +1;
 590         else
 591             *dy = -1;
 592
 593     else if (nx == tx) /* gy > ny */
 594         if (gx > nx)
 595             *dy = -1;
 596         else
 597             *dx = +1;
 598     else if (gx == nx)
 599         *dx = to_goal_x;
 600     else if (gap_x_on_goal_side)
 601         if (gy == ty + 1 && gx < tx)
 602             *dx = to_tile_x;
 603         else
 604             *dy = -1;
 605
 606     else if (ny - ty > abs(nx - tx))
 607         *dy = -1;
 608     else
 609         *dx = to_tile_x;
 610 }
 611
 612 static int compute_hint(const game_state *state, int *out_x, int *out_y)
 613 {
 614     /* The overall solving process is this:
 615      * 1. Find the next piece to be put in its place
 616      * 2. Move it diagonally towards its place
 617      * 3. Move it horizontally or vertically towards its place
 618      * (Modulo the last two tiles at the end of each row/column)
 619      */
 620
 621     int gx = X(state, state->gap_pos);
 622     int gy = Y(state, state->gap_pos);
 623
 624     int tx, ty, nx, ny, ox, oy, /* {target,next,next2}_{x,y} */ i;
 625     int dx = 0, dy = 0;
 626
 627     /* 1. Find the next piece
 628      * if (there are no more unfinished columns than rows) {
 629      *     fill the top-most row, left to right
 630      * } else { fill the left-most column, top to bottom }
 631      */
 632     const int w = state->w, h = state->h, n = w*h;
 633     int next_piece = 0, next_piece_2 = 0, solr = 0, solc = 0;
 634     int unsolved_rows = h, unsolved_cols = w;
 635
 636     assert(out_x);
 637     assert(out_y);
 638
 639     while (solr < h && solc < w) {
 640         int start, step, stop;
 641         if (unsolved_cols <= unsolved_rows)
 642             start = solr*w + solc, step = 1, stop = unsolved_cols;
 643         else
 644             start = solr*w + solc, step = w, stop = unsolved_rows;
 645         for (i = 0; i < stop; ++i) {
 646             const int j = start + i*step;
 647             if (state->tiles[j] != j + 1) {
 648                 next_piece = j + 1;
 649                 next_piece_2 = next_piece + step;
 650                 break;
 651             }
 652         }
 653         if (i < stop) break;
 654
 655         (unsolved_cols <= unsolved_rows)
 656             ? (++solr, --unsolved_rows)
 657             : (++solc, --unsolved_cols);
 658     }
 659
 660     if (next_piece == n)
 661         return FALSE;
 662
 663     /* 2, 3. Move the next piece towards its place */
 664
 665     /* gx, gy already set */
 666     tx = X(state, next_piece - 1); /* where we're going */
 667     ty = Y(state, next_piece - 1);
 668     for (i = 0; i < n && state->tiles[i] != next_piece; ++i);
 669     nx = X(state, i); /* where we're at */
 670     ny = Y(state, i);
 671     for (i = 0; i < n && state->tiles[i] != next_piece_2; ++i);
 672     ox = X(state, i);
 673     oy = Y(state, i);
 674
 675     if (unsolved_cols <= unsolved_rows)
 676         next_move(nx, ny, ox, oy, gx, gy, tx, ty, w, &dx, &dy);
 677     else
 678         next_move(ny, nx, oy, ox, gy, gx, ty, tx, h, &dy, &dx);
 679
 680     assert (dx || dy);
 681
 682     *out_x = gx + dx;
 683     *out_y = gy + dy;
 684     return TRUE;
 685 }
 686
 687 static char *interpret_move(const game_state *state, game_ui *ui,
 688                             const game_drawstate *ds,
 689                             int x, int y, int button)
 690 {
 691     int cx = X(state, state->gap_pos), nx = cx;
 692     int cy = Y(state, state->gap_pos), ny = cy;
 693     char buf[80];
 694
 695     button &= ~MOD_MASK;
 696
 697     if (button == LEFT_BUTTON) {
 698         nx = FROMCOORD(x);
 699         ny = FROMCOORD(y);
 700         if (nx < 0 || nx >= state->w || ny < 0 || ny >= state->h)
 701             return NULL;               /* out of bounds */
 702     } else if (IS_CURSOR_MOVE(button)) {
 703         static int invert_cursor = -1;
 704         if (invert_cursor == -1) {
 705             char *env = getenv("FIFTEEN_INVERT_CURSOR");
 706             invert_cursor = (env && (env[0] == 'y' || env[0] == 'Y'));
 707         }
 708         button = flip_cursor(button); /* the default */
 709         if (invert_cursor)
 710             button = flip_cursor(button); /* undoes the first flip */
 711         move_cursor(button, &nx, &ny, state->w, state->h, FALSE);
 712     } else if ((button == 'h' || button == 'H') && !state->completed) {
 713         if (!compute_hint(state, &nx, &ny))
 714             return NULL; /* shouldn't happen, since ^^we^^checked^^ */
 715     } else
 716         return NULL;                   /* no move */
 717
 718     /*
 719      * Any click location should be equal to the gap location
 720      * in _precisely_ one coordinate.
 721      */
 722     if ((cx == nx) ^ (cy == ny)) {
 723         sprintf(buf, "M%d,%d", nx, ny);
 724         return dupstr(buf);
 725     }
 726
 727     return NULL;
 728 }
 729
 730 static game_state *execute_move(const game_state *from, const char *move)
 731 {
 732     int gx, gy, dx, dy, ux, uy, up, p;
 733     game_state *ret;
 734
 735     if (!strcmp(move, "S")) {
 736         int i;
 737
 738         ret = dup_game(from);
 739
 740         /*
 741          * Simply replace the grid with a solved one. For this game,
 742          * this isn't a useful operation for actually telling the user
 743          * what they should have done, but it is useful for
 744          * conveniently being able to get hold of a clean state from
 745          * which to practise manoeuvres.
 746          */
 747         for (i = 0; i < ret->n; i++)
 748             ret->tiles[i] = (i+1) % ret->n;
 749         ret->gap_pos = ret->n-1;
 750         ret->used_solve = TRUE;
 751         ret->completed = ret->movecount = 1;
 752
 753         return ret;
 754     }
 755
 756     gx = X(from, from->gap_pos);
 757     gy = Y(from, from->gap_pos);
 758
 759     if (move[0] != 'M' ||
 760         sscanf(move+1, "%d,%d", &dx, &dy) != 2 ||
 761         (dx == gx && dy == gy) || (dx != gx && dy != gy) ||
 762         dx < 0 || dx >= from->w || dy < 0 || dy >= from->h)
 763         return NULL;
 764
 765     /*
 766      * Find the unit displacement from the original gap
 767      * position towards this one.
 768      */
 769     ux = (dx < gx ? -1 : dx > gx ? +1 : 0);
 770     uy = (dy < gy ? -1 : dy > gy ? +1 : 0);
 771     up = C(from, ux, uy);
 772
 773     ret = dup_game(from);
 774
 775     ret->gap_pos = C(from, dx, dy);
 776     assert(ret->gap_pos >= 0 && ret->gap_pos < ret->n);
 777
 778     ret->tiles[ret->gap_pos] = 0;
 779
 780     for (p = from->gap_pos; p != ret->gap_pos; p += up) {
 781         assert(p >= 0 && p < from->n);
 782         ret->tiles[p] = from->tiles[p + up];
 783         ret->movecount++;
 784     }
 785
 786     /*
 787      * See if the game has been completed.
 788      */
 789     if (!ret->completed) {
 790         ret->completed = ret->movecount;
 791         for (p = 0; p < ret->n; p++)
 792             if (ret->tiles[p] != (p < ret->n-1 ? p+1 : 0))
 793                 ret->completed = 0;
 794     }
 795
 796     return ret;
 797 }
 798
 799 /* ----------------------------------------------------------------------
 800  * Drawing routines.
 801  */
 802
 803 static void game_compute_size(const game_params *params, int tilesize,
 804                               int *x, int *y)
 805 {
 806     /* Ick: fake up `ds->tilesize' for macro expansion purposes */
 807     struct { int tilesize; } ads, *ds = &ads;
 808     ads.tilesize = tilesize;
 809
 810     *x = TILE_SIZE * params->w + 2 * BORDER;
 811     *y = TILE_SIZE * params->h + 2 * BORDER;
 812 }
 813
 814 static void game_set_size(drawing *dr, game_drawstate *ds,
 815                           const game_params *params, int tilesize)
 816 {
 817     ds->tilesize = tilesize;
 818 }
 819
 820 static float *game_colours(frontend *fe, int *ncolours)
 821 {
 822     float *ret = snewn(3 * NCOLOURS, float);
 823     int i;
 824
 825     game_mkhighlight(fe, ret, COL_BACKGROUND, COL_HIGHLIGHT, COL_LOWLIGHT);
 826
 827     for (i = 0; i < 3; i++)
 828         ret[COL_TEXT * 3 + i] = 0.0;
 829
 830     *ncolours = NCOLOURS;
 831     return ret;
 832 }
 833
 834 static game_drawstate *game_new_drawstate(drawing *dr, const game_state *state)
 835 {
 836     struct game_drawstate *ds = snew(struct game_drawstate);
 837     int i;
 838
 839     ds->started = FALSE;
 840     ds->w = state->w;
 841     ds->h = state->h;
 842     ds->bgcolour = COL_BACKGROUND;
 843     ds->tiles = snewn(ds->w*ds->h, int);
 844     ds->tilesize = 0;                  /* haven't decided yet */
 845     for (i = 0; i < ds->w*ds->h; i++)
 846         ds->tiles[i] = -1;
 847
 848     return ds;
 849 }
 850
 851 static void game_free_drawstate(drawing *dr, game_drawstate *ds)
 852 {
 853     sfree(ds->tiles);
 854     sfree(ds);
 855 }
 856
 857 static void draw_tile(drawing *dr, game_drawstate *ds, const game_state *state,
 858                       int x, int y, int tile, int flash_colour)
 859 {
 860     if (tile == 0) {
 861         draw_rect(dr, x, y, TILE_SIZE, TILE_SIZE,
 862                   flash_colour);
 863     } else {
 864         int coords[6];
 865         char str[40];
 866
 867         coords[0] = x + TILE_SIZE - 1;
 868         coords[1] = y + TILE_SIZE - 1;
 869         coords[2] = x + TILE_SIZE - 1;
 870         coords[3] = y;
 871         coords[4] = x;
 872         coords[5] = y + TILE_SIZE - 1;
 873         draw_polygon(dr, coords, 3, COL_LOWLIGHT, COL_LOWLIGHT);
 874
 875         coords[0] = x;
 876         coords[1] = y;
 877         draw_polygon(dr, coords, 3, COL_HIGHLIGHT, COL_HIGHLIGHT);
 878
 879         draw_rect(dr, x + HIGHLIGHT_WIDTH, y + HIGHLIGHT_WIDTH,
 880                   TILE_SIZE - 2*HIGHLIGHT_WIDTH, TILE_SIZE - 2*HIGHLIGHT_WIDTH,
 881                   flash_colour);
 882
 883         sprintf(str, "%d", tile);
 884         draw_text(dr, x + TILE_SIZE/2, y + TILE_SIZE/2,
 885                   FONT_VARIABLE, TILE_SIZE/3, ALIGN_VCENTRE | ALIGN_HCENTRE,
 886                   COL_TEXT, str);
 887     }
 888     draw_update(dr, x, y, TILE_SIZE, TILE_SIZE);
 889 }
 890
 891 static void game_redraw(drawing *dr, game_drawstate *ds,
 892                         const game_state *oldstate, const game_state *state,
 893                         int dir, const game_ui *ui,
 894                         float animtime, float flashtime)
 895 {
 896     int i, pass, bgcolour;
 897
 898     if (flashtime > 0) {
 899         int frame = (int)(flashtime / FLASH_FRAME);
 900         bgcolour = (frame % 2 ? COL_LOWLIGHT : COL_HIGHLIGHT);
 901     } else
 902         bgcolour = COL_BACKGROUND;
 903
 904     if (!ds->started) {
 905         int coords[10];
 906
 907         draw_rect(dr, 0, 0,
 908                   TILE_SIZE * state->w + 2 * BORDER,
 909                   TILE_SIZE * state->h + 2 * BORDER, COL_BACKGROUND);
 910         draw_update(dr, 0, 0,
 911                     TILE_SIZE * state->w + 2 * BORDER,
 912                     TILE_SIZE * state->h + 2 * BORDER);
 913
 914         /*
 915          * Recessed area containing the whole puzzle.
 916          */
 917         coords[0] = COORD(state->w) + HIGHLIGHT_WIDTH - 1;
 918         coords[1] = COORD(state->h) + HIGHLIGHT_WIDTH - 1;
 919         coords[2] = COORD(state->w) + HIGHLIGHT_WIDTH - 1;
 920         coords[3] = COORD(0) - HIGHLIGHT_WIDTH;
 921         coords[4] = coords[2] - TILE_SIZE;
 922         coords[5] = coords[3] + TILE_SIZE;
 923         coords[8] = COORD(0) - HIGHLIGHT_WIDTH;
 924         coords[9] = COORD(state->h) + HIGHLIGHT_WIDTH - 1;
 925         coords[6] = coords[8] + TILE_SIZE;
 926         coords[7] = coords[9] - TILE_SIZE;
 927         draw_polygon(dr, coords, 5, COL_HIGHLIGHT, COL_HIGHLIGHT);
 928
 929         coords[1] = COORD(0) - HIGHLIGHT_WIDTH;
 930         coords[0] = COORD(0) - HIGHLIGHT_WIDTH;
 931         draw_polygon(dr, coords, 5, COL_LOWLIGHT, COL_LOWLIGHT);
 932
 933         ds->started = TRUE;
 934     }
 935
 936     /*
 937      * Now draw each tile. We do this in two passes to make
 938      * animation easy.
 939      */
 940     for (pass = 0; pass < 2; pass++) {
 941         for (i = 0; i < state->n; i++) {
 942             int t, t0;
 943             /*
 944              * Figure out what should be displayed at this
 945              * location. It's either a simple tile, or it's a
 946              * transition between two tiles (in which case we say
 947              * -1 because it must always be drawn).
 948              */
 949
 950             if (oldstate && oldstate->tiles[i] != state->tiles[i])
 951                 t = -1;
 952             else
 953                 t = state->tiles[i];
 954
 955             t0 = t;
 956
 957             if (ds->bgcolour != bgcolour ||   /* always redraw when flashing */
 958                 ds->tiles[i] != t || ds->tiles[i] == -1 || t == -1) {
 959                 int x, y;
 960
 961                 /*
 962                  * Figure out what to _actually_ draw, and where to
 963                  * draw it.
 964                  */
 965                 if (t == -1) {
 966                     int x0, y0, x1, y1;
 967                     int j;
 968
 969                     /*
 970                      * On the first pass, just blank the tile.
 971                      */
 972                     if (pass == 0) {
 973                         x = COORD(X(state, i));
 974                         y = COORD(Y(state, i));
 975                         t = 0;
 976                     } else {
 977                         float c;
 978
 979                         t = state->tiles[i];
 980
 981                         /*
 982                          * Don't bother moving the gap; just don't
 983                          * draw it.
 984                          */
 985                         if (t == 0)
 986                             continue;
 987
 988                         /*
 989                          * Find the coordinates of this tile in the old and
 990                          * new states.
 991                          */
 992                         x1 = COORD(X(state, i));
 993                         y1 = COORD(Y(state, i));
 994                         for (j = 0; j < oldstate->n; j++)
 995                             if (oldstate->tiles[j] == state->tiles[i])
 996                                 break;
 997                         assert(j < oldstate->n);
 998                         x0 = COORD(X(state, j));
 999                         y0 = COORD(Y(state, j));
1000
1001                         c = (animtime / ANIM_TIME);
1002                         if (c < 0.0F) c = 0.0F;
1003                         if (c > 1.0F) c = 1.0F;
1004
1005                         x = x0 + (int)(c * (x1 - x0));
1006                         y = y0 + (int)(c * (y1 - y0));
1007                     }
1008
1009                 } else {
1010                     if (pass == 0)
1011                         continue;
1012                     x = COORD(X(state, i));
1013                     y = COORD(Y(state, i));
1014                 }
1015
1016                 draw_tile(dr, ds, state, x, y, t, bgcolour);
1017             }
1018             ds->tiles[i] = t0;
1019         }
1020     }
1021     ds->bgcolour = bgcolour;
1022
1023     /*
1024      * Update the status bar.
1025      */
1026     {
1027         char statusbuf[256];
1028
1029         /*
1030          * Don't show the new status until we're also showing the
1031          * new _state_ - after the game animation is complete.
1032          */
1033         if (oldstate)
1034             state = oldstate;
1035
1036         if (state->used_solve)
1037             sprintf(statusbuf, "Moves since auto-solve: %d",
1038                     state->movecount - state->completed);
1039         else
1040             sprintf(statusbuf, "%sMoves: %d",
1041                     (state->completed ? "COMPLETED! " : ""),
1042                     (state->completed ? state->completed : state->movecount));
1043
1044         status_bar(dr, statusbuf);
1045     }
1046 }
1047
1048 static float game_anim_length(const game_state *oldstate,
1049                               const game_state *newstate, int dir, game_ui *ui)
1050 {
1051     return ANIM_TIME;
1052 }
1053
1054 static float game_flash_length(const game_state *oldstate,
1055                                const game_state *newstate, int dir, game_ui *ui)
1056 {
1057     if (!oldstate->completed && newstate->completed &&
1058         !oldstate->used_solve && !newstate->used_solve)
1059         return 2 * FLASH_FRAME;
1060     else
1061         return 0.0F;
1062 }
1063
1064 static int game_status(const game_state *state)
1065 {
1066     return state->completed ? +1 : 0;
1067 }
1068
1069 static int game_timing_state(const game_state *state, game_ui *ui)
1070 {
1071     return TRUE;
1072 }
1073
1074 static void game_print_size(const game_params *params, float *x, float *y)
1075 {
1076 }
1077
1078 static void game_print(drawing *dr, const game_state *state, int tilesize)
1079 {
1080 }
1081
1082 #ifdef COMBINED
1083 #define thegame fifteen
1084 #endif
1085
1086 const struct game thegame = {
1087     "Fifteen", "games.fifteen", "fifteen",
1088     default_params,
1089     game_fetch_preset,
1090     decode_params,
1091     encode_params,
1092     free_params,
1093     dup_params,
1094     TRUE, game_configure, custom_params,
1095     validate_params,
1096     new_game_desc,
1097     validate_desc,
1098     new_game,
1099     dup_game,
1100     free_game,
1101     TRUE, solve_game,
1102     TRUE, game_can_format_as_text_now, game_text_format,
1103     new_ui,
1104     free_ui,
1105     encode_ui,
1106     decode_ui,
1107     game_changed_state,
1108     interpret_move,
1109     execute_move,
1110     PREFERRED_TILE_SIZE, game_compute_size, game_set_size,
1111     game_colours,
1112     game_new_drawstate,
1113     game_free_drawstate,
1114     game_redraw,
1115     game_anim_length,
1116     game_flash_length,
1117     game_status,
1118     FALSE, FALSE, game_print_size, game_print,
1119     TRUE,                              /* wants_statusbar */
1120     FALSE, game_timing_state,
1121     0,                                 /* flags */
1122 };