X-Git-Url: https://git.distorted.org.uk/~mdw/sgt/puzzles/blobdiff_plain/092e93956c7a7cf7efa3ad5f8ae32bcf9ebdc6ae..a2f35d71b745ec2a03de58976c6434437c5f303e:/loopy.c diff --git a/loopy.c b/loopy.c index 488b507..7d03ed2 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; @@ -253,7 +254,10 @@ static void check_caches(const solver_state* sstate); A(Cairo,grid_new_cairo,3,4) \ A(Great-Hexagonal,grid_new_greathexagonal,3,3) \ A(Octagonal,grid_new_octagonal,3,3) \ - A(Kites,grid_new_kites,3,3) + A(Kites,grid_new_kites,3,3) \ + 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 @@ -300,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 @@ -504,6 +508,9 @@ static const game_params presets[] = { { 5, 4, DIFF_HARD, 5, NULL }, { 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 }, @@ -518,6 +525,9 @@ static const game_params presets[] = { { 5, 4, DIFF_HARD, 5, NULL }, { 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 }; @@ -702,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; } @@ -829,8 +839,14 @@ static float *game_colours(frontend *fe, int *ncolours) ret[COL_FOREGROUND * 3 + 1] = 0.0F; ret[COL_FOREGROUND * 3 + 2] = 0.0F; - ret[COL_LINEUNKNOWN * 3 + 0] = 0.8F; - ret[COL_LINEUNKNOWN * 3 + 1] = 0.8F; + /* + * We want COL_LINEUNKNOWN to be a yellow which is a bit darker + * than the background. (I previously set it to 0.8,0.8,0, but + * found that this went badly with the 0.8,0.8,0.8 favoured as a + * background by the Java frontend.) + */ + ret[COL_LINEUNKNOWN * 3 + 0] = ret[COL_BACKGROUND * 3 + 0] * 0.9F; + ret[COL_LINEUNKNOWN * 3 + 1] = ret[COL_BACKGROUND * 3 + 1] * 0.9F; ret[COL_LINEUNKNOWN * 3 + 2] = 0.0F; ret[COL_HIGHLIGHT * 3 + 0] = 1.0F; @@ -862,17 +878,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; } @@ -1868,7 +1889,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; @@ -1896,8 +1917,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); @@ -2412,6 +2436,13 @@ static int trivial_deductions(solver_state *sstate) if (state->clues[i] < 0) continue; + /* + * This code checks whether the numeric clue on a face is so + * large as to permit all its remaining LINE_UNKNOWNs to be + * filled in as LINE_YES, or alternatively so small as to + * permit them all to be filled in as LINE_NO. + */ + if (state->clues[i] < current_yes) { sstate->solver_status = SOLVER_MISTAKE; return DIFF_EASY; @@ -2433,6 +2464,57 @@ static int trivial_deductions(solver_state *sstate) sstate->face_solved[i] = TRUE; continue; } + + if (f->order - state->clues[i] == current_no + 1 && + f->order - current_yes - current_no > 2) { + /* + * One small refinement to the above: we also look for any + * adjacent pair of LINE_UNKNOWNs around the face with + * some LINE_YES incident on it from elsewhere. If we find + * one, then we know that pair of LINE_UNKNOWNs can't + * _both_ be LINE_YES, and hence that pushes us one line + * closer to being able to determine all the rest. + */ + int j, k, e1, e2, e, d; + + for (j = 0; j < f->order; j++) { + e1 = f->edges[j] - g->edges; + e2 = f->edges[j+1 < f->order ? j+1 : 0] - g->edges; + + if (g->edges[e1].dot1 == g->edges[e2].dot1 || + g->edges[e1].dot1 == g->edges[e2].dot2) { + d = g->edges[e1].dot1 - g->dots; + } else { + assert(g->edges[e1].dot2 == g->edges[e2].dot1 || + g->edges[e1].dot2 == g->edges[e2].dot2); + d = g->edges[e1].dot2 - g->dots; + } + + if (state->lines[e1] == LINE_UNKNOWN && + state->lines[e2] == LINE_UNKNOWN) { + for (k = 0; k < g->dots[d].order; k++) { + int e = g->dots[d].edges[k] - g->edges; + if (state->lines[e] == LINE_YES) + goto found; /* multi-level break */ + } + } + } + continue; + + found: + /* + * If we get here, we've found such a pair of edges, and + * they're e1 and e2. + */ + for (j = 0; j < f->order; j++) { + e = f->edges[j] - g->edges; + if (state->lines[e] == LINE_UNKNOWN && e != e1 && e != e2) { + int r = solver_set_line(sstate, e, LINE_YES); + assert(r); + diff = min(diff, DIFF_EASY); + } + } + } } check_caches(sstate); @@ -2531,7 +2613,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]; @@ -3319,263 +3401,809 @@ static void grid_to_screen(const game_drawstate *ds, const grid *g, *y += BORDER(ds->tilesize); } +static int solve_2x2_matrix(double mx[4], double vin[2], double vout[2]) +{ + double inv[4]; + double det; + det = (mx[0]*mx[3] - mx[1]*mx[2]); + if (det == 0) + return FALSE; + + inv[0] = mx[3] / det; + inv[1] = -mx[1] / det; + inv[2] = -mx[2] / det; + inv[3] = mx[0] / det; + + vout[0] = inv[0]*vin[0] + inv[1]*vin[1]; + vout[1] = inv[2]*vin[0] + inv[3]*vin[1]; + + return TRUE; +} + +static int solve_3x3_matrix(double mx[9], double vin[3], double vout[3]) +{ + double inv[9]; + double det; + + det = (mx[0]*mx[4]*mx[8] + mx[1]*mx[5]*mx[6] + mx[2]*mx[3]*mx[7] - + mx[0]*mx[5]*mx[7] - mx[1]*mx[3]*mx[8] - mx[2]*mx[4]*mx[6]); + if (det == 0) + return FALSE; + + inv[0] = (mx[4]*mx[8] - mx[5]*mx[7]) / det; + inv[1] = (mx[2]*mx[7] - mx[1]*mx[8]) / det; + inv[2] = (mx[1]*mx[5] - mx[2]*mx[4]) / det; + inv[3] = (mx[5]*mx[6] - mx[3]*mx[8]) / det; + inv[4] = (mx[0]*mx[8] - mx[2]*mx[6]) / det; + inv[5] = (mx[2]*mx[3] - mx[0]*mx[5]) / det; + inv[6] = (mx[3]*mx[7] - mx[4]*mx[6]) / det; + inv[7] = (mx[1]*mx[6] - mx[0]*mx[7]) / det; + inv[8] = (mx[0]*mx[4] - mx[1]*mx[3]) / det; + + vout[0] = inv[0]*vin[0] + inv[1]*vin[1] + inv[2]*vin[2]; + vout[1] = inv[3]*vin[0] + inv[4]*vin[1] + inv[5]*vin[2]; + vout[2] = inv[6]*vin[0] + inv[7]*vin[1] + inv[8]*vin[2]; + + return TRUE; +} + /* 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; + double xbest, ybest, bestdist; + int i, j, k, m; + grid_dot *edgedot1[3], *edgedot2[3]; + grid_dot *dots[3]; + int nedges, ndots; + 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. + * + * This point must be in contact with at least three edges and/or + * vertices; so we iterate through all combinations of three of + * those, and find candidate points in each set. + * + * We don't actually iterate literally over _edges_, in the sense + * of grid_edge structures. Instead, we fill in edgedot1[] and + * edgedot2[] with a pair of dots adjacent in the face's list of + * vertices. This ensures that we get the edges in consistent + * orientation, which we could not do from the grid structure + * alone. (A moment's consideration of an order-3 vertex should + * make it clear that if a notional arrow was written on each + * edge, _at least one_ of the three faces bordering that vertex + * would have to have the two arrows tip-to-tip or tail-to-tail + * rather than tip-to-tail.) + */ + nedges = ndots = 0; + bestdist = 0; + xbest = ybest = 0; + + for (i = 0; i+2 < 2*f->order; i++) { + if (i < f->order) { + edgedot1[nedges] = f->dots[i]; + edgedot2[nedges++] = f->dots[(i+1)%f->order]; + } else + dots[ndots++] = f->dots[i - f->order]; + + for (j = i+1; j+1 < 2*f->order; j++) { + if (j < f->order) { + edgedot1[nedges] = f->dots[j]; + edgedot2[nedges++] = f->dots[(j+1)%f->order]; + } else + dots[ndots++] = f->dots[j - f->order]; + + for (k = j+1; k < 2*f->order; k++) { + double cx[2], cy[2]; /* candidate positions */ + int cn = 0; /* number of candidates */ + + if (k < f->order) { + edgedot1[nedges] = f->dots[k]; + edgedot2[nedges++] = f->dots[(k+1)%f->order]; + } else + dots[ndots++] = f->dots[k - f->order]; + + /* + * Find a point, or pair of points, equidistant from + * all the specified edges and/or vertices. + */ + if (nedges == 3) { + /* + * Three edges. This is a linear matrix equation: + * each row of the matrix represents the fact that + * the point (x,y) we seek is at distance r from + * that edge, and we solve three of those + * simultaneously to obtain x,y,r. (We ignore r.) + */ + double matrix[9], vector[3], vector2[3]; + int m; + + for (m = 0; m < 3; m++) { + int x1 = edgedot1[m]->x, x2 = edgedot2[m]->x; + int y1 = edgedot1[m]->y, y2 = edgedot2[m]->y; + int dx = x2-x1, dy = y2-y1; + + /* + * ((x,y) - (x1,y1)) . (dy,-dx) = r |(dx,dy)| + * + * => x dy - y dx - r |(dx,dy)| = (x1 dy - y1 dx) + */ + matrix[3*m+0] = dy; + matrix[3*m+1] = -dx; + matrix[3*m+2] = -sqrt((double)dx*dx+(double)dy*dy); + vector[m] = (double)x1*dy - (double)y1*dx; + } - /* Best solution probably involves incentres (inscribed circles) */ + if (solve_3x3_matrix(matrix, vector, vector2)) { + cx[cn] = vector2[0]; + cy[cn] = vector2[1]; + cn++; + } + } else if (nedges == 2) { + /* + * Two edges and a dot. This will end up in a + * quadratic equation. + * + * First, look at the two edges. Having our point + * be some distance r from both of them gives rise + * to a pair of linear equations in x,y,r of the + * form + * + * (x-x1) dy - (y-y1) dx = r sqrt(dx^2+dy^2) + * + * We eliminate r between those equations to give + * us a single linear equation in x,y describing + * the locus of points equidistant from both lines + * - i.e. the angle bisector. + * + * We then choose one of x,y to be a parameter t, + * and derive linear formulae for x,y,r in terms + * of t. This enables us to write down the + * circular equation (x-xd)^2+(y-yd)^2=r^2 as a + * quadratic in t; solving that and substituting + * in for x,y gives us two candidate points. + */ + double eqs[2][4]; /* a,b,c,d : ax+by+cr=d */ + double eq[3]; /* a,b,c: ax+by=c */ + double xt[2], yt[2], rt[2]; /* a,b: {x,y,r}=at+b */ + double q[3]; /* a,b,c: at^2+bt+c=0 */ + double disc; + + /* Find equations of the two input lines. */ + for (m = 0; m < 2; m++) { + int x1 = edgedot1[m]->x, x2 = edgedot2[m]->x; + int y1 = edgedot1[m]->y, y2 = edgedot2[m]->y; + int dx = x2-x1, dy = y2-y1; + + eqs[m][0] = dy; + eqs[m][1] = -dx; + eqs[m][2] = -sqrt(dx*dx+dy*dy); + eqs[m][3] = x1*dy - y1*dx; + } - 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; + /* Derive the angle bisector by eliminating r. */ + eq[0] = eqs[0][0]*eqs[1][2] - eqs[1][0]*eqs[0][2]; + eq[1] = eqs[0][1]*eqs[1][2] - eqs[1][1]*eqs[0][2]; + eq[2] = eqs[0][3]*eqs[1][2] - eqs[1][3]*eqs[0][2]; + + /* Parametrise x and y in terms of some t. */ + if (abs(eq[0]) < abs(eq[1])) { + /* Parameter is x. */ + xt[0] = 1; xt[1] = 0; + yt[0] = -eq[0]/eq[1]; yt[1] = eq[2]/eq[1]; + } else { + /* Parameter is y. */ + yt[0] = 1; yt[1] = 0; + xt[0] = -eq[1]/eq[0]; xt[1] = eq[2]/eq[0]; + } + + /* Find a linear representation of r using eqs[0]. */ + rt[0] = -(eqs[0][0]*xt[0] + eqs[0][1]*yt[0])/eqs[0][2]; + rt[1] = (eqs[0][3] - eqs[0][0]*xt[1] - + eqs[0][1]*yt[1])/eqs[0][2]; + + /* Construct the quadratic equation. */ + q[0] = -rt[0]*rt[0]; + q[1] = -2*rt[0]*rt[1]; + q[2] = -rt[1]*rt[1]; + q[0] += xt[0]*xt[0]; + q[1] += 2*xt[0]*(xt[1]-dots[0]->x); + q[2] += (xt[1]-dots[0]->x)*(xt[1]-dots[0]->x); + q[0] += yt[0]*yt[0]; + q[1] += 2*yt[0]*(yt[1]-dots[0]->y); + q[2] += (yt[1]-dots[0]->y)*(yt[1]-dots[0]->y); + + /* And solve it. */ + disc = q[1]*q[1] - 4*q[0]*q[2]; + if (disc >= 0) { + double t; + + disc = sqrt(disc); + + t = (-q[1] + disc) / (2*q[0]); + cx[cn] = xt[0]*t + xt[1]; + cy[cn] = yt[0]*t + yt[1]; + cn++; + + t = (-q[1] - disc) / (2*q[0]); + cx[cn] = xt[0]*t + xt[1]; + cy[cn] = yt[0]*t + yt[1]; + cn++; + } + } else if (nedges == 1) { + /* + * Two dots and an edge. This one's another + * quadratic equation. + * + * The point we want must lie on the perpendicular + * bisector of the two dots; that much is obvious. + * So we can construct a parametrisation of that + * bisecting line, giving linear formulae for x,y + * in terms of t. We can also express the distance + * from the edge as such a linear formula. + * + * Then we set that equal to the radius of the + * circle passing through the two points, which is + * a Pythagoras exercise; that gives rise to a + * quadratic in t, which we solve. + */ + double xt[2], yt[2], rt[2]; /* a,b: {x,y,r}=at+b */ + double q[3]; /* a,b,c: at^2+bt+c=0 */ + double disc; + double halfsep; + + /* Find parametric formulae for x,y. */ + { + int x1 = dots[0]->x, x2 = dots[1]->x; + int y1 = dots[0]->y, y2 = dots[1]->y; + int dx = x2-x1, dy = y2-y1; + double d = sqrt((double)dx*dx + (double)dy*dy); + + xt[1] = (x1+x2)/2.0; + yt[1] = (y1+y2)/2.0; + /* It's convenient if we have t at standard scale. */ + xt[0] = -dy/d; + yt[0] = dx/d; + + /* Also note down half the separation between + * the dots, for use in computing the circle radius. */ + halfsep = 0.5*d; + } + + /* Find a parametric formula for r. */ + { + int x1 = edgedot1[0]->x, x2 = edgedot2[0]->x; + int y1 = edgedot1[0]->y, y2 = edgedot2[0]->y; + int dx = x2-x1, dy = y2-y1; + double d = sqrt((double)dx*dx + (double)dy*dy); + rt[0] = (xt[0]*dy - yt[0]*dx) / d; + rt[1] = ((xt[1]-x1)*dy - (yt[1]-y1)*dx) / d; + } + + /* Construct the quadratic equation. */ + q[0] = rt[0]*rt[0]; + q[1] = 2*rt[0]*rt[1]; + q[2] = rt[1]*rt[1]; + q[0] -= 1; + q[2] -= halfsep*halfsep; + + /* And solve it. */ + disc = q[1]*q[1] - 4*q[0]*q[2]; + if (disc >= 0) { + double t; + + disc = sqrt(disc); + + t = (-q[1] + disc) / (2*q[0]); + cx[cn] = xt[0]*t + xt[1]; + cy[cn] = yt[0]*t + yt[1]; + cn++; + + t = (-q[1] - disc) / (2*q[0]); + cx[cn] = xt[0]*t + xt[1]; + cy[cn] = yt[0]*t + yt[1]; + cn++; + } + } else if (nedges == 0) { + /* + * Three dots. This is another linear matrix + * equation, this time with each row of the matrix + * representing the perpendicular bisector between + * two of the points. Of course we only need two + * such lines to find their intersection, so we + * need only solve a 2x2 matrix equation. + */ + + double matrix[4], vector[2], vector2[2]; + int m; + + for (m = 0; m < 2; m++) { + int x1 = dots[m]->x, x2 = dots[m+1]->x; + int y1 = dots[m]->y, y2 = dots[m+1]->y; + int dx = x2-x1, dy = y2-y1; + + /* + * ((x,y) - (x1,y1)) . (dx,dy) = 1/2 |(dx,dy)|^2 + * + * => 2x dx + 2y dy = dx^2+dy^2 + (2 x1 dx + 2 y1 dy) + */ + matrix[2*m+0] = 2*dx; + matrix[2*m+1] = 2*dy; + vector[m] = ((double)dx*dx + (double)dy*dy + + 2.0*x1*dx + 2.0*y1*dy); + } + + if (solve_2x2_matrix(matrix, vector, vector2)) { + cx[cn] = vector2[0]; + cy[cn] = vector2[1]; + cn++; + } + } + + /* + * Now go through our candidate points and see if any + * of them are better than what we've got so far. + */ + for (m = 0; m < cn; m++) { + double x = cx[m], y = cy[m]; + + /* + * 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 e, in = 0; + for (e = 0; e < f->order; e++) { + int xs = f->edges[e]->dot1->x; + int xe = f->edges[e]->dot2->x; + int ys = f->edges[e]->dot1->y; + int ye = f->edges[e]->dot2->y; + 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) { + double mindist = HUGE_VAL; + int e, d; + + /* + * This point is inside the polygon, so now we check + * its minimum distance to every edge and corner. + * First the corners ... + */ + for (d = 0; d < f->order; d++) { + int xp = f->dots[d]->x; + int yp = f->dots[d]->y; + double dx = x - xp, dy = y - yp; + double dist = dx*dx + 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 (e = 0; e < f->order; e++) { + int xs = f->edges[e]->dot1->x; + int xe = f->edges[e]->dot2->x; + int ys = f->edges[e]->dot1->y; + int ye = f->edges[e]->dot2->y; + + /* + * 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; + double pdx = x - xs, pdy = y - ys; + double pde = pdx * edx + 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. + */ + + double pdre = pdx * edy - pdy * edx; + double 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; + } + } + } + + if (k < f->order) + nedges--; + else + ndots--; + } + if (j < f->order) + nedges--; + else + ndots--; + } + if (i < f->order) + nedges--; + else + ndots--; } - sx /= f->order; - sy /= f->order; - /* convert to screen coordinates */ - grid_to_screen(ds, g, sx, sy, x, y); + assert(bestdist > 0); + + /* convert to screen coordinates. Round doubles to nearest. */ + grid_to_screen(ds, g, xbest+0.5, ybest+0.5, + &ds->textx[faceindex], &ds->texty[faceindex]); + + *xret = ds->textx[faceindex]; + *yret = ds->texty[faceindex]; } -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 face_text_bbox(game_drawstate *ds, grid *g, grid_face *f, + int *x, int *y, int *w, int *h) { - grid *g = state->game_grid; - int border = BORDER(ds->tilesize); - int i, n; - char c[2]; - int line_colour, flash_changed; - int clue_mistake; - int clue_satisfied; + int xx, yy; + face_text_pos(ds, g, f, &xx, &yy); - if (!ds->started) { - /* - * The initial contents of the window are not guaranteed and - * can vary with front ends. To be on the safe side, all games - * should start by drawing a big background-colour rectangle - * covering the whole window. - */ - int grid_width = g->highest_x - g->lowest_x; - int grid_height = g->highest_y - g->lowest_y; - int w = grid_width * ds->tilesize / g->tilesize; - int h = grid_height * ds->tilesize / g->tilesize; - draw_rect(dr, 0, 0, w + 2 * border + 1, h + 2 * border + 1, - COL_BACKGROUND); + /* There seems to be a certain amount of trial-and-error involved + * in working out the correct bounding-box for the text. */ - /* Draw clues */ - for (i = 0; i < g->num_faces; i++) { - grid_face *f; - int x, y; + *x = xx - ds->tilesize/4 - 1; + *y = yy - ds->tilesize/4 - 3; + *w = ds->tilesize/2 + 2; + *h = ds->tilesize/2 + 5; +} - c[0] = CLUE2CHAR(state->clues[i]); - c[1] = '\0'; - f = g->faces + i; - face_text_pos(ds, g, f, &x, &y); - draw_text(dr, x, y, FONT_VARIABLE, ds->tilesize/2, - ALIGN_VCENTRE | ALIGN_HCENTRE, COL_FOREGROUND, c); - } - draw_update(dr, 0, 0, w + 2 * border, h + 2 * border); +static void game_redraw_clue(drawing *dr, game_drawstate *ds, + game_state *state, int i) +{ + grid *g = state->game_grid; + grid_face *f = g->faces + i; + int x, y; + char c[3]; + + if (state->clues[i] < 10) { + c[0] = CLUE2CHAR(state->clues[i]); + c[1] = '\0'; + } else { + sprintf(c, "%d", state->clues[i]); } - if (flashtime > 0 && - (flashtime <= FLASH_TIME/3 || - flashtime >= FLASH_TIME*2/3)) { - flash_changed = !ds->flashing; - ds->flashing = TRUE; + face_text_pos(ds, g, f, &x, &y); + draw_text(dr, x, y, + FONT_VARIABLE, ds->tilesize/2, + ALIGN_VCENTRE | ALIGN_HCENTRE, + ds->clue_error[i] ? COL_MISTAKE : + ds->clue_satisfied[i] ? COL_SATISFIED : COL_FOREGROUND, c); +} + +static void edge_bbox(game_drawstate *ds, grid *g, grid_edge *e, + int *x, int *y, int *w, int *h) +{ + int x1 = e->dot1->x; + int y1 = e->dot1->y; + int x2 = e->dot2->x; + int y2 = e->dot2->y; + int xmin, xmax, ymin, ymax; + + grid_to_screen(ds, g, x1, y1, &x1, &y1); + grid_to_screen(ds, g, x2, y2, &x2, &y2); + /* Allow extra margin for dots, and thickness of lines */ + xmin = min(x1, x2) - 2; + xmax = max(x1, x2) + 2; + ymin = min(y1, y2) - 2; + ymax = max(y1, y2) + 2; + + *x = xmin; + *y = ymin; + *w = xmax - xmin + 1; + *h = ymax - ymin + 1; +} + +static void dot_bbox(game_drawstate *ds, grid *g, grid_dot *d, + int *x, int *y, int *w, int *h) +{ + int x1, y1; + + grid_to_screen(ds, g, d->x, d->y, &x1, &y1); + + *x = x1 - 2; + *y = y1 - 2; + *w = 5; + *h = 5; +} + +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, int phase) +{ + grid *g = state->game_grid; + grid_edge *e = g->edges + i; + int x1, x2, y1, y2; + int xmin, ymin, xmax, ymax; + int line_colour; + + if (state->line_errors[i]) + line_colour = COL_MISTAKE; + else if (state->lines[i] == LINE_UNKNOWN) + line_colour = COL_LINEUNKNOWN; + else if (state->lines[i] == LINE_NO) + line_colour = COL_FAINT; + else if (ds->flashing) + 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); + grid_to_screen(ds, g, e->dot2->x, e->dot2->y, &x2, &y2); + + xmin = min(x1, x2); + xmax = max(x1, x2); + ymin = min(y1, y2); + ymax = max(y1, y2); + + if (line_colour == COL_FAINT) { + static int draw_faint_lines = -1; + if (draw_faint_lines < 0) { + char *env = getenv("LOOPY_FAINT_LINES"); + draw_faint_lines = (!env || (env[0] == 'y' || + env[0] == 'Y')); + } + if (draw_faint_lines) + draw_line(dr, x1, y1, x2, y2, line_colour); } else { - flash_changed = ds->flashing; - ds->flashing = FALSE; + draw_thick_line(dr, 3.0, + x1 + 0.5, y1 + 0.5, + x2 + 0.5, y2 + 0.5, + line_colour); } +} - /* Some platforms may perform anti-aliasing, which may prevent clean - * repainting of lines when the colour is changed. - * If a line needs to be over-drawn in a different colour, erase a - * bounding-box around the line, then flag all nearby objects for redraw. +static void game_redraw_dot(drawing *dr, game_drawstate *ds, + game_state *state, int i) +{ + grid *g = state->game_grid; + grid_dot *d = g->dots + i; + int x, y; + + grid_to_screen(ds, g, d->x, d->y, &x, &y); + draw_circle(dr, x, y, 2, COL_FOREGROUND, COL_FOREGROUND); +} + +static int boxes_intersect(int x0, int y0, int w0, int h0, + int x1, int y1, int w1, int h1) +{ + /* + * Two intervals intersect iff neither is wholly on one side of + * the other. Two boxes intersect iff their horizontal and + * vertical intervals both intersect. */ - if (ds->started) { - const char redraw_flag = (char)(1<<7); + return (x0 < x1+w1 && x1 < x0+w0 && y0 < y1+h1 && y1 < y0+h0); +} + +static void game_redraw_in_rect(drawing *dr, game_drawstate *ds, + game_state *state, int x, int y, int w, int h) +{ + grid *g = state->game_grid; + int i, phase; + int bx, by, bw, bh; + + clip(dr, x, y, w, h); + draw_rect(dr, x, y, w, h, COL_BACKGROUND); + + for (i = 0; i < g->num_faces; i++) { + if (state->clues[i] >= 0) { + face_text_bbox(ds, g, &g->faces[i], &bx, &by, &bw, &bh); + if (boxes_intersect(x, y, w, h, bx, by, bw, bh)) + game_redraw_clue(dr, ds, state, i); + } + } + for (phase = 0; phase < NPHASES; phase++) { for (i = 0; i < g->num_edges; i++) { - char prev_ds = (ds->lines[i] & ~redraw_flag); - char new_ds = state->lines[i]; - if (state->line_errors[i]) - new_ds = DS_LINE_ERROR; - - /* If we're changing state, AND - * the previous state was a coloured line */ - if ((prev_ds != new_ds) && (prev_ds != LINE_NO)) { - grid_edge *e = g->edges + i; - int x1 = e->dot1->x; - int y1 = e->dot1->y; - int x2 = e->dot2->x; - int y2 = e->dot2->y; - int xmin, xmax, ymin, ymax; - int j; - grid_to_screen(ds, g, x1, y1, &x1, &y1); - grid_to_screen(ds, g, x2, y2, &x2, &y2); - /* Allow extra margin for dots, and thickness of lines */ - xmin = min(x1, x2) - 2; - xmax = max(x1, x2) + 2; - ymin = min(y1, y2) - 2; - ymax = max(y1, y2) + 2; - /* For testing, I find it helpful to change COL_BACKGROUND - * to COL_SATISFIED here. */ - draw_rect(dr, xmin, ymin, xmax - xmin + 1, ymax - ymin + 1, - COL_BACKGROUND); - draw_update(dr, xmin, ymin, xmax - xmin + 1, ymax - ymin + 1); - - /* Mark nearby lines for redraw */ - for (j = 0; j < e->dot1->order; j++) - ds->lines[e->dot1->edges[j] - g->edges] |= redraw_flag; - for (j = 0; j < e->dot2->order; j++) - ds->lines[e->dot2->edges[j] - g->edges] |= redraw_flag; - /* Mark nearby clues for redraw. Use a value that is - * neither TRUE nor FALSE for this. */ - if (e->face1) - ds->clue_error[e->face1 - g->faces] = 2; - if (e->face2) - ds->clue_error[e->face2 - g->faces] = 2; - } + edge_bbox(ds, g, &g->edges[i], &bx, &by, &bw, &bh); + if (boxes_intersect(x, y, w, h, bx, by, bw, bh)) + game_redraw_line(dr, ds, state, i, phase); } } + for (i = 0; i < g->num_dots; i++) { + dot_bbox(ds, g, &g->dots[i], &bx, &by, &bw, &bh); + if (boxes_intersect(x, y, w, h, bx, by, bw, bh)) + game_redraw_dot(dr, ds, state, i); + } - /* Redraw clue colours if necessary */ - for (i = 0; i < g->num_faces; i++) { - grid_face *f = g->faces + i; - int sides = f->order; - int j; - n = state->clues[i]; - if (n < 0) - continue; + unclip(dr); + draw_update(dr, x, y, w, h); +} - c[0] = CLUE2CHAR(n); - c[1] = '\0'; +static void game_redraw(drawing *dr, game_drawstate *ds, game_state *oldstate, + game_state *state, int dir, game_ui *ui, + float animtime, float flashtime) +{ +#define REDRAW_OBJECTS_LIMIT 16 /* Somewhat arbitrary tradeoff */ - clue_mistake = (face_order(state, i, LINE_YES) > n || - face_order(state, i, LINE_NO ) > (sides-n)); + grid *g = state->game_grid; + int border = BORDER(ds->tilesize); + int i; + int flash_changed; + int redraw_everything = FALSE; - clue_satisfied = (face_order(state, i, LINE_YES) == n && - face_order(state, i, LINE_NO ) == (sides-n)); + int edges[REDRAW_OBJECTS_LIMIT], nedges = 0; + int faces[REDRAW_OBJECTS_LIMIT], nfaces = 0; - if (clue_mistake != ds->clue_error[i] - || clue_satisfied != ds->clue_satisfied[i]) { - int x, y; - face_text_pos(ds, g, f, &x, &y); - /* There seems to be a certain amount of trial-and-error - * involved in working out the correct bounding-box for - * the text. */ - draw_rect(dr, x - ds->tilesize/4 - 1, y - ds->tilesize/4 - 3, - ds->tilesize/2 + 2, ds->tilesize/2 + 5, - COL_BACKGROUND); - draw_text(dr, x, y, - FONT_VARIABLE, ds->tilesize/2, - ALIGN_VCENTRE | ALIGN_HCENTRE, - clue_mistake ? COL_MISTAKE : - clue_satisfied ? COL_SATISFIED : COL_FOREGROUND, c); - draw_update(dr, x - ds->tilesize/4 - 1, y - ds->tilesize/4 - 3, - ds->tilesize/2 + 2, ds->tilesize/2 + 5); + /* Redrawing is somewhat involved. + * + * An update can theoretically affect an arbitrary number of edges + * (consider, for example, completing or breaking a cycle which doesn't + * satisfy all the clues -- we'll switch many edges between error and + * normal states). On the other hand, redrawing the whole grid takes a + * while, making the game feel sluggish, and many updates are actually + * quite well localized. + * + * This redraw algorithm attempts to cope with both situations gracefully + * and correctly. For localized changes, we set a clip rectangle, fill + * it with background, and then redraw (a plausible but conservative + * guess at) the objects which intersect the rectangle; if several + * objects need redrawing, we'll do them individually. However, if lots + * of objects are affected, we'll just redraw everything. + * + * The reason for all of this is that it's just not safe to do the redraw + * piecemeal. If you try to draw an antialiased diagonal line over + * itself, you get a slightly thicker antialiased diagonal line, which + * looks rather ugly after a while. + * + * So, we take two passes over the grid. The first attempts to work out + * what needs doing, and the second actually does it. + */ - ds->clue_error[i] = clue_mistake; - ds->clue_satisfied[i] = clue_satisfied; + if (!ds->started) + redraw_everything = TRUE; + else { + + /* First, trundle through the faces. */ + for (i = 0; i < g->num_faces; i++) { + grid_face *f = g->faces + i; + int sides = f->order; + int clue_mistake; + int clue_satisfied; + int n = state->clues[i]; + if (n < 0) + continue; + + clue_mistake = (face_order(state, i, LINE_YES) > n || + face_order(state, i, LINE_NO ) > (sides-n)); + clue_satisfied = (face_order(state, i, LINE_YES) == n && + face_order(state, i, LINE_NO ) == (sides-n)); + + if (clue_mistake != ds->clue_error[i] || + clue_satisfied != ds->clue_satisfied[i]) { + ds->clue_error[i] = clue_mistake; + ds->clue_satisfied[i] = clue_satisfied; + if (nfaces == REDRAW_OBJECTS_LIMIT) + redraw_everything = TRUE; + else + faces[nfaces++] = i; + } + } - /* Sometimes, the bounding-box encroaches into the surrounding - * lines (particularly if the window is resized fairly small). - * So redraw them. */ - for (j = 0; j < f->order; j++) - ds->lines[f->edges[j] - g->edges] = -1; - } + /* Work out what the flash state needs to be. */ + if (flashtime > 0 && + (flashtime <= FLASH_TIME/3 || + flashtime >= FLASH_TIME*2/3)) { + flash_changed = !ds->flashing; + ds->flashing = TRUE; + } else { + flash_changed = ds->flashing; + ds->flashing = FALSE; + } + + /* Now, trundle through the edges. */ + for (i = 0; i < g->num_edges; i++) { + char new_ds = + state->line_errors[i] ? DS_LINE_ERROR : state->lines[i]; + if (new_ds != ds->lines[i] || + (flash_changed && state->lines[i] == LINE_YES)) { + ds->lines[i] = new_ds; + if (nedges == REDRAW_OBJECTS_LIMIT) + redraw_everything = TRUE; + else + edges[nedges++] = i; + } + } } - /* Lines */ - for (i = 0; i < g->num_edges; i++) { - grid_edge *e = g->edges + i; - int x1, x2, y1, y2; - int xmin, ymin, xmax, ymax; - char new_ds, need_draw; - new_ds = state->lines[i]; - if (state->line_errors[i]) - new_ds = DS_LINE_ERROR; - need_draw = (new_ds != ds->lines[i]) ? TRUE : FALSE; - if (flash_changed && (state->lines[i] == LINE_YES)) - need_draw = TRUE; - if (!ds->started) - need_draw = TRUE; /* draw everything at the start */ - ds->lines[i] = new_ds; - if (!need_draw) - continue; - if (state->line_errors[i]) - line_colour = COL_MISTAKE; - else if (state->lines[i] == LINE_UNKNOWN) - line_colour = COL_LINEUNKNOWN; - else if (state->lines[i] == LINE_NO) - line_colour = COL_FAINT; - else if (ds->flashing) - line_colour = COL_HIGHLIGHT; - else - line_colour = COL_FOREGROUND; + /* Pass one is now done. Now we do the actual drawing. */ + if (redraw_everything) { + int grid_width = g->highest_x - g->lowest_x; + int grid_height = g->highest_y - g->lowest_y; + int w = grid_width * ds->tilesize / g->tilesize; + int h = grid_height * ds->tilesize / g->tilesize; - /* Convert from grid to screen coordinates */ - grid_to_screen(ds, g, e->dot1->x, e->dot1->y, &x1, &y1); - grid_to_screen(ds, g, e->dot2->x, e->dot2->y, &x2, &y2); + game_redraw_in_rect(dr, ds, state, + 0, 0, w + 2*border + 1, h + 2*border + 1); + } else { - xmin = min(x1, x2); - xmax = max(x1, x2); - ymin = min(y1, y2); - ymax = max(y1, y2); - - if (line_colour == COL_FAINT) { - static int draw_faint_lines = -1; - if (draw_faint_lines < 0) { - char *env = getenv("LOOPY_FAINT_LINES"); - draw_faint_lines = (!env || (env[0] == 'y' || - env[0] == 'Y')); - } - if (draw_faint_lines) - draw_line(dr, x1, y1, x2, y2, line_colour); - } else { - /* (dx, dy) points roughly from (x1, y1) to (x2, y2). - * The line is then "fattened" in a (roughly) perpendicular - * direction to create a thin rectangle. */ - int dx = (x1 > x2) ? -1 : ((x1 < x2) ? 1 : 0); - int dy = (y1 > y2) ? -1 : ((y1 < y2) ? 1 : 0); - int points[8]; - points[0] = x1 + dy; - points[1] = y1 - dx; - points[2] = x1 - dy; - points[3] = y1 + dx; - points[4] = x2 - dy; - points[5] = y2 + dx; - points[6] = x2 + dy; - points[7] = y2 - dx; - draw_polygon(dr, points, 4, line_colour, line_colour); - } - if (ds->started) { - /* Draw dots at ends of the line */ - draw_circle(dr, x1, y1, 2, COL_FOREGROUND, COL_FOREGROUND); - draw_circle(dr, x2, y2, 2, COL_FOREGROUND, COL_FOREGROUND); - } - draw_update(dr, xmin-2, ymin-2, xmax - xmin + 4, ymax - ymin + 4); - } - - /* Draw dots */ - if (!ds->started) { - for (i = 0; i < g->num_dots; i++) { - grid_dot *d = g->dots + i; - int x, y; - grid_to_screen(ds, g, d->x, d->y, &x, &y); - draw_circle(dr, x, y, 2, COL_FOREGROUND, COL_FOREGROUND); - } + /* Right. Now we roll up our sleeves. */ + + for (i = 0; i < nfaces; i++) { + grid_face *f = g->faces + faces[i]; + int x, y, w, h; + + face_text_bbox(ds, g, f, &x, &y, &w, &h); + game_redraw_in_rect(dr, ds, state, x, y, w, h); + } + + for (i = 0; i < nedges; i++) { + grid_edge *e = g->edges + edges[i]; + int x, y, w, h; + + edge_bbox(ds, g, e, &x, &y, &w, &h); + game_redraw_in_rect(dr, ds, state, x, y, w, h); + } } + ds->started = TRUE; } @@ -3590,6 +4218,11 @@ static float game_flash_length(game_state *oldstate, game_state *newstate, return 0.0F; } +static int game_is_solved(game_state *state) +{ + return state->solved; +} + static void game_print_size(game_params *params, float *x, float *y) { int pw, ph; @@ -3716,6 +4349,7 @@ const struct game thegame = { game_redraw, game_anim_length, game_flash_length, + game_is_solved, TRUE, FALSE, game_print_size, game_print, FALSE /* wants_statusbar */, FALSE, game_timing_state,