ref: deff331e5f8d46215b967b7eaa7f64b13878785a
parent: 1add03f7b8a502d4453f53f4ea6930d0e71a6bb0
author: Simon Tatham <anakin@pobox.com>
date: Wed Feb 24 14:01:42 EST 2016
Bridges: use the new findloop for loop detection. Bridges only needs a loop detector for its non-default 'don't allow loops' mode. But the one it had was using the graph-pruning strategy, which means it had the dumb-bell bug - two loops joined by a path would highlight the path as well as the loops. Switching to the new findloop system fixes that bug. A side effect is that I've been able to remove the 'scratch' array from the game_state, which was only used by the old loop finder, so that should save memory.
--- a/bridges.R
+++ b/bridges.R
@@ -1,6 +1,6 @@
# -*- makefile -*-
-BRIDGES_EXTRA = dsf
+BRIDGES_EXTRA = dsf findloop
bridges : [X] GTK COMMON bridges BRIDGES_EXTRA bridges-icon|no-icon
--- a/bridges.c
+++ b/bridges.c
@@ -156,7 +156,7 @@
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. */
@@ -175,7 +175,6 @@
#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)))
@@ -1051,95 +1050,84 @@
}
}
-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;
+ 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;
- 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++;
+ 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;
+ int x, y;
+ struct findloopstate *fls;
+ struct bridges_neighbour_ctx ctx;
+ int ret;
- memcpy(state->scratch, state->grid, GRIDSZ(state));
+ fls = findloop_new_state(state->w * state->h);
+ ctx.state = state;
+ ret = findloop_run(fls, state->w * state->h, bridges_neighbour, &ctx);
- /* 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. */
-
- /* 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;
+ for (x = 0; x < state->w; x++) {+ int u, v;
- 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;
+ 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)
@@ -1743,8 +1731,6 @@
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));
@@ -1789,8 +1775,6 @@
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));
@@ -1830,7 +1814,6 @@
sfree(state->wha);
- sfree(state->scratch);
sfree(state->grid);
sfree(state);
}