diff options
Diffstat (limited to 'apps/plugins/puzzles/src/galaxies.c')
-rw-r--r-- | apps/plugins/puzzles/src/galaxies.c | 3995 |
1 files changed, 3995 insertions, 0 deletions
diff --git a/apps/plugins/puzzles/src/galaxies.c b/apps/plugins/puzzles/src/galaxies.c new file mode 100644 index 0000000000..f4f75c629c --- /dev/null +++ b/apps/plugins/puzzles/src/galaxies.c | |||
@@ -0,0 +1,3995 @@ | |||
1 | /* | ||
2 | * galaxies.c: implementation of 'Tentai Show' from Nikoli, | ||
3 | * also sometimes called 'Spiral Galaxies'. | ||
4 | * | ||
5 | * Notes: | ||
6 | * | ||
7 | * Grid is stored as size (2n-1), holding edges as well as spaces | ||
8 | * (and thus vertices too, at edge intersections). | ||
9 | * | ||
10 | * Any dot will thus be positioned at one of our grid points, | ||
11 | * which saves any faffing with half-of-a-square stuff. | ||
12 | * | ||
13 | * Edges have on/off state; obviously the actual edges of the | ||
14 | * board are fixed to on, and everything else starts as off. | ||
15 | * | ||
16 | * TTD: | ||
17 | * Cleverer solver | ||
18 | * Think about how to display remote groups of tiles? | ||
19 | * | ||
20 | * Bugs: | ||
21 | * | ||
22 | * Notable puzzle IDs: | ||
23 | * | ||
24 | * Nikoli's example [web site has wrong highlighting] | ||
25 | * (at http://www.nikoli.co.jp/en/puzzles/astronomical_show/): | ||
26 | * 5x5:eBbbMlaBbOEnf | ||
27 | * | ||
28 | * The 'spiral galaxies puzzles are NP-complete' paper | ||
29 | * (at http://www.stetson.edu/~efriedma/papers/spiral.pdf): | ||
30 | * 7x7:chpgdqqqoezdddki | ||
31 | * | ||
32 | * Puzzle competition pdf examples | ||
33 | * (at http://www.puzzleratings.org/Yurekli2006puz.pdf): | ||
34 | * 6x6:EDbaMucCohbrecEi | ||
35 | * 10x10:beFbufEEzowDlxldibMHezBQzCdcFzjlci | ||
36 | * 13x13:dCemIHFFkJajjgDfdbdBzdzEgjccoPOcztHjBczLDjczqktJjmpreivvNcggFi | ||
37 | * | ||
38 | */ | ||
39 | |||
40 | #include <stdio.h> | ||
41 | #include <stdlib.h> | ||
42 | #include <string.h> | ||
43 | #include <assert.h> | ||
44 | #include <ctype.h> | ||
45 | #include <math.h> | ||
46 | |||
47 | #include "puzzles.h" | ||
48 | |||
49 | #ifdef DEBUGGING | ||
50 | #define solvep debug | ||
51 | #else | ||
52 | int solver_show_working; | ||
53 | #define solvep(x) do { if (solver_show_working) { printf x; } } while(0) | ||
54 | #endif | ||
55 | |||
56 | #ifdef STANDALONE_PICTURE_GENERATOR | ||
57 | /* | ||
58 | * Dirty hack to enable the generator to construct a game ID which | ||
59 | * solves to a specified black-and-white bitmap. We define a global | ||
60 | * variable here which gives the desired colour of each square, and | ||
61 | * we arrange that the grid generator never merges squares of | ||
62 | * different colours. | ||
63 | * | ||
64 | * The bitmap as stored here is a simple int array (at these sizes | ||
65 | * it isn't worth doing fiddly bit-packing). picture[y*w+x] is 1 | ||
66 | * iff the pixel at (x,y) is intended to be black. | ||
67 | * | ||
68 | * (It might be nice to be able to specify some pixels as | ||
69 | * don't-care, to give the generator more leeway. But that might be | ||
70 | * fiddly.) | ||
71 | */ | ||
72 | static int *picture; | ||
73 | #endif | ||
74 | |||
75 | enum { | ||
76 | COL_BACKGROUND, | ||
77 | COL_WHITEBG, | ||
78 | COL_BLACKBG, | ||
79 | COL_WHITEDOT, | ||
80 | COL_BLACKDOT, | ||
81 | COL_GRID, | ||
82 | COL_EDGE, | ||
83 | COL_ARROW, | ||
84 | COL_CURSOR, | ||
85 | NCOLOURS | ||
86 | }; | ||
87 | |||
88 | #define DIFFLIST(A) \ | ||
89 | A(NORMAL,Normal,n) \ | ||
90 | A(UNREASONABLE,Unreasonable,u) | ||
91 | |||
92 | #define ENUM(upper,title,lower) DIFF_ ## upper, | ||
93 | #define TITLE(upper,title,lower) #title, | ||
94 | #define ENCODE(upper,title,lower) #lower | ||
95 | #define CONFIG(upper,title,lower) ":" #title | ||
96 | enum { DIFFLIST(ENUM) | ||
97 | DIFF_IMPOSSIBLE, DIFF_AMBIGUOUS, DIFF_UNFINISHED, DIFF_MAX }; | ||
98 | static char const *const galaxies_diffnames[] = { | ||
99 | DIFFLIST(TITLE) "Impossible", "Ambiguous", "Unfinished" }; | ||
100 | static char const galaxies_diffchars[] = DIFFLIST(ENCODE); | ||
101 | #define DIFFCONFIG DIFFLIST(CONFIG) | ||
102 | |||
103 | struct game_params { | ||
104 | /* X and Y is the area of the board as seen by | ||
105 | * the user, not the (2n+1) area the game uses. */ | ||
106 | int w, h, diff; | ||
107 | }; | ||
108 | |||
109 | enum { s_tile, s_edge, s_vertex }; | ||
110 | |||
111 | #define F_DOT 1 /* there's a dot here */ | ||
112 | #define F_EDGE_SET 2 /* the edge is set */ | ||
113 | #define F_TILE_ASSOC 4 /* this tile is associated with a dot. */ | ||
114 | #define F_DOT_BLACK 8 /* (ui only) dot is black. */ | ||
115 | #define F_MARK 16 /* scratch flag */ | ||
116 | #define F_REACHABLE 32 | ||
117 | #define F_SCRATCH 64 | ||
118 | #define F_MULTIPLE 128 | ||
119 | #define F_DOT_HOLD 256 | ||
120 | #define F_GOOD 512 | ||
121 | |||
122 | typedef struct space { | ||
123 | int x, y; /* its position */ | ||
124 | int type; | ||
125 | unsigned int flags; | ||
126 | int dotx, doty; /* if flags & F_TILE_ASSOC */ | ||
127 | int nassoc; /* if flags & F_DOT */ | ||
128 | } space; | ||
129 | |||
130 | #define INGRID(s,x,y) ((x) >= 0 && (y) >= 0 && \ | ||
131 | (x) < (state)->sx && (y) < (state)->sy) | ||
132 | #define INUI(s,x,y) ((x) > 0 && (y) > 0 && \ | ||
133 | (x) < ((state)->sx-1) && (y) < ((state)->sy-1)) | ||
134 | |||
135 | #define GRID(s,g,x,y) ((s)->g[((y)*(s)->sx)+(x)]) | ||
136 | #define SPACE(s,x,y) GRID(s,grid,x,y) | ||
137 | |||
138 | struct game_state { | ||
139 | int w, h; /* size from params */ | ||
140 | int sx, sy; /* allocated size, (2x-1)*(2y-1) */ | ||
141 | space *grid; | ||
142 | int completed, used_solve; | ||
143 | int ndots; | ||
144 | space **dots; | ||
145 | |||
146 | midend *me; /* to call supersede_game_desc */ | ||
147 | int cdiff; /* difficulty of current puzzle (for status bar), | ||
148 | or -1 if stale. */ | ||
149 | }; | ||
150 | |||
151 | static int check_complete(const game_state *state, int *dsf, int *colours); | ||
152 | static int solver_state(game_state *state, int maxdiff); | ||
153 | static int solver_obvious(game_state *state); | ||
154 | static int solver_obvious_dot(game_state *state, space *dot); | ||
155 | static space *space_opposite_dot(const game_state *state, const space *sp, | ||
156 | const space *dot); | ||
157 | static space *tile_opposite(const game_state *state, const space *sp); | ||
158 | |||
159 | /* ---------------------------------------------------------- | ||
160 | * Game parameters and presets | ||
161 | */ | ||
162 | |||
163 | /* make up some sensible default sizes */ | ||
164 | |||
165 | #define DEFAULT_PRESET 0 | ||
166 | |||
167 | static const game_params galaxies_presets[] = { | ||
168 | { 7, 7, DIFF_NORMAL }, | ||
169 | { 7, 7, DIFF_UNREASONABLE }, | ||
170 | { 10, 10, DIFF_NORMAL }, | ||
171 | { 15, 15, DIFF_NORMAL }, | ||
172 | }; | ||
173 | |||
174 | static int game_fetch_preset(int i, char **name, game_params **params) | ||
175 | { | ||
176 | game_params *ret; | ||
177 | char buf[80]; | ||
178 | |||
179 | if (i < 0 || i >= lenof(galaxies_presets)) | ||
180 | return FALSE; | ||
181 | |||
182 | ret = snew(game_params); | ||
183 | *ret = galaxies_presets[i]; /* structure copy */ | ||
184 | |||
185 | sprintf(buf, "%dx%d %s", ret->w, ret->h, | ||
186 | galaxies_diffnames[ret->diff]); | ||
187 | |||
188 | if (name) *name = dupstr(buf); | ||
189 | *params = ret; | ||
190 | return TRUE; | ||
191 | } | ||
192 | |||
193 | static game_params *default_params(void) | ||
194 | { | ||
195 | game_params *ret; | ||
196 | game_fetch_preset(DEFAULT_PRESET, NULL, &ret); | ||
197 | return ret; | ||
198 | } | ||
199 | |||
200 | static void free_params(game_params *params) | ||
201 | { | ||
202 | sfree(params); | ||
203 | } | ||
204 | |||
205 | static game_params *dup_params(const game_params *params) | ||
206 | { | ||
207 | game_params *ret = snew(game_params); | ||
208 | *ret = *params; /* structure copy */ | ||
209 | return ret; | ||
210 | } | ||
211 | |||
212 | static void decode_params(game_params *params, char const *string) | ||
213 | { | ||
214 | params->h = params->w = atoi(string); | ||
215 | params->diff = DIFF_NORMAL; | ||
216 | while (*string && isdigit((unsigned char)*string)) string++; | ||
217 | if (*string == 'x') { | ||
218 | string++; | ||
219 | params->h = atoi(string); | ||
220 | while (*string && isdigit((unsigned char)*string)) string++; | ||
221 | } | ||
222 | if (*string == 'd') { | ||
223 | int i; | ||
224 | string++; | ||
225 | for (i = 0; i <= DIFF_UNREASONABLE; i++) | ||
226 | if (*string == galaxies_diffchars[i]) | ||
227 | params->diff = i; | ||
228 | if (*string) string++; | ||
229 | } | ||
230 | } | ||
231 | |||
232 | static char *encode_params(const game_params *params, int full) | ||
233 | { | ||
234 | char str[80]; | ||
235 | sprintf(str, "%dx%d", params->w, params->h); | ||
236 | if (full) | ||
237 | sprintf(str + strlen(str), "d%c", galaxies_diffchars[params->diff]); | ||
238 | return dupstr(str); | ||
239 | } | ||
240 | |||
241 | static config_item *game_configure(const game_params *params) | ||
242 | { | ||
243 | config_item *ret; | ||
244 | char buf[80]; | ||
245 | |||
246 | ret = snewn(4, config_item); | ||
247 | |||
248 | ret[0].name = "Width"; | ||
249 | ret[0].type = C_STRING; | ||
250 | sprintf(buf, "%d", params->w); | ||
251 | ret[0].sval = dupstr(buf); | ||
252 | ret[0].ival = 0; | ||
253 | |||
254 | ret[1].name = "Height"; | ||
255 | ret[1].type = C_STRING; | ||
256 | sprintf(buf, "%d", params->h); | ||
257 | ret[1].sval = dupstr(buf); | ||
258 | ret[1].ival = 0; | ||
259 | |||
260 | ret[2].name = "Difficulty"; | ||
261 | ret[2].type = C_CHOICES; | ||
262 | ret[2].sval = DIFFCONFIG; | ||
263 | ret[2].ival = params->diff; | ||
264 | |||
265 | ret[3].name = NULL; | ||
266 | ret[3].type = C_END; | ||
267 | ret[3].sval = NULL; | ||
268 | ret[3].ival = 0; | ||
269 | |||
270 | return ret; | ||
271 | } | ||
272 | |||
273 | static game_params *custom_params(const config_item *cfg) | ||
274 | { | ||
275 | game_params *ret = snew(game_params); | ||
276 | |||
277 | ret->w = atoi(cfg[0].sval); | ||
278 | ret->h = atoi(cfg[1].sval); | ||
279 | ret->diff = cfg[2].ival; | ||
280 | |||
281 | return ret; | ||
282 | } | ||
283 | |||
284 | static char *validate_params(const game_params *params, int full) | ||
285 | { | ||
286 | if (params->w < 3 || params->h < 3) | ||
287 | return "Width and height must both be at least 3"; | ||
288 | /* | ||
289 | * This shouldn't be able to happen at all, since decode_params | ||
290 | * and custom_params will never generate anything that isn't | ||
291 | * within range. | ||
292 | */ | ||
293 | assert(params->diff <= DIFF_UNREASONABLE); | ||
294 | |||
295 | return NULL; | ||
296 | } | ||
297 | |||
298 | /* ---------------------------------------------------------- | ||
299 | * Game utility functions. | ||
300 | */ | ||
301 | |||
302 | static void add_dot(space *space) { | ||
303 | assert(!(space->flags & F_DOT)); | ||
304 | space->flags |= F_DOT; | ||
305 | space->nassoc = 0; | ||
306 | } | ||
307 | |||
308 | static void remove_dot(space *space) { | ||
309 | assert(space->flags & F_DOT); | ||
310 | space->flags &= ~F_DOT; | ||
311 | } | ||
312 | |||
313 | static void remove_assoc(const game_state *state, space *tile) { | ||
314 | if (tile->flags & F_TILE_ASSOC) { | ||
315 | SPACE(state, tile->dotx, tile->doty).nassoc--; | ||
316 | tile->flags &= ~F_TILE_ASSOC; | ||
317 | tile->dotx = -1; | ||
318 | tile->doty = -1; | ||
319 | } | ||
320 | } | ||
321 | |||
322 | static void remove_assoc_with_opposite(game_state *state, space *tile) { | ||
323 | space *opposite; | ||
324 | |||
325 | if (!(tile->flags & F_TILE_ASSOC)) { | ||
326 | return; | ||
327 | } | ||
328 | |||
329 | opposite = tile_opposite(state, tile); | ||
330 | remove_assoc(state, tile); | ||
331 | |||
332 | if (opposite != NULL && opposite != tile) { | ||
333 | remove_assoc(state, opposite); | ||
334 | } | ||
335 | } | ||
336 | |||
337 | static void add_assoc(const game_state *state, space *tile, space *dot) { | ||
338 | remove_assoc(state, tile); | ||
339 | |||
340 | #ifdef STANDALONE_PICTURE_GENERATOR | ||
341 | if (picture) | ||
342 | assert(!picture[(tile->y/2) * state->w + (tile->x/2)] == | ||
343 | !(dot->flags & F_DOT_BLACK)); | ||
344 | #endif | ||
345 | tile->flags |= F_TILE_ASSOC; | ||
346 | tile->dotx = dot->x; | ||
347 | tile->doty = dot->y; | ||
348 | dot->nassoc++; | ||
349 | /*debug(("add_assoc sp %d %d --> dot %d,%d, new nassoc %d.\n", | ||
350 | tile->x, tile->y, dot->x, dot->y, dot->nassoc));*/ | ||
351 | } | ||
352 | |||
353 | static void add_assoc_with_opposite(game_state *state, space *tile, space *dot) { | ||
354 | int *colors; | ||
355 | space *opposite = space_opposite_dot(state, tile, dot); | ||
356 | |||
357 | if (opposite == NULL) { | ||
358 | return; | ||
359 | } | ||
360 | if (opposite->flags & F_DOT) { | ||
361 | return; | ||
362 | } | ||
363 | |||
364 | colors = snewn(state->w * state->h, int); | ||
365 | check_complete(state, NULL, colors); | ||
366 | if (colors[(tile->y - 1)/2 * state->w + (tile->x - 1)/2]) { | ||
367 | sfree(colors); | ||
368 | return; | ||
369 | } | ||
370 | if (colors[(opposite->y - 1)/2 * state->w + (opposite->x - 1)/2]) { | ||
371 | sfree(colors); | ||
372 | return; | ||
373 | } | ||
374 | |||
375 | sfree(colors); | ||
376 | remove_assoc_with_opposite(state, tile); | ||
377 | add_assoc(state, tile, dot); | ||
378 | remove_assoc_with_opposite(state, opposite); | ||
379 | add_assoc(state, opposite, dot); | ||
380 | } | ||
381 | |||
382 | static space *sp2dot(const game_state *state, int x, int y) | ||
383 | { | ||
384 | space *sp = &SPACE(state, x, y); | ||
385 | if (!(sp->flags & F_TILE_ASSOC)) return NULL; | ||
386 | return &SPACE(state, sp->dotx, sp->doty); | ||
387 | } | ||
388 | |||
389 | #define IS_VERTICAL_EDGE(x) ((x % 2) == 0) | ||
390 | |||
391 | static int game_can_format_as_text_now(const game_params *params) | ||
392 | { | ||
393 | return TRUE; | ||
394 | } | ||
395 | |||
396 | static char *game_text_format(const game_state *state) | ||
397 | { | ||
398 | int maxlen = (state->sx+1)*state->sy, x, y; | ||
399 | char *ret, *p; | ||
400 | space *sp; | ||
401 | |||
402 | ret = snewn(maxlen+1, char); | ||
403 | p = ret; | ||
404 | |||
405 | for (y = 0; y < state->sy; y++) { | ||
406 | for (x = 0; x < state->sx; x++) { | ||
407 | sp = &SPACE(state, x, y); | ||
408 | if (sp->flags & F_DOT) | ||
409 | *p++ = 'o'; | ||
410 | #if 0 | ||
411 | else if (sp->flags & (F_REACHABLE|F_MULTIPLE|F_MARK)) | ||
412 | *p++ = (sp->flags & F_MULTIPLE) ? 'M' : | ||
413 | (sp->flags & F_REACHABLE) ? 'R' : 'X'; | ||
414 | #endif | ||
415 | else { | ||
416 | switch (sp->type) { | ||
417 | case s_tile: | ||
418 | if (sp->flags & F_TILE_ASSOC) { | ||
419 | space *dot = sp2dot(state, sp->x, sp->y); | ||
420 | if (dot && dot->flags & F_DOT) | ||
421 | *p++ = (dot->flags & F_DOT_BLACK) ? 'B' : 'W'; | ||
422 | else | ||
423 | *p++ = '?'; /* association with not-a-dot. */ | ||
424 | } else | ||
425 | *p++ = ' '; | ||
426 | break; | ||
427 | |||
428 | case s_vertex: | ||
429 | *p++ = '+'; | ||
430 | break; | ||
431 | |||
432 | case s_edge: | ||
433 | if (sp->flags & F_EDGE_SET) | ||
434 | *p++ = (IS_VERTICAL_EDGE(x)) ? '|' : '-'; | ||
435 | else | ||
436 | *p++ = ' '; | ||
437 | break; | ||
438 | |||
439 | default: | ||
440 | assert(!"shouldn't get here!"); | ||
441 | } | ||
442 | } | ||
443 | } | ||
444 | *p++ = '\n'; | ||
445 | } | ||
446 | |||
447 | assert(p - ret == maxlen); | ||
448 | *p = '\0'; | ||
449 | |||
450 | return ret; | ||
451 | } | ||
452 | |||
453 | static void dbg_state(const game_state *state) | ||
454 | { | ||
455 | #ifdef DEBUGGING | ||
456 | char *temp = game_text_format(state); | ||
457 | debug(("%s\n", temp)); | ||
458 | sfree(temp); | ||
459 | #endif | ||
460 | } | ||
461 | |||
462 | /* Space-enumeration callbacks should all return 1 for 'progress made', | ||
463 | * -1 for 'impossible', and 0 otherwise. */ | ||
464 | typedef int (*space_cb)(game_state *state, space *sp, void *ctx); | ||
465 | |||
466 | #define IMPOSSIBLE_QUITS 1 | ||
467 | |||
468 | static int foreach_sub(game_state *state, space_cb cb, unsigned int f, | ||
469 | void *ctx, int startx, int starty) | ||
470 | { | ||
471 | int x, y, progress = 0, impossible = 0, ret; | ||
472 | space *sp; | ||
473 | |||
474 | for (y = starty; y < state->sy; y += 2) { | ||
475 | sp = &SPACE(state, startx, y); | ||
476 | for (x = startx; x < state->sx; x += 2) { | ||
477 | ret = cb(state, sp, ctx); | ||
478 | if (ret == -1) { | ||
479 | if (f & IMPOSSIBLE_QUITS) return -1; | ||
480 | impossible = -1; | ||
481 | } else if (ret == 1) { | ||
482 | progress = 1; | ||
483 | } | ||
484 | sp += 2; | ||
485 | } | ||
486 | } | ||
487 | return impossible ? -1 : progress; | ||
488 | } | ||
489 | |||
490 | static int foreach_tile(game_state *state, space_cb cb, unsigned int f, | ||
491 | void *ctx) | ||
492 | { | ||
493 | return foreach_sub(state, cb, f, ctx, 1, 1); | ||
494 | } | ||
495 | |||
496 | static int foreach_edge(game_state *state, space_cb cb, unsigned int f, | ||
497 | void *ctx) | ||
498 | { | ||
499 | int ret1, ret2; | ||
500 | |||
501 | ret1 = foreach_sub(state, cb, f, ctx, 0, 1); | ||
502 | ret2 = foreach_sub(state, cb, f, ctx, 1, 0); | ||
503 | |||
504 | if (ret1 == -1 || ret2 == -1) return -1; | ||
505 | return (ret1 || ret2) ? 1 : 0; | ||
506 | } | ||
507 | |||
508 | #if 0 | ||
509 | static int foreach_vertex(game_state *state, space_cb cb, unsigned int f, | ||
510 | void *ctx) | ||
511 | { | ||
512 | return foreach_sub(state, cb, f, ctx, 0, 0); | ||
513 | } | ||
514 | #endif | ||
515 | |||
516 | #if 0 | ||
517 | static int is_same_assoc(game_state *state, | ||
518 | int x1, int y1, int x2, int y2) | ||
519 | { | ||
520 | space *s1, *s2; | ||
521 | |||
522 | if (!INGRID(state, x1, y1) || !INGRID(state, x2, y2)) | ||
523 | return 0; | ||
524 | |||
525 | s1 = &SPACE(state, x1, y1); | ||
526 | s2 = &SPACE(state, x2, y2); | ||
527 | assert(s1->type == s_tile && s2->type == s_tile); | ||
528 | if ((s1->flags & F_TILE_ASSOC) && (s2->flags & F_TILE_ASSOC) && | ||
529 | s1->dotx == s2->dotx && s1->doty == s2->doty) | ||
530 | return 1; | ||
531 | return 0; /* 0 if not same or not both associated. */ | ||
532 | } | ||
533 | #endif | ||
534 | |||
535 | #if 0 | ||
536 | static int edges_into_vertex(game_state *state, | ||
537 | int x, int y) | ||
538 | { | ||
539 | int dx, dy, nx, ny, count = 0; | ||
540 | |||
541 | assert(SPACE(state, x, y).type == s_vertex); | ||
542 | for (dx = -1; dx <= 1; dx++) { | ||
543 | for (dy = -1; dy <= 1; dy++) { | ||
544 | if (dx != 0 && dy != 0) continue; | ||
545 | if (dx == 0 && dy == 0) continue; | ||
546 | |||
547 | nx = x+dx; ny = y+dy; | ||
548 | if (!INGRID(state, nx, ny)) continue; | ||
549 | assert(SPACE(state, nx, ny).type == s_edge); | ||
550 | if (SPACE(state, nx, ny).flags & F_EDGE_SET) | ||
551 | count++; | ||
552 | } | ||
553 | } | ||
554 | return count; | ||
555 | } | ||
556 | #endif | ||
557 | |||
558 | static space *space_opposite_dot(const game_state *state, const space *sp, | ||
559 | const space *dot) | ||
560 | { | ||
561 | int dx, dy, tx, ty; | ||
562 | space *sp2; | ||
563 | |||
564 | dx = sp->x - dot->x; | ||
565 | dy = sp->y - dot->y; | ||
566 | tx = dot->x - dx; | ||
567 | ty = dot->y - dy; | ||
568 | if (!INGRID(state, tx, ty)) return NULL; | ||
569 | |||
570 | sp2 = &SPACE(state, tx, ty); | ||
571 | assert(sp2->type == sp->type); | ||
572 | return sp2; | ||
573 | } | ||
574 | |||
575 | static space *tile_opposite(const game_state *state, const space *sp) | ||
576 | { | ||
577 | space *dot; | ||
578 | |||
579 | assert(sp->flags & F_TILE_ASSOC); | ||
580 | dot = &SPACE(state, sp->dotx, sp->doty); | ||
581 | return space_opposite_dot(state, sp, dot); | ||
582 | } | ||
583 | |||
584 | static int dotfortile(game_state *state, space *tile, space *dot) | ||
585 | { | ||
586 | space *tile_opp = space_opposite_dot(state, tile, dot); | ||
587 | |||
588 | if (!tile_opp) return 0; /* opposite would be off grid */ | ||
589 | if (tile_opp->flags & F_TILE_ASSOC && | ||
590 | (tile_opp->dotx != dot->x || tile_opp->doty != dot->y)) | ||
591 | return 0; /* opposite already associated with diff. dot */ | ||
592 | return 1; | ||
593 | } | ||
594 | |||
595 | static void adjacencies(game_state *state, space *sp, space **a1s, space **a2s) | ||
596 | { | ||
597 | int dxs[4] = {-1, 1, 0, 0}, dys[4] = {0, 0, -1, 1}; | ||
598 | int n, x, y; | ||
599 | |||
600 | /* this function needs optimising. */ | ||
601 | |||
602 | for (n = 0; n < 4; n++) { | ||
603 | x = sp->x+dxs[n]; | ||
604 | y = sp->y+dys[n]; | ||
605 | |||
606 | if (INGRID(state, x, y)) { | ||
607 | a1s[n] = &SPACE(state, x, y); | ||
608 | |||
609 | x += dxs[n]; y += dys[n]; | ||
610 | |||
611 | if (INGRID(state, x, y)) | ||
612 | a2s[n] = &SPACE(state, x, y); | ||
613 | else | ||
614 | a2s[n] = NULL; | ||
615 | } else { | ||
616 | a1s[n] = a2s[n] = NULL; | ||
617 | } | ||
618 | } | ||
619 | } | ||
620 | |||
621 | static int outline_tile_fordot(game_state *state, space *tile, int mark) | ||
622 | { | ||
623 | space *tadj[4], *eadj[4]; | ||
624 | int i, didsth = 0, edge, same; | ||
625 | |||
626 | assert(tile->type == s_tile); | ||
627 | adjacencies(state, tile, eadj, tadj); | ||
628 | for (i = 0; i < 4; i++) { | ||
629 | if (!eadj[i]) continue; | ||
630 | |||
631 | edge = (eadj[i]->flags & F_EDGE_SET) ? 1 : 0; | ||
632 | if (tadj[i]) { | ||
633 | if (!(tile->flags & F_TILE_ASSOC)) | ||
634 | same = (tadj[i]->flags & F_TILE_ASSOC) ? 0 : 1; | ||
635 | else | ||
636 | same = ((tadj[i]->flags & F_TILE_ASSOC) && | ||
637 | tile->dotx == tadj[i]->dotx && | ||
638 | tile->doty == tadj[i]->doty) ? 1 : 0; | ||
639 | } else | ||
640 | same = 0; | ||
641 | |||
642 | if (!edge && !same) { | ||
643 | if (mark) eadj[i]->flags |= F_EDGE_SET; | ||
644 | didsth = 1; | ||
645 | } else if (edge && same) { | ||
646 | if (mark) eadj[i]->flags &= ~F_EDGE_SET; | ||
647 | didsth = 1; | ||
648 | } | ||
649 | } | ||
650 | return didsth; | ||
651 | } | ||
652 | |||
653 | static void tiles_from_edge(game_state *state, space *sp, space **ts) | ||
654 | { | ||
655 | int xs[2], ys[2]; | ||
656 | |||
657 | if (IS_VERTICAL_EDGE(sp->x)) { | ||
658 | xs[0] = sp->x-1; ys[0] = sp->y; | ||
659 | xs[1] = sp->x+1; ys[1] = sp->y; | ||
660 | } else { | ||
661 | xs[0] = sp->x; ys[0] = sp->y-1; | ||
662 | xs[1] = sp->x; ys[1] = sp->y+1; | ||
663 | } | ||
664 | ts[0] = INGRID(state, xs[0], ys[0]) ? &SPACE(state, xs[0], ys[0]) : NULL; | ||
665 | ts[1] = INGRID(state, xs[1], ys[1]) ? &SPACE(state, xs[1], ys[1]) : NULL; | ||
666 | } | ||
667 | |||
668 | /* Returns a move string for use by 'solve', including the initial | ||
669 | * 'S' if issolve is true. */ | ||
670 | static char *diff_game(const game_state *src, const game_state *dest, | ||
671 | int issolve) | ||
672 | { | ||
673 | int movelen = 0, movesize = 256, x, y, len; | ||
674 | char *move = snewn(movesize, char), buf[80], *sep = ""; | ||
675 | char achar = issolve ? 'a' : 'A'; | ||
676 | space *sps, *spd; | ||
677 | |||
678 | assert(src->sx == dest->sx && src->sy == dest->sy); | ||
679 | |||
680 | if (issolve) { | ||
681 | move[movelen++] = 'S'; | ||
682 | sep = ";"; | ||
683 | } | ||
684 | move[movelen] = '\0'; | ||
685 | for (x = 0; x < src->sx; x++) { | ||
686 | for (y = 0; y < src->sy; y++) { | ||
687 | sps = &SPACE(src, x, y); | ||
688 | spd = &SPACE(dest, x, y); | ||
689 | |||
690 | assert(sps->type == spd->type); | ||
691 | |||
692 | len = 0; | ||
693 | if (sps->type == s_tile) { | ||
694 | if ((sps->flags & F_TILE_ASSOC) && | ||
695 | (spd->flags & F_TILE_ASSOC)) { | ||
696 | if (sps->dotx != spd->dotx || | ||
697 | sps->doty != spd->doty) | ||
698 | /* Both associated; change association, if different */ | ||
699 | len = sprintf(buf, "%s%c%d,%d,%d,%d", sep, | ||
700 | (int)achar, x, y, spd->dotx, spd->doty); | ||
701 | } else if (sps->flags & F_TILE_ASSOC) | ||
702 | /* Only src associated; remove. */ | ||
703 | len = sprintf(buf, "%sU%d,%d", sep, x, y); | ||
704 | else if (spd->flags & F_TILE_ASSOC) | ||
705 | /* Only dest associated; add. */ | ||
706 | len = sprintf(buf, "%s%c%d,%d,%d,%d", sep, | ||
707 | (int)achar, x, y, spd->dotx, spd->doty); | ||
708 | } else if (sps->type == s_edge) { | ||
709 | if ((sps->flags & F_EDGE_SET) != (spd->flags & F_EDGE_SET)) | ||
710 | /* edge flags are different; flip them. */ | ||
711 | len = sprintf(buf, "%sE%d,%d", sep, x, y); | ||
712 | } | ||
713 | if (len) { | ||
714 | if (movelen + len >= movesize) { | ||
715 | movesize = movelen + len + 256; | ||
716 | move = sresize(move, movesize, char); | ||
717 | } | ||
718 | strcpy(move + movelen, buf); | ||
719 | movelen += len; | ||
720 | sep = ";"; | ||
721 | } | ||
722 | } | ||
723 | } | ||
724 | debug(("diff_game src then dest:\n")); | ||
725 | dbg_state(src); | ||
726 | dbg_state(dest); | ||
727 | debug(("diff string %s\n", move)); | ||
728 | return move; | ||
729 | } | ||
730 | |||
731 | /* Returns 1 if a dot here would not be too close to any other dots | ||
732 | * (and would avoid other game furniture). */ | ||
733 | static int dot_is_possible(game_state *state, space *sp, int allow_assoc) | ||
734 | { | ||
735 | int bx = 0, by = 0, dx, dy; | ||
736 | space *adj; | ||
737 | #ifdef STANDALONE_PICTURE_GENERATOR | ||
738 | int col = -1; | ||
739 | #endif | ||
740 | |||
741 | switch (sp->type) { | ||
742 | case s_tile: | ||
743 | bx = by = 1; break; | ||
744 | case s_edge: | ||
745 | if (IS_VERTICAL_EDGE(sp->x)) { | ||
746 | bx = 2; by = 1; | ||
747 | } else { | ||
748 | bx = 1; by = 2; | ||
749 | } | ||
750 | break; | ||
751 | case s_vertex: | ||
752 | bx = by = 2; break; | ||
753 | } | ||
754 | |||
755 | for (dx = -bx; dx <= bx; dx++) { | ||
756 | for (dy = -by; dy <= by; dy++) { | ||
757 | if (!INGRID(state, sp->x+dx, sp->y+dy)) continue; | ||
758 | |||
759 | adj = &SPACE(state, sp->x+dx, sp->y+dy); | ||
760 | |||
761 | #ifdef STANDALONE_PICTURE_GENERATOR | ||
762 | /* | ||
763 | * Check that all the squares we're looking at have the | ||
764 | * same colour. | ||
765 | */ | ||
766 | if (picture) { | ||
767 | if (adj->type == s_tile) { | ||
768 | int c = picture[(adj->y / 2) * state->w + (adj->x / 2)]; | ||
769 | if (col < 0) | ||
770 | col = c; | ||
771 | if (c != col) | ||
772 | return 0; /* colour mismatch */ | ||
773 | } | ||
774 | } | ||
775 | #endif | ||
776 | |||
777 | if (!allow_assoc && (adj->flags & F_TILE_ASSOC)) | ||
778 | return 0; | ||
779 | |||
780 | if (dx != 0 || dy != 0) { | ||
781 | /* Other than our own square, no dots nearby. */ | ||
782 | if (adj->flags & (F_DOT)) | ||
783 | return 0; | ||
784 | } | ||
785 | |||
786 | /* We don't want edges within our rectangle | ||
787 | * (but don't care about edges on the edge) */ | ||
788 | if (abs(dx) < bx && abs(dy) < by && | ||
789 | adj->flags & F_EDGE_SET) | ||
790 | return 0; | ||
791 | } | ||
792 | } | ||
793 | return 1; | ||
794 | } | ||
795 | |||
796 | /* ---------------------------------------------------------- | ||
797 | * Game generation, structure creation, and descriptions. | ||
798 | */ | ||
799 | |||
800 | static game_state *blank_game(int w, int h) | ||
801 | { | ||
802 | game_state *state = snew(game_state); | ||
803 | int x, y; | ||
804 | |||
805 | state->w = w; | ||
806 | state->h = h; | ||
807 | |||
808 | state->sx = (w*2)+1; | ||
809 | state->sy = (h*2)+1; | ||
810 | state->grid = snewn(state->sx * state->sy, space); | ||
811 | state->completed = state->used_solve = 0; | ||
812 | |||
813 | for (x = 0; x < state->sx; x++) { | ||
814 | for (y = 0; y < state->sy; y++) { | ||
815 | space *sp = &SPACE(state, x, y); | ||
816 | memset(sp, 0, sizeof(space)); | ||
817 | sp->x = x; | ||
818 | sp->y = y; | ||
819 | if ((x % 2) == 0 && (y % 2) == 0) | ||
820 | sp->type = s_vertex; | ||
821 | else if ((x % 2) == 0 || (y % 2) == 0) { | ||
822 | sp->type = s_edge; | ||
823 | if (x == 0 || y == 0 || x == state->sx-1 || y == state->sy-1) | ||
824 | sp->flags |= F_EDGE_SET; | ||
825 | } else | ||
826 | sp->type = s_tile; | ||
827 | } | ||
828 | } | ||
829 | |||
830 | state->ndots = 0; | ||
831 | state->dots = NULL; | ||
832 | |||
833 | state->me = NULL; /* filled in by new_game. */ | ||
834 | state->cdiff = -1; | ||
835 | |||
836 | return state; | ||
837 | } | ||
838 | |||
839 | static void game_update_dots(game_state *state) | ||
840 | { | ||
841 | int i, n, sz = state->sx * state->sy; | ||
842 | |||
843 | if (state->dots) sfree(state->dots); | ||
844 | state->ndots = 0; | ||
845 | |||
846 | for (i = 0; i < sz; i++) { | ||
847 | if (state->grid[i].flags & F_DOT) state->ndots++; | ||
848 | } | ||
849 | state->dots = snewn(state->ndots, space *); | ||
850 | n = 0; | ||
851 | for (i = 0; i < sz; i++) { | ||
852 | if (state->grid[i].flags & F_DOT) | ||
853 | state->dots[n++] = &state->grid[i]; | ||
854 | } | ||
855 | } | ||
856 | |||
857 | static void clear_game(game_state *state, int cleardots) | ||
858 | { | ||
859 | int x, y; | ||
860 | |||
861 | /* don't erase edge flags around outline! */ | ||
862 | for (x = 1; x < state->sx-1; x++) { | ||
863 | for (y = 1; y < state->sy-1; y++) { | ||
864 | if (cleardots) | ||
865 | SPACE(state, x, y).flags = 0; | ||
866 | else | ||
867 | SPACE(state, x, y).flags &= (F_DOT|F_DOT_BLACK); | ||
868 | } | ||
869 | } | ||
870 | if (cleardots) game_update_dots(state); | ||
871 | } | ||
872 | |||
873 | static game_state *dup_game(const game_state *state) | ||
874 | { | ||
875 | game_state *ret = blank_game(state->w, state->h); | ||
876 | |||
877 | ret->completed = state->completed; | ||
878 | ret->used_solve = state->used_solve; | ||
879 | |||
880 | memcpy(ret->grid, state->grid, | ||
881 | ret->sx*ret->sy*sizeof(space)); | ||
882 | |||
883 | game_update_dots(ret); | ||
884 | |||
885 | ret->me = state->me; | ||
886 | ret->cdiff = state->cdiff; | ||
887 | |||
888 | return ret; | ||
889 | } | ||
890 | |||
891 | static void free_game(game_state *state) | ||
892 | { | ||
893 | if (state->dots) sfree(state->dots); | ||
894 | sfree(state->grid); | ||
895 | sfree(state); | ||
896 | } | ||
897 | |||
898 | /* Game description is a sequence of letters representing the number | ||
899 | * of spaces (a = 0, y = 24) before the next dot; a-y for a white dot, | ||
900 | * and A-Y for a black dot. 'z' is 25 spaces (and no dot). | ||
901 | * | ||
902 | * I know it's a bitch to generate by hand, so we provide | ||
903 | * an edit mode. | ||
904 | */ | ||
905 | |||
906 | static char *encode_game(game_state *state) | ||
907 | { | ||
908 | char *desc, *p; | ||
909 | int run, x, y, area; | ||
910 | unsigned int f; | ||
911 | |||
912 | area = (state->sx-2) * (state->sy-2); | ||
913 | |||
914 | desc = snewn(area, char); | ||
915 | p = desc; | ||
916 | run = 0; | ||
917 | for (y = 1; y < state->sy-1; y++) { | ||
918 | for (x = 1; x < state->sx-1; x++) { | ||
919 | f = SPACE(state, x, y).flags; | ||
920 | |||
921 | /* a/A is 0 spaces between, b/B is 1 space, ... | ||
922 | * y/Y is 24 spaces, za/zA is 25 spaces, ... | ||
923 | * It's easier to count from 0 because we then | ||
924 | * don't have to special-case the top left-hand corner | ||
925 | * (which could be a dot with 0 spaces before it). */ | ||
926 | if (!(f & F_DOT)) | ||
927 | run++; | ||
928 | else { | ||
929 | while (run > 24) { | ||
930 | *p++ = 'z'; | ||
931 | run -= 25; | ||
932 | } | ||
933 | *p++ = ((f & F_DOT_BLACK) ? 'A' : 'a') + run; | ||
934 | run = 0; | ||
935 | } | ||
936 | } | ||
937 | } | ||
938 | assert(p - desc < area); | ||
939 | *p++ = '\0'; | ||
940 | desc = sresize(desc, p - desc, char); | ||
941 | |||
942 | return desc; | ||
943 | } | ||
944 | |||
945 | struct movedot { | ||
946 | int op; | ||
947 | space *olddot, *newdot; | ||
948 | }; | ||
949 | |||
950 | enum { MD_CHECK, MD_MOVE }; | ||
951 | |||
952 | static int movedot_cb(game_state *state, space *tile, void *vctx) | ||
953 | { | ||
954 | struct movedot *md = (struct movedot *)vctx; | ||
955 | space *newopp = NULL; | ||
956 | |||
957 | assert(tile->type == s_tile); | ||
958 | assert(md->olddot && md->newdot); | ||
959 | |||
960 | if (!(tile->flags & F_TILE_ASSOC)) return 0; | ||
961 | if (tile->dotx != md->olddot->x || tile->doty != md->olddot->y) | ||
962 | return 0; | ||
963 | |||
964 | newopp = space_opposite_dot(state, tile, md->newdot); | ||
965 | |||
966 | switch (md->op) { | ||
967 | case MD_CHECK: | ||
968 | /* If the tile is associated with the old dot, check its | ||
969 | * opposite wrt the _new_ dot is empty or same assoc. */ | ||
970 | if (!newopp) return -1; /* no new opposite */ | ||
971 | if (newopp->flags & F_TILE_ASSOC) { | ||
972 | if (newopp->dotx != md->olddot->x || | ||
973 | newopp->doty != md->olddot->y) | ||
974 | return -1; /* associated, but wrong dot. */ | ||
975 | } | ||
976 | #ifdef STANDALONE_PICTURE_GENERATOR | ||
977 | if (picture) { | ||
978 | /* | ||
979 | * Reject if either tile and the dot don't match in colour. | ||
980 | */ | ||
981 | if (!(picture[(tile->y/2) * state->w + (tile->x/2)]) ^ | ||
982 | !(md->newdot->flags & F_DOT_BLACK)) | ||
983 | return -1; | ||
984 | if (!(picture[(newopp->y/2) * state->w + (newopp->x/2)]) ^ | ||
985 | !(md->newdot->flags & F_DOT_BLACK)) | ||
986 | return -1; | ||
987 | } | ||
988 | #endif | ||
989 | break; | ||
990 | |||
991 | case MD_MOVE: | ||
992 | /* Move dot associations: anything that was associated | ||
993 | * with the old dot, and its opposite wrt the new dot, | ||
994 | * become associated with the new dot. */ | ||
995 | assert(newopp); | ||
996 | debug(("Associating %d,%d and %d,%d with new dot %d,%d.\n", | ||
997 | tile->x, tile->y, newopp->x, newopp->y, | ||
998 | md->newdot->x, md->newdot->y)); | ||
999 | add_assoc(state, tile, md->newdot); | ||
1000 | add_assoc(state, newopp, md->newdot); | ||
1001 | return 1; /* we did something! */ | ||
1002 | } | ||
1003 | return 0; | ||
1004 | } | ||
1005 | |||
1006 | /* For the given dot, first see if we could expand it into all the given | ||
1007 | * extra spaces (by checking for empty spaces on the far side), and then | ||
1008 | * see if we can move the dot to shift the CoG to include the new spaces. | ||
1009 | */ | ||
1010 | static int dot_expand_or_move(game_state *state, space *dot, | ||
1011 | space **toadd, int nadd) | ||
1012 | { | ||
1013 | space *tileopp; | ||
1014 | int i, ret, nnew, cx, cy; | ||
1015 | struct movedot md; | ||
1016 | |||
1017 | debug(("dot_expand_or_move: %d tiles for dot %d,%d\n", | ||
1018 | nadd, dot->x, dot->y)); | ||
1019 | for (i = 0; i < nadd; i++) | ||
1020 | debug(("dot_expand_or_move: dot %d,%d\n", | ||
1021 | toadd[i]->x, toadd[i]->y)); | ||
1022 | assert(dot->flags & F_DOT); | ||
1023 | |||
1024 | #ifdef STANDALONE_PICTURE_GENERATOR | ||
1025 | if (picture) { | ||
1026 | /* | ||
1027 | * Reject the expansion totally if any of the new tiles are | ||
1028 | * the wrong colour. | ||
1029 | */ | ||
1030 | for (i = 0; i < nadd; i++) { | ||
1031 | if (!(picture[(toadd[i]->y/2) * state->w + (toadd[i]->x/2)]) ^ | ||
1032 | !(dot->flags & F_DOT_BLACK)) | ||
1033 | return 0; | ||
1034 | } | ||
1035 | } | ||
1036 | #endif | ||
1037 | |||
1038 | /* First off, could we just expand the current dot's tile to cover | ||
1039 | * the space(s) passed in and their opposites? */ | ||
1040 | for (i = 0; i < nadd; i++) { | ||
1041 | tileopp = space_opposite_dot(state, toadd[i], dot); | ||
1042 | if (!tileopp) goto noexpand; | ||
1043 | if (tileopp->flags & F_TILE_ASSOC) goto noexpand; | ||
1044 | #ifdef STANDALONE_PICTURE_GENERATOR | ||
1045 | if (picture) { | ||
1046 | /* | ||
1047 | * The opposite tiles have to be the right colour as well. | ||
1048 | */ | ||
1049 | if (!(picture[(tileopp->y/2) * state->w + (tileopp->x/2)]) ^ | ||
1050 | !(dot->flags & F_DOT_BLACK)) | ||
1051 | goto noexpand; | ||
1052 | } | ||
1053 | #endif | ||
1054 | } | ||
1055 | /* OK, all spaces have valid empty opposites: associate spaces and | ||
1056 | * opposites with our dot. */ | ||
1057 | for (i = 0; i < nadd; i++) { | ||
1058 | tileopp = space_opposite_dot(state, toadd[i], dot); | ||
1059 | add_assoc(state, toadd[i], dot); | ||
1060 | add_assoc(state, tileopp, dot); | ||
1061 | debug(("Added associations %d,%d and %d,%d --> %d,%d\n", | ||
1062 | toadd[i]->x, toadd[i]->y, | ||
1063 | tileopp->x, tileopp->y, | ||
1064 | dot->x, dot->y)); | ||
1065 | dbg_state(state); | ||
1066 | } | ||
1067 | return 1; | ||
1068 | |||
1069 | noexpand: | ||
1070 | /* Otherwise, try to move dot so as to encompass given spaces: */ | ||
1071 | /* first, calculate the 'centre of gravity' of the new dot. */ | ||
1072 | nnew = dot->nassoc + nadd; /* number of tiles assoc. with new dot. */ | ||
1073 | cx = dot->x * dot->nassoc; | ||
1074 | cy = dot->y * dot->nassoc; | ||
1075 | for (i = 0; i < nadd; i++) { | ||
1076 | cx += toadd[i]->x; | ||
1077 | cy += toadd[i]->y; | ||
1078 | } | ||
1079 | /* If the CoG isn't a whole number, it's not possible. */ | ||
1080 | if ((cx % nnew) != 0 || (cy % nnew) != 0) { | ||
1081 | debug(("Unable to move dot %d,%d, CoG not whole number.\n", | ||
1082 | dot->x, dot->y)); | ||
1083 | return 0; | ||
1084 | } | ||
1085 | cx /= nnew; cy /= nnew; | ||
1086 | |||
1087 | /* Check whether all spaces in the old tile would have a good | ||
1088 | * opposite wrt the new dot. */ | ||
1089 | md.olddot = dot; | ||
1090 | md.newdot = &SPACE(state, cx, cy); | ||
1091 | md.op = MD_CHECK; | ||
1092 | ret = foreach_tile(state, movedot_cb, IMPOSSIBLE_QUITS, &md); | ||
1093 | if (ret == -1) { | ||
1094 | debug(("Unable to move dot %d,%d, new dot not symmetrical.\n", | ||
1095 | dot->x, dot->y)); | ||
1096 | return 0; | ||
1097 | } | ||
1098 | /* Also check whether all spaces we're adding would have a good | ||
1099 | * opposite wrt the new dot. */ | ||
1100 | for (i = 0; i < nadd; i++) { | ||
1101 | tileopp = space_opposite_dot(state, toadd[i], md.newdot); | ||
1102 | if (tileopp && (tileopp->flags & F_TILE_ASSOC) && | ||
1103 | (tileopp->dotx != dot->x || tileopp->doty != dot->y)) { | ||
1104 | tileopp = NULL; | ||
1105 | } | ||
1106 | if (!tileopp) { | ||
1107 | debug(("Unable to move dot %d,%d, new dot not symmetrical.\n", | ||
1108 | dot->x, dot->y)); | ||
1109 | return 0; | ||
1110 | } | ||
1111 | #ifdef STANDALONE_PICTURE_GENERATOR | ||
1112 | if (picture) { | ||
1113 | if (!(picture[(tileopp->y/2) * state->w + (tileopp->x/2)]) ^ | ||
1114 | !(dot->flags & F_DOT_BLACK)) | ||
1115 | return 0; | ||
1116 | } | ||
1117 | #endif | ||
1118 | } | ||
1119 | |||
1120 | /* If we've got here, we're ok. First, associate all of 'toadd' | ||
1121 | * with the _old_ dot (so they'll get fixed up, with their opposites, | ||
1122 | * in the next step). */ | ||
1123 | for (i = 0; i < nadd; i++) { | ||
1124 | debug(("Associating to-add %d,%d with old dot %d,%d.\n", | ||
1125 | toadd[i]->x, toadd[i]->y, dot->x, dot->y)); | ||
1126 | add_assoc(state, toadd[i], dot); | ||
1127 | } | ||
1128 | |||
1129 | /* Finally, move the dot and fix up all the old associations. */ | ||
1130 | debug(("Moving dot at %d,%d to %d,%d\n", | ||
1131 | dot->x, dot->y, md.newdot->x, md.newdot->y)); | ||
1132 | { | ||
1133 | #ifdef STANDALONE_PICTURE_GENERATOR | ||
1134 | int f = dot->flags & F_DOT_BLACK; | ||
1135 | #endif | ||
1136 | remove_dot(dot); | ||
1137 | add_dot(md.newdot); | ||
1138 | #ifdef STANDALONE_PICTURE_GENERATOR | ||
1139 | md.newdot->flags |= f; | ||
1140 | #endif | ||
1141 | } | ||
1142 | |||
1143 | md.op = MD_MOVE; | ||
1144 | ret = foreach_tile(state, movedot_cb, 0, &md); | ||
1145 | assert(ret == 1); | ||
1146 | dbg_state(state); | ||
1147 | |||
1148 | return 1; | ||
1149 | } | ||
1150 | |||
1151 | /* Hard-code to a max. of 2x2 squares, for speed (less malloc) */ | ||
1152 | #define MAX_TOADD 4 | ||
1153 | #define MAX_OUTSIDE 8 | ||
1154 | |||
1155 | #define MAX_TILE_PERC 20 | ||
1156 | |||
1157 | static int generate_try_block(game_state *state, random_state *rs, | ||
1158 | int x1, int y1, int x2, int y2) | ||
1159 | { | ||
1160 | int x, y, nadd = 0, nout = 0, i, maxsz; | ||
1161 | space *sp, *toadd[MAX_TOADD], *outside[MAX_OUTSIDE], *dot; | ||
1162 | |||
1163 | if (!INGRID(state, x1, y1) || !INGRID(state, x2, y2)) return 0; | ||
1164 | |||
1165 | /* We limit the maximum size of tiles to be ~2*sqrt(area); so, | ||
1166 | * a 5x5 grid shouldn't have anything >10 tiles, a 20x20 grid | ||
1167 | * nothing >40 tiles. */ | ||
1168 | maxsz = (int)sqrt((double)(state->w * state->h)) * 2; | ||
1169 | debug(("generate_try_block, maxsz %d\n", maxsz)); | ||
1170 | |||
1171 | /* Make a static list of the spaces; if any space is already | ||
1172 | * associated then quit immediately. */ | ||
1173 | for (x = x1; x <= x2; x += 2) { | ||
1174 | for (y = y1; y <= y2; y += 2) { | ||
1175 | assert(nadd < MAX_TOADD); | ||
1176 | sp = &SPACE(state, x, y); | ||
1177 | assert(sp->type == s_tile); | ||
1178 | if (sp->flags & F_TILE_ASSOC) return 0; | ||
1179 | toadd[nadd++] = sp; | ||
1180 | } | ||
1181 | } | ||
1182 | |||
1183 | /* Make a list of the spaces outside of our block, and shuffle it. */ | ||
1184 | #define OUTSIDE(x, y) do { \ | ||
1185 | if (INGRID(state, (x), (y))) { \ | ||
1186 | assert(nout < MAX_OUTSIDE); \ | ||
1187 | outside[nout++] = &SPACE(state, (x), (y)); \ | ||
1188 | } \ | ||
1189 | } while(0) | ||
1190 | for (x = x1; x <= x2; x += 2) { | ||
1191 | OUTSIDE(x, y1-2); | ||
1192 | OUTSIDE(x, y2+2); | ||
1193 | } | ||
1194 | for (y = y1; y <= y2; y += 2) { | ||
1195 | OUTSIDE(x1-2, y); | ||
1196 | OUTSIDE(x2+2, y); | ||
1197 | } | ||
1198 | shuffle(outside, nout, sizeof(space *), rs); | ||
1199 | |||
1200 | for (i = 0; i < nout; i++) { | ||
1201 | if (!(outside[i]->flags & F_TILE_ASSOC)) continue; | ||
1202 | dot = &SPACE(state, outside[i]->dotx, outside[i]->doty); | ||
1203 | if (dot->nassoc >= maxsz) { | ||
1204 | debug(("Not adding to dot %d,%d, large enough (%d) already.\n", | ||
1205 | dot->x, dot->y, dot->nassoc)); | ||
1206 | continue; | ||
1207 | } | ||
1208 | if (dot_expand_or_move(state, dot, toadd, nadd)) return 1; | ||
1209 | } | ||
1210 | return 0; | ||
1211 | } | ||
1212 | |||
1213 | #ifdef STANDALONE_SOLVER | ||
1214 | int maxtries; | ||
1215 | #define MAXTRIES maxtries | ||
1216 | #else | ||
1217 | #define MAXTRIES 50 | ||
1218 | #endif | ||
1219 | |||
1220 | #define GP_DOTS 1 | ||
1221 | |||
1222 | static void generate_pass(game_state *state, random_state *rs, int *scratch, | ||
1223 | int perc, unsigned int flags) | ||
1224 | { | ||
1225 | int sz = state->sx*state->sy, nspc, i, ret; | ||
1226 | |||
1227 | shuffle(scratch, sz, sizeof(int), rs); | ||
1228 | |||
1229 | /* This bug took me a, er, little while to track down. On PalmOS, | ||
1230 | * which has 16-bit signed ints, puzzles over about 9x9 started | ||
1231 | * failing to generate because the nspc calculation would start | ||
1232 | * to overflow, causing the dots not to be filled in properly. */ | ||
1233 | nspc = (int)(((long)perc * (long)sz) / 100L); | ||
1234 | debug(("generate_pass: %d%% (%d of %dx%d) squares, flags 0x%x\n", | ||
1235 | perc, nspc, state->sx, state->sy, flags)); | ||
1236 | |||
1237 | for (i = 0; i < nspc; i++) { | ||
1238 | space *sp = &state->grid[scratch[i]]; | ||
1239 | int x1 = sp->x, y1 = sp->y, x2 = sp->x, y2 = sp->y; | ||
1240 | |||
1241 | if (sp->type == s_edge) { | ||
1242 | if (IS_VERTICAL_EDGE(sp->x)) { | ||
1243 | x1--; x2++; | ||
1244 | } else { | ||
1245 | y1--; y2++; | ||
1246 | } | ||
1247 | } | ||
1248 | if (sp->type != s_vertex) { | ||
1249 | /* heuristic; expanding from vertices tends to generate lots of | ||
1250 | * too-big regions of tiles. */ | ||
1251 | if (generate_try_block(state, rs, x1, y1, x2, y2)) | ||
1252 | continue; /* we expanded successfully. */ | ||
1253 | } | ||
1254 | |||
1255 | if (!(flags & GP_DOTS)) continue; | ||
1256 | |||
1257 | if ((sp->type == s_edge) && (i % 2)) { | ||
1258 | debug(("Omitting edge %d,%d as half-of.\n", sp->x, sp->y)); | ||
1259 | continue; | ||
1260 | } | ||
1261 | |||
1262 | /* If we've got here we might want to put a dot down. Check | ||
1263 | * if we can, and add one if so. */ | ||
1264 | if (dot_is_possible(state, sp, 0)) { | ||
1265 | add_dot(sp); | ||
1266 | #ifdef STANDALONE_PICTURE_GENERATOR | ||
1267 | if (picture) { | ||
1268 | if (picture[(sp->y/2) * state->w + (sp->x/2)]) | ||
1269 | sp->flags |= F_DOT_BLACK; | ||
1270 | } | ||
1271 | #endif | ||
1272 | ret = solver_obvious_dot(state, sp); | ||
1273 | assert(ret != -1); | ||
1274 | debug(("Added dot (and obvious associations) at %d,%d\n", | ||
1275 | sp->x, sp->y)); | ||
1276 | dbg_state(state); | ||
1277 | } | ||
1278 | } | ||
1279 | dbg_state(state); | ||
1280 | } | ||
1281 | |||
1282 | static char *new_game_desc(const game_params *params, random_state *rs, | ||
1283 | char **aux, int interactive) | ||
1284 | { | ||
1285 | game_state *state = blank_game(params->w, params->h), *copy; | ||
1286 | char *desc; | ||
1287 | int *scratch, sz = state->sx*state->sy, i; | ||
1288 | int diff, ntries = 0, cc; | ||
1289 | |||
1290 | /* Random list of squares to try and process, one-by-one. */ | ||
1291 | scratch = snewn(sz, int); | ||
1292 | for (i = 0; i < sz; i++) scratch[i] = i; | ||
1293 | |||
1294 | generate: | ||
1295 | clear_game(state, 1); | ||
1296 | ntries++; | ||
1297 | |||
1298 | /* generate_pass(state, rs, scratch, 10, GP_DOTS); */ | ||
1299 | /* generate_pass(state, rs, scratch, 100, 0); */ | ||
1300 | generate_pass(state, rs, scratch, 100, GP_DOTS); | ||
1301 | |||
1302 | game_update_dots(state); | ||
1303 | |||
1304 | if (state->ndots == 1) goto generate; | ||
1305 | |||
1306 | #ifdef DEBUGGING | ||
1307 | { | ||
1308 | char *tmp = encode_game(state); | ||
1309 | debug(("new_game_desc state %dx%d:%s\n", params->w, params->h, tmp)); | ||
1310 | sfree(tmp); | ||
1311 | } | ||
1312 | #endif | ||
1313 | |||
1314 | for (i = 0; i < state->sx*state->sy; i++) | ||
1315 | if (state->grid[i].type == s_tile) | ||
1316 | outline_tile_fordot(state, &state->grid[i], TRUE); | ||
1317 | cc = check_complete(state, NULL, NULL); | ||
1318 | assert(cc); | ||
1319 | |||
1320 | copy = dup_game(state); | ||
1321 | clear_game(copy, 0); | ||
1322 | dbg_state(copy); | ||
1323 | diff = solver_state(copy, params->diff); | ||
1324 | free_game(copy); | ||
1325 | |||
1326 | assert(diff != DIFF_IMPOSSIBLE); | ||
1327 | if (diff != params->diff) { | ||
1328 | /* | ||
1329 | * We'll grudgingly accept a too-easy puzzle, but we must | ||
1330 | * _not_ permit a too-hard one (one which the solver | ||
1331 | * couldn't handle at all). | ||
1332 | */ | ||
1333 | if (diff > params->diff || | ||
1334 | ntries < MAXTRIES) goto generate; | ||
1335 | } | ||
1336 | |||
1337 | #ifdef STANDALONE_PICTURE_GENERATOR | ||
1338 | /* | ||
1339 | * Postprocessing pass to prevent excessive numbers of adjacent | ||
1340 | * singletons. Iterate over all edges in random shuffled order; | ||
1341 | * for each edge that separates two regions, investigate | ||
1342 | * whether removing that edge and merging the regions would | ||
1343 | * still yield a valid and soluble puzzle. (The two regions | ||
1344 | * must also be the same colour, of course.) If so, do it. | ||
1345 | * | ||
1346 | * This postprocessing pass is slow (due to repeated solver | ||
1347 | * invocations), and seems to be unnecessary during normal | ||
1348 | * unconstrained game generation. However, when generating a | ||
1349 | * game under colour constraints, excessive singletons seem to | ||
1350 | * turn up more often, so it's worth doing this. | ||
1351 | */ | ||
1352 | { | ||
1353 | int *posns, nposns; | ||
1354 | int i, j, newdiff; | ||
1355 | game_state *copy2; | ||
1356 | |||
1357 | nposns = params->w * (params->h+1) + params->h * (params->w+1); | ||
1358 | posns = snewn(nposns, int); | ||
1359 | for (i = j = 0; i < state->sx*state->sy; i++) | ||
1360 | if (state->grid[i].type == s_edge) | ||
1361 | posns[j++] = i; | ||
1362 | assert(j == nposns); | ||
1363 | |||
1364 | shuffle(posns, nposns, sizeof(*posns), rs); | ||
1365 | |||
1366 | for (i = 0; i < nposns; i++) { | ||
1367 | int x, y, x0, y0, x1, y1, cx, cy, cn, cx0, cy0, cx1, cy1, tx, ty; | ||
1368 | space *s0, *s1, *ts, *d0, *d1, *dn; | ||
1369 | int ok; | ||
1370 | |||
1371 | /* Coordinates of edge space */ | ||
1372 | x = posns[i] % state->sx; | ||
1373 | y = posns[i] / state->sx; | ||
1374 | |||
1375 | /* Coordinates of square spaces on either side of edge */ | ||
1376 | x0 = ((x+1) & ~1) - 1; /* round down to next odd number */ | ||
1377 | y0 = ((y+1) & ~1) - 1; | ||
1378 | x1 = 2*x-x0; /* and reflect about x to get x1 */ | ||
1379 | y1 = 2*y-y0; | ||
1380 | |||
1381 | if (!INGRID(state, x0, y0) || !INGRID(state, x1, y1)) | ||
1382 | continue; /* outermost edge of grid */ | ||
1383 | s0 = &SPACE(state, x0, y0); | ||
1384 | s1 = &SPACE(state, x1, y1); | ||
1385 | assert(s0->type == s_tile && s1->type == s_tile); | ||
1386 | |||
1387 | if (s0->dotx == s1->dotx && s0->doty == s1->doty) | ||
1388 | continue; /* tiles _already_ owned by same dot */ | ||
1389 | |||
1390 | d0 = &SPACE(state, s0->dotx, s0->doty); | ||
1391 | d1 = &SPACE(state, s1->dotx, s1->doty); | ||
1392 | |||
1393 | if ((d0->flags ^ d1->flags) & F_DOT_BLACK) | ||
1394 | continue; /* different colours: cannot merge */ | ||
1395 | |||
1396 | /* | ||
1397 | * Work out where the centre of gravity of the new | ||
1398 | * region would be. | ||
1399 | */ | ||
1400 | cx = d0->nassoc * d0->x + d1->nassoc * d1->x; | ||
1401 | cy = d0->nassoc * d0->y + d1->nassoc * d1->y; | ||
1402 | cn = d0->nassoc + d1->nassoc; | ||
1403 | if (cx % cn || cy % cn) | ||
1404 | continue; /* CoG not at integer coordinates */ | ||
1405 | cx /= cn; | ||
1406 | cy /= cn; | ||
1407 | assert(INUI(state, cx, cy)); | ||
1408 | |||
1409 | /* | ||
1410 | * Ensure that the CoG would actually be _in_ the new | ||
1411 | * region, by verifying that all its surrounding tiles | ||
1412 | * belong to one or other of our two dots. | ||
1413 | */ | ||
1414 | cx0 = ((cx+1) & ~1) - 1; /* round down to next odd number */ | ||
1415 | cy0 = ((cy+1) & ~1) - 1; | ||
1416 | cx1 = 2*cx-cx0; /* and reflect about cx to get cx1 */ | ||
1417 | cy1 = 2*cy-cy0; | ||
1418 | ok = TRUE; | ||
1419 | for (ty = cy0; ty <= cy1; ty += 2) | ||
1420 | for (tx = cx0; tx <= cx1; tx += 2) { | ||
1421 | ts = &SPACE(state, tx, ty); | ||
1422 | assert(ts->type == s_tile); | ||
1423 | if ((ts->dotx != d0->x || ts->doty != d0->y) && | ||
1424 | (ts->dotx != d1->x || ts->doty != d1->y)) | ||
1425 | ok = FALSE; | ||
1426 | } | ||
1427 | if (!ok) | ||
1428 | continue; | ||
1429 | |||
1430 | /* | ||
1431 | * Verify that for every tile in either source region, | ||
1432 | * that tile's image in the new CoG is also in one of | ||
1433 | * the two source regions. | ||
1434 | */ | ||
1435 | for (ty = 1; ty < state->sy; ty += 2) { | ||
1436 | for (tx = 1; tx < state->sx; tx += 2) { | ||
1437 | int tx1, ty1; | ||
1438 | |||
1439 | ts = &SPACE(state, tx, ty); | ||
1440 | assert(ts->type == s_tile); | ||
1441 | if ((ts->dotx != d0->x || ts->doty != d0->y) && | ||
1442 | (ts->dotx != d1->x || ts->doty != d1->y)) | ||
1443 | continue; /* not part of these tiles anyway */ | ||
1444 | tx1 = 2*cx-tx; | ||
1445 | ty1 = 2*cy-ty; | ||
1446 | if (!INGRID(state, tx1, ty1)) { | ||
1447 | ok = FALSE; | ||
1448 | break; | ||
1449 | } | ||
1450 | ts = &SPACE(state, cx+cx-tx, cy+cy-ty); | ||
1451 | if ((ts->dotx != d0->x || ts->doty != d0->y) && | ||
1452 | (ts->dotx != d1->x || ts->doty != d1->y)) { | ||
1453 | ok = FALSE; | ||
1454 | break; | ||
1455 | } | ||
1456 | } | ||
1457 | if (!ok) | ||
1458 | break; | ||
1459 | } | ||
1460 | if (!ok) | ||
1461 | continue; | ||
1462 | |||
1463 | /* | ||
1464 | * Now we're clear to attempt the merge. We take a copy | ||
1465 | * of the game state first, so we can revert it easily | ||
1466 | * if the resulting puzzle turns out to have become | ||
1467 | * insoluble. | ||
1468 | */ | ||
1469 | copy2 = dup_game(state); | ||
1470 | |||
1471 | remove_dot(d0); | ||
1472 | remove_dot(d1); | ||
1473 | dn = &SPACE(state, cx, cy); | ||
1474 | add_dot(dn); | ||
1475 | dn->flags |= (d0->flags & F_DOT_BLACK); | ||
1476 | for (ty = 1; ty < state->sy; ty += 2) { | ||
1477 | for (tx = 1; tx < state->sx; tx += 2) { | ||
1478 | ts = &SPACE(state, tx, ty); | ||
1479 | assert(ts->type == s_tile); | ||
1480 | if ((ts->dotx != d0->x || ts->doty != d0->y) && | ||
1481 | (ts->dotx != d1->x || ts->doty != d1->y)) | ||
1482 | continue; /* not part of these tiles anyway */ | ||
1483 | add_assoc(state, ts, dn); | ||
1484 | } | ||
1485 | } | ||
1486 | |||
1487 | copy = dup_game(state); | ||
1488 | clear_game(copy, 0); | ||
1489 | dbg_state(copy); | ||
1490 | newdiff = solver_state(copy, params->diff); | ||
1491 | free_game(copy); | ||
1492 | if (diff == newdiff) { | ||
1493 | /* Still just as soluble. Let the merge stand. */ | ||
1494 | free_game(copy2); | ||
1495 | } else { | ||
1496 | /* Became insoluble. Revert. */ | ||
1497 | free_game(state); | ||
1498 | state = copy2; | ||
1499 | } | ||
1500 | } | ||
1501 | sfree(posns); | ||
1502 | } | ||
1503 | #endif | ||
1504 | |||
1505 | desc = encode_game(state); | ||
1506 | #ifndef STANDALONE_SOLVER | ||
1507 | debug(("new_game_desc generated: \n")); | ||
1508 | dbg_state(state); | ||
1509 | #endif | ||
1510 | |||
1511 | free_game(state); | ||
1512 | sfree(scratch); | ||
1513 | |||
1514 | return desc; | ||
1515 | } | ||
1516 | |||
1517 | static int dots_too_close(game_state *state) | ||
1518 | { | ||
1519 | /* Quick-and-dirty check, using half the solver: | ||
1520 | * solver_obvious will only fail if the dots are | ||
1521 | * too close together, so dot-proximity associations | ||
1522 | * overlap. */ | ||
1523 | game_state *tmp = dup_game(state); | ||
1524 | int ret = solver_obvious(tmp); | ||
1525 | free_game(tmp); | ||
1526 | return (ret == -1) ? 1 : 0; | ||
1527 | } | ||
1528 | |||
1529 | static game_state *load_game(const game_params *params, const char *desc, | ||
1530 | char **why_r) | ||
1531 | { | ||
1532 | game_state *state = blank_game(params->w, params->h); | ||
1533 | char *why = NULL; | ||
1534 | int i, x, y, n; | ||
1535 | unsigned int df; | ||
1536 | |||
1537 | i = 0; | ||
1538 | while (*desc) { | ||
1539 | n = *desc++; | ||
1540 | if (n == 'z') { | ||
1541 | i += 25; | ||
1542 | continue; | ||
1543 | } | ||
1544 | if (n >= 'a' && n <= 'y') { | ||
1545 | i += n - 'a'; | ||
1546 | df = 0; | ||
1547 | } else if (n >= 'A' && n <= 'Y') { | ||
1548 | i += n - 'A'; | ||
1549 | df = F_DOT_BLACK; | ||
1550 | } else { | ||
1551 | why = "Invalid characters in game description"; goto fail; | ||
1552 | } | ||
1553 | /* if we got here we incremented i and have a dot to add. */ | ||
1554 | y = (i / (state->sx-2)) + 1; | ||
1555 | x = (i % (state->sx-2)) + 1; | ||
1556 | if (!INUI(state, x, y)) { | ||
1557 | why = "Too much data to fit in grid"; goto fail; | ||
1558 | } | ||
1559 | add_dot(&SPACE(state, x, y)); | ||
1560 | SPACE(state, x, y).flags |= df; | ||
1561 | i++; | ||
1562 | } | ||
1563 | game_update_dots(state); | ||
1564 | |||
1565 | if (dots_too_close(state)) { | ||
1566 | why = "Dots too close together"; goto fail; | ||
1567 | } | ||
1568 | |||
1569 | return state; | ||
1570 | |||
1571 | fail: | ||
1572 | free_game(state); | ||
1573 | if (why_r) *why_r = why; | ||
1574 | return NULL; | ||
1575 | } | ||
1576 | |||
1577 | static char *validate_desc(const game_params *params, const char *desc) | ||
1578 | { | ||
1579 | char *why = NULL; | ||
1580 | game_state *dummy = load_game(params, desc, &why); | ||
1581 | if (dummy) { | ||
1582 | free_game(dummy); | ||
1583 | assert(!why); | ||
1584 | } else | ||
1585 | assert(why); | ||
1586 | return why; | ||
1587 | } | ||
1588 | |||
1589 | static game_state *new_game(midend *me, const game_params *params, | ||
1590 | const char *desc) | ||
1591 | { | ||
1592 | game_state *state = load_game(params, desc, NULL); | ||
1593 | if (!state) { | ||
1594 | assert("Unable to load ?validated game."); | ||
1595 | return NULL; | ||
1596 | } | ||
1597 | #ifdef EDITOR | ||
1598 | state->me = me; | ||
1599 | #endif | ||
1600 | return state; | ||
1601 | } | ||
1602 | |||
1603 | /* ---------------------------------------------------------- | ||
1604 | * Solver and all its little wizards. | ||
1605 | */ | ||
1606 | |||
1607 | int solver_recurse_depth; | ||
1608 | |||
1609 | typedef struct solver_ctx { | ||
1610 | game_state *state; | ||
1611 | int sz; /* state->sx * state->sy */ | ||
1612 | space **scratch; /* size sz */ | ||
1613 | |||
1614 | } solver_ctx; | ||
1615 | |||
1616 | static solver_ctx *new_solver(game_state *state) | ||
1617 | { | ||
1618 | solver_ctx *sctx = snew(solver_ctx); | ||
1619 | sctx->state = state; | ||
1620 | sctx->sz = state->sx*state->sy; | ||
1621 | sctx->scratch = snewn(sctx->sz, space *); | ||
1622 | return sctx; | ||
1623 | } | ||
1624 | |||
1625 | static void free_solver(solver_ctx *sctx) | ||
1626 | { | ||
1627 | sfree(sctx->scratch); | ||
1628 | sfree(sctx); | ||
1629 | } | ||
1630 | |||
1631 | /* Solver ideas so far: | ||
1632 | * | ||
1633 | * For any empty space, work out how many dots it could associate | ||
1634 | * with: | ||
1635 | * it needs line-of-sight | ||
1636 | * it needs an empty space on the far side | ||
1637 | * any adjacent lines need corresponding line possibilities. | ||
1638 | */ | ||
1639 | |||
1640 | /* The solver_ctx should keep a list of dot positions, for quicker looping. | ||
1641 | * | ||
1642 | * Solver techniques, in order of difficulty: | ||
1643 | * obvious adjacency to dots | ||
1644 | * transferring tiles to opposite side | ||
1645 | * transferring lines to opposite side | ||
1646 | * one possible dot for a given tile based on opposite availability | ||
1647 | * tile with 3 definite edges next to an associated tile must associate | ||
1648 | with same dot. | ||
1649 | * | ||
1650 | * one possible dot for a given tile based on line-of-sight | ||
1651 | */ | ||
1652 | |||
1653 | static int solver_add_assoc(game_state *state, space *tile, int dx, int dy, | ||
1654 | const char *why) | ||
1655 | { | ||
1656 | space *dot, *tile_opp; | ||
1657 | |||
1658 | dot = &SPACE(state, dx, dy); | ||
1659 | tile_opp = space_opposite_dot(state, tile, dot); | ||
1660 | |||
1661 | assert(tile->type == s_tile); | ||
1662 | if (tile->flags & F_TILE_ASSOC) { | ||
1663 | if ((tile->dotx != dx) || (tile->doty != dy)) { | ||
1664 | solvep(("%*sSet %d,%d --> %d,%d (%s) impossible; " | ||
1665 | "already --> %d,%d.\n", | ||
1666 | solver_recurse_depth*4, "", | ||
1667 | tile->x, tile->y, dx, dy, why, | ||
1668 | tile->dotx, tile->doty)); | ||
1669 | return -1; | ||
1670 | } | ||
1671 | return 0; /* no-op */ | ||
1672 | } | ||
1673 | if (!tile_opp) { | ||
1674 | solvep(("%*s%d,%d --> %d,%d impossible, no opposite tile.\n", | ||
1675 | solver_recurse_depth*4, "", tile->x, tile->y, dx, dy)); | ||
1676 | return -1; | ||
1677 | } | ||
1678 | if (tile_opp->flags & F_TILE_ASSOC && | ||
1679 | (tile_opp->dotx != dx || tile_opp->doty != dy)) { | ||
1680 | solvep(("%*sSet %d,%d --> %d,%d (%s) impossible; " | ||
1681 | "opposite already --> %d,%d.\n", | ||
1682 | solver_recurse_depth*4, "", | ||
1683 | tile->x, tile->y, dx, dy, why, | ||
1684 | tile_opp->dotx, tile_opp->doty)); | ||
1685 | return -1; | ||
1686 | } | ||
1687 | |||
1688 | add_assoc(state, tile, dot); | ||
1689 | add_assoc(state, tile_opp, dot); | ||
1690 | solvep(("%*sSetting %d,%d --> %d,%d (%s).\n", | ||
1691 | solver_recurse_depth*4, "", | ||
1692 | tile->x, tile->y,dx, dy, why)); | ||
1693 | solvep(("%*sSetting %d,%d --> %d,%d (%s, opposite).\n", | ||
1694 | solver_recurse_depth*4, "", | ||
1695 | tile_opp->x, tile_opp->y, dx, dy, why)); | ||
1696 | return 1; | ||
1697 | } | ||
1698 | |||
1699 | static int solver_obvious_dot(game_state *state, space *dot) | ||
1700 | { | ||
1701 | int dx, dy, ret, didsth = 0; | ||
1702 | space *tile; | ||
1703 | |||
1704 | debug(("%*ssolver_obvious_dot for %d,%d.\n", | ||
1705 | solver_recurse_depth*4, "", dot->x, dot->y)); | ||
1706 | |||
1707 | assert(dot->flags & F_DOT); | ||
1708 | for (dx = -1; dx <= 1; dx++) { | ||
1709 | for (dy = -1; dy <= 1; dy++) { | ||
1710 | if (!INGRID(state, dot->x+dx, dot->y+dy)) continue; | ||
1711 | |||
1712 | tile = &SPACE(state, dot->x+dx, dot->y+dy); | ||
1713 | if (tile->type == s_tile) { | ||
1714 | ret = solver_add_assoc(state, tile, dot->x, dot->y, | ||
1715 | "next to dot"); | ||
1716 | if (ret < 0) return -1; | ||
1717 | if (ret > 0) didsth = 1; | ||
1718 | } | ||
1719 | } | ||
1720 | } | ||
1721 | return didsth; | ||
1722 | } | ||
1723 | |||
1724 | static int solver_obvious(game_state *state) | ||
1725 | { | ||
1726 | int i, didsth = 0, ret; | ||
1727 | |||
1728 | debug(("%*ssolver_obvious.\n", solver_recurse_depth*4, "")); | ||
1729 | |||
1730 | for (i = 0; i < state->ndots; i++) { | ||
1731 | ret = solver_obvious_dot(state, state->dots[i]); | ||
1732 | if (ret < 0) return -1; | ||
1733 | if (ret > 0) didsth = 1; | ||
1734 | } | ||
1735 | return didsth; | ||
1736 | } | ||
1737 | |||
1738 | static int solver_lines_opposite_cb(game_state *state, space *edge, void *ctx) | ||
1739 | { | ||
1740 | int didsth = 0, n, dx, dy; | ||
1741 | space *tiles[2], *tile_opp, *edge_opp; | ||
1742 | |||
1743 | assert(edge->type == s_edge); | ||
1744 | |||
1745 | tiles_from_edge(state, edge, tiles); | ||
1746 | |||
1747 | /* if tiles[0] && tiles[1] && they're both associated | ||
1748 | * and they're both associated with different dots, | ||
1749 | * ensure the line is set. */ | ||
1750 | if (!(edge->flags & F_EDGE_SET) && | ||
1751 | tiles[0] && tiles[1] && | ||
1752 | (tiles[0]->flags & F_TILE_ASSOC) && | ||
1753 | (tiles[1]->flags & F_TILE_ASSOC) && | ||
1754 | (tiles[0]->dotx != tiles[1]->dotx || | ||
1755 | tiles[0]->doty != tiles[1]->doty)) { | ||
1756 | /* No edge, but the two adjacent tiles are both | ||
1757 | * associated with different dots; add the edge. */ | ||
1758 | solvep(("%*sSetting edge %d,%d - tiles different dots.\n", | ||
1759 | solver_recurse_depth*4, "", edge->x, edge->y)); | ||
1760 | edge->flags |= F_EDGE_SET; | ||
1761 | didsth = 1; | ||
1762 | } | ||
1763 | |||
1764 | if (!(edge->flags & F_EDGE_SET)) return didsth; | ||
1765 | for (n = 0; n < 2; n++) { | ||
1766 | if (!tiles[n]) continue; | ||
1767 | assert(tiles[n]->type == s_tile); | ||
1768 | if (!(tiles[n]->flags & F_TILE_ASSOC)) continue; | ||
1769 | |||
1770 | tile_opp = tile_opposite(state, tiles[n]); | ||
1771 | if (!tile_opp) { | ||
1772 | solvep(("%*simpossible: edge %d,%d has assoc. tile %d,%d" | ||
1773 | " with no opposite.\n", | ||
1774 | solver_recurse_depth*4, "", | ||
1775 | edge->x, edge->y, tiles[n]->x, tiles[n]->y)); | ||
1776 | /* edge of tile has no opposite edge (off grid?); | ||
1777 | * this is impossible. */ | ||
1778 | return -1; | ||
1779 | } | ||
1780 | |||
1781 | dx = tiles[n]->x - edge->x; | ||
1782 | dy = tiles[n]->y - edge->y; | ||
1783 | assert(INGRID(state, tile_opp->x+dx, tile_opp->y+dy)); | ||
1784 | edge_opp = &SPACE(state, tile_opp->x+dx, tile_opp->y+dy); | ||
1785 | if (!(edge_opp->flags & F_EDGE_SET)) { | ||
1786 | solvep(("%*sSetting edge %d,%d as opposite %d,%d\n", | ||
1787 | solver_recurse_depth*4, "", | ||
1788 | tile_opp->x-dx, tile_opp->y-dy, edge->x, edge->y)); | ||
1789 | edge_opp->flags |= F_EDGE_SET; | ||
1790 | didsth = 1; | ||
1791 | } | ||
1792 | } | ||
1793 | return didsth; | ||
1794 | } | ||
1795 | |||
1796 | static int solver_spaces_oneposs_cb(game_state *state, space *tile, void *ctx) | ||
1797 | { | ||
1798 | int n, eset, ret; | ||
1799 | space *edgeadj[4], *tileadj[4]; | ||
1800 | int dotx, doty; | ||
1801 | |||
1802 | assert(tile->type == s_tile); | ||
1803 | if (tile->flags & F_TILE_ASSOC) return 0; | ||
1804 | |||
1805 | adjacencies(state, tile, edgeadj, tileadj); | ||
1806 | |||
1807 | /* Empty tile. If each edge is either set, or associated with | ||
1808 | * the same dot, we must also associate with dot. */ | ||
1809 | eset = 0; dotx = -1; doty = -1; | ||
1810 | for (n = 0; n < 4; n++) { | ||
1811 | assert(edgeadj[n]); | ||
1812 | assert(edgeadj[n]->type == s_edge); | ||
1813 | if (edgeadj[n]->flags & F_EDGE_SET) { | ||
1814 | eset++; | ||
1815 | } else { | ||
1816 | assert(tileadj[n]); | ||
1817 | assert(tileadj[n]->type == s_tile); | ||
1818 | |||
1819 | /* If an adjacent tile is empty we can't make any deductions.*/ | ||
1820 | if (!(tileadj[n]->flags & F_TILE_ASSOC)) | ||
1821 | return 0; | ||
1822 | |||
1823 | /* If an adjacent tile is assoc. with a different dot | ||
1824 | * we can't make any deductions. */ | ||
1825 | if (dotx != -1 && doty != -1 && | ||
1826 | (tileadj[n]->dotx != dotx || | ||
1827 | tileadj[n]->doty != doty)) | ||
1828 | return 0; | ||
1829 | |||
1830 | dotx = tileadj[n]->dotx; | ||
1831 | doty = tileadj[n]->doty; | ||
1832 | } | ||
1833 | } | ||
1834 | if (eset == 4) { | ||
1835 | solvep(("%*simpossible: empty tile %d,%d has 4 edges\n", | ||
1836 | solver_recurse_depth*4, "", | ||
1837 | tile->x, tile->y)); | ||
1838 | return -1; | ||
1839 | } | ||
1840 | assert(dotx != -1 && doty != -1); | ||
1841 | |||
1842 | ret = solver_add_assoc(state, tile, dotx, doty, "rest are edges"); | ||
1843 | if (ret == -1) return -1; | ||
1844 | assert(ret != 0); /* really should have done something. */ | ||
1845 | |||
1846 | return 1; | ||
1847 | } | ||
1848 | |||
1849 | /* Improved algorithm for tracking line-of-sight from dots, and not spaces. | ||
1850 | * | ||
1851 | * The solver_ctx already stores a list of dots: the algorithm proceeds by | ||
1852 | * expanding outwards from each dot in turn, expanding first to the boundary | ||
1853 | * of its currently-connected tile and then to all empty tiles that could see | ||
1854 | * it. Empty tiles will be flagged with a 'can see dot <x,y>' sticker. | ||
1855 | * | ||
1856 | * Expansion will happen by (symmetrically opposite) pairs of squares; if | ||
1857 | * a square hasn't an opposite number there's no point trying to expand through | ||
1858 | * it. Empty tiles will therefore also be tagged in pairs. | ||
1859 | * | ||
1860 | * If an empty tile already has a 'can see dot <x,y>' tag from a previous dot, | ||
1861 | * it (and its partner) gets untagged (or, rather, a 'can see two dots' tag) | ||
1862 | * because we're looking for single-dot possibilities. | ||
1863 | * | ||
1864 | * Once we've gone through all the dots, any which still have a 'can see dot' | ||
1865 | * tag get associated with that dot (because it must have been the only one); | ||
1866 | * any without any tag (i.e. that could see _no_ dots) cause an impossibility | ||
1867 | * marked. | ||
1868 | * | ||
1869 | * The expansion will happen each time with a stored list of (space *) pairs, | ||
1870 | * rather than a mark-and-sweep idea; that's horrifically inefficient. | ||
1871 | * | ||
1872 | * expansion algorithm: | ||
1873 | * | ||
1874 | * * allocate list of (space *) the size of s->sx*s->sy. | ||
1875 | * * allocate second grid for (flags, dotx, doty) size of sx*sy. | ||
1876 | * | ||
1877 | * clear second grid (flags = 0, all dotx and doty = 0) | ||
1878 | * flags: F_REACHABLE, F_MULTIPLE | ||
1879 | * | ||
1880 | * | ||
1881 | * * for each dot, start with one pair of tiles that are associated with it -- | ||
1882 | * * vertex --> (dx+1, dy+1), (dx-1, dy-1) | ||
1883 | * * edge --> (adj1, adj2) | ||
1884 | * * tile --> (tile, tile) ??? | ||
1885 | * * mark that pair of tiles with F_MARK, clear all other F_MARKs. | ||
1886 | * * add two tiles to start of list. | ||
1887 | * | ||
1888 | * set start = 0, end = next = 2 | ||
1889 | * | ||
1890 | * from (start to end-1, step 2) { | ||
1891 | * * we have two tiles (t1, t2), opposites wrt our dot. | ||
1892 | * * for each (at1) sensible adjacent tile to t1 (i.e. not past an edge): | ||
1893 | * * work out at2 as the opposite to at1 | ||
1894 | * * assert at1 and at2 have the same F_MARK values. | ||
1895 | * * if at1 & F_MARK ignore it (we've been there on a previous sweep) | ||
1896 | * * if either are associated with a different dot | ||
1897 | * * mark both with F_MARK (so we ignore them later) | ||
1898 | * * otherwise (assoc. with our dot, or empty): | ||
1899 | * * mark both with F_MARK | ||
1900 | * * add their space * values to the end of the list, set next += 2. | ||
1901 | * } | ||
1902 | * | ||
1903 | * if (end == next) | ||
1904 | * * we didn't add any new squares; exit the loop. | ||
1905 | * else | ||
1906 | * * set start = next+1, end = next. go round again | ||
1907 | * | ||
1908 | * We've finished expanding from the dot. Now, for each square we have | ||
1909 | * in our list (--> each square with F_MARK): | ||
1910 | * * if the tile is empty: | ||
1911 | * * if F_REACHABLE was already set | ||
1912 | * * set F_MULTIPLE | ||
1913 | * * otherwise | ||
1914 | * * set F_REACHABLE, set dotx and doty to our dot. | ||
1915 | * | ||
1916 | * Then, continue the whole thing for each dot in turn. | ||
1917 | * | ||
1918 | * Once we've done for each dot, go through the entire grid looking for | ||
1919 | * empty tiles: for each empty tile: | ||
1920 | * if F_REACHABLE and not F_MULTIPLE, set that dot (and its double) | ||
1921 | * if !F_REACHABLE, return as impossible. | ||
1922 | * | ||
1923 | */ | ||
1924 | |||
1925 | /* Returns 1 if this tile is either already associated with this dot, | ||
1926 | * or blank. */ | ||
1927 | static int solver_expand_checkdot(space *tile, space *dot) | ||
1928 | { | ||
1929 | if (!(tile->flags & F_TILE_ASSOC)) return 1; | ||
1930 | if (tile->dotx == dot->x && tile->doty == dot->y) return 1; | ||
1931 | return 0; | ||
1932 | } | ||
1933 | |||
1934 | static void solver_expand_fromdot(game_state *state, space *dot, solver_ctx *sctx) | ||
1935 | { | ||
1936 | int i, j, x, y, start, end, next; | ||
1937 | space *sp; | ||
1938 | |||
1939 | /* Clear the grid of the (space) flags we'll use. */ | ||
1940 | |||
1941 | /* This is well optimised; analysis showed that: | ||
1942 | for (i = 0; i < sctx->sz; i++) state->grid[i].flags &= ~F_MARK; | ||
1943 | took up ~85% of the total function time! */ | ||
1944 | for (y = 1; y < state->sy; y += 2) { | ||
1945 | sp = &SPACE(state, 1, y); | ||
1946 | for (x = 1; x < state->sx; x += 2, sp += 2) | ||
1947 | sp->flags &= ~F_MARK; | ||
1948 | } | ||
1949 | |||
1950 | /* Seed the list of marked squares with two that must be associated | ||
1951 | * with our dot (possibly the same space) */ | ||
1952 | if (dot->type == s_tile) { | ||
1953 | sctx->scratch[0] = sctx->scratch[1] = dot; | ||
1954 | } else if (dot->type == s_edge) { | ||
1955 | tiles_from_edge(state, dot, sctx->scratch); | ||
1956 | } else if (dot->type == s_vertex) { | ||
1957 | /* pick two of the opposite ones arbitrarily. */ | ||
1958 | sctx->scratch[0] = &SPACE(state, dot->x-1, dot->y-1); | ||
1959 | sctx->scratch[1] = &SPACE(state, dot->x+1, dot->y+1); | ||
1960 | } | ||
1961 | assert(sctx->scratch[0]->flags & F_TILE_ASSOC); | ||
1962 | assert(sctx->scratch[1]->flags & F_TILE_ASSOC); | ||
1963 | |||
1964 | sctx->scratch[0]->flags |= F_MARK; | ||
1965 | sctx->scratch[1]->flags |= F_MARK; | ||
1966 | |||
1967 | debug(("%*sexpand from dot %d,%d seeded with %d,%d and %d,%d.\n", | ||
1968 | solver_recurse_depth*4, "", dot->x, dot->y, | ||
1969 | sctx->scratch[0]->x, sctx->scratch[0]->y, | ||
1970 | sctx->scratch[1]->x, sctx->scratch[1]->y)); | ||
1971 | |||
1972 | start = 0; end = 2; next = 2; | ||
1973 | |||
1974 | expand: | ||
1975 | debug(("%*sexpand: start %d, end %d, next %d\n", | ||
1976 | solver_recurse_depth*4, "", start, end, next)); | ||
1977 | for (i = start; i < end; i += 2) { | ||
1978 | space *t1 = sctx->scratch[i]/*, *t2 = sctx->scratch[i+1]*/; | ||
1979 | space *edges[4], *tileadj[4], *tileadj2; | ||
1980 | |||
1981 | adjacencies(state, t1, edges, tileadj); | ||
1982 | |||
1983 | for (j = 0; j < 4; j++) { | ||
1984 | assert(edges[j]); | ||
1985 | if (edges[j]->flags & F_EDGE_SET) continue; | ||
1986 | assert(tileadj[j]); | ||
1987 | |||
1988 | if (tileadj[j]->flags & F_MARK) continue; /* seen before. */ | ||
1989 | |||
1990 | /* We have a tile adjacent to t1; find its opposite. */ | ||
1991 | tileadj2 = space_opposite_dot(state, tileadj[j], dot); | ||
1992 | if (!tileadj2) { | ||
1993 | debug(("%*sMarking %d,%d, no opposite.\n", | ||
1994 | solver_recurse_depth*4, "", | ||
1995 | tileadj[j]->x, tileadj[j]->y)); | ||
1996 | tileadj[j]->flags |= F_MARK; | ||
1997 | continue; /* no opposite, so mark for next time. */ | ||
1998 | } | ||
1999 | /* If the tile had an opposite we should have either seen both of | ||
2000 | * these, or neither of these, before. */ | ||
2001 | assert(!(tileadj2->flags & F_MARK)); | ||
2002 | |||
2003 | if (solver_expand_checkdot(tileadj[j], dot) && | ||
2004 | solver_expand_checkdot(tileadj2, dot)) { | ||
2005 | /* Both tiles could associate with this dot; add them to | ||
2006 | * our list. */ | ||
2007 | debug(("%*sAdding %d,%d and %d,%d to possibles list.\n", | ||
2008 | solver_recurse_depth*4, "", | ||
2009 | tileadj[j]->x, tileadj[j]->y, tileadj2->x, tileadj2->y)); | ||
2010 | sctx->scratch[next++] = tileadj[j]; | ||
2011 | sctx->scratch[next++] = tileadj2; | ||
2012 | } | ||
2013 | /* Either way, we've seen these tiles already so mark them. */ | ||
2014 | debug(("%*sMarking %d,%d and %d,%d.\n", | ||
2015 | solver_recurse_depth*4, "", | ||
2016 | tileadj[j]->x, tileadj[j]->y, tileadj2->x, tileadj2->y)); | ||
2017 | tileadj[j]->flags |= F_MARK; | ||
2018 | tileadj2->flags |= F_MARK; | ||
2019 | } | ||
2020 | } | ||
2021 | if (next > end) { | ||
2022 | /* We added more squares; go back and try again. */ | ||
2023 | start = end; end = next; goto expand; | ||
2024 | } | ||
2025 | |||
2026 | /* We've expanded as far as we can go. Now we update the main flags | ||
2027 | * on all tiles we've expanded into -- if they were empty, we have | ||
2028 | * found possible associations for this dot. */ | ||
2029 | for (i = 0; i < end; i++) { | ||
2030 | if (sctx->scratch[i]->flags & F_TILE_ASSOC) continue; | ||
2031 | if (sctx->scratch[i]->flags & F_REACHABLE) { | ||
2032 | /* This is (at least) the second dot this tile could | ||
2033 | * associate with. */ | ||
2034 | debug(("%*sempty tile %d,%d could assoc. other dot %d,%d\n", | ||
2035 | solver_recurse_depth*4, "", | ||
2036 | sctx->scratch[i]->x, sctx->scratch[i]->y, dot->x, dot->y)); | ||
2037 | sctx->scratch[i]->flags |= F_MULTIPLE; | ||
2038 | } else { | ||
2039 | /* This is the first (possibly only) dot. */ | ||
2040 | debug(("%*sempty tile %d,%d could assoc. 1st dot %d,%d\n", | ||
2041 | solver_recurse_depth*4, "", | ||
2042 | sctx->scratch[i]->x, sctx->scratch[i]->y, dot->x, dot->y)); | ||
2043 | sctx->scratch[i]->flags |= F_REACHABLE; | ||
2044 | sctx->scratch[i]->dotx = dot->x; | ||
2045 | sctx->scratch[i]->doty = dot->y; | ||
2046 | } | ||
2047 | } | ||
2048 | dbg_state(state); | ||
2049 | } | ||
2050 | |||
2051 | static int solver_expand_postcb(game_state *state, space *tile, void *ctx) | ||
2052 | { | ||
2053 | assert(tile->type == s_tile); | ||
2054 | |||
2055 | if (tile->flags & F_TILE_ASSOC) return 0; | ||
2056 | |||
2057 | if (!(tile->flags & F_REACHABLE)) { | ||
2058 | solvep(("%*simpossible: space (%d,%d) can reach no dots.\n", | ||
2059 | solver_recurse_depth*4, "", tile->x, tile->y)); | ||
2060 | return -1; | ||
2061 | } | ||
2062 | if (tile->flags & F_MULTIPLE) return 0; | ||
2063 | |||
2064 | return solver_add_assoc(state, tile, tile->dotx, tile->doty, | ||
2065 | "single possible dot after expansion"); | ||
2066 | } | ||
2067 | |||
2068 | static int solver_expand_dots(game_state *state, solver_ctx *sctx) | ||
2069 | { | ||
2070 | int i; | ||
2071 | |||
2072 | for (i = 0; i < sctx->sz; i++) | ||
2073 | state->grid[i].flags &= ~(F_REACHABLE|F_MULTIPLE); | ||
2074 | |||
2075 | for (i = 0; i < state->ndots; i++) | ||
2076 | solver_expand_fromdot(state, state->dots[i], sctx); | ||
2077 | |||
2078 | return foreach_tile(state, solver_expand_postcb, IMPOSSIBLE_QUITS, sctx); | ||
2079 | } | ||
2080 | |||
2081 | struct recurse_ctx { | ||
2082 | space *best; | ||
2083 | int bestn; | ||
2084 | }; | ||
2085 | |||
2086 | static int solver_recurse_cb(game_state *state, space *tile, void *ctx) | ||
2087 | { | ||
2088 | struct recurse_ctx *rctx = (struct recurse_ctx *)ctx; | ||
2089 | int i, n = 0; | ||
2090 | |||
2091 | assert(tile->type == s_tile); | ||
2092 | if (tile->flags & F_TILE_ASSOC) return 0; | ||
2093 | |||
2094 | /* We're unassociated: count up all the dots we could associate with. */ | ||
2095 | for (i = 0; i < state->ndots; i++) { | ||
2096 | if (dotfortile(state, tile, state->dots[i])) | ||
2097 | n++; | ||
2098 | } | ||
2099 | if (n > rctx->bestn) { | ||
2100 | rctx->bestn = n; | ||
2101 | rctx->best = tile; | ||
2102 | } | ||
2103 | return 0; | ||
2104 | } | ||
2105 | |||
2106 | #define MAXRECURSE 5 | ||
2107 | |||
2108 | static int solver_recurse(game_state *state, int maxdiff) | ||
2109 | { | ||
2110 | int diff = DIFF_IMPOSSIBLE, ret, n, gsz = state->sx * state->sy; | ||
2111 | space *ingrid, *outgrid = NULL, *bestopp; | ||
2112 | struct recurse_ctx rctx; | ||
2113 | |||
2114 | if (solver_recurse_depth >= MAXRECURSE) { | ||
2115 | solvep(("Limiting recursion to %d, returning.", MAXRECURSE)); | ||
2116 | return DIFF_UNFINISHED; | ||
2117 | } | ||
2118 | |||
2119 | /* Work out the cell to recurse on; go through all unassociated tiles | ||
2120 | * and find which one has the most possible dots it could associate | ||
2121 | * with. */ | ||
2122 | rctx.best = NULL; | ||
2123 | rctx.bestn = 0; | ||
2124 | |||
2125 | foreach_tile(state, solver_recurse_cb, 0, &rctx); | ||
2126 | if (rctx.bestn == 0) return DIFF_IMPOSSIBLE; /* or assert? */ | ||
2127 | assert(rctx.best); | ||
2128 | |||
2129 | solvep(("%*sRecursing around %d,%d, with %d possible dots.\n", | ||
2130 | solver_recurse_depth*4, "", | ||
2131 | rctx.best->x, rctx.best->y, rctx.bestn)); | ||
2132 | |||
2133 | #ifdef STANDALONE_SOLVER | ||
2134 | solver_recurse_depth++; | ||
2135 | #endif | ||
2136 | |||
2137 | ingrid = snewn(gsz, space); | ||
2138 | memcpy(ingrid, state->grid, gsz * sizeof(space)); | ||
2139 | |||
2140 | for (n = 0; n < state->ndots; n++) { | ||
2141 | memcpy(state->grid, ingrid, gsz * sizeof(space)); | ||
2142 | |||
2143 | if (!dotfortile(state, rctx.best, state->dots[n])) continue; | ||
2144 | |||
2145 | /* set cell (temporarily) pointing to that dot. */ | ||
2146 | solver_add_assoc(state, rctx.best, | ||
2147 | state->dots[n]->x, state->dots[n]->y, | ||
2148 | "Attempting for recursion"); | ||
2149 | |||
2150 | ret = solver_state(state, maxdiff); | ||
2151 | |||
2152 | if (diff == DIFF_IMPOSSIBLE && ret != DIFF_IMPOSSIBLE) { | ||
2153 | /* we found our first solved grid; copy it away. */ | ||
2154 | assert(!outgrid); | ||
2155 | outgrid = snewn(gsz, space); | ||
2156 | memcpy(outgrid, state->grid, gsz * sizeof(space)); | ||
2157 | } | ||
2158 | /* reset cell back to unassociated. */ | ||
2159 | bestopp = tile_opposite(state, rctx.best); | ||
2160 | assert(bestopp && bestopp->flags & F_TILE_ASSOC); | ||
2161 | |||
2162 | remove_assoc(state, rctx.best); | ||
2163 | remove_assoc(state, bestopp); | ||
2164 | |||
2165 | if (ret == DIFF_AMBIGUOUS || ret == DIFF_UNFINISHED) | ||
2166 | diff = ret; | ||
2167 | else if (ret == DIFF_IMPOSSIBLE) | ||
2168 | /* no change */; | ||
2169 | else { | ||
2170 | /* precisely one solution */ | ||
2171 | if (diff == DIFF_IMPOSSIBLE) | ||
2172 | diff = DIFF_UNREASONABLE; | ||
2173 | else | ||
2174 | diff = DIFF_AMBIGUOUS; | ||
2175 | } | ||
2176 | /* if we've found >1 solution, or ran out of recursion, | ||
2177 | * give up immediately. */ | ||
2178 | if (diff == DIFF_AMBIGUOUS || diff == DIFF_UNFINISHED) | ||
2179 | break; | ||
2180 | } | ||
2181 | |||
2182 | #ifdef STANDALONE_SOLVER | ||
2183 | solver_recurse_depth--; | ||
2184 | #endif | ||
2185 | |||
2186 | if (outgrid) { | ||
2187 | /* we found (at least one) soln; copy it back to state */ | ||
2188 | memcpy(state->grid, outgrid, gsz * sizeof(space)); | ||
2189 | sfree(outgrid); | ||
2190 | } | ||
2191 | sfree(ingrid); | ||
2192 | return diff; | ||
2193 | } | ||
2194 | |||
2195 | static int solver_state(game_state *state, int maxdiff) | ||
2196 | { | ||
2197 | solver_ctx *sctx = new_solver(state); | ||
2198 | int ret, diff = DIFF_NORMAL; | ||
2199 | |||
2200 | #ifdef STANDALONE_PICTURE_GENERATOR | ||
2201 | /* hack, hack: set picture to NULL during solving so that add_assoc | ||
2202 | * won't complain when we attempt recursive guessing and guess wrong */ | ||
2203 | int *savepic = picture; | ||
2204 | picture = NULL; | ||
2205 | #endif | ||
2206 | |||
2207 | ret = solver_obvious(state); | ||
2208 | if (ret < 0) { | ||
2209 | diff = DIFF_IMPOSSIBLE; | ||
2210 | goto got_result; | ||
2211 | } | ||
2212 | |||
2213 | #define CHECKRET(d) do { \ | ||
2214 | if (ret < 0) { diff = DIFF_IMPOSSIBLE; goto got_result; } \ | ||
2215 | if (ret > 0) { diff = max(diff, (d)); goto cont; } \ | ||
2216 | } while(0) | ||
2217 | |||
2218 | while (1) { | ||
2219 | cont: | ||
2220 | ret = foreach_edge(state, solver_lines_opposite_cb, | ||
2221 | IMPOSSIBLE_QUITS, sctx); | ||
2222 | CHECKRET(DIFF_NORMAL); | ||
2223 | |||
2224 | ret = foreach_tile(state, solver_spaces_oneposs_cb, | ||
2225 | IMPOSSIBLE_QUITS, sctx); | ||
2226 | CHECKRET(DIFF_NORMAL); | ||
2227 | |||
2228 | ret = solver_expand_dots(state, sctx); | ||
2229 | CHECKRET(DIFF_NORMAL); | ||
2230 | |||
2231 | if (maxdiff <= DIFF_NORMAL) | ||
2232 | break; | ||
2233 | |||
2234 | /* harder still? */ | ||
2235 | |||
2236 | /* if we reach here, we've made no deductions, so we terminate. */ | ||
2237 | break; | ||
2238 | } | ||
2239 | |||
2240 | if (check_complete(state, NULL, NULL)) goto got_result; | ||
2241 | |||
2242 | diff = (maxdiff >= DIFF_UNREASONABLE) ? | ||
2243 | solver_recurse(state, maxdiff) : DIFF_UNFINISHED; | ||
2244 | |||
2245 | got_result: | ||
2246 | free_solver(sctx); | ||
2247 | #ifndef STANDALONE_SOLVER | ||
2248 | debug(("solver_state ends, diff %s:\n", galaxies_diffnames[diff])); | ||
2249 | dbg_state(state); | ||
2250 | #endif | ||
2251 | |||
2252 | #ifdef STANDALONE_PICTURE_GENERATOR | ||
2253 | picture = savepic; | ||
2254 | #endif | ||
2255 | |||
2256 | return diff; | ||
2257 | } | ||
2258 | |||
2259 | #ifndef EDITOR | ||
2260 | static char *solve_game(const game_state *state, const game_state *currstate, | ||
2261 | const char *aux, char **error) | ||
2262 | { | ||
2263 | game_state *tosolve; | ||
2264 | char *ret; | ||
2265 | int i; | ||
2266 | int diff; | ||
2267 | |||
2268 | tosolve = dup_game(currstate); | ||
2269 | diff = solver_state(tosolve, DIFF_UNREASONABLE); | ||
2270 | if (diff != DIFF_UNFINISHED && diff != DIFF_IMPOSSIBLE) { | ||
2271 | debug(("solve_game solved with current state.\n")); | ||
2272 | goto solved; | ||
2273 | } | ||
2274 | free_game(tosolve); | ||
2275 | |||
2276 | tosolve = dup_game(state); | ||
2277 | diff = solver_state(tosolve, DIFF_UNREASONABLE); | ||
2278 | if (diff != DIFF_UNFINISHED && diff != DIFF_IMPOSSIBLE) { | ||
2279 | debug(("solve_game solved with original state.\n")); | ||
2280 | goto solved; | ||
2281 | } | ||
2282 | free_game(tosolve); | ||
2283 | |||
2284 | return NULL; | ||
2285 | |||
2286 | solved: | ||
2287 | /* | ||
2288 | * Clear tile associations: the solution will only include the | ||
2289 | * edges. | ||
2290 | */ | ||
2291 | for (i = 0; i < tosolve->sx*tosolve->sy; i++) | ||
2292 | tosolve->grid[i].flags &= ~F_TILE_ASSOC; | ||
2293 | ret = diff_game(currstate, tosolve, 1); | ||
2294 | free_game(tosolve); | ||
2295 | return ret; | ||
2296 | } | ||
2297 | #endif | ||
2298 | |||
2299 | /* ---------------------------------------------------------- | ||
2300 | * User interface. | ||
2301 | */ | ||
2302 | |||
2303 | struct game_ui { | ||
2304 | int dragging; | ||
2305 | int dx, dy; /* pixel coords of drag pos. */ | ||
2306 | int dotx, doty; /* grid coords of dot we're dragging from. */ | ||
2307 | int srcx, srcy; /* grid coords of drag start */ | ||
2308 | int cur_x, cur_y, cur_visible; | ||
2309 | }; | ||
2310 | |||
2311 | static game_ui *new_ui(const game_state *state) | ||
2312 | { | ||
2313 | game_ui *ui = snew(game_ui); | ||
2314 | ui->dragging = FALSE; | ||
2315 | ui->cur_x = ui->cur_y = 1; | ||
2316 | ui->cur_visible = 0; | ||
2317 | return ui; | ||
2318 | } | ||
2319 | |||
2320 | static void free_ui(game_ui *ui) | ||
2321 | { | ||
2322 | sfree(ui); | ||
2323 | } | ||
2324 | |||
2325 | static char *encode_ui(const game_ui *ui) | ||
2326 | { | ||
2327 | return NULL; | ||
2328 | } | ||
2329 | |||
2330 | static void decode_ui(game_ui *ui, const char *encoding) | ||
2331 | { | ||
2332 | } | ||
2333 | |||
2334 | static void game_changed_state(game_ui *ui, const game_state *oldstate, | ||
2335 | const game_state *newstate) | ||
2336 | { | ||
2337 | } | ||
2338 | |||
2339 | #define FLASH_TIME 0.15F | ||
2340 | |||
2341 | #define PREFERRED_TILE_SIZE 32 | ||
2342 | #define TILE_SIZE (ds->tilesize) | ||
2343 | #define DOT_SIZE (TILE_SIZE / 4) | ||
2344 | #define EDGE_THICKNESS (max(TILE_SIZE / 16, 2)) | ||
2345 | #define BORDER TILE_SIZE | ||
2346 | |||
2347 | #define COORD(x) ( (x) * TILE_SIZE + BORDER ) | ||
2348 | #define SCOORD(x) ( ((x) * TILE_SIZE)/2 + BORDER ) | ||
2349 | #define FROMCOORD(x) ( ((x) - BORDER) / TILE_SIZE ) | ||
2350 | |||
2351 | #define DRAW_WIDTH (BORDER * 2 + ds->w * TILE_SIZE) | ||
2352 | #define DRAW_HEIGHT (BORDER * 2 + ds->h * TILE_SIZE) | ||
2353 | |||
2354 | #define CURSOR_SIZE DOT_SIZE | ||
2355 | |||
2356 | struct game_drawstate { | ||
2357 | int started; | ||
2358 | int w, h; | ||
2359 | int tilesize; | ||
2360 | unsigned long *grid; | ||
2361 | int *dx, *dy; | ||
2362 | blitter *bl; | ||
2363 | blitter *blmirror; | ||
2364 | |||
2365 | int dragging, dragx, dragy; | ||
2366 | |||
2367 | int *colour_scratch; | ||
2368 | |||
2369 | int cx, cy, cur_visible; | ||
2370 | blitter *cur_bl; | ||
2371 | }; | ||
2372 | |||
2373 | #define CORNER_TOLERANCE 0.15F | ||
2374 | #define CENTRE_TOLERANCE 0.15F | ||
2375 | |||
2376 | /* | ||
2377 | * Round FP coordinates to the centre of the nearest edge. | ||
2378 | */ | ||
2379 | #ifndef EDITOR | ||
2380 | static void coord_round_to_edge(float x, float y, int *xr, int *yr) | ||
2381 | { | ||
2382 | float xs, ys, xv, yv, dx, dy; | ||
2383 | |||
2384 | /* | ||
2385 | * Find the nearest square-centre. | ||
2386 | */ | ||
2387 | xs = (float)floor(x) + 0.5F; | ||
2388 | ys = (float)floor(y) + 0.5F; | ||
2389 | |||
2390 | /* | ||
2391 | * Find the nearest grid vertex. | ||
2392 | */ | ||
2393 | xv = (float)floor(x + 0.5F); | ||
2394 | yv = (float)floor(y + 0.5F); | ||
2395 | |||
2396 | /* | ||
2397 | * Determine whether the horizontal or vertical edge from that | ||
2398 | * vertex alongside that square is closer to us, by comparing | ||
2399 | * distances from the square cente. | ||
2400 | */ | ||
2401 | dx = (float)fabs(x - xs); | ||
2402 | dy = (float)fabs(y - ys); | ||
2403 | if (dx > dy) { | ||
2404 | /* Vertical edge: x-coord of corner, | ||
2405 | * y-coord of square centre. */ | ||
2406 | *xr = 2 * (int)xv; | ||
2407 | *yr = 1 + 2 * (int)floor(ys); | ||
2408 | } else { | ||
2409 | /* Horizontal edge: x-coord of square centre, | ||
2410 | * y-coord of corner. */ | ||
2411 | *xr = 1 + 2 * (int)floor(xs); | ||
2412 | *yr = 2 * (int)yv; | ||
2413 | } | ||
2414 | } | ||
2415 | #endif | ||
2416 | |||
2417 | #ifdef EDITOR | ||
2418 | static char *interpret_move(const game_state *state, game_ui *ui, | ||
2419 | const game_drawstate *ds, | ||
2420 | int x, int y, int button) | ||
2421 | { | ||
2422 | char buf[80]; | ||
2423 | int px, py; | ||
2424 | space *sp; | ||
2425 | |||
2426 | px = 2*FROMCOORD((float)x) + 0.5; | ||
2427 | py = 2*FROMCOORD((float)y) + 0.5; | ||
2428 | |||
2429 | state->cdiff = -1; | ||
2430 | |||
2431 | if (button == 'C' || button == 'c') return dupstr("C"); | ||
2432 | |||
2433 | if (button == 'S' || button == 's') { | ||
2434 | char *ret; | ||
2435 | game_state *tmp = dup_game(state); | ||
2436 | state->cdiff = solver_state(tmp, DIFF_UNREASONABLE-1); | ||
2437 | ret = diff_game(state, tmp, 0); | ||
2438 | free_game(tmp); | ||
2439 | return ret; | ||
2440 | } | ||
2441 | |||
2442 | if (button == LEFT_BUTTON || button == RIGHT_BUTTON) { | ||
2443 | if (!INUI(state, px, py)) return NULL; | ||
2444 | sp = &SPACE(state, px, py); | ||
2445 | if (!dot_is_possible(state, sp, 1)) return NULL; | ||
2446 | sprintf(buf, "%c%d,%d", | ||
2447 | (char)((button == LEFT_BUTTON) ? 'D' : 'd'), px, py); | ||
2448 | return dupstr(buf); | ||
2449 | } | ||
2450 | |||
2451 | return NULL; | ||
2452 | } | ||
2453 | #else | ||
2454 | static char *interpret_move(const game_state *state, game_ui *ui, | ||
2455 | const game_drawstate *ds, | ||
2456 | int x, int y, int button) | ||
2457 | { | ||
2458 | /* UI operations (play mode): | ||
2459 | * | ||
2460 | * Toggle edge (set/unset) (left-click on edge) | ||
2461 | * Associate space with dot (left-drag from dot) | ||
2462 | * Unassociate space (left-drag from space off grid) | ||
2463 | * Autofill lines around shape? (right-click?) | ||
2464 | * | ||
2465 | * (edit mode; will clear all lines/associations) | ||
2466 | * | ||
2467 | * Add or remove dot (left-click) | ||
2468 | */ | ||
2469 | char buf[80]; | ||
2470 | const char *sep = ""; | ||
2471 | int px, py; | ||
2472 | space *sp, *dot; | ||
2473 | |||
2474 | buf[0] = '\0'; | ||
2475 | |||
2476 | if (button == 'H' || button == 'h') { | ||
2477 | char *ret; | ||
2478 | game_state *tmp = dup_game(state); | ||
2479 | solver_obvious(tmp); | ||
2480 | ret = diff_game(state, tmp, 0); | ||
2481 | free_game(tmp); | ||
2482 | return ret; | ||
2483 | } | ||
2484 | |||
2485 | if (button == LEFT_BUTTON) { | ||
2486 | ui->cur_visible = 0; | ||
2487 | coord_round_to_edge(FROMCOORD((float)x), FROMCOORD((float)y), | ||
2488 | &px, &py); | ||
2489 | |||
2490 | if (!INUI(state, px, py)) return NULL; | ||
2491 | |||
2492 | sp = &SPACE(state, px, py); | ||
2493 | assert(sp->type == s_edge); | ||
2494 | { | ||
2495 | sprintf(buf, "E%d,%d", px, py); | ||
2496 | return dupstr(buf); | ||
2497 | } | ||
2498 | } else if (button == RIGHT_BUTTON) { | ||
2499 | int px1, py1; | ||
2500 | |||
2501 | ui->cur_visible = 0; | ||
2502 | |||
2503 | px = (int)(2*FROMCOORD((float)x) + 0.5); | ||
2504 | py = (int)(2*FROMCOORD((float)y) + 0.5); | ||
2505 | |||
2506 | dot = NULL; | ||
2507 | |||
2508 | /* | ||
2509 | * If there's a dot anywhere nearby, we pick up an arrow | ||
2510 | * pointing at that dot. | ||
2511 | */ | ||
2512 | for (py1 = py-1; py1 <= py+1; py1++) | ||
2513 | for (px1 = px-1; px1 <= px+1; px1++) { | ||
2514 | if (px1 >= 0 && px1 < state->sx && | ||
2515 | py1 >= 0 && py1 < state->sy && | ||
2516 | x >= SCOORD(px1-1) && x < SCOORD(px1+1) && | ||
2517 | y >= SCOORD(py1-1) && y < SCOORD(py1+1) && | ||
2518 | SPACE(state, px1, py1).flags & F_DOT) { | ||
2519 | /* | ||
2520 | * Found a dot. Begin a drag from it. | ||
2521 | */ | ||
2522 | dot = &SPACE(state, px1, py1); | ||
2523 | ui->srcx = px1; | ||
2524 | ui->srcy = py1; | ||
2525 | goto done; /* multi-level break */ | ||
2526 | } | ||
2527 | } | ||
2528 | |||
2529 | /* | ||
2530 | * Otherwise, find the nearest _square_, and pick up the | ||
2531 | * same arrow as it's got on it, if any. | ||
2532 | */ | ||
2533 | if (!dot) { | ||
2534 | px = 2*FROMCOORD(x+TILE_SIZE) - 1; | ||
2535 | py = 2*FROMCOORD(y+TILE_SIZE) - 1; | ||
2536 | if (px >= 0 && px < state->sx && py >= 0 && py < state->sy) { | ||
2537 | sp = &SPACE(state, px, py); | ||
2538 | if (sp->flags & F_TILE_ASSOC) { | ||
2539 | dot = &SPACE(state, sp->dotx, sp->doty); | ||
2540 | ui->srcx = px; | ||
2541 | ui->srcy = py; | ||
2542 | } | ||
2543 | } | ||
2544 | } | ||
2545 | |||
2546 | done: | ||
2547 | /* | ||
2548 | * Now, if we've managed to find a dot, begin a drag. | ||
2549 | */ | ||
2550 | if (dot) { | ||
2551 | ui->dragging = TRUE; | ||
2552 | ui->dx = x; | ||
2553 | ui->dy = y; | ||
2554 | ui->dotx = dot->x; | ||
2555 | ui->doty = dot->y; | ||
2556 | return ""; | ||
2557 | } | ||
2558 | } else if (button == RIGHT_DRAG && ui->dragging) { | ||
2559 | /* just move the drag coords. */ | ||
2560 | ui->dx = x; | ||
2561 | ui->dy = y; | ||
2562 | return ""; | ||
2563 | } else if (button == RIGHT_RELEASE && ui->dragging) { | ||
2564 | ui->dragging = FALSE; | ||
2565 | |||
2566 | /* | ||
2567 | * Drags are always targeted at a single square. | ||
2568 | */ | ||
2569 | px = 2*FROMCOORD(x+TILE_SIZE) - 1; | ||
2570 | py = 2*FROMCOORD(y+TILE_SIZE) - 1; | ||
2571 | |||
2572 | /* | ||
2573 | * Dragging an arrow on to the same square it started from | ||
2574 | * is a null move; just update the ui and finish. | ||
2575 | */ | ||
2576 | if (px == ui->srcx && py == ui->srcy) | ||
2577 | return ""; | ||
2578 | |||
2579 | /* | ||
2580 | * Otherwise, we remove the arrow from its starting | ||
2581 | * square if we didn't start from a dot... | ||
2582 | */ | ||
2583 | if ((ui->srcx != ui->dotx || ui->srcy != ui->doty) && | ||
2584 | SPACE(state, ui->srcx, ui->srcy).flags & F_TILE_ASSOC) { | ||
2585 | sprintf(buf + strlen(buf), "%sU%d,%d", sep, ui->srcx, ui->srcy); | ||
2586 | sep = ";"; | ||
2587 | } | ||
2588 | |||
2589 | /* | ||
2590 | * ... and if the square we're moving it _to_ is valid, we | ||
2591 | * add one there instead. | ||
2592 | */ | ||
2593 | if (INUI(state, px, py)) { | ||
2594 | sp = &SPACE(state, px, py); | ||
2595 | |||
2596 | if (!(sp->flags & F_DOT)) | ||
2597 | sprintf(buf + strlen(buf), "%sA%d,%d,%d,%d", | ||
2598 | sep, px, py, ui->dotx, ui->doty); | ||
2599 | } | ||
2600 | |||
2601 | if (buf[0]) | ||
2602 | return dupstr(buf); | ||
2603 | else | ||
2604 | return ""; | ||
2605 | } else if (IS_CURSOR_MOVE(button)) { | ||
2606 | move_cursor(button, &ui->cur_x, &ui->cur_y, state->sx-1, state->sy-1, 0); | ||
2607 | if (ui->cur_x < 1) ui->cur_x = 1; | ||
2608 | if (ui->cur_y < 1) ui->cur_y = 1; | ||
2609 | ui->cur_visible = 1; | ||
2610 | if (ui->dragging) { | ||
2611 | ui->dx = SCOORD(ui->cur_x); | ||
2612 | ui->dy = SCOORD(ui->cur_y); | ||
2613 | } | ||
2614 | return ""; | ||
2615 | } else if (IS_CURSOR_SELECT(button)) { | ||
2616 | if (!ui->cur_visible) { | ||
2617 | ui->cur_visible = 1; | ||
2618 | return ""; | ||
2619 | } | ||
2620 | sp = &SPACE(state, ui->cur_x, ui->cur_y); | ||
2621 | if (ui->dragging) { | ||
2622 | ui->dragging = FALSE; | ||
2623 | |||
2624 | if ((ui->srcx != ui->dotx || ui->srcy != ui->doty) && | ||
2625 | SPACE(state, ui->srcx, ui->srcy).flags & F_TILE_ASSOC) { | ||
2626 | sprintf(buf, "%sU%d,%d", sep, ui->srcx, ui->srcy); | ||
2627 | sep = ";"; | ||
2628 | } | ||
2629 | if (sp->type == s_tile && !(sp->flags & F_DOT) && !(sp->flags & F_TILE_ASSOC)) { | ||
2630 | sprintf(buf + strlen(buf), "%sA%d,%d,%d,%d", | ||
2631 | sep, ui->cur_x, ui->cur_y, ui->dotx, ui->doty); | ||
2632 | } | ||
2633 | return dupstr(buf); | ||
2634 | } else if (sp->flags & F_DOT) { | ||
2635 | ui->dragging = TRUE; | ||
2636 | ui->dx = SCOORD(ui->cur_x); | ||
2637 | ui->dy = SCOORD(ui->cur_y); | ||
2638 | ui->dotx = ui->srcx = ui->cur_x; | ||
2639 | ui->doty = ui->srcy = ui->cur_y; | ||
2640 | return ""; | ||
2641 | } else if (sp->flags & F_TILE_ASSOC) { | ||
2642 | assert(sp->type == s_tile); | ||
2643 | ui->dragging = TRUE; | ||
2644 | ui->dx = SCOORD(ui->cur_x); | ||
2645 | ui->dy = SCOORD(ui->cur_y); | ||
2646 | ui->dotx = sp->dotx; | ||
2647 | ui->doty = sp->doty; | ||
2648 | ui->srcx = ui->cur_x; | ||
2649 | ui->srcy = ui->cur_y; | ||
2650 | return ""; | ||
2651 | } else if (sp->type == s_edge) { | ||
2652 | sprintf(buf, "E%d,%d", ui->cur_x, ui->cur_y); | ||
2653 | return dupstr(buf); | ||
2654 | } | ||
2655 | } | ||
2656 | |||
2657 | return NULL; | ||
2658 | } | ||
2659 | #endif | ||
2660 | |||
2661 | static int check_complete(const game_state *state, int *dsf, int *colours) | ||
2662 | { | ||
2663 | int w = state->w, h = state->h; | ||
2664 | int x, y, i, ret; | ||
2665 | |||
2666 | int free_dsf; | ||
2667 | struct sqdata { | ||
2668 | int minx, miny, maxx, maxy; | ||
2669 | int cx, cy; | ||
2670 | int valid, colour; | ||
2671 | } *sqdata; | ||
2672 | |||
2673 | if (!dsf) { | ||
2674 | dsf = snew_dsf(w*h); | ||
2675 | free_dsf = TRUE; | ||
2676 | } else { | ||
2677 | dsf_init(dsf, w*h); | ||
2678 | free_dsf = FALSE; | ||
2679 | } | ||
2680 | |||
2681 | /* | ||
2682 | * During actual game play, completion checking is done on the | ||
2683 | * basis of the edges rather than the square associations. So | ||
2684 | * first we must go through the grid figuring out the connected | ||
2685 | * components into which the edges divide it. | ||
2686 | */ | ||
2687 | for (y = 0; y < h; y++) | ||
2688 | for (x = 0; x < w; x++) { | ||
2689 | if (y+1 < h && !(SPACE(state, 2*x+1, 2*y+2).flags & F_EDGE_SET)) | ||
2690 | dsf_merge(dsf, y*w+x, (y+1)*w+x); | ||
2691 | if (x+1 < w && !(SPACE(state, 2*x+2, 2*y+1).flags & F_EDGE_SET)) | ||
2692 | dsf_merge(dsf, y*w+x, y*w+(x+1)); | ||
2693 | } | ||
2694 | |||
2695 | /* | ||
2696 | * That gives us our connected components. Now, for each | ||
2697 | * component, decide whether it's _valid_. A valid component is | ||
2698 | * one which: | ||
2699 | * | ||
2700 | * - is 180-degree rotationally symmetric | ||
2701 | * - has a dot at its centre of symmetry | ||
2702 | * - has no other dots anywhere within it (including on its | ||
2703 | * boundary) | ||
2704 | * - contains no internal edges (i.e. edges separating two | ||
2705 | * squares which are both part of the component). | ||
2706 | */ | ||
2707 | |||
2708 | /* | ||
2709 | * First, go through the grid finding the bounding box of each | ||
2710 | * component. | ||
2711 | */ | ||
2712 | sqdata = snewn(w*h, struct sqdata); | ||
2713 | for (i = 0; i < w*h; i++) { | ||
2714 | sqdata[i].minx = w+1; | ||
2715 | sqdata[i].miny = h+1; | ||
2716 | sqdata[i].maxx = sqdata[i].maxy = -1; | ||
2717 | sqdata[i].valid = FALSE; | ||
2718 | } | ||
2719 | for (y = 0; y < h; y++) | ||
2720 | for (x = 0; x < w; x++) { | ||
2721 | i = dsf_canonify(dsf, y*w+x); | ||
2722 | if (sqdata[i].minx > x) | ||
2723 | sqdata[i].minx = x; | ||
2724 | if (sqdata[i].maxx < x) | ||
2725 | sqdata[i].maxx = x; | ||
2726 | if (sqdata[i].miny > y) | ||
2727 | sqdata[i].miny = y; | ||
2728 | if (sqdata[i].maxy < y) | ||
2729 | sqdata[i].maxy = y; | ||
2730 | sqdata[i].valid = TRUE; | ||
2731 | } | ||
2732 | |||
2733 | /* | ||
2734 | * Now we're in a position to loop over each actual component | ||
2735 | * and figure out where its centre of symmetry has to be if | ||
2736 | * it's anywhere. | ||
2737 | */ | ||
2738 | for (i = 0; i < w*h; i++) | ||
2739 | if (sqdata[i].valid) { | ||
2740 | int cx, cy; | ||
2741 | cx = sqdata[i].cx = sqdata[i].minx + sqdata[i].maxx + 1; | ||
2742 | cy = sqdata[i].cy = sqdata[i].miny + sqdata[i].maxy + 1; | ||
2743 | if (!(SPACE(state, sqdata[i].cx, sqdata[i].cy).flags & F_DOT)) | ||
2744 | sqdata[i].valid = FALSE; /* no dot at centre of symmetry */ | ||
2745 | if (dsf_canonify(dsf, (cy-1)/2*w+(cx-1)/2) != i || | ||
2746 | dsf_canonify(dsf, (cy)/2*w+(cx-1)/2) != i || | ||
2747 | dsf_canonify(dsf, (cy-1)/2*w+(cx)/2) != i || | ||
2748 | dsf_canonify(dsf, (cy)/2*w+(cx)/2) != i) | ||
2749 | sqdata[i].valid = FALSE; /* dot at cx,cy isn't ours */ | ||
2750 | if (SPACE(state, sqdata[i].cx, sqdata[i].cy).flags & F_DOT_BLACK) | ||
2751 | sqdata[i].colour = 2; | ||
2752 | else | ||
2753 | sqdata[i].colour = 1; | ||
2754 | } | ||
2755 | |||
2756 | /* | ||
2757 | * Now we loop over the whole grid again, this time finding | ||
2758 | * extraneous dots (any dot which wholly or partially overlaps | ||
2759 | * a square and is not at the centre of symmetry of that | ||
2760 | * square's component disqualifies the component from validity) | ||
2761 | * and extraneous edges (any edge separating two squares | ||
2762 | * belonging to the same component also disqualifies that | ||
2763 | * component). | ||
2764 | */ | ||
2765 | for (y = 1; y < state->sy-1; y++) | ||
2766 | for (x = 1; x < state->sx-1; x++) { | ||
2767 | space *sp = &SPACE(state, x, y); | ||
2768 | |||
2769 | if (sp->flags & F_DOT) { | ||
2770 | /* | ||
2771 | * There's a dot here. Use it to disqualify any | ||
2772 | * component which deserves it. | ||
2773 | */ | ||
2774 | int cx, cy; | ||
2775 | for (cy = (y-1) >> 1; cy <= y >> 1; cy++) | ||
2776 | for (cx = (x-1) >> 1; cx <= x >> 1; cx++) { | ||
2777 | i = dsf_canonify(dsf, cy*w+cx); | ||
2778 | if (x != sqdata[i].cx || y != sqdata[i].cy) | ||
2779 | sqdata[i].valid = FALSE; | ||
2780 | } | ||
2781 | } | ||
2782 | |||
2783 | if (sp->flags & F_EDGE_SET) { | ||
2784 | /* | ||
2785 | * There's an edge here. Use it to disqualify a | ||
2786 | * component if necessary. | ||
2787 | */ | ||
2788 | int cx1 = (x-1) >> 1, cx2 = x >> 1; | ||
2789 | int cy1 = (y-1) >> 1, cy2 = y >> 1; | ||
2790 | assert((cx1==cx2) ^ (cy1==cy2)); | ||
2791 | i = dsf_canonify(dsf, cy1*w+cx1); | ||
2792 | if (i == dsf_canonify(dsf, cy2*w+cx2)) | ||
2793 | sqdata[i].valid = FALSE; | ||
2794 | } | ||
2795 | } | ||
2796 | |||
2797 | /* | ||
2798 | * And finally we test rotational symmetry: for each square in | ||
2799 | * the grid, find which component it's in, test that that | ||
2800 | * component also has a square in the symmetric position, and | ||
2801 | * disqualify it if it doesn't. | ||
2802 | */ | ||
2803 | for (y = 0; y < h; y++) | ||
2804 | for (x = 0; x < w; x++) { | ||
2805 | int x2, y2; | ||
2806 | |||
2807 | i = dsf_canonify(dsf, y*w+x); | ||
2808 | |||
2809 | x2 = sqdata[i].cx - 1 - x; | ||
2810 | y2 = sqdata[i].cy - 1 - y; | ||
2811 | if (i != dsf_canonify(dsf, y2*w+x2)) | ||
2812 | sqdata[i].valid = FALSE; | ||
2813 | } | ||
2814 | |||
2815 | /* | ||
2816 | * That's it. We now have all the connected components marked | ||
2817 | * as valid or not valid. So now we return a `colours' array if | ||
2818 | * we were asked for one, and also we return an overall | ||
2819 | * true/false value depending on whether _every_ square in the | ||
2820 | * grid is part of a valid component. | ||
2821 | */ | ||
2822 | ret = TRUE; | ||
2823 | for (i = 0; i < w*h; i++) { | ||
2824 | int ci = dsf_canonify(dsf, i); | ||
2825 | int thisok = sqdata[ci].valid; | ||
2826 | if (colours) | ||
2827 | colours[i] = thisok ? sqdata[ci].colour : 0; | ||
2828 | ret = ret && thisok; | ||
2829 | } | ||
2830 | |||
2831 | sfree(sqdata); | ||
2832 | if (free_dsf) | ||
2833 | sfree(dsf); | ||
2834 | |||
2835 | return ret; | ||
2836 | } | ||
2837 | |||
2838 | static game_state *execute_move(const game_state *state, const char *move) | ||
2839 | { | ||
2840 | int x, y, ax, ay, n, dx, dy; | ||
2841 | game_state *ret = dup_game(state); | ||
2842 | space *sp, *dot; | ||
2843 | int currently_solving = FALSE; | ||
2844 | |||
2845 | debug(("%s\n", move)); | ||
2846 | |||
2847 | while (*move) { | ||
2848 | char c = *move; | ||
2849 | if (c == 'E' || c == 'U' || c == 'M' | ||
2850 | #ifdef EDITOR | ||
2851 | || c == 'D' || c == 'd' | ||
2852 | #endif | ||
2853 | ) { | ||
2854 | move++; | ||
2855 | if (sscanf(move, "%d,%d%n", &x, &y, &n) != 2 || | ||
2856 | !INUI(ret, x, y)) | ||
2857 | goto badmove; | ||
2858 | |||
2859 | sp = &SPACE(ret, x, y); | ||
2860 | #ifdef EDITOR | ||
2861 | if (c == 'D' || c == 'd') { | ||
2862 | unsigned int currf, newf, maskf; | ||
2863 | |||
2864 | if (!dot_is_possible(ret, sp, 1)) goto badmove; | ||
2865 | |||
2866 | newf = F_DOT | (c == 'd' ? F_DOT_BLACK : 0); | ||
2867 | currf = GRID(ret, grid, x, y).flags; | ||
2868 | maskf = F_DOT | F_DOT_BLACK; | ||
2869 | /* if we clicked 'white dot': | ||
2870 | * white --> empty, empty --> white, black --> white. | ||
2871 | * if we clicked 'black dot': | ||
2872 | * black --> empty, empty --> black, white --> black. | ||
2873 | */ | ||
2874 | if (currf & maskf) { | ||
2875 | sp->flags &= ~maskf; | ||
2876 | if ((currf & maskf) != newf) | ||
2877 | sp->flags |= newf; | ||
2878 | } else | ||
2879 | sp->flags |= newf; | ||
2880 | sp->nassoc = 0; /* edit-mode disallows associations. */ | ||
2881 | game_update_dots(ret); | ||
2882 | } else | ||
2883 | #endif | ||
2884 | if (c == 'E') { | ||
2885 | if (sp->type != s_edge) goto badmove; | ||
2886 | sp->flags ^= F_EDGE_SET; | ||
2887 | } else if (c == 'U') { | ||
2888 | if (sp->type != s_tile || !(sp->flags & F_TILE_ASSOC)) | ||
2889 | goto badmove; | ||
2890 | /* The solver doesn't assume we'll mirror things */ | ||
2891 | if (currently_solving) | ||
2892 | remove_assoc(ret, sp); | ||
2893 | else | ||
2894 | remove_assoc_with_opposite(ret, sp); | ||
2895 | } else if (c == 'M') { | ||
2896 | if (!(sp->flags & F_DOT)) goto badmove; | ||
2897 | sp->flags ^= F_DOT_HOLD; | ||
2898 | } | ||
2899 | move += n; | ||
2900 | } else if (c == 'A' || c == 'a') { | ||
2901 | move++; | ||
2902 | if (sscanf(move, "%d,%d,%d,%d%n", &x, &y, &ax, &ay, &n) != 4 || | ||
2903 | x < 1 || y < 1 || x >= (ret->sx-1) || y >= (ret->sy-1) || | ||
2904 | ax < 1 || ay < 1 || ax >= (ret->sx-1) || ay >= (ret->sy-1)) | ||
2905 | goto badmove; | ||
2906 | |||
2907 | dot = &GRID(ret, grid, ax, ay); | ||
2908 | if (!(dot->flags & F_DOT))goto badmove; | ||
2909 | if (dot->flags & F_DOT_HOLD) goto badmove; | ||
2910 | |||
2911 | for (dx = -1; dx <= 1; dx++) { | ||
2912 | for (dy = -1; dy <= 1; dy++) { | ||
2913 | sp = &GRID(ret, grid, x+dx, y+dy); | ||
2914 | if (sp->type != s_tile) continue; | ||
2915 | if (sp->flags & F_TILE_ASSOC) { | ||
2916 | space *dot = &SPACE(ret, sp->dotx, sp->doty); | ||
2917 | if (dot->flags & F_DOT_HOLD) continue; | ||
2918 | } | ||
2919 | /* The solver doesn't assume we'll mirror things */ | ||
2920 | if (currently_solving) | ||
2921 | add_assoc(ret, sp, dot); | ||
2922 | else | ||
2923 | add_assoc_with_opposite(ret, sp, dot); | ||
2924 | } | ||
2925 | } | ||
2926 | move += n; | ||
2927 | #ifdef EDITOR | ||
2928 | } else if (c == 'C') { | ||
2929 | move++; | ||
2930 | clear_game(ret, 1); | ||
2931 | #endif | ||
2932 | } else if (c == 'S') { | ||
2933 | move++; | ||
2934 | ret->used_solve = 1; | ||
2935 | currently_solving = TRUE; | ||
2936 | } else | ||
2937 | goto badmove; | ||
2938 | |||
2939 | if (*move == ';') | ||
2940 | move++; | ||
2941 | else if (*move) | ||
2942 | goto badmove; | ||
2943 | } | ||
2944 | if (check_complete(ret, NULL, NULL)) | ||
2945 | ret->completed = 1; | ||
2946 | return ret; | ||
2947 | |||
2948 | badmove: | ||
2949 | free_game(ret); | ||
2950 | return NULL; | ||
2951 | } | ||
2952 | |||
2953 | /* ---------------------------------------------------------------------- | ||
2954 | * Drawing routines. | ||
2955 | */ | ||
2956 | |||
2957 | /* Lines will be much smaller size than squares; say, 1/8 the size? | ||
2958 | * | ||
2959 | * Need a 'top-left corner of location XxY' to take this into account; | ||
2960 | * alternaticaly, that could give the middle of that location, and the | ||
2961 | * drawing code would just know the expected dimensions. | ||
2962 | * | ||
2963 | * We also need something to take a click and work out what it was | ||
2964 | * we were interested in. Clicking on vertices is required because | ||
2965 | * we may want to drag from them, for example. | ||
2966 | */ | ||
2967 | |||
2968 | static void game_compute_size(const game_params *params, int sz, | ||
2969 | int *x, int *y) | ||
2970 | { | ||
2971 | struct { int tilesize, w, h; } ads, *ds = &ads; | ||
2972 | |||
2973 | ds->tilesize = sz; | ||
2974 | ds->w = params->w; | ||
2975 | ds->h = params->h; | ||
2976 | |||
2977 | *x = DRAW_WIDTH; | ||
2978 | *y = DRAW_HEIGHT; | ||
2979 | } | ||
2980 | |||
2981 | static void game_set_size(drawing *dr, game_drawstate *ds, | ||
2982 | const game_params *params, int sz) | ||
2983 | { | ||
2984 | ds->tilesize = sz; | ||
2985 | |||
2986 | assert(TILE_SIZE > 0); | ||
2987 | |||
2988 | assert(!ds->bl); | ||
2989 | ds->bl = blitter_new(dr, TILE_SIZE, TILE_SIZE); | ||
2990 | |||
2991 | assert(!ds->blmirror); | ||
2992 | ds->blmirror = blitter_new(dr, TILE_SIZE, TILE_SIZE); | ||
2993 | |||
2994 | assert(!ds->cur_bl); | ||
2995 | ds->cur_bl = blitter_new(dr, TILE_SIZE, TILE_SIZE); | ||
2996 | } | ||
2997 | |||
2998 | static float *game_colours(frontend *fe, int *ncolours) | ||
2999 | { | ||
3000 | float *ret = snewn(3 * NCOLOURS, float); | ||
3001 | int i; | ||
3002 | |||
3003 | /* | ||
3004 | * We call game_mkhighlight to ensure the background colour | ||
3005 | * isn't completely white. We don't actually use the high- and | ||
3006 | * lowlight colours it generates. | ||
3007 | */ | ||
3008 | game_mkhighlight(fe, ret, COL_BACKGROUND, COL_WHITEBG, COL_BLACKBG); | ||
3009 | |||
3010 | for (i = 0; i < 3; i++) { | ||
3011 | /* | ||
3012 | * Currently, white dots and white-background squares are | ||
3013 | * both pure white. | ||
3014 | */ | ||
3015 | ret[COL_WHITEDOT * 3 + i] = 1.0F; | ||
3016 | ret[COL_WHITEBG * 3 + i] = 1.0F; | ||
3017 | |||
3018 | /* | ||
3019 | * But black-background squares are a dark grey, whereas | ||
3020 | * black dots are really black. | ||
3021 | */ | ||
3022 | ret[COL_BLACKDOT * 3 + i] = 0.0F; | ||
3023 | ret[COL_BLACKBG * 3 + i] = ret[COL_BACKGROUND * 3 + i] * 0.3F; | ||
3024 | |||
3025 | /* | ||
3026 | * In unfilled squares, we draw a faint gridwork. | ||
3027 | */ | ||
3028 | ret[COL_GRID * 3 + i] = ret[COL_BACKGROUND * 3 + i] * 0.8F; | ||
3029 | |||
3030 | /* | ||
3031 | * Edges and arrows are filled in in pure black. | ||
3032 | */ | ||
3033 | ret[COL_EDGE * 3 + i] = 0.0F; | ||
3034 | ret[COL_ARROW * 3 + i] = 0.0F; | ||
3035 | } | ||
3036 | |||
3037 | #ifdef EDITOR | ||
3038 | /* tinge the edit background to bluey */ | ||
3039 | ret[COL_BACKGROUND * 3 + 0] = ret[COL_BACKGROUND * 3 + 0] * 0.8F; | ||
3040 | ret[COL_BACKGROUND * 3 + 1] = ret[COL_BACKGROUND * 3 + 0] * 0.8F; | ||
3041 | ret[COL_BACKGROUND * 3 + 2] = min(ret[COL_BACKGROUND * 3 + 0] * 1.4F, 1.0F); | ||
3042 | #endif | ||
3043 | |||
3044 | ret[COL_CURSOR * 3 + 0] = min(ret[COL_BACKGROUND * 3 + 0] * 1.4F, 1.0F); | ||
3045 | ret[COL_CURSOR * 3 + 1] = ret[COL_BACKGROUND * 3 + 0] * 0.8F; | ||
3046 | ret[COL_CURSOR * 3 + 2] = ret[COL_BACKGROUND * 3 + 0] * 0.8F; | ||
3047 | |||
3048 | *ncolours = NCOLOURS; | ||
3049 | return ret; | ||
3050 | } | ||
3051 | |||
3052 | static game_drawstate *game_new_drawstate(drawing *dr, const game_state *state) | ||
3053 | { | ||
3054 | struct game_drawstate *ds = snew(struct game_drawstate); | ||
3055 | int i; | ||
3056 | |||
3057 | ds->started = 0; | ||
3058 | ds->w = state->w; | ||
3059 | ds->h = state->h; | ||
3060 | |||
3061 | ds->grid = snewn(ds->w*ds->h, unsigned long); | ||
3062 | for (i = 0; i < ds->w*ds->h; i++) | ||
3063 | ds->grid[i] = 0xFFFFFFFFUL; | ||
3064 | ds->dx = snewn(ds->w*ds->h, int); | ||
3065 | ds->dy = snewn(ds->w*ds->h, int); | ||
3066 | |||
3067 | ds->bl = NULL; | ||
3068 | ds->blmirror = NULL; | ||
3069 | ds->dragging = FALSE; | ||
3070 | ds->dragx = ds->dragy = 0; | ||
3071 | |||
3072 | ds->colour_scratch = snewn(ds->w * ds->h, int); | ||
3073 | |||
3074 | ds->cur_bl = NULL; | ||
3075 | ds->cx = ds->cy = 0; | ||
3076 | ds->cur_visible = 0; | ||
3077 | |||
3078 | return ds; | ||
3079 | } | ||
3080 | |||
3081 | static void game_free_drawstate(drawing *dr, game_drawstate *ds) | ||
3082 | { | ||
3083 | if (ds->cur_bl) blitter_free(dr, ds->cur_bl); | ||
3084 | sfree(ds->colour_scratch); | ||
3085 | if (ds->blmirror) blitter_free(dr, ds->blmirror); | ||
3086 | if (ds->bl) blitter_free(dr, ds->bl); | ||
3087 | sfree(ds->dx); | ||
3088 | sfree(ds->dy); | ||
3089 | sfree(ds->grid); | ||
3090 | sfree(ds); | ||
3091 | } | ||
3092 | |||
3093 | #define DRAW_EDGE_L 0x0001 | ||
3094 | #define DRAW_EDGE_R 0x0002 | ||
3095 | #define DRAW_EDGE_U 0x0004 | ||
3096 | #define DRAW_EDGE_D 0x0008 | ||
3097 | #define DRAW_CORNER_UL 0x0010 | ||
3098 | #define DRAW_CORNER_UR 0x0020 | ||
3099 | #define DRAW_CORNER_DL 0x0040 | ||
3100 | #define DRAW_CORNER_DR 0x0080 | ||
3101 | #define DRAW_WHITE 0x0100 | ||
3102 | #define DRAW_BLACK 0x0200 | ||
3103 | #define DRAW_ARROW 0x0400 | ||
3104 | #define DRAW_CURSOR 0x0800 | ||
3105 | #define DOT_SHIFT_C 12 | ||
3106 | #define DOT_SHIFT_M 2 | ||
3107 | #define DOT_WHITE 1UL | ||
3108 | #define DOT_BLACK 2UL | ||
3109 | |||
3110 | /* | ||
3111 | * Draw an arrow centred on (cx,cy), pointing in the direction | ||
3112 | * (ddx,ddy). (I.e. pointing at the point (cx+ddx, cy+ddy). | ||
3113 | */ | ||
3114 | static void draw_arrow(drawing *dr, game_drawstate *ds, | ||
3115 | int cx, int cy, int ddx, int ddy, int col) | ||
3116 | { | ||
3117 | float vlen = (float)sqrt(ddx*ddx+ddy*ddy); | ||
3118 | float xdx = ddx/vlen, xdy = ddy/vlen; | ||
3119 | float ydx = -xdy, ydy = xdx; | ||
3120 | int e1x = cx + (int)(xdx*TILE_SIZE/3), e1y = cy + (int)(xdy*TILE_SIZE/3); | ||
3121 | int e2x = cx - (int)(xdx*TILE_SIZE/3), e2y = cy - (int)(xdy*TILE_SIZE/3); | ||
3122 | int adx = (int)((ydx-xdx)*TILE_SIZE/8), ady = (int)((ydy-xdy)*TILE_SIZE/8); | ||
3123 | int adx2 = (int)((-ydx-xdx)*TILE_SIZE/8), ady2 = (int)((-ydy-xdy)*TILE_SIZE/8); | ||
3124 | |||
3125 | draw_line(dr, e1x, e1y, e2x, e2y, col); | ||
3126 | draw_line(dr, e1x, e1y, e1x+adx, e1y+ady, col); | ||
3127 | draw_line(dr, e1x, e1y, e1x+adx2, e1y+ady2, col); | ||
3128 | } | ||
3129 | |||
3130 | static void draw_square(drawing *dr, game_drawstate *ds, int x, int y, | ||
3131 | unsigned long flags, int ddx, int ddy) | ||
3132 | { | ||
3133 | int lx = COORD(x), ly = COORD(y); | ||
3134 | int dx, dy; | ||
3135 | int gridcol; | ||
3136 | |||
3137 | clip(dr, lx, ly, TILE_SIZE, TILE_SIZE); | ||
3138 | |||
3139 | /* | ||
3140 | * Draw the tile background. | ||
3141 | */ | ||
3142 | draw_rect(dr, lx, ly, TILE_SIZE, TILE_SIZE, | ||
3143 | (flags & DRAW_WHITE ? COL_WHITEBG : | ||
3144 | flags & DRAW_BLACK ? COL_BLACKBG : COL_BACKGROUND)); | ||
3145 | |||
3146 | /* | ||
3147 | * Draw the grid. | ||
3148 | */ | ||
3149 | gridcol = (flags & DRAW_BLACK ? COL_BLACKDOT : COL_GRID); | ||
3150 | draw_rect(dr, lx, ly, 1, TILE_SIZE, gridcol); | ||
3151 | draw_rect(dr, lx, ly, TILE_SIZE, 1, gridcol); | ||
3152 | |||
3153 | /* | ||
3154 | * Draw the arrow, if present, or the cursor, if here. | ||
3155 | */ | ||
3156 | if (flags & DRAW_ARROW) | ||
3157 | draw_arrow(dr, ds, lx + TILE_SIZE/2, ly + TILE_SIZE/2, ddx, ddy, | ||
3158 | (flags & DRAW_CURSOR) ? COL_CURSOR : COL_ARROW); | ||
3159 | else if (flags & DRAW_CURSOR) | ||
3160 | draw_rect_outline(dr, | ||
3161 | lx + TILE_SIZE/2 - CURSOR_SIZE, | ||
3162 | ly + TILE_SIZE/2 - CURSOR_SIZE, | ||
3163 | 2*CURSOR_SIZE+1, 2*CURSOR_SIZE+1, | ||
3164 | COL_CURSOR); | ||
3165 | |||
3166 | /* | ||
3167 | * Draw the edges. | ||
3168 | */ | ||
3169 | if (flags & DRAW_EDGE_L) | ||
3170 | draw_rect(dr, lx, ly, EDGE_THICKNESS, TILE_SIZE, COL_EDGE); | ||
3171 | if (flags & DRAW_EDGE_R) | ||
3172 | draw_rect(dr, lx + TILE_SIZE - EDGE_THICKNESS + 1, ly, | ||
3173 | EDGE_THICKNESS - 1, TILE_SIZE, COL_EDGE); | ||
3174 | if (flags & DRAW_EDGE_U) | ||
3175 | draw_rect(dr, lx, ly, TILE_SIZE, EDGE_THICKNESS, COL_EDGE); | ||
3176 | if (flags & DRAW_EDGE_D) | ||
3177 | draw_rect(dr, lx, ly + TILE_SIZE - EDGE_THICKNESS + 1, | ||
3178 | TILE_SIZE, EDGE_THICKNESS - 1, COL_EDGE); | ||
3179 | if (flags & DRAW_CORNER_UL) | ||
3180 | draw_rect(dr, lx, ly, EDGE_THICKNESS, EDGE_THICKNESS, COL_EDGE); | ||
3181 | if (flags & DRAW_CORNER_UR) | ||
3182 | draw_rect(dr, lx + TILE_SIZE - EDGE_THICKNESS + 1, ly, | ||
3183 | EDGE_THICKNESS - 1, EDGE_THICKNESS, COL_EDGE); | ||
3184 | if (flags & DRAW_CORNER_DL) | ||
3185 | draw_rect(dr, lx, ly + TILE_SIZE - EDGE_THICKNESS + 1, | ||
3186 | EDGE_THICKNESS, EDGE_THICKNESS - 1, COL_EDGE); | ||
3187 | if (flags & DRAW_CORNER_DR) | ||
3188 | draw_rect(dr, lx + TILE_SIZE - EDGE_THICKNESS + 1, | ||
3189 | ly + TILE_SIZE - EDGE_THICKNESS + 1, | ||
3190 | EDGE_THICKNESS - 1, EDGE_THICKNESS - 1, COL_EDGE); | ||
3191 | |||
3192 | /* | ||
3193 | * Draw the dots. | ||
3194 | */ | ||
3195 | for (dy = 0; dy < 3; dy++) | ||
3196 | for (dx = 0; dx < 3; dx++) { | ||
3197 | int dotval = (flags >> (DOT_SHIFT_C + DOT_SHIFT_M*(dy*3+dx))); | ||
3198 | dotval &= (1 << DOT_SHIFT_M)-1; | ||
3199 | |||
3200 | if (dotval) | ||
3201 | draw_circle(dr, lx+dx*TILE_SIZE/2, ly+dy*TILE_SIZE/2, | ||
3202 | DOT_SIZE, | ||
3203 | (dotval == 1 ? COL_WHITEDOT : COL_BLACKDOT), | ||
3204 | COL_BLACKDOT); | ||
3205 | } | ||
3206 | |||
3207 | unclip(dr); | ||
3208 | draw_update(dr, lx, ly, TILE_SIZE, TILE_SIZE); | ||
3209 | } | ||
3210 | |||
3211 | static void calculate_opposite_point(const game_ui *ui, | ||
3212 | const game_drawstate *ds, const int x, | ||
3213 | const int y, int *oppositex, | ||
3214 | int *oppositey) | ||
3215 | { | ||
3216 | /* oppositex - dotx = dotx - x <=> oppositex = 2 * dotx - x */ | ||
3217 | *oppositex = 2 * SCOORD(ui->dotx) - x; | ||
3218 | *oppositey = 2 * SCOORD(ui->doty) - y; | ||
3219 | } | ||
3220 | |||
3221 | static void game_redraw(drawing *dr, game_drawstate *ds, | ||
3222 | const game_state *oldstate, const game_state *state, | ||
3223 | int dir, const game_ui *ui, | ||
3224 | float animtime, float flashtime) | ||
3225 | { | ||
3226 | int w = ds->w, h = ds->h; | ||
3227 | int x, y, flashing = FALSE; | ||
3228 | int oppx, oppy; | ||
3229 | |||
3230 | if (flashtime > 0) { | ||
3231 | int frame = (int)(flashtime / FLASH_TIME); | ||
3232 | flashing = (frame % 2 == 0); | ||
3233 | } | ||
3234 | |||
3235 | if (ds->dragging) { | ||
3236 | assert(ds->bl); | ||
3237 | assert(ds->blmirror); | ||
3238 | calculate_opposite_point(ui, ds, ds->dragx + TILE_SIZE/2, | ||
3239 | ds->dragy + TILE_SIZE/2, &oppx, &oppy); | ||
3240 | oppx -= TILE_SIZE/2; | ||
3241 | oppy -= TILE_SIZE/2; | ||
3242 | blitter_load(dr, ds->bl, ds->dragx, ds->dragy); | ||
3243 | draw_update(dr, ds->dragx, ds->dragy, TILE_SIZE, TILE_SIZE); | ||
3244 | blitter_load(dr, ds->blmirror, oppx, oppy); | ||
3245 | draw_update(dr, oppx, oppy, TILE_SIZE, TILE_SIZE); | ||
3246 | ds->dragging = FALSE; | ||
3247 | } | ||
3248 | if (ds->cur_visible) { | ||
3249 | assert(ds->cur_bl); | ||
3250 | blitter_load(dr, ds->cur_bl, ds->cx, ds->cy); | ||
3251 | draw_update(dr, ds->cx, ds->cy, CURSOR_SIZE*2+1, CURSOR_SIZE*2+1); | ||
3252 | ds->cur_visible = FALSE; | ||
3253 | } | ||
3254 | |||
3255 | if (!ds->started) { | ||
3256 | draw_rect(dr, 0, 0, DRAW_WIDTH, DRAW_HEIGHT, COL_BACKGROUND); | ||
3257 | draw_rect(dr, BORDER - EDGE_THICKNESS + 1, BORDER - EDGE_THICKNESS + 1, | ||
3258 | w*TILE_SIZE + EDGE_THICKNESS*2 - 1, | ||
3259 | h*TILE_SIZE + EDGE_THICKNESS*2 - 1, COL_EDGE); | ||
3260 | draw_update(dr, 0, 0, DRAW_WIDTH, DRAW_HEIGHT); | ||
3261 | ds->started = TRUE; | ||
3262 | } | ||
3263 | |||
3264 | check_complete(state, NULL, ds->colour_scratch); | ||
3265 | |||
3266 | for (y = 0; y < h; y++) | ||
3267 | for (x = 0; x < w; x++) { | ||
3268 | unsigned long flags = 0; | ||
3269 | int ddx = 0, ddy = 0; | ||
3270 | space *sp, *opp; | ||
3271 | int dx, dy; | ||
3272 | |||
3273 | /* | ||
3274 | * Set up the flags for this square. Firstly, see if we | ||
3275 | * have edges. | ||
3276 | */ | ||
3277 | if (SPACE(state, x*2, y*2+1).flags & F_EDGE_SET) | ||
3278 | flags |= DRAW_EDGE_L; | ||
3279 | if (SPACE(state, x*2+2, y*2+1).flags & F_EDGE_SET) | ||
3280 | flags |= DRAW_EDGE_R; | ||
3281 | if (SPACE(state, x*2+1, y*2).flags & F_EDGE_SET) | ||
3282 | flags |= DRAW_EDGE_U; | ||
3283 | if (SPACE(state, x*2+1, y*2+2).flags & F_EDGE_SET) | ||
3284 | flags |= DRAW_EDGE_D; | ||
3285 | |||
3286 | /* | ||
3287 | * Also, mark corners of neighbouring edges. | ||
3288 | */ | ||
3289 | if ((x > 0 && SPACE(state, x*2-1, y*2).flags & F_EDGE_SET) || | ||
3290 | (y > 0 && SPACE(state, x*2, y*2-1).flags & F_EDGE_SET)) | ||
3291 | flags |= DRAW_CORNER_UL; | ||
3292 | if ((x+1 < w && SPACE(state, x*2+3, y*2).flags & F_EDGE_SET) || | ||
3293 | (y > 0 && SPACE(state, x*2+2, y*2-1).flags & F_EDGE_SET)) | ||
3294 | flags |= DRAW_CORNER_UR; | ||
3295 | if ((x > 0 && SPACE(state, x*2-1, y*2+2).flags & F_EDGE_SET) || | ||
3296 | (y+1 < h && SPACE(state, x*2, y*2+3).flags & F_EDGE_SET)) | ||
3297 | flags |= DRAW_CORNER_DL; | ||
3298 | if ((x+1 < w && SPACE(state, x*2+3, y*2+2).flags & F_EDGE_SET) || | ||
3299 | (y+1 < h && SPACE(state, x*2+2, y*2+3).flags & F_EDGE_SET)) | ||
3300 | flags |= DRAW_CORNER_DR; | ||
3301 | |||
3302 | /* | ||
3303 | * If this square is part of a valid region, paint it | ||
3304 | * that region's colour. Exception: if we're flashing, | ||
3305 | * everything goes briefly back to background colour. | ||
3306 | */ | ||
3307 | sp = &SPACE(state, x*2+1, y*2+1); | ||
3308 | if (sp->flags & F_TILE_ASSOC) { | ||
3309 | opp = tile_opposite(state, sp); | ||
3310 | } else { | ||
3311 | opp = NULL; | ||
3312 | } | ||
3313 | if (ds->colour_scratch[y*w+x] && !flashing) { | ||
3314 | flags |= (ds->colour_scratch[y*w+x] == 2 ? | ||
3315 | DRAW_BLACK : DRAW_WHITE); | ||
3316 | } | ||
3317 | |||
3318 | /* | ||
3319 | * If this square is associated with a dot but it isn't | ||
3320 | * part of a valid region, draw an arrow in it pointing | ||
3321 | * in the direction of that dot. | ||
3322 | * | ||
3323 | * Exception: if this is the source point of an active | ||
3324 | * drag, we don't draw the arrow. | ||
3325 | */ | ||
3326 | if ((sp->flags & F_TILE_ASSOC) && !ds->colour_scratch[y*w+x]) { | ||
3327 | if (ui->dragging && ui->srcx == x*2+1 && ui->srcy == y*2+1) { | ||
3328 | /* tile is the source, don't do it */ | ||
3329 | } else if (ui->dragging && opp && ui->srcx == opp->x && ui->srcy == opp->y) { | ||
3330 | /* opposite tile is the source, don't do it */ | ||
3331 | } else if (sp->doty != y*2+1 || sp->dotx != x*2+1) { | ||
3332 | flags |= DRAW_ARROW; | ||
3333 | ddy = sp->doty - (y*2+1); | ||
3334 | ddx = sp->dotx - (x*2+1); | ||
3335 | } | ||
3336 | } | ||
3337 | |||
3338 | /* | ||
3339 | * Now go through the nine possible places we could | ||
3340 | * have dots. | ||
3341 | */ | ||
3342 | for (dy = 0; dy < 3; dy++) | ||
3343 | for (dx = 0; dx < 3; dx++) { | ||
3344 | sp = &SPACE(state, x*2+dx, y*2+dy); | ||
3345 | if (sp->flags & F_DOT) { | ||
3346 | unsigned long dotval = (sp->flags & F_DOT_BLACK ? | ||
3347 | DOT_BLACK : DOT_WHITE); | ||
3348 | flags |= dotval << (DOT_SHIFT_C + | ||
3349 | DOT_SHIFT_M*(dy*3+dx)); | ||
3350 | } | ||
3351 | } | ||
3352 | |||
3353 | /* | ||
3354 | * Now work out if we have to draw a cursor for this square; | ||
3355 | * cursors-on-lines are taken care of below. | ||
3356 | */ | ||
3357 | if (ui->cur_visible && | ||
3358 | ui->cur_x == x*2+1 && ui->cur_y == y*2+1 && | ||
3359 | !(SPACE(state, x*2+1, y*2+1).flags & F_DOT)) | ||
3360 | flags |= DRAW_CURSOR; | ||
3361 | |||
3362 | /* | ||
3363 | * Now we have everything we're going to need. Draw the | ||
3364 | * square. | ||
3365 | */ | ||
3366 | if (ds->grid[y*w+x] != flags || | ||
3367 | ds->dx[y*w+x] != ddx || | ||
3368 | ds->dy[y*w+x] != ddy) { | ||
3369 | draw_square(dr, ds, x, y, flags, ddx, ddy); | ||
3370 | ds->grid[y*w+x] = flags; | ||
3371 | ds->dx[y*w+x] = ddx; | ||
3372 | ds->dy[y*w+x] = ddy; | ||
3373 | } | ||
3374 | } | ||
3375 | |||
3376 | /* | ||
3377 | * Draw a cursor. This secondary blitter is much less invasive than trying | ||
3378 | * to fix up all of the rest of the code with sufficient flags to be able to | ||
3379 | * display this sensibly. | ||
3380 | */ | ||
3381 | if (ui->cur_visible) { | ||
3382 | space *sp = &SPACE(state, ui->cur_x, ui->cur_y); | ||
3383 | ds->cur_visible = TRUE; | ||
3384 | ds->cx = SCOORD(ui->cur_x) - CURSOR_SIZE; | ||
3385 | ds->cy = SCOORD(ui->cur_y) - CURSOR_SIZE; | ||
3386 | blitter_save(dr, ds->cur_bl, ds->cx, ds->cy); | ||
3387 | if (sp->flags & F_DOT) { | ||
3388 | /* draw a red dot (over the top of whatever would be there already) */ | ||
3389 | draw_circle(dr, SCOORD(ui->cur_x), SCOORD(ui->cur_y), DOT_SIZE, | ||
3390 | COL_CURSOR, COL_BLACKDOT); | ||
3391 | } else if (sp->type != s_tile) { | ||
3392 | /* draw an edge/vertex square; tile cursors are dealt with above. */ | ||
3393 | int dx = (ui->cur_x % 2) ? CURSOR_SIZE : CURSOR_SIZE/3; | ||
3394 | int dy = (ui->cur_y % 2) ? CURSOR_SIZE : CURSOR_SIZE/3; | ||
3395 | int x1 = SCOORD(ui->cur_x)-dx, y1 = SCOORD(ui->cur_y)-dy; | ||
3396 | int xs = dx*2+1, ys = dy*2+1; | ||
3397 | |||
3398 | draw_rect(dr, x1, y1, xs, ys, COL_CURSOR); | ||
3399 | } | ||
3400 | draw_update(dr, ds->cx, ds->cy, CURSOR_SIZE*2+1, CURSOR_SIZE*2+1); | ||
3401 | } | ||
3402 | |||
3403 | if (ui->dragging) { | ||
3404 | ds->dragging = TRUE; | ||
3405 | ds->dragx = ui->dx - TILE_SIZE/2; | ||
3406 | ds->dragy = ui->dy - TILE_SIZE/2; | ||
3407 | calculate_opposite_point(ui, ds, ui->dx, ui->dy, &oppx, &oppy); | ||
3408 | blitter_save(dr, ds->bl, ds->dragx, ds->dragy); | ||
3409 | blitter_save(dr, ds->blmirror, oppx - TILE_SIZE/2, oppy - TILE_SIZE/2); | ||
3410 | draw_arrow(dr, ds, ui->dx, ui->dy, SCOORD(ui->dotx) - ui->dx, | ||
3411 | SCOORD(ui->doty) - ui->dy, COL_ARROW); | ||
3412 | draw_arrow(dr, ds, oppx, oppy, SCOORD(ui->dotx) - oppx, | ||
3413 | SCOORD(ui->doty) - oppy, COL_ARROW); | ||
3414 | } | ||
3415 | #ifdef EDITOR | ||
3416 | { | ||
3417 | char buf[256]; | ||
3418 | if (state->cdiff != -1) | ||
3419 | sprintf(buf, "Puzzle is %s.", galaxies_diffnames[state->cdiff]); | ||
3420 | else | ||
3421 | buf[0] = '\0'; | ||
3422 | status_bar(dr, buf); | ||
3423 | } | ||
3424 | #endif | ||
3425 | } | ||
3426 | |||
3427 | static float game_anim_length(const game_state *oldstate, | ||
3428 | const game_state *newstate, int dir, game_ui *ui) | ||
3429 | { | ||
3430 | return 0.0F; | ||
3431 | } | ||
3432 | |||
3433 | static float game_flash_length(const game_state *oldstate, | ||
3434 | const game_state *newstate, int dir, game_ui *ui) | ||
3435 | { | ||
3436 | if ((!oldstate->completed && newstate->completed) && | ||
3437 | !(newstate->used_solve)) | ||
3438 | return 3 * FLASH_TIME; | ||
3439 | else | ||
3440 | return 0.0F; | ||
3441 | } | ||
3442 | |||
3443 | static int game_status(const game_state *state) | ||
3444 | { | ||
3445 | return state->completed ? +1 : 0; | ||
3446 | } | ||
3447 | |||
3448 | static int game_timing_state(const game_state *state, game_ui *ui) | ||
3449 | { | ||
3450 | return TRUE; | ||
3451 | } | ||
3452 | |||
3453 | #ifndef EDITOR | ||
3454 | static void game_print_size(const game_params *params, float *x, float *y) | ||
3455 | { | ||
3456 | int pw, ph; | ||
3457 | |||
3458 | /* | ||
3459 | * 8mm squares by default. (There isn't all that much detail | ||
3460 | * that needs to go in each square.) | ||
3461 | */ | ||
3462 | game_compute_size(params, 800, &pw, &ph); | ||
3463 | *x = pw / 100.0F; | ||
3464 | *y = ph / 100.0F; | ||
3465 | } | ||
3466 | |||
3467 | static void game_print(drawing *dr, const game_state *state, int sz) | ||
3468 | { | ||
3469 | int w = state->w, h = state->h; | ||
3470 | int white, black, blackish; | ||
3471 | int x, y, i, j; | ||
3472 | int *colours, *dsf; | ||
3473 | int *coords = NULL; | ||
3474 | int ncoords = 0, coordsize = 0; | ||
3475 | |||
3476 | /* Ick: fake up `ds->tilesize' for macro expansion purposes */ | ||
3477 | game_drawstate ads, *ds = &ads; | ||
3478 | ds->tilesize = sz; | ||
3479 | |||
3480 | white = print_mono_colour(dr, 1); | ||
3481 | black = print_mono_colour(dr, 0); | ||
3482 | blackish = print_hatched_colour(dr, HATCH_X); | ||
3483 | |||
3484 | /* | ||
3485 | * Get the completion information. | ||
3486 | */ | ||
3487 | dsf = snewn(w * h, int); | ||
3488 | colours = snewn(w * h, int); | ||
3489 | check_complete(state, dsf, colours); | ||
3490 | |||
3491 | /* | ||
3492 | * Draw the grid. | ||
3493 | */ | ||
3494 | print_line_width(dr, TILE_SIZE / 64); | ||
3495 | for (x = 1; x < w; x++) | ||
3496 | draw_line(dr, COORD(x), COORD(0), COORD(x), COORD(h), black); | ||
3497 | for (y = 1; y < h; y++) | ||
3498 | draw_line(dr, COORD(0), COORD(y), COORD(w), COORD(y), black); | ||
3499 | |||
3500 | /* | ||
3501 | * Shade the completed regions. Just in case any particular | ||
3502 | * printing platform deals badly with adjacent | ||
3503 | * similarly-hatched regions, we'll fill each one as a single | ||
3504 | * polygon. | ||
3505 | */ | ||
3506 | for (i = 0; i < w*h; i++) { | ||
3507 | j = dsf_canonify(dsf, i); | ||
3508 | if (colours[j] != 0) { | ||
3509 | int dx, dy, t; | ||
3510 | |||
3511 | /* | ||
3512 | * This is the first square we've run into belonging to | ||
3513 | * this polyomino, which means an edge of the polyomino | ||
3514 | * is certain to be to our left. (After we finish | ||
3515 | * tracing round it, we'll set the colours[] entry to | ||
3516 | * zero to prevent accidentally doing it again.) | ||
3517 | */ | ||
3518 | |||
3519 | x = i % w; | ||
3520 | y = i / w; | ||
3521 | dx = -1; | ||
3522 | dy = 0; | ||
3523 | ncoords = 0; | ||
3524 | while (1) { | ||
3525 | /* | ||
3526 | * We are currently sitting on square (x,y), which | ||
3527 | * we know to be in our polyomino, and we also know | ||
3528 | * that (x+dx,y+dy) is not. The way I visualise | ||
3529 | * this is that we're standing to the right of a | ||
3530 | * boundary line, stretching our left arm out to | ||
3531 | * point to the exterior square on the far side. | ||
3532 | */ | ||
3533 | |||
3534 | /* | ||
3535 | * First, check if we've gone round the entire | ||
3536 | * polyomino. | ||
3537 | */ | ||
3538 | if (ncoords > 0 && | ||
3539 | (x == i%w && y == i/w && dx == -1 && dy == 0)) | ||
3540 | break; | ||
3541 | |||
3542 | /* | ||
3543 | * Add to our coordinate list the coordinate | ||
3544 | * backwards and to the left of where we are. | ||
3545 | */ | ||
3546 | if (ncoords + 2 > coordsize) { | ||
3547 | coordsize = (ncoords * 3 / 2) + 64; | ||
3548 | coords = sresize(coords, coordsize, int); | ||
3549 | } | ||
3550 | coords[ncoords++] = COORD((2*x+1 + dx + dy) / 2); | ||
3551 | coords[ncoords++] = COORD((2*y+1 + dy - dx) / 2); | ||
3552 | |||
3553 | /* | ||
3554 | * Follow the edge round. If the square directly in | ||
3555 | * front of us is not part of the polyomino, we | ||
3556 | * turn right; if it is and so is the square in | ||
3557 | * front of (x+dx,y+dy), we turn left; otherwise we | ||
3558 | * go straight on. | ||
3559 | */ | ||
3560 | if (x-dy < 0 || x-dy >= w || y+dx < 0 || y+dx >= h || | ||
3561 | dsf_canonify(dsf, (y+dx)*w+(x-dy)) != j) { | ||
3562 | /* Turn right. */ | ||
3563 | t = dx; | ||
3564 | dx = -dy; | ||
3565 | dy = t; | ||
3566 | } else if (x+dx-dy >= 0 && x+dx-dy < w && | ||
3567 | y+dy+dx >= 0 && y+dy+dx < h && | ||
3568 | dsf_canonify(dsf, (y+dy+dx)*w+(x+dx-dy)) == j) { | ||
3569 | /* Turn left. */ | ||
3570 | x += dx; | ||
3571 | y += dy; | ||
3572 | t = dx; | ||
3573 | dx = dy; | ||
3574 | dy = -t; | ||
3575 | x -= dx; | ||
3576 | y -= dy; | ||
3577 | } else { | ||
3578 | /* Straight on. */ | ||
3579 | x -= dy; | ||
3580 | y += dx; | ||
3581 | } | ||
3582 | } | ||
3583 | |||
3584 | /* | ||
3585 | * Now we have our polygon complete, so fill it. | ||
3586 | */ | ||
3587 | draw_polygon(dr, coords, ncoords/2, | ||
3588 | colours[j] == 2 ? blackish : -1, black); | ||
3589 | |||
3590 | /* | ||
3591 | * And mark this polyomino as done. | ||
3592 | */ | ||
3593 | colours[j] = 0; | ||
3594 | } | ||
3595 | } | ||
3596 | |||
3597 | /* | ||
3598 | * Draw the edges. | ||
3599 | */ | ||
3600 | for (y = 0; y <= h; y++) | ||
3601 | for (x = 0; x <= w; x++) { | ||
3602 | if (x < w && SPACE(state, x*2+1, y*2).flags & F_EDGE_SET) | ||
3603 | draw_rect(dr, COORD(x)-EDGE_THICKNESS, COORD(y)-EDGE_THICKNESS, | ||
3604 | EDGE_THICKNESS * 2 + TILE_SIZE, EDGE_THICKNESS * 2, | ||
3605 | black); | ||
3606 | if (y < h && SPACE(state, x*2, y*2+1).flags & F_EDGE_SET) | ||
3607 | draw_rect(dr, COORD(x)-EDGE_THICKNESS, COORD(y)-EDGE_THICKNESS, | ||
3608 | EDGE_THICKNESS * 2, EDGE_THICKNESS * 2 + TILE_SIZE, | ||
3609 | black); | ||
3610 | } | ||
3611 | |||
3612 | /* | ||
3613 | * Draw the dots. | ||
3614 | */ | ||
3615 | for (y = 0; y <= 2*h; y++) | ||
3616 | for (x = 0; x <= 2*w; x++) | ||
3617 | if (SPACE(state, x, y).flags & F_DOT) { | ||
3618 | draw_circle(dr, (int)COORD(x/2.0), (int)COORD(y/2.0), DOT_SIZE, | ||
3619 | (SPACE(state, x, y).flags & F_DOT_BLACK ? | ||
3620 | black : white), black); | ||
3621 | } | ||
3622 | |||
3623 | sfree(dsf); | ||
3624 | sfree(colours); | ||
3625 | sfree(coords); | ||
3626 | } | ||
3627 | #endif | ||
3628 | |||
3629 | #ifdef COMBINED | ||
3630 | #define thegame galaxies | ||
3631 | #endif | ||
3632 | |||
3633 | const struct game thegame = { | ||
3634 | "Galaxies", "games.galaxies", "galaxies", | ||
3635 | default_params, | ||
3636 | game_fetch_preset, NULL, | ||
3637 | decode_params, | ||
3638 | encode_params, | ||
3639 | free_params, | ||
3640 | dup_params, | ||
3641 | TRUE, game_configure, custom_params, | ||
3642 | validate_params, | ||
3643 | new_game_desc, | ||
3644 | validate_desc, | ||
3645 | new_game, | ||
3646 | dup_game, | ||
3647 | free_game, | ||
3648 | #ifdef EDITOR | ||
3649 | FALSE, NULL, | ||
3650 | #else | ||
3651 | TRUE, solve_game, | ||
3652 | #endif | ||
3653 | TRUE, game_can_format_as_text_now, game_text_format, | ||
3654 | new_ui, | ||
3655 | free_ui, | ||
3656 | encode_ui, | ||
3657 | decode_ui, | ||
3658 | game_changed_state, | ||
3659 | interpret_move, | ||
3660 | execute_move, | ||
3661 | PREFERRED_TILE_SIZE, game_compute_size, game_set_size, | ||
3662 | game_colours, | ||
3663 | game_new_drawstate, | ||
3664 | game_free_drawstate, | ||
3665 | game_redraw, | ||
3666 | game_anim_length, | ||
3667 | game_flash_length, | ||
3668 | game_status, | ||
3669 | #ifdef EDITOR | ||
3670 | FALSE, FALSE, NULL, NULL, | ||
3671 | TRUE, /* wants_statusbar */ | ||
3672 | #else | ||
3673 | TRUE, FALSE, game_print_size, game_print, | ||
3674 | FALSE, /* wants_statusbar */ | ||
3675 | #endif | ||
3676 | FALSE, game_timing_state, | ||
3677 | REQUIRE_RBUTTON, /* flags */ | ||
3678 | }; | ||
3679 | |||
3680 | #ifdef STANDALONE_SOLVER | ||
3681 | |||
3682 | const char *quis; | ||
3683 | |||
3684 | #include <time.h> | ||
3685 | |||
3686 | static void usage_exit(const char *msg) | ||
3687 | { | ||
3688 | if (msg) | ||
3689 | fprintf(stderr, "%s: %s\n", quis, msg); | ||
3690 | fprintf(stderr, "Usage: %s [--seed SEED] --soak <params> | [game_id [game_id ...]]\n", quis); | ||
3691 | exit(1); | ||
3692 | } | ||
3693 | |||
3694 | static void dump_state(game_state *state) | ||
3695 | { | ||
3696 | char *temp = game_text_format(state); | ||
3697 | printf("%s\n", temp); | ||
3698 | sfree(temp); | ||
3699 | } | ||
3700 | |||
3701 | static int gen(game_params *p, random_state *rs, int debug) | ||
3702 | { | ||
3703 | char *desc; | ||
3704 | int diff; | ||
3705 | game_state *state; | ||
3706 | |||
3707 | #ifndef DEBUGGING | ||
3708 | solver_show_working = debug; | ||
3709 | #endif | ||
3710 | printf("Generating a %dx%d %s puzzle.\n", | ||
3711 | p->w, p->h, galaxies_diffnames[p->diff]); | ||
3712 | |||
3713 | desc = new_game_desc(p, rs, NULL, 0); | ||
3714 | state = new_game(NULL, p, desc); | ||
3715 | dump_state(state); | ||
3716 | |||
3717 | diff = solver_state(state, DIFF_UNREASONABLE); | ||
3718 | printf("Generated %s game %dx%d:%s\n", | ||
3719 | galaxies_diffnames[diff], p->w, p->h, desc); | ||
3720 | dump_state(state); | ||
3721 | |||
3722 | free_game(state); | ||
3723 | sfree(desc); | ||
3724 | |||
3725 | return diff; | ||
3726 | } | ||
3727 | |||
3728 | static void soak(game_params *p, random_state *rs) | ||
3729 | { | ||
3730 | time_t tt_start, tt_now, tt_last; | ||
3731 | char *desc; | ||
3732 | game_state *st; | ||
3733 | int diff, n = 0, i, diffs[DIFF_MAX], ndots = 0, nspaces = 0; | ||
3734 | |||
3735 | #ifndef DEBUGGING | ||
3736 | solver_show_working = 0; | ||
3737 | #endif | ||
3738 | tt_start = tt_now = time(NULL); | ||
3739 | for (i = 0; i < DIFF_MAX; i++) diffs[i] = 0; | ||
3740 | maxtries = 1; | ||
3741 | |||
3742 | printf("Soak-generating a %dx%d grid, max. diff %s.\n", | ||
3743 | p->w, p->h, galaxies_diffnames[p->diff]); | ||
3744 | printf(" ["); | ||
3745 | for (i = 0; i < DIFF_MAX; i++) | ||
3746 | printf("%s%s", (i == 0) ? "" : ", ", galaxies_diffnames[i]); | ||
3747 | printf("]\n"); | ||
3748 | |||
3749 | while (1) { | ||
3750 | desc = new_game_desc(p, rs, NULL, 0); | ||
3751 | st = new_game(NULL, p, desc); | ||
3752 | diff = solver_state(st, p->diff); | ||
3753 | nspaces += st->w*st->h; | ||
3754 | for (i = 0; i < st->sx*st->sy; i++) | ||
3755 | if (st->grid[i].flags & F_DOT) ndots++; | ||
3756 | free_game(st); | ||
3757 | sfree(desc); | ||
3758 | |||
3759 | diffs[diff]++; | ||
3760 | n++; | ||
3761 | tt_last = time(NULL); | ||
3762 | if (tt_last > tt_now) { | ||
3763 | tt_now = tt_last; | ||
3764 | printf("%d total, %3.1f/s, [", | ||
3765 | n, (double)n / ((double)tt_now - tt_start)); | ||
3766 | for (i = 0; i < DIFF_MAX; i++) | ||
3767 | printf("%s%.1f%%", (i == 0) ? "" : ", ", | ||
3768 | 100.0 * ((double)diffs[i] / (double)n)); | ||
3769 | printf("], %.1f%% dots\n", | ||
3770 | 100.0 * ((double)ndots / (double)nspaces)); | ||
3771 | } | ||
3772 | } | ||
3773 | } | ||
3774 | |||
3775 | int main(int argc, char **argv) | ||
3776 | { | ||
3777 | game_params *p; | ||
3778 | char *id = NULL, *desc, *err; | ||
3779 | game_state *s; | ||
3780 | int diff, do_soak = 0, verbose = 0; | ||
3781 | random_state *rs; | ||
3782 | time_t seed = time(NULL); | ||
3783 | |||
3784 | quis = argv[0]; | ||
3785 | while (--argc > 0) { | ||
3786 | char *p = *++argv; | ||
3787 | if (!strcmp(p, "-v")) { | ||
3788 | verbose = 1; | ||
3789 | } else if (!strcmp(p, "--seed")) { | ||
3790 | if (argc == 0) usage_exit("--seed needs an argument"); | ||
3791 | seed = (time_t)atoi(*++argv); | ||
3792 | argc--; | ||
3793 | } else if (!strcmp(p, "--soak")) { | ||
3794 | do_soak = 1; | ||
3795 | } else if (*p == '-') { | ||
3796 | usage_exit("unrecognised option"); | ||
3797 | } else { | ||
3798 | id = p; | ||
3799 | } | ||
3800 | } | ||
3801 | |||
3802 | maxtries = 50; | ||
3803 | |||
3804 | p = default_params(); | ||
3805 | rs = random_new((void*)&seed, sizeof(time_t)); | ||
3806 | |||
3807 | if (do_soak) { | ||
3808 | if (!id) usage_exit("need one argument for --soak"); | ||
3809 | decode_params(p, *argv); | ||
3810 | soak(p, rs); | ||
3811 | return 0; | ||
3812 | } | ||
3813 | |||
3814 | if (!id) { | ||
3815 | while (1) { | ||
3816 | p->w = random_upto(rs, 15) + 3; | ||
3817 | p->h = random_upto(rs, 15) + 3; | ||
3818 | p->diff = random_upto(rs, DIFF_UNREASONABLE); | ||
3819 | diff = gen(p, rs, 0); | ||
3820 | } | ||
3821 | return 0; | ||
3822 | } | ||
3823 | |||
3824 | desc = strchr(id, ':'); | ||
3825 | if (!desc) { | ||
3826 | decode_params(p, id); | ||
3827 | gen(p, rs, verbose); | ||
3828 | } else { | ||
3829 | #ifndef DEBUGGING | ||
3830 | solver_show_working = 1; | ||
3831 | #endif | ||
3832 | *desc++ = '\0'; | ||
3833 | decode_params(p, id); | ||
3834 | err = validate_desc(p, desc); | ||
3835 | if (err) { | ||
3836 | fprintf(stderr, "%s: %s\n", argv[0], err); | ||
3837 | exit(1); | ||
3838 | } | ||
3839 | s = new_game(NULL, p, desc); | ||
3840 | diff = solver_state(s, DIFF_UNREASONABLE); | ||
3841 | dump_state(s); | ||
3842 | printf("Puzzle is %s.\n", galaxies_diffnames[diff]); | ||
3843 | free_game(s); | ||
3844 | } | ||
3845 | |||
3846 | free_params(p); | ||
3847 | |||
3848 | return 0; | ||
3849 | } | ||
3850 | |||
3851 | #endif | ||
3852 | |||
3853 | #ifdef STANDALONE_PICTURE_GENERATOR | ||
3854 | |||
3855 | /* | ||
3856 | * Main program for the standalone picture generator. To use it, | ||
3857 | * simply provide it with an XBM-format bitmap file (note XBM, not | ||
3858 | * XPM) on standard input, and it will output a game ID in return. | ||
3859 | * For example: | ||
3860 | * | ||
3861 | * $ ./galaxiespicture < badly-drawn-cat.xbm | ||
3862 | * 11x11:eloMBLzFeEzLNMWifhaWYdDbixCymBbBMLoDdewGg | ||
3863 | * | ||
3864 | * If you want a puzzle with a non-standard difficulty level, pass | ||
3865 | * a partial parameters string as a command-line argument (e.g. | ||
3866 | * `./galaxiespicture du < foo.xbm', where `du' is the same suffix | ||
3867 | * which if it appeared in a random-seed game ID would set the | ||
3868 | * difficulty level to Unreasonable). However, be aware that if the | ||
3869 | * generator fails to produce an adequately difficult puzzle too | ||
3870 | * many times then it will give up and return an easier one (just | ||
3871 | * as it does during normal GUI play). To be sure you really have | ||
3872 | * the difficulty you asked for, use galaxiessolver to | ||
3873 | * double-check. | ||
3874 | * | ||
3875 | * (Perhaps I ought to include an option to make this standalone | ||
3876 | * generator carry on looping until it really does get the right | ||
3877 | * difficulty. Hmmm.) | ||
3878 | */ | ||
3879 | |||
3880 | #include <time.h> | ||
3881 | |||
3882 | int main(int argc, char **argv) | ||
3883 | { | ||
3884 | game_params *par; | ||
3885 | char *params, *desc; | ||
3886 | random_state *rs; | ||
3887 | time_t seed = time(NULL); | ||
3888 | char buf[4096]; | ||
3889 | int i; | ||
3890 | int x, y; | ||
3891 | |||
3892 | par = default_params(); | ||
3893 | if (argc > 1) | ||
3894 | decode_params(par, argv[1]); /* get difficulty */ | ||
3895 | par->w = par->h = -1; | ||
3896 | |||
3897 | /* | ||
3898 | * Now read an XBM file from standard input. This is simple and | ||
3899 | * hacky and will do very little error detection, so don't feed | ||
3900 | * it bogus data. | ||
3901 | */ | ||
3902 | picture = NULL; | ||
3903 | x = y = 0; | ||
3904 | while (fgets(buf, sizeof(buf), stdin)) { | ||
3905 | buf[strcspn(buf, "\r\n")] = '\0'; | ||
3906 | if (!strncmp(buf, "#define", 7)) { | ||
3907 | /* | ||
3908 | * Lines starting `#define' give the width and height. | ||
3909 | */ | ||
3910 | char *num = buf + strlen(buf); | ||
3911 | char *symend; | ||
3912 | |||
3913 | while (num > buf && isdigit((unsigned char)num[-1])) | ||
3914 | num--; | ||
3915 | symend = num; | ||
3916 | while (symend > buf && isspace((unsigned char)symend[-1])) | ||
3917 | symend--; | ||
3918 | |||
3919 | if (symend-5 >= buf && !strncmp(symend-5, "width", 5)) | ||
3920 | par->w = atoi(num); | ||
3921 | else if (symend-6 >= buf && !strncmp(symend-6, "height", 6)) | ||
3922 | par->h = atoi(num); | ||
3923 | } else { | ||
3924 | /* | ||
3925 | * Otherwise, break the string up into words and take | ||
3926 | * any word of the form `0x' plus hex digits to be a | ||
3927 | * byte. | ||
3928 | */ | ||
3929 | char *p, *wordstart; | ||
3930 | |||
3931 | if (!picture) { | ||
3932 | if (par->w < 0 || par->h < 0) { | ||
3933 | printf("failed to read width and height\n"); | ||
3934 | return 1; | ||
3935 | } | ||
3936 | picture = snewn(par->w * par->h, int); | ||
3937 | for (i = 0; i < par->w * par->h; i++) | ||
3938 | picture[i] = -1; | ||
3939 | } | ||
3940 | |||
3941 | p = buf; | ||
3942 | while (*p) { | ||
3943 | while (*p && (*p == ',' || isspace((unsigned char)*p))) | ||
3944 | p++; | ||
3945 | wordstart = p; | ||
3946 | while (*p && !(*p == ',' || *p == '}' || | ||
3947 | isspace((unsigned char)*p))) | ||
3948 | p++; | ||
3949 | if (*p) | ||
3950 | *p++ = '\0'; | ||
3951 | |||
3952 | if (wordstart[0] == '0' && | ||
3953 | (wordstart[1] == 'x' || wordstart[1] == 'X') && | ||
3954 | !wordstart[2 + strspn(wordstart+2, | ||
3955 | "0123456789abcdefABCDEF")]) { | ||
3956 | unsigned long byte = strtoul(wordstart+2, NULL, 16); | ||
3957 | for (i = 0; i < 8; i++) { | ||
3958 | int bit = (byte >> i) & 1; | ||
3959 | if (y < par->h && x < par->w) | ||
3960 | picture[y * par->w + x] = bit; | ||
3961 | x++; | ||
3962 | } | ||
3963 | |||
3964 | if (x >= par->w) { | ||
3965 | x = 0; | ||
3966 | y++; | ||
3967 | } | ||
3968 | } | ||
3969 | } | ||
3970 | } | ||
3971 | } | ||
3972 | |||
3973 | for (i = 0; i < par->w * par->h; i++) | ||
3974 | if (picture[i] < 0) { | ||
3975 | fprintf(stderr, "failed to read enough bitmap data\n"); | ||
3976 | return 1; | ||
3977 | } | ||
3978 | |||
3979 | rs = random_new((void*)&seed, sizeof(time_t)); | ||
3980 | |||
3981 | desc = new_game_desc(par, rs, NULL, FALSE); | ||
3982 | params = encode_params(par, FALSE); | ||
3983 | printf("%s:%s\n", params, desc); | ||
3984 | |||
3985 | sfree(desc); | ||
3986 | sfree(params); | ||
3987 | free_params(par); | ||
3988 | random_free(rs); | ||
3989 | |||
3990 | return 0; | ||
3991 | } | ||
3992 | |||
3993 | #endif | ||
3994 | |||
3995 | /* vim: set shiftwidth=4 tabstop=8: */ | ||