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