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