X-Git-Url: https://git.distorted.org.uk/~mdw/sgt/puzzles/blobdiff_plain/e30d39f6f3df08ea9c8a91df5db31d0346d1c5ad..e0936bbdf14b05964b4a0929012d042a4d554ba0:/loopy.c diff --git a/loopy.c b/loopy.c index 07f17a9..212c229 100644 --- a/loopy.c +++ b/loopy.c @@ -228,6 +228,7 @@ struct game_drawstate { int started; int tilesize; int flashing; + int *textx, *texty; char *lines; char *clue_error; char *clue_satisfied; @@ -254,7 +255,9 @@ static void check_caches(const solver_state* sstate); A(Great-Hexagonal,grid_new_greathexagonal,3,3) \ A(Octagonal,grid_new_octagonal,3,3) \ A(Kites,grid_new_kites,3,3) \ - A(Floret,grid_new_floret,1,2) + A(Floret,grid_new_floret,1,2) \ + A(Dodecagonal,grid_new_dodecagonal,2,2) \ + A(Great-Dodecagonal,grid_new_greatdodecagonal,2,2) #define GRID_NAME(title,fn,amin,omin) #title, #define GRID_CONFIG(title,fn,amin,omin) ":" #title @@ -301,7 +304,7 @@ static void params_generate_grid(game_params *params) ((field) &= ~(1<<(bit)), TRUE) : FALSE) #define CLUE2CHAR(c) \ - ((c < 0) ? ' ' : c + '0') + ((c < 0) ? ' ' : c < 10 ? c + '0' : c - 10 + 'A') /* ---------------------------------------------------------------------- * General struct manipulation and other straightforward code @@ -506,6 +509,8 @@ static const game_params presets[] = { { 5, 5, DIFF_HARD, 6, NULL }, { 5, 5, DIFF_HARD, 7, NULL }, { 3, 3, DIFF_HARD, 8, NULL }, + { 3, 3, DIFF_HARD, 9, NULL }, + { 3, 3, DIFF_HARD, 10, NULL }, #else { 7, 7, DIFF_EASY, 0, NULL }, { 10, 10, DIFF_EASY, 0, NULL }, @@ -521,6 +526,8 @@ static const game_params presets[] = { { 7, 7, DIFF_HARD, 6, NULL }, { 5, 5, DIFF_HARD, 7, NULL }, { 5, 5, DIFF_HARD, 8, NULL }, + { 5, 4, DIFF_HARD, 9, NULL }, + { 5, 4, DIFF_HARD, 10, NULL }, #endif }; @@ -705,7 +712,7 @@ static char *validate_desc(game_params *params, char *desc) g = params->game_grid; for (; *desc; ++desc) { - if (*desc >= '0' && *desc <= '9') { + if ((*desc >= '0' && *desc <= '9') || (*desc >= 'A' && *desc <= 'Z')) { count++; continue; } @@ -865,17 +872,22 @@ static game_drawstate *game_new_drawstate(drawing *dr, game_state *state) struct game_drawstate *ds = snew(struct game_drawstate); int num_faces = state->game_grid->num_faces; int num_edges = state->game_grid->num_edges; + int i; ds->tilesize = 0; ds->started = 0; ds->lines = snewn(num_edges, char); ds->clue_error = snewn(num_faces, char); ds->clue_satisfied = snewn(num_faces, char); + ds->textx = snewn(num_faces, int); + ds->texty = snewn(num_faces, int); ds->flashing = 0; memset(ds->lines, LINE_UNKNOWN, num_edges); memset(ds->clue_error, 0, num_faces); memset(ds->clue_satisfied, 0, num_faces); + for (i = 0; i < num_faces; i++) + ds->textx[i] = ds->texty[i] = -1; return ds; } @@ -1822,6 +1834,7 @@ static char *new_game_desc(game_params *params, random_state *rs, grid *g; game_state *state = snew(game_state); game_state *state_new; + int count = 0; params_generate_grid(params); state->game_grid = g = params->game_grid; g->refcount++; @@ -1843,6 +1856,7 @@ static char *new_game_desc(game_params *params, random_state *rs, * preventing games smaller than 4x4 seems to stop this happening */ do { add_full_clues(state, rs); + if (++count%100 == 0) printf("tried %d times to make a unique board\n", count); } while (!game_has_unique_soln(state, params->diff)); state_new = remove_clues(state, rs, params->diff); @@ -1871,7 +1885,7 @@ static game_state *new_game(midend *me, game_params *params, char *desc) int i; game_state *state = snew(game_state); int empties_to_make = 0; - int n; + int n,n2; const char *dp = desc; grid *g; int num_faces, num_edges; @@ -1899,8 +1913,11 @@ static game_state *new_game(midend *me, game_params *params, char *desc) assert(*dp); n = *dp - '0'; + n2 = *dp - 'A' + 10; if (n >= 0 && n < 10) { state->clues[i] = n; + } else if (n2 >= 10 && n2 < 36) { + state->clues[i] = n2; } else { n = *dp - 'a' + 1; assert(n > 0); @@ -2534,7 +2551,7 @@ static int dline_deductions(solver_state *sstate) * on that. We check this with an assertion, in case someone decides to * make a grid which has larger faces than this. Note, this algorithm * could get quite expensive if there are many large faces. */ -#define MAX_FACE_SIZE 8 +#define MAX_FACE_SIZE 12 for (i = 0; i < g->num_faces; i++) { int maxs[MAX_FACE_SIZE][MAX_FACE_SIZE]; @@ -3325,29 +3342,175 @@ static void grid_to_screen(const game_drawstate *ds, const grid *g, /* Returns (into x,y) position of centre of face for rendering the text clue. */ static void face_text_pos(const game_drawstate *ds, const grid *g, - const grid_face *f, int *x, int *y) + const grid_face *f, int *xret, int *yret) { - int i; + int x, y, x0, y0, x1, y1, xbest, ybest, i, shift; + long bestdist; + int faceindex = f - g->faces; - /* Simplest solution is the centroid. Might not work in some cases. */ + /* + * Return the cached position for this face, if we've already + * worked it out. + */ + if (ds->textx[faceindex] >= 0) { + *xret = ds->textx[faceindex]; + *yret = ds->texty[faceindex]; + return; + } - /* Another algorithm to look into: - * Find the midpoints of the sides, find the bounding-box, - * then take the centre of that. */ + /* + * Otherwise, try to find the point in the polygon with the + * maximum distance to any edge or corner. + * + * Start by working out the face's bounding box, in grid + * coordinates. + */ + x0 = x1 = f->dots[0]->x; + y0 = y1 = f->dots[0]->y; + for (i = 1; i < f->order; i++) { + if (x0 > f->dots[i]->x) x0 = f->dots[i]->x; + if (x1 < f->dots[i]->x) x1 = f->dots[i]->x; + if (y0 > f->dots[i]->y) y0 = f->dots[i]->y; + if (y1 < f->dots[i]->y) y1 = f->dots[i]->y; + } - /* Best solution probably involves incentres (inscribed circles) */ + /* + * If the grid is at excessive resolution, decide on a scaling + * factor to bring it within reasonable bounds so we don't have to + * think too hard or suffer integer overflow. + */ + shift = 0; + while (x1 - x0 > 128 || y1 - y0 > 128) { + shift++; + x0 >>= 1; + x1 >>= 1; + y0 >>= 1; + y1 >>= 1; + } - int sx = 0, sy = 0; /* sums */ - for (i = 0; i < f->order; i++) { - grid_dot *d = f->dots[i]; - sx += d->x; - sy += d->y; + /* + * Now iterate over every point in that bounding box. + */ + xbest = ybest = -1; + bestdist = -1; + for (y = y0; y <= y1; y++) { + for (x = x0; x <= x1; x++) { + /* + * First, disqualify the point if it's not inside the + * polygon, which we work out by counting the edges to the + * right of the point. (For tiebreaking purposes when + * edges start or end on our y-coordinate or go right + * through it, we consider our point to be offset by a + * small _positive_ epsilon in both the x- and + * y-direction.) + */ + int in = 0; + for (i = 0; i < f->order; i++) { + int xs = f->edges[i]->dot1->x >> shift; + int xe = f->edges[i]->dot2->x >> shift; + int ys = f->edges[i]->dot1->y >> shift; + int ye = f->edges[i]->dot2->y >> shift; + if ((y >= ys && y < ye) || (y >= ye && y < ys)) { + /* + * The line goes past our y-position. Now we need + * to know if its x-coordinate when it does so is + * to our right. + * + * The x-coordinate in question is mathematically + * (y - ys) * (xe - xs) / (ye - ys), and we want + * to know whether (x - xs) >= that. Of course we + * avoid the division, so we can work in integers; + * to do this we must multiply both sides of the + * inequality by ye - ys, which means we must + * first check that's not negative. + */ + int num = xe - xs, denom = ye - ys; + if (denom < 0) { + num = -num; + denom = -denom; + } + if ((x - xs) * denom >= (y - ys) * num) + in ^= 1; + } + } + + if (in) { + long mindist = LONG_MAX; + + /* + * This point is inside the polygon, so now we check + * its minimum distance to every edge and corner. + * First the corners ... + */ + for (i = 0; i < f->order; i++) { + int xp = f->dots[i]->x >> shift; + int yp = f->dots[i]->y >> shift; + int dx = x - xp, dy = y - yp; + long dist = (long)dx*dx + (long)dy*dy; + if (mindist > dist) + mindist = dist; + } + + /* + * ... and now also check the perpendicular distance + * to every edge, if the perpendicular lies between + * the edge's endpoints. + */ + for (i = 0; i < f->order; i++) { + int xs = f->edges[i]->dot1->x >> shift; + int xe = f->edges[i]->dot2->x >> shift; + int ys = f->edges[i]->dot1->y >> shift; + int ye = f->edges[i]->dot2->y >> shift; + + /* + * If s and e are our endpoints, and p our + * candidate circle centre, the foot of a + * perpendicular from p to the line se lies + * between s and e if and only if (p-s).(e-s) lies + * strictly between 0 and (e-s).(e-s). + */ + int edx = xe - xs, edy = ye - ys; + int pdx = x - xs, pdy = y - ys; + long pde = (long)pdx * edx + (long)pdy * edy; + long ede = (long)edx * edx + (long)edy * edy; + if (0 < pde && pde < ede) { + /* + * Yes, the nearest point on this edge is + * closer than either endpoint, so we must + * take it into account by measuring the + * perpendicular distance to the edge and + * checking its square against mindist. + */ + + long pdre = (long)pdx * edy - (long)pdy * edx; + long sqlen = pdre * pdre / ede; + + if (mindist > sqlen) + mindist = sqlen; + } + } + + /* + * Right. Now we know the biggest circle around this + * point, so we can check it against bestdist. + */ + if (bestdist < mindist) { + bestdist = mindist; + xbest = x; + ybest = y; + } + } + } } - sx /= f->order; - sy /= f->order; + + assert(bestdist >= 0); /* convert to screen coordinates */ - grid_to_screen(ds, g, sx, sy, x, y); + grid_to_screen(ds, g, xbest << shift, ybest << shift, + &ds->textx[faceindex], &ds->texty[faceindex]); + + *xret = ds->textx[faceindex]; + *yret = ds->texty[faceindex]; } static void game_redraw_clue(drawing *dr, game_drawstate *ds, @@ -3356,10 +3519,14 @@ static void game_redraw_clue(drawing *dr, game_drawstate *ds, grid *g = state->game_grid; grid_face *f = g->faces + i; int x, y; - char c[2]; + char c[3]; - c[0] = CLUE2CHAR(state->clues[i]); - c[1] = '\0'; + if (state->clues[i] < 10) { + c[0] = CLUE2CHAR(state->clues[i]); + c[1] = '\0'; + } else { + sprintf(c, "%d", state->clues[i]); + } face_text_pos(ds, g, f, &x, &y); draw_text(dr, x, y, @@ -3369,8 +3536,13 @@ static void game_redraw_clue(drawing *dr, game_drawstate *ds, ds->clue_satisfied[i] ? COL_SATISFIED : COL_FOREGROUND, c); } +static const int loopy_line_redraw_phases[] = { + COL_FAINT, COL_LINEUNKNOWN, COL_FOREGROUND, COL_HIGHLIGHT, COL_MISTAKE +}; +#define NPHASES lenof(loopy_line_redraw_phases) + static void game_redraw_line(drawing *dr, game_drawstate *ds, - game_state *state, int i) + game_state *state, int i, int phase) { grid *g = state->game_grid; grid_edge *e = g->edges + i; @@ -3388,6 +3560,8 @@ static void game_redraw_line(drawing *dr, game_drawstate *ds, line_colour = COL_HIGHLIGHT; else line_colour = COL_FOREGROUND; + if (line_colour != loopy_line_redraw_phases[phase]) + return; /* Convert from grid to screen coordinates */ grid_to_screen(ds, g, e->dot1->x, e->dot1->y, &x1, &y1); @@ -3434,7 +3608,7 @@ static void game_redraw(drawing *dr, game_drawstate *ds, game_state *oldstate, grid *g = state->game_grid; int border = BORDER(ds->tilesize); - int i; + int i, phase; int flash_changed; int redraw_everything = FALSE; @@ -3537,8 +3711,9 @@ static void game_redraw(drawing *dr, game_drawstate *ds, game_state *oldstate, for (i = 0; i < g->num_faces; i++) game_redraw_clue(dr, ds, state, i); - for (i = 0; i < g->num_edges; i++) - game_redraw_line(dr, ds, state, i); + for (phase = 0; phase < NPHASES; phase++) + for (i = 0; i < g->num_edges; i++) + game_redraw_line(dr, ds, state, i, phase); for (i = 0; i < g->num_dots; i++) game_redraw_dot(dr, ds, state, i); @@ -3564,8 +3739,10 @@ static void game_redraw(drawing *dr, game_drawstate *ds, game_state *oldstate, draw_rect(dr, x, y, w, h, COL_BACKGROUND); game_redraw_clue(dr, ds, state, faces[i]); - for (j = 0; j < f->order; j++) - game_redraw_line(dr, ds, state, f->edges[j] - g->edges); + for (phase = 0; phase < NPHASES; phase++) + for (j = 0; j < f->order; j++) + game_redraw_line(dr, ds, state, f->edges[j] - g->edges, + phase); for (j = 0; j < f->order; j++) game_redraw_dot(dr, ds, state, f->dots[j] - g->dots); unclip(dr); @@ -3599,17 +3776,19 @@ static void game_redraw(drawing *dr, game_drawstate *ds, game_state *oldstate, if (e->face2) game_redraw_clue(dr, ds, state, e->face2 - g->faces); - game_redraw_line(dr, ds, state, edges[i]); - for (j = 0; j < e->dot1->order; j++) { - ee = e->dot1->edges[j]; - if (ee != e) - game_redraw_line(dr, ds, state, ee - g->edges); - } - for (j = 0; j < e->dot2->order; j++) { - ee = e->dot2->edges[j]; - if (ee != e) - game_redraw_line(dr, ds, state, ee - g->edges); - } + for (phase = 0; phase < NPHASES; phase++) { + game_redraw_line(dr, ds, state, edges[i], phase); + for (j = 0; j < e->dot1->order; j++) { + ee = e->dot1->edges[j]; + if (ee != e) + game_redraw_line(dr, ds, state, ee - g->edges, phase); + } + for (j = 0; j < e->dot2->order; j++) { + ee = e->dot2->edges[j]; + if (ee != e) + game_redraw_line(dr, ds, state, ee - g->edges, phase); + } + } game_redraw_dot(dr, ds, state, e->dot1 - g->dots); game_redraw_dot(dr, ds, state, e->dot2 - g->dots);