2 * sokoban.c: An implementation of the well-known Sokoban barrel-
3 * pushing game. Random generation is too simplistic to be
4 * credible, but the rest of the gameplay works well enough to use
5 * it with hand-written level descriptions.
11 * - I think it would be better to ditch the `prev' array, and
12 * instead make the `dist' array strictly monotonic (by having
13 * each distance be something like I*A+S, where A is the grid
14 * area, I the number of INITIAL squares trampled on, and S the
15 * number of harmless spaces moved through). This would permit
16 * the path-tracing when a pull is actually made to choose
17 * randomly from all the possible shortest routes, which would
18 * be superior in terms of eliminating directional bias.
19 * + So when tracing the path back to the current px,py, we
20 * look at all four adjacent squares, find the minimum
21 * distance, check that it's _strictly smaller_ than that of
22 * the current square, and restrict our choice to precisely
23 * those squares with that minimum distance.
24 * + The other place `prev' is currently used is in the check
25 * for consistency of a pull. We would have to replace the
26 * check for whether prev[ny*w+nx]==oy*w+ox with a check that
27 * made sure there was at least one adjacent square with a
28 * smaller distance which _wasn't_ oy*w+ox. Then when we did
29 * the path-tracing we'd also have to take this special case
32 * - More discriminating choice of pull. (Snigger.)
33 * + favour putting targets in clumps
34 * + try to shoot for a reasonably consistent number of barrels
35 * (adjust willingness to generate a new barrel depending on
36 * how many are already present)
37 * + adjust willingness to break new ground depending on how
38 * much is already broken
40 * - generation time parameters:
41 * + enable NetHack mode (and find a better place for the hole)
42 * + decide how many of the remaining Is should be walls
44 * - at the end of generation, randomly position the starting
45 * player coordinates, probably by (somehow) reusing the same
46 * bfs currently inside the loop.
48 * - possible backtracking?
50 * - IWBNI we could spot completely unreachable bits of level at
51 * the outside, and not bother drawing grid lines for them. The
52 * NH levels currently look a bit weird with grid lines on the
53 * outside of the boundary.
66 * Various subsets of these constants are used during game
67 * generation, game play, game IDs and the game_drawstate.
69 #define INITIAL 'i' /* used only in game generation */
76 #define BARRELTARGET 'f' /* target is 'f'illed */
77 #define PLAYER 'u' /* yo'u'; used in game IDs */
78 #define PLAYERTARGET 'v' /* bad letter: v is to u as t is to s */
79 #define INVALID '!' /* used in drawstate to force redraw */
81 * We also support the use of any capital letter as a barrel, which
82 * will be displayed with that letter as a label. (This facilitates
83 * people distributing annotated game IDs for particular Sokoban
84 * levels, so they can accompany them with verbal instructions
85 * about pushing particular barrels in particular ways.) Therefore,
86 * to find out whether something is a barrel, we need a test
87 * function which does a bit more than just comparing to BARREL.
89 * When resting on target squares, capital-letter barrels are
90 * replaced with their control-character value (A -> ^A).
92 #define IS_PLAYER(c) ( (c)==PLAYER || (c)==PLAYERTARGET )
93 #define IS_BARREL(c) ( (c)==BARREL || (c)==BARRELTARGET || \
94 ((c)>='A' && (c)<='Z') || ((c)>=1 && (c)<=26) )
95 #define IS_ON_TARGET(c) ( (c)==TARGET || (c)==BARRELTARGET || \
96 (c)==PLAYERTARGET || ((c)>=1 && (c)<=26) )
97 #define TARGETISE(b) ( (b)==BARREL ? BARRELTARGET : (b)-('A'-1) )
98 #define DETARGETISE(b) ( (b)==BARRELTARGET ? BARREL : (b)+('A'-1) )
99 #define BARREL_LABEL(b) ( (b)>='A'&&(b)<='Z' ? (b) : \
100 (b)>=1 && (b)<=26 ? (b)+('A'-1) : 0 )
102 #define DX(d) (d == 0 ? -1 : d == 2 ? +1 : 0)
103 #define DY(d) (d == 1 ? -1 : d == 3 ? +1 : 0)
105 #define FLASH_LENGTH 0.3F
126 * FIXME: a parameter involving degree of filling in?
137 static game_params *default_params(void)
139 game_params *ret = snew(game_params);
147 static void free_params(game_params *params)
152 static game_params *dup_params(const game_params *params)
154 game_params *ret = snew(game_params);
155 *ret = *params; /* structure copy */
159 static const struct game_params sokoban_presets[] = {
165 static int game_fetch_preset(int i, char **name, game_params **params)
171 if (i < 0 || i >= lenof(sokoban_presets))
174 p = sokoban_presets[i];
175 ret = dup_params(&p);
176 sprintf(namebuf, "%dx%d", ret->w, ret->h);
177 retname = dupstr(namebuf);
184 static void decode_params(game_params *params, char const *string)
186 params->w = params->h = atoi(string);
187 while (*string && isdigit((unsigned char)*string)) string++;
188 if (*string == 'x') {
190 params->h = atoi(string);
194 static char *encode_params(const game_params *params, int full)
198 sprintf(data, "%dx%d", params->w, params->h);
203 static config_item *game_configure(const game_params *params)
208 ret = snewn(3, config_item);
210 ret[0].name = "Width";
211 ret[0].type = C_STRING;
212 sprintf(buf, "%d", params->w);
213 ret[0].sval = dupstr(buf);
216 ret[1].name = "Height";
217 ret[1].type = C_STRING;
218 sprintf(buf, "%d", params->h);
219 ret[1].sval = dupstr(buf);
230 static game_params *custom_params(const config_item *cfg)
232 game_params *ret = snew(game_params);
234 ret->w = atoi(cfg[0].sval);
235 ret->h = atoi(cfg[1].sval);
240 static char *validate_params(const game_params *params, int full)
242 if (params->w < 4 || params->h < 4)
243 return "Width and height must both be at least 4";
248 /* ----------------------------------------------------------------------
249 * Game generation mechanism.
251 * To generate a Sokoban level, we begin with a completely blank
252 * grid and make valid inverse moves. Grid squares can be in a
253 * number of states. The states are:
255 * - INITIAL: this square has not as yet been touched by any
256 * inverse move, which essentially means we haven't decided what
259 * - SPACE: this square is a space.
261 * - TARGET: this square is a space which is also the target for a
264 * - BARREL: this square contains a barrel.
266 * - BARRELTARGET: this square contains a barrel _on_ a target.
268 * - WALL: this square is a wall.
270 * - PLAYER: this square contains the player.
272 * - PLAYERTARGET: this square contains the player on a target.
274 * We begin with every square of the in state INITIAL, apart from a
275 * solid ring of WALLs around the edge. We randomly position the
276 * PLAYER somewhere. Thereafter our valid moves are:
278 * - to move the PLAYER in one direction _pulling_ a barrel after
279 * us. For this to work, we must have SPACE or INITIAL in the
280 * direction we're moving, and BARREL or BARRELTARGET in the
281 * direction we're moving away from. We leave SPACE or TARGET
282 * respectively in the vacated square.
284 * - to create a new barrel by transforming an INITIAL square into
287 * - to move the PLAYER freely through SPACE and TARGET squares,
288 * leaving SPACE or TARGET where it started.
290 * - to move the player through INITIAL squares, carving a tunnel
291 * of SPACEs as it goes.
293 * We try to avoid destroying INITIAL squares wherever possible (if
294 * there's a path to where we want to be using only SPACE, then we
295 * should always use that). At the end of generation, every square
296 * still in state INITIAL is one which was not required at any
297 * point during generation, which means we can randomly choose
298 * whether to make it SPACE or WALL.
300 * It's unclear as yet what the right strategy for wall placement
301 * should be. Too few WALLs will yield many alternative solutions
302 * to the puzzle, whereas too many might rule out so many
303 * possibilities that the intended solution becomes obvious.
306 static void sokoban_generate(int w, int h, unsigned char *grid, int moves,
307 int nethack, random_state *rs)
310 int ox, oy, nx, ny, score;
314 int *dist, *prev, *heap;
315 int x, y, px, py, i, j, d, heapsize, npulls;
317 pulls = snewn(w * h * 4, struct pull);
318 dist = snewn(w * h, int);
319 prev = snewn(w * h, int);
320 heap = snewn(w * h, int);
323 * Configure the initial grid.
325 for (y = 0; y < h; y++)
326 for (x = 0; x < w; x++)
327 grid[y*w+x] = (x == 0 || y == 0 || x == w-1 || y == h-1 ?
335 i = random_upto(rs, (w-2) * (h-2));
343 * Now loop around making random inverse Sokoban moves. In this
344 * loop we aim to make one actual barrel-pull per iteration,
345 * plus as many free moves as are necessary to get into
346 * position for that pull.
348 while (moves-- >= 0) {
350 * First enumerate all the viable barrel-pulls we can
351 * possibly make, counting two pulls of the same barrel in
352 * different directions as different. We also include pulls
353 * we can perform by creating a new barrel. Each pull is
354 * marked with the amount of violence it would have to do
358 for (y = 0; y < h; y++)
359 for (x = 0; x < w; x++)
360 for (d = 0; d < 4; d++) {
363 int nx = x + dx, ny = y + dy;
364 int npx = nx + dx, npy = ny + dy;
368 * The candidate move is to put the player at
369 * (nx,ny), and move him to (npx,npy), pulling
370 * a barrel at (x,y) to (nx,ny). So first we
371 * must check that all those squares are within
372 * the boundaries of the grid. For this it is
373 * sufficient to check npx,npy.
375 if (npx < 0 || npx >= w || npy < 0 || npy >= h)
379 * (x,y) must either be a barrel, or a square
380 * which we can convert into a barrel.
382 switch (grid[y*w+x]) {
383 case BARREL: case BARRELTARGET:
388 score += 10 /* new_barrel_score */;
399 * (nx,ny) must either be a space, or a square
400 * which we can convert into a space.
402 switch (grid[ny*w+nx]) {
403 case SPACE: case TARGET:
406 score += 3 /* new_space_score */;
413 * (npx,npy) must also either be a space, or a
414 * square which we can convert into a space.
416 switch (grid[npy*w+npx]) {
417 case SPACE: case TARGET:
420 score += 3 /* new_space_score */;
427 * That's sufficient to tag this as a possible
428 * pull right now. We still don't know if we
429 * can reach the required player position, but
430 * that's a job for the subsequent BFS phase to
433 pulls[npulls].ox = x;
434 pulls[npulls].oy = y;
435 pulls[npulls].nx = nx;
436 pulls[npulls].ny = ny;
437 pulls[npulls].score = score;
438 #ifdef GENERATION_DIAGNOSTICS
439 printf("found potential pull: (%d,%d)-(%d,%d) cost %d\n",
440 pulls[npulls].ox, pulls[npulls].oy,
441 pulls[npulls].nx, pulls[npulls].ny,
442 pulls[npulls].score);
446 #ifdef GENERATION_DIAGNOSTICS
447 printf("found %d potential pulls\n", npulls);
451 * If there are no pulls available at all, we give up.
453 * (FIXME: or perhaps backtrack?)
459 * Now we do a BFS from our current position, to find all
460 * the squares we can get the player into.
462 * This BFS is unusually tricky. We want to give a positive
463 * distance only to squares which we have to carve through
464 * INITIALs to get to, which means we can't just stick
465 * every square we reach on the end of our to-do list.
466 * Instead, we must maintain our list as a proper priority
469 for (i = 0; i < w*h; i++)
470 dist[i] = prev[i] = -1;
476 #define PARENT(n) ( ((n)-1)/2 )
477 #define LCHILD(n) ( 2*(n)+1 )
478 #define RCHILD(n) ( 2*(n)+2 )
479 #define SWAP(i,j) do { int swaptmp = (i); (i) = (j); (j) = swaptmp; } while (0)
481 while (heapsize > 0) {
483 * Pull the smallest element off the heap: it's at
484 * position 0. Move the arbitrary element from the very
485 * end of the heap into position 0.
491 heap[0] = heap[heapsize];
494 * Now repeatedly move that arbitrary element down the
495 * heap by swapping it with the more suitable of its
506 break; /* we've hit bottom */
508 if (rc >= heapsize) {
510 * Special case: there is only one child to
513 if (dist[heap[i]] > dist[heap[lc]])
514 SWAP(heap[i], heap[lc]);
516 /* _Now_ we've hit bottom. */
520 * The common case: there are two children and
521 * we must check them both.
523 if (dist[heap[i]] > dist[heap[lc]] ||
524 dist[heap[i]] > dist[heap[rc]]) {
526 * Pick the more appropriate child to swap with
527 * (i.e. the one which would want to be the
528 * parent if one were above the other - as one
531 if (dist[heap[lc]] > dist[heap[rc]]) {
532 SWAP(heap[i], heap[rc]);
535 SWAP(heap[i], heap[lc]);
539 /* This element is in the right place; we're done. */
546 * OK, that's given us (x,y) for this phase of the
547 * search. Now try all directions from here.
550 for (d = 0; d < 4; d++) {
553 int nx = x + dx, ny = y + dy;
554 if (nx < 0 || nx >= w || ny < 0 || ny >= h)
556 if (grid[ny*w+nx] != SPACE && grid[ny*w+nx] != TARGET &&
557 grid[ny*w+nx] != INITIAL)
559 if (dist[ny*w+nx] == -1) {
560 dist[ny*w+nx] = dist[y*w+x] + (grid[ny*w+nx] == INITIAL);
561 prev[ny*w+nx] = y*w+x;
564 * Now insert ny*w+nx at the end of the heap,
565 * and move it down to its appropriate resting
569 heap[heapsize++] = ny*w+nx;
572 * Swap element n with its parent repeatedly to
573 * preserve the heap property.
579 if (dist[heap[p]] > dist[heap[i]]) {
580 SWAP(heap[p], heap[i]);
594 #ifdef GENERATION_DIAGNOSTICS
595 printf("distance map:\n");
596 for (i = 0; i < h; i++) {
597 for (j = 0; j < w; j++) {
615 * Now we can go back through the `pulls' array, adjusting
616 * the score for each pull depending on how hard it is to
617 * reach its starting point, and also throwing out any
618 * whose starting points are genuinely unreachable even
619 * with the possibility of carving through INITIAL squares.
621 for (i = j = 0; i < npulls; i++) {
622 #ifdef GENERATION_DIAGNOSTICS
623 printf("potential pull (%d,%d)-(%d,%d)",
624 pulls[i].ox, pulls[i].oy,
625 pulls[i].nx, pulls[i].ny);
629 if (dist[y*w+x] < 0) {
630 #ifdef GENERATION_DIAGNOSTICS
631 printf(" unreachable\n");
633 continue; /* this pull isn't feasible at all */
636 * Another nasty special case we have to check is
637 * whether the initial barrel location (ox,oy) is
638 * on the path used to reach the square. This can
639 * occur if that square is in state INITIAL: the
640 * pull is initially considered valid on the basis
641 * that the INITIAL can become BARRELTARGET, and
642 * it's also considered reachable on the basis that
643 * INITIAL can be turned into SPACE, but it can't
646 * Fortunately, if (ox,oy) is on the path at all,
647 * it must be only one space from the end, so this
648 * is easy to spot and rule out.
650 if (prev[y*w+x] == pulls[i].oy*w+pulls[i].ox) {
651 #ifdef GENERATION_DIAGNOSTICS
652 printf(" goes through itself\n");
654 continue; /* this pull isn't feasible at all */
656 pulls[j] = pulls[i]; /* structure copy */
657 pulls[j].score += dist[y*w+x] * 3 /* new_space_score */;
658 #ifdef GENERATION_DIAGNOSTICS
659 printf(" reachable at distance %d (cost now %d)\n",
660 dist[y*w+x], pulls[j].score);
668 * Again, if there are no pulls available at all, we give
671 * (FIXME: or perhaps backtrack?)
677 * Now choose which pull to make. On the one hand we should
678 * prefer pulls which do less damage to the INITIAL squares
679 * (thus, ones for which we can already get into position
680 * via existing SPACEs, and for which the barrel already
681 * exists and doesn't have to be invented); on the other,
682 * we want to avoid _always_ preferring such pulls, on the
683 * grounds that that will lead to levels without very much
686 * When creating new barrels, we prefer creations which are
687 * next to existing TARGET squares.
689 * FIXME: for the moment I'll make this very simple indeed.
691 i = random_upto(rs, npulls);
694 * Actually make the pull, including carving a path to get
695 * to the site if necessary.
699 while (prev[y*w+x] >= 0) {
702 if (grid[y*w+x] == INITIAL)
709 px = 2*pulls[i].nx - pulls[i].ox;
710 py = 2*pulls[i].ny - pulls[i].oy;
711 if (grid[py*w+px] == INITIAL)
712 grid[py*w+px] = SPACE;
713 if (grid[pulls[i].ny*w+pulls[i].nx] == TARGET)
714 grid[pulls[i].ny*w+pulls[i].nx] = BARRELTARGET;
716 grid[pulls[i].ny*w+pulls[i].nx] = BARREL;
717 if (grid[pulls[i].oy*w+pulls[i].ox] == BARREL)
718 grid[pulls[i].oy*w+pulls[i].ox] = SPACE;
719 else if (grid[pulls[i].oy*w+pulls[i].ox] != DEEP_PIT)
720 grid[pulls[i].oy*w+pulls[i].ox] = TARGET;
728 if (grid[py*w+px] == TARGET)
729 grid[py*w+px] = PLAYERTARGET;
731 grid[py*w+px] = PLAYER;
734 static char *new_game_desc(const game_params *params, random_state *rs,
735 char **aux, int interactive)
737 int w = params->w, h = params->h;
739 int desclen, descpos, descsize, prev, count;
744 * FIXME: perhaps some more interesting means of choosing how
747 grid = snewn(w*h, unsigned char);
748 sokoban_generate(w, h, grid, w*h, FALSE, rs);
750 desclen = descpos = descsize = 0;
754 for (i = 0; i < w*h; i++) {
755 if (descsize < desclen + 40) {
756 descsize = desclen + 100;
757 desc = sresize(desc, descsize, char);
758 desc[desclen] = '\0';
762 j = 'w'; /* FIXME: make some of these 's'? */
800 desclen = descpos + sprintf(desc+descpos, "%d", count);
809 static char *validate_desc(const game_params *params, const char *desc)
811 int w = params->w, h = params->h;
818 if (*desc && isdigit((unsigned char)*desc)) {
820 while (*desc && isdigit((unsigned char)*desc)) desc++;
825 if (c == PLAYER || c == PLAYERTARGET)
827 else if (c == INITIAL || c == SPACE || c == WALL || c == TARGET ||
828 c == PIT || c == DEEP_PIT || IS_BARREL(c))
831 return "Invalid character in game description";
835 return "Too much data in game description";
837 return "Too little data in game description";
839 return "No starting player position specified";
841 return "More than one starting player position specified";
846 static game_state *new_game(midend *me, const game_params *params,
849 int w = params->w, h = params->h;
850 game_state *state = snew(game_state);
853 state->p = *params; /* structure copy */
854 state->grid = snewn(w*h, unsigned char);
855 state->px = state->py = -1;
856 state->completed = FALSE;
863 if (*desc && isdigit((unsigned char)*desc)) {
865 while (*desc && isdigit((unsigned char)*desc)) desc++;
868 if (c == PLAYER || c == PLAYERTARGET) {
871 c = IS_ON_TARGET(c) ? TARGET : SPACE;
875 state->grid[i++] = c;
879 assert(state->px != -1 && state->py != -1);
884 static game_state *dup_game(const game_state *state)
886 int w = state->p.w, h = state->p.h;
887 game_state *ret = snew(game_state);
889 ret->p = state->p; /* structure copy */
890 ret->grid = snewn(w*h, unsigned char);
891 memcpy(ret->grid, state->grid, w*h);
894 ret->completed = state->completed;
899 static void free_game(game_state *state)
905 static char *solve_game(const game_state *state, const game_state *currstate,
906 const char *aux, char **error)
911 static int game_can_format_as_text_now(const game_params *params)
916 static char *game_text_format(const game_state *state)
921 static game_ui *new_ui(const game_state *state)
926 static void free_ui(game_ui *ui)
930 static char *encode_ui(const game_ui *ui)
935 static void decode_ui(game_ui *ui, const char *encoding)
939 static void game_changed_state(game_ui *ui, const game_state *oldstate,
940 const game_state *newstate)
944 struct game_drawstate {
948 unsigned short *grid;
951 #define PREFERRED_TILESIZE 32
952 #define TILESIZE (ds->tilesize)
953 #define BORDER (TILESIZE)
954 #define HIGHLIGHT_WIDTH (TILESIZE / 10)
955 #define COORD(x) ( (x) * TILESIZE + BORDER )
956 #define FROMCOORD(x) ( ((x) - BORDER + TILESIZE) / TILESIZE - 1 )
959 * I'm going to need to do most of the move-type analysis in both
960 * interpret_move and execute_move, so I'll abstract it out into a
961 * subfunction. move_type() returns -1 for an illegal move, 0 for a
962 * movement, and 1 for a push.
964 int move_type(game_state *state, int dx, int dy)
966 int w = state->p.w, h = state->p.h;
967 int px = state->px, py = state->py;
968 int nx, ny, nbx, nby;
970 assert(dx >= -1 && dx <= +1);
971 assert(dy >= -1 && dy <= +1);
978 * Disallow any move that goes off the grid.
980 if (nx < 0 || nx >= w || ny < 0 || ny >= h)
984 * Examine the target square of the move to see whether it's a
985 * space, a barrel, or a wall.
988 if (state->grid[ny*w+nx] == WALL ||
989 state->grid[ny*w+nx] == PIT ||
990 state->grid[ny*w+nx] == DEEP_PIT)
991 return -1; /* this one's easy; just disallow it */
993 if (IS_BARREL(state->grid[ny*w+nx])) {
995 * This is a push move. For a start, that means it must not
1002 * Now find the location of the third square involved in
1003 * the push, and stop if it's off the edge.
1007 if (nbx < 0 || nbx >= w || nby < 0 || nby >= h)
1011 * That third square must be able to accept a barrel.
1013 if (state->grid[nby*w+nbx] == SPACE ||
1014 state->grid[nby*w+nbx] == TARGET ||
1015 state->grid[nby*w+nbx] == PIT ||
1016 state->grid[nby*w+nbx] == DEEP_PIT) {
1018 * The push is valid.
1026 * This is just an ordinary move. We've already checked the
1027 * target square, so the only thing left to check is that a
1028 * diagonal move has a space on one side to have notionally
1032 state->grid[(py+dy)*w+px] != SPACE &&
1033 state->grid[(py+dy)*w+px] != TARGET &&
1034 state->grid[py*w+(px+dx)] != SPACE &&
1035 state->grid[py*w+(px+dx)] != TARGET)
1039 * Otherwise, the move is valid.
1045 static char *interpret_move(const game_state *state, game_ui *ui,
1046 const game_drawstate *ds,
1047 int x, int y, int button)
1053 * Diagonal movement is supported as it is in NetHack: it's
1054 * for movement only (never pushing), and one of the two
1055 * squares adjacent to both the source and destination
1056 * squares must be free to move through. In other words, it
1057 * is only a shorthand for two orthogonal moves and cannot
1058 * change the nature of the actual puzzle game.
1060 if (button == CURSOR_UP || button == (MOD_NUM_KEYPAD | '8'))
1062 else if (button == CURSOR_DOWN || button == (MOD_NUM_KEYPAD | '2'))
1064 else if (button == CURSOR_LEFT || button == (MOD_NUM_KEYPAD | '4'))
1066 else if (button == CURSOR_RIGHT || button == (MOD_NUM_KEYPAD | '6'))
1068 else if (button == (MOD_NUM_KEYPAD | '7'))
1070 else if (button == (MOD_NUM_KEYPAD | '9'))
1072 else if (button == (MOD_NUM_KEYPAD | '1'))
1074 else if (button == (MOD_NUM_KEYPAD | '3'))
1076 else if (button == LEFT_BUTTON)
1078 if(x < COORD(state->px))
1080 else if (x > COORD(state->px + 1))
1082 if(y < COORD(state->py))
1084 else if (y > COORD(state->py + 1))
1090 if((dx == 0) && (dy == 0))
1093 if (move_type(state, dx, dy) < 0)
1096 move = snewn(2, char);
1098 move[0] = '5' - 3*dy + dx;
1102 static game_state *execute_move(const game_state *state, const char *move)
1104 int w = state->p.w, h = state->p.h;
1105 int px = state->px, py = state->py;
1106 int dx, dy, nx, ny, nbx, nby, type, m, i, freebarrels, freetargets;
1109 if (*move < '1' || *move == '5' || *move > '9' || move[1])
1110 return NULL; /* invalid move string */
1113 dx = (m + 2) % 3 - 1;
1114 dy = 2 - (m + 2) / 3;
1115 type = move_type(state, dx, dy);
1119 ret = dup_game(state);
1132 b = ret->grid[ny*w+nx];
1133 if (IS_ON_TARGET(b)) {
1134 ret->grid[ny*w+nx] = TARGET;
1137 ret->grid[ny*w+nx] = SPACE;
1139 if (ret->grid[nby*w+nbx] == PIT)
1140 ret->grid[nby*w+nbx] = SPACE;
1141 else if (ret->grid[nby*w+nbx] == DEEP_PIT)
1142 /* do nothing - the pit eats the barrel and remains there */;
1143 else if (ret->grid[nby*w+nbx] == TARGET)
1144 ret->grid[nby*w+nbx] = TARGETISE(b);
1146 ret->grid[nby*w+nbx] = b;
1153 * Check for completion. This is surprisingly complicated,
1154 * given the presence of pits and deep pits, and also the fact
1155 * that some Sokoban levels with pits have fewer pits than
1156 * barrels (due to providing spares, e.g. NetHack's). I think
1157 * the completion condition in fact must be that the game
1158 * cannot become any _more_ complete. That is, _either_ there
1159 * are no remaining barrels not on targets, _or_ there is a
1160 * good reason why any such barrels cannot be placed. The only
1161 * available good reason is that there are no remaining pits,
1162 * no free target squares, and no deep pits at all.
1164 if (!ret->completed) {
1165 freebarrels = FALSE;
1166 freetargets = FALSE;
1167 for (i = 0; i < w*h; i++) {
1168 int v = ret->grid[i];
1170 if (IS_BARREL(v) && !IS_ON_TARGET(v))
1172 if (v == DEEP_PIT || v == PIT ||
1173 (!IS_BARREL(v) && IS_ON_TARGET(v)))
1177 if (!freebarrels || !freetargets)
1178 ret->completed = TRUE;
1184 /* ----------------------------------------------------------------------
1188 static void game_compute_size(const game_params *params, int tilesize,
1191 /* Ick: fake up `ds->tilesize' for macro expansion purposes */
1192 struct { int tilesize; } ads, *ds = &ads;
1193 ads.tilesize = tilesize;
1195 *x = 2 * BORDER + 1 + params->w * TILESIZE;
1196 *y = 2 * BORDER + 1 + params->h * TILESIZE;
1199 static void game_set_size(drawing *dr, game_drawstate *ds,
1200 const game_params *params, int tilesize)
1202 ds->tilesize = tilesize;
1205 static float *game_colours(frontend *fe, int *ncolours)
1207 float *ret = snewn(3 * NCOLOURS, float);
1210 game_mkhighlight(fe, ret, COL_BACKGROUND, COL_HIGHLIGHT, COL_LOWLIGHT);
1212 ret[COL_OUTLINE * 3 + 0] = 0.0F;
1213 ret[COL_OUTLINE * 3 + 1] = 0.0F;
1214 ret[COL_OUTLINE * 3 + 2] = 0.0F;
1216 ret[COL_PLAYER * 3 + 0] = 0.0F;
1217 ret[COL_PLAYER * 3 + 1] = 1.0F;
1218 ret[COL_PLAYER * 3 + 2] = 0.0F;
1220 ret[COL_BARREL * 3 + 0] = 0.6F;
1221 ret[COL_BARREL * 3 + 1] = 0.3F;
1222 ret[COL_BARREL * 3 + 2] = 0.0F;
1224 ret[COL_TARGET * 3 + 0] = ret[COL_LOWLIGHT * 3 + 0];
1225 ret[COL_TARGET * 3 + 1] = ret[COL_LOWLIGHT * 3 + 1];
1226 ret[COL_TARGET * 3 + 2] = ret[COL_LOWLIGHT * 3 + 2];
1228 ret[COL_PIT * 3 + 0] = ret[COL_LOWLIGHT * 3 + 0] / 2;
1229 ret[COL_PIT * 3 + 1] = ret[COL_LOWLIGHT * 3 + 1] / 2;
1230 ret[COL_PIT * 3 + 2] = ret[COL_LOWLIGHT * 3 + 2] / 2;
1232 ret[COL_DEEP_PIT * 3 + 0] = 0.0F;
1233 ret[COL_DEEP_PIT * 3 + 1] = 0.0F;
1234 ret[COL_DEEP_PIT * 3 + 2] = 0.0F;
1236 ret[COL_TEXT * 3 + 0] = 1.0F;
1237 ret[COL_TEXT * 3 + 1] = 1.0F;
1238 ret[COL_TEXT * 3 + 2] = 1.0F;
1240 ret[COL_GRID * 3 + 0] = ret[COL_LOWLIGHT * 3 + 0];
1241 ret[COL_GRID * 3 + 1] = ret[COL_LOWLIGHT * 3 + 1];
1242 ret[COL_GRID * 3 + 2] = ret[COL_LOWLIGHT * 3 + 2];
1244 ret[COL_OUTLINE * 3 + 0] = 0.0F;
1245 ret[COL_OUTLINE * 3 + 1] = 0.0F;
1246 ret[COL_OUTLINE * 3 + 2] = 0.0F;
1248 for (i = 0; i < 3; i++) {
1249 ret[COL_WALL * 3 + i] = (3 * ret[COL_BACKGROUND * 3 + i] +
1250 1 * ret[COL_HIGHLIGHT * 3 + i]) / 4;
1253 *ncolours = NCOLOURS;
1257 static game_drawstate *game_new_drawstate(drawing *dr, const game_state *state)
1259 int w = state->p.w, h = state->p.h;
1260 struct game_drawstate *ds = snew(struct game_drawstate);
1264 ds->p = state->p; /* structure copy */
1265 ds->grid = snewn(w*h, unsigned short);
1266 for (i = 0; i < w*h; i++)
1267 ds->grid[i] = INVALID;
1268 ds->started = FALSE;
1273 static void game_free_drawstate(drawing *dr, game_drawstate *ds)
1279 static void draw_tile(drawing *dr, game_drawstate *ds, int x, int y, int v)
1281 int tx = COORD(x), ty = COORD(y);
1282 int bg = (v & 0x100 ? COL_HIGHLIGHT : COL_BACKGROUND);
1286 clip(dr, tx+1, ty+1, TILESIZE-1, TILESIZE-1);
1287 draw_rect(dr, tx+1, ty+1, TILESIZE-1, TILESIZE-1, bg);
1292 coords[0] = tx + TILESIZE;
1293 coords[1] = ty + TILESIZE;
1294 coords[2] = tx + TILESIZE;
1297 coords[5] = ty + TILESIZE;
1298 draw_polygon(dr, coords, 3, COL_LOWLIGHT, COL_LOWLIGHT);
1302 draw_polygon(dr, coords, 3, COL_HIGHLIGHT, COL_HIGHLIGHT);
1304 draw_rect(dr, tx + 1 + HIGHLIGHT_WIDTH, ty + 1 + HIGHLIGHT_WIDTH,
1305 TILESIZE - 2*HIGHLIGHT_WIDTH,
1306 TILESIZE - 2*HIGHLIGHT_WIDTH, COL_WALL);
1307 } else if (v == PIT) {
1308 draw_circle(dr, tx + TILESIZE/2, ty + TILESIZE/2,
1309 TILESIZE*3/7, COL_PIT, COL_OUTLINE);
1310 } else if (v == DEEP_PIT) {
1311 draw_circle(dr, tx + TILESIZE/2, ty + TILESIZE/2,
1312 TILESIZE*3/7, COL_DEEP_PIT, COL_OUTLINE);
1314 if (IS_ON_TARGET(v)) {
1315 draw_circle(dr, tx + TILESIZE/2, ty + TILESIZE/2,
1316 TILESIZE*3/7, COL_TARGET, COL_OUTLINE);
1319 draw_circle(dr, tx + TILESIZE/2, ty + TILESIZE/2,
1320 TILESIZE/3, COL_PLAYER, COL_OUTLINE);
1321 } else if (IS_BARREL(v)) {
1324 draw_circle(dr, tx + TILESIZE/2, ty + TILESIZE/2,
1325 TILESIZE/3, COL_BARREL, COL_OUTLINE);
1327 str[0] = BARREL_LABEL(v);
1329 draw_text(dr, tx + TILESIZE/2, ty + TILESIZE/2,
1330 FONT_VARIABLE, TILESIZE/2,
1331 ALIGN_VCENTRE | ALIGN_HCENTRE, COL_TEXT, str);
1337 draw_update(dr, tx, ty, TILESIZE, TILESIZE);
1340 static void game_redraw(drawing *dr, game_drawstate *ds,
1341 const game_state *oldstate, const game_state *state,
1342 int dir, const game_ui *ui,
1343 float animtime, float flashtime)
1345 int w = state->p.w, h = state->p.h /*, wh = w*h */;
1350 !((int)(flashtime * 3 / FLASH_LENGTH) % 2))
1356 * Initialise a fresh drawstate.
1362 * Blank out the window initially.
1364 game_compute_size(&ds->p, TILESIZE, &wid, &ht);
1365 draw_rect(dr, 0, 0, wid, ht, COL_BACKGROUND);
1366 draw_update(dr, 0, 0, wid, ht);
1369 * Draw the grid lines.
1371 for (y = 0; y <= h; y++)
1372 draw_line(dr, COORD(0), COORD(y), COORD(w), COORD(y),
1374 for (x = 0; x <= w; x++)
1375 draw_line(dr, COORD(x), COORD(0), COORD(x), COORD(h),
1382 * Draw the grid contents.
1384 for (y = 0; y < h; y++)
1385 for (x = 0; x < w; x++) {
1386 int v = state->grid[y*w+x];
1387 if (y == state->py && x == state->px) {
1398 if (ds->grid[y*w+x] != v) {
1399 draw_tile(dr, ds, x, y, v);
1400 ds->grid[y*w+x] = v;
1406 static float game_anim_length(const game_state *oldstate,
1407 const game_state *newstate, int dir, game_ui *ui)
1412 static float game_flash_length(const game_state *oldstate,
1413 const game_state *newstate, int dir, game_ui *ui)
1415 if (!oldstate->completed && newstate->completed)
1416 return FLASH_LENGTH;
1421 static int game_status(const game_state *state)
1423 return state->completed ? +1 : 0;
1426 static int game_timing_state(const game_state *state, game_ui *ui)
1431 static void game_print_size(const game_params *params, float *x, float *y)
1435 static void game_print(drawing *dr, const game_state *state, int tilesize)
1440 #define thegame sokoban
1443 const struct game thegame = {
1444 "Sokoban", NULL, NULL,
1451 TRUE, game_configure, custom_params,
1459 FALSE, game_can_format_as_text_now, game_text_format,
1467 PREFERRED_TILESIZE, game_compute_size, game_set_size,
1470 game_free_drawstate,
1475 FALSE, FALSE, game_print_size, game_print,
1476 FALSE, /* wants_statusbar */
1477 FALSE, game_timing_state,