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 <math.h>
  10
  11 #include "puzzles.h"
  12 #include "tree234.h"
  13
  14 #define PI 3.141592653589793238462643383279502884197169399
  15
  16 #define MATMUL(xr,yr,m,x,y) do { \
  17     float rx, ry, xx = (x), yy = (y), *mat = (m); \
  18     rx = mat[0] * xx + mat[2] * yy; \
  19     ry = mat[1] * xx + mat[3] * yy; \
  20     (xr) = rx; (yr) = ry; \
  21 } while (0)
  22
  23 /* Direction and other bitfields */
  24 #define R 0x01
  25 #define U 0x02
  26 #define L 0x04
  27 #define D 0x08
  28 #define LOCKED 0x10
  29 #define ACTIVE 0x20
  30 /* Corner flags go in the barriers array */
  31 #define RU 0x10
  32 #define UL 0x20
  33 #define LD 0x40
  34 #define DR 0x80
  35
  36 /* Rotations: Anticlockwise, Clockwise, Flip, general rotate */
  37 #define A(x) ( (((x) & 0x07) << 1) | (((x) & 0x08) >> 3) )
  38 #define C(x) ( (((x) & 0x0E) >> 1) | (((x) & 0x01) << 3) )
  39 #define F(x) ( (((x) & 0x0C) >> 2) | (((x) & 0x03) << 2) )
  40 #define ROT(x, n) ( ((n)&3) == 0 ? (x) : \
  41                     ((n)&3) == 1 ? A(x) : \
  42                     ((n)&3) == 2 ? F(x) : C(x) )
  43
  44 /* X and Y displacements */
  45 #define X(x) ( (x) == R ? +1 : (x) == L ? -1 : 0 )
  46 #define Y(x) ( (x) == D ? +1 : (x) == U ? -1 : 0 )
  47
  48 /* Bit count */
  49 #define COUNT(x) ( (((x) & 0x08) >> 3) + (((x) & 0x04) >> 2) + \
  50                    (((x) & 0x02) >> 1) + ((x) & 0x01) )
  51
  52 #define TILE_SIZE 32
  53 #define TILE_BORDER 1
  54 #define WINDOW_OFFSET 16
  55
  56 #define ROTATE_TIME 0.1
  57 #define FLASH_FRAME 0.05
  58
  59 enum {
  60     COL_BACKGROUND,
  61     COL_LOCKED,
  62     COL_BORDER,
  63     COL_WIRE,
  64     COL_ENDPOINT,
  65     COL_POWERED,
  66     COL_BARRIER,
  67     NCOLOURS
  68 };
  69
  70 struct game_params {
  71     int width;
  72     int height;
  73     int wrapping;
  74     float barrier_probability;
  75 };
  76
  77 struct game_state {
  78     int width, height, cx, cy, wrapping, completed, last_rotate_dir;
  79     unsigned char *tiles;
  80     unsigned char *barriers;
  81 };
  82
  83 #define OFFSET(x2,y2,x1,y1,dir,state) \
  84     ( (x2) = ((x1) + (state)->width + X((dir))) % (state)->width, \
  85       (y2) = ((y1) + (state)->height + Y((dir))) % (state)->height)
  86
  87 #define index(state, a, x, y) ( a[(y) * (state)->width + (x)] )
  88 #define tile(state, x, y)     index(state, (state)->tiles, x, y)
  89 #define barrier(state, x, y)  index(state, (state)->barriers, x, y)
  90
  91 struct xyd {
  92     int x, y, direction;
  93 };
  94
  95 static int xyd_cmp(void *av, void *bv) {
  96     struct xyd *a = (struct xyd *)av;
  97     struct xyd *b = (struct xyd *)bv;
  98     if (a->x < b->x)
  99         return -1;
 100     if (a->x > b->x)
 101         return +1;
 102     if (a->y < b->y)
 103         return -1;
 104     if (a->y > b->y)
 105         return +1;
 106     if (a->direction < b->direction)
 107         return -1;
 108     if (a->direction > b->direction)
 109         return +1;
 110     return 0;
 111 };
 112
 113 static struct xyd *new_xyd(int x, int y, int direction)
 114 {
 115     struct xyd *xyd = snew(struct xyd);
 116     xyd->x = x;
 117     xyd->y = y;
 118     xyd->direction = direction;
 119     return xyd;
 120 }
 121
 122 /* ----------------------------------------------------------------------
 123  * Manage game parameters.
 124  */
 125 game_params *default_params(void)
 126 {
 127     game_params *ret = snew(game_params);
 128
 129     ret->width = 11;
 130     ret->height = 11;
 131     ret->wrapping = TRUE;
 132     ret->barrier_probability = 0.1;
 133
 134     return ret;
 135 }
 136
 137 void free_params(game_params *params)
 138 {
 139     sfree(params);
 140 }
 141
 142 /* ----------------------------------------------------------------------
 143  * Randomly select a new game seed.
 144  */
 145
 146 char *new_game_seed(game_params *params)
 147 {
 148     /*
 149      * The full description of a Net game is far too large to
 150      * encode directly in the seed, so by default we'll have to go
 151      * for the simple approach of providing a random-number seed.
 152      *
 153      * (This does not restrict me from _later on_ inventing a seed
 154      * string syntax which can never be generated by this code -
 155      * for example, strings beginning with a letter - allowing me
 156      * to type in a precise game, and have new_game detect it and
 157      * understand it and do something completely different.)
 158      */
 159     char buf[40];
 160     sprintf(buf, "%d", rand());
 161     return dupstr(buf);
 162 }
 163
 164 /* ----------------------------------------------------------------------
 165  * Construct an initial game state, given a seed and parameters.
 166  */
 167
 168 game_state *new_game(game_params *params, char *seed)
 169 {
 170     random_state *rs;
 171     game_state *state;
 172     tree234 *possibilities, *barriers;
 173     int w, h, x, y, nbarriers;
 174
 175     assert(params->width > 2);
 176     assert(params->height > 2);
 177
 178     /*
 179      * Create a blank game state.
 180      */
 181     state = snew(game_state);
 182     w = state->width = params->width;
 183     h = state->height = params->height;
 184     state->cx = state->width / 2;
 185     state->cy = state->height / 2;
 186     state->wrapping = params->wrapping;
 187     state->last_rotate_dir = +1;       /* *shrug* */
 188     state->completed = FALSE;
 189     state->tiles = snewn(state->width * state->height, unsigned char);
 190     memset(state->tiles, 0, state->width * state->height);
 191     state->barriers = snewn(state->width * state->height, unsigned char);
 192     memset(state->barriers, 0, state->width * state->height);
 193
 194     /*
 195      * Set up border barriers if this is a non-wrapping game.
 196      */
 197     if (!state->wrapping) {
 198         for (x = 0; x < state->width; x++) {
 199             barrier(state, x, 0) |= U;
 200             barrier(state, x, state->height-1) |= D;
 201         }
 202         for (y = 0; y < state->height; y++) {
 203             barrier(state, 0, y) |= L;
 204             barrier(state, state->width-1, y) |= R;
 205         }
 206     }
 207
 208     /*
 209      * Seed the internal random number generator.
 210      */
 211     rs = random_init(seed, strlen(seed));
 212
 213     /*
 214      * Construct the unshuffled grid.
 215      *
 216      * To do this, we simply start at the centre point, repeatedly
 217      * choose a random possibility out of the available ways to
 218      * extend a used square into an unused one, and do it. After
 219      * extending the third line out of a square, we remove the
 220      * fourth from the possibilities list to avoid any full-cross
 221      * squares (which would make the game too easy because they
 222      * only have one orientation).
 223      *
 224      * The slightly worrying thing is the avoidance of full-cross
 225      * squares. Can this cause our unsophisticated construction
 226      * algorithm to paint itself into a corner, by getting into a
 227      * situation where there are some unreached squares and the
 228      * only way to reach any of them is to extend a T-piece into a
 229      * full cross?
 230      *
 231      * Answer: no it can't, and here's a proof.
 232      *
 233      * Any contiguous group of such unreachable squares must be
 234      * surrounded on _all_ sides by T-pieces pointing away from the
 235      * group. (If not, then there is a square which can be extended
 236      * into one of the `unreachable' ones, and so it wasn't
 237      * unreachable after all.) In particular, this implies that
 238      * each contiguous group of unreachable squares must be
 239      * rectangular in shape (any deviation from that yields a
 240      * non-T-piece next to an `unreachable' square).
 241      *
 242      * So we have a rectangle of unreachable squares, with T-pieces
 243      * forming a solid border around the rectangle. The corners of
 244      * that border must be connected (since every tile connects all
 245      * the lines arriving in it), and therefore the border must
 246      * form a closed loop around the rectangle.
 247      *
 248      * But this can't have happened in the first place, since we
 249      * _know_ we've avoided creating closed loops! Hence, no such
 250      * situation can ever arise, and the naive grid construction
 251      * algorithm will guaranteeably result in a complete grid
 252      * containing no unreached squares, no full crosses _and_ no
 253      * closed loops. []
 254      */
 255     possibilities = newtree234(xyd_cmp);
 256
 257     add234(possibilities, new_xyd(state->cx, state->cy, R));
 258     add234(possibilities, new_xyd(state->cx, state->cy, U));
 259     add234(possibilities, new_xyd(state->cx, state->cy, L));
 260     add234(possibilities, new_xyd(state->cx, state->cy, D));
 261
 262     while (count234(possibilities) > 0) {
 263         int i;
 264         struct xyd *xyd;
 265         int x1, y1, d1, x2, y2, d2, d;
 266
 267         /*
 268          * Extract a randomly chosen possibility from the list.
 269          */
 270         i = random_upto(rs, count234(possibilities));
 271         xyd = delpos234(possibilities, i);
 272         x1 = xyd->x;
 273         y1 = xyd->y;
 274         d1 = xyd->direction;
 275         sfree(xyd);
 276
 277         OFFSET(x2, y2, x1, y1, d1, state);
 278         d2 = F(d1);
 279 #ifdef DEBUG
 280         printf("picked (%d,%d,%c) <-> (%d,%d,%c)\n",
 281                x1, y1, "0RU3L567D9abcdef"[d1], x2, y2, "0RU3L567D9abcdef"[d2]);
 282 #endif
 283
 284         /*
 285          * Make the connection. (We should be moving to an as yet
 286          * unused tile.)
 287          */
 288         tile(state, x1, y1) |= d1;
 289         assert(tile(state, x2, y2) == 0);
 290         tile(state, x2, y2) |= d2;
 291
 292         /*
 293          * If we have created a T-piece, remove its last
 294          * possibility.
 295          */
 296         if (COUNT(tile(state, x1, y1)) == 3) {
 297             struct xyd xyd1, *xydp;
 298
 299             xyd1.x = x1;
 300             xyd1.y = y1;
 301             xyd1.direction = 0x0F ^ tile(state, x1, y1);
 302
 303             xydp = find234(possibilities, &xyd1, NULL);
 304
 305             if (xydp) {
 306 #ifdef DEBUG
 307                 printf("T-piece; removing (%d,%d,%c)\n",
 308                        xydp->x, xydp->y, "0RU3L567D9abcdef"[xydp->direction]);
 309 #endif
 310                 del234(possibilities, xydp);
 311                 sfree(xydp);
 312             }
 313         }
 314
 315         /*
 316          * Remove all other possibilities that were pointing at the
 317          * tile we've just moved into.
 318          */
 319         for (d = 1; d < 0x10; d <<= 1) {
 320             int x3, y3, d3;
 321             struct xyd xyd1, *xydp;
 322
 323             OFFSET(x3, y3, x2, y2, d, state);
 324             d3 = F(d);
 325
 326             xyd1.x = x3;
 327             xyd1.y = y3;
 328             xyd1.direction = d3;
 329
 330             xydp = find234(possibilities, &xyd1, NULL);
 331
 332             if (xydp) {
 333 #ifdef DEBUG
 334                 printf("Loop avoidance; removing (%d,%d,%c)\n",
 335                        xydp->x, xydp->y, "0RU3L567D9abcdef"[xydp->direction]);
 336 #endif
 337                 del234(possibilities, xydp);
 338                 sfree(xydp);
 339             }
 340         }
 341
 342         /*
 343          * Add new possibilities to the list for moving _out_ of
 344          * the tile we have just moved into.
 345          */
 346         for (d = 1; d < 0x10; d <<= 1) {
 347             int x3, y3;
 348
 349             if (d == d2)
 350                 continue;              /* we've got this one already */
 351
 352             if (!state->wrapping) {
 353                 if (d == U && y2 == 0)
 354                     continue;
 355                 if (d == D && y2 == state->height-1)
 356                     continue;
 357                 if (d == L && x2 == 0)
 358                     continue;
 359                 if (d == R && x2 == state->width-1)
 360                     continue;
 361             }
 362
 363             OFFSET(x3, y3, x2, y2, d, state);
 364
 365             if (tile(state, x3, y3))
 366                 continue;              /* this would create a loop */
 367
 368 #ifdef DEBUG
 369             printf("New frontier; adding (%d,%d,%c)\n",
 370                    x2, y2, "0RU3L567D9abcdef"[d]);
 371 #endif
 372             add234(possibilities, new_xyd(x2, y2, d));
 373         }
 374     }
 375     /* Having done that, we should have no possibilities remaining. */
 376     assert(count234(possibilities) == 0);
 377     freetree234(possibilities);
 378
 379     /*
 380      * Now compute a list of the possible barrier locations.
 381      */
 382     barriers = newtree234(xyd_cmp);
 383     for (y = 0; y < state->height; y++) {
 384         for (x = 0; x < state->width; x++) {
 385
 386             if (!(tile(state, x, y) & R) &&
 387                 (state->wrapping || x < state->width-1))
 388                 add234(barriers, new_xyd(x, y, R));
 389             if (!(tile(state, x, y) & D) &&
 390                 (state->wrapping || y < state->height-1))
 391                 add234(barriers, new_xyd(x, y, D));
 392         }
 393     }
 394
 395     /*
 396      * Now shuffle the grid.
 397      */
 398     for (y = 0; y < state->height; y++) {
 399         for (x = 0; x < state->width; x++) {
 400             int orig = tile(state, x, y);
 401             int rot = random_upto(rs, 4);
 402             tile(state, x, y) = ROT(orig, rot);
 403         }
 404     }
 405
 406     /*
 407      * And now choose barrier locations. (We carefully do this
 408      * _after_ shuffling, so that changing the barrier rate in the
 409      * params while keeping the game seed the same will give the
 410      * same shuffled grid and _only_ change the barrier locations.
 411      * Also the way we choose barrier locations, by repeatedly
 412      * choosing one possibility from the list until we have enough,
 413      * is designed to ensure that raising the barrier rate while
 414      * keeping the seed the same will provide a superset of the
 415      * previous barrier set - i.e. if you ask for 10 barriers, and
 416      * then decide that's still too hard and ask for 20, you'll get
 417      * the original 10 plus 10 more, rather than getting 20 new
 418      * ones and the chance of remembering your first 10.)
 419      */
 420     nbarriers = params->barrier_probability * count234(barriers);
 421     assert(nbarriers >= 0 && nbarriers <= count234(barriers));
 422
 423     while (nbarriers > 0) {
 424         int i;
 425         struct xyd *xyd;
 426         int x1, y1, d1, x2, y2, d2;
 427
 428         /*
 429          * Extract a randomly chosen barrier from the list.
 430          */
 431         i = random_upto(rs, count234(barriers));
 432         xyd = delpos234(barriers, i);
 433
 434         assert(xyd != NULL);
 435
 436         x1 = xyd->x;
 437         y1 = xyd->y;
 438         d1 = xyd->direction;
 439         sfree(xyd);
 440
 441         OFFSET(x2, y2, x1, y1, d1, state);
 442         d2 = F(d1);
 443
 444         barrier(state, x1, y1) |= d1;
 445         barrier(state, x2, y2) |= d2;
 446
 447         nbarriers--;
 448     }
 449
 450     /*
 451      * Clean up the rest of the barrier list.
 452      */
 453     {
 454         struct xyd *xyd;
 455
 456         while ( (xyd = delpos234(barriers, 0)) != NULL)
 457             sfree(xyd);
 458
 459         freetree234(barriers);
 460     }
 461
 462     /*
 463      * Set up the barrier corner flags, for drawing barriers
 464      * prettily when they meet.
 465      */
 466     for (y = 0; y < state->height; y++) {
 467         for (x = 0; x < state->width; x++) {
 468             int dir;
 469
 470             for (dir = 1; dir < 0x10; dir <<= 1) {
 471                 int dir2 = A(dir);
 472                 int x1, y1, x2, y2, x3, y3;
 473                 int corner = FALSE;
 474
 475                 if (!(barrier(state, x, y) & dir))
 476                     continue;
 477
 478                 if (barrier(state, x, y) & dir2)
 479                     corner = TRUE;
 480
 481                 x1 = x + X(dir), y1 = y + Y(dir);
 482                 if (x1 >= 0 && x1 < state->width &&
 483                     y1 >= 0 && y1 < state->width &&
 484                     (barrier(state, x1, y1) & dir2))
 485                     corner = TRUE;
 486
 487                 x2 = x + X(dir2), y2 = y + Y(dir2);
 488                 if (x2 >= 0 && x2 < state->width &&
 489                     y2 >= 0 && y2 < state->width &&
 490                     (barrier(state, x2, y2) & dir))
 491                     corner = TRUE;
 492
 493                 if (corner) {
 494                     barrier(state, x, y) |= (dir << 4);
 495                     if (x1 >= 0 && x1 < state->width &&
 496                         y1 >= 0 && y1 < state->width)
 497                         barrier(state, x1, y1) |= (A(dir) << 4);
 498                     if (x2 >= 0 && x2 < state->width &&
 499                         y2 >= 0 && y2 < state->width)
 500                         barrier(state, x2, y2) |= (C(dir) << 4);
 501                     x3 = x + X(dir) + X(dir2), y3 = y + Y(dir) + Y(dir2);
 502                     if (x3 >= 0 && x3 < state->width &&
 503                         y3 >= 0 && y3 < state->width)
 504                         barrier(state, x3, y3) |= (F(dir) << 4);
 505                 }
 506             }
 507         }
 508     }
 509
 510     random_free(rs);
 511
 512     return state;
 513 }
 514
 515 game_state *dup_game(game_state *state)
 516 {
 517     game_state *ret;
 518
 519     ret = snew(game_state);
 520     ret->width = state->width;
 521     ret->height = state->height;
 522     ret->cx = state->cx;
 523     ret->cy = state->cy;
 524     ret->wrapping = state->wrapping;
 525     ret->completed = state->completed;
 526     ret->last_rotate_dir = state->last_rotate_dir;
 527     ret->tiles = snewn(state->width * state->height, unsigned char);
 528     memcpy(ret->tiles, state->tiles, state->width * state->height);
 529     ret->barriers = snewn(state->width * state->height, unsigned char);
 530     memcpy(ret->barriers, state->barriers, state->width * state->height);
 531
 532     return ret;
 533 }
 534
 535 void free_game(game_state *state)
 536 {
 537     sfree(state->tiles);
 538     sfree(state->barriers);
 539     sfree(state);
 540 }
 541
 542 /* ----------------------------------------------------------------------
 543  * Utility routine.
 544  */
 545
 546 /*
 547  * Compute which squares are reachable from the centre square, as a
 548  * quick visual aid to determining how close the game is to
 549  * completion. This is also a simple way to tell if the game _is_
 550  * completed - just call this function and see whether every square
 551  * is marked active.
 552  */
 553 static unsigned char *compute_active(game_state *state)
 554 {
 555     unsigned char *active;
 556     tree234 *todo;
 557     struct xyd *xyd;
 558
 559     active = snewn(state->width * state->height, unsigned char);
 560     memset(active, 0, state->width * state->height);
 561
 562     /*
 563      * We only store (x,y) pairs in todo, but it's easier to reuse
 564      * xyd_cmp and just store direction 0 every time.
 565      */
 566     todo = newtree234(xyd_cmp);
 567     index(state, active, state->cx, state->cy) = ACTIVE;
 568     add234(todo, new_xyd(state->cx, state->cy, 0));
 569
 570     while ( (xyd = delpos234(todo, 0)) != NULL) {
 571         int x1, y1, d1, x2, y2, d2;
 572
 573         x1 = xyd->x;
 574         y1 = xyd->y;
 575         sfree(xyd);
 576
 577         for (d1 = 1; d1 < 0x10; d1 <<= 1) {
 578             OFFSET(x2, y2, x1, y1, d1, state);
 579             d2 = F(d1);
 580
 581             /*
 582              * If the next tile in this direction is connected to
 583              * us, and there isn't a barrier in the way, and it
 584              * isn't already marked active, then mark it active and
 585              * add it to the to-examine list.
 586              */
 587             if ((tile(state, x1, y1) & d1) &&
 588                 (tile(state, x2, y2) & d2) &&
 589                 !(barrier(state, x1, y1) & d1) &&
 590                 !index(state, active, x2, y2)) {
 591                 index(state, active, x2, y2) = ACTIVE;
 592                 add234(todo, new_xyd(x2, y2, 0));
 593             }
 594         }
 595     }
 596     /* Now we expect the todo list to have shrunk to zero size. */
 597     assert(count234(todo) == 0);
 598     freetree234(todo);
 599
 600     return active;
 601 }
 602
 603 /* ----------------------------------------------------------------------
 604  * Process a move.
 605  */
 606 game_state *make_move(game_state *state, int x, int y, int button)
 607 {
 608     game_state *ret;
 609     int tx, ty, orig;
 610
 611     /*
 612      * All moves in Net are made with the mouse.
 613      */
 614     if (button != LEFT_BUTTON &&
 615         button != MIDDLE_BUTTON &&
 616         button != RIGHT_BUTTON)
 617         return NULL;
 618
 619     /*
 620      * The button must have been clicked on a valid tile.
 621      */
 622     x -= WINDOW_OFFSET + TILE_BORDER;
 623     y -= WINDOW_OFFSET + TILE_BORDER;
 624     if (x < 0 || y < 0)
 625         return NULL;
 626     tx = x / TILE_SIZE;
 627     ty = y / TILE_SIZE;
 628     if (tx >= state->width || ty >= state->height)
 629         return NULL;
 630     if (tx % TILE_SIZE >= TILE_SIZE - TILE_BORDER ||
 631         ty % TILE_SIZE >= TILE_SIZE - TILE_BORDER)
 632         return NULL;
 633
 634     /*
 635      * The middle button locks or unlocks a tile. (A locked tile
 636      * cannot be turned, and is visually marked as being locked.
 637      * This is a convenience for the player, so that once they are
 638      * sure which way round a tile goes, they can lock it and thus
 639      * avoid forgetting later on that they'd already done that one;
 640      * and the locking also prevents them turning the tile by
 641      * accident. If they change their mind, another middle click
 642      * unlocks it.)
 643      */
 644     if (button == MIDDLE_BUTTON) {
 645         ret = dup_game(state);
 646         tile(ret, tx, ty) ^= LOCKED;
 647         return ret;
 648     }
 649
 650     /*
 651      * The left and right buttons have no effect if clicked on a
 652      * locked tile.
 653      */
 654     if (tile(state, tx, ty) & LOCKED)
 655         return NULL;
 656
 657     /*
 658      * Otherwise, turn the tile one way or the other. Left button
 659      * turns anticlockwise; right button turns clockwise.
 660      */
 661     ret = dup_game(state);
 662     orig = tile(ret, tx, ty);
 663     if (button == LEFT_BUTTON) {
 664         tile(ret, tx, ty) = A(orig);
 665         ret->last_rotate_dir = +1;
 666     } else {
 667         tile(ret, tx, ty) = C(orig);
 668         ret->last_rotate_dir = -1;
 669     }
 670
 671     /*
 672      * Check whether the game has been completed.
 673      */
 674     {
 675         unsigned char *active = compute_active(ret);
 676         int x1, y1;
 677         int complete = TRUE;
 678
 679         for (x1 = 0; x1 < ret->width; x1++)
 680             for (y1 = 0; y1 < ret->height; y1++)
 681                 if (!index(ret, active, x1, y1)) {
 682                     complete = FALSE;
 683                     goto break_label;  /* break out of two loops at once */
 684                 }
 685         break_label:
 686
 687         sfree(active);
 688
 689         if (complete)
 690             ret->completed = TRUE;
 691     }
 692
 693     return ret;
 694 }
 695
 696 /* ----------------------------------------------------------------------
 697  * Routines for drawing the game position on the screen.
 698  */
 699
 700 struct game_drawstate {
 701     int started;
 702     int width, height;
 703     unsigned char *visible;
 704 };
 705
 706 game_drawstate *game_new_drawstate(game_state *state)
 707 {
 708     game_drawstate *ds = snew(game_drawstate);
 709
 710     ds->started = FALSE;
 711     ds->width = state->width;
 712     ds->height = state->height;
 713     ds->visible = snewn(state->width * state->height, unsigned char);
 714     memset(ds->visible, 0xFF, state->width * state->height);
 715
 716     return ds;
 717 }
 718
 719 void game_free_drawstate(game_drawstate *ds)
 720 {
 721     sfree(ds->visible);
 722     sfree(ds);
 723 }
 724
 725 void game_size(game_params *params, int *x, int *y)
 726 {
 727     *x = WINDOW_OFFSET * 2 + TILE_SIZE * params->width + TILE_BORDER;
 728     *y = WINDOW_OFFSET * 2 + TILE_SIZE * params->height + TILE_BORDER;
 729 }
 730
 731 float *game_colours(frontend *fe, game_state *state, int *ncolours)
 732 {
 733     float *ret;
 734
 735     ret = snewn(NCOLOURS * 3, float);
 736     *ncolours = NCOLOURS;
 737
 738     /*
 739      * Basic background colour is whatever the front end thinks is
 740      * a sensible default.
 741      */
 742     frontend_default_colour(fe, &ret[COL_BACKGROUND * 3]);
 743
 744     /*
 745      * Wires are black.
 746      */
 747     ret[COL_WIRE * 3 + 0] = 0.0;
 748     ret[COL_WIRE * 3 + 1] = 0.0;
 749     ret[COL_WIRE * 3 + 2] = 0.0;
 750
 751     /*
 752      * Powered wires and powered endpoints are cyan.
 753      */
 754     ret[COL_POWERED * 3 + 0] = 0.0;
 755     ret[COL_POWERED * 3 + 1] = 1.0;
 756     ret[COL_POWERED * 3 + 2] = 1.0;
 757
 758     /*
 759      * Barriers are red.
 760      */
 761     ret[COL_BARRIER * 3 + 0] = 1.0;
 762     ret[COL_BARRIER * 3 + 1] = 0.0;
 763     ret[COL_BARRIER * 3 + 2] = 0.0;
 764
 765     /*
 766      * Unpowered endpoints are blue.
 767      */
 768     ret[COL_ENDPOINT * 3 + 0] = 0.0;
 769     ret[COL_ENDPOINT * 3 + 1] = 0.0;
 770     ret[COL_ENDPOINT * 3 + 2] = 1.0;
 771
 772     /*
 773      * Tile borders are a darker grey than the background.
 774      */
 775     ret[COL_BORDER * 3 + 0] = 0.5 * ret[COL_BACKGROUND * 3 + 0];
 776     ret[COL_BORDER * 3 + 1] = 0.5 * ret[COL_BACKGROUND * 3 + 1];
 777     ret[COL_BORDER * 3 + 2] = 0.5 * ret[COL_BACKGROUND * 3 + 2];
 778
 779     /*
 780      * Locked tiles are a grey in between those two.
 781      */
 782     ret[COL_LOCKED * 3 + 0] = 0.75 * ret[COL_BACKGROUND * 3 + 0];
 783     ret[COL_LOCKED * 3 + 1] = 0.75 * ret[COL_BACKGROUND * 3 + 1];
 784     ret[COL_LOCKED * 3 + 2] = 0.75 * ret[COL_BACKGROUND * 3 + 2];
 785
 786     return ret;
 787 }
 788
 789 static void draw_thick_line(frontend *fe, int x1, int y1, int x2, int y2,
 790                             int colour)
 791 {
 792     draw_line(fe, x1-1, y1, x2-1, y2, COL_WIRE);
 793     draw_line(fe, x1+1, y1, x2+1, y2, COL_WIRE);
 794     draw_line(fe, x1, y1-1, x2, y2-1, COL_WIRE);
 795     draw_line(fe, x1, y1+1, x2, y2+1, COL_WIRE);
 796     draw_line(fe, x1, y1, x2, y2, colour);
 797 }
 798
 799 static void draw_rect_coords(frontend *fe, int x1, int y1, int x2, int y2,
 800                              int colour)
 801 {
 802     int mx = (x1 < x2 ? x1 : x2);
 803     int my = (y1 < y2 ? y1 : y2);
 804     int dx = (x2 + x1 - 2*mx + 1);
 805     int dy = (y2 + y1 - 2*my + 1);
 806
 807     draw_rect(fe, mx, my, dx, dy, colour);
 808 }
 809
 810 static void draw_barrier_corner(frontend *fe, int x, int y, int dir, int phase)
 811 {
 812     int bx = WINDOW_OFFSET + TILE_SIZE * x;
 813     int by = WINDOW_OFFSET + TILE_SIZE * y;
 814     int x1, y1, dx, dy, dir2;
 815
 816     dir >>= 4;
 817
 818     dir2 = A(dir);
 819     dx = X(dir) + X(dir2);
 820     dy = Y(dir) + Y(dir2);
 821     x1 = (dx > 0 ? TILE_SIZE+TILE_BORDER-1 : 0);
 822     y1 = (dy > 0 ? TILE_SIZE+TILE_BORDER-1 : 0);
 823
 824     if (phase == 0) {
 825         draw_rect_coords(fe, bx+x1, by+y1,
 826                          bx+x1-TILE_BORDER*dx, by+y1-(TILE_BORDER-1)*dy,
 827                          COL_WIRE);
 828         draw_rect_coords(fe, bx+x1, by+y1,
 829                          bx+x1-(TILE_BORDER-1)*dx, by+y1-TILE_BORDER*dy,
 830                          COL_WIRE);
 831     } else {
 832         draw_rect_coords(fe, bx+x1, by+y1,
 833                          bx+x1-(TILE_BORDER-1)*dx, by+y1-(TILE_BORDER-1)*dy,
 834                          COL_BARRIER);
 835     }
 836 }
 837
 838 static void draw_barrier(frontend *fe, int x, int y, int dir, int phase)
 839 {
 840     int bx = WINDOW_OFFSET + TILE_SIZE * x;
 841     int by = WINDOW_OFFSET + TILE_SIZE * y;
 842     int x1, y1, w, h;
 843
 844     x1 = (X(dir) > 0 ? TILE_SIZE : X(dir) == 0 ? TILE_BORDER : 0);
 845     y1 = (Y(dir) > 0 ? TILE_SIZE : Y(dir) == 0 ? TILE_BORDER : 0);
 846     w = (X(dir) ? TILE_BORDER : TILE_SIZE - TILE_BORDER);
 847     h = (Y(dir) ? TILE_BORDER : TILE_SIZE - TILE_BORDER);
 848
 849     if (phase == 0) {
 850         draw_rect(fe, bx+x1-X(dir), by+y1-Y(dir), w, h, COL_WIRE);
 851     } else {
 852         draw_rect(fe, bx+x1, by+y1, w, h, COL_BARRIER);
 853     }
 854 }
 855
 856 static void draw_tile(frontend *fe, game_state *state, int x, int y, int tile,
 857                       float angle)
 858 {
 859     int bx = WINDOW_OFFSET + TILE_SIZE * x;
 860     int by = WINDOW_OFFSET + TILE_SIZE * y;
 861     float matrix[4];
 862     float cx, cy, ex, ey, tx, ty;
 863     int dir, col, phase;
 864
 865     /*
 866      * When we draw a single tile, we must draw everything up to
 867      * and including the borders around the tile. This means that
 868      * if the neighbouring tiles have connections to those borders,
 869      * we must draw those connections on the borders themselves.
 870      *
 871      * This would be terribly fiddly if we ever had to draw a tile
 872      * while its neighbour was in mid-rotate, because we'd have to
 873      * arrange to _know_ that the neighbour was being rotated and
 874      * hence had an anomalous effect on the redraw of this tile.
 875      * Fortunately, the drawing algorithm avoids ever calling us in
 876      * this circumstance: we're either drawing lots of straight
 877      * tiles at game start or after a move is complete, or we're
 878      * repeatedly drawing only the rotating tile. So no problem.
 879      */
 880
 881     /*
 882      * So. First blank the tile out completely: draw a big
 883      * rectangle in border colour, and a smaller rectangle in
 884      * background colour to fill it in.
 885      */
 886     draw_rect(fe, bx, by, TILE_SIZE+TILE_BORDER, TILE_SIZE+TILE_BORDER,
 887               COL_BORDER);
 888     draw_rect(fe, bx+TILE_BORDER, by+TILE_BORDER,
 889               TILE_SIZE-TILE_BORDER, TILE_SIZE-TILE_BORDER,
 890               tile & LOCKED ? COL_LOCKED : COL_BACKGROUND);
 891
 892     /*
 893      * Set up the rotation matrix.
 894      */
 895     matrix[0] = cos(angle * PI / 180.0);
 896     matrix[1] = -sin(angle * PI / 180.0);
 897     matrix[2] = sin(angle * PI / 180.0);
 898     matrix[3] = cos(angle * PI / 180.0);
 899
 900     /*
 901      * Draw the wires.
 902      */
 903     cx = cy = TILE_BORDER + (TILE_SIZE-TILE_BORDER) / 2.0 - 0.5;
 904     col = (tile & ACTIVE ? COL_POWERED : COL_WIRE);
 905     for (dir = 1; dir < 0x10; dir <<= 1) {
 906         if (tile & dir) {
 907             ex = (TILE_SIZE - TILE_BORDER - 1.0) / 2.0 * X(dir);
 908             ey = (TILE_SIZE - TILE_BORDER - 1.0) / 2.0 * Y(dir);
 909             MATMUL(tx, ty, matrix, ex, ey);
 910             draw_thick_line(fe, bx+cx, by+cy, bx+(cx+tx), by+(cy+ty),
 911                             COL_WIRE);
 912         }
 913     }
 914     for (dir = 1; dir < 0x10; dir <<= 1) {
 915         if (tile & dir) {
 916             ex = (TILE_SIZE - TILE_BORDER - 1.0) / 2.0 * X(dir);
 917             ey = (TILE_SIZE - TILE_BORDER - 1.0) / 2.0 * Y(dir);
 918             MATMUL(tx, ty, matrix, ex, ey);
 919             draw_line(fe, bx+cx, by+cy, bx+(cx+tx), by+(cy+ty), col);
 920         }
 921     }
 922
 923     /*
 924      * Draw the box in the middle. We do this in blue if the tile
 925      * is an unpowered endpoint, in cyan if the tile is a powered
 926      * endpoint, in black if the tile is the centrepiece, and
 927      * otherwise not at all.
 928      */
 929     col = -1;
 930     if (x == state->cx && y == state->cy)
 931         col = COL_WIRE;
 932     else if (COUNT(tile) == 1) {
 933         col = (tile & ACTIVE ? COL_POWERED : COL_ENDPOINT);
 934     }
 935     if (col >= 0) {
 936         int i, points[8];
 937
 938         points[0] = +1; points[1] = +1;
 939         points[2] = +1; points[3] = -1;
 940         points[4] = -1; points[5] = -1;
 941         points[6] = -1; points[7] = +1;
 942
 943         for (i = 0; i < 8; i += 2) {
 944             ex = (TILE_SIZE * 0.24) * points[i];
 945             ey = (TILE_SIZE * 0.24) * points[i+1];
 946             MATMUL(tx, ty, matrix, ex, ey);
 947             points[i] = bx+cx+tx;
 948             points[i+1] = by+cy+ty;
 949         }
 950
 951         draw_polygon(fe, points, 4, TRUE, col);
 952         draw_polygon(fe, points, 4, FALSE, COL_WIRE);
 953     }
 954
 955     /*
 956      * Draw the points on the border if other tiles are connected
 957      * to us.
 958      */
 959     for (dir = 1; dir < 0x10; dir <<= 1) {
 960         int dx, dy, px, py, lx, ly, vx, vy, ox, oy;
 961
 962         dx = X(dir);
 963         dy = Y(dir);
 964
 965         ox = x + dx;
 966         oy = y + dy;
 967
 968         if (ox < 0 || ox >= state->width || oy < 0 || oy >= state->height)
 969             continue;
 970
 971         if (!(tile(state, ox, oy) & F(dir)))
 972             continue;
 973
 974         px = bx + (dx>0 ? TILE_SIZE + TILE_BORDER - 1 : dx<0 ? 0 : cx);
 975         py = by + (dy>0 ? TILE_SIZE + TILE_BORDER - 1 : dy<0 ? 0 : cy);
 976         lx = dx * (TILE_BORDER-1);
 977         ly = dy * (TILE_BORDER-1);
 978         vx = (dy ? 1 : 0);
 979         vy = (dx ? 1 : 0);
 980
 981         if (angle == 0.0 && (tile & dir)) {
 982             /*
 983              * If we are fully connected to the other tile, we must
 984              * draw right across the tile border. (We can use our
 985              * own ACTIVE state to determine what colour to do this
 986              * in: if we are fully connected to the other tile then
 987              * the two ACTIVE states will be the same.)
 988              */
 989             draw_rect_coords(fe, px-vx, py-vy, px+lx+vx, py+ly+vy, COL_WIRE);
 990             draw_rect_coords(fe, px, py, px+lx, py+ly,
 991                              (tile & ACTIVE) ? COL_POWERED : COL_WIRE);
 992         } else {
 993             /*
 994              * The other tile extends into our border, but isn't
 995              * actually connected to us. Just draw a single black
 996              * dot.
 997              */
 998             draw_rect_coords(fe, px, py, px, py, COL_WIRE);
 999         }
1000     }
1001
1002     /*
1003      * Draw barrier corners, and then barriers.
1004      */
1005     for (phase = 0; phase < 2; phase++) {
1006         for (dir = 1; dir < 0x10; dir <<= 1)
1007             if (barrier(state, x, y) & (dir << 4))
1008                 draw_barrier_corner(fe, x, y, dir << 4, phase);
1009         for (dir = 1; dir < 0x10; dir <<= 1)
1010             if (barrier(state, x, y) & dir)
1011                 draw_barrier(fe, x, y, dir, phase);
1012     }
1013
1014     draw_update(fe, bx, by, TILE_SIZE+TILE_BORDER, TILE_SIZE+TILE_BORDER);
1015 }
1016
1017 void game_redraw(frontend *fe, game_drawstate *ds, game_state *oldstate,
1018                  game_state *state, float t)
1019 {
1020     int x, y, tx, ty, frame;
1021     unsigned char *active;
1022     float angle = 0.0;
1023
1024     /*
1025      * Clear the screen and draw the exterior barrier lines if this
1026      * is our first call.
1027      */
1028     if (!ds->started) {
1029         int phase;
1030
1031         ds->started = TRUE;
1032
1033         draw_rect(fe, 0, 0,
1034                   WINDOW_OFFSET * 2 + TILE_SIZE * state->width + TILE_BORDER,
1035                   WINDOW_OFFSET * 2 + TILE_SIZE * state->height + TILE_BORDER,
1036                   COL_BACKGROUND);
1037         draw_update(fe, 0, 0,
1038                     WINDOW_OFFSET*2 + TILE_SIZE*state->width + TILE_BORDER,
1039                     WINDOW_OFFSET*2 + TILE_SIZE*state->height + TILE_BORDER);
1040
1041         for (phase = 0; phase < 2; phase++) {
1042
1043             for (x = 0; x < ds->width; x++) {
1044                 if (barrier(state, x, 0) & UL)
1045                     draw_barrier_corner(fe, x, -1, LD, phase);
1046                 if (barrier(state, x, 0) & RU)
1047                     draw_barrier_corner(fe, x, -1, DR, phase);
1048                 if (barrier(state, x, 0) & U)
1049                     draw_barrier(fe, x, -1, D, phase);
1050                 if (barrier(state, x, ds->height-1) & DR)
1051                     draw_barrier_corner(fe, x, ds->height, RU, phase);
1052                 if (barrier(state, x, ds->height-1) & LD)
1053                     draw_barrier_corner(fe, x, ds->height, UL, phase);
1054                 if (barrier(state, x, ds->height-1) & D)
1055                     draw_barrier(fe, x, ds->height, U, phase);
1056             }
1057
1058             for (y = 0; y < ds->height; y++) {
1059                 if (barrier(state, 0, y) & UL)
1060                     draw_barrier_corner(fe, -1, y, RU, phase);
1061                 if (barrier(state, 0, y) & LD)
1062                     draw_barrier_corner(fe, -1, y, DR, phase);
1063                 if (barrier(state, 0, y) & L)
1064                     draw_barrier(fe, -1, y, R, phase);
1065                 if (barrier(state, ds->width-1, y) & RU)
1066                     draw_barrier_corner(fe, ds->width, y, UL, phase);
1067                 if (barrier(state, ds->width-1, y) & DR)
1068                     draw_barrier_corner(fe, ds->width, y, LD, phase);
1069                 if (barrier(state, ds->width-1, y) & R)
1070                     draw_barrier(fe, ds->width, y, L, phase);
1071             }
1072         }
1073     }
1074
1075     tx = ty = -1;
1076     frame = -1;
1077     if (oldstate && (t < ROTATE_TIME)) {
1078         /*
1079          * We're animating a tile rotation. Find the turning tile,
1080          * if any.
1081          */
1082         for (x = 0; x < oldstate->width; x++)
1083             for (y = 0; y < oldstate->height; y++)
1084                 if ((tile(oldstate, x, y) ^ tile(state, x, y)) & 0xF) {
1085                     tx = x, ty = y;
1086                     goto break_label;  /* leave both loops at once */
1087                 }
1088         break_label:
1089
1090         if (tx >= 0) {
1091             if (tile(state, tx, ty) == ROT(tile(oldstate, tx, ty),
1092                                            state->last_rotate_dir))
1093                 angle = state->last_rotate_dir * 90.0 * (t / ROTATE_TIME);
1094             else
1095                 angle = state->last_rotate_dir * -90.0 * (t / ROTATE_TIME);
1096             state = oldstate;
1097         }
1098     } else if (t > ROTATE_TIME) {
1099         /*
1100          * We're animating a completion flash. Find which frame
1101          * we're at.
1102          */
1103         frame = (t - ROTATE_TIME) / FLASH_FRAME;
1104     }
1105
1106     /*
1107      * Draw any tile which differs from the way it was last drawn.
1108      */
1109     active = compute_active(state);
1110
1111     for (x = 0; x < ds->width; x++)
1112         for (y = 0; y < ds->height; y++) {
1113             unsigned char c = tile(state, x, y) | index(state, active, x, y);
1114
1115             /*
1116              * In a completion flash, we adjust the LOCKED bit
1117              * depending on our distance from the centre point and
1118              * the frame number.
1119              */
1120             if (frame >= 0) {
1121                 int xdist, ydist, dist;
1122                 xdist = (x < state->cx ? state->cx - x : x - state->cx);
1123                 ydist = (y < state->cy ? state->cy - y : y - state->cy);
1124                 dist = (xdist > ydist ? xdist : ydist);
1125
1126                 if (frame >= dist && frame < dist+4) {
1127                     int lock = (frame - dist) & 1;
1128                     lock = lock ? LOCKED : 0;
1129                     c = (c &~ LOCKED) | lock;
1130                 }
1131             }
1132
1133             if (index(state, ds->visible, x, y) != c ||
1134                 index(state, ds->visible, x, y) == 0xFF ||
1135                 (x == tx && y == ty)) {
1136                 draw_tile(fe, state, x, y, c,
1137                           (x == tx && y == ty ? angle : 0.0));
1138                 if (x == tx && y == ty)
1139                     index(state, ds->visible, x, y) = 0xFF;
1140                 else
1141                     index(state, ds->visible, x, y) = c;
1142             }
1143         }
1144
1145     sfree(active);
1146 }
1147
1148 float game_anim_length(game_state *oldstate, game_state *newstate)
1149 {
1150     float ret = 0.0;
1151     int x, y;
1152
1153     /*
1154      * If there's a tile which has been rotated, allow time to
1155      * animate its rotation.
1156      */
1157     for (x = 0; x < oldstate->width; x++)
1158         for (y = 0; y < oldstate->height; y++)
1159             if ((tile(oldstate, x, y) ^ tile(newstate, x, y)) & 0xF) {
1160                 ret = ROTATE_TIME;
1161                 goto break_label;      /* leave both loops at once */
1162             }
1163     break_label:
1164
1165     /*
1166      * Also, if the game has just been completed, allow time for a
1167      * completion flash.
1168      */
1169     if (!oldstate->completed && newstate->completed) {
1170         int size;
1171         size = 0;
1172         if (size < newstate->cx+1)
1173             size = newstate->cx+1;
1174         if (size < newstate->cy+1)
1175             size = newstate->cy+1;
1176         if (size < newstate->width - newstate->cx)
1177             size = newstate->width - newstate->cx;
1178         if (size < newstate->height - newstate->cy)
1179             size = newstate->height - newstate->cy;
1180         ret += FLASH_FRAME * (size+4);
1181     }
1182
1183     return ret;
1184 }