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 * - This puzzle, perhaps uniquely among the collection, could use
17 * support for non-aspect-ratio-preserving resizes. This would
18 * require some sort of fairly large redesign, unfortunately (since
19 * it would invalidate the basic assumption that puzzles' size
20 * requirements are adequately expressed by a single scalar tile
21 * size), and probably complicate the rest of the puzzles' API as a
22 * result. So I'm not sure I really want to do it.
24 * - It would be nice if we could somehow auto-detect a real `long
25 * long' type on the host platform and use it in place of my
26 * hand-hacked int64s. It'd be faster and more reliable.
39 #define CIRCLE_RADIUS 6
40 #define DRAG_THRESHOLD (CIRCLE_RADIUS * 2)
41 #define PREFERRED_TILESIZE 64
43 #define FLASH_TIME 0.30F
44 #define ANIM_TIME 0.13F
45 #define SOLVEANIM_TIME 0.50F
63 typedef struct point {
65 * Points are stored using rational coordinates, with the same
66 * denominator for both coordinates.
73 * This structure is implicitly associated with a particular
74 * point set, so all it has to do is to store two point
75 * indices. It is required to store them in the order (lower,
76 * higher), i.e. a < b always.
82 int n; /* number of points */
86 int refcount; /* for deallocation */
87 tree234 *edges; /* stores `edge' structures */
92 int w, h; /* extent of coordinate system only */
95 int *crosses; /* mark edges which are crossed */
98 int completed, cheated, just_solved;
101 static int edgecmpC(const void *av, const void *bv)
103 const edge *a = (const edge *)av;
104 const edge *b = (const edge *)bv;
108 else if (a->a > b->a)
110 else if (a->b < b->b)
112 else if (a->b > b->b)
117 static int edgecmp(void *av, void *bv) { return edgecmpC(av, bv); }
119 static game_params *default_params(void)
121 game_params *ret = snew(game_params);
128 static int game_fetch_preset(int i, char **name, game_params **params)
135 case 0: n = 6; break;
136 case 1: n = 10; break;
137 case 2: n = 15; break;
138 case 3: n = 20; break;
139 case 4: n = 25; break;
140 default: return FALSE;
143 sprintf(buf, "%d points", n);
146 *params = ret = snew(game_params);
152 static void free_params(game_params *params)
157 static game_params *dup_params(const game_params *params)
159 game_params *ret = snew(game_params);
160 *ret = *params; /* structure copy */
164 static void decode_params(game_params *params, char const *string)
166 params->n = atoi(string);
169 static char *encode_params(const game_params *params, int full)
173 sprintf(buf, "%d", params->n);
178 static config_item *game_configure(const game_params *params)
183 ret = snewn(3, config_item);
185 ret[0].name = "Number of points";
186 ret[0].type = C_STRING;
187 sprintf(buf, "%d", params->n);
188 ret[0].u.string.sval = dupstr(buf);
196 static game_params *custom_params(const config_item *cfg)
198 game_params *ret = snew(game_params);
200 ret->n = atoi(cfg[0].u.string.sval);
205 static const char *validate_params(const game_params *params, int full)
208 return "Number of points must be at least four";
212 /* ----------------------------------------------------------------------
213 * Small number of 64-bit integer arithmetic operations, to prevent
214 * integer overflow at the very core of cross().
222 #define greater64(i,j) ( (i).hi>(j).hi || ((i).hi==(j).hi && (i).lo>(j).lo))
223 #define sign64(i) ((i).hi < 0 ? -1 : (i).hi==0 && (i).lo==0 ? 0 : +1)
225 static int64 mulu32to64(unsigned long x, unsigned long y)
227 unsigned long a, b, c, d, t;
230 a = (x & 0xFFFF) * (y & 0xFFFF);
231 b = (x & 0xFFFF) * (y >> 16);
232 c = (x >> 16) * (y & 0xFFFF);
233 d = (x >> 16) * (y >> 16);
236 ret.hi = d + (b >> 16) + (c >> 16);
237 t = (b & 0xFFFF) << 16;
241 t = (c & 0xFFFF) << 16;
246 #ifdef DIAGNOSTIC_VIA_LONGLONG
247 assert(((unsigned long long)ret.hi << 32) + ret.lo ==
248 (unsigned long long)x * y);
254 static int64 mul32to64(long x, long y)
258 #ifdef DIAGNOSTIC_VIA_LONGLONG
259 long long realret = (long long)x * y;
263 x = -x, sign = -sign;
265 y = -y, sign = -sign;
267 ret = mulu32to64(x, y);
276 #ifdef DIAGNOSTIC_VIA_LONGLONG
277 assert(((unsigned long long)ret.hi << 32) + ret.lo == realret);
283 static int64 dotprod64(long a, long b, long p, long q)
287 ab = mul32to64(a, b);
288 pq = mul32to64(p, q);
297 * Determine whether the line segments between a1 and a2, and
298 * between b1 and b2, intersect. We count it as an intersection if
299 * any of the endpoints lies _on_ the other line.
301 static int cross(point a1, point a2, point b1, point b2)
303 long b1x, b1y, b2x, b2y, px, py;
307 * The condition for crossing is that b1 and b2 are on opposite
308 * sides of the line a1-a2, and vice versa. We determine this
309 * by taking the dot product of b1-a1 with a vector
310 * perpendicular to a2-a1, and similarly with b2-a1, and seeing
311 * if they have different signs.
315 * Construct the vector b1-a1. We don't have to worry too much
316 * about the denominator, because we're only going to check the
317 * sign of this vector; we just need to get the numerator
320 b1x = b1.x * a1.d - a1.x * b1.d;
321 b1y = b1.y * a1.d - a1.y * b1.d;
322 /* Now construct b2-a1, and a vector perpendicular to a2-a1,
323 * in the same way. */
324 b2x = b2.x * a1.d - a1.x * b2.d;
325 b2y = b2.y * a1.d - a1.y * b2.d;
326 px = a1.y * a2.d - a2.y * a1.d;
327 py = a2.x * a1.d - a1.x * a2.d;
328 /* Take the dot products. Here we resort to 64-bit arithmetic. */
329 d1 = dotprod64(b1x, px, b1y, py);
330 d2 = dotprod64(b2x, px, b2y, py);
331 /* If they have the same non-zero sign, the lines do not cross. */
332 if ((sign64(d1) > 0 && sign64(d2) > 0) ||
333 (sign64(d1) < 0 && sign64(d2) < 0))
337 * If the dot products are both exactly zero, then the two line
338 * segments are collinear. At this point the intersection
339 * condition becomes whether or not they overlap within their
342 if (sign64(d1) == 0 && sign64(d2) == 0) {
343 /* Construct the vector a2-a1. */
344 px = a2.x * a1.d - a1.x * a2.d;
345 py = a2.y * a1.d - a1.y * a2.d;
346 /* Determine the dot products of b1-a1 and b2-a1 with this. */
347 d1 = dotprod64(b1x, px, b1y, py);
348 d2 = dotprod64(b2x, px, b2y, py);
349 /* If they're both strictly negative, the lines do not cross. */
350 if (sign64(d1) < 0 && sign64(d2) < 0)
352 /* Otherwise, take the dot product of a2-a1 with itself. If
353 * the other two dot products both exceed this, the lines do
355 d3 = dotprod64(px, px, py, py);
356 if (greater64(d1, d3) && greater64(d2, d3))
361 * We've eliminated the only important special case, and we
362 * have determined that b1 and b2 are on opposite sides of the
363 * line a1-a2. Now do the same thing the other way round and
366 b1x = a1.x * b1.d - b1.x * a1.d;
367 b1y = a1.y * b1.d - b1.y * a1.d;
368 b2x = a2.x * b1.d - b1.x * a2.d;
369 b2y = a2.y * b1.d - b1.y * a2.d;
370 px = b1.y * b2.d - b2.y * b1.d;
371 py = b2.x * b1.d - b1.x * b2.d;
372 d1 = dotprod64(b1x, px, b1y, py);
373 d2 = dotprod64(b2x, px, b2y, py);
374 if ((sign64(d1) > 0 && sign64(d2) > 0) ||
375 (sign64(d1) < 0 && sign64(d2) < 0))
379 * The lines must cross.
384 static unsigned long squarert(unsigned long n) {
385 unsigned long d, a, b, di;
389 b = 1L << 30; /* largest available power of 4 */
404 * Our solutions are arranged on a square grid big enough that n
405 * points occupy about 1/POINTDENSITY of the grid.
407 #define POINTDENSITY 3
409 #define COORDLIMIT(n) squarert((n) * POINTDENSITY)
411 static void addedge(tree234 *edges, int a, int b)
413 edge *e = snew(edge);
423 static int isedge(tree234 *edges, int a, int b)
432 return find234(edges, &e, NULL) != NULL;
435 typedef struct vertex {
440 static int vertcmpC(const void *av, const void *bv)
442 const vertex *a = (vertex *)av;
443 const vertex *b = (vertex *)bv;
445 if (a->param < b->param)
447 else if (a->param > b->param)
449 else if (a->vindex < b->vindex)
451 else if (a->vindex > b->vindex)
455 static int vertcmp(void *av, void *bv) { return vertcmpC(av, bv); }
458 * Construct point coordinates for n points arranged in a circle,
459 * within the bounding box (0,0) to (w,w).
461 static void make_circle(point *pts, int n, int w)
466 * First, decide on a denominator. Although in principle it
467 * would be nice to set this really high so as to finely
468 * distinguish all the points on the circle, I'm going to set
469 * it at a fixed size to prevent integer overflow problems.
471 d = PREFERRED_TILESIZE;
474 * Leave a little space outside the circle.
482 for (i = 0; i < n; i++) {
483 double angle = i * 2 * PI / n;
484 double x = r * sin(angle), y = - r * cos(angle);
485 pts[i].x = (long)(c + x + 0.5);
486 pts[i].y = (long)(c + y + 0.5);
491 static char *new_game_desc(const game_params *params, random_state *rs,
492 char **aux, int interactive)
494 int n = params->n, i;
498 tree234 *edges, *vertices;
500 vertex *v, *vs, *vlist;
503 w = h = COORDLIMIT(n);
506 * Choose n points from this grid.
508 pts = snewn(n, point);
509 tmp = snewn(w*h, long);
510 for (i = 0; i < w*h; i++)
512 shuffle(tmp, w*h, sizeof(*tmp), rs);
513 for (i = 0; i < n; i++) {
514 pts[i].x = tmp[i] % w;
515 pts[i].y = tmp[i] / w;
521 * Now start adding edges between the points.
523 * At all times, we attempt to add an edge to the lowest-degree
524 * vertex we currently have, and we try the other vertices as
525 * candidate second endpoints in order of distance from this
526 * one. We stop as soon as we find an edge which
528 * (a) does not increase any vertex's degree beyond MAXDEGREE
529 * (b) does not cross any existing edges
530 * (c) does not intersect any actual point.
532 vs = snewn(n, vertex);
533 vertices = newtree234(vertcmp);
534 for (i = 0; i < n; i++) {
536 v->param = 0; /* in this tree, param is the degree */
540 edges = newtree234(edgecmp);
541 vlist = snewn(n, vertex);
545 for (i = 0; i < n; i++) {
546 v = index234(vertices, i);
549 if (v->param >= MAXDEGREE)
550 break; /* nothing left to add! */
553 * Sort the other vertices into order of their distance
554 * from this one. Don't bother looking below i, because
555 * we've already tried those edges the other way round.
556 * Also here we rule out target vertices with too high
557 * a degree, and (of course) ones to which we already
561 for (k = i+1; k < n; k++) {
562 vertex *kv = index234(vertices, k);
566 if (kv->param >= MAXDEGREE || isedge(edges, ki, j))
569 vlist[m].vindex = ki;
570 dx = pts[ki].x - pts[j].x;
571 dy = pts[ki].y - pts[j].y;
572 vlist[m].param = dx*dx + dy*dy;
576 qsort(vlist, m, sizeof(*vlist), vertcmpC);
578 for (k = 0; k < m; k++) {
580 int ki = vlist[k].vindex;
583 * Check to see whether this edge intersects any
584 * existing edge or point.
586 for (p = 0; p < n; p++)
587 if (p != ki && p != j && cross(pts[ki], pts[j],
592 for (p = 0; (e = index234(edges, p)) != NULL; p++)
593 if (e->a != ki && e->a != j &&
594 e->b != ki && e->b != j &&
595 cross(pts[ki], pts[j], pts[e->a], pts[e->b]))
601 * We're done! Add this edge, modify the degrees of
602 * the two vertices involved, and break.
604 addedge(edges, j, ki);
606 del234(vertices, vs+j);
608 add234(vertices, vs+j);
609 del234(vertices, vs+ki);
611 add234(vertices, vs+ki);
620 break; /* we're done. */
624 * That's our graph. Now shuffle the points, making sure that
625 * they come out with at least one crossed line when arranged
626 * in a circle (so that the puzzle isn't immediately solved!).
628 tmp = snewn(n, long);
629 for (i = 0; i < n; i++)
631 pts2 = snewn(n, point);
632 make_circle(pts2, n, w);
634 shuffle(tmp, n, sizeof(*tmp), rs);
635 for (i = 0; (e = index234(edges, i)) != NULL; i++) {
636 for (j = i+1; (e2 = index234(edges, j)) != NULL; j++) {
637 if (e2->a == e->a || e2->a == e->b ||
638 e2->b == e->a || e2->b == e->b)
640 if (cross(pts2[tmp[e2->a]], pts2[tmp[e2->b]],
641 pts2[tmp[e->a]], pts2[tmp[e->b]]))
648 break; /* we've found a crossing */
652 * We're done. Now encode the graph in a string format. Let's
653 * use a comma-separated list of dash-separated vertex number
654 * pairs, numbered from zero. We'll sort the list to prevent
667 for (i = 0; (e = index234(edges, i)) != NULL; i++) {
669 ea[i].a = min(tmp[e->a], tmp[e->b]);
670 ea[i].b = max(tmp[e->a], tmp[e->b]);
671 retlen += 1 + sprintf(buf, "%d-%d", ea[i].a, ea[i].b);
674 qsort(ea, m, sizeof(*ea), edgecmpC);
676 ret = snewn(retlen, char);
680 for (i = 0; i < m; i++) {
681 k += sprintf(ret + k, "%s%d-%d", sep, ea[i].a, ea[i].b);
690 * Encode the solution we started with as an aux_info string.
697 auxlen = 2; /* leading 'S' and trailing '\0' */
698 for (i = 0; i < n; i++) {
706 pts2[j].x += pts2[j].d / 2;
707 pts2[j].y += pts2[j].d / 2;
708 auxlen += sprintf(buf, ";P%d:%ld,%ld/%ld", i,
709 pts2[j].x, pts2[j].y, pts2[j].d);
712 auxstr = snewn(auxlen, char);
714 for (i = 0; i < n; i++)
715 k += sprintf(auxstr+k, ";P%d:%ld,%ld/%ld", i,
716 pts2[i].x, pts2[i].y, pts2[i].d);
724 freetree234(vertices);
726 while ((e = delpos234(edges, 0)) != NULL)
734 static const char *validate_desc(const game_params *params, const char *desc)
740 if (a < 0 || a >= params->n)
741 return "Number out of range in game description";
742 while (*desc && isdigit((unsigned char)*desc)) desc++;
744 return "Expected '-' after number in game description";
745 desc++; /* eat dash */
747 if (b < 0 || b >= params->n)
748 return "Number out of range in game description";
749 while (*desc && isdigit((unsigned char)*desc)) desc++;
752 return "Expected ',' after number in game description";
753 desc++; /* eat comma */
760 static void mark_crossings(game_state *state)
766 #ifdef SHOW_CROSSINGS
767 for (i = 0; (e = index234(state->graph->edges, i)) != NULL; i++)
768 state->crosses[i] = FALSE;
772 * Check correctness: for every pair of edges, see whether they
775 for (i = 0; (e = index234(state->graph->edges, i)) != NULL; i++) {
776 for (j = i+1; (e2 = index234(state->graph->edges, j)) != NULL; j++) {
777 if (e2->a == e->a || e2->a == e->b ||
778 e2->b == e->a || e2->b == e->b)
780 if (cross(state->pts[e2->a], state->pts[e2->b],
781 state->pts[e->a], state->pts[e->b])) {
783 #ifdef SHOW_CROSSINGS
784 state->crosses[i] = state->crosses[j] = TRUE;
786 goto done; /* multi-level break - sorry */
793 * e == NULL if we've gone through all the edge pairs
794 * without finding a crossing.
796 #ifndef SHOW_CROSSINGS
800 state->completed = TRUE;
803 static game_state *new_game(midend *me, const game_params *params,
807 game_state *state = snew(game_state);
810 state->params = *params;
811 state->w = state->h = COORDLIMIT(n);
812 state->pts = snewn(n, point);
813 make_circle(state->pts, n, state->w);
814 state->graph = snew(struct graph);
815 state->graph->refcount = 1;
816 state->graph->edges = newtree234(edgecmp);
817 state->completed = state->cheated = state->just_solved = FALSE;
821 assert(a >= 0 && a < params->n);
822 while (*desc && isdigit((unsigned char)*desc)) desc++;
823 assert(*desc == '-');
824 desc++; /* eat dash */
826 assert(b >= 0 && b < params->n);
827 while (*desc && isdigit((unsigned char)*desc)) desc++;
829 assert(*desc == ',');
830 desc++; /* eat comma */
832 addedge(state->graph->edges, a, b);
835 #ifdef SHOW_CROSSINGS
836 state->crosses = snewn(count234(state->graph->edges), int);
837 mark_crossings(state); /* sets up `crosses' and `completed' */
843 static game_state *dup_game(const game_state *state)
845 int n = state->params.n;
846 game_state *ret = snew(game_state);
848 ret->params = state->params;
851 ret->pts = snewn(n, point);
852 memcpy(ret->pts, state->pts, n * sizeof(point));
853 ret->graph = state->graph;
854 ret->graph->refcount++;
855 ret->completed = state->completed;
856 ret->cheated = state->cheated;
857 ret->just_solved = state->just_solved;
858 #ifdef SHOW_CROSSINGS
859 ret->crosses = snewn(count234(ret->graph->edges), int);
860 memcpy(ret->crosses, state->crosses,
861 count234(ret->graph->edges) * sizeof(int));
867 static void free_game(game_state *state)
869 if (--state->graph->refcount <= 0) {
871 while ((e = delpos234(state->graph->edges, 0)) != NULL)
873 freetree234(state->graph->edges);
880 static char *solve_game(const game_state *state, const game_state *currstate,
881 const char *aux, const char **error)
883 int n = state->params.n;
892 *error = "Solution not known for this puzzle";
897 * Decode the aux_info to get the original point positions.
899 pts = snewn(n, point);
901 for (i = 0; i < n; i++) {
904 int ret = sscanf(aux, ";P%d:%ld,%ld/%ld%n", &p, &x, &y, &d, &k);
905 if (ret != 4 || p != i) {
906 *error = "Internal error: aux_info badly formatted";
917 * Now go through eight possible symmetries of the point set.
918 * For each one, work out the sum of the Euclidean distances
919 * between the points' current positions and their new ones.
921 * We're squaring distances here, which means we're at risk of
922 * integer overflow. Fortunately, there's no real need to be
923 * massively careful about rounding errors, since this is a
924 * non-essential bit of the code; so I'll just work in floats
930 for (i = 0; i < 8; i++) {
933 matrix[0] = matrix[1] = matrix[2] = matrix[3] = 0;
934 matrix[i & 1] = (i & 2) ? +1 : -1;
935 matrix[3-(i&1)] = (i & 4) ? +1 : -1;
938 for (j = 0; j < n; j++) {
939 float px = (float)pts[j].x / pts[j].d;
940 float py = (float)pts[j].y / pts[j].d;
941 float sx = (float)currstate->pts[j].x / currstate->pts[j].d;
942 float sy = (float)currstate->pts[j].y / currstate->pts[j].d;
943 float cx = (float)currstate->w / 2;
944 float cy = (float)currstate->h / 2;
945 float ox, oy, dx, dy;
950 ox = matrix[0] * px + matrix[1] * py;
951 oy = matrix[2] * px + matrix[3] * py;
962 if (besti < 0 || bestd > d) {
971 * Now we know which symmetry is closest to the points' current
974 matrix[0] = matrix[1] = matrix[2] = matrix[3] = 0;
975 matrix[besti & 1] = (besti & 2) ? +1 : -1;
976 matrix[3-(besti&1)] = (besti & 4) ? +1 : -1;
979 ret = snewn(retsize, char);
984 for (i = 0; i < n; i++) {
985 float px = (float)pts[i].x / pts[i].d;
986 float py = (float)pts[i].y / pts[i].d;
987 float cx = (float)currstate->w / 2;
988 float cy = (float)currstate->h / 2;
995 ox = matrix[0] * px + matrix[1] * py;
996 oy = matrix[2] * px + matrix[3] * py;
1002 * Use a fixed denominator of 2, because we know the
1003 * original points were on an integer grid offset by 1/2.
1008 pts[i].x = (long)(ox + 0.5F);
1009 pts[i].y = (long)(oy + 0.5F);
1011 extra = sprintf(buf, ";P%d:%ld,%ld/%ld", i,
1012 pts[i].x, pts[i].y, pts[i].d);
1013 if (retlen + extra >= retsize) {
1014 retsize = retlen + extra + 256;
1015 ret = sresize(ret, retsize, char);
1017 strcpy(ret + retlen, buf);
1026 static int game_can_format_as_text_now(const game_params *params)
1031 static char *game_text_format(const game_state *state)
1037 int dragpoint; /* point being dragged; -1 if none */
1038 point newpoint; /* where it's been dragged to so far */
1039 int just_dragged; /* reset in game_changed_state */
1040 int just_moved; /* _set_ in game_changed_state */
1044 static game_ui *new_ui(const game_state *state)
1046 game_ui *ui = snew(game_ui);
1048 ui->just_moved = ui->just_dragged = FALSE;
1052 static void free_ui(game_ui *ui)
1057 static char *encode_ui(const game_ui *ui)
1062 static void decode_ui(game_ui *ui, const char *encoding)
1066 static void game_changed_state(game_ui *ui, const game_state *oldstate,
1067 const game_state *newstate)
1070 ui->just_moved = ui->just_dragged;
1071 ui->just_dragged = FALSE;
1074 struct game_drawstate {
1080 static char *interpret_move(const game_state *state, game_ui *ui,
1081 const game_drawstate *ds,
1082 int x, int y, int button)
1084 int n = state->params.n;
1086 if (IS_MOUSE_DOWN(button)) {
1091 * Begin drag. We drag the vertex _nearest_ to the pointer,
1092 * just in case one is nearly on top of another and we want
1093 * to drag the latter. However, we drag nothing at all if
1094 * the nearest vertex is outside DRAG_THRESHOLD.
1099 for (i = 0; i < n; i++) {
1100 long px = state->pts[i].x * ds->tilesize / state->pts[i].d;
1101 long py = state->pts[i].y * ds->tilesize / state->pts[i].d;
1104 long d = dx*dx + dy*dy;
1106 if (best == -1 || bestd > d) {
1112 if (bestd <= DRAG_THRESHOLD * DRAG_THRESHOLD) {
1113 ui->dragpoint = best;
1116 ui->newpoint.d = ds->tilesize;
1120 } else if (IS_MOUSE_DRAG(button) && ui->dragpoint >= 0) {
1123 ui->newpoint.d = ds->tilesize;
1125 } else if (IS_MOUSE_RELEASE(button) && ui->dragpoint >= 0) {
1126 int p = ui->dragpoint;
1129 ui->dragpoint = -1; /* terminate drag, no matter what */
1132 * First, see if we're within range. The user can cancel a
1133 * drag by dragging the point right off the window.
1135 if (ui->newpoint.x < 0 ||
1136 ui->newpoint.x >= (long)state->w*ui->newpoint.d ||
1137 ui->newpoint.y < 0 ||
1138 ui->newpoint.y >= (long)state->h*ui->newpoint.d)
1142 * We aren't cancelling the drag. Construct a move string
1143 * indicating where this point is going to.
1145 sprintf(buf, "P%d:%ld,%ld/%ld", p,
1146 ui->newpoint.x, ui->newpoint.y, ui->newpoint.d);
1147 ui->just_dragged = TRUE;
1154 static game_state *execute_move(const game_state *state, const char *move)
1156 int n = state->params.n;
1159 game_state *ret = dup_game(state);
1161 ret->just_solved = FALSE;
1166 if (*move == ';') move++;
1167 ret->cheated = ret->just_solved = TRUE;
1170 sscanf(move+1, "%d:%ld,%ld/%ld%n", &p, &x, &y, &d, &k) == 4 &&
1171 p >= 0 && p < n && d > 0) {
1177 if (*move == ';') move++;
1184 mark_crossings(ret);
1189 /* ----------------------------------------------------------------------
1193 static void game_compute_size(const game_params *params, int tilesize,
1196 *x = *y = COORDLIMIT(params->n) * tilesize;
1199 static void game_set_size(drawing *dr, game_drawstate *ds,
1200 const game_params *params, int tilesize)
1202 ds->tilesize = tilesize;
1205 static float *game_colours(frontend *fe, int *ncolours)
1207 float *ret = snewn(3 * NCOLOURS, float);
1210 * COL_BACKGROUND is what we use as the normal background colour.
1211 * Unusually, though, it isn't colour #0: COL_SYSBACKGROUND, a bit
1212 * darker, takes that place. This means that if the user resizes
1213 * an Untangle window so as to change its aspect ratio, the
1214 * still-square playable area will be distinguished from the dead
1217 game_mkhighlight(fe, ret, COL_BACKGROUND, -1, COL_SYSBACKGROUND);
1219 ret[COL_LINE * 3 + 0] = 0.0F;
1220 ret[COL_LINE * 3 + 1] = 0.0F;
1221 ret[COL_LINE * 3 + 2] = 0.0F;
1223 #ifdef SHOW_CROSSINGS
1224 ret[COL_CROSSEDLINE * 3 + 0] = 1.0F;
1225 ret[COL_CROSSEDLINE * 3 + 1] = 0.0F;
1226 ret[COL_CROSSEDLINE * 3 + 2] = 0.0F;
1229 ret[COL_OUTLINE * 3 + 0] = 0.0F;
1230 ret[COL_OUTLINE * 3 + 1] = 0.0F;
1231 ret[COL_OUTLINE * 3 + 2] = 0.0F;
1233 ret[COL_POINT * 3 + 0] = 0.0F;
1234 ret[COL_POINT * 3 + 1] = 0.0F;
1235 ret[COL_POINT * 3 + 2] = 1.0F;
1237 ret[COL_DRAGPOINT * 3 + 0] = 1.0F;
1238 ret[COL_DRAGPOINT * 3 + 1] = 1.0F;
1239 ret[COL_DRAGPOINT * 3 + 2] = 1.0F;
1241 ret[COL_NEIGHBOUR * 3 + 0] = 1.0F;
1242 ret[COL_NEIGHBOUR * 3 + 1] = 0.0F;
1243 ret[COL_NEIGHBOUR * 3 + 2] = 0.0F;
1245 ret[COL_FLASH1 * 3 + 0] = 0.5F;
1246 ret[COL_FLASH1 * 3 + 1] = 0.5F;
1247 ret[COL_FLASH1 * 3 + 2] = 0.5F;
1249 ret[COL_FLASH2 * 3 + 0] = 1.0F;
1250 ret[COL_FLASH2 * 3 + 1] = 1.0F;
1251 ret[COL_FLASH2 * 3 + 2] = 1.0F;
1253 *ncolours = NCOLOURS;
1257 static game_drawstate *game_new_drawstate(drawing *dr, const game_state *state)
1259 struct game_drawstate *ds = snew(struct game_drawstate);
1263 ds->x = snewn(state->params.n, long);
1264 ds->y = snewn(state->params.n, long);
1265 for (i = 0; i < state->params.n; i++)
1266 ds->x[i] = ds->y[i] = -1;
1273 static void game_free_drawstate(drawing *dr, game_drawstate *ds)
1280 static point mix(point a, point b, float distance)
1285 ret.x = (long)(a.x * b.d + distance * (b.x * a.d - a.x * b.d));
1286 ret.y = (long)(a.y * b.d + distance * (b.y * a.d - a.y * b.d));
1291 static void game_redraw(drawing *dr, game_drawstate *ds,
1292 const game_state *oldstate, const game_state *state,
1293 int dir, const game_ui *ui,
1294 float animtime, float flashtime)
1299 int bg, points_moved;
1302 * There's no terribly sensible way to do partial redraws of
1303 * this game, so I'm going to have to resort to redrawing the
1304 * whole thing every time.
1308 bg = COL_BACKGROUND;
1309 else if ((int)(flashtime * 4 / FLASH_TIME) % 2 == 0)
1315 * To prevent excessive spinning on redraw during a completion
1316 * flash, we first check to see if _either_ the flash
1317 * background colour has changed _or_ at least one point has
1318 * moved _or_ a drag has begun or ended, and abandon the redraw
1319 * if neither is the case.
1321 * Also in this loop we work out the coordinates of all the
1322 * points for this redraw.
1324 points_moved = FALSE;
1325 for (i = 0; i < state->params.n; i++) {
1326 point p = state->pts[i];
1329 if (ui->dragpoint == i)
1333 p = mix(oldstate->pts[i], p, animtime / ui->anim_length);
1335 x = p.x * ds->tilesize / p.d;
1336 y = p.y * ds->tilesize / p.d;
1338 if (ds->x[i] != x || ds->y[i] != y)
1339 points_moved = TRUE;
1345 if (ds->bg == bg && ds->dragpoint == ui->dragpoint && !points_moved)
1346 return; /* nothing to do */
1348 ds->dragpoint = ui->dragpoint;
1351 game_compute_size(&state->params, ds->tilesize, &w, &h);
1352 draw_rect(dr, 0, 0, w, h, bg);
1358 for (i = 0; (e = index234(state->graph->edges, i)) != NULL; i++) {
1359 draw_line(dr, ds->x[e->a], ds->y[e->a], ds->x[e->b], ds->y[e->b],
1360 #ifdef SHOW_CROSSINGS
1361 (oldstate?oldstate:state)->crosses[i] ?
1370 * When dragging, we should not only vary the colours, but
1371 * leave the point being dragged until last.
1373 for (j = 0; j < 3; j++) {
1374 int thisc = (j == 0 ? COL_POINT :
1375 j == 1 ? COL_NEIGHBOUR : COL_DRAGPOINT);
1376 for (i = 0; i < state->params.n; i++) {
1379 if (ui->dragpoint == i) {
1381 } else if (ui->dragpoint >= 0 &&
1382 isedge(state->graph->edges, ui->dragpoint, i)) {
1389 #ifdef VERTEX_NUMBERS
1390 draw_circle(dr, ds->x[i], ds->y[i], DRAG_THRESHOLD, bg, bg);
1393 sprintf(buf, "%d", i);
1394 draw_text(dr, ds->x[i], ds->y[i], FONT_VARIABLE,
1396 ALIGN_VCENTRE|ALIGN_HCENTRE, c, buf);
1399 draw_circle(dr, ds->x[i], ds->y[i], CIRCLE_RADIUS,
1406 draw_update(dr, 0, 0, w, h);
1409 static float game_anim_length(const game_state *oldstate,
1410 const game_state *newstate, int dir, game_ui *ui)
1414 if ((dir < 0 ? oldstate : newstate)->just_solved)
1415 ui->anim_length = SOLVEANIM_TIME;
1417 ui->anim_length = ANIM_TIME;
1418 return ui->anim_length;
1421 static float game_flash_length(const game_state *oldstate,
1422 const game_state *newstate, int dir, game_ui *ui)
1424 if (!oldstate->completed && newstate->completed &&
1425 !oldstate->cheated && !newstate->cheated)
1430 static int game_status(const game_state *state)
1432 return state->completed ? +1 : 0;
1435 static int game_timing_state(const game_state *state, game_ui *ui)
1440 static void game_print_size(const game_params *params, float *x, float *y)
1444 static void game_print(drawing *dr, const game_state *state, int tilesize)
1449 #define thegame untangle
1452 const struct game thegame = {
1453 "Untangle", "games.untangle", "untangle",
1455 game_fetch_preset, NULL,
1460 TRUE, game_configure, custom_params,
1468 FALSE, game_can_format_as_text_now, game_text_format,
1476 PREFERRED_TILESIZE, game_compute_size, game_set_size,
1479 game_free_drawstate,
1484 FALSE, FALSE, game_print_size, game_print,
1485 FALSE, /* wants_statusbar */
1486 FALSE, game_timing_state,
1487 SOLVE_ANIMATES, /* flags */