untangle.c

   1 /*
   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.
   6  *
   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.
  11  */
  12
  13 /*
  14  * TODO:
  15  *
  16  *  - Docs and checklist etc
  17  *  - Any way we can speed up redraws on GTK? Uck.
  18  */
  19
  20 #include <stdio.h>
  21 #include <stdlib.h>
  22 #include <string.h>
  23 #include <assert.h>
  24 #include <ctype.h>
  25 #include <math.h>
  26
  27 #include "puzzles.h"
  28 #include "tree234.h"
  29
  30 #define CIRCLE_RADIUS 6
  31 #define DRAG_THRESHOLD (CIRCLE_RADIUS * 2)
  32 #define PREFERRED_TILESIZE 64
  33
  34 #define FLASH_TIME 0.30F
  35 #define ANIM_TIME 0.13F
  36 #define SOLVEANIM_TIME 0.50F
  37
  38 enum {
  39     COL_BACKGROUND,
  40     COL_LINE,
  41     COL_OUTLINE,
  42     COL_POINT,
  43     COL_DRAGPOINT,
  44     COL_NEIGHBOUR,
  45     COL_FLASH1,
  46     COL_FLASH2,
  47     NCOLOURS
  48 };
  49
  50 typedef struct point {
  51     /*
  52      * Points are stored using rational coordinates, with the same
  53      * denominator for both coordinates.
  54      */
  55     long x, y, d;
  56 } point;
  57
  58 typedef struct edge {
  59     /*
  60      * This structure is implicitly associated with a particular
  61      * point set, so all it has to do is to store two point
  62      * indices. It is required to store them in the order (lower,
  63      * higher), i.e. a < b always.
  64      */
  65     int a, b;
  66 } edge;
  67
  68 struct game_params {
  69     int n;                             /* number of points */
  70 };
  71
  72 struct graph {
  73     int refcount;                      /* for deallocation */
  74     tree234 *edges;                    /* stores `edge' structures */
  75 };
  76
  77 struct game_state {
  78     game_params params;
  79     int w, h;                          /* extent of coordinate system only */
  80     point *pts;
  81     struct graph *graph;
  82     int completed, cheated, just_solved;
  83 };
  84
  85 static int edgecmpC(const void *av, const void *bv)
  86 {
  87     const edge *a = (const edge *)av;
  88     const edge *b = (const edge *)bv;
  89
  90     if (a->a < b->a)
  91         return -1;
  92     else if (a->a > b->a)
  93         return +1;
  94     else if (a->b < b->b)
  95         return -1;
  96     else if (a->b > b->b)
  97         return +1;
  98     return 0;
  99 }
 100
 101 static int edgecmp(void *av, void *bv) { return edgecmpC(av, bv); }
 102
 103 static game_params *default_params(void)
 104 {
 105     game_params *ret = snew(game_params);
 106
 107     ret->n = 10;
 108
 109     return ret;
 110 }
 111
 112 static int game_fetch_preset(int i, char **name, game_params **params)
 113 {
 114     game_params *ret;
 115     int n;
 116     char buf[80];
 117
 118     switch (i) {
 119       case 0: n = 6; break;
 120       case 1: n = 10; break;
 121       case 2: n = 15; break;
 122       case 3: n = 20; break;
 123       case 4: n = 25; break;
 124       default: return FALSE;
 125     }
 126
 127     sprintf(buf, "%d points", n);
 128     *name = dupstr(buf);
 129
 130     *params = ret = snew(game_params);
 131     ret->n = n;
 132
 133     return TRUE;
 134 }
 135
 136 static void free_params(game_params *params)
 137 {
 138     sfree(params);
 139 }
 140
 141 static game_params *dup_params(game_params *params)
 142 {
 143     game_params *ret = snew(game_params);
 144     *ret = *params;                    /* structure copy */
 145     return ret;
 146 }
 147
 148 static void decode_params(game_params *params, char const *string)
 149 {
 150     params->n = atoi(string);
 151 }
 152
 153 static char *encode_params(game_params *params, int full)
 154 {
 155     char buf[80];
 156
 157     sprintf(buf, "%d", params->n);
 158
 159     return dupstr(buf);
 160 }
 161
 162 static config_item *game_configure(game_params *params)
 163 {
 164     config_item *ret;
 165     char buf[80];
 166
 167     ret = snewn(3, config_item);
 168
 169     ret[0].name = "Number of points";
 170     ret[0].type = C_STRING;
 171     sprintf(buf, "%d", params->n);
 172     ret[0].sval = dupstr(buf);
 173     ret[0].ival = 0;
 174
 175     ret[1].name = NULL;
 176     ret[1].type = C_END;
 177     ret[1].sval = NULL;
 178     ret[1].ival = 0;
 179
 180     return ret;
 181 }
 182
 183 static game_params *custom_params(config_item *cfg)
 184 {
 185     game_params *ret = snew(game_params);
 186
 187     ret->n = atoi(cfg[0].sval);
 188
 189     return ret;
 190 }
 191
 192 static char *validate_params(game_params *params, int full)
 193 {
 194     if (params->n < 4)
 195         return "Number of points must be at least four";
 196     return NULL;
 197 }
 198
 199 /*
 200  * Determine whether the line segments between a1 and a2, and
 201  * between b1 and b2, intersect. We count it as an intersection if
 202  * any of the endpoints lies _on_ the other line.
 203  */
 204 static int cross(point a1, point a2, point b1, point b2)
 205 {
 206     long b1x, b1y, b2x, b2y, px, py, d1, d2, d3;
 207
 208     /*
 209      * The condition for crossing is that b1 and b2 are on opposite
 210      * sides of the line a1-a2, and vice versa. We determine this
 211      * by taking the dot product of b1-a1 with a vector
 212      * perpendicular to a2-a1, and similarly with b2-a1, and seeing
 213      * if they have different signs.
 214      */
 215
 216     /*
 217      * Construct the vector b1-a1. We don't have to worry too much
 218      * about the denominator, because we're only going to check the
 219      * sign of this vector; we just need to get the numerator
 220      * right.
 221      */
 222     b1x = b1.x * a1.d - a1.x * b1.d;
 223     b1y = b1.y * a1.d - a1.y * b1.d;
 224     /* Now construct b2-a1, and a vector perpendicular to a2-a1,
 225      * in the same way. */
 226     b2x = b2.x * a1.d - a1.x * b2.d;
 227     b2y = b2.y * a1.d - a1.y * b2.d;
 228     px = a1.y * a2.d - a2.y * a1.d;
 229     py = a2.x * a1.d - a1.x * a2.d;
 230     /* Take the dot products. */
 231     d1 = b1x * px + b1y * py;
 232     d2 = b2x * px + b2y * py;
 233     /* If they have the same non-zero sign, the lines do not cross. */
 234     if ((d1 > 0 && d2 > 0) || (d1 < 0 && d2 < 0))
 235         return FALSE;
 236
 237     /*
 238      * If the dot products are both exactly zero, then the two line
 239      * segments are collinear. At this point the intersection
 240      * condition becomes whether or not they overlap within their
 241      * line.
 242      */
 243     if (d1 == 0 && d2 == 0) {
 244         /* Construct the vector a2-a1. */
 245         px = a2.x * a1.d - a1.x * a2.d;
 246         py = a2.y * a1.d - a1.y * a2.d;
 247         /* Determine the dot products of b1-a1 and b2-a1 with this. */
 248         d1 = b1x * px + b1y * py;
 249         d2 = b2x * px + b2y * py;
 250         /* If they're both strictly negative, the lines do not cross. */
 251         if (d1 < 0 && d2 < 0)
 252             return FALSE;
 253         /* Otherwise, take the dot product of a2-a1 with itself. If
 254          * the other two dot products both exceed this, the lines do
 255          * not cross. */
 256         d3 = px * px + py * py;
 257         if (d1 > d3 && d2 > d3)
 258             return FALSE;
 259     }
 260
 261     /*
 262      * We've eliminated the only important special case, and we
 263      * have determined that b1 and b2 are on opposite sides of the
 264      * line a1-a2. Now do the same thing the other way round and
 265      * we're done.
 266      */
 267     b1x = a1.x * b1.d - b1.x * a1.d;
 268     b1y = a1.y * b1.d - b1.y * a1.d;
 269     b2x = a2.x * b1.d - b1.x * a2.d;
 270     b2y = a2.y * b1.d - b1.y * a2.d;
 271     px = b1.y * b2.d - b2.y * b1.d;
 272     py = b2.x * b1.d - b1.x * b2.d;
 273     d1 = b1x * px + b1y * py;
 274     d2 = b2x * px + b2y * py;
 275     if ((d1 > 0 && d2 > 0) || (d1 < 0 && d2 < 0))
 276         return FALSE;
 277
 278     /*
 279      * The lines must cross.
 280      */
 281     return TRUE;
 282 }
 283
 284 static unsigned long squarert(unsigned long n) {
 285     unsigned long d, a, b, di;
 286
 287     d = n;
 288     a = 0;
 289     b = 1L << 30;                      /* largest available power of 4 */
 290     do {
 291         a >>= 1;
 292         di = 2*a + b;
 293         if (di <= d) {
 294             d -= di;
 295             a += b;
 296         }
 297         b >>= 2;
 298     } while (b);
 299
 300     return a;
 301 }
 302
 303 /*
 304  * Our solutions are arranged on a square grid big enough that n
 305  * points occupy about 1/POINTDENSITY of the grid.
 306  */
 307 #define POINTDENSITY 3
 308 #define MAXDEGREE 4
 309 #define COORDLIMIT(n) squarert((n) * POINTDENSITY)
 310
 311 static void addedge(tree234 *edges, int a, int b)
 312 {
 313     edge *e = snew(edge);
 314
 315     assert(a != b);
 316
 317     e->a = min(a, b);
 318     e->b = max(a, b);
 319
 320     add234(edges, e);
 321 }
 322
 323 static int isedge(tree234 *edges, int a, int b)
 324 {
 325     edge e;
 326
 327     assert(a != b);
 328
 329     e.a = min(a, b);
 330     e.b = max(a, b);
 331
 332     return find234(edges, &e, NULL) != NULL;
 333 }
 334
 335 typedef struct vertex {
 336     int param;
 337     int vindex;
 338 } vertex;
 339
 340 static int vertcmpC(const void *av, const void *bv)
 341 {
 342     const vertex *a = (vertex *)av;
 343     const vertex *b = (vertex *)bv;
 344
 345     if (a->param < b->param)
 346         return -1;
 347     else if (a->param > b->param)
 348         return +1;
 349     else if (a->vindex < b->vindex)
 350         return -1;
 351     else if (a->vindex > b->vindex)
 352         return +1;
 353     return 0;
 354 }
 355 static int vertcmp(void *av, void *bv) { return vertcmpC(av, bv); }
 356
 357 /*
 358  * Construct point coordinates for n points arranged in a circle,
 359  * within the bounding box (0,0) to (w,w).
 360  */
 361 static void make_circle(point *pts, int n, int w)
 362 {
 363     long d, r, c, i;
 364
 365     /*
 366      * First, decide on a denominator. Although in principle it
 367      * would be nice to set this really high so as to finely
 368      * distinguish all the points on the circle, I'm going to set
 369      * it at a fixed size to prevent integer overflow problems.
 370      */
 371     d = PREFERRED_TILESIZE;
 372
 373     /*
 374      * Leave a little space outside the circle.
 375      */
 376     c = d * w / 2;
 377     r = d * w * 3 / 7;
 378
 379     /*
 380      * Place the points.
 381      */
 382     for (i = 0; i < n; i++) {
 383         double angle = i * 2 * PI / n;
 384         double x = r * sin(angle), y = - r * cos(angle);
 385         pts[i].x = (long)(c + x + 0.5);
 386         pts[i].y = (long)(c + y + 0.5);
 387         pts[i].d = d;
 388     }
 389 }
 390
 391 static char *new_game_desc(game_params *params, random_state *rs,
 392                            char **aux, int interactive)
 393 {
 394     int n = params->n, i;
 395     long w, h, j, k, m;
 396     point *pts, *pts2;
 397     long *tmp;
 398     tree234 *edges, *vertices;
 399     edge *e, *e2;
 400     vertex *v, *vs, *vlist;
 401     char *ret;
 402
 403     w = h = COORDLIMIT(n);
 404
 405     /*
 406      * Choose n points from this grid.
 407      */
 408     pts = snewn(n, point);
 409     tmp = snewn(w*h, long);
 410     for (i = 0; i < w*h; i++)
 411         tmp[i] = i;
 412     shuffle(tmp, w*h, sizeof(*tmp), rs);
 413     for (i = 0; i < n; i++) {
 414         pts[i].x = tmp[i] % w;
 415         pts[i].y = tmp[i] / w;
 416         pts[i].d = 1;
 417     }
 418     sfree(tmp);
 419
 420     /*
 421      * Now start adding edges between the points.
 422      *
 423      * At all times, we attempt to add an edge to the lowest-degree
 424      * vertex we currently have, and we try the other vertices as
 425      * candidate second endpoints in order of distance from this
 426      * one. We stop as soon as we find an edge which
 427      *
 428      *  (a) does not increase any vertex's degree beyond MAXDEGREE
 429      *  (b) does not cross any existing edges
 430      *  (c) does not intersect any actual point.
 431      */
 432     vs = snewn(n, vertex);
 433     vertices = newtree234(vertcmp);
 434     for (i = 0; i < n; i++) {
 435         v = vs + i;
 436         v->param = 0;                  /* in this tree, param is the degree */
 437         v->vindex = i;
 438         add234(vertices, v);
 439     }
 440     edges = newtree234(edgecmp);
 441     vlist = snewn(n, vertex);
 442     while (1) {
 443         int added = FALSE;
 444
 445         for (i = 0; i < n; i++) {
 446             v = index234(vertices, i);
 447             j = v->vindex;
 448
 449             if (v->param >= MAXDEGREE)
 450                 break;                 /* nothing left to add! */
 451
 452             /*
 453              * Sort the other vertices into order of their distance
 454              * from this one. Don't bother looking below i, because
 455              * we've already tried those edges the other way round.
 456              * Also here we rule out target vertices with too high
 457              * a degree, and (of course) ones to which we already
 458              * have an edge.
 459              */
 460             m = 0;
 461             for (k = i+1; k < n; k++) {
 462                 vertex *kv = index234(vertices, k);
 463                 int ki = kv->vindex;
 464                 int dx, dy;
 465
 466                 if (kv->param >= MAXDEGREE || isedge(edges, ki, j))
 467                     continue;
 468
 469                 vlist[m].vindex = ki;
 470                 dx = pts[ki].x - pts[j].x;
 471                 dy = pts[ki].y - pts[j].y;
 472                 vlist[m].param = dx*dx + dy*dy;
 473                 m++;
 474             }
 475
 476             qsort(vlist, m, sizeof(*vlist), vertcmpC);
 477
 478             for (k = 0; k < m; k++) {
 479                 int p;
 480                 int ki = vlist[k].vindex;
 481
 482                 /*
 483                  * Check to see whether this edge intersects any
 484                  * existing edge or point.
 485                  */
 486                 for (p = 0; p < n; p++)
 487                     if (p != ki && p != j && cross(pts[ki], pts[j],
 488                                                    pts[p], pts[p]))
 489                         break;
 490                 if (p < n)
 491                     continue;
 492                 for (p = 0; (e = index234(edges, p)) != NULL; p++)
 493                     if (e->a != ki && e->a != j &&
 494                         e->b != ki && e->b != j &&
 495                         cross(pts[ki], pts[j], pts[e->a], pts[e->b]))
 496                         break;
 497                 if (e)
 498                     continue;
 499
 500                 /*
 501                  * We're done! Add this edge, modify the degrees of
 502                  * the two vertices involved, and break.
 503                  */
 504                 addedge(edges, j, ki);
 505                 added = TRUE;
 506                 del234(vertices, vs+j);
 507                 vs[j].param++;
 508                 add234(vertices, vs+j);
 509                 del234(vertices, vs+ki);
 510                 vs[ki].param++;
 511                 add234(vertices, vs+ki);
 512                 break;
 513             }
 514
 515             if (k < m)
 516                 break;
 517         }
 518
 519         if (!added)
 520             break;                     /* we're done. */
 521     }
 522
 523     /*
 524      * That's our graph. Now shuffle the points, making sure that
 525      * they come out with at least one crossed line when arranged
 526      * in a circle (so that the puzzle isn't immediately solved!).
 527      */
 528     tmp = snewn(n, long);
 529     for (i = 0; i < n; i++)
 530         tmp[i] = i;
 531     pts2 = snewn(n, point);
 532     make_circle(pts2, n, w);
 533     while (1) {
 534         shuffle(tmp, n, sizeof(*tmp), rs);
 535         for (i = 0; (e = index234(edges, i)) != NULL; i++) {
 536             for (j = i+1; (e2 = index234(edges, j)) != NULL; j++) {
 537                 if (e2->a == e->a || e2->a == e->b ||
 538                     e2->b == e->a || e2->b == e->b)
 539                     continue;
 540                 if (cross(pts2[tmp[e2->a]], pts2[tmp[e2->b]],
 541                           pts2[tmp[e->a]], pts2[tmp[e->b]]))
 542                     break;
 543             }
 544             if (e2)
 545                 break;
 546         }
 547         if (e)
 548             break;                     /* we've found a crossing */
 549     }
 550
 551     /*
 552      * We're done. Now encode the graph in a string format. Let's
 553      * use a comma-separated list of dash-separated vertex number
 554      * pairs, numbered from zero. We'll sort the list to prevent
 555      * side channels.
 556      */
 557     ret = NULL;
 558     {
 559         char *sep;
 560         char buf[80];
 561         int retlen;
 562         edge *ea;
 563
 564         retlen = 0;
 565         m = count234(edges);
 566         ea = snewn(m, edge);
 567         for (i = 0; (e = index234(edges, i)) != NULL; i++) {
 568             assert(i < m);
 569             ea[i].a = min(tmp[e->a], tmp[e->b]);
 570             ea[i].b = max(tmp[e->a], tmp[e->b]);
 571             retlen += 1 + sprintf(buf, "%d-%d", ea[i].a, ea[i].b);
 572         }
 573         assert(i == m);
 574         qsort(ea, m, sizeof(*ea), edgecmpC);
 575
 576         ret = snewn(retlen, char);
 577         sep = "";
 578         k = 0;
 579
 580         for (i = 0; i < m; i++) {
 581             k += sprintf(ret + k, "%s%d-%d", sep, ea[i].a, ea[i].b);
 582             sep = ",";
 583         }
 584         assert(k < retlen);
 585
 586         sfree(ea);
 587     }
 588
 589     /*
 590      * Encode the solution we started with as an aux_info string.
 591      */
 592     {
 593         char buf[80];
 594         char *auxstr;
 595         int auxlen;
 596
 597         auxlen = 2;                    /* leading 'S' and trailing '\0' */
 598         for (i = 0; i < n; i++) {
 599             j = tmp[i];
 600             pts2[j] = pts[i];
 601             if (pts2[j].d & 1) {
 602                 pts2[j].x *= 2;
 603                 pts2[j].y *= 2;
 604                 pts2[j].d *= 2;
 605             }
 606             pts2[j].x += pts2[j].d / 2;
 607             pts2[j].y += pts2[j].d / 2;
 608             auxlen += sprintf(buf, ";P%d:%ld,%ld/%ld", i,
 609                               pts2[j].x, pts2[j].y, pts2[j].d);
 610         }
 611         k = 0;
 612         auxstr = snewn(auxlen, char);
 613         auxstr[k++] = 'S';
 614         for (i = 0; i < n; i++)
 615             k += sprintf(auxstr+k, ";P%d:%ld,%ld/%ld", i,
 616                          pts2[i].x, pts2[i].y, pts2[i].d);
 617         assert(k < auxlen);
 618         *aux = auxstr;
 619     }
 620     sfree(pts2);
 621
 622     sfree(tmp);
 623     sfree(vlist);
 624     freetree234(vertices);
 625     sfree(vs);
 626     while ((e = delpos234(edges, 0)) != NULL)
 627         sfree(e);
 628     freetree234(edges);
 629     sfree(pts);
 630
 631     return ret;
 632 }
 633
 634 static char *validate_desc(game_params *params, char *desc)
 635 {
 636     int a, b;
 637
 638     while (*desc) {
 639         a = atoi(desc);
 640         if (a < 0 || a >= params->n)
 641             return "Number out of range in game description";
 642         while (*desc && isdigit((unsigned char)*desc)) desc++;
 643         if (*desc != '-')
 644             return "Expected '-' after number in game description";
 645         desc++;                        /* eat dash */
 646         b = atoi(desc);
 647         if (b < 0 || b >= params->n)
 648             return "Number out of range in game description";
 649         while (*desc && isdigit((unsigned char)*desc)) desc++;
 650         if (*desc) {
 651             if (*desc != ',')
 652                 return "Expected ',' after number in game description";
 653             desc++;                    /* eat comma */
 654         }
 655     }
 656
 657     return NULL;
 658 }
 659
 660 static game_state *new_game(midend_data *me, game_params *params, char *desc)
 661 {
 662     int n = params->n;
 663     game_state *state = snew(game_state);
 664     int a, b;
 665
 666     state->params = *params;
 667     state->w = state->h = COORDLIMIT(n);
 668     state->pts = snewn(n, point);
 669     make_circle(state->pts, n, state->w);
 670     state->graph = snew(struct graph);
 671     state->graph->refcount = 1;
 672     state->graph->edges = newtree234(edgecmp);
 673     state->completed = state->cheated = state->just_solved = FALSE;
 674
 675     while (*desc) {
 676         a = atoi(desc);
 677         assert(a >= 0 && a < params->n);
 678         while (*desc && isdigit((unsigned char)*desc)) desc++;
 679         assert(*desc == '-');
 680         desc++;                        /* eat dash */
 681         b = atoi(desc);
 682         assert(b >= 0 && b < params->n);
 683         while (*desc && isdigit((unsigned char)*desc)) desc++;
 684         if (*desc) {
 685             assert(*desc == ',');
 686             desc++;                    /* eat comma */
 687         }
 688         addedge(state->graph->edges, a, b);
 689     }
 690
 691     return state;
 692 }
 693
 694 static game_state *dup_game(game_state *state)
 695 {
 696     int n = state->params.n;
 697     game_state *ret = snew(game_state);
 698
 699     ret->params = state->params;
 700     ret->w = state->w;
 701     ret->h = state->h;
 702     ret->pts = snewn(n, point);
 703     memcpy(ret->pts, state->pts, n * sizeof(point));
 704     ret->graph = state->graph;
 705     ret->graph->refcount++;
 706     ret->completed = state->completed;
 707     ret->cheated = state->cheated;
 708     ret->just_solved = state->just_solved;
 709
 710     return ret;
 711 }
 712
 713 static void free_game(game_state *state)
 714 {
 715     if (--state->graph->refcount <= 0) {
 716         edge *e;
 717         while ((e = delpos234(state->graph->edges, 0)) != NULL)
 718             sfree(e);
 719         freetree234(state->graph->edges);
 720         sfree(state->graph);
 721     }
 722     sfree(state->pts);
 723     sfree(state);
 724 }
 725
 726 static char *solve_game(game_state *state, game_state *currstate,
 727                         char *aux, char **error)
 728 {
 729     int n = state->params.n;
 730     int matrix[4];
 731     point *pts;
 732     int i, j, besti;
 733     float bestd;
 734     char buf[80], *ret;
 735     int retlen, retsize;
 736
 737     if (!aux) {
 738         *error = "Solution not known for this puzzle";
 739         return NULL;
 740     }
 741
 742     /*
 743      * Decode the aux_info to get the original point positions.
 744      */
 745     pts = snewn(n, point);
 746     aux++;                             /* eat 'S' */
 747     for (i = 0; i < n; i++) {
 748         int p, k;
 749         long x, y, d;
 750         int ret = sscanf(aux, ";P%d:%ld,%ld/%ld%n", &p, &x, &y, &d, &k);
 751         if (ret != 4 || p != i) {
 752             *error = "Internal error: aux_info badly formatted";
 753             sfree(pts);
 754             return NULL;
 755         }
 756         pts[i].x = x;
 757         pts[i].y = y;
 758         pts[i].d = d;
 759         aux += k;
 760     }
 761
 762     /*
 763      * Now go through eight possible symmetries of the point set.
 764      * For each one, work out the sum of the Euclidean distances
 765      * between the points' current positions and their new ones.
 766      *
 767      * We're squaring distances here, which means we're at risk of
 768      * integer overflow. Fortunately, there's no real need to be
 769      * massively careful about rounding errors, since this is a
 770      * non-essential bit of the code; so I'll just work in floats
 771      * internally.
 772      */
 773     besti = -1;
 774     bestd = 0.0F;
 775
 776     for (i = 0; i < 8; i++) {
 777         float d;
 778
 779         matrix[0] = matrix[1] = matrix[2] = matrix[3] = 0;
 780         matrix[i & 1] = (i & 2) ? +1 : -1;
 781         matrix[3-(i&1)] = (i & 4) ? +1 : -1;
 782
 783         d = 0.0F;
 784         for (j = 0; j < n; j++) {
 785             float px = (float)pts[j].x / pts[j].d;
 786             float py = (float)pts[j].y / pts[j].d;
 787             float sx = (float)currstate->pts[j].x / currstate->pts[j].d;
 788             float sy = (float)currstate->pts[j].y / currstate->pts[j].d;
 789             float cx = (float)currstate->w / 2;
 790             float cy = (float)currstate->h / 2;
 791             float ox, oy, dx, dy;
 792
 793             px -= cx;
 794             py -= cy;
 795
 796             ox = matrix[0] * px + matrix[1] * py;
 797             oy = matrix[2] * px + matrix[3] * py;
 798
 799             ox += cx;
 800             oy += cy;
 801
 802             dx = ox - sx;
 803             dy = oy - sy;
 804
 805             d += dx*dx + dy*dy;
 806         }
 807
 808         if (besti < 0 || bestd > d) {
 809             besti = i;
 810             bestd = d;
 811         }
 812     }
 813
 814     assert(besti >= 0);
 815
 816     /*
 817      * Now we know which symmetry is closest to the points' current
 818      * positions. Use it.
 819      */
 820     matrix[0] = matrix[1] = matrix[2] = matrix[3] = 0;
 821     matrix[besti & 1] = (besti & 2) ? +1 : -1;
 822     matrix[3-(besti&1)] = (besti & 4) ? +1 : -1;
 823
 824     retsize = 256;
 825     ret = snewn(retsize, char);
 826     retlen = 0;
 827     ret[retlen++] = 'S';
 828     ret[retlen] = '\0';
 829
 830     for (i = 0; i < n; i++) {
 831         float px = (float)pts[i].x / pts[i].d;
 832         float py = (float)pts[i].y / pts[i].d;
 833         float cx = (float)currstate->w / 2;
 834         float cy = (float)currstate->h / 2;
 835         float ox, oy;
 836         int extra;
 837
 838         px -= cx;
 839         py -= cy;
 840
 841         ox = matrix[0] * px + matrix[1] * py;
 842         oy = matrix[2] * px + matrix[3] * py;
 843
 844         ox += cx;
 845         oy += cy;
 846
 847         /*
 848          * Use a fixed denominator of 2, because we know the
 849          * original points were on an integer grid offset by 1/2.
 850          */
 851         pts[i].d = 2;
 852         ox *= pts[i].d;
 853         oy *= pts[i].d;
 854         pts[i].x = ox + 0.5;
 855         pts[i].y = oy + 0.5;
 856
 857         extra = sprintf(buf, ";P%d:%ld,%ld/%ld", i,
 858                         pts[i].x, pts[i].y, pts[i].d);
 859         if (retlen + extra >= retsize) {
 860             retsize = retlen + extra + 256;
 861             ret = sresize(ret, retsize, char);
 862         }
 863         strcpy(ret + retlen, buf);
 864         retlen += extra;
 865     }
 866
 867     sfree(pts);
 868
 869     return ret;
 870 }
 871
 872 static char *game_text_format(game_state *state)
 873 {
 874     return NULL;
 875 }
 876
 877 struct game_ui {
 878     int dragpoint;                     /* point being dragged; -1 if none */
 879     point newpoint;                    /* where it's been dragged to so far */
 880     int just_dragged;                  /* reset in game_changed_state */
 881     int just_moved;                    /* _set_ in game_changed_state */
 882     float anim_length;
 883 };
 884
 885 static game_ui *new_ui(game_state *state)
 886 {
 887     game_ui *ui = snew(game_ui);
 888     ui->dragpoint = -1;
 889     ui->just_moved = ui->just_dragged = FALSE;
 890     return ui;
 891 }
 892
 893 static void free_ui(game_ui *ui)
 894 {
 895     sfree(ui);
 896 }
 897
 898 static char *encode_ui(game_ui *ui)
 899 {
 900     return NULL;
 901 }
 902
 903 static void decode_ui(game_ui *ui, char *encoding)
 904 {
 905 }
 906
 907 static void game_changed_state(game_ui *ui, game_state *oldstate,
 908                                game_state *newstate)
 909 {
 910     ui->dragpoint = -1;
 911     ui->just_moved = ui->just_dragged;
 912     ui->just_dragged = FALSE;
 913 }
 914
 915 struct game_drawstate {
 916     long tilesize;
 917 };
 918
 919 static char *interpret_move(game_state *state, game_ui *ui, game_drawstate *ds,
 920                             int x, int y, int button)
 921 {
 922     int n = state->params.n;
 923
 924     if (button == LEFT_BUTTON) {
 925         int i, best;
 926         long bestd;
 927
 928         /*
 929          * Begin drag. We drag the vertex _nearest_ to the pointer,
 930          * just in case one is nearly on top of another and we want
 931          * to drag the latter. However, we drag nothing at all if
 932          * the nearest vertex is outside DRAG_THRESHOLD.
 933          */
 934         best = -1;
 935         bestd = 0;
 936
 937         for (i = 0; i < n; i++) {
 938             long px = state->pts[i].x * ds->tilesize / state->pts[i].d;
 939             long py = state->pts[i].y * ds->tilesize / state->pts[i].d;
 940             long dx = px - x;
 941             long dy = py - y;
 942             long d = dx*dx + dy*dy;
 943
 944             if (best == -1 || bestd > d) {
 945                 best = i;
 946                 bestd = d;
 947             }
 948         }
 949
 950         if (bestd <= DRAG_THRESHOLD * DRAG_THRESHOLD) {
 951             ui->dragpoint = best;
 952             ui->newpoint.x = x;
 953             ui->newpoint.y = y;
 954             ui->newpoint.d = ds->tilesize;
 955             return "";
 956         }
 957
 958     } else if (button == LEFT_DRAG && ui->dragpoint >= 0) {
 959         ui->newpoint.x = x;
 960         ui->newpoint.y = y;
 961         ui->newpoint.d = ds->tilesize;
 962         return "";
 963     } else if (button == LEFT_RELEASE && ui->dragpoint >= 0) {
 964         int p = ui->dragpoint;
 965         char buf[80];
 966
 967         ui->dragpoint = -1;            /* terminate drag, no matter what */
 968
 969         /*
 970          * First, see if we're within range. The user can cancel a
 971          * drag by dragging the point right off the window.
 972          */
 973         if (ui->newpoint.x < 0 ||
 974             ui->newpoint.x >= (long)state->w*ui->newpoint.d ||
 975             ui->newpoint.y < 0 ||
 976             ui->newpoint.y >= (long)state->h*ui->newpoint.d)
 977             return "";
 978
 979         /*
 980          * We aren't cancelling the drag. Construct a move string
 981          * indicating where this point is going to.
 982          */
 983         sprintf(buf, "P%d:%ld,%ld/%ld", p,
 984                 ui->newpoint.x, ui->newpoint.y, ui->newpoint.d);
 985         ui->just_dragged = TRUE;
 986         return dupstr(buf);
 987     }
 988
 989     return NULL;
 990 }
 991
 992 static game_state *execute_move(game_state *state, char *move)
 993 {
 994     int n = state->params.n;
 995     int p, k;
 996     long x, y, d;
 997     game_state *ret = dup_game(state);
 998
 999     ret->just_solved = FALSE;
1000
1001     while (*move) {
1002         if (*move == 'S') {
1003             move++;
1004             if (*move == ';') move++;
1005             ret->cheated = ret->just_solved = TRUE;
1006         }
1007         if (*move == 'P' &&
1008             sscanf(move+1, "%d:%ld,%ld/%ld%n", &p, &x, &y, &d, &k) == 4 &&
1009             p >= 0 && p < n && d > 0) {
1010             ret->pts[p].x = x;
1011             ret->pts[p].y = y;
1012             ret->pts[p].d = d;
1013
1014             move += k+1;
1015             if (*move == ';') move++;
1016         } else {
1017             free_game(ret);
1018             return NULL;
1019         }
1020     }
1021
1022     /*
1023      * Check correctness: for every pair of edges, see whether they
1024      * cross.
1025      */
1026     if (!ret->completed) {
1027         int i, j;
1028         edge *e, *e2;
1029
1030         for (i = 0; (e = index234(ret->graph->edges, i)) != NULL; i++) {
1031             for (j = i+1; (e2 = index234(ret->graph->edges, j)) != NULL; j++) {
1032                 if (e2->a == e->a || e2->a == e->b ||
1033                     e2->b == e->a || e2->b == e->b)
1034                     continue;
1035                 if (cross(ret->pts[e2->a], ret->pts[e2->b],
1036                           ret->pts[e->a], ret->pts[e->b]))
1037                     break;
1038             }
1039             if (e2)
1040                 break;
1041         }
1042
1043         /*
1044          * e == NULL if we've gone through all the edge pairs
1045          * without finding a crossing.
1046          */
1047         ret->completed = (e == NULL);
1048     }
1049
1050     return ret;
1051 }
1052
1053 /* ----------------------------------------------------------------------
1054  * Drawing routines.
1055  */
1056
1057 static void game_compute_size(game_params *params, int tilesize,
1058                               int *x, int *y)
1059 {
1060     *x = *y = COORDLIMIT(params->n) * tilesize;
1061 }
1062
1063 static void game_set_size(game_drawstate *ds, game_params *params,
1064                           int tilesize)
1065 {
1066     ds->tilesize = tilesize;
1067 }
1068
1069 static float *game_colours(frontend *fe, game_state *state, int *ncolours)
1070 {
1071     float *ret = snewn(3 * NCOLOURS, float);
1072
1073     frontend_default_colour(fe, &ret[COL_BACKGROUND * 3]);
1074
1075     ret[COL_LINE * 3 + 0] = 0.0F;
1076     ret[COL_LINE * 3 + 1] = 0.0F;
1077     ret[COL_LINE * 3 + 2] = 0.0F;
1078
1079     ret[COL_OUTLINE * 3 + 0] = 0.0F;
1080     ret[COL_OUTLINE * 3 + 1] = 0.0F;
1081     ret[COL_OUTLINE * 3 + 2] = 0.0F;
1082
1083     ret[COL_POINT * 3 + 0] = 0.0F;
1084     ret[COL_POINT * 3 + 1] = 0.0F;
1085     ret[COL_POINT * 3 + 2] = 1.0F;
1086
1087     ret[COL_DRAGPOINT * 3 + 0] = 1.0F;
1088     ret[COL_DRAGPOINT * 3 + 1] = 1.0F;
1089     ret[COL_DRAGPOINT * 3 + 2] = 1.0F;
1090
1091     ret[COL_NEIGHBOUR * 3 + 0] = 1.0F;
1092     ret[COL_NEIGHBOUR * 3 + 1] = 0.0F;
1093     ret[COL_NEIGHBOUR * 3 + 2] = 0.0F;
1094
1095     ret[COL_FLASH1 * 3 + 0] = 0.5F;
1096     ret[COL_FLASH1 * 3 + 1] = 0.5F;
1097     ret[COL_FLASH1 * 3 + 2] = 0.5F;
1098
1099     ret[COL_FLASH2 * 3 + 0] = 1.0F;
1100     ret[COL_FLASH2 * 3 + 1] = 1.0F;
1101     ret[COL_FLASH2 * 3 + 2] = 1.0F;
1102
1103     *ncolours = NCOLOURS;
1104     return ret;
1105 }
1106
1107 static game_drawstate *game_new_drawstate(game_state *state)
1108 {
1109     struct game_drawstate *ds = snew(struct game_drawstate);
1110
1111     ds->tilesize = 0;
1112
1113     return ds;
1114 }
1115
1116 static void game_free_drawstate(game_drawstate *ds)
1117 {
1118     sfree(ds);
1119 }
1120
1121 static point mix(point a, point b, float distance)
1122 {
1123     point ret;
1124
1125     ret.d = a.d * b.d;
1126     ret.x = a.x * b.d + distance * (b.x * a.d - a.x * b.d);
1127     ret.y = a.y * b.d + distance * (b.y * a.d - a.y * b.d);
1128
1129     return ret;
1130 }
1131
1132 static void game_redraw(frontend *fe, game_drawstate *ds, game_state *oldstate,
1133                         game_state *state, int dir, game_ui *ui,
1134                         float animtime, float flashtime)
1135 {
1136     int w, h;
1137     edge *e;
1138     int i, j;
1139     int bg;
1140
1141     /*
1142      * There's no terribly sensible way to do partial redraws of
1143      * this game, so I'm going to have to resort to redrawing the
1144      * whole thing every time.
1145      */
1146
1147     if (flashtime == 0)
1148         bg = COL_BACKGROUND;
1149     else if ((int)(flashtime * 4 / FLASH_TIME) % 2 == 0)
1150         bg = COL_FLASH1;
1151     else
1152         bg = COL_FLASH2;
1153
1154     game_compute_size(&state->params, ds->tilesize, &w, &h);
1155     draw_rect(fe, 0, 0, w, h, bg);
1156
1157     /*
1158      * Draw the edges.
1159      */
1160
1161     for (i = 0; (e = index234(state->graph->edges, i)) != NULL; i++) {
1162         point p1, p2;
1163         long x1, y1, x2, y2;
1164
1165         p1 = state->pts[e->a];
1166         p2 = state->pts[e->b];
1167         if (ui->dragpoint == e->a)
1168             p1 = ui->newpoint;
1169         else if (ui->dragpoint == e->b)
1170             p2 = ui->newpoint;
1171
1172         if (oldstate) {
1173             p1 = mix(oldstate->pts[e->a], p1, animtime / ui->anim_length);
1174             p2 = mix(oldstate->pts[e->b], p2, animtime / ui->anim_length);
1175         }
1176
1177         x1 = p1.x * ds->tilesize / p1.d;
1178         y1 = p1.y * ds->tilesize / p1.d;
1179         x2 = p2.x * ds->tilesize / p2.d;
1180         y2 = p2.y * ds->tilesize / p2.d;
1181
1182         draw_line(fe, x1, y1, x2, y2, COL_LINE);
1183     }
1184
1185     /*
1186      * Draw the points.
1187      *
1188      * When dragging, we should not only vary the colours, but
1189      * leave the point being dragged until last.
1190      */
1191     for (j = 0; j < 3; j++) {
1192         int thisc = (j == 0 ? COL_POINT :
1193                      j == 1 ? COL_NEIGHBOUR : COL_DRAGPOINT);
1194         for (i = 0; i < state->params.n; i++) {
1195             long x, y;
1196             int c;
1197             point p = state->pts[i];
1198
1199             if (ui->dragpoint == i) {
1200                 p = ui->newpoint;
1201                 c = COL_DRAGPOINT;
1202             } else if (ui->dragpoint >= 0 &&
1203                        isedge(state->graph->edges, ui->dragpoint, i)) {
1204                 c = COL_NEIGHBOUR;
1205             } else {
1206                 c = COL_POINT;
1207             }
1208
1209             if (oldstate)
1210                 p = mix(oldstate->pts[i], p, animtime / ui->anim_length);
1211
1212             if (c == thisc) {
1213                 x = p.x * ds->tilesize / p.d;
1214                 y = p.y * ds->tilesize / p.d;
1215
1216 #ifdef VERTEX_NUMBERS
1217                 draw_circle(fe, x, y, DRAG_THRESHOLD, bg, bg);
1218                 {
1219                     char buf[80];
1220                     sprintf(buf, "%d", i);
1221                     draw_text(fe, x, y, FONT_VARIABLE, DRAG_THRESHOLD*3/2,
1222                               ALIGN_VCENTRE|ALIGN_HCENTRE, c, buf);
1223                 }
1224 #else
1225                 draw_circle(fe, x, y, CIRCLE_RADIUS, c, COL_OUTLINE);
1226 #endif
1227             }
1228         }
1229     }
1230
1231     draw_update(fe, 0, 0, w, h);
1232 }
1233
1234 static float game_anim_length(game_state *oldstate, game_state *newstate,
1235                               int dir, game_ui *ui)
1236 {
1237     if (ui->just_moved)
1238         return 0.0F;
1239     if ((dir < 0 ? oldstate : newstate)->just_solved)
1240         ui->anim_length = SOLVEANIM_TIME;
1241     else
1242         ui->anim_length = ANIM_TIME;
1243     return ui->anim_length;
1244 }
1245
1246 static float game_flash_length(game_state *oldstate, game_state *newstate,
1247                                int dir, game_ui *ui)
1248 {
1249     if (!oldstate->completed && newstate->completed &&
1250         !oldstate->cheated && !newstate->cheated)
1251         return FLASH_TIME;
1252     return 0.0F;
1253 }
1254
1255 static int game_wants_statusbar(void)
1256 {
1257     return FALSE;
1258 }
1259
1260 static int game_timing_state(game_state *state, game_ui *ui)
1261 {
1262     return TRUE;
1263 }
1264
1265 #ifdef COMBINED
1266 #define thegame untangle
1267 #endif
1268
1269 const struct game thegame = {
1270     "Untangle", "games.untangle",
1271     default_params,
1272     game_fetch_preset,
1273     decode_params,
1274     encode_params,
1275     free_params,
1276     dup_params,
1277     TRUE, game_configure, custom_params,
1278     validate_params,
1279     new_game_desc,
1280     validate_desc,
1281     new_game,
1282     dup_game,
1283     free_game,
1284     TRUE, solve_game,
1285     FALSE, game_text_format,
1286     new_ui,
1287     free_ui,
1288     encode_ui,
1289     decode_ui,
1290     game_changed_state,
1291     interpret_move,
1292     execute_move,
1293     PREFERRED_TILESIZE, game_compute_size, game_set_size,
1294     game_colours,
1295     game_new_drawstate,
1296     game_free_drawstate,
1297     game_redraw,
1298     game_anim_length,
1299     game_flash_length,
1300     game_wants_statusbar,
1301     FALSE, game_timing_state,
1302     SOLVE_ANIMATES,                    /* mouse_priorities */
1303 };