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