sixteen.c

   1 /*
   2  * sixteen.c: `16-puzzle', a sliding-tiles jigsaw which differs
   3  * from the 15-puzzle in that you toroidally rotate a row or column
   4  * at a time.
   5  */
   6
   7 #include <stdio.h>
   8 #include <stdlib.h>
   9 #include <string.h>
  10 #include <assert.h>
  11 #include <ctype.h>
  12 #include <math.h>
  13
  14 #include "puzzles.h"
  15
  16 #define TILE_SIZE 48
  17 #define BORDER    TILE_SIZE            /* big border to fill with arrows */
  18 #define HIGHLIGHT_WIDTH (TILE_SIZE / 20)
  19 #define COORD(x)  ( (x) * TILE_SIZE + BORDER )
  20 #define FROMCOORD(x)  ( ((x) - BORDER + 2*TILE_SIZE) / TILE_SIZE - 2 )
  21
  22 #define ANIM_TIME 0.13F
  23 #define FLASH_FRAME 0.13F
  24
  25 #define X(state, i) ( (i) % (state)->w )
  26 #define Y(state, i) ( (i) / (state)->w )
  27 #define C(state, x, y) ( (y) * (state)->w + (x) )
  28
  29 enum {
  30     COL_BACKGROUND,
  31     COL_TEXT,
  32     COL_HIGHLIGHT,
  33     COL_LOWLIGHT,
  34     NCOLOURS
  35 };
  36
  37 struct game_params {
  38     int w, h;
  39     int movetarget;
  40 };
  41
  42 struct game_state {
  43     int w, h, n;
  44     int *tiles;
  45     int completed;
  46     int just_used_solve;               /* used to suppress undo animation */
  47     int used_solve;                    /* used to suppress completion flash */
  48     int movecount, movetarget;
  49     int last_movement_sense;
  50 };
  51
  52 static game_params *default_params(void)
  53 {
  54     game_params *ret = snew(game_params);
  55
  56     ret->w = ret->h = 4;
  57     ret->movetarget = 0;
  58
  59     return ret;
  60 }
  61
  62 static int game_fetch_preset(int i, char **name, game_params **params)
  63 {
  64     game_params *ret;
  65     int w, h;
  66     char buf[80];
  67
  68     switch (i) {
  69       case 0: w = 3, h = 3; break;
  70       case 1: w = 4, h = 3; break;
  71       case 2: w = 4, h = 4; break;
  72       case 3: w = 5, h = 4; break;
  73       case 4: w = 5, h = 5; break;
  74       default: return FALSE;
  75     }
  76
  77     sprintf(buf, "%dx%d", w, h);
  78     *name = dupstr(buf);
  79     *params = ret = snew(game_params);
  80     ret->w = w;
  81     ret->h = h;
  82     ret->movetarget = 0;
  83     return TRUE;
  84 }
  85
  86 static void free_params(game_params *params)
  87 {
  88     sfree(params);
  89 }
  90
  91 static game_params *dup_params(game_params *params)
  92 {
  93     game_params *ret = snew(game_params);
  94     *ret = *params;                    /* structure copy */
  95     return ret;
  96 }
  97
  98 static game_params *decode_params(char const *string)
  99 {
 100     game_params *ret = default_params();
 101
 102     ret->w = ret->h = atoi(string);
 103     while (*string && isdigit(*string)) string++;
 104     if (*string == 'x') {
 105         string++;
 106         ret->h = atoi(string);
 107         while (*string && isdigit((unsigned char)*string))
 108             string++;
 109     }
 110     if (*string == 'm') {
 111         string++;
 112         ret->movetarget = atoi(string);
 113         while (*string && isdigit((unsigned char)*string))
 114             string++;
 115     }
 116
 117     return ret;
 118 }
 119
 120 static char *encode_params(game_params *params)
 121 {
 122     char data[256];
 123
 124     sprintf(data, "%dx%d", params->w, params->h);
 125
 126     return dupstr(data);
 127 }
 128
 129 static config_item *game_configure(game_params *params)
 130 {
 131     config_item *ret;
 132     char buf[80];
 133
 134     ret = snewn(4, config_item);
 135
 136     ret[0].name = "Width";
 137     ret[0].type = C_STRING;
 138     sprintf(buf, "%d", params->w);
 139     ret[0].sval = dupstr(buf);
 140     ret[0].ival = 0;
 141
 142     ret[1].name = "Height";
 143     ret[1].type = C_STRING;
 144     sprintf(buf, "%d", params->h);
 145     ret[1].sval = dupstr(buf);
 146     ret[1].ival = 0;
 147
 148     ret[2].name = "Number of shuffling moves";
 149     ret[2].type = C_STRING;
 150     sprintf(buf, "%d", params->movetarget);
 151     ret[2].sval = dupstr(buf);
 152     ret[2].ival = 0;
 153
 154     ret[3].name = NULL;
 155     ret[3].type = C_END;
 156     ret[3].sval = NULL;
 157     ret[3].ival = 0;
 158
 159     return ret;
 160 }
 161
 162 static game_params *custom_params(config_item *cfg)
 163 {
 164     game_params *ret = snew(game_params);
 165
 166     ret->w = atoi(cfg[0].sval);
 167     ret->h = atoi(cfg[1].sval);
 168     ret->movetarget = atoi(cfg[2].sval);
 169
 170     return ret;
 171 }
 172
 173 static char *validate_params(game_params *params)
 174 {
 175     if (params->w < 2 && params->h < 2)
 176         return "Width and height must both be at least two";
 177
 178     return NULL;
 179 }
 180
 181 static int perm_parity(int *perm, int n)
 182 {
 183     int i, j, ret;
 184
 185     ret = 0;
 186
 187     for (i = 0; i < n-1; i++)
 188         for (j = i+1; j < n; j++)
 189             if (perm[i] > perm[j])
 190                 ret = !ret;
 191
 192     return ret;
 193 }
 194
 195 static char *new_game_seed(game_params *params, random_state *rs,
 196                            game_aux_info **aux)
 197 {
 198     int stop, n, i, x;
 199     int x1, x2, p1, p2;
 200     int *tiles, *used;
 201     char *ret;
 202     int retlen;
 203
 204     n = params->w * params->h;
 205
 206     tiles = snewn(n, int);
 207
 208     if (params->movetarget) {
 209         int prevstart = -1, prevoffset = -1, prevdirection = 0, nrepeats = 0;
 210
 211         /*
 212          * Shuffle the old-fashioned way, by making a series of
 213          * single moves on the grid.
 214          */
 215
 216         for (i = 0; i < n; i++)
 217             tiles[i] = i;
 218
 219         for (i = 0; i < params->movetarget; i++) {
 220             int start, offset, len, direction;
 221             int j, tmp;
 222
 223             /*
 224              * Choose a move to make. We can choose from any row
 225              * or any column.
 226              */
 227             while (1) {
 228                 j = random_upto(rs, params->w + params->h);
 229
 230                 if (j < params->w) {
 231                     /* Column. */
 232                     start = j;
 233                     offset = params->w;
 234                     len = params->h;
 235                 } else {
 236                     /* Row. */
 237                     start = (j - params->w) * params->w;
 238                     offset = 1;
 239                     len = params->w;
 240                 }
 241
 242                 direction = -1 + 2 * random_upto(rs, 2);
 243
 244                 /*
 245                  * To at least _try_ to avoid boring cases, check that
 246                  * this move doesn't directly undo the previous one, or
 247                  * repeat it so many times as to turn it into fewer
 248                  * moves.
 249                  */
 250                 if (start == prevstart && offset == prevoffset) {
 251                     if (direction == -prevdirection)
 252                         continue;      /* inverse of previous move */
 253                     else if (2 * (nrepeats+1) > len)
 254                         continue;      /* previous move repeated too often */
 255                 }
 256
 257                 /* If we didn't `continue', we've found an OK move to make. */
 258                 break;
 259             }
 260
 261             /*
 262              * Now save the move into the `prev' variables.
 263              */
 264             if (start == prevstart && offset == prevoffset) {
 265                 nrepeats++;
 266             } else {
 267                 prevstart = start;
 268                 prevoffset = offset;
 269                 prevdirection = direction;
 270                 nrepeats = 1;
 271             }
 272
 273             /*
 274              * And make it.
 275              */
 276             if (direction < 0) {
 277                 start += (len-1) * offset;
 278                 offset = -offset;
 279             }
 280             tmp = tiles[start];
 281             for (j = 0; j+1 < len; j++)
 282                 tiles[start + j*offset] = tiles[start + (j+1)*offset];
 283             tiles[start + (len-1) * offset] = tmp;
 284         }
 285
 286     } else {
 287
 288         used = snewn(n, int);
 289
 290         for (i = 0; i < n; i++) {
 291             tiles[i] = -1;
 292             used[i] = FALSE;
 293         }
 294
 295         /*
 296          * If both dimensions are odd, there is a parity
 297          * constraint.
 298          */
 299         if (params->w & params->h & 1)
 300             stop = 2;
 301         else
 302             stop = 0;
 303
 304         /*
 305          * Place everything except (possibly) the last two tiles.
 306          */
 307         for (x = 0, i = n; i > stop; i--) {
 308             int k = i > 1 ? random_upto(rs, i) : 0;
 309             int j;
 310
 311             for (j = 0; j < n; j++)
 312                 if (!used[j] && (k-- == 0))
 313                     break;
 314
 315             assert(j < n && !used[j]);
 316             used[j] = TRUE;
 317
 318             while (tiles[x] >= 0)
 319                 x++;
 320             assert(x < n);
 321             tiles[x] = j;
 322         }
 323
 324         if (stop) {
 325             /*
 326              * Find the last two locations, and the last two
 327              * pieces.
 328              */
 329             while (tiles[x] >= 0)
 330                 x++;
 331             assert(x < n);
 332             x1 = x;
 333             x++;
 334             while (tiles[x] >= 0)
 335                 x++;
 336             assert(x < n);
 337             x2 = x;
 338
 339             for (i = 0; i < n; i++)
 340                 if (!used[i])
 341                     break;
 342             p1 = i;
 343             for (i = p1+1; i < n; i++)
 344                 if (!used[i])
 345                     break;
 346             p2 = i;
 347
 348             /*
 349              * Try the last two tiles one way round. If that fails,
 350              * swap them.
 351              */
 352             tiles[x1] = p1;
 353             tiles[x2] = p2;
 354             if (perm_parity(tiles, n) != 0) {
 355                 tiles[x1] = p2;
 356                 tiles[x2] = p1;
 357                 assert(perm_parity(tiles, n) == 0);
 358             }
 359         }
 360
 361         sfree(used);
 362     }
 363
 364     /*
 365      * Now construct the game seed, by describing the tile array as
 366      * a simple sequence of comma-separated integers.
 367      */
 368     ret = NULL;
 369     retlen = 0;
 370     for (i = 0; i < n; i++) {
 371         char buf[80];
 372         int k;
 373
 374         k = sprintf(buf, "%d,", tiles[i]+1);
 375
 376         ret = sresize(ret, retlen + k + 1, char);
 377         strcpy(ret + retlen, buf);
 378         retlen += k;
 379     }
 380     ret[retlen-1] = '\0';              /* delete last comma */
 381
 382     sfree(tiles);
 383
 384     return ret;
 385 }
 386
 387 static void game_free_aux_info(game_aux_info *aux)
 388 {
 389     assert(!"Shouldn't happen");
 390 }
 391
 392
 393 static char *validate_seed(game_params *params, char *seed)
 394 {
 395     char *p, *err;
 396     int i, area;
 397     int *used;
 398
 399     area = params->w * params->h;
 400     p = seed;
 401     err = NULL;
 402
 403     used = snewn(area, int);
 404     for (i = 0; i < area; i++)
 405         used[i] = FALSE;
 406
 407     for (i = 0; i < area; i++) {
 408         char *q = p;
 409         int n;
 410
 411         if (*p < '0' || *p > '9') {
 412             err = "Not enough numbers in string";
 413             goto leave;
 414         }
 415         while (*p >= '0' && *p <= '9')
 416             p++;
 417         if (i < area-1 && *p != ',') {
 418             err = "Expected comma after number";
 419             goto leave;
 420         }
 421         else if (i == area-1 && *p) {
 422             err = "Excess junk at end of string";
 423             goto leave;
 424         }
 425         n = atoi(q);
 426         if (n < 1 || n > area) {
 427             err = "Number out of range";
 428             goto leave;
 429         }
 430         if (used[n-1]) {
 431             err = "Number used twice";
 432             goto leave;
 433         }
 434         used[n-1] = TRUE;
 435
 436         if (*p) p++;                   /* eat comma */
 437     }
 438
 439     leave:
 440     sfree(used);
 441     return err;
 442 }
 443
 444 static game_state *new_game(game_params *params, char *seed)
 445 {
 446     game_state *state = snew(game_state);
 447     int i;
 448     char *p;
 449
 450     state->w = params->w;
 451     state->h = params->h;
 452     state->n = params->w * params->h;
 453     state->tiles = snewn(state->n, int);
 454
 455     p = seed;
 456     i = 0;
 457     for (i = 0; i < state->n; i++) {
 458         assert(*p);
 459         state->tiles[i] = atoi(p);
 460         while (*p && *p != ',')
 461             p++;
 462         if (*p) p++;                   /* eat comma */
 463     }
 464     assert(!*p);
 465
 466     state->completed = state->movecount = 0;
 467     state->movetarget = params->movetarget;
 468     state->used_solve = state->just_used_solve = FALSE;
 469     state->last_movement_sense = 0;
 470
 471     return state;
 472 }
 473
 474 static game_state *dup_game(game_state *state)
 475 {
 476     game_state *ret = snew(game_state);
 477
 478     ret->w = state->w;
 479     ret->h = state->h;
 480     ret->n = state->n;
 481     ret->tiles = snewn(state->w * state->h, int);
 482     memcpy(ret->tiles, state->tiles, state->w * state->h * sizeof(int));
 483     ret->completed = state->completed;
 484     ret->movecount = state->movecount;
 485     ret->movetarget = state->movetarget;
 486     ret->used_solve = state->used_solve;
 487     ret->just_used_solve = state->just_used_solve;
 488     ret->last_movement_sense = state->last_movement_sense;
 489
 490     return ret;
 491 }
 492
 493 static void free_game(game_state *state)
 494 {
 495     sfree(state);
 496 }
 497
 498 static game_state *solve_game(game_state *state, game_aux_info *aux,
 499                               char **error)
 500 {
 501     game_state *ret = dup_game(state);
 502     int i;
 503
 504     /*
 505      * Simply replace the grid with a solved one. For this game,
 506      * this isn't a useful operation for actually telling the user
 507      * what they should have done, but it is useful for
 508      * conveniently being able to get hold of a clean state from
 509      * which to practise manoeuvres.
 510      */
 511     for (i = 0; i < ret->n; i++)
 512         ret->tiles[i] = i+1;
 513     ret->used_solve = ret->just_used_solve = TRUE;
 514     ret->completed = ret->movecount = 1;
 515
 516     return ret;
 517 }
 518
 519 static char *game_text_format(game_state *state)
 520 {
 521     char *ret, *p, buf[80];
 522     int x, y, col, maxlen;
 523
 524     /*
 525      * First work out how many characters we need to display each
 526      * number.
 527      */
 528     col = sprintf(buf, "%d", state->n);
 529
 530     /*
 531      * Now we know the exact total size of the grid we're going to
 532      * produce: it's got h rows, each containing w lots of col, w-1
 533      * spaces and a trailing newline.
 534      */
 535     maxlen = state->h * state->w * (col+1);
 536
 537     ret = snewn(maxlen+1, char);
 538     p = ret;
 539
 540     for (y = 0; y < state->h; y++) {
 541         for (x = 0; x < state->w; x++) {
 542             int v = state->tiles[state->w*y+x];
 543             sprintf(buf, "%*d", col, v);
 544             memcpy(p, buf, col);
 545             p += col;
 546             if (x+1 == state->w)
 547                 *p++ = '\n';
 548             else
 549                 *p++ = ' ';
 550         }
 551     }
 552
 553     assert(p - ret == maxlen);
 554     *p = '\0';
 555     return ret;
 556 }
 557
 558 static game_ui *new_ui(game_state *state)
 559 {
 560     return NULL;
 561 }
 562
 563 static void free_ui(game_ui *ui)
 564 {
 565 }
 566
 567 static game_state *make_move(game_state *from, game_ui *ui,
 568                              int x, int y, int button)
 569 {
 570     int cx, cy;
 571     int dx, dy, tx, ty, n;
 572     game_state *ret;
 573
 574     if (button != LEFT_BUTTON && button != RIGHT_BUTTON)
 575         return NULL;
 576
 577     cx = FROMCOORD(x);
 578     cy = FROMCOORD(y);
 579     if (cx == -1 && cy >= 0 && cy < from->h)
 580         n = from->w, dx = +1, dy = 0;
 581     else if (cx == from->w && cy >= 0 && cy < from->h)
 582         n = from->w, dx = -1, dy = 0;
 583     else if (cy == -1 && cx >= 0 && cx < from->w)
 584         n = from->h, dy = +1, dx = 0;
 585     else if (cy == from->h && cx >= 0 && cx < from->w)
 586         n = from->h, dy = -1, dx = 0;
 587     else
 588         return NULL;                   /* invalid click location */
 589
 590     /* reverse direction if right hand button is pressed */
 591     if (button == RIGHT_BUTTON)
 592     {
 593         dx = -dx; if (dx) cx = from->w - 1 - cx;
 594         dy = -dy; if (dy) cy = from->h - 1 - cy;
 595     }
 596
 597     ret = dup_game(from);
 598     ret->just_used_solve = FALSE;      /* zero this in a hurry */
 599
 600     do {
 601         cx += dx;
 602         cy += dy;
 603         tx = (cx + dx + from->w) % from->w;
 604         ty = (cy + dy + from->h) % from->h;
 605         ret->tiles[C(ret, cx, cy)] = from->tiles[C(from, tx, ty)];
 606     } while (--n > 0);
 607
 608     ret->movecount++;
 609
 610     ret->last_movement_sense = -(dx+dy);
 611
 612     /*
 613      * See if the game has been completed.
 614      */
 615     if (!ret->completed) {
 616         ret->completed = ret->movecount;
 617         for (n = 0; n < ret->n; n++)
 618             if (ret->tiles[n] != n+1)
 619                 ret->completed = FALSE;
 620     }
 621
 622     return ret;
 623 }
 624
 625 /* ----------------------------------------------------------------------
 626  * Drawing routines.
 627  */
 628
 629 struct game_drawstate {
 630     int started;
 631     int w, h, bgcolour;
 632     int *tiles;
 633 };
 634
 635 static void game_size(game_params *params, int *x, int *y)
 636 {
 637     *x = TILE_SIZE * params->w + 2 * BORDER;
 638     *y = TILE_SIZE * params->h + 2 * BORDER;
 639 }
 640
 641 static float *game_colours(frontend *fe, game_state *state, int *ncolours)
 642 {
 643     float *ret = snewn(3 * NCOLOURS, float);
 644     int i;
 645     float max;
 646
 647     frontend_default_colour(fe, &ret[COL_BACKGROUND * 3]);
 648
 649     /*
 650      * Drop the background colour so that the highlight is
 651      * noticeably brighter than it while still being under 1.
 652      */
 653     max = ret[COL_BACKGROUND*3];
 654     for (i = 1; i < 3; i++)
 655         if (ret[COL_BACKGROUND*3+i] > max)
 656             max = ret[COL_BACKGROUND*3+i];
 657     if (max * 1.2F > 1.0F) {
 658         for (i = 0; i < 3; i++)
 659             ret[COL_BACKGROUND*3+i] /= (max * 1.2F);
 660     }
 661
 662     for (i = 0; i < 3; i++) {
 663         ret[COL_HIGHLIGHT * 3 + i] = ret[COL_BACKGROUND * 3 + i] * 1.2F;
 664         ret[COL_LOWLIGHT * 3 + i] = ret[COL_BACKGROUND * 3 + i] * 0.8F;
 665         ret[COL_TEXT * 3 + i] = 0.0;
 666     }
 667
 668     *ncolours = NCOLOURS;
 669     return ret;
 670 }
 671
 672 static game_drawstate *game_new_drawstate(game_state *state)
 673 {
 674     struct game_drawstate *ds = snew(struct game_drawstate);
 675     int i;
 676
 677     ds->started = FALSE;
 678     ds->w = state->w;
 679     ds->h = state->h;
 680     ds->bgcolour = COL_BACKGROUND;
 681     ds->tiles = snewn(ds->w*ds->h, int);
 682     for (i = 0; i < ds->w*ds->h; i++)
 683         ds->tiles[i] = -1;
 684
 685     return ds;
 686 }
 687
 688 static void game_free_drawstate(game_drawstate *ds)
 689 {
 690     sfree(ds->tiles);
 691     sfree(ds);
 692 }
 693
 694 static void draw_tile(frontend *fe, game_state *state, int x, int y,
 695                       int tile, int flash_colour)
 696 {
 697     if (tile == 0) {
 698         draw_rect(fe, x, y, TILE_SIZE, TILE_SIZE,
 699                   flash_colour);
 700     } else {
 701         int coords[6];
 702         char str[40];
 703
 704         coords[0] = x + TILE_SIZE - 1;
 705         coords[1] = y + TILE_SIZE - 1;
 706         coords[2] = x + TILE_SIZE - 1;
 707         coords[3] = y;
 708         coords[4] = x;
 709         coords[5] = y + TILE_SIZE - 1;
 710         draw_polygon(fe, coords, 3, TRUE, COL_LOWLIGHT);
 711         draw_polygon(fe, coords, 3, FALSE, COL_LOWLIGHT);
 712
 713         coords[0] = x;
 714         coords[1] = y;
 715         draw_polygon(fe, coords, 3, TRUE, COL_HIGHLIGHT);
 716         draw_polygon(fe, coords, 3, FALSE, COL_HIGHLIGHT);
 717
 718         draw_rect(fe, x + HIGHLIGHT_WIDTH, y + HIGHLIGHT_WIDTH,
 719                   TILE_SIZE - 2*HIGHLIGHT_WIDTH, TILE_SIZE - 2*HIGHLIGHT_WIDTH,
 720                   flash_colour);
 721
 722         sprintf(str, "%d", tile);
 723         draw_text(fe, x + TILE_SIZE/2, y + TILE_SIZE/2,
 724                   FONT_VARIABLE, TILE_SIZE/3, ALIGN_VCENTRE | ALIGN_HCENTRE,
 725                   COL_TEXT, str);
 726     }
 727     draw_update(fe, x, y, TILE_SIZE, TILE_SIZE);
 728 }
 729
 730 static void draw_arrow(frontend *fe, int x, int y, int xdx, int xdy)
 731 {
 732     int coords[14];
 733     int ydy = -xdx, ydx = xdy;
 734
 735 #define POINT(n, xx, yy) ( \
 736     coords[2*(n)+0] = x + (xx)*xdx + (yy)*ydx, \
 737     coords[2*(n)+1] = y + (xx)*xdy + (yy)*ydy)
 738
 739     POINT(0, TILE_SIZE / 2, 3 * TILE_SIZE / 4);   /* top of arrow */
 740     POINT(1, 3 * TILE_SIZE / 4, TILE_SIZE / 2);   /* right corner */
 741     POINT(2, 5 * TILE_SIZE / 8, TILE_SIZE / 2);   /* right concave */
 742     POINT(3, 5 * TILE_SIZE / 8, TILE_SIZE / 4);   /* bottom right */
 743     POINT(4, 3 * TILE_SIZE / 8, TILE_SIZE / 4);   /* bottom left */
 744     POINT(5, 3 * TILE_SIZE / 8, TILE_SIZE / 2);   /* left concave */
 745     POINT(6,     TILE_SIZE / 4, TILE_SIZE / 2);   /* left corner */
 746
 747     draw_polygon(fe, coords, 7, TRUE, COL_LOWLIGHT);
 748     draw_polygon(fe, coords, 7, FALSE, COL_TEXT);
 749 }
 750
 751 static void game_redraw(frontend *fe, game_drawstate *ds, game_state *oldstate,
 752                  game_state *state, int dir, game_ui *ui,
 753                  float animtime, float flashtime)
 754 {
 755     int i, bgcolour;
 756
 757     if (flashtime > 0) {
 758         int frame = (int)(flashtime / FLASH_FRAME);
 759         bgcolour = (frame % 2 ? COL_LOWLIGHT : COL_HIGHLIGHT);
 760     } else
 761         bgcolour = COL_BACKGROUND;
 762
 763     if (!ds->started) {
 764         int coords[6];
 765
 766         draw_rect(fe, 0, 0,
 767                   TILE_SIZE * state->w + 2 * BORDER,
 768                   TILE_SIZE * state->h + 2 * BORDER, COL_BACKGROUND);
 769         draw_update(fe, 0, 0,
 770                     TILE_SIZE * state->w + 2 * BORDER,
 771                     TILE_SIZE * state->h + 2 * BORDER);
 772
 773         /*
 774          * Recessed area containing the whole puzzle.
 775          */
 776         coords[0] = COORD(state->w) + HIGHLIGHT_WIDTH - 1;
 777         coords[1] = COORD(state->h) + HIGHLIGHT_WIDTH - 1;
 778         coords[2] = COORD(state->w) + HIGHLIGHT_WIDTH - 1;
 779         coords[3] = COORD(0) - HIGHLIGHT_WIDTH;
 780         coords[4] = COORD(0) - HIGHLIGHT_WIDTH;
 781         coords[5] = COORD(state->h) + HIGHLIGHT_WIDTH - 1;
 782         draw_polygon(fe, coords, 3, TRUE, COL_HIGHLIGHT);
 783         draw_polygon(fe, coords, 3, FALSE, COL_HIGHLIGHT);
 784
 785         coords[1] = COORD(0) - HIGHLIGHT_WIDTH;
 786         coords[0] = COORD(0) - HIGHLIGHT_WIDTH;
 787         draw_polygon(fe, coords, 3, TRUE, COL_LOWLIGHT);
 788         draw_polygon(fe, coords, 3, FALSE, COL_LOWLIGHT);
 789
 790         /*
 791          * Arrows for making moves.
 792          */
 793         for (i = 0; i < state->w; i++) {
 794             draw_arrow(fe, COORD(i), COORD(0), +1, 0);
 795             draw_arrow(fe, COORD(i+1), COORD(state->h), -1, 0);
 796         }
 797         for (i = 0; i < state->h; i++) {
 798             draw_arrow(fe, COORD(state->w), COORD(i), 0, +1);
 799             draw_arrow(fe, COORD(0), COORD(i+1), 0, -1);
 800         }
 801
 802         ds->started = TRUE;
 803     }
 804
 805     /*
 806      * Now draw each tile.
 807      */
 808
 809     clip(fe, COORD(0), COORD(0), TILE_SIZE*state->w, TILE_SIZE*state->h);
 810
 811     for (i = 0; i < state->n; i++) {
 812         int t, t0;
 813         /*
 814          * Figure out what should be displayed at this
 815          * location. It's either a simple tile, or it's a
 816          * transition between two tiles (in which case we say
 817          * -1 because it must always be drawn).
 818          */
 819
 820         if (oldstate && oldstate->tiles[i] != state->tiles[i])
 821             t = -1;
 822         else
 823             t = state->tiles[i];
 824
 825         t0 = t;
 826
 827         if (ds->bgcolour != bgcolour ||   /* always redraw when flashing */
 828             ds->tiles[i] != t || ds->tiles[i] == -1 || t == -1) {
 829             int x, y, x2, y2;
 830
 831             /*
 832              * Figure out what to _actually_ draw, and where to
 833              * draw it.
 834              */
 835             if (t == -1) {
 836                 int x0, y0, x1, y1, dx, dy;
 837                 int j;
 838                 float c;
 839                 int sense;
 840
 841                 if (dir < 0) {
 842                     assert(oldstate);
 843                     sense = -oldstate->last_movement_sense;
 844                 } else {
 845                     sense = state->last_movement_sense;
 846                 }
 847
 848                 t = state->tiles[i];
 849
 850                 /*
 851                  * FIXME: must be prepared to draw a double
 852                  * tile in some situations.
 853                  */
 854
 855                 /*
 856                  * Find the coordinates of this tile in the old and
 857                  * new states.
 858                  */
 859                 x1 = COORD(X(state, i));
 860                 y1 = COORD(Y(state, i));
 861                 for (j = 0; j < oldstate->n; j++)
 862                     if (oldstate->tiles[j] == state->tiles[i])
 863                         break;
 864                 assert(j < oldstate->n);
 865                 x0 = COORD(X(state, j));
 866                 y0 = COORD(Y(state, j));
 867
 868                 dx = (x1 - x0);
 869                 if (dx != 0 &&
 870                     dx != TILE_SIZE * sense) {
 871                     dx = (dx < 0 ? dx + TILE_SIZE * state->w :
 872                           dx - TILE_SIZE * state->w);
 873                     assert(abs(dx) == TILE_SIZE);
 874                 }
 875                 dy = (y1 - y0);
 876                 if (dy != 0 &&
 877                     dy != TILE_SIZE * sense) {
 878                     dy = (dy < 0 ? dy + TILE_SIZE * state->h :
 879                           dy - TILE_SIZE * state->h);
 880                     assert(abs(dy) == TILE_SIZE);
 881                 }
 882
 883                 c = (animtime / ANIM_TIME);
 884                 if (c < 0.0F) c = 0.0F;
 885                 if (c > 1.0F) c = 1.0F;
 886
 887                 x = x0 + (int)(c * dx);
 888                 y = y0 + (int)(c * dy);
 889                 x2 = x1 - dx + (int)(c * dx);
 890                 y2 = y1 - dy + (int)(c * dy);
 891             } else {
 892                 x = COORD(X(state, i));
 893                 y = COORD(Y(state, i));
 894                 x2 = y2 = -1;
 895             }
 896
 897             draw_tile(fe, state, x, y, t, bgcolour);
 898             if (x2 != -1 || y2 != -1)
 899                 draw_tile(fe, state, x2, y2, t, bgcolour);
 900         }
 901         ds->tiles[i] = t0;
 902     }
 903
 904     unclip(fe);
 905
 906     ds->bgcolour = bgcolour;
 907
 908     /*
 909      * Update the status bar.
 910      */
 911     {
 912         char statusbuf[256];
 913
 914         /*
 915          * Don't show the new status until we're also showing the
 916          * new _state_ - after the game animation is complete.
 917          */
 918         if (oldstate)
 919             state = oldstate;
 920
 921         if (state->used_solve)
 922             sprintf(statusbuf, "Moves since auto-solve: %d",
 923                     state->movecount - state->completed);
 924         else {
 925             sprintf(statusbuf, "%sMoves: %d",
 926                     (state->completed ? "COMPLETED! " : ""),
 927                     (state->completed ? state->completed : state->movecount));
 928             if (state->movetarget)
 929                 sprintf(statusbuf+strlen(statusbuf), " (target %d)",
 930                         state->movetarget);
 931         }
 932
 933         status_bar(fe, statusbuf);
 934     }
 935 }
 936
 937 static float game_anim_length(game_state *oldstate,
 938                               game_state *newstate, int dir)
 939 {
 940     if ((dir > 0 && newstate->just_used_solve) ||
 941         (dir < 0 && oldstate->just_used_solve))
 942         return 0.0F;
 943     else
 944         return ANIM_TIME;
 945 }
 946
 947 static float game_flash_length(game_state *oldstate,
 948                                game_state *newstate, int dir)
 949 {
 950     if (!oldstate->completed && newstate->completed &&
 951         !oldstate->used_solve && !newstate->used_solve)
 952         return 2 * FLASH_FRAME;
 953     else
 954         return 0.0F;
 955 }
 956
 957 static int game_wants_statusbar(void)
 958 {
 959     return TRUE;
 960 }
 961
 962 #ifdef COMBINED
 963 #define thegame sixteen
 964 #endif
 965
 966 const struct game thegame = {
 967     "Sixteen", "games.sixteen",
 968     default_params,
 969     game_fetch_preset,
 970     decode_params,
 971     encode_params,
 972     free_params,
 973     dup_params,
 974     TRUE, game_configure, custom_params,
 975     validate_params,
 976     new_game_seed,
 977     game_free_aux_info,
 978     validate_seed,
 979     new_game,
 980     dup_game,
 981     free_game,
 982     TRUE, solve_game,
 983     TRUE, game_text_format,
 984     new_ui,
 985     free_ui,
 986     make_move,
 987     game_size,
 988     game_colours,
 989     game_new_drawstate,
 990     game_free_drawstate,
 991     game_redraw,
 992     game_anim_length,
 993     game_flash_length,
 994     game_wants_statusbar,
 995 };