2 * galaxies.c: implementation of 'Tentai Show' from Nikoli,
3 * also sometimes called 'Spiral Galaxies'.
7 * Grid is stored as size (2n-1), holding edges as well as spaces
8 * (and thus vertices too, at edge intersections).
10 * Any dot will thus be positioned at one of our grid points,
11 * which saves any faffing with half-of-a-square stuff.
13 * Edges have on/off state; obviously the actual edges of the
14 * board are fixed to on, and everything else starts as off.
18 * Think about how to display remote groups of tiles?
24 * Nikoli's example [web site has wrong highlighting]
25 * (at http://www.nikoli.co.jp/en/puzzles/astronomical_show/):
28 * The 'spiral galaxies puzzles are NP-complete' paper
29 * (at http://www.stetson.edu/~efriedma/papers/spiral.pdf):
30 * 7x7:chpgdqqqoezdddki
32 * Puzzle competition pdf examples
33 * (at http://www.puzzleratings.org/Yurekli2006puz.pdf):
34 * 6x6:EDbaMucCohbrecEi
35 * 10x10:beFbufEEzowDlxldibMHezBQzCdcFzjlci
36 * 13x13:dCemIHFFkJajjgDfdbdBzdzEgjccoPOcztHjBczLDjczqktJjmpreivvNcggFi
52 int solver_show_working
;
53 #define solvep(x) do { if (solver_show_working) { printf x; } } while(0)
56 #ifdef STANDALONE_PICTURE_GENERATOR
58 * Dirty hack to enable the generator to construct a game ID which
59 * solves to a specified black-and-white bitmap. We define a global
60 * variable here which gives the desired colour of each square, and
61 * we arrange that the grid generator never merges squares of
64 * The bitmap as stored here is a simple int array (at these sizes
65 * it isn't worth doing fiddly bit-packing). picture[y*w+x] is 1
66 * iff the pixel at (x,y) is intended to be black.
68 * (It might be nice to be able to specify some pixels as
69 * don't-care, to give the generator more leeway. But that might be
89 A(UNREASONABLE,Unreasonable,u)
91 #define ENUM(upper,title,lower) DIFF_ ## upper,
92 #define TITLE(upper,title,lower) #title,
93 #define ENCODE(upper,title,lower) #lower
94 #define CONFIG(upper,title,lower) ":" #title
96 DIFF_IMPOSSIBLE
, DIFF_AMBIGUOUS
, DIFF_UNFINISHED
, DIFF_MAX
};
97 static char const *const galaxies_diffnames
[] = {
98 DIFFLIST(TITLE
) "Impossible", "Ambiguous", "Unfinished" };
99 static char const galaxies_diffchars
[] = DIFFLIST(ENCODE
);
100 #define DIFFCONFIG DIFFLIST(CONFIG)
103 /* X and Y is the area of the board as seen by
104 * the user, not the (2n+1) area the game uses. */
108 enum { s_tile
, s_edge
, s_vertex
};
110 #define F_DOT 1 /* there's a dot here */
111 #define F_EDGE_SET 2 /* the edge is set */
112 #define F_TILE_ASSOC 4 /* this tile is associated with a dot. */
113 #define F_DOT_BLACK 8 /* (ui only) dot is black. */
114 #define F_MARK 16 /* scratch flag */
115 #define F_REACHABLE 32
117 #define F_MULTIPLE 128
118 #define F_DOT_HOLD 256
121 typedef struct space
{
122 int x
, y
; /* its position */
125 int dotx
, doty
; /* if flags & F_TILE_ASSOC */
126 int nassoc
; /* if flags & F_DOT */
129 #define INGRID(s,x,y) ((x) >= 0 && (y) >= 0 && \
130 (x) < (state)->sx && (y) < (state)->sy)
131 #define INUI(s,x,y) ((x) > 0 && (y) > 0 && \
132 (x) < ((state)->sx-1) && (y) < ((state)->sy-1))
134 #define GRID(s,g,x,y) ((s)->g[((y)*(s)->sx)+(x)])
135 #define SPACE(s,x,y) GRID(s,grid,x,y)
138 int w
, h
; /* size from params */
139 int sx
, sy
; /* allocated size, (2x-1)*(2y-1) */
141 int completed
, used_solve
;
145 midend
*me
; /* to call supersede_game_desc */
146 int cdiff
; /* difficulty of current puzzle (for status bar),
150 /* ----------------------------------------------------------
151 * Game parameters and presets
154 /* make up some sensible default sizes */
156 #define DEFAULT_PRESET 0
158 static const game_params galaxies_presets
[] = {
159 { 7, 7, DIFF_NORMAL
},
160 { 7, 7, DIFF_UNREASONABLE
},
161 { 10, 10, DIFF_NORMAL
},
162 { 15, 15, DIFF_NORMAL
},
165 static int game_fetch_preset(int i
, char **name
, game_params
**params
)
170 if (i
< 0 || i
>= lenof(galaxies_presets
))
173 ret
= snew(game_params
);
174 *ret
= galaxies_presets
[i
]; /* structure copy */
176 sprintf(buf
, "%dx%d %s", ret
->w
, ret
->h
,
177 galaxies_diffnames
[ret
->diff
]);
179 if (name
) *name
= dupstr(buf
);
184 static game_params
*default_params(void)
187 game_fetch_preset(DEFAULT_PRESET
, NULL
, &ret
);
191 static void free_params(game_params
*params
)
196 static game_params
*dup_params(game_params
*params
)
198 game_params
*ret
= snew(game_params
);
199 *ret
= *params
; /* structure copy */
203 static void decode_params(game_params
*params
, char const *string
)
205 params
->h
= params
->w
= atoi(string
);
206 params
->diff
= DIFF_NORMAL
;
207 while (*string
&& isdigit((unsigned char)*string
)) string
++;
208 if (*string
== 'x') {
210 params
->h
= atoi(string
);
211 while (*string
&& isdigit((unsigned char)*string
)) string
++;
213 if (*string
== 'd') {
216 for (i
= 0; i
<= DIFF_UNREASONABLE
; i
++)
217 if (*string
== galaxies_diffchars
[i
])
219 if (*string
) string
++;
223 static char *encode_params(game_params
*params
, int full
)
226 sprintf(str
, "%dx%d", params
->w
, params
->h
);
228 sprintf(str
+ strlen(str
), "d%c", galaxies_diffchars
[params
->diff
]);
232 static config_item
*game_configure(game_params
*params
)
237 ret
= snewn(4, config_item
);
239 ret
[0].name
= "Width";
240 ret
[0].type
= C_STRING
;
241 sprintf(buf
, "%d", params
->w
);
242 ret
[0].sval
= dupstr(buf
);
245 ret
[1].name
= "Height";
246 ret
[1].type
= C_STRING
;
247 sprintf(buf
, "%d", params
->h
);
248 ret
[1].sval
= dupstr(buf
);
251 ret
[2].name
= "Difficulty";
252 ret
[2].type
= C_CHOICES
;
253 ret
[2].sval
= DIFFCONFIG
;
254 ret
[2].ival
= params
->diff
;
264 static game_params
*custom_params(config_item
*cfg
)
266 game_params
*ret
= snew(game_params
);
268 ret
->w
= atoi(cfg
[0].sval
);
269 ret
->h
= atoi(cfg
[1].sval
);
270 ret
->diff
= cfg
[2].ival
;
275 static char *validate_params(game_params
*params
, int full
)
277 if (params
->w
< 3 || params
->h
< 3)
278 return "Width and height must both be at least 3";
280 * This shouldn't be able to happen at all, since decode_params
281 * and custom_params will never generate anything that isn't
284 assert(params
->diff
<= DIFF_UNREASONABLE
);
289 /* ----------------------------------------------------------
290 * Game utility functions.
293 static void add_dot(space
*space
) {
294 assert(!(space
->flags
& F_DOT
));
295 space
->flags
|= F_DOT
;
299 static void remove_dot(space
*space
) {
300 assert(space
->flags
& F_DOT
);
301 space
->flags
&= ~F_DOT
;
304 static void remove_assoc(game_state
*state
, space
*tile
) {
305 if (tile
->flags
& F_TILE_ASSOC
) {
306 SPACE(state
, tile
->dotx
, tile
->doty
).nassoc
--;
307 tile
->flags
&= ~F_TILE_ASSOC
;
313 static void add_assoc(game_state
*state
, space
*tile
, space
*dot
) {
314 remove_assoc(state
, tile
);
316 #ifdef STANDALONE_PICTURE_GENERATOR
318 assert(!picture
[(tile
->y
/2) * state
->w
+ (tile
->x
/2)] ==
319 !(dot
->flags
& F_DOT_BLACK
));
321 tile
->flags
|= F_TILE_ASSOC
;
325 /*debug(("add_assoc sp %d %d --> dot %d,%d, new nassoc %d.\n",
326 tile->x, tile->y, dot->x, dot->y, dot->nassoc));*/
329 static struct space
*sp2dot(game_state
*state
, int x
, int y
)
331 struct space
*sp
= &SPACE(state
, x
, y
);
332 if (!(sp
->flags
& F_TILE_ASSOC
)) return NULL
;
333 return &SPACE(state
, sp
->dotx
, sp
->doty
);
336 #define IS_VERTICAL_EDGE(x) ((x % 2) == 0)
338 static char *game_text_format(game_state
*state
)
340 int maxlen
= (state
->sx
+1)*state
->sy
, x
, y
;
344 ret
= snewn(maxlen
+1, char);
347 for (y
= 0; y
< state
->sy
; y
++) {
348 for (x
= 0; x
< state
->sx
; x
++) {
349 sp
= &SPACE(state
, x
, y
);
350 if (sp
->flags
& F_DOT
)
353 else if (sp
->flags
& (F_REACHABLE
|F_MULTIPLE
|F_MARK
))
354 *p
++ = (sp
->flags
& F_MULTIPLE
) ?
'M' :
355 (sp
->flags
& F_REACHABLE
) ?
'R' : 'X';
360 if (sp
->flags
& F_TILE_ASSOC
) {
361 space
*dot
= sp2dot(state
, sp
->x
, sp
->y
);
362 if (dot
->flags
& F_DOT
)
363 *p
++ = (dot
->flags
& F_DOT_BLACK
) ?
'B' : 'W';
365 *p
++ = '?'; /* association with not-a-dot. */
375 if (sp
->flags
& F_EDGE_SET
)
376 *p
++ = (IS_VERTICAL_EDGE(x
)) ?
'|' : '-';
382 assert(!"shouldn't get here!");
389 assert(p
- ret
== maxlen
);
395 static void dbg_state(game_state
*state
)
398 char *temp
= game_text_format(state
);
399 debug(("%s\n", temp
));
404 /* Space-enumeration callbacks should all return 1 for 'progress made',
405 * -1 for 'impossible', and 0 otherwise. */
406 typedef int (*space_cb
)(game_state
*state
, space
*sp
, void *ctx
);
408 #define IMPOSSIBLE_QUITS 1
410 static int foreach_sub(game_state
*state
, space_cb cb
, unsigned int f
,
411 void *ctx
, int startx
, int starty
)
413 int x
, y
, progress
= 0, impossible
= 0, ret
;
416 for (y
= starty
; y
< state
->sy
; y
+= 2) {
417 sp
= &SPACE(state
, startx
, y
);
418 for (x
= startx
; x
< state
->sx
; x
+= 2) {
419 ret
= cb(state
, sp
, ctx
);
421 if (f
& IMPOSSIBLE_QUITS
) return -1;
423 } else if (ret
== 1) {
429 return impossible ?
-1 : progress
;
432 static int foreach_tile(game_state
*state
, space_cb cb
, unsigned int f
,
435 return foreach_sub(state
, cb
, f
, ctx
, 1, 1);
438 static int foreach_edge(game_state
*state
, space_cb cb
, unsigned int f
,
443 ret1
= foreach_sub(state
, cb
, f
, ctx
, 0, 1);
444 ret2
= foreach_sub(state
, cb
, f
, ctx
, 1, 0);
446 if (ret1
== -1 || ret2
== -1) return -1;
447 return (ret1
|| ret2
) ?
1 : 0;
451 static int foreach_vertex(game_state
*state
, space_cb cb
, unsigned int f
,
454 return foreach_sub(state
, cb
, f
, ctx
, 0, 0);
459 static int is_same_assoc(game_state
*state
,
460 int x1
, int y1
, int x2
, int y2
)
462 struct space
*s1
, *s2
;
464 if (!INGRID(state
, x1
, y1
) || !INGRID(state
, x2
, y2
))
467 s1
= &SPACE(state
, x1
, y1
);
468 s2
= &SPACE(state
, x2
, y2
);
469 assert(s1
->type
== s_tile
&& s2
->type
== s_tile
);
470 if ((s1
->flags
& F_TILE_ASSOC
) && (s2
->flags
& F_TILE_ASSOC
) &&
471 s1
->dotx
== s2
->dotx
&& s1
->doty
== s2
->doty
)
473 return 0; /* 0 if not same or not both associated. */
478 static int edges_into_vertex(game_state
*state
,
481 int dx
, dy
, nx
, ny
, count
= 0;
483 assert(SPACE(state
, x
, y
).type
== s_vertex
);
484 for (dx
= -1; dx
<= 1; dx
++) {
485 for (dy
= -1; dy
<= 1; dy
++) {
486 if (dx
!= 0 && dy
!= 0) continue;
487 if (dx
== 0 && dy
== 0) continue;
489 nx
= x
+dx
; ny
= y
+dy
;
490 if (!INGRID(state
, nx
, ny
)) continue;
491 assert(SPACE(state
, nx
, ny
).type
== s_edge
);
492 if (SPACE(state
, nx
, ny
).flags
& F_EDGE_SET
)
500 static struct space
*space_opposite_dot(struct game_state
*state
,
501 struct space
*sp
, struct space
*dot
)
510 if (!INGRID(state
, tx
, ty
)) return NULL
;
512 sp2
= &SPACE(state
, tx
, ty
);
513 assert(sp2
->type
== sp
->type
);
517 static struct space
*tile_opposite(struct game_state
*state
, struct space
*sp
)
521 assert(sp
->flags
& F_TILE_ASSOC
);
522 dot
= &SPACE(state
, sp
->dotx
, sp
->doty
);
523 return space_opposite_dot(state
, sp
, dot
);
526 static int dotfortile(game_state
*state
, space
*tile
, space
*dot
)
528 space
*tile_opp
= space_opposite_dot(state
, tile
, dot
);
530 if (!tile_opp
) return 0; /* opposite would be off grid */
531 if (tile_opp
->flags
& F_TILE_ASSOC
&&
532 (tile_opp
->dotx
!= dot
->x
|| tile_opp
->doty
!= dot
->y
))
533 return 0; /* opposite already associated with diff. dot */
537 static void adjacencies(struct game_state
*state
, struct space
*sp
,
538 struct space
**a1s
, struct space
**a2s
)
540 int dxs
[4] = {-1, 1, 0, 0}, dys
[4] = {0, 0, -1, 1};
543 /* this function needs optimising. */
545 for (n
= 0; n
< 4; n
++) {
549 if (INGRID(state
, x
, y
)) {
550 a1s
[n
] = &SPACE(state
, x
, y
);
552 x
+= dxs
[n
]; y
+= dys
[n
];
554 if (INGRID(state
, x
, y
))
555 a2s
[n
] = &SPACE(state
, x
, y
);
559 a1s
[n
] = a2s
[n
] = NULL
;
564 static int outline_tile_fordot(game_state
*state
, space
*tile
, int mark
)
566 struct space
*tadj
[4], *eadj
[4];
567 int i
, didsth
= 0, edge
, same
;
569 assert(tile
->type
== s_tile
);
570 adjacencies(state
, tile
, eadj
, tadj
);
571 for (i
= 0; i
< 4; i
++) {
572 if (!eadj
[i
]) continue;
574 edge
= (eadj
[i
]->flags
& F_EDGE_SET
) ?
1 : 0;
576 if (!(tile
->flags
& F_TILE_ASSOC
))
577 same
= (tadj
[i
]->flags
& F_TILE_ASSOC
) ?
0 : 1;
579 same
= ((tadj
[i
]->flags
& F_TILE_ASSOC
) &&
580 tile
->dotx
== tadj
[i
]->dotx
&&
581 tile
->doty
== tadj
[i
]->doty
) ?
1 : 0;
585 if (!edge
&& !same
) {
586 if (mark
) eadj
[i
]->flags
|= F_EDGE_SET
;
588 } else if (edge
&& same
) {
589 if (mark
) eadj
[i
]->flags
&= ~F_EDGE_SET
;
596 static void tiles_from_edge(struct game_state
*state
,
597 struct space
*sp
, struct space
**ts
)
601 if (IS_VERTICAL_EDGE(sp
->x
)) {
602 xs
[0] = sp
->x
-1; ys
[0] = sp
->y
;
603 xs
[1] = sp
->x
+1; ys
[1] = sp
->y
;
605 xs
[0] = sp
->x
; ys
[0] = sp
->y
-1;
606 xs
[1] = sp
->x
; ys
[1] = sp
->y
+1;
608 ts
[0] = INGRID(state
, xs
[0], ys
[0]) ?
&SPACE(state
, xs
[0], ys
[0]) : NULL
;
609 ts
[1] = INGRID(state
, xs
[1], ys
[1]) ?
&SPACE(state
, xs
[1], ys
[1]) : NULL
;
612 /* Returns a move string for use by 'solve', including the initial
613 * 'S' if issolve is true. */
614 static char *diff_game(game_state
*src
, game_state
*dest
, int issolve
)
616 int movelen
= 0, movesize
= 256, x
, y
, len
;
617 char *move
= snewn(movesize
, char), buf
[80], *sep
= "";
618 char achar
= issolve ?
'a' : 'A';
621 assert(src
->sx
== dest
->sx
&& src
->sy
== dest
->sy
);
624 move
[movelen
++] = 'S';
627 move
[movelen
] = '\0';
628 for (x
= 0; x
< src
->sx
; x
++) {
629 for (y
= 0; y
< src
->sy
; y
++) {
630 sps
= &SPACE(src
, x
, y
);
631 spd
= &SPACE(dest
, x
, y
);
633 assert(sps
->type
== spd
->type
);
636 if (sps
->type
== s_tile
) {
637 if ((sps
->flags
& F_TILE_ASSOC
) &&
638 (spd
->flags
& F_TILE_ASSOC
)) {
639 if (sps
->dotx
!= spd
->dotx
||
640 sps
->doty
!= spd
->doty
)
641 /* Both associated; change association, if different */
642 len
= sprintf(buf
, "%s%c%d,%d,%d,%d", sep
,
643 (int)achar
, x
, y
, spd
->dotx
, spd
->doty
);
644 } else if (sps
->flags
& F_TILE_ASSOC
)
645 /* Only src associated; remove. */
646 len
= sprintf(buf
, "%sU%d,%d", sep
, x
, y
);
647 else if (spd
->flags
& F_TILE_ASSOC
)
648 /* Only dest associated; add. */
649 len
= sprintf(buf
, "%s%c%d,%d,%d,%d", sep
,
650 (int)achar
, x
, y
, spd
->dotx
, spd
->doty
);
651 } else if (sps
->type
== s_edge
) {
652 if ((sps
->flags
& F_EDGE_SET
) != (spd
->flags
& F_EDGE_SET
))
653 /* edge flags are different; flip them. */
654 len
= sprintf(buf
, "%sE%d,%d", sep
, x
, y
);
657 if (movelen
+ len
>= movesize
) {
658 movesize
= movelen
+ len
+ 256;
659 move
= sresize(move
, movesize
, char);
661 strcpy(move
+ movelen
, buf
);
667 debug(("diff_game src then dest:\n"));
670 debug(("diff string %s\n", move
));
674 /* Returns 1 if a dot here would not be too close to any other dots
675 * (and would avoid other game furniture). */
676 static int dot_is_possible(game_state
*state
, space
*sp
, int allow_assoc
)
678 int bx
= 0, by
= 0, dx
, dy
;
680 #ifdef STANDALONE_PICTURE_GENERATOR
688 if (IS_VERTICAL_EDGE(sp
->x
)) {
698 for (dx
= -bx
; dx
<= bx
; dx
++) {
699 for (dy
= -by
; dy
<= by
; dy
++) {
700 if (!INGRID(state
, sp
->x
+dx
, sp
->y
+dy
)) continue;
702 adj
= &SPACE(state
, sp
->x
+dx
, sp
->y
+dy
);
704 #ifdef STANDALONE_PICTURE_GENERATOR
706 * Check that all the squares we're looking at have the
710 if (adj
->type
== s_tile
) {
711 int c
= picture
[(adj
->y
/ 2) * state
->w
+ (adj
->x
/ 2)];
715 return 0; /* colour mismatch */
720 if (!allow_assoc
&& (adj
->flags
& F_TILE_ASSOC
))
723 if (dx
!= 0 || dy
!= 0) {
724 /* Other than our own square, no dots nearby. */
725 if (adj
->flags
& (F_DOT
))
729 /* We don't want edges within our rectangle
730 * (but don't care about edges on the edge) */
731 if (abs(dx
) < bx
&& abs(dy
) < by
&&
732 adj
->flags
& F_EDGE_SET
)
739 /* ----------------------------------------------------------
740 * Game generation, structure creation, and descriptions.
743 static game_state
*blank_game(int w
, int h
)
745 game_state
*state
= snew(game_state
);
753 state
->grid
= snewn(state
->sx
* state
->sy
, struct space
);
754 state
->completed
= state
->used_solve
= 0;
756 for (x
= 0; x
< state
->sx
; x
++) {
757 for (y
= 0; y
< state
->sy
; y
++) {
758 struct space
*sp
= &SPACE(state
, x
, y
);
759 memset(sp
, 0, sizeof(struct space
));
762 if ((x
% 2) == 0 && (y
% 2) == 0)
764 else if ((x
% 2) == 0 || (y
% 2) == 0) {
766 if (x
== 0 || y
== 0 || x
== state
->sx
-1 || y
== state
->sy
-1)
767 sp
->flags
|= F_EDGE_SET
;
776 state
->me
= NULL
; /* filled in by new_game. */
782 static void game_update_dots(game_state
*state
)
784 int i
, n
, sz
= state
->sx
* state
->sy
;
786 if (state
->dots
) sfree(state
->dots
);
789 for (i
= 0; i
< sz
; i
++) {
790 if (state
->grid
[i
].flags
& F_DOT
) state
->ndots
++;
792 state
->dots
= snewn(state
->ndots
, space
*);
794 for (i
= 0; i
< sz
; i
++) {
795 if (state
->grid
[i
].flags
& F_DOT
)
796 state
->dots
[n
++] = &state
->grid
[i
];
800 static void clear_game(game_state
*state
, int cleardots
)
804 /* don't erase edge flags around outline! */
805 for (x
= 1; x
< state
->sx
-1; x
++) {
806 for (y
= 1; y
< state
->sy
-1; y
++) {
808 SPACE(state
, x
, y
).flags
= 0;
810 SPACE(state
, x
, y
).flags
&= (F_DOT
|F_DOT_BLACK
);
813 if (cleardots
) game_update_dots(state
);
816 static game_state
*dup_game(game_state
*state
)
818 game_state
*ret
= blank_game(state
->w
, state
->h
);
820 ret
->completed
= state
->completed
;
821 ret
->used_solve
= state
->used_solve
;
823 memcpy(ret
->grid
, state
->grid
,
824 ret
->sx
*ret
->sy
*sizeof(struct space
));
826 game_update_dots(ret
);
829 ret
->cdiff
= state
->cdiff
;
834 static void free_game(game_state
*state
)
836 if (state
->dots
) sfree(state
->dots
);
841 /* Game description is a sequence of letters representing the number
842 * of spaces (a = 0, y = 24) before the next dot; a-y for a white dot,
843 * and A-Y for a black dot. 'z' is 25 spaces (and no dot).
845 * I know it's a bitch to generate by hand, so we provide
849 static char *encode_game(game_state
*state
)
855 area
= (state
->sx
-2) * (state
->sy
-2);
857 desc
= snewn(area
, char);
860 for (y
= 1; y
< state
->sy
-1; y
++) {
861 for (x
= 1; x
< state
->sx
-1; x
++) {
862 f
= SPACE(state
, x
, y
).flags
;
864 /* a/A is 0 spaces between, b/B is 1 space, ...
865 * y/Y is 24 spaces, za/zA is 25 spaces, ...
866 * It's easier to count from 0 because we then
867 * don't have to special-case the top left-hand corner
868 * (which could be a dot with 0 spaces before it). */
876 *p
++ = ((f
& F_DOT_BLACK
) ?
'A' : 'a') + run
;
881 assert(p
- desc
< area
);
883 desc
= sresize(desc
, p
- desc
, char);
890 space
*olddot
, *newdot
;
893 enum { MD_CHECK
, MD_MOVE
};
895 static int movedot_cb(game_state
*state
, space
*tile
, void *vctx
)
897 struct movedot
*md
= (struct movedot
*)vctx
;
898 space
*newopp
= NULL
;
900 assert(tile
->type
== s_tile
);
901 assert(md
->olddot
&& md
->newdot
);
903 if (!(tile
->flags
& F_TILE_ASSOC
)) return 0;
904 if (tile
->dotx
!= md
->olddot
->x
|| tile
->doty
!= md
->olddot
->y
)
907 newopp
= space_opposite_dot(state
, tile
, md
->newdot
);
911 /* If the tile is associated with the old dot, check its
912 * opposite wrt the _new_ dot is empty or same assoc. */
913 if (!newopp
) return -1; /* no new opposite */
914 if (newopp
->flags
& F_TILE_ASSOC
) {
915 if (newopp
->dotx
!= md
->olddot
->x
||
916 newopp
->doty
!= md
->olddot
->y
)
917 return -1; /* associated, but wrong dot. */
919 #ifdef STANDALONE_PICTURE_GENERATOR
922 * Reject if either tile and the dot don't match in colour.
924 if (!(picture
[(tile
->y
/2) * state
->w
+ (tile
->x
/2)]) ^
925 !(md
->newdot
->flags
& F_DOT_BLACK
))
927 if (!(picture
[(newopp
->y
/2) * state
->w
+ (newopp
->x
/2)]) ^
928 !(md
->newdot
->flags
& F_DOT_BLACK
))
935 /* Move dot associations: anything that was associated
936 * with the old dot, and its opposite wrt the new dot,
937 * become associated with the new dot. */
939 debug(("Associating %d,%d and %d,%d with new dot %d,%d.\n",
940 tile
->x
, tile
->y
, newopp
->x
, newopp
->y
,
941 md
->newdot
->x
, md
->newdot
->y
));
942 add_assoc(state
, tile
, md
->newdot
);
943 add_assoc(state
, newopp
, md
->newdot
);
944 return 1; /* we did something! */
949 /* For the given dot, first see if we could expand it into all the given
950 * extra spaces (by checking for empty spaces on the far side), and then
951 * see if we can move the dot to shift the CoG to include the new spaces.
953 static int dot_expand_or_move(game_state
*state
, space
*dot
,
954 space
**toadd
, int nadd
)
957 int i
, ret
, nnew
, cx
, cy
;
960 debug(("dot_expand_or_move: %d tiles for dot %d,%d\n",
961 nadd
, dot
->x
, dot
->y
));
962 for (i
= 0; i
< nadd
; i
++)
963 debug(("dot_expand_or_move: dot %d,%d\n",
964 toadd
[i
]->x
, toadd
[i
]->y
));
965 assert(dot
->flags
& F_DOT
);
967 #ifdef STANDALONE_PICTURE_GENERATOR
970 * Reject the expansion totally if any of the new tiles are
973 for (i
= 0; i
< nadd
; i
++) {
974 if (!(picture
[(toadd
[i
]->y
/2) * state
->w
+ (toadd
[i
]->x
/2)]) ^
975 !(dot
->flags
& F_DOT_BLACK
))
981 /* First off, could we just expand the current dot's tile to cover
982 * the space(s) passed in and their opposites? */
983 for (i
= 0; i
< nadd
; i
++) {
984 tileopp
= space_opposite_dot(state
, toadd
[i
], dot
);
985 if (!tileopp
) goto noexpand
;
986 if (tileopp
->flags
& F_TILE_ASSOC
) goto noexpand
;
987 #ifdef STANDALONE_PICTURE_GENERATOR
990 * The opposite tiles have to be the right colour as well.
992 if (!(picture
[(tileopp
->y
/2) * state
->w
+ (tileopp
->x
/2)]) ^
993 !(dot
->flags
& F_DOT_BLACK
))
998 /* OK, all spaces have valid empty opposites: associate spaces and
999 * opposites with our dot. */
1000 for (i
= 0; i
< nadd
; i
++) {
1001 tileopp
= space_opposite_dot(state
, toadd
[i
], dot
);
1002 add_assoc(state
, toadd
[i
], dot
);
1003 add_assoc(state
, tileopp
, dot
);
1004 debug(("Added associations %d,%d and %d,%d --> %d,%d\n",
1005 toadd
[i
]->x
, toadd
[i
]->y
,
1006 tileopp
->x
, tileopp
->y
,
1013 /* Otherwise, try to move dot so as to encompass given spaces: */
1014 /* first, calculate the 'centre of gravity' of the new dot. */
1015 nnew
= dot
->nassoc
+ nadd
; /* number of tiles assoc. with new dot. */
1016 cx
= dot
->x
* dot
->nassoc
;
1017 cy
= dot
->y
* dot
->nassoc
;
1018 for (i
= 0; i
< nadd
; i
++) {
1022 /* If the CoG isn't a whole number, it's not possible. */
1023 if ((cx
% nnew
) != 0 || (cy
% nnew
) != 0) {
1024 debug(("Unable to move dot %d,%d, CoG not whole number.\n",
1028 cx
/= nnew
; cy
/= nnew
;
1030 /* Check whether all spaces in the old tile would have a good
1031 * opposite wrt the new dot. */
1033 md
.newdot
= &SPACE(state
, cx
, cy
);
1035 ret
= foreach_tile(state
, movedot_cb
, IMPOSSIBLE_QUITS
, &md
);
1037 debug(("Unable to move dot %d,%d, new dot not symmetrical.\n",
1041 /* Also check whether all spaces we're adding would have a good
1042 * opposite wrt the new dot. */
1043 for (i
= 0; i
< nadd
; i
++) {
1044 tileopp
= space_opposite_dot(state
, toadd
[i
], md
.newdot
);
1045 if (tileopp
&& (tileopp
->flags
& F_TILE_ASSOC
) &&
1046 (tileopp
->dotx
!= dot
->x
|| tileopp
->doty
!= dot
->y
)) {
1050 debug(("Unable to move dot %d,%d, new dot not symmetrical.\n",
1054 #ifdef STANDALONE_PICTURE_GENERATOR
1056 if (!(picture
[(tileopp
->y
/2) * state
->w
+ (tileopp
->x
/2)]) ^
1057 !(dot
->flags
& F_DOT_BLACK
))
1063 /* If we've got here, we're ok. First, associate all of 'toadd'
1064 * with the _old_ dot (so they'll get fixed up, with their opposites,
1065 * in the next step). */
1066 for (i
= 0; i
< nadd
; i
++) {
1067 debug(("Associating to-add %d,%d with old dot %d,%d.\n",
1068 toadd
[i
]->x
, toadd
[i
]->y
, dot
->x
, dot
->y
));
1069 add_assoc(state
, toadd
[i
], dot
);
1072 /* Finally, move the dot and fix up all the old associations. */
1073 debug(("Moving dot at %d,%d to %d,%d\n",
1074 dot
->x
, dot
->y
, md
.newdot
->x
, md
.newdot
->y
));
1076 #ifdef STANDALONE_PICTURE_GENERATOR
1077 int f
= dot
->flags
& F_DOT_BLACK
;
1081 #ifdef STANDALONE_PICTURE_GENERATOR
1082 md
.newdot
->flags
|= f
;
1087 ret
= foreach_tile(state
, movedot_cb
, 0, &md
);
1094 /* Hard-code to a max. of 2x2 squares, for speed (less malloc) */
1096 #define MAX_OUTSIDE 8
1098 #define MAX_TILE_PERC 20
1100 static int generate_try_block(game_state
*state
, random_state
*rs
,
1101 int x1
, int y1
, int x2
, int y2
)
1103 int x
, y
, nadd
= 0, nout
= 0, i
, maxsz
;
1104 space
*sp
, *toadd
[MAX_TOADD
], *outside
[MAX_OUTSIDE
], *dot
;
1106 if (!INGRID(state
, x1
, y1
) || !INGRID(state
, x2
, y2
)) return 0;
1108 /* We limit the maximum size of tiles to be ~2*sqrt(area); so,
1109 * a 5x5 grid shouldn't have anything >10 tiles, a 20x20 grid
1110 * nothing >40 tiles. */
1111 maxsz
= (int)sqrt((double)(state
->w
* state
->h
)) * 2;
1112 debug(("generate_try_block, maxsz %d\n", maxsz
));
1114 /* Make a static list of the spaces; if any space is already
1115 * associated then quit immediately. */
1116 for (x
= x1
; x
<= x2
; x
+= 2) {
1117 for (y
= y1
; y
<= y2
; y
+= 2) {
1118 assert(nadd
< MAX_TOADD
);
1119 sp
= &SPACE(state
, x
, y
);
1120 assert(sp
->type
== s_tile
);
1121 if (sp
->flags
& F_TILE_ASSOC
) return 0;
1126 /* Make a list of the spaces outside of our block, and shuffle it. */
1127 #define OUTSIDE(x, y) do { \
1128 if (INGRID(state, (x), (y))) { \
1129 assert(nout < MAX_OUTSIDE); \
1130 outside[nout++] = &SPACE(state, (x), (y)); \
1133 for (x
= x1
; x
<= x2
; x
+= 2) {
1137 for (y
= y1
; y
<= y2
; y
+= 2) {
1141 shuffle(outside
, nout
, sizeof(space
*), rs
);
1143 for (i
= 0; i
< nout
; i
++) {
1144 if (!(outside
[i
]->flags
& F_TILE_ASSOC
)) continue;
1145 dot
= &SPACE(state
, outside
[i
]->dotx
, outside
[i
]->doty
);
1146 if (dot
->nassoc
>= maxsz
) {
1147 debug(("Not adding to dot %d,%d, large enough (%d) already.\n",
1148 dot
->x
, dot
->y
, dot
->nassoc
));
1151 if (dot_expand_or_move(state
, dot
, toadd
, nadd
)) return 1;
1156 #ifdef STANDALONE_SOLVER
1158 #define MAXTRIES maxtries
1163 static int solver_obvious_dot(game_state
*state
,space
*dot
);
1167 static void generate_pass(game_state
*state
, random_state
*rs
, int *scratch
,
1168 int perc
, unsigned int flags
)
1170 int sz
= state
->sx
*state
->sy
, nspc
, i
, ret
;
1172 shuffle(scratch
, sz
, sizeof(int), rs
);
1174 /* This bug took me a, er, little while to track down. On PalmOS,
1175 * which has 16-bit signed ints, puzzles over about 9x9 started
1176 * failing to generate because the nspc calculation would start
1177 * to overflow, causing the dots not to be filled in properly. */
1178 nspc
= (int)(((long)perc
* (long)sz
) / 100L);
1179 debug(("generate_pass: %d%% (%d of %dx%d) squares, flags 0x%x\n",
1180 perc
, nspc
, state
->sx
, state
->sy
, flags
));
1182 for (i
= 0; i
< nspc
; i
++) {
1183 space
*sp
= &state
->grid
[scratch
[i
]];
1184 int x1
= sp
->x
, y1
= sp
->y
, x2
= sp
->x
, y2
= sp
->y
;
1186 if (sp
->type
== s_edge
) {
1187 if (IS_VERTICAL_EDGE(sp
->x
)) {
1193 if (sp
->type
!= s_vertex
) {
1194 /* heuristic; expanding from vertices tends to generate lots of
1195 * too-big regions of tiles. */
1196 if (generate_try_block(state
, rs
, x1
, y1
, x2
, y2
))
1197 continue; /* we expanded successfully. */
1200 if (!(flags
& GP_DOTS
)) continue;
1202 if ((sp
->type
== s_edge
) && (i
% 2)) {
1203 debug(("Omitting edge %d,%d as half-of.\n", sp
->x
, sp
->y
));
1207 /* If we've got here we might want to put a dot down. Check
1208 * if we can, and add one if so. */
1209 if (dot_is_possible(state
, sp
, 0)) {
1211 #ifdef STANDALONE_PICTURE_GENERATOR
1213 if (picture
[(sp
->y
/2) * state
->w
+ (sp
->x
/2)])
1214 sp
->flags
|= F_DOT_BLACK
;
1217 ret
= solver_obvious_dot(state
, sp
);
1219 debug(("Added dot (and obvious associations) at %d,%d\n",
1227 static int check_complete(game_state
*state
, int *dsf
, int *colours
);
1228 static int solver_state(game_state
*state
, int maxdiff
);
1230 static char *new_game_desc(game_params
*params
, random_state
*rs
,
1231 char **aux
, int interactive
)
1233 game_state
*state
= blank_game(params
->w
, params
->h
), *copy
;
1235 int *scratch
, sz
= state
->sx
*state
->sy
, i
;
1236 int diff
, ntries
= 0, cc
;
1238 /* Random list of squares to try and process, one-by-one. */
1239 scratch
= snewn(sz
, int);
1240 for (i
= 0; i
< sz
; i
++) scratch
[i
] = i
;
1243 clear_game(state
, 1);
1246 /* generate_pass(state, rs, scratch, 10, GP_DOTS); */
1247 /* generate_pass(state, rs, scratch, 100, 0); */
1248 generate_pass(state
, rs
, scratch
, 100, GP_DOTS
);
1250 game_update_dots(state
);
1254 char *tmp
= encode_game(state
);
1255 debug(("new_game_desc state %dx%d:%s\n", params
->w
, params
->h
, tmp
));
1260 for (i
= 0; i
< state
->sx
*state
->sy
; i
++)
1261 if (state
->grid
[i
].type
== s_tile
)
1262 outline_tile_fordot(state
, &state
->grid
[i
], TRUE
);
1263 cc
= check_complete(state
, NULL
, NULL
);
1266 copy
= dup_game(state
);
1267 clear_game(copy
, 0);
1269 diff
= solver_state(copy
, params
->diff
);
1272 assert(diff
!= DIFF_IMPOSSIBLE
);
1273 if (diff
!= params
->diff
) {
1275 * We'll grudgingly accept a too-easy puzzle, but we must
1276 * _not_ permit a too-hard one (one which the solver
1277 * couldn't handle at all).
1279 if (diff
> params
->diff
||
1280 ntries
< MAXTRIES
) goto generate
;
1283 #ifdef STANDALONE_PICTURE_GENERATOR
1285 * Postprocessing pass to prevent excessive numbers of adjacent
1286 * singletons. Iterate over all edges in random shuffled order;
1287 * for each edge that separates two regions, investigate
1288 * whether removing that edge and merging the regions would
1289 * still yield a valid and soluble puzzle. (The two regions
1290 * must also be the same colour, of course.) If so, do it.
1292 * This postprocessing pass is slow (due to repeated solver
1293 * invocations), and seems to be unnecessary during normal
1294 * unconstrained game generation. However, when generating a
1295 * game under colour constraints, excessive singletons seem to
1296 * turn up more often, so it's worth doing this.
1303 nposns
= params
->w
* (params
->h
+1) + params
->h
* (params
->w
+1);
1304 posns
= snewn(nposns
, int);
1305 for (i
= j
= 0; i
< state
->sx
*state
->sy
; i
++)
1306 if (state
->grid
[i
].type
== s_edge
)
1308 assert(j
== nposns
);
1310 shuffle(posns
, nposns
, sizeof(*posns
), rs
);
1312 for (i
= 0; i
< nposns
; i
++) {
1313 int x
, y
, x0
, y0
, x1
, y1
, cx
, cy
, cn
, cx0
, cy0
, cx1
, cy1
, tx
, ty
;
1314 space
*s0
, *s1
, *ts
, *d0
, *d1
, *dn
;
1317 /* Coordinates of edge space */
1318 x
= posns
[i
] % state
->sx
;
1319 y
= posns
[i
] / state
->sx
;
1321 /* Coordinates of square spaces on either side of edge */
1322 x0
= ((x
+1) & ~1) - 1; /* round down to next odd number */
1323 y0
= ((y
+1) & ~1) - 1;
1324 x1
= 2*x
-x0
; /* and reflect about x to get x1 */
1327 if (!INGRID(state
, x0
, y0
) || !INGRID(state
, x1
, y1
))
1328 continue; /* outermost edge of grid */
1329 s0
= &SPACE(state
, x0
, y0
);
1330 s1
= &SPACE(state
, x1
, y1
);
1331 assert(s0
->type
== s_tile
&& s1
->type
== s_tile
);
1333 if (s0
->dotx
== s1
->dotx
&& s0
->doty
== s1
->doty
)
1334 continue; /* tiles _already_ owned by same dot */
1336 d0
= &SPACE(state
, s0
->dotx
, s0
->doty
);
1337 d1
= &SPACE(state
, s1
->dotx
, s1
->doty
);
1339 if ((d0
->flags
^ d1
->flags
) & F_DOT_BLACK
)
1340 continue; /* different colours: cannot merge */
1343 * Work out where the centre of gravity of the new
1346 cx
= d0
->nassoc
* d0
->x
+ d1
->nassoc
* d1
->x
;
1347 cy
= d0
->nassoc
* d0
->y
+ d1
->nassoc
* d1
->y
;
1348 cn
= d0
->nassoc
+ d1
->nassoc
;
1349 if (cx
% cn
|| cy
% cn
)
1350 continue; /* CoG not at integer coordinates */
1353 assert(INUI(state
, cx
, cy
));
1356 * Ensure that the CoG would actually be _in_ the new
1357 * region, by verifying that all its surrounding tiles
1358 * belong to one or other of our two dots.
1360 cx0
= ((cx
+1) & ~1) - 1; /* round down to next odd number */
1361 cy0
= ((cy
+1) & ~1) - 1;
1362 cx1
= 2*cx
-cx0
; /* and reflect about cx to get cx1 */
1365 for (ty
= cy0
; ty
<= cy1
; ty
+= 2)
1366 for (tx
= cx0
; tx
<= cx1
; tx
+= 2) {
1367 ts
= &SPACE(state
, tx
, ty
);
1368 assert(ts
->type
== s_tile
);
1369 if ((ts
->dotx
!= d0
->x
|| ts
->doty
!= d0
->y
) &&
1370 (ts
->dotx
!= d1
->x
|| ts
->doty
!= d1
->y
))
1377 * Verify that for every tile in either source region,
1378 * that tile's image in the new CoG is also in one of
1379 * the two source regions.
1381 for (ty
= 1; ty
< state
->sy
; ty
+= 2) {
1382 for (tx
= 1; tx
< state
->sx
; tx
+= 2) {
1385 ts
= &SPACE(state
, tx
, ty
);
1386 assert(ts
->type
== s_tile
);
1387 if ((ts
->dotx
!= d0
->x
|| ts
->doty
!= d0
->y
) &&
1388 (ts
->dotx
!= d1
->x
|| ts
->doty
!= d1
->y
))
1389 continue; /* not part of these tiles anyway */
1392 if (!INGRID(state
, tx1
, ty1
)) {
1396 ts
= &SPACE(state
, cx
+cx
-tx
, cy
+cy
-ty
);
1397 if ((ts
->dotx
!= d0
->x
|| ts
->doty
!= d0
->y
) &&
1398 (ts
->dotx
!= d1
->x
|| ts
->doty
!= d1
->y
)) {
1410 * Now we're clear to attempt the merge. We take a copy
1411 * of the game state first, so we can revert it easily
1412 * if the resulting puzzle turns out to have become
1415 copy2
= dup_game(state
);
1419 dn
= &SPACE(state
, cx
, cy
);
1421 dn
->flags
|= (d0
->flags
& F_DOT_BLACK
);
1422 for (ty
= 1; ty
< state
->sy
; ty
+= 2) {
1423 for (tx
= 1; tx
< state
->sx
; tx
+= 2) {
1424 ts
= &SPACE(state
, tx
, ty
);
1425 assert(ts
->type
== s_tile
);
1426 if ((ts
->dotx
!= d0
->x
|| ts
->doty
!= d0
->y
) &&
1427 (ts
->dotx
!= d1
->x
|| ts
->doty
!= d1
->y
))
1428 continue; /* not part of these tiles anyway */
1429 add_assoc(state
, ts
, dn
);
1433 copy
= dup_game(state
);
1434 clear_game(copy
, 0);
1436 newdiff
= solver_state(copy
, params
->diff
);
1438 if (diff
== newdiff
) {
1439 /* Still just as soluble. Let the merge stand. */
1442 /* Became insoluble. Revert. */
1450 desc
= encode_game(state
);
1451 #ifndef STANDALONE_SOLVER
1452 debug(("new_game_desc generated: \n"));
1462 static int solver_obvious(game_state
*state
);
1464 static int dots_too_close(game_state
*state
)
1466 /* Quick-and-dirty check, using half the solver:
1467 * solver_obvious will only fail if the dots are
1468 * too close together, so dot-proximity associations
1470 game_state
*tmp
= dup_game(state
);
1471 int ret
= solver_obvious(tmp
);
1473 return (ret
== -1) ?
1 : 0;
1476 static game_state
*load_game(game_params
*params
, char *desc
,
1479 game_state
*state
= blank_game(params
->w
, params
->h
);
1491 if (n
>= 'a' && n
<= 'y') {
1494 } else if (n
>= 'A' && n
<= 'Y') {
1498 why
= "Invalid characters in game description"; goto fail
;
1500 /* if we got here we incremented i and have a dot to add. */
1501 y
= (i
/ (state
->sx
-2)) + 1;
1502 x
= (i
% (state
->sx
-2)) + 1;
1503 if (!INUI(state
, x
, y
)) {
1504 why
= "Too much data to fit in grid"; goto fail
;
1506 add_dot(&SPACE(state
, x
, y
));
1507 SPACE(state
, x
, y
).flags
|= df
;
1510 game_update_dots(state
);
1512 if (dots_too_close(state
)) {
1513 why
= "Dots too close together"; goto fail
;
1520 if (why_r
) *why_r
= why
;
1524 static char *validate_desc(game_params
*params
, char *desc
)
1527 game_state
*dummy
= load_game(params
, desc
, &why
);
1536 static game_state
*new_game(midend
*me
, game_params
*params
, char *desc
)
1538 game_state
*state
= load_game(params
, desc
, NULL
);
1540 assert("Unable to load ?validated game.");
1549 /* ----------------------------------------------------------
1550 * Solver and all its little wizards.
1553 int solver_recurse_depth
;
1555 typedef struct solver_ctx
{
1557 int sz
; /* state->sx * state->sy */
1558 space
**scratch
; /* size sz */
1562 static solver_ctx
*new_solver(game_state
*state
)
1564 solver_ctx
*sctx
= snew(solver_ctx
);
1565 sctx
->state
= state
;
1566 sctx
->sz
= state
->sx
*state
->sy
;
1567 sctx
->scratch
= snewn(sctx
->sz
, space
*);
1571 static void free_solver(solver_ctx
*sctx
)
1573 sfree(sctx
->scratch
);
1577 /* Solver ideas so far:
1579 * For any empty space, work out how many dots it could associate
1581 * it needs line-of-sight
1582 * it needs an empty space on the far side
1583 * any adjacent lines need corresponding line possibilities.
1586 /* The solver_ctx should keep a list of dot positions, for quicker looping.
1588 * Solver techniques, in order of difficulty:
1589 * obvious adjacency to dots
1590 * transferring tiles to opposite side
1591 * transferring lines to opposite side
1592 * one possible dot for a given tile based on opposite availability
1593 * tile with 3 definite edges next to an associated tile must associate
1596 * one possible dot for a given tile based on line-of-sight
1599 static int solver_add_assoc(game_state
*state
, space
*tile
, int dx
, int dy
,
1602 space
*dot
, *tile_opp
;
1604 dot
= &SPACE(state
, dx
, dy
);
1605 tile_opp
= space_opposite_dot(state
, tile
, dot
);
1607 assert(tile
->type
== s_tile
);
1608 if (tile
->flags
& F_TILE_ASSOC
) {
1609 if ((tile
->dotx
!= dx
) || (tile
->doty
!= dy
)) {
1610 solvep(("%*sSet %d,%d --> %d,%d (%s) impossible; "
1611 "already --> %d,%d.\n",
1612 solver_recurse_depth
*4, "",
1613 tile
->x
, tile
->y
, dx
, dy
, why
,
1614 tile
->dotx
, tile
->doty
));
1617 return 0; /* no-op */
1620 solvep(("%*s%d,%d --> %d,%d impossible, no opposite tile.\n",
1621 solver_recurse_depth
*4, "", tile
->x
, tile
->y
, dx
, dy
));
1624 if (tile_opp
->flags
& F_TILE_ASSOC
&&
1625 (tile_opp
->dotx
!= dx
|| tile_opp
->doty
!= dy
)) {
1626 solvep(("%*sSet %d,%d --> %d,%d (%s) impossible; "
1627 "opposite already --> %d,%d.\n",
1628 solver_recurse_depth
*4, "",
1629 tile
->x
, tile
->y
, dx
, dy
, why
,
1630 tile_opp
->dotx
, tile_opp
->doty
));
1634 add_assoc(state
, tile
, dot
);
1635 add_assoc(state
, tile_opp
, dot
);
1636 solvep(("%*sSetting %d,%d --> %d,%d (%s).\n",
1637 solver_recurse_depth
*4, "",
1638 tile
->x
, tile
->y
,dx
, dy
, why
));
1639 solvep(("%*sSetting %d,%d --> %d,%d (%s, opposite).\n",
1640 solver_recurse_depth
*4, "",
1641 tile_opp
->x
, tile_opp
->y
, dx
, dy
, why
));
1645 static int solver_obvious_dot(game_state
*state
, space
*dot
)
1647 int dx
, dy
, ret
, didsth
= 0;
1650 debug(("%*ssolver_obvious_dot for %d,%d.\n",
1651 solver_recurse_depth
*4, "", dot
->x
, dot
->y
));
1653 assert(dot
->flags
& F_DOT
);
1654 for (dx
= -1; dx
<= 1; dx
++) {
1655 for (dy
= -1; dy
<= 1; dy
++) {
1656 if (!INGRID(state
, dot
->x
+dx
, dot
->y
+dy
)) continue;
1658 tile
= &SPACE(state
, dot
->x
+dx
, dot
->y
+dy
);
1659 if (tile
->type
== s_tile
) {
1660 ret
= solver_add_assoc(state
, tile
, dot
->x
, dot
->y
,
1662 if (ret
< 0) return -1;
1663 if (ret
> 0) didsth
= 1;
1670 static int solver_obvious(game_state
*state
)
1672 int i
, didsth
= 0, ret
;
1674 debug(("%*ssolver_obvious.\n", solver_recurse_depth
*4, ""));
1676 for (i
= 0; i
< state
->ndots
; i
++) {
1677 ret
= solver_obvious_dot(state
, state
->dots
[i
]);
1678 if (ret
< 0) return -1;
1679 if (ret
> 0) didsth
= 1;
1684 static int solver_lines_opposite_cb(game_state
*state
, space
*edge
, void *ctx
)
1686 int didsth
= 0, n
, dx
, dy
;
1687 space
*tiles
[2], *tile_opp
, *edge_opp
;
1689 assert(edge
->type
== s_edge
);
1691 tiles_from_edge(state
, edge
, tiles
);
1693 /* if tiles[0] && tiles[1] && they're both associated
1694 * and they're both associated with different dots,
1695 * ensure the line is set. */
1696 if (!(edge
->flags
& F_EDGE_SET
) &&
1697 tiles
[0] && tiles
[1] &&
1698 (tiles
[0]->flags
& F_TILE_ASSOC
) &&
1699 (tiles
[1]->flags
& F_TILE_ASSOC
) &&
1700 (tiles
[0]->dotx
!= tiles
[1]->dotx
||
1701 tiles
[0]->doty
!= tiles
[1]->doty
)) {
1702 /* No edge, but the two adjacent tiles are both
1703 * associated with different dots; add the edge. */
1704 solvep(("%*sSetting edge %d,%d - tiles different dots.\n",
1705 solver_recurse_depth
*4, "", edge
->x
, edge
->y
));
1706 edge
->flags
|= F_EDGE_SET
;
1710 if (!(edge
->flags
& F_EDGE_SET
)) return didsth
;
1711 for (n
= 0; n
< 2; n
++) {
1712 if (!tiles
[n
]) continue;
1713 assert(tiles
[n
]->type
== s_tile
);
1714 if (!(tiles
[n
]->flags
& F_TILE_ASSOC
)) continue;
1716 tile_opp
= tile_opposite(state
, tiles
[n
]);
1718 solvep(("%*simpossible: edge %d,%d has assoc. tile %d,%d"
1719 " with no opposite.\n",
1720 solver_recurse_depth
*4, "",
1721 edge
->x
, edge
->y
, tiles
[n
]->x
, tiles
[n
]->y
));
1722 /* edge of tile has no opposite edge (off grid?);
1723 * this is impossible. */
1727 dx
= tiles
[n
]->x
- edge
->x
;
1728 dy
= tiles
[n
]->y
- edge
->y
;
1729 assert(INGRID(state
, tile_opp
->x
+dx
, tile_opp
->y
+dy
));
1730 edge_opp
= &SPACE(state
, tile_opp
->x
+dx
, tile_opp
->y
+dy
);
1731 if (!(edge_opp
->flags
& F_EDGE_SET
)) {
1732 solvep(("%*sSetting edge %d,%d as opposite %d,%d\n",
1733 solver_recurse_depth
*4, "",
1734 tile_opp
->x
-dx
, tile_opp
->y
-dy
, edge
->x
, edge
->y
));
1735 edge_opp
->flags
|= F_EDGE_SET
;
1742 static int solver_spaces_oneposs_cb(game_state
*state
, space
*tile
, void *ctx
)
1745 struct space
*edgeadj
[4], *tileadj
[4];
1748 assert(tile
->type
== s_tile
);
1749 if (tile
->flags
& F_TILE_ASSOC
) return 0;
1751 adjacencies(state
, tile
, edgeadj
, tileadj
);
1753 /* Empty tile. If each edge is either set, or associated with
1754 * the same dot, we must also associate with dot. */
1755 eset
= 0; dotx
= -1; doty
= -1;
1756 for (n
= 0; n
< 4; n
++) {
1758 assert(edgeadj
[n
]->type
== s_edge
);
1759 if (edgeadj
[n
]->flags
& F_EDGE_SET
) {
1763 assert(tileadj
[n
]->type
== s_tile
);
1765 /* If an adjacent tile is empty we can't make any deductions.*/
1766 if (!(tileadj
[n
]->flags
& F_TILE_ASSOC
))
1769 /* If an adjacent tile is assoc. with a different dot
1770 * we can't make any deductions. */
1771 if (dotx
!= -1 && doty
!= -1 &&
1772 (tileadj
[n
]->dotx
!= dotx
||
1773 tileadj
[n
]->doty
!= doty
))
1776 dotx
= tileadj
[n
]->dotx
;
1777 doty
= tileadj
[n
]->doty
;
1781 solvep(("%*simpossible: empty tile %d,%d has 4 edges\n",
1782 solver_recurse_depth
*4, "",
1786 assert(dotx
!= -1 && doty
!= -1);
1788 ret
= solver_add_assoc(state
, tile
, dotx
, doty
, "rest are edges");
1789 if (ret
== -1) return -1;
1790 assert(ret
!= 0); /* really should have done something. */
1795 /* Improved algorithm for tracking line-of-sight from dots, and not spaces.
1797 * The solver_ctx already stores a list of dots: the algorithm proceeds by
1798 * expanding outwards from each dot in turn, expanding first to the boundary
1799 * of its currently-connected tile and then to all empty tiles that could see
1800 * it. Empty tiles will be flagged with a 'can see dot <x,y>' sticker.
1802 * Expansion will happen by (symmetrically opposite) pairs of squares; if
1803 * a square hasn't an opposite number there's no point trying to expand through
1804 * it. Empty tiles will therefore also be tagged in pairs.
1806 * If an empty tile already has a 'can see dot <x,y>' tag from a previous dot,
1807 * it (and its partner) gets untagged (or, rather, a 'can see two dots' tag)
1808 * because we're looking for single-dot possibilities.
1810 * Once we've gone through all the dots, any which still have a 'can see dot'
1811 * tag get associated with that dot (because it must have been the only one);
1812 * any without any tag (i.e. that could see _no_ dots) cause an impossibility
1815 * The expansion will happen each time with a stored list of (space *) pairs,
1816 * rather than a mark-and-sweep idea; that's horrifically inefficient.
1818 * expansion algorithm:
1820 * * allocate list of (space *) the size of s->sx*s->sy.
1821 * * allocate second grid for (flags, dotx, doty) size of sx*sy.
1823 * clear second grid (flags = 0, all dotx and doty = 0)
1824 * flags: F_REACHABLE, F_MULTIPLE
1827 * * for each dot, start with one pair of tiles that are associated with it --
1828 * * vertex --> (dx+1, dy+1), (dx-1, dy-1)
1829 * * edge --> (adj1, adj2)
1830 * * tile --> (tile, tile) ???
1831 * * mark that pair of tiles with F_MARK, clear all other F_MARKs.
1832 * * add two tiles to start of list.
1834 * set start = 0, end = next = 2
1836 * from (start to end-1, step 2) {
1837 * * we have two tiles (t1, t2), opposites wrt our dot.
1838 * * for each (at1) sensible adjacent tile to t1 (i.e. not past an edge):
1839 * * work out at2 as the opposite to at1
1840 * * assert at1 and at2 have the same F_MARK values.
1841 * * if at1 & F_MARK ignore it (we've been there on a previous sweep)
1842 * * if either are associated with a different dot
1843 * * mark both with F_MARK (so we ignore them later)
1844 * * otherwise (assoc. with our dot, or empty):
1845 * * mark both with F_MARK
1846 * * add their space * values to the end of the list, set next += 2.
1850 * * we didn't add any new squares; exit the loop.
1852 * * set start = next+1, end = next. go round again
1854 * We've finished expanding from the dot. Now, for each square we have
1855 * in our list (--> each square with F_MARK):
1856 * * if the tile is empty:
1857 * * if F_REACHABLE was already set
1860 * * set F_REACHABLE, set dotx and doty to our dot.
1862 * Then, continue the whole thing for each dot in turn.
1864 * Once we've done for each dot, go through the entire grid looking for
1865 * empty tiles: for each empty tile:
1866 * if F_REACHABLE and not F_MULTIPLE, set that dot (and its double)
1867 * if !F_REACHABLE, return as impossible.
1871 /* Returns 1 if this tile is either already associated with this dot,
1873 static int solver_expand_checkdot(space
*tile
, space
*dot
)
1875 if (!(tile
->flags
& F_TILE_ASSOC
)) return 1;
1876 if (tile
->dotx
== dot
->x
&& tile
->doty
== dot
->y
) return 1;
1880 static void solver_expand_fromdot(game_state
*state
, space
*dot
, solver_ctx
*sctx
)
1882 int i
, j
, x
, y
, start
, end
, next
;
1885 /* Clear the grid of the (space) flags we'll use. */
1887 /* This is well optimised; analysis showed that:
1888 for (i = 0; i < sctx->sz; i++) state->grid[i].flags &= ~F_MARK;
1889 took up ~85% of the total function time! */
1890 for (y
= 1; y
< state
->sy
; y
+= 2) {
1891 sp
= &SPACE(state
, 1, y
);
1892 for (x
= 1; x
< state
->sx
; x
+= 2, sp
+= 2)
1893 sp
->flags
&= ~F_MARK
;
1896 /* Seed the list of marked squares with two that must be associated
1897 * with our dot (possibly the same space) */
1898 if (dot
->type
== s_tile
) {
1899 sctx
->scratch
[0] = sctx
->scratch
[1] = dot
;
1900 } else if (dot
->type
== s_edge
) {
1901 tiles_from_edge(state
, dot
, sctx
->scratch
);
1902 } else if (dot
->type
== s_vertex
) {
1903 /* pick two of the opposite ones arbitrarily. */
1904 sctx
->scratch
[0] = &SPACE(state
, dot
->x
-1, dot
->y
-1);
1905 sctx
->scratch
[1] = &SPACE(state
, dot
->x
+1, dot
->y
+1);
1907 assert(sctx
->scratch
[0]->flags
& F_TILE_ASSOC
);
1908 assert(sctx
->scratch
[1]->flags
& F_TILE_ASSOC
);
1910 sctx
->scratch
[0]->flags
|= F_MARK
;
1911 sctx
->scratch
[1]->flags
|= F_MARK
;
1913 debug(("%*sexpand from dot %d,%d seeded with %d,%d and %d,%d.\n",
1914 solver_recurse_depth
*4, "", dot
->x
, dot
->y
,
1915 sctx
->scratch
[0]->x
, sctx
->scratch
[0]->y
,
1916 sctx
->scratch
[1]->x
, sctx
->scratch
[1]->y
));
1918 start
= 0; end
= 2; next
= 2;
1921 debug(("%*sexpand: start %d, end %d, next %d\n",
1922 solver_recurse_depth
*4, "", start
, end
, next
));
1923 for (i
= start
; i
< end
; i
+= 2) {
1924 space
*t1
= sctx
->scratch
[i
]/*, *t2 = sctx->scratch[i+1]*/;
1925 space
*edges
[4], *tileadj
[4], *tileadj2
;
1927 adjacencies(state
, t1
, edges
, tileadj
);
1929 for (j
= 0; j
< 4; j
++) {
1931 if (edges
[j
]->flags
& F_EDGE_SET
) continue;
1934 if (tileadj
[j
]->flags
& F_MARK
) continue; /* seen before. */
1936 /* We have a tile adjacent to t1; find its opposite. */
1937 tileadj2
= space_opposite_dot(state
, tileadj
[j
], dot
);
1939 debug(("%*sMarking %d,%d, no opposite.\n",
1940 solver_recurse_depth
*4, "",
1941 tileadj
[j
]->x
, tileadj
[j
]->y
));
1942 tileadj
[j
]->flags
|= F_MARK
;
1943 continue; /* no opposite, so mark for next time. */
1945 /* If the tile had an opposite we should have either seen both of
1946 * these, or neither of these, before. */
1947 assert(!(tileadj2
->flags
& F_MARK
));
1949 if (solver_expand_checkdot(tileadj
[j
], dot
) &&
1950 solver_expand_checkdot(tileadj2
, dot
)) {
1951 /* Both tiles could associate with this dot; add them to
1953 debug(("%*sAdding %d,%d and %d,%d to possibles list.\n",
1954 solver_recurse_depth
*4, "",
1955 tileadj
[j
]->x
, tileadj
[j
]->y
, tileadj2
->x
, tileadj2
->y
));
1956 sctx
->scratch
[next
++] = tileadj
[j
];
1957 sctx
->scratch
[next
++] = tileadj2
;
1959 /* Either way, we've seen these tiles already so mark them. */
1960 debug(("%*sMarking %d,%d and %d,%d.\n",
1961 solver_recurse_depth
*4, "",
1962 tileadj
[j
]->x
, tileadj
[j
]->y
, tileadj2
->x
, tileadj2
->y
));
1963 tileadj
[j
]->flags
|= F_MARK
;
1964 tileadj2
->flags
|= F_MARK
;
1968 /* We added more squares; go back and try again. */
1969 start
= end
; end
= next
; goto expand
;
1972 /* We've expanded as far as we can go. Now we update the main flags
1973 * on all tiles we've expanded into -- if they were empty, we have
1974 * found possible associations for this dot. */
1975 for (i
= 0; i
< end
; i
++) {
1976 if (sctx
->scratch
[i
]->flags
& F_TILE_ASSOC
) continue;
1977 if (sctx
->scratch
[i
]->flags
& F_REACHABLE
) {
1978 /* This is (at least) the second dot this tile could
1979 * associate with. */
1980 debug(("%*sempty tile %d,%d could assoc. other dot %d,%d\n",
1981 solver_recurse_depth
*4, "",
1982 sctx
->scratch
[i
]->x
, sctx
->scratch
[i
]->y
, dot
->x
, dot
->y
));
1983 sctx
->scratch
[i
]->flags
|= F_MULTIPLE
;
1985 /* This is the first (possibly only) dot. */
1986 debug(("%*sempty tile %d,%d could assoc. 1st dot %d,%d\n",
1987 solver_recurse_depth
*4, "",
1988 sctx
->scratch
[i
]->x
, sctx
->scratch
[i
]->y
, dot
->x
, dot
->y
));
1989 sctx
->scratch
[i
]->flags
|= F_REACHABLE
;
1990 sctx
->scratch
[i
]->dotx
= dot
->x
;
1991 sctx
->scratch
[i
]->doty
= dot
->y
;
1997 static int solver_expand_postcb(game_state
*state
, space
*tile
, void *ctx
)
1999 assert(tile
->type
== s_tile
);
2001 if (tile
->flags
& F_TILE_ASSOC
) return 0;
2003 if (!(tile
->flags
& F_REACHABLE
)) {
2004 solvep(("%*simpossible: space (%d,%d) can reach no dots.\n",
2005 solver_recurse_depth
*4, "", tile
->x
, tile
->y
));
2008 if (tile
->flags
& F_MULTIPLE
) return 0;
2010 return solver_add_assoc(state
, tile
, tile
->dotx
, tile
->doty
,
2011 "single possible dot after expansion");
2014 static int solver_expand_dots(game_state
*state
, solver_ctx
*sctx
)
2018 for (i
= 0; i
< sctx
->sz
; i
++)
2019 state
->grid
[i
].flags
&= ~(F_REACHABLE
|F_MULTIPLE
);
2021 for (i
= 0; i
< state
->ndots
; i
++)
2022 solver_expand_fromdot(state
, state
->dots
[i
], sctx
);
2024 return foreach_tile(state
, solver_expand_postcb
, IMPOSSIBLE_QUITS
, sctx
);
2027 struct recurse_ctx
{
2032 static int solver_recurse_cb(game_state
*state
, space
*tile
, void *ctx
)
2034 struct recurse_ctx
*rctx
= (struct recurse_ctx
*)ctx
;
2037 assert(tile
->type
== s_tile
);
2038 if (tile
->flags
& F_TILE_ASSOC
) return 0;
2040 /* We're unassociated: count up all the dots we could associate with. */
2041 for (i
= 0; i
< state
->ndots
; i
++) {
2042 if (dotfortile(state
, tile
, state
->dots
[i
]))
2045 if (n
> rctx
->bestn
) {
2052 static int solver_state(game_state
*state
, int maxdiff
);
2054 #define MAXRECURSE 5
2056 static int solver_recurse(game_state
*state
, int maxdiff
)
2058 int diff
= DIFF_IMPOSSIBLE
, ret
, n
, gsz
= state
->sx
* state
->sy
;
2059 space
*ingrid
, *outgrid
= NULL
, *bestopp
;
2060 struct recurse_ctx rctx
;
2062 if (solver_recurse_depth
>= MAXRECURSE
) {
2063 solvep(("Limiting recursion to %d, returning.", MAXRECURSE
));
2064 return DIFF_UNFINISHED
;
2067 /* Work out the cell to recurse on; go through all unassociated tiles
2068 * and find which one has the most possible dots it could associate
2073 foreach_tile(state
, solver_recurse_cb
, 0, &rctx
);
2074 if (rctx
.bestn
== 0) return DIFF_IMPOSSIBLE
; /* or assert? */
2077 solvep(("%*sRecursing around %d,%d, with %d possible dots.\n",
2078 solver_recurse_depth
*4, "",
2079 rctx
.best
->x
, rctx
.best
->y
, rctx
.bestn
));
2081 #ifdef STANDALONE_SOLVER
2082 solver_recurse_depth
++;
2085 ingrid
= snewn(gsz
, struct space
);
2086 memcpy(ingrid
, state
->grid
, gsz
* sizeof(struct space
));
2088 for (n
= 0; n
< state
->ndots
; n
++) {
2089 memcpy(state
->grid
, ingrid
, gsz
* sizeof(struct space
));
2091 if (!dotfortile(state
, rctx
.best
, state
->dots
[n
])) continue;
2093 /* set cell (temporarily) pointing to that dot. */
2094 solver_add_assoc(state
, rctx
.best
,
2095 state
->dots
[n
]->x
, state
->dots
[n
]->y
,
2096 "Attempting for recursion");
2098 ret
= solver_state(state
, maxdiff
);
2100 if (diff
== DIFF_IMPOSSIBLE
&& ret
!= DIFF_IMPOSSIBLE
) {
2101 /* we found our first solved grid; copy it away. */
2103 outgrid
= snewn(gsz
, struct space
);
2104 memcpy(outgrid
, state
->grid
, gsz
* sizeof(struct space
));
2106 /* reset cell back to unassociated. */
2107 bestopp
= tile_opposite(state
, rctx
.best
);
2108 assert(bestopp
&& bestopp
->flags
& F_TILE_ASSOC
);
2110 remove_assoc(state
, rctx
.best
);
2111 remove_assoc(state
, bestopp
);
2113 if (ret
== DIFF_AMBIGUOUS
|| ret
== DIFF_UNFINISHED
)
2115 else if (ret
== DIFF_IMPOSSIBLE
)
2118 /* precisely one solution */
2119 if (diff
== DIFF_IMPOSSIBLE
)
2120 diff
= DIFF_UNREASONABLE
;
2122 diff
= DIFF_AMBIGUOUS
;
2124 /* if we've found >1 solution, or ran out of recursion,
2125 * give up immediately. */
2126 if (diff
== DIFF_AMBIGUOUS
|| diff
== DIFF_UNFINISHED
)
2130 #ifdef STANDALONE_SOLVER
2131 solver_recurse_depth
--;
2135 /* we found (at least one) soln; copy it back to state */
2136 memcpy(state
->grid
, outgrid
, gsz
* sizeof(struct space
));
2143 static int solver_state(game_state
*state
, int maxdiff
)
2145 solver_ctx
*sctx
= new_solver(state
);
2146 int ret
, diff
= DIFF_NORMAL
;
2148 #ifdef STANDALONE_PICTURE_GENERATOR
2149 /* hack, hack: set picture to NULL during solving so that add_assoc
2150 * won't complain when we attempt recursive guessing and guess wrong */
2151 int *savepic
= picture
;
2155 ret
= solver_obvious(state
);
2157 diff
= DIFF_IMPOSSIBLE
;
2161 #define CHECKRET(d) do { \
2162 if (ret < 0) { diff = DIFF_IMPOSSIBLE; goto got_result; } \
2163 if (ret > 0) { diff = max(diff, (d)); goto cont; } \
2168 ret
= foreach_edge(state
, solver_lines_opposite_cb
,
2169 IMPOSSIBLE_QUITS
, sctx
);
2170 CHECKRET(DIFF_NORMAL
);
2172 ret
= foreach_tile(state
, solver_spaces_oneposs_cb
,
2173 IMPOSSIBLE_QUITS
, sctx
);
2174 CHECKRET(DIFF_NORMAL
);
2176 ret
= solver_expand_dots(state
, sctx
);
2177 CHECKRET(DIFF_NORMAL
);
2179 if (maxdiff
<= DIFF_NORMAL
)
2184 /* if we reach here, we've made no deductions, so we terminate. */
2188 if (check_complete(state
, NULL
, NULL
)) goto got_result
;
2190 diff
= (maxdiff
>= DIFF_UNREASONABLE
) ?
2191 solver_recurse(state
, maxdiff
) : DIFF_UNFINISHED
;
2195 #ifndef STANDALONE_SOLVER
2196 debug(("solver_state ends, diff %s:\n", galaxies_diffnames
[diff
]));
2200 #ifdef STANDALONE_PICTURE_GENERATOR
2208 static char *solve_game(game_state
*state
, game_state
*currstate
,
2209 char *aux
, char **error
)
2211 game_state
*tosolve
;
2216 tosolve
= dup_game(currstate
);
2217 diff
= solver_state(tosolve
, DIFF_UNREASONABLE
);
2218 if (diff
!= DIFF_UNFINISHED
&& diff
!= DIFF_IMPOSSIBLE
) {
2219 debug(("solve_game solved with current state.\n"));
2224 tosolve
= dup_game(state
);
2225 diff
= solver_state(tosolve
, DIFF_UNREASONABLE
);
2226 if (diff
!= DIFF_UNFINISHED
&& diff
!= DIFF_IMPOSSIBLE
) {
2227 debug(("solve_game solved with original state.\n"));
2236 * Clear tile associations: the solution will only include the
2239 for (i
= 0; i
< tosolve
->sx
*tosolve
->sy
; i
++)
2240 tosolve
->grid
[i
].flags
&= ~F_TILE_ASSOC
;
2241 ret
= diff_game(currstate
, tosolve
, 1);
2247 /* ----------------------------------------------------------
2253 int dx
, dy
; /* pixel coords of drag pos. */
2254 int dotx
, doty
; /* grid coords of dot we're dragging from. */
2255 int srcx
, srcy
; /* grid coords of drag start */
2258 static game_ui
*new_ui(game_state
*state
)
2260 game_ui
*ui
= snew(game_ui
);
2261 ui
->dragging
= FALSE
;
2265 static void free_ui(game_ui
*ui
)
2270 static char *encode_ui(game_ui
*ui
)
2275 static void decode_ui(game_ui
*ui
, char *encoding
)
2279 static void game_changed_state(game_ui
*ui
, game_state
*oldstate
,
2280 game_state
*newstate
)
2284 #define FLASH_TIME 0.15F
2286 #define PREFERRED_TILE_SIZE 32
2287 #define TILE_SIZE (ds->tilesize)
2288 #define DOT_SIZE (TILE_SIZE / 4)
2289 #define EDGE_THICKNESS (max(TILE_SIZE / 16, 2))
2290 #define BORDER TILE_SIZE
2292 #define COORD(x) ( (x) * TILE_SIZE + BORDER )
2293 #define SCOORD(x) ( ((x) * TILE_SIZE)/2 + BORDER )
2294 #define FROMCOORD(x) ( ((x) - BORDER) / TILE_SIZE )
2296 #define DRAW_WIDTH (BORDER * 2 + ds->w * TILE_SIZE)
2297 #define DRAW_HEIGHT (BORDER * 2 + ds->h * TILE_SIZE)
2299 struct game_drawstate
{
2303 unsigned long *grid
;
2307 int dragging
, dragx
, dragy
;
2309 int *colour_scratch
;
2312 #define CORNER_TOLERANCE 0.15F
2313 #define CENTRE_TOLERANCE 0.15F
2316 * Round FP coordinates to the centre of the nearest edge.
2319 static void coord_round_to_edge(float x
, float y
, int *xr
, int *yr
)
2321 float xs
, ys
, xv
, yv
, dx
, dy
;
2324 * Find the nearest square-centre.
2326 xs
= (float)floor(x
) + 0.5F
;
2327 ys
= (float)floor(y
) + 0.5F
;
2330 * Find the nearest grid vertex.
2332 xv
= (float)floor(x
+ 0.5F
);
2333 yv
= (float)floor(y
+ 0.5F
);
2336 * Determine whether the horizontal or vertical edge from that
2337 * vertex alongside that square is closer to us, by comparing
2338 * distances from the square cente.
2340 dx
= (float)fabs(x
- xs
);
2341 dy
= (float)fabs(y
- ys
);
2343 /* Vertical edge: x-coord of corner,
2344 * y-coord of square centre. */
2346 *yr
= 1 + 2 * (int)floor(ys
);
2348 /* Horizontal edge: x-coord of square centre,
2349 * y-coord of corner. */
2350 *xr
= 1 + 2 * (int)floor(xs
);
2357 static char *interpret_move(game_state
*state
, game_ui
*ui
, game_drawstate
*ds
,
2358 int x
, int y
, int button
)
2364 px
= 2*FROMCOORD((float)x
) + 0.5;
2365 py
= 2*FROMCOORD((float)y
) + 0.5;
2369 if (button
== 'C' || button
== 'c') return dupstr("C");
2371 if (button
== 'S' || button
== 's') {
2373 game_state
*tmp
= dup_game(state
);
2374 state
->cdiff
= solver_state(tmp
, DIFF_UNREASONABLE
-1);
2375 ret
= diff_game(state
, tmp
, 0);
2380 if (button
== LEFT_BUTTON
|| button
== RIGHT_BUTTON
) {
2381 if (!INUI(state
, px
, py
)) return NULL
;
2382 sp
= &SPACE(state
, px
, py
);
2383 if (!dot_is_possible(state
, sp
, 1)) return NULL
;
2384 sprintf(buf
, "%c%d,%d",
2385 (char)((button
== LEFT_BUTTON
) ?
'D' : 'd'), px
, py
);
2392 static char *interpret_move(game_state
*state
, game_ui
*ui
, game_drawstate
*ds
,
2393 int x
, int y
, int button
)
2395 /* UI operations (play mode):
2397 * Toggle edge (set/unset) (left-click on edge)
2398 * Associate space with dot (left-drag from dot)
2399 * Unassociate space (left-drag from space off grid)
2400 * Autofill lines around shape? (right-click?)
2402 * (edit mode; will clear all lines/associations)
2404 * Add or remove dot (left-click)
2409 struct space
*sp
, *dot
;
2411 if (button
== 'H' || button
== 'h') {
2413 game_state
*tmp
= dup_game(state
);
2414 solver_obvious(tmp
);
2415 ret
= diff_game(state
, tmp
, 0);
2420 if (button
== LEFT_BUTTON
) {
2421 coord_round_to_edge(FROMCOORD((float)x
), FROMCOORD((float)y
),
2424 if (!INUI(state
, px
, py
)) return NULL
;
2426 sp
= &SPACE(state
, px
, py
);
2427 assert(sp
->type
== s_edge
);
2429 sprintf(buf
, "E%d,%d", px
, py
);
2432 } else if (button
== RIGHT_BUTTON
) {
2435 px
= (int)(2*FROMCOORD((float)x
) + 0.5);
2436 py
= (int)(2*FROMCOORD((float)y
) + 0.5);
2441 * If there's a dot anywhere nearby, we pick up an arrow
2442 * pointing at that dot.
2444 for (py1
= py
-1; py1
<= py
+1; py1
++)
2445 for (px1
= px
-1; px1
<= px
+1; px1
++) {
2446 if (px1
>= 0 && px1
< state
->sx
&&
2447 py1
>= 0 && py1
< state
->sy
&&
2448 x
>= SCOORD(px1
-1) && x
< SCOORD(px1
+1) &&
2449 y
>= SCOORD(py1
-1) && y
< SCOORD(py1
+1) &&
2450 SPACE(state
, px1
, py1
).flags
& F_DOT
) {
2452 * Found a dot. Begin a drag from it.
2454 dot
= &SPACE(state
, px1
, py1
);
2457 goto done
; /* multi-level break */
2462 * Otherwise, find the nearest _square_, and pick up the
2463 * same arrow as it's got on it, if any.
2466 px
= 2*FROMCOORD(x
+TILE_SIZE
) - 1;
2467 py
= 2*FROMCOORD(y
+TILE_SIZE
) - 1;
2468 if (px
>= 0 && px
< state
->sx
&& py
>= 0 && py
< state
->sy
) {
2469 sp
= &SPACE(state
, px
, py
);
2470 if (sp
->flags
& F_TILE_ASSOC
) {
2471 dot
= &SPACE(state
, sp
->dotx
, sp
->doty
);
2480 * Now, if we've managed to find a dot, begin a drag.
2483 ui
->dragging
= TRUE
;
2490 } else if (button
== RIGHT_DRAG
&& ui
->dragging
) {
2491 /* just move the drag coords. */
2495 } else if (button
== RIGHT_RELEASE
&& ui
->dragging
) {
2496 ui
->dragging
= FALSE
;
2499 * Drags are always targeted at a single square.
2501 px
= 2*FROMCOORD(x
+TILE_SIZE
) - 1;
2502 py
= 2*FROMCOORD(y
+TILE_SIZE
) - 1;
2505 * Dragging an arrow on to the same square it started from
2506 * is a null move; just update the ui and finish.
2508 if (px
== ui
->srcx
&& py
== ui
->srcy
)
2515 * Otherwise, we remove the arrow from its starting
2516 * square if we didn't start from a dot...
2518 if ((ui
->srcx
!= ui
->dotx
|| ui
->srcy
!= ui
->doty
) &&
2519 SPACE(state
, ui
->srcx
, ui
->srcy
).flags
& F_TILE_ASSOC
) {
2520 sprintf(buf
+ strlen(buf
), "%sU%d,%d", sep
, ui
->srcx
, ui
->srcy
);
2525 * ... and if the square we're moving it _to_ is valid, we
2526 * add one there instead.
2528 if (INUI(state
, px
, py
)) {
2529 sp
= &SPACE(state
, px
, py
);
2531 if (!(sp
->flags
& F_DOT
) && !(sp
->flags
& F_TILE_ASSOC
))
2532 sprintf(buf
+ strlen(buf
), "%sA%d,%d,%d,%d",
2533 sep
, px
, py
, ui
->dotx
, ui
->doty
);
2546 static int check_complete(game_state
*state
, int *dsf
, int *colours
)
2548 int w
= state
->w
, h
= state
->h
;
2553 int minx
, miny
, maxx
, maxy
;
2559 dsf
= snew_dsf(w
*h
);
2567 * During actual game play, completion checking is done on the
2568 * basis of the edges rather than the square associations. So
2569 * first we must go through the grid figuring out the connected
2570 * components into which the edges divide it.
2572 for (y
= 0; y
< h
; y
++)
2573 for (x
= 0; x
< w
; x
++) {
2574 if (y
+1 < h
&& !(SPACE(state
, 2*x
+1, 2*y
+2).flags
& F_EDGE_SET
))
2575 dsf_merge(dsf
, y
*w
+x
, (y
+1)*w
+x
);
2576 if (x
+1 < w
&& !(SPACE(state
, 2*x
+2, 2*y
+1).flags
& F_EDGE_SET
))
2577 dsf_merge(dsf
, y
*w
+x
, y
*w
+(x
+1));
2581 * That gives us our connected components. Now, for each
2582 * component, decide whether it's _valid_. A valid component is
2585 * - is 180-degree rotationally symmetric
2586 * - has a dot at its centre of symmetry
2587 * - has no other dots anywhere within it (including on its
2589 * - contains no internal edges (i.e. edges separating two
2590 * squares which are both part of the component).
2594 * First, go through the grid finding the bounding box of each
2597 sqdata
= snewn(w
*h
, struct sqdata
);
2598 for (i
= 0; i
< w
*h
; i
++) {
2599 sqdata
[i
].minx
= w
+1;
2600 sqdata
[i
].miny
= h
+1;
2601 sqdata
[i
].maxx
= sqdata
[i
].maxy
= -1;
2602 sqdata
[i
].valid
= FALSE
;
2604 for (y
= 0; y
< h
; y
++)
2605 for (x
= 0; x
< w
; x
++) {
2606 i
= dsf_canonify(dsf
, y
*w
+x
);
2607 if (sqdata
[i
].minx
> x
)
2609 if (sqdata
[i
].maxx
< x
)
2611 if (sqdata
[i
].miny
> y
)
2613 if (sqdata
[i
].maxy
< y
)
2615 sqdata
[i
].valid
= TRUE
;
2619 * Now we're in a position to loop over each actual component
2620 * and figure out where its centre of symmetry has to be if
2623 for (i
= 0; i
< w
*h
; i
++)
2624 if (sqdata
[i
].valid
) {
2626 cx
= sqdata
[i
].cx
= sqdata
[i
].minx
+ sqdata
[i
].maxx
+ 1;
2627 cy
= sqdata
[i
].cy
= sqdata
[i
].miny
+ sqdata
[i
].maxy
+ 1;
2628 if (!(SPACE(state
, sqdata
[i
].cx
, sqdata
[i
].cy
).flags
& F_DOT
))
2629 sqdata
[i
].valid
= FALSE
; /* no dot at centre of symmetry */
2630 if (dsf_canonify(dsf
, (cy
-1)/2*w
+(cx
-1)/2) != i
||
2631 dsf_canonify(dsf
, (cy
)/2*w
+(cx
-1)/2) != i
||
2632 dsf_canonify(dsf
, (cy
-1)/2*w
+(cx
)/2) != i
||
2633 dsf_canonify(dsf
, (cy
)/2*w
+(cx
)/2) != i
)
2634 sqdata
[i
].valid
= FALSE
; /* dot at cx,cy isn't ours */
2635 if (SPACE(state
, sqdata
[i
].cx
, sqdata
[i
].cy
).flags
& F_DOT_BLACK
)
2636 sqdata
[i
].colour
= 2;
2638 sqdata
[i
].colour
= 1;
2642 * Now we loop over the whole grid again, this time finding
2643 * extraneous dots (any dot which wholly or partially overlaps
2644 * a square and is not at the centre of symmetry of that
2645 * square's component disqualifies the component from validity)
2646 * and extraneous edges (any edge separating two squares
2647 * belonging to the same component also disqualifies that
2650 for (y
= 1; y
< state
->sy
-1; y
++)
2651 for (x
= 1; x
< state
->sx
-1; x
++) {
2652 space
*sp
= &SPACE(state
, x
, y
);
2654 if (sp
->flags
& F_DOT
) {
2656 * There's a dot here. Use it to disqualify any
2657 * component which deserves it.
2660 for (cy
= (y
-1) >> 1; cy
<= y
>> 1; cy
++)
2661 for (cx
= (x
-1) >> 1; cx
<= x
>> 1; cx
++) {
2662 i
= dsf_canonify(dsf
, cy
*w
+cx
);
2663 if (x
!= sqdata
[i
].cx
|| y
!= sqdata
[i
].cy
)
2664 sqdata
[i
].valid
= FALSE
;
2668 if (sp
->flags
& F_EDGE_SET
) {
2670 * There's an edge here. Use it to disqualify a
2671 * component if necessary.
2673 int cx1
= (x
-1) >> 1, cx2
= x
>> 1;
2674 int cy1
= (y
-1) >> 1, cy2
= y
>> 1;
2675 assert((cx1
==cx2
) ^ (cy1
==cy2
));
2676 i
= dsf_canonify(dsf
, cy1
*w
+cx1
);
2677 if (i
== dsf_canonify(dsf
, cy2
*w
+cx2
))
2678 sqdata
[i
].valid
= FALSE
;
2683 * And finally we test rotational symmetry: for each square in
2684 * the grid, find which component it's in, test that that
2685 * component also has a square in the symmetric position, and
2686 * disqualify it if it doesn't.
2688 for (y
= 0; y
< h
; y
++)
2689 for (x
= 0; x
< w
; x
++) {
2692 i
= dsf_canonify(dsf
, y
*w
+x
);
2694 x2
= sqdata
[i
].cx
- 1 - x
;
2695 y2
= sqdata
[i
].cy
- 1 - y
;
2696 if (i
!= dsf_canonify(dsf
, y2
*w
+x2
))
2697 sqdata
[i
].valid
= FALSE
;
2701 * That's it. We now have all the connected components marked
2702 * as valid or not valid. So now we return a `colours' array if
2703 * we were asked for one, and also we return an overall
2704 * true/false value depending on whether _every_ square in the
2705 * grid is part of a valid component.
2708 for (i
= 0; i
< w
*h
; i
++) {
2709 int ci
= dsf_canonify(dsf
, i
);
2710 int thisok
= sqdata
[ci
].valid
;
2712 colours
[i
] = thisok ? sqdata
[ci
].colour
: 0;
2713 ret
= ret
&& thisok
;
2723 static game_state
*execute_move(game_state
*state
, char *move
)
2725 int x
, y
, ax
, ay
, n
, dx
, dy
;
2726 game_state
*ret
= dup_game(state
);
2727 struct space
*sp
, *dot
;
2729 debug(("%s\n", move
));
2733 if (c
== 'E' || c
== 'U' || c
== 'M'
2735 || c
== 'D' || c
== 'd'
2739 if (sscanf(move
, "%d,%d%n", &x
, &y
, &n
) != 2 ||
2743 sp
= &SPACE(ret
, x
, y
);
2745 if (c
== 'D' || c
== 'd') {
2746 unsigned int currf
, newf
, maskf
;
2748 if (!dot_is_possible(state
, sp
, 1)) goto badmove
;
2750 newf
= F_DOT
| (c
== 'd' ? F_DOT_BLACK
: 0);
2751 currf
= GRID(ret
, grid
, x
, y
).flags
;
2752 maskf
= F_DOT
| F_DOT_BLACK
;
2753 /* if we clicked 'white dot':
2754 * white --> empty, empty --> white, black --> white.
2755 * if we clicker 'black dot':
2756 * black --> empty, empty --> black, white --> black.
2758 if (currf
& maskf
) {
2759 sp
->flags
&= ~maskf
;
2760 if ((currf
& maskf
) != newf
)
2764 sp
->nassoc
= 0; /* edit-mode disallows associations. */
2765 game_update_dots(ret
);
2769 if (sp
->type
!= s_edge
) goto badmove
;
2770 sp
->flags
^= F_EDGE_SET
;
2771 } else if (c
== 'U') {
2772 if (sp
->type
!= s_tile
|| !(sp
->flags
& F_TILE_ASSOC
))
2774 remove_assoc(ret
, sp
);
2775 } else if (c
== 'M') {
2776 if (!(sp
->flags
& F_DOT
)) goto badmove
;
2777 sp
->flags
^= F_DOT_HOLD
;
2780 } else if (c
== 'A' || c
== 'a') {
2782 if (sscanf(move
, "%d,%d,%d,%d%n", &x
, &y
, &ax
, &ay
, &n
) != 4 ||
2783 x
< 1 || y
< 1 || x
>= (state
->sx
-1) || y
>= (state
->sy
-1) ||
2784 ax
< 1 || ay
< 1 || ax
>= (state
->sx
-1) || ay
>= (state
->sy
-1))
2787 dot
= &GRID(ret
, grid
, ax
, ay
);
2788 if (!(dot
->flags
& F_DOT
))goto badmove
;
2789 if (dot
->flags
& F_DOT_HOLD
) goto badmove
;
2791 for (dx
= -1; dx
<= 1; dx
++) {
2792 for (dy
= -1; dy
<= 1; dy
++) {
2793 sp
= &GRID(ret
, grid
, x
+dx
, y
+dy
);
2794 if (sp
->type
!= s_tile
) continue;
2795 if (sp
->flags
& F_TILE_ASSOC
) {
2796 space
*dot
= &SPACE(state
, sp
->dotx
, sp
->doty
);
2797 if (dot
->flags
& F_DOT_HOLD
) continue;
2799 add_assoc(state
, sp
, dot
);
2804 } else if (c
== 'C') {
2808 } else if (c
== 'S') {
2810 ret
->used_solve
= 1;
2819 if (check_complete(ret
, NULL
, NULL
))
2828 /* ----------------------------------------------------------------------
2832 /* Lines will be much smaller size than squares; say, 1/8 the size?
2834 * Need a 'top-left corner of location XxY' to take this into account;
2835 * alternaticaly, that could give the middle of that location, and the
2836 * drawing code would just know the expected dimensions.
2838 * We also need something to take a click and work out what it was
2839 * we were interested in. Clicking on vertices is required because
2840 * we may want to drag from them, for example.
2843 static void game_compute_size(game_params
*params
, int sz
,
2846 struct { int tilesize
, w
, h
; } ads
, *ds
= &ads
;
2856 static void game_set_size(drawing
*dr
, game_drawstate
*ds
,
2857 game_params
*params
, int sz
)
2861 assert(TILE_SIZE
> 0);
2864 ds
->bl
= blitter_new(dr
, TILE_SIZE
, TILE_SIZE
);
2867 static float *game_colours(frontend
*fe
, int *ncolours
)
2869 float *ret
= snewn(3 * NCOLOURS
, float);
2873 * We call game_mkhighlight to ensure the background colour
2874 * isn't completely white. We don't actually use the high- and
2875 * lowlight colours it generates.
2877 game_mkhighlight(fe
, ret
, COL_BACKGROUND
, COL_WHITEBG
, COL_BLACKBG
);
2879 for (i
= 0; i
< 3; i
++) {
2881 * Currently, white dots and white-background squares are
2884 ret
[COL_WHITEDOT
* 3 + i
] = 1.0F
;
2885 ret
[COL_WHITEBG
* 3 + i
] = 1.0F
;
2888 * But black-background squares are a dark grey, whereas
2889 * black dots are really black.
2891 ret
[COL_BLACKDOT
* 3 + i
] = 0.0F
;
2892 ret
[COL_BLACKBG
* 3 + i
] = ret
[COL_BACKGROUND
* 3 + i
] * 0.3F
;
2895 * In unfilled squares, we draw a faint gridwork.
2897 ret
[COL_GRID
* 3 + i
] = ret
[COL_BACKGROUND
* 3 + i
] * 0.8F
;
2900 * Edges and arrows are filled in in pure black.
2902 ret
[COL_EDGE
* 3 + i
] = 0.0F
;
2903 ret
[COL_ARROW
* 3 + i
] = 0.0F
;
2907 /* tinge the edit background to bluey */
2908 ret
[COL_BACKGROUND
* 3 + 0] = ret
[COL_BACKGROUND
* 3 + 0] * 0.8F
;
2909 ret
[COL_BACKGROUND
* 3 + 1] = ret
[COL_BACKGROUND
* 3 + 0] * 0.8F
;
2910 ret
[COL_BACKGROUND
* 3 + 2] = ret
[COL_BACKGROUND
* 3 + 0] * 1.4F
;
2911 if (ret
[COL_BACKGROUND
* 3 + 2] > 1.0F
) ret
[COL_BACKGROUND
* 3 + 2] = 1.0F
;
2914 *ncolours
= NCOLOURS
;
2918 static game_drawstate
*game_new_drawstate(drawing
*dr
, game_state
*state
)
2920 struct game_drawstate
*ds
= snew(struct game_drawstate
);
2927 ds
->grid
= snewn(ds
->w
*ds
->h
, unsigned long);
2928 for (i
= 0; i
< ds
->w
*ds
->h
; i
++)
2929 ds
->grid
[i
] = 0xFFFFFFFFUL
;
2930 ds
->dx
= snewn(ds
->w
*ds
->h
, int);
2931 ds
->dy
= snewn(ds
->w
*ds
->h
, int);
2934 ds
->dragging
= FALSE
;
2935 ds
->dragx
= ds
->dragy
= 0;
2937 ds
->colour_scratch
= snewn(ds
->w
* ds
->h
, int);
2942 static void game_free_drawstate(drawing
*dr
, game_drawstate
*ds
)
2944 sfree(ds
->colour_scratch
);
2945 if (ds
->bl
) blitter_free(dr
, ds
->bl
);
2952 #define DRAW_EDGE_L 0x0001
2953 #define DRAW_EDGE_R 0x0002
2954 #define DRAW_EDGE_U 0x0004
2955 #define DRAW_EDGE_D 0x0008
2956 #define DRAW_CORNER_UL 0x0010
2957 #define DRAW_CORNER_UR 0x0020
2958 #define DRAW_CORNER_DL 0x0040
2959 #define DRAW_CORNER_DR 0x0080
2960 #define DRAW_WHITE 0x0100
2961 #define DRAW_BLACK 0x0200
2962 #define DRAW_ARROW 0x0400
2963 #define DOT_SHIFT_C 11
2964 #define DOT_SHIFT_M 2
2965 #define DOT_WHITE 1UL
2966 #define DOT_BLACK 2UL
2969 * Draw an arrow centred on (cx,cy), pointing in the direction
2970 * (ddx,ddy). (I.e. pointing at the point (cx+ddx, cy+ddy).
2972 static void draw_arrow(drawing
*dr
, game_drawstate
*ds
,
2973 int cx
, int cy
, int ddx
, int ddy
)
2975 float vlen
= (float)sqrt(ddx
*ddx
+ddy
*ddy
);
2976 float xdx
= ddx
/vlen
, xdy
= ddy
/vlen
;
2977 float ydx
= -xdy
, ydy
= xdx
;
2978 int e1x
= cx
+ (int)(xdx
*TILE_SIZE
/3), e1y
= cy
+ (int)(xdy
*TILE_SIZE
/3);
2979 int e2x
= cx
- (int)(xdx
*TILE_SIZE
/3), e2y
= cy
- (int)(xdy
*TILE_SIZE
/3);
2980 int adx
= (int)((ydx
-xdx
)*TILE_SIZE
/8), ady
= (int)((ydy
-xdy
)*TILE_SIZE
/8);
2981 int adx2
= (int)((-ydx
-xdx
)*TILE_SIZE
/8), ady2
= (int)((-ydy
-xdy
)*TILE_SIZE
/8);
2983 draw_line(dr
, e1x
, e1y
, e2x
, e2y
, COL_ARROW
);
2984 draw_line(dr
, e1x
, e1y
, e1x
+adx
, e1y
+ady
, COL_ARROW
);
2985 draw_line(dr
, e1x
, e1y
, e1x
+adx2
, e1y
+ady2
, COL_ARROW
);
2988 static void draw_square(drawing
*dr
, game_drawstate
*ds
, int x
, int y
,
2989 unsigned long flags
, int ddx
, int ddy
)
2991 int lx
= COORD(x
), ly
= COORD(y
);
2995 clip(dr
, lx
, ly
, TILE_SIZE
, TILE_SIZE
);
2998 * Draw the tile background.
3000 draw_rect(dr
, lx
, ly
, TILE_SIZE
, TILE_SIZE
,
3001 (flags
& DRAW_WHITE ? COL_WHITEBG
:
3002 flags
& DRAW_BLACK ? COL_BLACKBG
: COL_BACKGROUND
));
3007 gridcol
= (flags
& DRAW_BLACK ? COL_BLACKDOT
: COL_GRID
);
3008 draw_rect(dr
, lx
, ly
, 1, TILE_SIZE
, gridcol
);
3009 draw_rect(dr
, lx
, ly
, TILE_SIZE
, 1, gridcol
);
3014 if (flags
& DRAW_ARROW
)
3015 draw_arrow(dr
, ds
, lx
+ TILE_SIZE
/2, ly
+ TILE_SIZE
/2, ddx
, ddy
);
3020 if (flags
& DRAW_EDGE_L
)
3021 draw_rect(dr
, lx
, ly
, EDGE_THICKNESS
, TILE_SIZE
, COL_EDGE
);
3022 if (flags
& DRAW_EDGE_R
)
3023 draw_rect(dr
, lx
+ TILE_SIZE
- EDGE_THICKNESS
+ 1, ly
,
3024 EDGE_THICKNESS
- 1, TILE_SIZE
, COL_EDGE
);
3025 if (flags
& DRAW_EDGE_U
)
3026 draw_rect(dr
, lx
, ly
, TILE_SIZE
, EDGE_THICKNESS
, COL_EDGE
);
3027 if (flags
& DRAW_EDGE_D
)
3028 draw_rect(dr
, lx
, ly
+ TILE_SIZE
- EDGE_THICKNESS
+ 1,
3029 TILE_SIZE
, EDGE_THICKNESS
- 1, COL_EDGE
);
3030 if (flags
& DRAW_CORNER_UL
)
3031 draw_rect(dr
, lx
, ly
, EDGE_THICKNESS
, EDGE_THICKNESS
, COL_EDGE
);
3032 if (flags
& DRAW_CORNER_UR
)
3033 draw_rect(dr
, lx
+ TILE_SIZE
- EDGE_THICKNESS
+ 1, ly
,
3034 EDGE_THICKNESS
- 1, EDGE_THICKNESS
, COL_EDGE
);
3035 if (flags
& DRAW_CORNER_DL
)
3036 draw_rect(dr
, lx
, ly
+ TILE_SIZE
- EDGE_THICKNESS
+ 1,
3037 EDGE_THICKNESS
, EDGE_THICKNESS
- 1, COL_EDGE
);
3038 if (flags
& DRAW_CORNER_DR
)
3039 draw_rect(dr
, lx
+ TILE_SIZE
- EDGE_THICKNESS
+ 1,
3040 ly
+ TILE_SIZE
- EDGE_THICKNESS
+ 1,
3041 EDGE_THICKNESS
- 1, EDGE_THICKNESS
- 1, COL_EDGE
);
3046 for (dy
= 0; dy
< 3; dy
++)
3047 for (dx
= 0; dx
< 3; dx
++) {
3048 int dotval
= (flags
>> (DOT_SHIFT_C
+ DOT_SHIFT_M
*(dy
*3+dx
)));
3049 dotval
&= (1 << DOT_SHIFT_M
)-1;
3052 draw_circle(dr
, lx
+dx
*TILE_SIZE
/2, ly
+dy
*TILE_SIZE
/2,
3054 (dotval
== 1 ? COL_WHITEDOT
: COL_BLACKDOT
),
3059 draw_update(dr
, lx
, ly
, TILE_SIZE
, TILE_SIZE
);
3062 static void game_redraw(drawing
*dr
, game_drawstate
*ds
, game_state
*oldstate
,
3063 game_state
*state
, int dir
, game_ui
*ui
,
3064 float animtime
, float flashtime
)
3066 int w
= ds
->w
, h
= ds
->h
;
3067 int x
, y
, flashing
= FALSE
;
3069 if (flashtime
> 0) {
3070 int frame
= (int)(flashtime
/ FLASH_TIME
);
3071 flashing
= (frame
% 2 == 0);
3076 blitter_load(dr
, ds
->bl
, ds
->dragx
, ds
->dragy
);
3077 draw_update(dr
, ds
->dragx
, ds
->dragy
, TILE_SIZE
, TILE_SIZE
);
3078 ds
->dragging
= FALSE
;
3082 draw_rect(dr
, 0, 0, DRAW_WIDTH
, DRAW_HEIGHT
, COL_BACKGROUND
);
3083 draw_rect(dr
, BORDER
- EDGE_THICKNESS
+ 1, BORDER
- EDGE_THICKNESS
+ 1,
3084 w
*TILE_SIZE
+ EDGE_THICKNESS
*2 - 1,
3085 h
*TILE_SIZE
+ EDGE_THICKNESS
*2 - 1, COL_EDGE
);
3086 draw_update(dr
, 0, 0, DRAW_WIDTH
, DRAW_HEIGHT
);
3090 check_complete(state
, NULL
, ds
->colour_scratch
);
3092 for (y
= 0; y
< h
; y
++)
3093 for (x
= 0; x
< w
; x
++) {
3094 unsigned long flags
= 0;
3095 int ddx
= 0, ddy
= 0;
3100 * Set up the flags for this square. Firstly, see if we
3103 if (SPACE(state
, x
*2, y
*2+1).flags
& F_EDGE_SET
)
3104 flags
|= DRAW_EDGE_L
;
3105 if (SPACE(state
, x
*2+2, y
*2+1).flags
& F_EDGE_SET
)
3106 flags
|= DRAW_EDGE_R
;
3107 if (SPACE(state
, x
*2+1, y
*2).flags
& F_EDGE_SET
)
3108 flags
|= DRAW_EDGE_U
;
3109 if (SPACE(state
, x
*2+1, y
*2+2).flags
& F_EDGE_SET
)
3110 flags
|= DRAW_EDGE_D
;
3113 * Also, mark corners of neighbouring edges.
3115 if ((x
> 0 && SPACE(state
, x
*2-1, y
*2).flags
& F_EDGE_SET
) ||
3116 (y
> 0 && SPACE(state
, x
*2, y
*2-1).flags
& F_EDGE_SET
))
3117 flags
|= DRAW_CORNER_UL
;
3118 if ((x
+1 < w
&& SPACE(state
, x
*2+3, y
*2).flags
& F_EDGE_SET
) ||
3119 (y
> 0 && SPACE(state
, x
*2+2, y
*2-1).flags
& F_EDGE_SET
))
3120 flags
|= DRAW_CORNER_UR
;
3121 if ((x
> 0 && SPACE(state
, x
*2-1, y
*2+2).flags
& F_EDGE_SET
) ||
3122 (y
+1 < h
&& SPACE(state
, x
*2, y
*2+3).flags
& F_EDGE_SET
))
3123 flags
|= DRAW_CORNER_DL
;
3124 if ((x
+1 < w
&& SPACE(state
, x
*2+3, y
*2+2).flags
& F_EDGE_SET
) ||
3125 (y
+1 < h
&& SPACE(state
, x
*2+2, y
*2+3).flags
& F_EDGE_SET
))
3126 flags
|= DRAW_CORNER_DR
;
3129 * If this square is part of a valid region, paint it
3130 * that region's colour. Exception: if we're flashing,
3131 * everything goes briefly back to background colour.
3133 sp
= &SPACE(state
, x
*2+1, y
*2+1);
3134 if (ds
->colour_scratch
[y
*w
+x
] && !flashing
) {
3135 flags
|= (ds
->colour_scratch
[y
*w
+x
] == 2 ?
3136 DRAW_BLACK
: DRAW_WHITE
);
3140 * If this square is associated with a dot but it isn't
3141 * part of a valid region, draw an arrow in it pointing
3142 * in the direction of that dot.
3144 * Exception: if this is the source point of an active
3145 * drag, we don't draw the arrow.
3147 if ((sp
->flags
& F_TILE_ASSOC
) && !ds
->colour_scratch
[y
*w
+x
]) {
3148 if (ui
->dragging
&& ui
->srcx
== x
*2+1 && ui
->srcy
== y
*2+1) {
3150 } else if (sp
->doty
!= y
*2+1 || sp
->dotx
!= x
*2+1) {
3151 flags
|= DRAW_ARROW
;
3152 ddy
= sp
->doty
- (y
*2+1);
3153 ddx
= sp
->dotx
- (x
*2+1);
3158 * Now go through the nine possible places we could
3161 for (dy
= 0; dy
< 3; dy
++)
3162 for (dx
= 0; dx
< 3; dx
++) {
3163 sp
= &SPACE(state
, x
*2+dx
, y
*2+dy
);
3164 if (sp
->flags
& F_DOT
) {
3165 unsigned long dotval
= (sp
->flags
& F_DOT_BLACK ?
3166 DOT_BLACK
: DOT_WHITE
);
3167 flags
|= dotval
<< (DOT_SHIFT_C
+
3168 DOT_SHIFT_M
*(dy
*3+dx
));
3173 * Now we have everything we're going to need. Draw the
3176 if (ds
->grid
[y
*w
+x
] != flags
||
3177 ds
->dx
[y
*w
+x
] != ddx
||
3178 ds
->dy
[y
*w
+x
] != ddy
) {
3179 draw_square(dr
, ds
, x
, y
, flags
, ddx
, ddy
);
3180 ds
->grid
[y
*w
+x
] = flags
;
3181 ds
->dx
[y
*w
+x
] = ddx
;
3182 ds
->dy
[y
*w
+x
] = ddy
;
3187 ds
->dragging
= TRUE
;
3188 ds
->dragx
= ui
->dx
- TILE_SIZE
/2;
3189 ds
->dragy
= ui
->dy
- TILE_SIZE
/2;
3190 blitter_save(dr
, ds
->bl
, ds
->dragx
, ds
->dragy
);
3191 draw_arrow(dr
, ds
, ui
->dx
, ui
->dy
,
3192 SCOORD(ui
->dotx
) - ui
->dx
,
3193 SCOORD(ui
->doty
) - ui
->dy
);
3198 if (state
->cdiff
!= -1)
3199 sprintf(buf
, "Puzzle is %s.", galaxies_diffnames
[state
->cdiff
]);
3202 status_bar(dr
, buf
);
3207 static float game_anim_length(game_state
*oldstate
, game_state
*newstate
,
3208 int dir
, game_ui
*ui
)
3213 static float game_flash_length(game_state
*oldstate
, game_state
*newstate
,
3214 int dir
, game_ui
*ui
)
3216 if ((!oldstate
->completed
&& newstate
->completed
) &&
3217 !(newstate
->used_solve
))
3218 return 3 * FLASH_TIME
;
3223 static int game_timing_state(game_state
*state
, game_ui
*ui
)
3229 static void game_print_size(game_params
*params
, float *x
, float *y
)
3234 * 8mm squares by default. (There isn't all that much detail
3235 * that needs to go in each square.)
3237 game_compute_size(params
, 800, &pw
, &ph
);
3242 static void game_print(drawing
*dr
, game_state
*state
, int sz
)
3244 int w
= state
->w
, h
= state
->h
;
3245 int white
, black
, blackish
;
3249 int ncoords
= 0, coordsize
= 0;
3251 /* Ick: fake up `ds->tilesize' for macro expansion purposes */
3252 game_drawstate ads
, *ds
= &ads
;
3255 white
= print_grey_colour(dr
, HATCH_CLEAR
, 1.0F
);
3256 black
= print_grey_colour(dr
, HATCH_SOLID
, 0.0F
);
3257 blackish
= print_grey_colour(dr
, HATCH_X
, 0.5F
);
3260 * Get the completion information.
3262 dsf
= snewn(w
* h
, int);
3263 colours
= snewn(w
* h
, int);
3264 check_complete(state
, dsf
, colours
);
3269 print_line_width(dr
, TILE_SIZE
/ 64);
3270 for (x
= 1; x
< w
; x
++)
3271 draw_line(dr
, COORD(x
), COORD(0), COORD(x
), COORD(h
), black
);
3272 for (y
= 1; y
< h
; y
++)
3273 draw_line(dr
, COORD(0), COORD(y
), COORD(w
), COORD(y
), black
);
3276 * Shade the completed regions. Just in case any particular
3277 * printing platform deals badly with adjacent
3278 * similarly-hatched regions, we'll fill each one as a single
3281 for (i
= 0; i
< w
*h
; i
++) {
3282 j
= dsf_canonify(dsf
, i
);
3283 if (colours
[j
] != 0) {
3287 * This is the first square we've run into belonging to
3288 * this polyomino, which means an edge of the polyomino
3289 * is certain to be to our left. (After we finish
3290 * tracing round it, we'll set the colours[] entry to
3291 * zero to prevent accidentally doing it again.)
3301 * We are currently sitting on square (x,y), which
3302 * we know to be in our polyomino, and we also know
3303 * that (x+dx,y+dy) is not. The way I visualise
3304 * this is that we're standing to the right of a
3305 * boundary line, stretching our left arm out to
3306 * point to the exterior square on the far side.
3310 * First, check if we've gone round the entire
3314 (x
== i
%w
&& y
== i
/w
&& dx
== -1 && dy
== 0))
3318 * Add to our coordinate list the coordinate
3319 * backwards and to the left of where we are.
3321 if (ncoords
+ 2 > coordsize
) {
3322 coordsize
= (ncoords
* 3 / 2) + 64;
3323 coords
= sresize(coords
, coordsize
, int);
3325 coords
[ncoords
++] = COORD((2*x
+1 + dx
+ dy
) / 2);
3326 coords
[ncoords
++] = COORD((2*y
+1 + dy
- dx
) / 2);
3329 * Follow the edge round. If the square directly in
3330 * front of us is not part of the polyomino, we
3331 * turn right; if it is and so is the square in
3332 * front of (x+dx,y+dy), we turn left; otherwise we
3335 if (x
-dy
< 0 || x
-dy
>= w
|| y
+dx
< 0 || y
+dx
>= h
||
3336 dsf_canonify(dsf
, (y
+dx
)*w
+(x
-dy
)) != j
) {
3341 } else if (x
+dx
-dy
>= 0 && x
+dx
-dy
< w
&&
3342 y
+dy
+dx
>= 0 && y
+dy
+dx
< h
&&
3343 dsf_canonify(dsf
, (y
+dy
+dx
)*w
+(x
+dx
-dy
)) == j
) {
3360 * Now we have our polygon complete, so fill it.
3362 draw_polygon(dr
, coords
, ncoords
/2,
3363 colours
[j
] == 2 ? blackish
: -1, black
);
3366 * And mark this polyomino as done.
3375 for (y
= 0; y
<= h
; y
++)
3376 for (x
= 0; x
<= w
; x
++) {
3377 if (x
< w
&& SPACE(state
, x
*2+1, y
*2).flags
& F_EDGE_SET
)
3378 draw_rect(dr
, COORD(x
)-EDGE_THICKNESS
, COORD(y
)-EDGE_THICKNESS
,
3379 EDGE_THICKNESS
* 2 + TILE_SIZE
, EDGE_THICKNESS
* 2,
3381 if (y
< h
&& SPACE(state
, x
*2, y
*2+1).flags
& F_EDGE_SET
)
3382 draw_rect(dr
, COORD(x
)-EDGE_THICKNESS
, COORD(y
)-EDGE_THICKNESS
,
3383 EDGE_THICKNESS
* 2, EDGE_THICKNESS
* 2 + TILE_SIZE
,
3390 for (y
= 0; y
<= 2*h
; y
++)
3391 for (x
= 0; x
<= 2*w
; x
++)
3392 if (SPACE(state
, x
, y
).flags
& F_DOT
) {
3393 draw_circle(dr
, (int)COORD(x
/2.0), (int)COORD(y
/2.0), DOT_SIZE
,
3394 (SPACE(state
, x
, y
).flags
& F_DOT_BLACK ?
3395 black
: white
), black
);
3405 #define thegame galaxies
3408 const struct game thegame
= {
3409 "Galaxies", "games.galaxies", "galaxies",
3416 TRUE
, game_configure
, custom_params
,
3428 TRUE
, game_text_format
,
3436 PREFERRED_TILE_SIZE
, game_compute_size
, game_set_size
,
3439 game_free_drawstate
,
3444 FALSE
, FALSE
, NULL
, NULL
,
3445 TRUE
, /* wants_statusbar */
3447 TRUE
, FALSE
, game_print_size
, game_print
,
3448 FALSE
, /* wants_statusbar */
3450 FALSE
, game_timing_state
,
3451 REQUIRE_RBUTTON
, /* flags */
3454 #ifdef STANDALONE_SOLVER
3460 static void usage_exit(const char *msg
)
3463 fprintf(stderr
, "%s: %s\n", quis
, msg
);
3464 fprintf(stderr
, "Usage: %s [--seed SEED] --soak <params> | [game_id [game_id ...]]\n", quis
);
3468 static void dump_state(game_state
*state
)
3470 char *temp
= game_text_format(state
);
3471 printf("%s\n", temp
);
3475 static int gen(game_params
*p
, random_state
*rs
, int debug
)
3482 solver_show_working
= debug
;
3484 printf("Generating a %dx%d %s puzzle.\n",
3485 p
->w
, p
->h
, galaxies_diffnames
[p
->diff
]);
3487 desc
= new_game_desc(p
, rs
, NULL
, 0);
3488 state
= new_game(NULL
, p
, desc
);
3491 diff
= solver_state(state
, DIFF_UNREASONABLE
);
3492 printf("Generated %s game %dx%d:%s\n",
3493 galaxies_diffnames
[diff
], p
->w
, p
->h
, desc
);
3502 static void soak(game_params
*p
, random_state
*rs
)
3504 time_t tt_start
, tt_now
, tt_last
;
3507 int diff
, n
= 0, i
, diffs
[DIFF_MAX
], ndots
= 0, nspaces
= 0;
3510 solver_show_working
= 0;
3512 tt_start
= tt_now
= time(NULL
);
3513 for (i
= 0; i
< DIFF_MAX
; i
++) diffs
[i
] = 0;
3516 printf("Soak-generating a %dx%d grid, max. diff %s.\n",
3517 p
->w
, p
->h
, galaxies_diffnames
[p
->diff
]);
3519 for (i
= 0; i
< DIFF_MAX
; i
++)
3520 printf("%s%s", (i
== 0) ?
"" : ", ", galaxies_diffnames
[i
]);
3524 desc
= new_game_desc(p
, rs
, NULL
, 0);
3525 st
= new_game(NULL
, p
, desc
);
3526 diff
= solver_state(st
, p
->diff
);
3527 nspaces
+= st
->w
*st
->h
;
3528 for (i
= 0; i
< st
->sx
*st
->sy
; i
++)
3529 if (st
->grid
[i
].flags
& F_DOT
) ndots
++;
3535 tt_last
= time(NULL
);
3536 if (tt_last
> tt_now
) {
3538 printf("%d total, %3.1f/s, [",
3539 n
, (double)n
/ ((double)tt_now
- tt_start
));
3540 for (i
= 0; i
< DIFF_MAX
; i
++)
3541 printf("%s%.1f%%", (i
== 0) ?
"" : ", ",
3542 100.0 * ((double)diffs
[i
] / (double)n
));
3543 printf("], %.1f%% dots\n",
3544 100.0 * ((double)ndots
/ (double)nspaces
));
3549 int main(int argc
, char **argv
)
3552 char *id
= NULL
, *desc
, *err
;
3554 int diff
, do_soak
= 0, verbose
= 0;
3556 time_t seed
= time(NULL
);
3559 while (--argc
> 0) {
3561 if (!strcmp(p
, "-v")) {
3563 } else if (!strcmp(p
, "--seed")) {
3564 if (argc
== 0) usage_exit("--seed needs an argument");
3565 seed
= (time_t)atoi(*++argv
);
3567 } else if (!strcmp(p
, "--soak")) {
3569 } else if (*p
== '-') {
3570 usage_exit("unrecognised option");
3578 p
= default_params();
3579 rs
= random_new((void*)&seed
, sizeof(time_t));
3582 if (!id
) usage_exit("need one argument for --soak");
3583 decode_params(p
, *argv
);
3590 p
->w
= random_upto(rs
, 15) + 3;
3591 p
->h
= random_upto(rs
, 15) + 3;
3592 p
->diff
= random_upto(rs
, DIFF_UNREASONABLE
);
3593 diff
= gen(p
, rs
, 0);
3598 desc
= strchr(id
, ':');
3600 decode_params(p
, id
);
3601 gen(p
, rs
, verbose
);
3604 solver_show_working
= 1;
3607 decode_params(p
, id
);
3608 err
= validate_desc(p
, desc
);
3610 fprintf(stderr
, "%s: %s\n", argv
[0], err
);
3613 s
= new_game(NULL
, p
, desc
);
3614 diff
= solver_state(s
, DIFF_UNREASONABLE
);
3616 printf("Puzzle is %s.\n", galaxies_diffnames
[diff
]);
3627 #ifdef STANDALONE_PICTURE_GENERATOR
3630 * Main program for the standalone picture generator. To use it,
3631 * simply provide it with an XBM-format bitmap file (note XBM, not
3632 * XPM) on standard input, and it will output a game ID in return.
3635 * $ ./galaxiespicture < badly-drawn-cat.xbm
3636 * 11x11:eloMBLzFeEzLNMWifhaWYdDbixCymBbBMLoDdewGg
3638 * If you want a puzzle with a non-standard difficulty level, pass
3639 * a partial parameters string as a command-line argument (e.g.
3640 * `./galaxiespicture du < foo.xbm', where `du' is the same suffix
3641 * which if it appeared in a random-seed game ID would set the
3642 * difficulty level to Unreasonable). However, be aware that if the
3643 * generator fails to produce an adequately difficult puzzle too
3644 * many times then it will give up and return an easier one (just
3645 * as it does during normal GUI play). To be sure you really have
3646 * the difficulty you asked for, use galaxiessolver to
3649 * (Perhaps I ought to include an option to make this standalone
3650 * generator carry on looping until it really does get the right
3651 * difficulty. Hmmm.)
3656 int main(int argc
, char **argv
)
3659 char *params
, *desc
;
3661 time_t seed
= time(NULL
);
3666 par
= default_params();
3668 decode_params(par
, argv
[1]); /* get difficulty */
3669 par
->w
= par
->h
= -1;
3672 * Now read an XBM file from standard input. This is simple and
3673 * hacky and will do very little error detection, so don't feed
3678 while (fgets(buf
, sizeof(buf
), stdin
)) {
3679 buf
[strcspn(buf
, "\r\n")] = '\0';
3680 if (!strncmp(buf
, "#define", 7)) {
3682 * Lines starting `#define' give the width and height.
3684 char *num
= buf
+ strlen(buf
);
3687 while (num
> buf
&& isdigit((unsigned char)num
[-1]))
3690 while (symend
> buf
&& isspace((unsigned char)symend
[-1]))
3693 if (symend
-5 >= buf
&& !strncmp(symend
-5, "width", 5))
3695 else if (symend
-6 >= buf
&& !strncmp(symend
-6, "height", 6))
3699 * Otherwise, break the string up into words and take
3700 * any word of the form `0x' plus hex digits to be a
3703 char *p
, *wordstart
;
3706 if (par
->w
< 0 || par
->h
< 0) {
3707 printf("failed to read width and height\n");
3710 picture
= snewn(par
->w
* par
->h
, int);
3711 for (i
= 0; i
< par
->w
* par
->h
; i
++)
3717 while (*p
&& (*p
== ',' || isspace((unsigned char)*p
)))
3720 while (*p
&& !(*p
== ',' || *p
== '}' ||
3721 isspace((unsigned char)*p
)))
3726 if (wordstart
[0] == '0' &&
3727 (wordstart
[1] == 'x' || wordstart
[1] == 'X') &&
3728 !wordstart
[2 + strspn(wordstart
+2,
3729 "0123456789abcdefABCDEF")]) {
3730 unsigned long byte
= strtoul(wordstart
+2, NULL
, 16);
3731 for (i
= 0; i
< 8; i
++) {
3732 int bit
= (byte
>> i
) & 1;
3733 if (y
< par
->h
&& x
< par
->w
)
3734 picture
[y
* par
->w
+ x
] = bit
;
3747 for (i
= 0; i
< par
->w
* par
->h
; i
++)
3748 if (picture
[i
] < 0) {
3749 fprintf(stderr
, "failed to read enough bitmap data\n");
3753 rs
= random_new((void*)&seed
, sizeof(time_t));
3755 desc
= new_game_desc(par
, rs
, NULL
, FALSE
);
3756 params
= encode_params(par
, FALSE
);
3757 printf("%s:%s\n", params
, desc
);
3769 /* vim: set shiftwidth=4 tabstop=8: */