2 * slide.c: Implementation of the block-sliding puzzle `Klotski'.
8 * - Improve the generator.
9 * * actually, we seem to be mostly sensible already now. I
10 * want more choice over the type of main block and location
11 * of the exit/target, and I think I probably ought to give
12 * up on compactness and just bite the bullet and have the
13 * target area right outside the main wall, but mostly I
15 * * the move limit tends to make the game _slower_ to
16 * generate, which is odd. Perhaps investigate why.
18 * - Improve the graphics.
19 * * All the colours are a bit wishy-washy. _Some_ dark
20 * colours would surely not be excessive? Probably darken
21 * the tiles, the walls and the main block, and leave the
23 * * The cattle grid effect is still disgusting. Think of
24 * something completely different.
25 * * The highlight for next-piece-to-move in the solver is
26 * excessive, and the shadow blends in too well with the
27 * piece lowlights. Adjust both.
41 * The implementation of this game revolves around the insight
42 * which makes an exhaustive-search solver feasible: although
43 * there are many blocks which can be rearranged in many ways, any
44 * two blocks of the same shape are _indistinguishable_ and hence
45 * the number of _distinct_ board layouts is generally much
46 * smaller. So we adopt a representation for board layouts which
47 * is inherently canonical, i.e. there are no two distinct
48 * representations which encode indistinguishable layouts.
50 * The way we do this is to encode each square of the board, in
51 * the normal left-to-right top-to-bottom order, as being one of
52 * the following things:
53 * - the first square (in the given order) of a block (`anchor')
54 * - special case of the above: the anchor for the _main_ block
55 * (i.e. the one which the aim of the game is to get to the
57 * - a subsequent square of a block whose previous square was N
59 * - an impassable wall
61 * (We also separately store data about which board positions are
62 * forcefields only passable by the main block. We can't encode
63 * that in the main board data, because then the main block would
64 * destroy forcefields as it went over them.)
66 * Hence, for example, a 2x2 square block would be encoded as
67 * ANCHOR, followed by DIST(1), and w-2 squares later on there
68 * would be DIST(w-1) followed by DIST(1). So if you start at the
69 * last of those squares, the DIST numbers give you a linked list
70 * pointing back through all the other squares in the same block.
72 * So the solver simply does a bfs over all reachable positions,
73 * encoding them in this format and storing them in a tree234 to
74 * ensure it doesn't ever revisit an already-analysed position.
79 * The colours are arranged here so that every base colour is
80 * directly followed by its highlight colour and then its
81 * lowlight colour. Do not break this, or draw_tile() will get
88 COL_DRAGGING_HIGHLIGHT,
89 COL_DRAGGING_LOWLIGHT,
94 COL_MAIN_DRAGGING_HIGHLIGHT,
95 COL_MAIN_DRAGGING_LOWLIGHT,
103 * Board layout is a simple array of bytes. Each byte holds:
105 #define ANCHOR 255 /* top-left-most square of some piece */
106 #define MAINANCHOR 254 /* anchor of _main_ piece */
107 #define EMPTY 253 /* empty square */
108 #define WALL 252 /* immovable wall */
110 /* all other values indicate distance back to previous square of same block */
111 #define ISDIST(x) ( (unsigned char)((x)-1) <= MAXDIST-1 )
113 #define ISANCHOR(x) ( (x)==ANCHOR || (x)==MAINANCHOR )
114 #define ISBLOCK(x) ( ISANCHOR(x) || ISDIST(x) )
117 * MAXDIST is the largest DIST value we can encode. This must
118 * therefore also be the maximum puzzle width in theory (although
119 * solver running time will dictate a much smaller limit in
122 #define MAXWID MAXDIST
129 struct game_immutable_state {
131 unsigned char *forcefield;
134 struct game_solution {
136 int *moves; /* just like from solve_board() */
142 unsigned char *board;
143 int tx, ty; /* target coords for MAINANCHOR */
144 int minmoves; /* for display only */
145 int lastmoved, lastmoved_pos; /* for move counting */
149 struct game_immutable_state *imm;
150 struct game_solution *soln;
154 static game_params *default_params(void)
156 game_params *ret = snew(game_params);
165 static const struct game_params slide_presets[] = {
171 static int game_fetch_preset(int i, char **name, game_params **params)
176 if (i < 0 || i >= lenof(slide_presets))
179 ret = snew(game_params);
180 *ret = slide_presets[i];
182 sprintf(str, "%dx%d", ret->w, ret->h);
183 if (ret->maxmoves >= 0)
184 sprintf(str + strlen(str), ", max %d moves", ret->maxmoves);
186 sprintf(str + strlen(str), ", no move limit");
193 static void free_params(game_params *params)
198 static game_params *dup_params(game_params *params)
200 game_params *ret = snew(game_params);
201 *ret = *params; /* structure copy */
205 static void decode_params(game_params *params, char const *string)
207 params->w = params->h = atoi(string);
208 while (*string && isdigit((unsigned char)*string)) string++;
209 if (*string == 'x') {
211 params->h = atoi(string);
212 while (*string && isdigit((unsigned char)*string)) string++;
214 if (*string == 'm') {
216 params->maxmoves = atoi(string);
217 while (*string && isdigit((unsigned char)*string)) string++;
218 } else if (*string == 'u') {
220 params->maxmoves = -1;
224 static char *encode_params(game_params *params, int full)
228 sprintf(data, "%dx%d", params->w, params->h);
229 if (params->maxmoves >= 0)
230 sprintf(data + strlen(data), "m%d", params->maxmoves);
232 sprintf(data + strlen(data), "u");
237 static config_item *game_configure(game_params *params)
242 ret = snewn(4, config_item);
244 ret[0].name = "Width";
245 ret[0].type = C_STRING;
246 sprintf(buf, "%d", params->w);
247 ret[0].sval = dupstr(buf);
250 ret[1].name = "Height";
251 ret[1].type = C_STRING;
252 sprintf(buf, "%d", params->h);
253 ret[1].sval = dupstr(buf);
256 ret[2].name = "Solution length limit";
257 ret[2].type = C_STRING;
258 sprintf(buf, "%d", params->maxmoves);
259 ret[2].sval = dupstr(buf);
270 static game_params *custom_params(config_item *cfg)
272 game_params *ret = snew(game_params);
274 ret->w = atoi(cfg[0].sval);
275 ret->h = atoi(cfg[1].sval);
276 ret->maxmoves = atoi(cfg[2].sval);
281 static char *validate_params(game_params *params, int full)
283 if (params->w > MAXWID)
284 return "Width must be at most " STR(MAXWID);
287 return "Width must be at least 5";
289 return "Height must be at least 4";
294 static char *board_text_format(int w, int h, unsigned char *data,
295 unsigned char *forcefield)
298 int *dsf = snew_dsf(wh);
300 int retpos, retlen = (w*2+2)*(h*2+1)+1;
301 char *ret = snewn(retlen, char);
303 for (i = 0; i < wh; i++)
305 dsf_merge(dsf, i - data[i], i);
307 for (y = 0; y < 2*h+1; y++) {
308 for (x = 0; x < 2*w+1; x++) {
310 int i = (y/2)*w+(x/2);
312 #define dtype(i) (ISBLOCK(data[i]) ? \
313 dsf_canonify(dsf, i) : data[i])
314 #define dchar(t) ((t)==EMPTY ? ' ' : (t)==WALL ? '#' : \
315 data[t] == MAINANCHOR ? '*' : '%')
317 if (y % 2 && x % 2) {
320 } else if (y % 2 && !(x % 2)) {
321 int j1 = (x > 0 ? dtype(i-1) : -1);
322 int j2 = (x < 2*w ? dtype(i) : -1);
327 } else if (!(y % 2) && (x % 2)) {
328 int j1 = (y > 0 ? dtype(i-w) : -1);
329 int j2 = (y < 2*h ? dtype(i) : -1);
335 int j1 = (x > 0 && y > 0 ? dtype(i-w-1) : -1);
336 int j2 = (x > 0 && y < 2*h ? dtype(i-1) : -1);
337 int j3 = (x < 2*w && y > 0 ? dtype(i-w) : -1);
338 int j4 = (x < 2*w && y < 2*h ? dtype(i) : -1);
339 if (j1 == j2 && j2 == j3 && j3 == j4)
341 else if (j1 == j2 && j3 == j4)
343 else if (j1 == j3 && j2 == j4)
349 assert(retpos < retlen);
352 assert(retpos < retlen);
353 ret[retpos++] = '\n';
355 assert(retpos < retlen);
356 ret[retpos++] = '\0';
357 assert(retpos == retlen);
362 /* ----------------------------------------------------------------------
367 * During solver execution, the set of visited board positions is
368 * stored as a tree234 of the following structures. `w', `h' and
369 * `data' are obvious in meaning; `dist' represents the minimum
370 * distance to reach this position from the starting point.
372 * `prev' links each board to the board position from which it was
373 * most efficiently derived.
382 static int boardcmp(void *av, void *bv)
384 struct board *a = (struct board *)av;
385 struct board *b = (struct board *)bv;
386 return memcmp(a->data, b->data, a->w * a->h);
389 static struct board *newboard(int w, int h, unsigned char *data)
391 struct board *b = malloc(sizeof(struct board) + w*h);
392 b->data = (unsigned char *)b + sizeof(struct board);
393 memcpy(b->data, data, w*h);
402 * The actual solver. Given a board, attempt to find the minimum
403 * length of move sequence which moves MAINANCHOR to (tx,ty), or
404 * -1 if no solution exists. Returns that minimum length.
406 * Also, if `moveout' is provided, writes out the moves in the
407 * form of a sequence of pairs of integers indicating the source
408 * and destination points of the anchor of the moved piece in each
409 * move. Exactly twice as many integers are written as the number
410 * returned from solve_board(), and `moveout' receives an int *
411 * which is a pointer to a dynamically allocated array.
413 static int solve_board(int w, int h, unsigned char *board,
414 unsigned char *forcefield, int tx, int ty,
415 int movelimit, int **moveout)
418 struct board *b, *b2, *b3;
419 int *next, *anchors, *which;
420 int *movereached, *movequeue, mqhead, mqtail;
421 tree234 *sorted, *queue;
426 #ifdef SOLVER_DIAGNOSTICS
428 char *t = board_text_format(w, h, board);
429 for (i = 0; i < h; i++) {
430 for (j = 0; j < w; j++) {
431 int c = board[i*w+j];
434 else if (c == MAINANCHOR)
436 else if (c == ANCHOR)
446 printf("Starting solver for:\n%s\n", t);
451 sorted = newtree234(boardcmp);
452 queue = newtree234(NULL);
454 b = newboard(w, h, board);
457 addpos234(queue, b, 0);
460 next = snewn(wh, int);
461 anchors = snewn(wh, int);
462 which = snewn(wh, int);
463 movereached = snewn(wh, int);
464 movequeue = snewn(wh, int);
467 while ((b = delpos234(queue, 0)) != NULL) {
469 if (movelimit >= 0 && b->dist >= movelimit) {
471 * The problem is not soluble in under `movelimit'
472 * moves, so we can quit right now.
477 if (b->dist != lastdist) {
478 #ifdef SOLVER_DIAGNOSTICS
479 printf("dist %d (%d)\n", b->dist, count234(sorted));
484 * Find all the anchors and form a linked list of the
485 * squares within each block.
487 for (i = 0; i < wh; i++) {
491 if (ISANCHOR(b->data[i])) {
494 } else if (ISDIST(b->data[i])) {
502 * For each anchor, do an array-based BFS to find all the
503 * places we can slide it to.
505 for (i = 0; i < wh; i++) {
510 for (j = 0; j < wh; j++)
511 movereached[j] = FALSE;
512 movequeue[mqtail++] = i;
513 while (mqhead < mqtail) {
514 int pos = movequeue[mqhead++];
517 * Try to move in each direction from here.
519 for (dir = 0; dir < 4; dir++) {
520 int dx = (dir == 0 ? -1 : dir == 1 ? +1 : 0);
521 int dy = (dir == 2 ? -1 : dir == 3 ? +1 : 0);
522 int offset = dy*w + dx;
523 int newpos = pos + offset;
527 * For each square involved in this block,
528 * check to see if the square d spaces away
529 * from it is either empty or part of the same
532 for (j = i; j >= 0; j = next[j]) {
533 int jy = (pos+j-i) / w + dy, jx = (pos+j-i) % w + dx;
534 if (jy >= 0 && jy < h && jx >= 0 && jx < w &&
535 ((b->data[j+d] == EMPTY || which[j+d] == i) &&
536 (b->data[i] == MAINANCHOR || !forcefield[j+d])))
542 continue; /* this direction wasn't feasible */
545 * If we've already tried moving this piece
548 if (movereached[newpos])
550 movereached[newpos] = TRUE;
551 movequeue[mqtail++] = newpos;
554 * We have a viable move. Make it.
556 b2 = newboard(w, h, b->data);
557 for (j = i; j >= 0; j = next[j])
559 for (j = i; j >= 0; j = next[j])
560 b2->data[j+d] = b->data[j];
562 b3 = add234(sorted, b2);
564 sfree(b2); /* we already got one */
566 b2->dist = b->dist + 1;
568 addpos234(queue, b2, qlen++);
569 if (b2->data[ty*w+tx] == MAINANCHOR)
570 goto done; /* search completed! */
584 * Now b2 represents the solved position. Backtrack to
585 * output the solution.
587 *moveout = snewn(ret * 2, int);
591 int from = -1, to = -1;
596 * Scan b and b2 to find out which piece has
599 for (i = 0; i < wh; i++) {
600 if (ISANCHOR(b->data[i]) && !ISANCHOR(b2->data[i])) {
603 } else if (!ISANCHOR(b->data[i]) && ISANCHOR(b2->data[i])){
609 assert(from >= 0 && to >= 0);
611 (*moveout)[--j] = to;
612 (*moveout)[--j] = from;
619 ret = -1; /* no solution */
626 while ((b = delpos234(sorted, 0)) != NULL)
639 /* ----------------------------------------------------------------------
640 * Random board generation.
643 static void generate_board(int w, int h, int *rtx, int *rty, int *minmoves,
644 random_state *rs, unsigned char **rboard,
645 unsigned char **rforcefield, int movelimit)
648 unsigned char *board, *board2, *forcefield;
649 unsigned char *tried_merge;
651 int *list, nlist, pos;
654 int moves = 0; /* placate optimiser */
657 * Set up a board and fill it with singletons, except for a
660 board = snewn(wh, unsigned char);
661 forcefield = snewn(wh, unsigned char);
662 board2 = snewn(wh, unsigned char);
663 memset(board, ANCHOR, wh);
664 memset(forcefield, FALSE, wh);
665 for (i = 0; i < w; i++)
666 board[i] = board[i+w*(h-1)] = WALL;
667 for (i = 0; i < h; i++)
668 board[i*w] = board[i*w+(w-1)] = WALL;
670 tried_merge = snewn(wh * wh, unsigned char);
671 memset(tried_merge, 0, wh*wh);
675 * Invent a main piece at one extreme. (FIXME: vary the
676 * extreme, and the piece.)
678 board[w+1] = MAINANCHOR;
679 board[w+2] = DIST(1);
680 board[w*2+1] = DIST(w-1);
681 board[w*2+2] = DIST(1);
684 * Invent a target position. (FIXME: vary this too.)
688 forcefield[ty*w+tx+1] = forcefield[(ty+1)*w+tx+1] = TRUE;
689 board[ty*w+tx+1] = board[(ty+1)*w+tx+1] = EMPTY;
692 * Gradually remove singletons until the game becomes soluble.
694 for (j = w; j-- > 0 ;)
695 for (i = h; i-- > 0 ;)
696 if (board[i*w+j] == ANCHOR) {
698 * See if the board is already soluble.
700 if ((moves = solve_board(w, h, board, forcefield,
701 tx, ty, movelimit, NULL)) >= 0)
705 * Otherwise, remove this piece.
707 board[i*w+j] = EMPTY;
709 assert(!"We shouldn't get here");
713 * Make a list of all the inter-block edges on the board.
715 list = snewn(wh*2, int);
717 for (i = 0; i+1 < w; i++)
718 for (j = 0; j < h; j++)
719 list[nlist++] = (j*w+i) * 2 + 0; /* edge to the right of j*w+i */
720 for (j = 0; j+1 < h; j++)
721 for (i = 0; i < w; i++)
722 list[nlist++] = (j*w+i) * 2 + 1; /* edge below j*w+i */
725 * Now go through that list in random order, trying to merge
726 * the blocks on each side of each edge.
728 shuffle(list, nlist, sizeof(*list), rs);
734 y1 = y2 = pos / (w*2);
735 x1 = x2 = (pos / 2) % w;
744 * Immediately abandon the attempt if we've already tried
745 * to merge the same pair of blocks along a different
748 c1 = dsf_canonify(dsf, p1);
749 c2 = dsf_canonify(dsf, p2);
750 if (tried_merge[c1 * wh + c2])
754 * In order to be mergeable, these two squares must each
755 * either be, or belong to, a non-main anchor, and their
756 * anchors must also be distinct.
758 if (!ISBLOCK(board[p1]) || !ISBLOCK(board[p2]))
760 while (ISDIST(board[p1]))
762 while (ISDIST(board[p2]))
764 if (board[p1] == MAINANCHOR || board[p2] == MAINANCHOR || p1 == p2)
768 * We can merge these blocks. Try it, and see if the
769 * puzzle remains soluble.
771 memcpy(board2, board, wh);
773 while (p1 < wh || p2 < wh) {
775 * p1 and p2 are the squares at the head of each block
776 * list. Pick the smaller one and put it on the output
783 assert(i - j <= MAXDIST);
784 board[i] = DIST(i - j);
789 * Now advance whichever list that came from.
794 } while (p1 < wh && board[p1] != DIST(p1-i));
798 } while (p2 < wh && board[p2] != DIST(p2-i));
801 j = solve_board(w, h, board, forcefield, tx, ty, movelimit, NULL);
804 * Didn't work. Revert the merge.
806 memcpy(board, board2, wh);
807 tried_merge[c1 * wh + c2] = tried_merge[c2 * wh + c1] = TRUE;
813 dsf_merge(dsf, c1, c2);
814 c = dsf_canonify(dsf, c1);
815 for (i = 0; i < wh; i++)
816 tried_merge[c*wh+i] = (tried_merge[c1*wh+i] |
817 tried_merge[c2*wh+i]);
818 for (i = 0; i < wh; i++)
819 tried_merge[i*wh+c] = (tried_merge[i*wh+c1] |
820 tried_merge[i*wh+c2]);
829 *rforcefield = forcefield;
833 /* ----------------------------------------------------------------------
834 * End of solver/generator code.
837 static char *new_game_desc(game_params *params, random_state *rs,
838 char **aux, int interactive)
840 int w = params->w, h = params->h, wh = w*h;
841 int tx, ty, minmoves;
842 unsigned char *board, *forcefield;
846 generate_board(params->w, params->h, &tx, &ty, &minmoves, rs,
847 &board, &forcefield, params->maxmoves);
848 #ifdef GENERATOR_DIAGNOSTICS
850 char *t = board_text_format(params->w, params->h, board);
857 * Encode as a game ID.
859 ret = snewn(wh * 6 + 40, char);
863 if (ISDIST(board[i])) {
864 p += sprintf(p, "d%d", board[i]);
868 int b = board[i], f = forcefield[i];
869 int c = (b == ANCHOR ? 'a' :
870 b == MAINANCHOR ? 'm' :
872 /* b == WALL ? */ 'w');
876 while (i < wh && board[i] == b && forcefield[i] == f)
879 p += sprintf(p, "%d", count);
882 p += sprintf(p, ",%d,%d,%d", tx, ty, minmoves);
883 ret = sresize(ret, p+1 - ret, char);
891 static char *validate_desc(game_params *params, char *desc)
893 int w = params->w, h = params->h, wh = w*h;
895 int mains = 0, mpos = -1;
896 int i, tx, ty, minmoves;
899 active = snewn(wh, int);
900 link = snewn(wh, int);
903 while (*desc && *desc != ',') {
905 ret = "Too much data in game description";
910 if (*desc == 'f' || *desc == 'F') {
913 ret = "Expected another character after 'f' in game "
919 if (*desc == 'd' || *desc == 'D') {
923 if (!isdigit((unsigned char)*desc)) {
924 ret = "Expected a number after 'd' in game description";
928 while (*desc && isdigit((unsigned char)*desc)) desc++;
930 if (dist <= 0 || dist > i) {
931 ret = "Out-of-range number after 'd' in game description";
935 if (!active[i - dist]) {
936 ret = "Invalid back-reference in game description";
943 active[link[i]] = FALSE;
949 if (!strchr("aAmMeEwW", c)) {
950 ret = "Invalid character in game description";
953 if (isdigit((unsigned char)*desc)) {
955 while (*desc && isdigit((unsigned char)*desc)) desc++;
957 if (i + count > wh) {
958 ret = "Too much data in game description";
961 while (count-- > 0) {
962 active[i] = (strchr("aAmM", c) != NULL);
964 if (strchr("mM", c) != NULL) {
973 ret = (mains == 0 ? "No main piece specified in game description" :
974 "More than one main piece specified in game description");
978 ret = "Not enough data in game description";
983 * Now read the target coordinates.
985 i = sscanf(desc, ",%d,%d,%d", &tx, &ty, &minmoves);
987 ret = "No target coordinates specified";
990 * (but minmoves is optional)
1002 static game_state *new_game(midend *me, game_params *params, char *desc)
1004 int w = params->w, h = params->h, wh = w*h;
1008 state = snew(game_state);
1011 state->board = snewn(wh, unsigned char);
1012 state->lastmoved = state->lastmoved_pos = -1;
1013 state->movecount = 0;
1014 state->imm = snew(struct game_immutable_state);
1015 state->imm->refcount = 1;
1016 state->imm->forcefield = snewn(wh, unsigned char);
1020 while (*desc && *desc != ',') {
1031 if (*desc == 'd' || *desc == 'D') {
1036 while (*desc && isdigit((unsigned char)*desc)) desc++;
1038 state->board[i] = DIST(dist);
1039 state->imm->forcefield[i] = f;
1046 if (isdigit((unsigned char)*desc)) {
1048 while (*desc && isdigit((unsigned char)*desc)) desc++;
1050 assert(i + count <= wh);
1052 c = (c == 'a' || c == 'A' ? ANCHOR :
1053 c == 'm' || c == 'M' ? MAINANCHOR :
1054 c == 'e' || c == 'E' ? EMPTY :
1055 /* c == 'w' || c == 'W' ? */ WALL);
1057 while (count-- > 0) {
1058 state->board[i] = c;
1059 state->imm->forcefield[i] = f;
1066 * Now read the target coordinates.
1068 state->tx = state->ty = 0;
1069 state->minmoves = -1;
1070 i = sscanf(desc, ",%d,%d,%d", &state->tx, &state->ty, &state->minmoves);
1072 if (state->board[state->ty*w+state->tx] == MAINANCHOR)
1073 state->completed = 0; /* already complete! */
1075 state->completed = -1;
1077 state->cheated = FALSE;
1079 state->soln_index = -1;
1084 static game_state *dup_game(game_state *state)
1086 int w = state->w, h = state->h, wh = w*h;
1087 game_state *ret = snew(game_state);
1091 ret->board = snewn(wh, unsigned char);
1092 memcpy(ret->board, state->board, wh);
1093 ret->tx = state->tx;
1094 ret->ty = state->ty;
1095 ret->minmoves = state->minmoves;
1096 ret->lastmoved = state->lastmoved;
1097 ret->lastmoved_pos = state->lastmoved_pos;
1098 ret->movecount = state->movecount;
1099 ret->completed = state->completed;
1100 ret->cheated = state->cheated;
1101 ret->imm = state->imm;
1102 ret->imm->refcount++;
1103 ret->soln = state->soln;
1104 ret->soln_index = state->soln_index;
1106 ret->soln->refcount++;
1111 static void free_game(game_state *state)
1113 if (--state->imm->refcount <= 0) {
1114 sfree(state->imm->forcefield);
1117 if (state->soln && --state->soln->refcount <= 0) {
1118 sfree(state->soln->moves);
1121 sfree(state->board);
1125 static char *solve_game(game_state *state, game_state *currstate,
1126 char *aux, char **error)
1134 * Run the solver and attempt to find the shortest solution
1135 * from the current position.
1137 nmoves = solve_board(state->w, state->h, state->board,
1138 state->imm->forcefield, state->tx, state->ty,
1142 *error = "Unable to find a solution to this puzzle";
1146 *error = "Puzzle is already solved";
1151 * Encode the resulting solution as a move string.
1153 ret = snewn(nmoves * 40, char);
1157 for (i = 0; i < nmoves; i++) {
1158 p += sprintf(p, "%c%d-%d", sep, moves[i*2], moves[i*2+1]);
1163 assert(p - ret < nmoves * 40);
1164 ret = sresize(ret, p+1 - ret, char);
1169 static int game_can_format_as_text_now(game_params *params)
1174 static char *game_text_format(game_state *state)
1176 return board_text_format(state->w, state->h, state->board,
1177 state->imm->forcefield);
1183 int drag_offset_x, drag_offset_y;
1185 unsigned char *reachable;
1186 int *bfs_queue; /* used as scratch in interpret_move */
1189 static game_ui *new_ui(game_state *state)
1191 int w = state->w, h = state->h, wh = w*h;
1192 game_ui *ui = snew(game_ui);
1194 ui->dragging = FALSE;
1195 ui->drag_anchor = ui->drag_currpos = -1;
1196 ui->drag_offset_x = ui->drag_offset_y = -1;
1197 ui->reachable = snewn(wh, unsigned char);
1198 memset(ui->reachable, 0, wh);
1199 ui->bfs_queue = snewn(wh, int);
1204 static void free_ui(game_ui *ui)
1206 sfree(ui->bfs_queue);
1207 sfree(ui->reachable);
1211 static char *encode_ui(game_ui *ui)
1216 static void decode_ui(game_ui *ui, char *encoding)
1220 static void game_changed_state(game_ui *ui, game_state *oldstate,
1221 game_state *newstate)
1225 #define PREFERRED_TILESIZE 32
1226 #define TILESIZE (ds->tilesize)
1227 #define BORDER (TILESIZE/2)
1228 #define COORD(x) ( (x) * TILESIZE + BORDER )
1229 #define FROMCOORD(x) ( ((x) - BORDER + TILESIZE) / TILESIZE - 1 )
1230 #define BORDER_WIDTH (1 + TILESIZE/20)
1231 #define HIGHLIGHT_WIDTH (1 + TILESIZE/16)
1233 #define FLASH_INTERVAL 0.10F
1234 #define FLASH_TIME 3*FLASH_INTERVAL
1236 struct game_drawstate {
1239 unsigned long *grid; /* what's currently displayed */
1243 static char *interpret_move(game_state *state, game_ui *ui, game_drawstate *ds,
1244 int x, int y, int button)
1246 int w = state->w, h = state->h, wh = w*h;
1250 if (button == LEFT_BUTTON) {
1254 if (tx < 0 || tx >= w || ty < 0 || ty >= h ||
1255 !ISBLOCK(state->board[ty*w+tx]))
1256 return NULL; /* this click has no effect */
1259 * User has clicked on a block. Find the block's anchor
1260 * and register that we've started dragging it.
1263 while (ISDIST(state->board[i]))
1264 i -= state->board[i];
1265 assert(i >= 0 && i < wh);
1267 ui->dragging = TRUE;
1268 ui->drag_anchor = i;
1269 ui->drag_offset_x = tx - (i % w);
1270 ui->drag_offset_y = ty - (i / w);
1271 ui->drag_currpos = i;
1274 * Now we immediately bfs out from the current location of
1275 * the anchor, to find all the places to which this block
1278 memset(ui->reachable, FALSE, wh);
1280 ui->reachable[i] = TRUE;
1281 ui->bfs_queue[qtail++] = i;
1282 for (j = i; j < wh; j++)
1283 if (state->board[j] == DIST(j - i))
1285 while (qhead < qtail) {
1286 int pos = ui->bfs_queue[qhead++];
1287 int x = pos % w, y = pos / w;
1290 for (dir = 0; dir < 4; dir++) {
1291 int dx = (dir == 0 ? -1 : dir == 1 ? +1 : 0);
1292 int dy = (dir == 2 ? -1 : dir == 3 ? +1 : 0);
1295 if (x + dx < 0 || x + dx >= w ||
1296 y + dy < 0 || y + dy >= h)
1299 newpos = pos + dy*w + dx;
1300 if (ui->reachable[newpos])
1301 continue; /* already done this one */
1304 * Now search the grid to see if the block we're
1305 * dragging could fit into this space.
1307 for (j = i; j >= 0; j = (ISDIST(state->board[j]) ?
1308 j - state->board[j] : -1)) {
1309 int jx = (j+pos-ui->drag_anchor) % w;
1310 int jy = (j+pos-ui->drag_anchor) / w;
1313 if (jx + dx < 0 || jx + dx >= w ||
1314 jy + dy < 0 || jy + dy >= h)
1315 break; /* this position isn't valid at all */
1317 j2 = (j+pos-ui->drag_anchor) + dy*w + dx;
1319 if (state->board[j2] == EMPTY &&
1320 (!state->imm->forcefield[j2] ||
1321 state->board[ui->drag_anchor] == MAINANCHOR))
1323 while (ISDIST(state->board[j2]))
1324 j2 -= state->board[j2];
1325 assert(j2 >= 0 && j2 < wh);
1326 if (j2 == ui->drag_anchor)
1334 * If we got to the end of that loop without
1335 * disqualifying this position, mark it as
1336 * reachable for this drag.
1338 ui->reachable[newpos] = TRUE;
1339 ui->bfs_queue[qtail++] = newpos;
1345 * And that's it. Update the display to reflect the start
1349 } else if (button == LEFT_DRAG && ui->dragging) {
1350 int dist, distlimit, dx, dy, s, px, py;
1355 tx -= ui->drag_offset_x;
1356 ty -= ui->drag_offset_y;
1359 * Now search outwards from (tx,ty), in order of Manhattan
1360 * distance, until we find a reachable square.
1363 distlimit = max(distlimit, h+ty);
1364 distlimit = max(distlimit, tx);
1365 distlimit = max(distlimit, ty);
1366 for (dist = 0; dist <= distlimit; dist++) {
1367 for (dx = -dist; dx <= dist; dx++)
1368 for (s = -1; s <= +1; s += 2) {
1369 dy = s * (dist - abs(dx));
1372 if (px >= 0 && px < w && py >= 0 && py < h &&
1373 ui->reachable[py*w+px]) {
1374 ui->drag_currpos = py*w+px;
1379 return NULL; /* give up - this drag has no effect */
1380 } else if (button == LEFT_RELEASE && ui->dragging) {
1381 char data[256], *str;
1384 * Terminate the drag, and if the piece has actually moved
1385 * then return a move string quoting the old and new
1386 * locations of the piece's anchor.
1388 if (ui->drag_anchor != ui->drag_currpos) {
1389 sprintf(data, "M%d-%d", ui->drag_anchor, ui->drag_currpos);
1392 str = ""; /* null move; just update the UI */
1394 ui->dragging = FALSE;
1395 ui->drag_anchor = ui->drag_currpos = -1;
1396 ui->drag_offset_x = ui->drag_offset_y = -1;
1397 memset(ui->reachable, 0, wh);
1400 } else if (button == ' ' && state->soln) {
1402 * Make the next move in the stored solution.
1407 a1 = state->soln->moves[state->soln_index*2];
1408 a2 = state->soln->moves[state->soln_index*2+1];
1409 if (a1 == state->lastmoved_pos)
1410 a1 = state->lastmoved;
1412 sprintf(data, "M%d-%d", a1, a2);
1413 return dupstr(data);
1419 static int move_piece(int w, int h, const unsigned char *src,
1420 unsigned char *dst, unsigned char *ff, int from, int to)
1425 if (!ISANCHOR(dst[from]))
1429 * Scan to the far end of the piece's linked list.
1431 for (i = j = from; j < wh; j++)
1432 if (src[j] == DIST(j - i))
1436 * Remove the piece from its old location in the new
1439 for (j = i; j >= 0; j = (ISDIST(src[j]) ? j - src[j] : -1))
1443 * And put it back in at the new location.
1445 for (j = i; j >= 0; j = (ISDIST(src[j]) ? j - src[j] : -1)) {
1446 int jn = j + to - from;
1447 if (jn < 0 || jn >= wh)
1449 if (dst[jn] == EMPTY && (!ff[jn] || src[from] == MAINANCHOR)) {
1459 static game_state *execute_move(game_state *state, char *move)
1461 int w = state->w, h = state->h /* , wh = w*h */;
1463 int a1, a2, n, movesize;
1464 game_state *ret = dup_game(state);
1470 * This is a solve move, so we just set up a stored
1473 if (ret->soln && --ret->soln->refcount <= 0) {
1474 sfree(ret->soln->moves);
1477 ret->soln = snew(struct game_solution);
1478 ret->soln->nmoves = 0;
1479 ret->soln->moves = NULL;
1480 ret->soln->refcount = 1;
1481 ret->soln_index = 0;
1482 ret->cheated = TRUE;
1487 if (sscanf(move, "%d-%d%n", &a1, &a2, &n) != 2) {
1493 * Special case: if the first move in the solution
1494 * involves the piece for which we already have a
1495 * partial stored move, adjust the source point to
1496 * the original starting point of that piece.
1498 if (ret->soln->nmoves == 0 && a1 == ret->lastmoved)
1499 a1 = ret->lastmoved_pos;
1501 if (ret->soln->nmoves >= movesize) {
1502 movesize = (ret->soln->nmoves + 48) * 4 / 3;
1503 ret->soln->moves = sresize(ret->soln->moves,
1507 ret->soln->moves[2*ret->soln->nmoves] = a1;
1508 ret->soln->moves[2*ret->soln->nmoves+1] = a2;
1509 ret->soln->nmoves++;
1513 move++; /* eat comma */
1515 } else if (c == 'M') {
1517 if (sscanf(move, "%d-%d%n", &a1, &a2, &n) != 2 ||
1518 !move_piece(w, h, state->board, ret->board,
1519 state->imm->forcefield, a1, a2)) {
1523 if (a1 == ret->lastmoved) {
1525 * If the player has moved the same piece as they
1526 * moved last time, don't increment the move
1527 * count. In fact, if they've put the piece back
1528 * where it started from, _decrement_ the move
1531 if (a2 == ret->lastmoved_pos) {
1532 ret->movecount--; /* reverted last move */
1533 ret->lastmoved = ret->lastmoved_pos = -1;
1535 ret->lastmoved = a2;
1536 /* don't change lastmoved_pos */
1539 ret->lastmoved = a2;
1540 ret->lastmoved_pos = a1;
1545 * If we have a stored solution path, see if we've
1546 * strayed from it or successfully made the next move
1549 if (ret->soln && ret->lastmoved_pos >= 0) {
1550 if (ret->lastmoved_pos !=
1551 ret->soln->moves[ret->soln_index*2]) {
1552 /* strayed from the path */
1553 ret->soln->refcount--;
1554 assert(ret->soln->refcount > 0);
1555 /* `state' at least still exists */
1557 ret->soln_index = -1;
1558 } else if (ret->lastmoved ==
1559 ret->soln->moves[ret->soln_index*2+1]) {
1560 /* advanced along the path */
1562 if (ret->soln_index >= ret->soln->nmoves) {
1563 /* finished the path! */
1564 ret->soln->refcount--;
1565 assert(ret->soln->refcount > 0);
1566 /* `state' at least still exists */
1568 ret->soln_index = -1;
1573 if (ret->board[a2] == MAINANCHOR &&
1574 a2 == ret->ty * w + ret->tx && ret->completed < 0)
1575 ret->completed = ret->movecount;
1592 /* ----------------------------------------------------------------------
1596 static void game_compute_size(game_params *params, int tilesize,
1599 /* fool the macros */
1600 struct dummy { int tilesize; } dummy, *ds = &dummy;
1601 dummy.tilesize = tilesize;
1603 *x = params->w * TILESIZE + 2*BORDER;
1604 *y = params->h * TILESIZE + 2*BORDER;
1607 static void game_set_size(drawing *dr, game_drawstate *ds,
1608 game_params *params, int tilesize)
1610 ds->tilesize = tilesize;
1613 static void raise_colour(float *target, float *src, float *limit)
1616 for (i = 0; i < 3; i++)
1617 target[i] = (2*src[i] + limit[i]) / 3;
1620 static float *game_colours(frontend *fe, int *ncolours)
1622 float *ret = snewn(3 * NCOLOURS, float);
1624 game_mkhighlight(fe, ret, COL_BACKGROUND, COL_HIGHLIGHT, COL_LOWLIGHT);
1627 * When dragging a tile, we light it up a bit.
1629 raise_colour(ret+3*COL_DRAGGING,
1630 ret+3*COL_BACKGROUND, ret+3*COL_HIGHLIGHT);
1631 raise_colour(ret+3*COL_DRAGGING_HIGHLIGHT,
1632 ret+3*COL_HIGHLIGHT, ret+3*COL_HIGHLIGHT);
1633 raise_colour(ret+3*COL_DRAGGING_LOWLIGHT,
1634 ret+3*COL_LOWLIGHT, ret+3*COL_HIGHLIGHT);
1637 * The main tile is tinted blue.
1639 ret[COL_MAIN * 3 + 0] = ret[COL_BACKGROUND * 3 + 0];
1640 ret[COL_MAIN * 3 + 1] = ret[COL_BACKGROUND * 3 + 1];
1641 ret[COL_MAIN * 3 + 2] = ret[COL_HIGHLIGHT * 3 + 2];
1642 game_mkhighlight_specific(fe, ret, COL_MAIN,
1643 COL_MAIN_HIGHLIGHT, COL_MAIN_LOWLIGHT);
1646 * And we light that up a bit too when dragging.
1648 raise_colour(ret+3*COL_MAIN_DRAGGING,
1649 ret+3*COL_MAIN, ret+3*COL_MAIN_HIGHLIGHT);
1650 raise_colour(ret+3*COL_MAIN_DRAGGING_HIGHLIGHT,
1651 ret+3*COL_MAIN_HIGHLIGHT, ret+3*COL_MAIN_HIGHLIGHT);
1652 raise_colour(ret+3*COL_MAIN_DRAGGING_LOWLIGHT,
1653 ret+3*COL_MAIN_LOWLIGHT, ret+3*COL_MAIN_HIGHLIGHT);
1656 * The target area on the floor is tinted green.
1658 ret[COL_TARGET * 3 + 0] = ret[COL_BACKGROUND * 3 + 0];
1659 ret[COL_TARGET * 3 + 1] = ret[COL_HIGHLIGHT * 3 + 1];
1660 ret[COL_TARGET * 3 + 2] = ret[COL_BACKGROUND * 3 + 2];
1661 game_mkhighlight_specific(fe, ret, COL_TARGET,
1662 COL_TARGET_HIGHLIGHT, COL_TARGET_LOWLIGHT);
1664 *ncolours = NCOLOURS;
1668 static game_drawstate *game_new_drawstate(drawing *dr, game_state *state)
1670 int w = state->w, h = state->h, wh = w*h;
1671 struct game_drawstate *ds = snew(struct game_drawstate);
1677 ds->started = FALSE;
1678 ds->grid = snewn(wh, unsigned long);
1679 for (i = 0; i < wh; i++)
1680 ds->grid[i] = ~(unsigned long)0;
1685 static void game_free_drawstate(drawing *dr, game_drawstate *ds)
1691 #define BG_NORMAL 0x00000001UL
1692 #define BG_TARGET 0x00000002UL
1693 #define BG_FORCEFIELD 0x00000004UL
1694 #define FLASH_LOW 0x00000008UL
1695 #define FLASH_HIGH 0x00000010UL
1696 #define FG_WALL 0x00000020UL
1697 #define FG_MAIN 0x00000040UL
1698 #define FG_NORMAL 0x00000080UL
1699 #define FG_DRAGGING 0x00000100UL
1700 #define FG_SHADOW 0x00000200UL
1701 #define FG_SOLVEPIECE 0x00000400UL
1702 #define FG_MAINPIECESH 11
1703 #define FG_SHADOWSH 19
1705 #define PIECE_LBORDER 0x00000001UL
1706 #define PIECE_TBORDER 0x00000002UL
1707 #define PIECE_RBORDER 0x00000004UL
1708 #define PIECE_BBORDER 0x00000008UL
1709 #define PIECE_TLCORNER 0x00000010UL
1710 #define PIECE_TRCORNER 0x00000020UL
1711 #define PIECE_BLCORNER 0x00000040UL
1712 #define PIECE_BRCORNER 0x00000080UL
1713 #define PIECE_MASK 0x000000FFUL
1718 #define TYPE_MASK 0xF000
1719 #define COL_MASK 0x0FFF
1720 #define TYPE_RECT 0x0000
1721 #define TYPE_TLCIRC 0x4000
1722 #define TYPE_TRCIRC 0x5000
1723 #define TYPE_BLCIRC 0x6000
1724 #define TYPE_BRCIRC 0x7000
1725 static void maybe_rect(drawing *dr, int x, int y, int w, int h,
1726 int coltype, int col2)
1728 int colour = coltype & COL_MASK, type = coltype & TYPE_MASK;
1730 if (colour > NCOLOURS)
1732 if (type == TYPE_RECT) {
1733 draw_rect(dr, x, y, w, h, colour);
1737 clip(dr, x, y, w, h);
1747 if (col2 == -1 || col2 == coltype) {
1749 draw_circle(dr, cx, cy, r, colour, colour);
1752 * We aim to draw a quadrant of a circle in two
1753 * different colours. We do this using Bresenham's
1754 * algorithm directly, because the Puzzles drawing API
1755 * doesn't have a draw-sector primitive.
1757 int bx, by, bd, bd2;
1758 int xm = (type & 0x1000 ? -1 : +1);
1759 int ym = (type & 0x2000 ? -1 : +1);
1769 int x1 = cx+xm*bx, y1 = cy+ym*bx;
1772 x2 = cx+xm*by; y2 = y1;
1773 draw_rect(dr, min(x1,x2), min(y1,y2),
1774 abs(x1-x2)+1, abs(y1-y2)+1, colour);
1775 x2 = x1; y2 = cy+ym*by;
1776 draw_rect(dr, min(x1,x2), min(y1,y2),
1777 abs(x1-x2)+1, abs(y1-y2)+1, col2);
1781 bd2 = bd - (2*by - 1);
1782 if (abs(bd2) < abs(bd)) {
1794 static void draw_wallpart(drawing *dr, game_drawstate *ds,
1795 int tx, int ty, unsigned long val,
1796 int cl, int cc, int ch)
1800 draw_rect(dr, tx, ty, TILESIZE, TILESIZE, cc);
1801 if (val & PIECE_LBORDER)
1802 draw_rect(dr, tx, ty, HIGHLIGHT_WIDTH, TILESIZE,
1804 if (val & PIECE_RBORDER)
1805 draw_rect(dr, tx+TILESIZE-HIGHLIGHT_WIDTH, ty,
1806 HIGHLIGHT_WIDTH, TILESIZE, cl);
1807 if (val & PIECE_TBORDER)
1808 draw_rect(dr, tx, ty, TILESIZE, HIGHLIGHT_WIDTH, ch);
1809 if (val & PIECE_BBORDER)
1810 draw_rect(dr, tx, ty+TILESIZE-HIGHLIGHT_WIDTH,
1811 TILESIZE, HIGHLIGHT_WIDTH, cl);
1812 if (!((PIECE_BBORDER | PIECE_LBORDER) &~ val)) {
1813 draw_rect(dr, tx, ty+TILESIZE-HIGHLIGHT_WIDTH,
1814 HIGHLIGHT_WIDTH, HIGHLIGHT_WIDTH, cl);
1815 clip(dr, tx, ty+TILESIZE-HIGHLIGHT_WIDTH,
1816 HIGHLIGHT_WIDTH, HIGHLIGHT_WIDTH);
1818 coords[1] = ty + TILESIZE - HIGHLIGHT_WIDTH - 1;
1819 coords[2] = tx + HIGHLIGHT_WIDTH;
1820 coords[3] = ty + TILESIZE - HIGHLIGHT_WIDTH - 1;
1822 coords[5] = ty + TILESIZE;
1823 draw_polygon(dr, coords, 3, ch, ch);
1825 } else if (val & PIECE_BLCORNER) {
1826 draw_rect(dr, tx, ty+TILESIZE-HIGHLIGHT_WIDTH,
1827 HIGHLIGHT_WIDTH, HIGHLIGHT_WIDTH, ch);
1828 clip(dr, tx, ty+TILESIZE-HIGHLIGHT_WIDTH,
1829 HIGHLIGHT_WIDTH, HIGHLIGHT_WIDTH);
1831 coords[1] = ty + TILESIZE - HIGHLIGHT_WIDTH - 1;
1832 coords[2] = tx + HIGHLIGHT_WIDTH;
1833 coords[3] = ty + TILESIZE - HIGHLIGHT_WIDTH - 1;
1835 coords[5] = ty + TILESIZE;
1836 draw_polygon(dr, coords, 3, cl, cl);
1839 if (!((PIECE_TBORDER | PIECE_RBORDER) &~ val)) {
1840 draw_rect(dr, tx+TILESIZE-HIGHLIGHT_WIDTH, ty,
1841 HIGHLIGHT_WIDTH, HIGHLIGHT_WIDTH, cl);
1842 clip(dr, tx+TILESIZE-HIGHLIGHT_WIDTH, ty,
1843 HIGHLIGHT_WIDTH, HIGHLIGHT_WIDTH);
1844 coords[0] = tx + TILESIZE - HIGHLIGHT_WIDTH - 1;
1846 coords[2] = tx + TILESIZE;
1848 coords[4] = tx + TILESIZE - HIGHLIGHT_WIDTH - 1;
1849 coords[5] = ty + HIGHLIGHT_WIDTH;
1850 draw_polygon(dr, coords, 3, ch, ch);
1852 } else if (val & PIECE_TRCORNER) {
1853 draw_rect(dr, tx+TILESIZE-HIGHLIGHT_WIDTH, ty,
1854 HIGHLIGHT_WIDTH, HIGHLIGHT_WIDTH, ch);
1855 clip(dr, tx+TILESIZE-HIGHLIGHT_WIDTH, ty,
1856 HIGHLIGHT_WIDTH, HIGHLIGHT_WIDTH);
1857 coords[0] = tx + TILESIZE - HIGHLIGHT_WIDTH - 1;
1859 coords[2] = tx + TILESIZE;
1861 coords[4] = tx + TILESIZE - HIGHLIGHT_WIDTH - 1;
1862 coords[5] = ty + HIGHLIGHT_WIDTH;
1863 draw_polygon(dr, coords, 3, cl, cl);
1866 if (val & PIECE_TLCORNER)
1867 draw_rect(dr, tx, ty, HIGHLIGHT_WIDTH, HIGHLIGHT_WIDTH, ch);
1868 if (val & PIECE_BRCORNER)
1869 draw_rect(dr, tx+TILESIZE-HIGHLIGHT_WIDTH,
1870 ty+TILESIZE-HIGHLIGHT_WIDTH,
1871 HIGHLIGHT_WIDTH, HIGHLIGHT_WIDTH, cl);
1874 static void draw_piecepart(drawing *dr, game_drawstate *ds,
1875 int tx, int ty, unsigned long val,
1876 int cl, int cc, int ch)
1881 * Drawing the blocks is hellishly fiddly. The blocks don't
1882 * stretch to the full size of the tile; there's a border
1883 * around them of size BORDER_WIDTH. Then they have bevelled
1884 * borders of size HIGHLIGHT_WIDTH, and also rounded corners.
1886 * I tried for some time to find a clean and clever way to
1887 * figure out what needed drawing from the corner and border
1888 * flags, but in the end the cleanest way I could find was the
1889 * following. We divide the grid square into 25 parts by
1890 * ruling four horizontal and four vertical lines across it;
1891 * those lines are at BORDER_WIDTH and BORDER_WIDTH +
1892 * HIGHLIGHT_WIDTH from the top, from the bottom, from the
1893 * left and from the right. Then we carefully consider each of
1894 * the resulting 25 sections of square, and decide separately
1895 * what needs to go in it based on the flags. In complicated
1896 * cases there can be up to five possibilities affecting any
1897 * given section (no corner or border flags, just the corner
1898 * flag, one border flag, the other border flag, both border
1899 * flags). So there's a lot of very fiddly logic here and all
1900 * I could really think to do was give it my best shot and
1901 * then test it and correct all the typos. Not fun to write,
1902 * and I'm sure it isn't fun to read either, but it seems to
1907 x[1] = x[0] + BORDER_WIDTH;
1908 x[2] = x[1] + HIGHLIGHT_WIDTH;
1909 x[5] = tx + TILESIZE;
1910 x[4] = x[5] - BORDER_WIDTH;
1911 x[3] = x[4] - HIGHLIGHT_WIDTH;
1914 y[1] = y[0] + BORDER_WIDTH;
1915 y[2] = y[1] + HIGHLIGHT_WIDTH;
1916 y[5] = ty + TILESIZE;
1917 y[4] = y[5] - BORDER_WIDTH;
1918 y[3] = y[4] - HIGHLIGHT_WIDTH;
1920 #define RECT(p,q) x[p], y[q], x[(p)+1]-x[p], y[(q)+1]-y[q]
1922 maybe_rect(dr, RECT(0,0),
1923 (val & (PIECE_TLCORNER | PIECE_TBORDER |
1924 PIECE_LBORDER)) ? -1 : cc, -1);
1925 maybe_rect(dr, RECT(1,0),
1926 (val & PIECE_TLCORNER) ? ch : (val & PIECE_TBORDER) ? -1 :
1927 (val & PIECE_LBORDER) ? ch : cc, -1);
1928 maybe_rect(dr, RECT(2,0),
1929 (val & PIECE_TBORDER) ? -1 : cc, -1);
1930 maybe_rect(dr, RECT(3,0),
1931 (val & PIECE_TRCORNER) ? cl : (val & PIECE_TBORDER) ? -1 :
1932 (val & PIECE_RBORDER) ? cl : cc, -1);
1933 maybe_rect(dr, RECT(4,0),
1934 (val & (PIECE_TRCORNER | PIECE_TBORDER |
1935 PIECE_RBORDER)) ? -1 : cc, -1);
1936 maybe_rect(dr, RECT(0,1),
1937 (val & PIECE_TLCORNER) ? ch : (val & PIECE_LBORDER) ? -1 :
1938 (val & PIECE_TBORDER) ? ch : cc, -1);
1939 maybe_rect(dr, RECT(1,1),
1940 (val & PIECE_TLCORNER) ? cc : -1, -1);
1941 maybe_rect(dr, RECT(1,1),
1942 (val & PIECE_TLCORNER) ? ch | TYPE_TLCIRC :
1943 !((PIECE_TBORDER | PIECE_LBORDER) &~ val) ? ch | TYPE_BRCIRC :
1944 (val & (PIECE_TBORDER | PIECE_LBORDER)) ? ch : cc, -1);
1945 maybe_rect(dr, RECT(2,1),
1946 (val & PIECE_TBORDER) ? ch : cc, -1);
1947 maybe_rect(dr, RECT(3,1),
1948 (val & PIECE_TRCORNER) ? cc : -1, -1);
1949 maybe_rect(dr, RECT(3,1),
1950 (val & (PIECE_TBORDER | PIECE_RBORDER)) == PIECE_TBORDER ? ch :
1951 (val & (PIECE_TBORDER | PIECE_RBORDER)) == PIECE_RBORDER ? cl :
1952 !((PIECE_TBORDER|PIECE_RBORDER) &~ val) ? cl | TYPE_BLCIRC :
1953 (val & PIECE_TRCORNER) ? cl | TYPE_TRCIRC :
1955 maybe_rect(dr, RECT(4,1),
1956 (val & PIECE_TRCORNER) ? ch : (val & PIECE_RBORDER) ? -1 :
1957 (val & PIECE_TBORDER) ? ch : cc, -1);
1958 maybe_rect(dr, RECT(0,2),
1959 (val & PIECE_LBORDER) ? -1 : cc, -1);
1960 maybe_rect(dr, RECT(1,2),
1961 (val & PIECE_LBORDER) ? ch : cc, -1);
1962 maybe_rect(dr, RECT(2,2),
1964 maybe_rect(dr, RECT(3,2),
1965 (val & PIECE_RBORDER) ? cl : cc, -1);
1966 maybe_rect(dr, RECT(4,2),
1967 (val & PIECE_RBORDER) ? -1 : cc, -1);
1968 maybe_rect(dr, RECT(0,3),
1969 (val & PIECE_BLCORNER) ? cl : (val & PIECE_LBORDER) ? -1 :
1970 (val & PIECE_BBORDER) ? cl : cc, -1);
1971 maybe_rect(dr, RECT(1,3),
1972 (val & PIECE_BLCORNER) ? cc : -1, -1);
1973 maybe_rect(dr, RECT(1,3),
1974 (val & (PIECE_BBORDER | PIECE_LBORDER)) == PIECE_BBORDER ? cl :
1975 (val & (PIECE_BBORDER | PIECE_LBORDER)) == PIECE_LBORDER ? ch :
1976 !((PIECE_BBORDER|PIECE_LBORDER) &~ val) ? ch | TYPE_TRCIRC :
1977 (val & PIECE_BLCORNER) ? ch | TYPE_BLCIRC :
1979 maybe_rect(dr, RECT(2,3),
1980 (val & PIECE_BBORDER) ? cl : cc, -1);
1981 maybe_rect(dr, RECT(3,3),
1982 (val & PIECE_BRCORNER) ? cc : -1, -1);
1983 maybe_rect(dr, RECT(3,3),
1984 (val & PIECE_BRCORNER) ? cl | TYPE_BRCIRC :
1985 !((PIECE_BBORDER | PIECE_RBORDER) &~ val) ? cl | TYPE_TLCIRC :
1986 (val & (PIECE_BBORDER | PIECE_RBORDER)) ? cl : cc, -1);
1987 maybe_rect(dr, RECT(4,3),
1988 (val & PIECE_BRCORNER) ? cl : (val & PIECE_RBORDER) ? -1 :
1989 (val & PIECE_BBORDER) ? cl : cc, -1);
1990 maybe_rect(dr, RECT(0,4),
1991 (val & (PIECE_BLCORNER | PIECE_BBORDER |
1992 PIECE_LBORDER)) ? -1 : cc, -1);
1993 maybe_rect(dr, RECT(1,4),
1994 (val & PIECE_BLCORNER) ? ch : (val & PIECE_BBORDER) ? -1 :
1995 (val & PIECE_LBORDER) ? ch : cc, -1);
1996 maybe_rect(dr, RECT(2,4),
1997 (val & PIECE_BBORDER) ? -1 : cc, -1);
1998 maybe_rect(dr, RECT(3,4),
1999 (val & PIECE_BRCORNER) ? cl : (val & PIECE_BBORDER) ? -1 :
2000 (val & PIECE_RBORDER) ? cl : cc, -1);
2001 maybe_rect(dr, RECT(4,4),
2002 (val & (PIECE_BRCORNER | PIECE_BBORDER |
2003 PIECE_RBORDER)) ? -1 : cc, -1);
2008 static void draw_tile(drawing *dr, game_drawstate *ds,
2009 int x, int y, unsigned long val)
2011 int tx = COORD(x), ty = COORD(y);
2015 * Draw the tile background.
2017 if (val & BG_TARGET)
2020 cc = COL_BACKGROUND;
2023 if (val & FLASH_LOW)
2025 else if (val & FLASH_HIGH)
2028 draw_rect(dr, tx, ty, TILESIZE, TILESIZE, cc);
2029 if (val & BG_FORCEFIELD) {
2031 * Cattle-grid effect to indicate that nothing but the
2032 * main block can slide over this square.
2034 int n = 3 * (TILESIZE / (3*HIGHLIGHT_WIDTH));
2037 for (i = 1; i < n; i += 3) {
2038 draw_rect(dr, tx,ty+(TILESIZE*i/n), TILESIZE,HIGHLIGHT_WIDTH, cl);
2039 draw_rect(dr, tx+(TILESIZE*i/n),ty, HIGHLIGHT_WIDTH,TILESIZE, cl);
2044 * Draw the tile midground: a shadow of a block, for
2045 * displaying partial solutions.
2047 if (val & FG_SHADOW) {
2048 draw_piecepart(dr, ds, tx, ty, (val >> FG_SHADOWSH) & PIECE_MASK,
2053 * Draw the tile foreground, i.e. some section of a block or
2056 if (val & FG_WALL) {
2057 cc = COL_BACKGROUND;
2060 if (val & FLASH_LOW)
2062 else if (val & FLASH_HIGH)
2065 draw_wallpart(dr, ds, tx, ty, (val >> FG_MAINPIECESH) & PIECE_MASK,
2067 } else if (val & (FG_MAIN | FG_NORMAL)) {
2068 if (val & FG_DRAGGING)
2069 cc = (val & FG_MAIN ? COL_MAIN_DRAGGING : COL_DRAGGING);
2071 cc = (val & FG_MAIN ? COL_MAIN : COL_BACKGROUND);
2075 if (val & FLASH_LOW)
2077 else if (val & (FLASH_HIGH | FG_SOLVEPIECE))
2080 draw_piecepart(dr, ds, tx, ty, (val >> FG_MAINPIECESH) & PIECE_MASK,
2084 draw_update(dr, tx, ty, TILESIZE, TILESIZE);
2087 static unsigned long find_piecepart(int w, int h, int *dsf, int x, int y)
2090 int canon = dsf_canonify(dsf, i);
2091 unsigned long val = 0;
2093 if (x == 0 || canon != dsf_canonify(dsf, i-1))
2094 val |= PIECE_LBORDER;
2095 if (y== 0 || canon != dsf_canonify(dsf, i-w))
2096 val |= PIECE_TBORDER;
2097 if (x == w-1 || canon != dsf_canonify(dsf, i+1))
2098 val |= PIECE_RBORDER;
2099 if (y == h-1 || canon != dsf_canonify(dsf, i+w))
2100 val |= PIECE_BBORDER;
2101 if (!(val & (PIECE_TBORDER | PIECE_LBORDER)) &&
2102 canon != dsf_canonify(dsf, i-1-w))
2103 val |= PIECE_TLCORNER;
2104 if (!(val & (PIECE_TBORDER | PIECE_RBORDER)) &&
2105 canon != dsf_canonify(dsf, i+1-w))
2106 val |= PIECE_TRCORNER;
2107 if (!(val & (PIECE_BBORDER | PIECE_LBORDER)) &&
2108 canon != dsf_canonify(dsf, i-1+w))
2109 val |= PIECE_BLCORNER;
2110 if (!(val & (PIECE_BBORDER | PIECE_RBORDER)) &&
2111 canon != dsf_canonify(dsf, i+1+w))
2112 val |= PIECE_BRCORNER;
2116 static void game_redraw(drawing *dr, game_drawstate *ds, game_state *oldstate,
2117 game_state *state, int dir, game_ui *ui,
2118 float animtime, float flashtime)
2120 int w = state->w, h = state->h, wh = w*h;
2121 unsigned char *board;
2123 int x, y, mainanchor, mainpos, dragpos, solvepos, solvesrc, solvedst;
2127 * The initial contents of the window are not guaranteed
2128 * and can vary with front ends. To be on the safe side,
2129 * all games should start by drawing a big
2130 * background-colour rectangle covering the whole window.
2132 draw_rect(dr, 0, 0, 10*ds->tilesize, 10*ds->tilesize, COL_BACKGROUND);
2137 * Construct the board we'll be displaying (which may be
2138 * different from the one in state if ui describes a drag in
2141 board = snewn(wh, unsigned char);
2142 memcpy(board, state->board, wh);
2144 int mpret = move_piece(w, h, state->board, board,
2145 state->imm->forcefield,
2146 ui->drag_anchor, ui->drag_currpos);
2151 solvesrc = state->soln->moves[state->soln_index*2];
2152 solvedst = state->soln->moves[state->soln_index*2+1];
2153 if (solvesrc == state->lastmoved_pos)
2154 solvesrc = state->lastmoved;
2155 if (solvesrc == ui->drag_anchor)
2156 solvesrc = ui->drag_currpos;
2158 solvesrc = solvedst = -1;
2161 * Build a dsf out of that board, so we can conveniently tell
2162 * which edges are connected and which aren't.
2166 for (y = 0; y < h; y++)
2167 for (x = 0; x < w; x++) {
2170 if (ISDIST(board[i]))
2171 dsf_merge(dsf, i, i - board[i]);
2172 if (board[i] == MAINANCHOR)
2174 if (board[i] == WALL) {
2175 if (x > 0 && board[i-1] == WALL)
2176 dsf_merge(dsf, i, i-1);
2177 if (y > 0 && board[i-w] == WALL)
2178 dsf_merge(dsf, i, i-w);
2181 assert(mainanchor >= 0);
2182 mainpos = dsf_canonify(dsf, mainanchor);
2183 dragpos = ui->drag_currpos > 0 ? dsf_canonify(dsf, ui->drag_currpos) : -1;
2184 solvepos = solvesrc >= 0 ? dsf_canonify(dsf, solvesrc) : -1;
2187 * Now we can construct the data about what we want to draw.
2189 for (y = 0; y < h; y++)
2190 for (x = 0; x < w; x++) {
2197 * See if this square is part of the target area.
2199 j = i + mainanchor - (state->ty * w + state->tx);
2200 while (j >= 0 && j < wh && ISDIST(board[j]))
2202 if (j == mainanchor)
2207 if (state->imm->forcefield[i])
2208 val |= BG_FORCEFIELD;
2210 if (flashtime > 0) {
2211 int flashtype = (int)(flashtime / FLASH_INTERVAL) & 1;
2212 val |= (flashtype ? FLASH_LOW : FLASH_HIGH);
2215 if (board[i] != EMPTY) {
2216 canon = dsf_canonify(dsf, i);
2218 if (board[i] == WALL)
2220 else if (canon == mainpos)
2224 if (canon == dragpos)
2226 if (canon == solvepos)
2227 val |= FG_SOLVEPIECE;
2230 * Now look around to see if other squares
2231 * belonging to the same block are adjacent to us.
2233 val |= find_piecepart(w, h, dsf, x, y) << FG_MAINPIECESH;
2237 * If we're in the middle of showing a solution,
2238 * display a shadow piece for the target of the
2241 if (solvepos >= 0) {
2242 int si = i - solvedst + solvesrc;
2243 if (si >= 0 && si < wh && dsf_canonify(dsf, si) == solvepos) {
2244 val |= find_piecepart(w, h, dsf,
2245 si % w, si / w) << FG_SHADOWSH;
2250 if (val != ds->grid[i]) {
2251 draw_tile(dr, ds, x, y, val);
2257 * Update the status bar.
2260 char statusbuf[256];
2262 sprintf(statusbuf, "%sMoves: %d",
2263 (state->completed >= 0 ?
2264 (state->cheated ? "Auto-solved. " : "COMPLETED! ") :
2265 (state->cheated ? "Auto-solver used. " : "")),
2266 (state->completed >= 0 ? state->completed : state->movecount));
2267 if (state->minmoves >= 0)
2268 sprintf(statusbuf+strlen(statusbuf), " (min %d)",
2271 status_bar(dr, statusbuf);
2278 static float game_anim_length(game_state *oldstate, game_state *newstate,
2279 int dir, game_ui *ui)
2284 static float game_flash_length(game_state *oldstate, game_state *newstate,
2285 int dir, game_ui *ui)
2287 if (oldstate->completed < 0 && newstate->completed >= 0)
2293 static int game_timing_state(game_state *state, game_ui *ui)
2298 static void game_print_size(game_params *params, float *x, float *y)
2302 static void game_print(drawing *dr, game_state *state, int tilesize)
2307 #define thegame slide
2310 const struct game thegame = {
2311 "Slide", NULL, NULL,
2318 TRUE, game_configure, custom_params,
2326 TRUE, game_can_format_as_text_now, game_text_format,
2334 PREFERRED_TILESIZE, game_compute_size, game_set_size,
2337 game_free_drawstate,
2341 FALSE, FALSE, game_print_size, game_print,
2342 TRUE, /* wants_statusbar */
2343 FALSE, game_timing_state,
2347 #ifdef STANDALONE_SOLVER
2351 int main(int argc, char **argv)
2355 char *id = NULL, *desc, *err;
2357 int ret, really_verbose = FALSE;
2360 while (--argc > 0) {
2362 if (!strcmp(p, "-v")) {
2363 really_verbose = TRUE;
2364 } else if (!strcmp(p, "-c")) {
2366 } else if (*p == '-') {
2367 fprintf(stderr, "%s: unrecognised option `%s'\n", argv[0], p);
2375 fprintf(stderr, "usage: %s [-c | -v] <game_id>\n", argv[0]);
2379 desc = strchr(id, ':');
2381 fprintf(stderr, "%s: game id expects a colon in it\n", argv[0]);
2386 p = default_params();
2387 decode_params(p, id);
2388 err = validate_desc(p, desc);
2390 fprintf(stderr, "%s: %s\n", argv[0], err);
2393 s = new_game(NULL, p, desc);
2395 ret = solve_board(s->w, s->h, s->board, s->imm->forcefield,
2396 s->tx, s->ty, -1, &moves);
2398 printf("No solution found\n");
2402 printf("%d moves required\n", ret);
2407 char *text = board_text_format(s->w, s->h, s->board,
2408 s->imm->forcefield);
2411 printf("position %d:\n%s", index, text);
2417 moveret = move_piece(s->w, s->h, s->board,
2418 s2->board, s->imm->forcefield,
2419 moves[index*2], moves[index*2+1]);