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