b6b0369e |
1 | /* |
2 | * pattern.c: the pattern-reconstruction game known as `nonograms'. |
3 | * |
4 | * TODO before checkin: |
5 | * |
6 | * - make some sort of stab at number-of-numbers judgment |
7 | */ |
8 | |
9 | #include <stdio.h> |
10 | #include <stdlib.h> |
11 | #include <string.h> |
12 | #include <assert.h> |
13 | #include <ctype.h> |
14 | #include <math.h> |
15 | |
16 | #include "puzzles.h" |
17 | |
18 | #define max(x,y) ( (x)>(y) ? (x):(y) ) |
19 | #define min(x,y) ( (x)<(y) ? (x):(y) ) |
20 | |
21 | const char *const game_name = "Pattern"; |
22 | const char *const game_winhelp_topic = "games.pattern"; |
23 | const int game_can_configure = TRUE; |
24 | |
25 | enum { |
26 | COL_BACKGROUND, |
27 | COL_EMPTY, |
28 | COL_FULL, |
29 | COL_UNKNOWN, |
30 | COL_GRID, |
31 | NCOLOURS |
32 | }; |
33 | |
34 | #define BORDER 18 |
35 | #define TLBORDER(d) ( (d) / 5 + 2 ) |
36 | #define GUTTER 12 |
37 | #define TILE_SIZE 24 |
38 | |
39 | #define FROMCOORD(d, x) \ |
40 | ( ((x) - (BORDER + GUTTER + TILE_SIZE * TLBORDER(d))) / TILE_SIZE ) |
41 | |
42 | #define SIZE(d) (2*BORDER + GUTTER + TILE_SIZE * (TLBORDER(d) + (d))) |
43 | |
44 | #define TOCOORD(d, x) (BORDER + GUTTER + TILE_SIZE * (TLBORDER(d) + (x))) |
45 | |
46 | struct game_params { |
47 | int w, h; |
48 | }; |
49 | |
50 | #define GRID_UNKNOWN 2 |
51 | #define GRID_FULL 1 |
52 | #define GRID_EMPTY 0 |
53 | |
54 | struct game_state { |
55 | int w, h; |
56 | unsigned char *grid; |
57 | int rowsize; |
58 | int *rowdata, *rowlen; |
59 | int completed; |
60 | }; |
61 | |
62 | #define FLASH_TIME 0.13F |
63 | |
64 | game_params *default_params(void) |
65 | { |
66 | game_params *ret = snew(game_params); |
67 | |
68 | ret->w = ret->h = 15; |
69 | |
70 | return ret; |
71 | } |
72 | |
73 | int game_fetch_preset(int i, char **name, game_params **params) |
74 | { |
75 | game_params *ret; |
76 | char str[80]; |
77 | static const struct { int x, y; } values[] = { |
78 | {10, 10}, |
79 | {15, 15}, |
80 | {20, 20}, |
81 | {25, 25}, |
82 | {30, 30}, |
83 | }; |
84 | |
85 | if (i < 0 || i >= lenof(values)) |
86 | return FALSE; |
87 | |
88 | ret = snew(game_params); |
89 | ret->w = values[i].x; |
90 | ret->h = values[i].y; |
91 | |
92 | sprintf(str, "%dx%d", ret->w, ret->h); |
93 | |
94 | *name = dupstr(str); |
95 | *params = ret; |
96 | return TRUE; |
97 | } |
98 | |
99 | void free_params(game_params *params) |
100 | { |
101 | sfree(params); |
102 | } |
103 | |
104 | game_params *dup_params(game_params *params) |
105 | { |
106 | game_params *ret = snew(game_params); |
107 | *ret = *params; /* structure copy */ |
108 | return ret; |
109 | } |
110 | |
111 | game_params *decode_params(char const *string) |
112 | { |
113 | game_params *ret = default_params(); |
114 | char const *p = string; |
115 | |
116 | ret->w = atoi(p); |
117 | while (*p && isdigit(*p)) p++; |
118 | if (*p == 'x') { |
119 | p++; |
120 | ret->h = atoi(p); |
121 | while (*p && isdigit(*p)) p++; |
122 | } else { |
123 | ret->h = ret->w; |
124 | } |
125 | |
126 | return ret; |
127 | } |
128 | |
129 | char *encode_params(game_params *params) |
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 | config_item *game_configure(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 | game_params *custom_params(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 | char *validate_params(game_params *params) |
179 | { |
180 | if (params->w <= 0 && params->h <= 0) |
181 | return "Width and height must both be greater than zero"; |
182 | if (params->w <= 0) |
183 | return "Width must be greater than zero"; |
184 | if (params->h <= 0) |
185 | return "Height must be greater than zero"; |
186 | return NULL; |
187 | } |
188 | |
189 | /* ---------------------------------------------------------------------- |
190 | * Puzzle generation code. |
191 | * |
192 | * For this particular puzzle, it seemed important to me to ensure |
193 | * a unique solution. I do this the brute-force way, by having a |
194 | * solver algorithm alongside the generator, and repeatedly |
195 | * generating a random grid until I find one whose solution is |
196 | * unique. It turns out that this isn't too onerous on a modern PC |
197 | * provided you keep grid size below around 30. Any offers of |
198 | * better algorithms, however, will be very gratefully received. |
199 | * |
200 | * Another annoyance of this approach is that it limits the |
201 | * available puzzles to those solvable by the algorithm I've used. |
202 | * My algorithm only ever considers a single row or column at any |
203 | * one time, which means it's incapable of solving the following |
204 | * difficult example (found by Bella Image around 1995/6, when she |
205 | * and I were both doing maths degrees): |
206 | * |
207 | * 2 1 2 1 |
208 | * |
209 | * +--+--+--+--+ |
210 | * 1 1 | | | | | |
211 | * +--+--+--+--+ |
212 | * 2 | | | | | |
213 | * +--+--+--+--+ |
214 | * 1 | | | | | |
215 | * +--+--+--+--+ |
216 | * 1 | | | | | |
217 | * +--+--+--+--+ |
218 | * |
219 | * Obviously this cannot be solved by a one-row-or-column-at-a-time |
220 | * algorithm (it would require at least one row or column reading |
221 | * `2 1', `1 2', `3' or `4' to get started). However, it can be |
222 | * proved to have a unique solution: if the top left square were |
223 | * empty, then the only option for the top row would be to fill the |
224 | * two squares in the 1 columns, which would imply the squares |
225 | * below those were empty, leaving no place for the 2 in the second |
226 | * row. Contradiction. Hence the top left square is full, and the |
227 | * unique solution follows easily from that starting point. |
228 | * |
229 | * (The game ID for this puzzle is 4x4:2/1/2/1/1.1/2/1/1 , in case |
230 | * it's useful to anyone.) |
231 | */ |
232 | |
233 | static int float_compare(const void *av, const void *bv) |
234 | { |
235 | const float *a = (const float *)av; |
236 | const float *b = (const float *)bv; |
237 | if (*a < *b) |
238 | return -1; |
239 | else if (*a > *b) |
240 | return +1; |
241 | else |
242 | return 0; |
243 | } |
244 | |
245 | static void generate(random_state *rs, int w, int h, unsigned char *retgrid) |
246 | { |
247 | float *fgrid; |
248 | float *fgrid2; |
249 | int step, i, j; |
250 | float threshold; |
251 | |
252 | fgrid = snewn(w*h, float); |
253 | |
254 | for (i = 0; i < h; i++) { |
255 | for (j = 0; j < w; j++) { |
256 | fgrid[i*w+j] = random_upto(rs, 100000000UL) / 100000000.F; |
257 | } |
258 | } |
259 | |
260 | /* |
261 | * The above gives a completely random splattering of black and |
262 | * white cells. We want to gently bias this in favour of _some_ |
263 | * reasonably thick areas of white and black, while retaining |
264 | * some randomness and fine detail. |
265 | * |
266 | * So we evolve the starting grid using a cellular automaton. |
267 | * Currently, I'm doing something very simple indeed, which is |
268 | * to set each square to the average of the surrounding nine |
269 | * cells (or the average of fewer, if we're on a corner). |
270 | */ |
271 | for (step = 0; step < 1; step++) { |
272 | fgrid2 = snewn(w*h, float); |
273 | |
274 | for (i = 0; i < h; i++) { |
275 | for (j = 0; j < w; j++) { |
276 | float sx, xbar; |
277 | int n, p, q; |
278 | |
279 | /* |
280 | * Compute the average of the surrounding cells. |
281 | */ |
282 | n = 0; |
283 | sx = 0.F; |
284 | for (p = -1; p <= +1; p++) { |
285 | for (q = -1; q <= +1; q++) { |
286 | if (i+p < 0 || i+p >= h || j+q < 0 || j+q >= w) |
287 | continue; |
288 | n++; |
289 | sx += fgrid[(i+p)*w+(j+q)]; |
290 | } |
291 | } |
292 | xbar = sx / n; |
293 | |
294 | fgrid2[i*w+j] = xbar; |
295 | } |
296 | } |
297 | |
298 | sfree(fgrid); |
299 | fgrid = fgrid2; |
300 | } |
301 | |
302 | fgrid2 = snewn(w*h, float); |
303 | memcpy(fgrid2, fgrid, w*h*sizeof(float)); |
304 | qsort(fgrid2, w*h, sizeof(float), float_compare); |
305 | threshold = fgrid2[w*h/2]; |
306 | sfree(fgrid2); |
307 | |
308 | for (i = 0; i < h; i++) { |
309 | for (j = 0; j < w; j++) { |
310 | retgrid[i*w+j] = (fgrid[i*w+j] > threshold ? GRID_FULL : |
311 | GRID_EMPTY); |
312 | } |
313 | } |
314 | |
315 | sfree(fgrid); |
316 | } |
317 | |
318 | int compute_rowdata(int *ret, unsigned char *start, int len, int step) |
319 | { |
320 | int i, n; |
321 | |
322 | n = 0; |
323 | |
324 | for (i = 0; i < len; i++) { |
b6b0369e |
325 | if (start[i*step] == GRID_FULL) { |
326 | int runlen = 1; |
0526a222 |
327 | while (i+runlen < len && start[(i+runlen)*step] == GRID_FULL) |
b6b0369e |
328 | runlen++; |
329 | ret[n++] = runlen; |
330 | i += runlen; |
331 | } |
0526a222 |
332 | |
c87ce51a |
333 | if (i < len && start[i*step] == GRID_UNKNOWN) |
0526a222 |
334 | return -1; |
b6b0369e |
335 | } |
336 | |
337 | return n; |
338 | } |
339 | |
340 | #define UNKNOWN 0 |
341 | #define BLOCK 1 |
342 | #define DOT 2 |
343 | #define STILL_UNKNOWN 3 |
344 | |
345 | static void do_recurse(unsigned char *known, unsigned char *deduced, |
346 | unsigned char *row, int *data, int len, |
347 | int freespace, int ndone, int lowest) |
348 | { |
349 | int i, j, k; |
350 | |
351 | if (data[ndone]) { |
352 | for (i=0; i<=freespace; i++) { |
353 | j = lowest; |
354 | for (k=0; k<i; k++) row[j++] = DOT; |
355 | for (k=0; k<data[ndone]; k++) row[j++] = BLOCK; |
356 | if (j < len) row[j++] = DOT; |
357 | do_recurse(known, deduced, row, data, len, |
358 | freespace-i, ndone+1, j); |
359 | } |
360 | } else { |
361 | for (i=lowest; i<len; i++) |
362 | row[i] = DOT; |
363 | for (i=0; i<len; i++) |
364 | if (known[i] && known[i] != row[i]) |
365 | return; |
366 | for (i=0; i<len; i++) |
367 | deduced[i] |= row[i]; |
368 | } |
369 | } |
370 | |
371 | static int do_row(unsigned char *known, unsigned char *deduced, |
372 | unsigned char *row, |
373 | unsigned char *start, int len, int step, int *data) |
374 | { |
375 | int rowlen, i, freespace, done_any; |
376 | |
377 | freespace = len+1; |
378 | for (rowlen = 0; data[rowlen]; rowlen++) |
379 | freespace -= data[rowlen]+1; |
380 | |
381 | for (i = 0; i < len; i++) { |
382 | known[i] = start[i*step]; |
383 | deduced[i] = 0; |
384 | } |
385 | |
386 | do_recurse(known, deduced, row, data, len, freespace, 0, 0); |
387 | done_any = FALSE; |
388 | for (i=0; i<len; i++) |
389 | if (deduced[i] && deduced[i] != STILL_UNKNOWN && !known[i]) { |
390 | start[i*step] = deduced[i]; |
391 | done_any = TRUE; |
392 | } |
393 | return done_any; |
394 | } |
395 | |
396 | static unsigned char *generate_soluble(random_state *rs, int w, int h) |
397 | { |
398 | int i, j, done_any, ok, ntries, max; |
399 | unsigned char *grid, *matrix, *workspace; |
400 | int *rowdata; |
401 | |
402 | grid = snewn(w*h, unsigned char); |
403 | matrix = snewn(w*h, unsigned char); |
404 | max = max(w, h); |
405 | workspace = snewn(max*3, unsigned char); |
406 | rowdata = snewn(max+1, int); |
407 | |
408 | ntries = 0; |
409 | |
410 | do { |
411 | ntries++; |
412 | |
413 | generate(rs, w, h, grid); |
414 | |
415 | memset(matrix, 0, w*h); |
416 | |
417 | do { |
418 | done_any = 0; |
419 | for (i=0; i<h; i++) { |
420 | rowdata[compute_rowdata(rowdata, grid+i*w, w, 1)] = 0; |
421 | done_any |= do_row(workspace, workspace+max, workspace+2*max, |
422 | matrix+i*w, w, 1, rowdata); |
423 | } |
424 | for (i=0; i<w; i++) { |
425 | rowdata[compute_rowdata(rowdata, grid+i, h, w)] = 0; |
426 | done_any |= do_row(workspace, workspace+max, workspace+2*max, |
427 | matrix+i, h, w, rowdata); |
428 | } |
429 | } while (done_any); |
430 | |
431 | ok = TRUE; |
432 | for (i=0; i<h; i++) { |
433 | for (j=0; j<w; j++) { |
434 | if (matrix[i*w+j] == UNKNOWN) |
435 | ok = FALSE; |
436 | } |
437 | } |
438 | } while (!ok); |
439 | |
440 | sfree(matrix); |
441 | sfree(workspace); |
442 | sfree(rowdata); |
443 | return grid; |
444 | } |
445 | |
446 | char *new_game_seed(game_params *params, random_state *rs) |
447 | { |
448 | unsigned char *grid; |
449 | int i, j, max, rowlen, *rowdata; |
450 | char intbuf[80], *seed; |
451 | int seedlen, seedpos; |
452 | |
453 | grid = generate_soluble(rs, params->w, params->h); |
454 | max = max(params->w, params->h); |
455 | rowdata = snewn(max, int); |
456 | |
457 | /* |
458 | * Seed is a slash-separated list of row contents; each row |
459 | * contents section is a dot-separated list of integers. Row |
460 | * contents are listed in the order (columns left to right, |
461 | * then rows top to bottom). |
462 | * |
463 | * Simplest way to handle memory allocation is to make two |
464 | * passes, first computing the seed size and then writing it |
465 | * out. |
466 | */ |
467 | seedlen = 0; |
468 | for (i = 0; i < params->w + params->h; i++) { |
469 | if (i < params->w) |
470 | rowlen = compute_rowdata(rowdata, grid+i, params->h, params->w); |
471 | else |
472 | rowlen = compute_rowdata(rowdata, grid+(i-params->w)*params->w, |
473 | params->w, 1); |
474 | if (rowlen > 0) { |
475 | for (j = 0; j < rowlen; j++) { |
476 | seedlen += 1 + sprintf(intbuf, "%d", rowdata[j]); |
477 | } |
478 | } else { |
479 | seedlen++; |
480 | } |
481 | } |
482 | seed = snewn(seedlen, char); |
483 | seedpos = 0; |
484 | for (i = 0; i < params->w + params->h; i++) { |
485 | if (i < params->w) |
486 | rowlen = compute_rowdata(rowdata, grid+i, params->h, params->w); |
487 | else |
488 | rowlen = compute_rowdata(rowdata, grid+(i-params->w)*params->w, |
489 | params->w, 1); |
490 | if (rowlen > 0) { |
491 | for (j = 0; j < rowlen; j++) { |
492 | int len = sprintf(seed+seedpos, "%d", rowdata[j]); |
493 | if (j+1 < rowlen) |
494 | seed[seedpos + len] = '.'; |
495 | else |
496 | seed[seedpos + len] = '/'; |
497 | seedpos += len+1; |
498 | } |
499 | } else { |
500 | seed[seedpos++] = '/'; |
501 | } |
502 | } |
503 | assert(seedpos == seedlen); |
504 | assert(seed[seedlen-1] == '/'); |
505 | seed[seedlen-1] = '\0'; |
506 | sfree(rowdata); |
507 | return seed; |
508 | } |
509 | |
510 | char *validate_seed(game_params *params, char *seed) |
511 | { |
512 | int i, n, rowspace; |
513 | char *p; |
514 | |
515 | for (i = 0; i < params->w + params->h; i++) { |
516 | if (i < params->w) |
517 | rowspace = params->h + 1; |
518 | else |
519 | rowspace = params->w + 1; |
520 | |
521 | if (*seed && isdigit((unsigned char)*seed)) { |
522 | do { |
523 | p = seed; |
524 | while (seed && isdigit((unsigned char)*seed)) seed++; |
525 | n = atoi(p); |
526 | rowspace -= n+1; |
527 | |
528 | if (rowspace < 0) { |
529 | if (i < params->w) |
530 | return "at least one column contains more numbers than will fit"; |
531 | else |
532 | return "at least one row contains more numbers than will fit"; |
533 | } |
534 | } while (*seed++ == '.'); |
535 | } else { |
536 | seed++; /* expect a slash immediately */ |
537 | } |
538 | |
539 | if (seed[-1] == '/') { |
540 | if (i+1 == params->w + params->h) |
541 | return "too many row/column specifications"; |
542 | } else if (seed[-1] == '\0') { |
543 | if (i+1 < params->w + params->h) |
544 | return "too few row/column specifications"; |
545 | } else |
546 | return "unrecognised character in game specification"; |
547 | } |
548 | |
549 | return NULL; |
550 | } |
551 | |
552 | game_state *new_game(game_params *params, char *seed) |
553 | { |
554 | int i; |
555 | char *p; |
556 | game_state *state = snew(game_state); |
557 | |
558 | state->w = params->w; |
559 | state->h = params->h; |
560 | |
561 | state->grid = snewn(state->w * state->h, unsigned char); |
562 | memset(state->grid, GRID_UNKNOWN, state->w * state->h); |
563 | |
564 | state->rowsize = max(state->w, state->h); |
565 | state->rowdata = snewn(state->rowsize * (state->w + state->h), int); |
566 | state->rowlen = snewn(state->w + state->h, int); |
567 | |
568 | state->completed = FALSE; |
569 | |
570 | for (i = 0; i < params->w + params->h; i++) { |
571 | state->rowlen[i] = 0; |
572 | if (*seed && isdigit((unsigned char)*seed)) { |
573 | do { |
574 | p = seed; |
575 | while (seed && isdigit((unsigned char)*seed)) seed++; |
576 | state->rowdata[state->rowsize * i + state->rowlen[i]++] = |
577 | atoi(p); |
578 | } while (*seed++ == '.'); |
579 | } else { |
580 | seed++; /* expect a slash immediately */ |
581 | } |
582 | } |
583 | |
584 | return state; |
585 | } |
586 | |
587 | game_state *dup_game(game_state *state) |
588 | { |
589 | game_state *ret = snew(game_state); |
590 | |
591 | ret->w = state->w; |
592 | ret->h = state->h; |
593 | |
594 | ret->grid = snewn(ret->w * ret->h, unsigned char); |
595 | memcpy(ret->grid, state->grid, ret->w * ret->h); |
596 | |
597 | ret->rowsize = state->rowsize; |
598 | ret->rowdata = snewn(ret->rowsize * (ret->w + ret->h), int); |
599 | ret->rowlen = snewn(ret->w + ret->h, int); |
600 | memcpy(ret->rowdata, state->rowdata, |
601 | ret->rowsize * (ret->w + ret->h) * sizeof(int)); |
602 | memcpy(ret->rowlen, state->rowlen, |
603 | (ret->w + ret->h) * sizeof(int)); |
604 | |
605 | ret->completed = state->completed; |
606 | |
607 | return ret; |
608 | } |
609 | |
610 | void free_game(game_state *state) |
611 | { |
612 | sfree(state->rowdata); |
613 | sfree(state->rowlen); |
614 | sfree(state->grid); |
615 | sfree(state); |
616 | } |
617 | |
618 | struct game_ui { |
619 | int dragging; |
620 | int drag_start_x; |
621 | int drag_start_y; |
622 | int drag_end_x; |
623 | int drag_end_y; |
624 | int drag, release, state; |
625 | }; |
626 | |
627 | game_ui *new_ui(game_state *state) |
628 | { |
629 | game_ui *ret; |
630 | |
631 | ret = snew(game_ui); |
632 | ret->dragging = FALSE; |
633 | |
634 | return ret; |
635 | } |
636 | |
637 | void free_ui(game_ui *ui) |
638 | { |
639 | sfree(ui); |
640 | } |
641 | |
642 | game_state *make_move(game_state *from, game_ui *ui, int x, int y, int button) |
643 | { |
644 | game_state *ret; |
645 | |
646 | x = FROMCOORD(from->w, x); |
647 | y = FROMCOORD(from->h, y); |
648 | |
649 | if (x >= 0 && x < from->w && y >= 0 && y < from->h && |
650 | (button == LEFT_BUTTON || button == RIGHT_BUTTON || |
651 | button == MIDDLE_BUTTON)) { |
652 | |
653 | ui->dragging = TRUE; |
654 | |
655 | if (button == LEFT_BUTTON) { |
656 | ui->drag = LEFT_DRAG; |
657 | ui->release = LEFT_RELEASE; |
658 | ui->state = GRID_FULL; |
659 | } else if (button == RIGHT_BUTTON) { |
660 | ui->drag = RIGHT_DRAG; |
661 | ui->release = RIGHT_RELEASE; |
662 | ui->state = GRID_EMPTY; |
663 | } else /* if (button == MIDDLE_BUTTON) */ { |
664 | ui->drag = MIDDLE_DRAG; |
665 | ui->release = MIDDLE_RELEASE; |
666 | ui->state = GRID_UNKNOWN; |
667 | } |
668 | |
669 | ui->drag_start_x = ui->drag_end_x = x; |
670 | ui->drag_start_y = ui->drag_end_y = y; |
671 | |
672 | return from; /* UI activity occurred */ |
673 | } |
674 | |
675 | if (ui->dragging && button == ui->drag) { |
676 | /* |
677 | * There doesn't seem much point in allowing a rectangle |
678 | * drag; people will generally only want to drag a single |
679 | * horizontal or vertical line, so we make that easy by |
680 | * snapping to it. |
681 | * |
682 | * Exception: if we're _middle_-button dragging to tag |
683 | * things as UNKNOWN, we may well want to trash an entire |
684 | * area and start over! |
685 | */ |
686 | if (ui->state != GRID_UNKNOWN) { |
687 | if (abs(x - ui->drag_start_x) > abs(y - ui->drag_start_y)) |
688 | y = ui->drag_start_y; |
689 | else |
690 | x = ui->drag_start_x; |
691 | } |
692 | |
693 | if (x < 0) x = 0; |
694 | if (y < 0) y = 0; |
695 | if (x >= from->w) x = from->w - 1; |
696 | if (y >= from->h) y = from->h - 1; |
697 | |
698 | ui->drag_end_x = x; |
699 | ui->drag_end_y = y; |
700 | |
701 | return from; /* UI activity occurred */ |
702 | } |
703 | |
704 | if (ui->dragging && button == ui->release) { |
705 | int x1, x2, y1, y2, xx, yy; |
706 | int move_needed = FALSE; |
707 | |
708 | x1 = min(ui->drag_start_x, ui->drag_end_x); |
709 | x2 = max(ui->drag_start_x, ui->drag_end_x); |
710 | y1 = min(ui->drag_start_y, ui->drag_end_y); |
711 | y2 = max(ui->drag_start_y, ui->drag_end_y); |
712 | |
713 | for (yy = y1; yy <= y2; yy++) |
714 | for (xx = x1; xx <= x2; xx++) |
715 | if (from->grid[yy * from->w + xx] != ui->state) |
716 | move_needed = TRUE; |
717 | |
718 | ui->dragging = FALSE; |
719 | |
720 | if (move_needed) { |
721 | ret = dup_game(from); |
722 | for (yy = y1; yy <= y2; yy++) |
723 | for (xx = x1; xx <= x2; xx++) |
724 | ret->grid[yy * ret->w + xx] = ui->state; |
725 | |
726 | /* |
727 | * An actual change, so check to see if we've completed |
728 | * the game. |
729 | */ |
730 | if (!ret->completed) { |
731 | int *rowdata = snewn(ret->rowsize, int); |
732 | int i, len; |
733 | |
734 | ret->completed = TRUE; |
735 | |
736 | for (i=0; i<ret->w; i++) { |
737 | len = compute_rowdata(rowdata, |
738 | ret->grid+i, ret->h, ret->w); |
739 | if (len != ret->rowlen[i] || |
740 | memcmp(ret->rowdata+i*ret->rowsize, rowdata, |
741 | len * sizeof(int))) { |
742 | ret->completed = FALSE; |
743 | break; |
744 | } |
745 | } |
746 | for (i=0; i<ret->h; i++) { |
747 | len = compute_rowdata(rowdata, |
748 | ret->grid+i*ret->w, ret->w, 1); |
749 | if (len != ret->rowlen[i+ret->w] || |
750 | memcmp(ret->rowdata+(i+ret->w)*ret->rowsize, rowdata, |
751 | len * sizeof(int))) { |
752 | ret->completed = FALSE; |
753 | break; |
754 | } |
755 | } |
756 | |
757 | sfree(rowdata); |
758 | } |
759 | |
760 | return ret; |
761 | } else |
762 | return from; /* UI activity occurred */ |
763 | } |
764 | |
765 | return NULL; |
766 | } |
767 | |
768 | /* ---------------------------------------------------------------------- |
769 | * Drawing routines. |
770 | */ |
771 | |
772 | struct game_drawstate { |
773 | int started; |
774 | int w, h; |
775 | unsigned char *visible; |
776 | }; |
777 | |
778 | void game_size(game_params *params, int *x, int *y) |
779 | { |
780 | *x = SIZE(params->w); |
781 | *y = SIZE(params->h); |
782 | } |
783 | |
784 | float *game_colours(frontend *fe, game_state *state, int *ncolours) |
785 | { |
786 | float *ret = snewn(3 * NCOLOURS, float); |
787 | |
788 | frontend_default_colour(fe, &ret[COL_BACKGROUND * 3]); |
789 | |
790 | ret[COL_GRID * 3 + 0] = 0.3F; |
791 | ret[COL_GRID * 3 + 1] = 0.3F; |
792 | ret[COL_GRID * 3 + 2] = 0.3F; |
793 | |
794 | ret[COL_UNKNOWN * 3 + 0] = 0.5F; |
795 | ret[COL_UNKNOWN * 3 + 1] = 0.5F; |
796 | ret[COL_UNKNOWN * 3 + 2] = 0.5F; |
797 | |
798 | ret[COL_FULL * 3 + 0] = 0.0F; |
799 | ret[COL_FULL * 3 + 1] = 0.0F; |
800 | ret[COL_FULL * 3 + 2] = 0.0F; |
801 | |
802 | ret[COL_EMPTY * 3 + 0] = 1.0F; |
803 | ret[COL_EMPTY * 3 + 1] = 1.0F; |
804 | ret[COL_EMPTY * 3 + 2] = 1.0F; |
805 | |
806 | *ncolours = NCOLOURS; |
807 | return ret; |
808 | } |
809 | |
810 | game_drawstate *game_new_drawstate(game_state *state) |
811 | { |
812 | struct game_drawstate *ds = snew(struct game_drawstate); |
813 | |
814 | ds->started = FALSE; |
815 | ds->w = state->w; |
816 | ds->h = state->h; |
817 | ds->visible = snewn(ds->w * ds->h, unsigned char); |
818 | memset(ds->visible, 255, ds->w * ds->h); |
819 | |
820 | return ds; |
821 | } |
822 | |
823 | void game_free_drawstate(game_drawstate *ds) |
824 | { |
825 | sfree(ds->visible); |
826 | sfree(ds); |
827 | } |
828 | |
829 | static void grid_square(frontend *fe, game_drawstate *ds, |
830 | int y, int x, int state) |
831 | { |
832 | int xl, xr, yt, yb; |
833 | |
834 | draw_rect(fe, TOCOORD(ds->w, x), TOCOORD(ds->h, y), |
835 | TILE_SIZE, TILE_SIZE, COL_GRID); |
836 | |
837 | xl = (x % 5 == 0 ? 1 : 0); |
838 | yt = (y % 5 == 0 ? 1 : 0); |
839 | xr = (x % 5 == 4 || x == ds->w-1 ? 1 : 0); |
840 | yb = (y % 5 == 4 || y == ds->h-1 ? 1 : 0); |
841 | |
842 | draw_rect(fe, TOCOORD(ds->w, x) + 1 + xl, TOCOORD(ds->h, y) + 1 + yt, |
843 | TILE_SIZE - xl - xr - 1, TILE_SIZE - yt - yb - 1, |
844 | (state == GRID_FULL ? COL_FULL : |
845 | state == GRID_EMPTY ? COL_EMPTY : COL_UNKNOWN)); |
846 | |
847 | draw_update(fe, TOCOORD(ds->w, x), TOCOORD(ds->h, y), |
848 | TILE_SIZE, TILE_SIZE); |
849 | } |
850 | |
851 | void game_redraw(frontend *fe, game_drawstate *ds, game_state *oldstate, |
852 | game_state *state, int dir, game_ui *ui, |
853 | float animtime, float flashtime) |
854 | { |
855 | int i, j; |
856 | int x1, x2, y1, y2; |
857 | |
858 | if (!ds->started) { |
859 | /* |
860 | * The initial contents of the window are not guaranteed |
861 | * and can vary with front ends. To be on the safe side, |
862 | * all games should start by drawing a big background- |
863 | * colour rectangle covering the whole window. |
864 | */ |
865 | draw_rect(fe, 0, 0, SIZE(ds->w), SIZE(ds->h), COL_BACKGROUND); |
866 | |
867 | /* |
868 | * Draw the numbers. |
869 | */ |
870 | for (i = 0; i < ds->w + ds->h; i++) { |
871 | int rowlen = state->rowlen[i]; |
872 | int *rowdata = state->rowdata + state->rowsize * i; |
873 | int nfit; |
874 | |
875 | /* |
876 | * Normally I space the numbers out by the same |
877 | * distance as the tile size. However, if there are |
878 | * more numbers than available spaces, I have to squash |
879 | * them up a bit. |
880 | */ |
881 | nfit = max(rowlen, TLBORDER(ds->h))-1; |
882 | assert(nfit > 0); |
883 | |
884 | for (j = 0; j < rowlen; j++) { |
885 | int x, y; |
886 | char str[80]; |
887 | |
888 | if (i < ds->w) { |
889 | x = TOCOORD(ds->w, i); |
890 | y = BORDER + TILE_SIZE * (TLBORDER(ds->h)-1); |
891 | y -= ((rowlen-j-1)*TILE_SIZE) * (TLBORDER(ds->h)-1) / nfit; |
892 | } else { |
893 | y = TOCOORD(ds->h, i - ds->w); |
894 | x = BORDER + TILE_SIZE * (TLBORDER(ds->w)-1); |
895 | x -= ((rowlen-j-1)*TILE_SIZE) * (TLBORDER(ds->h)-1) / nfit; |
896 | } |
897 | |
898 | sprintf(str, "%d", rowdata[j]); |
899 | draw_text(fe, x+TILE_SIZE/2, y+TILE_SIZE/2, FONT_VARIABLE, |
900 | TILE_SIZE/2, ALIGN_HCENTRE | ALIGN_VCENTRE, |
901 | COL_FULL, str); /* FIXME: COL_TEXT */ |
902 | } |
903 | } |
904 | |
905 | /* |
906 | * Draw the grid outline. |
907 | */ |
908 | draw_rect(fe, TOCOORD(ds->w, 0) - 1, TOCOORD(ds->h, 0) - 1, |
909 | ds->w * TILE_SIZE + 2, ds->h * TILE_SIZE + 2, |
910 | COL_GRID); |
911 | |
912 | ds->started = TRUE; |
913 | |
914 | draw_update(fe, 0, 0, SIZE(ds->w), SIZE(ds->h)); |
915 | } |
916 | |
917 | if (ui->dragging) { |
918 | x1 = min(ui->drag_start_x, ui->drag_end_x); |
919 | x2 = max(ui->drag_start_x, ui->drag_end_x); |
920 | y1 = min(ui->drag_start_y, ui->drag_end_y); |
921 | y2 = max(ui->drag_start_y, ui->drag_end_y); |
922 | } else { |
923 | x1 = x2 = y1 = y2 = -1; /* placate gcc warnings */ |
924 | } |
925 | |
926 | /* |
927 | * Now draw any grid squares which have changed since last |
928 | * redraw. |
929 | */ |
930 | for (i = 0; i < ds->h; i++) { |
931 | for (j = 0; j < ds->w; j++) { |
932 | int val; |
933 | |
934 | /* |
935 | * Work out what state this square should be drawn in, |
936 | * taking any current drag operation into account. |
937 | */ |
938 | if (ui->dragging && x1 <= j && j <= x2 && y1 <= i && i <= y2) |
939 | val = ui->state; |
940 | else |
941 | val = state->grid[i * state->w + j]; |
942 | |
943 | /* |
944 | * Briefly invert everything twice during a completion |
945 | * flash. |
946 | */ |
947 | if (flashtime > 0 && |
948 | (flashtime <= FLASH_TIME/3 || flashtime >= FLASH_TIME*2/3) && |
949 | val != GRID_UNKNOWN) |
950 | val = (GRID_FULL ^ GRID_EMPTY) ^ val; |
951 | |
952 | if (ds->visible[i * ds->w + j] != val) { |
953 | grid_square(fe, ds, i, j, val); |
954 | ds->visible[i * ds->w + j] = val; |
955 | } |
956 | } |
957 | } |
958 | } |
959 | |
960 | float game_anim_length(game_state *oldstate, game_state *newstate, int dir) |
961 | { |
962 | return 0.0F; |
963 | } |
964 | |
965 | float game_flash_length(game_state *oldstate, game_state *newstate, int dir) |
966 | { |
967 | if (!oldstate->completed && newstate->completed) |
968 | return FLASH_TIME; |
969 | return 0.0F; |
970 | } |
971 | |
972 | int game_wants_statusbar(void) |
973 | { |
974 | return FALSE; |
975 | } |