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