X-Git-Url: https://git.distorted.org.uk/~mdw/sgt/puzzles/blobdiff_plain/ac511ec9c1cd34babf973d3615abd30169c11050..b83e4849db985a582f5f0cfe4a0e78218a1c594a:/unfinished/slide.c diff --git a/unfinished/slide.c b/unfinished/slide.c index c9afe41..58bd6eb 100644 --- a/unfinished/slide.c +++ b/unfinished/slide.c @@ -17,11 +17,22 @@ * cases. * * - Improve the generator. + * * actually, we seem to be mostly sensible already now. I + * want more choice over the type of main block and location + * of the exit/target, and I think I probably ought to give + * up on compactness and just bite the bullet and have the + * target area right outside the main wall, but mostly I + * think it's OK. + * * the move limit tends to make the game _slower_ to + * generate, which is odd. Perhaps investigate why. * - * - All the colours are a bit wishy-washy. _Some_ dark colours - * would surely not be excessive? Probably darken the tiles, - * the walls and the main block, and leave the target marker - * pale. + * - Improve the graphics. + * * All the colours are a bit wishy-washy. _Some_ dark + * colours would surely not be excessive? Probably darken + * the tiles, the walls and the main block, and leave the + * target marker pale. + * * The cattle grid effect is still disgusting. Think of + * something completely different. */ #include @@ -120,6 +131,7 @@ enum { struct game_params { int w, h; + int maxmoves; }; struct game_immutable_state { @@ -142,17 +154,17 @@ static game_params *default_params(void) { game_params *ret = snew(game_params); - ret->w = 8; + ret->w = 7; ret->h = 6; + ret->maxmoves = 40; return ret; } static const struct game_params slide_presets[] = { - {6, 5}, - {7, 5}, - {7, 6}, - {8, 6}, + {7, 6, 25}, + {7, 6, -1}, + {8, 6, -1}, }; static int game_fetch_preset(int i, char **name, game_params **params) @@ -167,6 +179,10 @@ static int game_fetch_preset(int i, char **name, game_params **params) *ret = slide_presets[i]; sprintf(str, "%dx%d", ret->w, ret->h); + if (ret->maxmoves >= 0) + sprintf(str + strlen(str), ", max %d moves", ret->maxmoves); + else + sprintf(str + strlen(str), ", no move limit"); *name = dupstr(str); *params = ret; @@ -192,6 +208,15 @@ static void decode_params(game_params *params, char const *string) if (*string == 'x') { string++; params->h = atoi(string); + while (*string && isdigit((unsigned char)*string)) string++; + } + if (*string == 'm') { + string++; + params->maxmoves = atoi(string); + while (*string && isdigit((unsigned char)*string)) string++; + } else if (*string == 'u') { + string++; + params->maxmoves = -1; } } @@ -200,6 +225,10 @@ static char *encode_params(game_params *params, int full) char data[256]; sprintf(data, "%dx%d", params->w, params->h); + if (params->maxmoves >= 0) + sprintf(data + strlen(data), "m%d", params->maxmoves); + else + sprintf(data + strlen(data), "u"); return dupstr(data); } @@ -209,7 +238,7 @@ static config_item *game_configure(game_params *params) config_item *ret; char buf[80]; - ret = snewn(3, config_item); + ret = snewn(4, config_item); ret[0].name = "Width"; ret[0].type = C_STRING; @@ -223,11 +252,17 @@ static config_item *game_configure(game_params *params) ret[1].sval = dupstr(buf); ret[1].ival = 0; - ret[2].name = NULL; - ret[2].type = C_END; - ret[2].sval = NULL; + ret[2].name = "Solution length limit"; + ret[2].type = C_STRING; + sprintf(buf, "%d", params->maxmoves); + ret[2].sval = dupstr(buf); ret[2].ival = 0; + ret[3].name = NULL; + ret[3].type = C_END; + ret[3].sval = NULL; + ret[3].ival = 0; + return ret; } @@ -237,6 +272,7 @@ static game_params *custom_params(config_item *cfg) ret->w = atoi(cfg[0].sval); ret->h = atoi(cfg[1].sval); + ret->maxmoves = atoi(cfg[2].sval); return ret; } @@ -369,7 +405,8 @@ static struct board *newboard(int w, int h, unsigned char *data) * as-yet-unprovided parameter. */ static int solve_board(int w, int h, unsigned char *board, - unsigned char *forcefield, int tx, int ty) + unsigned char *forcefield, int tx, int ty, + int movelimit) { int wh = w*h; struct board *b, *b2, *b3; @@ -423,6 +460,14 @@ static int solve_board(int w, int h, unsigned char *board, while ((b = delpos234(queue, 0)) != NULL) { qlen--; + if (movelimit >= 0 && b->dist >= movelimit) { + /* + * The problem is not soluble in under `movelimit' + * moves, so we can quit right now. + */ + b2 = NULL; + goto done; + } if (b->dist != lastdist) { #ifdef SOLVER_DIAGNOSTICS printf("dist %d (%d)\n", b->dist, count234(sorted)); @@ -552,10 +597,12 @@ static int solve_board(int w, int h, unsigned char *board, static void generate_board(int w, int h, int *rtx, int *rty, int *minmoves, random_state *rs, unsigned char **rboard, - unsigned char **rforcefield) + unsigned char **rforcefield, int movelimit) { int wh = w*h; unsigned char *board, *board2, *forcefield; + unsigned char *tried_merge; + int *dsf; int *list, nlist, pos; int tx, ty; int i, j; @@ -575,6 +622,10 @@ static void generate_board(int w, int h, int *rtx, int *rty, int *minmoves, for (i = 0; i < h; i++) board[i*w] = board[i*w+(w-1)] = WALL; + tried_merge = snewn(wh * wh, unsigned char); + memset(tried_merge, 0, wh*wh); + dsf = snew_dsf(wh); + /* * Invent a main piece at one extreme. (FIXME: vary the * extreme, and the piece.) @@ -602,7 +653,7 @@ static void generate_board(int w, int h, int *rtx, int *rty, int *minmoves, * See if the board is already soluble. */ if ((moves = solve_board(w, h, board, forcefield, - tx, ty)) >= 0) + tx, ty, movelimit)) >= 0) goto soluble; /* @@ -628,19 +679,11 @@ static void generate_board(int w, int h, int *rtx, int *rty, int *minmoves, /* * Now go through that list in random order, trying to merge * the blocks on each side of each edge. - * - * FIXME: this seems to produce unpleasantly unbalanced - * results. Perhaps we'd do better if we always tried to - * combine the _smallest_ block with something? - * - * FIXME: also one reason it's slow might be because we aren't - * tracking which blocks we've already tried to merge, when - * another edge ends up linking the same ones. */ shuffle(list, nlist, sizeof(*list), rs); while (nlist > 0) { - int x1, y1, p1; - int x2, y2, p2; + int x1, y1, p1, c1; + int x2, y2, p2, c2; pos = list[--nlist]; y1 = y2 = pos / (w*2); @@ -653,6 +696,16 @@ static void generate_board(int w, int h, int *rtx, int *rty, int *minmoves, p2 = y2*w+x2; /* + * Immediately abandon the attempt if we've already tried + * to merge the same pair of blocks along a different + * edge. + */ + c1 = dsf_canonify(dsf, p1); + c2 = dsf_canonify(dsf, p2); + if (tried_merge[c1 * wh + c2]) + continue; + + /* * In order to be mergeable, these two squares must each * either be, or belong to, a non-main anchor, and their * anchors must also be distinct. @@ -700,14 +753,26 @@ static void generate_board(int w, int h, int *rtx, int *rty, int *minmoves, } while (p2 < wh && board[p2] != DIST(p2-i)); } } - j = solve_board(w, h, board, forcefield, tx, ty); + j = solve_board(w, h, board, forcefield, tx, ty, movelimit); if (j < 0) { /* * Didn't work. Revert the merge. */ memcpy(board, board2, wh); + tried_merge[c1 * wh + c2] = tried_merge[c2 * wh + c1] = TRUE; } else { + int c; + moves = j; + + dsf_merge(dsf, c1, c2); + c = dsf_canonify(dsf, c1); + for (i = 0; i < wh; i++) + tried_merge[c*wh+i] = (tried_merge[c1*wh+i] | + tried_merge[c2*wh+i]); + for (i = 0; i < wh; i++) + tried_merge[i*wh+c] = (tried_merge[i*wh+c1] | + tried_merge[i*wh+c2]); } } @@ -734,7 +799,7 @@ static char *new_game_desc(game_params *params, random_state *rs, int i; generate_board(params->w, params->h, &tx, &ty, &minmoves, rs, - &board, &forcefield); + &board, &forcefield, params->maxmoves); #ifdef GENERATOR_DIAGNOSTICS { char *t = board_text_format(params->w, params->h, board); @@ -1835,7 +1900,7 @@ static void game_redraw(drawing *dr, game_drawstate *ds, game_state *oldstate, sprintf(statusbuf, "%sMoves: %d", (state->completed >= 0 ? "COMPLETED! " : ""), (state->completed >= 0 ? state->completed : state->movecount)); - if (state->minmoves) + if (state->minmoves >= 0) sprintf(statusbuf+strlen(statusbuf), " (min %d)", state->minmoves);