char *errors; /* size w*h: errors detected */
char *marks; /* size w*h: 'no line here' marks placed. */
int completed, used_solve;
- int loop_length; /* filled in by check_completion when complete. */
};
#define DEFAULT_PRESET 3
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 buf[256];
sprintf(buf, "%dx%d", params->w, params->h);
return dupstr(buf);
}
-static config_item *game_configure(game_params *params)
+static config_item *game_configure(const game_params *params)
{
config_item *ret;
char buf[64];
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->w < 5) return "Width must be at least five";
if (params->h < 5) return "Height must be at least five";
#endif
}
-static int new_clues(game_params *params, random_state *rs,
+static int new_clues(const game_params *params, random_state *rs,
char *clues, char *grid)
{
int w = params->w, h = params->h, diff = params->difficulty;
return ngen;
}
-static char *new_game_desc(game_params *params, random_state *rs,
+static char *new_game_desc(const game_params *params, random_state *rs,
char **aux, int interactive)
{
char *grid, *clues;
return desc;
}
-static char *validate_desc(game_params *params, char *desc)
+static char *validate_desc(const game_params *params, const char *desc)
{
int i, sizesofar;
const int totalsize = params->w * params->h;
return NULL;
}
-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 = snew(game_state);
int i, j, sz = params->w*params->h;
return state;
}
-static game_state *dup_game(game_state *state)
+static game_state *dup_game(const game_state *state)
{
game_state *ret = snew(game_state);
int sz = state->shared->sz, i;
#define ERROR_CLUE 16
-static void dsf_update_completion(game_state *state, int *loopclass,
- int ax, int ay, char dir,
- int *dsf, int *dsfsize)
+static void dsf_update_completion(game_state *state, int ax, int ay, char dir,
+ int *dsf)
{
int w = state->shared->w /*, h = state->shared->h */;
- int ac = ay*w+ax, ae, bx, by, bc, be;
+ int ac = ay*w+ax, bx, by, bc;
if (!(state->lines[ac] & dir)) return; /* no link */
bx = ax + DX(dir); by = ay + DY(dir);
assert(INGRID(state, bx, by)); /* should not have a link off grid */
bc = by*w+bx;
-#if 0
assert(state->lines[bc] & F(dir)); /* should have reciprocal link */
-#endif
- /* TODO put above assertion back in once we stop generating partially
- * soluble puzzles. */
if (!(state->lines[bc] & F(dir))) return;
- ae = dsf_canonify(dsf, ac);
- be = dsf_canonify(dsf, bc);
-
- if (ae == be) { /* detected a loop! */
- if (*loopclass != -1) /* this is the second loop, doom. */
- return;
- *loopclass = ae;
- } else {
- int size = dsfsize[ae] + dsfsize[be];
- dsf_merge(dsf, ac, bc);
- ae = dsf_canonify(dsf, ac);
- dsfsize[ae] = size;
- }
- return;
+ dsf_merge(dsf, ac, bc);
}
static void check_completion(game_state *state, int mark)
{
int w = state->shared->w, h = state->shared->h, x, y, i, d;
- int had_error = FALSE /*, is_complete = FALSE */, loopclass;
- int *dsf, *dsfsize;
+ int had_error = FALSE;
+ int *dsf, *component_state;
+ int nsilly, nloop, npath, largest_comp, largest_size, total_pathsize;
+ enum { COMP_NONE, COMP_LOOP, COMP_PATH, COMP_SILLY, COMP_EMPTY };
if (mark) {
for (i = 0; i < w*h; i++) {
#define ERROR(x,y,e) do { had_error = TRUE; if (mark) state->errors[(y)*w+(x)] |= (e); } while(0)
/*
- * First of all: we should have one single closed loop, passing through all clues.
+ * Analyse the solution into loops, paths and stranger things.
+ * Basic strategy here is all the same as in Loopy - see the big
+ * comment in loopy.c's check_completion() - and for exactly the
+ * same reasons, since Loopy and Pearl have basically the same
+ * form of expected solution.
*/
- dsf = snewn(w*h, int);
- dsfsize = snewn(w*h, int);
- dsf_init(dsf, w*h);
- for (i = 0; i < w*h; i++) dsfsize[i] = 1;
- loopclass = -1;
+ dsf = snew_dsf(w*h);
+ /* Build the dsf. */
for (x = 0; x < w; x++) {
for (y = 0; y < h; y++) {
- dsf_update_completion(state, &loopclass, x, y, R, dsf, dsfsize);
- dsf_update_completion(state, &loopclass, x, y, D, dsf, dsfsize);
+ dsf_update_completion(state, x, y, R, dsf);
+ dsf_update_completion(state, x, y, D, dsf);
}
}
- if (loopclass != -1) {
- /* We have a loop. Check all squares with lines on. */
- for (x = 0; x < w; x++) {
- for (y = 0; y < h; y++) {
- if (state->lines[y*w+x] == BLANK) {
- if (state->shared->clues[y*w+x] != NOCLUE) {
- /* the loop doesn't include this clue square! */
- ERROR(x, y, ERROR_CLUE);
- }
- } else {
- if (dsf_canonify(dsf, y*w+x) != loopclass) {
- /* these lines are not on the loop: mark them as error. */
- ERROR(x, y, state->lines[y*w+x]);
- }
- }
- }
- }
+
+ /* Initialise a state variable for each connected component. */
+ component_state = snewn(w*h, int);
+ for (i = 0; i < w*h; i++) {
+ if (dsf_canonify(dsf, i) == i)
+ component_state[i] = COMP_LOOP;
+ else
+ component_state[i] = COMP_NONE;
}
/*
- * Second: check no clues are contradicted.
+ * Classify components, and mark errors where a square has more
+ * than two line segments.
*/
-
for (x = 0; x < w; x++) {
for (y = 0; y < h; y++) {
int type = state->lines[y*w+x];
- /*
- * Check that no square has more than two line segments.
- */
- if (NBITS(type) > 2) {
+ int degree = NBITS(type);
+ int comp = dsf_canonify(dsf, y*w+x);
+ if (degree > 2) {
ERROR(x,y,type);
+ component_state[comp] = COMP_SILLY;
+ } else if (degree == 0) {
+ component_state[comp] = COMP_EMPTY;
+ } else if (degree == 1) {
+ if (component_state[comp] != COMP_SILLY)
+ component_state[comp] = COMP_PATH;
}
- /*
- * Check that no clues are contradicted. This code is similar to
- * the code that sets up the maximal clue array for any given
- * loop.
- */
+ }
+ }
+
+ /* Count the components, and find the largest sensible one. */
+ nsilly = nloop = npath = 0;
+ total_pathsize = 0;
+ largest_comp = largest_size = -1;
+ for (i = 0; i < w*h; i++) {
+ if (component_state[i] == COMP_SILLY) {
+ nsilly++;
+ } else if (component_state[i] == COMP_PATH) {
+ total_pathsize += dsf_size(dsf, i);
+ npath = 1;
+ } else if (component_state[i] == COMP_LOOP) {
+ int this_size;
+
+ nloop++;
+
+ if ((this_size = dsf_size(dsf, i)) > largest_size) {
+ largest_comp = i;
+ largest_size = this_size;
+ }
+ }
+ }
+ if (largest_size < total_pathsize) {
+ largest_comp = -1; /* means the paths */
+ largest_size = total_pathsize;
+ }
+
+ if (nloop > 0 && nloop + npath > 1) {
+ /*
+ * If there are at least two sensible components including at
+ * least one loop, highlight every sensible component that is
+ * not the largest one.
+ */
+ for (i = 0; i < w*h; i++) {
+ int comp = dsf_canonify(dsf, i);
+ if (component_state[comp] == COMP_PATH)
+ comp = -1; /* part of the 'all paths' quasi-component */
+ if ((component_state[comp] == COMP_PATH &&
+ -1 != largest_comp) ||
+ (component_state[comp] == COMP_LOOP &&
+ comp != largest_comp))
+ ERROR(i%w, i/w, state->lines[i]);
+ }
+ }
+
+ /* Now we've finished with the dsf and component states. The only
+ * thing we'll need to remember later on is whether all edges were
+ * part of a single loop, for which our counter variables
+ * nsilly,nloop,npath are enough. */
+ sfree(component_state);
+ sfree(dsf);
+
+ /*
+ * Check that no clues are contradicted. This code is similar to
+ * the code that sets up the maximal clue array for any given
+ * loop.
+ */
+ for (x = 0; x < w; x++) {
+ for (y = 0; y < h; y++) {
+ int type = state->lines[y*w+x];
if (state->shared->clues[y*w+x] == CORNER) {
/* Supposed to be a corner: will find a contradiction if
* it actually contains a straight line, or if it touches any
}
}
}
- if (!had_error && loopclass != -1) {
- state->completed = TRUE;
- state->loop_length = dsfsize[loopclass];
- } else {
- state->completed = FALSE;
- }
- sfree(dsf);
- sfree(dsfsize);
+ if (nloop == 1 && nsilly == 0 && npath == 0) {
+ /*
+ * If there's exactly one loop (so that the puzzle is at least
+ * potentially complete), we need to ensure it hasn't left any
+ * clue out completely.
+ */
+ for (x = 0; x < w; x++) {
+ for (y = 0; y < h; y++) {
+ if (state->lines[y*w+x] == BLANK) {
+ if (state->shared->clues[y*w+x] != NOCLUE) {
+ /* the loop doesn't include this clue square! */
+ ERROR(x, y, ERROR_CLUE);
+ }
+ }
+ }
+ }
- return;
+ /*
+ * But if not, then we're done!
+ */
+ if (!had_error)
+ state->completed = TRUE;
+ }
}
/* completion check:
* - no clues must be contradicted (highlight clue itself in error if so)
* - if there is a closed loop it must include every line segment laid
* - if there's a smaller closed loop then highlight whole loop as error
- * - no square must have more than 3 lines radiating from centre point
+ * - no square must have more than 2 lines radiating from centre point
* (highlight all lines in that square as error if so)
*/
return move;
}
-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)
{
game_state *solved = dup_game(state);
int i, ret, sz = state->shared->sz;
return move;
}
-static int game_can_format_as_text_now(game_params *params)
+static int game_can_format_as_text_now(const game_params *params)
{
- return FALSE;
+ return TRUE;
}
-static char *game_text_format(game_state *state)
+static char *game_text_format(const game_state *state)
{
- return NULL;
+ int w = state->shared->w, h = state->shared->h, cw = 4, ch = 2;
+ int gw = cw*(w-1) + 2, gh = ch*(h-1) + 1, len = gw * gh, r, c, j;
+ char *board = snewn(len + 1, char);
+
+ assert(board);
+ memset(board, ' ', len);
+
+ for (r = 0; r < h; ++r) {
+ for (c = 0; c < w; ++c) {
+ int i = r*w + c, cell = r*ch*gw + c*cw;
+ board[cell] = "+BW"[(unsigned char)state->shared->clues[i]];
+ if (c < w - 1 && (state->lines[i] & R || state->lines[i+1] & L))
+ memset(board + cell + 1, '-', cw - 1);
+ if (r < h - 1 && (state->lines[i] & D || state->lines[i+w] & U))
+ for (j = 1; j < ch; ++j) board[cell + j*gw] = '|';
+ if (c < w - 1 && (state->marks[i] & R || state->marks[i+1] & L))
+ board[cell + cw/2] = 'x';
+ if (r < h - 1 && (state->marks[i] & D || state->marks[i+w] & U))
+ board[cell + (ch/2 * gw)] = 'x';
+ }
+
+ for (j = 0; j < (r == h - 1 ? 1 : ch); ++j)
+ board[r*ch*gw + (gw - 1) + j*gw] = '\n';
+ }
+
+ board[len] = '\0';
+ return board;
}
struct game_ui {
int cursor_active; /* TRUE iff cursor is shown */
};
-static game_ui *new_ui(game_state *state)
+static game_ui *new_ui(const game_state *state)
{
game_ui *ui = snew(game_ui);
int sz = state->shared->sz;
sfree(ui);
}
-static char *encode_ui(game_ui *ui)
+static char *encode_ui(const game_ui *ui)
{
return NULL;
}
-static void decode_ui(game_ui *ui, char *encoding)
+static void decode_ui(game_ui *ui, const char *encoding)
{
}
-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)
{
}
char *draglines; /* size w*h; lines flipped by current drag */
};
-static void update_ui_drag(game_state *state, game_ui *ui, int gx, int gy)
+static void update_ui_drag(const game_state *state, game_ui *ui,
+ int gx, int gy)
{
int /* sz = state->shared->sz, */ w = state->shared->w;
int i, ox, oy, pos;
* to state newstate, each of which equals either 0 or dir]
* }
*/
-static void interpret_ui_drag(game_state *state, game_ui *ui, int *clearing,
- int i, int *sx, int *sy, int *dx, int *dy,
- int *dir, int *oldstate, int *newstate)
+static void interpret_ui_drag(const game_state *state, const game_ui *ui,
+ int *clearing, int i, int *sx, int *sy,
+ int *dx, int *dy, int *dir,
+ int *oldstate, int *newstate)
{
int w = state->shared->w;
int sp = ui->dragcoords[i], dp = ui->dragcoords[i+1];
}
}
-static char *mark_in_direction(game_state *state, int x, int y, int dir,
- int ismark, char *buf)
+static char *mark_in_direction(const game_state *state, int x, int y, int dir,
+ int primary, char *buf)
{
int w = state->shared->w /*, h = state->shared->h, sz = state->shared->sz */;
int x2 = x + DX(dir);
int y2 = y + DY(dir);
int dir2 = F(dir);
- char ch = ismark ? 'M' : 'F';
+
+ char ch = primary ? 'F' : 'M', *other;
if (!INGRID(state, x, y) || !INGRID(state, x2, y2)) return "";
+
/* disallow laying a mark over a line, or vice versa. */
- if (ismark) {
- if ((state->lines[y*w+x] & dir) || (state->lines[y2*w+x2] & dir2))
- return "";
- } else {
- if ((state->marks[y*w+x] & dir) || (state->marks[y2*w+x2] & dir2))
- return "";
- }
+ other = primary ? state->marks : state->lines;
+ if (other[y*w+x] & dir || other[y2*w+x2] & dir2) return "";
sprintf(buf, "%c%d,%d,%d;%c%d,%d,%d", ch, dir, x, y, ch, dir2, x2, y2);
return dupstr(buf);
(btn) == CURSOR_DOWN ? D : (btn) == CURSOR_UP ? U :\
(btn) == CURSOR_LEFT ? L : R)
-static char *interpret_move(game_state *state, game_ui *ui, 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)
{
int w = state->shared->w, h = state->shared->h /*, sz = state->shared->sz */;
int gx = FROMCOORD(x), gy = FROMCOORD(y), i;
int release = FALSE;
char tmpbuf[80];
+ int shift = button & MOD_SHFT, control = button & MOD_CTRL;
+ button &= ~MOD_MASK;
+
if (IS_MOUSE_DOWN(button)) {
ui->cursor_active = FALSE;
if (IS_MOUSE_RELEASE(button)) release = TRUE;
- if (IS_CURSOR_MOVE(button & ~MOD_MASK)) {
+ if (IS_CURSOR_MOVE(button)) {
if (!ui->cursor_active) {
ui->cursor_active = TRUE;
- } else if (button & (MOD_SHFT | MOD_CTRL)) {
+ } else if (control | shift) {
+ char *move;
if (ui->ndragcoords > 0) return NULL;
ui->ndragcoords = -1;
- return mark_in_direction(state, ui->curx, ui->cury,
- KEY_DIRECTION(button & ~MOD_MASK),
- (button & MOD_SHFT), tmpbuf);
+ move = mark_in_direction(state, ui->curx, ui->cury,
+ KEY_DIRECTION(button), control, tmpbuf);
+ if (control && !shift && *move)
+ move_cursor(button, &ui->curx, &ui->cury, w, h, FALSE);
+ return move;
} else {
move_cursor(button, &ui->curx, &ui->cury, w, h, FALSE);
if (ui->ndragcoords >= 0)
return "";
}
- if (IS_CURSOR_SELECT(button & ~MOD_MASK)) {
+ if (IS_CURSOR_SELECT(button)) {
if (!ui->cursor_active) {
ui->cursor_active = TRUE;
return "";
}
}
+ if (button == 27 || button == '\b') {
+ ui->ndragcoords = -1;
+ return "";
+ }
+
if (release) {
if (ui->ndragcoords > 0) {
/* End of a drag: process the cached line data. */
direction = (x < cx) ? L : R;
}
return mark_in_direction(state, gx, gy, direction,
- (button == RIGHT_RELEASE), tmpbuf);
+ (button == LEFT_RELEASE), tmpbuf);
}
}
}
return NULL;
}
-static game_state *execute_move(game_state *state, char *move)
+static game_state *execute_move(const game_state *state, const char *move)
{
int w = state->shared->w, h = state->shared->h;
char c;
#define FLASH_TIME 0.5F
-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)
{
/* Ick: fake up `ds->tilesize' for macro expansion purposes */
struct { int halfsz; } ads, *ds = &ads;
}
static void game_set_size(drawing *dr, game_drawstate *ds,
- game_params *params, int tilesize)
+ const game_params *params, int tilesize)
{
ds->halfsz = (tilesize-1)/2;
}
return ret;
}
-static game_drawstate *game_new_drawstate(drawing *dr, game_state *state)
+static game_drawstate *game_new_drawstate(drawing *dr, const game_state *state)
{
struct game_drawstate *ds = snew(struct game_drawstate);
int i;
}
}
-static void draw_square(drawing *dr, game_drawstate *ds, game_ui *ui,
+static void draw_square(drawing *dr, game_drawstate *ds, const game_ui *ui,
int x, int y, unsigned int lflags, char clue)
{
int ox = COORD(x), oy = COORD(y);
draw_update(dr, ox, oy, TILE_SIZE, TILE_SIZE);
}
-static void game_redraw(drawing *dr, game_drawstate *ds, game_state *oldstate,
- game_state *state, int dir, game_ui *ui,
- float animtime, float flashtime)
+static void game_redraw(drawing *dr, game_drawstate *ds,
+ const game_state *oldstate, const game_state *state,
+ int dir, const game_ui *ui,
+ float animtime, float flashtime)
{
int w = state->shared->w, h = state->shared->h, sz = state->shared->sz;
int x, y, force = 0, flashing = 0;
}
}
-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)
{
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 (!oldstate->completed &&
- newstate->completed && !newstate->used_solve)
+ if (!oldstate->completed && newstate->completed &&
+ !oldstate->used_solve && !newstate->used_solve)
return FLASH_TIME;
else
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;
*y = ph / 100.0F;
}
-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->shared->w, h = state->shared->h, x, y;
int black = print_mono_colour(dr, 0);
dup_game,
free_game,
TRUE, solve_game,
- FALSE, game_can_format_as_text_now, game_text_format,
+ TRUE, game_can_format_as_text_now, game_text_format,
new_ui,
free_ui,
encode_ui,
~ian / sgt-puzzles.git / blobdiff