ref: 23d4322fec38f8ffac930bc541e08309e1d02f11
dir: /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> #ifdef NO_TGMATH_H # include <math.h> #else # include <tgmath.h> #endif #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; bool 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 bool 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, bool 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].u.string.sval = dupstr(buf); ret[1].name = "Height"; ret[1].type = C_STRING; sprintf(buf, "%d", params->h); ret[1].u.string.sval = dupstr(buf); ret[2].name = NULL; ret[2].type = C_END; return ret; } static game_params *custom_params(const config_item *cfg) { game_params *ret = snew(game_params); ret->w = atoi(cfg[0].u.string.sval); ret->h = atoi(cfg[1].u.string.sval); return ret; } static const char *validate_params(const game_params *params, bool 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, bool 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, bool 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 const 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, const char **error) { return NULL; } static bool 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 void game_changed_state(game_ui *ui, const game_state *oldstate, const game_state *newstate) { } struct game_drawstate { game_params p; int tilesize; bool 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. */ static int move_type(const 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; bool 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, const game_ui *ui, 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) { /* * 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 void game_get_cursor_location(const game_ui *ui, const game_drawstate *ds, const game_state *state, const game_params *params, int *x, int *y, int *w, int *h) { } static int game_status(const game_state *state) { return state->completed ? +1 : 0; } static bool game_timing_state(const game_state *state, game_ui *ui) { return true; } static void game_print_size(const game_params *params, const game_ui *ui, float *x, float *y) { } static void game_print(drawing *dr, const game_state *state, const game_ui *ui, 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, NULL, NULL, /* get_prefs, set_prefs */ new_ui, free_ui, NULL, /* encode_ui */ NULL, /* decode_ui */ NULL, /* game_request_keys */ game_changed_state, NULL, /* current_key_label */ 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_get_cursor_location, game_status, false, false, game_print_size, game_print, false, /* wants_statusbar */ false, game_timing_state, 0, /* flags */ };