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.13F
  23 #define FLASH_FRAME 0.13F
  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, random_state *rs)
 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 = random_upto(rs, 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 = random_upto(rs, 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 char *validate_seed(game_params *params, char *seed)
 250 {
 251     char *p, *err;
 252     int i, area;
 253     int *used;
 254
 255     area = params->w * params->h;
 256     p = seed;
 257     err = NULL;
 258
 259     used = snewn(area, int);
 260     for (i = 0; i < area; i++)
 261         used[i] = FALSE;
 262
 263     for (i = 0; i < area; i++) {
 264         char *q = p;
 265         int n;
 266
 267         if (*p < '0' || *p > '9') {
 268             err = "Not enough numbers in string";
 269             goto leave;
 270         }
 271         while (*p >= '0' && *p <= '9')
 272             p++;
 273         if (i < area-1 && *p != ',') {
 274             err = "Expected comma after number";
 275             goto leave;
 276         }
 277         else if (i == area-1 && *p) {
 278             err = "Excess junk at end of string";
 279             goto leave;
 280         }
 281         n = atoi(q);
 282         if (n < 0 || n >= area) {
 283             err = "Number out of range";
 284             goto leave;
 285         }
 286         if (used[n]) {
 287             err = "Number used twice";
 288             goto leave;
 289         }
 290         used[n] = TRUE;
 291
 292         if (*p) p++;                   /* eat comma */
 293     }
 294
 295     leave:
 296     sfree(used);
 297     return err;
 298 }
 299
 300 game_state *new_game(game_params *params, char *seed)
 301 {
 302     game_state *state = snew(game_state);
 303     int i;
 304     char *p;
 305
 306     state->w = params->w;
 307     state->h = params->h;
 308     state->n = params->w * params->h;
 309     state->tiles = snewn(state->n, int);
 310
 311     state->gap_pos = 0;
 312     p = seed;
 313     i = 0;
 314     for (i = 0; i < state->n; i++) {
 315         assert(*p);
 316         state->tiles[i] = atoi(p);
 317         if (state->tiles[i] == 0)
 318             state->gap_pos = i;
 319         while (*p && *p != ',')
 320             p++;
 321         if (*p) p++;                   /* eat comma */
 322     }
 323     assert(!*p);
 324     assert(state->tiles[state->gap_pos] == 0);
 325
 326     state->completed = state->movecount = 0;
 327
 328     return state;
 329 }
 330
 331 game_state *dup_game(game_state *state)
 332 {
 333     game_state *ret = snew(game_state);
 334
 335     ret->w = state->w;
 336     ret->h = state->h;
 337     ret->n = state->n;
 338     ret->tiles = snewn(state->w * state->h, int);
 339     memcpy(ret->tiles, state->tiles, state->w * state->h * sizeof(int));
 340     ret->gap_pos = state->gap_pos;
 341     ret->completed = state->completed;
 342     ret->movecount = state->movecount;
 343
 344     return ret;
 345 }
 346
 347 void free_game(game_state *state)
 348 {
 349     sfree(state);
 350 }
 351
 352 game_state *make_move(game_state *from, int x, int y, int button)
 353 {
 354     int gx, gy, dx, dy, ux, uy, up, p;
 355     game_state *ret;
 356
 357     gx = X(from, from->gap_pos);
 358     gy = Y(from, from->gap_pos);
 359
 360     if (button == CURSOR_RIGHT && gx > 0)
 361         dx = gx - 1, dy = gy;
 362     else if (button == CURSOR_LEFT && gx < from->w-1)
 363         dx = gx + 1, dy = gy;
 364     else if (button == CURSOR_DOWN && gy > 0)
 365         dy = gy - 1, dx = gx;
 366     else if (button == CURSOR_UP && gy < from->h-1)
 367         dy = gy + 1, dx = gx;
 368     else if (button == LEFT_BUTTON) {
 369         dx = FROMCOORD(x);
 370         dy = FROMCOORD(y);
 371         if (dx < 0 || dx >= from->w || dy < 0 || dy >= from->h)
 372             return NULL;               /* out of bounds */
 373         /*
 374          * Any click location should be equal to the gap location
 375          * in _precisely_ one coordinate.
 376          */
 377         if ((dx == gx && dy == gy) || (dx != gx && dy != gy))
 378             return NULL;
 379     } else
 380         return NULL;                   /* no move */
 381
 382     /*
 383      * Find the unit displacement from the original gap
 384      * position towards this one.
 385      */
 386     ux = (dx < gx ? -1 : dx > gx ? +1 : 0);
 387     uy = (dy < gy ? -1 : dy > gy ? +1 : 0);
 388     up = C(from, ux, uy);
 389
 390     ret = dup_game(from);
 391
 392     ret->gap_pos = C(from, dx, dy);
 393     assert(ret->gap_pos >= 0 && ret->gap_pos < ret->n);
 394
 395     ret->tiles[ret->gap_pos] = 0;
 396
 397     for (p = from->gap_pos; p != ret->gap_pos; p += up) {
 398         assert(p >= 0 && p < from->n);
 399         ret->tiles[p] = from->tiles[p + up];
 400         ret->movecount++;
 401     }
 402
 403     /*
 404      * See if the game has been completed.
 405      */
 406     if (!ret->completed) {
 407         ret->completed = ret->movecount;
 408         for (p = 0; p < ret->n; p++)
 409             if (ret->tiles[p] != (p < ret->n-1 ? p+1 : 0))
 410                 ret->completed = 0;
 411     }
 412
 413     return ret;
 414 }
 415
 416 /* ----------------------------------------------------------------------
 417  * Drawing routines.
 418  */
 419
 420 struct game_drawstate {
 421     int started;
 422     int w, h, bgcolour;
 423     int *tiles;
 424 };
 425
 426 void game_size(game_params *params, int *x, int *y)
 427 {
 428     *x = TILE_SIZE * params->w + 2 * BORDER;
 429     *y = TILE_SIZE * params->h + 2 * BORDER;
 430 }
 431
 432 float *game_colours(frontend *fe, game_state *state, int *ncolours)
 433 {
 434     float *ret = snewn(3 * NCOLOURS, float);
 435     int i;
 436     float max;
 437
 438     frontend_default_colour(fe, &ret[COL_BACKGROUND * 3]);
 439
 440     /*
 441      * Drop the background colour so that the highlight is
 442      * noticeably brighter than it while still being under 1.
 443      */
 444     max = ret[COL_BACKGROUND*3];
 445     for (i = 1; i < 3; i++)
 446         if (ret[COL_BACKGROUND*3+i] > max)
 447             max = ret[COL_BACKGROUND*3+i];
 448     if (max * 1.2F > 1.0F) {
 449         for (i = 0; i < 3; i++)
 450             ret[COL_BACKGROUND*3+i] /= (max * 1.2F);
 451     }
 452
 453     for (i = 0; i < 3; i++) {
 454         ret[COL_HIGHLIGHT * 3 + i] = ret[COL_BACKGROUND * 3 + i] * 1.2F;
 455         ret[COL_LOWLIGHT * 3 + i] = ret[COL_BACKGROUND * 3 + i] * 0.8F;
 456         ret[COL_TEXT * 3 + i] = 0.0;
 457     }
 458
 459     *ncolours = NCOLOURS;
 460     return ret;
 461 }
 462
 463 game_drawstate *game_new_drawstate(game_state *state)
 464 {
 465     struct game_drawstate *ds = snew(struct game_drawstate);
 466     int i;
 467
 468     ds->started = FALSE;
 469     ds->w = state->w;
 470     ds->h = state->h;
 471     ds->bgcolour = COL_BACKGROUND;
 472     ds->tiles = snewn(ds->w*ds->h, int);
 473     for (i = 0; i < ds->w*ds->h; i++)
 474         ds->tiles[i] = -1;
 475
 476     return ds;
 477 }
 478
 479 void game_free_drawstate(game_drawstate *ds)
 480 {
 481     sfree(ds->tiles);
 482     sfree(ds);
 483 }
 484
 485 static void draw_tile(frontend *fe, game_state *state, int x, int y,
 486                       int tile, int flash_colour)
 487 {
 488     if (tile == 0) {
 489         draw_rect(fe, x, y, TILE_SIZE, TILE_SIZE,
 490                   flash_colour);
 491     } else {
 492         int coords[6];
 493         char str[40];
 494
 495         coords[0] = x + TILE_SIZE - 1;
 496         coords[1] = y + TILE_SIZE - 1;
 497         coords[2] = x + TILE_SIZE - 1;
 498         coords[3] = y;
 499         coords[4] = x;
 500         coords[5] = y + TILE_SIZE - 1;
 501         draw_polygon(fe, coords, 3, TRUE, COL_LOWLIGHT);
 502         draw_polygon(fe, coords, 3, FALSE, COL_LOWLIGHT);
 503
 504         coords[0] = x;
 505         coords[1] = y;
 506         draw_polygon(fe, coords, 3, TRUE, COL_HIGHLIGHT);
 507         draw_polygon(fe, coords, 3, FALSE, COL_HIGHLIGHT);
 508
 509         draw_rect(fe, x + HIGHLIGHT_WIDTH, y + HIGHLIGHT_WIDTH,
 510                   TILE_SIZE - 2*HIGHLIGHT_WIDTH, TILE_SIZE - 2*HIGHLIGHT_WIDTH,
 511                   flash_colour);
 512
 513         sprintf(str, "%d", tile);
 514         draw_text(fe, x + TILE_SIZE/2, y + TILE_SIZE/2,
 515                   FONT_VARIABLE, TILE_SIZE/3, ALIGN_VCENTRE | ALIGN_HCENTRE,
 516                   COL_TEXT, str);
 517     }
 518     draw_update(fe, x, y, TILE_SIZE, TILE_SIZE);
 519 }
 520
 521 void game_redraw(frontend *fe, game_drawstate *ds, game_state *oldstate,
 522                  game_state *state, float animtime, float flashtime)
 523 {
 524     int i, pass, bgcolour;
 525
 526     if (flashtime > 0) {
 527         int frame = (int)(flashtime / FLASH_FRAME);
 528         bgcolour = (frame % 2 ? COL_LOWLIGHT : COL_HIGHLIGHT);
 529     } else
 530         bgcolour = COL_BACKGROUND;
 531
 532     if (!ds->started) {
 533         int coords[6];
 534
 535         draw_rect(fe, 0, 0,
 536                   TILE_SIZE * state->w + 2 * BORDER,
 537                   TILE_SIZE * state->h + 2 * BORDER, COL_BACKGROUND);
 538         draw_update(fe, 0, 0,
 539                     TILE_SIZE * state->w + 2 * BORDER,
 540                     TILE_SIZE * state->h + 2 * BORDER);
 541
 542         /*
 543          * Recessed area containing the whole puzzle.
 544          */
 545         coords[0] = COORD(state->w) + HIGHLIGHT_WIDTH - 1;
 546         coords[1] = COORD(state->h) + HIGHLIGHT_WIDTH - 1;
 547         coords[2] = COORD(state->w) + HIGHLIGHT_WIDTH - 1;
 548         coords[3] = COORD(0) - HIGHLIGHT_WIDTH;
 549         coords[4] = COORD(0) - HIGHLIGHT_WIDTH;
 550         coords[5] = COORD(state->h) + HIGHLIGHT_WIDTH - 1;
 551         draw_polygon(fe, coords, 3, TRUE, COL_HIGHLIGHT);
 552         draw_polygon(fe, coords, 3, FALSE, COL_HIGHLIGHT);
 553
 554         coords[1] = COORD(0) - HIGHLIGHT_WIDTH;
 555         coords[0] = COORD(0) - HIGHLIGHT_WIDTH;
 556         draw_polygon(fe, coords, 3, TRUE, COL_LOWLIGHT);
 557         draw_polygon(fe, coords, 3, FALSE, COL_LOWLIGHT);
 558
 559         ds->started = TRUE;
 560     }
 561
 562     /*
 563      * Now draw each tile. We do this in two passes to make
 564      * animation easy.
 565      */
 566     for (pass = 0; pass < 2; pass++) {
 567         for (i = 0; i < state->n; i++) {
 568             int t, t0;
 569             /*
 570              * Figure out what should be displayed at this
 571              * location. It's either a simple tile, or it's a
 572              * transition between two tiles (in which case we say
 573              * -1 because it must always be drawn).
 574              */
 575
 576             if (oldstate && oldstate->tiles[i] != state->tiles[i])
 577                 t = -1;
 578             else
 579                 t = state->tiles[i];
 580
 581             t0 = t;
 582
 583             if (ds->bgcolour != bgcolour ||   /* always redraw when flashing */
 584                 ds->tiles[i] != t || ds->tiles[i] == -1 || t == -1) {
 585                 int x, y;
 586
 587                 /*
 588                  * Figure out what to _actually_ draw, and where to
 589                  * draw it.
 590                  */
 591                 if (t == -1) {
 592                     int x0, y0, x1, y1;
 593                     int j;
 594
 595                     /*
 596                      * On the first pass, just blank the tile.
 597                      */
 598                     if (pass == 0) {
 599                         x = COORD(X(state, i));
 600                         y = COORD(Y(state, i));
 601                         t = 0;
 602                     } else {
 603                         float c;
 604
 605                         t = state->tiles[i];
 606
 607                         /*
 608                          * Don't bother moving the gap; just don't
 609                          * draw it.
 610                          */
 611                         if (t == 0)
 612                             continue;
 613
 614                         /*
 615                          * Find the coordinates of this tile in the old and
 616                          * new states.
 617                          */
 618                         x1 = COORD(X(state, i));
 619                         y1 = COORD(Y(state, i));
 620                         for (j = 0; j < oldstate->n; j++)
 621                             if (oldstate->tiles[j] == state->tiles[i])
 622                                 break;
 623                         assert(j < oldstate->n);
 624                         x0 = COORD(X(state, j));
 625                         y0 = COORD(Y(state, j));
 626
 627                         c = (animtime / ANIM_TIME);
 628                         if (c < 0.0F) c = 0.0F;
 629                         if (c > 1.0F) c = 1.0F;
 630
 631                         x = x0 + (int)(c * (x1 - x0));
 632                         y = y0 + (int)(c * (y1 - y0));
 633                     }
 634
 635                 } else {
 636                     if (pass == 0)
 637                         continue;
 638                     x = COORD(X(state, i));
 639                     y = COORD(Y(state, i));
 640                 }
 641
 642                 draw_tile(fe, state, x, y, t, bgcolour);
 643             }
 644             ds->tiles[i] = t0;
 645         }
 646     }
 647     ds->bgcolour = bgcolour;
 648
 649     /*
 650      * Update the status bar.
 651      */
 652     {
 653         char statusbuf[256];
 654
 655         /*
 656          * Don't show the new status until we're also showing the
 657          * new _state_ - after the game animation is complete.
 658          */
 659         if (oldstate)
 660             state = oldstate;
 661
 662         sprintf(statusbuf, "%sMoves: %d",
 663                 (state->completed ? "COMPLETED! " : ""),
 664                 (state->completed ? state->completed : state->movecount));
 665
 666         status_bar(fe, statusbuf);
 667     }
 668 }
 669
 670 float game_anim_length(game_state *oldstate, game_state *newstate)
 671 {
 672     return ANIM_TIME;
 673 }
 674
 675 float game_flash_length(game_state *oldstate, game_state *newstate)
 676 {
 677     if (!oldstate->completed && newstate->completed)
 678         return 2 * FLASH_FRAME;
 679     else
 680         return 0.0F;
 681 }
 682
 683 int game_wants_statusbar(void)
 684 {
 685     return TRUE;
 686 }