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