* 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 <stdio.h>
struct game_params {
int w, h;
+ int maxmoves;
};
struct game_immutable_state {
{
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)
*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;
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;
}
}
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);
}
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;
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;
}
ret->w = atoi(cfg[0].sval);
ret->h = atoi(cfg[1].sval);
+ ret->maxmoves = atoi(cfg[2].sval);
return ret;
}
* 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;
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));
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;
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.)
* See if the board is already soluble.
*/
if ((moves = solve_board(w, h, board, forcefield,
- tx, ty)) >= 0)
+ tx, ty, movelimit)) >= 0)
goto soluble;
/*
/*
* 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);
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.
} 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]);
}
}
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);
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);
~mdw / sgt / puzzles / blobdiff