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