mdw@git.distorted.org.uk Git - sgt/puzzles/blob - 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 <math.h>
  12
  13 #include "puzzles.h"
  14
  15 const char *const game_name = "Sixteen";
  16
  17 #define TILE_SIZE 48
  18 #define BORDER    TILE_SIZE            /* big border to fill with arrows */
  19 #define HIGHLIGHT_WIDTH (TILE_SIZE / 20)
  20 #define COORD(x)  ( (x) * TILE_SIZE + BORDER )
  21 #define FROMCOORD(x)  ( ((x) - BORDER + 2*TILE_SIZE) / TILE_SIZE - 2 )
  22
  23 #define ANIM_TIME 0.1F
  24 #define FLASH_FRAME 0.1F
  25
  26 #define X(state, i) ( (i) % (state)->w )
  27 #define Y(state, i) ( (i) / (state)->w )
  28 #define C(state, x, y) ( (y) * (state)->w + (x) )
  29
  30 enum {
  31     COL_BACKGROUND,
  32     COL_TEXT,
  33     COL_HIGHLIGHT,
  34     COL_LOWLIGHT,
  35     NCOLOURS
  36 };
  37
  38 struct game_params {
  39     int w, h;
  40 };
  41
  42 struct game_state {
  43     int w, h, n;
  44     int *tiles;
  45     int completed;
  46 };
  47
  48 game_params *default_params(void)
  49 {
  50     game_params *ret = snew(game_params);
  51
  52     ret->w = ret->h = 4;
  53
  54     return ret;
  55 }
  56
  57 int game_fetch_preset(int i, char **name, game_params **params)
  58 {
  59     game_params *ret;
  60     int w, h;
  61     char buf[80];
  62
  63     switch (i) {
  64       case 0: w = 3, h = 3; break;
  65       case 1: w = 4, h = 3; break;
  66       case 2: w = 4, h = 4; break;
  67       case 3: w = 5, h = 4; break;
  68       case 4: w = 5, h = 5; break;
  69       default: return FALSE;
  70     }
  71
  72     sprintf(buf, "%dx%d", w, h);
  73     *name = dupstr(buf);
  74     *params = ret = snew(game_params);
  75     ret->w = w;
  76     ret->h = h;
  77     return TRUE;
  78 }
  79
  80 void free_params(game_params *params)
  81 {
  82     sfree(params);
  83 }
  84
  85 game_params *dup_params(game_params *params)
  86 {
  87     game_params *ret = snew(game_params);
  88     *ret = *params;                    /* structure copy */
  89     return ret;
  90 }
  91
  92 int perm_parity(int *perm, int n)
  93 {
  94     int i, j, ret;
  95
  96     ret = 0;
  97
  98     for (i = 0; i < n-1; i++)
  99         for (j = i+1; j < n; j++)
 100             if (perm[i] > perm[j])
 101                 ret = !ret;
 102
 103     return ret;
 104 }
 105
 106 char *new_game_seed(game_params *params)
 107 {
 108     int stop, n, i, x;
 109     int x1, x2, p1, p2;
 110     int *tiles, *used;
 111     char *ret;
 112     int retlen;
 113
 114     n = params->w * params->h;
 115
 116     tiles = snewn(n, int);
 117     used = snewn(n, int);
 118
 119     for (i = 0; i < n; i++) {
 120         tiles[i] = -1;
 121         used[i] = FALSE;
 122     }
 123
 124     /*
 125      * If both dimensions are odd, there is a parity constraint.
 126      */
 127     if (params->w & params->h & 1)
 128         stop = 2;
 129     else
 130         stop = 0;
 131
 132     /*
 133      * Place everything except (possibly) the last two tiles.
 134      */
 135     for (x = 0, i = n; i > stop; i--) {
 136         int k = i > 1 ? rand_upto(i) : 0;
 137         int j;
 138
 139         for (j = 0; j < n; j++)
 140             if (!used[j] && (k-- == 0))
 141                 break;
 142
 143         assert(j < n && !used[j]);
 144         used[j] = TRUE;
 145
 146         while (tiles[x] >= 0)
 147             x++;
 148         assert(x < n);
 149         tiles[x] = j;
 150     }
 151
 152     if (stop) {
 153         /*
 154          * Find the last two locations, and the last two pieces.
 155          */
 156         while (tiles[x] >= 0)
 157             x++;
 158         assert(x < n);
 159         x1 = x;
 160         x++;
 161         while (tiles[x] >= 0)
 162             x++;
 163         assert(x < n);
 164         x2 = x;
 165
 166         for (i = 0; i < n; i++)
 167             if (!used[i])
 168                 break;
 169         p1 = i;
 170         for (i = p1+1; i < n; i++)
 171             if (!used[i])
 172                 break;
 173         p2 = i;
 174
 175         /*
 176          * Try the last two tiles one way round. If that fails, swap
 177          * them.
 178          */
 179         tiles[x1] = p1;
 180         tiles[x2] = p2;
 181         if (perm_parity(tiles, n) != 0) {
 182             tiles[x1] = p2;
 183             tiles[x2] = p1;
 184             assert(perm_parity(tiles, n) == 0);
 185         }
 186     }
 187
 188     /*
 189      * Now construct the game seed, by describing the tile array as
 190      * a simple sequence of comma-separated integers.
 191      */
 192     ret = NULL;
 193     retlen = 0;
 194     for (i = 0; i < n; i++) {
 195         char buf[80];
 196         int k;
 197
 198         k = sprintf(buf, "%d,", tiles[i]+1);
 199
 200         ret = sresize(ret, retlen + k + 1, char);
 201         strcpy(ret + retlen, buf);
 202         retlen += k;
 203     }
 204     ret[retlen-1] = '\0';              /* delete last comma */
 205
 206     sfree(tiles);
 207     sfree(used);
 208
 209     return ret;
 210 }
 211
 212 game_state *new_game(game_params *params, char *seed)
 213 {
 214     game_state *state = snew(game_state);
 215     int i;
 216     char *p;
 217
 218     state->w = params->w;
 219     state->h = params->h;
 220     state->n = params->w * params->h;
 221     state->tiles = snewn(state->n, int);
 222
 223     p = seed;
 224     i = 0;
 225     for (i = 0; i < state->n; i++) {
 226         assert(*p);
 227         state->tiles[i] = atoi(p);
 228         while (*p && *p != ',')
 229             p++;
 230         if (*p) p++;                   /* eat comma */
 231     }
 232     assert(!*p);
 233
 234     state->completed = FALSE;
 235
 236     return state;
 237 }
 238
 239 game_state *dup_game(game_state *state)
 240 {
 241     game_state *ret = snew(game_state);
 242
 243     ret->w = state->w;
 244     ret->h = state->h;
 245     ret->n = state->n;
 246     ret->tiles = snewn(state->w * state->h, int);
 247     memcpy(ret->tiles, state->tiles, state->w * state->h * sizeof(int));
 248     ret->completed = state->completed;
 249
 250     return ret;
 251 }
 252
 253 void free_game(game_state *state)
 254 {
 255     sfree(state);
 256 }
 257
 258 game_state *make_move(game_state *from, int x, int y, int button)
 259 {
 260     int cx, cy;
 261     int dx, dy, tx, ty, n;
 262     game_state *ret;
 263
 264     if (button != LEFT_BUTTON)
 265         return NULL;
 266
 267     cx = FROMCOORD(x);
 268     cy = FROMCOORD(y);
 269     if (cx == -1 && cy >= 0 && cy < from->h)
 270         n = from->w, dx = +1, dy = 0;
 271     else if (cx == from->w && cy >= 0 && cy < from->h)
 272         n = from->w, dx = -1, dy = 0;
 273     else if (cy == -1 && cx >= 0 && cx < from->w)
 274         n = from->h, dy = +1, dx = 0;
 275     else if (cy == from->h && cx >= 0 && cx < from->w)
 276         n = from->h, dy = -1, dx = 0;
 277     else
 278         return NULL;                   /* invalid click location */
 279
 280     ret = dup_game(from);
 281
 282     do {
 283         cx += dx;
 284         cy += dy;
 285         tx = (cx + dx + from->w) % from->w;
 286         ty = (cy + dy + from->h) % from->h;
 287         ret->tiles[C(ret, cx, cy)] = from->tiles[C(from, tx, ty)];
 288     } while (--n > 0);
 289
 290     /*
 291      * See if the game has been completed.
 292      */
 293     if (!ret->completed) {
 294         ret->completed = TRUE;
 295         for (n = 0; n < ret->n; n++)
 296             if (ret->tiles[n] != n+1)
 297                 ret->completed = FALSE;
 298     }
 299
 300     return ret;
 301 }
 302
 303 /* ----------------------------------------------------------------------
 304  * Drawing routines.
 305  */
 306
 307 struct game_drawstate {
 308     int started;
 309     int w, h, bgcolour;
 310     int *tiles;
 311 };
 312
 313 void game_size(game_params *params, int *x, int *y)
 314 {
 315     *x = TILE_SIZE * params->w + 2 * BORDER;
 316     *y = TILE_SIZE * params->h + 2 * BORDER;
 317 }
 318
 319 float *game_colours(frontend *fe, game_state *state, int *ncolours)
 320 {
 321     float *ret = snewn(3 * NCOLOURS, float);
 322     int i;
 323     float max;
 324
 325     frontend_default_colour(fe, &ret[COL_BACKGROUND * 3]);
 326
 327     /*
 328      * Drop the background colour so that the highlight is
 329      * noticeably brighter than it while still being under 1.
 330      */
 331     max = ret[COL_BACKGROUND*3];
 332     for (i = 1; i < 3; i++)
 333         if (ret[COL_BACKGROUND*3+i] > max)
 334             max = ret[COL_BACKGROUND*3+i];
 335     if (max * 1.2F > 1.0F) {
 336         for (i = 0; i < 3; i++)
 337             ret[COL_BACKGROUND*3+i] /= (max * 1.2F);
 338     }
 339
 340     for (i = 0; i < 3; i++) {
 341         ret[COL_HIGHLIGHT * 3 + i] = ret[COL_BACKGROUND * 3 + i] * 1.2F;
 342         ret[COL_LOWLIGHT * 3 + i] = ret[COL_BACKGROUND * 3 + i] * 0.8F;
 343         ret[COL_TEXT * 3 + i] = 0.0;
 344     }
 345
 346     *ncolours = NCOLOURS;
 347     return ret;
 348 }
 349
 350 game_drawstate *game_new_drawstate(game_state *state)
 351 {
 352     struct game_drawstate *ds = snew(struct game_drawstate);
 353     int i;
 354
 355     ds->started = FALSE;
 356     ds->w = state->w;
 357     ds->h = state->h;
 358     ds->bgcolour = COL_BACKGROUND;
 359     ds->tiles = snewn(ds->w*ds->h, int);
 360     for (i = 0; i < ds->w*ds->h; i++)
 361         ds->tiles[i] = -1;
 362
 363     return ds;
 364 }
 365
 366 void game_free_drawstate(game_drawstate *ds)
 367 {
 368     sfree(ds->tiles);
 369     sfree(ds);
 370 }
 371
 372 static void draw_tile(frontend *fe, game_state *state, int x, int y,
 373                       int tile, int flash_colour)
 374 {
 375     if (tile == 0) {
 376         draw_rect(fe, x, y, TILE_SIZE, TILE_SIZE,
 377                   flash_colour);
 378     } else {
 379         int coords[6];
 380         char str[40];
 381
 382         coords[0] = x + TILE_SIZE - 1;
 383         coords[1] = y + TILE_SIZE - 1;
 384         coords[2] = x + TILE_SIZE - 1;
 385         coords[3] = y;
 386         coords[4] = x;
 387         coords[5] = y + TILE_SIZE - 1;
 388         draw_polygon(fe, coords, 3, TRUE, COL_LOWLIGHT);
 389         draw_polygon(fe, coords, 3, FALSE, COL_LOWLIGHT);
 390
 391         coords[0] = x;
 392         coords[1] = y;
 393         draw_polygon(fe, coords, 3, TRUE, COL_HIGHLIGHT);
 394         draw_polygon(fe, coords, 3, FALSE, COL_HIGHLIGHT);
 395
 396         draw_rect(fe, x + HIGHLIGHT_WIDTH, y + HIGHLIGHT_WIDTH,
 397                   TILE_SIZE - 2*HIGHLIGHT_WIDTH, TILE_SIZE - 2*HIGHLIGHT_WIDTH,
 398                   flash_colour);
 399
 400         sprintf(str, "%d", tile);
 401         draw_text(fe, x + TILE_SIZE/2, y + TILE_SIZE/2,
 402                   FONT_VARIABLE, TILE_SIZE/3, ALIGN_VCENTRE | ALIGN_HCENTRE,
 403                   COL_TEXT, str);
 404     }
 405     draw_update(fe, x, y, TILE_SIZE, TILE_SIZE);
 406 }
 407
 408 static void draw_arrow(frontend *fe, int x, int y, int xdx, int xdy)
 409 {
 410     int coords[14];
 411     int ydy = -xdx, ydx = xdy;
 412
 413 #define POINT(n, xx, yy) ( \
 414     coords[2*(n)+0] = x + (xx)*xdx + (yy)*ydx, \
 415     coords[2*(n)+1] = y + (xx)*xdy + (yy)*ydy)
 416
 417     POINT(0, TILE_SIZE / 2, 3 * TILE_SIZE / 4);   /* top of arrow */
 418     POINT(1, 3 * TILE_SIZE / 4, TILE_SIZE / 2);   /* right corner */
 419     POINT(2, 5 * TILE_SIZE / 8, TILE_SIZE / 2);   /* right concave */
 420     POINT(3, 5 * TILE_SIZE / 8, TILE_SIZE / 4);   /* bottom right */
 421     POINT(4, 3 * TILE_SIZE / 8, TILE_SIZE / 4);   /* bottom left */
 422     POINT(5, 3 * TILE_SIZE / 8, TILE_SIZE / 2);   /* left concave */
 423     POINT(6,     TILE_SIZE / 4, TILE_SIZE / 2);   /* left corner */
 424
 425     draw_polygon(fe, coords, 7, TRUE, COL_LOWLIGHT);
 426     draw_polygon(fe, coords, 7, FALSE, COL_TEXT);
 427 }
 428
 429 void game_redraw(frontend *fe, game_drawstate *ds, game_state *oldstate,
 430                  game_state *state, float animtime, float flashtime)
 431 {
 432     int i, pass, bgcolour;
 433
 434     if (flashtime > 0) {
 435         int frame = (int)(flashtime / FLASH_FRAME);
 436         bgcolour = (frame % 2 ? COL_LOWLIGHT : COL_HIGHLIGHT);
 437     } else
 438         bgcolour = COL_BACKGROUND;
 439
 440     if (!ds->started) {
 441         int coords[6];
 442
 443         draw_rect(fe, 0, 0,
 444                   TILE_SIZE * state->w + 2 * BORDER,
 445                   TILE_SIZE * state->h + 2 * BORDER, COL_BACKGROUND);
 446         draw_update(fe, 0, 0,
 447                     TILE_SIZE * state->w + 2 * BORDER,
 448                     TILE_SIZE * state->h + 2 * BORDER);
 449
 450         /*
 451          * Recessed area containing the whole puzzle.
 452          */
 453         coords[0] = COORD(state->w) + HIGHLIGHT_WIDTH - 1;
 454         coords[1] = COORD(state->h) + HIGHLIGHT_WIDTH - 1;
 455         coords[2] = COORD(state->w) + HIGHLIGHT_WIDTH - 1;
 456         coords[3] = COORD(0) - HIGHLIGHT_WIDTH;
 457         coords[4] = COORD(0) - HIGHLIGHT_WIDTH;
 458         coords[5] = COORD(state->h) + HIGHLIGHT_WIDTH - 1;
 459         draw_polygon(fe, coords, 3, TRUE, COL_HIGHLIGHT);
 460         draw_polygon(fe, coords, 3, FALSE, COL_HIGHLIGHT);
 461
 462         coords[1] = COORD(0) - HIGHLIGHT_WIDTH;
 463         coords[0] = COORD(0) - HIGHLIGHT_WIDTH;
 464         draw_polygon(fe, coords, 3, TRUE, COL_LOWLIGHT);
 465         draw_polygon(fe, coords, 3, FALSE, COL_LOWLIGHT);
 466
 467         /*
 468          * Arrows for making moves.
 469          */
 470         for (i = 0; i < state->w; i++) {
 471             draw_arrow(fe, COORD(i), COORD(0), +1, 0);
 472             draw_arrow(fe, COORD(i+1), COORD(state->h), -1, 0);
 473         }
 474         for (i = 0; i < state->h; i++) {
 475             draw_arrow(fe, COORD(state->w), COORD(i), 0, +1);
 476             draw_arrow(fe, COORD(0), COORD(i+1), 0, -1);
 477         }
 478
 479         ds->started = TRUE;
 480     }
 481
 482     /*
 483      * Now draw each tile. We do this in two passes to make
 484      * animation easy.
 485      */
 486
 487     clip(fe, COORD(0), COORD(0), TILE_SIZE*state->w, TILE_SIZE*state->h);
 488
 489     for (pass = 0; pass < 2; pass++) {
 490         for (i = 0; i < state->n; i++) {
 491             int t, t0;
 492             /*
 493              * Figure out what should be displayed at this
 494              * location. It's either a simple tile, or it's a
 495              * transition between two tiles (in which case we say
 496              * -1 because it must always be drawn).
 497              */
 498
 499             if (oldstate && oldstate->tiles[i] != state->tiles[i])
 500                 t = -1;
 501             else
 502                 t = state->tiles[i];
 503
 504             t0 = t;
 505
 506             if (ds->bgcolour != bgcolour ||   /* always redraw when flashing */
 507                 ds->tiles[i] != t || ds->tiles[i] == -1 || t == -1) {
 508                 int x, y, x2, y2;
 509
 510                 /*
 511                  * Figure out what to _actually_ draw, and where to
 512                  * draw it.
 513                  */
 514                 if (t == -1) {
 515                     int x0, y0, x1, y1, dx, dy;
 516                     int j;
 517
 518                     /*
 519                      * On the first pass, just blank the tile.
 520                      */
 521                     if (pass == 0) {
 522                         x = COORD(X(state, i));
 523                         y = COORD(Y(state, i));
 524                         x2 = y2 = -1;
 525                         t = 0;
 526                     } else {
 527                         float c;
 528
 529                         t = state->tiles[i];
 530
 531                         /*
 532                          * FIXME: must be prepared to draw a double
 533                          * tile in some situations.
 534                          */
 535
 536                         /*
 537                          * Find the coordinates of this tile in the old and
 538                          * new states.
 539                          */
 540                         x1 = COORD(X(state, i));
 541                         y1 = COORD(Y(state, i));
 542                         for (j = 0; j < oldstate->n; j++)
 543                             if (oldstate->tiles[j] == state->tiles[i])
 544                                 break;
 545                         assert(j < oldstate->n);
 546                         x0 = COORD(X(state, j));
 547                         y0 = COORD(Y(state, j));
 548
 549                         dx = (x1 - x0);
 550                         if (abs(dx) > TILE_SIZE) {
 551                             dx = (dx < 0 ? dx + TILE_SIZE * state->w :
 552                                   dx - TILE_SIZE * state->w);
 553                             assert(abs(dx) == TILE_SIZE);
 554                         }
 555                         dy = (y1 - y0);
 556                         if (abs(dy) > TILE_SIZE) {
 557                             dy = (dy < 0 ? dy + TILE_SIZE * state->h :
 558                                   dy - TILE_SIZE * state->h);
 559                             assert(abs(dy) == TILE_SIZE);
 560                         }
 561
 562                         c = (animtime / ANIM_TIME);
 563                         if (c < 0.0F) c = 0.0F;
 564                         if (c > 1.0F) c = 1.0F;
 565
 566                         x = x0 + (int)(c * dx);
 567                         y = y0 + (int)(c * dy);
 568                         x2 = x1 - dx + (int)(c * dx);
 569                         y2 = y1 - dy + (int)(c * dy);
 570                     }
 571
 572                 } else {
 573                     if (pass == 0)
 574                         continue;
 575                     x = COORD(X(state, i));
 576                     y = COORD(Y(state, i));
 577                     x2 = y2 = -1;
 578                 }
 579
 580                 draw_tile(fe, state, x, y, t, bgcolour);
 581                 if (x2 != -1 || y2 != -1)
 582                     draw_tile(fe, state, x2, y2, t, bgcolour);
 583             }
 584             ds->tiles[i] = t0;
 585         }
 586     }
 587
 588     unclip(fe);
 589
 590     ds->bgcolour = bgcolour;
 591 }
 592
 593 float game_anim_length(game_state *oldstate, game_state *newstate)
 594 {
 595     return ANIM_TIME;
 596 }
 597
 598 float game_flash_length(game_state *oldstate, game_state *newstate)
 599 {
 600     if (!oldstate->completed && newstate->completed)
 601         return 2 * FLASH_FRAME;
 602     else
 603         return 0.0F;
 604 }