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