Correction from James H: sqrt(0) shouldn't occur any more than

[sgt/puzzles] / unfinished / sokoban.c

/*
 * sokoban.c: An implementation of the well-known Sokoban barrel-
 * pushing game. Random generation is too simplistic to be
 * credible, but the rest of the gameplay works well enough to use
 * it with hand-written level descriptions.
 */

/*
 * TODO:
 * 
 *  - I think it would be better to ditch the `prev' array, and
 *    instead make the `dist' array strictly monotonic (by having
 *    each distance be something like I*A+S, where A is the grid
 *    area, I the number of INITIAL squares trampled on, and S the
 *    number of harmless spaces moved through). This would permit
 *    the path-tracing when a pull is actually made to choose
 *    randomly from all the possible shortest routes, which would
 *    be superior in terms of eliminating directional bias.
 *     + So when tracing the path back to the current px,py, we
 *       look at all four adjacent squares, find the minimum
 *       distance, check that it's _strictly smaller_ than that of
 *       the current square, and restrict our choice to precisely
 *       those squares with that minimum distance.
 *     + The other place `prev' is currently used is in the check
 *       for consistency of a pull. We would have to replace the
 *       check for whether prev[ny*w+nx]==oy*w+ox with a check that
 *       made sure there was at least one adjacent square with a
 *       smaller distance which _wasn't_ oy*w+ox. Then when we did
 *       the path-tracing we'd also have to take this special case
 *       into account.
 * 
 *  - More discriminating choice of pull. (Snigger.)
 *     + favour putting targets in clumps
 *     + try to shoot for a reasonably consistent number of barrels
 *       (adjust willingness to generate a new barrel depending on
 *       how many are already present)
 *     + adjust willingness to break new ground depending on how
 *       much is already broken
 * 
 *  - generation time parameters:
 *     + enable NetHack mode (and find a better place for the hole)
 *     + decide how many of the remaining Is should be walls
 * 
 *  - at the end of generation, randomly position the starting
 *    player coordinates, probably by (somehow) reusing the same
 *    bfs currently inside the loop.
 * 
 *  - possible backtracking?
 * 
 *  - IWBNI we could spot completely unreachable bits of level at
 *    the outside, and not bother drawing grid lines for them. The
 *    NH levels currently look a bit weird with grid lines on the
 *    outside of the boundary.
 */

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <assert.h>
#include <ctype.h>
#include <math.h>

#include "puzzles.h"

/*
 * Various subsets of these constants are used during game
 * generation, game play, game IDs and the game_drawstate.
 */
#define INITIAL      'i'               /* used only in game generation */
#define SPACE        's'
#define WALL         'w'
#define PIT          'p'
#define DEEP_PIT     'd'
#define TARGET       't'
#define BARREL       'b'
#define BARRELTARGET 'f'               /* target is 'f'illed */
#define PLAYER       'u'               /* yo'u'; used in game IDs */
#define PLAYERTARGET 'v'               /* bad letter: v is to u as t is to s */
#define INVALID      '!'               /* used in drawstate to force redraw */
/*
 * We also support the use of any capital letter as a barrel, which
 * will be displayed with that letter as a label. (This facilitates
 * people distributing annotated game IDs for particular Sokoban
 * levels, so they can accompany them with verbal instructions
 * about pushing particular barrels in particular ways.) Therefore,
 * to find out whether something is a barrel, we need a test
 * function which does a bit more than just comparing to BARREL.
 * 
 * When resting on target squares, capital-letter barrels are
 * replaced with their control-character value (A -> ^A).
 */
#define IS_PLAYER(c) ( (c)==PLAYER || (c)==PLAYERTARGET )
#define IS_BARREL(c) ( (c)==BARREL || (c)==BARRELTARGET || \
                       ((c)>='A' && (c)<='Z') || ((c)>=1 && (c)<=26) )
#define IS_ON_TARGET(c) ( (c)==TARGET || (c)==BARRELTARGET || \
                          (c)==PLAYERTARGET || ((c)>=1 && (c)<=26) )
#define TARGETISE(b) ( (b)==BARREL ? BARRELTARGET : (b)-('A'-1) )
#define DETARGETISE(b) ( (b)==BARRELTARGET ? BARREL : (b)+('A'-1) )
#define BARREL_LABEL(b) ( (b)>='A'&&(b)<='Z' ? (b) : \
                          (b)>=1 && (b)<=26 ? (b)+('A'-1) : 0 )

#define DX(d) (d == 0 ? -1 : d == 2 ? +1 : 0)
#define DY(d) (d == 1 ? -1 : d == 3 ? +1 : 0)

#define FLASH_LENGTH 0.3F

enum {
    COL_BACKGROUND,
    COL_TARGET,
    COL_PIT,
    COL_DEEP_PIT,
    COL_BARREL,
    COL_PLAYER,
    COL_TEXT,
    COL_GRID,
    COL_OUTLINE,
    COL_HIGHLIGHT,
    COL_LOWLIGHT,
    COL_WALL,
    NCOLOURS
};

struct game_params {
    int w, h;
    /*
     * FIXME: a parameter involving degree of filling in?
     */
};

struct game_state {
    game_params p;
    unsigned char *grid;
    int px, py;
    int completed;
};

static game_params *default_params(void)
{
    game_params *ret = snew(game_params);

    ret->w = 12;
    ret->h = 10;

    return ret;
}

static void free_params(game_params *params)
{
    sfree(params);
}

static game_params *dup_params(game_params *params)
{
    game_params *ret = snew(game_params);
    *ret = *params;                    /* structure copy */
    return ret;
}

static const struct game_params sokoban_presets[] = {
    { 12, 10 },
    { 16, 12 },
    { 20, 16 },
};

static int game_fetch_preset(int i, char **name, game_params **params)
{
    game_params p, *ret;
    char *retname;
    char namebuf[80];

    if (i < 0 || i >= lenof(sokoban_presets))
        return FALSE;

    p = sokoban_presets[i];
    ret = dup_params(&p);
    sprintf(namebuf, "%dx%d", ret->w, ret->h);
    retname = dupstr(namebuf);

    *params = ret;
    *name = retname;
    return TRUE;
}

static void decode_params(game_params *params, char const *string)
{
    params->w = params->h = atoi(string);
    while (*string && isdigit((unsigned char)*string)) string++;
    if (*string == 'x') {
        string++;
        params->h = atoi(string);
    }
}

static char *encode_params(game_params *params, int full)
{
    char data[256];

    sprintf(data, "%dx%d", params->w, params->h);

    return dupstr(data);
}

static config_item *game_configure(game_params *params)
{
    config_item *ret;
    char buf[80];

    ret = snewn(3, config_item);

    ret[0].name = "Width";
    ret[0].type = C_STRING;
    sprintf(buf, "%d", params->w);
    ret[0].sval = dupstr(buf);
    ret[0].ival = 0;

    ret[1].name = "Height";
    ret[1].type = C_STRING;
    sprintf(buf, "%d", params->h);
    ret[1].sval = dupstr(buf);
    ret[1].ival = 0;

    ret[2].name = NULL;
    ret[2].type = C_END;
    ret[2].sval = NULL;
    ret[2].ival = 0;

    return ret;
}

static game_params *custom_params(config_item *cfg)
{
    game_params *ret = snew(game_params);

    ret->w = atoi(cfg[0].sval);
    ret->h = atoi(cfg[1].sval);

    return ret;
}

static char *validate_params(game_params *params, int full)
{
    if (params->w < 4 || params->h < 4)
        return "Width and height must both be at least 4";

    return NULL;
}

/* ----------------------------------------------------------------------
 * Game generation mechanism.
 * 
 * To generate a Sokoban level, we begin with a completely blank
 * grid and make valid inverse moves. Grid squares can be in a
 * number of states. The states are:
 * 
 *  - INITIAL: this square has not as yet been touched by any
 *    inverse move, which essentially means we haven't decided what
 *    it is yet.
 * 
 *  - SPACE: this square is a space.
 * 
 *  - TARGET: this square is a space which is also the target for a
 *    barrel.
 * 
 *  - BARREL: this square contains a barrel.
 * 
 *  - BARRELTARGET: this square contains a barrel _on_ a target.
 * 
 *  - WALL: this square is a wall.
 * 
 *  - PLAYER: this square contains the player.
 * 
 *  - PLAYERTARGET: this square contains the player on a target.
 * 
 * We begin with every square of the in state INITIAL, apart from a
 * solid ring of WALLs around the edge. We randomly position the
 * PLAYER somewhere. Thereafter our valid moves are:
 * 
 *  - to move the PLAYER in one direction _pulling_ a barrel after
 *    us. For this to work, we must have SPACE or INITIAL in the
 *    direction we're moving, and BARREL or BARRELTARGET in the
 *    direction we're moving away from. We leave SPACE or TARGET
 *    respectively in the vacated square.
 * 
 *  - to create a new barrel by transforming an INITIAL square into
 *    BARRELTARGET.
 * 
 *  - to move the PLAYER freely through SPACE and TARGET squares,
 *    leaving SPACE or TARGET where it started.
 * 
 *  - to move the player through INITIAL squares, carving a tunnel
 *    of SPACEs as it goes.
 * 
 * We try to avoid destroying INITIAL squares wherever possible (if
 * there's a path to where we want to be using only SPACE, then we
 * should always use that). At the end of generation, every square
 * still in state INITIAL is one which was not required at any
 * point during generation, which means we can randomly choose
 * whether to make it SPACE or WALL.
 * 
 * It's unclear as yet what the right strategy for wall placement
 * should be. Too few WALLs will yield many alternative solutions
 * to the puzzle, whereas too many might rule out so many
 * possibilities that the intended solution becomes obvious.
 */

static void sokoban_generate(int w, int h, unsigned char *grid, int moves,
                             int nethack, random_state *rs)
{
    struct pull {
        int ox, oy, nx, ny, score;
    };

    struct pull *pulls;
    int *dist, *prev, *heap;
    int x, y, px, py, i, j, d, heapsize, npulls;

    pulls = snewn(w * h * 4, struct pull);
    dist = snewn(w * h, int);
    prev = snewn(w * h, int);
    heap = snewn(w * h, int);

    /*
     * Configure the initial grid.
     */
    for (y = 0; y < h; y++)
        for (x = 0; x < w; x++)
            grid[y*w+x] = (x == 0 || y == 0 || x == w-1 || y == h-1 ?
                           WALL : INITIAL);
    if (nethack)
        grid[1] = DEEP_PIT;

    /*
     * Place the player.
     */
    i = random_upto(rs, (w-2) * (h-2));
    x = 1 + i % (w-2);
    y = 1 + i / (w-2);
    grid[y*w+x] = SPACE;
    px = x;
    py = y;

    /*
     * Now loop around making random inverse Sokoban moves. In this
     * loop we aim to make one actual barrel-pull per iteration,
     * plus as many free moves as are necessary to get into
     * position for that pull.
     */
    while (moves-- >= 0) {
        /*
         * First enumerate all the viable barrel-pulls we can
         * possibly make, counting two pulls of the same barrel in
         * different directions as different. We also include pulls
         * we can perform by creating a new barrel. Each pull is
         * marked with the amount of violence it would have to do
         * to the grid.
         */
        npulls = 0;
        for (y = 0; y < h; y++)
            for (x = 0; x < w; x++)
                for (d = 0; d < 4; d++) {
                    int dx = DX(d);
                    int dy = DY(d);
                    int nx = x + dx, ny = y + dy;
                    int npx = nx + dx, npy = ny + dy;
                    int score = 0;

                    /*
                     * The candidate move is to put the player at
                     * (nx,ny), and move him to (npx,npy), pulling
                     * a barrel at (x,y) to (nx,ny). So first we
                     * must check that all those squares are within
                     * the boundaries of the grid. For this it is
                     * sufficient to check npx,npy.
                     */
                    if (npx < 0 || npx >= w || npy < 0 || npy >= h)
                        continue;

                    /*
                     * (x,y) must either be a barrel, or a square
                     * which we can convert into a barrel.
                     */
                    switch (grid[y*w+x]) {
                      case BARREL: case BARRELTARGET:
                        break;
                      case INITIAL:
                        if (nethack)
                            continue;
                        score += 10 /* new_barrel_score */;
                        break;
                      case DEEP_PIT:
                        if (!nethack)
                            continue;
                        break;
                      default:
                        continue;
                    }

                    /*
                     * (nx,ny) must either be a space, or a square
                     * which we can convert into a space.
                     */
                    switch (grid[ny*w+nx]) {
                      case SPACE: case TARGET:
                        break;
                      case INITIAL:
                        score += 3 /* new_space_score */;
                        break;
                      default:
                        continue;
                    }

                    /*
                     * (npx,npy) must also either be a space, or a
                     * square which we can convert into a space.
                     */
                    switch (grid[npy*w+npx]) {
                      case SPACE: case TARGET:
                        break;
                      case INITIAL:
                        score += 3 /* new_space_score */;
                        break;
                      default:
                        continue;
                    }

                    /*
                     * That's sufficient to tag this as a possible
                     * pull right now. We still don't know if we
                     * can reach the required player position, but
                     * that's a job for the subsequent BFS phase to
                     * tell us.
                     */
                    pulls[npulls].ox = x;
                    pulls[npulls].oy = y;
                    pulls[npulls].nx = nx;
                    pulls[npulls].ny = ny;
                    pulls[npulls].score = score;
#ifdef GENERATION_DIAGNOSTICS
                    printf("found potential pull: (%d,%d)-(%d,%d) cost %d\n",
                           pulls[npulls].ox, pulls[npulls].oy,
                           pulls[npulls].nx, pulls[npulls].ny,
                           pulls[npulls].score);
#endif
                    npulls++;
                }
#ifdef GENERATION_DIAGNOSTICS
        printf("found %d potential pulls\n", npulls);
#endif

        /*
         * If there are no pulls available at all, we give up.
         * 
         * (FIXME: or perhaps backtrack?)
         */
        if (npulls == 0)
            break;

        /*
         * Now we do a BFS from our current position, to find all
         * the squares we can get the player into.
         * 
         * This BFS is unusually tricky. We want to give a positive
         * distance only to squares which we have to carve through
         * INITIALs to get to, which means we can't just stick
         * every square we reach on the end of our to-do list.
         * Instead, we must maintain our list as a proper priority
         * queue.
         */
        for (i = 0; i < w*h; i++)
            dist[i] = prev[i] = -1;

        heap[0] = py*w+px;
        heapsize = 1;
        dist[py*w+px] = 0;

#define PARENT(n) ( ((n)-1)/2 )
#define LCHILD(n) ( 2*(n)+1 )
#define RCHILD(n) ( 2*(n)+2 )
#define SWAP(i,j) do { int swaptmp = (i); (i) = (j); (j) = swaptmp; } while (0)

        while (heapsize > 0) {
            /*
             * Pull the smallest element off the heap: it's at
             * position 0. Move the arbitrary element from the very
             * end of the heap into position 0.
             */
            y = heap[0] / w;
            x = heap[0] % w;

            heapsize--;
            heap[0] = heap[heapsize];

            /*
             * Now repeatedly move that arbitrary element down the
             * heap by swapping it with the more suitable of its
             * children.
             */
            i = 0;
            while (1) {
                int lc, rc;

                lc = LCHILD(i);
                rc = RCHILD(i);

                if (lc >= heapsize)
                    break;             /* we've hit bottom */

                if (rc >= heapsize) {
                    /*
                     * Special case: there is only one child to
                     * check.
                     */
                    if (dist[heap[i]] > dist[heap[lc]])
                        SWAP(heap[i], heap[lc]);

                    /* _Now_ we've hit bottom. */
                    break;
                } else {
                    /*
                     * The common case: there are two children and
                     * we must check them both.
                     */
                    if (dist[heap[i]] > dist[heap[lc]] ||
                        dist[heap[i]] > dist[heap[rc]]) {
                        /*
                         * Pick the more appropriate child to swap with
                         * (i.e. the one which would want to be the
                         * parent if one were above the other - as one
                         * is about to be).
                         */
                        if (dist[heap[lc]] > dist[heap[rc]]) {
                            SWAP(heap[i], heap[rc]);
                            i = rc;
                        } else {
                            SWAP(heap[i], heap[lc]);
                            i = lc;
                        }
                    } else {
                        /* This element is in the right place; we're done. */
                        break;
                    }
                }
            }

            /*
             * OK, that's given us (x,y) for this phase of the
             * search. Now try all directions from here.
             */

            for (d = 0; d < 4; d++) {
                int dx = DX(d);
                int dy = DY(d);
                int nx = x + dx, ny = y + dy;
                if (nx < 0 || nx >= w || ny < 0 || ny >= h)
                    continue;
                if (grid[ny*w+nx] != SPACE && grid[ny*w+nx] != TARGET &&
                    grid[ny*w+nx] != INITIAL)
                    continue;
                if (dist[ny*w+nx] == -1) {
                    dist[ny*w+nx] = dist[y*w+x] + (grid[ny*w+nx] == INITIAL);
                    prev[ny*w+nx] = y*w+x;

                    /*
                     * Now insert ny*w+nx at the end of the heap,
                     * and move it down to its appropriate resting
                     * place.
                     */
                    i = heapsize;
                    heap[heapsize++] = ny*w+nx;

                    /*
                     * Swap element n with its parent repeatedly to
                     * preserve the heap property.
                     */

                    while (i > 0) {
                        int p = PARENT(i);

                        if (dist[heap[p]] > dist[heap[i]]) {
                            SWAP(heap[p], heap[i]);
                            i = p;
                        } else
                            break;
                    }
                }
            }
        }

#undef PARENT
#undef LCHILD
#undef RCHILD
#undef SWAP

#ifdef GENERATION_DIAGNOSTICS
        printf("distance map:\n");
        for (i = 0; i < h; i++) {
            for (j = 0; j < w; j++) {
                int d = dist[i*w+j];
                int c;
                if (d < 0)
                    c = '#';
                else if (d >= 36)
                    c = '!';
                else if (d >= 10)
                    c = 'A' - 10 + d;
                else
                    c = '0' + d;
                putchar(c);
            }
            putchar('\n');
        }
#endif

        /*
         * Now we can go back through the `pulls' array, adjusting
         * the score for each pull depending on how hard it is to
         * reach its starting point, and also throwing out any
         * whose starting points are genuinely unreachable even
         * with the possibility of carving through INITIAL squares.
         */
        for (i = j = 0; i < npulls; i++) {
#ifdef GENERATION_DIAGNOSTICS
            printf("potential pull (%d,%d)-(%d,%d)",
                   pulls[i].ox, pulls[i].oy,
                   pulls[i].nx, pulls[i].ny);
#endif
            x = pulls[i].nx;
            y = pulls[i].ny;
            if (dist[y*w+x] < 0) {
#ifdef GENERATION_DIAGNOSTICS
                printf(" unreachable\n");
#endif
                continue;              /* this pull isn't feasible at all */
            } else {
                /*
                 * Another nasty special case we have to check is
                 * whether the initial barrel location (ox,oy) is
                 * on the path used to reach the square. This can
                 * occur if that square is in state INITIAL: the
                 * pull is initially considered valid on the basis
                 * that the INITIAL can become BARRELTARGET, and
                 * it's also considered reachable on the basis that
                 * INITIAL can be turned into SPACE, but it can't
                 * be both at once.
                 * 
                 * Fortunately, if (ox,oy) is on the path at all,
                 * it must be only one space from the end, so this
                 * is easy to spot and rule out.
                 */
                if (prev[y*w+x] == pulls[i].oy*w+pulls[i].ox) {
#ifdef GENERATION_DIAGNOSTICS
                    printf(" goes through itself\n");
#endif
                    continue;          /* this pull isn't feasible at all */
                }
                pulls[j] = pulls[i];   /* structure copy */
                pulls[j].score += dist[y*w+x] * 3 /* new_space_score */;
#ifdef GENERATION_DIAGNOSTICS
                printf(" reachable at distance %d (cost now %d)\n",
                       dist[y*w+x], pulls[j].score);
#endif
                j++;
            }
        }
        npulls = j;

        /*
         * Again, if there are no pulls available at all, we give
         * up.
         * 
         * (FIXME: or perhaps backtrack?)
         */
        if (npulls == 0)
            break;

        /*
         * Now choose which pull to make. On the one hand we should
         * prefer pulls which do less damage to the INITIAL squares
         * (thus, ones for which we can already get into position
         * via existing SPACEs, and for which the barrel already
         * exists and doesn't have to be invented); on the other,
         * we want to avoid _always_ preferring such pulls, on the
         * grounds that that will lead to levels without very much
         * stuff in.
         * 
         * When creating new barrels, we prefer creations which are
         * next to existing TARGET squares.
         * 
         * FIXME: for the moment I'll make this very simple indeed.
         */
        i = random_upto(rs, npulls);

        /*
         * Actually make the pull, including carving a path to get
         * to the site if necessary.
         */
        x = pulls[i].nx;
        y = pulls[i].ny;
        while (prev[y*w+x] >= 0) {
            int p;

            if (grid[y*w+x] == INITIAL)
                grid[y*w+x] = SPACE;

            p = prev[y*w+x];
            y = p / w;
            x = p % w;
        }
        px = 2*pulls[i].nx - pulls[i].ox;
        py = 2*pulls[i].ny - pulls[i].oy;
        if (grid[py*w+px] == INITIAL)
            grid[py*w+px] = SPACE;
        if (grid[pulls[i].ny*w+pulls[i].nx] == TARGET)
            grid[pulls[i].ny*w+pulls[i].nx] = BARRELTARGET;
        else
            grid[pulls[i].ny*w+pulls[i].nx] = BARREL;
        if (grid[pulls[i].oy*w+pulls[i].ox] == BARREL)
            grid[pulls[i].oy*w+pulls[i].ox] = SPACE;
        else if (grid[pulls[i].oy*w+pulls[i].ox] != DEEP_PIT)
            grid[pulls[i].oy*w+pulls[i].ox] = TARGET;
    }

    sfree(heap);
    sfree(prev);
    sfree(dist);
    sfree(pulls);

    if (grid[py*w+px] == TARGET)
        grid[py*w+px] = PLAYERTARGET;
    else
        grid[py*w+px] = PLAYER;
}

static char *new_game_desc(game_params *params, random_state *rs,
                           char **aux, int interactive)
{
    int w = params->w, h = params->h;
    char *desc;
    int desclen, descpos, descsize, prev, count;
    unsigned char *grid;
    int i, j;

    /*
     * FIXME: perhaps some more interesting means of choosing how
     * many moves to try?
     */
    grid = snewn(w*h, unsigned char);
    sokoban_generate(w, h, grid, w*h, FALSE, rs);

    desclen = descpos = descsize = 0;
    desc = NULL;
    prev = -1;
    count = 0;
    for (i = 0; i < w*h; i++) {
        if (descsize < desclen + 40) {
            descsize = desclen + 100;
            desc = sresize(desc, descsize, char);
            desc[desclen] = '\0';
        }
        switch (grid[i]) {
          case INITIAL:
            j = 'w';                   /* FIXME: make some of these 's'? */
            break;
          case SPACE:
            j = 's';
            break;
          case WALL:
            j = 'w';
            break;
          case TARGET:
            j = 't';
            break;
          case BARREL:
            j = 'b';
            break;
          case BARRELTARGET:
            j = 'f';
            break;
          case DEEP_PIT:
            j = 'd';
            break;
          case PLAYER:
            j = 'u';
            break;
          case PLAYERTARGET:
            j = 'v';
            break;
          default:
            j = '?';
            break;
        }
        assert(j != '?');
        if (j != prev) {
            desc[desclen++] = j;
            descpos = desclen;
            prev = j;
            count = 1;
        } else {
            count++;
            desclen = descpos + sprintf(desc+descpos, "%d", count);
        }
    }

    sfree(grid);

    return desc;
}

static char *validate_desc(game_params *params, char *desc)
{
    int w = params->w, h = params->h;
    int area = 0;
    int nplayers = 0;

    while (*desc) {
        int c = *desc++;
        int n = 1;
        if (*desc && isdigit((unsigned char)*desc)) {
            n = atoi(desc);
            while (*desc && isdigit((unsigned char)*desc)) desc++;
        }

        area += n;

        if (c == PLAYER || c == PLAYERTARGET)
            nplayers += n;
        else if (c == INITIAL || c == SPACE || c == WALL || c == TARGET ||
                 c == PIT || c == DEEP_PIT || IS_BARREL(c))
            /* ok */;
        else
            return "Invalid character in game description";
    }

    if (area > w*h)
        return "Too much data in game description";
    if (area < w*h)
        return "Too little data in game description";
    if (nplayers < 1)
        return "No starting player position specified";
    if (nplayers > 1)
        return "More than one starting player position specified";

    return NULL;
}

static game_state *new_game(midend *me, game_params *params, char *desc)
{
    int w = params->w, h = params->h;
    game_state *state = snew(game_state);
    int i;

    state->p = *params;                /* structure copy */
    state->grid = snewn(w*h, unsigned char);
    state->px = state->py = -1;
    state->completed = FALSE;

    i = 0;

    while (*desc) {
        int c = *desc++;
        int n = 1;
        if (*desc && isdigit((unsigned char)*desc)) {
            n = atoi(desc);
            while (*desc && isdigit((unsigned char)*desc)) desc++;
        }

        if (c == PLAYER || c == PLAYERTARGET) {
            state->py = i / w;
            state->px = i % w;
            c = IS_ON_TARGET(c) ? TARGET : SPACE;
        }

        while (n-- > 0)
            state->grid[i++] = c;
    }

    assert(i == w*h);
    assert(state->px != -1 && state->py != -1);

    return state;
}

static game_state *dup_game(game_state *state)
{
    int w = state->p.w, h = state->p.h;
    game_state *ret = snew(game_state);

    ret->p = state->p;                 /* structure copy */
    ret->grid = snewn(w*h, unsigned char);
    memcpy(ret->grid, state->grid, w*h);
    ret->px = state->px;
    ret->py = state->py;
    ret->completed = state->completed;

    return ret;
}

static void free_game(game_state *state)
{
    sfree(state->grid);
    sfree(state);
}

static char *solve_game(game_state *state, game_state *currstate,
                        char *aux, char **error)
{
    return NULL;
}

static char *game_text_format(game_state *state)
{
    return NULL;
}

static game_ui *new_ui(game_state *state)
{
    return NULL;
}

static void free_ui(game_ui *ui)
{
}

static char *encode_ui(game_ui *ui)
{
    return NULL;
}

static void decode_ui(game_ui *ui, char *encoding)
{
}

static void game_changed_state(game_ui *ui, game_state *oldstate,
                               game_state *newstate)
{
}

struct game_drawstate {
    game_params p;
    int tilesize;
    int started;
    unsigned short *grid;
};

#define PREFERRED_TILESIZE 32
#define TILESIZE (ds->tilesize)
#define BORDER    (TILESIZE)
#define HIGHLIGHT_WIDTH (TILESIZE / 10)
#define COORD(x)  ( (x) * TILESIZE + BORDER )
#define FROMCOORD(x)  ( ((x) - BORDER + TILESIZE) / TILESIZE - 1 )

/*
 * I'm going to need to do most of the move-type analysis in both
 * interpret_move and execute_move, so I'll abstract it out into a
 * subfunction. move_type() returns -1 for an illegal move, 0 for a
 * movement, and 1 for a push.
 */
int move_type(game_state *state, int dx, int dy)
{
    int w = state->p.w, h = state->p.h;
    int px = state->px, py = state->py;
    int nx, ny, nbx, nby;

    assert(dx >= -1 && dx <= +1);
    assert(dy >= -1 && dy <= +1);
    assert(dx || dy);

    nx = px + dx;
    ny = py + dy;

    /*
     * Disallow any move that goes off the grid.
     */
    if (nx < 0 || nx >= w || ny < 0 || ny >= h)
        return -1;

    /*
     * Examine the target square of the move to see whether it's a
     * space, a barrel, or a wall.
     */

    if (state->grid[ny*w+nx] == WALL ||
        state->grid[ny*w+nx] == PIT ||
        state->grid[ny*w+nx] == DEEP_PIT)
        return -1;                     /* this one's easy; just disallow it */

    if (IS_BARREL(state->grid[ny*w+nx])) {
        /*
         * This is a push move. For a start, that means it must not
         * be diagonal.
         */
        if (dy && dx)
            return -1;

        /*
         * Now find the location of the third square involved in
         * the push, and stop if it's off the edge.
         */
        nbx = nx + dx;
        nby = ny + dy;
        if (nbx < 0 || nbx >= w || nby < 0 || nby >= h)
            return -1;

        /*
         * That third square must be able to accept a barrel.
         */
        if (state->grid[nby*w+nbx] == SPACE ||
            state->grid[nby*w+nbx] == TARGET ||
            state->grid[nby*w+nbx] == PIT ||
            state->grid[nby*w+nbx] == DEEP_PIT) {
            /*
             * The push is valid.
             */
            return 1;
        } else {
            return -1;
        }
    } else {
        /*
         * This is just an ordinary move. We've already checked the
         * target square, so the only thing left to check is that a
         * diagonal move has a space on one side to have notionally
         * gone through.
         */
        if (dx && dy &&
            state->grid[(py+dy)*w+px] != SPACE &&
            state->grid[(py+dy)*w+px] != TARGET &&
            state->grid[py*w+(px+dx)] != SPACE &&
            state->grid[py*w+(px+dx)] != TARGET)
            return -1;

        /*
         * Otherwise, the move is valid.
         */
        return 0;
    }
}

static char *interpret_move(game_state *state, game_ui *ui, game_drawstate *ds,
                            int x, int y, int button)
{
    int dx, dy;
    char *move;

    /*
     * Diagonal movement is supported as it is in NetHack: it's
     * for movement only (never pushing), and one of the two
     * squares adjacent to both the source and destination
     * squares must be free to move through. In other words, it
     * is only a shorthand for two orthogonal moves and cannot
     * change the nature of the actual puzzle game.
     */
    if (button == CURSOR_UP || button == (MOD_NUM_KEYPAD | '8'))
        dx = 0, dy = -1;
    else if (button == CURSOR_DOWN || button == (MOD_NUM_KEYPAD | '2'))
        dx = 0, dy = +1;
    else if (button == CURSOR_LEFT || button == (MOD_NUM_KEYPAD | '4'))
        dx = -1, dy = 0;
    else if (button == CURSOR_RIGHT || button == (MOD_NUM_KEYPAD | '6'))
        dx = +1, dy = 0;
    else if (button == (MOD_NUM_KEYPAD | '7'))
        dx = -1, dy = -1;
    else if (button == (MOD_NUM_KEYPAD | '9'))
        dx = +1, dy = -1;
    else if (button == (MOD_NUM_KEYPAD | '1'))
        dx = -1, dy = +1;
    else if (button == (MOD_NUM_KEYPAD | '3'))
        dx = +1, dy = +1;
    else
        return NULL;

    if (move_type(state, dx, dy) < 0)
        return NULL;

    move = snewn(2, char);
    move[1] = '\0';
    move[0] = '5' - 3*dy + dx;
    return move;
}

static game_state *execute_move(game_state *state, char *move)
{
    int w = state->p.w, h = state->p.h;
    int px = state->px, py = state->py;
    int dx, dy, nx, ny, nbx, nby, type, m, i, freebarrels, freetargets;
    game_state *ret;

    if (*move < '1' || *move == '5' || *move > '9' || move[1])
        return NULL;                   /* invalid move string */

    m = *move - '0';
    dx = (m + 2) % 3 - 1;
    dy = 2 - (m + 2) / 3;
    type = move_type(state, dx, dy);
    if (type < 0)
        return NULL;

    ret = dup_game(state);

    nx = px + dx;
    ny = py + dy;
    nbx = nx + dx;
    nby = ny + dy;

    if (type) {
        int b;

        /*
         * Push.
         */
        b = ret->grid[ny*w+nx];
        if (IS_ON_TARGET(b)) {
            ret->grid[ny*w+nx] = TARGET;
            b = DETARGETISE(b);
        } else
            ret->grid[ny*w+nx] = SPACE;

        if (ret->grid[nby*w+nbx] == PIT)
            ret->grid[nby*w+nbx] = SPACE;
        else if (ret->grid[nby*w+nbx] == DEEP_PIT)
            /* do nothing - the pit eats the barrel and remains there */;
        else if (ret->grid[nby*w+nbx] == TARGET)
            ret->grid[nby*w+nbx] = TARGETISE(b);
        else
            ret->grid[nby*w+nbx] = b;
    }

    ret->px = nx;
    ret->py = ny;

    /*
     * Check for completion. This is surprisingly complicated,
     * given the presence of pits and deep pits, and also the fact
     * that some Sokoban levels with pits have fewer pits than
     * barrels (due to providing spares, e.g. NetHack's). I think
     * the completion condition in fact must be that the game
     * cannot become any _more_ complete. That is, _either_ there
     * are no remaining barrels not on targets, _or_ there is a
     * good reason why any such barrels cannot be placed. The only
     * available good reason is that there are no remaining pits,
     * no free target squares, and no deep pits at all.
     */
    if (!ret->completed) {
        freebarrels = FALSE;
        freetargets = FALSE;
        for (i = 0; i < w*h; i++) {
            int v = ret->grid[i];

            if (IS_BARREL(v) && !IS_ON_TARGET(v))
                freebarrels = TRUE;
            if (v == DEEP_PIT || v == PIT ||
                (!IS_BARREL(v) && IS_ON_TARGET(v)))
                freetargets = TRUE;
        }

        if (!freebarrels || !freetargets)
            ret->completed = TRUE;
    }

    return ret;
}

/* ----------------------------------------------------------------------
 * Drawing routines.
 */

static void game_compute_size(game_params *params, int tilesize,
                              int *x, int *y)
{
    /* Ick: fake up `ds->tilesize' for macro expansion purposes */
    struct { int tilesize; } ads, *ds = &ads;
    ads.tilesize = tilesize;

    *x = 2 * BORDER + 1 + params->w * TILESIZE;
    *y = 2 * BORDER + 1 + params->h * TILESIZE;
}

static void game_set_size(drawing *dr, game_drawstate *ds,
                          game_params *params, int tilesize)
{
    ds->tilesize = tilesize;
}

static float *game_colours(frontend *fe, int *ncolours)
{
    float *ret = snewn(3 * NCOLOURS, float);
    int i;

    game_mkhighlight(fe, ret, COL_BACKGROUND, COL_HIGHLIGHT, COL_LOWLIGHT);

    ret[COL_OUTLINE * 3 + 0] = 0.0F;
    ret[COL_OUTLINE * 3 + 1] = 0.0F;
    ret[COL_OUTLINE * 3 + 2] = 0.0F;

    ret[COL_PLAYER * 3 + 0] = 0.0F;
    ret[COL_PLAYER * 3 + 1] = 1.0F;
    ret[COL_PLAYER * 3 + 2] = 0.0F;

    ret[COL_BARREL * 3 + 0] = 0.6F;
    ret[COL_BARREL * 3 + 1] = 0.3F;
    ret[COL_BARREL * 3 + 2] = 0.0F;

    ret[COL_TARGET * 3 + 0] = ret[COL_LOWLIGHT * 3 + 0];
    ret[COL_TARGET * 3 + 1] = ret[COL_LOWLIGHT * 3 + 1];
    ret[COL_TARGET * 3 + 2] = ret[COL_LOWLIGHT * 3 + 2];

    ret[COL_PIT * 3 + 0] = ret[COL_LOWLIGHT * 3 + 0] / 2;
    ret[COL_PIT * 3 + 1] = ret[COL_LOWLIGHT * 3 + 1] / 2;
    ret[COL_PIT * 3 + 2] = ret[COL_LOWLIGHT * 3 + 2] / 2;

    ret[COL_DEEP_PIT * 3 + 0] = 0.0F;
    ret[COL_DEEP_PIT * 3 + 1] = 0.0F;
    ret[COL_DEEP_PIT * 3 + 2] = 0.0F;

    ret[COL_TEXT * 3 + 0] = 1.0F;
    ret[COL_TEXT * 3 + 1] = 1.0F;
    ret[COL_TEXT * 3 + 2] = 1.0F;

    ret[COL_GRID * 3 + 0] = ret[COL_LOWLIGHT * 3 + 0];
    ret[COL_GRID * 3 + 1] = ret[COL_LOWLIGHT * 3 + 1];
    ret[COL_GRID * 3 + 2] = ret[COL_LOWLIGHT * 3 + 2];

    ret[COL_OUTLINE * 3 + 0] = 0.0F;
    ret[COL_OUTLINE * 3 + 1] = 0.0F;
    ret[COL_OUTLINE * 3 + 2] = 0.0F;

    for (i = 0; i < 3; i++) {
        ret[COL_WALL * 3 + i] = (3 * ret[COL_BACKGROUND * 3 + i] +
                                 1 * ret[COL_HIGHLIGHT * 3 + i]) / 4;
    }

    *ncolours = NCOLOURS;
    return ret;
}

static game_drawstate *game_new_drawstate(drawing *dr, game_state *state)
{
    int w = state->p.w, h = state->p.h;
    struct game_drawstate *ds = snew(struct game_drawstate);
    int i;

    ds->tilesize = 0;
    ds->p = state->p;                  /* structure copy */
    ds->grid = snewn(w*h, unsigned short);
    for (i = 0; i < w*h; i++)
        ds->grid[i] = INVALID;
    ds->started = FALSE;

    return ds;
}

static void game_free_drawstate(drawing *dr, game_drawstate *ds)
{
    sfree(ds->grid);
    sfree(ds);
}

static void draw_tile(drawing *dr, game_drawstate *ds, int x, int y, int v)
{
    int tx = COORD(x), ty = COORD(y);
    int bg = (v & 0x100 ? COL_HIGHLIGHT : COL_BACKGROUND);

    v &= 0xFF;

    clip(dr, tx+1, ty+1, TILESIZE-1, TILESIZE-1);
    draw_rect(dr, tx+1, ty+1, TILESIZE-1, TILESIZE-1, bg);

    if (v == WALL) {
        int coords[6];

        coords[0] = tx + TILESIZE;
        coords[1] = ty + TILESIZE;
        coords[2] = tx + TILESIZE;
        coords[3] = ty + 1;
        coords[4] = tx + 1;
        coords[5] = ty + TILESIZE;
        draw_polygon(dr, coords, 3, COL_LOWLIGHT, COL_LOWLIGHT);

        coords[0] = tx + 1;
        coords[1] = ty + 1;
        draw_polygon(dr, coords, 3, COL_HIGHLIGHT, COL_HIGHLIGHT);

        draw_rect(dr, tx + 1 + HIGHLIGHT_WIDTH, ty + 1 + HIGHLIGHT_WIDTH,
                  TILESIZE - 2*HIGHLIGHT_WIDTH,
                  TILESIZE - 2*HIGHLIGHT_WIDTH, COL_WALL);
    } else if (v == PIT) {
        draw_circle(dr, tx + TILESIZE/2, ty + TILESIZE/2,
                    TILESIZE*3/7, COL_PIT, COL_OUTLINE);
    } else if (v == DEEP_PIT) {
        draw_circle(dr, tx + TILESIZE/2, ty + TILESIZE/2,
                    TILESIZE*3/7, COL_DEEP_PIT, COL_OUTLINE);
    } else {
        if (IS_ON_TARGET(v)) {
            draw_circle(dr, tx + TILESIZE/2, ty + TILESIZE/2,
                        TILESIZE*3/7, COL_TARGET, COL_OUTLINE);
        }
        if (IS_PLAYER(v)) {
            draw_circle(dr, tx + TILESIZE/2, ty + TILESIZE/2,
                        TILESIZE/3, COL_PLAYER, COL_OUTLINE);
        } else if (IS_BARREL(v)) {
            char str[2];

            draw_circle(dr, tx + TILESIZE/2, ty + TILESIZE/2,
                        TILESIZE/3, COL_BARREL, COL_OUTLINE);
            str[1] = '\0';
            str[0] = BARREL_LABEL(v);
            if (str[0]) {
                draw_text(dr, tx + TILESIZE/2, ty + TILESIZE/2,
                          FONT_VARIABLE, TILESIZE/2,
                          ALIGN_VCENTRE | ALIGN_HCENTRE, COL_TEXT, str);
            }
        }
    }

    unclip(dr);
    draw_update(dr, tx, ty, TILESIZE, TILESIZE);
}

static void game_redraw(drawing *dr, game_drawstate *ds, game_state *oldstate,
                        game_state *state, int dir, game_ui *ui,
                        float animtime, float flashtime)
{
    int w = state->p.w, h = state->p.h /*, wh = w*h */;
    int x, y;
    int flashtype;

    if (flashtime &&
        !((int)(flashtime * 3 / FLASH_LENGTH) % 2))
        flashtype = 0x100;
    else
        flashtype = 0;

    /*
     * Initialise a fresh drawstate.
     */
    if (!ds->started) {
        int wid, ht;

        /*
         * Blank out the window initially.
         */
        game_compute_size(&ds->p, TILESIZE, &wid, &ht);
        draw_rect(dr, 0, 0, wid, ht, COL_BACKGROUND);
        draw_update(dr, 0, 0, wid, ht);

        /*
         * Draw the grid lines.
         */
        for (y = 0; y <= h; y++)
            draw_line(dr, COORD(0), COORD(y), COORD(w), COORD(y),
                      COL_LOWLIGHT);
        for (x = 0; x <= w; x++)
            draw_line(dr, COORD(x), COORD(0), COORD(x), COORD(h),
                      COL_LOWLIGHT);

        ds->started = TRUE;
    }

    /*
     * Draw the grid contents.
     */
    for (y = 0; y < h; y++)
        for (x = 0; x < w; x++) {
            int v = state->grid[y*w+x];
            if (y == state->py && x == state->px) {
                if (v == TARGET)
                    v = PLAYERTARGET;
                else {
                    assert(v == SPACE);
                    v = PLAYER;
                }
            }

            v |= flashtype;

            if (ds->grid[y*w+x] != v) {
                draw_tile(dr, ds, x, y, v);
                ds->grid[y*w+x] = v;
            }
        }

}

static float game_anim_length(game_state *oldstate, game_state *newstate,
                              int dir, game_ui *ui)
{
    return 0.0F;
}

static float game_flash_length(game_state *oldstate, game_state *newstate,
                               int dir, game_ui *ui)
{
    if (!oldstate->completed && newstate->completed)
        return FLASH_LENGTH;
    else
        return 0.0F;
}

static int game_timing_state(game_state *state, game_ui *ui)
{
    return TRUE;
}

static void game_print_size(game_params *params, float *x, float *y)
{
}

static void game_print(drawing *dr, game_state *state, int tilesize)
{
}

#ifdef COMBINED
#define thegame sokoban
#endif

const struct game thegame = {
    "Sokoban", NULL, NULL,
    default_params,
    game_fetch_preset,
    decode_params,
    encode_params,
    free_params,
    dup_params,
    TRUE, game_configure, custom_params,
    validate_params,
    new_game_desc,
    validate_desc,
    new_game,
    dup_game,
    free_game,
    FALSE, solve_game,
    FALSE, game_text_format,
    new_ui,
    free_ui,
    encode_ui,
    decode_ui,
    game_changed_state,
    interpret_move,
    execute_move,
    PREFERRED_TILESIZE, game_compute_size, game_set_size,
    game_colours,
    game_new_drawstate,
    game_free_drawstate,
    game_redraw,
    game_anim_length,
    game_flash_length,
    FALSE, FALSE, game_print_size, game_print,
    FALSE,                             /* wants_statusbar */
    FALSE, game_timing_state,
    0,                                 /* flags */
};