tsiry-sandratraina.com
A modern Music Player Daemon based on Rockbox open source high quality audio player
libadwaita
audio
rust
zig
deno
mpris
rockbox
mpd
1/*
2 * galaxies.c: implementation of 'Tentai Show' from Nikoli,
3 * also sometimes called 'Spiral Galaxies'.
4 *
5 * Notes:
6 *
7 * Grid is stored as size (2n-1), holding edges as well as spaces
8 * (and thus vertices too, at edge intersections).
9 *
10 * Any dot will thus be positioned at one of our grid points,
11 * which saves any faffing with half-of-a-square stuff.
12 *
13 * Edges have on/off state; obviously the actual edges of the
14 * board are fixed to on, and everything else starts as off.
15 *
16 * Future solver directions:
17 *
18 * - Non-local version of the exclave extension? Suppose you have an
19 * exclave with multiple potential paths back home, but all of them
20 * go through the same tile somewhere in the middle of the path.
21 * Then _that_ critical square can be assigned to the home dot,
22 * even if we don't yet know the details of the path from it to
23 * either existing region.
24 *
25 * - Permit non-simply-connected puzzle instances in sub-Unreasonable
26 * mode? Even the simplest case 5x3:ubb is graded Unreasonable at
27 * present, because we have no solution technique short of
28 * recursion that can handle it.
29 *
30 * The reasoning a human uses for that puzzle is to observe that
31 * the centre left square has to connect to the centre dot, so it
32 * must have _some_ path back there. It could go round either side
33 * of the dot in the way. But _whichever_ way it goes, that rules
34 * out the left dot extending to the squares above and below it,
35 * because if it did that, that would block _both_ routes back to
36 * the centre.
37 *
38 * But the exclave-extending deduction we have at present is only
39 * capable of extending an exclave with _one_ liberty. This has
40 * two, so the only technique we have available is to try them one
41 * by one via recursion.
42 *
43 * My vague plan to fix this would be to re-run the exclave
44 * extension on a per-dot basis (probably after working out a
45 * non-local version as described above): instead of trying to find
46 * all exclaves at once, try it for one exclave at a time, or
47 * perhaps all exclaves relating to a particular home dot H. The
48 * point of this is that then you could spot pairs of squares with
49 * _two_ possible dots, one of which is H, and which are opposite
50 * to each other with respect to their other dot D (such as the
51 * squares above/below the left dot in this example). And then you
52 * merge those into one vertex of the connectivity graph, on the
53 * grounds that they're either both H or both D - and _then_ you
54 * have an exclave with only one path back home, and can make
55 * progress.
56 *
57 * Bugs:
58 *
59 * Notable puzzle IDs:
60 *
61 * Nikoli's example [web site has wrong highlighting]
62 * (at http://www.nikoli.co.jp/en/puzzles/astronomical_show/):
63 * 5x5:eBbbMlaBbOEnf
64 *
65 * The 'spiral galaxies puzzles are NP-complete' paper
66 * (at http://www.stetson.edu/~efriedma/papers/spiral.pdf):
67 * 7x7:chpgdqqqoezdddki
68 *
69 * Puzzle competition pdf examples
70 * (at http://www.puzzleratings.org/Yurekli2006puz.pdf):
71 * 6x6:EDbaMucCohbrecEi
72 * 10x10:beFbufEEzowDlxldibMHezBQzCdcFzjlci
73 * 13x13:dCemIHFFkJajjgDfdbdBzdzEgjccoPOcztHjBczLDjczqktJjmpreivvNcggFi
74 *
75 */
76
77#include <stdio.h>
78#include <stdlib.h>
79#include <string.h>
80#include <assert.h>
81#include <ctype.h>
82#include <limits.h>
83#ifdef NO_TGMATH_H
84# include <math.h>
85#else
86# include <tgmath.h>
87#endif
88
89#include "puzzles.h"
90
91#ifdef DEBUGGING
92#define solvep debug
93#elif defined STANDALONE_SOLVER
94static bool solver_show_working;
95#define solvep(x) do { if (solver_show_working) { printf x; } } while(0)
96#else
97#define solvep(x) ((void)0)
98#endif
99
100#ifdef STANDALONE_PICTURE_GENERATOR
101/*
102 * Dirty hack to enable the generator to construct a game ID which
103 * solves to a specified black-and-white bitmap. We define a global
104 * variable here which gives the desired colour of each square, and
105 * we arrange that the grid generator never merges squares of
106 * different colours.
107 *
108 * The bitmap as stored here is a simple int array (at these sizes
109 * it isn't worth doing fiddly bit-packing). picture[y*w+x] is 1
110 * iff the pixel at (x,y) is intended to be black.
111 *
112 * (It might be nice to be able to specify some pixels as
113 * don't-care, to give the generator more leeway. But that might be
114 * fiddly.)
115 */
116static int *picture;
117#endif
118
119enum {
120 COL_BACKGROUND,
121 COL_WHITEBG,
122 COL_BLACKBG,
123 COL_WHITEDOT,
124 COL_BLACKDOT,
125 COL_GRID,
126 COL_EDGE,
127 COL_ARROW,
128 COL_CURSOR,
129 NCOLOURS
130};
131
132#define DIFFLIST(A) \
133 A(NORMAL,Normal,n) \
134 A(UNREASONABLE,Unreasonable,u)
135
136#define ENUM(upper,title,lower) DIFF_ ## upper,
137#define TITLE(upper,title,lower) #title,
138#define ENCODE(upper,title,lower) #lower
139#define CONFIG(upper,title,lower) ":" #title
140enum { DIFFLIST(ENUM)
141 DIFF_IMPOSSIBLE, DIFF_AMBIGUOUS, DIFF_UNFINISHED, DIFF_MAX };
142static char const *const galaxies_diffnames[] = {
143 DIFFLIST(TITLE) "Impossible", "Ambiguous", "Unfinished" };
144static char const galaxies_diffchars[] = DIFFLIST(ENCODE);
145#define DIFFCONFIG DIFFLIST(CONFIG)
146
147struct game_params {
148 /* X and Y is the area of the board as seen by
149 * the user, not the (2n+1) area the game uses. */
150 int w, h, diff;
151};
152
153enum { s_tile, s_edge, s_vertex };
154
155#define F_DOT 1 /* there's a dot here */
156#define F_EDGE_SET 2 /* the edge is set */
157#define F_TILE_ASSOC 4 /* this tile is associated with a dot. */
158#define F_DOT_BLACK 8 /* (ui only) dot is black. */
159#define F_MARK 16 /* scratch flag */
160#define F_REACHABLE 32
161#define F_SCRATCH 64
162#define F_MULTIPLE 128
163#define F_DOT_HOLD 256
164#define F_GOOD 512
165
166typedef struct space {
167 int x, y; /* its position */
168 int type;
169 unsigned int flags;
170 int dotx, doty; /* if flags & F_TILE_ASSOC */
171 int nassoc; /* if flags & F_DOT */
172} space;
173
174#define INGRID(s,x,y) ((x) >= 0 && (y) >= 0 && \
175 (x) < (state)->sx && (y) < (state)->sy)
176#define INUI(s,x,y) ((x) > 0 && (y) > 0 && \
177 (x) < ((state)->sx-1) && (y) < ((state)->sy-1))
178
179#define GRID(s,g,x,y) ((s)->g[((y)*(s)->sx)+(x)])
180#define SPACE(s,x,y) GRID(s,grid,x,y)
181
182struct game_state {
183 int w, h; /* size from params */
184 int sx, sy; /* allocated size, (2x-1)*(2y-1) */
185 space *grid;
186 bool completed, used_solve;
187 int ndots;
188 space **dots;
189
190 midend *me; /* to call supersede_game_desc */
191 int cdiff; /* difficulty of current puzzle (for status bar),
192 or -1 if stale. */
193};
194
195static bool check_complete(const game_state *state, DSF *dsf, int *colours);
196static int solver_state_inner(game_state *state, int maxdiff, int depth);
197static int solver_state(game_state *state, int maxdiff);
198static int solver_obvious(game_state *state);
199static int solver_obvious_dot(game_state *state, space *dot);
200static space *space_opposite_dot(const game_state *state, const space *sp,
201 const space *dot);
202static space *tile_opposite(const game_state *state, const space *sp);
203static game_state *execute_move(const game_state *state, const char *move);
204
205/* ----------------------------------------------------------
206 * Game parameters and presets
207 */
208
209/* make up some sensible default sizes */
210
211#define DEFAULT_PRESET 0
212
213static const game_params galaxies_presets[] = {
214 { 7, 7, DIFF_NORMAL },
215 { 7, 7, DIFF_UNREASONABLE },
216 { 10, 10, DIFF_NORMAL },
217 { 10, 10, DIFF_UNREASONABLE },
218 { 15, 15, DIFF_NORMAL },
219 { 15, 15, DIFF_UNREASONABLE },
220};
221
222static bool game_fetch_preset(int i, char **name, game_params **params)
223{
224 game_params *ret;
225 char buf[80];
226
227 if (i < 0 || i >= lenof(galaxies_presets))
228 return false;
229
230 ret = snew(game_params);
231 *ret = galaxies_presets[i]; /* structure copy */
232
233 sprintf(buf, "%dx%d %s", ret->w, ret->h,
234 galaxies_diffnames[ret->diff]);
235
236 if (name) *name = dupstr(buf);
237 *params = ret;
238 return true;
239}
240
241static game_params *default_params(void)
242{
243 game_params *ret;
244 game_fetch_preset(DEFAULT_PRESET, NULL, &ret);
245 return ret;
246}
247
248static void free_params(game_params *params)
249{
250 sfree(params);
251}
252
253static game_params *dup_params(const game_params *params)
254{
255 game_params *ret = snew(game_params);
256 *ret = *params; /* structure copy */
257 return ret;
258}
259
260static void decode_params(game_params *params, char const *string)
261{
262 params->h = params->w = atoi(string);
263 params->diff = DIFF_NORMAL;
264 while (*string && isdigit((unsigned char)*string)) string++;
265 if (*string == 'x') {
266 string++;
267 params->h = atoi(string);
268 while (*string && isdigit((unsigned char)*string)) string++;
269 }
270 if (*string == 'd') {
271 int i;
272 string++;
273 for (i = 0; i <= DIFF_UNREASONABLE; i++)
274 if (*string == galaxies_diffchars[i])
275 params->diff = i;
276 if (*string) string++;
277 }
278}
279
280static char *encode_params(const game_params *params, bool full)
281{
282 char str[80];
283 sprintf(str, "%dx%d", params->w, params->h);
284 if (full)
285 sprintf(str + strlen(str), "d%c", galaxies_diffchars[params->diff]);
286 return dupstr(str);
287}
288
289static config_item *game_configure(const game_params *params)
290{
291 config_item *ret;
292 char buf[80];
293
294 ret = snewn(4, config_item);
295
296 ret[0].name = "Width";
297 ret[0].type = C_STRING;
298 sprintf(buf, "%d", params->w);
299 ret[0].u.string.sval = dupstr(buf);
300
301 ret[1].name = "Height";
302 ret[1].type = C_STRING;
303 sprintf(buf, "%d", params->h);
304 ret[1].u.string.sval = dupstr(buf);
305
306 ret[2].name = "Difficulty";
307 ret[2].type = C_CHOICES;
308 ret[2].u.choices.choicenames = DIFFCONFIG;
309 ret[2].u.choices.selected = params->diff;
310
311 ret[3].name = NULL;
312 ret[3].type = C_END;
313
314 return ret;
315}
316
317static game_params *custom_params(const config_item *cfg)
318{
319 game_params *ret = snew(game_params);
320
321 ret->w = atoi(cfg[0].u.string.sval);
322 ret->h = atoi(cfg[1].u.string.sval);
323 ret->diff = cfg[2].u.choices.selected;
324
325 return ret;
326}
327
328static const char *validate_params(const game_params *params, bool full)
329{
330 if (params->w < 3 || params->h < 3)
331 return "Width and height must both be at least 3";
332 if (params->w > INT_MAX / 2 || params->h > INT_MAX / 2 ||
333 params->w > (INT_MAX - params->w*2 - params->h*2 - 1) / 4 / params->h)
334 return "Width times height must not be unreasonably large";
335
336 /*
337 * This shouldn't be able to happen at all, since decode_params
338 * and custom_params will never generate anything that isn't
339 * within range.
340 */
341 assert(params->diff <= DIFF_UNREASONABLE);
342
343 return NULL;
344}
345
346/* ----------------------------------------------------------
347 * Game utility functions.
348 */
349
350static void add_dot(space *space) {
351 assert(!(space->flags & F_DOT));
352 space->flags |= F_DOT;
353 space->nassoc = 0;
354}
355
356static void remove_dot(space *space) {
357 assert(space->flags & F_DOT);
358 space->flags &= ~F_DOT;
359}
360
361static void remove_assoc(const game_state *state, space *tile) {
362 if (tile->flags & F_TILE_ASSOC) {
363 SPACE(state, tile->dotx, tile->doty).nassoc--;
364 tile->flags &= ~F_TILE_ASSOC;
365 tile->dotx = -1;
366 tile->doty = -1;
367 }
368}
369
370static void remove_assoc_with_opposite(game_state *state, space *tile) {
371 space *opposite;
372
373 if (!(tile->flags & F_TILE_ASSOC)) {
374 return;
375 }
376
377 opposite = tile_opposite(state, tile);
378 remove_assoc(state, tile);
379
380 if (opposite != NULL && opposite != tile) {
381 remove_assoc(state, opposite);
382 }
383}
384
385static void add_assoc(const game_state *state, space *tile, space *dot) {
386 remove_assoc(state, tile);
387
388#ifdef STANDALONE_PICTURE_GENERATOR
389 if (picture)
390 assert(!picture[(tile->y/2) * state->w + (tile->x/2)] ==
391 !(dot->flags & F_DOT_BLACK));
392#endif
393 tile->flags |= F_TILE_ASSOC;
394 tile->dotx = dot->x;
395 tile->doty = dot->y;
396 dot->nassoc++;
397 /*debug(("add_assoc sp %d %d --> dot %d,%d, new nassoc %d.\n",
398 tile->x, tile->y, dot->x, dot->y, dot->nassoc));*/
399}
400
401static bool ok_to_add_assoc_with_opposite_internal(
402 const game_state *state, space *tile, space *opposite)
403{
404 int *colors;
405 bool toret;
406
407 if (tile->type != s_tile)
408 return false;
409 if (tile->flags & F_DOT)
410 return false;
411 if (opposite == NULL)
412 return false;
413 if (opposite->flags & F_DOT)
414 return false;
415
416 toret = true;
417 colors = snewn(state->w * state->h, int);
418 check_complete(state, NULL, colors);
419
420 if (colors[(tile->y - 1)/2 * state->w + (tile->x - 1)/2])
421 toret = false;
422 if (colors[(opposite->y - 1)/2 * state->w + (opposite->x - 1)/2])
423 toret = false;
424
425 sfree(colors);
426 return toret;
427}
428
429#ifndef EDITOR
430static bool ok_to_add_assoc_with_opposite(
431 const game_state *state, space *tile, space *dot)
432{
433 space *opposite = space_opposite_dot(state, tile, dot);
434 return ok_to_add_assoc_with_opposite_internal(state, tile, opposite);
435}
436#endif
437
438static void add_assoc_with_opposite(game_state *state, space *tile, space *dot) {
439 space *opposite = space_opposite_dot(state, tile, dot);
440
441 if(opposite && ok_to_add_assoc_with_opposite_internal(
442 state, tile, opposite))
443 {
444 remove_assoc_with_opposite(state, tile);
445 add_assoc(state, tile, dot);
446 remove_assoc_with_opposite(state, opposite);
447 add_assoc(state, opposite, dot);
448 }
449}
450
451#ifndef EDITOR
452static space *sp2dot(const game_state *state, int x, int y)
453{
454 space *sp = &SPACE(state, x, y);
455 if (!(sp->flags & F_TILE_ASSOC)) return NULL;
456 return &SPACE(state, sp->dotx, sp->doty);
457}
458#endif
459
460#define IS_VERTICAL_EDGE(x) ((x % 2) == 0)
461
462static bool game_can_format_as_text_now(const game_params *params)
463{
464 return true;
465}
466
467static char *encode_game(const game_state *state);
468
469static char *game_text_format(const game_state *state)
470{
471#ifdef EDITOR
472 game_params par;
473 char *params, *desc, *ret;
474 par.w = state->w;
475 par.h = state->h;
476 par.diff = DIFF_MAX; /* shouldn't be used */
477 params = encode_params(&par, false);
478 desc = encode_game(state);
479 ret = snewn(strlen(params) + strlen(desc) + 2, char);
480 sprintf(ret, "%s:%s", params, desc);
481 sfree(params);
482 sfree(desc);
483 return ret;
484#else
485 int maxlen = (state->sx+1)*state->sy, x, y;
486 char *ret, *p;
487 space *sp;
488
489 ret = snewn(maxlen+1, char);
490 p = ret;
491
492 for (y = 0; y < state->sy; y++) {
493 for (x = 0; x < state->sx; x++) {
494 sp = &SPACE(state, x, y);
495 if (sp->flags & F_DOT)
496 *p++ = 'o';
497#if 0
498 else if (sp->flags & (F_REACHABLE|F_MULTIPLE|F_MARK))
499 *p++ = (sp->flags & F_MULTIPLE) ? 'M' :
500 (sp->flags & F_REACHABLE) ? 'R' : 'X';
501#endif
502 else {
503 switch (sp->type) {
504 case s_tile:
505 if (sp->flags & F_TILE_ASSOC) {
506 space *dot = sp2dot(state, sp->x, sp->y);
507 if (dot && dot->flags & F_DOT)
508 *p++ = (dot->flags & F_DOT_BLACK) ? 'B' : 'W';
509 else
510 *p++ = '?'; /* association with not-a-dot. */
511 } else
512 *p++ = ' ';
513 break;
514
515 case s_vertex:
516 *p++ = '+';
517 break;
518
519 case s_edge:
520 if (sp->flags & F_EDGE_SET)
521 *p++ = (IS_VERTICAL_EDGE(x)) ? '|' : '-';
522 else
523 *p++ = ' ';
524 break;
525
526 default:
527 assert(!"shouldn't get here!");
528 }
529 }
530 }
531 *p++ = '\n';
532 }
533
534 assert(p - ret == maxlen);
535 *p = '\0';
536
537 return ret;
538#endif
539}
540
541static void dbg_state(const game_state *state)
542{
543#ifdef DEBUGGING
544 char *temp = game_text_format(state);
545 debug(("%s\n", temp));
546 sfree(temp);
547#endif
548}
549
550/* Space-enumeration callbacks should all return 1 for 'progress made',
551 * -1 for 'impossible', and 0 otherwise. */
552typedef int (*space_cb)(game_state *state, space *sp, void *ctx);
553
554#define IMPOSSIBLE_QUITS 1
555
556static int foreach_sub(game_state *state, space_cb cb, unsigned int f,
557 void *ctx, int startx, int starty)
558{
559 int x, y, ret;
560 bool progress = false, impossible = false;
561 space *sp;
562
563 for (y = starty; y < state->sy; y += 2) {
564 sp = &SPACE(state, startx, y);
565 for (x = startx; x < state->sx; x += 2) {
566 ret = cb(state, sp, ctx);
567 if (ret == -1) {
568 if (f & IMPOSSIBLE_QUITS) return -1;
569 impossible = true;
570 } else if (ret == 1) {
571 progress = true;
572 }
573 sp += 2;
574 }
575 }
576 return impossible ? -1 : progress ? 1 : 0;
577}
578
579static int foreach_tile(game_state *state, space_cb cb, unsigned int f,
580 void *ctx)
581{
582 return foreach_sub(state, cb, f, ctx, 1, 1);
583}
584
585static int foreach_edge(game_state *state, space_cb cb, unsigned int f,
586 void *ctx)
587{
588 int ret1, ret2;
589
590 ret1 = foreach_sub(state, cb, f, ctx, 0, 1);
591 ret2 = foreach_sub(state, cb, f, ctx, 1, 0);
592
593 if (ret1 == -1 || ret2 == -1) return -1;
594 return (ret1 || ret2) ? 1 : 0;
595}
596
597#if 0
598static int foreach_vertex(game_state *state, space_cb cb, unsigned int f,
599 void *ctx)
600{
601 return foreach_sub(state, cb, f, ctx, 0, 0);
602}
603#endif
604
605#if 0
606static int is_same_assoc(game_state *state,
607 int x1, int y1, int x2, int y2)
608{
609 space *s1, *s2;
610
611 if (!INGRID(state, x1, y1) || !INGRID(state, x2, y2))
612 return 0;
613
614 s1 = &SPACE(state, x1, y1);
615 s2 = &SPACE(state, x2, y2);
616 assert(s1->type == s_tile && s2->type == s_tile);
617 if ((s1->flags & F_TILE_ASSOC) && (s2->flags & F_TILE_ASSOC) &&
618 s1->dotx == s2->dotx && s1->doty == s2->doty)
619 return 1;
620 return 0; /* 0 if not same or not both associated. */
621}
622#endif
623
624#if 0
625static int edges_into_vertex(game_state *state,
626 int x, int y)
627{
628 int dx, dy, nx, ny, count = 0;
629
630 assert(SPACE(state, x, y).type == s_vertex);
631 for (dx = -1; dx <= 1; dx++) {
632 for (dy = -1; dy <= 1; dy++) {
633 if (dx != 0 && dy != 0) continue;
634 if (dx == 0 && dy == 0) continue;
635
636 nx = x+dx; ny = y+dy;
637 if (!INGRID(state, nx, ny)) continue;
638 assert(SPACE(state, nx, ny).type == s_edge);
639 if (SPACE(state, nx, ny).flags & F_EDGE_SET)
640 count++;
641 }
642 }
643 return count;
644}
645#endif
646
647static space *space_opposite_dot(const game_state *state, const space *sp,
648 const space *dot)
649{
650 int dx, dy, tx, ty;
651 space *sp2;
652
653 dx = sp->x - dot->x;
654 dy = sp->y - dot->y;
655 tx = dot->x - dx;
656 ty = dot->y - dy;
657 if (!INGRID(state, tx, ty)) return NULL;
658
659 sp2 = &SPACE(state, tx, ty);
660 assert(sp2->type == sp->type);
661 return sp2;
662}
663
664static space *tile_opposite(const game_state *state, const space *sp)
665{
666 space *dot;
667
668 assert(sp->flags & F_TILE_ASSOC);
669 dot = &SPACE(state, sp->dotx, sp->doty);
670 return space_opposite_dot(state, sp, dot);
671}
672
673static bool dotfortile(game_state *state, space *tile, space *dot)
674{
675 space *tile_opp = space_opposite_dot(state, tile, dot);
676
677 if (!tile_opp) return false; /* opposite would be off grid */
678 if (tile_opp->flags & F_TILE_ASSOC &&
679 (tile_opp->dotx != dot->x || tile_opp->doty != dot->y))
680 return false; /* opposite already associated with diff. dot */
681 return true;
682}
683
684static void adjacencies(game_state *state, space *sp, space **a1s, space **a2s)
685{
686 int dxs[4] = {-1, 1, 0, 0}, dys[4] = {0, 0, -1, 1};
687 int n, x, y;
688
689 /* this function needs optimising. */
690
691 for (n = 0; n < 4; n++) {
692 x = sp->x+dxs[n];
693 y = sp->y+dys[n];
694
695 if (INGRID(state, x, y)) {
696 a1s[n] = &SPACE(state, x, y);
697
698 x += dxs[n]; y += dys[n];
699
700 if (INGRID(state, x, y))
701 a2s[n] = &SPACE(state, x, y);
702 else
703 a2s[n] = NULL;
704 } else {
705 a1s[n] = a2s[n] = NULL;
706 }
707 }
708}
709
710static bool outline_tile_fordot(game_state *state, space *tile, bool mark)
711{
712 space *tadj[4], *eadj[4];
713 int i;
714 bool didsth = false, edge, same;
715
716 assert(tile->type == s_tile);
717 adjacencies(state, tile, eadj, tadj);
718 for (i = 0; i < 4; i++) {
719 if (!eadj[i]) continue;
720
721 edge = eadj[i]->flags & F_EDGE_SET;
722 if (tadj[i]) {
723 if (!(tile->flags & F_TILE_ASSOC))
724 same = !(tadj[i]->flags & F_TILE_ASSOC);
725 else
726 same = ((tadj[i]->flags & F_TILE_ASSOC) &&
727 tile->dotx == tadj[i]->dotx &&
728 tile->doty == tadj[i]->doty);
729 } else
730 same = false;
731
732 if (!edge && !same) {
733 if (mark) eadj[i]->flags |= F_EDGE_SET;
734 didsth = true;
735 } else if (edge && same) {
736 if (mark) eadj[i]->flags &= ~F_EDGE_SET;
737 didsth = true;
738 }
739 }
740 return didsth;
741}
742
743static void tiles_from_edge(game_state *state, space *sp, space **ts)
744{
745 int xs[2], ys[2];
746
747 if (IS_VERTICAL_EDGE(sp->x)) {
748 xs[0] = sp->x-1; ys[0] = sp->y;
749 xs[1] = sp->x+1; ys[1] = sp->y;
750 } else {
751 xs[0] = sp->x; ys[0] = sp->y-1;
752 xs[1] = sp->x; ys[1] = sp->y+1;
753 }
754 ts[0] = INGRID(state, xs[0], ys[0]) ? &SPACE(state, xs[0], ys[0]) : NULL;
755 ts[1] = INGRID(state, xs[1], ys[1]) ? &SPACE(state, xs[1], ys[1]) : NULL;
756}
757
758/* Returns a move string for use by 'solve', including the initial
759 * 'S' if issolve is true. */
760static char *diff_game(const game_state *src, const game_state *dest,
761 bool issolve, int set_cdiff)
762{
763 int movelen = 0, movesize = 256, x, y, len;
764 char *move = snewn(movesize, char), buf[80];
765 const char *sep = "";
766 char achar = issolve ? 'a' : 'A';
767 space *sps, *spd;
768
769 assert(src->sx == dest->sx && src->sy == dest->sy);
770
771 if (issolve) {
772 move[movelen++] = 'S';
773 sep = ";";
774 }
775#ifdef EDITOR
776 if (set_cdiff >= 0) {
777 switch (set_cdiff) {
778 case DIFF_IMPOSSIBLE:
779 movelen += sprintf(move+movelen, "%sII", sep);
780 break;
781 case DIFF_AMBIGUOUS:
782 movelen += sprintf(move+movelen, "%sIA", sep);
783 break;
784 case DIFF_UNFINISHED:
785 movelen += sprintf(move+movelen, "%sIU", sep);
786 break;
787 default:
788 movelen += sprintf(move+movelen, "%si%c",
789 sep, galaxies_diffchars[set_cdiff]);
790 break;
791 }
792 sep = ";";
793 }
794#endif
795 move[movelen] = '\0';
796 for (x = 0; x < src->sx; x++) {
797 for (y = 0; y < src->sy; y++) {
798 sps = &SPACE(src, x, y);
799 spd = &SPACE(dest, x, y);
800
801 assert(sps->type == spd->type);
802
803 len = 0;
804 if (sps->type == s_tile) {
805 if ((sps->flags & F_TILE_ASSOC) &&
806 (spd->flags & F_TILE_ASSOC)) {
807 if (sps->dotx != spd->dotx ||
808 sps->doty != spd->doty)
809 /* Both associated; change association, if different */
810 len = sprintf(buf, "%s%c%d,%d,%d,%d", sep,
811 (int)achar, x, y, spd->dotx, spd->doty);
812 } else if (sps->flags & F_TILE_ASSOC)
813 /* Only src associated; remove. */
814 len = sprintf(buf, "%sU%d,%d", sep, x, y);
815 else if (spd->flags & F_TILE_ASSOC)
816 /* Only dest associated; add. */
817 len = sprintf(buf, "%s%c%d,%d,%d,%d", sep,
818 (int)achar, x, y, spd->dotx, spd->doty);
819 } else if (sps->type == s_edge) {
820 if ((sps->flags & F_EDGE_SET) != (spd->flags & F_EDGE_SET))
821 /* edge flags are different; flip them. */
822 len = sprintf(buf, "%sE%d,%d", sep, x, y);
823 }
824 if (len) {
825 if (movelen + len >= movesize) {
826 movesize = movelen + len + 256;
827 move = sresize(move, movesize, char);
828 }
829 strcpy(move + movelen, buf);
830 movelen += len;
831 sep = ";";
832 }
833 }
834 }
835 debug(("diff_game src then dest:\n"));
836 dbg_state(src);
837 dbg_state(dest);
838 debug(("diff string %s\n", move));
839 return move;
840}
841
842/* Returns true if a dot here would not be too close to any other dots
843 * (and would avoid other game furniture). */
844static bool dot_is_possible(const game_state *state, space *sp,
845 bool allow_assoc)
846{
847 int bx = 0, by = 0, dx, dy;
848 space *adj;
849#ifdef STANDALONE_PICTURE_GENERATOR
850 int col = -1;
851#endif
852
853 switch (sp->type) {
854 case s_tile:
855 bx = by = 1; break;
856 case s_edge:
857 if (IS_VERTICAL_EDGE(sp->x)) {
858 bx = 2; by = 1;
859 } else {
860 bx = 1; by = 2;
861 }
862 break;
863 case s_vertex:
864 bx = by = 2; break;
865 }
866
867 for (dx = -bx; dx <= bx; dx++) {
868 for (dy = -by; dy <= by; dy++) {
869 if (!INGRID(state, sp->x+dx, sp->y+dy)) continue;
870
871 adj = &SPACE(state, sp->x+dx, sp->y+dy);
872
873#ifdef STANDALONE_PICTURE_GENERATOR
874 /*
875 * Check that all the squares we're looking at have the
876 * same colour.
877 */
878 if (picture) {
879 if (adj->type == s_tile) {
880 int c = picture[(adj->y / 2) * state->w + (adj->x / 2)];
881 if (col < 0)
882 col = c;
883 if (c != col)
884 return false; /* colour mismatch */
885 }
886 }
887#endif
888
889 if (!allow_assoc && (adj->flags & F_TILE_ASSOC))
890 return false;
891
892 if (dx != 0 || dy != 0) {
893 /* Other than our own square, no dots nearby. */
894 if (adj->flags & (F_DOT))
895 return false;
896 }
897
898 /* We don't want edges within our rectangle
899 * (but don't care about edges on the edge) */
900 if (abs(dx) < bx && abs(dy) < by &&
901 adj->flags & F_EDGE_SET)
902 return false;
903 }
904 }
905 return true;
906}
907
908/* ----------------------------------------------------------
909 * Game generation, structure creation, and descriptions.
910 */
911
912static game_state *blank_game(int w, int h)
913{
914 game_state *state = snew(game_state);
915 int x, y;
916
917 state->w = w;
918 state->h = h;
919
920 state->sx = (w*2)+1;
921 state->sy = (h*2)+1;
922 state->grid = snewn(state->sx * state->sy, space);
923 state->completed = false;
924 state->used_solve = false;
925
926 for (x = 0; x < state->sx; x++) {
927 for (y = 0; y < state->sy; y++) {
928 space *sp = &SPACE(state, x, y);
929 memset(sp, 0, sizeof(space));
930 sp->x = x;
931 sp->y = y;
932 if ((x % 2) == 0 && (y % 2) == 0)
933 sp->type = s_vertex;
934 else if ((x % 2) == 0 || (y % 2) == 0) {
935 sp->type = s_edge;
936 if (x == 0 || y == 0 || x == state->sx-1 || y == state->sy-1)
937 sp->flags |= F_EDGE_SET;
938 } else
939 sp->type = s_tile;
940 }
941 }
942
943 state->ndots = 0;
944 state->dots = NULL;
945
946 state->me = NULL; /* filled in by new_game. */
947 state->cdiff = -1;
948
949 return state;
950}
951
952static void game_update_dots(game_state *state)
953{
954 int i, n, sz = state->sx * state->sy;
955
956 if (state->dots) sfree(state->dots);
957 state->ndots = 0;
958
959 for (i = 0; i < sz; i++) {
960 if (state->grid[i].flags & F_DOT) state->ndots++;
961 }
962 state->dots = snewn(state->ndots, space *);
963 n = 0;
964 for (i = 0; i < sz; i++) {
965 if (state->grid[i].flags & F_DOT)
966 state->dots[n++] = &state->grid[i];
967 }
968}
969
970static void clear_game(game_state *state, bool cleardots)
971{
972 int x, y;
973
974 /* don't erase edge flags around outline! */
975 for (x = 1; x < state->sx-1; x++) {
976 for (y = 1; y < state->sy-1; y++) {
977 if (cleardots)
978 SPACE(state, x, y).flags = 0;
979 else
980 SPACE(state, x, y).flags &= (F_DOT|F_DOT_BLACK);
981 }
982 }
983 if (cleardots) game_update_dots(state);
984}
985
986static game_state *dup_game(const game_state *state)
987{
988 game_state *ret = blank_game(state->w, state->h);
989
990 ret->completed = state->completed;
991 ret->used_solve = state->used_solve;
992
993 memcpy(ret->grid, state->grid,
994 ret->sx*ret->sy*sizeof(space));
995
996 game_update_dots(ret);
997
998 ret->me = state->me;
999 ret->cdiff = state->cdiff;
1000
1001 return ret;
1002}
1003
1004static void free_game(game_state *state)
1005{
1006 if (state->dots) sfree(state->dots);
1007 sfree(state->grid);
1008 sfree(state);
1009}
1010
1011/* Game description is a sequence of letters representing the number
1012 * of spaces (a = 0, y = 24) before the next dot; a-y for a white dot,
1013 * and A-Y for a black dot. 'z' is 25 spaces (and no dot).
1014 *
1015 * I know it's a bitch to generate by hand, so we provide
1016 * an edit mode.
1017 */
1018
1019static char *encode_game(const game_state *state)
1020{
1021 char *desc, *p;
1022 int run, x, y, area;
1023 unsigned int f;
1024
1025 area = (state->sx-2) * (state->sy-2);
1026
1027 desc = snewn(area, char);
1028 p = desc;
1029 run = 0;
1030 for (y = 1; y < state->sy-1; y++) {
1031 for (x = 1; x < state->sx-1; x++) {
1032 f = SPACE(state, x, y).flags;
1033
1034 /* a/A is 0 spaces between, b/B is 1 space, ...
1035 * y/Y is 24 spaces, za/zA is 25 spaces, ...
1036 * It's easier to count from 0 because we then
1037 * don't have to special-case the top left-hand corner
1038 * (which could be a dot with 0 spaces before it). */
1039 if (!(f & F_DOT))
1040 run++;
1041 else {
1042 while (run > 24) {
1043 *p++ = 'z';
1044 run -= 25;
1045 }
1046 *p++ = ((f & F_DOT_BLACK) ? 'A' : 'a') + run;
1047 run = 0;
1048 }
1049 }
1050 }
1051 assert(p - desc < area);
1052 *p++ = '\0';
1053 desc = sresize(desc, p - desc, char);
1054
1055 return desc;
1056}
1057
1058struct movedot {
1059 int op;
1060 space *olddot, *newdot;
1061};
1062
1063enum { MD_CHECK, MD_MOVE };
1064
1065static int movedot_cb(game_state *state, space *tile, void *vctx)
1066{
1067 struct movedot *md = (struct movedot *)vctx;
1068 space *newopp = NULL;
1069
1070 assert(tile->type == s_tile);
1071 assert(md->olddot && md->newdot);
1072
1073 if (!(tile->flags & F_TILE_ASSOC)) return 0;
1074 if (tile->dotx != md->olddot->x || tile->doty != md->olddot->y)
1075 return 0;
1076
1077 newopp = space_opposite_dot(state, tile, md->newdot);
1078
1079 switch (md->op) {
1080 case MD_CHECK:
1081 /* If the tile is associated with the old dot, check its
1082 * opposite wrt the _new_ dot is empty or same assoc. */
1083 if (!newopp) return -1; /* no new opposite */
1084 if (newopp->flags & F_TILE_ASSOC) {
1085 if (newopp->dotx != md->olddot->x ||
1086 newopp->doty != md->olddot->y)
1087 return -1; /* associated, but wrong dot. */
1088 }
1089#ifdef STANDALONE_PICTURE_GENERATOR
1090 if (picture) {
1091 /*
1092 * Reject if either tile and the dot don't match in colour.
1093 */
1094 if (!(picture[(tile->y/2) * state->w + (tile->x/2)]) ^
1095 !(md->newdot->flags & F_DOT_BLACK))
1096 return -1;
1097 if (!(picture[(newopp->y/2) * state->w + (newopp->x/2)]) ^
1098 !(md->newdot->flags & F_DOT_BLACK))
1099 return -1;
1100 }
1101#endif
1102 break;
1103
1104 case MD_MOVE:
1105 /* Move dot associations: anything that was associated
1106 * with the old dot, and its opposite wrt the new dot,
1107 * become associated with the new dot. */
1108 assert(newopp);
1109 debug(("Associating %d,%d and %d,%d with new dot %d,%d.\n",
1110 tile->x, tile->y, newopp->x, newopp->y,
1111 md->newdot->x, md->newdot->y));
1112 add_assoc(state, tile, md->newdot);
1113 add_assoc(state, newopp, md->newdot);
1114 return 1; /* we did something! */
1115 }
1116 return 0;
1117}
1118
1119/* For the given dot, first see if we could expand it into all the given
1120 * extra spaces (by checking for empty spaces on the far side), and then
1121 * see if we can move the dot to shift the CoG to include the new spaces.
1122 */
1123static bool dot_expand_or_move(game_state *state, space *dot,
1124 space **toadd, int nadd)
1125{
1126 space *tileopp;
1127 int i, ret, nnew, cx, cy;
1128 struct movedot md;
1129
1130 debug(("dot_expand_or_move: %d tiles for dot %d,%d\n",
1131 nadd, dot->x, dot->y));
1132 for (i = 0; i < nadd; i++)
1133 debug(("dot_expand_or_move: dot %d,%d\n",
1134 toadd[i]->x, toadd[i]->y));
1135 assert(dot->flags & F_DOT);
1136
1137#ifdef STANDALONE_PICTURE_GENERATOR
1138 if (picture) {
1139 /*
1140 * Reject the expansion totally if any of the new tiles are
1141 * the wrong colour.
1142 */
1143 for (i = 0; i < nadd; i++) {
1144 if (!(picture[(toadd[i]->y/2) * state->w + (toadd[i]->x/2)]) ^
1145 !(dot->flags & F_DOT_BLACK))
1146 return false;
1147 }
1148 }
1149#endif
1150
1151 /* First off, could we just expand the current dot's tile to cover
1152 * the space(s) passed in and their opposites? */
1153 for (i = 0; i < nadd; i++) {
1154 tileopp = space_opposite_dot(state, toadd[i], dot);
1155 if (!tileopp) goto noexpand;
1156 if (tileopp->flags & F_TILE_ASSOC) goto noexpand;
1157#ifdef STANDALONE_PICTURE_GENERATOR
1158 if (picture) {
1159 /*
1160 * The opposite tiles have to be the right colour as well.
1161 */
1162 if (!(picture[(tileopp->y/2) * state->w + (tileopp->x/2)]) ^
1163 !(dot->flags & F_DOT_BLACK))
1164 goto noexpand;
1165 }
1166#endif
1167 }
1168 /* OK, all spaces have valid empty opposites: associate spaces and
1169 * opposites with our dot. */
1170 for (i = 0; i < nadd; i++) {
1171 tileopp = space_opposite_dot(state, toadd[i], dot);
1172 add_assoc(state, toadd[i], dot);
1173 add_assoc(state, tileopp, dot);
1174 debug(("Added associations %d,%d and %d,%d --> %d,%d\n",
1175 toadd[i]->x, toadd[i]->y,
1176 tileopp->x, tileopp->y,
1177 dot->x, dot->y));
1178 dbg_state(state);
1179 }
1180 return true;
1181
1182noexpand:
1183 /* Otherwise, try to move dot so as to encompass given spaces: */
1184 /* first, calculate the 'centre of gravity' of the new dot. */
1185 nnew = dot->nassoc + nadd; /* number of tiles assoc. with new dot. */
1186 cx = dot->x * dot->nassoc;
1187 cy = dot->y * dot->nassoc;
1188 for (i = 0; i < nadd; i++) {
1189 cx += toadd[i]->x;
1190 cy += toadd[i]->y;
1191 }
1192 /* If the CoG isn't a whole number, it's not possible. */
1193 if ((cx % nnew) != 0 || (cy % nnew) != 0) {
1194 debug(("Unable to move dot %d,%d, CoG not whole number.\n",
1195 dot->x, dot->y));
1196 return false;
1197 }
1198 cx /= nnew; cy /= nnew;
1199
1200 /* Check whether all spaces in the old tile would have a good
1201 * opposite wrt the new dot. */
1202 md.olddot = dot;
1203 md.newdot = &SPACE(state, cx, cy);
1204 md.op = MD_CHECK;
1205 ret = foreach_tile(state, movedot_cb, IMPOSSIBLE_QUITS, &md);
1206 if (ret == -1) {
1207 debug(("Unable to move dot %d,%d, new dot not symmetrical.\n",
1208 dot->x, dot->y));
1209 return false;
1210 }
1211 /* Also check whether all spaces we're adding would have a good
1212 * opposite wrt the new dot. */
1213 for (i = 0; i < nadd; i++) {
1214 tileopp = space_opposite_dot(state, toadd[i], md.newdot);
1215 if (tileopp && (tileopp->flags & F_TILE_ASSOC) &&
1216 (tileopp->dotx != dot->x || tileopp->doty != dot->y)) {
1217 tileopp = NULL;
1218 }
1219 if (!tileopp) {
1220 debug(("Unable to move dot %d,%d, new dot not symmetrical.\n",
1221 dot->x, dot->y));
1222 return false;
1223 }
1224#ifdef STANDALONE_PICTURE_GENERATOR
1225 if (picture) {
1226 if (!(picture[(tileopp->y/2) * state->w + (tileopp->x/2)]) ^
1227 !(dot->flags & F_DOT_BLACK))
1228 return false;
1229 }
1230#endif
1231 }
1232
1233 /* If we've got here, we're ok. First, associate all of 'toadd'
1234 * with the _old_ dot (so they'll get fixed up, with their opposites,
1235 * in the next step). */
1236 for (i = 0; i < nadd; i++) {
1237 debug(("Associating to-add %d,%d with old dot %d,%d.\n",
1238 toadd[i]->x, toadd[i]->y, dot->x, dot->y));
1239 add_assoc(state, toadd[i], dot);
1240 }
1241
1242 /* Finally, move the dot and fix up all the old associations. */
1243 debug(("Moving dot at %d,%d to %d,%d\n",
1244 dot->x, dot->y, md.newdot->x, md.newdot->y));
1245 {
1246#ifdef STANDALONE_PICTURE_GENERATOR
1247 int f = dot->flags & F_DOT_BLACK;
1248#endif
1249 remove_dot(dot);
1250 add_dot(md.newdot);
1251#ifdef STANDALONE_PICTURE_GENERATOR
1252 md.newdot->flags |= f;
1253#endif
1254 }
1255
1256 md.op = MD_MOVE;
1257 ret = foreach_tile(state, movedot_cb, 0, &md);
1258 assert(ret == 1);
1259 dbg_state(state);
1260
1261 return true;
1262}
1263
1264/* Hard-code to a max. of 2x2 squares, for speed (less malloc) */
1265#define MAX_TOADD 4
1266#define MAX_OUTSIDE 8
1267
1268#define MAX_TILE_PERC 20
1269
1270static bool generate_try_block(game_state *state, random_state *rs,
1271 int x1, int y1, int x2, int y2)
1272{
1273 int x, y, nadd = 0, nout = 0, i, maxsz;
1274 space *sp, *toadd[MAX_TOADD], *outside[MAX_OUTSIDE], *dot;
1275
1276 if (!INGRID(state, x1, y1) || !INGRID(state, x2, y2)) return false;
1277
1278 /* We limit the maximum size of tiles to be ~2*sqrt(area); so,
1279 * a 5x5 grid shouldn't have anything >10 tiles, a 20x20 grid
1280 * nothing >40 tiles. */
1281 maxsz = (int)sqrt((double)(state->w * state->h)) * 2;
1282 debug(("generate_try_block, maxsz %d\n", maxsz));
1283
1284 /* Make a static list of the spaces; if any space is already
1285 * associated then quit immediately. */
1286 for (x = x1; x <= x2; x += 2) {
1287 for (y = y1; y <= y2; y += 2) {
1288 assert(nadd < MAX_TOADD);
1289 sp = &SPACE(state, x, y);
1290 assert(sp->type == s_tile);
1291 if (sp->flags & F_TILE_ASSOC) return false;
1292 toadd[nadd++] = sp;
1293 }
1294 }
1295
1296 /* Make a list of the spaces outside of our block, and shuffle it. */
1297#define OUTSIDE(x, y) do { \
1298 if (INGRID(state, (x), (y))) { \
1299 assert(nout < MAX_OUTSIDE); \
1300 outside[nout++] = &SPACE(state, (x), (y)); \
1301 } \
1302} while(0)
1303 for (x = x1; x <= x2; x += 2) {
1304 OUTSIDE(x, y1-2);
1305 OUTSIDE(x, y2+2);
1306 }
1307 for (y = y1; y <= y2; y += 2) {
1308 OUTSIDE(x1-2, y);
1309 OUTSIDE(x2+2, y);
1310 }
1311 shuffle(outside, nout, sizeof(space *), rs);
1312
1313 for (i = 0; i < nout; i++) {
1314 if (!(outside[i]->flags & F_TILE_ASSOC)) continue;
1315 dot = &SPACE(state, outside[i]->dotx, outside[i]->doty);
1316 if (dot->nassoc >= maxsz) {
1317 debug(("Not adding to dot %d,%d, large enough (%d) already.\n",
1318 dot->x, dot->y, dot->nassoc));
1319 continue;
1320 }
1321 if (dot_expand_or_move(state, dot, toadd, nadd)) return true;
1322 }
1323 return false;
1324}
1325
1326#ifdef STANDALONE_SOLVER
1327static bool one_try; /* override for soak testing */
1328#endif
1329
1330#define GP_DOTS 1
1331
1332static void generate_pass(game_state *state, random_state *rs, int *scratch,
1333 int perc, unsigned int flags)
1334{
1335 int sz = state->sx*state->sy, nspc, i, ret;
1336
1337 /* Random list of squares to try and process, one-by-one. */
1338 for (i = 0; i < sz; i++) scratch[i] = i;
1339 shuffle(scratch, sz, sizeof(int), rs);
1340
1341 /* This bug took me a, er, little while to track down. On PalmOS,
1342 * which has 16-bit signed ints, puzzles over about 9x9 started
1343 * failing to generate because the nspc calculation would start
1344 * to overflow, causing the dots not to be filled in properly. */
1345 nspc = (int)(((long)perc * (long)sz) / 100L);
1346 debug(("generate_pass: %d%% (%d of %dx%d) squares, flags 0x%x\n",
1347 perc, nspc, state->sx, state->sy, flags));
1348
1349 for (i = 0; i < nspc; i++) {
1350 space *sp = &state->grid[scratch[i]];
1351 int x1 = sp->x, y1 = sp->y, x2 = sp->x, y2 = sp->y;
1352
1353 if (sp->type == s_edge) {
1354 if (IS_VERTICAL_EDGE(sp->x)) {
1355 x1--; x2++;
1356 } else {
1357 y1--; y2++;
1358 }
1359 }
1360 if (sp->type != s_vertex) {
1361 /* heuristic; expanding from vertices tends to generate lots of
1362 * too-big regions of tiles. */
1363 if (generate_try_block(state, rs, x1, y1, x2, y2))
1364 continue; /* we expanded successfully. */
1365 }
1366
1367 if (!(flags & GP_DOTS)) continue;
1368
1369 if ((sp->type == s_edge) && (i % 2)) {
1370 debug(("Omitting edge %d,%d as half-of.\n", sp->x, sp->y));
1371 continue;
1372 }
1373
1374 /* If we've got here we might want to put a dot down. Check
1375 * if we can, and add one if so. */
1376 if (dot_is_possible(state, sp, false)) {
1377 add_dot(sp);
1378#ifdef STANDALONE_PICTURE_GENERATOR
1379 if (picture) {
1380 if (picture[(sp->y/2) * state->w + (sp->x/2)])
1381 sp->flags |= F_DOT_BLACK;
1382 }
1383#endif
1384 ret = solver_obvious_dot(state, sp);
1385 assert(ret != -1);
1386 debug(("Added dot (and obvious associations) at %d,%d\n",
1387 sp->x, sp->y));
1388 dbg_state(state);
1389 }
1390 }
1391 dbg_state(state);
1392}
1393
1394/*
1395 * We try several times to generate a grid at all, before even feeding
1396 * it to the solver. Then we pick whichever of the resulting grids was
1397 * the most 'wiggly', as measured by the number of inward corners in
1398 * the shape of any region.
1399 *
1400 * Rationale: wiggly shapes are what make this puzzle fun, and it's
1401 * disappointing to be served a game whose entire solution is a
1402 * collection of rectangles. But we also don't want to introduce a
1403 * _hard requirement_ of wiggliness, because a player who knew that
1404 * was there would be able to use it as an extra clue. This way, we
1405 * just probabilistically skew in favour of wiggliness.
1406 */
1407#define GENERATE_TRIES 10
1408
1409static bool is_wiggle(const game_state *state, int x, int y, int dx, int dy)
1410{
1411 int x1 = x+2*dx, y1 = y+2*dy;
1412 int x2 = x-2*dy, y2 = y+2*dx;
1413 space *t, *t1, *t2;
1414
1415 if (!INGRID(state, x1, y1) || !INGRID(state, x2, y2))
1416 return false;
1417
1418 t = &SPACE(state, x, y);
1419 t1 = &SPACE(state, x1, y1);
1420 t2 = &SPACE(state, x2, y2);
1421 return ((t1->dotx == t2->dotx && t1->doty == t2->doty) &&
1422 !(t1->dotx == t->dotx && t1->doty == t->doty));
1423}
1424
1425static int measure_wiggliness(const game_state *state, int *scratch)
1426{
1427 int sz = state->sx*state->sy;
1428 int x, y, nwiggles = 0;
1429 memset(scratch, 0, sz);
1430
1431 for (y = 1; y < state->sy; y += 2) {
1432 for (x = 1; x < state->sx; x += 2) {
1433 if (y+2 < state->sy) {
1434 nwiggles += is_wiggle(state, x, y, 0, +1);
1435 nwiggles += is_wiggle(state, x, y, 0, -1);
1436 nwiggles += is_wiggle(state, x, y, +1, 0);
1437 nwiggles += is_wiggle(state, x, y, -1, 0);
1438 }
1439 }
1440 }
1441
1442 return nwiggles;
1443}
1444
1445static char *new_game_desc(const game_params *params, random_state *rs,
1446 char **aux, bool interactive)
1447{
1448 game_state *state = blank_game(params->w, params->h), *copy;
1449 char *desc;
1450 int *scratch, sz = state->sx*state->sy, i;
1451 int diff, best_wiggliness;
1452 bool cc;
1453
1454 scratch = snewn(sz, int);
1455
1456generate:
1457 best_wiggliness = -1;
1458 copy = NULL;
1459 for (i = 0; i < GENERATE_TRIES; i++) {
1460 int this_wiggliness;
1461
1462 do {
1463 clear_game(state, true);
1464 generate_pass(state, rs, scratch, 100, GP_DOTS);
1465 game_update_dots(state);
1466 } while (state->ndots == 1);
1467
1468 this_wiggliness = measure_wiggliness(state, scratch);
1469 debug(("Grid gen #%d: wiggliness=%d", i, this_wiggliness));
1470 if (this_wiggliness > best_wiggliness) {
1471 best_wiggliness = this_wiggliness;
1472 if (copy)
1473 free_game(copy);
1474 copy = dup_game(state);
1475 debug((" new best"));
1476 }
1477 debug(("\n"));
1478 }
1479 assert(copy);
1480 free_game(state);
1481 state = copy;
1482
1483#ifdef DEBUGGING
1484 {
1485 char *tmp = encode_game(state);
1486 debug(("new_game_desc state %dx%d:%s\n", params->w, params->h, tmp));
1487 sfree(tmp);
1488 }
1489#endif
1490
1491 for (i = 0; i < state->sx*state->sy; i++)
1492 if (state->grid[i].type == s_tile)
1493 outline_tile_fordot(state, &state->grid[i], true);
1494 cc = check_complete(state, NULL, NULL);
1495 assert(cc);
1496
1497 copy = dup_game(state);
1498 clear_game(copy, false);
1499 dbg_state(copy);
1500 diff = solver_state(copy, params->diff);
1501 free_game(copy);
1502
1503 assert(diff != DIFF_IMPOSSIBLE);
1504 if (diff != params->diff) {
1505 /*
1506 * If the puzzle was insoluble at this difficulty level (i.e.
1507 * too hard), _or_ soluble at a lower level (too easy), go
1508 * round again.
1509 *
1510 * An exception is in soak-testing mode, where we return the
1511 * first puzzle we got regardless.
1512 */
1513#ifdef STANDALONE_SOLVER
1514 if (!one_try)
1515#endif
1516 goto generate;
1517 }
1518
1519#ifdef STANDALONE_PICTURE_GENERATOR
1520 /*
1521 * Postprocessing pass to prevent excessive numbers of adjacent
1522 * singletons. Iterate over all edges in random shuffled order;
1523 * for each edge that separates two regions, investigate
1524 * whether removing that edge and merging the regions would
1525 * still yield a valid and soluble puzzle. (The two regions
1526 * must also be the same colour, of course.) If so, do it.
1527 *
1528 * This postprocessing pass is slow (due to repeated solver
1529 * invocations), and seems to be unnecessary during normal
1530 * unconstrained game generation. However, when generating a
1531 * game under colour constraints, excessive singletons seem to
1532 * turn up more often, so it's worth doing this.
1533 */
1534 {
1535 int *posns, nposns;
1536 int i, j, newdiff;
1537 game_state *copy2;
1538
1539 nposns = params->w * (params->h+1) + params->h * (params->w+1);
1540 posns = snewn(nposns, int);
1541 for (i = j = 0; i < state->sx*state->sy; i++)
1542 if (state->grid[i].type == s_edge)
1543 posns[j++] = i;
1544 assert(j == nposns);
1545
1546 shuffle(posns, nposns, sizeof(*posns), rs);
1547
1548 for (i = 0; i < nposns; i++) {
1549 int x, y, x0, y0, x1, y1, cx, cy, cn, cx0, cy0, cx1, cy1, tx, ty;
1550 space *s0, *s1, *ts, *d0, *d1, *dn;
1551 bool ok;
1552
1553 /* Coordinates of edge space */
1554 x = posns[i] % state->sx;
1555 y = posns[i] / state->sx;
1556
1557 /* Coordinates of square spaces on either side of edge */
1558 x0 = ((x+1) & ~1) - 1; /* round down to next odd number */
1559 y0 = ((y+1) & ~1) - 1;
1560 x1 = 2*x-x0; /* and reflect about x to get x1 */
1561 y1 = 2*y-y0;
1562
1563 if (!INGRID(state, x0, y0) || !INGRID(state, x1, y1))
1564 continue; /* outermost edge of grid */
1565 s0 = &SPACE(state, x0, y0);
1566 s1 = &SPACE(state, x1, y1);
1567 assert(s0->type == s_tile && s1->type == s_tile);
1568
1569 if (s0->dotx == s1->dotx && s0->doty == s1->doty)
1570 continue; /* tiles _already_ owned by same dot */
1571
1572 d0 = &SPACE(state, s0->dotx, s0->doty);
1573 d1 = &SPACE(state, s1->dotx, s1->doty);
1574
1575 if ((d0->flags ^ d1->flags) & F_DOT_BLACK)
1576 continue; /* different colours: cannot merge */
1577
1578 /*
1579 * Work out where the centre of gravity of the new
1580 * region would be.
1581 */
1582 cx = d0->nassoc * d0->x + d1->nassoc * d1->x;
1583 cy = d0->nassoc * d0->y + d1->nassoc * d1->y;
1584 cn = d0->nassoc + d1->nassoc;
1585 if (cx % cn || cy % cn)
1586 continue; /* CoG not at integer coordinates */
1587 cx /= cn;
1588 cy /= cn;
1589 assert(INUI(state, cx, cy));
1590
1591 /*
1592 * Ensure that the CoG would actually be _in_ the new
1593 * region, by verifying that all its surrounding tiles
1594 * belong to one or other of our two dots.
1595 */
1596 cx0 = ((cx+1) & ~1) - 1; /* round down to next odd number */
1597 cy0 = ((cy+1) & ~1) - 1;
1598 cx1 = 2*cx-cx0; /* and reflect about cx to get cx1 */
1599 cy1 = 2*cy-cy0;
1600 ok = true;
1601 for (ty = cy0; ty <= cy1; ty += 2)
1602 for (tx = cx0; tx <= cx1; tx += 2) {
1603 ts = &SPACE(state, tx, ty);
1604 assert(ts->type == s_tile);
1605 if ((ts->dotx != d0->x || ts->doty != d0->y) &&
1606 (ts->dotx != d1->x || ts->doty != d1->y))
1607 ok = false;
1608 }
1609 if (!ok)
1610 continue;
1611
1612 /*
1613 * Verify that for every tile in either source region,
1614 * that tile's image in the new CoG is also in one of
1615 * the two source regions.
1616 */
1617 for (ty = 1; ty < state->sy; ty += 2) {
1618 for (tx = 1; tx < state->sx; tx += 2) {
1619 int tx1, ty1;
1620
1621 ts = &SPACE(state, tx, ty);
1622 assert(ts->type == s_tile);
1623 if ((ts->dotx != d0->x || ts->doty != d0->y) &&
1624 (ts->dotx != d1->x || ts->doty != d1->y))
1625 continue; /* not part of these tiles anyway */
1626 tx1 = 2*cx-tx;
1627 ty1 = 2*cy-ty;
1628 if (!INGRID(state, tx1, ty1)) {
1629 ok = false;
1630 break;
1631 }
1632 ts = &SPACE(state, cx+cx-tx, cy+cy-ty);
1633 if ((ts->dotx != d0->x || ts->doty != d0->y) &&
1634 (ts->dotx != d1->x || ts->doty != d1->y)) {
1635 ok = false;
1636 break;
1637 }
1638 }
1639 if (!ok)
1640 break;
1641 }
1642 if (!ok)
1643 continue;
1644
1645 /*
1646 * Now we're clear to attempt the merge. We take a copy
1647 * of the game state first, so we can revert it easily
1648 * if the resulting puzzle turns out to have become
1649 * insoluble.
1650 */
1651 copy2 = dup_game(state);
1652
1653 remove_dot(d0);
1654 remove_dot(d1);
1655 dn = &SPACE(state, cx, cy);
1656 add_dot(dn);
1657 dn->flags |= (d0->flags & F_DOT_BLACK);
1658 for (ty = 1; ty < state->sy; ty += 2) {
1659 for (tx = 1; tx < state->sx; tx += 2) {
1660 ts = &SPACE(state, tx, ty);
1661 assert(ts->type == s_tile);
1662 if ((ts->dotx != d0->x || ts->doty != d0->y) &&
1663 (ts->dotx != d1->x || ts->doty != d1->y))
1664 continue; /* not part of these tiles anyway */
1665 add_assoc(state, ts, dn);
1666 }
1667 }
1668
1669 copy = dup_game(state);
1670 clear_game(copy, false);
1671 dbg_state(copy);
1672 newdiff = solver_state(copy, params->diff);
1673 free_game(copy);
1674 if (diff == newdiff) {
1675 /* Still just as soluble. Let the merge stand. */
1676 free_game(copy2);
1677 } else {
1678 /* Became insoluble. Revert. */
1679 free_game(state);
1680 state = copy2;
1681 }
1682 }
1683 sfree(posns);
1684 }
1685#endif
1686
1687 desc = encode_game(state);
1688#ifndef STANDALONE_SOLVER
1689 debug(("new_game_desc generated: \n"));
1690 dbg_state(state);
1691#endif
1692
1693 game_state *blank = blank_game(params->w, params->h);
1694 *aux = diff_game(blank, state, true, -1);
1695 free_game(blank);
1696
1697 free_game(state);
1698 sfree(scratch);
1699
1700 return desc;
1701}
1702
1703static bool dots_too_close(game_state *state)
1704{
1705 /* Quick-and-dirty check, using half the solver:
1706 * solver_obvious will only fail if the dots are
1707 * too close together, so dot-proximity associations
1708 * overlap. */
1709 game_state *tmp = dup_game(state);
1710 int ret = solver_obvious(tmp);
1711 free_game(tmp);
1712 return ret == -1;
1713}
1714
1715static game_state *load_game(const game_params *params, const char *desc,
1716 const char **why_r)
1717{
1718 game_state *state = blank_game(params->w, params->h);
1719 const char *why = NULL;
1720 int i, x, y, n;
1721 unsigned int df;
1722
1723 i = 0;
1724 while (*desc) {
1725 n = *desc++;
1726 if (n == 'z') {
1727 i += 25;
1728 continue;
1729 }
1730 if (n >= 'a' && n <= 'y') {
1731 i += n - 'a';
1732 df = 0;
1733 } else if (n >= 'A' && n <= 'Y') {
1734 i += n - 'A';
1735 df = F_DOT_BLACK;
1736 } else {
1737 why = "Invalid characters in game description"; goto fail;
1738 }
1739 /* if we got here we incremented i and have a dot to add. */
1740 y = (i / (state->sx-2)) + 1;
1741 x = (i % (state->sx-2)) + 1;
1742 if (!INUI(state, x, y)) {
1743 why = "Too much data to fit in grid"; goto fail;
1744 }
1745 add_dot(&SPACE(state, x, y));
1746 SPACE(state, x, y).flags |= df;
1747 i++;
1748 }
1749 game_update_dots(state);
1750
1751 if (dots_too_close(state)) {
1752 why = "Dots too close together"; goto fail;
1753 }
1754
1755 return state;
1756
1757fail:
1758 free_game(state);
1759 if (why_r) *why_r = why;
1760 return NULL;
1761}
1762
1763static const char *validate_desc(const game_params *params, const char *desc)
1764{
1765 const char *why = NULL;
1766 game_state *dummy = load_game(params, desc, &why);
1767 if (dummy) {
1768 free_game(dummy);
1769 assert(!why);
1770 } else
1771 assert(why);
1772 return why;
1773}
1774
1775static game_state *new_game(midend *me, const game_params *params,
1776 const char *desc)
1777{
1778 game_state *state = load_game(params, desc, NULL);
1779 if (!state) {
1780 assert("Unable to load ?validated game.");
1781 return NULL;
1782 }
1783#ifdef EDITOR
1784 state->me = me;
1785#endif
1786 return state;
1787}
1788
1789/* ----------------------------------------------------------
1790 * Solver and all its little wizards.
1791 */
1792
1793#if defined DEBUGGING || defined STANDALONE_SOLVER
1794static int solver_recurse_depth;
1795#define STATIC_RECURSION_DEPTH
1796#endif
1797
1798typedef struct solver_ctx {
1799 game_state *state;
1800 int sz; /* state->sx * state->sy */
1801 space **scratch; /* size sz */
1802 DSF *dsf; /* size sz */
1803 int *iscratch; /* size sz */
1804} solver_ctx;
1805
1806static solver_ctx *new_solver(game_state *state)
1807{
1808 solver_ctx *sctx = snew(solver_ctx);
1809 sctx->state = state;
1810 sctx->sz = state->sx*state->sy;
1811 sctx->scratch = snewn(sctx->sz, space *);
1812 sctx->dsf = dsf_new(sctx->sz);
1813 sctx->iscratch = snewn(sctx->sz, int);
1814 return sctx;
1815}
1816
1817static void free_solver(solver_ctx *sctx)
1818{
1819 sfree(sctx->scratch);
1820 dsf_free(sctx->dsf);
1821 sfree(sctx->iscratch);
1822 sfree(sctx);
1823}
1824
1825 /* Solver ideas so far:
1826 *
1827 * For any empty space, work out how many dots it could associate
1828 * with:
1829 * it needs line-of-sight
1830 * it needs an empty space on the far side
1831 * any adjacent lines need corresponding line possibilities.
1832 */
1833
1834/* The solver_ctx should keep a list of dot positions, for quicker looping.
1835 *
1836 * Solver techniques, in order of difficulty:
1837 * obvious adjacency to dots
1838 * transferring tiles to opposite side
1839 * transferring lines to opposite side
1840 * one possible dot for a given tile based on opposite availability
1841 * tile with 3 definite edges next to an associated tile must associate
1842 with same dot.
1843 *
1844 * one possible dot for a given tile based on line-of-sight
1845 */
1846
1847static int solver_add_assoc(game_state *state, space *tile, int dx, int dy,
1848 const char *why)
1849{
1850 space *dot, *tile_opp;
1851
1852 dot = &SPACE(state, dx, dy);
1853 tile_opp = space_opposite_dot(state, tile, dot);
1854
1855 assert(tile->type == s_tile);
1856 if (tile->flags & F_TILE_ASSOC) {
1857 if ((tile->dotx != dx) || (tile->doty != dy)) {
1858 solvep(("%*sSet %d,%d --> %d,%d (%s) impossible; "
1859 "already --> %d,%d.\n",
1860 solver_recurse_depth*4, "",
1861 tile->x, tile->y, dx, dy, why,
1862 tile->dotx, tile->doty));
1863 return -1;
1864 }
1865 return 0; /* no-op */
1866 }
1867 if (!tile_opp) {
1868 solvep(("%*s%d,%d --> %d,%d impossible, no opposite tile.\n",
1869 solver_recurse_depth*4, "", tile->x, tile->y, dx, dy));
1870 return -1;
1871 }
1872 if (tile_opp->flags & F_TILE_ASSOC &&
1873 (tile_opp->dotx != dx || tile_opp->doty != dy)) {
1874 solvep(("%*sSet %d,%d --> %d,%d (%s) impossible; "
1875 "opposite already --> %d,%d.\n",
1876 solver_recurse_depth*4, "",
1877 tile->x, tile->y, dx, dy, why,
1878 tile_opp->dotx, tile_opp->doty));
1879 return -1;
1880 }
1881
1882 add_assoc(state, tile, dot);
1883 add_assoc(state, tile_opp, dot);
1884 solvep(("%*sSetting %d,%d --> %d,%d (%s).\n",
1885 solver_recurse_depth*4, "",
1886 tile->x, tile->y,dx, dy, why));
1887 solvep(("%*sSetting %d,%d --> %d,%d (%s, opposite).\n",
1888 solver_recurse_depth*4, "",
1889 tile_opp->x, tile_opp->y, dx, dy, why));
1890 return 1;
1891}
1892
1893static int solver_obvious_dot(game_state *state, space *dot)
1894{
1895 int dx, dy, ret, didsth = 0;
1896 space *tile;
1897
1898 debug(("%*ssolver_obvious_dot for %d,%d.\n",
1899 solver_recurse_depth*4, "", dot->x, dot->y));
1900
1901 assert(dot->flags & F_DOT);
1902 for (dx = -1; dx <= 1; dx++) {
1903 for (dy = -1; dy <= 1; dy++) {
1904 if (!INGRID(state, dot->x+dx, dot->y+dy)) continue;
1905
1906 tile = &SPACE(state, dot->x+dx, dot->y+dy);
1907 if (tile->type == s_tile) {
1908 ret = solver_add_assoc(state, tile, dot->x, dot->y,
1909 "next to dot");
1910 if (ret < 0) return -1;
1911 if (ret > 0) didsth = 1;
1912 }
1913 }
1914 }
1915 return didsth;
1916}
1917
1918static int solver_obvious(game_state *state)
1919{
1920 int i, didsth = 0, ret;
1921
1922 debug(("%*ssolver_obvious.\n", solver_recurse_depth*4, ""));
1923
1924 for (i = 0; i < state->ndots; i++) {
1925 ret = solver_obvious_dot(state, state->dots[i]);
1926 if (ret < 0) return -1;
1927 if (ret > 0) didsth = 1;
1928 }
1929 return didsth;
1930}
1931
1932static int solver_lines_opposite_cb(game_state *state, space *edge, void *ctx)
1933{
1934 int didsth = 0, n, dx, dy;
1935 space *tiles[2], *tile_opp, *edge_opp;
1936
1937 assert(edge->type == s_edge);
1938
1939 tiles_from_edge(state, edge, tiles);
1940
1941 /* if tiles[0] && tiles[1] && they're both associated
1942 * and they're both associated with different dots,
1943 * ensure the line is set. */
1944 if (!(edge->flags & F_EDGE_SET) &&
1945 tiles[0] && tiles[1] &&
1946 (tiles[0]->flags & F_TILE_ASSOC) &&
1947 (tiles[1]->flags & F_TILE_ASSOC) &&
1948 (tiles[0]->dotx != tiles[1]->dotx ||
1949 tiles[0]->doty != tiles[1]->doty)) {
1950 /* No edge, but the two adjacent tiles are both
1951 * associated with different dots; add the edge. */
1952 solvep(("%*sSetting edge %d,%d - tiles different dots.\n",
1953 solver_recurse_depth*4, "", edge->x, edge->y));
1954 edge->flags |= F_EDGE_SET;
1955 didsth = 1;
1956 }
1957
1958 if (!(edge->flags & F_EDGE_SET)) return didsth;
1959 for (n = 0; n < 2; n++) {
1960 if (!tiles[n]) continue;
1961 assert(tiles[n]->type == s_tile);
1962 if (!(tiles[n]->flags & F_TILE_ASSOC)) continue;
1963
1964 tile_opp = tile_opposite(state, tiles[n]);
1965 if (!tile_opp) {
1966 solvep(("%*simpossible: edge %d,%d has assoc. tile %d,%d"
1967 " with no opposite.\n",
1968 solver_recurse_depth*4, "",
1969 edge->x, edge->y, tiles[n]->x, tiles[n]->y));
1970 /* edge of tile has no opposite edge (off grid?);
1971 * this is impossible. */
1972 return -1;
1973 }
1974
1975 dx = tiles[n]->x - edge->x;
1976 dy = tiles[n]->y - edge->y;
1977 assert(INGRID(state, tile_opp->x+dx, tile_opp->y+dy));
1978 edge_opp = &SPACE(state, tile_opp->x+dx, tile_opp->y+dy);
1979 if (!(edge_opp->flags & F_EDGE_SET)) {
1980 solvep(("%*sSetting edge %d,%d as opposite %d,%d\n",
1981 solver_recurse_depth*4, "",
1982 tile_opp->x+dx, tile_opp->y+dy, edge->x, edge->y));
1983 edge_opp->flags |= F_EDGE_SET;
1984 didsth = 1;
1985 }
1986 }
1987 return didsth;
1988}
1989
1990static int solver_spaces_oneposs_cb(game_state *state, space *tile, void *ctx)
1991{
1992 int n, eset, ret;
1993 space *edgeadj[4], *tileadj[4];
1994 int dotx, doty;
1995
1996 assert(tile->type == s_tile);
1997 if (tile->flags & F_TILE_ASSOC) return 0;
1998
1999 adjacencies(state, tile, edgeadj, tileadj);
2000
2001 /* Empty tile. If each edge is either set, or associated with
2002 * the same dot, we must also associate with dot. */
2003 eset = 0; dotx = -1; doty = -1;
2004 for (n = 0; n < 4; n++) {
2005 assert(edgeadj[n]);
2006 assert(edgeadj[n]->type == s_edge);
2007 if (edgeadj[n]->flags & F_EDGE_SET) {
2008 eset++;
2009 } else {
2010 assert(tileadj[n]);
2011 assert(tileadj[n]->type == s_tile);
2012
2013 /* If an adjacent tile is empty we can't make any deductions.*/
2014 if (!(tileadj[n]->flags & F_TILE_ASSOC))
2015 return 0;
2016
2017 /* If an adjacent tile is assoc. with a different dot
2018 * we can't make any deductions. */
2019 if (dotx != -1 && doty != -1 &&
2020 (tileadj[n]->dotx != dotx ||
2021 tileadj[n]->doty != doty))
2022 return 0;
2023
2024 dotx = tileadj[n]->dotx;
2025 doty = tileadj[n]->doty;
2026 }
2027 }
2028 if (eset == 4) {
2029 solvep(("%*simpossible: empty tile %d,%d has 4 edges\n",
2030 solver_recurse_depth*4, "",
2031 tile->x, tile->y));
2032 return -1;
2033 }
2034 assert(dotx != -1 && doty != -1);
2035
2036 ret = solver_add_assoc(state, tile, dotx, doty, "rest are edges");
2037 if (ret == -1) return -1;
2038 assert(ret != 0); /* really should have done something. */
2039
2040 return 1;
2041}
2042
2043/* Improved algorithm for tracking line-of-sight from dots, and not spaces.
2044 *
2045 * The solver_ctx already stores a list of dots: the algorithm proceeds by
2046 * expanding outwards from each dot in turn, expanding first to the boundary
2047 * of its currently-connected tile and then to all empty tiles that could see
2048 * it. Empty tiles will be flagged with a 'can see dot <x,y>' sticker.
2049 *
2050 * Expansion will happen by (symmetrically opposite) pairs of squares; if
2051 * a square hasn't an opposite number there's no point trying to expand through
2052 * it. Empty tiles will therefore also be tagged in pairs.
2053 *
2054 * If an empty tile already has a 'can see dot <x,y>' tag from a previous dot,
2055 * it (and its partner) gets untagged (or, rather, a 'can see two dots' tag)
2056 * because we're looking for single-dot possibilities.
2057 *
2058 * Once we've gone through all the dots, any which still have a 'can see dot'
2059 * tag get associated with that dot (because it must have been the only one);
2060 * any without any tag (i.e. that could see _no_ dots) cause an impossibility
2061 * marked.
2062 *
2063 * The expansion will happen each time with a stored list of (space *) pairs,
2064 * rather than a mark-and-sweep idea; that's horrifically inefficient.
2065 *
2066 * expansion algorithm:
2067 *
2068 * * allocate list of (space *) the size of s->sx*s->sy.
2069 * * allocate second grid for (flags, dotx, doty) size of sx*sy.
2070 *
2071 * clear second grid (flags = 0, all dotx and doty = 0)
2072 * flags: F_REACHABLE, F_MULTIPLE
2073 *
2074 *
2075 * * for each dot, start with one pair of tiles that are associated with it --
2076 * * vertex --> (dx+1, dy+1), (dx-1, dy-1)
2077 * * edge --> (adj1, adj2)
2078 * * tile --> (tile, tile) ???
2079 * * mark that pair of tiles with F_MARK, clear all other F_MARKs.
2080 * * add two tiles to start of list.
2081 *
2082 * set start = 0, end = next = 2
2083 *
2084 * from (start to end-1, step 2) {
2085 * * we have two tiles (t1, t2), opposites wrt our dot.
2086 * * for each (at1) sensible adjacent tile to t1 (i.e. not past an edge):
2087 * * work out at2 as the opposite to at1
2088 * * assert at1 and at2 have the same F_MARK values.
2089 * * if at1 & F_MARK ignore it (we've been there on a previous sweep)
2090 * * if either are associated with a different dot
2091 * * mark both with F_MARK (so we ignore them later)
2092 * * otherwise (assoc. with our dot, or empty):
2093 * * mark both with F_MARK
2094 * * add their space * values to the end of the list, set next += 2.
2095 * }
2096 *
2097 * if (end == next)
2098 * * we didn't add any new squares; exit the loop.
2099 * else
2100 * * set start = next+1, end = next. go round again
2101 *
2102 * We've finished expanding from the dot. Now, for each square we have
2103 * in our list (--> each square with F_MARK):
2104 * * if the tile is empty:
2105 * * if F_REACHABLE was already set
2106 * * set F_MULTIPLE
2107 * * otherwise
2108 * * set F_REACHABLE, set dotx and doty to our dot.
2109 *
2110 * Then, continue the whole thing for each dot in turn.
2111 *
2112 * Once we've done for each dot, go through the entire grid looking for
2113 * empty tiles: for each empty tile:
2114 * if F_REACHABLE and not F_MULTIPLE, set that dot (and its double)
2115 * if !F_REACHABLE, return as impossible.
2116 *
2117 */
2118
2119/* Returns true if this tile is either already associated with this dot,
2120 * or blank. */
2121static bool solver_expand_checkdot(space *tile, space *dot)
2122{
2123 if (!(tile->flags & F_TILE_ASSOC)) return true;
2124 if (tile->dotx == dot->x && tile->doty == dot->y) return true;
2125 return false;
2126}
2127
2128static void solver_expand_fromdot(game_state *state, space *dot, solver_ctx *sctx)
2129{
2130 int i, j, x, y, start, end, next;
2131 space *sp;
2132
2133 /* Clear the grid of the (space) flags we'll use. */
2134
2135 /* This is well optimised; analysis showed that:
2136 for (i = 0; i < sctx->sz; i++) state->grid[i].flags &= ~F_MARK;
2137 took up ~85% of the total function time! */
2138 for (y = 1; y < state->sy; y += 2) {
2139 sp = &SPACE(state, 1, y);
2140 for (x = 1; x < state->sx; x += 2, sp += 2)
2141 sp->flags &= ~F_MARK;
2142 }
2143
2144 /* Seed the list of marked squares with two that must be associated
2145 * with our dot (possibly the same space) */
2146 if (dot->type == s_tile) {
2147 sctx->scratch[0] = sctx->scratch[1] = dot;
2148 } else if (dot->type == s_edge) {
2149 tiles_from_edge(state, dot, sctx->scratch);
2150 } else if (dot->type == s_vertex) {
2151 /* pick two of the opposite ones arbitrarily. */
2152 sctx->scratch[0] = &SPACE(state, dot->x-1, dot->y-1);
2153 sctx->scratch[1] = &SPACE(state, dot->x+1, dot->y+1);
2154 }
2155 assert(sctx->scratch[0]->flags & F_TILE_ASSOC);
2156 assert(sctx->scratch[1]->flags & F_TILE_ASSOC);
2157
2158 sctx->scratch[0]->flags |= F_MARK;
2159 sctx->scratch[1]->flags |= F_MARK;
2160
2161 debug(("%*sexpand from dot %d,%d seeded with %d,%d and %d,%d.\n",
2162 solver_recurse_depth*4, "", dot->x, dot->y,
2163 sctx->scratch[0]->x, sctx->scratch[0]->y,
2164 sctx->scratch[1]->x, sctx->scratch[1]->y));
2165
2166 start = 0; end = 2; next = 2;
2167
2168expand:
2169 debug(("%*sexpand: start %d, end %d, next %d\n",
2170 solver_recurse_depth*4, "", start, end, next));
2171 for (i = start; i < end; i += 2) {
2172 space *t1 = sctx->scratch[i]/*, *t2 = sctx->scratch[i+1]*/;
2173 space *edges[4], *tileadj[4], *tileadj2;
2174
2175 adjacencies(state, t1, edges, tileadj);
2176
2177 for (j = 0; j < 4; j++) {
2178 assert(edges[j]);
2179 if (edges[j]->flags & F_EDGE_SET) continue;
2180 assert(tileadj[j]);
2181
2182 if (tileadj[j]->flags & F_MARK) continue; /* seen before. */
2183
2184 /* We have a tile adjacent to t1; find its opposite. */
2185 tileadj2 = space_opposite_dot(state, tileadj[j], dot);
2186 if (!tileadj2) {
2187 debug(("%*sMarking %d,%d, no opposite.\n",
2188 solver_recurse_depth*4, "",
2189 tileadj[j]->x, tileadj[j]->y));
2190 tileadj[j]->flags |= F_MARK;
2191 continue; /* no opposite, so mark for next time. */
2192 }
2193 /* If the tile had an opposite we should have either seen both of
2194 * these, or neither of these, before. */
2195 assert(!(tileadj2->flags & F_MARK));
2196
2197 if (solver_expand_checkdot(tileadj[j], dot) &&
2198 solver_expand_checkdot(tileadj2, dot)) {
2199 /* Both tiles could associate with this dot; add them to
2200 * our list. */
2201 debug(("%*sAdding %d,%d and %d,%d to possibles list.\n",
2202 solver_recurse_depth*4, "",
2203 tileadj[j]->x, tileadj[j]->y, tileadj2->x, tileadj2->y));
2204 sctx->scratch[next++] = tileadj[j];
2205 sctx->scratch[next++] = tileadj2;
2206 }
2207 /* Either way, we've seen these tiles already so mark them. */
2208 debug(("%*sMarking %d,%d and %d,%d.\n",
2209 solver_recurse_depth*4, "",
2210 tileadj[j]->x, tileadj[j]->y, tileadj2->x, tileadj2->y));
2211 tileadj[j]->flags |= F_MARK;
2212 tileadj2->flags |= F_MARK;
2213 }
2214 }
2215 if (next > end) {
2216 /* We added more squares; go back and try again. */
2217 start = end; end = next; goto expand;
2218 }
2219
2220 /* We've expanded as far as we can go. Now we update the main flags
2221 * on all tiles we've expanded into -- if they were empty, we have
2222 * found possible associations for this dot. */
2223 for (i = 0; i < end; i++) {
2224 if (sctx->scratch[i]->flags & F_TILE_ASSOC) continue;
2225 if (sctx->scratch[i]->flags & F_REACHABLE) {
2226 /* This is (at least) the second dot this tile could
2227 * associate with. */
2228 debug(("%*sempty tile %d,%d could assoc. other dot %d,%d\n",
2229 solver_recurse_depth*4, "",
2230 sctx->scratch[i]->x, sctx->scratch[i]->y, dot->x, dot->y));
2231 sctx->scratch[i]->flags |= F_MULTIPLE;
2232 } else {
2233 /* This is the first (possibly only) dot. */
2234 debug(("%*sempty tile %d,%d could assoc. 1st dot %d,%d\n",
2235 solver_recurse_depth*4, "",
2236 sctx->scratch[i]->x, sctx->scratch[i]->y, dot->x, dot->y));
2237 sctx->scratch[i]->flags |= F_REACHABLE;
2238 sctx->scratch[i]->dotx = dot->x;
2239 sctx->scratch[i]->doty = dot->y;
2240 }
2241 }
2242 dbg_state(state);
2243}
2244
2245static int solver_expand_postcb(game_state *state, space *tile, void *ctx)
2246{
2247 assert(tile->type == s_tile);
2248
2249 if (tile->flags & F_TILE_ASSOC) return 0;
2250
2251 if (!(tile->flags & F_REACHABLE)) {
2252 solvep(("%*simpossible: space (%d,%d) can reach no dots.\n",
2253 solver_recurse_depth*4, "", tile->x, tile->y));
2254 return -1;
2255 }
2256 if (tile->flags & F_MULTIPLE) return 0;
2257
2258 return solver_add_assoc(state, tile, tile->dotx, tile->doty,
2259 "single possible dot after expansion");
2260}
2261
2262static int solver_expand_dots(game_state *state, solver_ctx *sctx)
2263{
2264 int i;
2265
2266 for (i = 0; i < sctx->sz; i++)
2267 state->grid[i].flags &= ~(F_REACHABLE|F_MULTIPLE);
2268
2269 for (i = 0; i < state->ndots; i++)
2270 solver_expand_fromdot(state, state->dots[i], sctx);
2271
2272 return foreach_tile(state, solver_expand_postcb, IMPOSSIBLE_QUITS, sctx);
2273}
2274
2275static int solver_extend_exclaves(game_state *state, solver_ctx *sctx)
2276{
2277 int x, y, done_something = 0;
2278
2279 /*
2280 * Make a dsf by unifying any two adjacent tiles associated with
2281 * the same dot. This will identify separate connected components
2282 * of the tiles belonging to a given dot. Any such component that
2283 * doesn't contain its own dot is an 'exclave', and will need some
2284 * kind of path of tiles to connect it back to the dot.
2285 */
2286 dsf_reinit(sctx->dsf);
2287 for (x = 1; x < state->sx; x += 2) {
2288 for (y = 1; y < state->sy; y += 2) {
2289 int dotx, doty;
2290 space *tile, *othertile;
2291
2292 tile = &SPACE(state, x, y);
2293 if (!(tile->flags & F_TILE_ASSOC))
2294 continue; /* not associated with any dot */
2295 dotx = tile->dotx;
2296 doty = tile->doty;
2297
2298 if (INGRID(state, x+2, y)) {
2299 othertile = &SPACE(state, x+2, y);
2300 if ((othertile->flags & F_TILE_ASSOC) &&
2301 othertile->dotx == dotx && othertile->doty == doty)
2302 dsf_merge(sctx->dsf, y*state->sx+x, y*state->sx+(x+2));
2303 }
2304
2305 if (INGRID(state, x, y+2)) {
2306 othertile = &SPACE(state, x, y+2);
2307 if ((othertile->flags & F_TILE_ASSOC) &&
2308 othertile->dotx == dotx && othertile->doty == doty)
2309 dsf_merge(sctx->dsf, y*state->sx+x, (y+2)*state->sx+x);
2310 }
2311 }
2312 }
2313
2314 /*
2315 * Go through the grid again, and count the 'liberties' of each
2316 * connected component, in the Go sense, i.e. the number of
2317 * currently unassociated squares adjacent to the component. The
2318 * idea is that if an exclave has just one liberty, then that
2319 * square _must_ extend the exclave, or else it will be completely
2320 * cut off from connecting back to its home dot.
2321 *
2322 * We need to count each adjacent square just once, even if it
2323 * borders the component on multiple edges. So we'll go through
2324 * each unassociated square, check all four of its neighbours, and
2325 * de-duplicate them.
2326 *
2327 * We'll store the count of liberties in the entry of iscratch
2328 * corresponding to the square centre (i.e. with odd coordinates).
2329 * Every time we find a liberty, we store its index in the square
2330 * to the left of that, so that when a component has exactly one
2331 * liberty we can remember what it was.
2332 *
2333 * Square centres that are not the canonical dsf element of a
2334 * connected component will get their liberty count set to -1,
2335 * which will allow us to identify them in the later loop (after
2336 * we start making changes and need to spot that an associated
2337 * square _now_ was not associated when the dsf was built).
2338 */
2339
2340 /* Initialise iscratch */
2341 for (x = 1; x < state->sx; x += 2) {
2342 for (y = 1; y < state->sy; y += 2) {
2343 int index = y * state->sx + x;
2344 if (!(SPACE(state, x, y).flags & F_TILE_ASSOC) ||
2345 dsf_canonify(sctx->dsf, index) != index) {
2346 sctx->iscratch[index] = -1; /* mark as not a component */
2347 } else {
2348 sctx->iscratch[index] = 0; /* zero liberty count */
2349 sctx->iscratch[index-1] = 0; /* initialise neighbour id */
2350 }
2351 }
2352 }
2353
2354 /* Find each unassociated square and see what it's a liberty of */
2355 for (x = 1; x < state->sx; x += 2) {
2356 for (y = 1; y < state->sy; y += 2) {
2357 int dx, dy, ni[4], nn, i;
2358
2359 if ((SPACE(state, x, y).flags & F_TILE_ASSOC))
2360 continue; /* not an unassociated square */
2361
2362 /* Find distinct indices of adjacent components */
2363 nn = 0;
2364 for (dx = -1; dx <= 1; dx++) {
2365 for (dy = -1; dy <= 1; dy++) {
2366 if (dx != 0 && dy != 0) continue;
2367 if (dx == 0 && dy == 0) continue;
2368
2369 if (INGRID(state, x+2*dx, y+2*dy) &&
2370 (SPACE(state, x+2*dx, y+2*dy).flags & F_TILE_ASSOC)) {
2371 /* Find id of the component adjacent to x,y */
2372 int nindex = (y+2*dy) * state->sx + (x+2*dx);
2373 nindex = dsf_canonify(sctx->dsf, nindex);
2374
2375 /* See if we've seen it before in another direction */
2376 for (i = 0; i < nn; i++)
2377 if (ni[i] == nindex)
2378 break;
2379 if (i == nn) {
2380 /* No, it's new. Mark x,y as a liberty of it */
2381 sctx->iscratch[nindex]++;
2382 assert(nindex > 0);
2383 sctx->iscratch[nindex-1] = y * state->sx + x;
2384
2385 /* And record this component as having been seen */
2386 ni[nn++] = nindex;
2387 }
2388 }
2389 }
2390 }
2391 }
2392 }
2393
2394 /*
2395 * Now we have all the data we need to find exclaves with exactly
2396 * one liberty. In each case, associate the unique liberty square
2397 * with the same dot.
2398 */
2399 for (x = 1; x < state->sx; x += 2) {
2400 for (y = 1; y < state->sy; y += 2) {
2401 int index, dotx, doty, ex, ey, added;
2402 space *tile;
2403
2404 index = y*state->sx+x;
2405 if (sctx->iscratch[index] == -1)
2406 continue; /* wasn't canonical when dsf was built */
2407
2408 tile = &SPACE(state, x, y);
2409 if (!(tile->flags & F_TILE_ASSOC))
2410 continue; /* not associated with any dot */
2411 dotx = tile->dotx;
2412 doty = tile->doty;
2413
2414 if (index == dsf_canonify(
2415 sctx->dsf, (doty | 1) * state->sx + (dotx | 1)))
2416 continue; /* not an exclave - contains its own dot */
2417
2418 if (sctx->iscratch[index] == 0) {
2419 solvep(("%*sExclave at %d,%d has no liberties!\n",
2420 solver_recurse_depth*4, "", x, y));
2421 return -1;
2422 }
2423
2424 if (sctx->iscratch[index] != 1)
2425 continue; /* more than one liberty, can't be sure which */
2426
2427 assert(sctx->iscratch[index-1] != 0);
2428 ex = sctx->iscratch[index-1] % state->sx;
2429 ey = sctx->iscratch[index-1] / state->sx;
2430 tile = &SPACE(state, ex, ey);
2431 if (tile->flags & F_TILE_ASSOC)
2432 continue; /* already done by earlier iteration of this loop */
2433
2434 added = solver_add_assoc(state, tile, dotx, doty,
2435 "to connect exclave");
2436 if (added < 0)
2437 return -1;
2438 if (added > 0)
2439 done_something = 1;
2440 }
2441 }
2442
2443 return done_something;
2444}
2445
2446struct recurse_ctx {
2447 space *best;
2448 int bestn;
2449};
2450
2451static int solver_recurse_cb(game_state *state, space *tile, void *ctx)
2452{
2453 struct recurse_ctx *rctx = (struct recurse_ctx *)ctx;
2454 int i, n = 0;
2455
2456 assert(tile->type == s_tile);
2457 if (tile->flags & F_TILE_ASSOC) return 0;
2458
2459 /* We're unassociated: count up all the dots we could associate with. */
2460 for (i = 0; i < state->ndots; i++) {
2461 if (dotfortile(state, tile, state->dots[i]))
2462 n++;
2463 }
2464 if (n > rctx->bestn) {
2465 rctx->bestn = n;
2466 rctx->best = tile;
2467 }
2468 return 0;
2469}
2470
2471#define MAXRECURSE 5
2472
2473static int solver_recurse(game_state *state, int maxdiff, int depth)
2474{
2475 int diff = DIFF_IMPOSSIBLE, ret, n, gsz = state->sx * state->sy;
2476 space *ingrid, *outgrid = NULL, *bestopp;
2477 struct recurse_ctx rctx;
2478
2479 if (depth >= MAXRECURSE) {
2480 solvep(("Limiting recursion to %d, returning.\n", MAXRECURSE));
2481 return DIFF_UNFINISHED;
2482 }
2483
2484 /* Work out the cell to recurse on; go through all unassociated tiles
2485 * and find which one has the most possible dots it could associate
2486 * with. */
2487 rctx.best = NULL;
2488 rctx.bestn = 0;
2489
2490 foreach_tile(state, solver_recurse_cb, 0, &rctx);
2491 if (rctx.bestn == 0) return DIFF_IMPOSSIBLE; /* or assert? */
2492 assert(rctx.best);
2493
2494 solvep(("%*sRecursing around %d,%d, with %d possible dots.\n",
2495 solver_recurse_depth*4, "",
2496 rctx.best->x, rctx.best->y, rctx.bestn));
2497
2498 ingrid = snewn(gsz, space);
2499 memcpy(ingrid, state->grid, gsz * sizeof(space));
2500
2501 for (n = 0; n < state->ndots; n++) {
2502 memcpy(state->grid, ingrid, gsz * sizeof(space));
2503
2504 if (!dotfortile(state, rctx.best, state->dots[n])) continue;
2505
2506 /* set cell (temporarily) pointing to that dot. */
2507 solver_add_assoc(state, rctx.best,
2508 state->dots[n]->x, state->dots[n]->y,
2509 "Attempting for recursion");
2510
2511 ret = solver_state_inner(state, maxdiff, depth + 1);
2512
2513#ifdef STATIC_RECURSION_DEPTH
2514 solver_recurse_depth = depth; /* restore after recursion returns */
2515#endif
2516
2517 if (diff == DIFF_IMPOSSIBLE && ret != DIFF_IMPOSSIBLE) {
2518 /* we found our first solved grid; copy it away. */
2519 assert(!outgrid);
2520 outgrid = snewn(gsz, space);
2521 memcpy(outgrid, state->grid, gsz * sizeof(space));
2522 }
2523 /* reset cell back to unassociated. */
2524 bestopp = tile_opposite(state, rctx.best);
2525 assert(bestopp && bestopp->flags & F_TILE_ASSOC);
2526
2527 remove_assoc(state, rctx.best);
2528 remove_assoc(state, bestopp);
2529
2530 if (ret == DIFF_AMBIGUOUS || ret == DIFF_UNFINISHED)
2531 diff = ret;
2532 else if (ret == DIFF_IMPOSSIBLE)
2533 /* no change */;
2534 else {
2535 /* precisely one solution */
2536 if (diff == DIFF_IMPOSSIBLE)
2537 diff = DIFF_UNREASONABLE;
2538 else
2539 diff = DIFF_AMBIGUOUS;
2540 }
2541 /* if we've found >1 solution, or ran out of recursion,
2542 * give up immediately. */
2543 if (diff == DIFF_AMBIGUOUS || diff == DIFF_UNFINISHED)
2544 break;
2545 }
2546
2547 if (outgrid) {
2548 /* we found (at least one) soln; copy it back to state */
2549 memcpy(state->grid, outgrid, gsz * sizeof(space));
2550 sfree(outgrid);
2551 }
2552 sfree(ingrid);
2553 return diff;
2554}
2555
2556static int solver_state_inner(game_state *state, int maxdiff, int depth)
2557{
2558 solver_ctx *sctx = new_solver(state);
2559 int ret, diff = DIFF_NORMAL;
2560
2561#ifdef STANDALONE_PICTURE_GENERATOR
2562 /* hack, hack: set picture to NULL during solving so that add_assoc
2563 * won't complain when we attempt recursive guessing and guess wrong */
2564 int *savepic = picture;
2565 picture = NULL;
2566#endif
2567
2568#ifdef STATIC_RECURSION_DEPTH
2569 solver_recurse_depth = depth;
2570#endif
2571
2572 ret = solver_obvious(state);
2573 if (ret < 0) {
2574 diff = DIFF_IMPOSSIBLE;
2575 goto got_result;
2576 }
2577
2578#define CHECKRET(d) do { \
2579 if (ret < 0) { diff = DIFF_IMPOSSIBLE; goto got_result; } \
2580 if (ret > 0) { diff = max(diff, (d)); goto cont; } \
2581} while(0)
2582
2583 while (1) {
2584cont:
2585 ret = foreach_edge(state, solver_lines_opposite_cb,
2586 IMPOSSIBLE_QUITS, sctx);
2587 CHECKRET(DIFF_NORMAL);
2588
2589 ret = foreach_tile(state, solver_spaces_oneposs_cb,
2590 IMPOSSIBLE_QUITS, sctx);
2591 CHECKRET(DIFF_NORMAL);
2592
2593 ret = solver_expand_dots(state, sctx);
2594 CHECKRET(DIFF_NORMAL);
2595
2596 ret = solver_extend_exclaves(state, sctx);
2597 CHECKRET(DIFF_NORMAL);
2598
2599 if (maxdiff <= DIFF_NORMAL)
2600 break;
2601
2602 /* harder still? */
2603
2604 /* if we reach here, we've made no deductions, so we terminate. */
2605 break;
2606 }
2607
2608 if (check_complete(state, NULL, NULL)) goto got_result;
2609
2610 diff = (maxdiff >= DIFF_UNREASONABLE) ?
2611 solver_recurse(state, maxdiff, depth) : DIFF_UNFINISHED;
2612
2613got_result:
2614 free_solver(sctx);
2615#ifndef STANDALONE_SOLVER
2616 debug(("solver_state ends, diff %s:\n", galaxies_diffnames[diff]));
2617 dbg_state(state);
2618#endif
2619
2620#ifdef STANDALONE_PICTURE_GENERATOR
2621 picture = savepic;
2622#endif
2623
2624 return diff;
2625}
2626
2627static int solver_state(game_state *state, int maxdiff)
2628{
2629 return solver_state_inner(state, maxdiff, 0);
2630}
2631
2632#ifndef EDITOR
2633static char *solve_game(const game_state *state, const game_state *currstate,
2634 const char *aux, const char **error)
2635{
2636 game_state *tosolve;
2637 char *ret;
2638 int i;
2639 int diff;
2640
2641 if (aux) {
2642 tosolve = execute_move(state, aux);
2643 goto solved;
2644 } else {
2645 tosolve = dup_game(currstate);
2646 diff = solver_state(tosolve, DIFF_UNREASONABLE);
2647 if (diff != DIFF_UNFINISHED && diff != DIFF_IMPOSSIBLE) {
2648 debug(("solve_game solved with current state.\n"));
2649 goto solved;
2650 }
2651 free_game(tosolve);
2652
2653 tosolve = dup_game(state);
2654 diff = solver_state(tosolve, DIFF_UNREASONABLE);
2655 if (diff != DIFF_UNFINISHED && diff != DIFF_IMPOSSIBLE) {
2656 debug(("solve_game solved with original state.\n"));
2657 goto solved;
2658 }
2659 free_game(tosolve);
2660 }
2661
2662 return NULL;
2663
2664solved:
2665 /*
2666 * Clear tile associations: the solution will only include the
2667 * edges.
2668 */
2669 for (i = 0; i < tosolve->sx*tosolve->sy; i++)
2670 tosolve->grid[i].flags &= ~F_TILE_ASSOC;
2671 ret = diff_game(currstate, tosolve, true, -1);
2672 free_game(tosolve);
2673 return ret;
2674}
2675#endif
2676
2677/* ----------------------------------------------------------
2678 * User interface.
2679 */
2680
2681struct game_ui {
2682 bool dragging;
2683 int dx, dy; /* pixel coords of drag pos. */
2684 int dotx, doty; /* grid coords of dot we're dragging from. */
2685 int srcx, srcy; /* grid coords of drag start */
2686 int cur_x, cur_y;
2687 bool cur_visible;
2688};
2689
2690static game_ui *new_ui(const game_state *state)
2691{
2692 game_ui *ui = snew(game_ui);
2693 ui->dragging = false;
2694 ui->cur_x = ui->cur_y = 1;
2695 ui->cur_visible = getenv_bool("PUZZLES_SHOW_CURSOR", false);
2696 return ui;
2697}
2698
2699static void free_ui(game_ui *ui)
2700{
2701 sfree(ui);
2702}
2703
2704static void game_changed_state(game_ui *ui, const game_state *oldstate,
2705 const game_state *newstate)
2706{
2707}
2708
2709#define FLASH_TIME 0.15F
2710
2711#define PREFERRED_TILE_SIZE 32
2712#define TILE_SIZE (ds->tilesize)
2713#define DOT_SIZE (TILE_SIZE / 4)
2714#define EDGE_THICKNESS (max(TILE_SIZE / 16, 2))
2715#define BORDER TILE_SIZE
2716
2717#define COORD(x) ( (x) * TILE_SIZE + BORDER )
2718#define SCOORD(x) ( ((x) * TILE_SIZE)/2 + BORDER )
2719#define FROMCOORD(x) ( ((x) - BORDER) / TILE_SIZE )
2720
2721#define DRAW_WIDTH (BORDER * 2 + ds->w * TILE_SIZE)
2722#define DRAW_HEIGHT (BORDER * 2 + ds->h * TILE_SIZE)
2723
2724#define CURSOR_SIZE DOT_SIZE
2725
2726struct game_drawstate {
2727 bool started;
2728 int w, h;
2729 int tilesize;
2730 unsigned long *grid;
2731 int *dx, *dy;
2732 blitter *bl;
2733 blitter *blmirror;
2734
2735 bool dragging;
2736 int dragx, dragy, oppx, oppy;
2737
2738 int *colour_scratch;
2739
2740 int cx, cy;
2741 bool cur_visible;
2742 blitter *cur_bl;
2743};
2744
2745#define CORNER_TOLERANCE 0.15F
2746#define CENTRE_TOLERANCE 0.15F
2747
2748/*
2749 * Round FP coordinates to the centre of the nearest edge.
2750 */
2751#ifndef EDITOR
2752static void coord_round_to_edge(float x, float y, int *xr, int *yr)
2753{
2754 float xs, ys, xv, yv, dx, dy;
2755
2756 /*
2757 * Find the nearest square-centre.
2758 */
2759 xs = (float)floor(x) + 0.5F;
2760 ys = (float)floor(y) + 0.5F;
2761
2762 /*
2763 * Find the nearest grid vertex.
2764 */
2765 xv = (float)floor(x + 0.5F);
2766 yv = (float)floor(y + 0.5F);
2767
2768 /*
2769 * Determine whether the horizontal or vertical edge from that
2770 * vertex alongside that square is closer to us, by comparing
2771 * distances from the square cente.
2772 */
2773 dx = (float)fabs(x - xs);
2774 dy = (float)fabs(y - ys);
2775 if (dx > dy) {
2776 /* Vertical edge: x-coord of corner,
2777 * y-coord of square centre. */
2778 *xr = 2 * (int)xv;
2779 *yr = 1 + 2 * (int)floor(ys);
2780 } else {
2781 /* Horizontal edge: x-coord of square centre,
2782 * y-coord of corner. */
2783 *xr = 1 + 2 * (int)floor(xs);
2784 *yr = 2 * (int)yv;
2785 }
2786}
2787#endif
2788
2789#ifdef EDITOR
2790static char *interpret_move(const game_state *state, game_ui *ui,
2791 const game_drawstate *ds,
2792 int x, int y, int button)
2793{
2794 char buf[80];
2795 int px, py;
2796 space *sp;
2797
2798 px = 2*FROMCOORD((float)x) + 0.5F;
2799 py = 2*FROMCOORD((float)y) + 0.5F;
2800
2801 if (button == 'C' || button == 'c') return dupstr("C");
2802
2803 if (button == 'S' || button == 's') {
2804 char *ret;
2805 game_state *tmp = dup_game(state);
2806 int cdiff = solver_state(tmp, DIFF_UNREASONABLE-1);
2807 ret = diff_game(state, tmp, 0, cdiff);
2808 free_game(tmp);
2809 return ret;
2810 }
2811
2812 if (button == LEFT_BUTTON || button == RIGHT_BUTTON) {
2813 if (!INUI(state, px, py)) return MOVE_UNUSED;
2814 sp = &SPACE(state, px, py);
2815 if (!dot_is_possible(state, sp, 1)) return MOVE_NO_EFFECT;
2816 sprintf(buf, "%c%d,%d",
2817 (char)((button == LEFT_BUTTON) ? 'D' : 'd'), px, py);
2818 return dupstr(buf);
2819 }
2820
2821 return MOVE_UNUSED;
2822}
2823#else
2824static bool edge_placement_legal(const game_state *state, int x, int y)
2825{
2826 space *sp = &SPACE(state, x, y);
2827 if (sp->type != s_edge)
2828 return false; /* this is a face-centre or a grid vertex */
2829
2830 /* Check this line doesn't actually intersect a dot */
2831 unsigned int flags = (GRID(state, grid, x, y).flags |
2832 GRID(state, grid, x & ~1U, y & ~1U).flags |
2833 GRID(state, grid, (x+1) & ~1U, (y+1) & ~1U).flags);
2834 if (flags & F_DOT)
2835 return false;
2836 return true;
2837}
2838
2839static const char *current_key_label(const game_ui *ui,
2840 const game_state *state, int button)
2841{
2842 space *sp;
2843
2844 if (IS_CURSOR_SELECT(button) && ui->cur_visible) {
2845 sp = &SPACE(state, ui->cur_x, ui->cur_y);
2846 if (ui->dragging) {
2847 if (ui->cur_x == ui->srcx && ui->cur_y == ui->srcy)
2848 return "Cancel";
2849 if (ok_to_add_assoc_with_opposite(
2850 state, &SPACE(state, ui->cur_x, ui->cur_y),
2851 &SPACE(state, ui->dotx, ui->doty)))
2852 return "Place";
2853 return (ui->srcx == ui->dotx && ui->srcy == ui->doty) ?
2854 "Cancel" : "Remove";
2855 } else if (sp->flags & F_DOT)
2856 return "New arrow";
2857 else if (sp->flags & F_TILE_ASSOC)
2858 return "Move arrow";
2859 else if (sp->type == s_edge &&
2860 edge_placement_legal(state, ui->cur_x, ui->cur_y))
2861 return (sp->flags & F_EDGE_SET) ? "Clear" : "Edge";
2862 }
2863 return "";
2864}
2865
2866static char *interpret_move(const game_state *state, game_ui *ui,
2867 const game_drawstate *ds,
2868 int x, int y, int button)
2869{
2870 /* UI operations (play mode):
2871 *
2872 * Toggle edge (set/unset) (left-click on edge)
2873 * Associate space with dot (left-drag from dot)
2874 * Unassociate space (left-drag from space off grid)
2875 * Autofill lines around shape? (right-click?)
2876 *
2877 * (edit mode; will clear all lines/associations)
2878 *
2879 * Add or remove dot (left-click)
2880 */
2881 char buf[80];
2882 const char *sep = "";
2883 int px, py;
2884 space *sp, *dot;
2885
2886 buf[0] = '\0';
2887
2888 if (button == 'H' || button == 'h') {
2889 char *ret;
2890 game_state *tmp = dup_game(state);
2891 solver_obvious(tmp);
2892 ret = diff_game(state, tmp, false, -1);
2893 free_game(tmp);
2894 return ret;
2895 }
2896
2897 if (button == LEFT_BUTTON) {
2898 ui->cur_visible = false;
2899 coord_round_to_edge(FROMCOORD((float)x), FROMCOORD((float)y),
2900 &px, &py);
2901
2902 if (!INUI(state, px, py)) return MOVE_UNUSED;
2903 if (!edge_placement_legal(state, px, py))
2904 return MOVE_NO_EFFECT;
2905
2906 sprintf(buf, "E%d,%d", px, py);
2907 return dupstr(buf);
2908 } else if (button == RIGHT_BUTTON) {
2909 int px1, py1;
2910
2911 ui->cur_visible = false;
2912
2913 px = (int)(2*FROMCOORD((float)x) + 0.5F);
2914 py = (int)(2*FROMCOORD((float)y) + 0.5F);
2915
2916 dot = NULL;
2917
2918 /*
2919 * If there's a dot anywhere nearby, we pick up an arrow
2920 * pointing at that dot.
2921 */
2922 for (py1 = py-1; py1 <= py+1; py1++)
2923 for (px1 = px-1; px1 <= px+1; px1++) {
2924 if (px1 >= 0 && px1 < state->sx &&
2925 py1 >= 0 && py1 < state->sy &&
2926 x >= SCOORD(px1-1) && x < SCOORD(px1+1) &&
2927 y >= SCOORD(py1-1) && y < SCOORD(py1+1) &&
2928 SPACE(state, px1, py1).flags & F_DOT) {
2929 /*
2930 * Found a dot. Begin a drag from it.
2931 */
2932 dot = &SPACE(state, px1, py1);
2933 ui->srcx = px1;
2934 ui->srcy = py1;
2935 goto done; /* multi-level break */
2936 }
2937 }
2938
2939 /*
2940 * Otherwise, find the nearest _square_, and pick up the
2941 * same arrow as it's got on it, if any.
2942 */
2943 if (!dot) {
2944 px = 2*FROMCOORD(x+TILE_SIZE) - 1;
2945 py = 2*FROMCOORD(y+TILE_SIZE) - 1;
2946 if (px >= 0 && px < state->sx && py >= 0 && py < state->sy) {
2947 sp = &SPACE(state, px, py);
2948 if (sp->flags & F_TILE_ASSOC) {
2949 dot = &SPACE(state, sp->dotx, sp->doty);
2950 ui->srcx = px;
2951 ui->srcy = py;
2952 }
2953 }
2954 }
2955
2956 done:
2957 /*
2958 * Now, if we've managed to find a dot, begin a drag.
2959 */
2960 if (dot) {
2961 ui->dragging = true;
2962 ui->dx = x;
2963 ui->dy = y;
2964 ui->dotx = dot->x;
2965 ui->doty = dot->y;
2966 return MOVE_UI_UPDATE;
2967 }
2968 return MOVE_NO_EFFECT;
2969 } else if (button == RIGHT_DRAG && ui->dragging) {
2970 /* just move the drag coords. */
2971 ui->dx = x;
2972 ui->dy = y;
2973 return MOVE_UI_UPDATE;
2974 } else if (button == RIGHT_RELEASE && ui->dragging) {
2975 /*
2976 * Drags are always targeted at a single square.
2977 */
2978 px = 2*FROMCOORD(x+TILE_SIZE) - 1;
2979 py = 2*FROMCOORD(y+TILE_SIZE) - 1;
2980
2981 dropped: /* We arrive here from the end of a keyboard drag. */
2982 ui->dragging = false;
2983 /*
2984 * Dragging an arrow on to the same square it started from
2985 * is a null move; just update the ui and finish.
2986 */
2987 if (px == ui->srcx && py == ui->srcy)
2988 return MOVE_UI_UPDATE;
2989
2990 /*
2991 * Otherwise, we remove the arrow from its starting
2992 * square if we didn't start from a dot...
2993 */
2994 if ((ui->srcx != ui->dotx || ui->srcy != ui->doty) &&
2995 SPACE(state, ui->srcx, ui->srcy).flags & F_TILE_ASSOC) {
2996 sprintf(buf + strlen(buf), "%sU%d,%d", sep, ui->srcx, ui->srcy);
2997 sep = ";";
2998 }
2999
3000 /*
3001 * ... and if the square we're moving it _to_ is valid, we
3002 * add one there instead.
3003 */
3004 if (INUI(state, px, py)) {
3005 sp = &SPACE(state, px, py);
3006 dot = &SPACE(state, ui->dotx, ui->doty);
3007
3008 /*
3009 * Exception: if it's not actually legal to add an arrow
3010 * and its opposite at this position, we don't try,
3011 * because otherwise we'd append an empty entry to the
3012 * undo chain.
3013 */
3014 if (ok_to_add_assoc_with_opposite(state, sp, dot))
3015 sprintf(buf + strlen(buf), "%sA%d,%d,%d,%d",
3016 sep, px, py, ui->dotx, ui->doty);
3017 }
3018
3019 if (buf[0])
3020 return dupstr(buf);
3021 else
3022 return MOVE_UI_UPDATE;
3023 } else if (IS_CURSOR_MOVE(button)) {
3024 int cx = ui->cur_x - 1, cy = ui->cur_y - 1;
3025 char *ret = move_cursor(button, &cx, &cy, state->sx-2, state->sy-2,
3026 false, &ui->cur_visible);
3027 ui->cur_x = cx + 1, ui->cur_y = cy + 1;
3028 if (ui->dragging) {
3029 ui->dx = SCOORD(ui->cur_x);
3030 ui->dy = SCOORD(ui->cur_y);
3031 }
3032 return ret;
3033 } else if (IS_CURSOR_SELECT(button)) {
3034 if (!ui->cur_visible) {
3035 ui->cur_visible = true;
3036 return MOVE_UI_UPDATE;
3037 }
3038 sp = &SPACE(state, ui->cur_x, ui->cur_y);
3039 if (ui->dragging) {
3040 px = ui->cur_x; py = ui->cur_y;
3041 goto dropped;
3042 } else if (sp->flags & F_DOT) {
3043 ui->dragging = true;
3044 ui->dx = SCOORD(ui->cur_x);
3045 ui->dy = SCOORD(ui->cur_y);
3046 ui->dotx = ui->srcx = ui->cur_x;
3047 ui->doty = ui->srcy = ui->cur_y;
3048 return MOVE_UI_UPDATE;
3049 } else if (sp->flags & F_TILE_ASSOC) {
3050 assert(sp->type == s_tile);
3051 ui->dragging = true;
3052 ui->dx = SCOORD(ui->cur_x);
3053 ui->dy = SCOORD(ui->cur_y);
3054 ui->dotx = sp->dotx;
3055 ui->doty = sp->doty;
3056 ui->srcx = ui->cur_x;
3057 ui->srcy = ui->cur_y;
3058 return MOVE_UI_UPDATE;
3059 } else if (sp->type == s_edge &&
3060 edge_placement_legal(state, ui->cur_x, ui->cur_y)) {
3061 sprintf(buf, "E%d,%d", ui->cur_x, ui->cur_y);
3062 return dupstr(buf);
3063 }
3064 }
3065
3066 return MOVE_UNUSED;
3067}
3068#endif
3069
3070static bool check_complete(const game_state *state, DSF *dsf, int *colours)
3071{
3072 int w = state->w, h = state->h;
3073 int x, y, i;
3074 bool ret;
3075
3076 bool free_dsf;
3077 struct sqdata {
3078 int minx, miny, maxx, maxy;
3079 int cx, cy;
3080 bool valid;
3081 int colour;
3082 } *sqdata;
3083
3084 if (!dsf) {
3085 dsf = dsf_new(w*h);
3086 free_dsf = true;
3087 } else {
3088 dsf_reinit(dsf);
3089 free_dsf = false;
3090 }
3091
3092 /*
3093 * During actual game play, completion checking is done on the
3094 * basis of the edges rather than the square associations. So
3095 * first we must go through the grid figuring out the connected
3096 * components into which the edges divide it.
3097 */
3098 for (y = 0; y < h; y++)
3099 for (x = 0; x < w; x++) {
3100 if (y+1 < h && !(SPACE(state, 2*x+1, 2*y+2).flags & F_EDGE_SET))
3101 dsf_merge(dsf, y*w+x, (y+1)*w+x);
3102 if (x+1 < w && !(SPACE(state, 2*x+2, 2*y+1).flags & F_EDGE_SET))
3103 dsf_merge(dsf, y*w+x, y*w+(x+1));
3104 }
3105
3106 /*
3107 * That gives us our connected components. Now, for each
3108 * component, decide whether it's _valid_. A valid component is
3109 * one which:
3110 *
3111 * - is 180-degree rotationally symmetric
3112 * - has a dot at its centre of symmetry
3113 * - has no other dots anywhere within it (including on its
3114 * boundary)
3115 * - contains no internal edges (i.e. edges separating two
3116 * squares which are both part of the component).
3117 */
3118
3119 /*
3120 * First, go through the grid finding the bounding box of each
3121 * component.
3122 */
3123 sqdata = snewn(w*h, struct sqdata);
3124 for (i = 0; i < w*h; i++) {
3125 sqdata[i].minx = w+1;
3126 sqdata[i].miny = h+1;
3127 sqdata[i].maxx = sqdata[i].maxy = -1;
3128 sqdata[i].valid = false;
3129 }
3130 for (y = 0; y < h; y++)
3131 for (x = 0; x < w; x++) {
3132 i = dsf_canonify(dsf, y*w+x);
3133 if (sqdata[i].minx > x)
3134 sqdata[i].minx = x;
3135 if (sqdata[i].maxx < x)
3136 sqdata[i].maxx = x;
3137 if (sqdata[i].miny > y)
3138 sqdata[i].miny = y;
3139 if (sqdata[i].maxy < y)
3140 sqdata[i].maxy = y;
3141 sqdata[i].valid = true;
3142 }
3143
3144 /*
3145 * Now we're in a position to loop over each actual component
3146 * and figure out where its centre of symmetry has to be if
3147 * it's anywhere.
3148 */
3149 for (i = 0; i < w*h; i++)
3150 if (sqdata[i].valid) {
3151 int cx, cy;
3152 cx = sqdata[i].cx = sqdata[i].minx + sqdata[i].maxx + 1;
3153 cy = sqdata[i].cy = sqdata[i].miny + sqdata[i].maxy + 1;
3154 if (!(SPACE(state, sqdata[i].cx, sqdata[i].cy).flags & F_DOT))
3155 sqdata[i].valid = false; /* no dot at centre of symmetry */
3156 if (dsf_canonify(dsf, (cy-1)/2*w+(cx-1)/2) != i ||
3157 dsf_canonify(dsf, (cy)/2*w+(cx-1)/2) != i ||
3158 dsf_canonify(dsf, (cy-1)/2*w+(cx)/2) != i ||
3159 dsf_canonify(dsf, (cy)/2*w+(cx)/2) != i)
3160 sqdata[i].valid = false; /* dot at cx,cy isn't ours */
3161 if (SPACE(state, sqdata[i].cx, sqdata[i].cy).flags & F_DOT_BLACK)
3162 sqdata[i].colour = 2;
3163 else
3164 sqdata[i].colour = 1;
3165 }
3166
3167 /*
3168 * Now we loop over the whole grid again, this time finding
3169 * extraneous dots (any dot which wholly or partially overlaps
3170 * a square and is not at the centre of symmetry of that
3171 * square's component disqualifies the component from validity)
3172 * and extraneous edges (any edge separating two squares
3173 * belonging to the same component also disqualifies that
3174 * component).
3175 */
3176 for (y = 1; y < state->sy-1; y++)
3177 for (x = 1; x < state->sx-1; x++) {
3178 space *sp = &SPACE(state, x, y);
3179
3180 if (sp->flags & F_DOT) {
3181 /*
3182 * There's a dot here. Use it to disqualify any
3183 * component which deserves it.
3184 */
3185 int cx, cy;
3186 for (cy = (y-1) >> 1; cy <= y >> 1; cy++)
3187 for (cx = (x-1) >> 1; cx <= x >> 1; cx++) {
3188 i = dsf_canonify(dsf, cy*w+cx);
3189 if (x != sqdata[i].cx || y != sqdata[i].cy)
3190 sqdata[i].valid = false;
3191 }
3192 }
3193
3194 if (sp->flags & F_EDGE_SET) {
3195 /*
3196 * There's an edge here. Use it to disqualify a
3197 * component if necessary.
3198 */
3199 int cx1 = (x-1) >> 1, cx2 = x >> 1;
3200 int cy1 = (y-1) >> 1, cy2 = y >> 1;
3201 assert((cx1==cx2) ^ (cy1==cy2));
3202 i = dsf_canonify(dsf, cy1*w+cx1);
3203 if (i == dsf_canonify(dsf, cy2*w+cx2))
3204 sqdata[i].valid = false;
3205 }
3206 }
3207
3208 /*
3209 * And finally we test rotational symmetry: for each square in
3210 * the grid, find which component it's in, test that that
3211 * component also has a square in the symmetric position, and
3212 * disqualify it if it doesn't.
3213 */
3214 for (y = 0; y < h; y++)
3215 for (x = 0; x < w; x++) {
3216 int x2, y2;
3217
3218 i = dsf_canonify(dsf, y*w+x);
3219
3220 x2 = sqdata[i].cx - 1 - x;
3221 y2 = sqdata[i].cy - 1 - y;
3222 if (i != dsf_canonify(dsf, y2*w+x2))
3223 sqdata[i].valid = false;
3224 }
3225
3226 /*
3227 * That's it. We now have all the connected components marked
3228 * as valid or not valid. So now we return a `colours' array if
3229 * we were asked for one, and also we return an overall
3230 * true/false value depending on whether _every_ square in the
3231 * grid is part of a valid component.
3232 */
3233 ret = true;
3234 for (i = 0; i < w*h; i++) {
3235 int ci = dsf_canonify(dsf, i);
3236 bool thisok = sqdata[ci].valid;
3237 if (colours)
3238 colours[i] = thisok ? sqdata[ci].colour : 0;
3239 ret = ret && thisok;
3240 }
3241
3242 sfree(sqdata);
3243 if (free_dsf)
3244 dsf_free(dsf);
3245
3246 return ret;
3247}
3248
3249static game_state *execute_move(const game_state *state, const char *move)
3250{
3251 int x, y, ax, ay, n, dx, dy;
3252 game_state *ret = dup_game(state);
3253 space *sp, *dot;
3254 bool currently_solving = false;
3255
3256 debug(("%s\n", move));
3257
3258 while (*move) {
3259 char c = *move;
3260 if (c == 'E' || c == 'U' || c == 'M'
3261#ifdef EDITOR
3262 || c == 'D' || c == 'd'
3263#endif
3264 ) {
3265 move++;
3266 if (sscanf(move, "%d,%d%n", &x, &y, &n) != 2 ||
3267 !INUI(ret, x, y))
3268 goto badmove;
3269
3270 sp = &SPACE(ret, x, y);
3271#ifdef EDITOR
3272 if (c == 'D' || c == 'd') {
3273 unsigned int currf, newf, maskf;
3274
3275 if (!dot_is_possible(ret, sp, 1)) goto badmove;
3276
3277 newf = F_DOT | (c == 'd' ? F_DOT_BLACK : 0);
3278 currf = GRID(ret, grid, x, y).flags;
3279 maskf = F_DOT | F_DOT_BLACK;
3280 /* if we clicked 'white dot':
3281 * white --> empty, empty --> white, black --> white.
3282 * if we clicked 'black dot':
3283 * black --> empty, empty --> black, white --> black.
3284 */
3285 if (currf & maskf) {
3286 sp->flags &= ~maskf;
3287 if ((currf & maskf) != newf)
3288 sp->flags |= newf;
3289 } else
3290 sp->flags |= newf;
3291 sp->nassoc = 0; /* edit-mode disallows associations. */
3292 game_update_dots(ret);
3293 } else
3294#endif
3295 if (c == 'E') {
3296 if (sp->type != s_edge) goto badmove;
3297 sp->flags ^= F_EDGE_SET;
3298 } else if (c == 'U') {
3299 if (sp->type != s_tile || !(sp->flags & F_TILE_ASSOC))
3300 goto badmove;
3301 /* The solver doesn't assume we'll mirror things */
3302 if (currently_solving)
3303 remove_assoc(ret, sp);
3304 else
3305 remove_assoc_with_opposite(ret, sp);
3306 } else if (c == 'M') {
3307 if (!(sp->flags & F_DOT)) goto badmove;
3308 sp->flags ^= F_DOT_HOLD;
3309 }
3310 move += n;
3311 } else if (c == 'A' || c == 'a') {
3312 move++;
3313 if (sscanf(move, "%d,%d,%d,%d%n", &x, &y, &ax, &ay, &n) != 4 ||
3314 x < 1 || y < 1 || x >= (ret->sx-1) || y >= (ret->sy-1) ||
3315 ax < 1 || ay < 1 || ax >= (ret->sx-1) || ay >= (ret->sy-1))
3316 goto badmove;
3317
3318 dot = &GRID(ret, grid, ax, ay);
3319 if (!(dot->flags & F_DOT))goto badmove;
3320 if (dot->flags & F_DOT_HOLD) goto badmove;
3321
3322 for (dx = -1; dx <= 1; dx++) {
3323 for (dy = -1; dy <= 1; dy++) {
3324 sp = &GRID(ret, grid, x+dx, y+dy);
3325 if (sp->type != s_tile) continue;
3326 if (sp->flags & F_TILE_ASSOC) {
3327 space *dot = &SPACE(ret, sp->dotx, sp->doty);
3328 if (dot->flags & F_DOT_HOLD) continue;
3329 }
3330 /* The solver doesn't assume we'll mirror things */
3331 if (currently_solving)
3332 add_assoc(ret, sp, dot);
3333 else
3334 add_assoc_with_opposite(ret, sp, dot);
3335 }
3336 }
3337 move += n;
3338#ifdef EDITOR
3339 } else if (c == 'C') {
3340 move++;
3341 clear_game(ret, true);
3342 } else if (c == 'i') {
3343 int diff;
3344 move++;
3345 for (diff = 0; diff <= DIFF_UNREASONABLE; diff++)
3346 if (*move == galaxies_diffchars[diff])
3347 break;
3348 if (diff > DIFF_UNREASONABLE)
3349 goto badmove;
3350
3351 ret->cdiff = diff;
3352 move++;
3353 } else if (c == 'I') {
3354 int diff;
3355 move++;
3356 switch (*move) {
3357 case 'A':
3358 diff = DIFF_AMBIGUOUS;
3359 break;
3360 case 'I':
3361 diff = DIFF_IMPOSSIBLE;
3362 break;
3363 case 'U':
3364 diff = DIFF_UNFINISHED;
3365 break;
3366 default:
3367 goto badmove;
3368 }
3369 ret->cdiff = diff;
3370 move++;
3371#endif
3372 } else if (c == 'S') {
3373 move++;
3374 ret->used_solve = true;
3375 currently_solving = true;
3376 } else
3377 goto badmove;
3378
3379 if (*move == ';')
3380 move++;
3381 else if (*move)
3382 goto badmove;
3383 }
3384 if (check_complete(ret, NULL, NULL))
3385 ret->completed = true;
3386 return ret;
3387
3388badmove:
3389 free_game(ret);
3390 return NULL;
3391}
3392
3393/* ----------------------------------------------------------------------
3394 * Drawing routines.
3395 */
3396
3397/* Lines will be much smaller size than squares; say, 1/8 the size?
3398 *
3399 * Need a 'top-left corner of location XxY' to take this into account;
3400 * alternaticaly, that could give the middle of that location, and the
3401 * drawing code would just know the expected dimensions.
3402 *
3403 * We also need something to take a click and work out what it was
3404 * we were interested in. Clicking on vertices is required because
3405 * we may want to drag from them, for example.
3406 */
3407
3408static void game_compute_size(const game_params *params, int sz,
3409 const game_ui *ui, int *x, int *y)
3410{
3411 struct { int tilesize, w, h; } ads, *ds = &ads;
3412
3413 ds->tilesize = sz;
3414 ds->w = params->w;
3415 ds->h = params->h;
3416
3417 *x = DRAW_WIDTH;
3418 *y = DRAW_HEIGHT;
3419}
3420
3421static void game_set_size(drawing *dr, game_drawstate *ds,
3422 const game_params *params, int sz)
3423{
3424 ds->tilesize = sz;
3425
3426 assert(TILE_SIZE > 0);
3427
3428 assert(!ds->bl);
3429 ds->bl = blitter_new(dr, TILE_SIZE, TILE_SIZE);
3430
3431 assert(!ds->blmirror);
3432 ds->blmirror = blitter_new(dr, TILE_SIZE, TILE_SIZE);
3433
3434 assert(!ds->cur_bl);
3435 ds->cur_bl = blitter_new(dr, TILE_SIZE, TILE_SIZE);
3436}
3437
3438static float *game_colours(frontend *fe, int *ncolours)
3439{
3440 float *ret = snewn(3 * NCOLOURS, float);
3441 int i;
3442
3443 /*
3444 * We call game_mkhighlight to ensure the background colour
3445 * isn't completely white. We don't actually use the high- and
3446 * lowlight colours it generates.
3447 */
3448 game_mkhighlight(fe, ret, COL_BACKGROUND, COL_WHITEBG, COL_BLACKBG);
3449
3450 for (i = 0; i < 3; i++) {
3451 /*
3452 * Currently, white dots and white-background squares are
3453 * both pure white.
3454 */
3455 ret[COL_WHITEDOT * 3 + i] = 1.0F;
3456 ret[COL_WHITEBG * 3 + i] = 1.0F;
3457
3458 /*
3459 * But black-background squares are a dark grey, whereas
3460 * black dots are really black.
3461 */
3462 ret[COL_BLACKDOT * 3 + i] = 0.0F;
3463 ret[COL_BLACKBG * 3 + i] = ret[COL_BACKGROUND * 3 + i] * 0.3F;
3464
3465 /*
3466 * In unfilled squares, we draw a faint gridwork.
3467 */
3468 ret[COL_GRID * 3 + i] = ret[COL_BACKGROUND * 3 + i] * 0.8F;
3469
3470 /*
3471 * Edges and arrows are filled in in pure black.
3472 */
3473 ret[COL_EDGE * 3 + i] = 0.0F;
3474 ret[COL_ARROW * 3 + i] = 0.0F;
3475 }
3476
3477#ifdef EDITOR
3478 /* tinge the edit background to bluey */
3479 ret[COL_BACKGROUND * 3 + 0] = ret[COL_BACKGROUND * 3 + 0] * 0.8F;
3480 ret[COL_BACKGROUND * 3 + 1] = ret[COL_BACKGROUND * 3 + 0] * 0.8F;
3481 ret[COL_BACKGROUND * 3 + 2] = min(ret[COL_BACKGROUND * 3 + 0] * 1.4F, 1.0F);
3482#endif
3483
3484 ret[COL_CURSOR * 3 + 0] = min(ret[COL_BACKGROUND * 3 + 0] * 1.4F, 1.0F);
3485 ret[COL_CURSOR * 3 + 1] = ret[COL_BACKGROUND * 3 + 0] * 0.8F;
3486 ret[COL_CURSOR * 3 + 2] = ret[COL_BACKGROUND * 3 + 0] * 0.8F;
3487
3488 *ncolours = NCOLOURS;
3489 return ret;
3490}
3491
3492static game_drawstate *game_new_drawstate(drawing *dr, const game_state *state)
3493{
3494 struct game_drawstate *ds = snew(struct game_drawstate);
3495 int i;
3496
3497 ds->started = false;
3498 ds->w = state->w;
3499 ds->h = state->h;
3500
3501 ds->grid = snewn(ds->w*ds->h, unsigned long);
3502 for (i = 0; i < ds->w*ds->h; i++)
3503 ds->grid[i] = 0xFFFFFFFFUL;
3504 ds->dx = snewn(ds->w*ds->h, int);
3505 ds->dy = snewn(ds->w*ds->h, int);
3506
3507 ds->bl = NULL;
3508 ds->blmirror = NULL;
3509 ds->dragging = false;
3510 ds->dragx = ds->dragy = ds->oppx = ds->oppy = 0;
3511
3512 ds->colour_scratch = snewn(ds->w * ds->h, int);
3513
3514 ds->cur_bl = NULL;
3515 ds->cx = ds->cy = 0;
3516 ds->cur_visible = false;
3517
3518 return ds;
3519}
3520
3521static void game_free_drawstate(drawing *dr, game_drawstate *ds)
3522{
3523 if (ds->cur_bl) blitter_free(dr, ds->cur_bl);
3524 sfree(ds->colour_scratch);
3525 if (ds->blmirror) blitter_free(dr, ds->blmirror);
3526 if (ds->bl) blitter_free(dr, ds->bl);
3527 sfree(ds->dx);
3528 sfree(ds->dy);
3529 sfree(ds->grid);
3530 sfree(ds);
3531}
3532
3533#define DRAW_EDGE_L 0x0001
3534#define DRAW_EDGE_R 0x0002
3535#define DRAW_EDGE_U 0x0004
3536#define DRAW_EDGE_D 0x0008
3537#define DRAW_CORNER_UL 0x0010
3538#define DRAW_CORNER_UR 0x0020
3539#define DRAW_CORNER_DL 0x0040
3540#define DRAW_CORNER_DR 0x0080
3541#define DRAW_WHITE 0x0100
3542#define DRAW_BLACK 0x0200
3543#define DRAW_ARROW 0x0400
3544#define DRAW_CURSOR 0x0800
3545#define DOT_SHIFT_C 12
3546#define DOT_SHIFT_M 2
3547#define DOT_WHITE 1UL
3548#define DOT_BLACK 2UL
3549
3550/*
3551 * Draw an arrow centred on (cx,cy), pointing in the direction
3552 * (ddx,ddy). (I.e. pointing at the point (cx+ddx, cy+ddy).
3553 */
3554static void draw_arrow(drawing *dr, game_drawstate *ds,
3555 int cx, int cy, int ddx, int ddy, int col)
3556{
3557 int sqdist = ddx*ddx+ddy*ddy;
3558 if (sqdist == 0)
3559 return; /* avoid division by zero */
3560 float vlen = (float)sqrt(sqdist);
3561 float xdx = ddx/vlen, xdy = ddy/vlen;
3562 float ydx = -xdy, ydy = xdx;
3563 int e1x = cx + (int)(xdx*TILE_SIZE/3), e1y = cy + (int)(xdy*TILE_SIZE/3);
3564 int e2x = cx - (int)(xdx*TILE_SIZE/3), e2y = cy - (int)(xdy*TILE_SIZE/3);
3565 int adx = (int)((ydx-xdx)*TILE_SIZE/8), ady = (int)((ydy-xdy)*TILE_SIZE/8);
3566 int adx2 = (int)((-ydx-xdx)*TILE_SIZE/8), ady2 = (int)((-ydy-xdy)*TILE_SIZE/8);
3567
3568 draw_line(dr, e1x, e1y, e2x, e2y, col);
3569 draw_line(dr, e1x, e1y, e1x+adx, e1y+ady, col);
3570 draw_line(dr, e1x, e1y, e1x+adx2, e1y+ady2, col);
3571}
3572
3573static void draw_square(drawing *dr, game_drawstate *ds, int x, int y,
3574 unsigned long flags, int ddx, int ddy)
3575{
3576 int lx = COORD(x), ly = COORD(y);
3577 int dx, dy;
3578 int gridcol;
3579
3580 clip(dr, lx, ly, TILE_SIZE, TILE_SIZE);
3581
3582 /*
3583 * Draw the tile background.
3584 */
3585 draw_rect(dr, lx, ly, TILE_SIZE, TILE_SIZE,
3586 (flags & DRAW_WHITE ? COL_WHITEBG :
3587 flags & DRAW_BLACK ? COL_BLACKBG : COL_BACKGROUND));
3588
3589 /*
3590 * Draw the grid.
3591 */
3592 gridcol = (flags & DRAW_BLACK ? COL_BLACKDOT : COL_GRID);
3593 draw_rect(dr, lx, ly, 1, TILE_SIZE, gridcol);
3594 draw_rect(dr, lx, ly, TILE_SIZE, 1, gridcol);
3595
3596 /*
3597 * Draw the arrow, if present, or the cursor, if here.
3598 */
3599 if (flags & DRAW_ARROW)
3600 draw_arrow(dr, ds, lx + TILE_SIZE/2, ly + TILE_SIZE/2, ddx, ddy,
3601 (flags & DRAW_CURSOR) ? COL_CURSOR : COL_ARROW);
3602 else if (flags & DRAW_CURSOR)
3603 draw_rect_outline(dr,
3604 lx + TILE_SIZE/2 - CURSOR_SIZE,
3605 ly + TILE_SIZE/2 - CURSOR_SIZE,
3606 2*CURSOR_SIZE+1, 2*CURSOR_SIZE+1,
3607 COL_CURSOR);
3608
3609 /*
3610 * Draw the edges.
3611 */
3612 if (flags & DRAW_EDGE_L)
3613 draw_rect(dr, lx, ly, EDGE_THICKNESS, TILE_SIZE, COL_EDGE);
3614 if (flags & DRAW_EDGE_R)
3615 draw_rect(dr, lx + TILE_SIZE - EDGE_THICKNESS + 1, ly,
3616 EDGE_THICKNESS - 1, TILE_SIZE, COL_EDGE);
3617 if (flags & DRAW_EDGE_U)
3618 draw_rect(dr, lx, ly, TILE_SIZE, EDGE_THICKNESS, COL_EDGE);
3619 if (flags & DRAW_EDGE_D)
3620 draw_rect(dr, lx, ly + TILE_SIZE - EDGE_THICKNESS + 1,
3621 TILE_SIZE, EDGE_THICKNESS - 1, COL_EDGE);
3622 if (flags & DRAW_CORNER_UL)
3623 draw_rect(dr, lx, ly, EDGE_THICKNESS, EDGE_THICKNESS, COL_EDGE);
3624 if (flags & DRAW_CORNER_UR)
3625 draw_rect(dr, lx + TILE_SIZE - EDGE_THICKNESS + 1, ly,
3626 EDGE_THICKNESS - 1, EDGE_THICKNESS, COL_EDGE);
3627 if (flags & DRAW_CORNER_DL)
3628 draw_rect(dr, lx, ly + TILE_SIZE - EDGE_THICKNESS + 1,
3629 EDGE_THICKNESS, EDGE_THICKNESS - 1, COL_EDGE);
3630 if (flags & DRAW_CORNER_DR)
3631 draw_rect(dr, lx + TILE_SIZE - EDGE_THICKNESS + 1,
3632 ly + TILE_SIZE - EDGE_THICKNESS + 1,
3633 EDGE_THICKNESS - 1, EDGE_THICKNESS - 1, COL_EDGE);
3634
3635 /*
3636 * Draw the dots.
3637 */
3638 for (dy = 0; dy < 3; dy++)
3639 for (dx = 0; dx < 3; dx++) {
3640 int dotval = (flags >> (DOT_SHIFT_C + DOT_SHIFT_M*(dy*3+dx)));
3641 dotval &= (1 << DOT_SHIFT_M)-1;
3642
3643 if (dotval)
3644 draw_circle(dr, lx+dx*TILE_SIZE/2, ly+dy*TILE_SIZE/2,
3645 DOT_SIZE,
3646 (dotval == 1 ? COL_WHITEDOT : COL_BLACKDOT),
3647 COL_BLACKDOT);
3648 }
3649
3650 unclip(dr);
3651 draw_update(dr, lx, ly, TILE_SIZE, TILE_SIZE);
3652}
3653
3654static void calculate_opposite_point(const game_ui *ui,
3655 const game_drawstate *ds, const int x,
3656 const int y, int *oppositex,
3657 int *oppositey)
3658{
3659 /* oppositex - dotx = dotx - x <=> oppositex = 2 * dotx - x */
3660 *oppositex = 2 * SCOORD(ui->dotx) - x;
3661 *oppositey = 2 * SCOORD(ui->doty) - y;
3662}
3663
3664static void game_redraw(drawing *dr, game_drawstate *ds,
3665 const game_state *oldstate, const game_state *state,
3666 int dir, const game_ui *ui,
3667 float animtime, float flashtime)
3668{
3669 int w = ds->w, h = ds->h;
3670 int x, y;
3671 bool flashing = false;
3672
3673 if (flashtime > 0) {
3674 int frame = (int)(flashtime / FLASH_TIME);
3675 flashing = (frame % 2 == 0);
3676 }
3677
3678 if (ds->dragging) {
3679 assert(ds->bl);
3680 assert(ds->blmirror);
3681 blitter_load(dr, ds->blmirror, ds->oppx, ds->oppy);
3682 draw_update(dr, ds->oppx, ds->oppy, TILE_SIZE, TILE_SIZE);
3683 blitter_load(dr, ds->bl, ds->dragx, ds->dragy);
3684 draw_update(dr, ds->dragx, ds->dragy, TILE_SIZE, TILE_SIZE);
3685 ds->dragging = false;
3686 }
3687 if (ds->cur_visible) {
3688 assert(ds->cur_bl);
3689 blitter_load(dr, ds->cur_bl, ds->cx, ds->cy);
3690 draw_update(dr, ds->cx, ds->cy, CURSOR_SIZE*2+1, CURSOR_SIZE*2+1);
3691 ds->cur_visible = false;
3692 }
3693
3694 if (!ds->started) {
3695 draw_rect(dr, BORDER - EDGE_THICKNESS + 1, BORDER - EDGE_THICKNESS + 1,
3696 w*TILE_SIZE + EDGE_THICKNESS*2 - 1,
3697 h*TILE_SIZE + EDGE_THICKNESS*2 - 1, COL_EDGE);
3698 draw_update(dr, 0, 0, DRAW_WIDTH, DRAW_HEIGHT);
3699 ds->started = true;
3700 }
3701
3702 check_complete(state, NULL, ds->colour_scratch);
3703
3704 for (y = 0; y < h; y++)
3705 for (x = 0; x < w; x++) {
3706 unsigned long flags = 0;
3707 int ddx = 0, ddy = 0;
3708 space *sp, *opp;
3709 int dx, dy;
3710
3711 /*
3712 * Set up the flags for this square. Firstly, see if we
3713 * have edges.
3714 */
3715 if (SPACE(state, x*2, y*2+1).flags & F_EDGE_SET)
3716 flags |= DRAW_EDGE_L;
3717 if (SPACE(state, x*2+2, y*2+1).flags & F_EDGE_SET)
3718 flags |= DRAW_EDGE_R;
3719 if (SPACE(state, x*2+1, y*2).flags & F_EDGE_SET)
3720 flags |= DRAW_EDGE_U;
3721 if (SPACE(state, x*2+1, y*2+2).flags & F_EDGE_SET)
3722 flags |= DRAW_EDGE_D;
3723
3724 /*
3725 * Also, mark corners of neighbouring edges.
3726 */
3727 if ((x > 0 && SPACE(state, x*2-1, y*2).flags & F_EDGE_SET) ||
3728 (y > 0 && SPACE(state, x*2, y*2-1).flags & F_EDGE_SET))
3729 flags |= DRAW_CORNER_UL;
3730 if ((x+1 < w && SPACE(state, x*2+3, y*2).flags & F_EDGE_SET) ||
3731 (y > 0 && SPACE(state, x*2+2, y*2-1).flags & F_EDGE_SET))
3732 flags |= DRAW_CORNER_UR;
3733 if ((x > 0 && SPACE(state, x*2-1, y*2+2).flags & F_EDGE_SET) ||
3734 (y+1 < h && SPACE(state, x*2, y*2+3).flags & F_EDGE_SET))
3735 flags |= DRAW_CORNER_DL;
3736 if ((x+1 < w && SPACE(state, x*2+3, y*2+2).flags & F_EDGE_SET) ||
3737 (y+1 < h && SPACE(state, x*2+2, y*2+3).flags & F_EDGE_SET))
3738 flags |= DRAW_CORNER_DR;
3739
3740 /*
3741 * If this square is part of a valid region, paint it
3742 * that region's colour. Exception: if we're flashing,
3743 * everything goes briefly back to background colour.
3744 */
3745 sp = &SPACE(state, x*2+1, y*2+1);
3746 if (sp->flags & F_TILE_ASSOC) {
3747 opp = tile_opposite(state, sp);
3748 } else {
3749 opp = NULL;
3750 }
3751 if (ds->colour_scratch[y*w+x] && !flashing) {
3752 flags |= (ds->colour_scratch[y*w+x] == 2 ?
3753 DRAW_BLACK : DRAW_WHITE);
3754 }
3755
3756 /*
3757 * If this square is associated with a dot but it isn't
3758 * part of a valid region, draw an arrow in it pointing
3759 * in the direction of that dot.
3760 *
3761 * Exception: if this is the source point of an active
3762 * drag, we don't draw the arrow.
3763 */
3764 if ((sp->flags & F_TILE_ASSOC) && !ds->colour_scratch[y*w+x]) {
3765 if (ui->dragging && ui->srcx == x*2+1 && ui->srcy == y*2+1) {
3766 /* tile is the source, don't do it */
3767 } else if (ui->dragging && opp && ui->srcx == opp->x && ui->srcy == opp->y) {
3768 /* opposite tile is the source, don't do it */
3769 } else if (sp->doty != y*2+1 || sp->dotx != x*2+1) {
3770 flags |= DRAW_ARROW;
3771 ddy = sp->doty - (y*2+1);
3772 ddx = sp->dotx - (x*2+1);
3773 }
3774 }
3775
3776 /*
3777 * Now go through the nine possible places we could
3778 * have dots.
3779 */
3780 for (dy = 0; dy < 3; dy++)
3781 for (dx = 0; dx < 3; dx++) {
3782 sp = &SPACE(state, x*2+dx, y*2+dy);
3783 if (sp->flags & F_DOT) {
3784 unsigned long dotval = (sp->flags & F_DOT_BLACK ?
3785 DOT_BLACK : DOT_WHITE);
3786 flags |= dotval << (DOT_SHIFT_C +
3787 DOT_SHIFT_M*(dy*3+dx));
3788 }
3789 }
3790
3791 /*
3792 * Now work out if we have to draw a cursor for this square;
3793 * cursors-on-lines are taken care of below.
3794 */
3795 if (ui->cur_visible &&
3796 ui->cur_x == x*2+1 && ui->cur_y == y*2+1 &&
3797 !(SPACE(state, x*2+1, y*2+1).flags & F_DOT))
3798 flags |= DRAW_CURSOR;
3799
3800 /*
3801 * Now we have everything we're going to need. Draw the
3802 * square.
3803 */
3804 if (ds->grid[y*w+x] != flags ||
3805 ds->dx[y*w+x] != ddx ||
3806 ds->dy[y*w+x] != ddy) {
3807 draw_square(dr, ds, x, y, flags, ddx, ddy);
3808 ds->grid[y*w+x] = flags;
3809 ds->dx[y*w+x] = ddx;
3810 ds->dy[y*w+x] = ddy;
3811 }
3812 }
3813
3814 /*
3815 * Draw a cursor. This secondary blitter is much less invasive than trying
3816 * to fix up all of the rest of the code with sufficient flags to be able to
3817 * display this sensibly.
3818 */
3819 if (ui->cur_visible) {
3820 space *sp = &SPACE(state, ui->cur_x, ui->cur_y);
3821 ds->cur_visible = true;
3822 ds->cx = SCOORD(ui->cur_x) - CURSOR_SIZE;
3823 ds->cy = SCOORD(ui->cur_y) - CURSOR_SIZE;
3824 blitter_save(dr, ds->cur_bl, ds->cx, ds->cy);
3825 if (sp->flags & F_DOT) {
3826 /* draw a red dot (over the top of whatever would be there already) */
3827 draw_circle(dr, SCOORD(ui->cur_x), SCOORD(ui->cur_y), DOT_SIZE,
3828 COL_CURSOR, COL_BLACKDOT);
3829 } else if (sp->type != s_tile) {
3830 /* draw an edge/vertex square; tile cursors are dealt with above. */
3831 int dx = (ui->cur_x % 2) ? CURSOR_SIZE : CURSOR_SIZE/3;
3832 int dy = (ui->cur_y % 2) ? CURSOR_SIZE : CURSOR_SIZE/3;
3833 int x1 = SCOORD(ui->cur_x)-dx, y1 = SCOORD(ui->cur_y)-dy;
3834 int xs = dx*2+1, ys = dy*2+1;
3835
3836 draw_rect(dr, x1, y1, xs, ys, COL_CURSOR);
3837 }
3838 draw_update(dr, ds->cx, ds->cy, CURSOR_SIZE*2+1, CURSOR_SIZE*2+1);
3839 }
3840
3841 if (ui->dragging) {
3842 int oppx, oppy;
3843
3844 ds->dragging = true;
3845 ds->dragx = ui->dx - TILE_SIZE/2;
3846 ds->dragy = ui->dy - TILE_SIZE/2;
3847 calculate_opposite_point(ui, ds, ui->dx, ui->dy, &oppx, &oppy);
3848 ds->oppx = oppx - TILE_SIZE/2;
3849 ds->oppy = oppy - TILE_SIZE/2;
3850
3851 blitter_save(dr, ds->bl, ds->dragx, ds->dragy);
3852 clip(dr, ds->dragx, ds->dragy, TILE_SIZE, TILE_SIZE);
3853 draw_arrow(dr, ds, ui->dx, ui->dy, SCOORD(ui->dotx) - ui->dx,
3854 SCOORD(ui->doty) - ui->dy, COL_ARROW);
3855 unclip(dr);
3856 draw_update(dr, ds->dragx, ds->dragy, TILE_SIZE, TILE_SIZE);
3857
3858 blitter_save(dr, ds->blmirror, ds->oppx, ds->oppy);
3859 clip(dr, ds->oppx, ds->oppy, TILE_SIZE, TILE_SIZE);
3860 draw_arrow(dr, ds, oppx, oppy, SCOORD(ui->dotx) - oppx,
3861 SCOORD(ui->doty) - oppy, COL_ARROW);
3862 unclip(dr);
3863 draw_update(dr, ds->oppx, ds->oppy, TILE_SIZE, TILE_SIZE);
3864 }
3865#ifdef EDITOR
3866 {
3867 char buf[256];
3868 if (state->cdiff != -1)
3869 sprintf(buf, "Puzzle is %s.", galaxies_diffnames[state->cdiff]);
3870 else
3871 buf[0] = '\0';
3872 status_bar(dr, buf);
3873 }
3874#endif
3875}
3876
3877static float game_anim_length(const game_state *oldstate,
3878 const game_state *newstate, int dir, game_ui *ui)
3879{
3880 return 0.0F;
3881}
3882
3883static float game_flash_length(const game_state *oldstate,
3884 const game_state *newstate, int dir, game_ui *ui)
3885{
3886 if ((!oldstate->completed && newstate->completed) &&
3887 !(newstate->used_solve))
3888 return 3 * FLASH_TIME;
3889 else
3890 return 0.0F;
3891}
3892
3893static void game_get_cursor_location(const game_ui *ui,
3894 const game_drawstate *ds,
3895 const game_state *state,
3896 const game_params *params,
3897 int *x, int *y, int *w, int *h)
3898{
3899 if(ui->cur_visible) {
3900 space *sp = &SPACE(state, ui->cur_x, ui->cur_y);
3901
3902 if(sp->flags & F_DOT) {
3903 *x = SCOORD(ui->cur_x) - DOT_SIZE;
3904 *y = SCOORD(ui->cur_y) - DOT_SIZE;
3905 *w = *h = 2 * DOT_SIZE + 1;
3906 } else if(sp->type != s_tile) {
3907 int dx = (ui->cur_x % 2) ? CURSOR_SIZE : CURSOR_SIZE/3;
3908 int dy = (ui->cur_y % 2) ? CURSOR_SIZE : CURSOR_SIZE/3;
3909 int x1 = SCOORD(ui->cur_x)-dx, y1 = SCOORD(ui->cur_y)-dy;
3910 int xs = dx*2+1, ys = dy*2+1;
3911
3912 *x = x1;
3913 *y = y1;
3914 *w = xs;
3915 *h = ys;
3916 } else {
3917 *x = SCOORD(ui->cur_x) - CURSOR_SIZE;
3918 *y = SCOORD(ui->cur_y) - CURSOR_SIZE;
3919 *w = *h = 2 * CURSOR_SIZE + 1;
3920 }
3921 }
3922}
3923
3924static int game_status(const game_state *state)
3925{
3926 return state->completed ? +1 : 0;
3927}
3928
3929#ifndef EDITOR
3930static void game_print_size(const game_params *params, const game_ui *ui,
3931 float *x, float *y)
3932{
3933 int pw, ph;
3934
3935 /*
3936 * 8mm squares by default. (There isn't all that much detail
3937 * that needs to go in each square.)
3938 */
3939 game_compute_size(params, 800, ui, &pw, &ph);
3940 *x = pw / 100.0F;
3941 *y = ph / 100.0F;
3942}
3943
3944static void game_print(drawing *dr, const game_state *state, const game_ui *ui,
3945 int sz)
3946{
3947 int w = state->w, h = state->h;
3948 int white, black, blackish;
3949 int x, y, i, j;
3950 int *colours;
3951 DSF *dsf;
3952 int *coords = NULL;
3953 int ncoords = 0, coordsize = 0;
3954
3955 /* Ick: fake up `ds->tilesize' for macro expansion purposes */
3956 game_drawstate ads, *ds = &ads;
3957 ds->tilesize = sz;
3958
3959 white = print_mono_colour(dr, 1);
3960 black = print_mono_colour(dr, 0);
3961 blackish = print_hatched_colour(dr, HATCH_X);
3962
3963 /*
3964 * Get the completion information.
3965 */
3966 dsf = dsf_new(w * h);
3967 colours = snewn(w * h, int);
3968 check_complete(state, dsf, colours);
3969
3970 /*
3971 * Draw the grid.
3972 */
3973 print_line_width(dr, TILE_SIZE / 64);
3974 for (x = 1; x < w; x++)
3975 draw_line(dr, COORD(x), COORD(0), COORD(x), COORD(h), black);
3976 for (y = 1; y < h; y++)
3977 draw_line(dr, COORD(0), COORD(y), COORD(w), COORD(y), black);
3978
3979 /*
3980 * Shade the completed regions. Just in case any particular
3981 * printing platform deals badly with adjacent
3982 * similarly-hatched regions, we'll fill each one as a single
3983 * polygon.
3984 */
3985 for (i = 0; i < w*h; i++) {
3986 j = dsf_canonify(dsf, i);
3987 if (colours[j] != 0) {
3988 int dx, dy, t;
3989
3990 /*
3991 * This is the first square we've run into belonging to
3992 * this polyomino, which means an edge of the polyomino
3993 * is certain to be to our left. (After we finish
3994 * tracing round it, we'll set the colours[] entry to
3995 * zero to prevent accidentally doing it again.)
3996 */
3997
3998 x = i % w;
3999 y = i / w;
4000 dx = -1;
4001 dy = 0;
4002 ncoords = 0;
4003 while (1) {
4004 /*
4005 * We are currently sitting on square (x,y), which
4006 * we know to be in our polyomino, and we also know
4007 * that (x+dx,y+dy) is not. The way I visualise
4008 * this is that we're standing to the right of a
4009 * boundary line, stretching our left arm out to
4010 * point to the exterior square on the far side.
4011 */
4012
4013 /*
4014 * First, check if we've gone round the entire
4015 * polyomino.
4016 */
4017 if (ncoords > 0 &&
4018 (x == i%w && y == i/w && dx == -1 && dy == 0))
4019 break;
4020
4021 /*
4022 * Add to our coordinate list the coordinate
4023 * backwards and to the left of where we are.
4024 */
4025 if (ncoords + 2 > coordsize) {
4026 coordsize = (ncoords * 3 / 2) + 64;
4027 coords = sresize(coords, coordsize, int);
4028 }
4029 coords[ncoords++] = COORD((2*x+1 + dx + dy) / 2);
4030 coords[ncoords++] = COORD((2*y+1 + dy - dx) / 2);
4031
4032 /*
4033 * Follow the edge round. If the square directly in
4034 * front of us is not part of the polyomino, we
4035 * turn right; if it is and so is the square in
4036 * front of (x+dx,y+dy), we turn left; otherwise we
4037 * go straight on.
4038 */
4039 if (x-dy < 0 || x-dy >= w || y+dx < 0 || y+dx >= h ||
4040 dsf_canonify(dsf, (y+dx)*w+(x-dy)) != j) {
4041 /* Turn right. */
4042 t = dx;
4043 dx = -dy;
4044 dy = t;
4045 } else if (x+dx-dy >= 0 && x+dx-dy < w &&
4046 y+dy+dx >= 0 && y+dy+dx < h &&
4047 dsf_canonify(dsf, (y+dy+dx)*w+(x+dx-dy)) == j) {
4048 /* Turn left. */
4049 x += dx;
4050 y += dy;
4051 t = dx;
4052 dx = dy;
4053 dy = -t;
4054 x -= dx;
4055 y -= dy;
4056 } else {
4057 /* Straight on. */
4058 x -= dy;
4059 y += dx;
4060 }
4061 }
4062
4063 /*
4064 * Now we have our polygon complete, so fill it.
4065 */
4066 draw_polygon(dr, coords, ncoords/2,
4067 colours[j] == 2 ? blackish : -1, black);
4068
4069 /*
4070 * And mark this polyomino as done.
4071 */
4072 colours[j] = 0;
4073 }
4074 }
4075
4076 /*
4077 * Draw the edges.
4078 */
4079 for (y = 0; y <= h; y++)
4080 for (x = 0; x <= w; x++) {
4081 if (x < w && SPACE(state, x*2+1, y*2).flags & F_EDGE_SET)
4082 draw_rect(dr, COORD(x)-EDGE_THICKNESS, COORD(y)-EDGE_THICKNESS,
4083 EDGE_THICKNESS * 2 + TILE_SIZE, EDGE_THICKNESS * 2,
4084 black);
4085 if (y < h && SPACE(state, x*2, y*2+1).flags & F_EDGE_SET)
4086 draw_rect(dr, COORD(x)-EDGE_THICKNESS, COORD(y)-EDGE_THICKNESS,
4087 EDGE_THICKNESS * 2, EDGE_THICKNESS * 2 + TILE_SIZE,
4088 black);
4089 }
4090
4091 /*
4092 * Draw the dots.
4093 */
4094 for (y = 0; y <= 2*h; y++)
4095 for (x = 0; x <= 2*w; x++)
4096 if (SPACE(state, x, y).flags & F_DOT) {
4097 draw_circle(dr, (int)COORD(x/2.0), (int)COORD(y/2.0), DOT_SIZE,
4098 (SPACE(state, x, y).flags & F_DOT_BLACK ?
4099 black : white), black);
4100 }
4101
4102 dsf_free(dsf);
4103 sfree(colours);
4104 sfree(coords);
4105}
4106#endif
4107
4108#ifdef COMBINED
4109#define thegame galaxies
4110#endif
4111
4112const struct game thegame = {
4113 "Galaxies", "games.galaxies", "galaxies",
4114 default_params,
4115 game_fetch_preset, NULL,
4116 decode_params,
4117 encode_params,
4118 free_params,
4119 dup_params,
4120 true, game_configure, custom_params,
4121 validate_params,
4122 new_game_desc,
4123 validate_desc,
4124 new_game,
4125 dup_game,
4126 free_game,
4127#ifdef EDITOR
4128 false, NULL,
4129#else
4130 true, solve_game,
4131#endif
4132 true, game_can_format_as_text_now, game_text_format,
4133 NULL, NULL, /* get_prefs, set_prefs */
4134 new_ui,
4135 free_ui,
4136 NULL, /* encode_ui */
4137 NULL, /* decode_ui */
4138 NULL, /* game_request_keys */
4139 game_changed_state,
4140#ifdef EDITOR
4141 NULL,
4142#else
4143 current_key_label,
4144#endif
4145 interpret_move,
4146 execute_move,
4147 PREFERRED_TILE_SIZE, game_compute_size, game_set_size,
4148 game_colours,
4149 game_new_drawstate,
4150 game_free_drawstate,
4151 game_redraw,
4152 game_anim_length,
4153 game_flash_length,
4154 game_get_cursor_location,
4155 game_status,
4156#ifdef EDITOR
4157 false, false, NULL, NULL,
4158 true, /* wants_statusbar */
4159#else
4160 true, false, game_print_size, game_print,
4161 false, /* wants_statusbar */
4162#endif
4163 false, NULL, /* timing_state */
4164 REQUIRE_RBUTTON, /* flags */
4165};
4166
4167#ifdef STANDALONE_SOLVER
4168
4169static const char *quis;
4170
4171#include <time.h>
4172
4173static void usage_exit(const char *msg)
4174{
4175 if (msg)
4176 fprintf(stderr, "%s: %s\n", quis, msg);
4177 fprintf(stderr, "Usage: %s [--seed SEED] --soak <params> | [game_id [game_id ...]]\n", quis);
4178 exit(1);
4179}
4180
4181static void dump_state(game_state *state)
4182{
4183 char *temp = game_text_format(state);
4184 printf("%s\n", temp);
4185 sfree(temp);
4186}
4187
4188static int gen(game_params *p, random_state *rs, bool debug)
4189{
4190 char *desc;
4191 int diff;
4192 game_state *state;
4193
4194#ifndef DEBUGGING
4195 solver_show_working = debug;
4196#endif
4197 printf("Generating a %dx%d %s puzzle.\n",
4198 p->w, p->h, galaxies_diffnames[p->diff]);
4199
4200 desc = new_game_desc(p, rs, NULL, false);
4201 state = new_game(NULL, p, desc);
4202 dump_state(state);
4203
4204 diff = solver_state(state, DIFF_UNREASONABLE);
4205 printf("Generated %s game %dx%d:%s\n",
4206 galaxies_diffnames[diff], p->w, p->h, desc);
4207 dump_state(state);
4208
4209 free_game(state);
4210 sfree(desc);
4211
4212 return diff;
4213}
4214
4215static void soak(game_params *p, random_state *rs)
4216{
4217 time_t tt_start, tt_now, tt_last;
4218 char *desc;
4219 game_state *st;
4220 int diff, n = 0, i, diffs[DIFF_MAX], ndots = 0, nspaces = 0;
4221
4222#ifndef DEBUGGING
4223 solver_show_working = false;
4224#endif
4225 tt_start = tt_now = time(NULL);
4226 for (i = 0; i < DIFF_MAX; i++) diffs[i] = 0;
4227 one_try = true;
4228
4229 printf("Soak-generating a %dx%d grid, max. diff %s.\n",
4230 p->w, p->h, galaxies_diffnames[p->diff]);
4231 printf(" [");
4232 for (i = 0; i < DIFF_MAX; i++)
4233 printf("%s%s", (i == 0) ? "" : ", ", galaxies_diffnames[i]);
4234 printf("]\n");
4235
4236 while (1) {
4237 char *aux;
4238 desc = new_game_desc(p, rs, &aux, false);
4239 sfree(aux);
4240 st = new_game(NULL, p, desc);
4241 diff = solver_state(st, p->diff);
4242 nspaces += st->w*st->h;
4243 for (i = 0; i < st->sx*st->sy; i++)
4244 if (st->grid[i].flags & F_DOT) ndots++;
4245 free_game(st);
4246 sfree(desc);
4247
4248 diffs[diff]++;
4249 n++;
4250 tt_last = time(NULL);
4251 if (tt_last > tt_now) {
4252 tt_now = tt_last;
4253 printf("%d total, %3.1f/s, [",
4254 n, (double)n / ((double)tt_now - tt_start));
4255 for (i = 0; i < DIFF_MAX; i++)
4256 printf("%s%.1f%%", (i == 0) ? "" : ", ",
4257 100.0 * ((double)diffs[i] / (double)n));
4258 printf("], %.1f%% dots\n",
4259 100.0 * ((double)ndots / (double)nspaces));
4260 }
4261 }
4262}
4263
4264int main(int argc, char **argv)
4265{
4266 game_params *p;
4267 char *id = NULL, *desc;
4268 const char *err;
4269 game_state *s;
4270 int diff;
4271 bool do_soak = false, verbose = false;
4272 random_state *rs;
4273 time_t seed = time(NULL);
4274
4275 quis = argv[0];
4276 while (--argc > 0) {
4277 char *p = *++argv;
4278 if (!strcmp(p, "-v")) {
4279 verbose = true;
4280 } else if (!strcmp(p, "--seed")) {
4281 if (argc == 0) usage_exit("--seed needs an argument");
4282 seed = (time_t)atoi(*++argv);
4283 argc--;
4284 } else if (!strcmp(p, "--soak")) {
4285 do_soak = true;
4286 } else if (*p == '-') {
4287 usage_exit("unrecognised option");
4288 } else {
4289 id = p;
4290 }
4291 }
4292
4293 p = default_params();
4294 rs = random_new((void*)&seed, sizeof(time_t));
4295
4296 if (do_soak) {
4297 if (!id) usage_exit("need one argument for --soak");
4298 decode_params(p, *argv);
4299 soak(p, rs);
4300 return 0;
4301 }
4302
4303 if (!id) {
4304 while (1) {
4305 p->w = random_upto(rs, 15) + 3;
4306 p->h = random_upto(rs, 15) + 3;
4307 p->diff = random_upto(rs, DIFF_UNREASONABLE);
4308 diff = gen(p, rs, false);
4309 }
4310 return 0;
4311 }
4312
4313 desc = strchr(id, ':');
4314 if (!desc) {
4315 decode_params(p, id);
4316 gen(p, rs, verbose);
4317 } else {
4318#ifndef DEBUGGING
4319 solver_show_working = true;
4320#endif
4321 *desc++ = '\0';
4322 decode_params(p, id);
4323 err = validate_desc(p, desc);
4324 if (err) {
4325 fprintf(stderr, "%s: %s\n", argv[0], err);
4326 exit(1);
4327 }
4328 s = new_game(NULL, p, desc);
4329 diff = solver_state(s, DIFF_UNREASONABLE);
4330 dump_state(s);
4331 printf("Puzzle is %s.\n", galaxies_diffnames[diff]);
4332 free_game(s);
4333 }
4334
4335 free_params(p);
4336
4337 return 0;
4338}
4339
4340#endif
4341
4342#ifdef STANDALONE_PICTURE_GENERATOR
4343
4344/*
4345 * Main program for the standalone picture generator. To use it,
4346 * simply provide it with an XBM-format bitmap file (note XBM, not
4347 * XPM) on standard input, and it will output a game ID in return.
4348 * For example:
4349 *
4350 * $ ./galaxiespicture < badly-drawn-cat.xbm
4351 * 11x11:eloMBLzFeEzLNMWifhaWYdDbixCymBbBMLoDdewGg
4352 *
4353 * If you want a puzzle with a non-standard difficulty level, pass
4354 * a partial parameters string as a command-line argument (e.g.
4355 * `./galaxiespicture du < foo.xbm', where `du' is the same suffix
4356 * which if it appeared in a random-seed game ID would set the
4357 * difficulty level to Unreasonable). However, be aware that if the
4358 * generator fails to produce an adequately difficult puzzle too
4359 * many times then it will give up and return an easier one (just
4360 * as it does during normal GUI play). To be sure you really have
4361 * the difficulty you asked for, use galaxiessolver to
4362 * double-check.
4363 *
4364 * (Perhaps I ought to include an option to make this standalone
4365 * generator carry on looping until it really does get the right
4366 * difficulty. Hmmm.)
4367 */
4368
4369#include <time.h>
4370
4371int main(int argc, char **argv)
4372{
4373 game_params *par;
4374 char *params, *desc;
4375 random_state *rs;
4376 time_t seed = time(NULL);
4377 char buf[4096];
4378 int i;
4379 int x, y;
4380
4381 par = default_params();
4382 if (argc > 1)
4383 decode_params(par, argv[1]); /* get difficulty */
4384 par->w = par->h = -1;
4385
4386 /*
4387 * Now read an XBM file from standard input. This is simple and
4388 * hacky and will do very little error detection, so don't feed
4389 * it bogus data.
4390 */
4391 picture = NULL;
4392 x = y = 0;
4393 while (fgets(buf, sizeof(buf), stdin)) {
4394 buf[strcspn(buf, "\r\n")] = '\0';
4395 if (!strncmp(buf, "#define", 7)) {
4396 /*
4397 * Lines starting `#define' give the width and height.
4398 */
4399 char *num = buf + strlen(buf);
4400 char *symend;
4401
4402 while (num > buf && isdigit((unsigned char)num[-1]))
4403 num--;
4404 symend = num;
4405 while (symend > buf && isspace((unsigned char)symend[-1]))
4406 symend--;
4407
4408 if (symend-5 >= buf && !strncmp(symend-5, "width", 5))
4409 par->w = atoi(num);
4410 else if (symend-6 >= buf && !strncmp(symend-6, "height", 6))
4411 par->h = atoi(num);
4412 } else {
4413 /*
4414 * Otherwise, break the string up into words and take
4415 * any word of the form `0x' plus hex digits to be a
4416 * byte.
4417 */
4418 char *p, *wordstart;
4419
4420 if (!picture) {
4421 if (par->w < 0 || par->h < 0) {
4422 printf("failed to read width and height\n");
4423 return 1;
4424 }
4425 picture = snewn(par->w * par->h, int);
4426 for (i = 0; i < par->w * par->h; i++)
4427 picture[i] = -1;
4428 }
4429
4430 p = buf;
4431 while (*p) {
4432 while (*p && (*p == ',' || isspace((unsigned char)*p)))
4433 p++;
4434 wordstart = p;
4435 while (*p && !(*p == ',' || *p == '}' ||
4436 isspace((unsigned char)*p)))
4437 p++;
4438 if (*p)
4439 *p++ = '\0';
4440
4441 if (wordstart[0] == '0' &&
4442 (wordstart[1] == 'x' || wordstart[1] == 'X') &&
4443 !wordstart[2 + strspn(wordstart+2,
4444 "0123456789abcdefABCDEF")]) {
4445 unsigned long byte = strtoul(wordstart+2, NULL, 16);
4446 for (i = 0; i < 8; i++) {
4447 int bit = (byte >> i) & 1;
4448 if (y < par->h && x < par->w)
4449 picture[y * par->w + x] = bit;
4450 x++;
4451 }
4452
4453 if (x >= par->w) {
4454 x = 0;
4455 y++;
4456 }
4457 }
4458 }
4459 }
4460 }
4461
4462 for (i = 0; i < par->w * par->h; i++)
4463 if (picture[i] < 0) {
4464 fprintf(stderr, "failed to read enough bitmap data\n");
4465 return 1;
4466 }
4467
4468 rs = random_new((void*)&seed, sizeof(time_t));
4469
4470 desc = new_game_desc(par, rs, NULL, false);
4471 params = encode_params(par, false);
4472 printf("%s:%s\n", params, desc);
4473
4474 sfree(desc);
4475 sfree(params);
4476 free_params(par);
4477 random_free(rs);
4478
4479 return 0;
4480}
4481
4482#endif
4483
4484/* vim: set shiftwidth=4 tabstop=8: */