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.
21 * - All the colours are a bit wishy-washy. _Some_ dark colours
22 * would surely not be excessive? Probably darken the tiles,
23 * the walls and the main block, and leave the target marker
38 * The implementation of this game revolves around the insight
39 * which makes an exhaustive-search solver feasible: although
40 * there are many blocks which can be rearranged in many ways, any
41 * two blocks of the same shape are _indistinguishable_ and hence
42 * the number of _distinct_ board layouts is generally much
43 * smaller. So we adopt a representation for board layouts which
44 * is inherently canonical, i.e. there are no two distinct
45 * representations which encode indistinguishable layouts.
47 * The way we do this is to encode each square of the board, in
48 * the normal left-to-right top-to-bottom order, as being one of
49 * the following things:
50 * - the first square (in the given order) of a block (`anchor')
51 * - special case of the above: the anchor for the _main_ block
52 * (i.e. the one which the aim of the game is to get to the
54 * - a subsequent square of a block whose previous square was N
56 * - an impassable wall
58 * (We also separately store data about which board positions are
59 * forcefields only passable by the main block. We can't encode
60 * that in the main board data, because then the main block would
61 * destroy forcefields as it went over them.)
63 * Hence, for example, a 2x2 square block would be encoded as
64 * ANCHOR, followed by DIST(1), and w-2 squares later on there
65 * would be DIST(w-1) followed by DIST(1). So if you start at the
66 * last of those squares, the DIST numbers give you a linked list
67 * pointing back through all the other squares in the same block.
69 * So the solver simply does a bfs over all reachable positions,
70 * encoding them in this format and storing them in a tree234 to
71 * ensure it doesn't ever revisit an already-analysed position.
76 * The colours are arranged here so that every base colour is
77 * directly followed by its highlight colour and then its
78 * lowlight colour. Do not break this, or draw_tile() will get
85 COL_DRAGGING_HIGHLIGHT,
86 COL_DRAGGING_LOWLIGHT,
91 COL_MAIN_DRAGGING_HIGHLIGHT,
92 COL_MAIN_DRAGGING_LOWLIGHT,
100 * Board layout is a simple array of bytes. Each byte holds:
102 #define ANCHOR 255 /* top-left-most square of some piece */
103 #define MAINANCHOR 254 /* anchor of _main_ piece */
104 #define EMPTY 253 /* empty square */
105 #define WALL 252 /* immovable wall */
107 /* all other values indicate distance back to previous square of same block */
108 #define ISDIST(x) ( (unsigned char)((x)-1) <= MAXDIST-1 )
110 #define ISANCHOR(x) ( (x)==ANCHOR || (x)==MAINANCHOR )
111 #define ISBLOCK(x) ( ISANCHOR(x) || ISDIST(x) )
114 * MAXDIST is the largest DIST value we can encode. This must
115 * therefore also be the maximum puzzle width in theory (although
116 * solver running time will dictate a much smaller limit in
119 #define MAXWID MAXDIST
125 struct game_immutable_state {
127 unsigned char *forcefield;
132 unsigned char *board;
133 int tx, ty; /* target coords for MAINANCHOR */
134 int minmoves; /* for display only */
135 int lastmoved, lastmoved_pos; /* for move counting */
138 struct game_immutable_state *imm;
141 static game_params *default_params(void)
143 game_params *ret = snew(game_params);
151 static const struct game_params slide_presets[] = {
158 static int game_fetch_preset(int i, char **name, game_params **params)
163 if (i < 0 || i >= lenof(slide_presets))
166 ret = snew(game_params);
167 *ret = slide_presets[i];
169 sprintf(str, "%dx%d", ret->w, ret->h);
176 static void free_params(game_params *params)
181 static game_params *dup_params(game_params *params)
183 game_params *ret = snew(game_params);
184 *ret = *params; /* structure copy */
188 static void decode_params(game_params *params, char const *string)
190 params->w = params->h = atoi(string);
191 while (*string && isdigit((unsigned char)*string)) string++;
192 if (*string == 'x') {
194 params->h = atoi(string);
198 static char *encode_params(game_params *params, int full)
202 sprintf(data, "%dx%d", params->w, params->h);
207 static config_item *game_configure(game_params *params)
212 ret = snewn(3, config_item);
214 ret[0].name = "Width";
215 ret[0].type = C_STRING;
216 sprintf(buf, "%d", params->w);
217 ret[0].sval = dupstr(buf);
220 ret[1].name = "Height";
221 ret[1].type = C_STRING;
222 sprintf(buf, "%d", params->h);
223 ret[1].sval = dupstr(buf);
234 static game_params *custom_params(config_item *cfg)
236 game_params *ret = snew(game_params);
238 ret->w = atoi(cfg[0].sval);
239 ret->h = atoi(cfg[1].sval);
244 static char *validate_params(game_params *params, int full)
246 if (params->w > MAXWID)
247 return "Width must be at most " STR(MAXWID);
250 return "Width must be at least 5";
252 return "Height must be at least 4";
257 static char *board_text_format(int w, int h, unsigned char *data,
258 unsigned char *forcefield)
261 int *dsf = snew_dsf(wh);
263 int retpos, retlen = (w*2+2)*(h*2+1)+1;
264 char *ret = snewn(retlen, char);
266 for (i = 0; i < wh; i++)
268 dsf_merge(dsf, i - data[i], i);
270 for (y = 0; y < 2*h+1; y++) {
271 for (x = 0; x < 2*w+1; x++) {
273 int i = (y/2)*w+(x/2);
275 #define dtype(i) (ISBLOCK(data[i]) ? \
276 dsf_canonify(dsf, i) : data[i])
277 #define dchar(t) ((t)==EMPTY ? ' ' : (t)==WALL ? '#' : \
278 data[t] == MAINANCHOR ? '*' : '%')
280 if (y % 2 && x % 2) {
283 } else if (y % 2 && !(x % 2)) {
284 int j1 = (x > 0 ? dtype(i-1) : -1);
285 int j2 = (x < 2*w ? dtype(i) : -1);
290 } else if (!(y % 2) && (x % 2)) {
291 int j1 = (y > 0 ? dtype(i-w) : -1);
292 int j2 = (y < 2*h ? dtype(i) : -1);
298 int j1 = (x > 0 && y > 0 ? dtype(i-w-1) : -1);
299 int j2 = (x > 0 && y < 2*h ? dtype(i-1) : -1);
300 int j3 = (x < 2*w && y > 0 ? dtype(i-w) : -1);
301 int j4 = (x < 2*w && y < 2*h ? dtype(i) : -1);
302 if (j1 == j2 && j2 == j3 && j3 == j4)
304 else if (j1 == j2 && j3 == j4)
306 else if (j1 == j3 && j2 == j4)
312 assert(retpos < retlen);
315 assert(retpos < retlen);
316 ret[retpos++] = '\n';
318 assert(retpos < retlen);
319 ret[retpos++] = '\0';
320 assert(retpos == retlen);
325 /* ----------------------------------------------------------------------
330 * During solver execution, the set of visited board positions is
331 * stored as a tree234 of the following structures. `w', `h' and
332 * `data' are obvious in meaning; `dist' represents the minimum
333 * distance to reach this position from the starting point.
335 * `prev' links each board to the board position from which it was
336 * most efficiently derived.
345 static int boardcmp(void *av, void *bv)
347 struct board *a = (struct board *)av;
348 struct board *b = (struct board *)bv;
349 return memcmp(a->data, b->data, a->w * a->h);
352 static struct board *newboard(int w, int h, unsigned char *data)
354 struct board *b = malloc(sizeof(struct board) + w*h);
355 b->data = (unsigned char *)b + sizeof(struct board);
356 memcpy(b->data, data, w*h);
365 * The actual solver. Given a board, attempt to find the minimum
366 * length of move sequence which moves MAINANCHOR to (tx,ty), or
367 * -1 if no solution exists. Returns that minimum length, and
368 * (FIXME) optionally also writes out the actual moves into an
369 * as-yet-unprovided parameter.
371 static int solve_board(int w, int h, unsigned char *board,
372 unsigned char *forcefield, int tx, int ty)
375 struct board *b, *b2, *b3;
376 int *next, *anchors, *which;
377 int *movereached, *movequeue, mqhead, mqtail;
378 tree234 *sorted, *queue;
383 #ifdef SOLVER_DIAGNOSTICS
385 char *t = board_text_format(w, h, board);
386 for (i = 0; i < h; i++) {
387 for (j = 0; j < w; j++) {
388 int c = board[i*w+j];
391 else if (c == MAINANCHOR)
393 else if (c == ANCHOR)
403 printf("Starting solver for:\n%s\n", t);
408 sorted = newtree234(boardcmp);
409 queue = newtree234(NULL);
411 b = newboard(w, h, board);
414 addpos234(queue, b, 0);
417 next = snewn(wh, int);
418 anchors = snewn(wh, int);
419 which = snewn(wh, int);
420 movereached = snewn(wh, int);
421 movequeue = snewn(wh, int);
424 while ((b = delpos234(queue, 0)) != NULL) {
426 if (b->dist != lastdist) {
427 #ifdef SOLVER_DIAGNOSTICS
428 printf("dist %d (%d)\n", b->dist, count234(sorted));
433 * Find all the anchors and form a linked list of the
434 * squares within each block.
436 for (i = 0; i < wh; i++) {
440 if (ISANCHOR(b->data[i])) {
443 } else if (ISDIST(b->data[i])) {
451 * For each anchor, do an array-based BFS to find all the
452 * places we can slide it to.
454 for (i = 0; i < wh; i++) {
459 for (j = 0; j < wh; j++)
460 movereached[j] = FALSE;
461 movequeue[mqtail++] = i;
462 while (mqhead < mqtail) {
463 int pos = movequeue[mqhead++];
466 * Try to move in each direction from here.
468 for (dir = 0; dir < 4; dir++) {
469 int dx = (dir == 0 ? -1 : dir == 1 ? +1 : 0);
470 int dy = (dir == 2 ? -1 : dir == 3 ? +1 : 0);
471 int offset = dy*w + dx;
472 int newpos = pos + offset;
476 * For each square involved in this block,
477 * check to see if the square d spaces away
478 * from it is either empty or part of the same
481 for (j = i; j >= 0; j = next[j]) {
482 int jy = (pos+j-i) / w + dy, jx = (pos+j-i) % w + dx;
483 if (jy >= 0 && jy < h && jx >= 0 && jx < w &&
484 ((b->data[j+d] == EMPTY || which[j+d] == i) &&
485 (b->data[i] == MAINANCHOR || !forcefield[j+d])))
491 continue; /* this direction wasn't feasible */
494 * If we've already tried moving this piece
497 if (movereached[newpos])
499 movereached[newpos] = TRUE;
500 movequeue[mqtail++] = newpos;
503 * We have a viable move. Make it.
505 b2 = newboard(w, h, b->data);
506 for (j = i; j >= 0; j = next[j])
508 for (j = i; j >= 0; j = next[j])
509 b2->data[j+d] = b->data[j];
511 b3 = add234(sorted, b2);
513 sfree(b2); /* we already got one */
515 b2->dist = b->dist + 1;
517 addpos234(queue, b2, qlen++);
518 if (b2->data[ty*w+tx] == MAINANCHOR)
519 goto done; /* search completed! */
532 ret = -1; /* no solution */
536 while ((b = delpos234(sorted, 0)) != NULL)
549 /* ----------------------------------------------------------------------
550 * Random board generation.
553 static void generate_board(int w, int h, int *rtx, int *rty, int *minmoves,
554 random_state *rs, unsigned char **rboard,
555 unsigned char **rforcefield)
558 unsigned char *board, *board2, *forcefield;
559 int *list, nlist, pos;
565 * Set up a board and fill it with singletons, except for a
568 board = snewn(wh, unsigned char);
569 forcefield = snewn(wh, unsigned char);
570 board2 = snewn(wh, unsigned char);
571 memset(board, ANCHOR, wh);
572 memset(forcefield, FALSE, wh);
573 for (i = 0; i < w; i++)
574 board[i] = board[i+w*(h-1)] = WALL;
575 for (i = 0; i < h; i++)
576 board[i*w] = board[i*w+(w-1)] = WALL;
579 * Invent a main piece at one extreme. (FIXME: vary the
580 * extreme, and the piece.)
582 board[w+1] = MAINANCHOR;
583 board[w+2] = DIST(1);
584 board[w*2+1] = DIST(w-1);
585 board[w*2+2] = DIST(1);
588 * Invent a target position. (FIXME: vary this too.)
592 forcefield[ty*w+tx+1] = forcefield[(ty+1)*w+tx+1] = TRUE;
593 board[ty*w+tx+1] = board[(ty+1)*w+tx+1] = EMPTY;
596 * Gradually remove singletons until the game becomes soluble.
598 for (j = w; j-- > 0 ;)
599 for (i = h; i-- > 0 ;)
600 if (board[i*w+j] == ANCHOR) {
602 * See if the board is already soluble.
604 if ((moves = solve_board(w, h, board, forcefield,
609 * Otherwise, remove this piece.
611 board[i*w+j] = EMPTY;
613 assert(!"We shouldn't get here");
617 * Make a list of all the inter-block edges on the board.
619 list = snewn(wh*2, int);
621 for (i = 0; i+1 < w; i++)
622 for (j = 0; j < h; j++)
623 list[nlist++] = (j*w+i) * 2 + 0; /* edge to the right of j*w+i */
624 for (j = 0; j+1 < h; j++)
625 for (i = 0; i < w; i++)
626 list[nlist++] = (j*w+i) * 2 + 1; /* edge below j*w+i */
629 * Now go through that list in random order, trying to merge
630 * the blocks on each side of each edge.
632 * FIXME: this seems to produce unpleasantly unbalanced
633 * results. Perhaps we'd do better if we always tried to
634 * combine the _smallest_ block with something?
636 * FIXME: also one reason it's slow might be because we aren't
637 * tracking which blocks we've already tried to merge, when
638 * another edge ends up linking the same ones.
640 shuffle(list, nlist, sizeof(*list), rs);
646 y1 = y2 = pos / (w*2);
647 x1 = x2 = (pos / 2) % w;
656 * In order to be mergeable, these two squares must each
657 * either be, or belong to, a non-main anchor, and their
658 * anchors must also be distinct.
660 if (!ISBLOCK(board[p1]) || !ISBLOCK(board[p2]))
662 while (ISDIST(board[p1]))
664 while (ISDIST(board[p2]))
666 if (board[p1] == MAINANCHOR || board[p2] == MAINANCHOR || p1 == p2)
670 * We can merge these blocks. Try it, and see if the
671 * puzzle remains soluble.
673 memcpy(board2, board, wh);
675 while (p1 < wh || p2 < wh) {
677 * p1 and p2 are the squares at the head of each block
678 * list. Pick the smaller one and put it on the output
685 assert(i - j <= MAXDIST);
686 board[i] = DIST(i - j);
691 * Now advance whichever list that came from.
696 } while (p1 < wh && board[p1] != DIST(p1-i));
700 } while (p2 < wh && board[p2] != DIST(p2-i));
703 j = solve_board(w, h, board, forcefield, tx, ty);
706 * Didn't work. Revert the merge.
708 memcpy(board, board2, wh);
719 *rforcefield = forcefield;
723 /* ----------------------------------------------------------------------
724 * End of solver/generator code.
727 static char *new_game_desc(game_params *params, random_state *rs,
728 char **aux, int interactive)
730 int w = params->w, h = params->h, wh = w*h;
731 int tx, ty, minmoves;
732 unsigned char *board, *forcefield;
736 generate_board(params->w, params->h, &tx, &ty, &minmoves, rs,
737 &board, &forcefield);
738 #ifdef GENERATOR_DIAGNOSTICS
740 char *t = board_text_format(params->w, params->h, board);
747 * Encode as a game ID.
749 ret = snewn(wh * 6 + 40, char);
753 if (ISDIST(board[i])) {
754 p += sprintf(p, "d%d", board[i]);
758 int b = board[i], f = forcefield[i];
759 int c = (b == ANCHOR ? 'a' :
760 b == MAINANCHOR ? 'm' :
762 /* b == WALL ? */ 'w');
766 while (i < wh && board[i] == b && forcefield[i] == f)
769 p += sprintf(p, "%d", count);
772 p += sprintf(p, ",%d,%d,%d", tx, ty, minmoves);
773 ret = sresize(ret, p+1 - ret, char);
776 * FIXME: generate an aux string
785 static char *validate_desc(game_params *params, char *desc)
787 int w = params->w, h = params->h, wh = w*h;
789 int mains = 0, mpos = -1;
790 int i, j, tx, ty, minmoves;
793 active = snewn(wh, int);
794 link = snewn(wh, int);
797 while (*desc && *desc != ',') {
799 ret = "Too much data in game description";
804 if (*desc == 'f' || *desc == 'F') {
807 ret = "Expected another character after 'f' in game "
813 if (*desc == 'd' || *desc == 'D') {
817 if (!isdigit((unsigned char)*desc)) {
818 ret = "Expected a number after 'd' in game description";
822 while (*desc && isdigit((unsigned char)*desc)) desc++;
824 if (dist <= 0 || dist > i) {
825 ret = "Out-of-range number after 'd' in game description";
829 if (!active[i - dist]) {
830 ret = "Invalid back-reference in game description";
835 for (j = i; j > 0; j = link[j])
836 if (j == i-1 || j == i-w)
839 ret = "Disconnected piece in game description";
844 active[link[i]] = FALSE;
850 if (!strchr("aAmMeEwW", c)) {
851 ret = "Invalid character in game description";
854 if (isdigit((unsigned char)*desc)) {
856 while (*desc && isdigit((unsigned char)*desc)) desc++;
858 if (i + count > wh) {
859 ret = "Too much data in game description";
862 while (count-- > 0) {
863 active[i] = (strchr("aAmM", c) != NULL);
865 if (strchr("mM", c) != NULL) {
874 ret = (mains == 0 ? "No main piece specified in game description" :
875 "More than one main piece specified in game description");
879 ret = "Not enough data in game description";
884 * Now read the target coordinates.
886 i = sscanf(desc, ",%d,%d,%d", &tx, &ty, &minmoves);
888 ret = "No target coordinates specified";
891 * (but minmoves is optional)
903 static game_state *new_game(midend *me, game_params *params, char *desc)
905 int w = params->w, h = params->h, wh = w*h;
909 state = snew(game_state);
912 state->board = snewn(wh, unsigned char);
913 state->lastmoved = state->lastmoved_pos = -1;
914 state->movecount = 0;
915 state->imm = snew(struct game_immutable_state);
916 state->imm->refcount = 1;
917 state->imm->forcefield = snewn(wh, unsigned char);
921 while (*desc && *desc != ',') {
932 if (*desc == 'd' || *desc == 'D') {
937 while (*desc && isdigit((unsigned char)*desc)) desc++;
939 state->board[i] = DIST(dist);
940 state->imm->forcefield[i] = f;
947 if (isdigit((unsigned char)*desc)) {
949 while (*desc && isdigit((unsigned char)*desc)) desc++;
951 assert(i + count <= wh);
953 c = (c == 'a' || c == 'A' ? ANCHOR :
954 c == 'm' || c == 'M' ? MAINANCHOR :
955 c == 'e' || c == 'E' ? EMPTY :
956 /* c == 'w' || c == 'W' ? */ WALL);
958 while (count-- > 0) {
960 state->imm->forcefield[i] = f;
967 * Now read the target coordinates.
969 state->tx = state->ty = 0;
970 state->minmoves = -1;
971 i = sscanf(desc, ",%d,%d,%d", &state->tx, &state->ty, &state->minmoves);
973 if (state->board[state->ty*w+state->tx] == MAINANCHOR)
974 state->completed = 0; /* already complete! */
976 state->completed = -1;
981 static game_state *dup_game(game_state *state)
983 int w = state->w, h = state->h, wh = w*h;
984 game_state *ret = snew(game_state);
988 ret->board = snewn(wh, unsigned char);
989 memcpy(ret->board, state->board, wh);
992 ret->minmoves = state->minmoves;
993 ret->lastmoved = state->lastmoved;
994 ret->lastmoved_pos = state->lastmoved_pos;
995 ret->movecount = state->movecount;
996 ret->completed = state->completed;
997 ret->imm = state->imm;
998 ret->imm->refcount++;
1003 static void free_game(game_state *state)
1005 if (--state->imm->refcount <= 0) {
1006 sfree(state->imm->forcefield);
1009 sfree(state->board);
1013 static char *solve_game(game_state *state, game_state *currstate,
1014 char *aux, char **error)
1017 * FIXME: we have a solver, so use it
1019 * FIXME: we should have generated an aux string, so use that
1024 static char *game_text_format(game_state *state)
1026 return board_text_format(state->w, state->h, state->board,
1027 state->imm->forcefield);
1033 int drag_offset_x, drag_offset_y;
1035 unsigned char *reachable;
1036 int *bfs_queue; /* used as scratch in interpret_move */
1039 static game_ui *new_ui(game_state *state)
1041 int w = state->w, h = state->h, wh = w*h;
1042 game_ui *ui = snew(game_ui);
1044 ui->dragging = FALSE;
1045 ui->drag_anchor = ui->drag_currpos = -1;
1046 ui->drag_offset_x = ui->drag_offset_y = -1;
1047 ui->reachable = snewn(wh, unsigned char);
1048 memset(ui->reachable, 0, wh);
1049 ui->bfs_queue = snewn(wh, int);
1054 static void free_ui(game_ui *ui)
1056 sfree(ui->bfs_queue);
1057 sfree(ui->reachable);
1061 static char *encode_ui(game_ui *ui)
1066 static void decode_ui(game_ui *ui, char *encoding)
1070 static void game_changed_state(game_ui *ui, game_state *oldstate,
1071 game_state *newstate)
1075 #define PREFERRED_TILESIZE 32
1076 #define TILESIZE (ds->tilesize)
1077 #define BORDER (TILESIZE/2)
1078 #define COORD(x) ( (x) * TILESIZE + BORDER )
1079 #define FROMCOORD(x) ( ((x) - BORDER + TILESIZE) / TILESIZE - 1 )
1080 #define BORDER_WIDTH (1 + TILESIZE/20)
1081 #define HIGHLIGHT_WIDTH (1 + TILESIZE/16)
1083 #define FLASH_INTERVAL 0.10F
1084 #define FLASH_TIME 3*FLASH_INTERVAL
1086 struct game_drawstate {
1089 unsigned long *grid; /* what's currently displayed */
1093 static char *interpret_move(game_state *state, game_ui *ui, game_drawstate *ds,
1094 int x, int y, int button)
1096 int w = state->w, h = state->h, wh = w*h;
1100 if (button == LEFT_BUTTON) {
1104 if (tx < 0 || tx >= w || ty < 0 || ty >= h ||
1105 !ISBLOCK(state->board[ty*w+tx]))
1106 return NULL; /* this click has no effect */
1109 * User has clicked on a block. Find the block's anchor
1110 * and register that we've started dragging it.
1113 while (ISDIST(state->board[i]))
1114 i -= state->board[i];
1115 assert(i >= 0 && i < wh);
1117 ui->dragging = TRUE;
1118 ui->drag_anchor = i;
1119 ui->drag_offset_x = tx - (i % w);
1120 ui->drag_offset_y = ty - (i / w);
1121 ui->drag_currpos = i;
1124 * Now we immediately bfs out from the current location of
1125 * the anchor, to find all the places to which this block
1128 memset(ui->reachable, FALSE, wh);
1130 ui->reachable[i] = TRUE;
1131 ui->bfs_queue[qtail++] = i;
1132 for (j = i; j < wh; j++)
1133 if (state->board[j] == DIST(j - i))
1135 while (qhead < qtail) {
1136 int pos = ui->bfs_queue[qhead++];
1137 int x = pos % w, y = pos / w;
1140 for (dir = 0; dir < 4; dir++) {
1141 int dx = (dir == 0 ? -1 : dir == 1 ? +1 : 0);
1142 int dy = (dir == 2 ? -1 : dir == 3 ? +1 : 0);
1145 if (x + dx < 0 || x + dx >= w ||
1146 y + dy < 0 || y + dy >= h)
1149 newpos = pos + dy*w + dx;
1150 if (ui->reachable[newpos])
1151 continue; /* already done this one */
1154 * Now search the grid to see if the block we're
1155 * dragging could fit into this space.
1157 for (j = i; j >= 0; j = (ISDIST(state->board[j]) ?
1158 j - state->board[j] : -1)) {
1159 int jx = (j+pos-ui->drag_anchor) % w;
1160 int jy = (j+pos-ui->drag_anchor) / w;
1163 if (jx + dx < 0 || jx + dx >= w ||
1164 jy + dy < 0 || jy + dy >= h)
1165 break; /* this position isn't valid at all */
1167 j2 = (j+pos-ui->drag_anchor) + dy*w + dx;
1169 if (state->board[j2] == EMPTY &&
1170 (!state->imm->forcefield[j2] ||
1171 state->board[ui->drag_anchor] == MAINANCHOR))
1173 while (ISDIST(state->board[j2]))
1174 j2 -= state->board[j2];
1175 assert(j2 >= 0 && j2 < wh);
1176 if (j2 == ui->drag_anchor)
1184 * If we got to the end of that loop without
1185 * disqualifying this position, mark it as
1186 * reachable for this drag.
1188 ui->reachable[newpos] = TRUE;
1189 ui->bfs_queue[qtail++] = newpos;
1195 * And that's it. Update the display to reflect the start
1199 } else if (button == LEFT_DRAG && ui->dragging) {
1203 tx -= ui->drag_offset_x;
1204 ty -= ui->drag_offset_y;
1205 if (tx < 0 || tx >= w || ty < 0 || ty >= h ||
1206 !ui->reachable[ty*w+tx])
1207 return NULL; /* this drag has no effect */
1209 ui->drag_currpos = ty*w+tx;
1211 } else if (button == LEFT_RELEASE && ui->dragging) {
1212 char data[256], *str;
1215 * Terminate the drag, and if the piece has actually moved
1216 * then return a move string quoting the old and new
1217 * locations of the piece's anchor.
1219 if (ui->drag_anchor != ui->drag_currpos) {
1220 sprintf(data, "M%d-%d", ui->drag_anchor, ui->drag_currpos);
1223 str = ""; /* null move; just update the UI */
1225 ui->dragging = FALSE;
1226 ui->drag_anchor = ui->drag_currpos = -1;
1227 ui->drag_offset_x = ui->drag_offset_y = -1;
1228 memset(ui->reachable, 0, wh);
1236 static int move_piece(int w, int h, const unsigned char *src,
1237 unsigned char *dst, unsigned char *ff, int from, int to)
1242 if (!ISANCHOR(dst[from]))
1246 * Scan to the far end of the piece's linked list.
1248 for (i = j = from; j < wh; j++)
1249 if (src[j] == DIST(j - i))
1253 * Remove the piece from its old location in the new
1256 for (j = i; j >= 0; j = (ISDIST(src[j]) ? j - src[j] : -1))
1260 * And put it back in at the new location.
1262 for (j = i; j >= 0; j = (ISDIST(src[j]) ? j - src[j] : -1)) {
1263 int jn = j + to - from;
1264 if (jn < 0 || jn >= wh)
1266 if (dst[jn] == EMPTY && (!ff[jn] || src[from] == MAINANCHOR)) {
1276 static game_state *execute_move(game_state *state, char *move)
1278 int w = state->w, h = state->h /* , wh = w*h */;
1281 game_state *ret = dup_game(state);
1287 if (sscanf(move, "%d-%d%n", &a1, &a2, &n) != 2 ||
1288 !move_piece(w, h, state->board, ret->board,
1289 state->imm->forcefield, a1, a2)) {
1293 if (a1 == ret->lastmoved) {
1295 * If the player has moved the same piece as they
1296 * moved last time, don't increment the move
1297 * count. In fact, if they've put the piece back
1298 * where it started from, _decrement_ the move
1301 if (a2 == ret->lastmoved_pos) {
1302 ret->movecount--; /* reverted last move */
1303 ret->lastmoved = ret->lastmoved_pos = -1;
1305 ret->lastmoved = a2;
1306 /* don't change lastmoved_pos */
1309 ret->lastmoved = a2;
1310 ret->lastmoved_pos = a1;
1313 if (ret->board[a2] == MAINANCHOR &&
1314 a2 == ret->ty * w + ret->tx && ret->completed < 0)
1315 ret->completed = ret->movecount;
1332 /* ----------------------------------------------------------------------
1336 static void game_compute_size(game_params *params, int tilesize,
1339 /* fool the macros */
1340 struct dummy { int tilesize; } dummy = { tilesize }, *ds = &dummy;
1342 *x = params->w * TILESIZE + 2*BORDER;
1343 *y = params->h * TILESIZE + 2*BORDER;
1346 static void game_set_size(drawing *dr, game_drawstate *ds,
1347 game_params *params, int tilesize)
1349 ds->tilesize = tilesize;
1352 static void raise_colour(float *target, float *src, float *limit)
1355 for (i = 0; i < 3; i++)
1356 target[i] = (2*src[i] + limit[i]) / 3;
1359 static float *game_colours(frontend *fe, int *ncolours)
1361 float *ret = snewn(3 * NCOLOURS, float);
1363 game_mkhighlight(fe, ret, COL_BACKGROUND, COL_HIGHLIGHT, COL_LOWLIGHT);
1366 * When dragging a tile, we light it up a bit.
1368 raise_colour(ret+3*COL_DRAGGING,
1369 ret+3*COL_BACKGROUND, ret+3*COL_HIGHLIGHT);
1370 raise_colour(ret+3*COL_DRAGGING_HIGHLIGHT,
1371 ret+3*COL_HIGHLIGHT, ret+3*COL_HIGHLIGHT);
1372 raise_colour(ret+3*COL_DRAGGING_LOWLIGHT,
1373 ret+3*COL_LOWLIGHT, ret+3*COL_HIGHLIGHT);
1376 * The main tile is tinted blue.
1378 ret[COL_MAIN * 3 + 0] = ret[COL_BACKGROUND * 3 + 0];
1379 ret[COL_MAIN * 3 + 1] = ret[COL_BACKGROUND * 3 + 1];
1380 ret[COL_MAIN * 3 + 2] = ret[COL_HIGHLIGHT * 3 + 2];
1381 game_mkhighlight_specific(fe, ret, COL_MAIN,
1382 COL_MAIN_HIGHLIGHT, COL_MAIN_LOWLIGHT);
1385 * And we light that up a bit too when dragging.
1387 raise_colour(ret+3*COL_MAIN_DRAGGING,
1388 ret+3*COL_MAIN, ret+3*COL_MAIN_HIGHLIGHT);
1389 raise_colour(ret+3*COL_MAIN_DRAGGING_HIGHLIGHT,
1390 ret+3*COL_MAIN_HIGHLIGHT, ret+3*COL_MAIN_HIGHLIGHT);
1391 raise_colour(ret+3*COL_MAIN_DRAGGING_LOWLIGHT,
1392 ret+3*COL_MAIN_LOWLIGHT, ret+3*COL_MAIN_HIGHLIGHT);
1395 * The target area on the floor is tinted green.
1397 ret[COL_TARGET * 3 + 0] = ret[COL_BACKGROUND * 3 + 0];
1398 ret[COL_TARGET * 3 + 1] = ret[COL_HIGHLIGHT * 3 + 1];
1399 ret[COL_TARGET * 3 + 2] = ret[COL_BACKGROUND * 3 + 2];
1400 game_mkhighlight_specific(fe, ret, COL_TARGET,
1401 COL_TARGET_HIGHLIGHT, COL_TARGET_LOWLIGHT);
1403 *ncolours = NCOLOURS;
1407 static game_drawstate *game_new_drawstate(drawing *dr, game_state *state)
1409 int w = state->w, h = state->h, wh = w*h;
1410 struct game_drawstate *ds = snew(struct game_drawstate);
1416 ds->started = FALSE;
1417 ds->grid = snewn(wh, unsigned long);
1418 for (i = 0; i < wh; i++)
1419 ds->grid[i] = ~(unsigned long)0;
1424 static void game_free_drawstate(drawing *dr, game_drawstate *ds)
1430 #define BG_NORMAL 0x00000001UL
1431 #define BG_TARGET 0x00000002UL
1432 #define BG_FORCEFIELD 0x00000004UL
1433 #define FLASH_LOW 0x00000008UL
1434 #define FLASH_HIGH 0x00000010UL
1435 #define FG_WALL 0x00000020UL
1436 #define FG_MAIN 0x00000040UL
1437 #define FG_NORMAL 0x00000080UL
1438 #define FG_DRAGGING 0x00000100UL
1439 #define FG_LBORDER 0x00000200UL
1440 #define FG_TBORDER 0x00000400UL
1441 #define FG_RBORDER 0x00000800UL
1442 #define FG_BBORDER 0x00001000UL
1443 #define FG_TLCORNER 0x00002000UL
1444 #define FG_TRCORNER 0x00004000UL
1445 #define FG_BLCORNER 0x00008000UL
1446 #define FG_BRCORNER 0x00010000UL
1451 #define TYPE_MASK 0xF000
1452 #define COL_MASK 0x0FFF
1453 #define TYPE_RECT 0x0000
1454 #define TYPE_TLCIRC 0x4000
1455 #define TYPE_TRCIRC 0x5000
1456 #define TYPE_BLCIRC 0x6000
1457 #define TYPE_BRCIRC 0x7000
1458 static void maybe_rect(drawing *dr, int x, int y, int w, int h, int coltype)
1460 int colour = coltype & COL_MASK, type = coltype & TYPE_MASK;
1462 if (colour > NCOLOURS)
1464 if (type == TYPE_RECT) {
1465 draw_rect(dr, x, y, w, h, colour);
1469 clip(dr, x, y, w, h);
1479 draw_circle(dr, cx, cy, r, colour, colour);
1485 static void draw_tile(drawing *dr, game_drawstate *ds,
1486 int x, int y, unsigned long val)
1488 int tx = COORD(x), ty = COORD(y);
1492 * Draw the tile background.
1494 if (val & BG_TARGET)
1497 cc = COL_BACKGROUND;
1500 if (val & FLASH_LOW)
1502 else if (val & FLASH_HIGH)
1505 draw_rect(dr, tx, ty, TILESIZE, TILESIZE, cc);
1506 if (val & BG_FORCEFIELD) {
1508 * Cattle-grid effect to indicate that nothing but the
1509 * main block can slide over this square.
1511 int n = 3 * (TILESIZE / (3*HIGHLIGHT_WIDTH));
1514 for (i = 1; i < n; i += 3) {
1515 draw_rect(dr, tx,ty+(TILESIZE*i/n), TILESIZE,HIGHLIGHT_WIDTH, cl);
1516 draw_rect(dr, tx+(TILESIZE*i/n),ty, HIGHLIGHT_WIDTH,TILESIZE, cl);
1521 * Draw the tile foreground, i.e. some section of a block or
1524 if (val & FG_WALL) {
1525 cc = COL_BACKGROUND;
1528 if (val & FLASH_LOW)
1530 else if (val & FLASH_HIGH)
1533 draw_rect(dr, tx, ty, TILESIZE, TILESIZE, cc);
1534 if (val & FG_LBORDER)
1535 draw_rect(dr, tx, ty, HIGHLIGHT_WIDTH, TILESIZE,
1537 if (val & FG_RBORDER)
1538 draw_rect(dr, tx+TILESIZE-HIGHLIGHT_WIDTH, ty,
1539 HIGHLIGHT_WIDTH, TILESIZE, cl);
1540 if (val & FG_TBORDER)
1541 draw_rect(dr, tx, ty, TILESIZE, HIGHLIGHT_WIDTH, ch);
1542 if (val & FG_BBORDER)
1543 draw_rect(dr, tx, ty+TILESIZE-HIGHLIGHT_WIDTH,
1544 TILESIZE, HIGHLIGHT_WIDTH, cl);
1545 if (!((FG_BBORDER | FG_LBORDER) &~ val))
1546 draw_rect(dr, tx, ty+TILESIZE-HIGHLIGHT_WIDTH,
1547 HIGHLIGHT_WIDTH, HIGHLIGHT_WIDTH, cc);
1548 if (!((FG_TBORDER | FG_RBORDER) &~ val))
1549 draw_rect(dr, tx+TILESIZE-HIGHLIGHT_WIDTH, ty,
1550 HIGHLIGHT_WIDTH, HIGHLIGHT_WIDTH, cc);
1551 if (val & FG_TLCORNER)
1552 draw_rect(dr, tx, ty, HIGHLIGHT_WIDTH, HIGHLIGHT_WIDTH, ch);
1553 if (val & FG_BRCORNER)
1554 draw_rect(dr, tx+TILESIZE-HIGHLIGHT_WIDTH,
1555 ty+TILESIZE-HIGHLIGHT_WIDTH,
1556 HIGHLIGHT_WIDTH, HIGHLIGHT_WIDTH, cl);
1557 } else if (val & (FG_MAIN | FG_NORMAL)) {
1560 if (val & FG_DRAGGING)
1561 cc = (val & FG_MAIN ? COL_MAIN_DRAGGING : COL_DRAGGING);
1563 cc = (val & FG_MAIN ? COL_MAIN : COL_BACKGROUND);
1567 if (val & FLASH_LOW)
1569 else if (val & FLASH_HIGH)
1573 * Drawing the blocks is hellishly fiddly. The blocks
1574 * don't stretch to the full size of the tile; there's a
1575 * border around them of size BORDER_WIDTH. Then they have
1576 * bevelled borders of size HIGHLIGHT_WIDTH, and also
1579 * I tried for some time to find a clean and clever way to
1580 * figure out what needed drawing from the corner and
1581 * border flags, but in the end the cleanest way I could
1582 * find was the following. We divide the grid square into
1583 * 25 parts by ruling four horizontal and four vertical
1584 * lines across it; those lines are at BORDER_WIDTH and
1585 * BORDER_WIDTH+HIGHLIGHT_WIDTH from the top, from the
1586 * bottom, from the left and from the right. Then we
1587 * carefully consider each of the resulting 25 sections of
1588 * square, and decide separately what needs to go in it
1589 * based on the flags. In complicated cases there can be
1590 * up to five possibilities affecting any given section
1591 * (no corner or border flags, just the corner flag, one
1592 * border flag, the other border flag, both border flags).
1593 * So there's a lot of very fiddly logic here and all I
1594 * could really think to do was give it my best shot and
1595 * then test it and correct all the typos. Not fun to
1596 * write, and I'm sure it isn't fun to read either, but it
1601 x[1] = x[0] + BORDER_WIDTH;
1602 x[2] = x[1] + HIGHLIGHT_WIDTH;
1603 x[5] = tx + TILESIZE;
1604 x[4] = x[5] - BORDER_WIDTH;
1605 x[3] = x[4] - HIGHLIGHT_WIDTH;
1608 y[1] = y[0] + BORDER_WIDTH;
1609 y[2] = y[1] + HIGHLIGHT_WIDTH;
1610 y[5] = ty + TILESIZE;
1611 y[4] = y[5] - BORDER_WIDTH;
1612 y[3] = y[4] - HIGHLIGHT_WIDTH;
1614 #define RECT(p,q) x[p], y[q], x[(p)+1]-x[p], y[(q)+1]-y[q]
1616 maybe_rect(dr, RECT(0,0),
1617 (val & (FG_TLCORNER | FG_TBORDER | FG_LBORDER)) ? -1 : cc);
1618 maybe_rect(dr, RECT(1,0),
1619 (val & FG_TLCORNER) ? ch : (val & FG_TBORDER) ? -1 :
1620 (val & FG_LBORDER) ? ch : cc);
1621 maybe_rect(dr, RECT(2,0),
1622 (val & FG_TBORDER) ? -1 : cc);
1623 maybe_rect(dr, RECT(3,0),
1624 (val & FG_TRCORNER) ? cl : (val & FG_TBORDER) ? -1 :
1625 (val & FG_RBORDER) ? cl : cc);
1626 maybe_rect(dr, RECT(4,0),
1627 (val & (FG_TRCORNER | FG_TBORDER | FG_RBORDER)) ? -1 : cc);
1628 maybe_rect(dr, RECT(0,1),
1629 (val & FG_TLCORNER) ? ch : (val & FG_LBORDER) ? -1 :
1630 (val & FG_TBORDER) ? ch : cc);
1631 maybe_rect(dr, RECT(1,1),
1632 (val & FG_TLCORNER) ? cc : -1);
1633 maybe_rect(dr, RECT(1,1),
1634 (val & FG_TLCORNER) ? ch | TYPE_TLCIRC :
1635 !((FG_TBORDER | FG_LBORDER) &~ val) ? ch | TYPE_BRCIRC :
1636 (val & (FG_TBORDER | FG_LBORDER)) ? ch : cc);
1637 maybe_rect(dr, RECT(2,1),
1638 (val & FG_TBORDER) ? ch : cc);
1639 maybe_rect(dr, RECT(3,1),
1640 (val & (FG_TBORDER | FG_RBORDER)) == FG_TBORDER ? ch :
1641 (val & (FG_TBORDER | FG_RBORDER)) == FG_RBORDER ? cl :
1642 !((FG_TBORDER|FG_RBORDER) &~ val) ? cc | TYPE_BLCIRC : cc);
1643 maybe_rect(dr, RECT(4,1),
1644 (val & FG_TRCORNER) ? ch : (val & FG_RBORDER) ? -1 :
1645 (val & FG_TBORDER) ? ch : cc);
1646 maybe_rect(dr, RECT(0,2),
1647 (val & FG_LBORDER) ? -1 : cc);
1648 maybe_rect(dr, RECT(1,2),
1649 (val & FG_LBORDER) ? ch : cc);
1650 maybe_rect(dr, RECT(2,2),
1652 maybe_rect(dr, RECT(3,2),
1653 (val & FG_RBORDER) ? cl : cc);
1654 maybe_rect(dr, RECT(4,2),
1655 (val & FG_RBORDER) ? -1 : cc);
1656 maybe_rect(dr, RECT(0,3),
1657 (val & FG_BLCORNER) ? cl : (val & FG_LBORDER) ? -1 :
1658 (val & FG_BBORDER) ? cl : cc);
1659 maybe_rect(dr, RECT(1,3),
1660 (val & (FG_BBORDER | FG_LBORDER)) == FG_BBORDER ? cl :
1661 (val & (FG_BBORDER | FG_LBORDER)) == FG_LBORDER ? ch :
1662 !((FG_BBORDER|FG_LBORDER) &~ val) ? cc | TYPE_TRCIRC : cc);
1663 maybe_rect(dr, RECT(2,3),
1664 (val & FG_BBORDER) ? cl : cc);
1665 maybe_rect(dr, RECT(3,3),
1666 (val & FG_BRCORNER) ? cc : -1);
1667 maybe_rect(dr, RECT(3,3),
1668 (val & FG_BRCORNER) ? cl | TYPE_BRCIRC :
1669 !((FG_BBORDER | FG_RBORDER) &~ val) ? cl | TYPE_TLCIRC :
1670 (val & (FG_BBORDER | FG_RBORDER)) ? cl : cc);
1671 maybe_rect(dr, RECT(4,3),
1672 (val & FG_BRCORNER) ? cl : (val & FG_RBORDER) ? -1 :
1673 (val & FG_BBORDER) ? cl : cc);
1674 maybe_rect(dr, RECT(0,4),
1675 (val & (FG_BLCORNER | FG_BBORDER | FG_LBORDER)) ? -1 : cc);
1676 maybe_rect(dr, RECT(1,4),
1677 (val & FG_BLCORNER) ? ch : (val & FG_BBORDER) ? -1 :
1678 (val & FG_LBORDER) ? ch : cc);
1679 maybe_rect(dr, RECT(2,4),
1680 (val & FG_BBORDER) ? -1 : cc);
1681 maybe_rect(dr, RECT(3,4),
1682 (val & FG_BRCORNER) ? cl : (val & FG_BBORDER) ? -1 :
1683 (val & FG_RBORDER) ? cl : cc);
1684 maybe_rect(dr, RECT(4,4),
1685 (val & (FG_BRCORNER | FG_BBORDER | FG_RBORDER)) ? -1 : cc);
1691 draw_update(dr, tx, ty, TILESIZE, TILESIZE);
1694 static void game_redraw(drawing *dr, game_drawstate *ds, game_state *oldstate,
1695 game_state *state, int dir, game_ui *ui,
1696 float animtime, float flashtime)
1698 int w = state->w, h = state->h, wh = w*h;
1699 unsigned char *board;
1701 int x, y, mainanchor, mainpos, dragpos;
1705 * The initial contents of the window are not guaranteed
1706 * and can vary with front ends. To be on the safe side,
1707 * all games should start by drawing a big
1708 * background-colour rectangle covering the whole window.
1710 draw_rect(dr, 0, 0, 10*ds->tilesize, 10*ds->tilesize, COL_BACKGROUND);
1715 * Construct the board we'll be displaying (which may be
1716 * different from the one in state if ui describes a drag in
1719 board = snewn(wh, unsigned char);
1720 memcpy(board, state->board, wh);
1722 int mpret = move_piece(w, h, state->board, board,
1723 state->imm->forcefield,
1724 ui->drag_anchor, ui->drag_currpos);
1729 * Build a dsf out of that board, so we can conveniently tell
1730 * which edges are connected and which aren't.
1734 for (y = 0; y < h; y++)
1735 for (x = 0; x < w; x++) {
1738 if (ISDIST(board[i]))
1739 dsf_merge(dsf, i, i - board[i]);
1740 if (board[i] == MAINANCHOR)
1742 if (board[i] == WALL) {
1743 if (x > 0 && board[i-1] == WALL)
1744 dsf_merge(dsf, i, i-1);
1745 if (y > 0 && board[i-w] == WALL)
1746 dsf_merge(dsf, i, i-w);
1749 assert(mainanchor >= 0);
1750 mainpos = dsf_canonify(dsf, mainanchor);
1751 dragpos = ui->drag_currpos > 0 ? dsf_canonify(dsf, ui->drag_currpos) : -1;
1754 * Now we can construct the data about what we want to draw.
1756 for (y = 0; y < h; y++)
1757 for (x = 0; x < w; x++) {
1764 * See if this square is part of the target area.
1766 j = i + mainanchor - (state->ty * w + state->tx);
1767 while (j >= 0 && j < wh && ISDIST(board[j]))
1769 if (j == mainanchor)
1774 if (state->imm->forcefield[i])
1775 val |= BG_FORCEFIELD;
1777 if (flashtime > 0) {
1778 int flashtype = (int)(flashtime / FLASH_INTERVAL) & 1;
1779 val |= (flashtype ? FLASH_LOW : FLASH_HIGH);
1782 if (board[i] != EMPTY) {
1783 canon = dsf_canonify(dsf, i);
1785 if (board[i] == WALL)
1787 else if (canon == mainpos)
1791 if (canon == dragpos)
1795 * Now look around to see if other squares
1796 * belonging to the same block are adjacent to us.
1798 if (x == 0 || canon != dsf_canonify(dsf, i-1))
1800 if (y== 0 || canon != dsf_canonify(dsf, i-w))
1802 if (x == w-1 || canon != dsf_canonify(dsf, i+1))
1804 if (y == h-1 || canon != dsf_canonify(dsf, i+w))
1806 if (!(val & (FG_TBORDER | FG_LBORDER)) &&
1807 canon != dsf_canonify(dsf, i-1-w))
1809 if (!(val & (FG_TBORDER | FG_RBORDER)) &&
1810 canon != dsf_canonify(dsf, i+1-w))
1812 if (!(val & (FG_BBORDER | FG_LBORDER)) &&
1813 canon != dsf_canonify(dsf, i-1+w))
1815 if (!(val & (FG_BBORDER | FG_RBORDER)) &&
1816 canon != dsf_canonify(dsf, i+1+w))
1820 if (val != ds->grid[i]) {
1821 draw_tile(dr, ds, x, y, val);
1827 * Update the status bar.
1830 char statusbuf[256];
1833 * FIXME: do something about auto-solve?
1835 sprintf(statusbuf, "%sMoves: %d",
1836 (state->completed >= 0 ? "COMPLETED! " : ""),
1837 (state->completed >= 0 ? state->completed : state->movecount));
1838 if (state->minmoves)
1839 sprintf(statusbuf+strlen(statusbuf), " (min %d)",
1842 status_bar(dr, statusbuf);
1849 static float game_anim_length(game_state *oldstate, game_state *newstate,
1850 int dir, game_ui *ui)
1855 static float game_flash_length(game_state *oldstate, game_state *newstate,
1856 int dir, game_ui *ui)
1858 if (oldstate->completed < 0 && newstate->completed >= 0)
1864 static int game_timing_state(game_state *state, game_ui *ui)
1869 static void game_print_size(game_params *params, float *x, float *y)
1873 static void game_print(drawing *dr, game_state *state, int tilesize)
1878 #define thegame nullgame
1881 const struct game thegame = {
1882 "Slide", NULL, NULL,
1889 TRUE, game_configure, custom_params,
1896 FALSE, solve_game, /* FIXME */
1897 TRUE, game_text_format,
1905 PREFERRED_TILESIZE, game_compute_size, game_set_size,
1908 game_free_drawstate,
1912 FALSE, FALSE, game_print_size, game_print,
1913 TRUE, /* wants_statusbar */
1914 FALSE, game_timing_state,