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 DP1 (DIRECTIONS+1)
  36 #define DX(dir) ( (dir) & 3 ? (((dir) & 7) > 4 ? -1 : +1) : 0 )
  37 #define DY(dir) ( DX((dir)+6) )
  38
  39 /*
  40  * Lvalue macro which expects x and y to be in range.
  41  */
  42 #define LV_AT(w, h, grid, x, y) ( (grid)[(y)*(w)+(x)] )
  43
  44 /*
  45  * Rvalue macro which can cope with x and y being out of range.
  46  */
  47 #define AT(w, h, grid, x, y) ( (x)<0 || (x)>=(w) || (y)<0 || (y)>=(h) ? \
  48                                WALL : LV_AT(w, h, grid, x, y) )
  49
  50 enum {
  51     COL_BACKGROUND,
  52     COL_OUTLINE,
  53     COL_HIGHLIGHT,
  54     COL_LOWLIGHT,
  55     COL_PLAYER,
  56     COL_DEAD_PLAYER,
  57     COL_MINE,
  58     COL_GEM,
  59     COL_WALL,
  60     COL_HINT,
  61     NCOLOURS
  62 };
  63
  64 struct game_params {
  65     int w, h;
  66 };
  67
  68 typedef struct soln {
  69     int refcount;
  70     int len;
  71     unsigned char *list;
  72 } soln;
  73
  74 struct game_state {
  75     game_params p;
  76     int px, py;
  77     int gems;
  78     char *grid;
  79     int distance_moved;
  80     int dead;
  81     int cheated;
  82     int solnpos;
  83     soln *soln;
  84 };
  85
  86 static game_params *default_params(void)
  87 {
  88     game_params *ret = snew(game_params);
  89
  90     ret->w = 10;
  91 #ifdef PORTRAIT_SCREEN
  92     ret->h = 10;
  93 #else
  94     ret->h = 8;
  95 #endif
  96     return ret;
  97 }
  98
  99 static void free_params(game_params *params)
 100 {
 101     sfree(params);
 102 }
 103
 104 static game_params *dup_params(const game_params *params)
 105 {
 106     game_params *ret = snew(game_params);
 107     *ret = *params;                    /* structure copy */
 108     return ret;
 109 }
 110
 111 static const struct game_params inertia_presets[] = {
 112 #ifdef PORTRAIT_SCREEN
 113     { 10, 10 },
 114     { 12, 12 },
 115     { 16, 16 },
 116 #else
 117     { 10, 8 },
 118     { 15, 12 },
 119     { 20, 16 },
 120 #endif
 121 };
 122
 123 static int game_fetch_preset(int i, char **name, game_params **params)
 124 {
 125     game_params p, *ret;
 126     char *retname;
 127     char namebuf[80];
 128
 129     if (i < 0 || i >= lenof(inertia_presets))
 130         return FALSE;
 131
 132     p = inertia_presets[i];
 133     ret = dup_params(&p);
 134     sprintf(namebuf, "%dx%d", ret->w, ret->h);
 135     retname = dupstr(namebuf);
 136
 137     *params = ret;
 138     *name = retname;
 139     return TRUE;
 140 }
 141
 142 static void decode_params(game_params *params, char const *string)
 143 {
 144     params->w = params->h = atoi(string);
 145     while (*string && isdigit((unsigned char)*string)) string++;
 146     if (*string == 'x') {
 147         string++;
 148         params->h = atoi(string);
 149     }
 150 }
 151
 152 static char *encode_params(const game_params *params, int full)
 153 {
 154     char data[256];
 155
 156     sprintf(data, "%dx%d", params->w, params->h);
 157
 158     return dupstr(data);
 159 }
 160
 161 static config_item *game_configure(const game_params *params)
 162 {
 163     config_item *ret;
 164     char buf[80];
 165
 166     ret = snewn(3, config_item);
 167
 168     ret[0].name = "Width";
 169     ret[0].type = C_STRING;
 170     sprintf(buf, "%d", params->w);
 171     ret[0].u.string.sval = dupstr(buf);
 172
 173     ret[1].name = "Height";
 174     ret[1].type = C_STRING;
 175     sprintf(buf, "%d", params->h);
 176     ret[1].u.string.sval = dupstr(buf);
 177
 178     ret[2].name = NULL;
 179     ret[2].type = C_END;
 180
 181     return ret;
 182 }
 183
 184 static game_params *custom_params(const config_item *cfg)
 185 {
 186     game_params *ret = snew(game_params);
 187
 188     ret->w = atoi(cfg[0].u.string.sval);
 189     ret->h = atoi(cfg[1].u.string.sval);
 190
 191     return ret;
 192 }
 193
 194 static const char *validate_params(const game_params *params, int full)
 195 {
 196     /*
 197      * Avoid completely degenerate cases which only have one
 198      * row/column. We probably could generate completable puzzles
 199      * of that shape, but they'd be forced to be extremely boring
 200      * and at large sizes would take a while to happen upon at
 201      * random as well.
 202      */
 203     if (params->w < 2 || params->h < 2)
 204         return "Width and height must both be at least two";
 205
 206     /*
 207      * The grid construction algorithm creates 1/5 as many gems as
 208      * grid squares, and must create at least one gem to have an
 209      * actual puzzle. However, an area-five grid is ruled out by
 210      * the above constraint, so the practical minimum is six.
 211      */
 212     if (params->w * params->h < 6)
 213         return "Grid area must be at least six squares";
 214
 215     return NULL;
 216 }
 217
 218 /* ----------------------------------------------------------------------
 219  * Solver used by grid generator.
 220  */
 221
 222 struct solver_scratch {
 223     unsigned char *reachable_from, *reachable_to;
 224     int *positions;
 225 };
 226
 227 static struct solver_scratch *new_scratch(int w, int h)
 228 {
 229     struct solver_scratch *sc = snew(struct solver_scratch);
 230
 231     sc->reachable_from = snewn(w * h * DIRECTIONS, unsigned char);
 232     sc->reachable_to = snewn(w * h * DIRECTIONS, unsigned char);
 233     sc->positions = snewn(w * h * DIRECTIONS, int);
 234
 235     return sc;
 236 }
 237
 238 static void free_scratch(struct solver_scratch *sc)
 239 {
 240     sfree(sc->reachable_from);
 241     sfree(sc->reachable_to);
 242     sfree(sc->positions);
 243     sfree(sc);
 244 }
 245
 246 static int can_go(int w, int h, char *grid,
 247                   int x1, int y1, int dir1, int x2, int y2, int dir2)
 248 {
 249     /*
 250      * Returns TRUE if we can transition directly from (x1,y1)
 251      * going in direction dir1, to (x2,y2) going in direction dir2.
 252      */
 253
 254     /*
 255      * If we're actually in the middle of an unoccupyable square,
 256      * we cannot make any move.
 257      */
 258     if (AT(w, h, grid, x1, y1) == WALL ||
 259         AT(w, h, grid, x1, y1) == MINE)
 260         return FALSE;
 261
 262     /*
 263      * If a move is capable of stopping at x1,y1,dir1, and x2,y2 is
 264      * the same coordinate as x1,y1, then we can make the
 265      * transition (by stopping and changing direction).
 266      *
 267      * For this to be the case, we have to either have a wall
 268      * beyond x1,y1,dir1, or have a stop on x1,y1.
 269      */
 270     if (x2 == x1 && y2 == y1 &&
 271         (AT(w, h, grid, x1, y1) == STOP ||
 272          AT(w, h, grid, x1, y1) == START ||
 273          AT(w, h, grid, x1+DX(dir1), y1+DY(dir1)) == WALL))
 274         return TRUE;
 275
 276     /*
 277      * If a move is capable of continuing here, then x1,y1,dir1 can
 278      * move one space further on.
 279      */
 280     if (x2 == x1+DX(dir1) && y2 == y1+DY(dir1) && dir1 == dir2 &&
 281         (AT(w, h, grid, x2, y2) == BLANK ||
 282          AT(w, h, grid, x2, y2) == GEM ||
 283          AT(w, h, grid, x2, y2) == STOP ||
 284          AT(w, h, grid, x2, y2) == START))
 285         return TRUE;
 286
 287     /*
 288      * That's it.
 289      */
 290     return FALSE;
 291 }
 292
 293 static int find_gem_candidates(int w, int h, char *grid,
 294                                struct solver_scratch *sc)
 295 {
 296     int wh = w*h;
 297     int head, tail;
 298     int sx, sy, gx, gy, gd, pass, possgems;
 299
 300     /*
 301      * This function finds all the candidate gem squares, which are
 302      * precisely those squares which can be picked up on a loop
 303      * from the starting point back to the starting point. Doing
 304      * this may involve passing through such a square in the middle
 305      * of a move; so simple breadth-first search over the _squares_
 306      * of the grid isn't quite adequate, because it might be that
 307      * we can only reach a gem from the start by moving over it in
 308      * one direction, but can only return to the start if we were
 309      * moving over it in another direction.
 310      *
 311      * Instead, we BFS over a space which mentions each grid square
 312      * eight times - once for each direction. We also BFS twice:
 313      * once to find out what square+direction pairs we can reach
 314      * _from_ the start point, and once to find out what pairs we
 315      * can reach the start point from. Then a square is reachable
 316      * if any of the eight directions for that square has both
 317      * flags set.
 318      */
 319
 320     memset(sc->reachable_from, 0, wh * DIRECTIONS);
 321     memset(sc->reachable_to, 0, wh * DIRECTIONS);
 322
 323     /*
 324      * Find the starting square.
 325      */
 326     sx = -1;                           /* placate optimiser */
 327     for (sy = 0; sy < h; sy++) {
 328         for (sx = 0; sx < w; sx++)
 329             if (AT(w, h, grid, sx, sy) == START)
 330                 break;
 331         if (sx < w)
 332             break;
 333     }
 334     assert(sy < h);
 335
 336     for (pass = 0; pass < 2; pass++) {
 337         unsigned char *reachable = (pass == 0 ? sc->reachable_from :
 338                                     sc->reachable_to);
 339         int sign = (pass == 0 ? +1 : -1);
 340         int dir;
 341
 342 #ifdef SOLVER_DIAGNOSTICS
 343         printf("starting pass %d\n", pass);
 344 #endif
 345
 346         /*
 347          * `head' and `tail' are indices within sc->positions which
 348          * track the list of board positions left to process.
 349          */
 350         head = tail = 0;
 351         for (dir = 0; dir < DIRECTIONS; dir++) {
 352             int index = (sy*w+sx)*DIRECTIONS+dir;
 353             sc->positions[tail++] = index;
 354             reachable[index] = TRUE;
 355 #ifdef SOLVER_DIAGNOSTICS
 356             printf("starting point %d,%d,%d\n", sx, sy, dir);
 357 #endif
 358         }
 359
 360         /*
 361          * Now repeatedly pick an element off the list and process
 362          * it.
 363          */
 364         while (head < tail) {
 365             int index = sc->positions[head++];
 366             int dir = index % DIRECTIONS;
 367             int x = (index / DIRECTIONS) % w;
 368             int y = index / (w * DIRECTIONS);
 369             int n, x2, y2, d2, i2;
 370
 371 #ifdef SOLVER_DIAGNOSTICS
 372             printf("processing point %d,%d,%d\n", x, y, dir);
 373 #endif
 374             /*
 375              * The places we attempt to switch to here are:
 376              *  - each possible direction change (all the other
 377              *    directions in this square)
 378              *  - one step further in the direction we're going (or
 379              *    one step back, if we're in the reachable_to pass).
 380              */
 381             for (n = -1; n < DIRECTIONS; n++) {
 382                 if (n < 0) {
 383                     x2 = x + sign * DX(dir);
 384                     y2 = y + sign * DY(dir);
 385                     d2 = dir;
 386                 } else {
 387                     x2 = x;
 388                     y2 = y;
 389                     d2 = n;
 390                 }
 391                 i2 = (y2*w+x2)*DIRECTIONS+d2;
 392                 if (x2 >= 0 && x2 < w &&
 393                     y2 >= 0 && y2 < h &&
 394                     !reachable[i2]) {
 395                     int ok;
 396 #ifdef SOLVER_DIAGNOSTICS
 397                     printf("  trying point %d,%d,%d", x2, y2, d2);
 398 #endif
 399                     if (pass == 0)
 400                         ok = can_go(w, h, grid, x, y, dir, x2, y2, d2);
 401                     else
 402                         ok = can_go(w, h, grid, x2, y2, d2, x, y, dir);
 403 #ifdef SOLVER_DIAGNOSTICS
 404                     printf(" - %sok\n", ok ? "" : "not ");
 405 #endif
 406                     if (ok) {
 407                         sc->positions[tail++] = i2;
 408                         reachable[i2] = TRUE;
 409                     }
 410                 }
 411             }
 412         }
 413     }
 414
 415     /*
 416      * And that should be it. Now all we have to do is find the
 417      * squares for which there exists _some_ direction such that
 418      * the square plus that direction form a tuple which is both
 419      * reachable from the start and reachable to the start.
 420      */
 421     possgems = 0;
 422     for (gy = 0; gy < h; gy++)
 423         for (gx = 0; gx < w; gx++)
 424             if (AT(w, h, grid, gx, gy) == BLANK) {
 425                 for (gd = 0; gd < DIRECTIONS; gd++) {
 426                     int index = (gy*w+gx)*DIRECTIONS+gd;
 427                     if (sc->reachable_from[index] && sc->reachable_to[index]) {
 428 #ifdef SOLVER_DIAGNOSTICS
 429                         printf("space at %d,%d is reachable via"
 430                                " direction %d\n", gx, gy, gd);
 431 #endif
 432                         LV_AT(w, h, grid, gx, gy) = POSSGEM;
 433                         possgems++;
 434                         break;
 435                     }
 436                 }
 437             }
 438
 439     return possgems;
 440 }
 441
 442 /* ----------------------------------------------------------------------
 443  * Grid generation code.
 444  */
 445
 446 static char *gengrid(int w, int h, random_state *rs)
 447 {
 448     int wh = w*h;
 449     char *grid = snewn(wh+1, char);
 450     struct solver_scratch *sc = new_scratch(w, h);
 451     int maxdist_threshold, tries;
 452
 453     maxdist_threshold = 2;
 454     tries = 0;
 455
 456     while (1) {
 457         int i, j;
 458         int possgems;
 459         int *dist, *list, head, tail, maxdist;
 460
 461         /*
 462          * We're going to fill the grid with the five basic piece
 463          * types in about 1/5 proportion. For the moment, though,
 464          * we leave out the gems, because we'll put those in
 465          * _after_ we run the solver to tell us where the viable
 466          * locations are.
 467          */
 468         i = 0;
 469         for (j = 0; j < wh/5; j++)
 470             grid[i++] = WALL;
 471         for (j = 0; j < wh/5; j++)
 472             grid[i++] = STOP;
 473         for (j = 0; j < wh/5; j++)
 474             grid[i++] = MINE;
 475         assert(i < wh);
 476         grid[i++] = START;
 477         while (i < wh)
 478             grid[i++] = BLANK;
 479         shuffle(grid, wh, sizeof(*grid), rs);
 480
 481         /*
 482          * Find the viable gem locations, and immediately give up
 483          * and try again if there aren't enough of them.
 484          */
 485         possgems = find_gem_candidates(w, h, grid, sc);
 486         if (possgems < wh/5)
 487             continue;
 488
 489         /*
 490          * We _could_ now select wh/5 of the POSSGEMs and set them
 491          * to GEM, and have a viable level. However, there's a
 492          * chance that a large chunk of the level will turn out to
 493          * be unreachable, so first we test for that.
 494          *
 495          * We do this by finding the largest distance from any
 496          * square to the nearest POSSGEM, by breadth-first search.
 497          * If this is above a critical threshold, we abort and try
 498          * again.
 499          *
 500          * (This search is purely geometric, without regard to
 501          * walls and long ways round.)
 502          */
 503         dist = sc->positions;
 504         list = sc->positions + wh;
 505         for (i = 0; i < wh; i++)
 506             dist[i] = -1;
 507         head = tail = 0;
 508         for (i = 0; i < wh; i++)
 509             if (grid[i] == POSSGEM) {
 510                 dist[i] = 0;
 511                 list[tail++] = i;
 512             }
 513         maxdist = 0;
 514         while (head < tail) {
 515             int pos, x, y, d;
 516
 517             pos = list[head++];
 518             if (maxdist < dist[pos])
 519                 maxdist = dist[pos];
 520
 521             x = pos % w;
 522             y = pos / w;
 523
 524             for (d = 0; d < DIRECTIONS; d++) {
 525                 int x2, y2, p2;
 526
 527                 x2 = x + DX(d);
 528                 y2 = y + DY(d);
 529
 530                 if (x2 >= 0 && x2 < w && y2 >= 0 && y2 < h) {
 531                     p2 = y2*w+x2;
 532                     if (dist[p2] < 0) {
 533                         dist[p2] = dist[pos] + 1;
 534                         list[tail++] = p2;
 535                     }
 536                 }
 537             }
 538         }
 539         assert(head == wh && tail == wh);
 540
 541         /*
 542          * Now abandon this grid and go round again if maxdist is
 543          * above the required threshold.
 544          *
 545          * We can safely start the threshold as low as 2. As we
 546          * accumulate failed generation attempts, we gradually
 547          * raise it as we get more desperate.
 548          */
 549         if (maxdist > maxdist_threshold) {
 550             tries++;
 551             if (tries == 50) {
 552                 maxdist_threshold++;
 553                 tries = 0;
 554             }
 555             continue;
 556         }
 557
 558         /*
 559          * Now our reachable squares are plausibly evenly
 560          * distributed over the grid. I'm not actually going to
 561          * _enforce_ that I place the gems in such a way as not to
 562          * increase that maxdist value; I'm now just going to trust
 563          * to the RNG to pick a sensible subset of the POSSGEMs.
 564          */
 565         j = 0;
 566         for (i = 0; i < wh; i++)
 567             if (grid[i] == POSSGEM)
 568                 list[j++] = i;
 569         shuffle(list, j, sizeof(*list), rs);
 570         for (i = 0; i < j; i++)
 571             grid[list[i]] = (i < wh/5 ? GEM : BLANK);
 572         break;
 573     }
 574
 575     free_scratch(sc);
 576
 577     grid[wh] = '\0';
 578
 579     return grid;
 580 }
 581
 582 static char *new_game_desc(const game_params *params, random_state *rs,
 583                            char **aux, int interactive)
 584 {
 585     return gengrid(params->w, params->h, rs);
 586 }
 587
 588 static const char *validate_desc(const game_params *params, const char *desc)
 589 {
 590     int w = params->w, h = params->h, wh = w*h;
 591     int starts = 0, gems = 0, i;
 592
 593     for (i = 0; i < wh; i++) {
 594         if (!desc[i])
 595             return "Not enough data to fill grid";
 596         if (desc[i] != WALL && desc[i] != START && desc[i] != STOP &&
 597             desc[i] != GEM && desc[i] != MINE && desc[i] != BLANK)
 598             return "Unrecognised character in game description";
 599         if (desc[i] == START)
 600             starts++;
 601         if (desc[i] == GEM)
 602             gems++;
 603     }
 604     if (desc[i])
 605         return "Too much data to fill grid";
 606     if (starts < 1)
 607         return "No starting square specified";
 608     if (starts > 1)
 609         return "More than one starting square specified";
 610     if (gems < 1)
 611         return "No gems specified";
 612
 613     return NULL;
 614 }
 615
 616 static game_state *new_game(midend *me, const game_params *params,
 617                             const char *desc)
 618 {
 619     int w = params->w, h = params->h, wh = w*h;
 620     int i;
 621     game_state *state = snew(game_state);
 622
 623     state->p = *params;                /* structure copy */
 624
 625     state->grid = snewn(wh, char);
 626     assert(strlen(desc) == wh);
 627     memcpy(state->grid, desc, wh);
 628
 629     state->px = state->py = -1;
 630     state->gems = 0;
 631     for (i = 0; i < wh; i++) {
 632         if (state->grid[i] == START) {
 633             state->grid[i] = STOP;
 634             state->px = i % w;
 635             state->py = i / w;
 636         } else if (state->grid[i] == GEM) {
 637             state->gems++;
 638         }
 639     }
 640
 641     assert(state->gems > 0);
 642     assert(state->px >= 0 && state->py >= 0);
 643
 644     state->distance_moved = 0;
 645     state->dead = FALSE;
 646
 647     state->cheated = FALSE;
 648     state->solnpos = 0;
 649     state->soln = NULL;
 650
 651     return state;
 652 }
 653
 654 static game_state *dup_game(const game_state *state)
 655 {
 656     int w = state->p.w, h = state->p.h, wh = w*h;
 657     game_state *ret = snew(game_state);
 658
 659     ret->p = state->p;
 660     ret->px = state->px;
 661     ret->py = state->py;
 662     ret->gems = state->gems;
 663     ret->grid = snewn(wh, char);
 664     ret->distance_moved = state->distance_moved;
 665     ret->dead = FALSE;
 666     memcpy(ret->grid, state->grid, wh);
 667     ret->cheated = state->cheated;
 668     ret->soln = state->soln;
 669     if (ret->soln)
 670         ret->soln->refcount++;
 671     ret->solnpos = state->solnpos;
 672
 673     return ret;
 674 }
 675
 676 static void free_game(game_state *state)
 677 {
 678     if (state->soln && --state->soln->refcount == 0) {
 679         sfree(state->soln->list);
 680         sfree(state->soln);
 681     }
 682     sfree(state->grid);
 683     sfree(state);
 684 }
 685
 686 /*
 687  * Internal function used by solver.
 688  */
 689 static int move_goes_to(int w, int h, char *grid, int x, int y, int d)
 690 {
 691     int dr;
 692
 693     /*
 694      * See where we'd get to if we made this move.
 695      */
 696     dr = -1;                           /* placate optimiser */
 697     while (1) {
 698         if (AT(w, h, grid, x+DX(d), y+DY(d)) == WALL) {
 699             dr = DIRECTIONS;           /* hit a wall, so end up stationary */
 700             break;
 701         }
 702         x += DX(d);
 703         y += DY(d);
 704         if (AT(w, h, grid, x, y) == STOP) {
 705             dr = DIRECTIONS;           /* hit a stop, so end up stationary */
 706             break;
 707         }
 708         if (AT(w, h, grid, x, y) == GEM) {
 709             dr = d;                    /* hit a gem, so we're still moving */
 710             break;
 711         }
 712         if (AT(w, h, grid, x, y) == MINE)
 713             return -1;                 /* hit a mine, so move is invalid */
 714     }
 715     assert(dr >= 0);
 716     return (y*w+x)*DP1+dr;
 717 }
 718
 719 static int compare_integers(const void *av, const void *bv)
 720 {
 721     const int *a = (const int *)av;
 722     const int *b = (const int *)bv;
 723     if (*a < *b)
 724         return -1;
 725     else if (*a > *b)
 726         return +1;
 727     else
 728         return 0;
 729 }
 730
 731 static char *solve_game(const game_state *state, const game_state *currstate,
 732                         const char *aux, const char **error)
 733 {
 734     int w = currstate->p.w, h = currstate->p.h, wh = w*h;
 735     int *nodes, *nodeindex, *edges, *backedges, *edgei, *backedgei, *circuit;
 736     int nedges;
 737     int *dist, *dist2, *list;
 738     int *unvisited;
 739     int circuitlen, circuitsize;
 740     int head, tail, pass, i, j, n, x, y, d, dd;
 741     const char *err;
 742     char *soln, *p;
 743
 744     /*
 745      * Before anything else, deal with the special case in which
 746      * all the gems are already collected.
 747      */
 748     for (i = 0; i < wh; i++)
 749         if (currstate->grid[i] == GEM)
 750             break;
 751     if (i == wh) {
 752         *error = "Game is already solved";
 753         return NULL;
 754     }
 755
 756     /*
 757      * Solving Inertia is a question of first building up the graph
 758      * of where you can get to from where, and secondly finding a
 759      * tour of the graph which takes in every gem.
 760      *
 761      * This is of course a close cousin of the travelling salesman
 762      * problem, which is NP-complete; so I rather doubt that any
 763      * _optimal_ tour can be found in plausible time. Hence I'll
 764      * restrict myself to merely finding a not-too-bad one.
 765      *
 766      * First construct the graph, by bfsing out move by move from
 767      * the current player position. Graph vertices will be
 768      *  - every endpoint of a move (place the ball can be
 769      *    stationary)
 770      *  - every gem (place the ball can go through in motion).
 771      *    Vertices of this type have an associated direction, since
 772      *    if a gem can be collected by sliding through it in two
 773      *    different directions it doesn't follow that you can
 774      *    change direction at it.
 775      *
 776      * I'm going to refer to a non-directional vertex as
 777      * (y*w+x)*DP1+DIRECTIONS, and a directional one as
 778      * (y*w+x)*DP1+d.
 779      */
 780
 781     /*
 782      * nodeindex[] maps node codes as shown above to numeric
 783      * indices in the nodes[] array.
 784      */
 785     nodeindex = snewn(DP1*wh, int);
 786     for (i = 0; i < DP1*wh; i++)
 787         nodeindex[i] = -1;
 788
 789     /*
 790      * Do the bfs to find all the interesting graph nodes.
 791      */
 792     nodes = snewn(DP1*wh, int);
 793     head = tail = 0;
 794
 795     nodes[tail] = (currstate->py * w + currstate->px) * DP1 + DIRECTIONS;
 796     nodeindex[nodes[0]] = tail;
 797     tail++;
 798
 799     while (head < tail) {
 800         int nc = nodes[head++], nnc;
 801
 802         d = nc % DP1;
 803
 804         /*
 805          * Plot all possible moves from this node. If the node is
 806          * directed, there's only one.
 807          */
 808         for (dd = 0; dd < DIRECTIONS; dd++) {
 809             x = nc / DP1;
 810             y = x / w;
 811             x %= w;
 812
 813             if (d < DIRECTIONS && d != dd)
 814                 continue;
 815
 816             nnc = move_goes_to(w, h, currstate->grid, x, y, dd);
 817             if (nnc >= 0 && nnc != nc) {
 818                 if (nodeindex[nnc] < 0) {
 819                     nodes[tail] = nnc;
 820                     nodeindex[nnc] = tail;
 821                     tail++;
 822                 }
 823             }
 824         }
 825     }
 826     n = head;
 827
 828     /*
 829      * Now we know how many nodes we have, allocate the edge array
 830      * and go through setting up the edges.
 831      */
 832     edges = snewn(DIRECTIONS*n, int);
 833     edgei = snewn(n+1, int);
 834     nedges = 0;
 835
 836     for (i = 0; i < n; i++) {
 837         int nc = nodes[i];
 838
 839         edgei[i] = nedges;
 840
 841         d = nc % DP1;
 842         x = nc / DP1;
 843         y = x / w;
 844         x %= w;
 845
 846         for (dd = 0; dd < DIRECTIONS; dd++) {
 847             int nnc;
 848
 849             if (d >= DIRECTIONS || d == dd) {
 850                 nnc = move_goes_to(w, h, currstate->grid, x, y, dd);
 851
 852                 if (nnc >= 0 && nnc != nc)
 853                     edges[nedges++] = nodeindex[nnc];
 854             }
 855         }
 856     }
 857     edgei[n] = nedges;
 858
 859     /*
 860      * Now set up the backedges array.
 861      */
 862     backedges = snewn(nedges, int);
 863     backedgei = snewn(n+1, int);
 864     for (i = j = 0; i < nedges; i++) {
 865         while (j+1 < n && i >= edgei[j+1])
 866             j++;
 867         backedges[i] = edges[i] * n + j;
 868     }
 869     qsort(backedges, nedges, sizeof(int), compare_integers);
 870     backedgei[0] = 0;
 871     for (i = j = 0; i < nedges; i++) {
 872         int k = backedges[i] / n;
 873         backedges[i] %= n;
 874         while (j < k)
 875             backedgei[++j] = i;
 876     }
 877     backedgei[n] = nedges;
 878
 879     /*
 880      * Set up the initial tour. At all times, our tour is a circuit
 881      * of graph vertices (which may, and probably will often,
 882      * repeat vertices). To begin with, it's got exactly one vertex
 883      * in it, which is the player's current starting point.
 884      */
 885     circuitsize = 256;
 886     circuit = snewn(circuitsize, int);
 887     circuitlen = 0;
 888     circuit[circuitlen++] = 0;         /* node index 0 is the starting posn */
 889
 890     /*
 891      * Track which gems are as yet unvisited.
 892      */
 893     unvisited = snewn(wh, int);
 894     for (i = 0; i < wh; i++)
 895         unvisited[i] = FALSE;
 896     for (i = 0; i < wh; i++)
 897         if (currstate->grid[i] == GEM)
 898             unvisited[i] = TRUE;
 899
 900     /*
 901      * Allocate space for doing bfses inside the main loop.
 902      */
 903     dist = snewn(n, int);
 904     dist2 = snewn(n, int);
 905     list = snewn(n, int);
 906
 907     err = NULL;
 908     soln = NULL;
 909
 910     /*
 911      * Now enter the main loop, in each iteration of which we
 912      * extend the tour to take in an as yet uncollected gem.
 913      */
 914     while (1) {
 915         int target, n1, n2, bestdist, extralen, targetpos;
 916
 917 #ifdef TSP_DIAGNOSTICS
 918         printf("circuit is");
 919         for (i = 0; i < circuitlen; i++) {
 920             int nc = nodes[circuit[i]];
 921             printf(" (%d,%d,%d)", nc/DP1%w, nc/(DP1*w), nc%DP1);
 922         }
 923         printf("\n");
 924         printf("moves are ");
 925         x = nodes[circuit[0]] / DP1 % w;
 926         y = nodes[circuit[0]] / DP1 / w;
 927         for (i = 1; i < circuitlen; i++) {
 928             int x2, y2, dx, dy;
 929             if (nodes[circuit[i]] % DP1 != DIRECTIONS)
 930                 continue;
 931             x2 = nodes[circuit[i]] / DP1 % w;
 932             y2 = nodes[circuit[i]] / DP1 / w;
 933             dx = (x2 > x ? +1 : x2 < x ? -1 : 0);
 934             dy = (y2 > y ? +1 : y2 < y ? -1 : 0);
 935             for (d = 0; d < DIRECTIONS; d++)
 936                 if (DX(d) == dx && DY(d) == dy)
 937                     printf("%c", "89632147"[d]);
 938             x = x2;
 939             y = y2;
 940         }
 941         printf("\n");
 942 #endif
 943
 944         /*
 945          * First, start a pair of bfses at _every_ vertex currently
 946          * in the tour, and extend them outwards to find the
 947          * nearest as yet unreached gem vertex.
 948          *
 949          * This is largely a heuristic: we could pick _any_ doubly
 950          * reachable node here and still get a valid tour as
 951          * output. I hope that picking a nearby one will result in
 952          * generally good tours.
 953          */
 954         for (pass = 0; pass < 2; pass++) {
 955             int *ep = (pass == 0 ? edges : backedges);
 956             int *ei = (pass == 0 ? edgei : backedgei);
 957             int *dp = (pass == 0 ? dist : dist2);
 958             head = tail = 0;
 959             for (i = 0; i < n; i++)
 960                 dp[i] = -1;
 961             for (i = 0; i < circuitlen; i++) {
 962                 int ni = circuit[i];
 963                 if (dp[ni] < 0) {
 964                     dp[ni] = 0;
 965                     list[tail++] = ni;
 966                 }
 967             }
 968             while (head < tail) {
 969                 int ni = list[head++];
 970                 for (i = ei[ni]; i < ei[ni+1]; i++) {
 971                     int ti = ep[i];
 972                     if (ti >= 0 && dp[ti] < 0) {
 973                         dp[ti] = dp[ni] + 1;
 974                         list[tail++] = ti;
 975                     }
 976                 }
 977             }
 978         }
 979         /* Now find the nearest unvisited gem. */
 980         bestdist = -1;
 981         target = -1;
 982         for (i = 0; i < n; i++) {
 983             if (unvisited[nodes[i] / DP1] &&
 984                 dist[i] >= 0 && dist2[i] >= 0) {
 985                 int thisdist = dist[i] + dist2[i];
 986                 if (bestdist < 0 || bestdist > thisdist) {
 987                     bestdist = thisdist;
 988                     target = i;
 989                 }
 990             }
 991         }
 992
 993         if (target < 0) {
 994             /*
 995              * If we get to here, we haven't found a gem we can get
 996              * at all, which means we terminate this loop.
 997              */
 998             break;
 999         }
1000
1001         /*
1002          * Now we have a graph vertex at list[tail-1] which is an
1003          * unvisited gem. We want to add that vertex to our tour.
1004          * So we run two more breadth-first searches: one starting
1005          * from that vertex and following forward edges, and
1006          * another starting from the same vertex and following
1007          * backward edges. This allows us to determine, for each
1008          * node on the current tour, how quickly we can get both to
1009          * and from the target vertex from that node.
1010          */
1011 #ifdef TSP_DIAGNOSTICS
1012         printf("target node is %d (%d,%d,%d)\n", target, nodes[target]/DP1%w,
1013                nodes[target]/DP1/w, nodes[target]%DP1);
1014 #endif
1015
1016         for (pass = 0; pass < 2; pass++) {
1017             int *ep = (pass == 0 ? edges : backedges);
1018             int *ei = (pass == 0 ? edgei : backedgei);
1019             int *dp = (pass == 0 ? dist : dist2);
1020
1021             for (i = 0; i < n; i++)
1022                 dp[i] = -1;
1023             head = tail = 0;
1024
1025             dp[target] = 0;
1026             list[tail++] = target;
1027
1028             while (head < tail) {
1029                 int ni = list[head++];
1030                 for (i = ei[ni]; i < ei[ni+1]; i++) {
1031                     int ti = ep[i];
1032                     if (ti >= 0 && dp[ti] < 0) {
1033                         dp[ti] = dp[ni] + 1;
1034 /*printf("pass %d: set dist of vertex %d to %d (via %d)\n", pass, ti, dp[ti], ni);*/
1035                         list[tail++] = ti;
1036                     }
1037                 }
1038             }
1039         }
1040
1041         /*
1042          * Now for every node n, dist[n] gives the length of the
1043          * shortest path from the target vertex to n, and dist2[n]
1044          * gives the length of the shortest path from n to the
1045          * target vertex.
1046          *
1047          * Our next step is to search linearly along the tour to
1048          * find the optimum place to insert a trip to the target
1049          * vertex and back. Our two options are either
1050          *  (a) to find two adjacent vertices A,B in the tour and
1051          *      replace the edge A->B with the path A->target->B
1052          *  (b) to find a single vertex X in the tour and replace
1053          *      it with the complete round trip X->target->X.
1054          * We do whichever takes the fewest moves.
1055          */
1056         n1 = n2 = -1;
1057         bestdist = -1;
1058         for (i = 0; i < circuitlen; i++) {
1059             int thisdist;
1060
1061             /*
1062              * Try a round trip from vertex i.
1063              */
1064             if (dist[circuit[i]] >= 0 &&
1065                 dist2[circuit[i]] >= 0) {
1066                 thisdist = dist[circuit[i]] + dist2[circuit[i]];
1067                 if (bestdist < 0 || thisdist < bestdist) {
1068                     bestdist = thisdist;
1069                     n1 = n2 = i;
1070                 }
1071             }
1072
1073             /*
1074              * Try a trip from vertex i via target to vertex i+1.
1075              */
1076             if (i+1 < circuitlen &&
1077                 dist2[circuit[i]] >= 0 &&
1078                 dist[circuit[i+1]] >= 0) {
1079                 thisdist = dist2[circuit[i]] + dist[circuit[i+1]];
1080                 if (bestdist < 0 || thisdist < bestdist) {
1081                     bestdist = thisdist;
1082                     n1 = i;
1083                     n2 = i+1;
1084                 }
1085             }
1086         }
1087         if (bestdist < 0) {
1088             /*
1089              * We couldn't find a round trip taking in this gem _at
1090              * all_. Give up.
1091              */
1092             err = "Unable to find a solution from this starting point";
1093             break;
1094         }
1095 #ifdef TSP_DIAGNOSTICS
1096         printf("insertion point: n1=%d, n2=%d, dist=%d\n", n1, n2, bestdist);
1097 #endif
1098
1099 #ifdef TSP_DIAGNOSTICS
1100         printf("circuit before lengthening is");
1101         for (i = 0; i < circuitlen; i++) {
1102             printf(" %d", circuit[i]);
1103         }
1104         printf("\n");
1105 #endif
1106
1107         /*
1108          * Now actually lengthen the tour to take in this round
1109          * trip.
1110          */
1111         extralen = dist2[circuit[n1]] + dist[circuit[n2]];
1112         if (n1 != n2)
1113             extralen--;
1114         circuitlen += extralen;
1115         if (circuitlen >= circuitsize) {
1116             circuitsize = circuitlen + 256;
1117             circuit = sresize(circuit, circuitsize, int);
1118         }
1119         memmove(circuit + n2 + extralen, circuit + n2,
1120                 (circuitlen - n2 - extralen) * sizeof(int));
1121         n2 += extralen;
1122
1123 #ifdef TSP_DIAGNOSTICS
1124         printf("circuit in middle of lengthening is");
1125         for (i = 0; i < circuitlen; i++) {
1126             printf(" %d", circuit[i]);
1127         }
1128         printf("\n");
1129 #endif
1130
1131         /*
1132          * Find the shortest-path routes to and from the target,
1133          * and write them into the circuit.
1134          */
1135         targetpos = n1 + dist2[circuit[n1]];
1136         assert(targetpos - dist2[circuit[n1]] == n1);
1137         assert(targetpos + dist[circuit[n2]] == n2);
1138         for (pass = 0; pass < 2; pass++) {
1139             int dir = (pass == 0 ? -1 : +1);
1140             int *ep = (pass == 0 ? backedges : edges);
1141             int *ei = (pass == 0 ? backedgei : edgei);
1142             int *dp = (pass == 0 ? dist : dist2);
1143             int nn = (pass == 0 ? n2 : n1);
1144             int ni = circuit[nn], ti, dest = nn;
1145
1146             while (1) {
1147                 circuit[dest] = ni;
1148                 if (dp[ni] == 0)
1149                     break;
1150                 dest += dir;
1151                 ti = -1;
1152 /*printf("pass %d: looking at vertex %d\n", pass, ni);*/
1153                 for (i = ei[ni]; i < ei[ni+1]; i++) {
1154                     ti = ep[i];
1155                     if (ti >= 0 && dp[ti] == dp[ni] - 1)
1156                         break;
1157                 }
1158                 assert(i < ei[ni+1] && ti >= 0);
1159                 ni = ti;
1160             }
1161         }
1162
1163 #ifdef TSP_DIAGNOSTICS
1164         printf("circuit after lengthening is");
1165         for (i = 0; i < circuitlen; i++) {
1166             printf(" %d", circuit[i]);
1167         }
1168         printf("\n");
1169 #endif
1170
1171         /*
1172          * Finally, mark all gems that the new piece of circuit
1173          * passes through as visited.
1174          */
1175         for (i = n1; i <= n2; i++) {
1176             int pos = nodes[circuit[i]] / DP1;
1177             assert(pos >= 0 && pos < wh);
1178             unvisited[pos] = FALSE;
1179         }
1180     }
1181
1182 #ifdef TSP_DIAGNOSTICS
1183     printf("before reduction, moves are ");
1184     x = nodes[circuit[0]] / DP1 % w;
1185     y = nodes[circuit[0]] / DP1 / w;
1186     for (i = 1; i < circuitlen; i++) {
1187         int x2, y2, dx, dy;
1188         if (nodes[circuit[i]] % DP1 != DIRECTIONS)
1189             continue;
1190         x2 = nodes[circuit[i]] / DP1 % w;
1191         y2 = nodes[circuit[i]] / DP1 / w;
1192         dx = (x2 > x ? +1 : x2 < x ? -1 : 0);
1193         dy = (y2 > y ? +1 : y2 < y ? -1 : 0);
1194         for (d = 0; d < DIRECTIONS; d++)
1195             if (DX(d) == dx && DY(d) == dy)
1196                 printf("%c", "89632147"[d]);
1197         x = x2;
1198         y = y2;
1199     }
1200     printf("\n");
1201 #endif
1202
1203     /*
1204      * That's got a basic solution. Now optimise it by removing
1205      * redundant sections of the circuit: it's entirely possible
1206      * that a piece of circuit we carefully inserted at one stage
1207      * to collect a gem has become pointless because the steps
1208      * required to collect some _later_ gem necessarily passed
1209      * through the same one.
1210      *
1211      * So first we go through and work out how many times each gem
1212      * is collected. Then we look for maximal sections of circuit
1213      * which are redundant in the sense that their removal would
1214      * not reduce any gem's collection count to zero, and replace
1215      * each one with a bfs-derived fastest path between their
1216      * endpoints.
1217      */
1218     while (1) {
1219         int oldlen = circuitlen;
1220         int dir;
1221
1222         for (dir = +1; dir >= -1; dir -= 2) {
1223
1224             for (i = 0; i < wh; i++)
1225                 unvisited[i] = 0;
1226             for (i = 0; i < circuitlen; i++) {
1227                 int xy = nodes[circuit[i]] / DP1;
1228                 if (currstate->grid[xy] == GEM)
1229                     unvisited[xy]++;
1230             }
1231
1232             /*
1233              * If there's any gem we didn't end up visiting at all,
1234              * give up.
1235              */
1236             for (i = 0; i < wh; i++) {
1237                 if (currstate->grid[i] == GEM && unvisited[i] == 0) {
1238                     err = "Unable to find a solution from this starting point";
1239                     break;
1240                 }
1241             }
1242             if (i < wh)
1243                 break;
1244
1245             for (i = j = (dir > 0 ? 0 : circuitlen-1);
1246                  i < circuitlen && i >= 0;
1247                  i += dir) {
1248                 int xy = nodes[circuit[i]] / DP1;
1249                 if (currstate->grid[xy] == GEM && unvisited[xy] > 1) {
1250                     unvisited[xy]--;
1251                 } else if (currstate->grid[xy] == GEM || i == circuitlen-1) {
1252                     /*
1253                      * circuit[i] collects a gem for the only time,
1254                      * or is the last node in the circuit.
1255                      * Therefore it cannot be removed; so we now
1256                      * want to replace the path from circuit[j] to
1257                      * circuit[i] with a bfs-shortest path.
1258                      */
1259                     int p, q, k, dest, ni, ti, thisdist;
1260
1261                     /*
1262                      * Set up the upper and lower bounds of the
1263                      * reduced section.
1264                      */
1265                     p = min(i, j);
1266                     q = max(i, j);
1267
1268 #ifdef TSP_DIAGNOSTICS
1269                     printf("optimising section from %d - %d\n", p, q);
1270 #endif
1271
1272                     for (k = 0; k < n; k++)
1273                         dist[k] = -1;
1274                     head = tail = 0;
1275
1276                     dist[circuit[p]] = 0;
1277                     list[tail++] = circuit[p];
1278
1279                     while (head < tail && dist[circuit[q]] < 0) {
1280                         int ni = list[head++];
1281                         for (k = edgei[ni]; k < edgei[ni+1]; k++) {
1282                             int ti = edges[k];
1283                             if (ti >= 0 && dist[ti] < 0) {
1284                                 dist[ti] = dist[ni] + 1;
1285                                 list[tail++] = ti;
1286                             }
1287                         }
1288                     }
1289
1290                     thisdist = dist[circuit[q]];
1291                     assert(thisdist >= 0 && thisdist <= q-p);
1292
1293                     memmove(circuit+p+thisdist, circuit+q,
1294                             (circuitlen - q) * sizeof(int));
1295                     circuitlen -= q-p;
1296                     q = p + thisdist;
1297                     circuitlen += q-p;
1298
1299                     if (dir > 0)
1300                         i = q;         /* resume loop from the right place */
1301
1302 #ifdef TSP_DIAGNOSTICS
1303                     printf("new section runs from %d - %d\n", p, q);
1304 #endif
1305
1306                     dest = q;
1307                     assert(dest >= 0);
1308                     ni = circuit[q];
1309
1310                     while (1) {
1311                         /* printf("dest=%d circuitlen=%d ni=%d dist[ni]=%d\n", dest, circuitlen, ni, dist[ni]); */
1312                         circuit[dest] = ni;
1313                         if (dist[ni] == 0)
1314                             break;
1315                         dest--;
1316                         ti = -1;
1317                         for (k = backedgei[ni]; k < backedgei[ni+1]; k++) {
1318                             ti = backedges[k];
1319                             if (ti >= 0 && dist[ti] == dist[ni] - 1)
1320                                 break;
1321                         }
1322                         assert(k < backedgei[ni+1] && ti >= 0);
1323                         ni = ti;
1324                     }
1325
1326                     /*
1327                      * Now re-increment the visit counts for the
1328                      * new path.
1329                      */
1330                     while (++p < q) {
1331                         int xy = nodes[circuit[p]] / DP1;
1332                         if (currstate->grid[xy] == GEM)
1333                             unvisited[xy]++;
1334                     }
1335
1336                     j = i;
1337
1338 #ifdef TSP_DIAGNOSTICS
1339                     printf("during reduction, circuit is");
1340                     for (k = 0; k < circuitlen; k++) {
1341                         int nc = nodes[circuit[k]];
1342                         printf(" (%d,%d,%d)", nc/DP1%w, nc/(DP1*w), nc%DP1);
1343                     }
1344                     printf("\n");
1345                     printf("moves are ");
1346                     x = nodes[circuit[0]] / DP1 % w;
1347                     y = nodes[circuit[0]] / DP1 / w;
1348                     for (k = 1; k < circuitlen; k++) {
1349                         int x2, y2, dx, dy;
1350                         if (nodes[circuit[k]] % DP1 != DIRECTIONS)
1351                             continue;
1352                         x2 = nodes[circuit[k]] / DP1 % w;
1353                         y2 = nodes[circuit[k]] / DP1 / w;
1354                         dx = (x2 > x ? +1 : x2 < x ? -1 : 0);
1355                         dy = (y2 > y ? +1 : y2 < y ? -1 : 0);
1356                         for (d = 0; d < DIRECTIONS; d++)
1357                             if (DX(d) == dx && DY(d) == dy)
1358                                 printf("%c", "89632147"[d]);
1359                         x = x2;
1360                         y = y2;
1361                     }
1362                     printf("\n");
1363 #endif
1364                 }
1365             }
1366
1367 #ifdef TSP_DIAGNOSTICS
1368             printf("after reduction, moves are ");
1369             x = nodes[circuit[0]] / DP1 % w;
1370             y = nodes[circuit[0]] / DP1 / w;
1371             for (i = 1; i < circuitlen; i++) {
1372                 int x2, y2, dx, dy;
1373                 if (nodes[circuit[i]] % DP1 != DIRECTIONS)
1374                     continue;
1375                 x2 = nodes[circuit[i]] / DP1 % w;
1376                 y2 = nodes[circuit[i]] / DP1 / w;
1377                 dx = (x2 > x ? +1 : x2 < x ? -1 : 0);
1378                 dy = (y2 > y ? +1 : y2 < y ? -1 : 0);
1379                 for (d = 0; d < DIRECTIONS; d++)
1380                     if (DX(d) == dx && DY(d) == dy)
1381                         printf("%c", "89632147"[d]);
1382                 x = x2;
1383                 y = y2;
1384             }
1385             printf("\n");
1386 #endif
1387         }
1388
1389         /*
1390          * If we've managed an entire reduction pass in each
1391          * direction and not made the solution any shorter, we're
1392          * _really_ done.
1393          */
1394         if (circuitlen == oldlen)
1395             break;
1396     }
1397
1398     /*
1399      * Encode the solution as a move string.
1400      */
1401     if (!err) {
1402         soln = snewn(circuitlen+2, char);
1403         p = soln;
1404         *p++ = 'S';
1405         x = nodes[circuit[0]] / DP1 % w;
1406         y = nodes[circuit[0]] / DP1 / w;
1407         for (i = 1; i < circuitlen; i++) {
1408             int x2, y2, dx, dy;
1409             if (nodes[circuit[i]] % DP1 != DIRECTIONS)
1410                 continue;
1411             x2 = nodes[circuit[i]] / DP1 % w;
1412             y2 = nodes[circuit[i]] / DP1 / w;
1413             dx = (x2 > x ? +1 : x2 < x ? -1 : 0);
1414             dy = (y2 > y ? +1 : y2 < y ? -1 : 0);
1415             for (d = 0; d < DIRECTIONS; d++)
1416                 if (DX(d) == dx && DY(d) == dy) {
1417                     *p++ = '0' + d;
1418                     break;
1419                 }
1420             assert(d < DIRECTIONS);
1421             x = x2;
1422             y = y2;
1423         }
1424         *p++ = '\0';
1425         assert(p - soln < circuitlen+2);
1426     }
1427
1428     sfree(list);
1429     sfree(dist);
1430     sfree(dist2);
1431     sfree(unvisited);
1432     sfree(circuit);
1433     sfree(backedgei);
1434     sfree(backedges);
1435     sfree(edgei);
1436     sfree(edges);
1437     sfree(nodeindex);
1438     sfree(nodes);
1439
1440     if (err)
1441         *error = err;
1442
1443     return soln;
1444 }
1445
1446 static int game_can_format_as_text_now(const game_params *params)
1447 {
1448     return TRUE;
1449 }
1450
1451 static char *game_text_format(const game_state *state)
1452 {
1453     int w = state->p.w, h = state->p.h, r, c;
1454     int cw = 4, ch = 2, gw = cw*w + 2, gh = ch * h + 1, len = gw * gh;
1455     char *board = snewn(len + 1, char);
1456
1457     sprintf(board, "%*s+\n", len - 2, "");
1458
1459     for (r = 0; r < h; ++r) {
1460         for (c = 0; c < w; ++c) {
1461             int cell = r*ch*gw + cw*c, center = cell + gw*ch/2 + cw/2;
1462             int i = r*w + c;
1463             switch (state->grid[i]) {
1464             case BLANK: break;
1465             case GEM: board[center] = 'o'; break;
1466             case MINE: board[center] = 'M'; break;
1467             case STOP: board[center-1] = '('; board[center+1] = ')'; break;
1468             case WALL: memset(board + center - 1, 'X', 3);
1469             }
1470
1471             if (r == state->py && c == state->px) {
1472                 if (!state->dead) board[center] = '@';
1473                 else memcpy(board + center - 1, ":-(", 3);
1474             }
1475             board[cell] = '+';
1476             memset(board + cell + 1, '-', cw - 1);
1477             for (i = 1; i < ch; ++i) board[cell + i*gw] = '|';
1478         }
1479         for (c = 0; c < ch; ++c) {
1480             board[(r*ch+c)*gw + gw - 2] = "|+"[!c];
1481             board[(r*ch+c)*gw + gw - 1] = '\n';
1482         }
1483     }
1484     memset(board + len - gw, '-', gw - 2);
1485     for (c = 0; c < w; ++c) board[len - gw + cw*c] = '+';
1486
1487     return board;
1488 }
1489
1490 struct game_ui {
1491     float anim_length;
1492     int flashtype;
1493     int deaths;
1494     int just_made_move;
1495     int just_died;
1496 };
1497
1498 static game_ui *new_ui(const game_state *state)
1499 {
1500     game_ui *ui = snew(game_ui);
1501     ui->anim_length = 0.0F;
1502     ui->flashtype = 0;
1503     ui->deaths = 0;
1504     ui->just_made_move = FALSE;
1505     ui->just_died = FALSE;
1506     return ui;
1507 }
1508
1509 static void free_ui(game_ui *ui)
1510 {
1511     sfree(ui);
1512 }
1513
1514 static char *encode_ui(const game_ui *ui)
1515 {
1516     char buf[80];
1517     /*
1518      * The deaths counter needs preserving across a serialisation.
1519      */
1520     sprintf(buf, "D%d", ui->deaths);
1521     return dupstr(buf);
1522 }
1523
1524 static void decode_ui(game_ui *ui, const char *encoding)
1525 {
1526     int p = 0;
1527     sscanf(encoding, "D%d%n", &ui->deaths, &p);
1528 }
1529
1530 static void game_changed_state(game_ui *ui, const game_state *oldstate,
1531                                const game_state *newstate)
1532 {
1533     /*
1534      * Increment the deaths counter. We only do this if
1535      * ui->just_made_move is set (redoing a suicide move doesn't
1536      * kill you _again_), and also we only do it if the game wasn't
1537      * already completed (once you're finished, you can play).
1538      */
1539     if (!oldstate->dead && newstate->dead && ui->just_made_move &&
1540         oldstate->gems) {
1541         ui->deaths++;
1542         ui->just_died = TRUE;
1543     } else {
1544         ui->just_died = FALSE;
1545     }
1546     ui->just_made_move = FALSE;
1547 }
1548
1549 struct game_drawstate {
1550     game_params p;
1551     int tilesize;
1552     int started;
1553     unsigned short *grid;
1554     blitter *player_background;
1555     int player_bg_saved, pbgx, pbgy;
1556 };
1557
1558 #define PREFERRED_TILESIZE 32
1559 #define TILESIZE (ds->tilesize)
1560 #ifdef SMALL_SCREEN
1561 #define BORDER    (TILESIZE / 4)
1562 #else
1563 #define BORDER    (TILESIZE)
1564 #endif
1565 #define HIGHLIGHT_WIDTH (TILESIZE / 10)
1566 #define COORD(x)  ( (x) * TILESIZE + BORDER )
1567 #define FROMCOORD(x)  ( ((x) - BORDER + TILESIZE) / TILESIZE - 1 )
1568
1569 static char *interpret_move(const game_state *state, game_ui *ui,
1570                             const game_drawstate *ds,
1571                             int x, int y, int button)
1572 {
1573     int w = state->p.w, h = state->p.h /*, wh = w*h */;
1574     int dir;
1575     char buf[80];
1576
1577     dir = -1;
1578
1579     if (button == LEFT_BUTTON) {
1580         /*
1581          * Mouse-clicking near the target point (or, more
1582          * accurately, in the appropriate octant) is an alternative
1583          * way to input moves.
1584          */
1585
1586         if (FROMCOORD(x) != state->px || FROMCOORD(y) != state->py) {
1587             int dx, dy;
1588             float angle;
1589
1590             dx = FROMCOORD(x) - state->px;
1591             dy = FROMCOORD(y) - state->py;
1592             /* I pass dx,dy rather than dy,dx so that the octants
1593              * end up the right way round. */
1594             angle = atan2(dx, -dy);
1595
1596             angle = (angle + (PI/8)) / (PI/4);
1597             assert(angle > -16.0F);
1598             dir = (int)(angle + 16.0F) & 7;
1599         }
1600     } else if (button == CURSOR_UP || button == (MOD_NUM_KEYPAD | '8'))
1601         dir = 0;
1602     else if (button == CURSOR_DOWN || button == (MOD_NUM_KEYPAD | '2'))
1603         dir = 4;
1604     else if (button == CURSOR_LEFT || button == (MOD_NUM_KEYPAD | '4'))
1605         dir = 6;
1606     else if (button == CURSOR_RIGHT || button == (MOD_NUM_KEYPAD | '6'))
1607         dir = 2;
1608     else if (button == (MOD_NUM_KEYPAD | '7'))
1609         dir = 7;
1610     else if (button == (MOD_NUM_KEYPAD | '1'))
1611         dir = 5;
1612     else if (button == (MOD_NUM_KEYPAD | '9'))
1613         dir = 1;
1614     else if (button == (MOD_NUM_KEYPAD | '3'))
1615         dir = 3;
1616     else if (IS_CURSOR_SELECT(button) &&
1617              state->soln && state->solnpos < state->soln->len)
1618         dir = state->soln->list[state->solnpos];
1619
1620     if (dir < 0)
1621         return NULL;
1622
1623     /*
1624      * Reject the move if we can't make it at all due to a wall
1625      * being in the way.
1626      */
1627     if (AT(w, h, state->grid, state->px+DX(dir), state->py+DY(dir)) == WALL)
1628         return NULL;
1629
1630     /*
1631      * Reject the move if we're dead!
1632      */
1633     if (state->dead)
1634         return NULL;
1635
1636     /*
1637      * Otherwise, we can make the move. All we need to specify is
1638      * the direction.
1639      */
1640     ui->just_made_move = TRUE;
1641     sprintf(buf, "%d", dir);
1642     return dupstr(buf);
1643 }
1644
1645 static void install_new_solution(game_state *ret, const char *move)
1646 {
1647     int i;
1648     soln *sol;
1649     assert (*move == 'S');
1650     ++move;
1651
1652     sol = snew(soln);
1653     sol->len = strlen(move);
1654     sol->list = snewn(sol->len, unsigned char);
1655     for (i = 0; i < sol->len; ++i) sol->list[i] = move[i] - '0';
1656
1657     if (ret->soln && --ret->soln->refcount == 0) {
1658         sfree(ret->soln->list);
1659         sfree(ret->soln);
1660     }
1661
1662     ret->soln = sol;
1663     sol->refcount = 1;
1664
1665     ret->cheated = TRUE;
1666     ret->solnpos = 0;
1667 }
1668
1669 static void discard_solution(game_state *ret)
1670 {
1671     --ret->soln->refcount;
1672     assert(ret->soln->refcount > 0); /* ret has a soln-pointing dup */
1673     ret->soln = NULL;
1674     ret->solnpos = 0;
1675 }
1676
1677 static game_state *execute_move(const game_state *state, const char *move)
1678 {
1679     int w = state->p.w, h = state->p.h /*, wh = w*h */;
1680     int dir;
1681     game_state *ret;
1682
1683     if (*move == 'S') {
1684         /*
1685          * This is a solve move, so we don't actually _change_ the
1686          * grid but merely set up a stored solution path.
1687          */
1688         ret = dup_game(state);
1689         install_new_solution(ret, move);
1690         return ret;
1691     }
1692
1693     dir = atoi(move);
1694     if (dir < 0 || dir >= DIRECTIONS)
1695         return NULL;                   /* huh? */
1696
1697     if (state->dead)
1698         return NULL;
1699
1700     if (AT(w, h, state->grid, state->px+DX(dir), state->py+DY(dir)) == WALL)
1701         return NULL;                   /* wall in the way! */
1702
1703     /*
1704      * Now make the move.
1705      */
1706     ret = dup_game(state);
1707     ret->distance_moved = 0;
1708     while (1) {
1709         ret->px += DX(dir);
1710         ret->py += DY(dir);
1711         ret->distance_moved++;
1712
1713         if (AT(w, h, ret->grid, ret->px, ret->py) == GEM) {
1714             LV_AT(w, h, ret->grid, ret->px, ret->py) = BLANK;
1715             ret->gems--;
1716         }
1717
1718         if (AT(w, h, ret->grid, ret->px, ret->py) == MINE) {
1719             ret->dead = TRUE;
1720             break;
1721         }
1722
1723         if (AT(w, h, ret->grid, ret->px, ret->py) == STOP ||
1724             AT(w, h, ret->grid, ret->px+DX(dir),
1725                ret->py+DY(dir)) == WALL)
1726             break;
1727     }
1728
1729     if (ret->soln) {
1730         if (ret->dead || ret->gems == 0)
1731             discard_solution(ret);
1732         else if (ret->soln->list[ret->solnpos] == dir) {
1733             ++ret->solnpos;
1734             assert(ret->solnpos < ret->soln->len); /* or gems == 0 */
1735             assert(!ret->dead); /* or not a solution */
1736         } else {
1737             const char *error = NULL;
1738             char *soln = solve_game(NULL, ret, NULL, &error);
1739             if (!error) {
1740                 install_new_solution(ret, soln);
1741                 sfree(soln);
1742             } else discard_solution(ret);
1743         }
1744     }
1745
1746     return ret;
1747 }
1748
1749 /* ----------------------------------------------------------------------
1750  * Drawing routines.
1751  */
1752
1753 static void game_compute_size(const game_params *params, int tilesize,
1754                               int *x, int *y)
1755 {
1756     /* Ick: fake up `ds->tilesize' for macro expansion purposes */
1757     struct { int tilesize; } ads, *ds = &ads;
1758     ads.tilesize = tilesize;
1759
1760     *x = 2 * BORDER + 1 + params->w * TILESIZE;
1761     *y = 2 * BORDER + 1 + params->h * TILESIZE;
1762 }
1763
1764 static void game_set_size(drawing *dr, game_drawstate *ds,
1765                           const game_params *params, int tilesize)
1766 {
1767     ds->tilesize = tilesize;
1768
1769     assert(!ds->player_background);    /* set_size is never called twice */
1770     assert(!ds->player_bg_saved);
1771
1772     ds->player_background = blitter_new(dr, TILESIZE, TILESIZE);
1773 }
1774
1775 static float *game_colours(frontend *fe, int *ncolours)
1776 {
1777     float *ret = snewn(3 * NCOLOURS, float);
1778     int i;
1779
1780     game_mkhighlight(fe, ret, COL_BACKGROUND, COL_HIGHLIGHT, COL_LOWLIGHT);
1781
1782     ret[COL_OUTLINE * 3 + 0] = 0.0F;
1783     ret[COL_OUTLINE * 3 + 1] = 0.0F;
1784     ret[COL_OUTLINE * 3 + 2] = 0.0F;
1785
1786     ret[COL_PLAYER * 3 + 0] = 0.0F;
1787     ret[COL_PLAYER * 3 + 1] = 1.0F;
1788     ret[COL_PLAYER * 3 + 2] = 0.0F;
1789
1790     ret[COL_DEAD_PLAYER * 3 + 0] = 1.0F;
1791     ret[COL_DEAD_PLAYER * 3 + 1] = 0.0F;
1792     ret[COL_DEAD_PLAYER * 3 + 2] = 0.0F;
1793
1794     ret[COL_MINE * 3 + 0] = 0.0F;
1795     ret[COL_MINE * 3 + 1] = 0.0F;
1796     ret[COL_MINE * 3 + 2] = 0.0F;
1797
1798     ret[COL_GEM * 3 + 0] = 0.6F;
1799     ret[COL_GEM * 3 + 1] = 1.0F;
1800     ret[COL_GEM * 3 + 2] = 1.0F;
1801
1802     for (i = 0; i < 3; i++) {
1803         ret[COL_WALL * 3 + i] = (3 * ret[COL_BACKGROUND * 3 + i] +
1804                                  1 * ret[COL_HIGHLIGHT * 3 + i]) / 4;
1805     }
1806
1807     ret[COL_HINT * 3 + 0] = 1.0F;
1808     ret[COL_HINT * 3 + 1] = 1.0F;
1809     ret[COL_HINT * 3 + 2] = 0.0F;
1810
1811     *ncolours = NCOLOURS;
1812     return ret;
1813 }
1814
1815 static game_drawstate *game_new_drawstate(drawing *dr, const game_state *state)
1816 {
1817     int w = state->p.w, h = state->p.h, wh = w*h;
1818     struct game_drawstate *ds = snew(struct game_drawstate);
1819     int i;
1820
1821     ds->tilesize = 0;
1822
1823     /* We can't allocate the blitter rectangle for the player background
1824      * until we know what size to make it. */
1825     ds->player_background = NULL;
1826     ds->player_bg_saved = FALSE;
1827     ds->pbgx = ds->pbgy = -1;
1828
1829     ds->p = state->p;                  /* structure copy */
1830     ds->started = FALSE;
1831     ds->grid = snewn(wh, unsigned short);
1832     for (i = 0; i < wh; i++)
1833         ds->grid[i] = UNDRAWN;
1834
1835     return ds;
1836 }
1837
1838 static void game_free_drawstate(drawing *dr, game_drawstate *ds)
1839 {
1840     if (ds->player_background)
1841         blitter_free(dr, ds->player_background);
1842     sfree(ds->grid);
1843     sfree(ds);
1844 }
1845
1846 static void draw_player(drawing *dr, game_drawstate *ds, int x, int y,
1847                         int dead, int hintdir)
1848 {
1849     if (dead) {
1850         int coords[DIRECTIONS*4];
1851         int d;
1852
1853         for (d = 0; d < DIRECTIONS; d++) {
1854             float x1, y1, x2, y2, x3, y3, len;
1855
1856             x1 = DX(d);
1857             y1 = DY(d);
1858             len = sqrt(x1*x1+y1*y1); x1 /= len; y1 /= len;
1859
1860             x3 = DX(d+1);
1861             y3 = DY(d+1);
1862             len = sqrt(x3*x3+y3*y3); x3 /= len; y3 /= len;
1863
1864             x2 = (x1+x3) / 4;
1865             y2 = (y1+y3) / 4;
1866
1867             coords[d*4+0] = x + TILESIZE/2 + (int)((TILESIZE*3/7) * x1);
1868             coords[d*4+1] = y + TILESIZE/2 + (int)((TILESIZE*3/7) * y1);
1869             coords[d*4+2] = x + TILESIZE/2 + (int)((TILESIZE*3/7) * x2);
1870             coords[d*4+3] = y + TILESIZE/2 + (int)((TILESIZE*3/7) * y2);
1871         }
1872         draw_polygon(dr, coords, DIRECTIONS*2, COL_DEAD_PLAYER, COL_OUTLINE);
1873     } else {
1874         draw_circle(dr, x + TILESIZE/2, y + TILESIZE/2,
1875                     TILESIZE/3, COL_PLAYER, COL_OUTLINE);
1876     }
1877
1878     if (!dead && hintdir >= 0) {
1879         float scale = (DX(hintdir) && DY(hintdir) ? 0.8F : 1.0F);
1880         int ax = (TILESIZE*2/5) * scale * DX(hintdir);
1881         int ay = (TILESIZE*2/5) * scale * DY(hintdir);
1882         int px = -ay, py = ax;
1883         int ox = x + TILESIZE/2, oy = y + TILESIZE/2;
1884         int coords[14], *c;
1885
1886         c = coords;
1887         *c++ = ox + px/9;
1888         *c++ = oy + py/9;
1889         *c++ = ox + px/9 + ax*2/3;
1890         *c++ = oy + py/9 + ay*2/3;
1891         *c++ = ox + px/3 + ax*2/3;
1892         *c++ = oy + py/3 + ay*2/3;
1893         *c++ = ox + ax;
1894         *c++ = oy + ay;
1895         *c++ = ox - px/3 + ax*2/3;
1896         *c++ = oy - py/3 + ay*2/3;
1897         *c++ = ox - px/9 + ax*2/3;
1898         *c++ = oy - py/9 + ay*2/3;
1899         *c++ = ox - px/9;
1900         *c++ = oy - py/9;
1901         draw_polygon(dr, coords, 7, COL_HINT, COL_OUTLINE);
1902     }
1903
1904     draw_update(dr, x, y, TILESIZE, TILESIZE);
1905 }
1906
1907 #define FLASH_DEAD 0x100
1908 #define FLASH_WIN  0x200
1909 #define FLASH_MASK 0x300
1910
1911 static void draw_tile(drawing *dr, game_drawstate *ds, int x, int y, int v)
1912 {
1913     int tx = COORD(x), ty = COORD(y);
1914     int bg = (v & FLASH_DEAD ? COL_DEAD_PLAYER :
1915               v & FLASH_WIN ? COL_HIGHLIGHT : COL_BACKGROUND);
1916
1917     v &= ~FLASH_MASK;
1918
1919     clip(dr, tx+1, ty+1, TILESIZE-1, TILESIZE-1);
1920     draw_rect(dr, tx+1, ty+1, TILESIZE-1, TILESIZE-1, bg);
1921
1922     if (v == WALL) {
1923         int coords[6];
1924
1925         coords[0] = tx + TILESIZE;
1926         coords[1] = ty + TILESIZE;
1927         coords[2] = tx + TILESIZE;
1928         coords[3] = ty + 1;
1929         coords[4] = tx + 1;
1930         coords[5] = ty + TILESIZE;
1931         draw_polygon(dr, coords, 3, COL_LOWLIGHT, COL_LOWLIGHT);
1932
1933         coords[0] = tx + 1;
1934         coords[1] = ty + 1;
1935         draw_polygon(dr, coords, 3, COL_HIGHLIGHT, COL_HIGHLIGHT);
1936
1937         draw_rect(dr, tx + 1 + HIGHLIGHT_WIDTH, ty + 1 + HIGHLIGHT_WIDTH,
1938                   TILESIZE - 2*HIGHLIGHT_WIDTH,
1939                   TILESIZE - 2*HIGHLIGHT_WIDTH, COL_WALL);
1940     } else if (v == MINE) {
1941         int cx = tx + TILESIZE / 2;
1942         int cy = ty + TILESIZE / 2;
1943         int r = TILESIZE / 2 - 3;
1944
1945         draw_circle(dr, cx, cy, 5*r/6, COL_MINE, COL_MINE);
1946         draw_rect(dr, cx - r/6, cy - r, 2*(r/6)+1, 2*r+1, COL_MINE);
1947         draw_rect(dr, cx - r, cy - r/6, 2*r+1, 2*(r/6)+1, COL_MINE);
1948         draw_rect(dr, cx-r/3, cy-r/3, r/3, r/4, COL_HIGHLIGHT);
1949     } else if (v == STOP) {
1950         draw_circle(dr, tx + TILESIZE/2, ty + TILESIZE/2,
1951                     TILESIZE*3/7, -1, COL_OUTLINE);
1952         draw_rect(dr, tx + TILESIZE*3/7, ty+1,
1953                   TILESIZE - 2*(TILESIZE*3/7) + 1, TILESIZE-1, bg);
1954         draw_rect(dr, tx+1, ty + TILESIZE*3/7,
1955                   TILESIZE-1, TILESIZE - 2*(TILESIZE*3/7) + 1, bg);
1956     } else if (v == GEM) {
1957         int coords[8];
1958
1959         coords[0] = tx+TILESIZE/2;
1960         coords[1] = ty+TILESIZE/2-TILESIZE*5/14;
1961         coords[2] = tx+TILESIZE/2-TILESIZE*5/14;
1962         coords[3] = ty+TILESIZE/2;
1963         coords[4] = tx+TILESIZE/2;
1964         coords[5] = ty+TILESIZE/2+TILESIZE*5/14;
1965         coords[6] = tx+TILESIZE/2+TILESIZE*5/14;
1966         coords[7] = ty+TILESIZE/2;
1967
1968         draw_polygon(dr, coords, 4, COL_GEM, COL_OUTLINE);
1969     }
1970
1971     unclip(dr);
1972     draw_update(dr, tx, ty, TILESIZE, TILESIZE);
1973 }
1974
1975 #define BASE_ANIM_LENGTH 0.1F
1976 #define FLASH_LENGTH 0.3F
1977
1978 static void game_redraw(drawing *dr, game_drawstate *ds,
1979                         const game_state *oldstate, const game_state *state,
1980                         int dir, const game_ui *ui,
1981                         float animtime, float flashtime)
1982 {
1983     int w = state->p.w, h = state->p.h /*, wh = w*h */;
1984     int x, y;
1985     float ap;
1986     int player_dist;
1987     int flashtype;
1988     int gems, deaths;
1989     char status[256];
1990
1991     if (flashtime &&
1992         !((int)(flashtime * 3 / FLASH_LENGTH) % 2))
1993         flashtype = ui->flashtype;
1994     else
1995         flashtype = 0;
1996
1997     /*
1998      * Erase the player sprite.
1999      */
2000     if (ds->player_bg_saved) {
2001         assert(ds->player_background);
2002         blitter_load(dr, ds->player_background, ds->pbgx, ds->pbgy);
2003         draw_update(dr, ds->pbgx, ds->pbgy, TILESIZE, TILESIZE);
2004         ds->player_bg_saved = FALSE;
2005     }
2006
2007     /*
2008      * Initialise a fresh drawstate.
2009      */
2010     if (!ds->started) {
2011         int wid, ht;
2012
2013         /*
2014          * Blank out the window initially.
2015          */
2016         game_compute_size(&ds->p, TILESIZE, &wid, &ht);
2017         draw_rect(dr, 0, 0, wid, ht, COL_BACKGROUND);
2018         draw_update(dr, 0, 0, wid, ht);
2019
2020         /*
2021          * Draw the grid lines.
2022          */
2023         for (y = 0; y <= h; y++)
2024             draw_line(dr, COORD(0), COORD(y), COORD(w), COORD(y),
2025                       COL_LOWLIGHT);
2026         for (x = 0; x <= w; x++)
2027             draw_line(dr, COORD(x), COORD(0), COORD(x), COORD(h),
2028                       COL_LOWLIGHT);
2029
2030         ds->started = TRUE;
2031     }
2032
2033     /*
2034      * If we're in the process of animating a move, let's start by
2035      * working out how far the player has moved from their _older_
2036      * state.
2037      */
2038     if (oldstate) {
2039         ap = animtime / ui->anim_length;
2040         player_dist = ap * (dir > 0 ? state : oldstate)->distance_moved;
2041     } else {
2042         player_dist = 0;
2043         ap = 0.0F;
2044     }
2045
2046     /*
2047      * Draw the grid contents.
2048      *
2049      * We count the gems as we go round this loop, for the purposes
2050      * of the status bar. Of course we have a gems counter in the
2051      * game_state already, but if we do the counting in this loop
2052      * then it tracks gems being picked up in a sliding move, and
2053      * updates one by one.
2054      */
2055     gems = 0;
2056     for (y = 0; y < h; y++)
2057         for (x = 0; x < w; x++) {
2058             unsigned short v = (unsigned char)state->grid[y*w+x];
2059
2060             /*
2061              * Special case: if the player is in the process of
2062              * moving over a gem, we draw the gem iff they haven't
2063              * gone past it yet.
2064              */
2065             if (oldstate && oldstate->grid[y*w+x] != state->grid[y*w+x]) {
2066                 /*
2067                  * Compute the distance from this square to the
2068                  * original player position.
2069                  */
2070                 int dist = max(abs(x - oldstate->px), abs(y - oldstate->py));
2071
2072                 /*
2073                  * If the player has reached here, use the new grid
2074                  * element. Otherwise use the old one.
2075                  */
2076                 if (player_dist < dist)
2077                     v = oldstate->grid[y*w+x];
2078                 else
2079                     v = state->grid[y*w+x];
2080             }
2081
2082             /*
2083              * Special case: erase the mine the dead player is
2084              * sitting on. Only at the end of the move.
2085              */
2086             if (v == MINE && !oldstate && state->dead &&
2087                 x == state->px && y == state->py)
2088                 v = BLANK;
2089
2090             if (v == GEM)
2091                 gems++;
2092
2093             v |= flashtype;
2094
2095             if (ds->grid[y*w+x] != v) {
2096                 draw_tile(dr, ds, x, y, v);
2097                 ds->grid[y*w+x] = v;
2098             }
2099         }
2100
2101     /*
2102      * Gem counter in the status bar. We replace it with
2103      * `COMPLETED!' when it reaches zero ... or rather, when the
2104      * _current state_'s gem counter is zero. (Thus, `Gems: 0' is
2105      * shown between the collection of the last gem and the
2106      * completion of the move animation that did it.)
2107      */
2108     if (state->dead && (!oldstate || oldstate->dead)) {
2109         sprintf(status, "DEAD!");
2110     } else if (state->gems || (oldstate && oldstate->gems)) {
2111         if (state->cheated)
2112             sprintf(status, "Auto-solver used. ");
2113         else
2114             *status = '\0';
2115         sprintf(status + strlen(status), "Gems: %d", gems);
2116     } else if (state->cheated) {
2117         sprintf(status, "Auto-solved.");
2118     } else {
2119         sprintf(status, "COMPLETED!");
2120     }
2121     /* We subtract one from the visible death counter if we're still
2122      * animating the move at the end of which the death took place. */
2123     deaths = ui->deaths;
2124     if (oldstate && ui->just_died) {
2125         assert(deaths > 0);
2126         deaths--;
2127     }
2128     if (deaths)
2129         sprintf(status + strlen(status), "   Deaths: %d", deaths);
2130     status_bar(dr, status);
2131
2132     /*
2133      * Draw the player sprite.
2134      */
2135     assert(!ds->player_bg_saved);
2136     assert(ds->player_background);
2137     {
2138         int ox, oy, nx, ny;
2139         nx = COORD(state->px);
2140         ny = COORD(state->py);
2141         if (oldstate) {
2142             ox = COORD(oldstate->px);
2143             oy = COORD(oldstate->py);
2144         } else {
2145             ox = nx;
2146             oy = ny;
2147         }
2148         ds->pbgx = ox + ap * (nx - ox);
2149         ds->pbgy = oy + ap * (ny - oy);
2150     }
2151     blitter_save(dr, ds->player_background, ds->pbgx, ds->pbgy);
2152     draw_player(dr, ds, ds->pbgx, ds->pbgy,
2153                 (state->dead && !oldstate),
2154                 (!oldstate && state->soln ?
2155                  state->soln->list[state->solnpos] : -1));
2156     ds->player_bg_saved = TRUE;
2157 }
2158
2159 static float game_anim_length(const game_state *oldstate,
2160                               const game_state *newstate, int dir, game_ui *ui)
2161 {
2162     int dist;
2163     if (dir > 0)
2164         dist = newstate->distance_moved;
2165     else
2166         dist = oldstate->distance_moved;
2167     ui->anim_length = sqrt(dist) * BASE_ANIM_LENGTH;
2168     return ui->anim_length;
2169 }
2170
2171 static float game_flash_length(const game_state *oldstate,
2172                                const game_state *newstate, int dir, game_ui *ui)
2173 {
2174     if (!oldstate->dead && newstate->dead) {
2175         ui->flashtype = FLASH_DEAD;
2176         return FLASH_LENGTH;
2177     } else if (oldstate->gems && !newstate->gems) {
2178         ui->flashtype = FLASH_WIN;
2179         return FLASH_LENGTH;
2180     }
2181     return 0.0F;
2182 }
2183
2184 static int game_status(const game_state *state)
2185 {
2186     /*
2187      * We never report the game as lost, on the grounds that if the
2188      * player has died they're quite likely to want to undo and carry
2189      * on.
2190      */
2191     return state->gems == 0 ? +1 : 0;
2192 }
2193
2194 static int game_timing_state(const game_state *state, game_ui *ui)
2195 {
2196     return TRUE;
2197 }
2198
2199 static void game_print_size(const game_params *params, float *x, float *y)
2200 {
2201 }
2202
2203 static void game_print(drawing *dr, const game_state *state, int tilesize)
2204 {
2205 }
2206
2207 #ifdef COMBINED
2208 #define thegame inertia
2209 #endif
2210
2211 const struct game thegame = {
2212     "Inertia", "games.inertia", "inertia",
2213     default_params,
2214     game_fetch_preset, NULL,
2215     decode_params,
2216     encode_params,
2217     free_params,
2218     dup_params,
2219     TRUE, game_configure, custom_params,
2220     validate_params,
2221     new_game_desc,
2222     validate_desc,
2223     new_game,
2224     dup_game,
2225     free_game,
2226     TRUE, solve_game,
2227     TRUE, game_can_format_as_text_now, game_text_format,
2228     new_ui,
2229     free_ui,
2230     encode_ui,
2231     decode_ui,
2232     game_changed_state,
2233     interpret_move,
2234     execute_move,
2235     PREFERRED_TILESIZE, game_compute_size, game_set_size,
2236     game_colours,
2237     game_new_drawstate,
2238     game_free_drawstate,
2239     game_redraw,
2240     game_anim_length,
2241     game_flash_length,
2242     game_status,
2243     FALSE, FALSE, game_print_size, game_print,
2244     TRUE,                              /* wants_statusbar */
2245     FALSE, game_timing_state,
2246     0,                                 /* flags */
2247 };