X-Git-Url: https://git.distorted.org.uk/~mdw/sgt/puzzles/blobdiff_plain/9b4b03d31e30089e9f45f6ea166561c4c0c25a9c..50ff573008fcfcc1cf1e9c071d36f5c84e2684dc:/net.c diff --git a/net.c b/net.c index 78df30d..5308031 100644 --- a/net.c +++ b/net.c @@ -75,8 +75,15 @@ struct game_params { float barrier_probability; }; +struct game_aux_info { + int width, height; + unsigned char *tiles; +}; + struct game_state { - int width, height, cx, cy, wrapping, completed, last_rotate_dir; + int width, height, cx, cy, wrapping, completed; + int last_rotate_x, last_rotate_y, last_rotate_dir; + int used_solve, just_used_solve; unsigned char *tiles; unsigned char *barriers; }; @@ -181,9 +188,8 @@ static game_params *dup_params(game_params *params) return ret; } -static game_params *decode_params(char const *string) +static void decode_params(game_params *ret, char const *string) { - game_params *ret = default_params(); char const *p = string; ret->width = atoi(p); @@ -199,11 +205,9 @@ static game_params *decode_params(char const *string) } else { ret->height = ret->width; } - - return ret; } -static char *encode_params(game_params *params) +static char *encode_params(game_params *params, int full) { char ret[400]; int len; @@ -211,7 +215,7 @@ static char *encode_params(game_params *params) len = sprintf(ret, "%dx%d", params->width, params->height); if (params->wrapping) ret[len++] = 'w'; - if (params->barrier_probability) + if (full && params->barrier_probability) len += sprintf(ret+len, "b%g", params->barrier_probability); assert(len < lenof(ret)); ret[len] = '\0'; @@ -287,84 +291,27 @@ static char *validate_params(game_params *params) } /* ---------------------------------------------------------------------- - * Randomly select a new game seed. + * Randomly select a new game description. */ -static char *new_game_seed(game_params *params, random_state *rs) +static char *new_game_desc(game_params *params, random_state *rs, + game_aux_info **aux) { - /* - * The full description of a Net game is far too large to - * encode directly in the seed, so by default we'll have to go - * for the simple approach of providing a random-number seed. - * - * (This does not restrict me from _later on_ inventing a seed - * string syntax which can never be generated by this code - - * for example, strings beginning with a letter - allowing me - * to type in a precise game, and have new_game detect it and - * understand it and do something completely different.) - */ - char buf[40]; - sprintf(buf, "%lu", random_bits(rs, 32)); - return dupstr(buf); -} + tree234 *possibilities, *barriertree; + int w, h, x, y, cx, cy, nbarriers; + unsigned char *tiles, *barriers; + char *desc, *p; -static char *validate_seed(game_params *params, char *seed) -{ - /* - * Since any string at all will suffice to seed the RNG, there - * is no validation required. - */ - return NULL; -} + w = params->width; + h = params->height; -/* ---------------------------------------------------------------------- - * Construct an initial game state, given a seed and parameters. - */ + tiles = snewn(w * h, unsigned char); + memset(tiles, 0, w * h); + barriers = snewn(w * h, unsigned char); + memset(barriers, 0, w * h); -static game_state *new_game(game_params *params, char *seed) -{ - random_state *rs; - game_state *state; - tree234 *possibilities, *barriers; - int w, h, x, y, nbarriers; - - assert(params->width > 0 && params->height > 0); - assert(params->width > 1 || params->height > 1); - - /* - * Create a blank game state. - */ - state = snew(game_state); - w = state->width = params->width; - h = state->height = params->height; - state->cx = state->width / 2; - state->cy = state->height / 2; - state->wrapping = params->wrapping; - state->last_rotate_dir = 0; - state->completed = FALSE; - state->tiles = snewn(state->width * state->height, unsigned char); - memset(state->tiles, 0, state->width * state->height); - state->barriers = snewn(state->width * state->height, unsigned char); - memset(state->barriers, 0, state->width * state->height); - - /* - * Set up border barriers if this is a non-wrapping game. - */ - if (!state->wrapping) { - for (x = 0; x < state->width; x++) { - barrier(state, x, 0) |= U; - barrier(state, x, state->height-1) |= D; - } - for (y = 0; y < state->height; y++) { - barrier(state, 0, y) |= L; - barrier(state, state->width-1, y) |= R; - } - } - - /* - * Seed the internal random number generator. - */ - rs = random_init(seed, strlen(seed)); + cx = w / 2; + cy = h / 2; /* * Construct the unshuffled grid. @@ -410,14 +357,14 @@ static game_state *new_game(game_params *params, char *seed) */ possibilities = newtree234(xyd_cmp); - if (state->cx+1 < state->width) - add234(possibilities, new_xyd(state->cx, state->cy, R)); - if (state->cy-1 >= 0) - add234(possibilities, new_xyd(state->cx, state->cy, U)); - if (state->cx-1 >= 0) - add234(possibilities, new_xyd(state->cx, state->cy, L)); - if (state->cy+1 < state->height) - add234(possibilities, new_xyd(state->cx, state->cy, D)); + if (cx+1 < w) + add234(possibilities, new_xyd(cx, cy, R)); + if (cy-1 >= 0) + add234(possibilities, new_xyd(cx, cy, U)); + if (cx-1 >= 0) + add234(possibilities, new_xyd(cx, cy, L)); + if (cy+1 < h) + add234(possibilities, new_xyd(cx, cy, D)); while (count234(possibilities) > 0) { int i; @@ -434,7 +381,7 @@ static game_state *new_game(game_params *params, char *seed) d1 = xyd->direction; sfree(xyd); - OFFSET(x2, y2, x1, y1, d1, state); + OFFSET(x2, y2, x1, y1, d1, params); d2 = F(d1); #ifdef DEBUG printf("picked (%d,%d,%c) <-> (%d,%d,%c)\n", @@ -445,20 +392,20 @@ static game_state *new_game(game_params *params, char *seed) * Make the connection. (We should be moving to an as yet * unused tile.) */ - tile(state, x1, y1) |= d1; - assert(tile(state, x2, y2) == 0); - tile(state, x2, y2) |= d2; + index(params, tiles, x1, y1) |= d1; + assert(index(params, tiles, x2, y2) == 0); + index(params, tiles, x2, y2) |= d2; /* * If we have created a T-piece, remove its last * possibility. */ - if (COUNT(tile(state, x1, y1)) == 3) { + if (COUNT(index(params, tiles, x1, y1)) == 3) { struct xyd xyd1, *xydp; xyd1.x = x1; xyd1.y = y1; - xyd1.direction = 0x0F ^ tile(state, x1, y1); + xyd1.direction = 0x0F ^ index(params, tiles, x1, y1); xydp = find234(possibilities, &xyd1, NULL); @@ -480,7 +427,7 @@ static game_state *new_game(game_params *params, char *seed) int x3, y3, d3; struct xyd xyd1, *xydp; - OFFSET(x3, y3, x2, y2, d, state); + OFFSET(x3, y3, x2, y2, d, params); d3 = F(d); xyd1.x = x3; @@ -509,20 +456,20 @@ static game_state *new_game(game_params *params, char *seed) if (d == d2) continue; /* we've got this one already */ - if (!state->wrapping) { + if (!params->wrapping) { if (d == U && y2 == 0) continue; - if (d == D && y2 == state->height-1) + if (d == D && y2 == h-1) continue; if (d == L && x2 == 0) continue; - if (d == R && x2 == state->width-1) + if (d == R && x2 == w-1) continue; } - OFFSET(x3, y3, x2, y2, d, state); + OFFSET(x3, y3, x2, y2, d, params); - if (tile(state, x3, y3)) + if (index(params, tiles, x3, y3)) continue; /* this would create a loop */ #ifdef DEBUG @@ -539,34 +486,49 @@ static game_state *new_game(game_params *params, char *seed) /* * Now compute a list of the possible barrier locations. */ - barriers = newtree234(xyd_cmp); - for (y = 0; y < state->height; y++) { - for (x = 0; x < state->width; x++) { - - if (!(tile(state, x, y) & R) && - (state->wrapping || x < state->width-1)) - add234(barriers, new_xyd(x, y, R)); - if (!(tile(state, x, y) & D) && - (state->wrapping || y < state->height-1)) - add234(barriers, new_xyd(x, y, D)); + barriertree = newtree234(xyd_cmp); + for (y = 0; y < h; y++) { + for (x = 0; x < w; x++) { + + if (!(index(params, tiles, x, y) & R) && + (params->wrapping || x < w-1)) + add234(barriertree, new_xyd(x, y, R)); + if (!(index(params, tiles, x, y) & D) && + (params->wrapping || y < h-1)) + add234(barriertree, new_xyd(x, y, D)); } } /* + * Save the unshuffled grid in an aux_info. + */ + { + game_aux_info *solution; + + solution = snew(game_aux_info); + solution->width = w; + solution->height = h; + solution->tiles = snewn(w * h, unsigned char); + memcpy(solution->tiles, tiles, w * h); + + *aux = solution; + } + + /* * Now shuffle the grid. */ - for (y = 0; y < state->height; y++) { - for (x = 0; x < state->width; x++) { - int orig = tile(state, x, y); + for (y = 0; y < h; y++) { + for (x = 0; x < w; x++) { + int orig = index(params, tiles, x, y); int rot = random_upto(rs, 4); - tile(state, x, y) = ROT(orig, rot); + index(params, tiles, x, y) = ROT(orig, rot); } } /* * And now choose barrier locations. (We carefully do this * _after_ shuffling, so that changing the barrier rate in the - * params while keeping the game seed the same will give the + * params while keeping the random seed the same will give the * same shuffled grid and _only_ change the barrier locations. * Also the way we choose barrier locations, by repeatedly * choosing one possibility from the list until we have enough, @@ -577,8 +539,8 @@ static game_state *new_game(game_params *params, char *seed) * the original 10 plus 10 more, rather than getting 20 new * ones and the chance of remembering your first 10.) */ - nbarriers = (int)(params->barrier_probability * count234(barriers)); - assert(nbarriers >= 0 && nbarriers <= count234(barriers)); + nbarriers = (int)(params->barrier_probability * count234(barriertree)); + assert(nbarriers >= 0 && nbarriers <= count234(barriertree)); while (nbarriers > 0) { int i; @@ -588,8 +550,8 @@ static game_state *new_game(game_params *params, char *seed) /* * Extract a randomly chosen barrier from the list. */ - i = random_upto(rs, count234(barriers)); - xyd = delpos234(barriers, i); + i = random_upto(rs, count234(barriertree)); + xyd = delpos234(barriertree, i); assert(xyd != NULL); @@ -598,11 +560,11 @@ static game_state *new_game(game_params *params, char *seed) d1 = xyd->direction; sfree(xyd); - OFFSET(x2, y2, x1, y1, d1, state); + OFFSET(x2, y2, x1, y1, d1, params); d2 = F(d1); - barrier(state, x1, y1) |= d1; - barrier(state, x2, y2) |= d2; + index(params, barriers, x1, y1) |= d1; + index(params, barriers, x2, y2) |= d2; nbarriers--; } @@ -613,10 +575,147 @@ static game_state *new_game(game_params *params, char *seed) { struct xyd *xyd; - while ( (xyd = delpos234(barriers, 0)) != NULL) + while ( (xyd = delpos234(barriertree, 0)) != NULL) sfree(xyd); - freetree234(barriers); + freetree234(barriertree); + } + + /* + * Finally, encode the grid into a string game description. + * + * My syntax is extremely simple: each square is encoded as a + * hex digit in which bit 0 means a connection on the right, + * bit 1 means up, bit 2 left and bit 3 down. (i.e. the same + * encoding as used internally). Each digit is followed by + * optional barrier indicators: `v' means a vertical barrier to + * the right of it, and `h' means a horizontal barrier below + * it. + */ + desc = snewn(w * h * 3 + 1, char); + p = desc; + for (y = 0; y < h; y++) { + for (x = 0; x < w; x++) { + *p++ = "0123456789abcdef"[index(params, tiles, x, y)]; + if ((params->wrapping || x < w-1) && + (index(params, barriers, x, y) & R)) + *p++ = 'v'; + if ((params->wrapping || y < h-1) && + (index(params, barriers, x, y) & D)) + *p++ = 'h'; + } + } + assert(p - desc <= w*h*3); + + sfree(tiles); + sfree(barriers); + + return desc; +} + +static void game_free_aux_info(game_aux_info *aux) +{ + sfree(aux->tiles); + sfree(aux); +} + +static char *validate_desc(game_params *params, char *desc) +{ + int w = params->width, h = params->height; + int i; + + for (i = 0; i < w*h; i++) { + if (*desc >= '0' && *desc <= '9') + /* OK */; + else if (*desc >= 'a' && *desc <= 'f') + /* OK */; + else if (*desc >= 'A' && *desc <= 'F') + /* OK */; + else if (!*desc) + return "Game description shorter than expected"; + else + return "Game description contained unexpected character"; + desc++; + while (*desc == 'h' || *desc == 'v') + desc++; + } + if (*desc) + return "Game description longer than expected"; + + return NULL; +} + +/* ---------------------------------------------------------------------- + * Construct an initial game state, given a description and parameters. + */ + +static game_state *new_game(game_params *params, char *desc) +{ + game_state *state; + int w, h, x, y; + + assert(params->width > 0 && params->height > 0); + assert(params->width > 1 || params->height > 1); + + /* + * Create a blank game state. + */ + state = snew(game_state); + w = state->width = params->width; + h = state->height = params->height; + state->cx = state->width / 2; + state->cy = state->height / 2; + state->wrapping = params->wrapping; + state->last_rotate_dir = state->last_rotate_x = state->last_rotate_y = 0; + state->completed = state->used_solve = state->just_used_solve = FALSE; + state->tiles = snewn(state->width * state->height, unsigned char); + memset(state->tiles, 0, state->width * state->height); + state->barriers = snewn(state->width * state->height, unsigned char); + memset(state->barriers, 0, state->width * state->height); + + /* + * Parse the game description into the grid. + */ + for (y = 0; y < h; y++) { + for (x = 0; x < w; x++) { + if (*desc >= '0' && *desc <= '9') + tile(state, x, y) = *desc - '0'; + else if (*desc >= 'a' && *desc <= 'f') + tile(state, x, y) = *desc - 'a' + 10; + else if (*desc >= 'A' && *desc <= 'F') + tile(state, x, y) = *desc - 'A' + 10; + if (*desc) + desc++; + while (*desc == 'h' || *desc == 'v') { + int x2, y2, d1, d2; + if (*desc == 'v') + d1 = R; + else + d1 = D; + + OFFSET(x2, y2, x, y, d1, state); + d2 = F(d1); + + barrier(state, x, y) |= d1; + barrier(state, x2, y2) |= d2; + + desc++; + } + } + } + + /* + * Set up border barriers if this is a non-wrapping game. + */ + if (!state->wrapping) { + for (x = 0; x < state->width; x++) { + barrier(state, x, 0) |= U; + barrier(state, x, state->height-1) |= D; + } + for (y = 0; y < state->height; y++) { + barrier(state, 0, y) |= L; + barrier(state, state->width-1, y) |= R; + } } /* @@ -667,8 +766,6 @@ static game_state *new_game(game_params *params, char *seed) } } - random_free(rs); - return state; } @@ -683,7 +780,11 @@ static game_state *dup_game(game_state *state) ret->cy = state->cy; ret->wrapping = state->wrapping; ret->completed = state->completed; + ret->used_solve = state->used_solve; + ret->just_used_solve = state->just_used_solve; ret->last_rotate_dir = state->last_rotate_dir; + ret->last_rotate_x = state->last_rotate_x; + ret->last_rotate_y = state->last_rotate_y; ret->tiles = snewn(state->width * state->height, unsigned char); memcpy(ret->tiles, state->tiles, state->width * state->height); ret->barriers = snewn(state->width * state->height, unsigned char); @@ -699,6 +800,26 @@ static void free_game(game_state *state) sfree(state); } +static game_state *solve_game(game_state *state, game_aux_info *aux, + char **error) +{ + game_state *ret; + + if (!aux) { + *error = "Solution not known for this puzzle"; + return NULL; + } + + assert(aux->width == state->width); + assert(aux->height == state->height); + ret = dup_game(state); + memcpy(ret->tiles, aux->tiles, ret->width * ret->height); + ret->used_solve = ret->just_used_solve = TRUE; + ret->completed = TRUE; + + return ret; +} + static char *game_text_format(game_state *state) { return NULL; @@ -871,8 +992,9 @@ static game_state *make_move(game_state *state, game_ui *ui, if (button == MIDDLE_BUTTON) { ret = dup_game(state); + ret->just_used_solve = FALSE; tile(ret, tx, ty) ^= LOCKED; - ret->last_rotate_dir = 0; + ret->last_rotate_dir = ret->last_rotate_x = ret->last_rotate_y = 0; return ret; } else if (button == LEFT_BUTTON || button == RIGHT_BUTTON) { @@ -889,6 +1011,7 @@ static game_state *make_move(game_state *state, game_ui *ui, * turns anticlockwise; right button turns clockwise. */ ret = dup_game(state); + ret->just_used_solve = FALSE; orig = tile(ret, tx, ty); if (button == LEFT_BUTTON) { tile(ret, tx, ty) = A(orig); @@ -897,6 +1020,8 @@ static game_state *make_move(game_state *state, game_ui *ui, tile(ret, tx, ty) = C(orig); ret->last_rotate_dir = -1; } + ret->last_rotate_x = tx; + ret->last_rotate_y = ty; } else if (button == 'J') { @@ -905,6 +1030,7 @@ static game_state *make_move(game_state *state, game_ui *ui, */ int jx, jy; ret = dup_game(state); + ret->just_used_solve = FALSE; for (jy = 0; jy < ret->height; jy++) { for (jx = 0; jx < ret->width; jx++) { if (!(tile(ret, jx, jy) & LOCKED)) { @@ -915,6 +1041,7 @@ static game_state *make_move(game_state *state, game_ui *ui, } } ret->last_rotate_dir = 0; /* suppress animation */ + ret->last_rotate_x = ret->last_rotate_y = 0; } else assert(0); @@ -928,7 +1055,7 @@ static game_state *make_move(game_state *state, game_ui *ui, for (x1 = 0; x1 < ret->width; x1++) for (y1 = 0; y1 < ret->height; y1++) - if (!index(ret, active, x1, y1)) { + if ((tile(ret, x1, y1) & 0xF) && !index(ret, active, x1, y1)) { complete = FALSE; goto break_label; /* break out of two loops at once */ } @@ -1349,23 +1476,15 @@ static void game_redraw(frontend *fe, game_drawstate *ds, game_state *oldstate, state->last_rotate_dir; if (oldstate && (t < ROTATE_TIME) && last_rotate_dir) { /* - * We're animating a single tile rotation. Find the turning tile, - * if any. + * We're animating a single tile rotation. Find the turning + * tile. */ - for (x = 0; x < oldstate->width; x++) - for (y = 0; y < oldstate->height; y++) - if ((tile(oldstate, x, y) ^ tile(state, x, y)) & 0xF) { - tx = x, ty = y; - goto break_label; /* leave both loops at once */ - } - break_label: - - if (tx >= 0) { - angle = last_rotate_dir * dir * 90.0F * (t / ROTATE_TIME); - state = oldstate; - } + tx = (dir==-1 ? oldstate->last_rotate_x : state->last_rotate_x); + ty = (dir==-1 ? oldstate->last_rotate_y : state->last_rotate_y); + angle = last_rotate_dir * dir * 90.0F * (t / ROTATE_TIME); + state = oldstate; } - + frame = -1; if (ft > 0) { /* @@ -1422,15 +1541,19 @@ static void game_redraw(frontend *fe, game_drawstate *ds, game_state *oldstate, */ { char statusbuf[256]; - int i, n, a; + int i, n, n2, a; n = state->width * state->height; - for (i = a = 0; i < n; i++) + for (i = a = n2 = 0; i < n; i++) { if (active[i]) a++; + if (state->tiles[i] & 0xF) + n2++; + } sprintf(statusbuf, "%sActive: %d/%d", - (state->completed ? "COMPLETED! " : ""), a, n); + (state->used_solve ? "Auto-solved. " : + state->completed ? "COMPLETED! " : ""), a, n2); status_bar(fe, statusbuf); } @@ -1441,26 +1564,22 @@ static void game_redraw(frontend *fe, game_drawstate *ds, game_state *oldstate, static float game_anim_length(game_state *oldstate, game_state *newstate, int dir) { - int x, y, last_rotate_dir; + int last_rotate_dir; + + /* + * Don't animate an auto-solve move. + */ + if ((dir > 0 && newstate->just_used_solve) || + (dir < 0 && oldstate->just_used_solve)) + return 0.0F; /* * Don't animate if last_rotate_dir is zero. */ last_rotate_dir = dir==-1 ? oldstate->last_rotate_dir : newstate->last_rotate_dir; - if (last_rotate_dir) { - - /* - * If there's a tile which has been rotated, allow time to - * animate its rotation. - */ - for (x = 0; x < oldstate->width; x++) - for (y = 0; y < oldstate->height; y++) - if ((tile(oldstate, x, y) ^ tile(newstate, x, y)) & 0xF) { - return ROTATE_TIME; - } - - } + if (last_rotate_dir) + return ROTATE_TIME; return 0.0F; } @@ -1472,7 +1591,8 @@ static float game_flash_length(game_state *oldstate, * If the game has just been completed, we display a completion * flash. */ - if (!oldstate->completed && newstate->completed) { + if (!oldstate->completed && newstate->completed && + !oldstate->used_solve && !newstate->used_solve) { int size; size = 0; if (size < newstate->cx+1) @@ -1508,11 +1628,13 @@ const struct game thegame = { dup_params, TRUE, game_configure, custom_params, validate_params, - new_game_seed, - validate_seed, + new_game_desc, + game_free_aux_info, + validate_desc, new_game, dup_game, free_game, + TRUE, solve_game, FALSE, game_text_format, new_ui, free_ui,