#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) )
COL_ENDPOINT,
COL_POWERED,
COL_BARRIER,
+ COL_LOOP,
NCOLOURS
};
float barrier_probability;
};
+typedef struct game_immutable_state {
+ int refcount;
+ unsigned char *barriers;
+} game_immutable_state;
+
struct game_state {
int width, height, wrapping, completed;
int last_rotate_x, last_rotate_y, last_rotate_dir;
int used_solve;
unsigned char *tiles;
- unsigned char *barriers;
+ struct game_immutable_state *imm;
};
#define OFFSETWH(x2,y2,x1,y1,dir,width,height) \
#define index(state, a, x, y) ( a[(y) * (state)->width + (x)] )
#define tile(state, x, y) index(state, (state)->tiles, x, y)
-#define barrier(state, x, y) index(state, (state)->barriers, x, y)
+#define barrier(state, x, y) index(state, (state)->imm->barriers, x, y)
struct xyd {
int x, y, direction;
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 */
}
}
-static char *encode_params(game_params *params, int full)
+static char *encode_params(const game_params *params, int full)
{
char ret[400];
int len;
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];
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);
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";
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)
{
#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;
/*
* 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;
}
}
sfree(perimeter);
}
+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)
{
/*
* 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;
/*
* 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);
}
}
+ /*
+ * 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
mismatches++;
}
- if (mismatches > 0)
- break;
+ if (mismatches == 0)
+ continue;
+
+ /* OK. */
+ break;
}
/*
return desc;
}
-static char *validate_desc(const 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;
* 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;
w = state->width = params->width;
h = state->height = params->height;
state->wrapping = params->wrapping;
+ state->imm = snew(game_immutable_state);
+ state->imm->refcount = 1;
state->last_rotate_dir = state->last_rotate_x = state->last_rotate_y = 0;
state->completed = state->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);
+ state->imm->barriers = snewn(state->width * state->height, unsigned char);
+ memset(state->imm->barriers, 0, state->width * state->height);
/*
* Parse the game description into the grid.
return state;
}
-static game_state *dup_game(game_state *state)
+static game_state *dup_game(const game_state *state)
{
game_state *ret;
ret = snew(game_state);
+ ret->imm = state->imm;
+ ret->imm->refcount++;
ret->width = state->width;
ret->height = state->height;
ret->wrapping = state->wrapping;
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);
- memcpy(ret->barriers, state->barriers, state->width * state->height);
return ret;
}
static void free_game(game_state *state)
{
+ if (--state->imm->refcount == 0) {
+ sfree(state->imm->barriers);
+ sfree(state->imm);
+ }
sfree(state->tiles);
- sfree(state->barriers);
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;
* 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->imm->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];
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;
}
* 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;
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->imm->barriers);
+}
+
struct game_ui {
int org_x, org_y; /* origin */
int cx, cy; /* source tile (game coordinates) */
#endif
};
-static game_ui *new_ui(game_state *state)
+static game_ui *new_ui(const game_state *state)
{
void *seed;
int seedsize;
sfree(ui);
}
-static char *encode_ui(game_ui *ui)
+static char *encode_ui(const game_ui *ui)
{
char buf[120];
/*
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)
{
}
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,
- const 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;
}
}
-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;
/*
* 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;
* 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;
}
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;
}
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.
*/
/*
* 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;
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
*/
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
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;
/*
* 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 &&
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;
}
* Update the status bar.
*/
{
- char statusbuf[256];
+ char statusbuf[256], *p;
int i, n, n2, a;
+ int complete = FALSE;
- n = state->width * state->height;
- for (i = a = n2 = 0; i < n; i++) {
- if (active[i])
- a++;
- if (state->tiles[i] & 0xF)
- n2++;
+ p = statusbuf;
+ *p = '\0'; /* ensure even an empty status string is terminated */
+
+ 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;
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
return 0.0F;
}
-static int game_status(game_state *state)
+static int game_status(const game_state *state)
{
return state->completed ? +1 : 0;
}
-static int game_timing_state(game_state *state, game_ui *ui)
+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;
}
}
-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);
const struct game thegame = {
"Net", "games.net", "net",
default_params,
- game_fetch_preset,
+ game_fetch_preset, NULL,
decode_params,
encode_params,
free_params,
~ian / sgt-puzzles.git / blobdiff