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 * Randomly select a new game seed.
96 char *new_game_seed(game_params
*params
)
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.
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.)
110 sprintf(buf
, "%d", rand());
114 /* ----------------------------------------------------------------------
115 * Construct an initial game state, given a seed and parameters.
118 game_state
*new_game(game_params
*params
, char *seed
)
122 tree234
*possibilities
, *barriers
;
123 int w
, h
, x
, y
, nbarriers
;
125 assert(params
->width
> 2);
126 assert(params
->height
> 2);
129 * Create a blank game state.
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
);
142 * Set up border barriers if this is a non-wrapping game.
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
;
149 for (y
= 0; y
< state
->height
; y
++) {
150 barrier(state
, y
, 0) |= L
;
151 barrier(state
, y
, state
->width
-1) |= R
;
156 * Seed the internal random number generator.
158 rs
= random_init(seed
, strlen(seed
));
161 * Construct the unshuffled grid.
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).
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
178 * Answer: no it can't, and here's a proof.
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).
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.
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
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
));
208 while (count234(possibilities
) > 0) {
211 int x1
, y1
, d1
, x2
, y2
, d2
, d
;
214 * Extract a randomly chosen possibility from the list.
216 i
= random_upto(rs
, count234(possibilities
));
217 xyd
= delpos234(possibilities
, i
);
223 OFFSET(x2
, y2
, x1
, y1
, d1
, state
);
226 printf("picked (%d,%d,%c) <-> (%d,%d,%c)\n",
227 x1
, y1
, "0RU3L567D9abcdef"[d1
], x2
, y2
, "0RU3L567D9abcdef"[d2
]);
231 * Make the connection. (We should be moving to an as yet
234 tile(state
, x1
, y1
) |= d1
;
235 assert(tile(state
, x2
, y2
) == 0);
236 tile(state
, x2
, y2
) |= d2
;
239 * If we have created a T-piece, remove its last
242 if (COUNT(tile(state
, x1
, y1
)) == 3) {
243 struct xyd xyd1
, *xydp
;
247 xyd1
.direction
= 0x0F ^ tile(state
, x1
, y1
);
249 xydp
= find234(possibilities
, &xyd1
, NULL
);
253 printf("T-piece; removing (%d,%d,%c)\n",
254 xydp
->x
, xydp
->y
, "0RU3L567D9abcdef"[xydp
->direction
]);
256 del234(possibilities
, xydp
);
262 * Remove all other possibilities that were pointing at the
263 * tile we've just moved into.
265 for (d
= 1; d
< 0x10; d
<<= 1) {
267 struct xyd xyd1
, *xydp
;
269 OFFSET(x3
, y3
, x2
, y2
, d
, state
);
276 xydp
= find234(possibilities
, &xyd1
, NULL
);
280 printf("Loop avoidance; removing (%d,%d,%c)\n",
281 xydp
->x
, xydp
->y
, "0RU3L567D9abcdef"[xydp
->direction
]);
283 del234(possibilities
, xydp
);
289 * Add new possibilities to the list for moving _out_ of
290 * the tile we have just moved into.
292 for (d
= 1; d
< 0x10; d
<<= 1) {
296 continue; /* we've got this one already */
298 if (!state
->wrapping
) {
299 if (d
== U
&& y2
== 0)
301 if (d
== D
&& y2
== state
->height
-1)
303 if (d
== L
&& x2
== 0)
305 if (d
== R
&& x2
== state
->width
-1)
309 OFFSET(x3
, y3
, x2
, y2
, d
, state
);
311 if (tile(state
, x3
, y3
))
312 continue; /* this would create a loop */
315 printf("New frontier; adding (%d,%d,%c)\n",
316 x2
, y2
, "0RU3L567D9abcdef"[d
]);
318 add234(possibilities
, new_xyd(x2
, y2
, d
));
321 /* Having done that, we should have no possibilities remaining. */
322 assert(count234(possibilities
) == 0);
323 freetree234(possibilities
);
326 * Now compute a list of the possible barrier locations.
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
++) {
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
));
340 * Now shuffle the grid.
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
);
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.)
364 nbarriers
= params
->barrier_probability
* count234(barriers
);
365 assert(nbarriers
>= 0 && nbarriers
<= count234(barriers
));
367 while (nbarriers
> 0) {
370 int x1
, y1
, d1
, x2
, y2
, d2
;
373 * Extract a randomly chosen barrier from the list.
375 i
= random_upto(rs
, count234(barriers
));
376 xyd
= delpos234(barriers
, i
);
385 OFFSET(x2
, y2
, x1
, y1
, d1
, state
);
388 barrier(state
, x1
, y1
) |= d1
;
389 barrier(state
, x2
, y2
) |= d2
;
395 * Clean up the rest of the barrier list.
400 while ( (xyd
= delpos234(barriers
, 0)) != NULL
)
403 freetree234(barriers
);
411 game_state
*dup_game(game_state
*state
)
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
);
428 void free_game(game_state
*state
)
431 sfree(state
->barriers
);
435 /* ----------------------------------------------------------------------
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
446 static unsigned char *compute_active(game_state
*state
)
448 unsigned char *active
;
452 active
= snewn(state
->width
* state
->height
, unsigned char);
453 memset(active
, 0, state
->width
* state
->height
);
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.
459 todo
= newtree234(xyd_cmp
);
460 add234(todo
, new_xyd(state
->width
/ 2, state
->height
/ 2, 0));
462 while ( (xyd
= delpos234(todo
, 0)) != NULL
) {
463 int x1
, y1
, d1
, x2
, y2
, d2
;
469 for (d1
= 1; d1
< 0x10; d1
<<= 1) {
470 OFFSET(x2
, y2
, x1
, y1
, d1
, state
);
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.
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));
488 /* Now we expect the todo list to have shrunk to zero size. */
489 assert(count234(todo
) == 0);
495 /* ----------------------------------------------------------------------
498 game_state
*make_move(game_state
*state
, int x
, int y
, int button
)
504 * All moves in Net are made with the mouse.
506 if (button
!= LEFT_BUTTON
&&
507 button
!= MIDDLE_BUTTON
&&
508 button
!= RIGHT_BUTTON
)
512 * The button must have been clicked on a valid tile.
520 if (tx
>= state
->width
|| ty
>= state
->height
)
522 if (tx
% TILE_SIZE
>= TILE_SIZE
- TILE_BORDER
||
523 ty
% TILE_SIZE
>= TILE_SIZE
- TILE_BORDER
)
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
536 if (button
== MIDDLE_BUTTON
) {
537 ret
= dup_game(state
);
538 tile(ret
, tx
, ty
) ^= LOCKED
;
543 * The left and right buttons have no effect if clicked on a
546 if (tile(state
, tx
, ty
) & LOCKED
)
550 * Otherwise, turn the tile one way or the other. Left button
551 * turns anticlockwise; right button turns clockwise.
553 ret
= dup_game(state
);
554 orig
= tile(ret
, tx
, ty
);
555 if (button
== LEFT_BUTTON
)
556 tile(ret
, tx
, ty
) = A(orig
);
558 tile(ret
, tx
, ty
) = C(orig
);
561 * Check whether the game has been completed.
564 unsigned char *active
= compute_active(ret
);
568 for (x1
= 0; x1
< ret
->width
; x1
++)
569 for (y1
= 0; y1
< ret
->height
; y1
++)
570 if (!index(ret
, active
, x1
, y1
)) {
572 goto break_label
; /* break out of two loops at once */
579 ret
->completed
= TRUE
;
585 /* ----------------------------------------------------------------------
586 * Routines for drawing the game position on the screen.
589 #ifndef TESTMODE /* FIXME: should be #ifdef */
593 game_params params
= { 13, 11, TRUE
, 0.1 };
596 unsigned char *active
;
599 state
= new_game(¶ms
, seed
);
600 active
= compute_active(state
);
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");
611 printf("\033[0;31m");
612 putchar("~``m`qjv`lxtkwua"[tile(state
, x
, y
)]);