219680799499af508fd5ac5db802fe39d66da166
13 /* Direction bitfields */
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) )
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 )
33 #define COUNT(x) ( (((x) & 0x08) >> 3) + (((x) & 0x04) >> 2) + \
34 (((x) & 0x02) >> 1) + ((x) & 0x01) )
38 #define WINDOW_OFFSET 16
44 float barrier_probability
;
48 int width
, height
, wrapping
, completed
;
50 unsigned char *barriers
;
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)
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)
65 static int xyd_cmp(void *av
, void *bv
) {
66 struct xyd
*a
= (struct xyd
*)av
;
67 struct xyd
*b
= (struct xyd
*)bv
;
76 if (a
->direction
< b
->direction
)
78 if (a
->direction
> b
->direction
)
83 static struct xyd
*new_xyd(int x
, int y
, int direction
)
85 struct xyd
*xyd
= snew(struct xyd
);
88 xyd
->direction
= direction
;
92 /* ----------------------------------------------------------------------
93 * Manage game parameters.
95 game_params
*default_params(void)
97 game_params
*ret
= snew(game_params
);
101 ret
->wrapping
= FALSE
;
102 ret
->barrier_probability
= 0.0;
107 void free_params(game_params
*params
)
112 /* ----------------------------------------------------------------------
113 * Randomly select a new game seed.
116 char *new_game_seed(game_params
*params
)
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.
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.)
130 sprintf(buf
, "%d", rand());
134 /* ----------------------------------------------------------------------
135 * Construct an initial game state, given a seed and parameters.
138 game_state
*new_game(game_params
*params
, char *seed
)
142 tree234
*possibilities
, *barriers
;
143 int w
, h
, x
, y
, nbarriers
;
145 assert(params
->width
> 2);
146 assert(params
->height
> 2);
149 * Create a blank game state.
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
);
162 * Set up border barriers if this is a non-wrapping game.
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
;
169 for (y
= 0; y
< state
->height
; y
++) {
170 barrier(state
, y
, 0) |= L
;
171 barrier(state
, y
, state
->width
-1) |= R
;
176 * Seed the internal random number generator.
178 rs
= random_init(seed
, strlen(seed
));
181 * Construct the unshuffled grid.
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).
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
198 * Answer: no it can't, and here's a proof.
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).
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.
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
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
));
228 while (count234(possibilities
) > 0) {
231 int x1
, y1
, d1
, x2
, y2
, d2
, d
;
234 * Extract a randomly chosen possibility from the list.
236 i
= random_upto(rs
, count234(possibilities
));
237 xyd
= delpos234(possibilities
, i
);
243 OFFSET(x2
, y2
, x1
, y1
, d1
, state
);
246 printf("picked (%d,%d,%c) <-> (%d,%d,%c)\n",
247 x1
, y1
, "0RU3L567D9abcdef"[d1
], x2
, y2
, "0RU3L567D9abcdef"[d2
]);
251 * Make the connection. (We should be moving to an as yet
254 tile(state
, x1
, y1
) |= d1
;
255 assert(tile(state
, x2
, y2
) == 0);
256 tile(state
, x2
, y2
) |= d2
;
259 * If we have created a T-piece, remove its last
262 if (COUNT(tile(state
, x1
, y1
)) == 3) {
263 struct xyd xyd1
, *xydp
;
267 xyd1
.direction
= 0x0F ^ tile(state
, x1
, y1
);
269 xydp
= find234(possibilities
, &xyd1
, NULL
);
273 printf("T-piece; removing (%d,%d,%c)\n",
274 xydp
->x
, xydp
->y
, "0RU3L567D9abcdef"[xydp
->direction
]);
276 del234(possibilities
, xydp
);
282 * Remove all other possibilities that were pointing at the
283 * tile we've just moved into.
285 for (d
= 1; d
< 0x10; d
<<= 1) {
287 struct xyd xyd1
, *xydp
;
289 OFFSET(x3
, y3
, x2
, y2
, d
, state
);
296 xydp
= find234(possibilities
, &xyd1
, NULL
);
300 printf("Loop avoidance; removing (%d,%d,%c)\n",
301 xydp
->x
, xydp
->y
, "0RU3L567D9abcdef"[xydp
->direction
]);
303 del234(possibilities
, xydp
);
309 * Add new possibilities to the list for moving _out_ of
310 * the tile we have just moved into.
312 for (d
= 1; d
< 0x10; d
<<= 1) {
316 continue; /* we've got this one already */
318 if (!state
->wrapping
) {
319 if (d
== U
&& y2
== 0)
321 if (d
== D
&& y2
== state
->height
-1)
323 if (d
== L
&& x2
== 0)
325 if (d
== R
&& x2
== state
->width
-1)
329 OFFSET(x3
, y3
, x2
, y2
, d
, state
);
331 if (tile(state
, x3
, y3
))
332 continue; /* this would create a loop */
335 printf("New frontier; adding (%d,%d,%c)\n",
336 x2
, y2
, "0RU3L567D9abcdef"[d
]);
338 add234(possibilities
, new_xyd(x2
, y2
, d
));
341 /* Having done that, we should have no possibilities remaining. */
342 assert(count234(possibilities
) == 0);
343 freetree234(possibilities
);
346 * Now compute a list of the possible barrier locations.
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
++) {
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
));
360 * Now shuffle the grid.
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
);
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.)
384 nbarriers
= params
->barrier_probability
* count234(barriers
);
385 assert(nbarriers
>= 0 && nbarriers
<= count234(barriers
));
387 while (nbarriers
> 0) {
390 int x1
, y1
, d1
, x2
, y2
, d2
;
393 * Extract a randomly chosen barrier from the list.
395 i
= random_upto(rs
, count234(barriers
));
396 xyd
= delpos234(barriers
, i
);
405 OFFSET(x2
, y2
, x1
, y1
, d1
, state
);
408 barrier(state
, x1
, y1
) |= d1
;
409 barrier(state
, x2
, y2
) |= d2
;
415 * Clean up the rest of the barrier list.
420 while ( (xyd
= delpos234(barriers
, 0)) != NULL
)
423 freetree234(barriers
);
431 game_state
*dup_game(game_state
*state
)
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
);
448 void free_game(game_state
*state
)
451 sfree(state
->barriers
);
455 /* ----------------------------------------------------------------------
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
466 static unsigned char *compute_active(game_state
*state
)
468 unsigned char *active
;
472 active
= snewn(state
->width
* state
->height
, unsigned char);
473 memset(active
, 0, state
->width
* state
->height
);
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.
479 todo
= newtree234(xyd_cmp
);
480 add234(todo
, new_xyd(state
->width
/ 2, state
->height
/ 2, 0));
482 while ( (xyd
= delpos234(todo
, 0)) != NULL
) {
483 int x1
, y1
, d1
, x2
, y2
, d2
;
489 for (d1
= 1; d1
< 0x10; d1
<<= 1) {
490 OFFSET(x2
, y2
, x1
, y1
, d1
, state
);
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.
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));
508 /* Now we expect the todo list to have shrunk to zero size. */
509 assert(count234(todo
) == 0);
515 /* ----------------------------------------------------------------------
518 game_state
*make_move(game_state
*state
, int x
, int y
, int button
)
524 * All moves in Net are made with the mouse.
526 if (button
!= LEFT_BUTTON
&&
527 button
!= MIDDLE_BUTTON
&&
528 button
!= RIGHT_BUTTON
)
532 * The button must have been clicked on a valid tile.
534 x
-= WINDOW_OFFSET
+ TILE_BORDER
;
535 y
-= WINDOW_OFFSET
+ TILE_BORDER
;
540 if (tx
>= state
->width
|| ty
>= state
->height
)
542 if (tx
% TILE_SIZE
>= TILE_SIZE
- TILE_BORDER
||
543 ty
% TILE_SIZE
>= TILE_SIZE
- TILE_BORDER
)
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
556 if (button
== MIDDLE_BUTTON
) {
557 ret
= dup_game(state
);
558 tile(ret
, tx
, ty
) ^= LOCKED
;
563 * The left and right buttons have no effect if clicked on a
566 if (tile(state
, tx
, ty
) & LOCKED
)
570 * Otherwise, turn the tile one way or the other. Left button
571 * turns anticlockwise; right button turns clockwise.
573 ret
= dup_game(state
);
574 orig
= tile(ret
, tx
, ty
);
575 if (button
== LEFT_BUTTON
)
576 tile(ret
, tx
, ty
) = A(orig
);
578 tile(ret
, tx
, ty
) = C(orig
);
581 * Check whether the game has been completed.
584 unsigned char *active
= compute_active(ret
);
588 for (x1
= 0; x1
< ret
->width
; x1
++)
589 for (y1
= 0; y1
< ret
->height
; y1
++)
590 if (!index(ret
, active
, x1
, y1
)) {
592 goto break_label
; /* break out of two loops at once */
599 ret
->completed
= TRUE
;
605 /* ----------------------------------------------------------------------
606 * Routines for drawing the game position on the screen.
609 void game_size(game_params
*params
, int *x
, int *y
)
611 *x
= WINDOW_OFFSET
* 2 + TILE_SIZE
* params
->width
+ TILE_BORDER
;
612 *y
= WINDOW_OFFSET
* 2 + TILE_SIZE
* params
->height
+ TILE_BORDER
;
615 /* ----------------------------------------------------------------------
623 game_params params
= { 13, 11, TRUE
, 0.1 };
626 unsigned char *active
;
629 state
= new_game(¶ms
, seed
);
630 active
= compute_active(state
);
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");
641 printf("\033[0;31m");
642 putchar("~``m`qjv`lxtkwua"[tile(state
, x
, y
)]);