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