X-Git-Url: https://git.distorted.org.uk/~mdw/sgt/puzzles/blobdiff_plain/1ad942e7feb35231f8642f26a5fb238c68d937d4..HEAD:/untangle.c diff --git a/untangle.c b/untangle.c index 5d01e9a..beb2871 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 }; @@ -50,7 +58,7 @@ typedef struct point { * Points are stored using rational coordinates, with the same * denominator for both coordinates. */ - int x, y, d; + long x, y, d; } point; typedef struct edge { @@ -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) + +static 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; +} + +static 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; +} + +static 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) { - int 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; /* @@ -358,7 +456,7 @@ static int vertcmp(void *av, void *bv) { return vertcmpC(av, bv); } */ static void make_circle(point *pts, int n, int w) { - int d, r, c, i; + long d, r, c, i; /* * First, decide on a denominator. Although in principle it @@ -380,8 +478,8 @@ static void make_circle(point *pts, int n, int w) for (i = 0; i < n; i++) { double angle = i * 2 * PI / n; double x = r * sin(angle), y = - r * cos(angle); - pts[i].x = (int)(c + x + 0.5); - pts[i].y = (int)(c + y + 0.5); + pts[i].x = (long)(c + x + 0.5); + pts[i].y = (long)(c + y + 0.5); pts[i].d = d; } } @@ -389,10 +487,10 @@ static void make_circle(point *pts, int n, int w) static char *new_game_desc(game_params *params, random_state *rs, char **aux, int interactive) { - int n = params->n; - int w, h, i, j, k, m; + int n = params->n, i; + long w, h, j, k, m; point *pts, *pts2; - int *tmp; + long *tmp; tree234 *edges, *vertices; edge *e, *e2; vertex *v, *vs, *vlist; @@ -404,7 +502,7 @@ static char *new_game_desc(game_params *params, random_state *rs, * Choose n points from this grid. */ pts = snewn(n, point); - tmp = snewn(w*h, int); + tmp = snewn(w*h, long); for (i = 0; i < w*h; i++) tmp[i] = i; shuffle(tmp, w*h, sizeof(*tmp), rs); @@ -523,7 +621,7 @@ static char *new_game_desc(game_params *params, random_state *rs, * they come out with at least one crossed line when arranged * in a circle (so that the puzzle isn't immediately solved!). */ - tmp = snewn(n, int); + tmp = snewn(n, long); for (i = 0; i < n; i++) tmp[i] = i; pts2 = snewn(n, point); @@ -603,14 +701,14 @@ static char *new_game_desc(game_params *params, random_state *rs, } pts2[j].x += pts2[j].d / 2; pts2[j].y += pts2[j].d / 2; - auxlen += sprintf(buf, ";P%d:%d,%d/%d", i, + auxlen += sprintf(buf, ";P%d:%ld,%ld/%ld", i, pts2[j].x, pts2[j].y, pts2[j].d); } k = 0; auxstr = snewn(auxlen, char); auxstr[k++] = 'S'; for (i = 0; i < n; i++) - k += sprintf(auxstr+k, ";P%d:%d,%d/%d", i, + k += sprintf(auxstr+k, ";P%d:%ld,%ld/%ld", i, pts2[i].x, pts2[i].y, pts2[i].d); assert(k < auxlen); *aux = auxstr; @@ -655,7 +753,50 @@ static char *validate_desc(game_params *params, char *desc) return NULL; } -static game_state *new_game(midend_data *me, game_params *params, char *desc) +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 *me, game_params *params, char *desc) { int n = params->n; game_state *state = snew(game_state); @@ -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,152 @@ 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 = (long)(ox + 0.5F); + pts[i].y = (long)(oy + 0.5F); + + 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 int game_can_format_as_text_now(game_params *params) +{ + return TRUE; } static char *game_text_format(game_state *state) @@ -776,16 +1067,19 @@ static void game_changed_state(game_ui *ui, game_state *oldstate, } struct game_drawstate { - int tilesize; + long tilesize; + int bg, dragpoint; + long *x, *y; }; -static char *interpret_move(game_state *state, game_ui *ui, game_drawstate *ds, +static char *interpret_move(game_state *state, game_ui *ui, const game_drawstate *ds, int x, int y, int button) { int n = state->params.n; - if (button == LEFT_BUTTON) { - int i, best, bestd; + if (IS_MOUSE_DOWN(button)) { + int i, best; + long bestd; /* * Begin drag. We drag the vertex _nearest_ to the pointer, @@ -797,11 +1091,11 @@ static char *interpret_move(game_state *state, game_ui *ui, game_drawstate *ds, bestd = 0; for (i = 0; i < n; i++) { - int px = state->pts[i].x * ds->tilesize / state->pts[i].d; - int py = state->pts[i].y * ds->tilesize / state->pts[i].d; - int dx = px - x; - int dy = py - y; - int d = dx*dx + dy*dy; + long px = state->pts[i].x * ds->tilesize / state->pts[i].d; + long py = state->pts[i].y * ds->tilesize / state->pts[i].d; + long dx = px - x; + long dy = py - y; + long d = dx*dx + dy*dy; if (best == -1 || bestd > d) { best = i; @@ -817,12 +1111,12 @@ static char *interpret_move(game_state *state, game_ui *ui, game_drawstate *ds, return ""; } - } else if (button == LEFT_DRAG && ui->dragpoint >= 0) { + } else if (IS_MOUSE_DRAG(button) && ui->dragpoint >= 0) { ui->newpoint.x = x; ui->newpoint.y = y; ui->newpoint.d = ds->tilesize; return ""; - } else if (button == LEFT_RELEASE && ui->dragpoint >= 0) { + } else if (IS_MOUSE_RELEASE(button) && ui->dragpoint >= 0) { int p = ui->dragpoint; char buf[80]; @@ -832,15 +1126,17 @@ static char *interpret_move(game_state *state, game_ui *ui, game_drawstate *ds, * First, see if we're within range. The user can cancel a * drag by dragging the point right off the window. */ - if (ui->newpoint.x < 0 || ui->newpoint.x >= state->w*ui->newpoint.d || - ui->newpoint.y < 0 || ui->newpoint.y >= state->h*ui->newpoint.d) + if (ui->newpoint.x < 0 || + ui->newpoint.x >= (long)state->w*ui->newpoint.d || + ui->newpoint.y < 0 || + ui->newpoint.y >= (long)state->h*ui->newpoint.d) return ""; /* * We aren't cancelling the drag. Construct a move string * indicating where this point is going to. */ - sprintf(buf, "P%d:%d,%d/%d", p, + sprintf(buf, "P%d:%ld,%ld/%ld", p, ui->newpoint.x, ui->newpoint.y, ui->newpoint.d); ui->just_dragged = TRUE; return dupstr(buf); @@ -852,7 +1148,8 @@ static char *interpret_move(game_state *state, game_ui *ui, game_drawstate *ds, static game_state *execute_move(game_state *state, char *move) { int n = state->params.n; - int p, x, y, d, k; + int p, k; + long x, y, d; game_state *ret = dup_game(state); ret->just_solved = FALSE; @@ -864,7 +1161,7 @@ static game_state *execute_move(game_state *state, char *move) ret->cheated = ret->just_solved = TRUE; } if (*move == 'P' && - sscanf(move+1, "%d:%d,%d/%d%n", &p, &x, &y, &d, &k) == 4 && + sscanf(move+1, "%d:%ld,%ld/%ld%n", &p, &x, &y, &d, &k) == 4 && p >= 0 && p < n && d > 0) { ret->pts[p].x = x; ret->pts[p].y = y; @@ -878,33 +1175,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; } @@ -919,13 +1190,13 @@ static void game_compute_size(game_params *params, int tilesize, *x = *y = COORDLIMIT(params->n) * tilesize; } -static void game_set_size(game_drawstate *ds, game_params *params, - int tilesize) +static void game_set_size(drawing *dr, game_drawstate *ds, + game_params *params, int tilesize) { ds->tilesize = tilesize; } -static float *game_colours(frontend *fe, game_state *state, int *ncolours) +static float *game_colours(frontend *fe, int *ncolours) { float *ret = snewn(3 * NCOLOURS, float); @@ -935,6 +1206,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; @@ -951,21 +1228,38 @@ 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; } -static game_drawstate *game_new_drawstate(game_state *state) +static game_drawstate *game_new_drawstate(drawing *dr, game_state *state) { struct game_drawstate *ds = snew(struct game_drawstate); + int i; ds->tilesize = 0; + ds->x = snewn(state->params.n, long); + ds->y = snewn(state->params.n, long); + for (i = 0; i < state->params.n; i++) + ds->x[i] = ds->y[i] = -1; + ds->bg = -1; + ds->dragpoint = -1; return ds; } -static void game_free_drawstate(game_drawstate *ds) +static void game_free_drawstate(drawing *dr, game_drawstate *ds) { + sfree(ds->y); + sfree(ds->x); sfree(ds); } @@ -974,20 +1268,20 @@ static point mix(point a, point b, float distance) point ret; ret.d = a.d * b.d; - ret.x = a.x * b.d + distance * (b.x * a.d - a.x * b.d); - ret.y = a.y * b.d + distance * (b.y * a.d - a.y * b.d); + ret.x = (long)(a.x * b.d + distance * (b.x * a.d - a.x * b.d)); + ret.y = (long)(a.y * b.d + distance * (b.y * a.d - a.y * b.d)); return ret; } -static void game_redraw(frontend *fe, game_drawstate *ds, game_state *oldstate, +static void game_redraw(drawing *dr, game_drawstate *ds, game_state *oldstate, game_state *state, int dir, game_ui *ui, float animtime, float flashtime) { int w, h; edge *e; int i, j; - int bg; + int bg, points_moved; /* * There's no terribly sensible way to do partial redraws of @@ -995,36 +1289,64 @@ 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; + + /* + * To prevent excessive spinning on redraw during a completion + * flash, we first check to see if _either_ the flash + * background colour has changed _or_ at least one point has + * moved _or_ a drag has begun or ended, and abandon the redraw + * if neither is the case. + * + * Also in this loop we work out the coordinates of all the + * points for this redraw. + */ + points_moved = FALSE; + for (i = 0; i < state->params.n; i++) { + point p = state->pts[i]; + long x, y; + + if (ui->dragpoint == i) + p = ui->newpoint; + + if (oldstate) + p = mix(oldstate->pts[i], p, animtime / ui->anim_length); + + x = p.x * ds->tilesize / p.d; + y = p.y * ds->tilesize / p.d; + + if (ds->x[i] != x || ds->y[i] != y) + points_moved = TRUE; + + ds->x[i] = x; + ds->y[i] = y; + } + + if (ds->bg == bg && ds->dragpoint == ui->dragpoint && !points_moved) + return; /* nothing to do */ + + ds->dragpoint = ui->dragpoint; + ds->bg = bg; + game_compute_size(&state->params, ds->tilesize, &w, &h); - draw_rect(fe, 0, 0, w, h, bg); + draw_rect(dr, 0, 0, w, h, bg); /* * Draw the edges. */ for (i = 0; (e = index234(state->graph->edges, i)) != NULL; i++) { - point p1, p2; - int x1, y1, x2, y2; - - p1 = state->pts[e->a]; - p2 = state->pts[e->b]; - if (ui->dragpoint == e->a) - p1 = ui->newpoint; - else if (ui->dragpoint == e->b) - p2 = ui->newpoint; - - if (oldstate) { - p1 = mix(oldstate->pts[e->a], p1, animtime / ui->anim_length); - p2 = mix(oldstate->pts[e->b], p2, animtime / ui->anim_length); - } - - x1 = p1.x * ds->tilesize / p1.d; - y1 = p1.y * ds->tilesize / p1.d; - 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(dr, ds->x[e->a], ds->y[e->a], ds->x[e->b], ds->y[e->b], +#ifdef SHOW_CROSSINGS + (oldstate?oldstate:state)->crosses[i] ? + COL_CROSSEDLINE : +#endif + COL_LINE); } /* @@ -1037,11 +1359,9 @@ static void game_redraw(frontend *fe, game_drawstate *ds, game_state *oldstate, int thisc = (j == 0 ? COL_POINT : j == 1 ? COL_NEIGHBOUR : COL_DRAGPOINT); for (i = 0; i < state->params.n; i++) { - int x, y, c; - point p = state->pts[i]; + int c; if (ui->dragpoint == i) { - p = ui->newpoint; c = COL_DRAGPOINT; } else if (ui->dragpoint >= 0 && isedge(state->graph->edges, ui->dragpoint, i)) { @@ -1050,29 +1370,25 @@ static void game_redraw(frontend *fe, game_drawstate *ds, game_state *oldstate, c = COL_POINT; } - if (oldstate) - p = mix(oldstate->pts[i], p, animtime / ui->anim_length); - if (c == thisc) { - x = p.x * ds->tilesize / p.d; - y = p.y * ds->tilesize / p.d; - #ifdef VERTEX_NUMBERS - draw_circle(fe, x, y, DRAG_THRESHOLD, bg, bg); + draw_circle(dr, ds->x[i], ds->y[i], DRAG_THRESHOLD, bg, bg); { char buf[80]; sprintf(buf, "%d", i); - draw_text(fe, x, y, FONT_VARIABLE, DRAG_THRESHOLD*3/2, + draw_text(dr, ds->x[i], ds->y[i], FONT_VARIABLE, + DRAG_THRESHOLD*3/2, ALIGN_VCENTRE|ALIGN_HCENTRE, c, buf); } #else - draw_circle(fe, x, y, CIRCLE_RADIUS, c, COL_OUTLINE); + draw_circle(dr, ds->x[i], ds->y[i], CIRCLE_RADIUS, + c, COL_OUTLINE); #endif } } } - draw_update(fe, 0, 0, w, h); + draw_update(dr, 0, 0, w, h); } static float game_anim_length(game_state *oldstate, game_state *newstate, @@ -1096,9 +1412,9 @@ static float game_flash_length(game_state *oldstate, game_state *newstate, return 0.0F; } -static int game_wants_statusbar(void) +static int game_status(game_state *state) { - return FALSE; + return state->completed ? +1 : 0; } static int game_timing_state(game_state *state, game_ui *ui) @@ -1106,12 +1422,20 @@ static int game_timing_state(game_state *state, game_ui *ui) return TRUE; } +static void game_print_size(game_params *params, float *x, float *y) +{ +} + +static void game_print(drawing *dr, game_state *state, int tilesize) +{ +} + #ifdef COMBINED #define thegame untangle #endif const struct game thegame = { - "Untangle", "games.untangle", + "Untangle", "games.untangle", "untangle", default_params, game_fetch_preset, decode_params, @@ -1126,7 +1450,7 @@ const struct game thegame = { dup_game, free_game, TRUE, solve_game, - FALSE, game_text_format, + FALSE, game_can_format_as_text_now, game_text_format, new_ui, free_ui, encode_ui, @@ -1141,7 +1465,9 @@ const struct game thegame = { game_redraw, game_anim_length, game_flash_length, - game_wants_statusbar, + game_status, + FALSE, FALSE, game_print_size, game_print, + FALSE, /* wants_statusbar */ FALSE, game_timing_state, - SOLVE_ANIMATES, /* mouse_priorities */ + SOLVE_ANIMATES, /* flags */ };