X-Git-Url: https://git.distorted.org.uk/~mdw/sgt/puzzles/blobdiff_plain/42159ec64bc26ce5d0ae2f8381f31a230ac4756e..19937f86816c7e683d6130d928a02d148add6e3f:/untangle.c diff --git a/untangle.c b/untangle.c index a16e9cd..14a5c6c 100644 --- a/untangle.c +++ b/untangle.c @@ -13,8 +13,11 @@ /* * TODO: * - * - Docs and checklist etc * - Any way we can speed up redraws on GTK? Uck. + * + * - It would be nice if we could somehow auto-detect a real `long + * long' type on the host platform and use it in place of my + * hand-hacked int64s. It'd be faster and more reliable. */ #include @@ -31,17 +34,22 @@ #define DRAG_THRESHOLD (CIRCLE_RADIUS * 2) #define PREFERRED_TILESIZE 64 -#define FLASH_TIME 0.13F +#define FLASH_TIME 0.30F #define ANIM_TIME 0.13F #define SOLVEANIM_TIME 0.50F enum { COL_BACKGROUND, COL_LINE, +#ifdef SHOW_CROSSINGS + COL_CROSSEDLINE, +#endif COL_OUTLINE, COL_POINT, COL_DRAGPOINT, COL_NEIGHBOUR, + COL_FLASH1, + COL_FLASH2, NCOLOURS }; @@ -76,6 +84,9 @@ struct game_state { game_params params; int w, h; /* extent of coordinate system only */ point *pts; +#ifdef SHOW_CROSSINGS + int *crosses; /* mark edges which are crossed */ +#endif struct graph *graph; int completed, cheated, just_solved; }; @@ -194,6 +205,90 @@ static char *validate_params(game_params *params, int full) return NULL; } +/* ---------------------------------------------------------------------- + * Small number of 64-bit integer arithmetic operations, to prevent + * integer overflow at the very core of cross(). + */ + +typedef struct { + long hi; + unsigned long lo; +} int64; + +#define greater64(i,j) ( (i).hi>(j).hi || ((i).hi==(j).hi && (i).lo>(j).lo)) +#define sign64(i) ((i).hi < 0 ? -1 : (i).hi==0 && (i).lo==0 ? 0 : +1) + +int64 mulu32to64(unsigned long x, unsigned long y) +{ + unsigned long a, b, c, d, t; + int64 ret; + + a = (x & 0xFFFF) * (y & 0xFFFF); + b = (x & 0xFFFF) * (y >> 16); + c = (x >> 16) * (y & 0xFFFF); + d = (x >> 16) * (y >> 16); + + ret.lo = a; + ret.hi = d + (b >> 16) + (c >> 16); + t = (b & 0xFFFF) << 16; + ret.lo += t; + if (ret.lo < t) + ret.hi++; + t = (c & 0xFFFF) << 16; + ret.lo += t; + if (ret.lo < t) + ret.hi++; + +#ifdef DIAGNOSTIC_VIA_LONGLONG + assert(((unsigned long long)ret.hi << 32) + ret.lo == + (unsigned long long)x * y); +#endif + + return ret; +} + +int64 mul32to64(long x, long y) +{ + int sign = +1; + int64 ret; +#ifdef DIAGNOSTIC_VIA_LONGLONG + long long realret = (long long)x * y; +#endif + + if (x < 0) + x = -x, sign = -sign; + if (y < 0) + y = -y, sign = -sign; + + ret = mulu32to64(x, y); + + if (sign < 0) { + ret.hi = -ret.hi; + ret.lo = -ret.lo; + if (ret.lo) + ret.hi--; + } + +#ifdef DIAGNOSTIC_VIA_LONGLONG + assert(((unsigned long long)ret.hi << 32) + ret.lo == realret); +#endif + + return ret; +} + +int64 dotprod64(long a, long b, long p, long q) +{ + int64 ab, pq; + + ab = mul32to64(a, b); + pq = mul32to64(p, q); + ab.hi += pq.hi; + ab.lo += pq.lo; + if (ab.lo < pq.lo) + ab.hi++; + return ab; +} + /* * Determine whether the line segments between a1 and a2, and * between b1 and b2, intersect. We count it as an intersection if @@ -201,7 +296,8 @@ static char *validate_params(game_params *params, int full) */ static int cross(point a1, point a2, point b1, point b2) { - long b1x, b1y, b2x, b2y, px, py, d1, d2, d3; + long b1x, b1y, b2x, b2y, px, py; + int64 d1, d2, d3; /* * The condition for crossing is that b1 and b2 are on opposite @@ -225,11 +321,12 @@ static int cross(point a1, point a2, point b1, point b2) b2y = b2.y * a1.d - a1.y * b2.d; px = a1.y * a2.d - a2.y * a1.d; py = a2.x * a1.d - a1.x * a2.d; - /* Take the dot products. */ - d1 = b1x * px + b1y * py; - d2 = b2x * px + b2y * py; + /* Take the dot products. Here we resort to 64-bit arithmetic. */ + d1 = dotprod64(b1x, px, b1y, py); + d2 = dotprod64(b2x, px, b2y, py); /* If they have the same non-zero sign, the lines do not cross. */ - if ((d1 > 0 && d2 > 0) || (d1 < 0 && d2 < 0)) + if ((sign64(d1) > 0 && sign64(d2) > 0) || + (sign64(d1) < 0 && sign64(d2) < 0)) return FALSE; /* @@ -238,21 +335,21 @@ static int cross(point a1, point a2, point b1, point b2) * condition becomes whether or not they overlap within their * line. */ - if (d1 == 0 && d2 == 0) { + if (sign64(d1) == 0 && sign64(d2) == 0) { /* Construct the vector a2-a1. */ px = a2.x * a1.d - a1.x * a2.d; py = a2.y * a1.d - a1.y * a2.d; /* Determine the dot products of b1-a1 and b2-a1 with this. */ - d1 = b1x * px + b1y * py; - d2 = b2x * px + b2y * py; + d1 = dotprod64(b1x, px, b1y, py); + d2 = dotprod64(b2x, px, b2y, py); /* If they're both strictly negative, the lines do not cross. */ - if (d1 < 0 && d2 < 0) + if (sign64(d1) < 0 && sign64(d2) < 0) return FALSE; /* Otherwise, take the dot product of a2-a1 with itself. If * the other two dot products both exceed this, the lines do * not cross. */ - d3 = px * px + py * py; - if (d1 > d3 && d2 > d3) + d3 = dotprod64(px, px, py, py); + if (greater64(d1, d3) && greater64(d2, d3)) return FALSE; } @@ -268,9 +365,10 @@ static int cross(point a1, point a2, point b1, point b2) b2y = a2.y * b1.d - b1.y * a2.d; px = b1.y * b2.d - b2.y * b1.d; py = b2.x * b1.d - b1.x * b2.d; - d1 = b1x * px + b1y * py; - d2 = b2x * px + b2y * py; - if ((d1 > 0 && d2 > 0) || (d1 < 0 && d2 < 0)) + d1 = dotprod64(b1x, px, b1y, py); + d2 = dotprod64(b2x, px, b2y, py); + if ((sign64(d1) > 0 && sign64(d2) > 0) || + (sign64(d1) < 0 && sign64(d2) < 0)) return FALSE; /* @@ -655,6 +753,49 @@ static char *validate_desc(game_params *params, char *desc) return NULL; } +static void mark_crossings(game_state *state) +{ + int ok = TRUE; + int i, j; + edge *e, *e2; + +#ifdef SHOW_CROSSINGS + for (i = 0; (e = index234(state->graph->edges, i)) != NULL; i++) + state->crosses[i] = FALSE; +#endif + + /* + * Check correctness: for every pair of edges, see whether they + * cross. + */ + for (i = 0; (e = index234(state->graph->edges, i)) != NULL; i++) { + for (j = i+1; (e2 = index234(state->graph->edges, j)) != NULL; j++) { + if (e2->a == e->a || e2->a == e->b || + e2->b == e->a || e2->b == e->b) + continue; + if (cross(state->pts[e2->a], state->pts[e2->b], + state->pts[e->a], state->pts[e->b])) { + ok = FALSE; +#ifdef SHOW_CROSSINGS + state->crosses[i] = state->crosses[j] = TRUE; +#else + goto done; /* multi-level break - sorry */ +#endif + } + } + } + + /* + * e == NULL if we've gone through all the edge pairs + * without finding a crossing. + */ +#ifndef SHOW_CROSSINGS + done: +#endif + if (ok) + state->completed = TRUE; +} + static game_state *new_game(midend_data *me, game_params *params, char *desc) { int n = params->n; @@ -686,6 +827,11 @@ static game_state *new_game(midend_data *me, game_params *params, char *desc) addedge(state->graph->edges, a, b); } +#ifdef SHOW_CROSSINGS + state->crosses = snewn(count234(state->graph->edges), int); + mark_crossings(state); /* sets up `crosses' and `completed' */ +#endif + return state; } @@ -704,6 +850,11 @@ static game_state *dup_game(game_state *state) ret->completed = state->completed; ret->cheated = state->cheated; ret->just_solved = state->just_solved; +#ifdef SHOW_CROSSINGS + ret->crosses = snewn(count234(ret->graph->edges), int); + memcpy(ret->crosses, state->crosses, + count234(ret->graph->edges) * sizeof(int)); +#endif return ret; } @@ -724,12 +875,147 @@ static void free_game(game_state *state) static char *solve_game(game_state *state, game_state *currstate, char *aux, char **error) { + int n = state->params.n; + int matrix[4]; + point *pts; + int i, j, besti; + float bestd; + char buf[80], *ret; + int retlen, retsize; + if (!aux) { *error = "Solution not known for this puzzle"; return NULL; } - return dupstr(aux); + /* + * Decode the aux_info to get the original point positions. + */ + pts = snewn(n, point); + aux++; /* eat 'S' */ + for (i = 0; i < n; i++) { + int p, k; + long x, y, d; + int ret = sscanf(aux, ";P%d:%ld,%ld/%ld%n", &p, &x, &y, &d, &k); + if (ret != 4 || p != i) { + *error = "Internal error: aux_info badly formatted"; + sfree(pts); + return NULL; + } + pts[i].x = x; + pts[i].y = y; + pts[i].d = d; + aux += k; + } + + /* + * Now go through eight possible symmetries of the point set. + * For each one, work out the sum of the Euclidean distances + * between the points' current positions and their new ones. + * + * We're squaring distances here, which means we're at risk of + * integer overflow. Fortunately, there's no real need to be + * massively careful about rounding errors, since this is a + * non-essential bit of the code; so I'll just work in floats + * internally. + */ + besti = -1; + bestd = 0.0F; + + for (i = 0; i < 8; i++) { + float d; + + matrix[0] = matrix[1] = matrix[2] = matrix[3] = 0; + matrix[i & 1] = (i & 2) ? +1 : -1; + matrix[3-(i&1)] = (i & 4) ? +1 : -1; + + d = 0.0F; + for (j = 0; j < n; j++) { + float px = (float)pts[j].x / pts[j].d; + float py = (float)pts[j].y / pts[j].d; + float sx = (float)currstate->pts[j].x / currstate->pts[j].d; + float sy = (float)currstate->pts[j].y / currstate->pts[j].d; + float cx = (float)currstate->w / 2; + float cy = (float)currstate->h / 2; + float ox, oy, dx, dy; + + px -= cx; + py -= cy; + + ox = matrix[0] * px + matrix[1] * py; + oy = matrix[2] * px + matrix[3] * py; + + ox += cx; + oy += cy; + + dx = ox - sx; + dy = oy - sy; + + d += dx*dx + dy*dy; + } + + if (besti < 0 || bestd > d) { + besti = i; + bestd = d; + } + } + + assert(besti >= 0); + + /* + * Now we know which symmetry is closest to the points' current + * positions. Use it. + */ + matrix[0] = matrix[1] = matrix[2] = matrix[3] = 0; + matrix[besti & 1] = (besti & 2) ? +1 : -1; + matrix[3-(besti&1)] = (besti & 4) ? +1 : -1; + + retsize = 256; + ret = snewn(retsize, char); + retlen = 0; + ret[retlen++] = 'S'; + ret[retlen] = '\0'; + + for (i = 0; i < n; i++) { + float px = (float)pts[i].x / pts[i].d; + float py = (float)pts[i].y / pts[i].d; + float cx = (float)currstate->w / 2; + float cy = (float)currstate->h / 2; + float ox, oy; + int extra; + + px -= cx; + py -= cy; + + ox = matrix[0] * px + matrix[1] * py; + oy = matrix[2] * px + matrix[3] * py; + + ox += cx; + oy += cy; + + /* + * Use a fixed denominator of 2, because we know the + * original points were on an integer grid offset by 1/2. + */ + pts[i].d = 2; + ox *= pts[i].d; + oy *= pts[i].d; + pts[i].x = ox + 0.5; + pts[i].y = oy + 0.5; + + extra = sprintf(buf, ";P%d:%ld,%ld/%ld", i, + pts[i].x, pts[i].y, pts[i].d); + if (retlen + extra >= retsize) { + retsize = retlen + extra + 256; + ret = sresize(ret, retsize, char); + } + strcpy(ret + retlen, buf); + retlen += extra; + } + + sfree(pts); + + return ret; } static char *game_text_format(game_state *state) @@ -882,33 +1168,7 @@ static game_state *execute_move(game_state *state, char *move) } } - /* - * Check correctness: for every pair of edges, see whether they - * cross. - */ - if (!ret->completed) { - int i, j; - edge *e, *e2; - - for (i = 0; (e = index234(ret->graph->edges, i)) != NULL; i++) { - for (j = i+1; (e2 = index234(ret->graph->edges, j)) != NULL; j++) { - if (e2->a == e->a || e2->a == e->b || - e2->b == e->a || e2->b == e->b) - continue; - if (cross(ret->pts[e2->a], ret->pts[e2->b], - ret->pts[e->a], ret->pts[e->b])) - break; - } - if (e2) - break; - } - - /* - * e == NULL if we've gone through all the edge pairs - * without finding a crossing. - */ - ret->completed = (e == NULL); - } + mark_crossings(ret); return ret; } @@ -939,6 +1199,12 @@ static float *game_colours(frontend *fe, game_state *state, int *ncolours) ret[COL_LINE * 3 + 1] = 0.0F; ret[COL_LINE * 3 + 2] = 0.0F; +#ifdef SHOW_CROSSINGS + ret[COL_CROSSEDLINE * 3 + 0] = 1.0F; + ret[COL_CROSSEDLINE * 3 + 1] = 0.0F; + ret[COL_CROSSEDLINE * 3 + 2] = 0.0F; +#endif + ret[COL_OUTLINE * 3 + 0] = 0.0F; ret[COL_OUTLINE * 3 + 1] = 0.0F; ret[COL_OUTLINE * 3 + 2] = 0.0F; @@ -955,6 +1221,14 @@ static float *game_colours(frontend *fe, game_state *state, int *ncolours) ret[COL_NEIGHBOUR * 3 + 1] = 0.0F; ret[COL_NEIGHBOUR * 3 + 2] = 0.0F; + ret[COL_FLASH1 * 3 + 0] = 0.5F; + ret[COL_FLASH1 * 3 + 1] = 0.5F; + ret[COL_FLASH1 * 3 + 2] = 0.5F; + + ret[COL_FLASH2 * 3 + 0] = 1.0F; + ret[COL_FLASH2 * 3 + 1] = 1.0F; + ret[COL_FLASH2 * 3 + 2] = 1.0F; + *ncolours = NCOLOURS; return ret; } @@ -999,7 +1273,13 @@ static void game_redraw(frontend *fe, game_drawstate *ds, game_state *oldstate, * whole thing every time. */ - bg = (flashtime != 0 ? COL_DRAGPOINT : COL_BACKGROUND); + if (flashtime == 0) + bg = COL_BACKGROUND; + else if ((int)(flashtime * 4 / FLASH_TIME) % 2 == 0) + bg = COL_FLASH1; + else + bg = COL_FLASH2; + game_compute_size(&state->params, ds->tilesize, &w, &h); draw_rect(fe, 0, 0, w, h, bg); @@ -1028,7 +1308,12 @@ static void game_redraw(frontend *fe, game_drawstate *ds, game_state *oldstate, x2 = p2.x * ds->tilesize / p2.d; y2 = p2.y * ds->tilesize / p2.d; - draw_line(fe, x1, y1, x2, y2, COL_LINE); + draw_line(fe, x1, y1, x2, y2, +#ifdef SHOW_CROSSINGS + (oldstate?oldstate:state)->crosses[i] ? + COL_CROSSEDLINE : +#endif + COL_LINE); } /*