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
  10 #include "puzzles.h"
  11 #include "tree234.h"
  12
  13 /* Direction bitfields */
  14 #define R 0x01
  15 #define U 0x02
  16 #define L 0x04
  17 #define D 0x08
  18 #define LOCKED 0x10
  19
  20 /* Rotations: Anticlockwise, Clockwise, Flip, general rotate */
  21 #define A(x) ( (((x) & 0x07) << 1) | (((x) & 0x08) >> 3) )
  22 #define C(x) ( (((x) & 0x0E) >> 1) | (((x) & 0x01) << 3) )
  23 #define F(x) ( (((x) & 0x0C) >> 2) | (((x) & 0x03) << 2) )
  24 #define ROT(x, n) ( ((n)&3) == 0 ? (x) : \
  25                     ((n)&3) == 1 ? A(x) : \
  26                     ((n)&3) == 2 ? F(x) : C(x) )
  27
  28 /* X and Y displacements */
  29 #define X(x) ( (x) == R ? +1 : (x) == L ? -1 : 0 )
  30 #define Y(x) ( (x) == D ? +1 : (x) == U ? -1 : 0 )
  31
  32 /* Bit count */
  33 #define COUNT(x) ( (((x) & 0x08) >> 3) + (((x) & 0x04) >> 2) + \
  34                    (((x) & 0x02) >> 1) + ((x) & 0x01) )
  35
  36 #define TILE_SIZE 32
  37 #define TILE_BORDER 1
  38 #define WINDOW_OFFSET 16
  39
  40 struct game_params {
  41     int width;
  42     int height;
  43     int wrapping;
  44     float barrier_probability;
  45 };
  46
  47 struct game_state {
  48     int width, height, wrapping, completed;
  49     unsigned char *tiles;
  50     unsigned char *barriers;
  51 };
  52
  53 #define OFFSET(x2,y2,x1,y1,dir,state) \
  54     ( (x2) = ((x1) + (state)->width + X((dir))) % (state)->width, \
  55       (y2) = ((y1) + (state)->height + Y((dir))) % (state)->height)
  56
  57 #define index(state, a, x, y) ( a[(y) * (state)->width + (x)] )
  58 #define tile(state, x, y)     index(state, (state)->tiles, x, y)
  59 #define barrier(state, x, y)  index(state, (state)->barriers, x, y)
  60
  61 struct xyd {
  62     int x, y, direction;
  63 };
  64
  65 static int xyd_cmp(void *av, void *bv) {
  66     struct xyd *a = (struct xyd *)av;
  67     struct xyd *b = (struct xyd *)bv;
  68     if (a->x < b->x)
  69         return -1;
  70     if (a->x > b->x)
  71         return +1;
  72     if (a->y < b->y)
  73         return -1;
  74     if (a->y > b->y)
  75         return +1;
  76     if (a->direction < b->direction)
  77         return -1;
  78     if (a->direction > b->direction)
  79         return +1;
  80     return 0;
  81 };
  82
  83 static struct xyd *new_xyd(int x, int y, int direction)
  84 {
  85     struct xyd *xyd = snew(struct xyd);
  86     xyd->x = x;
  87     xyd->y = y;
  88     xyd->direction = direction;
  89     return xyd;
  90 }
  91
  92 /* ----------------------------------------------------------------------
  93  * Randomly select a new game seed.
  94  */
  95
  96 char *new_game_seed(game_params *params)
  97 {
  98     /*
  99      * The full description of a Net game is far too large to
 100      * encode directly in the seed, so by default we'll have to go
 101      * for the simple approach of providing a random-number seed.
 102      *
 103      * (This does not restrict me from _later on_ inventing a seed
 104      * string syntax which can never be generated by this code -
 105      * for example, strings beginning with a letter - allowing me
 106      * to type in a precise game, and have new_game detect it and
 107      * understand it and do something completely different.)
 108      */
 109     char buf[40];
 110     sprintf(buf, "%d", rand());
 111     return dupstr(buf);
 112 }
 113
 114 /* ----------------------------------------------------------------------
 115  * Construct an initial game state, given a seed and parameters.
 116  */
 117
 118 game_state *new_game(game_params *params, char *seed)
 119 {
 120     random_state *rs;
 121     game_state *state;
 122     tree234 *possibilities, *barriers;
 123     int w, h, x, y, nbarriers;
 124
 125     assert(params->width > 2);
 126     assert(params->height > 2);
 127
 128     /*
 129      * Create a blank game state.
 130      */
 131     state = snew(game_state);
 132     w = state->width = params->width;
 133     h = state->height = params->height;
 134     state->wrapping = params->wrapping;
 135     state->completed = FALSE;
 136     state->tiles = snewn(state->width * state->height, unsigned char);
 137     memset(state->tiles, 0, state->width * state->height);
 138     state->barriers = snewn(state->width * state->height, unsigned char);
 139     memset(state->barriers, 0, state->width * state->height);
 140
 141     /*
 142      * Set up border barriers if this is a non-wrapping game.
 143      */
 144     if (!state->wrapping) {
 145         for (x = 0; x < state->width; x++) {
 146             barrier(state, x, 0) |= U;
 147             barrier(state, x, state->height-1) |= D;
 148         }
 149         for (y = 0; y < state->height; y++) {
 150             barrier(state, y, 0) |= L;
 151             barrier(state, y, state->width-1) |= R;
 152         }
 153     }
 154
 155     /*
 156      * Seed the internal random number generator.
 157      */
 158     rs = random_init(seed, strlen(seed));
 159
 160     /*
 161      * Construct the unshuffled grid.
 162      *
 163      * To do this, we simply start at the centre point, repeatedly
 164      * choose a random possibility out of the available ways to
 165      * extend a used square into an unused one, and do it. After
 166      * extending the third line out of a square, we remove the
 167      * fourth from the possibilities list to avoid any full-cross
 168      * squares (which would make the game too easy because they
 169      * only have one orientation).
 170      *
 171      * The slightly worrying thing is the avoidance of full-cross
 172      * squares. Can this cause our unsophisticated construction
 173      * algorithm to paint itself into a corner, by getting into a
 174      * situation where there are some unreached squares and the
 175      * only way to reach any of them is to extend a T-piece into a
 176      * full cross?
 177      *
 178      * Answer: no it can't, and here's a proof.
 179      *
 180      * Any contiguous group of such unreachable squares must be
 181      * surrounded on _all_ sides by T-pieces pointing away from the
 182      * group. (If not, then there is a square which can be extended
 183      * into one of the `unreachable' ones, and so it wasn't
 184      * unreachable after all.) In particular, this implies that
 185      * each contiguous group of unreachable squares must be
 186      * rectangular in shape (any deviation from that yields a
 187      * non-T-piece next to an `unreachable' square).
 188      *
 189      * So we have a rectangle of unreachable squares, with T-pieces
 190      * forming a solid border around the rectangle. The corners of
 191      * that border must be connected (since every tile connects all
 192      * the lines arriving in it), and therefore the border must
 193      * form a closed loop around the rectangle.
 194      *
 195      * But this can't have happened in the first place, since we
 196      * _know_ we've avoided creating closed loops! Hence, no such
 197      * situation can ever arise, and the naive grid construction
 198      * algorithm will guaranteeably result in a complete grid
 199      * containing no unreached squares, no full crosses _and_ no
 200      * closed loops. []
 201      */
 202     possibilities = newtree234(xyd_cmp);
 203     add234(possibilities, new_xyd(w/2, h/2, R));
 204     add234(possibilities, new_xyd(w/2, h/2, U));
 205     add234(possibilities, new_xyd(w/2, h/2, L));
 206     add234(possibilities, new_xyd(w/2, h/2, D));
 207
 208     while (count234(possibilities) > 0) {
 209         int i;
 210         struct xyd *xyd;
 211         int x1, y1, d1, x2, y2, d2, d;
 212
 213         /*
 214          * Extract a randomly chosen possibility from the list.
 215          */
 216         i = random_upto(rs, count234(possibilities));
 217         xyd = delpos234(possibilities, i);
 218         x1 = xyd->x;
 219         y1 = xyd->y;
 220         d1 = xyd->direction;
 221         sfree(xyd);
 222
 223         OFFSET(x2, y2, x1, y1, d1, state);
 224         d2 = F(d1);
 225 #ifdef DEBUG
 226         printf("picked (%d,%d,%c) <-> (%d,%d,%c)\n",
 227                x1, y1, "0RU3L567D9abcdef"[d1], x2, y2, "0RU3L567D9abcdef"[d2]);
 228 #endif
 229
 230         /*
 231          * Make the connection. (We should be moving to an as yet
 232          * unused tile.)
 233          */
 234         tile(state, x1, y1) |= d1;
 235         assert(tile(state, x2, y2) == 0);
 236         tile(state, x2, y2) |= d2;
 237
 238         /*
 239          * If we have created a T-piece, remove its last
 240          * possibility.
 241          */
 242         if (COUNT(tile(state, x1, y1)) == 3) {
 243             struct xyd xyd1, *xydp;
 244
 245             xyd1.x = x1;
 246             xyd1.y = y1;
 247             xyd1.direction = 0x0F ^ tile(state, x1, y1);
 248
 249             xydp = find234(possibilities, &xyd1, NULL);
 250
 251             if (xydp) {
 252 #ifdef DEBUG
 253                 printf("T-piece; removing (%d,%d,%c)\n",
 254                        xydp->x, xydp->y, "0RU3L567D9abcdef"[xydp->direction]);
 255 #endif
 256                 del234(possibilities, xydp);
 257                 sfree(xydp);
 258             }
 259         }
 260
 261         /*
 262          * Remove all other possibilities that were pointing at the
 263          * tile we've just moved into.
 264          */
 265         for (d = 1; d < 0x10; d <<= 1) {
 266             int x3, y3, d3;
 267             struct xyd xyd1, *xydp;
 268
 269             OFFSET(x3, y3, x2, y2, d, state);
 270             d3 = F(d);
 271
 272             xyd1.x = x3;
 273             xyd1.y = y3;
 274             xyd1.direction = d3;
 275
 276             xydp = find234(possibilities, &xyd1, NULL);
 277
 278             if (xydp) {
 279 #ifdef DEBUG
 280                 printf("Loop avoidance; removing (%d,%d,%c)\n",
 281                        xydp->x, xydp->y, "0RU3L567D9abcdef"[xydp->direction]);
 282 #endif
 283                 del234(possibilities, xydp);
 284                 sfree(xydp);
 285             }
 286         }
 287
 288         /*
 289          * Add new possibilities to the list for moving _out_ of
 290          * the tile we have just moved into.
 291          */
 292         for (d = 1; d < 0x10; d <<= 1) {
 293             int x3, y3;
 294
 295             if (d == d2)
 296                 continue;              /* we've got this one already */
 297
 298             if (!state->wrapping) {
 299                 if (d == U && y2 == 0)
 300                     continue;
 301                 if (d == D && y2 == state->height-1)
 302                     continue;
 303                 if (d == L && x2 == 0)
 304                     continue;
 305                 if (d == R && x2 == state->width-1)
 306                     continue;
 307             }
 308
 309             OFFSET(x3, y3, x2, y2, d, state);
 310
 311             if (tile(state, x3, y3))
 312                 continue;              /* this would create a loop */
 313
 314 #ifdef DEBUG
 315             printf("New frontier; adding (%d,%d,%c)\n",
 316                    x2, y2, "0RU3L567D9abcdef"[d]);
 317 #endif
 318             add234(possibilities, new_xyd(x2, y2, d));
 319         }
 320     }
 321     /* Having done that, we should have no possibilities remaining. */
 322     assert(count234(possibilities) == 0);
 323     freetree234(possibilities);
 324
 325     /*
 326      * Now compute a list of the possible barrier locations.
 327      */
 328     barriers = newtree234(xyd_cmp);
 329     for (y = 0; y < state->height - (!state->wrapping); y++) {
 330         for (x = 0; x < state->width - (!state->wrapping); x++) {
 331
 332             if (!(tile(state, x, y) & R))
 333                 add234(barriers, new_xyd(x, y, R));
 334             if (!(tile(state, x, y) & D))
 335                 add234(barriers, new_xyd(x, y, D));
 336         }
 337     }
 338
 339     /*
 340      * Now shuffle the grid.
 341      */
 342     for (y = 0; y < state->height - (!state->wrapping); y++) {
 343         for (x = 0; x < state->width - (!state->wrapping); x++) {
 344             int orig = tile(state, x, y);
 345             int rot = random_upto(rs, 4);
 346             tile(state, x, y) = ROT(orig, rot);
 347         }
 348     }
 349
 350     /*
 351      * And now choose barrier locations. (We carefully do this
 352      * _after_ shuffling, so that changing the barrier rate in the
 353      * params while keeping the game seed the same will give the
 354      * same shuffled grid and _only_ change the barrier locations.
 355      * Also the way we choose barrier locations, by repeatedly
 356      * choosing one possibility from the list until we have enough,
 357      * is designed to ensure that raising the barrier rate while
 358      * keeping the seed the same will provide a superset of the
 359      * previous barrier set - i.e. if you ask for 10 barriers, and
 360      * then decide that's still too hard and ask for 20, you'll get
 361      * the original 10 plus 10 more, rather than getting 20 new
 362      * ones and the chance of remembering your first 10.)
 363      */
 364     nbarriers = params->barrier_probability * count234(barriers);
 365     assert(nbarriers >= 0 && nbarriers <= count234(barriers));
 366
 367     while (nbarriers > 0) {
 368         int i;
 369         struct xyd *xyd;
 370         int x1, y1, d1, x2, y2, d2;
 371
 372         /*
 373          * Extract a randomly chosen barrier from the list.
 374          */
 375         i = random_upto(rs, count234(barriers));
 376         xyd = delpos234(barriers, i);
 377
 378         assert(xyd != NULL);
 379
 380         x1 = xyd->x;
 381         y1 = xyd->y;
 382         d1 = xyd->direction;
 383         sfree(xyd);
 384
 385         OFFSET(x2, y2, x1, y1, d1, state);
 386         d2 = F(d1);
 387
 388         barrier(state, x1, y1) |= d1;
 389         barrier(state, x2, y2) |= d2;
 390
 391         nbarriers--;
 392     }
 393
 394     /*
 395      * Clean up the rest of the barrier list.
 396      */
 397     {
 398         struct xyd *xyd;
 399
 400         while ( (xyd = delpos234(barriers, 0)) != NULL)
 401             sfree(xyd);
 402
 403         freetree234(barriers);
 404     }
 405
 406     random_free(rs);
 407
 408     return state;
 409 }
 410
 411 game_state *dup_game(game_state *state)
 412 {
 413     game_state *ret;
 414
 415     ret = snew(game_state);
 416     ret->width = state->width;
 417     ret->height = state->height;
 418     ret->wrapping = state->wrapping;
 419     ret->completed = state->completed;
 420     ret->tiles = snewn(state->width * state->height, unsigned char);
 421     memcpy(ret->tiles, state->tiles, state->width * state->height);
 422     ret->barriers = snewn(state->width * state->height, unsigned char);
 423     memcpy(ret->barriers, state->barriers, state->width * state->height);
 424
 425     return ret;
 426 }
 427
 428 void free_game(game_state *state)
 429 {
 430     sfree(state->tiles);
 431     sfree(state->barriers);
 432     sfree(state);
 433 }
 434
 435 /* ----------------------------------------------------------------------
 436  * Utility routine.
 437  */
 438
 439 /*
 440  * Compute which squares are reachable from the centre square, as a
 441  * quick visual aid to determining how close the game is to
 442  * completion. This is also a simple way to tell if the game _is_
 443  * completed - just call this function and see whether every square
 444  * is marked active.
 445  */
 446 static unsigned char *compute_active(game_state *state)
 447 {
 448     unsigned char *active;
 449     tree234 *todo;
 450     struct xyd *xyd;
 451
 452     active = snewn(state->width * state->height, unsigned char);
 453     memset(active, 0, state->width * state->height);
 454
 455     /*
 456      * We only store (x,y) pairs in todo, but it's easier to reuse
 457      * xyd_cmp and just store direction 0 every time.
 458      */
 459     todo = newtree234(xyd_cmp);
 460     add234(todo, new_xyd(state->width / 2, state->height / 2, 0));
 461
 462     while ( (xyd = delpos234(todo, 0)) != NULL) {
 463         int x1, y1, d1, x2, y2, d2;
 464
 465         x1 = xyd->x;
 466         y1 = xyd->y;
 467         sfree(xyd);
 468
 469         for (d1 = 1; d1 < 0x10; d1 <<= 1) {
 470             OFFSET(x2, y2, x1, y1, d1, state);
 471             d2 = F(d1);
 472
 473             /*
 474              * If the next tile in this direction is connected to
 475              * us, and there isn't a barrier in the way, and it
 476              * isn't already marked active, then mark it active and
 477              * add it to the to-examine list.
 478              */
 479             if ((tile(state, x1, y1) & d1) &&
 480                 (tile(state, x2, y2) & d2) &&
 481                 !(barrier(state, x1, y1) & d1) &&
 482                 !index(state, active, x2, y2)) {
 483                 index(state, active, x2, y2) = 1;
 484                 add234(todo, new_xyd(x2, y2, 0));
 485             }
 486         }
 487     }
 488     /* Now we expect the todo list to have shrunk to zero size. */
 489     assert(count234(todo) == 0);
 490     freetree234(todo);
 491
 492     return active;
 493 }
 494
 495 /* ----------------------------------------------------------------------
 496  * Process a move.
 497  */
 498 game_state *make_move(game_state *state, int x, int y, int button)
 499 {
 500     game_state *ret;
 501     int tx, ty, orig;
 502
 503     /*
 504      * All moves in Net are made with the mouse.
 505      */
 506     if (button != LEFT_BUTTON &&
 507         button != MIDDLE_BUTTON &&
 508         button != RIGHT_BUTTON)
 509         return NULL;
 510
 511     /*
 512      * The button must have been clicked on a valid tile.
 513      */
 514     x -= WINDOW_OFFSET;
 515     y -= WINDOW_OFFSET;
 516     if (x < 0 || y < 0)
 517         return NULL;
 518     tx = x / TILE_SIZE;
 519     ty = y / TILE_SIZE;
 520     if (tx >= state->width || ty >= state->height)
 521         return NULL;
 522     if (tx % TILE_SIZE >= TILE_SIZE - TILE_BORDER ||
 523         ty % TILE_SIZE >= TILE_SIZE - TILE_BORDER)
 524         return NULL;
 525
 526     /*
 527      * The middle button locks or unlocks a tile. (A locked tile
 528      * cannot be turned, and is visually marked as being locked.
 529      * This is a convenience for the player, so that once they are
 530      * sure which way round a tile goes, they can lock it and thus
 531      * avoid forgetting later on that they'd already done that one;
 532      * and the locking also prevents them turning the tile by
 533      * accident. If they change their mind, another middle click
 534      * unlocks it.)
 535      */
 536     if (button == MIDDLE_BUTTON) {
 537         ret = dup_game(state);
 538         tile(ret, tx, ty) ^= LOCKED;
 539         return ret;
 540     }
 541
 542     /*
 543      * The left and right buttons have no effect if clicked on a
 544      * locked tile.
 545      */
 546     if (tile(state, tx, ty) & LOCKED)
 547         return NULL;
 548
 549     /*
 550      * Otherwise, turn the tile one way or the other. Left button
 551      * turns anticlockwise; right button turns clockwise.
 552      */
 553     ret = dup_game(state);
 554     orig = tile(ret, tx, ty);
 555     if (button == LEFT_BUTTON)
 556         tile(ret, tx, ty) = A(orig);
 557     else
 558         tile(ret, tx, ty) = C(orig);
 559
 560     /*
 561      * Check whether the game has been completed.
 562      */
 563     {
 564         unsigned char *active = compute_active(ret);
 565         int x1, y1;
 566         int complete = TRUE;
 567
 568         for (x1 = 0; x1 < ret->width; x1++)
 569             for (y1 = 0; y1 < ret->height; y1++)
 570                 if (!index(ret, active, x1, y1)) {
 571                     complete = FALSE;
 572                     goto break_label;  /* break out of two loops at once */
 573                 }
 574         break_label:
 575
 576         sfree(active);
 577
 578         if (complete)
 579             ret->completed = TRUE;
 580     }
 581
 582     return ret;
 583 }
 584
 585 /* ----------------------------------------------------------------------
 586  * Routines for drawing the game position on the screen.
 587  */
 588
 589 #ifndef TESTMODE                       /* FIXME: should be #ifdef */
 590
 591 int main(void)
 592 {
 593     game_params params = { 13, 11, TRUE, 0.1 };
 594     char *seed;
 595     game_state *state;
 596     unsigned char *active;
 597
 598     seed = "123";
 599     state = new_game(&params, seed);
 600     active = compute_active(state);
 601
 602     {
 603         int x, y;
 604
 605         printf("\033)0\016");
 606         for (y = 0; y < state->height; y++) {
 607             for (x = 0; x < state->width; x++) {
 608                 if (index(state, active, x, y))
 609                     printf("\033[1;32m");
 610                 else
 611                     printf("\033[0;31m");
 612                 putchar("~``m`qjv`lxtkwua"[tile(state, x, y)]);
 613             }
 614             printf("\033[m\n");
 615         }
 616         printf("\017");
 617     }
 618
 619     free_game(state);
 620
 621     return 0;
 622 }
 623
 624 #endif