From 881746789a489fad85aae8317555f73dbe261556 Mon Sep 17 00:00:00 2001 From: Franklin Wei Date: Sat, 29 Apr 2017 18:21:56 -0400 Subject: puzzles: refactor and resync with upstream This brings puzzles up-to-date with upstream revision 2d333750272c3967cfd5cd3677572cddeaad5932, though certain changes made by me, including cursor-only Untangle and some compilation fixes remain. Upstream code has been moved to its separate subdirectory and future syncs can be done by simply copying over the new sources. Change-Id: Ia6506ca5f78c3627165ea6791d38db414ace0804 --- apps/plugins/puzzles/src/unfinished/sokoban.c | 1479 +++++++++++++++++++++++++ 1 file changed, 1479 insertions(+) create mode 100644 apps/plugins/puzzles/src/unfinished/sokoban.c (limited to 'apps/plugins/puzzles/src/unfinished/sokoban.c') diff --git a/apps/plugins/puzzles/src/unfinished/sokoban.c b/apps/plugins/puzzles/src/unfinished/sokoban.c new file mode 100644 index 0000000000..2f0af35bc2 --- /dev/null +++ b/apps/plugins/puzzles/src/unfinished/sokoban.c @@ -0,0 +1,1479 @@ +/* + * 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 +#include +#include +#include +#include +#include + +#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(const 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(const game_params *params, int full) +{ + char data[256]; + + sprintf(data, "%dx%d", params->w, params->h); + + return dupstr(data); +} + +static config_item *game_configure(const 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(const 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(const 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(const 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(const game_params *params, const 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, const game_params *params, + const 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(const 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(const game_state *state, const game_state *currstate, + const char *aux, char **error) +{ + return NULL; +} + +static int game_can_format_as_text_now(const game_params *params) +{ + return TRUE; +} + +static char *game_text_format(const game_state *state) +{ + return NULL; +} + +static game_ui *new_ui(const game_state *state) +{ + return NULL; +} + +static void free_ui(game_ui *ui) +{ +} + +static char *encode_ui(const game_ui *ui) +{ + return NULL; +} + +static void decode_ui(game_ui *ui, const char *encoding) +{ +} + +static void game_changed_state(game_ui *ui, const game_state *oldstate, + const 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(const game_state *state, game_ui *ui, + const game_drawstate *ds, + int x, int y, int button) +{ + int dx=0, dy=0; + 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 if (button == LEFT_BUTTON) + { + if(x < COORD(state->px)) + dx = -1; + else if (x > COORD(state->px + 1)) + dx = 1; + if(y < COORD(state->py)) + dy = -1; + else if (y > COORD(state->py + 1)) + dy = 1; + } + else + return NULL; + + if((dx == 0) && (dy == 0)) + 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(const game_state *state, const 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(const 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, + const 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, const 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, + const game_state *oldstate, const game_state *state, + int dir, const 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(const game_state *oldstate, + const game_state *newstate, int dir, game_ui *ui) +{ + return 0.0F; +} + +static float game_flash_length(const game_state *oldstate, + const game_state *newstate, int dir, game_ui *ui) +{ + if (!oldstate->completed && newstate->completed) + return FLASH_LENGTH; + else + return 0.0F; +} + +static int game_status(const game_state *state) +{ + return state->completed ? +1 : 0; +} + +static int game_timing_state(const game_state *state, game_ui *ui) +{ + return TRUE; +} + +static void game_print_size(const game_params *params, float *x, float *y) +{ +} + +static void game_print(drawing *dr, const game_state *state, int tilesize) +{ +} + +#ifdef COMBINED +#define thegame sokoban +#endif + +const struct game thegame = { + "Sokoban", NULL, NULL, + default_params, + game_fetch_preset, NULL, + 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_can_format_as_text_now, 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, + game_status, + FALSE, FALSE, game_print_size, game_print, + FALSE, /* wants_statusbar */ + FALSE, game_timing_state, + 0, /* flags */ +}; -- cgit v1.2.3