ref: 4227ac1fd5dc25c247e7526526079b85e1890766
dir: /bridges.c/
/* * bridges.c: Implementation of the Nikoli game 'Bridges'. * * Things still to do: * * - The solver's algorithmic design is not really ideal. It makes * use of the same data representation as gameplay uses, which * often looks like a tempting reuse of code but isn't always a * good idea. In this case, it's unpleasant that each edge of the * graph ends up represented as multiple squares on a grid, with * flags indicating when edges and non-edges cross; that's useful * when the result can be directly translated into positions of * graphics on the display, but in purely internal work it makes * even simple manipulations during solving more painful than they * should be, and complex ones have no choice but to modify the * data structures temporarily, test things, and put them back. I * envisage a complete solver rewrite along the following lines: * + We have a collection of vertices (islands) and edges * (potential bridge locations, i.e. pairs of horizontal or * vertical islands with no other island in between). * + Each edge has an associated list of edges that cross it, and * hence with which it is mutually exclusive. * + For each edge, we track the min and max number of bridges we * currently think possible. * + For each vertex, we track the number of _liberties_ it has, * i.e. its clue number minus the min bridge count for each edge * out of it. * + We also maintain a dsf that identifies sets of vertices which * are connected components of the puzzle so far, and for each * equivalence class we track the total number of liberties for * that component. (The dsf mechanism will also already track * the size of each component, i.e. number of islands.) * + So incrementing the min for an edge requires processing along * the lines of: * - set the max for all edges crossing that one to zero * - decrement the liberty count for the vertex at each end, * and also for each vertex's equivalence class (NB they may * be the same class) * - unify the two equivalence classes if they're not already, * and if so, set the liberty count for the new class to be * the sum of the previous two. * + Decrementing the max is much easier, however. * + With this data structure the really fiddly stuff in stage3() * becomes more or less trivial, because it's now a quick job to * find out whether an island would form an isolated subgraph if * connected to a given subset of its neighbours: * - identify the connected components containing the test * vertex and its putative new neighbours (but be careful not * to count a component more than once if two or more of the * vertices involved are already in the same one) * - find the sum of those components' liberty counts, and also * the total number of islands involved * - if the total liberty count of the connected components is * exactly equal to twice the number of edges we'd be adding * (of course each edge destroys two liberties, one at each * end) then these components would become a subgraph with * zero liberties if connected together. * - therefore, if that subgraph also contains fewer than the * total number of islands, it's disallowed. * - As mentioned in stage3(), once we've identified such a * disallowed pattern, we have two choices for what to do * with it: if the candidate set of neighbours has size 1 we * can reduce the max for the edge to that one neighbour, * whereas if its complement has size 1 we can increase the * min for the edge to the _omitted_ neighbour. * * - write a recursive solver? */ #include <stdio.h> #include <stdlib.h> #include <string.h> #include <assert.h> #include <ctype.h> #include <limits.h> #ifdef NO_TGMATH_H # include <math.h> #else # include <tgmath.h> #endif #include "puzzles.h" /* Turn this on for hints about which lines are considered possibilities. */ #undef DRAW_GRID /* --- structures for params, state, etc. --- */ #define MAX_BRIDGES 4 #define PREFERRED_TILE_SIZE 24 #define TILE_SIZE (ds->tilesize) #define BORDER (TILE_SIZE / 2) #define COORD(x) ( (x) * TILE_SIZE + BORDER ) #define FROMCOORD(x) ( ((x) - BORDER + TILE_SIZE) / TILE_SIZE - 1 ) #define FLASH_TIME 0.50F enum { COL_BACKGROUND, COL_FOREGROUND, COL_HIGHLIGHT, COL_LOWLIGHT, COL_SELECTED, COL_MARK, COL_HINT, COL_GRID, COL_WARNING, COL_CURSOR, NCOLOURS }; struct game_params { int w, h, maxb; int islands, expansion; /* %age of island squares, %age chance of expansion */ bool allowloops; int difficulty; }; /* general flags used by all structs */ #define G_ISLAND 0x0001 #define G_LINEV 0x0002 /* contains a vert. line */ #define G_LINEH 0x0004 /* contains a horiz. line (mutex with LINEV) */ #define G_LINE (G_LINEV|G_LINEH) #define G_MARKV 0x0008 #define G_MARKH 0x0010 #define G_MARK (G_MARKV|G_MARKH) #define G_NOLINEV 0x0020 #define G_NOLINEH 0x0040 #define G_NOLINE (G_NOLINEV|G_NOLINEH) /* flags used by the error checker */ #define G_WARN 0x0080 /* flags used by the solver etc. */ #define G_SWEEP 0x1000 #define G_FLAGSH (G_LINEH|G_MARKH|G_NOLINEH) #define G_FLAGSV (G_LINEV|G_MARKV|G_NOLINEV) typedef unsigned int grid_type; /* change me later if we invent > 16 bits of flags. */ struct solver_state { DSF *dsf, *tmpdsf; int *comptspaces, *tmpcompspaces; int refcount; }; /* state->gridi is an optimisation; it stores the pointer to the island * structs indexed by (x,y). It's not strictly necessary (we could use * find234 instead), but Purify showed that board generation (mostly the solver) * was spending 60% of its time in find234. */ struct surrounds { /* cloned from lightup.c */ struct { int x, y, dx, dy, off; } points[4]; int npoints, nislands; }; struct island { game_state *state; int x, y, count; struct surrounds adj; }; struct game_state { int w, h, maxb; bool completed, solved; bool allowloops; grid_type *grid; struct island *islands; int n_islands, n_islands_alloc; game_params params; /* used by the aux solver. */ #define N_WH_ARRAYS 5 char *wha, *possv, *possh, *lines, *maxv, *maxh; struct island **gridi; struct solver_state *solver; /* refcounted */ }; #define GRIDSZ(s) ((s)->w * (s)->h * sizeof(grid_type)) #define INGRID(s,x,y) ((x) >= 0 && (x) < (s)->w && (y) >= 0 && (y) < (s)->h) #define DINDEX(x,y) ((y)*state->w + (x)) #define INDEX(s,g,x,y) ((s)->g[(y)*((s)->w) + (x)]) #define IDX(s,g,i) ((s)->g[(i)]) #define GRID(s,x,y) INDEX(s,grid,x,y) #define POSSIBLES(s,dx,x,y) ((dx) ? (INDEX(s,possh,x,y)) : (INDEX(s,possv,x,y))) #define MAXIMUM(s,dx,x,y) ((dx) ? (INDEX(s,maxh,x,y)) : (INDEX(s,maxv,x,y))) #define GRIDCOUNT(s,x,y,f) ((GRID(s,x,y) & (f)) ? (INDEX(s,lines,x,y)) : 0) #define WITHIN2(x,min,max) ((x) >= (min) && (x) <= (max)) #define WITHIN(x,min,max) ((min) > (max) ? \ WITHIN2(x,max,min) : WITHIN2(x,min,max)) /* --- island struct and tree support functions --- */ #define ISLAND_ORTH(is,j,f,df) \ (is->f + (is->adj.points[(j)].off*is->adj.points[(j)].df)) #define ISLAND_ORTHX(is,j) ISLAND_ORTH(is,j,x,dx) #define ISLAND_ORTHY(is,j) ISLAND_ORTH(is,j,y,dy) static void fixup_islands_for_realloc(game_state *state) { int i; for (i = 0; i < state->w*state->h; i++) state->gridi[i] = NULL; for (i = 0; i < state->n_islands; i++) { struct island *is = &state->islands[i]; is->state = state; INDEX(state, gridi, is->x, is->y) = is; } } static bool game_can_format_as_text_now(const game_params *params) { return true; } static char *game_text_format(const game_state *state) { int x, y, len, nl; char *ret, *p; struct island *is; grid_type grid; len = (state->h) * (state->w+1) + 1; ret = snewn(len, char); p = ret; for (y = 0; y < state->h; y++) { for (x = 0; x < state->w; x++) { grid = GRID(state,x,y); nl = INDEX(state,lines,x,y); is = INDEX(state, gridi, x, y); if (is) { *p++ = '0' + is->count; } else if (grid & G_LINEV) { *p++ = (nl > 1) ? '"' : (nl == 1) ? '|' : '!'; /* gaah, want a double-bar. */ } else if (grid & G_LINEH) { *p++ = (nl > 1) ? '=' : (nl == 1) ? '-' : '~'; } else { *p++ = '.'; } } *p++ = '\n'; } *p++ = '\0'; assert(p - ret == len); return ret; } static void debug_state(game_state *state) { char *textversion = game_text_format(state); debug(("%s", textversion)); sfree(textversion); } /*static void debug_possibles(game_state *state) { int x, y; debug(("possh followed by possv\n")); for (y = 0; y < state->h; y++) { for (x = 0; x < state->w; x++) { debug(("%d", POSSIBLES(state, 1, x, y))); } debug((" ")); for (x = 0; x < state->w; x++) { debug(("%d", POSSIBLES(state, 0, x, y))); } debug(("\n")); } debug(("\n")); for (y = 0; y < state->h; y++) { for (x = 0; x < state->w; x++) { debug(("%d", MAXIMUM(state, 1, x, y))); } debug((" ")); for (x = 0; x < state->w; x++) { debug(("%d", MAXIMUM(state, 0, x, y))); } debug(("\n")); } debug(("\n")); }*/ static void island_set_surrounds(struct island *is) { assert(INGRID(is->state,is->x,is->y)); is->adj.npoints = is->adj.nislands = 0; #define ADDPOINT(cond,ddx,ddy) do {\ if (cond) { \ is->adj.points[is->adj.npoints].x = is->x+(ddx); \ is->adj.points[is->adj.npoints].y = is->y+(ddy); \ is->adj.points[is->adj.npoints].dx = (ddx); \ is->adj.points[is->adj.npoints].dy = (ddy); \ is->adj.points[is->adj.npoints].off = 0; \ is->adj.npoints++; \ } } while(0) ADDPOINT(is->x > 0, -1, 0); ADDPOINT(is->x < (is->state->w-1), +1, 0); ADDPOINT(is->y > 0, 0, -1); ADDPOINT(is->y < (is->state->h-1), 0, +1); } static void island_find_orthogonal(struct island *is) { /* fills in the rest of the 'surrounds' structure, assuming * all other islands are now in place. */ int i, x, y, dx, dy, off; is->adj.nislands = 0; for (i = 0; i < is->adj.npoints; i++) { dx = is->adj.points[i].dx; dy = is->adj.points[i].dy; x = is->x + dx; y = is->y + dy; off = 1; is->adj.points[i].off = 0; while (INGRID(is->state, x, y)) { if (GRID(is->state, x, y) & G_ISLAND) { is->adj.points[i].off = off; is->adj.nislands++; /*debug(("island (%d,%d) has orth is. %d*(%d,%d) away at (%d,%d).\n", is->x, is->y, off, dx, dy, ISLAND_ORTHX(is,i), ISLAND_ORTHY(is,i)));*/ goto foundisland; } off++; x += dx; y += dy; } foundisland: ; } } static bool island_hasbridge(struct island *is, int direction) { int x = is->adj.points[direction].x; int y = is->adj.points[direction].y; grid_type gline = is->adj.points[direction].dx ? G_LINEH : G_LINEV; if (GRID(is->state, x, y) & gline) return true; return false; } static struct island *island_find_connection(struct island *is, int adjpt) { struct island *is_r; assert(adjpt < is->adj.npoints); if (!is->adj.points[adjpt].off) return NULL; if (!island_hasbridge(is, adjpt)) return NULL; is_r = INDEX(is->state, gridi, ISLAND_ORTHX(is, adjpt), ISLAND_ORTHY(is, adjpt)); assert(is_r); return is_r; } static struct island *island_add(game_state *state, int x, int y, int count) { struct island *is; bool realloced = false; assert(!(GRID(state,x,y) & G_ISLAND)); GRID(state,x,y) |= G_ISLAND; state->n_islands++; if (state->n_islands > state->n_islands_alloc) { state->n_islands_alloc = state->n_islands * 2; state->islands = sresize(state->islands, state->n_islands_alloc, struct island); realloced = true; } is = &state->islands[state->n_islands-1]; memset(is, 0, sizeof(struct island)); is->state = state; is->x = x; is->y = y; is->count = count; island_set_surrounds(is); if (realloced) fixup_islands_for_realloc(state); else INDEX(state, gridi, x, y) = is; return is; } /* n = -1 means 'flip NOLINE flags [and set line to 0].' */ static void island_join(struct island *i1, struct island *i2, int n, bool is_max) { game_state *state = i1->state; int s, e, x, y; assert(i1->state == i2->state); assert(n >= -1 && n <= i1->state->maxb); if (i1->x == i2->x) { x = i1->x; if (i1->y < i2->y) { s = i1->y+1; e = i2->y-1; } else { s = i2->y+1; e = i1->y-1; } for (y = s; y <= e; y++) { if (is_max) { INDEX(state,maxv,x,y) = n; } else { if (n < 0) { GRID(state,x,y) ^= G_NOLINEV; } else if (n == 0) { GRID(state,x,y) &= ~G_LINEV; } else { GRID(state,x,y) |= G_LINEV; INDEX(state,lines,x,y) = n; } } } } else if (i1->y == i2->y) { y = i1->y; if (i1->x < i2->x) { s = i1->x+1; e = i2->x-1; } else { s = i2->x+1; e = i1->x-1; } for (x = s; x <= e; x++) { if (is_max) { INDEX(state,maxh,x,y) = n; } else { if (n < 0) { GRID(state,x,y) ^= G_NOLINEH; } else if (n == 0) { GRID(state,x,y) &= ~G_LINEH; } else { GRID(state,x,y) |= G_LINEH; INDEX(state,lines,x,y) = n; } } } } else { assert(!"island_join: islands not orthogonal."); } } /* Counts the number of bridges currently attached to the island. */ static int island_countbridges(struct island *is) { int i, c = 0; for (i = 0; i < is->adj.npoints; i++) { c += GRIDCOUNT(is->state, is->adj.points[i].x, is->adj.points[i].y, is->adj.points[i].dx ? G_LINEH : G_LINEV); } /*debug(("island count for (%d,%d) is %d.\n", is->x, is->y, c));*/ return c; } static int island_adjspace(struct island *is, bool marks, int missing, int direction) { int x, y, poss, curr, dx; grid_type gline, mline; x = is->adj.points[direction].x; y = is->adj.points[direction].y; dx = is->adj.points[direction].dx; gline = dx ? G_LINEH : G_LINEV; if (marks) { mline = dx ? G_MARKH : G_MARKV; if (GRID(is->state,x,y) & mline) return 0; } poss = POSSIBLES(is->state, dx, x, y); poss = min(poss, missing); curr = GRIDCOUNT(is->state, x, y, gline); poss = min(poss, MAXIMUM(is->state, dx, x, y) - curr); return poss; } /* Counts the number of bridge spaces left around the island; * expects the possibles to be up-to-date. */ static int island_countspaces(struct island *is, bool marks) { int i, c = 0, missing; missing = is->count - island_countbridges(is); if (missing < 0) return 0; for (i = 0; i < is->adj.npoints; i++) { c += island_adjspace(is, marks, missing, i); } return c; } /* Returns a bridge count rather than a boolean */ static int island_isadj(struct island *is, int direction) { int x, y; grid_type gline, mline; x = is->adj.points[direction].x; y = is->adj.points[direction].y; mline = is->adj.points[direction].dx ? G_MARKH : G_MARKV; gline = is->adj.points[direction].dx ? G_LINEH : G_LINEV; if (GRID(is->state, x, y) & mline) { /* If we're marked (i.e. the thing to attach to is complete) * only count an adjacency if we're already attached. */ return GRIDCOUNT(is->state, x, y, gline); } else { /* If we're unmarked, count possible adjacency iff it's * flagged as POSSIBLE. */ return POSSIBLES(is->state, is->adj.points[direction].dx, x, y); } return 0; } /* Counts the no. of possible adjacent islands (including islands * we're already connected to). */ static int island_countadj(struct island *is) { int i, nadj = 0; for (i = 0; i < is->adj.npoints; i++) { if (island_isadj(is, i)) nadj++; } return nadj; } static void island_togglemark(struct island *is) { int i, j, x, y, o; struct island *is_loop; /* mark the island... */ GRID(is->state, is->x, is->y) ^= G_MARK; /* ...remove all marks on non-island squares... */ for (x = 0; x < is->state->w; x++) { for (y = 0; y < is->state->h; y++) { if (!(GRID(is->state, x, y) & G_ISLAND)) GRID(is->state, x, y) &= ~G_MARK; } } /* ...and add marks to squares around marked islands. */ for (i = 0; i < is->state->n_islands; i++) { is_loop = &is->state->islands[i]; if (!(GRID(is_loop->state, is_loop->x, is_loop->y) & G_MARK)) continue; for (j = 0; j < is_loop->adj.npoints; j++) { /* if this direction takes us to another island, mark all * squares between the two islands. */ if (!is_loop->adj.points[j].off) continue; assert(is_loop->adj.points[j].off > 1); for (o = 1; o < is_loop->adj.points[j].off; o++) { GRID(is_loop->state, is_loop->x + is_loop->adj.points[j].dx*o, is_loop->y + is_loop->adj.points[j].dy*o) |= is_loop->adj.points[j].dy ? G_MARKV : G_MARKH; } } } } static bool island_impossible(struct island *is, bool strict) { int curr = island_countbridges(is), nspc = is->count - curr, nsurrspc; int i, poss; struct island *is_orth; if (nspc < 0) { debug(("island at (%d,%d) impossible because full.\n", is->x, is->y)); return true; /* too many bridges */ } else if ((curr + island_countspaces(is, false)) < is->count) { debug(("island at (%d,%d) impossible because not enough spaces.\n", is->x, is->y)); return true; /* impossible to create enough bridges */ } else if (strict && curr < is->count) { debug(("island at (%d,%d) impossible because locked.\n", is->x, is->y)); return true; /* not enough bridges and island is locked */ } /* Count spaces in surrounding islands. */ nsurrspc = 0; for (i = 0; i < is->adj.npoints; i++) { int ifree, dx = is->adj.points[i].dx; if (!is->adj.points[i].off) continue; poss = POSSIBLES(is->state, dx, is->adj.points[i].x, is->adj.points[i].y); if (poss == 0) continue; is_orth = INDEX(is->state, gridi, ISLAND_ORTHX(is,i), ISLAND_ORTHY(is,i)); assert(is_orth); ifree = is_orth->count - island_countbridges(is_orth); if (ifree > 0) { /* * ifree is the number of bridges unfilled in the other * island, which is clearly an upper bound on the number * of extra bridges this island may run to it. * * Another upper bound is the number of bridges unfilled * on the specific line between here and there. We must * take the minimum of both. */ int bmax = MAXIMUM(is->state, dx, is->adj.points[i].x, is->adj.points[i].y); int bcurr = GRIDCOUNT(is->state, is->adj.points[i].x, is->adj.points[i].y, dx ? G_LINEH : G_LINEV); assert(bcurr <= bmax); nsurrspc += min(ifree, bmax - bcurr); } } if (nsurrspc < nspc) { debug(("island at (%d,%d) impossible: surr. islands %d spc, need %d.\n", is->x, is->y, nsurrspc, nspc)); return true; /* not enough spaces around surrounding islands to fill this one. */ } return false; } /* --- Game parameter functions --- */ #define DEFAULT_PRESET 0 static const struct game_params bridges_presets[] = { { 7, 7, 2, 30, 10, 1, 0 }, { 7, 7, 2, 30, 10, 1, 1 }, { 7, 7, 2, 30, 10, 1, 2 }, { 10, 10, 2, 30, 10, 1, 0 }, { 10, 10, 2, 30, 10, 1, 1 }, { 10, 10, 2, 30, 10, 1, 2 }, { 15, 15, 2, 30, 10, 1, 0 }, { 15, 15, 2, 30, 10, 1, 1 }, { 15, 15, 2, 30, 10, 1, 2 }, }; static game_params *default_params(void) { game_params *ret = snew(game_params); *ret = bridges_presets[DEFAULT_PRESET]; return ret; } static bool game_fetch_preset(int i, char **name, game_params **params) { game_params *ret; char buf[80]; if (i < 0 || i >= lenof(bridges_presets)) return false; ret = default_params(); *ret = bridges_presets[i]; *params = ret; sprintf(buf, "%dx%d %s", ret->w, ret->h, ret->difficulty == 0 ? "easy" : ret->difficulty == 1 ? "medium" : "hard"); *name = dupstr(buf); return true; } static void free_params(game_params *params) { sfree(params); } static game_params *dup_params(const game_params *params) { game_params *ret = snew(game_params); *ret = *params; /* structure copy */ return ret; } #define EATNUM(x) do { \ (x) = atoi(string); \ while (*string && isdigit((unsigned char)*string)) string++; \ } while(0) static void decode_params(game_params *params, char const *string) { EATNUM(params->w); params->h = params->w; if (*string == 'x') { string++; EATNUM(params->h); } if (*string == 'i') { string++; EATNUM(params->islands); } if (*string == 'e') { string++; EATNUM(params->expansion); } if (*string == 'm') { string++; EATNUM(params->maxb); } params->allowloops = true; if (*string == 'L') { string++; params->allowloops = false; } if (*string == 'd') { string++; EATNUM(params->difficulty); } } static char *encode_params(const game_params *params, bool full) { char buf[80]; if (full) { sprintf(buf, "%dx%di%de%dm%d%sd%d", params->w, params->h, params->islands, params->expansion, params->maxb, params->allowloops ? "" : "L", params->difficulty); } else { sprintf(buf, "%dx%dm%d%s", params->w, params->h, params->maxb, params->allowloops ? "" : "L"); } return dupstr(buf); } static config_item *game_configure(const game_params *params) { config_item *ret; char buf[80]; ret = snewn(8, config_item); ret[0].name = "Width"; ret[0].type = C_STRING; sprintf(buf, "%d", params->w); ret[0].u.string.sval = dupstr(buf); ret[1].name = "Height"; ret[1].type = C_STRING; sprintf(buf, "%d", params->h); ret[1].u.string.sval = dupstr(buf); ret[2].name = "Difficulty"; ret[2].type = C_CHOICES; ret[2].u.choices.choicenames = ":Easy:Medium:Hard"; ret[2].u.choices.selected = params->difficulty; ret[3].name = "Allow loops"; ret[3].type = C_BOOLEAN; ret[3].u.boolean.bval = params->allowloops; ret[4].name = "Max. bridges per direction"; ret[4].type = C_CHOICES; ret[4].u.choices.choicenames = ":1:2:3:4"; /* keep up-to-date with * MAX_BRIDGES */ ret[4].u.choices.selected = params->maxb - 1; ret[5].name = "%age of island squares"; ret[5].type = C_CHOICES; ret[5].u.choices.choicenames = ":5%:10%:15%:20%:25%:30%"; ret[5].u.choices.selected = (params->islands / 5)-1; ret[6].name = "Expansion factor (%age)"; ret[6].type = C_CHOICES; ret[6].u.choices.choicenames = ":0%:10%:20%:30%:40%:50%:60%:70%:80%:90%:100%"; ret[6].u.choices.selected = params->expansion / 10; ret[7].name = NULL; ret[7].type = C_END; return ret; } static game_params *custom_params(const config_item *cfg) { game_params *ret = snew(game_params); ret->w = atoi(cfg[0].u.string.sval); ret->h = atoi(cfg[1].u.string.sval); ret->difficulty = cfg[2].u.choices.selected; ret->allowloops = cfg[3].u.boolean.bval; ret->maxb = cfg[4].u.choices.selected + 1; ret->islands = (cfg[5].u.choices.selected + 1) * 5; ret->expansion = cfg[6].u.choices.selected * 10; return ret; } static const char *validate_params(const game_params *params, bool full) { if (params->w < 3 || params->h < 3) return "Width and height must be at least 3"; if (params->w > INT_MAX / params->h) return "Width times height must not be unreasonably large"; if (params->maxb < 1 || params->maxb > MAX_BRIDGES) return "Too many bridges."; if (full) { if (params->islands <= 0 || params->islands > 30) return "%age of island squares must be between 1% and 30%"; if (params->expansion < 0 || params->expansion > 100) return "Expansion factor must be between 0 and 100"; } return NULL; } /* --- Game encoding and differences --- */ static char *encode_game(game_state *state) { char *ret, *p; int wh = state->w*state->h, run, x, y; struct island *is; ret = snewn(wh + 1, char); p = ret; run = 0; for (y = 0; y < state->h; y++) { for (x = 0; x < state->w; x++) { is = INDEX(state, gridi, x, y); if (is) { if (run) { *p++ = ('a'-1) + run; run = 0; } if (is->count < 10) *p++ = '0' + is->count; else *p++ = 'A' + (is->count - 10); } else { if (run == 26) { *p++ = ('a'-1) + run; run = 0; } run++; } } } if (run) { *p++ = ('a'-1) + run; run = 0; } *p = '\0'; assert(p - ret <= wh); return ret; } static char *game_state_diff(const game_state *src, const game_state *dest) { int movesize = 256, movelen = 0; char *move = snewn(movesize, char), buf[80]; int i, d, x, y, len; grid_type gline, nline; struct island *is_s, *is_d, *is_orth; #define APPEND do { \ if (movelen + len >= movesize) { \ movesize = movelen + len + 256; \ move = sresize(move, movesize, char); \ } \ strcpy(move + movelen, buf); \ movelen += len; \ } while(0) move[movelen++] = 'S'; move[movelen] = '\0'; assert(src->n_islands == dest->n_islands); for (i = 0; i < src->n_islands; i++) { is_s = &src->islands[i]; is_d = &dest->islands[i]; assert(is_s->x == is_d->x); assert(is_s->y == is_d->y); assert(is_s->adj.npoints == is_d->adj.npoints); /* more paranoia */ for (d = 0; d < is_s->adj.npoints; d++) { if (is_s->adj.points[d].dx == -1 || is_s->adj.points[d].dy == -1) continue; x = is_s->adj.points[d].x; y = is_s->adj.points[d].y; gline = is_s->adj.points[d].dx ? G_LINEH : G_LINEV; nline = is_s->adj.points[d].dx ? G_NOLINEH : G_NOLINEV; is_orth = INDEX(dest, gridi, ISLAND_ORTHX(is_d, d), ISLAND_ORTHY(is_d, d)); if (GRIDCOUNT(src, x, y, gline) != GRIDCOUNT(dest, x, y, gline)) { assert(is_orth); len = sprintf(buf, ";L%d,%d,%d,%d,%d", is_s->x, is_s->y, is_orth->x, is_orth->y, GRIDCOUNT(dest, x, y, gline)); APPEND; } if ((GRID(src,x,y) & nline) != (GRID(dest, x, y) & nline)) { assert(is_orth); len = sprintf(buf, ";N%d,%d,%d,%d", is_s->x, is_s->y, is_orth->x, is_orth->y); APPEND; } } if ((GRID(src, is_s->x, is_s->y) & G_MARK) != (GRID(dest, is_d->x, is_d->y) & G_MARK)) { len = sprintf(buf, ";M%d,%d", is_s->x, is_s->y); APPEND; } } return move; } /* --- Game setup and solving utilities --- */ /* This function is optimised; a Quantify showed that lots of grid-generation time * (>50%) was spent in here. Hence the IDX() stuff. */ static void map_update_possibles(game_state *state) { int x, y, s, e, i, np, maxb, w = state->w, idx; bool bl; struct island *is_s = NULL, *is_f = NULL; /* Run down vertical stripes [un]setting possv... */ for (x = 0; x < state->w; x++) { idx = x; s = e = -1; bl = false; maxb = state->params.maxb; /* placate optimiser */ /* Unset possible flags until we find an island. */ for (y = 0; y < state->h; y++) { is_s = IDX(state, gridi, idx); if (is_s) { maxb = is_s->count; break; } IDX(state, possv, idx) = 0; idx += w; } for (; y < state->h; y++) { maxb = min(maxb, IDX(state, maxv, idx)); is_f = IDX(state, gridi, idx); if (is_f) { assert(is_s); np = min(maxb, is_f->count); if (s != -1) { for (i = s; i <= e; i++) { INDEX(state, possv, x, i) = bl ? 0 : np; } } s = y+1; bl = false; is_s = is_f; maxb = is_s->count; } else { e = y; if (IDX(state,grid,idx) & (G_LINEH|G_NOLINEV)) bl = true; } idx += w; } if (s != -1) { for (i = s; i <= e; i++) INDEX(state, possv, x, i) = 0; } } /* ...and now do horizontal stripes [un]setting possh. */ /* can we lose this clone'n'hack? */ for (y = 0; y < state->h; y++) { idx = y*w; s = e = -1; bl = false; maxb = state->params.maxb; /* placate optimiser */ for (x = 0; x < state->w; x++) { is_s = IDX(state, gridi, idx); if (is_s) { maxb = is_s->count; break; } IDX(state, possh, idx) = 0; idx += 1; } for (; x < state->w; x++) { maxb = min(maxb, IDX(state, maxh, idx)); is_f = IDX(state, gridi, idx); if (is_f) { assert(is_s); np = min(maxb, is_f->count); if (s != -1) { for (i = s; i <= e; i++) { INDEX(state, possh, i, y) = bl ? 0 : np; } } s = x+1; bl = false; is_s = is_f; maxb = is_s->count; } else { e = x; if (IDX(state,grid,idx) & (G_LINEV|G_NOLINEH)) bl = true; } idx += 1; } if (s != -1) { for (i = s; i <= e; i++) INDEX(state, possh, i, y) = 0; } } } static void map_count(game_state *state) { int i, n, ax, ay; grid_type flag, grid; struct island *is; for (i = 0; i < state->n_islands; i++) { is = &state->islands[i]; is->count = 0; for (n = 0; n < is->adj.npoints; n++) { ax = is->adj.points[n].x; ay = is->adj.points[n].y; flag = (ax == is->x) ? G_LINEV : G_LINEH; grid = GRID(state,ax,ay); if (grid & flag) { is->count += INDEX(state,lines,ax,ay); } } } } static void map_find_orthogonal(game_state *state) { int i; for (i = 0; i < state->n_islands; i++) { island_find_orthogonal(&state->islands[i]); } } struct bridges_neighbour_ctx { game_state *state; int i, n, neighbours[4]; }; static int bridges_neighbour(int vertex, void *vctx) { struct bridges_neighbour_ctx *ctx = (struct bridges_neighbour_ctx *)vctx; if (vertex >= 0) { game_state *state = ctx->state; int w = state->w, x = vertex % w, y = vertex / w; grid_type grid = GRID(state, x, y), gline = grid & G_LINE; struct island *is; int x1, y1, x2, y2, i; ctx->i = ctx->n = 0; is = INDEX(state, gridi, x, y); if (is) { for (i = 0; i < is->adj.npoints; i++) { gline = is->adj.points[i].dx ? G_LINEH : G_LINEV; if (GRID(state, is->adj.points[i].x, is->adj.points[i].y) & gline) { ctx->neighbours[ctx->n++] = (is->adj.points[i].y * w + is->adj.points[i].x); } } } else if (gline) { if (gline & G_LINEV) { x1 = x2 = x; y1 = y-1; y2 = y+1; } else { x1 = x-1; x2 = x+1; y1 = y2 = y; } /* Non-island squares with edges in should never be * pointing off the edge of the grid. */ assert(INGRID(state, x1, y1)); assert(INGRID(state, x2, y2)); if (GRID(state, x1, y1) & (gline | G_ISLAND)) ctx->neighbours[ctx->n++] = y1 * w + x1; if (GRID(state, x2, y2) & (gline | G_ISLAND)) ctx->neighbours[ctx->n++] = y2 * w + x2; } } if (ctx->i < ctx->n) return ctx->neighbours[ctx->i++]; else return -1; } static bool map_hasloops(game_state *state, bool mark) { int x, y; struct findloopstate *fls; struct bridges_neighbour_ctx ctx; bool ret; fls = findloop_new_state(state->w * state->h); ctx.state = state; ret = findloop_run(fls, state->w * state->h, bridges_neighbour, &ctx); if (mark) { for (y = 0; y < state->h; y++) { for (x = 0; x < state->w; x++) { int u, v; u = y * state->w + x; for (v = bridges_neighbour(u, &ctx); v >= 0; v = bridges_neighbour(-1, &ctx)) if (findloop_is_loop_edge(fls, u, v)) GRID(state,x,y) |= G_WARN; } } } findloop_free_state(fls); return ret; } static void map_group(game_state *state) { int i, d1, d2; int x, y, x2, y2; DSF *dsf = state->solver->dsf; struct island *is, *is_join; /* Initialise dsf. */ dsf_reinit(dsf); /* For each island, find connected islands right or down * and merge the dsf for the island squares as well as the * bridge squares. */ for (x = 0; x < state->w; x++) { for (y = 0; y < state->h; y++) { GRID(state,x,y) &= ~(G_SWEEP|G_WARN); /* for group_full. */ is = INDEX(state, gridi, x, y); if (!is) continue; d1 = DINDEX(x,y); for (i = 0; i < is->adj.npoints; i++) { /* only want right/down */ if (is->adj.points[i].dx == -1 || is->adj.points[i].dy == -1) continue; is_join = island_find_connection(is, i); if (!is_join) continue; d2 = DINDEX(is_join->x, is_join->y); if (dsf_equivalent(dsf, d1, d2)) { ; /* we have a loop. See comment in map_hasloops. */ /* However, we still want to merge all squares joining * this side-that-makes-a-loop. */ } /* merge all squares between island 1 and island 2. */ for (x2 = x; x2 <= is_join->x; x2++) { for (y2 = y; y2 <= is_join->y; y2++) { d2 = DINDEX(x2,y2); if (d1 != d2) dsf_merge(dsf,d1,d2); } } } } } } static bool map_group_check(game_state *state, int canon, bool warn, int *nislands_r) { DSF *dsf = state->solver->dsf; int nislands = 0; int x, y, i; bool allfull = true; struct island *is; for (i = 0; i < state->n_islands; i++) { is = &state->islands[i]; if (dsf_canonify(dsf, DINDEX(is->x,is->y)) != canon) continue; GRID(state, is->x, is->y) |= G_SWEEP; nislands++; if (island_countbridges(is) != is->count) allfull = false; } if (warn && allfull && nislands != state->n_islands) { /* we're full and this island group isn't the whole set. * Mark all squares with this dsf canon as ERR. */ for (x = 0; x < state->w; x++) { for (y = 0; y < state->h; y++) { if (dsf_canonify(dsf, DINDEX(x,y)) == canon) { GRID(state,x,y) |= G_WARN; } } } } if (nislands_r) *nislands_r = nislands; return allfull; } static bool map_group_full(game_state *state, int *ngroups_r) { DSF *dsf = state->solver->dsf; int ngroups = 0; int i; bool anyfull = false; struct island *is; /* NB this assumes map_group (or sth else) has cleared G_SWEEP. */ for (i = 0; i < state->n_islands; i++) { is = &state->islands[i]; if (GRID(state,is->x,is->y) & G_SWEEP) continue; ngroups++; if (map_group_check(state, dsf_canonify(dsf, DINDEX(is->x,is->y)), true, NULL)) anyfull = true; } *ngroups_r = ngroups; return anyfull; } static bool map_check(game_state *state) { int ngroups; /* Check for loops, if necessary. */ if (!state->allowloops) { if (map_hasloops(state, true)) return false; } /* Place islands into island groups and check for early * satisfied-groups. */ map_group(state); /* clears WARN and SWEEP */ if (map_group_full(state, &ngroups)) { if (ngroups == 1) return true; } return false; } static void map_clear(game_state *state) { int x, y; for (x = 0; x < state->w; x++) { for (y = 0; y < state->h; y++) { /* clear most flags; might want to be slightly more careful here. */ GRID(state,x,y) &= G_ISLAND; } } } static void solve_join(struct island *is, int direction, int n, bool is_max) { struct island *is_orth; int d1, d2; DSF *dsf = is->state->solver->dsf; game_state *state = is->state; /* for DINDEX */ is_orth = INDEX(is->state, gridi, ISLAND_ORTHX(is, direction), ISLAND_ORTHY(is, direction)); assert(is_orth); /*debug(("...joining (%d,%d) to (%d,%d) with %d bridge(s).\n", is->x, is->y, is_orth->x, is_orth->y, n));*/ island_join(is, is_orth, n, is_max); if (n > 0 && !is_max) { d1 = DINDEX(is->x, is->y); d2 = DINDEX(is_orth->x, is_orth->y); if (!dsf_equivalent(dsf, d1, d2)) dsf_merge(dsf, d1, d2); } } static int solve_fillone(struct island *is) { int i, nadded = 0; debug(("solve_fillone for island (%d,%d).\n", is->x, is->y)); for (i = 0; i < is->adj.npoints; i++) { if (island_isadj(is, i)) { if (island_hasbridge(is, i)) { /* already attached; do nothing. */; } else { solve_join(is, i, 1, false); nadded++; } } } return nadded; } static int solve_fill(struct island *is) { /* for each unmarked adjacent, make sure we convert every possible bridge * to a real one, and then work out the possibles afresh. */ int i, nnew, ncurr, nadded = 0, missing; debug(("solve_fill for island (%d,%d).\n", is->x, is->y)); missing = is->count - island_countbridges(is); if (missing < 0) return 0; /* very like island_countspaces. */ for (i = 0; i < is->adj.npoints; i++) { nnew = island_adjspace(is, true, missing, i); if (nnew) { ncurr = GRIDCOUNT(is->state, is->adj.points[i].x, is->adj.points[i].y, is->adj.points[i].dx ? G_LINEH : G_LINEV); solve_join(is, i, nnew + ncurr, false); nadded += nnew; } } return nadded; } static bool solve_island_stage1(struct island *is, bool *didsth_r) { int bridges = island_countbridges(is); int nspaces = island_countspaces(is, true); int nadj = island_countadj(is); bool didsth = false; assert(didsth_r); /*debug(("island at (%d,%d) filled %d/%d (%d spc) nadj %d\n", is->x, is->y, bridges, is->count, nspaces, nadj));*/ if (bridges > is->count) { /* We only ever add bridges when we're sure they fit, or that's * the only place they can go. If we've added bridges such that * another island has become wrong, the puzzle must not have had * a solution. */ debug(("...island at (%d,%d) is overpopulated!\n", is->x, is->y)); return false; } else if (bridges == is->count) { /* This island is full. Make sure it's marked (and update * possibles if we did). */ if (!(GRID(is->state, is->x, is->y) & G_MARK)) { debug(("...marking island (%d,%d) as full.\n", is->x, is->y)); island_togglemark(is); didsth = true; } } else if (GRID(is->state, is->x, is->y) & G_MARK) { debug(("...island (%d,%d) is marked but unfinished!\n", is->x, is->y)); return false; /* island has been marked unfinished; no solution from here. */ } else { /* This is the interesting bit; we try and fill in more information * about this island. */ if (is->count == bridges + nspaces) { if (solve_fill(is) > 0) didsth = true; } else if (is->count > ((nadj-1) * is->state->maxb)) { /* must have at least one bridge in each possible direction. */ if (solve_fillone(is) > 0) didsth = true; } } if (didsth) { map_update_possibles(is->state); *didsth_r = true; } return true; } /* returns true if a new line here would cause a loop. */ static bool solve_island_checkloop(struct island *is, int direction) { struct island *is_orth; DSF *dsf = is->state->solver->dsf; int d1, d2; game_state *state = is->state; if (is->state->allowloops) return false; /* don't care anyway */ if (island_hasbridge(is, direction)) return false; /* already has a bridge */ if (island_isadj(is, direction) == 0) return false; /* no adj island */ is_orth = INDEX(is->state, gridi, ISLAND_ORTHX(is,direction), ISLAND_ORTHY(is,direction)); if (!is_orth) return false; d1 = DINDEX(is->x, is->y); d2 = DINDEX(is_orth->x, is_orth->y); if (dsf_equivalent(dsf, d1, d2)) { /* two islands are connected already; don't join them. */ return true; } return false; } static bool solve_island_stage2(struct island *is, bool *didsth_r) { int navail = 0, nadj, i; bool added = false, removed = false; assert(didsth_r); for (i = 0; i < is->adj.npoints; i++) { if (solve_island_checkloop(is, i)) { debug(("removing possible loop at (%d,%d) direction %d.\n", is->x, is->y, i)); solve_join(is, i, -1, false); map_update_possibles(is->state); removed = true; } else { navail += island_isadj(is, i); /*debug(("stage2: navail for (%d,%d) direction (%d,%d) is %d.\n", is->x, is->y, is->adj.points[i].dx, is->adj.points[i].dy, island_isadj(is, i)));*/ } } /*debug(("island at (%d,%d) navail %d: checking...\n", is->x, is->y, navail));*/ for (i = 0; i < is->adj.npoints; i++) { if (!island_hasbridge(is, i)) { nadj = island_isadj(is, i); if (nadj > 0 && (navail - nadj) < is->count) { /* we couldn't now complete the island without at * least one bridge here; put it in. */ /*debug(("nadj %d, navail %d, is->count %d.\n", nadj, navail, is->count));*/ debug(("island at (%d,%d) direction (%d,%d) must have 1 bridge\n", is->x, is->y, is->adj.points[i].dx, is->adj.points[i].dy)); solve_join(is, i, 1, false); added = true; /*debug_state(is->state); debug_possibles(is->state);*/ } } } if (added) map_update_possibles(is->state); if (added || removed) *didsth_r = true; return true; } static bool solve_island_subgroup(struct island *is, int direction) { struct island *is_join; int nislands; DSF *dsf = is->state->solver->dsf; game_state *state = is->state; debug(("..checking subgroups.\n")); /* if is isn't full, return 0. */ if (island_countbridges(is) < is->count) { debug(("...orig island (%d,%d) not full.\n", is->x, is->y)); return false; } if (direction >= 0) { is_join = INDEX(state, gridi, ISLAND_ORTHX(is, direction), ISLAND_ORTHY(is, direction)); assert(is_join); /* if is_join isn't full, return 0. */ if (island_countbridges(is_join) < is_join->count) { debug(("...dest island (%d,%d) not full.\n", is_join->x, is_join->y)); return false; } } /* Check group membership for is->dsf; if it's full return 1. */ if (map_group_check(state, dsf_canonify(dsf, DINDEX(is->x,is->y)), false, &nislands)) { if (nislands < state->n_islands) { /* we have a full subgroup that isn't the whole set. * This isn't allowed. */ debug(("island at (%d,%d) makes full subgroup, disallowing.\n", is->x, is->y)); return true; } else { debug(("...has finished puzzle.\n")); } } return false; } static bool solve_island_impossible(game_state *state) { struct island *is; int i; /* If any islands are impossible, return 1. */ for (i = 0; i < state->n_islands; i++) { is = &state->islands[i]; if (island_impossible(is, false)) { debug(("island at (%d,%d) has become impossible, disallowing.\n", is->x, is->y)); return true; } } return false; } /* Bear in mind that this function is really rather inefficient. */ static bool solve_island_stage3(struct island *is, bool *didsth_r) { int i, n, x, y, missing, spc, curr, maxb; bool didsth = false; struct solver_state *ss = is->state->solver; assert(didsth_r); missing = is->count - island_countbridges(is); if (missing <= 0) return true; for (i = 0; i < is->adj.npoints; i++) { x = is->adj.points[i].x; y = is->adj.points[i].y; spc = island_adjspace(is, true, missing, i); if (spc == 0) continue; curr = GRIDCOUNT(is->state, x, y, is->adj.points[i].dx ? G_LINEH : G_LINEV); debug(("island at (%d,%d) s3, trying %d - %d bridges.\n", is->x, is->y, curr+1, curr+spc)); /* Now we know that this island could have more bridges, * to bring the total from curr+1 to curr+spc. */ maxb = -1; /* We have to squirrel the dsf away and restore it afterwards; * it is additive only, and can't be removed from. */ dsf_copy(ss->tmpdsf, ss->dsf); for (n = curr+1; n <= curr+spc; n++) { solve_join(is, i, n, false); map_update_possibles(is->state); if (solve_island_subgroup(is, i) || solve_island_impossible(is->state)) { maxb = n-1; debug(("island at (%d,%d) d(%d,%d) new max of %d bridges:\n", is->x, is->y, is->adj.points[i].dx, is->adj.points[i].dy, maxb)); break; } } solve_join(is, i, curr, false); /* put back to before. */ dsf_copy(ss->dsf, ss->tmpdsf); if (maxb != -1) { /*debug_state(is->state);*/ if (maxb == 0) { debug(("...adding NOLINE.\n")); solve_join(is, i, -1, false); /* we can't have any bridges here. */ } else { debug(("...setting maximum\n")); solve_join(is, i, maxb, true); } didsth = true; } map_update_possibles(is->state); } for (i = 0; i < is->adj.npoints; i++) { /* * Now check to see if any currently empty direction must have * at least one bridge in order to avoid forming an isolated * subgraph. This differs from the check above in that it * considers multiple target islands. For example: * * 2 2 4 * 1 3 2 * 3 * 4 * * The example on the left can be handled by the above loop: * it will observe that connecting the central 2 twice to the * left would form an isolated subgraph, and hence it will * restrict that 2 to at most one bridge in that direction. * But the example on the right won't be handled by that loop, * because the deduction requires us to imagine connecting the * 3 to _both_ the 1 and 2 at once to form an isolated * subgraph. * * This pass is necessary _as well_ as the above one, because * neither can do the other's job. In the left one, * restricting the direction which _would_ cause trouble can * be done even if it's not yet clear which of the remaining * directions has to have a compensatory bridge; whereas the * pass below that can handle the right-hand example does need * to know what direction to point the necessary bridge in. * * Neither pass can handle the most general case, in which we * observe that an arbitrary subset of an island's neighbours * would form an isolated subgraph with it if it connected * maximally to them, and hence that at least one bridge must * point to some neighbour outside that subset but we don't * know which neighbour. To handle that, we'd have to have a * richer data format for the solver, which could cope with * recording the idea that at least one of two edges must have * a bridge. */ bool got = false; int before[4]; int j; spc = island_adjspace(is, true, missing, i); if (spc == 0) continue; for (j = 0; j < is->adj.npoints; j++) before[j] = GRIDCOUNT(is->state, is->adj.points[j].x, is->adj.points[j].y, is->adj.points[j].dx ? G_LINEH : G_LINEV); if (before[i] != 0) continue; /* this idea is pointless otherwise */ dsf_copy(ss->tmpdsf, ss->dsf); for (j = 0; j < is->adj.npoints; j++) { spc = island_adjspace(is, true, missing, j); if (spc == 0) continue; if (j == i) continue; solve_join(is, j, before[j] + spc, false); } map_update_possibles(is->state); if (solve_island_subgroup(is, -1)) got = true; for (j = 0; j < is->adj.npoints; j++) solve_join(is, j, before[j], false); dsf_copy(ss->dsf, ss->tmpdsf); if (got) { debug(("island at (%d,%d) must connect in direction (%d,%d) to" " avoid full subgroup.\n", is->x, is->y, is->adj.points[i].dx, is->adj.points[i].dy)); solve_join(is, i, 1, false); didsth = true; } map_update_possibles(is->state); } if (didsth) *didsth_r = didsth; return true; } #define CONTINUE_IF_FULL do { \ if (GRID(state, is->x, is->y) & G_MARK) { \ /* island full, don't try fixing it */ \ continue; \ } } while(0) static int solve_sub(game_state *state, int difficulty, int depth) { struct island *is; int i; while (1) { bool didsth = false; /* First island iteration: things we can work out by looking at * properties of the island as a whole. */ for (i = 0; i < state->n_islands; i++) { is = &state->islands[i]; if (!solve_island_stage1(is, &didsth)) return 0; } if (didsth) continue; else if (difficulty < 1) break; /* Second island iteration: thing we can work out by looking at * properties of individual island connections. */ for (i = 0; i < state->n_islands; i++) { is = &state->islands[i]; CONTINUE_IF_FULL; if (!solve_island_stage2(is, &didsth)) return 0; } if (didsth) continue; else if (difficulty < 2) break; /* Third island iteration: things we can only work out by looking * at groups of islands. */ for (i = 0; i < state->n_islands; i++) { is = &state->islands[i]; if (!solve_island_stage3(is, &didsth)) return 0; } if (didsth) continue; else if (difficulty < 3) break; /* If we can be bothered, write a recursive solver to finish here. */ break; } if (map_check(state)) return 1; /* solved it */ return 0; } static void solve_for_hint(game_state *state) { map_group(state); solve_sub(state, 10, 0); } static int solve_from_scratch(game_state *state, int difficulty) { map_clear(state); map_group(state); map_update_possibles(state); return solve_sub(state, difficulty, 0); } /* --- New game functions --- */ static game_state *new_state(const game_params *params) { game_state *ret = snew(game_state); int wh = params->w * params->h, i; ret->w = params->w; ret->h = params->h; ret->allowloops = params->allowloops; ret->maxb = params->maxb; ret->params = *params; ret->grid = snewn(wh, grid_type); memset(ret->grid, 0, GRIDSZ(ret)); ret->wha = snewn(wh*N_WH_ARRAYS, char); memset(ret->wha, 0, wh*N_WH_ARRAYS*sizeof(char)); ret->possv = ret->wha; ret->possh = ret->wha + wh; ret->lines = ret->wha + wh*2; ret->maxv = ret->wha + wh*3; ret->maxh = ret->wha + wh*4; memset(ret->maxv, ret->maxb, wh*sizeof(char)); memset(ret->maxh, ret->maxb, wh*sizeof(char)); ret->islands = NULL; ret->n_islands = 0; ret->n_islands_alloc = 0; ret->gridi = snewn(wh, struct island *); for (i = 0; i < wh; i++) ret->gridi[i] = NULL; ret->solved = false; ret->completed = false; ret->solver = snew(struct solver_state); ret->solver->dsf = dsf_new(wh); ret->solver->tmpdsf = dsf_new(wh); ret->solver->refcount = 1; return ret; } static game_state *dup_game(const game_state *state) { game_state *ret = snew(game_state); int wh = state->w*state->h; ret->w = state->w; ret->h = state->h; ret->allowloops = state->allowloops; ret->maxb = state->maxb; ret->params = state->params; ret->grid = snewn(wh, grid_type); memcpy(ret->grid, state->grid, GRIDSZ(ret)); ret->wha = snewn(wh*N_WH_ARRAYS, char); memcpy(ret->wha, state->wha, wh*N_WH_ARRAYS*sizeof(char)); ret->possv = ret->wha; ret->possh = ret->wha + wh; ret->lines = ret->wha + wh*2; ret->maxv = ret->wha + wh*3; ret->maxh = ret->wha + wh*4; ret->islands = snewn(state->n_islands, struct island); memcpy(ret->islands, state->islands, state->n_islands * sizeof(struct island)); ret->n_islands = ret->n_islands_alloc = state->n_islands; ret->gridi = snewn(wh, struct island *); fixup_islands_for_realloc(ret); ret->solved = state->solved; ret->completed = state->completed; ret->solver = state->solver; ret->solver->refcount++; return ret; } static void free_game(game_state *state) { if (--state->solver->refcount <= 0) { dsf_free(state->solver->dsf); dsf_free(state->solver->tmpdsf); sfree(state->solver); } sfree(state->islands); sfree(state->gridi); sfree(state->wha); sfree(state->grid); sfree(state); } #define MAX_NEWISLAND_TRIES 50 #define MIN_SENSIBLE_ISLANDS 3 #define ORDER(a,b) do { if (a < b) { int tmp=a; int a=b; int b=tmp; } } while(0) static char *new_game_desc(const game_params *params, random_state *rs, char **aux, bool interactive) { game_state *tobuild = NULL; int i, j, wh = params->w * params->h, x, y, dx, dy; int minx, miny, maxx, maxy, joinx, joiny, newx, newy, diffx, diffy; int ni_req = max((params->islands * wh) / 100, MIN_SENSIBLE_ISLANDS), ni_curr, ni_bad; struct island *is, *is2; char *ret; unsigned int echeck; /* pick a first island position randomly. */ generate: if (tobuild) free_game(tobuild); tobuild = new_state(params); x = random_upto(rs, params->w); y = random_upto(rs, params->h); island_add(tobuild, x, y, 0); ni_curr = 1; ni_bad = 0; debug(("Created initial island at (%d,%d).\n", x, y)); while (ni_curr < ni_req) { /* Pick a random island to try and extend from. */ i = random_upto(rs, tobuild->n_islands); is = &tobuild->islands[i]; /* Pick a random direction to extend in. */ j = random_upto(rs, is->adj.npoints); dx = is->adj.points[j].x - is->x; dy = is->adj.points[j].y - is->y; /* Find out limits of where we could put a new island. */ joinx = joiny = -1; minx = is->x + 2*dx; miny = is->y + 2*dy; /* closest is 2 units away. */ x = is->x+dx; y = is->y+dy; if (GRID(tobuild,x,y) & (G_LINEV|G_LINEH)) { /* already a line next to the island, continue. */ goto bad; } while (1) { if (x < 0 || x >= params->w || y < 0 || y >= params->h) { /* got past the edge; put a possible at the island * and exit. */ maxx = x-dx; maxy = y-dy; goto foundmax; } if (GRID(tobuild,x,y) & G_ISLAND) { /* could join up to an existing island... */ joinx = x; joiny = y; /* ... or make a new one 2 spaces away. */ maxx = x - 2*dx; maxy = y - 2*dy; goto foundmax; } else if (GRID(tobuild,x,y) & (G_LINEV|G_LINEH)) { /* could make a new one 1 space away from the line. */ maxx = x - dx; maxy = y - dy; goto foundmax; } x += dx; y += dy; } foundmax: debug(("Island at (%d,%d) with d(%d,%d) has new positions " "(%d,%d) -> (%d,%d), join (%d,%d).\n", is->x, is->y, dx, dy, minx, miny, maxx, maxy, joinx, joiny)); /* Now we know where we could either put a new island * (between min and max), or (if loops are allowed) could join on * to an existing island (at join). */ if (params->allowloops && joinx != -1 && joiny != -1) { if (random_upto(rs, 100) < (unsigned long)params->expansion) { is2 = INDEX(tobuild, gridi, joinx, joiny); debug(("Joining island at (%d,%d) to (%d,%d).\n", is->x, is->y, is2->x, is2->y)); goto join; } } diffx = (maxx - minx) * dx; diffy = (maxy - miny) * dy; if (diffx < 0 || diffy < 0) goto bad; if (random_upto(rs,100) < (unsigned long)params->expansion) { newx = maxx; newy = maxy; debug(("Creating new island at (%d,%d) (expanded).\n", newx, newy)); } else { newx = minx + random_upto(rs,diffx+1)*dx; newy = miny + random_upto(rs,diffy+1)*dy; debug(("Creating new island at (%d,%d).\n", newx, newy)); } /* check we're not next to island in the other orthogonal direction. */ if ((INGRID(tobuild,newx+dy,newy+dx) && (GRID(tobuild,newx+dy,newy+dx) & G_ISLAND)) || (INGRID(tobuild,newx-dy,newy-dx) && (GRID(tobuild,newx-dy,newy-dx) & G_ISLAND))) { debug(("New location is adjacent to island, skipping.\n")); goto bad; } is2 = island_add(tobuild, newx, newy, 0); /* Must get is again at this point; the array might have * been realloced by island_add... */ is = &tobuild->islands[i]; /* ...but order will not change. */ ni_curr++; ni_bad = 0; join: island_join(is, is2, random_upto(rs, tobuild->maxb)+1, false); debug_state(tobuild); continue; bad: ni_bad++; if (ni_bad > MAX_NEWISLAND_TRIES) { debug(("Unable to create any new islands after %d tries; " "created %d [%d%%] (instead of %d [%d%%] requested).\n", MAX_NEWISLAND_TRIES, ni_curr, ni_curr * 100 / wh, ni_req, ni_req * 100 / wh)); goto generated; } } generated: if (ni_curr == 1) { debug(("Only generated one island (!), retrying.\n")); goto generate; } /* Check we have at least one island on each extremity of the grid. */ echeck = 0; for (x = 0; x < params->w; x++) { if (INDEX(tobuild, gridi, x, 0)) echeck |= 1; if (INDEX(tobuild, gridi, x, params->h-1)) echeck |= 2; } for (y = 0; y < params->h; y++) { if (INDEX(tobuild, gridi, 0, y)) echeck |= 4; if (INDEX(tobuild, gridi, params->w-1, y)) echeck |= 8; } if (echeck != 15) { debug(("Generated grid doesn't fill to sides, retrying.\n")); goto generate; } map_count(tobuild); map_find_orthogonal(tobuild); if (params->difficulty > 0) { if ((ni_curr > MIN_SENSIBLE_ISLANDS) && (solve_from_scratch(tobuild, params->difficulty-1) > 0)) { debug(("Grid is solvable at difficulty %d (too easy); retrying.\n", params->difficulty-1)); goto generate; } } if (solve_from_scratch(tobuild, params->difficulty) == 0) { debug(("Grid not solvable at difficulty %d, (too hard); retrying.\n", params->difficulty)); goto generate; } /* ... tobuild is now solved. We rely on this making the diff for aux. */ debug_state(tobuild); ret = encode_game(tobuild); { game_state *clean = dup_game(tobuild); map_clear(clean); map_update_possibles(clean); *aux = game_state_diff(clean, tobuild); free_game(clean); } free_game(tobuild); return ret; } static const char *validate_desc(const game_params *params, const char *desc) { int i, j, wh = params->w * params->h, nislands = 0; bool *last_row = snewn(params->w, bool); memset(last_row, 0, params->w * sizeof(bool)); for (i = 0; i < wh; i++) { if ((*desc >= '1' && *desc <= '9') || (*desc >= 'A' && *desc <= 'G')) { nislands++; /* Look for other islands to the left and above. */ if ((i % params->w > 0 && last_row[i % params->w - 1]) || last_row[i % params->w]) { sfree(last_row); return "Game description contains joined islands"; } last_row[i % params->w] = true; } else if (*desc >= 'a' && *desc <= 'z') { for (j = 0; j < *desc - 'a' + 1; j++) last_row[(i + j) % params->w] = false; i += *desc - 'a'; /* plus the i++ */ } else if (!*desc) { sfree(last_row); return "Game description shorter than expected"; } else { sfree(last_row); return "Game description contains unexpected character"; } desc++; } sfree(last_row); if (*desc || i > wh) return "Game description longer than expected"; if (nislands < 2) return "Game description has too few islands"; return NULL; } static game_state *new_game_sub(const game_params *params, const char *desc) { game_state *state = new_state(params); int x, y, run = 0; debug(("new_game[_sub]: desc = '%s'.\n", desc)); for (y = 0; y < params->h; y++) { for (x = 0; x < params->w; x++) { char c = '\0'; if (run == 0) { c = *desc++; assert(c != 'S'); if (c >= 'a' && c <= 'z') run = c - 'a' + 1; } if (run > 0) { c = 'S'; run--; } switch (c) { case '1': case '2': case '3': case '4': case '5': case '6': case '7': case '8': case '9': island_add(state, x, y, (c - '0')); break; case 'A': case 'B': case 'C': case 'D': case 'E': case 'F': case 'G': island_add(state, x, y, (c - 'A') + 10); break; case 'S': /* empty square */ break; default: assert(!"Malformed desc."); break; } } } if (*desc) assert(!"Over-long desc."); map_find_orthogonal(state); map_update_possibles(state); return state; } static game_state *new_game(midend *me, const game_params *params, const char *desc) { return new_game_sub(params, desc); } struct game_ui { int dragx_src, dragy_src; /* source; -1 means no drag */ int dragx_dst, dragy_dst; /* src's closest orth island. */ grid_type todraw; bool dragging, drag_is_noline; int nlines; int cur_x, cur_y; /* cursor position */ bool cur_visible; bool show_hints; }; static char *ui_cancel_drag(game_ui *ui) { ui->dragx_src = ui->dragy_src = -1; ui->dragx_dst = ui->dragy_dst = -1; ui->dragging = false; return UI_UPDATE; } static game_ui *new_ui(const game_state *state) { game_ui *ui = snew(game_ui); ui_cancel_drag(ui); ui->cur_x = state->islands[0].x; ui->cur_y = state->islands[0].y; ui->cur_visible = getenv_bool("PUZZLES_SHOW_CURSOR", false); ui->show_hints = false; return ui; } static void free_ui(game_ui *ui) { sfree(ui); } static void game_changed_state(game_ui *ui, const game_state *oldstate, const game_state *newstate) { } static const char *current_key_label(const game_ui *ui, const game_state *state, int button) { if (IS_CURSOR_SELECT(button)) { if (!ui->cur_visible) return ""; /* Actually shows cursor. */ if (ui->dragging || button == CURSOR_SELECT2) return "Finished"; if (GRID(state, ui->cur_x, ui->cur_y) & G_ISLAND) return "Select"; } return ""; } struct game_drawstate { int tilesize; int w, h; unsigned long *grid, *newgrid; int *lv, *lh; bool started, dragging; }; static void game_get_cursor_location(const game_ui *ui, const game_drawstate *ds, const game_state *state, const game_params *params, int *x, int *y, int *w, int *h) { if(ui->cur_visible) { *x = COORD(ui->cur_x); *y = COORD(ui->cur_y); *w = *h = TILE_SIZE; } } /* * The contents of ds->grid are complicated, because of the circular * islands which overlap their own grid square into neighbouring * squares. An island square can contain pieces of the bridges in all * directions, and conversely a bridge square can be intruded on by * islands from any direction. * * So we define one group of flags describing what's important about * an island, and another describing a bridge. Island squares' entries * in ds->grid contain one of the former and four of the latter; bridge * squares, four of the former and _two_ of the latter - because a * horizontal and vertical 'bridge' can cross, when one of them is a * 'no bridge here' pencil mark. * * Bridge flags need to indicate 0-4 actual bridges (3 bits), a 'no * bridge' row of crosses, or a grey hint line; that's 7 * possibilities, so 3 bits suffice. But then we also need to vary the * colours: the bridges can turn COL_WARNING if they're part of a loop * in no-loops mode, COL_HIGHLIGHT during a victory flash, or * COL_SELECTED if they're the bridge the user is currently dragging, * so that's 2 more bits for foreground colour. Also bridges can be * backed by COL_MARK if they're locked by the user, so that's one * more bit, making 6 bits per bridge direction. * * Island flags omit the actual island clue (it never changes during * the game, so doesn't have to be stored in ds->grid to check against * the previous version), so they just need to include 2 bits for * foreground colour (an island can be normal, COL_HIGHLIGHT during * victory, COL_WARNING if its clue is unsatisfiable, or COL_SELECTED * if it's part of the user's drag) and 2 bits for background (normal, * COL_MARK for a locked island, COL_CURSOR for the keyboard cursor). * That's 4 bits per island direction. We must also indicate whether * no island is present at all (in the case where the island is * potentially intruding into the side of a line square), which we do * using the unused 4th value of the background field. * * So an island square needs 4 + 4*6 = 28 bits, while a bridge square * needs 4*4 + 2*6 = 28 bits too. Both only just fit in 32 bits, which * is handy, because otherwise we'd have to faff around forever with * little structs! */ /* Flags for line data */ #define DL_COUNTMASK 0x07 #define DL_COUNT_CROSS 0x06 #define DL_COUNT_HINT 0x07 #define DL_COLMASK 0x18 #define DL_COL_NORMAL 0x00 #define DL_COL_WARNING 0x08 #define DL_COL_FLASH 0x10 #define DL_COL_SELECTED 0x18 #define DL_LOCK 0x20 #define DL_MASK 0x3F /* Flags for island data */ #define DI_COLMASK 0x03 #define DI_COL_NORMAL 0x00 #define DI_COL_FLASH 0x01 #define DI_COL_WARNING 0x02 #define DI_COL_SELECTED 0x03 #define DI_BGMASK 0x0C #define DI_BG_NO_ISLAND 0x00 #define DI_BG_NORMAL 0x04 #define DI_BG_MARK 0x08 #define DI_BG_CURSOR 0x0C #define DI_MASK 0x0F /* Shift counts for the format of a 32-bit word in an island square */ #define D_I_ISLAND_SHIFT 0 #define D_I_LINE_SHIFT_L 4 #define D_I_LINE_SHIFT_R 10 #define D_I_LINE_SHIFT_U 16 #define D_I_LINE_SHIFT_D 24 /* Shift counts for the format of a 32-bit word in a line square */ #define D_L_ISLAND_SHIFT_L 0 #define D_L_ISLAND_SHIFT_R 4 #define D_L_ISLAND_SHIFT_U 8 #define D_L_ISLAND_SHIFT_D 12 #define D_L_LINE_SHIFT_H 16 #define D_L_LINE_SHIFT_V 22 static char *update_drag_dst(const game_state *state, game_ui *ui, const game_drawstate *ds, int nx, int ny) { int ox, oy, dx, dy, i, currl, maxb; struct island *is; grid_type gtype, ntype, mtype, curr; if (ui->dragx_src == -1 || ui->dragy_src == -1) return NULL; ui->dragx_dst = -1; ui->dragy_dst = -1; /* work out which of the four directions we're closest to... */ ox = COORD(ui->dragx_src) + TILE_SIZE/2; oy = COORD(ui->dragy_src) + TILE_SIZE/2; if (abs(nx-ox) < abs(ny-oy)) { dx = 0; dy = (ny-oy) < 0 ? -1 : 1; gtype = G_LINEV; ntype = G_NOLINEV; mtype = G_MARKV; maxb = INDEX(state, maxv, ui->dragx_src+dx, ui->dragy_src+dy); } else { dy = 0; dx = (nx-ox) < 0 ? -1 : 1; gtype = G_LINEH; ntype = G_NOLINEH; mtype = G_MARKH; maxb = INDEX(state, maxh, ui->dragx_src+dx, ui->dragy_src+dy); } if (ui->drag_is_noline) { ui->todraw = ntype; } else { curr = GRID(state, ui->dragx_src+dx, ui->dragy_src+dy); currl = INDEX(state, lines, ui->dragx_src+dx, ui->dragy_src+dy); if (curr & gtype) { if (currl == maxb) { ui->todraw = 0; ui->nlines = 0; } else { ui->todraw = gtype; ui->nlines = currl + 1; } } else { ui->todraw = gtype; ui->nlines = 1; } } /* ... and see if there's an island off in that direction. */ is = INDEX(state, gridi, ui->dragx_src, ui->dragy_src); for (i = 0; i < is->adj.npoints; i++) { if (is->adj.points[i].off == 0) continue; curr = GRID(state, is->x+dx, is->y+dy); if (curr & mtype) continue; /* don't allow changes to marked lines. */ if (ui->drag_is_noline) { if (curr & gtype) continue; /* no no-line where already a line */ } else { if (POSSIBLES(state, dx, is->x+dx, is->y+dy) == 0) continue; /* no line if !possible. */ if (curr & ntype) continue; /* can't have a bridge where there's a no-line. */ } if (is->adj.points[i].dx == dx && is->adj.points[i].dy == dy) { ui->dragx_dst = ISLAND_ORTHX(is,i); ui->dragy_dst = ISLAND_ORTHY(is,i); } } /*debug(("update_drag src (%d,%d) d(%d,%d) dst (%d,%d)\n", ui->dragx_src, ui->dragy_src, dx, dy, ui->dragx_dst, ui->dragy_dst));*/ return UI_UPDATE; } static char *finish_drag(const game_state *state, game_ui *ui) { char buf[80]; if (ui->dragx_src == -1 || ui->dragy_src == -1) return NULL; if (ui->dragx_dst == -1 || ui->dragy_dst == -1) return ui_cancel_drag(ui); if (ui->drag_is_noline) { sprintf(buf, "N%d,%d,%d,%d", ui->dragx_src, ui->dragy_src, ui->dragx_dst, ui->dragy_dst); } else { sprintf(buf, "L%d,%d,%d,%d,%d", ui->dragx_src, ui->dragy_src, ui->dragx_dst, ui->dragy_dst, ui->nlines); } ui_cancel_drag(ui); return dupstr(buf); } static char *interpret_move(const game_state *state, game_ui *ui, const game_drawstate *ds, int x, int y, int button) { int gx = FROMCOORD(x), gy = FROMCOORD(y); char buf[80], *ret; grid_type ggrid = INGRID(state,gx,gy) ? GRID(state,gx,gy) : 0; bool shift = button & MOD_SHFT, control = button & MOD_CTRL; button &= ~MOD_MASK; if (button == LEFT_BUTTON || button == RIGHT_BUTTON) { if (!INGRID(state, gx, gy)) return NULL; ui->cur_visible = false; if (ggrid & G_ISLAND) { ui->dragx_src = gx; ui->dragy_src = gy; return UI_UPDATE; } else return ui_cancel_drag(ui); } else if (button == LEFT_DRAG || button == RIGHT_DRAG) { if (INGRID(state, ui->dragx_src, ui->dragy_src) && (gx != ui->dragx_src || gy != ui->dragy_src) && !(GRID(state,ui->dragx_src,ui->dragy_src) & G_MARK)) { ui->dragging = true; ui->drag_is_noline = (button == RIGHT_DRAG); return update_drag_dst(state, ui, ds, x, y); } else { /* cancel a drag when we go back to the starting point */ ui->dragx_dst = -1; ui->dragy_dst = -1; return UI_UPDATE; } } else if (button == LEFT_RELEASE || button == RIGHT_RELEASE) { if (ui->dragging) { return finish_drag(state, ui); } else { if (!INGRID(state, ui->dragx_src, ui->dragy_src) || gx != ui->dragx_src || gy != ui->dragy_src) { return ui_cancel_drag(ui); } ui_cancel_drag(ui); if (!INGRID(state, gx, gy)) return NULL; if (!(GRID(state, gx, gy) & G_ISLAND)) return NULL; sprintf(buf, "M%d,%d", gx, gy); return dupstr(buf); } } else if (button == 'h' || button == 'H') { game_state *solved = dup_game(state); solve_for_hint(solved); ret = game_state_diff(state, solved); free_game(solved); return ret; } else if (IS_CURSOR_MOVE(button)) { ui->cur_visible = true; if (control || shift) { ui->dragx_src = ui->cur_x; ui->dragy_src = ui->cur_y; ui->dragging = true; ui->drag_is_noline = !control; } if (ui->dragging) { int nx = ui->cur_x, ny = ui->cur_y; move_cursor(button, &nx, &ny, state->w, state->h, false); if (nx == ui->cur_x && ny == ui->cur_y) return NULL; update_drag_dst(state, ui, ds, COORD(nx)+TILE_SIZE/2, COORD(ny)+TILE_SIZE/2); return finish_drag(state, ui); } else { int dx = (button == CURSOR_RIGHT) ? +1 : (button == CURSOR_LEFT) ? -1 : 0; int dy = (button == CURSOR_DOWN) ? +1 : (button == CURSOR_UP) ? -1 : 0; int dorthx = 1 - abs(dx), dorthy = 1 - abs(dy); int dir, orth, nx = x, ny = y; /* 'orthorder' is a tweak to ensure that if you press RIGHT and * happen to move upwards, when you press LEFT you then tend * downwards (rather than upwards again). */ int orthorder = (button == CURSOR_LEFT || button == CURSOR_UP) ? 1 : -1; /* This attempts to find an island in the direction you're * asking for, broadly speaking. If you ask to go right, for * example, it'll look for islands to the right and slightly * above or below your current horiz. position, allowing * further above/below the further away it searches. */ assert(GRID(state, ui->cur_x, ui->cur_y) & G_ISLAND); /* currently this is depth-first (so orthogonally-adjacent * islands across the other side of the grid will be moved to * before closer islands slightly offset). Swap the order of * these two loops to change to breadth-first search. */ for (orth = 0; ; orth++) { bool oingrid = false; for (dir = 1; ; dir++) { bool dingrid = false; if (orth > dir) continue; /* only search in cone outwards. */ nx = ui->cur_x + dir*dx + orth*dorthx*orthorder; ny = ui->cur_y + dir*dy + orth*dorthy*orthorder; if (INGRID(state, nx, ny)) { dingrid = true; oingrid = true; if (GRID(state, nx, ny) & G_ISLAND) goto found; } nx = ui->cur_x + dir*dx - orth*dorthx*orthorder; ny = ui->cur_y + dir*dy - orth*dorthy*orthorder; if (INGRID(state, nx, ny)) { dingrid = true; oingrid = true; if (GRID(state, nx, ny) & G_ISLAND) goto found; } if (!dingrid) break; } if (!oingrid) return UI_UPDATE; } /* not reached */ found: ui->cur_x = nx; ui->cur_y = ny; return UI_UPDATE; } } else if (IS_CURSOR_SELECT(button)) { if (!ui->cur_visible) { ui->cur_visible = true; return UI_UPDATE; } if (ui->dragging || button == CURSOR_SELECT2) { ui_cancel_drag(ui); if (ui->dragx_dst == -1 && ui->dragy_dst == -1) { sprintf(buf, "M%d,%d", ui->cur_x, ui->cur_y); return dupstr(buf); } else return UI_UPDATE; } else { grid_type v = GRID(state, ui->cur_x, ui->cur_y); if (v & G_ISLAND) { ui->dragging = true; ui->dragx_src = ui->cur_x; ui->dragy_src = ui->cur_y; ui->dragx_dst = ui->dragy_dst = -1; ui->drag_is_noline = (button == CURSOR_SELECT2); return UI_UPDATE; } } } else if ((button >= '0' && button <= '9') || (button >= 'a' && button <= 'f') || (button >= 'A' && button <= 'F')) { /* jump to island with .count == number closest to cur_{x,y} */ int best_x = -1, best_y = -1, best_sqdist = -1, number = -1, i; if (button >= '0' && button <= '9') number = (button == '0' ? 16 : button - '0'); else if (button >= 'a' && button <= 'f') number = 10 + button - 'a'; else if (button >= 'A' && button <= 'F') number = 10 + button - 'A'; if (!ui->cur_visible) { ui->cur_visible = true; return UI_UPDATE; } for (i = 0; i < state->n_islands; ++i) { int x = state->islands[i].x, y = state->islands[i].y; int dx = x - ui->cur_x, dy = y - ui->cur_y; int sqdist = dx*dx + dy*dy; if (state->islands[i].count != number) continue; if (x == ui->cur_x && y == ui->cur_y) continue; /* new_game() reads the islands in row-major order, so by * breaking ties in favor of `first in state->islands' we * also break ties by `lexicographically smallest (y, x)'. * Thus, there's a stable pattern to how ties are broken * which the user can learn and use to navigate faster. */ if (best_sqdist == -1 || sqdist < best_sqdist) { best_x = x; best_y = y; best_sqdist = sqdist; } } if (best_x != -1 && best_y != -1) { ui->cur_x = best_x; ui->cur_y = best_y; return UI_UPDATE; } else return NULL; } else if (button == 'g' || button == 'G') { ui->show_hints = !ui->show_hints; return UI_UPDATE; } return NULL; } static game_state *execute_move(const game_state *state, const char *move) { game_state *ret = dup_game(state); int x1, y1, x2, y2, nl, n; struct island *is1, *is2; char c; debug(("execute_move: %s\n", move)); if (!*move) goto badmove; while (*move) { c = *move++; if (c == 'S') { ret->solved = true; n = 0; } else if (c == 'L') { if (sscanf(move, "%d,%d,%d,%d,%d%n", &x1, &y1, &x2, &y2, &nl, &n) != 5) goto badmove; if (!INGRID(ret, x1, y1) || !INGRID(ret, x2, y2)) goto badmove; /* Precisely one co-ordinate must differ between islands. */ if ((x1 != x2) + (y1 != y2) != 1) goto badmove; is1 = INDEX(ret, gridi, x1, y1); is2 = INDEX(ret, gridi, x2, y2); if (!is1 || !is2) goto badmove; if (nl < 0 || nl > state->maxb) goto badmove; island_join(is1, is2, nl, false); } else if (c == 'N') { if (sscanf(move, "%d,%d,%d,%d%n", &x1, &y1, &x2, &y2, &n) != 4) goto badmove; if (!INGRID(ret, x1, y1) || !INGRID(ret, x2, y2)) goto badmove; if ((x1 != x2) + (y1 != y2) != 1) goto badmove; is1 = INDEX(ret, gridi, x1, y1); is2 = INDEX(ret, gridi, x2, y2); if (!is1 || !is2) goto badmove; island_join(is1, is2, -1, false); } else if (c == 'M') { if (sscanf(move, "%d,%d%n", &x1, &y1, &n) != 2) goto badmove; if (!INGRID(ret, x1, y1)) goto badmove; is1 = INDEX(ret, gridi, x1, y1); if (!is1) goto badmove; island_togglemark(is1); } else goto badmove; move += n; if (*move == ';') move++; else if (*move) goto badmove; } map_update_possibles(ret); if (map_check(ret)) { debug(("Game completed.\n")); ret->completed = true; } return ret; badmove: debug(("%s: unrecognised move.\n", move)); free_game(ret); return NULL; } static char *solve_game(const game_state *state, const game_state *currstate, const char *aux, const char **error) { char *ret; game_state *solved; if (aux) { debug(("solve_game: aux = %s\n", aux)); solved = execute_move(state, aux); if (!solved) { *error = "Generated aux string is not a valid move (!)."; return NULL; } } else { solved = dup_game(state); /* solve with max strength... */ if (solve_from_scratch(solved, 10) == 0) { free_game(solved); *error = "Game does not have a (non-recursive) solution."; return NULL; } } ret = game_state_diff(currstate, solved); free_game(solved); debug(("solve_game: ret = %s\n", ret)); return ret; } /* ---------------------------------------------------------------------- * Drawing routines. */ static void game_compute_size(const game_params *params, int tilesize, const game_ui *ui, int *x, int *y) { /* Ick: fake up `ds->tilesize' for macro expansion purposes */ struct { int tilesize; } ads, *ds = &ads; ads.tilesize = tilesize; *x = TILE_SIZE * params->w + 2 * BORDER; *y = TILE_SIZE * params->h + 2 * BORDER; } static void game_set_size(drawing *dr, game_drawstate *ds, const game_params *params, int tilesize) { ds->tilesize = tilesize; } static float *game_colours(frontend *fe, int *ncolours) { float *ret = snewn(3 * NCOLOURS, float); int i; game_mkhighlight(fe, ret, COL_BACKGROUND, COL_HIGHLIGHT, COL_LOWLIGHT); for (i = 0; i < 3; i++) { ret[COL_FOREGROUND * 3 + i] = 0.0F; ret[COL_HINT * 3 + i] = ret[COL_LOWLIGHT * 3 + i]; ret[COL_GRID * 3 + i] = (ret[COL_HINT * 3 + i] + ret[COL_BACKGROUND * 3 + i]) * 0.5F; ret[COL_MARK * 3 + i] = ret[COL_HIGHLIGHT * 3 + i]; } ret[COL_WARNING * 3 + 0] = 1.0F; ret[COL_WARNING * 3 + 1] = 0.25F; ret[COL_WARNING * 3 + 2] = 0.25F; ret[COL_SELECTED * 3 + 0] = 0.25F; ret[COL_SELECTED * 3 + 1] = 1.00F; ret[COL_SELECTED * 3 + 2] = 0.25F; ret[COL_CURSOR * 3 + 0] = min(ret[COL_BACKGROUND * 3 + 0] * 1.4F, 1.0F); ret[COL_CURSOR * 3 + 1] = ret[COL_BACKGROUND * 3 + 1] * 0.8F; ret[COL_CURSOR * 3 + 2] = ret[COL_BACKGROUND * 3 + 2] * 0.8F; *ncolours = NCOLOURS; return ret; } static game_drawstate *game_new_drawstate(drawing *dr, const game_state *state) { struct game_drawstate *ds = snew(struct game_drawstate); int wh = state->w*state->h; int i; ds->tilesize = 0; ds->w = state->w; ds->h = state->h; ds->started = false; ds->dragging = false; ds->grid = snewn(wh, unsigned long); for (i = 0; i < wh; i++) ds->grid[i] = ~0UL; ds->newgrid = snewn(wh, unsigned long); ds->lv = snewn(wh, int); ds->lh = snewn(wh, int); memset(ds->lv, 0, wh*sizeof(int)); memset(ds->lh, 0, wh*sizeof(int)); return ds; } static void game_free_drawstate(drawing *dr, game_drawstate *ds) { sfree(ds->lv); sfree(ds->lh); sfree(ds->newgrid); sfree(ds->grid); sfree(ds); } #define LINE_WIDTH (TILE_SIZE/8) #define TS8(x) (((x)*TILE_SIZE)/8) #define OFFSET(thing) ((TILE_SIZE/2) - ((thing)/2)) static bool between_island(const game_state *state, int sx, int sy, int dx, int dy) { int x = sx - dx, y = sy - dy; while (INGRID(state, x, y)) { if (GRID(state, x, y) & G_ISLAND) goto found; x -= dx; y -= dy; } return false; found: x = sx + dx, y = sy + dy; while (INGRID(state, x, y)) { if (GRID(state, x, y) & G_ISLAND) return true; x += dx; y += dy; } return false; } static void lines_lvlh(const game_state *state, const game_ui *ui, int x, int y, grid_type v, int *lv_r, int *lh_r) { int lh = 0, lv = 0; if (v & G_LINEV) lv = INDEX(state,lines,x,y); if (v & G_LINEH) lh = INDEX(state,lines,x,y); if (ui->show_hints) { if (between_island(state, x, y, 0, 1) && !lv) lv = 1; if (between_island(state, x, y, 1, 0) && !lh) lh = 1; } /*debug(("lvlh: (%d,%d) v 0x%x lv %d lh %d.\n", x, y, v, lv, lh));*/ *lv_r = lv; *lh_r = lh; } static void draw_cross(drawing *dr, game_drawstate *ds, int ox, int oy, int col) { int off = TS8(2); draw_line(dr, ox, oy, ox+off, oy+off, col); draw_line(dr, ox+off, oy, ox, oy+off, col); } static void draw_general_line(drawing *dr, game_drawstate *ds, int ox, int oy, int fx, int fy, int ax, int ay, int len, unsigned long ldata, int which) { /* * Draw one direction of lines in a square. To permit the same * code to handle horizontal and vertical lines, fx,fy are the * 'forward' direction (along the lines) and ax,ay are the * 'across' direction. * * We draw the white background for a locked bridge if (which & * 1), and draw the bridges themselves if (which & 2). This * permits us to get two overlapping locked bridges right without * one of them erasing part of the other. */ int fg; fg = ((ldata & DL_COUNTMASK) == DL_COUNT_HINT ? COL_HINT : (ldata & DL_COLMASK) == DL_COL_SELECTED ? COL_SELECTED : (ldata & DL_COLMASK) == DL_COL_FLASH ? COL_HIGHLIGHT : (ldata & DL_COLMASK) == DL_COL_WARNING ? COL_WARNING : COL_FOREGROUND); if ((ldata & DL_COUNTMASK) == DL_COUNT_CROSS) { draw_cross(dr, ds, ox + TS8(1)*fx + TS8(3)*ax, oy + TS8(1)*fy + TS8(3)*ay, fg); draw_cross(dr, ds, ox + TS8(5)*fx + TS8(3)*ax, oy + TS8(5)*fy + TS8(3)*ay, fg); } else if ((ldata & DL_COUNTMASK) != 0) { int lh, lw, gw, bw, i, loff; lh = (ldata & DL_COUNTMASK); if (lh == DL_COUNT_HINT) lh = 1; lw = gw = LINE_WIDTH; while ((bw = lw * lh + gw * (lh+1)) > TILE_SIZE) gw--; loff = OFFSET(bw); if (which & 1) { if ((ldata & DL_LOCK) && fg != COL_HINT) draw_rect(dr, ox + loff*ax, oy + loff*ay, len*fx+bw*ax, len*fy+bw*ay, COL_MARK); } if (which & 2) { for (i = 0; i < lh; i++, loff += lw + gw) draw_rect(dr, ox + (loff+gw)*ax, oy + (loff+gw)*ay, len*fx+lw*ax, len*fy+lw*ay, fg); } } } static void draw_hline(drawing *dr, game_drawstate *ds, int ox, int oy, int w, unsigned long vdata, int which) { draw_general_line(dr, ds, ox, oy, 1, 0, 0, 1, w, vdata, which); } static void draw_vline(drawing *dr, game_drawstate *ds, int ox, int oy, int h, unsigned long vdata, int which) { draw_general_line(dr, ds, ox, oy, 0, 1, 1, 0, h, vdata, which); } #define ISLAND_RADIUS ((TILE_SIZE*12)/20) #define ISLAND_NUMSIZE(clue) \ (((clue) < 10) ? (TILE_SIZE*7)/10 : (TILE_SIZE*5)/10) static void draw_island(drawing *dr, game_drawstate *ds, int ox, int oy, int clue, unsigned long idata) { int half, orad, irad, fg, bg; if ((idata & DI_BGMASK) == DI_BG_NO_ISLAND) return; half = TILE_SIZE/2; orad = ISLAND_RADIUS; irad = orad - LINE_WIDTH; fg = ((idata & DI_COLMASK) == DI_COL_SELECTED ? COL_SELECTED : (idata & DI_COLMASK) == DI_COL_WARNING ? COL_WARNING : (idata & DI_COLMASK) == DI_COL_FLASH ? COL_HIGHLIGHT : COL_FOREGROUND); bg = ((idata & DI_BGMASK) == DI_BG_CURSOR ? COL_CURSOR : (idata & DI_BGMASK) == DI_BG_MARK ? COL_MARK : COL_BACKGROUND); /* draw a thick circle */ draw_circle(dr, ox+half, oy+half, orad, fg, fg); draw_circle(dr, ox+half, oy+half, irad, bg, bg); if (clue > 0) { char str[32]; int textcolour = (fg == COL_SELECTED ? COL_FOREGROUND : fg); sprintf(str, "%d", clue); draw_text(dr, ox+half, oy+half, FONT_VARIABLE, ISLAND_NUMSIZE(clue), ALIGN_VCENTRE | ALIGN_HCENTRE, textcolour, str); } } static void draw_island_tile(drawing *dr, game_drawstate *ds, int x, int y, int clue, unsigned long data) { int ox = COORD(x), oy = COORD(y); int which; clip(dr, ox, oy, TILE_SIZE, TILE_SIZE); draw_rect(dr, ox, oy, TILE_SIZE, TILE_SIZE, COL_BACKGROUND); /* * Because of the possibility of incoming bridges just about * meeting at one corner, we must split the line-drawing into * background and foreground segments. */ for (which = 1; which <= 2; which <<= 1) { draw_hline(dr, ds, ox, oy, TILE_SIZE/2, (data >> D_I_LINE_SHIFT_L) & DL_MASK, which); draw_hline(dr, ds, ox + TILE_SIZE - TILE_SIZE/2, oy, TILE_SIZE/2, (data >> D_I_LINE_SHIFT_R) & DL_MASK, which); draw_vline(dr, ds, ox, oy, TILE_SIZE/2, (data >> D_I_LINE_SHIFT_U) & DL_MASK, which); draw_vline(dr, ds, ox, oy + TILE_SIZE - TILE_SIZE/2, TILE_SIZE/2, (data >> D_I_LINE_SHIFT_D) & DL_MASK, which); } draw_island(dr, ds, ox, oy, clue, (data >> D_I_ISLAND_SHIFT) & DI_MASK); unclip(dr); draw_update(dr, ox, oy, TILE_SIZE, TILE_SIZE); } static void draw_line_tile(drawing *dr, game_drawstate *ds, int x, int y, unsigned long data) { int ox = COORD(x), oy = COORD(y); unsigned long hdata, vdata; clip(dr, ox, oy, TILE_SIZE, TILE_SIZE); draw_rect(dr, ox, oy, TILE_SIZE, TILE_SIZE, COL_BACKGROUND); /* * We have to think about which of the horizontal and vertical * line to draw first, if both exist. * * The rule is that hint lines are drawn at the bottom, then * NOLINE crosses, then actual bridges. The enumeration in the * DL_COUNTMASK field is set up so that this drops out of a * straight comparison between the two. * * Since lines crossing in this type of square cannot both be * actual bridges, there's no need to pass a nontrivial 'which' * parameter to draw_[hv]line. */ hdata = (data >> D_L_LINE_SHIFT_H) & DL_MASK; vdata = (data >> D_L_LINE_SHIFT_V) & DL_MASK; if ((hdata & DL_COUNTMASK) > (vdata & DL_COUNTMASK)) { draw_hline(dr, ds, ox, oy, TILE_SIZE, hdata, 3); draw_vline(dr, ds, ox, oy, TILE_SIZE, vdata, 3); } else { draw_vline(dr, ds, ox, oy, TILE_SIZE, vdata, 3); draw_hline(dr, ds, ox, oy, TILE_SIZE, hdata, 3); } /* * The islands drawn at the edges of a line tile don't need clue * numbers. */ draw_island(dr, ds, ox - TILE_SIZE, oy, -1, (data >> D_L_ISLAND_SHIFT_L) & DI_MASK); draw_island(dr, ds, ox + TILE_SIZE, oy, -1, (data >> D_L_ISLAND_SHIFT_R) & DI_MASK); draw_island(dr, ds, ox, oy - TILE_SIZE, -1, (data >> D_L_ISLAND_SHIFT_U) & DI_MASK); draw_island(dr, ds, ox, oy + TILE_SIZE, -1, (data >> D_L_ISLAND_SHIFT_D) & DI_MASK); unclip(dr); draw_update(dr, ox, oy, TILE_SIZE, TILE_SIZE); } static void draw_edge_tile(drawing *dr, game_drawstate *ds, int x, int y, int dx, int dy, unsigned long data) { int ox = COORD(x), oy = COORD(y); int cx = ox, cy = oy, cw = TILE_SIZE, ch = TILE_SIZE; if (dy) { if (dy > 0) cy += TILE_SIZE/2; ch -= TILE_SIZE/2; } else { if (dx > 0) cx += TILE_SIZE/2; cw -= TILE_SIZE/2; } clip(dr, cx, cy, cw, ch); draw_rect(dr, cx, cy, cw, ch, COL_BACKGROUND); draw_island(dr, ds, ox + TILE_SIZE*dx, oy + TILE_SIZE*dy, -1, (data >> D_I_ISLAND_SHIFT) & DI_MASK); unclip(dr); draw_update(dr, cx, cy, cw, ch); } static void game_redraw(drawing *dr, game_drawstate *ds, const game_state *oldstate, const game_state *state, int dir, const game_ui *ui, float animtime, float flashtime) { int x, y, lv, lh; grid_type v; bool flash = false; struct island *is, *is_drag_src = NULL, *is_drag_dst = NULL; if (flashtime) { int f = (int)(flashtime * 5 / FLASH_TIME); if (f == 1 || f == 3) flash = true; } /* Clear screen, if required. */ if (!ds->started) { #ifdef DRAW_GRID draw_rect_outline(dr, COORD(0)-1, COORD(0)-1, TILE_SIZE * ds->w + 2, TILE_SIZE * ds->h + 2, COL_GRID); #endif draw_update(dr, 0, 0, TILE_SIZE * ds->w + 2 * BORDER, TILE_SIZE * ds->h + 2 * BORDER); ds->started = true; } if (ui->dragx_src != -1 && ui->dragy_src != -1) { ds->dragging = true; is_drag_src = INDEX(state, gridi, ui->dragx_src, ui->dragy_src); assert(is_drag_src); if (ui->dragx_dst != -1 && ui->dragy_dst != -1) { is_drag_dst = INDEX(state, gridi, ui->dragx_dst, ui->dragy_dst); assert(is_drag_dst); } } else ds->dragging = false; /* * Set up ds->newgrid with the current grid contents. */ for (x = 0; x < ds->w; x++) for (y = 0; y < ds->h; y++) INDEX(ds,newgrid,x,y) = 0; for (x = 0; x < ds->w; x++) { for (y = 0; y < ds->h; y++) { v = GRID(state, x, y); if (v & G_ISLAND) { /* * An island square. Compute the drawing data for the * island, and put it in this square and surrounding * squares. */ unsigned long idata = 0; is = INDEX(state, gridi, x, y); if (flash) idata |= DI_COL_FLASH; if (is_drag_src && (is == is_drag_src || (is_drag_dst && is == is_drag_dst))) idata |= DI_COL_SELECTED; else if (island_impossible(is, v & G_MARK) || (v & G_WARN)) idata |= DI_COL_WARNING; else idata |= DI_COL_NORMAL; if (ui->cur_visible && ui->cur_x == is->x && ui->cur_y == is->y) idata |= DI_BG_CURSOR; else if (v & G_MARK) idata |= DI_BG_MARK; else idata |= DI_BG_NORMAL; INDEX(ds,newgrid,x,y) |= idata << D_I_ISLAND_SHIFT; if (x > 0 && !(GRID(state,x-1,y) & G_ISLAND)) INDEX(ds,newgrid,x-1,y) |= idata << D_L_ISLAND_SHIFT_R; if (x+1 < state->w && !(GRID(state,x+1,y) & G_ISLAND)) INDEX(ds,newgrid,x+1,y) |= idata << D_L_ISLAND_SHIFT_L; if (y > 0 && !(GRID(state,x,y-1) & G_ISLAND)) INDEX(ds,newgrid,x,y-1) |= idata << D_L_ISLAND_SHIFT_D; if (y+1 < state->h && !(GRID(state,x,y+1) & G_ISLAND)) INDEX(ds,newgrid,x,y+1) |= idata << D_L_ISLAND_SHIFT_U; } else { unsigned long hdata, vdata; bool selh = false, selv = false; /* * A line (non-island) square. Compute the drawing * data for any horizontal and vertical lines in the * square, and put them in this square's entry and * optionally those for neighbouring islands too. */ if (is_drag_dst && WITHIN(x,is_drag_src->x, is_drag_dst->x) && WITHIN(y,is_drag_src->y, is_drag_dst->y)) { if (is_drag_src->x != is_drag_dst->x) selh = true; else selv = true; } lines_lvlh(state, ui, x, y, v, &lv, &lh); hdata = (v & G_NOLINEH ? DL_COUNT_CROSS : v & G_LINEH ? lh : (ui->show_hints && between_island(state,x,y,1,0)) ? DL_COUNT_HINT : 0); vdata = (v & G_NOLINEV ? DL_COUNT_CROSS : v & G_LINEV ? lv : (ui->show_hints && between_island(state,x,y,0,1)) ? DL_COUNT_HINT : 0); hdata |= (flash ? DL_COL_FLASH : v & G_WARN ? DL_COL_WARNING : selh ? DL_COL_SELECTED : DL_COL_NORMAL); vdata |= (flash ? DL_COL_FLASH : v & G_WARN ? DL_COL_WARNING : selv ? DL_COL_SELECTED : DL_COL_NORMAL); if (v & G_MARKH) hdata |= DL_LOCK; if (v & G_MARKV) vdata |= DL_LOCK; INDEX(ds,newgrid,x,y) |= hdata << D_L_LINE_SHIFT_H; INDEX(ds,newgrid,x,y) |= vdata << D_L_LINE_SHIFT_V; if (x > 0 && (GRID(state,x-1,y) & G_ISLAND)) INDEX(ds,newgrid,x-1,y) |= hdata << D_I_LINE_SHIFT_R; if (x+1 < state->w && (GRID(state,x+1,y) & G_ISLAND)) INDEX(ds,newgrid,x+1,y) |= hdata << D_I_LINE_SHIFT_L; if (y > 0 && (GRID(state,x,y-1) & G_ISLAND)) INDEX(ds,newgrid,x,y-1) |= vdata << D_I_LINE_SHIFT_D; if (y+1 < state->h && (GRID(state,x,y+1) & G_ISLAND)) INDEX(ds,newgrid,x,y+1) |= vdata << D_I_LINE_SHIFT_U; } } } /* * Now go through and draw any changed grid square. */ for (x = 0; x < ds->w; x++) { for (y = 0; y < ds->h; y++) { unsigned long newval = INDEX(ds,newgrid,x,y); if (INDEX(ds,grid,x,y) != newval) { v = GRID(state, x, y); if (v & G_ISLAND) { is = INDEX(state, gridi, x, y); draw_island_tile(dr, ds, x, y, is->count, newval); /* * If this tile is right at the edge of the grid, * we must also draw the part of the island that * goes completely out of bounds. We don't bother * keeping separate entries in ds->newgrid for * these tiles; it's easier just to redraw them * iff we redraw their parent island tile. */ if (x == 0) draw_edge_tile(dr, ds, x-1, y, +1, 0, newval); if (y == 0) draw_edge_tile(dr, ds, x, y-1, 0, +1, newval); if (x == state->w-1) draw_edge_tile(dr, ds, x+1, y, -1, 0, newval); if (y == state->h-1) draw_edge_tile(dr, ds, x, y+1, 0, -1, newval); } else { draw_line_tile(dr, ds, x, y, newval); } INDEX(ds,grid,x,y) = newval; } } } } static float game_anim_length(const game_state *oldstate, const game_state *newstate, int dir, game_ui *ui) { return 0.0F; } static float game_flash_length(const game_state *oldstate, const game_state *newstate, int dir, game_ui *ui) { if (!oldstate->completed && newstate->completed && !oldstate->solved && !newstate->solved) return FLASH_TIME; return 0.0F; } static int game_status(const game_state *state) { return state->completed ? +1 : 0; } static void game_print_size(const game_params *params, const game_ui *ui, float *x, float *y) { int pw, ph; /* 10mm squares by default. */ game_compute_size(params, 1000, ui, &pw, &ph); *x = pw / 100.0F; *y = ph / 100.0F; } static void game_print(drawing *dr, const game_state *state, const game_ui *ui, int ts) { int ink = print_mono_colour(dr, 0); int paper = print_mono_colour(dr, 1); int x, y, cx, cy, i, nl; int loff; grid_type grid; /* Ick: fake up `ds->tilesize' for macro expansion purposes */ game_drawstate ads, *ds = &ads; ads.tilesize = ts; /* I don't think this wants a border. */ /* Bridges */ loff = ts / (8 * sqrt((state->params.maxb - 1))); print_line_width(dr, ts / 12); for (x = 0; x < state->w; x++) { for (y = 0; y < state->h; y++) { cx = COORD(x); cy = COORD(y); grid = GRID(state,x,y); nl = INDEX(state,lines,x,y); if (grid & G_ISLAND) continue; if (grid & G_LINEV) { for (i = 0; i < nl; i++) draw_line(dr, cx+ts/2+(2*i-nl+1)*loff, cy, cx+ts/2+(2*i-nl+1)*loff, cy+ts, ink); } if (grid & G_LINEH) { for (i = 0; i < nl; i++) draw_line(dr, cx, cy+ts/2+(2*i-nl+1)*loff, cx+ts, cy+ts/2+(2*i-nl+1)*loff, ink); } } } /* Islands */ for (i = 0; i < state->n_islands; i++) { char str[32]; struct island *is = &state->islands[i]; grid = GRID(state, is->x, is->y); cx = COORD(is->x) + ts/2; cy = COORD(is->y) + ts/2; draw_circle(dr, cx, cy, ISLAND_RADIUS, paper, ink); sprintf(str, "%d", is->count); draw_text(dr, cx, cy, FONT_VARIABLE, ISLAND_NUMSIZE(is->count), ALIGN_VCENTRE | ALIGN_HCENTRE, ink, str); } } #ifdef COMBINED #define thegame bridges #endif const struct game thegame = { "Bridges", "games.bridges", "bridges", default_params, game_fetch_preset, NULL, decode_params, encode_params, free_params, dup_params, true, game_configure, custom_params, validate_params, new_game_desc, validate_desc, new_game, dup_game, free_game, true, solve_game, true, game_can_format_as_text_now, game_text_format, NULL, NULL, /* get_prefs, set_prefs */ new_ui, free_ui, NULL, /* encode_ui */ NULL, /* decode_ui */ NULL, /* game_request_keys */ game_changed_state, current_key_label, interpret_move, execute_move, PREFERRED_TILE_SIZE, game_compute_size, game_set_size, game_colours, game_new_drawstate, game_free_drawstate, game_redraw, game_anim_length, game_flash_length, game_get_cursor_location, game_status, true, false, game_print_size, game_print, false, /* wants_statusbar */ false, NULL, /* timing_state */ REQUIRE_RBUTTON, /* flags */ }; /* vim: set shiftwidth=4 tabstop=8: */