diff options
Diffstat (limited to 'apps/plugins/puzzles/src/net.c')
-rw-r--r-- | apps/plugins/puzzles/src/net.c | 3240 |
1 files changed, 3240 insertions, 0 deletions
diff --git a/apps/plugins/puzzles/src/net.c b/apps/plugins/puzzles/src/net.c new file mode 100644 index 0000000000..de51f82fd7 --- /dev/null +++ b/apps/plugins/puzzles/src/net.c | |||
@@ -0,0 +1,3240 @@ | |||
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 <ctype.h> | ||
10 | #include <math.h> | ||
11 | |||
12 | #include "puzzles.h" | ||
13 | #include "tree234.h" | ||
14 | |||
15 | /* | ||
16 | * The standard user interface for Net simply has left- and | ||
17 | * right-button mouse clicks in a square rotate it one way or the | ||
18 | * other. We also provide, by #ifdef, a separate interface based on | ||
19 | * rotational dragging motions. I initially developed this for the | ||
20 | * Mac on the basis that it might work better than the click | ||
21 | * interface with only one mouse button available, but in fact | ||
22 | * found it to be quite strange and unintuitive. Apparently it | ||
23 | * works better on stylus-driven platforms such as Palm and | ||
24 | * PocketPC, though, so we enable it by default there. | ||
25 | */ | ||
26 | #ifdef STYLUS_BASED | ||
27 | #define USE_DRAGGING | ||
28 | #endif | ||
29 | |||
30 | #define MATMUL(xr,yr,m,x,y) do { \ | ||
31 | float rx, ry, xx = (x), yy = (y), *mat = (m); \ | ||
32 | rx = mat[0] * xx + mat[2] * yy; \ | ||
33 | ry = mat[1] * xx + mat[3] * yy; \ | ||
34 | (xr) = rx; (yr) = ry; \ | ||
35 | } while (0) | ||
36 | |||
37 | /* Direction and other bitfields */ | ||
38 | #define R 0x01 | ||
39 | #define U 0x02 | ||
40 | #define L 0x04 | ||
41 | #define D 0x08 | ||
42 | #define LOCKED 0x10 | ||
43 | #define ACTIVE 0x20 | ||
44 | #define RLOOP (R << 6) | ||
45 | #define ULOOP (U << 6) | ||
46 | #define LLOOP (L << 6) | ||
47 | #define DLOOP (D << 6) | ||
48 | #define LOOP(dir) ((dir) << 6) | ||
49 | |||
50 | /* Rotations: Anticlockwise, Clockwise, Flip, general rotate */ | ||
51 | #define A(x) ( (((x) & 0x07) << 1) | (((x) & 0x08) >> 3) ) | ||
52 | #define C(x) ( (((x) & 0x0E) >> 1) | (((x) & 0x01) << 3) ) | ||
53 | #define F(x) ( (((x) & 0x0C) >> 2) | (((x) & 0x03) << 2) ) | ||
54 | #define ROT(x, n) ( ((n)&3) == 0 ? (x) : \ | ||
55 | ((n)&3) == 1 ? A(x) : \ | ||
56 | ((n)&3) == 2 ? F(x) : C(x) ) | ||
57 | |||
58 | /* X and Y displacements */ | ||
59 | #define X(x) ( (x) == R ? +1 : (x) == L ? -1 : 0 ) | ||
60 | #define Y(x) ( (x) == D ? +1 : (x) == U ? -1 : 0 ) | ||
61 | |||
62 | /* Bit count */ | ||
63 | #define COUNT(x) ( (((x) & 0x08) >> 3) + (((x) & 0x04) >> 2) + \ | ||
64 | (((x) & 0x02) >> 1) + ((x) & 0x01) ) | ||
65 | |||
66 | #define PREFERRED_TILE_SIZE 32 | ||
67 | #define TILE_SIZE (ds->tilesize) | ||
68 | #define TILE_BORDER 1 | ||
69 | #ifdef SMALL_SCREEN | ||
70 | #define WINDOW_OFFSET 4 | ||
71 | #else | ||
72 | #define WINDOW_OFFSET 16 | ||
73 | #endif | ||
74 | |||
75 | #define ROTATE_TIME 0.13F | ||
76 | #define FLASH_FRAME 0.07F | ||
77 | |||
78 | /* Transform physical coords to game coords using game_drawstate ds */ | ||
79 | #define GX(x) (((x) + ds->org_x) % ds->width) | ||
80 | #define GY(y) (((y) + ds->org_y) % ds->height) | ||
81 | /* ...and game coords to physical coords */ | ||
82 | #define RX(x) (((x) + ds->width - ds->org_x) % ds->width) | ||
83 | #define RY(y) (((y) + ds->height - ds->org_y) % ds->height) | ||
84 | |||
85 | enum { | ||
86 | COL_BACKGROUND, | ||
87 | COL_LOCKED, | ||
88 | COL_BORDER, | ||
89 | COL_WIRE, | ||
90 | COL_ENDPOINT, | ||
91 | COL_POWERED, | ||
92 | COL_BARRIER, | ||
93 | COL_LOOP, | ||
94 | NCOLOURS | ||
95 | }; | ||
96 | |||
97 | struct game_params { | ||
98 | int width; | ||
99 | int height; | ||
100 | int wrapping; | ||
101 | int unique; | ||
102 | float barrier_probability; | ||
103 | }; | ||
104 | |||
105 | struct game_state { | ||
106 | int width, height, wrapping, completed; | ||
107 | int last_rotate_x, last_rotate_y, last_rotate_dir; | ||
108 | int used_solve; | ||
109 | unsigned char *tiles; | ||
110 | unsigned char *barriers; | ||
111 | }; | ||
112 | |||
113 | #define OFFSETWH(x2,y2,x1,y1,dir,width,height) \ | ||
114 | ( (x2) = ((x1) + width + X((dir))) % width, \ | ||
115 | (y2) = ((y1) + height + Y((dir))) % height) | ||
116 | |||
117 | #define OFFSET(x2,y2,x1,y1,dir,state) \ | ||
118 | OFFSETWH(x2,y2,x1,y1,dir,(state)->width,(state)->height) | ||
119 | |||
120 | #define index(state, a, x, y) ( a[(y) * (state)->width + (x)] ) | ||
121 | #define tile(state, x, y) index(state, (state)->tiles, x, y) | ||
122 | #define barrier(state, x, y) index(state, (state)->barriers, x, y) | ||
123 | |||
124 | struct xyd { | ||
125 | int x, y, direction; | ||
126 | }; | ||
127 | |||
128 | static int xyd_cmp(const void *av, const void *bv) { | ||
129 | const struct xyd *a = (const struct xyd *)av; | ||
130 | const struct xyd *b = (const struct xyd *)bv; | ||
131 | if (a->x < b->x) | ||
132 | return -1; | ||
133 | if (a->x > b->x) | ||
134 | return +1; | ||
135 | if (a->y < b->y) | ||
136 | return -1; | ||
137 | if (a->y > b->y) | ||
138 | return +1; | ||
139 | if (a->direction < b->direction) | ||
140 | return -1; | ||
141 | if (a->direction > b->direction) | ||
142 | return +1; | ||
143 | return 0; | ||
144 | } | ||
145 | |||
146 | static int xyd_cmp_nc(void *av, void *bv) { return xyd_cmp(av, bv); } | ||
147 | |||
148 | static struct xyd *new_xyd(int x, int y, int direction) | ||
149 | { | ||
150 | struct xyd *xyd = snew(struct xyd); | ||
151 | xyd->x = x; | ||
152 | xyd->y = y; | ||
153 | xyd->direction = direction; | ||
154 | return xyd; | ||
155 | } | ||
156 | |||
157 | /* ---------------------------------------------------------------------- | ||
158 | * Manage game parameters. | ||
159 | */ | ||
160 | static game_params *default_params(void) | ||
161 | { | ||
162 | game_params *ret = snew(game_params); | ||
163 | |||
164 | ret->width = 5; | ||
165 | ret->height = 5; | ||
166 | ret->wrapping = FALSE; | ||
167 | ret->unique = TRUE; | ||
168 | ret->barrier_probability = 0.0; | ||
169 | |||
170 | return ret; | ||
171 | } | ||
172 | |||
173 | static const struct game_params net_presets[] = { | ||
174 | {5, 5, FALSE, TRUE, 0.0}, | ||
175 | {7, 7, FALSE, TRUE, 0.0}, | ||
176 | {9, 9, FALSE, TRUE, 0.0}, | ||
177 | {11, 11, FALSE, TRUE, 0.0}, | ||
178 | #ifndef SMALL_SCREEN | ||
179 | {13, 11, FALSE, TRUE, 0.0}, | ||
180 | #endif | ||
181 | {5, 5, TRUE, TRUE, 0.0}, | ||
182 | {7, 7, TRUE, TRUE, 0.0}, | ||
183 | {9, 9, TRUE, TRUE, 0.0}, | ||
184 | {11, 11, TRUE, TRUE, 0.0}, | ||
185 | #ifndef SMALL_SCREEN | ||
186 | {13, 11, TRUE, TRUE, 0.0}, | ||
187 | #endif | ||
188 | }; | ||
189 | |||
190 | static int game_fetch_preset(int i, char **name, game_params **params) | ||
191 | { | ||
192 | game_params *ret; | ||
193 | char str[80]; | ||
194 | |||
195 | if (i < 0 || i >= lenof(net_presets)) | ||
196 | return FALSE; | ||
197 | |||
198 | ret = snew(game_params); | ||
199 | *ret = net_presets[i]; | ||
200 | |||
201 | sprintf(str, "%dx%d%s", ret->width, ret->height, | ||
202 | ret->wrapping ? " wrapping" : ""); | ||
203 | |||
204 | *name = dupstr(str); | ||
205 | *params = ret; | ||
206 | return TRUE; | ||
207 | } | ||
208 | |||
209 | static void free_params(game_params *params) | ||
210 | { | ||
211 | sfree(params); | ||
212 | } | ||
213 | |||
214 | static game_params *dup_params(const game_params *params) | ||
215 | { | ||
216 | game_params *ret = snew(game_params); | ||
217 | *ret = *params; /* structure copy */ | ||
218 | return ret; | ||
219 | } | ||
220 | |||
221 | static void decode_params(game_params *ret, char const *string) | ||
222 | { | ||
223 | char const *p = string; | ||
224 | |||
225 | ret->width = atoi(p); | ||
226 | while (*p && isdigit((unsigned char)*p)) p++; | ||
227 | if (*p == 'x') { | ||
228 | p++; | ||
229 | ret->height = atoi(p); | ||
230 | while (*p && isdigit((unsigned char)*p)) p++; | ||
231 | } else { | ||
232 | ret->height = ret->width; | ||
233 | } | ||
234 | |||
235 | while (*p) { | ||
236 | if (*p == 'w') { | ||
237 | p++; | ||
238 | ret->wrapping = TRUE; | ||
239 | } else if (*p == 'b') { | ||
240 | p++; | ||
241 | ret->barrier_probability = (float)atof(p); | ||
242 | while (*p && (*p == '.' || isdigit((unsigned char)*p))) p++; | ||
243 | } else if (*p == 'a') { | ||
244 | p++; | ||
245 | ret->unique = FALSE; | ||
246 | } else | ||
247 | p++; /* skip any other gunk */ | ||
248 | } | ||
249 | } | ||
250 | |||
251 | static char *encode_params(const game_params *params, int full) | ||
252 | { | ||
253 | char ret[400]; | ||
254 | int len; | ||
255 | |||
256 | len = sprintf(ret, "%dx%d", params->width, params->height); | ||
257 | if (params->wrapping) | ||
258 | ret[len++] = 'w'; | ||
259 | if (full && params->barrier_probability) | ||
260 | len += sprintf(ret+len, "b%g", params->barrier_probability); | ||
261 | if (full && !params->unique) | ||
262 | ret[len++] = 'a'; | ||
263 | assert(len < lenof(ret)); | ||
264 | ret[len] = '\0'; | ||
265 | |||
266 | return dupstr(ret); | ||
267 | } | ||
268 | |||
269 | static config_item *game_configure(const game_params *params) | ||
270 | { | ||
271 | config_item *ret; | ||
272 | char buf[80]; | ||
273 | |||
274 | ret = snewn(6, config_item); | ||
275 | |||
276 | ret[0].name = "Width"; | ||
277 | ret[0].type = C_STRING; | ||
278 | sprintf(buf, "%d", params->width); | ||
279 | ret[0].sval = dupstr(buf); | ||
280 | ret[0].ival = 0; | ||
281 | |||
282 | ret[1].name = "Height"; | ||
283 | ret[1].type = C_STRING; | ||
284 | sprintf(buf, "%d", params->height); | ||
285 | ret[1].sval = dupstr(buf); | ||
286 | ret[1].ival = 0; | ||
287 | |||
288 | ret[2].name = "Walls wrap around"; | ||
289 | ret[2].type = C_BOOLEAN; | ||
290 | ret[2].sval = NULL; | ||
291 | ret[2].ival = params->wrapping; | ||
292 | |||
293 | ret[3].name = "Barrier probability"; | ||
294 | ret[3].type = C_STRING; | ||
295 | sprintf(buf, "%g", params->barrier_probability); | ||
296 | ret[3].sval = dupstr(buf); | ||
297 | ret[3].ival = 0; | ||
298 | |||
299 | ret[4].name = "Ensure unique solution"; | ||
300 | ret[4].type = C_BOOLEAN; | ||
301 | ret[4].sval = NULL; | ||
302 | ret[4].ival = params->unique; | ||
303 | |||
304 | ret[5].name = NULL; | ||
305 | ret[5].type = C_END; | ||
306 | ret[5].sval = NULL; | ||
307 | ret[5].ival = 0; | ||
308 | |||
309 | return ret; | ||
310 | } | ||
311 | |||
312 | static game_params *custom_params(const config_item *cfg) | ||
313 | { | ||
314 | game_params *ret = snew(game_params); | ||
315 | |||
316 | ret->width = atoi(cfg[0].sval); | ||
317 | ret->height = atoi(cfg[1].sval); | ||
318 | ret->wrapping = cfg[2].ival; | ||
319 | ret->barrier_probability = (float)atof(cfg[3].sval); | ||
320 | ret->unique = cfg[4].ival; | ||
321 | |||
322 | return ret; | ||
323 | } | ||
324 | |||
325 | static char *validate_params(const game_params *params, int full) | ||
326 | { | ||
327 | if (params->width <= 0 || params->height <= 0) | ||
328 | return "Width and height must both be greater than zero"; | ||
329 | if (params->width <= 1 && params->height <= 1) | ||
330 | return "At least one of width and height must be greater than one"; | ||
331 | if (params->barrier_probability < 0) | ||
332 | return "Barrier probability may not be negative"; | ||
333 | if (params->barrier_probability > 1) | ||
334 | return "Barrier probability may not be greater than 1"; | ||
335 | |||
336 | /* | ||
337 | * Specifying either grid dimension as 2 in a wrapping puzzle | ||
338 | * makes it actually impossible to ensure a unique puzzle | ||
339 | * solution. | ||
340 | * | ||
341 | * Proof: | ||
342 | * | ||
343 | * Without loss of generality, let us assume the puzzle _width_ | ||
344 | * is 2, so we can conveniently discuss rows without having to | ||
345 | * say `rows/columns' all the time. (The height may be 2 as | ||
346 | * well, but that doesn't matter.) | ||
347 | * | ||
348 | * In each row, there are two edges between tiles: the inner | ||
349 | * edge (running down the centre of the grid) and the outer | ||
350 | * edge (the identified left and right edges of the grid). | ||
351 | * | ||
352 | * Lemma: In any valid 2xn puzzle there must be at least one | ||
353 | * row in which _exactly one_ of the inner edge and outer edge | ||
354 | * is connected. | ||
355 | * | ||
356 | * Proof: No row can have _both_ inner and outer edges | ||
357 | * connected, because this would yield a loop. So the only | ||
358 | * other way to falsify the lemma is for every row to have | ||
359 | * _neither_ the inner nor outer edge connected. But this | ||
360 | * means there is no connection at all between the left and | ||
361 | * right columns of the puzzle, so there are two disjoint | ||
362 | * subgraphs, which is also disallowed. [] | ||
363 | * | ||
364 | * Given such a row, it is always possible to make the | ||
365 | * disconnected edge connected and the connected edge | ||
366 | * disconnected without changing the state of any other edge. | ||
367 | * (This is easily seen by case analysis on the various tiles: | ||
368 | * left-pointing and right-pointing endpoints can be exchanged, | ||
369 | * likewise T-pieces, and a corner piece can select its | ||
370 | * horizontal connectivity independently of its vertical.) This | ||
371 | * yields a distinct valid solution. | ||
372 | * | ||
373 | * Thus, for _every_ row in which exactly one of the inner and | ||
374 | * outer edge is connected, there are two valid states for that | ||
375 | * row, and hence the total number of solutions of the puzzle | ||
376 | * is at least 2^(number of such rows), and in particular is at | ||
377 | * least 2 since there must be at least one such row. [] | ||
378 | */ | ||
379 | if (full && params->unique && params->wrapping && | ||
380 | (params->width == 2 || params->height == 2)) | ||
381 | return "No wrapping puzzle with a width or height of 2 can have" | ||
382 | " a unique solution"; | ||
383 | |||
384 | return NULL; | ||
385 | } | ||
386 | |||
387 | /* ---------------------------------------------------------------------- | ||
388 | * Solver used to assure solution uniqueness during generation. | ||
389 | */ | ||
390 | |||
391 | /* | ||
392 | * Test cases I used while debugging all this were | ||
393 | * | ||
394 | * ./net --generate 1 13x11w#12300 | ||
395 | * which expands under the non-unique grid generation rules to | ||
396 | * 13x11w:5eaade1bd222664436d5e2965c12656b1129dd825219e3274d558d5eb2dab5da18898e571d5a2987be79746bd95726c597447d6da96188c513add829da7681da954db113d3cd244 | ||
397 | * and has two ambiguous areas. | ||
398 | * | ||
399 | * An even better one is | ||
400 | * 13x11w#507896411361192 | ||
401 | * which expands to | ||
402 | * 13x11w:b7125b1aec598eb31bd58d82572bc11494e5dee4e8db2bdd29b88d41a16bdd996d2996ddec8c83741a1e8674e78328ba71737b8894a9271b1cd1399453d1952e43951d9b712822e | ||
403 | * and has an ambiguous area _and_ a situation where loop avoidance | ||
404 | * is a necessary deductive technique. | ||
405 | * | ||
406 | * Then there's | ||
407 | * 48x25w#820543338195187 | ||
408 | * becoming | ||
409 | * 48x25w:255989d14cdd185deaa753a93821a12edc1ab97943ac127e2685d7b8b3c48861b2192416139212b316eddd35de43714ebc7628d753db32e596284d9ec52c5a7dc1b4c811a655117d16dc28921b2b4161352cab1d89d18bc836b8b891d55ea4622a1251861b5bc9a8aa3e5bcd745c95229ca6c3b5e21d5832d397e917325793d7eb442dc351b2db2a52ba8e1651642275842d8871d5534aabc6d5b741aaa2d48ed2a7dbbb3151ddb49d5b9a7ed1ab98ee75d613d656dbba347bc514c84556b43a9bc65a3256ead792488b862a9d2a8a39b4255a4949ed7dbd79443292521265896b4399c95ede89d7c8c797a6a57791a849adea489359a158aa12e5dacce862b8333b7ebea7d344d1a3c53198864b73a9dedde7b663abb1b539e1e8853b1b7edb14a2a17ebaae4dbe63598a2e7e9a2dbdad415bc1d8cb88cbab5a8c82925732cd282e641ea3bd7d2c6e776de9117a26be86deb7c82c89524b122cb9397cd1acd2284e744ea62b9279bae85479ababe315c3ac29c431333395b24e6a1e3c43a2da42d4dce84aadd5b154aea555eaddcbd6e527d228c19388d9b424d94214555a7edbdeebe569d4a56dc51a86bd9963e377bb74752bd5eaa5761ba545e297b62a1bda46ab4aee423ad6c661311783cc18786d4289236563cb4a75ec67d481c14814994464cd1b87396dee63e5ab6e952cc584baa1d4c47cb557ec84dbb63d487c8728118673a166846dd3a4ebc23d6cb9c5827d96b4556e91899db32b517eda815ae271a8911bd745447121dc8d321557bc2a435ebec1bbac35b1a291669451174e6aa2218a4a9c5a6ca31ebc45d84e3a82c121e9ced7d55e9a | ||
410 | * which has a spot (far right) where slightly more complex loop | ||
411 | * avoidance is required. | ||
412 | */ | ||
413 | |||
414 | struct todo { | ||
415 | unsigned char *marked; | ||
416 | int *buffer; | ||
417 | int buflen; | ||
418 | int head, tail; | ||
419 | }; | ||
420 | |||
421 | static struct todo *todo_new(int maxsize) | ||
422 | { | ||
423 | struct todo *todo = snew(struct todo); | ||
424 | todo->marked = snewn(maxsize, unsigned char); | ||
425 | memset(todo->marked, 0, maxsize); | ||
426 | todo->buflen = maxsize + 1; | ||
427 | todo->buffer = snewn(todo->buflen, int); | ||
428 | todo->head = todo->tail = 0; | ||
429 | return todo; | ||
430 | } | ||
431 | |||
432 | static void todo_free(struct todo *todo) | ||
433 | { | ||
434 | sfree(todo->marked); | ||
435 | sfree(todo->buffer); | ||
436 | sfree(todo); | ||
437 | } | ||
438 | |||
439 | static void todo_add(struct todo *todo, int index) | ||
440 | { | ||
441 | if (todo->marked[index]) | ||
442 | return; /* already on the list */ | ||
443 | todo->marked[index] = TRUE; | ||
444 | todo->buffer[todo->tail++] = index; | ||
445 | if (todo->tail == todo->buflen) | ||
446 | todo->tail = 0; | ||
447 | } | ||
448 | |||
449 | static int todo_get(struct todo *todo) { | ||
450 | int ret; | ||
451 | |||
452 | if (todo->head == todo->tail) | ||
453 | return -1; /* list is empty */ | ||
454 | ret = todo->buffer[todo->head++]; | ||
455 | if (todo->head == todo->buflen) | ||
456 | todo->head = 0; | ||
457 | todo->marked[ret] = FALSE; | ||
458 | |||
459 | return ret; | ||
460 | } | ||
461 | |||
462 | static int net_solver(int w, int h, unsigned char *tiles, | ||
463 | unsigned char *barriers, int wrapping) | ||
464 | { | ||
465 | unsigned char *tilestate; | ||
466 | unsigned char *edgestate; | ||
467 | int *deadends; | ||
468 | int *equivalence; | ||
469 | struct todo *todo; | ||
470 | int i, j, x, y; | ||
471 | int area; | ||
472 | int done_something; | ||
473 | |||
474 | /* | ||
475 | * Set up the solver's data structures. | ||
476 | */ | ||
477 | |||
478 | /* | ||
479 | * tilestate stores the possible orientations of each tile. | ||
480 | * There are up to four of these, so we'll index the array in | ||
481 | * fours. tilestate[(y * w + x) * 4] and its three successive | ||
482 | * members give the possible orientations, clearing to 255 from | ||
483 | * the end as things are ruled out. | ||
484 | * | ||
485 | * In this loop we also count up the area of the grid (which is | ||
486 | * not _necessarily_ equal to w*h, because there might be one | ||
487 | * or more blank squares present. This will never happen in a | ||
488 | * grid generated _by_ this program, but it's worth keeping the | ||
489 | * solver as general as possible.) | ||
490 | */ | ||
491 | tilestate = snewn(w * h * 4, unsigned char); | ||
492 | area = 0; | ||
493 | for (i = 0; i < w*h; i++) { | ||
494 | tilestate[i * 4] = tiles[i] & 0xF; | ||
495 | for (j = 1; j < 4; j++) { | ||
496 | if (tilestate[i * 4 + j - 1] == 255 || | ||
497 | A(tilestate[i * 4 + j - 1]) == tilestate[i * 4]) | ||
498 | tilestate[i * 4 + j] = 255; | ||
499 | else | ||
500 | tilestate[i * 4 + j] = A(tilestate[i * 4 + j - 1]); | ||
501 | } | ||
502 | if (tiles[i] != 0) | ||
503 | area++; | ||
504 | } | ||
505 | |||
506 | /* | ||
507 | * edgestate stores the known state of each edge. It is 0 for | ||
508 | * unknown, 1 for open (connected) and 2 for closed (not | ||
509 | * connected). | ||
510 | * | ||
511 | * In principle we need only worry about each edge once each, | ||
512 | * but in fact it's easier to track each edge twice so that we | ||
513 | * can reference it from either side conveniently. Also I'm | ||
514 | * going to allocate _five_ bytes per tile, rather than the | ||
515 | * obvious four, so that I can index edgestate[(y*w+x) * 5 + d] | ||
516 | * where d is 1,2,4,8 and they never overlap. | ||
517 | */ | ||
518 | edgestate = snewn((w * h - 1) * 5 + 9, unsigned char); | ||
519 | memset(edgestate, 0, (w * h - 1) * 5 + 9); | ||
520 | |||
521 | /* | ||
522 | * deadends tracks which edges have dead ends on them. It is | ||
523 | * indexed by tile and direction: deadends[(y*w+x) * 5 + d] | ||
524 | * tells you whether heading out of tile (x,y) in direction d | ||
525 | * can reach a limited amount of the grid. Values are area+1 | ||
526 | * (no dead end known) or less than that (can reach _at most_ | ||
527 | * this many other tiles by heading this way out of this tile). | ||
528 | */ | ||
529 | deadends = snewn((w * h - 1) * 5 + 9, int); | ||
530 | for (i = 0; i < (w * h - 1) * 5 + 9; i++) | ||
531 | deadends[i] = area+1; | ||
532 | |||
533 | /* | ||
534 | * equivalence tracks which sets of tiles are known to be | ||
535 | * connected to one another, so we can avoid creating loops by | ||
536 | * linking together tiles which are already linked through | ||
537 | * another route. | ||
538 | * | ||
539 | * This is a disjoint set forest structure: equivalence[i] | ||
540 | * contains the index of another member of the equivalence | ||
541 | * class containing i, or contains i itself for precisely one | ||
542 | * member in each such class. To find a representative member | ||
543 | * of the equivalence class containing i, you keep replacing i | ||
544 | * with equivalence[i] until it stops changing; then you go | ||
545 | * _back_ along the same path and point everything on it | ||
546 | * directly at the representative member so as to speed up | ||
547 | * future searches. Then you test equivalence between tiles by | ||
548 | * finding the representative of each tile and seeing if | ||
549 | * they're the same; and you create new equivalence (merge | ||
550 | * classes) by finding the representative of each tile and | ||
551 | * setting equivalence[one]=the_other. | ||
552 | */ | ||
553 | equivalence = snew_dsf(w * h); | ||
554 | |||
555 | /* | ||
556 | * On a non-wrapping grid, we instantly know that all the edges | ||
557 | * round the edge are closed. | ||
558 | */ | ||
559 | if (!wrapping) { | ||
560 | for (i = 0; i < w; i++) { | ||
561 | edgestate[i * 5 + 2] = edgestate[((h-1) * w + i) * 5 + 8] = 2; | ||
562 | } | ||
563 | for (i = 0; i < h; i++) { | ||
564 | edgestate[(i * w + w-1) * 5 + 1] = edgestate[(i * w) * 5 + 4] = 2; | ||
565 | } | ||
566 | } | ||
567 | |||
568 | /* | ||
569 | * If we have barriers available, we can mark those edges as | ||
570 | * closed too. | ||
571 | */ | ||
572 | if (barriers) { | ||
573 | for (y = 0; y < h; y++) for (x = 0; x < w; x++) { | ||
574 | int d; | ||
575 | for (d = 1; d <= 8; d += d) { | ||
576 | if (barriers[y*w+x] & d) { | ||
577 | int x2, y2; | ||
578 | /* | ||
579 | * In principle the barrier list should already | ||
580 | * contain each barrier from each side, but | ||
581 | * let's not take chances with our internal | ||
582 | * consistency. | ||
583 | */ | ||
584 | OFFSETWH(x2, y2, x, y, d, w, h); | ||
585 | edgestate[(y*w+x) * 5 + d] = 2; | ||
586 | edgestate[(y2*w+x2) * 5 + F(d)] = 2; | ||
587 | } | ||
588 | } | ||
589 | } | ||
590 | } | ||
591 | |||
592 | /* | ||
593 | * Since most deductions made by this solver are local (the | ||
594 | * exception is loop avoidance, where joining two tiles | ||
595 | * together on one side of the grid can theoretically permit a | ||
596 | * fresh deduction on the other), we can address the scaling | ||
597 | * problem inherent in iterating repeatedly over the entire | ||
598 | * grid by instead working with a to-do list. | ||
599 | */ | ||
600 | todo = todo_new(w * h); | ||
601 | |||
602 | /* | ||
603 | * Main deductive loop. | ||
604 | */ | ||
605 | done_something = TRUE; /* prevent instant termination! */ | ||
606 | while (1) { | ||
607 | int index; | ||
608 | |||
609 | /* | ||
610 | * Take a tile index off the todo list and process it. | ||
611 | */ | ||
612 | index = todo_get(todo); | ||
613 | if (index == -1) { | ||
614 | /* | ||
615 | * If we have run out of immediate things to do, we | ||
616 | * have no choice but to scan the whole grid for | ||
617 | * longer-range things we've missed. Hence, I now add | ||
618 | * every square on the grid back on to the to-do list. | ||
619 | * I also set `done_something' to FALSE at this point; | ||
620 | * if we later come back here and find it still FALSE, | ||
621 | * we will know we've scanned the entire grid without | ||
622 | * finding anything new to do, and we can terminate. | ||
623 | */ | ||
624 | if (!done_something) | ||
625 | break; | ||
626 | for (i = 0; i < w*h; i++) | ||
627 | todo_add(todo, i); | ||
628 | done_something = FALSE; | ||
629 | |||
630 | index = todo_get(todo); | ||
631 | } | ||
632 | |||
633 | y = index / w; | ||
634 | x = index % w; | ||
635 | { | ||
636 | int d, ourclass = dsf_canonify(equivalence, y*w+x); | ||
637 | int deadendmax[9]; | ||
638 | |||
639 | deadendmax[1] = deadendmax[2] = deadendmax[4] = deadendmax[8] = 0; | ||
640 | |||
641 | for (i = j = 0; i < 4 && tilestate[(y*w+x) * 4 + i] != 255; i++) { | ||
642 | int valid; | ||
643 | int nnondeadends, nondeadends[4], deadendtotal; | ||
644 | int nequiv, equiv[5]; | ||
645 | int val = tilestate[(y*w+x) * 4 + i]; | ||
646 | |||
647 | valid = TRUE; | ||
648 | nnondeadends = deadendtotal = 0; | ||
649 | equiv[0] = ourclass; | ||
650 | nequiv = 1; | ||
651 | for (d = 1; d <= 8; d += d) { | ||
652 | /* | ||
653 | * Immediately rule out this orientation if it | ||
654 | * conflicts with any known edge. | ||
655 | */ | ||
656 | if ((edgestate[(y*w+x) * 5 + d] == 1 && !(val & d)) || | ||
657 | (edgestate[(y*w+x) * 5 + d] == 2 && (val & d))) | ||
658 | valid = FALSE; | ||
659 | |||
660 | if (val & d) { | ||
661 | /* | ||
662 | * Count up the dead-end statistics. | ||
663 | */ | ||
664 | if (deadends[(y*w+x) * 5 + d] <= area) { | ||
665 | deadendtotal += deadends[(y*w+x) * 5 + d]; | ||
666 | } else { | ||
667 | nondeadends[nnondeadends++] = d; | ||
668 | } | ||
669 | |||
670 | /* | ||
671 | * Ensure we aren't linking to any tiles, | ||
672 | * through edges not already known to be | ||
673 | * open, which create a loop. | ||
674 | */ | ||
675 | if (edgestate[(y*w+x) * 5 + d] == 0) { | ||
676 | int c, k, x2, y2; | ||
677 | |||
678 | OFFSETWH(x2, y2, x, y, d, w, h); | ||
679 | c = dsf_canonify(equivalence, y2*w+x2); | ||
680 | for (k = 0; k < nequiv; k++) | ||
681 | if (c == equiv[k]) | ||
682 | break; | ||
683 | if (k == nequiv) | ||
684 | equiv[nequiv++] = c; | ||
685 | else | ||
686 | valid = FALSE; | ||
687 | } | ||
688 | } | ||
689 | } | ||
690 | |||
691 | if (nnondeadends == 0) { | ||
692 | /* | ||
693 | * If this orientation links together dead-ends | ||
694 | * with a total area of less than the entire | ||
695 | * grid, it is invalid. | ||
696 | * | ||
697 | * (We add 1 to deadendtotal because of the | ||
698 | * tile itself, of course; one tile linking | ||
699 | * dead ends of size 2 and 3 forms a subnetwork | ||
700 | * with a total area of 6, not 5.) | ||
701 | */ | ||
702 | if (deadendtotal > 0 && deadendtotal+1 < area) | ||
703 | valid = FALSE; | ||
704 | } else if (nnondeadends == 1) { | ||
705 | /* | ||
706 | * If this orientation links together one or | ||
707 | * more dead-ends with precisely one | ||
708 | * non-dead-end, then we may have to mark that | ||
709 | * non-dead-end as a dead end going the other | ||
710 | * way. However, it depends on whether all | ||
711 | * other orientations share the same property. | ||
712 | */ | ||
713 | deadendtotal++; | ||
714 | if (deadendmax[nondeadends[0]] < deadendtotal) | ||
715 | deadendmax[nondeadends[0]] = deadendtotal; | ||
716 | } else { | ||
717 | /* | ||
718 | * If this orientation links together two or | ||
719 | * more non-dead-ends, then we can rule out the | ||
720 | * possibility of putting in new dead-end | ||
721 | * markings in those directions. | ||
722 | */ | ||
723 | int k; | ||
724 | for (k = 0; k < nnondeadends; k++) | ||
725 | deadendmax[nondeadends[k]] = area+1; | ||
726 | } | ||
727 | |||
728 | if (valid) | ||
729 | tilestate[(y*w+x) * 4 + j++] = val; | ||
730 | #ifdef SOLVER_DIAGNOSTICS | ||
731 | else | ||
732 | printf("ruling out orientation %x at %d,%d\n", val, x, y); | ||
733 | #endif | ||
734 | } | ||
735 | |||
736 | assert(j > 0); /* we can't lose _all_ possibilities! */ | ||
737 | |||
738 | if (j < i) { | ||
739 | done_something = TRUE; | ||
740 | |||
741 | /* | ||
742 | * We have ruled out at least one tile orientation. | ||
743 | * Make sure the rest are blanked. | ||
744 | */ | ||
745 | while (j < 4) | ||
746 | tilestate[(y*w+x) * 4 + j++] = 255; | ||
747 | } | ||
748 | |||
749 | /* | ||
750 | * Now go through the tile orientations again and see | ||
751 | * if we've deduced anything new about any edges. | ||
752 | */ | ||
753 | { | ||
754 | int a, o; | ||
755 | a = 0xF; o = 0; | ||
756 | |||
757 | for (i = 0; i < 4 && tilestate[(y*w+x) * 4 + i] != 255; i++) { | ||
758 | a &= tilestate[(y*w+x) * 4 + i]; | ||
759 | o |= tilestate[(y*w+x) * 4 + i]; | ||
760 | } | ||
761 | for (d = 1; d <= 8; d += d) | ||
762 | if (edgestate[(y*w+x) * 5 + d] == 0) { | ||
763 | int x2, y2, d2; | ||
764 | OFFSETWH(x2, y2, x, y, d, w, h); | ||
765 | d2 = F(d); | ||
766 | if (a & d) { | ||
767 | /* This edge is open in all orientations. */ | ||
768 | #ifdef SOLVER_DIAGNOSTICS | ||
769 | printf("marking edge %d,%d:%d open\n", x, y, d); | ||
770 | #endif | ||
771 | edgestate[(y*w+x) * 5 + d] = 1; | ||
772 | edgestate[(y2*w+x2) * 5 + d2] = 1; | ||
773 | dsf_merge(equivalence, y*w+x, y2*w+x2); | ||
774 | done_something = TRUE; | ||
775 | todo_add(todo, y2*w+x2); | ||
776 | } else if (!(o & d)) { | ||
777 | /* This edge is closed in all orientations. */ | ||
778 | #ifdef SOLVER_DIAGNOSTICS | ||
779 | printf("marking edge %d,%d:%d closed\n", x, y, d); | ||
780 | #endif | ||
781 | edgestate[(y*w+x) * 5 + d] = 2; | ||
782 | edgestate[(y2*w+x2) * 5 + d2] = 2; | ||
783 | done_something = TRUE; | ||
784 | todo_add(todo, y2*w+x2); | ||
785 | } | ||
786 | } | ||
787 | |||
788 | } | ||
789 | |||
790 | /* | ||
791 | * Now check the dead-end markers and see if any of | ||
792 | * them has lowered from the real ones. | ||
793 | */ | ||
794 | for (d = 1; d <= 8; d += d) { | ||
795 | int x2, y2, d2; | ||
796 | OFFSETWH(x2, y2, x, y, d, w, h); | ||
797 | d2 = F(d); | ||
798 | if (deadendmax[d] > 0 && | ||
799 | deadends[(y2*w+x2) * 5 + d2] > deadendmax[d]) { | ||
800 | #ifdef SOLVER_DIAGNOSTICS | ||
801 | printf("setting dead end value %d,%d:%d to %d\n", | ||
802 | x2, y2, d2, deadendmax[d]); | ||
803 | #endif | ||
804 | deadends[(y2*w+x2) * 5 + d2] = deadendmax[d]; | ||
805 | done_something = TRUE; | ||
806 | todo_add(todo, y2*w+x2); | ||
807 | } | ||
808 | } | ||
809 | |||
810 | } | ||
811 | } | ||
812 | |||
813 | /* | ||
814 | * Mark all completely determined tiles as locked. | ||
815 | */ | ||
816 | j = TRUE; | ||
817 | for (i = 0; i < w*h; i++) { | ||
818 | if (tilestate[i * 4 + 1] == 255) { | ||
819 | assert(tilestate[i * 4 + 0] != 255); | ||
820 | tiles[i] = tilestate[i * 4] | LOCKED; | ||
821 | } else { | ||
822 | tiles[i] &= ~LOCKED; | ||
823 | j = FALSE; | ||
824 | } | ||
825 | } | ||
826 | |||
827 | /* | ||
828 | * Free up working space. | ||
829 | */ | ||
830 | todo_free(todo); | ||
831 | sfree(tilestate); | ||
832 | sfree(edgestate); | ||
833 | sfree(deadends); | ||
834 | sfree(equivalence); | ||
835 | |||
836 | return j; | ||
837 | } | ||
838 | |||
839 | /* ---------------------------------------------------------------------- | ||
840 | * Randomly select a new game description. | ||
841 | */ | ||
842 | |||
843 | /* | ||
844 | * Function to randomly perturb an ambiguous section in a grid, to | ||
845 | * attempt to ensure unique solvability. | ||
846 | */ | ||
847 | static void perturb(int w, int h, unsigned char *tiles, int wrapping, | ||
848 | random_state *rs, int startx, int starty, int startd) | ||
849 | { | ||
850 | struct xyd *perimeter, *perim2, *loop[2], looppos[2]; | ||
851 | int nperim, perimsize, nloop[2], loopsize[2]; | ||
852 | int x, y, d, i; | ||
853 | |||
854 | /* | ||
855 | * We know that the tile at (startx,starty) is part of an | ||
856 | * ambiguous section, and we also know that its neighbour in | ||
857 | * direction startd is fully specified. We begin by tracing all | ||
858 | * the way round the ambiguous area. | ||
859 | */ | ||
860 | nperim = perimsize = 0; | ||
861 | perimeter = NULL; | ||
862 | x = startx; | ||
863 | y = starty; | ||
864 | d = startd; | ||
865 | #ifdef PERTURB_DIAGNOSTICS | ||
866 | printf("perturb %d,%d:%d\n", x, y, d); | ||
867 | #endif | ||
868 | do { | ||
869 | int x2, y2, d2; | ||
870 | |||
871 | if (nperim >= perimsize) { | ||
872 | perimsize = perimsize * 3 / 2 + 32; | ||
873 | perimeter = sresize(perimeter, perimsize, struct xyd); | ||
874 | } | ||
875 | perimeter[nperim].x = x; | ||
876 | perimeter[nperim].y = y; | ||
877 | perimeter[nperim].direction = d; | ||
878 | nperim++; | ||
879 | #ifdef PERTURB_DIAGNOSTICS | ||
880 | printf("perimeter: %d,%d:%d\n", x, y, d); | ||
881 | #endif | ||
882 | |||
883 | /* | ||
884 | * First, see if we can simply turn left from where we are | ||
885 | * and find another locked square. | ||
886 | */ | ||
887 | d2 = A(d); | ||
888 | OFFSETWH(x2, y2, x, y, d2, w, h); | ||
889 | if ((!wrapping && (abs(x2-x) > 1 || abs(y2-y) > 1)) || | ||
890 | (tiles[y2*w+x2] & LOCKED)) { | ||
891 | d = d2; | ||
892 | } else { | ||
893 | /* | ||
894 | * Failing that, step left into the new square and look | ||
895 | * in front of us. | ||
896 | */ | ||
897 | x = x2; | ||
898 | y = y2; | ||
899 | OFFSETWH(x2, y2, x, y, d, w, h); | ||
900 | if ((wrapping || (abs(x2-x) <= 1 && abs(y2-y) <= 1)) && | ||
901 | !(tiles[y2*w+x2] & LOCKED)) { | ||
902 | /* | ||
903 | * And failing _that_, we're going to have to step | ||
904 | * forward into _that_ square and look right at the | ||
905 | * same locked square as we started with. | ||
906 | */ | ||
907 | x = x2; | ||
908 | y = y2; | ||
909 | d = C(d); | ||
910 | } | ||
911 | } | ||
912 | |||
913 | } while (x != startx || y != starty || d != startd); | ||
914 | |||
915 | /* | ||
916 | * Our technique for perturbing this ambiguous area is to | ||
917 | * search round its edge for a join we can make: that is, an | ||
918 | * edge on the perimeter which is (a) not currently connected, | ||
919 | * and (b) connecting it would not yield a full cross on either | ||
920 | * side. Then we make that join, search round the network to | ||
921 | * find the loop thus constructed, and sever the loop at a | ||
922 | * randomly selected other point. | ||
923 | */ | ||
924 | perim2 = snewn(nperim, struct xyd); | ||
925 | memcpy(perim2, perimeter, nperim * sizeof(struct xyd)); | ||
926 | /* Shuffle the perimeter, so as to search it without directional bias. */ | ||
927 | shuffle(perim2, nperim, sizeof(*perim2), rs); | ||
928 | for (i = 0; i < nperim; i++) { | ||
929 | int x2, y2; | ||
930 | |||
931 | x = perim2[i].x; | ||
932 | y = perim2[i].y; | ||
933 | d = perim2[i].direction; | ||
934 | |||
935 | OFFSETWH(x2, y2, x, y, d, w, h); | ||
936 | if (!wrapping && (abs(x2-x) > 1 || abs(y2-y) > 1)) | ||
937 | continue; /* can't link across non-wrapping border */ | ||
938 | if (tiles[y*w+x] & d) | ||
939 | continue; /* already linked in this direction! */ | ||
940 | if (((tiles[y*w+x] | d) & 15) == 15) | ||
941 | continue; /* can't turn this tile into a cross */ | ||
942 | if (((tiles[y2*w+x2] | F(d)) & 15) == 15) | ||
943 | continue; /* can't turn other tile into a cross */ | ||
944 | |||
945 | /* | ||
946 | * We've found the point at which we're going to make a new | ||
947 | * link. | ||
948 | */ | ||
949 | #ifdef PERTURB_DIAGNOSTICS | ||
950 | printf("linking %d,%d:%d\n", x, y, d); | ||
951 | #endif | ||
952 | tiles[y*w+x] |= d; | ||
953 | tiles[y2*w+x2] |= F(d); | ||
954 | |||
955 | break; | ||
956 | } | ||
957 | sfree(perim2); | ||
958 | |||
959 | if (i == nperim) { | ||
960 | sfree(perimeter); | ||
961 | return; /* nothing we can do! */ | ||
962 | } | ||
963 | |||
964 | /* | ||
965 | * Now we've constructed a new link, we need to find the entire | ||
966 | * loop of which it is a part. | ||
967 | * | ||
968 | * In principle, this involves doing a complete search round | ||
969 | * the network. However, I anticipate that in the vast majority | ||
970 | * of cases the loop will be quite small, so what I'm going to | ||
971 | * do is make _two_ searches round the network in parallel, one | ||
972 | * keeping its metaphorical hand on the left-hand wall while | ||
973 | * the other keeps its hand on the right. As soon as one of | ||
974 | * them gets back to its starting point, I abandon the other. | ||
975 | */ | ||
976 | for (i = 0; i < 2; i++) { | ||
977 | loopsize[i] = nloop[i] = 0; | ||
978 | loop[i] = NULL; | ||
979 | looppos[i].x = x; | ||
980 | looppos[i].y = y; | ||
981 | looppos[i].direction = d; | ||
982 | } | ||
983 | while (1) { | ||
984 | for (i = 0; i < 2; i++) { | ||
985 | int x2, y2, j; | ||
986 | |||
987 | x = looppos[i].x; | ||
988 | y = looppos[i].y; | ||
989 | d = looppos[i].direction; | ||
990 | |||
991 | OFFSETWH(x2, y2, x, y, d, w, h); | ||
992 | |||
993 | /* | ||
994 | * Add this path segment to the loop, unless it exactly | ||
995 | * reverses the previous one on the loop in which case | ||
996 | * we take it away again. | ||
997 | */ | ||
998 | #ifdef PERTURB_DIAGNOSTICS | ||
999 | printf("looppos[%d] = %d,%d:%d\n", i, x, y, d); | ||
1000 | #endif | ||
1001 | if (nloop[i] > 0 && | ||
1002 | loop[i][nloop[i]-1].x == x2 && | ||
1003 | loop[i][nloop[i]-1].y == y2 && | ||
1004 | loop[i][nloop[i]-1].direction == F(d)) { | ||
1005 | #ifdef PERTURB_DIAGNOSTICS | ||
1006 | printf("removing path segment %d,%d:%d from loop[%d]\n", | ||
1007 | x2, y2, F(d), i); | ||
1008 | #endif | ||
1009 | nloop[i]--; | ||
1010 | } else { | ||
1011 | if (nloop[i] >= loopsize[i]) { | ||
1012 | loopsize[i] = loopsize[i] * 3 / 2 + 32; | ||
1013 | loop[i] = sresize(loop[i], loopsize[i], struct xyd); | ||
1014 | } | ||
1015 | #ifdef PERTURB_DIAGNOSTICS | ||
1016 | printf("adding path segment %d,%d:%d to loop[%d]\n", | ||
1017 | x, y, d, i); | ||
1018 | #endif | ||
1019 | loop[i][nloop[i]++] = looppos[i]; | ||
1020 | } | ||
1021 | |||
1022 | #ifdef PERTURB_DIAGNOSTICS | ||
1023 | printf("tile at new location is %x\n", tiles[y2*w+x2] & 0xF); | ||
1024 | #endif | ||
1025 | d = F(d); | ||
1026 | for (j = 0; j < 4; j++) { | ||
1027 | if (i == 0) | ||
1028 | d = A(d); | ||
1029 | else | ||
1030 | d = C(d); | ||
1031 | #ifdef PERTURB_DIAGNOSTICS | ||
1032 | printf("trying dir %d\n", d); | ||
1033 | #endif | ||
1034 | if (tiles[y2*w+x2] & d) { | ||
1035 | looppos[i].x = x2; | ||
1036 | looppos[i].y = y2; | ||
1037 | looppos[i].direction = d; | ||
1038 | break; | ||
1039 | } | ||
1040 | } | ||
1041 | |||
1042 | assert(j < 4); | ||
1043 | assert(nloop[i] > 0); | ||
1044 | |||
1045 | if (looppos[i].x == loop[i][0].x && | ||
1046 | looppos[i].y == loop[i][0].y && | ||
1047 | looppos[i].direction == loop[i][0].direction) { | ||
1048 | #ifdef PERTURB_DIAGNOSTICS | ||
1049 | printf("loop %d finished tracking\n", i); | ||
1050 | #endif | ||
1051 | |||
1052 | /* | ||
1053 | * Having found our loop, we now sever it at a | ||
1054 | * randomly chosen point - absolutely any will do - | ||
1055 | * which is not the one we joined it at to begin | ||
1056 | * with. Conveniently, the one we joined it at is | ||
1057 | * loop[i][0], so we just avoid that one. | ||
1058 | */ | ||
1059 | j = random_upto(rs, nloop[i]-1) + 1; | ||
1060 | x = loop[i][j].x; | ||
1061 | y = loop[i][j].y; | ||
1062 | d = loop[i][j].direction; | ||
1063 | OFFSETWH(x2, y2, x, y, d, w, h); | ||
1064 | tiles[y*w+x] &= ~d; | ||
1065 | tiles[y2*w+x2] &= ~F(d); | ||
1066 | |||
1067 | break; | ||
1068 | } | ||
1069 | } | ||
1070 | if (i < 2) | ||
1071 | break; | ||
1072 | } | ||
1073 | sfree(loop[0]); | ||
1074 | sfree(loop[1]); | ||
1075 | |||
1076 | /* | ||
1077 | * Finally, we must mark the entire disputed section as locked, | ||
1078 | * to prevent the perturb function being called on it multiple | ||
1079 | * times. | ||
1080 | * | ||
1081 | * To do this, we _sort_ the perimeter of the area. The | ||
1082 | * existing xyd_cmp function will arrange things into columns | ||
1083 | * for us, in such a way that each column has the edges in | ||
1084 | * vertical order. Then we can work down each column and fill | ||
1085 | * in all the squares between an up edge and a down edge. | ||
1086 | */ | ||
1087 | qsort(perimeter, nperim, sizeof(struct xyd), xyd_cmp); | ||
1088 | x = y = -1; | ||
1089 | for (i = 0; i <= nperim; i++) { | ||
1090 | if (i == nperim || perimeter[i].x > x) { | ||
1091 | /* | ||
1092 | * Fill in everything from the last Up edge to the | ||
1093 | * bottom of the grid, if necessary. | ||
1094 | */ | ||
1095 | if (x != -1) { | ||
1096 | while (y < h) { | ||
1097 | #ifdef PERTURB_DIAGNOSTICS | ||
1098 | printf("resolved: locking tile %d,%d\n", x, y); | ||
1099 | #endif | ||
1100 | tiles[y * w + x] |= LOCKED; | ||
1101 | y++; | ||
1102 | } | ||
1103 | x = y = -1; | ||
1104 | } | ||
1105 | |||
1106 | if (i == nperim) | ||
1107 | break; | ||
1108 | |||
1109 | x = perimeter[i].x; | ||
1110 | y = 0; | ||
1111 | } | ||
1112 | |||
1113 | if (perimeter[i].direction == U) { | ||
1114 | x = perimeter[i].x; | ||
1115 | y = perimeter[i].y; | ||
1116 | } else if (perimeter[i].direction == D) { | ||
1117 | /* | ||
1118 | * Fill in everything from the last Up edge to here. | ||
1119 | */ | ||
1120 | assert(x == perimeter[i].x && y <= perimeter[i].y); | ||
1121 | while (y <= perimeter[i].y) { | ||
1122 | #ifdef PERTURB_DIAGNOSTICS | ||
1123 | printf("resolved: locking tile %d,%d\n", x, y); | ||
1124 | #endif | ||
1125 | tiles[y * w + x] |= LOCKED; | ||
1126 | y++; | ||
1127 | } | ||
1128 | x = y = -1; | ||
1129 | } | ||
1130 | } | ||
1131 | |||
1132 | sfree(perimeter); | ||
1133 | } | ||
1134 | |||
1135 | static int *compute_loops_inner(int w, int h, int wrapping, | ||
1136 | const unsigned char *tiles, | ||
1137 | const unsigned char *barriers); | ||
1138 | |||
1139 | static char *new_game_desc(const game_params *params, random_state *rs, | ||
1140 | char **aux, int interactive) | ||
1141 | { | ||
1142 | tree234 *possibilities, *barriertree; | ||
1143 | int w, h, x, y, cx, cy, nbarriers; | ||
1144 | unsigned char *tiles, *barriers; | ||
1145 | char *desc, *p; | ||
1146 | |||
1147 | w = params->width; | ||
1148 | h = params->height; | ||
1149 | |||
1150 | cx = w / 2; | ||
1151 | cy = h / 2; | ||
1152 | |||
1153 | tiles = snewn(w * h, unsigned char); | ||
1154 | barriers = snewn(w * h, unsigned char); | ||
1155 | |||
1156 | begin_generation: | ||
1157 | |||
1158 | memset(tiles, 0, w * h); | ||
1159 | memset(barriers, 0, w * h); | ||
1160 | |||
1161 | /* | ||
1162 | * Construct the unshuffled grid. | ||
1163 | * | ||
1164 | * To do this, we simply start at the centre point, repeatedly | ||
1165 | * choose a random possibility out of the available ways to | ||
1166 | * extend a used square into an unused one, and do it. After | ||
1167 | * extending the third line out of a square, we remove the | ||
1168 | * fourth from the possibilities list to avoid any full-cross | ||
1169 | * squares (which would make the game too easy because they | ||
1170 | * only have one orientation). | ||
1171 | * | ||
1172 | * The slightly worrying thing is the avoidance of full-cross | ||
1173 | * squares. Can this cause our unsophisticated construction | ||
1174 | * algorithm to paint itself into a corner, by getting into a | ||
1175 | * situation where there are some unreached squares and the | ||
1176 | * only way to reach any of them is to extend a T-piece into a | ||
1177 | * full cross? | ||
1178 | * | ||
1179 | * Answer: no it can't, and here's a proof. | ||
1180 | * | ||
1181 | * Any contiguous group of such unreachable squares must be | ||
1182 | * surrounded on _all_ sides by T-pieces pointing away from the | ||
1183 | * group. (If not, then there is a square which can be extended | ||
1184 | * into one of the `unreachable' ones, and so it wasn't | ||
1185 | * unreachable after all.) In particular, this implies that | ||
1186 | * each contiguous group of unreachable squares must be | ||
1187 | * rectangular in shape (any deviation from that yields a | ||
1188 | * non-T-piece next to an `unreachable' square). | ||
1189 | * | ||
1190 | * So we have a rectangle of unreachable squares, with T-pieces | ||
1191 | * forming a solid border around the rectangle. The corners of | ||
1192 | * that border must be connected (since every tile connects all | ||
1193 | * the lines arriving in it), and therefore the border must | ||
1194 | * form a closed loop around the rectangle. | ||
1195 | * | ||
1196 | * But this can't have happened in the first place, since we | ||
1197 | * _know_ we've avoided creating closed loops! Hence, no such | ||
1198 | * situation can ever arise, and the naive grid construction | ||
1199 | * algorithm will guaranteeably result in a complete grid | ||
1200 | * containing no unreached squares, no full crosses _and_ no | ||
1201 | * closed loops. [] | ||
1202 | */ | ||
1203 | possibilities = newtree234(xyd_cmp_nc); | ||
1204 | |||
1205 | if (cx+1 < w) | ||
1206 | add234(possibilities, new_xyd(cx, cy, R)); | ||
1207 | if (cy-1 >= 0) | ||
1208 | add234(possibilities, new_xyd(cx, cy, U)); | ||
1209 | if (cx-1 >= 0) | ||
1210 | add234(possibilities, new_xyd(cx, cy, L)); | ||
1211 | if (cy+1 < h) | ||
1212 | add234(possibilities, new_xyd(cx, cy, D)); | ||
1213 | |||
1214 | while (count234(possibilities) > 0) { | ||
1215 | int i; | ||
1216 | struct xyd *xyd; | ||
1217 | int x1, y1, d1, x2, y2, d2, d; | ||
1218 | |||
1219 | /* | ||
1220 | * Extract a randomly chosen possibility from the list. | ||
1221 | */ | ||
1222 | i = random_upto(rs, count234(possibilities)); | ||
1223 | xyd = delpos234(possibilities, i); | ||
1224 | x1 = xyd->x; | ||
1225 | y1 = xyd->y; | ||
1226 | d1 = xyd->direction; | ||
1227 | sfree(xyd); | ||
1228 | |||
1229 | OFFSET(x2, y2, x1, y1, d1, params); | ||
1230 | d2 = F(d1); | ||
1231 | #ifdef GENERATION_DIAGNOSTICS | ||
1232 | printf("picked (%d,%d,%c) <-> (%d,%d,%c)\n", | ||
1233 | x1, y1, "0RU3L567D9abcdef"[d1], x2, y2, "0RU3L567D9abcdef"[d2]); | ||
1234 | #endif | ||
1235 | |||
1236 | /* | ||
1237 | * Make the connection. (We should be moving to an as yet | ||
1238 | * unused tile.) | ||
1239 | */ | ||
1240 | index(params, tiles, x1, y1) |= d1; | ||
1241 | assert(index(params, tiles, x2, y2) == 0); | ||
1242 | index(params, tiles, x2, y2) |= d2; | ||
1243 | |||
1244 | /* | ||
1245 | * If we have created a T-piece, remove its last | ||
1246 | * possibility. | ||
1247 | */ | ||
1248 | if (COUNT(index(params, tiles, x1, y1)) == 3) { | ||
1249 | struct xyd xyd1, *xydp; | ||
1250 | |||
1251 | xyd1.x = x1; | ||
1252 | xyd1.y = y1; | ||
1253 | xyd1.direction = 0x0F ^ index(params, tiles, x1, y1); | ||
1254 | |||
1255 | xydp = find234(possibilities, &xyd1, NULL); | ||
1256 | |||
1257 | if (xydp) { | ||
1258 | #ifdef GENERATION_DIAGNOSTICS | ||
1259 | printf("T-piece; removing (%d,%d,%c)\n", | ||
1260 | xydp->x, xydp->y, "0RU3L567D9abcdef"[xydp->direction]); | ||
1261 | #endif | ||
1262 | del234(possibilities, xydp); | ||
1263 | sfree(xydp); | ||
1264 | } | ||
1265 | } | ||
1266 | |||
1267 | /* | ||
1268 | * Remove all other possibilities that were pointing at the | ||
1269 | * tile we've just moved into. | ||
1270 | */ | ||
1271 | for (d = 1; d < 0x10; d <<= 1) { | ||
1272 | int x3, y3, d3; | ||
1273 | struct xyd xyd1, *xydp; | ||
1274 | |||
1275 | OFFSET(x3, y3, x2, y2, d, params); | ||
1276 | d3 = F(d); | ||
1277 | |||
1278 | xyd1.x = x3; | ||
1279 | xyd1.y = y3; | ||
1280 | xyd1.direction = d3; | ||
1281 | |||
1282 | xydp = find234(possibilities, &xyd1, NULL); | ||
1283 | |||
1284 | if (xydp) { | ||
1285 | #ifdef GENERATION_DIAGNOSTICS | ||
1286 | printf("Loop avoidance; removing (%d,%d,%c)\n", | ||
1287 | xydp->x, xydp->y, "0RU3L567D9abcdef"[xydp->direction]); | ||
1288 | #endif | ||
1289 | del234(possibilities, xydp); | ||
1290 | sfree(xydp); | ||
1291 | } | ||
1292 | } | ||
1293 | |||
1294 | /* | ||
1295 | * Add new possibilities to the list for moving _out_ of | ||
1296 | * the tile we have just moved into. | ||
1297 | */ | ||
1298 | for (d = 1; d < 0x10; d <<= 1) { | ||
1299 | int x3, y3; | ||
1300 | |||
1301 | if (d == d2) | ||
1302 | continue; /* we've got this one already */ | ||
1303 | |||
1304 | if (!params->wrapping) { | ||
1305 | if (d == U && y2 == 0) | ||
1306 | continue; | ||
1307 | if (d == D && y2 == h-1) | ||
1308 | continue; | ||
1309 | if (d == L && x2 == 0) | ||
1310 | continue; | ||
1311 | if (d == R && x2 == w-1) | ||
1312 | continue; | ||
1313 | } | ||
1314 | |||
1315 | OFFSET(x3, y3, x2, y2, d, params); | ||
1316 | |||
1317 | if (index(params, tiles, x3, y3)) | ||
1318 | continue; /* this would create a loop */ | ||
1319 | |||
1320 | #ifdef GENERATION_DIAGNOSTICS | ||
1321 | printf("New frontier; adding (%d,%d,%c)\n", | ||
1322 | x2, y2, "0RU3L567D9abcdef"[d]); | ||
1323 | #endif | ||
1324 | add234(possibilities, new_xyd(x2, y2, d)); | ||
1325 | } | ||
1326 | } | ||
1327 | /* Having done that, we should have no possibilities remaining. */ | ||
1328 | assert(count234(possibilities) == 0); | ||
1329 | freetree234(possibilities); | ||
1330 | |||
1331 | if (params->unique) { | ||
1332 | int prevn = -1; | ||
1333 | |||
1334 | /* | ||
1335 | * Run the solver to check unique solubility. | ||
1336 | */ | ||
1337 | while (!net_solver(w, h, tiles, NULL, params->wrapping)) { | ||
1338 | int n = 0; | ||
1339 | |||
1340 | /* | ||
1341 | * We expect (in most cases) that most of the grid will | ||
1342 | * be uniquely specified already, and the remaining | ||
1343 | * ambiguous sections will be small and separate. So | ||
1344 | * our strategy is to find each individual such | ||
1345 | * section, and perform a perturbation on the network | ||
1346 | * in that area. | ||
1347 | */ | ||
1348 | for (y = 0; y < h; y++) for (x = 0; x < w; x++) { | ||
1349 | if (x+1 < w && ((tiles[y*w+x] ^ tiles[y*w+x+1]) & LOCKED)) { | ||
1350 | n++; | ||
1351 | if (tiles[y*w+x] & LOCKED) | ||
1352 | perturb(w, h, tiles, params->wrapping, rs, x+1, y, L); | ||
1353 | else | ||
1354 | perturb(w, h, tiles, params->wrapping, rs, x, y, R); | ||
1355 | } | ||
1356 | if (y+1 < h && ((tiles[y*w+x] ^ tiles[(y+1)*w+x]) & LOCKED)) { | ||
1357 | n++; | ||
1358 | if (tiles[y*w+x] & LOCKED) | ||
1359 | perturb(w, h, tiles, params->wrapping, rs, x, y+1, U); | ||
1360 | else | ||
1361 | perturb(w, h, tiles, params->wrapping, rs, x, y, D); | ||
1362 | } | ||
1363 | } | ||
1364 | |||
1365 | /* | ||
1366 | * Now n counts the number of ambiguous sections we | ||
1367 | * have fiddled with. If we haven't managed to decrease | ||
1368 | * it from the last time we ran the solver, give up and | ||
1369 | * regenerate the entire grid. | ||
1370 | */ | ||
1371 | if (prevn != -1 && prevn <= n) | ||
1372 | goto begin_generation; /* (sorry) */ | ||
1373 | |||
1374 | prevn = n; | ||
1375 | } | ||
1376 | |||
1377 | /* | ||
1378 | * The solver will have left a lot of LOCKED bits lying | ||
1379 | * around in the tiles array. Remove them. | ||
1380 | */ | ||
1381 | for (x = 0; x < w*h; x++) | ||
1382 | tiles[x] &= ~LOCKED; | ||
1383 | } | ||
1384 | |||
1385 | /* | ||
1386 | * Now compute a list of the possible barrier locations. | ||
1387 | */ | ||
1388 | barriertree = newtree234(xyd_cmp_nc); | ||
1389 | for (y = 0; y < h; y++) { | ||
1390 | for (x = 0; x < w; x++) { | ||
1391 | |||
1392 | if (!(index(params, tiles, x, y) & R) && | ||
1393 | (params->wrapping || x < w-1)) | ||
1394 | add234(barriertree, new_xyd(x, y, R)); | ||
1395 | if (!(index(params, tiles, x, y) & D) && | ||
1396 | (params->wrapping || y < h-1)) | ||
1397 | add234(barriertree, new_xyd(x, y, D)); | ||
1398 | } | ||
1399 | } | ||
1400 | |||
1401 | /* | ||
1402 | * Save the unshuffled grid in aux. | ||
1403 | */ | ||
1404 | { | ||
1405 | char *solution; | ||
1406 | int i; | ||
1407 | |||
1408 | solution = snewn(w * h + 1, char); | ||
1409 | for (i = 0; i < w * h; i++) | ||
1410 | solution[i] = "0123456789abcdef"[tiles[i] & 0xF]; | ||
1411 | solution[w*h] = '\0'; | ||
1412 | |||
1413 | *aux = solution; | ||
1414 | } | ||
1415 | |||
1416 | /* | ||
1417 | * Now shuffle the grid. | ||
1418 | * | ||
1419 | * In order to avoid accidentally generating an already-solved | ||
1420 | * grid, we will reshuffle as necessary to ensure that at least | ||
1421 | * one edge has a mismatched connection. | ||
1422 | * | ||
1423 | * This can always be done, since validate_params() enforces a | ||
1424 | * grid area of at least 2 and our generator never creates | ||
1425 | * either type of rotationally invariant tile (cross and | ||
1426 | * blank). Hence there must be at least one edge separating | ||
1427 | * distinct tiles, and it must be possible to find orientations | ||
1428 | * of those tiles such that one tile is trying to connect | ||
1429 | * through that edge and the other is not. | ||
1430 | * | ||
1431 | * (We could be more subtle, and allow the shuffle to generate | ||
1432 | * a grid in which all tiles match up locally and the only | ||
1433 | * criterion preventing the grid from being already solved is | ||
1434 | * connectedness. However, that would take more effort, and | ||
1435 | * it's easier to simply make sure every grid is _obviously_ | ||
1436 | * not solved.) | ||
1437 | * | ||
1438 | * We also require that our shuffle produces no loops in the | ||
1439 | * initial grid state, because it's a bit rude to light up a 'HEY, | ||
1440 | * YOU DID SOMETHING WRONG!' indicator when the user hasn't even | ||
1441 | * had a chance to do _anything_ yet. This also is possible just | ||
1442 | * by retrying the whole shuffle on failure, because it's clear | ||
1443 | * that at least one non-solved shuffle with no loops must exist. | ||
1444 | * (Proof: take the _solved_ state of the puzzle, and rotate one | ||
1445 | * endpoint.) | ||
1446 | */ | ||
1447 | while (1) { | ||
1448 | int mismatches, prev_loopsquares, this_loopsquares, i; | ||
1449 | int *loops; | ||
1450 | |||
1451 | shuffle: | ||
1452 | for (y = 0; y < h; y++) { | ||
1453 | for (x = 0; x < w; x++) { | ||
1454 | int orig = index(params, tiles, x, y); | ||
1455 | int rot = random_upto(rs, 4); | ||
1456 | index(params, tiles, x, y) = ROT(orig, rot); | ||
1457 | } | ||
1458 | } | ||
1459 | |||
1460 | /* | ||
1461 | * Check for loops, and try to fix them by reshuffling just | ||
1462 | * the squares involved. | ||
1463 | */ | ||
1464 | prev_loopsquares = w*h+1; | ||
1465 | while (1) { | ||
1466 | loops = compute_loops_inner(w, h, params->wrapping, tiles, NULL); | ||
1467 | this_loopsquares = 0; | ||
1468 | for (i = 0; i < w*h; i++) { | ||
1469 | if (loops[i]) { | ||
1470 | int orig = tiles[i]; | ||
1471 | int rot = random_upto(rs, 4); | ||
1472 | tiles[i] = ROT(orig, rot); | ||
1473 | this_loopsquares++; | ||
1474 | } | ||
1475 | } | ||
1476 | sfree(loops); | ||
1477 | if (this_loopsquares > prev_loopsquares) { | ||
1478 | /* | ||
1479 | * We're increasing rather than reducing the number of | ||
1480 | * loops. Give up and go back to the full shuffle. | ||
1481 | */ | ||
1482 | goto shuffle; | ||
1483 | } | ||
1484 | if (this_loopsquares == 0) | ||
1485 | break; | ||
1486 | prev_loopsquares = this_loopsquares; | ||
1487 | } | ||
1488 | |||
1489 | mismatches = 0; | ||
1490 | /* | ||
1491 | * I can't even be bothered to check for mismatches across | ||
1492 | * a wrapping edge, so I'm just going to enforce that there | ||
1493 | * must be a mismatch across a non-wrapping edge, which is | ||
1494 | * still always possible. | ||
1495 | */ | ||
1496 | for (y = 0; y < h; y++) for (x = 0; x < w; x++) { | ||
1497 | if (x+1 < w && ((ROT(index(params, tiles, x, y), 2) ^ | ||
1498 | index(params, tiles, x+1, y)) & L)) | ||
1499 | mismatches++; | ||
1500 | if (y+1 < h && ((ROT(index(params, tiles, x, y), 2) ^ | ||
1501 | index(params, tiles, x, y+1)) & U)) | ||
1502 | mismatches++; | ||
1503 | } | ||
1504 | |||
1505 | if (mismatches == 0) | ||
1506 | continue; | ||
1507 | |||
1508 | /* OK. */ | ||
1509 | break; | ||
1510 | } | ||
1511 | |||
1512 | /* | ||
1513 | * And now choose barrier locations. (We carefully do this | ||
1514 | * _after_ shuffling, so that changing the barrier rate in the | ||
1515 | * params while keeping the random seed the same will give the | ||
1516 | * same shuffled grid and _only_ change the barrier locations. | ||
1517 | * Also the way we choose barrier locations, by repeatedly | ||
1518 | * choosing one possibility from the list until we have enough, | ||
1519 | * is designed to ensure that raising the barrier rate while | ||
1520 | * keeping the seed the same will provide a superset of the | ||
1521 | * previous barrier set - i.e. if you ask for 10 barriers, and | ||
1522 | * then decide that's still too hard and ask for 20, you'll get | ||
1523 | * the original 10 plus 10 more, rather than getting 20 new | ||
1524 | * ones and the chance of remembering your first 10.) | ||
1525 | */ | ||
1526 | nbarriers = (int)(params->barrier_probability * count234(barriertree)); | ||
1527 | assert(nbarriers >= 0 && nbarriers <= count234(barriertree)); | ||
1528 | |||
1529 | while (nbarriers > 0) { | ||
1530 | int i; | ||
1531 | struct xyd *xyd; | ||
1532 | int x1, y1, d1, x2, y2, d2; | ||
1533 | |||
1534 | /* | ||
1535 | * Extract a randomly chosen barrier from the list. | ||
1536 | */ | ||
1537 | i = random_upto(rs, count234(barriertree)); | ||
1538 | xyd = delpos234(barriertree, i); | ||
1539 | |||
1540 | assert(xyd != NULL); | ||
1541 | |||
1542 | x1 = xyd->x; | ||
1543 | y1 = xyd->y; | ||
1544 | d1 = xyd->direction; | ||
1545 | sfree(xyd); | ||
1546 | |||
1547 | OFFSET(x2, y2, x1, y1, d1, params); | ||
1548 | d2 = F(d1); | ||
1549 | |||
1550 | index(params, barriers, x1, y1) |= d1; | ||
1551 | index(params, barriers, x2, y2) |= d2; | ||
1552 | |||
1553 | nbarriers--; | ||
1554 | } | ||
1555 | |||
1556 | /* | ||
1557 | * Clean up the rest of the barrier list. | ||
1558 | */ | ||
1559 | { | ||
1560 | struct xyd *xyd; | ||
1561 | |||
1562 | while ( (xyd = delpos234(barriertree, 0)) != NULL) | ||
1563 | sfree(xyd); | ||
1564 | |||
1565 | freetree234(barriertree); | ||
1566 | } | ||
1567 | |||
1568 | /* | ||
1569 | * Finally, encode the grid into a string game description. | ||
1570 | * | ||
1571 | * My syntax is extremely simple: each square is encoded as a | ||
1572 | * hex digit in which bit 0 means a connection on the right, | ||
1573 | * bit 1 means up, bit 2 left and bit 3 down. (i.e. the same | ||
1574 | * encoding as used internally). Each digit is followed by | ||
1575 | * optional barrier indicators: `v' means a vertical barrier to | ||
1576 | * the right of it, and `h' means a horizontal barrier below | ||
1577 | * it. | ||
1578 | */ | ||
1579 | desc = snewn(w * h * 3 + 1, char); | ||
1580 | p = desc; | ||
1581 | for (y = 0; y < h; y++) { | ||
1582 | for (x = 0; x < w; x++) { | ||
1583 | *p++ = "0123456789abcdef"[index(params, tiles, x, y)]; | ||
1584 | if ((params->wrapping || x < w-1) && | ||
1585 | (index(params, barriers, x, y) & R)) | ||
1586 | *p++ = 'v'; | ||
1587 | if ((params->wrapping || y < h-1) && | ||
1588 | (index(params, barriers, x, y) & D)) | ||
1589 | *p++ = 'h'; | ||
1590 | } | ||
1591 | } | ||
1592 | assert(p - desc <= w*h*3); | ||
1593 | *p = '\0'; | ||
1594 | |||
1595 | sfree(tiles); | ||
1596 | sfree(barriers); | ||
1597 | |||
1598 | return desc; | ||
1599 | } | ||
1600 | |||
1601 | static char *validate_desc(const game_params *params, const char *desc) | ||
1602 | { | ||
1603 | int w = params->width, h = params->height; | ||
1604 | int i; | ||
1605 | |||
1606 | for (i = 0; i < w*h; i++) { | ||
1607 | if (*desc >= '0' && *desc <= '9') | ||
1608 | /* OK */; | ||
1609 | else if (*desc >= 'a' && *desc <= 'f') | ||
1610 | /* OK */; | ||
1611 | else if (*desc >= 'A' && *desc <= 'F') | ||
1612 | /* OK */; | ||
1613 | else if (!*desc) | ||
1614 | return "Game description shorter than expected"; | ||
1615 | else | ||
1616 | return "Game description contained unexpected character"; | ||
1617 | desc++; | ||
1618 | while (*desc == 'h' || *desc == 'v') | ||
1619 | desc++; | ||
1620 | } | ||
1621 | if (*desc) | ||
1622 | return "Game description longer than expected"; | ||
1623 | |||
1624 | return NULL; | ||
1625 | } | ||
1626 | |||
1627 | /* ---------------------------------------------------------------------- | ||
1628 | * Construct an initial game state, given a description and parameters. | ||
1629 | */ | ||
1630 | |||
1631 | static game_state *new_game(midend *me, const game_params *params, | ||
1632 | const char *desc) | ||
1633 | { | ||
1634 | game_state *state; | ||
1635 | int w, h, x, y; | ||
1636 | |||
1637 | assert(params->width > 0 && params->height > 0); | ||
1638 | assert(params->width > 1 || params->height > 1); | ||
1639 | |||
1640 | /* | ||
1641 | * Create a blank game state. | ||
1642 | */ | ||
1643 | state = snew(game_state); | ||
1644 | w = state->width = params->width; | ||
1645 | h = state->height = params->height; | ||
1646 | state->wrapping = params->wrapping; | ||
1647 | state->last_rotate_dir = state->last_rotate_x = state->last_rotate_y = 0; | ||
1648 | state->completed = state->used_solve = FALSE; | ||
1649 | state->tiles = snewn(state->width * state->height, unsigned char); | ||
1650 | memset(state->tiles, 0, state->width * state->height); | ||
1651 | state->barriers = snewn(state->width * state->height, unsigned char); | ||
1652 | memset(state->barriers, 0, state->width * state->height); | ||
1653 | |||
1654 | /* | ||
1655 | * Parse the game description into the grid. | ||
1656 | */ | ||
1657 | for (y = 0; y < h; y++) { | ||
1658 | for (x = 0; x < w; x++) { | ||
1659 | if (*desc >= '0' && *desc <= '9') | ||
1660 | tile(state, x, y) = *desc - '0'; | ||
1661 | else if (*desc >= 'a' && *desc <= 'f') | ||
1662 | tile(state, x, y) = *desc - 'a' + 10; | ||
1663 | else if (*desc >= 'A' && *desc <= 'F') | ||
1664 | tile(state, x, y) = *desc - 'A' + 10; | ||
1665 | if (*desc) | ||
1666 | desc++; | ||
1667 | while (*desc == 'h' || *desc == 'v') { | ||
1668 | int x2, y2, d1, d2; | ||
1669 | if (*desc == 'v') | ||
1670 | d1 = R; | ||
1671 | else | ||
1672 | d1 = D; | ||
1673 | |||
1674 | OFFSET(x2, y2, x, y, d1, state); | ||
1675 | d2 = F(d1); | ||
1676 | |||
1677 | barrier(state, x, y) |= d1; | ||
1678 | barrier(state, x2, y2) |= d2; | ||
1679 | |||
1680 | desc++; | ||
1681 | } | ||
1682 | } | ||
1683 | } | ||
1684 | |||
1685 | /* | ||
1686 | * Set up border barriers if this is a non-wrapping game. | ||
1687 | */ | ||
1688 | if (!state->wrapping) { | ||
1689 | for (x = 0; x < state->width; x++) { | ||
1690 | barrier(state, x, 0) |= U; | ||
1691 | barrier(state, x, state->height-1) |= D; | ||
1692 | } | ||
1693 | for (y = 0; y < state->height; y++) { | ||
1694 | barrier(state, 0, y) |= L; | ||
1695 | barrier(state, state->width-1, y) |= R; | ||
1696 | } | ||
1697 | } else { | ||
1698 | /* | ||
1699 | * We check whether this is de-facto a non-wrapping game | ||
1700 | * despite the parameters, in case we were passed the | ||
1701 | * description of a non-wrapping game. This is so that we | ||
1702 | * can change some aspects of the UI behaviour. | ||
1703 | */ | ||
1704 | state->wrapping = FALSE; | ||
1705 | for (x = 0; x < state->width; x++) | ||
1706 | if (!(barrier(state, x, 0) & U) || | ||
1707 | !(barrier(state, x, state->height-1) & D)) | ||
1708 | state->wrapping = TRUE; | ||
1709 | for (y = 0; y < state->height; y++) | ||
1710 | if (!(barrier(state, 0, y) & L) || | ||
1711 | !(barrier(state, state->width-1, y) & R)) | ||
1712 | state->wrapping = TRUE; | ||
1713 | } | ||
1714 | |||
1715 | return state; | ||
1716 | } | ||
1717 | |||
1718 | static game_state *dup_game(const game_state *state) | ||
1719 | { | ||
1720 | game_state *ret; | ||
1721 | |||
1722 | ret = snew(game_state); | ||
1723 | ret->width = state->width; | ||
1724 | ret->height = state->height; | ||
1725 | ret->wrapping = state->wrapping; | ||
1726 | ret->completed = state->completed; | ||
1727 | ret->used_solve = state->used_solve; | ||
1728 | ret->last_rotate_dir = state->last_rotate_dir; | ||
1729 | ret->last_rotate_x = state->last_rotate_x; | ||
1730 | ret->last_rotate_y = state->last_rotate_y; | ||
1731 | ret->tiles = snewn(state->width * state->height, unsigned char); | ||
1732 | memcpy(ret->tiles, state->tiles, state->width * state->height); | ||
1733 | ret->barriers = snewn(state->width * state->height, unsigned char); | ||
1734 | memcpy(ret->barriers, state->barriers, state->width * state->height); | ||
1735 | |||
1736 | return ret; | ||
1737 | } | ||
1738 | |||
1739 | static void free_game(game_state *state) | ||
1740 | { | ||
1741 | sfree(state->tiles); | ||
1742 | sfree(state->barriers); | ||
1743 | sfree(state); | ||
1744 | } | ||
1745 | |||
1746 | static char *solve_game(const game_state *state, const game_state *currstate, | ||
1747 | const char *aux, char **error) | ||
1748 | { | ||
1749 | unsigned char *tiles; | ||
1750 | char *ret; | ||
1751 | int retlen, retsize; | ||
1752 | int i; | ||
1753 | |||
1754 | tiles = snewn(state->width * state->height, unsigned char); | ||
1755 | |||
1756 | if (!aux) { | ||
1757 | /* | ||
1758 | * Run the internal solver on the provided grid. This might | ||
1759 | * not yield a complete solution. | ||
1760 | */ | ||
1761 | memcpy(tiles, state->tiles, state->width * state->height); | ||
1762 | net_solver(state->width, state->height, tiles, | ||
1763 | state->barriers, state->wrapping); | ||
1764 | } else { | ||
1765 | for (i = 0; i < state->width * state->height; i++) { | ||
1766 | int c = aux[i]; | ||
1767 | |||
1768 | if (c >= '0' && c <= '9') | ||
1769 | tiles[i] = c - '0'; | ||
1770 | else if (c >= 'a' && c <= 'f') | ||
1771 | tiles[i] = c - 'a' + 10; | ||
1772 | else if (c >= 'A' && c <= 'F') | ||
1773 | tiles[i] = c - 'A' + 10; | ||
1774 | |||
1775 | tiles[i] |= LOCKED; | ||
1776 | } | ||
1777 | } | ||
1778 | |||
1779 | /* | ||
1780 | * Now construct a string which can be passed to execute_move() | ||
1781 | * to transform the current grid into the solved one. | ||
1782 | */ | ||
1783 | retsize = 256; | ||
1784 | ret = snewn(retsize, char); | ||
1785 | retlen = 0; | ||
1786 | ret[retlen++] = 'S'; | ||
1787 | |||
1788 | for (i = 0; i < state->width * state->height; i++) { | ||
1789 | int from = currstate->tiles[i], to = tiles[i]; | ||
1790 | int ft = from & (R|L|U|D), tt = to & (R|L|U|D); | ||
1791 | int x = i % state->width, y = i / state->width; | ||
1792 | int chr = '\0'; | ||
1793 | char buf[80], *p = buf; | ||
1794 | |||
1795 | if (from == to) | ||
1796 | continue; /* nothing needs doing at all */ | ||
1797 | |||
1798 | /* | ||
1799 | * To transform this tile into the desired tile: first | ||
1800 | * unlock the tile if it's locked, then rotate it if | ||
1801 | * necessary, then lock it if necessary. | ||
1802 | */ | ||
1803 | if (from & LOCKED) | ||
1804 | p += sprintf(p, ";L%d,%d", x, y); | ||
1805 | |||
1806 | if (tt == A(ft)) | ||
1807 | chr = 'A'; | ||
1808 | else if (tt == C(ft)) | ||
1809 | chr = 'C'; | ||
1810 | else if (tt == F(ft)) | ||
1811 | chr = 'F'; | ||
1812 | else { | ||
1813 | assert(tt == ft); | ||
1814 | chr = '\0'; | ||
1815 | } | ||
1816 | if (chr) | ||
1817 | p += sprintf(p, ";%c%d,%d", chr, x, y); | ||
1818 | |||
1819 | if (to & LOCKED) | ||
1820 | p += sprintf(p, ";L%d,%d", x, y); | ||
1821 | |||
1822 | if (p > buf) { | ||
1823 | if (retlen + (p - buf) >= retsize) { | ||
1824 | retsize = retlen + (p - buf) + 512; | ||
1825 | ret = sresize(ret, retsize, char); | ||
1826 | } | ||
1827 | memcpy(ret+retlen, buf, p - buf); | ||
1828 | retlen += p - buf; | ||
1829 | } | ||
1830 | } | ||
1831 | |||
1832 | assert(retlen < retsize); | ||
1833 | ret[retlen] = '\0'; | ||
1834 | ret = sresize(ret, retlen+1, char); | ||
1835 | |||
1836 | sfree(tiles); | ||
1837 | |||
1838 | return ret; | ||
1839 | } | ||
1840 | |||
1841 | static int game_can_format_as_text_now(const game_params *params) | ||
1842 | { | ||
1843 | return TRUE; | ||
1844 | } | ||
1845 | |||
1846 | static char *game_text_format(const game_state *state) | ||
1847 | { | ||
1848 | return NULL; | ||
1849 | } | ||
1850 | |||
1851 | /* ---------------------------------------------------------------------- | ||
1852 | * Utility routine. | ||
1853 | */ | ||
1854 | |||
1855 | /* | ||
1856 | * Compute which squares are reachable from the centre square, as a | ||
1857 | * quick visual aid to determining how close the game is to | ||
1858 | * completion. This is also a simple way to tell if the game _is_ | ||
1859 | * completed - just call this function and see whether every square | ||
1860 | * is marked active. | ||
1861 | */ | ||
1862 | static unsigned char *compute_active(const game_state *state, int cx, int cy) | ||
1863 | { | ||
1864 | unsigned char *active; | ||
1865 | tree234 *todo; | ||
1866 | struct xyd *xyd; | ||
1867 | |||
1868 | active = snewn(state->width * state->height, unsigned char); | ||
1869 | memset(active, 0, state->width * state->height); | ||
1870 | |||
1871 | /* | ||
1872 | * We only store (x,y) pairs in todo, but it's easier to reuse | ||
1873 | * xyd_cmp and just store direction 0 every time. | ||
1874 | */ | ||
1875 | todo = newtree234(xyd_cmp_nc); | ||
1876 | index(state, active, cx, cy) = ACTIVE; | ||
1877 | add234(todo, new_xyd(cx, cy, 0)); | ||
1878 | |||
1879 | while ( (xyd = delpos234(todo, 0)) != NULL) { | ||
1880 | int x1, y1, d1, x2, y2, d2; | ||
1881 | |||
1882 | x1 = xyd->x; | ||
1883 | y1 = xyd->y; | ||
1884 | sfree(xyd); | ||
1885 | |||
1886 | for (d1 = 1; d1 < 0x10; d1 <<= 1) { | ||
1887 | OFFSET(x2, y2, x1, y1, d1, state); | ||
1888 | d2 = F(d1); | ||
1889 | |||
1890 | /* | ||
1891 | * If the next tile in this direction is connected to | ||
1892 | * us, and there isn't a barrier in the way, and it | ||
1893 | * isn't already marked active, then mark it active and | ||
1894 | * add it to the to-examine list. | ||
1895 | */ | ||
1896 | if ((tile(state, x1, y1) & d1) && | ||
1897 | (tile(state, x2, y2) & d2) && | ||
1898 | !(barrier(state, x1, y1) & d1) && | ||
1899 | !index(state, active, x2, y2)) { | ||
1900 | index(state, active, x2, y2) = ACTIVE; | ||
1901 | add234(todo, new_xyd(x2, y2, 0)); | ||
1902 | } | ||
1903 | } | ||
1904 | } | ||
1905 | /* Now we expect the todo list to have shrunk to zero size. */ | ||
1906 | assert(count234(todo) == 0); | ||
1907 | freetree234(todo); | ||
1908 | |||
1909 | return active; | ||
1910 | } | ||
1911 | |||
1912 | struct net_neighbour_ctx { | ||
1913 | int w, h; | ||
1914 | const unsigned char *tiles, *barriers; | ||
1915 | int i, n, neighbours[4]; | ||
1916 | }; | ||
1917 | static int net_neighbour(int vertex, void *vctx) | ||
1918 | { | ||
1919 | struct net_neighbour_ctx *ctx = (struct net_neighbour_ctx *)vctx; | ||
1920 | |||
1921 | if (vertex >= 0) { | ||
1922 | int x = vertex % ctx->w, y = vertex / ctx->w; | ||
1923 | int tile, dir, x1, y1, v1; | ||
1924 | |||
1925 | ctx->i = ctx->n = 0; | ||
1926 | |||
1927 | tile = ctx->tiles[vertex]; | ||
1928 | if (ctx->barriers) | ||
1929 | tile &= ~ctx->barriers[vertex]; | ||
1930 | |||
1931 | for (dir = 1; dir < 0x10; dir <<= 1) { | ||
1932 | if (!(tile & dir)) | ||
1933 | continue; | ||
1934 | OFFSETWH(x1, y1, x, y, dir, ctx->w, ctx->h); | ||
1935 | v1 = y1 * ctx->w + x1; | ||
1936 | if (ctx->tiles[v1] & F(dir)) | ||
1937 | ctx->neighbours[ctx->n++] = v1; | ||
1938 | } | ||
1939 | } | ||
1940 | |||
1941 | if (ctx->i < ctx->n) | ||
1942 | return ctx->neighbours[ctx->i++]; | ||
1943 | else | ||
1944 | return -1; | ||
1945 | } | ||
1946 | |||
1947 | static int *compute_loops_inner(int w, int h, int wrapping, | ||
1948 | const unsigned char *tiles, | ||
1949 | const unsigned char *barriers) | ||
1950 | { | ||
1951 | struct net_neighbour_ctx ctx; | ||
1952 | struct findloopstate *fls; | ||
1953 | int *loops; | ||
1954 | int x, y; | ||
1955 | |||
1956 | fls = findloop_new_state(w*h); | ||
1957 | ctx.w = w; | ||
1958 | ctx.h = h; | ||
1959 | ctx.tiles = tiles; | ||
1960 | ctx.barriers = barriers; | ||
1961 | findloop_run(fls, w*h, net_neighbour, &ctx); | ||
1962 | |||
1963 | loops = snewn(w*h, int); | ||
1964 | |||
1965 | for (y = 0; y < h; y++) { | ||
1966 | for (x = 0; x < w; x++) { | ||
1967 | int x1, y1, dir; | ||
1968 | int flags = 0; | ||
1969 | |||
1970 | for (dir = 1; dir < 0x10; dir <<= 1) { | ||
1971 | if ((tiles[y*w+x] & dir) && | ||
1972 | !(barriers && (barriers[y*w+x] & dir))) { | ||
1973 | OFFSETWH(x1, y1, x, y, dir, w, h); | ||
1974 | if ((tiles[y1*w+x1] & F(dir)) && | ||
1975 | findloop_is_loop_edge(fls, y*w+x, y1*w+x1)) | ||
1976 | flags |= LOOP(dir); | ||
1977 | } | ||
1978 | } | ||
1979 | loops[y*w+x] = flags; | ||
1980 | } | ||
1981 | } | ||
1982 | |||
1983 | findloop_free_state(fls); | ||
1984 | return loops; | ||
1985 | } | ||
1986 | |||
1987 | static int *compute_loops(const game_state *state) | ||
1988 | { | ||
1989 | return compute_loops_inner(state->width, state->height, state->wrapping, | ||
1990 | state->tiles, state->barriers); | ||
1991 | } | ||
1992 | |||
1993 | struct game_ui { | ||
1994 | int org_x, org_y; /* origin */ | ||
1995 | int cx, cy; /* source tile (game coordinates) */ | ||
1996 | int cur_x, cur_y; | ||
1997 | int cur_visible; | ||
1998 | random_state *rs; /* used for jumbling */ | ||
1999 | #ifdef USE_DRAGGING | ||
2000 | int dragtilex, dragtiley, dragstartx, dragstarty, dragged; | ||
2001 | #endif | ||
2002 | }; | ||
2003 | |||
2004 | static game_ui *new_ui(const game_state *state) | ||
2005 | { | ||
2006 | void *seed; | ||
2007 | int seedsize; | ||
2008 | game_ui *ui = snew(game_ui); | ||
2009 | ui->org_x = ui->org_y = 0; | ||
2010 | ui->cur_x = ui->cx = state->width / 2; | ||
2011 | ui->cur_y = ui->cy = state->height / 2; | ||
2012 | ui->cur_visible = FALSE; | ||
2013 | get_random_seed(&seed, &seedsize); | ||
2014 | ui->rs = random_new(seed, seedsize); | ||
2015 | sfree(seed); | ||
2016 | |||
2017 | return ui; | ||
2018 | } | ||
2019 | |||
2020 | static void free_ui(game_ui *ui) | ||
2021 | { | ||
2022 | random_free(ui->rs); | ||
2023 | sfree(ui); | ||
2024 | } | ||
2025 | |||
2026 | static char *encode_ui(const game_ui *ui) | ||
2027 | { | ||
2028 | char buf[120]; | ||
2029 | /* | ||
2030 | * We preserve the origin and centre-point coordinates over a | ||
2031 | * serialise. | ||
2032 | */ | ||
2033 | sprintf(buf, "O%d,%d;C%d,%d", ui->org_x, ui->org_y, ui->cx, ui->cy); | ||
2034 | return dupstr(buf); | ||
2035 | } | ||
2036 | |||
2037 | static void decode_ui(game_ui *ui, const char *encoding) | ||
2038 | { | ||
2039 | sscanf(encoding, "O%d,%d;C%d,%d", | ||
2040 | &ui->org_x, &ui->org_y, &ui->cx, &ui->cy); | ||
2041 | } | ||
2042 | |||
2043 | static void game_changed_state(game_ui *ui, const game_state *oldstate, | ||
2044 | const game_state *newstate) | ||
2045 | { | ||
2046 | } | ||
2047 | |||
2048 | struct game_drawstate { | ||
2049 | int started; | ||
2050 | int width, height; | ||
2051 | int org_x, org_y; | ||
2052 | int tilesize; | ||
2053 | int *visible; | ||
2054 | }; | ||
2055 | |||
2056 | /* ---------------------------------------------------------------------- | ||
2057 | * Process a move. | ||
2058 | */ | ||
2059 | static char *interpret_move(const game_state *state, game_ui *ui, | ||
2060 | const game_drawstate *ds, | ||
2061 | int x, int y, int button) | ||
2062 | { | ||
2063 | char *nullret; | ||
2064 | int tx = -1, ty = -1, dir = 0; | ||
2065 | int shift = button & MOD_SHFT, ctrl = button & MOD_CTRL; | ||
2066 | enum { | ||
2067 | NONE, ROTATE_LEFT, ROTATE_180, ROTATE_RIGHT, TOGGLE_LOCK, JUMBLE, | ||
2068 | MOVE_ORIGIN, MOVE_SOURCE, MOVE_ORIGIN_AND_SOURCE, MOVE_CURSOR | ||
2069 | } action; | ||
2070 | |||
2071 | button &= ~MOD_MASK; | ||
2072 | nullret = NULL; | ||
2073 | action = NONE; | ||
2074 | |||
2075 | if (button == LEFT_BUTTON || | ||
2076 | button == MIDDLE_BUTTON || | ||
2077 | #ifdef USE_DRAGGING | ||
2078 | button == LEFT_DRAG || | ||
2079 | button == LEFT_RELEASE || | ||
2080 | button == RIGHT_DRAG || | ||
2081 | button == RIGHT_RELEASE || | ||
2082 | #endif | ||
2083 | button == RIGHT_BUTTON) { | ||
2084 | |||
2085 | if (ui->cur_visible) { | ||
2086 | ui->cur_visible = FALSE; | ||
2087 | nullret = ""; | ||
2088 | } | ||
2089 | |||
2090 | /* | ||
2091 | * The button must have been clicked on a valid tile. | ||
2092 | */ | ||
2093 | x -= WINDOW_OFFSET + TILE_BORDER; | ||
2094 | y -= WINDOW_OFFSET + TILE_BORDER; | ||
2095 | if (x < 0 || y < 0) | ||
2096 | return nullret; | ||
2097 | tx = x / TILE_SIZE; | ||
2098 | ty = y / TILE_SIZE; | ||
2099 | if (tx >= state->width || ty >= state->height) | ||
2100 | return nullret; | ||
2101 | /* Transform from physical to game coords */ | ||
2102 | tx = (tx + ui->org_x) % state->width; | ||
2103 | ty = (ty + ui->org_y) % state->height; | ||
2104 | if (x % TILE_SIZE >= TILE_SIZE - TILE_BORDER || | ||
2105 | y % TILE_SIZE >= TILE_SIZE - TILE_BORDER) | ||
2106 | return nullret; | ||
2107 | |||
2108 | #ifdef USE_DRAGGING | ||
2109 | |||
2110 | if (button == MIDDLE_BUTTON | ||
2111 | #ifdef STYLUS_BASED | ||
2112 | || button == RIGHT_BUTTON /* with a stylus, `right-click' locks */ | ||
2113 | #endif | ||
2114 | ) { | ||
2115 | /* | ||
2116 | * Middle button never drags: it only toggles the lock. | ||
2117 | */ | ||
2118 | action = TOGGLE_LOCK; | ||
2119 | } else if (button == LEFT_BUTTON | ||
2120 | #ifndef STYLUS_BASED | ||
2121 | || button == RIGHT_BUTTON /* (see above) */ | ||
2122 | #endif | ||
2123 | ) { | ||
2124 | /* | ||
2125 | * Otherwise, we note down the start point for a drag. | ||
2126 | */ | ||
2127 | ui->dragtilex = tx; | ||
2128 | ui->dragtiley = ty; | ||
2129 | ui->dragstartx = x % TILE_SIZE; | ||
2130 | ui->dragstarty = y % TILE_SIZE; | ||
2131 | ui->dragged = FALSE; | ||
2132 | return nullret; /* no actual action */ | ||
2133 | } else if (button == LEFT_DRAG | ||
2134 | #ifndef STYLUS_BASED | ||
2135 | || button == RIGHT_DRAG | ||
2136 | #endif | ||
2137 | ) { | ||
2138 | /* | ||
2139 | * Find the new drag point and see if it necessitates a | ||
2140 | * rotation. | ||
2141 | */ | ||
2142 | int x0,y0, xA,yA, xC,yC, xF,yF; | ||
2143 | int mx, my; | ||
2144 | int d0, dA, dC, dF, dmin; | ||
2145 | |||
2146 | tx = ui->dragtilex; | ||
2147 | ty = ui->dragtiley; | ||
2148 | |||
2149 | mx = x - (ui->dragtilex * TILE_SIZE); | ||
2150 | my = y - (ui->dragtiley * TILE_SIZE); | ||
2151 | |||
2152 | x0 = ui->dragstartx; | ||
2153 | y0 = ui->dragstarty; | ||
2154 | xA = ui->dragstarty; | ||
2155 | yA = TILE_SIZE-1 - ui->dragstartx; | ||
2156 | xF = TILE_SIZE-1 - ui->dragstartx; | ||
2157 | yF = TILE_SIZE-1 - ui->dragstarty; | ||
2158 | xC = TILE_SIZE-1 - ui->dragstarty; | ||
2159 | yC = ui->dragstartx; | ||
2160 | |||
2161 | d0 = (mx-x0)*(mx-x0) + (my-y0)*(my-y0); | ||
2162 | dA = (mx-xA)*(mx-xA) + (my-yA)*(my-yA); | ||
2163 | dF = (mx-xF)*(mx-xF) + (my-yF)*(my-yF); | ||
2164 | dC = (mx-xC)*(mx-xC) + (my-yC)*(my-yC); | ||
2165 | |||
2166 | dmin = min(min(d0,dA),min(dF,dC)); | ||
2167 | |||
2168 | if (d0 == dmin) { | ||
2169 | return nullret; | ||
2170 | } else if (dF == dmin) { | ||
2171 | action = ROTATE_180; | ||
2172 | ui->dragstartx = xF; | ||
2173 | ui->dragstarty = yF; | ||
2174 | ui->dragged = TRUE; | ||
2175 | } else if (dA == dmin) { | ||
2176 | action = ROTATE_LEFT; | ||
2177 | ui->dragstartx = xA; | ||
2178 | ui->dragstarty = yA; | ||
2179 | ui->dragged = TRUE; | ||
2180 | } else /* dC == dmin */ { | ||
2181 | action = ROTATE_RIGHT; | ||
2182 | ui->dragstartx = xC; | ||
2183 | ui->dragstarty = yC; | ||
2184 | ui->dragged = TRUE; | ||
2185 | } | ||
2186 | } else if (button == LEFT_RELEASE | ||
2187 | #ifndef STYLUS_BASED | ||
2188 | || button == RIGHT_RELEASE | ||
2189 | #endif | ||
2190 | ) { | ||
2191 | if (!ui->dragged) { | ||
2192 | /* | ||
2193 | * There was a click but no perceptible drag: | ||
2194 | * revert to single-click behaviour. | ||
2195 | */ | ||
2196 | tx = ui->dragtilex; | ||
2197 | ty = ui->dragtiley; | ||
2198 | |||
2199 | if (button == LEFT_RELEASE) | ||
2200 | action = ROTATE_LEFT; | ||
2201 | else | ||
2202 | action = ROTATE_RIGHT; | ||
2203 | } else | ||
2204 | return nullret; /* no action */ | ||
2205 | } | ||
2206 | |||
2207 | #else /* USE_DRAGGING */ | ||
2208 | |||
2209 | action = (button == LEFT_BUTTON ? ROTATE_LEFT : | ||
2210 | button == RIGHT_BUTTON ? ROTATE_RIGHT : TOGGLE_LOCK); | ||
2211 | |||
2212 | #endif /* USE_DRAGGING */ | ||
2213 | |||
2214 | } else if (IS_CURSOR_MOVE(button)) { | ||
2215 | switch (button) { | ||
2216 | case CURSOR_UP: dir = U; break; | ||
2217 | case CURSOR_DOWN: dir = D; break; | ||
2218 | case CURSOR_LEFT: dir = L; break; | ||
2219 | case CURSOR_RIGHT: dir = R; break; | ||
2220 | default: return nullret; | ||
2221 | } | ||
2222 | if (shift && ctrl) action = MOVE_ORIGIN_AND_SOURCE; | ||
2223 | else if (shift) action = MOVE_ORIGIN; | ||
2224 | else if (ctrl) action = MOVE_SOURCE; | ||
2225 | else action = MOVE_CURSOR; | ||
2226 | } else if (button == 'a' || button == 's' || button == 'd' || | ||
2227 | button == 'A' || button == 'S' || button == 'D' || | ||
2228 | button == 'f' || button == 'F' || | ||
2229 | IS_CURSOR_SELECT(button)) { | ||
2230 | tx = ui->cur_x; | ||
2231 | ty = ui->cur_y; | ||
2232 | if (button == 'a' || button == 'A' || button == CURSOR_SELECT) | ||
2233 | action = ROTATE_LEFT; | ||
2234 | else if (button == 's' || button == 'S' || button == CURSOR_SELECT2) | ||
2235 | action = TOGGLE_LOCK; | ||
2236 | else if (button == 'd' || button == 'D') | ||
2237 | action = ROTATE_RIGHT; | ||
2238 | else if (button == 'f' || button == 'F') | ||
2239 | action = ROTATE_180; | ||
2240 | ui->cur_visible = TRUE; | ||
2241 | } else if (button == 'j' || button == 'J') { | ||
2242 | /* XXX should we have some mouse control for this? */ | ||
2243 | action = JUMBLE; | ||
2244 | } else | ||
2245 | return nullret; | ||
2246 | |||
2247 | /* | ||
2248 | * The middle button locks or unlocks a tile. (A locked tile | ||
2249 | * cannot be turned, and is visually marked as being locked. | ||
2250 | * This is a convenience for the player, so that once they are | ||
2251 | * sure which way round a tile goes, they can lock it and thus | ||
2252 | * avoid forgetting later on that they'd already done that one; | ||
2253 | * and the locking also prevents them turning the tile by | ||
2254 | * accident. If they change their mind, another middle click | ||
2255 | * unlocks it.) | ||
2256 | */ | ||
2257 | if (action == TOGGLE_LOCK) { | ||
2258 | char buf[80]; | ||
2259 | sprintf(buf, "L%d,%d", tx, ty); | ||
2260 | return dupstr(buf); | ||
2261 | } else if (action == ROTATE_LEFT || action == ROTATE_RIGHT || | ||
2262 | action == ROTATE_180) { | ||
2263 | char buf[80]; | ||
2264 | |||
2265 | /* | ||
2266 | * The left and right buttons have no effect if clicked on a | ||
2267 | * locked tile. | ||
2268 | */ | ||
2269 | if (tile(state, tx, ty) & LOCKED) | ||
2270 | return nullret; | ||
2271 | |||
2272 | /* | ||
2273 | * Otherwise, turn the tile one way or the other. Left button | ||
2274 | * turns anticlockwise; right button turns clockwise. | ||
2275 | */ | ||
2276 | sprintf(buf, "%c%d,%d", (int)(action == ROTATE_LEFT ? 'A' : | ||
2277 | action == ROTATE_RIGHT ? 'C' : 'F'), tx, ty); | ||
2278 | return dupstr(buf); | ||
2279 | } else if (action == JUMBLE) { | ||
2280 | /* | ||
2281 | * Jumble all unlocked tiles to random orientations. | ||
2282 | */ | ||
2283 | |||
2284 | int jx, jy, maxlen; | ||
2285 | char *ret, *p; | ||
2286 | |||
2287 | /* | ||
2288 | * Maximum string length assumes no int can be converted to | ||
2289 | * decimal and take more than 11 digits! | ||
2290 | */ | ||
2291 | maxlen = state->width * state->height * 25 + 3; | ||
2292 | |||
2293 | ret = snewn(maxlen, char); | ||
2294 | p = ret; | ||
2295 | *p++ = 'J'; | ||
2296 | |||
2297 | for (jy = 0; jy < state->height; jy++) { | ||
2298 | for (jx = 0; jx < state->width; jx++) { | ||
2299 | if (!(tile(state, jx, jy) & LOCKED)) { | ||
2300 | int rot = random_upto(ui->rs, 4); | ||
2301 | if (rot) { | ||
2302 | p += sprintf(p, ";%c%d,%d", "AFC"[rot-1], jx, jy); | ||
2303 | } | ||
2304 | } | ||
2305 | } | ||
2306 | } | ||
2307 | *p++ = '\0'; | ||
2308 | assert(p - ret < maxlen); | ||
2309 | ret = sresize(ret, p - ret, char); | ||
2310 | |||
2311 | return ret; | ||
2312 | } else if (action == MOVE_ORIGIN || action == MOVE_SOURCE || | ||
2313 | action == MOVE_ORIGIN_AND_SOURCE || action == MOVE_CURSOR) { | ||
2314 | assert(dir != 0); | ||
2315 | if (action == MOVE_ORIGIN || action == MOVE_ORIGIN_AND_SOURCE) { | ||
2316 | if (state->wrapping) { | ||
2317 | OFFSET(ui->org_x, ui->org_y, ui->org_x, ui->org_y, dir, state); | ||
2318 | } else return nullret; /* disallowed for non-wrapping grids */ | ||
2319 | } | ||
2320 | if (action == MOVE_SOURCE || action == MOVE_ORIGIN_AND_SOURCE) { | ||
2321 | OFFSET(ui->cx, ui->cy, ui->cx, ui->cy, dir, state); | ||
2322 | } | ||
2323 | if (action == MOVE_CURSOR) { | ||
2324 | OFFSET(ui->cur_x, ui->cur_y, ui->cur_x, ui->cur_y, dir, state); | ||
2325 | ui->cur_visible = TRUE; | ||
2326 | } | ||
2327 | return ""; | ||
2328 | } else { | ||
2329 | return NULL; | ||
2330 | } | ||
2331 | } | ||
2332 | |||
2333 | static game_state *execute_move(const game_state *from, const char *move) | ||
2334 | { | ||
2335 | game_state *ret; | ||
2336 | int tx = -1, ty = -1, n, noanim, orig; | ||
2337 | |||
2338 | ret = dup_game(from); | ||
2339 | |||
2340 | if (move[0] == 'J' || move[0] == 'S') { | ||
2341 | if (move[0] == 'S') | ||
2342 | ret->used_solve = TRUE; | ||
2343 | |||
2344 | move++; | ||
2345 | if (*move == ';') | ||
2346 | move++; | ||
2347 | noanim = TRUE; | ||
2348 | } else | ||
2349 | noanim = FALSE; | ||
2350 | |||
2351 | ret->last_rotate_dir = 0; /* suppress animation */ | ||
2352 | ret->last_rotate_x = ret->last_rotate_y = 0; | ||
2353 | |||
2354 | while (*move) { | ||
2355 | if ((move[0] == 'A' || move[0] == 'C' || | ||
2356 | move[0] == 'F' || move[0] == 'L') && | ||
2357 | sscanf(move+1, "%d,%d%n", &tx, &ty, &n) >= 2 && | ||
2358 | tx >= 0 && tx < from->width && ty >= 0 && ty < from->height) { | ||
2359 | orig = tile(ret, tx, ty); | ||
2360 | if (move[0] == 'A') { | ||
2361 | tile(ret, tx, ty) = A(orig); | ||
2362 | if (!noanim) | ||
2363 | ret->last_rotate_dir = +1; | ||
2364 | } else if (move[0] == 'F') { | ||
2365 | tile(ret, tx, ty) = F(orig); | ||
2366 | if (!noanim) | ||
2367 | ret->last_rotate_dir = +2; /* + for sake of argument */ | ||
2368 | } else if (move[0] == 'C') { | ||
2369 | tile(ret, tx, ty) = C(orig); | ||
2370 | if (!noanim) | ||
2371 | ret->last_rotate_dir = -1; | ||
2372 | } else { | ||
2373 | assert(move[0] == 'L'); | ||
2374 | tile(ret, tx, ty) ^= LOCKED; | ||
2375 | } | ||
2376 | |||
2377 | move += 1 + n; | ||
2378 | if (*move == ';') move++; | ||
2379 | } else { | ||
2380 | free_game(ret); | ||
2381 | return NULL; | ||
2382 | } | ||
2383 | } | ||
2384 | if (!noanim) { | ||
2385 | if (tx == -1 || ty == -1) { free_game(ret); return NULL; } | ||
2386 | ret->last_rotate_x = tx; | ||
2387 | ret->last_rotate_y = ty; | ||
2388 | } | ||
2389 | |||
2390 | /* | ||
2391 | * Check whether the game has been completed. | ||
2392 | * | ||
2393 | * For this purpose it doesn't matter where the source square is, | ||
2394 | * because we can start from anywhere (or, at least, any square | ||
2395 | * that's non-empty!), and correctly determine whether the game is | ||
2396 | * completed. | ||
2397 | */ | ||
2398 | { | ||
2399 | unsigned char *active; | ||
2400 | int pos; | ||
2401 | int complete = TRUE; | ||
2402 | |||
2403 | for (pos = 0; pos < ret->width * ret->height; pos++) | ||
2404 | if (ret->tiles[pos] & 0xF) | ||
2405 | break; | ||
2406 | |||
2407 | if (pos < ret->width * ret->height) { | ||
2408 | active = compute_active(ret, pos % ret->width, pos / ret->width); | ||
2409 | |||
2410 | for (pos = 0; pos < ret->width * ret->height; pos++) | ||
2411 | if ((ret->tiles[pos] & 0xF) && !active[pos]) { | ||
2412 | complete = FALSE; | ||
2413 | break; | ||
2414 | } | ||
2415 | |||
2416 | sfree(active); | ||
2417 | } | ||
2418 | |||
2419 | if (complete) | ||
2420 | ret->completed = TRUE; | ||
2421 | } | ||
2422 | |||
2423 | return ret; | ||
2424 | } | ||
2425 | |||
2426 | |||
2427 | /* ---------------------------------------------------------------------- | ||
2428 | * Routines for drawing the game position on the screen. | ||
2429 | */ | ||
2430 | |||
2431 | static game_drawstate *game_new_drawstate(drawing *dr, const game_state *state) | ||
2432 | { | ||
2433 | game_drawstate *ds = snew(game_drawstate); | ||
2434 | int i; | ||
2435 | |||
2436 | ds->started = FALSE; | ||
2437 | ds->width = state->width; | ||
2438 | ds->height = state->height; | ||
2439 | ds->org_x = ds->org_y = -1; | ||
2440 | ds->visible = snewn(state->width * state->height, int); | ||
2441 | ds->tilesize = 0; /* undecided yet */ | ||
2442 | for (i = 0; i < state->width * state->height; i++) | ||
2443 | ds->visible[i] = -1; | ||
2444 | |||
2445 | return ds; | ||
2446 | } | ||
2447 | |||
2448 | static void game_free_drawstate(drawing *dr, game_drawstate *ds) | ||
2449 | { | ||
2450 | sfree(ds->visible); | ||
2451 | sfree(ds); | ||
2452 | } | ||
2453 | |||
2454 | static void game_compute_size(const game_params *params, int tilesize, | ||
2455 | int *x, int *y) | ||
2456 | { | ||
2457 | *x = WINDOW_OFFSET * 2 + tilesize * params->width + TILE_BORDER; | ||
2458 | *y = WINDOW_OFFSET * 2 + tilesize * params->height + TILE_BORDER; | ||
2459 | } | ||
2460 | |||
2461 | static void game_set_size(drawing *dr, game_drawstate *ds, | ||
2462 | const game_params *params, int tilesize) | ||
2463 | { | ||
2464 | ds->tilesize = tilesize; | ||
2465 | } | ||
2466 | |||
2467 | static float *game_colours(frontend *fe, int *ncolours) | ||
2468 | { | ||
2469 | float *ret; | ||
2470 | |||
2471 | ret = snewn(NCOLOURS * 3, float); | ||
2472 | *ncolours = NCOLOURS; | ||
2473 | |||
2474 | /* | ||
2475 | * Basic background colour is whatever the front end thinks is | ||
2476 | * a sensible default. | ||
2477 | */ | ||
2478 | frontend_default_colour(fe, &ret[COL_BACKGROUND * 3]); | ||
2479 | |||
2480 | /* | ||
2481 | * Wires are black. | ||
2482 | */ | ||
2483 | ret[COL_WIRE * 3 + 0] = 0.0F; | ||
2484 | ret[COL_WIRE * 3 + 1] = 0.0F; | ||
2485 | ret[COL_WIRE * 3 + 2] = 0.0F; | ||
2486 | |||
2487 | /* | ||
2488 | * Powered wires and powered endpoints are cyan. | ||
2489 | */ | ||
2490 | ret[COL_POWERED * 3 + 0] = 0.0F; | ||
2491 | ret[COL_POWERED * 3 + 1] = 1.0F; | ||
2492 | ret[COL_POWERED * 3 + 2] = 1.0F; | ||
2493 | |||
2494 | /* | ||
2495 | * Barriers are red. | ||
2496 | */ | ||
2497 | ret[COL_BARRIER * 3 + 0] = 1.0F; | ||
2498 | ret[COL_BARRIER * 3 + 1] = 0.0F; | ||
2499 | ret[COL_BARRIER * 3 + 2] = 0.0F; | ||
2500 | |||
2501 | /* | ||
2502 | * Highlighted loops are red as well. | ||
2503 | */ | ||
2504 | ret[COL_LOOP * 3 + 0] = 1.0F; | ||
2505 | ret[COL_LOOP * 3 + 1] = 0.0F; | ||
2506 | ret[COL_LOOP * 3 + 2] = 0.0F; | ||
2507 | |||
2508 | /* | ||
2509 | * Unpowered endpoints are blue. | ||
2510 | */ | ||
2511 | ret[COL_ENDPOINT * 3 + 0] = 0.0F; | ||
2512 | ret[COL_ENDPOINT * 3 + 1] = 0.0F; | ||
2513 | ret[COL_ENDPOINT * 3 + 2] = 1.0F; | ||
2514 | |||
2515 | /* | ||
2516 | * Tile borders are a darker grey than the background. | ||
2517 | */ | ||
2518 | ret[COL_BORDER * 3 + 0] = 0.5F * ret[COL_BACKGROUND * 3 + 0]; | ||
2519 | ret[COL_BORDER * 3 + 1] = 0.5F * ret[COL_BACKGROUND * 3 + 1]; | ||
2520 | ret[COL_BORDER * 3 + 2] = 0.5F * ret[COL_BACKGROUND * 3 + 2]; | ||
2521 | |||
2522 | /* | ||
2523 | * Locked tiles are a grey in between those two. | ||
2524 | */ | ||
2525 | ret[COL_LOCKED * 3 + 0] = 0.75F * ret[COL_BACKGROUND * 3 + 0]; | ||
2526 | ret[COL_LOCKED * 3 + 1] = 0.75F * ret[COL_BACKGROUND * 3 + 1]; | ||
2527 | ret[COL_LOCKED * 3 + 2] = 0.75F * ret[COL_BACKGROUND * 3 + 2]; | ||
2528 | |||
2529 | return ret; | ||
2530 | } | ||
2531 | |||
2532 | static void draw_filled_line(drawing *dr, int x1, int y1, int x2, int y2, | ||
2533 | int colour) | ||
2534 | { | ||
2535 | draw_line(dr, x1-1, y1, x2-1, y2, COL_WIRE); | ||
2536 | draw_line(dr, x1+1, y1, x2+1, y2, COL_WIRE); | ||
2537 | draw_line(dr, x1, y1-1, x2, y2-1, COL_WIRE); | ||
2538 | draw_line(dr, x1, y1+1, x2, y2+1, COL_WIRE); | ||
2539 | draw_line(dr, x1, y1, x2, y2, colour); | ||
2540 | } | ||
2541 | |||
2542 | static void draw_rect_coords(drawing *dr, int x1, int y1, int x2, int y2, | ||
2543 | int colour) | ||
2544 | { | ||
2545 | int mx = (x1 < x2 ? x1 : x2); | ||
2546 | int my = (y1 < y2 ? y1 : y2); | ||
2547 | int dx = (x2 + x1 - 2*mx + 1); | ||
2548 | int dy = (y2 + y1 - 2*my + 1); | ||
2549 | |||
2550 | draw_rect(dr, mx, my, dx, dy, colour); | ||
2551 | } | ||
2552 | |||
2553 | /* | ||
2554 | * draw_barrier_corner() and draw_barrier() are passed physical coords | ||
2555 | */ | ||
2556 | static void draw_barrier_corner(drawing *dr, game_drawstate *ds, | ||
2557 | int x, int y, int dx, int dy, int phase) | ||
2558 | { | ||
2559 | int bx = WINDOW_OFFSET + TILE_SIZE * x; | ||
2560 | int by = WINDOW_OFFSET + TILE_SIZE * y; | ||
2561 | int x1, y1; | ||
2562 | |||
2563 | x1 = (dx > 0 ? TILE_SIZE+TILE_BORDER-1 : 0); | ||
2564 | y1 = (dy > 0 ? TILE_SIZE+TILE_BORDER-1 : 0); | ||
2565 | |||
2566 | if (phase == 0) { | ||
2567 | draw_rect_coords(dr, bx+x1+dx, by+y1, | ||
2568 | bx+x1-TILE_BORDER*dx, by+y1-(TILE_BORDER-1)*dy, | ||
2569 | COL_WIRE); | ||
2570 | draw_rect_coords(dr, bx+x1, by+y1+dy, | ||
2571 | bx+x1-(TILE_BORDER-1)*dx, by+y1-TILE_BORDER*dy, | ||
2572 | COL_WIRE); | ||
2573 | } else { | ||
2574 | draw_rect_coords(dr, bx+x1, by+y1, | ||
2575 | bx+x1-(TILE_BORDER-1)*dx, by+y1-(TILE_BORDER-1)*dy, | ||
2576 | COL_BARRIER); | ||
2577 | } | ||
2578 | } | ||
2579 | |||
2580 | static void draw_barrier(drawing *dr, game_drawstate *ds, | ||
2581 | int x, int y, int dir, int phase) | ||
2582 | { | ||
2583 | int bx = WINDOW_OFFSET + TILE_SIZE * x; | ||
2584 | int by = WINDOW_OFFSET + TILE_SIZE * y; | ||
2585 | int x1, y1, w, h; | ||
2586 | |||
2587 | x1 = (X(dir) > 0 ? TILE_SIZE : X(dir) == 0 ? TILE_BORDER : 0); | ||
2588 | y1 = (Y(dir) > 0 ? TILE_SIZE : Y(dir) == 0 ? TILE_BORDER : 0); | ||
2589 | w = (X(dir) ? TILE_BORDER : TILE_SIZE - TILE_BORDER); | ||
2590 | h = (Y(dir) ? TILE_BORDER : TILE_SIZE - TILE_BORDER); | ||
2591 | |||
2592 | if (phase == 0) { | ||
2593 | draw_rect(dr, bx+x1-X(dir), by+y1-Y(dir), w, h, COL_WIRE); | ||
2594 | } else { | ||
2595 | draw_rect(dr, bx+x1, by+y1, w, h, COL_BARRIER); | ||
2596 | } | ||
2597 | } | ||
2598 | |||
2599 | /* | ||
2600 | * draw_tile() is passed physical coordinates | ||
2601 | */ | ||
2602 | static void draw_tile(drawing *dr, const game_state *state, game_drawstate *ds, | ||
2603 | int x, int y, int tile, int src, float angle, int cursor) | ||
2604 | { | ||
2605 | int bx = WINDOW_OFFSET + TILE_SIZE * x; | ||
2606 | int by = WINDOW_OFFSET + TILE_SIZE * y; | ||
2607 | float matrix[4]; | ||
2608 | float cx, cy, ex, ey, tx, ty; | ||
2609 | int dir, col, phase; | ||
2610 | |||
2611 | /* | ||
2612 | * When we draw a single tile, we must draw everything up to | ||
2613 | * and including the borders around the tile. This means that | ||
2614 | * if the neighbouring tiles have connections to those borders, | ||
2615 | * we must draw those connections on the borders themselves. | ||
2616 | */ | ||
2617 | |||
2618 | clip(dr, bx, by, TILE_SIZE+TILE_BORDER, TILE_SIZE+TILE_BORDER); | ||
2619 | |||
2620 | /* | ||
2621 | * So. First blank the tile out completely: draw a big | ||
2622 | * rectangle in border colour, and a smaller rectangle in | ||
2623 | * background colour to fill it in. | ||
2624 | */ | ||
2625 | draw_rect(dr, bx, by, TILE_SIZE+TILE_BORDER, TILE_SIZE+TILE_BORDER, | ||
2626 | COL_BORDER); | ||
2627 | draw_rect(dr, bx+TILE_BORDER, by+TILE_BORDER, | ||
2628 | TILE_SIZE-TILE_BORDER, TILE_SIZE-TILE_BORDER, | ||
2629 | tile & LOCKED ? COL_LOCKED : COL_BACKGROUND); | ||
2630 | |||
2631 | /* | ||
2632 | * Draw an inset outline rectangle as a cursor, in whichever of | ||
2633 | * COL_LOCKED and COL_BACKGROUND we aren't currently drawing | ||
2634 | * in. | ||
2635 | */ | ||
2636 | if (cursor) { | ||
2637 | draw_line(dr, bx+TILE_SIZE/8, by+TILE_SIZE/8, | ||
2638 | bx+TILE_SIZE/8, by+TILE_SIZE-TILE_SIZE/8, | ||
2639 | tile & LOCKED ? COL_BACKGROUND : COL_LOCKED); | ||
2640 | draw_line(dr, bx+TILE_SIZE/8, by+TILE_SIZE/8, | ||
2641 | bx+TILE_SIZE-TILE_SIZE/8, by+TILE_SIZE/8, | ||
2642 | tile & LOCKED ? COL_BACKGROUND : COL_LOCKED); | ||
2643 | draw_line(dr, bx+TILE_SIZE-TILE_SIZE/8, by+TILE_SIZE/8, | ||
2644 | bx+TILE_SIZE-TILE_SIZE/8, by+TILE_SIZE-TILE_SIZE/8, | ||
2645 | tile & LOCKED ? COL_BACKGROUND : COL_LOCKED); | ||
2646 | draw_line(dr, bx+TILE_SIZE/8, by+TILE_SIZE-TILE_SIZE/8, | ||
2647 | bx+TILE_SIZE-TILE_SIZE/8, by+TILE_SIZE-TILE_SIZE/8, | ||
2648 | tile & LOCKED ? COL_BACKGROUND : COL_LOCKED); | ||
2649 | } | ||
2650 | |||
2651 | /* | ||
2652 | * Set up the rotation matrix. | ||
2653 | */ | ||
2654 | matrix[0] = (float)cos(angle * PI / 180.0); | ||
2655 | matrix[1] = (float)-sin(angle * PI / 180.0); | ||
2656 | matrix[2] = (float)sin(angle * PI / 180.0); | ||
2657 | matrix[3] = (float)cos(angle * PI / 180.0); | ||
2658 | |||
2659 | /* | ||
2660 | * Draw the wires. | ||
2661 | */ | ||
2662 | cx = cy = TILE_BORDER + (TILE_SIZE-TILE_BORDER) / 2.0F - 0.5F; | ||
2663 | col = (tile & ACTIVE ? COL_POWERED : COL_WIRE); | ||
2664 | for (dir = 1; dir < 0x10; dir <<= 1) { | ||
2665 | if (tile & dir) { | ||
2666 | ex = (TILE_SIZE - TILE_BORDER - 1.0F) / 2.0F * X(dir); | ||
2667 | ey = (TILE_SIZE - TILE_BORDER - 1.0F) / 2.0F * Y(dir); | ||
2668 | MATMUL(tx, ty, matrix, ex, ey); | ||
2669 | draw_filled_line(dr, bx+(int)cx, by+(int)cy, | ||
2670 | bx+(int)(cx+tx), by+(int)(cy+ty), | ||
2671 | COL_WIRE); | ||
2672 | } | ||
2673 | } | ||
2674 | for (dir = 1; dir < 0x10; dir <<= 1) { | ||
2675 | if (tile & dir) { | ||
2676 | ex = (TILE_SIZE - TILE_BORDER - 1.0F) / 2.0F * X(dir); | ||
2677 | ey = (TILE_SIZE - TILE_BORDER - 1.0F) / 2.0F * Y(dir); | ||
2678 | MATMUL(tx, ty, matrix, ex, ey); | ||
2679 | draw_line(dr, bx+(int)cx, by+(int)cy, | ||
2680 | bx+(int)(cx+tx), by+(int)(cy+ty), | ||
2681 | (tile & LOOP(dir)) ? COL_LOOP : col); | ||
2682 | } | ||
2683 | } | ||
2684 | /* If we've drawn any loop-highlighted arms, make sure the centre | ||
2685 | * point is loop-coloured rather than a later arm overwriting it. */ | ||
2686 | if (tile & (RLOOP | ULOOP | LLOOP | DLOOP)) | ||
2687 | draw_rect(dr, bx+(int)cx, by+(int)cy, 1, 1, COL_LOOP); | ||
2688 | |||
2689 | /* | ||
2690 | * Draw the box in the middle. We do this in blue if the tile | ||
2691 | * is an unpowered endpoint, in cyan if the tile is a powered | ||
2692 | * endpoint, in black if the tile is the centrepiece, and | ||
2693 | * otherwise not at all. | ||
2694 | */ | ||
2695 | col = -1; | ||
2696 | if (src) | ||
2697 | col = COL_WIRE; | ||
2698 | else if (COUNT(tile) == 1) { | ||
2699 | col = (tile & ACTIVE ? COL_POWERED : COL_ENDPOINT); | ||
2700 | } | ||
2701 | if (col >= 0) { | ||
2702 | int i, points[8]; | ||
2703 | |||
2704 | points[0] = +1; points[1] = +1; | ||
2705 | points[2] = +1; points[3] = -1; | ||
2706 | points[4] = -1; points[5] = -1; | ||
2707 | points[6] = -1; points[7] = +1; | ||
2708 | |||
2709 | for (i = 0; i < 8; i += 2) { | ||
2710 | ex = (TILE_SIZE * 0.24F) * points[i]; | ||
2711 | ey = (TILE_SIZE * 0.24F) * points[i+1]; | ||
2712 | MATMUL(tx, ty, matrix, ex, ey); | ||
2713 | points[i] = bx+(int)(cx+tx); | ||
2714 | points[i+1] = by+(int)(cy+ty); | ||
2715 | } | ||
2716 | |||
2717 | draw_polygon(dr, points, 4, col, COL_WIRE); | ||
2718 | } | ||
2719 | |||
2720 | /* | ||
2721 | * Draw the points on the border if other tiles are connected | ||
2722 | * to us. | ||
2723 | */ | ||
2724 | for (dir = 1; dir < 0x10; dir <<= 1) { | ||
2725 | int dx, dy, px, py, lx, ly, vx, vy, ox, oy; | ||
2726 | |||
2727 | dx = X(dir); | ||
2728 | dy = Y(dir); | ||
2729 | |||
2730 | ox = x + dx; | ||
2731 | oy = y + dy; | ||
2732 | |||
2733 | if (ox < 0 || ox >= state->width || oy < 0 || oy >= state->height) | ||
2734 | continue; | ||
2735 | |||
2736 | if (!(tile(state, GX(ox), GY(oy)) & F(dir))) | ||
2737 | continue; | ||
2738 | |||
2739 | px = bx + (int)(dx>0 ? TILE_SIZE + TILE_BORDER - 1 : dx<0 ? 0 : cx); | ||
2740 | py = by + (int)(dy>0 ? TILE_SIZE + TILE_BORDER - 1 : dy<0 ? 0 : cy); | ||
2741 | lx = dx * (TILE_BORDER-1); | ||
2742 | ly = dy * (TILE_BORDER-1); | ||
2743 | vx = (dy ? 1 : 0); | ||
2744 | vy = (dx ? 1 : 0); | ||
2745 | |||
2746 | if (angle == 0.0 && (tile & dir)) { | ||
2747 | /* | ||
2748 | * If we are fully connected to the other tile, we must | ||
2749 | * draw right across the tile border. (We can use our | ||
2750 | * own ACTIVE state to determine what colour to do this | ||
2751 | * in: if we are fully connected to the other tile then | ||
2752 | * the two ACTIVE states will be the same.) | ||
2753 | */ | ||
2754 | draw_rect_coords(dr, px-vx, py-vy, px+lx+vx, py+ly+vy, COL_WIRE); | ||
2755 | draw_rect_coords(dr, px, py, px+lx, py+ly, | ||
2756 | ((tile & LOOP(dir)) ? COL_LOOP : | ||
2757 | (tile & ACTIVE) ? COL_POWERED : | ||
2758 | COL_WIRE)); | ||
2759 | } else { | ||
2760 | /* | ||
2761 | * The other tile extends into our border, but isn't | ||
2762 | * actually connected to us. Just draw a single black | ||
2763 | * dot. | ||
2764 | */ | ||
2765 | draw_rect_coords(dr, px, py, px, py, COL_WIRE); | ||
2766 | } | ||
2767 | } | ||
2768 | |||
2769 | /* | ||
2770 | * Draw barrier corners, and then barriers. | ||
2771 | */ | ||
2772 | for (phase = 0; phase < 2; phase++) { | ||
2773 | for (dir = 1; dir < 0x10; dir <<= 1) { | ||
2774 | int x1, y1, corner = FALSE; | ||
2775 | /* | ||
2776 | * If at least one barrier terminates at the corner | ||
2777 | * between dir and A(dir), draw a barrier corner. | ||
2778 | */ | ||
2779 | if (barrier(state, GX(x), GY(y)) & (dir | A(dir))) { | ||
2780 | corner = TRUE; | ||
2781 | } else { | ||
2782 | /* | ||
2783 | * Only count barriers terminating at this corner | ||
2784 | * if they're physically next to the corner. (That | ||
2785 | * is, if they've wrapped round from the far side | ||
2786 | * of the screen, they don't count.) | ||
2787 | */ | ||
2788 | x1 = x + X(dir); | ||
2789 | y1 = y + Y(dir); | ||
2790 | if (x1 >= 0 && x1 < state->width && | ||
2791 | y1 >= 0 && y1 < state->height && | ||
2792 | (barrier(state, GX(x1), GY(y1)) & A(dir))) { | ||
2793 | corner = TRUE; | ||
2794 | } else { | ||
2795 | x1 = x + X(A(dir)); | ||
2796 | y1 = y + Y(A(dir)); | ||
2797 | if (x1 >= 0 && x1 < state->width && | ||
2798 | y1 >= 0 && y1 < state->height && | ||
2799 | (barrier(state, GX(x1), GY(y1)) & dir)) | ||
2800 | corner = TRUE; | ||
2801 | } | ||
2802 | } | ||
2803 | |||
2804 | if (corner) { | ||
2805 | /* | ||
2806 | * At least one barrier terminates here. Draw a | ||
2807 | * corner. | ||
2808 | */ | ||
2809 | draw_barrier_corner(dr, ds, x, y, | ||
2810 | X(dir)+X(A(dir)), Y(dir)+Y(A(dir)), | ||
2811 | phase); | ||
2812 | } | ||
2813 | } | ||
2814 | |||
2815 | for (dir = 1; dir < 0x10; dir <<= 1) | ||
2816 | if (barrier(state, GX(x), GY(y)) & dir) | ||
2817 | draw_barrier(dr, ds, x, y, dir, phase); | ||
2818 | } | ||
2819 | |||
2820 | unclip(dr); | ||
2821 | |||
2822 | draw_update(dr, bx, by, TILE_SIZE+TILE_BORDER, TILE_SIZE+TILE_BORDER); | ||
2823 | } | ||
2824 | |||
2825 | static void game_redraw(drawing *dr, game_drawstate *ds, | ||
2826 | const game_state *oldstate, const game_state *state, | ||
2827 | int dir, const game_ui *ui, | ||
2828 | float t, float ft) | ||
2829 | { | ||
2830 | int x, y, tx, ty, frame, last_rotate_dir, moved_origin = FALSE; | ||
2831 | unsigned char *active; | ||
2832 | int *loops; | ||
2833 | float angle = 0.0; | ||
2834 | |||
2835 | /* | ||
2836 | * Clear the screen, and draw the exterior barrier lines, if | ||
2837 | * this is our first call or if the origin has changed. | ||
2838 | */ | ||
2839 | if (!ds->started || ui->org_x != ds->org_x || ui->org_y != ds->org_y) { | ||
2840 | int phase; | ||
2841 | |||
2842 | ds->started = TRUE; | ||
2843 | |||
2844 | draw_rect(dr, 0, 0, | ||
2845 | WINDOW_OFFSET * 2 + TILE_SIZE * state->width + TILE_BORDER, | ||
2846 | WINDOW_OFFSET * 2 + TILE_SIZE * state->height + TILE_BORDER, | ||
2847 | COL_BACKGROUND); | ||
2848 | |||
2849 | ds->org_x = ui->org_x; | ||
2850 | ds->org_y = ui->org_y; | ||
2851 | moved_origin = TRUE; | ||
2852 | |||
2853 | draw_update(dr, 0, 0, | ||
2854 | WINDOW_OFFSET*2 + TILE_SIZE*state->width + TILE_BORDER, | ||
2855 | WINDOW_OFFSET*2 + TILE_SIZE*state->height + TILE_BORDER); | ||
2856 | |||
2857 | for (phase = 0; phase < 2; phase++) { | ||
2858 | |||
2859 | for (x = 0; x < ds->width; x++) { | ||
2860 | if (x+1 < ds->width) { | ||
2861 | if (barrier(state, GX(x), GY(0)) & R) | ||
2862 | draw_barrier_corner(dr, ds, x, -1, +1, +1, phase); | ||
2863 | if (barrier(state, GX(x), GY(ds->height-1)) & R) | ||
2864 | draw_barrier_corner(dr, ds, x, ds->height, +1, -1, phase); | ||
2865 | } | ||
2866 | if (barrier(state, GX(x), GY(0)) & U) { | ||
2867 | draw_barrier_corner(dr, ds, x, -1, -1, +1, phase); | ||
2868 | draw_barrier_corner(dr, ds, x, -1, +1, +1, phase); | ||
2869 | draw_barrier(dr, ds, x, -1, D, phase); | ||
2870 | } | ||
2871 | if (barrier(state, GX(x), GY(ds->height-1)) & D) { | ||
2872 | draw_barrier_corner(dr, ds, x, ds->height, -1, -1, phase); | ||
2873 | draw_barrier_corner(dr, ds, x, ds->height, +1, -1, phase); | ||
2874 | draw_barrier(dr, ds, x, ds->height, U, phase); | ||
2875 | } | ||
2876 | } | ||
2877 | |||
2878 | for (y = 0; y < ds->height; y++) { | ||
2879 | if (y+1 < ds->height) { | ||
2880 | if (barrier(state, GX(0), GY(y)) & D) | ||
2881 | draw_barrier_corner(dr, ds, -1, y, +1, +1, phase); | ||
2882 | if (barrier(state, GX(ds->width-1), GY(y)) & D) | ||
2883 | draw_barrier_corner(dr, ds, ds->width, y, -1, +1, phase); | ||
2884 | } | ||
2885 | if (barrier(state, GX(0), GY(y)) & L) { | ||
2886 | draw_barrier_corner(dr, ds, -1, y, +1, -1, phase); | ||
2887 | draw_barrier_corner(dr, ds, -1, y, +1, +1, phase); | ||
2888 | draw_barrier(dr, ds, -1, y, R, phase); | ||
2889 | } | ||
2890 | if (barrier(state, GX(ds->width-1), GY(y)) & R) { | ||
2891 | draw_barrier_corner(dr, ds, ds->width, y, -1, -1, phase); | ||
2892 | draw_barrier_corner(dr, ds, ds->width, y, -1, +1, phase); | ||
2893 | draw_barrier(dr, ds, ds->width, y, L, phase); | ||
2894 | } | ||
2895 | } | ||
2896 | } | ||
2897 | } | ||
2898 | |||
2899 | tx = ty = -1; | ||
2900 | last_rotate_dir = dir==-1 ? oldstate->last_rotate_dir : | ||
2901 | state->last_rotate_dir; | ||
2902 | if (oldstate && (t < ROTATE_TIME) && last_rotate_dir) { | ||
2903 | /* | ||
2904 | * We're animating a single tile rotation. Find the turning | ||
2905 | * tile. | ||
2906 | */ | ||
2907 | tx = (dir==-1 ? oldstate->last_rotate_x : state->last_rotate_x); | ||
2908 | ty = (dir==-1 ? oldstate->last_rotate_y : state->last_rotate_y); | ||
2909 | angle = last_rotate_dir * dir * 90.0F * (t / ROTATE_TIME); | ||
2910 | state = oldstate; | ||
2911 | } | ||
2912 | |||
2913 | frame = -1; | ||
2914 | if (ft > 0) { | ||
2915 | /* | ||
2916 | * We're animating a completion flash. Find which frame | ||
2917 | * we're at. | ||
2918 | */ | ||
2919 | frame = (int)(ft / FLASH_FRAME); | ||
2920 | } | ||
2921 | |||
2922 | /* | ||
2923 | * Draw any tile which differs from the way it was last drawn. | ||
2924 | */ | ||
2925 | active = compute_active(state, ui->cx, ui->cy); | ||
2926 | loops = compute_loops(state); | ||
2927 | |||
2928 | for (x = 0; x < ds->width; x++) | ||
2929 | for (y = 0; y < ds->height; y++) { | ||
2930 | int c = tile(state, GX(x), GY(y)) | | ||
2931 | index(state, active, GX(x), GY(y)) | | ||
2932 | index(state, loops, GX(x), GY(y)); | ||
2933 | int is_src = GX(x) == ui->cx && GY(y) == ui->cy; | ||
2934 | int is_anim = GX(x) == tx && GY(y) == ty; | ||
2935 | int is_cursor = ui->cur_visible && | ||
2936 | GX(x) == ui->cur_x && GY(y) == ui->cur_y; | ||
2937 | |||
2938 | /* | ||
2939 | * In a completion flash, we adjust the LOCKED bit | ||
2940 | * depending on our distance from the centre point and | ||
2941 | * the frame number. | ||
2942 | */ | ||
2943 | if (frame >= 0) { | ||
2944 | int rcx = RX(ui->cx), rcy = RY(ui->cy); | ||
2945 | int xdist, ydist, dist; | ||
2946 | xdist = (x < rcx ? rcx - x : x - rcx); | ||
2947 | ydist = (y < rcy ? rcy - y : y - rcy); | ||
2948 | dist = (xdist > ydist ? xdist : ydist); | ||
2949 | |||
2950 | if (frame >= dist && frame < dist+4) { | ||
2951 | int lock = (frame - dist) & 1; | ||
2952 | lock = lock ? LOCKED : 0; | ||
2953 | c = (c &~ LOCKED) | lock; | ||
2954 | } | ||
2955 | } | ||
2956 | |||
2957 | if (moved_origin || | ||
2958 | index(state, ds->visible, x, y) != c || | ||
2959 | index(state, ds->visible, x, y) == -1 || | ||
2960 | is_src || is_anim || is_cursor) { | ||
2961 | draw_tile(dr, state, ds, x, y, c, | ||
2962 | is_src, (is_anim ? angle : 0.0F), is_cursor); | ||
2963 | if (is_src || is_anim || is_cursor) | ||
2964 | index(state, ds->visible, x, y) = -1; | ||
2965 | else | ||
2966 | index(state, ds->visible, x, y) = c; | ||
2967 | } | ||
2968 | } | ||
2969 | |||
2970 | /* | ||
2971 | * Update the status bar. | ||
2972 | */ | ||
2973 | { | ||
2974 | char statusbuf[256], *p; | ||
2975 | int i, n, n2, a; | ||
2976 | int complete = FALSE; | ||
2977 | |||
2978 | p = statusbuf; | ||
2979 | *p = '\0'; /* ensure even an empty status string is terminated */ | ||
2980 | |||
2981 | if (state->used_solve) { | ||
2982 | p += sprintf(p, "Auto-solved. "); | ||
2983 | complete = TRUE; | ||
2984 | } else if (state->completed) { | ||
2985 | p += sprintf(p, "COMPLETED! "); | ||
2986 | complete = TRUE; | ||
2987 | } | ||
2988 | |||
2989 | /* | ||
2990 | * Omit the 'Active: n/N' counter completely if the source | ||
2991 | * tile is a completely empty one, because then the active | ||
2992 | * count can't help but read '1'. | ||
2993 | */ | ||
2994 | if (tile(state, ui->cx, ui->cy) & 0xF) { | ||
2995 | n = state->width * state->height; | ||
2996 | for (i = a = n2 = 0; i < n; i++) { | ||
2997 | if (active[i]) | ||
2998 | a++; | ||
2999 | if (state->tiles[i] & 0xF) | ||
3000 | n2++; | ||
3001 | } | ||
3002 | |||
3003 | /* | ||
3004 | * Also, if we're displaying a completion indicator and | ||
3005 | * the game is still in its completed state (i.e. every | ||
3006 | * tile is active), we might as well omit this too. | ||
3007 | */ | ||
3008 | if (!complete || a < n2) | ||
3009 | p += sprintf(p, "Active: %d/%d", a, n2); | ||
3010 | } | ||
3011 | |||
3012 | status_bar(dr, statusbuf); | ||
3013 | } | ||
3014 | |||
3015 | sfree(active); | ||
3016 | sfree(loops); | ||
3017 | } | ||
3018 | |||
3019 | static float game_anim_length(const game_state *oldstate, | ||
3020 | const game_state *newstate, int dir, game_ui *ui) | ||
3021 | { | ||
3022 | int last_rotate_dir; | ||
3023 | |||
3024 | /* | ||
3025 | * Don't animate if last_rotate_dir is zero. | ||
3026 | */ | ||
3027 | last_rotate_dir = dir==-1 ? oldstate->last_rotate_dir : | ||
3028 | newstate->last_rotate_dir; | ||
3029 | if (last_rotate_dir) | ||
3030 | return ROTATE_TIME; | ||
3031 | |||
3032 | return 0.0F; | ||
3033 | } | ||
3034 | |||
3035 | static float game_flash_length(const game_state *oldstate, | ||
3036 | const game_state *newstate, int dir, game_ui *ui) | ||
3037 | { | ||
3038 | /* | ||
3039 | * If the game has just been completed, we display a completion | ||
3040 | * flash. | ||
3041 | */ | ||
3042 | if (!oldstate->completed && newstate->completed && | ||
3043 | !oldstate->used_solve && !newstate->used_solve) { | ||
3044 | int size = 0; | ||
3045 | if (size < newstate->width) | ||
3046 | size = newstate->width; | ||
3047 | if (size < newstate->height) | ||
3048 | size = newstate->height; | ||
3049 | return FLASH_FRAME * (size+4); | ||
3050 | } | ||
3051 | |||
3052 | return 0.0F; | ||
3053 | } | ||
3054 | |||
3055 | static int game_status(const game_state *state) | ||
3056 | { | ||
3057 | return state->completed ? +1 : 0; | ||
3058 | } | ||
3059 | |||
3060 | static int game_timing_state(const game_state *state, game_ui *ui) | ||
3061 | { | ||
3062 | return TRUE; | ||
3063 | } | ||
3064 | |||
3065 | static void game_print_size(const game_params *params, float *x, float *y) | ||
3066 | { | ||
3067 | int pw, ph; | ||
3068 | |||
3069 | /* | ||
3070 | * I'll use 8mm squares by default. | ||
3071 | */ | ||
3072 | game_compute_size(params, 800, &pw, &ph); | ||
3073 | *x = pw / 100.0F; | ||
3074 | *y = ph / 100.0F; | ||
3075 | } | ||
3076 | |||
3077 | static void draw_diagram(drawing *dr, game_drawstate *ds, int x, int y, | ||
3078 | int topleft, int v, int drawlines, int ink) | ||
3079 | { | ||
3080 | int tx, ty, cx, cy, r, br, k, thick; | ||
3081 | |||
3082 | tx = WINDOW_OFFSET + TILE_SIZE * x; | ||
3083 | ty = WINDOW_OFFSET + TILE_SIZE * y; | ||
3084 | |||
3085 | /* | ||
3086 | * Find our centre point. | ||
3087 | */ | ||
3088 | if (topleft) { | ||
3089 | cx = tx + (v & L ? TILE_SIZE / 4 : TILE_SIZE / 6); | ||
3090 | cy = ty + (v & U ? TILE_SIZE / 4 : TILE_SIZE / 6); | ||
3091 | r = TILE_SIZE / 8; | ||
3092 | br = TILE_SIZE / 32; | ||
3093 | } else { | ||
3094 | cx = tx + TILE_SIZE / 2; | ||
3095 | cy = ty + TILE_SIZE / 2; | ||
3096 | r = TILE_SIZE / 2; | ||
3097 | br = TILE_SIZE / 8; | ||
3098 | } | ||
3099 | thick = r / 20; | ||
3100 | |||
3101 | /* | ||
3102 | * Draw the square block if we have an endpoint. | ||
3103 | */ | ||
3104 | if (v == 1 || v == 2 || v == 4 || v == 8) | ||
3105 | draw_rect(dr, cx - br, cy - br, br*2, br*2, ink); | ||
3106 | |||
3107 | /* | ||
3108 | * Draw each radial line. | ||
3109 | */ | ||
3110 | if (drawlines) { | ||
3111 | for (k = 1; k < 16; k *= 2) | ||
3112 | if (v & k) { | ||
3113 | int x1 = min(cx, cx + (r-thick) * X(k)); | ||
3114 | int x2 = max(cx, cx + (r-thick) * X(k)); | ||
3115 | int y1 = min(cy, cy + (r-thick) * Y(k)); | ||
3116 | int y2 = max(cy, cy + (r-thick) * Y(k)); | ||
3117 | draw_rect(dr, x1 - thick, y1 - thick, | ||
3118 | (x2 - x1) + 2*thick, (y2 - y1) + 2*thick, ink); | ||
3119 | } | ||
3120 | } | ||
3121 | } | ||
3122 | |||
3123 | static void game_print(drawing *dr, const game_state *state, int tilesize) | ||
3124 | { | ||
3125 | int w = state->width, h = state->height; | ||
3126 | int ink = print_mono_colour(dr, 0); | ||
3127 | int x, y; | ||
3128 | |||
3129 | /* Ick: fake up `ds->tilesize' for macro expansion purposes */ | ||
3130 | game_drawstate ads, *ds = &ads; | ||
3131 | game_set_size(dr, ds, NULL, tilesize); | ||
3132 | |||
3133 | /* | ||
3134 | * Border. | ||
3135 | */ | ||
3136 | print_line_width(dr, TILE_SIZE / (state->wrapping ? 128 : 12)); | ||
3137 | draw_rect_outline(dr, WINDOW_OFFSET, WINDOW_OFFSET, | ||
3138 | TILE_SIZE * w, TILE_SIZE * h, ink); | ||
3139 | |||
3140 | /* | ||
3141 | * Grid. | ||
3142 | */ | ||
3143 | print_line_width(dr, TILE_SIZE / 128); | ||
3144 | for (x = 1; x < w; x++) | ||
3145 | draw_line(dr, WINDOW_OFFSET + TILE_SIZE * x, WINDOW_OFFSET, | ||
3146 | WINDOW_OFFSET + TILE_SIZE * x, WINDOW_OFFSET + TILE_SIZE * h, | ||
3147 | ink); | ||
3148 | for (y = 1; y < h; y++) | ||
3149 | draw_line(dr, WINDOW_OFFSET, WINDOW_OFFSET + TILE_SIZE * y, | ||
3150 | WINDOW_OFFSET + TILE_SIZE * w, WINDOW_OFFSET + TILE_SIZE * y, | ||
3151 | ink); | ||
3152 | |||
3153 | /* | ||
3154 | * Barriers. | ||
3155 | */ | ||
3156 | for (y = 0; y <= h; y++) | ||
3157 | for (x = 0; x <= w; x++) { | ||
3158 | int b = barrier(state, x % w, y % h); | ||
3159 | if (x < w && (b & U)) | ||
3160 | draw_rect(dr, WINDOW_OFFSET + TILE_SIZE * x - TILE_SIZE/24, | ||
3161 | WINDOW_OFFSET + TILE_SIZE * y - TILE_SIZE/24, | ||
3162 | TILE_SIZE + TILE_SIZE/24 * 2, TILE_SIZE/24 * 2, ink); | ||
3163 | if (y < h && (b & L)) | ||
3164 | draw_rect(dr, WINDOW_OFFSET + TILE_SIZE * x - TILE_SIZE/24, | ||
3165 | WINDOW_OFFSET + TILE_SIZE * y - TILE_SIZE/24, | ||
3166 | TILE_SIZE/24 * 2, TILE_SIZE + TILE_SIZE/24 * 2, ink); | ||
3167 | } | ||
3168 | |||
3169 | /* | ||
3170 | * Grid contents. | ||
3171 | */ | ||
3172 | for (y = 0; y < h; y++) | ||
3173 | for (x = 0; x < w; x++) { | ||
3174 | int vx, v = tile(state, x, y); | ||
3175 | int locked = v & LOCKED; | ||
3176 | |||
3177 | v &= 0xF; | ||
3178 | |||
3179 | /* | ||
3180 | * Rotate into a standard orientation for the top left | ||
3181 | * corner diagram. | ||
3182 | */ | ||
3183 | vx = v; | ||
3184 | while (vx != 0 && vx != 15 && vx != 1 && vx != 9 && vx != 13 && | ||
3185 | vx != 5) | ||
3186 | vx = A(vx); | ||
3187 | |||
3188 | /* | ||
3189 | * Draw the top left corner diagram. | ||
3190 | */ | ||
3191 | draw_diagram(dr, ds, x, y, TRUE, vx, TRUE, ink); | ||
3192 | |||
3193 | /* | ||
3194 | * Draw the real solution diagram, if we're doing so. | ||
3195 | */ | ||
3196 | draw_diagram(dr, ds, x, y, FALSE, v, locked, ink); | ||
3197 | } | ||
3198 | } | ||
3199 | |||
3200 | #ifdef COMBINED | ||
3201 | #define thegame net | ||
3202 | #endif | ||
3203 | |||
3204 | const struct game thegame = { | ||
3205 | "Net", "games.net", "net", | ||
3206 | default_params, | ||
3207 | game_fetch_preset, NULL, | ||
3208 | decode_params, | ||
3209 | encode_params, | ||
3210 | free_params, | ||
3211 | dup_params, | ||
3212 | TRUE, game_configure, custom_params, | ||
3213 | validate_params, | ||
3214 | new_game_desc, | ||
3215 | validate_desc, | ||
3216 | new_game, | ||
3217 | dup_game, | ||
3218 | free_game, | ||
3219 | TRUE, solve_game, | ||
3220 | FALSE, game_can_format_as_text_now, game_text_format, | ||
3221 | new_ui, | ||
3222 | free_ui, | ||
3223 | encode_ui, | ||
3224 | decode_ui, | ||
3225 | game_changed_state, | ||
3226 | interpret_move, | ||
3227 | execute_move, | ||
3228 | PREFERRED_TILE_SIZE, game_compute_size, game_set_size, | ||
3229 | game_colours, | ||
3230 | game_new_drawstate, | ||
3231 | game_free_drawstate, | ||
3232 | game_redraw, | ||
3233 | game_anim_length, | ||
3234 | game_flash_length, | ||
3235 | game_status, | ||
3236 | TRUE, FALSE, game_print_size, game_print, | ||
3237 | TRUE, /* wants_statusbar */ | ||
3238 | FALSE, game_timing_state, | ||
3239 | 0, /* flags */ | ||
3240 | }; | ||