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
90 A(UNREASONABLE,Unreasonable,u)
92 #define ENUM(upper,title,lower) DIFF_ ## upper,
93 #define TITLE(upper,title,lower) #title,
94 #define ENCODE(upper,title,lower) #lower
95 #define CONFIG(upper,title,lower) ":" #title
97 DIFF_IMPOSSIBLE, DIFF_AMBIGUOUS, DIFF_UNFINISHED, DIFF_MAX };
98 static char const *const galaxies_diffnames[] = {
99 DIFFLIST(TITLE) "Impossible", "Ambiguous", "Unfinished" };
100 static char const galaxies_diffchars[] = DIFFLIST(ENCODE);
101 #define DIFFCONFIG DIFFLIST(CONFIG)
104 /* X and Y is the area of the board as seen by
105 * the user, not the (2n+1) area the game uses. */
109 enum { s_tile, s_edge, s_vertex };
111 #define F_DOT 1 /* there's a dot here */
112 #define F_EDGE_SET 2 /* the edge is set */
113 #define F_TILE_ASSOC 4 /* this tile is associated with a dot. */
114 #define F_DOT_BLACK 8 /* (ui only) dot is black. */
115 #define F_MARK 16 /* scratch flag */
116 #define F_REACHABLE 32
118 #define F_MULTIPLE 128
119 #define F_DOT_HOLD 256
122 typedef struct space {
123 int x, y; /* its position */
126 int dotx, doty; /* if flags & F_TILE_ASSOC */
127 int nassoc; /* if flags & F_DOT */
130 #define INGRID(s,x,y) ((x) >= 0 && (y) >= 0 && \
131 (x) < (state)->sx && (y) < (state)->sy)
132 #define INUI(s,x,y) ((x) > 0 && (y) > 0 && \
133 (x) < ((state)->sx-1) && (y) < ((state)->sy-1))
135 #define GRID(s,g,x,y) ((s)->g[((y)*(s)->sx)+(x)])
136 #define SPACE(s,x,y) GRID(s,grid,x,y)
139 int w, h; /* size from params */
140 int sx, sy; /* allocated size, (2x-1)*(2y-1) */
142 int completed, used_solve;
146 midend *me; /* to call supersede_game_desc */
147 int cdiff; /* difficulty of current puzzle (for status bar),
151 static int check_complete(const game_state *state, int *dsf, int *colours);
152 static int solver_state(game_state *state, int maxdiff);
153 static int solver_obvious(game_state *state);
154 static int solver_obvious_dot(game_state *state, space *dot);
155 static space *space_opposite_dot(const game_state *state, const space *sp,
157 static space *tile_opposite(const game_state *state, const space *sp);
159 /* ----------------------------------------------------------
160 * Game parameters and presets
163 /* make up some sensible default sizes */
165 #define DEFAULT_PRESET 0
167 static const game_params galaxies_presets[] = {
168 { 7, 7, DIFF_NORMAL },
169 { 7, 7, DIFF_UNREASONABLE },
170 { 10, 10, DIFF_NORMAL },
171 { 15, 15, DIFF_NORMAL },
174 static int game_fetch_preset(int i, char **name, game_params **params)
179 if (i < 0 || i >= lenof(galaxies_presets))
182 ret = snew(game_params);
183 *ret = galaxies_presets[i]; /* structure copy */
185 sprintf(buf, "%dx%d %s", ret->w, ret->h,
186 galaxies_diffnames[ret->diff]);
188 if (name) *name = dupstr(buf);
193 static game_params *default_params(void)
196 game_fetch_preset(DEFAULT_PRESET, NULL, &ret);
200 static void free_params(game_params *params)
205 static game_params *dup_params(const game_params *params)
207 game_params *ret = snew(game_params);
208 *ret = *params; /* structure copy */
212 static void decode_params(game_params *params, char const *string)
214 params->h = params->w = atoi(string);
215 params->diff = DIFF_NORMAL;
216 while (*string && isdigit((unsigned char)*string)) string++;
217 if (*string == 'x') {
219 params->h = atoi(string);
220 while (*string && isdigit((unsigned char)*string)) string++;
222 if (*string == 'd') {
225 for (i = 0; i <= DIFF_UNREASONABLE; i++)
226 if (*string == galaxies_diffchars[i])
228 if (*string) string++;
232 static char *encode_params(const game_params *params, int full)
235 sprintf(str, "%dx%d", params->w, params->h);
237 sprintf(str + strlen(str), "d%c", galaxies_diffchars[params->diff]);
241 static config_item *game_configure(const game_params *params)
246 ret = snewn(4, config_item);
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);
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);
258 ret[2].name = "Difficulty";
259 ret[2].type = C_CHOICES;
260 ret[2].u.choices.choicenames = DIFFCONFIG;
261 ret[2].u.choices.selected = params->diff;
269 static game_params *custom_params(const config_item *cfg)
271 game_params *ret = snew(game_params);
273 ret->w = atoi(cfg[0].u.string.sval);
274 ret->h = atoi(cfg[1].u.string.sval);
275 ret->diff = cfg[2].u.choices.selected;
280 static const char *validate_params(const game_params *params, int full)
282 if (params->w < 3 || params->h < 3)
283 return "Width and height must both be at least 3";
285 * This shouldn't be able to happen at all, since decode_params
286 * and custom_params will never generate anything that isn't
289 assert(params->diff <= DIFF_UNREASONABLE);
294 /* ----------------------------------------------------------
295 * Game utility functions.
298 static void add_dot(space *space) {
299 assert(!(space->flags & F_DOT));
300 space->flags |= F_DOT;
304 static void remove_dot(space *space) {
305 assert(space->flags & F_DOT);
306 space->flags &= ~F_DOT;
309 static void remove_assoc(const game_state *state, space *tile) {
310 if (tile->flags & F_TILE_ASSOC) {
311 SPACE(state, tile->dotx, tile->doty).nassoc--;
312 tile->flags &= ~F_TILE_ASSOC;
318 static void remove_assoc_with_opposite(game_state *state, space *tile) {
321 if (!(tile->flags & F_TILE_ASSOC)) {
325 opposite = tile_opposite(state, tile);
326 remove_assoc(state, tile);
328 if (opposite != NULL && opposite != tile) {
329 remove_assoc(state, opposite);
333 static void add_assoc(const game_state *state, space *tile, space *dot) {
334 remove_assoc(state, tile);
336 #ifdef STANDALONE_PICTURE_GENERATOR
338 assert(!picture[(tile->y/2) * state->w + (tile->x/2)] ==
339 !(dot->flags & F_DOT_BLACK));
341 tile->flags |= F_TILE_ASSOC;
345 /*debug(("add_assoc sp %d %d --> dot %d,%d, new nassoc %d.\n",
346 tile->x, tile->y, dot->x, dot->y, dot->nassoc));*/
349 static void add_assoc_with_opposite(game_state *state, space *tile, space *dot) {
351 space *opposite = space_opposite_dot(state, tile, dot);
353 if (opposite == NULL) {
356 if (opposite->flags & F_DOT) {
360 colors = snewn(state->w * state->h, int);
361 check_complete(state, NULL, colors);
362 if (colors[(tile->y - 1)/2 * state->w + (tile->x - 1)/2]) {
366 if (colors[(opposite->y - 1)/2 * state->w + (opposite->x - 1)/2]) {
372 remove_assoc_with_opposite(state, tile);
373 add_assoc(state, tile, dot);
374 remove_assoc_with_opposite(state, opposite);
375 add_assoc(state, opposite, dot);
378 static space *sp2dot(const game_state *state, int x, int y)
380 space *sp = &SPACE(state, x, y);
381 if (!(sp->flags & F_TILE_ASSOC)) return NULL;
382 return &SPACE(state, sp->dotx, sp->doty);
385 #define IS_VERTICAL_EDGE(x) ((x % 2) == 0)
387 static int game_can_format_as_text_now(const game_params *params)
392 static char *game_text_format(const game_state *state)
394 int maxlen = (state->sx+1)*state->sy, x, y;
398 ret = snewn(maxlen+1, char);
401 for (y = 0; y < state->sy; y++) {
402 for (x = 0; x < state->sx; x++) {
403 sp = &SPACE(state, x, y);
404 if (sp->flags & F_DOT)
407 else if (sp->flags & (F_REACHABLE|F_MULTIPLE|F_MARK))
408 *p++ = (sp->flags & F_MULTIPLE) ? 'M' :
409 (sp->flags & F_REACHABLE) ? 'R' : 'X';
414 if (sp->flags & F_TILE_ASSOC) {
415 space *dot = sp2dot(state, sp->x, sp->y);
416 if (dot && dot->flags & F_DOT)
417 *p++ = (dot->flags & F_DOT_BLACK) ? 'B' : 'W';
419 *p++ = '?'; /* association with not-a-dot. */
429 if (sp->flags & F_EDGE_SET)
430 *p++ = (IS_VERTICAL_EDGE(x)) ? '|' : '-';
436 assert(!"shouldn't get here!");
443 assert(p - ret == maxlen);
449 static void dbg_state(const game_state *state)
452 char *temp = game_text_format(state);
453 debug(("%s\n", temp));
458 /* Space-enumeration callbacks should all return 1 for 'progress made',
459 * -1 for 'impossible', and 0 otherwise. */
460 typedef int (*space_cb)(game_state *state, space *sp, void *ctx);
462 #define IMPOSSIBLE_QUITS 1
464 static int foreach_sub(game_state *state, space_cb cb, unsigned int f,
465 void *ctx, int startx, int starty)
467 int x, y, progress = 0, impossible = 0, ret;
470 for (y = starty; y < state->sy; y += 2) {
471 sp = &SPACE(state, startx, y);
472 for (x = startx; x < state->sx; x += 2) {
473 ret = cb(state, sp, ctx);
475 if (f & IMPOSSIBLE_QUITS) return -1;
477 } else if (ret == 1) {
483 return impossible ? -1 : progress;
486 static int foreach_tile(game_state *state, space_cb cb, unsigned int f,
489 return foreach_sub(state, cb, f, ctx, 1, 1);
492 static int foreach_edge(game_state *state, space_cb cb, unsigned int f,
497 ret1 = foreach_sub(state, cb, f, ctx, 0, 1);
498 ret2 = foreach_sub(state, cb, f, ctx, 1, 0);
500 if (ret1 == -1 || ret2 == -1) return -1;
501 return (ret1 || ret2) ? 1 : 0;
505 static int foreach_vertex(game_state *state, space_cb cb, unsigned int f,
508 return foreach_sub(state, cb, f, ctx, 0, 0);
513 static int is_same_assoc(game_state *state,
514 int x1, int y1, int x2, int y2)
518 if (!INGRID(state, x1, y1) || !INGRID(state, x2, y2))
521 s1 = &SPACE(state, x1, y1);
522 s2 = &SPACE(state, x2, y2);
523 assert(s1->type == s_tile && s2->type == s_tile);
524 if ((s1->flags & F_TILE_ASSOC) && (s2->flags & F_TILE_ASSOC) &&
525 s1->dotx == s2->dotx && s1->doty == s2->doty)
527 return 0; /* 0 if not same or not both associated. */
532 static int edges_into_vertex(game_state *state,
535 int dx, dy, nx, ny, count = 0;
537 assert(SPACE(state, x, y).type == s_vertex);
538 for (dx = -1; dx <= 1; dx++) {
539 for (dy = -1; dy <= 1; dy++) {
540 if (dx != 0 && dy != 0) continue;
541 if (dx == 0 && dy == 0) continue;
543 nx = x+dx; ny = y+dy;
544 if (!INGRID(state, nx, ny)) continue;
545 assert(SPACE(state, nx, ny).type == s_edge);
546 if (SPACE(state, nx, ny).flags & F_EDGE_SET)
554 static space *space_opposite_dot(const game_state *state, const space *sp,
564 if (!INGRID(state, tx, ty)) return NULL;
566 sp2 = &SPACE(state, tx, ty);
567 assert(sp2->type == sp->type);
571 static space *tile_opposite(const game_state *state, const space *sp)
575 assert(sp->flags & F_TILE_ASSOC);
576 dot = &SPACE(state, sp->dotx, sp->doty);
577 return space_opposite_dot(state, sp, dot);
580 static int dotfortile(game_state *state, space *tile, space *dot)
582 space *tile_opp = space_opposite_dot(state, tile, dot);
584 if (!tile_opp) return 0; /* opposite would be off grid */
585 if (tile_opp->flags & F_TILE_ASSOC &&
586 (tile_opp->dotx != dot->x || tile_opp->doty != dot->y))
587 return 0; /* opposite already associated with diff. dot */
591 static void adjacencies(game_state *state, space *sp, space **a1s, space **a2s)
593 int dxs[4] = {-1, 1, 0, 0}, dys[4] = {0, 0, -1, 1};
596 /* this function needs optimising. */
598 for (n = 0; n < 4; n++) {
602 if (INGRID(state, x, y)) {
603 a1s[n] = &SPACE(state, x, y);
605 x += dxs[n]; y += dys[n];
607 if (INGRID(state, x, y))
608 a2s[n] = &SPACE(state, x, y);
612 a1s[n] = a2s[n] = NULL;
617 static int outline_tile_fordot(game_state *state, space *tile, int mark)
619 space *tadj[4], *eadj[4];
620 int i, didsth = 0, edge, same;
622 assert(tile->type == s_tile);
623 adjacencies(state, tile, eadj, tadj);
624 for (i = 0; i < 4; i++) {
625 if (!eadj[i]) continue;
627 edge = (eadj[i]->flags & F_EDGE_SET) ? 1 : 0;
629 if (!(tile->flags & F_TILE_ASSOC))
630 same = (tadj[i]->flags & F_TILE_ASSOC) ? 0 : 1;
632 same = ((tadj[i]->flags & F_TILE_ASSOC) &&
633 tile->dotx == tadj[i]->dotx &&
634 tile->doty == tadj[i]->doty) ? 1 : 0;
638 if (!edge && !same) {
639 if (mark) eadj[i]->flags |= F_EDGE_SET;
641 } else if (edge && same) {
642 if (mark) eadj[i]->flags &= ~F_EDGE_SET;
649 static void tiles_from_edge(game_state *state, space *sp, space **ts)
653 if (IS_VERTICAL_EDGE(sp->x)) {
654 xs[0] = sp->x-1; ys[0] = sp->y;
655 xs[1] = sp->x+1; ys[1] = sp->y;
657 xs[0] = sp->x; ys[0] = sp->y-1;
658 xs[1] = sp->x; ys[1] = sp->y+1;
660 ts[0] = INGRID(state, xs[0], ys[0]) ? &SPACE(state, xs[0], ys[0]) : NULL;
661 ts[1] = INGRID(state, xs[1], ys[1]) ? &SPACE(state, xs[1], ys[1]) : NULL;
664 /* Returns a move string for use by 'solve', including the initial
665 * 'S' if issolve is true. */
666 static char *diff_game(const game_state *src, const game_state *dest,
669 int movelen = 0, movesize = 256, x, y, len;
670 char *move = snewn(movesize, char), buf[80];
671 const char *sep = "";
672 char achar = issolve ? 'a' : 'A';
675 assert(src->sx == dest->sx && src->sy == dest->sy);
678 move[movelen++] = 'S';
681 move[movelen] = '\0';
682 for (x = 0; x < src->sx; x++) {
683 for (y = 0; y < src->sy; y++) {
684 sps = &SPACE(src, x, y);
685 spd = &SPACE(dest, x, y);
687 assert(sps->type == spd->type);
690 if (sps->type == s_tile) {
691 if ((sps->flags & F_TILE_ASSOC) &&
692 (spd->flags & F_TILE_ASSOC)) {
693 if (sps->dotx != spd->dotx ||
694 sps->doty != spd->doty)
695 /* Both associated; change association, if different */
696 len = sprintf(buf, "%s%c%d,%d,%d,%d", sep,
697 (int)achar, x, y, spd->dotx, spd->doty);
698 } else if (sps->flags & F_TILE_ASSOC)
699 /* Only src associated; remove. */
700 len = sprintf(buf, "%sU%d,%d", sep, x, y);
701 else if (spd->flags & F_TILE_ASSOC)
702 /* Only dest associated; add. */
703 len = sprintf(buf, "%s%c%d,%d,%d,%d", sep,
704 (int)achar, x, y, spd->dotx, spd->doty);
705 } else if (sps->type == s_edge) {
706 if ((sps->flags & F_EDGE_SET) != (spd->flags & F_EDGE_SET))
707 /* edge flags are different; flip them. */
708 len = sprintf(buf, "%sE%d,%d", sep, x, y);
711 if (movelen + len >= movesize) {
712 movesize = movelen + len + 256;
713 move = sresize(move, movesize, char);
715 strcpy(move + movelen, buf);
721 debug(("diff_game src then dest:\n"));
724 debug(("diff string %s\n", move));
728 /* Returns 1 if a dot here would not be too close to any other dots
729 * (and would avoid other game furniture). */
730 static int dot_is_possible(game_state *state, space *sp, int allow_assoc)
732 int bx = 0, by = 0, dx, dy;
734 #ifdef STANDALONE_PICTURE_GENERATOR
742 if (IS_VERTICAL_EDGE(sp->x)) {
752 for (dx = -bx; dx <= bx; dx++) {
753 for (dy = -by; dy <= by; dy++) {
754 if (!INGRID(state, sp->x+dx, sp->y+dy)) continue;
756 adj = &SPACE(state, sp->x+dx, sp->y+dy);
758 #ifdef STANDALONE_PICTURE_GENERATOR
760 * Check that all the squares we're looking at have the
764 if (adj->type == s_tile) {
765 int c = picture[(adj->y / 2) * state->w + (adj->x / 2)];
769 return 0; /* colour mismatch */
774 if (!allow_assoc && (adj->flags & F_TILE_ASSOC))
777 if (dx != 0 || dy != 0) {
778 /* Other than our own square, no dots nearby. */
779 if (adj->flags & (F_DOT))
783 /* We don't want edges within our rectangle
784 * (but don't care about edges on the edge) */
785 if (abs(dx) < bx && abs(dy) < by &&
786 adj->flags & F_EDGE_SET)
793 /* ----------------------------------------------------------
794 * Game generation, structure creation, and descriptions.
797 static game_state *blank_game(int w, int h)
799 game_state *state = snew(game_state);
807 state->grid = snewn(state->sx * state->sy, space);
808 state->completed = state->used_solve = 0;
810 for (x = 0; x < state->sx; x++) {
811 for (y = 0; y < state->sy; y++) {
812 space *sp = &SPACE(state, x, y);
813 memset(sp, 0, sizeof(space));
816 if ((x % 2) == 0 && (y % 2) == 0)
818 else if ((x % 2) == 0 || (y % 2) == 0) {
820 if (x == 0 || y == 0 || x == state->sx-1 || y == state->sy-1)
821 sp->flags |= F_EDGE_SET;
830 state->me = NULL; /* filled in by new_game. */
836 static void game_update_dots(game_state *state)
838 int i, n, sz = state->sx * state->sy;
840 if (state->dots) sfree(state->dots);
843 for (i = 0; i < sz; i++) {
844 if (state->grid[i].flags & F_DOT) state->ndots++;
846 state->dots = snewn(state->ndots, space *);
848 for (i = 0; i < sz; i++) {
849 if (state->grid[i].flags & F_DOT)
850 state->dots[n++] = &state->grid[i];
854 static void clear_game(game_state *state, int cleardots)
858 /* don't erase edge flags around outline! */
859 for (x = 1; x < state->sx-1; x++) {
860 for (y = 1; y < state->sy-1; y++) {
862 SPACE(state, x, y).flags = 0;
864 SPACE(state, x, y).flags &= (F_DOT|F_DOT_BLACK);
867 if (cleardots) game_update_dots(state);
870 static game_state *dup_game(const game_state *state)
872 game_state *ret = blank_game(state->w, state->h);
874 ret->completed = state->completed;
875 ret->used_solve = state->used_solve;
877 memcpy(ret->grid, state->grid,
878 ret->sx*ret->sy*sizeof(space));
880 game_update_dots(ret);
883 ret->cdiff = state->cdiff;
888 static void free_game(game_state *state)
890 if (state->dots) sfree(state->dots);
895 /* Game description is a sequence of letters representing the number
896 * of spaces (a = 0, y = 24) before the next dot; a-y for a white dot,
897 * and A-Y for a black dot. 'z' is 25 spaces (and no dot).
899 * I know it's a bitch to generate by hand, so we provide
903 static char *encode_game(game_state *state)
909 area = (state->sx-2) * (state->sy-2);
911 desc = snewn(area, char);
914 for (y = 1; y < state->sy-1; y++) {
915 for (x = 1; x < state->sx-1; x++) {
916 f = SPACE(state, x, y).flags;
918 /* a/A is 0 spaces between, b/B is 1 space, ...
919 * y/Y is 24 spaces, za/zA is 25 spaces, ...
920 * It's easier to count from 0 because we then
921 * don't have to special-case the top left-hand corner
922 * (which could be a dot with 0 spaces before it). */
930 *p++ = ((f & F_DOT_BLACK) ? 'A' : 'a') + run;
935 assert(p - desc < area);
937 desc = sresize(desc, p - desc, char);
944 space *olddot, *newdot;
947 enum { MD_CHECK, MD_MOVE };
949 static int movedot_cb(game_state *state, space *tile, void *vctx)
951 struct movedot *md = (struct movedot *)vctx;
952 space *newopp = NULL;
954 assert(tile->type == s_tile);
955 assert(md->olddot && md->newdot);
957 if (!(tile->flags & F_TILE_ASSOC)) return 0;
958 if (tile->dotx != md->olddot->x || tile->doty != md->olddot->y)
961 newopp = space_opposite_dot(state, tile, md->newdot);
965 /* If the tile is associated with the old dot, check its
966 * opposite wrt the _new_ dot is empty or same assoc. */
967 if (!newopp) return -1; /* no new opposite */
968 if (newopp->flags & F_TILE_ASSOC) {
969 if (newopp->dotx != md->olddot->x ||
970 newopp->doty != md->olddot->y)
971 return -1; /* associated, but wrong dot. */
973 #ifdef STANDALONE_PICTURE_GENERATOR
976 * Reject if either tile and the dot don't match in colour.
978 if (!(picture[(tile->y/2) * state->w + (tile->x/2)]) ^
979 !(md->newdot->flags & F_DOT_BLACK))
981 if (!(picture[(newopp->y/2) * state->w + (newopp->x/2)]) ^
982 !(md->newdot->flags & F_DOT_BLACK))
989 /* Move dot associations: anything that was associated
990 * with the old dot, and its opposite wrt the new dot,
991 * become associated with the new dot. */
993 debug(("Associating %d,%d and %d,%d with new dot %d,%d.\n",
994 tile->x, tile->y, newopp->x, newopp->y,
995 md->newdot->x, md->newdot->y));
996 add_assoc(state, tile, md->newdot);
997 add_assoc(state, newopp, md->newdot);
998 return 1; /* we did something! */
1003 /* For the given dot, first see if we could expand it into all the given
1004 * extra spaces (by checking for empty spaces on the far side), and then
1005 * see if we can move the dot to shift the CoG to include the new spaces.
1007 static int dot_expand_or_move(game_state *state, space *dot,
1008 space **toadd, int nadd)
1011 int i, ret, nnew, cx, cy;
1014 debug(("dot_expand_or_move: %d tiles for dot %d,%d\n",
1015 nadd, dot->x, dot->y));
1016 for (i = 0; i < nadd; i++)
1017 debug(("dot_expand_or_move: dot %d,%d\n",
1018 toadd[i]->x, toadd[i]->y));
1019 assert(dot->flags & F_DOT);
1021 #ifdef STANDALONE_PICTURE_GENERATOR
1024 * Reject the expansion totally if any of the new tiles are
1027 for (i = 0; i < nadd; i++) {
1028 if (!(picture[(toadd[i]->y/2) * state->w + (toadd[i]->x/2)]) ^
1029 !(dot->flags & F_DOT_BLACK))
1035 /* First off, could we just expand the current dot's tile to cover
1036 * the space(s) passed in and their opposites? */
1037 for (i = 0; i < nadd; i++) {
1038 tileopp = space_opposite_dot(state, toadd[i], dot);
1039 if (!tileopp) goto noexpand;
1040 if (tileopp->flags & F_TILE_ASSOC) goto noexpand;
1041 #ifdef STANDALONE_PICTURE_GENERATOR
1044 * The opposite tiles have to be the right colour as well.
1046 if (!(picture[(tileopp->y/2) * state->w + (tileopp->x/2)]) ^
1047 !(dot->flags & F_DOT_BLACK))
1052 /* OK, all spaces have valid empty opposites: associate spaces and
1053 * opposites with our dot. */
1054 for (i = 0; i < nadd; i++) {
1055 tileopp = space_opposite_dot(state, toadd[i], dot);
1056 add_assoc(state, toadd[i], dot);
1057 add_assoc(state, tileopp, dot);
1058 debug(("Added associations %d,%d and %d,%d --> %d,%d\n",
1059 toadd[i]->x, toadd[i]->y,
1060 tileopp->x, tileopp->y,
1067 /* Otherwise, try to move dot so as to encompass given spaces: */
1068 /* first, calculate the 'centre of gravity' of the new dot. */
1069 nnew = dot->nassoc + nadd; /* number of tiles assoc. with new dot. */
1070 cx = dot->x * dot->nassoc;
1071 cy = dot->y * dot->nassoc;
1072 for (i = 0; i < nadd; i++) {
1076 /* If the CoG isn't a whole number, it's not possible. */
1077 if ((cx % nnew) != 0 || (cy % nnew) != 0) {
1078 debug(("Unable to move dot %d,%d, CoG not whole number.\n",
1082 cx /= nnew; cy /= nnew;
1084 /* Check whether all spaces in the old tile would have a good
1085 * opposite wrt the new dot. */
1087 md.newdot = &SPACE(state, cx, cy);
1089 ret = foreach_tile(state, movedot_cb, IMPOSSIBLE_QUITS, &md);
1091 debug(("Unable to move dot %d,%d, new dot not symmetrical.\n",
1095 /* Also check whether all spaces we're adding would have a good
1096 * opposite wrt the new dot. */
1097 for (i = 0; i < nadd; i++) {
1098 tileopp = space_opposite_dot(state, toadd[i], md.newdot);
1099 if (tileopp && (tileopp->flags & F_TILE_ASSOC) &&
1100 (tileopp->dotx != dot->x || tileopp->doty != dot->y)) {
1104 debug(("Unable to move dot %d,%d, new dot not symmetrical.\n",
1108 #ifdef STANDALONE_PICTURE_GENERATOR
1110 if (!(picture[(tileopp->y/2) * state->w + (tileopp->x/2)]) ^
1111 !(dot->flags & F_DOT_BLACK))
1117 /* If we've got here, we're ok. First, associate all of 'toadd'
1118 * with the _old_ dot (so they'll get fixed up, with their opposites,
1119 * in the next step). */
1120 for (i = 0; i < nadd; i++) {
1121 debug(("Associating to-add %d,%d with old dot %d,%d.\n",
1122 toadd[i]->x, toadd[i]->y, dot->x, dot->y));
1123 add_assoc(state, toadd[i], dot);
1126 /* Finally, move the dot and fix up all the old associations. */
1127 debug(("Moving dot at %d,%d to %d,%d\n",
1128 dot->x, dot->y, md.newdot->x, md.newdot->y));
1130 #ifdef STANDALONE_PICTURE_GENERATOR
1131 int f = dot->flags & F_DOT_BLACK;
1135 #ifdef STANDALONE_PICTURE_GENERATOR
1136 md.newdot->flags |= f;
1141 ret = foreach_tile(state, movedot_cb, 0, &md);
1148 /* Hard-code to a max. of 2x2 squares, for speed (less malloc) */
1150 #define MAX_OUTSIDE 8
1152 #define MAX_TILE_PERC 20
1154 static int generate_try_block(game_state *state, random_state *rs,
1155 int x1, int y1, int x2, int y2)
1157 int x, y, nadd = 0, nout = 0, i, maxsz;
1158 space *sp, *toadd[MAX_TOADD], *outside[MAX_OUTSIDE], *dot;
1160 if (!INGRID(state, x1, y1) || !INGRID(state, x2, y2)) return 0;
1162 /* We limit the maximum size of tiles to be ~2*sqrt(area); so,
1163 * a 5x5 grid shouldn't have anything >10 tiles, a 20x20 grid
1164 * nothing >40 tiles. */
1165 maxsz = (int)sqrt((double)(state->w * state->h)) * 2;
1166 debug(("generate_try_block, maxsz %d\n", maxsz));
1168 /* Make a static list of the spaces; if any space is already
1169 * associated then quit immediately. */
1170 for (x = x1; x <= x2; x += 2) {
1171 for (y = y1; y <= y2; y += 2) {
1172 assert(nadd < MAX_TOADD);
1173 sp = &SPACE(state, x, y);
1174 assert(sp->type == s_tile);
1175 if (sp->flags & F_TILE_ASSOC) return 0;
1180 /* Make a list of the spaces outside of our block, and shuffle it. */
1181 #define OUTSIDE(x, y) do { \
1182 if (INGRID(state, (x), (y))) { \
1183 assert(nout < MAX_OUTSIDE); \
1184 outside[nout++] = &SPACE(state, (x), (y)); \
1187 for (x = x1; x <= x2; x += 2) {
1191 for (y = y1; y <= y2; y += 2) {
1195 shuffle(outside, nout, sizeof(space *), rs);
1197 for (i = 0; i < nout; i++) {
1198 if (!(outside[i]->flags & F_TILE_ASSOC)) continue;
1199 dot = &SPACE(state, outside[i]->dotx, outside[i]->doty);
1200 if (dot->nassoc >= maxsz) {
1201 debug(("Not adding to dot %d,%d, large enough (%d) already.\n",
1202 dot->x, dot->y, dot->nassoc));
1205 if (dot_expand_or_move(state, dot, toadd, nadd)) return 1;
1210 #ifdef STANDALONE_SOLVER
1212 #define MAXTRIES maxtries
1219 static void generate_pass(game_state *state, random_state *rs, int *scratch,
1220 int perc, unsigned int flags)
1222 int sz = state->sx*state->sy, nspc, i, ret;
1224 shuffle(scratch, sz, sizeof(int), rs);
1226 /* This bug took me a, er, little while to track down. On PalmOS,
1227 * which has 16-bit signed ints, puzzles over about 9x9 started
1228 * failing to generate because the nspc calculation would start
1229 * to overflow, causing the dots not to be filled in properly. */
1230 nspc = (int)(((long)perc * (long)sz) / 100L);
1231 debug(("generate_pass: %d%% (%d of %dx%d) squares, flags 0x%x\n",
1232 perc, nspc, state->sx, state->sy, flags));
1234 for (i = 0; i < nspc; i++) {
1235 space *sp = &state->grid[scratch[i]];
1236 int x1 = sp->x, y1 = sp->y, x2 = sp->x, y2 = sp->y;
1238 if (sp->type == s_edge) {
1239 if (IS_VERTICAL_EDGE(sp->x)) {
1245 if (sp->type != s_vertex) {
1246 /* heuristic; expanding from vertices tends to generate lots of
1247 * too-big regions of tiles. */
1248 if (generate_try_block(state, rs, x1, y1, x2, y2))
1249 continue; /* we expanded successfully. */
1252 if (!(flags & GP_DOTS)) continue;
1254 if ((sp->type == s_edge) && (i % 2)) {
1255 debug(("Omitting edge %d,%d as half-of.\n", sp->x, sp->y));
1259 /* If we've got here we might want to put a dot down. Check
1260 * if we can, and add one if so. */
1261 if (dot_is_possible(state, sp, 0)) {
1263 #ifdef STANDALONE_PICTURE_GENERATOR
1265 if (picture[(sp->y/2) * state->w + (sp->x/2)])
1266 sp->flags |= F_DOT_BLACK;
1269 ret = solver_obvious_dot(state, sp);
1271 debug(("Added dot (and obvious associations) at %d,%d\n",
1279 static char *new_game_desc(const game_params *params, random_state *rs,
1280 char **aux, int interactive)
1282 game_state *state = blank_game(params->w, params->h), *copy;
1284 int *scratch, sz = state->sx*state->sy, i;
1285 int diff, ntries = 0, cc;
1287 /* Random list of squares to try and process, one-by-one. */
1288 scratch = snewn(sz, int);
1289 for (i = 0; i < sz; i++) scratch[i] = i;
1292 clear_game(state, 1);
1295 /* generate_pass(state, rs, scratch, 10, GP_DOTS); */
1296 /* generate_pass(state, rs, scratch, 100, 0); */
1297 generate_pass(state, rs, scratch, 100, GP_DOTS);
1299 game_update_dots(state);
1301 if (state->ndots == 1) goto generate;
1305 char *tmp = encode_game(state);
1306 debug(("new_game_desc state %dx%d:%s\n", params->w, params->h, tmp));
1311 for (i = 0; i < state->sx*state->sy; i++)
1312 if (state->grid[i].type == s_tile)
1313 outline_tile_fordot(state, &state->grid[i], TRUE);
1314 cc = check_complete(state, NULL, NULL);
1317 copy = dup_game(state);
1318 clear_game(copy, 0);
1320 diff = solver_state(copy, params->diff);
1323 assert(diff != DIFF_IMPOSSIBLE);
1324 if (diff != params->diff) {
1326 * We'll grudgingly accept a too-easy puzzle, but we must
1327 * _not_ permit a too-hard one (one which the solver
1328 * couldn't handle at all).
1330 if (diff > params->diff ||
1331 ntries < MAXTRIES) goto generate;
1334 #ifdef STANDALONE_PICTURE_GENERATOR
1336 * Postprocessing pass to prevent excessive numbers of adjacent
1337 * singletons. Iterate over all edges in random shuffled order;
1338 * for each edge that separates two regions, investigate
1339 * whether removing that edge and merging the regions would
1340 * still yield a valid and soluble puzzle. (The two regions
1341 * must also be the same colour, of course.) If so, do it.
1343 * This postprocessing pass is slow (due to repeated solver
1344 * invocations), and seems to be unnecessary during normal
1345 * unconstrained game generation. However, when generating a
1346 * game under colour constraints, excessive singletons seem to
1347 * turn up more often, so it's worth doing this.
1354 nposns = params->w * (params->h+1) + params->h * (params->w+1);
1355 posns = snewn(nposns, int);
1356 for (i = j = 0; i < state->sx*state->sy; i++)
1357 if (state->grid[i].type == s_edge)
1359 assert(j == nposns);
1361 shuffle(posns, nposns, sizeof(*posns), rs);
1363 for (i = 0; i < nposns; i++) {
1364 int x, y, x0, y0, x1, y1, cx, cy, cn, cx0, cy0, cx1, cy1, tx, ty;
1365 space *s0, *s1, *ts, *d0, *d1, *dn;
1368 /* Coordinates of edge space */
1369 x = posns[i] % state->sx;
1370 y = posns[i] / state->sx;
1372 /* Coordinates of square spaces on either side of edge */
1373 x0 = ((x+1) & ~1) - 1; /* round down to next odd number */
1374 y0 = ((y+1) & ~1) - 1;
1375 x1 = 2*x-x0; /* and reflect about x to get x1 */
1378 if (!INGRID(state, x0, y0) || !INGRID(state, x1, y1))
1379 continue; /* outermost edge of grid */
1380 s0 = &SPACE(state, x0, y0);
1381 s1 = &SPACE(state, x1, y1);
1382 assert(s0->type == s_tile && s1->type == s_tile);
1384 if (s0->dotx == s1->dotx && s0->doty == s1->doty)
1385 continue; /* tiles _already_ owned by same dot */
1387 d0 = &SPACE(state, s0->dotx, s0->doty);
1388 d1 = &SPACE(state, s1->dotx, s1->doty);
1390 if ((d0->flags ^ d1->flags) & F_DOT_BLACK)
1391 continue; /* different colours: cannot merge */
1394 * Work out where the centre of gravity of the new
1397 cx = d0->nassoc * d0->x + d1->nassoc * d1->x;
1398 cy = d0->nassoc * d0->y + d1->nassoc * d1->y;
1399 cn = d0->nassoc + d1->nassoc;
1400 if (cx % cn || cy % cn)
1401 continue; /* CoG not at integer coordinates */
1404 assert(INUI(state, cx, cy));
1407 * Ensure that the CoG would actually be _in_ the new
1408 * region, by verifying that all its surrounding tiles
1409 * belong to one or other of our two dots.
1411 cx0 = ((cx+1) & ~1) - 1; /* round down to next odd number */
1412 cy0 = ((cy+1) & ~1) - 1;
1413 cx1 = 2*cx-cx0; /* and reflect about cx to get cx1 */
1416 for (ty = cy0; ty <= cy1; ty += 2)
1417 for (tx = cx0; tx <= cx1; tx += 2) {
1418 ts = &SPACE(state, tx, ty);
1419 assert(ts->type == s_tile);
1420 if ((ts->dotx != d0->x || ts->doty != d0->y) &&
1421 (ts->dotx != d1->x || ts->doty != d1->y))
1428 * Verify that for every tile in either source region,
1429 * that tile's image in the new CoG is also in one of
1430 * the two source regions.
1432 for (ty = 1; ty < state->sy; ty += 2) {
1433 for (tx = 1; tx < state->sx; tx += 2) {
1436 ts = &SPACE(state, tx, ty);
1437 assert(ts->type == s_tile);
1438 if ((ts->dotx != d0->x || ts->doty != d0->y) &&
1439 (ts->dotx != d1->x || ts->doty != d1->y))
1440 continue; /* not part of these tiles anyway */
1443 if (!INGRID(state, tx1, ty1)) {
1447 ts = &SPACE(state, cx+cx-tx, cy+cy-ty);
1448 if ((ts->dotx != d0->x || ts->doty != d0->y) &&
1449 (ts->dotx != d1->x || ts->doty != d1->y)) {
1461 * Now we're clear to attempt the merge. We take a copy
1462 * of the game state first, so we can revert it easily
1463 * if the resulting puzzle turns out to have become
1466 copy2 = dup_game(state);
1470 dn = &SPACE(state, cx, cy);
1472 dn->flags |= (d0->flags & F_DOT_BLACK);
1473 for (ty = 1; ty < state->sy; ty += 2) {
1474 for (tx = 1; tx < state->sx; tx += 2) {
1475 ts = &SPACE(state, tx, ty);
1476 assert(ts->type == s_tile);
1477 if ((ts->dotx != d0->x || ts->doty != d0->y) &&
1478 (ts->dotx != d1->x || ts->doty != d1->y))
1479 continue; /* not part of these tiles anyway */
1480 add_assoc(state, ts, dn);
1484 copy = dup_game(state);
1485 clear_game(copy, 0);
1487 newdiff = solver_state(copy, params->diff);
1489 if (diff == newdiff) {
1490 /* Still just as soluble. Let the merge stand. */
1493 /* Became insoluble. Revert. */
1502 desc = encode_game(state);
1503 #ifndef STANDALONE_SOLVER
1504 debug(("new_game_desc generated: \n"));
1514 static int dots_too_close(game_state *state)
1516 /* Quick-and-dirty check, using half the solver:
1517 * solver_obvious will only fail if the dots are
1518 * too close together, so dot-proximity associations
1520 game_state *tmp = dup_game(state);
1521 int ret = solver_obvious(tmp);
1523 return (ret == -1) ? 1 : 0;
1526 static game_state *load_game(const game_params *params, const char *desc,
1529 game_state *state = blank_game(params->w, params->h);
1530 const char *why = NULL;
1541 if (n >= 'a' && n <= 'y') {
1544 } else if (n >= 'A' && n <= 'Y') {
1548 why = "Invalid characters in game description"; goto fail;
1550 /* if we got here we incremented i and have a dot to add. */
1551 y = (i / (state->sx-2)) + 1;
1552 x = (i % (state->sx-2)) + 1;
1553 if (!INUI(state, x, y)) {
1554 why = "Too much data to fit in grid"; goto fail;
1556 add_dot(&SPACE(state, x, y));
1557 SPACE(state, x, y).flags |= df;
1560 game_update_dots(state);
1562 if (dots_too_close(state)) {
1563 why = "Dots too close together"; goto fail;
1570 if (why_r) *why_r = why;
1574 static const char *validate_desc(const game_params *params, const char *desc)
1576 const char *why = NULL;
1577 game_state *dummy = load_game(params, desc, &why);
1586 static game_state *new_game(midend *me, const game_params *params,
1589 game_state *state = load_game(params, desc, NULL);
1591 assert("Unable to load ?validated game.");
1600 /* ----------------------------------------------------------
1601 * Solver and all its little wizards.
1604 int solver_recurse_depth;
1606 typedef struct solver_ctx {
1608 int sz; /* state->sx * state->sy */
1609 space **scratch; /* size sz */
1613 static solver_ctx *new_solver(game_state *state)
1615 solver_ctx *sctx = snew(solver_ctx);
1616 sctx->state = state;
1617 sctx->sz = state->sx*state->sy;
1618 sctx->scratch = snewn(sctx->sz, space *);
1622 static void free_solver(solver_ctx *sctx)
1624 sfree(sctx->scratch);
1628 /* Solver ideas so far:
1630 * For any empty space, work out how many dots it could associate
1632 * it needs line-of-sight
1633 * it needs an empty space on the far side
1634 * any adjacent lines need corresponding line possibilities.
1637 /* The solver_ctx should keep a list of dot positions, for quicker looping.
1639 * Solver techniques, in order of difficulty:
1640 * obvious adjacency to dots
1641 * transferring tiles to opposite side
1642 * transferring lines to opposite side
1643 * one possible dot for a given tile based on opposite availability
1644 * tile with 3 definite edges next to an associated tile must associate
1647 * one possible dot for a given tile based on line-of-sight
1650 static int solver_add_assoc(game_state *state, space *tile, int dx, int dy,
1653 space *dot, *tile_opp;
1655 dot = &SPACE(state, dx, dy);
1656 tile_opp = space_opposite_dot(state, tile, dot);
1658 assert(tile->type == s_tile);
1659 if (tile->flags & F_TILE_ASSOC) {
1660 if ((tile->dotx != dx) || (tile->doty != dy)) {
1661 solvep(("%*sSet %d,%d --> %d,%d (%s) impossible; "
1662 "already --> %d,%d.\n",
1663 solver_recurse_depth*4, "",
1664 tile->x, tile->y, dx, dy, why,
1665 tile->dotx, tile->doty));
1668 return 0; /* no-op */
1671 solvep(("%*s%d,%d --> %d,%d impossible, no opposite tile.\n",
1672 solver_recurse_depth*4, "", tile->x, tile->y, dx, dy));
1675 if (tile_opp->flags & F_TILE_ASSOC &&
1676 (tile_opp->dotx != dx || tile_opp->doty != dy)) {
1677 solvep(("%*sSet %d,%d --> %d,%d (%s) impossible; "
1678 "opposite already --> %d,%d.\n",
1679 solver_recurse_depth*4, "",
1680 tile->x, tile->y, dx, dy, why,
1681 tile_opp->dotx, tile_opp->doty));
1685 add_assoc(state, tile, dot);
1686 add_assoc(state, tile_opp, dot);
1687 solvep(("%*sSetting %d,%d --> %d,%d (%s).\n",
1688 solver_recurse_depth*4, "",
1689 tile->x, tile->y,dx, dy, why));
1690 solvep(("%*sSetting %d,%d --> %d,%d (%s, opposite).\n",
1691 solver_recurse_depth*4, "",
1692 tile_opp->x, tile_opp->y, dx, dy, why));
1696 static int solver_obvious_dot(game_state *state, space *dot)
1698 int dx, dy, ret, didsth = 0;
1701 debug(("%*ssolver_obvious_dot for %d,%d.\n",
1702 solver_recurse_depth*4, "", dot->x, dot->y));
1704 assert(dot->flags & F_DOT);
1705 for (dx = -1; dx <= 1; dx++) {
1706 for (dy = -1; dy <= 1; dy++) {
1707 if (!INGRID(state, dot->x+dx, dot->y+dy)) continue;
1709 tile = &SPACE(state, dot->x+dx, dot->y+dy);
1710 if (tile->type == s_tile) {
1711 ret = solver_add_assoc(state, tile, dot->x, dot->y,
1713 if (ret < 0) return -1;
1714 if (ret > 0) didsth = 1;
1721 static int solver_obvious(game_state *state)
1723 int i, didsth = 0, ret;
1725 debug(("%*ssolver_obvious.\n", solver_recurse_depth*4, ""));
1727 for (i = 0; i < state->ndots; i++) {
1728 ret = solver_obvious_dot(state, state->dots[i]);
1729 if (ret < 0) return -1;
1730 if (ret > 0) didsth = 1;
1735 static int solver_lines_opposite_cb(game_state *state, space *edge, void *ctx)
1737 int didsth = 0, n, dx, dy;
1738 space *tiles[2], *tile_opp, *edge_opp;
1740 assert(edge->type == s_edge);
1742 tiles_from_edge(state, edge, tiles);
1744 /* if tiles[0] && tiles[1] && they're both associated
1745 * and they're both associated with different dots,
1746 * ensure the line is set. */
1747 if (!(edge->flags & F_EDGE_SET) &&
1748 tiles[0] && tiles[1] &&
1749 (tiles[0]->flags & F_TILE_ASSOC) &&
1750 (tiles[1]->flags & F_TILE_ASSOC) &&
1751 (tiles[0]->dotx != tiles[1]->dotx ||
1752 tiles[0]->doty != tiles[1]->doty)) {
1753 /* No edge, but the two adjacent tiles are both
1754 * associated with different dots; add the edge. */
1755 solvep(("%*sSetting edge %d,%d - tiles different dots.\n",
1756 solver_recurse_depth*4, "", edge->x, edge->y));
1757 edge->flags |= F_EDGE_SET;
1761 if (!(edge->flags & F_EDGE_SET)) return didsth;
1762 for (n = 0; n < 2; n++) {
1763 if (!tiles[n]) continue;
1764 assert(tiles[n]->type == s_tile);
1765 if (!(tiles[n]->flags & F_TILE_ASSOC)) continue;
1767 tile_opp = tile_opposite(state, tiles[n]);
1769 solvep(("%*simpossible: edge %d,%d has assoc. tile %d,%d"
1770 " with no opposite.\n",
1771 solver_recurse_depth*4, "",
1772 edge->x, edge->y, tiles[n]->x, tiles[n]->y));
1773 /* edge of tile has no opposite edge (off grid?);
1774 * this is impossible. */
1778 dx = tiles[n]->x - edge->x;
1779 dy = tiles[n]->y - edge->y;
1780 assert(INGRID(state, tile_opp->x+dx, tile_opp->y+dy));
1781 edge_opp = &SPACE(state, tile_opp->x+dx, tile_opp->y+dy);
1782 if (!(edge_opp->flags & F_EDGE_SET)) {
1783 solvep(("%*sSetting edge %d,%d as opposite %d,%d\n",
1784 solver_recurse_depth*4, "",
1785 tile_opp->x-dx, tile_opp->y-dy, edge->x, edge->y));
1786 edge_opp->flags |= F_EDGE_SET;
1793 static int solver_spaces_oneposs_cb(game_state *state, space *tile, void *ctx)
1796 space *edgeadj[4], *tileadj[4];
1799 assert(tile->type == s_tile);
1800 if (tile->flags & F_TILE_ASSOC) return 0;
1802 adjacencies(state, tile, edgeadj, tileadj);
1804 /* Empty tile. If each edge is either set, or associated with
1805 * the same dot, we must also associate with dot. */
1806 eset = 0; dotx = -1; doty = -1;
1807 for (n = 0; n < 4; n++) {
1809 assert(edgeadj[n]->type == s_edge);
1810 if (edgeadj[n]->flags & F_EDGE_SET) {
1814 assert(tileadj[n]->type == s_tile);
1816 /* If an adjacent tile is empty we can't make any deductions.*/
1817 if (!(tileadj[n]->flags & F_TILE_ASSOC))
1820 /* If an adjacent tile is assoc. with a different dot
1821 * we can't make any deductions. */
1822 if (dotx != -1 && doty != -1 &&
1823 (tileadj[n]->dotx != dotx ||
1824 tileadj[n]->doty != doty))
1827 dotx = tileadj[n]->dotx;
1828 doty = tileadj[n]->doty;
1832 solvep(("%*simpossible: empty tile %d,%d has 4 edges\n",
1833 solver_recurse_depth*4, "",
1837 assert(dotx != -1 && doty != -1);
1839 ret = solver_add_assoc(state, tile, dotx, doty, "rest are edges");
1840 if (ret == -1) return -1;
1841 assert(ret != 0); /* really should have done something. */
1846 /* Improved algorithm for tracking line-of-sight from dots, and not spaces.
1848 * The solver_ctx already stores a list of dots: the algorithm proceeds by
1849 * expanding outwards from each dot in turn, expanding first to the boundary
1850 * of its currently-connected tile and then to all empty tiles that could see
1851 * it. Empty tiles will be flagged with a 'can see dot <x,y>' sticker.
1853 * Expansion will happen by (symmetrically opposite) pairs of squares; if
1854 * a square hasn't an opposite number there's no point trying to expand through
1855 * it. Empty tiles will therefore also be tagged in pairs.
1857 * If an empty tile already has a 'can see dot <x,y>' tag from a previous dot,
1858 * it (and its partner) gets untagged (or, rather, a 'can see two dots' tag)
1859 * because we're looking for single-dot possibilities.
1861 * Once we've gone through all the dots, any which still have a 'can see dot'
1862 * tag get associated with that dot (because it must have been the only one);
1863 * any without any tag (i.e. that could see _no_ dots) cause an impossibility
1866 * The expansion will happen each time with a stored list of (space *) pairs,
1867 * rather than a mark-and-sweep idea; that's horrifically inefficient.
1869 * expansion algorithm:
1871 * * allocate list of (space *) the size of s->sx*s->sy.
1872 * * allocate second grid for (flags, dotx, doty) size of sx*sy.
1874 * clear second grid (flags = 0, all dotx and doty = 0)
1875 * flags: F_REACHABLE, F_MULTIPLE
1878 * * for each dot, start with one pair of tiles that are associated with it --
1879 * * vertex --> (dx+1, dy+1), (dx-1, dy-1)
1880 * * edge --> (adj1, adj2)
1881 * * tile --> (tile, tile) ???
1882 * * mark that pair of tiles with F_MARK, clear all other F_MARKs.
1883 * * add two tiles to start of list.
1885 * set start = 0, end = next = 2
1887 * from (start to end-1, step 2) {
1888 * * we have two tiles (t1, t2), opposites wrt our dot.
1889 * * for each (at1) sensible adjacent tile to t1 (i.e. not past an edge):
1890 * * work out at2 as the opposite to at1
1891 * * assert at1 and at2 have the same F_MARK values.
1892 * * if at1 & F_MARK ignore it (we've been there on a previous sweep)
1893 * * if either are associated with a different dot
1894 * * mark both with F_MARK (so we ignore them later)
1895 * * otherwise (assoc. with our dot, or empty):
1896 * * mark both with F_MARK
1897 * * add their space * values to the end of the list, set next += 2.
1901 * * we didn't add any new squares; exit the loop.
1903 * * set start = next+1, end = next. go round again
1905 * We've finished expanding from the dot. Now, for each square we have
1906 * in our list (--> each square with F_MARK):
1907 * * if the tile is empty:
1908 * * if F_REACHABLE was already set
1911 * * set F_REACHABLE, set dotx and doty to our dot.
1913 * Then, continue the whole thing for each dot in turn.
1915 * Once we've done for each dot, go through the entire grid looking for
1916 * empty tiles: for each empty tile:
1917 * if F_REACHABLE and not F_MULTIPLE, set that dot (and its double)
1918 * if !F_REACHABLE, return as impossible.
1922 /* Returns 1 if this tile is either already associated with this dot,
1924 static int solver_expand_checkdot(space *tile, space *dot)
1926 if (!(tile->flags & F_TILE_ASSOC)) return 1;
1927 if (tile->dotx == dot->x && tile->doty == dot->y) return 1;
1931 static void solver_expand_fromdot(game_state *state, space *dot, solver_ctx *sctx)
1933 int i, j, x, y, start, end, next;
1936 /* Clear the grid of the (space) flags we'll use. */
1938 /* This is well optimised; analysis showed that:
1939 for (i = 0; i < sctx->sz; i++) state->grid[i].flags &= ~F_MARK;
1940 took up ~85% of the total function time! */
1941 for (y = 1; y < state->sy; y += 2) {
1942 sp = &SPACE(state, 1, y);
1943 for (x = 1; x < state->sx; x += 2, sp += 2)
1944 sp->flags &= ~F_MARK;
1947 /* Seed the list of marked squares with two that must be associated
1948 * with our dot (possibly the same space) */
1949 if (dot->type == s_tile) {
1950 sctx->scratch[0] = sctx->scratch[1] = dot;
1951 } else if (dot->type == s_edge) {
1952 tiles_from_edge(state, dot, sctx->scratch);
1953 } else if (dot->type == s_vertex) {
1954 /* pick two of the opposite ones arbitrarily. */
1955 sctx->scratch[0] = &SPACE(state, dot->x-1, dot->y-1);
1956 sctx->scratch[1] = &SPACE(state, dot->x+1, dot->y+1);
1958 assert(sctx->scratch[0]->flags & F_TILE_ASSOC);
1959 assert(sctx->scratch[1]->flags & F_TILE_ASSOC);
1961 sctx->scratch[0]->flags |= F_MARK;
1962 sctx->scratch[1]->flags |= F_MARK;
1964 debug(("%*sexpand from dot %d,%d seeded with %d,%d and %d,%d.\n",
1965 solver_recurse_depth*4, "", dot->x, dot->y,
1966 sctx->scratch[0]->x, sctx->scratch[0]->y,
1967 sctx->scratch[1]->x, sctx->scratch[1]->y));
1969 start = 0; end = 2; next = 2;
1972 debug(("%*sexpand: start %d, end %d, next %d\n",
1973 solver_recurse_depth*4, "", start, end, next));
1974 for (i = start; i < end; i += 2) {
1975 space *t1 = sctx->scratch[i]/*, *t2 = sctx->scratch[i+1]*/;
1976 space *edges[4], *tileadj[4], *tileadj2;
1978 adjacencies(state, t1, edges, tileadj);
1980 for (j = 0; j < 4; j++) {
1982 if (edges[j]->flags & F_EDGE_SET) continue;
1985 if (tileadj[j]->flags & F_MARK) continue; /* seen before. */
1987 /* We have a tile adjacent to t1; find its opposite. */
1988 tileadj2 = space_opposite_dot(state, tileadj[j], dot);
1990 debug(("%*sMarking %d,%d, no opposite.\n",
1991 solver_recurse_depth*4, "",
1992 tileadj[j]->x, tileadj[j]->y));
1993 tileadj[j]->flags |= F_MARK;
1994 continue; /* no opposite, so mark for next time. */
1996 /* If the tile had an opposite we should have either seen both of
1997 * these, or neither of these, before. */
1998 assert(!(tileadj2->flags & F_MARK));
2000 if (solver_expand_checkdot(tileadj[j], dot) &&
2001 solver_expand_checkdot(tileadj2, dot)) {
2002 /* Both tiles could associate with this dot; add them to
2004 debug(("%*sAdding %d,%d and %d,%d to possibles list.\n",
2005 solver_recurse_depth*4, "",
2006 tileadj[j]->x, tileadj[j]->y, tileadj2->x, tileadj2->y));
2007 sctx->scratch[next++] = tileadj[j];
2008 sctx->scratch[next++] = tileadj2;
2010 /* Either way, we've seen these tiles already so mark them. */
2011 debug(("%*sMarking %d,%d and %d,%d.\n",
2012 solver_recurse_depth*4, "",
2013 tileadj[j]->x, tileadj[j]->y, tileadj2->x, tileadj2->y));
2014 tileadj[j]->flags |= F_MARK;
2015 tileadj2->flags |= F_MARK;
2019 /* We added more squares; go back and try again. */
2020 start = end; end = next; goto expand;
2023 /* We've expanded as far as we can go. Now we update the main flags
2024 * on all tiles we've expanded into -- if they were empty, we have
2025 * found possible associations for this dot. */
2026 for (i = 0; i < end; i++) {
2027 if (sctx->scratch[i]->flags & F_TILE_ASSOC) continue;
2028 if (sctx->scratch[i]->flags & F_REACHABLE) {
2029 /* This is (at least) the second dot this tile could
2030 * associate with. */
2031 debug(("%*sempty tile %d,%d could assoc. other dot %d,%d\n",
2032 solver_recurse_depth*4, "",
2033 sctx->scratch[i]->x, sctx->scratch[i]->y, dot->x, dot->y));
2034 sctx->scratch[i]->flags |= F_MULTIPLE;
2036 /* This is the first (possibly only) dot. */
2037 debug(("%*sempty tile %d,%d could assoc. 1st dot %d,%d\n",
2038 solver_recurse_depth*4, "",
2039 sctx->scratch[i]->x, sctx->scratch[i]->y, dot->x, dot->y));
2040 sctx->scratch[i]->flags |= F_REACHABLE;
2041 sctx->scratch[i]->dotx = dot->x;
2042 sctx->scratch[i]->doty = dot->y;
2048 static int solver_expand_postcb(game_state *state, space *tile, void *ctx)
2050 assert(tile->type == s_tile);
2052 if (tile->flags & F_TILE_ASSOC) return 0;
2054 if (!(tile->flags & F_REACHABLE)) {
2055 solvep(("%*simpossible: space (%d,%d) can reach no dots.\n",
2056 solver_recurse_depth*4, "", tile->x, tile->y));
2059 if (tile->flags & F_MULTIPLE) return 0;
2061 return solver_add_assoc(state, tile, tile->dotx, tile->doty,
2062 "single possible dot after expansion");
2065 static int solver_expand_dots(game_state *state, solver_ctx *sctx)
2069 for (i = 0; i < sctx->sz; i++)
2070 state->grid[i].flags &= ~(F_REACHABLE|F_MULTIPLE);
2072 for (i = 0; i < state->ndots; i++)
2073 solver_expand_fromdot(state, state->dots[i], sctx);
2075 return foreach_tile(state, solver_expand_postcb, IMPOSSIBLE_QUITS, sctx);
2078 struct recurse_ctx {
2083 static int solver_recurse_cb(game_state *state, space *tile, void *ctx)
2085 struct recurse_ctx *rctx = (struct recurse_ctx *)ctx;
2088 assert(tile->type == s_tile);
2089 if (tile->flags & F_TILE_ASSOC) return 0;
2091 /* We're unassociated: count up all the dots we could associate with. */
2092 for (i = 0; i < state->ndots; i++) {
2093 if (dotfortile(state, tile, state->dots[i]))
2096 if (n > rctx->bestn) {
2103 #define MAXRECURSE 5
2105 static int solver_recurse(game_state *state, int maxdiff)
2107 int diff = DIFF_IMPOSSIBLE, ret, n, gsz = state->sx * state->sy;
2108 space *ingrid, *outgrid = NULL, *bestopp;
2109 struct recurse_ctx rctx;
2111 if (solver_recurse_depth >= MAXRECURSE) {
2112 solvep(("Limiting recursion to %d, returning.", MAXRECURSE));
2113 return DIFF_UNFINISHED;
2116 /* Work out the cell to recurse on; go through all unassociated tiles
2117 * and find which one has the most possible dots it could associate
2122 foreach_tile(state, solver_recurse_cb, 0, &rctx);
2123 if (rctx.bestn == 0) return DIFF_IMPOSSIBLE; /* or assert? */
2126 solvep(("%*sRecursing around %d,%d, with %d possible dots.\n",
2127 solver_recurse_depth*4, "",
2128 rctx.best->x, rctx.best->y, rctx.bestn));
2130 #ifdef STANDALONE_SOLVER
2131 solver_recurse_depth++;
2134 ingrid = snewn(gsz, space);
2135 memcpy(ingrid, state->grid, gsz * sizeof(space));
2137 for (n = 0; n < state->ndots; n++) {
2138 memcpy(state->grid, ingrid, gsz * sizeof(space));
2140 if (!dotfortile(state, rctx.best, state->dots[n])) continue;
2142 /* set cell (temporarily) pointing to that dot. */
2143 solver_add_assoc(state, rctx.best,
2144 state->dots[n]->x, state->dots[n]->y,
2145 "Attempting for recursion");
2147 ret = solver_state(state, maxdiff);
2149 if (diff == DIFF_IMPOSSIBLE && ret != DIFF_IMPOSSIBLE) {
2150 /* we found our first solved grid; copy it away. */
2152 outgrid = snewn(gsz, space);
2153 memcpy(outgrid, state->grid, gsz * sizeof(space));
2155 /* reset cell back to unassociated. */
2156 bestopp = tile_opposite(state, rctx.best);
2157 assert(bestopp && bestopp->flags & F_TILE_ASSOC);
2159 remove_assoc(state, rctx.best);
2160 remove_assoc(state, bestopp);
2162 if (ret == DIFF_AMBIGUOUS || ret == DIFF_UNFINISHED)
2164 else if (ret == DIFF_IMPOSSIBLE)
2167 /* precisely one solution */
2168 if (diff == DIFF_IMPOSSIBLE)
2169 diff = DIFF_UNREASONABLE;
2171 diff = DIFF_AMBIGUOUS;
2173 /* if we've found >1 solution, or ran out of recursion,
2174 * give up immediately. */
2175 if (diff == DIFF_AMBIGUOUS || diff == DIFF_UNFINISHED)
2179 #ifdef STANDALONE_SOLVER
2180 solver_recurse_depth--;
2184 /* we found (at least one) soln; copy it back to state */
2185 memcpy(state->grid, outgrid, gsz * sizeof(space));
2192 static int solver_state(game_state *state, int maxdiff)
2194 solver_ctx *sctx = new_solver(state);
2195 int ret, diff = DIFF_NORMAL;
2197 #ifdef STANDALONE_PICTURE_GENERATOR
2198 /* hack, hack: set picture to NULL during solving so that add_assoc
2199 * won't complain when we attempt recursive guessing and guess wrong */
2200 int *savepic = picture;
2204 ret = solver_obvious(state);
2206 diff = DIFF_IMPOSSIBLE;
2210 #define CHECKRET(d) do { \
2211 if (ret < 0) { diff = DIFF_IMPOSSIBLE; goto got_result; } \
2212 if (ret > 0) { diff = max(diff, (d)); goto cont; } \
2217 ret = foreach_edge(state, solver_lines_opposite_cb,
2218 IMPOSSIBLE_QUITS, sctx);
2219 CHECKRET(DIFF_NORMAL);
2221 ret = foreach_tile(state, solver_spaces_oneposs_cb,
2222 IMPOSSIBLE_QUITS, sctx);
2223 CHECKRET(DIFF_NORMAL);
2225 ret = solver_expand_dots(state, sctx);
2226 CHECKRET(DIFF_NORMAL);
2228 if (maxdiff <= DIFF_NORMAL)
2233 /* if we reach here, we've made no deductions, so we terminate. */
2237 if (check_complete(state, NULL, NULL)) goto got_result;
2239 diff = (maxdiff >= DIFF_UNREASONABLE) ?
2240 solver_recurse(state, maxdiff) : DIFF_UNFINISHED;
2244 #ifndef STANDALONE_SOLVER
2245 debug(("solver_state ends, diff %s:\n", galaxies_diffnames[diff]));
2249 #ifdef STANDALONE_PICTURE_GENERATOR
2257 static char *solve_game(const game_state *state, const game_state *currstate,
2258 const char *aux, const char **error)
2260 game_state *tosolve;
2265 tosolve = dup_game(currstate);
2266 diff = solver_state(tosolve, DIFF_UNREASONABLE);
2267 if (diff != DIFF_UNFINISHED && diff != DIFF_IMPOSSIBLE) {
2268 debug(("solve_game solved with current state.\n"));
2273 tosolve = dup_game(state);
2274 diff = solver_state(tosolve, DIFF_UNREASONABLE);
2275 if (diff != DIFF_UNFINISHED && diff != DIFF_IMPOSSIBLE) {
2276 debug(("solve_game solved with original state.\n"));
2285 * Clear tile associations: the solution will only include the
2288 for (i = 0; i < tosolve->sx*tosolve->sy; i++)
2289 tosolve->grid[i].flags &= ~F_TILE_ASSOC;
2290 ret = diff_game(currstate, tosolve, 1);
2296 /* ----------------------------------------------------------
2302 int dx, dy; /* pixel coords of drag pos. */
2303 int dotx, doty; /* grid coords of dot we're dragging from. */
2304 int srcx, srcy; /* grid coords of drag start */
2305 int cur_x, cur_y, cur_visible;
2308 static game_ui *new_ui(const game_state *state)
2310 game_ui *ui = snew(game_ui);
2311 ui->dragging = FALSE;
2312 ui->cur_x = ui->cur_y = 1;
2313 ui->cur_visible = 0;
2317 static void free_ui(game_ui *ui)
2322 static char *encode_ui(const game_ui *ui)
2327 static void decode_ui(game_ui *ui, const char *encoding)
2331 static void game_changed_state(game_ui *ui, const game_state *oldstate,
2332 const game_state *newstate)
2336 #define FLASH_TIME 0.15F
2338 #define PREFERRED_TILE_SIZE 32
2339 #define TILE_SIZE (ds->tilesize)
2340 #define DOT_SIZE (TILE_SIZE / 4)
2341 #define EDGE_THICKNESS (max(TILE_SIZE / 16, 2))
2342 #define BORDER TILE_SIZE
2344 #define COORD(x) ( (x) * TILE_SIZE + BORDER )
2345 #define SCOORD(x) ( ((x) * TILE_SIZE)/2 + BORDER )
2346 #define FROMCOORD(x) ( ((x) - BORDER) / TILE_SIZE )
2348 #define DRAW_WIDTH (BORDER * 2 + ds->w * TILE_SIZE)
2349 #define DRAW_HEIGHT (BORDER * 2 + ds->h * TILE_SIZE)
2351 #define CURSOR_SIZE DOT_SIZE
2353 struct game_drawstate {
2357 unsigned long *grid;
2362 int dragging, dragx, dragy;
2364 int *colour_scratch;
2366 int cx, cy, cur_visible;
2370 #define CORNER_TOLERANCE 0.15F
2371 #define CENTRE_TOLERANCE 0.15F
2374 * Round FP coordinates to the centre of the nearest edge.
2377 static void coord_round_to_edge(float x, float y, int *xr, int *yr)
2379 float xs, ys, xv, yv, dx, dy;
2382 * Find the nearest square-centre.
2384 xs = (float)floor(x) + 0.5F;
2385 ys = (float)floor(y) + 0.5F;
2388 * Find the nearest grid vertex.
2390 xv = (float)floor(x + 0.5F);
2391 yv = (float)floor(y + 0.5F);
2394 * Determine whether the horizontal or vertical edge from that
2395 * vertex alongside that square is closer to us, by comparing
2396 * distances from the square cente.
2398 dx = (float)fabs(x - xs);
2399 dy = (float)fabs(y - ys);
2401 /* Vertical edge: x-coord of corner,
2402 * y-coord of square centre. */
2404 *yr = 1 + 2 * (int)floor(ys);
2406 /* Horizontal edge: x-coord of square centre,
2407 * y-coord of corner. */
2408 *xr = 1 + 2 * (int)floor(xs);
2415 static char *interpret_move(const game_state *state, game_ui *ui,
2416 const game_drawstate *ds,
2417 int x, int y, int button)
2423 px = 2*FROMCOORD((float)x) + 0.5;
2424 py = 2*FROMCOORD((float)y) + 0.5;
2428 if (button == 'C' || button == 'c') return dupstr("C");
2430 if (button == 'S' || button == 's') {
2432 game_state *tmp = dup_game(state);
2433 state->cdiff = solver_state(tmp, DIFF_UNREASONABLE-1);
2434 ret = diff_game(state, tmp, 0);
2439 if (button == LEFT_BUTTON || button == RIGHT_BUTTON) {
2440 if (!INUI(state, px, py)) return NULL;
2441 sp = &SPACE(state, px, py);
2442 if (!dot_is_possible(state, sp, 1)) return NULL;
2443 sprintf(buf, "%c%d,%d",
2444 (char)((button == LEFT_BUTTON) ? 'D' : 'd'), px, py);
2451 static char *interpret_move(const game_state *state, game_ui *ui,
2452 const game_drawstate *ds,
2453 int x, int y, int button)
2455 /* UI operations (play mode):
2457 * Toggle edge (set/unset) (left-click on edge)
2458 * Associate space with dot (left-drag from dot)
2459 * Unassociate space (left-drag from space off grid)
2460 * Autofill lines around shape? (right-click?)
2462 * (edit mode; will clear all lines/associations)
2464 * Add or remove dot (left-click)
2467 const char *sep = "";
2473 if (button == 'H' || button == 'h') {
2475 game_state *tmp = dup_game(state);
2476 solver_obvious(tmp);
2477 ret = diff_game(state, tmp, 0);
2482 if (button == LEFT_BUTTON) {
2483 ui->cur_visible = 0;
2484 coord_round_to_edge(FROMCOORD((float)x), FROMCOORD((float)y),
2487 if (!INUI(state, px, py)) return NULL;
2489 sp = &SPACE(state, px, py);
2490 assert(sp->type == s_edge);
2492 sprintf(buf, "E%d,%d", px, py);
2495 } else if (button == RIGHT_BUTTON) {
2498 ui->cur_visible = 0;
2500 px = (int)(2*FROMCOORD((float)x) + 0.5);
2501 py = (int)(2*FROMCOORD((float)y) + 0.5);
2506 * If there's a dot anywhere nearby, we pick up an arrow
2507 * pointing at that dot.
2509 for (py1 = py-1; py1 <= py+1; py1++)
2510 for (px1 = px-1; px1 <= px+1; px1++) {
2511 if (px1 >= 0 && px1 < state->sx &&
2512 py1 >= 0 && py1 < state->sy &&
2513 x >= SCOORD(px1-1) && x < SCOORD(px1+1) &&
2514 y >= SCOORD(py1-1) && y < SCOORD(py1+1) &&
2515 SPACE(state, px1, py1).flags & F_DOT) {
2517 * Found a dot. Begin a drag from it.
2519 dot = &SPACE(state, px1, py1);
2522 goto done; /* multi-level break */
2527 * Otherwise, find the nearest _square_, and pick up the
2528 * same arrow as it's got on it, if any.
2531 px = 2*FROMCOORD(x+TILE_SIZE) - 1;
2532 py = 2*FROMCOORD(y+TILE_SIZE) - 1;
2533 if (px >= 0 && px < state->sx && py >= 0 && py < state->sy) {
2534 sp = &SPACE(state, px, py);
2535 if (sp->flags & F_TILE_ASSOC) {
2536 dot = &SPACE(state, sp->dotx, sp->doty);
2545 * Now, if we've managed to find a dot, begin a drag.
2548 ui->dragging = TRUE;
2555 } else if (button == RIGHT_DRAG && ui->dragging) {
2556 /* just move the drag coords. */
2560 } else if (button == RIGHT_RELEASE && ui->dragging) {
2561 ui->dragging = FALSE;
2564 * Drags are always targeted at a single square.
2566 px = 2*FROMCOORD(x+TILE_SIZE) - 1;
2567 py = 2*FROMCOORD(y+TILE_SIZE) - 1;
2570 * Dragging an arrow on to the same square it started from
2571 * is a null move; just update the ui and finish.
2573 if (px == ui->srcx && py == ui->srcy)
2577 * Otherwise, we remove the arrow from its starting
2578 * square if we didn't start from a dot...
2580 if ((ui->srcx != ui->dotx || ui->srcy != ui->doty) &&
2581 SPACE(state, ui->srcx, ui->srcy).flags & F_TILE_ASSOC) {
2582 sprintf(buf + strlen(buf), "%sU%d,%d", sep, ui->srcx, ui->srcy);
2587 * ... and if the square we're moving it _to_ is valid, we
2588 * add one there instead.
2590 if (INUI(state, px, py)) {
2591 sp = &SPACE(state, px, py);
2593 if (!(sp->flags & F_DOT))
2594 sprintf(buf + strlen(buf), "%sA%d,%d,%d,%d",
2595 sep, px, py, ui->dotx, ui->doty);
2602 } else if (IS_CURSOR_MOVE(button)) {
2603 move_cursor(button, &ui->cur_x, &ui->cur_y, state->sx-1, state->sy-1, 0);
2604 if (ui->cur_x < 1) ui->cur_x = 1;
2605 if (ui->cur_y < 1) ui->cur_y = 1;
2606 ui->cur_visible = 1;
2608 ui->dx = SCOORD(ui->cur_x);
2609 ui->dy = SCOORD(ui->cur_y);
2612 } else if (IS_CURSOR_SELECT(button)) {
2613 if (!ui->cur_visible) {
2614 ui->cur_visible = 1;
2617 sp = &SPACE(state, ui->cur_x, ui->cur_y);
2619 ui->dragging = FALSE;
2621 if ((ui->srcx != ui->dotx || ui->srcy != ui->doty) &&
2622 SPACE(state, ui->srcx, ui->srcy).flags & F_TILE_ASSOC) {
2623 sprintf(buf, "%sU%d,%d", sep, ui->srcx, ui->srcy);
2626 if (sp->type == s_tile && !(sp->flags & F_DOT) && !(sp->flags & F_TILE_ASSOC)) {
2627 sprintf(buf + strlen(buf), "%sA%d,%d,%d,%d",
2628 sep, ui->cur_x, ui->cur_y, ui->dotx, ui->doty);
2631 } else if (sp->flags & F_DOT) {
2632 ui->dragging = TRUE;
2633 ui->dx = SCOORD(ui->cur_x);
2634 ui->dy = SCOORD(ui->cur_y);
2635 ui->dotx = ui->srcx = ui->cur_x;
2636 ui->doty = ui->srcy = ui->cur_y;
2638 } else if (sp->flags & F_TILE_ASSOC) {
2639 assert(sp->type == s_tile);
2640 ui->dragging = TRUE;
2641 ui->dx = SCOORD(ui->cur_x);
2642 ui->dy = SCOORD(ui->cur_y);
2643 ui->dotx = sp->dotx;
2644 ui->doty = sp->doty;
2645 ui->srcx = ui->cur_x;
2646 ui->srcy = ui->cur_y;
2648 } else if (sp->type == s_edge) {
2649 sprintf(buf, "E%d,%d", ui->cur_x, ui->cur_y);
2658 static int check_complete(const game_state *state, int *dsf, int *colours)
2660 int w = state->w, h = state->h;
2665 int minx, miny, maxx, maxy;
2671 dsf = snew_dsf(w*h);
2679 * During actual game play, completion checking is done on the
2680 * basis of the edges rather than the square associations. So
2681 * first we must go through the grid figuring out the connected
2682 * components into which the edges divide it.
2684 for (y = 0; y < h; y++)
2685 for (x = 0; x < w; x++) {
2686 if (y+1 < h && !(SPACE(state, 2*x+1, 2*y+2).flags & F_EDGE_SET))
2687 dsf_merge(dsf, y*w+x, (y+1)*w+x);
2688 if (x+1 < w && !(SPACE(state, 2*x+2, 2*y+1).flags & F_EDGE_SET))
2689 dsf_merge(dsf, y*w+x, y*w+(x+1));
2693 * That gives us our connected components. Now, for each
2694 * component, decide whether it's _valid_. A valid component is
2697 * - is 180-degree rotationally symmetric
2698 * - has a dot at its centre of symmetry
2699 * - has no other dots anywhere within it (including on its
2701 * - contains no internal edges (i.e. edges separating two
2702 * squares which are both part of the component).
2706 * First, go through the grid finding the bounding box of each
2709 sqdata = snewn(w*h, struct sqdata);
2710 for (i = 0; i < w*h; i++) {
2711 sqdata[i].minx = w+1;
2712 sqdata[i].miny = h+1;
2713 sqdata[i].maxx = sqdata[i].maxy = -1;
2714 sqdata[i].valid = FALSE;
2716 for (y = 0; y < h; y++)
2717 for (x = 0; x < w; x++) {
2718 i = dsf_canonify(dsf, y*w+x);
2719 if (sqdata[i].minx > x)
2721 if (sqdata[i].maxx < x)
2723 if (sqdata[i].miny > y)
2725 if (sqdata[i].maxy < y)
2727 sqdata[i].valid = TRUE;
2731 * Now we're in a position to loop over each actual component
2732 * and figure out where its centre of symmetry has to be if
2735 for (i = 0; i < w*h; i++)
2736 if (sqdata[i].valid) {
2738 cx = sqdata[i].cx = sqdata[i].minx + sqdata[i].maxx + 1;
2739 cy = sqdata[i].cy = sqdata[i].miny + sqdata[i].maxy + 1;
2740 if (!(SPACE(state, sqdata[i].cx, sqdata[i].cy).flags & F_DOT))
2741 sqdata[i].valid = FALSE; /* no dot at centre of symmetry */
2742 if (dsf_canonify(dsf, (cy-1)/2*w+(cx-1)/2) != i ||
2743 dsf_canonify(dsf, (cy)/2*w+(cx-1)/2) != i ||
2744 dsf_canonify(dsf, (cy-1)/2*w+(cx)/2) != i ||
2745 dsf_canonify(dsf, (cy)/2*w+(cx)/2) != i)
2746 sqdata[i].valid = FALSE; /* dot at cx,cy isn't ours */
2747 if (SPACE(state, sqdata[i].cx, sqdata[i].cy).flags & F_DOT_BLACK)
2748 sqdata[i].colour = 2;
2750 sqdata[i].colour = 1;
2754 * Now we loop over the whole grid again, this time finding
2755 * extraneous dots (any dot which wholly or partially overlaps
2756 * a square and is not at the centre of symmetry of that
2757 * square's component disqualifies the component from validity)
2758 * and extraneous edges (any edge separating two squares
2759 * belonging to the same component also disqualifies that
2762 for (y = 1; y < state->sy-1; y++)
2763 for (x = 1; x < state->sx-1; x++) {
2764 space *sp = &SPACE(state, x, y);
2766 if (sp->flags & F_DOT) {
2768 * There's a dot here. Use it to disqualify any
2769 * component which deserves it.
2772 for (cy = (y-1) >> 1; cy <= y >> 1; cy++)
2773 for (cx = (x-1) >> 1; cx <= x >> 1; cx++) {
2774 i = dsf_canonify(dsf, cy*w+cx);
2775 if (x != sqdata[i].cx || y != sqdata[i].cy)
2776 sqdata[i].valid = FALSE;
2780 if (sp->flags & F_EDGE_SET) {
2782 * There's an edge here. Use it to disqualify a
2783 * component if necessary.
2785 int cx1 = (x-1) >> 1, cx2 = x >> 1;
2786 int cy1 = (y-1) >> 1, cy2 = y >> 1;
2787 assert((cx1==cx2) ^ (cy1==cy2));
2788 i = dsf_canonify(dsf, cy1*w+cx1);
2789 if (i == dsf_canonify(dsf, cy2*w+cx2))
2790 sqdata[i].valid = FALSE;
2795 * And finally we test rotational symmetry: for each square in
2796 * the grid, find which component it's in, test that that
2797 * component also has a square in the symmetric position, and
2798 * disqualify it if it doesn't.
2800 for (y = 0; y < h; y++)
2801 for (x = 0; x < w; x++) {
2804 i = dsf_canonify(dsf, y*w+x);
2806 x2 = sqdata[i].cx - 1 - x;
2807 y2 = sqdata[i].cy - 1 - y;
2808 if (i != dsf_canonify(dsf, y2*w+x2))
2809 sqdata[i].valid = FALSE;
2813 * That's it. We now have all the connected components marked
2814 * as valid or not valid. So now we return a `colours' array if
2815 * we were asked for one, and also we return an overall
2816 * true/false value depending on whether _every_ square in the
2817 * grid is part of a valid component.
2820 for (i = 0; i < w*h; i++) {
2821 int ci = dsf_canonify(dsf, i);
2822 int thisok = sqdata[ci].valid;
2824 colours[i] = thisok ? sqdata[ci].colour : 0;
2825 ret = ret && thisok;
2835 static game_state *execute_move(const game_state *state, const char *move)
2837 int x, y, ax, ay, n, dx, dy;
2838 game_state *ret = dup_game(state);
2840 int currently_solving = FALSE;
2842 debug(("%s\n", move));
2846 if (c == 'E' || c == 'U' || c == 'M'
2848 || c == 'D' || c == 'd'
2852 if (sscanf(move, "%d,%d%n", &x, &y, &n) != 2 ||
2856 sp = &SPACE(ret, x, y);
2858 if (c == 'D' || c == 'd') {
2859 unsigned int currf, newf, maskf;
2861 if (!dot_is_possible(ret, sp, 1)) goto badmove;
2863 newf = F_DOT | (c == 'd' ? F_DOT_BLACK : 0);
2864 currf = GRID(ret, grid, x, y).flags;
2865 maskf = F_DOT | F_DOT_BLACK;
2866 /* if we clicked 'white dot':
2867 * white --> empty, empty --> white, black --> white.
2868 * if we clicked 'black dot':
2869 * black --> empty, empty --> black, white --> black.
2871 if (currf & maskf) {
2872 sp->flags &= ~maskf;
2873 if ((currf & maskf) != newf)
2877 sp->nassoc = 0; /* edit-mode disallows associations. */
2878 game_update_dots(ret);
2882 if (sp->type != s_edge) goto badmove;
2883 sp->flags ^= F_EDGE_SET;
2884 } else if (c == 'U') {
2885 if (sp->type != s_tile || !(sp->flags & F_TILE_ASSOC))
2887 /* The solver doesn't assume we'll mirror things */
2888 if (currently_solving)
2889 remove_assoc(ret, sp);
2891 remove_assoc_with_opposite(ret, sp);
2892 } else if (c == 'M') {
2893 if (!(sp->flags & F_DOT)) goto badmove;
2894 sp->flags ^= F_DOT_HOLD;
2897 } else if (c == 'A' || c == 'a') {
2899 if (sscanf(move, "%d,%d,%d,%d%n", &x, &y, &ax, &ay, &n) != 4 ||
2900 x < 1 || y < 1 || x >= (ret->sx-1) || y >= (ret->sy-1) ||
2901 ax < 1 || ay < 1 || ax >= (ret->sx-1) || ay >= (ret->sy-1))
2904 dot = &GRID(ret, grid, ax, ay);
2905 if (!(dot->flags & F_DOT))goto badmove;
2906 if (dot->flags & F_DOT_HOLD) goto badmove;
2908 for (dx = -1; dx <= 1; dx++) {
2909 for (dy = -1; dy <= 1; dy++) {
2910 sp = &GRID(ret, grid, x+dx, y+dy);
2911 if (sp->type != s_tile) continue;
2912 if (sp->flags & F_TILE_ASSOC) {
2913 space *dot = &SPACE(ret, sp->dotx, sp->doty);
2914 if (dot->flags & F_DOT_HOLD) continue;
2916 /* The solver doesn't assume we'll mirror things */
2917 if (currently_solving)
2918 add_assoc(ret, sp, dot);
2920 add_assoc_with_opposite(ret, sp, dot);
2925 } else if (c == 'C') {
2929 } else if (c == 'S') {
2931 ret->used_solve = 1;
2932 currently_solving = TRUE;
2941 if (check_complete(ret, NULL, NULL))
2950 /* ----------------------------------------------------------------------
2954 /* Lines will be much smaller size than squares; say, 1/8 the size?
2956 * Need a 'top-left corner of location XxY' to take this into account;
2957 * alternaticaly, that could give the middle of that location, and the
2958 * drawing code would just know the expected dimensions.
2960 * We also need something to take a click and work out what it was
2961 * we were interested in. Clicking on vertices is required because
2962 * we may want to drag from them, for example.
2965 static void game_compute_size(const game_params *params, int sz,
2968 struct { int tilesize, w, h; } ads, *ds = &ads;
2978 static void game_set_size(drawing *dr, game_drawstate *ds,
2979 const game_params *params, int sz)
2983 assert(TILE_SIZE > 0);
2986 ds->bl = blitter_new(dr, TILE_SIZE, TILE_SIZE);
2988 assert(!ds->blmirror);
2989 ds->blmirror = blitter_new(dr, TILE_SIZE, TILE_SIZE);
2991 assert(!ds->cur_bl);
2992 ds->cur_bl = blitter_new(dr, TILE_SIZE, TILE_SIZE);
2995 static float *game_colours(frontend *fe, int *ncolours)
2997 float *ret = snewn(3 * NCOLOURS, float);
3001 * We call game_mkhighlight to ensure the background colour
3002 * isn't completely white. We don't actually use the high- and
3003 * lowlight colours it generates.
3005 game_mkhighlight(fe, ret, COL_BACKGROUND, COL_WHITEBG, COL_BLACKBG);
3007 for (i = 0; i < 3; i++) {
3009 * Currently, white dots and white-background squares are
3012 ret[COL_WHITEDOT * 3 + i] = 1.0F;
3013 ret[COL_WHITEBG * 3 + i] = 1.0F;
3016 * But black-background squares are a dark grey, whereas
3017 * black dots are really black.
3019 ret[COL_BLACKDOT * 3 + i] = 0.0F;
3020 ret[COL_BLACKBG * 3 + i] = ret[COL_BACKGROUND * 3 + i] * 0.3F;
3023 * In unfilled squares, we draw a faint gridwork.
3025 ret[COL_GRID * 3 + i] = ret[COL_BACKGROUND * 3 + i] * 0.8F;
3028 * Edges and arrows are filled in in pure black.
3030 ret[COL_EDGE * 3 + i] = 0.0F;
3031 ret[COL_ARROW * 3 + i] = 0.0F;
3035 /* tinge the edit background to bluey */
3036 ret[COL_BACKGROUND * 3 + 0] = ret[COL_BACKGROUND * 3 + 0] * 0.8F;
3037 ret[COL_BACKGROUND * 3 + 1] = ret[COL_BACKGROUND * 3 + 0] * 0.8F;
3038 ret[COL_BACKGROUND * 3 + 2] = min(ret[COL_BACKGROUND * 3 + 0] * 1.4F, 1.0F);
3041 ret[COL_CURSOR * 3 + 0] = min(ret[COL_BACKGROUND * 3 + 0] * 1.4F, 1.0F);
3042 ret[COL_CURSOR * 3 + 1] = ret[COL_BACKGROUND * 3 + 0] * 0.8F;
3043 ret[COL_CURSOR * 3 + 2] = ret[COL_BACKGROUND * 3 + 0] * 0.8F;
3045 *ncolours = NCOLOURS;
3049 static game_drawstate *game_new_drawstate(drawing *dr, const game_state *state)
3051 struct game_drawstate *ds = snew(struct game_drawstate);
3058 ds->grid = snewn(ds->w*ds->h, unsigned long);
3059 for (i = 0; i < ds->w*ds->h; i++)
3060 ds->grid[i] = 0xFFFFFFFFUL;
3061 ds->dx = snewn(ds->w*ds->h, int);
3062 ds->dy = snewn(ds->w*ds->h, int);
3065 ds->blmirror = NULL;
3066 ds->dragging = FALSE;
3067 ds->dragx = ds->dragy = 0;
3069 ds->colour_scratch = snewn(ds->w * ds->h, int);
3072 ds->cx = ds->cy = 0;
3073 ds->cur_visible = 0;
3078 static void game_free_drawstate(drawing *dr, game_drawstate *ds)
3080 if (ds->cur_bl) blitter_free(dr, ds->cur_bl);
3081 sfree(ds->colour_scratch);
3082 if (ds->blmirror) blitter_free(dr, ds->blmirror);
3083 if (ds->bl) blitter_free(dr, ds->bl);
3090 #define DRAW_EDGE_L 0x0001
3091 #define DRAW_EDGE_R 0x0002
3092 #define DRAW_EDGE_U 0x0004
3093 #define DRAW_EDGE_D 0x0008
3094 #define DRAW_CORNER_UL 0x0010
3095 #define DRAW_CORNER_UR 0x0020
3096 #define DRAW_CORNER_DL 0x0040
3097 #define DRAW_CORNER_DR 0x0080
3098 #define DRAW_WHITE 0x0100
3099 #define DRAW_BLACK 0x0200
3100 #define DRAW_ARROW 0x0400
3101 #define DRAW_CURSOR 0x0800
3102 #define DOT_SHIFT_C 12
3103 #define DOT_SHIFT_M 2
3104 #define DOT_WHITE 1UL
3105 #define DOT_BLACK 2UL
3108 * Draw an arrow centred on (cx,cy), pointing in the direction
3109 * (ddx,ddy). (I.e. pointing at the point (cx+ddx, cy+ddy).
3111 static void draw_arrow(drawing *dr, game_drawstate *ds,
3112 int cx, int cy, int ddx, int ddy, int col)
3114 float vlen = (float)sqrt(ddx*ddx+ddy*ddy);
3115 float xdx = ddx/vlen, xdy = ddy/vlen;
3116 float ydx = -xdy, ydy = xdx;
3117 int e1x = cx + (int)(xdx*TILE_SIZE/3), e1y = cy + (int)(xdy*TILE_SIZE/3);
3118 int e2x = cx - (int)(xdx*TILE_SIZE/3), e2y = cy - (int)(xdy*TILE_SIZE/3);
3119 int adx = (int)((ydx-xdx)*TILE_SIZE/8), ady = (int)((ydy-xdy)*TILE_SIZE/8);
3120 int adx2 = (int)((-ydx-xdx)*TILE_SIZE/8), ady2 = (int)((-ydy-xdy)*TILE_SIZE/8);
3122 draw_line(dr, e1x, e1y, e2x, e2y, col);
3123 draw_line(dr, e1x, e1y, e1x+adx, e1y+ady, col);
3124 draw_line(dr, e1x, e1y, e1x+adx2, e1y+ady2, col);
3127 static void draw_square(drawing *dr, game_drawstate *ds, int x, int y,
3128 unsigned long flags, int ddx, int ddy)
3130 int lx = COORD(x), ly = COORD(y);
3134 clip(dr, lx, ly, TILE_SIZE, TILE_SIZE);
3137 * Draw the tile background.
3139 draw_rect(dr, lx, ly, TILE_SIZE, TILE_SIZE,
3140 (flags & DRAW_WHITE ? COL_WHITEBG :
3141 flags & DRAW_BLACK ? COL_BLACKBG : COL_BACKGROUND));
3146 gridcol = (flags & DRAW_BLACK ? COL_BLACKDOT : COL_GRID);
3147 draw_rect(dr, lx, ly, 1, TILE_SIZE, gridcol);
3148 draw_rect(dr, lx, ly, TILE_SIZE, 1, gridcol);
3151 * Draw the arrow, if present, or the cursor, if here.
3153 if (flags & DRAW_ARROW)
3154 draw_arrow(dr, ds, lx + TILE_SIZE/2, ly + TILE_SIZE/2, ddx, ddy,
3155 (flags & DRAW_CURSOR) ? COL_CURSOR : COL_ARROW);
3156 else if (flags & DRAW_CURSOR)
3157 draw_rect_outline(dr,
3158 lx + TILE_SIZE/2 - CURSOR_SIZE,
3159 ly + TILE_SIZE/2 - CURSOR_SIZE,
3160 2*CURSOR_SIZE+1, 2*CURSOR_SIZE+1,
3166 if (flags & DRAW_EDGE_L)
3167 draw_rect(dr, lx, ly, EDGE_THICKNESS, TILE_SIZE, COL_EDGE);
3168 if (flags & DRAW_EDGE_R)
3169 draw_rect(dr, lx + TILE_SIZE - EDGE_THICKNESS + 1, ly,
3170 EDGE_THICKNESS - 1, TILE_SIZE, COL_EDGE);
3171 if (flags & DRAW_EDGE_U)
3172 draw_rect(dr, lx, ly, TILE_SIZE, EDGE_THICKNESS, COL_EDGE);
3173 if (flags & DRAW_EDGE_D)
3174 draw_rect(dr, lx, ly + TILE_SIZE - EDGE_THICKNESS + 1,
3175 TILE_SIZE, EDGE_THICKNESS - 1, COL_EDGE);
3176 if (flags & DRAW_CORNER_UL)
3177 draw_rect(dr, lx, ly, EDGE_THICKNESS, EDGE_THICKNESS, COL_EDGE);
3178 if (flags & DRAW_CORNER_UR)
3179 draw_rect(dr, lx + TILE_SIZE - EDGE_THICKNESS + 1, ly,
3180 EDGE_THICKNESS - 1, EDGE_THICKNESS, COL_EDGE);
3181 if (flags & DRAW_CORNER_DL)
3182 draw_rect(dr, lx, ly + TILE_SIZE - EDGE_THICKNESS + 1,
3183 EDGE_THICKNESS, EDGE_THICKNESS - 1, COL_EDGE);
3184 if (flags & DRAW_CORNER_DR)
3185 draw_rect(dr, lx + TILE_SIZE - EDGE_THICKNESS + 1,
3186 ly + TILE_SIZE - EDGE_THICKNESS + 1,
3187 EDGE_THICKNESS - 1, EDGE_THICKNESS - 1, COL_EDGE);
3192 for (dy = 0; dy < 3; dy++)
3193 for (dx = 0; dx < 3; dx++) {
3194 int dotval = (flags >> (DOT_SHIFT_C + DOT_SHIFT_M*(dy*3+dx)));
3195 dotval &= (1 << DOT_SHIFT_M)-1;
3198 draw_circle(dr, lx+dx*TILE_SIZE/2, ly+dy*TILE_SIZE/2,
3200 (dotval == 1 ? COL_WHITEDOT : COL_BLACKDOT),
3205 draw_update(dr, lx, ly, TILE_SIZE, TILE_SIZE);
3208 static void calculate_opposite_point(const game_ui *ui,
3209 const game_drawstate *ds, const int x,
3210 const int y, int *oppositex,
3213 /* oppositex - dotx = dotx - x <=> oppositex = 2 * dotx - x */
3214 *oppositex = 2 * SCOORD(ui->dotx) - x;
3215 *oppositey = 2 * SCOORD(ui->doty) - y;
3218 static void game_redraw(drawing *dr, game_drawstate *ds,
3219 const game_state *oldstate, const game_state *state,
3220 int dir, const game_ui *ui,
3221 float animtime, float flashtime)
3223 int w = ds->w, h = ds->h;
3224 int x, y, flashing = FALSE;
3227 if (flashtime > 0) {
3228 int frame = (int)(flashtime / FLASH_TIME);
3229 flashing = (frame % 2 == 0);
3234 assert(ds->blmirror);
3235 calculate_opposite_point(ui, ds, ds->dragx + TILE_SIZE/2,
3236 ds->dragy + TILE_SIZE/2, &oppx, &oppy);
3237 oppx -= TILE_SIZE/2;
3238 oppy -= TILE_SIZE/2;
3239 blitter_load(dr, ds->bl, ds->dragx, ds->dragy);
3240 draw_update(dr, ds->dragx, ds->dragy, TILE_SIZE, TILE_SIZE);
3241 blitter_load(dr, ds->blmirror, oppx, oppy);
3242 draw_update(dr, oppx, oppy, TILE_SIZE, TILE_SIZE);
3243 ds->dragging = FALSE;
3245 if (ds->cur_visible) {
3247 blitter_load(dr, ds->cur_bl, ds->cx, ds->cy);
3248 draw_update(dr, ds->cx, ds->cy, CURSOR_SIZE*2+1, CURSOR_SIZE*2+1);
3249 ds->cur_visible = FALSE;
3253 draw_rect(dr, 0, 0, DRAW_WIDTH, DRAW_HEIGHT, COL_BACKGROUND);
3254 draw_rect(dr, BORDER - EDGE_THICKNESS + 1, BORDER - EDGE_THICKNESS + 1,
3255 w*TILE_SIZE + EDGE_THICKNESS*2 - 1,
3256 h*TILE_SIZE + EDGE_THICKNESS*2 - 1, COL_EDGE);
3257 draw_update(dr, 0, 0, DRAW_WIDTH, DRAW_HEIGHT);
3261 check_complete(state, NULL, ds->colour_scratch);
3263 for (y = 0; y < h; y++)
3264 for (x = 0; x < w; x++) {
3265 unsigned long flags = 0;
3266 int ddx = 0, ddy = 0;
3271 * Set up the flags for this square. Firstly, see if we
3274 if (SPACE(state, x*2, y*2+1).flags & F_EDGE_SET)
3275 flags |= DRAW_EDGE_L;
3276 if (SPACE(state, x*2+2, y*2+1).flags & F_EDGE_SET)
3277 flags |= DRAW_EDGE_R;
3278 if (SPACE(state, x*2+1, y*2).flags & F_EDGE_SET)
3279 flags |= DRAW_EDGE_U;
3280 if (SPACE(state, x*2+1, y*2+2).flags & F_EDGE_SET)
3281 flags |= DRAW_EDGE_D;
3284 * Also, mark corners of neighbouring edges.
3286 if ((x > 0 && SPACE(state, x*2-1, y*2).flags & F_EDGE_SET) ||
3287 (y > 0 && SPACE(state, x*2, y*2-1).flags & F_EDGE_SET))
3288 flags |= DRAW_CORNER_UL;
3289 if ((x+1 < w && SPACE(state, x*2+3, y*2).flags & F_EDGE_SET) ||
3290 (y > 0 && SPACE(state, x*2+2, y*2-1).flags & F_EDGE_SET))
3291 flags |= DRAW_CORNER_UR;
3292 if ((x > 0 && SPACE(state, x*2-1, y*2+2).flags & F_EDGE_SET) ||
3293 (y+1 < h && SPACE(state, x*2, y*2+3).flags & F_EDGE_SET))
3294 flags |= DRAW_CORNER_DL;
3295 if ((x+1 < w && SPACE(state, x*2+3, y*2+2).flags & F_EDGE_SET) ||
3296 (y+1 < h && SPACE(state, x*2+2, y*2+3).flags & F_EDGE_SET))
3297 flags |= DRAW_CORNER_DR;
3300 * If this square is part of a valid region, paint it
3301 * that region's colour. Exception: if we're flashing,
3302 * everything goes briefly back to background colour.
3304 sp = &SPACE(state, x*2+1, y*2+1);
3305 if (sp->flags & F_TILE_ASSOC) {
3306 opp = tile_opposite(state, sp);
3310 if (ds->colour_scratch[y*w+x] && !flashing) {
3311 flags |= (ds->colour_scratch[y*w+x] == 2 ?
3312 DRAW_BLACK : DRAW_WHITE);
3316 * If this square is associated with a dot but it isn't
3317 * part of a valid region, draw an arrow in it pointing
3318 * in the direction of that dot.
3320 * Exception: if this is the source point of an active
3321 * drag, we don't draw the arrow.
3323 if ((sp->flags & F_TILE_ASSOC) && !ds->colour_scratch[y*w+x]) {
3324 if (ui->dragging && ui->srcx == x*2+1 && ui->srcy == y*2+1) {
3325 /* tile is the source, don't do it */
3326 } else if (ui->dragging && opp && ui->srcx == opp->x && ui->srcy == opp->y) {
3327 /* opposite tile is the source, don't do it */
3328 } else if (sp->doty != y*2+1 || sp->dotx != x*2+1) {
3329 flags |= DRAW_ARROW;
3330 ddy = sp->doty - (y*2+1);
3331 ddx = sp->dotx - (x*2+1);
3336 * Now go through the nine possible places we could
3339 for (dy = 0; dy < 3; dy++)
3340 for (dx = 0; dx < 3; dx++) {
3341 sp = &SPACE(state, x*2+dx, y*2+dy);
3342 if (sp->flags & F_DOT) {
3343 unsigned long dotval = (sp->flags & F_DOT_BLACK ?
3344 DOT_BLACK : DOT_WHITE);
3345 flags |= dotval << (DOT_SHIFT_C +
3346 DOT_SHIFT_M*(dy*3+dx));
3351 * Now work out if we have to draw a cursor for this square;
3352 * cursors-on-lines are taken care of below.
3354 if (ui->cur_visible &&
3355 ui->cur_x == x*2+1 && ui->cur_y == y*2+1 &&
3356 !(SPACE(state, x*2+1, y*2+1).flags & F_DOT))
3357 flags |= DRAW_CURSOR;
3360 * Now we have everything we're going to need. Draw the
3363 if (ds->grid[y*w+x] != flags ||
3364 ds->dx[y*w+x] != ddx ||
3365 ds->dy[y*w+x] != ddy) {
3366 draw_square(dr, ds, x, y, flags, ddx, ddy);
3367 ds->grid[y*w+x] = flags;
3368 ds->dx[y*w+x] = ddx;
3369 ds->dy[y*w+x] = ddy;
3374 * Draw a cursor. This secondary blitter is much less invasive than trying
3375 * to fix up all of the rest of the code with sufficient flags to be able to
3376 * display this sensibly.
3378 if (ui->cur_visible) {
3379 space *sp = &SPACE(state, ui->cur_x, ui->cur_y);
3380 ds->cur_visible = TRUE;
3381 ds->cx = SCOORD(ui->cur_x) - CURSOR_SIZE;
3382 ds->cy = SCOORD(ui->cur_y) - CURSOR_SIZE;
3383 blitter_save(dr, ds->cur_bl, ds->cx, ds->cy);
3384 if (sp->flags & F_DOT) {
3385 /* draw a red dot (over the top of whatever would be there already) */
3386 draw_circle(dr, SCOORD(ui->cur_x), SCOORD(ui->cur_y), DOT_SIZE,
3387 COL_CURSOR, COL_BLACKDOT);
3388 } else if (sp->type != s_tile) {
3389 /* draw an edge/vertex square; tile cursors are dealt with above. */
3390 int dx = (ui->cur_x % 2) ? CURSOR_SIZE : CURSOR_SIZE/3;
3391 int dy = (ui->cur_y % 2) ? CURSOR_SIZE : CURSOR_SIZE/3;
3392 int x1 = SCOORD(ui->cur_x)-dx, y1 = SCOORD(ui->cur_y)-dy;
3393 int xs = dx*2+1, ys = dy*2+1;
3395 draw_rect(dr, x1, y1, xs, ys, COL_CURSOR);
3397 draw_update(dr, ds->cx, ds->cy, CURSOR_SIZE*2+1, CURSOR_SIZE*2+1);
3401 ds->dragging = TRUE;
3402 ds->dragx = ui->dx - TILE_SIZE/2;
3403 ds->dragy = ui->dy - TILE_SIZE/2;
3404 calculate_opposite_point(ui, ds, ui->dx, ui->dy, &oppx, &oppy);
3405 blitter_save(dr, ds->bl, ds->dragx, ds->dragy);
3406 blitter_save(dr, ds->blmirror, oppx - TILE_SIZE/2, oppy - TILE_SIZE/2);
3407 draw_arrow(dr, ds, ui->dx, ui->dy, SCOORD(ui->dotx) - ui->dx,
3408 SCOORD(ui->doty) - ui->dy, COL_ARROW);
3409 draw_arrow(dr, ds, oppx, oppy, SCOORD(ui->dotx) - oppx,
3410 SCOORD(ui->doty) - oppy, COL_ARROW);
3415 if (state->cdiff != -1)
3416 sprintf(buf, "Puzzle is %s.", galaxies_diffnames[state->cdiff]);
3419 status_bar(dr, buf);
3424 static float game_anim_length(const game_state *oldstate,
3425 const game_state *newstate, int dir, game_ui *ui)
3430 static float game_flash_length(const game_state *oldstate,
3431 const game_state *newstate, int dir, game_ui *ui)
3433 if ((!oldstate->completed && newstate->completed) &&
3434 !(newstate->used_solve))
3435 return 3 * FLASH_TIME;
3440 static int game_status(const game_state *state)
3442 return state->completed ? +1 : 0;
3445 static int game_timing_state(const game_state *state, game_ui *ui)
3451 static void game_print_size(const game_params *params, float *x, float *y)
3456 * 8mm squares by default. (There isn't all that much detail
3457 * that needs to go in each square.)
3459 game_compute_size(params, 800, &pw, &ph);
3464 static void game_print(drawing *dr, const game_state *state, int sz)
3466 int w = state->w, h = state->h;
3467 int white, black, blackish;
3471 int ncoords = 0, coordsize = 0;
3473 /* Ick: fake up `ds->tilesize' for macro expansion purposes */
3474 game_drawstate ads, *ds = &ads;
3477 white = print_mono_colour(dr, 1);
3478 black = print_mono_colour(dr, 0);
3479 blackish = print_hatched_colour(dr, HATCH_X);
3482 * Get the completion information.
3484 dsf = snewn(w * h, int);
3485 colours = snewn(w * h, int);
3486 check_complete(state, dsf, colours);
3491 print_line_width(dr, TILE_SIZE / 64);
3492 for (x = 1; x < w; x++)
3493 draw_line(dr, COORD(x), COORD(0), COORD(x), COORD(h), black);
3494 for (y = 1; y < h; y++)
3495 draw_line(dr, COORD(0), COORD(y), COORD(w), COORD(y), black);
3498 * Shade the completed regions. Just in case any particular
3499 * printing platform deals badly with adjacent
3500 * similarly-hatched regions, we'll fill each one as a single
3503 for (i = 0; i < w*h; i++) {
3504 j = dsf_canonify(dsf, i);
3505 if (colours[j] != 0) {
3509 * This is the first square we've run into belonging to
3510 * this polyomino, which means an edge of the polyomino
3511 * is certain to be to our left. (After we finish
3512 * tracing round it, we'll set the colours[] entry to
3513 * zero to prevent accidentally doing it again.)
3523 * We are currently sitting on square (x,y), which
3524 * we know to be in our polyomino, and we also know
3525 * that (x+dx,y+dy) is not. The way I visualise
3526 * this is that we're standing to the right of a
3527 * boundary line, stretching our left arm out to
3528 * point to the exterior square on the far side.
3532 * First, check if we've gone round the entire
3536 (x == i%w && y == i/w && dx == -1 && dy == 0))
3540 * Add to our coordinate list the coordinate
3541 * backwards and to the left of where we are.
3543 if (ncoords + 2 > coordsize) {
3544 coordsize = (ncoords * 3 / 2) + 64;
3545 coords = sresize(coords, coordsize, int);
3547 coords[ncoords++] = COORD((2*x+1 + dx + dy) / 2);
3548 coords[ncoords++] = COORD((2*y+1 + dy - dx) / 2);
3551 * Follow the edge round. If the square directly in
3552 * front of us is not part of the polyomino, we
3553 * turn right; if it is and so is the square in
3554 * front of (x+dx,y+dy), we turn left; otherwise we
3557 if (x-dy < 0 || x-dy >= w || y+dx < 0 || y+dx >= h ||
3558 dsf_canonify(dsf, (y+dx)*w+(x-dy)) != j) {
3563 } else if (x+dx-dy >= 0 && x+dx-dy < w &&
3564 y+dy+dx >= 0 && y+dy+dx < h &&
3565 dsf_canonify(dsf, (y+dy+dx)*w+(x+dx-dy)) == j) {
3582 * Now we have our polygon complete, so fill it.
3584 draw_polygon(dr, coords, ncoords/2,
3585 colours[j] == 2 ? blackish : -1, black);
3588 * And mark this polyomino as done.
3597 for (y = 0; y <= h; y++)
3598 for (x = 0; x <= w; x++) {
3599 if (x < w && SPACE(state, x*2+1, y*2).flags & F_EDGE_SET)
3600 draw_rect(dr, COORD(x)-EDGE_THICKNESS, COORD(y)-EDGE_THICKNESS,
3601 EDGE_THICKNESS * 2 + TILE_SIZE, EDGE_THICKNESS * 2,
3603 if (y < h && SPACE(state, x*2, y*2+1).flags & F_EDGE_SET)
3604 draw_rect(dr, COORD(x)-EDGE_THICKNESS, COORD(y)-EDGE_THICKNESS,
3605 EDGE_THICKNESS * 2, EDGE_THICKNESS * 2 + TILE_SIZE,
3612 for (y = 0; y <= 2*h; y++)
3613 for (x = 0; x <= 2*w; x++)
3614 if (SPACE(state, x, y).flags & F_DOT) {
3615 draw_circle(dr, (int)COORD(x/2.0), (int)COORD(y/2.0), DOT_SIZE,
3616 (SPACE(state, x, y).flags & F_DOT_BLACK ?
3617 black : white), black);
3627 #define thegame galaxies
3630 const struct game thegame = {
3631 "Galaxies", "games.galaxies", "galaxies",
3633 game_fetch_preset, NULL,
3638 TRUE, game_configure, custom_params,
3650 TRUE, game_can_format_as_text_now, game_text_format,
3658 PREFERRED_TILE_SIZE, game_compute_size, game_set_size,
3661 game_free_drawstate,
3667 FALSE, FALSE, NULL, NULL,
3668 TRUE, /* wants_statusbar */
3670 TRUE, FALSE, game_print_size, game_print,
3671 FALSE, /* wants_statusbar */
3673 FALSE, game_timing_state,
3674 REQUIRE_RBUTTON, /* flags */
3677 #ifdef STANDALONE_SOLVER
3683 static void usage_exit(const char *msg)
3686 fprintf(stderr, "%s: %s\n", quis, msg);
3687 fprintf(stderr, "Usage: %s [--seed SEED] --soak <params> | [game_id [game_id ...]]\n", quis);
3691 static void dump_state(game_state *state)
3693 char *temp = game_text_format(state);
3694 printf("%s\n", temp);
3698 static int gen(game_params *p, random_state *rs, int debug)
3705 solver_show_working = debug;
3707 printf("Generating a %dx%d %s puzzle.\n",
3708 p->w, p->h, galaxies_diffnames[p->diff]);
3710 desc = new_game_desc(p, rs, NULL, 0);
3711 state = new_game(NULL, p, desc);
3714 diff = solver_state(state, DIFF_UNREASONABLE);
3715 printf("Generated %s game %dx%d:%s\n",
3716 galaxies_diffnames[diff], p->w, p->h, desc);
3725 static void soak(game_params *p, random_state *rs)
3727 time_t tt_start, tt_now, tt_last;
3730 int diff, n = 0, i, diffs[DIFF_MAX], ndots = 0, nspaces = 0;
3733 solver_show_working = 0;
3735 tt_start = tt_now = time(NULL);
3736 for (i = 0; i < DIFF_MAX; i++) diffs[i] = 0;
3739 printf("Soak-generating a %dx%d grid, max. diff %s.\n",
3740 p->w, p->h, galaxies_diffnames[p->diff]);
3742 for (i = 0; i < DIFF_MAX; i++)
3743 printf("%s%s", (i == 0) ? "" : ", ", galaxies_diffnames[i]);
3747 desc = new_game_desc(p, rs, NULL, 0);
3748 st = new_game(NULL, p, desc);
3749 diff = solver_state(st, p->diff);
3750 nspaces += st->w*st->h;
3751 for (i = 0; i < st->sx*st->sy; i++)
3752 if (st->grid[i].flags & F_DOT) ndots++;
3758 tt_last = time(NULL);
3759 if (tt_last > tt_now) {
3761 printf("%d total, %3.1f/s, [",
3762 n, (double)n / ((double)tt_now - tt_start));
3763 for (i = 0; i < DIFF_MAX; i++)
3764 printf("%s%.1f%%", (i == 0) ? "" : ", ",
3765 100.0 * ((double)diffs[i] / (double)n));
3766 printf("], %.1f%% dots\n",
3767 100.0 * ((double)ndots / (double)nspaces));
3772 int main(int argc, char **argv)
3775 char *id = NULL, *desc;
3778 int diff, do_soak = 0, verbose = 0;
3780 time_t seed = time(NULL);
3783 while (--argc > 0) {
3785 if (!strcmp(p, "-v")) {
3787 } else if (!strcmp(p, "--seed")) {
3788 if (argc == 0) usage_exit("--seed needs an argument");
3789 seed = (time_t)atoi(*++argv);
3791 } else if (!strcmp(p, "--soak")) {
3793 } else if (*p == '-') {
3794 usage_exit("unrecognised option");
3802 p = default_params();
3803 rs = random_new((void*)&seed, sizeof(time_t));
3806 if (!id) usage_exit("need one argument for --soak");
3807 decode_params(p, *argv);
3814 p->w = random_upto(rs, 15) + 3;
3815 p->h = random_upto(rs, 15) + 3;
3816 p->diff = random_upto(rs, DIFF_UNREASONABLE);
3817 diff = gen(p, rs, 0);
3822 desc = strchr(id, ':');
3824 decode_params(p, id);
3825 gen(p, rs, verbose);
3828 solver_show_working = 1;
3831 decode_params(p, id);
3832 err = validate_desc(p, desc);
3834 fprintf(stderr, "%s: %s\n", argv[0], err);
3837 s = new_game(NULL, p, desc);
3838 diff = solver_state(s, DIFF_UNREASONABLE);
3840 printf("Puzzle is %s.\n", galaxies_diffnames[diff]);
3851 #ifdef STANDALONE_PICTURE_GENERATOR
3854 * Main program for the standalone picture generator. To use it,
3855 * simply provide it with an XBM-format bitmap file (note XBM, not
3856 * XPM) on standard input, and it will output a game ID in return.
3859 * $ ./galaxiespicture < badly-drawn-cat.xbm
3860 * 11x11:eloMBLzFeEzLNMWifhaWYdDbixCymBbBMLoDdewGg
3862 * If you want a puzzle with a non-standard difficulty level, pass
3863 * a partial parameters string as a command-line argument (e.g.
3864 * `./galaxiespicture du < foo.xbm', where `du' is the same suffix
3865 * which if it appeared in a random-seed game ID would set the
3866 * difficulty level to Unreasonable). However, be aware that if the
3867 * generator fails to produce an adequately difficult puzzle too
3868 * many times then it will give up and return an easier one (just
3869 * as it does during normal GUI play). To be sure you really have
3870 * the difficulty you asked for, use galaxiessolver to
3873 * (Perhaps I ought to include an option to make this standalone
3874 * generator carry on looping until it really does get the right
3875 * difficulty. Hmmm.)
3880 int main(int argc, char **argv)
3883 char *params, *desc;
3885 time_t seed = time(NULL);
3890 par = default_params();
3892 decode_params(par, argv[1]); /* get difficulty */
3893 par->w = par->h = -1;
3896 * Now read an XBM file from standard input. This is simple and
3897 * hacky and will do very little error detection, so don't feed
3902 while (fgets(buf, sizeof(buf), stdin)) {
3903 buf[strcspn(buf, "\r\n")] = '\0';
3904 if (!strncmp(buf, "#define", 7)) {
3906 * Lines starting `#define' give the width and height.
3908 char *num = buf + strlen(buf);
3911 while (num > buf && isdigit((unsigned char)num[-1]))
3914 while (symend > buf && isspace((unsigned char)symend[-1]))
3917 if (symend-5 >= buf && !strncmp(symend-5, "width", 5))
3919 else if (symend-6 >= buf && !strncmp(symend-6, "height", 6))
3923 * Otherwise, break the string up into words and take
3924 * any word of the form `0x' plus hex digits to be a
3927 char *p, *wordstart;
3930 if (par->w < 0 || par->h < 0) {
3931 printf("failed to read width and height\n");
3934 picture = snewn(par->w * par->h, int);
3935 for (i = 0; i < par->w * par->h; i++)
3941 while (*p && (*p == ',' || isspace((unsigned char)*p)))
3944 while (*p && !(*p == ',' || *p == '}' ||
3945 isspace((unsigned char)*p)))
3950 if (wordstart[0] == '0' &&
3951 (wordstart[1] == 'x' || wordstart[1] == 'X') &&
3952 !wordstart[2 + strspn(wordstart+2,
3953 "0123456789abcdefABCDEF")]) {
3954 unsigned long byte = strtoul(wordstart+2, NULL, 16);
3955 for (i = 0; i < 8; i++) {
3956 int bit = (byte >> i) & 1;
3957 if (y < par->h && x < par->w)
3958 picture[y * par->w + x] = bit;
3971 for (i = 0; i < par->w * par->h; i++)
3972 if (picture[i] < 0) {
3973 fprintf(stderr, "failed to read enough bitmap data\n");
3977 rs = random_new((void*)&seed, sizeof(time_t));
3979 desc = new_game_desc(par, rs, NULL, FALSE);
3980 params = encode_params(par, FALSE);
3981 printf("%s:%s\n", params, desc);
3993 /* vim: set shiftwidth=4 tabstop=8: */