unfinished/sokoban.c

   1 /*
   2  * sokoban.c: An implementation of the well-known Sokoban barrel-
   3  * pushing game. Random generation is too simplistic to be
   4  * credible, but the rest of the gameplay works well enough to use
   5  * it with hand-written level descriptions.
   6  */
   7
   8 /*
   9  * TODO:
  10  *
  11  *  - I think it would be better to ditch the `prev' array, and
  12  *    instead make the `dist' array strictly monotonic (by having
  13  *    each distance be something like I*A+S, where A is the grid
  14  *    area, I the number of INITIAL squares trampled on, and S the
  15  *    number of harmless spaces moved through). This would permit
  16  *    the path-tracing when a pull is actually made to choose
  17  *    randomly from all the possible shortest routes, which would
  18  *    be superior in terms of eliminating directional bias.
  19  *     + So when tracing the path back to the current px,py, we
  20  *       look at all four adjacent squares, find the minimum
  21  *       distance, check that it's _strictly smaller_ than that of
  22  *       the current square, and restrict our choice to precisely
  23  *       those squares with that minimum distance.
  24  *     + The other place `prev' is currently used is in the check
  25  *       for consistency of a pull. We would have to replace the
  26  *       check for whether prev[ny*w+nx]==oy*w+ox with a check that
  27  *       made sure there was at least one adjacent square with a
  28  *       smaller distance which _wasn't_ oy*w+ox. Then when we did
  29  *       the path-tracing we'd also have to take this special case
  30  *       into account.
  31  *
  32  *  - More discriminating choice of pull. (Snigger.)
  33  *     + favour putting targets in clumps
  34  *     + try to shoot for a reasonably consistent number of barrels
  35  *       (adjust willingness to generate a new barrel depending on
  36  *       how many are already present)
  37  *     + adjust willingness to break new ground depending on how
  38  *       much is already broken
  39  *
  40  *  - generation time parameters:
  41  *     + enable NetHack mode (and find a better place for the hole)
  42  *     + decide how many of the remaining Is should be walls
  43  *
  44  *  - at the end of generation, randomly position the starting
  45  *    player coordinates, probably by (somehow) reusing the same
  46  *    bfs currently inside the loop.
  47  *
  48  *  - possible backtracking?
  49  *
  50  *  - IWBNI we could spot completely unreachable bits of level at
  51  *    the outside, and not bother drawing grid lines for them. The
  52  *    NH levels currently look a bit weird with grid lines on the
  53  *    outside of the boundary.
  54  */
  55
  56 #include <stdio.h>
  57 #include <stdlib.h>
  58 #include <string.h>
  59 #include <assert.h>
  60 #include <ctype.h>
  61 #include <math.h>
  62
  63 #include "puzzles.h"
  64
  65 /*
  66  * Various subsets of these constants are used during game
  67  * generation, game play, game IDs and the game_drawstate.
  68  */
  69 #define INITIAL      'i'               /* used only in game generation */
  70 #define SPACE        's'
  71 #define WALL         'w'
  72 #define PIT          'p'
  73 #define DEEP_PIT     'd'
  74 #define TARGET       't'
  75 #define BARREL       'b'
  76 #define BARRELTARGET 'f'               /* target is 'f'illed */
  77 #define PLAYER       'u'               /* yo'u'; used in game IDs */
  78 #define PLAYERTARGET 'v'               /* bad letter: v is to u as t is to s */
  79 #define INVALID      '!'               /* used in drawstate to force redraw */
  80 /*
  81  * We also support the use of any capital letter as a barrel, which
  82  * will be displayed with that letter as a label. (This facilitates
  83  * people distributing annotated game IDs for particular Sokoban
  84  * levels, so they can accompany them with verbal instructions
  85  * about pushing particular barrels in particular ways.) Therefore,
  86  * to find out whether something is a barrel, we need a test
  87  * function which does a bit more than just comparing to BARREL.
  88  *
  89  * When resting on target squares, capital-letter barrels are
  90  * replaced with their control-character value (A -> ^A).
  91  */
  92 #define IS_PLAYER(c) ( (c)==PLAYER || (c)==PLAYERTARGET )
  93 #define IS_BARREL(c) ( (c)==BARREL || (c)==BARRELTARGET || \
  94                        ((c)>='A' && (c)<='Z') || ((c)>=1 && (c)<=26) )
  95 #define IS_ON_TARGET(c) ( (c)==TARGET || (c)==BARRELTARGET || \
  96                           (c)==PLAYERTARGET || ((c)>=1 && (c)<=26) )
  97 #define TARGETISE(b) ( (b)==BARREL ? BARRELTARGET : (b)-('A'-1) )
  98 #define DETARGETISE(b) ( (b)==BARRELTARGET ? BARREL : (b)+('A'-1) )
  99 #define BARREL_LABEL(b) ( (b)>='A'&&(b)<='Z' ? (b) : \
 100                           (b)>=1 && (b)<=26 ? (b)+('A'-1) : 0 )
 101
 102 #define DX(d) (d == 0 ? -1 : d == 2 ? +1 : 0)
 103 #define DY(d) (d == 1 ? -1 : d == 3 ? +1 : 0)
 104
 105 #define FLASH_LENGTH 0.3F
 106
 107 enum {
 108     COL_BACKGROUND,
 109     COL_TARGET,
 110     COL_PIT,
 111     COL_DEEP_PIT,
 112     COL_BARREL,
 113     COL_PLAYER,
 114     COL_TEXT,
 115     COL_GRID,
 116     COL_OUTLINE,
 117     COL_HIGHLIGHT,
 118     COL_LOWLIGHT,
 119     COL_WALL,
 120     NCOLOURS
 121 };
 122
 123 struct game_params {
 124     int w, h;
 125     /*
 126      * FIXME: a parameter involving degree of filling in?
 127      */
 128 };
 129
 130 struct game_state {
 131     game_params p;
 132     unsigned char *grid;
 133     int px, py;
 134     int completed;
 135 };
 136
 137 static game_params *default_params(void)
 138 {
 139     game_params *ret = snew(game_params);
 140
 141     ret->w = 12;
 142     ret->h = 10;
 143
 144     return ret;
 145 }
 146
 147 static void free_params(game_params *params)
 148 {
 149     sfree(params);
 150 }
 151
 152 static game_params *dup_params(game_params *params)
 153 {
 154     game_params *ret = snew(game_params);
 155     *ret = *params;                    /* structure copy */
 156     return ret;
 157 }
 158
 159 static const struct game_params sokoban_presets[] = {
 160     { 12, 10 },
 161     { 16, 12 },
 162     { 20, 16 },
 163 };
 164
 165 static int game_fetch_preset(int i, char **name, game_params **params)
 166 {
 167     game_params p, *ret;
 168     char *retname;
 169     char namebuf[80];
 170
 171     if (i < 0 || i >= lenof(sokoban_presets))
 172         return FALSE;
 173
 174     p = sokoban_presets[i];
 175     ret = dup_params(&p);
 176     sprintf(namebuf, "%dx%d", ret->w, ret->h);
 177     retname = dupstr(namebuf);
 178
 179     *params = ret;
 180     *name = retname;
 181     return TRUE;
 182 }
 183
 184 static void decode_params(game_params *params, char const *string)
 185 {
 186     params->w = params->h = atoi(string);
 187     while (*string && isdigit((unsigned char)*string)) string++;
 188     if (*string == 'x') {
 189         string++;
 190         params->h = atoi(string);
 191     }
 192 }
 193
 194 static char *encode_params(game_params *params, int full)
 195 {
 196     char data[256];
 197
 198     sprintf(data, "%dx%d", params->w, params->h);
 199
 200     return dupstr(data);
 201 }
 202
 203 static config_item *game_configure(game_params *params)
 204 {
 205     config_item *ret;
 206     char buf[80];
 207
 208     ret = snewn(3, config_item);
 209
 210     ret[0].name = "Width";
 211     ret[0].type = C_STRING;
 212     sprintf(buf, "%d", params->w);
 213     ret[0].sval = dupstr(buf);
 214     ret[0].ival = 0;
 215
 216     ret[1].name = "Height";
 217     ret[1].type = C_STRING;
 218     sprintf(buf, "%d", params->h);
 219     ret[1].sval = dupstr(buf);
 220     ret[1].ival = 0;
 221
 222     ret[2].name = NULL;
 223     ret[2].type = C_END;
 224     ret[2].sval = NULL;
 225     ret[2].ival = 0;
 226
 227     return ret;
 228 }
 229
 230 static game_params *custom_params(config_item *cfg)
 231 {
 232     game_params *ret = snew(game_params);
 233
 234     ret->w = atoi(cfg[0].sval);
 235     ret->h = atoi(cfg[1].sval);
 236
 237     return ret;
 238 }
 239
 240 static char *validate_params(game_params *params, int full)
 241 {
 242     if (params->w < 4 || params->h < 4)
 243         return "Width and height must both be at least 4";
 244
 245     return NULL;
 246 }
 247
 248 /* ----------------------------------------------------------------------
 249  * Game generation mechanism.
 250  *
 251  * To generate a Sokoban level, we begin with a completely blank
 252  * grid and make valid inverse moves. Grid squares can be in a
 253  * number of states. The states are:
 254  *
 255  *  - INITIAL: this square has not as yet been touched by any
 256  *    inverse move, which essentially means we haven't decided what
 257  *    it is yet.
 258  *
 259  *  - SPACE: this square is a space.
 260  *
 261  *  - TARGET: this square is a space which is also the target for a
 262  *    barrel.
 263  *
 264  *  - BARREL: this square contains a barrel.
 265  *
 266  *  - BARRELTARGET: this square contains a barrel _on_ a target.
 267  *
 268  *  - WALL: this square is a wall.
 269  *
 270  *  - PLAYER: this square contains the player.
 271  *
 272  *  - PLAYERTARGET: this square contains the player on a target.
 273  *
 274  * We begin with every square of the in state INITIAL, apart from a
 275  * solid ring of WALLs around the edge. We randomly position the
 276  * PLAYER somewhere. Thereafter our valid moves are:
 277  *
 278  *  - to move the PLAYER in one direction _pulling_ a barrel after
 279  *    us. For this to work, we must have SPACE or INITIAL in the
 280  *    direction we're moving, and BARREL or BARRELTARGET in the
 281  *    direction we're moving away from. We leave SPACE or TARGET
 282  *    respectively in the vacated square.
 283  *
 284  *  - to create a new barrel by transforming an INITIAL square into
 285  *    BARRELTARGET.
 286  *
 287  *  - to move the PLAYER freely through SPACE and TARGET squares,
 288  *    leaving SPACE or TARGET where it started.
 289  *
 290  *  - to move the player through INITIAL squares, carving a tunnel
 291  *    of SPACEs as it goes.
 292  *
 293  * We try to avoid destroying INITIAL squares wherever possible (if
 294  * there's a path to where we want to be using only SPACE, then we
 295  * should always use that). At the end of generation, every square
 296  * still in state INITIAL is one which was not required at any
 297  * point during generation, which means we can randomly choose
 298  * whether to make it SPACE or WALL.
 299  *
 300  * It's unclear as yet what the right strategy for wall placement
 301  * should be. Too few WALLs will yield many alternative solutions
 302  * to the puzzle, whereas too many might rule out so many
 303  * possibilities that the intended solution becomes obvious.
 304  */
 305
 306 static void sokoban_generate(int w, int h, unsigned char *grid, int moves,
 307                              int nethack, random_state *rs)
 308 {
 309     struct pull {
 310         int ox, oy, nx, ny, score;
 311     };
 312
 313     struct pull *pulls;
 314     int *dist, *prev, *heap;
 315     int x, y, px, py, i, j, d, heapsize, npulls;
 316
 317     pulls = snewn(w * h * 4, struct pull);
 318     dist = snewn(w * h, int);
 319     prev = snewn(w * h, int);
 320     heap = snewn(w * h, int);
 321
 322     /*
 323      * Configure the initial grid.
 324      */
 325     for (y = 0; y < h; y++)
 326         for (x = 0; x < w; x++)
 327             grid[y*w+x] = (x == 0 || y == 0 || x == w-1 || y == h-1 ?
 328                            WALL : INITIAL);
 329     if (nethack)
 330         grid[1] = DEEP_PIT;
 331
 332     /*
 333      * Place the player.
 334      */
 335     i = random_upto(rs, (w-2) * (h-2));
 336     x = 1 + i % (w-2);
 337     y = 1 + i / (w-2);
 338     grid[y*w+x] = SPACE;
 339     px = x;
 340     py = y;
 341
 342     /*
 343      * Now loop around making random inverse Sokoban moves. In this
 344      * loop we aim to make one actual barrel-pull per iteration,
 345      * plus as many free moves as are necessary to get into
 346      * position for that pull.
 347      */
 348     while (moves-- >= 0) {
 349         /*
 350          * First enumerate all the viable barrel-pulls we can
 351          * possibly make, counting two pulls of the same barrel in
 352          * different directions as different. We also include pulls
 353          * we can perform by creating a new barrel. Each pull is
 354          * marked with the amount of violence it would have to do
 355          * to the grid.
 356          */
 357         npulls = 0;
 358         for (y = 0; y < h; y++)
 359             for (x = 0; x < w; x++)
 360                 for (d = 0; d < 4; d++) {
 361                     int dx = DX(d);
 362                     int dy = DY(d);
 363                     int nx = x + dx, ny = y + dy;
 364                     int npx = nx + dx, npy = ny + dy;
 365                     int score = 0;
 366
 367                     /*
 368                      * The candidate move is to put the player at
 369                      * (nx,ny), and move him to (npx,npy), pulling
 370                      * a barrel at (x,y) to (nx,ny). So first we
 371                      * must check that all those squares are within
 372                      * the boundaries of the grid. For this it is
 373                      * sufficient to check npx,npy.
 374                      */
 375                     if (npx < 0 || npx >= w || npy < 0 || npy >= h)
 376                         continue;
 377
 378                     /*
 379                      * (x,y) must either be a barrel, or a square
 380                      * which we can convert into a barrel.
 381                      */
 382                     switch (grid[y*w+x]) {
 383                       case BARREL: case BARRELTARGET:
 384                         break;
 385                       case INITIAL:
 386                         if (nethack)
 387                             continue;
 388                         score += 10 /* new_barrel_score */;
 389                         break;
 390                       case DEEP_PIT:
 391                         if (!nethack)
 392                             continue;
 393                         break;
 394                       default:
 395                         continue;
 396                     }
 397
 398                     /*
 399                      * (nx,ny) must either be a space, or a square
 400                      * which we can convert into a space.
 401                      */
 402                     switch (grid[ny*w+nx]) {
 403                       case SPACE: case TARGET:
 404                         break;
 405                       case INITIAL:
 406                         score += 3 /* new_space_score */;
 407                         break;
 408                       default:
 409                         continue;
 410                     }
 411
 412                     /*
 413                      * (npx,npy) must also either be a space, or a
 414                      * square which we can convert into a space.
 415                      */
 416                     switch (grid[npy*w+npx]) {
 417                       case SPACE: case TARGET:
 418                         break;
 419                       case INITIAL:
 420                         score += 3 /* new_space_score */;
 421                         break;
 422                       default:
 423                         continue;
 424                     }
 425
 426                     /*
 427                      * That's sufficient to tag this as a possible
 428                      * pull right now. We still don't know if we
 429                      * can reach the required player position, but
 430                      * that's a job for the subsequent BFS phase to
 431                      * tell us.
 432                      */
 433                     pulls[npulls].ox = x;
 434                     pulls[npulls].oy = y;
 435                     pulls[npulls].nx = nx;
 436                     pulls[npulls].ny = ny;
 437                     pulls[npulls].score = score;
 438 #ifdef GENERATION_DIAGNOSTICS
 439                     printf("found potential pull: (%d,%d)-(%d,%d) cost %d\n",
 440                            pulls[npulls].ox, pulls[npulls].oy,
 441                            pulls[npulls].nx, pulls[npulls].ny,
 442                            pulls[npulls].score);
 443 #endif
 444                     npulls++;
 445                 }
 446 #ifdef GENERATION_DIAGNOSTICS
 447         printf("found %d potential pulls\n", npulls);
 448 #endif
 449
 450         /*
 451          * If there are no pulls available at all, we give up.
 452          *
 453          * (FIXME: or perhaps backtrack?)
 454          */
 455         if (npulls == 0)
 456             break;
 457
 458         /*
 459          * Now we do a BFS from our current position, to find all
 460          * the squares we can get the player into.
 461          *
 462          * This BFS is unusually tricky. We want to give a positive
 463          * distance only to squares which we have to carve through
 464          * INITIALs to get to, which means we can't just stick
 465          * every square we reach on the end of our to-do list.
 466          * Instead, we must maintain our list as a proper priority
 467          * queue.
 468          */
 469         for (i = 0; i < w*h; i++)
 470             dist[i] = prev[i] = -1;
 471
 472         heap[0] = py*w+px;
 473         heapsize = 1;
 474         dist[py*w+px] = 0;
 475
 476 #define PARENT(n) ( ((n)-1)/2 )
 477 #define LCHILD(n) ( 2*(n)+1 )
 478 #define RCHILD(n) ( 2*(n)+2 )
 479 #define SWAP(i,j) do { int swaptmp = (i); (i) = (j); (j) = swaptmp; } while (0)
 480
 481         while (heapsize > 0) {
 482             /*
 483              * Pull the smallest element off the heap: it's at
 484              * position 0. Move the arbitrary element from the very
 485              * end of the heap into position 0.
 486              */
 487             y = heap[0] / w;
 488             x = heap[0] % w;
 489
 490             heapsize--;
 491             heap[0] = heap[heapsize];
 492
 493             /*
 494              * Now repeatedly move that arbitrary element down the
 495              * heap by swapping it with the more suitable of its
 496              * children.
 497              */
 498             i = 0;
 499             while (1) {
 500                 int lc, rc;
 501
 502                 lc = LCHILD(i);
 503                 rc = RCHILD(i);
 504
 505                 if (lc >= heapsize)
 506                     break;             /* we've hit bottom */
 507
 508                 if (rc >= heapsize) {
 509                     /*
 510                      * Special case: there is only one child to
 511                      * check.
 512                      */
 513                     if (dist[heap[i]] > dist[heap[lc]])
 514                         SWAP(heap[i], heap[lc]);
 515
 516                     /* _Now_ we've hit bottom. */
 517                     break;
 518                 } else {
 519                     /*
 520                      * The common case: there are two children and
 521                      * we must check them both.
 522                      */
 523                     if (dist[heap[i]] > dist[heap[lc]] ||
 524                         dist[heap[i]] > dist[heap[rc]]) {
 525                         /*
 526                          * Pick the more appropriate child to swap with
 527                          * (i.e. the one which would want to be the
 528                          * parent if one were above the other - as one
 529                          * is about to be).
 530                          */
 531                         if (dist[heap[lc]] > dist[heap[rc]]) {
 532                             SWAP(heap[i], heap[rc]);
 533                             i = rc;
 534                         } else {
 535                             SWAP(heap[i], heap[lc]);
 536                             i = lc;
 537                         }
 538                     } else {
 539                         /* This element is in the right place; we're done. */
 540                         break;
 541                     }
 542                 }
 543             }
 544
 545             /*
 546              * OK, that's given us (x,y) for this phase of the
 547              * search. Now try all directions from here.
 548              */
 549
 550             for (d = 0; d < 4; d++) {
 551                 int dx = DX(d);
 552                 int dy = DY(d);
 553                 int nx = x + dx, ny = y + dy;
 554                 if (nx < 0 || nx >= w || ny < 0 || ny >= h)
 555                     continue;
 556                 if (grid[ny*w+nx] != SPACE && grid[ny*w+nx] != TARGET &&
 557                     grid[ny*w+nx] != INITIAL)
 558                     continue;
 559                 if (dist[ny*w+nx] == -1) {
 560                     dist[ny*w+nx] = dist[y*w+x] + (grid[ny*w+nx] == INITIAL);
 561                     prev[ny*w+nx] = y*w+x;
 562
 563                     /*
 564                      * Now insert ny*w+nx at the end of the heap,
 565                      * and move it down to its appropriate resting
 566                      * place.
 567                      */
 568                     i = heapsize;
 569                     heap[heapsize++] = ny*w+nx;
 570
 571                     /*
 572                      * Swap element n with its parent repeatedly to
 573                      * preserve the heap property.
 574                      */
 575
 576                     while (i > 0) {
 577                         int p = PARENT(i);
 578
 579                         if (dist[heap[p]] > dist[heap[i]]) {
 580                             SWAP(heap[p], heap[i]);
 581                             i = p;
 582                         } else
 583                             break;
 584                     }
 585                 }
 586             }
 587         }
 588
 589 #undef PARENT
 590 #undef LCHILD
 591 #undef RCHILD
 592 #undef SWAP
 593
 594 #ifdef GENERATION_DIAGNOSTICS
 595         printf("distance map:\n");
 596         for (i = 0; i < h; i++) {
 597             for (j = 0; j < w; j++) {
 598                 int d = dist[i*w+j];
 599                 int c;
 600                 if (d < 0)
 601                     c = '#';
 602                 else if (d >= 36)
 603                     c = '!';
 604                 else if (d >= 10)
 605                     c = 'A' - 10 + d;
 606                 else
 607                     c = '0' + d;
 608                 putchar(c);
 609             }
 610             putchar('\n');
 611         }
 612 #endif
 613
 614         /*
 615          * Now we can go back through the `pulls' array, adjusting
 616          * the score for each pull depending on how hard it is to
 617          * reach its starting point, and also throwing out any
 618          * whose starting points are genuinely unreachable even
 619          * with the possibility of carving through INITIAL squares.
 620          */
 621         for (i = j = 0; i < npulls; i++) {
 622 #ifdef GENERATION_DIAGNOSTICS
 623             printf("potential pull (%d,%d)-(%d,%d)",
 624                    pulls[i].ox, pulls[i].oy,
 625                    pulls[i].nx, pulls[i].ny);
 626 #endif
 627             x = pulls[i].nx;
 628             y = pulls[i].ny;
 629             if (dist[y*w+x] < 0) {
 630 #ifdef GENERATION_DIAGNOSTICS
 631                 printf(" unreachable\n");
 632 #endif
 633                 continue;              /* this pull isn't feasible at all */
 634             } else {
 635                 /*
 636                  * Another nasty special case we have to check is
 637                  * whether the initial barrel location (ox,oy) is
 638                  * on the path used to reach the square. This can
 639                  * occur if that square is in state INITIAL: the
 640                  * pull is initially considered valid on the basis
 641                  * that the INITIAL can become BARRELTARGET, and
 642                  * it's also considered reachable on the basis that
 643                  * INITIAL can be turned into SPACE, but it can't
 644                  * be both at once.
 645                  *
 646                  * Fortunately, if (ox,oy) is on the path at all,
 647                  * it must be only one space from the end, so this
 648                  * is easy to spot and rule out.
 649                  */
 650                 if (prev[y*w+x] == pulls[i].oy*w+pulls[i].ox) {
 651 #ifdef GENERATION_DIAGNOSTICS
 652                     printf(" goes through itself\n");
 653 #endif
 654                     continue;          /* this pull isn't feasible at all */
 655                 }
 656                 pulls[j] = pulls[i];   /* structure copy */
 657                 pulls[j].score += dist[y*w+x] * 3 /* new_space_score */;
 658 #ifdef GENERATION_DIAGNOSTICS
 659                 printf(" reachable at distance %d (cost now %d)\n",
 660                        dist[y*w+x], pulls[j].score);
 661 #endif
 662                 j++;
 663             }
 664         }
 665         npulls = j;
 666
 667         /*
 668          * Again, if there are no pulls available at all, we give
 669          * up.
 670          *
 671          * (FIXME: or perhaps backtrack?)
 672          */
 673         if (npulls == 0)
 674             break;
 675
 676         /*
 677          * Now choose which pull to make. On the one hand we should
 678          * prefer pulls which do less damage to the INITIAL squares
 679          * (thus, ones for which we can already get into position
 680          * via existing SPACEs, and for which the barrel already
 681          * exists and doesn't have to be invented); on the other,
 682          * we want to avoid _always_ preferring such pulls, on the
 683          * grounds that that will lead to levels without very much
 684          * stuff in.
 685          *
 686          * When creating new barrels, we prefer creations which are
 687          * next to existing TARGET squares.
 688          *
 689          * FIXME: for the moment I'll make this very simple indeed.
 690          */
 691         i = random_upto(rs, npulls);
 692
 693         /*
 694          * Actually make the pull, including carving a path to get
 695          * to the site if necessary.
 696          */
 697         x = pulls[i].nx;
 698         y = pulls[i].ny;
 699         while (prev[y*w+x] >= 0) {
 700             int p;
 701
 702             if (grid[y*w+x] == INITIAL)
 703                 grid[y*w+x] = SPACE;
 704
 705             p = prev[y*w+x];
 706             y = p / w;
 707             x = p % w;
 708         }
 709         px = 2*pulls[i].nx - pulls[i].ox;
 710         py = 2*pulls[i].ny - pulls[i].oy;
 711         if (grid[py*w+px] == INITIAL)
 712             grid[py*w+px] = SPACE;
 713         if (grid[pulls[i].ny*w+pulls[i].nx] == TARGET)
 714             grid[pulls[i].ny*w+pulls[i].nx] = BARRELTARGET;
 715         else
 716             grid[pulls[i].ny*w+pulls[i].nx] = BARREL;
 717         if (grid[pulls[i].oy*w+pulls[i].ox] == BARREL)
 718             grid[pulls[i].oy*w+pulls[i].ox] = SPACE;
 719         else if (grid[pulls[i].oy*w+pulls[i].ox] != DEEP_PIT)
 720             grid[pulls[i].oy*w+pulls[i].ox] = TARGET;
 721     }
 722
 723     sfree(heap);
 724     sfree(prev);
 725     sfree(dist);
 726     sfree(pulls);
 727
 728     if (grid[py*w+px] == TARGET)
 729         grid[py*w+px] = PLAYERTARGET;
 730     else
 731         grid[py*w+px] = PLAYER;
 732 }
 733
 734 static char *new_game_desc(game_params *params, random_state *rs,
 735                            char **aux, int interactive)
 736 {
 737     int w = params->w, h = params->h;
 738     char *desc;
 739     int desclen, descpos, descsize, prev, count;
 740     unsigned char *grid;
 741     int i, j;
 742
 743     /*
 744      * FIXME: perhaps some more interesting means of choosing how
 745      * many moves to try?
 746      */
 747     grid = snewn(w*h, unsigned char);
 748     sokoban_generate(w, h, grid, w*h, FALSE, rs);
 749
 750     desclen = descpos = descsize = 0;
 751     desc = NULL;
 752     prev = -1;
 753     count = 0;
 754     for (i = 0; i < w*h; i++) {
 755         if (descsize < desclen + 40) {
 756             descsize = desclen + 100;
 757             desc = sresize(desc, descsize, char);
 758             desc[desclen] = '\0';
 759         }
 760         switch (grid[i]) {
 761           case INITIAL:
 762             j = 'w';                   /* FIXME: make some of these 's'? */
 763             break;
 764           case SPACE:
 765             j = 's';
 766             break;
 767           case WALL:
 768             j = 'w';
 769             break;
 770           case TARGET:
 771             j = 't';
 772             break;
 773           case BARREL:
 774             j = 'b';
 775             break;
 776           case BARRELTARGET:
 777             j = 'f';
 778             break;
 779           case DEEP_PIT:
 780             j = 'd';
 781             break;
 782           case PLAYER:
 783             j = 'u';
 784             break;
 785           case PLAYERTARGET:
 786             j = 'v';
 787             break;
 788           default:
 789             j = '?';
 790             break;
 791         }
 792         assert(j != '?');
 793         if (j != prev) {
 794             desc[desclen++] = j;
 795             descpos = desclen;
 796             prev = j;
 797             count = 1;
 798         } else {
 799             count++;
 800             desclen = descpos + sprintf(desc+descpos, "%d", count);
 801         }
 802     }
 803
 804     sfree(grid);
 805
 806     return desc;
 807 }
 808
 809 static char *validate_desc(game_params *params, char *desc)
 810 {
 811     int w = params->w, h = params->h;
 812     int area = 0;
 813     int nplayers = 0;
 814
 815     while (*desc) {
 816         int c = *desc++;
 817         int n = 1;
 818         if (*desc && isdigit((unsigned char)*desc)) {
 819             n = atoi(desc);
 820             while (*desc && isdigit((unsigned char)*desc)) desc++;
 821         }
 822
 823         area += n;
 824
 825         if (c == PLAYER || c == PLAYERTARGET)
 826             nplayers += n;
 827         else if (c == INITIAL || c == SPACE || c == WALL || c == TARGET ||
 828                  c == PIT || c == DEEP_PIT || IS_BARREL(c))
 829             /* ok */;
 830         else
 831             return "Invalid character in game description";
 832     }
 833
 834     if (area > w*h)
 835         return "Too much data in game description";
 836     if (area < w*h)
 837         return "Too little data in game description";
 838     if (nplayers < 1)
 839         return "No starting player position specified";
 840     if (nplayers > 1)
 841         return "More than one starting player position specified";
 842
 843     return NULL;
 844 }
 845
 846 static game_state *new_game(midend *me, game_params *params, char *desc)
 847 {
 848     int w = params->w, h = params->h;
 849     game_state *state = snew(game_state);
 850     int i;
 851
 852     state->p = *params;                /* structure copy */
 853     state->grid = snewn(w*h, unsigned char);
 854     state->px = state->py = -1;
 855     state->completed = FALSE;
 856
 857     i = 0;
 858
 859     while (*desc) {
 860         int c = *desc++;
 861         int n = 1;
 862         if (*desc && isdigit((unsigned char)*desc)) {
 863             n = atoi(desc);
 864             while (*desc && isdigit((unsigned char)*desc)) desc++;
 865         }
 866
 867         if (c == PLAYER || c == PLAYERTARGET) {
 868             state->py = i / w;
 869             state->px = i % w;
 870             c = IS_ON_TARGET(c) ? TARGET : SPACE;
 871         }
 872
 873         while (n-- > 0)
 874             state->grid[i++] = c;
 875     }
 876
 877     assert(i == w*h);
 878     assert(state->px != -1 && state->py != -1);
 879
 880     return state;
 881 }
 882
 883 static game_state *dup_game(game_state *state)
 884 {
 885     int w = state->p.w, h = state->p.h;
 886     game_state *ret = snew(game_state);
 887
 888     ret->p = state->p;                 /* structure copy */
 889     ret->grid = snewn(w*h, unsigned char);
 890     memcpy(ret->grid, state->grid, w*h);
 891     ret->px = state->px;
 892     ret->py = state->py;
 893     ret->completed = state->completed;
 894
 895     return ret;
 896 }
 897
 898 static void free_game(game_state *state)
 899 {
 900     sfree(state->grid);
 901     sfree(state);
 902 }
 903
 904 static char *solve_game(game_state *state, game_state *currstate,
 905                         char *aux, char **error)
 906 {
 907     return NULL;
 908 }
 909
 910 static char *game_text_format(game_state *state)
 911 {
 912     return NULL;
 913 }
 914
 915 static game_ui *new_ui(game_state *state)
 916 {
 917     return NULL;
 918 }
 919
 920 static void free_ui(game_ui *ui)
 921 {
 922 }
 923
 924 static char *encode_ui(game_ui *ui)
 925 {
 926     return NULL;
 927 }
 928
 929 static void decode_ui(game_ui *ui, char *encoding)
 930 {
 931 }
 932
 933 static void game_changed_state(game_ui *ui, game_state *oldstate,
 934                                game_state *newstate)
 935 {
 936 }
 937
 938 struct game_drawstate {
 939     game_params p;
 940     int tilesize;
 941     int started;
 942     unsigned short *grid;
 943 };
 944
 945 #define PREFERRED_TILESIZE 32
 946 #define TILESIZE (ds->tilesize)
 947 #define BORDER    (TILESIZE)
 948 #define HIGHLIGHT_WIDTH (TILESIZE / 10)
 949 #define COORD(x)  ( (x) * TILESIZE + BORDER )
 950 #define FROMCOORD(x)  ( ((x) - BORDER + TILESIZE) / TILESIZE - 1 )
 951
 952 /*
 953  * I'm going to need to do most of the move-type analysis in both
 954  * interpret_move and execute_move, so I'll abstract it out into a
 955  * subfunction. move_type() returns -1 for an illegal move, 0 for a
 956  * movement, and 1 for a push.
 957  */
 958 int move_type(game_state *state, int dx, int dy)
 959 {
 960     int w = state->p.w, h = state->p.h;
 961     int px = state->px, py = state->py;
 962     int nx, ny, nbx, nby;
 963
 964     assert(dx >= -1 && dx <= +1);
 965     assert(dy >= -1 && dy <= +1);
 966     assert(dx || dy);
 967
 968     nx = px + dx;
 969     ny = py + dy;
 970
 971     /*
 972      * Disallow any move that goes off the grid.
 973      */
 974     if (nx < 0 || nx >= w || ny < 0 || ny >= h)
 975         return -1;
 976
 977     /*
 978      * Examine the target square of the move to see whether it's a
 979      * space, a barrel, or a wall.
 980      */
 981
 982     if (state->grid[ny*w+nx] == WALL ||
 983         state->grid[ny*w+nx] == PIT ||
 984         state->grid[ny*w+nx] == DEEP_PIT)
 985         return -1;                     /* this one's easy; just disallow it */
 986
 987     if (IS_BARREL(state->grid[ny*w+nx])) {
 988         /*
 989          * This is a push move. For a start, that means it must not
 990          * be diagonal.
 991          */
 992         if (dy && dx)
 993             return -1;
 994
 995         /*
 996          * Now find the location of the third square involved in
 997          * the push, and stop if it's off the edge.
 998          */
 999         nbx = nx + dx;
1000         nby = ny + dy;
1001         if (nbx < 0 || nbx >= w || nby < 0 || nby >= h)
1002             return -1;
1003
1004         /*
1005          * That third square must be able to accept a barrel.
1006          */
1007         if (state->grid[nby*w+nbx] == SPACE ||
1008             state->grid[nby*w+nbx] == TARGET ||
1009             state->grid[nby*w+nbx] == PIT ||
1010             state->grid[nby*w+nbx] == DEEP_PIT) {
1011             /*
1012              * The push is valid.
1013              */
1014             return 1;
1015         } else {
1016             return -1;
1017         }
1018     } else {
1019         /*
1020          * This is just an ordinary move. We've already checked the
1021          * target square, so the only thing left to check is that a
1022          * diagonal move has a space on one side to have notionally
1023          * gone through.
1024          */
1025         if (dx && dy &&
1026             state->grid[(py+dy)*w+px] != SPACE &&
1027             state->grid[(py+dy)*w+px] != TARGET &&
1028             state->grid[py*w+(px+dx)] != SPACE &&
1029             state->grid[py*w+(px+dx)] != TARGET)
1030             return -1;
1031
1032         /*
1033          * Otherwise, the move is valid.
1034          */
1035         return 0;
1036     }
1037 }
1038
1039 static char *interpret_move(game_state *state, game_ui *ui, game_drawstate *ds,
1040                             int x, int y, int button)
1041 {
1042     int dx, dy;
1043     char *move;
1044
1045     /*
1046      * Diagonal movement is supported as it is in NetHack: it's
1047      * for movement only (never pushing), and one of the two
1048      * squares adjacent to both the source and destination
1049      * squares must be free to move through. In other words, it
1050      * is only a shorthand for two orthogonal moves and cannot
1051      * change the nature of the actual puzzle game.
1052      */
1053     if (button == CURSOR_UP || button == (MOD_NUM_KEYPAD | '8'))
1054         dx = 0, dy = -1;
1055     else if (button == CURSOR_DOWN || button == (MOD_NUM_KEYPAD | '2'))
1056         dx = 0, dy = +1;
1057     else if (button == CURSOR_LEFT || button == (MOD_NUM_KEYPAD | '4'))
1058         dx = -1, dy = 0;
1059     else if (button == CURSOR_RIGHT || button == (MOD_NUM_KEYPAD | '6'))
1060         dx = +1, dy = 0;
1061     else if (button == (MOD_NUM_KEYPAD | '7'))
1062         dx = -1, dy = -1;
1063     else if (button == (MOD_NUM_KEYPAD | '9'))
1064         dx = +1, dy = -1;
1065     else if (button == (MOD_NUM_KEYPAD | '1'))
1066         dx = -1, dy = +1;
1067     else if (button == (MOD_NUM_KEYPAD | '3'))
1068         dx = +1, dy = +1;
1069     else
1070         return NULL;
1071
1072     if (move_type(state, dx, dy) < 0)
1073         return NULL;
1074
1075     move = snewn(2, char);
1076     move[1] = '\0';
1077     move[0] = '5' - 3*dy + dx;
1078     return move;
1079 }
1080
1081 static game_state *execute_move(game_state *state, char *move)
1082 {
1083     int w = state->p.w, h = state->p.h;
1084     int px = state->px, py = state->py;
1085     int dx, dy, nx, ny, nbx, nby, type, m, i, freebarrels, freetargets;
1086     game_state *ret;
1087
1088     if (*move < '1' || *move == '5' || *move > '9' || move[1])
1089         return NULL;                   /* invalid move string */
1090
1091     m = *move - '0';
1092     dx = (m + 2) % 3 - 1;
1093     dy = 2 - (m + 2) / 3;
1094     type = move_type(state, dx, dy);
1095     if (type < 0)
1096         return NULL;
1097
1098     ret = dup_game(state);
1099
1100     nx = px + dx;
1101     ny = py + dy;
1102     nbx = nx + dx;
1103     nby = ny + dy;
1104
1105     if (type) {
1106         int b;
1107
1108         /*
1109          * Push.
1110          */
1111         b = ret->grid[ny*w+nx];
1112         if (IS_ON_TARGET(b)) {
1113             ret->grid[ny*w+nx] = TARGET;
1114             b = DETARGETISE(b);
1115         } else
1116             ret->grid[ny*w+nx] = SPACE;
1117
1118         if (ret->grid[nby*w+nbx] == PIT)
1119             ret->grid[nby*w+nbx] = SPACE;
1120         else if (ret->grid[nby*w+nbx] == DEEP_PIT)
1121             /* do nothing - the pit eats the barrel and remains there */;
1122         else if (ret->grid[nby*w+nbx] == TARGET)
1123             ret->grid[nby*w+nbx] = TARGETISE(b);
1124         else
1125             ret->grid[nby*w+nbx] = b;
1126     }
1127
1128     ret->px = nx;
1129     ret->py = ny;
1130
1131     /*
1132      * Check for completion. This is surprisingly complicated,
1133      * given the presence of pits and deep pits, and also the fact
1134      * that some Sokoban levels with pits have fewer pits than
1135      * barrels (due to providing spares, e.g. NetHack's). I think
1136      * the completion condition in fact must be that the game
1137      * cannot become any _more_ complete. That is, _either_ there
1138      * are no remaining barrels not on targets, _or_ there is a
1139      * good reason why any such barrels cannot be placed. The only
1140      * available good reason is that there are no remaining pits,
1141      * no free target squares, and no deep pits at all.
1142      */
1143     if (!ret->completed) {
1144         freebarrels = FALSE;
1145         freetargets = FALSE;
1146         for (i = 0; i < w*h; i++) {
1147             int v = ret->grid[i];
1148
1149             if (IS_BARREL(v) && !IS_ON_TARGET(v))
1150                 freebarrels = TRUE;
1151             if (v == DEEP_PIT || v == PIT ||
1152                 (!IS_BARREL(v) && IS_ON_TARGET(v)))
1153                 freetargets = TRUE;
1154         }
1155
1156         if (!freebarrels || !freetargets)
1157             ret->completed = TRUE;
1158     }
1159
1160     return ret;
1161 }
1162
1163 /* ----------------------------------------------------------------------
1164  * Drawing routines.
1165  */
1166
1167 static void game_compute_size(game_params *params, int tilesize,
1168                               int *x, int *y)
1169 {
1170     /* Ick: fake up `ds->tilesize' for macro expansion purposes */
1171     struct { int tilesize; } ads, *ds = &ads;
1172     ads.tilesize = tilesize;
1173
1174     *x = 2 * BORDER + 1 + params->w * TILESIZE;
1175     *y = 2 * BORDER + 1 + params->h * TILESIZE;
1176 }
1177
1178 static void game_set_size(drawing *dr, game_drawstate *ds,
1179                           game_params *params, int tilesize)
1180 {
1181     ds->tilesize = tilesize;
1182 }
1183
1184 static float *game_colours(frontend *fe, int *ncolours)
1185 {
1186     float *ret = snewn(3 * NCOLOURS, float);
1187     int i;
1188
1189     game_mkhighlight(fe, ret, COL_BACKGROUND, COL_HIGHLIGHT, COL_LOWLIGHT);
1190
1191     ret[COL_OUTLINE * 3 + 0] = 0.0F;
1192     ret[COL_OUTLINE * 3 + 1] = 0.0F;
1193     ret[COL_OUTLINE * 3 + 2] = 0.0F;
1194
1195     ret[COL_PLAYER * 3 + 0] = 0.0F;
1196     ret[COL_PLAYER * 3 + 1] = 1.0F;
1197     ret[COL_PLAYER * 3 + 2] = 0.0F;
1198
1199     ret[COL_BARREL * 3 + 0] = 0.6F;
1200     ret[COL_BARREL * 3 + 1] = 0.3F;
1201     ret[COL_BARREL * 3 + 2] = 0.0F;
1202
1203     ret[COL_TARGET * 3 + 0] = ret[COL_LOWLIGHT * 3 + 0];
1204     ret[COL_TARGET * 3 + 1] = ret[COL_LOWLIGHT * 3 + 1];
1205     ret[COL_TARGET * 3 + 2] = ret[COL_LOWLIGHT * 3 + 2];
1206
1207     ret[COL_PIT * 3 + 0] = ret[COL_LOWLIGHT * 3 + 0] / 2;
1208     ret[COL_PIT * 3 + 1] = ret[COL_LOWLIGHT * 3 + 1] / 2;
1209     ret[COL_PIT * 3 + 2] = ret[COL_LOWLIGHT * 3 + 2] / 2;
1210
1211     ret[COL_DEEP_PIT * 3 + 0] = 0.0F;
1212     ret[COL_DEEP_PIT * 3 + 1] = 0.0F;
1213     ret[COL_DEEP_PIT * 3 + 2] = 0.0F;
1214
1215     ret[COL_TEXT * 3 + 0] = 1.0F;
1216     ret[COL_TEXT * 3 + 1] = 1.0F;
1217     ret[COL_TEXT * 3 + 2] = 1.0F;
1218
1219     ret[COL_GRID * 3 + 0] = ret[COL_LOWLIGHT * 3 + 0];
1220     ret[COL_GRID * 3 + 1] = ret[COL_LOWLIGHT * 3 + 1];
1221     ret[COL_GRID * 3 + 2] = ret[COL_LOWLIGHT * 3 + 2];
1222
1223     ret[COL_OUTLINE * 3 + 0] = 0.0F;
1224     ret[COL_OUTLINE * 3 + 1] = 0.0F;
1225     ret[COL_OUTLINE * 3 + 2] = 0.0F;
1226
1227     for (i = 0; i < 3; i++) {
1228         ret[COL_WALL * 3 + i] = (3 * ret[COL_BACKGROUND * 3 + i] +
1229                                  1 * ret[COL_HIGHLIGHT * 3 + i]) / 4;
1230     }
1231
1232     *ncolours = NCOLOURS;
1233     return ret;
1234 }
1235
1236 static game_drawstate *game_new_drawstate(drawing *dr, game_state *state)
1237 {
1238     int w = state->p.w, h = state->p.h;
1239     struct game_drawstate *ds = snew(struct game_drawstate);
1240     int i;
1241
1242     ds->tilesize = 0;
1243     ds->p = state->p;                  /* structure copy */
1244     ds->grid = snewn(w*h, unsigned short);
1245     for (i = 0; i < w*h; i++)
1246         ds->grid[i] = INVALID;
1247     ds->started = FALSE;
1248
1249     return ds;
1250 }
1251
1252 static void game_free_drawstate(drawing *dr, game_drawstate *ds)
1253 {
1254     sfree(ds->grid);
1255     sfree(ds);
1256 }
1257
1258 static void draw_tile(drawing *dr, game_drawstate *ds, int x, int y, int v)
1259 {
1260     int tx = COORD(x), ty = COORD(y);
1261     int bg = (v & 0x100 ? COL_HIGHLIGHT : COL_BACKGROUND);
1262
1263     v &= 0xFF;
1264
1265     clip(dr, tx+1, ty+1, TILESIZE-1, TILESIZE-1);
1266     draw_rect(dr, tx+1, ty+1, TILESIZE-1, TILESIZE-1, bg);
1267
1268     if (v == WALL) {
1269         int coords[6];
1270
1271         coords[0] = tx + TILESIZE;
1272         coords[1] = ty + TILESIZE;
1273         coords[2] = tx + TILESIZE;
1274         coords[3] = ty + 1;
1275         coords[4] = tx + 1;
1276         coords[5] = ty + TILESIZE;
1277         draw_polygon(dr, coords, 3, COL_LOWLIGHT, COL_LOWLIGHT);
1278
1279         coords[0] = tx + 1;
1280         coords[1] = ty + 1;
1281         draw_polygon(dr, coords, 3, COL_HIGHLIGHT, COL_HIGHLIGHT);
1282
1283         draw_rect(dr, tx + 1 + HIGHLIGHT_WIDTH, ty + 1 + HIGHLIGHT_WIDTH,
1284                   TILESIZE - 2*HIGHLIGHT_WIDTH,
1285                   TILESIZE - 2*HIGHLIGHT_WIDTH, COL_WALL);
1286     } else if (v == PIT) {
1287         draw_circle(dr, tx + TILESIZE/2, ty + TILESIZE/2,
1288                     TILESIZE*3/7, COL_PIT, COL_OUTLINE);
1289     } else if (v == DEEP_PIT) {
1290         draw_circle(dr, tx + TILESIZE/2, ty + TILESIZE/2,
1291                     TILESIZE*3/7, COL_DEEP_PIT, COL_OUTLINE);
1292     } else {
1293         if (IS_ON_TARGET(v)) {
1294             draw_circle(dr, tx + TILESIZE/2, ty + TILESIZE/2,
1295                         TILESIZE*3/7, COL_TARGET, COL_OUTLINE);
1296         }
1297         if (IS_PLAYER(v)) {
1298             draw_circle(dr, tx + TILESIZE/2, ty + TILESIZE/2,
1299                         TILESIZE/3, COL_PLAYER, COL_OUTLINE);
1300         } else if (IS_BARREL(v)) {
1301             char str[2];
1302
1303             draw_circle(dr, tx + TILESIZE/2, ty + TILESIZE/2,
1304                         TILESIZE/3, COL_BARREL, COL_OUTLINE);
1305             str[1] = '\0';
1306             str[0] = BARREL_LABEL(v);
1307             if (str[0]) {
1308                 draw_text(dr, tx + TILESIZE/2, ty + TILESIZE/2,
1309                           FONT_VARIABLE, TILESIZE/2,
1310                           ALIGN_VCENTRE | ALIGN_HCENTRE, COL_TEXT, str);
1311             }
1312         }
1313     }
1314
1315     unclip(dr);
1316     draw_update(dr, tx, ty, TILESIZE, TILESIZE);
1317 }
1318
1319 static void game_redraw(drawing *dr, game_drawstate *ds, game_state *oldstate,
1320                         game_state *state, int dir, game_ui *ui,
1321                         float animtime, float flashtime)
1322 {
1323     int w = state->p.w, h = state->p.h /*, wh = w*h */;
1324     int x, y;
1325     int flashtype;
1326
1327     if (flashtime &&
1328         !((int)(flashtime * 3 / FLASH_LENGTH) % 2))
1329         flashtype = 0x100;
1330     else
1331         flashtype = 0;
1332
1333     /*
1334      * Initialise a fresh drawstate.
1335      */
1336     if (!ds->started) {
1337         int wid, ht;
1338
1339         /*
1340          * Blank out the window initially.
1341          */
1342         game_compute_size(&ds->p, TILESIZE, &wid, &ht);
1343         draw_rect(dr, 0, 0, wid, ht, COL_BACKGROUND);
1344         draw_update(dr, 0, 0, wid, ht);
1345
1346         /*
1347          * Draw the grid lines.
1348          */
1349         for (y = 0; y <= h; y++)
1350             draw_line(dr, COORD(0), COORD(y), COORD(w), COORD(y),
1351                       COL_LOWLIGHT);
1352         for (x = 0; x <= w; x++)
1353             draw_line(dr, COORD(x), COORD(0), COORD(x), COORD(h),
1354                       COL_LOWLIGHT);
1355
1356         ds->started = TRUE;
1357     }
1358
1359     /*
1360      * Draw the grid contents.
1361      */
1362     for (y = 0; y < h; y++)
1363         for (x = 0; x < w; x++) {
1364             int v = state->grid[y*w+x];
1365             if (y == state->py && x == state->px) {
1366                 if (v == TARGET)
1367                     v = PLAYERTARGET;
1368                 else {
1369                     assert(v == SPACE);
1370                     v = PLAYER;
1371                 }
1372             }
1373
1374             v |= flashtype;
1375
1376             if (ds->grid[y*w+x] != v) {
1377                 draw_tile(dr, ds, x, y, v);
1378                 ds->grid[y*w+x] = v;
1379             }
1380         }
1381
1382 }
1383
1384 static float game_anim_length(game_state *oldstate, game_state *newstate,
1385                               int dir, game_ui *ui)
1386 {
1387     return 0.0F;
1388 }
1389
1390 static float game_flash_length(game_state *oldstate, game_state *newstate,
1391                                int dir, game_ui *ui)
1392 {
1393     if (!oldstate->completed && newstate->completed)
1394         return FLASH_LENGTH;
1395     else
1396         return 0.0F;
1397 }
1398
1399 static int game_timing_state(game_state *state, game_ui *ui)
1400 {
1401     return TRUE;
1402 }
1403
1404 static void game_print_size(game_params *params, float *x, float *y)
1405 {
1406 }
1407
1408 static void game_print(drawing *dr, game_state *state, int tilesize)
1409 {
1410 }
1411
1412 #ifdef COMBINED
1413 #define thegame sokoban
1414 #endif
1415
1416 const struct game thegame = {
1417     "Sokoban", NULL, NULL,
1418     default_params,
1419     game_fetch_preset,
1420     decode_params,
1421     encode_params,
1422     free_params,
1423     dup_params,
1424     TRUE, game_configure, custom_params,
1425     validate_params,
1426     new_game_desc,
1427     validate_desc,
1428     new_game,
1429     dup_game,
1430     free_game,
1431     FALSE, solve_game,
1432     FALSE, game_text_format,
1433     new_ui,
1434     free_ui,
1435     encode_ui,
1436     decode_ui,
1437     game_changed_state,
1438     interpret_move,
1439     execute_move,
1440     PREFERRED_TILESIZE, game_compute_size, game_set_size,
1441     game_colours,
1442     game_new_drawstate,
1443     game_free_drawstate,
1444     game_redraw,
1445     game_anim_length,
1446     game_flash_length,
1447     FALSE, FALSE, game_print_size, game_print,
1448     FALSE,                             /* wants_statusbar */
1449     FALSE, game_timing_state,
1450     0,                                 /* flags */
1451 };