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. */
83 /* --- structures for params, state, etc. --- */
87 #define PREFERRED_TILE_SIZE 24
88 #define TILE_SIZE (ds->tilesize)
89 #define BORDER (TILE_SIZE / 2)
91 #define COORD(x) ( (x) * TILE_SIZE + BORDER )
92 #define FROMCOORD(x) ( ((x) - BORDER + TILE_SIZE) / TILE_SIZE - 1 )
94 #define FLASH_TIME 0.50F
99 COL_HIGHLIGHT
, COL_LOWLIGHT
,
100 COL_SELECTED
, COL_MARK
,
109 int islands
, expansion
; /* %age of island squares, %age chance of expansion */
110 int allowloops
, difficulty
;
113 /* general flags used by all structs */
114 #define G_ISLAND 0x0001
115 #define G_LINEV 0x0002 /* contains a vert. line */
116 #define G_LINEH 0x0004 /* contains a horiz. line (mutex with LINEV) */
117 #define G_LINE (G_LINEV|G_LINEH)
118 #define G_MARKV 0x0008
119 #define G_MARKH 0x0010
120 #define G_MARK (G_MARKV|G_MARKH)
121 #define G_NOLINEV 0x0020
122 #define G_NOLINEH 0x0040
123 #define G_NOLINE (G_NOLINEV|G_NOLINEH)
125 /* flags used by the drawstate */
126 #define G_ISSEL 0x0080
127 #define G_REDRAW 0x0100
128 #define G_FLASH 0x0200
129 #define G_WARN 0x0400
130 #define G_CURSOR 0x0800
132 /* flags used by the solver etc. */
133 #define G_SWEEP 0x1000
135 #define G_FLAGSH (G_LINEH|G_MARKH|G_NOLINEH)
136 #define G_FLAGSV (G_LINEV|G_MARKV|G_NOLINEV)
138 typedef unsigned int grid_type
; /* change me later if we invent > 16 bits of flags. */
140 struct solver_state
{
141 int *dsf
, *comptspaces
;
142 int *tmpdsf
, *tmpcompspaces
;
146 /* state->gridi is an optimisation; it stores the pointer to the island
147 * structs indexed by (x,y). It's not strictly necessary (we could use
148 * find234 instead), but Purify showed that board generation (mostly the solver)
149 * was spending 60% of its time in find234. */
151 struct surrounds
{ /* cloned from lightup.c */
152 struct { int x
, y
, dx
, dy
, off
; } points
[4];
153 int npoints
, nislands
;
159 struct surrounds adj
;
163 int w
, h
, completed
, solved
, allowloops
, maxb
;
164 grid_type
*grid
, *scratch
;
165 struct island
*islands
;
166 int n_islands
, n_islands_alloc
;
167 game_params params
; /* used by the aux solver. */
168 #define N_WH_ARRAYS 5
169 char *wha
, *possv
, *possh
, *lines
, *maxv
, *maxh
;
170 struct island
**gridi
;
171 struct solver_state
*solver
; /* refcounted */
174 #define GRIDSZ(s) ((s)->w * (s)->h * sizeof(grid_type))
176 #define INGRID(s,x,y) ((x) >= 0 && (x) < (s)->w && (y) >= 0 && (y) < (s)->h)
178 #define DINDEX(x,y) ((y)*state->w + (x))
180 #define INDEX(s,g,x,y) ((s)->g[(y)*((s)->w) + (x)])
181 #define IDX(s,g,i) ((s)->g[(i)])
182 #define GRID(s,x,y) INDEX(s,grid,x,y)
183 #define SCRATCH(s,x,y) INDEX(s,scratch,x,y)
184 #define POSSIBLES(s,dx,x,y) ((dx) ? (INDEX(s,possh,x,y)) : (INDEX(s,possv,x,y)))
185 #define MAXIMUM(s,dx,x,y) ((dx) ? (INDEX(s,maxh,x,y)) : (INDEX(s,maxv,x,y)))
187 #define GRIDCOUNT(s,x,y,f) ((GRID(s,x,y) & (f)) ? (INDEX(s,lines,x,y)) : 0)
189 #define WITHIN2(x,min,max) (((x) < (min)) ? 0 : (((x) > (max)) ? 0 : 1))
190 #define WITHIN(x,min,max) ((min) > (max) ? \
191 WITHIN2(x,max,min) : WITHIN2(x,min,max))
193 /* --- island struct and tree support functions --- */
195 #define ISLAND_ORTH(is,j,f,df) \
196 (is->f + (is->adj.points[(j)].off*is->adj.points[(j)].df))
198 #define ISLAND_ORTHX(is,j) ISLAND_ORTH(is,j,x,dx)
199 #define ISLAND_ORTHY(is,j) ISLAND_ORTH(is,j,y,dy)
201 static void fixup_islands_for_realloc(game_state
*state
)
205 for (i
= 0; i
< state
->w
*state
->h
; i
++) state
->gridi
[i
] = NULL
;
206 for (i
= 0; i
< state
->n_islands
; i
++) {
207 struct island
*is
= &state
->islands
[i
];
209 INDEX(state
, gridi
, is
->x
, is
->y
) = is
;
213 static int game_can_format_as_text_now(game_params
*params
)
218 static char *game_text_format(game_state
*state
)
225 len
= (state
->h
) * (state
->w
+1) + 1;
226 ret
= snewn(len
, char);
229 for (y
= 0; y
< state
->h
; y
++) {
230 for (x
= 0; x
< state
->w
; x
++) {
231 grid
= GRID(state
,x
,y
);
232 nl
= INDEX(state
,lines
,x
,y
);
233 is
= INDEX(state
, gridi
, x
, y
);
235 *p
++ = '0' + is
->count
;
236 } else if (grid
& G_LINEV
) {
237 *p
++ = (nl
> 1) ?
'"' : (nl
== 1) ?
'|' : '!'; /* gaah, want a double-bar. */
238 } else if (grid
& G_LINEH
) {
239 *p
++ = (nl
> 1) ?
'=' : (nl
== 1) ?
'-' : '~';
248 assert(p
- ret
== len
);
252 static void debug_state(game_state
*state
)
254 char *textversion
= game_text_format(state
);
255 debug(("%s", textversion
));
259 /*static void debug_possibles(game_state *state)
262 debug(("possh followed by possv\n"));
263 for (y = 0; y < state->h; y++) {
264 for (x = 0; x < state->w; x++) {
265 debug(("%d", POSSIBLES(state, 1, x, y)));
268 for (x = 0; x < state->w; x++) {
269 debug(("%d", POSSIBLES(state, 0, x, y)));
274 for (y = 0; y < state->h; y++) {
275 for (x = 0; x < state->w; x++) {
276 debug(("%d", MAXIMUM(state, 1, x, y)));
279 for (x = 0; x < state->w; x++) {
280 debug(("%d", MAXIMUM(state, 0, x, y)));
287 static void island_set_surrounds(struct island
*is
)
289 assert(INGRID(is
->state
,is
->x
,is
->y
));
290 is
->adj
.npoints
= is
->adj
.nislands
= 0;
291 #define ADDPOINT(cond,ddx,ddy) do {\
293 is->adj.points[is->adj.npoints].x = is->x+(ddx); \
294 is->adj.points[is->adj.npoints].y = is->y+(ddy); \
295 is->adj.points[is->adj.npoints].dx = (ddx); \
296 is->adj.points[is->adj.npoints].dy = (ddy); \
297 is->adj.points[is->adj.npoints].off = 0; \
300 ADDPOINT(is
->x
> 0, -1, 0);
301 ADDPOINT(is
->x
< (is
->state
->w
-1), +1, 0);
302 ADDPOINT(is
->y
> 0, 0, -1);
303 ADDPOINT(is
->y
< (is
->state
->h
-1), 0, +1);
306 static void island_find_orthogonal(struct island
*is
)
308 /* fills in the rest of the 'surrounds' structure, assuming
309 * all other islands are now in place. */
310 int i
, x
, y
, dx
, dy
, off
;
312 is
->adj
.nislands
= 0;
313 for (i
= 0; i
< is
->adj
.npoints
; i
++) {
314 dx
= is
->adj
.points
[i
].dx
;
315 dy
= is
->adj
.points
[i
].dy
;
319 is
->adj
.points
[i
].off
= 0;
320 while (INGRID(is
->state
, x
, y
)) {
321 if (GRID(is
->state
, x
, y
) & G_ISLAND
) {
322 is
->adj
.points
[i
].off
= off
;
324 /*debug(("island (%d,%d) has orth is. %d*(%d,%d) away at (%d,%d).\n",
325 is->x, is->y, off, dx, dy,
326 ISLAND_ORTHX(is,i), ISLAND_ORTHY(is,i)));*/
329 off
++; x
+= dx
; y
+= dy
;
336 static int island_hasbridge(struct island
*is
, int direction
)
338 int x
= is
->adj
.points
[direction
].x
;
339 int y
= is
->adj
.points
[direction
].y
;
340 grid_type gline
= is
->adj
.points
[direction
].dx ? G_LINEH
: G_LINEV
;
342 if (GRID(is
->state
, x
, y
) & gline
) return 1;
346 static struct island
*island_find_connection(struct island
*is
, int adjpt
)
350 assert(adjpt
< is
->adj
.npoints
);
351 if (!is
->adj
.points
[adjpt
].off
) return NULL
;
352 if (!island_hasbridge(is
, adjpt
)) return NULL
;
354 is_r
= INDEX(is
->state
, gridi
,
355 ISLAND_ORTHX(is
, adjpt
), ISLAND_ORTHY(is
, adjpt
));
361 static struct island
*island_add(game_state
*state
, int x
, int y
, int count
)
366 assert(!(GRID(state
,x
,y
) & G_ISLAND
));
367 GRID(state
,x
,y
) |= G_ISLAND
;
370 if (state
->n_islands
> state
->n_islands_alloc
) {
371 state
->n_islands_alloc
= state
->n_islands
* 2;
373 sresize(state
->islands
, state
->n_islands_alloc
, struct island
);
376 is
= &state
->islands
[state
->n_islands
-1];
378 memset(is
, 0, sizeof(struct island
));
383 island_set_surrounds(is
);
386 fixup_islands_for_realloc(state
);
388 INDEX(state
, gridi
, x
, y
) = is
;
394 /* n = -1 means 'flip NOLINE flags [and set line to 0].' */
395 static void island_join(struct island
*i1
, struct island
*i2
, int n
, int is_max
)
397 game_state
*state
= i1
->state
;
400 assert(i1
->state
== i2
->state
);
401 assert(n
>= -1 && n
<= i1
->state
->maxb
);
403 if (i1
->x
== i2
->x
) {
406 s
= i1
->y
+1; e
= i2
->y
-1;
408 s
= i2
->y
+1; e
= i1
->y
-1;
410 for (y
= s
; y
<= e
; y
++) {
412 INDEX(state
,maxv
,x
,y
) = n
;
415 GRID(state
,x
,y
) ^= G_NOLINEV
;
417 GRID(state
,x
,y
) &= ~G_LINEV
;
419 GRID(state
,x
,y
) |= G_LINEV
;
420 INDEX(state
,lines
,x
,y
) = n
;
424 } else if (i1
->y
== i2
->y
) {
427 s
= i1
->x
+1; e
= i2
->x
-1;
429 s
= i2
->x
+1; e
= i1
->x
-1;
431 for (x
= s
; x
<= e
; x
++) {
433 INDEX(state
,maxh
,x
,y
) = n
;
436 GRID(state
,x
,y
) ^= G_NOLINEH
;
438 GRID(state
,x
,y
) &= ~G_LINEH
;
440 GRID(state
,x
,y
) |= G_LINEH
;
441 INDEX(state
,lines
,x
,y
) = n
;
446 assert(!"island_join: islands not orthogonal.");
450 /* Counts the number of bridges currently attached to the island. */
451 static int island_countbridges(struct island
*is
)
455 for (i
= 0; i
< is
->adj
.npoints
; i
++) {
456 c
+= GRIDCOUNT(is
->state
,
457 is
->adj
.points
[i
].x
, is
->adj
.points
[i
].y
,
458 is
->adj
.points
[i
].dx ? G_LINEH
: G_LINEV
);
460 /*debug(("island count for (%d,%d) is %d.\n", is->x, is->y, c));*/
464 static int island_adjspace(struct island
*is
, int marks
, int missing
,
467 int x
, y
, poss
, curr
, dx
;
468 grid_type gline
, mline
;
470 x
= is
->adj
.points
[direction
].x
;
471 y
= is
->adj
.points
[direction
].y
;
472 dx
= is
->adj
.points
[direction
].dx
;
473 gline
= dx ? G_LINEH
: G_LINEV
;
476 mline
= dx ? G_MARKH
: G_MARKV
;
477 if (GRID(is
->state
,x
,y
) & mline
) return 0;
479 poss
= POSSIBLES(is
->state
, dx
, x
, y
);
480 poss
= min(poss
, missing
);
482 curr
= GRIDCOUNT(is
->state
, x
, y
, gline
);
483 poss
= min(poss
, MAXIMUM(is
->state
, dx
, x
, y
) - curr
);
488 /* Counts the number of bridge spaces left around the island;
489 * expects the possibles to be up-to-date. */
490 static int island_countspaces(struct island
*is
, int marks
)
492 int i
, c
= 0, missing
;
494 missing
= is
->count
- island_countbridges(is
);
495 if (missing
< 0) return 0;
497 for (i
= 0; i
< is
->adj
.npoints
; i
++) {
498 c
+= island_adjspace(is
, marks
, missing
, i
);
503 static int island_isadj(struct island
*is
, int direction
)
506 grid_type gline
, mline
;
508 x
= is
->adj
.points
[direction
].x
;
509 y
= is
->adj
.points
[direction
].y
;
511 mline
= is
->adj
.points
[direction
].dx ? G_MARKH
: G_MARKV
;
512 gline
= is
->adj
.points
[direction
].dx ? G_LINEH
: G_LINEV
;
513 if (GRID(is
->state
, x
, y
) & mline
) {
514 /* If we're marked (i.e. the thing to attach to is complete)
515 * only count an adjacency if we're already attached. */
516 return GRIDCOUNT(is
->state
, x
, y
, gline
);
518 /* If we're unmarked, count possible adjacency iff it's
519 * flagged as POSSIBLE. */
520 return POSSIBLES(is
->state
, is
->adj
.points
[direction
].dx
, x
, y
);
525 /* Counts the no. of possible adjacent islands (including islands
526 * we're already connected to). */
527 static int island_countadj(struct island
*is
)
531 for (i
= 0; i
< is
->adj
.npoints
; i
++) {
532 if (island_isadj(is
, i
)) nadj
++;
537 static void island_togglemark(struct island
*is
)
540 struct island
*is_loop
;
542 /* mark the island... */
543 GRID(is
->state
, is
->x
, is
->y
) ^= G_MARK
;
545 /* ...remove all marks on non-island squares... */
546 for (x
= 0; x
< is
->state
->w
; x
++) {
547 for (y
= 0; y
< is
->state
->h
; y
++) {
548 if (!(GRID(is
->state
, x
, y
) & G_ISLAND
))
549 GRID(is
->state
, x
, y
) &= ~G_MARK
;
553 /* ...and add marks to squares around marked islands. */
554 for (i
= 0; i
< is
->state
->n_islands
; i
++) {
555 is_loop
= &is
->state
->islands
[i
];
556 if (!(GRID(is_loop
->state
, is_loop
->x
, is_loop
->y
) & G_MARK
))
559 for (j
= 0; j
< is_loop
->adj
.npoints
; j
++) {
560 /* if this direction takes us to another island, mark all
561 * squares between the two islands. */
562 if (!is_loop
->adj
.points
[j
].off
) continue;
563 assert(is_loop
->adj
.points
[j
].off
> 1);
564 for (o
= 1; o
< is_loop
->adj
.points
[j
].off
; o
++) {
566 is_loop
->x
+ is_loop
->adj
.points
[j
].dx
*o
,
567 is_loop
->y
+ is_loop
->adj
.points
[j
].dy
*o
) |=
568 is_loop
->adj
.points
[j
].dy ? G_MARKV
: G_MARKH
;
574 static int island_impossible(struct island
*is
, int strict
)
576 int curr
= island_countbridges(is
), nspc
= is
->count
- curr
, nsurrspc
;
578 struct island
*is_orth
;
581 debug(("island at (%d,%d) impossible because full.\n", is
->x
, is
->y
));
582 return 1; /* too many bridges */
583 } else if ((curr
+ island_countspaces(is
, 0)) < is
->count
) {
584 debug(("island at (%d,%d) impossible because not enough spaces.\n", is
->x
, is
->y
));
585 return 1; /* impossible to create enough bridges */
586 } else if (strict
&& curr
< is
->count
) {
587 debug(("island at (%d,%d) impossible because locked.\n", is
->x
, is
->y
));
588 return 1; /* not enough bridges and island is locked */
591 /* Count spaces in surrounding islands. */
593 for (i
= 0; i
< is
->adj
.npoints
; i
++) {
594 int ifree
, dx
= is
->adj
.points
[i
].dx
;
596 if (!is
->adj
.points
[i
].off
) continue;
597 poss
= POSSIBLES(is
->state
, dx
,
598 is
->adj
.points
[i
].x
, is
->adj
.points
[i
].y
);
599 if (poss
== 0) continue;
600 is_orth
= INDEX(is
->state
, gridi
,
601 ISLAND_ORTHX(is
,i
), ISLAND_ORTHY(is
,i
));
604 ifree
= is_orth
->count
- island_countbridges(is_orth
);
607 * ifree is the number of bridges unfilled in the other
608 * island, which is clearly an upper bound on the number
609 * of extra bridges this island may run to it.
611 * Another upper bound is the number of bridges unfilled
612 * on the specific line between here and there. We must
613 * take the minimum of both.
615 int bmax
= MAXIMUM(is
->state
, dx
,
616 is
->adj
.points
[i
].x
, is
->adj
.points
[i
].y
);
617 int bcurr
= GRIDCOUNT(is
->state
,
618 is
->adj
.points
[i
].x
, is
->adj
.points
[i
].y
,
619 dx ? G_LINEH
: G_LINEV
);
620 assert(bcurr
<= bmax
);
621 nsurrspc
+= min(ifree
, bmax
- bcurr
);
624 if (nsurrspc
< nspc
) {
625 debug(("island at (%d,%d) impossible: surr. islands %d spc, need %d.\n",
626 is
->x
, is
->y
, nsurrspc
, nspc
));
627 return 1; /* not enough spaces around surrounding islands to fill this one. */
633 /* --- Game parameter functions --- */
635 #define DEFAULT_PRESET 0
637 const struct game_params bridges_presets
[] = {
638 { 7, 7, 2, 30, 10, 1, 0 },
639 { 7, 7, 2, 30, 10, 1, 1 },
640 { 7, 7, 2, 30, 10, 1, 2 },
641 { 10, 10, 2, 30, 10, 1, 0 },
642 { 10, 10, 2, 30, 10, 1, 1 },
643 { 10, 10, 2, 30, 10, 1, 2 },
644 { 15, 15, 2, 30, 10, 1, 0 },
645 { 15, 15, 2, 30, 10, 1, 1 },
646 { 15, 15, 2, 30, 10, 1, 2 },
649 static game_params
*default_params(void)
651 game_params
*ret
= snew(game_params
);
652 *ret
= bridges_presets
[DEFAULT_PRESET
];
657 static int game_fetch_preset(int i
, char **name
, game_params
**params
)
662 if (i
< 0 || i
>= lenof(bridges_presets
))
665 ret
= default_params();
666 *ret
= bridges_presets
[i
];
669 sprintf(buf
, "%dx%d %s", ret
->w
, ret
->h
,
670 ret
->difficulty
== 0 ?
"easy" :
671 ret
->difficulty
== 1 ?
"medium" : "hard");
677 static void free_params(game_params
*params
)
682 static game_params
*dup_params(game_params
*params
)
684 game_params
*ret
= snew(game_params
);
685 *ret
= *params
; /* structure copy */
689 #define EATNUM(x) do { \
690 (x) = atoi(string); \
691 while (*string && isdigit((unsigned char)*string)) string++; \
694 static void decode_params(game_params
*params
, char const *string
)
697 params
->h
= params
->w
;
698 if (*string
== 'x') {
702 if (*string
== 'i') {
704 EATNUM(params
->islands
);
706 if (*string
== 'e') {
708 EATNUM(params
->expansion
);
710 if (*string
== 'm') {
712 EATNUM(params
->maxb
);
714 params
->allowloops
= 1;
715 if (*string
== 'L') {
717 params
->allowloops
= 0;
719 if (*string
== 'd') {
721 EATNUM(params
->difficulty
);
725 static char *encode_params(game_params
*params
, int full
)
730 sprintf(buf
, "%dx%di%de%dm%d%sd%d",
731 params
->w
, params
->h
, params
->islands
, params
->expansion
,
732 params
->maxb
, params
->allowloops ?
"" : "L",
735 sprintf(buf
, "%dx%dm%d%s", params
->w
, params
->h
,
736 params
->maxb
, params
->allowloops ?
"" : "L");
741 static config_item
*game_configure(game_params
*params
)
746 ret
= snewn(8, config_item
);
748 ret
[0].name
= "Width";
749 ret
[0].type
= C_STRING
;
750 sprintf(buf
, "%d", params
->w
);
751 ret
[0].sval
= dupstr(buf
);
754 ret
[1].name
= "Height";
755 ret
[1].type
= C_STRING
;
756 sprintf(buf
, "%d", params
->h
);
757 ret
[1].sval
= dupstr(buf
);
760 ret
[2].name
= "Difficulty";
761 ret
[2].type
= C_CHOICES
;
762 ret
[2].sval
= ":Easy:Medium:Hard";
763 ret
[2].ival
= params
->difficulty
;
765 ret
[3].name
= "Allow loops";
766 ret
[3].type
= C_BOOLEAN
;
768 ret
[3].ival
= params
->allowloops
;
770 ret
[4].name
= "Max. bridges per direction";
771 ret
[4].type
= C_CHOICES
;
772 ret
[4].sval
= ":1:2:3:4"; /* keep up-to-date with MAX_BRIDGES */
773 ret
[4].ival
= params
->maxb
- 1;
775 ret
[5].name
= "%age of island squares";
776 ret
[5].type
= C_CHOICES
;
777 ret
[5].sval
= ":5%:10%:15%:20%:25%:30%";
778 ret
[5].ival
= (params
->islands
/ 5)-1;
780 ret
[6].name
= "Expansion factor (%age)";
781 ret
[6].type
= C_CHOICES
;
782 ret
[6].sval
= ":0%:10%:20%:30%:40%:50%:60%:70%:80%:90%:100%";
783 ret
[6].ival
= params
->expansion
/ 10;
793 static game_params
*custom_params(config_item
*cfg
)
795 game_params
*ret
= snew(game_params
);
797 ret
->w
= atoi(cfg
[0].sval
);
798 ret
->h
= atoi(cfg
[1].sval
);
799 ret
->difficulty
= cfg
[2].ival
;
800 ret
->allowloops
= cfg
[3].ival
;
801 ret
->maxb
= cfg
[4].ival
+ 1;
802 ret
->islands
= (cfg
[5].ival
+ 1) * 5;
803 ret
->expansion
= cfg
[6].ival
* 10;
808 static char *validate_params(game_params
*params
, int full
)
810 if (params
->w
< 3 || params
->h
< 3)
811 return "Width and height must be at least 3";
812 if (params
->maxb
< 1 || params
->maxb
> MAX_BRIDGES
)
813 return "Too many bridges.";
815 if (params
->islands
<= 0 || params
->islands
> 30)
816 return "%age of island squares must be between 1% and 30%";
817 if (params
->expansion
< 0 || params
->expansion
> 100)
818 return "Expansion factor must be between 0 and 100";
823 /* --- Game encoding and differences --- */
825 static char *encode_game(game_state
*state
)
828 int wh
= state
->w
*state
->h
, run
, x
, y
;
831 ret
= snewn(wh
+ 1, char);
834 for (y
= 0; y
< state
->h
; y
++) {
835 for (x
= 0; x
< state
->w
; x
++) {
836 is
= INDEX(state
, gridi
, x
, y
);
839 *p
++ = ('a'-1) + run
;
843 *p
++ = '0' + is
->count
;
845 *p
++ = 'A' + (is
->count
- 10);
848 *p
++ = ('a'-1) + run
;
856 *p
++ = ('a'-1) + run
;
860 assert(p
- ret
<= wh
);
865 static char *game_state_diff(game_state
*src
, game_state
*dest
)
867 int movesize
= 256, movelen
= 0;
868 char *move
= snewn(movesize
, char), buf
[80];
870 grid_type gline
, nline
;
871 struct island
*is_s
, *is_d
, *is_orth
;
873 #define APPEND do { \
874 if (movelen + len >= movesize) { \
875 movesize = movelen + len + 256; \
876 move = sresize(move, movesize, char); \
878 strcpy(move + movelen, buf); \
882 move
[movelen
++] = 'S';
883 move
[movelen
] = '\0';
885 assert(src
->n_islands
== dest
->n_islands
);
887 for (i
= 0; i
< src
->n_islands
; i
++) {
888 is_s
= &src
->islands
[i
];
889 is_d
= &dest
->islands
[i
];
890 assert(is_s
->x
== is_d
->x
);
891 assert(is_s
->y
== is_d
->y
);
892 assert(is_s
->adj
.npoints
== is_d
->adj
.npoints
); /* more paranoia */
894 for (d
= 0; d
< is_s
->adj
.npoints
; d
++) {
895 if (is_s
->adj
.points
[d
].dx
== -1 ||
896 is_s
->adj
.points
[d
].dy
== -1) continue;
898 x
= is_s
->adj
.points
[d
].x
;
899 y
= is_s
->adj
.points
[d
].y
;
900 gline
= is_s
->adj
.points
[d
].dx ? G_LINEH
: G_LINEV
;
901 nline
= is_s
->adj
.points
[d
].dx ? G_NOLINEH
: G_NOLINEV
;
902 is_orth
= INDEX(dest
, gridi
,
903 ISLAND_ORTHX(is_d
, d
), ISLAND_ORTHY(is_d
, d
));
905 if (GRIDCOUNT(src
, x
, y
, gline
) != GRIDCOUNT(dest
, x
, y
, gline
)) {
907 len
= sprintf(buf
, ";L%d,%d,%d,%d,%d",
908 is_s
->x
, is_s
->y
, is_orth
->x
, is_orth
->y
,
909 GRIDCOUNT(dest
, x
, y
, gline
));
912 if ((GRID(src
,x
,y
) & nline
) != (GRID(dest
, x
, y
) & nline
)) {
914 len
= sprintf(buf
, ";N%d,%d,%d,%d",
915 is_s
->x
, is_s
->y
, is_orth
->x
, is_orth
->y
);
919 if ((GRID(src
, is_s
->x
, is_s
->y
) & G_MARK
) !=
920 (GRID(dest
, is_d
->x
, is_d
->y
) & G_MARK
)) {
921 len
= sprintf(buf
, ";M%d,%d", is_s
->x
, is_s
->y
);
928 /* --- Game setup and solving utilities --- */
930 /* This function is optimised; a Quantify showed that lots of grid-generation time
931 * (>50%) was spent in here. Hence the IDX() stuff. */
933 static void map_update_possibles(game_state
*state
)
935 int x
, y
, s
, e
, bl
, i
, np
, maxb
, w
= state
->w
, idx
;
936 struct island
*is_s
= NULL
, *is_f
= NULL
;
938 /* Run down vertical stripes [un]setting possv... */
939 for (x
= 0; x
< state
->w
; x
++) {
943 maxb
= state
->params
.maxb
; /* placate optimiser */
944 /* Unset possible flags until we find an island. */
945 for (y
= 0; y
< state
->h
; y
++) {
946 is_s
= IDX(state
, gridi
, idx
);
952 IDX(state
, possv
, idx
) = 0;
955 for (; y
< state
->h
; y
++) {
956 maxb
= min(maxb
, IDX(state
, maxv
, idx
));
957 is_f
= IDX(state
, gridi
, idx
);
960 np
= min(maxb
, is_f
->count
);
963 for (i
= s
; i
<= e
; i
++) {
964 INDEX(state
, possv
, x
, i
) = bl ?
0 : np
;
973 if (IDX(state
,grid
,idx
) & (G_LINEH
|G_NOLINEV
)) bl
= 1;
978 for (i
= s
; i
<= e
; i
++)
979 INDEX(state
, possv
, x
, i
) = 0;
983 /* ...and now do horizontal stripes [un]setting possh. */
984 /* can we lose this clone'n'hack? */
985 for (y
= 0; y
< state
->h
; y
++) {
989 maxb
= state
->params
.maxb
; /* placate optimiser */
990 for (x
= 0; x
< state
->w
; x
++) {
991 is_s
= IDX(state
, gridi
, idx
);
997 IDX(state
, possh
, idx
) = 0;
1000 for (; x
< state
->w
; x
++) {
1001 maxb
= min(maxb
, IDX(state
, maxh
, idx
));
1002 is_f
= IDX(state
, gridi
, idx
);
1005 np
= min(maxb
, is_f
->count
);
1008 for (i
= s
; i
<= e
; i
++) {
1009 INDEX(state
, possh
, i
, y
) = bl ?
0 : np
;
1018 if (IDX(state
,grid
,idx
) & (G_LINEV
|G_NOLINEH
)) bl
= 1;
1023 for (i
= s
; i
<= e
; i
++)
1024 INDEX(state
, possh
, i
, y
) = 0;
1029 static void map_count(game_state
*state
)
1032 grid_type flag
, grid
;
1035 for (i
= 0; i
< state
->n_islands
; i
++) {
1036 is
= &state
->islands
[i
];
1038 for (n
= 0; n
< is
->adj
.npoints
; n
++) {
1039 ax
= is
->adj
.points
[n
].x
;
1040 ay
= is
->adj
.points
[n
].y
;
1041 flag
= (ax
== is
->x
) ? G_LINEV
: G_LINEH
;
1042 grid
= GRID(state
,ax
,ay
);
1044 is
->count
+= INDEX(state
,lines
,ax
,ay
);
1050 static void map_find_orthogonal(game_state
*state
)
1054 for (i
= 0; i
< state
->n_islands
; i
++) {
1055 island_find_orthogonal(&state
->islands
[i
]);
1059 static int grid_degree(game_state
*state
, int x
, int y
, int *nx_r
, int *ny_r
)
1061 grid_type grid
= SCRATCH(state
, x
, y
), gline
= grid
& G_LINE
;
1063 int x1
, y1
, x2
, y2
, c
= 0, i
, nx
, ny
;
1065 nx
= ny
= -1; /* placate optimiser */
1066 is
= INDEX(state
, gridi
, x
, y
);
1068 for (i
= 0; i
< is
->adj
.npoints
; i
++) {
1069 gline
= is
->adj
.points
[i
].dx ? G_LINEH
: G_LINEV
;
1071 is
->adj
.points
[i
].x
,
1072 is
->adj
.points
[i
].y
) & gline
) {
1073 nx
= is
->adj
.points
[i
].x
;
1074 ny
= is
->adj
.points
[i
].y
;
1079 if (gline
& G_LINEV
) {
1086 /* Non-island squares with edges in should never be pointing off the
1087 * edge of the grid. */
1088 assert(INGRID(state
, x1
, y1
));
1089 assert(INGRID(state
, x2
, y2
));
1090 if (SCRATCH(state
, x1
, y1
) & (gline
| G_ISLAND
)) {
1091 nx
= x1
; ny
= y1
; c
++;
1093 if (SCRATCH(state
, x2
, y2
) & (gline
| G_ISLAND
)) {
1094 nx
= x2
; ny
= y2
; c
++;
1098 assert(nx
!= -1 && ny
!= -1); /* paranoia */
1099 *nx_r
= nx
; *ny_r
= ny
;
1104 static int map_hasloops(game_state
*state
, int mark
)
1106 int x
, y
, ox
, oy
, nx
= 0, ny
= 0, loop
= 0;
1108 memcpy(state
->scratch
, state
->grid
, GRIDSZ(state
));
1110 /* This algorithm is actually broken; if there are two loops connected
1111 * by bridges this will also highlight bridges. The correct algorithm
1112 * uses a dsf and a two-pass edge-detection algorithm (see check_correct
1113 * in slant.c); this is BALGE for now, especially since disallow-loops
1114 * is not the default for this puzzle. If we want to fix this later then
1115 * copy the alg in slant.c to the empty statement in map_group. */
1117 /* Remove all 1-degree edges. */
1118 for (y
= 0; y
< state
->h
; y
++) {
1119 for (x
= 0; x
< state
->w
; x
++) {
1121 while (grid_degree(state
, ox
, oy
, &nx
, &ny
) == 1) {
1122 /*debug(("hasloops: removing 1-degree at (%d,%d).\n", ox, oy));*/
1123 SCRATCH(state
, ox
, oy
) &= ~(G_LINE
|G_ISLAND
);
1128 /* Mark any remaining edges as G_WARN, if required. */
1129 for (x
= 0; x
< state
->w
; x
++) {
1130 for (y
= 0; y
< state
->h
; y
++) {
1131 if (GRID(state
,x
,y
) & G_ISLAND
) continue;
1133 if (SCRATCH(state
, x
, y
) & G_LINE
) {
1135 /*debug(("hasloops: marking loop square at (%d,%d).\n",
1137 GRID(state
,x
,y
) |= G_WARN
;
1140 return 1; /* short-cut as soon as we find one */
1143 GRID(state
,x
,y
) &= ~G_WARN
;
1150 static void map_group(game_state
*state
)
1152 int i
, wh
= state
->w
*state
->h
, d1
, d2
;
1154 int *dsf
= state
->solver
->dsf
;
1155 struct island
*is
, *is_join
;
1157 /* Initialise dsf. */
1160 /* For each island, find connected islands right or down
1161 * and merge the dsf for the island squares as well as the
1162 * bridge squares. */
1163 for (x
= 0; x
< state
->w
; x
++) {
1164 for (y
= 0; y
< state
->h
; y
++) {
1165 GRID(state
,x
,y
) &= ~(G_SWEEP
|G_WARN
); /* for group_full. */
1167 is
= INDEX(state
, gridi
, x
, y
);
1170 for (i
= 0; i
< is
->adj
.npoints
; i
++) {
1171 /* only want right/down */
1172 if (is
->adj
.points
[i
].dx
== -1 ||
1173 is
->adj
.points
[i
].dy
== -1) continue;
1175 is_join
= island_find_connection(is
, i
);
1176 if (!is_join
) continue;
1178 d2
= DINDEX(is_join
->x
, is_join
->y
);
1179 if (dsf_canonify(dsf
,d1
) == dsf_canonify(dsf
,d2
)) {
1180 ; /* we have a loop. See comment in map_hasloops. */
1181 /* However, we still want to merge all squares joining
1182 * this side-that-makes-a-loop. */
1184 /* merge all squares between island 1 and island 2. */
1185 for (x2
= x
; x2
<= is_join
->x
; x2
++) {
1186 for (y2
= y
; y2
<= is_join
->y
; y2
++) {
1188 if (d1
!= d2
) dsf_merge(dsf
,d1
,d2
);
1196 static int map_group_check(game_state
*state
, int canon
, int warn
,
1199 int *dsf
= state
->solver
->dsf
, nislands
= 0;
1200 int x
, y
, i
, allfull
= 1;
1203 for (i
= 0; i
< state
->n_islands
; i
++) {
1204 is
= &state
->islands
[i
];
1205 if (dsf_canonify(dsf
, DINDEX(is
->x
,is
->y
)) != canon
) continue;
1207 GRID(state
, is
->x
, is
->y
) |= G_SWEEP
;
1209 if (island_countbridges(is
) != is
->count
)
1212 if (warn
&& allfull
&& nislands
!= state
->n_islands
) {
1213 /* we're full and this island group isn't the whole set.
1214 * Mark all squares with this dsf canon as ERR. */
1215 for (x
= 0; x
< state
->w
; x
++) {
1216 for (y
= 0; y
< state
->h
; y
++) {
1217 if (dsf_canonify(dsf
, DINDEX(x
,y
)) == canon
) {
1218 GRID(state
,x
,y
) |= G_WARN
;
1224 if (nislands_r
) *nislands_r
= nislands
;
1228 static int map_group_full(game_state
*state
, int *ngroups_r
)
1230 int *dsf
= state
->solver
->dsf
, ngroups
= 0;
1234 /* NB this assumes map_group (or sth else) has cleared G_SWEEP. */
1236 for (i
= 0; i
< state
->n_islands
; i
++) {
1237 is
= &state
->islands
[i
];
1238 if (GRID(state
,is
->x
,is
->y
) & G_SWEEP
) continue;
1241 if (map_group_check(state
, dsf_canonify(dsf
, DINDEX(is
->x
,is
->y
)),
1246 *ngroups_r
= ngroups
;
1250 static int map_check(game_state
*state
)
1254 /* Check for loops, if necessary. */
1255 if (!state
->allowloops
) {
1256 if (map_hasloops(state
, 1))
1260 /* Place islands into island groups and check for early
1261 * satisfied-groups. */
1262 map_group(state
); /* clears WARN and SWEEP */
1263 if (map_group_full(state
, &ngroups
)) {
1264 if (ngroups
== 1) return 1;
1269 static void map_clear(game_state
*state
)
1273 for (x
= 0; x
< state
->w
; x
++) {
1274 for (y
= 0; y
< state
->h
; y
++) {
1275 /* clear most flags; might want to be slightly more careful here. */
1276 GRID(state
,x
,y
) &= G_ISLAND
;
1281 static void solve_join(struct island
*is
, int direction
, int n
, int is_max
)
1283 struct island
*is_orth
;
1284 int d1
, d2
, *dsf
= is
->state
->solver
->dsf
;
1285 game_state
*state
= is
->state
; /* for DINDEX */
1287 is_orth
= INDEX(is
->state
, gridi
,
1288 ISLAND_ORTHX(is
, direction
),
1289 ISLAND_ORTHY(is
, direction
));
1291 /*debug(("...joining (%d,%d) to (%d,%d) with %d bridge(s).\n",
1292 is->x, is->y, is_orth->x, is_orth->y, n));*/
1293 island_join(is
, is_orth
, n
, is_max
);
1295 if (n
> 0 && !is_max
) {
1296 d1
= DINDEX(is
->x
, is
->y
);
1297 d2
= DINDEX(is_orth
->x
, is_orth
->y
);
1298 if (dsf_canonify(dsf
, d1
) != dsf_canonify(dsf
, d2
))
1299 dsf_merge(dsf
, d1
, d2
);
1303 static int solve_fillone(struct island
*is
)
1307 debug(("solve_fillone for island (%d,%d).\n", is
->x
, is
->y
));
1309 for (i
= 0; i
< is
->adj
.npoints
; i
++) {
1310 if (island_isadj(is
, i
)) {
1311 if (island_hasbridge(is
, i
)) {
1312 /* already attached; do nothing. */;
1314 solve_join(is
, i
, 1, 0);
1322 static int solve_fill(struct island
*is
)
1324 /* for each unmarked adjacent, make sure we convert every possible bridge
1325 * to a real one, and then work out the possibles afresh. */
1326 int i
, nnew
, ncurr
, nadded
= 0, missing
;
1328 debug(("solve_fill for island (%d,%d).\n", is
->x
, is
->y
));
1330 missing
= is
->count
- island_countbridges(is
);
1331 if (missing
< 0) return 0;
1333 /* very like island_countspaces. */
1334 for (i
= 0; i
< is
->adj
.npoints
; i
++) {
1335 nnew
= island_adjspace(is
, 1, missing
, i
);
1337 ncurr
= GRIDCOUNT(is
->state
,
1338 is
->adj
.points
[i
].x
, is
->adj
.points
[i
].y
,
1339 is
->adj
.points
[i
].dx ? G_LINEH
: G_LINEV
);
1341 solve_join(is
, i
, nnew
+ ncurr
, 0);
1348 static int solve_island_stage1(struct island
*is
, int *didsth_r
)
1350 int bridges
= island_countbridges(is
);
1351 int nspaces
= island_countspaces(is
, 1);
1352 int nadj
= island_countadj(is
);
1357 /*debug(("island at (%d,%d) filled %d/%d (%d spc) nadj %d\n",
1358 is->x, is->y, bridges, is->count, nspaces, nadj));*/
1359 if (bridges
> is
->count
) {
1360 /* We only ever add bridges when we're sure they fit, or that's
1361 * the only place they can go. If we've added bridges such that
1362 * another island has become wrong, the puzzle must not have had
1364 debug(("...island at (%d,%d) is overpopulated!\n", is
->x
, is
->y
));
1366 } else if (bridges
== is
->count
) {
1367 /* This island is full. Make sure it's marked (and update
1368 * possibles if we did). */
1369 if (!(GRID(is
->state
, is
->x
, is
->y
) & G_MARK
)) {
1370 debug(("...marking island (%d,%d) as full.\n", is
->x
, is
->y
));
1371 island_togglemark(is
);
1374 } else if (GRID(is
->state
, is
->x
, is
->y
) & G_MARK
) {
1375 debug(("...island (%d,%d) is marked but unfinished!\n",
1377 return 0; /* island has been marked unfinished; no solution from here. */
1379 /* This is the interesting bit; we try and fill in more information
1380 * about this island. */
1381 if (is
->count
== bridges
+ nspaces
) {
1382 if (solve_fill(is
) > 0) didsth
= 1;
1383 } else if (is
->count
> ((nadj
-1) * is
->state
->maxb
)) {
1384 /* must have at least one bridge in each possible direction. */
1385 if (solve_fillone(is
) > 0) didsth
= 1;
1389 map_update_possibles(is
->state
);
1395 /* returns non-zero if a new line here would cause a loop. */
1396 static int solve_island_checkloop(struct island
*is
, int direction
)
1398 struct island
*is_orth
;
1399 int *dsf
= is
->state
->solver
->dsf
, d1
, d2
;
1400 game_state
*state
= is
->state
;
1402 if (is
->state
->allowloops
) return 0; /* don't care anyway */
1403 if (island_hasbridge(is
, direction
)) return 0; /* already has a bridge */
1404 if (island_isadj(is
, direction
) == 0) return 0; /* no adj island */
1406 is_orth
= INDEX(is
->state
, gridi
,
1407 ISLAND_ORTHX(is
,direction
),
1408 ISLAND_ORTHY(is
,direction
));
1409 if (!is_orth
) return 0;
1411 d1
= DINDEX(is
->x
, is
->y
);
1412 d2
= DINDEX(is_orth
->x
, is_orth
->y
);
1413 if (dsf_canonify(dsf
, d1
) == dsf_canonify(dsf
, d2
)) {
1414 /* two islands are connected already; don't join them. */
1420 static int solve_island_stage2(struct island
*is
, int *didsth_r
)
1422 int added
= 0, removed
= 0, navail
= 0, nadj
, i
;
1426 for (i
= 0; i
< is
->adj
.npoints
; i
++) {
1427 if (solve_island_checkloop(is
, i
)) {
1428 debug(("removing possible loop at (%d,%d) direction %d.\n",
1430 solve_join(is
, i
, -1, 0);
1431 map_update_possibles(is
->state
);
1434 navail
+= island_isadj(is
, i
);
1435 /*debug(("stage2: navail for (%d,%d) direction (%d,%d) is %d.\n",
1437 is->adj.points[i].dx, is->adj.points[i].dy,
1438 island_isadj(is, i)));*/
1442 /*debug(("island at (%d,%d) navail %d: checking...\n", is->x, is->y, navail));*/
1444 for (i
= 0; i
< is
->adj
.npoints
; i
++) {
1445 if (!island_hasbridge(is
, i
)) {
1446 nadj
= island_isadj(is
, i
);
1447 if (nadj
> 0 && (navail
- nadj
) < is
->count
) {
1448 /* we couldn't now complete the island without at
1449 * least one bridge here; put it in. */
1450 /*debug(("nadj %d, navail %d, is->count %d.\n",
1451 nadj, navail, is->count));*/
1452 debug(("island at (%d,%d) direction (%d,%d) must have 1 bridge\n",
1454 is
->adj
.points
[i
].dx
, is
->adj
.points
[i
].dy
));
1455 solve_join(is
, i
, 1, 0);
1457 /*debug_state(is->state);
1458 debug_possibles(is->state);*/
1462 if (added
) map_update_possibles(is
->state
);
1463 if (added
|| removed
) *didsth_r
= 1;
1467 static int solve_island_subgroup(struct island
*is
, int direction
)
1469 struct island
*is_join
;
1470 int nislands
, *dsf
= is
->state
->solver
->dsf
;
1471 game_state
*state
= is
->state
;
1473 debug(("..checking subgroups.\n"));
1475 /* if is isn't full, return 0. */
1476 if (island_countbridges(is
) < is
->count
) {
1477 debug(("...orig island (%d,%d) not full.\n", is
->x
, is
->y
));
1481 if (direction
>= 0) {
1482 is_join
= INDEX(state
, gridi
,
1483 ISLAND_ORTHX(is
, direction
),
1484 ISLAND_ORTHY(is
, direction
));
1487 /* if is_join isn't full, return 0. */
1488 if (island_countbridges(is_join
) < is_join
->count
) {
1489 debug(("...dest island (%d,%d) not full.\n",
1490 is_join
->x
, is_join
->y
));
1495 /* Check group membership for is->dsf; if it's full return 1. */
1496 if (map_group_check(state
, dsf_canonify(dsf
, DINDEX(is
->x
,is
->y
)),
1498 if (nislands
< state
->n_islands
) {
1499 /* we have a full subgroup that isn't the whole set.
1500 * This isn't allowed. */
1501 debug(("island at (%d,%d) makes full subgroup, disallowing.\n",
1505 debug(("...has finished puzzle.\n"));
1511 static int solve_island_impossible(game_state
*state
)
1516 /* If any islands are impossible, return 1. */
1517 for (i
= 0; i
< state
->n_islands
; i
++) {
1518 is
= &state
->islands
[i
];
1519 if (island_impossible(is
, 0)) {
1520 debug(("island at (%d,%d) has become impossible, disallowing.\n",
1528 /* Bear in mind that this function is really rather inefficient. */
1529 static int solve_island_stage3(struct island
*is
, int *didsth_r
)
1531 int i
, n
, x
, y
, missing
, spc
, curr
, maxb
, didsth
= 0;
1532 int wh
= is
->state
->w
* is
->state
->h
;
1533 struct solver_state
*ss
= is
->state
->solver
;
1537 missing
= is
->count
- island_countbridges(is
);
1538 if (missing
<= 0) return 1;
1540 for (i
= 0; i
< is
->adj
.npoints
; i
++) {
1541 /* We only do right- or down-pointing bridges. */
1542 if (is
->adj
.points
[i
].dx
== -1 ||
1543 is
->adj
.points
[i
].dy
== -1) continue;
1545 x
= is
->adj
.points
[i
].x
;
1546 y
= is
->adj
.points
[i
].y
;
1547 spc
= island_adjspace(is
, 1, missing
, i
);
1548 if (spc
== 0) continue;
1550 curr
= GRIDCOUNT(is
->state
, x
, y
,
1551 is
->adj
.points
[i
].dx ? G_LINEH
: G_LINEV
);
1552 debug(("island at (%d,%d) s3, trying %d - %d bridges.\n",
1553 is
->x
, is
->y
, curr
+1, curr
+spc
));
1555 /* Now we know that this island could have more bridges,
1556 * to bring the total from curr+1 to curr+spc. */
1558 /* We have to squirrel the dsf away and restore it afterwards;
1559 * it is additive only, and can't be removed from. */
1560 memcpy(ss
->tmpdsf
, ss
->dsf
, wh
*sizeof(int));
1561 for (n
= curr
+1; n
<= curr
+spc
; n
++) {
1562 solve_join(is
, i
, n
, 0);
1563 map_update_possibles(is
->state
);
1565 if (solve_island_subgroup(is
, i
) ||
1566 solve_island_impossible(is
->state
)) {
1568 debug(("island at (%d,%d) d(%d,%d) new max of %d bridges:\n",
1570 is
->adj
.points
[i
].dx
, is
->adj
.points
[i
].dy
,
1575 solve_join(is
, i
, curr
, 0); /* put back to before. */
1576 memcpy(ss
->dsf
, ss
->tmpdsf
, wh
*sizeof(int));
1579 /*debug_state(is->state);*/
1581 debug(("...adding NOLINE.\n"));
1582 solve_join(is
, i
, -1, 0); /* we can't have any bridges here. */
1584 debug(("...setting maximum\n"));
1585 solve_join(is
, i
, maxb
, 1);
1589 map_update_possibles(is
->state
);
1592 for (i
= 0; i
< is
->adj
.npoints
; i
++) {
1594 * Now check to see if any currently empty direction must have
1595 * at least one bridge in order to avoid forming an isolated
1596 * subgraph. This differs from the check above in that it
1597 * considers multiple target islands. For example:
1604 * The example on the left can be handled by the above loop:
1605 * it will observe that connecting the central 2 twice to the
1606 * left would form an isolated subgraph, and hence it will
1607 * restrict that 2 to at most one bridge in that direction.
1608 * But the example on the right won't be handled by that loop,
1609 * because the deduction requires us to imagine connecting the
1610 * 3 to _both_ the 1 and 2 at once to form an isolated
1613 * This pass is necessary _as well_ as the above one, because
1614 * neither can do the other's job. In the left one,
1615 * restricting the direction which _would_ cause trouble can
1616 * be done even if it's not yet clear which of the remaining
1617 * directions has to have a compensatory bridge; whereas the
1618 * pass below that can handle the right-hand example does need
1619 * to know what direction to point the necessary bridge in.
1621 * Neither pass can handle the most general case, in which we
1622 * observe that an arbitrary subset of an island's neighbours
1623 * would form an isolated subgraph with it if it connected
1624 * maximally to them, and hence that at least one bridge must
1625 * point to some neighbour outside that subset but we don't
1626 * know which neighbour. To handle that, we'd have to have a
1627 * richer data format for the solver, which could cope with
1628 * recording the idea that at least one of two edges must have
1635 spc
= island_adjspace(is
, 1, missing
, i
);
1636 if (spc
== 0) continue;
1638 for (j
= 0; j
< is
->adj
.npoints
; j
++)
1639 before
[j
] = GRIDCOUNT(is
->state
,
1640 is
->adj
.points
[j
].x
,
1641 is
->adj
.points
[j
].y
,
1642 is
->adj
.points
[j
].dx ? G_LINEH
: G_LINEV
);
1643 if (before
[i
] != 0) continue; /* this idea is pointless otherwise */
1645 memcpy(ss
->tmpdsf
, ss
->dsf
, wh
*sizeof(int));
1647 for (j
= 0; j
< is
->adj
.npoints
; j
++) {
1648 spc
= island_adjspace(is
, 1, missing
, j
);
1649 if (spc
== 0) continue;
1650 if (j
== i
) continue;
1651 solve_join(is
, j
, before
[j
] + spc
, 0);
1653 map_update_possibles(is
->state
);
1655 if (solve_island_subgroup(is
, -1))
1658 for (j
= 0; j
< is
->adj
.npoints
; j
++)
1659 solve_join(is
, j
, before
[j
], 0);
1660 memcpy(ss
->dsf
, ss
->tmpdsf
, wh
*sizeof(int));
1663 debug(("island at (%d,%d) must connect in direction (%d,%d) to"
1664 " avoid full subgroup.\n",
1665 is
->x
, is
->y
, is
->adj
.points
[i
].dx
, is
->adj
.points
[i
].dy
));
1666 solve_join(is
, i
, 1, 0);
1670 map_update_possibles(is
->state
);
1673 if (didsth
) *didsth_r
= didsth
;
1677 #define CONTINUE_IF_FULL do { \
1678 if (GRID(state, is->x, is->y) & G_MARK) { \
1679 /* island full, don't try fixing it */ \
1683 static int solve_sub(game_state
*state
, int difficulty
, int depth
)
1691 /* First island iteration: things we can work out by looking at
1692 * properties of the island as a whole. */
1693 for (i
= 0; i
< state
->n_islands
; i
++) {
1694 is
= &state
->islands
[i
];
1695 if (!solve_island_stage1(is
, &didsth
)) return 0;
1697 if (didsth
) continue;
1698 else if (difficulty
< 1) break;
1700 /* Second island iteration: thing we can work out by looking at
1701 * properties of individual island connections. */
1702 for (i
= 0; i
< state
->n_islands
; i
++) {
1703 is
= &state
->islands
[i
];
1705 if (!solve_island_stage2(is
, &didsth
)) return 0;
1707 if (didsth
) continue;
1708 else if (difficulty
< 2) break;
1710 /* Third island iteration: things we can only work out by looking
1711 * at groups of islands. */
1712 for (i
= 0; i
< state
->n_islands
; i
++) {
1713 is
= &state
->islands
[i
];
1714 if (!solve_island_stage3(is
, &didsth
)) return 0;
1716 if (didsth
) continue;
1717 else if (difficulty
< 3) break;
1719 /* If we can be bothered, write a recursive solver to finish here. */
1722 if (map_check(state
)) return 1; /* solved it */
1726 static void solve_for_hint(game_state
*state
)
1729 solve_sub(state
, 10, 0);
1732 static int solve_from_scratch(game_state
*state
, int difficulty
)
1736 map_update_possibles(state
);
1737 return solve_sub(state
, difficulty
, 0);
1740 /* --- New game functions --- */
1742 static game_state
*new_state(game_params
*params
)
1744 game_state
*ret
= snew(game_state
);
1745 int wh
= params
->w
* params
->h
, i
;
1749 ret
->allowloops
= params
->allowloops
;
1750 ret
->maxb
= params
->maxb
;
1751 ret
->params
= *params
;
1753 ret
->grid
= snewn(wh
, grid_type
);
1754 memset(ret
->grid
, 0, GRIDSZ(ret
));
1755 ret
->scratch
= snewn(wh
, grid_type
);
1756 memset(ret
->scratch
, 0, GRIDSZ(ret
));
1758 ret
->wha
= snewn(wh
*N_WH_ARRAYS
, char);
1759 memset(ret
->wha
, 0, wh
*N_WH_ARRAYS
*sizeof(char));
1761 ret
->possv
= ret
->wha
;
1762 ret
->possh
= ret
->wha
+ wh
;
1763 ret
->lines
= ret
->wha
+ wh
*2;
1764 ret
->maxv
= ret
->wha
+ wh
*3;
1765 ret
->maxh
= ret
->wha
+ wh
*4;
1767 memset(ret
->maxv
, ret
->maxb
, wh
*sizeof(char));
1768 memset(ret
->maxh
, ret
->maxb
, wh
*sizeof(char));
1770 ret
->islands
= NULL
;
1772 ret
->n_islands_alloc
= 0;
1774 ret
->gridi
= snewn(wh
, struct island
*);
1775 for (i
= 0; i
< wh
; i
++) ret
->gridi
[i
] = NULL
;
1777 ret
->solved
= ret
->completed
= 0;
1779 ret
->solver
= snew(struct solver_state
);
1780 ret
->solver
->dsf
= snew_dsf(wh
);
1781 ret
->solver
->tmpdsf
= snewn(wh
, int);
1783 ret
->solver
->refcount
= 1;
1788 static game_state
*dup_game(game_state
*state
)
1790 game_state
*ret
= snew(game_state
);
1791 int wh
= state
->w
*state
->h
;
1795 ret
->allowloops
= state
->allowloops
;
1796 ret
->maxb
= state
->maxb
;
1797 ret
->params
= state
->params
;
1799 ret
->grid
= snewn(wh
, grid_type
);
1800 memcpy(ret
->grid
, state
->grid
, GRIDSZ(ret
));
1801 ret
->scratch
= snewn(wh
, grid_type
);
1802 memcpy(ret
->scratch
, state
->scratch
, GRIDSZ(ret
));
1804 ret
->wha
= snewn(wh
*N_WH_ARRAYS
, char);
1805 memcpy(ret
->wha
, state
->wha
, wh
*N_WH_ARRAYS
*sizeof(char));
1807 ret
->possv
= ret
->wha
;
1808 ret
->possh
= ret
->wha
+ wh
;
1809 ret
->lines
= ret
->wha
+ wh
*2;
1810 ret
->maxv
= ret
->wha
+ wh
*3;
1811 ret
->maxh
= ret
->wha
+ wh
*4;
1813 ret
->islands
= snewn(state
->n_islands
, struct island
);
1814 memcpy(ret
->islands
, state
->islands
, state
->n_islands
* sizeof(struct island
));
1815 ret
->n_islands
= ret
->n_islands_alloc
= state
->n_islands
;
1817 ret
->gridi
= snewn(wh
, struct island
*);
1818 fixup_islands_for_realloc(ret
);
1820 ret
->solved
= state
->solved
;
1821 ret
->completed
= state
->completed
;
1823 ret
->solver
= state
->solver
;
1824 ret
->solver
->refcount
++;
1829 static void free_game(game_state
*state
)
1831 if (--state
->solver
->refcount
<= 0) {
1832 sfree(state
->solver
->dsf
);
1833 sfree(state
->solver
->tmpdsf
);
1834 sfree(state
->solver
);
1837 sfree(state
->islands
);
1838 sfree(state
->gridi
);
1842 sfree(state
->scratch
);
1847 #define MAX_NEWISLAND_TRIES 50
1848 #define MIN_SENSIBLE_ISLANDS 3
1850 #define ORDER(a,b) do { if (a < b) { int tmp=a; int a=b; int b=tmp; } } while(0)
1852 static char *new_game_desc(game_params
*params
, random_state
*rs
,
1853 char **aux
, int interactive
)
1855 game_state
*tobuild
= NULL
;
1856 int i
, j
, wh
= params
->w
* params
->h
, x
, y
, dx
, dy
;
1857 int minx
, miny
, maxx
, maxy
, joinx
, joiny
, newx
, newy
, diffx
, diffy
;
1858 int ni_req
= max((params
->islands
* wh
) / 100, MIN_SENSIBLE_ISLANDS
), ni_curr
, ni_bad
;
1859 struct island
*is
, *is2
;
1861 unsigned int echeck
;
1863 /* pick a first island position randomly. */
1865 if (tobuild
) free_game(tobuild
);
1866 tobuild
= new_state(params
);
1868 x
= random_upto(rs
, params
->w
);
1869 y
= random_upto(rs
, params
->h
);
1870 island_add(tobuild
, x
, y
, 0);
1873 debug(("Created initial island at (%d,%d).\n", x
, y
));
1875 while (ni_curr
< ni_req
) {
1876 /* Pick a random island to try and extend from. */
1877 i
= random_upto(rs
, tobuild
->n_islands
);
1878 is
= &tobuild
->islands
[i
];
1880 /* Pick a random direction to extend in. */
1881 j
= random_upto(rs
, is
->adj
.npoints
);
1882 dx
= is
->adj
.points
[j
].x
- is
->x
;
1883 dy
= is
->adj
.points
[j
].y
- is
->y
;
1885 /* Find out limits of where we could put a new island. */
1887 minx
= is
->x
+ 2*dx
; miny
= is
->y
+ 2*dy
; /* closest is 2 units away. */
1888 x
= is
->x
+dx
; y
= is
->y
+dy
;
1889 if (GRID(tobuild
,x
,y
) & (G_LINEV
|G_LINEH
)) {
1890 /* already a line next to the island, continue. */
1894 if (x
< 0 || x
>= params
->w
|| y
< 0 || y
>= params
->h
) {
1895 /* got past the edge; put a possible at the island
1897 maxx
= x
-dx
; maxy
= y
-dy
;
1900 if (GRID(tobuild
,x
,y
) & G_ISLAND
) {
1901 /* could join up to an existing island... */
1902 joinx
= x
; joiny
= y
;
1903 /* ... or make a new one 2 spaces away. */
1904 maxx
= x
- 2*dx
; maxy
= y
- 2*dy
;
1906 } else if (GRID(tobuild
,x
,y
) & (G_LINEV
|G_LINEH
)) {
1907 /* could make a new one 1 space away from the line. */
1908 maxx
= x
- dx
; maxy
= y
- dy
;
1915 debug(("Island at (%d,%d) with d(%d,%d) has new positions "
1916 "(%d,%d) -> (%d,%d), join (%d,%d).\n",
1917 is
->x
, is
->y
, dx
, dy
, minx
, miny
, maxx
, maxy
, joinx
, joiny
));
1918 /* Now we know where we could either put a new island
1919 * (between min and max), or (if loops are allowed) could join on
1920 * to an existing island (at join). */
1921 if (params
->allowloops
&& joinx
!= -1 && joiny
!= -1) {
1922 if (random_upto(rs
, 100) < (unsigned long)params
->expansion
) {
1923 is2
= INDEX(tobuild
, gridi
, joinx
, joiny
);
1924 debug(("Joining island at (%d,%d) to (%d,%d).\n",
1925 is
->x
, is
->y
, is2
->x
, is2
->y
));
1929 diffx
= (maxx
- minx
) * dx
;
1930 diffy
= (maxy
- miny
) * dy
;
1931 if (diffx
< 0 || diffy
< 0) goto bad
;
1932 if (random_upto(rs
,100) < (unsigned long)params
->expansion
) {
1933 newx
= maxx
; newy
= maxy
;
1934 debug(("Creating new island at (%d,%d) (expanded).\n", newx
, newy
));
1936 newx
= minx
+ random_upto(rs
,diffx
+1)*dx
;
1937 newy
= miny
+ random_upto(rs
,diffy
+1)*dy
;
1938 debug(("Creating new island at (%d,%d).\n", newx
, newy
));
1940 /* check we're not next to island in the other orthogonal direction. */
1941 if ((INGRID(tobuild
,newx
+dy
,newy
+dx
) && (GRID(tobuild
,newx
+dy
,newy
+dx
) & G_ISLAND
)) ||
1942 (INGRID(tobuild
,newx
-dy
,newy
-dx
) && (GRID(tobuild
,newx
-dy
,newy
-dx
) & G_ISLAND
))) {
1943 debug(("New location is adjacent to island, skipping.\n"));
1946 is2
= island_add(tobuild
, newx
, newy
, 0);
1947 /* Must get is again at this point; the array might have
1948 * been realloced by island_add... */
1949 is
= &tobuild
->islands
[i
]; /* ...but order will not change. */
1951 ni_curr
++; ni_bad
= 0;
1953 island_join(is
, is2
, random_upto(rs
, tobuild
->maxb
)+1, 0);
1954 debug_state(tobuild
);
1959 if (ni_bad
> MAX_NEWISLAND_TRIES
) {
1960 debug(("Unable to create any new islands after %d tries; "
1961 "created %d [%d%%] (instead of %d [%d%%] requested).\n",
1962 MAX_NEWISLAND_TRIES
,
1963 ni_curr
, ni_curr
* 100 / wh
,
1964 ni_req
, ni_req
* 100 / wh
));
1971 debug(("Only generated one island (!), retrying.\n"));
1974 /* Check we have at least one island on each extremity of the grid. */
1976 for (x
= 0; x
< params
->w
; x
++) {
1977 if (INDEX(tobuild
, gridi
, x
, 0)) echeck
|= 1;
1978 if (INDEX(tobuild
, gridi
, x
, params
->h
-1)) echeck
|= 2;
1980 for (y
= 0; y
< params
->h
; y
++) {
1981 if (INDEX(tobuild
, gridi
, 0, y
)) echeck
|= 4;
1982 if (INDEX(tobuild
, gridi
, params
->w
-1, y
)) echeck
|= 8;
1985 debug(("Generated grid doesn't fill to sides, retrying.\n"));
1990 map_find_orthogonal(tobuild
);
1992 if (params
->difficulty
> 0) {
1993 if ((ni_curr
> MIN_SENSIBLE_ISLANDS
) &&
1994 (solve_from_scratch(tobuild
, params
->difficulty
-1) > 0)) {
1995 debug(("Grid is solvable at difficulty %d (too easy); retrying.\n",
1996 params
->difficulty
-1));
2001 if (solve_from_scratch(tobuild
, params
->difficulty
) == 0) {
2002 debug(("Grid not solvable at difficulty %d, (too hard); retrying.\n",
2003 params
->difficulty
));
2007 /* ... tobuild is now solved. We rely on this making the diff for aux. */
2008 debug_state(tobuild
);
2009 ret
= encode_game(tobuild
);
2011 game_state
*clean
= dup_game(tobuild
);
2013 map_update_possibles(clean
);
2014 *aux
= game_state_diff(clean
, tobuild
);
2022 static char *validate_desc(game_params
*params
, char *desc
)
2024 int i
, wh
= params
->w
* params
->h
;
2026 for (i
= 0; i
< wh
; i
++) {
2027 if (*desc
>= '1' && *desc
<= '9')
2029 else if (*desc
>= 'a' && *desc
<= 'z')
2030 i
+= *desc
- 'a'; /* plus the i++ */
2031 else if (*desc
>= 'A' && *desc
<= 'G')
2033 else if (*desc
== 'V' || *desc
== 'W' ||
2034 *desc
== 'X' || *desc
== 'Y' ||
2035 *desc
== 'H' || *desc
== 'I' ||
2036 *desc
== 'J' || *desc
== 'K')
2039 return "Game description shorter than expected";
2041 return "Game description containers unexpected character";
2044 if (*desc
|| i
> wh
)
2045 return "Game description longer than expected";
2050 static game_state
*new_game_sub(game_params
*params
, char *desc
)
2052 game_state
*state
= new_state(params
);
2055 debug(("new_game[_sub]: desc = '%s'.\n", desc
));
2057 for (y
= 0; y
< params
->h
; y
++) {
2058 for (x
= 0; x
< params
->w
; x
++) {
2064 if (c
>= 'a' && c
<= 'z')
2074 case '1': case '2': case '3': case '4':
2075 case '5': case '6': case '7': case '8': case '9':
2076 island_add(state
, x
, y
, (c
- '0'));
2079 case 'A': case 'B': case 'C': case 'D':
2080 case 'E': case 'F': case 'G':
2081 island_add(state
, x
, y
, (c
- 'A') + 10);
2089 assert(!"Malformed desc.");
2094 if (*desc
) assert(!"Over-long desc.");
2096 map_find_orthogonal(state
);
2097 map_update_possibles(state
);
2102 static game_state
*new_game(midend
*me
, game_params
*params
, char *desc
)
2104 return new_game_sub(params
, desc
);
2108 int dragx_src
, dragy_src
; /* source; -1 means no drag */
2109 int dragx_dst
, dragy_dst
; /* src's closest orth island. */
2111 int dragging
, drag_is_noline
, nlines
;
2113 int cur_x
, cur_y
, cur_visible
; /* cursor position */
2117 static char *ui_cancel_drag(game_ui
*ui
)
2119 ui
->dragx_src
= ui
->dragy_src
= -1;
2120 ui
->dragx_dst
= ui
->dragy_dst
= -1;
2125 static game_ui
*new_ui(game_state
*state
)
2127 game_ui
*ui
= snew(game_ui
);
2129 ui
->cur_x
= state
->islands
[0].x
;
2130 ui
->cur_y
= state
->islands
[0].y
;
2131 ui
->cur_visible
= 0;
2136 static void free_ui(game_ui
*ui
)
2141 static char *encode_ui(game_ui
*ui
)
2146 static void decode_ui(game_ui
*ui
, char *encoding
)
2150 static void game_changed_state(game_ui
*ui
, game_state
*oldstate
,
2151 game_state
*newstate
)
2155 struct game_drawstate
{
2160 int started
, dragging
;
2164 static char *update_drag_dst(game_state
*state
, game_ui
*ui
, game_drawstate
*ds
,
2167 int ox
, oy
, dx
, dy
, i
, currl
, maxb
;
2169 grid_type gtype
, ntype
, mtype
, curr
;
2171 if (ui
->dragx_src
== -1 || ui
->dragy_src
== -1) return NULL
;
2176 /* work out which of the four directions we're closest to... */
2177 ox
= COORD(ui
->dragx_src
) + TILE_SIZE
/2;
2178 oy
= COORD(ui
->dragy_src
) + TILE_SIZE
/2;
2180 if (abs(nx
-ox
) < abs(ny
-oy
)) {
2182 dy
= (ny
-oy
) < 0 ?
-1 : 1;
2183 gtype
= G_LINEV
; ntype
= G_NOLINEV
; mtype
= G_MARKV
;
2184 maxb
= INDEX(state
, maxv
, ui
->dragx_src
+dx
, ui
->dragy_src
+dy
);
2187 dx
= (nx
-ox
) < 0 ?
-1 : 1;
2188 gtype
= G_LINEH
; ntype
= G_NOLINEH
; mtype
= G_MARKH
;
2189 maxb
= INDEX(state
, maxh
, ui
->dragx_src
+dx
, ui
->dragy_src
+dy
);
2191 if (ui
->drag_is_noline
) {
2194 curr
= GRID(state
, ui
->dragx_src
+dx
, ui
->dragy_src
+dy
);
2195 currl
= INDEX(state
, lines
, ui
->dragx_src
+dx
, ui
->dragy_src
+dy
);
2198 if (currl
== maxb
) {
2203 ui
->nlines
= currl
+ 1;
2211 /* ... and see if there's an island off in that direction. */
2212 is
= INDEX(state
, gridi
, ui
->dragx_src
, ui
->dragy_src
);
2213 for (i
= 0; i
< is
->adj
.npoints
; i
++) {
2214 if (is
->adj
.points
[i
].off
== 0) continue;
2215 curr
= GRID(state
, is
->x
+dx
, is
->y
+dy
);
2216 if (curr
& mtype
) continue; /* don't allow changes to marked lines. */
2217 if (ui
->drag_is_noline
) {
2218 if (curr
& gtype
) continue; /* no no-line where already a line */
2220 if (POSSIBLES(state
, dx
, is
->x
+dx
, is
->y
+dy
) == 0) continue; /* no line if !possible. */
2221 if (curr
& ntype
) continue; /* can't have a bridge where there's a no-line. */
2224 if (is
->adj
.points
[i
].dx
== dx
&&
2225 is
->adj
.points
[i
].dy
== dy
) {
2226 ui
->dragx_dst
= ISLAND_ORTHX(is
,i
);
2227 ui
->dragy_dst
= ISLAND_ORTHY(is
,i
);
2230 /*debug(("update_drag src (%d,%d) d(%d,%d) dst (%d,%d)\n",
2231 ui->dragx_src, ui->dragy_src, dx, dy,
2232 ui->dragx_dst, ui->dragy_dst));*/
2236 static char *finish_drag(game_state
*state
, game_ui
*ui
)
2240 if (ui
->dragx_src
== -1 || ui
->dragy_src
== -1)
2242 if (ui
->dragx_dst
== -1 || ui
->dragy_dst
== -1)
2243 return ui_cancel_drag(ui
);
2245 if (ui
->drag_is_noline
) {
2246 sprintf(buf
, "N%d,%d,%d,%d",
2247 ui
->dragx_src
, ui
->dragy_src
,
2248 ui
->dragx_dst
, ui
->dragy_dst
);
2250 sprintf(buf
, "L%d,%d,%d,%d,%d",
2251 ui
->dragx_src
, ui
->dragy_src
,
2252 ui
->dragx_dst
, ui
->dragy_dst
, ui
->nlines
);
2260 static char *interpret_move(game_state
*state
, game_ui
*ui
, game_drawstate
*ds
,
2261 int x
, int y
, int button
)
2263 int gx
= FROMCOORD(x
), gy
= FROMCOORD(y
);
2265 grid_type ggrid
= INGRID(state
,gx
,gy
) ?
GRID(state
,gx
,gy
) : 0;
2267 if (button
== LEFT_BUTTON
|| button
== RIGHT_BUTTON
) {
2268 if (!INGRID(state
, gx
, gy
)) return NULL
;
2269 ui
->cur_visible
= 0;
2270 if ((ggrid
& G_ISLAND
) && !(ggrid
& G_MARK
)) {
2275 return ui_cancel_drag(ui
);
2276 } else if (button
== LEFT_DRAG
|| button
== RIGHT_DRAG
) {
2277 if (gx
!= ui
->dragx_src
|| gy
!= ui
->dragy_src
) {
2279 ui
->drag_is_noline
= (button
== RIGHT_DRAG
) ?
1 : 0;
2280 return update_drag_dst(state
, ui
, ds
, x
, y
);
2282 /* cancel a drag when we go back to the starting point */
2287 } else if (button
== LEFT_RELEASE
|| button
== RIGHT_RELEASE
) {
2289 return finish_drag(state
, ui
);
2292 if (!INGRID(state
, gx
, gy
)) return NULL
;
2293 if (!(GRID(state
, gx
, gy
) & G_ISLAND
)) return NULL
;
2294 sprintf(buf
, "M%d,%d", gx
, gy
);
2297 } else if (button
== 'h' || button
== 'H') {
2298 game_state
*solved
= dup_game(state
);
2299 solve_for_hint(solved
);
2300 ret
= game_state_diff(state
, solved
);
2303 } else if (IS_CURSOR_MOVE(button
)) {
2304 ui
->cur_visible
= 1;
2306 int nx
= ui
->cur_x
, ny
= ui
->cur_y
;
2308 move_cursor(button
, &nx
, &ny
, state
->w
, state
->h
, 0);
2309 update_drag_dst(state
, ui
, ds
,
2310 COORD(nx
)+TILE_SIZE
/2,
2311 COORD(ny
)+TILE_SIZE
/2);
2312 return finish_drag(state
, ui
);
2314 int dx
= (button
== CURSOR_RIGHT
) ?
+1 : (button
== CURSOR_LEFT
) ?
-1 : 0;
2315 int dy
= (button
== CURSOR_DOWN
) ?
+1 : (button
== CURSOR_UP
) ?
-1 : 0;
2316 int dorthx
= 1 - abs(dx
), dorthy
= 1 - abs(dy
);
2317 int dir
, orth
, nx
= x
, ny
= y
;
2319 /* 'orthorder' is a tweak to ensure that if you press RIGHT and
2320 * happen to move upwards, when you press LEFT you then tend
2321 * downwards (rather than upwards again). */
2322 int orthorder
= (button
== CURSOR_LEFT
|| button
== CURSOR_UP
) ?
1 : -1;
2324 /* This attempts to find an island in the direction you're
2325 * asking for, broadly speaking. If you ask to go right, for
2326 * example, it'll look for islands to the right and slightly
2327 * above or below your current horiz. position, allowing
2328 * further above/below the further away it searches. */
2330 assert(GRID(state
, ui
->cur_x
, ui
->cur_y
) & G_ISLAND
);
2331 /* currently this is depth-first (so orthogonally-adjacent
2332 * islands across the other side of the grid will be moved to
2333 * before closer islands slightly offset). Swap the order of
2334 * these two loops to change to breadth-first search. */
2335 for (orth
= 0; ; orth
++) {
2337 for (dir
= 1; ; dir
++) {
2340 if (orth
> dir
) continue; /* only search in cone outwards. */
2342 nx
= ui
->cur_x
+ dir
*dx
+ orth
*dorthx
*orthorder
;
2343 ny
= ui
->cur_y
+ dir
*dy
+ orth
*dorthy
*orthorder
;
2344 if (INGRID(state
, nx
, ny
)) {
2345 dingrid
= oingrid
= 1;
2346 if (GRID(state
, nx
, ny
) & G_ISLAND
) goto found
;
2349 nx
= ui
->cur_x
+ dir
*dx
- orth
*dorthx
*orthorder
;
2350 ny
= ui
->cur_y
+ dir
*dy
- orth
*dorthy
*orthorder
;
2351 if (INGRID(state
, nx
, ny
)) {
2352 dingrid
= oingrid
= 1;
2353 if (GRID(state
, nx
, ny
) & G_ISLAND
) goto found
;
2356 if (!dingrid
) break;
2358 if (!oingrid
) return "";
2367 } else if (IS_CURSOR_SELECT(button
)) {
2368 if (!ui
->cur_visible
) {
2369 ui
->cur_visible
= 1;
2374 if (ui
->dragx_dst
== -1 && ui
->dragy_dst
== -1) {
2375 sprintf(buf
, "M%d,%d", ui
->cur_x
, ui
->cur_y
);
2380 grid_type v
= GRID(state
, ui
->cur_x
, ui
->cur_y
);
2383 ui
->dragx_src
= ui
->cur_x
;
2384 ui
->dragy_src
= ui
->cur_y
;
2385 ui
->dragx_dst
= ui
->dragy_dst
= -1;
2386 ui
->drag_is_noline
= (button
== CURSOR_SELECT2
) ?
1 : 0;
2390 } else if (button
== 'g' || button
== 'G') {
2391 ui
->show_hints
= 1 - ui
->show_hints
;
2398 static game_state
*execute_move(game_state
*state
, char *move
)
2400 game_state
*ret
= dup_game(state
);
2401 int x1
, y1
, x2
, y2
, nl
, n
;
2402 struct island
*is1
, *is2
;
2405 debug(("execute_move: %s\n", move
));
2407 if (!*move
) goto badmove
;
2413 } else if (c
== 'L') {
2414 if (sscanf(move
, "%d,%d,%d,%d,%d%n",
2415 &x1
, &y1
, &x2
, &y2
, &nl
, &n
) != 5)
2417 if (!INGRID(ret
, x1
, y1
) || !INGRID(ret
, x2
, y2
))
2419 is1
= INDEX(ret
, gridi
, x1
, y1
);
2420 is2
= INDEX(ret
, gridi
, x2
, y2
);
2421 if (!is1
|| !is2
) goto badmove
;
2422 if (nl
< 0 || nl
> state
->maxb
) goto badmove
;
2423 island_join(is1
, is2
, nl
, 0);
2424 } else if (c
== 'N') {
2425 if (sscanf(move
, "%d,%d,%d,%d%n",
2426 &x1
, &y1
, &x2
, &y2
, &n
) != 4)
2428 if (!INGRID(ret
, x1
, y1
) || !INGRID(ret
, x2
, y2
))
2430 is1
= INDEX(ret
, gridi
, x1
, y1
);
2431 is2
= INDEX(ret
, gridi
, x2
, y2
);
2432 if (!is1
|| !is2
) goto badmove
;
2433 island_join(is1
, is2
, -1, 0);
2434 } else if (c
== 'M') {
2435 if (sscanf(move
, "%d,%d%n",
2438 if (!INGRID(ret
, x1
, y1
))
2440 is1
= INDEX(ret
, gridi
, x1
, y1
);
2441 if (!is1
) goto badmove
;
2442 island_togglemark(is1
);
2449 else if (*move
) goto badmove
;
2452 map_update_possibles(ret
);
2453 if (map_check(ret
)) {
2454 debug(("Game completed.\n"));
2460 debug(("%s: unrecognised move.\n", move
));
2465 static char *solve_game(game_state
*state
, game_state
*currstate
,
2466 char *aux
, char **error
)
2472 debug(("solve_game: aux = %s\n", aux
));
2473 solved
= execute_move(state
, aux
);
2475 *error
= "Generated aux string is not a valid move (!).";
2479 solved
= dup_game(state
);
2480 /* solve with max strength... */
2481 if (solve_from_scratch(solved
, 10) == 0) {
2483 *error
= "Game does not have a (non-recursive) solution.";
2487 ret
= game_state_diff(currstate
, solved
);
2489 debug(("solve_game: ret = %s\n", ret
));
2493 /* ----------------------------------------------------------------------
2497 static void game_compute_size(game_params
*params
, int tilesize
,
2500 /* Ick: fake up `ds->tilesize' for macro expansion purposes */
2501 struct { int tilesize
; } ads
, *ds
= &ads
;
2502 ads
.tilesize
= tilesize
;
2504 *x
= TILE_SIZE
* params
->w
+ 2 * BORDER
;
2505 *y
= TILE_SIZE
* params
->h
+ 2 * BORDER
;
2508 static void game_set_size(drawing
*dr
, game_drawstate
*ds
,
2509 game_params
*params
, int tilesize
)
2511 ds
->tilesize
= tilesize
;
2514 static float *game_colours(frontend
*fe
, int *ncolours
)
2516 float *ret
= snewn(3 * NCOLOURS
, float);
2519 game_mkhighlight(fe
, ret
, COL_BACKGROUND
, COL_HIGHLIGHT
, COL_LOWLIGHT
);
2521 for (i
= 0; i
< 3; i
++) {
2522 ret
[COL_FOREGROUND
* 3 + i
] = 0.0F
;
2523 ret
[COL_HINT
* 3 + i
] = ret
[COL_LOWLIGHT
* 3 + i
];
2524 ret
[COL_GRID
* 3 + i
] =
2525 (ret
[COL_HINT
* 3 + i
] + ret
[COL_BACKGROUND
* 3 + i
]) * 0.5F
;
2526 ret
[COL_MARK
* 3 + i
] = ret
[COL_HIGHLIGHT
* 3 + i
];
2528 ret
[COL_WARNING
* 3 + 0] = 1.0F
;
2529 ret
[COL_WARNING
* 3 + 1] = 0.25F
;
2530 ret
[COL_WARNING
* 3 + 2] = 0.25F
;
2532 ret
[COL_SELECTED
* 3 + 0] = 0.25F
;
2533 ret
[COL_SELECTED
* 3 + 1] = 1.00F
;
2534 ret
[COL_SELECTED
* 3 + 2] = 0.25F
;
2536 ret
[COL_CURSOR
* 3 + 0] = min(ret
[COL_BACKGROUND
* 3 + 0] * 1.4F
, 1.0F
);
2537 ret
[COL_CURSOR
* 3 + 1] = ret
[COL_BACKGROUND
* 3 + 1] * 0.8F
;
2538 ret
[COL_CURSOR
* 3 + 2] = ret
[COL_BACKGROUND
* 3 + 2] * 0.8F
;
2540 *ncolours
= NCOLOURS
;
2544 static game_drawstate
*game_new_drawstate(drawing
*dr
, game_state
*state
)
2546 struct game_drawstate
*ds
= snew(struct game_drawstate
);
2547 int wh
= state
->w
*state
->h
;
2553 ds
->grid
= snewn(wh
, grid_type
);
2554 memset(ds
->grid
, -1, wh
*sizeof(grid_type
));
2555 ds
->lv
= snewn(wh
, int);
2556 ds
->lh
= snewn(wh
, int);
2557 memset(ds
->lv
, 0, wh
*sizeof(int));
2558 memset(ds
->lh
, 0, wh
*sizeof(int));
2564 static void game_free_drawstate(drawing
*dr
, game_drawstate
*ds
)
2572 #define LINE_WIDTH (TILE_SIZE/8)
2573 #define TS8(x) (((x)*TILE_SIZE)/8)
2575 #define OFFSET(thing) ((TILE_SIZE/2) - ((thing)/2))
2577 static void lines_vert(drawing
*dr
, game_drawstate
*ds
,
2578 int ox
, int oy
, int lv
, int col
, grid_type v
)
2580 int lw
= LINE_WIDTH
, gw
= LINE_WIDTH
, bw
, i
, loff
;
2581 while ((bw
= lw
* lv
+ gw
* (lv
+1)) > TILE_SIZE
)
2585 draw_rect(dr
, ox
+ loff
, oy
, bw
, TILE_SIZE
, COL_MARK
);
2586 for (i
= 0; i
< lv
; i
++, loff
+= lw
+ gw
)
2587 draw_rect(dr
, ox
+ loff
+ gw
, oy
, lw
, TILE_SIZE
, col
);
2590 static void lines_horiz(drawing
*dr
, game_drawstate
*ds
,
2591 int ox
, int oy
, int lh
, int col
, grid_type v
)
2593 int lw
= LINE_WIDTH
, gw
= LINE_WIDTH
, bw
, i
, loff
;
2594 while ((bw
= lw
* lh
+ gw
* (lh
+1)) > TILE_SIZE
)
2598 draw_rect(dr
, ox
, oy
+ loff
, TILE_SIZE
, bw
, COL_MARK
);
2599 for (i
= 0; i
< lh
; i
++, loff
+= lw
+ gw
)
2600 draw_rect(dr
, ox
, oy
+ loff
+ gw
, TILE_SIZE
, lw
, col
);
2603 static void line_cross(drawing
*dr
, game_drawstate
*ds
,
2604 int ox
, int oy
, int col
, grid_type v
)
2607 draw_line(dr
, ox
, oy
, ox
+off
, oy
+off
, col
);
2608 draw_line(dr
, ox
+off
, oy
, ox
, oy
+off
, col
);
2611 static int between_island(game_state
*state
, int sx
, int sy
, int dx
, int dy
)
2613 int x
= sx
- dx
, y
= sy
- dy
;
2615 while (INGRID(state
, x
, y
)) {
2616 if (GRID(state
, x
, y
) & G_ISLAND
) goto found
;
2621 x
= sx
+ dx
, y
= sy
+ dy
;
2622 while (INGRID(state
, x
, y
)) {
2623 if (GRID(state
, x
, y
) & G_ISLAND
) return 1;
2629 static void lines_lvlh(game_state
*state
, game_ui
*ui
, int x
, int y
, grid_type v
,
2630 int *lv_r
, int *lh_r
)
2634 if (v
& G_LINEV
) lv
= INDEX(state
,lines
,x
,y
);
2635 if (v
& G_LINEH
) lh
= INDEX(state
,lines
,x
,y
);
2637 if (ui
->show_hints
) {
2638 if (between_island(state
, x
, y
, 0, 1) && !lv
) lv
= 1;
2639 if (between_island(state
, x
, y
, 1, 0) && !lh
) lh
= 1;
2641 /*debug(("lvlh: (%d,%d) v 0x%x lv %d lh %d.\n", x, y, v, lv, lh));*/
2642 *lv_r
= lv
; *lh_r
= lh
;
2645 static void dsf_debug_draw(drawing
*dr
,
2646 game_state
*state
, game_drawstate
*ds
,
2650 int ts
= TILE_SIZE
/2;
2651 int ox
= COORD(x
) + ts
/2, oy
= COORD(y
) + ts
/2;
2654 sprintf(str
, "%d", dsf_canonify(state
->solver
->dsf
, DINDEX(x
,y
)));
2655 draw_text(dr
, ox
, oy
, FONT_VARIABLE
, ts
,
2656 ALIGN_VCENTRE
| ALIGN_HCENTRE
, COL_WARNING
, str
);
2660 static void lines_redraw(drawing
*dr
,
2661 game_state
*state
, game_drawstate
*ds
, game_ui
*ui
,
2662 int x
, int y
, grid_type v
, int lv
, int lh
)
2664 int ox
= COORD(x
), oy
= COORD(y
);
2665 int vcol
= (v
& G_FLASH
) ? COL_HIGHLIGHT
:
2666 (v
& G_WARN
) ? COL_WARNING
: COL_FOREGROUND
, hcol
= vcol
;
2667 grid_type todraw
= v
& G_NOLINE
;
2670 if (ui
->todraw
& G_FLAGSH
) hcol
= COL_SELECTED
;
2671 if (ui
->todraw
& G_FLAGSV
) vcol
= COL_SELECTED
;
2672 todraw
|= ui
->todraw
;
2675 draw_rect(dr
, ox
, oy
, TILE_SIZE
, TILE_SIZE
, COL_BACKGROUND
);
2677 draw_rect(dr, ox+TILE_SIZE/4, oy+TILE_SIZE/4,
2678 TILE_SIZE/2, TILE_SIZE/2, COL_CURSOR);*/
2681 if (ui
->show_hints
) {
2682 if (between_island(state
, x
, y
, 0, 1) && !(v
& G_LINEV
))
2684 if (between_island(state
, x
, y
, 1, 0) && !(v
& G_LINEH
))
2688 draw_rect_outline(dr
, ox
, oy
, TILE_SIZE
, TILE_SIZE
, COL_GRID
);
2691 if (todraw
& G_NOLINEV
) {
2692 line_cross(dr
, ds
, ox
+ TS8(3), oy
+ TS8(1), vcol
, todraw
);
2693 line_cross(dr
, ds
, ox
+ TS8(3), oy
+ TS8(5), vcol
, todraw
);
2695 if (todraw
& G_NOLINEH
) {
2696 line_cross(dr
, ds
, ox
+ TS8(1), oy
+ TS8(3), hcol
, todraw
);
2697 line_cross(dr
, ds
, ox
+ TS8(5), oy
+ TS8(3), hcol
, todraw
);
2699 /* if we're drawing a real line and a hint, make sure we draw the real
2701 if (lv
&& vcol
== COL_HINT
) lines_vert(dr
, ds
, ox
, oy
, lv
, vcol
, v
);
2702 if (lh
) lines_horiz(dr
, ds
, ox
, oy
, lh
, hcol
, v
);
2703 if (lv
&& vcol
!= COL_HINT
) lines_vert(dr
, ds
, ox
, oy
, lv
, vcol
, v
);
2705 dsf_debug_draw(dr
, state
, ds
, x
, y
);
2706 draw_update(dr
, ox
, oy
, TILE_SIZE
, TILE_SIZE
);
2709 #define ISLAND_RADIUS ((TILE_SIZE*12)/20)
2710 #define ISLAND_NUMSIZE(is) \
2711 (((is)->count < 10) ? (TILE_SIZE*7)/10 : (TILE_SIZE*5)/10)
2713 static void island_redraw(drawing
*dr
,
2714 game_state
*state
, game_drawstate
*ds
,
2715 struct island
*is
, grid_type v
)
2717 /* These overlap the edges of their squares, which is why they're drawn later.
2718 * We know they can't overlap each other because they're not allowed within 2
2719 * squares of each other. */
2720 int half
= TILE_SIZE
/2;
2721 int ox
= COORD(is
->x
) + half
, oy
= COORD(is
->y
) + half
;
2722 int orad
= ISLAND_RADIUS
, irad
= orad
- LINE_WIDTH
;
2723 int updatesz
= orad
*2+1;
2724 int tcol
= (v
& G_FLASH
) ? COL_HIGHLIGHT
:
2725 (v
& G_WARN
) ? COL_WARNING
: COL_FOREGROUND
;
2726 int col
= (v
& G_ISSEL
) ? COL_SELECTED
: tcol
;
2727 int bg
= (v
& G_CURSOR
) ? COL_CURSOR
:
2728 (v
& G_MARK
) ? COL_MARK
: COL_BACKGROUND
;
2732 draw_rect_outline(dr
, COORD(is
->x
), COORD(is
->y
),
2733 TILE_SIZE
, TILE_SIZE
, COL_GRID
);
2736 /* draw a thick circle */
2737 draw_circle(dr
, ox
, oy
, orad
, col
, col
);
2738 draw_circle(dr
, ox
, oy
, irad
, bg
, bg
);
2740 sprintf(str
, "%d", is
->count
);
2741 draw_text(dr
, ox
, oy
, FONT_VARIABLE
, ISLAND_NUMSIZE(is
),
2742 ALIGN_VCENTRE
| ALIGN_HCENTRE
, tcol
, str
);
2744 dsf_debug_draw(dr
, state
, ds
, is
->x
, is
->y
);
2745 draw_update(dr
, ox
- orad
, oy
- orad
, updatesz
, updatesz
);
2748 static void game_redraw(drawing
*dr
, game_drawstate
*ds
, game_state
*oldstate
,
2749 game_state
*state
, int dir
, game_ui
*ui
,
2750 float animtime
, float flashtime
)
2752 int x
, y
, force
= 0, i
, j
, redraw
, lv
, lh
;
2753 grid_type v
, dsv
, flash
= 0;
2754 struct island
*is
, *is_drag_src
= NULL
, *is_drag_dst
= NULL
;
2757 int f
= (int)(flashtime
* 5 / FLASH_TIME
);
2758 if (f
== 1 || f
== 3) flash
= G_FLASH
;
2761 /* Clear screen, if required. */
2764 TILE_SIZE
* ds
->w
+ 2 * BORDER
,
2765 TILE_SIZE
* ds
->h
+ 2 * BORDER
, COL_BACKGROUND
);
2767 draw_rect_outline(dr
,
2768 COORD(0)-1, COORD(0)-1,
2769 TILE_SIZE
* ds
->w
+ 2, TILE_SIZE
* ds
->h
+ 2,
2772 draw_update(dr
, 0, 0,
2773 TILE_SIZE
* ds
->w
+ 2 * BORDER
,
2774 TILE_SIZE
* ds
->h
+ 2 * BORDER
);
2779 if (ui
->dragx_src
!= -1 && ui
->dragy_src
!= -1) {
2781 is_drag_src
= INDEX(state
, gridi
, ui
->dragx_src
, ui
->dragy_src
);
2782 assert(is_drag_src
);
2783 if (ui
->dragx_dst
!= -1 && ui
->dragy_dst
!= -1) {
2784 is_drag_dst
= INDEX(state
, gridi
, ui
->dragx_dst
, ui
->dragy_dst
);
2785 assert(is_drag_dst
);
2790 if (ui
->show_hints
!= ds
->show_hints
) {
2792 ds
->show_hints
= ui
->show_hints
;
2795 /* Draw all lines (and hints, if we want), but *not* islands. */
2796 for (x
= 0; x
< ds
->w
; x
++) {
2797 for (y
= 0; y
< ds
->h
; y
++) {
2798 v
= GRID(state
, x
, y
) | flash
;
2799 dsv
= GRID(ds
,x
,y
) & ~G_REDRAW
;
2801 if (v
& G_ISLAND
) continue;
2804 if (WITHIN(x
,is_drag_src
->x
, is_drag_dst
->x
) &&
2805 WITHIN(y
,is_drag_src
->y
, is_drag_dst
->y
))
2808 lines_lvlh(state
, ui
, x
, y
, v
, &lv
, &lh
);
2810 /*if (ui->cur_visible && ui->cur_x == x && ui->cur_y == y)
2814 lv
!= INDEX(ds
,lv
,x
,y
) ||
2815 lh
!= INDEX(ds
,lh
,x
,y
) ||
2817 GRID(ds
, x
, y
) = v
| G_REDRAW
;
2818 INDEX(ds
,lv
,x
,y
) = lv
;
2819 INDEX(ds
,lh
,x
,y
) = lh
;
2820 lines_redraw(dr
, state
, ds
, ui
, x
, y
, v
, lv
, lh
);
2822 GRID(ds
,x
,y
) &= ~G_REDRAW
;
2827 for (i
= 0; i
< state
->n_islands
; i
++) {
2828 is
= &state
->islands
[i
];
2829 v
= GRID(state
, is
->x
, is
->y
) | flash
;
2832 for (j
= 0; j
< is
->adj
.npoints
; j
++) {
2833 if (GRID(ds
,is
->adj
.points
[j
].x
,is
->adj
.points
[j
].y
) & G_REDRAW
) {
2839 if (is
== is_drag_src
)
2841 else if (is_drag_dst
&& is
== is_drag_dst
)
2845 if (island_impossible(is
, v
& G_MARK
)) v
|= G_WARN
;
2847 if (ui
->cur_visible
&& ui
->cur_x
== is
->x
&& ui
->cur_y
== is
->y
)
2850 if ((v
!= GRID(ds
, is
->x
, is
->y
)) || force
|| redraw
) {
2851 GRID(ds
,is
->x
,is
->y
) = v
;
2852 island_redraw(dr
, state
, ds
, is
, v
);
2857 static float game_anim_length(game_state
*oldstate
, game_state
*newstate
,
2858 int dir
, game_ui
*ui
)
2863 static float game_flash_length(game_state
*oldstate
, game_state
*newstate
,
2864 int dir
, game_ui
*ui
)
2866 if (!oldstate
->completed
&& newstate
->completed
&&
2867 !oldstate
->solved
&& !newstate
->solved
)
2873 static int game_status(game_state
*state
)
2875 return state
->completed ?
+1 : 0;
2878 static int game_timing_state(game_state
*state
, game_ui
*ui
)
2883 static void game_print_size(game_params
*params
, float *x
, float *y
)
2887 /* 10mm squares by default. */
2888 game_compute_size(params
, 1000, &pw
, &ph
);
2893 static void game_print(drawing
*dr
, game_state
*state
, int ts
)
2895 int ink
= print_mono_colour(dr
, 0);
2896 int paper
= print_mono_colour(dr
, 1);
2897 int x
, y
, cx
, cy
, i
, nl
;
2901 /* Ick: fake up `ds->tilesize' for macro expansion purposes */
2902 game_drawstate ads
, *ds
= &ads
;
2905 /* I don't think this wants a border. */
2908 loff
= ts
/ (8 * sqrt((state
->params
.maxb
- 1)));
2909 print_line_width(dr
, ts
/ 12);
2910 for (x
= 0; x
< state
->w
; x
++) {
2911 for (y
= 0; y
< state
->h
; y
++) {
2912 cx
= COORD(x
); cy
= COORD(y
);
2913 grid
= GRID(state
,x
,y
);
2914 nl
= INDEX(state
,lines
,x
,y
);
2916 if (grid
& G_ISLAND
) continue;
2917 if (grid
& G_LINEV
) {
2918 for (i
= 0; i
< nl
; i
++)
2919 draw_line(dr
, cx
+ts
/2+(2*i
-nl
+1)*loff
, cy
,
2920 cx
+ts
/2+(2*i
-nl
+1)*loff
, cy
+ts
, ink
);
2922 if (grid
& G_LINEH
) {
2923 for (i
= 0; i
< nl
; i
++)
2924 draw_line(dr
, cx
, cy
+ts
/2+(2*i
-nl
+1)*loff
,
2925 cx
+ts
, cy
+ts
/2+(2*i
-nl
+1)*loff
, ink
);
2931 for (i
= 0; i
< state
->n_islands
; i
++) {
2933 struct island
*is
= &state
->islands
[i
];
2934 grid
= GRID(state
, is
->x
, is
->y
);
2935 cx
= COORD(is
->x
) + ts
/2;
2936 cy
= COORD(is
->y
) + ts
/2;
2938 draw_circle(dr
, cx
, cy
, ISLAND_RADIUS
, paper
, ink
);
2940 sprintf(str
, "%d", is
->count
);
2941 draw_text(dr
, cx
, cy
, FONT_VARIABLE
, ISLAND_NUMSIZE(is
),
2942 ALIGN_VCENTRE
| ALIGN_HCENTRE
, ink
, str
);
2947 #define thegame bridges
2950 const struct game thegame
= {
2951 "Bridges", "games.bridges", "bridges",
2958 TRUE
, game_configure
, custom_params
,
2966 TRUE
, game_can_format_as_text_now
, game_text_format
,
2974 PREFERRED_TILE_SIZE
, game_compute_size
, game_set_size
,
2977 game_free_drawstate
,
2982 TRUE
, FALSE
, game_print_size
, game_print
,
2983 FALSE
, /* wants_statusbar */
2984 FALSE
, game_timing_state
,
2985 REQUIRE_RBUTTON
, /* flags */
2988 /* vim: set shiftwidth=4 tabstop=8: */