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]);