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].sval
= dupstr(buf
);
748 ret
[1].name
= "Height";
749 ret
[1].type
= C_STRING
;
750 sprintf(buf
, "%d", params
->h
);
751 ret
[1].sval
= dupstr(buf
);
754 ret
[2].name
= "Difficulty";
755 ret
[2].type
= C_CHOICES
;
756 ret
[2].sval
= ":Easy:Medium:Hard";
757 ret
[2].ival
= params
->difficulty
;
759 ret
[3].name
= "Allow loops";
760 ret
[3].type
= C_BOOLEAN
;
762 ret
[3].ival
= params
->allowloops
;
764 ret
[4].name
= "Max. bridges per direction";
765 ret
[4].type
= C_CHOICES
;
766 ret
[4].sval
= ":1:2:3:4"; /* keep up-to-date with MAX_BRIDGES */
767 ret
[4].ival
= params
->maxb
- 1;
769 ret
[5].name
= "%age of island squares";
770 ret
[5].type
= C_CHOICES
;
771 ret
[5].sval
= ":5%:10%:15%:20%:25%:30%";
772 ret
[5].ival
= (params
->islands
/ 5)-1;
774 ret
[6].name
= "Expansion factor (%age)";
775 ret
[6].type
= C_CHOICES
;
776 ret
[6].sval
= ":0%:10%:20%:30%:40%:50%:60%:70%:80%:90%:100%";
777 ret
[6].ival
= params
->expansion
/ 10;
787 static game_params
*custom_params(const config_item
*cfg
)
789 game_params
*ret
= snew(game_params
);
791 ret
->w
= atoi(cfg
[0].sval
);
792 ret
->h
= atoi(cfg
[1].sval
);
793 ret
->difficulty
= cfg
[2].ival
;
794 ret
->allowloops
= cfg
[3].ival
;
795 ret
->maxb
= cfg
[4].ival
+ 1;
796 ret
->islands
= (cfg
[5].ival
+ 1) * 5;
797 ret
->expansion
= cfg
[6].ival
* 10;
802 static char *validate_params(const game_params
*params
, int full
)
804 if (params
->w
< 3 || params
->h
< 3)
805 return "Width and height must be at least 3";
806 if (params
->maxb
< 1 || params
->maxb
> MAX_BRIDGES
)
807 return "Too many bridges.";
809 if (params
->islands
<= 0 || params
->islands
> 30)
810 return "%age of island squares must be between 1% and 30%";
811 if (params
->expansion
< 0 || params
->expansion
> 100)
812 return "Expansion factor must be between 0 and 100";
817 /* --- Game encoding and differences --- */
819 static char *encode_game(game_state
*state
)
822 int wh
= state
->w
*state
->h
, run
, x
, y
;
825 ret
= snewn(wh
+ 1, char);
828 for (y
= 0; y
< state
->h
; y
++) {
829 for (x
= 0; x
< state
->w
; x
++) {
830 is
= INDEX(state
, gridi
, x
, y
);
833 *p
++ = ('a'-1) + run
;
837 *p
++ = '0' + is
->count
;
839 *p
++ = 'A' + (is
->count
- 10);
842 *p
++ = ('a'-1) + run
;
850 *p
++ = ('a'-1) + run
;
854 assert(p
- ret
<= wh
);
859 static char *game_state_diff(const game_state
*src
, const game_state
*dest
)
861 int movesize
= 256, movelen
= 0;
862 char *move
= snewn(movesize
, char), buf
[80];
864 grid_type gline
, nline
;
865 struct island
*is_s
, *is_d
, *is_orth
;
867 #define APPEND do { \
868 if (movelen + len >= movesize) { \
869 movesize = movelen + len + 256; \
870 move = sresize(move, movesize, char); \
872 strcpy(move + movelen, buf); \
876 move
[movelen
++] = 'S';
877 move
[movelen
] = '\0';
879 assert(src
->n_islands
== dest
->n_islands
);
881 for (i
= 0; i
< src
->n_islands
; i
++) {
882 is_s
= &src
->islands
[i
];
883 is_d
= &dest
->islands
[i
];
884 assert(is_s
->x
== is_d
->x
);
885 assert(is_s
->y
== is_d
->y
);
886 assert(is_s
->adj
.npoints
== is_d
->adj
.npoints
); /* more paranoia */
888 for (d
= 0; d
< is_s
->adj
.npoints
; d
++) {
889 if (is_s
->adj
.points
[d
].dx
== -1 ||
890 is_s
->adj
.points
[d
].dy
== -1) continue;
892 x
= is_s
->adj
.points
[d
].x
;
893 y
= is_s
->adj
.points
[d
].y
;
894 gline
= is_s
->adj
.points
[d
].dx
? G_LINEH
: G_LINEV
;
895 nline
= is_s
->adj
.points
[d
].dx
? G_NOLINEH
: G_NOLINEV
;
896 is_orth
= INDEX(dest
, gridi
,
897 ISLAND_ORTHX(is_d
, d
), ISLAND_ORTHY(is_d
, d
));
899 if (GRIDCOUNT(src
, x
, y
, gline
) != GRIDCOUNT(dest
, x
, y
, gline
)) {
901 len
= sprintf(buf
, ";L%d,%d,%d,%d,%d",
902 is_s
->x
, is_s
->y
, is_orth
->x
, is_orth
->y
,
903 GRIDCOUNT(dest
, x
, y
, gline
));
906 if ((GRID(src
,x
,y
) & nline
) != (GRID(dest
, x
, y
) & nline
)) {
908 len
= sprintf(buf
, ";N%d,%d,%d,%d",
909 is_s
->x
, is_s
->y
, is_orth
->x
, is_orth
->y
);
913 if ((GRID(src
, is_s
->x
, is_s
->y
) & G_MARK
) !=
914 (GRID(dest
, is_d
->x
, is_d
->y
) & G_MARK
)) {
915 len
= sprintf(buf
, ";M%d,%d", is_s
->x
, is_s
->y
);
922 /* --- Game setup and solving utilities --- */
924 /* This function is optimised; a Quantify showed that lots of grid-generation time
925 * (>50%) was spent in here. Hence the IDX() stuff. */
927 static void map_update_possibles(game_state
*state
)
929 int x
, y
, s
, e
, bl
, i
, np
, maxb
, w
= state
->w
, idx
;
930 struct island
*is_s
= NULL
, *is_f
= NULL
;
932 /* Run down vertical stripes [un]setting possv... */
933 for (x
= 0; x
< state
->w
; x
++) {
937 maxb
= state
->params
.maxb
; /* placate optimiser */
938 /* Unset possible flags until we find an island. */
939 for (y
= 0; y
< state
->h
; y
++) {
940 is_s
= IDX(state
, gridi
, idx
);
946 IDX(state
, possv
, idx
) = 0;
949 for (; y
< state
->h
; y
++) {
950 maxb
= min(maxb
, IDX(state
, maxv
, idx
));
951 is_f
= IDX(state
, gridi
, idx
);
954 np
= min(maxb
, is_f
->count
);
957 for (i
= s
; i
<= e
; i
++) {
958 INDEX(state
, possv
, x
, i
) = bl
? 0 : np
;
967 if (IDX(state
,grid
,idx
) & (G_LINEH
|G_NOLINEV
)) bl
= 1;
972 for (i
= s
; i
<= e
; i
++)
973 INDEX(state
, possv
, x
, i
) = 0;
977 /* ...and now do horizontal stripes [un]setting possh. */
978 /* can we lose this clone'n'hack? */
979 for (y
= 0; y
< state
->h
; y
++) {
983 maxb
= state
->params
.maxb
; /* placate optimiser */
984 for (x
= 0; x
< state
->w
; x
++) {
985 is_s
= IDX(state
, gridi
, idx
);
991 IDX(state
, possh
, idx
) = 0;
994 for (; x
< state
->w
; x
++) {
995 maxb
= min(maxb
, IDX(state
, maxh
, idx
));
996 is_f
= IDX(state
, gridi
, idx
);
999 np
= min(maxb
, is_f
->count
);
1002 for (i
= s
; i
<= e
; i
++) {
1003 INDEX(state
, possh
, i
, y
) = bl
? 0 : np
;
1012 if (IDX(state
,grid
,idx
) & (G_LINEV
|G_NOLINEH
)) bl
= 1;
1017 for (i
= s
; i
<= e
; i
++)
1018 INDEX(state
, possh
, i
, y
) = 0;
1023 static void map_count(game_state
*state
)
1026 grid_type flag
, grid
;
1029 for (i
= 0; i
< state
->n_islands
; i
++) {
1030 is
= &state
->islands
[i
];
1032 for (n
= 0; n
< is
->adj
.npoints
; n
++) {
1033 ax
= is
->adj
.points
[n
].x
;
1034 ay
= is
->adj
.points
[n
].y
;
1035 flag
= (ax
== is
->x
) ? G_LINEV
: G_LINEH
;
1036 grid
= GRID(state
,ax
,ay
);
1038 is
->count
+= INDEX(state
,lines
,ax
,ay
);
1044 static void map_find_orthogonal(game_state
*state
)
1048 for (i
= 0; i
< state
->n_islands
; i
++) {
1049 island_find_orthogonal(&state
->islands
[i
]);
1053 struct bridges_neighbour_ctx
{
1055 int i
, n
, neighbours
[4];
1057 static int bridges_neighbour(int vertex
, void *vctx
)
1059 struct bridges_neighbour_ctx
*ctx
= (struct bridges_neighbour_ctx
*)vctx
;
1061 game_state
*state
= ctx
->state
;
1062 int w
= state
->w
, x
= vertex
% w
, y
= vertex
/ w
;
1063 grid_type grid
= GRID(state
, x
, y
), gline
= grid
& G_LINE
;
1065 int x1
, y1
, x2
, y2
, i
;
1067 ctx
->i
= ctx
->n
= 0;
1069 is
= INDEX(state
, gridi
, x
, y
);
1071 for (i
= 0; i
< is
->adj
.npoints
; i
++) {
1072 gline
= is
->adj
.points
[i
].dx
? G_LINEH
: G_LINEV
;
1073 if (GRID(state
, is
->adj
.points
[i
].x
,
1074 is
->adj
.points
[i
].y
) & gline
) {
1075 ctx
->neighbours
[ctx
->n
++] =
1076 (is
->adj
.points
[i
].y
* w
+ is
->adj
.points
[i
].x
);
1080 if (gline
& G_LINEV
) {
1087 /* Non-island squares with edges in should never be
1088 * pointing off the edge of the grid. */
1089 assert(INGRID(state
, x1
, y1
));
1090 assert(INGRID(state
, x2
, y2
));
1091 if (GRID(state
, x1
, y1
) & (gline
| G_ISLAND
))
1092 ctx
->neighbours
[ctx
->n
++] = y1
* w
+ x1
;
1093 if (GRID(state
, x2
, y2
) & (gline
| G_ISLAND
))
1094 ctx
->neighbours
[ctx
->n
++] = y2
* w
+ x2
;
1098 if (ctx
->i
< ctx
->n
)
1099 return ctx
->neighbours
[ctx
->i
++];
1104 static int map_hasloops(game_state
*state
, int mark
)
1107 struct findloopstate
*fls
;
1108 struct bridges_neighbour_ctx ctx
;
1111 fls
= findloop_new_state(state
->w
* state
->h
);
1113 ret
= findloop_run(fls
, state
->w
* state
->h
, bridges_neighbour
, &ctx
);
1116 for (y
= 0; y
< state
->h
; y
++) {
1117 for (x
= 0; x
< state
->w
; x
++) {
1120 u
= y
* state
->w
+ x
;
1121 for (v
= bridges_neighbour(u
, &ctx
); v
>= 0;
1122 v
= bridges_neighbour(-1, &ctx
))
1123 if (findloop_is_loop_edge(fls
, u
, v
))
1124 GRID(state
,x
,y
) |= G_WARN
;
1129 findloop_free_state(fls
);
1133 static void map_group(game_state
*state
)
1135 int i
, wh
= state
->w
*state
->h
, d1
, d2
;
1137 int *dsf
= state
->solver
->dsf
;
1138 struct island
*is
, *is_join
;
1140 /* Initialise dsf. */
1143 /* For each island, find connected islands right or down
1144 * and merge the dsf for the island squares as well as the
1145 * bridge squares. */
1146 for (x
= 0; x
< state
->w
; x
++) {
1147 for (y
= 0; y
< state
->h
; y
++) {
1148 GRID(state
,x
,y
) &= ~(G_SWEEP
|G_WARN
); /* for group_full. */
1150 is
= INDEX(state
, gridi
, x
, y
);
1153 for (i
= 0; i
< is
->adj
.npoints
; i
++) {
1154 /* only want right/down */
1155 if (is
->adj
.points
[i
].dx
== -1 ||
1156 is
->adj
.points
[i
].dy
== -1) continue;
1158 is_join
= island_find_connection(is
, i
);
1159 if (!is_join
) continue;
1161 d2
= DINDEX(is_join
->x
, is_join
->y
);
1162 if (dsf_canonify(dsf
,d1
) == dsf_canonify(dsf
,d2
)) {
1163 ; /* we have a loop. See comment in map_hasloops. */
1164 /* However, we still want to merge all squares joining
1165 * this side-that-makes-a-loop. */
1167 /* merge all squares between island 1 and island 2. */
1168 for (x2
= x
; x2
<= is_join
->x
; x2
++) {
1169 for (y2
= y
; y2
<= is_join
->y
; y2
++) {
1171 if (d1
!= d2
) dsf_merge(dsf
,d1
,d2
);
1179 static int map_group_check(game_state
*state
, int canon
, int warn
,
1182 int *dsf
= state
->solver
->dsf
, nislands
= 0;
1183 int x
, y
, i
, allfull
= 1;
1186 for (i
= 0; i
< state
->n_islands
; i
++) {
1187 is
= &state
->islands
[i
];
1188 if (dsf_canonify(dsf
, DINDEX(is
->x
,is
->y
)) != canon
) continue;
1190 GRID(state
, is
->x
, is
->y
) |= G_SWEEP
;
1192 if (island_countbridges(is
) != is
->count
)
1195 if (warn
&& allfull
&& nislands
!= state
->n_islands
) {
1196 /* we're full and this island group isn't the whole set.
1197 * Mark all squares with this dsf canon as ERR. */
1198 for (x
= 0; x
< state
->w
; x
++) {
1199 for (y
= 0; y
< state
->h
; y
++) {
1200 if (dsf_canonify(dsf
, DINDEX(x
,y
)) == canon
) {
1201 GRID(state
,x
,y
) |= G_WARN
;
1207 if (nislands_r
) *nislands_r
= nislands
;
1211 static int map_group_full(game_state
*state
, int *ngroups_r
)
1213 int *dsf
= state
->solver
->dsf
, ngroups
= 0;
1217 /* NB this assumes map_group (or sth else) has cleared G_SWEEP. */
1219 for (i
= 0; i
< state
->n_islands
; i
++) {
1220 is
= &state
->islands
[i
];
1221 if (GRID(state
,is
->x
,is
->y
) & G_SWEEP
) continue;
1224 if (map_group_check(state
, dsf_canonify(dsf
, DINDEX(is
->x
,is
->y
)),
1229 *ngroups_r
= ngroups
;
1233 static int map_check(game_state
*state
)
1237 /* Check for loops, if necessary. */
1238 if (!state
->allowloops
) {
1239 if (map_hasloops(state
, 1))
1243 /* Place islands into island groups and check for early
1244 * satisfied-groups. */
1245 map_group(state
); /* clears WARN and SWEEP */
1246 if (map_group_full(state
, &ngroups
)) {
1247 if (ngroups
== 1) return 1;
1252 static void map_clear(game_state
*state
)
1256 for (x
= 0; x
< state
->w
; x
++) {
1257 for (y
= 0; y
< state
->h
; y
++) {
1258 /* clear most flags; might want to be slightly more careful here. */
1259 GRID(state
,x
,y
) &= G_ISLAND
;
1264 static void solve_join(struct island
*is
, int direction
, int n
, int is_max
)
1266 struct island
*is_orth
;
1267 int d1
, d2
, *dsf
= is
->state
->solver
->dsf
;
1268 game_state
*state
= is
->state
; /* for DINDEX */
1270 is_orth
= INDEX(is
->state
, gridi
,
1271 ISLAND_ORTHX(is
, direction
),
1272 ISLAND_ORTHY(is
, direction
));
1274 /*debug(("...joining (%d,%d) to (%d,%d) with %d bridge(s).\n",
1275 is->x, is->y, is_orth->x, is_orth->y, n));*/
1276 island_join(is
, is_orth
, n
, is_max
);
1278 if (n
> 0 && !is_max
) {
1279 d1
= DINDEX(is
->x
, is
->y
);
1280 d2
= DINDEX(is_orth
->x
, is_orth
->y
);
1281 if (dsf_canonify(dsf
, d1
) != dsf_canonify(dsf
, d2
))
1282 dsf_merge(dsf
, d1
, d2
);
1286 static int solve_fillone(struct island
*is
)
1290 debug(("solve_fillone for island (%d,%d).\n", is
->x
, is
->y
));
1292 for (i
= 0; i
< is
->adj
.npoints
; i
++) {
1293 if (island_isadj(is
, i
)) {
1294 if (island_hasbridge(is
, i
)) {
1295 /* already attached; do nothing. */;
1297 solve_join(is
, i
, 1, 0);
1305 static int solve_fill(struct island
*is
)
1307 /* for each unmarked adjacent, make sure we convert every possible bridge
1308 * to a real one, and then work out the possibles afresh. */
1309 int i
, nnew
, ncurr
, nadded
= 0, missing
;
1311 debug(("solve_fill for island (%d,%d).\n", is
->x
, is
->y
));
1313 missing
= is
->count
- island_countbridges(is
);
1314 if (missing
< 0) return 0;
1316 /* very like island_countspaces. */
1317 for (i
= 0; i
< is
->adj
.npoints
; i
++) {
1318 nnew
= island_adjspace(is
, 1, missing
, i
);
1320 ncurr
= GRIDCOUNT(is
->state
,
1321 is
->adj
.points
[i
].x
, is
->adj
.points
[i
].y
,
1322 is
->adj
.points
[i
].dx
? G_LINEH
: G_LINEV
);
1324 solve_join(is
, i
, nnew
+ ncurr
, 0);
1331 static int solve_island_stage1(struct island
*is
, int *didsth_r
)
1333 int bridges
= island_countbridges(is
);
1334 int nspaces
= island_countspaces(is
, 1);
1335 int nadj
= island_countadj(is
);
1340 /*debug(("island at (%d,%d) filled %d/%d (%d spc) nadj %d\n",
1341 is->x, is->y, bridges, is->count, nspaces, nadj));*/
1342 if (bridges
> is
->count
) {
1343 /* We only ever add bridges when we're sure they fit, or that's
1344 * the only place they can go. If we've added bridges such that
1345 * another island has become wrong, the puzzle must not have had
1347 debug(("...island at (%d,%d) is overpopulated!\n", is
->x
, is
->y
));
1349 } else if (bridges
== is
->count
) {
1350 /* This island is full. Make sure it's marked (and update
1351 * possibles if we did). */
1352 if (!(GRID(is
->state
, is
->x
, is
->y
) & G_MARK
)) {
1353 debug(("...marking island (%d,%d) as full.\n", is
->x
, is
->y
));
1354 island_togglemark(is
);
1357 } else if (GRID(is
->state
, is
->x
, is
->y
) & G_MARK
) {
1358 debug(("...island (%d,%d) is marked but unfinished!\n",
1360 return 0; /* island has been marked unfinished; no solution from here. */
1362 /* This is the interesting bit; we try and fill in more information
1363 * about this island. */
1364 if (is
->count
== bridges
+ nspaces
) {
1365 if (solve_fill(is
) > 0) didsth
= 1;
1366 } else if (is
->count
> ((nadj
-1) * is
->state
->maxb
)) {
1367 /* must have at least one bridge in each possible direction. */
1368 if (solve_fillone(is
) > 0) didsth
= 1;
1372 map_update_possibles(is
->state
);
1378 /* returns non-zero if a new line here would cause a loop. */
1379 static int solve_island_checkloop(struct island
*is
, int direction
)
1381 struct island
*is_orth
;
1382 int *dsf
= is
->state
->solver
->dsf
, d1
, d2
;
1383 game_state
*state
= is
->state
;
1385 if (is
->state
->allowloops
) return 0; /* don't care anyway */
1386 if (island_hasbridge(is
, direction
)) return 0; /* already has a bridge */
1387 if (island_isadj(is
, direction
) == 0) return 0; /* no adj island */
1389 is_orth
= INDEX(is
->state
, gridi
,
1390 ISLAND_ORTHX(is
,direction
),
1391 ISLAND_ORTHY(is
,direction
));
1392 if (!is_orth
) return 0;
1394 d1
= DINDEX(is
->x
, is
->y
);
1395 d2
= DINDEX(is_orth
->x
, is_orth
->y
);
1396 if (dsf_canonify(dsf
, d1
) == dsf_canonify(dsf
, d2
)) {
1397 /* two islands are connected already; don't join them. */
1403 static int solve_island_stage2(struct island
*is
, int *didsth_r
)
1405 int added
= 0, removed
= 0, navail
= 0, nadj
, i
;
1409 for (i
= 0; i
< is
->adj
.npoints
; i
++) {
1410 if (solve_island_checkloop(is
, i
)) {
1411 debug(("removing possible loop at (%d,%d) direction %d.\n",
1413 solve_join(is
, i
, -1, 0);
1414 map_update_possibles(is
->state
);
1417 navail
+= island_isadj(is
, i
);
1418 /*debug(("stage2: navail for (%d,%d) direction (%d,%d) is %d.\n",
1420 is->adj.points[i].dx, is->adj.points[i].dy,
1421 island_isadj(is, i)));*/
1425 /*debug(("island at (%d,%d) navail %d: checking...\n", is->x, is->y, navail));*/
1427 for (i
= 0; i
< is
->adj
.npoints
; i
++) {
1428 if (!island_hasbridge(is
, i
)) {
1429 nadj
= island_isadj(is
, i
);
1430 if (nadj
> 0 && (navail
- nadj
) < is
->count
) {
1431 /* we couldn't now complete the island without at
1432 * least one bridge here; put it in. */
1433 /*debug(("nadj %d, navail %d, is->count %d.\n",
1434 nadj, navail, is->count));*/
1435 debug(("island at (%d,%d) direction (%d,%d) must have 1 bridge\n",
1437 is
->adj
.points
[i
].dx
, is
->adj
.points
[i
].dy
));
1438 solve_join(is
, i
, 1, 0);
1440 /*debug_state(is->state);
1441 debug_possibles(is->state);*/
1445 if (added
) map_update_possibles(is
->state
);
1446 if (added
|| removed
) *didsth_r
= 1;
1450 static int solve_island_subgroup(struct island
*is
, int direction
)
1452 struct island
*is_join
;
1453 int nislands
, *dsf
= is
->state
->solver
->dsf
;
1454 game_state
*state
= is
->state
;
1456 debug(("..checking subgroups.\n"));
1458 /* if is isn't full, return 0. */
1459 if (island_countbridges(is
) < is
->count
) {
1460 debug(("...orig island (%d,%d) not full.\n", is
->x
, is
->y
));
1464 if (direction
>= 0) {
1465 is_join
= INDEX(state
, gridi
,
1466 ISLAND_ORTHX(is
, direction
),
1467 ISLAND_ORTHY(is
, direction
));
1470 /* if is_join isn't full, return 0. */
1471 if (island_countbridges(is_join
) < is_join
->count
) {
1472 debug(("...dest island (%d,%d) not full.\n",
1473 is_join
->x
, is_join
->y
));
1478 /* Check group membership for is->dsf; if it's full return 1. */
1479 if (map_group_check(state
, dsf_canonify(dsf
, DINDEX(is
->x
,is
->y
)),
1481 if (nislands
< state
->n_islands
) {
1482 /* we have a full subgroup that isn't the whole set.
1483 * This isn't allowed. */
1484 debug(("island at (%d,%d) makes full subgroup, disallowing.\n",
1488 debug(("...has finished puzzle.\n"));
1494 static int solve_island_impossible(game_state
*state
)
1499 /* If any islands are impossible, return 1. */
1500 for (i
= 0; i
< state
->n_islands
; i
++) {
1501 is
= &state
->islands
[i
];
1502 if (island_impossible(is
, 0)) {
1503 debug(("island at (%d,%d) has become impossible, disallowing.\n",
1511 /* Bear in mind that this function is really rather inefficient. */
1512 static int solve_island_stage3(struct island
*is
, int *didsth_r
)
1514 int i
, n
, x
, y
, missing
, spc
, curr
, maxb
, didsth
= 0;
1515 int wh
= is
->state
->w
* is
->state
->h
;
1516 struct solver_state
*ss
= is
->state
->solver
;
1520 missing
= is
->count
- island_countbridges(is
);
1521 if (missing
<= 0) return 1;
1523 for (i
= 0; i
< is
->adj
.npoints
; i
++) {
1524 x
= is
->adj
.points
[i
].x
;
1525 y
= is
->adj
.points
[i
].y
;
1526 spc
= island_adjspace(is
, 1, missing
, i
);
1527 if (spc
== 0) continue;
1529 curr
= GRIDCOUNT(is
->state
, x
, y
,
1530 is
->adj
.points
[i
].dx
? G_LINEH
: G_LINEV
);
1531 debug(("island at (%d,%d) s3, trying %d - %d bridges.\n",
1532 is
->x
, is
->y
, curr
+1, curr
+spc
));
1534 /* Now we know that this island could have more bridges,
1535 * to bring the total from curr+1 to curr+spc. */
1537 /* We have to squirrel the dsf away and restore it afterwards;
1538 * it is additive only, and can't be removed from. */
1539 memcpy(ss
->tmpdsf
, ss
->dsf
, wh
*sizeof(int));
1540 for (n
= curr
+1; n
<= curr
+spc
; n
++) {
1541 solve_join(is
, i
, n
, 0);
1542 map_update_possibles(is
->state
);
1544 if (solve_island_subgroup(is
, i
) ||
1545 solve_island_impossible(is
->state
)) {
1547 debug(("island at (%d,%d) d(%d,%d) new max of %d bridges:\n",
1549 is
->adj
.points
[i
].dx
, is
->adj
.points
[i
].dy
,
1554 solve_join(is
, i
, curr
, 0); /* put back to before. */
1555 memcpy(ss
->dsf
, ss
->tmpdsf
, wh
*sizeof(int));
1558 /*debug_state(is->state);*/
1560 debug(("...adding NOLINE.\n"));
1561 solve_join(is
, i
, -1, 0); /* we can't have any bridges here. */
1563 debug(("...setting maximum\n"));
1564 solve_join(is
, i
, maxb
, 1);
1568 map_update_possibles(is
->state
);
1571 for (i
= 0; i
< is
->adj
.npoints
; i
++) {
1573 * Now check to see if any currently empty direction must have
1574 * at least one bridge in order to avoid forming an isolated
1575 * subgraph. This differs from the check above in that it
1576 * considers multiple target islands. For example:
1583 * The example on the left can be handled by the above loop:
1584 * it will observe that connecting the central 2 twice to the
1585 * left would form an isolated subgraph, and hence it will
1586 * restrict that 2 to at most one bridge in that direction.
1587 * But the example on the right won't be handled by that loop,
1588 * because the deduction requires us to imagine connecting the
1589 * 3 to _both_ the 1 and 2 at once to form an isolated
1592 * This pass is necessary _as well_ as the above one, because
1593 * neither can do the other's job. In the left one,
1594 * restricting the direction which _would_ cause trouble can
1595 * be done even if it's not yet clear which of the remaining
1596 * directions has to have a compensatory bridge; whereas the
1597 * pass below that can handle the right-hand example does need
1598 * to know what direction to point the necessary bridge in.
1600 * Neither pass can handle the most general case, in which we
1601 * observe that an arbitrary subset of an island's neighbours
1602 * would form an isolated subgraph with it if it connected
1603 * maximally to them, and hence that at least one bridge must
1604 * point to some neighbour outside that subset but we don't
1605 * know which neighbour. To handle that, we'd have to have a
1606 * richer data format for the solver, which could cope with
1607 * recording the idea that at least one of two edges must have
1614 spc
= island_adjspace(is
, 1, missing
, i
);
1615 if (spc
== 0) continue;
1617 for (j
= 0; j
< is
->adj
.npoints
; j
++)
1618 before
[j
] = GRIDCOUNT(is
->state
,
1619 is
->adj
.points
[j
].x
,
1620 is
->adj
.points
[j
].y
,
1621 is
->adj
.points
[j
].dx
? G_LINEH
: G_LINEV
);
1622 if (before
[i
] != 0) continue; /* this idea is pointless otherwise */
1624 memcpy(ss
->tmpdsf
, ss
->dsf
, wh
*sizeof(int));
1626 for (j
= 0; j
< is
->adj
.npoints
; j
++) {
1627 spc
= island_adjspace(is
, 1, missing
, j
);
1628 if (spc
== 0) continue;
1629 if (j
== i
) continue;
1630 solve_join(is
, j
, before
[j
] + spc
, 0);
1632 map_update_possibles(is
->state
);
1634 if (solve_island_subgroup(is
, -1))
1637 for (j
= 0; j
< is
->adj
.npoints
; j
++)
1638 solve_join(is
, j
, before
[j
], 0);
1639 memcpy(ss
->dsf
, ss
->tmpdsf
, wh
*sizeof(int));
1642 debug(("island at (%d,%d) must connect in direction (%d,%d) to"
1643 " avoid full subgroup.\n",
1644 is
->x
, is
->y
, is
->adj
.points
[i
].dx
, is
->adj
.points
[i
].dy
));
1645 solve_join(is
, i
, 1, 0);
1649 map_update_possibles(is
->state
);
1652 if (didsth
) *didsth_r
= didsth
;
1656 #define CONTINUE_IF_FULL do { \
1657 if (GRID(state, is->x, is->y) & G_MARK) { \
1658 /* island full, don't try fixing it */ \
1662 static int solve_sub(game_state
*state
, int difficulty
, int depth
)
1670 /* First island iteration: things we can work out by looking at
1671 * properties of the island as a whole. */
1672 for (i
= 0; i
< state
->n_islands
; i
++) {
1673 is
= &state
->islands
[i
];
1674 if (!solve_island_stage1(is
, &didsth
)) return 0;
1676 if (didsth
) continue;
1677 else if (difficulty
< 1) break;
1679 /* Second island iteration: thing we can work out by looking at
1680 * properties of individual island connections. */
1681 for (i
= 0; i
< state
->n_islands
; i
++) {
1682 is
= &state
->islands
[i
];
1684 if (!solve_island_stage2(is
, &didsth
)) return 0;
1686 if (didsth
) continue;
1687 else if (difficulty
< 2) break;
1689 /* Third island iteration: things we can only work out by looking
1690 * at groups of islands. */
1691 for (i
= 0; i
< state
->n_islands
; i
++) {
1692 is
= &state
->islands
[i
];
1693 if (!solve_island_stage3(is
, &didsth
)) return 0;
1695 if (didsth
) continue;
1696 else if (difficulty
< 3) break;
1698 /* If we can be bothered, write a recursive solver to finish here. */
1701 if (map_check(state
)) return 1; /* solved it */
1705 static void solve_for_hint(game_state
*state
)
1708 solve_sub(state
, 10, 0);
1711 static int solve_from_scratch(game_state
*state
, int difficulty
)
1715 map_update_possibles(state
);
1716 return solve_sub(state
, difficulty
, 0);
1719 /* --- New game functions --- */
1721 static game_state
*new_state(const game_params
*params
)
1723 game_state
*ret
= snew(game_state
);
1724 int wh
= params
->w
* params
->h
, i
;
1728 ret
->allowloops
= params
->allowloops
;
1729 ret
->maxb
= params
->maxb
;
1730 ret
->params
= *params
;
1732 ret
->grid
= snewn(wh
, grid_type
);
1733 memset(ret
->grid
, 0, GRIDSZ(ret
));
1735 ret
->wha
= snewn(wh
*N_WH_ARRAYS
, char);
1736 memset(ret
->wha
, 0, wh
*N_WH_ARRAYS
*sizeof(char));
1738 ret
->possv
= ret
->wha
;
1739 ret
->possh
= ret
->wha
+ wh
;
1740 ret
->lines
= ret
->wha
+ wh
*2;
1741 ret
->maxv
= ret
->wha
+ wh
*3;
1742 ret
->maxh
= ret
->wha
+ wh
*4;
1744 memset(ret
->maxv
, ret
->maxb
, wh
*sizeof(char));
1745 memset(ret
->maxh
, ret
->maxb
, wh
*sizeof(char));
1747 ret
->islands
= NULL
;
1749 ret
->n_islands_alloc
= 0;
1751 ret
->gridi
= snewn(wh
, struct island
*);
1752 for (i
= 0; i
< wh
; i
++) ret
->gridi
[i
] = NULL
;
1754 ret
->solved
= ret
->completed
= 0;
1756 ret
->solver
= snew(struct solver_state
);
1757 ret
->solver
->dsf
= snew_dsf(wh
);
1758 ret
->solver
->tmpdsf
= snewn(wh
, int);
1760 ret
->solver
->refcount
= 1;
1765 static game_state
*dup_game(const game_state
*state
)
1767 game_state
*ret
= snew(game_state
);
1768 int wh
= state
->w
*state
->h
;
1772 ret
->allowloops
= state
->allowloops
;
1773 ret
->maxb
= state
->maxb
;
1774 ret
->params
= state
->params
;
1776 ret
->grid
= snewn(wh
, grid_type
);
1777 memcpy(ret
->grid
, state
->grid
, GRIDSZ(ret
));
1779 ret
->wha
= snewn(wh
*N_WH_ARRAYS
, char);
1780 memcpy(ret
->wha
, state
->wha
, wh
*N_WH_ARRAYS
*sizeof(char));
1782 ret
->possv
= ret
->wha
;
1783 ret
->possh
= ret
->wha
+ wh
;
1784 ret
->lines
= ret
->wha
+ wh
*2;
1785 ret
->maxv
= ret
->wha
+ wh
*3;
1786 ret
->maxh
= ret
->wha
+ wh
*4;
1788 ret
->islands
= snewn(state
->n_islands
, struct island
);
1789 memcpy(ret
->islands
, state
->islands
, state
->n_islands
* sizeof(struct island
));
1790 ret
->n_islands
= ret
->n_islands_alloc
= state
->n_islands
;
1792 ret
->gridi
= snewn(wh
, struct island
*);
1793 fixup_islands_for_realloc(ret
);
1795 ret
->solved
= state
->solved
;
1796 ret
->completed
= state
->completed
;
1798 ret
->solver
= state
->solver
;
1799 ret
->solver
->refcount
++;
1804 static void free_game(game_state
*state
)
1806 if (--state
->solver
->refcount
<= 0) {
1807 sfree(state
->solver
->dsf
);
1808 sfree(state
->solver
->tmpdsf
);
1809 sfree(state
->solver
);
1812 sfree(state
->islands
);
1813 sfree(state
->gridi
);
1821 #define MAX_NEWISLAND_TRIES 50
1822 #define MIN_SENSIBLE_ISLANDS 3
1824 #define ORDER(a,b) do { if (a < b) { int tmp=a; int a=b; int b=tmp; } } while(0)
1826 static char *new_game_desc(const game_params
*params
, random_state
*rs
,
1827 char **aux
, int interactive
)
1829 game_state
*tobuild
= NULL
;
1830 int i
, j
, wh
= params
->w
* params
->h
, x
, y
, dx
, dy
;
1831 int minx
, miny
, maxx
, maxy
, joinx
, joiny
, newx
, newy
, diffx
, diffy
;
1832 int ni_req
= max((params
->islands
* wh
) / 100, MIN_SENSIBLE_ISLANDS
), ni_curr
, ni_bad
;
1833 struct island
*is
, *is2
;
1835 unsigned int echeck
;
1837 /* pick a first island position randomly. */
1839 if (tobuild
) free_game(tobuild
);
1840 tobuild
= new_state(params
);
1842 x
= random_upto(rs
, params
->w
);
1843 y
= random_upto(rs
, params
->h
);
1844 island_add(tobuild
, x
, y
, 0);
1847 debug(("Created initial island at (%d,%d).\n", x
, y
));
1849 while (ni_curr
< ni_req
) {
1850 /* Pick a random island to try and extend from. */
1851 i
= random_upto(rs
, tobuild
->n_islands
);
1852 is
= &tobuild
->islands
[i
];
1854 /* Pick a random direction to extend in. */
1855 j
= random_upto(rs
, is
->adj
.npoints
);
1856 dx
= is
->adj
.points
[j
].x
- is
->x
;
1857 dy
= is
->adj
.points
[j
].y
- is
->y
;
1859 /* Find out limits of where we could put a new island. */
1861 minx
= is
->x
+ 2*dx
; miny
= is
->y
+ 2*dy
; /* closest is 2 units away. */
1862 x
= is
->x
+dx
; y
= is
->y
+dy
;
1863 if (GRID(tobuild
,x
,y
) & (G_LINEV
|G_LINEH
)) {
1864 /* already a line next to the island, continue. */
1868 if (x
< 0 || x
>= params
->w
|| y
< 0 || y
>= params
->h
) {
1869 /* got past the edge; put a possible at the island
1871 maxx
= x
-dx
; maxy
= y
-dy
;
1874 if (GRID(tobuild
,x
,y
) & G_ISLAND
) {
1875 /* could join up to an existing island... */
1876 joinx
= x
; joiny
= y
;
1877 /* ... or make a new one 2 spaces away. */
1878 maxx
= x
- 2*dx
; maxy
= y
- 2*dy
;
1880 } else if (GRID(tobuild
,x
,y
) & (G_LINEV
|G_LINEH
)) {
1881 /* could make a new one 1 space away from the line. */
1882 maxx
= x
- dx
; maxy
= y
- dy
;
1889 debug(("Island at (%d,%d) with d(%d,%d) has new positions "
1890 "(%d,%d) -> (%d,%d), join (%d,%d).\n",
1891 is
->x
, is
->y
, dx
, dy
, minx
, miny
, maxx
, maxy
, joinx
, joiny
));
1892 /* Now we know where we could either put a new island
1893 * (between min and max), or (if loops are allowed) could join on
1894 * to an existing island (at join). */
1895 if (params
->allowloops
&& joinx
!= -1 && joiny
!= -1) {
1896 if (random_upto(rs
, 100) < (unsigned long)params
->expansion
) {
1897 is2
= INDEX(tobuild
, gridi
, joinx
, joiny
);
1898 debug(("Joining island at (%d,%d) to (%d,%d).\n",
1899 is
->x
, is
->y
, is2
->x
, is2
->y
));
1903 diffx
= (maxx
- minx
) * dx
;
1904 diffy
= (maxy
- miny
) * dy
;
1905 if (diffx
< 0 || diffy
< 0) goto bad
;
1906 if (random_upto(rs
,100) < (unsigned long)params
->expansion
) {
1907 newx
= maxx
; newy
= maxy
;
1908 debug(("Creating new island at (%d,%d) (expanded).\n", newx
, newy
));
1910 newx
= minx
+ random_upto(rs
,diffx
+1)*dx
;
1911 newy
= miny
+ random_upto(rs
,diffy
+1)*dy
;
1912 debug(("Creating new island at (%d,%d).\n", newx
, newy
));
1914 /* check we're not next to island in the other orthogonal direction. */
1915 if ((INGRID(tobuild
,newx
+dy
,newy
+dx
) && (GRID(tobuild
,newx
+dy
,newy
+dx
) & G_ISLAND
)) ||
1916 (INGRID(tobuild
,newx
-dy
,newy
-dx
) && (GRID(tobuild
,newx
-dy
,newy
-dx
) & G_ISLAND
))) {
1917 debug(("New location is adjacent to island, skipping.\n"));
1920 is2
= island_add(tobuild
, newx
, newy
, 0);
1921 /* Must get is again at this point; the array might have
1922 * been realloced by island_add... */
1923 is
= &tobuild
->islands
[i
]; /* ...but order will not change. */
1925 ni_curr
++; ni_bad
= 0;
1927 island_join(is
, is2
, random_upto(rs
, tobuild
->maxb
)+1, 0);
1928 debug_state(tobuild
);
1933 if (ni_bad
> MAX_NEWISLAND_TRIES
) {
1934 debug(("Unable to create any new islands after %d tries; "
1935 "created %d [%d%%] (instead of %d [%d%%] requested).\n",
1936 MAX_NEWISLAND_TRIES
,
1937 ni_curr
, ni_curr
* 100 / wh
,
1938 ni_req
, ni_req
* 100 / wh
));
1945 debug(("Only generated one island (!), retrying.\n"));
1948 /* Check we have at least one island on each extremity of the grid. */
1950 for (x
= 0; x
< params
->w
; x
++) {
1951 if (INDEX(tobuild
, gridi
, x
, 0)) echeck
|= 1;
1952 if (INDEX(tobuild
, gridi
, x
, params
->h
-1)) echeck
|= 2;
1954 for (y
= 0; y
< params
->h
; y
++) {
1955 if (INDEX(tobuild
, gridi
, 0, y
)) echeck
|= 4;
1956 if (INDEX(tobuild
, gridi
, params
->w
-1, y
)) echeck
|= 8;
1959 debug(("Generated grid doesn't fill to sides, retrying.\n"));
1964 map_find_orthogonal(tobuild
);
1966 if (params
->difficulty
> 0) {
1967 if ((ni_curr
> MIN_SENSIBLE_ISLANDS
) &&
1968 (solve_from_scratch(tobuild
, params
->difficulty
-1) > 0)) {
1969 debug(("Grid is solvable at difficulty %d (too easy); retrying.\n",
1970 params
->difficulty
-1));
1975 if (solve_from_scratch(tobuild
, params
->difficulty
) == 0) {
1976 debug(("Grid not solvable at difficulty %d, (too hard); retrying.\n",
1977 params
->difficulty
));
1981 /* ... tobuild is now solved. We rely on this making the diff for aux. */
1982 debug_state(tobuild
);
1983 ret
= encode_game(tobuild
);
1985 game_state
*clean
= dup_game(tobuild
);
1987 map_update_possibles(clean
);
1988 *aux
= game_state_diff(clean
, tobuild
);
1996 static char *validate_desc(const game_params
*params
, const char *desc
)
1998 int i
, wh
= params
->w
* params
->h
;
2000 for (i
= 0; i
< wh
; i
++) {
2001 if (*desc
>= '1' && *desc
<= '9')
2003 else if (*desc
>= 'a' && *desc
<= 'z')
2004 i
+= *desc
- 'a'; /* plus the i++ */
2005 else if (*desc
>= 'A' && *desc
<= 'G')
2007 else if (*desc
== 'V' || *desc
== 'W' ||
2008 *desc
== 'X' || *desc
== 'Y' ||
2009 *desc
== 'H' || *desc
== 'I' ||
2010 *desc
== 'J' || *desc
== 'K')
2013 return "Game description shorter than expected";
2015 return "Game description contains unexpected character";
2018 if (*desc
|| i
> wh
)
2019 return "Game description longer than expected";
2024 static game_state
*new_game_sub(const game_params
*params
, const char *desc
)
2026 game_state
*state
= new_state(params
);
2029 debug(("new_game[_sub]: desc = '%s'.\n", desc
));
2031 for (y
= 0; y
< params
->h
; y
++) {
2032 for (x
= 0; x
< params
->w
; x
++) {
2038 if (c
>= 'a' && c
<= 'z')
2048 case '1': case '2': case '3': case '4':
2049 case '5': case '6': case '7': case '8': case '9':
2050 island_add(state
, x
, y
, (c
- '0'));
2053 case 'A': case 'B': case 'C': case 'D':
2054 case 'E': case 'F': case 'G':
2055 island_add(state
, x
, y
, (c
- 'A') + 10);
2063 assert(!"Malformed desc.");
2068 if (*desc
) assert(!"Over-long desc.");
2070 map_find_orthogonal(state
);
2071 map_update_possibles(state
);
2076 static game_state
*new_game(midend
*me
, const game_params
*params
,
2079 return new_game_sub(params
, desc
);
2083 int dragx_src
, dragy_src
; /* source; -1 means no drag */
2084 int dragx_dst
, dragy_dst
; /* src's closest orth island. */
2086 int dragging
, drag_is_noline
, nlines
;
2088 int cur_x
, cur_y
, cur_visible
; /* cursor position */
2092 static char *ui_cancel_drag(game_ui
*ui
)
2094 ui
->dragx_src
= ui
->dragy_src
= -1;
2095 ui
->dragx_dst
= ui
->dragy_dst
= -1;
2100 static game_ui
*new_ui(const game_state
*state
)
2102 game_ui
*ui
= snew(game_ui
);
2104 ui
->cur_x
= state
->islands
[0].x
;
2105 ui
->cur_y
= state
->islands
[0].y
;
2106 ui
->cur_visible
= 0;
2111 static void free_ui(game_ui
*ui
)
2116 static char *encode_ui(const game_ui
*ui
)
2121 static void decode_ui(game_ui
*ui
, const char *encoding
)
2125 static void game_changed_state(game_ui
*ui
, const game_state
*oldstate
,
2126 const game_state
*newstate
)
2130 struct game_drawstate
{
2133 unsigned long *grid
, *newgrid
;
2135 int started
, dragging
;
2139 * The contents of ds->grid are complicated, because of the circular
2140 * islands which overlap their own grid square into neighbouring
2141 * squares. An island square can contain pieces of the bridges in all
2142 * directions, and conversely a bridge square can be intruded on by
2143 * islands from any direction.
2145 * So we define one group of flags describing what's important about
2146 * an island, and another describing a bridge. Island squares' entries
2147 * in ds->grid contain one of the former and four of the latter; bridge
2148 * squares, four of the former and _two_ of the latter - because a
2149 * horizontal and vertical 'bridge' can cross, when one of them is a
2150 * 'no bridge here' pencil mark.
2152 * Bridge flags need to indicate 0-4 actual bridges (3 bits), a 'no
2153 * bridge' row of crosses, or a grey hint line; that's 7
2154 * possibilities, so 3 bits suffice. But then we also need to vary the
2155 * colours: the bridges can turn COL_WARNING if they're part of a loop
2156 * in no-loops mode, COL_HIGHLIGHT during a victory flash, or
2157 * COL_SELECTED if they're the bridge the user is currently dragging,
2158 * so that's 2 more bits for foreground colour. Also bridges can be
2159 * backed by COL_MARK if they're locked by the user, so that's one
2160 * more bit, making 6 bits per bridge direction.
2162 * Island flags omit the actual island clue (it never changes during
2163 * the game, so doesn't have to be stored in ds->grid to check against
2164 * the previous version), so they just need to include 2 bits for
2165 * foreground colour (an island can be normal, COL_HIGHLIGHT during
2166 * victory, COL_WARNING if its clue is unsatisfiable, or COL_SELECTED
2167 * if it's part of the user's drag) and 2 bits for background (normal,
2168 * COL_MARK for a locked island, COL_CURSOR for the keyboard cursor).
2169 * That's 4 bits per island direction. We must also indicate whether
2170 * no island is present at all (in the case where the island is
2171 * potentially intruding into the side of a line square), which we do
2172 * using the unused 4th value of the background field.
2174 * So an island square needs 4 + 4*6 = 28 bits, while a bridge square
2175 * needs 4*4 + 2*6 = 28 bits too. Both only just fit in 32 bits, which
2176 * is handy, because otherwise we'd have to faff around forever with
2179 /* Flags for line data */
2180 #define DL_COUNTMASK 0x07
2181 #define DL_COUNT_CROSS 0x06
2182 #define DL_COUNT_HINT 0x07
2183 #define DL_COLMASK 0x18
2184 #define DL_COL_NORMAL 0x00
2185 #define DL_COL_WARNING 0x08
2186 #define DL_COL_FLASH 0x10
2187 #define DL_COL_SELECTED 0x18
2188 #define DL_LOCK 0x20
2189 #define DL_MASK 0x3F
2190 /* Flags for island data */
2191 #define DI_COLMASK 0x03
2192 #define DI_COL_NORMAL 0x00
2193 #define DI_COL_FLASH 0x01
2194 #define DI_COL_WARNING 0x02
2195 #define DI_COL_SELECTED 0x03
2196 #define DI_BGMASK 0x0C
2197 #define DI_BG_NO_ISLAND 0x00
2198 #define DI_BG_NORMAL 0x04
2199 #define DI_BG_MARK 0x08
2200 #define DI_BG_CURSOR 0x0C
2201 #define DI_MASK 0x0F
2202 /* Shift counts for the format of a 32-bit word in an island square */
2203 #define D_I_ISLAND_SHIFT 0
2204 #define D_I_LINE_SHIFT_L 4
2205 #define D_I_LINE_SHIFT_R 10
2206 #define D_I_LINE_SHIFT_U 16
2207 #define D_I_LINE_SHIFT_D 24
2208 /* Shift counts for the format of a 32-bit word in a line square */
2209 #define D_L_ISLAND_SHIFT_L 0
2210 #define D_L_ISLAND_SHIFT_R 4
2211 #define D_L_ISLAND_SHIFT_U 8
2212 #define D_L_ISLAND_SHIFT_D 12
2213 #define D_L_LINE_SHIFT_H 16
2214 #define D_L_LINE_SHIFT_V 22
2216 static char *update_drag_dst(const game_state
*state
, game_ui
*ui
,
2217 const game_drawstate
*ds
, int nx
, int ny
)
2219 int ox
, oy
, dx
, dy
, i
, currl
, maxb
;
2221 grid_type gtype
, ntype
, mtype
, curr
;
2223 if (ui
->dragx_src
== -1 || ui
->dragy_src
== -1) return NULL
;
2228 /* work out which of the four directions we're closest to... */
2229 ox
= COORD(ui
->dragx_src
) + TILE_SIZE
/2;
2230 oy
= COORD(ui
->dragy_src
) + TILE_SIZE
/2;
2232 if (abs(nx
-ox
) < abs(ny
-oy
)) {
2234 dy
= (ny
-oy
) < 0 ? -1 : 1;
2235 gtype
= G_LINEV
; ntype
= G_NOLINEV
; mtype
= G_MARKV
;
2236 maxb
= INDEX(state
, maxv
, ui
->dragx_src
+dx
, ui
->dragy_src
+dy
);
2239 dx
= (nx
-ox
) < 0 ? -1 : 1;
2240 gtype
= G_LINEH
; ntype
= G_NOLINEH
; mtype
= G_MARKH
;
2241 maxb
= INDEX(state
, maxh
, ui
->dragx_src
+dx
, ui
->dragy_src
+dy
);
2243 if (ui
->drag_is_noline
) {
2246 curr
= GRID(state
, ui
->dragx_src
+dx
, ui
->dragy_src
+dy
);
2247 currl
= INDEX(state
, lines
, ui
->dragx_src
+dx
, ui
->dragy_src
+dy
);
2250 if (currl
== maxb
) {
2255 ui
->nlines
= currl
+ 1;
2263 /* ... and see if there's an island off in that direction. */
2264 is
= INDEX(state
, gridi
, ui
->dragx_src
, ui
->dragy_src
);
2265 for (i
= 0; i
< is
->adj
.npoints
; i
++) {
2266 if (is
->adj
.points
[i
].off
== 0) continue;
2267 curr
= GRID(state
, is
->x
+dx
, is
->y
+dy
);
2268 if (curr
& mtype
) continue; /* don't allow changes to marked lines. */
2269 if (ui
->drag_is_noline
) {
2270 if (curr
& gtype
) continue; /* no no-line where already a line */
2272 if (POSSIBLES(state
, dx
, is
->x
+dx
, is
->y
+dy
) == 0) continue; /* no line if !possible. */
2273 if (curr
& ntype
) continue; /* can't have a bridge where there's a no-line. */
2276 if (is
->adj
.points
[i
].dx
== dx
&&
2277 is
->adj
.points
[i
].dy
== dy
) {
2278 ui
->dragx_dst
= ISLAND_ORTHX(is
,i
);
2279 ui
->dragy_dst
= ISLAND_ORTHY(is
,i
);
2282 /*debug(("update_drag src (%d,%d) d(%d,%d) dst (%d,%d)\n",
2283 ui->dragx_src, ui->dragy_src, dx, dy,
2284 ui->dragx_dst, ui->dragy_dst));*/
2288 static char *finish_drag(const game_state
*state
, game_ui
*ui
)
2292 if (ui
->dragx_src
== -1 || ui
->dragy_src
== -1)
2294 if (ui
->dragx_dst
== -1 || ui
->dragy_dst
== -1)
2295 return ui_cancel_drag(ui
);
2297 if (ui
->drag_is_noline
) {
2298 sprintf(buf
, "N%d,%d,%d,%d",
2299 ui
->dragx_src
, ui
->dragy_src
,
2300 ui
->dragx_dst
, ui
->dragy_dst
);
2302 sprintf(buf
, "L%d,%d,%d,%d,%d",
2303 ui
->dragx_src
, ui
->dragy_src
,
2304 ui
->dragx_dst
, ui
->dragy_dst
, ui
->nlines
);
2312 static char *interpret_move(const game_state
*state
, game_ui
*ui
,
2313 const game_drawstate
*ds
,
2314 int x
, int y
, int button
)
2316 int gx
= FROMCOORD(x
), gy
= FROMCOORD(y
);
2318 grid_type ggrid
= INGRID(state
,gx
,gy
) ? GRID(state
,gx
,gy
) : 0;
2319 int shift
= button
& MOD_SHFT
, control
= button
& MOD_CTRL
;
2320 button
&= ~MOD_MASK
;
2322 if (button
== LEFT_BUTTON
|| button
== RIGHT_BUTTON
) {
2323 if (!INGRID(state
, gx
, gy
)) return NULL
;
2324 ui
->cur_visible
= 0;
2325 if (ggrid
& G_ISLAND
) {
2330 return ui_cancel_drag(ui
);
2331 } else if (button
== LEFT_DRAG
|| button
== RIGHT_DRAG
) {
2332 if (INGRID(state
, ui
->dragx_src
, ui
->dragy_src
)
2333 && (gx
!= ui
->dragx_src
|| gy
!= ui
->dragy_src
)
2334 && !(GRID(state
,ui
->dragx_src
,ui
->dragy_src
) & G_MARK
)) {
2336 ui
->drag_is_noline
= (button
== RIGHT_DRAG
) ? 1 : 0;
2337 return update_drag_dst(state
, ui
, ds
, x
, y
);
2339 /* cancel a drag when we go back to the starting point */
2344 } else if (button
== LEFT_RELEASE
|| button
== RIGHT_RELEASE
) {
2346 return finish_drag(state
, ui
);
2348 if (!INGRID(state
, ui
->dragx_src
, ui
->dragy_src
)
2349 || gx
!= ui
->dragx_src
|| gy
!= ui
->dragy_src
) {
2350 return ui_cancel_drag(ui
);
2353 if (!INGRID(state
, gx
, gy
)) return NULL
;
2354 if (!(GRID(state
, gx
, gy
) & G_ISLAND
)) return NULL
;
2355 sprintf(buf
, "M%d,%d", gx
, gy
);
2358 } else if (button
== 'h' || button
== 'H') {
2359 game_state
*solved
= dup_game(state
);
2360 solve_for_hint(solved
);
2361 ret
= game_state_diff(state
, solved
);
2364 } else if (IS_CURSOR_MOVE(button
)) {
2365 ui
->cur_visible
= 1;
2366 if (control
|| shift
) {
2367 ui
->dragx_src
= ui
->cur_x
;
2368 ui
->dragy_src
= ui
->cur_y
;
2369 ui
->dragging
= TRUE
;
2370 ui
->drag_is_noline
= !control
;
2373 int nx
= ui
->cur_x
, ny
= ui
->cur_y
;
2375 move_cursor(button
, &nx
, &ny
, state
->w
, state
->h
, 0);
2376 if (nx
== ui
->cur_x
&& ny
== ui
->cur_y
)
2378 update_drag_dst(state
, ui
, ds
,
2379 COORD(nx
)+TILE_SIZE
/2,
2380 COORD(ny
)+TILE_SIZE
/2);
2381 return finish_drag(state
, ui
);
2383 int dx
= (button
== CURSOR_RIGHT
) ? +1 : (button
== CURSOR_LEFT
) ? -1 : 0;
2384 int dy
= (button
== CURSOR_DOWN
) ? +1 : (button
== CURSOR_UP
) ? -1 : 0;
2385 int dorthx
= 1 - abs(dx
), dorthy
= 1 - abs(dy
);
2386 int dir
, orth
, nx
= x
, ny
= y
;
2388 /* 'orthorder' is a tweak to ensure that if you press RIGHT and
2389 * happen to move upwards, when you press LEFT you then tend
2390 * downwards (rather than upwards again). */
2391 int orthorder
= (button
== CURSOR_LEFT
|| button
== CURSOR_UP
) ? 1 : -1;
2393 /* This attempts to find an island in the direction you're
2394 * asking for, broadly speaking. If you ask to go right, for
2395 * example, it'll look for islands to the right and slightly
2396 * above or below your current horiz. position, allowing
2397 * further above/below the further away it searches. */
2399 assert(GRID(state
, ui
->cur_x
, ui
->cur_y
) & G_ISLAND
);
2400 /* currently this is depth-first (so orthogonally-adjacent
2401 * islands across the other side of the grid will be moved to
2402 * before closer islands slightly offset). Swap the order of
2403 * these two loops to change to breadth-first search. */
2404 for (orth
= 0; ; orth
++) {
2406 for (dir
= 1; ; dir
++) {
2409 if (orth
> dir
) continue; /* only search in cone outwards. */
2411 nx
= ui
->cur_x
+ dir
*dx
+ orth
*dorthx
*orthorder
;
2412 ny
= ui
->cur_y
+ dir
*dy
+ orth
*dorthy
*orthorder
;
2413 if (INGRID(state
, nx
, ny
)) {
2414 dingrid
= oingrid
= 1;
2415 if (GRID(state
, nx
, ny
) & G_ISLAND
) goto found
;
2418 nx
= ui
->cur_x
+ dir
*dx
- orth
*dorthx
*orthorder
;
2419 ny
= ui
->cur_y
+ dir
*dy
- orth
*dorthy
*orthorder
;
2420 if (INGRID(state
, nx
, ny
)) {
2421 dingrid
= oingrid
= 1;
2422 if (GRID(state
, nx
, ny
) & G_ISLAND
) goto found
;
2425 if (!dingrid
) break;
2427 if (!oingrid
) return "";
2436 } else if (IS_CURSOR_SELECT(button
)) {
2437 if (!ui
->cur_visible
) {
2438 ui
->cur_visible
= 1;
2441 if (ui
->dragging
|| button
== CURSOR_SELECT2
) {
2443 if (ui
->dragx_dst
== -1 && ui
->dragy_dst
== -1) {
2444 sprintf(buf
, "M%d,%d", ui
->cur_x
, ui
->cur_y
);
2449 grid_type v
= GRID(state
, ui
->cur_x
, ui
->cur_y
);
2452 ui
->dragx_src
= ui
->cur_x
;
2453 ui
->dragy_src
= ui
->cur_y
;
2454 ui
->dragx_dst
= ui
->dragy_dst
= -1;
2455 ui
->drag_is_noline
= (button
== CURSOR_SELECT2
) ? 1 : 0;
2459 } else if ((button
>= '0' && button
<= '9') ||
2460 (button
>= 'a' && button
<= 'f') ||
2461 (button
>= 'A' && button
<= 'F')) {
2462 /* jump to island with .count == number closest to cur_{x,y} */
2463 int best_x
= -1, best_y
= -1, best_sqdist
= -1, number
= -1, i
;
2465 if (button
>= '0' && button
<= '9')
2466 number
= (button
== '0' ? 16 : button
- '0');
2467 else if (button
>= 'a' && button
<= 'f')
2468 number
= 10 + button
- 'a';
2469 else if (button
>= 'A' && button
<= 'F')
2470 number
= 10 + button
- 'A';
2472 if (!ui
->cur_visible
) {
2473 ui
->cur_visible
= 1;
2477 for (i
= 0; i
< state
->n_islands
; ++i
) {
2478 int x
= state
->islands
[i
].x
, y
= state
->islands
[i
].y
;
2479 int dx
= x
- ui
->cur_x
, dy
= y
- ui
->cur_y
;
2480 int sqdist
= dx
*dx
+ dy
*dy
;
2482 if (state
->islands
[i
].count
!= number
)
2484 if (x
== ui
->cur_x
&& y
== ui
->cur_y
)
2487 /* new_game() reads the islands in row-major order, so by
2488 * breaking ties in favor of `first in state->islands' we
2489 * also break ties by `lexicographically smallest (y, x)'.
2490 * Thus, there's a stable pattern to how ties are broken
2491 * which the user can learn and use to navigate faster. */
2492 if (best_sqdist
== -1 || sqdist
< best_sqdist
) {
2495 best_sqdist
= sqdist
;
2498 if (best_x
!= -1 && best_y
!= -1) {
2504 } else if (button
== 'g' || button
== 'G') {
2505 ui
->show_hints
= 1 - ui
->show_hints
;
2512 static game_state
*execute_move(const game_state
*state
, const char *move
)
2514 game_state
*ret
= dup_game(state
);
2515 int x1
, y1
, x2
, y2
, nl
, n
;
2516 struct island
*is1
, *is2
;
2519 debug(("execute_move: %s\n", move
));
2521 if (!*move
) goto badmove
;
2527 } else if (c
== 'L') {
2528 if (sscanf(move
, "%d,%d,%d,%d,%d%n",
2529 &x1
, &y1
, &x2
, &y2
, &nl
, &n
) != 5)
2531 if (!INGRID(ret
, x1
, y1
) || !INGRID(ret
, x2
, y2
))
2533 is1
= INDEX(ret
, gridi
, x1
, y1
);
2534 is2
= INDEX(ret
, gridi
, x2
, y2
);
2535 if (!is1
|| !is2
) goto badmove
;
2536 if (nl
< 0 || nl
> state
->maxb
) goto badmove
;
2537 island_join(is1
, is2
, nl
, 0);
2538 } else if (c
== 'N') {
2539 if (sscanf(move
, "%d,%d,%d,%d%n",
2540 &x1
, &y1
, &x2
, &y2
, &n
) != 4)
2542 if (!INGRID(ret
, x1
, y1
) || !INGRID(ret
, x2
, y2
))
2544 is1
= INDEX(ret
, gridi
, x1
, y1
);
2545 is2
= INDEX(ret
, gridi
, x2
, y2
);
2546 if (!is1
|| !is2
) goto badmove
;
2547 island_join(is1
, is2
, -1, 0);
2548 } else if (c
== 'M') {
2549 if (sscanf(move
, "%d,%d%n",
2552 if (!INGRID(ret
, x1
, y1
))
2554 is1
= INDEX(ret
, gridi
, x1
, y1
);
2555 if (!is1
) goto badmove
;
2556 island_togglemark(is1
);
2563 else if (*move
) goto badmove
;
2566 map_update_possibles(ret
);
2567 if (map_check(ret
)) {
2568 debug(("Game completed.\n"));
2574 debug(("%s: unrecognised move.\n", move
));
2579 static char *solve_game(const game_state
*state
, const game_state
*currstate
,
2580 const char *aux
, char **error
)
2586 debug(("solve_game: aux = %s\n", aux
));
2587 solved
= execute_move(state
, aux
);
2589 *error
= "Generated aux string is not a valid move (!).";
2593 solved
= dup_game(state
);
2594 /* solve with max strength... */
2595 if (solve_from_scratch(solved
, 10) == 0) {
2597 *error
= "Game does not have a (non-recursive) solution.";
2601 ret
= game_state_diff(currstate
, solved
);
2603 debug(("solve_game: ret = %s\n", ret
));
2607 /* ----------------------------------------------------------------------
2611 static void game_compute_size(const game_params
*params
, int tilesize
,
2614 /* Ick: fake up `ds->tilesize' for macro expansion purposes */
2615 struct { int tilesize
; } ads
, *ds
= &ads
;
2616 ads
.tilesize
= tilesize
;
2618 *x
= TILE_SIZE
* params
->w
+ 2 * BORDER
;
2619 *y
= TILE_SIZE
* params
->h
+ 2 * BORDER
;
2622 static void game_set_size(drawing
*dr
, game_drawstate
*ds
,
2623 const game_params
*params
, int tilesize
)
2625 ds
->tilesize
= tilesize
;
2628 static float *game_colours(frontend
*fe
, int *ncolours
)
2630 float *ret
= snewn(3 * NCOLOURS
, float);
2633 game_mkhighlight(fe
, ret
, COL_BACKGROUND
, COL_HIGHLIGHT
, COL_LOWLIGHT
);
2635 for (i
= 0; i
< 3; i
++) {
2636 ret
[COL_FOREGROUND
* 3 + i
] = 0.0F
;
2637 ret
[COL_HINT
* 3 + i
] = ret
[COL_LOWLIGHT
* 3 + i
];
2638 ret
[COL_GRID
* 3 + i
] =
2639 (ret
[COL_HINT
* 3 + i
] + ret
[COL_BACKGROUND
* 3 + i
]) * 0.5F
;
2640 ret
[COL_MARK
* 3 + i
] = ret
[COL_HIGHLIGHT
* 3 + i
];
2642 ret
[COL_WARNING
* 3 + 0] = 1.0F
;
2643 ret
[COL_WARNING
* 3 + 1] = 0.25F
;
2644 ret
[COL_WARNING
* 3 + 2] = 0.25F
;
2646 ret
[COL_SELECTED
* 3 + 0] = 0.25F
;
2647 ret
[COL_SELECTED
* 3 + 1] = 1.00F
;
2648 ret
[COL_SELECTED
* 3 + 2] = 0.25F
;
2650 ret
[COL_CURSOR
* 3 + 0] = min(ret
[COL_BACKGROUND
* 3 + 0] * 1.4F
, 1.0F
);
2651 ret
[COL_CURSOR
* 3 + 1] = ret
[COL_BACKGROUND
* 3 + 1] * 0.8F
;
2652 ret
[COL_CURSOR
* 3 + 2] = ret
[COL_BACKGROUND
* 3 + 2] * 0.8F
;
2654 *ncolours
= NCOLOURS
;
2658 static game_drawstate
*game_new_drawstate(drawing
*dr
, const game_state
*state
)
2660 struct game_drawstate
*ds
= snew(struct game_drawstate
);
2661 int wh
= state
->w
*state
->h
;
2669 ds
->grid
= snewn(wh
, unsigned long);
2670 for (i
= 0; i
< wh
; i
++)
2672 ds
->newgrid
= snewn(wh
, unsigned long);
2673 ds
->lv
= snewn(wh
, int);
2674 ds
->lh
= snewn(wh
, int);
2675 memset(ds
->lv
, 0, wh
*sizeof(int));
2676 memset(ds
->lh
, 0, wh
*sizeof(int));
2681 static void game_free_drawstate(drawing
*dr
, game_drawstate
*ds
)
2690 #define LINE_WIDTH (TILE_SIZE/8)
2691 #define TS8(x) (((x)*TILE_SIZE)/8)
2693 #define OFFSET(thing) ((TILE_SIZE/2) - ((thing)/2))
2695 static int between_island(const game_state
*state
, int sx
, int sy
,
2698 int x
= sx
- dx
, y
= sy
- dy
;
2700 while (INGRID(state
, x
, y
)) {
2701 if (GRID(state
, x
, y
) & G_ISLAND
) goto found
;
2706 x
= sx
+ dx
, y
= sy
+ dy
;
2707 while (INGRID(state
, x
, y
)) {
2708 if (GRID(state
, x
, y
) & G_ISLAND
) return 1;
2714 static void lines_lvlh(const game_state
*state
, const game_ui
*ui
,
2715 int x
, int y
, grid_type v
, int *lv_r
, int *lh_r
)
2719 if (v
& G_LINEV
) lv
= INDEX(state
,lines
,x
,y
);
2720 if (v
& G_LINEH
) lh
= INDEX(state
,lines
,x
,y
);
2722 if (ui
->show_hints
) {
2723 if (between_island(state
, x
, y
, 0, 1) && !lv
) lv
= 1;
2724 if (between_island(state
, x
, y
, 1, 0) && !lh
) lh
= 1;
2726 /*debug(("lvlh: (%d,%d) v 0x%x lv %d lh %d.\n", x, y, v, lv, lh));*/
2727 *lv_r
= lv
; *lh_r
= lh
;
2730 static void draw_cross(drawing
*dr
, game_drawstate
*ds
,
2731 int ox
, int oy
, int col
)
2734 draw_line(dr
, ox
, oy
, ox
+off
, oy
+off
, col
);
2735 draw_line(dr
, ox
+off
, oy
, ox
, oy
+off
, col
);
2738 static void draw_general_line(drawing
*dr
, game_drawstate
*ds
,
2739 int ox
, int oy
, int fx
, int fy
, int ax
, int ay
,
2740 int len
, unsigned long ldata
, int which
)
2743 * Draw one direction of lines in a square. To permit the same
2744 * code to handle horizontal and vertical lines, fx,fy are the
2745 * 'forward' direction (along the lines) and ax,ay are the
2746 * 'across' direction.
2748 * We draw the white background for a locked bridge if (which &
2749 * 1), and draw the bridges themselves if (which & 2). This
2750 * permits us to get two overlapping locked bridges right without
2751 * one of them erasing part of the other.
2755 fg
= ((ldata
& DL_COUNTMASK
) == DL_COUNT_HINT
? COL_HINT
:
2756 (ldata
& DL_COLMASK
) == DL_COL_SELECTED
? COL_SELECTED
:
2757 (ldata
& DL_COLMASK
) == DL_COL_FLASH
? COL_HIGHLIGHT
:
2758 (ldata
& DL_COLMASK
) == DL_COL_WARNING
? COL_WARNING
:
2761 if ((ldata
& DL_COUNTMASK
) == DL_COUNT_CROSS
) {
2763 ox
+ TS8(1)*fx
+ TS8(3)*ax
,
2764 oy
+ TS8(1)*fy
+ TS8(3)*ay
, fg
);
2766 ox
+ TS8(5)*fx
+ TS8(3)*ax
,
2767 oy
+ TS8(5)*fy
+ TS8(3)*ay
, fg
);
2768 } else if ((ldata
& DL_COUNTMASK
) != 0) {
2769 int lh
, lw
, gw
, bw
, i
, loff
;
2771 lh
= (ldata
& DL_COUNTMASK
);
2772 if (lh
== DL_COUNT_HINT
)
2775 lw
= gw
= LINE_WIDTH
;
2776 while ((bw
= lw
* lh
+ gw
* (lh
+1)) > TILE_SIZE
)
2782 if ((ldata
& DL_LOCK
) && fg
!= COL_HINT
)
2783 draw_rect(dr
, ox
+ loff
*ax
, oy
+ loff
*ay
,
2784 len
*fx
+bw
*ax
, len
*fy
+bw
*ay
, COL_MARK
);
2787 for (i
= 0; i
< lh
; i
++, loff
+= lw
+ gw
)
2788 draw_rect(dr
, ox
+ (loff
+gw
)*ax
, oy
+ (loff
+gw
)*ay
,
2789 len
*fx
+lw
*ax
, len
*fy
+lw
*ay
, fg
);
2794 static void draw_hline(drawing
*dr
, game_drawstate
*ds
,
2795 int ox
, int oy
, int w
, unsigned long vdata
, int which
)
2797 draw_general_line(dr
, ds
, ox
, oy
, 1, 0, 0, 1, w
, vdata
, which
);
2800 static void draw_vline(drawing
*dr
, game_drawstate
*ds
,
2801 int ox
, int oy
, int h
, unsigned long vdata
, int which
)
2803 draw_general_line(dr
, ds
, ox
, oy
, 0, 1, 1, 0, h
, vdata
, which
);
2806 #define ISLAND_RADIUS ((TILE_SIZE*12)/20)
2807 #define ISLAND_NUMSIZE(clue) \
2808 (((clue) < 10) ? (TILE_SIZE*7)/10 : (TILE_SIZE*5)/10)
2810 static void draw_island(drawing
*dr
, game_drawstate
*ds
,
2811 int ox
, int oy
, int clue
, unsigned long idata
)
2813 int half
, orad
, irad
, fg
, bg
;
2815 if ((idata
& DI_BGMASK
) == DI_BG_NO_ISLAND
)
2819 orad
= ISLAND_RADIUS
;
2820 irad
= orad
- LINE_WIDTH
;
2821 fg
= ((idata
& DI_COLMASK
) == DI_COL_SELECTED
? COL_SELECTED
:
2822 (idata
& DI_COLMASK
) == DI_COL_WARNING
? COL_WARNING
:
2823 (idata
& DI_COLMASK
) == DI_COL_FLASH
? COL_HIGHLIGHT
:
2825 bg
= ((idata
& DI_BGMASK
) == DI_BG_CURSOR
? COL_CURSOR
:
2826 (idata
& DI_BGMASK
) == DI_BG_MARK
? COL_MARK
:
2829 /* draw a thick circle */
2830 draw_circle(dr
, ox
+half
, oy
+half
, orad
, fg
, fg
);
2831 draw_circle(dr
, ox
+half
, oy
+half
, irad
, bg
, bg
);
2835 int textcolour
= (fg
== COL_SELECTED
? COL_FOREGROUND
: fg
);
2836 sprintf(str
, "%d", clue
);
2837 draw_text(dr
, ox
+half
, oy
+half
, FONT_VARIABLE
, ISLAND_NUMSIZE(clue
),
2838 ALIGN_VCENTRE
| ALIGN_HCENTRE
, textcolour
, str
);
2842 static void draw_island_tile(drawing
*dr
, game_drawstate
*ds
,
2843 int x
, int y
, int clue
, unsigned long data
)
2845 int ox
= COORD(x
), oy
= COORD(y
);
2848 clip(dr
, ox
, oy
, TILE_SIZE
, TILE_SIZE
);
2849 draw_rect(dr
, ox
, oy
, TILE_SIZE
, TILE_SIZE
, COL_BACKGROUND
);
2852 * Because of the possibility of incoming bridges just about
2853 * meeting at one corner, we must split the line-drawing into
2854 * background and foreground segments.
2856 for (which
= 1; which
<= 2; which
<<= 1) {
2857 draw_hline(dr
, ds
, ox
, oy
, TILE_SIZE
/2,
2858 (data
>> D_I_LINE_SHIFT_L
) & DL_MASK
, which
);
2859 draw_hline(dr
, ds
, ox
+ TILE_SIZE
- TILE_SIZE
/2, oy
, TILE_SIZE
/2,
2860 (data
>> D_I_LINE_SHIFT_R
) & DL_MASK
, which
);
2861 draw_vline(dr
, ds
, ox
, oy
, TILE_SIZE
/2,
2862 (data
>> D_I_LINE_SHIFT_U
) & DL_MASK
, which
);
2863 draw_vline(dr
, ds
, ox
, oy
+ TILE_SIZE
- TILE_SIZE
/2, TILE_SIZE
/2,
2864 (data
>> D_I_LINE_SHIFT_D
) & DL_MASK
, which
);
2866 draw_island(dr
, ds
, ox
, oy
, clue
, (data
>> D_I_ISLAND_SHIFT
) & DI_MASK
);
2869 draw_update(dr
, ox
, oy
, TILE_SIZE
, TILE_SIZE
);
2872 static void draw_line_tile(drawing
*dr
, game_drawstate
*ds
,
2873 int x
, int y
, unsigned long data
)
2875 int ox
= COORD(x
), oy
= COORD(y
);
2876 unsigned long hdata
, vdata
;
2878 clip(dr
, ox
, oy
, TILE_SIZE
, TILE_SIZE
);
2879 draw_rect(dr
, ox
, oy
, TILE_SIZE
, TILE_SIZE
, COL_BACKGROUND
);
2882 * We have to think about which of the horizontal and vertical
2883 * line to draw first, if both exist.
2885 * The rule is that hint lines are drawn at the bottom, then
2886 * NOLINE crosses, then actual bridges. The enumeration in the
2887 * DL_COUNTMASK field is set up so that this drops out of a
2888 * straight comparison between the two.
2890 * Since lines crossing in this type of square cannot both be
2891 * actual bridges, there's no need to pass a nontrivial 'which'
2892 * parameter to draw_[hv]line.
2894 hdata
= (data
>> D_L_LINE_SHIFT_H
) & DL_MASK
;
2895 vdata
= (data
>> D_L_LINE_SHIFT_V
) & DL_MASK
;
2896 if ((hdata
& DL_COUNTMASK
) > (vdata
& DL_COUNTMASK
)) {
2897 draw_hline(dr
, ds
, ox
, oy
, TILE_SIZE
, hdata
, 3);
2898 draw_vline(dr
, ds
, ox
, oy
, TILE_SIZE
, vdata
, 3);
2900 draw_vline(dr
, ds
, ox
, oy
, TILE_SIZE
, vdata
, 3);
2901 draw_hline(dr
, ds
, ox
, oy
, TILE_SIZE
, hdata
, 3);
2905 * The islands drawn at the edges of a line tile don't need clue
2908 draw_island(dr
, ds
, ox
- TILE_SIZE
, oy
, -1,
2909 (data
>> D_L_ISLAND_SHIFT_L
) & DI_MASK
);
2910 draw_island(dr
, ds
, ox
+ TILE_SIZE
, oy
, -1,
2911 (data
>> D_L_ISLAND_SHIFT_R
) & DI_MASK
);
2912 draw_island(dr
, ds
, ox
, oy
- TILE_SIZE
, -1,
2913 (data
>> D_L_ISLAND_SHIFT_U
) & DI_MASK
);
2914 draw_island(dr
, ds
, ox
, oy
+ TILE_SIZE
, -1,
2915 (data
>> D_L_ISLAND_SHIFT_D
) & DI_MASK
);
2918 draw_update(dr
, ox
, oy
, TILE_SIZE
, TILE_SIZE
);
2921 static void draw_edge_tile(drawing
*dr
, game_drawstate
*ds
,
2922 int x
, int y
, int dx
, int dy
, unsigned long data
)
2924 int ox
= COORD(x
), oy
= COORD(y
);
2925 int cx
= ox
, cy
= oy
, cw
= TILE_SIZE
, ch
= TILE_SIZE
;
2936 clip(dr
, cx
, cy
, cw
, ch
);
2937 draw_rect(dr
, cx
, cy
, cw
, ch
, COL_BACKGROUND
);
2939 draw_island(dr
, ds
, ox
+ TILE_SIZE
*dx
, oy
+ TILE_SIZE
*dy
, -1,
2940 (data
>> D_I_ISLAND_SHIFT
) & DI_MASK
);
2943 draw_update(dr
, cx
, cy
, cw
, ch
);
2946 static void game_redraw(drawing
*dr
, game_drawstate
*ds
,
2947 const game_state
*oldstate
, const game_state
*state
,
2948 int dir
, const game_ui
*ui
,
2949 float animtime
, float flashtime
)
2952 grid_type v
, flash
= 0;
2953 struct island
*is
, *is_drag_src
= NULL
, *is_drag_dst
= NULL
;
2956 int f
= (int)(flashtime
* 5 / FLASH_TIME
);
2957 if (f
== 1 || f
== 3) flash
= TRUE
;
2960 /* Clear screen, if required. */
2963 TILE_SIZE
* ds
->w
+ 2 * BORDER
,
2964 TILE_SIZE
* ds
->h
+ 2 * BORDER
, COL_BACKGROUND
);
2966 draw_rect_outline(dr
,
2967 COORD(0)-1, COORD(0)-1,
2968 TILE_SIZE
* ds
->w
+ 2, TILE_SIZE
* ds
->h
+ 2,
2971 draw_update(dr
, 0, 0,
2972 TILE_SIZE
* ds
->w
+ 2 * BORDER
,
2973 TILE_SIZE
* ds
->h
+ 2 * BORDER
);
2977 if (ui
->dragx_src
!= -1 && ui
->dragy_src
!= -1) {
2979 is_drag_src
= INDEX(state
, gridi
, ui
->dragx_src
, ui
->dragy_src
);
2980 assert(is_drag_src
);
2981 if (ui
->dragx_dst
!= -1 && ui
->dragy_dst
!= -1) {
2982 is_drag_dst
= INDEX(state
, gridi
, ui
->dragx_dst
, ui
->dragy_dst
);
2983 assert(is_drag_dst
);
2989 * Set up ds->newgrid with the current grid contents.
2991 for (x
= 0; x
< ds
->w
; x
++)
2992 for (y
= 0; y
< ds
->h
; y
++)
2993 INDEX(ds
,newgrid
,x
,y
) = 0;
2995 for (x
= 0; x
< ds
->w
; x
++) {
2996 for (y
= 0; y
< ds
->h
; y
++) {
2997 v
= GRID(state
, x
, y
);
3001 * An island square. Compute the drawing data for the
3002 * island, and put it in this square and surrounding
3005 unsigned long idata
= 0;
3007 is
= INDEX(state
, gridi
, x
, y
);
3010 idata
|= DI_COL_FLASH
;
3011 if (is_drag_src
&& (is
== is_drag_src
||
3012 (is_drag_dst
&& is
== is_drag_dst
)))
3013 idata
|= DI_COL_SELECTED
;
3014 else if (island_impossible(is
, v
& G_MARK
) || (v
& G_WARN
))
3015 idata
|= DI_COL_WARNING
;
3017 idata
|= DI_COL_NORMAL
;
3019 if (ui
->cur_visible
&&
3020 ui
->cur_x
== is
->x
&& ui
->cur_y
== is
->y
)
3021 idata
|= DI_BG_CURSOR
;
3022 else if (v
& G_MARK
)
3023 idata
|= DI_BG_MARK
;
3025 idata
|= DI_BG_NORMAL
;
3027 INDEX(ds
,newgrid
,x
,y
) |= idata
<< D_I_ISLAND_SHIFT
;
3028 if (x
> 0 && !(GRID(state
,x
-1,y
) & G_ISLAND
))
3029 INDEX(ds
,newgrid
,x
-1,y
) |= idata
<< D_L_ISLAND_SHIFT_R
;
3030 if (x
+1 < state
->w
&& !(GRID(state
,x
+1,y
) & G_ISLAND
))
3031 INDEX(ds
,newgrid
,x
+1,y
) |= idata
<< D_L_ISLAND_SHIFT_L
;
3032 if (y
> 0 && !(GRID(state
,x
,y
-1) & G_ISLAND
))
3033 INDEX(ds
,newgrid
,x
,y
-1) |= idata
<< D_L_ISLAND_SHIFT_D
;
3034 if (y
+1 < state
->h
&& !(GRID(state
,x
,y
+1) & G_ISLAND
))
3035 INDEX(ds
,newgrid
,x
,y
+1) |= idata
<< D_L_ISLAND_SHIFT_U
;
3037 unsigned long hdata
, vdata
;
3038 int selh
= FALSE
, selv
= FALSE
;
3041 * A line (non-island) square. Compute the drawing
3042 * data for any horizontal and vertical lines in the
3043 * square, and put them in this square's entry and
3044 * optionally those for neighbouring islands too.
3048 WITHIN(x
,is_drag_src
->x
, is_drag_dst
->x
) &&
3049 WITHIN(y
,is_drag_src
->y
, is_drag_dst
->y
)) {
3050 if (is_drag_src
->x
!= is_drag_dst
->x
)
3055 lines_lvlh(state
, ui
, x
, y
, v
, &lv
, &lh
);
3057 hdata
= (v
& G_NOLINEH
? DL_COUNT_CROSS
:
3060 between_island(state
,x
,y
,1,0)) ? DL_COUNT_HINT
: 0);
3061 vdata
= (v
& G_NOLINEV
? DL_COUNT_CROSS
:
3064 between_island(state
,x
,y
,0,1)) ? DL_COUNT_HINT
: 0);
3066 hdata
|= (flash
? DL_COL_FLASH
:
3067 v
& G_WARN
? DL_COL_WARNING
:
3068 selh
? DL_COL_SELECTED
:
3070 vdata
|= (flash
? DL_COL_FLASH
:
3071 v
& G_WARN
? DL_COL_WARNING
:
3072 selv
? DL_COL_SELECTED
:
3080 INDEX(ds
,newgrid
,x
,y
) |= hdata
<< D_L_LINE_SHIFT_H
;
3081 INDEX(ds
,newgrid
,x
,y
) |= vdata
<< D_L_LINE_SHIFT_V
;
3082 if (x
> 0 && (GRID(state
,x
-1,y
) & G_ISLAND
))
3083 INDEX(ds
,newgrid
,x
-1,y
) |= hdata
<< D_I_LINE_SHIFT_R
;
3084 if (x
+1 < state
->w
&& (GRID(state
,x
+1,y
) & G_ISLAND
))
3085 INDEX(ds
,newgrid
,x
+1,y
) |= hdata
<< D_I_LINE_SHIFT_L
;
3086 if (y
> 0 && (GRID(state
,x
,y
-1) & G_ISLAND
))
3087 INDEX(ds
,newgrid
,x
,y
-1) |= vdata
<< D_I_LINE_SHIFT_D
;
3088 if (y
+1 < state
->h
&& (GRID(state
,x
,y
+1) & G_ISLAND
))
3089 INDEX(ds
,newgrid
,x
,y
+1) |= vdata
<< D_I_LINE_SHIFT_U
;
3095 * Now go through and draw any changed grid square.
3097 for (x
= 0; x
< ds
->w
; x
++) {
3098 for (y
= 0; y
< ds
->h
; y
++) {
3099 unsigned long newval
= INDEX(ds
,newgrid
,x
,y
);
3100 if (INDEX(ds
,grid
,x
,y
) != newval
) {
3101 v
= GRID(state
, x
, y
);
3103 is
= INDEX(state
, gridi
, x
, y
);
3104 draw_island_tile(dr
, ds
, x
, y
, is
->count
, newval
);
3107 * If this tile is right at the edge of the grid,
3108 * we must also draw the part of the island that
3109 * goes completely out of bounds. We don't bother
3110 * keeping separate entries in ds->newgrid for
3111 * these tiles; it's easier just to redraw them
3112 * iff we redraw their parent island tile.
3115 draw_edge_tile(dr
, ds
, x
-1, y
, +1, 0, newval
);
3117 draw_edge_tile(dr
, ds
, x
, y
-1, 0, +1, newval
);
3118 if (x
== state
->w
-1)
3119 draw_edge_tile(dr
, ds
, x
+1, y
, -1, 0, newval
);
3120 if (y
== state
->h
-1)
3121 draw_edge_tile(dr
, ds
, x
, y
+1, 0, -1, newval
);
3123 draw_line_tile(dr
, ds
, x
, y
, newval
);
3125 INDEX(ds
,grid
,x
,y
) = newval
;
3131 static float game_anim_length(const game_state
*oldstate
,
3132 const game_state
*newstate
, int dir
, game_ui
*ui
)
3137 static float game_flash_length(const game_state
*oldstate
,
3138 const game_state
*newstate
, int dir
, game_ui
*ui
)
3140 if (!oldstate
->completed
&& newstate
->completed
&&
3141 !oldstate
->solved
&& !newstate
->solved
)
3147 static int game_status(const game_state
*state
)
3149 return state
->completed
? +1 : 0;
3152 static int game_timing_state(const game_state
*state
, game_ui
*ui
)
3157 static void game_print_size(const game_params
*params
, float *x
, float *y
)
3161 /* 10mm squares by default. */
3162 game_compute_size(params
, 1000, &pw
, &ph
);
3167 static void game_print(drawing
*dr
, const game_state
*state
, int ts
)
3169 int ink
= print_mono_colour(dr
, 0);
3170 int paper
= print_mono_colour(dr
, 1);
3171 int x
, y
, cx
, cy
, i
, nl
;
3175 /* Ick: fake up `ds->tilesize' for macro expansion purposes */
3176 game_drawstate ads
, *ds
= &ads
;
3179 /* I don't think this wants a border. */
3182 loff
= ts
/ (8 * sqrt((state
->params
.maxb
- 1)));
3183 print_line_width(dr
, ts
/ 12);
3184 for (x
= 0; x
< state
->w
; x
++) {
3185 for (y
= 0; y
< state
->h
; y
++) {
3186 cx
= COORD(x
); cy
= COORD(y
);
3187 grid
= GRID(state
,x
,y
);
3188 nl
= INDEX(state
,lines
,x
,y
);
3190 if (grid
& G_ISLAND
) continue;
3191 if (grid
& G_LINEV
) {
3192 for (i
= 0; i
< nl
; i
++)
3193 draw_line(dr
, cx
+ts
/2+(2*i
-nl
+1)*loff
, cy
,
3194 cx
+ts
/2+(2*i
-nl
+1)*loff
, cy
+ts
, ink
);
3196 if (grid
& G_LINEH
) {
3197 for (i
= 0; i
< nl
; i
++)
3198 draw_line(dr
, cx
, cy
+ts
/2+(2*i
-nl
+1)*loff
,
3199 cx
+ts
, cy
+ts
/2+(2*i
-nl
+1)*loff
, ink
);
3205 for (i
= 0; i
< state
->n_islands
; i
++) {
3207 struct island
*is
= &state
->islands
[i
];
3208 grid
= GRID(state
, is
->x
, is
->y
);
3209 cx
= COORD(is
->x
) + ts
/2;
3210 cy
= COORD(is
->y
) + ts
/2;
3212 draw_circle(dr
, cx
, cy
, ISLAND_RADIUS
, paper
, ink
);
3214 sprintf(str
, "%d", is
->count
);
3215 draw_text(dr
, cx
, cy
, FONT_VARIABLE
, ISLAND_NUMSIZE(is
->count
),
3216 ALIGN_VCENTRE
| ALIGN_HCENTRE
, ink
, str
);
3221 #define thegame bridges
3224 const struct game thegame
= {
3225 "Bridges", "games.bridges", "bridges",
3227 game_fetch_preset
, NULL
,
3232 TRUE
, game_configure
, custom_params
,
3240 TRUE
, game_can_format_as_text_now
, game_text_format
,
3248 PREFERRED_TILE_SIZE
, game_compute_size
, game_set_size
,
3251 game_free_drawstate
,
3256 TRUE
, FALSE
, game_print_size
, game_print
,
3257 FALSE
, /* wants_statusbar */
3258 FALSE
, game_timing_state
,
3259 REQUIRE_RBUTTON
, /* flags */
3262 /* vim: set shiftwidth=4 tabstop=8: */