2 * bridges.c: Implementation of the Nikoli game 'Bridges'.
6 * - The solver's algorithmic design is not really ideal. It makes
7 * use of the same data representation as gameplay uses, which
8 * often looks like a tempting reuse of code but isn't always a
9 * good idea. In this case, it's unpleasant that each edge of the
10 * graph ends up represented as multiple squares on a grid, with
11 * flags indicating when edges and non-edges cross; that's useful
12 * when the result can be directly translated into positions of
13 * graphics on the display, but in purely internal work it makes
14 * even simple manipulations during solving more painful than they
15 * should be, and complex ones have no choice but to modify the
16 * data structures temporarily, test things, and put them back. I
17 * envisage a complete solver rewrite along the following lines:
18 * + We have a collection of vertices (islands) and edges
19 * (potential bridge locations, i.e. pairs of horizontal or
20 * vertical islands with no other island in between).
21 * + Each edge has an associated list of edges that cross it, and
22 * hence with which it is mutually exclusive.
23 * + For each edge, we track the min and max number of bridges we
24 * currently think possible.
25 * + For each vertex, we track the number of _liberties_ it has,
26 * i.e. its clue number minus the min bridge count for each edge
28 * + We also maintain a dsf that identifies sets of vertices which
29 * are connected components of the puzzle so far, and for each
30 * equivalence class we track the total number of liberties for
31 * that component. (The dsf mechanism will also already track
32 * the size of each component, i.e. number of islands.)
33 * + So incrementing the min for an edge requires processing along
35 * - set the max for all edges crossing that one to zero
36 * - decrement the liberty count for the vertex at each end,
37 * and also for each vertex's equivalence class (NB they may
39 * - unify the two equivalence classes if they're not already,
40 * and if so, set the liberty count for the new class to be
41 * the sum of the previous two.
42 * + Decrementing the max is much easier, however.
43 * + With this data structure the really fiddly stuff in stage3()
44 * becomes more or less trivial, because it's now a quick job to
45 * find out whether an island would form an isolated subgraph if
46 * connected to a given subset of its neighbours:
47 * - identify the connected components containing the test
48 * vertex and its putative new neighbours (but be careful not
49 * to count a component more than once if two or more of the
50 * vertices involved are already in the same one)
51 * - find the sum of those components' liberty counts, and also
52 * the total number of islands involved
53 * - if the total liberty count of the connected components is
54 * exactly equal to twice the number of edges we'd be adding
55 * (of course each edge destroys two liberties, one at each
56 * end) then these components would become a subgraph with
57 * zero liberties if connected together.
58 * - therefore, if that subgraph also contains fewer than the
59 * total number of islands, it's disallowed.
60 * - As mentioned in stage3(), once we've identified such a
61 * disallowed pattern, we have two choices for what to do
62 * with it: if the candidate set of neighbours has size 1 we
63 * can reduce the max for the edge to that one neighbour,
64 * whereas if its complement has size 1 we can increase the
65 * min for the edge to the _omitted_ neighbour.
67 * - write a recursive solver?
79 /* Turn this on for hints about which lines are considered possibilities. */
82 /* --- structures for params, state, etc. --- */
86 #define PREFERRED_TILE_SIZE 24
87 #define TILE_SIZE (ds->tilesize)
88 #define BORDER (TILE_SIZE / 2)
90 #define COORD(x) ( (x) * TILE_SIZE + BORDER )
91 #define FROMCOORD(x) ( ((x) - BORDER + TILE_SIZE) / TILE_SIZE - 1 )
93 #define FLASH_TIME 0.50F
98 COL_HIGHLIGHT, COL_LOWLIGHT,
99 COL_SELECTED, COL_MARK,
108 int islands, expansion; /* %age of island squares, %age chance of expansion */
109 int allowloops, difficulty;
112 /* general flags used by all structs */
113 #define G_ISLAND 0x0001
114 #define G_LINEV 0x0002 /* contains a vert. line */
115 #define G_LINEH 0x0004 /* contains a horiz. line (mutex with LINEV) */
116 #define G_LINE (G_LINEV|G_LINEH)
117 #define G_MARKV 0x0008
118 #define G_MARKH 0x0010
119 #define G_MARK (G_MARKV|G_MARKH)
120 #define G_NOLINEV 0x0020
121 #define G_NOLINEH 0x0040
122 #define G_NOLINE (G_NOLINEV|G_NOLINEH)
124 /* flags used by the error checker */
125 #define G_WARN 0x0080
127 /* flags used by the solver etc. */
128 #define G_SWEEP 0x1000
130 #define G_FLAGSH (G_LINEH|G_MARKH|G_NOLINEH)
131 #define G_FLAGSV (G_LINEV|G_MARKV|G_NOLINEV)
133 typedef unsigned int grid_type; /* change me later if we invent > 16 bits of flags. */
135 struct solver_state {
136 int *dsf, *comptspaces;
137 int *tmpdsf, *tmpcompspaces;
141 /* state->gridi is an optimisation; it stores the pointer to the island
142 * structs indexed by (x,y). It's not strictly necessary (we could use
143 * find234 instead), but Purify showed that board generation (mostly the solver)
144 * was spending 60% of its time in find234. */
146 struct surrounds { /* cloned from lightup.c */
147 struct { int x, y, dx, dy, off; } points[4];
148 int npoints, nislands;
154 struct surrounds adj;
158 int w, h, completed, solved, allowloops, maxb;
160 struct island *islands;
161 int n_islands, n_islands_alloc;
162 game_params params; /* used by the aux solver. */
163 #define N_WH_ARRAYS 5
164 char *wha, *possv, *possh, *lines, *maxv, *maxh;
165 struct island **gridi;
166 struct solver_state *solver; /* refcounted */
169 #define GRIDSZ(s) ((s)->w * (s)->h * sizeof(grid_type))
171 #define INGRID(s,x,y) ((x) >= 0 && (x) < (s)->w && (y) >= 0 && (y) < (s)->h)
173 #define DINDEX(x,y) ((y)*state->w + (x))
175 #define INDEX(s,g,x,y) ((s)->g[(y)*((s)->w) + (x)])
176 #define IDX(s,g,i) ((s)->g[(i)])
177 #define GRID(s,x,y) INDEX(s,grid,x,y)
178 #define POSSIBLES(s,dx,x,y) ((dx) ? (INDEX(s,possh,x,y)) : (INDEX(s,possv,x,y)))
179 #define MAXIMUM(s,dx,x,y) ((dx) ? (INDEX(s,maxh,x,y)) : (INDEX(s,maxv,x,y)))
181 #define GRIDCOUNT(s,x,y,f) ((GRID(s,x,y) & (f)) ? (INDEX(s,lines,x,y)) : 0)
183 #define WITHIN2(x,min,max) (((x) < (min)) ? 0 : (((x) > (max)) ? 0 : 1))
184 #define WITHIN(x,min,max) ((min) > (max) ? \
185 WITHIN2(x,max,min) : WITHIN2(x,min,max))
187 /* --- island struct and tree support functions --- */
189 #define ISLAND_ORTH(is,j,f,df) \
190 (is->f + (is->adj.points[(j)].off*is->adj.points[(j)].df))
192 #define ISLAND_ORTHX(is,j) ISLAND_ORTH(is,j,x,dx)
193 #define ISLAND_ORTHY(is,j) ISLAND_ORTH(is,j,y,dy)
195 static void fixup_islands_for_realloc(game_state *state)
199 for (i = 0; i < state->w*state->h; i++) state->gridi[i] = NULL;
200 for (i = 0; i < state->n_islands; i++) {
201 struct island *is = &state->islands[i];
203 INDEX(state, gridi, is->x, is->y) = is;
207 static int game_can_format_as_text_now(const game_params *params)
212 static char *game_text_format(const game_state *state)
219 len = (state->h) * (state->w+1) + 1;
220 ret = snewn(len, char);
223 for (y = 0; y < state->h; y++) {
224 for (x = 0; x < state->w; x++) {
225 grid = GRID(state,x,y);
226 nl = INDEX(state,lines,x,y);
227 is = INDEX(state, gridi, x, y);
229 *p++ = '0' + is->count;
230 } else if (grid & G_LINEV) {
231 *p++ = (nl > 1) ? '"' : (nl == 1) ? '|' : '!'; /* gaah, want a double-bar. */
232 } else if (grid & G_LINEH) {
233 *p++ = (nl > 1) ? '=' : (nl == 1) ? '-' : '~';
242 assert(p - ret == len);
246 static void debug_state(game_state *state)
248 char *textversion = game_text_format(state);
249 debug(("%s", textversion));
253 /*static void debug_possibles(game_state *state)
256 debug(("possh followed by possv\n"));
257 for (y = 0; y < state->h; y++) {
258 for (x = 0; x < state->w; x++) {
259 debug(("%d", POSSIBLES(state, 1, x, y)));
262 for (x = 0; x < state->w; x++) {
263 debug(("%d", POSSIBLES(state, 0, x, y)));
268 for (y = 0; y < state->h; y++) {
269 for (x = 0; x < state->w; x++) {
270 debug(("%d", MAXIMUM(state, 1, x, y)));
273 for (x = 0; x < state->w; x++) {
274 debug(("%d", MAXIMUM(state, 0, x, y)));
281 static void island_set_surrounds(struct island *is)
283 assert(INGRID(is->state,is->x,is->y));
284 is->adj.npoints = is->adj.nislands = 0;
285 #define ADDPOINT(cond,ddx,ddy) do {\
287 is->adj.points[is->adj.npoints].x = is->x+(ddx); \
288 is->adj.points[is->adj.npoints].y = is->y+(ddy); \
289 is->adj.points[is->adj.npoints].dx = (ddx); \
290 is->adj.points[is->adj.npoints].dy = (ddy); \
291 is->adj.points[is->adj.npoints].off = 0; \
294 ADDPOINT(is->x > 0, -1, 0);
295 ADDPOINT(is->x < (is->state->w-1), +1, 0);
296 ADDPOINT(is->y > 0, 0, -1);
297 ADDPOINT(is->y < (is->state->h-1), 0, +1);
300 static void island_find_orthogonal(struct island *is)
302 /* fills in the rest of the 'surrounds' structure, assuming
303 * all other islands are now in place. */
304 int i, x, y, dx, dy, off;
306 is->adj.nislands = 0;
307 for (i = 0; i < is->adj.npoints; i++) {
308 dx = is->adj.points[i].dx;
309 dy = is->adj.points[i].dy;
313 is->adj.points[i].off = 0;
314 while (INGRID(is->state, x, y)) {
315 if (GRID(is->state, x, y) & G_ISLAND) {
316 is->adj.points[i].off = off;
318 /*debug(("island (%d,%d) has orth is. %d*(%d,%d) away at (%d,%d).\n",
319 is->x, is->y, off, dx, dy,
320 ISLAND_ORTHX(is,i), ISLAND_ORTHY(is,i)));*/
323 off++; x += dx; y += dy;
330 static int island_hasbridge(struct island *is, int direction)
332 int x = is->adj.points[direction].x;
333 int y = is->adj.points[direction].y;
334 grid_type gline = is->adj.points[direction].dx ? G_LINEH : G_LINEV;
336 if (GRID(is->state, x, y) & gline) return 1;
340 static struct island *island_find_connection(struct island *is, int adjpt)
344 assert(adjpt < is->adj.npoints);
345 if (!is->adj.points[adjpt].off) return NULL;
346 if (!island_hasbridge(is, adjpt)) return NULL;
348 is_r = INDEX(is->state, gridi,
349 ISLAND_ORTHX(is, adjpt), ISLAND_ORTHY(is, adjpt));
355 static struct island *island_add(game_state *state, int x, int y, int count)
360 assert(!(GRID(state,x,y) & G_ISLAND));
361 GRID(state,x,y) |= G_ISLAND;
364 if (state->n_islands > state->n_islands_alloc) {
365 state->n_islands_alloc = state->n_islands * 2;
367 sresize(state->islands, state->n_islands_alloc, struct island);
370 is = &state->islands[state->n_islands-1];
372 memset(is, 0, sizeof(struct island));
377 island_set_surrounds(is);
380 fixup_islands_for_realloc(state);
382 INDEX(state, gridi, x, y) = is;
388 /* n = -1 means 'flip NOLINE flags [and set line to 0].' */
389 static void island_join(struct island *i1, struct island *i2, int n, int is_max)
391 game_state *state = i1->state;
394 assert(i1->state == i2->state);
395 assert(n >= -1 && n <= i1->state->maxb);
397 if (i1->x == i2->x) {
400 s = i1->y+1; e = i2->y-1;
402 s = i2->y+1; e = i1->y-1;
404 for (y = s; y <= e; y++) {
406 INDEX(state,maxv,x,y) = n;
409 GRID(state,x,y) ^= G_NOLINEV;
411 GRID(state,x,y) &= ~G_LINEV;
413 GRID(state,x,y) |= G_LINEV;
414 INDEX(state,lines,x,y) = n;
418 } else if (i1->y == i2->y) {
421 s = i1->x+1; e = i2->x-1;
423 s = i2->x+1; e = i1->x-1;
425 for (x = s; x <= e; x++) {
427 INDEX(state,maxh,x,y) = n;
430 GRID(state,x,y) ^= G_NOLINEH;
432 GRID(state,x,y) &= ~G_LINEH;
434 GRID(state,x,y) |= G_LINEH;
435 INDEX(state,lines,x,y) = n;
440 assert(!"island_join: islands not orthogonal.");
444 /* Counts the number of bridges currently attached to the island. */
445 static int island_countbridges(struct island *is)
449 for (i = 0; i < is->adj.npoints; i++) {
450 c += GRIDCOUNT(is->state,
451 is->adj.points[i].x, is->adj.points[i].y,
452 is->adj.points[i].dx ? G_LINEH : G_LINEV);
454 /*debug(("island count for (%d,%d) is %d.\n", is->x, is->y, c));*/
458 static int island_adjspace(struct island *is, int marks, int missing,
461 int x, y, poss, curr, dx;
462 grid_type gline, mline;
464 x = is->adj.points[direction].x;
465 y = is->adj.points[direction].y;
466 dx = is->adj.points[direction].dx;
467 gline = dx ? G_LINEH : G_LINEV;
470 mline = dx ? G_MARKH : G_MARKV;
471 if (GRID(is->state,x,y) & mline) return 0;
473 poss = POSSIBLES(is->state, dx, x, y);
474 poss = min(poss, missing);
476 curr = GRIDCOUNT(is->state, x, y, gline);
477 poss = min(poss, MAXIMUM(is->state, dx, x, y) - curr);
482 /* Counts the number of bridge spaces left around the island;
483 * expects the possibles to be up-to-date. */
484 static int island_countspaces(struct island *is, int marks)
486 int i, c = 0, missing;
488 missing = is->count - island_countbridges(is);
489 if (missing < 0) return 0;
491 for (i = 0; i < is->adj.npoints; i++) {
492 c += island_adjspace(is, marks, missing, i);
497 static int island_isadj(struct island *is, int direction)
500 grid_type gline, mline;
502 x = is->adj.points[direction].x;
503 y = is->adj.points[direction].y;
505 mline = is->adj.points[direction].dx ? G_MARKH : G_MARKV;
506 gline = is->adj.points[direction].dx ? G_LINEH : G_LINEV;
507 if (GRID(is->state, x, y) & mline) {
508 /* If we're marked (i.e. the thing to attach to is complete)
509 * only count an adjacency if we're already attached. */
510 return GRIDCOUNT(is->state, x, y, gline);
512 /* If we're unmarked, count possible adjacency iff it's
513 * flagged as POSSIBLE. */
514 return POSSIBLES(is->state, is->adj.points[direction].dx, x, y);
519 /* Counts the no. of possible adjacent islands (including islands
520 * we're already connected to). */
521 static int island_countadj(struct island *is)
525 for (i = 0; i < is->adj.npoints; i++) {
526 if (island_isadj(is, i)) nadj++;
531 static void island_togglemark(struct island *is)
534 struct island *is_loop;
536 /* mark the island... */
537 GRID(is->state, is->x, is->y) ^= G_MARK;
539 /* ...remove all marks on non-island squares... */
540 for (x = 0; x < is->state->w; x++) {
541 for (y = 0; y < is->state->h; y++) {
542 if (!(GRID(is->state, x, y) & G_ISLAND))
543 GRID(is->state, x, y) &= ~G_MARK;
547 /* ...and add marks to squares around marked islands. */
548 for (i = 0; i < is->state->n_islands; i++) {
549 is_loop = &is->state->islands[i];
550 if (!(GRID(is_loop->state, is_loop->x, is_loop->y) & G_MARK))
553 for (j = 0; j < is_loop->adj.npoints; j++) {
554 /* if this direction takes us to another island, mark all
555 * squares between the two islands. */
556 if (!is_loop->adj.points[j].off) continue;
557 assert(is_loop->adj.points[j].off > 1);
558 for (o = 1; o < is_loop->adj.points[j].off; o++) {
560 is_loop->x + is_loop->adj.points[j].dx*o,
561 is_loop->y + is_loop->adj.points[j].dy*o) |=
562 is_loop->adj.points[j].dy ? G_MARKV : G_MARKH;
568 static int island_impossible(struct island *is, int strict)
570 int curr = island_countbridges(is), nspc = is->count - curr, nsurrspc;
572 struct island *is_orth;
575 debug(("island at (%d,%d) impossible because full.\n", is->x, is->y));
576 return 1; /* too many bridges */
577 } else if ((curr + island_countspaces(is, 0)) < is->count) {
578 debug(("island at (%d,%d) impossible because not enough spaces.\n", is->x, is->y));
579 return 1; /* impossible to create enough bridges */
580 } else if (strict && curr < is->count) {
581 debug(("island at (%d,%d) impossible because locked.\n", is->x, is->y));
582 return 1; /* not enough bridges and island is locked */
585 /* Count spaces in surrounding islands. */
587 for (i = 0; i < is->adj.npoints; i++) {
588 int ifree, dx = is->adj.points[i].dx;
590 if (!is->adj.points[i].off) continue;
591 poss = POSSIBLES(is->state, dx,
592 is->adj.points[i].x, is->adj.points[i].y);
593 if (poss == 0) continue;
594 is_orth = INDEX(is->state, gridi,
595 ISLAND_ORTHX(is,i), ISLAND_ORTHY(is,i));
598 ifree = is_orth->count - island_countbridges(is_orth);
601 * ifree is the number of bridges unfilled in the other
602 * island, which is clearly an upper bound on the number
603 * of extra bridges this island may run to it.
605 * Another upper bound is the number of bridges unfilled
606 * on the specific line between here and there. We must
607 * take the minimum of both.
609 int bmax = MAXIMUM(is->state, dx,
610 is->adj.points[i].x, is->adj.points[i].y);
611 int bcurr = GRIDCOUNT(is->state,
612 is->adj.points[i].x, is->adj.points[i].y,
613 dx ? G_LINEH : G_LINEV);
614 assert(bcurr <= bmax);
615 nsurrspc += min(ifree, bmax - bcurr);
618 if (nsurrspc < nspc) {
619 debug(("island at (%d,%d) impossible: surr. islands %d spc, need %d.\n",
620 is->x, is->y, nsurrspc, nspc));
621 return 1; /* not enough spaces around surrounding islands to fill this one. */
627 /* --- Game parameter functions --- */
629 #define DEFAULT_PRESET 0
631 const struct game_params bridges_presets[] = {
632 { 7, 7, 2, 30, 10, 1, 0 },
633 { 7, 7, 2, 30, 10, 1, 1 },
634 { 7, 7, 2, 30, 10, 1, 2 },
635 { 10, 10, 2, 30, 10, 1, 0 },
636 { 10, 10, 2, 30, 10, 1, 1 },
637 { 10, 10, 2, 30, 10, 1, 2 },
638 { 15, 15, 2, 30, 10, 1, 0 },
639 { 15, 15, 2, 30, 10, 1, 1 },
640 { 15, 15, 2, 30, 10, 1, 2 },
643 static game_params *default_params(void)
645 game_params *ret = snew(game_params);
646 *ret = bridges_presets[DEFAULT_PRESET];
651 static int game_fetch_preset(int i, char **name, game_params **params)
656 if (i < 0 || i >= lenof(bridges_presets))
659 ret = default_params();
660 *ret = bridges_presets[i];
663 sprintf(buf, "%dx%d %s", ret->w, ret->h,
664 ret->difficulty == 0 ? "easy" :
665 ret->difficulty == 1 ? "medium" : "hard");
671 static void free_params(game_params *params)
676 static game_params *dup_params(const game_params *params)
678 game_params *ret = snew(game_params);
679 *ret = *params; /* structure copy */
683 #define EATNUM(x) do { \
684 (x) = atoi(string); \
685 while (*string && isdigit((unsigned char)*string)) string++; \
688 static void decode_params(game_params *params, char const *string)
691 params->h = params->w;
692 if (*string == 'x') {
696 if (*string == 'i') {
698 EATNUM(params->islands);
700 if (*string == 'e') {
702 EATNUM(params->expansion);
704 if (*string == 'm') {
706 EATNUM(params->maxb);
708 params->allowloops = 1;
709 if (*string == 'L') {
711 params->allowloops = 0;
713 if (*string == 'd') {
715 EATNUM(params->difficulty);
719 static char *encode_params(const game_params *params, int full)
724 sprintf(buf, "%dx%di%de%dm%d%sd%d",
725 params->w, params->h, params->islands, params->expansion,
726 params->maxb, params->allowloops ? "" : "L",
729 sprintf(buf, "%dx%dm%d%s", params->w, params->h,
730 params->maxb, params->allowloops ? "" : "L");
735 static config_item *game_configure(const game_params *params)
740 ret = snewn(8, config_item);
742 ret[0].name = "Width";
743 ret[0].type = C_STRING;
744 sprintf(buf, "%d", params->w);
745 ret[0].u.string.sval = dupstr(buf);
747 ret[1].name = "Height";
748 ret[1].type = C_STRING;
749 sprintf(buf, "%d", params->h);
750 ret[1].u.string.sval = dupstr(buf);
752 ret[2].name = "Difficulty";
753 ret[2].type = C_CHOICES;
754 ret[2].u.choices.choicenames = ":Easy:Medium:Hard";
755 ret[2].u.choices.selected = params->difficulty;
757 ret[3].name = "Allow loops";
758 ret[3].type = C_BOOLEAN;
759 ret[3].u.boolean.bval = params->allowloops;
761 ret[4].name = "Max. bridges per direction";
762 ret[4].type = C_CHOICES;
763 ret[4].u.choices.choicenames = ":1:2:3:4"; /* keep up-to-date with
765 ret[4].u.choices.selected = params->maxb - 1;
767 ret[5].name = "%age of island squares";
768 ret[5].type = C_CHOICES;
769 ret[5].u.choices.choicenames = ":5%:10%:15%:20%:25%:30%";
770 ret[5].u.choices.selected = (params->islands / 5)-1;
772 ret[6].name = "Expansion factor (%age)";
773 ret[6].type = C_CHOICES;
774 ret[6].u.choices.choicenames = ":0%:10%:20%:30%:40%:50%:60%:70%:80%:90%:100%";
775 ret[6].u.choices.selected = params->expansion / 10;
783 static game_params *custom_params(const config_item *cfg)
785 game_params *ret = snew(game_params);
787 ret->w = atoi(cfg[0].u.string.sval);
788 ret->h = atoi(cfg[1].u.string.sval);
789 ret->difficulty = cfg[2].u.choices.selected;
790 ret->allowloops = cfg[3].u.boolean.bval;
791 ret->maxb = cfg[4].u.choices.selected + 1;
792 ret->islands = (cfg[5].u.choices.selected + 1) * 5;
793 ret->expansion = cfg[6].u.choices.selected * 10;
798 static char *validate_params(const game_params *params, int full)
800 if (params->w < 3 || params->h < 3)
801 return "Width and height must be at least 3";
802 if (params->maxb < 1 || params->maxb > MAX_BRIDGES)
803 return "Too many bridges.";
805 if (params->islands <= 0 || params->islands > 30)
806 return "%age of island squares must be between 1% and 30%";
807 if (params->expansion < 0 || params->expansion > 100)
808 return "Expansion factor must be between 0 and 100";
813 /* --- Game encoding and differences --- */
815 static char *encode_game(game_state *state)
818 int wh = state->w*state->h, run, x, y;
821 ret = snewn(wh + 1, char);
824 for (y = 0; y < state->h; y++) {
825 for (x = 0; x < state->w; x++) {
826 is = INDEX(state, gridi, x, y);
829 *p++ = ('a'-1) + run;
833 *p++ = '0' + is->count;
835 *p++ = 'A' + (is->count - 10);
838 *p++ = ('a'-1) + run;
846 *p++ = ('a'-1) + run;
850 assert(p - ret <= wh);
855 static char *game_state_diff(const game_state *src, const game_state *dest)
857 int movesize = 256, movelen = 0;
858 char *move = snewn(movesize, char), buf[80];
860 grid_type gline, nline;
861 struct island *is_s, *is_d, *is_orth;
863 #define APPEND do { \
864 if (movelen + len >= movesize) { \
865 movesize = movelen + len + 256; \
866 move = sresize(move, movesize, char); \
868 strcpy(move + movelen, buf); \
872 move[movelen++] = 'S';
873 move[movelen] = '\0';
875 assert(src->n_islands == dest->n_islands);
877 for (i = 0; i < src->n_islands; i++) {
878 is_s = &src->islands[i];
879 is_d = &dest->islands[i];
880 assert(is_s->x == is_d->x);
881 assert(is_s->y == is_d->y);
882 assert(is_s->adj.npoints == is_d->adj.npoints); /* more paranoia */
884 for (d = 0; d < is_s->adj.npoints; d++) {
885 if (is_s->adj.points[d].dx == -1 ||
886 is_s->adj.points[d].dy == -1) continue;
888 x = is_s->adj.points[d].x;
889 y = is_s->adj.points[d].y;
890 gline = is_s->adj.points[d].dx ? G_LINEH : G_LINEV;
891 nline = is_s->adj.points[d].dx ? G_NOLINEH : G_NOLINEV;
892 is_orth = INDEX(dest, gridi,
893 ISLAND_ORTHX(is_d, d), ISLAND_ORTHY(is_d, d));
895 if (GRIDCOUNT(src, x, y, gline) != GRIDCOUNT(dest, x, y, gline)) {
897 len = sprintf(buf, ";L%d,%d,%d,%d,%d",
898 is_s->x, is_s->y, is_orth->x, is_orth->y,
899 GRIDCOUNT(dest, x, y, gline));
902 if ((GRID(src,x,y) & nline) != (GRID(dest, x, y) & nline)) {
904 len = sprintf(buf, ";N%d,%d,%d,%d",
905 is_s->x, is_s->y, is_orth->x, is_orth->y);
909 if ((GRID(src, is_s->x, is_s->y) & G_MARK) !=
910 (GRID(dest, is_d->x, is_d->y) & G_MARK)) {
911 len = sprintf(buf, ";M%d,%d", is_s->x, is_s->y);
918 /* --- Game setup and solving utilities --- */
920 /* This function is optimised; a Quantify showed that lots of grid-generation time
921 * (>50%) was spent in here. Hence the IDX() stuff. */
923 static void map_update_possibles(game_state *state)
925 int x, y, s, e, bl, i, np, maxb, w = state->w, idx;
926 struct island *is_s = NULL, *is_f = NULL;
928 /* Run down vertical stripes [un]setting possv... */
929 for (x = 0; x < state->w; x++) {
933 maxb = state->params.maxb; /* placate optimiser */
934 /* Unset possible flags until we find an island. */
935 for (y = 0; y < state->h; y++) {
936 is_s = IDX(state, gridi, idx);
942 IDX(state, possv, idx) = 0;
945 for (; y < state->h; y++) {
946 maxb = min(maxb, IDX(state, maxv, idx));
947 is_f = IDX(state, gridi, idx);
950 np = min(maxb, is_f->count);
953 for (i = s; i <= e; i++) {
954 INDEX(state, possv, x, i) = bl ? 0 : np;
963 if (IDX(state,grid,idx) & (G_LINEH|G_NOLINEV)) bl = 1;
968 for (i = s; i <= e; i++)
969 INDEX(state, possv, x, i) = 0;
973 /* ...and now do horizontal stripes [un]setting possh. */
974 /* can we lose this clone'n'hack? */
975 for (y = 0; y < state->h; y++) {
979 maxb = state->params.maxb; /* placate optimiser */
980 for (x = 0; x < state->w; x++) {
981 is_s = IDX(state, gridi, idx);
987 IDX(state, possh, idx) = 0;
990 for (; x < state->w; x++) {
991 maxb = min(maxb, IDX(state, maxh, idx));
992 is_f = IDX(state, gridi, idx);
995 np = min(maxb, is_f->count);
998 for (i = s; i <= e; i++) {
999 INDEX(state, possh, i, y) = bl ? 0 : np;
1008 if (IDX(state,grid,idx) & (G_LINEV|G_NOLINEH)) bl = 1;
1013 for (i = s; i <= e; i++)
1014 INDEX(state, possh, i, y) = 0;
1019 static void map_count(game_state *state)
1022 grid_type flag, grid;
1025 for (i = 0; i < state->n_islands; i++) {
1026 is = &state->islands[i];
1028 for (n = 0; n < is->adj.npoints; n++) {
1029 ax = is->adj.points[n].x;
1030 ay = is->adj.points[n].y;
1031 flag = (ax == is->x) ? G_LINEV : G_LINEH;
1032 grid = GRID(state,ax,ay);
1034 is->count += INDEX(state,lines,ax,ay);
1040 static void map_find_orthogonal(game_state *state)
1044 for (i = 0; i < state->n_islands; i++) {
1045 island_find_orthogonal(&state->islands[i]);
1049 struct bridges_neighbour_ctx {
1051 int i, n, neighbours[4];
1053 static int bridges_neighbour(int vertex, void *vctx)
1055 struct bridges_neighbour_ctx *ctx = (struct bridges_neighbour_ctx *)vctx;
1057 game_state *state = ctx->state;
1058 int w = state->w, x = vertex % w, y = vertex / w;
1059 grid_type grid = GRID(state, x, y), gline = grid & G_LINE;
1061 int x1, y1, x2, y2, i;
1063 ctx->i = ctx->n = 0;
1065 is = INDEX(state, gridi, x, y);
1067 for (i = 0; i < is->adj.npoints; i++) {
1068 gline = is->adj.points[i].dx ? G_LINEH : G_LINEV;
1069 if (GRID(state, is->adj.points[i].x,
1070 is->adj.points[i].y) & gline) {
1071 ctx->neighbours[ctx->n++] =
1072 (is->adj.points[i].y * w + is->adj.points[i].x);
1076 if (gline & G_LINEV) {
1083 /* Non-island squares with edges in should never be
1084 * pointing off the edge of the grid. */
1085 assert(INGRID(state, x1, y1));
1086 assert(INGRID(state, x2, y2));
1087 if (GRID(state, x1, y1) & (gline | G_ISLAND))
1088 ctx->neighbours[ctx->n++] = y1 * w + x1;
1089 if (GRID(state, x2, y2) & (gline | G_ISLAND))
1090 ctx->neighbours[ctx->n++] = y2 * w + x2;
1094 if (ctx->i < ctx->n)
1095 return ctx->neighbours[ctx->i++];
1100 static int map_hasloops(game_state *state, int mark)
1103 struct findloopstate *fls;
1104 struct bridges_neighbour_ctx ctx;
1107 fls = findloop_new_state(state->w * state->h);
1109 ret = findloop_run(fls, state->w * state->h, bridges_neighbour, &ctx);
1112 for (y = 0; y < state->h; y++) {
1113 for (x = 0; x < state->w; x++) {
1116 u = y * state->w + x;
1117 for (v = bridges_neighbour(u, &ctx); v >= 0;
1118 v = bridges_neighbour(-1, &ctx))
1119 if (findloop_is_loop_edge(fls, u, v))
1120 GRID(state,x,y) |= G_WARN;
1125 findloop_free_state(fls);
1129 static void map_group(game_state *state)
1131 int i, wh = state->w*state->h, d1, d2;
1133 int *dsf = state->solver->dsf;
1134 struct island *is, *is_join;
1136 /* Initialise dsf. */
1139 /* For each island, find connected islands right or down
1140 * and merge the dsf for the island squares as well as the
1141 * bridge squares. */
1142 for (x = 0; x < state->w; x++) {
1143 for (y = 0; y < state->h; y++) {
1144 GRID(state,x,y) &= ~(G_SWEEP|G_WARN); /* for group_full. */
1146 is = INDEX(state, gridi, x, y);
1149 for (i = 0; i < is->adj.npoints; i++) {
1150 /* only want right/down */
1151 if (is->adj.points[i].dx == -1 ||
1152 is->adj.points[i].dy == -1) continue;
1154 is_join = island_find_connection(is, i);
1155 if (!is_join) continue;
1157 d2 = DINDEX(is_join->x, is_join->y);
1158 if (dsf_canonify(dsf,d1) == dsf_canonify(dsf,d2)) {
1159 ; /* we have a loop. See comment in map_hasloops. */
1160 /* However, we still want to merge all squares joining
1161 * this side-that-makes-a-loop. */
1163 /* merge all squares between island 1 and island 2. */
1164 for (x2 = x; x2 <= is_join->x; x2++) {
1165 for (y2 = y; y2 <= is_join->y; y2++) {
1167 if (d1 != d2) dsf_merge(dsf,d1,d2);
1175 static int map_group_check(game_state *state, int canon, int warn,
1178 int *dsf = state->solver->dsf, nislands = 0;
1179 int x, y, i, allfull = 1;
1182 for (i = 0; i < state->n_islands; i++) {
1183 is = &state->islands[i];
1184 if (dsf_canonify(dsf, DINDEX(is->x,is->y)) != canon) continue;
1186 GRID(state, is->x, is->y) |= G_SWEEP;
1188 if (island_countbridges(is) != is->count)
1191 if (warn && allfull && nislands != state->n_islands) {
1192 /* we're full and this island group isn't the whole set.
1193 * Mark all squares with this dsf canon as ERR. */
1194 for (x = 0; x < state->w; x++) {
1195 for (y = 0; y < state->h; y++) {
1196 if (dsf_canonify(dsf, DINDEX(x,y)) == canon) {
1197 GRID(state,x,y) |= G_WARN;
1203 if (nislands_r) *nislands_r = nislands;
1207 static int map_group_full(game_state *state, int *ngroups_r)
1209 int *dsf = state->solver->dsf, ngroups = 0;
1213 /* NB this assumes map_group (or sth else) has cleared G_SWEEP. */
1215 for (i = 0; i < state->n_islands; i++) {
1216 is = &state->islands[i];
1217 if (GRID(state,is->x,is->y) & G_SWEEP) continue;
1220 if (map_group_check(state, dsf_canonify(dsf, DINDEX(is->x,is->y)),
1225 *ngroups_r = ngroups;
1229 static int map_check(game_state *state)
1233 /* Check for loops, if necessary. */
1234 if (!state->allowloops) {
1235 if (map_hasloops(state, 1))
1239 /* Place islands into island groups and check for early
1240 * satisfied-groups. */
1241 map_group(state); /* clears WARN and SWEEP */
1242 if (map_group_full(state, &ngroups)) {
1243 if (ngroups == 1) return 1;
1248 static void map_clear(game_state *state)
1252 for (x = 0; x < state->w; x++) {
1253 for (y = 0; y < state->h; y++) {
1254 /* clear most flags; might want to be slightly more careful here. */
1255 GRID(state,x,y) &= G_ISLAND;
1260 static void solve_join(struct island *is, int direction, int n, int is_max)
1262 struct island *is_orth;
1263 int d1, d2, *dsf = is->state->solver->dsf;
1264 game_state *state = is->state; /* for DINDEX */
1266 is_orth = INDEX(is->state, gridi,
1267 ISLAND_ORTHX(is, direction),
1268 ISLAND_ORTHY(is, direction));
1270 /*debug(("...joining (%d,%d) to (%d,%d) with %d bridge(s).\n",
1271 is->x, is->y, is_orth->x, is_orth->y, n));*/
1272 island_join(is, is_orth, n, is_max);
1274 if (n > 0 && !is_max) {
1275 d1 = DINDEX(is->x, is->y);
1276 d2 = DINDEX(is_orth->x, is_orth->y);
1277 if (dsf_canonify(dsf, d1) != dsf_canonify(dsf, d2))
1278 dsf_merge(dsf, d1, d2);
1282 static int solve_fillone(struct island *is)
1286 debug(("solve_fillone for island (%d,%d).\n", is->x, is->y));
1288 for (i = 0; i < is->adj.npoints; i++) {
1289 if (island_isadj(is, i)) {
1290 if (island_hasbridge(is, i)) {
1291 /* already attached; do nothing. */;
1293 solve_join(is, i, 1, 0);
1301 static int solve_fill(struct island *is)
1303 /* for each unmarked adjacent, make sure we convert every possible bridge
1304 * to a real one, and then work out the possibles afresh. */
1305 int i, nnew, ncurr, nadded = 0, missing;
1307 debug(("solve_fill for island (%d,%d).\n", is->x, is->y));
1309 missing = is->count - island_countbridges(is);
1310 if (missing < 0) return 0;
1312 /* very like island_countspaces. */
1313 for (i = 0; i < is->adj.npoints; i++) {
1314 nnew = island_adjspace(is, 1, missing, i);
1316 ncurr = GRIDCOUNT(is->state,
1317 is->adj.points[i].x, is->adj.points[i].y,
1318 is->adj.points[i].dx ? G_LINEH : G_LINEV);
1320 solve_join(is, i, nnew + ncurr, 0);
1327 static int solve_island_stage1(struct island *is, int *didsth_r)
1329 int bridges = island_countbridges(is);
1330 int nspaces = island_countspaces(is, 1);
1331 int nadj = island_countadj(is);
1336 /*debug(("island at (%d,%d) filled %d/%d (%d spc) nadj %d\n",
1337 is->x, is->y, bridges, is->count, nspaces, nadj));*/
1338 if (bridges > is->count) {
1339 /* We only ever add bridges when we're sure they fit, or that's
1340 * the only place they can go. If we've added bridges such that
1341 * another island has become wrong, the puzzle must not have had
1343 debug(("...island at (%d,%d) is overpopulated!\n", is->x, is->y));
1345 } else if (bridges == is->count) {
1346 /* This island is full. Make sure it's marked (and update
1347 * possibles if we did). */
1348 if (!(GRID(is->state, is->x, is->y) & G_MARK)) {
1349 debug(("...marking island (%d,%d) as full.\n", is->x, is->y));
1350 island_togglemark(is);
1353 } else if (GRID(is->state, is->x, is->y) & G_MARK) {
1354 debug(("...island (%d,%d) is marked but unfinished!\n",
1356 return 0; /* island has been marked unfinished; no solution from here. */
1358 /* This is the interesting bit; we try and fill in more information
1359 * about this island. */
1360 if (is->count == bridges + nspaces) {
1361 if (solve_fill(is) > 0) didsth = 1;
1362 } else if (is->count > ((nadj-1) * is->state->maxb)) {
1363 /* must have at least one bridge in each possible direction. */
1364 if (solve_fillone(is) > 0) didsth = 1;
1368 map_update_possibles(is->state);
1374 /* returns non-zero if a new line here would cause a loop. */
1375 static int solve_island_checkloop(struct island *is, int direction)
1377 struct island *is_orth;
1378 int *dsf = is->state->solver->dsf, d1, d2;
1379 game_state *state = is->state;
1381 if (is->state->allowloops) return 0; /* don't care anyway */
1382 if (island_hasbridge(is, direction)) return 0; /* already has a bridge */
1383 if (island_isadj(is, direction) == 0) return 0; /* no adj island */
1385 is_orth = INDEX(is->state, gridi,
1386 ISLAND_ORTHX(is,direction),
1387 ISLAND_ORTHY(is,direction));
1388 if (!is_orth) return 0;
1390 d1 = DINDEX(is->x, is->y);
1391 d2 = DINDEX(is_orth->x, is_orth->y);
1392 if (dsf_canonify(dsf, d1) == dsf_canonify(dsf, d2)) {
1393 /* two islands are connected already; don't join them. */
1399 static int solve_island_stage2(struct island *is, int *didsth_r)
1401 int added = 0, removed = 0, navail = 0, nadj, i;
1405 for (i = 0; i < is->adj.npoints; i++) {
1406 if (solve_island_checkloop(is, i)) {
1407 debug(("removing possible loop at (%d,%d) direction %d.\n",
1409 solve_join(is, i, -1, 0);
1410 map_update_possibles(is->state);
1413 navail += island_isadj(is, i);
1414 /*debug(("stage2: navail for (%d,%d) direction (%d,%d) is %d.\n",
1416 is->adj.points[i].dx, is->adj.points[i].dy,
1417 island_isadj(is, i)));*/
1421 /*debug(("island at (%d,%d) navail %d: checking...\n", is->x, is->y, navail));*/
1423 for (i = 0; i < is->adj.npoints; i++) {
1424 if (!island_hasbridge(is, i)) {
1425 nadj = island_isadj(is, i);
1426 if (nadj > 0 && (navail - nadj) < is->count) {
1427 /* we couldn't now complete the island without at
1428 * least one bridge here; put it in. */
1429 /*debug(("nadj %d, navail %d, is->count %d.\n",
1430 nadj, navail, is->count));*/
1431 debug(("island at (%d,%d) direction (%d,%d) must have 1 bridge\n",
1433 is->adj.points[i].dx, is->adj.points[i].dy));
1434 solve_join(is, i, 1, 0);
1436 /*debug_state(is->state);
1437 debug_possibles(is->state);*/
1441 if (added) map_update_possibles(is->state);
1442 if (added || removed) *didsth_r = 1;
1446 static int solve_island_subgroup(struct island *is, int direction)
1448 struct island *is_join;
1449 int nislands, *dsf = is->state->solver->dsf;
1450 game_state *state = is->state;
1452 debug(("..checking subgroups.\n"));
1454 /* if is isn't full, return 0. */
1455 if (island_countbridges(is) < is->count) {
1456 debug(("...orig island (%d,%d) not full.\n", is->x, is->y));
1460 if (direction >= 0) {
1461 is_join = INDEX(state, gridi,
1462 ISLAND_ORTHX(is, direction),
1463 ISLAND_ORTHY(is, direction));
1466 /* if is_join isn't full, return 0. */
1467 if (island_countbridges(is_join) < is_join->count) {
1468 debug(("...dest island (%d,%d) not full.\n",
1469 is_join->x, is_join->y));
1474 /* Check group membership for is->dsf; if it's full return 1. */
1475 if (map_group_check(state, dsf_canonify(dsf, DINDEX(is->x,is->y)),
1477 if (nislands < state->n_islands) {
1478 /* we have a full subgroup that isn't the whole set.
1479 * This isn't allowed. */
1480 debug(("island at (%d,%d) makes full subgroup, disallowing.\n",
1484 debug(("...has finished puzzle.\n"));
1490 static int solve_island_impossible(game_state *state)
1495 /* If any islands are impossible, return 1. */
1496 for (i = 0; i < state->n_islands; i++) {
1497 is = &state->islands[i];
1498 if (island_impossible(is, 0)) {
1499 debug(("island at (%d,%d) has become impossible, disallowing.\n",
1507 /* Bear in mind that this function is really rather inefficient. */
1508 static int solve_island_stage3(struct island *is, int *didsth_r)
1510 int i, n, x, y, missing, spc, curr, maxb, didsth = 0;
1511 int wh = is->state->w * is->state->h;
1512 struct solver_state *ss = is->state->solver;
1516 missing = is->count - island_countbridges(is);
1517 if (missing <= 0) return 1;
1519 for (i = 0; i < is->adj.npoints; i++) {
1520 x = is->adj.points[i].x;
1521 y = is->adj.points[i].y;
1522 spc = island_adjspace(is, 1, missing, i);
1523 if (spc == 0) continue;
1525 curr = GRIDCOUNT(is->state, x, y,
1526 is->adj.points[i].dx ? G_LINEH : G_LINEV);
1527 debug(("island at (%d,%d) s3, trying %d - %d bridges.\n",
1528 is->x, is->y, curr+1, curr+spc));
1530 /* Now we know that this island could have more bridges,
1531 * to bring the total from curr+1 to curr+spc. */
1533 /* We have to squirrel the dsf away and restore it afterwards;
1534 * it is additive only, and can't be removed from. */
1535 memcpy(ss->tmpdsf, ss->dsf, wh*sizeof(int));
1536 for (n = curr+1; n <= curr+spc; n++) {
1537 solve_join(is, i, n, 0);
1538 map_update_possibles(is->state);
1540 if (solve_island_subgroup(is, i) ||
1541 solve_island_impossible(is->state)) {
1543 debug(("island at (%d,%d) d(%d,%d) new max of %d bridges:\n",
1545 is->adj.points[i].dx, is->adj.points[i].dy,
1550 solve_join(is, i, curr, 0); /* put back to before. */
1551 memcpy(ss->dsf, ss->tmpdsf, wh*sizeof(int));
1554 /*debug_state(is->state);*/
1556 debug(("...adding NOLINE.\n"));
1557 solve_join(is, i, -1, 0); /* we can't have any bridges here. */
1559 debug(("...setting maximum\n"));
1560 solve_join(is, i, maxb, 1);
1564 map_update_possibles(is->state);
1567 for (i = 0; i < is->adj.npoints; i++) {
1569 * Now check to see if any currently empty direction must have
1570 * at least one bridge in order to avoid forming an isolated
1571 * subgraph. This differs from the check above in that it
1572 * considers multiple target islands. For example:
1579 * The example on the left can be handled by the above loop:
1580 * it will observe that connecting the central 2 twice to the
1581 * left would form an isolated subgraph, and hence it will
1582 * restrict that 2 to at most one bridge in that direction.
1583 * But the example on the right won't be handled by that loop,
1584 * because the deduction requires us to imagine connecting the
1585 * 3 to _both_ the 1 and 2 at once to form an isolated
1588 * This pass is necessary _as well_ as the above one, because
1589 * neither can do the other's job. In the left one,
1590 * restricting the direction which _would_ cause trouble can
1591 * be done even if it's not yet clear which of the remaining
1592 * directions has to have a compensatory bridge; whereas the
1593 * pass below that can handle the right-hand example does need
1594 * to know what direction to point the necessary bridge in.
1596 * Neither pass can handle the most general case, in which we
1597 * observe that an arbitrary subset of an island's neighbours
1598 * would form an isolated subgraph with it if it connected
1599 * maximally to them, and hence that at least one bridge must
1600 * point to some neighbour outside that subset but we don't
1601 * know which neighbour. To handle that, we'd have to have a
1602 * richer data format for the solver, which could cope with
1603 * recording the idea that at least one of two edges must have
1610 spc = island_adjspace(is, 1, missing, i);
1611 if (spc == 0) continue;
1613 for (j = 0; j < is->adj.npoints; j++)
1614 before[j] = GRIDCOUNT(is->state,
1615 is->adj.points[j].x,
1616 is->adj.points[j].y,
1617 is->adj.points[j].dx ? G_LINEH : G_LINEV);
1618 if (before[i] != 0) continue; /* this idea is pointless otherwise */
1620 memcpy(ss->tmpdsf, ss->dsf, wh*sizeof(int));
1622 for (j = 0; j < is->adj.npoints; j++) {
1623 spc = island_adjspace(is, 1, missing, j);
1624 if (spc == 0) continue;
1625 if (j == i) continue;
1626 solve_join(is, j, before[j] + spc, 0);
1628 map_update_possibles(is->state);
1630 if (solve_island_subgroup(is, -1))
1633 for (j = 0; j < is->adj.npoints; j++)
1634 solve_join(is, j, before[j], 0);
1635 memcpy(ss->dsf, ss->tmpdsf, wh*sizeof(int));
1638 debug(("island at (%d,%d) must connect in direction (%d,%d) to"
1639 " avoid full subgroup.\n",
1640 is->x, is->y, is->adj.points[i].dx, is->adj.points[i].dy));
1641 solve_join(is, i, 1, 0);
1645 map_update_possibles(is->state);
1648 if (didsth) *didsth_r = didsth;
1652 #define CONTINUE_IF_FULL do { \
1653 if (GRID(state, is->x, is->y) & G_MARK) { \
1654 /* island full, don't try fixing it */ \
1658 static int solve_sub(game_state *state, int difficulty, int depth)
1666 /* First island iteration: things we can work out by looking at
1667 * properties of the island as a whole. */
1668 for (i = 0; i < state->n_islands; i++) {
1669 is = &state->islands[i];
1670 if (!solve_island_stage1(is, &didsth)) return 0;
1672 if (didsth) continue;
1673 else if (difficulty < 1) break;
1675 /* Second island iteration: thing we can work out by looking at
1676 * properties of individual island connections. */
1677 for (i = 0; i < state->n_islands; i++) {
1678 is = &state->islands[i];
1680 if (!solve_island_stage2(is, &didsth)) return 0;
1682 if (didsth) continue;
1683 else if (difficulty < 2) break;
1685 /* Third island iteration: things we can only work out by looking
1686 * at groups of islands. */
1687 for (i = 0; i < state->n_islands; i++) {
1688 is = &state->islands[i];
1689 if (!solve_island_stage3(is, &didsth)) return 0;
1691 if (didsth) continue;
1692 else if (difficulty < 3) break;
1694 /* If we can be bothered, write a recursive solver to finish here. */
1697 if (map_check(state)) return 1; /* solved it */
1701 static void solve_for_hint(game_state *state)
1704 solve_sub(state, 10, 0);
1707 static int solve_from_scratch(game_state *state, int difficulty)
1711 map_update_possibles(state);
1712 return solve_sub(state, difficulty, 0);
1715 /* --- New game functions --- */
1717 static game_state *new_state(const game_params *params)
1719 game_state *ret = snew(game_state);
1720 int wh = params->w * params->h, i;
1724 ret->allowloops = params->allowloops;
1725 ret->maxb = params->maxb;
1726 ret->params = *params;
1728 ret->grid = snewn(wh, grid_type);
1729 memset(ret->grid, 0, GRIDSZ(ret));
1731 ret->wha = snewn(wh*N_WH_ARRAYS, char);
1732 memset(ret->wha, 0, wh*N_WH_ARRAYS*sizeof(char));
1734 ret->possv = ret->wha;
1735 ret->possh = ret->wha + wh;
1736 ret->lines = ret->wha + wh*2;
1737 ret->maxv = ret->wha + wh*3;
1738 ret->maxh = ret->wha + wh*4;
1740 memset(ret->maxv, ret->maxb, wh*sizeof(char));
1741 memset(ret->maxh, ret->maxb, wh*sizeof(char));
1743 ret->islands = NULL;
1745 ret->n_islands_alloc = 0;
1747 ret->gridi = snewn(wh, struct island *);
1748 for (i = 0; i < wh; i++) ret->gridi[i] = NULL;
1750 ret->solved = ret->completed = 0;
1752 ret->solver = snew(struct solver_state);
1753 ret->solver->dsf = snew_dsf(wh);
1754 ret->solver->tmpdsf = snewn(wh, int);
1756 ret->solver->refcount = 1;
1761 static game_state *dup_game(const game_state *state)
1763 game_state *ret = snew(game_state);
1764 int wh = state->w*state->h;
1768 ret->allowloops = state->allowloops;
1769 ret->maxb = state->maxb;
1770 ret->params = state->params;
1772 ret->grid = snewn(wh, grid_type);
1773 memcpy(ret->grid, state->grid, GRIDSZ(ret));
1775 ret->wha = snewn(wh*N_WH_ARRAYS, char);
1776 memcpy(ret->wha, state->wha, wh*N_WH_ARRAYS*sizeof(char));
1778 ret->possv = ret->wha;
1779 ret->possh = ret->wha + wh;
1780 ret->lines = ret->wha + wh*2;
1781 ret->maxv = ret->wha + wh*3;
1782 ret->maxh = ret->wha + wh*4;
1784 ret->islands = snewn(state->n_islands, struct island);
1785 memcpy(ret->islands, state->islands, state->n_islands * sizeof(struct island));
1786 ret->n_islands = ret->n_islands_alloc = state->n_islands;
1788 ret->gridi = snewn(wh, struct island *);
1789 fixup_islands_for_realloc(ret);
1791 ret->solved = state->solved;
1792 ret->completed = state->completed;
1794 ret->solver = state->solver;
1795 ret->solver->refcount++;
1800 static void free_game(game_state *state)
1802 if (--state->solver->refcount <= 0) {
1803 sfree(state->solver->dsf);
1804 sfree(state->solver->tmpdsf);
1805 sfree(state->solver);
1808 sfree(state->islands);
1809 sfree(state->gridi);
1817 #define MAX_NEWISLAND_TRIES 50
1818 #define MIN_SENSIBLE_ISLANDS 3
1820 #define ORDER(a,b) do { if (a < b) { int tmp=a; int a=b; int b=tmp; } } while(0)
1822 static char *new_game_desc(const game_params *params, random_state *rs,
1823 char **aux, int interactive)
1825 game_state *tobuild = NULL;
1826 int i, j, wh = params->w * params->h, x, y, dx, dy;
1827 int minx, miny, maxx, maxy, joinx, joiny, newx, newy, diffx, diffy;
1828 int ni_req = max((params->islands * wh) / 100, MIN_SENSIBLE_ISLANDS), ni_curr, ni_bad;
1829 struct island *is, *is2;
1831 unsigned int echeck;
1833 /* pick a first island position randomly. */
1835 if (tobuild) free_game(tobuild);
1836 tobuild = new_state(params);
1838 x = random_upto(rs, params->w);
1839 y = random_upto(rs, params->h);
1840 island_add(tobuild, x, y, 0);
1843 debug(("Created initial island at (%d,%d).\n", x, y));
1845 while (ni_curr < ni_req) {
1846 /* Pick a random island to try and extend from. */
1847 i = random_upto(rs, tobuild->n_islands);
1848 is = &tobuild->islands[i];
1850 /* Pick a random direction to extend in. */
1851 j = random_upto(rs, is->adj.npoints);
1852 dx = is->adj.points[j].x - is->x;
1853 dy = is->adj.points[j].y - is->y;
1855 /* Find out limits of where we could put a new island. */
1857 minx = is->x + 2*dx; miny = is->y + 2*dy; /* closest is 2 units away. */
1858 x = is->x+dx; y = is->y+dy;
1859 if (GRID(tobuild,x,y) & (G_LINEV|G_LINEH)) {
1860 /* already a line next to the island, continue. */
1864 if (x < 0 || x >= params->w || y < 0 || y >= params->h) {
1865 /* got past the edge; put a possible at the island
1867 maxx = x-dx; maxy = y-dy;
1870 if (GRID(tobuild,x,y) & G_ISLAND) {
1871 /* could join up to an existing island... */
1872 joinx = x; joiny = y;
1873 /* ... or make a new one 2 spaces away. */
1874 maxx = x - 2*dx; maxy = y - 2*dy;
1876 } else if (GRID(tobuild,x,y) & (G_LINEV|G_LINEH)) {
1877 /* could make a new one 1 space away from the line. */
1878 maxx = x - dx; maxy = y - dy;
1885 debug(("Island at (%d,%d) with d(%d,%d) has new positions "
1886 "(%d,%d) -> (%d,%d), join (%d,%d).\n",
1887 is->x, is->y, dx, dy, minx, miny, maxx, maxy, joinx, joiny));
1888 /* Now we know where we could either put a new island
1889 * (between min and max), or (if loops are allowed) could join on
1890 * to an existing island (at join). */
1891 if (params->allowloops && joinx != -1 && joiny != -1) {
1892 if (random_upto(rs, 100) < (unsigned long)params->expansion) {
1893 is2 = INDEX(tobuild, gridi, joinx, joiny);
1894 debug(("Joining island at (%d,%d) to (%d,%d).\n",
1895 is->x, is->y, is2->x, is2->y));
1899 diffx = (maxx - minx) * dx;
1900 diffy = (maxy - miny) * dy;
1901 if (diffx < 0 || diffy < 0) goto bad;
1902 if (random_upto(rs,100) < (unsigned long)params->expansion) {
1903 newx = maxx; newy = maxy;
1904 debug(("Creating new island at (%d,%d) (expanded).\n", newx, newy));
1906 newx = minx + random_upto(rs,diffx+1)*dx;
1907 newy = miny + random_upto(rs,diffy+1)*dy;
1908 debug(("Creating new island at (%d,%d).\n", newx, newy));
1910 /* check we're not next to island in the other orthogonal direction. */
1911 if ((INGRID(tobuild,newx+dy,newy+dx) && (GRID(tobuild,newx+dy,newy+dx) & G_ISLAND)) ||
1912 (INGRID(tobuild,newx-dy,newy-dx) && (GRID(tobuild,newx-dy,newy-dx) & G_ISLAND))) {
1913 debug(("New location is adjacent to island, skipping.\n"));
1916 is2 = island_add(tobuild, newx, newy, 0);
1917 /* Must get is again at this point; the array might have
1918 * been realloced by island_add... */
1919 is = &tobuild->islands[i]; /* ...but order will not change. */
1921 ni_curr++; ni_bad = 0;
1923 island_join(is, is2, random_upto(rs, tobuild->maxb)+1, 0);
1924 debug_state(tobuild);
1929 if (ni_bad > MAX_NEWISLAND_TRIES) {
1930 debug(("Unable to create any new islands after %d tries; "
1931 "created %d [%d%%] (instead of %d [%d%%] requested).\n",
1932 MAX_NEWISLAND_TRIES,
1933 ni_curr, ni_curr * 100 / wh,
1934 ni_req, ni_req * 100 / wh));
1941 debug(("Only generated one island (!), retrying.\n"));
1944 /* Check we have at least one island on each extremity of the grid. */
1946 for (x = 0; x < params->w; x++) {
1947 if (INDEX(tobuild, gridi, x, 0)) echeck |= 1;
1948 if (INDEX(tobuild, gridi, x, params->h-1)) echeck |= 2;
1950 for (y = 0; y < params->h; y++) {
1951 if (INDEX(tobuild, gridi, 0, y)) echeck |= 4;
1952 if (INDEX(tobuild, gridi, params->w-1, y)) echeck |= 8;
1955 debug(("Generated grid doesn't fill to sides, retrying.\n"));
1960 map_find_orthogonal(tobuild);
1962 if (params->difficulty > 0) {
1963 if ((ni_curr > MIN_SENSIBLE_ISLANDS) &&
1964 (solve_from_scratch(tobuild, params->difficulty-1) > 0)) {
1965 debug(("Grid is solvable at difficulty %d (too easy); retrying.\n",
1966 params->difficulty-1));
1971 if (solve_from_scratch(tobuild, params->difficulty) == 0) {
1972 debug(("Grid not solvable at difficulty %d, (too hard); retrying.\n",
1973 params->difficulty));
1977 /* ... tobuild is now solved. We rely on this making the diff for aux. */
1978 debug_state(tobuild);
1979 ret = encode_game(tobuild);
1981 game_state *clean = dup_game(tobuild);
1983 map_update_possibles(clean);
1984 *aux = game_state_diff(clean, tobuild);
1992 static char *validate_desc(const game_params *params, const char *desc)
1994 int i, wh = params->w * params->h;
1996 for (i = 0; i < wh; i++) {
1997 if (*desc >= '1' && *desc <= '9')
1999 else if (*desc >= 'a' && *desc <= 'z')
2000 i += *desc - 'a'; /* plus the i++ */
2001 else if (*desc >= 'A' && *desc <= 'G')
2003 else if (*desc == 'V' || *desc == 'W' ||
2004 *desc == 'X' || *desc == 'Y' ||
2005 *desc == 'H' || *desc == 'I' ||
2006 *desc == 'J' || *desc == 'K')
2009 return "Game description shorter than expected";
2011 return "Game description contains unexpected character";
2014 if (*desc || i > wh)
2015 return "Game description longer than expected";
2020 static game_state *new_game_sub(const game_params *params, const char *desc)
2022 game_state *state = new_state(params);
2025 debug(("new_game[_sub]: desc = '%s'.\n", desc));
2027 for (y = 0; y < params->h; y++) {
2028 for (x = 0; x < params->w; x++) {
2034 if (c >= 'a' && c <= 'z')
2044 case '1': case '2': case '3': case '4':
2045 case '5': case '6': case '7': case '8': case '9':
2046 island_add(state, x, y, (c - '0'));
2049 case 'A': case 'B': case 'C': case 'D':
2050 case 'E': case 'F': case 'G':
2051 island_add(state, x, y, (c - 'A') + 10);
2059 assert(!"Malformed desc.");
2064 if (*desc) assert(!"Over-long desc.");
2066 map_find_orthogonal(state);
2067 map_update_possibles(state);
2072 static game_state *new_game(midend *me, const game_params *params,
2075 return new_game_sub(params, desc);
2079 int dragx_src, dragy_src; /* source; -1 means no drag */
2080 int dragx_dst, dragy_dst; /* src's closest orth island. */
2082 int dragging, drag_is_noline, nlines;
2084 int cur_x, cur_y, cur_visible; /* cursor position */
2088 static char *ui_cancel_drag(game_ui *ui)
2090 ui->dragx_src = ui->dragy_src = -1;
2091 ui->dragx_dst = ui->dragy_dst = -1;
2096 static game_ui *new_ui(const game_state *state)
2098 game_ui *ui = snew(game_ui);
2100 ui->cur_x = state->islands[0].x;
2101 ui->cur_y = state->islands[0].y;
2102 ui->cur_visible = 0;
2107 static void free_ui(game_ui *ui)
2112 static char *encode_ui(const game_ui *ui)
2117 static void decode_ui(game_ui *ui, const char *encoding)
2121 static void game_changed_state(game_ui *ui, const game_state *oldstate,
2122 const game_state *newstate)
2126 struct game_drawstate {
2129 unsigned long *grid, *newgrid;
2131 int started, dragging;
2135 * The contents of ds->grid are complicated, because of the circular
2136 * islands which overlap their own grid square into neighbouring
2137 * squares. An island square can contain pieces of the bridges in all
2138 * directions, and conversely a bridge square can be intruded on by
2139 * islands from any direction.
2141 * So we define one group of flags describing what's important about
2142 * an island, and another describing a bridge. Island squares' entries
2143 * in ds->grid contain one of the former and four of the latter; bridge
2144 * squares, four of the former and _two_ of the latter - because a
2145 * horizontal and vertical 'bridge' can cross, when one of them is a
2146 * 'no bridge here' pencil mark.
2148 * Bridge flags need to indicate 0-4 actual bridges (3 bits), a 'no
2149 * bridge' row of crosses, or a grey hint line; that's 7
2150 * possibilities, so 3 bits suffice. But then we also need to vary the
2151 * colours: the bridges can turn COL_WARNING if they're part of a loop
2152 * in no-loops mode, COL_HIGHLIGHT during a victory flash, or
2153 * COL_SELECTED if they're the bridge the user is currently dragging,
2154 * so that's 2 more bits for foreground colour. Also bridges can be
2155 * backed by COL_MARK if they're locked by the user, so that's one
2156 * more bit, making 6 bits per bridge direction.
2158 * Island flags omit the actual island clue (it never changes during
2159 * the game, so doesn't have to be stored in ds->grid to check against
2160 * the previous version), so they just need to include 2 bits for
2161 * foreground colour (an island can be normal, COL_HIGHLIGHT during
2162 * victory, COL_WARNING if its clue is unsatisfiable, or COL_SELECTED
2163 * if it's part of the user's drag) and 2 bits for background (normal,
2164 * COL_MARK for a locked island, COL_CURSOR for the keyboard cursor).
2165 * That's 4 bits per island direction. We must also indicate whether
2166 * no island is present at all (in the case where the island is
2167 * potentially intruding into the side of a line square), which we do
2168 * using the unused 4th value of the background field.
2170 * So an island square needs 4 + 4*6 = 28 bits, while a bridge square
2171 * needs 4*4 + 2*6 = 28 bits too. Both only just fit in 32 bits, which
2172 * is handy, because otherwise we'd have to faff around forever with
2175 /* Flags for line data */
2176 #define DL_COUNTMASK 0x07
2177 #define DL_COUNT_CROSS 0x06
2178 #define DL_COUNT_HINT 0x07
2179 #define DL_COLMASK 0x18
2180 #define DL_COL_NORMAL 0x00
2181 #define DL_COL_WARNING 0x08
2182 #define DL_COL_FLASH 0x10
2183 #define DL_COL_SELECTED 0x18
2184 #define DL_LOCK 0x20
2185 #define DL_MASK 0x3F
2186 /* Flags for island data */
2187 #define DI_COLMASK 0x03
2188 #define DI_COL_NORMAL 0x00
2189 #define DI_COL_FLASH 0x01
2190 #define DI_COL_WARNING 0x02
2191 #define DI_COL_SELECTED 0x03
2192 #define DI_BGMASK 0x0C
2193 #define DI_BG_NO_ISLAND 0x00
2194 #define DI_BG_NORMAL 0x04
2195 #define DI_BG_MARK 0x08
2196 #define DI_BG_CURSOR 0x0C
2197 #define DI_MASK 0x0F
2198 /* Shift counts for the format of a 32-bit word in an island square */
2199 #define D_I_ISLAND_SHIFT 0
2200 #define D_I_LINE_SHIFT_L 4
2201 #define D_I_LINE_SHIFT_R 10
2202 #define D_I_LINE_SHIFT_U 16
2203 #define D_I_LINE_SHIFT_D 24
2204 /* Shift counts for the format of a 32-bit word in a line square */
2205 #define D_L_ISLAND_SHIFT_L 0
2206 #define D_L_ISLAND_SHIFT_R 4
2207 #define D_L_ISLAND_SHIFT_U 8
2208 #define D_L_ISLAND_SHIFT_D 12
2209 #define D_L_LINE_SHIFT_H 16
2210 #define D_L_LINE_SHIFT_V 22
2212 static char *update_drag_dst(const game_state *state, game_ui *ui,
2213 const game_drawstate *ds, int nx, int ny)
2215 int ox, oy, dx, dy, i, currl, maxb;
2217 grid_type gtype, ntype, mtype, curr;
2219 if (ui->dragx_src == -1 || ui->dragy_src == -1) return NULL;
2224 /* work out which of the four directions we're closest to... */
2225 ox = COORD(ui->dragx_src) + TILE_SIZE/2;
2226 oy = COORD(ui->dragy_src) + TILE_SIZE/2;
2228 if (abs(nx-ox) < abs(ny-oy)) {
2230 dy = (ny-oy) < 0 ? -1 : 1;
2231 gtype = G_LINEV; ntype = G_NOLINEV; mtype = G_MARKV;
2232 maxb = INDEX(state, maxv, ui->dragx_src+dx, ui->dragy_src+dy);
2235 dx = (nx-ox) < 0 ? -1 : 1;
2236 gtype = G_LINEH; ntype = G_NOLINEH; mtype = G_MARKH;
2237 maxb = INDEX(state, maxh, ui->dragx_src+dx, ui->dragy_src+dy);
2239 if (ui->drag_is_noline) {
2242 curr = GRID(state, ui->dragx_src+dx, ui->dragy_src+dy);
2243 currl = INDEX(state, lines, ui->dragx_src+dx, ui->dragy_src+dy);
2246 if (currl == maxb) {
2251 ui->nlines = currl + 1;
2259 /* ... and see if there's an island off in that direction. */
2260 is = INDEX(state, gridi, ui->dragx_src, ui->dragy_src);
2261 for (i = 0; i < is->adj.npoints; i++) {
2262 if (is->adj.points[i].off == 0) continue;
2263 curr = GRID(state, is->x+dx, is->y+dy);
2264 if (curr & mtype) continue; /* don't allow changes to marked lines. */
2265 if (ui->drag_is_noline) {
2266 if (curr & gtype) continue; /* no no-line where already a line */
2268 if (POSSIBLES(state, dx, is->x+dx, is->y+dy) == 0) continue; /* no line if !possible. */
2269 if (curr & ntype) continue; /* can't have a bridge where there's a no-line. */
2272 if (is->adj.points[i].dx == dx &&
2273 is->adj.points[i].dy == dy) {
2274 ui->dragx_dst = ISLAND_ORTHX(is,i);
2275 ui->dragy_dst = ISLAND_ORTHY(is,i);
2278 /*debug(("update_drag src (%d,%d) d(%d,%d) dst (%d,%d)\n",
2279 ui->dragx_src, ui->dragy_src, dx, dy,
2280 ui->dragx_dst, ui->dragy_dst));*/
2284 static char *finish_drag(const game_state *state, game_ui *ui)
2288 if (ui->dragx_src == -1 || ui->dragy_src == -1)
2290 if (ui->dragx_dst == -1 || ui->dragy_dst == -1)
2291 return ui_cancel_drag(ui);
2293 if (ui->drag_is_noline) {
2294 sprintf(buf, "N%d,%d,%d,%d",
2295 ui->dragx_src, ui->dragy_src,
2296 ui->dragx_dst, ui->dragy_dst);
2298 sprintf(buf, "L%d,%d,%d,%d,%d",
2299 ui->dragx_src, ui->dragy_src,
2300 ui->dragx_dst, ui->dragy_dst, ui->nlines);
2308 static char *interpret_move(const game_state *state, game_ui *ui,
2309 const game_drawstate *ds,
2310 int x, int y, int button)
2312 int gx = FROMCOORD(x), gy = FROMCOORD(y);
2314 grid_type ggrid = INGRID(state,gx,gy) ? GRID(state,gx,gy) : 0;
2315 int shift = button & MOD_SHFT, control = button & MOD_CTRL;
2316 button &= ~MOD_MASK;
2318 if (button == LEFT_BUTTON || button == RIGHT_BUTTON) {
2319 if (!INGRID(state, gx, gy)) return NULL;
2320 ui->cur_visible = 0;
2321 if (ggrid & G_ISLAND) {
2326 return ui_cancel_drag(ui);
2327 } else if (button == LEFT_DRAG || button == RIGHT_DRAG) {
2328 if (INGRID(state, ui->dragx_src, ui->dragy_src)
2329 && (gx != ui->dragx_src || gy != ui->dragy_src)
2330 && !(GRID(state,ui->dragx_src,ui->dragy_src) & G_MARK)) {
2332 ui->drag_is_noline = (button == RIGHT_DRAG) ? 1 : 0;
2333 return update_drag_dst(state, ui, ds, x, y);
2335 /* cancel a drag when we go back to the starting point */
2340 } else if (button == LEFT_RELEASE || button == RIGHT_RELEASE) {
2342 return finish_drag(state, ui);
2344 if (!INGRID(state, ui->dragx_src, ui->dragy_src)
2345 || gx != ui->dragx_src || gy != ui->dragy_src) {
2346 return ui_cancel_drag(ui);
2349 if (!INGRID(state, gx, gy)) return NULL;
2350 if (!(GRID(state, gx, gy) & G_ISLAND)) return NULL;
2351 sprintf(buf, "M%d,%d", gx, gy);
2354 } else if (button == 'h' || button == 'H') {
2355 game_state *solved = dup_game(state);
2356 solve_for_hint(solved);
2357 ret = game_state_diff(state, solved);
2360 } else if (IS_CURSOR_MOVE(button)) {
2361 ui->cur_visible = 1;
2362 if (control || shift) {
2363 ui->dragx_src = ui->cur_x;
2364 ui->dragy_src = ui->cur_y;
2365 ui->dragging = TRUE;
2366 ui->drag_is_noline = !control;
2369 int nx = ui->cur_x, ny = ui->cur_y;
2371 move_cursor(button, &nx, &ny, state->w, state->h, 0);
2372 if (nx == ui->cur_x && ny == ui->cur_y)
2374 update_drag_dst(state, ui, ds,
2375 COORD(nx)+TILE_SIZE/2,
2376 COORD(ny)+TILE_SIZE/2);
2377 return finish_drag(state, ui);
2379 int dx = (button == CURSOR_RIGHT) ? +1 : (button == CURSOR_LEFT) ? -1 : 0;
2380 int dy = (button == CURSOR_DOWN) ? +1 : (button == CURSOR_UP) ? -1 : 0;
2381 int dorthx = 1 - abs(dx), dorthy = 1 - abs(dy);
2382 int dir, orth, nx = x, ny = y;
2384 /* 'orthorder' is a tweak to ensure that if you press RIGHT and
2385 * happen to move upwards, when you press LEFT you then tend
2386 * downwards (rather than upwards again). */
2387 int orthorder = (button == CURSOR_LEFT || button == CURSOR_UP) ? 1 : -1;
2389 /* This attempts to find an island in the direction you're
2390 * asking for, broadly speaking. If you ask to go right, for
2391 * example, it'll look for islands to the right and slightly
2392 * above or below your current horiz. position, allowing
2393 * further above/below the further away it searches. */
2395 assert(GRID(state, ui->cur_x, ui->cur_y) & G_ISLAND);
2396 /* currently this is depth-first (so orthogonally-adjacent
2397 * islands across the other side of the grid will be moved to
2398 * before closer islands slightly offset). Swap the order of
2399 * these two loops to change to breadth-first search. */
2400 for (orth = 0; ; orth++) {
2402 for (dir = 1; ; dir++) {
2405 if (orth > dir) continue; /* only search in cone outwards. */
2407 nx = ui->cur_x + dir*dx + orth*dorthx*orthorder;
2408 ny = ui->cur_y + dir*dy + orth*dorthy*orthorder;
2409 if (INGRID(state, nx, ny)) {
2410 dingrid = oingrid = 1;
2411 if (GRID(state, nx, ny) & G_ISLAND) goto found;
2414 nx = ui->cur_x + dir*dx - orth*dorthx*orthorder;
2415 ny = ui->cur_y + dir*dy - orth*dorthy*orthorder;
2416 if (INGRID(state, nx, ny)) {
2417 dingrid = oingrid = 1;
2418 if (GRID(state, nx, ny) & G_ISLAND) goto found;
2421 if (!dingrid) break;
2423 if (!oingrid) return UI_UPDATE;
2432 } else if (IS_CURSOR_SELECT(button)) {
2433 if (!ui->cur_visible) {
2434 ui->cur_visible = 1;
2437 if (ui->dragging || button == CURSOR_SELECT2) {
2439 if (ui->dragx_dst == -1 && ui->dragy_dst == -1) {
2440 sprintf(buf, "M%d,%d", ui->cur_x, ui->cur_y);
2445 grid_type v = GRID(state, ui->cur_x, ui->cur_y);
2448 ui->dragx_src = ui->cur_x;
2449 ui->dragy_src = ui->cur_y;
2450 ui->dragx_dst = ui->dragy_dst = -1;
2451 ui->drag_is_noline = (button == CURSOR_SELECT2) ? 1 : 0;
2455 } else if ((button >= '0' && button <= '9') ||
2456 (button >= 'a' && button <= 'f') ||
2457 (button >= 'A' && button <= 'F')) {
2458 /* jump to island with .count == number closest to cur_{x,y} */
2459 int best_x = -1, best_y = -1, best_sqdist = -1, number = -1, i;
2461 if (button >= '0' && button <= '9')
2462 number = (button == '0' ? 16 : button - '0');
2463 else if (button >= 'a' && button <= 'f')
2464 number = 10 + button - 'a';
2465 else if (button >= 'A' && button <= 'F')
2466 number = 10 + button - 'A';
2468 if (!ui->cur_visible) {
2469 ui->cur_visible = 1;
2473 for (i = 0; i < state->n_islands; ++i) {
2474 int x = state->islands[i].x, y = state->islands[i].y;
2475 int dx = x - ui->cur_x, dy = y - ui->cur_y;
2476 int sqdist = dx*dx + dy*dy;
2478 if (state->islands[i].count != number)
2480 if (x == ui->cur_x && y == ui->cur_y)
2483 /* new_game() reads the islands in row-major order, so by
2484 * breaking ties in favor of `first in state->islands' we
2485 * also break ties by `lexicographically smallest (y, x)'.
2486 * Thus, there's a stable pattern to how ties are broken
2487 * which the user can learn and use to navigate faster. */
2488 if (best_sqdist == -1 || sqdist < best_sqdist) {
2491 best_sqdist = sqdist;
2494 if (best_x != -1 && best_y != -1) {
2500 } else if (button == 'g' || button == 'G') {
2501 ui->show_hints = 1 - ui->show_hints;
2508 static game_state *execute_move(const game_state *state, const char *move)
2510 game_state *ret = dup_game(state);
2511 int x1, y1, x2, y2, nl, n;
2512 struct island *is1, *is2;
2515 debug(("execute_move: %s\n", move));
2517 if (!*move) goto badmove;
2523 } else if (c == 'L') {
2524 if (sscanf(move, "%d,%d,%d,%d,%d%n",
2525 &x1, &y1, &x2, &y2, &nl, &n) != 5)
2527 if (!INGRID(ret, x1, y1) || !INGRID(ret, x2, y2))
2529 is1 = INDEX(ret, gridi, x1, y1);
2530 is2 = INDEX(ret, gridi, x2, y2);
2531 if (!is1 || !is2) goto badmove;
2532 if (nl < 0 || nl > state->maxb) goto badmove;
2533 island_join(is1, is2, nl, 0);
2534 } else if (c == 'N') {
2535 if (sscanf(move, "%d,%d,%d,%d%n",
2536 &x1, &y1, &x2, &y2, &n) != 4)
2538 if (!INGRID(ret, x1, y1) || !INGRID(ret, x2, y2))
2540 is1 = INDEX(ret, gridi, x1, y1);
2541 is2 = INDEX(ret, gridi, x2, y2);
2542 if (!is1 || !is2) goto badmove;
2543 island_join(is1, is2, -1, 0);
2544 } else if (c == 'M') {
2545 if (sscanf(move, "%d,%d%n",
2548 if (!INGRID(ret, x1, y1))
2550 is1 = INDEX(ret, gridi, x1, y1);
2551 if (!is1) goto badmove;
2552 island_togglemark(is1);
2559 else if (*move) goto badmove;
2562 map_update_possibles(ret);
2563 if (map_check(ret)) {
2564 debug(("Game completed.\n"));
2570 debug(("%s: unrecognised move.\n", move));
2575 static char *solve_game(const game_state *state, const game_state *currstate,
2576 const char *aux, char **error)
2582 debug(("solve_game: aux = %s\n", aux));
2583 solved = execute_move(state, aux);
2585 *error = "Generated aux string is not a valid move (!).";
2589 solved = dup_game(state);
2590 /* solve with max strength... */
2591 if (solve_from_scratch(solved, 10) == 0) {
2593 *error = "Game does not have a (non-recursive) solution.";
2597 ret = game_state_diff(currstate, solved);
2599 debug(("solve_game: ret = %s\n", ret));
2603 /* ----------------------------------------------------------------------
2607 static void game_compute_size(const game_params *params, int tilesize,
2610 /* Ick: fake up `ds->tilesize' for macro expansion purposes */
2611 struct { int tilesize; } ads, *ds = &ads;
2612 ads.tilesize = tilesize;
2614 *x = TILE_SIZE * params->w + 2 * BORDER;
2615 *y = TILE_SIZE * params->h + 2 * BORDER;
2618 static void game_set_size(drawing *dr, game_drawstate *ds,
2619 const game_params *params, int tilesize)
2621 ds->tilesize = tilesize;
2624 static float *game_colours(frontend *fe, int *ncolours)
2626 float *ret = snewn(3 * NCOLOURS, float);
2629 game_mkhighlight(fe, ret, COL_BACKGROUND, COL_HIGHLIGHT, COL_LOWLIGHT);
2631 for (i = 0; i < 3; i++) {
2632 ret[COL_FOREGROUND * 3 + i] = 0.0F;
2633 ret[COL_HINT * 3 + i] = ret[COL_LOWLIGHT * 3 + i];
2634 ret[COL_GRID * 3 + i] =
2635 (ret[COL_HINT * 3 + i] + ret[COL_BACKGROUND * 3 + i]) * 0.5F;
2636 ret[COL_MARK * 3 + i] = ret[COL_HIGHLIGHT * 3 + i];
2638 ret[COL_WARNING * 3 + 0] = 1.0F;
2639 ret[COL_WARNING * 3 + 1] = 0.25F;
2640 ret[COL_WARNING * 3 + 2] = 0.25F;
2642 ret[COL_SELECTED * 3 + 0] = 0.25F;
2643 ret[COL_SELECTED * 3 + 1] = 1.00F;
2644 ret[COL_SELECTED * 3 + 2] = 0.25F;
2646 ret[COL_CURSOR * 3 + 0] = min(ret[COL_BACKGROUND * 3 + 0] * 1.4F, 1.0F);
2647 ret[COL_CURSOR * 3 + 1] = ret[COL_BACKGROUND * 3 + 1] * 0.8F;
2648 ret[COL_CURSOR * 3 + 2] = ret[COL_BACKGROUND * 3 + 2] * 0.8F;
2650 *ncolours = NCOLOURS;
2654 static game_drawstate *game_new_drawstate(drawing *dr, const game_state *state)
2656 struct game_drawstate *ds = snew(struct game_drawstate);
2657 int wh = state->w*state->h;
2665 ds->grid = snewn(wh, unsigned long);
2666 for (i = 0; i < wh; i++)
2668 ds->newgrid = snewn(wh, unsigned long);
2669 ds->lv = snewn(wh, int);
2670 ds->lh = snewn(wh, int);
2671 memset(ds->lv, 0, wh*sizeof(int));
2672 memset(ds->lh, 0, wh*sizeof(int));
2677 static void game_free_drawstate(drawing *dr, game_drawstate *ds)
2686 #define LINE_WIDTH (TILE_SIZE/8)
2687 #define TS8(x) (((x)*TILE_SIZE)/8)
2689 #define OFFSET(thing) ((TILE_SIZE/2) - ((thing)/2))
2691 static int between_island(const game_state *state, int sx, int sy,
2694 int x = sx - dx, y = sy - dy;
2696 while (INGRID(state, x, y)) {
2697 if (GRID(state, x, y) & G_ISLAND) goto found;
2702 x = sx + dx, y = sy + dy;
2703 while (INGRID(state, x, y)) {
2704 if (GRID(state, x, y) & G_ISLAND) return 1;
2710 static void lines_lvlh(const game_state *state, const game_ui *ui,
2711 int x, int y, grid_type v, int *lv_r, int *lh_r)
2715 if (v & G_LINEV) lv = INDEX(state,lines,x,y);
2716 if (v & G_LINEH) lh = INDEX(state,lines,x,y);
2718 if (ui->show_hints) {
2719 if (between_island(state, x, y, 0, 1) && !lv) lv = 1;
2720 if (between_island(state, x, y, 1, 0) && !lh) lh = 1;
2722 /*debug(("lvlh: (%d,%d) v 0x%x lv %d lh %d.\n", x, y, v, lv, lh));*/
2723 *lv_r = lv; *lh_r = lh;
2726 static void draw_cross(drawing *dr, game_drawstate *ds,
2727 int ox, int oy, int col)
2730 draw_line(dr, ox, oy, ox+off, oy+off, col);
2731 draw_line(dr, ox+off, oy, ox, oy+off, col);
2734 static void draw_general_line(drawing *dr, game_drawstate *ds,
2735 int ox, int oy, int fx, int fy, int ax, int ay,
2736 int len, unsigned long ldata, int which)
2739 * Draw one direction of lines in a square. To permit the same
2740 * code to handle horizontal and vertical lines, fx,fy are the
2741 * 'forward' direction (along the lines) and ax,ay are the
2742 * 'across' direction.
2744 * We draw the white background for a locked bridge if (which &
2745 * 1), and draw the bridges themselves if (which & 2). This
2746 * permits us to get two overlapping locked bridges right without
2747 * one of them erasing part of the other.
2751 fg = ((ldata & DL_COUNTMASK) == DL_COUNT_HINT ? COL_HINT :
2752 (ldata & DL_COLMASK) == DL_COL_SELECTED ? COL_SELECTED :
2753 (ldata & DL_COLMASK) == DL_COL_FLASH ? COL_HIGHLIGHT :
2754 (ldata & DL_COLMASK) == DL_COL_WARNING ? COL_WARNING :
2757 if ((ldata & DL_COUNTMASK) == DL_COUNT_CROSS) {
2759 ox + TS8(1)*fx + TS8(3)*ax,
2760 oy + TS8(1)*fy + TS8(3)*ay, fg);
2762 ox + TS8(5)*fx + TS8(3)*ax,
2763 oy + TS8(5)*fy + TS8(3)*ay, fg);
2764 } else if ((ldata & DL_COUNTMASK) != 0) {
2765 int lh, lw, gw, bw, i, loff;
2767 lh = (ldata & DL_COUNTMASK);
2768 if (lh == DL_COUNT_HINT)
2771 lw = gw = LINE_WIDTH;
2772 while ((bw = lw * lh + gw * (lh+1)) > TILE_SIZE)
2778 if ((ldata & DL_LOCK) && fg != COL_HINT)
2779 draw_rect(dr, ox + loff*ax, oy + loff*ay,
2780 len*fx+bw*ax, len*fy+bw*ay, COL_MARK);
2783 for (i = 0; i < lh; i++, loff += lw + gw)
2784 draw_rect(dr, ox + (loff+gw)*ax, oy + (loff+gw)*ay,
2785 len*fx+lw*ax, len*fy+lw*ay, fg);
2790 static void draw_hline(drawing *dr, game_drawstate *ds,
2791 int ox, int oy, int w, unsigned long vdata, int which)
2793 draw_general_line(dr, ds, ox, oy, 1, 0, 0, 1, w, vdata, which);
2796 static void draw_vline(drawing *dr, game_drawstate *ds,
2797 int ox, int oy, int h, unsigned long vdata, int which)
2799 draw_general_line(dr, ds, ox, oy, 0, 1, 1, 0, h, vdata, which);
2802 #define ISLAND_RADIUS ((TILE_SIZE*12)/20)
2803 #define ISLAND_NUMSIZE(clue) \
2804 (((clue) < 10) ? (TILE_SIZE*7)/10 : (TILE_SIZE*5)/10)
2806 static void draw_island(drawing *dr, game_drawstate *ds,
2807 int ox, int oy, int clue, unsigned long idata)
2809 int half, orad, irad, fg, bg;
2811 if ((idata & DI_BGMASK) == DI_BG_NO_ISLAND)
2815 orad = ISLAND_RADIUS;
2816 irad = orad - LINE_WIDTH;
2817 fg = ((idata & DI_COLMASK) == DI_COL_SELECTED ? COL_SELECTED :
2818 (idata & DI_COLMASK) == DI_COL_WARNING ? COL_WARNING :
2819 (idata & DI_COLMASK) == DI_COL_FLASH ? COL_HIGHLIGHT :
2821 bg = ((idata & DI_BGMASK) == DI_BG_CURSOR ? COL_CURSOR :
2822 (idata & DI_BGMASK) == DI_BG_MARK ? COL_MARK :
2825 /* draw a thick circle */
2826 draw_circle(dr, ox+half, oy+half, orad, fg, fg);
2827 draw_circle(dr, ox+half, oy+half, irad, bg, bg);
2831 int textcolour = (fg == COL_SELECTED ? COL_FOREGROUND : fg);
2832 sprintf(str, "%d", clue);
2833 draw_text(dr, ox+half, oy+half, FONT_VARIABLE, ISLAND_NUMSIZE(clue),
2834 ALIGN_VCENTRE | ALIGN_HCENTRE, textcolour, str);
2838 static void draw_island_tile(drawing *dr, game_drawstate *ds,
2839 int x, int y, int clue, unsigned long data)
2841 int ox = COORD(x), oy = COORD(y);
2844 clip(dr, ox, oy, TILE_SIZE, TILE_SIZE);
2845 draw_rect(dr, ox, oy, TILE_SIZE, TILE_SIZE, COL_BACKGROUND);
2848 * Because of the possibility of incoming bridges just about
2849 * meeting at one corner, we must split the line-drawing into
2850 * background and foreground segments.
2852 for (which = 1; which <= 2; which <<= 1) {
2853 draw_hline(dr, ds, ox, oy, TILE_SIZE/2,
2854 (data >> D_I_LINE_SHIFT_L) & DL_MASK, which);
2855 draw_hline(dr, ds, ox + TILE_SIZE - TILE_SIZE/2, oy, TILE_SIZE/2,
2856 (data >> D_I_LINE_SHIFT_R) & DL_MASK, which);
2857 draw_vline(dr, ds, ox, oy, TILE_SIZE/2,
2858 (data >> D_I_LINE_SHIFT_U) & DL_MASK, which);
2859 draw_vline(dr, ds, ox, oy + TILE_SIZE - TILE_SIZE/2, TILE_SIZE/2,
2860 (data >> D_I_LINE_SHIFT_D) & DL_MASK, which);
2862 draw_island(dr, ds, ox, oy, clue, (data >> D_I_ISLAND_SHIFT) & DI_MASK);
2865 draw_update(dr, ox, oy, TILE_SIZE, TILE_SIZE);
2868 static void draw_line_tile(drawing *dr, game_drawstate *ds,
2869 int x, int y, unsigned long data)
2871 int ox = COORD(x), oy = COORD(y);
2872 unsigned long hdata, vdata;
2874 clip(dr, ox, oy, TILE_SIZE, TILE_SIZE);
2875 draw_rect(dr, ox, oy, TILE_SIZE, TILE_SIZE, COL_BACKGROUND);
2878 * We have to think about which of the horizontal and vertical
2879 * line to draw first, if both exist.
2881 * The rule is that hint lines are drawn at the bottom, then
2882 * NOLINE crosses, then actual bridges. The enumeration in the
2883 * DL_COUNTMASK field is set up so that this drops out of a
2884 * straight comparison between the two.
2886 * Since lines crossing in this type of square cannot both be
2887 * actual bridges, there's no need to pass a nontrivial 'which'
2888 * parameter to draw_[hv]line.
2890 hdata = (data >> D_L_LINE_SHIFT_H) & DL_MASK;
2891 vdata = (data >> D_L_LINE_SHIFT_V) & DL_MASK;
2892 if ((hdata & DL_COUNTMASK) > (vdata & DL_COUNTMASK)) {
2893 draw_hline(dr, ds, ox, oy, TILE_SIZE, hdata, 3);
2894 draw_vline(dr, ds, ox, oy, TILE_SIZE, vdata, 3);
2896 draw_vline(dr, ds, ox, oy, TILE_SIZE, vdata, 3);
2897 draw_hline(dr, ds, ox, oy, TILE_SIZE, hdata, 3);
2901 * The islands drawn at the edges of a line tile don't need clue
2904 draw_island(dr, ds, ox - TILE_SIZE, oy, -1,
2905 (data >> D_L_ISLAND_SHIFT_L) & DI_MASK);
2906 draw_island(dr, ds, ox + TILE_SIZE, oy, -1,
2907 (data >> D_L_ISLAND_SHIFT_R) & DI_MASK);
2908 draw_island(dr, ds, ox, oy - TILE_SIZE, -1,
2909 (data >> D_L_ISLAND_SHIFT_U) & DI_MASK);
2910 draw_island(dr, ds, ox, oy + TILE_SIZE, -1,
2911 (data >> D_L_ISLAND_SHIFT_D) & DI_MASK);
2914 draw_update(dr, ox, oy, TILE_SIZE, TILE_SIZE);
2917 static void draw_edge_tile(drawing *dr, game_drawstate *ds,
2918 int x, int y, int dx, int dy, unsigned long data)
2920 int ox = COORD(x), oy = COORD(y);
2921 int cx = ox, cy = oy, cw = TILE_SIZE, ch = TILE_SIZE;
2932 clip(dr, cx, cy, cw, ch);
2933 draw_rect(dr, cx, cy, cw, ch, COL_BACKGROUND);
2935 draw_island(dr, ds, ox + TILE_SIZE*dx, oy + TILE_SIZE*dy, -1,
2936 (data >> D_I_ISLAND_SHIFT) & DI_MASK);
2939 draw_update(dr, cx, cy, cw, ch);
2942 static void game_redraw(drawing *dr, game_drawstate *ds,
2943 const game_state *oldstate, const game_state *state,
2944 int dir, const game_ui *ui,
2945 float animtime, float flashtime)
2948 grid_type v, flash = 0;
2949 struct island *is, *is_drag_src = NULL, *is_drag_dst = NULL;
2952 int f = (int)(flashtime * 5 / FLASH_TIME);
2953 if (f == 1 || f == 3) flash = TRUE;
2956 /* Clear screen, if required. */
2959 TILE_SIZE * ds->w + 2 * BORDER,
2960 TILE_SIZE * ds->h + 2 * BORDER, COL_BACKGROUND);
2962 draw_rect_outline(dr,
2963 COORD(0)-1, COORD(0)-1,
2964 TILE_SIZE * ds->w + 2, TILE_SIZE * ds->h + 2,
2967 draw_update(dr, 0, 0,
2968 TILE_SIZE * ds->w + 2 * BORDER,
2969 TILE_SIZE * ds->h + 2 * BORDER);
2973 if (ui->dragx_src != -1 && ui->dragy_src != -1) {
2975 is_drag_src = INDEX(state, gridi, ui->dragx_src, ui->dragy_src);
2976 assert(is_drag_src);
2977 if (ui->dragx_dst != -1 && ui->dragy_dst != -1) {
2978 is_drag_dst = INDEX(state, gridi, ui->dragx_dst, ui->dragy_dst);
2979 assert(is_drag_dst);
2985 * Set up ds->newgrid with the current grid contents.
2987 for (x = 0; x < ds->w; x++)
2988 for (y = 0; y < ds->h; y++)
2989 INDEX(ds,newgrid,x,y) = 0;
2991 for (x = 0; x < ds->w; x++) {
2992 for (y = 0; y < ds->h; y++) {
2993 v = GRID(state, x, y);
2997 * An island square. Compute the drawing data for the
2998 * island, and put it in this square and surrounding
3001 unsigned long idata = 0;
3003 is = INDEX(state, gridi, x, y);
3006 idata |= DI_COL_FLASH;
3007 if (is_drag_src && (is == is_drag_src ||
3008 (is_drag_dst && is == is_drag_dst)))
3009 idata |= DI_COL_SELECTED;
3010 else if (island_impossible(is, v & G_MARK) || (v & G_WARN))
3011 idata |= DI_COL_WARNING;
3013 idata |= DI_COL_NORMAL;
3015 if (ui->cur_visible &&
3016 ui->cur_x == is->x && ui->cur_y == is->y)
3017 idata |= DI_BG_CURSOR;
3018 else if (v & G_MARK)
3019 idata |= DI_BG_MARK;
3021 idata |= DI_BG_NORMAL;
3023 INDEX(ds,newgrid,x,y) |= idata << D_I_ISLAND_SHIFT;
3024 if (x > 0 && !(GRID(state,x-1,y) & G_ISLAND))
3025 INDEX(ds,newgrid,x-1,y) |= idata << D_L_ISLAND_SHIFT_R;
3026 if (x+1 < state->w && !(GRID(state,x+1,y) & G_ISLAND))
3027 INDEX(ds,newgrid,x+1,y) |= idata << D_L_ISLAND_SHIFT_L;
3028 if (y > 0 && !(GRID(state,x,y-1) & G_ISLAND))
3029 INDEX(ds,newgrid,x,y-1) |= idata << D_L_ISLAND_SHIFT_D;
3030 if (y+1 < state->h && !(GRID(state,x,y+1) & G_ISLAND))
3031 INDEX(ds,newgrid,x,y+1) |= idata << D_L_ISLAND_SHIFT_U;
3033 unsigned long hdata, vdata;
3034 int selh = FALSE, selv = FALSE;
3037 * A line (non-island) square. Compute the drawing
3038 * data for any horizontal and vertical lines in the
3039 * square, and put them in this square's entry and
3040 * optionally those for neighbouring islands too.
3044 WITHIN(x,is_drag_src->x, is_drag_dst->x) &&
3045 WITHIN(y,is_drag_src->y, is_drag_dst->y)) {
3046 if (is_drag_src->x != is_drag_dst->x)
3051 lines_lvlh(state, ui, x, y, v, &lv, &lh);
3053 hdata = (v & G_NOLINEH ? DL_COUNT_CROSS :
3056 between_island(state,x,y,1,0)) ? DL_COUNT_HINT : 0);
3057 vdata = (v & G_NOLINEV ? DL_COUNT_CROSS :
3060 between_island(state,x,y,0,1)) ? DL_COUNT_HINT : 0);
3062 hdata |= (flash ? DL_COL_FLASH :
3063 v & G_WARN ? DL_COL_WARNING :
3064 selh ? DL_COL_SELECTED :
3066 vdata |= (flash ? DL_COL_FLASH :
3067 v & G_WARN ? DL_COL_WARNING :
3068 selv ? DL_COL_SELECTED :
3076 INDEX(ds,newgrid,x,y) |= hdata << D_L_LINE_SHIFT_H;
3077 INDEX(ds,newgrid,x,y) |= vdata << D_L_LINE_SHIFT_V;
3078 if (x > 0 && (GRID(state,x-1,y) & G_ISLAND))
3079 INDEX(ds,newgrid,x-1,y) |= hdata << D_I_LINE_SHIFT_R;
3080 if (x+1 < state->w && (GRID(state,x+1,y) & G_ISLAND))
3081 INDEX(ds,newgrid,x+1,y) |= hdata << D_I_LINE_SHIFT_L;
3082 if (y > 0 && (GRID(state,x,y-1) & G_ISLAND))
3083 INDEX(ds,newgrid,x,y-1) |= vdata << D_I_LINE_SHIFT_D;
3084 if (y+1 < state->h && (GRID(state,x,y+1) & G_ISLAND))
3085 INDEX(ds,newgrid,x,y+1) |= vdata << D_I_LINE_SHIFT_U;
3091 * Now go through and draw any changed grid square.
3093 for (x = 0; x < ds->w; x++) {
3094 for (y = 0; y < ds->h; y++) {
3095 unsigned long newval = INDEX(ds,newgrid,x,y);
3096 if (INDEX(ds,grid,x,y) != newval) {
3097 v = GRID(state, x, y);
3099 is = INDEX(state, gridi, x, y);
3100 draw_island_tile(dr, ds, x, y, is->count, newval);
3103 * If this tile is right at the edge of the grid,
3104 * we must also draw the part of the island that
3105 * goes completely out of bounds. We don't bother
3106 * keeping separate entries in ds->newgrid for
3107 * these tiles; it's easier just to redraw them
3108 * iff we redraw their parent island tile.
3111 draw_edge_tile(dr, ds, x-1, y, +1, 0, newval);
3113 draw_edge_tile(dr, ds, x, y-1, 0, +1, newval);
3114 if (x == state->w-1)
3115 draw_edge_tile(dr, ds, x+1, y, -1, 0, newval);
3116 if (y == state->h-1)
3117 draw_edge_tile(dr, ds, x, y+1, 0, -1, newval);
3119 draw_line_tile(dr, ds, x, y, newval);
3121 INDEX(ds,grid,x,y) = newval;
3127 static float game_anim_length(const game_state *oldstate,
3128 const game_state *newstate, int dir, game_ui *ui)
3133 static float game_flash_length(const game_state *oldstate,
3134 const game_state *newstate, int dir, game_ui *ui)
3136 if (!oldstate->completed && newstate->completed &&
3137 !oldstate->solved && !newstate->solved)
3143 static int game_status(const game_state *state)
3145 return state->completed ? +1 : 0;
3148 static int game_timing_state(const game_state *state, game_ui *ui)
3153 static void game_print_size(const game_params *params, float *x, float *y)
3157 /* 10mm squares by default. */
3158 game_compute_size(params, 1000, &pw, &ph);
3163 static void game_print(drawing *dr, const game_state *state, int ts)
3165 int ink = print_mono_colour(dr, 0);
3166 int paper = print_mono_colour(dr, 1);
3167 int x, y, cx, cy, i, nl;
3171 /* Ick: fake up `ds->tilesize' for macro expansion purposes */
3172 game_drawstate ads, *ds = &ads;
3175 /* I don't think this wants a border. */
3178 loff = ts / (8 * sqrt((state->params.maxb - 1)));
3179 print_line_width(dr, ts / 12);
3180 for (x = 0; x < state->w; x++) {
3181 for (y = 0; y < state->h; y++) {
3182 cx = COORD(x); cy = COORD(y);
3183 grid = GRID(state,x,y);
3184 nl = INDEX(state,lines,x,y);
3186 if (grid & G_ISLAND) continue;
3187 if (grid & G_LINEV) {
3188 for (i = 0; i < nl; i++)
3189 draw_line(dr, cx+ts/2+(2*i-nl+1)*loff, cy,
3190 cx+ts/2+(2*i-nl+1)*loff, cy+ts, ink);
3192 if (grid & G_LINEH) {
3193 for (i = 0; i < nl; i++)
3194 draw_line(dr, cx, cy+ts/2+(2*i-nl+1)*loff,
3195 cx+ts, cy+ts/2+(2*i-nl+1)*loff, ink);
3201 for (i = 0; i < state->n_islands; i++) {
3203 struct island *is = &state->islands[i];
3204 grid = GRID(state, is->x, is->y);
3205 cx = COORD(is->x) + ts/2;
3206 cy = COORD(is->y) + ts/2;
3208 draw_circle(dr, cx, cy, ISLAND_RADIUS, paper, ink);
3210 sprintf(str, "%d", is->count);
3211 draw_text(dr, cx, cy, FONT_VARIABLE, ISLAND_NUMSIZE(is->count),
3212 ALIGN_VCENTRE | ALIGN_HCENTRE, ink, str);
3217 #define thegame bridges
3220 const struct game thegame = {
3221 "Bridges", "games.bridges", "bridges",
3223 game_fetch_preset, NULL,
3228 TRUE, game_configure, custom_params,
3236 TRUE, game_can_format_as_text_now, game_text_format,
3244 PREFERRED_TILE_SIZE, game_compute_size, game_set_size,
3247 game_free_drawstate,
3252 TRUE, FALSE, game_print_size, game_print,
3253 FALSE, /* wants_statusbar */
3254 FALSE, game_timing_state,
3255 REQUIRE_RBUTTON, /* flags */
3258 /* vim: set shiftwidth=4 tabstop=8: */