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(const 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(const 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(const 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(const 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(const 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(const 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(const game_params *params, const 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, const game_params *params,
 847                             const char *desc)
 848 {
 849     int w = params->w, h = params->h;
 850     game_state *state = snew(game_state);
 851     int i;
 852
 853     state->p = *params;                /* structure copy */
 854     state->grid = snewn(w*h, unsigned char);
 855     state->px = state->py = -1;
 856     state->completed = FALSE;
 857
 858     i = 0;
 859
 860     while (*desc) {
 861         int c = *desc++;
 862         int n = 1;
 863         if (*desc && isdigit((unsigned char)*desc)) {
 864             n = atoi(desc);
 865             while (*desc && isdigit((unsigned char)*desc)) desc++;
 866         }
 867
 868         if (c == PLAYER || c == PLAYERTARGET) {
 869             state->py = i / w;
 870             state->px = i % w;
 871             c = IS_ON_TARGET(c) ? TARGET : SPACE;
 872         }
 873
 874         while (n-- > 0)
 875             state->grid[i++] = c;
 876     }
 877
 878     assert(i == w*h);
 879     assert(state->px != -1 && state->py != -1);
 880
 881     return state;
 882 }
 883
 884 static game_state *dup_game(const game_state *state)
 885 {
 886     int w = state->p.w, h = state->p.h;
 887     game_state *ret = snew(game_state);
 888
 889     ret->p = state->p;                 /* structure copy */
 890     ret->grid = snewn(w*h, unsigned char);
 891     memcpy(ret->grid, state->grid, w*h);
 892     ret->px = state->px;
 893     ret->py = state->py;
 894     ret->completed = state->completed;
 895
 896     return ret;
 897 }
 898
 899 static void free_game(game_state *state)
 900 {
 901     sfree(state->grid);
 902     sfree(state);
 903 }
 904
 905 static char *solve_game(const game_state *state, const game_state *currstate,
 906                         const char *aux, char **error)
 907 {
 908     return NULL;
 909 }
 910
 911 static int game_can_format_as_text_now(const game_params *params)
 912 {
 913     return TRUE;
 914 }
 915
 916 static char *game_text_format(const game_state *state)
 917 {
 918     return NULL;
 919 }
 920
 921 static game_ui *new_ui(const game_state *state)
 922 {
 923     return NULL;
 924 }
 925
 926 static void free_ui(game_ui *ui)
 927 {
 928 }
 929
 930 static char *encode_ui(const game_ui *ui)
 931 {
 932     return NULL;
 933 }
 934
 935 static void decode_ui(game_ui *ui, const char *encoding)
 936 {
 937 }
 938
 939 static void game_changed_state(game_ui *ui, const game_state *oldstate,
 940                                const game_state *newstate)
 941 {
 942 }
 943
 944 struct game_drawstate {
 945     game_params p;
 946     int tilesize;
 947     int started;
 948     unsigned short *grid;
 949 };
 950
 951 #define PREFERRED_TILESIZE 32
 952 #define TILESIZE (ds->tilesize)
 953 #define BORDER    (TILESIZE)
 954 #define HIGHLIGHT_WIDTH (TILESIZE / 10)
 955 #define COORD(x)  ( (x) * TILESIZE + BORDER )
 956 #define FROMCOORD(x)  ( ((x) - BORDER + TILESIZE) / TILESIZE - 1 )
 957
 958 /*
 959  * I'm going to need to do most of the move-type analysis in both
 960  * interpret_move and execute_move, so I'll abstract it out into a
 961  * subfunction. move_type() returns -1 for an illegal move, 0 for a
 962  * movement, and 1 for a push.
 963  */
 964 int move_type(game_state *state, int dx, int dy)
 965 {
 966     int w = state->p.w, h = state->p.h;
 967     int px = state->px, py = state->py;
 968     int nx, ny, nbx, nby;
 969
 970     assert(dx >= -1 && dx <= +1);
 971     assert(dy >= -1 && dy <= +1);
 972     assert(dx || dy);
 973
 974     nx = px + dx;
 975     ny = py + dy;
 976
 977     /*
 978      * Disallow any move that goes off the grid.
 979      */
 980     if (nx < 0 || nx >= w || ny < 0 || ny >= h)
 981         return -1;
 982
 983     /*
 984      * Examine the target square of the move to see whether it's a
 985      * space, a barrel, or a wall.
 986      */
 987
 988     if (state->grid[ny*w+nx] == WALL ||
 989         state->grid[ny*w+nx] == PIT ||
 990         state->grid[ny*w+nx] == DEEP_PIT)
 991         return -1;                     /* this one's easy; just disallow it */
 992
 993     if (IS_BARREL(state->grid[ny*w+nx])) {
 994         /*
 995          * This is a push move. For a start, that means it must not
 996          * be diagonal.
 997          */
 998         if (dy && dx)
 999             return -1;
1000
1001         /*
1002          * Now find the location of the third square involved in
1003          * the push, and stop if it's off the edge.
1004          */
1005         nbx = nx + dx;
1006         nby = ny + dy;
1007         if (nbx < 0 || nbx >= w || nby < 0 || nby >= h)
1008             return -1;
1009
1010         /*
1011          * That third square must be able to accept a barrel.
1012          */
1013         if (state->grid[nby*w+nbx] == SPACE ||
1014             state->grid[nby*w+nbx] == TARGET ||
1015             state->grid[nby*w+nbx] == PIT ||
1016             state->grid[nby*w+nbx] == DEEP_PIT) {
1017             /*
1018              * The push is valid.
1019              */
1020             return 1;
1021         } else {
1022             return -1;
1023         }
1024     } else {
1025         /*
1026          * This is just an ordinary move. We've already checked the
1027          * target square, so the only thing left to check is that a
1028          * diagonal move has a space on one side to have notionally
1029          * gone through.
1030          */
1031         if (dx && dy &&
1032             state->grid[(py+dy)*w+px] != SPACE &&
1033             state->grid[(py+dy)*w+px] != TARGET &&
1034             state->grid[py*w+(px+dx)] != SPACE &&
1035             state->grid[py*w+(px+dx)] != TARGET)
1036             return -1;
1037
1038         /*
1039          * Otherwise, the move is valid.
1040          */
1041         return 0;
1042     }
1043 }
1044
1045 static char *interpret_move(const game_state *state, game_ui *ui,
1046                             const game_drawstate *ds,
1047                             int x, int y, int button)
1048 {
1049     int dx=0, dy=0;
1050     char *move;
1051
1052     /*
1053      * Diagonal movement is supported as it is in NetHack: it's
1054      * for movement only (never pushing), and one of the two
1055      * squares adjacent to both the source and destination
1056      * squares must be free to move through. In other words, it
1057      * is only a shorthand for two orthogonal moves and cannot
1058      * change the nature of the actual puzzle game.
1059      */
1060     if (button == CURSOR_UP || button == (MOD_NUM_KEYPAD | '8'))
1061         dx = 0, dy = -1;
1062     else if (button == CURSOR_DOWN || button == (MOD_NUM_KEYPAD | '2'))
1063         dx = 0, dy = +1;
1064     else if (button == CURSOR_LEFT || button == (MOD_NUM_KEYPAD | '4'))
1065         dx = -1, dy = 0;
1066     else if (button == CURSOR_RIGHT || button == (MOD_NUM_KEYPAD | '6'))
1067         dx = +1, dy = 0;
1068     else if (button == (MOD_NUM_KEYPAD | '7'))
1069         dx = -1, dy = -1;
1070     else if (button == (MOD_NUM_KEYPAD | '9'))
1071         dx = +1, dy = -1;
1072     else if (button == (MOD_NUM_KEYPAD | '1'))
1073         dx = -1, dy = +1;
1074     else if (button == (MOD_NUM_KEYPAD | '3'))
1075         dx = +1, dy = +1;
1076     else if (button == LEFT_BUTTON)
1077     {
1078         if(x < COORD(state->px))
1079             dx = -1;
1080         else if (x > COORD(state->px + 1))
1081             dx = 1;
1082         if(y < COORD(state->py))
1083             dy = -1;
1084         else if (y > COORD(state->py + 1))
1085             dy = 1;
1086     }
1087     else
1088         return NULL;
1089
1090     if((dx == 0) && (dy == 0))
1091         return(NULL);
1092
1093     if (move_type(state, dx, dy) < 0)
1094         return NULL;
1095
1096     move = snewn(2, char);
1097     move[1] = '\0';
1098     move[0] = '5' - 3*dy + dx;
1099     return move;
1100 }
1101
1102 static game_state *execute_move(const game_state *state, const char *move)
1103 {
1104     int w = state->p.w, h = state->p.h;
1105     int px = state->px, py = state->py;
1106     int dx, dy, nx, ny, nbx, nby, type, m, i, freebarrels, freetargets;
1107     game_state *ret;
1108
1109     if (*move < '1' || *move == '5' || *move > '9' || move[1])
1110         return NULL;                   /* invalid move string */
1111
1112     m = *move - '0';
1113     dx = (m + 2) % 3 - 1;
1114     dy = 2 - (m + 2) / 3;
1115     type = move_type(state, dx, dy);
1116     if (type < 0)
1117         return NULL;
1118
1119     ret = dup_game(state);
1120
1121     nx = px + dx;
1122     ny = py + dy;
1123     nbx = nx + dx;
1124     nby = ny + dy;
1125
1126     if (type) {
1127         int b;
1128
1129         /*
1130          * Push.
1131          */
1132         b = ret->grid[ny*w+nx];
1133         if (IS_ON_TARGET(b)) {
1134             ret->grid[ny*w+nx] = TARGET;
1135             b = DETARGETISE(b);
1136         } else
1137             ret->grid[ny*w+nx] = SPACE;
1138
1139         if (ret->grid[nby*w+nbx] == PIT)
1140             ret->grid[nby*w+nbx] = SPACE;
1141         else if (ret->grid[nby*w+nbx] == DEEP_PIT)
1142             /* do nothing - the pit eats the barrel and remains there */;
1143         else if (ret->grid[nby*w+nbx] == TARGET)
1144             ret->grid[nby*w+nbx] = TARGETISE(b);
1145         else
1146             ret->grid[nby*w+nbx] = b;
1147     }
1148
1149     ret->px = nx;
1150     ret->py = ny;
1151
1152     /*
1153      * Check for completion. This is surprisingly complicated,
1154      * given the presence of pits and deep pits, and also the fact
1155      * that some Sokoban levels with pits have fewer pits than
1156      * barrels (due to providing spares, e.g. NetHack's). I think
1157      * the completion condition in fact must be that the game
1158      * cannot become any _more_ complete. That is, _either_ there
1159      * are no remaining barrels not on targets, _or_ there is a
1160      * good reason why any such barrels cannot be placed. The only
1161      * available good reason is that there are no remaining pits,
1162      * no free target squares, and no deep pits at all.
1163      */
1164     if (!ret->completed) {
1165         freebarrels = FALSE;
1166         freetargets = FALSE;
1167         for (i = 0; i < w*h; i++) {
1168             int v = ret->grid[i];
1169
1170             if (IS_BARREL(v) && !IS_ON_TARGET(v))
1171                 freebarrels = TRUE;
1172             if (v == DEEP_PIT || v == PIT ||
1173                 (!IS_BARREL(v) && IS_ON_TARGET(v)))
1174                 freetargets = TRUE;
1175         }
1176
1177         if (!freebarrels || !freetargets)
1178             ret->completed = TRUE;
1179     }
1180
1181     return ret;
1182 }
1183
1184 /* ----------------------------------------------------------------------
1185  * Drawing routines.
1186  */
1187
1188 static void game_compute_size(const game_params *params, int tilesize,
1189                               int *x, int *y)
1190 {
1191     /* Ick: fake up `ds->tilesize' for macro expansion purposes */
1192     struct { int tilesize; } ads, *ds = &ads;
1193     ads.tilesize = tilesize;
1194
1195     *x = 2 * BORDER + 1 + params->w * TILESIZE;
1196     *y = 2 * BORDER + 1 + params->h * TILESIZE;
1197 }
1198
1199 static void game_set_size(drawing *dr, game_drawstate *ds,
1200                           const game_params *params, int tilesize)
1201 {
1202     ds->tilesize = tilesize;
1203 }
1204
1205 static float *game_colours(frontend *fe, int *ncolours)
1206 {
1207     float *ret = snewn(3 * NCOLOURS, float);
1208     int i;
1209
1210     game_mkhighlight(fe, ret, COL_BACKGROUND, COL_HIGHLIGHT, COL_LOWLIGHT);
1211
1212     ret[COL_OUTLINE * 3 + 0] = 0.0F;
1213     ret[COL_OUTLINE * 3 + 1] = 0.0F;
1214     ret[COL_OUTLINE * 3 + 2] = 0.0F;
1215
1216     ret[COL_PLAYER * 3 + 0] = 0.0F;
1217     ret[COL_PLAYER * 3 + 1] = 1.0F;
1218     ret[COL_PLAYER * 3 + 2] = 0.0F;
1219
1220     ret[COL_BARREL * 3 + 0] = 0.6F;
1221     ret[COL_BARREL * 3 + 1] = 0.3F;
1222     ret[COL_BARREL * 3 + 2] = 0.0F;
1223
1224     ret[COL_TARGET * 3 + 0] = ret[COL_LOWLIGHT * 3 + 0];
1225     ret[COL_TARGET * 3 + 1] = ret[COL_LOWLIGHT * 3 + 1];
1226     ret[COL_TARGET * 3 + 2] = ret[COL_LOWLIGHT * 3 + 2];
1227
1228     ret[COL_PIT * 3 + 0] = ret[COL_LOWLIGHT * 3 + 0] / 2;
1229     ret[COL_PIT * 3 + 1] = ret[COL_LOWLIGHT * 3 + 1] / 2;
1230     ret[COL_PIT * 3 + 2] = ret[COL_LOWLIGHT * 3 + 2] / 2;
1231
1232     ret[COL_DEEP_PIT * 3 + 0] = 0.0F;
1233     ret[COL_DEEP_PIT * 3 + 1] = 0.0F;
1234     ret[COL_DEEP_PIT * 3 + 2] = 0.0F;
1235
1236     ret[COL_TEXT * 3 + 0] = 1.0F;
1237     ret[COL_TEXT * 3 + 1] = 1.0F;
1238     ret[COL_TEXT * 3 + 2] = 1.0F;
1239
1240     ret[COL_GRID * 3 + 0] = ret[COL_LOWLIGHT * 3 + 0];
1241     ret[COL_GRID * 3 + 1] = ret[COL_LOWLIGHT * 3 + 1];
1242     ret[COL_GRID * 3 + 2] = ret[COL_LOWLIGHT * 3 + 2];
1243
1244     ret[COL_OUTLINE * 3 + 0] = 0.0F;
1245     ret[COL_OUTLINE * 3 + 1] = 0.0F;
1246     ret[COL_OUTLINE * 3 + 2] = 0.0F;
1247
1248     for (i = 0; i < 3; i++) {
1249         ret[COL_WALL * 3 + i] = (3 * ret[COL_BACKGROUND * 3 + i] +
1250                                  1 * ret[COL_HIGHLIGHT * 3 + i]) / 4;
1251     }
1252
1253     *ncolours = NCOLOURS;
1254     return ret;
1255 }
1256
1257 static game_drawstate *game_new_drawstate(drawing *dr, const game_state *state)
1258 {
1259     int w = state->p.w, h = state->p.h;
1260     struct game_drawstate *ds = snew(struct game_drawstate);
1261     int i;
1262
1263     ds->tilesize = 0;
1264     ds->p = state->p;                  /* structure copy */
1265     ds->grid = snewn(w*h, unsigned short);
1266     for (i = 0; i < w*h; i++)
1267         ds->grid[i] = INVALID;
1268     ds->started = FALSE;
1269
1270     return ds;
1271 }
1272
1273 static void game_free_drawstate(drawing *dr, game_drawstate *ds)
1274 {
1275     sfree(ds->grid);
1276     sfree(ds);
1277 }
1278
1279 static void draw_tile(drawing *dr, game_drawstate *ds, int x, int y, int v)
1280 {
1281     int tx = COORD(x), ty = COORD(y);
1282     int bg = (v & 0x100 ? COL_HIGHLIGHT : COL_BACKGROUND);
1283
1284     v &= 0xFF;
1285
1286     clip(dr, tx+1, ty+1, TILESIZE-1, TILESIZE-1);
1287     draw_rect(dr, tx+1, ty+1, TILESIZE-1, TILESIZE-1, bg);
1288
1289     if (v == WALL) {
1290         int coords[6];
1291
1292         coords[0] = tx + TILESIZE;
1293         coords[1] = ty + TILESIZE;
1294         coords[2] = tx + TILESIZE;
1295         coords[3] = ty + 1;
1296         coords[4] = tx + 1;
1297         coords[5] = ty + TILESIZE;
1298         draw_polygon(dr, coords, 3, COL_LOWLIGHT, COL_LOWLIGHT);
1299
1300         coords[0] = tx + 1;
1301         coords[1] = ty + 1;
1302         draw_polygon(dr, coords, 3, COL_HIGHLIGHT, COL_HIGHLIGHT);
1303
1304         draw_rect(dr, tx + 1 + HIGHLIGHT_WIDTH, ty + 1 + HIGHLIGHT_WIDTH,
1305                   TILESIZE - 2*HIGHLIGHT_WIDTH,
1306                   TILESIZE - 2*HIGHLIGHT_WIDTH, COL_WALL);
1307     } else if (v == PIT) {
1308         draw_circle(dr, tx + TILESIZE/2, ty + TILESIZE/2,
1309                     TILESIZE*3/7, COL_PIT, COL_OUTLINE);
1310     } else if (v == DEEP_PIT) {
1311         draw_circle(dr, tx + TILESIZE/2, ty + TILESIZE/2,
1312                     TILESIZE*3/7, COL_DEEP_PIT, COL_OUTLINE);
1313     } else {
1314         if (IS_ON_TARGET(v)) {
1315             draw_circle(dr, tx + TILESIZE/2, ty + TILESIZE/2,
1316                         TILESIZE*3/7, COL_TARGET, COL_OUTLINE);
1317         }
1318         if (IS_PLAYER(v)) {
1319             draw_circle(dr, tx + TILESIZE/2, ty + TILESIZE/2,
1320                         TILESIZE/3, COL_PLAYER, COL_OUTLINE);
1321         } else if (IS_BARREL(v)) {
1322             char str[2];
1323
1324             draw_circle(dr, tx + TILESIZE/2, ty + TILESIZE/2,
1325                         TILESIZE/3, COL_BARREL, COL_OUTLINE);
1326             str[1] = '\0';
1327             str[0] = BARREL_LABEL(v);
1328             if (str[0]) {
1329                 draw_text(dr, tx + TILESIZE/2, ty + TILESIZE/2,
1330                           FONT_VARIABLE, TILESIZE/2,
1331                           ALIGN_VCENTRE | ALIGN_HCENTRE, COL_TEXT, str);
1332             }
1333         }
1334     }
1335
1336     unclip(dr);
1337     draw_update(dr, tx, ty, TILESIZE, TILESIZE);
1338 }
1339
1340 static void game_redraw(drawing *dr, game_drawstate *ds,
1341                         const game_state *oldstate, const game_state *state,
1342                         int dir, const game_ui *ui,
1343                         float animtime, float flashtime)
1344 {
1345     int w = state->p.w, h = state->p.h /*, wh = w*h */;
1346     int x, y;
1347     int flashtype;
1348
1349     if (flashtime &&
1350         !((int)(flashtime * 3 / FLASH_LENGTH) % 2))
1351         flashtype = 0x100;
1352     else
1353         flashtype = 0;
1354
1355     /*
1356      * Initialise a fresh drawstate.
1357      */
1358     if (!ds->started) {
1359         int wid, ht;
1360
1361         /*
1362          * Blank out the window initially.
1363          */
1364         game_compute_size(&ds->p, TILESIZE, &wid, &ht);
1365         draw_rect(dr, 0, 0, wid, ht, COL_BACKGROUND);
1366         draw_update(dr, 0, 0, wid, ht);
1367
1368         /*
1369          * Draw the grid lines.
1370          */
1371         for (y = 0; y <= h; y++)
1372             draw_line(dr, COORD(0), COORD(y), COORD(w), COORD(y),
1373                       COL_LOWLIGHT);
1374         for (x = 0; x <= w; x++)
1375             draw_line(dr, COORD(x), COORD(0), COORD(x), COORD(h),
1376                       COL_LOWLIGHT);
1377
1378         ds->started = TRUE;
1379     }
1380
1381     /*
1382      * Draw the grid contents.
1383      */
1384     for (y = 0; y < h; y++)
1385         for (x = 0; x < w; x++) {
1386             int v = state->grid[y*w+x];
1387             if (y == state->py && x == state->px) {
1388                 if (v == TARGET)
1389                     v = PLAYERTARGET;
1390                 else {
1391                     assert(v == SPACE);
1392                     v = PLAYER;
1393                 }
1394             }
1395
1396             v |= flashtype;
1397
1398             if (ds->grid[y*w+x] != v) {
1399                 draw_tile(dr, ds, x, y, v);
1400                 ds->grid[y*w+x] = v;
1401             }
1402         }
1403
1404 }
1405
1406 static float game_anim_length(const game_state *oldstate,
1407                               const game_state *newstate, int dir, game_ui *ui)
1408 {
1409     return 0.0F;
1410 }
1411
1412 static float game_flash_length(const game_state *oldstate,
1413                                const game_state *newstate, int dir, game_ui *ui)
1414 {
1415     if (!oldstate->completed && newstate->completed)
1416         return FLASH_LENGTH;
1417     else
1418         return 0.0F;
1419 }
1420
1421 static int game_status(const game_state *state)
1422 {
1423     return state->completed ? +1 : 0;
1424 }
1425
1426 static int game_timing_state(const game_state *state, game_ui *ui)
1427 {
1428     return TRUE;
1429 }
1430
1431 static void game_print_size(const game_params *params, float *x, float *y)
1432 {
1433 }
1434
1435 static void game_print(drawing *dr, const game_state *state, int tilesize)
1436 {
1437 }
1438
1439 #ifdef COMBINED
1440 #define thegame sokoban
1441 #endif
1442
1443 const struct game thegame = {
1444     "Sokoban", NULL, NULL,
1445     default_params,
1446     game_fetch_preset, NULL,
1447     decode_params,
1448     encode_params,
1449     free_params,
1450     dup_params,
1451     TRUE, game_configure, custom_params,
1452     validate_params,
1453     new_game_desc,
1454     validate_desc,
1455     new_game,
1456     dup_game,
1457     free_game,
1458     FALSE, solve_game,
1459     FALSE, game_can_format_as_text_now, game_text_format,
1460     new_ui,
1461     free_ui,
1462     encode_ui,
1463     decode_ui,
1464     game_changed_state,
1465     interpret_move,
1466     execute_move,
1467     PREFERRED_TILESIZE, game_compute_size, game_set_size,
1468     game_colours,
1469     game_new_drawstate,
1470     game_free_drawstate,
1471     game_redraw,
1472     game_anim_length,
1473     game_flash_length,
1474     game_status,
1475     FALSE, FALSE, game_print_size, game_print,
1476     FALSE,                             /* wants_statusbar */
1477     FALSE, game_timing_state,
1478     0,                                 /* flags */
1479 };