X-Git-Url: https://git.distorted.org.uk/~mdw/sgt/puzzles/blobdiff_plain/6aa6af4c00e72c789d76949d735ccb07da5e47a1..9c63a0112329c153911475b014dfdbf2f36b943c:/rect.c diff --git a/rect.c b/rect.c index c1eaa2c..229ce18 100644 --- a/rect.c +++ b/rect.c @@ -9,18 +9,16 @@ /* * TODO: * - * - Improve on singleton removal by making an aesthetic choice - * about which of the options to take. - * - * - When doing the 3x3 trick in singleton removal, limit the size - * of the generated rectangles in accordance with the max - * rectangle size. - * - * - If we start by sorting the rectlist in descending order - * of area, we might be able to bias our random number - * selection to produce a few large rectangles more often - * than oodles of small ones? Unsure, but might be worth a - * try. + * - Improve singleton removal. + * + It would be nice to limit the size of the generated + * rectangles in accordance with existing constraints such as + * the maximum rectangle size and the one about not + * generating a rectangle the full width or height of the + * grid. + * + This could be achieved by making a less random choice + * about which of the available options to use. + * + Alternatively, we could create our rectangle and then + * split it up. */ #include @@ -60,8 +58,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 @@ -98,9 +97,12 @@ 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; + case 5: w = 17, h = 17; break; + case 6: w = 19, h = 19; break; default: return FALSE; } @@ -212,9 +214,9 @@ static game_params *custom_params(config_item *cfg) 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"; @@ -745,7 +747,7 @@ static int rect_solver(int w, int h, int nrects, struct numberdata *numbers, int placement; int number; } *rpns = NULL; - int nrpns = 0, rpnsize = 0; + size_t nrpns = 0, rpnsize = 0; int j; for (i = 0; i < nrects; i++) { @@ -885,13 +887,26 @@ static int rect_solver(int w, int h, int nrects, struct numberdata *numbers, * Grid generation code. */ -static struct rectlist *get_rectlist(game_params *params, int *grid) +/* + * This function does one of two things. If passed r==NULL, it + * counts the number of possible rectangles which cover the given + * square, and returns it in *n. If passed r!=NULL then it _reads_ + * *n to find an index, counts the possible rectangles until it + * reaches the nth, and writes it into r. + * + * `scratch' is expected to point to an array of 2 * params->w + * ints, used internally as scratch space (and passed in like this + * to avoid re-allocating and re-freeing it every time round a + * tight loop). + */ +static void enum_rects(game_params *params, int *grid, struct rect *r, int *n, + int sx, int sy, int *scratch) { - int rw, rh; - int x, y; - int maxarea; - struct rect *rects = NULL; - int nrects = 0, rectsize = 0; + int rw, rh, mw, mh; + int x, y, dx, dy; + int maxarea, realmaxarea; + int index = 0; + int *top, *bottom; /* * Maximum rectangle area is 1/6 of total grid size, unless @@ -902,43 +917,97 @@ static struct rectlist *get_rectlist(game_params *params, int *grid) if (maxarea < 2) maxarea = 2; - for (rw = 1; rw <= params->w; rw++) - for (rh = 1; rh <= params->h; rh++) { - if (rw * rh > maxarea) + /* + * Scan the grid to find the limits of the region within which + * any rectangle containing this point must fall. This will + * save us trawling the inside of every rectangle later on to + * see if it contains any used squares. + */ + top = scratch; + bottom = scratch + params->w; + for (dy = -1; dy <= +1; dy += 2) { + int *array = (dy == -1 ? top : bottom); + for (dx = -1; dx <= +1; dx += 2) { + for (x = sx; x >= 0 && x < params->w; x += dx) { + array[x] = -2 * params->h * dy; + for (y = sy; y >= 0 && y < params->h; y += dy) { + if (index(params, grid, x, y) == -1 && + (x == sx || dy*y <= dy*array[x-dx])) + array[x] = y; + else + break; + } + } + } + } + + /* + * Now scan again to work out the largest rectangles we can fit + * in the grid, so that we can terminate the following loops + * early once we get down to not having much space left in the + * grid. + */ + realmaxarea = 0; + for (x = 0; x < params->w; x++) { + int x2; + + rh = bottom[x] - top[x] + 1; + if (rh <= 0) + continue; /* no rectangles can start here */ + + dx = (x > sx ? -1 : +1); + for (x2 = x; x2 >= 0 && x2 < params->w; x2 += dx) + if (bottom[x2] < bottom[x] || top[x2] > top[x]) + break; + + rw = abs(x2 - x); + if (realmaxarea < rw * rh) + realmaxarea = rw * rh; + } + + if (realmaxarea > maxarea) + realmaxarea = maxarea; + + /* + * Rectangles which go right the way across the grid are + * boring, although they can't be helped in the case of + * extremely small grids. (Also they might be generated later + * on by the singleton-removal process; we can't help that.) + */ + mw = params->w - 1; + if (mw < 3) mw++; + mh = params->h - 1; + if (mh < 3) mh++; + + for (rw = 1; rw <= mw; rw++) + for (rh = 1; rh <= mh; rh++) { + if (rw * rh > realmaxarea) continue; if (rw * rh == 1) continue; - for (x = 0; x <= params->w - rw; x++) - for (y = 0; y <= params->h - rh; y++) { - if (nrects >= rectsize) { - rectsize = nrects + 256; - rects = sresize(rects, rectsize, struct rect); + for (x = max(sx - rw + 1, 0); x <= min(sx, params->w - rw); x++) + for (y = max(sy - rh + 1, 0); y <= min(sy, params->h - rh); + y++) { + /* + * Check this rectangle against the region we + * defined above. + */ + if (top[x] <= y && top[x+rw-1] <= y && + bottom[x] >= y+rh-1 && bottom[x+rw-1] >= y+rh-1) { + if (r && index == *n) { + r->x = x; + r->y = y; + r->w = rw; + r->h = rh; + return; + } + index++; } - - rects[nrects].x = x; - rects[nrects].y = y; - rects[nrects].w = rw; - rects[nrects].h = rh; - nrects++; } } - if (nrects > 0) { - struct rectlist *ret; - ret = snew(struct rectlist); - ret->rects = rects; - ret->n = nrects; - return ret; - } else { - assert(rects == NULL); /* hence no need to free */ - return NULL; - } -} - -static void free_rectlist(struct rectlist *list) -{ - sfree(list->rects); - sfree(list); + assert(!r); + *n = index; } static void place_rect(game_params *params, int *grid, struct rect r) @@ -1057,9 +1126,9 @@ static char *new_game_desc(game_params *params, random_state *rs, game_aux_info **aux, int interactive) { int *grid, *numbers = NULL; - struct rectlist *list; - int x, y, y2, y2last, yx, run, i; + int x, y, y2, y2last, yx, run, i, nsquares; char *desc, *p; + int *enum_rects_scratch; game_params params2real, *params2 = ¶ms2real; while (1) { @@ -1074,47 +1143,67 @@ static char *new_game_desc(game_params *params, random_state *rs, grid = snewn(params2->w * params2->h, int); + enum_rects_scratch = snewn(2 * params2->w, int); + + nsquares = 0; for (y = 0; y < params2->h; y++) for (x = 0; x < params2->w; x++) { index(params2, grid, x, y) = -1; + nsquares++; } - list = get_rectlist(params2, grid); - assert(list != NULL); - /* - * Place rectangles until we can't any more. + * Place rectangles until we can't any more. We do this by + * finding a square we haven't yet covered, and randomly + * choosing a rectangle to cover it. */ - while (list->n > 0) { - int i, m; + + while (nsquares > 0) { + int square = random_upto(rs, nsquares); + int n; struct rect r; - /* - * Pick a random rectangle. - */ - i = random_upto(rs, list->n); - r = list->rects[i]; + x = params2->w; + y = params2->h; + for (y = 0; y < params2->h; y++) { + for (x = 0; x < params2->w; x++) { + if (index(params2, grid, x, y) == -1 && square-- == 0) + break; + } + if (x < params2->w) + break; + } + assert(x < params2->w && y < params2->h); /* - * Place it. + * Now see how many rectangles fit around this one. */ - place_rect(params2, grid, r); + enum_rects(params2, grid, NULL, &n, x, y, enum_rects_scratch); - /* - * Winnow the list by removing any rectangles which - * overlap this one. - */ - m = 0; - for (i = 0; i < list->n; i++) { - struct rect s = list->rects[i]; - if (s.x+s.w <= r.x || r.x+r.w <= s.x || - s.y+s.h <= r.y || r.y+r.h <= s.y) - list->rects[m++] = s; + if (!n) { + /* + * There are no possible rectangles covering this + * square, meaning it must be a singleton. Mark it + * -2 so we know not to keep trying. + */ + index(params2, grid, x, y) = -2; + nsquares--; + } else { + /* + * Pick one at random. + */ + n = random_upto(rs, n); + enum_rects(params2, grid, &r, &n, x, y, enum_rects_scratch); + + /* + * Place it. + */ + place_rect(params2, grid, r); + nsquares -= r.w * r.h; } - list->n = m; } - free_rectlist(list); + sfree(enum_rects_scratch); /* * Deal with singleton spaces remaining in the grid, one by @@ -1763,8 +1852,8 @@ static void free_game(game_state *state) sfree(state); } -static game_state *solve_game(game_state *state, game_aux_info *ai, - char **error) +static game_state *solve_game(game_state *state, game_state *currstate, + game_aux_info *ai, char **error) { game_state *ret; @@ -2029,6 +2118,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) @@ -2039,6 +2136,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; } @@ -2120,11 +2221,11 @@ static void coord_round(float x, float y, int *xr, int *yr) /* Vertical edge: x-coord of corner, * y-coord of square centre. */ *xr = 2 * (int)xv; - *yr = 1 + 2 * (int)ys; + *yr = 1 + 2 * (int)floor(ys); } else { /* Horizontal edge: x-coord of square centre, * y-coord of corner. */ - *xr = 1 + 2 * (int)xs; + *xr = 1 + 2 * (int)floor(xs); *yr = 2 * (int)yv; } } @@ -2134,20 +2235,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. @@ -2178,9 +2270,19 @@ 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; @@ -2207,10 +2309,33 @@ 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; + + if (xc >= 0 && xc <= 2*from->w && + yc >= 0 && yc <= 2*from->h) { + 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 */ + } else { + ui->x1 = -1; + ui->y1 = -1; + ui->x2 = -1; + ui->y2 = -1; + } } ret = NULL; @@ -2262,6 +2387,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; } @@ -2278,20 +2407,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)) ) +#define MAX4(x,y,z,w) ( max(max(x,y),max(z,w)) ) -struct game_drawstate { - int started; - int w, h; - unsigned int *visible; -}; - -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; } @@ -2334,7 +2474,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; @@ -2347,9 +2488,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]; @@ -2460,7 +2601,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); @@ -2476,20 +2617,42 @@ 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); @@ -2512,7 +2675,7 @@ 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) @@ -2544,6 +2707,7 @@ const struct game thegame = { TRUE, game_text_format, new_ui, free_ui, + game_changed_state, make_move, game_size, game_colours, @@ -2554,4 +2718,5 @@ const struct game thegame = { game_flash_length, game_wants_statusbar, FALSE, game_timing_state, + 0, /* mouse_priorities */ };