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/pattern.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/pattern.c')
-rw-r--r-- | apps/plugins/puzzles/src/pattern.c | 2255 |
1 files changed, 2255 insertions, 0 deletions
diff --git a/apps/plugins/puzzles/src/pattern.c b/apps/plugins/puzzles/src/pattern.c new file mode 100644 index 0000000000..9a74e55318 --- /dev/null +++ b/apps/plugins/puzzles/src/pattern.c | |||
@@ -0,0 +1,2255 @@ | |||
1 | /* | ||
2 | * pattern.c: the pattern-reconstruction game known as `nonograms'. | ||
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 | enum { | ||
15 | COL_BACKGROUND, | ||
16 | COL_EMPTY, | ||
17 | COL_FULL, | ||
18 | COL_TEXT, | ||
19 | COL_UNKNOWN, | ||
20 | COL_GRID, | ||
21 | COL_CURSOR, | ||
22 | COL_ERROR, | ||
23 | NCOLOURS | ||
24 | }; | ||
25 | |||
26 | #define PREFERRED_TILE_SIZE 24 | ||
27 | #define TILE_SIZE (ds->tilesize) | ||
28 | #define BORDER (3 * TILE_SIZE / 4) | ||
29 | #define TLBORDER(d) ( (d) / 5 + 2 ) | ||
30 | #define GUTTER (TILE_SIZE / 2) | ||
31 | |||
32 | #define FROMCOORD(d, x) \ | ||
33 | ( ((x) - (BORDER + GUTTER + TILE_SIZE * TLBORDER(d))) / TILE_SIZE ) | ||
34 | |||
35 | #define SIZE(d) (2*BORDER + GUTTER + TILE_SIZE * (TLBORDER(d) + (d))) | ||
36 | #define GETTILESIZE(d, w) ((double)w / (2.0 + (double)TLBORDER(d) + (double)(d))) | ||
37 | |||
38 | #define TOCOORD(d, x) (BORDER + GUTTER + TILE_SIZE * (TLBORDER(d) + (x))) | ||
39 | |||
40 | struct game_params { | ||
41 | int w, h; | ||
42 | }; | ||
43 | |||
44 | #define GRID_UNKNOWN 2 | ||
45 | #define GRID_FULL 1 | ||
46 | #define GRID_EMPTY 0 | ||
47 | |||
48 | typedef struct game_state_common { | ||
49 | /* Parts of the game state that don't change during play. */ | ||
50 | int w, h; | ||
51 | int rowsize; | ||
52 | int *rowdata, *rowlen; | ||
53 | unsigned char *immutable; | ||
54 | int refcount; | ||
55 | } game_state_common; | ||
56 | |||
57 | struct game_state { | ||
58 | game_state_common *common; | ||
59 | unsigned char *grid; | ||
60 | int completed, cheated; | ||
61 | }; | ||
62 | |||
63 | #define FLASH_TIME 0.13F | ||
64 | |||
65 | static game_params *default_params(void) | ||
66 | { | ||
67 | game_params *ret = snew(game_params); | ||
68 | |||
69 | ret->w = ret->h = 15; | ||
70 | |||
71 | return ret; | ||
72 | } | ||
73 | |||
74 | static const struct game_params pattern_presets[] = { | ||
75 | {10, 10}, | ||
76 | {15, 15}, | ||
77 | {20, 20}, | ||
78 | #ifndef SLOW_SYSTEM | ||
79 | {25, 25}, | ||
80 | {30, 30}, | ||
81 | #endif | ||
82 | }; | ||
83 | |||
84 | static int game_fetch_preset(int i, char **name, game_params **params) | ||
85 | { | ||
86 | game_params *ret; | ||
87 | char str[80]; | ||
88 | |||
89 | if (i < 0 || i >= lenof(pattern_presets)) | ||
90 | return FALSE; | ||
91 | |||
92 | ret = snew(game_params); | ||
93 | *ret = pattern_presets[i]; | ||
94 | |||
95 | sprintf(str, "%dx%d", ret->w, ret->h); | ||
96 | |||
97 | *name = dupstr(str); | ||
98 | *params = ret; | ||
99 | return TRUE; | ||
100 | } | ||
101 | |||
102 | static void free_params(game_params *params) | ||
103 | { | ||
104 | sfree(params); | ||
105 | } | ||
106 | |||
107 | static game_params *dup_params(const game_params *params) | ||
108 | { | ||
109 | game_params *ret = snew(game_params); | ||
110 | *ret = *params; /* structure copy */ | ||
111 | return ret; | ||
112 | } | ||
113 | |||
114 | static void decode_params(game_params *ret, char const *string) | ||
115 | { | ||
116 | char const *p = string; | ||
117 | |||
118 | ret->w = atoi(p); | ||
119 | while (*p && isdigit((unsigned char)*p)) p++; | ||
120 | if (*p == 'x') { | ||
121 | p++; | ||
122 | ret->h = atoi(p); | ||
123 | while (*p && isdigit((unsigned char)*p)) p++; | ||
124 | } else { | ||
125 | ret->h = ret->w; | ||
126 | } | ||
127 | } | ||
128 | |||
129 | static char *encode_params(const game_params *params, int full) | ||
130 | { | ||
131 | char ret[400]; | ||
132 | int len; | ||
133 | |||
134 | len = sprintf(ret, "%dx%d", params->w, params->h); | ||
135 | assert(len < lenof(ret)); | ||
136 | ret[len] = '\0'; | ||
137 | |||
138 | return dupstr(ret); | ||
139 | } | ||
140 | |||
141 | static config_item *game_configure(const game_params *params) | ||
142 | { | ||
143 | config_item *ret; | ||
144 | char buf[80]; | ||
145 | |||
146 | ret = snewn(3, config_item); | ||
147 | |||
148 | ret[0].name = "Width"; | ||
149 | ret[0].type = C_STRING; | ||
150 | sprintf(buf, "%d", params->w); | ||
151 | ret[0].sval = dupstr(buf); | ||
152 | ret[0].ival = 0; | ||
153 | |||
154 | ret[1].name = "Height"; | ||
155 | ret[1].type = C_STRING; | ||
156 | sprintf(buf, "%d", params->h); | ||
157 | ret[1].sval = dupstr(buf); | ||
158 | ret[1].ival = 0; | ||
159 | |||
160 | ret[2].name = NULL; | ||
161 | ret[2].type = C_END; | ||
162 | ret[2].sval = NULL; | ||
163 | ret[2].ival = 0; | ||
164 | |||
165 | return ret; | ||
166 | } | ||
167 | |||
168 | static game_params *custom_params(const config_item *cfg) | ||
169 | { | ||
170 | game_params *ret = snew(game_params); | ||
171 | |||
172 | ret->w = atoi(cfg[0].sval); | ||
173 | ret->h = atoi(cfg[1].sval); | ||
174 | |||
175 | return ret; | ||
176 | } | ||
177 | |||
178 | static char *validate_params(const game_params *params, int full) | ||
179 | { | ||
180 | if (params->w <= 0 || params->h <= 0) | ||
181 | return "Width and height must both be greater than zero"; | ||
182 | return NULL; | ||
183 | } | ||
184 | |||
185 | /* ---------------------------------------------------------------------- | ||
186 | * Puzzle generation code. | ||
187 | * | ||
188 | * For this particular puzzle, it seemed important to me to ensure | ||
189 | * a unique solution. I do this the brute-force way, by having a | ||
190 | * solver algorithm alongside the generator, and repeatedly | ||
191 | * generating a random grid until I find one whose solution is | ||
192 | * unique. It turns out that this isn't too onerous on a modern PC | ||
193 | * provided you keep grid size below around 30. Any offers of | ||
194 | * better algorithms, however, will be very gratefully received. | ||
195 | * | ||
196 | * Another annoyance of this approach is that it limits the | ||
197 | * available puzzles to those solvable by the algorithm I've used. | ||
198 | * My algorithm only ever considers a single row or column at any | ||
199 | * one time, which means it's incapable of solving the following | ||
200 | * difficult example (found by Bella Image around 1995/6, when she | ||
201 | * and I were both doing maths degrees): | ||
202 | * | ||
203 | * 2 1 2 1 | ||
204 | * | ||
205 | * +--+--+--+--+ | ||
206 | * 1 1 | | | | | | ||
207 | * +--+--+--+--+ | ||
208 | * 2 | | | | | | ||
209 | * +--+--+--+--+ | ||
210 | * 1 | | | | | | ||
211 | * +--+--+--+--+ | ||
212 | * 1 | | | | | | ||
213 | * +--+--+--+--+ | ||
214 | * | ||
215 | * Obviously this cannot be solved by a one-row-or-column-at-a-time | ||
216 | * algorithm (it would require at least one row or column reading | ||
217 | * `2 1', `1 2', `3' or `4' to get started). However, it can be | ||
218 | * proved to have a unique solution: if the top left square were | ||
219 | * empty, then the only option for the top row would be to fill the | ||
220 | * two squares in the 1 columns, which would imply the squares | ||
221 | * below those were empty, leaving no place for the 2 in the second | ||
222 | * row. Contradiction. Hence the top left square is full, and the | ||
223 | * unique solution follows easily from that starting point. | ||
224 | * | ||
225 | * (The game ID for this puzzle is 4x4:2/1/2/1/1.1/2/1/1 , in case | ||
226 | * it's useful to anyone.) | ||
227 | */ | ||
228 | |||
229 | #ifndef STANDALONE_PICTURE_GENERATOR | ||
230 | static int float_compare(const void *av, const void *bv) | ||
231 | { | ||
232 | const float *a = (const float *)av; | ||
233 | const float *b = (const float *)bv; | ||
234 | if (*a < *b) | ||
235 | return -1; | ||
236 | else if (*a > *b) | ||
237 | return +1; | ||
238 | else | ||
239 | return 0; | ||
240 | } | ||
241 | |||
242 | static void generate(random_state *rs, int w, int h, unsigned char *retgrid) | ||
243 | { | ||
244 | float *fgrid; | ||
245 | float *fgrid2; | ||
246 | int step, i, j; | ||
247 | float threshold; | ||
248 | |||
249 | fgrid = snewn(w*h, float); | ||
250 | |||
251 | for (i = 0; i < h; i++) { | ||
252 | for (j = 0; j < w; j++) { | ||
253 | fgrid[i*w+j] = random_upto(rs, 100000000UL) / 100000000.F; | ||
254 | } | ||
255 | } | ||
256 | |||
257 | /* | ||
258 | * The above gives a completely random splattering of black and | ||
259 | * white cells. We want to gently bias this in favour of _some_ | ||
260 | * reasonably thick areas of white and black, while retaining | ||
261 | * some randomness and fine detail. | ||
262 | * | ||
263 | * So we evolve the starting grid using a cellular automaton. | ||
264 | * Currently, I'm doing something very simple indeed, which is | ||
265 | * to set each square to the average of the surrounding nine | ||
266 | * cells (or the average of fewer, if we're on a corner). | ||
267 | */ | ||
268 | for (step = 0; step < 1; step++) { | ||
269 | fgrid2 = snewn(w*h, float); | ||
270 | |||
271 | for (i = 0; i < h; i++) { | ||
272 | for (j = 0; j < w; j++) { | ||
273 | float sx, xbar; | ||
274 | int n, p, q; | ||
275 | |||
276 | /* | ||
277 | * Compute the average of the surrounding cells. | ||
278 | */ | ||
279 | n = 0; | ||
280 | sx = 0.F; | ||
281 | for (p = -1; p <= +1; p++) { | ||
282 | for (q = -1; q <= +1; q++) { | ||
283 | if (i+p < 0 || i+p >= h || j+q < 0 || j+q >= w) | ||
284 | continue; | ||
285 | /* | ||
286 | * An additional special case not mentioned | ||
287 | * above: if a grid dimension is 2xn then | ||
288 | * we do not average across that dimension | ||
289 | * at all. Otherwise a 2x2 grid would | ||
290 | * contain four identical squares. | ||
291 | */ | ||
292 | if ((h==2 && p!=0) || (w==2 && q!=0)) | ||
293 | continue; | ||
294 | n++; | ||
295 | sx += fgrid[(i+p)*w+(j+q)]; | ||
296 | } | ||
297 | } | ||
298 | xbar = sx / n; | ||
299 | |||
300 | fgrid2[i*w+j] = xbar; | ||
301 | } | ||
302 | } | ||
303 | |||
304 | sfree(fgrid); | ||
305 | fgrid = fgrid2; | ||
306 | } | ||
307 | |||
308 | fgrid2 = snewn(w*h, float); | ||
309 | memcpy(fgrid2, fgrid, w*h*sizeof(float)); | ||
310 | qsort(fgrid2, w*h, sizeof(float), float_compare); | ||
311 | threshold = fgrid2[w*h/2]; | ||
312 | sfree(fgrid2); | ||
313 | |||
314 | for (i = 0; i < h; i++) { | ||
315 | for (j = 0; j < w; j++) { | ||
316 | retgrid[i*w+j] = (fgrid[i*w+j] >= threshold ? GRID_FULL : | ||
317 | GRID_EMPTY); | ||
318 | } | ||
319 | } | ||
320 | |||
321 | sfree(fgrid); | ||
322 | } | ||
323 | #endif | ||
324 | |||
325 | static int compute_rowdata(int *ret, unsigned char *start, int len, int step) | ||
326 | { | ||
327 | int i, n; | ||
328 | |||
329 | n = 0; | ||
330 | |||
331 | for (i = 0; i < len; i++) { | ||
332 | if (start[i*step] == GRID_FULL) { | ||
333 | int runlen = 1; | ||
334 | while (i+runlen < len && start[(i+runlen)*step] == GRID_FULL) | ||
335 | runlen++; | ||
336 | ret[n++] = runlen; | ||
337 | i += runlen; | ||
338 | } | ||
339 | |||
340 | if (i < len && start[i*step] == GRID_UNKNOWN) | ||
341 | return -1; | ||
342 | } | ||
343 | |||
344 | return n; | ||
345 | } | ||
346 | |||
347 | #define UNKNOWN 0 | ||
348 | #define BLOCK 1 | ||
349 | #define DOT 2 | ||
350 | #define STILL_UNKNOWN 3 | ||
351 | |||
352 | #ifdef STANDALONE_SOLVER | ||
353 | int verbose = FALSE; | ||
354 | #endif | ||
355 | |||
356 | static int do_recurse(unsigned char *known, unsigned char *deduced, | ||
357 | unsigned char *row, | ||
358 | unsigned char *minpos_done, unsigned char *maxpos_done, | ||
359 | unsigned char *minpos_ok, unsigned char *maxpos_ok, | ||
360 | int *data, int len, | ||
361 | int freespace, int ndone, int lowest) | ||
362 | { | ||
363 | int i, j, k; | ||
364 | |||
365 | |||
366 | /* This algorithm basically tries all possible ways the given rows of | ||
367 | * black blocks can be laid out in the row/column being examined. | ||
368 | * Special care is taken to avoid checking the tail of a row/column | ||
369 | * if the same conditions have already been checked during this recursion | ||
370 | * The algorithm also takes care to cut its losses as soon as an | ||
371 | * invalid (partial) solution is detected. | ||
372 | */ | ||
373 | if (data[ndone]) { | ||
374 | if (lowest >= minpos_done[ndone] && lowest <= maxpos_done[ndone]) { | ||
375 | if (lowest >= minpos_ok[ndone] && lowest <= maxpos_ok[ndone]) { | ||
376 | for (i=0; i<lowest; i++) | ||
377 | deduced[i] |= row[i]; | ||
378 | } | ||
379 | return lowest >= minpos_ok[ndone] && lowest <= maxpos_ok[ndone]; | ||
380 | } else { | ||
381 | if (lowest < minpos_done[ndone]) minpos_done[ndone] = lowest; | ||
382 | if (lowest > maxpos_done[ndone]) maxpos_done[ndone] = lowest; | ||
383 | } | ||
384 | for (i=0; i<=freespace; i++) { | ||
385 | j = lowest; | ||
386 | for (k=0; k<i; k++) { | ||
387 | if (known[j] == BLOCK) goto next_iter; | ||
388 | row[j++] = DOT; | ||
389 | } | ||
390 | for (k=0; k<data[ndone]; k++) { | ||
391 | if (known[j] == DOT) goto next_iter; | ||
392 | row[j++] = BLOCK; | ||
393 | } | ||
394 | if (j < len) { | ||
395 | if (known[j] == BLOCK) goto next_iter; | ||
396 | row[j++] = DOT; | ||
397 | } | ||
398 | if (do_recurse(known, deduced, row, minpos_done, maxpos_done, | ||
399 | minpos_ok, maxpos_ok, data, len, freespace-i, ndone+1, j)) { | ||
400 | if (lowest < minpos_ok[ndone]) minpos_ok[ndone] = lowest; | ||
401 | if (lowest + i > maxpos_ok[ndone]) maxpos_ok[ndone] = lowest + i; | ||
402 | if (lowest + i > maxpos_done[ndone]) maxpos_done[ndone] = lowest + i; | ||
403 | } | ||
404 | next_iter: | ||
405 | j++; | ||
406 | } | ||
407 | return lowest >= minpos_ok[ndone] && lowest <= maxpos_ok[ndone]; | ||
408 | } else { | ||
409 | for (i=lowest; i<len; i++) { | ||
410 | if (known[i] == BLOCK) return FALSE; | ||
411 | row[i] = DOT; | ||
412 | } | ||
413 | for (i=0; i<len; i++) | ||
414 | deduced[i] |= row[i]; | ||
415 | return TRUE; | ||
416 | } | ||
417 | } | ||
418 | |||
419 | |||
420 | static int do_row(unsigned char *known, unsigned char *deduced, | ||
421 | unsigned char *row, | ||
422 | unsigned char *minpos_done, unsigned char *maxpos_done, | ||
423 | unsigned char *minpos_ok, unsigned char *maxpos_ok, | ||
424 | unsigned char *start, int len, int step, int *data, | ||
425 | unsigned int *changed | ||
426 | #ifdef STANDALONE_SOLVER | ||
427 | , const char *rowcol, int index, int cluewid | ||
428 | #endif | ||
429 | ) | ||
430 | { | ||
431 | int rowlen, i, freespace, done_any; | ||
432 | |||
433 | freespace = len+1; | ||
434 | for (rowlen = 0; data[rowlen]; rowlen++) { | ||
435 | minpos_done[rowlen] = minpos_ok[rowlen] = len - 1; | ||
436 | maxpos_done[rowlen] = maxpos_ok[rowlen] = 0; | ||
437 | freespace -= data[rowlen]+1; | ||
438 | } | ||
439 | |||
440 | for (i = 0; i < len; i++) { | ||
441 | known[i] = start[i*step]; | ||
442 | deduced[i] = 0; | ||
443 | } | ||
444 | for (i = len - 1; i >= 0 && known[i] == DOT; i--) | ||
445 | freespace--; | ||
446 | |||
447 | if (rowlen == 0) { | ||
448 | memset(deduced, DOT, len); | ||
449 | } else { | ||
450 | do_recurse(known, deduced, row, minpos_done, maxpos_done, minpos_ok, | ||
451 | maxpos_ok, data, len, freespace, 0, 0); | ||
452 | } | ||
453 | |||
454 | done_any = FALSE; | ||
455 | for (i=0; i<len; i++) | ||
456 | if (deduced[i] && deduced[i] != STILL_UNKNOWN && !known[i]) { | ||
457 | start[i*step] = deduced[i]; | ||
458 | if (changed) changed[i]++; | ||
459 | done_any = TRUE; | ||
460 | } | ||
461 | #ifdef STANDALONE_SOLVER | ||
462 | if (verbose && done_any) { | ||
463 | char buf[80]; | ||
464 | int thiscluewid; | ||
465 | printf("%s %2d: [", rowcol, index); | ||
466 | for (thiscluewid = -1, i = 0; data[i]; i++) | ||
467 | thiscluewid += sprintf(buf, " %d", data[i]); | ||
468 | printf("%*s", cluewid - thiscluewid, ""); | ||
469 | for (i = 0; data[i]; i++) | ||
470 | printf(" %d", data[i]); | ||
471 | printf(" ] "); | ||
472 | for (i = 0; i < len; i++) | ||
473 | putchar(known[i] == BLOCK ? '#' : | ||
474 | known[i] == DOT ? '.' : '?'); | ||
475 | printf(" -> "); | ||
476 | for (i = 0; i < len; i++) | ||
477 | putchar(start[i*step] == BLOCK ? '#' : | ||
478 | start[i*step] == DOT ? '.' : '?'); | ||
479 | putchar('\n'); | ||
480 | } | ||
481 | #endif | ||
482 | return done_any; | ||
483 | } | ||
484 | |||
485 | static int solve_puzzle(const game_state *state, unsigned char *grid, | ||
486 | int w, int h, | ||
487 | unsigned char *matrix, unsigned char *workspace, | ||
488 | unsigned int *changed_h, unsigned int *changed_w, | ||
489 | int *rowdata | ||
490 | #ifdef STANDALONE_SOLVER | ||
491 | , int cluewid | ||
492 | #else | ||
493 | , int dummy | ||
494 | #endif | ||
495 | ) | ||
496 | { | ||
497 | int i, j, ok, max; | ||
498 | int max_h, max_w; | ||
499 | |||
500 | assert((state!=NULL && state->common->rowdata!=NULL) ^ (grid!=NULL)); | ||
501 | |||
502 | max = max(w, h); | ||
503 | |||
504 | memset(matrix, 0, w*h); | ||
505 | if (state) { | ||
506 | for (i=0; i<w*h; i++) { | ||
507 | if (state->common->immutable[i]) | ||
508 | matrix[i] = state->grid[i]; | ||
509 | } | ||
510 | } | ||
511 | |||
512 | /* For each column, compute how many squares can be deduced | ||
513 | * from just the row-data and initial clues. | ||
514 | * Later, changed_* will hold how many squares were changed | ||
515 | * in every row/column in the previous iteration | ||
516 | * Changed_* is used to choose the next rows / cols to re-examine | ||
517 | */ | ||
518 | for (i=0; i<h; i++) { | ||
519 | int freespace, rowlen; | ||
520 | if (state && state->common->rowdata) { | ||
521 | memcpy(rowdata, state->common->rowdata + state->common->rowsize*(w+i), max*sizeof(int)); | ||
522 | rowlen = state->common->rowlen[w+i]; | ||
523 | } else { | ||
524 | rowlen = compute_rowdata(rowdata, grid+i*w, w, 1); | ||
525 | } | ||
526 | rowdata[rowlen] = 0; | ||
527 | if (rowlen == 0) { | ||
528 | changed_h[i] = w; | ||
529 | } else { | ||
530 | for (j=0, freespace=w+1; rowdata[j]; j++) | ||
531 | freespace -= rowdata[j] + 1; | ||
532 | for (j=0, changed_h[i]=0; rowdata[j]; j++) | ||
533 | if (rowdata[j] > freespace) | ||
534 | changed_h[i] += rowdata[j] - freespace; | ||
535 | } | ||
536 | for (j = 0; j < w; j++) | ||
537 | if (matrix[i*w+j]) | ||
538 | changed_h[i]++; | ||
539 | } | ||
540 | for (i=0,max_h=0; i<h; i++) | ||
541 | if (changed_h[i] > max_h) | ||
542 | max_h = changed_h[i]; | ||
543 | for (i=0; i<w; i++) { | ||
544 | int freespace, rowlen; | ||
545 | if (state && state->common->rowdata) { | ||
546 | memcpy(rowdata, state->common->rowdata + state->common->rowsize*i, max*sizeof(int)); | ||
547 | rowlen = state->common->rowlen[i]; | ||
548 | } else { | ||
549 | rowlen = compute_rowdata(rowdata, grid+i, h, w); | ||
550 | } | ||
551 | rowdata[rowlen] = 0; | ||
552 | if (rowlen == 0) { | ||
553 | changed_w[i] = h; | ||
554 | } else { | ||
555 | for (j=0, freespace=h+1; rowdata[j]; j++) | ||
556 | freespace -= rowdata[j] + 1; | ||
557 | for (j=0, changed_w[i]=0; rowdata[j]; j++) | ||
558 | if (rowdata[j] > freespace) | ||
559 | changed_w[i] += rowdata[j] - freespace; | ||
560 | } | ||
561 | for (j = 0; j < h; j++) | ||
562 | if (matrix[j*w+i]) | ||
563 | changed_w[i]++; | ||
564 | } | ||
565 | for (i=0,max_w=0; i<w; i++) | ||
566 | if (changed_w[i] > max_w) | ||
567 | max_w = changed_w[i]; | ||
568 | |||
569 | /* Solve the puzzle. | ||
570 | * Process rows/columns individually. Deductions involving more than one | ||
571 | * row and/or column at a time are not supported. | ||
572 | * Take care to only process rows/columns which have been changed since they | ||
573 | * were previously processed. | ||
574 | * Also, prioritize rows/columns which have had the most changes since their | ||
575 | * previous processing, as they promise the greatest benefit. | ||
576 | * Extremely rectangular grids (e.g. 10x20, 15x40, etc.) are not treated specially. | ||
577 | */ | ||
578 | do { | ||
579 | for (; max_h && max_h >= max_w; max_h--) { | ||
580 | for (i=0; i<h; i++) { | ||
581 | if (changed_h[i] >= max_h) { | ||
582 | if (state && state->common->rowdata) { | ||
583 | memcpy(rowdata, state->common->rowdata + state->common->rowsize*(w+i), max*sizeof(int)); | ||
584 | rowdata[state->common->rowlen[w+i]] = 0; | ||
585 | } else { | ||
586 | rowdata[compute_rowdata(rowdata, grid+i*w, w, 1)] = 0; | ||
587 | } | ||
588 | do_row(workspace, workspace+max, workspace+2*max, | ||
589 | workspace+3*max, workspace+4*max, | ||
590 | workspace+5*max, workspace+6*max, | ||
591 | matrix+i*w, w, 1, rowdata, changed_w | ||
592 | #ifdef STANDALONE_SOLVER | ||
593 | , "row", i+1, cluewid | ||
594 | #endif | ||
595 | ); | ||
596 | changed_h[i] = 0; | ||
597 | } | ||
598 | } | ||
599 | for (i=0,max_w=0; i<w; i++) | ||
600 | if (changed_w[i] > max_w) | ||
601 | max_w = changed_w[i]; | ||
602 | } | ||
603 | for (; max_w && max_w >= max_h; max_w--) { | ||
604 | for (i=0; i<w; i++) { | ||
605 | if (changed_w[i] >= max_w) { | ||
606 | if (state && state->common->rowdata) { | ||
607 | memcpy(rowdata, state->common->rowdata + state->common->rowsize*i, max*sizeof(int)); | ||
608 | rowdata[state->common->rowlen[i]] = 0; | ||
609 | } else { | ||
610 | rowdata[compute_rowdata(rowdata, grid+i, h, w)] = 0; | ||
611 | } | ||
612 | do_row(workspace, workspace+max, workspace+2*max, | ||
613 | workspace+3*max, workspace+4*max, | ||
614 | workspace+5*max, workspace+6*max, | ||
615 | matrix+i, h, w, rowdata, changed_h | ||
616 | #ifdef STANDALONE_SOLVER | ||
617 | , "col", i+1, cluewid | ||
618 | #endif | ||
619 | ); | ||
620 | changed_w[i] = 0; | ||
621 | } | ||
622 | } | ||
623 | for (i=0,max_h=0; i<h; i++) | ||
624 | if (changed_h[i] > max_h) | ||
625 | max_h = changed_h[i]; | ||
626 | } | ||
627 | } while (max_h>0 || max_w>0); | ||
628 | |||
629 | ok = TRUE; | ||
630 | for (i=0; i<h; i++) { | ||
631 | for (j=0; j<w; j++) { | ||
632 | if (matrix[i*w+j] == UNKNOWN) | ||
633 | ok = FALSE; | ||
634 | } | ||
635 | } | ||
636 | |||
637 | return ok; | ||
638 | } | ||
639 | |||
640 | #ifndef STANDALONE_PICTURE_GENERATOR | ||
641 | static unsigned char *generate_soluble(random_state *rs, int w, int h) | ||
642 | { | ||
643 | int i, j, ok, ntries, max; | ||
644 | unsigned char *grid, *matrix, *workspace; | ||
645 | unsigned int *changed_h, *changed_w; | ||
646 | int *rowdata; | ||
647 | |||
648 | max = max(w, h); | ||
649 | |||
650 | grid = snewn(w*h, unsigned char); | ||
651 | /* Allocate this here, to avoid having to reallocate it again for every geneerated grid */ | ||
652 | matrix = snewn(w*h, unsigned char); | ||
653 | workspace = snewn(max*7, unsigned char); | ||
654 | changed_h = snewn(max+1, unsigned int); | ||
655 | changed_w = snewn(max+1, unsigned int); | ||
656 | rowdata = snewn(max+1, int); | ||
657 | |||
658 | ntries = 0; | ||
659 | |||
660 | do { | ||
661 | ntries++; | ||
662 | |||
663 | generate(rs, w, h, grid); | ||
664 | |||
665 | /* | ||
666 | * The game is a bit too easy if any row or column is | ||
667 | * completely black or completely white. An exception is | ||
668 | * made for rows/columns that are under 3 squares, | ||
669 | * otherwise nothing will ever be successfully generated. | ||
670 | */ | ||
671 | ok = TRUE; | ||
672 | if (w > 2) { | ||
673 | for (i = 0; i < h; i++) { | ||
674 | int colours = 0; | ||
675 | for (j = 0; j < w; j++) | ||
676 | colours |= (grid[i*w+j] == GRID_FULL ? 2 : 1); | ||
677 | if (colours != 3) | ||
678 | ok = FALSE; | ||
679 | } | ||
680 | } | ||
681 | if (h > 2) { | ||
682 | for (j = 0; j < w; j++) { | ||
683 | int colours = 0; | ||
684 | for (i = 0; i < h; i++) | ||
685 | colours |= (grid[i*w+j] == GRID_FULL ? 2 : 1); | ||
686 | if (colours != 3) | ||
687 | ok = FALSE; | ||
688 | } | ||
689 | } | ||
690 | if (!ok) | ||
691 | continue; | ||
692 | |||
693 | ok = solve_puzzle(NULL, grid, w, h, matrix, workspace, | ||
694 | changed_h, changed_w, rowdata, 0); | ||
695 | } while (!ok); | ||
696 | |||
697 | sfree(matrix); | ||
698 | sfree(workspace); | ||
699 | sfree(changed_h); | ||
700 | sfree(changed_w); | ||
701 | sfree(rowdata); | ||
702 | return grid; | ||
703 | } | ||
704 | #endif | ||
705 | |||
706 | #ifdef STANDALONE_PICTURE_GENERATOR | ||
707 | unsigned char *picture; | ||
708 | #endif | ||
709 | |||
710 | static char *new_game_desc(const game_params *params, random_state *rs, | ||
711 | char **aux, int interactive) | ||
712 | { | ||
713 | unsigned char *grid; | ||
714 | int i, j, max, rowlen, *rowdata; | ||
715 | char intbuf[80], *desc; | ||
716 | int desclen, descpos; | ||
717 | #ifdef STANDALONE_PICTURE_GENERATOR | ||
718 | game_state *state; | ||
719 | int *index; | ||
720 | #endif | ||
721 | |||
722 | max = max(params->w, params->h); | ||
723 | |||
724 | #ifdef STANDALONE_PICTURE_GENERATOR | ||
725 | /* | ||
726 | * Fixed input picture. | ||
727 | */ | ||
728 | grid = snewn(params->w * params->h, unsigned char); | ||
729 | memcpy(grid, picture, params->w * params->h); | ||
730 | |||
731 | /* | ||
732 | * Now winnow the immutable square set as far as possible. | ||
733 | */ | ||
734 | state = snew(game_state); | ||
735 | state->grid = grid; | ||
736 | state->common = snew(game_state_common); | ||
737 | state->common->rowdata = NULL; | ||
738 | state->common->immutable = snewn(params->w * params->h, unsigned char); | ||
739 | memset(state->common->immutable, 1, params->w * params->h); | ||
740 | |||
741 | index = snewn(params->w * params->h, int); | ||
742 | for (i = 0; i < params->w * params->h; i++) | ||
743 | index[i] = i; | ||
744 | shuffle(index, params->w * params->h, sizeof(*index), rs); | ||
745 | |||
746 | { | ||
747 | unsigned char *matrix = snewn(params->w*params->h, unsigned char); | ||
748 | unsigned char *workspace = snewn(max*7, unsigned char); | ||
749 | unsigned int *changed_h = snewn(max+1, unsigned int); | ||
750 | unsigned int *changed_w = snewn(max+1, unsigned int); | ||
751 | int *rowdata = snewn(max+1, int); | ||
752 | for (i = 0; i < params->w * params->h; i++) { | ||
753 | state->common->immutable[index[i]] = 0; | ||
754 | if (!solve_puzzle(state, grid, params->w, params->h, | ||
755 | matrix, workspace, changed_h, changed_w, | ||
756 | rowdata, 0)) | ||
757 | state->common->immutable[index[i]] = 1; | ||
758 | } | ||
759 | sfree(workspace); | ||
760 | sfree(changed_h); | ||
761 | sfree(changed_w); | ||
762 | sfree(rowdata); | ||
763 | sfree(matrix); | ||
764 | } | ||
765 | #else | ||
766 | grid = generate_soluble(rs, params->w, params->h); | ||
767 | #endif | ||
768 | rowdata = snewn(max, int); | ||
769 | |||
770 | /* | ||
771 | * Save the solved game in aux. | ||
772 | */ | ||
773 | if (aux) { | ||
774 | char *ai = snewn(params->w * params->h + 2, char); | ||
775 | |||
776 | /* | ||
777 | * String format is exactly the same as a solve move, so we | ||
778 | * can just dupstr this in solve_game(). | ||
779 | */ | ||
780 | |||
781 | ai[0] = 'S'; | ||
782 | |||
783 | for (i = 0; i < params->w * params->h; i++) | ||
784 | ai[i+1] = grid[i] ? '1' : '0'; | ||
785 | |||
786 | ai[params->w * params->h + 1] = '\0'; | ||
787 | |||
788 | *aux = ai; | ||
789 | } | ||
790 | |||
791 | /* | ||
792 | * Seed is a slash-separated list of row contents; each row | ||
793 | * contents section is a dot-separated list of integers. Row | ||
794 | * contents are listed in the order (columns left to right, | ||
795 | * then rows top to bottom). | ||
796 | * | ||
797 | * Simplest way to handle memory allocation is to make two | ||
798 | * passes, first computing the seed size and then writing it | ||
799 | * out. | ||
800 | */ | ||
801 | desclen = 0; | ||
802 | for (i = 0; i < params->w + params->h; i++) { | ||
803 | if (i < params->w) | ||
804 | rowlen = compute_rowdata(rowdata, grid+i, params->h, params->w); | ||
805 | else | ||
806 | rowlen = compute_rowdata(rowdata, grid+(i-params->w)*params->w, | ||
807 | params->w, 1); | ||
808 | if (rowlen > 0) { | ||
809 | for (j = 0; j < rowlen; j++) { | ||
810 | desclen += 1 + sprintf(intbuf, "%d", rowdata[j]); | ||
811 | } | ||
812 | } else { | ||
813 | desclen++; | ||
814 | } | ||
815 | } | ||
816 | desc = snewn(desclen, char); | ||
817 | descpos = 0; | ||
818 | for (i = 0; i < params->w + params->h; i++) { | ||
819 | if (i < params->w) | ||
820 | rowlen = compute_rowdata(rowdata, grid+i, params->h, params->w); | ||
821 | else | ||
822 | rowlen = compute_rowdata(rowdata, grid+(i-params->w)*params->w, | ||
823 | params->w, 1); | ||
824 | if (rowlen > 0) { | ||
825 | for (j = 0; j < rowlen; j++) { | ||
826 | int len = sprintf(desc+descpos, "%d", rowdata[j]); | ||
827 | if (j+1 < rowlen) | ||
828 | desc[descpos + len] = '.'; | ||
829 | else | ||
830 | desc[descpos + len] = '/'; | ||
831 | descpos += len+1; | ||
832 | } | ||
833 | } else { | ||
834 | desc[descpos++] = '/'; | ||
835 | } | ||
836 | } | ||
837 | assert(descpos == desclen); | ||
838 | assert(desc[desclen-1] == '/'); | ||
839 | desc[desclen-1] = '\0'; | ||
840 | #ifdef STANDALONE_PICTURE_GENERATOR | ||
841 | for (i = 0; i < params->w * params->h; i++) | ||
842 | if (state->common->immutable[i]) | ||
843 | break; | ||
844 | if (i < params->w * params->h) { | ||
845 | /* | ||
846 | * At least one immutable square, so we need a suffix. | ||
847 | */ | ||
848 | int run; | ||
849 | |||
850 | desc = sresize(desc, desclen + params->w * params->h + 3, char); | ||
851 | desc[descpos-1] = ','; | ||
852 | |||
853 | run = 0; | ||
854 | for (i = 0; i < params->w * params->h; i++) { | ||
855 | if (!state->common->immutable[i]) { | ||
856 | run++; | ||
857 | if (run == 25) { | ||
858 | desc[descpos++] = 'z'; | ||
859 | run = 0; | ||
860 | } | ||
861 | } else { | ||
862 | desc[descpos++] = run + (grid[i] == GRID_FULL ? 'A' : 'a'); | ||
863 | run = 0; | ||
864 | } | ||
865 | } | ||
866 | if (run > 0) | ||
867 | desc[descpos++] = run + 'a'; | ||
868 | desc[descpos] = '\0'; | ||
869 | } | ||
870 | sfree(state->common->immutable); | ||
871 | sfree(state->common); | ||
872 | sfree(state); | ||
873 | #endif | ||
874 | sfree(rowdata); | ||
875 | sfree(grid); | ||
876 | return desc; | ||
877 | } | ||
878 | |||
879 | static char *validate_desc(const game_params *params, const char *desc) | ||
880 | { | ||
881 | int i, n, rowspace; | ||
882 | const char *p; | ||
883 | |||
884 | for (i = 0; i < params->w + params->h; i++) { | ||
885 | if (i < params->w) | ||
886 | rowspace = params->h + 1; | ||
887 | else | ||
888 | rowspace = params->w + 1; | ||
889 | |||
890 | if (*desc && isdigit((unsigned char)*desc)) { | ||
891 | do { | ||
892 | p = desc; | ||
893 | while (*desc && isdigit((unsigned char)*desc)) desc++; | ||
894 | n = atoi(p); | ||
895 | rowspace -= n+1; | ||
896 | |||
897 | if (rowspace < 0) { | ||
898 | if (i < params->w) | ||
899 | return "at least one column contains more numbers than will fit"; | ||
900 | else | ||
901 | return "at least one row contains more numbers than will fit"; | ||
902 | } | ||
903 | } while (*desc++ == '.'); | ||
904 | } else { | ||
905 | desc++; /* expect a slash immediately */ | ||
906 | } | ||
907 | |||
908 | if (desc[-1] == '/') { | ||
909 | if (i+1 == params->w + params->h) | ||
910 | return "too many row/column specifications"; | ||
911 | } else if (desc[-1] == '\0' || desc[-1] == ',') { | ||
912 | if (i+1 < params->w + params->h) | ||
913 | return "too few row/column specifications"; | ||
914 | } else | ||
915 | return "unrecognised character in game specification"; | ||
916 | } | ||
917 | |||
918 | if (desc[-1] == ',') { | ||
919 | /* | ||
920 | * Optional extra piece of game description which fills in | ||
921 | * some grid squares as extra clues. | ||
922 | */ | ||
923 | i = 0; | ||
924 | while (i < params->w * params->h) { | ||
925 | int c = (unsigned char)*desc++; | ||
926 | if ((c >= 'a' && c <= 'z') || | ||
927 | (c >= 'A' && c <= 'Z')) { | ||
928 | int len = tolower(c) - 'a'; | ||
929 | i += len; | ||
930 | if (len < 25 && i < params->w*params->h) | ||
931 | i++; | ||
932 | if (i > params->w * params->h) { | ||
933 | return "too much data in clue-squares section"; | ||
934 | } | ||
935 | } else if (!c) { | ||
936 | return "too little data in clue-squares section"; | ||
937 | } else { | ||
938 | return "unrecognised character in clue-squares section"; | ||
939 | } | ||
940 | } | ||
941 | if (*desc) { | ||
942 | return "too much data in clue-squares section"; | ||
943 | } | ||
944 | } | ||
945 | |||
946 | return NULL; | ||
947 | } | ||
948 | |||
949 | static game_state *new_game(midend *me, const game_params *params, | ||
950 | const char *desc) | ||
951 | { | ||
952 | int i; | ||
953 | const char *p; | ||
954 | game_state *state = snew(game_state); | ||
955 | |||
956 | state->common = snew(game_state_common); | ||
957 | state->common->refcount = 1; | ||
958 | |||
959 | state->common->w = params->w; | ||
960 | state->common->h = params->h; | ||
961 | |||
962 | state->grid = snewn(state->common->w * state->common->h, unsigned char); | ||
963 | memset(state->grid, GRID_UNKNOWN, state->common->w * state->common->h); | ||
964 | |||
965 | state->common->immutable = snewn(state->common->w * state->common->h, | ||
966 | unsigned char); | ||
967 | memset(state->common->immutable, 0, state->common->w * state->common->h); | ||
968 | |||
969 | state->common->rowsize = max(state->common->w, state->common->h); | ||
970 | state->common->rowdata = snewn(state->common->rowsize * (state->common->w + state->common->h), int); | ||
971 | state->common->rowlen = snewn(state->common->w + state->common->h, int); | ||
972 | |||
973 | state->completed = state->cheated = FALSE; | ||
974 | |||
975 | for (i = 0; i < params->w + params->h; i++) { | ||
976 | state->common->rowlen[i] = 0; | ||
977 | if (*desc && isdigit((unsigned char)*desc)) { | ||
978 | do { | ||
979 | p = desc; | ||
980 | while (*desc && isdigit((unsigned char)*desc)) desc++; | ||
981 | state->common->rowdata[state->common->rowsize * i + state->common->rowlen[i]++] = | ||
982 | atoi(p); | ||
983 | } while (*desc++ == '.'); | ||
984 | } else { | ||
985 | desc++; /* expect a slash immediately */ | ||
986 | } | ||
987 | } | ||
988 | |||
989 | if (desc[-1] == ',') { | ||
990 | /* | ||
991 | * Optional extra piece of game description which fills in | ||
992 | * some grid squares as extra clues. | ||
993 | */ | ||
994 | i = 0; | ||
995 | while (i < params->w * params->h) { | ||
996 | int c = (unsigned char)*desc++; | ||
997 | int full = isupper(c), len = tolower(c) - 'a'; | ||
998 | i += len; | ||
999 | if (len < 25 && i < params->w*params->h) { | ||
1000 | state->grid[i] = full ? GRID_FULL : GRID_EMPTY; | ||
1001 | state->common->immutable[i] = TRUE; | ||
1002 | i++; | ||
1003 | } | ||
1004 | } | ||
1005 | } | ||
1006 | |||
1007 | return state; | ||
1008 | } | ||
1009 | |||
1010 | static game_state *dup_game(const game_state *state) | ||
1011 | { | ||
1012 | game_state *ret = snew(game_state); | ||
1013 | |||
1014 | ret->common = state->common; | ||
1015 | ret->common->refcount++; | ||
1016 | |||
1017 | ret->grid = snewn(ret->common->w * ret->common->h, unsigned char); | ||
1018 | memcpy(ret->grid, state->grid, ret->common->w * ret->common->h); | ||
1019 | |||
1020 | ret->completed = state->completed; | ||
1021 | ret->cheated = state->cheated; | ||
1022 | |||
1023 | return ret; | ||
1024 | } | ||
1025 | |||
1026 | static void free_game(game_state *state) | ||
1027 | { | ||
1028 | if (--state->common->refcount == 0) { | ||
1029 | sfree(state->common->rowdata); | ||
1030 | sfree(state->common->rowlen); | ||
1031 | sfree(state->common->immutable); | ||
1032 | sfree(state->common); | ||
1033 | } | ||
1034 | sfree(state->grid); | ||
1035 | sfree(state); | ||
1036 | } | ||
1037 | |||
1038 | static char *solve_game(const game_state *state, const game_state *currstate, | ||
1039 | const char *ai, char **error) | ||
1040 | { | ||
1041 | unsigned char *matrix; | ||
1042 | int w = state->common->w, h = state->common->h; | ||
1043 | int i; | ||
1044 | char *ret; | ||
1045 | int max, ok; | ||
1046 | unsigned char *workspace; | ||
1047 | unsigned int *changed_h, *changed_w; | ||
1048 | int *rowdata; | ||
1049 | |||
1050 | /* | ||
1051 | * If we already have the solved state in ai, copy it out. | ||
1052 | */ | ||
1053 | if (ai) | ||
1054 | return dupstr(ai); | ||
1055 | |||
1056 | max = max(w, h); | ||
1057 | matrix = snewn(w*h, unsigned char); | ||
1058 | workspace = snewn(max*7, unsigned char); | ||
1059 | changed_h = snewn(max+1, unsigned int); | ||
1060 | changed_w = snewn(max+1, unsigned int); | ||
1061 | rowdata = snewn(max+1, int); | ||
1062 | |||
1063 | ok = solve_puzzle(state, NULL, w, h, matrix, workspace, | ||
1064 | changed_h, changed_w, rowdata, 0); | ||
1065 | |||
1066 | sfree(workspace); | ||
1067 | sfree(changed_h); | ||
1068 | sfree(changed_w); | ||
1069 | sfree(rowdata); | ||
1070 | |||
1071 | if (!ok) { | ||
1072 | sfree(matrix); | ||
1073 | *error = "Solving algorithm cannot complete this puzzle"; | ||
1074 | return NULL; | ||
1075 | } | ||
1076 | |||
1077 | ret = snewn(w*h+2, char); | ||
1078 | ret[0] = 'S'; | ||
1079 | for (i = 0; i < w*h; i++) { | ||
1080 | assert(matrix[i] == BLOCK || matrix[i] == DOT); | ||
1081 | ret[i+1] = (matrix[i] == BLOCK ? '1' : '0'); | ||
1082 | } | ||
1083 | ret[w*h+1] = '\0'; | ||
1084 | |||
1085 | sfree(matrix); | ||
1086 | |||
1087 | return ret; | ||
1088 | } | ||
1089 | |||
1090 | static int game_can_format_as_text_now(const game_params *params) | ||
1091 | { | ||
1092 | return TRUE; | ||
1093 | } | ||
1094 | |||
1095 | static char *game_text_format(const game_state *state) | ||
1096 | { | ||
1097 | int w = state->common->w, h = state->common->h, i, j; | ||
1098 | int left_gap = 0, top_gap = 0, ch = 2, cw = 1, limit = 1; | ||
1099 | |||
1100 | int len, topleft, lw, lh, gw, gh; /* {line,grid}_{width,height} */ | ||
1101 | char *board, *buf; | ||
1102 | |||
1103 | for (i = 0; i < w; ++i) { | ||
1104 | top_gap = max(top_gap, state->common->rowlen[i]); | ||
1105 | for (j = 0; j < state->common->rowlen[i]; ++j) | ||
1106 | while (state->common->rowdata[i*state->common->rowsize + j] >= limit) { | ||
1107 | ++cw; | ||
1108 | limit *= 10; | ||
1109 | } | ||
1110 | } | ||
1111 | for (i = 0; i < h; ++i) { | ||
1112 | int rowlen = 0, predecessors = FALSE; | ||
1113 | for (j = 0; j < state->common->rowlen[i+w]; ++j) { | ||
1114 | int copy = state->common->rowdata[(i+w)*state->common->rowsize + j]; | ||
1115 | rowlen += predecessors; | ||
1116 | predecessors = TRUE; | ||
1117 | do ++rowlen; while (copy /= 10); | ||
1118 | } | ||
1119 | left_gap = max(left_gap, rowlen); | ||
1120 | } | ||
1121 | |||
1122 | cw = max(cw, 3); | ||
1123 | |||
1124 | gw = w*cw + 2; | ||
1125 | gh = h*ch + 1; | ||
1126 | lw = gw + left_gap; | ||
1127 | lh = gh + top_gap; | ||
1128 | len = lw * lh; | ||
1129 | topleft = lw * top_gap + left_gap; | ||
1130 | |||
1131 | board = snewn(len + 1, char); | ||
1132 | sprintf(board, "%*s\n", len - 2, ""); | ||
1133 | |||
1134 | for (i = 0; i < lh; ++i) { | ||
1135 | board[lw - 1 + i*lw] = '\n'; | ||
1136 | if (i < top_gap) continue; | ||
1137 | board[lw - 2 + i*lw] = ((i - top_gap) % ch ? '|' : '+'); | ||
1138 | } | ||
1139 | |||
1140 | for (i = 0; i < w; ++i) { | ||
1141 | for (j = 0; j < state->common->rowlen[i]; ++j) { | ||
1142 | int cell = topleft + i*cw + 1 + lw*(j - state->common->rowlen[i]); | ||
1143 | int nch = sprintf(board + cell, "%*d", cw - 1, | ||
1144 | state->common->rowdata[i*state->common->rowsize + j]); | ||
1145 | board[cell + nch] = ' '; /* de-NUL-ify */ | ||
1146 | } | ||
1147 | } | ||
1148 | |||
1149 | buf = snewn(left_gap, char); | ||
1150 | for (i = 0; i < h; ++i) { | ||
1151 | char *p = buf, *start = board + top_gap*lw + left_gap + (i*ch+1)*lw; | ||
1152 | for (j = 0; j < state->common->rowlen[i+w]; ++j) { | ||
1153 | if (p > buf) *p++ = ' '; | ||
1154 | p += sprintf(p, "%d", state->common->rowdata[(i+w)*state->common->rowsize + j]); | ||
1155 | } | ||
1156 | memcpy(start - (p - buf), buf, p - buf); | ||
1157 | } | ||
1158 | |||
1159 | for (i = 0; i < w; ++i) { | ||
1160 | for (j = 0; j < h; ++j) { | ||
1161 | int cell = topleft + i*cw + j*ch*lw; | ||
1162 | int center = cell + cw/2 + (ch/2)*lw; | ||
1163 | int dx, dy; | ||
1164 | board[cell] = 0 ? center : '+'; | ||
1165 | for (dx = 1; dx < cw; ++dx) board[cell + dx] = '-'; | ||
1166 | for (dy = 1; dy < ch; ++dy) board[cell + dy*lw] = '|'; | ||
1167 | if (state->grid[i*w+j] == GRID_UNKNOWN) continue; | ||
1168 | for (dx = 1; dx < cw; ++dx) | ||
1169 | for (dy = 1; dy < ch; ++dy) | ||
1170 | board[cell + dx + dy*lw] = | ||
1171 | state->grid[i*w+j] == GRID_FULL ? '#' : '.'; | ||
1172 | } | ||
1173 | } | ||
1174 | |||
1175 | memcpy(board + topleft + h*ch*lw, board + topleft, gw - 1); | ||
1176 | |||
1177 | sfree(buf); | ||
1178 | |||
1179 | return board; | ||
1180 | } | ||
1181 | |||
1182 | struct game_ui { | ||
1183 | int dragging; | ||
1184 | int drag_start_x; | ||
1185 | int drag_start_y; | ||
1186 | int drag_end_x; | ||
1187 | int drag_end_y; | ||
1188 | int drag, release, state; | ||
1189 | int cur_x, cur_y, cur_visible; | ||
1190 | }; | ||
1191 | |||
1192 | static game_ui *new_ui(const game_state *state) | ||
1193 | { | ||
1194 | game_ui *ret; | ||
1195 | |||
1196 | ret = snew(game_ui); | ||
1197 | ret->dragging = FALSE; | ||
1198 | ret->cur_x = ret->cur_y = ret->cur_visible = 0; | ||
1199 | |||
1200 | return ret; | ||
1201 | } | ||
1202 | |||
1203 | static void free_ui(game_ui *ui) | ||
1204 | { | ||
1205 | sfree(ui); | ||
1206 | } | ||
1207 | |||
1208 | static char *encode_ui(const game_ui *ui) | ||
1209 | { | ||
1210 | return NULL; | ||
1211 | } | ||
1212 | |||
1213 | static void decode_ui(game_ui *ui, const char *encoding) | ||
1214 | { | ||
1215 | } | ||
1216 | |||
1217 | static void game_changed_state(game_ui *ui, const game_state *oldstate, | ||
1218 | const game_state *newstate) | ||
1219 | { | ||
1220 | } | ||
1221 | |||
1222 | struct game_drawstate { | ||
1223 | int started; | ||
1224 | int w, h; | ||
1225 | int tilesize; | ||
1226 | unsigned char *visible, *numcolours; | ||
1227 | int cur_x, cur_y; | ||
1228 | }; | ||
1229 | |||
1230 | static char *interpret_move(const game_state *state, game_ui *ui, | ||
1231 | const game_drawstate *ds, | ||
1232 | int x, int y, int button) | ||
1233 | { | ||
1234 | int control = button & MOD_CTRL, shift = button & MOD_SHFT; | ||
1235 | button &= ~MOD_MASK; | ||
1236 | |||
1237 | x = FROMCOORD(state->common->w, x); | ||
1238 | y = FROMCOORD(state->common->h, y); | ||
1239 | |||
1240 | if (x >= 0 && x < state->common->w && y >= 0 && y < state->common->h && | ||
1241 | (button == LEFT_BUTTON || button == RIGHT_BUTTON || | ||
1242 | button == MIDDLE_BUTTON)) { | ||
1243 | #ifdef STYLUS_BASED | ||
1244 | int currstate = state->grid[y * state->common->w + x]; | ||
1245 | #endif | ||
1246 | |||
1247 | ui->dragging = TRUE; | ||
1248 | |||
1249 | if (button == LEFT_BUTTON) { | ||
1250 | ui->drag = LEFT_DRAG; | ||
1251 | ui->release = LEFT_RELEASE; | ||
1252 | #ifdef STYLUS_BASED | ||
1253 | ui->state = (currstate + 2) % 3; /* FULL -> EMPTY -> UNKNOWN */ | ||
1254 | #else | ||
1255 | ui->state = GRID_FULL; | ||
1256 | #endif | ||
1257 | } else if (button == RIGHT_BUTTON) { | ||
1258 | ui->drag = RIGHT_DRAG; | ||
1259 | ui->release = RIGHT_RELEASE; | ||
1260 | #ifdef STYLUS_BASED | ||
1261 | ui->state = (currstate + 1) % 3; /* EMPTY -> FULL -> UNKNOWN */ | ||
1262 | #else | ||
1263 | ui->state = GRID_EMPTY; | ||
1264 | #endif | ||
1265 | } else /* if (button == MIDDLE_BUTTON) */ { | ||
1266 | ui->drag = MIDDLE_DRAG; | ||
1267 | ui->release = MIDDLE_RELEASE; | ||
1268 | ui->state = GRID_UNKNOWN; | ||
1269 | } | ||
1270 | |||
1271 | ui->drag_start_x = ui->drag_end_x = x; | ||
1272 | ui->drag_start_y = ui->drag_end_y = y; | ||
1273 | ui->cur_visible = 0; | ||
1274 | |||
1275 | return ""; /* UI activity occurred */ | ||
1276 | } | ||
1277 | |||
1278 | if (ui->dragging && button == ui->drag) { | ||
1279 | /* | ||
1280 | * There doesn't seem much point in allowing a rectangle | ||
1281 | * drag; people will generally only want to drag a single | ||
1282 | * horizontal or vertical line, so we make that easy by | ||
1283 | * snapping to it. | ||
1284 | * | ||
1285 | * Exception: if we're _middle_-button dragging to tag | ||
1286 | * things as UNKNOWN, we may well want to trash an entire | ||
1287 | * area and start over! | ||
1288 | */ | ||
1289 | if (ui->state != GRID_UNKNOWN) { | ||
1290 | if (abs(x - ui->drag_start_x) > abs(y - ui->drag_start_y)) | ||
1291 | y = ui->drag_start_y; | ||
1292 | else | ||
1293 | x = ui->drag_start_x; | ||
1294 | } | ||
1295 | |||
1296 | if (x < 0) x = 0; | ||
1297 | if (y < 0) y = 0; | ||
1298 | if (x >= state->common->w) x = state->common->w - 1; | ||
1299 | if (y >= state->common->h) y = state->common->h - 1; | ||
1300 | |||
1301 | ui->drag_end_x = x; | ||
1302 | ui->drag_end_y = y; | ||
1303 | |||
1304 | return ""; /* UI activity occurred */ | ||
1305 | } | ||
1306 | |||
1307 | if (ui->dragging && button == ui->release) { | ||
1308 | int x1, x2, y1, y2, xx, yy; | ||
1309 | int move_needed = FALSE; | ||
1310 | |||
1311 | x1 = min(ui->drag_start_x, ui->drag_end_x); | ||
1312 | x2 = max(ui->drag_start_x, ui->drag_end_x); | ||
1313 | y1 = min(ui->drag_start_y, ui->drag_end_y); | ||
1314 | y2 = max(ui->drag_start_y, ui->drag_end_y); | ||
1315 | |||
1316 | for (yy = y1; yy <= y2; yy++) | ||
1317 | for (xx = x1; xx <= x2; xx++) | ||
1318 | if (!state->common->immutable[yy * state->common->w + xx] && | ||
1319 | state->grid[yy * state->common->w + xx] != ui->state) | ||
1320 | move_needed = TRUE; | ||
1321 | |||
1322 | ui->dragging = FALSE; | ||
1323 | |||
1324 | if (move_needed) { | ||
1325 | char buf[80]; | ||
1326 | sprintf(buf, "%c%d,%d,%d,%d", | ||
1327 | (char)(ui->state == GRID_FULL ? 'F' : | ||
1328 | ui->state == GRID_EMPTY ? 'E' : 'U'), | ||
1329 | x1, y1, x2-x1+1, y2-y1+1); | ||
1330 | return dupstr(buf); | ||
1331 | } else | ||
1332 | return ""; /* UI activity occurred */ | ||
1333 | } | ||
1334 | |||
1335 | if (IS_CURSOR_MOVE(button)) { | ||
1336 | int x = ui->cur_x, y = ui->cur_y, newstate; | ||
1337 | char buf[80]; | ||
1338 | move_cursor(button, &ui->cur_x, &ui->cur_y, state->common->w, state->common->h, 0); | ||
1339 | ui->cur_visible = 1; | ||
1340 | if (!control && !shift) return ""; | ||
1341 | |||
1342 | newstate = control ? shift ? GRID_UNKNOWN : GRID_FULL : GRID_EMPTY; | ||
1343 | if (state->grid[y * state->common->w + x] == newstate && | ||
1344 | state->grid[ui->cur_y * state->common->w + ui->cur_x] == newstate) | ||
1345 | return ""; | ||
1346 | |||
1347 | sprintf(buf, "%c%d,%d,%d,%d", control ? shift ? 'U' : 'F' : 'E', | ||
1348 | min(x, ui->cur_x), min(y, ui->cur_y), | ||
1349 | abs(x - ui->cur_x) + 1, abs(y - ui->cur_y) + 1); | ||
1350 | return dupstr(buf); | ||
1351 | } | ||
1352 | |||
1353 | if (IS_CURSOR_SELECT(button)) { | ||
1354 | int currstate = state->grid[ui->cur_y * state->common->w + ui->cur_x]; | ||
1355 | int newstate; | ||
1356 | char buf[80]; | ||
1357 | |||
1358 | if (!ui->cur_visible) { | ||
1359 | ui->cur_visible = 1; | ||
1360 | return ""; | ||
1361 | } | ||
1362 | |||
1363 | if (button == CURSOR_SELECT2) | ||
1364 | newstate = currstate == GRID_UNKNOWN ? GRID_EMPTY : | ||
1365 | currstate == GRID_EMPTY ? GRID_FULL : GRID_UNKNOWN; | ||
1366 | else | ||
1367 | newstate = currstate == GRID_UNKNOWN ? GRID_FULL : | ||
1368 | currstate == GRID_FULL ? GRID_EMPTY : GRID_UNKNOWN; | ||
1369 | |||
1370 | sprintf(buf, "%c%d,%d,%d,%d", | ||
1371 | (char)(newstate == GRID_FULL ? 'F' : | ||
1372 | newstate == GRID_EMPTY ? 'E' : 'U'), | ||
1373 | ui->cur_x, ui->cur_y, 1, 1); | ||
1374 | return dupstr(buf); | ||
1375 | } | ||
1376 | |||
1377 | return NULL; | ||
1378 | } | ||
1379 | |||
1380 | static game_state *execute_move(const game_state *from, const char *move) | ||
1381 | { | ||
1382 | game_state *ret; | ||
1383 | int x1, x2, y1, y2, xx, yy; | ||
1384 | int val; | ||
1385 | |||
1386 | if (move[0] == 'S' && | ||
1387 | strlen(move) == from->common->w * from->common->h + 1) { | ||
1388 | int i; | ||
1389 | |||
1390 | ret = dup_game(from); | ||
1391 | |||
1392 | for (i = 0; i < ret->common->w * ret->common->h; i++) | ||
1393 | ret->grid[i] = (move[i+1] == '1' ? GRID_FULL : GRID_EMPTY); | ||
1394 | |||
1395 | ret->completed = ret->cheated = TRUE; | ||
1396 | |||
1397 | return ret; | ||
1398 | } else if ((move[0] == 'F' || move[0] == 'E' || move[0] == 'U') && | ||
1399 | sscanf(move+1, "%d,%d,%d,%d", &x1, &y1, &x2, &y2) == 4 && | ||
1400 | x1 >= 0 && x2 >= 0 && x1+x2 <= from->common->w && | ||
1401 | y1 >= 0 && y2 >= 0 && y1+y2 <= from->common->h) { | ||
1402 | |||
1403 | x2 += x1; | ||
1404 | y2 += y1; | ||
1405 | val = (move[0] == 'F' ? GRID_FULL : | ||
1406 | move[0] == 'E' ? GRID_EMPTY : GRID_UNKNOWN); | ||
1407 | |||
1408 | ret = dup_game(from); | ||
1409 | for (yy = y1; yy < y2; yy++) | ||
1410 | for (xx = x1; xx < x2; xx++) | ||
1411 | if (!ret->common->immutable[yy * ret->common->w + xx]) | ||
1412 | ret->grid[yy * ret->common->w + xx] = val; | ||
1413 | |||
1414 | /* | ||
1415 | * An actual change, so check to see if we've completed the | ||
1416 | * game. | ||
1417 | */ | ||
1418 | if (!ret->completed) { | ||
1419 | int *rowdata = snewn(ret->common->rowsize, int); | ||
1420 | int i, len; | ||
1421 | |||
1422 | ret->completed = TRUE; | ||
1423 | |||
1424 | for (i=0; i<ret->common->w; i++) { | ||
1425 | len = compute_rowdata(rowdata, ret->grid+i, | ||
1426 | ret->common->h, ret->common->w); | ||
1427 | if (len != ret->common->rowlen[i] || | ||
1428 | memcmp(ret->common->rowdata+i*ret->common->rowsize, | ||
1429 | rowdata, len * sizeof(int))) { | ||
1430 | ret->completed = FALSE; | ||
1431 | break; | ||
1432 | } | ||
1433 | } | ||
1434 | for (i=0; i<ret->common->h; i++) { | ||
1435 | len = compute_rowdata(rowdata, ret->grid+i*ret->common->w, | ||
1436 | ret->common->w, 1); | ||
1437 | if (len != ret->common->rowlen[i+ret->common->w] || | ||
1438 | memcmp(ret->common->rowdata + | ||
1439 | (i+ret->common->w)*ret->common->rowsize, | ||
1440 | rowdata, len * sizeof(int))) { | ||
1441 | ret->completed = FALSE; | ||
1442 | break; | ||
1443 | } | ||
1444 | } | ||
1445 | |||
1446 | sfree(rowdata); | ||
1447 | } | ||
1448 | |||
1449 | return ret; | ||
1450 | } else | ||
1451 | return NULL; | ||
1452 | } | ||
1453 | |||
1454 | /* ---------------------------------------------------------------------- | ||
1455 | * Error-checking during gameplay. | ||
1456 | */ | ||
1457 | |||
1458 | /* | ||
1459 | * The difficulty in error-checking Pattern is to make the error check | ||
1460 | * _weak_ enough. The most obvious way would be to check each row and | ||
1461 | * column by calling (a modified form of) do_row() to recursively | ||
1462 | * analyse the row contents against the clue set and see if the | ||
1463 | * GRID_UNKNOWNs could be filled in in any way that would end up | ||
1464 | * correct. However, this turns out to be such a strong error check as | ||
1465 | * to constitute a spoiler in many situations: you make a typo while | ||
1466 | * trying to fill in one row, and not only does the row light up to | ||
1467 | * indicate an error, but several columns crossed by the move also | ||
1468 | * light up and draw your attention to deductions you hadn't even | ||
1469 | * noticed you could make. | ||
1470 | * | ||
1471 | * So instead I restrict error-checking to 'complete runs' within a | ||
1472 | * row, by which I mean contiguous sequences of GRID_FULL bounded at | ||
1473 | * both ends by either GRID_EMPTY or the ends of the row. We identify | ||
1474 | * all the complete runs in a row, and verify that _those_ are | ||
1475 | * consistent with the row's clue list. Sequences of complete runs | ||
1476 | * separated by solid GRID_EMPTY are required to match contiguous | ||
1477 | * sequences in the clue list, whereas if there's at least one | ||
1478 | * GRID_UNKNOWN between any two complete runs then those two need not | ||
1479 | * be contiguous in the clue list. | ||
1480 | * | ||
1481 | * To simplify the edge cases, I pretend that the clue list for the | ||
1482 | * row is extended with a 0 at each end, and I also pretend that the | ||
1483 | * grid data for the row is extended with a GRID_EMPTY and a | ||
1484 | * zero-length run at each end. This permits the contiguity checker to | ||
1485 | * handle the fiddly end effects (e.g. if the first contiguous | ||
1486 | * sequence of complete runs in the grid matches _something_ in the | ||
1487 | * clue list but not at the beginning, this is allowable iff there's a | ||
1488 | * GRID_UNKNOWN before the first one) with minimal faff, since the end | ||
1489 | * effects just drop out as special cases of the normal inter-run | ||
1490 | * handling (in this code the above case is not 'at the end of the | ||
1491 | * clue list' at all, but between the implicit initial zero run and | ||
1492 | * the first nonzero one). | ||
1493 | * | ||
1494 | * We must also be a little careful about how we search for a | ||
1495 | * contiguous sequence of runs. In the clue list (1 1 2 1 2 3), | ||
1496 | * suppose we see a GRID_UNKNOWN and then a length-1 run. We search | ||
1497 | * for 1 in the clue list and find it at the very beginning. But now | ||
1498 | * suppose we find a length-2 run with no GRID_UNKNOWN before it. We | ||
1499 | * can't naively look at the next clue from the 1 we found, because | ||
1500 | * that'll be the second 1 and won't match. Instead, we must backtrack | ||
1501 | * by observing that the 2 we've just found must be contiguous with | ||
1502 | * the 1 we've already seen, so we search for the sequence (1 2) and | ||
1503 | * find it starting at the second 1. Now if we see a 3, we must | ||
1504 | * rethink again and search for (1 2 3). | ||
1505 | */ | ||
1506 | |||
1507 | struct errcheck_state { | ||
1508 | /* | ||
1509 | * rowdata and rowlen point at the clue data for this row in the | ||
1510 | * game state. | ||
1511 | */ | ||
1512 | int *rowdata; | ||
1513 | int rowlen; | ||
1514 | /* | ||
1515 | * rowpos indicates the lowest position where it would be valid to | ||
1516 | * see our next run length. It might be equal to rowlen, | ||
1517 | * indicating that the next run would have to be the terminating 0. | ||
1518 | */ | ||
1519 | int rowpos; | ||
1520 | /* | ||
1521 | * ncontig indicates how many runs we've seen in a contiguous | ||
1522 | * block. This is taken into account when searching for the next | ||
1523 | * run we find, unless ncontig is zeroed out first by encountering | ||
1524 | * a GRID_UNKNOWN. | ||
1525 | */ | ||
1526 | int ncontig; | ||
1527 | }; | ||
1528 | |||
1529 | static int errcheck_found_run(struct errcheck_state *es, int r) | ||
1530 | { | ||
1531 | /* Macro to handle the pretence that rowdata has a 0 at each end */ | ||
1532 | #define ROWDATA(k) ((k)<0 || (k)>=es->rowlen ? 0 : es->rowdata[(k)]) | ||
1533 | |||
1534 | /* | ||
1535 | * See if we can find this new run length at a position where it | ||
1536 | * also matches the last 'ncontig' runs we've seen. | ||
1537 | */ | ||
1538 | int i, newpos; | ||
1539 | for (newpos = es->rowpos; newpos <= es->rowlen; newpos++) { | ||
1540 | |||
1541 | if (ROWDATA(newpos) != r) | ||
1542 | goto notfound; | ||
1543 | |||
1544 | for (i = 1; i <= es->ncontig; i++) | ||
1545 | if (ROWDATA(newpos - i) != ROWDATA(es->rowpos - i)) | ||
1546 | goto notfound; | ||
1547 | |||
1548 | es->rowpos = newpos+1; | ||
1549 | es->ncontig++; | ||
1550 | return TRUE; | ||
1551 | |||
1552 | notfound:; | ||
1553 | } | ||
1554 | |||
1555 | return FALSE; | ||
1556 | |||
1557 | #undef ROWDATA | ||
1558 | } | ||
1559 | |||
1560 | static int check_errors(const game_state *state, int i) | ||
1561 | { | ||
1562 | int start, step, end, j; | ||
1563 | int val, runlen; | ||
1564 | struct errcheck_state aes, *es = &aes; | ||
1565 | |||
1566 | es->rowlen = state->common->rowlen[i]; | ||
1567 | es->rowdata = state->common->rowdata + state->common->rowsize * i; | ||
1568 | /* Pretend that we've already encountered the initial zero run */ | ||
1569 | es->ncontig = 1; | ||
1570 | es->rowpos = 0; | ||
1571 | |||
1572 | if (i < state->common->w) { | ||
1573 | start = i; | ||
1574 | step = state->common->w; | ||
1575 | end = start + step * state->common->h; | ||
1576 | } else { | ||
1577 | start = (i - state->common->w) * state->common->w; | ||
1578 | step = 1; | ||
1579 | end = start + step * state->common->w; | ||
1580 | } | ||
1581 | |||
1582 | runlen = -1; | ||
1583 | for (j = start - step; j <= end; j += step) { | ||
1584 | if (j < start || j == end) | ||
1585 | val = GRID_EMPTY; | ||
1586 | else | ||
1587 | val = state->grid[j]; | ||
1588 | |||
1589 | if (val == GRID_UNKNOWN) { | ||
1590 | runlen = -1; | ||
1591 | es->ncontig = 0; | ||
1592 | } else if (val == GRID_FULL) { | ||
1593 | if (runlen >= 0) | ||
1594 | runlen++; | ||
1595 | } else if (val == GRID_EMPTY) { | ||
1596 | if (runlen > 0) { | ||
1597 | if (!errcheck_found_run(es, runlen)) | ||
1598 | return TRUE; /* error! */ | ||
1599 | } | ||
1600 | runlen = 0; | ||
1601 | } | ||
1602 | } | ||
1603 | |||
1604 | /* Signal end-of-row by sending errcheck_found_run the terminating | ||
1605 | * zero run, which will be marked as contiguous with the previous | ||
1606 | * run if and only if there hasn't been a GRID_UNKNOWN before. */ | ||
1607 | if (!errcheck_found_run(es, 0)) | ||
1608 | return TRUE; /* error at the last minute! */ | ||
1609 | |||
1610 | return FALSE; /* no error */ | ||
1611 | } | ||
1612 | |||
1613 | /* ---------------------------------------------------------------------- | ||
1614 | * Drawing routines. | ||
1615 | */ | ||
1616 | |||
1617 | static void game_compute_size(const game_params *params, int tilesize, | ||
1618 | int *x, int *y) | ||
1619 | { | ||
1620 | /* Ick: fake up `ds->tilesize' for macro expansion purposes */ | ||
1621 | struct { int tilesize; } ads, *ds = &ads; | ||
1622 | ads.tilesize = tilesize; | ||
1623 | |||
1624 | *x = SIZE(params->w); | ||
1625 | *y = SIZE(params->h); | ||
1626 | } | ||
1627 | |||
1628 | static void game_set_size(drawing *dr, game_drawstate *ds, | ||
1629 | const game_params *params, int tilesize) | ||
1630 | { | ||
1631 | ds->tilesize = tilesize; | ||
1632 | } | ||
1633 | |||
1634 | static float *game_colours(frontend *fe, int *ncolours) | ||
1635 | { | ||
1636 | float *ret = snewn(3 * NCOLOURS, float); | ||
1637 | int i; | ||
1638 | |||
1639 | frontend_default_colour(fe, &ret[COL_BACKGROUND * 3]); | ||
1640 | |||
1641 | for (i = 0; i < 3; i++) { | ||
1642 | ret[COL_GRID * 3 + i] = 0.3F; | ||
1643 | ret[COL_UNKNOWN * 3 + i] = 0.5F; | ||
1644 | ret[COL_TEXT * 3 + i] = 0.0F; | ||
1645 | ret[COL_FULL * 3 + i] = 0.0F; | ||
1646 | ret[COL_EMPTY * 3 + i] = 1.0F; | ||
1647 | } | ||
1648 | ret[COL_CURSOR * 3 + 0] = 1.0F; | ||
1649 | ret[COL_CURSOR * 3 + 1] = 0.25F; | ||
1650 | ret[COL_CURSOR * 3 + 2] = 0.25F; | ||
1651 | ret[COL_ERROR * 3 + 0] = 1.0F; | ||
1652 | ret[COL_ERROR * 3 + 1] = 0.0F; | ||
1653 | ret[COL_ERROR * 3 + 2] = 0.0F; | ||
1654 | |||
1655 | *ncolours = NCOLOURS; | ||
1656 | return ret; | ||
1657 | } | ||
1658 | |||
1659 | static game_drawstate *game_new_drawstate(drawing *dr, const game_state *state) | ||
1660 | { | ||
1661 | struct game_drawstate *ds = snew(struct game_drawstate); | ||
1662 | |||
1663 | ds->started = FALSE; | ||
1664 | ds->w = state->common->w; | ||
1665 | ds->h = state->common->h; | ||
1666 | ds->visible = snewn(ds->w * ds->h, unsigned char); | ||
1667 | ds->tilesize = 0; /* not decided yet */ | ||
1668 | memset(ds->visible, 255, ds->w * ds->h); | ||
1669 | ds->numcolours = snewn(ds->w + ds->h, unsigned char); | ||
1670 | memset(ds->numcolours, 255, ds->w + ds->h); | ||
1671 | ds->cur_x = ds->cur_y = 0; | ||
1672 | |||
1673 | return ds; | ||
1674 | } | ||
1675 | |||
1676 | static void game_free_drawstate(drawing *dr, game_drawstate *ds) | ||
1677 | { | ||
1678 | sfree(ds->visible); | ||
1679 | sfree(ds); | ||
1680 | } | ||
1681 | |||
1682 | static void grid_square(drawing *dr, game_drawstate *ds, | ||
1683 | int y, int x, int state, int cur) | ||
1684 | { | ||
1685 | int xl, xr, yt, yb, dx, dy, dw, dh; | ||
1686 | |||
1687 | draw_rect(dr, TOCOORD(ds->w, x), TOCOORD(ds->h, y), | ||
1688 | TILE_SIZE, TILE_SIZE, COL_GRID); | ||
1689 | |||
1690 | xl = (x % 5 == 0 ? 1 : 0); | ||
1691 | yt = (y % 5 == 0 ? 1 : 0); | ||
1692 | xr = (x % 5 == 4 || x == ds->w-1 ? 1 : 0); | ||
1693 | yb = (y % 5 == 4 || y == ds->h-1 ? 1 : 0); | ||
1694 | |||
1695 | dx = TOCOORD(ds->w, x) + 1 + xl; | ||
1696 | dy = TOCOORD(ds->h, y) + 1 + yt; | ||
1697 | dw = TILE_SIZE - xl - xr - 1; | ||
1698 | dh = TILE_SIZE - yt - yb - 1; | ||
1699 | |||
1700 | draw_rect(dr, dx, dy, dw, dh, | ||
1701 | (state == GRID_FULL ? COL_FULL : | ||
1702 | state == GRID_EMPTY ? COL_EMPTY : COL_UNKNOWN)); | ||
1703 | if (cur) { | ||
1704 | draw_rect_outline(dr, dx, dy, dw, dh, COL_CURSOR); | ||
1705 | draw_rect_outline(dr, dx+1, dy+1, dw-2, dh-2, COL_CURSOR); | ||
1706 | } | ||
1707 | |||
1708 | draw_update(dr, TOCOORD(ds->w, x), TOCOORD(ds->h, y), | ||
1709 | TILE_SIZE, TILE_SIZE); | ||
1710 | } | ||
1711 | |||
1712 | /* | ||
1713 | * Draw the numbers for a single row or column. | ||
1714 | */ | ||
1715 | static void draw_numbers(drawing *dr, game_drawstate *ds, | ||
1716 | const game_state *state, int i, int erase, int colour) | ||
1717 | { | ||
1718 | int rowlen = state->common->rowlen[i]; | ||
1719 | int *rowdata = state->common->rowdata + state->common->rowsize * i; | ||
1720 | int nfit; | ||
1721 | int j; | ||
1722 | |||
1723 | if (erase) { | ||
1724 | if (i < state->common->w) { | ||
1725 | draw_rect(dr, TOCOORD(state->common->w, i), 0, | ||
1726 | TILE_SIZE, BORDER + TLBORDER(state->common->h) * TILE_SIZE, | ||
1727 | COL_BACKGROUND); | ||
1728 | } else { | ||
1729 | draw_rect(dr, 0, TOCOORD(state->common->h, i - state->common->w), | ||
1730 | BORDER + TLBORDER(state->common->w) * TILE_SIZE, TILE_SIZE, | ||
1731 | COL_BACKGROUND); | ||
1732 | } | ||
1733 | } | ||
1734 | |||
1735 | /* | ||
1736 | * Normally I space the numbers out by the same distance as the | ||
1737 | * tile size. However, if there are more numbers than available | ||
1738 | * spaces, I have to squash them up a bit. | ||
1739 | */ | ||
1740 | if (i < state->common->w) | ||
1741 | nfit = TLBORDER(state->common->h); | ||
1742 | else | ||
1743 | nfit = TLBORDER(state->common->w); | ||
1744 | nfit = max(rowlen, nfit) - 1; | ||
1745 | assert(nfit > 0); | ||
1746 | |||
1747 | for (j = 0; j < rowlen; j++) { | ||
1748 | int x, y; | ||
1749 | char str[80]; | ||
1750 | |||
1751 | if (i < state->common->w) { | ||
1752 | x = TOCOORD(state->common->w, i); | ||
1753 | y = BORDER + TILE_SIZE * (TLBORDER(state->common->h)-1); | ||
1754 | y -= ((rowlen-j-1)*TILE_SIZE) * (TLBORDER(state->common->h)-1) / nfit; | ||
1755 | } else { | ||
1756 | y = TOCOORD(state->common->h, i - state->common->w); | ||
1757 | x = BORDER + TILE_SIZE * (TLBORDER(state->common->w)-1); | ||
1758 | x -= ((rowlen-j-1)*TILE_SIZE) * (TLBORDER(state->common->w)-1) / nfit; | ||
1759 | } | ||
1760 | |||
1761 | sprintf(str, "%d", rowdata[j]); | ||
1762 | draw_text(dr, x+TILE_SIZE/2, y+TILE_SIZE/2, FONT_VARIABLE, | ||
1763 | TILE_SIZE/2, ALIGN_HCENTRE | ALIGN_VCENTRE, colour, str); | ||
1764 | } | ||
1765 | |||
1766 | if (i < state->common->w) { | ||
1767 | draw_update(dr, TOCOORD(state->common->w, i), 0, | ||
1768 | TILE_SIZE, BORDER + TLBORDER(state->common->h) * TILE_SIZE); | ||
1769 | } else { | ||
1770 | draw_update(dr, 0, TOCOORD(state->common->h, i - state->common->w), | ||
1771 | BORDER + TLBORDER(state->common->w) * TILE_SIZE, TILE_SIZE); | ||
1772 | } | ||
1773 | } | ||
1774 | |||
1775 | static void game_redraw(drawing *dr, game_drawstate *ds, | ||
1776 | const game_state *oldstate, const game_state *state, | ||
1777 | int dir, const game_ui *ui, | ||
1778 | float animtime, float flashtime) | ||
1779 | { | ||
1780 | int i, j; | ||
1781 | int x1, x2, y1, y2; | ||
1782 | int cx, cy, cmoved; | ||
1783 | |||
1784 | if (!ds->started) { | ||
1785 | /* | ||
1786 | * The initial contents of the window are not guaranteed | ||
1787 | * and can vary with front ends. To be on the safe side, | ||
1788 | * all games should start by drawing a big background- | ||
1789 | * colour rectangle covering the whole window. | ||
1790 | */ | ||
1791 | draw_rect(dr, 0, 0, SIZE(ds->w), SIZE(ds->h), COL_BACKGROUND); | ||
1792 | |||
1793 | /* | ||
1794 | * Draw the grid outline. | ||
1795 | */ | ||
1796 | draw_rect(dr, TOCOORD(ds->w, 0) - 1, TOCOORD(ds->h, 0) - 1, | ||
1797 | ds->w * TILE_SIZE + 3, ds->h * TILE_SIZE + 3, | ||
1798 | COL_GRID); | ||
1799 | |||
1800 | ds->started = TRUE; | ||
1801 | |||
1802 | draw_update(dr, 0, 0, SIZE(ds->w), SIZE(ds->h)); | ||
1803 | } | ||
1804 | |||
1805 | if (ui->dragging) { | ||
1806 | x1 = min(ui->drag_start_x, ui->drag_end_x); | ||
1807 | x2 = max(ui->drag_start_x, ui->drag_end_x); | ||
1808 | y1 = min(ui->drag_start_y, ui->drag_end_y); | ||
1809 | y2 = max(ui->drag_start_y, ui->drag_end_y); | ||
1810 | } else { | ||
1811 | x1 = x2 = y1 = y2 = -1; /* placate gcc warnings */ | ||
1812 | } | ||
1813 | |||
1814 | if (ui->cur_visible) { | ||
1815 | cx = ui->cur_x; cy = ui->cur_y; | ||
1816 | } else { | ||
1817 | cx = cy = -1; | ||
1818 | } | ||
1819 | cmoved = (cx != ds->cur_x || cy != ds->cur_y); | ||
1820 | |||
1821 | /* | ||
1822 | * Now draw any grid squares which have changed since last | ||
1823 | * redraw. | ||
1824 | */ | ||
1825 | for (i = 0; i < ds->h; i++) { | ||
1826 | for (j = 0; j < ds->w; j++) { | ||
1827 | int val, cc = 0; | ||
1828 | |||
1829 | /* | ||
1830 | * Work out what state this square should be drawn in, | ||
1831 | * taking any current drag operation into account. | ||
1832 | */ | ||
1833 | if (ui->dragging && x1 <= j && j <= x2 && y1 <= i && i <= y2 && | ||
1834 | !state->common->immutable[i * state->common->w + j]) | ||
1835 | val = ui->state; | ||
1836 | else | ||
1837 | val = state->grid[i * state->common->w + j]; | ||
1838 | |||
1839 | if (cmoved) { | ||
1840 | /* the cursor has moved; if we were the old or | ||
1841 | * the new cursor position we need to redraw. */ | ||
1842 | if (j == cx && i == cy) cc = 1; | ||
1843 | if (j == ds->cur_x && i == ds->cur_y) cc = 1; | ||
1844 | } | ||
1845 | |||
1846 | /* | ||
1847 | * Briefly invert everything twice during a completion | ||
1848 | * flash. | ||
1849 | */ | ||
1850 | if (flashtime > 0 && | ||
1851 | (flashtime <= FLASH_TIME/3 || flashtime >= FLASH_TIME*2/3) && | ||
1852 | val != GRID_UNKNOWN) | ||
1853 | val = (GRID_FULL ^ GRID_EMPTY) ^ val; | ||
1854 | |||
1855 | if (ds->visible[i * ds->w + j] != val || cc) { | ||
1856 | grid_square(dr, ds, i, j, val, | ||
1857 | (j == cx && i == cy)); | ||
1858 | ds->visible[i * ds->w + j] = val; | ||
1859 | } | ||
1860 | } | ||
1861 | } | ||
1862 | ds->cur_x = cx; ds->cur_y = cy; | ||
1863 | |||
1864 | /* | ||
1865 | * Redraw any numbers which have changed their colour due to error | ||
1866 | * indication. | ||
1867 | */ | ||
1868 | for (i = 0; i < state->common->w + state->common->h; i++) { | ||
1869 | int colour = check_errors(state, i) ? COL_ERROR : COL_TEXT; | ||
1870 | if (ds->numcolours[i] != colour) { | ||
1871 | draw_numbers(dr, ds, state, i, TRUE, colour); | ||
1872 | ds->numcolours[i] = colour; | ||
1873 | } | ||
1874 | } | ||
1875 | } | ||
1876 | |||
1877 | static float game_anim_length(const game_state *oldstate, | ||
1878 | const game_state *newstate, int dir, game_ui *ui) | ||
1879 | { | ||
1880 | return 0.0F; | ||
1881 | } | ||
1882 | |||
1883 | static float game_flash_length(const game_state *oldstate, | ||
1884 | const game_state *newstate, int dir, game_ui *ui) | ||
1885 | { | ||
1886 | if (!oldstate->completed && newstate->completed && | ||
1887 | !oldstate->cheated && !newstate->cheated) | ||
1888 | return FLASH_TIME; | ||
1889 | return 0.0F; | ||
1890 | } | ||
1891 | |||
1892 | static int game_status(const game_state *state) | ||
1893 | { | ||
1894 | return state->completed ? +1 : 0; | ||
1895 | } | ||
1896 | |||
1897 | static int game_timing_state(const game_state *state, game_ui *ui) | ||
1898 | { | ||
1899 | return TRUE; | ||
1900 | } | ||
1901 | |||
1902 | static void game_print_size(const game_params *params, float *x, float *y) | ||
1903 | { | ||
1904 | int pw, ph; | ||
1905 | |||
1906 | /* | ||
1907 | * I'll use 5mm squares by default. | ||
1908 | */ | ||
1909 | game_compute_size(params, 500, &pw, &ph); | ||
1910 | *x = pw / 100.0F; | ||
1911 | *y = ph / 100.0F; | ||
1912 | } | ||
1913 | |||
1914 | static void game_print(drawing *dr, const game_state *state, int tilesize) | ||
1915 | { | ||
1916 | int w = state->common->w, h = state->common->h; | ||
1917 | int ink = print_mono_colour(dr, 0); | ||
1918 | int x, y, i; | ||
1919 | |||
1920 | /* Ick: fake up `ds->tilesize' for macro expansion purposes */ | ||
1921 | game_drawstate ads, *ds = &ads; | ||
1922 | game_set_size(dr, ds, NULL, tilesize); | ||
1923 | |||
1924 | /* | ||
1925 | * Border. | ||
1926 | */ | ||
1927 | print_line_width(dr, TILE_SIZE / 16); | ||
1928 | draw_rect_outline(dr, TOCOORD(w, 0), TOCOORD(h, 0), | ||
1929 | w*TILE_SIZE, h*TILE_SIZE, ink); | ||
1930 | |||
1931 | /* | ||
1932 | * Grid. | ||
1933 | */ | ||
1934 | for (x = 1; x < w; x++) { | ||
1935 | print_line_width(dr, TILE_SIZE / (x % 5 ? 128 : 24)); | ||
1936 | draw_line(dr, TOCOORD(w, x), TOCOORD(h, 0), | ||
1937 | TOCOORD(w, x), TOCOORD(h, h), ink); | ||
1938 | } | ||
1939 | for (y = 1; y < h; y++) { | ||
1940 | print_line_width(dr, TILE_SIZE / (y % 5 ? 128 : 24)); | ||
1941 | draw_line(dr, TOCOORD(w, 0), TOCOORD(h, y), | ||
1942 | TOCOORD(w, w), TOCOORD(h, y), ink); | ||
1943 | } | ||
1944 | |||
1945 | /* | ||
1946 | * Clues. | ||
1947 | */ | ||
1948 | for (i = 0; i < state->common->w + state->common->h; i++) | ||
1949 | draw_numbers(dr, ds, state, i, FALSE, ink); | ||
1950 | |||
1951 | /* | ||
1952 | * Solution. | ||
1953 | */ | ||
1954 | print_line_width(dr, TILE_SIZE / 128); | ||
1955 | for (y = 0; y < h; y++) | ||
1956 | for (x = 0; x < w; x++) { | ||
1957 | if (state->grid[y*w+x] == GRID_FULL) | ||
1958 | draw_rect(dr, TOCOORD(w, x), TOCOORD(h, y), | ||
1959 | TILE_SIZE, TILE_SIZE, ink); | ||
1960 | else if (state->grid[y*w+x] == GRID_EMPTY) | ||
1961 | draw_circle(dr, TOCOORD(w, x) + TILE_SIZE/2, | ||
1962 | TOCOORD(h, y) + TILE_SIZE/2, | ||
1963 | TILE_SIZE/12, ink, ink); | ||
1964 | } | ||
1965 | } | ||
1966 | |||
1967 | #ifdef COMBINED | ||
1968 | #define thegame pattern | ||
1969 | #endif | ||
1970 | |||
1971 | const struct game thegame = { | ||
1972 | "Pattern", "games.pattern", "pattern", | ||
1973 | default_params, | ||
1974 | game_fetch_preset, NULL, | ||
1975 | decode_params, | ||
1976 | encode_params, | ||
1977 | free_params, | ||
1978 | dup_params, | ||
1979 | TRUE, game_configure, custom_params, | ||
1980 | validate_params, | ||
1981 | new_game_desc, | ||
1982 | validate_desc, | ||
1983 | new_game, | ||
1984 | dup_game, | ||
1985 | free_game, | ||
1986 | TRUE, solve_game, | ||
1987 | TRUE, game_can_format_as_text_now, game_text_format, | ||
1988 | new_ui, | ||
1989 | free_ui, | ||
1990 | encode_ui, | ||
1991 | decode_ui, | ||
1992 | game_changed_state, | ||
1993 | interpret_move, | ||
1994 | execute_move, | ||
1995 | PREFERRED_TILE_SIZE, game_compute_size, game_set_size, | ||
1996 | game_colours, | ||
1997 | game_new_drawstate, | ||
1998 | game_free_drawstate, | ||
1999 | game_redraw, | ||
2000 | game_anim_length, | ||
2001 | game_flash_length, | ||
2002 | game_status, | ||
2003 | TRUE, FALSE, game_print_size, game_print, | ||
2004 | FALSE, /* wants_statusbar */ | ||
2005 | FALSE, game_timing_state, | ||
2006 | REQUIRE_RBUTTON, /* flags */ | ||
2007 | }; | ||
2008 | |||
2009 | #ifdef STANDALONE_SOLVER | ||
2010 | |||
2011 | int main(int argc, char **argv) | ||
2012 | { | ||
2013 | game_params *p; | ||
2014 | game_state *s; | ||
2015 | char *id = NULL, *desc, *err; | ||
2016 | |||
2017 | while (--argc > 0) { | ||
2018 | char *p = *++argv; | ||
2019 | if (*p == '-') { | ||
2020 | if (!strcmp(p, "-v")) { | ||
2021 | verbose = TRUE; | ||
2022 | } else { | ||
2023 | fprintf(stderr, "%s: unrecognised option `%s'\n", argv[0], p); | ||
2024 | return 1; | ||
2025 | } | ||
2026 | } else { | ||
2027 | id = p; | ||
2028 | } | ||
2029 | } | ||
2030 | |||
2031 | if (!id) { | ||
2032 | fprintf(stderr, "usage: %s <game_id>\n", argv[0]); | ||
2033 | return 1; | ||
2034 | } | ||
2035 | |||
2036 | desc = strchr(id, ':'); | ||
2037 | if (!desc) { | ||
2038 | fprintf(stderr, "%s: game id expects a colon in it\n", argv[0]); | ||
2039 | return 1; | ||
2040 | } | ||
2041 | *desc++ = '\0'; | ||
2042 | |||
2043 | p = default_params(); | ||
2044 | decode_params(p, id); | ||
2045 | err = validate_desc(p, desc); | ||
2046 | if (err) { | ||
2047 | fprintf(stderr, "%s: %s\n", argv[0], err); | ||
2048 | return 1; | ||
2049 | } | ||
2050 | s = new_game(NULL, p, desc); | ||
2051 | |||
2052 | { | ||
2053 | int w = p->w, h = p->h, i, j, max, cluewid = 0; | ||
2054 | unsigned char *matrix, *workspace; | ||
2055 | unsigned int *changed_h, *changed_w; | ||
2056 | int *rowdata; | ||
2057 | |||
2058 | matrix = snewn(w*h, unsigned char); | ||
2059 | max = max(w, h); | ||
2060 | workspace = snewn(max*7, unsigned char); | ||
2061 | changed_h = snewn(max+1, unsigned int); | ||
2062 | changed_w = snewn(max+1, unsigned int); | ||
2063 | rowdata = snewn(max+1, int); | ||
2064 | |||
2065 | if (verbose) { | ||
2066 | int thiswid; | ||
2067 | /* | ||
2068 | * Work out the maximum text width of the clue numbers | ||
2069 | * in a row or column, so we can print the solver's | ||
2070 | * working in a nicely lined up way. | ||
2071 | */ | ||
2072 | for (i = 0; i < (w+h); i++) { | ||
2073 | char buf[80]; | ||
2074 | for (thiswid = -1, j = 0; j < s->common->rowlen[i]; j++) | ||
2075 | thiswid += sprintf | ||
2076 | (buf, " %d", | ||
2077 | s->common->rowdata[s->common->rowsize*i+j]); | ||
2078 | if (cluewid < thiswid) | ||
2079 | cluewid = thiswid; | ||
2080 | } | ||
2081 | } | ||
2082 | |||
2083 | solve_puzzle(s, NULL, w, h, matrix, workspace, | ||
2084 | changed_h, changed_w, rowdata, cluewid); | ||
2085 | |||
2086 | for (i = 0; i < h; i++) { | ||
2087 | for (j = 0; j < w; j++) { | ||
2088 | int c = (matrix[i*w+j] == UNKNOWN ? '?' : | ||
2089 | matrix[i*w+j] == BLOCK ? '#' : | ||
2090 | matrix[i*w+j] == DOT ? '.' : | ||
2091 | '!'); | ||
2092 | putchar(c); | ||
2093 | } | ||
2094 | printf("\n"); | ||
2095 | } | ||
2096 | } | ||
2097 | |||
2098 | return 0; | ||
2099 | } | ||
2100 | |||
2101 | #endif | ||
2102 | |||
2103 | #ifdef STANDALONE_PICTURE_GENERATOR | ||
2104 | |||
2105 | /* | ||
2106 | * Main program for the standalone picture generator. To use it, | ||
2107 | * simply provide it with an XBM-format bitmap file (note XBM, not | ||
2108 | * XPM) on standard input, and it will output a game ID in return. | ||
2109 | * For example: | ||
2110 | * | ||
2111 | * $ ./patternpicture < calligraphic-A.xbm | ||
2112 | * 15x15:2/4/2/2/2/3/3/3.1/3.1/3.1/11/14/12/6/1/2/2/3/4/5/1.3/2.3/1.3/2.3/1.4/9/1.1.3/2.2.3/5.4/3.2 | ||
2113 | * | ||
2114 | * That looks easy, of course - all the program has done is to count | ||
2115 | * up the clue numbers! But in fact, it's done more than that: it's | ||
2116 | * also checked that the result is uniquely soluble from just the | ||
2117 | * numbers. If it hadn't been, then it would have also left some | ||
2118 | * filled squares in the playing area as extra clues. | ||
2119 | * | ||
2120 | * $ ./patternpicture < cube.xbm | ||
2121 | * 15x15:10/2.1/1.1.1/1.1.1/1.1.1/1.1.1/1.1.1/1.1.1/1.1.1/1.10/1.1.1/1.1.1/1.1.1/2.1/10/10/1.2/1.1.1/1.1.1/1.1.1/10.1/1.1.1/1.1.1/1.1.1/1.1.1/1.1.1/1.1.1/1.1.1/1.2/10,TNINzzzzGNzw | ||
2122 | * | ||
2123 | * This enables a reasonably convenient design workflow for coming up | ||
2124 | * with pictorial Pattern puzzles which _are_ uniquely soluble without | ||
2125 | * those inelegant pre-filled squares. Fire up a bitmap editor (X11 | ||
2126 | * bitmap(1) is good enough), save a trial .xbm, and then test it by | ||
2127 | * running a command along the lines of | ||
2128 | * | ||
2129 | * $ ./pattern $(./patternpicture < test.xbm) | ||
2130 | * | ||
2131 | * If the resulting window pops up with some pre-filled squares, then | ||
2132 | * that tells you which parts of the image are giving rise to | ||
2133 | * ambiguities, so try making tweaks in those areas, try the test | ||
2134 | * command again, and see if it helps. Once you have a design for | ||
2135 | * which the Pattern starting grid comes out empty, there's your game | ||
2136 | * ID. | ||
2137 | */ | ||
2138 | |||
2139 | #include <time.h> | ||
2140 | |||
2141 | int main(int argc, char **argv) | ||
2142 | { | ||
2143 | game_params *par; | ||
2144 | char *params, *desc; | ||
2145 | random_state *rs; | ||
2146 | time_t seed = time(NULL); | ||
2147 | char buf[4096]; | ||
2148 | int i; | ||
2149 | int x, y; | ||
2150 | |||
2151 | par = default_params(); | ||
2152 | if (argc > 1) | ||
2153 | decode_params(par, argv[1]); /* get difficulty */ | ||
2154 | par->w = par->h = -1; | ||
2155 | |||
2156 | /* | ||
2157 | * Now read an XBM file from standard input. This is simple and | ||
2158 | * hacky and will do very little error detection, so don't feed | ||
2159 | * it bogus data. | ||
2160 | */ | ||
2161 | picture = NULL; | ||
2162 | x = y = 0; | ||
2163 | while (fgets(buf, sizeof(buf), stdin)) { | ||
2164 | buf[strcspn(buf, "\r\n")] = '\0'; | ||
2165 | if (!strncmp(buf, "#define", 7)) { | ||
2166 | /* | ||
2167 | * Lines starting `#define' give the width and height. | ||
2168 | */ | ||
2169 | char *num = buf + strlen(buf); | ||
2170 | char *symend; | ||
2171 | |||
2172 | while (num > buf && isdigit((unsigned char)num[-1])) | ||
2173 | num--; | ||
2174 | symend = num; | ||
2175 | while (symend > buf && isspace((unsigned char)symend[-1])) | ||
2176 | symend--; | ||
2177 | |||
2178 | if (symend-5 >= buf && !strncmp(symend-5, "width", 5)) | ||
2179 | par->w = atoi(num); | ||
2180 | else if (symend-6 >= buf && !strncmp(symend-6, "height", 6)) | ||
2181 | par->h = atoi(num); | ||
2182 | } else { | ||
2183 | /* | ||
2184 | * Otherwise, break the string up into words and take | ||
2185 | * any word of the form `0x' plus hex digits to be a | ||
2186 | * byte. | ||
2187 | */ | ||
2188 | char *p, *wordstart; | ||
2189 | |||
2190 | if (!picture) { | ||
2191 | if (par->w < 0 || par->h < 0) { | ||
2192 | printf("failed to read width and height\n"); | ||
2193 | return 1; | ||
2194 | } | ||
2195 | picture = snewn(par->w * par->h, unsigned char); | ||
2196 | for (i = 0; i < par->w * par->h; i++) | ||
2197 | picture[i] = GRID_UNKNOWN; | ||
2198 | } | ||
2199 | |||
2200 | p = buf; | ||
2201 | while (*p) { | ||
2202 | while (*p && (*p == ',' || isspace((unsigned char)*p))) | ||
2203 | p++; | ||
2204 | wordstart = p; | ||
2205 | while (*p && !(*p == ',' || *p == '}' || | ||
2206 | isspace((unsigned char)*p))) | ||
2207 | p++; | ||
2208 | if (*p) | ||
2209 | *p++ = '\0'; | ||
2210 | |||
2211 | if (wordstart[0] == '0' && | ||
2212 | (wordstart[1] == 'x' || wordstart[1] == 'X') && | ||
2213 | !wordstart[2 + strspn(wordstart+2, | ||
2214 | "0123456789abcdefABCDEF")]) { | ||
2215 | unsigned long byte = strtoul(wordstart+2, NULL, 16); | ||
2216 | for (i = 0; i < 8; i++) { | ||
2217 | int bit = (byte >> i) & 1; | ||
2218 | if (y < par->h && x < par->w) | ||
2219 | picture[y * par->w + x] = | ||
2220 | bit ? GRID_FULL : GRID_EMPTY; | ||
2221 | x++; | ||
2222 | } | ||
2223 | |||
2224 | if (x >= par->w) { | ||
2225 | x = 0; | ||
2226 | y++; | ||
2227 | } | ||
2228 | } | ||
2229 | } | ||
2230 | } | ||
2231 | } | ||
2232 | |||
2233 | for (i = 0; i < par->w * par->h; i++) | ||
2234 | if (picture[i] == GRID_UNKNOWN) { | ||
2235 | fprintf(stderr, "failed to read enough bitmap data\n"); | ||
2236 | return 1; | ||
2237 | } | ||
2238 | |||
2239 | rs = random_new((void*)&seed, sizeof(time_t)); | ||
2240 | |||
2241 | desc = new_game_desc(par, rs, NULL, FALSE); | ||
2242 | params = encode_params(par, FALSE); | ||
2243 | printf("%s:%s\n", params, desc); | ||
2244 | |||
2245 | sfree(desc); | ||
2246 | sfree(params); | ||
2247 | free_params(par); | ||
2248 | random_free(rs); | ||
2249 | |||
2250 | return 0; | ||
2251 | } | ||
2252 | |||
2253 | #endif | ||
2254 | |||
2255 | /* vim: set shiftwidth=4 tabstop=8: */ | ||