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