f278dcf4 |
1 | /* |
2 | * pearl.c: Nikoli's `Masyu' puzzle. Currently this is a blank |
3 | * puzzle file with nothing but a test solver-generator. |
4 | */ |
5 | |
6 | /* |
7 | * TODO: |
8 | * |
9 | * - The generation method appears to be fundamentally flawed. I |
10 | * think generating a random loop and then choosing a clue set |
11 | * is simply not a viable approach, because on a test run of |
12 | * 10,000 attempts, it generated _six_ viable puzzles. All the |
13 | * rest of the randomly generated loops failed to be soluble |
14 | * even given a maximal clue set. Also, the vast majority of the |
15 | * clues were white circles (straight clues); black circles |
16 | * (corners) seem very uncommon. |
17 | * + So what can we do? One possible approach would be to |
18 | * adjust the random loop generation so that it created loops |
19 | * which were in some heuristic sense more likely to be |
20 | * viable Masyu puzzles. Certainly a good start on that would |
21 | * be to arrange that black clues actually _came up_ slightly |
22 | * more often, but I have no idea whether that would be |
23 | * sufficient. |
24 | * + A second option would be to throw the entire mechanism out |
25 | * and instead write a different generator from scratch which |
26 | * evolves the solution along with the puzzle: place a few |
27 | * clues, nail down a bit of the loop, place another clue, |
28 | * nail down some more, etc. It's unclear whether this can |
29 | * sensibly be done, though. |
30 | * |
31 | * - Puzzle playing UI and everything else apart from the |
32 | * generator... |
33 | */ |
34 | |
35 | #include <stdio.h> |
36 | #include <stdlib.h> |
37 | #include <string.h> |
38 | #include <assert.h> |
39 | #include <ctype.h> |
40 | #include <math.h> |
41 | |
42 | #include "puzzles.h" |
43 | |
44 | #define NOCLUE 0 |
45 | #define CORNER 1 |
46 | #define STRAIGHT 2 |
47 | |
48 | #define R 1 |
49 | #define U 2 |
50 | #define L 4 |
51 | #define D 8 |
52 | |
53 | #define DX(d) ( ((d)==R) - ((d)==L) ) |
54 | #define DY(d) ( ((d)==D) - ((d)==U) ) |
55 | |
56 | #define F(d) (((d << 2) | (d >> 2)) & 0xF) |
57 | #define C(d) (((d << 3) | (d >> 1)) & 0xF) |
58 | #define A(d) (((d << 1) | (d >> 3)) & 0xF) |
59 | |
60 | #define LR (L | R) |
61 | #define RL (R | L) |
62 | #define UD (U | D) |
63 | #define DU (D | U) |
64 | #define LU (L | U) |
65 | #define UL (U | L) |
66 | #define LD (L | D) |
67 | #define DL (D | L) |
68 | #define RU (R | U) |
69 | #define UR (U | R) |
70 | #define RD (R | D) |
71 | #define DR (D | R) |
72 | #define BLANK 0 |
73 | #define UNKNOWN 15 |
74 | |
75 | #define bLR (1 << LR) |
76 | #define bRL (1 << RL) |
77 | #define bUD (1 << UD) |
78 | #define bDU (1 << DU) |
79 | #define bLU (1 << LU) |
80 | #define bUL (1 << UL) |
81 | #define bLD (1 << LD) |
82 | #define bDL (1 << DL) |
83 | #define bRU (1 << RU) |
84 | #define bUR (1 << UR) |
85 | #define bRD (1 << RD) |
86 | #define bDR (1 << DR) |
87 | #define bBLANK (1 << BLANK) |
88 | |
89 | enum { |
90 | COL_BACKGROUND, |
91 | NCOLOURS |
92 | }; |
93 | |
94 | struct game_params { |
95 | int FIXME; |
96 | }; |
97 | |
98 | struct game_state { |
99 | int FIXME; |
100 | }; |
101 | |
102 | static game_params *default_params(void) |
103 | { |
104 | game_params *ret = snew(game_params); |
105 | |
106 | ret->FIXME = 0; |
107 | |
108 | return ret; |
109 | } |
110 | |
111 | static int game_fetch_preset(int i, char **name, game_params **params) |
112 | { |
113 | return FALSE; |
114 | } |
115 | |
116 | static void free_params(game_params *params) |
117 | { |
118 | sfree(params); |
119 | } |
120 | |
121 | static game_params *dup_params(game_params *params) |
122 | { |
123 | game_params *ret = snew(game_params); |
124 | *ret = *params; /* structure copy */ |
125 | return ret; |
126 | } |
127 | |
128 | static void decode_params(game_params *params, char const *string) |
129 | { |
130 | } |
131 | |
132 | static char *encode_params(game_params *params, int full) |
133 | { |
134 | return dupstr("FIXME"); |
135 | } |
136 | |
137 | static config_item *game_configure(game_params *params) |
138 | { |
139 | return NULL; |
140 | } |
141 | |
142 | static game_params *custom_params(config_item *cfg) |
143 | { |
144 | return NULL; |
145 | } |
146 | |
147 | static char *validate_params(game_params *params, int full) |
148 | { |
149 | return NULL; |
150 | } |
151 | |
152 | /* ---------------------------------------------------------------------- |
153 | * Solver. |
154 | */ |
155 | |
156 | int pearl_solve(int w, int h, char *clues, char *result) |
157 | { |
158 | int W = 2*w+1, H = 2*h+1; |
159 | short *workspace; |
160 | int *dsf, *dsfsize; |
161 | int x, y, b, d; |
162 | int ret = -1; |
163 | |
164 | /* |
165 | * workspace[(2*y+1)*W+(2*x+1)] indicates the possible nature |
166 | * of the square (x,y), as a logical OR of bitfields. |
167 | * |
168 | * workspace[(2*y)*W+(2*x+1)], for x odd and y even, indicates |
169 | * whether the horizontal edge between (x,y) and (x+1,y) is |
170 | * connected (1), disconnected (2) or unknown (3). |
171 | * |
172 | * workspace[(2*y+1)*W+(2*x)], indicates the same about the |
173 | * vertical edge between (x,y) and (x,y+1). |
174 | * |
175 | * Initially, every square is considered capable of being in |
176 | * any of the seven possible states (two straights, four |
177 | * corners and empty), except those corresponding to clue |
178 | * squares which are more restricted. |
179 | * |
180 | * Initially, all edges are unknown, except the ones around the |
181 | * grid border which are known to be disconnected. |
182 | */ |
183 | workspace = snewn(W*H, short); |
184 | for (x = 0; x < W*H; x++) |
185 | workspace[x] = 0; |
186 | /* Square states */ |
187 | for (y = 0; y < h; y++) |
188 | for (x = 0; x < w; x++) |
189 | switch (clues[y*w+x]) { |
190 | case CORNER: |
191 | workspace[(2*y+1)*W+(2*x+1)] = bLU|bLD|bRU|bRD; |
192 | break; |
193 | case STRAIGHT: |
194 | workspace[(2*y+1)*W+(2*x+1)] = bLR|bUD; |
195 | break; |
196 | default: |
197 | workspace[(2*y+1)*W+(2*x+1)] = bLR|bUD|bLU|bLD|bRU|bRD|bBLANK; |
198 | break; |
199 | } |
200 | /* Horizontal edges */ |
201 | for (y = 0; y <= h; y++) |
202 | for (x = 0; x < w; x++) |
203 | workspace[(2*y)*W+(2*x+1)] = (y==0 || y==h ? 2 : 3); |
204 | /* Vertical edges */ |
205 | for (y = 0; y < h; y++) |
206 | for (x = 0; x <= w; x++) |
207 | workspace[(2*y+1)*W+(2*x)] = (x==0 || x==w ? 2 : 3); |
208 | |
209 | /* |
210 | * We maintain a dsf of connected squares, together with a |
211 | * count of the size of each equivalence class. |
212 | */ |
213 | dsf = snewn(w*h, int); |
214 | dsfsize = snewn(w*h, int); |
215 | |
216 | /* |
217 | * Now repeatedly try to find something we can do. |
218 | */ |
219 | while (1) { |
ffb5d90c |
220 | int done_something = FALSE; |
f278dcf4 |
221 | |
222 | #ifdef SOLVER_DIAGNOSTICS |
223 | for (y = 0; y < H; y++) { |
224 | for (x = 0; x < W; x++) |
225 | printf("%*x", (x&1) ? 5 : 2, workspace[y*W+x]); |
226 | printf("\n"); |
227 | } |
228 | #endif |
229 | |
f278dcf4 |
230 | /* |
231 | * Go through the square state words, and discard any |
232 | * square state which is inconsistent with known facts |
233 | * about the edges around the square. |
234 | */ |
235 | for (y = 0; y < h; y++) |
236 | for (x = 0; x < w; x++) { |
237 | for (b = 0; b < 0xD; b++) |
238 | if (workspace[(2*y+1)*W+(2*x+1)] & (1<<b)) { |
239 | /* |
240 | * If any edge of this square is known to |
241 | * be connected when state b would require |
242 | * it disconnected, or vice versa, discard |
243 | * the state. |
244 | */ |
245 | for (d = 1; d <= 8; d += d) { |
246 | int ex = 2*x+1 + DX(d), ey = 2*y+1 + DY(d); |
247 | if (workspace[ey*W+ex] == |
248 | ((b & d) ? 2 : 1)) { |
249 | workspace[(2*y+1)*W+(2*x+1)] &= ~(1<<b); |
250 | #ifdef SOLVER_DIAGNOSTICS |
251 | printf("edge (%d,%d)-(%d,%d) rules out state" |
252 | " %d for square (%d,%d)\n", |
253 | ex/2, ey/2, (ex+1)/2, (ey+1)/2, |
254 | b, x, y); |
255 | #endif |
256 | done_something = TRUE; |
257 | break; |
258 | } |
259 | } |
260 | } |
261 | |
262 | /* |
263 | * Consistency check: each square must have at |
264 | * least one state left! |
265 | */ |
266 | if (!workspace[(2*y+1)*W+(2*x+1)]) { |
267 | #ifdef SOLVER_DIAGNOSTICS |
268 | printf("edge check at (%d,%d): inconsistency\n", x, y); |
ffb5d90c |
269 | #endif |
f278dcf4 |
270 | ret = 0; |
271 | goto cleanup; |
f278dcf4 |
272 | } |
273 | } |
274 | |
275 | /* |
276 | * Now go through the states array again, and nail down any |
277 | * unknown edge if one of its neighbouring squares makes it |
278 | * known. |
279 | */ |
280 | for (y = 0; y < h; y++) |
281 | for (x = 0; x < w; x++) { |
282 | int edgeor = 0, edgeand = 15; |
283 | |
284 | for (b = 0; b < 0xD; b++) |
285 | if (workspace[(2*y+1)*W+(2*x+1)] & (1<<b)) { |
286 | edgeor |= b; |
287 | edgeand &= b; |
288 | } |
289 | |
290 | /* |
291 | * Now any bit clear in edgeor marks a disconnected |
292 | * edge, and any bit set in edgeand marks a |
293 | * connected edge. |
294 | */ |
295 | |
296 | /* First check consistency: neither bit is both! */ |
297 | if (edgeand & ~edgeor) { |
298 | #ifdef SOLVER_DIAGNOSTICS |
299 | printf("square check at (%d,%d): inconsistency\n", x, y); |
ffb5d90c |
300 | #endif |
f278dcf4 |
301 | ret = 0; |
302 | goto cleanup; |
f278dcf4 |
303 | } |
304 | |
305 | for (d = 1; d <= 8; d += d) { |
306 | int ex = 2*x+1 + DX(d), ey = 2*y+1 + DY(d); |
307 | |
308 | if (!(edgeor & d) && workspace[ey*W+ex] == 3) { |
309 | workspace[ey*W+ex] = 2; |
310 | done_something = TRUE; |
311 | #ifdef SOLVER_DIAGNOSTICS |
312 | printf("possible states of square (%d,%d) force edge" |
313 | " (%d,%d)-(%d,%d) to be disconnected\n", |
314 | x, y, ex/2, ey/2, (ex+1)/2, (ey+1)/2); |
315 | #endif |
316 | } else if ((edgeand & d) && workspace[ey*W+ex] == 3) { |
317 | workspace[ey*W+ex] = 1; |
318 | done_something = TRUE; |
319 | #ifdef SOLVER_DIAGNOSTICS |
320 | printf("possible states of square (%d,%d) force edge" |
321 | " (%d,%d)-(%d,%d) to be connected\n", |
322 | x, y, ex/2, ey/2, (ex+1)/2, (ey+1)/2); |
323 | #endif |
324 | } |
325 | } |
326 | } |
327 | |
328 | if (done_something) |
329 | continue; |
330 | |
331 | /* |
332 | * Now for longer-range clue-based deductions (using the |
333 | * rules that a corner clue must connect to two straight |
334 | * squares, and a straight clue must connect to at least |
335 | * one corner square). |
336 | */ |
337 | for (y = 0; y < h; y++) |
338 | for (x = 0; x < w; x++) |
339 | switch (clues[y*w+x]) { |
340 | case CORNER: |
341 | for (d = 1; d <= 8; d += d) { |
342 | int ex = 2*x+1 + DX(d), ey = 2*y+1 + DY(d); |
343 | int fx = ex + DX(d), fy = ey + DY(d); |
344 | int type = d | F(d); |
345 | |
346 | if (workspace[ey*W+ex] == 1) { |
347 | /* |
348 | * If a corner clue is connected on any |
349 | * edge, then we can immediately nail |
350 | * down the square beyond that edge as |
351 | * being a straight in the appropriate |
352 | * direction. |
353 | */ |
354 | if (workspace[fy*W+fx] != (1<<type)) { |
355 | workspace[fy*W+fx] = (1<<type); |
356 | done_something = TRUE; |
357 | #ifdef SOLVER_DIAGNOSTICS |
358 | printf("corner clue at (%d,%d) forces square " |
359 | "(%d,%d) into state %d\n", x, y, |
360 | fx/2, fy/2, type); |
361 | #endif |
362 | |
363 | } |
364 | } else if (workspace[ey*W+ex] == 3) { |
365 | /* |
366 | * Conversely, if a corner clue is |
367 | * separated by an unknown edge from a |
368 | * square which _cannot_ be a straight |
369 | * in the appropriate direction, we can |
370 | * mark that edge as disconnected. |
371 | */ |
372 | if (!(workspace[fy*W+fx] & (1<<type))) { |
373 | workspace[ey*W+ex] = 2; |
374 | done_something = TRUE; |
375 | #ifdef SOLVER_DIAGNOSTICS |
376 | printf("corner clue at (%d,%d), plus square " |
377 | "(%d,%d) not being state %d, " |
378 | "disconnects edge (%d,%d)-(%d,%d)\n", |
379 | x, y, fx/2, fy/2, type, |
380 | ex/2, ey/2, (ex+1)/2, (ey+1)/2); |
381 | #endif |
382 | |
383 | } |
384 | } |
385 | } |
386 | |
f278dcf4 |
387 | break; |
388 | case STRAIGHT: |
389 | /* |
390 | * If a straight clue is between two squares |
391 | * neither of which is capable of being a |
392 | * corner connected to it, then the straight |
393 | * clue cannot point in that direction. |
394 | */ |
395 | for (d = 1; d <= 2; d += d) { |
396 | int fx = 2*x+1 + 2*DX(d), fy = 2*y+1 + 2*DY(d); |
397 | int gx = 2*x+1 - 2*DX(d), gy = 2*y+1 - 2*DY(d); |
398 | int type = d | F(d); |
399 | |
400 | if (!(workspace[(2*y+1)*W+(2*x+1)] & (1<<type))) |
401 | continue; |
402 | |
403 | if (!(workspace[fy*W+fx] & ((1<<(F(d)|A(d))) | |
404 | (1<<(F(d)|C(d))))) && |
405 | !(workspace[gy*W+gx] & ((1<<( d |A(d))) | |
406 | (1<<( d |C(d)))))) { |
407 | workspace[(2*y+1)*W+(2*x+1)] &= ~(1<<type); |
408 | done_something = TRUE; |
409 | #ifdef SOLVER_DIAGNOSTICS |
410 | printf("straight clue at (%d,%d) cannot corner at " |
411 | "(%d,%d) or (%d,%d) so is not state %d\n", |
412 | x, y, fx/2, fy/2, gx/2, gy/2, type); |
413 | #endif |
414 | } |
415 | |
416 | } |
417 | |
418 | /* |
419 | * If a straight clue with known direction is |
420 | * connected on one side to a known straight, |
421 | * then on the other side it must be a corner. |
422 | */ |
423 | for (d = 1; d <= 8; d += d) { |
424 | int fx = 2*x+1 + 2*DX(d), fy = 2*y+1 + 2*DY(d); |
425 | int gx = 2*x+1 - 2*DX(d), gy = 2*y+1 - 2*DY(d); |
426 | int type = d | F(d); |
427 | |
428 | if (workspace[(2*y+1)*W+(2*x+1)] != (1<<type)) |
429 | continue; |
430 | |
431 | if (!(workspace[fy*W+fx] &~ (bLR|bUD)) && |
432 | (workspace[gy*W+gx] &~ (bLU|bLD|bRU|bRD))) { |
433 | workspace[gy*W+gx] &= (bLU|bLD|bRU|bRD); |
434 | done_something = TRUE; |
435 | #ifdef SOLVER_DIAGNOSTICS |
436 | printf("straight clue at (%d,%d) connecting to " |
437 | "straight at (%d,%d) makes (%d,%d) a " |
438 | "corner\n", x, y, fx/2, fy/2, gx/2, gy/2); |
439 | #endif |
440 | } |
441 | |
442 | } |
443 | break; |
444 | } |
445 | |
446 | if (done_something) |
447 | continue; |
448 | |
449 | /* |
450 | * Now detect shortcut loops. |
451 | */ |
452 | |
453 | { |
454 | int nonblanks, loopclass; |
455 | |
456 | dsf_init(dsf, w*h); |
457 | for (x = 0; x < w*h; x++) |
458 | dsfsize[x] = 1; |
459 | |
460 | /* |
461 | * First go through the edge entries and update the dsf |
462 | * of which squares are connected to which others. We |
463 | * also track the number of squares in each equivalence |
464 | * class, and count the overall number of |
465 | * known-non-blank squares. |
466 | * |
467 | * In the process of doing this, we must notice if a |
468 | * loop has already been formed. If it has, we blank |
469 | * out any square which isn't part of that loop |
470 | * (failing a consistency check if any such square does |
471 | * not have BLANK as one of its remaining options) and |
472 | * exit the deduction loop with success. |
473 | */ |
474 | nonblanks = 0; |
475 | loopclass = -1; |
476 | for (y = 1; y < H-1; y++) |
477 | for (x = 1; x < W-1; x++) |
478 | if ((y ^ x) & 1) { |
479 | /* |
480 | * (x,y) are the workspace coordinates of |
481 | * an edge field. Compute the normal-space |
482 | * coordinates of the squares it connects. |
483 | */ |
484 | int ax = (x-1)/2, ay = (y-1)/2, ac = ay*w+ax; |
485 | int bx = x/2, by = y/2, bc = by*w+bx; |
486 | |
487 | /* |
488 | * If the edge is connected, do the dsf |
489 | * thing. |
490 | */ |
491 | if (workspace[y*W+x] == 1) { |
492 | int ae, be; |
493 | |
494 | ae = dsf_canonify(dsf, ac); |
495 | be = dsf_canonify(dsf, bc); |
496 | |
497 | if (ae == be) { |
498 | /* |
499 | * We have a loop! |
500 | */ |
501 | if (loopclass != -1) { |
502 | /* |
503 | * In fact, we have two |
504 | * separate loops, which is |
505 | * doom. |
506 | */ |
507 | #ifdef SOLVER_DIAGNOSTICS |
508 | printf("two loops found in grid!\n"); |
509 | #endif |
510 | ret = 0; |
511 | goto cleanup; |
512 | } |
513 | loopclass = ae; |
514 | } else { |
515 | /* |
516 | * Merge the two equivalence |
517 | * classes. |
518 | */ |
519 | int size = dsfsize[ae] + dsfsize[be]; |
520 | dsf_merge(dsf, ac, bc); |
521 | ae = dsf_canonify(dsf, ac); |
522 | dsfsize[ae] = size; |
523 | } |
524 | } |
525 | } else if ((y & x) & 1) { |
526 | /* |
527 | * (x,y) are the workspace coordinates of a |
528 | * square field. If the square is |
529 | * definitely not blank, count it. |
530 | */ |
531 | if (!(workspace[y*W+x] & bBLANK)) |
532 | nonblanks++; |
533 | } |
534 | |
535 | /* |
536 | * If we discovered an existing loop above, we must now |
537 | * blank every square not part of it, and exit the main |
538 | * deduction loop. |
539 | */ |
540 | if (loopclass != -1) { |
541 | #ifdef SOLVER_DIAGNOSTICS |
542 | printf("loop found in grid!\n"); |
543 | #endif |
544 | for (y = 0; y < h; y++) |
545 | for (x = 0; x < w; x++) |
546 | if (dsf_canonify(dsf, y*w+x) != loopclass) { |
547 | if (workspace[(y*2+1)*W+(x*2+1)] & bBLANK) { |
548 | workspace[(y*2+1)*W+(x*2+1)] = bBLANK; |
549 | } else { |
550 | /* |
551 | * This square is not part of the |
552 | * loop, but is known non-blank. We |
553 | * have goofed. |
554 | */ |
555 | #ifdef SOLVER_DIAGNOSTICS |
556 | printf("non-blank square (%d,%d) found outside" |
557 | " loop!\n", x, y); |
558 | #endif |
559 | ret = 0; |
560 | goto cleanup; |
561 | } |
562 | } |
563 | /* |
564 | * And we're done. |
565 | */ |
566 | ret = 1; |
567 | break; |
568 | } |
569 | |
570 | /* |
571 | * Now go through the workspace again and mark any edge |
572 | * which would cause a shortcut loop (i.e. would |
573 | * connect together two squares in the same equivalence |
574 | * class, and that equivalence class does not contain |
575 | * _all_ the known-non-blank squares currently in the |
576 | * grid) as disconnected. Also, mark any _square state_ |
577 | * which would cause a shortcut loop as disconnected. |
578 | */ |
579 | for (y = 1; y < H-1; y++) |
580 | for (x = 1; x < W-1; x++) |
581 | if ((y ^ x) & 1) { |
582 | /* |
583 | * (x,y) are the workspace coordinates of |
584 | * an edge field. Compute the normal-space |
585 | * coordinates of the squares it connects. |
586 | */ |
587 | int ax = (x-1)/2, ay = (y-1)/2, ac = ay*w+ax; |
588 | int bx = x/2, by = y/2, bc = by*w+bx; |
589 | |
590 | /* |
591 | * If the edge is currently unknown, and |
592 | * sits between two squares in the same |
593 | * equivalence class, and the size of that |
594 | * class is less than nonblanks, then |
595 | * connecting this edge would be a shortcut |
596 | * loop and so we must not do so. |
597 | */ |
598 | if (workspace[y*W+x] == 3) { |
599 | int ae, be; |
600 | |
601 | ae = dsf_canonify(dsf, ac); |
602 | be = dsf_canonify(dsf, bc); |
603 | |
604 | if (ae == be) { |
605 | /* |
606 | * We have a loop. Is it a shortcut? |
607 | */ |
608 | if (dsfsize[ae] < nonblanks) { |
609 | /* |
610 | * Yes! Mark this edge disconnected. |
611 | */ |
612 | workspace[y*W+x] = 2; |
613 | done_something = TRUE; |
614 | #ifdef SOLVER_DIAGNOSTICS |
615 | printf("edge (%d,%d)-(%d,%d) would create" |
616 | " a shortcut loop, hence must be" |
617 | " disconnected\n", x/2, y/2, |
618 | (x+1)/2, (y+1)/2); |
619 | #endif |
620 | } |
621 | } |
622 | } |
623 | } else if ((y & x) & 1) { |
624 | /* |
625 | * (x,y) are the workspace coordinates of a |
626 | * square field. Go through its possible |
627 | * (non-blank) states and see if any gives |
628 | * rise to a shortcut loop. |
629 | * |
630 | * This is slightly fiddly, because we have |
631 | * to check whether this square is already |
632 | * part of the same equivalence class as |
633 | * the things it's joining. |
634 | */ |
635 | int ae = dsf_canonify(dsf, (y/2)*w+(x/2)); |
636 | |
637 | for (b = 2; b < 0xD; b++) |
638 | if (workspace[y*W+x] & (1<<b)) { |
639 | /* |
640 | * Find the equivalence classes of |
641 | * the two squares this one would |
642 | * connect if it were in this |
643 | * state. |
644 | */ |
645 | int e = -1; |
646 | |
647 | for (d = 1; d <= 8; d += d) if (b & d) { |
648 | int xx = x/2 + DX(d), yy = y/2 + DY(d); |
649 | int ee = dsf_canonify(dsf, yy*w+xx); |
650 | |
651 | if (e == -1) |
652 | ee = e; |
653 | else if (e != ee) |
654 | e = -2; |
655 | } |
656 | |
657 | if (e >= 0) { |
658 | /* |
659 | * This square state would form |
660 | * a loop on equivalence class |
661 | * e. Measure the size of that |
662 | * loop, and see if it's a |
663 | * shortcut. |
664 | */ |
665 | int loopsize = dsfsize[e]; |
666 | if (e != ae) |
667 | loopsize++;/* add the square itself */ |
668 | if (loopsize < nonblanks) { |
669 | /* |
670 | * It is! Mark this square |
671 | * state invalid. |
672 | */ |
673 | workspace[y*W+x] &= ~(1<<b); |
674 | done_something = TRUE; |
675 | #ifdef SOLVER_DIAGNOSTICS |
676 | printf("square (%d,%d) would create a " |
677 | "shortcut loop in state %d, " |
678 | "hence cannot be\n", |
679 | x/2, y/2, b); |
680 | #endif |
681 | } |
682 | } |
683 | } |
684 | } |
685 | } |
686 | |
687 | if (done_something) |
688 | continue; |
689 | |
690 | /* |
691 | * If we reach here, there is nothing left we can do. |
692 | * Return 2 for ambiguous puzzle. |
693 | */ |
694 | ret = 2; |
695 | goto cleanup; |
696 | } |
697 | |
698 | /* |
699 | * If we reach _here_, it's by `break' out of the main loop, |
700 | * which means we've successfully achieved a solution. This |
701 | * means that we expect every square to be nailed down to |
702 | * exactly one possibility. Transcribe those possibilities into |
703 | * the result array. |
704 | */ |
705 | for (y = 0; y < h; y++) |
706 | for (x = 0; x < w; x++) { |
707 | for (b = 0; b < 0xD; b++) |
708 | if (workspace[(2*y+1)*W+(2*x+1)] == (1<<b)) { |
709 | result[y*w+x] = b; |
710 | break; |
711 | } |
712 | assert(b < 0xD); /* we should have had a break by now */ |
713 | } |
714 | |
715 | cleanup: |
716 | sfree(dsfsize); |
717 | sfree(dsf); |
718 | sfree(workspace); |
719 | assert(ret >= 0); |
720 | return ret; |
721 | } |
722 | |
723 | /* ---------------------------------------------------------------------- |
724 | * Loop generator. |
725 | */ |
726 | |
727 | void pearl_loopgen(int w, int h, char *grid, random_state *rs) |
728 | { |
729 | int *options, *mindist, *maxdist, *list; |
730 | int x, y, d, total, n, area, limit; |
731 | |
732 | /* |
733 | * We're eventually going to have to return a w-by-h array |
734 | * containing line segment data. However, it's more convenient |
735 | * while actually generating the loop to consider the problem |
736 | * as a (w-1) by (h-1) array in which some squares are `inside' |
737 | * and some `outside'. |
738 | * |
739 | * I'm going to use the top left corner of my return array in |
740 | * the latter manner until the end of the function. |
741 | */ |
742 | |
743 | /* |
744 | * To begin with, all squares are outside (0), except for one |
745 | * randomly selected one which is inside (1). |
746 | */ |
747 | memset(grid, 0, w*h); |
748 | x = random_upto(rs, w-1); |
749 | y = random_upto(rs, h-1); |
750 | grid[y*w+x] = 1; |
751 | |
752 | /* |
753 | * I'm also going to need an array to store the possible |
754 | * options for the next extension of the grid. |
755 | */ |
756 | options = snewn(w*h, int); |
757 | for (x = 0; x < w*h; x++) |
758 | options[x] = 0; |
759 | |
760 | /* |
761 | * And some arrays and a list for breadth-first searching. |
762 | */ |
763 | mindist = snewn(w*h, int); |
764 | maxdist = snewn(w*h, int); |
765 | list = snewn(w*h, int); |
766 | |
767 | /* |
768 | * Now we repeatedly scan the grid for feasible squares into |
769 | * which we can extend our loop, pick one, and do it. |
770 | */ |
771 | area = 1; |
772 | |
773 | while (1) { |
774 | #ifdef LOOPGEN_DIAGNOSTICS |
775 | for (y = 0; y < h; y++) { |
776 | for (x = 0; x < w; x++) |
777 | printf("%d", grid[y*w+x]); |
778 | printf("\n"); |
779 | } |
780 | printf("\n"); |
781 | #endif |
782 | |
783 | /* |
784 | * Our primary aim in growing this loop is to make it |
785 | * reasonably _dense_ in the target rectangle. That is, we |
786 | * want the maximum over all squares of the minimum |
787 | * distance from that square to the loop to be small. |
788 | * |
789 | * Therefore, we start with a breadth-first search of the |
790 | * grid to find those minimum distances. |
791 | */ |
792 | { |
793 | int head = 0, tail = 0; |
794 | int i; |
795 | |
796 | for (i = 0; i < w*h; i++) { |
797 | mindist[i] = -1; |
798 | if (grid[i]) { |
799 | mindist[i] = 0; |
800 | list[tail++] = i; |
801 | } |
802 | } |
803 | |
804 | while (head < tail) { |
805 | i = list[head++]; |
806 | y = i / w; |
807 | x = i % w; |
808 | for (d = 1; d <= 8; d += d) { |
809 | int xx = x + DX(d), yy = y + DY(d); |
810 | if (xx >= 0 && xx < w && yy >= 0 && yy < h && |
811 | mindist[yy*w+xx] < 0) { |
812 | mindist[yy*w+xx] = mindist[i] + 1; |
813 | list[tail++] = yy*w+xx; |
814 | } |
815 | } |
816 | } |
817 | |
818 | /* |
819 | * Having done the BFS, we now backtrack along its path |
820 | * to determine the most distant square that each |
821 | * square is on the shortest path to. This tells us |
822 | * which of the loop extension candidates (all of which |
823 | * are squares marked 1) is most desirable to extend |
824 | * into in terms of minimising the maximum distance |
825 | * from any empty square to the nearest loop square. |
826 | */ |
827 | for (head = tail; head-- > 0 ;) { |
828 | int max; |
829 | |
830 | i = list[head]; |
831 | y = i / w; |
832 | x = i % w; |
833 | |
834 | max = mindist[i]; |
835 | |
836 | for (d = 1; d <= 8; d += d) { |
837 | int xx = x + DX(d), yy = y + DY(d); |
838 | if (xx >= 0 && xx < w && yy >= 0 && yy < h && |
839 | mindist[yy*w+xx] > mindist[i] && |
840 | maxdist[yy*w+xx] > max) { |
841 | max = maxdist[yy*w+xx]; |
842 | } |
843 | } |
844 | |
845 | maxdist[i] = max; |
846 | } |
847 | } |
848 | |
849 | /* |
850 | * A square is a viable candidate for extension of our loop |
851 | * if and only if the following conditions are all met: |
852 | * - It is currently labelled 0. |
853 | * - At least one of its four orthogonal neighbours is |
854 | * labelled 1. |
855 | * - If you consider its eight orthogonal and diagonal |
856 | * neighbours to form a ring, that ring contains at most |
857 | * one contiguous run of 1s. (It must also contain at |
858 | * _least_ one, of course, but that's already guaranteed |
859 | * by the previous condition so there's no need to test |
860 | * it separately.) |
861 | */ |
862 | total = 0; |
863 | for (y = 0; y < h-1; y++) |
864 | for (x = 0; x < w-1; x++) { |
865 | int ring[8]; |
866 | int rx, neighbours, runs, dist; |
867 | |
868 | dist = maxdist[y*w+x]; |
869 | options[y*w+x] = 0; |
870 | |
871 | if (grid[y*w+x]) |
872 | continue; /* it isn't labelled 0 */ |
873 | |
874 | neighbours = 0; |
875 | for (rx = 0, d = 1; d <= 8; rx += 2, d += d) { |
876 | int x2 = x + DX(d), y2 = y + DY(d); |
877 | int x3 = x2 + DX(A(d)), y3 = y2 + DY(A(d)); |
878 | int g2 = (x2 >= 0 && x2 < w && y2 >= 0 && y2 < h ? |
879 | grid[y2*w+x2] : 0); |
880 | int g3 = (x3 >= 0 && x3 < w && y3 >= 0 && y3 < h ? |
881 | grid[y3*w+x3] : 0); |
882 | ring[rx] = g2; |
883 | ring[rx+1] = g3; |
884 | if (g2) |
885 | neighbours++; |
886 | } |
887 | |
888 | if (!neighbours) |
889 | continue; /* it doesn't have a 1 neighbour */ |
890 | |
891 | runs = 0; |
892 | for (rx = 0; rx < 8; rx++) |
893 | if (ring[rx] && !ring[(rx+1) & 7]) |
894 | runs++; |
895 | |
896 | if (runs > 1) |
897 | continue; /* too many runs of 1s */ |
898 | |
899 | /* |
900 | * Now we know this square is a viable extension |
901 | * candidate. Mark it. |
902 | * |
903 | * FIXME: probabilistic prioritisation based on |
904 | * perimeter perturbation? (Wow, must keep that |
905 | * phrase.) |
906 | */ |
907 | options[y*w+x] = dist * (4-neighbours) * (4-neighbours); |
908 | total += options[y*w+x]; |
909 | } |
910 | |
911 | if (!total) |
912 | break; /* nowhere to go! */ |
913 | |
914 | /* |
915 | * Now pick a random one of the viable extension squares, |
916 | * and extend into it. |
917 | */ |
918 | n = random_upto(rs, total); |
919 | for (y = 0; y < h-1; y++) |
920 | for (x = 0; x < w-1; x++) { |
921 | assert(n >= 0); |
922 | if (options[y*w+x] > n) |
923 | goto found; /* two-level break */ |
924 | n -= options[y*w+x]; |
925 | } |
926 | assert(!"We shouldn't ever get here"); |
927 | found: |
928 | grid[y*w+x] = 1; |
929 | area++; |
930 | |
931 | /* |
932 | * We terminate the loop when around 7/12 of the grid area |
933 | * is full, but we also require that the loop has reached |
934 | * all four edges. |
935 | */ |
936 | limit = random_upto(rs, (w-1)*(h-1)) + 13*(w-1)*(h-1); |
937 | if (24 * area > limit) { |
938 | int l = FALSE, r = FALSE, u = FALSE, d = FALSE; |
939 | for (x = 0; x < w; x++) { |
940 | if (grid[0*w+x]) |
941 | u = TRUE; |
942 | if (grid[(h-2)*w+x]) |
943 | d = TRUE; |
944 | } |
945 | for (y = 0; y < h; y++) { |
946 | if (grid[y*w+0]) |
947 | l = TRUE; |
948 | if (grid[y*w+(w-2)]) |
949 | r = TRUE; |
950 | } |
951 | if (l && r && u && d) |
952 | break; |
953 | } |
954 | } |
955 | |
956 | sfree(list); |
957 | sfree(maxdist); |
958 | sfree(mindist); |
959 | sfree(options); |
960 | |
961 | #ifdef LOOPGEN_DIAGNOSTICS |
962 | printf("final loop:\n"); |
963 | for (y = 0; y < h; y++) { |
964 | for (x = 0; x < w; x++) |
965 | printf("%d", grid[y*w+x]); |
966 | printf("\n"); |
967 | } |
968 | printf("\n"); |
969 | #endif |
970 | |
971 | /* |
972 | * Now convert this array of 0s and 1s into an array of path |
973 | * components. |
974 | */ |
975 | for (y = h; y-- > 0 ;) { |
976 | for (x = w; x-- > 0 ;) { |
977 | /* |
978 | * Examine the four grid squares of which (x,y) are in |
979 | * the bottom right, to determine the output for this |
980 | * square. |
981 | */ |
982 | int ul = (x > 0 && y > 0 ? grid[(y-1)*w+(x-1)] : 0); |
983 | int ur = (y > 0 ? grid[(y-1)*w+x] : 0); |
984 | int dl = (x > 0 ? grid[y*w+(x-1)] : 0); |
985 | int dr = grid[y*w+x]; |
986 | int type = 0; |
987 | |
988 | if (ul != ur) type |= U; |
989 | if (dl != dr) type |= D; |
990 | if (ul != dl) type |= L; |
991 | if (ur != dr) type |= R; |
992 | |
993 | assert((bLR|bUD|bLU|bLD|bRU|bRD|bBLANK) & (1 << type)); |
994 | |
995 | grid[y*w+x] = type; |
996 | |
997 | } |
998 | } |
999 | |
1000 | #if defined LOOPGEN_DIAGNOSTICS && !defined GENERATION_DIAGNOSTICS |
1001 | printf("as returned:\n"); |
1002 | for (y = 0; y < h; y++) { |
1003 | for (x = 0; x < w; x++) { |
1004 | int type = grid[y*w+x]; |
1005 | char s[5], *p = s; |
1006 | if (type & L) *p++ = 'L'; |
1007 | if (type & R) *p++ = 'R'; |
1008 | if (type & U) *p++ = 'U'; |
1009 | if (type & D) *p++ = 'D'; |
1010 | *p = '\0'; |
1011 | printf("%3s", s); |
1012 | } |
1013 | printf("\n"); |
1014 | } |
1015 | printf("\n"); |
1016 | #endif |
1017 | } |
1018 | |
1019 | static char *new_game_desc(game_params *params, random_state *rs, |
1020 | char **aux, int interactive) |
1021 | { |
1022 | char *grid, *clues; |
1023 | int *clueorder; |
1024 | int w = 10, h = 10; |
1025 | int x, y, d, ret, i; |
1026 | |
1027 | #if 0 |
1028 | clues = snewn(7*7, char); |
1029 | memcpy(clues, |
1030 | "\0\1\0\0\2\0\0" |
1031 | "\0\0\0\2\0\0\0" |
1032 | "\0\0\0\2\0\0\1" |
1033 | "\2\0\0\2\0\0\0" |
1034 | "\2\0\0\0\0\0\1" |
1035 | "\0\0\1\0\0\2\0" |
1036 | "\0\0\2\0\0\0\0", 7*7); |
1037 | grid = snewn(7*7, char); |
1038 | printf("%d\n", pearl_solve(7, 7, clues, grid)); |
1039 | #elif 0 |
1040 | clues = snewn(10*10, char); |
1041 | memcpy(clues, |
1042 | "\0\0\2\0\2\0\0\0\0\0" |
1043 | "\0\0\0\0\2\0\0\0\1\0" |
1044 | "\0\0\1\0\1\0\2\0\0\0" |
1045 | "\0\0\0\2\0\0\2\0\0\0" |
1046 | "\1\0\0\0\0\2\0\0\0\2" |
1047 | "\0\0\2\0\0\0\0\2\0\0" |
1048 | "\0\0\1\0\0\0\2\0\0\0" |
1049 | "\2\0\0\0\1\0\0\0\0\2" |
1050 | "\0\0\0\0\0\0\2\2\0\0" |
1051 | "\0\0\1\0\0\0\0\0\0\1", 10*10); |
1052 | grid = snewn(10*10, char); |
1053 | printf("%d\n", pearl_solve(10, 10, clues, grid)); |
1054 | #elif 0 |
1055 | clues = snewn(10*10, char); |
1056 | memcpy(clues, |
1057 | "\0\0\0\0\0\0\1\0\0\0" |
1058 | "\0\1\0\1\2\0\0\0\0\2" |
1059 | "\0\0\0\0\0\0\0\0\0\1" |
1060 | "\2\0\0\1\2\2\1\0\0\0" |
1061 | "\1\0\0\0\0\0\0\1\0\0" |
1062 | "\0\0\2\0\0\0\0\0\0\2" |
1063 | "\0\0\0\2\1\2\1\0\0\2" |
1064 | "\2\0\0\0\0\0\0\0\0\0" |
1065 | "\2\0\0\0\0\1\1\0\2\0" |
1066 | "\0\0\0\2\0\0\0\0\0\0", 10*10); |
1067 | grid = snewn(10*10, char); |
1068 | printf("%d\n", pearl_solve(10, 10, clues, grid)); |
1069 | #endif |
1070 | |
1071 | grid = snewn(w*h, char); |
1072 | clues = snewn(w*h, char); |
1073 | clueorder = snewn(w*h, int); |
1074 | |
1075 | while (1) { |
1076 | pearl_loopgen(w, h, grid, rs); |
1077 | |
1078 | #ifdef GENERATION_DIAGNOSTICS |
1079 | printf("grid array:\n"); |
1080 | for (y = 0; y < h; y++) { |
1081 | for (x = 0; x < w; x++) { |
1082 | int type = grid[y*w+x]; |
1083 | char s[5], *p = s; |
1084 | if (type & L) *p++ = 'L'; |
1085 | if (type & R) *p++ = 'R'; |
1086 | if (type & U) *p++ = 'U'; |
1087 | if (type & D) *p++ = 'D'; |
1088 | *p = '\0'; |
1089 | printf("%2s ", s); |
1090 | } |
1091 | printf("\n"); |
1092 | } |
1093 | printf("\n"); |
1094 | #endif |
1095 | |
1096 | /* |
1097 | * Set up the maximal clue array. |
1098 | */ |
1099 | for (y = 0; y < h; y++) |
1100 | for (x = 0; x < w; x++) { |
1101 | int type = grid[y*w+x]; |
1102 | |
1103 | clues[y*w+x] = NOCLUE; |
1104 | |
1105 | if ((bLR|bUD) & (1 << type)) { |
1106 | /* |
1107 | * This is a straight; see if it's a viable |
1108 | * candidate for a straight clue. It qualifies if |
1109 | * at least one of the squares it connects to is a |
1110 | * corner. |
1111 | */ |
1112 | for (d = 1; d <= 8; d += d) if (type & d) { |
1113 | int xx = x + DX(d), yy = y + DY(d); |
1114 | assert(xx >= 0 && xx < w && yy >= 0 && yy < h); |
1115 | if ((bLU|bLD|bRU|bRD) & (1 << grid[yy*w+xx])) |
1116 | break; |
1117 | } |
1118 | if (d <= 8) /* we found one */ |
1119 | clues[y*w+x] = STRAIGHT; |
1120 | } else if ((bLU|bLD|bRU|bRD) & (1 << type)) { |
1121 | /* |
1122 | * This is a corner; see if it's a viable candidate |
1123 | * for a corner clue. It qualifies if all the |
1124 | * squares it connects to are straights. |
1125 | */ |
1126 | for (d = 1; d <= 8; d += d) if (type & d) { |
1127 | int xx = x + DX(d), yy = y + DY(d); |
1128 | assert(xx >= 0 && xx < w && yy >= 0 && yy < h); |
1129 | if (!((bLR|bUD) & (1 << grid[yy*w+xx]))) |
1130 | break; |
1131 | } |
1132 | if (d > 8) /* we didn't find a counterexample */ |
1133 | clues[y*w+x] = CORNER; |
1134 | } |
1135 | } |
1136 | |
1137 | #ifdef GENERATION_DIAGNOSTICS |
1138 | printf("clue array:\n"); |
1139 | for (y = 0; y < h; y++) { |
1140 | for (x = 0; x < w; x++) { |
1141 | printf("%c", " *O"[(unsigned char)clues[y*w+x]]); |
1142 | } |
1143 | printf("\n"); |
1144 | } |
1145 | printf("\n"); |
1146 | #endif |
1147 | |
1148 | /* |
1149 | * See if we can solve the puzzle just like this. |
1150 | */ |
1151 | ret = pearl_solve(w, h, clues, grid); |
1152 | assert(ret > 0); /* shouldn't be inconsistent! */ |
1153 | if (ret != 1) |
1154 | continue; /* go round and try again */ |
1155 | |
1156 | /* |
1157 | * Now shuffle the grid points and gradually remove the |
1158 | * clues to find a minimal set which still leaves the |
1159 | * puzzle soluble. |
1160 | */ |
1161 | for (i = 0; i < w*h; i++) |
1162 | clueorder[i] = i; |
1163 | shuffle(clueorder, w*h, sizeof(*clueorder), rs); |
1164 | for (i = 0; i < w*h; i++) { |
1165 | int clue; |
1166 | |
1167 | y = clueorder[i] / w; |
1168 | x = clueorder[i] % w; |
1169 | |
1170 | if (clues[y*w+x] == 0) |
1171 | continue; |
1172 | |
1173 | clue = clues[y*w+x]; |
1174 | clues[y*w+x] = 0; /* try removing this clue */ |
1175 | |
1176 | ret = pearl_solve(w, h, clues, grid); |
1177 | assert(ret > 0); |
1178 | if (ret != 1) |
1179 | clues[y*w+x] = clue; /* oops, put it back again */ |
1180 | } |
1181 | |
1182 | #ifdef FINISHED_PUZZLE |
1183 | printf("clue array:\n"); |
1184 | for (y = 0; y < h; y++) { |
1185 | for (x = 0; x < w; x++) { |
1186 | printf("%c", " *O"[(unsigned char)clues[y*w+x]]); |
1187 | } |
1188 | printf("\n"); |
1189 | } |
1190 | printf("\n"); |
1191 | #endif |
1192 | |
1193 | break; /* got it */ |
1194 | } |
1195 | |
1196 | sfree(grid); |
1197 | sfree(clues); |
1198 | sfree(clueorder); |
1199 | |
1200 | return dupstr("FIXME"); |
1201 | } |
1202 | |
1203 | static char *validate_desc(game_params *params, char *desc) |
1204 | { |
1205 | return NULL; |
1206 | } |
1207 | |
1208 | static game_state *new_game(midend *me, game_params *params, char *desc) |
1209 | { |
1210 | game_state *state = snew(game_state); |
1211 | |
1212 | state->FIXME = 0; |
1213 | |
1214 | return state; |
1215 | } |
1216 | |
1217 | static game_state *dup_game(game_state *state) |
1218 | { |
1219 | game_state *ret = snew(game_state); |
1220 | |
1221 | ret->FIXME = state->FIXME; |
1222 | |
1223 | return ret; |
1224 | } |
1225 | |
1226 | static void free_game(game_state *state) |
1227 | { |
1228 | sfree(state); |
1229 | } |
1230 | |
1231 | static char *solve_game(game_state *state, game_state *currstate, |
1232 | char *aux, char **error) |
1233 | { |
1234 | return NULL; |
1235 | } |
1236 | |
fa3abef5 |
1237 | static int game_can_format_as_text_now(game_params *params) |
1238 | { |
1239 | return TRUE; |
1240 | } |
1241 | |
f278dcf4 |
1242 | static char *game_text_format(game_state *state) |
1243 | { |
1244 | return NULL; |
1245 | } |
1246 | |
1247 | static game_ui *new_ui(game_state *state) |
1248 | { |
1249 | return NULL; |
1250 | } |
1251 | |
1252 | static void free_ui(game_ui *ui) |
1253 | { |
1254 | } |
1255 | |
1256 | static char *encode_ui(game_ui *ui) |
1257 | { |
1258 | return NULL; |
1259 | } |
1260 | |
1261 | static void decode_ui(game_ui *ui, char *encoding) |
1262 | { |
1263 | } |
1264 | |
1265 | static void game_changed_state(game_ui *ui, game_state *oldstate, |
1266 | game_state *newstate) |
1267 | { |
1268 | } |
1269 | |
1270 | struct game_drawstate { |
1271 | int tilesize; |
1272 | int FIXME; |
1273 | }; |
1274 | |
1275 | static char *interpret_move(game_state *state, game_ui *ui, game_drawstate *ds, |
1276 | int x, int y, int button) |
1277 | { |
1278 | return NULL; |
1279 | } |
1280 | |
1281 | static game_state *execute_move(game_state *state, char *move) |
1282 | { |
1283 | return NULL; |
1284 | } |
1285 | |
1286 | /* ---------------------------------------------------------------------- |
1287 | * Drawing routines. |
1288 | */ |
1289 | |
1290 | static void game_compute_size(game_params *params, int tilesize, |
1291 | int *x, int *y) |
1292 | { |
1293 | *x = *y = 10 * tilesize; /* FIXME */ |
1294 | } |
1295 | |
1296 | static void game_set_size(drawing *dr, game_drawstate *ds, |
1297 | game_params *params, int tilesize) |
1298 | { |
1299 | ds->tilesize = tilesize; |
1300 | } |
1301 | |
1302 | static float *game_colours(frontend *fe, int *ncolours) |
1303 | { |
1304 | float *ret = snewn(3 * NCOLOURS, float); |
1305 | |
1306 | frontend_default_colour(fe, &ret[COL_BACKGROUND * 3]); |
1307 | |
1308 | *ncolours = NCOLOURS; |
1309 | return ret; |
1310 | } |
1311 | |
1312 | static game_drawstate *game_new_drawstate(drawing *dr, game_state *state) |
1313 | { |
1314 | struct game_drawstate *ds = snew(struct game_drawstate); |
1315 | |
1316 | ds->tilesize = 0; |
1317 | ds->FIXME = 0; |
1318 | |
1319 | return ds; |
1320 | } |
1321 | |
1322 | static void game_free_drawstate(drawing *dr, game_drawstate *ds) |
1323 | { |
1324 | sfree(ds); |
1325 | } |
1326 | |
1327 | static void game_redraw(drawing *dr, game_drawstate *ds, game_state *oldstate, |
1328 | game_state *state, int dir, game_ui *ui, |
1329 | float animtime, float flashtime) |
1330 | { |
1331 | /* |
1332 | * The initial contents of the window are not guaranteed and |
1333 | * can vary with front ends. To be on the safe side, all games |
1334 | * should start by drawing a big background-colour rectangle |
1335 | * covering the whole window. |
1336 | */ |
1337 | draw_rect(dr, 0, 0, 10*ds->tilesize, 10*ds->tilesize, COL_BACKGROUND); |
1338 | } |
1339 | |
1340 | static float game_anim_length(game_state *oldstate, game_state *newstate, |
1341 | int dir, game_ui *ui) |
1342 | { |
1343 | return 0.0F; |
1344 | } |
1345 | |
1346 | static float game_flash_length(game_state *oldstate, game_state *newstate, |
1347 | int dir, game_ui *ui) |
1348 | { |
1349 | return 0.0F; |
1350 | } |
1351 | |
1352 | static int game_timing_state(game_state *state, game_ui *ui) |
1353 | { |
1354 | return TRUE; |
1355 | } |
1356 | |
1357 | static void game_print_size(game_params *params, float *x, float *y) |
1358 | { |
1359 | } |
1360 | |
1361 | static void game_print(drawing *dr, game_state *state, int tilesize) |
1362 | { |
1363 | } |
1364 | |
1365 | #ifdef COMBINED |
1366 | #define thegame pearl |
1367 | #endif |
1368 | |
1369 | const struct game thegame = { |
750037d7 |
1370 | "Pearl", NULL, NULL, |
f278dcf4 |
1371 | default_params, |
1372 | game_fetch_preset, |
1373 | decode_params, |
1374 | encode_params, |
1375 | free_params, |
1376 | dup_params, |
1377 | FALSE, game_configure, custom_params, |
1378 | validate_params, |
1379 | new_game_desc, |
1380 | validate_desc, |
1381 | new_game, |
1382 | dup_game, |
1383 | free_game, |
1384 | FALSE, solve_game, |
fa3abef5 |
1385 | FALSE, game_can_format_as_text_now, game_text_format, |
f278dcf4 |
1386 | new_ui, |
1387 | free_ui, |
1388 | encode_ui, |
1389 | decode_ui, |
1390 | game_changed_state, |
1391 | interpret_move, |
1392 | execute_move, |
1393 | 20 /* FIXME */, game_compute_size, game_set_size, |
1394 | game_colours, |
1395 | game_new_drawstate, |
1396 | game_free_drawstate, |
1397 | game_redraw, |
1398 | game_anim_length, |
1399 | game_flash_length, |
1400 | FALSE, FALSE, game_print_size, game_print, |
1401 | FALSE, /* wants_statusbar */ |
1402 | FALSE, game_timing_state, |
1403 | 0, /* flags */ |
1404 | }; |