X-Git-Url: http://www.chiark.greenend.org.uk/ucgi/~ian/git?a=blobdiff_plain;f=pearl.c;h=c6c305f3f22a477d69e177b78770ef04b590d588;hb=a0a581c8b5422bf0c5ed3fde6aa25811e4eb89fc;hp=967059290185e218cc925ca5acf4784ac38949de;hpb=3b250baa02a7332510685948bf17576c397b8ceb;p=sgt-puzzles.git diff --git a/pearl.c b/pearl.c index 9670592..c6c305f 100644 --- a/pearl.c +++ b/pearl.c @@ -130,7 +130,6 @@ struct game_state { 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 @@ -180,7 +179,7 @@ static void free_params(game_params *params) 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 */ @@ -214,7 +213,7 @@ static void decode_params(game_params *ret, char const *string) } } -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); @@ -225,7 +224,7 @@ static char *encode_params(game_params *params, int full) 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]; @@ -262,7 +261,7 @@ static config_item *game_configure(game_params *params) 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); @@ -274,7 +273,7 @@ static game_params *custom_params(config_item *cfg) 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"; @@ -1158,7 +1157,7 @@ void pearl_loopgen(int w, int h, char *lines, random_state *rs) #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; @@ -1356,7 +1355,7 @@ static int new_clues(game_params *params, random_state *rs, 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; @@ -1393,7 +1392,7 @@ static char *new_game_desc(game_params *params, random_state *rs, 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; @@ -1416,7 +1415,8 @@ static char *validate_desc(game_params *params, char *desc) 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; @@ -1452,7 +1452,7 @@ static game_state *new_game(midend *me, game_params *params, char *desc) 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; @@ -1495,12 +1495,11 @@ static char nbits[16] = { 0, 1, 1, 2, #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); @@ -1508,34 +1507,19 @@ static void dsf_update_completion(game_state *state, int *loopclass, 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++) { @@ -1546,57 +1530,109 @@ static void check_completion(game_state *state, int mark) #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 && + -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 @@ -1637,17 +1673,30 @@ static void check_completion(game_state *state, int mark) } } } - 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: @@ -1655,7 +1704,7 @@ static void check_completion(game_state *state, int mark) * - 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) */ @@ -1676,8 +1725,8 @@ static char *solve_for_diff(game_state *state, char *old_lines, char *new_lines) 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; @@ -1721,14 +1770,40 @@ done: 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 { @@ -1741,7 +1816,7 @@ 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; @@ -1760,17 +1835,17 @@ static void free_ui(game_ui *ui) 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) { } @@ -1820,7 +1895,8 @@ struct game_drawstate { 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; @@ -1904,9 +1980,10 @@ static void update_ui_drag(game_state *state, game_ui *ui, int gx, int gy) * 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]; @@ -1935,24 +2012,21 @@ static void interpret_ui_drag(game_state *state, game_ui *ui, int *clearing, } } -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); @@ -1962,14 +2036,18 @@ static char *mark_in_direction(game_state *state, int x, int y, int dir, (btn) == CURSOR_DOWN ? D : (btn) == CURSOR_UP ? U :\ (btn) == CURSOR_LEFT ? L : R) -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) { 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; @@ -1992,15 +2070,18 @@ static char *interpret_move(game_state *state, game_ui *ui, const game_drawstate 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) @@ -2009,7 +2090,7 @@ static char *interpret_move(game_state *state, game_ui *ui, const game_drawstate return ""; } - if (IS_CURSOR_SELECT(button & ~MOD_MASK)) { + if (IS_CURSOR_SELECT(button)) { if (!ui->cursor_active) { ui->cursor_active = TRUE; return ""; @@ -2027,6 +2108,11 @@ static char *interpret_move(game_state *state, game_ui *ui, const game_drawstate } } + if (button == 27 || button == '\b') { + ui->ndragcoords = -1; + return ""; + } + if (release) { if (ui->ndragcoords > 0) { /* End of a drag: process the cached line data. */ @@ -2093,7 +2179,7 @@ static char *interpret_move(game_state *state, game_ui *ui, const game_drawstate direction = (x < cx) ? L : R; } return mark_in_direction(state, gx, gy, direction, - (button == RIGHT_RELEASE), tmpbuf); + (button == LEFT_RELEASE), tmpbuf); } } } @@ -2104,7 +2190,7 @@ static char *interpret_move(game_state *state, game_ui *ui, const game_drawstate 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; @@ -2179,8 +2265,8 @@ badmove: #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; @@ -2191,7 +2277,7 @@ static void game_compute_size(game_params *params, int tilesize, } 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; } @@ -2230,7 +2316,7 @@ static float *game_colours(frontend *fe, int *ncolours) 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; @@ -2289,7 +2375,7 @@ static void draw_lines_specific(drawing *dr, game_drawstate *ds, } } -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); @@ -2366,9 +2452,10 @@ static void draw_square(drawing *dr, game_drawstate *ds, game_ui *ui, 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; @@ -2441,33 +2528,33 @@ static void game_redraw(drawing *dr, game_drawstate *ds, game_state *oldstate, } } -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; @@ -2479,7 +2566,7 @@ static void game_print_size(game_params *params, float *x, float *y) *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); @@ -2521,7 +2608,7 @@ static void game_print(drawing *dr, game_state *state, int tilesize) const struct game thegame = { "Pearl", "games.pearl", "pearl", default_params, - game_fetch_preset, + game_fetch_preset, NULL, decode_params, encode_params, free_params, @@ -2534,7 +2621,7 @@ const struct game thegame = { 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,