From b83e4849db985a582f5f0cfe4a0e78218a1c594a Mon Sep 17 00:00:00 2001 From: simon Date: Mon, 7 May 2007 19:08:52 +0000 Subject: [PATCH] Add an optional move limit during game generation. git-svn-id: svn://svn.tartarus.org/sgt/puzzles@7554 cda61777-01e9-0310-a592-d414129be87e --- unfinished/slide.c | 77 +++++++++++++++++++++++++++++++++++------------------- 1 file changed, 50 insertions(+), 27 deletions(-) diff --git a/unfinished/slide.c b/unfinished/slide.c index 130c7b9..58bd6eb 100644 --- a/unfinished/slide.c +++ b/unfinished/slide.c @@ -23,17 +23,8 @@ * 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. - * * but adjust the presets, because 8x6 is _slow_ to - * generate. - * * also, introduce a difficulty scheme, in the form of - * limiting the minimum move count. This is obviously - * sensible, because it also speeds up generation since the - * solver can bomb out once it hits that ceiling! - * + I was going to say I'd need to work out a minimum move - * count for each grid size, but actually I think not: if - * you ask for too few moves, it just has to remove still - * more singletons, until at move count 1 you end up with - * nothing in your way at all and it SERVES YOU RIGHT! + * * the move limit tends to make the game _slower_ to + * generate, which is odd. Perhaps investigate why. * * - Improve the graphics. * * All the colours are a bit wishy-washy. _Some_ dark @@ -140,6 +131,7 @@ enum { struct game_params { int w, h; + int maxmoves; }; struct game_immutable_state { @@ -162,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) @@ -187,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; @@ -212,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; } } @@ -220,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); } @@ -229,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; @@ -243,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; } @@ -257,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; } @@ -389,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; @@ -443,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)); @@ -572,7 +597,7 @@ 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; @@ -628,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; /* @@ -678,9 +703,7 @@ static void generate_board(int w, int h, int *rtx, int *rty, int *minmoves, c1 = dsf_canonify(dsf, p1); c2 = dsf_canonify(dsf, p2); if (tried_merge[c1 * wh + c2]) -{printf("aha\n"); continue; -} /* * In order to be mergeable, these two squares must each @@ -730,7 +753,7 @@ 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. @@ -776,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); -- 2.11.0