2 * bridges.c: Implementation of the Nikoli game 'Bridges'.
6 * * write a recursive solver?
18 /* Turn this on for hints about which lines are considered possibilities. */
22 /* --- structures for params, state, etc. --- */
26 #define PREFERRED_TILE_SIZE 24
27 #define TILE_SIZE (ds->tilesize)
28 #define BORDER (TILE_SIZE / 2)
30 #define COORD(x) ( (x) * TILE_SIZE + BORDER )
31 #define FROMCOORD(x) ( ((x) - BORDER + TILE_SIZE) / TILE_SIZE - 1 )
33 #define FLASH_TIME 0.50F
38 COL_HIGHLIGHT, COL_LOWLIGHT,
39 COL_SELECTED, COL_MARK,
48 int islands, expansion; /* %age of island squares, %age chance of expansion */
49 int allowloops, difficulty;
52 /* general flags used by all structs */
53 #define G_ISLAND 0x0001
54 #define G_LINEV 0x0002 /* contains a vert. line */
55 #define G_LINEH 0x0004 /* contains a horiz. line (mutex with LINEV) */
56 #define G_LINE (G_LINEV|G_LINEH)
57 #define G_MARKV 0x0008
58 #define G_MARKH 0x0010
59 #define G_MARK (G_MARKV|G_MARKH)
60 #define G_NOLINEV 0x0020
61 #define G_NOLINEH 0x0040
62 #define G_NOLINE (G_NOLINEV|G_NOLINEH)
64 /* flags used by the drawstate */
65 #define G_ISSEL 0x0080
66 #define G_REDRAW 0x0100
67 #define G_FLASH 0x0200
69 #define G_CURSOR 0x0800
71 /* flags used by the solver etc. */
72 #define G_SWEEP 0x1000
74 #define G_FLAGSH (G_LINEH|G_MARKH|G_NOLINEH)
75 #define G_FLAGSV (G_LINEV|G_MARKV|G_NOLINEV)
77 typedef unsigned int grid_type; /* change me later if we invent > 16 bits of flags. */
80 int *dsf, *comptspaces;
81 int *tmpdsf, *tmpcompspaces;
85 /* state->gridi is an optimisation; it stores the pointer to the island
86 * structs indexed by (x,y). It's not strictly necessary (we could use
87 * find234 instead), but Purify showed that board generation (mostly the solver)
88 * was spending 60% of its time in find234. */
90 struct surrounds { /* cloned from lightup.c */
91 struct { int x, y, dx, dy, off; } points[4];
92 int npoints, nislands;
102 int w, h, completed, solved, allowloops, maxb;
103 grid_type *grid, *scratch;
104 struct island *islands;
105 int n_islands, n_islands_alloc;
106 game_params params; /* used by the aux solver. */
107 #define N_WH_ARRAYS 5
108 char *wha, *possv, *possh, *lines, *maxv, *maxh;
109 struct island **gridi;
110 struct solver_state *solver; /* refcounted */
113 #define GRIDSZ(s) ((s)->w * (s)->h * sizeof(grid_type))
115 #define INGRID(s,x,y) ((x) >= 0 && (x) < (s)->w && (y) >= 0 && (y) < (s)->h)
117 #define DINDEX(x,y) ((y)*state->w + (x))
119 #define INDEX(s,g,x,y) ((s)->g[(y)*((s)->w) + (x)])
120 #define IDX(s,g,i) ((s)->g[(i)])
121 #define GRID(s,x,y) INDEX(s,grid,x,y)
122 #define SCRATCH(s,x,y) INDEX(s,scratch,x,y)
123 #define POSSIBLES(s,dx,x,y) ((dx) ? (INDEX(s,possh,x,y)) : (INDEX(s,possv,x,y)))
124 #define MAXIMUM(s,dx,x,y) ((dx) ? (INDEX(s,maxh,x,y)) : (INDEX(s,maxv,x,y)))
126 #define GRIDCOUNT(s,x,y,f) ((GRID(s,x,y) & (f)) ? (INDEX(s,lines,x,y)) : 0)
128 #define WITHIN2(x,min,max) (((x) < (min)) ? 0 : (((x) > (max)) ? 0 : 1))
129 #define WITHIN(x,min,max) ((min) > (max) ? \
130 WITHIN2(x,max,min) : WITHIN2(x,min,max))
132 /* --- island struct and tree support functions --- */
134 #define ISLAND_ORTH(is,j,f,df) \
135 (is->f + (is->adj.points[(j)].off*is->adj.points[(j)].df))
137 #define ISLAND_ORTHX(is,j) ISLAND_ORTH(is,j,x,dx)
138 #define ISLAND_ORTHY(is,j) ISLAND_ORTH(is,j,y,dy)
140 static void fixup_islands_for_realloc(game_state *state)
144 for (i = 0; i < state->w*state->h; i++) state->gridi[i] = NULL;
145 for (i = 0; i < state->n_islands; i++) {
146 struct island *is = &state->islands[i];
148 INDEX(state, gridi, is->x, is->y) = is;
152 static int game_can_format_as_text_now(game_params *params)
157 static char *game_text_format(game_state *state)
164 len = (state->h) * (state->w+1) + 1;
165 ret = snewn(len, char);
168 for (y = 0; y < state->h; y++) {
169 for (x = 0; x < state->w; x++) {
170 grid = GRID(state,x,y);
171 nl = INDEX(state,lines,x,y);
172 is = INDEX(state, gridi, x, y);
174 *p++ = '0' + is->count;
175 } else if (grid & G_LINEV) {
176 *p++ = (nl > 1) ? '"' : (nl == 1) ? '|' : '!'; /* gaah, want a double-bar. */
177 } else if (grid & G_LINEH) {
178 *p++ = (nl > 1) ? '=' : (nl == 1) ? '-' : '~';
187 assert(p - ret == len);
191 static void debug_state(game_state *state)
193 char *textversion = game_text_format(state);
194 debug(("%s", textversion));
198 /*static void debug_possibles(game_state *state)
201 debug(("possh followed by possv\n"));
202 for (y = 0; y < state->h; y++) {
203 for (x = 0; x < state->w; x++) {
204 debug(("%d", POSSIBLES(state, 1, x, y)));
207 for (x = 0; x < state->w; x++) {
208 debug(("%d", POSSIBLES(state, 0, x, y)));
213 for (y = 0; y < state->h; y++) {
214 for (x = 0; x < state->w; x++) {
215 debug(("%d", MAXIMUM(state, 1, x, y)));
218 for (x = 0; x < state->w; x++) {
219 debug(("%d", MAXIMUM(state, 0, x, y)));
226 static void island_set_surrounds(struct island *is)
228 assert(INGRID(is->state,is->x,is->y));
229 is->adj.npoints = is->adj.nislands = 0;
230 #define ADDPOINT(cond,ddx,ddy) do {\
232 is->adj.points[is->adj.npoints].x = is->x+(ddx); \
233 is->adj.points[is->adj.npoints].y = is->y+(ddy); \
234 is->adj.points[is->adj.npoints].dx = (ddx); \
235 is->adj.points[is->adj.npoints].dy = (ddy); \
236 is->adj.points[is->adj.npoints].off = 0; \
239 ADDPOINT(is->x > 0, -1, 0);
240 ADDPOINT(is->x < (is->state->w-1), +1, 0);
241 ADDPOINT(is->y > 0, 0, -1);
242 ADDPOINT(is->y < (is->state->h-1), 0, +1);
245 static void island_find_orthogonal(struct island *is)
247 /* fills in the rest of the 'surrounds' structure, assuming
248 * all other islands are now in place. */
249 int i, x, y, dx, dy, off;
251 is->adj.nislands = 0;
252 for (i = 0; i < is->adj.npoints; i++) {
253 dx = is->adj.points[i].dx;
254 dy = is->adj.points[i].dy;
258 is->adj.points[i].off = 0;
259 while (INGRID(is->state, x, y)) {
260 if (GRID(is->state, x, y) & G_ISLAND) {
261 is->adj.points[i].off = off;
263 /*debug(("island (%d,%d) has orth is. %d*(%d,%d) away at (%d,%d).\n",
264 is->x, is->y, off, dx, dy,
265 ISLAND_ORTHX(is,i), ISLAND_ORTHY(is,i)));*/
268 off++; x += dx; y += dy;
275 static int island_hasbridge(struct island *is, int direction)
277 int x = is->adj.points[direction].x;
278 int y = is->adj.points[direction].y;
279 grid_type gline = is->adj.points[direction].dx ? G_LINEH : G_LINEV;
281 if (GRID(is->state, x, y) & gline) return 1;
285 static struct island *island_find_connection(struct island *is, int adjpt)
289 assert(adjpt < is->adj.npoints);
290 if (!is->adj.points[adjpt].off) return NULL;
291 if (!island_hasbridge(is, adjpt)) return NULL;
293 is_r = INDEX(is->state, gridi,
294 ISLAND_ORTHX(is, adjpt), ISLAND_ORTHY(is, adjpt));
300 static struct island *island_add(game_state *state, int x, int y, int count)
305 assert(!(GRID(state,x,y) & G_ISLAND));
306 GRID(state,x,y) |= G_ISLAND;
309 if (state->n_islands > state->n_islands_alloc) {
310 state->n_islands_alloc = state->n_islands * 2;
312 sresize(state->islands, state->n_islands_alloc, struct island);
315 is = &state->islands[state->n_islands-1];
317 memset(is, 0, sizeof(struct island));
322 island_set_surrounds(is);
325 fixup_islands_for_realloc(state);
327 INDEX(state, gridi, x, y) = is;
333 /* n = -1 means 'flip NOLINE flags [and set line to 0].' */
334 static void island_join(struct island *i1, struct island *i2, int n, int is_max)
336 game_state *state = i1->state;
339 assert(i1->state == i2->state);
340 assert(n >= -1 && n <= i1->state->maxb);
342 if (i1->x == i2->x) {
345 s = i1->y+1; e = i2->y-1;
347 s = i2->y+1; e = i1->y-1;
349 for (y = s; y <= e; y++) {
351 INDEX(state,maxv,x,y) = n;
354 GRID(state,x,y) ^= G_NOLINEV;
356 GRID(state,x,y) &= ~G_LINEV;
358 GRID(state,x,y) |= G_LINEV;
359 INDEX(state,lines,x,y) = n;
363 } else if (i1->y == i2->y) {
366 s = i1->x+1; e = i2->x-1;
368 s = i2->x+1; e = i1->x-1;
370 for (x = s; x <= e; x++) {
372 INDEX(state,maxh,x,y) = n;
375 GRID(state,x,y) ^= G_NOLINEH;
377 GRID(state,x,y) &= ~G_LINEH;
379 GRID(state,x,y) |= G_LINEH;
380 INDEX(state,lines,x,y) = n;
385 assert(!"island_join: islands not orthogonal.");
389 /* Counts the number of bridges currently attached to the island. */
390 static int island_countbridges(struct island *is)
394 for (i = 0; i < is->adj.npoints; i++) {
395 c += GRIDCOUNT(is->state,
396 is->adj.points[i].x, is->adj.points[i].y,
397 is->adj.points[i].dx ? G_LINEH : G_LINEV);
399 /*debug(("island count for (%d,%d) is %d.\n", is->x, is->y, c));*/
403 static int island_adjspace(struct island *is, int marks, int missing,
406 int x, y, poss, curr, dx;
407 grid_type gline, mline;
409 x = is->adj.points[direction].x;
410 y = is->adj.points[direction].y;
411 dx = is->adj.points[direction].dx;
412 gline = dx ? G_LINEH : G_LINEV;
415 mline = dx ? G_MARKH : G_MARKV;
416 if (GRID(is->state,x,y) & mline) return 0;
418 poss = POSSIBLES(is->state, dx, x, y);
419 poss = min(poss, missing);
421 curr = GRIDCOUNT(is->state, x, y, gline);
422 poss = min(poss, MAXIMUM(is->state, dx, x, y) - curr);
427 /* Counts the number of bridge spaces left around the island;
428 * expects the possibles to be up-to-date. */
429 static int island_countspaces(struct island *is, int marks)
431 int i, c = 0, missing;
433 missing = is->count - island_countbridges(is);
434 if (missing < 0) return 0;
436 for (i = 0; i < is->adj.npoints; i++) {
437 c += island_adjspace(is, marks, missing, i);
442 static int island_isadj(struct island *is, int direction)
445 grid_type gline, mline;
447 x = is->adj.points[direction].x;
448 y = is->adj.points[direction].y;
450 mline = is->adj.points[direction].dx ? G_MARKH : G_MARKV;
451 gline = is->adj.points[direction].dx ? G_LINEH : G_LINEV;
452 if (GRID(is->state, x, y) & mline) {
453 /* If we're marked (i.e. the thing to attach to is complete)
454 * only count an adjacency if we're already attached. */
455 return GRIDCOUNT(is->state, x, y, gline);
457 /* If we're unmarked, count possible adjacency iff it's
458 * flagged as POSSIBLE. */
459 return POSSIBLES(is->state, is->adj.points[direction].dx, x, y);
464 /* Counts the no. of possible adjacent islands (including islands
465 * we're already connected to). */
466 static int island_countadj(struct island *is)
470 for (i = 0; i < is->adj.npoints; i++) {
471 if (island_isadj(is, i)) nadj++;
476 static void island_togglemark(struct island *is)
479 struct island *is_loop;
481 /* mark the island... */
482 GRID(is->state, is->x, is->y) ^= G_MARK;
484 /* ...remove all marks on non-island squares... */
485 for (x = 0; x < is->state->w; x++) {
486 for (y = 0; y < is->state->h; y++) {
487 if (!(GRID(is->state, x, y) & G_ISLAND))
488 GRID(is->state, x, y) &= ~G_MARK;
492 /* ...and add marks to squares around marked islands. */
493 for (i = 0; i < is->state->n_islands; i++) {
494 is_loop = &is->state->islands[i];
495 if (!(GRID(is_loop->state, is_loop->x, is_loop->y) & G_MARK))
498 for (j = 0; j < is_loop->adj.npoints; j++) {
499 /* if this direction takes us to another island, mark all
500 * squares between the two islands. */
501 if (!is_loop->adj.points[j].off) continue;
502 assert(is_loop->adj.points[j].off > 1);
503 for (o = 1; o < is_loop->adj.points[j].off; o++) {
505 is_loop->x + is_loop->adj.points[j].dx*o,
506 is_loop->y + is_loop->adj.points[j].dy*o) |=
507 is_loop->adj.points[j].dy ? G_MARKV : G_MARKH;
513 static int island_impossible(struct island *is, int strict)
515 int curr = island_countbridges(is), nspc = is->count - curr, nsurrspc;
517 struct island *is_orth;
520 debug(("island at (%d,%d) impossible because full.\n", is->x, is->y));
521 return 1; /* too many bridges */
522 } else if ((curr + island_countspaces(is, 0)) < is->count) {
523 debug(("island at (%d,%d) impossible because not enough spaces.\n", is->x, is->y));
524 return 1; /* impossible to create enough bridges */
525 } else if (strict && curr < is->count) {
526 debug(("island at (%d,%d) impossible because locked.\n", is->x, is->y));
527 return 1; /* not enough bridges and island is locked */
530 /* Count spaces in surrounding islands. */
532 for (i = 0; i < is->adj.npoints; i++) {
533 int ifree, dx = is->adj.points[i].dx;
535 if (!is->adj.points[i].off) continue;
536 poss = POSSIBLES(is->state, dx,
537 is->adj.points[i].x, is->adj.points[i].y);
538 if (poss == 0) continue;
539 is_orth = INDEX(is->state, gridi,
540 ISLAND_ORTHX(is,i), ISLAND_ORTHY(is,i));
543 ifree = is_orth->count - island_countbridges(is_orth);
546 * ifree is the number of bridges unfilled in the other
547 * island, which is clearly an upper bound on the number
548 * of extra bridges this island may run to it.
550 * Another upper bound is the number of bridges unfilled
551 * on the specific line between here and there. We must
552 * take the minimum of both.
554 int bmax = MAXIMUM(is->state, dx,
555 is->adj.points[i].x, is->adj.points[i].y);
556 int bcurr = GRIDCOUNT(is->state,
557 is->adj.points[i].x, is->adj.points[i].y,
558 dx ? G_LINEH : G_LINEV);
559 assert(bcurr <= bmax);
560 nsurrspc += min(ifree, bmax - bcurr);
563 if (nsurrspc < nspc) {
564 debug(("island at (%d,%d) impossible: surr. islands %d spc, need %d.\n",
565 is->x, is->y, nsurrspc, nspc));
566 return 1; /* not enough spaces around surrounding islands to fill this one. */
572 /* --- Game parameter functions --- */
574 #define DEFAULT_PRESET 0
576 const struct game_params bridges_presets[] = {
577 { 7, 7, 2, 30, 10, 1, 0 },
578 { 7, 7, 2, 30, 10, 1, 1 },
579 { 7, 7, 2, 30, 10, 1, 2 },
580 { 10, 10, 2, 30, 10, 1, 0 },
581 { 10, 10, 2, 30, 10, 1, 1 },
582 { 10, 10, 2, 30, 10, 1, 2 },
583 { 15, 15, 2, 30, 10, 1, 0 },
584 { 15, 15, 2, 30, 10, 1, 1 },
585 { 15, 15, 2, 30, 10, 1, 2 },
588 static game_params *default_params(void)
590 game_params *ret = snew(game_params);
591 *ret = bridges_presets[DEFAULT_PRESET];
596 static int game_fetch_preset(int i, char **name, game_params **params)
601 if (i < 0 || i >= lenof(bridges_presets))
604 ret = default_params();
605 *ret = bridges_presets[i];
608 sprintf(buf, "%dx%d %s", ret->w, ret->h,
609 ret->difficulty == 0 ? "easy" :
610 ret->difficulty == 1 ? "medium" : "hard");
616 static void free_params(game_params *params)
621 static game_params *dup_params(game_params *params)
623 game_params *ret = snew(game_params);
624 *ret = *params; /* structure copy */
628 #define EATNUM(x) do { \
629 (x) = atoi(string); \
630 while (*string && isdigit((unsigned char)*string)) string++; \
633 static void decode_params(game_params *params, char const *string)
636 params->h = params->w;
637 if (*string == 'x') {
641 if (*string == 'i') {
643 EATNUM(params->islands);
645 if (*string == 'e') {
647 EATNUM(params->expansion);
649 if (*string == 'm') {
651 EATNUM(params->maxb);
653 params->allowloops = 1;
654 if (*string == 'L') {
656 params->allowloops = 0;
658 if (*string == 'd') {
660 EATNUM(params->difficulty);
664 static char *encode_params(game_params *params, int full)
669 sprintf(buf, "%dx%di%de%dm%d%sd%d",
670 params->w, params->h, params->islands, params->expansion,
671 params->maxb, params->allowloops ? "" : "L",
674 sprintf(buf, "%dx%dm%d%s", params->w, params->h,
675 params->maxb, params->allowloops ? "" : "L");
680 static config_item *game_configure(game_params *params)
685 ret = snewn(8, config_item);
687 ret[0].name = "Width";
688 ret[0].type = C_STRING;
689 sprintf(buf, "%d", params->w);
690 ret[0].sval = dupstr(buf);
693 ret[1].name = "Height";
694 ret[1].type = C_STRING;
695 sprintf(buf, "%d", params->h);
696 ret[1].sval = dupstr(buf);
699 ret[2].name = "Difficulty";
700 ret[2].type = C_CHOICES;
701 ret[2].sval = ":Easy:Medium:Hard";
702 ret[2].ival = params->difficulty;
704 ret[3].name = "Allow loops";
705 ret[3].type = C_BOOLEAN;
707 ret[3].ival = params->allowloops;
709 ret[4].name = "Max. bridges per direction";
710 ret[4].type = C_CHOICES;
711 ret[4].sval = ":1:2:3:4"; /* keep up-to-date with MAX_BRIDGES */
712 ret[4].ival = params->maxb - 1;
714 ret[5].name = "%age of island squares";
715 ret[5].type = C_CHOICES;
716 ret[5].sval = ":5%:10%:15%:20%:25%:30%";
717 ret[5].ival = (params->islands / 5)-1;
719 ret[6].name = "Expansion factor (%age)";
720 ret[6].type = C_CHOICES;
721 ret[6].sval = ":0%:10%:20%:30%:40%:50%:60%:70%:80%:90%:100%";
722 ret[6].ival = params->expansion / 10;
732 static game_params *custom_params(config_item *cfg)
734 game_params *ret = snew(game_params);
736 ret->w = atoi(cfg[0].sval);
737 ret->h = atoi(cfg[1].sval);
738 ret->difficulty = cfg[2].ival;
739 ret->allowloops = cfg[3].ival;
740 ret->maxb = cfg[4].ival + 1;
741 ret->islands = (cfg[5].ival + 1) * 5;
742 ret->expansion = cfg[6].ival * 10;
747 static char *validate_params(game_params *params, int full)
749 if (params->w < 3 || params->h < 3)
750 return "Width and height must be at least 3";
751 if (params->maxb < 1 || params->maxb > MAX_BRIDGES)
752 return "Too many bridges.";
754 if (params->islands <= 0 || params->islands > 30)
755 return "%age of island squares must be between 1% and 30%";
756 if (params->expansion < 0 || params->expansion > 100)
757 return "Expansion factor must be between 0 and 100";
762 /* --- Game encoding and differences --- */
764 static char *encode_game(game_state *state)
767 int wh = state->w*state->h, run, x, y;
770 ret = snewn(wh + 1, char);
773 for (y = 0; y < state->h; y++) {
774 for (x = 0; x < state->w; x++) {
775 is = INDEX(state, gridi, x, y);
778 *p++ = ('a'-1) + run;
782 *p++ = '0' + is->count;
784 *p++ = 'A' + (is->count - 10);
787 *p++ = ('a'-1) + run;
795 *p++ = ('a'-1) + run;
799 assert(p - ret <= wh);
804 static char *game_state_diff(game_state *src, game_state *dest)
806 int movesize = 256, movelen = 0;
807 char *move = snewn(movesize, char), buf[80];
809 grid_type gline, nline;
810 struct island *is_s, *is_d, *is_orth;
812 #define APPEND do { \
813 if (movelen + len >= movesize) { \
814 movesize = movelen + len + 256; \
815 move = sresize(move, movesize, char); \
817 strcpy(move + movelen, buf); \
821 move[movelen++] = 'S';
822 move[movelen] = '\0';
824 assert(src->n_islands == dest->n_islands);
826 for (i = 0; i < src->n_islands; i++) {
827 is_s = &src->islands[i];
828 is_d = &dest->islands[i];
829 assert(is_s->x == is_d->x);
830 assert(is_s->y == is_d->y);
831 assert(is_s->adj.npoints == is_d->adj.npoints); /* more paranoia */
833 for (d = 0; d < is_s->adj.npoints; d++) {
834 if (is_s->adj.points[d].dx == -1 ||
835 is_s->adj.points[d].dy == -1) continue;
837 x = is_s->adj.points[d].x;
838 y = is_s->adj.points[d].y;
839 gline = is_s->adj.points[d].dx ? G_LINEH : G_LINEV;
840 nline = is_s->adj.points[d].dx ? G_NOLINEH : G_NOLINEV;
841 is_orth = INDEX(dest, gridi,
842 ISLAND_ORTHX(is_d, d), ISLAND_ORTHY(is_d, d));
844 if (GRIDCOUNT(src, x, y, gline) != GRIDCOUNT(dest, x, y, gline)) {
846 len = sprintf(buf, ";L%d,%d,%d,%d,%d",
847 is_s->x, is_s->y, is_orth->x, is_orth->y,
848 GRIDCOUNT(dest, x, y, gline));
851 if ((GRID(src,x,y) & nline) != (GRID(dest, x, y) & nline)) {
853 len = sprintf(buf, ";N%d,%d,%d,%d",
854 is_s->x, is_s->y, is_orth->x, is_orth->y);
858 if ((GRID(src, is_s->x, is_s->y) & G_MARK) !=
859 (GRID(dest, is_d->x, is_d->y) & G_MARK)) {
860 len = sprintf(buf, ";M%d,%d", is_s->x, is_s->y);
867 /* --- Game setup and solving utilities --- */
869 /* This function is optimised; a Quantify showed that lots of grid-generation time
870 * (>50%) was spent in here. Hence the IDX() stuff. */
872 static void map_update_possibles(game_state *state)
874 int x, y, s, e, bl, i, np, maxb, w = state->w, idx;
875 struct island *is_s = NULL, *is_f = NULL;
877 /* Run down vertical stripes [un]setting possv... */
878 for (x = 0; x < state->w; x++) {
882 /* Unset possible flags until we find an island. */
883 for (y = 0; y < state->h; y++) {
884 is_s = IDX(state, gridi, idx);
890 IDX(state, possv, idx) = 0;
893 for (; y < state->h; y++) {
894 maxb = min(maxb, IDX(state, maxv, idx));
895 is_f = IDX(state, gridi, idx);
898 np = min(maxb, is_f->count);
901 for (i = s; i <= e; i++) {
902 INDEX(state, possv, x, i) = bl ? 0 : np;
911 if (IDX(state,grid,idx) & (G_LINEH|G_NOLINEV)) bl = 1;
916 for (i = s; i <= e; i++)
917 INDEX(state, possv, x, i) = 0;
921 /* ...and now do horizontal stripes [un]setting possh. */
922 /* can we lose this clone'n'hack? */
923 for (y = 0; y < state->h; y++) {
927 for (x = 0; x < state->w; x++) {
928 is_s = IDX(state, gridi, idx);
934 IDX(state, possh, idx) = 0;
937 for (; x < state->w; x++) {
938 maxb = min(maxb, IDX(state, maxh, idx));
939 is_f = IDX(state, gridi, idx);
942 np = min(maxb, is_f->count);
945 for (i = s; i <= e; i++) {
946 INDEX(state, possh, i, y) = bl ? 0 : np;
955 if (IDX(state,grid,idx) & (G_LINEV|G_NOLINEH)) bl = 1;
960 for (i = s; i <= e; i++)
961 INDEX(state, possh, i, y) = 0;
966 static void map_count(game_state *state)
969 grid_type flag, grid;
972 for (i = 0; i < state->n_islands; i++) {
973 is = &state->islands[i];
975 for (n = 0; n < is->adj.npoints; n++) {
976 ax = is->adj.points[n].x;
977 ay = is->adj.points[n].y;
978 flag = (ax == is->x) ? G_LINEV : G_LINEH;
979 grid = GRID(state,ax,ay);
981 is->count += INDEX(state,lines,ax,ay);
987 static void map_find_orthogonal(game_state *state)
991 for (i = 0; i < state->n_islands; i++) {
992 island_find_orthogonal(&state->islands[i]);
996 static int grid_degree(game_state *state, int x, int y, int *nx_r, int *ny_r)
998 grid_type grid = SCRATCH(state, x, y), gline = grid & G_LINE;
1000 int x1, y1, x2, y2, c = 0, i, nx, ny;
1002 nx = ny = -1; /* placate optimiser */
1003 is = INDEX(state, gridi, x, y);
1005 for (i = 0; i < is->adj.npoints; i++) {
1006 gline = is->adj.points[i].dx ? G_LINEH : G_LINEV;
1008 is->adj.points[i].x,
1009 is->adj.points[i].y) & gline) {
1010 nx = is->adj.points[i].x;
1011 ny = is->adj.points[i].y;
1016 if (gline & G_LINEV) {
1023 /* Non-island squares with edges in should never be pointing off the
1024 * edge of the grid. */
1025 assert(INGRID(state, x1, y1));
1026 assert(INGRID(state, x2, y2));
1027 if (SCRATCH(state, x1, y1) & (gline | G_ISLAND)) {
1028 nx = x1; ny = y1; c++;
1030 if (SCRATCH(state, x2, y2) & (gline | G_ISLAND)) {
1031 nx = x2; ny = y2; c++;
1035 assert(nx != -1 && ny != -1); /* paranoia */
1036 *nx_r = nx; *ny_r = ny;
1041 static int map_hasloops(game_state *state, int mark)
1043 int x, y, ox, oy, nx = 0, ny = 0, loop = 0;
1045 memcpy(state->scratch, state->grid, GRIDSZ(state));
1047 /* This algorithm is actually broken; if there are two loops connected
1048 * by bridges this will also highlight bridges. The correct algorithm
1049 * uses a dsf and a two-pass edge-detection algorithm (see check_correct
1050 * in slant.c); this is BALGE for now, especially since disallow-loops
1051 * is not the default for this puzzle. If we want to fix this later then
1052 * copy the alg in slant.c to the empty statement in map_group. */
1054 /* Remove all 1-degree edges. */
1055 for (y = 0; y < state->h; y++) {
1056 for (x = 0; x < state->w; x++) {
1058 while (grid_degree(state, ox, oy, &nx, &ny) == 1) {
1059 /*debug(("hasloops: removing 1-degree at (%d,%d).\n", ox, oy));*/
1060 SCRATCH(state, ox, oy) &= ~(G_LINE|G_ISLAND);
1065 /* Mark any remaining edges as G_WARN, if required. */
1066 for (x = 0; x < state->w; x++) {
1067 for (y = 0; y < state->h; y++) {
1068 if (GRID(state,x,y) & G_ISLAND) continue;
1070 if (SCRATCH(state, x, y) & G_LINE) {
1072 /*debug(("hasloops: marking loop square at (%d,%d).\n",
1074 GRID(state,x,y) |= G_WARN;
1077 return 1; /* short-cut as soon as we find one */
1080 GRID(state,x,y) &= ~G_WARN;
1087 static void map_group(game_state *state)
1089 int i, wh = state->w*state->h, d1, d2;
1091 int *dsf = state->solver->dsf;
1092 struct island *is, *is_join;
1094 /* Initialise dsf. */
1097 /* For each island, find connected islands right or down
1098 * and merge the dsf for the island squares as well as the
1099 * bridge squares. */
1100 for (x = 0; x < state->w; x++) {
1101 for (y = 0; y < state->h; y++) {
1102 GRID(state,x,y) &= ~(G_SWEEP|G_WARN); /* for group_full. */
1104 is = INDEX(state, gridi, x, y);
1107 for (i = 0; i < is->adj.npoints; i++) {
1108 /* only want right/down */
1109 if (is->adj.points[i].dx == -1 ||
1110 is->adj.points[i].dy == -1) continue;
1112 is_join = island_find_connection(is, i);
1113 if (!is_join) continue;
1115 d2 = DINDEX(is_join->x, is_join->y);
1116 if (dsf_canonify(dsf,d1) == dsf_canonify(dsf,d2)) {
1117 ; /* we have a loop. See comment in map_hasloops. */
1118 /* However, we still want to merge all squares joining
1119 * this side-that-makes-a-loop. */
1121 /* merge all squares between island 1 and island 2. */
1122 for (x2 = x; x2 <= is_join->x; x2++) {
1123 for (y2 = y; y2 <= is_join->y; y2++) {
1125 if (d1 != d2) dsf_merge(dsf,d1,d2);
1133 static int map_group_check(game_state *state, int canon, int warn,
1136 int *dsf = state->solver->dsf, nislands = 0;
1137 int x, y, i, allfull = 1;
1140 for (i = 0; i < state->n_islands; i++) {
1141 is = &state->islands[i];
1142 if (dsf_canonify(dsf, DINDEX(is->x,is->y)) != canon) continue;
1144 GRID(state, is->x, is->y) |= G_SWEEP;
1146 if (island_countbridges(is) != is->count)
1149 if (warn && allfull && nislands != state->n_islands) {
1150 /* we're full and this island group isn't the whole set.
1151 * Mark all squares with this dsf canon as ERR. */
1152 for (x = 0; x < state->w; x++) {
1153 for (y = 0; y < state->h; y++) {
1154 if (dsf_canonify(dsf, DINDEX(x,y)) == canon) {
1155 GRID(state,x,y) |= G_WARN;
1161 if (nislands_r) *nislands_r = nislands;
1165 static int map_group_full(game_state *state, int *ngroups_r)
1167 int *dsf = state->solver->dsf, ngroups = 0;
1171 /* NB this assumes map_group (or sth else) has cleared G_SWEEP. */
1173 for (i = 0; i < state->n_islands; i++) {
1174 is = &state->islands[i];
1175 if (GRID(state,is->x,is->y) & G_SWEEP) continue;
1178 if (map_group_check(state, dsf_canonify(dsf, DINDEX(is->x,is->y)),
1183 *ngroups_r = ngroups;
1187 static int map_check(game_state *state)
1191 /* Check for loops, if necessary. */
1192 if (!state->allowloops) {
1193 if (map_hasloops(state, 1))
1197 /* Place islands into island groups and check for early
1198 * satisfied-groups. */
1199 map_group(state); /* clears WARN and SWEEP */
1200 if (map_group_full(state, &ngroups)) {
1201 if (ngroups == 1) return 1;
1206 static void map_clear(game_state *state)
1210 for (x = 0; x < state->w; x++) {
1211 for (y = 0; y < state->h; y++) {
1212 /* clear most flags; might want to be slightly more careful here. */
1213 GRID(state,x,y) &= G_ISLAND;
1218 static void solve_join(struct island *is, int direction, int n, int is_max)
1220 struct island *is_orth;
1221 int d1, d2, *dsf = is->state->solver->dsf;
1222 game_state *state = is->state; /* for DINDEX */
1224 is_orth = INDEX(is->state, gridi,
1225 ISLAND_ORTHX(is, direction),
1226 ISLAND_ORTHY(is, direction));
1228 /*debug(("...joining (%d,%d) to (%d,%d) with %d bridge(s).\n",
1229 is->x, is->y, is_orth->x, is_orth->y, n));*/
1230 island_join(is, is_orth, n, is_max);
1232 if (n > 0 && !is_max) {
1233 d1 = DINDEX(is->x, is->y);
1234 d2 = DINDEX(is_orth->x, is_orth->y);
1235 if (dsf_canonify(dsf, d1) != dsf_canonify(dsf, d2))
1236 dsf_merge(dsf, d1, d2);
1240 static int solve_fillone(struct island *is)
1244 debug(("solve_fillone for island (%d,%d).\n", is->x, is->y));
1246 for (i = 0; i < is->adj.npoints; i++) {
1247 if (island_isadj(is, i)) {
1248 if (island_hasbridge(is, i)) {
1249 /* already attached; do nothing. */;
1251 solve_join(is, i, 1, 0);
1259 static int solve_fill(struct island *is)
1261 /* for each unmarked adjacent, make sure we convert every possible bridge
1262 * to a real one, and then work out the possibles afresh. */
1263 int i, nnew, ncurr, nadded = 0, missing;
1265 debug(("solve_fill for island (%d,%d).\n", is->x, is->y));
1267 missing = is->count - island_countbridges(is);
1268 if (missing < 0) return 0;
1270 /* very like island_countspaces. */
1271 for (i = 0; i < is->adj.npoints; i++) {
1272 nnew = island_adjspace(is, 1, missing, i);
1274 ncurr = GRIDCOUNT(is->state,
1275 is->adj.points[i].x, is->adj.points[i].y,
1276 is->adj.points[i].dx ? G_LINEH : G_LINEV);
1278 solve_join(is, i, nnew + ncurr, 0);
1285 static int solve_island_stage1(struct island *is, int *didsth_r)
1287 int bridges = island_countbridges(is);
1288 int nspaces = island_countspaces(is, 1);
1289 int nadj = island_countadj(is);
1294 /*debug(("island at (%d,%d) filled %d/%d (%d spc) nadj %d\n",
1295 is->x, is->y, bridges, is->count, nspaces, nadj));*/
1296 if (bridges > is->count) {
1297 /* We only ever add bridges when we're sure they fit, or that's
1298 * the only place they can go. If we've added bridges such that
1299 * another island has become wrong, the puzzle must not have had
1301 debug(("...island at (%d,%d) is overpopulated!\n", is->x, is->y));
1303 } else if (bridges == is->count) {
1304 /* This island is full. Make sure it's marked (and update
1305 * possibles if we did). */
1306 if (!(GRID(is->state, is->x, is->y) & G_MARK)) {
1307 debug(("...marking island (%d,%d) as full.\n", is->x, is->y));
1308 island_togglemark(is);
1311 } else if (GRID(is->state, is->x, is->y) & G_MARK) {
1312 debug(("...island (%d,%d) is marked but unfinished!\n",
1314 return 0; /* island has been marked unfinished; no solution from here. */
1316 /* This is the interesting bit; we try and fill in more information
1317 * about this island. */
1318 if (is->count == bridges + nspaces) {
1319 if (solve_fill(is) > 0) didsth = 1;
1320 } else if (is->count > ((nadj-1) * is->state->maxb)) {
1321 /* must have at least one bridge in each possible direction. */
1322 if (solve_fillone(is) > 0) didsth = 1;
1326 map_update_possibles(is->state);
1332 /* returns non-zero if a new line here would cause a loop. */
1333 static int solve_island_checkloop(struct island *is, int direction)
1335 struct island *is_orth;
1336 int *dsf = is->state->solver->dsf, d1, d2;
1337 game_state *state = is->state;
1339 if (is->state->allowloops) return 0; /* don't care anyway */
1340 if (island_hasbridge(is, direction)) return 0; /* already has a bridge */
1341 if (island_isadj(is, direction) == 0) return 0; /* no adj island */
1343 is_orth = INDEX(is->state, gridi,
1344 ISLAND_ORTHX(is,direction),
1345 ISLAND_ORTHY(is,direction));
1346 if (!is_orth) return 0;
1348 d1 = DINDEX(is->x, is->y);
1349 d2 = DINDEX(is_orth->x, is_orth->y);
1350 if (dsf_canonify(dsf, d1) == dsf_canonify(dsf, d2)) {
1351 /* two islands are connected already; don't join them. */
1357 static int solve_island_stage2(struct island *is, int *didsth_r)
1359 int added = 0, removed = 0, navail = 0, nadj, i;
1363 for (i = 0; i < is->adj.npoints; i++) {
1364 if (solve_island_checkloop(is, i)) {
1365 debug(("removing possible loop at (%d,%d) direction %d.\n",
1367 solve_join(is, i, -1, 0);
1368 map_update_possibles(is->state);
1371 navail += island_isadj(is, i);
1372 /*debug(("stage2: navail for (%d,%d) direction (%d,%d) is %d.\n",
1374 is->adj.points[i].dx, is->adj.points[i].dy,
1375 island_isadj(is, i)));*/
1379 /*debug(("island at (%d,%d) navail %d: checking...\n", is->x, is->y, navail));*/
1381 for (i = 0; i < is->adj.npoints; i++) {
1382 if (!island_hasbridge(is, i)) {
1383 nadj = island_isadj(is, i);
1384 if (nadj > 0 && (navail - nadj) < is->count) {
1385 /* we couldn't now complete the island without at
1386 * least one bridge here; put it in. */
1387 /*debug(("nadj %d, navail %d, is->count %d.\n",
1388 nadj, navail, is->count));*/
1389 debug(("island at (%d,%d) direction (%d,%d) must have 1 bridge\n",
1391 is->adj.points[i].dx, is->adj.points[i].dy));
1392 solve_join(is, i, 1, 0);
1394 /*debug_state(is->state);
1395 debug_possibles(is->state);*/
1399 if (added) map_update_possibles(is->state);
1400 if (added || removed) *didsth_r = 1;
1404 static int solve_island_subgroup(struct island *is, int direction, int n)
1406 struct island *is_join;
1407 int nislands, *dsf = is->state->solver->dsf;
1408 game_state *state = is->state;
1410 debug(("..checking subgroups.\n"));
1412 /* if is isn't full, return 0. */
1413 if (n < is->count) {
1414 debug(("...orig island (%d,%d) not full.\n", is->x, is->y));
1418 if (direction >= 0) {
1419 is_join = INDEX(state, gridi,
1420 ISLAND_ORTHX(is, direction),
1421 ISLAND_ORTHY(is, direction));
1424 /* if is_join isn't full, return 0. */
1425 if (island_countbridges(is_join) < is_join->count) {
1426 debug(("...dest island (%d,%d) not full.\n",
1427 is_join->x, is_join->y));
1432 /* Check group membership for is->dsf; if it's full return 1. */
1433 if (map_group_check(state, dsf_canonify(dsf, DINDEX(is->x,is->y)),
1435 if (nislands < state->n_islands) {
1436 /* we have a full subgroup that isn't the whole set.
1437 * This isn't allowed. */
1438 debug(("island at (%d,%d) makes full subgroup, disallowing.\n",
1442 debug(("...has finished puzzle.\n"));
1448 static int solve_island_impossible(game_state *state)
1453 /* If any islands are impossible, return 1. */
1454 for (i = 0; i < state->n_islands; i++) {
1455 is = &state->islands[i];
1456 if (island_impossible(is, 0)) {
1457 debug(("island at (%d,%d) has become impossible, disallowing.\n",
1465 /* Bear in mind that this function is really rather inefficient. */
1466 static int solve_island_stage3(struct island *is, int *didsth_r)
1468 int i, n, x, y, missing, spc, curr, maxb, didsth = 0;
1469 int wh = is->state->w * is->state->h;
1470 struct solver_state *ss = is->state->solver;
1474 missing = is->count - island_countbridges(is);
1475 if (missing <= 0) return 1;
1477 for (i = 0; i < is->adj.npoints; i++) {
1478 /* We only do right- or down-pointing bridges. */
1479 if (is->adj.points[i].dx == -1 ||
1480 is->adj.points[i].dy == -1) continue;
1482 x = is->adj.points[i].x;
1483 y = is->adj.points[i].y;
1484 spc = island_adjspace(is, 1, missing, i);
1485 if (spc == 0) continue;
1487 curr = GRIDCOUNT(is->state, x, y,
1488 is->adj.points[i].dx ? G_LINEH : G_LINEV);
1489 debug(("island at (%d,%d) s3, trying %d - %d bridges.\n",
1490 is->x, is->y, curr+1, curr+spc));
1492 /* Now we know that this island could have more bridges,
1493 * to bring the total from curr+1 to curr+spc. */
1495 /* We have to squirrel the dsf away and restore it afterwards;
1496 * it is additive only, and can't be removed from. */
1497 memcpy(ss->tmpdsf, ss->dsf, wh*sizeof(int));
1498 for (n = curr+1; n <= curr+spc; n++) {
1499 solve_join(is, i, n, 0);
1500 map_update_possibles(is->state);
1502 if (solve_island_subgroup(is, i, n) ||
1503 solve_island_impossible(is->state)) {
1505 debug(("island at (%d,%d) d(%d,%d) new max of %d bridges:\n",
1507 is->adj.points[i].dx, is->adj.points[i].dy,
1512 solve_join(is, i, curr, 0); /* put back to before. */
1513 memcpy(ss->dsf, ss->tmpdsf, wh*sizeof(int));
1516 /*debug_state(is->state);*/
1518 debug(("...adding NOLINE.\n"));
1519 solve_join(is, i, -1, 0); /* we can't have any bridges here. */
1521 debug(("...setting maximum\n"));
1522 solve_join(is, i, maxb, 1);
1526 map_update_possibles(is->state);
1529 for (i = 0; i < is->adj.npoints; i++) {
1531 * Now check to see if any currently empty direction must have
1532 * at least one bridge in order to avoid forming an isolated
1533 * subgraph. This differs from the check above in that it
1534 * considers multiple target islands. For example:
1541 * The example on the left can be handled by the above loop:
1542 * it will observe that connecting the central 2 twice to the
1543 * left would form an isolated subgraph, and hence it will
1544 * restrict that 2 to at most one bridge in that direction.
1545 * But the example on the right won't be handled by that loop,
1546 * because the deduction requires us to imagine connecting the
1547 * 3 to _both_ the 1 and 2 at once to form an isolated
1550 * This pass is necessary _as well_ as the above one, because
1551 * neither can do the other's job. In the left one,
1552 * restricting the direction which _would_ cause trouble can
1553 * be done even if it's not yet clear which of the remaining
1554 * directions has to have a compensatory bridge; whereas the
1555 * pass below that can handle the right-hand example does need
1556 * to know what direction to point the necessary bridge in.
1558 * Neither pass can handle the most general case, in which we
1559 * observe that an arbitrary subset of an island's neighbours
1560 * would form an isolated subgraph with it if it connected
1561 * maximally to them, and hence that at least one bridge must
1562 * point to some neighbour outside that subset but we don't
1563 * know which neighbour. To handle that, we'd have to have a
1564 * richer data format for the solver, which could cope with
1565 * recording the idea that at least one of two edges must have
1572 spc = island_adjspace(is, 1, missing, i);
1573 if (spc == 0) continue;
1575 for (j = 0; j < is->adj.npoints; j++)
1576 before[j] = GRIDCOUNT(is->state,
1577 is->adj.points[j].x,
1578 is->adj.points[j].y,
1579 is->adj.points[j].dx ? G_LINEH : G_LINEV);
1580 if (before[i] != 0) continue; /* this idea is pointless otherwise */
1582 memcpy(ss->tmpdsf, ss->dsf, wh*sizeof(int));
1584 for (j = 0; j < is->adj.npoints; j++) {
1585 spc = island_adjspace(is, 1, missing, j);
1586 if (spc == 0) continue;
1587 if (j == i) continue;
1588 solve_join(is, j, before[j] + spc, 0);
1590 map_update_possibles(is->state);
1592 if (solve_island_subgroup(is, -1, n))
1595 for (j = 0; j < is->adj.npoints; j++)
1596 solve_join(is, j, before[j], 0);
1597 memcpy(ss->dsf, ss->tmpdsf, wh*sizeof(int));
1600 debug(("island at (%d,%d) must connect in direction (%d,%d) to"
1601 " avoid full subgroup.\n",
1602 is->x, is->y, is->adj.points[i].dx, is->adj.points[i].dy));
1603 solve_join(is, i, 1, 0);
1607 map_update_possibles(is->state);
1610 if (didsth) *didsth_r = didsth;
1614 #define CONTINUE_IF_FULL do { \
1615 if (GRID(state, is->x, is->y) & G_MARK) { \
1616 /* island full, don't try fixing it */ \
1620 static int solve_sub(game_state *state, int difficulty, int depth)
1628 /* First island iteration: things we can work out by looking at
1629 * properties of the island as a whole. */
1630 for (i = 0; i < state->n_islands; i++) {
1631 is = &state->islands[i];
1632 if (!solve_island_stage1(is, &didsth)) return 0;
1634 if (didsth) continue;
1635 else if (difficulty < 1) break;
1637 /* Second island iteration: thing we can work out by looking at
1638 * properties of individual island connections. */
1639 for (i = 0; i < state->n_islands; i++) {
1640 is = &state->islands[i];
1642 if (!solve_island_stage2(is, &didsth)) return 0;
1644 if (didsth) continue;
1645 else if (difficulty < 2) break;
1647 /* Third island iteration: things we can only work out by looking
1648 * at groups of islands. */
1649 for (i = 0; i < state->n_islands; i++) {
1650 is = &state->islands[i];
1651 if (!solve_island_stage3(is, &didsth)) return 0;
1653 if (didsth) continue;
1654 else if (difficulty < 3) break;
1656 /* If we can be bothered, write a recursive solver to finish here. */
1659 if (map_check(state)) return 1; /* solved it */
1663 static void solve_for_hint(game_state *state)
1666 solve_sub(state, 10, 0);
1669 static int solve_from_scratch(game_state *state, int difficulty)
1673 map_update_possibles(state);
1674 return solve_sub(state, difficulty, 0);
1677 /* --- New game functions --- */
1679 static game_state *new_state(game_params *params)
1681 game_state *ret = snew(game_state);
1682 int wh = params->w * params->h, i;
1686 ret->allowloops = params->allowloops;
1687 ret->maxb = params->maxb;
1688 ret->params = *params;
1690 ret->grid = snewn(wh, grid_type);
1691 memset(ret->grid, 0, GRIDSZ(ret));
1692 ret->scratch = snewn(wh, grid_type);
1693 memset(ret->scratch, 0, GRIDSZ(ret));
1695 ret->wha = snewn(wh*N_WH_ARRAYS, char);
1696 memset(ret->wha, 0, wh*N_WH_ARRAYS*sizeof(char));
1698 ret->possv = ret->wha;
1699 ret->possh = ret->wha + wh;
1700 ret->lines = ret->wha + wh*2;
1701 ret->maxv = ret->wha + wh*3;
1702 ret->maxh = ret->wha + wh*4;
1704 memset(ret->maxv, ret->maxb, wh*sizeof(char));
1705 memset(ret->maxh, ret->maxb, wh*sizeof(char));
1707 ret->islands = NULL;
1709 ret->n_islands_alloc = 0;
1711 ret->gridi = snewn(wh, struct island *);
1712 for (i = 0; i < wh; i++) ret->gridi[i] = NULL;
1714 ret->solved = ret->completed = 0;
1716 ret->solver = snew(struct solver_state);
1717 ret->solver->dsf = snew_dsf(wh);
1718 ret->solver->tmpdsf = snewn(wh, int);
1720 ret->solver->refcount = 1;
1725 static game_state *dup_game(game_state *state)
1727 game_state *ret = snew(game_state);
1728 int wh = state->w*state->h;
1732 ret->allowloops = state->allowloops;
1733 ret->maxb = state->maxb;
1734 ret->params = state->params;
1736 ret->grid = snewn(wh, grid_type);
1737 memcpy(ret->grid, state->grid, GRIDSZ(ret));
1738 ret->scratch = snewn(wh, grid_type);
1739 memcpy(ret->scratch, state->scratch, GRIDSZ(ret));
1741 ret->wha = snewn(wh*N_WH_ARRAYS, char);
1742 memcpy(ret->wha, state->wha, wh*N_WH_ARRAYS*sizeof(char));
1744 ret->possv = ret->wha;
1745 ret->possh = ret->wha + wh;
1746 ret->lines = ret->wha + wh*2;
1747 ret->maxv = ret->wha + wh*3;
1748 ret->maxh = ret->wha + wh*4;
1750 ret->islands = snewn(state->n_islands, struct island);
1751 memcpy(ret->islands, state->islands, state->n_islands * sizeof(struct island));
1752 ret->n_islands = ret->n_islands_alloc = state->n_islands;
1754 ret->gridi = snewn(wh, struct island *);
1755 fixup_islands_for_realloc(ret);
1757 ret->solved = state->solved;
1758 ret->completed = state->completed;
1760 ret->solver = state->solver;
1761 ret->solver->refcount++;
1766 static void free_game(game_state *state)
1768 if (--state->solver->refcount <= 0) {
1769 sfree(state->solver->dsf);
1770 sfree(state->solver->tmpdsf);
1771 sfree(state->solver);
1774 sfree(state->islands);
1775 sfree(state->gridi);
1779 sfree(state->scratch);
1784 #define MAX_NEWISLAND_TRIES 50
1785 #define MIN_SENSIBLE_ISLANDS 3
1787 #define ORDER(a,b) do { if (a < b) { int tmp=a; int a=b; int b=tmp; } } while(0)
1789 static char *new_game_desc(game_params *params, random_state *rs,
1790 char **aux, int interactive)
1792 game_state *tobuild = NULL;
1793 int i, j, wh = params->w * params->h, x, y, dx, dy;
1794 int minx, miny, maxx, maxy, joinx, joiny, newx, newy, diffx, diffy;
1795 int ni_req = max((params->islands * wh) / 100, MIN_SENSIBLE_ISLANDS), ni_curr, ni_bad;
1796 struct island *is, *is2;
1798 unsigned int echeck;
1800 /* pick a first island position randomly. */
1802 if (tobuild) free_game(tobuild);
1803 tobuild = new_state(params);
1805 x = random_upto(rs, params->w);
1806 y = random_upto(rs, params->h);
1807 island_add(tobuild, x, y, 0);
1810 debug(("Created initial island at (%d,%d).\n", x, y));
1812 while (ni_curr < ni_req) {
1813 /* Pick a random island to try and extend from. */
1814 i = random_upto(rs, tobuild->n_islands);
1815 is = &tobuild->islands[i];
1817 /* Pick a random direction to extend in. */
1818 j = random_upto(rs, is->adj.npoints);
1819 dx = is->adj.points[j].x - is->x;
1820 dy = is->adj.points[j].y - is->y;
1822 /* Find out limits of where we could put a new island. */
1824 minx = is->x + 2*dx; miny = is->y + 2*dy; /* closest is 2 units away. */
1825 x = is->x+dx; y = is->y+dy;
1826 if (GRID(tobuild,x,y) & (G_LINEV|G_LINEH)) {
1827 /* already a line next to the island, continue. */
1831 if (x < 0 || x >= params->w || y < 0 || y >= params->h) {
1832 /* got past the edge; put a possible at the island
1834 maxx = x-dx; maxy = y-dy;
1837 if (GRID(tobuild,x,y) & G_ISLAND) {
1838 /* could join up to an existing island... */
1839 joinx = x; joiny = y;
1840 /* ... or make a new one 2 spaces away. */
1841 maxx = x - 2*dx; maxy = y - 2*dy;
1843 } else if (GRID(tobuild,x,y) & (G_LINEV|G_LINEH)) {
1844 /* could make a new one 1 space away from the line. */
1845 maxx = x - dx; maxy = y - dy;
1852 debug(("Island at (%d,%d) with d(%d,%d) has new positions "
1853 "(%d,%d) -> (%d,%d), join (%d,%d).\n",
1854 is->x, is->y, dx, dy, minx, miny, maxx, maxy, joinx, joiny));
1855 /* Now we know where we could either put a new island
1856 * (between min and max), or (if loops are allowed) could join on
1857 * to an existing island (at join). */
1858 if (params->allowloops && joinx != -1 && joiny != -1) {
1859 if (random_upto(rs, 100) < (unsigned long)params->expansion) {
1860 is2 = INDEX(tobuild, gridi, joinx, joiny);
1861 debug(("Joining island at (%d,%d) to (%d,%d).\n",
1862 is->x, is->y, is2->x, is2->y));
1866 diffx = (maxx - minx) * dx;
1867 diffy = (maxy - miny) * dy;
1868 if (diffx < 0 || diffy < 0) goto bad;
1869 if (random_upto(rs,100) < (unsigned long)params->expansion) {
1870 newx = maxx; newy = maxy;
1871 debug(("Creating new island at (%d,%d) (expanded).\n", newx, newy));
1873 newx = minx + random_upto(rs,diffx+1)*dx;
1874 newy = miny + random_upto(rs,diffy+1)*dy;
1875 debug(("Creating new island at (%d,%d).\n", newx, newy));
1877 /* check we're not next to island in the other orthogonal direction. */
1878 if ((INGRID(tobuild,newx+dy,newy+dx) && (GRID(tobuild,newx+dy,newy+dx) & G_ISLAND)) ||
1879 (INGRID(tobuild,newx-dy,newy-dx) && (GRID(tobuild,newx-dy,newy-dx) & G_ISLAND))) {
1880 debug(("New location is adjacent to island, skipping.\n"));
1883 is2 = island_add(tobuild, newx, newy, 0);
1884 /* Must get is again at this point; the array might have
1885 * been realloced by island_add... */
1886 is = &tobuild->islands[i]; /* ...but order will not change. */
1888 ni_curr++; ni_bad = 0;
1890 island_join(is, is2, random_upto(rs, tobuild->maxb)+1, 0);
1891 debug_state(tobuild);
1896 if (ni_bad > MAX_NEWISLAND_TRIES) {
1897 debug(("Unable to create any new islands after %d tries; "
1898 "created %d [%d%%] (instead of %d [%d%%] requested).\n",
1899 MAX_NEWISLAND_TRIES,
1900 ni_curr, ni_curr * 100 / wh,
1901 ni_req, ni_req * 100 / wh));
1908 debug(("Only generated one island (!), retrying.\n"));
1911 /* Check we have at least one island on each extremity of the grid. */
1913 for (x = 0; x < params->w; x++) {
1914 if (INDEX(tobuild, gridi, x, 0)) echeck |= 1;
1915 if (INDEX(tobuild, gridi, x, params->h-1)) echeck |= 2;
1917 for (y = 0; y < params->h; y++) {
1918 if (INDEX(tobuild, gridi, 0, y)) echeck |= 4;
1919 if (INDEX(tobuild, gridi, params->w-1, y)) echeck |= 8;
1922 debug(("Generated grid doesn't fill to sides, retrying.\n"));
1927 map_find_orthogonal(tobuild);
1929 if (params->difficulty > 0) {
1930 if ((ni_curr > MIN_SENSIBLE_ISLANDS) &&
1931 (solve_from_scratch(tobuild, params->difficulty-1) > 0)) {
1932 debug(("Grid is solvable at difficulty %d (too easy); retrying.\n",
1933 params->difficulty-1));
1938 if (solve_from_scratch(tobuild, params->difficulty) == 0) {
1939 debug(("Grid not solvable at difficulty %d, (too hard); retrying.\n",
1940 params->difficulty));
1944 /* ... tobuild is now solved. We rely on this making the diff for aux. */
1945 debug_state(tobuild);
1946 ret = encode_game(tobuild);
1948 game_state *clean = dup_game(tobuild);
1950 map_update_possibles(clean);
1951 *aux = game_state_diff(clean, tobuild);
1959 static char *validate_desc(game_params *params, char *desc)
1961 int i, wh = params->w * params->h;
1963 for (i = 0; i < wh; i++) {
1964 if (*desc >= '1' && *desc <= '9')
1966 else if (*desc >= 'a' && *desc <= 'z')
1967 i += *desc - 'a'; /* plus the i++ */
1968 else if (*desc >= 'A' && *desc <= 'G')
1970 else if (*desc == 'V' || *desc == 'W' ||
1971 *desc == 'X' || *desc == 'Y' ||
1972 *desc == 'H' || *desc == 'I' ||
1973 *desc == 'J' || *desc == 'K')
1976 return "Game description shorter than expected";
1978 return "Game description containers unexpected character";
1981 if (*desc || i > wh)
1982 return "Game description longer than expected";
1987 static game_state *new_game_sub(game_params *params, char *desc)
1989 game_state *state = new_state(params);
1992 debug(("new_game[_sub]: desc = '%s'.\n", desc));
1994 for (y = 0; y < params->h; y++) {
1995 for (x = 0; x < params->w; x++) {
2001 if (c >= 'a' && c <= 'z')
2011 case '1': case '2': case '3': case '4':
2012 case '5': case '6': case '7': case '8': case '9':
2013 island_add(state, x, y, (c - '0'));
2016 case 'A': case 'B': case 'C': case 'D':
2017 case 'E': case 'F': case 'G':
2018 island_add(state, x, y, (c - 'A') + 10);
2026 assert(!"Malformed desc.");
2031 if (*desc) assert(!"Over-long desc.");
2033 map_find_orthogonal(state);
2034 map_update_possibles(state);
2039 static game_state *new_game(midend *me, game_params *params, char *desc)
2041 return new_game_sub(params, desc);
2045 int dragx_src, dragy_src; /* source; -1 means no drag */
2046 int dragx_dst, dragy_dst; /* src's closest orth island. */
2048 int dragging, drag_is_noline, nlines;
2050 int cur_x, cur_y, cur_visible; /* cursor position */
2054 static char *ui_cancel_drag(game_ui *ui)
2056 ui->dragx_src = ui->dragy_src = -1;
2057 ui->dragx_dst = ui->dragy_dst = -1;
2062 static game_ui *new_ui(game_state *state)
2064 game_ui *ui = snew(game_ui);
2066 ui->cur_x = state->islands[0].x;
2067 ui->cur_y = state->islands[0].y;
2068 ui->cur_visible = 0;
2073 static void free_ui(game_ui *ui)
2078 static char *encode_ui(game_ui *ui)
2083 static void decode_ui(game_ui *ui, char *encoding)
2087 static void game_changed_state(game_ui *ui, game_state *oldstate,
2088 game_state *newstate)
2092 struct game_drawstate {
2097 int started, dragging;
2101 static char *update_drag_dst(game_state *state, game_ui *ui, game_drawstate *ds,
2104 int ox, oy, dx, dy, i, currl, maxb;
2106 grid_type gtype, ntype, mtype, curr;
2108 if (ui->dragx_src == -1 || ui->dragy_src == -1) return NULL;
2113 /* work out which of the four directions we're closest to... */
2114 ox = COORD(ui->dragx_src) + TILE_SIZE/2;
2115 oy = COORD(ui->dragy_src) + TILE_SIZE/2;
2117 if (abs(nx-ox) < abs(ny-oy)) {
2119 dy = (ny-oy) < 0 ? -1 : 1;
2120 gtype = G_LINEV; ntype = G_NOLINEV; mtype = G_MARKV;
2121 maxb = INDEX(state, maxv, ui->dragx_src+dx, ui->dragy_src+dy);
2124 dx = (nx-ox) < 0 ? -1 : 1;
2125 gtype = G_LINEH; ntype = G_NOLINEH; mtype = G_MARKH;
2126 maxb = INDEX(state, maxh, ui->dragx_src+dx, ui->dragy_src+dy);
2128 if (ui->drag_is_noline) {
2131 curr = GRID(state, ui->dragx_src+dx, ui->dragy_src+dy);
2132 currl = INDEX(state, lines, ui->dragx_src+dx, ui->dragy_src+dy);
2135 if (currl == maxb) {
2140 ui->nlines = currl + 1;
2148 /* ... and see if there's an island off in that direction. */
2149 is = INDEX(state, gridi, ui->dragx_src, ui->dragy_src);
2150 for (i = 0; i < is->adj.npoints; i++) {
2151 if (is->adj.points[i].off == 0) continue;
2152 curr = GRID(state, is->x+dx, is->y+dy);
2153 if (curr & mtype) continue; /* don't allow changes to marked lines. */
2154 if (ui->drag_is_noline) {
2155 if (curr & gtype) continue; /* no no-line where already a line */
2157 if (POSSIBLES(state, dx, is->x+dx, is->y+dy) == 0) continue; /* no line if !possible. */
2158 if (curr & ntype) continue; /* can't have a bridge where there's a no-line. */
2161 if (is->adj.points[i].dx == dx &&
2162 is->adj.points[i].dy == dy) {
2163 ui->dragx_dst = ISLAND_ORTHX(is,i);
2164 ui->dragy_dst = ISLAND_ORTHY(is,i);
2167 /*debug(("update_drag src (%d,%d) d(%d,%d) dst (%d,%d)\n",
2168 ui->dragx_src, ui->dragy_src, dx, dy,
2169 ui->dragx_dst, ui->dragy_dst));*/
2173 static char *finish_drag(game_state *state, game_ui *ui)
2177 if (ui->dragx_src == -1 || ui->dragy_src == -1)
2179 if (ui->dragx_dst == -1 || ui->dragy_dst == -1)
2180 return ui_cancel_drag(ui);
2182 if (ui->drag_is_noline) {
2183 sprintf(buf, "N%d,%d,%d,%d",
2184 ui->dragx_src, ui->dragy_src,
2185 ui->dragx_dst, ui->dragy_dst);
2187 sprintf(buf, "L%d,%d,%d,%d,%d",
2188 ui->dragx_src, ui->dragy_src,
2189 ui->dragx_dst, ui->dragy_dst, ui->nlines);
2197 static char *interpret_move(game_state *state, game_ui *ui, game_drawstate *ds,
2198 int x, int y, int button)
2200 int gx = FROMCOORD(x), gy = FROMCOORD(y);
2202 grid_type ggrid = INGRID(state,gx,gy) ? GRID(state,gx,gy) : 0;
2204 if (button == LEFT_BUTTON || button == RIGHT_BUTTON) {
2205 if (!INGRID(state, gx, gy)) return NULL;
2206 ui->cur_visible = 0;
2207 if ((ggrid & G_ISLAND) && !(ggrid & G_MARK)) {
2212 return ui_cancel_drag(ui);
2213 } else if (button == LEFT_DRAG || button == RIGHT_DRAG) {
2214 if (gx != ui->dragx_src || gy != ui->dragy_src) {
2216 ui->drag_is_noline = (button == RIGHT_DRAG) ? 1 : 0;
2217 return update_drag_dst(state, ui, ds, x, y);
2219 /* cancel a drag when we go back to the starting point */
2224 } else if (button == LEFT_RELEASE || button == RIGHT_RELEASE) {
2226 return finish_drag(state, ui);
2229 if (!INGRID(state, gx, gy)) return NULL;
2230 if (!(GRID(state, gx, gy) & G_ISLAND)) return NULL;
2231 sprintf(buf, "M%d,%d", gx, gy);
2234 } else if (button == 'h' || button == 'H') {
2235 game_state *solved = dup_game(state);
2236 solve_for_hint(solved);
2237 ret = game_state_diff(state, solved);
2240 } else if (IS_CURSOR_MOVE(button)) {
2241 ui->cur_visible = 1;
2243 int nx = ui->cur_x, ny = ui->cur_y;
2245 move_cursor(button, &nx, &ny, state->w, state->h, 0);
2246 update_drag_dst(state, ui, ds,
2247 COORD(nx)+TILE_SIZE/2,
2248 COORD(ny)+TILE_SIZE/2);
2249 return finish_drag(state, ui);
2251 int dx = (button == CURSOR_RIGHT) ? +1 : (button == CURSOR_LEFT) ? -1 : 0;
2252 int dy = (button == CURSOR_DOWN) ? +1 : (button == CURSOR_UP) ? -1 : 0;
2253 int dorthx = 1 - abs(dx), dorthy = 1 - abs(dy);
2254 int dir, orth, nx = x, ny = y;
2256 /* 'orthorder' is a tweak to ensure that if you press RIGHT and
2257 * happen to move upwards, when you press LEFT you then tend
2258 * downwards (rather than upwards again). */
2259 int orthorder = (button == CURSOR_LEFT || button == CURSOR_UP) ? 1 : -1;
2261 /* This attempts to find an island in the direction you're
2262 * asking for, broadly speaking. If you ask to go right, for
2263 * example, it'll look for islands to the right and slightly
2264 * above or below your current horiz. position, allowing
2265 * further above/below the further away it searches. */
2267 assert(GRID(state, ui->cur_x, ui->cur_y) & G_ISLAND);
2268 /* currently this is depth-first (so orthogonally-adjacent
2269 * islands across the other side of the grid will be moved to
2270 * before closer islands slightly offset). Swap the order of
2271 * these two loops to change to breadth-first search. */
2272 for (orth = 0; ; orth++) {
2274 for (dir = 1; ; dir++) {
2277 if (orth > dir) continue; /* only search in cone outwards. */
2279 nx = ui->cur_x + dir*dx + orth*dorthx*orthorder;
2280 ny = ui->cur_y + dir*dy + orth*dorthy*orthorder;
2281 if (INGRID(state, nx, ny)) {
2282 dingrid = oingrid = 1;
2283 if (GRID(state, nx, ny) & G_ISLAND) goto found;
2286 nx = ui->cur_x + dir*dx - orth*dorthx*orthorder;
2287 ny = ui->cur_y + dir*dy - orth*dorthy*orthorder;
2288 if (INGRID(state, nx, ny)) {
2289 dingrid = oingrid = 1;
2290 if (GRID(state, nx, ny) & G_ISLAND) goto found;
2293 if (!dingrid) break;
2295 if (!oingrid) return "";
2304 } else if (IS_CURSOR_SELECT(button)) {
2305 if (!ui->cur_visible) {
2306 ui->cur_visible = 1;
2311 if (ui->dragx_dst == -1 && ui->dragy_dst == -1) {
2312 sprintf(buf, "M%d,%d", ui->cur_x, ui->cur_y);
2317 grid_type v = GRID(state, ui->cur_x, ui->cur_y);
2320 ui->dragx_src = ui->cur_x;
2321 ui->dragy_src = ui->cur_y;
2322 ui->dragx_dst = ui->dragy_dst = -1;
2323 ui->drag_is_noline = (button == CURSOR_SELECT2) ? 1 : 0;
2327 } else if (button == 'g' || button == 'G') {
2328 ui->show_hints = 1 - ui->show_hints;
2335 static game_state *execute_move(game_state *state, char *move)
2337 game_state *ret = dup_game(state);
2338 int x1, y1, x2, y2, nl, n;
2339 struct island *is1, *is2;
2342 debug(("execute_move: %s\n", move));
2344 if (!*move) goto badmove;
2350 } else if (c == 'L') {
2351 if (sscanf(move, "%d,%d,%d,%d,%d%n",
2352 &x1, &y1, &x2, &y2, &nl, &n) != 5)
2354 if (!INGRID(ret, x1, y1) || !INGRID(ret, x2, y2))
2356 is1 = INDEX(ret, gridi, x1, y1);
2357 is2 = INDEX(ret, gridi, x2, y2);
2358 if (!is1 || !is2) goto badmove;
2359 if (nl < 0 || nl > state->maxb) goto badmove;
2360 island_join(is1, is2, nl, 0);
2361 } else if (c == 'N') {
2362 if (sscanf(move, "%d,%d,%d,%d%n",
2363 &x1, &y1, &x2, &y2, &n) != 4)
2365 if (!INGRID(ret, x1, y1) || !INGRID(ret, x2, y2))
2367 is1 = INDEX(ret, gridi, x1, y1);
2368 is2 = INDEX(ret, gridi, x2, y2);
2369 if (!is1 || !is2) goto badmove;
2370 island_join(is1, is2, -1, 0);
2371 } else if (c == 'M') {
2372 if (sscanf(move, "%d,%d%n",
2375 if (!INGRID(ret, x1, y1))
2377 is1 = INDEX(ret, gridi, x1, y1);
2378 if (!is1) goto badmove;
2379 island_togglemark(is1);
2386 else if (*move) goto badmove;
2389 map_update_possibles(ret);
2390 if (map_check(ret)) {
2391 debug(("Game completed.\n"));
2397 debug(("%s: unrecognised move.\n", move));
2402 static char *solve_game(game_state *state, game_state *currstate,
2403 char *aux, char **error)
2409 debug(("solve_game: aux = %s\n", aux));
2410 solved = execute_move(state, aux);
2412 *error = "Generated aux string is not a valid move (!).";
2416 solved = dup_game(state);
2417 /* solve with max strength... */
2418 if (solve_from_scratch(solved, 10) == 0) {
2420 *error = "Game does not have a (non-recursive) solution.";
2424 ret = game_state_diff(currstate, solved);
2426 debug(("solve_game: ret = %s\n", ret));
2430 /* ----------------------------------------------------------------------
2434 static void game_compute_size(game_params *params, int tilesize,
2437 /* Ick: fake up `ds->tilesize' for macro expansion purposes */
2438 struct { int tilesize; } ads, *ds = &ads;
2439 ads.tilesize = tilesize;
2441 *x = TILE_SIZE * params->w + 2 * BORDER;
2442 *y = TILE_SIZE * params->h + 2 * BORDER;
2445 static void game_set_size(drawing *dr, game_drawstate *ds,
2446 game_params *params, int tilesize)
2448 ds->tilesize = tilesize;
2451 static float *game_colours(frontend *fe, int *ncolours)
2453 float *ret = snewn(3 * NCOLOURS, float);
2456 game_mkhighlight(fe, ret, COL_BACKGROUND, COL_HIGHLIGHT, COL_LOWLIGHT);
2458 for (i = 0; i < 3; i++) {
2459 ret[COL_FOREGROUND * 3 + i] = 0.0F;
2460 ret[COL_HINT * 3 + i] = ret[COL_LOWLIGHT * 3 + i];
2461 ret[COL_GRID * 3 + i] =
2462 (ret[COL_HINT * 3 + i] + ret[COL_BACKGROUND * 3 + i]) * 0.5F;
2463 ret[COL_MARK * 3 + i] = ret[COL_HIGHLIGHT * 3 + i];
2465 ret[COL_WARNING * 3 + 0] = 1.0F;
2466 ret[COL_WARNING * 3 + 1] = 0.25F;
2467 ret[COL_WARNING * 3 + 2] = 0.25F;
2469 ret[COL_SELECTED * 3 + 0] = 0.25F;
2470 ret[COL_SELECTED * 3 + 1] = 1.00F;
2471 ret[COL_SELECTED * 3 + 2] = 0.25F;
2473 ret[COL_CURSOR * 3 + 0] = min(ret[COL_BACKGROUND * 3 + 0] * 1.4F, 1.0F);
2474 ret[COL_CURSOR * 3 + 1] = ret[COL_BACKGROUND * 3 + 1] * 0.8F;
2475 ret[COL_CURSOR * 3 + 2] = ret[COL_BACKGROUND * 3 + 2] * 0.8F;
2477 *ncolours = NCOLOURS;
2481 static game_drawstate *game_new_drawstate(drawing *dr, game_state *state)
2483 struct game_drawstate *ds = snew(struct game_drawstate);
2484 int wh = state->w*state->h;
2490 ds->grid = snewn(wh, grid_type);
2491 memset(ds->grid, -1, wh*sizeof(grid_type));
2492 ds->lv = snewn(wh, int);
2493 ds->lh = snewn(wh, int);
2494 memset(ds->lv, 0, wh*sizeof(int));
2495 memset(ds->lh, 0, wh*sizeof(int));
2501 static void game_free_drawstate(drawing *dr, game_drawstate *ds)
2509 #define LINE_WIDTH (TILE_SIZE/8)
2510 #define TS8(x) (((x)*TILE_SIZE)/8)
2512 #define OFFSET(thing) ((TILE_SIZE/2) - ((thing)/2))
2514 static void lines_vert(drawing *dr, game_drawstate *ds,
2515 int ox, int oy, int lv, int col, grid_type v)
2517 int lw = LINE_WIDTH, gw = LINE_WIDTH, bw, i, loff;
2518 while ((bw = lw * lv + gw * (lv+1)) > TILE_SIZE)
2522 draw_rect(dr, ox + loff, oy, bw, TILE_SIZE, COL_MARK);
2523 for (i = 0; i < lv; i++, loff += lw + gw)
2524 draw_rect(dr, ox + loff + gw, oy, lw, TILE_SIZE, col);
2527 static void lines_horiz(drawing *dr, game_drawstate *ds,
2528 int ox, int oy, int lh, int col, grid_type v)
2530 int lw = LINE_WIDTH, gw = LINE_WIDTH, bw, i, loff;
2531 while ((bw = lw * lh + gw * (lh+1)) > TILE_SIZE)
2535 draw_rect(dr, ox, oy + loff, TILE_SIZE, bw, COL_MARK);
2536 for (i = 0; i < lh; i++, loff += lw + gw)
2537 draw_rect(dr, ox, oy + loff + gw, TILE_SIZE, lw, col);
2540 static void line_cross(drawing *dr, game_drawstate *ds,
2541 int ox, int oy, int col, grid_type v)
2544 draw_line(dr, ox, oy, ox+off, oy+off, col);
2545 draw_line(dr, ox+off, oy, ox, oy+off, col);
2548 static int between_island(game_state *state, int sx, int sy, int dx, int dy)
2550 int x = sx - dx, y = sy - dy;
2552 while (INGRID(state, x, y)) {
2553 if (GRID(state, x, y) & G_ISLAND) goto found;
2558 x = sx + dx, y = sy + dy;
2559 while (INGRID(state, x, y)) {
2560 if (GRID(state, x, y) & G_ISLAND) return 1;
2566 static void lines_lvlh(game_state *state, game_ui *ui, int x, int y, grid_type v,
2567 int *lv_r, int *lh_r)
2571 if (v & G_LINEV) lv = INDEX(state,lines,x,y);
2572 if (v & G_LINEH) lh = INDEX(state,lines,x,y);
2574 if (ui->show_hints) {
2575 if (between_island(state, x, y, 0, 1) && !lv) lv = 1;
2576 if (between_island(state, x, y, 1, 0) && !lh) lh = 1;
2578 /*debug(("lvlh: (%d,%d) v 0x%x lv %d lh %d.\n", x, y, v, lv, lh));*/
2579 *lv_r = lv; *lh_r = lh;
2582 static void dsf_debug_draw(drawing *dr,
2583 game_state *state, game_drawstate *ds,
2587 int ts = TILE_SIZE/2;
2588 int ox = COORD(x) + ts/2, oy = COORD(y) + ts/2;
2591 sprintf(str, "%d", dsf_canonify(state->solver->dsf, DINDEX(x,y)));
2592 draw_text(dr, ox, oy, FONT_VARIABLE, ts,
2593 ALIGN_VCENTRE | ALIGN_HCENTRE, COL_WARNING, str);
2597 static void lines_redraw(drawing *dr,
2598 game_state *state, game_drawstate *ds, game_ui *ui,
2599 int x, int y, grid_type v, int lv, int lh)
2601 int ox = COORD(x), oy = COORD(y);
2602 int vcol = (v & G_FLASH) ? COL_HIGHLIGHT :
2603 (v & G_WARN) ? COL_WARNING : COL_FOREGROUND, hcol = vcol;
2604 grid_type todraw = v & G_NOLINE;
2607 if (ui->todraw & G_FLAGSH) hcol = COL_SELECTED;
2608 if (ui->todraw & G_FLAGSV) vcol = COL_SELECTED;
2609 todraw |= ui->todraw;
2612 draw_rect(dr, ox, oy, TILE_SIZE, TILE_SIZE, COL_BACKGROUND);
2614 draw_rect(dr, ox+TILE_SIZE/4, oy+TILE_SIZE/4,
2615 TILE_SIZE/2, TILE_SIZE/2, COL_CURSOR);*/
2618 if (ui->show_hints) {
2619 if (between_island(state, x, y, 0, 1) && !(v & G_LINEV))
2621 if (between_island(state, x, y, 1, 0) && !(v & G_LINEH))
2625 draw_rect_outline(dr, ox, oy, TILE_SIZE, TILE_SIZE, COL_GRID);
2628 if (todraw & G_NOLINEV) {
2629 line_cross(dr, ds, ox + TS8(3), oy + TS8(1), vcol, todraw);
2630 line_cross(dr, ds, ox + TS8(3), oy + TS8(5), vcol, todraw);
2632 if (todraw & G_NOLINEH) {
2633 line_cross(dr, ds, ox + TS8(1), oy + TS8(3), hcol, todraw);
2634 line_cross(dr, ds, ox + TS8(5), oy + TS8(3), hcol, todraw);
2636 /* if we're drawing a real line and a hint, make sure we draw the real
2638 if (lv && vcol == COL_HINT) lines_vert(dr, ds, ox, oy, lv, vcol, v);
2639 if (lh) lines_horiz(dr, ds, ox, oy, lh, hcol, v);
2640 if (lv && vcol != COL_HINT) lines_vert(dr, ds, ox, oy, lv, vcol, v);
2642 dsf_debug_draw(dr, state, ds, x, y);
2643 draw_update(dr, ox, oy, TILE_SIZE, TILE_SIZE);
2646 #define ISLAND_RADIUS ((TILE_SIZE*12)/20)
2647 #define ISLAND_NUMSIZE(is) \
2648 (((is)->count < 10) ? (TILE_SIZE*7)/10 : (TILE_SIZE*5)/10)
2650 static void island_redraw(drawing *dr,
2651 game_state *state, game_drawstate *ds,
2652 struct island *is, grid_type v)
2654 /* These overlap the edges of their squares, which is why they're drawn later.
2655 * We know they can't overlap each other because they're not allowed within 2
2656 * squares of each other. */
2657 int half = TILE_SIZE/2;
2658 int ox = COORD(is->x) + half, oy = COORD(is->y) + half;
2659 int orad = ISLAND_RADIUS, irad = orad - LINE_WIDTH;
2660 int updatesz = orad*2+1;
2661 int tcol = (v & G_FLASH) ? COL_HIGHLIGHT :
2662 (v & G_WARN) ? COL_WARNING : COL_FOREGROUND;
2663 int col = (v & G_ISSEL) ? COL_SELECTED : tcol;
2664 int bg = (v & G_CURSOR) ? COL_CURSOR :
2665 (v & G_MARK) ? COL_MARK : COL_BACKGROUND;
2669 draw_rect_outline(dr, COORD(is->x), COORD(is->y),
2670 TILE_SIZE, TILE_SIZE, COL_GRID);
2673 /* draw a thick circle */
2674 draw_circle(dr, ox, oy, orad, col, col);
2675 draw_circle(dr, ox, oy, irad, bg, bg);
2677 sprintf(str, "%d", is->count);
2678 draw_text(dr, ox, oy, FONT_VARIABLE, ISLAND_NUMSIZE(is),
2679 ALIGN_VCENTRE | ALIGN_HCENTRE, tcol, str);
2681 dsf_debug_draw(dr, state, ds, is->x, is->y);
2682 draw_update(dr, ox - orad, oy - orad, updatesz, updatesz);
2685 static void game_redraw(drawing *dr, game_drawstate *ds, game_state *oldstate,
2686 game_state *state, int dir, game_ui *ui,
2687 float animtime, float flashtime)
2689 int x, y, force = 0, i, j, redraw, lv, lh;
2690 grid_type v, dsv, flash = 0;
2691 struct island *is, *is_drag_src = NULL, *is_drag_dst = NULL;
2694 int f = (int)(flashtime * 5 / FLASH_TIME);
2695 if (f == 1 || f == 3) flash = G_FLASH;
2698 /* Clear screen, if required. */
2701 TILE_SIZE * ds->w + 2 * BORDER,
2702 TILE_SIZE * ds->h + 2 * BORDER, COL_BACKGROUND);
2704 draw_rect_outline(dr,
2705 COORD(0)-1, COORD(0)-1,
2706 TILE_SIZE * ds->w + 2, TILE_SIZE * ds->h + 2,
2709 draw_update(dr, 0, 0,
2710 TILE_SIZE * ds->w + 2 * BORDER,
2711 TILE_SIZE * ds->h + 2 * BORDER);
2716 if (ui->dragx_src != -1 && ui->dragy_src != -1) {
2718 is_drag_src = INDEX(state, gridi, ui->dragx_src, ui->dragy_src);
2719 assert(is_drag_src);
2720 if (ui->dragx_dst != -1 && ui->dragy_dst != -1) {
2721 is_drag_dst = INDEX(state, gridi, ui->dragx_dst, ui->dragy_dst);
2722 assert(is_drag_dst);
2727 if (ui->show_hints != ds->show_hints) {
2729 ds->show_hints = ui->show_hints;
2732 /* Draw all lines (and hints, if we want), but *not* islands. */
2733 for (x = 0; x < ds->w; x++) {
2734 for (y = 0; y < ds->h; y++) {
2735 v = GRID(state, x, y) | flash;
2736 dsv = GRID(ds,x,y) & ~G_REDRAW;
2738 if (v & G_ISLAND) continue;
2741 if (WITHIN(x,is_drag_src->x, is_drag_dst->x) &&
2742 WITHIN(y,is_drag_src->y, is_drag_dst->y))
2745 lines_lvlh(state, ui, x, y, v, &lv, &lh);
2747 /*if (ui->cur_visible && ui->cur_x == x && ui->cur_y == y)
2751 lv != INDEX(ds,lv,x,y) ||
2752 lh != INDEX(ds,lh,x,y) ||
2754 GRID(ds, x, y) = v | G_REDRAW;
2755 INDEX(ds,lv,x,y) = lv;
2756 INDEX(ds,lh,x,y) = lh;
2757 lines_redraw(dr, state, ds, ui, x, y, v, lv, lh);
2759 GRID(ds,x,y) &= ~G_REDRAW;
2764 for (i = 0; i < state->n_islands; i++) {
2765 is = &state->islands[i];
2766 v = GRID(state, is->x, is->y) | flash;
2769 for (j = 0; j < is->adj.npoints; j++) {
2770 if (GRID(ds,is->adj.points[j].x,is->adj.points[j].y) & G_REDRAW) {
2776 if (is == is_drag_src)
2778 else if (is_drag_dst && is == is_drag_dst)
2782 if (island_impossible(is, v & G_MARK)) v |= G_WARN;
2784 if (ui->cur_visible && ui->cur_x == is->x && ui->cur_y == is->y)
2787 if ((v != GRID(ds, is->x, is->y)) || force || redraw) {
2788 GRID(ds,is->x,is->y) = v;
2789 island_redraw(dr, state, ds, is, v);
2794 static float game_anim_length(game_state *oldstate, game_state *newstate,
2795 int dir, game_ui *ui)
2800 static float game_flash_length(game_state *oldstate, game_state *newstate,
2801 int dir, game_ui *ui)
2803 if (!oldstate->completed && newstate->completed &&
2804 !oldstate->solved && !newstate->solved)
2810 static int game_status(game_state *state)
2812 return state->completed ? +1 : 0;
2815 static int game_timing_state(game_state *state, game_ui *ui)
2820 static void game_print_size(game_params *params, float *x, float *y)
2824 /* 10mm squares by default. */
2825 game_compute_size(params, 1000, &pw, &ph);
2830 static void game_print(drawing *dr, game_state *state, int ts)
2832 int ink = print_mono_colour(dr, 0);
2833 int paper = print_mono_colour(dr, 1);
2834 int x, y, cx, cy, i, nl;
2838 /* Ick: fake up `ds->tilesize' for macro expansion purposes */
2839 game_drawstate ads, *ds = &ads;
2842 /* I don't think this wants a border. */
2845 loff = ts / (8 * sqrt((state->params.maxb - 1)));
2846 print_line_width(dr, ts / 12);
2847 for (x = 0; x < state->w; x++) {
2848 for (y = 0; y < state->h; y++) {
2849 cx = COORD(x); cy = COORD(y);
2850 grid = GRID(state,x,y);
2851 nl = INDEX(state,lines,x,y);
2853 if (grid & G_ISLAND) continue;
2854 if (grid & G_LINEV) {
2855 for (i = 0; i < nl; i++)
2856 draw_line(dr, cx+ts/2+(2*i-nl+1)*loff, cy,
2857 cx+ts/2+(2*i-nl+1)*loff, cy+ts, ink);
2859 if (grid & G_LINEH) {
2860 for (i = 0; i < nl; i++)
2861 draw_line(dr, cx, cy+ts/2+(2*i-nl+1)*loff,
2862 cx+ts, cy+ts/2+(2*i-nl+1)*loff, ink);
2868 for (i = 0; i < state->n_islands; i++) {
2870 struct island *is = &state->islands[i];
2871 grid = GRID(state, is->x, is->y);
2872 cx = COORD(is->x) + ts/2;
2873 cy = COORD(is->y) + ts/2;
2875 draw_circle(dr, cx, cy, ISLAND_RADIUS, paper, ink);
2877 sprintf(str, "%d", is->count);
2878 draw_text(dr, cx, cy, FONT_VARIABLE, ISLAND_NUMSIZE(is),
2879 ALIGN_VCENTRE | ALIGN_HCENTRE, ink, str);
2884 #define thegame bridges
2887 const struct game thegame = {
2888 "Bridges", "games.bridges", "bridges",
2895 TRUE, game_configure, custom_params,
2903 TRUE, game_can_format_as_text_now, game_text_format,
2911 PREFERRED_TILE_SIZE, game_compute_size, game_set_size,
2914 game_free_drawstate,
2919 TRUE, FALSE, game_print_size, game_print,
2920 FALSE, /* wants_statusbar */
2921 FALSE, game_timing_state,
2922 REQUIRE_RBUTTON, /* flags */
2925 /* vim: set shiftwidth=4 tabstop=8: */