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