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/flip.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/flip.c')
-rw-r--r-- | apps/plugins/puzzles/src/flip.c | 1349 |
1 files changed, 1349 insertions, 0 deletions
diff --git a/apps/plugins/puzzles/src/flip.c b/apps/plugins/puzzles/src/flip.c new file mode 100644 index 0000000000..c7126fb7d9 --- /dev/null +++ b/apps/plugins/puzzles/src/flip.c | |||
@@ -0,0 +1,1349 @@ | |||
1 | /* | ||
2 | * flip.c: Puzzle involving lighting up all the squares on a grid, | ||
3 | * where each click toggles an overlapping set of lights. | ||
4 | */ | ||
5 | |||
6 | #include <stdio.h> | ||
7 | #include <stdlib.h> | ||
8 | #include <string.h> | ||
9 | #include <assert.h> | ||
10 | #include <ctype.h> | ||
11 | #include <math.h> | ||
12 | |||
13 | #include "puzzles.h" | ||
14 | #include "tree234.h" | ||
15 | |||
16 | enum { | ||
17 | COL_BACKGROUND, | ||
18 | COL_WRONG, | ||
19 | COL_RIGHT, | ||
20 | COL_GRID, | ||
21 | COL_DIAG, | ||
22 | COL_HINT, | ||
23 | COL_CURSOR, | ||
24 | NCOLOURS | ||
25 | }; | ||
26 | |||
27 | #define PREFERRED_TILE_SIZE 48 | ||
28 | #define TILE_SIZE (ds->tilesize) | ||
29 | #define BORDER (TILE_SIZE / 2) | ||
30 | #define COORD(x) ( (x) * TILE_SIZE + BORDER ) | ||
31 | #define FROMCOORD(x) ( ((x) - BORDER + TILE_SIZE) / TILE_SIZE - 1 ) | ||
32 | |||
33 | #define ANIM_TIME 0.25F | ||
34 | #define FLASH_FRAME 0.07F | ||
35 | |||
36 | /* | ||
37 | * Possible ways to decide which lights are toggled by each click. | ||
38 | * Essentially, each of these describes a means of inventing a | ||
39 | * matrix over GF(2). | ||
40 | */ | ||
41 | enum { | ||
42 | CROSSES, RANDOM | ||
43 | }; | ||
44 | |||
45 | struct game_params { | ||
46 | int w, h; | ||
47 | int matrix_type; | ||
48 | }; | ||
49 | |||
50 | /* | ||
51 | * This structure is shared between all the game_states describing | ||
52 | * a particular game, so it's reference-counted. | ||
53 | */ | ||
54 | struct matrix { | ||
55 | int refcount; | ||
56 | unsigned char *matrix; /* array of (w*h) by (w*h) */ | ||
57 | }; | ||
58 | |||
59 | struct game_state { | ||
60 | int w, h; | ||
61 | int moves, completed, cheated, hints_active; | ||
62 | unsigned char *grid; /* array of w*h */ | ||
63 | struct matrix *matrix; | ||
64 | }; | ||
65 | |||
66 | static game_params *default_params(void) | ||
67 | { | ||
68 | game_params *ret = snew(game_params); | ||
69 | |||
70 | ret->w = ret->h = 5; | ||
71 | ret->matrix_type = CROSSES; | ||
72 | |||
73 | return ret; | ||
74 | } | ||
75 | |||
76 | static const struct game_params flip_presets[] = { | ||
77 | {3, 3, CROSSES}, | ||
78 | {4, 4, CROSSES}, | ||
79 | {5, 5, CROSSES}, | ||
80 | {3, 3, RANDOM}, | ||
81 | {4, 4, RANDOM}, | ||
82 | {5, 5, RANDOM}, | ||
83 | }; | ||
84 | |||
85 | static int game_fetch_preset(int i, char **name, game_params **params) | ||
86 | { | ||
87 | game_params *ret; | ||
88 | char str[80]; | ||
89 | |||
90 | if (i < 0 || i >= lenof(flip_presets)) | ||
91 | return FALSE; | ||
92 | |||
93 | ret = snew(game_params); | ||
94 | *ret = flip_presets[i]; | ||
95 | |||
96 | sprintf(str, "%dx%d %s", ret->w, ret->h, | ||
97 | ret->matrix_type == CROSSES ? "Crosses" : "Random"); | ||
98 | |||
99 | *name = dupstr(str); | ||
100 | *params = ret; | ||
101 | return TRUE; | ||
102 | } | ||
103 | |||
104 | static void free_params(game_params *params) | ||
105 | { | ||
106 | sfree(params); | ||
107 | } | ||
108 | |||
109 | static game_params *dup_params(const game_params *params) | ||
110 | { | ||
111 | game_params *ret = snew(game_params); | ||
112 | *ret = *params; /* structure copy */ | ||
113 | return ret; | ||
114 | } | ||
115 | |||
116 | static void decode_params(game_params *ret, char const *string) | ||
117 | { | ||
118 | ret->w = ret->h = atoi(string); | ||
119 | while (*string && isdigit((unsigned char)*string)) string++; | ||
120 | if (*string == 'x') { | ||
121 | string++; | ||
122 | ret->h = atoi(string); | ||
123 | while (*string && isdigit((unsigned char)*string)) string++; | ||
124 | } | ||
125 | if (*string == 'r') { | ||
126 | string++; | ||
127 | ret->matrix_type = RANDOM; | ||
128 | } else if (*string == 'c') { | ||
129 | string++; | ||
130 | ret->matrix_type = CROSSES; | ||
131 | } | ||
132 | } | ||
133 | |||
134 | static char *encode_params(const game_params *params, int full) | ||
135 | { | ||
136 | char data[256]; | ||
137 | |||
138 | sprintf(data, "%dx%d%s", params->w, params->h, | ||
139 | !full ? "" : params->matrix_type == CROSSES ? "c" : "r"); | ||
140 | |||
141 | return dupstr(data); | ||
142 | } | ||
143 | |||
144 | static config_item *game_configure(const game_params *params) | ||
145 | { | ||
146 | config_item *ret = snewn(4, config_item); | ||
147 | char buf[80]; | ||
148 | |||
149 | ret[0].name = "Width"; | ||
150 | ret[0].type = C_STRING; | ||
151 | sprintf(buf, "%d", params->w); | ||
152 | ret[0].sval = dupstr(buf); | ||
153 | ret[0].ival = 0; | ||
154 | |||
155 | ret[1].name = "Height"; | ||
156 | ret[1].type = C_STRING; | ||
157 | sprintf(buf, "%d", params->h); | ||
158 | ret[1].sval = dupstr(buf); | ||
159 | ret[1].ival = 0; | ||
160 | |||
161 | ret[2].name = "Shape type"; | ||
162 | ret[2].type = C_CHOICES; | ||
163 | ret[2].sval = ":Crosses:Random"; | ||
164 | ret[2].ival = params->matrix_type; | ||
165 | |||
166 | ret[3].name = NULL; | ||
167 | ret[3].type = C_END; | ||
168 | ret[3].sval = NULL; | ||
169 | ret[3].ival = 0; | ||
170 | |||
171 | return ret; | ||
172 | } | ||
173 | |||
174 | static game_params *custom_params(const config_item *cfg) | ||
175 | { | ||
176 | game_params *ret = snew(game_params); | ||
177 | |||
178 | ret->w = atoi(cfg[0].sval); | ||
179 | ret->h = atoi(cfg[1].sval); | ||
180 | ret->matrix_type = cfg[2].ival; | ||
181 | |||
182 | return ret; | ||
183 | } | ||
184 | |||
185 | static char *validate_params(const game_params *params, int full) | ||
186 | { | ||
187 | if (params->w <= 0 || params->h <= 0) | ||
188 | return "Width and height must both be greater than zero"; | ||
189 | return NULL; | ||
190 | } | ||
191 | |||
192 | static char *encode_bitmap(unsigned char *bmp, int len) | ||
193 | { | ||
194 | int slen = (len + 3) / 4; | ||
195 | char *ret; | ||
196 | int i; | ||
197 | |||
198 | ret = snewn(slen + 1, char); | ||
199 | for (i = 0; i < slen; i++) { | ||
200 | int j, v; | ||
201 | v = 0; | ||
202 | for (j = 0; j < 4; j++) | ||
203 | if (i*4+j < len && bmp[i*4+j]) | ||
204 | v |= 8 >> j; | ||
205 | ret[i] = "0123456789abcdef"[v]; | ||
206 | } | ||
207 | ret[slen] = '\0'; | ||
208 | return ret; | ||
209 | } | ||
210 | |||
211 | static void decode_bitmap(unsigned char *bmp, int len, const char *hex) | ||
212 | { | ||
213 | int slen = (len + 3) / 4; | ||
214 | int i; | ||
215 | |||
216 | for (i = 0; i < slen; i++) { | ||
217 | int j, v, c = hex[i]; | ||
218 | if (c >= '0' && c <= '9') | ||
219 | v = c - '0'; | ||
220 | else if (c >= 'A' && c <= 'F') | ||
221 | v = c - 'A' + 10; | ||
222 | else if (c >= 'a' && c <= 'f') | ||
223 | v = c - 'a' + 10; | ||
224 | else | ||
225 | v = 0; /* shouldn't happen */ | ||
226 | for (j = 0; j < 4; j++) { | ||
227 | if (i*4+j < len) { | ||
228 | if (v & (8 >> j)) | ||
229 | bmp[i*4+j] = 1; | ||
230 | else | ||
231 | bmp[i*4+j] = 0; | ||
232 | } | ||
233 | } | ||
234 | } | ||
235 | } | ||
236 | |||
237 | /* | ||
238 | * Structure used during random matrix generation, and a compare | ||
239 | * function to permit storage in a tree234. | ||
240 | */ | ||
241 | struct sq { | ||
242 | int cx, cy; /* coords of click square */ | ||
243 | int x, y; /* coords of output square */ | ||
244 | /* | ||
245 | * Number of click squares which currently affect this output | ||
246 | * square. | ||
247 | */ | ||
248 | int coverage; | ||
249 | /* | ||
250 | * Number of output squares currently affected by this click | ||
251 | * square. | ||
252 | */ | ||
253 | int ominosize; | ||
254 | }; | ||
255 | #define SORT(field) do { \ | ||
256 | if (a->field < b->field) \ | ||
257 | return -1; \ | ||
258 | else if (a->field > b->field) \ | ||
259 | return +1; \ | ||
260 | } while (0) | ||
261 | /* | ||
262 | * Compare function for choosing the next square to add. We must | ||
263 | * sort by coverage, then by omino size, then everything else. | ||
264 | */ | ||
265 | static int sqcmp_pick(void *av, void *bv) | ||
266 | { | ||
267 | struct sq *a = (struct sq *)av; | ||
268 | struct sq *b = (struct sq *)bv; | ||
269 | SORT(coverage); | ||
270 | SORT(ominosize); | ||
271 | SORT(cy); | ||
272 | SORT(cx); | ||
273 | SORT(y); | ||
274 | SORT(x); | ||
275 | return 0; | ||
276 | } | ||
277 | /* | ||
278 | * Compare function for adjusting the coverage figures after a | ||
279 | * change. We sort first by coverage and output square, then by | ||
280 | * everything else. | ||
281 | */ | ||
282 | static int sqcmp_cov(void *av, void *bv) | ||
283 | { | ||
284 | struct sq *a = (struct sq *)av; | ||
285 | struct sq *b = (struct sq *)bv; | ||
286 | SORT(coverage); | ||
287 | SORT(y); | ||
288 | SORT(x); | ||
289 | SORT(ominosize); | ||
290 | SORT(cy); | ||
291 | SORT(cx); | ||
292 | return 0; | ||
293 | } | ||
294 | /* | ||
295 | * Compare function for adjusting the omino sizes after a change. | ||
296 | * We sort first by omino size and input square, then by everything | ||
297 | * else. | ||
298 | */ | ||
299 | static int sqcmp_osize(void *av, void *bv) | ||
300 | { | ||
301 | struct sq *a = (struct sq *)av; | ||
302 | struct sq *b = (struct sq *)bv; | ||
303 | SORT(ominosize); | ||
304 | SORT(cy); | ||
305 | SORT(cx); | ||
306 | SORT(coverage); | ||
307 | SORT(y); | ||
308 | SORT(x); | ||
309 | return 0; | ||
310 | } | ||
311 | static void addsq(tree234 *t, int w, int h, int cx, int cy, | ||
312 | int x, int y, unsigned char *matrix) | ||
313 | { | ||
314 | int wh = w * h; | ||
315 | struct sq *sq; | ||
316 | int i; | ||
317 | |||
318 | if (x < 0 || x >= w || y < 0 || y >= h) | ||
319 | return; | ||
320 | if (abs(x-cx) > 1 || abs(y-cy) > 1) | ||
321 | return; | ||
322 | if (matrix[(cy*w+cx) * wh + y*w+x]) | ||
323 | return; | ||
324 | |||
325 | sq = snew(struct sq); | ||
326 | sq->cx = cx; | ||
327 | sq->cy = cy; | ||
328 | sq->x = x; | ||
329 | sq->y = y; | ||
330 | sq->coverage = sq->ominosize = 0; | ||
331 | for (i = 0; i < wh; i++) { | ||
332 | if (matrix[i * wh + y*w+x]) | ||
333 | sq->coverage++; | ||
334 | if (matrix[(cy*w+cx) * wh + i]) | ||
335 | sq->ominosize++; | ||
336 | } | ||
337 | |||
338 | if (add234(t, sq) != sq) | ||
339 | sfree(sq); /* already there */ | ||
340 | } | ||
341 | static void addneighbours(tree234 *t, int w, int h, int cx, int cy, | ||
342 | int x, int y, unsigned char *matrix) | ||
343 | { | ||
344 | addsq(t, w, h, cx, cy, x-1, y, matrix); | ||
345 | addsq(t, w, h, cx, cy, x+1, y, matrix); | ||
346 | addsq(t, w, h, cx, cy, x, y-1, matrix); | ||
347 | addsq(t, w, h, cx, cy, x, y+1, matrix); | ||
348 | } | ||
349 | |||
350 | static char *new_game_desc(const game_params *params, random_state *rs, | ||
351 | char **aux, int interactive) | ||
352 | { | ||
353 | int w = params->w, h = params->h, wh = w * h; | ||
354 | int i, j; | ||
355 | unsigned char *matrix, *grid; | ||
356 | char *mbmp, *gbmp, *ret; | ||
357 | |||
358 | matrix = snewn(wh * wh, unsigned char); | ||
359 | grid = snewn(wh, unsigned char); | ||
360 | |||
361 | /* | ||
362 | * First set up the matrix. | ||
363 | */ | ||
364 | switch (params->matrix_type) { | ||
365 | case CROSSES: | ||
366 | for (i = 0; i < wh; i++) { | ||
367 | int ix = i % w, iy = i / w; | ||
368 | for (j = 0; j < wh; j++) { | ||
369 | int jx = j % w, jy = j / w; | ||
370 | if (abs(jx - ix) + abs(jy - iy) <= 1) | ||
371 | matrix[i*wh+j] = 1; | ||
372 | else | ||
373 | matrix[i*wh+j] = 0; | ||
374 | } | ||
375 | } | ||
376 | break; | ||
377 | case RANDOM: | ||
378 | while (1) { | ||
379 | tree234 *pick, *cov, *osize; | ||
380 | int limit; | ||
381 | |||
382 | pick = newtree234(sqcmp_pick); | ||
383 | cov = newtree234(sqcmp_cov); | ||
384 | osize = newtree234(sqcmp_osize); | ||
385 | |||
386 | memset(matrix, 0, wh * wh); | ||
387 | for (i = 0; i < wh; i++) { | ||
388 | matrix[i*wh+i] = 1; | ||
389 | } | ||
390 | |||
391 | for (i = 0; i < wh; i++) { | ||
392 | int ix = i % w, iy = i / w; | ||
393 | addneighbours(pick, w, h, ix, iy, ix, iy, matrix); | ||
394 | addneighbours(cov, w, h, ix, iy, ix, iy, matrix); | ||
395 | addneighbours(osize, w, h, ix, iy, ix, iy, matrix); | ||
396 | } | ||
397 | |||
398 | /* | ||
399 | * Repeatedly choose a square to add to the matrix, | ||
400 | * until we have enough. I'll arbitrarily choose our | ||
401 | * limit to be the same as the total number of set bits | ||
402 | * in the crosses matrix. | ||
403 | */ | ||
404 | limit = 4*wh - 2*(w+h); /* centre squares already present */ | ||
405 | |||
406 | while (limit-- > 0) { | ||
407 | struct sq *sq, *sq2, sqlocal; | ||
408 | int k; | ||
409 | |||
410 | /* | ||
411 | * Find the lowest element in the pick tree. | ||
412 | */ | ||
413 | sq = index234(pick, 0); | ||
414 | |||
415 | /* | ||
416 | * Find the highest element with the same coverage | ||
417 | * and omino size, by setting all other elements to | ||
418 | * lots. | ||
419 | */ | ||
420 | sqlocal = *sq; | ||
421 | sqlocal.cx = sqlocal.cy = sqlocal.x = sqlocal.y = wh; | ||
422 | sq = findrelpos234(pick, &sqlocal, NULL, REL234_LT, &k); | ||
423 | assert(sq != 0); | ||
424 | |||
425 | /* | ||
426 | * Pick at random from all elements up to k of the | ||
427 | * pick tree. | ||
428 | */ | ||
429 | k = random_upto(rs, k+1); | ||
430 | sq = delpos234(pick, k); | ||
431 | del234(cov, sq); | ||
432 | del234(osize, sq); | ||
433 | |||
434 | /* | ||
435 | * Add this square to the matrix. | ||
436 | */ | ||
437 | matrix[(sq->cy * w + sq->cx) * wh + (sq->y * w + sq->x)] = 1; | ||
438 | |||
439 | /* | ||
440 | * Correct the matrix coverage field of any sq | ||
441 | * which points at this output square. | ||
442 | */ | ||
443 | sqlocal = *sq; | ||
444 | sqlocal.cx = sqlocal.cy = sqlocal.ominosize = -1; | ||
445 | while ((sq2 = findrel234(cov, &sqlocal, NULL, | ||
446 | REL234_GT)) != NULL && | ||
447 | sq2->coverage == sq->coverage && | ||
448 | sq2->x == sq->x && sq2->y == sq->y) { | ||
449 | del234(pick, sq2); | ||
450 | del234(cov, sq2); | ||
451 | del234(osize, sq2); | ||
452 | sq2->coverage++; | ||
453 | add234(pick, sq2); | ||
454 | add234(cov, sq2); | ||
455 | add234(osize, sq2); | ||
456 | } | ||
457 | |||
458 | /* | ||
459 | * Correct the omino size field of any sq which | ||
460 | * points at this input square. | ||
461 | */ | ||
462 | sqlocal = *sq; | ||
463 | sqlocal.x = sqlocal.y = sqlocal.coverage = -1; | ||
464 | while ((sq2 = findrel234(osize, &sqlocal, NULL, | ||
465 | REL234_GT)) != NULL && | ||
466 | sq2->ominosize == sq->ominosize && | ||
467 | sq2->cx == sq->cx && sq2->cy == sq->cy) { | ||
468 | del234(pick, sq2); | ||
469 | del234(cov, sq2); | ||
470 | del234(osize, sq2); | ||
471 | sq2->ominosize++; | ||
472 | add234(pick, sq2); | ||
473 | add234(cov, sq2); | ||
474 | add234(osize, sq2); | ||
475 | } | ||
476 | |||
477 | /* | ||
478 | * The sq we actually picked out of the tree is | ||
479 | * finished with; but its neighbours now need to | ||
480 | * appear. | ||
481 | */ | ||
482 | addneighbours(pick, w,h, sq->cx,sq->cy, sq->x,sq->y, matrix); | ||
483 | addneighbours(cov, w,h, sq->cx,sq->cy, sq->x,sq->y, matrix); | ||
484 | addneighbours(osize, w,h, sq->cx,sq->cy, sq->x,sq->y, matrix); | ||
485 | sfree(sq); | ||
486 | } | ||
487 | |||
488 | /* | ||
489 | * Free all remaining sq structures. | ||
490 | */ | ||
491 | { | ||
492 | struct sq *sq; | ||
493 | while ((sq = delpos234(pick, 0)) != NULL) | ||
494 | sfree(sq); | ||
495 | } | ||
496 | freetree234(pick); | ||
497 | freetree234(cov); | ||
498 | freetree234(osize); | ||
499 | |||
500 | /* | ||
501 | * Finally, check to see if any two matrix rows are | ||
502 | * exactly identical. If so, this is not an acceptable | ||
503 | * matrix, and we give up and go round again. | ||
504 | * | ||
505 | * I haven't been immediately able to think of a | ||
506 | * plausible means of algorithmically avoiding this | ||
507 | * situation (by, say, making a small perturbation to | ||
508 | * an offending matrix), so for the moment I'm just | ||
509 | * going to deal with it by throwing the whole thing | ||
510 | * away. I suspect this will lead to scalability | ||
511 | * problems (since most of the things happening in | ||
512 | * these matrices are local, the chance of _some_ | ||
513 | * neighbourhood having two identical regions will | ||
514 | * increase with the grid area), but so far this puzzle | ||
515 | * seems to be really hard at large sizes so I'm not | ||
516 | * massively worried yet. Anyone needs this done | ||
517 | * better, they're welcome to submit a patch. | ||
518 | */ | ||
519 | for (i = 0; i < wh; i++) { | ||
520 | for (j = 0; j < wh; j++) | ||
521 | if (i != j && | ||
522 | !memcmp(matrix + i * wh, matrix + j * wh, wh)) | ||
523 | break; | ||
524 | if (j < wh) | ||
525 | break; | ||
526 | } | ||
527 | if (i == wh) | ||
528 | break; /* no matches found */ | ||
529 | } | ||
530 | break; | ||
531 | } | ||
532 | |||
533 | /* | ||
534 | * Now invent a random initial set of lights. | ||
535 | * | ||
536 | * At first glance it looks as if it might be quite difficult | ||
537 | * to choose equiprobably from all soluble light sets. After | ||
538 | * all, soluble light sets are those in the image space of the | ||
539 | * transformation matrix; so first we'd have to identify that | ||
540 | * space and its dimension, then pick a random coordinate for | ||
541 | * each basis vector and recombine. Lot of fiddly matrix | ||
542 | * algebra there. | ||
543 | * | ||
544 | * However, vector spaces are nicely orthogonal and relieve us | ||
545 | * of all that difficulty. For every point in the image space, | ||
546 | * there are precisely as many points in the input space that | ||
547 | * map to it as there are elements in the kernel of the | ||
548 | * transformation matrix (because adding any kernel element to | ||
549 | * the input does not change the output, and because any two | ||
550 | * inputs mapping to the same output must differ by an element | ||
551 | * of the kernel because that's what the kernel _is_); and | ||
552 | * these cosets are all disjoint (obviously, since no input | ||
553 | * point can map to more than one output point) and cover the | ||
554 | * whole space (equally obviously, because no input point can | ||
555 | * map to fewer than one output point!). | ||
556 | * | ||
557 | * So the input space contains the same number of points for | ||
558 | * each point in the output space; thus, we can simply choose | ||
559 | * equiprobably from elements of the _input_ space, and filter | ||
560 | * the result through the transformation matrix in the obvious | ||
561 | * way, and we thereby guarantee to choose equiprobably from | ||
562 | * all the output points. Phew! | ||
563 | */ | ||
564 | while (1) { | ||
565 | memset(grid, 0, wh); | ||
566 | for (i = 0; i < wh; i++) { | ||
567 | int v = random_upto(rs, 2); | ||
568 | if (v) { | ||
569 | for (j = 0; j < wh; j++) | ||
570 | grid[j] ^= matrix[i*wh+j]; | ||
571 | } | ||
572 | } | ||
573 | /* | ||
574 | * Ensure we don't have the starting state already! | ||
575 | */ | ||
576 | for (i = 0; i < wh; i++) | ||
577 | if (grid[i]) | ||
578 | break; | ||
579 | if (i < wh) | ||
580 | break; | ||
581 | } | ||
582 | |||
583 | /* | ||
584 | * Now encode the matrix and the starting grid as a game | ||
585 | * description. We'll do this by concatenating two great big | ||
586 | * hex bitmaps. | ||
587 | */ | ||
588 | mbmp = encode_bitmap(matrix, wh*wh); | ||
589 | gbmp = encode_bitmap(grid, wh); | ||
590 | ret = snewn(strlen(mbmp) + strlen(gbmp) + 2, char); | ||
591 | sprintf(ret, "%s,%s", mbmp, gbmp); | ||
592 | sfree(mbmp); | ||
593 | sfree(gbmp); | ||
594 | sfree(matrix); | ||
595 | sfree(grid); | ||
596 | return ret; | ||
597 | } | ||
598 | |||
599 | static char *validate_desc(const game_params *params, const char *desc) | ||
600 | { | ||
601 | int w = params->w, h = params->h, wh = w * h; | ||
602 | int mlen = (wh*wh+3)/4, glen = (wh+3)/4; | ||
603 | |||
604 | if (strspn(desc, "0123456789abcdefABCDEF") != mlen) | ||
605 | return "Matrix description is wrong length"; | ||
606 | if (desc[mlen] != ',') | ||
607 | return "Expected comma after matrix description"; | ||
608 | if (strspn(desc+mlen+1, "0123456789abcdefABCDEF") != glen) | ||
609 | return "Grid description is wrong length"; | ||
610 | if (desc[mlen+1+glen]) | ||
611 | return "Unexpected data after grid description"; | ||
612 | |||
613 | return NULL; | ||
614 | } | ||
615 | |||
616 | static game_state *new_game(midend *me, const game_params *params, | ||
617 | const char *desc) | ||
618 | { | ||
619 | int w = params->w, h = params->h, wh = w * h; | ||
620 | int mlen = (wh*wh+3)/4; | ||
621 | |||
622 | game_state *state = snew(game_state); | ||
623 | |||
624 | state->w = w; | ||
625 | state->h = h; | ||
626 | state->completed = FALSE; | ||
627 | state->cheated = FALSE; | ||
628 | state->hints_active = FALSE; | ||
629 | state->moves = 0; | ||
630 | state->matrix = snew(struct matrix); | ||
631 | state->matrix->refcount = 1; | ||
632 | state->matrix->matrix = snewn(wh*wh, unsigned char); | ||
633 | decode_bitmap(state->matrix->matrix, wh*wh, desc); | ||
634 | state->grid = snewn(wh, unsigned char); | ||
635 | decode_bitmap(state->grid, wh, desc + mlen + 1); | ||
636 | |||
637 | return state; | ||
638 | } | ||
639 | |||
640 | static game_state *dup_game(const game_state *state) | ||
641 | { | ||
642 | game_state *ret = snew(game_state); | ||
643 | |||
644 | ret->w = state->w; | ||
645 | ret->h = state->h; | ||
646 | ret->completed = state->completed; | ||
647 | ret->cheated = state->cheated; | ||
648 | ret->hints_active = state->hints_active; | ||
649 | ret->moves = state->moves; | ||
650 | ret->matrix = state->matrix; | ||
651 | state->matrix->refcount++; | ||
652 | ret->grid = snewn(ret->w * ret->h, unsigned char); | ||
653 | memcpy(ret->grid, state->grid, ret->w * ret->h); | ||
654 | |||
655 | return ret; | ||
656 | } | ||
657 | |||
658 | static void free_game(game_state *state) | ||
659 | { | ||
660 | sfree(state->grid); | ||
661 | if (--state->matrix->refcount <= 0) { | ||
662 | sfree(state->matrix->matrix); | ||
663 | sfree(state->matrix); | ||
664 | } | ||
665 | sfree(state); | ||
666 | } | ||
667 | |||
668 | static void rowxor(unsigned char *row1, unsigned char *row2, int len) | ||
669 | { | ||
670 | int i; | ||
671 | for (i = 0; i < len; i++) | ||
672 | row1[i] ^= row2[i]; | ||
673 | } | ||
674 | |||
675 | static char *solve_game(const game_state *state, const game_state *currstate, | ||
676 | const char *aux, char **error) | ||
677 | { | ||
678 | int w = state->w, h = state->h, wh = w * h; | ||
679 | unsigned char *equations, *solution, *shortest; | ||
680 | int *und, nund; | ||
681 | int rowsdone, colsdone; | ||
682 | int i, j, k, len, bestlen; | ||
683 | char *ret; | ||
684 | |||
685 | /* | ||
686 | * Set up a list of simultaneous equations. Each one is of | ||
687 | * length (wh+1) and has wh coefficients followed by a value. | ||
688 | */ | ||
689 | equations = snewn((wh + 1) * wh, unsigned char); | ||
690 | for (i = 0; i < wh; i++) { | ||
691 | for (j = 0; j < wh; j++) | ||
692 | equations[i * (wh+1) + j] = currstate->matrix->matrix[j*wh+i]; | ||
693 | equations[i * (wh+1) + wh] = currstate->grid[i] & 1; | ||
694 | } | ||
695 | |||
696 | /* | ||
697 | * Perform Gaussian elimination over GF(2). | ||
698 | */ | ||
699 | rowsdone = colsdone = 0; | ||
700 | nund = 0; | ||
701 | und = snewn(wh, int); | ||
702 | do { | ||
703 | /* | ||
704 | * Find the leftmost column which has a 1 in it somewhere | ||
705 | * outside the first `rowsdone' rows. | ||
706 | */ | ||
707 | j = -1; | ||
708 | for (i = colsdone; i < wh; i++) { | ||
709 | for (j = rowsdone; j < wh; j++) | ||
710 | if (equations[j * (wh+1) + i]) | ||
711 | break; | ||
712 | if (j < wh) | ||
713 | break; /* found one */ | ||
714 | /* | ||
715 | * This is a column which will not have an equation | ||
716 | * controlling it. Mark it as undetermined. | ||
717 | */ | ||
718 | und[nund++] = i; | ||
719 | } | ||
720 | |||
721 | /* | ||
722 | * If there wasn't one, then we've finished: all remaining | ||
723 | * equations are of the form 0 = constant. Check to see if | ||
724 | * any of them wants 0 to be equal to 1; this is the | ||
725 | * condition which indicates an insoluble problem | ||
726 | * (therefore _hopefully_ one typed in by a user!). | ||
727 | */ | ||
728 | if (i == wh) { | ||
729 | for (j = rowsdone; j < wh; j++) | ||
730 | if (equations[j * (wh+1) + wh]) { | ||
731 | *error = "No solution exists for this position"; | ||
732 | sfree(equations); | ||
733 | sfree(und); | ||
734 | return NULL; | ||
735 | } | ||
736 | break; | ||
737 | } | ||
738 | |||
739 | /* | ||
740 | * We've found a 1. It's in column i, and the topmost 1 in | ||
741 | * that column is in row j. Do a row-XOR to move it up to | ||
742 | * the topmost row if it isn't already there. | ||
743 | */ | ||
744 | assert(j != -1); | ||
745 | if (j > rowsdone) | ||
746 | rowxor(equations + rowsdone*(wh+1), equations + j*(wh+1), wh+1); | ||
747 | |||
748 | /* | ||
749 | * Do row-XORs to eliminate that 1 from all rows below the | ||
750 | * topmost row. | ||
751 | */ | ||
752 | for (j = rowsdone + 1; j < wh; j++) | ||
753 | if (equations[j*(wh+1) + i]) | ||
754 | rowxor(equations + j*(wh+1), | ||
755 | equations + rowsdone*(wh+1), wh+1); | ||
756 | |||
757 | /* | ||
758 | * Mark this row and column as done. | ||
759 | */ | ||
760 | rowsdone++; | ||
761 | colsdone = i+1; | ||
762 | |||
763 | /* | ||
764 | * If we've done all the rows, terminate. | ||
765 | */ | ||
766 | } while (rowsdone < wh); | ||
767 | |||
768 | /* | ||
769 | * If we reach here, we have the ability to produce a solution. | ||
770 | * So we go through _all_ possible solutions (each | ||
771 | * corresponding to a set of arbitrary choices of those | ||
772 | * components not directly determined by an equation), and pick | ||
773 | * one requiring the smallest number of flips. | ||
774 | */ | ||
775 | solution = snewn(wh, unsigned char); | ||
776 | shortest = snewn(wh, unsigned char); | ||
777 | memset(solution, 0, wh); | ||
778 | bestlen = wh + 1; | ||
779 | while (1) { | ||
780 | /* | ||
781 | * Find a solution based on the current values of the | ||
782 | * undetermined variables. | ||
783 | */ | ||
784 | for (j = rowsdone; j-- ;) { | ||
785 | int v; | ||
786 | |||
787 | /* | ||
788 | * Find the leftmost set bit in this equation. | ||
789 | */ | ||
790 | for (i = 0; i < wh; i++) | ||
791 | if (equations[j * (wh+1) + i]) | ||
792 | break; | ||
793 | assert(i < wh); /* there must have been one! */ | ||
794 | |||
795 | /* | ||
796 | * Compute this variable using the rest. | ||
797 | */ | ||
798 | v = equations[j * (wh+1) + wh]; | ||
799 | for (k = i+1; k < wh; k++) | ||
800 | if (equations[j * (wh+1) + k]) | ||
801 | v ^= solution[k]; | ||
802 | |||
803 | solution[i] = v; | ||
804 | } | ||
805 | |||
806 | /* | ||
807 | * Compare this solution to the current best one, and | ||
808 | * replace the best one if this one is shorter. | ||
809 | */ | ||
810 | len = 0; | ||
811 | for (i = 0; i < wh; i++) | ||
812 | if (solution[i]) | ||
813 | len++; | ||
814 | if (len < bestlen) { | ||
815 | bestlen = len; | ||
816 | memcpy(shortest, solution, wh); | ||
817 | } | ||
818 | |||
819 | /* | ||
820 | * Now increment the binary number given by the | ||
821 | * undetermined variables: turn all 1s into 0s until we see | ||
822 | * a 0, at which point we turn it into a 1. | ||
823 | */ | ||
824 | for (i = 0; i < nund; i++) { | ||
825 | solution[und[i]] = !solution[und[i]]; | ||
826 | if (solution[und[i]]) | ||
827 | break; | ||
828 | } | ||
829 | |||
830 | /* | ||
831 | * If we didn't find a 0 at any point, we have wrapped | ||
832 | * round and are back at the start, i.e. we have enumerated | ||
833 | * all solutions. | ||
834 | */ | ||
835 | if (i == nund) | ||
836 | break; | ||
837 | } | ||
838 | |||
839 | /* | ||
840 | * We have a solution. Produce a move string encoding the | ||
841 | * solution. | ||
842 | */ | ||
843 | ret = snewn(wh + 2, char); | ||
844 | ret[0] = 'S'; | ||
845 | for (i = 0; i < wh; i++) | ||
846 | ret[i+1] = shortest[i] ? '1' : '0'; | ||
847 | ret[wh+1] = '\0'; | ||
848 | |||
849 | sfree(shortest); | ||
850 | sfree(solution); | ||
851 | sfree(equations); | ||
852 | sfree(und); | ||
853 | |||
854 | return ret; | ||
855 | } | ||
856 | |||
857 | static int game_can_format_as_text_now(const game_params *params) | ||
858 | { | ||
859 | return TRUE; | ||
860 | } | ||
861 | |||
862 | #define RIGHT 1 | ||
863 | #define DOWN gw | ||
864 | |||
865 | static char *game_text_format(const game_state *state) | ||
866 | { | ||
867 | int w = state->w, h = state->h, wh = w*h, r, c, dx, dy; | ||
868 | int cw = 4, ch = 4, gw = w * cw + 2, gh = h * ch + 1, len = gw * gh; | ||
869 | char *board = snewn(len + 1, char); | ||
870 | |||
871 | memset(board, ' ', len - 1); | ||
872 | |||
873 | for (r = 0; r < h; ++r) { | ||
874 | for (c = 0; c < w; ++c) { | ||
875 | int cell = r*ch*gw + c*cw, center = cell+(ch/2)*DOWN + cw/2*RIGHT; | ||
876 | char flip = (state->grid[r*w + c] & 1) ? '#' : '.'; | ||
877 | for (dy = -1 + (r == 0); dy <= 1 - (r == h - 1); ++dy) | ||
878 | for (dx = -1 + (c == 0); dx <= 1 - (c == w - 1); ++dx) | ||
879 | if (state->matrix->matrix[(r*w+c)*wh + ((r+dy)*w + c+dx)]) | ||
880 | board[center + dy*DOWN + dx*RIGHT] = flip; | ||
881 | board[cell] = '+'; | ||
882 | for (dx = 1; dx < cw; ++dx) board[cell+dx*RIGHT] = '-'; | ||
883 | for (dy = 1; dy < ch; ++dy) board[cell+dy*DOWN] = '|'; | ||
884 | } | ||
885 | board[r*ch*gw + gw - 2] = '+'; | ||
886 | board[r*ch*gw + gw - 1] = '\n'; | ||
887 | for (dy = 1; dy < ch; ++dy) { | ||
888 | board[r*ch*gw + gw - 2 + dy*DOWN] = '|'; | ||
889 | board[r*ch*gw + gw - 1 + dy*DOWN] = '\n'; | ||
890 | } | ||
891 | } | ||
892 | memset(board + len - gw, '-', gw - 2); | ||
893 | for (c = 0; c <= w; ++c) board[len - gw + cw*c] = '+'; | ||
894 | board[len - 1] = '\n'; | ||
895 | board[len] = '\0'; | ||
896 | return board; | ||
897 | } | ||
898 | |||
899 | #undef RIGHT | ||
900 | #undef DOWN | ||
901 | |||
902 | struct game_ui { | ||
903 | int cx, cy, cdraw; | ||
904 | }; | ||
905 | |||
906 | static game_ui *new_ui(const game_state *state) | ||
907 | { | ||
908 | game_ui *ui = snew(game_ui); | ||
909 | ui->cx = ui->cy = ui->cdraw = 0; | ||
910 | return ui; | ||
911 | } | ||
912 | |||
913 | static void free_ui(game_ui *ui) | ||
914 | { | ||
915 | sfree(ui); | ||
916 | } | ||
917 | |||
918 | static char *encode_ui(const game_ui *ui) | ||
919 | { | ||
920 | return NULL; | ||
921 | } | ||
922 | |||
923 | static void decode_ui(game_ui *ui, const char *encoding) | ||
924 | { | ||
925 | } | ||
926 | |||
927 | static void game_changed_state(game_ui *ui, const game_state *oldstate, | ||
928 | const game_state *newstate) | ||
929 | { | ||
930 | } | ||
931 | |||
932 | struct game_drawstate { | ||
933 | int w, h, started; | ||
934 | unsigned char *tiles; | ||
935 | int tilesize; | ||
936 | }; | ||
937 | |||
938 | static char *interpret_move(const game_state *state, game_ui *ui, | ||
939 | const game_drawstate *ds, | ||
940 | int x, int y, int button) | ||
941 | { | ||
942 | int w = state->w, h = state->h, wh = w * h; | ||
943 | char buf[80], *nullret = NULL; | ||
944 | |||
945 | if (button == LEFT_BUTTON || IS_CURSOR_SELECT(button)) { | ||
946 | int tx, ty; | ||
947 | if (button == LEFT_BUTTON) { | ||
948 | tx = FROMCOORD(x), ty = FROMCOORD(y); | ||
949 | ui->cdraw = 0; | ||
950 | } else { | ||
951 | tx = ui->cx; ty = ui->cy; | ||
952 | ui->cdraw = 1; | ||
953 | } | ||
954 | nullret = ""; | ||
955 | |||
956 | if (tx >= 0 && tx < w && ty >= 0 && ty < h) { | ||
957 | /* | ||
958 | * It's just possible that a manually entered game ID | ||
959 | * will have at least one square do nothing whatsoever. | ||
960 | * If so, we avoid encoding a move at all. | ||
961 | */ | ||
962 | int i = ty*w+tx, j, makemove = FALSE; | ||
963 | for (j = 0; j < wh; j++) { | ||
964 | if (state->matrix->matrix[i*wh+j]) | ||
965 | makemove = TRUE; | ||
966 | } | ||
967 | if (makemove) { | ||
968 | sprintf(buf, "M%d,%d", tx, ty); | ||
969 | return dupstr(buf); | ||
970 | } else { | ||
971 | return NULL; | ||
972 | } | ||
973 | } | ||
974 | } | ||
975 | else if (IS_CURSOR_MOVE(button)) { | ||
976 | int dx = 0, dy = 0; | ||
977 | switch (button) { | ||
978 | case CURSOR_UP: dy = -1; break; | ||
979 | case CURSOR_DOWN: dy = 1; break; | ||
980 | case CURSOR_RIGHT: dx = 1; break; | ||
981 | case CURSOR_LEFT: dx = -1; break; | ||
982 | default: assert(!"shouldn't get here"); | ||
983 | } | ||
984 | ui->cx += dx; ui->cy += dy; | ||
985 | ui->cx = min(max(ui->cx, 0), state->w - 1); | ||
986 | ui->cy = min(max(ui->cy, 0), state->h - 1); | ||
987 | ui->cdraw = 1; | ||
988 | nullret = ""; | ||
989 | } | ||
990 | |||
991 | return nullret; | ||
992 | } | ||
993 | |||
994 | static game_state *execute_move(const game_state *from, const char *move) | ||
995 | { | ||
996 | int w = from->w, h = from->h, wh = w * h; | ||
997 | game_state *ret; | ||
998 | int x, y; | ||
999 | |||
1000 | if (move[0] == 'S' && strlen(move) == wh+1) { | ||
1001 | int i; | ||
1002 | |||
1003 | ret = dup_game(from); | ||
1004 | ret->hints_active = TRUE; | ||
1005 | ret->cheated = TRUE; | ||
1006 | for (i = 0; i < wh; i++) { | ||
1007 | ret->grid[i] &= ~2; | ||
1008 | if (move[i+1] != '0') | ||
1009 | ret->grid[i] |= 2; | ||
1010 | } | ||
1011 | return ret; | ||
1012 | } else if (move[0] == 'M' && | ||
1013 | sscanf(move+1, "%d,%d", &x, &y) == 2 && | ||
1014 | x >= 0 && x < w && y >= 0 && y < h) { | ||
1015 | int i, j, done; | ||
1016 | |||
1017 | ret = dup_game(from); | ||
1018 | |||
1019 | if (!ret->completed) | ||
1020 | ret->moves++; | ||
1021 | |||
1022 | i = y * w + x; | ||
1023 | |||
1024 | done = TRUE; | ||
1025 | for (j = 0; j < wh; j++) { | ||
1026 | ret->grid[j] ^= ret->matrix->matrix[i*wh+j]; | ||
1027 | if (ret->grid[j] & 1) | ||
1028 | done = FALSE; | ||
1029 | } | ||
1030 | ret->grid[i] ^= 2; /* toggle hint */ | ||
1031 | if (done) { | ||
1032 | ret->completed = TRUE; | ||
1033 | ret->hints_active = FALSE; | ||
1034 | } | ||
1035 | |||
1036 | return ret; | ||
1037 | } else | ||
1038 | return NULL; /* can't parse move string */ | ||
1039 | } | ||
1040 | |||
1041 | /* ---------------------------------------------------------------------- | ||
1042 | * Drawing routines. | ||
1043 | */ | ||
1044 | |||
1045 | static void game_compute_size(const game_params *params, int tilesize, | ||
1046 | int *x, int *y) | ||
1047 | { | ||
1048 | /* Ick: fake up `ds->tilesize' for macro expansion purposes */ | ||
1049 | struct { int tilesize; } ads, *ds = &ads; | ||
1050 | ads.tilesize = tilesize; | ||
1051 | |||
1052 | *x = TILE_SIZE * params->w + 2 * BORDER; | ||
1053 | *y = TILE_SIZE * params->h + 2 * BORDER; | ||
1054 | } | ||
1055 | |||
1056 | static void game_set_size(drawing *dr, game_drawstate *ds, | ||
1057 | const game_params *params, int tilesize) | ||
1058 | { | ||
1059 | ds->tilesize = tilesize; | ||
1060 | } | ||
1061 | |||
1062 | static float *game_colours(frontend *fe, int *ncolours) | ||
1063 | { | ||
1064 | float *ret = snewn(3 * NCOLOURS, float); | ||
1065 | |||
1066 | frontend_default_colour(fe, &ret[COL_BACKGROUND * 3]); | ||
1067 | |||
1068 | ret[COL_WRONG * 3 + 0] = ret[COL_BACKGROUND * 3 + 0] / 3; | ||
1069 | ret[COL_WRONG * 3 + 1] = ret[COL_BACKGROUND * 3 + 1] / 3; | ||
1070 | ret[COL_WRONG * 3 + 2] = ret[COL_BACKGROUND * 3 + 2] / 3; | ||
1071 | |||
1072 | ret[COL_RIGHT * 3 + 0] = 1.0F; | ||
1073 | ret[COL_RIGHT * 3 + 1] = 1.0F; | ||
1074 | ret[COL_RIGHT * 3 + 2] = 1.0F; | ||
1075 | |||
1076 | ret[COL_GRID * 3 + 0] = ret[COL_BACKGROUND * 3 + 0] / 1.5F; | ||
1077 | ret[COL_GRID * 3 + 1] = ret[COL_BACKGROUND * 3 + 1] / 1.5F; | ||
1078 | ret[COL_GRID * 3 + 2] = ret[COL_BACKGROUND * 3 + 2] / 1.5F; | ||
1079 | |||
1080 | ret[COL_DIAG * 3 + 0] = ret[COL_GRID * 3 + 0]; | ||
1081 | ret[COL_DIAG * 3 + 1] = ret[COL_GRID * 3 + 1]; | ||
1082 | ret[COL_DIAG * 3 + 2] = ret[COL_GRID * 3 + 2]; | ||
1083 | |||
1084 | ret[COL_HINT * 3 + 0] = 1.0F; | ||
1085 | ret[COL_HINT * 3 + 1] = 0.0F; | ||
1086 | ret[COL_HINT * 3 + 2] = 0.0F; | ||
1087 | |||
1088 | ret[COL_CURSOR * 3 + 0] = 0.8F; | ||
1089 | ret[COL_CURSOR * 3 + 1] = 0.0F; | ||
1090 | ret[COL_CURSOR * 3 + 2] = 0.0F; | ||
1091 | |||
1092 | *ncolours = NCOLOURS; | ||
1093 | return ret; | ||
1094 | } | ||
1095 | |||
1096 | static game_drawstate *game_new_drawstate(drawing *dr, const game_state *state) | ||
1097 | { | ||
1098 | struct game_drawstate *ds = snew(struct game_drawstate); | ||
1099 | int i; | ||
1100 | |||
1101 | ds->started = FALSE; | ||
1102 | ds->w = state->w; | ||
1103 | ds->h = state->h; | ||
1104 | ds->tiles = snewn(ds->w*ds->h, unsigned char); | ||
1105 | ds->tilesize = 0; /* haven't decided yet */ | ||
1106 | for (i = 0; i < ds->w*ds->h; i++) | ||
1107 | ds->tiles[i] = -1; | ||
1108 | |||
1109 | return ds; | ||
1110 | } | ||
1111 | |||
1112 | static void game_free_drawstate(drawing *dr, game_drawstate *ds) | ||
1113 | { | ||
1114 | sfree(ds->tiles); | ||
1115 | sfree(ds); | ||
1116 | } | ||
1117 | |||
1118 | static void draw_tile(drawing *dr, game_drawstate *ds, const game_state *state, | ||
1119 | int x, int y, int tile, int anim, float animtime) | ||
1120 | { | ||
1121 | int w = ds->w, h = ds->h, wh = w * h; | ||
1122 | int bx = x * TILE_SIZE + BORDER, by = y * TILE_SIZE + BORDER; | ||
1123 | int i, j, dcol = (tile & 4) ? COL_CURSOR : COL_DIAG; | ||
1124 | |||
1125 | clip(dr, bx+1, by+1, TILE_SIZE-1, TILE_SIZE-1); | ||
1126 | |||
1127 | draw_rect(dr, bx+1, by+1, TILE_SIZE-1, TILE_SIZE-1, | ||
1128 | anim ? COL_BACKGROUND : tile & 1 ? COL_WRONG : COL_RIGHT); | ||
1129 | if (anim) { | ||
1130 | /* | ||
1131 | * Draw a polygon indicating that the square is diagonally | ||
1132 | * flipping over. | ||
1133 | */ | ||
1134 | int coords[8], colour; | ||
1135 | |||
1136 | coords[0] = bx + TILE_SIZE; | ||
1137 | coords[1] = by; | ||
1138 | coords[2] = bx + (int)((float)TILE_SIZE * animtime); | ||
1139 | coords[3] = by + (int)((float)TILE_SIZE * animtime); | ||
1140 | coords[4] = bx; | ||
1141 | coords[5] = by + TILE_SIZE; | ||
1142 | coords[6] = bx + TILE_SIZE - (int)((float)TILE_SIZE * animtime); | ||
1143 | coords[7] = by + TILE_SIZE - (int)((float)TILE_SIZE * animtime); | ||
1144 | |||
1145 | colour = (tile & 1 ? COL_WRONG : COL_RIGHT); | ||
1146 | if (animtime < 0.5) | ||
1147 | colour = COL_WRONG + COL_RIGHT - colour; | ||
1148 | |||
1149 | draw_polygon(dr, coords, 4, colour, COL_GRID); | ||
1150 | } | ||
1151 | |||
1152 | /* | ||
1153 | * Draw a little diagram in the tile which indicates which | ||
1154 | * surrounding tiles flip when this one is clicked. | ||
1155 | */ | ||
1156 | for (i = 0; i < h; i++) | ||
1157 | for (j = 0; j < w; j++) | ||
1158 | if (state->matrix->matrix[(y*w+x)*wh + i*w+j]) { | ||
1159 | int ox = j - x, oy = i - y; | ||
1160 | int td = TILE_SIZE / 16; | ||
1161 | int cx = (bx + TILE_SIZE/2) + (2 * ox - 1) * td; | ||
1162 | int cy = (by + TILE_SIZE/2) + (2 * oy - 1) * td; | ||
1163 | if (ox == 0 && oy == 0) | ||
1164 | draw_rect(dr, cx, cy, 2*td+1, 2*td+1, dcol); | ||
1165 | else { | ||
1166 | draw_line(dr, cx, cy, cx+2*td, cy, dcol); | ||
1167 | draw_line(dr, cx, cy+2*td, cx+2*td, cy+2*td, dcol); | ||
1168 | draw_line(dr, cx, cy, cx, cy+2*td, dcol); | ||
1169 | draw_line(dr, cx+2*td, cy, cx+2*td, cy+2*td, dcol); | ||
1170 | } | ||
1171 | } | ||
1172 | |||
1173 | /* | ||
1174 | * Draw a hint rectangle if required. | ||
1175 | */ | ||
1176 | if (tile & 2) { | ||
1177 | int x1 = bx + TILE_SIZE / 20, x2 = bx + TILE_SIZE - TILE_SIZE / 20; | ||
1178 | int y1 = by + TILE_SIZE / 20, y2 = by + TILE_SIZE - TILE_SIZE / 20; | ||
1179 | int i = 3; | ||
1180 | while (i--) { | ||
1181 | draw_line(dr, x1, y1, x2, y1, COL_HINT); | ||
1182 | draw_line(dr, x1, y2, x2, y2, COL_HINT); | ||
1183 | draw_line(dr, x1, y1, x1, y2, COL_HINT); | ||
1184 | draw_line(dr, x2, y1, x2, y2, COL_HINT); | ||
1185 | x1++, y1++, x2--, y2--; | ||
1186 | } | ||
1187 | } | ||
1188 | |||
1189 | unclip(dr); | ||
1190 | |||
1191 | draw_update(dr, bx+1, by+1, TILE_SIZE-1, TILE_SIZE-1); | ||
1192 | } | ||
1193 | |||
1194 | static void game_redraw(drawing *dr, game_drawstate *ds, | ||
1195 | const game_state *oldstate, const game_state *state, | ||
1196 | int dir, const game_ui *ui, | ||
1197 | float animtime, float flashtime) | ||
1198 | { | ||
1199 | int w = ds->w, h = ds->h, wh = w * h; | ||
1200 | int i, flashframe; | ||
1201 | |||
1202 | if (!ds->started) { | ||
1203 | draw_rect(dr, 0, 0, TILE_SIZE * w + 2 * BORDER, | ||
1204 | TILE_SIZE * h + 2 * BORDER, COL_BACKGROUND); | ||
1205 | |||
1206 | /* | ||
1207 | * Draw the grid lines. | ||
1208 | */ | ||
1209 | for (i = 0; i <= w; i++) | ||
1210 | draw_line(dr, i * TILE_SIZE + BORDER, BORDER, | ||
1211 | i * TILE_SIZE + BORDER, h * TILE_SIZE + BORDER, | ||
1212 | COL_GRID); | ||
1213 | for (i = 0; i <= h; i++) | ||
1214 | draw_line(dr, BORDER, i * TILE_SIZE + BORDER, | ||
1215 | w * TILE_SIZE + BORDER, i * TILE_SIZE + BORDER, | ||
1216 | COL_GRID); | ||
1217 | |||
1218 | draw_update(dr, 0, 0, TILE_SIZE * w + 2 * BORDER, | ||
1219 | TILE_SIZE * h + 2 * BORDER); | ||
1220 | |||
1221 | ds->started = TRUE; | ||
1222 | } | ||
1223 | |||
1224 | if (flashtime) | ||
1225 | flashframe = (int)(flashtime / FLASH_FRAME); | ||
1226 | else | ||
1227 | flashframe = -1; | ||
1228 | |||
1229 | animtime /= ANIM_TIME; /* scale it so it goes from 0 to 1 */ | ||
1230 | |||
1231 | for (i = 0; i < wh; i++) { | ||
1232 | int x = i % w, y = i / w; | ||
1233 | int fx, fy, fd; | ||
1234 | int v = state->grid[i]; | ||
1235 | int vv; | ||
1236 | |||
1237 | if (flashframe >= 0) { | ||
1238 | fx = (w+1)/2 - min(x+1, w-x); | ||
1239 | fy = (h+1)/2 - min(y+1, h-y); | ||
1240 | fd = max(fx, fy); | ||
1241 | if (fd == flashframe) | ||
1242 | v |= 1; | ||
1243 | else if (fd == flashframe - 1) | ||
1244 | v &= ~1; | ||
1245 | } | ||
1246 | |||
1247 | if (!state->hints_active) | ||
1248 | v &= ~2; | ||
1249 | if (ui->cdraw && ui->cx == x && ui->cy == y) | ||
1250 | v |= 4; | ||
1251 | |||
1252 | if (oldstate && ((state->grid[i] ^ oldstate->grid[i]) &~ 2)) | ||
1253 | vv = 255; /* means `animated' */ | ||
1254 | else | ||
1255 | vv = v; | ||
1256 | |||
1257 | if (ds->tiles[i] == 255 || vv == 255 || ds->tiles[i] != vv) { | ||
1258 | draw_tile(dr, ds, state, x, y, v, vv == 255, animtime); | ||
1259 | ds->tiles[i] = vv; | ||
1260 | } | ||
1261 | } | ||
1262 | |||
1263 | { | ||
1264 | char buf[256]; | ||
1265 | |||
1266 | sprintf(buf, "%sMoves: %d", | ||
1267 | (state->completed ? | ||
1268 | (state->cheated ? "Auto-solved. " : "COMPLETED! ") : | ||
1269 | (state->cheated ? "Auto-solver used. " : "")), | ||
1270 | state->moves); | ||
1271 | |||
1272 | status_bar(dr, buf); | ||
1273 | } | ||
1274 | } | ||
1275 | |||
1276 | static float game_anim_length(const game_state *oldstate, | ||
1277 | const game_state *newstate, int dir, game_ui *ui) | ||
1278 | { | ||
1279 | return ANIM_TIME; | ||
1280 | } | ||
1281 | |||
1282 | static float game_flash_length(const game_state *oldstate, | ||
1283 | const game_state *newstate, int dir, game_ui *ui) | ||
1284 | { | ||
1285 | if (!oldstate->completed && newstate->completed) | ||
1286 | return FLASH_FRAME * (max((newstate->w+1)/2, (newstate->h+1)/2)+1); | ||
1287 | |||
1288 | return 0.0F; | ||
1289 | } | ||
1290 | |||
1291 | static int game_status(const game_state *state) | ||
1292 | { | ||
1293 | return state->completed ? +1 : 0; | ||
1294 | } | ||
1295 | |||
1296 | static int game_timing_state(const game_state *state, game_ui *ui) | ||
1297 | { | ||
1298 | return TRUE; | ||
1299 | } | ||
1300 | |||
1301 | static void game_print_size(const game_params *params, float *x, float *y) | ||
1302 | { | ||
1303 | } | ||
1304 | |||
1305 | static void game_print(drawing *dr, const game_state *state, int tilesize) | ||
1306 | { | ||
1307 | } | ||
1308 | |||
1309 | #ifdef COMBINED | ||
1310 | #define thegame flip | ||
1311 | #endif | ||
1312 | |||
1313 | const struct game thegame = { | ||
1314 | "Flip", "games.flip", "flip", | ||
1315 | default_params, | ||
1316 | game_fetch_preset, NULL, | ||
1317 | decode_params, | ||
1318 | encode_params, | ||
1319 | free_params, | ||
1320 | dup_params, | ||
1321 | TRUE, game_configure, custom_params, | ||
1322 | validate_params, | ||
1323 | new_game_desc, | ||
1324 | validate_desc, | ||
1325 | new_game, | ||
1326 | dup_game, | ||
1327 | free_game, | ||
1328 | TRUE, solve_game, | ||
1329 | TRUE, game_can_format_as_text_now, game_text_format, | ||
1330 | new_ui, | ||
1331 | free_ui, | ||
1332 | encode_ui, | ||
1333 | decode_ui, | ||
1334 | game_changed_state, | ||
1335 | interpret_move, | ||
1336 | execute_move, | ||
1337 | PREFERRED_TILE_SIZE, game_compute_size, game_set_size, | ||
1338 | game_colours, | ||
1339 | game_new_drawstate, | ||
1340 | game_free_drawstate, | ||
1341 | game_redraw, | ||
1342 | game_anim_length, | ||
1343 | game_flash_length, | ||
1344 | game_status, | ||
1345 | FALSE, FALSE, game_print_size, game_print, | ||
1346 | TRUE, /* wants_statusbar */ | ||
1347 | FALSE, game_timing_state, | ||
1348 | 0, /* flags */ | ||
1349 | }; | ||