+/*
+ * 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,
+ 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 */
+};