X-Git-Url: https://git.distorted.org.uk/~mdw/sgt/puzzles/blobdiff_plain/26801d29c8305a5cb9bd3709909b1eeb896aa3e4..375c9b4d4c8b128dfd09125f4b61f6a00d8af104:/rect.c diff --git a/rect.c b/rect.c index 524d97b..95d1d8c 100644 --- a/rect.c +++ b/rect.c @@ -45,6 +45,7 @@ enum { struct game_params { int w, h; float expandfactor; + int unique; }; #define INDEX(state, x, y) (((y) * (state)->w) + (x)) @@ -59,8 +60,9 @@ struct game_params { #define HRANGE(state,x,y) CRANGE(state,x,y,0,1) #define VRANGE(state,x,y) CRANGE(state,x,y,1,0) -#define TILE_SIZE 24 -#define BORDER 18 +#define PREFERRED_TILE_SIZE 24 +#define TILE_SIZE (ds->tilesize) +#define BORDER (TILE_SIZE * 3 / 4) #define CORNER_TOLERANCE 0.15F #define CENTRE_TOLERANCE 0.15F @@ -84,6 +86,7 @@ static game_params *default_params(void) ret->w = ret->h = 7; ret->expandfactor = 0.0F; + ret->unique = TRUE; return ret; } @@ -96,9 +99,14 @@ static int game_fetch_preset(int i, char **name, game_params **params) switch (i) { case 0: w = 7, h = 7; break; - case 1: w = 11, h = 11; break; - case 2: w = 15, h = 15; break; - case 3: w = 19, h = 19; break; + case 1: w = 9, h = 9; break; + case 2: w = 11, h = 11; break; + case 3: w = 13, h = 13; break; + case 4: w = 15, h = 15; break; +#ifndef SLOW_SYSTEM + case 5: w = 17, h = 17; break; + case 6: w = 19, h = 19; break; +#endif default: return FALSE; } @@ -108,6 +116,7 @@ static int game_fetch_preset(int i, char **name, game_params **params) ret->w = w; ret->h = h; ret->expandfactor = 0.0F; + ret->unique = TRUE; return TRUE; } @@ -135,6 +144,12 @@ static void decode_params(game_params *ret, char const *string) if (*string == 'e') { string++; ret->expandfactor = atof(string); + while (*string && + (*string == '.' || isdigit((unsigned char)*string))) string++; + } + if (*string == 'a') { + string++; + ret->unique = FALSE; } } @@ -145,6 +160,8 @@ static char *encode_params(game_params *params, int full) sprintf(data, "%dx%d", params->w, params->h); if (full && params->expandfactor) sprintf(data + strlen(data), "e%g", params->expandfactor); + if (full && !params->unique) + strcat(data, "a"); return dupstr(data); } @@ -174,10 +191,15 @@ static config_item *game_configure(game_params *params) ret[2].sval = dupstr(buf); ret[2].ival = 0; - ret[3].name = NULL; - ret[3].type = C_END; + ret[3].name = "Ensure unique solution"; + ret[3].type = C_BOOLEAN; ret[3].sval = NULL; - ret[3].ival = 0; + ret[3].ival = params->unique; + + ret[4].name = NULL; + ret[4].type = C_END; + ret[4].sval = NULL; + ret[4].ival = 0; return ret; } @@ -189,15 +211,16 @@ static game_params *custom_params(config_item *cfg) ret->w = atoi(cfg[0].sval); ret->h = atoi(cfg[1].sval); ret->expandfactor = atof(cfg[2].sval); + ret->unique = cfg[3].ival; return ret; } static char *validate_params(game_params *params) { - if (params->w <= 0 && params->h <= 0) + if (params->w <= 0 || params->h <= 0) return "Width and height must both be greater than zero"; - if (params->w < 2 && params->h < 2) + if (params->w*params->h < 2) return "Grid area must be greater than one"; if (params->expandfactor < 0.0F) return "Expansion factor may not be negative"; @@ -304,7 +327,7 @@ static void remove_number_placement(int w, int h, struct numberdata *number, } static int rect_solver(int w, int h, int nrects, struct numberdata *numbers, - random_state *rs) + game_state *result, random_state *rs) { struct rectlist *rectpositions; int *overlaps, *rectbyplace, *workspace; @@ -722,7 +745,7 @@ static int rect_solver(int w, int h, int nrects, struct numberdata *numbers, * rectangle) which overlaps a candidate placement of the * number for some other rectangle. */ - { + if (rs) { struct rpn { int rect; int placement; @@ -827,8 +850,28 @@ static int rect_solver(int w, int h, int nrects, struct numberdata *numbers, i, rectpositions[i].n); #endif assert(rectpositions[i].n > 0); - if (rectpositions[i].n > 1) + if (rectpositions[i].n > 1) { ret = FALSE; + } else if (result) { + /* + * Place the rectangle in its only possible position. + */ + int x, y; + struct rect *r = &rectpositions[i].rects[0]; + + for (y = 0; y < r->h; y++) { + if (r->x > 0) + vedge(result, r->x, r->y+y) = 1; + if (r->x+r->w < result->w) + vedge(result, r->x+r->w, r->y+y) = 1; + } + for (x = 0; x < r->w; x++) { + if (r->y > 0) + hedge(result, r->x+x, r->y) = 1; + if (r->y+r->h < result->h) + hedge(result, r->x+x, r->y+r->h) = 1; + } + } } /* @@ -1017,7 +1060,7 @@ struct game_aux_info { }; static char *new_game_desc(game_params *params, random_state *rs, - game_aux_info **aux) + game_aux_info **aux, int interactive) { int *grid, *numbers = NULL; struct rectlist *list; @@ -1505,7 +1548,11 @@ static char *new_game_desc(game_params *params, random_state *rs, } } - ret = rect_solver(params->w, params->h, nnumbers, nd, rs); + if (params->unique) + ret = rect_solver(params->w, params->h, nnumbers, nd, + NULL, rs); + else + ret = TRUE; /* allow any number placement at all */ if (ret) { /* @@ -1650,7 +1697,7 @@ static char *validate_desc(game_params *params, char *desc) return NULL; } -static game_state *new_game(game_params *params, char *desc) +static game_state *new_game(midend_data *me, game_params *params, char *desc) { game_state *state = snew(game_state); int x, y, i, area; @@ -1728,8 +1775,45 @@ static game_state *solve_game(game_state *state, game_aux_info *ai, game_state *ret; if (!ai) { - *error = "Solution not known for this puzzle"; - return NULL; + int i, j, n; + struct numberdata *nd; + + /* + * Attempt the in-built solver. + */ + + /* Set up each number's (very short) candidate position list. */ + for (i = n = 0; i < state->h * state->w; i++) + if (state->grid[i]) + n++; + + nd = snewn(n, struct numberdata); + + for (i = j = 0; i < state->h * state->w; i++) + if (state->grid[i]) { + nd[j].area = state->grid[i]; + nd[j].npoints = 1; + nd[j].points = snewn(1, struct point); + nd[j].points[0].x = i % state->w; + nd[j].points[0].y = i / state->w; + j++; + } + + assert(j == n); + + ret = dup_game(state); + ret->cheated = TRUE; + + rect_solver(state->w, state->h, n, nd, ret, NULL); + + /* + * Clean up. + */ + for (i = 0; i < n; i++) + sfree(nd[i].points); + sfree(nd); + + return ret; } assert(state->w == ai->w); @@ -1951,6 +2035,14 @@ struct game_ui { * treated as a small drag rather than a click. */ int dragged; + /* + * These are the co-ordinates of the top-left and bottom-right squares + * in the drag box, respectively, or -1 otherwise. + */ + int x1; + int y1; + int x2; + int y2; }; static game_ui *new_ui(game_state *state) @@ -1961,6 +2053,10 @@ static game_ui *new_ui(game_state *state) ui->drag_end_x = -1; ui->drag_end_y = -1; ui->dragged = FALSE; + ui->x1 = -1; + ui->y1 = -1; + ui->x2 = -1; + ui->y2 = -1; return ui; } @@ -2056,20 +2152,11 @@ static void coord_round(float x, float y, int *xr, int *yr) static void ui_draw_rect(game_state *state, game_ui *ui, unsigned char *hedge, unsigned char *vedge, int c) { - int x1, x2, y1, y2, x, y, t; - - x1 = ui->drag_start_x; - x2 = ui->drag_end_x; - if (x2 < x1) { t = x1; x1 = x2; x2 = t; } - - y1 = ui->drag_start_y; - y2 = ui->drag_end_y; - if (y2 < y1) { t = y1; y1 = y2; y2 = t; } - - x1 = x1 / 2; /* rounds down */ - x2 = (x2+1) / 2; /* rounds up */ - y1 = y1 / 2; /* rounds down */ - y2 = (y2+1) / 2; /* rounds up */ + int x, y; + int x1 = ui->x1; + int y1 = ui->y1; + int x2 = ui->x2; + int y2 = ui->y2; /* * Draw horizontal edges of rectangles. @@ -2100,13 +2187,25 @@ static void ui_draw_rect(game_state *state, game_ui *ui, } } -static game_state *make_move(game_state *from, game_ui *ui, - int x, int y, int button) +static void game_changed_state(game_ui *ui, game_state *oldstate, + game_state *newstate) { +} + +struct game_drawstate { + int started; + int w, h, tilesize; + unsigned long *visible; +}; + +static game_state *make_move(game_state *from, game_ui *ui, game_drawstate *ds, + int x, int y, int button) { int xc, yc; int startdrag = FALSE, enddrag = FALSE, active = FALSE; game_state *ret; + button &= ~MOD_MASK; + if (button == LEFT_BUTTON) { startdrag = TRUE; } else if (button == LEFT_RELEASE) { @@ -2127,10 +2226,26 @@ static game_state *make_move(game_state *from, game_ui *ui, } if (xc != ui->drag_end_x || yc != ui->drag_end_y) { + int t; + ui->drag_end_x = xc; ui->drag_end_y = yc; ui->dragged = TRUE; active = TRUE; + + ui->x1 = ui->drag_start_x; + ui->x2 = ui->drag_end_x; + if (ui->x2 < ui->x1) { t = ui->x1; ui->x1 = ui->x2; ui->x2 = t; } + + ui->y1 = ui->drag_start_y; + ui->y2 = ui->drag_end_y; + if (ui->y2 < ui->y1) { t = ui->y1; ui->y1 = ui->y2; ui->y2 = t; } + + ui->x1 = ui->x1 / 2; /* rounds down */ + ui->x2 = (ui->x2+1) / 2; /* rounds up */ + ui->y1 = ui->y1 / 2; /* rounds down */ + ui->y2 = (ui->y2+1) / 2; /* rounds up */ + } ret = NULL; @@ -2182,6 +2297,10 @@ static game_state *make_move(game_state *from, game_ui *ui, ui->drag_start_y = -1; ui->drag_end_x = -1; ui->drag_end_y = -1; + ui->x1 = -1; + ui->y1 = -1; + ui->x2 = -1; + ui->y2 = -1; ui->dragged = FALSE; active = TRUE; } @@ -2198,20 +2317,31 @@ static game_state *make_move(game_state *from, game_ui *ui, * Drawing routines. */ -#define CORRECT 65536 +#define CORRECT (1L<<16) #define COLOUR(k) ( (k)==1 ? COL_LINE : COL_DRAG ) -#define MAX(x,y) ( (x)>(y) ? (x) : (y) ) -#define MAX4(x,y,z,w) ( MAX(MAX(x,y),MAX(z,w)) ) - -struct game_drawstate { - int started; - int w, h; - unsigned int *visible; -}; +#define MAX4(x,y,z,w) ( max(max(x,y),max(z,w)) ) -static void game_size(game_params *params, int *x, int *y) +static void game_size(game_params *params, game_drawstate *ds, + int *x, int *y, int expand) { + int tsx, tsy, ts; + /* + * Each window dimension equals the tile size times 1.5 more + * than the grid dimension (the border is 3/4 the width of the + * tiles). + * + * We must cast to unsigned before multiplying by two, because + * *x might be INT_MAX. + */ + tsx = 2 * (unsigned)*x / (2 * params->w + 3); + tsy = 2 * (unsigned)*y / (2 * params->h + 3); + ts = min(tsx, tsy); + if (expand) + ds->tilesize = ts; + else + ds->tilesize = min(ts, PREFERRED_TILE_SIZE); + *x = params->w * TILE_SIZE + 2*BORDER + 1; *y = params->h * TILE_SIZE + 2*BORDER + 1; } @@ -2254,7 +2384,8 @@ static game_drawstate *game_new_drawstate(game_state *state) ds->started = FALSE; ds->w = state->w; ds->h = state->h; - ds->visible = snewn(ds->w * ds->h, unsigned int); + ds->visible = snewn(ds->w * ds->h, unsigned long); + ds->tilesize = 0; /* not decided yet */ for (i = 0; i < ds->w * ds->h; i++) ds->visible[i] = 0xFFFF; @@ -2267,9 +2398,9 @@ static void game_free_drawstate(game_drawstate *ds) sfree(ds); } -static void draw_tile(frontend *fe, game_state *state, int x, int y, - unsigned char *hedge, unsigned char *vedge, - unsigned char *corners, int correct) +static void draw_tile(frontend *fe, game_drawstate *ds, game_state *state, + int x, int y, unsigned char *hedge, unsigned char *vedge, + unsigned char *corners, int correct) { int cx = COORD(x), cy = COORD(y); char str[80]; @@ -2380,7 +2511,7 @@ static void game_redraw(frontend *fe, game_drawstate *ds, game_state *oldstate, for (x = 0; x < state->w; x++) for (y = 0; y < state->h; y++) { - unsigned int c = 0; + unsigned long c = 0; if (HRANGE(state,x,y)) c |= index(state,hedge,x,y); @@ -2396,33 +2527,55 @@ static void game_redraw(frontend *fe, game_drawstate *ds, game_state *oldstate, if (y+1 < state->h) c |= index(state,corners,x,y+1) << 12; if (x+1 < state->w && y+1 < state->h) - c |= index(state,corners,x+1,y+1) << 14; + /* cast to prevent 2<<14 sign-extending on promotion to long */ + c |= (unsigned long)index(state,corners,x+1,y+1) << 14; if (index(state, correct, x, y) && !flashtime) c |= CORRECT; if (index(ds,ds->visible,x,y) != c) { - draw_tile(fe, state, x, y, hedge, vedge, corners, c & CORRECT); + draw_tile(fe, ds, state, x, y, hedge, vedge, corners, + (c & CORRECT) ? 1 : 0); index(ds,ds->visible,x,y) = c; } } + { + char buf[256]; + + if (ui->x1 >= 0 && ui->y1 >= 0 && + ui->x2 >= 0 && ui->y2 >= 0) { + sprintf(buf, "%dx%d ", + ui->x2-ui->x1, + ui->y2-ui->y1); + } else { + buf[0] = '\0'; + } + + if (state->cheated) + strcat(buf, "Auto-solved."); + else if (state->completed) + strcat(buf, "COMPLETED!"); + + status_bar(fe, buf); + } + if (hedge != state->hedge) { sfree(hedge); sfree(vedge); - } + } sfree(corners); sfree(correct); } static float game_anim_length(game_state *oldstate, - game_state *newstate, int dir) + 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_state *newstate, int dir, game_ui *ui) { if (!oldstate->completed && newstate->completed && !oldstate->cheated && !newstate->cheated) @@ -2432,7 +2585,12 @@ static float game_flash_length(game_state *oldstate, static int game_wants_statusbar(void) { - return FALSE; + return TRUE; +} + +static int game_timing_state(game_state *state) +{ + return TRUE; } #ifdef COMBINED @@ -2459,6 +2617,7 @@ const struct game thegame = { TRUE, game_text_format, new_ui, free_ui, + game_changed_state, make_move, game_size, game_colours, @@ -2468,4 +2627,6 @@ const struct game thegame = { game_anim_length, game_flash_length, game_wants_statusbar, + FALSE, game_timing_state, + 0, /* mouse_priorities */ };