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