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