2 * untangle.c: Game about planar graphs. You are given a graph
3 * represented by points and straight lines, with some lines
4 * crossing; your task is to drag the points into a configuration
5 * where none of the lines cross.
7 * Cloned from a Flash game called `Planarity', by John Tantalo.
8 * <http://home.cwru.edu/~jnt5/Planarity> at the time of writing
9 * this. The Flash game had a fixed set of levels; my added value,
10 * as usual, is automatic generation of random games to order.
16 * - Any way we can speed up redraws on GTK? Uck.
18 * - It would be nice if we could somehow auto-detect a real `long
19 * long' type on the host platform and use it in place of my
20 * hand-hacked int64s. It'd be faster and more reliable.
33 #define CIRCLE_RADIUS 6
34 #define DRAG_THRESHOLD (CIRCLE_RADIUS * 2)
35 #define PREFERRED_TILESIZE 64
37 #define FLASH_TIME 0.30F
38 #define ANIM_TIME 0.13F
39 #define SOLVEANIM_TIME 0.50F
56 typedef struct point {
58 * Points are stored using rational coordinates, with the same
59 * denominator for both coordinates.
66 * This structure is implicitly associated with a particular
67 * point set, so all it has to do is to store two point
68 * indices. It is required to store them in the order (lower,
69 * higher), i.e. a < b always.
75 int n; /* number of points */
79 int refcount; /* for deallocation */
80 tree234 *edges; /* stores `edge' structures */
85 int w, h; /* extent of coordinate system only */
88 int *crosses; /* mark edges which are crossed */
91 int completed, cheated, just_solved;
94 static int edgecmpC(const void *av, const void *bv)
96 const edge *a = (const edge *)av;
97 const edge *b = (const edge *)bv;
101 else if (a->a > b->a)
103 else if (a->b < b->b)
105 else if (a->b > b->b)
110 static int edgecmp(void *av, void *bv) { return edgecmpC(av, bv); }
112 static game_params *default_params(void)
114 game_params *ret = snew(game_params);
121 static int game_fetch_preset(int i, char **name, game_params **params)
128 case 0: n = 6; break;
129 case 1: n = 10; break;
130 case 2: n = 15; break;
131 case 3: n = 20; break;
132 case 4: n = 25; break;
133 default: return FALSE;
136 sprintf(buf, "%d points", n);
139 *params = ret = snew(game_params);
145 static void free_params(game_params *params)
150 static game_params *dup_params(game_params *params)
152 game_params *ret = snew(game_params);
153 *ret = *params; /* structure copy */
157 static void decode_params(game_params *params, char const *string)
159 params->n = atoi(string);
162 static char *encode_params(game_params *params, int full)
166 sprintf(buf, "%d", params->n);
171 static config_item *game_configure(game_params *params)
176 ret = snewn(3, config_item);
178 ret[0].name = "Number of points";
179 ret[0].type = C_STRING;
180 sprintf(buf, "%d", params->n);
181 ret[0].sval = dupstr(buf);
192 static game_params *custom_params(config_item *cfg)
194 game_params *ret = snew(game_params);
196 ret->n = atoi(cfg[0].sval);
201 static char *validate_params(game_params *params, int full)
204 return "Number of points must be at least four";
208 /* ----------------------------------------------------------------------
209 * Small number of 64-bit integer arithmetic operations, to prevent
210 * integer overflow at the very core of cross().
218 #define greater64(i,j) ( (i).hi>(j).hi || ((i).hi==(j).hi && (i).lo>(j).lo))
219 #define sign64(i) ((i).hi < 0 ? -1 : (i).hi==0 && (i).lo==0 ? 0 : +1)
221 static int64 mulu32to64(unsigned long x, unsigned long y)
223 unsigned long a, b, c, d, t;
226 a = (x & 0xFFFF) * (y & 0xFFFF);
227 b = (x & 0xFFFF) * (y >> 16);
228 c = (x >> 16) * (y & 0xFFFF);
229 d = (x >> 16) * (y >> 16);
232 ret.hi = d + (b >> 16) + (c >> 16);
233 t = (b & 0xFFFF) << 16;
237 t = (c & 0xFFFF) << 16;
242 #ifdef DIAGNOSTIC_VIA_LONGLONG
243 assert(((unsigned long long)ret.hi << 32) + ret.lo ==
244 (unsigned long long)x * y);
250 static int64 mul32to64(long x, long y)
254 #ifdef DIAGNOSTIC_VIA_LONGLONG
255 long long realret = (long long)x * y;
259 x = -x, sign = -sign;
261 y = -y, sign = -sign;
263 ret = mulu32to64(x, y);
272 #ifdef DIAGNOSTIC_VIA_LONGLONG
273 assert(((unsigned long long)ret.hi << 32) + ret.lo == realret);
279 static int64 dotprod64(long a, long b, long p, long q)
283 ab = mul32to64(a, b);
284 pq = mul32to64(p, q);
293 * Determine whether the line segments between a1 and a2, and
294 * between b1 and b2, intersect. We count it as an intersection if
295 * any of the endpoints lies _on_ the other line.
297 static int cross(point a1, point a2, point b1, point b2)
299 long b1x, b1y, b2x, b2y, px, py;
303 * The condition for crossing is that b1 and b2 are on opposite
304 * sides of the line a1-a2, and vice versa. We determine this
305 * by taking the dot product of b1-a1 with a vector
306 * perpendicular to a2-a1, and similarly with b2-a1, and seeing
307 * if they have different signs.
311 * Construct the vector b1-a1. We don't have to worry too much
312 * about the denominator, because we're only going to check the
313 * sign of this vector; we just need to get the numerator
316 b1x = b1.x * a1.d - a1.x * b1.d;
317 b1y = b1.y * a1.d - a1.y * b1.d;
318 /* Now construct b2-a1, and a vector perpendicular to a2-a1,
319 * in the same way. */
320 b2x = b2.x * a1.d - a1.x * b2.d;
321 b2y = b2.y * a1.d - a1.y * b2.d;
322 px = a1.y * a2.d - a2.y * a1.d;
323 py = a2.x * a1.d - a1.x * a2.d;
324 /* Take the dot products. Here we resort to 64-bit arithmetic. */
325 d1 = dotprod64(b1x, px, b1y, py);
326 d2 = dotprod64(b2x, px, b2y, py);
327 /* If they have the same non-zero sign, the lines do not cross. */
328 if ((sign64(d1) > 0 && sign64(d2) > 0) ||
329 (sign64(d1) < 0 && sign64(d2) < 0))
333 * If the dot products are both exactly zero, then the two line
334 * segments are collinear. At this point the intersection
335 * condition becomes whether or not they overlap within their
338 if (sign64(d1) == 0 && sign64(d2) == 0) {
339 /* Construct the vector a2-a1. */
340 px = a2.x * a1.d - a1.x * a2.d;
341 py = a2.y * a1.d - a1.y * a2.d;
342 /* Determine the dot products of b1-a1 and b2-a1 with this. */
343 d1 = dotprod64(b1x, px, b1y, py);
344 d2 = dotprod64(b2x, px, b2y, py);
345 /* If they're both strictly negative, the lines do not cross. */
346 if (sign64(d1) < 0 && sign64(d2) < 0)
348 /* Otherwise, take the dot product of a2-a1 with itself. If
349 * the other two dot products both exceed this, the lines do
351 d3 = dotprod64(px, px, py, py);
352 if (greater64(d1, d3) && greater64(d2, d3))
357 * We've eliminated the only important special case, and we
358 * have determined that b1 and b2 are on opposite sides of the
359 * line a1-a2. Now do the same thing the other way round and
362 b1x = a1.x * b1.d - b1.x * a1.d;
363 b1y = a1.y * b1.d - b1.y * a1.d;
364 b2x = a2.x * b1.d - b1.x * a2.d;
365 b2y = a2.y * b1.d - b1.y * a2.d;
366 px = b1.y * b2.d - b2.y * b1.d;
367 py = b2.x * b1.d - b1.x * b2.d;
368 d1 = dotprod64(b1x, px, b1y, py);
369 d2 = dotprod64(b2x, px, b2y, py);
370 if ((sign64(d1) > 0 && sign64(d2) > 0) ||
371 (sign64(d1) < 0 && sign64(d2) < 0))
375 * The lines must cross.
380 static unsigned long squarert(unsigned long n) {
381 unsigned long d, a, b, di;
385 b = 1L << 30; /* largest available power of 4 */
400 * Our solutions are arranged on a square grid big enough that n
401 * points occupy about 1/POINTDENSITY of the grid.
403 #define POINTDENSITY 3
405 #define COORDLIMIT(n) squarert((n) * POINTDENSITY)
407 static void addedge(tree234 *edges, int a, int b)
409 edge *e = snew(edge);
419 static int isedge(tree234 *edges, int a, int b)
428 return find234(edges, &e, NULL) != NULL;
431 typedef struct vertex {
436 static int vertcmpC(const void *av, const void *bv)
438 const vertex *a = (vertex *)av;
439 const vertex *b = (vertex *)bv;
441 if (a->param < b->param)
443 else if (a->param > b->param)
445 else if (a->vindex < b->vindex)
447 else if (a->vindex > b->vindex)
451 static int vertcmp(void *av, void *bv) { return vertcmpC(av, bv); }
454 * Construct point coordinates for n points arranged in a circle,
455 * within the bounding box (0,0) to (w,w).
457 static void make_circle(point *pts, int n, int w)
462 * First, decide on a denominator. Although in principle it
463 * would be nice to set this really high so as to finely
464 * distinguish all the points on the circle, I'm going to set
465 * it at a fixed size to prevent integer overflow problems.
467 d = PREFERRED_TILESIZE;
470 * Leave a little space outside the circle.
478 for (i = 0; i < n; i++) {
479 double angle = i * 2 * PI / n;
480 double x = r * sin(angle), y = - r * cos(angle);
481 pts[i].x = (long)(c + x + 0.5);
482 pts[i].y = (long)(c + y + 0.5);
487 static char *new_game_desc(game_params *params, random_state *rs,
488 char **aux, int interactive)
490 int n = params->n, i;
494 tree234 *edges, *vertices;
496 vertex *v, *vs, *vlist;
499 w = h = COORDLIMIT(n);
502 * Choose n points from this grid.
504 pts = snewn(n, point);
505 tmp = snewn(w*h, long);
506 for (i = 0; i < w*h; i++)
508 shuffle(tmp, w*h, sizeof(*tmp), rs);
509 for (i = 0; i < n; i++) {
510 pts[i].x = tmp[i] % w;
511 pts[i].y = tmp[i] / w;
517 * Now start adding edges between the points.
519 * At all times, we attempt to add an edge to the lowest-degree
520 * vertex we currently have, and we try the other vertices as
521 * candidate second endpoints in order of distance from this
522 * one. We stop as soon as we find an edge which
524 * (a) does not increase any vertex's degree beyond MAXDEGREE
525 * (b) does not cross any existing edges
526 * (c) does not intersect any actual point.
528 vs = snewn(n, vertex);
529 vertices = newtree234(vertcmp);
530 for (i = 0; i < n; i++) {
532 v->param = 0; /* in this tree, param is the degree */
536 edges = newtree234(edgecmp);
537 vlist = snewn(n, vertex);
541 for (i = 0; i < n; i++) {
542 v = index234(vertices, i);
545 if (v->param >= MAXDEGREE)
546 break; /* nothing left to add! */
549 * Sort the other vertices into order of their distance
550 * from this one. Don't bother looking below i, because
551 * we've already tried those edges the other way round.
552 * Also here we rule out target vertices with too high
553 * a degree, and (of course) ones to which we already
557 for (k = i+1; k < n; k++) {
558 vertex *kv = index234(vertices, k);
562 if (kv->param >= MAXDEGREE || isedge(edges, ki, j))
565 vlist[m].vindex = ki;
566 dx = pts[ki].x - pts[j].x;
567 dy = pts[ki].y - pts[j].y;
568 vlist[m].param = dx*dx + dy*dy;
572 qsort(vlist, m, sizeof(*vlist), vertcmpC);
574 for (k = 0; k < m; k++) {
576 int ki = vlist[k].vindex;
579 * Check to see whether this edge intersects any
580 * existing edge or point.
582 for (p = 0; p < n; p++)
583 if (p != ki && p != j && cross(pts[ki], pts[j],
588 for (p = 0; (e = index234(edges, p)) != NULL; p++)
589 if (e->a != ki && e->a != j &&
590 e->b != ki && e->b != j &&
591 cross(pts[ki], pts[j], pts[e->a], pts[e->b]))
597 * We're done! Add this edge, modify the degrees of
598 * the two vertices involved, and break.
600 addedge(edges, j, ki);
602 del234(vertices, vs+j);
604 add234(vertices, vs+j);
605 del234(vertices, vs+ki);
607 add234(vertices, vs+ki);
616 break; /* we're done. */
620 * That's our graph. Now shuffle the points, making sure that
621 * they come out with at least one crossed line when arranged
622 * in a circle (so that the puzzle isn't immediately solved!).
624 tmp = snewn(n, long);
625 for (i = 0; i < n; i++)
627 pts2 = snewn(n, point);
628 make_circle(pts2, n, w);
630 shuffle(tmp, n, sizeof(*tmp), rs);
631 for (i = 0; (e = index234(edges, i)) != NULL; i++) {
632 for (j = i+1; (e2 = index234(edges, j)) != NULL; j++) {
633 if (e2->a == e->a || e2->a == e->b ||
634 e2->b == e->a || e2->b == e->b)
636 if (cross(pts2[tmp[e2->a]], pts2[tmp[e2->b]],
637 pts2[tmp[e->a]], pts2[tmp[e->b]]))
644 break; /* we've found a crossing */
648 * We're done. Now encode the graph in a string format. Let's
649 * use a comma-separated list of dash-separated vertex number
650 * pairs, numbered from zero. We'll sort the list to prevent
663 for (i = 0; (e = index234(edges, i)) != NULL; i++) {
665 ea[i].a = min(tmp[e->a], tmp[e->b]);
666 ea[i].b = max(tmp[e->a], tmp[e->b]);
667 retlen += 1 + sprintf(buf, "%d-%d", ea[i].a, ea[i].b);
670 qsort(ea, m, sizeof(*ea), edgecmpC);
672 ret = snewn(retlen, char);
676 for (i = 0; i < m; i++) {
677 k += sprintf(ret + k, "%s%d-%d", sep, ea[i].a, ea[i].b);
686 * Encode the solution we started with as an aux_info string.
693 auxlen = 2; /* leading 'S' and trailing '\0' */
694 for (i = 0; i < n; i++) {
702 pts2[j].x += pts2[j].d / 2;
703 pts2[j].y += pts2[j].d / 2;
704 auxlen += sprintf(buf, ";P%d:%ld,%ld/%ld", i,
705 pts2[j].x, pts2[j].y, pts2[j].d);
708 auxstr = snewn(auxlen, char);
710 for (i = 0; i < n; i++)
711 k += sprintf(auxstr+k, ";P%d:%ld,%ld/%ld", i,
712 pts2[i].x, pts2[i].y, pts2[i].d);
720 freetree234(vertices);
722 while ((e = delpos234(edges, 0)) != NULL)
730 static char *validate_desc(game_params *params, char *desc)
736 if (a < 0 || a >= params->n)
737 return "Number out of range in game description";
738 while (*desc && isdigit((unsigned char)*desc)) desc++;
740 return "Expected '-' after number in game description";
741 desc++; /* eat dash */
743 if (b < 0 || b >= params->n)
744 return "Number out of range in game description";
745 while (*desc && isdigit((unsigned char)*desc)) desc++;
748 return "Expected ',' after number in game description";
749 desc++; /* eat comma */
756 static void mark_crossings(game_state *state)
762 #ifdef SHOW_CROSSINGS
763 for (i = 0; (e = index234(state->graph->edges, i)) != NULL; i++)
764 state->crosses[i] = FALSE;
768 * Check correctness: for every pair of edges, see whether they
771 for (i = 0; (e = index234(state->graph->edges, i)) != NULL; i++) {
772 for (j = i+1; (e2 = index234(state->graph->edges, j)) != NULL; j++) {
773 if (e2->a == e->a || e2->a == e->b ||
774 e2->b == e->a || e2->b == e->b)
776 if (cross(state->pts[e2->a], state->pts[e2->b],
777 state->pts[e->a], state->pts[e->b])) {
779 #ifdef SHOW_CROSSINGS
780 state->crosses[i] = state->crosses[j] = TRUE;
782 goto done; /* multi-level break - sorry */
789 * e == NULL if we've gone through all the edge pairs
790 * without finding a crossing.
792 #ifndef SHOW_CROSSINGS
796 state->completed = TRUE;
799 static game_state *new_game(midend *me, game_params *params, char *desc)
802 game_state *state = snew(game_state);
805 state->params = *params;
806 state->w = state->h = COORDLIMIT(n);
807 state->pts = snewn(n, point);
808 make_circle(state->pts, n, state->w);
809 state->graph = snew(struct graph);
810 state->graph->refcount = 1;
811 state->graph->edges = newtree234(edgecmp);
812 state->completed = state->cheated = state->just_solved = FALSE;
816 assert(a >= 0 && a < params->n);
817 while (*desc && isdigit((unsigned char)*desc)) desc++;
818 assert(*desc == '-');
819 desc++; /* eat dash */
821 assert(b >= 0 && b < params->n);
822 while (*desc && isdigit((unsigned char)*desc)) desc++;
824 assert(*desc == ',');
825 desc++; /* eat comma */
827 addedge(state->graph->edges, a, b);
830 #ifdef SHOW_CROSSINGS
831 state->crosses = snewn(count234(state->graph->edges), int);
832 mark_crossings(state); /* sets up `crosses' and `completed' */
838 static game_state *dup_game(game_state *state)
840 int n = state->params.n;
841 game_state *ret = snew(game_state);
843 ret->params = state->params;
846 ret->pts = snewn(n, point);
847 memcpy(ret->pts, state->pts, n * sizeof(point));
848 ret->graph = state->graph;
849 ret->graph->refcount++;
850 ret->completed = state->completed;
851 ret->cheated = state->cheated;
852 ret->just_solved = state->just_solved;
853 #ifdef SHOW_CROSSINGS
854 ret->crosses = snewn(count234(ret->graph->edges), int);
855 memcpy(ret->crosses, state->crosses,
856 count234(ret->graph->edges) * sizeof(int));
862 static void free_game(game_state *state)
864 if (--state->graph->refcount <= 0) {
866 while ((e = delpos234(state->graph->edges, 0)) != NULL)
868 freetree234(state->graph->edges);
875 static char *solve_game(game_state *state, game_state *currstate,
876 char *aux, char **error)
878 int n = state->params.n;
887 *error = "Solution not known for this puzzle";
892 * Decode the aux_info to get the original point positions.
894 pts = snewn(n, point);
896 for (i = 0; i < n; i++) {
899 int ret = sscanf(aux, ";P%d:%ld,%ld/%ld%n", &p, &x, &y, &d, &k);
900 if (ret != 4 || p != i) {
901 *error = "Internal error: aux_info badly formatted";
912 * Now go through eight possible symmetries of the point set.
913 * For each one, work out the sum of the Euclidean distances
914 * between the points' current positions and their new ones.
916 * We're squaring distances here, which means we're at risk of
917 * integer overflow. Fortunately, there's no real need to be
918 * massively careful about rounding errors, since this is a
919 * non-essential bit of the code; so I'll just work in floats
925 for (i = 0; i < 8; i++) {
928 matrix[0] = matrix[1] = matrix[2] = matrix[3] = 0;
929 matrix[i & 1] = (i & 2) ? +1 : -1;
930 matrix[3-(i&1)] = (i & 4) ? +1 : -1;
933 for (j = 0; j < n; j++) {
934 float px = (float)pts[j].x / pts[j].d;
935 float py = (float)pts[j].y / pts[j].d;
936 float sx = (float)currstate->pts[j].x / currstate->pts[j].d;
937 float sy = (float)currstate->pts[j].y / currstate->pts[j].d;
938 float cx = (float)currstate->w / 2;
939 float cy = (float)currstate->h / 2;
940 float ox, oy, dx, dy;
945 ox = matrix[0] * px + matrix[1] * py;
946 oy = matrix[2] * px + matrix[3] * py;
957 if (besti < 0 || bestd > d) {
966 * Now we know which symmetry is closest to the points' current
969 matrix[0] = matrix[1] = matrix[2] = matrix[3] = 0;
970 matrix[besti & 1] = (besti & 2) ? +1 : -1;
971 matrix[3-(besti&1)] = (besti & 4) ? +1 : -1;
974 ret = snewn(retsize, char);
979 for (i = 0; i < n; i++) {
980 float px = (float)pts[i].x / pts[i].d;
981 float py = (float)pts[i].y / pts[i].d;
982 float cx = (float)currstate->w / 2;
983 float cy = (float)currstate->h / 2;
990 ox = matrix[0] * px + matrix[1] * py;
991 oy = matrix[2] * px + matrix[3] * py;
997 * Use a fixed denominator of 2, because we know the
998 * original points were on an integer grid offset by 1/2.
1003 pts[i].x = (long)(ox + 0.5F);
1004 pts[i].y = (long)(oy + 0.5F);
1006 extra = sprintf(buf, ";P%d:%ld,%ld/%ld", i,
1007 pts[i].x, pts[i].y, pts[i].d);
1008 if (retlen + extra >= retsize) {
1009 retsize = retlen + extra + 256;
1010 ret = sresize(ret, retsize, char);
1012 strcpy(ret + retlen, buf);
1021 static int game_can_format_as_text_now(game_params *params)
1026 static char *game_text_format(game_state *state)
1032 int dragpoint; /* point being dragged; -1 if none */
1033 point newpoint; /* where it's been dragged to so far */
1034 int just_dragged; /* reset in game_changed_state */
1035 int just_moved; /* _set_ in game_changed_state */
1039 static game_ui *new_ui(game_state *state)
1041 game_ui *ui = snew(game_ui);
1043 ui->just_moved = ui->just_dragged = FALSE;
1047 static void free_ui(game_ui *ui)
1052 static char *encode_ui(game_ui *ui)
1057 static void decode_ui(game_ui *ui, char *encoding)
1061 static void game_changed_state(game_ui *ui, game_state *oldstate,
1062 game_state *newstate)
1065 ui->just_moved = ui->just_dragged;
1066 ui->just_dragged = FALSE;
1069 struct game_drawstate {
1075 static char *interpret_move(game_state *state, game_ui *ui, game_drawstate *ds,
1076 int x, int y, int button)
1078 int n = state->params.n;
1080 if (IS_MOUSE_DOWN(button)) {
1085 * Begin drag. We drag the vertex _nearest_ to the pointer,
1086 * just in case one is nearly on top of another and we want
1087 * to drag the latter. However, we drag nothing at all if
1088 * the nearest vertex is outside DRAG_THRESHOLD.
1093 for (i = 0; i < n; i++) {
1094 long px = state->pts[i].x * ds->tilesize / state->pts[i].d;
1095 long py = state->pts[i].y * ds->tilesize / state->pts[i].d;
1098 long d = dx*dx + dy*dy;
1100 if (best == -1 || bestd > d) {
1106 if (bestd <= DRAG_THRESHOLD * DRAG_THRESHOLD) {
1107 ui->dragpoint = best;
1110 ui->newpoint.d = ds->tilesize;
1114 } else if (IS_MOUSE_DRAG(button) && ui->dragpoint >= 0) {
1117 ui->newpoint.d = ds->tilesize;
1119 } else if (IS_MOUSE_RELEASE(button) && ui->dragpoint >= 0) {
1120 int p = ui->dragpoint;
1123 ui->dragpoint = -1; /* terminate drag, no matter what */
1126 * First, see if we're within range. The user can cancel a
1127 * drag by dragging the point right off the window.
1129 if (ui->newpoint.x < 0 ||
1130 ui->newpoint.x >= (long)state->w*ui->newpoint.d ||
1131 ui->newpoint.y < 0 ||
1132 ui->newpoint.y >= (long)state->h*ui->newpoint.d)
1136 * We aren't cancelling the drag. Construct a move string
1137 * indicating where this point is going to.
1139 sprintf(buf, "P%d:%ld,%ld/%ld", p,
1140 ui->newpoint.x, ui->newpoint.y, ui->newpoint.d);
1141 ui->just_dragged = TRUE;
1148 static game_state *execute_move(game_state *state, char *move)
1150 int n = state->params.n;
1153 game_state *ret = dup_game(state);
1155 ret->just_solved = FALSE;
1160 if (*move == ';') move++;
1161 ret->cheated = ret->just_solved = TRUE;
1164 sscanf(move+1, "%d:%ld,%ld/%ld%n", &p, &x, &y, &d, &k) == 4 &&
1165 p >= 0 && p < n && d > 0) {
1171 if (*move == ';') move++;
1178 mark_crossings(ret);
1183 /* ----------------------------------------------------------------------
1187 static void game_compute_size(game_params *params, int tilesize,
1190 *x = *y = COORDLIMIT(params->n) * tilesize;
1193 static void game_set_size(drawing *dr, game_drawstate *ds,
1194 game_params *params, int tilesize)
1196 ds->tilesize = tilesize;
1199 static float *game_colours(frontend *fe, int *ncolours)
1201 float *ret = snewn(3 * NCOLOURS, float);
1203 frontend_default_colour(fe, &ret[COL_BACKGROUND * 3]);
1205 ret[COL_LINE * 3 + 0] = 0.0F;
1206 ret[COL_LINE * 3 + 1] = 0.0F;
1207 ret[COL_LINE * 3 + 2] = 0.0F;
1209 #ifdef SHOW_CROSSINGS
1210 ret[COL_CROSSEDLINE * 3 + 0] = 1.0F;
1211 ret[COL_CROSSEDLINE * 3 + 1] = 0.0F;
1212 ret[COL_CROSSEDLINE * 3 + 2] = 0.0F;
1215 ret[COL_OUTLINE * 3 + 0] = 0.0F;
1216 ret[COL_OUTLINE * 3 + 1] = 0.0F;
1217 ret[COL_OUTLINE * 3 + 2] = 0.0F;
1219 ret[COL_POINT * 3 + 0] = 0.0F;
1220 ret[COL_POINT * 3 + 1] = 0.0F;
1221 ret[COL_POINT * 3 + 2] = 1.0F;
1223 ret[COL_DRAGPOINT * 3 + 0] = 1.0F;
1224 ret[COL_DRAGPOINT * 3 + 1] = 1.0F;
1225 ret[COL_DRAGPOINT * 3 + 2] = 1.0F;
1227 ret[COL_NEIGHBOUR * 3 + 0] = 1.0F;
1228 ret[COL_NEIGHBOUR * 3 + 1] = 0.0F;
1229 ret[COL_NEIGHBOUR * 3 + 2] = 0.0F;
1231 ret[COL_FLASH1 * 3 + 0] = 0.5F;
1232 ret[COL_FLASH1 * 3 + 1] = 0.5F;
1233 ret[COL_FLASH1 * 3 + 2] = 0.5F;
1235 ret[COL_FLASH2 * 3 + 0] = 1.0F;
1236 ret[COL_FLASH2 * 3 + 1] = 1.0F;
1237 ret[COL_FLASH2 * 3 + 2] = 1.0F;
1239 *ncolours = NCOLOURS;
1243 static game_drawstate *game_new_drawstate(drawing *dr, game_state *state)
1245 struct game_drawstate *ds = snew(struct game_drawstate);
1249 ds->x = snewn(state->params.n, long);
1250 ds->y = snewn(state->params.n, long);
1251 for (i = 0; i < state->params.n; i++)
1252 ds->x[i] = ds->y[i] = -1;
1259 static void game_free_drawstate(drawing *dr, game_drawstate *ds)
1266 static point mix(point a, point b, float distance)
1271 ret.x = (long)(a.x * b.d + distance * (b.x * a.d - a.x * b.d));
1272 ret.y = (long)(a.y * b.d + distance * (b.y * a.d - a.y * b.d));
1277 static void game_redraw(drawing *dr, game_drawstate *ds, game_state *oldstate,
1278 game_state *state, int dir, game_ui *ui,
1279 float animtime, float flashtime)
1284 int bg, points_moved;
1287 * There's no terribly sensible way to do partial redraws of
1288 * this game, so I'm going to have to resort to redrawing the
1289 * whole thing every time.
1293 bg = COL_BACKGROUND;
1294 else if ((int)(flashtime * 4 / FLASH_TIME) % 2 == 0)
1300 * To prevent excessive spinning on redraw during a completion
1301 * flash, we first check to see if _either_ the flash
1302 * background colour has changed _or_ at least one point has
1303 * moved _or_ a drag has begun or ended, and abandon the redraw
1304 * if neither is the case.
1306 * Also in this loop we work out the coordinates of all the
1307 * points for this redraw.
1309 points_moved = FALSE;
1310 for (i = 0; i < state->params.n; i++) {
1311 point p = state->pts[i];
1314 if (ui->dragpoint == i)
1318 p = mix(oldstate->pts[i], p, animtime / ui->anim_length);
1320 x = p.x * ds->tilesize / p.d;
1321 y = p.y * ds->tilesize / p.d;
1323 if (ds->x[i] != x || ds->y[i] != y)
1324 points_moved = TRUE;
1330 if (ds->bg == bg && ds->dragpoint == ui->dragpoint && !points_moved)
1331 return; /* nothing to do */
1333 ds->dragpoint = ui->dragpoint;
1336 game_compute_size(&state->params, ds->tilesize, &w, &h);
1337 draw_rect(dr, 0, 0, w, h, bg);
1343 for (i = 0; (e = index234(state->graph->edges, i)) != NULL; i++) {
1344 draw_line(dr, ds->x[e->a], ds->y[e->a], ds->x[e->b], ds->y[e->b],
1345 #ifdef SHOW_CROSSINGS
1346 (oldstate?oldstate:state)->crosses[i] ?
1355 * When dragging, we should not only vary the colours, but
1356 * leave the point being dragged until last.
1358 for (j = 0; j < 3; j++) {
1359 int thisc = (j == 0 ? COL_POINT :
1360 j == 1 ? COL_NEIGHBOUR : COL_DRAGPOINT);
1361 for (i = 0; i < state->params.n; i++) {
1364 if (ui->dragpoint == i) {
1366 } else if (ui->dragpoint >= 0 &&
1367 isedge(state->graph->edges, ui->dragpoint, i)) {
1374 #ifdef VERTEX_NUMBERS
1375 draw_circle(dr, ds->x[i], ds->y[i], DRAG_THRESHOLD, bg, bg);
1378 sprintf(buf, "%d", i);
1379 draw_text(dr, ds->x[i], ds->y[i], FONT_VARIABLE,
1381 ALIGN_VCENTRE|ALIGN_HCENTRE, c, buf);
1384 draw_circle(dr, ds->x[i], ds->y[i], CIRCLE_RADIUS,
1391 draw_update(dr, 0, 0, w, h);
1394 static float game_anim_length(game_state *oldstate, game_state *newstate,
1395 int dir, game_ui *ui)
1399 if ((dir < 0 ? oldstate : newstate)->just_solved)
1400 ui->anim_length = SOLVEANIM_TIME;
1402 ui->anim_length = ANIM_TIME;
1403 return ui->anim_length;
1406 static float game_flash_length(game_state *oldstate, game_state *newstate,
1407 int dir, game_ui *ui)
1409 if (!oldstate->completed && newstate->completed &&
1410 !oldstate->cheated && !newstate->cheated)
1415 static int game_timing_state(game_state *state, game_ui *ui)
1420 static void game_print_size(game_params *params, float *x, float *y)
1424 static void game_print(drawing *dr, game_state *state, int tilesize)
1429 #define thegame untangle
1432 const struct game thegame = {
1433 "Untangle", "games.untangle", "untangle",
1440 TRUE, game_configure, custom_params,
1448 FALSE, game_can_format_as_text_now, game_text_format,
1456 PREFERRED_TILESIZE, game_compute_size, game_set_size,
1459 game_free_drawstate,
1463 FALSE, FALSE, game_print_size, game_print,
1464 FALSE, /* wants_statusbar */
1465 FALSE, game_timing_state,
1466 SOLVE_ANIMATES, /* flags */