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(const 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(const 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(const 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].u.string.sval = dupstr(buf);
249 ret[1].name = "Height";
250 ret[1].type = C_STRING;
251 sprintf(buf, "%d", params->h);
252 ret[1].u.string.sval = dupstr(buf);
254 ret[2].name = "Solution length limit";
255 ret[2].type = C_STRING;
256 sprintf(buf, "%d", params->maxmoves);
257 ret[2].u.string.sval = dupstr(buf);
265 static game_params *custom_params(const config_item *cfg)
267 game_params *ret = snew(game_params);
269 ret->w = atoi(cfg[0].u.string.sval);
270 ret->h = atoi(cfg[1].u.string.sval);
271 ret->maxmoves = atoi(cfg[2].u.string.sval);
276 static const char *validate_params(const game_params *params, int full)
278 if (params->w > MAXWID)
279 return "Width must be at most " STR(MAXWID);
282 return "Width must be at least 5";
284 return "Height must be at least 4";
289 static char *board_text_format(int w, int h, unsigned char *data,
290 unsigned char *forcefield)
293 int *dsf = snew_dsf(wh);
295 int retpos, retlen = (w*2+2)*(h*2+1)+1;
296 char *ret = snewn(retlen, char);
298 for (i = 0; i < wh; i++)
300 dsf_merge(dsf, i - data[i], i);
302 for (y = 0; y < 2*h+1; y++) {
303 for (x = 0; x < 2*w+1; x++) {
305 int i = (y/2)*w+(x/2);
307 #define dtype(i) (ISBLOCK(data[i]) ? \
308 dsf_canonify(dsf, i) : data[i])
309 #define dchar(t) ((t)==EMPTY ? ' ' : (t)==WALL ? '#' : \
310 data[t] == MAINANCHOR ? '*' : '%')
312 if (y % 2 && x % 2) {
315 } else if (y % 2 && !(x % 2)) {
316 int j1 = (x > 0 ? dtype(i-1) : -1);
317 int j2 = (x < 2*w ? dtype(i) : -1);
322 } else if (!(y % 2) && (x % 2)) {
323 int j1 = (y > 0 ? dtype(i-w) : -1);
324 int j2 = (y < 2*h ? dtype(i) : -1);
330 int j1 = (x > 0 && y > 0 ? dtype(i-w-1) : -1);
331 int j2 = (x > 0 && y < 2*h ? dtype(i-1) : -1);
332 int j3 = (x < 2*w && y > 0 ? dtype(i-w) : -1);
333 int j4 = (x < 2*w && y < 2*h ? dtype(i) : -1);
334 if (j1 == j2 && j2 == j3 && j3 == j4)
336 else if (j1 == j2 && j3 == j4)
338 else if (j1 == j3 && j2 == j4)
344 assert(retpos < retlen);
347 assert(retpos < retlen);
348 ret[retpos++] = '\n';
350 assert(retpos < retlen);
351 ret[retpos++] = '\0';
352 assert(retpos == retlen);
357 /* ----------------------------------------------------------------------
362 * During solver execution, the set of visited board positions is
363 * stored as a tree234 of the following structures. `w', `h' and
364 * `data' are obvious in meaning; `dist' represents the minimum
365 * distance to reach this position from the starting point.
367 * `prev' links each board to the board position from which it was
368 * most efficiently derived.
377 static int boardcmp(void *av, void *bv)
379 struct board *a = (struct board *)av;
380 struct board *b = (struct board *)bv;
381 return memcmp(a->data, b->data, a->w * a->h);
384 static struct board *newboard(int w, int h, unsigned char *data)
386 struct board *b = malloc(sizeof(struct board) + w*h);
387 b->data = (unsigned char *)b + sizeof(struct board);
388 memcpy(b->data, data, w*h);
397 * The actual solver. Given a board, attempt to find the minimum
398 * length of move sequence which moves MAINANCHOR to (tx,ty), or
399 * -1 if no solution exists. Returns that minimum length.
401 * Also, if `moveout' is provided, writes out the moves in the
402 * form of a sequence of pairs of integers indicating the source
403 * and destination points of the anchor of the moved piece in each
404 * move. Exactly twice as many integers are written as the number
405 * returned from solve_board(), and `moveout' receives an int *
406 * which is a pointer to a dynamically allocated array.
408 static int solve_board(int w, int h, unsigned char *board,
409 unsigned char *forcefield, int tx, int ty,
410 int movelimit, int **moveout)
413 struct board *b, *b2, *b3;
414 int *next, *anchors, *which;
415 int *movereached, *movequeue, mqhead, mqtail;
416 tree234 *sorted, *queue;
421 #ifdef SOLVER_DIAGNOSTICS
423 char *t = board_text_format(w, h, board);
424 for (i = 0; i < h; i++) {
425 for (j = 0; j < w; j++) {
426 int c = board[i*w+j];
429 else if (c == MAINANCHOR)
431 else if (c == ANCHOR)
441 printf("Starting solver for:\n%s\n", t);
446 sorted = newtree234(boardcmp);
447 queue = newtree234(NULL);
449 b = newboard(w, h, board);
452 addpos234(queue, b, 0);
455 next = snewn(wh, int);
456 anchors = snewn(wh, int);
457 which = snewn(wh, int);
458 movereached = snewn(wh, int);
459 movequeue = snewn(wh, int);
462 while ((b = delpos234(queue, 0)) != NULL) {
464 if (movelimit >= 0 && b->dist >= movelimit) {
466 * The problem is not soluble in under `movelimit'
467 * moves, so we can quit right now.
472 if (b->dist != lastdist) {
473 #ifdef SOLVER_DIAGNOSTICS
474 printf("dist %d (%d)\n", b->dist, count234(sorted));
479 * Find all the anchors and form a linked list of the
480 * squares within each block.
482 for (i = 0; i < wh; i++) {
486 if (ISANCHOR(b->data[i])) {
489 } else if (ISDIST(b->data[i])) {
497 * For each anchor, do an array-based BFS to find all the
498 * places we can slide it to.
500 for (i = 0; i < wh; i++) {
505 for (j = 0; j < wh; j++)
506 movereached[j] = FALSE;
507 movequeue[mqtail++] = i;
508 while (mqhead < mqtail) {
509 int pos = movequeue[mqhead++];
512 * Try to move in each direction from here.
514 for (dir = 0; dir < 4; dir++) {
515 int dx = (dir == 0 ? -1 : dir == 1 ? +1 : 0);
516 int dy = (dir == 2 ? -1 : dir == 3 ? +1 : 0);
517 int offset = dy*w + dx;
518 int newpos = pos + offset;
522 * For each square involved in this block,
523 * check to see if the square d spaces away
524 * from it is either empty or part of the same
527 for (j = i; j >= 0; j = next[j]) {
528 int jy = (pos+j-i) / w + dy, jx = (pos+j-i) % w + dx;
529 if (jy >= 0 && jy < h && jx >= 0 && jx < w &&
530 ((b->data[j+d] == EMPTY || which[j+d] == i) &&
531 (b->data[i] == MAINANCHOR || !forcefield[j+d])))
537 continue; /* this direction wasn't feasible */
540 * If we've already tried moving this piece
543 if (movereached[newpos])
545 movereached[newpos] = TRUE;
546 movequeue[mqtail++] = newpos;
549 * We have a viable move. Make it.
551 b2 = newboard(w, h, b->data);
552 for (j = i; j >= 0; j = next[j])
554 for (j = i; j >= 0; j = next[j])
555 b2->data[j+d] = b->data[j];
557 b3 = add234(sorted, b2);
559 sfree(b2); /* we already got one */
561 b2->dist = b->dist + 1;
563 addpos234(queue, b2, qlen++);
564 if (b2->data[ty*w+tx] == MAINANCHOR)
565 goto done; /* search completed! */
579 * Now b2 represents the solved position. Backtrack to
580 * output the solution.
582 *moveout = snewn(ret * 2, int);
586 int from = -1, to = -1;
591 * Scan b and b2 to find out which piece has
594 for (i = 0; i < wh; i++) {
595 if (ISANCHOR(b->data[i]) && !ISANCHOR(b2->data[i])) {
598 } else if (!ISANCHOR(b->data[i]) && ISANCHOR(b2->data[i])){
604 assert(from >= 0 && to >= 0);
606 (*moveout)[--j] = to;
607 (*moveout)[--j] = from;
614 ret = -1; /* no solution */
621 while ((b = delpos234(sorted, 0)) != NULL)
634 /* ----------------------------------------------------------------------
635 * Random board generation.
638 static void generate_board(int w, int h, int *rtx, int *rty, int *minmoves,
639 random_state *rs, unsigned char **rboard,
640 unsigned char **rforcefield, int movelimit)
643 unsigned char *board, *board2, *forcefield;
644 unsigned char *tried_merge;
646 int *list, nlist, pos;
649 int moves = 0; /* placate optimiser */
652 * Set up a board and fill it with singletons, except for a
655 board = snewn(wh, unsigned char);
656 forcefield = snewn(wh, unsigned char);
657 board2 = snewn(wh, unsigned char);
658 memset(board, ANCHOR, wh);
659 memset(forcefield, FALSE, wh);
660 for (i = 0; i < w; i++)
661 board[i] = board[i+w*(h-1)] = WALL;
662 for (i = 0; i < h; i++)
663 board[i*w] = board[i*w+(w-1)] = WALL;
665 tried_merge = snewn(wh * wh, unsigned char);
666 memset(tried_merge, 0, wh*wh);
670 * Invent a main piece at one extreme. (FIXME: vary the
671 * extreme, and the piece.)
673 board[w+1] = MAINANCHOR;
674 board[w+2] = DIST(1);
675 board[w*2+1] = DIST(w-1);
676 board[w*2+2] = DIST(1);
679 * Invent a target position. (FIXME: vary this too.)
683 forcefield[ty*w+tx+1] = forcefield[(ty+1)*w+tx+1] = TRUE;
684 board[ty*w+tx+1] = board[(ty+1)*w+tx+1] = EMPTY;
687 * Gradually remove singletons until the game becomes soluble.
689 for (j = w; j-- > 0 ;)
690 for (i = h; i-- > 0 ;)
691 if (board[i*w+j] == ANCHOR) {
693 * See if the board is already soluble.
695 if ((moves = solve_board(w, h, board, forcefield,
696 tx, ty, movelimit, NULL)) >= 0)
700 * Otherwise, remove this piece.
702 board[i*w+j] = EMPTY;
704 assert(!"We shouldn't get here");
708 * Make a list of all the inter-block edges on the board.
710 list = snewn(wh*2, int);
712 for (i = 0; i+1 < w; i++)
713 for (j = 0; j < h; j++)
714 list[nlist++] = (j*w+i) * 2 + 0; /* edge to the right of j*w+i */
715 for (j = 0; j+1 < h; j++)
716 for (i = 0; i < w; i++)
717 list[nlist++] = (j*w+i) * 2 + 1; /* edge below j*w+i */
720 * Now go through that list in random order, trying to merge
721 * the blocks on each side of each edge.
723 shuffle(list, nlist, sizeof(*list), rs);
729 y1 = y2 = pos / (w*2);
730 x1 = x2 = (pos / 2) % w;
739 * Immediately abandon the attempt if we've already tried
740 * to merge the same pair of blocks along a different
743 c1 = dsf_canonify(dsf, p1);
744 c2 = dsf_canonify(dsf, p2);
745 if (tried_merge[c1 * wh + c2])
749 * In order to be mergeable, these two squares must each
750 * either be, or belong to, a non-main anchor, and their
751 * anchors must also be distinct.
753 if (!ISBLOCK(board[p1]) || !ISBLOCK(board[p2]))
755 while (ISDIST(board[p1]))
757 while (ISDIST(board[p2]))
759 if (board[p1] == MAINANCHOR || board[p2] == MAINANCHOR || p1 == p2)
763 * We can merge these blocks. Try it, and see if the
764 * puzzle remains soluble.
766 memcpy(board2, board, wh);
768 while (p1 < wh || p2 < wh) {
770 * p1 and p2 are the squares at the head of each block
771 * list. Pick the smaller one and put it on the output
778 assert(i - j <= MAXDIST);
779 board[i] = DIST(i - j);
784 * Now advance whichever list that came from.
789 } while (p1 < wh && board[p1] != DIST(p1-i));
793 } while (p2 < wh && board[p2] != DIST(p2-i));
796 j = solve_board(w, h, board, forcefield, tx, ty, movelimit, NULL);
799 * Didn't work. Revert the merge.
801 memcpy(board, board2, wh);
802 tried_merge[c1 * wh + c2] = tried_merge[c2 * wh + c1] = TRUE;
808 dsf_merge(dsf, c1, c2);
809 c = dsf_canonify(dsf, c1);
810 for (i = 0; i < wh; i++)
811 tried_merge[c*wh+i] = (tried_merge[c1*wh+i] |
812 tried_merge[c2*wh+i]);
813 for (i = 0; i < wh; i++)
814 tried_merge[i*wh+c] = (tried_merge[i*wh+c1] |
815 tried_merge[i*wh+c2]);
827 *rforcefield = forcefield;
831 /* ----------------------------------------------------------------------
832 * End of solver/generator code.
835 static char *new_game_desc(const game_params *params, random_state *rs,
836 char **aux, int interactive)
838 int w = params->w, h = params->h, wh = w*h;
839 int tx, ty, minmoves;
840 unsigned char *board, *forcefield;
844 generate_board(params->w, params->h, &tx, &ty, &minmoves, rs,
845 &board, &forcefield, params->maxmoves);
846 #ifdef GENERATOR_DIAGNOSTICS
848 char *t = board_text_format(params->w, params->h, board);
855 * Encode as a game ID.
857 ret = snewn(wh * 6 + 40, char);
861 if (ISDIST(board[i])) {
862 p += sprintf(p, "d%d", board[i]);
866 int b = board[i], f = forcefield[i];
867 int c = (b == ANCHOR ? 'a' :
868 b == MAINANCHOR ? 'm' :
870 /* b == WALL ? */ 'w');
874 while (i < wh && board[i] == b && forcefield[i] == f)
877 p += sprintf(p, "%d", count);
880 p += sprintf(p, ",%d,%d,%d", tx, ty, minmoves);
881 ret = sresize(ret, p+1 - ret, char);
889 static const char *validate_desc(const game_params *params, const char *desc)
891 int w = params->w, h = params->h, wh = w*h;
894 int i, tx, ty, minmoves;
897 active = snewn(wh, int);
898 link = snewn(wh, int);
901 while (*desc && *desc != ',') {
903 ret = "Too much data in game description";
908 if (*desc == 'f' || *desc == 'F') {
911 ret = "Expected another character after 'f' in game "
917 if (*desc == 'd' || *desc == 'D') {
921 if (!isdigit((unsigned char)*desc)) {
922 ret = "Expected a number after 'd' in game description";
926 while (*desc && isdigit((unsigned char)*desc)) desc++;
928 if (dist <= 0 || dist > i) {
929 ret = "Out-of-range number after 'd' in game description";
933 if (!active[i - dist]) {
934 ret = "Invalid back-reference in game description";
941 active[link[i]] = FALSE;
947 if (!strchr("aAmMeEwW", c)) {
948 ret = "Invalid character in game description";
951 if (isdigit((unsigned char)*desc)) {
953 while (*desc && isdigit((unsigned char)*desc)) desc++;
955 if (i + count > wh) {
956 ret = "Too much data in game description";
959 while (count-- > 0) {
960 active[i] = (strchr("aAmM", c) != NULL);
962 if (strchr("mM", c) != NULL) {
970 ret = (mains == 0 ? "No main piece specified in game description" :
971 "More than one main piece specified in game description");
975 ret = "Not enough data in game description";
980 * Now read the target coordinates.
982 i = sscanf(desc, ",%d,%d,%d", &tx, &ty, &minmoves);
984 ret = "No target coordinates specified";
987 * (but minmoves is optional)
999 static game_state *new_game(midend *me, const game_params *params,
1002 int w = params->w, h = params->h, wh = w*h;
1006 state = snew(game_state);
1009 state->board = snewn(wh, unsigned char);
1010 state->lastmoved = state->lastmoved_pos = -1;
1011 state->movecount = 0;
1012 state->imm = snew(struct game_immutable_state);
1013 state->imm->refcount = 1;
1014 state->imm->forcefield = snewn(wh, unsigned char);
1018 while (*desc && *desc != ',') {
1029 if (*desc == 'd' || *desc == 'D') {
1034 while (*desc && isdigit((unsigned char)*desc)) desc++;
1036 state->board[i] = DIST(dist);
1037 state->imm->forcefield[i] = f;
1044 if (isdigit((unsigned char)*desc)) {
1046 while (*desc && isdigit((unsigned char)*desc)) desc++;
1048 assert(i + count <= wh);
1050 c = (c == 'a' || c == 'A' ? ANCHOR :
1051 c == 'm' || c == 'M' ? MAINANCHOR :
1052 c == 'e' || c == 'E' ? EMPTY :
1053 /* c == 'w' || c == 'W' ? */ WALL);
1055 while (count-- > 0) {
1056 state->board[i] = c;
1057 state->imm->forcefield[i] = f;
1064 * Now read the target coordinates.
1066 state->tx = state->ty = 0;
1067 state->minmoves = -1;
1068 i = sscanf(desc, ",%d,%d,%d", &state->tx, &state->ty, &state->minmoves);
1070 if (state->board[state->ty*w+state->tx] == MAINANCHOR)
1071 state->completed = 0; /* already complete! */
1073 state->completed = -1;
1075 state->cheated = FALSE;
1077 state->soln_index = -1;
1082 static game_state *dup_game(const game_state *state)
1084 int w = state->w, h = state->h, wh = w*h;
1085 game_state *ret = snew(game_state);
1089 ret->board = snewn(wh, unsigned char);
1090 memcpy(ret->board, state->board, wh);
1091 ret->tx = state->tx;
1092 ret->ty = state->ty;
1093 ret->minmoves = state->minmoves;
1094 ret->lastmoved = state->lastmoved;
1095 ret->lastmoved_pos = state->lastmoved_pos;
1096 ret->movecount = state->movecount;
1097 ret->completed = state->completed;
1098 ret->cheated = state->cheated;
1099 ret->imm = state->imm;
1100 ret->imm->refcount++;
1101 ret->soln = state->soln;
1102 ret->soln_index = state->soln_index;
1104 ret->soln->refcount++;
1109 static void free_game(game_state *state)
1111 if (--state->imm->refcount <= 0) {
1112 sfree(state->imm->forcefield);
1115 if (state->soln && --state->soln->refcount <= 0) {
1116 sfree(state->soln->moves);
1119 sfree(state->board);
1123 static char *solve_game(const game_state *state, const game_state *currstate,
1124 const char *aux, const char **error)
1132 * Run the solver and attempt to find the shortest solution
1133 * from the current position.
1135 nmoves = solve_board(state->w, state->h, state->board,
1136 state->imm->forcefield, state->tx, state->ty,
1140 *error = "Unable to find a solution to this puzzle";
1144 *error = "Puzzle is already solved";
1149 * Encode the resulting solution as a move string.
1151 ret = snewn(nmoves * 40, char);
1155 for (i = 0; i < nmoves; i++) {
1156 p += sprintf(p, "%c%d-%d", sep, moves[i*2], moves[i*2+1]);
1161 assert(p - ret < nmoves * 40);
1162 ret = sresize(ret, p+1 - ret, char);
1167 static int game_can_format_as_text_now(const game_params *params)
1172 static char *game_text_format(const game_state *state)
1174 return board_text_format(state->w, state->h, state->board,
1175 state->imm->forcefield);
1181 int drag_offset_x, drag_offset_y;
1183 unsigned char *reachable;
1184 int *bfs_queue; /* used as scratch in interpret_move */
1187 static game_ui *new_ui(const game_state *state)
1189 int w = state->w, h = state->h, wh = w*h;
1190 game_ui *ui = snew(game_ui);
1192 ui->dragging = FALSE;
1193 ui->drag_anchor = ui->drag_currpos = -1;
1194 ui->drag_offset_x = ui->drag_offset_y = -1;
1195 ui->reachable = snewn(wh, unsigned char);
1196 memset(ui->reachable, 0, wh);
1197 ui->bfs_queue = snewn(wh, int);
1202 static void free_ui(game_ui *ui)
1204 sfree(ui->bfs_queue);
1205 sfree(ui->reachable);
1209 static char *encode_ui(const game_ui *ui)
1214 static void decode_ui(game_ui *ui, const char *encoding)
1218 static void game_changed_state(game_ui *ui, const game_state *oldstate,
1219 const game_state *newstate)
1223 #define PREFERRED_TILESIZE 32
1224 #define TILESIZE (ds->tilesize)
1225 #define BORDER (TILESIZE/2)
1226 #define COORD(x) ( (x) * TILESIZE + BORDER )
1227 #define FROMCOORD(x) ( ((x) - BORDER + TILESIZE) / TILESIZE - 1 )
1228 #define BORDER_WIDTH (1 + TILESIZE/20)
1229 #define HIGHLIGHT_WIDTH (1 + TILESIZE/16)
1231 #define FLASH_INTERVAL 0.10F
1232 #define FLASH_TIME 3*FLASH_INTERVAL
1234 struct game_drawstate {
1237 unsigned long *grid; /* what's currently displayed */
1241 static char *interpret_move(const game_state *state, game_ui *ui,
1242 const game_drawstate *ds,
1243 int x, int y, int button)
1245 int w = state->w, h = state->h, wh = w*h;
1249 if (button == LEFT_BUTTON) {
1253 if (tx < 0 || tx >= w || ty < 0 || ty >= h ||
1254 !ISBLOCK(state->board[ty*w+tx]))
1255 return NULL; /* this click has no effect */
1258 * User has clicked on a block. Find the block's anchor
1259 * and register that we've started dragging it.
1262 while (ISDIST(state->board[i]))
1263 i -= state->board[i];
1264 assert(i >= 0 && i < wh);
1266 ui->dragging = TRUE;
1267 ui->drag_anchor = i;
1268 ui->drag_offset_x = tx - (i % w);
1269 ui->drag_offset_y = ty - (i / w);
1270 ui->drag_currpos = i;
1273 * Now we immediately bfs out from the current location of
1274 * the anchor, to find all the places to which this block
1277 memset(ui->reachable, FALSE, wh);
1279 ui->reachable[i] = TRUE;
1280 ui->bfs_queue[qtail++] = i;
1281 for (j = i; j < wh; j++)
1282 if (state->board[j] == DIST(j - i))
1284 while (qhead < qtail) {
1285 int pos = ui->bfs_queue[qhead++];
1286 int x = pos % w, y = pos / w;
1289 for (dir = 0; dir < 4; dir++) {
1290 int dx = (dir == 0 ? -1 : dir == 1 ? +1 : 0);
1291 int dy = (dir == 2 ? -1 : dir == 3 ? +1 : 0);
1294 if (x + dx < 0 || x + dx >= w ||
1295 y + dy < 0 || y + dy >= h)
1298 newpos = pos + dy*w + dx;
1299 if (ui->reachable[newpos])
1300 continue; /* already done this one */
1303 * Now search the grid to see if the block we're
1304 * dragging could fit into this space.
1306 for (j = i; j >= 0; j = (ISDIST(state->board[j]) ?
1307 j - state->board[j] : -1)) {
1308 int jx = (j+pos-ui->drag_anchor) % w;
1309 int jy = (j+pos-ui->drag_anchor) / w;
1312 if (jx + dx < 0 || jx + dx >= w ||
1313 jy + dy < 0 || jy + dy >= h)
1314 break; /* this position isn't valid at all */
1316 j2 = (j+pos-ui->drag_anchor) + dy*w + dx;
1318 if (state->board[j2] == EMPTY &&
1319 (!state->imm->forcefield[j2] ||
1320 state->board[ui->drag_anchor] == MAINANCHOR))
1322 while (ISDIST(state->board[j2]))
1323 j2 -= state->board[j2];
1324 assert(j2 >= 0 && j2 < wh);
1325 if (j2 == ui->drag_anchor)
1333 * If we got to the end of that loop without
1334 * disqualifying this position, mark it as
1335 * reachable for this drag.
1337 ui->reachable[newpos] = TRUE;
1338 ui->bfs_queue[qtail++] = newpos;
1344 * And that's it. Update the display to reflect the start
1348 } else if (button == LEFT_DRAG && ui->dragging) {
1349 int dist, distlimit, dx, dy, s, px, py;
1354 tx -= ui->drag_offset_x;
1355 ty -= ui->drag_offset_y;
1358 * Now search outwards from (tx,ty), in order of Manhattan
1359 * distance, until we find a reachable square.
1362 distlimit = max(distlimit, h+ty);
1363 distlimit = max(distlimit, tx);
1364 distlimit = max(distlimit, ty);
1365 for (dist = 0; dist <= distlimit; dist++) {
1366 for (dx = -dist; dx <= dist; dx++)
1367 for (s = -1; s <= +1; s += 2) {
1368 dy = s * (dist - abs(dx));
1371 if (px >= 0 && px < w && py >= 0 && py < h &&
1372 ui->reachable[py*w+px]) {
1373 ui->drag_currpos = py*w+px;
1378 return NULL; /* give up - this drag has no effect */
1379 } else if (button == LEFT_RELEASE && ui->dragging) {
1380 char data[256], *str;
1383 * Terminate the drag, and if the piece has actually moved
1384 * then return a move string quoting the old and new
1385 * locations of the piece's anchor.
1387 if (ui->drag_anchor != ui->drag_currpos) {
1388 sprintf(data, "M%d-%d", ui->drag_anchor, ui->drag_currpos);
1391 str = ""; /* null move; just update the UI */
1393 ui->dragging = FALSE;
1394 ui->drag_anchor = ui->drag_currpos = -1;
1395 ui->drag_offset_x = ui->drag_offset_y = -1;
1396 memset(ui->reachable, 0, wh);
1399 } else if (button == ' ' && state->soln) {
1401 * Make the next move in the stored solution.
1406 a1 = state->soln->moves[state->soln_index*2];
1407 a2 = state->soln->moves[state->soln_index*2+1];
1408 if (a1 == state->lastmoved_pos)
1409 a1 = state->lastmoved;
1411 sprintf(data, "M%d-%d", a1, a2);
1412 return dupstr(data);
1418 static int move_piece(int w, int h, const unsigned char *src,
1419 unsigned char *dst, unsigned char *ff, int from, int to)
1424 if (!ISANCHOR(dst[from]))
1428 * Scan to the far end of the piece's linked list.
1430 for (i = j = from; j < wh; j++)
1431 if (src[j] == DIST(j - i))
1435 * Remove the piece from its old location in the new
1438 for (j = i; j >= 0; j = (ISDIST(src[j]) ? j - src[j] : -1))
1442 * And put it back in at the new location.
1444 for (j = i; j >= 0; j = (ISDIST(src[j]) ? j - src[j] : -1)) {
1445 int jn = j + to - from;
1446 if (jn < 0 || jn >= wh)
1448 if (dst[jn] == EMPTY && (!ff[jn] || src[from] == MAINANCHOR)) {
1458 static game_state *execute_move(const game_state *state, const char *move)
1460 int w = state->w, h = state->h /* , wh = w*h */;
1462 int a1, a2, n, movesize;
1463 game_state *ret = dup_game(state);
1469 * This is a solve move, so we just set up a stored
1472 if (ret->soln && --ret->soln->refcount <= 0) {
1473 sfree(ret->soln->moves);
1476 ret->soln = snew(struct game_solution);
1477 ret->soln->nmoves = 0;
1478 ret->soln->moves = NULL;
1479 ret->soln->refcount = 1;
1480 ret->soln_index = 0;
1481 ret->cheated = TRUE;
1486 if (sscanf(move, "%d-%d%n", &a1, &a2, &n) != 2) {
1492 * Special case: if the first move in the solution
1493 * involves the piece for which we already have a
1494 * partial stored move, adjust the source point to
1495 * the original starting point of that piece.
1497 if (ret->soln->nmoves == 0 && a1 == ret->lastmoved)
1498 a1 = ret->lastmoved_pos;
1500 if (ret->soln->nmoves >= movesize) {
1501 movesize = (ret->soln->nmoves + 48) * 4 / 3;
1502 ret->soln->moves = sresize(ret->soln->moves,
1506 ret->soln->moves[2*ret->soln->nmoves] = a1;
1507 ret->soln->moves[2*ret->soln->nmoves+1] = a2;
1508 ret->soln->nmoves++;
1512 move++; /* eat comma */
1514 } else if (c == 'M') {
1516 if (sscanf(move, "%d-%d%n", &a1, &a2, &n) != 2 ||
1517 !move_piece(w, h, state->board, ret->board,
1518 state->imm->forcefield, a1, a2)) {
1522 if (a1 == ret->lastmoved) {
1524 * If the player has moved the same piece as they
1525 * moved last time, don't increment the move
1526 * count. In fact, if they've put the piece back
1527 * where it started from, _decrement_ the move
1530 if (a2 == ret->lastmoved_pos) {
1531 ret->movecount--; /* reverted last move */
1532 ret->lastmoved = ret->lastmoved_pos = -1;
1534 ret->lastmoved = a2;
1535 /* don't change lastmoved_pos */
1538 ret->lastmoved = a2;
1539 ret->lastmoved_pos = a1;
1544 * If we have a stored solution path, see if we've
1545 * strayed from it or successfully made the next move
1548 if (ret->soln && ret->lastmoved_pos >= 0) {
1549 if (ret->lastmoved_pos !=
1550 ret->soln->moves[ret->soln_index*2]) {
1551 /* strayed from the path */
1552 ret->soln->refcount--;
1553 assert(ret->soln->refcount > 0);
1554 /* `state' at least still exists */
1556 ret->soln_index = -1;
1557 } else if (ret->lastmoved ==
1558 ret->soln->moves[ret->soln_index*2+1]) {
1559 /* advanced along the path */
1561 if (ret->soln_index >= ret->soln->nmoves) {
1562 /* finished the path! */
1563 ret->soln->refcount--;
1564 assert(ret->soln->refcount > 0);
1565 /* `state' at least still exists */
1567 ret->soln_index = -1;
1572 if (ret->board[a2] == MAINANCHOR &&
1573 a2 == ret->ty * w + ret->tx && ret->completed < 0)
1574 ret->completed = ret->movecount;
1591 /* ----------------------------------------------------------------------
1595 static void game_compute_size(const game_params *params, int tilesize,
1598 /* fool the macros */
1599 struct dummy { int tilesize; } dummy, *ds = &dummy;
1600 dummy.tilesize = tilesize;
1602 *x = params->w * TILESIZE + 2*BORDER;
1603 *y = params->h * TILESIZE + 2*BORDER;
1606 static void game_set_size(drawing *dr, game_drawstate *ds,
1607 const game_params *params, int tilesize)
1609 ds->tilesize = tilesize;
1612 static void raise_colour(float *target, float *src, float *limit)
1615 for (i = 0; i < 3; i++)
1616 target[i] = (2*src[i] + limit[i]) / 3;
1619 static float *game_colours(frontend *fe, int *ncolours)
1621 float *ret = snewn(3 * NCOLOURS, float);
1623 game_mkhighlight(fe, ret, COL_BACKGROUND, COL_HIGHLIGHT, COL_LOWLIGHT);
1626 * When dragging a tile, we light it up a bit.
1628 raise_colour(ret+3*COL_DRAGGING,
1629 ret+3*COL_BACKGROUND, ret+3*COL_HIGHLIGHT);
1630 raise_colour(ret+3*COL_DRAGGING_HIGHLIGHT,
1631 ret+3*COL_HIGHLIGHT, ret+3*COL_HIGHLIGHT);
1632 raise_colour(ret+3*COL_DRAGGING_LOWLIGHT,
1633 ret+3*COL_LOWLIGHT, ret+3*COL_HIGHLIGHT);
1636 * The main tile is tinted blue.
1638 ret[COL_MAIN * 3 + 0] = ret[COL_BACKGROUND * 3 + 0];
1639 ret[COL_MAIN * 3 + 1] = ret[COL_BACKGROUND * 3 + 1];
1640 ret[COL_MAIN * 3 + 2] = ret[COL_HIGHLIGHT * 3 + 2];
1641 game_mkhighlight_specific(fe, ret, COL_MAIN,
1642 COL_MAIN_HIGHLIGHT, COL_MAIN_LOWLIGHT);
1645 * And we light that up a bit too when dragging.
1647 raise_colour(ret+3*COL_MAIN_DRAGGING,
1648 ret+3*COL_MAIN, ret+3*COL_MAIN_HIGHLIGHT);
1649 raise_colour(ret+3*COL_MAIN_DRAGGING_HIGHLIGHT,
1650 ret+3*COL_MAIN_HIGHLIGHT, ret+3*COL_MAIN_HIGHLIGHT);
1651 raise_colour(ret+3*COL_MAIN_DRAGGING_LOWLIGHT,
1652 ret+3*COL_MAIN_LOWLIGHT, ret+3*COL_MAIN_HIGHLIGHT);
1655 * The target area on the floor is tinted green.
1657 ret[COL_TARGET * 3 + 0] = ret[COL_BACKGROUND * 3 + 0];
1658 ret[COL_TARGET * 3 + 1] = ret[COL_HIGHLIGHT * 3 + 1];
1659 ret[COL_TARGET * 3 + 2] = ret[COL_BACKGROUND * 3 + 2];
1660 game_mkhighlight_specific(fe, ret, COL_TARGET,
1661 COL_TARGET_HIGHLIGHT, COL_TARGET_LOWLIGHT);
1663 *ncolours = NCOLOURS;
1667 static game_drawstate *game_new_drawstate(drawing *dr, const game_state *state)
1669 int w = state->w, h = state->h, wh = w*h;
1670 struct game_drawstate *ds = snew(struct game_drawstate);
1676 ds->started = FALSE;
1677 ds->grid = snewn(wh, unsigned long);
1678 for (i = 0; i < wh; i++)
1679 ds->grid[i] = ~(unsigned long)0;
1684 static void game_free_drawstate(drawing *dr, game_drawstate *ds)
1690 #define BG_NORMAL 0x00000001UL
1691 #define BG_TARGET 0x00000002UL
1692 #define BG_FORCEFIELD 0x00000004UL
1693 #define FLASH_LOW 0x00000008UL
1694 #define FLASH_HIGH 0x00000010UL
1695 #define FG_WALL 0x00000020UL
1696 #define FG_MAIN 0x00000040UL
1697 #define FG_NORMAL 0x00000080UL
1698 #define FG_DRAGGING 0x00000100UL
1699 #define FG_SHADOW 0x00000200UL
1700 #define FG_SOLVEPIECE 0x00000400UL
1701 #define FG_MAINPIECESH 11
1702 #define FG_SHADOWSH 19
1704 #define PIECE_LBORDER 0x00000001UL
1705 #define PIECE_TBORDER 0x00000002UL
1706 #define PIECE_RBORDER 0x00000004UL
1707 #define PIECE_BBORDER 0x00000008UL
1708 #define PIECE_TLCORNER 0x00000010UL
1709 #define PIECE_TRCORNER 0x00000020UL
1710 #define PIECE_BLCORNER 0x00000040UL
1711 #define PIECE_BRCORNER 0x00000080UL
1712 #define PIECE_MASK 0x000000FFUL
1717 #define TYPE_MASK 0xF000
1718 #define COL_MASK 0x0FFF
1719 #define TYPE_RECT 0x0000
1720 #define TYPE_TLCIRC 0x4000
1721 #define TYPE_TRCIRC 0x5000
1722 #define TYPE_BLCIRC 0x6000
1723 #define TYPE_BRCIRC 0x7000
1724 static void maybe_rect(drawing *dr, int x, int y, int w, int h,
1725 int coltype, int col2)
1727 int colour = coltype & COL_MASK, type = coltype & TYPE_MASK;
1729 if (colour > NCOLOURS)
1731 if (type == TYPE_RECT) {
1732 draw_rect(dr, x, y, w, h, colour);
1736 clip(dr, x, y, w, h);
1746 if (col2 == -1 || col2 == coltype) {
1748 draw_circle(dr, cx, cy, r, colour, colour);
1751 * We aim to draw a quadrant of a circle in two
1752 * different colours. We do this using Bresenham's
1753 * algorithm directly, because the Puzzles drawing API
1754 * doesn't have a draw-sector primitive.
1756 int bx, by, bd, bd2;
1757 int xm = (type & 0x1000 ? -1 : +1);
1758 int ym = (type & 0x2000 ? -1 : +1);
1768 int x1 = cx+xm*bx, y1 = cy+ym*bx;
1771 x2 = cx+xm*by; y2 = y1;
1772 draw_rect(dr, min(x1,x2), min(y1,y2),
1773 abs(x1-x2)+1, abs(y1-y2)+1, colour);
1774 x2 = x1; y2 = cy+ym*by;
1775 draw_rect(dr, min(x1,x2), min(y1,y2),
1776 abs(x1-x2)+1, abs(y1-y2)+1, col2);
1780 bd2 = bd - (2*by - 1);
1781 if (abs(bd2) < abs(bd)) {
1793 static void draw_wallpart(drawing *dr, game_drawstate *ds,
1794 int tx, int ty, unsigned long val,
1795 int cl, int cc, int ch)
1799 draw_rect(dr, tx, ty, TILESIZE, TILESIZE, cc);
1800 if (val & PIECE_LBORDER)
1801 draw_rect(dr, tx, ty, HIGHLIGHT_WIDTH, TILESIZE,
1803 if (val & PIECE_RBORDER)
1804 draw_rect(dr, tx+TILESIZE-HIGHLIGHT_WIDTH, ty,
1805 HIGHLIGHT_WIDTH, TILESIZE, cl);
1806 if (val & PIECE_TBORDER)
1807 draw_rect(dr, tx, ty, TILESIZE, HIGHLIGHT_WIDTH, ch);
1808 if (val & PIECE_BBORDER)
1809 draw_rect(dr, tx, ty+TILESIZE-HIGHLIGHT_WIDTH,
1810 TILESIZE, HIGHLIGHT_WIDTH, cl);
1811 if (!((PIECE_BBORDER | PIECE_LBORDER) &~ val)) {
1812 draw_rect(dr, tx, ty+TILESIZE-HIGHLIGHT_WIDTH,
1813 HIGHLIGHT_WIDTH, HIGHLIGHT_WIDTH, cl);
1814 clip(dr, tx, ty+TILESIZE-HIGHLIGHT_WIDTH,
1815 HIGHLIGHT_WIDTH, HIGHLIGHT_WIDTH);
1817 coords[1] = ty + TILESIZE - HIGHLIGHT_WIDTH - 1;
1818 coords[2] = tx + HIGHLIGHT_WIDTH;
1819 coords[3] = ty + TILESIZE - HIGHLIGHT_WIDTH - 1;
1821 coords[5] = ty + TILESIZE;
1822 draw_polygon(dr, coords, 3, ch, ch);
1824 } else if (val & PIECE_BLCORNER) {
1825 draw_rect(dr, tx, ty+TILESIZE-HIGHLIGHT_WIDTH,
1826 HIGHLIGHT_WIDTH, HIGHLIGHT_WIDTH, ch);
1827 clip(dr, tx, ty+TILESIZE-HIGHLIGHT_WIDTH,
1828 HIGHLIGHT_WIDTH, HIGHLIGHT_WIDTH);
1830 coords[1] = ty + TILESIZE - HIGHLIGHT_WIDTH - 1;
1831 coords[2] = tx + HIGHLIGHT_WIDTH;
1832 coords[3] = ty + TILESIZE - HIGHLIGHT_WIDTH - 1;
1834 coords[5] = ty + TILESIZE;
1835 draw_polygon(dr, coords, 3, cl, cl);
1838 if (!((PIECE_TBORDER | PIECE_RBORDER) &~ val)) {
1839 draw_rect(dr, tx+TILESIZE-HIGHLIGHT_WIDTH, ty,
1840 HIGHLIGHT_WIDTH, HIGHLIGHT_WIDTH, cl);
1841 clip(dr, tx+TILESIZE-HIGHLIGHT_WIDTH, ty,
1842 HIGHLIGHT_WIDTH, HIGHLIGHT_WIDTH);
1843 coords[0] = tx + TILESIZE - HIGHLIGHT_WIDTH - 1;
1845 coords[2] = tx + TILESIZE;
1847 coords[4] = tx + TILESIZE - HIGHLIGHT_WIDTH - 1;
1848 coords[5] = ty + HIGHLIGHT_WIDTH;
1849 draw_polygon(dr, coords, 3, ch, ch);
1851 } else if (val & PIECE_TRCORNER) {
1852 draw_rect(dr, tx+TILESIZE-HIGHLIGHT_WIDTH, ty,
1853 HIGHLIGHT_WIDTH, HIGHLIGHT_WIDTH, ch);
1854 clip(dr, tx+TILESIZE-HIGHLIGHT_WIDTH, ty,
1855 HIGHLIGHT_WIDTH, HIGHLIGHT_WIDTH);
1856 coords[0] = tx + TILESIZE - HIGHLIGHT_WIDTH - 1;
1858 coords[2] = tx + TILESIZE;
1860 coords[4] = tx + TILESIZE - HIGHLIGHT_WIDTH - 1;
1861 coords[5] = ty + HIGHLIGHT_WIDTH;
1862 draw_polygon(dr, coords, 3, cl, cl);
1865 if (val & PIECE_TLCORNER)
1866 draw_rect(dr, tx, ty, HIGHLIGHT_WIDTH, HIGHLIGHT_WIDTH, ch);
1867 if (val & PIECE_BRCORNER)
1868 draw_rect(dr, tx+TILESIZE-HIGHLIGHT_WIDTH,
1869 ty+TILESIZE-HIGHLIGHT_WIDTH,
1870 HIGHLIGHT_WIDTH, HIGHLIGHT_WIDTH, cl);
1873 static void draw_piecepart(drawing *dr, game_drawstate *ds,
1874 int tx, int ty, unsigned long val,
1875 int cl, int cc, int ch)
1880 * Drawing the blocks is hellishly fiddly. The blocks don't
1881 * stretch to the full size of the tile; there's a border
1882 * around them of size BORDER_WIDTH. Then they have bevelled
1883 * borders of size HIGHLIGHT_WIDTH, and also rounded corners.
1885 * I tried for some time to find a clean and clever way to
1886 * figure out what needed drawing from the corner and border
1887 * flags, but in the end the cleanest way I could find was the
1888 * following. We divide the grid square into 25 parts by
1889 * ruling four horizontal and four vertical lines across it;
1890 * those lines are at BORDER_WIDTH and BORDER_WIDTH +
1891 * HIGHLIGHT_WIDTH from the top, from the bottom, from the
1892 * left and from the right. Then we carefully consider each of
1893 * the resulting 25 sections of square, and decide separately
1894 * what needs to go in it based on the flags. In complicated
1895 * cases there can be up to five possibilities affecting any
1896 * given section (no corner or border flags, just the corner
1897 * flag, one border flag, the other border flag, both border
1898 * flags). So there's a lot of very fiddly logic here and all
1899 * I could really think to do was give it my best shot and
1900 * then test it and correct all the typos. Not fun to write,
1901 * and I'm sure it isn't fun to read either, but it seems to
1906 x[1] = x[0] + BORDER_WIDTH;
1907 x[2] = x[1] + HIGHLIGHT_WIDTH;
1908 x[5] = tx + TILESIZE;
1909 x[4] = x[5] - BORDER_WIDTH;
1910 x[3] = x[4] - HIGHLIGHT_WIDTH;
1913 y[1] = y[0] + BORDER_WIDTH;
1914 y[2] = y[1] + HIGHLIGHT_WIDTH;
1915 y[5] = ty + TILESIZE;
1916 y[4] = y[5] - BORDER_WIDTH;
1917 y[3] = y[4] - HIGHLIGHT_WIDTH;
1919 #define RECT(p,q) x[p], y[q], x[(p)+1]-x[p], y[(q)+1]-y[q]
1921 maybe_rect(dr, RECT(0,0),
1922 (val & (PIECE_TLCORNER | PIECE_TBORDER |
1923 PIECE_LBORDER)) ? -1 : cc, -1);
1924 maybe_rect(dr, RECT(1,0),
1925 (val & PIECE_TLCORNER) ? ch : (val & PIECE_TBORDER) ? -1 :
1926 (val & PIECE_LBORDER) ? ch : cc, -1);
1927 maybe_rect(dr, RECT(2,0),
1928 (val & PIECE_TBORDER) ? -1 : cc, -1);
1929 maybe_rect(dr, RECT(3,0),
1930 (val & PIECE_TRCORNER) ? cl : (val & PIECE_TBORDER) ? -1 :
1931 (val & PIECE_RBORDER) ? cl : cc, -1);
1932 maybe_rect(dr, RECT(4,0),
1933 (val & (PIECE_TRCORNER | PIECE_TBORDER |
1934 PIECE_RBORDER)) ? -1 : cc, -1);
1935 maybe_rect(dr, RECT(0,1),
1936 (val & PIECE_TLCORNER) ? ch : (val & PIECE_LBORDER) ? -1 :
1937 (val & PIECE_TBORDER) ? ch : cc, -1);
1938 maybe_rect(dr, RECT(1,1),
1939 (val & PIECE_TLCORNER) ? cc : -1, -1);
1940 maybe_rect(dr, RECT(1,1),
1941 (val & PIECE_TLCORNER) ? ch | TYPE_TLCIRC :
1942 !((PIECE_TBORDER | PIECE_LBORDER) &~ val) ? ch | TYPE_BRCIRC :
1943 (val & (PIECE_TBORDER | PIECE_LBORDER)) ? ch : cc, -1);
1944 maybe_rect(dr, RECT(2,1),
1945 (val & PIECE_TBORDER) ? ch : cc, -1);
1946 maybe_rect(dr, RECT(3,1),
1947 (val & PIECE_TRCORNER) ? cc : -1, -1);
1948 maybe_rect(dr, RECT(3,1),
1949 (val & (PIECE_TBORDER | PIECE_RBORDER)) == PIECE_TBORDER ? ch :
1950 (val & (PIECE_TBORDER | PIECE_RBORDER)) == PIECE_RBORDER ? cl :
1951 !((PIECE_TBORDER|PIECE_RBORDER) &~ val) ? cl | TYPE_BLCIRC :
1952 (val & PIECE_TRCORNER) ? cl | TYPE_TRCIRC :
1954 maybe_rect(dr, RECT(4,1),
1955 (val & PIECE_TRCORNER) ? ch : (val & PIECE_RBORDER) ? -1 :
1956 (val & PIECE_TBORDER) ? ch : cc, -1);
1957 maybe_rect(dr, RECT(0,2),
1958 (val & PIECE_LBORDER) ? -1 : cc, -1);
1959 maybe_rect(dr, RECT(1,2),
1960 (val & PIECE_LBORDER) ? ch : cc, -1);
1961 maybe_rect(dr, RECT(2,2),
1963 maybe_rect(dr, RECT(3,2),
1964 (val & PIECE_RBORDER) ? cl : cc, -1);
1965 maybe_rect(dr, RECT(4,2),
1966 (val & PIECE_RBORDER) ? -1 : cc, -1);
1967 maybe_rect(dr, RECT(0,3),
1968 (val & PIECE_BLCORNER) ? cl : (val & PIECE_LBORDER) ? -1 :
1969 (val & PIECE_BBORDER) ? cl : cc, -1);
1970 maybe_rect(dr, RECT(1,3),
1971 (val & PIECE_BLCORNER) ? cc : -1, -1);
1972 maybe_rect(dr, RECT(1,3),
1973 (val & (PIECE_BBORDER | PIECE_LBORDER)) == PIECE_BBORDER ? cl :
1974 (val & (PIECE_BBORDER | PIECE_LBORDER)) == PIECE_LBORDER ? ch :
1975 !((PIECE_BBORDER|PIECE_LBORDER) &~ val) ? ch | TYPE_TRCIRC :
1976 (val & PIECE_BLCORNER) ? ch | TYPE_BLCIRC :
1978 maybe_rect(dr, RECT(2,3),
1979 (val & PIECE_BBORDER) ? cl : cc, -1);
1980 maybe_rect(dr, RECT(3,3),
1981 (val & PIECE_BRCORNER) ? cc : -1, -1);
1982 maybe_rect(dr, RECT(3,3),
1983 (val & PIECE_BRCORNER) ? cl | TYPE_BRCIRC :
1984 !((PIECE_BBORDER | PIECE_RBORDER) &~ val) ? cl | TYPE_TLCIRC :
1985 (val & (PIECE_BBORDER | PIECE_RBORDER)) ? cl : cc, -1);
1986 maybe_rect(dr, RECT(4,3),
1987 (val & PIECE_BRCORNER) ? cl : (val & PIECE_RBORDER) ? -1 :
1988 (val & PIECE_BBORDER) ? cl : cc, -1);
1989 maybe_rect(dr, RECT(0,4),
1990 (val & (PIECE_BLCORNER | PIECE_BBORDER |
1991 PIECE_LBORDER)) ? -1 : cc, -1);
1992 maybe_rect(dr, RECT(1,4),
1993 (val & PIECE_BLCORNER) ? ch : (val & PIECE_BBORDER) ? -1 :
1994 (val & PIECE_LBORDER) ? ch : cc, -1);
1995 maybe_rect(dr, RECT(2,4),
1996 (val & PIECE_BBORDER) ? -1 : cc, -1);
1997 maybe_rect(dr, RECT(3,4),
1998 (val & PIECE_BRCORNER) ? cl : (val & PIECE_BBORDER) ? -1 :
1999 (val & PIECE_RBORDER) ? cl : cc, -1);
2000 maybe_rect(dr, RECT(4,4),
2001 (val & (PIECE_BRCORNER | PIECE_BBORDER |
2002 PIECE_RBORDER)) ? -1 : cc, -1);
2007 static void draw_tile(drawing *dr, game_drawstate *ds,
2008 int x, int y, unsigned long val)
2010 int tx = COORD(x), ty = COORD(y);
2014 * Draw the tile background.
2016 if (val & BG_TARGET)
2019 cc = COL_BACKGROUND;
2022 if (val & FLASH_LOW)
2024 else if (val & FLASH_HIGH)
2027 draw_rect(dr, tx, ty, TILESIZE, TILESIZE, cc);
2028 if (val & BG_FORCEFIELD) {
2030 * Cattle-grid effect to indicate that nothing but the
2031 * main block can slide over this square.
2033 int n = 3 * (TILESIZE / (3*HIGHLIGHT_WIDTH));
2036 for (i = 1; i < n; i += 3) {
2037 draw_rect(dr, tx,ty+(TILESIZE*i/n), TILESIZE,HIGHLIGHT_WIDTH, cl);
2038 draw_rect(dr, tx+(TILESIZE*i/n),ty, HIGHLIGHT_WIDTH,TILESIZE, cl);
2043 * Draw the tile midground: a shadow of a block, for
2044 * displaying partial solutions.
2046 if (val & FG_SHADOW) {
2047 draw_piecepart(dr, ds, tx, ty, (val >> FG_SHADOWSH) & PIECE_MASK,
2052 * Draw the tile foreground, i.e. some section of a block or
2055 if (val & FG_WALL) {
2056 cc = COL_BACKGROUND;
2059 if (val & FLASH_LOW)
2061 else if (val & FLASH_HIGH)
2064 draw_wallpart(dr, ds, tx, ty, (val >> FG_MAINPIECESH) & PIECE_MASK,
2066 } else if (val & (FG_MAIN | FG_NORMAL)) {
2067 if (val & FG_DRAGGING)
2068 cc = (val & FG_MAIN ? COL_MAIN_DRAGGING : COL_DRAGGING);
2070 cc = (val & FG_MAIN ? COL_MAIN : COL_BACKGROUND);
2074 if (val & FLASH_LOW)
2076 else if (val & (FLASH_HIGH | FG_SOLVEPIECE))
2079 draw_piecepart(dr, ds, tx, ty, (val >> FG_MAINPIECESH) & PIECE_MASK,
2083 draw_update(dr, tx, ty, TILESIZE, TILESIZE);
2086 static unsigned long find_piecepart(int w, int h, int *dsf, int x, int y)
2089 int canon = dsf_canonify(dsf, i);
2090 unsigned long val = 0;
2092 if (x == 0 || canon != dsf_canonify(dsf, i-1))
2093 val |= PIECE_LBORDER;
2094 if (y== 0 || canon != dsf_canonify(dsf, i-w))
2095 val |= PIECE_TBORDER;
2096 if (x == w-1 || canon != dsf_canonify(dsf, i+1))
2097 val |= PIECE_RBORDER;
2098 if (y == h-1 || canon != dsf_canonify(dsf, i+w))
2099 val |= PIECE_BBORDER;
2100 if (!(val & (PIECE_TBORDER | PIECE_LBORDER)) &&
2101 canon != dsf_canonify(dsf, i-1-w))
2102 val |= PIECE_TLCORNER;
2103 if (!(val & (PIECE_TBORDER | PIECE_RBORDER)) &&
2104 canon != dsf_canonify(dsf, i+1-w))
2105 val |= PIECE_TRCORNER;
2106 if (!(val & (PIECE_BBORDER | PIECE_LBORDER)) &&
2107 canon != dsf_canonify(dsf, i-1+w))
2108 val |= PIECE_BLCORNER;
2109 if (!(val & (PIECE_BBORDER | PIECE_RBORDER)) &&
2110 canon != dsf_canonify(dsf, i+1+w))
2111 val |= PIECE_BRCORNER;
2115 static void game_redraw(drawing *dr, game_drawstate *ds,
2116 const game_state *oldstate, const game_state *state,
2117 int dir, const 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(const game_state *oldstate,
2279 const game_state *newstate, int dir, game_ui *ui)
2284 static float game_flash_length(const game_state *oldstate,
2285 const game_state *newstate, int dir, game_ui *ui)
2287 if (oldstate->completed < 0 && newstate->completed >= 0)
2293 static int game_status(const game_state *state)
2295 return state->completed ? +1 : 0;
2298 static int game_timing_state(const game_state *state, game_ui *ui)
2303 static void game_print_size(const game_params *params, float *x, float *y)
2307 static void game_print(drawing *dr, const game_state *state, int tilesize)
2312 #define thegame slide
2315 const struct game thegame = {
2316 "Slide", NULL, NULL,
2318 game_fetch_preset, NULL,
2323 TRUE, game_configure, custom_params,
2331 TRUE, game_can_format_as_text_now, game_text_format,
2339 PREFERRED_TILESIZE, game_compute_size, game_set_size,
2342 game_free_drawstate,
2347 FALSE, FALSE, game_print_size, game_print,
2348 TRUE, /* wants_statusbar */
2349 FALSE, game_timing_state,
2353 #ifdef STANDALONE_SOLVER
2357 int main(int argc, char **argv)
2361 char *id = NULL, *desc, *err;
2366 while (--argc > 0) {
2369 if (!strcmp(p, "-v")) {
2373 if (!strcmp(p, "-c")) {
2375 } else if (*p == '-') {
2376 fprintf(stderr, "%s: unrecognised option `%s'\n", argv[0], p);
2384 fprintf(stderr, "usage: %s [-c | -v] <game_id>\n", argv[0]);
2388 desc = strchr(id, ':');
2390 fprintf(stderr, "%s: game id expects a colon in it\n", argv[0]);
2395 p = default_params();
2396 decode_params(p, id);
2397 err = validate_desc(p, desc);
2399 fprintf(stderr, "%s: %s\n", argv[0], err);
2402 s = new_game(NULL, p, desc);
2404 ret = solve_board(s->w, s->h, s->board, s->imm->forcefield,
2405 s->tx, s->ty, -1, &moves);
2407 printf("No solution found\n");
2411 printf("%d moves required\n", ret);
2416 char *text = board_text_format(s->w, s->h, s->board,
2417 s->imm->forcefield);
2420 printf("position %d:\n%s", index, text);
2426 moveret = move_piece(s->w, s->h, s->board,
2427 s2->board, s->imm->forcefield,
2428 moves[index*2], moves[index*2+1]);