*
* Things still to do:
*
- * * write a recursive solver?
+ * - 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 "puzzles.h"
/* Turn this on for hints about which lines are considered possibilities. */
-#undef DRAW_HINTS
#undef DRAW_GRID
-#undef DRAW_DSF
/* --- structures for params, state, etc. --- */
COL_SELECTED, COL_MARK,
COL_HINT, COL_GRID,
COL_WARNING,
+ COL_CURSOR,
NCOLOURS
};
#define G_NOLINEH 0x0040
#define G_NOLINE (G_NOLINEV|G_NOLINEH)
-/* flags used by the drawstate */
-#define G_ISSEL 0x0080
-#define G_REDRAW 0x0100
-#define G_FLASH 0x0200
-#define G_WARN 0x0400
+/* flags used by the error checker */
+#define G_WARN 0x0080
/* flags used by the solver etc. */
-#define G_SWEEP 0x0800
+#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 {
- int *dsf, *tmpdsf;
+ int *dsf, *comptspaces;
+ int *tmpdsf, *tmpcompspaces;
int refcount;
};
struct game_state {
int w, h, completed, solved, allowloops, maxb;
- grid_type *grid, *scratch;
+ grid_type *grid;
struct island *islands;
int n_islands, n_islands_alloc;
game_params params; /* used by the aux solver. */
#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 SCRATCH(s,x,y) INDEX(s,scratch,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)))
}
}
-static char *game_text_format(game_state *state)
+static int 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;
{
int curr = island_countbridges(is), nspc = is->count - curr, nsurrspc;
int i, poss;
- grid_type v;
struct island *is_orth;
if (nspc < 0) {
int ifree, dx = is->adj.points[i].dx;
if (!is->adj.points[i].off) continue;
- v = GRID(is->state, is->adj.points[i].x, is->adj.points[i].y);
poss = POSSIBLES(is->state, dx,
is->adj.points[i].x, is->adj.points[i].y);
if (poss == 0) continue;
assert(is_orth);
ifree = is_orth->count - island_countbridges(is_orth);
- if (ifree > 0)
- nsurrspc += min(ifree, MAXIMUM(is->state, dx,
- is->adj.points[i].x, is->adj.points[i].y));
+ 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",
sfree(params);
}
-static game_params *dup_params(game_params *params)
+static game_params *dup_params(const game_params *params)
{
game_params *ret = snew(game_params);
*ret = *params; /* structure copy */
}
}
-static char *encode_params(game_params *params, int full)
+static char *encode_params(const game_params *params, int full)
{
char buf[80];
return dupstr(buf);
}
-static config_item *game_configure(game_params *params)
+static config_item *game_configure(const game_params *params)
{
config_item *ret;
char buf[80];
return ret;
}
-static game_params *custom_params(config_item *cfg)
+static game_params *custom_params(const config_item *cfg)
{
game_params *ret = snew(game_params);
return ret;
}
-static char *validate_params(game_params *params, int full)
+static char *validate_params(const game_params *params, int full)
{
if (params->w < 3 || params->h < 3)
return "Width and height must be at least 3";
return ret;
}
-static char *game_state_diff(game_state *src, game_state *dest)
+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];
idx = x;
s = e = -1;
bl = 0;
+ 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) break;
+ 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);
- maxb = IDX(state, maxv, idx);
- np = min(maxb, min(is_s->count, is_f->count));
+ np = min(maxb, is_f->count);
if (s != -1) {
for (i = s; i <= e; i++) {
s = y+1;
bl = 0;
is_s = is_f;
+ maxb = is_s->count;
} else {
e = y;
if (IDX(state,grid,idx) & (G_LINEH|G_NOLINEV)) bl = 1;
idx = y*w;
s = e = -1;
bl = 0;
+ maxb = state->params.maxb; /* placate optimiser */
for (x = 0; x < state->w; x++) {
is_s = IDX(state, gridi, idx);
- if (is_s) break;
+ 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);
- maxb = IDX(state, maxh, idx);
- np = min(maxb, min(is_s->count, is_f->count));
+ np = min(maxb, is_f->count);
if (s != -1) {
for (i = s; i <= e; i++) {
s = x+1;
bl = 0;
is_s = is_f;
+ maxb = is_s->count;
} else {
e = x;
if (IDX(state,grid,idx) & (G_LINEV|G_NOLINEH)) bl = 1;
}
}
-static int grid_degree(game_state *state, int x, int y, int *nx_r, int *ny_r)
+struct bridges_neighbour_ctx {
+ game_state *state;
+ int i, n, neighbours[4];
+};
+static int bridges_neighbour(int vertex, void *vctx)
{
- grid_type grid = SCRATCH(state, x, y), gline = grid & G_LINE;
- struct island *is;
- int x1, y1, x2, y2, c = 0, i, nx, ny;
-
- nx = ny = -1; /* placate optimiser */
- 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 (SCRATCH(state,
- is->adj.points[i].x,
- is->adj.points[i].y) & gline) {
- nx = is->adj.points[i].x;
- ny = is->adj.points[i].y;
- c++;
+ 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;
}
- } 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 (SCRATCH(state, x1, y1) & (gline | G_ISLAND)) {
- nx = x1; ny = y1; c++;
- }
- if (SCRATCH(state, x2, y2) & (gline | G_ISLAND)) {
- nx = x2; ny = y2; c++;
- }
- }
- if (c == 1) {
- assert(nx != -1 && ny != -1); /* paranoia */
- *nx_r = nx; *ny_r = ny;
}
- return c;
+
+ if (ctx->i < ctx->n)
+ return ctx->neighbours[ctx->i++];
+ else
+ return -1;
}
static int map_hasloops(game_state *state, int mark)
{
- int x, y, ox, oy, nx = 0, ny = 0, loop = 0;
-
- memcpy(state->scratch, state->grid, GRIDSZ(state));
+ int x, y;
+ struct findloopstate *fls;
+ struct bridges_neighbour_ctx ctx;
+ int ret;
- /* This algorithm is actually broken; if there are two loops connected
- * by bridges this will also highlight bridges. The correct algorithm
- * uses a dsf and a two-pass edge-detection algorithm (see check_correct
- * in slant.c); this is BALGE for now, especially since disallow-loops
- * is not the default for this puzzle. If we want to fix this later then
- * copy the alg in slant.c to the empty statement in map_group. */
+ fls = findloop_new_state(state->w * state->h);
+ ctx.state = state;
+ ret = findloop_run(fls, state->w * state->h, bridges_neighbour, &ctx);
- /* Remove all 1-degree edges. */
- for (y = 0; y < state->h; y++) {
- for (x = 0; x < state->w; x++) {
- ox = x; oy = y;
- while (grid_degree(state, ox, oy, &nx, &ny) == 1) {
- /*debug(("hasloops: removing 1-degree at (%d,%d).\n", ox, oy));*/
- SCRATCH(state, ox, oy) &= ~(G_LINE|G_ISLAND);
- ox = nx; oy = ny;
- }
- }
- }
- /* Mark any remaining edges as G_WARN, if required. */
- for (x = 0; x < state->w; x++) {
+ if (mark) {
for (y = 0; y < state->h; y++) {
- if (GRID(state,x,y) & G_ISLAND) continue;
-
- if (SCRATCH(state, x, y) & G_LINE) {
- if (mark) {
- /*debug(("hasloops: marking loop square at (%d,%d).\n",
- x, y));*/
- GRID(state,x,y) |= G_WARN;
- loop = 1;
- } else
- return 1; /* short-cut as soon as we find one */
- } else {
- if (mark)
- GRID(state,x,y) &= ~G_WARN;
+ 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;
}
}
}
- return loop;
+
+ findloop_free_state(fls);
+ return ret;
}
static void map_group(game_state *state)
struct island *is, *is_join;
/* Initialise dsf. */
- for (i = 0; i < wh; i++)
- dsf[i] = i;
+ dsf_init(dsf, wh);
/* For each island, find connected islands right or down
* and merge the dsf for the island squares as well as the
return 1;
}
-static int solve_island_subgroup(struct island *is, int direction, int n)
+static int solve_island_subgroup(struct island *is, int direction)
{
struct island *is_join;
int nislands, *dsf = is->state->solver->dsf;
debug(("..checking subgroups.\n"));
/* if is isn't full, return 0. */
- if (n < is->count) {
+ if (island_countbridges(is) < is->count) {
debug(("...orig island (%d,%d) not full.\n", is->x, is->y));
return 0;
}
- is_join = INDEX(state, gridi,
- ISLAND_ORTHX(is, direction),
- ISLAND_ORTHY(is, direction));
- assert(is_join);
+ 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 0;
+ /* 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 0;
+ }
}
/* Check group membership for is->dsf; if it's full return 1. */
/* 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, n));
+ is->x, is->y));
return 1;
} else {
debug(("...has finished puzzle.\n"));
if (missing <= 0) return 1;
for (i = 0; i < is->adj.npoints; i++) {
- /* We only do right- or down-pointing bridges. */
- if (is->adj.points[i].dx == -1 ||
- is->adj.points[i].dy == -1) continue;
-
x = is->adj.points[i].x;
y = is->adj.points[i].y;
spc = island_adjspace(is, 1, missing, i);
solve_join(is, i, n, 0);
map_update_possibles(is->state);
- if (solve_island_subgroup(is, i, n) ||
+ 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",
if (maxb == 0) {
debug(("...adding NOLINE.\n"));
solve_join(is, i, -1, 0); /* we can't have any bridges here. */
- didsth = 1;
} else {
debug(("...setting maximum\n"));
solve_join(is, i, maxb, 1);
}
+ didsth = 1;
}
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.
+ */
+ int got = 0;
+ int before[4];
+ int j;
+
+ spc = island_adjspace(is, 1, 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 */
+
+ memcpy(ss->tmpdsf, ss->dsf, wh*sizeof(int));
+
+ for (j = 0; j < is->adj.npoints; j++) {
+ spc = island_adjspace(is, 1, missing, j);
+ if (spc == 0) continue;
+ if (j == i) continue;
+ solve_join(is, j, before[j] + spc, 0);
+ }
+ map_update_possibles(is->state);
+
+ if (solve_island_subgroup(is, -1))
+ got = 1;
+
+ for (j = 0; j < is->adj.npoints; j++)
+ solve_join(is, j, before[j], 0);
+ memcpy(ss->dsf, ss->tmpdsf, wh*sizeof(int));
+
+ 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, 0);
+ didsth = 1;
+ }
+
+ map_update_possibles(is->state);
+ }
+
if (didsth) *didsth_r = didsth;
return 1;
}
/* --- New game functions --- */
-static game_state *new_state(game_params *params)
+static game_state *new_state(const game_params *params)
{
game_state *ret = snew(game_state);
int wh = params->w * params->h, i;
ret->grid = snewn(wh, grid_type);
memset(ret->grid, 0, GRIDSZ(ret));
- ret->scratch = snewn(wh, grid_type);
- memset(ret->scratch, 0, GRIDSZ(ret));
ret->wha = snewn(wh*N_WH_ARRAYS, char);
memset(ret->wha, 0, wh*N_WH_ARRAYS*sizeof(char));
ret->solved = ret->completed = 0;
ret->solver = snew(struct solver_state);
- ret->solver->dsf = snewn(wh, int);
+ ret->solver->dsf = snew_dsf(wh);
ret->solver->tmpdsf = snewn(wh, int);
- for (i = 0; i < wh; i++) ret->solver->dsf[i] = i;
ret->solver->refcount = 1;
return ret;
}
-static game_state *dup_game(game_state *state)
+static game_state *dup_game(const game_state *state)
{
game_state *ret = snew(game_state);
int wh = state->w*state->h;
ret->grid = snewn(wh, grid_type);
memcpy(ret->grid, state->grid, GRIDSZ(ret));
- ret->scratch = snewn(wh, grid_type);
- memcpy(ret->scratch, state->scratch, GRIDSZ(ret));
ret->wha = snewn(wh*N_WH_ARRAYS, char);
memcpy(ret->wha, state->wha, wh*N_WH_ARRAYS*sizeof(char));
sfree(state->wha);
- sfree(state->scratch);
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(game_params *params, random_state *rs,
+static char *new_game_desc(const game_params *params, random_state *rs,
char **aux, int 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, 2), ni_curr, ni_bad;
+ int ni_req = max((params->islands * wh) / 100, MIN_SENSIBLE_ISLANDS), ni_curr, ni_bad;
struct island *is, *is2;
char *ret;
unsigned int echeck;
map_find_orthogonal(tobuild);
if (params->difficulty > 0) {
- if (solve_from_scratch(tobuild, params->difficulty-1) > 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;
return ret;
}
-static char *validate_desc(game_params *params, char *desc)
+static char *validate_desc(const game_params *params, const char *desc)
{
int i, wh = params->w * params->h;
else if (!*desc)
return "Game description shorter than expected";
else
- return "Game description containers unexpected character";
+ return "Game description contains unexpected character";
desc++;
}
if (*desc || i > wh)
return NULL;
}
-static game_state *new_game_sub(game_params *params, char *desc)
+static game_state *new_game_sub(const game_params *params, const char *desc)
{
game_state *state = new_state(params);
int x, y, run = 0;
return state;
}
-static game_state *new_game(midend *me, game_params *params, char *desc)
+static game_state *new_game(midend *me, const game_params *params,
+ const char *desc)
{
return new_game_sub(params, desc);
}
int dragx_dst, dragy_dst; /* src's closest orth island. */
grid_type todraw;
int dragging, drag_is_noline, nlines;
+
+ int cur_x, cur_y, cur_visible; /* cursor position */
+ int show_hints;
};
static char *ui_cancel_drag(game_ui *ui)
return "";
}
-static game_ui *new_ui(game_state *state)
+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 = 0;
+ ui->show_hints = 0;
return ui;
}
sfree(ui);
}
-static char *encode_ui(game_ui *ui)
+static char *encode_ui(const game_ui *ui)
{
return NULL;
}
-static void decode_ui(game_ui *ui, char *encoding)
+static void decode_ui(game_ui *ui, const char *encoding)
{
}
-static void game_changed_state(game_ui *ui, game_state *oldstate,
- game_state *newstate)
+static void game_changed_state(game_ui *ui, const game_state *oldstate,
+ const game_state *newstate)
{
}
struct game_drawstate {
int tilesize;
int w, h;
- grid_type *grid;
+ unsigned long *grid, *newgrid;
int *lv, *lh;
int started, dragging;
};
-static char *update_drag_dst(game_state *state, game_ui *ui, game_drawstate *ds,
- int nx, int ny)
+/*
+ * 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;
return "";
}
-static char *finish_drag(game_state *state, game_ui *ui)
+static char *finish_drag(const game_state *state, game_ui *ui)
{
char buf[80];
return dupstr(buf);
}
-static char *interpret_move(game_state *state, game_ui *ui, game_drawstate *ds,
- int x, int y, int button)
+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;
+ int 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;
- if ((ggrid & G_ISLAND) && !(ggrid & G_MARK)) {
+ ui->cur_visible = 0;
+ if (ggrid & G_ISLAND) {
ui->dragx_src = gx;
ui->dragy_src = gy;
return "";
} else
return ui_cancel_drag(ui);
} else if (button == LEFT_DRAG || button == RIGHT_DRAG) {
- if (gx != ui->dragx_src || gy != ui->dragy_src) {
+ 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 = 1;
ui->drag_is_noline = (button == RIGHT_DRAG) ? 1 : 0;
return update_drag_dst(state, ui, ds, x, y);
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;
ret = game_state_diff(state, solved);
free_game(solved);
return ret;
+ } else if (IS_CURSOR_MOVE(button)) {
+ ui->cur_visible = 1;
+ 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, 0);
+ 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++) {
+ int oingrid = 0;
+ for (dir = 1; ; dir++) {
+ int dingrid = 0;
+
+ 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 = oingrid = 1;
+ 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 = oingrid = 1;
+ if (GRID(state, nx, ny) & G_ISLAND) goto found;
+ }
+
+ if (!dingrid) break;
+ }
+ if (!oingrid) return "";
+ }
+ /* not reached */
+
+found:
+ ui->cur_x = nx;
+ ui->cur_y = ny;
+ return "";
+ }
+ } else if (IS_CURSOR_SELECT(button)) {
+ if (!ui->cur_visible) {
+ ui->cur_visible = 1;
+ return "";
+ }
+ 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 "";
+ } else {
+ grid_type v = GRID(state, ui->cur_x, ui->cur_y);
+ if (v & G_ISLAND) {
+ ui->dragging = 1;
+ 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) ? 1 : 0;
+ return "";
+ }
+ }
+ } 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 = 1;
+ return "";
+ }
+
+ 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 "";
+ } else
+ return NULL;
+ } else if (button == 'g' || button == 'G') {
+ ui->show_hints = 1 - ui->show_hints;
+ return "";
}
return NULL;
}
-static game_state *execute_move(game_state *state, char *move)
+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;
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;
is1 = INDEX(ret, gridi, x1, y1);
is2 = INDEX(ret, gridi, x2, y2);
if (!is1 || !is2) goto badmove;
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;
is1 = INDEX(ret, gridi, x1, y1);
is2 = INDEX(ret, gridi, x2, y2);
if (!is1 || !is2) goto badmove;
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);
return NULL;
}
-static char *solve_game(game_state *state, game_state *currstate,
- char *aux, char **error)
+static char *solve_game(const game_state *state, const game_state *currstate,
+ const char *aux, char **error)
{
char *ret;
game_state *solved;
* Drawing routines.
*/
-static void game_compute_size(game_params *params, int tilesize,
- int *x, int *y)
+static void game_compute_size(const game_params *params, int tilesize,
+ int *x, int *y)
{
/* Ick: fake up `ds->tilesize' for macro expansion purposes */
struct { int tilesize; } ads, *ds = &ads;
}
static void game_set_size(drawing *dr, game_drawstate *ds,
- game_params *params, int tilesize)
+ const game_params *params, int tilesize)
{
ds->tilesize = tilesize;
}
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, game_state *state)
+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 = 0;
- ds->grid = snewn(wh, grid_type);
- memset(ds->grid, -1, wh*sizeof(grid_type));
+ ds->dragging = 0;
+ 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));
{
sfree(ds->lv);
sfree(ds->lh);
+ sfree(ds->newgrid);
sfree(ds->grid);
sfree(ds);
}
#define OFFSET(thing) ((TILE_SIZE/2) - ((thing)/2))
-static void lines_vert(drawing *dr, game_drawstate *ds,
- int ox, int oy, int lv, int col, grid_type v)
+static int between_island(const game_state *state, int sx, int sy,
+ int dx, int dy)
{
- int lw = LINE_WIDTH, gw = LINE_WIDTH, bw, i, loff;
- while ((bw = lw * lv + gw * (lv+1)) > TILE_SIZE)
- gw--;
- loff = OFFSET(bw);
- if (v & G_MARKV)
- draw_rect(dr, ox + loff, oy, bw, TILE_SIZE, COL_MARK);
- for (i = 0; i < lv; i++, loff += lw + gw)
- draw_rect(dr, ox + loff + gw, oy, lw, TILE_SIZE, col);
+ 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 0;
+found:
+ x = sx + dx, y = sy + dy;
+ while (INGRID(state, x, y)) {
+ if (GRID(state, x, y) & G_ISLAND) return 1;
+ x += dx; y += dy;
+ }
+ return 0;
}
-static void lines_horiz(drawing *dr, game_drawstate *ds,
- int ox, int oy, int lh, int col, grid_type v)
+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 lw = LINE_WIDTH, gw = LINE_WIDTH, bw, i, loff;
- while ((bw = lw * lh + gw * (lh+1)) > TILE_SIZE)
- gw--;
- loff = OFFSET(bw);
- if (v & G_MARKH)
- draw_rect(dr, ox, oy + loff, TILE_SIZE, bw, COL_MARK);
- for (i = 0; i < lh; i++, loff += lw + gw)
- draw_rect(dr, ox, oy + loff + gw, TILE_SIZE, lw, col);
+ 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 line_cross(drawing *dr, game_drawstate *ds,
- int ox, int oy, int col, grid_type v)
+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 lines_lvlh(game_state *state, int x, int y, grid_type v,
- int *lv_r, int *lh_r)
+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)
{
- int lh = 0, lv = 0;
+ /*
+ * 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;
- if (v & G_LINEV) lv = INDEX(state,lines,x,y);
- if (v & G_LINEH) lh = INDEX(state,lines,x,y);
+ 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);
-#ifdef DRAW_HINTS
- if (INDEX(state, possv, x, y) && !lv) {
- lv = INDEX(state, possv, x, y);
- }
- if (INDEX(state, possh, x, y) && !lh) {
- lh = INDEX(state, possh, x, y);
+ 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);
+ }
}
-#endif
- /*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 dsf_debug_draw(drawing *dr,
- game_state *state, game_drawstate *ds,
- int x, int y)
+static void draw_hline(drawing *dr, game_drawstate *ds,
+ int ox, int oy, int w, unsigned long vdata, int which)
{
-#ifdef DRAW_DSF
- int ts = TILE_SIZE/2;
- int ox = COORD(x) + ts/2, oy = COORD(y) + ts/2;
- char str[10];
+ draw_general_line(dr, ds, ox, oy, 1, 0, 0, 1, w, vdata, which);
+}
- sprintf(str, "%d", dsf_canonify(state->solver->dsf, DINDEX(x,y)));
- draw_text(dr, ox, oy, FONT_VARIABLE, ts,
- ALIGN_VCENTRE | ALIGN_HCENTRE, COL_WARNING, str);
-#endif
+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);
}
-static void lines_redraw(drawing *dr,
- game_state *state, game_drawstate *ds, game_ui *ui,
- int x, int y, grid_type v, int lv, int lh)
+#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 ox = COORD(x), oy = COORD(y);
- int vcol = (v & G_FLASH) ? COL_HIGHLIGHT :
- (v & G_WARN) ? COL_WARNING : COL_FOREGROUND, hcol = vcol;
- grid_type todraw = v & G_NOLINE;
+ int half, orad, irad, fg, bg;
- if (v & G_ISSEL) {
- if (ui->todraw & G_FLAGSH) hcol = COL_SELECTED;
- if (ui->todraw & G_FLAGSV) vcol = COL_SELECTED;
- todraw |= ui->todraw;
- }
+ if ((idata & DI_BGMASK) == DI_BG_NO_ISLAND)
+ return;
- draw_rect(dr, ox, oy, TILE_SIZE, TILE_SIZE, COL_BACKGROUND);
+ 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);
-#ifdef DRAW_HINTS
- if (INDEX(state, possv, x, y) && !(v & G_LINEV))
- vcol = COL_HINT;
- if (INDEX(state, possh, x, y) && !(v & G_LINEH))
- hcol = COL_HINT;
-#endif
-#ifdef DRAW_GRID
- draw_rect_outline(dr, ox, oy, TILE_SIZE, TILE_SIZE, COL_GRID);
-#endif
+ /* 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 (todraw & G_NOLINEV) {
- line_cross(dr, ds, ox + TS8(3), oy + TS8(1), vcol, todraw);
- line_cross(dr, ds, ox + TS8(3), oy + TS8(5), vcol, todraw);
+ 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);
}
- if (todraw & G_NOLINEH) {
- line_cross(dr, ds, ox + TS8(1), oy + TS8(3), hcol, todraw);
- line_cross(dr, ds, ox + TS8(5), oy + TS8(3), hcol, todraw);
- }
- if (lv)
- lines_vert(dr, ds, ox, oy, lv, vcol, v);
- if (lh)
- lines_horiz(dr, ds, ox, oy, lh, hcol, v);
+}
+
+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);
- dsf_debug_draw(dr, state, ds, x, y);
+ /*
+ * 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);
}
-#define ISLAND_RADIUS ((TILE_SIZE*12)/20)
-#define ISLAND_NUMSIZE(is) \
- (((is)->count < 10) ? (TILE_SIZE*7)/10 : (TILE_SIZE*5)/10)
-
-static void island_redraw(drawing *dr,
- game_state *state, game_drawstate *ds,
- struct island *is, grid_type v)
-{
- /* These overlap the edges of their squares, which is why they're drawn later.
- * We know they can't overlap each other because they're not allowed within 2
- * squares of each other. */
- int half = TILE_SIZE/2;
- int ox = COORD(is->x) + half, oy = COORD(is->y) + half;
- int orad = ISLAND_RADIUS, irad = orad - LINE_WIDTH;
- int updatesz = orad*2+1;
- int tcol = (v & G_FLASH) ? COL_HIGHLIGHT :
- (v & G_WARN) ? COL_WARNING : COL_FOREGROUND;
- int col = (v & G_ISSEL) ? COL_SELECTED : tcol;
- int bg = (v & G_MARK) ? COL_MARK : COL_BACKGROUND;
- char str[10];
+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;
-#ifdef DRAW_GRID
- draw_rect_outline(dr, COORD(is->x), COORD(is->y),
- TILE_SIZE, TILE_SIZE, COL_GRID);
-#endif
+ clip(dr, ox, oy, TILE_SIZE, TILE_SIZE);
+ draw_rect(dr, ox, oy, TILE_SIZE, TILE_SIZE, COL_BACKGROUND);
- /* draw a thick circle */
- draw_circle(dr, ox, oy, orad, col, col);
- draw_circle(dr, ox, oy, irad, bg, bg);
+ /*
+ * 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);
- sprintf(str, "%d", is->count);
- draw_text(dr, ox, oy, FONT_VARIABLE, ISLAND_NUMSIZE(is),
- ALIGN_VCENTRE | ALIGN_HCENTRE, tcol, str);
+ draw_island(dr, ds, ox + TILE_SIZE*dx, oy + TILE_SIZE*dy, -1,
+ (data >> D_I_ISLAND_SHIFT) & DI_MASK);
- dsf_debug_draw(dr, state, ds, is->x, is->y);
- draw_update(dr, ox - orad, oy - orad, updatesz, updatesz);
+ unclip(dr);
+ draw_update(dr, cx, cy, cw, ch);
}
-static void game_redraw(drawing *dr, game_drawstate *ds, game_state *oldstate,
- game_state *state, int dir, game_ui *ui,
- float animtime, float flashtime)
+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, force = 0, i, j, redraw, lv, lh;
- grid_type v, dsv, flash = 0;
+ int x, y, lv, lh;
+ grid_type v, flash = 0;
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 = G_FLASH;
+ if (f == 1 || f == 3) flash = TRUE;
}
/* Clear screen, if required. */
TILE_SIZE * ds->w + 2 * BORDER,
TILE_SIZE * ds->h + 2 * BORDER);
ds->started = 1;
- force = 1;
}
if (ui->dragx_src != -1 && ui->dragy_src != -1) {
} else
ds->dragging = 0;
- /* Draw all lines (and hints, if we want), but *not* islands. */
+ /*
+ * 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) | flash;
- dsv = GRID(ds,x,y) & ~G_REDRAW;
-
- if (v & G_ISLAND) continue;
+ 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 (is_drag_dst) {
- if (WITHIN(x,is_drag_src->x, is_drag_dst->x) &&
- WITHIN(y,is_drag_src->y, is_drag_dst->y))
- v |= G_ISSEL;
+ 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;
+ int 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;
}
- lines_lvlh(state, x, y, v, &lv, &lh);
-
- if (v != dsv ||
- lv != INDEX(ds,lv,x,y) ||
- lh != INDEX(ds,lh,x,y) ||
- force) {
- GRID(ds, x, y) = v | G_REDRAW;
- INDEX(ds,lv,x,y) = lv;
- INDEX(ds,lh,x,y) = lh;
- lines_redraw(dr, state, ds, ui, x, y, v, lv, lh);
- } else
- GRID(ds,x,y) &= ~G_REDRAW;
}
}
- /* Draw islands. */
- for (i = 0; i < state->n_islands; i++) {
- is = &state->islands[i];
- v = GRID(state, is->x, is->y) | flash;
-
- redraw = 0;
- for (j = 0; j < is->adj.npoints; j++) {
- if (GRID(ds,is->adj.points[j].x,is->adj.points[j].y) & G_REDRAW) {
- redraw = 1;
+ /*
+ * 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;
}
}
-
- if (is_drag_src) {
- if (is == is_drag_src)
- v |= G_ISSEL;
- else if (is_drag_dst && is == is_drag_dst)
- v |= G_ISSEL;
- }
-
- if (island_impossible(is, v & G_MARK)) v |= G_WARN;
-
- if ((v != GRID(ds, is->x, is->y)) || force || redraw) {
- GRID(ds,is->x,is->y) = v;
- island_redraw(dr, state, ds, is, v);
- }
}
}
-static float game_anim_length(game_state *oldstate, game_state *newstate,
- int dir, game_ui *ui)
+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(game_state *oldstate, game_state *newstate,
- int dir, game_ui *ui)
+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 0.0F;
}
-static int game_timing_state(game_state *state, game_ui *ui)
+static int game_status(const game_state *state)
+{
+ return state->completed ? +1 : 0;
+}
+
+static int game_timing_state(const game_state *state, game_ui *ui)
{
return TRUE;
}
-static void game_print_size(game_params *params, float *x, float *y)
+static void game_print_size(const game_params *params, float *x, float *y)
{
int pw, ph;
/* 10mm squares by default. */
game_compute_size(params, 1000, &pw, &ph);
- *x = pw / 100.0;
- *y = ph / 100.0;
+ *x = pw / 100.0F;
+ *y = ph / 100.0F;
}
-static void game_print(drawing *dr, game_state *state, int ts)
+static void game_print(drawing *dr, const game_state *state, 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 = ts/8;
+ int loff;
grid_type grid;
/* Ick: fake up `ds->tilesize' for macro expansion purposes */
/* 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++) {
if (grid & G_ISLAND) continue;
if (grid & G_LINEV) {
- if (nl > 1) {
- draw_line(dr, cx+ts/2-loff, cy, cx+ts/2-loff, cy+ts, ink);
- draw_line(dr, cx+ts/2+loff, cy, cx+ts/2+loff, cy+ts, ink);
- } else {
- draw_line(dr, cx+ts/2, cy, cx+ts/2, cy+ts, ink);
- }
+ 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) {
- if (nl > 1) {
- draw_line(dr, cx, cy+ts/2-loff, cx+ts, cy+ts/2-loff, ink);
- draw_line(dr, cx, cy+ts/2+loff, cx+ts, cy+ts/2+loff, ink);
- } else {
- draw_line(dr, cx, cy+ts/2, cx+ts, cy+ts/2, ink);
- }
+ 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[10];
+ char str[32];
struct island *is = &state->islands[i];
grid = GRID(state, is->x, is->y);
cx = COORD(is->x) + 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),
+ draw_text(dr, cx, cy, FONT_VARIABLE, ISLAND_NUMSIZE(is->count),
ALIGN_VCENTRE | ALIGN_HCENTRE, ink, str);
}
}
#endif
const struct game thegame = {
- "Bridges", "games.bridges",
+ "Bridges", "games.bridges", "bridges",
default_params,
game_fetch_preset,
decode_params,
dup_game,
free_game,
TRUE, solve_game,
- TRUE, game_text_format,
+ TRUE, game_can_format_as_text_now, game_text_format,
new_ui,
free_ui,
encode_ui,
game_redraw,
game_anim_length,
game_flash_length,
+ game_status,
TRUE, FALSE, game_print_size, game_print,
FALSE, /* wants_statusbar */
FALSE, game_timing_state,
- 0, /* flags */
+ REQUIRE_RBUTTON, /* flags */
};
/* vim: set shiftwidth=4 tabstop=8: */