net.c

   1 /*
   2  * net.c: Net game.
   3  */
   4
   5 #include <stdio.h>
   6 #include <stdlib.h>
   7 #include <string.h>
   8 #include <assert.h>
   9 #include <ctype.h>
  10 #include <math.h>
  11
  12 #include "puzzles.h"
  13 #include "tree234.h"
  14
  15 #define PI 3.141592653589793238462643383279502884197169399
  16
  17 #define MATMUL(xr,yr,m,x,y) do { \
  18     float rx, ry, xx = (x), yy = (y), *mat = (m); \
  19     rx = mat[0] * xx + mat[2] * yy; \
  20     ry = mat[1] * xx + mat[3] * yy; \
  21     (xr) = rx; (yr) = ry; \
  22 } while (0)
  23
  24 /* Direction and other bitfields */
  25 #define R 0x01
  26 #define U 0x02
  27 #define L 0x04
  28 #define D 0x08
  29 #define LOCKED 0x10
  30 #define ACTIVE 0x20
  31 /* Corner flags go in the barriers array */
  32 #define RU 0x10
  33 #define UL 0x20
  34 #define LD 0x40
  35 #define DR 0x80
  36
  37 /* Rotations: Anticlockwise, Clockwise, Flip, general rotate */
  38 #define A(x) ( (((x) & 0x07) << 1) | (((x) & 0x08) >> 3) )
  39 #define C(x) ( (((x) & 0x0E) >> 1) | (((x) & 0x01) << 3) )
  40 #define F(x) ( (((x) & 0x0C) >> 2) | (((x) & 0x03) << 2) )
  41 #define ROT(x, n) ( ((n)&3) == 0 ? (x) : \
  42                     ((n)&3) == 1 ? A(x) : \
  43                     ((n)&3) == 2 ? F(x) : C(x) )
  44
  45 /* X and Y displacements */
  46 #define X(x) ( (x) == R ? +1 : (x) == L ? -1 : 0 )
  47 #define Y(x) ( (x) == D ? +1 : (x) == U ? -1 : 0 )
  48
  49 /* Bit count */
  50 #define COUNT(x) ( (((x) & 0x08) >> 3) + (((x) & 0x04) >> 2) + \
  51                    (((x) & 0x02) >> 1) + ((x) & 0x01) )
  52
  53 #define TILE_SIZE 32
  54 #define TILE_BORDER 1
  55 #define WINDOW_OFFSET 16
  56
  57 #define ROTATE_TIME 0.13F
  58 #define FLASH_FRAME 0.07F
  59
  60 enum {
  61     COL_BACKGROUND,
  62     COL_LOCKED,
  63     COL_BORDER,
  64     COL_WIRE,
  65     COL_ENDPOINT,
  66     COL_POWERED,
  67     COL_BARRIER,
  68     NCOLOURS
  69 };
  70
  71 struct game_params {
  72     int width;
  73     int height;
  74     int wrapping;
  75     int unique;
  76     float barrier_probability;
  77 };
  78
  79 struct game_aux_info {
  80     int width, height;
  81     unsigned char *tiles;
  82 };
  83
  84 struct game_state {
  85     int width, height, cx, cy, wrapping, completed;
  86     int last_rotate_x, last_rotate_y, last_rotate_dir;
  87     int used_solve, just_used_solve;
  88     unsigned char *tiles;
  89     unsigned char *barriers;
  90 };
  91
  92 #define OFFSETWH(x2,y2,x1,y1,dir,width,height) \
  93     ( (x2) = ((x1) + width + X((dir))) % width, \
  94       (y2) = ((y1) + height + Y((dir))) % height)
  95
  96 #define OFFSET(x2,y2,x1,y1,dir,state) \
  97         OFFSETWH(x2,y2,x1,y1,dir,(state)->width,(state)->height)
  98
  99 #define index(state, a, x, y) ( a[(y) * (state)->width + (x)] )
 100 #define tile(state, x, y)     index(state, (state)->tiles, x, y)
 101 #define barrier(state, x, y)  index(state, (state)->barriers, x, y)
 102
 103 struct xyd {
 104     int x, y, direction;
 105 };
 106
 107 static int xyd_cmp(const void *av, const void *bv) {
 108     const struct xyd *a = (const struct xyd *)av;
 109     const struct xyd *b = (const struct xyd *)bv;
 110     if (a->x < b->x)
 111         return -1;
 112     if (a->x > b->x)
 113         return +1;
 114     if (a->y < b->y)
 115         return -1;
 116     if (a->y > b->y)
 117         return +1;
 118     if (a->direction < b->direction)
 119         return -1;
 120     if (a->direction > b->direction)
 121         return +1;
 122     return 0;
 123 };
 124
 125 static int xyd_cmp_nc(void *av, void *bv) { return xyd_cmp(av, bv); }
 126
 127 static struct xyd *new_xyd(int x, int y, int direction)
 128 {
 129     struct xyd *xyd = snew(struct xyd);
 130     xyd->x = x;
 131     xyd->y = y;
 132     xyd->direction = direction;
 133     return xyd;
 134 }
 135
 136 /* ----------------------------------------------------------------------
 137  * Manage game parameters.
 138  */
 139 static game_params *default_params(void)
 140 {
 141     game_params *ret = snew(game_params);
 142
 143     ret->width = 5;
 144     ret->height = 5;
 145     ret->wrapping = FALSE;
 146     ret->unique = TRUE;
 147     ret->barrier_probability = 0.0;
 148
 149     return ret;
 150 }
 151
 152 static int game_fetch_preset(int i, char **name, game_params **params)
 153 {
 154     game_params *ret;
 155     char str[80];
 156     static const struct { int x, y, wrap; } values[] = {
 157         {5, 5, FALSE},
 158         {7, 7, FALSE},
 159         {9, 9, FALSE},
 160         {11, 11, FALSE},
 161         {13, 11, FALSE},
 162         {5, 5, TRUE},
 163         {7, 7, TRUE},
 164         {9, 9, TRUE},
 165         {11, 11, TRUE},
 166         {13, 11, TRUE},
 167     };
 168
 169     if (i < 0 || i >= lenof(values))
 170         return FALSE;
 171
 172     ret = snew(game_params);
 173     ret->width = values[i].x;
 174     ret->height = values[i].y;
 175     ret->wrapping = values[i].wrap;
 176     ret->unique = TRUE;
 177     ret->barrier_probability = 0.0;
 178
 179     sprintf(str, "%dx%d%s", ret->width, ret->height,
 180             ret->wrapping ? " wrapping" : "");
 181
 182     *name = dupstr(str);
 183     *params = ret;
 184     return TRUE;
 185 }
 186
 187 static void free_params(game_params *params)
 188 {
 189     sfree(params);
 190 }
 191
 192 static game_params *dup_params(game_params *params)
 193 {
 194     game_params *ret = snew(game_params);
 195     *ret = *params;                    /* structure copy */
 196     return ret;
 197 }
 198
 199 static void decode_params(game_params *ret, char const *string)
 200 {
 201     char const *p = string;
 202
 203     ret->width = atoi(p);
 204     while (*p && isdigit(*p)) p++;
 205     if (*p == 'x') {
 206         p++;
 207         ret->height = atoi(p);
 208         while (*p && isdigit(*p)) p++;
 209     } else {
 210         ret->height = ret->width;
 211     }
 212
 213     while (*p) {
 214         if (*p == 'w') {
 215             p++;
 216             ret->wrapping = TRUE;
 217         } else if (*p == 'b') {
 218             p++;
 219             ret->barrier_probability = atof(p);
 220             while (*p && isdigit(*p)) p++;
 221         } else if (*p == 'a') {
 222             p++;
 223             ret->unique = FALSE;
 224         }
 225     }
 226 }
 227
 228 static char *encode_params(game_params *params, int full)
 229 {
 230     char ret[400];
 231     int len;
 232
 233     len = sprintf(ret, "%dx%d", params->width, params->height);
 234     if (params->wrapping)
 235         ret[len++] = 'w';
 236     if (full && params->barrier_probability)
 237         len += sprintf(ret+len, "b%g", params->barrier_probability);
 238     if (!params->unique)
 239         ret[len++] = 'a';
 240     assert(len < lenof(ret));
 241     ret[len] = '\0';
 242
 243     return dupstr(ret);
 244 }
 245
 246 static config_item *game_configure(game_params *params)
 247 {
 248     config_item *ret;
 249     char buf[80];
 250
 251     ret = snewn(6, config_item);
 252
 253     ret[0].name = "Width";
 254     ret[0].type = C_STRING;
 255     sprintf(buf, "%d", params->width);
 256     ret[0].sval = dupstr(buf);
 257     ret[0].ival = 0;
 258
 259     ret[1].name = "Height";
 260     ret[1].type = C_STRING;
 261     sprintf(buf, "%d", params->height);
 262     ret[1].sval = dupstr(buf);
 263     ret[1].ival = 0;
 264
 265     ret[2].name = "Walls wrap around";
 266     ret[2].type = C_BOOLEAN;
 267     ret[2].sval = NULL;
 268     ret[2].ival = params->wrapping;
 269
 270     ret[3].name = "Barrier probability";
 271     ret[3].type = C_STRING;
 272     sprintf(buf, "%g", params->barrier_probability);
 273     ret[3].sval = dupstr(buf);
 274     ret[3].ival = 0;
 275
 276     ret[4].name = "Ensure unique solution";
 277     ret[4].type = C_BOOLEAN;
 278     ret[4].sval = NULL;
 279     ret[4].ival = params->unique;
 280
 281     ret[5].name = NULL;
 282     ret[5].type = C_END;
 283     ret[5].sval = NULL;
 284     ret[5].ival = 0;
 285
 286     return ret;
 287 }
 288
 289 static game_params *custom_params(config_item *cfg)
 290 {
 291     game_params *ret = snew(game_params);
 292
 293     ret->width = atoi(cfg[0].sval);
 294     ret->height = atoi(cfg[1].sval);
 295     ret->wrapping = cfg[2].ival;
 296     ret->barrier_probability = (float)atof(cfg[3].sval);
 297     ret->unique = cfg[4].ival;
 298
 299     return ret;
 300 }
 301
 302 static char *validate_params(game_params *params)
 303 {
 304     if (params->width <= 0 && params->height <= 0)
 305         return "Width and height must both be greater than zero";
 306     if (params->width <= 0)
 307         return "Width must be greater than zero";
 308     if (params->height <= 0)
 309         return "Height must be greater than zero";
 310     if (params->width <= 1 && params->height <= 1)
 311         return "At least one of width and height must be greater than one";
 312     if (params->barrier_probability < 0)
 313         return "Barrier probability may not be negative";
 314     if (params->barrier_probability > 1)
 315         return "Barrier probability may not be greater than 1";
 316     return NULL;
 317 }
 318
 319 /* ----------------------------------------------------------------------
 320  * Solver used to assure solution uniqueness during generation.
 321  */
 322
 323 /*
 324  * Test cases I used while debugging all this were
 325  *
 326  *   ./net --generate 1 13x11w#12300
 327  * which expands under the non-unique grid generation rules to
 328  *   13x11w:5eaade1bd222664436d5e2965c12656b1129dd825219e3274d558d5eb2dab5da18898e571d5a2987be79746bd95726c597447d6da96188c513add829da7681da954db113d3cd244
 329  * and has two ambiguous areas.
 330  *
 331  * An even better one is
 332  *   13x11w#507896411361192
 333  * which expands to
 334  *   13x11w:b7125b1aec598eb31bd58d82572bc11494e5dee4e8db2bdd29b88d41a16bdd996d2996ddec8c83741a1e8674e78328ba71737b8894a9271b1cd1399453d1952e43951d9b712822e
 335  * and has an ambiguous area _and_ a situation where loop avoidance
 336  * is a necessary deductive technique.
 337  *
 338  * Then there's
 339  *   48x25w#820543338195187
 340  * becoming
 341  *   48x25w:255989d14cdd185deaa753a93821a12edc1ab97943ac127e2685d7b8b3c48861b2192416139212b316eddd35de43714ebc7628d753db32e596284d9ec52c5a7dc1b4c811a655117d16dc28921b2b4161352cab1d89d18bc836b8b891d55ea4622a1251861b5bc9a8aa3e5bcd745c95229ca6c3b5e21d5832d397e917325793d7eb442dc351b2db2a52ba8e1651642275842d8871d5534aabc6d5b741aaa2d48ed2a7dbbb3151ddb49d5b9a7ed1ab98ee75d613d656dbba347bc514c84556b43a9bc65a3256ead792488b862a9d2a8a39b4255a4949ed7dbd79443292521265896b4399c95ede89d7c8c797a6a57791a849adea489359a158aa12e5dacce862b8333b7ebea7d344d1a3c53198864b73a9dedde7b663abb1b539e1e8853b1b7edb14a2a17ebaae4dbe63598a2e7e9a2dbdad415bc1d8cb88cbab5a8c82925732cd282e641ea3bd7d2c6e776de9117a26be86deb7c82c89524b122cb9397cd1acd2284e744ea62b9279bae85479ababe315c3ac29c431333395b24e6a1e3c43a2da42d4dce84aadd5b154aea555eaddcbd6e527d228c19388d9b424d94214555a7edbdeebe569d4a56dc51a86bd9963e377bb74752bd5eaa5761ba545e297b62a1bda46ab4aee423ad6c661311783cc18786d4289236563cb4a75ec67d481c14814994464cd1b87396dee63e5ab6e952cc584baa1d4c47cb557ec84dbb63d487c8728118673a166846dd3a4ebc23d6cb9c5827d96b4556e91899db32b517eda815ae271a8911bd745447121dc8d321557bc2a435ebec1bbac35b1a291669451174e6aa2218a4a9c5a6ca31ebc45d84e3a82c121e9ced7d55e9a
 342  * which has a spot (far right) where slightly more complex loop
 343  * avoidance is required.
 344  */
 345
 346 static int dsf_canonify(int *dsf, int val)
 347 {
 348     int v2 = val;
 349
 350     while (dsf[val] != val)
 351         val = dsf[val];
 352
 353     while (v2 != val) {
 354         int tmp = dsf[v2];
 355         dsf[v2] = val;
 356         v2 = tmp;
 357     }
 358
 359     return val;
 360 }
 361
 362 static void dsf_merge(int *dsf, int v1, int v2)
 363 {
 364     v1 = dsf_canonify(dsf, v1);
 365     v2 = dsf_canonify(dsf, v2);
 366     dsf[v2] = v1;
 367 }
 368
 369 struct todo {
 370     unsigned char *marked;
 371     int *buffer;
 372     int buflen;
 373     int head, tail;
 374 };
 375
 376 static struct todo *todo_new(int maxsize)
 377 {
 378     struct todo *todo = snew(struct todo);
 379     todo->marked = snewn(maxsize, unsigned char);
 380     memset(todo->marked, 0, maxsize);
 381     todo->buflen = maxsize + 1;
 382     todo->buffer = snewn(todo->buflen, int);
 383     todo->head = todo->tail = 0;
 384     return todo;
 385 }
 386
 387 static void todo_free(struct todo *todo)
 388 {
 389     sfree(todo->marked);
 390     sfree(todo->buffer);
 391     sfree(todo);
 392 }
 393
 394 static void todo_add(struct todo *todo, int index)
 395 {
 396     if (todo->marked[index])
 397         return;                        /* already on the list */
 398     todo->marked[index] = TRUE;
 399     todo->buffer[todo->tail++] = index;
 400     if (todo->tail == todo->buflen)
 401         todo->tail = 0;
 402 }
 403
 404 static int todo_get(struct todo *todo) {
 405     int ret;
 406
 407     if (todo->head == todo->tail)
 408         return -1;                     /* list is empty */
 409     ret = todo->buffer[todo->head++];
 410     if (todo->head == todo->buflen)
 411         todo->head = 0;
 412     todo->marked[ret] = FALSE;
 413
 414     return ret;
 415 }
 416
 417 static int net_solver(int w, int h, unsigned char *tiles, int wrapping)
 418 {
 419     unsigned char *tilestate;
 420     unsigned char *edgestate;
 421     int *deadends;
 422     int *equivalence;
 423     struct todo *todo;
 424     int i, j, x, y;
 425     int area;
 426     int done_something;
 427
 428     /*
 429      * Set up the solver's data structures.
 430      */
 431
 432     /*
 433      * tilestate stores the possible orientations of each tile.
 434      * There are up to four of these, so we'll index the array in
 435      * fours. tilestate[(y * w + x) * 4] and its three successive
 436      * members give the possible orientations, clearing to 255 from
 437      * the end as things are ruled out.
 438      *
 439      * In this loop we also count up the area of the grid (which is
 440      * not _necessarily_ equal to w*h, because there might be one
 441      * or more blank squares present. This will never happen in a
 442      * grid generated _by_ this program, but it's worth keeping the
 443      * solver as general as possible.)
 444      */
 445     tilestate = snewn(w * h * 4, unsigned char);
 446     area = 0;
 447     for (i = 0; i < w*h; i++) {
 448         tilestate[i * 4] = tiles[i] & 0xF;
 449         for (j = 1; j < 4; j++) {
 450             if (tilestate[i * 4 + j - 1] == 255 ||
 451                 A(tilestate[i * 4 + j - 1]) == tilestate[i * 4])
 452                 tilestate[i * 4 + j] = 255;
 453             else
 454                 tilestate[i * 4 + j] = A(tilestate[i * 4 + j - 1]);
 455         }
 456         if (tiles[i] != 0)
 457             area++;
 458     }
 459
 460     /*
 461      * edgestate stores the known state of each edge. It is 0 for
 462      * unknown, 1 for open (connected) and 2 for closed (not
 463      * connected).
 464      *
 465      * In principle we need only worry about each edge once each,
 466      * but in fact it's easier to track each edge twice so that we
 467      * can reference it from either side conveniently. Also I'm
 468      * going to allocate _five_ bytes per tile, rather than the
 469      * obvious four, so that I can index edgestate[(y*w+x) * 5 + d]
 470      * where d is 1,2,4,8 and they never overlap.
 471      */
 472     edgestate = snewn((w * h - 1) * 5 + 9, unsigned char);
 473     memset(edgestate, 0, (w * h - 1) * 5 + 9);
 474
 475     /*
 476      * deadends tracks which edges have dead ends on them. It is
 477      * indexed by tile and direction: deadends[(y*w+x) * 5 + d]
 478      * tells you whether heading out of tile (x,y) in direction d
 479      * can reach a limited amount of the grid. Values are area+1
 480      * (no dead end known) or less than that (can reach _at most_
 481      * this many other tiles by heading this way out of this tile).
 482      */
 483     deadends = snewn((w * h - 1) * 5 + 9, int);
 484     for (i = 0; i < (w * h - 1) * 5 + 9; i++)
 485         deadends[i] = area+1;
 486
 487     /*
 488      * equivalence tracks which sets of tiles are known to be
 489      * connected to one another, so we can avoid creating loops by
 490      * linking together tiles which are already linked through
 491      * another route.
 492      *
 493      * This is a disjoint set forest structure: equivalence[i]
 494      * contains the index of another member of the equivalence
 495      * class containing i, or contains i itself for precisely one
 496      * member in each such class. To find a representative member
 497      * of the equivalence class containing i, you keep replacing i
 498      * with equivalence[i] until it stops changing; then you go
 499      * _back_ along the same path and point everything on it
 500      * directly at the representative member so as to speed up
 501      * future searches. Then you test equivalence between tiles by
 502      * finding the representative of each tile and seeing if
 503      * they're the same; and you create new equivalence (merge
 504      * classes) by finding the representative of each tile and
 505      * setting equivalence[one]=the_other.
 506      */
 507     equivalence = snewn(w * h, int);
 508     for (i = 0; i < w*h; i++)
 509         equivalence[i] = i;            /* initially all distinct */
 510
 511     /*
 512      * On a non-wrapping grid, we instantly know that all the edges
 513      * round the edge are closed.
 514      */
 515     if (!wrapping) {
 516         for (i = 0; i < w; i++) {
 517             edgestate[i * 5 + 2] = edgestate[((h-1) * w + i) * 5 + 8] = 2;
 518         }
 519         for (i = 0; i < h; i++) {
 520             edgestate[(i * w + w-1) * 5 + 1] = edgestate[(i * w) * 5 + 4] = 2;
 521         }
 522     }
 523
 524     /*
 525      * Since most deductions made by this solver are local (the
 526      * exception is loop avoidance, where joining two tiles
 527      * together on one side of the grid can theoretically permit a
 528      * fresh deduction on the other), we can address the scaling
 529      * problem inherent in iterating repeatedly over the entire
 530      * grid by instead working with a to-do list.
 531      */
 532     todo = todo_new(w * h);
 533
 534     /*
 535      * Main deductive loop.
 536      */
 537     done_something = TRUE;             /* prevent instant termination! */
 538     while (1) {
 539         int index;
 540
 541         /*
 542          * Take a tile index off the todo list and process it.
 543          */
 544         index = todo_get(todo);
 545         if (index == -1) {
 546             /*
 547              * If we have run out of immediate things to do, we
 548              * have no choice but to scan the whole grid for
 549              * longer-range things we've missed. Hence, I now add
 550              * every square on the grid back on to the to-do list.
 551              * I also set `done_something' to FALSE at this point;
 552              * if we later come back here and find it still FALSE,
 553              * we will know we've scanned the entire grid without
 554              * finding anything new to do, and we can terminate.
 555              */
 556             if (!done_something)
 557                 break;
 558             for (i = 0; i < w*h; i++)
 559                 todo_add(todo, i);
 560             done_something = FALSE;
 561
 562             index = todo_get(todo);
 563         }
 564
 565         y = index / w;
 566         x = index % w;
 567         {
 568             int d, ourclass = dsf_canonify(equivalence, y*w+x);
 569             int deadendmax[9];
 570
 571             deadendmax[1] = deadendmax[2] = deadendmax[4] = deadendmax[8] = 0;
 572
 573             for (i = j = 0; i < 4 && tilestate[(y*w+x) * 4 + i] != 255; i++) {
 574                 int valid;
 575                 int nnondeadends, nondeadends[4], deadendtotal;
 576                 int nequiv, equiv[5];
 577                 int val = tilestate[(y*w+x) * 4 + i];
 578
 579                 valid = TRUE;
 580                 nnondeadends = deadendtotal = 0;
 581                 equiv[0] = ourclass;
 582                 nequiv = 1;
 583                 for (d = 1; d <= 8; d += d) {
 584                     /*
 585                      * Immediately rule out this orientation if it
 586                      * conflicts with any known edge.
 587                      */
 588                     if ((edgestate[(y*w+x) * 5 + d] == 1 && !(val & d)) ||
 589                         (edgestate[(y*w+x) * 5 + d] == 2 && (val & d)))
 590                         valid = FALSE;
 591
 592                     if (val & d) {
 593                         /*
 594                          * Count up the dead-end statistics.
 595                          */
 596                         if (deadends[(y*w+x) * 5 + d] <= area) {
 597                             deadendtotal += deadends[(y*w+x) * 5 + d];
 598                         } else {
 599                             nondeadends[nnondeadends++] = d;
 600                         }
 601
 602                         /*
 603                          * Ensure we aren't linking to any tiles,
 604                          * through edges not already known to be
 605                          * open, which create a loop.
 606                          */
 607                         if (edgestate[(y*w+x) * 5 + d] == 0) {
 608                             int c, k, x2, y2;
 609
 610                             OFFSETWH(x2, y2, x, y, d, w, h);
 611                             c = dsf_canonify(equivalence, y2*w+x2);
 612                             for (k = 0; k < nequiv; k++)
 613                                 if (c == equiv[k])
 614                                     break;
 615                             if (k == nequiv)
 616                                 equiv[nequiv++] = c;
 617                             else
 618                                 valid = FALSE;
 619                         }
 620                     }
 621                 }
 622
 623                 if (nnondeadends == 0) {
 624                     /*
 625                      * If this orientation links together dead-ends
 626                      * with a total area of less than the entire
 627                      * grid, it is invalid.
 628                      *
 629                      * (We add 1 to deadendtotal because of the
 630                      * tile itself, of course; one tile linking
 631                      * dead ends of size 2 and 3 forms a subnetwork
 632                      * with a total area of 6, not 5.)
 633                      */
 634                     if (deadendtotal+1 < area)
 635                         valid = FALSE;
 636                 } else if (nnondeadends == 1) {
 637                     /*
 638                      * If this orientation links together one or
 639                      * more dead-ends with precisely one
 640                      * non-dead-end, then we may have to mark that
 641                      * non-dead-end as a dead end going the other
 642                      * way. However, it depends on whether all
 643                      * other orientations share the same property.
 644                      */
 645                     deadendtotal++;
 646                     if (deadendmax[nondeadends[0]] < deadendtotal)
 647                         deadendmax[nondeadends[0]] = deadendtotal;
 648                 } else {
 649                     /*
 650                      * If this orientation links together two or
 651                      * more non-dead-ends, then we can rule out the
 652                      * possibility of putting in new dead-end
 653                      * markings in those directions.
 654                      */
 655                     int k;
 656                     for (k = 0; k < nnondeadends; k++)
 657                         deadendmax[nondeadends[k]] = area+1;
 658                 }
 659
 660                 if (valid)
 661                     tilestate[(y*w+x) * 4 + j++] = val;
 662 #ifdef SOLVER_DIAGNOSTICS
 663                 else
 664                     printf("ruling out orientation %x at %d,%d\n", val, x, y);
 665 #endif
 666             }
 667
 668             assert(j > 0);             /* we can't lose _all_ possibilities! */
 669
 670             if (j < i) {
 671                 int a, o;
 672                 done_something = TRUE;
 673
 674                 /*
 675                  * We have ruled out at least one tile orientation.
 676                  * Make sure the rest are blanked.
 677                  */
 678                 while (j < 4)
 679                     tilestate[(y*w+x) * 4 + j++] = 255;
 680
 681                 /*
 682                  * Now go through them again and see if we've
 683                  * deduced anything new about any edges.
 684                  */
 685                 a = 0xF; o = 0;
 686                 for (i = 0; i < 4 && tilestate[(y*w+x) * 4 + i] != 255; i++) {
 687                     a &= tilestate[(y*w+x) * 4 + i];
 688                     o |= tilestate[(y*w+x) * 4 + i];
 689                 }
 690                 for (d = 1; d <= 8; d += d)
 691                     if (edgestate[(y*w+x) * 5 + d] == 0) {
 692                         int x2, y2, d2;
 693                         OFFSETWH(x2, y2, x, y, d, w, h);
 694                         d2 = F(d);
 695                         if (a & d) {
 696                             /* This edge is open in all orientations. */
 697 #ifdef SOLVER_DIAGNOSTICS
 698                             printf("marking edge %d,%d:%d open\n", x, y, d);
 699 #endif
 700                             edgestate[(y*w+x) * 5 + d] = 1;
 701                             edgestate[(y2*w+x2) * 5 + d2] = 1;
 702                             dsf_merge(equivalence, y*w+x, y2*w+x2);
 703                             done_something = TRUE;
 704                             todo_add(todo, y2*w+x2);
 705                         } else if (!(o & d)) {
 706                             /* This edge is closed in all orientations. */
 707 #ifdef SOLVER_DIAGNOSTICS
 708                             printf("marking edge %d,%d:%d closed\n", x, y, d);
 709 #endif
 710                             edgestate[(y*w+x) * 5 + d] = 2;
 711                             edgestate[(y2*w+x2) * 5 + d2] = 2;
 712                             done_something = TRUE;
 713                             todo_add(todo, y2*w+x2);
 714                         }
 715                     }
 716
 717             }
 718
 719             /*
 720              * Now check the dead-end markers and see if any of
 721              * them has lowered from the real ones.
 722              */
 723             for (d = 1; d <= 8; d += d) {
 724                 int x2, y2, d2;
 725                 OFFSETWH(x2, y2, x, y, d, w, h);
 726                 d2 = F(d);
 727                 if (deadendmax[d] > 0 &&
 728                     deadends[(y2*w+x2) * 5 + d2] > deadendmax[d]) {
 729 #ifdef SOLVER_DIAGNOSTICS
 730                     printf("setting dead end value %d,%d:%d to %d\n",
 731                            x2, y2, d2, deadendmax[d]);
 732 #endif
 733                     deadends[(y2*w+x2) * 5 + d2] = deadendmax[d];
 734                     done_something = TRUE;
 735                     todo_add(todo, y2*w+x2);
 736                 }
 737             }
 738
 739         }
 740     }
 741
 742     /*
 743      * Mark all completely determined tiles as locked.
 744      */
 745     j = TRUE;
 746     for (i = 0; i < w*h; i++) {
 747         if (tilestate[i * 4 + 1] == 255) {
 748             assert(tilestate[i * 4 + 0] != 255);
 749             tiles[i] = tilestate[i * 4] | LOCKED;
 750         } else {
 751             tiles[i] &= ~LOCKED;
 752             j = FALSE;
 753         }
 754     }
 755
 756     /*
 757      * Free up working space.
 758      */
 759     todo_free(todo);
 760     sfree(tilestate);
 761     sfree(edgestate);
 762     sfree(deadends);
 763     sfree(equivalence);
 764
 765     return j;
 766 }
 767
 768 /* ----------------------------------------------------------------------
 769  * Randomly select a new game description.
 770  */
 771
 772 /*
 773  * Function to randomly perturb an ambiguous section in a grid, to
 774  * attempt to ensure unique solvability.
 775  */
 776 static void perturb(int w, int h, unsigned char *tiles, int wrapping,
 777                     random_state *rs, int startx, int starty, int startd)
 778 {
 779     struct xyd *perimeter, *perim2, *loop[2], looppos[2];
 780     int nperim, perimsize, nloop[2], loopsize[2];
 781     int x, y, d, i;
 782
 783     /*
 784      * We know that the tile at (startx,starty) is part of an
 785      * ambiguous section, and we also know that its neighbour in
 786      * direction startd is fully specified. We begin by tracing all
 787      * the way round the ambiguous area.
 788      */
 789     nperim = perimsize = 0;
 790     perimeter = NULL;
 791     x = startx;
 792     y = starty;
 793     d = startd;
 794 #ifdef PERTURB_DIAGNOSTICS
 795     printf("perturb %d,%d:%d\n", x, y, d);
 796 #endif
 797     do {
 798         int x2, y2, d2;
 799
 800         if (nperim >= perimsize) {
 801             perimsize = perimsize * 3 / 2 + 32;
 802             perimeter = sresize(perimeter, perimsize, struct xyd);
 803         }
 804         perimeter[nperim].x = x;
 805         perimeter[nperim].y = y;
 806         perimeter[nperim].direction = d;
 807         nperim++;
 808 #ifdef PERTURB_DIAGNOSTICS
 809         printf("perimeter: %d,%d:%d\n", x, y, d);
 810 #endif
 811
 812         /*
 813          * First, see if we can simply turn left from where we are
 814          * and find another locked square.
 815          */
 816         d2 = A(d);
 817         OFFSETWH(x2, y2, x, y, d2, w, h);
 818         if ((!wrapping && (abs(x2-x) > 1 || abs(y2-y) > 1)) ||
 819             (tiles[y2*w+x2] & LOCKED)) {
 820             d = d2;
 821         } else {
 822             /*
 823              * Failing that, step left into the new square and look
 824              * in front of us.
 825              */
 826             x = x2;
 827             y = y2;
 828             OFFSETWH(x2, y2, x, y, d, w, h);
 829             if ((wrapping || (abs(x2-x) <= 1 && abs(y2-y) <= 1)) &&
 830                 !(tiles[y2*w+x2] & LOCKED)) {
 831                 /*
 832                  * And failing _that_, we're going to have to step
 833                  * forward into _that_ square and look right at the
 834                  * same locked square as we started with.
 835                  */
 836                 x = x2;
 837                 y = y2;
 838                 d = C(d);
 839             }
 840         }
 841
 842     } while (x != startx || y != starty || d != startd);
 843
 844     /*
 845      * Our technique for perturbing this ambiguous area is to
 846      * search round its edge for a join we can make: that is, an
 847      * edge on the perimeter which is (a) not currently connected,
 848      * and (b) connecting it would not yield a full cross on either
 849      * side. Then we make that join, search round the network to
 850      * find the loop thus constructed, and sever the loop at a
 851      * randomly selected other point.
 852      */
 853     perim2 = snewn(nperim, struct xyd);
 854     memcpy(perim2, perimeter, nperim * sizeof(struct xyd));
 855     /* Shuffle the perimeter, so as to search it without directional bias. */
 856     for (i = nperim; --i ;) {
 857         int j = random_upto(rs, i+1);
 858         struct xyd t;
 859
 860         t = perim2[j];
 861         perim2[j] = perim2[i];
 862         perim2[i] = t;
 863     }
 864     for (i = 0; i < nperim; i++) {
 865         int x2, y2;
 866
 867         x = perim2[i].x;
 868         y = perim2[i].y;
 869         d = perim2[i].direction;
 870
 871         OFFSETWH(x2, y2, x, y, d, w, h);
 872         if (!wrapping && (abs(x2-x) > 1 || abs(y2-y) > 1))
 873             continue;            /* can't link across non-wrapping border */
 874         if (tiles[y*w+x] & d)
 875             continue;                  /* already linked in this direction! */
 876         if (((tiles[y*w+x] | d) & 15) == 15)
 877             continue;                  /* can't turn this tile into a cross */
 878         if (((tiles[y2*w+x2] | F(d)) & 15) == 15)
 879             continue;                  /* can't turn other tile into a cross */
 880
 881         /*
 882          * We've found the point at which we're going to make a new
 883          * link.
 884          */
 885 #ifdef PERTURB_DIAGNOSTICS
 886         printf("linking %d,%d:%d\n", x, y, d);
 887 #endif
 888         tiles[y*w+x] |= d;
 889         tiles[y2*w+x2] |= F(d);
 890
 891         break;
 892     }
 893
 894     if (i == nperim)
 895         return;                        /* nothing we can do! */
 896
 897     /*
 898      * Now we've constructed a new link, we need to find the entire
 899      * loop of which it is a part.
 900      *
 901      * In principle, this involves doing a complete search round
 902      * the network. However, I anticipate that in the vast majority
 903      * of cases the loop will be quite small, so what I'm going to
 904      * do is make _two_ searches round the network in parallel, one
 905      * keeping its metaphorical hand on the left-hand wall while
 906      * the other keeps its hand on the right. As soon as one of
 907      * them gets back to its starting point, I abandon the other.
 908      */
 909     for (i = 0; i < 2; i++) {
 910         loopsize[i] = nloop[i] = 0;
 911         loop[i] = NULL;
 912         looppos[i].x = x;
 913         looppos[i].y = y;
 914         looppos[i].direction = d;
 915     }
 916     while (1) {
 917         for (i = 0; i < 2; i++) {
 918             int x2, y2, j;
 919
 920             x = looppos[i].x;
 921             y = looppos[i].y;
 922             d = looppos[i].direction;
 923
 924             OFFSETWH(x2, y2, x, y, d, w, h);
 925
 926             /*
 927              * Add this path segment to the loop, unless it exactly
 928              * reverses the previous one on the loop in which case
 929              * we take it away again.
 930              */
 931 #ifdef PERTURB_DIAGNOSTICS
 932             printf("looppos[%d] = %d,%d:%d\n", i, x, y, d);
 933 #endif
 934             if (nloop[i] > 0 &&
 935                 loop[i][nloop[i]-1].x == x2 &&
 936                 loop[i][nloop[i]-1].y == y2 &&
 937                 loop[i][nloop[i]-1].direction == F(d)) {
 938 #ifdef PERTURB_DIAGNOSTICS
 939                 printf("removing path segment %d,%d:%d from loop[%d]\n",
 940                        x2, y2, F(d), i);
 941 #endif
 942                 nloop[i]--;
 943             } else {
 944                 if (nloop[i] >= loopsize[i]) {
 945                     loopsize[i] = loopsize[i] * 3 / 2 + 32;
 946                     loop[i] = sresize(loop[i], loopsize[i], struct xyd);
 947                 }
 948 #ifdef PERTURB_DIAGNOSTICS
 949                 printf("adding path segment %d,%d:%d to loop[%d]\n",
 950                        x, y, d, i);
 951 #endif
 952                 loop[i][nloop[i]++] = looppos[i];
 953             }
 954
 955 #ifdef PERTURB_DIAGNOSTICS
 956             printf("tile at new location is %x\n", tiles[y2*w+x2] & 0xF);
 957 #endif
 958             d = F(d);
 959             for (j = 0; j < 4; j++) {
 960                 if (i == 0)
 961                     d = A(d);
 962                 else
 963                     d = C(d);
 964 #ifdef PERTURB_DIAGNOSTICS
 965                 printf("trying dir %d\n", d);
 966 #endif
 967                 if (tiles[y2*w+x2] & d) {
 968                     looppos[i].x = x2;
 969                     looppos[i].y = y2;
 970                     looppos[i].direction = d;
 971                     break;
 972                 }
 973             }
 974
 975             assert(j < 4);
 976             assert(nloop[i] > 0);
 977
 978             if (looppos[i].x == loop[i][0].x &&
 979                 looppos[i].y == loop[i][0].y &&
 980                 looppos[i].direction == loop[i][0].direction) {
 981 #ifdef PERTURB_DIAGNOSTICS
 982                 printf("loop %d finished tracking\n", i);
 983 #endif
 984
 985                 /*
 986                  * Having found our loop, we now sever it at a
 987                  * randomly chosen point - absolutely any will do -
 988                  * which is not the one we joined it at to begin
 989                  * with. Conveniently, the one we joined it at is
 990                  * loop[i][0], so we just avoid that one.
 991                  */
 992                 j = random_upto(rs, nloop[i]-1) + 1;
 993                 x = loop[i][j].x;
 994                 y = loop[i][j].y;
 995                 d = loop[i][j].direction;
 996                 OFFSETWH(x2, y2, x, y, d, w, h);
 997                 tiles[y*w+x] &= ~d;
 998                 tiles[y2*w+x2] &= ~F(d);
 999
1000                 break;
1001             }
1002         }
1003         if (i < 2)
1004             break;
1005     }
1006     sfree(loop[0]);
1007     sfree(loop[1]);
1008
1009     /*
1010      * Finally, we must mark the entire disputed section as locked,
1011      * to prevent the perturb function being called on it multiple
1012      * times.
1013      *
1014      * To do this, we _sort_ the perimeter of the area. The
1015      * existing xyd_cmp function will arrange things into columns
1016      * for us, in such a way that each column has the edges in
1017      * vertical order. Then we can work down each column and fill
1018      * in all the squares between an up edge and a down edge.
1019      */
1020     qsort(perimeter, nperim, sizeof(struct xyd), xyd_cmp);
1021     x = y = -1;
1022     for (i = 0; i <= nperim; i++) {
1023         if (i == nperim || perimeter[i].x > x) {
1024             /*
1025              * Fill in everything from the last Up edge to the
1026              * bottom of the grid, if necessary.
1027              */
1028             if (x != -1) {
1029                 while (y < h) {
1030 #ifdef PERTURB_DIAGNOSTICS
1031                     printf("resolved: locking tile %d,%d\n", x, y);
1032 #endif
1033                     tiles[y * w + x] |= LOCKED;
1034                     y++;
1035                 }
1036                 x = y = -1;
1037             }
1038
1039             if (i == nperim)
1040                 break;
1041
1042             x = perimeter[i].x;
1043             y = 0;
1044         }
1045
1046         if (perimeter[i].direction == U) {
1047             x = perimeter[i].x;
1048             y = perimeter[i].y;
1049         } else if (perimeter[i].direction == D) {
1050             /*
1051              * Fill in everything from the last Up edge to here.
1052              */
1053             assert(x == perimeter[i].x && y <= perimeter[i].y);
1054             while (y <= perimeter[i].y) {
1055 #ifdef PERTURB_DIAGNOSTICS
1056                 printf("resolved: locking tile %d,%d\n", x, y);
1057 #endif
1058                 tiles[y * w + x] |= LOCKED;
1059                 y++;
1060             }
1061             x = y = -1;
1062         }
1063     }
1064
1065     sfree(perimeter);
1066 }
1067
1068 static char *new_game_desc(game_params *params, random_state *rs,
1069                            game_aux_info **aux)
1070 {
1071     tree234 *possibilities, *barriertree;
1072     int w, h, x, y, cx, cy, nbarriers;
1073     unsigned char *tiles, *barriers;
1074     char *desc, *p;
1075
1076     w = params->width;
1077     h = params->height;
1078
1079     cx = w / 2;
1080     cy = h / 2;
1081
1082     tiles = snewn(w * h, unsigned char);
1083     barriers = snewn(w * h, unsigned char);
1084
1085     begin_generation:
1086
1087     memset(tiles, 0, w * h);
1088     memset(barriers, 0, w * h);
1089
1090     /*
1091      * Construct the unshuffled grid.
1092      *
1093      * To do this, we simply start at the centre point, repeatedly
1094      * choose a random possibility out of the available ways to
1095      * extend a used square into an unused one, and do it. After
1096      * extending the third line out of a square, we remove the
1097      * fourth from the possibilities list to avoid any full-cross
1098      * squares (which would make the game too easy because they
1099      * only have one orientation).
1100      *
1101      * The slightly worrying thing is the avoidance of full-cross
1102      * squares. Can this cause our unsophisticated construction
1103      * algorithm to paint itself into a corner, by getting into a
1104      * situation where there are some unreached squares and the
1105      * only way to reach any of them is to extend a T-piece into a
1106      * full cross?
1107      *
1108      * Answer: no it can't, and here's a proof.
1109      *
1110      * Any contiguous group of such unreachable squares must be
1111      * surrounded on _all_ sides by T-pieces pointing away from the
1112      * group. (If not, then there is a square which can be extended
1113      * into one of the `unreachable' ones, and so it wasn't
1114      * unreachable after all.) In particular, this implies that
1115      * each contiguous group of unreachable squares must be
1116      * rectangular in shape (any deviation from that yields a
1117      * non-T-piece next to an `unreachable' square).
1118      *
1119      * So we have a rectangle of unreachable squares, with T-pieces
1120      * forming a solid border around the rectangle. The corners of
1121      * that border must be connected (since every tile connects all
1122      * the lines arriving in it), and therefore the border must
1123      * form a closed loop around the rectangle.
1124      *
1125      * But this can't have happened in the first place, since we
1126      * _know_ we've avoided creating closed loops! Hence, no such
1127      * situation can ever arise, and the naive grid construction
1128      * algorithm will guaranteeably result in a complete grid
1129      * containing no unreached squares, no full crosses _and_ no
1130      * closed loops. []
1131      */
1132     possibilities = newtree234(xyd_cmp_nc);
1133
1134     if (cx+1 < w)
1135         add234(possibilities, new_xyd(cx, cy, R));
1136     if (cy-1 >= 0)
1137         add234(possibilities, new_xyd(cx, cy, U));
1138     if (cx-1 >= 0)
1139         add234(possibilities, new_xyd(cx, cy, L));
1140     if (cy+1 < h)
1141         add234(possibilities, new_xyd(cx, cy, D));
1142
1143     while (count234(possibilities) > 0) {
1144         int i;
1145         struct xyd *xyd;
1146         int x1, y1, d1, x2, y2, d2, d;
1147
1148         /*
1149          * Extract a randomly chosen possibility from the list.
1150          */
1151         i = random_upto(rs, count234(possibilities));
1152         xyd = delpos234(possibilities, i);
1153         x1 = xyd->x;
1154         y1 = xyd->y;
1155         d1 = xyd->direction;
1156         sfree(xyd);
1157
1158         OFFSET(x2, y2, x1, y1, d1, params);
1159         d2 = F(d1);
1160 #ifdef DEBUG
1161         printf("picked (%d,%d,%c) <-> (%d,%d,%c)\n",
1162                x1, y1, "0RU3L567D9abcdef"[d1], x2, y2, "0RU3L567D9abcdef"[d2]);
1163 #endif
1164
1165         /*
1166          * Make the connection. (We should be moving to an as yet
1167          * unused tile.)
1168          */
1169         index(params, tiles, x1, y1) |= d1;
1170         assert(index(params, tiles, x2, y2) == 0);
1171         index(params, tiles, x2, y2) |= d2;
1172
1173         /*
1174          * If we have created a T-piece, remove its last
1175          * possibility.
1176          */
1177         if (COUNT(index(params, tiles, x1, y1)) == 3) {
1178             struct xyd xyd1, *xydp;
1179
1180             xyd1.x = x1;
1181             xyd1.y = y1;
1182             xyd1.direction = 0x0F ^ index(params, tiles, x1, y1);
1183
1184             xydp = find234(possibilities, &xyd1, NULL);
1185
1186             if (xydp) {
1187 #ifdef DEBUG
1188                 printf("T-piece; removing (%d,%d,%c)\n",
1189                        xydp->x, xydp->y, "0RU3L567D9abcdef"[xydp->direction]);
1190 #endif
1191                 del234(possibilities, xydp);
1192                 sfree(xydp);
1193             }
1194         }
1195
1196         /*
1197          * Remove all other possibilities that were pointing at the
1198          * tile we've just moved into.
1199          */
1200         for (d = 1; d < 0x10; d <<= 1) {
1201             int x3, y3, d3;
1202             struct xyd xyd1, *xydp;
1203
1204             OFFSET(x3, y3, x2, y2, d, params);
1205             d3 = F(d);
1206
1207             xyd1.x = x3;
1208             xyd1.y = y3;
1209             xyd1.direction = d3;
1210
1211             xydp = find234(possibilities, &xyd1, NULL);
1212
1213             if (xydp) {
1214 #ifdef DEBUG
1215                 printf("Loop avoidance; removing (%d,%d,%c)\n",
1216                        xydp->x, xydp->y, "0RU3L567D9abcdef"[xydp->direction]);
1217 #endif
1218                 del234(possibilities, xydp);
1219                 sfree(xydp);
1220             }
1221         }
1222
1223         /*
1224          * Add new possibilities to the list for moving _out_ of
1225          * the tile we have just moved into.
1226          */
1227         for (d = 1; d < 0x10; d <<= 1) {
1228             int x3, y3;
1229
1230             if (d == d2)
1231                 continue;              /* we've got this one already */
1232
1233             if (!params->wrapping) {
1234                 if (d == U && y2 == 0)
1235                     continue;
1236                 if (d == D && y2 == h-1)
1237                     continue;
1238                 if (d == L && x2 == 0)
1239                     continue;
1240                 if (d == R && x2 == w-1)
1241                     continue;
1242             }
1243
1244             OFFSET(x3, y3, x2, y2, d, params);
1245
1246             if (index(params, tiles, x3, y3))
1247                 continue;              /* this would create a loop */
1248
1249 #ifdef DEBUG
1250             printf("New frontier; adding (%d,%d,%c)\n",
1251                    x2, y2, "0RU3L567D9abcdef"[d]);
1252 #endif
1253             add234(possibilities, new_xyd(x2, y2, d));
1254         }
1255     }
1256     /* Having done that, we should have no possibilities remaining. */
1257     assert(count234(possibilities) == 0);
1258     freetree234(possibilities);
1259
1260     if (params->unique) {
1261         int prevn = -1;
1262
1263         /*
1264          * Run the solver to check unique solubility.
1265          */
1266         while (!net_solver(w, h, tiles, params->wrapping)) {
1267             int n = 0;
1268
1269             /*
1270              * We expect (in most cases) that most of the grid will
1271              * be uniquely specified already, and the remaining
1272              * ambiguous sections will be small and separate. So
1273              * our strategy is to find each individual such
1274              * section, and perform a perturbation on the network
1275              * in that area.
1276              */
1277             for (y = 0; y < h; y++) for (x = 0; x < w; x++) {
1278                 if (x+1 < w && ((tiles[y*w+x] ^ tiles[y*w+x+1]) & LOCKED)) {
1279                     n++;
1280                     if (tiles[y*w+x] & LOCKED)
1281                         perturb(w, h, tiles, params->wrapping, rs, x+1, y, L);
1282                     else
1283                         perturb(w, h, tiles, params->wrapping, rs, x, y, R);
1284                 }
1285                 if (y+1 < h && ((tiles[y*w+x] ^ tiles[(y+1)*w+x]) & LOCKED)) {
1286                     n++;
1287                     if (tiles[y*w+x] & LOCKED)
1288                         perturb(w, h, tiles, params->wrapping, rs, x, y+1, U);
1289                     else
1290                         perturb(w, h, tiles, params->wrapping, rs, x, y, D);
1291                 }
1292             }
1293
1294             /*
1295              * Now n counts the number of ambiguous sections we
1296              * have fiddled with. If we haven't managed to decrease
1297              * it from the last time we ran the solver, give up and
1298              * regenerate the entire grid.
1299              */
1300             if (prevn != -1 && prevn <= n)
1301                 goto begin_generation; /* (sorry) */
1302
1303             prevn = n;
1304         }
1305
1306         /*
1307          * The solver will have left a lot of LOCKED bits lying
1308          * around in the tiles array. Remove them.
1309          */
1310         for (x = 0; x < w*h; x++)
1311             tiles[x] &= ~LOCKED;
1312     }
1313
1314     /*
1315      * Now compute a list of the possible barrier locations.
1316      */
1317     barriertree = newtree234(xyd_cmp_nc);
1318     for (y = 0; y < h; y++) {
1319         for (x = 0; x < w; x++) {
1320
1321             if (!(index(params, tiles, x, y) & R) &&
1322                 (params->wrapping || x < w-1))
1323                 add234(barriertree, new_xyd(x, y, R));
1324             if (!(index(params, tiles, x, y) & D) &&
1325                 (params->wrapping || y < h-1))
1326                 add234(barriertree, new_xyd(x, y, D));
1327         }
1328     }
1329
1330     /*
1331      * Save the unshuffled grid in an aux_info.
1332      */
1333     {
1334         game_aux_info *solution;
1335
1336         solution = snew(game_aux_info);
1337         solution->width = w;
1338         solution->height = h;
1339         solution->tiles = snewn(w * h, unsigned char);
1340         memcpy(solution->tiles, tiles, w * h);
1341
1342         *aux = solution;
1343     }
1344
1345     /*
1346      * Now shuffle the grid.
1347      */
1348     for (y = 0; y < h; y++) {
1349         for (x = 0; x < w; x++) {
1350             int orig = index(params, tiles, x, y);
1351             int rot = random_upto(rs, 4);
1352             index(params, tiles, x, y) = ROT(orig, rot);
1353         }
1354     }
1355
1356     /*
1357      * And now choose barrier locations. (We carefully do this
1358      * _after_ shuffling, so that changing the barrier rate in the
1359      * params while keeping the random seed the same will give the
1360      * same shuffled grid and _only_ change the barrier locations.
1361      * Also the way we choose barrier locations, by repeatedly
1362      * choosing one possibility from the list until we have enough,
1363      * is designed to ensure that raising the barrier rate while
1364      * keeping the seed the same will provide a superset of the
1365      * previous barrier set - i.e. if you ask for 10 barriers, and
1366      * then decide that's still too hard and ask for 20, you'll get
1367      * the original 10 plus 10 more, rather than getting 20 new
1368      * ones and the chance of remembering your first 10.)
1369      */
1370     nbarriers = (int)(params->barrier_probability * count234(barriertree));
1371     assert(nbarriers >= 0 && nbarriers <= count234(barriertree));
1372
1373     while (nbarriers > 0) {
1374         int i;
1375         struct xyd *xyd;
1376         int x1, y1, d1, x2, y2, d2;
1377
1378         /*
1379          * Extract a randomly chosen barrier from the list.
1380          */
1381         i = random_upto(rs, count234(barriertree));
1382         xyd = delpos234(barriertree, i);
1383
1384         assert(xyd != NULL);
1385
1386         x1 = xyd->x;
1387         y1 = xyd->y;
1388         d1 = xyd->direction;
1389         sfree(xyd);
1390
1391         OFFSET(x2, y2, x1, y1, d1, params);
1392         d2 = F(d1);
1393
1394         index(params, barriers, x1, y1) |= d1;
1395         index(params, barriers, x2, y2) |= d2;
1396
1397         nbarriers--;
1398     }
1399
1400     /*
1401      * Clean up the rest of the barrier list.
1402      */
1403     {
1404         struct xyd *xyd;
1405
1406         while ( (xyd = delpos234(barriertree, 0)) != NULL)
1407             sfree(xyd);
1408
1409         freetree234(barriertree);
1410     }
1411
1412     /*
1413      * Finally, encode the grid into a string game description.
1414      *
1415      * My syntax is extremely simple: each square is encoded as a
1416      * hex digit in which bit 0 means a connection on the right,
1417      * bit 1 means up, bit 2 left and bit 3 down. (i.e. the same
1418      * encoding as used internally). Each digit is followed by
1419      * optional barrier indicators: `v' means a vertical barrier to
1420      * the right of it, and `h' means a horizontal barrier below
1421      * it.
1422      */
1423     desc = snewn(w * h * 3 + 1, char);
1424     p = desc;
1425     for (y = 0; y < h; y++) {
1426         for (x = 0; x < w; x++) {
1427             *p++ = "0123456789abcdef"[index(params, tiles, x, y)];
1428             if ((params->wrapping || x < w-1) &&
1429                 (index(params, barriers, x, y) & R))
1430                 *p++ = 'v';
1431             if ((params->wrapping || y < h-1) &&
1432                 (index(params, barriers, x, y) & D))
1433                 *p++ = 'h';
1434         }
1435     }
1436     assert(p - desc <= w*h*3);
1437     *p = '\0';
1438
1439     sfree(tiles);
1440     sfree(barriers);
1441
1442     return desc;
1443 }
1444
1445 static void game_free_aux_info(game_aux_info *aux)
1446 {
1447     sfree(aux->tiles);
1448     sfree(aux);
1449 }
1450
1451 static char *validate_desc(game_params *params, char *desc)
1452 {
1453     int w = params->width, h = params->height;
1454     int i;
1455
1456     for (i = 0; i < w*h; i++) {
1457         if (*desc >= '0' && *desc <= '9')
1458             /* OK */;
1459         else if (*desc >= 'a' && *desc <= 'f')
1460             /* OK */;
1461         else if (*desc >= 'A' && *desc <= 'F')
1462             /* OK */;
1463         else if (!*desc)
1464             return "Game description shorter than expected";
1465         else
1466             return "Game description contained unexpected character";
1467         desc++;
1468         while (*desc == 'h' || *desc == 'v')
1469             desc++;
1470     }
1471     if (*desc)
1472         return "Game description longer than expected";
1473
1474     return NULL;
1475 }
1476
1477 /* ----------------------------------------------------------------------
1478  * Construct an initial game state, given a description and parameters.
1479  */
1480
1481 static game_state *new_game(game_params *params, char *desc)
1482 {
1483     game_state *state;
1484     int w, h, x, y;
1485
1486     assert(params->width > 0 && params->height > 0);
1487     assert(params->width > 1 || params->height > 1);
1488
1489     /*
1490      * Create a blank game state.
1491      */
1492     state = snew(game_state);
1493     w = state->width = params->width;
1494     h = state->height = params->height;
1495     state->cx = state->width / 2;
1496     state->cy = state->height / 2;
1497     state->wrapping = params->wrapping;
1498     state->last_rotate_dir = state->last_rotate_x = state->last_rotate_y = 0;
1499     state->completed = state->used_solve = state->just_used_solve = FALSE;
1500     state->tiles = snewn(state->width * state->height, unsigned char);
1501     memset(state->tiles, 0, state->width * state->height);
1502     state->barriers = snewn(state->width * state->height, unsigned char);
1503     memset(state->barriers, 0, state->width * state->height);
1504
1505     /*
1506      * Parse the game description into the grid.
1507      */
1508     for (y = 0; y < h; y++) {
1509         for (x = 0; x < w; x++) {
1510             if (*desc >= '0' && *desc <= '9')
1511                 tile(state, x, y) = *desc - '0';
1512             else if (*desc >= 'a' && *desc <= 'f')
1513                 tile(state, x, y) = *desc - 'a' + 10;
1514             else if (*desc >= 'A' && *desc <= 'F')
1515                 tile(state, x, y) = *desc - 'A' + 10;
1516             if (*desc)
1517                 desc++;
1518             while (*desc == 'h' || *desc == 'v') {
1519                 int x2, y2, d1, d2;
1520                 if (*desc == 'v')
1521                     d1 = R;
1522                 else
1523                     d1 = D;
1524
1525                 OFFSET(x2, y2, x, y, d1, state);
1526                 d2 = F(d1);
1527
1528                 barrier(state, x, y) |= d1;
1529                 barrier(state, x2, y2) |= d2;
1530
1531                 desc++;
1532             }
1533         }
1534     }
1535
1536     /*
1537      * Set up border barriers if this is a non-wrapping game.
1538      */
1539     if (!state->wrapping) {
1540         for (x = 0; x < state->width; x++) {
1541             barrier(state, x, 0) |= U;
1542             barrier(state, x, state->height-1) |= D;
1543         }
1544         for (y = 0; y < state->height; y++) {
1545             barrier(state, 0, y) |= L;
1546             barrier(state, state->width-1, y) |= R;
1547         }
1548     }
1549
1550     /*
1551      * Set up the barrier corner flags, for drawing barriers
1552      * prettily when they meet.
1553      */
1554     for (y = 0; y < state->height; y++) {
1555         for (x = 0; x < state->width; x++) {
1556             int dir;
1557
1558             for (dir = 1; dir < 0x10; dir <<= 1) {
1559                 int dir2 = A(dir);
1560                 int x1, y1, x2, y2, x3, y3;
1561                 int corner = FALSE;
1562
1563                 if (!(barrier(state, x, y) & dir))
1564                     continue;
1565
1566                 if (barrier(state, x, y) & dir2)
1567                     corner = TRUE;
1568
1569                 x1 = x + X(dir), y1 = y + Y(dir);
1570                 if (x1 >= 0 && x1 < state->width &&
1571                     y1 >= 0 && y1 < state->height &&
1572                     (barrier(state, x1, y1) & dir2))
1573                     corner = TRUE;
1574
1575                 x2 = x + X(dir2), y2 = y + Y(dir2);
1576                 if (x2 >= 0 && x2 < state->width &&
1577                     y2 >= 0 && y2 < state->height &&
1578                     (barrier(state, x2, y2) & dir))
1579                     corner = TRUE;
1580
1581                 if (corner) {
1582                     barrier(state, x, y) |= (dir << 4);
1583                     if (x1 >= 0 && x1 < state->width &&
1584                         y1 >= 0 && y1 < state->height)
1585                         barrier(state, x1, y1) |= (A(dir) << 4);
1586                     if (x2 >= 0 && x2 < state->width &&
1587                         y2 >= 0 && y2 < state->height)
1588                         barrier(state, x2, y2) |= (C(dir) << 4);
1589                     x3 = x + X(dir) + X(dir2), y3 = y + Y(dir) + Y(dir2);
1590                     if (x3 >= 0 && x3 < state->width &&
1591                         y3 >= 0 && y3 < state->height)
1592                         barrier(state, x3, y3) |= (F(dir) << 4);
1593                 }
1594             }
1595         }
1596     }
1597
1598     return state;
1599 }
1600
1601 static game_state *dup_game(game_state *state)
1602 {
1603     game_state *ret;
1604
1605     ret = snew(game_state);
1606     ret->width = state->width;
1607     ret->height = state->height;
1608     ret->cx = state->cx;
1609     ret->cy = state->cy;
1610     ret->wrapping = state->wrapping;
1611     ret->completed = state->completed;
1612     ret->used_solve = state->used_solve;
1613     ret->just_used_solve = state->just_used_solve;
1614     ret->last_rotate_dir = state->last_rotate_dir;
1615     ret->last_rotate_x = state->last_rotate_x;
1616     ret->last_rotate_y = state->last_rotate_y;
1617     ret->tiles = snewn(state->width * state->height, unsigned char);
1618     memcpy(ret->tiles, state->tiles, state->width * state->height);
1619     ret->barriers = snewn(state->width * state->height, unsigned char);
1620     memcpy(ret->barriers, state->barriers, state->width * state->height);
1621
1622     return ret;
1623 }
1624
1625 static void free_game(game_state *state)
1626 {
1627     sfree(state->tiles);
1628     sfree(state->barriers);
1629     sfree(state);
1630 }
1631
1632 static game_state *solve_game(game_state *state, game_aux_info *aux,
1633                               char **error)
1634 {
1635     game_state *ret;
1636
1637     if (!aux) {
1638         /*
1639          * Run the internal solver on the provided grid. This might
1640          * not yield a complete solution.
1641          */
1642         ret = dup_game(state);
1643         net_solver(ret->width, ret->height, ret->tiles, ret->wrapping);
1644     } else {
1645         assert(aux->width == state->width);
1646         assert(aux->height == state->height);
1647         ret = dup_game(state);
1648         memcpy(ret->tiles, aux->tiles, ret->width * ret->height);
1649         ret->used_solve = ret->just_used_solve = TRUE;
1650         ret->completed = TRUE;
1651     }
1652
1653     return ret;
1654 }
1655
1656 static char *game_text_format(game_state *state)
1657 {
1658     return NULL;
1659 }
1660
1661 /* ----------------------------------------------------------------------
1662  * Utility routine.
1663  */
1664
1665 /*
1666  * Compute which squares are reachable from the centre square, as a
1667  * quick visual aid to determining how close the game is to
1668  * completion. This is also a simple way to tell if the game _is_
1669  * completed - just call this function and see whether every square
1670  * is marked active.
1671  */
1672 static unsigned char *compute_active(game_state *state)
1673 {
1674     unsigned char *active;
1675     tree234 *todo;
1676     struct xyd *xyd;
1677
1678     active = snewn(state->width * state->height, unsigned char);
1679     memset(active, 0, state->width * state->height);
1680
1681     /*
1682      * We only store (x,y) pairs in todo, but it's easier to reuse
1683      * xyd_cmp and just store direction 0 every time.
1684      */
1685     todo = newtree234(xyd_cmp_nc);
1686     index(state, active, state->cx, state->cy) = ACTIVE;
1687     add234(todo, new_xyd(state->cx, state->cy, 0));
1688
1689     while ( (xyd = delpos234(todo, 0)) != NULL) {
1690         int x1, y1, d1, x2, y2, d2;
1691
1692         x1 = xyd->x;
1693         y1 = xyd->y;
1694         sfree(xyd);
1695
1696         for (d1 = 1; d1 < 0x10; d1 <<= 1) {
1697             OFFSET(x2, y2, x1, y1, d1, state);
1698             d2 = F(d1);
1699
1700             /*
1701              * If the next tile in this direction is connected to
1702              * us, and there isn't a barrier in the way, and it
1703              * isn't already marked active, then mark it active and
1704              * add it to the to-examine list.
1705              */
1706             if ((tile(state, x1, y1) & d1) &&
1707                 (tile(state, x2, y2) & d2) &&
1708                 !(barrier(state, x1, y1) & d1) &&
1709                 !index(state, active, x2, y2)) {
1710                 index(state, active, x2, y2) = ACTIVE;
1711                 add234(todo, new_xyd(x2, y2, 0));
1712             }
1713         }
1714     }
1715     /* Now we expect the todo list to have shrunk to zero size. */
1716     assert(count234(todo) == 0);
1717     freetree234(todo);
1718
1719     return active;
1720 }
1721
1722 struct game_ui {
1723     int cur_x, cur_y;
1724     int cur_visible;
1725     random_state *rs; /* used for jumbling */
1726 };
1727
1728 static game_ui *new_ui(game_state *state)
1729 {
1730     void *seed;
1731     int seedsize;
1732     game_ui *ui = snew(game_ui);
1733     ui->cur_x = state->width / 2;
1734     ui->cur_y = state->height / 2;
1735     ui->cur_visible = FALSE;
1736     get_random_seed(&seed, &seedsize);
1737     ui->rs = random_init(seed, seedsize);
1738     sfree(seed);
1739
1740     return ui;
1741 }
1742
1743 static void free_ui(game_ui *ui)
1744 {
1745     random_free(ui->rs);
1746     sfree(ui);
1747 }
1748
1749 /* ----------------------------------------------------------------------
1750  * Process a move.
1751  */
1752 static game_state *make_move(game_state *state, game_ui *ui,
1753                              int x, int y, int button)
1754 {
1755     game_state *ret, *nullret;
1756     int tx, ty, orig;
1757
1758     nullret = NULL;
1759
1760     if (button == LEFT_BUTTON ||
1761         button == MIDDLE_BUTTON ||
1762         button == RIGHT_BUTTON) {
1763
1764         if (ui->cur_visible) {
1765             ui->cur_visible = FALSE;
1766             nullret = state;
1767         }
1768
1769         /*
1770          * The button must have been clicked on a valid tile.
1771          */
1772         x -= WINDOW_OFFSET + TILE_BORDER;
1773         y -= WINDOW_OFFSET + TILE_BORDER;
1774         if (x < 0 || y < 0)
1775             return nullret;
1776         tx = x / TILE_SIZE;
1777         ty = y / TILE_SIZE;
1778         if (tx >= state->width || ty >= state->height)
1779             return nullret;
1780         if (x % TILE_SIZE >= TILE_SIZE - TILE_BORDER ||
1781             y % TILE_SIZE >= TILE_SIZE - TILE_BORDER)
1782             return nullret;
1783     } else if (button == CURSOR_UP || button == CURSOR_DOWN ||
1784                button == CURSOR_RIGHT || button == CURSOR_LEFT) {
1785         if (button == CURSOR_UP && ui->cur_y > 0)
1786             ui->cur_y--;
1787         else if (button == CURSOR_DOWN && ui->cur_y < state->height-1)
1788             ui->cur_y++;
1789         else if (button == CURSOR_LEFT && ui->cur_x > 0)
1790             ui->cur_x--;
1791         else if (button == CURSOR_RIGHT && ui->cur_x < state->width-1)
1792             ui->cur_x++;
1793         else
1794             return nullret;            /* no cursor movement */
1795         ui->cur_visible = TRUE;
1796         return state;                  /* UI activity has occurred */
1797     } else if (button == 'a' || button == 's' || button == 'd' ||
1798                button == 'A' || button == 'S' || button == 'D') {
1799         tx = ui->cur_x;
1800         ty = ui->cur_y;
1801         if (button == 'a' || button == 'A')
1802             button = LEFT_BUTTON;
1803         else if (button == 's' || button == 'S')
1804             button = MIDDLE_BUTTON;
1805         else if (button == 'd' || button == 'D')
1806             button = RIGHT_BUTTON;
1807         ui->cur_visible = TRUE;
1808     } else if (button == 'j' || button == 'J') {
1809         /* XXX should we have some mouse control for this? */
1810         button = 'J';   /* canonify */
1811         tx = ty = -1;   /* shut gcc up :( */
1812     } else
1813         return nullret;
1814
1815     /*
1816      * The middle button locks or unlocks a tile. (A locked tile
1817      * cannot be turned, and is visually marked as being locked.
1818      * This is a convenience for the player, so that once they are
1819      * sure which way round a tile goes, they can lock it and thus
1820      * avoid forgetting later on that they'd already done that one;
1821      * and the locking also prevents them turning the tile by
1822      * accident. If they change their mind, another middle click
1823      * unlocks it.)
1824      */
1825     if (button == MIDDLE_BUTTON) {
1826
1827         ret = dup_game(state);
1828         ret->just_used_solve = FALSE;
1829         tile(ret, tx, ty) ^= LOCKED;
1830         ret->last_rotate_dir = ret->last_rotate_x = ret->last_rotate_y = 0;
1831         return ret;
1832
1833     } else if (button == LEFT_BUTTON || button == RIGHT_BUTTON) {
1834
1835         /*
1836          * The left and right buttons have no effect if clicked on a
1837          * locked tile.
1838          */
1839         if (tile(state, tx, ty) & LOCKED)
1840             return nullret;
1841
1842         /*
1843          * Otherwise, turn the tile one way or the other. Left button
1844          * turns anticlockwise; right button turns clockwise.
1845          */
1846         ret = dup_game(state);
1847         ret->just_used_solve = FALSE;
1848         orig = tile(ret, tx, ty);
1849         if (button == LEFT_BUTTON) {
1850             tile(ret, tx, ty) = A(orig);
1851             ret->last_rotate_dir = +1;
1852         } else {
1853             tile(ret, tx, ty) = C(orig);
1854             ret->last_rotate_dir = -1;
1855         }
1856         ret->last_rotate_x = tx;
1857         ret->last_rotate_y = ty;
1858
1859     } else if (button == 'J') {
1860
1861         /*
1862          * Jumble all unlocked tiles to random orientations.
1863          */
1864         int jx, jy;
1865         ret = dup_game(state);
1866         ret->just_used_solve = FALSE;
1867         for (jy = 0; jy < ret->height; jy++) {
1868             for (jx = 0; jx < ret->width; jx++) {
1869                 if (!(tile(ret, jx, jy) & LOCKED)) {
1870                     int rot = random_upto(ui->rs, 4);
1871                     orig = tile(ret, jx, jy);
1872                     tile(ret, jx, jy) = ROT(orig, rot);
1873                 }
1874             }
1875         }
1876         ret->last_rotate_dir = 0; /* suppress animation */
1877         ret->last_rotate_x = ret->last_rotate_y = 0;
1878
1879     } else assert(0);
1880
1881     /*
1882      * Check whether the game has been completed.
1883      */
1884     {
1885         unsigned char *active = compute_active(ret);
1886         int x1, y1;
1887         int complete = TRUE;
1888
1889         for (x1 = 0; x1 < ret->width; x1++)
1890             for (y1 = 0; y1 < ret->height; y1++)
1891                 if ((tile(ret, x1, y1) & 0xF) && !index(ret, active, x1, y1)) {
1892                     complete = FALSE;
1893                     goto break_label;  /* break out of two loops at once */
1894                 }
1895         break_label:
1896
1897         sfree(active);
1898
1899         if (complete)
1900             ret->completed = TRUE;
1901     }
1902
1903     return ret;
1904 }
1905
1906 /* ----------------------------------------------------------------------
1907  * Routines for drawing the game position on the screen.
1908  */
1909
1910 struct game_drawstate {
1911     int started;
1912     int width, height;
1913     unsigned char *visible;
1914 };
1915
1916 static game_drawstate *game_new_drawstate(game_state *state)
1917 {
1918     game_drawstate *ds = snew(game_drawstate);
1919
1920     ds->started = FALSE;
1921     ds->width = state->width;
1922     ds->height = state->height;
1923     ds->visible = snewn(state->width * state->height, unsigned char);
1924     memset(ds->visible, 0xFF, state->width * state->height);
1925
1926     return ds;
1927 }
1928
1929 static void game_free_drawstate(game_drawstate *ds)
1930 {
1931     sfree(ds->visible);
1932     sfree(ds);
1933 }
1934
1935 static void game_size(game_params *params, int *x, int *y)
1936 {
1937     *x = WINDOW_OFFSET * 2 + TILE_SIZE * params->width + TILE_BORDER;
1938     *y = WINDOW_OFFSET * 2 + TILE_SIZE * params->height + TILE_BORDER;
1939 }
1940
1941 static float *game_colours(frontend *fe, game_state *state, int *ncolours)
1942 {
1943     float *ret;
1944
1945     ret = snewn(NCOLOURS * 3, float);
1946     *ncolours = NCOLOURS;
1947
1948     /*
1949      * Basic background colour is whatever the front end thinks is
1950      * a sensible default.
1951      */
1952     frontend_default_colour(fe, &ret[COL_BACKGROUND * 3]);
1953
1954     /*
1955      * Wires are black.
1956      */
1957     ret[COL_WIRE * 3 + 0] = 0.0F;
1958     ret[COL_WIRE * 3 + 1] = 0.0F;
1959     ret[COL_WIRE * 3 + 2] = 0.0F;
1960
1961     /*
1962      * Powered wires and powered endpoints are cyan.
1963      */
1964     ret[COL_POWERED * 3 + 0] = 0.0F;
1965     ret[COL_POWERED * 3 + 1] = 1.0F;
1966     ret[COL_POWERED * 3 + 2] = 1.0F;
1967
1968     /*
1969      * Barriers are red.
1970      */
1971     ret[COL_BARRIER * 3 + 0] = 1.0F;
1972     ret[COL_BARRIER * 3 + 1] = 0.0F;
1973     ret[COL_BARRIER * 3 + 2] = 0.0F;
1974
1975     /*
1976      * Unpowered endpoints are blue.
1977      */
1978     ret[COL_ENDPOINT * 3 + 0] = 0.0F;
1979     ret[COL_ENDPOINT * 3 + 1] = 0.0F;
1980     ret[COL_ENDPOINT * 3 + 2] = 1.0F;
1981
1982     /*
1983      * Tile borders are a darker grey than the background.
1984      */
1985     ret[COL_BORDER * 3 + 0] = 0.5F * ret[COL_BACKGROUND * 3 + 0];
1986     ret[COL_BORDER * 3 + 1] = 0.5F * ret[COL_BACKGROUND * 3 + 1];
1987     ret[COL_BORDER * 3 + 2] = 0.5F * ret[COL_BACKGROUND * 3 + 2];
1988
1989     /*
1990      * Locked tiles are a grey in between those two.
1991      */
1992     ret[COL_LOCKED * 3 + 0] = 0.75F * ret[COL_BACKGROUND * 3 + 0];
1993     ret[COL_LOCKED * 3 + 1] = 0.75F * ret[COL_BACKGROUND * 3 + 1];
1994     ret[COL_LOCKED * 3 + 2] = 0.75F * ret[COL_BACKGROUND * 3 + 2];
1995
1996     return ret;
1997 }
1998
1999 static void draw_thick_line(frontend *fe, int x1, int y1, int x2, int y2,
2000                             int colour)
2001 {
2002     draw_line(fe, x1-1, y1, x2-1, y2, COL_WIRE);
2003     draw_line(fe, x1+1, y1, x2+1, y2, COL_WIRE);
2004     draw_line(fe, x1, y1-1, x2, y2-1, COL_WIRE);
2005     draw_line(fe, x1, y1+1, x2, y2+1, COL_WIRE);
2006     draw_line(fe, x1, y1, x2, y2, colour);
2007 }
2008
2009 static void draw_rect_coords(frontend *fe, int x1, int y1, int x2, int y2,
2010                              int colour)
2011 {
2012     int mx = (x1 < x2 ? x1 : x2);
2013     int my = (y1 < y2 ? y1 : y2);
2014     int dx = (x2 + x1 - 2*mx + 1);
2015     int dy = (y2 + y1 - 2*my + 1);
2016
2017     draw_rect(fe, mx, my, dx, dy, colour);
2018 }
2019
2020 static void draw_barrier_corner(frontend *fe, int x, int y, int dir, int phase)
2021 {
2022     int bx = WINDOW_OFFSET + TILE_SIZE * x;
2023     int by = WINDOW_OFFSET + TILE_SIZE * y;
2024     int x1, y1, dx, dy, dir2;
2025
2026     dir >>= 4;
2027
2028     dir2 = A(dir);
2029     dx = X(dir) + X(dir2);
2030     dy = Y(dir) + Y(dir2);
2031     x1 = (dx > 0 ? TILE_SIZE+TILE_BORDER-1 : 0);
2032     y1 = (dy > 0 ? TILE_SIZE+TILE_BORDER-1 : 0);
2033
2034     if (phase == 0) {
2035         draw_rect_coords(fe, bx+x1, by+y1,
2036                          bx+x1-TILE_BORDER*dx, by+y1-(TILE_BORDER-1)*dy,
2037                          COL_WIRE);
2038         draw_rect_coords(fe, bx+x1, by+y1,
2039                          bx+x1-(TILE_BORDER-1)*dx, by+y1-TILE_BORDER*dy,
2040                          COL_WIRE);
2041     } else {
2042         draw_rect_coords(fe, bx+x1, by+y1,
2043                          bx+x1-(TILE_BORDER-1)*dx, by+y1-(TILE_BORDER-1)*dy,
2044                          COL_BARRIER);
2045     }
2046 }
2047
2048 static void draw_barrier(frontend *fe, int x, int y, int dir, int phase)
2049 {
2050     int bx = WINDOW_OFFSET + TILE_SIZE * x;
2051     int by = WINDOW_OFFSET + TILE_SIZE * y;
2052     int x1, y1, w, h;
2053
2054     x1 = (X(dir) > 0 ? TILE_SIZE : X(dir) == 0 ? TILE_BORDER : 0);
2055     y1 = (Y(dir) > 0 ? TILE_SIZE : Y(dir) == 0 ? TILE_BORDER : 0);
2056     w = (X(dir) ? TILE_BORDER : TILE_SIZE - TILE_BORDER);
2057     h = (Y(dir) ? TILE_BORDER : TILE_SIZE - TILE_BORDER);
2058
2059     if (phase == 0) {
2060         draw_rect(fe, bx+x1-X(dir), by+y1-Y(dir), w, h, COL_WIRE);
2061     } else {
2062         draw_rect(fe, bx+x1, by+y1, w, h, COL_BARRIER);
2063     }
2064 }
2065
2066 static void draw_tile(frontend *fe, game_state *state, int x, int y, int tile,
2067                       float angle, int cursor)
2068 {
2069     int bx = WINDOW_OFFSET + TILE_SIZE * x;
2070     int by = WINDOW_OFFSET + TILE_SIZE * y;
2071     float matrix[4];
2072     float cx, cy, ex, ey, tx, ty;
2073     int dir, col, phase;
2074
2075     /*
2076      * When we draw a single tile, we must draw everything up to
2077      * and including the borders around the tile. This means that
2078      * if the neighbouring tiles have connections to those borders,
2079      * we must draw those connections on the borders themselves.
2080      *
2081      * This would be terribly fiddly if we ever had to draw a tile
2082      * while its neighbour was in mid-rotate, because we'd have to
2083      * arrange to _know_ that the neighbour was being rotated and
2084      * hence had an anomalous effect on the redraw of this tile.
2085      * Fortunately, the drawing algorithm avoids ever calling us in
2086      * this circumstance: we're either drawing lots of straight
2087      * tiles at game start or after a move is complete, or we're
2088      * repeatedly drawing only the rotating tile. So no problem.
2089      */
2090
2091     /*
2092      * So. First blank the tile out completely: draw a big
2093      * rectangle in border colour, and a smaller rectangle in
2094      * background colour to fill it in.
2095      */
2096     draw_rect(fe, bx, by, TILE_SIZE+TILE_BORDER, TILE_SIZE+TILE_BORDER,
2097               COL_BORDER);
2098     draw_rect(fe, bx+TILE_BORDER, by+TILE_BORDER,
2099               TILE_SIZE-TILE_BORDER, TILE_SIZE-TILE_BORDER,
2100               tile & LOCKED ? COL_LOCKED : COL_BACKGROUND);
2101
2102     /*
2103      * Draw an inset outline rectangle as a cursor, in whichever of
2104      * COL_LOCKED and COL_BACKGROUND we aren't currently drawing
2105      * in.
2106      */
2107     if (cursor) {
2108         draw_line(fe, bx+TILE_SIZE/8, by+TILE_SIZE/8,
2109                   bx+TILE_SIZE/8, by+TILE_SIZE-TILE_SIZE/8,
2110                   tile & LOCKED ? COL_BACKGROUND : COL_LOCKED);
2111         draw_line(fe, bx+TILE_SIZE/8, by+TILE_SIZE/8,
2112                   bx+TILE_SIZE-TILE_SIZE/8, by+TILE_SIZE/8,
2113                   tile & LOCKED ? COL_BACKGROUND : COL_LOCKED);
2114         draw_line(fe, bx+TILE_SIZE-TILE_SIZE/8, by+TILE_SIZE/8,
2115                   bx+TILE_SIZE-TILE_SIZE/8, by+TILE_SIZE-TILE_SIZE/8,
2116                   tile & LOCKED ? COL_BACKGROUND : COL_LOCKED);
2117         draw_line(fe, bx+TILE_SIZE/8, by+TILE_SIZE-TILE_SIZE/8,
2118                   bx+TILE_SIZE-TILE_SIZE/8, by+TILE_SIZE-TILE_SIZE/8,
2119                   tile & LOCKED ? COL_BACKGROUND : COL_LOCKED);
2120     }
2121
2122     /*
2123      * Set up the rotation matrix.
2124      */
2125     matrix[0] = (float)cos(angle * PI / 180.0);
2126     matrix[1] = (float)-sin(angle * PI / 180.0);
2127     matrix[2] = (float)sin(angle * PI / 180.0);
2128     matrix[3] = (float)cos(angle * PI / 180.0);
2129
2130     /*
2131      * Draw the wires.
2132      */
2133     cx = cy = TILE_BORDER + (TILE_SIZE-TILE_BORDER) / 2.0F - 0.5F;
2134     col = (tile & ACTIVE ? COL_POWERED : COL_WIRE);
2135     for (dir = 1; dir < 0x10; dir <<= 1) {
2136         if (tile & dir) {
2137             ex = (TILE_SIZE - TILE_BORDER - 1.0F) / 2.0F * X(dir);
2138             ey = (TILE_SIZE - TILE_BORDER - 1.0F) / 2.0F * Y(dir);
2139             MATMUL(tx, ty, matrix, ex, ey);
2140             draw_thick_line(fe, bx+(int)cx, by+(int)cy,
2141                             bx+(int)(cx+tx), by+(int)(cy+ty),
2142                             COL_WIRE);
2143         }
2144     }
2145     for (dir = 1; dir < 0x10; dir <<= 1) {
2146         if (tile & dir) {
2147             ex = (TILE_SIZE - TILE_BORDER - 1.0F) / 2.0F * X(dir);
2148             ey = (TILE_SIZE - TILE_BORDER - 1.0F) / 2.0F * Y(dir);
2149             MATMUL(tx, ty, matrix, ex, ey);
2150             draw_line(fe, bx+(int)cx, by+(int)cy,
2151                       bx+(int)(cx+tx), by+(int)(cy+ty), col);
2152         }
2153     }
2154
2155     /*
2156      * Draw the box in the middle. We do this in blue if the tile
2157      * is an unpowered endpoint, in cyan if the tile is a powered
2158      * endpoint, in black if the tile is the centrepiece, and
2159      * otherwise not at all.
2160      */
2161     col = -1;
2162     if (x == state->cx && y == state->cy)
2163         col = COL_WIRE;
2164     else if (COUNT(tile) == 1) {
2165         col = (tile & ACTIVE ? COL_POWERED : COL_ENDPOINT);
2166     }
2167     if (col >= 0) {
2168         int i, points[8];
2169
2170         points[0] = +1; points[1] = +1;
2171         points[2] = +1; points[3] = -1;
2172         points[4] = -1; points[5] = -1;
2173         points[6] = -1; points[7] = +1;
2174
2175         for (i = 0; i < 8; i += 2) {
2176             ex = (TILE_SIZE * 0.24F) * points[i];
2177             ey = (TILE_SIZE * 0.24F) * points[i+1];
2178             MATMUL(tx, ty, matrix, ex, ey);
2179             points[i] = bx+(int)(cx+tx);
2180             points[i+1] = by+(int)(cy+ty);
2181         }
2182
2183         draw_polygon(fe, points, 4, TRUE, col);
2184         draw_polygon(fe, points, 4, FALSE, COL_WIRE);
2185     }
2186
2187     /*
2188      * Draw the points on the border if other tiles are connected
2189      * to us.
2190      */
2191     for (dir = 1; dir < 0x10; dir <<= 1) {
2192         int dx, dy, px, py, lx, ly, vx, vy, ox, oy;
2193
2194         dx = X(dir);
2195         dy = Y(dir);
2196
2197         ox = x + dx;
2198         oy = y + dy;
2199
2200         if (ox < 0 || ox >= state->width || oy < 0 || oy >= state->height)
2201             continue;
2202
2203         if (!(tile(state, ox, oy) & F(dir)))
2204             continue;
2205
2206         px = bx + (int)(dx>0 ? TILE_SIZE + TILE_BORDER - 1 : dx<0 ? 0 : cx);
2207         py = by + (int)(dy>0 ? TILE_SIZE + TILE_BORDER - 1 : dy<0 ? 0 : cy);
2208         lx = dx * (TILE_BORDER-1);
2209         ly = dy * (TILE_BORDER-1);
2210         vx = (dy ? 1 : 0);
2211         vy = (dx ? 1 : 0);
2212
2213         if (angle == 0.0 && (tile & dir)) {
2214             /*
2215              * If we are fully connected to the other tile, we must
2216              * draw right across the tile border. (We can use our
2217              * own ACTIVE state to determine what colour to do this
2218              * in: if we are fully connected to the other tile then
2219              * the two ACTIVE states will be the same.)
2220              */
2221             draw_rect_coords(fe, px-vx, py-vy, px+lx+vx, py+ly+vy, COL_WIRE);
2222             draw_rect_coords(fe, px, py, px+lx, py+ly,
2223                              (tile & ACTIVE) ? COL_POWERED : COL_WIRE);
2224         } else {
2225             /*
2226              * The other tile extends into our border, but isn't
2227              * actually connected to us. Just draw a single black
2228              * dot.
2229              */
2230             draw_rect_coords(fe, px, py, px, py, COL_WIRE);
2231         }
2232     }
2233
2234     /*
2235      * Draw barrier corners, and then barriers.
2236      */
2237     for (phase = 0; phase < 2; phase++) {
2238         for (dir = 1; dir < 0x10; dir <<= 1)
2239             if (barrier(state, x, y) & (dir << 4))
2240                 draw_barrier_corner(fe, x, y, dir << 4, phase);
2241         for (dir = 1; dir < 0x10; dir <<= 1)
2242             if (barrier(state, x, y) & dir)
2243                 draw_barrier(fe, x, y, dir, phase);
2244     }
2245
2246     draw_update(fe, bx, by, TILE_SIZE+TILE_BORDER, TILE_SIZE+TILE_BORDER);
2247 }
2248
2249 static void game_redraw(frontend *fe, game_drawstate *ds, game_state *oldstate,
2250                  game_state *state, int dir, game_ui *ui, float t, float ft)
2251 {
2252     int x, y, tx, ty, frame, last_rotate_dir;
2253     unsigned char *active;
2254     float angle = 0.0;
2255
2256     /*
2257      * Clear the screen and draw the exterior barrier lines if this
2258      * is our first call.
2259      */
2260     if (!ds->started) {
2261         int phase;
2262
2263         ds->started = TRUE;
2264
2265         draw_rect(fe, 0, 0,
2266                   WINDOW_OFFSET * 2 + TILE_SIZE * state->width + TILE_BORDER,
2267                   WINDOW_OFFSET * 2 + TILE_SIZE * state->height + TILE_BORDER,
2268                   COL_BACKGROUND);
2269         draw_update(fe, 0, 0,
2270                     WINDOW_OFFSET*2 + TILE_SIZE*state->width + TILE_BORDER,
2271                     WINDOW_OFFSET*2 + TILE_SIZE*state->height + TILE_BORDER);
2272
2273         for (phase = 0; phase < 2; phase++) {
2274
2275             for (x = 0; x < ds->width; x++) {
2276                 if (barrier(state, x, 0) & UL)
2277                     draw_barrier_corner(fe, x, -1, LD, phase);
2278                 if (barrier(state, x, 0) & RU)
2279                     draw_barrier_corner(fe, x, -1, DR, phase);
2280                 if (barrier(state, x, 0) & U)
2281                     draw_barrier(fe, x, -1, D, phase);
2282                 if (barrier(state, x, ds->height-1) & DR)
2283                     draw_barrier_corner(fe, x, ds->height, RU, phase);
2284                 if (barrier(state, x, ds->height-1) & LD)
2285                     draw_barrier_corner(fe, x, ds->height, UL, phase);
2286                 if (barrier(state, x, ds->height-1) & D)
2287                     draw_barrier(fe, x, ds->height, U, phase);
2288             }
2289
2290             for (y = 0; y < ds->height; y++) {
2291                 if (barrier(state, 0, y) & UL)
2292                     draw_barrier_corner(fe, -1, y, RU, phase);
2293                 if (barrier(state, 0, y) & LD)
2294                     draw_barrier_corner(fe, -1, y, DR, phase);
2295                 if (barrier(state, 0, y) & L)
2296                     draw_barrier(fe, -1, y, R, phase);
2297                 if (barrier(state, ds->width-1, y) & RU)
2298                     draw_barrier_corner(fe, ds->width, y, UL, phase);
2299                 if (barrier(state, ds->width-1, y) & DR)
2300                     draw_barrier_corner(fe, ds->width, y, LD, phase);
2301                 if (barrier(state, ds->width-1, y) & R)
2302                     draw_barrier(fe, ds->width, y, L, phase);
2303             }
2304         }
2305     }
2306
2307     tx = ty = -1;
2308     last_rotate_dir = dir==-1 ? oldstate->last_rotate_dir :
2309                                 state->last_rotate_dir;
2310     if (oldstate && (t < ROTATE_TIME) && last_rotate_dir) {
2311         /*
2312          * We're animating a single tile rotation. Find the turning
2313          * tile.
2314          */
2315         tx = (dir==-1 ? oldstate->last_rotate_x : state->last_rotate_x);
2316         ty = (dir==-1 ? oldstate->last_rotate_y : state->last_rotate_y);
2317         angle = last_rotate_dir * dir * 90.0F * (t / ROTATE_TIME);
2318         state = oldstate;
2319     }
2320
2321     frame = -1;
2322     if (ft > 0) {
2323         /*
2324          * We're animating a completion flash. Find which frame
2325          * we're at.
2326          */
2327         frame = (int)(ft / FLASH_FRAME);
2328     }
2329
2330     /*
2331      * Draw any tile which differs from the way it was last drawn.
2332      */
2333     active = compute_active(state);
2334
2335     for (x = 0; x < ds->width; x++)
2336         for (y = 0; y < ds->height; y++) {
2337             unsigned char c = tile(state, x, y) | index(state, active, x, y);
2338
2339             /*
2340              * In a completion flash, we adjust the LOCKED bit
2341              * depending on our distance from the centre point and
2342              * the frame number.
2343              */
2344             if (frame >= 0) {
2345                 int xdist, ydist, dist;
2346                 xdist = (x < state->cx ? state->cx - x : x - state->cx);
2347                 ydist = (y < state->cy ? state->cy - y : y - state->cy);
2348                 dist = (xdist > ydist ? xdist : ydist);
2349
2350                 if (frame >= dist && frame < dist+4) {
2351                     int lock = (frame - dist) & 1;
2352                     lock = lock ? LOCKED : 0;
2353                     c = (c &~ LOCKED) | lock;
2354                 }
2355             }
2356
2357             if (index(state, ds->visible, x, y) != c ||
2358                 index(state, ds->visible, x, y) == 0xFF ||
2359                 (x == tx && y == ty) ||
2360                 (ui->cur_visible && x == ui->cur_x && y == ui->cur_y)) {
2361                 draw_tile(fe, state, x, y, c,
2362                           (x == tx && y == ty ? angle : 0.0F),
2363                           (ui->cur_visible && x == ui->cur_x && y == ui->cur_y));
2364                 if ((x == tx && y == ty) ||
2365                     (ui->cur_visible && x == ui->cur_x && y == ui->cur_y))
2366                     index(state, ds->visible, x, y) = 0xFF;
2367                 else
2368                     index(state, ds->visible, x, y) = c;
2369             }
2370         }
2371
2372     /*
2373      * Update the status bar.
2374      */
2375     {
2376         char statusbuf[256];
2377         int i, n, n2, a;
2378
2379         n = state->width * state->height;
2380         for (i = a = n2 = 0; i < n; i++) {
2381             if (active[i])
2382                 a++;
2383             if (state->tiles[i] & 0xF)
2384                 n2++;
2385         }
2386
2387         sprintf(statusbuf, "%sActive: %d/%d",
2388                 (state->used_solve ? "Auto-solved. " :
2389                  state->completed ? "COMPLETED! " : ""), a, n2);
2390
2391         status_bar(fe, statusbuf);
2392     }
2393
2394     sfree(active);
2395 }
2396
2397 static float game_anim_length(game_state *oldstate,
2398                               game_state *newstate, int dir)
2399 {
2400     int last_rotate_dir;
2401
2402     /*
2403      * Don't animate an auto-solve move.
2404      */
2405     if ((dir > 0 && newstate->just_used_solve) ||
2406        (dir < 0 && oldstate->just_used_solve))
2407        return 0.0F;
2408
2409     /*
2410      * Don't animate if last_rotate_dir is zero.
2411      */
2412     last_rotate_dir = dir==-1 ? oldstate->last_rotate_dir :
2413                                 newstate->last_rotate_dir;
2414     if (last_rotate_dir)
2415         return ROTATE_TIME;
2416
2417     return 0.0F;
2418 }
2419
2420 static float game_flash_length(game_state *oldstate,
2421                                game_state *newstate, int dir)
2422 {
2423     /*
2424      * If the game has just been completed, we display a completion
2425      * flash.
2426      */
2427     if (!oldstate->completed && newstate->completed &&
2428         !oldstate->used_solve && !newstate->used_solve) {
2429         int size;
2430         size = 0;
2431         if (size < newstate->cx+1)
2432             size = newstate->cx+1;
2433         if (size < newstate->cy+1)
2434             size = newstate->cy+1;
2435         if (size < newstate->width - newstate->cx)
2436             size = newstate->width - newstate->cx;
2437         if (size < newstate->height - newstate->cy)
2438             size = newstate->height - newstate->cy;
2439         return FLASH_FRAME * (size+4);
2440     }
2441
2442     return 0.0F;
2443 }
2444
2445 static int game_wants_statusbar(void)
2446 {
2447     return TRUE;
2448 }
2449
2450 #ifdef COMBINED
2451 #define thegame net
2452 #endif
2453
2454 const struct game thegame = {
2455     "Net", "games.net",
2456     default_params,
2457     game_fetch_preset,
2458     decode_params,
2459     encode_params,
2460     free_params,
2461     dup_params,
2462     TRUE, game_configure, custom_params,
2463     validate_params,
2464     new_game_desc,
2465     game_free_aux_info,
2466     validate_desc,
2467     new_game,
2468     dup_game,
2469     free_game,
2470     TRUE, solve_game,
2471     FALSE, game_text_format,
2472     new_ui,
2473     free_ui,
2474     make_move,
2475     game_size,
2476     game_colours,
2477     game_new_drawstate,
2478     game_free_drawstate,
2479     game_redraw,
2480     game_anim_length,
2481     game_flash_length,
2482     game_wants_statusbar,
2483 };