summaryrefslogtreecommitdiff
path: root/apps/plugins/puzzles/src/unfinished/slide.c
diff options
context:
space:
mode:
Diffstat (limited to 'apps/plugins/puzzles/src/unfinished/slide.c')
-rw-r--r--apps/plugins/puzzles/src/unfinished/slide.c2445
1 files changed, 2445 insertions, 0 deletions
diff --git a/apps/plugins/puzzles/src/unfinished/slide.c b/apps/plugins/puzzles/src/unfinished/slide.c
new file mode 100644
index 0000000000..9d4fce1461
--- /dev/null
+++ b/apps/plugins/puzzles/src/unfinished/slide.c
@@ -0,0 +1,2445 @@
1/*
2 * slide.c: Implementation of the block-sliding puzzle `Klotski'.
3 */
4
5/*
6 * TODO:
7 *
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
14 * think it's OK.
15 * * the move limit tends to make the game _slower_ to
16 * generate, which is odd. Perhaps investigate why.
17 *
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
22 * target marker pale.
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.
28 */
29
30#include <stdio.h>
31#include <stdlib.h>
32#include <string.h>
33#include <assert.h>
34#include <ctype.h>
35#include <math.h>
36
37#include "puzzles.h"
38#include "tree234.h"
39
40/*
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.
49 *
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
56 * target position)
57 * - a subsequent square of a block whose previous square was N
58 * squares ago
59 * - an impassable wall
60 *
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.)
65 *
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.
71 *
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.
75 */
76
77enum {
78 /*
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
82 * confused.
83 */
84 COL_BACKGROUND,
85 COL_HIGHLIGHT,
86 COL_LOWLIGHT,
87 COL_DRAGGING,
88 COL_DRAGGING_HIGHLIGHT,
89 COL_DRAGGING_LOWLIGHT,
90 COL_MAIN,
91 COL_MAIN_HIGHLIGHT,
92 COL_MAIN_LOWLIGHT,
93 COL_MAIN_DRAGGING,
94 COL_MAIN_DRAGGING_HIGHLIGHT,
95 COL_MAIN_DRAGGING_LOWLIGHT,
96 COL_TARGET,
97 COL_TARGET_HIGHLIGHT,
98 COL_TARGET_LOWLIGHT,
99 NCOLOURS
100};
101
102/*
103 * Board layout is a simple array of bytes. Each byte holds:
104 */
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 */
109#define MAXDIST 251
110/* all other values indicate distance back to previous square of same block */
111#define ISDIST(x) ( (unsigned char)((x)-1) <= MAXDIST-1 )
112#define DIST(x) (x)
113#define ISANCHOR(x) ( (x)==ANCHOR || (x)==MAINANCHOR )
114#define ISBLOCK(x) ( ISANCHOR(x) || ISDIST(x) )
115
116/*
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
120 * practice).
121 */
122#define MAXWID MAXDIST
123
124struct game_params {
125 int w, h;
126 int maxmoves;
127};
128
129struct game_immutable_state {
130 int refcount;
131 unsigned char *forcefield;
132};
133
134struct game_solution {
135 int nmoves;
136 int *moves; /* just like from solve_board() */
137 int refcount;
138};
139
140struct game_state {
141 int w, h;
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 */
146 int movecount;
147 int completed;
148 int cheated;
149 struct game_immutable_state *imm;
150 struct game_solution *soln;
151 int soln_index;
152};
153
154static game_params *default_params(void)
155{
156 game_params *ret = snew(game_params);
157
158 ret->w = 7;
159 ret->h = 6;
160 ret->maxmoves = 40;
161
162 return ret;
163}
164
165static const struct game_params slide_presets[] = {
166 {7, 6, 25},
167 {7, 6, -1},
168 {8, 6, -1},
169};
170
171static int game_fetch_preset(int i, char **name, game_params **params)
172{
173 game_params *ret;
174 char str[80];
175
176 if (i < 0 || i >= lenof(slide_presets))
177 return FALSE;
178
179 ret = snew(game_params);
180 *ret = slide_presets[i];
181
182 sprintf(str, "%dx%d", ret->w, ret->h);
183 if (ret->maxmoves >= 0)
184 sprintf(str + strlen(str), ", max %d moves", ret->maxmoves);
185 else
186 sprintf(str + strlen(str), ", no move limit");
187
188 *name = dupstr(str);
189 *params = ret;
190 return TRUE;
191}
192
193static void free_params(game_params *params)
194{
195 sfree(params);
196}
197
198static game_params *dup_params(const game_params *params)
199{
200 game_params *ret = snew(game_params);
201 *ret = *params; /* structure copy */
202 return ret;
203}
204
205static void decode_params(game_params *params, char const *string)
206{
207 params->w = params->h = atoi(string);
208 while (*string && isdigit((unsigned char)*string)) string++;
209 if (*string == 'x') {
210 string++;
211 params->h = atoi(string);
212 while (*string && isdigit((unsigned char)*string)) string++;
213 }
214 if (*string == 'm') {
215 string++;
216 params->maxmoves = atoi(string);
217 while (*string && isdigit((unsigned char)*string)) string++;
218 } else if (*string == 'u') {
219 string++;
220 params->maxmoves = -1;
221 }
222}
223
224static char *encode_params(const game_params *params, int full)
225{
226 char data[256];
227
228 sprintf(data, "%dx%d", params->w, params->h);
229 if (params->maxmoves >= 0)
230 sprintf(data + strlen(data), "m%d", params->maxmoves);
231 else
232 sprintf(data + strlen(data), "u");
233
234 return dupstr(data);
235}
236
237static config_item *game_configure(const game_params *params)
238{
239 config_item *ret;
240 char buf[80];
241
242 ret = snewn(4, config_item);
243
244 ret[0].name = "Width";
245 ret[0].type = C_STRING;
246 sprintf(buf, "%d", params->w);
247 ret[0].sval = dupstr(buf);
248 ret[0].ival = 0;
249
250 ret[1].name = "Height";
251 ret[1].type = C_STRING;
252 sprintf(buf, "%d", params->h);
253 ret[1].sval = dupstr(buf);
254 ret[1].ival = 0;
255
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);
260 ret[2].ival = 0;
261
262 ret[3].name = NULL;
263 ret[3].type = C_END;
264 ret[3].sval = NULL;
265 ret[3].ival = 0;
266
267 return ret;
268}
269
270static game_params *custom_params(const config_item *cfg)
271{
272 game_params *ret = snew(game_params);
273
274 ret->w = atoi(cfg[0].sval);
275 ret->h = atoi(cfg[1].sval);
276 ret->maxmoves = atoi(cfg[2].sval);
277
278 return ret;
279}
280
281static char *validate_params(const game_params *params, int full)
282{
283 if (params->w > MAXWID)
284 return "Width must be at most " STR(MAXWID);
285
286 if (params->w < 5)
287 return "Width must be at least 5";
288 if (params->h < 4)
289 return "Height must be at least 4";
290
291 return NULL;
292}
293
294static char *board_text_format(int w, int h, unsigned char *data,
295 unsigned char *forcefield)
296{
297 int wh = w*h;
298 int *dsf = snew_dsf(wh);
299 int i, x, y;
300 int retpos, retlen = (w*2+2)*(h*2+1)+1;
301 char *ret = snewn(retlen, char);
302
303 for (i = 0; i < wh; i++)
304 if (ISDIST(data[i]))
305 dsf_merge(dsf, i - data[i], i);
306 retpos = 0;
307 for (y = 0; y < 2*h+1; y++) {
308 for (x = 0; x < 2*w+1; x++) {
309 int v;
310 int i = (y/2)*w+(x/2);
311
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 ? '*' : '%')
316
317 if (y % 2 && x % 2) {
318 int j = dtype(i);
319 v = dchar(j);
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);
323 if (j1 != j2)
324 v = '|';
325 else
326 v = dchar(j1);
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);
330 if (j1 != j2)
331 v = '-';
332 else
333 v = dchar(j1);
334 } else {
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)
340 v = dchar(j1);
341 else if (j1 == j2 && j3 == j4)
342 v = '|';
343 else if (j1 == j3 && j2 == j4)
344 v = '-';
345 else
346 v = '+';
347 }
348
349 assert(retpos < retlen);
350 ret[retpos++] = v;
351 }
352 assert(retpos < retlen);
353 ret[retpos++] = '\n';
354 }
355 assert(retpos < retlen);
356 ret[retpos++] = '\0';
357 assert(retpos == retlen);
358
359 return ret;
360}
361
362/* ----------------------------------------------------------------------
363 * Solver.
364 */
365
366/*
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.
371 *
372 * `prev' links each board to the board position from which it was
373 * most efficiently derived.
374 */
375struct board {
376 int w, h;
377 int dist;
378 struct board *prev;
379 unsigned char *data;
380};
381
382static int boardcmp(void *av, void *bv)
383{
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);
387}
388
389static struct board *newboard(int w, int h, unsigned char *data)
390{
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);
394 b->w = w;
395 b->h = h;
396 b->dist = -1;
397 b->prev = NULL;
398 return b;
399}
400
401/*
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.
405 *
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.
412 */
413static int solve_board(int w, int h, unsigned char *board,
414 unsigned char *forcefield, int tx, int ty,
415 int movelimit, int **moveout)
416{
417 int wh = w*h;
418 struct board *b, *b2, *b3;
419 int *next, *anchors, *which;
420 int *movereached, *movequeue, mqhead, mqtail;
421 tree234 *sorted, *queue;
422 int i, j, dir;
423 int qlen, lastdist;
424 int ret;
425
426#ifdef SOLVER_DIAGNOSTICS
427 {
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];
432 if (ISDIST(c))
433 printf("D%-3d", c);
434 else if (c == MAINANCHOR)
435 printf("M ");
436 else if (c == ANCHOR)
437 printf("A ");
438 else if (c == WALL)
439 printf("W ");
440 else if (c == EMPTY)
441 printf("E ");
442 }
443 printf("\n");
444 }
445
446 printf("Starting solver for:\n%s\n", t);
447 sfree(t);
448 }
449#endif
450
451 sorted = newtree234(boardcmp);
452 queue = newtree234(NULL);
453
454 b = newboard(w, h, board);
455 b->dist = 0;
456 add234(sorted, b);
457 addpos234(queue, b, 0);
458 qlen = 1;
459
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);
465 lastdist = -1;
466
467 while ((b = delpos234(queue, 0)) != NULL) {
468 qlen--;
469 if (movelimit >= 0 && b->dist >= movelimit) {
470 /*
471 * The problem is not soluble in under `movelimit'
472 * moves, so we can quit right now.
473 */
474 b2 = NULL;
475 goto done;
476 }
477 if (b->dist != lastdist) {
478#ifdef SOLVER_DIAGNOSTICS
479 printf("dist %d (%d)\n", b->dist, count234(sorted));
480#endif
481 lastdist = b->dist;
482 }
483 /*
484 * Find all the anchors and form a linked list of the
485 * squares within each block.
486 */
487 for (i = 0; i < wh; i++) {
488 next[i] = -1;
489 anchors[i] = FALSE;
490 which[i] = -1;
491 if (ISANCHOR(b->data[i])) {
492 anchors[i] = TRUE;
493 which[i] = i;
494 } else if (ISDIST(b->data[i])) {
495 j = i - b->data[i];
496 next[j] = i;
497 which[i] = which[j];
498 }
499 }
500
501 /*
502 * For each anchor, do an array-based BFS to find all the
503 * places we can slide it to.
504 */
505 for (i = 0; i < wh; i++) {
506 if (!anchors[i])
507 continue;
508
509 mqhead = mqtail = 0;
510 for (j = 0; j < wh; j++)
511 movereached[j] = FALSE;
512 movequeue[mqtail++] = i;
513 while (mqhead < mqtail) {
514 int pos = movequeue[mqhead++];
515
516 /*
517 * Try to move in each direction from here.
518 */
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;
524 int d = newpos - i;
525
526 /*
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
530 * block.
531 */
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])))
537 /* ok */;
538 else
539 break;
540 }
541 if (j >= 0)
542 continue; /* this direction wasn't feasible */
543
544 /*
545 * If we've already tried moving this piece
546 * here, leave it.
547 */
548 if (movereached[newpos])
549 continue;
550 movereached[newpos] = TRUE;
551 movequeue[mqtail++] = newpos;
552
553 /*
554 * We have a viable move. Make it.
555 */
556 b2 = newboard(w, h, b->data);
557 for (j = i; j >= 0; j = next[j])
558 b2->data[j] = EMPTY;
559 for (j = i; j >= 0; j = next[j])
560 b2->data[j+d] = b->data[j];
561
562 b3 = add234(sorted, b2);
563 if (b3 != b2) {
564 sfree(b2); /* we already got one */
565 } else {
566 b2->dist = b->dist + 1;
567 b2->prev = b;
568 addpos234(queue, b2, qlen++);
569 if (b2->data[ty*w+tx] == MAINANCHOR)
570 goto done; /* search completed! */
571 }
572 }
573 }
574 }
575 }
576 b2 = NULL;
577
578 done:
579
580 if (b2) {
581 ret = b2->dist;
582 if (moveout) {
583 /*
584 * Now b2 represents the solved position. Backtrack to
585 * output the solution.
586 */
587 *moveout = snewn(ret * 2, int);
588 j = ret * 2;
589
590 while (b2->prev) {
591 int from = -1, to = -1;
592
593 b = b2->prev;
594
595 /*
596 * Scan b and b2 to find out which piece has
597 * moved.
598 */
599 for (i = 0; i < wh; i++) {
600 if (ISANCHOR(b->data[i]) && !ISANCHOR(b2->data[i])) {
601 assert(from == -1);
602 from = i;
603 } else if (!ISANCHOR(b->data[i]) && ISANCHOR(b2->data[i])){
604 assert(to == -1);
605 to = i;
606 }
607 }
608
609 assert(from >= 0 && to >= 0);
610 assert(j >= 2);
611 (*moveout)[--j] = to;
612 (*moveout)[--j] = from;
613
614 b2 = b;
615 }
616 assert(j == 0);
617 }
618 } else {
619 ret = -1; /* no solution */
620 if (moveout)
621 *moveout = NULL;
622 }
623
624 freetree234(queue);
625
626 while ((b = delpos234(sorted, 0)) != NULL)
627 sfree(b);
628 freetree234(sorted);
629
630 sfree(next);
631 sfree(anchors);
632 sfree(movereached);
633 sfree(movequeue);
634 sfree(which);
635
636 return ret;
637}
638
639/* ----------------------------------------------------------------------
640 * Random board generation.
641 */
642
643static 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)
646{
647 int wh = w*h;
648 unsigned char *board, *board2, *forcefield;
649 unsigned char *tried_merge;
650 int *dsf;
651 int *list, nlist, pos;
652 int tx, ty;
653 int i, j;
654 int moves = 0; /* placate optimiser */
655
656 /*
657 * Set up a board and fill it with singletons, except for a
658 * border of walls.
659 */
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;
669
670 tried_merge = snewn(wh * wh, unsigned char);
671 memset(tried_merge, 0, wh*wh);
672 dsf = snew_dsf(wh);
673
674 /*
675 * Invent a main piece at one extreme. (FIXME: vary the
676 * extreme, and the piece.)
677 */
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);
682
683 /*
684 * Invent a target position. (FIXME: vary this too.)
685 */
686 tx = w-2;
687 ty = h-3;
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;
690
691 /*
692 * Gradually remove singletons until the game becomes soluble.
693 */
694 for (j = w; j-- > 0 ;)
695 for (i = h; i-- > 0 ;)
696 if (board[i*w+j] == ANCHOR) {
697 /*
698 * See if the board is already soluble.
699 */
700 if ((moves = solve_board(w, h, board, forcefield,
701 tx, ty, movelimit, NULL)) >= 0)
702 goto soluble;
703
704 /*
705 * Otherwise, remove this piece.
706 */
707 board[i*w+j] = EMPTY;
708 }
709 assert(!"We shouldn't get here");
710 soluble:
711
712 /*
713 * Make a list of all the inter-block edges on the board.
714 */
715 list = snewn(wh*2, int);
716 nlist = 0;
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 */
723
724 /*
725 * Now go through that list in random order, trying to merge
726 * the blocks on each side of each edge.
727 */
728 shuffle(list, nlist, sizeof(*list), rs);
729 while (nlist > 0) {
730 int x1, y1, p1, c1;
731 int x2, y2, p2, c2;
732
733 pos = list[--nlist];
734 y1 = y2 = pos / (w*2);
735 x1 = x2 = (pos / 2) % w;
736 if (pos % 2)
737 y2++;
738 else
739 x2++;
740 p1 = y1*w+x1;
741 p2 = y2*w+x2;
742
743 /*
744 * Immediately abandon the attempt if we've already tried
745 * to merge the same pair of blocks along a different
746 * edge.
747 */
748 c1 = dsf_canonify(dsf, p1);
749 c2 = dsf_canonify(dsf, p2);
750 if (tried_merge[c1 * wh + c2])
751 continue;
752
753 /*
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.
757 */
758 if (!ISBLOCK(board[p1]) || !ISBLOCK(board[p2]))
759 continue;
760 while (ISDIST(board[p1]))
761 p1 -= board[p1];
762 while (ISDIST(board[p2]))
763 p2 -= board[p2];
764 if (board[p1] == MAINANCHOR || board[p2] == MAINANCHOR || p1 == p2)
765 continue;
766
767 /*
768 * We can merge these blocks. Try it, and see if the
769 * puzzle remains soluble.
770 */
771 memcpy(board2, board, wh);
772 j = -1;
773 while (p1 < wh || p2 < wh) {
774 /*
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
777 * block list.
778 */
779 i = min(p1, p2);
780 if (j < 0) {
781 board[i] = ANCHOR;
782 } else {
783 assert(i - j <= MAXDIST);
784 board[i] = DIST(i - j);
785 }
786 j = i;
787
788 /*
789 * Now advance whichever list that came from.
790 */
791 if (i == p1) {
792 do {
793 p1++;
794 } while (p1 < wh && board[p1] != DIST(p1-i));
795 } else {
796 do {
797 p2++;
798 } while (p2 < wh && board[p2] != DIST(p2-i));
799 }
800 }
801 j = solve_board(w, h, board, forcefield, tx, ty, movelimit, NULL);
802 if (j < 0) {
803 /*
804 * Didn't work. Revert the merge.
805 */
806 memcpy(board, board2, wh);
807 tried_merge[c1 * wh + c2] = tried_merge[c2 * wh + c1] = TRUE;
808 } else {
809 int c;
810
811 moves = j;
812
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]);
821 }
822 }
823
824 sfree(dsf);
825 sfree(list);
826 sfree(tried_merge);
827 sfree(board2);
828
829 *rtx = tx;
830 *rty = ty;
831 *rboard = board;
832 *rforcefield = forcefield;
833 *minmoves = moves;
834}
835
836/* ----------------------------------------------------------------------
837 * End of solver/generator code.
838 */
839
840static char *new_game_desc(const game_params *params, random_state *rs,
841 char **aux, int interactive)
842{
843 int w = params->w, h = params->h, wh = w*h;
844 int tx, ty, minmoves;
845 unsigned char *board, *forcefield;
846 char *ret, *p;
847 int i;
848
849 generate_board(params->w, params->h, &tx, &ty, &minmoves, rs,
850 &board, &forcefield, params->maxmoves);
851#ifdef GENERATOR_DIAGNOSTICS
852 {
853 char *t = board_text_format(params->w, params->h, board);
854 printf("%s\n", t);
855 sfree(t);
856 }
857#endif
858
859 /*
860 * Encode as a game ID.
861 */
862 ret = snewn(wh * 6 + 40, char);
863 p = ret;
864 i = 0;
865 while (i < wh) {
866 if (ISDIST(board[i])) {
867 p += sprintf(p, "d%d", board[i]);
868 i++;
869 } else {
870 int count = 1;
871 int b = board[i], f = forcefield[i];
872 int c = (b == ANCHOR ? 'a' :
873 b == MAINANCHOR ? 'm' :
874 b == EMPTY ? 'e' :
875 /* b == WALL ? */ 'w');
876 if (f) *p++ = 'f';
877 *p++ = c;
878 i++;
879 while (i < wh && board[i] == b && forcefield[i] == f)
880 i++, count++;
881 if (count > 1)
882 p += sprintf(p, "%d", count);
883 }
884 }
885 p += sprintf(p, ",%d,%d,%d", tx, ty, minmoves);
886 ret = sresize(ret, p+1 - ret, char);
887
888 sfree(board);
889 sfree(forcefield);
890
891 return ret;
892}
893
894static char *validate_desc(const game_params *params, const char *desc)
895{
896 int w = params->w, h = params->h, wh = w*h;
897 int *active, *link;
898 int mains = 0;
899 int i, tx, ty, minmoves;
900 char *ret;
901
902 active = snewn(wh, int);
903 link = snewn(wh, int);
904 i = 0;
905
906 while (*desc && *desc != ',') {
907 if (i >= wh) {
908 ret = "Too much data in game description";
909 goto done;
910 }
911 link[i] = -1;
912 active[i] = FALSE;
913 if (*desc == 'f' || *desc == 'F') {
914 desc++;
915 if (!*desc) {
916 ret = "Expected another character after 'f' in game "
917 "description";
918 goto done;
919 }
920 }
921
922 if (*desc == 'd' || *desc == 'D') {
923 int dist;
924
925 desc++;
926 if (!isdigit((unsigned char)*desc)) {
927 ret = "Expected a number after 'd' in game description";
928 goto done;
929 }
930 dist = atoi(desc);
931 while (*desc && isdigit((unsigned char)*desc)) desc++;
932
933 if (dist <= 0 || dist > i) {
934 ret = "Out-of-range number after 'd' in game description";
935 goto done;
936 }
937
938 if (!active[i - dist]) {
939 ret = "Invalid back-reference in game description";
940 goto done;
941 }
942
943 link[i] = i - dist;
944
945 active[i] = TRUE;
946 active[link[i]] = FALSE;
947 i++;
948 } else {
949 int c = *desc++;
950 int count = 1;
951
952 if (!strchr("aAmMeEwW", c)) {
953 ret = "Invalid character in game description";
954 goto done;
955 }
956 if (isdigit((unsigned char)*desc)) {
957 count = atoi(desc);
958 while (*desc && isdigit((unsigned char)*desc)) desc++;
959 }
960 if (i + count > wh) {
961 ret = "Too much data in game description";
962 goto done;
963 }
964 while (count-- > 0) {
965 active[i] = (strchr("aAmM", c) != NULL);
966 link[i] = -1;
967 if (strchr("mM", c) != NULL) {
968 mains++;
969 }
970 i++;
971 }
972 }
973 }
974 if (mains != 1) {
975 ret = (mains == 0 ? "No main piece specified in game description" :
976 "More than one main piece specified in game description");
977 goto done;
978 }
979 if (i < wh) {
980 ret = "Not enough data in game description";
981 goto done;
982 }
983
984 /*
985 * Now read the target coordinates.
986 */
987 i = sscanf(desc, ",%d,%d,%d", &tx, &ty, &minmoves);
988 if (i < 2) {
989 ret = "No target coordinates specified";
990 goto done;
991 /*
992 * (but minmoves is optional)
993 */
994 }
995
996 ret = NULL;
997
998 done:
999 sfree(active);
1000 sfree(link);
1001 return ret;
1002}
1003
1004static game_state *new_game(midend *me, const game_params *params,
1005 const char *desc)
1006{
1007 int w = params->w, h = params->h, wh = w*h;
1008 game_state *state;
1009 int i;
1010
1011 state = snew(game_state);
1012 state->w = w;
1013 state->h = h;
1014 state->board = snewn(wh, unsigned char);
1015 state->lastmoved = state->lastmoved_pos = -1;
1016 state->movecount = 0;
1017 state->imm = snew(struct game_immutable_state);
1018 state->imm->refcount = 1;
1019 state->imm->forcefield = snewn(wh, unsigned char);
1020
1021 i = 0;
1022
1023 while (*desc && *desc != ',') {
1024 int f = FALSE;
1025
1026 assert(i < wh);
1027
1028 if (*desc == 'f') {
1029 f = TRUE;
1030 desc++;
1031 assert(*desc);
1032 }
1033
1034 if (*desc == 'd' || *desc == 'D') {
1035 int dist;
1036
1037 desc++;
1038 dist = atoi(desc);
1039 while (*desc && isdigit((unsigned char)*desc)) desc++;
1040
1041 state->board[i] = DIST(dist);
1042 state->imm->forcefield[i] = f;
1043
1044 i++;
1045 } else {
1046 int c = *desc++;
1047 int count = 1;
1048
1049 if (isdigit((unsigned char)*desc)) {
1050 count = atoi(desc);
1051 while (*desc && isdigit((unsigned char)*desc)) desc++;
1052 }
1053 assert(i + count <= wh);
1054
1055 c = (c == 'a' || c == 'A' ? ANCHOR :
1056 c == 'm' || c == 'M' ? MAINANCHOR :
1057 c == 'e' || c == 'E' ? EMPTY :
1058 /* c == 'w' || c == 'W' ? */ WALL);
1059
1060 while (count-- > 0) {
1061 state->board[i] = c;
1062 state->imm->forcefield[i] = f;
1063 i++;
1064 }
1065 }
1066 }
1067
1068 /*
1069 * Now read the target coordinates.
1070 */
1071 state->tx = state->ty = 0;
1072 state->minmoves = -1;
1073 i = sscanf(desc, ",%d,%d,%d", &state->tx, &state->ty, &state->minmoves);
1074
1075 if (state->board[state->ty*w+state->tx] == MAINANCHOR)
1076 state->completed = 0; /* already complete! */
1077 else
1078 state->completed = -1;
1079
1080 state->cheated = FALSE;
1081 state->soln = NULL;
1082 state->soln_index = -1;
1083
1084 return state;
1085}
1086
1087static game_state *dup_game(const game_state *state)
1088{
1089 int w = state->w, h = state->h, wh = w*h;
1090 game_state *ret = snew(game_state);
1091
1092 ret->w = state->w;
1093 ret->h = state->h;
1094 ret->board = snewn(wh, unsigned char);
1095 memcpy(ret->board, state->board, wh);
1096 ret->tx = state->tx;
1097 ret->ty = state->ty;
1098 ret->minmoves = state->minmoves;
1099 ret->lastmoved = state->lastmoved;
1100 ret->lastmoved_pos = state->lastmoved_pos;
1101 ret->movecount = state->movecount;
1102 ret->completed = state->completed;
1103 ret->cheated = state->cheated;
1104 ret->imm = state->imm;
1105 ret->imm->refcount++;
1106 ret->soln = state->soln;
1107 ret->soln_index = state->soln_index;
1108 if (ret->soln)
1109 ret->soln->refcount++;
1110
1111 return ret;
1112}
1113
1114static void free_game(game_state *state)
1115{
1116 if (--state->imm->refcount <= 0) {
1117 sfree(state->imm->forcefield);
1118 sfree(state->imm);
1119 }
1120 if (state->soln && --state->soln->refcount <= 0) {
1121 sfree(state->soln->moves);
1122 sfree(state->soln);
1123 }
1124 sfree(state->board);
1125 sfree(state);
1126}
1127
1128static char *solve_game(const game_state *state, const game_state *currstate,
1129 const char *aux, char **error)
1130{
1131 int *moves;
1132 int nmoves;
1133 int i;
1134 char *ret, *p, sep;
1135
1136 /*
1137 * Run the solver and attempt to find the shortest solution
1138 * from the current position.
1139 */
1140 nmoves = solve_board(state->w, state->h, state->board,
1141 state->imm->forcefield, state->tx, state->ty,
1142 -1, &moves);
1143
1144 if (nmoves < 0) {
1145 *error = "Unable to find a solution to this puzzle";
1146 return NULL;
1147 }
1148 if (nmoves == 0) {
1149 *error = "Puzzle is already solved";
1150 return NULL;
1151 }
1152
1153 /*
1154 * Encode the resulting solution as a move string.
1155 */
1156 ret = snewn(nmoves * 40, char);
1157 p = ret;
1158 sep = 'S';
1159
1160 for (i = 0; i < nmoves; i++) {
1161 p += sprintf(p, "%c%d-%d", sep, moves[i*2], moves[i*2+1]);
1162 sep = ',';
1163 }
1164
1165 sfree(moves);
1166 assert(p - ret < nmoves * 40);
1167 ret = sresize(ret, p+1 - ret, char);
1168
1169 return ret;
1170}
1171
1172static int game_can_format_as_text_now(const game_params *params)
1173{
1174 return TRUE;
1175}
1176
1177static char *game_text_format(const game_state *state)
1178{
1179 return board_text_format(state->w, state->h, state->board,
1180 state->imm->forcefield);
1181}
1182
1183struct game_ui {
1184 int dragging;
1185 int drag_anchor;
1186 int drag_offset_x, drag_offset_y;
1187 int drag_currpos;
1188 unsigned char *reachable;
1189 int *bfs_queue; /* used as scratch in interpret_move */
1190};
1191
1192static game_ui *new_ui(const game_state *state)
1193{
1194 int w = state->w, h = state->h, wh = w*h;
1195 game_ui *ui = snew(game_ui);
1196
1197 ui->dragging = FALSE;
1198 ui->drag_anchor = ui->drag_currpos = -1;
1199 ui->drag_offset_x = ui->drag_offset_y = -1;
1200 ui->reachable = snewn(wh, unsigned char);
1201 memset(ui->reachable, 0, wh);
1202 ui->bfs_queue = snewn(wh, int);
1203
1204 return ui;
1205}
1206
1207static void free_ui(game_ui *ui)
1208{
1209 sfree(ui->bfs_queue);
1210 sfree(ui->reachable);
1211 sfree(ui);
1212}
1213
1214static char *encode_ui(const game_ui *ui)
1215{
1216 return NULL;
1217}
1218
1219static void decode_ui(game_ui *ui, const char *encoding)
1220{
1221}
1222
1223static void game_changed_state(game_ui *ui, const game_state *oldstate,
1224 const game_state *newstate)
1225{
1226}
1227
1228#define PREFERRED_TILESIZE 32
1229#define TILESIZE (ds->tilesize)
1230#define BORDER (TILESIZE/2)
1231#define COORD(x) ( (x) * TILESIZE + BORDER )
1232#define FROMCOORD(x) ( ((x) - BORDER + TILESIZE) / TILESIZE - 1 )
1233#define BORDER_WIDTH (1 + TILESIZE/20)
1234#define HIGHLIGHT_WIDTH (1 + TILESIZE/16)
1235
1236#define FLASH_INTERVAL 0.10F
1237#define FLASH_TIME 3*FLASH_INTERVAL
1238
1239struct game_drawstate {
1240 int tilesize;
1241 int w, h;
1242 unsigned long *grid; /* what's currently displayed */
1243 int started;
1244};
1245
1246static char *interpret_move(const game_state *state, game_ui *ui,
1247 const game_drawstate *ds,
1248 int x, int y, int button)
1249{
1250 int w = state->w, h = state->h, wh = w*h;
1251 int tx, ty, i, j;
1252 int qhead, qtail;
1253
1254 if (button == LEFT_BUTTON) {
1255 tx = FROMCOORD(x);
1256 ty = FROMCOORD(y);
1257
1258 if (tx < 0 || tx >= w || ty < 0 || ty >= h ||
1259 !ISBLOCK(state->board[ty*w+tx]))
1260 return NULL; /* this click has no effect */
1261
1262 /*
1263 * User has clicked on a block. Find the block's anchor
1264 * and register that we've started dragging it.
1265 */
1266 i = ty*w+tx;
1267 while (ISDIST(state->board[i]))
1268 i -= state->board[i];
1269 assert(i >= 0 && i < wh);
1270
1271 ui->dragging = TRUE;
1272 ui->drag_anchor = i;
1273 ui->drag_offset_x = tx - (i % w);
1274 ui->drag_offset_y = ty - (i / w);
1275 ui->drag_currpos = i;
1276
1277 /*
1278 * Now we immediately bfs out from the current location of
1279 * the anchor, to find all the places to which this block
1280 * can be dragged.
1281 */
1282 memset(ui->reachable, FALSE, wh);
1283 qhead = qtail = 0;
1284 ui->reachable[i] = TRUE;
1285 ui->bfs_queue[qtail++] = i;
1286 for (j = i; j < wh; j++)
1287 if (state->board[j] == DIST(j - i))
1288 i = j;
1289 while (qhead < qtail) {
1290 int pos = ui->bfs_queue[qhead++];
1291 int x = pos % w, y = pos / w;
1292 int dir;
1293
1294 for (dir = 0; dir < 4; dir++) {
1295 int dx = (dir == 0 ? -1 : dir == 1 ? +1 : 0);
1296 int dy = (dir == 2 ? -1 : dir == 3 ? +1 : 0);
1297 int newpos;
1298
1299 if (x + dx < 0 || x + dx >= w ||
1300 y + dy < 0 || y + dy >= h)
1301 continue;
1302
1303 newpos = pos + dy*w + dx;
1304 if (ui->reachable[newpos])
1305 continue; /* already done this one */
1306
1307 /*
1308 * Now search the grid to see if the block we're
1309 * dragging could fit into this space.
1310 */
1311 for (j = i; j >= 0; j = (ISDIST(state->board[j]) ?
1312 j - state->board[j] : -1)) {
1313 int jx = (j+pos-ui->drag_anchor) % w;
1314 int jy = (j+pos-ui->drag_anchor) / w;
1315 int j2;
1316
1317 if (jx + dx < 0 || jx + dx >= w ||
1318 jy + dy < 0 || jy + dy >= h)
1319 break; /* this position isn't valid at all */
1320
1321 j2 = (j+pos-ui->drag_anchor) + dy*w + dx;
1322
1323 if (state->board[j2] == EMPTY &&
1324 (!state->imm->forcefield[j2] ||
1325 state->board[ui->drag_anchor] == MAINANCHOR))
1326 continue;
1327 while (ISDIST(state->board[j2]))
1328 j2 -= state->board[j2];
1329 assert(j2 >= 0 && j2 < wh);
1330 if (j2 == ui->drag_anchor)
1331 continue;
1332 else
1333 break;
1334 }
1335
1336 if (j < 0) {
1337 /*
1338 * If we got to the end of that loop without
1339 * disqualifying this position, mark it as
1340 * reachable for this drag.
1341 */
1342 ui->reachable[newpos] = TRUE;
1343 ui->bfs_queue[qtail++] = newpos;
1344 }
1345 }
1346 }
1347
1348 /*
1349 * And that's it. Update the display to reflect the start
1350 * of a drag.
1351 */
1352 return "";
1353 } else if (button == LEFT_DRAG && ui->dragging) {
1354 int dist, distlimit, dx, dy, s, px, py;
1355
1356 tx = FROMCOORD(x);
1357 ty = FROMCOORD(y);
1358
1359 tx -= ui->drag_offset_x;
1360 ty -= ui->drag_offset_y;
1361
1362 /*
1363 * Now search outwards from (tx,ty), in order of Manhattan
1364 * distance, until we find a reachable square.
1365 */
1366 distlimit = w+tx;
1367 distlimit = max(distlimit, h+ty);
1368 distlimit = max(distlimit, tx);
1369 distlimit = max(distlimit, ty);
1370 for (dist = 0; dist <= distlimit; dist++) {
1371 for (dx = -dist; dx <= dist; dx++)
1372 for (s = -1; s <= +1; s += 2) {
1373 dy = s * (dist - abs(dx));
1374 px = tx + dx;
1375 py = ty + dy;
1376 if (px >= 0 && px < w && py >= 0 && py < h &&
1377 ui->reachable[py*w+px]) {
1378 ui->drag_currpos = py*w+px;
1379 return "";
1380 }
1381 }
1382 }
1383 return NULL; /* give up - this drag has no effect */
1384 } else if (button == LEFT_RELEASE && ui->dragging) {
1385 char data[256], *str;
1386
1387 /*
1388 * Terminate the drag, and if the piece has actually moved
1389 * then return a move string quoting the old and new
1390 * locations of the piece's anchor.
1391 */
1392 if (ui->drag_anchor != ui->drag_currpos) {
1393 sprintf(data, "M%d-%d", ui->drag_anchor, ui->drag_currpos);
1394 str = dupstr(data);
1395 } else
1396 str = ""; /* null move; just update the UI */
1397
1398 ui->dragging = FALSE;
1399 ui->drag_anchor = ui->drag_currpos = -1;
1400 ui->drag_offset_x = ui->drag_offset_y = -1;
1401 memset(ui->reachable, 0, wh);
1402
1403 return str;
1404 } else if (button == ' ' && state->soln) {
1405 /*
1406 * Make the next move in the stored solution.
1407 */
1408 char data[256];
1409 int a1, a2;
1410
1411 a1 = state->soln->moves[state->soln_index*2];
1412 a2 = state->soln->moves[state->soln_index*2+1];
1413 if (a1 == state->lastmoved_pos)
1414 a1 = state->lastmoved;
1415
1416 sprintf(data, "M%d-%d", a1, a2);
1417 return dupstr(data);
1418 }
1419
1420 return NULL;
1421}
1422
1423static int move_piece(int w, int h, const unsigned char *src,
1424 unsigned char *dst, unsigned char *ff, int from, int to)
1425{
1426 int wh = w*h;
1427 int i, j;
1428
1429 if (!ISANCHOR(dst[from]))
1430 return FALSE;
1431
1432 /*
1433 * Scan to the far end of the piece's linked list.
1434 */
1435 for (i = j = from; j < wh; j++)
1436 if (src[j] == DIST(j - i))
1437 i = j;
1438
1439 /*
1440 * Remove the piece from its old location in the new
1441 * game state.
1442 */
1443 for (j = i; j >= 0; j = (ISDIST(src[j]) ? j - src[j] : -1))
1444 dst[j] = EMPTY;
1445
1446 /*
1447 * And put it back in at the new location.
1448 */
1449 for (j = i; j >= 0; j = (ISDIST(src[j]) ? j - src[j] : -1)) {
1450 int jn = j + to - from;
1451 if (jn < 0 || jn >= wh)
1452 return FALSE;
1453 if (dst[jn] == EMPTY && (!ff[jn] || src[from] == MAINANCHOR)) {
1454 dst[jn] = src[j];
1455 } else {
1456 return FALSE;
1457 }
1458 }
1459
1460 return TRUE;
1461}
1462
1463static game_state *execute_move(const game_state *state, const char *move)
1464{
1465 int w = state->w, h = state->h /* , wh = w*h */;
1466 char c;
1467 int a1, a2, n, movesize;
1468 game_state *ret = dup_game(state);
1469
1470 while (*move) {
1471 c = *move;
1472 if (c == 'S') {
1473 /*
1474 * This is a solve move, so we just set up a stored
1475 * solution path.
1476 */
1477 if (ret->soln && --ret->soln->refcount <= 0) {
1478 sfree(ret->soln->moves);
1479 sfree(ret->soln);
1480 }
1481 ret->soln = snew(struct game_solution);
1482 ret->soln->nmoves = 0;
1483 ret->soln->moves = NULL;
1484 ret->soln->refcount = 1;
1485 ret->soln_index = 0;
1486 ret->cheated = TRUE;
1487
1488 movesize = 0;
1489 move++;
1490 while (1) {
1491 if (sscanf(move, "%d-%d%n", &a1, &a2, &n) != 2) {
1492 free_game(ret);
1493 return NULL;
1494 }
1495
1496 /*
1497 * Special case: if the first move in the solution
1498 * involves the piece for which we already have a
1499 * partial stored move, adjust the source point to
1500 * the original starting point of that piece.
1501 */
1502 if (ret->soln->nmoves == 0 && a1 == ret->lastmoved)
1503 a1 = ret->lastmoved_pos;
1504
1505 if (ret->soln->nmoves >= movesize) {
1506 movesize = (ret->soln->nmoves + 48) * 4 / 3;
1507 ret->soln->moves = sresize(ret->soln->moves,
1508 2*movesize, int);
1509 }
1510
1511 ret->soln->moves[2*ret->soln->nmoves] = a1;
1512 ret->soln->moves[2*ret->soln->nmoves+1] = a2;
1513 ret->soln->nmoves++;
1514 move += n;
1515 if (*move != ',')
1516 break;
1517 move++; /* eat comma */
1518 }
1519 } else if (c == 'M') {
1520 move++;
1521 if (sscanf(move, "%d-%d%n", &a1, &a2, &n) != 2 ||
1522 !move_piece(w, h, state->board, ret->board,
1523 state->imm->forcefield, a1, a2)) {
1524 free_game(ret);
1525 return NULL;
1526 }
1527 if (a1 == ret->lastmoved) {
1528 /*
1529 * If the player has moved the same piece as they
1530 * moved last time, don't increment the move
1531 * count. In fact, if they've put the piece back
1532 * where it started from, _decrement_ the move
1533 * count.
1534 */
1535 if (a2 == ret->lastmoved_pos) {
1536 ret->movecount--; /* reverted last move */
1537 ret->lastmoved = ret->lastmoved_pos = -1;
1538 } else {
1539 ret->lastmoved = a2;
1540 /* don't change lastmoved_pos */
1541 }
1542 } else {
1543 ret->lastmoved = a2;
1544 ret->lastmoved_pos = a1;
1545 ret->movecount++;
1546 }
1547
1548 /*
1549 * If we have a stored solution path, see if we've
1550 * strayed from it or successfully made the next move
1551 * along it.
1552 */
1553 if (ret->soln && ret->lastmoved_pos >= 0) {
1554 if (ret->lastmoved_pos !=
1555 ret->soln->moves[ret->soln_index*2]) {
1556 /* strayed from the path */
1557 ret->soln->refcount--;
1558 assert(ret->soln->refcount > 0);
1559 /* `state' at least still exists */
1560 ret->soln = NULL;
1561 ret->soln_index = -1;
1562 } else if (ret->lastmoved ==
1563 ret->soln->moves[ret->soln_index*2+1]) {
1564 /* advanced along the path */
1565 ret->soln_index++;
1566 if (ret->soln_index >= ret->soln->nmoves) {
1567 /* finished the path! */
1568 ret->soln->refcount--;
1569 assert(ret->soln->refcount > 0);
1570 /* `state' at least still exists */
1571 ret->soln = NULL;
1572 ret->soln_index = -1;
1573 }
1574 }
1575 }
1576
1577 if (ret->board[a2] == MAINANCHOR &&
1578 a2 == ret->ty * w + ret->tx && ret->completed < 0)
1579 ret->completed = ret->movecount;
1580 move += n;
1581 } else {
1582 free_game(ret);
1583 return NULL;
1584 }
1585 if (*move == ';')
1586 move++;
1587 else if (*move) {
1588 free_game(ret);
1589 return NULL;
1590 }
1591 }
1592
1593 return ret;
1594}
1595
1596/* ----------------------------------------------------------------------
1597 * Drawing routines.
1598 */
1599
1600static void game_compute_size(const game_params *params, int tilesize,
1601 int *x, int *y)
1602{
1603 /* fool the macros */
1604 struct dummy { int tilesize; } dummy, *ds = &dummy;
1605 dummy.tilesize = tilesize;
1606
1607 *x = params->w * TILESIZE + 2*BORDER;
1608 *y = params->h * TILESIZE + 2*BORDER;
1609}
1610
1611static void game_set_size(drawing *dr, game_drawstate *ds,
1612 const game_params *params, int tilesize)
1613{
1614 ds->tilesize = tilesize;
1615}
1616
1617static void raise_colour(float *target, float *src, float *limit)
1618{
1619 int i;
1620 for (i = 0; i < 3; i++)
1621 target[i] = (2*src[i] + limit[i]) / 3;
1622}
1623
1624static float *game_colours(frontend *fe, int *ncolours)
1625{
1626 float *ret = snewn(3 * NCOLOURS, float);
1627
1628 game_mkhighlight(fe, ret, COL_BACKGROUND, COL_HIGHLIGHT, COL_LOWLIGHT);
1629
1630 /*
1631 * When dragging a tile, we light it up a bit.
1632 */
1633 raise_colour(ret+3*COL_DRAGGING,
1634 ret+3*COL_BACKGROUND, ret+3*COL_HIGHLIGHT);
1635 raise_colour(ret+3*COL_DRAGGING_HIGHLIGHT,
1636 ret+3*COL_HIGHLIGHT, ret+3*COL_HIGHLIGHT);
1637 raise_colour(ret+3*COL_DRAGGING_LOWLIGHT,
1638 ret+3*COL_LOWLIGHT, ret+3*COL_HIGHLIGHT);
1639
1640 /*
1641 * The main tile is tinted blue.
1642 */
1643 ret[COL_MAIN * 3 + 0] = ret[COL_BACKGROUND * 3 + 0];
1644 ret[COL_MAIN * 3 + 1] = ret[COL_BACKGROUND * 3 + 1];
1645 ret[COL_MAIN * 3 + 2] = ret[COL_HIGHLIGHT * 3 + 2];
1646 game_mkhighlight_specific(fe, ret, COL_MAIN,
1647 COL_MAIN_HIGHLIGHT, COL_MAIN_LOWLIGHT);
1648
1649 /*
1650 * And we light that up a bit too when dragging.
1651 */
1652 raise_colour(ret+3*COL_MAIN_DRAGGING,
1653 ret+3*COL_MAIN, ret+3*COL_MAIN_HIGHLIGHT);
1654 raise_colour(ret+3*COL_MAIN_DRAGGING_HIGHLIGHT,
1655 ret+3*COL_MAIN_HIGHLIGHT, ret+3*COL_MAIN_HIGHLIGHT);
1656 raise_colour(ret+3*COL_MAIN_DRAGGING_LOWLIGHT,
1657 ret+3*COL_MAIN_LOWLIGHT, ret+3*COL_MAIN_HIGHLIGHT);
1658
1659 /*
1660 * The target area on the floor is tinted green.
1661 */
1662 ret[COL_TARGET * 3 + 0] = ret[COL_BACKGROUND * 3 + 0];
1663 ret[COL_TARGET * 3 + 1] = ret[COL_HIGHLIGHT * 3 + 1];
1664 ret[COL_TARGET * 3 + 2] = ret[COL_BACKGROUND * 3 + 2];
1665 game_mkhighlight_specific(fe, ret, COL_TARGET,
1666 COL_TARGET_HIGHLIGHT, COL_TARGET_LOWLIGHT);
1667
1668 *ncolours = NCOLOURS;
1669 return ret;
1670}
1671
1672static game_drawstate *game_new_drawstate(drawing *dr, const game_state *state)
1673{
1674 int w = state->w, h = state->h, wh = w*h;
1675 struct game_drawstate *ds = snew(struct game_drawstate);
1676 int i;
1677
1678 ds->tilesize = 0;
1679 ds->w = w;
1680 ds->h = h;
1681 ds->started = FALSE;
1682 ds->grid = snewn(wh, unsigned long);
1683 for (i = 0; i < wh; i++)
1684 ds->grid[i] = ~(unsigned long)0;
1685
1686 return ds;
1687}
1688
1689static void game_free_drawstate(drawing *dr, game_drawstate *ds)
1690{
1691 sfree(ds->grid);
1692 sfree(ds);
1693}
1694
1695#define BG_NORMAL 0x00000001UL
1696#define BG_TARGET 0x00000002UL
1697#define BG_FORCEFIELD 0x00000004UL
1698#define FLASH_LOW 0x00000008UL
1699#define FLASH_HIGH 0x00000010UL
1700#define FG_WALL 0x00000020UL
1701#define FG_MAIN 0x00000040UL
1702#define FG_NORMAL 0x00000080UL
1703#define FG_DRAGGING 0x00000100UL
1704#define FG_SHADOW 0x00000200UL
1705#define FG_SOLVEPIECE 0x00000400UL
1706#define FG_MAINPIECESH 11
1707#define FG_SHADOWSH 19
1708
1709#define PIECE_LBORDER 0x00000001UL
1710#define PIECE_TBORDER 0x00000002UL
1711#define PIECE_RBORDER 0x00000004UL
1712#define PIECE_BBORDER 0x00000008UL
1713#define PIECE_TLCORNER 0x00000010UL
1714#define PIECE_TRCORNER 0x00000020UL
1715#define PIECE_BLCORNER 0x00000040UL
1716#define PIECE_BRCORNER 0x00000080UL
1717#define PIECE_MASK 0x000000FFUL
1718
1719/*
1720 * Utility function.
1721 */
1722#define TYPE_MASK 0xF000
1723#define COL_MASK 0x0FFF
1724#define TYPE_RECT 0x0000
1725#define TYPE_TLCIRC 0x4000
1726#define TYPE_TRCIRC 0x5000
1727#define TYPE_BLCIRC 0x6000
1728#define TYPE_BRCIRC 0x7000
1729static void maybe_rect(drawing *dr, int x, int y, int w, int h,
1730 int coltype, int col2)
1731{
1732 int colour = coltype & COL_MASK, type = coltype & TYPE_MASK;
1733
1734 if (colour > NCOLOURS)
1735 return;
1736 if (type == TYPE_RECT) {
1737 draw_rect(dr, x, y, w, h, colour);
1738 } else {
1739 int cx, cy, r;
1740
1741 clip(dr, x, y, w, h);
1742
1743 cx = x;
1744 cy = y;
1745 r = w-1;
1746 if (type & 0x1000)
1747 cx += r;
1748 if (type & 0x2000)
1749 cy += r;
1750
1751 if (col2 == -1 || col2 == coltype) {
1752 assert(w == h);
1753 draw_circle(dr, cx, cy, r, colour, colour);
1754 } else {
1755 /*
1756 * We aim to draw a quadrant of a circle in two
1757 * different colours. We do this using Bresenham's
1758 * algorithm directly, because the Puzzles drawing API
1759 * doesn't have a draw-sector primitive.
1760 */
1761 int bx, by, bd, bd2;
1762 int xm = (type & 0x1000 ? -1 : +1);
1763 int ym = (type & 0x2000 ? -1 : +1);
1764
1765 by = r;
1766 bx = 0;
1767 bd = 0;
1768 while (by >= bx) {
1769 /*
1770 * Plot the point.
1771 */
1772 {
1773 int x1 = cx+xm*bx, y1 = cy+ym*bx;
1774 int x2, y2;
1775
1776 x2 = cx+xm*by; y2 = y1;
1777 draw_rect(dr, min(x1,x2), min(y1,y2),
1778 abs(x1-x2)+1, abs(y1-y2)+1, colour);
1779 x2 = x1; y2 = cy+ym*by;
1780 draw_rect(dr, min(x1,x2), min(y1,y2),
1781 abs(x1-x2)+1, abs(y1-y2)+1, col2);
1782 }
1783
1784 bd += 2*bx + 1;
1785 bd2 = bd - (2*by - 1);
1786 if (abs(bd2) < abs(bd)) {
1787 bd = bd2;
1788 by--;
1789 }
1790 bx++;
1791 }
1792 }
1793
1794 unclip(dr);
1795 }
1796}
1797
1798static void draw_wallpart(drawing *dr, game_drawstate *ds,
1799 int tx, int ty, unsigned long val,
1800 int cl, int cc, int ch)
1801{
1802 int coords[6];
1803
1804 draw_rect(dr, tx, ty, TILESIZE, TILESIZE, cc);
1805 if (val & PIECE_LBORDER)
1806 draw_rect(dr, tx, ty, HIGHLIGHT_WIDTH, TILESIZE,
1807 ch);
1808 if (val & PIECE_RBORDER)
1809 draw_rect(dr, tx+TILESIZE-HIGHLIGHT_WIDTH, ty,
1810 HIGHLIGHT_WIDTH, TILESIZE, cl);
1811 if (val & PIECE_TBORDER)
1812 draw_rect(dr, tx, ty, TILESIZE, HIGHLIGHT_WIDTH, ch);
1813 if (val & PIECE_BBORDER)
1814 draw_rect(dr, tx, ty+TILESIZE-HIGHLIGHT_WIDTH,
1815 TILESIZE, HIGHLIGHT_WIDTH, cl);
1816 if (!((PIECE_BBORDER | PIECE_LBORDER) &~ val)) {
1817 draw_rect(dr, tx, ty+TILESIZE-HIGHLIGHT_WIDTH,
1818 HIGHLIGHT_WIDTH, HIGHLIGHT_WIDTH, cl);
1819 clip(dr, tx, ty+TILESIZE-HIGHLIGHT_WIDTH,
1820 HIGHLIGHT_WIDTH, HIGHLIGHT_WIDTH);
1821 coords[0] = tx - 1;
1822 coords[1] = ty + TILESIZE - HIGHLIGHT_WIDTH - 1;
1823 coords[2] = tx + HIGHLIGHT_WIDTH;
1824 coords[3] = ty + TILESIZE - HIGHLIGHT_WIDTH - 1;
1825 coords[4] = tx - 1;
1826 coords[5] = ty + TILESIZE;
1827 draw_polygon(dr, coords, 3, ch, ch);
1828 unclip(dr);
1829 } else if (val & PIECE_BLCORNER) {
1830 draw_rect(dr, tx, ty+TILESIZE-HIGHLIGHT_WIDTH,
1831 HIGHLIGHT_WIDTH, HIGHLIGHT_WIDTH, ch);
1832 clip(dr, tx, ty+TILESIZE-HIGHLIGHT_WIDTH,
1833 HIGHLIGHT_WIDTH, HIGHLIGHT_WIDTH);
1834 coords[0] = tx - 1;
1835 coords[1] = ty + TILESIZE - HIGHLIGHT_WIDTH - 1;
1836 coords[2] = tx + HIGHLIGHT_WIDTH;
1837 coords[3] = ty + TILESIZE - HIGHLIGHT_WIDTH - 1;
1838 coords[4] = tx - 1;
1839 coords[5] = ty + TILESIZE;
1840 draw_polygon(dr, coords, 3, cl, cl);
1841 unclip(dr);
1842 }
1843 if (!((PIECE_TBORDER | PIECE_RBORDER) &~ val)) {
1844 draw_rect(dr, tx+TILESIZE-HIGHLIGHT_WIDTH, ty,
1845 HIGHLIGHT_WIDTH, HIGHLIGHT_WIDTH, cl);
1846 clip(dr, tx+TILESIZE-HIGHLIGHT_WIDTH, ty,
1847 HIGHLIGHT_WIDTH, HIGHLIGHT_WIDTH);
1848 coords[0] = tx + TILESIZE - HIGHLIGHT_WIDTH - 1;
1849 coords[1] = ty - 1;
1850 coords[2] = tx + TILESIZE;
1851 coords[3] = ty - 1;
1852 coords[4] = tx + TILESIZE - HIGHLIGHT_WIDTH - 1;
1853 coords[5] = ty + HIGHLIGHT_WIDTH;
1854 draw_polygon(dr, coords, 3, ch, ch);
1855 unclip(dr);
1856 } else if (val & PIECE_TRCORNER) {
1857 draw_rect(dr, tx+TILESIZE-HIGHLIGHT_WIDTH, ty,
1858 HIGHLIGHT_WIDTH, HIGHLIGHT_WIDTH, ch);
1859 clip(dr, tx+TILESIZE-HIGHLIGHT_WIDTH, ty,
1860 HIGHLIGHT_WIDTH, HIGHLIGHT_WIDTH);
1861 coords[0] = tx + TILESIZE - HIGHLIGHT_WIDTH - 1;
1862 coords[1] = ty - 1;
1863 coords[2] = tx + TILESIZE;
1864 coords[3] = ty - 1;
1865 coords[4] = tx + TILESIZE - HIGHLIGHT_WIDTH - 1;
1866 coords[5] = ty + HIGHLIGHT_WIDTH;
1867 draw_polygon(dr, coords, 3, cl, cl);
1868 unclip(dr);
1869 }
1870 if (val & PIECE_TLCORNER)
1871 draw_rect(dr, tx, ty, HIGHLIGHT_WIDTH, HIGHLIGHT_WIDTH, ch);
1872 if (val & PIECE_BRCORNER)
1873 draw_rect(dr, tx+TILESIZE-HIGHLIGHT_WIDTH,
1874 ty+TILESIZE-HIGHLIGHT_WIDTH,
1875 HIGHLIGHT_WIDTH, HIGHLIGHT_WIDTH, cl);
1876}
1877
1878static void draw_piecepart(drawing *dr, game_drawstate *ds,
1879 int tx, int ty, unsigned long val,
1880 int cl, int cc, int ch)
1881{
1882 int x[6], y[6];
1883
1884 /*
1885 * Drawing the blocks is hellishly fiddly. The blocks don't
1886 * stretch to the full size of the tile; there's a border
1887 * around them of size BORDER_WIDTH. Then they have bevelled
1888 * borders of size HIGHLIGHT_WIDTH, and also rounded corners.
1889 *
1890 * I tried for some time to find a clean and clever way to
1891 * figure out what needed drawing from the corner and border
1892 * flags, but in the end the cleanest way I could find was the
1893 * following. We divide the grid square into 25 parts by
1894 * ruling four horizontal and four vertical lines across it;
1895 * those lines are at BORDER_WIDTH and BORDER_WIDTH +
1896 * HIGHLIGHT_WIDTH from the top, from the bottom, from the
1897 * left and from the right. Then we carefully consider each of
1898 * the resulting 25 sections of square, and decide separately
1899 * what needs to go in it based on the flags. In complicated
1900 * cases there can be up to five possibilities affecting any
1901 * given section (no corner or border flags, just the corner
1902 * flag, one border flag, the other border flag, both border
1903 * flags). So there's a lot of very fiddly logic here and all
1904 * I could really think to do was give it my best shot and
1905 * then test it and correct all the typos. Not fun to write,
1906 * and I'm sure it isn't fun to read either, but it seems to
1907 * work.
1908 */
1909
1910 x[0] = tx;
1911 x[1] = x[0] + BORDER_WIDTH;
1912 x[2] = x[1] + HIGHLIGHT_WIDTH;
1913 x[5] = tx + TILESIZE;
1914 x[4] = x[5] - BORDER_WIDTH;
1915 x[3] = x[4] - HIGHLIGHT_WIDTH;
1916
1917 y[0] = ty;
1918 y[1] = y[0] + BORDER_WIDTH;
1919 y[2] = y[1] + HIGHLIGHT_WIDTH;
1920 y[5] = ty + TILESIZE;
1921 y[4] = y[5] - BORDER_WIDTH;
1922 y[3] = y[4] - HIGHLIGHT_WIDTH;
1923
1924#define RECT(p,q) x[p], y[q], x[(p)+1]-x[p], y[(q)+1]-y[q]
1925
1926 maybe_rect(dr, RECT(0,0),
1927 (val & (PIECE_TLCORNER | PIECE_TBORDER |
1928 PIECE_LBORDER)) ? -1 : cc, -1);
1929 maybe_rect(dr, RECT(1,0),
1930 (val & PIECE_TLCORNER) ? ch : (val & PIECE_TBORDER) ? -1 :
1931 (val & PIECE_LBORDER) ? ch : cc, -1);
1932 maybe_rect(dr, RECT(2,0),
1933 (val & PIECE_TBORDER) ? -1 : cc, -1);
1934 maybe_rect(dr, RECT(3,0),
1935 (val & PIECE_TRCORNER) ? cl : (val & PIECE_TBORDER) ? -1 :
1936 (val & PIECE_RBORDER) ? cl : cc, -1);
1937 maybe_rect(dr, RECT(4,0),
1938 (val & (PIECE_TRCORNER | PIECE_TBORDER |
1939 PIECE_RBORDER)) ? -1 : cc, -1);
1940 maybe_rect(dr, RECT(0,1),
1941 (val & PIECE_TLCORNER) ? ch : (val & PIECE_LBORDER) ? -1 :
1942 (val & PIECE_TBORDER) ? ch : cc, -1);
1943 maybe_rect(dr, RECT(1,1),
1944 (val & PIECE_TLCORNER) ? cc : -1, -1);
1945 maybe_rect(dr, RECT(1,1),
1946 (val & PIECE_TLCORNER) ? ch | TYPE_TLCIRC :
1947 !((PIECE_TBORDER | PIECE_LBORDER) &~ val) ? ch | TYPE_BRCIRC :
1948 (val & (PIECE_TBORDER | PIECE_LBORDER)) ? ch : cc, -1);
1949 maybe_rect(dr, RECT(2,1),
1950 (val & PIECE_TBORDER) ? ch : cc, -1);
1951 maybe_rect(dr, RECT(3,1),
1952 (val & PIECE_TRCORNER) ? cc : -1, -1);
1953 maybe_rect(dr, RECT(3,1),
1954 (val & (PIECE_TBORDER | PIECE_RBORDER)) == PIECE_TBORDER ? ch :
1955 (val & (PIECE_TBORDER | PIECE_RBORDER)) == PIECE_RBORDER ? cl :
1956 !((PIECE_TBORDER|PIECE_RBORDER) &~ val) ? cl | TYPE_BLCIRC :
1957 (val & PIECE_TRCORNER) ? cl | TYPE_TRCIRC :
1958 cc, ch);
1959 maybe_rect(dr, RECT(4,1),
1960 (val & PIECE_TRCORNER) ? ch : (val & PIECE_RBORDER) ? -1 :
1961 (val & PIECE_TBORDER) ? ch : cc, -1);
1962 maybe_rect(dr, RECT(0,2),
1963 (val & PIECE_LBORDER) ? -1 : cc, -1);
1964 maybe_rect(dr, RECT(1,2),
1965 (val & PIECE_LBORDER) ? ch : cc, -1);
1966 maybe_rect(dr, RECT(2,2),
1967 cc, -1);
1968 maybe_rect(dr, RECT(3,2),
1969 (val & PIECE_RBORDER) ? cl : cc, -1);
1970 maybe_rect(dr, RECT(4,2),
1971 (val & PIECE_RBORDER) ? -1 : cc, -1);
1972 maybe_rect(dr, RECT(0,3),
1973 (val & PIECE_BLCORNER) ? cl : (val & PIECE_LBORDER) ? -1 :
1974 (val & PIECE_BBORDER) ? cl : cc, -1);
1975 maybe_rect(dr, RECT(1,3),
1976 (val & PIECE_BLCORNER) ? cc : -1, -1);
1977 maybe_rect(dr, RECT(1,3),
1978 (val & (PIECE_BBORDER | PIECE_LBORDER)) == PIECE_BBORDER ? cl :
1979 (val & (PIECE_BBORDER | PIECE_LBORDER)) == PIECE_LBORDER ? ch :
1980 !((PIECE_BBORDER|PIECE_LBORDER) &~ val) ? ch | TYPE_TRCIRC :
1981 (val & PIECE_BLCORNER) ? ch | TYPE_BLCIRC :
1982 cc, cl);
1983 maybe_rect(dr, RECT(2,3),
1984 (val & PIECE_BBORDER) ? cl : cc, -1);
1985 maybe_rect(dr, RECT(3,3),
1986 (val & PIECE_BRCORNER) ? cc : -1, -1);
1987 maybe_rect(dr, RECT(3,3),
1988 (val & PIECE_BRCORNER) ? cl | TYPE_BRCIRC :
1989 !((PIECE_BBORDER | PIECE_RBORDER) &~ val) ? cl | TYPE_TLCIRC :
1990 (val & (PIECE_BBORDER | PIECE_RBORDER)) ? cl : cc, -1);
1991 maybe_rect(dr, RECT(4,3),
1992 (val & PIECE_BRCORNER) ? cl : (val & PIECE_RBORDER) ? -1 :
1993 (val & PIECE_BBORDER) ? cl : cc, -1);
1994 maybe_rect(dr, RECT(0,4),
1995 (val & (PIECE_BLCORNER | PIECE_BBORDER |
1996 PIECE_LBORDER)) ? -1 : cc, -1);
1997 maybe_rect(dr, RECT(1,4),
1998 (val & PIECE_BLCORNER) ? ch : (val & PIECE_BBORDER) ? -1 :
1999 (val & PIECE_LBORDER) ? ch : cc, -1);
2000 maybe_rect(dr, RECT(2,4),
2001 (val & PIECE_BBORDER) ? -1 : cc, -1);
2002 maybe_rect(dr, RECT(3,4),
2003 (val & PIECE_BRCORNER) ? cl : (val & PIECE_BBORDER) ? -1 :
2004 (val & PIECE_RBORDER) ? cl : cc, -1);
2005 maybe_rect(dr, RECT(4,4),
2006 (val & (PIECE_BRCORNER | PIECE_BBORDER |
2007 PIECE_RBORDER)) ? -1 : cc, -1);
2008
2009#undef RECT
2010}
2011
2012static void draw_tile(drawing *dr, game_drawstate *ds,
2013 int x, int y, unsigned long val)
2014{
2015 int tx = COORD(x), ty = COORD(y);
2016 int cc, ch, cl;
2017
2018 /*
2019 * Draw the tile background.
2020 */
2021 if (val & BG_TARGET)
2022 cc = COL_TARGET;
2023 else
2024 cc = COL_BACKGROUND;
2025 ch = cc+1;
2026 cl = cc+2;
2027 if (val & FLASH_LOW)
2028 cc = cl;
2029 else if (val & FLASH_HIGH)
2030 cc = ch;
2031
2032 draw_rect(dr, tx, ty, TILESIZE, TILESIZE, cc);
2033 if (val & BG_FORCEFIELD) {
2034 /*
2035 * Cattle-grid effect to indicate that nothing but the
2036 * main block can slide over this square.
2037 */
2038 int n = 3 * (TILESIZE / (3*HIGHLIGHT_WIDTH));
2039 int i;
2040
2041 for (i = 1; i < n; i += 3) {
2042 draw_rect(dr, tx,ty+(TILESIZE*i/n), TILESIZE,HIGHLIGHT_WIDTH, cl);
2043 draw_rect(dr, tx+(TILESIZE*i/n),ty, HIGHLIGHT_WIDTH,TILESIZE, cl);
2044 }
2045 }
2046
2047 /*
2048 * Draw the tile midground: a shadow of a block, for
2049 * displaying partial solutions.
2050 */
2051 if (val & FG_SHADOW) {
2052 draw_piecepart(dr, ds, tx, ty, (val >> FG_SHADOWSH) & PIECE_MASK,
2053 cl, cl, cl);
2054 }
2055
2056 /*
2057 * Draw the tile foreground, i.e. some section of a block or
2058 * wall.
2059 */
2060 if (val & FG_WALL) {
2061 cc = COL_BACKGROUND;
2062 ch = cc+1;
2063 cl = cc+2;
2064 if (val & FLASH_LOW)
2065 cc = cl;
2066 else if (val & FLASH_HIGH)
2067 cc = ch;
2068
2069 draw_wallpart(dr, ds, tx, ty, (val >> FG_MAINPIECESH) & PIECE_MASK,
2070 cl, cc, ch);
2071 } else if (val & (FG_MAIN | FG_NORMAL)) {
2072 if (val & FG_DRAGGING)
2073 cc = (val & FG_MAIN ? COL_MAIN_DRAGGING : COL_DRAGGING);
2074 else
2075 cc = (val & FG_MAIN ? COL_MAIN : COL_BACKGROUND);
2076 ch = cc+1;
2077 cl = cc+2;
2078
2079 if (val & FLASH_LOW)
2080 cc = cl;
2081 else if (val & (FLASH_HIGH | FG_SOLVEPIECE))
2082 cc = ch;
2083
2084 draw_piecepart(dr, ds, tx, ty, (val >> FG_MAINPIECESH) & PIECE_MASK,
2085 cl, cc, ch);
2086 }
2087
2088 draw_update(dr, tx, ty, TILESIZE, TILESIZE);
2089}
2090
2091static unsigned long find_piecepart(int w, int h, int *dsf, int x, int y)
2092{
2093 int i = y*w+x;
2094 int canon = dsf_canonify(dsf, i);
2095 unsigned long val = 0;
2096
2097 if (x == 0 || canon != dsf_canonify(dsf, i-1))
2098 val |= PIECE_LBORDER;
2099 if (y== 0 || canon != dsf_canonify(dsf, i-w))
2100 val |= PIECE_TBORDER;
2101 if (x == w-1 || canon != dsf_canonify(dsf, i+1))
2102 val |= PIECE_RBORDER;
2103 if (y == h-1 || canon != dsf_canonify(dsf, i+w))
2104 val |= PIECE_BBORDER;
2105 if (!(val & (PIECE_TBORDER | PIECE_LBORDER)) &&
2106 canon != dsf_canonify(dsf, i-1-w))
2107 val |= PIECE_TLCORNER;
2108 if (!(val & (PIECE_TBORDER | PIECE_RBORDER)) &&
2109 canon != dsf_canonify(dsf, i+1-w))
2110 val |= PIECE_TRCORNER;
2111 if (!(val & (PIECE_BBORDER | PIECE_LBORDER)) &&
2112 canon != dsf_canonify(dsf, i-1+w))
2113 val |= PIECE_BLCORNER;
2114 if (!(val & (PIECE_BBORDER | PIECE_RBORDER)) &&
2115 canon != dsf_canonify(dsf, i+1+w))
2116 val |= PIECE_BRCORNER;
2117 return val;
2118}
2119
2120static void game_redraw(drawing *dr, game_drawstate *ds,
2121 const game_state *oldstate, const game_state *state,
2122 int dir, const game_ui *ui,
2123 float animtime, float flashtime)
2124{
2125 int w = state->w, h = state->h, wh = w*h;
2126 unsigned char *board;
2127 int *dsf;
2128 int x, y, mainanchor, mainpos, dragpos, solvepos, solvesrc, solvedst;
2129
2130 if (!ds->started) {
2131 /*
2132 * The initial contents of the window are not guaranteed
2133 * and can vary with front ends. To be on the safe side,
2134 * all games should start by drawing a big
2135 * background-colour rectangle covering the whole window.
2136 */
2137 draw_rect(dr, 0, 0, 10*ds->tilesize, 10*ds->tilesize, COL_BACKGROUND);
2138 ds->started = TRUE;
2139 }
2140
2141 /*
2142 * Construct the board we'll be displaying (which may be
2143 * different from the one in state if ui describes a drag in
2144 * progress).
2145 */
2146 board = snewn(wh, unsigned char);
2147 memcpy(board, state->board, wh);
2148 if (ui->dragging) {
2149 int mpret = move_piece(w, h, state->board, board,
2150 state->imm->forcefield,
2151 ui->drag_anchor, ui->drag_currpos);
2152 assert(mpret);
2153 }
2154
2155 if (state->soln) {
2156 solvesrc = state->soln->moves[state->soln_index*2];
2157 solvedst = state->soln->moves[state->soln_index*2+1];
2158 if (solvesrc == state->lastmoved_pos)
2159 solvesrc = state->lastmoved;
2160 if (solvesrc == ui->drag_anchor)
2161 solvesrc = ui->drag_currpos;
2162 } else
2163 solvesrc = solvedst = -1;
2164
2165 /*
2166 * Build a dsf out of that board, so we can conveniently tell
2167 * which edges are connected and which aren't.
2168 */
2169 dsf = snew_dsf(wh);
2170 mainanchor = -1;
2171 for (y = 0; y < h; y++)
2172 for (x = 0; x < w; x++) {
2173 int i = y*w+x;
2174
2175 if (ISDIST(board[i]))
2176 dsf_merge(dsf, i, i - board[i]);
2177 if (board[i] == MAINANCHOR)
2178 mainanchor = i;
2179 if (board[i] == WALL) {
2180 if (x > 0 && board[i-1] == WALL)
2181 dsf_merge(dsf, i, i-1);
2182 if (y > 0 && board[i-w] == WALL)
2183 dsf_merge(dsf, i, i-w);
2184 }
2185 }
2186 assert(mainanchor >= 0);
2187 mainpos = dsf_canonify(dsf, mainanchor);
2188 dragpos = ui->drag_currpos > 0 ? dsf_canonify(dsf, ui->drag_currpos) : -1;
2189 solvepos = solvesrc >= 0 ? dsf_canonify(dsf, solvesrc) : -1;
2190
2191 /*
2192 * Now we can construct the data about what we want to draw.
2193 */
2194 for (y = 0; y < h; y++)
2195 for (x = 0; x < w; x++) {
2196 int i = y*w+x;
2197 int j;
2198 unsigned long val;
2199 int canon;
2200
2201 /*
2202 * See if this square is part of the target area.
2203 */
2204 j = i + mainanchor - (state->ty * w + state->tx);
2205 while (j >= 0 && j < wh && ISDIST(board[j]))
2206 j -= board[j];
2207 if (j == mainanchor)
2208 val = BG_TARGET;
2209 else
2210 val = BG_NORMAL;
2211
2212 if (state->imm->forcefield[i])
2213 val |= BG_FORCEFIELD;
2214
2215 if (flashtime > 0) {
2216 int flashtype = (int)(flashtime / FLASH_INTERVAL) & 1;
2217 val |= (flashtype ? FLASH_LOW : FLASH_HIGH);
2218 }
2219
2220 if (board[i] != EMPTY) {
2221 canon = dsf_canonify(dsf, i);
2222
2223 if (board[i] == WALL)
2224 val |= FG_WALL;
2225 else if (canon == mainpos)
2226 val |= FG_MAIN;
2227 else
2228 val |= FG_NORMAL;
2229 if (canon == dragpos)
2230 val |= FG_DRAGGING;
2231 if (canon == solvepos)
2232 val |= FG_SOLVEPIECE;
2233
2234 /*
2235 * Now look around to see if other squares
2236 * belonging to the same block are adjacent to us.
2237 */
2238 val |= find_piecepart(w, h, dsf, x, y) << FG_MAINPIECESH;
2239 }
2240
2241 /*
2242 * If we're in the middle of showing a solution,
2243 * display a shadow piece for the target of the
2244 * current move.
2245 */
2246 if (solvepos >= 0) {
2247 int si = i - solvedst + solvesrc;
2248 if (si >= 0 && si < wh && dsf_canonify(dsf, si) == solvepos) {
2249 val |= find_piecepart(w, h, dsf,
2250 si % w, si / w) << FG_SHADOWSH;
2251 val |= FG_SHADOW;
2252 }
2253 }
2254
2255 if (val != ds->grid[i]) {
2256 draw_tile(dr, ds, x, y, val);
2257 ds->grid[i] = val;
2258 }
2259 }
2260
2261 /*
2262 * Update the status bar.
2263 */
2264 {
2265 char statusbuf[256];
2266
2267 sprintf(statusbuf, "%sMoves: %d",
2268 (state->completed >= 0 ?
2269 (state->cheated ? "Auto-solved. " : "COMPLETED! ") :
2270 (state->cheated ? "Auto-solver used. " : "")),
2271 (state->completed >= 0 ? state->completed : state->movecount));
2272 if (state->minmoves >= 0)
2273 sprintf(statusbuf+strlen(statusbuf), " (min %d)",
2274 state->minmoves);
2275
2276 status_bar(dr, statusbuf);
2277 }
2278
2279 sfree(dsf);
2280 sfree(board);
2281}
2282
2283static float game_anim_length(const game_state *oldstate,
2284 const game_state *newstate, int dir, game_ui *ui)
2285{
2286 return 0.0F;
2287}
2288
2289static float game_flash_length(const game_state *oldstate,
2290 const game_state *newstate, int dir, game_ui *ui)
2291{
2292 if (oldstate->completed < 0 && newstate->completed >= 0)
2293 return FLASH_TIME;
2294
2295 return 0.0F;
2296}
2297
2298static int game_status(const game_state *state)
2299{
2300 return state->completed ? +1 : 0;
2301}
2302
2303static int game_timing_state(const game_state *state, game_ui *ui)
2304{
2305 return TRUE;
2306}
2307
2308static void game_print_size(const game_params *params, float *x, float *y)
2309{
2310}
2311
2312static void game_print(drawing *dr, const game_state *state, int tilesize)
2313{
2314}
2315
2316#ifdef COMBINED
2317#define thegame slide
2318#endif
2319
2320const struct game thegame = {
2321 "Slide", NULL, NULL,
2322 default_params,
2323 game_fetch_preset, NULL,
2324 decode_params,
2325 encode_params,
2326 free_params,
2327 dup_params,
2328 TRUE, game_configure, custom_params,
2329 validate_params,
2330 new_game_desc,
2331 validate_desc,
2332 new_game,
2333 dup_game,
2334 free_game,
2335 TRUE, solve_game,
2336 TRUE, game_can_format_as_text_now, game_text_format,
2337 new_ui,
2338 free_ui,
2339 encode_ui,
2340 decode_ui,
2341 game_changed_state,
2342 interpret_move,
2343 execute_move,
2344 PREFERRED_TILESIZE, game_compute_size, game_set_size,
2345 game_colours,
2346 game_new_drawstate,
2347 game_free_drawstate,
2348 game_redraw,
2349 game_anim_length,
2350 game_flash_length,
2351 game_status,
2352 FALSE, FALSE, game_print_size, game_print,
2353 TRUE, /* wants_statusbar */
2354 FALSE, game_timing_state,
2355 0, /* flags */
2356};
2357
2358#ifdef STANDALONE_SOLVER
2359
2360#include <stdarg.h>
2361
2362int main(int argc, char **argv)
2363{
2364 game_params *p;
2365 game_state *s;
2366 char *id = NULL, *desc, *err;
2367 int count = FALSE;
2368 int ret;
2369 int *moves;
2370
2371 while (--argc > 0) {
2372 char *p = *++argv;
2373 /*
2374 if (!strcmp(p, "-v")) {
2375 verbose = TRUE;
2376 } else
2377 */
2378 if (!strcmp(p, "-c")) {
2379 count = TRUE;
2380 } else if (*p == '-') {
2381 fprintf(stderr, "%s: unrecognised option `%s'\n", argv[0], p);
2382 return 1;
2383 } else {
2384 id = p;
2385 }
2386 }
2387
2388 if (!id) {
2389 fprintf(stderr, "usage: %s [-c | -v] <game_id>\n", argv[0]);
2390 return 1;
2391 }
2392
2393 desc = strchr(id, ':');
2394 if (!desc) {
2395 fprintf(stderr, "%s: game id expects a colon in it\n", argv[0]);
2396 return 1;
2397 }
2398 *desc++ = '\0';
2399
2400 p = default_params();
2401 decode_params(p, id);
2402 err = validate_desc(p, desc);
2403 if (err) {
2404 fprintf(stderr, "%s: %s\n", argv[0], err);
2405 return 1;
2406 }
2407 s = new_game(NULL, p, desc);
2408
2409 ret = solve_board(s->w, s->h, s->board, s->imm->forcefield,
2410 s->tx, s->ty, -1, &moves);
2411 if (ret < 0) {
2412 printf("No solution found\n");
2413 } else {
2414 int index = 0;
2415 if (count) {
2416 printf("%d moves required\n", ret);
2417 return 0;
2418 }
2419 while (1) {
2420 int moveret;
2421 char *text = board_text_format(s->w, s->h, s->board,
2422 s->imm->forcefield);
2423 game_state *s2;
2424
2425 printf("position %d:\n%s", index, text);
2426
2427 if (index >= ret)
2428 break;
2429
2430 s2 = dup_game(s);
2431 moveret = move_piece(s->w, s->h, s->board,
2432 s2->board, s->imm->forcefield,
2433 moves[index*2], moves[index*2+1]);
2434 assert(moveret);
2435
2436 free_game(s);
2437 s = s2;
2438 index++;
2439 }
2440 }
2441
2442 return 0;
2443}
2444
2445#endif
generated by cgit v1.2.3 (git 2.39.1) at 2024-09-21 08:47:16 +0000