diff options
author | Franklin Wei <git@fwei.tk> | 2017-04-29 18:21:56 -0400 |
---|---|---|
committer | Franklin Wei <git@fwei.tk> | 2017-04-29 18:24:42 -0400 |
commit | 881746789a489fad85aae8317555f73dbe261556 (patch) | |
tree | cec2946362c4698c8db3c10f3242ef546c2c22dd /apps/plugins/puzzles/src/signpost.c | |
parent | 03dd4b92be7dcd5c8ab06da3810887060e06abd5 (diff) | |
download | rockbox-881746789a489fad85aae8317555f73dbe261556.tar.gz rockbox-881746789a489fad85aae8317555f73dbe261556.zip |
puzzles: refactor and resync with upstream
This brings puzzles up-to-date with upstream revision
2d333750272c3967cfd5cd3677572cddeaad5932, though certain changes made
by me, including cursor-only Untangle and some compilation fixes
remain. Upstream code has been moved to its separate subdirectory and
future syncs can be done by simply copying over the new sources.
Change-Id: Ia6506ca5f78c3627165ea6791d38db414ace0804
Diffstat (limited to 'apps/plugins/puzzles/src/signpost.c')
-rw-r--r-- | apps/plugins/puzzles/src/signpost.c | 2480 |
1 files changed, 2480 insertions, 0 deletions
diff --git a/apps/plugins/puzzles/src/signpost.c b/apps/plugins/puzzles/src/signpost.c new file mode 100644 index 0000000000..ca72768c27 --- /dev/null +++ b/apps/plugins/puzzles/src/signpost.c | |||
@@ -0,0 +1,2480 @@ | |||
1 | /* | ||
2 | * signpost.c: implementation of the janko game 'arrow path' | ||
3 | */ | ||
4 | |||
5 | #include <stdio.h> | ||
6 | #include <stdlib.h> | ||
7 | #include <string.h> | ||
8 | #include <assert.h> | ||
9 | #include <ctype.h> | ||
10 | #include <math.h> | ||
11 | |||
12 | #include "puzzles.h" | ||
13 | |||
14 | #define PREFERRED_TILE_SIZE 48 | ||
15 | #define TILE_SIZE (ds->tilesize) | ||
16 | #define BLITTER_SIZE TILE_SIZE | ||
17 | #define BORDER (TILE_SIZE / 2) | ||
18 | |||
19 | #define COORD(x) ( (x) * TILE_SIZE + BORDER ) | ||
20 | #define FROMCOORD(x) ( ((x) - BORDER + TILE_SIZE) / TILE_SIZE - 1 ) | ||
21 | |||
22 | #define INGRID(s,x,y) ((x) >= 0 && (x) < (s)->w && (y) >= 0 && (y) < (s)->h) | ||
23 | |||
24 | #define FLASH_SPIN 0.7F | ||
25 | |||
26 | #define NBACKGROUNDS 16 | ||
27 | |||
28 | enum { | ||
29 | COL_BACKGROUND, COL_HIGHLIGHT, COL_LOWLIGHT, | ||
30 | COL_GRID, COL_CURSOR, COL_ERROR, COL_DRAG_ORIGIN, | ||
31 | COL_ARROW, COL_ARROW_BG_DIM, | ||
32 | COL_NUMBER, COL_NUMBER_SET, COL_NUMBER_SET_MID, | ||
33 | COL_B0, /* background colours */ | ||
34 | COL_M0 = COL_B0 + 1*NBACKGROUNDS, /* mid arrow colours */ | ||
35 | COL_D0 = COL_B0 + 2*NBACKGROUNDS, /* dim arrow colours */ | ||
36 | COL_X0 = COL_B0 + 3*NBACKGROUNDS, /* dim arrow colours */ | ||
37 | NCOLOURS = COL_B0 + 4*NBACKGROUNDS | ||
38 | }; | ||
39 | |||
40 | struct game_params { | ||
41 | int w, h; | ||
42 | int force_corner_start; | ||
43 | }; | ||
44 | |||
45 | enum { DIR_N = 0, DIR_NE, DIR_E, DIR_SE, DIR_S, DIR_SW, DIR_W, DIR_NW, DIR_MAX }; | ||
46 | static const char *dirstrings[8] = { "N ", "NE", "E ", "SE", "S ", "SW", "W ", "NW" }; | ||
47 | |||
48 | static const int dxs[DIR_MAX] = { 0, 1, 1, 1, 0, -1, -1, -1 }; | ||
49 | static const int dys[DIR_MAX] = { -1, -1, 0, 1, 1, 1, 0, -1 }; | ||
50 | |||
51 | #define DIR_OPPOSITE(d) ((d+4)%8) | ||
52 | |||
53 | struct game_state { | ||
54 | int w, h, n; | ||
55 | int completed, used_solve, impossible; | ||
56 | int *dirs; /* direction enums, size n */ | ||
57 | int *nums; /* numbers, size n */ | ||
58 | unsigned int *flags; /* flags, size n */ | ||
59 | int *next, *prev; /* links to other cell indexes, size n (-1 absent) */ | ||
60 | int *dsf; /* connects regions with a dsf. */ | ||
61 | int *numsi; /* for each number, which index is it in? (-1 absent) */ | ||
62 | }; | ||
63 | |||
64 | #define FLAG_IMMUTABLE 1 | ||
65 | #define FLAG_ERROR 2 | ||
66 | |||
67 | /* --- Generally useful functions --- */ | ||
68 | |||
69 | #define ISREALNUM(state, num) ((num) > 0 && (num) <= (state)->n) | ||
70 | |||
71 | static int whichdir(int fromx, int fromy, int tox, int toy) | ||
72 | { | ||
73 | int i, dx, dy; | ||
74 | |||
75 | dx = tox - fromx; | ||
76 | dy = toy - fromy; | ||
77 | |||
78 | if (dx && dy && abs(dx) != abs(dy)) return -1; | ||
79 | |||
80 | if (dx) dx = dx / abs(dx); /* limit to (-1, 0, 1) */ | ||
81 | if (dy) dy = dy / abs(dy); /* ditto */ | ||
82 | |||
83 | for (i = 0; i < DIR_MAX; i++) { | ||
84 | if (dx == dxs[i] && dy == dys[i]) return i; | ||
85 | } | ||
86 | return -1; | ||
87 | } | ||
88 | |||
89 | static int whichdiri(game_state *state, int fromi, int toi) | ||
90 | { | ||
91 | int w = state->w; | ||
92 | return whichdir(fromi%w, fromi/w, toi%w, toi/w); | ||
93 | } | ||
94 | |||
95 | static int ispointing(const game_state *state, int fromx, int fromy, | ||
96 | int tox, int toy) | ||
97 | { | ||
98 | int w = state->w, dir = state->dirs[fromy*w+fromx]; | ||
99 | |||
100 | /* (by convention) squares do not point to themselves. */ | ||
101 | if (fromx == tox && fromy == toy) return 0; | ||
102 | |||
103 | /* the final number points to nothing. */ | ||
104 | if (state->nums[fromy*w + fromx] == state->n) return 0; | ||
105 | |||
106 | while (1) { | ||
107 | if (!INGRID(state, fromx, fromy)) return 0; | ||
108 | if (fromx == tox && fromy == toy) return 1; | ||
109 | fromx += dxs[dir]; fromy += dys[dir]; | ||
110 | } | ||
111 | return 0; /* not reached */ | ||
112 | } | ||
113 | |||
114 | static int ispointingi(game_state *state, int fromi, int toi) | ||
115 | { | ||
116 | int w = state->w; | ||
117 | return ispointing(state, fromi%w, fromi/w, toi%w, toi/w); | ||
118 | } | ||
119 | |||
120 | /* Taking the number 'num', work out the gap between it and the next | ||
121 | * available number up or down (depending on d). Return 1 if the region | ||
122 | * at (x,y) will fit in that gap, or 0 otherwise. */ | ||
123 | static int move_couldfit(const game_state *state, int num, int d, int x, int y) | ||
124 | { | ||
125 | int n, gap, i = y*state->w+x, sz; | ||
126 | |||
127 | assert(d != 0); | ||
128 | /* The 'gap' is the number of missing numbers in the grid between | ||
129 | * our number and the next one in the sequence (up or down), or | ||
130 | * the end of the sequence (if we happen not to have 1/n present) */ | ||
131 | for (n = num + d, gap = 0; | ||
132 | ISREALNUM(state, n) && state->numsi[n] == -1; | ||
133 | n += d, gap++) ; /* empty loop */ | ||
134 | |||
135 | if (gap == 0) { | ||
136 | /* no gap, so the only allowable move is that that directly | ||
137 | * links the two numbers. */ | ||
138 | n = state->nums[i]; | ||
139 | return (n == num+d) ? 0 : 1; | ||
140 | } | ||
141 | if (state->prev[i] == -1 && state->next[i] == -1) | ||
142 | return 1; /* single unconnected square, always OK */ | ||
143 | |||
144 | sz = dsf_size(state->dsf, i); | ||
145 | return (sz > gap) ? 0 : 1; | ||
146 | } | ||
147 | |||
148 | static int isvalidmove(const game_state *state, int clever, | ||
149 | int fromx, int fromy, int tox, int toy) | ||
150 | { | ||
151 | int w = state->w, from = fromy*w+fromx, to = toy*w+tox; | ||
152 | int nfrom, nto; | ||
153 | |||
154 | if (!INGRID(state, fromx, fromy) || !INGRID(state, tox, toy)) | ||
155 | return 0; | ||
156 | |||
157 | /* can only move where we point */ | ||
158 | if (!ispointing(state, fromx, fromy, tox, toy)) | ||
159 | return 0; | ||
160 | |||
161 | nfrom = state->nums[from]; nto = state->nums[to]; | ||
162 | |||
163 | /* can't move _from_ the preset final number, or _to_ the preset 1. */ | ||
164 | if (((nfrom == state->n) && (state->flags[from] & FLAG_IMMUTABLE)) || | ||
165 | ((nto == 1) && (state->flags[to] & FLAG_IMMUTABLE))) | ||
166 | return 0; | ||
167 | |||
168 | /* can't create a new connection between cells in the same region | ||
169 | * as that would create a loop. */ | ||
170 | if (dsf_canonify(state->dsf, from) == dsf_canonify(state->dsf, to)) | ||
171 | return 0; | ||
172 | |||
173 | /* if both cells are actual numbers, can't drag if we're not | ||
174 | * one digit apart. */ | ||
175 | if (ISREALNUM(state, nfrom) && ISREALNUM(state, nto)) { | ||
176 | if (nfrom != nto-1) | ||
177 | return 0; | ||
178 | } else if (clever && ISREALNUM(state, nfrom)) { | ||
179 | if (!move_couldfit(state, nfrom, +1, tox, toy)) | ||
180 | return 0; | ||
181 | } else if (clever && ISREALNUM(state, nto)) { | ||
182 | if (!move_couldfit(state, nto, -1, fromx, fromy)) | ||
183 | return 0; | ||
184 | } | ||
185 | |||
186 | return 1; | ||
187 | } | ||
188 | |||
189 | static void makelink(game_state *state, int from, int to) | ||
190 | { | ||
191 | if (state->next[from] != -1) | ||
192 | state->prev[state->next[from]] = -1; | ||
193 | state->next[from] = to; | ||
194 | |||
195 | if (state->prev[to] != -1) | ||
196 | state->next[state->prev[to]] = -1; | ||
197 | state->prev[to] = from; | ||
198 | } | ||
199 | |||
200 | static int game_can_format_as_text_now(const game_params *params) | ||
201 | { | ||
202 | if (params->w * params->h >= 100) return 0; | ||
203 | return 1; | ||
204 | } | ||
205 | |||
206 | static char *game_text_format(const game_state *state) | ||
207 | { | ||
208 | int len = state->h * 2 * (4*state->w + 1) + state->h + 2; | ||
209 | int x, y, i, num, n, set; | ||
210 | char *ret, *p; | ||
211 | |||
212 | p = ret = snewn(len, char); | ||
213 | |||
214 | for (y = 0; y < state->h; y++) { | ||
215 | for (x = 0; x < state->h; x++) { | ||
216 | i = y*state->w+x; | ||
217 | *p++ = dirstrings[state->dirs[i]][0]; | ||
218 | *p++ = dirstrings[state->dirs[i]][1]; | ||
219 | *p++ = (state->flags[i] & FLAG_IMMUTABLE) ? 'I' : ' '; | ||
220 | *p++ = ' '; | ||
221 | } | ||
222 | *p++ = '\n'; | ||
223 | for (x = 0; x < state->h; x++) { | ||
224 | i = y*state->w+x; | ||
225 | num = state->nums[i]; | ||
226 | if (num == 0) { | ||
227 | *p++ = ' '; | ||
228 | *p++ = ' '; | ||
229 | *p++ = ' '; | ||
230 | } else { | ||
231 | n = num % (state->n+1); | ||
232 | set = num / (state->n+1); | ||
233 | |||
234 | assert(n <= 99); /* two digits only! */ | ||
235 | |||
236 | if (set != 0) | ||
237 | *p++ = set+'a'-1; | ||
238 | |||
239 | *p++ = (n >= 10) ? ('0' + (n/10)) : ' '; | ||
240 | *p++ = '0' + (n%10); | ||
241 | |||
242 | if (set == 0) | ||
243 | *p++ = ' '; | ||
244 | } | ||
245 | *p++ = ' '; | ||
246 | } | ||
247 | *p++ = '\n'; | ||
248 | *p++ = '\n'; | ||
249 | } | ||
250 | *p++ = '\0'; | ||
251 | |||
252 | return ret; | ||
253 | } | ||
254 | |||
255 | static void debug_state(const char *desc, game_state *state) | ||
256 | { | ||
257 | #ifdef DEBUGGING | ||
258 | char *dbg; | ||
259 | if (state->n >= 100) { | ||
260 | debug(("[ no game_text_format for this size ]")); | ||
261 | return; | ||
262 | } | ||
263 | dbg = game_text_format(state); | ||
264 | debug(("%s\n%s", desc, dbg)); | ||
265 | sfree(dbg); | ||
266 | #endif | ||
267 | } | ||
268 | |||
269 | |||
270 | static void strip_nums(game_state *state) { | ||
271 | int i; | ||
272 | for (i = 0; i < state->n; i++) { | ||
273 | if (!(state->flags[i] & FLAG_IMMUTABLE)) | ||
274 | state->nums[i] = 0; | ||
275 | } | ||
276 | memset(state->next, -1, state->n*sizeof(int)); | ||
277 | memset(state->prev, -1, state->n*sizeof(int)); | ||
278 | memset(state->numsi, -1, (state->n+1)*sizeof(int)); | ||
279 | dsf_init(state->dsf, state->n); | ||
280 | } | ||
281 | |||
282 | static int check_nums(game_state *orig, game_state *copy, int only_immutable) | ||
283 | { | ||
284 | int i, ret = 1; | ||
285 | assert(copy->n == orig->n); | ||
286 | for (i = 0; i < copy->n; i++) { | ||
287 | if (only_immutable && !(copy->flags[i] & FLAG_IMMUTABLE)) continue; | ||
288 | assert(copy->nums[i] >= 0); | ||
289 | assert(copy->nums[i] <= copy->n); | ||
290 | if (copy->nums[i] != orig->nums[i]) { | ||
291 | debug(("check_nums: (%d,%d) copy=%d, orig=%d.", | ||
292 | i%orig->w, i/orig->w, copy->nums[i], orig->nums[i])); | ||
293 | ret = 0; | ||
294 | } | ||
295 | } | ||
296 | return ret; | ||
297 | } | ||
298 | |||
299 | /* --- Game parameter/presets functions --- */ | ||
300 | |||
301 | static game_params *default_params(void) | ||
302 | { | ||
303 | game_params *ret = snew(game_params); | ||
304 | ret->w = ret->h = 4; | ||
305 | ret->force_corner_start = 1; | ||
306 | |||
307 | return ret; | ||
308 | } | ||
309 | |||
310 | static const struct game_params signpost_presets[] = { | ||
311 | { 4, 4, 1 }, | ||
312 | { 4, 4, 0 }, | ||
313 | { 5, 5, 1 }, | ||
314 | { 5, 5, 0 }, | ||
315 | { 6, 6, 1 }, | ||
316 | { 7, 7, 1 } | ||
317 | }; | ||
318 | |||
319 | static int game_fetch_preset(int i, char **name, game_params **params) | ||
320 | { | ||
321 | game_params *ret; | ||
322 | char buf[80]; | ||
323 | |||
324 | if (i < 0 || i >= lenof(signpost_presets)) | ||
325 | return FALSE; | ||
326 | |||
327 | ret = default_params(); | ||
328 | *ret = signpost_presets[i]; | ||
329 | *params = ret; | ||
330 | |||
331 | sprintf(buf, "%dx%d%s", ret->w, ret->h, | ||
332 | ret->force_corner_start ? "" : ", free ends"); | ||
333 | *name = dupstr(buf); | ||
334 | |||
335 | return TRUE; | ||
336 | } | ||
337 | |||
338 | static void free_params(game_params *params) | ||
339 | { | ||
340 | sfree(params); | ||
341 | } | ||
342 | |||
343 | static game_params *dup_params(const game_params *params) | ||
344 | { | ||
345 | game_params *ret = snew(game_params); | ||
346 | *ret = *params; /* structure copy */ | ||
347 | return ret; | ||
348 | } | ||
349 | |||
350 | static void decode_params(game_params *ret, char const *string) | ||
351 | { | ||
352 | ret->w = ret->h = atoi(string); | ||
353 | while (*string && isdigit((unsigned char)*string)) string++; | ||
354 | if (*string == 'x') { | ||
355 | string++; | ||
356 | ret->h = atoi(string); | ||
357 | while (*string && isdigit((unsigned char)*string)) string++; | ||
358 | } | ||
359 | ret->force_corner_start = 0; | ||
360 | if (*string == 'c') { | ||
361 | string++; | ||
362 | ret->force_corner_start = 1; | ||
363 | } | ||
364 | |||
365 | } | ||
366 | |||
367 | static char *encode_params(const game_params *params, int full) | ||
368 | { | ||
369 | char data[256]; | ||
370 | |||
371 | if (full) | ||
372 | sprintf(data, "%dx%d%s", params->w, params->h, | ||
373 | params->force_corner_start ? "c" : ""); | ||
374 | else | ||
375 | sprintf(data, "%dx%d", params->w, params->h); | ||
376 | |||
377 | return dupstr(data); | ||
378 | } | ||
379 | |||
380 | static config_item *game_configure(const game_params *params) | ||
381 | { | ||
382 | config_item *ret; | ||
383 | char buf[80]; | ||
384 | |||
385 | ret = snewn(4, config_item); | ||
386 | |||
387 | ret[0].name = "Width"; | ||
388 | ret[0].type = C_STRING; | ||
389 | sprintf(buf, "%d", params->w); | ||
390 | ret[0].sval = dupstr(buf); | ||
391 | ret[0].ival = 0; | ||
392 | |||
393 | ret[1].name = "Height"; | ||
394 | ret[1].type = C_STRING; | ||
395 | sprintf(buf, "%d", params->h); | ||
396 | ret[1].sval = dupstr(buf); | ||
397 | ret[1].ival = 0; | ||
398 | |||
399 | ret[2].name = "Start and end in corners"; | ||
400 | ret[2].type = C_BOOLEAN; | ||
401 | ret[2].sval = NULL; | ||
402 | ret[2].ival = params->force_corner_start; | ||
403 | |||
404 | ret[3].name = NULL; | ||
405 | ret[3].type = C_END; | ||
406 | ret[3].sval = NULL; | ||
407 | ret[3].ival = 0; | ||
408 | |||
409 | return ret; | ||
410 | } | ||
411 | |||
412 | static game_params *custom_params(const config_item *cfg) | ||
413 | { | ||
414 | game_params *ret = snew(game_params); | ||
415 | |||
416 | ret->w = atoi(cfg[0].sval); | ||
417 | ret->h = atoi(cfg[1].sval); | ||
418 | ret->force_corner_start = cfg[2].ival; | ||
419 | |||
420 | return ret; | ||
421 | } | ||
422 | |||
423 | static char *validate_params(const game_params *params, int full) | ||
424 | { | ||
425 | if (params->w < 1) return "Width must be at least one"; | ||
426 | if (params->h < 1) return "Height must be at least one"; | ||
427 | if (full && params->w == 1 && params->h == 1) | ||
428 | /* The UI doesn't let us move these from unsolved to solved, | ||
429 | * so we disallow generating (but not playing) them. */ | ||
430 | return "Width and height cannot both be one"; | ||
431 | return NULL; | ||
432 | } | ||
433 | |||
434 | /* --- Game description string generation and unpicking --- */ | ||
435 | |||
436 | static void blank_game_into(game_state *state) | ||
437 | { | ||
438 | memset(state->dirs, 0, state->n*sizeof(int)); | ||
439 | memset(state->nums, 0, state->n*sizeof(int)); | ||
440 | memset(state->flags, 0, state->n*sizeof(unsigned int)); | ||
441 | memset(state->next, -1, state->n*sizeof(int)); | ||
442 | memset(state->prev, -1, state->n*sizeof(int)); | ||
443 | memset(state->numsi, -1, (state->n+1)*sizeof(int)); | ||
444 | } | ||
445 | |||
446 | static game_state *blank_game(int w, int h) | ||
447 | { | ||
448 | game_state *state = snew(game_state); | ||
449 | |||
450 | memset(state, 0, sizeof(game_state)); | ||
451 | state->w = w; | ||
452 | state->h = h; | ||
453 | state->n = w*h; | ||
454 | |||
455 | state->dirs = snewn(state->n, int); | ||
456 | state->nums = snewn(state->n, int); | ||
457 | state->flags = snewn(state->n, unsigned int); | ||
458 | state->next = snewn(state->n, int); | ||
459 | state->prev = snewn(state->n, int); | ||
460 | state->dsf = snew_dsf(state->n); | ||
461 | state->numsi = snewn(state->n+1, int); | ||
462 | |||
463 | blank_game_into(state); | ||
464 | |||
465 | return state; | ||
466 | } | ||
467 | |||
468 | static void dup_game_to(game_state *to, const game_state *from) | ||
469 | { | ||
470 | to->completed = from->completed; | ||
471 | to->used_solve = from->used_solve; | ||
472 | to->impossible = from->impossible; | ||
473 | |||
474 | memcpy(to->dirs, from->dirs, to->n*sizeof(int)); | ||
475 | memcpy(to->flags, from->flags, to->n*sizeof(unsigned int)); | ||
476 | memcpy(to->nums, from->nums, to->n*sizeof(int)); | ||
477 | |||
478 | memcpy(to->next, from->next, to->n*sizeof(int)); | ||
479 | memcpy(to->prev, from->prev, to->n*sizeof(int)); | ||
480 | |||
481 | memcpy(to->dsf, from->dsf, to->n*sizeof(int)); | ||
482 | memcpy(to->numsi, from->numsi, (to->n+1)*sizeof(int)); | ||
483 | } | ||
484 | |||
485 | static game_state *dup_game(const game_state *state) | ||
486 | { | ||
487 | game_state *ret = blank_game(state->w, state->h); | ||
488 | dup_game_to(ret, state); | ||
489 | return ret; | ||
490 | } | ||
491 | |||
492 | static void free_game(game_state *state) | ||
493 | { | ||
494 | sfree(state->dirs); | ||
495 | sfree(state->nums); | ||
496 | sfree(state->flags); | ||
497 | sfree(state->next); | ||
498 | sfree(state->prev); | ||
499 | sfree(state->dsf); | ||
500 | sfree(state->numsi); | ||
501 | sfree(state); | ||
502 | } | ||
503 | |||
504 | static void unpick_desc(const game_params *params, const char *desc, | ||
505 | game_state **sout, char **mout) | ||
506 | { | ||
507 | game_state *state = blank_game(params->w, params->h); | ||
508 | char *msg = NULL, c; | ||
509 | int num = 0, i = 0; | ||
510 | |||
511 | while (*desc) { | ||
512 | if (i >= state->n) { | ||
513 | msg = "Game description longer than expected"; | ||
514 | goto done; | ||
515 | } | ||
516 | |||
517 | c = *desc; | ||
518 | if (isdigit((unsigned char)c)) { | ||
519 | num = (num*10) + (int)(c-'0'); | ||
520 | if (num > state->n) { | ||
521 | msg = "Number too large"; | ||
522 | goto done; | ||
523 | } | ||
524 | } else if ((c-'a') >= 0 && (c-'a') < DIR_MAX) { | ||
525 | state->nums[i] = num; | ||
526 | state->flags[i] = num ? FLAG_IMMUTABLE : 0; | ||
527 | num = 0; | ||
528 | |||
529 | state->dirs[i] = c - 'a'; | ||
530 | i++; | ||
531 | } else if (!*desc) { | ||
532 | msg = "Game description shorter than expected"; | ||
533 | goto done; | ||
534 | } else { | ||
535 | msg = "Game description contains unexpected characters"; | ||
536 | goto done; | ||
537 | } | ||
538 | desc++; | ||
539 | } | ||
540 | if (i < state->n) { | ||
541 | msg = "Game description shorter than expected"; | ||
542 | goto done; | ||
543 | } | ||
544 | |||
545 | done: | ||
546 | if (msg) { /* sth went wrong. */ | ||
547 | if (mout) *mout = msg; | ||
548 | free_game(state); | ||
549 | } else { | ||
550 | if (mout) *mout = NULL; | ||
551 | if (sout) *sout = state; | ||
552 | else free_game(state); | ||
553 | } | ||
554 | } | ||
555 | |||
556 | static char *generate_desc(game_state *state, int issolve) | ||
557 | { | ||
558 | char *ret, buf[80]; | ||
559 | int retlen, i, k; | ||
560 | |||
561 | ret = NULL; retlen = 0; | ||
562 | if (issolve) { | ||
563 | ret = sresize(ret, 2, char); | ||
564 | ret[0] = 'S'; ret[1] = '\0'; | ||
565 | retlen += 1; | ||
566 | } | ||
567 | for (i = 0; i < state->n; i++) { | ||
568 | if (state->nums[i]) | ||
569 | k = sprintf(buf, "%d%c", state->nums[i], (int)(state->dirs[i]+'a')); | ||
570 | else | ||
571 | k = sprintf(buf, "%c", (int)(state->dirs[i]+'a')); | ||
572 | ret = sresize(ret, retlen + k + 1, char); | ||
573 | strcpy(ret + retlen, buf); | ||
574 | retlen += k; | ||
575 | } | ||
576 | return ret; | ||
577 | } | ||
578 | |||
579 | /* --- Game generation --- */ | ||
580 | |||
581 | /* Fills in preallocated arrays ai (indices) and ad (directions) | ||
582 | * showing all non-numbered cells adjacent to index i, returns length */ | ||
583 | /* This function has been somewhat optimised... */ | ||
584 | static int cell_adj(game_state *state, int i, int *ai, int *ad) | ||
585 | { | ||
586 | int n = 0, a, x, y, sx, sy, dx, dy, newi; | ||
587 | int w = state->w, h = state->h; | ||
588 | |||
589 | sx = i % w; sy = i / w; | ||
590 | |||
591 | for (a = 0; a < DIR_MAX; a++) { | ||
592 | x = sx; y = sy; | ||
593 | dx = dxs[a]; dy = dys[a]; | ||
594 | while (1) { | ||
595 | x += dx; y += dy; | ||
596 | if (x < 0 || y < 0 || x >= w || y >= h) break; | ||
597 | |||
598 | newi = y*w + x; | ||
599 | if (state->nums[newi] == 0) { | ||
600 | ai[n] = newi; | ||
601 | ad[n] = a; | ||
602 | n++; | ||
603 | } | ||
604 | } | ||
605 | } | ||
606 | return n; | ||
607 | } | ||
608 | |||
609 | static int new_game_fill(game_state *state, random_state *rs, | ||
610 | int headi, int taili) | ||
611 | { | ||
612 | int nfilled, an, ret = 0, j; | ||
613 | int *aidx, *adir; | ||
614 | |||
615 | aidx = snewn(state->n, int); | ||
616 | adir = snewn(state->n, int); | ||
617 | |||
618 | debug(("new_game_fill: headi=%d, taili=%d.", headi, taili)); | ||
619 | |||
620 | memset(state->nums, 0, state->n*sizeof(int)); | ||
621 | |||
622 | state->nums[headi] = 1; | ||
623 | state->nums[taili] = state->n; | ||
624 | |||
625 | state->dirs[taili] = 0; | ||
626 | nfilled = 2; | ||
627 | assert(state->n > 1); | ||
628 | |||
629 | while (nfilled < state->n) { | ||
630 | /* Try and expand _from_ headi; keep going if there's only one | ||
631 | * place to go to. */ | ||
632 | an = cell_adj(state, headi, aidx, adir); | ||
633 | do { | ||
634 | if (an == 0) goto done; | ||
635 | j = random_upto(rs, an); | ||
636 | state->dirs[headi] = adir[j]; | ||
637 | state->nums[aidx[j]] = state->nums[headi] + 1; | ||
638 | nfilled++; | ||
639 | headi = aidx[j]; | ||
640 | an = cell_adj(state, headi, aidx, adir); | ||
641 | } while (an == 1); | ||
642 | |||
643 | if (nfilled == state->n) break; | ||
644 | |||
645 | /* Try and expand _to_ taili; keep going if there's only one | ||
646 | * place to go to. */ | ||
647 | an = cell_adj(state, taili, aidx, adir); | ||
648 | do { | ||
649 | if (an == 0) goto done; | ||
650 | j = random_upto(rs, an); | ||
651 | state->dirs[aidx[j]] = DIR_OPPOSITE(adir[j]); | ||
652 | state->nums[aidx[j]] = state->nums[taili] - 1; | ||
653 | nfilled++; | ||
654 | taili = aidx[j]; | ||
655 | an = cell_adj(state, taili, aidx, adir); | ||
656 | } while (an == 1); | ||
657 | } | ||
658 | /* If we get here we have headi and taili set but unconnected | ||
659 | * by direction: we need to set headi's direction so as to point | ||
660 | * at taili. */ | ||
661 | state->dirs[headi] = whichdiri(state, headi, taili); | ||
662 | |||
663 | /* it could happen that our last two weren't in line; if that's the | ||
664 | * case, we have to start again. */ | ||
665 | if (state->dirs[headi] != -1) ret = 1; | ||
666 | |||
667 | done: | ||
668 | sfree(aidx); | ||
669 | sfree(adir); | ||
670 | return ret; | ||
671 | } | ||
672 | |||
673 | /* Better generator: with the 'generate, sprinkle numbers, solve, | ||
674 | * repeat' algorithm we're _never_ generating anything greater than | ||
675 | * 6x6, and spending all of our time in new_game_fill (and very little | ||
676 | * in solve_state). | ||
677 | * | ||
678 | * So, new generator steps: | ||
679 | * generate the grid, at random (same as now). Numbers 1 and N get | ||
680 | immutable flag immediately. | ||
681 | * squirrel that away for the solved state. | ||
682 | * | ||
683 | * (solve:) Try and solve it. | ||
684 | * If we solved it, we're done: | ||
685 | * generate the description from current immutable numbers, | ||
686 | * free stuff that needs freeing, | ||
687 | * return description + solved state. | ||
688 | * If we didn't solve it: | ||
689 | * count #tiles in state we've made deductions about. | ||
690 | * while (1): | ||
691 | * randomise a scratch array. | ||
692 | * for each index in scratch (in turn): | ||
693 | * if the cell isn't empty, continue (through scratch array) | ||
694 | * set number + immutable in state. | ||
695 | * try and solve state. | ||
696 | * if we've solved it, we're done. | ||
697 | * otherwise, count #tiles. If it's more than we had before: | ||
698 | * good, break from this loop and re-randomise. | ||
699 | * otherwise (number didn't help): | ||
700 | * remove number and try next in scratch array. | ||
701 | * if we've got to the end of the scratch array, no luck: | ||
702 | free everything we need to, and go back to regenerate the grid. | ||
703 | */ | ||
704 | |||
705 | static int solve_state(game_state *state); | ||
706 | |||
707 | static void debug_desc(const char *what, game_state *state) | ||
708 | { | ||
709 | #if DEBUGGING | ||
710 | { | ||
711 | char *desc = generate_desc(state, 0); | ||
712 | debug(("%s game state: %dx%d:%s", what, state->w, state->h, desc)); | ||
713 | sfree(desc); | ||
714 | } | ||
715 | #endif | ||
716 | } | ||
717 | |||
718 | /* Expects a fully-numbered game_state on input, and makes sure | ||
719 | * FLAG_IMMUTABLE is only set on those numbers we need to solve | ||
720 | * (as for a real new-game); returns 1 if it managed | ||
721 | * this (such that it could solve it), or 0 if not. */ | ||
722 | static int new_game_strip(game_state *state, random_state *rs) | ||
723 | { | ||
724 | int *scratch, i, j, ret = 1; | ||
725 | game_state *copy = dup_game(state); | ||
726 | |||
727 | debug(("new_game_strip.")); | ||
728 | |||
729 | strip_nums(copy); | ||
730 | debug_desc("Stripped", copy); | ||
731 | |||
732 | if (solve_state(copy) > 0) { | ||
733 | debug(("new_game_strip: soluble immediately after strip.")); | ||
734 | free_game(copy); | ||
735 | return 1; | ||
736 | } | ||
737 | |||
738 | scratch = snewn(state->n, int); | ||
739 | for (i = 0; i < state->n; i++) scratch[i] = i; | ||
740 | shuffle(scratch, state->n, sizeof(int), rs); | ||
741 | |||
742 | /* This is scungy. It might just be quick enough. | ||
743 | * It goes through, adding set numbers in empty squares | ||
744 | * until either we run out of empty squares (in the one | ||
745 | * we're half-solving) or else we solve it properly. | ||
746 | * NB that we run the entire solver each time, which | ||
747 | * strips the grid beforehand; we will save time if we | ||
748 | * avoid that. */ | ||
749 | for (i = 0; i < state->n; i++) { | ||
750 | j = scratch[i]; | ||
751 | if (copy->nums[j] > 0 && copy->nums[j] <= state->n) | ||
752 | continue; /* already solved to a real number here. */ | ||
753 | assert(state->nums[j] <= state->n); | ||
754 | debug(("new_game_strip: testing add IMMUTABLE number %d at square (%d,%d).", | ||
755 | state->nums[j], j%state->w, j/state->w)); | ||
756 | copy->nums[j] = state->nums[j]; | ||
757 | copy->flags[j] |= FLAG_IMMUTABLE; | ||
758 | state->flags[j] |= FLAG_IMMUTABLE; | ||
759 | debug_state("Copy of state: ", copy); | ||
760 | strip_nums(copy); | ||
761 | if (solve_state(copy) > 0) goto solved; | ||
762 | assert(check_nums(state, copy, 1)); | ||
763 | } | ||
764 | ret = 0; | ||
765 | goto done; | ||
766 | |||
767 | solved: | ||
768 | debug(("new_game_strip: now solved.")); | ||
769 | /* Since we added basically at random, try now to remove numbers | ||
770 | * and see if we can still solve it; if we can (still), really | ||
771 | * remove the number. Make sure we don't remove the anchor numbers | ||
772 | * 1 and N. */ | ||
773 | for (i = 0; i < state->n; i++) { | ||
774 | j = scratch[i]; | ||
775 | if ((state->flags[j] & FLAG_IMMUTABLE) && | ||
776 | (state->nums[j] != 1 && state->nums[j] != state->n)) { | ||
777 | debug(("new_game_strip: testing remove IMMUTABLE number %d at square (%d,%d).", | ||
778 | state->nums[j], j%state->w, j/state->w)); | ||
779 | state->flags[j] &= ~FLAG_IMMUTABLE; | ||
780 | dup_game_to(copy, state); | ||
781 | strip_nums(copy); | ||
782 | if (solve_state(copy) > 0) { | ||
783 | assert(check_nums(state, copy, 0)); | ||
784 | debug(("new_game_strip: OK, removing number")); | ||
785 | } else { | ||
786 | assert(state->nums[j] <= state->n); | ||
787 | debug(("new_game_strip: cannot solve, putting IMMUTABLE back.")); | ||
788 | copy->nums[j] = state->nums[j]; | ||
789 | state->flags[j] |= FLAG_IMMUTABLE; | ||
790 | } | ||
791 | } | ||
792 | } | ||
793 | |||
794 | done: | ||
795 | debug(("new_game_strip: %ssuccessful.", ret ? "" : "not ")); | ||
796 | sfree(scratch); | ||
797 | free_game(copy); | ||
798 | return ret; | ||
799 | } | ||
800 | |||
801 | static char *new_game_desc(const game_params *params, random_state *rs, | ||
802 | char **aux, int interactive) | ||
803 | { | ||
804 | game_state *state = blank_game(params->w, params->h); | ||
805 | char *ret; | ||
806 | int headi, taili; | ||
807 | |||
808 | /* this shouldn't happen (validate_params), but let's play it safe */ | ||
809 | if (params->w == 1 && params->h == 1) return dupstr("1a"); | ||
810 | |||
811 | generate: | ||
812 | blank_game_into(state); | ||
813 | |||
814 | /* keep trying until we fill successfully. */ | ||
815 | do { | ||
816 | if (params->force_corner_start) { | ||
817 | headi = 0; | ||
818 | taili = state->n-1; | ||
819 | } else { | ||
820 | do { | ||
821 | headi = random_upto(rs, state->n); | ||
822 | taili = random_upto(rs, state->n); | ||
823 | } while (headi == taili); | ||
824 | } | ||
825 | } while (!new_game_fill(state, rs, headi, taili)); | ||
826 | |||
827 | debug_state("Filled game:", state); | ||
828 | |||
829 | assert(state->nums[headi] <= state->n); | ||
830 | assert(state->nums[taili] <= state->n); | ||
831 | |||
832 | state->flags[headi] |= FLAG_IMMUTABLE; | ||
833 | state->flags[taili] |= FLAG_IMMUTABLE; | ||
834 | |||
835 | /* This will have filled in directions and _all_ numbers. | ||
836 | * Store the game definition for this, as the solved-state. */ | ||
837 | if (!new_game_strip(state, rs)) { | ||
838 | goto generate; | ||
839 | } | ||
840 | strip_nums(state); | ||
841 | { | ||
842 | game_state *tosolve = dup_game(state); | ||
843 | assert(solve_state(tosolve) > 0); | ||
844 | free_game(tosolve); | ||
845 | } | ||
846 | ret = generate_desc(state, 0); | ||
847 | free_game(state); | ||
848 | return ret; | ||
849 | } | ||
850 | |||
851 | static char *validate_desc(const game_params *params, const char *desc) | ||
852 | { | ||
853 | char *ret = NULL; | ||
854 | |||
855 | unpick_desc(params, desc, NULL, &ret); | ||
856 | return ret; | ||
857 | } | ||
858 | |||
859 | /* --- Linked-list and numbers array --- */ | ||
860 | |||
861 | /* Assuming numbers are always up-to-date, there are only four possibilities | ||
862 | * for regions changing after a single valid move: | ||
863 | * | ||
864 | * 1) two differently-coloured regions being combined (the resulting colouring | ||
865 | * should be based on the larger of the two regions) | ||
866 | * 2) a numbered region having a single number added to the start (the | ||
867 | * region's colour will remain, and the numbers will shift by 1) | ||
868 | * 3) a numbered region having a single number added to the end (the | ||
869 | * region's colour and numbering remains as-is) | ||
870 | * 4) two unnumbered squares being joined (will pick the smallest unused set | ||
871 | * of colours to use for the new region). | ||
872 | * | ||
873 | * There should never be any complications with regions containing 3 colours | ||
874 | * being combined, since two of those colours should have been merged on a | ||
875 | * previous move. | ||
876 | * | ||
877 | * Most of the complications are in ensuring we don't accidentally set two | ||
878 | * regions with the same colour (e.g. if a region was split). If this happens | ||
879 | * we always try and give the largest original portion the original colour. | ||
880 | */ | ||
881 | |||
882 | #define COLOUR(a) ((a) / (state->n+1)) | ||
883 | #define START(c) ((c) * (state->n+1)) | ||
884 | |||
885 | struct head_meta { | ||
886 | int i; /* position */ | ||
887 | int sz; /* size of region */ | ||
888 | int start; /* region start number preferred, or 0 if !preference */ | ||
889 | int preference; /* 0 if we have no preference (and should just pick one) */ | ||
890 | const char *why; | ||
891 | }; | ||
892 | |||
893 | static void head_number(game_state *state, int i, struct head_meta *head) | ||
894 | { | ||
895 | int off = 0, ss, j = i, c, n, sz; | ||
896 | |||
897 | /* Insist we really were passed the head of a chain. */ | ||
898 | assert(state->prev[i] == -1 && state->next[i] != -1); | ||
899 | |||
900 | head->i = i; | ||
901 | head->sz = dsf_size(state->dsf, i); | ||
902 | head->why = NULL; | ||
903 | |||
904 | /* Search through this chain looking for real numbers, checking that | ||
905 | * they match up (if there are more than one). */ | ||
906 | head->preference = 0; | ||
907 | while (j != -1) { | ||
908 | if (state->flags[j] & FLAG_IMMUTABLE) { | ||
909 | ss = state->nums[j] - off; | ||
910 | if (!head->preference) { | ||
911 | head->start = ss; | ||
912 | head->preference = 1; | ||
913 | head->why = "contains cell with immutable number"; | ||
914 | } else if (head->start != ss) { | ||
915 | debug(("head_number: chain with non-sequential numbers!")); | ||
916 | state->impossible = 1; | ||
917 | } | ||
918 | } | ||
919 | off++; | ||
920 | j = state->next[j]; | ||
921 | assert(j != i); /* we have created a loop, obviously wrong */ | ||
922 | } | ||
923 | if (head->preference) goto done; | ||
924 | |||
925 | if (state->nums[i] == 0 && state->nums[state->next[i]] > state->n) { | ||
926 | /* (probably) empty cell onto the head of a coloured region: | ||
927 | * make sure we start at a 0 offset. */ | ||
928 | head->start = START(COLOUR(state->nums[state->next[i]])); | ||
929 | head->preference = 1; | ||
930 | head->why = "adding blank cell to head of numbered region"; | ||
931 | } else if (state->nums[i] <= state->n) { | ||
932 | /* if we're 0 we're probably just blank -- but even if we're a | ||
933 | * (real) numbered region, we don't have an immutable number | ||
934 | * in it (any more) otherwise it'd have been caught above, so | ||
935 | * reassign the colour. */ | ||
936 | head->start = 0; | ||
937 | head->preference = 0; | ||
938 | head->why = "lowest available colour group"; | ||
939 | } else { | ||
940 | c = COLOUR(state->nums[i]); | ||
941 | n = 1; | ||
942 | sz = dsf_size(state->dsf, i); | ||
943 | j = i; | ||
944 | while (state->next[j] != -1) { | ||
945 | j = state->next[j]; | ||
946 | if (state->nums[j] == 0 && state->next[j] == -1) { | ||
947 | head->start = START(c); | ||
948 | head->preference = 1; | ||
949 | head->why = "adding blank cell to end of numbered region"; | ||
950 | goto done; | ||
951 | } | ||
952 | if (COLOUR(state->nums[j]) == c) | ||
953 | n++; | ||
954 | else { | ||
955 | int start_alternate = START(COLOUR(state->nums[j])); | ||
956 | if (n < (sz - n)) { | ||
957 | head->start = start_alternate; | ||
958 | head->preference = 1; | ||
959 | head->why = "joining two coloured regions, swapping to larger colour"; | ||
960 | } else { | ||
961 | head->start = START(c); | ||
962 | head->preference = 1; | ||
963 | head->why = "joining two coloured regions, taking largest"; | ||
964 | } | ||
965 | goto done; | ||
966 | } | ||
967 | } | ||
968 | /* If we got here then we may have split a region into | ||
969 | * two; make sure we don't assign a colour we've already used. */ | ||
970 | if (c == 0) { | ||
971 | /* not convinced this shouldn't be an assertion failure here. */ | ||
972 | head->start = 0; | ||
973 | head->preference = 0; | ||
974 | } else { | ||
975 | head->start = START(c); | ||
976 | head->preference = 1; | ||
977 | } | ||
978 | head->why = "got to end of coloured region"; | ||
979 | } | ||
980 | |||
981 | done: | ||
982 | assert(head->why != NULL); | ||
983 | if (head->preference) | ||
984 | debug(("Chain at (%d,%d) numbered for preference at %d (colour %d): %s.", | ||
985 | head->i%state->w, head->i/state->w, | ||
986 | head->start, COLOUR(head->start), head->why)); | ||
987 | else | ||
988 | debug(("Chain at (%d,%d) using next available colour: %s.", | ||
989 | head->i%state->w, head->i/state->w, | ||
990 | head->why)); | ||
991 | } | ||
992 | |||
993 | #if 0 | ||
994 | static void debug_numbers(game_state *state) | ||
995 | { | ||
996 | int i, w=state->w; | ||
997 | |||
998 | for (i = 0; i < state->n; i++) { | ||
999 | debug(("(%d,%d) --> (%d,%d) --> (%d,%d)", | ||
1000 | state->prev[i]==-1 ? -1 : state->prev[i]%w, | ||
1001 | state->prev[i]==-1 ? -1 : state->prev[i]/w, | ||
1002 | i%w, i/w, | ||
1003 | state->next[i]==-1 ? -1 : state->next[i]%w, | ||
1004 | state->next[i]==-1 ? -1 : state->next[i]/w)); | ||
1005 | } | ||
1006 | w = w+1; | ||
1007 | } | ||
1008 | #endif | ||
1009 | |||
1010 | static void connect_numbers(game_state *state) | ||
1011 | { | ||
1012 | int i, di, dni; | ||
1013 | |||
1014 | dsf_init(state->dsf, state->n); | ||
1015 | for (i = 0; i < state->n; i++) { | ||
1016 | if (state->next[i] != -1) { | ||
1017 | assert(state->prev[state->next[i]] == i); | ||
1018 | di = dsf_canonify(state->dsf, i); | ||
1019 | dni = dsf_canonify(state->dsf, state->next[i]); | ||
1020 | if (di == dni) { | ||
1021 | debug(("connect_numbers: chain forms a loop.")); | ||
1022 | state->impossible = 1; | ||
1023 | } | ||
1024 | dsf_merge(state->dsf, di, dni); | ||
1025 | } | ||
1026 | } | ||
1027 | } | ||
1028 | |||
1029 | static int compare_heads(const void *a, const void *b) | ||
1030 | { | ||
1031 | struct head_meta *ha = (struct head_meta *)a; | ||
1032 | struct head_meta *hb = (struct head_meta *)b; | ||
1033 | |||
1034 | /* Heads with preferred colours first... */ | ||
1035 | if (ha->preference && !hb->preference) return -1; | ||
1036 | if (hb->preference && !ha->preference) return 1; | ||
1037 | |||
1038 | /* ...then heads with low colours first... */ | ||
1039 | if (ha->start < hb->start) return -1; | ||
1040 | if (ha->start > hb->start) return 1; | ||
1041 | |||
1042 | /* ... then large regions first... */ | ||
1043 | if (ha->sz > hb->sz) return -1; | ||
1044 | if (ha->sz < hb->sz) return 1; | ||
1045 | |||
1046 | /* ... then position. */ | ||
1047 | if (ha->i > hb->i) return -1; | ||
1048 | if (ha->i < hb->i) return 1; | ||
1049 | |||
1050 | return 0; | ||
1051 | } | ||
1052 | |||
1053 | static int lowest_start(game_state *state, struct head_meta *heads, int nheads) | ||
1054 | { | ||
1055 | int n, c; | ||
1056 | |||
1057 | /* NB start at 1: colour 0 is real numbers */ | ||
1058 | for (c = 1; c < state->n; c++) { | ||
1059 | for (n = 0; n < nheads; n++) { | ||
1060 | if (COLOUR(heads[n].start) == c) | ||
1061 | goto used; | ||
1062 | } | ||
1063 | return c; | ||
1064 | used: | ||
1065 | ; | ||
1066 | } | ||
1067 | assert(!"No available colours!"); | ||
1068 | return 0; | ||
1069 | } | ||
1070 | |||
1071 | static void update_numbers(game_state *state) | ||
1072 | { | ||
1073 | int i, j, n, nnum, nheads; | ||
1074 | struct head_meta *heads = snewn(state->n, struct head_meta); | ||
1075 | |||
1076 | for (n = 0; n < state->n; n++) | ||
1077 | state->numsi[n] = -1; | ||
1078 | |||
1079 | for (i = 0; i < state->n; i++) { | ||
1080 | if (state->flags[i] & FLAG_IMMUTABLE) { | ||
1081 | assert(state->nums[i] > 0); | ||
1082 | assert(state->nums[i] <= state->n); | ||
1083 | state->numsi[state->nums[i]] = i; | ||
1084 | } | ||
1085 | else if (state->prev[i] == -1 && state->next[i] == -1) | ||
1086 | state->nums[i] = 0; | ||
1087 | } | ||
1088 | connect_numbers(state); | ||
1089 | |||
1090 | /* Construct an array of the heads of all current regions, together | ||
1091 | * with their preferred colours. */ | ||
1092 | nheads = 0; | ||
1093 | for (i = 0; i < state->n; i++) { | ||
1094 | /* Look for a cell that is the start of a chain | ||
1095 | * (has a next but no prev). */ | ||
1096 | if (state->prev[i] != -1 || state->next[i] == -1) continue; | ||
1097 | |||
1098 | head_number(state, i, &heads[nheads++]); | ||
1099 | } | ||
1100 | |||
1101 | /* Sort that array: | ||
1102 | * - heads with preferred colours first, then | ||
1103 | * - heads with low colours first, then | ||
1104 | * - large regions first | ||
1105 | */ | ||
1106 | qsort(heads, nheads, sizeof(struct head_meta), compare_heads); | ||
1107 | |||
1108 | /* Remove duplicate-coloured regions. */ | ||
1109 | for (n = nheads-1; n >= 0; n--) { /* order is important! */ | ||
1110 | if ((n != 0) && (heads[n].start == heads[n-1].start)) { | ||
1111 | /* We have a duplicate-coloured region: since we're | ||
1112 | * sorted in size order and this is not the first | ||
1113 | * of its colour it's not the largest: recolour it. */ | ||
1114 | heads[n].start = START(lowest_start(state, heads, nheads)); | ||
1115 | heads[n].preference = -1; /* '-1' means 'was duplicate' */ | ||
1116 | } | ||
1117 | else if (!heads[n].preference) { | ||
1118 | assert(heads[n].start == 0); | ||
1119 | heads[n].start = START(lowest_start(state, heads, nheads)); | ||
1120 | } | ||
1121 | } | ||
1122 | |||
1123 | debug(("Region colouring after duplicate removal:")); | ||
1124 | |||
1125 | for (n = 0; n < nheads; n++) { | ||
1126 | debug((" Chain at (%d,%d) sz %d numbered at %d (colour %d): %s%s", | ||
1127 | heads[n].i % state->w, heads[n].i / state->w, heads[n].sz, | ||
1128 | heads[n].start, COLOUR(heads[n].start), heads[n].why, | ||
1129 | heads[n].preference == 0 ? " (next available)" : | ||
1130 | heads[n].preference < 0 ? " (duplicate, next available)" : "")); | ||
1131 | |||
1132 | nnum = heads[n].start; | ||
1133 | j = heads[n].i; | ||
1134 | while (j != -1) { | ||
1135 | if (!(state->flags[j] & FLAG_IMMUTABLE)) { | ||
1136 | if (nnum > 0 && nnum <= state->n) | ||
1137 | state->numsi[nnum] = j; | ||
1138 | state->nums[j] = nnum; | ||
1139 | } | ||
1140 | nnum++; | ||
1141 | j = state->next[j]; | ||
1142 | assert(j != heads[n].i); /* loop?! */ | ||
1143 | } | ||
1144 | } | ||
1145 | /*debug_numbers(state);*/ | ||
1146 | sfree(heads); | ||
1147 | } | ||
1148 | |||
1149 | static int check_completion(game_state *state, int mark_errors) | ||
1150 | { | ||
1151 | int n, j, k, error = 0, complete; | ||
1152 | |||
1153 | /* NB This only marks errors that are possible to perpetrate with | ||
1154 | * the current UI in interpret_move. Things like forming loops in | ||
1155 | * linked sections and having numbers not add up should be forbidden | ||
1156 | * by the code elsewhere, so we don't bother marking those (because | ||
1157 | * it would add lots of tricky drawing code for very little gain). */ | ||
1158 | if (mark_errors) { | ||
1159 | for (j = 0; j < state->n; j++) | ||
1160 | state->flags[j] &= ~FLAG_ERROR; | ||
1161 | } | ||
1162 | |||
1163 | /* Search for repeated numbers. */ | ||
1164 | for (j = 0; j < state->n; j++) { | ||
1165 | if (state->nums[j] > 0 && state->nums[j] <= state->n) { | ||
1166 | for (k = j+1; k < state->n; k++) { | ||
1167 | if (state->nums[k] == state->nums[j]) { | ||
1168 | if (mark_errors) { | ||
1169 | state->flags[j] |= FLAG_ERROR; | ||
1170 | state->flags[k] |= FLAG_ERROR; | ||
1171 | } | ||
1172 | error = 1; | ||
1173 | } | ||
1174 | } | ||
1175 | } | ||
1176 | } | ||
1177 | |||
1178 | /* Search and mark numbers n not pointing to n+1; if any numbers | ||
1179 | * are missing we know we've not completed. */ | ||
1180 | complete = 1; | ||
1181 | for (n = 1; n < state->n; n++) { | ||
1182 | if (state->numsi[n] == -1 || state->numsi[n+1] == -1) | ||
1183 | complete = 0; | ||
1184 | else if (!ispointingi(state, state->numsi[n], state->numsi[n+1])) { | ||
1185 | if (mark_errors) { | ||
1186 | state->flags[state->numsi[n]] |= FLAG_ERROR; | ||
1187 | state->flags[state->numsi[n+1]] |= FLAG_ERROR; | ||
1188 | } | ||
1189 | error = 1; | ||
1190 | } else { | ||
1191 | /* make sure the link is explicitly made here; for instance, this | ||
1192 | * is nice if the user drags from 2 out (making 3) and a 4 is also | ||
1193 | * visible; this ensures that the link from 3 to 4 is also made. */ | ||
1194 | if (mark_errors) | ||
1195 | makelink(state, state->numsi[n], state->numsi[n+1]); | ||
1196 | } | ||
1197 | } | ||
1198 | |||
1199 | /* Search and mark numbers less than 0, or 0 with links. */ | ||
1200 | for (n = 1; n < state->n; n++) { | ||
1201 | if ((state->nums[n] < 0) || | ||
1202 | (state->nums[n] == 0 && | ||
1203 | (state->next[n] != -1 || state->prev[n] != -1))) { | ||
1204 | error = 1; | ||
1205 | if (mark_errors) | ||
1206 | state->flags[n] |= FLAG_ERROR; | ||
1207 | } | ||
1208 | } | ||
1209 | |||
1210 | if (error) return 0; | ||
1211 | return complete; | ||
1212 | } | ||
1213 | static game_state *new_game(midend *me, const game_params *params, | ||
1214 | const char *desc) | ||
1215 | { | ||
1216 | game_state *state = NULL; | ||
1217 | |||
1218 | unpick_desc(params, desc, &state, NULL); | ||
1219 | if (!state) assert(!"new_game failed to unpick"); | ||
1220 | |||
1221 | update_numbers(state); | ||
1222 | check_completion(state, 1); /* update any auto-links */ | ||
1223 | |||
1224 | return state; | ||
1225 | } | ||
1226 | |||
1227 | /* --- Solver --- */ | ||
1228 | |||
1229 | /* If a tile has a single tile it can link _to_, or there's only a single | ||
1230 | * location that can link to a given tile, fill that link in. */ | ||
1231 | static int solve_single(game_state *state, game_state *copy, int *from) | ||
1232 | { | ||
1233 | int i, j, sx, sy, x, y, d, poss, w=state->w, nlinks = 0; | ||
1234 | |||
1235 | /* The from array is a list of 'which square can link _to_ us'; | ||
1236 | * we start off with from as '-1' (meaning 'not found'); if we find | ||
1237 | * something that can link to us it is set to that index, and then if | ||
1238 | * we find another we set it to -2. */ | ||
1239 | |||
1240 | memset(from, -1, state->n*sizeof(int)); | ||
1241 | |||
1242 | /* poss is 'can I link to anything' with the same meanings. */ | ||
1243 | |||
1244 | for (i = 0; i < state->n; i++) { | ||
1245 | if (state->next[i] != -1) continue; | ||
1246 | if (state->nums[i] == state->n) continue; /* no next from last no. */ | ||
1247 | |||
1248 | d = state->dirs[i]; | ||
1249 | poss = -1; | ||
1250 | sx = x = i%w; sy = y = i/w; | ||
1251 | while (1) { | ||
1252 | x += dxs[d]; y += dys[d]; | ||
1253 | if (!INGRID(state, x, y)) break; | ||
1254 | if (!isvalidmove(state, 1, sx, sy, x, y)) continue; | ||
1255 | |||
1256 | /* can't link to somewhere with a back-link we would have to | ||
1257 | * break (the solver just doesn't work like this). */ | ||
1258 | j = y*w+x; | ||
1259 | if (state->prev[j] != -1) continue; | ||
1260 | |||
1261 | if (state->nums[i] > 0 && state->nums[j] > 0 && | ||
1262 | state->nums[i] <= state->n && state->nums[j] <= state->n && | ||
1263 | state->nums[j] == state->nums[i]+1) { | ||
1264 | debug(("Solver: forcing link through existing consecutive numbers.")); | ||
1265 | poss = j; | ||
1266 | from[j] = i; | ||
1267 | break; | ||
1268 | } | ||
1269 | |||
1270 | /* if there's been a valid move already, we have to move on; | ||
1271 | * we can't make any deductions here. */ | ||
1272 | poss = (poss == -1) ? j : -2; | ||
1273 | |||
1274 | /* Modify the from array as described above (which is enumerating | ||
1275 | * what points to 'j' in a similar way). */ | ||
1276 | from[j] = (from[j] == -1) ? i : -2; | ||
1277 | } | ||
1278 | if (poss == -2) { | ||
1279 | /*debug(("Solver: (%d,%d) has multiple possible next squares.", sx, sy));*/ | ||
1280 | ; | ||
1281 | } else if (poss == -1) { | ||
1282 | debug(("Solver: nowhere possible for (%d,%d) to link to.", sx, sy)); | ||
1283 | copy->impossible = 1; | ||
1284 | return -1; | ||
1285 | } else { | ||
1286 | debug(("Solver: linking (%d,%d) to only possible next (%d,%d).", | ||
1287 | sx, sy, poss%w, poss/w)); | ||
1288 | makelink(copy, i, poss); | ||
1289 | nlinks++; | ||
1290 | } | ||
1291 | } | ||
1292 | |||
1293 | for (i = 0; i < state->n; i++) { | ||
1294 | if (state->prev[i] != -1) continue; | ||
1295 | if (state->nums[i] == 1) continue; /* no prev from 1st no. */ | ||
1296 | |||
1297 | x = i%w; y = i/w; | ||
1298 | if (from[i] == -1) { | ||
1299 | debug(("Solver: nowhere possible to link to (%d,%d)", x, y)); | ||
1300 | copy->impossible = 1; | ||
1301 | return -1; | ||
1302 | } else if (from[i] == -2) { | ||
1303 | /*debug(("Solver: (%d,%d) has multiple possible prev squares.", x, y));*/ | ||
1304 | ; | ||
1305 | } else { | ||
1306 | debug(("Solver: linking only possible prev (%d,%d) to (%d,%d).", | ||
1307 | from[i]%w, from[i]/w, x, y)); | ||
1308 | makelink(copy, from[i], i); | ||
1309 | nlinks++; | ||
1310 | } | ||
1311 | } | ||
1312 | |||
1313 | return nlinks; | ||
1314 | } | ||
1315 | |||
1316 | /* Returns 1 if we managed to solve it, 0 otherwise. */ | ||
1317 | static int solve_state(game_state *state) | ||
1318 | { | ||
1319 | game_state *copy = dup_game(state); | ||
1320 | int *scratch = snewn(state->n, int), ret; | ||
1321 | |||
1322 | debug_state("Before solver: ", state); | ||
1323 | |||
1324 | while (1) { | ||
1325 | update_numbers(state); | ||
1326 | |||
1327 | if (solve_single(state, copy, scratch)) { | ||
1328 | dup_game_to(state, copy); | ||
1329 | if (state->impossible) break; else continue; | ||
1330 | } | ||
1331 | break; | ||
1332 | } | ||
1333 | free_game(copy); | ||
1334 | sfree(scratch); | ||
1335 | |||
1336 | update_numbers(state); | ||
1337 | ret = state->impossible ? -1 : check_completion(state, 0); | ||
1338 | debug(("Solver finished: %s", | ||
1339 | ret < 0 ? "impossible" : ret > 0 ? "solved" : "not solved")); | ||
1340 | debug_state("After solver: ", state); | ||
1341 | return ret; | ||
1342 | } | ||
1343 | |||
1344 | static char *solve_game(const game_state *state, const game_state *currstate, | ||
1345 | const char *aux, char **error) | ||
1346 | { | ||
1347 | game_state *tosolve; | ||
1348 | char *ret = NULL; | ||
1349 | int result; | ||
1350 | |||
1351 | tosolve = dup_game(currstate); | ||
1352 | result = solve_state(tosolve); | ||
1353 | if (result > 0) | ||
1354 | ret = generate_desc(tosolve, 1); | ||
1355 | free_game(tosolve); | ||
1356 | if (ret) return ret; | ||
1357 | |||
1358 | tosolve = dup_game(state); | ||
1359 | result = solve_state(tosolve); | ||
1360 | if (result < 0) | ||
1361 | *error = "Puzzle is impossible."; | ||
1362 | else if (result == 0) | ||
1363 | *error = "Unable to solve puzzle."; | ||
1364 | else | ||
1365 | ret = generate_desc(tosolve, 1); | ||
1366 | |||
1367 | free_game(tosolve); | ||
1368 | |||
1369 | return ret; | ||
1370 | } | ||
1371 | |||
1372 | /* --- UI and move routines. --- */ | ||
1373 | |||
1374 | |||
1375 | struct game_ui { | ||
1376 | int cx, cy, cshow; | ||
1377 | |||
1378 | int dragging, drag_is_from; | ||
1379 | int sx, sy; /* grid coords of start cell */ | ||
1380 | int dx, dy; /* pixel coords of drag posn */ | ||
1381 | }; | ||
1382 | |||
1383 | static game_ui *new_ui(const game_state *state) | ||
1384 | { | ||
1385 | game_ui *ui = snew(game_ui); | ||
1386 | |||
1387 | /* NB: if this is ever changed to as to require more than a structure | ||
1388 | * copy to clone, there's code that needs fixing in game_redraw too. */ | ||
1389 | |||
1390 | ui->cx = ui->cy = ui->cshow = 0; | ||
1391 | |||
1392 | ui->dragging = 0; | ||
1393 | ui->sx = ui->sy = ui->dx = ui->dy = 0; | ||
1394 | |||
1395 | return ui; | ||
1396 | } | ||
1397 | |||
1398 | static void free_ui(game_ui *ui) | ||
1399 | { | ||
1400 | sfree(ui); | ||
1401 | } | ||
1402 | |||
1403 | static char *encode_ui(const game_ui *ui) | ||
1404 | { | ||
1405 | return NULL; | ||
1406 | } | ||
1407 | |||
1408 | static void decode_ui(game_ui *ui, const char *encoding) | ||
1409 | { | ||
1410 | } | ||
1411 | |||
1412 | static void game_changed_state(game_ui *ui, const game_state *oldstate, | ||
1413 | const game_state *newstate) | ||
1414 | { | ||
1415 | if (!oldstate->completed && newstate->completed) | ||
1416 | ui->cshow = ui->dragging = 0; | ||
1417 | } | ||
1418 | |||
1419 | struct game_drawstate { | ||
1420 | int tilesize, started, solved; | ||
1421 | int w, h, n; | ||
1422 | int *nums, *dirp; | ||
1423 | unsigned int *f; | ||
1424 | double angle_offset; | ||
1425 | |||
1426 | int dragging, dx, dy; | ||
1427 | blitter *dragb; | ||
1428 | }; | ||
1429 | |||
1430 | static char *interpret_move(const game_state *state, game_ui *ui, | ||
1431 | const game_drawstate *ds, | ||
1432 | int mx, int my, int button) | ||
1433 | { | ||
1434 | int x = FROMCOORD(mx), y = FROMCOORD(my), w = state->w; | ||
1435 | char buf[80]; | ||
1436 | |||
1437 | if (IS_CURSOR_MOVE(button)) { | ||
1438 | move_cursor(button, &ui->cx, &ui->cy, state->w, state->h, 0); | ||
1439 | ui->cshow = 1; | ||
1440 | if (ui->dragging) { | ||
1441 | ui->dx = COORD(ui->cx) + TILE_SIZE/2; | ||
1442 | ui->dy = COORD(ui->cy) + TILE_SIZE/2; | ||
1443 | } | ||
1444 | return ""; | ||
1445 | } else if (IS_CURSOR_SELECT(button)) { | ||
1446 | if (!ui->cshow) | ||
1447 | ui->cshow = 1; | ||
1448 | else if (ui->dragging) { | ||
1449 | ui->dragging = FALSE; | ||
1450 | if (ui->sx == ui->cx && ui->sy == ui->cy) return ""; | ||
1451 | if (ui->drag_is_from) { | ||
1452 | if (!isvalidmove(state, 0, ui->sx, ui->sy, ui->cx, ui->cy)) return ""; | ||
1453 | sprintf(buf, "L%d,%d-%d,%d", ui->sx, ui->sy, ui->cx, ui->cy); | ||
1454 | } else { | ||
1455 | if (!isvalidmove(state, 0, ui->cx, ui->cy, ui->sx, ui->sy)) return ""; | ||
1456 | sprintf(buf, "L%d,%d-%d,%d", ui->cx, ui->cy, ui->sx, ui->sy); | ||
1457 | } | ||
1458 | return dupstr(buf); | ||
1459 | } else { | ||
1460 | ui->dragging = TRUE; | ||
1461 | ui->sx = ui->cx; | ||
1462 | ui->sy = ui->cy; | ||
1463 | ui->dx = COORD(ui->cx) + TILE_SIZE/2; | ||
1464 | ui->dy = COORD(ui->cy) + TILE_SIZE/2; | ||
1465 | ui->drag_is_from = (button == CURSOR_SELECT) ? 1 : 0; | ||
1466 | } | ||
1467 | return ""; | ||
1468 | } | ||
1469 | if (IS_MOUSE_DOWN(button)) { | ||
1470 | if (ui->cshow) { | ||
1471 | ui->cshow = ui->dragging = 0; | ||
1472 | } | ||
1473 | assert(!ui->dragging); | ||
1474 | if (!INGRID(state, x, y)) return NULL; | ||
1475 | |||
1476 | if (button == LEFT_BUTTON) { | ||
1477 | /* disallow dragging from the final number. */ | ||
1478 | if ((state->nums[y*w+x] == state->n) && | ||
1479 | (state->flags[y*w+x] & FLAG_IMMUTABLE)) | ||
1480 | return NULL; | ||
1481 | } else if (button == RIGHT_BUTTON) { | ||
1482 | /* disallow dragging to the first number. */ | ||
1483 | if ((state->nums[y*w+x] == 1) && | ||
1484 | (state->flags[y*w+x] & FLAG_IMMUTABLE)) | ||
1485 | return NULL; | ||
1486 | } | ||
1487 | |||
1488 | ui->dragging = TRUE; | ||
1489 | ui->drag_is_from = (button == LEFT_BUTTON) ? 1 : 0; | ||
1490 | ui->sx = x; | ||
1491 | ui->sy = y; | ||
1492 | ui->dx = mx; | ||
1493 | ui->dy = my; | ||
1494 | ui->cshow = 0; | ||
1495 | return ""; | ||
1496 | } else if (IS_MOUSE_DRAG(button) && ui->dragging) { | ||
1497 | ui->dx = mx; | ||
1498 | ui->dy = my; | ||
1499 | return ""; | ||
1500 | } else if (IS_MOUSE_RELEASE(button) && ui->dragging) { | ||
1501 | ui->dragging = FALSE; | ||
1502 | if (ui->sx == x && ui->sy == y) return ""; /* single click */ | ||
1503 | |||
1504 | if (!INGRID(state, x, y)) { | ||
1505 | int si = ui->sy*w+ui->sx; | ||
1506 | if (state->prev[si] == -1 && state->next[si] == -1) | ||
1507 | return ""; | ||
1508 | sprintf(buf, "%c%d,%d", | ||
1509 | (int)(ui->drag_is_from ? 'C' : 'X'), ui->sx, ui->sy); | ||
1510 | return dupstr(buf); | ||
1511 | } | ||
1512 | |||
1513 | if (ui->drag_is_from) { | ||
1514 | if (!isvalidmove(state, 0, ui->sx, ui->sy, x, y)) return ""; | ||
1515 | sprintf(buf, "L%d,%d-%d,%d", ui->sx, ui->sy, x, y); | ||
1516 | } else { | ||
1517 | if (!isvalidmove(state, 0, x, y, ui->sx, ui->sy)) return ""; | ||
1518 | sprintf(buf, "L%d,%d-%d,%d", x, y, ui->sx, ui->sy); | ||
1519 | } | ||
1520 | return dupstr(buf); | ||
1521 | } /* else if (button == 'H' || button == 'h') | ||
1522 | return dupstr("H"); */ | ||
1523 | else if ((button == 'x' || button == 'X') && ui->cshow) { | ||
1524 | int si = ui->cy*w + ui->cx; | ||
1525 | if (state->prev[si] == -1 && state->next[si] == -1) | ||
1526 | return ""; | ||
1527 | sprintf(buf, "%c%d,%d", | ||
1528 | (int)((button == 'x') ? 'C' : 'X'), ui->cx, ui->cy); | ||
1529 | return dupstr(buf); | ||
1530 | } | ||
1531 | |||
1532 | return NULL; | ||
1533 | } | ||
1534 | |||
1535 | static void unlink_cell(game_state *state, int si) | ||
1536 | { | ||
1537 | debug(("Unlinking (%d,%d).", si%state->w, si/state->w)); | ||
1538 | if (state->prev[si] != -1) { | ||
1539 | debug((" ... removing prev link from (%d,%d).", | ||
1540 | state->prev[si]%state->w, state->prev[si]/state->w)); | ||
1541 | state->next[state->prev[si]] = -1; | ||
1542 | state->prev[si] = -1; | ||
1543 | } | ||
1544 | if (state->next[si] != -1) { | ||
1545 | debug((" ... removing next link to (%d,%d).", | ||
1546 | state->next[si]%state->w, state->next[si]/state->w)); | ||
1547 | state->prev[state->next[si]] = -1; | ||
1548 | state->next[si] = -1; | ||
1549 | } | ||
1550 | } | ||
1551 | |||
1552 | static game_state *execute_move(const game_state *state, const char *move) | ||
1553 | { | ||
1554 | game_state *ret = NULL; | ||
1555 | int sx, sy, ex, ey, si, ei, w = state->w; | ||
1556 | char c; | ||
1557 | |||
1558 | debug(("move: %s", move)); | ||
1559 | |||
1560 | if (move[0] == 'S') { | ||
1561 | game_params p; | ||
1562 | game_state *tmp; | ||
1563 | char *valid; | ||
1564 | int i; | ||
1565 | |||
1566 | p.w = state->w; p.h = state->h; | ||
1567 | valid = validate_desc(&p, move+1); | ||
1568 | if (valid) { | ||
1569 | debug(("execute_move: move not valid: %s", valid)); | ||
1570 | return NULL; | ||
1571 | } | ||
1572 | ret = dup_game(state); | ||
1573 | tmp = new_game(NULL, &p, move+1); | ||
1574 | for (i = 0; i < state->n; i++) { | ||
1575 | ret->prev[i] = tmp->prev[i]; | ||
1576 | ret->next[i] = tmp->next[i]; | ||
1577 | } | ||
1578 | free_game(tmp); | ||
1579 | ret->used_solve = 1; | ||
1580 | } else if (sscanf(move, "L%d,%d-%d,%d", &sx, &sy, &ex, &ey) == 4) { | ||
1581 | if (!isvalidmove(state, 0, sx, sy, ex, ey)) return NULL; | ||
1582 | |||
1583 | ret = dup_game(state); | ||
1584 | |||
1585 | si = sy*w+sx; ei = ey*w+ex; | ||
1586 | makelink(ret, si, ei); | ||
1587 | } else if (sscanf(move, "%c%d,%d", &c, &sx, &sy) == 3) { | ||
1588 | int sset; | ||
1589 | |||
1590 | if (c != 'C' && c != 'X') return NULL; | ||
1591 | if (!INGRID(state, sx, sy)) return NULL; | ||
1592 | si = sy*w+sx; | ||
1593 | if (state->prev[si] == -1 && state->next[si] == -1) | ||
1594 | return NULL; | ||
1595 | |||
1596 | ret = dup_game(state); | ||
1597 | |||
1598 | sset = state->nums[si] / (state->n+1); | ||
1599 | if (c == 'C' || (c == 'X' && sset == 0)) { | ||
1600 | /* Unlink the single cell we dragged from the board. */ | ||
1601 | unlink_cell(ret, si); | ||
1602 | } else { | ||
1603 | int i, set; | ||
1604 | for (i = 0; i < state->n; i++) { | ||
1605 | /* Unlink all cells in the same set as the one we dragged | ||
1606 | * from the board. */ | ||
1607 | |||
1608 | if (state->nums[i] == 0) continue; | ||
1609 | set = state->nums[i] / (state->n+1); | ||
1610 | if (set != sset) continue; | ||
1611 | |||
1612 | unlink_cell(ret, i); | ||
1613 | } | ||
1614 | } | ||
1615 | } else if (strcmp(move, "H") == 0) { | ||
1616 | ret = dup_game(state); | ||
1617 | solve_state(ret); | ||
1618 | } | ||
1619 | if (ret) { | ||
1620 | update_numbers(ret); | ||
1621 | if (check_completion(ret, 1)) ret->completed = 1; | ||
1622 | } | ||
1623 | |||
1624 | return ret; | ||
1625 | } | ||
1626 | |||
1627 | /* ---------------------------------------------------------------------- | ||
1628 | * Drawing routines. | ||
1629 | */ | ||
1630 | |||
1631 | static void game_compute_size(const game_params *params, int tilesize, | ||
1632 | int *x, int *y) | ||
1633 | { | ||
1634 | /* Ick: fake up `ds->tilesize' for macro expansion purposes */ | ||
1635 | struct { int tilesize, order; } ads, *ds = &ads; | ||
1636 | ads.tilesize = tilesize; | ||
1637 | |||
1638 | *x = TILE_SIZE * params->w + 2 * BORDER; | ||
1639 | *y = TILE_SIZE * params->h + 2 * BORDER; | ||
1640 | } | ||
1641 | |||
1642 | static void game_set_size(drawing *dr, game_drawstate *ds, | ||
1643 | const game_params *params, int tilesize) | ||
1644 | { | ||
1645 | ds->tilesize = tilesize; | ||
1646 | assert(TILE_SIZE > 0); | ||
1647 | |||
1648 | assert(!ds->dragb); | ||
1649 | ds->dragb = blitter_new(dr, BLITTER_SIZE, BLITTER_SIZE); | ||
1650 | } | ||
1651 | |||
1652 | /* Colours chosen from the webby palette to work as a background to black text, | ||
1653 | * W then some plausible approximation to pastelly ROYGBIV; we then interpolate | ||
1654 | * between consecutive pairs to give another 8 (and then the drawing routine | ||
1655 | * will reuse backgrounds). */ | ||
1656 | static const unsigned long bgcols[8] = { | ||
1657 | 0xffffff, /* white */ | ||
1658 | 0xffa07a, /* lightsalmon */ | ||
1659 | 0x98fb98, /* green */ | ||
1660 | 0x7fffd4, /* aquamarine */ | ||
1661 | 0x9370db, /* medium purple */ | ||
1662 | 0xffa500, /* orange */ | ||
1663 | 0x87cefa, /* lightskyblue */ | ||
1664 | 0xffff00, /* yellow */ | ||
1665 | }; | ||
1666 | |||
1667 | static float *game_colours(frontend *fe, int *ncolours) | ||
1668 | { | ||
1669 | float *ret = snewn(3 * NCOLOURS, float); | ||
1670 | int c, i; | ||
1671 | |||
1672 | game_mkhighlight(fe, ret, COL_BACKGROUND, COL_HIGHLIGHT, COL_LOWLIGHT); | ||
1673 | |||
1674 | for (i = 0; i < 3; i++) { | ||
1675 | ret[COL_NUMBER * 3 + i] = 0.0F; | ||
1676 | ret[COL_ARROW * 3 + i] = 0.0F; | ||
1677 | ret[COL_CURSOR * 3 + i] = ret[COL_BACKGROUND * 3 + i] / 2.0F; | ||
1678 | ret[COL_GRID * 3 + i] = ret[COL_BACKGROUND * 3 + i] / 1.3F; | ||
1679 | } | ||
1680 | ret[COL_NUMBER_SET * 3 + 0] = 0.0F; | ||
1681 | ret[COL_NUMBER_SET * 3 + 1] = 0.0F; | ||
1682 | ret[COL_NUMBER_SET * 3 + 2] = 0.9F; | ||
1683 | |||
1684 | ret[COL_ERROR * 3 + 0] = 1.0F; | ||
1685 | ret[COL_ERROR * 3 + 1] = 0.0F; | ||
1686 | ret[COL_ERROR * 3 + 2] = 0.0F; | ||
1687 | |||
1688 | ret[COL_DRAG_ORIGIN * 3 + 0] = 0.2F; | ||
1689 | ret[COL_DRAG_ORIGIN * 3 + 1] = 1.0F; | ||
1690 | ret[COL_DRAG_ORIGIN * 3 + 2] = 0.2F; | ||
1691 | |||
1692 | for (c = 0; c < 8; c++) { | ||
1693 | ret[(COL_B0 + c) * 3 + 0] = (float)((bgcols[c] & 0xff0000) >> 16) / 256.0F; | ||
1694 | ret[(COL_B0 + c) * 3 + 1] = (float)((bgcols[c] & 0xff00) >> 8) / 256.0F; | ||
1695 | ret[(COL_B0 + c) * 3 + 2] = (float)((bgcols[c] & 0xff)) / 256.0F; | ||
1696 | } | ||
1697 | for (c = 0; c < 8; c++) { | ||
1698 | for (i = 0; i < 3; i++) { | ||
1699 | ret[(COL_B0 + 8 + c) * 3 + i] = | ||
1700 | (ret[(COL_B0 + c) * 3 + i] + ret[(COL_B0 + c + 1) * 3 + i]) / 2.0F; | ||
1701 | } | ||
1702 | } | ||
1703 | |||
1704 | #define average(r,a,b,w) do { \ | ||
1705 | for (i = 0; i < 3; i++) \ | ||
1706 | ret[(r)*3+i] = ret[(a)*3+i] + w * (ret[(b)*3+i] - ret[(a)*3+i]); \ | ||
1707 | } while (0) | ||
1708 | average(COL_ARROW_BG_DIM, COL_BACKGROUND, COL_ARROW, 0.1F); | ||
1709 | average(COL_NUMBER_SET_MID, COL_B0, COL_NUMBER_SET, 0.3F); | ||
1710 | for (c = 0; c < NBACKGROUNDS; c++) { | ||
1711 | /* I assume here that COL_ARROW and COL_NUMBER are the same. | ||
1712 | * Otherwise I'd need two sets of COL_M*. */ | ||
1713 | average(COL_M0 + c, COL_B0 + c, COL_NUMBER, 0.3F); | ||
1714 | average(COL_D0 + c, COL_B0 + c, COL_NUMBER, 0.1F); | ||
1715 | average(COL_X0 + c, COL_BACKGROUND, COL_B0 + c, 0.5F); | ||
1716 | } | ||
1717 | |||
1718 | *ncolours = NCOLOURS; | ||
1719 | return ret; | ||
1720 | } | ||
1721 | |||
1722 | static game_drawstate *game_new_drawstate(drawing *dr, const game_state *state) | ||
1723 | { | ||
1724 | struct game_drawstate *ds = snew(struct game_drawstate); | ||
1725 | int i; | ||
1726 | |||
1727 | ds->tilesize = ds->started = ds->solved = 0; | ||
1728 | ds->w = state->w; | ||
1729 | ds->h = state->h; | ||
1730 | ds->n = state->n; | ||
1731 | |||
1732 | ds->nums = snewn(state->n, int); | ||
1733 | ds->dirp = snewn(state->n, int); | ||
1734 | ds->f = snewn(state->n, unsigned int); | ||
1735 | for (i = 0; i < state->n; i++) { | ||
1736 | ds->nums[i] = 0; | ||
1737 | ds->dirp[i] = -1; | ||
1738 | ds->f[i] = 0; | ||
1739 | } | ||
1740 | |||
1741 | ds->angle_offset = 0.0F; | ||
1742 | |||
1743 | ds->dragging = ds->dx = ds->dy = 0; | ||
1744 | ds->dragb = NULL; | ||
1745 | |||
1746 | return ds; | ||
1747 | } | ||
1748 | |||
1749 | static void game_free_drawstate(drawing *dr, game_drawstate *ds) | ||
1750 | { | ||
1751 | sfree(ds->nums); | ||
1752 | sfree(ds->dirp); | ||
1753 | sfree(ds->f); | ||
1754 | if (ds->dragb) blitter_free(dr, ds->dragb); | ||
1755 | |||
1756 | sfree(ds); | ||
1757 | } | ||
1758 | |||
1759 | /* cx, cy are top-left corner. sz is the 'radius' of the arrow. | ||
1760 | * ang is in radians, clockwise from 0 == straight up. */ | ||
1761 | static void draw_arrow(drawing *dr, int cx, int cy, int sz, double ang, | ||
1762 | int cfill, int cout) | ||
1763 | { | ||
1764 | int coords[14]; | ||
1765 | int xdx, ydx, xdy, ydy, xdx3, xdy3; | ||
1766 | double s = sin(ang), c = cos(ang); | ||
1767 | |||
1768 | xdx3 = (int)(sz * (c/3 + 1) + 0.5) - sz; | ||
1769 | xdy3 = (int)(sz * (s/3 + 1) + 0.5) - sz; | ||
1770 | xdx = (int)(sz * (c + 1) + 0.5) - sz; | ||
1771 | xdy = (int)(sz * (s + 1) + 0.5) - sz; | ||
1772 | ydx = -xdy; | ||
1773 | ydy = xdx; | ||
1774 | |||
1775 | |||
1776 | coords[2*0 + 0] = cx - ydx; | ||
1777 | coords[2*0 + 1] = cy - ydy; | ||
1778 | coords[2*1 + 0] = cx + xdx; | ||
1779 | coords[2*1 + 1] = cy + xdy; | ||
1780 | coords[2*2 + 0] = cx + xdx3; | ||
1781 | coords[2*2 + 1] = cy + xdy3; | ||
1782 | coords[2*3 + 0] = cx + xdx3 + ydx; | ||
1783 | coords[2*3 + 1] = cy + xdy3 + ydy; | ||
1784 | coords[2*4 + 0] = cx - xdx3 + ydx; | ||
1785 | coords[2*4 + 1] = cy - xdy3 + ydy; | ||
1786 | coords[2*5 + 0] = cx - xdx3; | ||
1787 | coords[2*5 + 1] = cy - xdy3; | ||
1788 | coords[2*6 + 0] = cx - xdx; | ||
1789 | coords[2*6 + 1] = cy - xdy; | ||
1790 | |||
1791 | draw_polygon(dr, coords, 7, cfill, cout); | ||
1792 | } | ||
1793 | |||
1794 | static void draw_arrow_dir(drawing *dr, int cx, int cy, int sz, int dir, | ||
1795 | int cfill, int cout, double angle_offset) | ||
1796 | { | ||
1797 | double ang = 2.0 * PI * (double)dir / 8.0 + angle_offset; | ||
1798 | draw_arrow(dr, cx, cy, sz, ang, cfill, cout); | ||
1799 | } | ||
1800 | |||
1801 | /* cx, cy are centre coordinates.. */ | ||
1802 | static void draw_star(drawing *dr, int cx, int cy, int rad, int npoints, | ||
1803 | int cfill, int cout, double angle_offset) | ||
1804 | { | ||
1805 | int *coords, n; | ||
1806 | double a, r; | ||
1807 | |||
1808 | assert(npoints > 0); | ||
1809 | |||
1810 | coords = snewn(npoints * 2 * 2, int); | ||
1811 | |||
1812 | for (n = 0; n < npoints * 2; n++) { | ||
1813 | a = 2.0 * PI * ((double)n / ((double)npoints * 2.0)) + angle_offset; | ||
1814 | r = (n % 2) ? (double)rad/2.0 : (double)rad; | ||
1815 | |||
1816 | /* We're rotating the point at (0, -r) by a degrees */ | ||
1817 | coords[2*n+0] = cx + (int)( r * sin(a)); | ||
1818 | coords[2*n+1] = cy + (int)(-r * cos(a)); | ||
1819 | } | ||
1820 | draw_polygon(dr, coords, npoints*2, cfill, cout); | ||
1821 | sfree(coords); | ||
1822 | } | ||
1823 | |||
1824 | static int num2col(game_drawstate *ds, int num) | ||
1825 | { | ||
1826 | int set = num / (ds->n+1); | ||
1827 | |||
1828 | if (num <= 0 || set == 0) return COL_B0; | ||
1829 | return COL_B0 + 1 + ((set-1) % 15); | ||
1830 | } | ||
1831 | |||
1832 | #define ARROW_HALFSZ (7 * TILE_SIZE / 32) | ||
1833 | |||
1834 | #define F_CUR 0x001 /* Cursor on this tile. */ | ||
1835 | #define F_DRAG_SRC 0x002 /* Tile is source of a drag. */ | ||
1836 | #define F_ERROR 0x004 /* Tile marked in error. */ | ||
1837 | #define F_IMMUTABLE 0x008 /* Tile (number) is immutable. */ | ||
1838 | #define F_ARROW_POINT 0x010 /* Tile points to other tile */ | ||
1839 | #define F_ARROW_INPOINT 0x020 /* Other tile points in here. */ | ||
1840 | #define F_DIM 0x040 /* Tile is dim */ | ||
1841 | |||
1842 | static void tile_redraw(drawing *dr, game_drawstate *ds, int tx, int ty, | ||
1843 | int dir, int dirp, int num, unsigned int f, | ||
1844 | double angle_offset, int print_ink) | ||
1845 | { | ||
1846 | int cb = TILE_SIZE / 16, textsz; | ||
1847 | char buf[20]; | ||
1848 | int arrowcol, sarrowcol, setcol, textcol; | ||
1849 | int acx, acy, asz, empty = 0; | ||
1850 | |||
1851 | if (num == 0 && !(f & F_ARROW_POINT) && !(f & F_ARROW_INPOINT)) { | ||
1852 | empty = 1; | ||
1853 | /* | ||
1854 | * We don't display text in empty cells: typically these are | ||
1855 | * signified by num=0. However, in some cases a cell could | ||
1856 | * have had the number 0 assigned to it if the user made an | ||
1857 | * error (e.g. tried to connect a chain of length 5 to the | ||
1858 | * immutable number 4) so we _do_ display the 0 if the cell | ||
1859 | * has a link in or a link out. | ||
1860 | */ | ||
1861 | } | ||
1862 | |||
1863 | /* Calculate colours. */ | ||
1864 | |||
1865 | if (print_ink >= 0) { | ||
1866 | /* | ||
1867 | * We're printing, so just do everything in black. | ||
1868 | */ | ||
1869 | arrowcol = textcol = print_ink; | ||
1870 | setcol = sarrowcol = -1; /* placate optimiser */ | ||
1871 | } else { | ||
1872 | |||
1873 | setcol = empty ? COL_BACKGROUND : num2col(ds, num); | ||
1874 | |||
1875 | #define dim(fg,bg) ( \ | ||
1876 | (bg)==COL_BACKGROUND ? COL_ARROW_BG_DIM : \ | ||
1877 | (bg) + COL_D0 - COL_B0 \ | ||
1878 | ) | ||
1879 | |||
1880 | #define mid(fg,bg) ( \ | ||
1881 | (fg)==COL_NUMBER_SET ? COL_NUMBER_SET_MID : \ | ||
1882 | (bg) + COL_M0 - COL_B0 \ | ||
1883 | ) | ||
1884 | |||
1885 | #define dimbg(bg) ( \ | ||
1886 | (bg)==COL_BACKGROUND ? COL_BACKGROUND : \ | ||
1887 | (bg) + COL_X0 - COL_B0 \ | ||
1888 | ) | ||
1889 | |||
1890 | if (f & F_DRAG_SRC) arrowcol = COL_DRAG_ORIGIN; | ||
1891 | else if (f & F_DIM) arrowcol = dim(COL_ARROW, setcol); | ||
1892 | else if (f & F_ARROW_POINT) arrowcol = mid(COL_ARROW, setcol); | ||
1893 | else arrowcol = COL_ARROW; | ||
1894 | |||
1895 | if ((f & F_ERROR) && !(f & F_IMMUTABLE)) textcol = COL_ERROR; | ||
1896 | else { | ||
1897 | if (f & F_IMMUTABLE) textcol = COL_NUMBER_SET; | ||
1898 | else textcol = COL_NUMBER; | ||
1899 | |||
1900 | if (f & F_DIM) textcol = dim(textcol, setcol); | ||
1901 | else if (((f & F_ARROW_POINT) || num==ds->n) && | ||
1902 | ((f & F_ARROW_INPOINT) || num==1)) | ||
1903 | textcol = mid(textcol, setcol); | ||
1904 | } | ||
1905 | |||
1906 | if (f & F_DIM) sarrowcol = dim(COL_ARROW, setcol); | ||
1907 | else sarrowcol = COL_ARROW; | ||
1908 | } | ||
1909 | |||
1910 | /* Clear tile background */ | ||
1911 | |||
1912 | if (print_ink < 0) { | ||
1913 | draw_rect(dr, tx, ty, TILE_SIZE, TILE_SIZE, | ||
1914 | (f & F_DIM) ? dimbg(setcol) : setcol); | ||
1915 | } | ||
1916 | |||
1917 | /* Draw large (outwards-pointing) arrow. */ | ||
1918 | |||
1919 | asz = ARROW_HALFSZ; /* 'radius' of arrow/star. */ | ||
1920 | acx = tx+TILE_SIZE/2+asz; /* centre x */ | ||
1921 | acy = ty+TILE_SIZE/2+asz; /* centre y */ | ||
1922 | |||
1923 | if (num == ds->n && (f & F_IMMUTABLE)) | ||
1924 | draw_star(dr, acx, acy, asz, 5, arrowcol, arrowcol, angle_offset); | ||
1925 | else | ||
1926 | draw_arrow_dir(dr, acx, acy, asz, dir, arrowcol, arrowcol, angle_offset); | ||
1927 | if (print_ink < 0 && (f & F_CUR)) | ||
1928 | draw_rect_corners(dr, acx, acy, asz+1, COL_CURSOR); | ||
1929 | |||
1930 | /* Draw dot iff this tile requires a predecessor and doesn't have one. */ | ||
1931 | |||
1932 | if (print_ink < 0) { | ||
1933 | acx = tx+TILE_SIZE/2-asz; | ||
1934 | acy = ty+TILE_SIZE/2+asz; | ||
1935 | |||
1936 | if (!(f & F_ARROW_INPOINT) && num != 1) { | ||
1937 | draw_circle(dr, acx, acy, asz / 4, sarrowcol, sarrowcol); | ||
1938 | } | ||
1939 | } | ||
1940 | |||
1941 | /* Draw text (number or set). */ | ||
1942 | |||
1943 | if (!empty) { | ||
1944 | int set = (num <= 0) ? 0 : num / (ds->n+1); | ||
1945 | |||
1946 | char *p = buf; | ||
1947 | if (set == 0 || num <= 0) { | ||
1948 | sprintf(buf, "%d", num); | ||
1949 | } else { | ||
1950 | int n = num % (ds->n+1); | ||
1951 | p += sizeof(buf) - 1; | ||
1952 | |||
1953 | if (n != 0) { | ||
1954 | sprintf(buf, "+%d", n); /* Just to get the length... */ | ||
1955 | p -= strlen(buf); | ||
1956 | sprintf(p, "+%d", n); | ||
1957 | } else { | ||
1958 | *p = '\0'; | ||
1959 | } | ||
1960 | do { | ||
1961 | set--; | ||
1962 | p--; | ||
1963 | *p = (char)((set % 26)+'a'); | ||
1964 | set /= 26; | ||
1965 | } while (set); | ||
1966 | } | ||
1967 | textsz = min(2*asz, (TILE_SIZE - 2 * cb) / (int)strlen(p)); | ||
1968 | draw_text(dr, tx + cb, ty + TILE_SIZE/4, FONT_VARIABLE, textsz, | ||
1969 | ALIGN_VCENTRE | ALIGN_HLEFT, textcol, p); | ||
1970 | } | ||
1971 | |||
1972 | if (print_ink < 0) { | ||
1973 | draw_rect_outline(dr, tx, ty, TILE_SIZE, TILE_SIZE, COL_GRID); | ||
1974 | draw_update(dr, tx, ty, TILE_SIZE, TILE_SIZE); | ||
1975 | } | ||
1976 | } | ||
1977 | |||
1978 | static void draw_drag_indicator(drawing *dr, game_drawstate *ds, | ||
1979 | const game_state *state, const game_ui *ui, | ||
1980 | int validdrag) | ||
1981 | { | ||
1982 | int dir, w = ds->w, acol = COL_ARROW; | ||
1983 | int fx = FROMCOORD(ui->dx), fy = FROMCOORD(ui->dy); | ||
1984 | double ang; | ||
1985 | |||
1986 | if (validdrag) { | ||
1987 | /* If we could move here, lock the arrow to the appropriate direction. */ | ||
1988 | dir = ui->drag_is_from ? state->dirs[ui->sy*w+ui->sx] : state->dirs[fy*w+fx]; | ||
1989 | |||
1990 | ang = (2.0 * PI * dir) / 8.0; /* similar to calculation in draw_arrow_dir. */ | ||
1991 | } else { | ||
1992 | /* Draw an arrow pointing away from/towards the origin cell. */ | ||
1993 | int ox = COORD(ui->sx) + TILE_SIZE/2, oy = COORD(ui->sy) + TILE_SIZE/2; | ||
1994 | double tana, offset; | ||
1995 | double xdiff = abs(ox - ui->dx), ydiff = abs(oy - ui->dy); | ||
1996 | |||
1997 | if (xdiff == 0) { | ||
1998 | ang = (oy > ui->dy) ? 0.0F : PI; | ||
1999 | } else if (ydiff == 0) { | ||
2000 | ang = (ox > ui->dx) ? 3.0F*PI/2.0F : PI/2.0F; | ||
2001 | } else { | ||
2002 | if (ui->dx > ox && ui->dy < oy) { | ||
2003 | tana = xdiff / ydiff; | ||
2004 | offset = 0.0F; | ||
2005 | } else if (ui->dx > ox && ui->dy > oy) { | ||
2006 | tana = ydiff / xdiff; | ||
2007 | offset = PI/2.0F; | ||
2008 | } else if (ui->dx < ox && ui->dy > oy) { | ||
2009 | tana = xdiff / ydiff; | ||
2010 | offset = PI; | ||
2011 | } else { | ||
2012 | tana = ydiff / xdiff; | ||
2013 | offset = 3.0F * PI / 2.0F; | ||
2014 | } | ||
2015 | ang = atan(tana) + offset; | ||
2016 | } | ||
2017 | |||
2018 | if (!ui->drag_is_from) ang += PI; /* point to origin, not away from. */ | ||
2019 | |||
2020 | } | ||
2021 | draw_arrow(dr, ui->dx, ui->dy, ARROW_HALFSZ, ang, acol, acol); | ||
2022 | } | ||
2023 | |||
2024 | static void game_redraw(drawing *dr, game_drawstate *ds, | ||
2025 | const game_state *oldstate, const game_state *state, | ||
2026 | int dir, const game_ui *ui, | ||
2027 | float animtime, float flashtime) | ||
2028 | { | ||
2029 | int x, y, i, w = ds->w, dirp, force = 0; | ||
2030 | unsigned int f; | ||
2031 | double angle_offset = 0.0; | ||
2032 | game_state *postdrop = NULL; | ||
2033 | |||
2034 | if (flashtime > 0.0F) | ||
2035 | angle_offset = 2.0 * PI * (flashtime / FLASH_SPIN); | ||
2036 | if (angle_offset != ds->angle_offset) { | ||
2037 | ds->angle_offset = angle_offset; | ||
2038 | force = 1; | ||
2039 | } | ||
2040 | |||
2041 | if (ds->dragging) { | ||
2042 | assert(ds->dragb); | ||
2043 | blitter_load(dr, ds->dragb, ds->dx, ds->dy); | ||
2044 | draw_update(dr, ds->dx, ds->dy, BLITTER_SIZE, BLITTER_SIZE); | ||
2045 | ds->dragging = FALSE; | ||
2046 | } | ||
2047 | |||
2048 | /* If an in-progress drag would make a valid move if finished, we | ||
2049 | * reflect that move in the board display. We let interpret_move do | ||
2050 | * most of the heavy lifting for us: we have to copy the game_ui so | ||
2051 | * as not to stomp on the real UI's drag state. */ | ||
2052 | if (ui->dragging) { | ||
2053 | game_ui uicopy = *ui; | ||
2054 | char *movestr = interpret_move(state, &uicopy, ds, ui->dx, ui->dy, LEFT_RELEASE); | ||
2055 | |||
2056 | if (movestr != NULL && strcmp(movestr, "") != 0) { | ||
2057 | postdrop = execute_move(state, movestr); | ||
2058 | sfree(movestr); | ||
2059 | |||
2060 | state = postdrop; | ||
2061 | } | ||
2062 | } | ||
2063 | |||
2064 | if (!ds->started) { | ||
2065 | int aw = TILE_SIZE * state->w; | ||
2066 | int ah = TILE_SIZE * state->h; | ||
2067 | draw_rect(dr, 0, 0, aw + 2 * BORDER, ah + 2 * BORDER, COL_BACKGROUND); | ||
2068 | draw_rect_outline(dr, BORDER - 1, BORDER - 1, aw + 2, ah + 2, COL_GRID); | ||
2069 | draw_update(dr, 0, 0, aw + 2 * BORDER, ah + 2 * BORDER); | ||
2070 | } | ||
2071 | for (x = 0; x < state->w; x++) { | ||
2072 | for (y = 0; y < state->h; y++) { | ||
2073 | i = y*w + x; | ||
2074 | f = 0; | ||
2075 | dirp = -1; | ||
2076 | |||
2077 | if (ui->cshow && x == ui->cx && y == ui->cy) | ||
2078 | f |= F_CUR; | ||
2079 | |||
2080 | if (ui->dragging) { | ||
2081 | if (x == ui->sx && y == ui->sy) | ||
2082 | f |= F_DRAG_SRC; | ||
2083 | else if (ui->drag_is_from) { | ||
2084 | if (!ispointing(state, ui->sx, ui->sy, x, y)) | ||
2085 | f |= F_DIM; | ||
2086 | } else { | ||
2087 | if (!ispointing(state, x, y, ui->sx, ui->sy)) | ||
2088 | f |= F_DIM; | ||
2089 | } | ||
2090 | } | ||
2091 | |||
2092 | if (state->impossible || | ||
2093 | state->nums[i] < 0 || state->flags[i] & FLAG_ERROR) | ||
2094 | f |= F_ERROR; | ||
2095 | if (state->flags[i] & FLAG_IMMUTABLE) | ||
2096 | f |= F_IMMUTABLE; | ||
2097 | |||
2098 | if (state->next[i] != -1) | ||
2099 | f |= F_ARROW_POINT; | ||
2100 | |||
2101 | if (state->prev[i] != -1) { | ||
2102 | /* Currently the direction here is from our square _back_ | ||
2103 | * to its previous. We could change this to give the opposite | ||
2104 | * sense to the direction. */ | ||
2105 | f |= F_ARROW_INPOINT; | ||
2106 | dirp = whichdir(x, y, state->prev[i]%w, state->prev[i]/w); | ||
2107 | } | ||
2108 | |||
2109 | if (state->nums[i] != ds->nums[i] || | ||
2110 | f != ds->f[i] || dirp != ds->dirp[i] || | ||
2111 | force || !ds->started) { | ||
2112 | int sign; | ||
2113 | { | ||
2114 | /* | ||
2115 | * Trivial and foolish configurable option done on | ||
2116 | * purest whim. With this option enabled, the | ||
2117 | * victory flash is done by rotating each square | ||
2118 | * in the opposite direction from its immediate | ||
2119 | * neighbours, so that they behave like a field of | ||
2120 | * interlocking gears. With it disabled, they all | ||
2121 | * rotate in the same direction. Choose for | ||
2122 | * yourself which is more brain-twisting :-) | ||
2123 | */ | ||
2124 | static int gear_mode = -1; | ||
2125 | if (gear_mode < 0) { | ||
2126 | char *env = getenv("SIGNPOST_GEARS"); | ||
2127 | gear_mode = (env && (env[0] == 'y' || env[0] == 'Y')); | ||
2128 | } | ||
2129 | if (gear_mode) | ||
2130 | sign = 1 - 2 * ((x ^ y) & 1); | ||
2131 | else | ||
2132 | sign = 1; | ||
2133 | } | ||
2134 | tile_redraw(dr, ds, | ||
2135 | BORDER + x * TILE_SIZE, | ||
2136 | BORDER + y * TILE_SIZE, | ||
2137 | state->dirs[i], dirp, state->nums[i], f, | ||
2138 | sign * angle_offset, -1); | ||
2139 | ds->nums[i] = state->nums[i]; | ||
2140 | ds->f[i] = f; | ||
2141 | ds->dirp[i] = dirp; | ||
2142 | } | ||
2143 | } | ||
2144 | } | ||
2145 | if (ui->dragging) { | ||
2146 | ds->dragging = TRUE; | ||
2147 | ds->dx = ui->dx - BLITTER_SIZE/2; | ||
2148 | ds->dy = ui->dy - BLITTER_SIZE/2; | ||
2149 | blitter_save(dr, ds->dragb, ds->dx, ds->dy); | ||
2150 | |||
2151 | draw_drag_indicator(dr, ds, state, ui, postdrop ? 1 : 0); | ||
2152 | } | ||
2153 | if (postdrop) free_game(postdrop); | ||
2154 | if (!ds->started) ds->started = TRUE; | ||
2155 | } | ||
2156 | |||
2157 | static float game_anim_length(const game_state *oldstate, | ||
2158 | const game_state *newstate, int dir, game_ui *ui) | ||
2159 | { | ||
2160 | return 0.0F; | ||
2161 | } | ||
2162 | |||
2163 | static float game_flash_length(const game_state *oldstate, | ||
2164 | const game_state *newstate, int dir, game_ui *ui) | ||
2165 | { | ||
2166 | if (!oldstate->completed && | ||
2167 | newstate->completed && !newstate->used_solve) | ||
2168 | return FLASH_SPIN; | ||
2169 | else | ||
2170 | return 0.0F; | ||
2171 | } | ||
2172 | |||
2173 | static int game_status(const game_state *state) | ||
2174 | { | ||
2175 | return state->completed ? +1 : 0; | ||
2176 | } | ||
2177 | |||
2178 | static int game_timing_state(const game_state *state, game_ui *ui) | ||
2179 | { | ||
2180 | return TRUE; | ||
2181 | } | ||
2182 | |||
2183 | static void game_print_size(const game_params *params, float *x, float *y) | ||
2184 | { | ||
2185 | int pw, ph; | ||
2186 | |||
2187 | game_compute_size(params, 1300, &pw, &ph); | ||
2188 | *x = pw / 100.0F; | ||
2189 | *y = ph / 100.0F; | ||
2190 | } | ||
2191 | |||
2192 | static void game_print(drawing *dr, const game_state *state, int tilesize) | ||
2193 | { | ||
2194 | int ink = print_mono_colour(dr, 0); | ||
2195 | int x, y; | ||
2196 | |||
2197 | /* Fake up just enough of a drawstate */ | ||
2198 | game_drawstate ads, *ds = &ads; | ||
2199 | ds->tilesize = tilesize; | ||
2200 | ds->n = state->n; | ||
2201 | |||
2202 | /* | ||
2203 | * Border and grid. | ||
2204 | */ | ||
2205 | print_line_width(dr, TILE_SIZE / 40); | ||
2206 | for (x = 1; x < state->w; x++) | ||
2207 | draw_line(dr, COORD(x), COORD(0), COORD(x), COORD(state->h), ink); | ||
2208 | for (y = 1; y < state->h; y++) | ||
2209 | draw_line(dr, COORD(0), COORD(y), COORD(state->w), COORD(y), ink); | ||
2210 | print_line_width(dr, 2*TILE_SIZE / 40); | ||
2211 | draw_rect_outline(dr, COORD(0), COORD(0), TILE_SIZE*state->w, | ||
2212 | TILE_SIZE*state->h, ink); | ||
2213 | |||
2214 | /* | ||
2215 | * Arrows and numbers. | ||
2216 | */ | ||
2217 | print_line_width(dr, 0); | ||
2218 | for (y = 0; y < state->h; y++) | ||
2219 | for (x = 0; x < state->w; x++) | ||
2220 | tile_redraw(dr, ds, COORD(x), COORD(y), state->dirs[y*state->w+x], | ||
2221 | 0, state->nums[y*state->w+x], 0, 0.0, ink); | ||
2222 | } | ||
2223 | |||
2224 | #ifdef COMBINED | ||
2225 | #define thegame signpost | ||
2226 | #endif | ||
2227 | |||
2228 | const struct game thegame = { | ||
2229 | "Signpost", "games.signpost", "signpost", | ||
2230 | default_params, | ||
2231 | game_fetch_preset, NULL, | ||
2232 | decode_params, | ||
2233 | encode_params, | ||
2234 | free_params, | ||
2235 | dup_params, | ||
2236 | TRUE, game_configure, custom_params, | ||
2237 | validate_params, | ||
2238 | new_game_desc, | ||
2239 | validate_desc, | ||
2240 | new_game, | ||
2241 | dup_game, | ||
2242 | free_game, | ||
2243 | TRUE, solve_game, | ||
2244 | TRUE, game_can_format_as_text_now, game_text_format, | ||
2245 | new_ui, | ||
2246 | free_ui, | ||
2247 | encode_ui, | ||
2248 | decode_ui, | ||
2249 | game_changed_state, | ||
2250 | interpret_move, | ||
2251 | execute_move, | ||
2252 | PREFERRED_TILE_SIZE, game_compute_size, game_set_size, | ||
2253 | game_colours, | ||
2254 | game_new_drawstate, | ||
2255 | game_free_drawstate, | ||
2256 | game_redraw, | ||
2257 | game_anim_length, | ||
2258 | game_flash_length, | ||
2259 | game_status, | ||
2260 | TRUE, FALSE, game_print_size, game_print, | ||
2261 | FALSE, /* wants_statusbar */ | ||
2262 | FALSE, game_timing_state, | ||
2263 | REQUIRE_RBUTTON, /* flags */ | ||
2264 | }; | ||
2265 | |||
2266 | #ifdef STANDALONE_SOLVER | ||
2267 | |||
2268 | #include <time.h> | ||
2269 | #include <stdarg.h> | ||
2270 | |||
2271 | const char *quis = NULL; | ||
2272 | int verbose = 0; | ||
2273 | |||
2274 | void usage(FILE *out) { | ||
2275 | fprintf(out, "usage: %s [--stdin] [--soak] [--seed SEED] <params>|<game id>\n", quis); | ||
2276 | } | ||
2277 | |||
2278 | static void cycle_seed(char **seedstr, random_state *rs) | ||
2279 | { | ||
2280 | char newseed[16]; | ||
2281 | int j; | ||
2282 | |||
2283 | newseed[15] = '\0'; | ||
2284 | newseed[0] = '1' + (char)random_upto(rs, 9); | ||
2285 | for (j = 1; j < 15; j++) | ||
2286 | newseed[j] = '0' + (char)random_upto(rs, 10); | ||
2287 | sfree(*seedstr); | ||
2288 | *seedstr = dupstr(newseed); | ||
2289 | } | ||
2290 | |||
2291 | static void start_soak(game_params *p, char *seedstr) | ||
2292 | { | ||
2293 | time_t tt_start, tt_now, tt_last; | ||
2294 | char *desc, *aux; | ||
2295 | random_state *rs; | ||
2296 | long n = 0, nnums = 0, i; | ||
2297 | game_state *state; | ||
2298 | |||
2299 | tt_start = tt_now = time(NULL); | ||
2300 | printf("Soak-generating a %dx%d grid.\n", p->w, p->h); | ||
2301 | |||
2302 | while (1) { | ||
2303 | rs = random_new(seedstr, strlen(seedstr)); | ||
2304 | desc = thegame.new_desc(p, rs, &aux, 0); | ||
2305 | |||
2306 | state = thegame.new_game(NULL, p, desc); | ||
2307 | for (i = 0; i < state->n; i++) { | ||
2308 | if (state->flags[i] & FLAG_IMMUTABLE) | ||
2309 | nnums++; | ||
2310 | } | ||
2311 | thegame.free_game(state); | ||
2312 | |||
2313 | sfree(desc); | ||
2314 | cycle_seed(&seedstr, rs); | ||
2315 | random_free(rs); | ||
2316 | |||
2317 | n++; | ||
2318 | tt_last = time(NULL); | ||
2319 | if (tt_last > tt_now) { | ||
2320 | tt_now = tt_last; | ||
2321 | printf("%ld total, %3.1f/s, %3.1f nums/grid (%3.1f%%).\n", | ||
2322 | n, | ||
2323 | (double)n / ((double)tt_now - tt_start), | ||
2324 | (double)nnums / (double)n, | ||
2325 | ((double)nnums * 100.0) / ((double)n * (double)p->w * (double)p->h) ); | ||
2326 | } | ||
2327 | } | ||
2328 | } | ||
2329 | |||
2330 | static void process_desc(char *id) | ||
2331 | { | ||
2332 | char *desc, *err, *solvestr; | ||
2333 | game_params *p; | ||
2334 | game_state *s; | ||
2335 | |||
2336 | printf("%s\n ", id); | ||
2337 | |||
2338 | desc = strchr(id, ':'); | ||
2339 | if (!desc) { | ||
2340 | fprintf(stderr, "%s: expecting game description.", quis); | ||
2341 | exit(1); | ||
2342 | } | ||
2343 | |||
2344 | *desc++ = '\0'; | ||
2345 | |||
2346 | p = thegame.default_params(); | ||
2347 | thegame.decode_params(p, id); | ||
2348 | err = thegame.validate_params(p, 1); | ||
2349 | if (err) { | ||
2350 | fprintf(stderr, "%s: %s", quis, err); | ||
2351 | thegame.free_params(p); | ||
2352 | return; | ||
2353 | } | ||
2354 | |||
2355 | err = thegame.validate_desc(p, desc); | ||
2356 | if (err) { | ||
2357 | fprintf(stderr, "%s: %s\nDescription: %s\n", quis, err, desc); | ||
2358 | thegame.free_params(p); | ||
2359 | return; | ||
2360 | } | ||
2361 | |||
2362 | s = thegame.new_game(NULL, p, desc); | ||
2363 | |||
2364 | solvestr = thegame.solve(s, s, NULL, &err); | ||
2365 | if (!solvestr) | ||
2366 | fprintf(stderr, "%s\n", err); | ||
2367 | else | ||
2368 | printf("Puzzle is soluble.\n"); | ||
2369 | |||
2370 | thegame.free_game(s); | ||
2371 | thegame.free_params(p); | ||
2372 | } | ||
2373 | |||
2374 | int main(int argc, const char *argv[]) | ||
2375 | { | ||
2376 | char *id = NULL, *desc, *err, *aux = NULL; | ||
2377 | int soak = 0, verbose = 0, stdin_desc = 0, n = 1, i; | ||
2378 | char *seedstr = NULL, newseed[16]; | ||
2379 | |||
2380 | setvbuf(stdout, NULL, _IONBF, 0); | ||
2381 | |||
2382 | quis = argv[0]; | ||
2383 | while (--argc > 0) { | ||
2384 | char *p = (char*)(*++argv); | ||
2385 | if (!strcmp(p, "-v") || !strcmp(p, "--verbose")) | ||
2386 | verbose = 1; | ||
2387 | else if (!strcmp(p, "--stdin")) | ||
2388 | stdin_desc = 1; | ||
2389 | else if (!strcmp(p, "-e") || !strcmp(p, "--seed")) { | ||
2390 | seedstr = dupstr(*++argv); | ||
2391 | argc--; | ||
2392 | } else if (!strcmp(p, "-n") || !strcmp(p, "--number")) { | ||
2393 | n = atoi(*++argv); | ||
2394 | argc--; | ||
2395 | } else if (!strcmp(p, "-s") || !strcmp(p, "--soak")) { | ||
2396 | soak = 1; | ||
2397 | } else if (*p == '-') { | ||
2398 | fprintf(stderr, "%s: unrecognised option `%s'\n", argv[0], p); | ||
2399 | usage(stderr); | ||
2400 | exit(1); | ||
2401 | } else { | ||
2402 | id = p; | ||
2403 | } | ||
2404 | } | ||
2405 | |||
2406 | sprintf(newseed, "%lu", (unsigned long) time(NULL)); | ||
2407 | seedstr = dupstr(newseed); | ||
2408 | |||
2409 | if (id || !stdin_desc) { | ||
2410 | if (id && strchr(id, ':')) { | ||
2411 | /* Parameters and description passed on cmd-line: | ||
2412 | * try and solve it. */ | ||
2413 | process_desc(id); | ||
2414 | } else { | ||
2415 | /* No description passed on cmd-line: decode parameters | ||
2416 | * (with optional seed too) */ | ||
2417 | |||
2418 | game_params *p = thegame.default_params(); | ||
2419 | |||
2420 | if (id) { | ||
2421 | char *cmdseed = strchr(id, '#'); | ||
2422 | if (cmdseed) { | ||
2423 | *cmdseed++ = '\0'; | ||
2424 | sfree(seedstr); | ||
2425 | seedstr = dupstr(cmdseed); | ||
2426 | } | ||
2427 | |||
2428 | thegame.decode_params(p, id); | ||
2429 | } | ||
2430 | |||
2431 | err = thegame.validate_params(p, 1); | ||
2432 | if (err) { | ||
2433 | fprintf(stderr, "%s: %s", quis, err); | ||
2434 | thegame.free_params(p); | ||
2435 | exit(1); | ||
2436 | } | ||
2437 | |||
2438 | /* We have a set of valid parameters; either soak with it | ||
2439 | * or generate a single game description and print to stdout. */ | ||
2440 | if (soak) | ||
2441 | start_soak(p, seedstr); | ||
2442 | else { | ||
2443 | char *pstring = thegame.encode_params(p, 0); | ||
2444 | |||
2445 | for (i = 0; i < n; i++) { | ||
2446 | random_state *rs = random_new(seedstr, strlen(seedstr)); | ||
2447 | |||
2448 | if (verbose) printf("%s#%s\n", pstring, seedstr); | ||
2449 | desc = thegame.new_desc(p, rs, &aux, 0); | ||
2450 | printf("%s:%s\n", pstring, desc); | ||
2451 | sfree(desc); | ||
2452 | |||
2453 | cycle_seed(&seedstr, rs); | ||
2454 | |||
2455 | random_free(rs); | ||
2456 | } | ||
2457 | |||
2458 | sfree(pstring); | ||
2459 | } | ||
2460 | thegame.free_params(p); | ||
2461 | } | ||
2462 | } | ||
2463 | |||
2464 | if (stdin_desc) { | ||
2465 | char buf[4096]; | ||
2466 | |||
2467 | while (fgets(buf, sizeof(buf), stdin)) { | ||
2468 | buf[strcspn(buf, "\r\n")] = '\0'; | ||
2469 | process_desc(buf); | ||
2470 | } | ||
2471 | } | ||
2472 | sfree(seedstr); | ||
2473 | |||
2474 | return 0; | ||
2475 | } | ||
2476 | |||
2477 | #endif | ||
2478 | |||
2479 | |||
2480 | /* vim: set shiftwidth=4 tabstop=8: */ | ||