X-Git-Url: http://www.chiark.greenend.org.uk/ucgi/~ian/git?a=blobdiff_plain;f=net.c;h=57d91d3581c5af92029ad219e505fa7db3f3c22f;hb=a0a581c8b5422bf0c5ed3fde6aa25811e4eb89fc;hp=c6226f2aca134c94ca46f8ac0c488f93847062fa;hpb=9cd182ffa92e97609d562883a1c8e74949963ba0;p=sgt-puzzles.git diff --git a/net.c b/net.c index c6226f2..57d91d3 100644 --- a/net.c +++ b/net.c @@ -41,6 +41,11 @@ #define D 0x08 #define LOCKED 0x10 #define ACTIVE 0x20 +#define RLOOP (R << 6) +#define ULOOP (U << 6) +#define LLOOP (L << 6) +#define DLOOP (D << 6) +#define LOOP(dir) ((dir) << 6) /* Rotations: Anticlockwise, Clockwise, Flip, general rotate */ #define A(x) ( (((x) & 0x07) << 1) | (((x) & 0x08) >> 3) ) @@ -85,6 +90,7 @@ enum { COL_ENDPOINT, COL_POWERED, COL_BARRIER, + COL_LOOP, NCOLOURS }; @@ -205,7 +211,7 @@ static void free_params(game_params *params) 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 */ @@ -242,7 +248,7 @@ static void decode_params(game_params *ret, char const *string) } } -static char *encode_params(game_params *params, int full) +static char *encode_params(const game_params *params, int full) { char ret[400]; int len; @@ -260,7 +266,7 @@ static char *encode_params(game_params *params, int full) return dupstr(ret); } -static config_item *game_configure(game_params *params) +static config_item *game_configure(const game_params *params) { config_item *ret; char buf[80]; @@ -303,7 +309,7 @@ static config_item *game_configure(game_params *params) 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); @@ -316,7 +322,7 @@ static game_params *custom_params(config_item *cfg) return ret; } -static char *validate_params(game_params *params, int full) +static char *validate_params(const game_params *params, int full) { if (params->width <= 0 || params->height <= 0) return "Width and height must both be greater than zero"; @@ -453,6 +459,11 @@ static int todo_get(struct todo *todo) { return ret; } +/* + * Return values: -1 means puzzle was proved inconsistent, 0 means we + * failed to narrow down to a unique solution, +1 means we solved it + * fully. + */ static int net_solver(int w, int h, unsigned char *tiles, unsigned char *barriers, int wrapping) { @@ -727,7 +738,11 @@ static int net_solver(int w, int h, unsigned char *tiles, #endif } - assert(j > 0); /* we can't lose _all_ possibilities! */ + if (j == 0) { + /* If we've ruled out all possible orientations for a + * tile, then our puzzle has no solution at all. */ + return -1; + } if (j < i) { done_something = TRUE; @@ -807,14 +822,14 @@ static int net_solver(int w, int h, unsigned char *tiles, /* * Mark all completely determined tiles as locked. */ - j = TRUE; + j = +1; for (i = 0; i < w*h; i++) { if (tilestate[i * 4 + 1] == 255) { assert(tilestate[i * 4 + 0] != 255); tiles[i] = tilestate[i * 4] | LOCKED; } else { tiles[i] &= ~LOCKED; - j = FALSE; + j = 0; } } @@ -1126,7 +1141,11 @@ static void perturb(int w, int h, unsigned char *tiles, int wrapping, sfree(perimeter); } -static char *new_game_desc(game_params *params, random_state *rs, +static int *compute_loops_inner(int w, int h, int wrapping, + const unsigned char *tiles, + const unsigned char *barriers); + +static char *new_game_desc(const game_params *params, random_state *rs, char **aux, int interactive) { tree234 *possibilities, *barriertree; @@ -1324,7 +1343,7 @@ static char *new_game_desc(game_params *params, random_state *rs, /* * Run the solver to check unique solubility. */ - while (!net_solver(w, h, tiles, NULL, params->wrapping)) { + while (net_solver(w, h, tiles, NULL, params->wrapping) != 1) { int n = 0; /* @@ -1424,10 +1443,21 @@ static char *new_game_desc(game_params *params, random_state *rs, * connectedness. However, that would take more effort, and * it's easier to simply make sure every grid is _obviously_ * not solved.) + * + * We also require that our shuffle produces no loops in the + * initial grid state, because it's a bit rude to light up a 'HEY, + * YOU DID SOMETHING WRONG!' indicator when the user hasn't even + * had a chance to do _anything_ yet. This also is possible just + * by retrying the whole shuffle on failure, because it's clear + * that at least one non-solved shuffle with no loops must exist. + * (Proof: take the _solved_ state of the puzzle, and rotate one + * endpoint.) */ while (1) { - int mismatches; + int mismatches, prev_loopsquares, this_loopsquares, i; + int *loops; + shuffle: for (y = 0; y < h; y++) { for (x = 0; x < w; x++) { int orig = index(params, tiles, x, y); @@ -1436,6 +1466,35 @@ static char *new_game_desc(game_params *params, random_state *rs, } } + /* + * Check for loops, and try to fix them by reshuffling just + * the squares involved. + */ + prev_loopsquares = w*h+1; + while (1) { + loops = compute_loops_inner(w, h, params->wrapping, tiles, NULL); + this_loopsquares = 0; + for (i = 0; i < w*h; i++) { + if (loops[i]) { + int orig = tiles[i]; + int rot = random_upto(rs, 4); + tiles[i] = ROT(orig, rot); + this_loopsquares++; + } + } + sfree(loops); + if (this_loopsquares > prev_loopsquares) { + /* + * We're increasing rather than reducing the number of + * loops. Give up and go back to the full shuffle. + */ + goto shuffle; + } + if (this_loopsquares == 0) + break; + prev_loopsquares = this_loopsquares; + } + mismatches = 0; /* * I can't even be bothered to check for mismatches across @@ -1452,8 +1511,11 @@ static char *new_game_desc(game_params *params, random_state *rs, mismatches++; } - if (mismatches > 0) - break; + if (mismatches == 0) + continue; + + /* OK. */ + break; } /* @@ -1545,7 +1607,7 @@ static char *new_game_desc(game_params *params, random_state *rs, return desc; } -static char *validate_desc(game_params *params, char *desc) +static char *validate_desc(const game_params *params, const char *desc) { int w = params->width, h = params->height; int i; @@ -1575,7 +1637,8 @@ static char *validate_desc(game_params *params, char *desc) * Construct an initial game state, given a description and parameters. */ -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) { game_state *state; int w, h, x, y; @@ -1661,7 +1724,7 @@ static game_state *new_game(midend *me, game_params *params, char *desc) return state; } -static game_state *dup_game(game_state *state) +static game_state *dup_game(const game_state *state) { game_state *ret; @@ -1689,8 +1752,8 @@ static void free_game(game_state *state) sfree(state); } -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) { unsigned char *tiles; char *ret; @@ -1704,9 +1767,17 @@ static char *solve_game(game_state *state, game_state *currstate, * Run the internal solver on the provided grid. This might * not yield a complete solution. */ + int solver_result; + memcpy(tiles, state->tiles, state->width * state->height); - net_solver(state->width, state->height, tiles, - state->barriers, state->wrapping); + solver_result = net_solver(state->width, state->height, tiles, + state->barriers, state->wrapping); + + if (solver_result < 0) { + *error = "No solution exists for this puzzle"; + sfree(tiles); + return NULL; + } } else { for (i = 0; i < state->width * state->height; i++) { int c = aux[i]; @@ -1784,12 +1855,12 @@ static char *solve_game(game_state *state, game_state *currstate, return ret; } -static int game_can_format_as_text_now(game_params *params) +static int game_can_format_as_text_now(const game_params *params) { return TRUE; } -static char *game_text_format(game_state *state) +static char *game_text_format(const game_state *state) { return NULL; } @@ -1805,7 +1876,7 @@ static char *game_text_format(game_state *state) * completed - just call this function and see whether every square * is marked active. */ -static unsigned char *compute_active(game_state *state, int cx, int cy) +static unsigned char *compute_active(const game_state *state, int cx, int cy) { unsigned char *active; tree234 *todo; @@ -1855,6 +1926,87 @@ static unsigned char *compute_active(game_state *state, int cx, int cy) return active; } +struct net_neighbour_ctx { + int w, h; + const unsigned char *tiles, *barriers; + int i, n, neighbours[4]; +}; +static int net_neighbour(int vertex, void *vctx) +{ + struct net_neighbour_ctx *ctx = (struct net_neighbour_ctx *)vctx; + + if (vertex >= 0) { + int x = vertex % ctx->w, y = vertex / ctx->w; + int tile, dir, x1, y1, v1; + + ctx->i = ctx->n = 0; + + tile = ctx->tiles[vertex]; + if (ctx->barriers) + tile &= ~ctx->barriers[vertex]; + + for (dir = 1; dir < 0x10; dir <<= 1) { + if (!(tile & dir)) + continue; + OFFSETWH(x1, y1, x, y, dir, ctx->w, ctx->h); + v1 = y1 * ctx->w + x1; + if (ctx->tiles[v1] & F(dir)) + ctx->neighbours[ctx->n++] = v1; + } + } + + if (ctx->i < ctx->n) + return ctx->neighbours[ctx->i++]; + else + return -1; +} + +static int *compute_loops_inner(int w, int h, int wrapping, + const unsigned char *tiles, + const unsigned char *barriers) +{ + struct net_neighbour_ctx ctx; + struct findloopstate *fls; + int *loops; + int x, y; + + fls = findloop_new_state(w*h); + ctx.w = w; + ctx.h = h; + ctx.tiles = tiles; + ctx.barriers = barriers; + findloop_run(fls, w*h, net_neighbour, &ctx); + + loops = snewn(w*h, int); + + for (y = 0; y < h; y++) { + for (x = 0; x < w; x++) { + int x1, y1, dir; + int flags = 0; + + for (dir = 1; dir < 0x10; dir <<= 1) { + if ((tiles[y*w+x] & dir) && + !(barriers && (barriers[y*w+x] & dir))) { + OFFSETWH(x1, y1, x, y, dir, w, h); + if ((tiles[y1*w+x1] & F(dir)) && + findloop_is_loop_edge(fls, y*w+x, y1*w+x1)) + flags |= LOOP(dir); + } + } + loops[y*w+x] = flags; + } + } + + findloop_free_state(fls); + return loops; +} + +static int *compute_loops(const game_state *state) +{ + return compute_loops_inner(state->width, state->height, state->wrapping, + state->tiles, state->barriers); +} + struct game_ui { int org_x, org_y; /* origin */ int cx, cy; /* source tile (game coordinates) */ @@ -1866,7 +2018,7 @@ struct game_ui { #endif }; -static game_ui *new_ui(game_state *state) +static game_ui *new_ui(const game_state *state) { void *seed; int seedsize; @@ -1888,7 +2040,7 @@ static void free_ui(game_ui *ui) sfree(ui); } -static char *encode_ui(game_ui *ui) +static char *encode_ui(const game_ui *ui) { char buf[120]; /* @@ -1899,14 +2051,14 @@ static char *encode_ui(game_ui *ui) return dupstr(buf); } -static void decode_ui(game_ui *ui, char *encoding) +static void decode_ui(game_ui *ui, const char *encoding) { sscanf(encoding, "O%d,%d;C%d,%d", &ui->org_x, &ui->org_y, &ui->cx, &ui->cy); } -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) { } @@ -1915,14 +2067,15 @@ struct game_drawstate { int width, height; int org_x, org_y; int tilesize; - unsigned char *visible; + int *visible; }; /* ---------------------------------------------------------------------- * Process a move. */ -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) { char *nullret; int tx = -1, ty = -1, dir = 0; @@ -2194,7 +2347,7 @@ static char *interpret_move(game_state *state, game_ui *ui, } } -static game_state *execute_move(game_state *from, char *move) +static game_state *execute_move(const game_state *from, const char *move) { game_state *ret; int tx = -1, ty = -1, n, noanim, orig; @@ -2254,24 +2407,31 @@ static game_state *execute_move(game_state *from, char *move) /* * Check whether the game has been completed. * - * For this purpose it doesn't matter where the source square - * is, because we can start from anywhere and correctly - * determine whether the game is completed. + * For this purpose it doesn't matter where the source square is, + * because we can start from anywhere (or, at least, any square + * that's non-empty!), and correctly determine whether the game is + * completed. */ { - unsigned char *active = compute_active(ret, 0, 0); - int x1, y1; + unsigned char *active; + int pos; int complete = TRUE; - for (x1 = 0; x1 < ret->width; x1++) - for (y1 = 0; y1 < ret->height; y1++) - if ((tile(ret, x1, y1) & 0xF) && !index(ret, active, x1, y1)) { + for (pos = 0; pos < ret->width * ret->height; pos++) + if (ret->tiles[pos] & 0xF) + break; + + if (pos < ret->width * ret->height) { + active = compute_active(ret, pos % ret->width, pos / ret->width); + + for (pos = 0; pos < ret->width * ret->height; pos++) + if ((ret->tiles[pos] & 0xF) && !active[pos]) { complete = FALSE; - goto break_label; /* break out of two loops at once */ - } - break_label: + break; + } - sfree(active); + sfree(active); + } if (complete) ret->completed = TRUE; @@ -2285,17 +2445,19 @@ static game_state *execute_move(game_state *from, char *move) * Routines for drawing the game position on the screen. */ -static game_drawstate *game_new_drawstate(drawing *dr, game_state *state) +static game_drawstate *game_new_drawstate(drawing *dr, const game_state *state) { game_drawstate *ds = snew(game_drawstate); + int i; ds->started = FALSE; ds->width = state->width; ds->height = state->height; ds->org_x = ds->org_y = -1; - ds->visible = snewn(state->width * state->height, unsigned char); + ds->visible = snewn(state->width * state->height, int); ds->tilesize = 0; /* undecided yet */ - memset(ds->visible, 0xFF, state->width * state->height); + for (i = 0; i < state->width * state->height; i++) + ds->visible[i] = -1; return ds; } @@ -2306,15 +2468,15 @@ static void game_free_drawstate(drawing *dr, game_drawstate *ds) sfree(ds); } -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) { *x = WINDOW_OFFSET * 2 + tilesize * params->width + TILE_BORDER; *y = WINDOW_OFFSET * 2 + tilesize * params->height + TILE_BORDER; } static void game_set_size(drawing *dr, game_drawstate *ds, - game_params *params, int tilesize) + const game_params *params, int tilesize) { ds->tilesize = tilesize; } @@ -2353,6 +2515,13 @@ static float *game_colours(frontend *fe, int *ncolours) ret[COL_BARRIER * 3 + 1] = 0.0F; ret[COL_BARRIER * 3 + 2] = 0.0F; + /* + * Highlighted loops are red as well. + */ + ret[COL_LOOP * 3 + 0] = 1.0F; + ret[COL_LOOP * 3 + 1] = 0.0F; + ret[COL_LOOP * 3 + 2] = 0.0F; + /* * Unpowered endpoints are blue. */ @@ -2447,7 +2616,7 @@ static void draw_barrier(drawing *dr, game_drawstate *ds, /* * draw_tile() is passed physical coordinates */ -static void draw_tile(drawing *dr, game_state *state, game_drawstate *ds, +static void draw_tile(drawing *dr, const game_state *state, game_drawstate *ds, int x, int y, int tile, int src, float angle, int cursor) { int bx = WINDOW_OFFSET + TILE_SIZE * x; @@ -2525,9 +2694,14 @@ static void draw_tile(drawing *dr, game_state *state, game_drawstate *ds, ey = (TILE_SIZE - TILE_BORDER - 1.0F) / 2.0F * Y(dir); MATMUL(tx, ty, matrix, ex, ey); draw_line(dr, bx+(int)cx, by+(int)cy, - bx+(int)(cx+tx), by+(int)(cy+ty), col); + bx+(int)(cx+tx), by+(int)(cy+ty), + (tile & LOOP(dir)) ? COL_LOOP : col); } } + /* If we've drawn any loop-highlighted arms, make sure the centre + * point is loop-coloured rather than a later arm overwriting it. */ + if (tile & (RLOOP | ULOOP | LLOOP | DLOOP)) + draw_rect(dr, bx+(int)cx, by+(int)cy, 1, 1, COL_LOOP); /* * Draw the box in the middle. We do this in blue if the tile @@ -2596,7 +2770,9 @@ static void draw_tile(drawing *dr, game_state *state, game_drawstate *ds, */ draw_rect_coords(dr, px-vx, py-vy, px+lx+vx, py+ly+vy, COL_WIRE); draw_rect_coords(dr, px, py, px+lx, py+ly, - (tile & ACTIVE) ? COL_POWERED : COL_WIRE); + ((tile & LOOP(dir)) ? COL_LOOP : + (tile & ACTIVE) ? COL_POWERED : + COL_WIRE)); } else { /* * The other tile extends into our border, but isn't @@ -2663,11 +2839,14 @@ static void draw_tile(drawing *dr, game_state *state, game_drawstate *ds, draw_update(dr, bx, by, TILE_SIZE+TILE_BORDER, TILE_SIZE+TILE_BORDER); } -static void game_redraw(drawing *dr, game_drawstate *ds, game_state *oldstate, - game_state *state, int dir, game_ui *ui, float t, float ft) +static void game_redraw(drawing *dr, game_drawstate *ds, + const game_state *oldstate, const game_state *state, + int dir, const game_ui *ui, + float t, float ft) { int x, y, tx, ty, frame, last_rotate_dir, moved_origin = FALSE; unsigned char *active; + int *loops; float angle = 0.0; /* @@ -2761,11 +2940,13 @@ static void game_redraw(drawing *dr, game_drawstate *ds, game_state *oldstate, * Draw any tile which differs from the way it was last drawn. */ active = compute_active(state, ui->cx, ui->cy); + loops = compute_loops(state); for (x = 0; x < ds->width; x++) for (y = 0; y < ds->height; y++) { - unsigned char c = tile(state, GX(x), GY(y)) | - index(state, active, GX(x), GY(y)); + int c = tile(state, GX(x), GY(y)) | + index(state, active, GX(x), GY(y)) | + index(state, loops, GX(x), GY(y)); int is_src = GX(x) == ui->cx && GY(y) == ui->cy; int is_anim = GX(x) == tx && GY(y) == ty; int is_cursor = ui->cur_visible && @@ -2792,12 +2973,12 @@ static void game_redraw(drawing *dr, game_drawstate *ds, game_state *oldstate, if (moved_origin || index(state, ds->visible, x, y) != c || - index(state, ds->visible, x, y) == 0xFF || + index(state, ds->visible, x, y) == -1 || is_src || is_anim || is_cursor) { draw_tile(dr, state, ds, x, y, c, is_src, (is_anim ? angle : 0.0F), is_cursor); if (is_src || is_anim || is_cursor) - index(state, ds->visible, x, y) = 0xFF; + index(state, ds->visible, x, y) = -1; else index(state, ds->visible, x, y) = c; } @@ -2807,29 +2988,53 @@ static void game_redraw(drawing *dr, game_drawstate *ds, game_state *oldstate, * Update the status bar. */ { - char statusbuf[256]; + char statusbuf[256], *p; int i, n, n2, a; + int complete = FALSE; + + p = statusbuf; + *p = '\0'; /* ensure even an empty status string is terminated */ - n = state->width * state->height; - for (i = a = n2 = 0; i < n; i++) { - if (active[i]) - a++; - if (state->tiles[i] & 0xF) - n2++; + if (state->used_solve) { + p += sprintf(p, "Auto-solved. "); + complete = TRUE; + } else if (state->completed) { + p += sprintf(p, "COMPLETED! "); + complete = TRUE; } - sprintf(statusbuf, "%sActive: %d/%d", - (state->used_solve ? "Auto-solved. " : - state->completed ? "COMPLETED! " : ""), a, n2); + /* + * Omit the 'Active: n/N' counter completely if the source + * tile is a completely empty one, because then the active + * count can't help but read '1'. + */ + if (tile(state, ui->cx, ui->cy) & 0xF) { + n = state->width * state->height; + for (i = a = n2 = 0; i < n; i++) { + if (active[i]) + a++; + if (state->tiles[i] & 0xF) + n2++; + } + + /* + * Also, if we're displaying a completion indicator and + * the game is still in its completed state (i.e. every + * tile is active), we might as well omit this too. + */ + if (!complete || a < n2) + p += sprintf(p, "Active: %d/%d", a, n2); + } status_bar(dr, statusbuf); } sfree(active); + sfree(loops); } -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) { int last_rotate_dir; @@ -2844,8 +3049,8 @@ static float game_anim_length(game_state *oldstate, 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 the game has just been completed, we display a completion @@ -2864,12 +3069,17 @@ static float game_flash_length(game_state *oldstate, 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; @@ -2927,7 +3137,7 @@ static void draw_diagram(drawing *dr, game_drawstate *ds, int x, int y, } } -static void game_print(drawing *dr, game_state *state, int tilesize) +static void game_print(drawing *dr, const game_state *state, int tilesize) { int w = state->width, h = state->height; int ink = print_mono_colour(dr, 0); @@ -3011,7 +3221,7 @@ static void game_print(drawing *dr, game_state *state, int tilesize) const struct game thegame = { "Net", "games.net", "net", default_params, - game_fetch_preset, + game_fetch_preset, NULL, decode_params, encode_params, free_params, @@ -3039,6 +3249,7 @@ const struct game thegame = { game_redraw, game_anim_length, game_flash_length, + game_status, TRUE, FALSE, game_print_size, game_print, TRUE, /* wants_statusbar */ FALSE, game_timing_state,