2 * slide.c: Implementation of the block-sliding puzzle `Klotski'.
9 * * try to generate a solution when Solve is pressed
10 * + from the start, or from here? From here, I fear.
11 * + hence, not much point saving the solution in an aux
13 * * Inertia-like method for telling the user the solution
14 * * standalone solver which draws diagrams
16 * - The dragging semantics are still subtly wrong in complex
19 * - Improve the generator.
20 * * actually, we seem to be mostly sensible already now. I
21 * want more choice over the type of main block and location
22 * of the exit/target, and I think I probably ought to give
23 * up on compactness and just bite the bullet and have the
24 * target area right outside the main wall, but mostly I
26 * * the move limit tends to make the game _slower_ to
27 * generate, which is odd. Perhaps investigate why.
29 * - Improve the graphics.
30 * * All the colours are a bit wishy-washy. _Some_ dark
31 * colours would surely not be excessive? Probably darken
32 * the tiles, the walls and the main block, and leave the
34 * * The cattle grid effect is still disgusting. Think of
35 * something completely different.
49 * The implementation of this game revolves around the insight
50 * which makes an exhaustive-search solver feasible: although
51 * there are many blocks which can be rearranged in many ways, any
52 * two blocks of the same shape are _indistinguishable_ and hence
53 * the number of _distinct_ board layouts is generally much
54 * smaller. So we adopt a representation for board layouts which
55 * is inherently canonical, i.e. there are no two distinct
56 * representations which encode indistinguishable layouts.
58 * The way we do this is to encode each square of the board, in
59 * the normal left-to-right top-to-bottom order, as being one of
60 * the following things:
61 * - the first square (in the given order) of a block (`anchor')
62 * - special case of the above: the anchor for the _main_ block
63 * (i.e. the one which the aim of the game is to get to the
65 * - a subsequent square of a block whose previous square was N
67 * - an impassable wall
69 * (We also separately store data about which board positions are
70 * forcefields only passable by the main block. We can't encode
71 * that in the main board data, because then the main block would
72 * destroy forcefields as it went over them.)
74 * Hence, for example, a 2x2 square block would be encoded as
75 * ANCHOR, followed by DIST(1), and w-2 squares later on there
76 * would be DIST(w-1) followed by DIST(1). So if you start at the
77 * last of those squares, the DIST numbers give you a linked list
78 * pointing back through all the other squares in the same block.
80 * So the solver simply does a bfs over all reachable positions,
81 * encoding them in this format and storing them in a tree234 to
82 * ensure it doesn't ever revisit an already-analysed position.
87 * The colours are arranged here so that every base colour is
88 * directly followed by its highlight colour and then its
89 * lowlight colour. Do not break this, or draw_tile() will get
96 COL_DRAGGING_HIGHLIGHT
,
97 COL_DRAGGING_LOWLIGHT
,
102 COL_MAIN_DRAGGING_HIGHLIGHT
,
103 COL_MAIN_DRAGGING_LOWLIGHT
,
105 COL_TARGET_HIGHLIGHT
,
111 * Board layout is a simple array of bytes. Each byte holds:
113 #define ANCHOR 255 /* top-left-most square of some piece */
114 #define MAINANCHOR 254 /* anchor of _main_ piece */
115 #define EMPTY 253 /* empty square */
116 #define WALL 252 /* immovable wall */
118 /* all other values indicate distance back to previous square of same block */
119 #define ISDIST(x) ( (unsigned char)((x)-1) <= MAXDIST-1 )
121 #define ISANCHOR(x) ( (x)==ANCHOR || (x)==MAINANCHOR )
122 #define ISBLOCK(x) ( ISANCHOR(x) || ISDIST(x) )
125 * MAXDIST is the largest DIST value we can encode. This must
126 * therefore also be the maximum puzzle width in theory (although
127 * solver running time will dictate a much smaller limit in
130 #define MAXWID MAXDIST
137 struct game_immutable_state
{
139 unsigned char *forcefield
;
144 unsigned char *board
;
145 int tx
, ty
; /* target coords for MAINANCHOR */
146 int minmoves
; /* for display only */
147 int lastmoved
, lastmoved_pos
; /* for move counting */
150 struct game_immutable_state
*imm
;
153 static game_params
*default_params(void)
155 game_params
*ret
= snew(game_params
);
164 static const struct game_params slide_presets
[] = {
170 static int game_fetch_preset(int i
, char **name
, game_params
**params
)
175 if (i
< 0 || i
>= lenof(slide_presets
))
178 ret
= snew(game_params
);
179 *ret
= slide_presets
[i
];
181 sprintf(str
, "%dx%d", ret
->w
, ret
->h
);
182 if (ret
->maxmoves
>= 0)
183 sprintf(str
+ strlen(str
), ", max %d moves", ret
->maxmoves
);
185 sprintf(str
+ strlen(str
), ", no move limit");
192 static void free_params(game_params
*params
)
197 static game_params
*dup_params(game_params
*params
)
199 game_params
*ret
= snew(game_params
);
200 *ret
= *params
; /* structure copy */
204 static void decode_params(game_params
*params
, char const *string
)
206 params
->w
= params
->h
= atoi(string
);
207 while (*string
&& isdigit((unsigned char)*string
)) string
++;
208 if (*string
== 'x') {
210 params
->h
= atoi(string
);
211 while (*string
&& isdigit((unsigned char)*string
)) string
++;
213 if (*string
== 'm') {
215 params
->maxmoves
= atoi(string
);
216 while (*string
&& isdigit((unsigned char)*string
)) string
++;
217 } else if (*string
== 'u') {
219 params
->maxmoves
= -1;
223 static char *encode_params(game_params
*params
, int full
)
227 sprintf(data
, "%dx%d", params
->w
, params
->h
);
228 if (params
->maxmoves
>= 0)
229 sprintf(data
+ strlen(data
), "m%d", params
->maxmoves
);
231 sprintf(data
+ strlen(data
), "u");
236 static config_item
*game_configure(game_params
*params
)
241 ret
= snewn(4, config_item
);
243 ret
[0].name
= "Width";
244 ret
[0].type
= C_STRING
;
245 sprintf(buf
, "%d", params
->w
);
246 ret
[0].sval
= dupstr(buf
);
249 ret
[1].name
= "Height";
250 ret
[1].type
= C_STRING
;
251 sprintf(buf
, "%d", params
->h
);
252 ret
[1].sval
= dupstr(buf
);
255 ret
[2].name
= "Solution length limit";
256 ret
[2].type
= C_STRING
;
257 sprintf(buf
, "%d", params
->maxmoves
);
258 ret
[2].sval
= dupstr(buf
);
269 static game_params
*custom_params(config_item
*cfg
)
271 game_params
*ret
= snew(game_params
);
273 ret
->w
= atoi(cfg
[0].sval
);
274 ret
->h
= atoi(cfg
[1].sval
);
275 ret
->maxmoves
= atoi(cfg
[2].sval
);
280 static char *validate_params(game_params
*params
, int full
)
282 if (params
->w
> MAXWID
)
283 return "Width must be at most " STR(MAXWID
);
286 return "Width must be at least 5";
288 return "Height must be at least 4";
293 static char *board_text_format(int w
, int h
, unsigned char *data
,
294 unsigned char *forcefield
)
297 int *dsf
= snew_dsf(wh
);
299 int retpos
, retlen
= (w
*2+2)*(h
*2+1)+1;
300 char *ret
= snewn(retlen
, char);
302 for (i
= 0; i
< wh
; i
++)
304 dsf_merge(dsf
, i
- data
[i
], i
);
306 for (y
= 0; y
< 2*h
+1; y
++) {
307 for (x
= 0; x
< 2*w
+1; x
++) {
309 int i
= (y
/2)*w
+(x
/2);
311 #define dtype(i) (ISBLOCK(data[i]) ? \
312 dsf_canonify(dsf, i) : data[i])
313 #define dchar(t) ((t)==EMPTY ? ' ' : (t)==WALL ? '#' : \
314 data[t] == MAINANCHOR ? '*' : '%')
316 if (y
% 2 && x
% 2) {
319 } else if (y
% 2 && !(x
% 2)) {
320 int j1
= (x
> 0 ?
dtype(i
-1) : -1);
321 int j2
= (x
< 2*w ?
dtype(i
) : -1);
326 } else if (!(y
% 2) && (x
% 2)) {
327 int j1
= (y
> 0 ?
dtype(i
-w
) : -1);
328 int j2
= (y
< 2*h ?
dtype(i
) : -1);
334 int j1
= (x
> 0 && y
> 0 ?
dtype(i
-w
-1) : -1);
335 int j2
= (x
> 0 && y
< 2*h ?
dtype(i
-1) : -1);
336 int j3
= (x
< 2*w
&& y
> 0 ?
dtype(i
-w
) : -1);
337 int j4
= (x
< 2*w
&& y
< 2*h ?
dtype(i
) : -1);
338 if (j1
== j2
&& j2
== j3
&& j3
== j4
)
340 else if (j1
== j2
&& j3
== j4
)
342 else if (j1
== j3
&& j2
== j4
)
348 assert(retpos
< retlen
);
351 assert(retpos
< retlen
);
352 ret
[retpos
++] = '\n';
354 assert(retpos
< retlen
);
355 ret
[retpos
++] = '\0';
356 assert(retpos
== retlen
);
361 /* ----------------------------------------------------------------------
366 * During solver execution, the set of visited board positions is
367 * stored as a tree234 of the following structures. `w', `h' and
368 * `data' are obvious in meaning; `dist' represents the minimum
369 * distance to reach this position from the starting point.
371 * `prev' links each board to the board position from which it was
372 * most efficiently derived.
381 static int boardcmp(void *av
, void *bv
)
383 struct board
*a
= (struct board
*)av
;
384 struct board
*b
= (struct board
*)bv
;
385 return memcmp(a
->data
, b
->data
, a
->w
* a
->h
);
388 static struct board
*newboard(int w
, int h
, unsigned char *data
)
390 struct board
*b
= malloc(sizeof(struct board
) + w
*h
);
391 b
->data
= (unsigned char *)b
+ sizeof(struct board
);
392 memcpy(b
->data
, data
, w
*h
);
401 * The actual solver. Given a board, attempt to find the minimum
402 * length of move sequence which moves MAINANCHOR to (tx,ty), or
403 * -1 if no solution exists. Returns that minimum length, and
404 * (FIXME) optionally also writes out the actual moves into an
405 * as-yet-unprovided parameter.
407 static int solve_board(int w
, int h
, unsigned char *board
,
408 unsigned char *forcefield
, int tx
, int ty
,
412 struct board
*b
, *b2
, *b3
;
413 int *next
, *anchors
, *which
;
414 int *movereached
, *movequeue
, mqhead
, mqtail
;
415 tree234
*sorted
, *queue
;
420 #ifdef SOLVER_DIAGNOSTICS
422 char *t
= board_text_format(w
, h
, board
);
423 for (i
= 0; i
< h
; i
++) {
424 for (j
= 0; j
< w
; j
++) {
425 int c
= board
[i
*w
+j
];
428 else if (c
== MAINANCHOR
)
430 else if (c
== ANCHOR
)
440 printf("Starting solver for:\n%s\n", t
);
445 sorted
= newtree234(boardcmp
);
446 queue
= newtree234(NULL
);
448 b
= newboard(w
, h
, board
);
451 addpos234(queue
, b
, 0);
454 next
= snewn(wh
, int);
455 anchors
= snewn(wh
, int);
456 which
= snewn(wh
, int);
457 movereached
= snewn(wh
, int);
458 movequeue
= snewn(wh
, int);
461 while ((b
= delpos234(queue
, 0)) != NULL
) {
463 if (movelimit
>= 0 && b
->dist
>= movelimit
) {
465 * The problem is not soluble in under `movelimit'
466 * moves, so we can quit right now.
471 if (b
->dist
!= lastdist
) {
472 #ifdef SOLVER_DIAGNOSTICS
473 printf("dist %d (%d)\n", b
->dist
, count234(sorted
));
478 * Find all the anchors and form a linked list of the
479 * squares within each block.
481 for (i
= 0; i
< wh
; i
++) {
485 if (ISANCHOR(b
->data
[i
])) {
488 } else if (ISDIST(b
->data
[i
])) {
496 * For each anchor, do an array-based BFS to find all the
497 * places we can slide it to.
499 for (i
= 0; i
< wh
; i
++) {
504 for (j
= 0; j
< wh
; j
++)
505 movereached
[j
] = FALSE
;
506 movequeue
[mqtail
++] = i
;
507 while (mqhead
< mqtail
) {
508 int pos
= movequeue
[mqhead
++];
511 * Try to move in each direction from here.
513 for (dir
= 0; dir
< 4; dir
++) {
514 int dx
= (dir
== 0 ?
-1 : dir
== 1 ?
+1 : 0);
515 int dy
= (dir
== 2 ?
-1 : dir
== 3 ?
+1 : 0);
516 int offset
= dy
*w
+ dx
;
517 int newpos
= pos
+ offset
;
521 * For each square involved in this block,
522 * check to see if the square d spaces away
523 * from it is either empty or part of the same
526 for (j
= i
; j
>= 0; j
= next
[j
]) {
527 int jy
= (pos
+j
-i
) / w
+ dy
, jx
= (pos
+j
-i
) % w
+ dx
;
528 if (jy
>= 0 && jy
< h
&& jx
>= 0 && jx
< w
&&
529 ((b
->data
[j
+d
] == EMPTY
|| which
[j
+d
] == i
) &&
530 (b
->data
[i
] == MAINANCHOR
|| !forcefield
[j
+d
])))
536 continue; /* this direction wasn't feasible */
539 * If we've already tried moving this piece
542 if (movereached
[newpos
])
544 movereached
[newpos
] = TRUE
;
545 movequeue
[mqtail
++] = newpos
;
548 * We have a viable move. Make it.
550 b2
= newboard(w
, h
, b
->data
);
551 for (j
= i
; j
>= 0; j
= next
[j
])
553 for (j
= i
; j
>= 0; j
= next
[j
])
554 b2
->data
[j
+d
] = b
->data
[j
];
556 b3
= add234(sorted
, b2
);
558 sfree(b2
); /* we already got one */
560 b2
->dist
= b
->dist
+ 1;
562 addpos234(queue
, b2
, qlen
++);
563 if (b2
->data
[ty
*w
+tx
] == MAINANCHOR
)
564 goto done
; /* search completed! */
577 ret
= -1; /* no solution */
581 while ((b
= delpos234(sorted
, 0)) != NULL
)
594 /* ----------------------------------------------------------------------
595 * Random board generation.
598 static void generate_board(int w
, int h
, int *rtx
, int *rty
, int *minmoves
,
599 random_state
*rs
, unsigned char **rboard
,
600 unsigned char **rforcefield
, int movelimit
)
603 unsigned char *board
, *board2
, *forcefield
;
604 unsigned char *tried_merge
;
606 int *list
, nlist
, pos
;
612 * Set up a board and fill it with singletons, except for a
615 board
= snewn(wh
, unsigned char);
616 forcefield
= snewn(wh
, unsigned char);
617 board2
= snewn(wh
, unsigned char);
618 memset(board
, ANCHOR
, wh
);
619 memset(forcefield
, FALSE
, wh
);
620 for (i
= 0; i
< w
; i
++)
621 board
[i
] = board
[i
+w
*(h
-1)] = WALL
;
622 for (i
= 0; i
< h
; i
++)
623 board
[i
*w
] = board
[i
*w
+(w
-1)] = WALL
;
625 tried_merge
= snewn(wh
* wh
, unsigned char);
626 memset(tried_merge
, 0, wh
*wh
);
630 * Invent a main piece at one extreme. (FIXME: vary the
631 * extreme, and the piece.)
633 board
[w
+1] = MAINANCHOR
;
634 board
[w
+2] = DIST(1);
635 board
[w
*2+1] = DIST(w
-1);
636 board
[w
*2+2] = DIST(1);
639 * Invent a target position. (FIXME: vary this too.)
643 forcefield
[ty
*w
+tx
+1] = forcefield
[(ty
+1)*w
+tx
+1] = TRUE
;
644 board
[ty
*w
+tx
+1] = board
[(ty
+1)*w
+tx
+1] = EMPTY
;
647 * Gradually remove singletons until the game becomes soluble.
649 for (j
= w
; j
-- > 0 ;)
650 for (i
= h
; i
-- > 0 ;)
651 if (board
[i
*w
+j
] == ANCHOR
) {
653 * See if the board is already soluble.
655 if ((moves
= solve_board(w
, h
, board
, forcefield
,
656 tx
, ty
, movelimit
)) >= 0)
660 * Otherwise, remove this piece.
662 board
[i
*w
+j
] = EMPTY
;
664 assert(!"We shouldn't get here");
668 * Make a list of all the inter-block edges on the board.
670 list
= snewn(wh
*2, int);
672 for (i
= 0; i
+1 < w
; i
++)
673 for (j
= 0; j
< h
; j
++)
674 list
[nlist
++] = (j
*w
+i
) * 2 + 0; /* edge to the right of j*w+i */
675 for (j
= 0; j
+1 < h
; j
++)
676 for (i
= 0; i
< w
; i
++)
677 list
[nlist
++] = (j
*w
+i
) * 2 + 1; /* edge below j*w+i */
680 * Now go through that list in random order, trying to merge
681 * the blocks on each side of each edge.
683 shuffle(list
, nlist
, sizeof(*list
), rs
);
689 y1
= y2
= pos
/ (w
*2);
690 x1
= x2
= (pos
/ 2) % w
;
699 * Immediately abandon the attempt if we've already tried
700 * to merge the same pair of blocks along a different
703 c1
= dsf_canonify(dsf
, p1
);
704 c2
= dsf_canonify(dsf
, p2
);
705 if (tried_merge
[c1
* wh
+ c2
])
709 * In order to be mergeable, these two squares must each
710 * either be, or belong to, a non-main anchor, and their
711 * anchors must also be distinct.
713 if (!ISBLOCK(board
[p1
]) || !ISBLOCK(board
[p2
]))
715 while (ISDIST(board
[p1
]))
717 while (ISDIST(board
[p2
]))
719 if (board
[p1
] == MAINANCHOR
|| board
[p2
] == MAINANCHOR
|| p1
== p2
)
723 * We can merge these blocks. Try it, and see if the
724 * puzzle remains soluble.
726 memcpy(board2
, board
, wh
);
728 while (p1
< wh
|| p2
< wh
) {
730 * p1 and p2 are the squares at the head of each block
731 * list. Pick the smaller one and put it on the output
738 assert(i
- j
<= MAXDIST
);
739 board
[i
] = DIST(i
- j
);
744 * Now advance whichever list that came from.
749 } while (p1
< wh
&& board
[p1
] != DIST(p1
-i
));
753 } while (p2
< wh
&& board
[p2
] != DIST(p2
-i
));
756 j
= solve_board(w
, h
, board
, forcefield
, tx
, ty
, movelimit
);
759 * Didn't work. Revert the merge.
761 memcpy(board
, board2
, wh
);
762 tried_merge
[c1
* wh
+ c2
] = tried_merge
[c2
* wh
+ c1
] = TRUE
;
768 dsf_merge(dsf
, c1
, c2
);
769 c
= dsf_canonify(dsf
, c1
);
770 for (i
= 0; i
< wh
; i
++)
771 tried_merge
[c
*wh
+i
] = (tried_merge
[c1
*wh
+i
] |
772 tried_merge
[c2
*wh
+i
]);
773 for (i
= 0; i
< wh
; i
++)
774 tried_merge
[i
*wh
+c
] = (tried_merge
[i
*wh
+c1
] |
775 tried_merge
[i
*wh
+c2
]);
784 *rforcefield
= forcefield
;
788 /* ----------------------------------------------------------------------
789 * End of solver/generator code.
792 static char *new_game_desc(game_params
*params
, random_state
*rs
,
793 char **aux
, int interactive
)
795 int w
= params
->w
, h
= params
->h
, wh
= w
*h
;
796 int tx
, ty
, minmoves
;
797 unsigned char *board
, *forcefield
;
801 generate_board(params
->w
, params
->h
, &tx
, &ty
, &minmoves
, rs
,
802 &board
, &forcefield
, params
->maxmoves
);
803 #ifdef GENERATOR_DIAGNOSTICS
805 char *t
= board_text_format(params
->w
, params
->h
, board
);
812 * Encode as a game ID.
814 ret
= snewn(wh
* 6 + 40, char);
818 if (ISDIST(board
[i
])) {
819 p
+= sprintf(p
, "d%d", board
[i
]);
823 int b
= board
[i
], f
= forcefield
[i
];
824 int c
= (b
== ANCHOR ?
'a' :
825 b
== MAINANCHOR ?
'm' :
827 /* b == WALL ? */ 'w');
831 while (i
< wh
&& board
[i
] == b
&& forcefield
[i
] == f
)
834 p
+= sprintf(p
, "%d", count
);
837 p
+= sprintf(p
, ",%d,%d,%d", tx
, ty
, minmoves
);
838 ret
= sresize(ret
, p
+1 - ret
, char);
841 * FIXME: generate an aux string
850 static char *validate_desc(game_params
*params
, char *desc
)
852 int w
= params
->w
, h
= params
->h
, wh
= w
*h
;
854 int mains
= 0, mpos
= -1;
855 int i
, j
, tx
, ty
, minmoves
;
858 active
= snewn(wh
, int);
859 link
= snewn(wh
, int);
862 while (*desc
&& *desc
!= ',') {
864 ret
= "Too much data in game description";
869 if (*desc
== 'f' || *desc
== 'F') {
872 ret
= "Expected another character after 'f' in game "
878 if (*desc
== 'd' || *desc
== 'D') {
882 if (!isdigit((unsigned char)*desc
)) {
883 ret
= "Expected a number after 'd' in game description";
887 while (*desc
&& isdigit((unsigned char)*desc
)) desc
++;
889 if (dist
<= 0 || dist
> i
) {
890 ret
= "Out-of-range number after 'd' in game description";
894 if (!active
[i
- dist
]) {
895 ret
= "Invalid back-reference in game description";
900 for (j
= i
; j
> 0; j
= link
[j
])
901 if (j
== i
-1 || j
== i
-w
)
904 ret
= "Disconnected piece in game description";
909 active
[link
[i
]] = FALSE
;
915 if (!strchr("aAmMeEwW", c
)) {
916 ret
= "Invalid character in game description";
919 if (isdigit((unsigned char)*desc
)) {
921 while (*desc
&& isdigit((unsigned char)*desc
)) desc
++;
923 if (i
+ count
> wh
) {
924 ret
= "Too much data in game description";
927 while (count
-- > 0) {
928 active
[i
] = (strchr("aAmM", c
) != NULL
);
930 if (strchr("mM", c
) != NULL
) {
939 ret
= (mains
== 0 ?
"No main piece specified in game description" :
940 "More than one main piece specified in game description");
944 ret
= "Not enough data in game description";
949 * Now read the target coordinates.
951 i
= sscanf(desc
, ",%d,%d,%d", &tx
, &ty
, &minmoves
);
953 ret
= "No target coordinates specified";
956 * (but minmoves is optional)
968 static game_state
*new_game(midend
*me
, game_params
*params
, char *desc
)
970 int w
= params
->w
, h
= params
->h
, wh
= w
*h
;
974 state
= snew(game_state
);
977 state
->board
= snewn(wh
, unsigned char);
978 state
->lastmoved
= state
->lastmoved_pos
= -1;
979 state
->movecount
= 0;
980 state
->imm
= snew(struct game_immutable_state
);
981 state
->imm
->refcount
= 1;
982 state
->imm
->forcefield
= snewn(wh
, unsigned char);
986 while (*desc
&& *desc
!= ',') {
997 if (*desc
== 'd' || *desc
== 'D') {
1002 while (*desc
&& isdigit((unsigned char)*desc
)) desc
++;
1004 state
->board
[i
] = DIST(dist
);
1005 state
->imm
->forcefield
[i
] = f
;
1012 if (isdigit((unsigned char)*desc
)) {
1014 while (*desc
&& isdigit((unsigned char)*desc
)) desc
++;
1016 assert(i
+ count
<= wh
);
1018 c
= (c
== 'a' || c
== 'A' ? ANCHOR
:
1019 c
== 'm' || c
== 'M' ? MAINANCHOR
:
1020 c
== 'e' || c
== 'E' ? EMPTY
:
1021 /* c == 'w' || c == 'W' ? */ WALL
);
1023 while (count
-- > 0) {
1024 state
->board
[i
] = c
;
1025 state
->imm
->forcefield
[i
] = f
;
1032 * Now read the target coordinates.
1034 state
->tx
= state
->ty
= 0;
1035 state
->minmoves
= -1;
1036 i
= sscanf(desc
, ",%d,%d,%d", &state
->tx
, &state
->ty
, &state
->minmoves
);
1038 if (state
->board
[state
->ty
*w
+state
->tx
] == MAINANCHOR
)
1039 state
->completed
= 0; /* already complete! */
1041 state
->completed
= -1;
1046 static game_state
*dup_game(game_state
*state
)
1048 int w
= state
->w
, h
= state
->h
, wh
= w
*h
;
1049 game_state
*ret
= snew(game_state
);
1053 ret
->board
= snewn(wh
, unsigned char);
1054 memcpy(ret
->board
, state
->board
, wh
);
1055 ret
->tx
= state
->tx
;
1056 ret
->ty
= state
->ty
;
1057 ret
->minmoves
= state
->minmoves
;
1058 ret
->lastmoved
= state
->lastmoved
;
1059 ret
->lastmoved_pos
= state
->lastmoved_pos
;
1060 ret
->movecount
= state
->movecount
;
1061 ret
->completed
= state
->completed
;
1062 ret
->imm
= state
->imm
;
1063 ret
->imm
->refcount
++;
1068 static void free_game(game_state
*state
)
1070 if (--state
->imm
->refcount
<= 0) {
1071 sfree(state
->imm
->forcefield
);
1074 sfree(state
->board
);
1078 static char *solve_game(game_state
*state
, game_state
*currstate
,
1079 char *aux
, char **error
)
1082 * FIXME: we have a solver, so use it
1084 * FIXME: we should have generated an aux string, so use that
1089 static char *game_text_format(game_state
*state
)
1091 return board_text_format(state
->w
, state
->h
, state
->board
,
1092 state
->imm
->forcefield
);
1098 int drag_offset_x
, drag_offset_y
;
1100 unsigned char *reachable
;
1101 int *bfs_queue
; /* used as scratch in interpret_move */
1104 static game_ui
*new_ui(game_state
*state
)
1106 int w
= state
->w
, h
= state
->h
, wh
= w
*h
;
1107 game_ui
*ui
= snew(game_ui
);
1109 ui
->dragging
= FALSE
;
1110 ui
->drag_anchor
= ui
->drag_currpos
= -1;
1111 ui
->drag_offset_x
= ui
->drag_offset_y
= -1;
1112 ui
->reachable
= snewn(wh
, unsigned char);
1113 memset(ui
->reachable
, 0, wh
);
1114 ui
->bfs_queue
= snewn(wh
, int);
1119 static void free_ui(game_ui
*ui
)
1121 sfree(ui
->bfs_queue
);
1122 sfree(ui
->reachable
);
1126 static char *encode_ui(game_ui
*ui
)
1131 static void decode_ui(game_ui
*ui
, char *encoding
)
1135 static void game_changed_state(game_ui
*ui
, game_state
*oldstate
,
1136 game_state
*newstate
)
1140 #define PREFERRED_TILESIZE 32
1141 #define TILESIZE (ds->tilesize)
1142 #define BORDER (TILESIZE/2)
1143 #define COORD(x) ( (x) * TILESIZE + BORDER )
1144 #define FROMCOORD(x) ( ((x) - BORDER + TILESIZE) / TILESIZE - 1 )
1145 #define BORDER_WIDTH (1 + TILESIZE/20)
1146 #define HIGHLIGHT_WIDTH (1 + TILESIZE/16)
1148 #define FLASH_INTERVAL 0.10F
1149 #define FLASH_TIME 3*FLASH_INTERVAL
1151 struct game_drawstate
{
1154 unsigned long *grid
; /* what's currently displayed */
1158 static char *interpret_move(game_state
*state
, game_ui
*ui
, game_drawstate
*ds
,
1159 int x
, int y
, int button
)
1161 int w
= state
->w
, h
= state
->h
, wh
= w
*h
;
1165 if (button
== LEFT_BUTTON
) {
1169 if (tx
< 0 || tx
>= w
|| ty
< 0 || ty
>= h
||
1170 !ISBLOCK(state
->board
[ty
*w
+tx
]))
1171 return NULL
; /* this click has no effect */
1174 * User has clicked on a block. Find the block's anchor
1175 * and register that we've started dragging it.
1178 while (ISDIST(state
->board
[i
]))
1179 i
-= state
->board
[i
];
1180 assert(i
>= 0 && i
< wh
);
1182 ui
->dragging
= TRUE
;
1183 ui
->drag_anchor
= i
;
1184 ui
->drag_offset_x
= tx
- (i
% w
);
1185 ui
->drag_offset_y
= ty
- (i
/ w
);
1186 ui
->drag_currpos
= i
;
1189 * Now we immediately bfs out from the current location of
1190 * the anchor, to find all the places to which this block
1193 memset(ui
->reachable
, FALSE
, wh
);
1195 ui
->reachable
[i
] = TRUE
;
1196 ui
->bfs_queue
[qtail
++] = i
;
1197 for (j
= i
; j
< wh
; j
++)
1198 if (state
->board
[j
] == DIST(j
- i
))
1200 while (qhead
< qtail
) {
1201 int pos
= ui
->bfs_queue
[qhead
++];
1202 int x
= pos
% w
, y
= pos
/ w
;
1205 for (dir
= 0; dir
< 4; dir
++) {
1206 int dx
= (dir
== 0 ?
-1 : dir
== 1 ?
+1 : 0);
1207 int dy
= (dir
== 2 ?
-1 : dir
== 3 ?
+1 : 0);
1210 if (x
+ dx
< 0 || x
+ dx
>= w
||
1211 y
+ dy
< 0 || y
+ dy
>= h
)
1214 newpos
= pos
+ dy
*w
+ dx
;
1215 if (ui
->reachable
[newpos
])
1216 continue; /* already done this one */
1219 * Now search the grid to see if the block we're
1220 * dragging could fit into this space.
1222 for (j
= i
; j
>= 0; j
= (ISDIST(state
->board
[j
]) ?
1223 j
- state
->board
[j
] : -1)) {
1224 int jx
= (j
+pos
-ui
->drag_anchor
) % w
;
1225 int jy
= (j
+pos
-ui
->drag_anchor
) / w
;
1228 if (jx
+ dx
< 0 || jx
+ dx
>= w
||
1229 jy
+ dy
< 0 || jy
+ dy
>= h
)
1230 break; /* this position isn't valid at all */
1232 j2
= (j
+pos
-ui
->drag_anchor
) + dy
*w
+ dx
;
1234 if (state
->board
[j2
] == EMPTY
&&
1235 (!state
->imm
->forcefield
[j2
] ||
1236 state
->board
[ui
->drag_anchor
] == MAINANCHOR
))
1238 while (ISDIST(state
->board
[j2
]))
1239 j2
-= state
->board
[j2
];
1240 assert(j2
>= 0 && j2
< wh
);
1241 if (j2
== ui
->drag_anchor
)
1249 * If we got to the end of that loop without
1250 * disqualifying this position, mark it as
1251 * reachable for this drag.
1253 ui
->reachable
[newpos
] = TRUE
;
1254 ui
->bfs_queue
[qtail
++] = newpos
;
1260 * And that's it. Update the display to reflect the start
1264 } else if (button
== LEFT_DRAG
&& ui
->dragging
) {
1268 tx
-= ui
->drag_offset_x
;
1269 ty
-= ui
->drag_offset_y
;
1270 if (tx
< 0 || tx
>= w
|| ty
< 0 || ty
>= h
||
1271 !ui
->reachable
[ty
*w
+tx
])
1272 return NULL
; /* this drag has no effect */
1274 ui
->drag_currpos
= ty
*w
+tx
;
1276 } else if (button
== LEFT_RELEASE
&& ui
->dragging
) {
1277 char data
[256], *str
;
1280 * Terminate the drag, and if the piece has actually moved
1281 * then return a move string quoting the old and new
1282 * locations of the piece's anchor.
1284 if (ui
->drag_anchor
!= ui
->drag_currpos
) {
1285 sprintf(data
, "M%d-%d", ui
->drag_anchor
, ui
->drag_currpos
);
1288 str
= ""; /* null move; just update the UI */
1290 ui
->dragging
= FALSE
;
1291 ui
->drag_anchor
= ui
->drag_currpos
= -1;
1292 ui
->drag_offset_x
= ui
->drag_offset_y
= -1;
1293 memset(ui
->reachable
, 0, wh
);
1301 static int move_piece(int w
, int h
, const unsigned char *src
,
1302 unsigned char *dst
, unsigned char *ff
, int from
, int to
)
1307 if (!ISANCHOR(dst
[from
]))
1311 * Scan to the far end of the piece's linked list.
1313 for (i
= j
= from
; j
< wh
; j
++)
1314 if (src
[j
] == DIST(j
- i
))
1318 * Remove the piece from its old location in the new
1321 for (j
= i
; j
>= 0; j
= (ISDIST(src
[j
]) ? j
- src
[j
] : -1))
1325 * And put it back in at the new location.
1327 for (j
= i
; j
>= 0; j
= (ISDIST(src
[j
]) ? j
- src
[j
] : -1)) {
1328 int jn
= j
+ to
- from
;
1329 if (jn
< 0 || jn
>= wh
)
1331 if (dst
[jn
] == EMPTY
&& (!ff
[jn
] || src
[from
] == MAINANCHOR
)) {
1341 static game_state
*execute_move(game_state
*state
, char *move
)
1343 int w
= state
->w
, h
= state
->h
/* , wh = w*h */;
1346 game_state
*ret
= dup_game(state
);
1352 if (sscanf(move
, "%d-%d%n", &a1
, &a2
, &n
) != 2 ||
1353 !move_piece(w
, h
, state
->board
, ret
->board
,
1354 state
->imm
->forcefield
, a1
, a2
)) {
1358 if (a1
== ret
->lastmoved
) {
1360 * If the player has moved the same piece as they
1361 * moved last time, don't increment the move
1362 * count. In fact, if they've put the piece back
1363 * where it started from, _decrement_ the move
1366 if (a2
== ret
->lastmoved_pos
) {
1367 ret
->movecount
--; /* reverted last move */
1368 ret
->lastmoved
= ret
->lastmoved_pos
= -1;
1370 ret
->lastmoved
= a2
;
1371 /* don't change lastmoved_pos */
1374 ret
->lastmoved
= a2
;
1375 ret
->lastmoved_pos
= a1
;
1378 if (ret
->board
[a2
] == MAINANCHOR
&&
1379 a2
== ret
->ty
* w
+ ret
->tx
&& ret
->completed
< 0)
1380 ret
->completed
= ret
->movecount
;
1397 /* ----------------------------------------------------------------------
1401 static void game_compute_size(game_params
*params
, int tilesize
,
1404 /* fool the macros */
1405 struct dummy
{ int tilesize
; } dummy
= { tilesize
}, *ds
= &dummy
;
1407 *x
= params
->w
* TILESIZE
+ 2*BORDER
;
1408 *y
= params
->h
* TILESIZE
+ 2*BORDER
;
1411 static void game_set_size(drawing
*dr
, game_drawstate
*ds
,
1412 game_params
*params
, int tilesize
)
1414 ds
->tilesize
= tilesize
;
1417 static void raise_colour(float *target
, float *src
, float *limit
)
1420 for (i
= 0; i
< 3; i
++)
1421 target
[i
] = (2*src
[i
] + limit
[i
]) / 3;
1424 static float *game_colours(frontend
*fe
, int *ncolours
)
1426 float *ret
= snewn(3 * NCOLOURS
, float);
1428 game_mkhighlight(fe
, ret
, COL_BACKGROUND
, COL_HIGHLIGHT
, COL_LOWLIGHT
);
1431 * When dragging a tile, we light it up a bit.
1433 raise_colour(ret
+3*COL_DRAGGING
,
1434 ret
+3*COL_BACKGROUND
, ret
+3*COL_HIGHLIGHT
);
1435 raise_colour(ret
+3*COL_DRAGGING_HIGHLIGHT
,
1436 ret
+3*COL_HIGHLIGHT
, ret
+3*COL_HIGHLIGHT
);
1437 raise_colour(ret
+3*COL_DRAGGING_LOWLIGHT
,
1438 ret
+3*COL_LOWLIGHT
, ret
+3*COL_HIGHLIGHT
);
1441 * The main tile is tinted blue.
1443 ret
[COL_MAIN
* 3 + 0] = ret
[COL_BACKGROUND
* 3 + 0];
1444 ret
[COL_MAIN
* 3 + 1] = ret
[COL_BACKGROUND
* 3 + 1];
1445 ret
[COL_MAIN
* 3 + 2] = ret
[COL_HIGHLIGHT
* 3 + 2];
1446 game_mkhighlight_specific(fe
, ret
, COL_MAIN
,
1447 COL_MAIN_HIGHLIGHT
, COL_MAIN_LOWLIGHT
);
1450 * And we light that up a bit too when dragging.
1452 raise_colour(ret
+3*COL_MAIN_DRAGGING
,
1453 ret
+3*COL_MAIN
, ret
+3*COL_MAIN_HIGHLIGHT
);
1454 raise_colour(ret
+3*COL_MAIN_DRAGGING_HIGHLIGHT
,
1455 ret
+3*COL_MAIN_HIGHLIGHT
, ret
+3*COL_MAIN_HIGHLIGHT
);
1456 raise_colour(ret
+3*COL_MAIN_DRAGGING_LOWLIGHT
,
1457 ret
+3*COL_MAIN_LOWLIGHT
, ret
+3*COL_MAIN_HIGHLIGHT
);
1460 * The target area on the floor is tinted green.
1462 ret
[COL_TARGET
* 3 + 0] = ret
[COL_BACKGROUND
* 3 + 0];
1463 ret
[COL_TARGET
* 3 + 1] = ret
[COL_HIGHLIGHT
* 3 + 1];
1464 ret
[COL_TARGET
* 3 + 2] = ret
[COL_BACKGROUND
* 3 + 2];
1465 game_mkhighlight_specific(fe
, ret
, COL_TARGET
,
1466 COL_TARGET_HIGHLIGHT
, COL_TARGET_LOWLIGHT
);
1468 *ncolours
= NCOLOURS
;
1472 static game_drawstate
*game_new_drawstate(drawing
*dr
, game_state
*state
)
1474 int w
= state
->w
, h
= state
->h
, wh
= w
*h
;
1475 struct game_drawstate
*ds
= snew(struct game_drawstate
);
1481 ds
->started
= FALSE
;
1482 ds
->grid
= snewn(wh
, unsigned long);
1483 for (i
= 0; i
< wh
; i
++)
1484 ds
->grid
[i
] = ~(unsigned long)0;
1489 static void game_free_drawstate(drawing
*dr
, game_drawstate
*ds
)
1495 #define BG_NORMAL 0x00000001UL
1496 #define BG_TARGET 0x00000002UL
1497 #define BG_FORCEFIELD 0x00000004UL
1498 #define FLASH_LOW 0x00000008UL
1499 #define FLASH_HIGH 0x00000010UL
1500 #define FG_WALL 0x00000020UL
1501 #define FG_MAIN 0x00000040UL
1502 #define FG_NORMAL 0x00000080UL
1503 #define FG_DRAGGING 0x00000100UL
1504 #define FG_LBORDER 0x00000200UL
1505 #define FG_TBORDER 0x00000400UL
1506 #define FG_RBORDER 0x00000800UL
1507 #define FG_BBORDER 0x00001000UL
1508 #define FG_TLCORNER 0x00002000UL
1509 #define FG_TRCORNER 0x00004000UL
1510 #define FG_BLCORNER 0x00008000UL
1511 #define FG_BRCORNER 0x00010000UL
1516 #define TYPE_MASK 0xF000
1517 #define COL_MASK 0x0FFF
1518 #define TYPE_RECT 0x0000
1519 #define TYPE_TLCIRC 0x4000
1520 #define TYPE_TRCIRC 0x5000
1521 #define TYPE_BLCIRC 0x6000
1522 #define TYPE_BRCIRC 0x7000
1523 static void maybe_rect(drawing
*dr
, int x
, int y
, int w
, int h
, int coltype
)
1525 int colour
= coltype
& COL_MASK
, type
= coltype
& TYPE_MASK
;
1527 if (colour
> NCOLOURS
)
1529 if (type
== TYPE_RECT
) {
1530 draw_rect(dr
, x
, y
, w
, h
, colour
);
1534 clip(dr
, x
, y
, w
, h
);
1544 draw_circle(dr
, cx
, cy
, r
, colour
, colour
);
1550 static void draw_tile(drawing
*dr
, game_drawstate
*ds
,
1551 int x
, int y
, unsigned long val
)
1553 int tx
= COORD(x
), ty
= COORD(y
);
1557 * Draw the tile background.
1559 if (val
& BG_TARGET
)
1562 cc
= COL_BACKGROUND
;
1565 if (val
& FLASH_LOW
)
1567 else if (val
& FLASH_HIGH
)
1570 draw_rect(dr
, tx
, ty
, TILESIZE
, TILESIZE
, cc
);
1571 if (val
& BG_FORCEFIELD
) {
1573 * Cattle-grid effect to indicate that nothing but the
1574 * main block can slide over this square.
1576 int n
= 3 * (TILESIZE
/ (3*HIGHLIGHT_WIDTH
));
1579 for (i
= 1; i
< n
; i
+= 3) {
1580 draw_rect(dr
, tx
,ty
+(TILESIZE
*i
/n
), TILESIZE
,HIGHLIGHT_WIDTH
, cl
);
1581 draw_rect(dr
, tx
+(TILESIZE
*i
/n
),ty
, HIGHLIGHT_WIDTH
,TILESIZE
, cl
);
1586 * Draw the tile foreground, i.e. some section of a block or
1589 if (val
& FG_WALL
) {
1590 cc
= COL_BACKGROUND
;
1593 if (val
& FLASH_LOW
)
1595 else if (val
& FLASH_HIGH
)
1598 draw_rect(dr
, tx
, ty
, TILESIZE
, TILESIZE
, cc
);
1599 if (val
& FG_LBORDER
)
1600 draw_rect(dr
, tx
, ty
, HIGHLIGHT_WIDTH
, TILESIZE
,
1602 if (val
& FG_RBORDER
)
1603 draw_rect(dr
, tx
+TILESIZE
-HIGHLIGHT_WIDTH
, ty
,
1604 HIGHLIGHT_WIDTH
, TILESIZE
, cl
);
1605 if (val
& FG_TBORDER
)
1606 draw_rect(dr
, tx
, ty
, TILESIZE
, HIGHLIGHT_WIDTH
, ch
);
1607 if (val
& FG_BBORDER
)
1608 draw_rect(dr
, tx
, ty
+TILESIZE
-HIGHLIGHT_WIDTH
,
1609 TILESIZE
, HIGHLIGHT_WIDTH
, cl
);
1610 if (!((FG_BBORDER
| FG_LBORDER
) &~ val
))
1611 draw_rect(dr
, tx
, ty
+TILESIZE
-HIGHLIGHT_WIDTH
,
1612 HIGHLIGHT_WIDTH
, HIGHLIGHT_WIDTH
, cc
);
1613 if (!((FG_TBORDER
| FG_RBORDER
) &~ val
))
1614 draw_rect(dr
, tx
+TILESIZE
-HIGHLIGHT_WIDTH
, ty
,
1615 HIGHLIGHT_WIDTH
, HIGHLIGHT_WIDTH
, cc
);
1616 if (val
& FG_TLCORNER
)
1617 draw_rect(dr
, tx
, ty
, HIGHLIGHT_WIDTH
, HIGHLIGHT_WIDTH
, ch
);
1618 if (val
& FG_BRCORNER
)
1619 draw_rect(dr
, tx
+TILESIZE
-HIGHLIGHT_WIDTH
,
1620 ty
+TILESIZE
-HIGHLIGHT_WIDTH
,
1621 HIGHLIGHT_WIDTH
, HIGHLIGHT_WIDTH
, cl
);
1622 } else if (val
& (FG_MAIN
| FG_NORMAL
)) {
1625 if (val
& FG_DRAGGING
)
1626 cc
= (val
& FG_MAIN ? COL_MAIN_DRAGGING
: COL_DRAGGING
);
1628 cc
= (val
& FG_MAIN ? COL_MAIN
: COL_BACKGROUND
);
1632 if (val
& FLASH_LOW
)
1634 else if (val
& FLASH_HIGH
)
1638 * Drawing the blocks is hellishly fiddly. The blocks
1639 * don't stretch to the full size of the tile; there's a
1640 * border around them of size BORDER_WIDTH. Then they have
1641 * bevelled borders of size HIGHLIGHT_WIDTH, and also
1644 * I tried for some time to find a clean and clever way to
1645 * figure out what needed drawing from the corner and
1646 * border flags, but in the end the cleanest way I could
1647 * find was the following. We divide the grid square into
1648 * 25 parts by ruling four horizontal and four vertical
1649 * lines across it; those lines are at BORDER_WIDTH and
1650 * BORDER_WIDTH+HIGHLIGHT_WIDTH from the top, from the
1651 * bottom, from the left and from the right. Then we
1652 * carefully consider each of the resulting 25 sections of
1653 * square, and decide separately what needs to go in it
1654 * based on the flags. In complicated cases there can be
1655 * up to five possibilities affecting any given section
1656 * (no corner or border flags, just the corner flag, one
1657 * border flag, the other border flag, both border flags).
1658 * So there's a lot of very fiddly logic here and all I
1659 * could really think to do was give it my best shot and
1660 * then test it and correct all the typos. Not fun to
1661 * write, and I'm sure it isn't fun to read either, but it
1666 x
[1] = x
[0] + BORDER_WIDTH
;
1667 x
[2] = x
[1] + HIGHLIGHT_WIDTH
;
1668 x
[5] = tx
+ TILESIZE
;
1669 x
[4] = x
[5] - BORDER_WIDTH
;
1670 x
[3] = x
[4] - HIGHLIGHT_WIDTH
;
1673 y
[1] = y
[0] + BORDER_WIDTH
;
1674 y
[2] = y
[1] + HIGHLIGHT_WIDTH
;
1675 y
[5] = ty
+ TILESIZE
;
1676 y
[4] = y
[5] - BORDER_WIDTH
;
1677 y
[3] = y
[4] - HIGHLIGHT_WIDTH
;
1679 #define RECT(p,q) x[p], y[q], x[(p)+1]-x[p], y[(q)+1]-y[q]
1681 maybe_rect(dr
, RECT(0,0),
1682 (val
& (FG_TLCORNER
| FG_TBORDER
| FG_LBORDER
)) ?
-1 : cc
);
1683 maybe_rect(dr
, RECT(1,0),
1684 (val
& FG_TLCORNER
) ? ch
: (val
& FG_TBORDER
) ?
-1 :
1685 (val
& FG_LBORDER
) ? ch
: cc
);
1686 maybe_rect(dr
, RECT(2,0),
1687 (val
& FG_TBORDER
) ?
-1 : cc
);
1688 maybe_rect(dr
, RECT(3,0),
1689 (val
& FG_TRCORNER
) ? cl
: (val
& FG_TBORDER
) ?
-1 :
1690 (val
& FG_RBORDER
) ? cl
: cc
);
1691 maybe_rect(dr
, RECT(4,0),
1692 (val
& (FG_TRCORNER
| FG_TBORDER
| FG_RBORDER
)) ?
-1 : cc
);
1693 maybe_rect(dr
, RECT(0,1),
1694 (val
& FG_TLCORNER
) ? ch
: (val
& FG_LBORDER
) ?
-1 :
1695 (val
& FG_TBORDER
) ? ch
: cc
);
1696 maybe_rect(dr
, RECT(1,1),
1697 (val
& FG_TLCORNER
) ? cc
: -1);
1698 maybe_rect(dr
, RECT(1,1),
1699 (val
& FG_TLCORNER
) ? ch
| TYPE_TLCIRC
:
1700 !((FG_TBORDER
| FG_LBORDER
) &~ val
) ? ch
| TYPE_BRCIRC
:
1701 (val
& (FG_TBORDER
| FG_LBORDER
)) ? ch
: cc
);
1702 maybe_rect(dr
, RECT(2,1),
1703 (val
& FG_TBORDER
) ? ch
: cc
);
1704 maybe_rect(dr
, RECT(3,1),
1705 (val
& (FG_TBORDER
| FG_RBORDER
)) == FG_TBORDER ? ch
:
1706 (val
& (FG_TBORDER
| FG_RBORDER
)) == FG_RBORDER ? cl
:
1707 !((FG_TBORDER
|FG_RBORDER
) &~ val
) ? cc
| TYPE_BLCIRC
: cc
);
1708 maybe_rect(dr
, RECT(4,1),
1709 (val
& FG_TRCORNER
) ? ch
: (val
& FG_RBORDER
) ?
-1 :
1710 (val
& FG_TBORDER
) ? ch
: cc
);
1711 maybe_rect(dr
, RECT(0,2),
1712 (val
& FG_LBORDER
) ?
-1 : cc
);
1713 maybe_rect(dr
, RECT(1,2),
1714 (val
& FG_LBORDER
) ? ch
: cc
);
1715 maybe_rect(dr
, RECT(2,2),
1717 maybe_rect(dr
, RECT(3,2),
1718 (val
& FG_RBORDER
) ? cl
: cc
);
1719 maybe_rect(dr
, RECT(4,2),
1720 (val
& FG_RBORDER
) ?
-1 : cc
);
1721 maybe_rect(dr
, RECT(0,3),
1722 (val
& FG_BLCORNER
) ? cl
: (val
& FG_LBORDER
) ?
-1 :
1723 (val
& FG_BBORDER
) ? cl
: cc
);
1724 maybe_rect(dr
, RECT(1,3),
1725 (val
& (FG_BBORDER
| FG_LBORDER
)) == FG_BBORDER ? cl
:
1726 (val
& (FG_BBORDER
| FG_LBORDER
)) == FG_LBORDER ? ch
:
1727 !((FG_BBORDER
|FG_LBORDER
) &~ val
) ? cc
| TYPE_TRCIRC
: cc
);
1728 maybe_rect(dr
, RECT(2,3),
1729 (val
& FG_BBORDER
) ? cl
: cc
);
1730 maybe_rect(dr
, RECT(3,3),
1731 (val
& FG_BRCORNER
) ? cc
: -1);
1732 maybe_rect(dr
, RECT(3,3),
1733 (val
& FG_BRCORNER
) ? cl
| TYPE_BRCIRC
:
1734 !((FG_BBORDER
| FG_RBORDER
) &~ val
) ? cl
| TYPE_TLCIRC
:
1735 (val
& (FG_BBORDER
| FG_RBORDER
)) ? cl
: cc
);
1736 maybe_rect(dr
, RECT(4,3),
1737 (val
& FG_BRCORNER
) ? cl
: (val
& FG_RBORDER
) ?
-1 :
1738 (val
& FG_BBORDER
) ? cl
: cc
);
1739 maybe_rect(dr
, RECT(0,4),
1740 (val
& (FG_BLCORNER
| FG_BBORDER
| FG_LBORDER
)) ?
-1 : cc
);
1741 maybe_rect(dr
, RECT(1,4),
1742 (val
& FG_BLCORNER
) ? ch
: (val
& FG_BBORDER
) ?
-1 :
1743 (val
& FG_LBORDER
) ? ch
: cc
);
1744 maybe_rect(dr
, RECT(2,4),
1745 (val
& FG_BBORDER
) ?
-1 : cc
);
1746 maybe_rect(dr
, RECT(3,4),
1747 (val
& FG_BRCORNER
) ? cl
: (val
& FG_BBORDER
) ?
-1 :
1748 (val
& FG_RBORDER
) ? cl
: cc
);
1749 maybe_rect(dr
, RECT(4,4),
1750 (val
& (FG_BRCORNER
| FG_BBORDER
| FG_RBORDER
)) ?
-1 : cc
);
1756 draw_update(dr
, tx
, ty
, TILESIZE
, TILESIZE
);
1759 static void game_redraw(drawing
*dr
, game_drawstate
*ds
, game_state
*oldstate
,
1760 game_state
*state
, int dir
, game_ui
*ui
,
1761 float animtime
, float flashtime
)
1763 int w
= state
->w
, h
= state
->h
, wh
= w
*h
;
1764 unsigned char *board
;
1766 int x
, y
, mainanchor
, mainpos
, dragpos
;
1770 * The initial contents of the window are not guaranteed
1771 * and can vary with front ends. To be on the safe side,
1772 * all games should start by drawing a big
1773 * background-colour rectangle covering the whole window.
1775 draw_rect(dr
, 0, 0, 10*ds
->tilesize
, 10*ds
->tilesize
, COL_BACKGROUND
);
1780 * Construct the board we'll be displaying (which may be
1781 * different from the one in state if ui describes a drag in
1784 board
= snewn(wh
, unsigned char);
1785 memcpy(board
, state
->board
, wh
);
1787 int mpret
= move_piece(w
, h
, state
->board
, board
,
1788 state
->imm
->forcefield
,
1789 ui
->drag_anchor
, ui
->drag_currpos
);
1794 * Build a dsf out of that board, so we can conveniently tell
1795 * which edges are connected and which aren't.
1799 for (y
= 0; y
< h
; y
++)
1800 for (x
= 0; x
< w
; x
++) {
1803 if (ISDIST(board
[i
]))
1804 dsf_merge(dsf
, i
, i
- board
[i
]);
1805 if (board
[i
] == MAINANCHOR
)
1807 if (board
[i
] == WALL
) {
1808 if (x
> 0 && board
[i
-1] == WALL
)
1809 dsf_merge(dsf
, i
, i
-1);
1810 if (y
> 0 && board
[i
-w
] == WALL
)
1811 dsf_merge(dsf
, i
, i
-w
);
1814 assert(mainanchor
>= 0);
1815 mainpos
= dsf_canonify(dsf
, mainanchor
);
1816 dragpos
= ui
->drag_currpos
> 0 ?
dsf_canonify(dsf
, ui
->drag_currpos
) : -1;
1819 * Now we can construct the data about what we want to draw.
1821 for (y
= 0; y
< h
; y
++)
1822 for (x
= 0; x
< w
; x
++) {
1829 * See if this square is part of the target area.
1831 j
= i
+ mainanchor
- (state
->ty
* w
+ state
->tx
);
1832 while (j
>= 0 && j
< wh
&& ISDIST(board
[j
]))
1834 if (j
== mainanchor
)
1839 if (state
->imm
->forcefield
[i
])
1840 val
|= BG_FORCEFIELD
;
1842 if (flashtime
> 0) {
1843 int flashtype
= (int)(flashtime
/ FLASH_INTERVAL
) & 1;
1844 val
|= (flashtype ? FLASH_LOW
: FLASH_HIGH
);
1847 if (board
[i
] != EMPTY
) {
1848 canon
= dsf_canonify(dsf
, i
);
1850 if (board
[i
] == WALL
)
1852 else if (canon
== mainpos
)
1856 if (canon
== dragpos
)
1860 * Now look around to see if other squares
1861 * belonging to the same block are adjacent to us.
1863 if (x
== 0 || canon
!= dsf_canonify(dsf
, i
-1))
1865 if (y
== 0 || canon
!= dsf_canonify(dsf
, i
-w
))
1867 if (x
== w
-1 || canon
!= dsf_canonify(dsf
, i
+1))
1869 if (y
== h
-1 || canon
!= dsf_canonify(dsf
, i
+w
))
1871 if (!(val
& (FG_TBORDER
| FG_LBORDER
)) &&
1872 canon
!= dsf_canonify(dsf
, i
-1-w
))
1874 if (!(val
& (FG_TBORDER
| FG_RBORDER
)) &&
1875 canon
!= dsf_canonify(dsf
, i
+1-w
))
1877 if (!(val
& (FG_BBORDER
| FG_LBORDER
)) &&
1878 canon
!= dsf_canonify(dsf
, i
-1+w
))
1880 if (!(val
& (FG_BBORDER
| FG_RBORDER
)) &&
1881 canon
!= dsf_canonify(dsf
, i
+1+w
))
1885 if (val
!= ds
->grid
[i
]) {
1886 draw_tile(dr
, ds
, x
, y
, val
);
1892 * Update the status bar.
1895 char statusbuf
[256];
1898 * FIXME: do something about auto-solve?
1900 sprintf(statusbuf
, "%sMoves: %d",
1901 (state
->completed
>= 0 ?
"COMPLETED! " : ""),
1902 (state
->completed
>= 0 ? state
->completed
: state
->movecount
));
1903 if (state
->minmoves
>= 0)
1904 sprintf(statusbuf
+strlen(statusbuf
), " (min %d)",
1907 status_bar(dr
, statusbuf
);
1914 static float game_anim_length(game_state
*oldstate
, game_state
*newstate
,
1915 int dir
, game_ui
*ui
)
1920 static float game_flash_length(game_state
*oldstate
, game_state
*newstate
,
1921 int dir
, game_ui
*ui
)
1923 if (oldstate
->completed
< 0 && newstate
->completed
>= 0)
1929 static int game_timing_state(game_state
*state
, game_ui
*ui
)
1934 static void game_print_size(game_params
*params
, float *x
, float *y
)
1938 static void game_print(drawing
*dr
, game_state
*state
, int tilesize
)
1943 #define thegame nullgame
1946 const struct game thegame
= {
1947 "Slide", NULL
, NULL
,
1954 TRUE
, game_configure
, custom_params
,
1961 FALSE
, solve_game
, /* FIXME */
1962 TRUE
, game_text_format
,
1970 PREFERRED_TILESIZE
, game_compute_size
, game_set_size
,
1973 game_free_drawstate
,
1977 FALSE
, FALSE
, game_print_size
, game_print
,
1978 TRUE
, /* wants_statusbar */
1979 FALSE
, game_timing_state
,