X-Git-Url: https://git.distorted.org.uk/~mdw/sgt/puzzles/blobdiff_plain/e5ab926fcb4c906364925d17c706c313a4913bea..HEAD:/bridges.c diff --git a/bridges.c b/bridges.c index be173ff..a5eef25 100644 --- a/bridges.c +++ b/bridges.c @@ -3,7 +3,68 @@ * * 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 @@ -16,7 +77,6 @@ #include "puzzles.h" /* Turn this on for hints about which lines are considered possibilities. */ -#undef DRAW_HINTS #undef DRAW_GRID #undef DRAW_DSF @@ -40,6 +100,7 @@ enum { COL_SELECTED, COL_MARK, COL_HINT, COL_GRID, COL_WARNING, + COL_CURSOR, NCOLOURS }; @@ -66,9 +127,10 @@ struct game_params { #define G_REDRAW 0x0100 #define G_FLASH 0x0200 #define G_WARN 0x0400 +#define G_CURSOR 0x0800 /* 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) @@ -76,7 +138,8 @@ struct game_params { 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; }; @@ -147,6 +210,11 @@ static void fixup_islands_for_realloc(game_state *state) } } +static int game_can_format_as_text_now(game_params *params) +{ + return TRUE; +} + static char *game_text_format(game_state *state) { int x, y, len, nl; @@ -507,7 +575,6 @@ static int island_impossible(struct island *is, int strict) { int curr = island_countbridges(is), nspc = is->count - curr, nsurrspc; int i, poss; - grid_type v; struct island *is_orth; if (nspc < 0) { @@ -527,7 +594,6 @@ static int island_impossible(struct island *is, int strict) 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; @@ -536,9 +602,24 @@ static int island_impossible(struct island *is, int strict) 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", @@ -859,20 +940,24 @@ static void map_update_possibles(game_state *state) 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++) { @@ -882,6 +967,7 @@ static void map_update_possibles(game_state *state) 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; @@ -900,19 +986,23 @@ static void map_update_possibles(game_state *state) 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++) { @@ -922,6 +1012,7 @@ static void map_update_possibles(game_state *state) 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; @@ -1064,8 +1155,7 @@ 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 @@ -1374,7 +1464,7 @@ static int solve_island_stage2(struct island *is, int *didsth_r) 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; @@ -1383,20 +1473,23 @@ static int solve_island_subgroup(struct island *is, int direction, int n) 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. */ @@ -1406,7 +1499,7 @@ static int solve_island_subgroup(struct island *is, int direction, int n) /* 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")); @@ -1445,10 +1538,6 @@ static int solve_island_stage3(struct island *is, int *didsth_r) 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); @@ -1469,7 +1558,7 @@ static int solve_island_stage3(struct island *is, int *didsth_r) 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", @@ -1487,14 +1576,96 @@ static int solve_island_stage3(struct island *is, int *didsth_r) 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; } @@ -1602,9 +1773,8 @@ static game_state *new_state(game_params *params) 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; @@ -1671,6 +1841,7 @@ static void free_game(game_state *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) @@ -1680,7 +1851,7 @@ static char *new_game_desc(game_params *params, random_state *rs, 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; @@ -1815,7 +1986,8 @@ generated: 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; @@ -1933,6 +2105,9 @@ struct game_ui { 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) @@ -1947,6 +2122,10 @@ static game_ui *new_ui(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; } @@ -1975,10 +2154,11 @@ struct game_drawstate { grid_type *grid; int *lv, *lh; int started, dragging; + int show_hints; }; -static char *update_drag_dst(game_state *state, game_ui *ui, game_drawstate *ds, - int nx, int ny) +static char *update_drag_dst(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; @@ -2073,7 +2253,7 @@ static char *finish_drag(game_state *state, game_ui *ui) return dupstr(buf); } -static char *interpret_move(game_state *state, game_ui *ui, game_drawstate *ds, +static char *interpret_move(game_state *state, game_ui *ui, const game_drawstate *ds, int x, int y, int button) { int gx = FROMCOORD(x), gy = FROMCOORD(y); @@ -2082,6 +2262,7 @@ static char *interpret_move(game_state *state, game_ui *ui, game_drawstate *ds, if (button == LEFT_BUTTON || button == RIGHT_BUTTON) { if (!INGRID(state, gx, gy)) return NULL; + ui->cur_visible = 0; if ((ggrid & G_ISLAND) && !(ggrid & G_MARK)) { ui->dragx_src = gx; ui->dragy_src = gy; @@ -2115,6 +2296,96 @@ static char *interpret_move(game_state *state, game_ui *ui, game_drawstate *ds, ret = game_state_diff(state, solved); free_game(solved); return ret; + } else if (IS_CURSOR_MOVE(button)) { + ui->cur_visible = 1; + if (ui->dragging) { + int nx = ui->cur_x, ny = ui->cur_y; + + move_cursor(button, &nx, &ny, state->w, state->h, 0); + 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) { + 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 == 'g' || button == 'G') { + ui->show_hints = 1 - ui->show_hints; + return ""; } return NULL; @@ -2139,6 +2410,8 @@ static game_state *execute_move(game_state *state, char *move) 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; @@ -2148,6 +2421,8 @@ static game_state *execute_move(game_state *state, char *move) 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; @@ -2156,6 +2431,8 @@ static game_state *execute_move(game_state *state, char *move) 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); @@ -2252,6 +2529,10 @@ static float *game_colours(frontend *fe, int *ncolours) 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; } @@ -2271,6 +2552,7 @@ static game_drawstate *game_new_drawstate(drawing *dr, game_state *state) ds->lh = snewn(wh, int); memset(ds->lv, 0, wh*sizeof(int)); memset(ds->lh, 0, wh*sizeof(int)); + ds->show_hints = 0; return ds; } @@ -2322,7 +2604,25 @@ static void line_cross(drawing *dr, game_drawstate *ds, draw_line(dr, ox+off, oy, ox, oy+off, col); } -static void lines_lvlh(game_state *state, int x, int y, grid_type v, +static int between_island(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 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_lvlh(game_state *state, game_ui *ui, int x, int y, grid_type v, int *lv_r, int *lh_r) { int lh = 0, lv = 0; @@ -2330,14 +2630,10 @@ static void lines_lvlh(game_state *state, int x, int y, grid_type v, if (v & G_LINEV) lv = INDEX(state,lines,x,y); if (v & G_LINEH) lh = INDEX(state,lines,x,y); -#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 (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; } -#endif /*debug(("lvlh: (%d,%d) v 0x%x lv %d lh %d.\n", x, y, v, lv, lh));*/ *lv_r = lv; *lh_r = lh; } @@ -2349,7 +2645,7 @@ static void dsf_debug_draw(drawing *dr, #ifdef DRAW_DSF int ts = TILE_SIZE/2; int ox = COORD(x) + ts/2, oy = COORD(y) + ts/2; - char str[10]; + char str[32]; sprintf(str, "%d", dsf_canonify(state->solver->dsf, DINDEX(x,y))); draw_text(dr, ox, oy, FONT_VARIABLE, ts, @@ -2373,13 +2669,17 @@ static void lines_redraw(drawing *dr, } draw_rect(dr, ox, oy, TILE_SIZE, TILE_SIZE, COL_BACKGROUND); + /*if (v & G_CURSOR) + draw_rect(dr, ox+TILE_SIZE/4, oy+TILE_SIZE/4, + TILE_SIZE/2, TILE_SIZE/2, COL_CURSOR);*/ -#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 + + if (ui->show_hints) { + if (between_island(state, x, y, 0, 1) && !(v & G_LINEV)) + vcol = COL_HINT; + if (between_island(state, x, y, 1, 0) && !(v & G_LINEH)) + hcol = COL_HINT; + } #ifdef DRAW_GRID draw_rect_outline(dr, ox, oy, TILE_SIZE, TILE_SIZE, COL_GRID); #endif @@ -2392,10 +2692,11 @@ static void lines_redraw(drawing *dr, 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); + /* if we're drawing a real line and a hint, make sure we draw the real + * line on top. */ + if (lv && vcol == COL_HINT) lines_vert(dr, ds, ox, oy, lv, vcol, v); + if (lh) lines_horiz(dr, ds, ox, oy, lh, hcol, v); + if (lv && vcol != COL_HINT) lines_vert(dr, ds, ox, oy, lv, vcol, v); dsf_debug_draw(dr, state, ds, x, y); draw_update(dr, ox, oy, TILE_SIZE, TILE_SIZE); @@ -2419,8 +2720,9 @@ static void island_redraw(drawing *dr, 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]; + int bg = (v & G_CURSOR) ? COL_CURSOR : + (v & G_MARK) ? COL_MARK : COL_BACKGROUND; + char str[32]; #ifdef DRAW_GRID draw_rect_outline(dr, COORD(is->x), COORD(is->y), @@ -2481,6 +2783,11 @@ static void game_redraw(drawing *dr, game_drawstate *ds, game_state *oldstate, } else ds->dragging = 0; + if (ui->show_hints != ds->show_hints) { + force = 1; + ds->show_hints = ui->show_hints; + } + /* Draw all lines (and hints, if we want), but *not* islands. */ for (x = 0; x < ds->w; x++) { for (y = 0; y < ds->h; y++) { @@ -2494,7 +2801,10 @@ static void game_redraw(drawing *dr, game_drawstate *ds, game_state *oldstate, WITHIN(y,is_drag_src->y, is_drag_dst->y)) v |= G_ISSEL; } - lines_lvlh(state, x, y, v, &lv, &lh); + lines_lvlh(state, ui, x, y, v, &lv, &lh); + + /*if (ui->cur_visible && ui->cur_x == x && ui->cur_y == y) + v |= G_CURSOR;*/ if (v != dsv || lv != INDEX(ds,lv,x,y) || @@ -2530,6 +2840,9 @@ static void game_redraw(drawing *dr, game_drawstate *ds, game_state *oldstate, if (island_impossible(is, v & G_MARK)) v |= G_WARN; + if (ui->cur_visible && ui->cur_x == is->x && ui->cur_y == is->y) + v |= G_CURSOR; + if ((v != GRID(ds, is->x, is->y)) || force || redraw) { GRID(ds,is->x,is->y) = v; island_redraw(dr, state, ds, is, v); @@ -2553,6 +2866,11 @@ static float game_flash_length(game_state *oldstate, game_state *newstate, return 0.0F; } +static int game_status(game_state *state) +{ + return state->completed ? +1 : 0; +} + static int game_timing_state(game_state *state, game_ui *ui) { return TRUE; @@ -2564,8 +2882,8 @@ static void game_print_size(game_params *params, float *x, float *y) /* 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) @@ -2573,7 +2891,7 @@ static void game_print(drawing *dr, 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 */ @@ -2583,6 +2901,7 @@ static void game_print(drawing *dr, game_state *state, int 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++) { @@ -2592,27 +2911,21 @@ static void game_print(drawing *dr, game_state *state, int ts) 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; @@ -2631,7 +2944,7 @@ static void game_print(drawing *dr, game_state *state, int ts) #endif const struct game thegame = { - "Bridges", "games.bridges", + "Bridges", "games.bridges", "bridges", default_params, game_fetch_preset, decode_params, @@ -2646,7 +2959,7 @@ const struct game thegame = { 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, @@ -2661,10 +2974,11 @@ const struct game thegame = { 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: */