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, and therefore also the top left, count as
 204      *    even.
 205      *
 206      *  - The parity of n. (The target permutation is 1,...,n-1,0
 207      *    rather than 0,...,n-1; this is a cyclic permutation of
 208      *    the starting point and hence is odd iff n is even.)
 209      */
 210     parity = (X(params, gap) ^ Y(params, gap) ^ (n+1)) & 1;
 211
 212     /*
 213      * Try the last two tiles one way round. If that fails, swap
 214      * them.
 215      */
 216     tiles[x1] = p1;
 217     tiles[x2] = p2;
 218     if (perm_parity(tiles, n) != parity) {
 219         tiles[x1] = p2;
 220         tiles[x2] = p1;
 221         assert(perm_parity(tiles, n) == parity);
 222     }
 223
 224     /*
 225      * Now construct the game seed, by describing the tile array as
 226      * a simple sequence of comma-separated integers.
 227      */
 228     ret = NULL;
 229     retlen = 0;
 230     for (i = 0; i < n; i++) {
 231         char buf[80];
 232         int k;
 233
 234         k = sprintf(buf, "%d,", tiles[i]);
 235
 236         ret = sresize(ret, retlen + k + 1, char);
 237         strcpy(ret + retlen, buf);
 238         retlen += k;
 239     }
 240     ret[retlen-1] = '\0';              /* delete last comma */
 241
 242     sfree(tiles);
 243     sfree(used);
 244
 245     return ret;
 246 }
 247
 248 game_state *new_game(game_params *params, char *seed)
 249 {
 250     game_state *state = snew(game_state);
 251     int i;
 252     char *p;
 253
 254     state->w = params->w;
 255     state->h = params->h;
 256     state->n = params->w * params->h;
 257     state->tiles = snewn(state->n, int);
 258
 259     state->gap_pos = 0;
 260     p = seed;
 261     i = 0;
 262     for (i = 0; i < state->n; i++) {
 263         assert(*p);
 264         state->tiles[i] = atoi(p);
 265         if (state->tiles[i] == 0)
 266             state->gap_pos = i;
 267         while (*p && *p != ',')
 268             p++;
 269         if (*p) p++;                   /* eat comma */
 270     }
 271     assert(!*p);
 272     assert(state->tiles[state->gap_pos] == 0);
 273
 274     state->completed = state->movecount = 0;
 275
 276     return state;
 277 }
 278
 279 game_state *dup_game(game_state *state)
 280 {
 281     game_state *ret = snew(game_state);
 282
 283     ret->w = state->w;
 284     ret->h = state->h;
 285     ret->n = state->n;
 286     ret->tiles = snewn(state->w * state->h, int);
 287     memcpy(ret->tiles, state->tiles, state->w * state->h * sizeof(int));
 288     ret->gap_pos = state->gap_pos;
 289     ret->completed = state->completed;
 290     ret->movecount = state->movecount;
 291
 292     return ret;
 293 }
 294
 295 void free_game(game_state *state)
 296 {
 297     sfree(state);
 298 }
 299
 300 game_state *make_move(game_state *from, int x, int y, int button)
 301 {
 302     int gx, gy, dx, dy, ux, uy, up, p;
 303     game_state *ret;
 304
 305     gx = X(from, from->gap_pos);
 306     gy = Y(from, from->gap_pos);
 307
 308     if (button == CURSOR_RIGHT && gx > 0)
 309         dx = gx - 1, dy = gy;
 310     else if (button == CURSOR_LEFT && gx < from->w-1)
 311         dx = gx + 1, dy = gy;
 312     else if (button == CURSOR_DOWN && gy > 0)
 313         dy = gy - 1, dx = gx;
 314     else if (button == CURSOR_UP && gy < from->h-1)
 315         dy = gy + 1, dx = gx;
 316     else if (button == LEFT_BUTTON) {
 317         dx = FROMCOORD(x);
 318         dy = FROMCOORD(y);
 319         if (dx < 0 || dx >= from->w || dy < 0 || dy >= from->h)
 320             return NULL;               /* out of bounds */
 321         /*
 322          * Any click location should be equal to the gap location
 323          * in _precisely_ one coordinate.
 324          */
 325         if ((dx == gx && dy == gy) || (dx != gx && dy != gy))
 326             return NULL;
 327     } else
 328         return NULL;                   /* no move */
 329
 330     /*
 331      * Find the unit displacement from the original gap
 332      * position towards this one.
 333      */
 334     ux = (dx < gx ? -1 : dx > gx ? +1 : 0);
 335     uy = (dy < gy ? -1 : dy > gy ? +1 : 0);
 336     up = C(from, ux, uy);
 337
 338     ret = dup_game(from);
 339
 340     ret->gap_pos = C(from, dx, dy);
 341     assert(ret->gap_pos >= 0 && ret->gap_pos < ret->n);
 342
 343     ret->tiles[ret->gap_pos] = 0;
 344
 345     for (p = from->gap_pos; p != ret->gap_pos; p += up) {
 346         assert(p >= 0 && p < from->n);
 347         ret->tiles[p] = from->tiles[p + up];
 348         ret->movecount++;
 349     }
 350
 351     /*
 352      * See if the game has been completed.
 353      */
 354     if (!ret->completed) {
 355         ret->completed = ret->movecount;
 356         for (p = 0; p < ret->n; p++)
 357             if (ret->tiles[p] != (p < ret->n-1 ? p+1 : 0))
 358                 ret->completed = 0;
 359     }
 360
 361     return ret;
 362 }
 363
 364 /* ----------------------------------------------------------------------
 365  * Drawing routines.
 366  */
 367
 368 struct game_drawstate {
 369     int started;
 370     int w, h, bgcolour;
 371     int *tiles;
 372 };
 373
 374 void game_size(game_params *params, int *x, int *y)
 375 {
 376     *x = TILE_SIZE * params->w + 2 * BORDER;
 377     *y = TILE_SIZE * params->h + 2 * BORDER;
 378 }
 379
 380 float *game_colours(frontend *fe, game_state *state, int *ncolours)
 381 {
 382     float *ret = snewn(3 * NCOLOURS, float);
 383     int i;
 384     float max;
 385
 386     frontend_default_colour(fe, &ret[COL_BACKGROUND * 3]);
 387
 388     /*
 389      * Drop the background colour so that the highlight is
 390      * noticeably brighter than it while still being under 1.
 391      */
 392     max = ret[COL_BACKGROUND*3];
 393     for (i = 1; i < 3; i++)
 394         if (ret[COL_BACKGROUND*3+i] > max)
 395             max = ret[COL_BACKGROUND*3+i];
 396     if (max * 1.2F > 1.0F) {
 397         for (i = 0; i < 3; i++)
 398             ret[COL_BACKGROUND*3+i] /= (max * 1.2F);
 399     }
 400
 401     for (i = 0; i < 3; i++) {
 402         ret[COL_HIGHLIGHT * 3 + i] = ret[COL_BACKGROUND * 3 + i] * 1.2F;
 403         ret[COL_LOWLIGHT * 3 + i] = ret[COL_BACKGROUND * 3 + i] * 0.8F;
 404         ret[COL_TEXT * 3 + i] = 0.0;
 405     }
 406
 407     *ncolours = NCOLOURS;
 408     return ret;
 409 }
 410
 411 game_drawstate *game_new_drawstate(game_state *state)
 412 {
 413     struct game_drawstate *ds = snew(struct game_drawstate);
 414     int i;
 415
 416     ds->started = FALSE;
 417     ds->w = state->w;
 418     ds->h = state->h;
 419     ds->bgcolour = COL_BACKGROUND;
 420     ds->tiles = snewn(ds->w*ds->h, int);
 421     for (i = 0; i < ds->w*ds->h; i++)
 422         ds->tiles[i] = -1;
 423
 424     return ds;
 425 }
 426
 427 void game_free_drawstate(game_drawstate *ds)
 428 {
 429     sfree(ds->tiles);
 430     sfree(ds);
 431 }
 432
 433 static void draw_tile(frontend *fe, game_state *state, int x, int y,
 434                       int tile, int flash_colour)
 435 {
 436     if (tile == 0) {
 437         draw_rect(fe, x, y, TILE_SIZE, TILE_SIZE,
 438                   flash_colour);
 439     } else {
 440         int coords[6];
 441         char str[40];
 442
 443         coords[0] = x + TILE_SIZE - 1;
 444         coords[1] = y + TILE_SIZE - 1;
 445         coords[2] = x + TILE_SIZE - 1;
 446         coords[3] = y;
 447         coords[4] = x;
 448         coords[5] = y + TILE_SIZE - 1;
 449         draw_polygon(fe, coords, 3, TRUE, COL_LOWLIGHT);
 450         draw_polygon(fe, coords, 3, FALSE, COL_LOWLIGHT);
 451
 452         coords[0] = x;
 453         coords[1] = y;
 454         draw_polygon(fe, coords, 3, TRUE, COL_HIGHLIGHT);
 455         draw_polygon(fe, coords, 3, FALSE, COL_HIGHLIGHT);
 456
 457         draw_rect(fe, x + HIGHLIGHT_WIDTH, y + HIGHLIGHT_WIDTH,
 458                   TILE_SIZE - 2*HIGHLIGHT_WIDTH, TILE_SIZE - 2*HIGHLIGHT_WIDTH,
 459                   flash_colour);
 460
 461         sprintf(str, "%d", tile);
 462         draw_text(fe, x + TILE_SIZE/2, y + TILE_SIZE/2,
 463                   FONT_VARIABLE, TILE_SIZE/3, ALIGN_VCENTRE | ALIGN_HCENTRE,
 464                   COL_TEXT, str);
 465     }
 466     draw_update(fe, x, y, TILE_SIZE, TILE_SIZE);
 467 }
 468
 469 void game_redraw(frontend *fe, game_drawstate *ds, game_state *oldstate,
 470                  game_state *state, float animtime, float flashtime)
 471 {
 472     int i, pass, bgcolour;
 473
 474     if (flashtime > 0) {
 475         int frame = (int)(flashtime / FLASH_FRAME);
 476         bgcolour = (frame % 2 ? COL_LOWLIGHT : COL_HIGHLIGHT);
 477     } else
 478         bgcolour = COL_BACKGROUND;
 479
 480     if (!ds->started) {
 481         int coords[6];
 482
 483         draw_rect(fe, 0, 0,
 484                   TILE_SIZE * state->w + 2 * BORDER,
 485                   TILE_SIZE * state->h + 2 * BORDER, COL_BACKGROUND);
 486         draw_update(fe, 0, 0,
 487                     TILE_SIZE * state->w + 2 * BORDER,
 488                     TILE_SIZE * state->h + 2 * BORDER);
 489
 490         /*
 491          * Recessed area containing the whole puzzle.
 492          */
 493         coords[0] = COORD(state->w) + HIGHLIGHT_WIDTH - 1;
 494         coords[1] = COORD(state->h) + HIGHLIGHT_WIDTH - 1;
 495         coords[2] = COORD(state->w) + HIGHLIGHT_WIDTH - 1;
 496         coords[3] = COORD(0) - HIGHLIGHT_WIDTH;
 497         coords[4] = COORD(0) - HIGHLIGHT_WIDTH;
 498         coords[5] = COORD(state->h) + HIGHLIGHT_WIDTH - 1;
 499         draw_polygon(fe, coords, 3, TRUE, COL_HIGHLIGHT);
 500         draw_polygon(fe, coords, 3, FALSE, COL_HIGHLIGHT);
 501
 502         coords[1] = COORD(0) - HIGHLIGHT_WIDTH;
 503         coords[0] = COORD(0) - HIGHLIGHT_WIDTH;
 504         draw_polygon(fe, coords, 3, TRUE, COL_LOWLIGHT);
 505         draw_polygon(fe, coords, 3, FALSE, COL_LOWLIGHT);
 506
 507         ds->started = TRUE;
 508     }
 509
 510     /*
 511      * Now draw each tile. We do this in two passes to make
 512      * animation easy.
 513      */
 514     for (pass = 0; pass < 2; pass++) {
 515         for (i = 0; i < state->n; i++) {
 516             int t, t0;
 517             /*
 518              * Figure out what should be displayed at this
 519              * location. It's either a simple tile, or it's a
 520              * transition between two tiles (in which case we say
 521              * -1 because it must always be drawn).
 522              */
 523
 524             if (oldstate && oldstate->tiles[i] != state->tiles[i])
 525                 t = -1;
 526             else
 527                 t = state->tiles[i];
 528
 529             t0 = t;
 530
 531             if (ds->bgcolour != bgcolour ||   /* always redraw when flashing */
 532                 ds->tiles[i] != t || ds->tiles[i] == -1 || t == -1) {
 533                 int x, y;
 534
 535                 /*
 536                  * Figure out what to _actually_ draw, and where to
 537                  * draw it.
 538                  */
 539                 if (t == -1) {
 540                     int x0, y0, x1, y1;
 541                     int j;
 542
 543                     /*
 544                      * On the first pass, just blank the tile.
 545                      */
 546                     if (pass == 0) {
 547                         x = COORD(X(state, i));
 548                         y = COORD(Y(state, i));
 549                         t = 0;
 550                     } else {
 551                         float c;
 552
 553                         t = state->tiles[i];
 554
 555                         /*
 556                          * Don't bother moving the gap; just don't
 557                          * draw it.
 558                          */
 559                         if (t == 0)
 560                             continue;
 561
 562                         /*
 563                          * Find the coordinates of this tile in the old and
 564                          * new states.
 565                          */
 566                         x1 = COORD(X(state, i));
 567                         y1 = COORD(Y(state, i));
 568                         for (j = 0; j < oldstate->n; j++)
 569                             if (oldstate->tiles[j] == state->tiles[i])
 570                                 break;
 571                         assert(j < oldstate->n);
 572                         x0 = COORD(X(state, j));
 573                         y0 = COORD(Y(state, j));
 574
 575                         c = (animtime / ANIM_TIME);
 576                         if (c < 0.0F) c = 0.0F;
 577                         if (c > 1.0F) c = 1.0F;
 578
 579                         x = x0 + (int)(c * (x1 - x0));
 580                         y = y0 + (int)(c * (y1 - y0));
 581                     }
 582
 583                 } else {
 584                     if (pass == 0)
 585                         continue;
 586                     x = COORD(X(state, i));
 587                     y = COORD(Y(state, i));
 588                 }
 589
 590                 draw_tile(fe, state, x, y, t, bgcolour);
 591             }
 592             ds->tiles[i] = t0;
 593         }
 594     }
 595     ds->bgcolour = bgcolour;
 596
 597     /*
 598      * Update the status bar.
 599      */
 600     {
 601         char statusbuf[256];
 602
 603         /*
 604          * Don't show the new status until we're also showing the
 605          * new _state_ - after the game animation is complete.
 606          */
 607         if (oldstate)
 608             state = oldstate;
 609
 610         sprintf(statusbuf, "%sMoves: %d",
 611                 (state->completed ? "COMPLETED! " : ""),
 612                 (state->completed ? state->completed : state->movecount));
 613
 614         status_bar(fe, statusbuf);
 615     }
 616 }
 617
 618 float game_anim_length(game_state *oldstate, game_state *newstate)
 619 {
 620     return ANIM_TIME;
 621 }
 622
 623 float game_flash_length(game_state *oldstate, game_state *newstate)
 624 {
 625     if (!oldstate->completed && newstate->completed)
 626         return 2 * FLASH_FRAME;
 627     else
 628         return 0.0F;
 629 }
 630
 631 int game_wants_statusbar(void)
 632 {
 633     return TRUE;
 634 }