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