diff options
Diffstat (limited to 'apps/plugins/puzzles/src/unfinished/sokoban.c')
-rw-r--r-- | apps/plugins/puzzles/src/unfinished/sokoban.c | 1486 |
1 files changed, 0 insertions, 1486 deletions
diff --git a/apps/plugins/puzzles/src/unfinished/sokoban.c b/apps/plugins/puzzles/src/unfinished/sokoban.c deleted file mode 100644 index ecc222c906..0000000000 --- a/apps/plugins/puzzles/src/unfinished/sokoban.c +++ /dev/null @@ -1,1486 +0,0 @@ -/* - * 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; - 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 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; - 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. - */ -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, - 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 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, 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, - NULL, /* game_request_keys */ - 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_get_cursor_location, - game_status, - false, false, game_print_size, game_print, - false, /* wants_statusbar */ - false, game_timing_state, - 0, /* flags */ -}; |