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_ui *new_ui(game_state *state)
 353 {
 354     return NULL;
 355 }
 356
 357 void free_ui(game_ui *ui)
 358 {
 359 }
 360
 361 game_state *make_move(game_state *from, game_ui *ui, int x, int y, int button)
 362 {
 363     int gx, gy, dx, dy, ux, uy, up, p;
 364     game_state *ret;
 365
 366     gx = X(from, from->gap_pos);
 367     gy = Y(from, from->gap_pos);
 368
 369     if (button == CURSOR_RIGHT && gx > 0)
 370         dx = gx - 1, dy = gy;
 371     else if (button == CURSOR_LEFT && gx < from->w-1)
 372         dx = gx + 1, dy = gy;
 373     else if (button == CURSOR_DOWN && gy > 0)
 374         dy = gy - 1, dx = gx;
 375     else if (button == CURSOR_UP && gy < from->h-1)
 376         dy = gy + 1, dx = gx;
 377     else if (button == LEFT_BUTTON) {
 378         dx = FROMCOORD(x);
 379         dy = FROMCOORD(y);
 380         if (dx < 0 || dx >= from->w || dy < 0 || dy >= from->h)
 381             return NULL;               /* out of bounds */
 382         /*
 383          * Any click location should be equal to the gap location
 384          * in _precisely_ one coordinate.
 385          */
 386         if ((dx == gx && dy == gy) || (dx != gx && dy != gy))
 387             return NULL;
 388     } else
 389         return NULL;                   /* no move */
 390
 391     /*
 392      * Find the unit displacement from the original gap
 393      * position towards this one.
 394      */
 395     ux = (dx < gx ? -1 : dx > gx ? +1 : 0);
 396     uy = (dy < gy ? -1 : dy > gy ? +1 : 0);
 397     up = C(from, ux, uy);
 398
 399     ret = dup_game(from);
 400
 401     ret->gap_pos = C(from, dx, dy);
 402     assert(ret->gap_pos >= 0 && ret->gap_pos < ret->n);
 403
 404     ret->tiles[ret->gap_pos] = 0;
 405
 406     for (p = from->gap_pos; p != ret->gap_pos; p += up) {
 407         assert(p >= 0 && p < from->n);
 408         ret->tiles[p] = from->tiles[p + up];
 409         ret->movecount++;
 410     }
 411
 412     /*
 413      * See if the game has been completed.
 414      */
 415     if (!ret->completed) {
 416         ret->completed = ret->movecount;
 417         for (p = 0; p < ret->n; p++)
 418             if (ret->tiles[p] != (p < ret->n-1 ? p+1 : 0))
 419                 ret->completed = 0;
 420     }
 421
 422     return ret;
 423 }
 424
 425 /* ----------------------------------------------------------------------
 426  * Drawing routines.
 427  */
 428
 429 struct game_drawstate {
 430     int started;
 431     int w, h, bgcolour;
 432     int *tiles;
 433 };
 434
 435 void game_size(game_params *params, int *x, int *y)
 436 {
 437     *x = TILE_SIZE * params->w + 2 * BORDER;
 438     *y = TILE_SIZE * params->h + 2 * BORDER;
 439 }
 440
 441 float *game_colours(frontend *fe, game_state *state, int *ncolours)
 442 {
 443     float *ret = snewn(3 * NCOLOURS, float);
 444     int i;
 445     float max;
 446
 447     frontend_default_colour(fe, &ret[COL_BACKGROUND * 3]);
 448
 449     /*
 450      * Drop the background colour so that the highlight is
 451      * noticeably brighter than it while still being under 1.
 452      */
 453     max = ret[COL_BACKGROUND*3];
 454     for (i = 1; i < 3; i++)
 455         if (ret[COL_BACKGROUND*3+i] > max)
 456             max = ret[COL_BACKGROUND*3+i];
 457     if (max * 1.2F > 1.0F) {
 458         for (i = 0; i < 3; i++)
 459             ret[COL_BACKGROUND*3+i] /= (max * 1.2F);
 460     }
 461
 462     for (i = 0; i < 3; i++) {
 463         ret[COL_HIGHLIGHT * 3 + i] = ret[COL_BACKGROUND * 3 + i] * 1.2F;
 464         ret[COL_LOWLIGHT * 3 + i] = ret[COL_BACKGROUND * 3 + i] * 0.8F;
 465         ret[COL_TEXT * 3 + i] = 0.0;
 466     }
 467
 468     *ncolours = NCOLOURS;
 469     return ret;
 470 }
 471
 472 game_drawstate *game_new_drawstate(game_state *state)
 473 {
 474     struct game_drawstate *ds = snew(struct game_drawstate);
 475     int i;
 476
 477     ds->started = FALSE;
 478     ds->w = state->w;
 479     ds->h = state->h;
 480     ds->bgcolour = COL_BACKGROUND;
 481     ds->tiles = snewn(ds->w*ds->h, int);
 482     for (i = 0; i < ds->w*ds->h; i++)
 483         ds->tiles[i] = -1;
 484
 485     return ds;
 486 }
 487
 488 void game_free_drawstate(game_drawstate *ds)
 489 {
 490     sfree(ds->tiles);
 491     sfree(ds);
 492 }
 493
 494 static void draw_tile(frontend *fe, game_state *state, int x, int y,
 495                       int tile, int flash_colour)
 496 {
 497     if (tile == 0) {
 498         draw_rect(fe, x, y, TILE_SIZE, TILE_SIZE,
 499                   flash_colour);
 500     } else {
 501         int coords[6];
 502         char str[40];
 503
 504         coords[0] = x + TILE_SIZE - 1;
 505         coords[1] = y + TILE_SIZE - 1;
 506         coords[2] = x + TILE_SIZE - 1;
 507         coords[3] = y;
 508         coords[4] = x;
 509         coords[5] = y + TILE_SIZE - 1;
 510         draw_polygon(fe, coords, 3, TRUE, COL_LOWLIGHT);
 511         draw_polygon(fe, coords, 3, FALSE, COL_LOWLIGHT);
 512
 513         coords[0] = x;
 514         coords[1] = y;
 515         draw_polygon(fe, coords, 3, TRUE, COL_HIGHLIGHT);
 516         draw_polygon(fe, coords, 3, FALSE, COL_HIGHLIGHT);
 517
 518         draw_rect(fe, x + HIGHLIGHT_WIDTH, y + HIGHLIGHT_WIDTH,
 519                   TILE_SIZE - 2*HIGHLIGHT_WIDTH, TILE_SIZE - 2*HIGHLIGHT_WIDTH,
 520                   flash_colour);
 521
 522         sprintf(str, "%d", tile);
 523         draw_text(fe, x + TILE_SIZE/2, y + TILE_SIZE/2,
 524                   FONT_VARIABLE, TILE_SIZE/3, ALIGN_VCENTRE | ALIGN_HCENTRE,
 525                   COL_TEXT, str);
 526     }
 527     draw_update(fe, x, y, TILE_SIZE, TILE_SIZE);
 528 }
 529
 530 void game_redraw(frontend *fe, game_drawstate *ds, game_state *oldstate,
 531                  game_state *state, game_ui *ui,
 532                  float animtime, float flashtime)
 533 {
 534     int i, pass, bgcolour;
 535
 536     if (flashtime > 0) {
 537         int frame = (int)(flashtime / FLASH_FRAME);
 538         bgcolour = (frame % 2 ? COL_LOWLIGHT : COL_HIGHLIGHT);
 539     } else
 540         bgcolour = COL_BACKGROUND;
 541
 542     if (!ds->started) {
 543         int coords[6];
 544
 545         draw_rect(fe, 0, 0,
 546                   TILE_SIZE * state->w + 2 * BORDER,
 547                   TILE_SIZE * state->h + 2 * BORDER, COL_BACKGROUND);
 548         draw_update(fe, 0, 0,
 549                     TILE_SIZE * state->w + 2 * BORDER,
 550                     TILE_SIZE * state->h + 2 * BORDER);
 551
 552         /*
 553          * Recessed area containing the whole puzzle.
 554          */
 555         coords[0] = COORD(state->w) + HIGHLIGHT_WIDTH - 1;
 556         coords[1] = COORD(state->h) + HIGHLIGHT_WIDTH - 1;
 557         coords[2] = COORD(state->w) + HIGHLIGHT_WIDTH - 1;
 558         coords[3] = COORD(0) - HIGHLIGHT_WIDTH;
 559         coords[4] = COORD(0) - HIGHLIGHT_WIDTH;
 560         coords[5] = COORD(state->h) + HIGHLIGHT_WIDTH - 1;
 561         draw_polygon(fe, coords, 3, TRUE, COL_HIGHLIGHT);
 562         draw_polygon(fe, coords, 3, FALSE, COL_HIGHLIGHT);
 563
 564         coords[1] = COORD(0) - HIGHLIGHT_WIDTH;
 565         coords[0] = COORD(0) - HIGHLIGHT_WIDTH;
 566         draw_polygon(fe, coords, 3, TRUE, COL_LOWLIGHT);
 567         draw_polygon(fe, coords, 3, FALSE, COL_LOWLIGHT);
 568
 569         ds->started = TRUE;
 570     }
 571
 572     /*
 573      * Now draw each tile. We do this in two passes to make
 574      * animation easy.
 575      */
 576     for (pass = 0; pass < 2; pass++) {
 577         for (i = 0; i < state->n; i++) {
 578             int t, t0;
 579             /*
 580              * Figure out what should be displayed at this
 581              * location. It's either a simple tile, or it's a
 582              * transition between two tiles (in which case we say
 583              * -1 because it must always be drawn).
 584              */
 585
 586             if (oldstate && oldstate->tiles[i] != state->tiles[i])
 587                 t = -1;
 588             else
 589                 t = state->tiles[i];
 590
 591             t0 = t;
 592
 593             if (ds->bgcolour != bgcolour ||   /* always redraw when flashing */
 594                 ds->tiles[i] != t || ds->tiles[i] == -1 || t == -1) {
 595                 int x, y;
 596
 597                 /*
 598                  * Figure out what to _actually_ draw, and where to
 599                  * draw it.
 600                  */
 601                 if (t == -1) {
 602                     int x0, y0, x1, y1;
 603                     int j;
 604
 605                     /*
 606                      * On the first pass, just blank the tile.
 607                      */
 608                     if (pass == 0) {
 609                         x = COORD(X(state, i));
 610                         y = COORD(Y(state, i));
 611                         t = 0;
 612                     } else {
 613                         float c;
 614
 615                         t = state->tiles[i];
 616
 617                         /*
 618                          * Don't bother moving the gap; just don't
 619                          * draw it.
 620                          */
 621                         if (t == 0)
 622                             continue;
 623
 624                         /*
 625                          * Find the coordinates of this tile in the old and
 626                          * new states.
 627                          */
 628                         x1 = COORD(X(state, i));
 629                         y1 = COORD(Y(state, i));
 630                         for (j = 0; j < oldstate->n; j++)
 631                             if (oldstate->tiles[j] == state->tiles[i])
 632                                 break;
 633                         assert(j < oldstate->n);
 634                         x0 = COORD(X(state, j));
 635                         y0 = COORD(Y(state, j));
 636
 637                         c = (animtime / ANIM_TIME);
 638                         if (c < 0.0F) c = 0.0F;
 639                         if (c > 1.0F) c = 1.0F;
 640
 641                         x = x0 + (int)(c * (x1 - x0));
 642                         y = y0 + (int)(c * (y1 - y0));
 643                     }
 644
 645                 } else {
 646                     if (pass == 0)
 647                         continue;
 648                     x = COORD(X(state, i));
 649                     y = COORD(Y(state, i));
 650                 }
 651
 652                 draw_tile(fe, state, x, y, t, bgcolour);
 653             }
 654             ds->tiles[i] = t0;
 655         }
 656     }
 657     ds->bgcolour = bgcolour;
 658
 659     /*
 660      * Update the status bar.
 661      */
 662     {
 663         char statusbuf[256];
 664
 665         /*
 666          * Don't show the new status until we're also showing the
 667          * new _state_ - after the game animation is complete.
 668          */
 669         if (oldstate)
 670             state = oldstate;
 671
 672         sprintf(statusbuf, "%sMoves: %d",
 673                 (state->completed ? "COMPLETED! " : ""),
 674                 (state->completed ? state->completed : state->movecount));
 675
 676         status_bar(fe, statusbuf);
 677     }
 678 }
 679
 680 float game_anim_length(game_state *oldstate, game_state *newstate)
 681 {
 682     return ANIM_TIME;
 683 }
 684
 685 float game_flash_length(game_state *oldstate, game_state *newstate)
 686 {
 687     if (!oldstate->completed && newstate->completed)
 688         return 2 * FLASH_FRAME;
 689     else
 690         return 0.0F;
 691 }
 692
 693 int game_wants_statusbar(void)
 694 {
 695     return TRUE;
 696 }