inertia.c

   1 /*
   2  * inertia.c: Game involving navigating round a grid picking up
   3  * gems.
   4  *
   5  * Game rules and basic generator design by Ben Olmstead.
   6  * This re-implementation was written by Simon Tatham.
   7  */
   8
   9 #include <stdio.h>
  10 #include <stdlib.h>
  11 #include <string.h>
  12 #include <assert.h>
  13 #include <ctype.h>
  14 #include <math.h>
  15
  16 #include "puzzles.h"
  17
  18 /* Used in the game_state */
  19 #define BLANK   'b'
  20 #define GEM     'g'
  21 #define MINE    'm'
  22 #define STOP    's'
  23 #define WALL    'w'
  24
  25 /* Used in the game IDs */
  26 #define START   'S'
  27
  28 /* Used in the game generation */
  29 #define POSSGEM 'G'
  30
  31 /* Used only in the game_drawstate*/
  32 #define UNDRAWN '?'
  33
  34 #define DIRECTIONS 8
  35 #define DX(dir) ( (dir) & 3 ? (((dir) & 7) > 4 ? -1 : +1) : 0 )
  36 #define DY(dir) ( DX((dir)+6) )
  37
  38 /*
  39  * Lvalue macro which expects x and y to be in range.
  40  */
  41 #define LV_AT(w, h, grid, x, y) ( (grid)[(y)*(w)+(x)] )
  42
  43 /*
  44  * Rvalue macro which can cope with x and y being out of range.
  45  */
  46 #define AT(w, h, grid, x, y) ( (x)<0 || (x)>=(w) || (y)<0 || (y)>=(h) ? \
  47                                WALL : LV_AT(w, h, grid, x, y) )
  48
  49 enum {
  50     COL_BACKGROUND,
  51     COL_OUTLINE,
  52     COL_HIGHLIGHT,
  53     COL_LOWLIGHT,
  54     COL_PLAYER,
  55     COL_DEAD_PLAYER,
  56     COL_MINE,
  57     COL_GEM,
  58     COL_WALL,
  59     NCOLOURS
  60 };
  61
  62 struct game_params {
  63     int w, h;
  64 };
  65
  66 struct game_state {
  67     game_params p;
  68     int px, py;
  69     int gems;
  70     char *grid;
  71     int distance_moved;
  72     int dead;
  73 };
  74
  75 static game_params *default_params(void)
  76 {
  77     game_params *ret = snew(game_params);
  78
  79     ret->w = 10;
  80     ret->h = 8;
  81
  82     return ret;
  83 }
  84
  85 static void free_params(game_params *params)
  86 {
  87     sfree(params);
  88 }
  89
  90 static game_params *dup_params(game_params *params)
  91 {
  92     game_params *ret = snew(game_params);
  93     *ret = *params;                    /* structure copy */
  94     return ret;
  95 }
  96
  97 static const struct game_params inertia_presets[] = {
  98     { 10, 8 },
  99     { 15, 12 },
 100     { 20, 16 },
 101 };
 102
 103 static int game_fetch_preset(int i, char **name, game_params **params)
 104 {
 105     game_params p, *ret;
 106     char *retname;
 107     char namebuf[80];
 108
 109     if (i < 0 || i >= lenof(inertia_presets))
 110         return FALSE;
 111
 112     p = inertia_presets[i];
 113     ret = dup_params(&p);
 114     sprintf(namebuf, "%dx%d", ret->w, ret->h);
 115     retname = dupstr(namebuf);
 116
 117     *params = ret;
 118     *name = retname;
 119     return TRUE;
 120 }
 121
 122 static void decode_params(game_params *params, char const *string)
 123 {
 124     params->w = params->h = atoi(string);
 125     while (*string && isdigit((unsigned char)*string)) string++;
 126     if (*string == 'x') {
 127         string++;
 128         params->h = atoi(string);
 129     }
 130 }
 131
 132 static char *encode_params(game_params *params, int full)
 133 {
 134     char data[256];
 135
 136     sprintf(data, "%dx%d", params->w, params->h);
 137
 138     return dupstr(data);
 139 }
 140
 141 static config_item *game_configure(game_params *params)
 142 {
 143     config_item *ret;
 144     char buf[80];
 145
 146     ret = snewn(3, config_item);
 147
 148     ret[0].name = "Width";
 149     ret[0].type = C_STRING;
 150     sprintf(buf, "%d", params->w);
 151     ret[0].sval = dupstr(buf);
 152     ret[0].ival = 0;
 153
 154     ret[1].name = "Height";
 155     ret[1].type = C_STRING;
 156     sprintf(buf, "%d", params->h);
 157     ret[1].sval = dupstr(buf);
 158     ret[1].ival = 0;
 159
 160     ret[2].name = NULL;
 161     ret[2].type = C_END;
 162     ret[2].sval = NULL;
 163     ret[2].ival = 0;
 164
 165     return ret;
 166 }
 167
 168 static game_params *custom_params(config_item *cfg)
 169 {
 170     game_params *ret = snew(game_params);
 171
 172     ret->w = atoi(cfg[0].sval);
 173     ret->h = atoi(cfg[1].sval);
 174
 175     return ret;
 176 }
 177
 178 static char *validate_params(game_params *params, int full)
 179 {
 180     /*
 181      * Avoid completely degenerate cases which only have one
 182      * row/column. We probably could generate completable puzzles
 183      * of that shape, but they'd be forced to be extremely boring
 184      * and at large sizes would take a while to happen upon at
 185      * random as well.
 186      */
 187     if (params->w < 2 || params->h < 2)
 188         return "Width and height must both be at least two";
 189
 190     /*
 191      * The grid construction algorithm creates 1/5 as many gems as
 192      * grid squares, and must create at least one gem to have an
 193      * actual puzzle. However, an area-five grid is ruled out by
 194      * the above constraint, so the practical minimum is six.
 195      */
 196     if (params->w * params->h < 6)
 197         return "Grid area must be at least six squares";
 198
 199     return NULL;
 200 }
 201
 202 /* ----------------------------------------------------------------------
 203  * Solver used by grid generator.
 204  */
 205
 206 struct solver_scratch {
 207     unsigned char *reachable_from, *reachable_to;
 208     int *positions;
 209 };
 210
 211 static struct solver_scratch *new_scratch(int w, int h)
 212 {
 213     struct solver_scratch *sc = snew(struct solver_scratch);
 214
 215     sc->reachable_from = snewn(w * h * DIRECTIONS, unsigned char);
 216     sc->reachable_to = snewn(w * h * DIRECTIONS, unsigned char);
 217     sc->positions = snewn(w * h * DIRECTIONS, int);
 218
 219     return sc;
 220 }
 221
 222 static void free_scratch(struct solver_scratch *sc)
 223 {
 224     sfree(sc->reachable_from);
 225     sfree(sc->reachable_to);
 226     sfree(sc->positions);
 227     sfree(sc);
 228 }
 229
 230 static int can_go(int w, int h, char *grid,
 231                   int x1, int y1, int dir1, int x2, int y2, int dir2)
 232 {
 233     /*
 234      * Returns TRUE if we can transition directly from (x1,y1)
 235      * going in direction dir1, to (x2,y2) going in direction dir2.
 236      */
 237
 238     /*
 239      * If we're actually in the middle of an unoccupyable square,
 240      * we cannot make any move.
 241      */
 242     if (AT(w, h, grid, x1, y1) == WALL ||
 243         AT(w, h, grid, x1, y1) == MINE)
 244         return FALSE;
 245
 246     /*
 247      * If a move is capable of stopping at x1,y1,dir1, and x2,y2 is
 248      * the same coordinate as x1,y1, then we can make the
 249      * transition (by stopping and changing direction).
 250      *
 251      * For this to be the case, we have to either have a wall
 252      * beyond x1,y1,dir1, or have a stop on x1,y1.
 253      */
 254     if (x2 == x1 && y2 == y1 &&
 255         (AT(w, h, grid, x1, y1) == STOP ||
 256          AT(w, h, grid, x1, y1) == START ||
 257          AT(w, h, grid, x1+DX(dir1), y1+DY(dir1)) == WALL))
 258         return TRUE;
 259
 260     /*
 261      * If a move is capable of continuing here, then x1,y1,dir1 can
 262      * move one space further on.
 263      */
 264     if (x2 == x1+DX(dir1) && y2 == y1+DY(dir1) && dir1 == dir2 &&
 265         (AT(w, h, grid, x2, y2) == BLANK ||
 266          AT(w, h, grid, x2, y2) == GEM ||
 267          AT(w, h, grid, x2, y2) == STOP ||
 268          AT(w, h, grid, x2, y2) == START))
 269         return TRUE;
 270
 271     /*
 272      * That's it.
 273      */
 274     return FALSE;
 275 }
 276
 277 static int find_gem_candidates(int w, int h, char *grid,
 278                                struct solver_scratch *sc)
 279 {
 280     int wh = w*h;
 281     int head, tail;
 282     int sx, sy, gx, gy, gd, pass, possgems;
 283
 284     /*
 285      * This function finds all the candidate gem squares, which are
 286      * precisely those squares which can be picked up on a loop
 287      * from the starting point back to the starting point. Doing
 288      * this may involve passing through such a square in the middle
 289      * of a move; so simple breadth-first search over the _squares_
 290      * of the grid isn't quite adequate, because it might be that
 291      * we can only reach a gem from the start by moving over it in
 292      * one direction, but can only return to the start if we were
 293      * moving over it in another direction.
 294      *
 295      * Instead, we BFS over a space which mentions each grid square
 296      * eight times - once for each direction. We also BFS twice:
 297      * once to find out what square+direction pairs we can reach
 298      * _from_ the start point, and once to find out what pairs we
 299      * can reach the start point from. Then a square is reachable
 300      * if any of the eight directions for that square has both
 301      * flags set.
 302      */
 303
 304     memset(sc->reachable_from, 0, wh * DIRECTIONS);
 305     memset(sc->reachable_to, 0, wh * DIRECTIONS);
 306
 307     /*
 308      * Find the starting square.
 309      */
 310     sx = -1;                           /* placate optimiser */
 311     for (sy = 0; sy < h; sy++) {
 312         for (sx = 0; sx < w; sx++)
 313             if (AT(w, h, grid, sx, sy) == START)
 314                 break;
 315         if (sx < w)
 316             break;
 317     }
 318     assert(sy < h);
 319
 320     for (pass = 0; pass < 2; pass++) {
 321         unsigned char *reachable = (pass == 0 ? sc->reachable_from :
 322                                     sc->reachable_to);
 323         int sign = (pass == 0 ? +1 : -1);
 324         int dir;
 325
 326 #ifdef SOLVER_DIAGNOSTICS
 327         printf("starting pass %d\n", pass);
 328 #endif
 329
 330         /*
 331          * `head' and `tail' are indices within sc->positions which
 332          * track the list of board positions left to process.
 333          */
 334         head = tail = 0;
 335         for (dir = 0; dir < DIRECTIONS; dir++) {
 336             int index = (sy*w+sx)*DIRECTIONS+dir;
 337             sc->positions[tail++] = index;
 338             reachable[index] = TRUE;
 339 #ifdef SOLVER_DIAGNOSTICS
 340             printf("starting point %d,%d,%d\n", sx, sy, dir);
 341 #endif
 342         }
 343
 344         /*
 345          * Now repeatedly pick an element off the list and process
 346          * it.
 347          */
 348         while (head < tail) {
 349             int index = sc->positions[head++];
 350             int dir = index % DIRECTIONS;
 351             int x = (index / DIRECTIONS) % w;
 352             int y = index / (w * DIRECTIONS);
 353             int n, x2, y2, d2, i2;
 354
 355 #ifdef SOLVER_DIAGNOSTICS
 356             printf("processing point %d,%d,%d\n", x, y, dir);
 357 #endif
 358             /*
 359              * The places we attempt to switch to here are:
 360              *  - each possible direction change (all the other
 361              *    directions in this square)
 362              *  - one step further in the direction we're going (or
 363              *    one step back, if we're in the reachable_to pass).
 364              */
 365             for (n = -1; n < DIRECTIONS; n++) {
 366                 if (n < 0) {
 367                     x2 = x + sign * DX(dir);
 368                     y2 = y + sign * DY(dir);
 369                     d2 = dir;
 370                 } else {
 371                     x2 = x;
 372                     y2 = y;
 373                     d2 = n;
 374                 }
 375                 i2 = (y2*w+x2)*DIRECTIONS+d2;
 376                 if (x2 >= 0 && x2 < w &&
 377                     y2 >= 0 && y2 < h &&
 378                     !reachable[i2]) {
 379                     int ok;
 380 #ifdef SOLVER_DIAGNOSTICS
 381                     printf("  trying point %d,%d,%d", x2, y2, d2);
 382 #endif
 383                     if (pass == 0)
 384                         ok = can_go(w, h, grid, x, y, dir, x2, y2, d2);
 385                     else
 386                         ok = can_go(w, h, grid, x2, y2, d2, x, y, dir);
 387 #ifdef SOLVER_DIAGNOSTICS
 388                     printf(" - %sok\n", ok ? "" : "not ");
 389 #endif
 390                     if (ok) {
 391                         sc->positions[tail++] = i2;
 392                         reachable[i2] = TRUE;
 393                     }
 394                 }
 395             }
 396         }
 397     }
 398
 399     /*
 400      * And that should be it. Now all we have to do is find the
 401      * squares for which there exists _some_ direction such that
 402      * the square plus that direction form a tuple which is both
 403      * reachable from the start and reachable to the start.
 404      */
 405     possgems = 0;
 406     for (gy = 0; gy < h; gy++)
 407         for (gx = 0; gx < w; gx++)
 408             if (AT(w, h, grid, gx, gy) == BLANK) {
 409                 for (gd = 0; gd < DIRECTIONS; gd++) {
 410                     int index = (gy*w+gx)*DIRECTIONS+gd;
 411                     if (sc->reachable_from[index] && sc->reachable_to[index]) {
 412 #ifdef SOLVER_DIAGNOSTICS
 413                         printf("space at %d,%d is reachable via"
 414                                " direction %d\n", gx, gy, gd);
 415 #endif
 416                         LV_AT(w, h, grid, gx, gy) = POSSGEM;
 417                         possgems++;
 418                         break;
 419                     }
 420                 }
 421             }
 422
 423     return possgems;
 424 }
 425
 426 /* ----------------------------------------------------------------------
 427  * Grid generation code.
 428  */
 429
 430 static char *gengrid(int w, int h, random_state *rs)
 431 {
 432     int wh = w*h;
 433     char *grid = snewn(wh+1, char);
 434     struct solver_scratch *sc = new_scratch(w, h);
 435     int maxdist_threshold, tries;
 436
 437     maxdist_threshold = 2;
 438     tries = 0;
 439
 440     while (1) {
 441         int i, j;
 442         int possgems;
 443         int *dist, *list, head, tail, maxdist;
 444
 445         /*
 446          * We're going to fill the grid with the five basic piece
 447          * types in about 1/5 proportion. For the moment, though,
 448          * we leave out the gems, because we'll put those in
 449          * _after_ we run the solver to tell us where the viable
 450          * locations are.
 451          */
 452         i = 0;
 453         for (j = 0; j < wh/5; j++)
 454             grid[i++] = WALL;
 455         for (j = 0; j < wh/5; j++)
 456             grid[i++] = STOP;
 457         for (j = 0; j < wh/5; j++)
 458             grid[i++] = MINE;
 459         assert(i < wh);
 460         grid[i++] = START;
 461         while (i < wh)
 462             grid[i++] = BLANK;
 463         shuffle(grid, wh, sizeof(*grid), rs);
 464
 465         /*
 466          * Find the viable gem locations, and immediately give up
 467          * and try again if there aren't enough of them.
 468          */
 469         possgems = find_gem_candidates(w, h, grid, sc);
 470         if (possgems < wh/5)
 471             continue;
 472
 473         /*
 474          * We _could_ now select wh/5 of the POSSGEMs and set them
 475          * to GEM, and have a viable level. However, there's a
 476          * chance that a large chunk of the level will turn out to
 477          * be unreachable, so first we test for that.
 478          *
 479          * We do this by finding the largest distance from any
 480          * square to the nearest POSSGEM, by breadth-first search.
 481          * If this is above a critical threshold, we abort and try
 482          * again.
 483          *
 484          * (This search is purely geometric, without regard to
 485          * walls and long ways round.)
 486          */
 487         dist = sc->positions;
 488         list = sc->positions + wh;
 489         for (i = 0; i < wh; i++)
 490             dist[i] = -1;
 491         head = tail = 0;
 492         for (i = 0; i < wh; i++)
 493             if (grid[i] == POSSGEM) {
 494                 dist[i] = 0;
 495                 list[tail++] = i;
 496             }
 497         maxdist = 0;
 498         while (head < tail) {
 499             int pos, x, y, d;
 500
 501             pos = list[head++];
 502             if (maxdist < dist[pos])
 503                 maxdist = dist[pos];
 504
 505             x = pos % w;
 506             y = pos / w;
 507
 508             for (d = 0; d < DIRECTIONS; d++) {
 509                 int x2, y2, p2;
 510
 511                 x2 = x + DX(d);
 512                 y2 = y + DY(d);
 513
 514                 if (x2 >= 0 && x2 < w && y2 >= 0 && y2 < h) {
 515                     p2 = y2*w+x2;
 516                     if (dist[p2] < 0) {
 517                         dist[p2] = dist[pos] + 1;
 518                         list[tail++] = p2;
 519                     }
 520                 }
 521             }
 522         }
 523         assert(head == wh && tail == wh);
 524
 525         /*
 526          * Now abandon this grid and go round again if maxdist is
 527          * above the required threshold.
 528          *
 529          * We can safely start the threshold as low as 2. As we
 530          * accumulate failed generation attempts, we gradually
 531          * raise it as we get more desperate.
 532          */
 533         if (maxdist > maxdist_threshold) {
 534             tries++;
 535             if (tries == 50) {
 536                 maxdist_threshold++;
 537                 tries = 0;
 538             }
 539             continue;
 540         }
 541
 542         /*
 543          * Now our reachable squares are plausibly evenly
 544          * distributed over the grid. I'm not actually going to
 545          * _enforce_ that I place the gems in such a way as not to
 546          * increase that maxdist value; I'm now just going to trust
 547          * to the RNG to pick a sensible subset of the POSSGEMs.
 548          */
 549         j = 0;
 550         for (i = 0; i < wh; i++)
 551             if (grid[i] == POSSGEM)
 552                 list[j++] = i;
 553         shuffle(list, j, sizeof(*list), rs);
 554         for (i = 0; i < j; i++)
 555             grid[list[i]] = (i < wh/5 ? GEM : BLANK);
 556         break;
 557     }
 558
 559     free_scratch(sc);
 560
 561     grid[wh] = '\0';
 562
 563     return grid;
 564 }
 565
 566 static char *new_game_desc(game_params *params, random_state *rs,
 567                            char **aux, int interactive)
 568 {
 569     return gengrid(params->w, params->h, rs);
 570 }
 571
 572 static char *validate_desc(game_params *params, char *desc)
 573 {
 574     int w = params->w, h = params->h, wh = w*h;
 575     int starts = 0, gems = 0, i;
 576
 577     for (i = 0; i < wh; i++) {
 578         if (!desc[i])
 579             return "Not enough data to fill grid";
 580         if (desc[i] != WALL && desc[i] != START && desc[i] != STOP &&
 581             desc[i] != GEM && desc[i] != MINE && desc[i] != BLANK)
 582             return "Unrecognised character in game description";
 583         if (desc[i] == START)
 584             starts++;
 585         if (desc[i] == GEM)
 586             gems++;
 587     }
 588     if (desc[i])
 589         return "Too much data to fill grid";
 590     if (starts < 1)
 591         return "No starting square specified";
 592     if (starts > 1)
 593         return "More than one starting square specified";
 594     if (gems < 1)
 595         return "No gems specified";
 596
 597     return NULL;
 598 }
 599
 600 static game_state *new_game(midend *me, game_params *params, char *desc)
 601 {
 602     int w = params->w, h = params->h, wh = w*h;
 603     int i;
 604     game_state *state = snew(game_state);
 605
 606     state->p = *params;                /* structure copy */
 607
 608     state->grid = snewn(wh, char);
 609     assert(strlen(desc) == wh);
 610     memcpy(state->grid, desc, wh);
 611
 612     state->px = state->py = -1;
 613     state->gems = 0;
 614     for (i = 0; i < wh; i++) {
 615         if (state->grid[i] == START) {
 616             state->grid[i] = STOP;
 617             state->px = i % w;
 618             state->py = i / w;
 619         } else if (state->grid[i] == GEM) {
 620             state->gems++;
 621         }
 622     }
 623
 624     assert(state->gems > 0);
 625     assert(state->px >= 0 && state->py >= 0);
 626
 627     state->distance_moved = 0;
 628     state->dead = FALSE;
 629
 630     return state;
 631 }
 632
 633 static game_state *dup_game(game_state *state)
 634 {
 635     int w = state->p.w, h = state->p.h, wh = w*h;
 636     game_state *ret = snew(game_state);
 637
 638     ret->p = state->p;
 639     ret->px = state->px;
 640     ret->py = state->py;
 641     ret->gems = state->gems;
 642     ret->grid = snewn(wh, char);
 643     ret->distance_moved = state->distance_moved;
 644     ret->dead = FALSE;
 645     memcpy(ret->grid, state->grid, wh);
 646
 647     return ret;
 648 }
 649
 650 static void free_game(game_state *state)
 651 {
 652     sfree(state->grid);
 653     sfree(state);
 654 }
 655
 656 static char *solve_game(game_state *state, game_state *currstate,
 657                         char *aux, char **error)
 658 {
 659     return NULL;
 660 }
 661
 662 static char *game_text_format(game_state *state)
 663 {
 664     return NULL;
 665 }
 666
 667 struct game_ui {
 668     float anim_length;
 669     int flashtype;
 670     int deaths;
 671     int just_made_move;
 672     int just_died;
 673 };
 674
 675 static game_ui *new_ui(game_state *state)
 676 {
 677     game_ui *ui = snew(game_ui);
 678     ui->anim_length = 0.0F;
 679     ui->flashtype = 0;
 680     ui->deaths = 0;
 681     ui->just_made_move = FALSE;
 682     ui->just_died = FALSE;
 683     return ui;
 684 }
 685
 686 static void free_ui(game_ui *ui)
 687 {
 688     sfree(ui);
 689 }
 690
 691 static char *encode_ui(game_ui *ui)
 692 {
 693     char buf[80];
 694     /*
 695      * The deaths counter needs preserving across a serialisation.
 696      */
 697     sprintf(buf, "D%d", ui->deaths);
 698     return dupstr(buf);
 699 }
 700
 701 static void decode_ui(game_ui *ui, char *encoding)
 702 {
 703     int p = 0;
 704     sscanf(encoding, "D%d%n", &ui->deaths, &p);
 705 }
 706
 707 static void game_changed_state(game_ui *ui, game_state *oldstate,
 708                                game_state *newstate)
 709 {
 710     /*
 711      * Increment the deaths counter. We only do this if
 712      * ui->just_made_move is set (redoing a suicide move doesn't
 713      * kill you _again_), and also we only do it if the game isn't
 714      * completed (once you're finished, you can play).
 715      */
 716     if (!oldstate->dead && newstate->dead && ui->just_made_move &&
 717         newstate->gems) {
 718         ui->deaths++;
 719         ui->just_died = TRUE;
 720     } else {
 721         ui->just_died = FALSE;
 722     }
 723     ui->just_made_move = FALSE;
 724 }
 725
 726 struct game_drawstate {
 727     game_params p;
 728     int tilesize;
 729     int started;
 730     unsigned short *grid;
 731     blitter *player_background;
 732     int player_bg_saved, pbgx, pbgy;
 733 };
 734
 735 #define PREFERRED_TILESIZE 32
 736 #define TILESIZE (ds->tilesize)
 737 #define BORDER    (TILESIZE)
 738 #define HIGHLIGHT_WIDTH (TILESIZE / 10)
 739 #define COORD(x)  ( (x) * TILESIZE + BORDER )
 740 #define FROMCOORD(x)  ( ((x) - BORDER + TILESIZE) / TILESIZE - 1 )
 741
 742 static char *interpret_move(game_state *state, game_ui *ui, game_drawstate *ds,
 743                             int x, int y, int button)
 744 {
 745     int w = state->p.w, h = state->p.h /*, wh = w*h */;
 746     int dir;
 747     char buf[80];
 748
 749     dir = -1;
 750
 751     if (button == LEFT_BUTTON) {
 752         /*
 753          * Mouse-clicking near the target point (or, more
 754          * accurately, in the appropriate octant) is an alternative
 755          * way to input moves.
 756          */
 757
 758         if (FROMCOORD(x) != state->px || FROMCOORD(y) != state->py) {
 759             int dx, dy;
 760             float angle;
 761
 762             dx = FROMCOORD(x) - state->px;
 763             dy = FROMCOORD(y) - state->py;
 764             /* I pass dx,dy rather than dy,dx so that the octants
 765              * end up the right way round. */
 766             angle = atan2(dx, -dy);
 767
 768             angle = (angle + (PI/8)) / (PI/4);
 769             assert(angle > -16.0F);
 770             dir = (int)(angle + 16.0F) & 7;
 771         }
 772     } else if (button == CURSOR_UP || button == (MOD_NUM_KEYPAD | '8'))
 773         dir = 0;
 774     else if (button == CURSOR_DOWN || button == (MOD_NUM_KEYPAD | '2'))
 775         dir = 4;
 776     else if (button == CURSOR_LEFT || button == (MOD_NUM_KEYPAD | '4'))
 777         dir = 6;
 778     else if (button == CURSOR_RIGHT || button == (MOD_NUM_KEYPAD | '6'))
 779         dir = 2;
 780     else if (button == (MOD_NUM_KEYPAD | '7'))
 781         dir = 7;
 782     else if (button == (MOD_NUM_KEYPAD | '1'))
 783         dir = 5;
 784     else if (button == (MOD_NUM_KEYPAD | '9'))
 785         dir = 1;
 786     else if (button == (MOD_NUM_KEYPAD | '3'))
 787         dir = 3;
 788
 789     if (dir < 0)
 790         return NULL;
 791
 792     /*
 793      * Reject the move if we can't make it at all due to a wall
 794      * being in the way.
 795      */
 796     if (AT(w, h, state->grid, state->px+DX(dir), state->py+DY(dir)) == WALL)
 797         return NULL;
 798
 799     /*
 800      * Reject the move if we're dead!
 801      */
 802     if (state->dead)
 803         return NULL;
 804
 805     /*
 806      * Otherwise, we can make the move. All we need to specify is
 807      * the direction.
 808      */
 809     ui->just_made_move = TRUE;
 810     sprintf(buf, "%d", dir);
 811     return dupstr(buf);
 812 }
 813
 814 static game_state *execute_move(game_state *state, char *move)
 815 {
 816     int w = state->p.w, h = state->p.h /*, wh = w*h */;
 817     int dir = atoi(move);
 818     game_state *ret;
 819
 820     if (dir < 0 || dir >= DIRECTIONS)
 821         return NULL;                   /* huh? */
 822
 823     if (state->dead)
 824         return NULL;
 825
 826     if (AT(w, h, state->grid, state->px+DX(dir), state->py+DY(dir)) == WALL)
 827         return NULL;                   /* wall in the way! */
 828
 829     /*
 830      * Now make the move.
 831      */
 832     ret = dup_game(state);
 833     ret->distance_moved = 0;
 834     while (1) {
 835         ret->px += DX(dir);
 836         ret->py += DY(dir);
 837         ret->distance_moved++;
 838
 839         if (AT(w, h, ret->grid, ret->px, ret->py) == GEM) {
 840             LV_AT(w, h, ret->grid, ret->px, ret->py) = BLANK;
 841             ret->gems--;
 842         }
 843
 844         if (AT(w, h, ret->grid, ret->px, ret->py) == MINE) {
 845             ret->dead = TRUE;
 846             break;
 847         }
 848
 849         if (AT(w, h, ret->grid, ret->px, ret->py) == STOP ||
 850             AT(w, h, ret->grid, ret->px+DX(dir),
 851                ret->py+DY(dir)) == WALL)
 852             break;
 853     }
 854
 855     return ret;
 856 }
 857
 858 /* ----------------------------------------------------------------------
 859  * Drawing routines.
 860  */
 861
 862 static void game_compute_size(game_params *params, int tilesize,
 863                               int *x, int *y)
 864 {
 865     /* Ick: fake up `ds->tilesize' for macro expansion purposes */
 866     struct { int tilesize; } ads, *ds = &ads;
 867     ads.tilesize = tilesize;
 868
 869     *x = 2 * BORDER + 1 + params->w * TILESIZE;
 870     *y = 2 * BORDER + 1 + params->h * TILESIZE;
 871 }
 872
 873 static void game_set_size(drawing *dr, game_drawstate *ds,
 874                           game_params *params, int tilesize)
 875 {
 876     ds->tilesize = tilesize;
 877
 878     assert(!ds->player_bg_saved);
 879
 880     if (ds->player_background)
 881         blitter_free(dr, ds->player_background);
 882     ds->player_background = blitter_new(dr, TILESIZE, TILESIZE);
 883 }
 884
 885 static float *game_colours(frontend *fe, game_state *state, int *ncolours)
 886 {
 887     float *ret = snewn(3 * NCOLOURS, float);
 888     int i;
 889
 890     game_mkhighlight(fe, ret, COL_BACKGROUND, COL_HIGHLIGHT, COL_LOWLIGHT);
 891
 892     ret[COL_OUTLINE * 3 + 0] = 0.0F;
 893     ret[COL_OUTLINE * 3 + 1] = 0.0F;
 894     ret[COL_OUTLINE * 3 + 2] = 0.0F;
 895
 896     ret[COL_PLAYER * 3 + 0] = 0.0F;
 897     ret[COL_PLAYER * 3 + 1] = 1.0F;
 898     ret[COL_PLAYER * 3 + 2] = 0.0F;
 899
 900     ret[COL_DEAD_PLAYER * 3 + 0] = 1.0F;
 901     ret[COL_DEAD_PLAYER * 3 + 1] = 0.0F;
 902     ret[COL_DEAD_PLAYER * 3 + 2] = 0.0F;
 903
 904     ret[COL_MINE * 3 + 0] = 0.0F;
 905     ret[COL_MINE * 3 + 1] = 0.0F;
 906     ret[COL_MINE * 3 + 2] = 0.0F;
 907
 908     ret[COL_GEM * 3 + 0] = 0.6F;
 909     ret[COL_GEM * 3 + 1] = 1.0F;
 910     ret[COL_GEM * 3 + 2] = 1.0F;
 911
 912     for (i = 0; i < 3; i++) {
 913         ret[COL_WALL * 3 + i] = (3 * ret[COL_BACKGROUND * 3 + i] +
 914                                  1 * ret[COL_HIGHLIGHT * 3 + i]) / 4;
 915     }
 916
 917     *ncolours = NCOLOURS;
 918     return ret;
 919 }
 920
 921 static game_drawstate *game_new_drawstate(drawing *dr, game_state *state)
 922 {
 923     int w = state->p.w, h = state->p.h, wh = w*h;
 924     struct game_drawstate *ds = snew(struct game_drawstate);
 925     int i;
 926
 927     ds->tilesize = 0;
 928
 929     /* We can't allocate the blitter rectangle for the player background
 930      * until we know what size to make it. */
 931     ds->player_background = NULL;
 932     ds->player_bg_saved = FALSE;
 933     ds->pbgx = ds->pbgy = -1;
 934
 935     ds->p = state->p;                  /* structure copy */
 936     ds->started = FALSE;
 937     ds->grid = snewn(wh, unsigned short);
 938     for (i = 0; i < wh; i++)
 939         ds->grid[i] = UNDRAWN;
 940
 941     return ds;
 942 }
 943
 944 static void game_free_drawstate(drawing *dr, game_drawstate *ds)
 945 {
 946     if (ds->player_background)
 947         blitter_free(dr, ds->player_background);
 948     sfree(ds->grid);
 949     sfree(ds);
 950 }
 951
 952 static void draw_player(drawing *dr, game_drawstate *ds, int x, int y,
 953                         int dead)
 954 {
 955     if (dead) {
 956         int coords[DIRECTIONS*4];
 957         int d;
 958
 959         for (d = 0; d < DIRECTIONS; d++) {
 960             float x1, y1, x2, y2, x3, y3, len;
 961
 962             x1 = DX(d);
 963             y1 = DY(d);
 964             len = sqrt(x1*x1+y1*y1); x1 /= len; y1 /= len;
 965
 966             x3 = DX(d+1);
 967             y3 = DY(d+1);
 968             len = sqrt(x3*x3+y3*y3); x3 /= len; y3 /= len;
 969
 970             x2 = (x1+x3) / 4;
 971             y2 = (y1+y3) / 4;
 972
 973             coords[d*4+0] = x + TILESIZE/2 + (int)((TILESIZE*3/7) * x1);
 974             coords[d*4+1] = y + TILESIZE/2 + (int)((TILESIZE*3/7) * y1);
 975             coords[d*4+2] = x + TILESIZE/2 + (int)((TILESIZE*3/7) * x2);
 976             coords[d*4+3] = y + TILESIZE/2 + (int)((TILESIZE*3/7) * y2);
 977         }
 978         draw_polygon(dr, coords, DIRECTIONS*2, COL_DEAD_PLAYER, COL_OUTLINE);
 979     } else {
 980         draw_circle(dr, x + TILESIZE/2, y + TILESIZE/2,
 981                     TILESIZE/3, COL_PLAYER, COL_OUTLINE);
 982     }
 983     draw_update(dr, x, y, TILESIZE, TILESIZE);
 984 }
 985
 986 #define FLASH_DEAD 0x100
 987 #define FLASH_WIN  0x200
 988 #define FLASH_MASK 0x300
 989
 990 static void draw_tile(drawing *dr, game_drawstate *ds, int x, int y, int v)
 991 {
 992     int tx = COORD(x), ty = COORD(y);
 993     int bg = (v & FLASH_DEAD ? COL_DEAD_PLAYER :
 994               v & FLASH_WIN ? COL_HIGHLIGHT : COL_BACKGROUND);
 995
 996     v &= ~FLASH_MASK;
 997
 998     clip(dr, tx+1, ty+1, TILESIZE-1, TILESIZE-1);
 999     draw_rect(dr, tx+1, ty+1, TILESIZE-1, TILESIZE-1, bg);
1000
1001     if (v == WALL) {
1002         int coords[6];
1003
1004         coords[0] = tx + TILESIZE;
1005         coords[1] = ty + TILESIZE;
1006         coords[2] = tx + TILESIZE;
1007         coords[3] = ty + 1;
1008         coords[4] = tx + 1;
1009         coords[5] = ty + TILESIZE;
1010         draw_polygon(dr, coords, 3, COL_LOWLIGHT, COL_LOWLIGHT);
1011
1012         coords[0] = tx + 1;
1013         coords[1] = ty + 1;
1014         draw_polygon(dr, coords, 3, COL_HIGHLIGHT, COL_HIGHLIGHT);
1015
1016         draw_rect(dr, tx + 1 + HIGHLIGHT_WIDTH, ty + 1 + HIGHLIGHT_WIDTH,
1017                   TILESIZE - 2*HIGHLIGHT_WIDTH,
1018                   TILESIZE - 2*HIGHLIGHT_WIDTH, COL_WALL);
1019     } else if (v == MINE) {
1020         int cx = tx + TILESIZE / 2;
1021         int cy = ty + TILESIZE / 2;
1022         int r = TILESIZE / 2 - 3;
1023         int coords[4*5*2];
1024         int xdx = 1, xdy = 0, ydx = 0, ydy = 1;
1025         int tdx, tdy, i;
1026
1027         for (i = 0; i < 4*5*2; i += 5*2) {
1028             coords[i+2*0+0] = cx - r/6*xdx + r*4/5*ydx;
1029             coords[i+2*0+1] = cy - r/6*xdy + r*4/5*ydy;
1030             coords[i+2*1+0] = cx - r/6*xdx + r*ydx;
1031             coords[i+2*1+1] = cy - r/6*xdy + r*ydy;
1032             coords[i+2*2+0] = cx + r/6*xdx + r*ydx;
1033             coords[i+2*2+1] = cy + r/6*xdy + r*ydy;
1034             coords[i+2*3+0] = cx + r/6*xdx + r*4/5*ydx;
1035             coords[i+2*3+1] = cy + r/6*xdy + r*4/5*ydy;
1036             coords[i+2*4+0] = cx + r*3/5*xdx + r*3/5*ydx;
1037             coords[i+2*4+1] = cy + r*3/5*xdy + r*3/5*ydy;
1038
1039             tdx = ydx;
1040             tdy = ydy;
1041             ydx = xdx;
1042             ydy = xdy;
1043             xdx = -tdx;
1044             xdy = -tdy;
1045         }
1046
1047         draw_polygon(dr, coords, 5*4, COL_MINE, COL_MINE);
1048
1049         draw_rect(dr, cx-r/3, cy-r/3, r/3, r/4, COL_HIGHLIGHT);
1050     } else if (v == STOP) {
1051         draw_circle(dr, tx + TILESIZE/2, ty + TILESIZE/2,
1052                     TILESIZE*3/7, -1, COL_OUTLINE);
1053         draw_rect(dr, tx + TILESIZE*3/7, ty+1,
1054                   TILESIZE - 2*(TILESIZE*3/7) + 1, TILESIZE-1, bg);
1055         draw_rect(dr, tx+1, ty + TILESIZE*3/7,
1056                   TILESIZE-1, TILESIZE - 2*(TILESIZE*3/7) + 1, bg);
1057     } else if (v == GEM) {
1058         int coords[8];
1059
1060         coords[0] = tx+TILESIZE/2;
1061         coords[1] = ty+TILESIZE*1/7;
1062         coords[2] = tx+TILESIZE*1/7;
1063         coords[3] = ty+TILESIZE/2;
1064         coords[4] = tx+TILESIZE/2;
1065         coords[5] = ty+TILESIZE-TILESIZE*1/7;
1066         coords[6] = tx+TILESIZE-TILESIZE*1/7;
1067         coords[7] = ty+TILESIZE/2;
1068
1069         draw_polygon(dr, coords, 4, COL_GEM, COL_OUTLINE);
1070     }
1071
1072     unclip(dr);
1073     draw_update(dr, tx, ty, TILESIZE, TILESIZE);
1074 }
1075
1076 #define BASE_ANIM_LENGTH 0.1F
1077 #define FLASH_LENGTH 0.3F
1078
1079 static void game_redraw(drawing *dr, game_drawstate *ds, game_state *oldstate,
1080                         game_state *state, int dir, game_ui *ui,
1081                         float animtime, float flashtime)
1082 {
1083     int w = state->p.w, h = state->p.h /*, wh = w*h */;
1084     int x, y;
1085     float ap;
1086     int player_dist;
1087     int flashtype;
1088     int gems, deaths;
1089     char status[256];
1090
1091     if (flashtime &&
1092         !((int)(flashtime * 3 / FLASH_LENGTH) % 2))
1093         flashtype = ui->flashtype;
1094     else
1095         flashtype = 0;
1096
1097     /*
1098      * Erase the player sprite.
1099      */
1100     if (ds->player_bg_saved) {
1101         assert(ds->player_background);
1102         blitter_load(dr, ds->player_background, ds->pbgx, ds->pbgy);
1103         draw_update(dr, ds->pbgx, ds->pbgy, TILESIZE, TILESIZE);
1104         ds->player_bg_saved = FALSE;
1105     }
1106
1107     /*
1108      * Initialise a fresh drawstate.
1109      */
1110     if (!ds->started) {
1111         int wid, ht;
1112
1113         /*
1114          * Blank out the window initially.
1115          */
1116         game_compute_size(&ds->p, TILESIZE, &wid, &ht);
1117         draw_rect(dr, 0, 0, wid, ht, COL_BACKGROUND);
1118         draw_update(dr, 0, 0, wid, ht);
1119
1120         /*
1121          * Draw the grid lines.
1122          */
1123         for (y = 0; y <= h; y++)
1124             draw_line(dr, COORD(0), COORD(y), COORD(w), COORD(y),
1125                       COL_LOWLIGHT);
1126         for (x = 0; x <= w; x++)
1127             draw_line(dr, COORD(x), COORD(0), COORD(x), COORD(h),
1128                       COL_LOWLIGHT);
1129
1130         ds->started = TRUE;
1131     }
1132
1133     /*
1134      * If we're in the process of animating a move, let's start by
1135      * working out how far the player has moved from their _older_
1136      * state.
1137      */
1138     if (oldstate) {
1139         ap = animtime / ui->anim_length;
1140         player_dist = ap * (dir > 0 ? state : oldstate)->distance_moved;
1141     } else {
1142         player_dist = 0;
1143         ap = 0.0F;
1144     }
1145
1146     /*
1147      * Draw the grid contents.
1148      *
1149      * We count the gems as we go round this loop, for the purposes
1150      * of the status bar. Of course we have a gems counter in the
1151      * game_state already, but if we do the counting in this loop
1152      * then it tracks gems being picked up in a sliding move, and
1153      * updates one by one.
1154      */
1155     gems = 0;
1156     for (y = 0; y < h; y++)
1157         for (x = 0; x < w; x++) {
1158             unsigned short v = (unsigned char)state->grid[y*w+x];
1159
1160             /*
1161              * Special case: if the player is in the process of
1162              * moving over a gem, we draw the gem iff they haven't
1163              * gone past it yet.
1164              */
1165             if (oldstate && oldstate->grid[y*w+x] != state->grid[y*w+x]) {
1166                 /*
1167                  * Compute the distance from this square to the
1168                  * original player position.
1169                  */
1170                 int dist = max(abs(x - oldstate->px), abs(y - oldstate->py));
1171
1172                 /*
1173                  * If the player has reached here, use the new grid
1174                  * element. Otherwise use the old one.
1175                  */
1176                 if (player_dist < dist)
1177                     v = oldstate->grid[y*w+x];
1178                 else
1179                     v = state->grid[y*w+x];
1180             }
1181
1182             /*
1183              * Special case: erase the mine the dead player is
1184              * sitting on. Only at the end of the move.
1185              */
1186             if (v == MINE && !oldstate && state->dead &&
1187                 x == state->px && y == state->py)
1188                 v = BLANK;
1189
1190             if (v == GEM)
1191                 gems++;
1192
1193             v |= flashtype;
1194
1195             if (ds->grid[y*w+x] != v) {
1196                 draw_tile(dr, ds, x, y, v);
1197                 ds->grid[y*w+x] = v;
1198             }
1199         }
1200
1201     /*
1202      * Gem counter in the status bar. We replace it with
1203      * `COMPLETED!' when it reaches zero ... or rather, when the
1204      * _current state_'s gem counter is zero. (Thus, `Gems: 0' is
1205      * shown between the collection of the last gem and the
1206      * completion of the move animation that did it.)
1207      */
1208     if (state->dead && (!oldstate || oldstate->dead))
1209         sprintf(status, "DEAD!");
1210     else if (state->gems || (oldstate && oldstate->gems))
1211         sprintf(status, "Gems: %d", gems);
1212     else
1213         sprintf(status, "COMPLETED!");
1214     /* We subtract one from the visible death counter if we're still
1215      * animating the move at the end of which the death took place. */
1216     deaths = ui->deaths;
1217     if (oldstate && ui->just_died) {
1218         assert(deaths > 0);
1219         deaths--;
1220     }
1221     if (deaths)
1222         sprintf(status + strlen(status), "   Deaths: %d", deaths);
1223     status_bar(dr, status);
1224
1225     /*
1226      * Draw the player sprite.
1227      */
1228     assert(!ds->player_bg_saved);
1229     assert(ds->player_background);
1230     {
1231         int ox, oy, nx, ny;
1232         nx = COORD(state->px);
1233         ny = COORD(state->py);
1234         if (oldstate) {
1235             ox = COORD(oldstate->px);
1236             oy = COORD(oldstate->py);
1237         } else {
1238             ox = nx;
1239             oy = ny;
1240         }
1241         ds->pbgx = ox + ap * (nx - ox);
1242         ds->pbgy = oy + ap * (ny - oy);
1243     }
1244     blitter_save(dr, ds->player_background, ds->pbgx, ds->pbgy);
1245     draw_player(dr, ds, ds->pbgx, ds->pbgy, (state->dead && !oldstate));
1246     ds->player_bg_saved = TRUE;
1247 }
1248
1249 static float game_anim_length(game_state *oldstate, game_state *newstate,
1250                               int dir, game_ui *ui)
1251 {
1252     int dist;
1253     if (dir > 0)
1254         dist = newstate->distance_moved;
1255     else
1256         dist = oldstate->distance_moved;
1257     ui->anim_length = sqrt(dist) * BASE_ANIM_LENGTH;
1258     return ui->anim_length;
1259 }
1260
1261 static float game_flash_length(game_state *oldstate, game_state *newstate,
1262                                int dir, game_ui *ui)
1263 {
1264     if (!oldstate->dead && newstate->dead) {
1265         ui->flashtype = FLASH_DEAD;
1266         return FLASH_LENGTH;
1267     } else if (oldstate->gems && !newstate->gems) {
1268         ui->flashtype = FLASH_WIN;
1269         return FLASH_LENGTH;
1270     }
1271     return 0.0F;
1272 }
1273
1274 static int game_wants_statusbar(void)
1275 {
1276     return TRUE;
1277 }
1278
1279 static int game_timing_state(game_state *state, game_ui *ui)
1280 {
1281     return TRUE;
1282 }
1283
1284 static void game_print_size(game_params *params, float *x, float *y)
1285 {
1286 }
1287
1288 static void game_print(drawing *dr, game_state *state, int tilesize)
1289 {
1290 }
1291
1292 #ifdef COMBINED
1293 #define thegame inertia
1294 #endif
1295
1296 const struct game thegame = {
1297     "Inertia", "games.inertia",
1298     default_params,
1299     game_fetch_preset,
1300     decode_params,
1301     encode_params,
1302     free_params,
1303     dup_params,
1304     TRUE, game_configure, custom_params,
1305     validate_params,
1306     new_game_desc,
1307     validate_desc,
1308     new_game,
1309     dup_game,
1310     free_game,
1311     FALSE, solve_game,
1312     FALSE, game_text_format,
1313     new_ui,
1314     free_ui,
1315     encode_ui,
1316     decode_ui,
1317     game_changed_state,
1318     interpret_move,
1319     execute_move,
1320     PREFERRED_TILESIZE, game_compute_size, game_set_size,
1321     game_colours,
1322     game_new_drawstate,
1323     game_free_drawstate,
1324     game_redraw,
1325     game_anim_length,
1326     game_flash_length,
1327     FALSE, FALSE, game_print_size, game_print,
1328     game_wants_statusbar,
1329     FALSE, game_timing_state,
1330     0,                                 /* mouse_priorities */
1331 };