From deff331e5f8d46215b967b7eaa7f64b13878785a Mon Sep 17 00:00:00 2001 From: Simon Tatham Date: Wed, 24 Feb 2016 19:01:42 +0000 Subject: [PATCH] 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. --- bridges.R | 2 +- bridges.c | 147 ++++++++++++++++++++++++------------------------------ 2 files changed, 66 insertions(+), 83 deletions(-) diff --git a/bridges.R b/bridges.R index ea9f186..75df309 100644 --- 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 diff --git a/bridges.c b/bridges.c index 25d3175..de7403e 100644 --- a/bridges.c +++ b/bridges.c @@ -156,7 +156,7 @@ struct island { 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 @@ struct game_state { #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 void map_find_orthogonal(game_state *state) } } -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 (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++; + } 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 (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) @@ -1743,8 +1731,6 @@ static game_state *new_state(const game_params *params) 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 @@ static game_state *dup_game(const game_state *state) 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 @@ static void free_game(game_state *state) sfree(state->wha); - sfree(state->scratch); sfree(state->grid); sfree(state); } -- 2.30.2