Mouse-based interface for Cube: you left-click anywhere on the grid
[sgt/puzzles] / pattern.c
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 #define max(x,y) ( (x)>(y) ? (x):(y) )
15 #define min(x,y) ( (x)<(y) ? (x):(y) )
16
17 enum {
18 COL_BACKGROUND,
19 COL_EMPTY,
20 COL_FULL,
21 COL_UNKNOWN,
22 COL_GRID,
23 NCOLOURS
24 };
25
26 #define BORDER 18
27 #define TLBORDER(d) ( (d) / 5 + 2 )
28 #define GUTTER 12
29 #define TILE_SIZE 24
30
31 #define FROMCOORD(d, x) \
32 ( ((x) - (BORDER + GUTTER + TILE_SIZE * TLBORDER(d))) / TILE_SIZE )
33
34 #define SIZE(d) (2*BORDER + GUTTER + TILE_SIZE * (TLBORDER(d) + (d)))
35
36 #define TOCOORD(d, x) (BORDER + GUTTER + TILE_SIZE * (TLBORDER(d) + (x)))
37
38 struct game_params {
39 int w, h;
40 };
41
42 #define GRID_UNKNOWN 2
43 #define GRID_FULL 1
44 #define GRID_EMPTY 0
45
46 struct game_state {
47 int w, h;
48 unsigned char *grid;
49 int rowsize;
50 int *rowdata, *rowlen;
51 int completed, cheated;
52 };
53
54 #define FLASH_TIME 0.13F
55
56 static game_params *default_params(void)
57 {
58 game_params *ret = snew(game_params);
59
60 ret->w = ret->h = 15;
61
62 return ret;
63 }
64
65 static int game_fetch_preset(int i, char **name, game_params **params)
66 {
67 game_params *ret;
68 char str[80];
69 static const struct { int x, y; } values[] = {
70 {10, 10},
71 {15, 15},
72 {20, 20},
73 {25, 25},
74 {30, 30},
75 };
76
77 if (i < 0 || i >= lenof(values))
78 return FALSE;
79
80 ret = snew(game_params);
81 ret->w = values[i].x;
82 ret->h = values[i].y;
83
84 sprintf(str, "%dx%d", ret->w, ret->h);
85
86 *name = dupstr(str);
87 *params = ret;
88 return TRUE;
89 }
90
91 static void free_params(game_params *params)
92 {
93 sfree(params);
94 }
95
96 static game_params *dup_params(game_params *params)
97 {
98 game_params *ret = snew(game_params);
99 *ret = *params; /* structure copy */
100 return ret;
101 }
102
103 static void decode_params(game_params *ret, char const *string)
104 {
105 char const *p = string;
106
107 ret->w = atoi(p);
108 while (*p && isdigit(*p)) p++;
109 if (*p == 'x') {
110 p++;
111 ret->h = atoi(p);
112 while (*p && isdigit(*p)) p++;
113 } else {
114 ret->h = ret->w;
115 }
116 }
117
118 static char *encode_params(game_params *params, int full)
119 {
120 char ret[400];
121 int len;
122
123 len = sprintf(ret, "%dx%d", params->w, params->h);
124 assert(len < lenof(ret));
125 ret[len] = '\0';
126
127 return dupstr(ret);
128 }
129
130 static config_item *game_configure(game_params *params)
131 {
132 config_item *ret;
133 char buf[80];
134
135 ret = snewn(3, config_item);
136
137 ret[0].name = "Width";
138 ret[0].type = C_STRING;
139 sprintf(buf, "%d", params->w);
140 ret[0].sval = dupstr(buf);
141 ret[0].ival = 0;
142
143 ret[1].name = "Height";
144 ret[1].type = C_STRING;
145 sprintf(buf, "%d", params->h);
146 ret[1].sval = dupstr(buf);
147 ret[1].ival = 0;
148
149 ret[2].name = NULL;
150 ret[2].type = C_END;
151 ret[2].sval = NULL;
152 ret[2].ival = 0;
153
154 return ret;
155 }
156
157 static game_params *custom_params(config_item *cfg)
158 {
159 game_params *ret = snew(game_params);
160
161 ret->w = atoi(cfg[0].sval);
162 ret->h = atoi(cfg[1].sval);
163
164 return ret;
165 }
166
167 static char *validate_params(game_params *params)
168 {
169 if (params->w <= 0 && params->h <= 0)
170 return "Width and height must both be greater than zero";
171 if (params->w <= 0)
172 return "Width must be greater than zero";
173 if (params->h <= 0)
174 return "Height must be greater than zero";
175 return NULL;
176 }
177
178 /* ----------------------------------------------------------------------
179 * Puzzle generation code.
180 *
181 * For this particular puzzle, it seemed important to me to ensure
182 * a unique solution. I do this the brute-force way, by having a
183 * solver algorithm alongside the generator, and repeatedly
184 * generating a random grid until I find one whose solution is
185 * unique. It turns out that this isn't too onerous on a modern PC
186 * provided you keep grid size below around 30. Any offers of
187 * better algorithms, however, will be very gratefully received.
188 *
189 * Another annoyance of this approach is that it limits the
190 * available puzzles to those solvable by the algorithm I've used.
191 * My algorithm only ever considers a single row or column at any
192 * one time, which means it's incapable of solving the following
193 * difficult example (found by Bella Image around 1995/6, when she
194 * and I were both doing maths degrees):
195 *
196 * 2 1 2 1
197 *
198 * +--+--+--+--+
199 * 1 1 | | | | |
200 * +--+--+--+--+
201 * 2 | | | | |
202 * +--+--+--+--+
203 * 1 | | | | |
204 * +--+--+--+--+
205 * 1 | | | | |
206 * +--+--+--+--+
207 *
208 * Obviously this cannot be solved by a one-row-or-column-at-a-time
209 * algorithm (it would require at least one row or column reading
210 * `2 1', `1 2', `3' or `4' to get started). However, it can be
211 * proved to have a unique solution: if the top left square were
212 * empty, then the only option for the top row would be to fill the
213 * two squares in the 1 columns, which would imply the squares
214 * below those were empty, leaving no place for the 2 in the second
215 * row. Contradiction. Hence the top left square is full, and the
216 * unique solution follows easily from that starting point.
217 *
218 * (The game ID for this puzzle is 4x4:2/1/2/1/1.1/2/1/1 , in case
219 * it's useful to anyone.)
220 */
221
222 static int float_compare(const void *av, const void *bv)
223 {
224 const float *a = (const float *)av;
225 const float *b = (const float *)bv;
226 if (*a < *b)
227 return -1;
228 else if (*a > *b)
229 return +1;
230 else
231 return 0;
232 }
233
234 static void generate(random_state *rs, int w, int h, unsigned char *retgrid)
235 {
236 float *fgrid;
237 float *fgrid2;
238 int step, i, j;
239 float threshold;
240
241 fgrid = snewn(w*h, float);
242
243 for (i = 0; i < h; i++) {
244 for (j = 0; j < w; j++) {
245 fgrid[i*w+j] = random_upto(rs, 100000000UL) / 100000000.F;
246 }
247 }
248
249 /*
250 * The above gives a completely random splattering of black and
251 * white cells. We want to gently bias this in favour of _some_
252 * reasonably thick areas of white and black, while retaining
253 * some randomness and fine detail.
254 *
255 * So we evolve the starting grid using a cellular automaton.
256 * Currently, I'm doing something very simple indeed, which is
257 * to set each square to the average of the surrounding nine
258 * cells (or the average of fewer, if we're on a corner).
259 */
260 for (step = 0; step < 1; step++) {
261 fgrid2 = snewn(w*h, float);
262
263 for (i = 0; i < h; i++) {
264 for (j = 0; j < w; j++) {
265 float sx, xbar;
266 int n, p, q;
267
268 /*
269 * Compute the average of the surrounding cells.
270 */
271 n = 0;
272 sx = 0.F;
273 for (p = -1; p <= +1; p++) {
274 for (q = -1; q <= +1; q++) {
275 if (i+p < 0 || i+p >= h || j+q < 0 || j+q >= w)
276 continue;
277 /*
278 * An additional special case not mentioned
279 * above: if a grid dimension is 2xn then
280 * we do not average across that dimension
281 * at all. Otherwise a 2x2 grid would
282 * contain four identical squares.
283 */
284 if ((h==2 && p!=0) || (w==2 && q!=0))
285 continue;
286 n++;
287 sx += fgrid[(i+p)*w+(j+q)];
288 }
289 }
290 xbar = sx / n;
291
292 fgrid2[i*w+j] = xbar;
293 }
294 }
295
296 sfree(fgrid);
297 fgrid = fgrid2;
298 }
299
300 fgrid2 = snewn(w*h, float);
301 memcpy(fgrid2, fgrid, w*h*sizeof(float));
302 qsort(fgrid2, w*h, sizeof(float), float_compare);
303 threshold = fgrid2[w*h/2];
304 sfree(fgrid2);
305
306 for (i = 0; i < h; i++) {
307 for (j = 0; j < w; j++) {
308 retgrid[i*w+j] = (fgrid[i*w+j] >= threshold ? GRID_FULL :
309 GRID_EMPTY);
310 }
311 }
312
313 sfree(fgrid);
314 }
315
316 static int compute_rowdata(int *ret, unsigned char *start, int len, int step)
317 {
318 int i, n;
319
320 n = 0;
321
322 for (i = 0; i < len; i++) {
323 if (start[i*step] == GRID_FULL) {
324 int runlen = 1;
325 while (i+runlen < len && start[(i+runlen)*step] == GRID_FULL)
326 runlen++;
327 ret[n++] = runlen;
328 i += runlen;
329 }
330
331 if (i < len && start[i*step] == GRID_UNKNOWN)
332 return -1;
333 }
334
335 return n;
336 }
337
338 #define UNKNOWN 0
339 #define BLOCK 1
340 #define DOT 2
341 #define STILL_UNKNOWN 3
342
343 static void do_recurse(unsigned char *known, unsigned char *deduced,
344 unsigned char *row, int *data, int len,
345 int freespace, int ndone, int lowest)
346 {
347 int i, j, k;
348
349 if (data[ndone]) {
350 for (i=0; i<=freespace; i++) {
351 j = lowest;
352 for (k=0; k<i; k++) row[j++] = DOT;
353 for (k=0; k<data[ndone]; k++) row[j++] = BLOCK;
354 if (j < len) row[j++] = DOT;
355 do_recurse(known, deduced, row, data, len,
356 freespace-i, ndone+1, j);
357 }
358 } else {
359 for (i=lowest; i<len; i++)
360 row[i] = DOT;
361 for (i=0; i<len; i++)
362 if (known[i] && known[i] != row[i])
363 return;
364 for (i=0; i<len; i++)
365 deduced[i] |= row[i];
366 }
367 }
368
369 static int do_row(unsigned char *known, unsigned char *deduced,
370 unsigned char *row,
371 unsigned char *start, int len, int step, int *data)
372 {
373 int rowlen, i, freespace, done_any;
374
375 freespace = len+1;
376 for (rowlen = 0; data[rowlen]; rowlen++)
377 freespace -= data[rowlen]+1;
378
379 for (i = 0; i < len; i++) {
380 known[i] = start[i*step];
381 deduced[i] = 0;
382 }
383
384 do_recurse(known, deduced, row, data, len, freespace, 0, 0);
385 done_any = FALSE;
386 for (i=0; i<len; i++)
387 if (deduced[i] && deduced[i] != STILL_UNKNOWN && !known[i]) {
388 start[i*step] = deduced[i];
389 done_any = TRUE;
390 }
391 return done_any;
392 }
393
394 static unsigned char *generate_soluble(random_state *rs, int w, int h)
395 {
396 int i, j, done_any, ok, ntries, max;
397 unsigned char *grid, *matrix, *workspace;
398 int *rowdata;
399
400 grid = snewn(w*h, unsigned char);
401 matrix = snewn(w*h, unsigned char);
402 max = max(w, h);
403 workspace = snewn(max*3, unsigned char);
404 rowdata = snewn(max+1, int);
405
406 ntries = 0;
407
408 do {
409 ntries++;
410
411 generate(rs, w, h, grid);
412
413 /*
414 * The game is a bit too easy if any row or column is
415 * completely black or completely white. An exception is
416 * made for rows/columns that are under 3 squares,
417 * otherwise nothing will ever be successfully generated.
418 */
419 ok = TRUE;
420 if (w > 2) {
421 for (i = 0; i < h; i++) {
422 int colours = 0;
423 for (j = 0; j < w; j++)
424 colours |= (grid[i*w+j] == GRID_FULL ? 2 : 1);
425 if (colours != 3)
426 ok = FALSE;
427 }
428 }
429 if (h > 2) {
430 for (j = 0; j < w; j++) {
431 int colours = 0;
432 for (i = 0; i < h; i++)
433 colours |= (grid[i*w+j] == GRID_FULL ? 2 : 1);
434 if (colours != 3)
435 ok = FALSE;
436 }
437 }
438 if (!ok)
439 continue;
440
441 memset(matrix, 0, w*h);
442
443 do {
444 done_any = 0;
445 for (i=0; i<h; i++) {
446 rowdata[compute_rowdata(rowdata, grid+i*w, w, 1)] = 0;
447 done_any |= do_row(workspace, workspace+max, workspace+2*max,
448 matrix+i*w, w, 1, rowdata);
449 }
450 for (i=0; i<w; i++) {
451 rowdata[compute_rowdata(rowdata, grid+i, h, w)] = 0;
452 done_any |= do_row(workspace, workspace+max, workspace+2*max,
453 matrix+i, h, w, rowdata);
454 }
455 } while (done_any);
456
457 ok = TRUE;
458 for (i=0; i<h; i++) {
459 for (j=0; j<w; j++) {
460 if (matrix[i*w+j] == UNKNOWN)
461 ok = FALSE;
462 }
463 }
464 } while (!ok);
465
466 sfree(matrix);
467 sfree(workspace);
468 sfree(rowdata);
469 return grid;
470 }
471
472 struct game_aux_info {
473 int w, h;
474 unsigned char *grid;
475 };
476
477 static char *new_game_desc(game_params *params, random_state *rs,
478 game_aux_info **aux, int interactive)
479 {
480 unsigned char *grid;
481 int i, j, max, rowlen, *rowdata;
482 char intbuf[80], *desc;
483 int desclen, descpos;
484
485 grid = generate_soluble(rs, params->w, params->h);
486 max = max(params->w, params->h);
487 rowdata = snewn(max, int);
488
489 /*
490 * Save the solved game in an aux_info.
491 */
492 {
493 game_aux_info *ai = snew(game_aux_info);
494
495 ai->w = params->w;
496 ai->h = params->h;
497 ai->grid = snewn(ai->w * ai->h, unsigned char);
498 memcpy(ai->grid, grid, ai->w * ai->h);
499
500 *aux = ai;
501 }
502
503 /*
504 * Seed is a slash-separated list of row contents; each row
505 * contents section is a dot-separated list of integers. Row
506 * contents are listed in the order (columns left to right,
507 * then rows top to bottom).
508 *
509 * Simplest way to handle memory allocation is to make two
510 * passes, first computing the seed size and then writing it
511 * out.
512 */
513 desclen = 0;
514 for (i = 0; i < params->w + params->h; i++) {
515 if (i < params->w)
516 rowlen = compute_rowdata(rowdata, grid+i, params->h, params->w);
517 else
518 rowlen = compute_rowdata(rowdata, grid+(i-params->w)*params->w,
519 params->w, 1);
520 if (rowlen > 0) {
521 for (j = 0; j < rowlen; j++) {
522 desclen += 1 + sprintf(intbuf, "%d", rowdata[j]);
523 }
524 } else {
525 desclen++;
526 }
527 }
528 desc = snewn(desclen, char);
529 descpos = 0;
530 for (i = 0; i < params->w + params->h; i++) {
531 if (i < params->w)
532 rowlen = compute_rowdata(rowdata, grid+i, params->h, params->w);
533 else
534 rowlen = compute_rowdata(rowdata, grid+(i-params->w)*params->w,
535 params->w, 1);
536 if (rowlen > 0) {
537 for (j = 0; j < rowlen; j++) {
538 int len = sprintf(desc+descpos, "%d", rowdata[j]);
539 if (j+1 < rowlen)
540 desc[descpos + len] = '.';
541 else
542 desc[descpos + len] = '/';
543 descpos += len+1;
544 }
545 } else {
546 desc[descpos++] = '/';
547 }
548 }
549 assert(descpos == desclen);
550 assert(desc[desclen-1] == '/');
551 desc[desclen-1] = '\0';
552 sfree(rowdata);
553 return desc;
554 }
555
556 static void game_free_aux_info(game_aux_info *aux)
557 {
558 sfree(aux->grid);
559 sfree(aux);
560 }
561
562 static char *validate_desc(game_params *params, char *desc)
563 {
564 int i, n, rowspace;
565 char *p;
566
567 for (i = 0; i < params->w + params->h; i++) {
568 if (i < params->w)
569 rowspace = params->h + 1;
570 else
571 rowspace = params->w + 1;
572
573 if (*desc && isdigit((unsigned char)*desc)) {
574 do {
575 p = desc;
576 while (desc && isdigit((unsigned char)*desc)) desc++;
577 n = atoi(p);
578 rowspace -= n+1;
579
580 if (rowspace < 0) {
581 if (i < params->w)
582 return "at least one column contains more numbers than will fit";
583 else
584 return "at least one row contains more numbers than will fit";
585 }
586 } while (*desc++ == '.');
587 } else {
588 desc++; /* expect a slash immediately */
589 }
590
591 if (desc[-1] == '/') {
592 if (i+1 == params->w + params->h)
593 return "too many row/column specifications";
594 } else if (desc[-1] == '\0') {
595 if (i+1 < params->w + params->h)
596 return "too few row/column specifications";
597 } else
598 return "unrecognised character in game specification";
599 }
600
601 return NULL;
602 }
603
604 static game_state *new_game(midend_data *me, game_params *params, char *desc)
605 {
606 int i;
607 char *p;
608 game_state *state = snew(game_state);
609
610 state->w = params->w;
611 state->h = params->h;
612
613 state->grid = snewn(state->w * state->h, unsigned char);
614 memset(state->grid, GRID_UNKNOWN, state->w * state->h);
615
616 state->rowsize = max(state->w, state->h);
617 state->rowdata = snewn(state->rowsize * (state->w + state->h), int);
618 state->rowlen = snewn(state->w + state->h, int);
619
620 state->completed = state->cheated = FALSE;
621
622 for (i = 0; i < params->w + params->h; i++) {
623 state->rowlen[i] = 0;
624 if (*desc && isdigit((unsigned char)*desc)) {
625 do {
626 p = desc;
627 while (desc && isdigit((unsigned char)*desc)) desc++;
628 state->rowdata[state->rowsize * i + state->rowlen[i]++] =
629 atoi(p);
630 } while (*desc++ == '.');
631 } else {
632 desc++; /* expect a slash immediately */
633 }
634 }
635
636 return state;
637 }
638
639 static game_state *dup_game(game_state *state)
640 {
641 game_state *ret = snew(game_state);
642
643 ret->w = state->w;
644 ret->h = state->h;
645
646 ret->grid = snewn(ret->w * ret->h, unsigned char);
647 memcpy(ret->grid, state->grid, ret->w * ret->h);
648
649 ret->rowsize = state->rowsize;
650 ret->rowdata = snewn(ret->rowsize * (ret->w + ret->h), int);
651 ret->rowlen = snewn(ret->w + ret->h, int);
652 memcpy(ret->rowdata, state->rowdata,
653 ret->rowsize * (ret->w + ret->h) * sizeof(int));
654 memcpy(ret->rowlen, state->rowlen,
655 (ret->w + ret->h) * sizeof(int));
656
657 ret->completed = state->completed;
658 ret->cheated = state->cheated;
659
660 return ret;
661 }
662
663 static void free_game(game_state *state)
664 {
665 sfree(state->rowdata);
666 sfree(state->rowlen);
667 sfree(state->grid);
668 sfree(state);
669 }
670
671 static game_state *solve_game(game_state *state, game_aux_info *ai,
672 char **error)
673 {
674 game_state *ret;
675
676 ret = dup_game(state);
677 ret->completed = ret->cheated = TRUE;
678
679 /*
680 * If we already have the solved state in an aux_info, copy it
681 * out.
682 */
683 if (ai) {
684
685 assert(ret->w == ai->w);
686 assert(ret->h == ai->h);
687 memcpy(ret->grid, ai->grid, ai->w * ai->h);
688
689 } else {
690 int w = state->w, h = state->h, i, j, done_any, max;
691 unsigned char *matrix, *workspace;
692 int *rowdata;
693
694 matrix = snewn(w*h, unsigned char);
695 max = max(w, h);
696 workspace = snewn(max*3, unsigned char);
697 rowdata = snewn(max+1, int);
698
699 memset(matrix, 0, w*h);
700
701 do {
702 done_any = 0;
703 for (i=0; i<h; i++) {
704 memcpy(rowdata, state->rowdata + state->rowsize*(w+i),
705 max*sizeof(int));
706 rowdata[state->rowlen[w+i]] = 0;
707 done_any |= do_row(workspace, workspace+max, workspace+2*max,
708 matrix+i*w, w, 1, rowdata);
709 }
710 for (i=0; i<w; i++) {
711 memcpy(rowdata, state->rowdata + state->rowsize*i, max*sizeof(int));
712 rowdata[state->rowlen[i]] = 0;
713 done_any |= do_row(workspace, workspace+max, workspace+2*max,
714 matrix+i, h, w, rowdata);
715 }
716 } while (done_any);
717
718 for (i = 0; i < h; i++) {
719 for (j = 0; j < w; j++) {
720 int c = (matrix[i*w+j] == BLOCK ? GRID_FULL :
721 matrix[i*w+j] == DOT ? GRID_EMPTY : GRID_UNKNOWN);
722 ret->grid[i*w+j] = c;
723 if (c == GRID_UNKNOWN)
724 ret->completed = FALSE;
725 }
726 }
727
728 if (!ret->completed) {
729 free_game(ret);
730 *error = "Solving algorithm cannot complete this puzzle";
731 return NULL;
732 }
733 }
734
735 return ret;
736 }
737
738 static char *game_text_format(game_state *state)
739 {
740 return NULL;
741 }
742
743 struct game_ui {
744 int dragging;
745 int drag_start_x;
746 int drag_start_y;
747 int drag_end_x;
748 int drag_end_y;
749 int drag, release, state;
750 };
751
752 static game_ui *new_ui(game_state *state)
753 {
754 game_ui *ret;
755
756 ret = snew(game_ui);
757 ret->dragging = FALSE;
758
759 return ret;
760 }
761
762 static void free_ui(game_ui *ui)
763 {
764 sfree(ui);
765 }
766
767 static game_state *make_move(game_state *from, game_ui *ui, game_drawstate *ds,
768 int x, int y, int button) {
769 game_state *ret;
770
771 button &= ~MOD_MASK;
772
773 x = FROMCOORD(from->w, x);
774 y = FROMCOORD(from->h, y);
775
776 if (x >= 0 && x < from->w && y >= 0 && y < from->h &&
777 (button == LEFT_BUTTON || button == RIGHT_BUTTON ||
778 button == MIDDLE_BUTTON)) {
779
780 ui->dragging = TRUE;
781
782 if (button == LEFT_BUTTON) {
783 ui->drag = LEFT_DRAG;
784 ui->release = LEFT_RELEASE;
785 ui->state = GRID_FULL;
786 } else if (button == RIGHT_BUTTON) {
787 ui->drag = RIGHT_DRAG;
788 ui->release = RIGHT_RELEASE;
789 ui->state = GRID_EMPTY;
790 } else /* if (button == MIDDLE_BUTTON) */ {
791 ui->drag = MIDDLE_DRAG;
792 ui->release = MIDDLE_RELEASE;
793 ui->state = GRID_UNKNOWN;
794 }
795
796 ui->drag_start_x = ui->drag_end_x = x;
797 ui->drag_start_y = ui->drag_end_y = y;
798
799 return from; /* UI activity occurred */
800 }
801
802 if (ui->dragging && button == ui->drag) {
803 /*
804 * There doesn't seem much point in allowing a rectangle
805 * drag; people will generally only want to drag a single
806 * horizontal or vertical line, so we make that easy by
807 * snapping to it.
808 *
809 * Exception: if we're _middle_-button dragging to tag
810 * things as UNKNOWN, we may well want to trash an entire
811 * area and start over!
812 */
813 if (ui->state != GRID_UNKNOWN) {
814 if (abs(x - ui->drag_start_x) > abs(y - ui->drag_start_y))
815 y = ui->drag_start_y;
816 else
817 x = ui->drag_start_x;
818 }
819
820 if (x < 0) x = 0;
821 if (y < 0) y = 0;
822 if (x >= from->w) x = from->w - 1;
823 if (y >= from->h) y = from->h - 1;
824
825 ui->drag_end_x = x;
826 ui->drag_end_y = y;
827
828 return from; /* UI activity occurred */
829 }
830
831 if (ui->dragging && button == ui->release) {
832 int x1, x2, y1, y2, xx, yy;
833 int move_needed = FALSE;
834
835 x1 = min(ui->drag_start_x, ui->drag_end_x);
836 x2 = max(ui->drag_start_x, ui->drag_end_x);
837 y1 = min(ui->drag_start_y, ui->drag_end_y);
838 y2 = max(ui->drag_start_y, ui->drag_end_y);
839
840 for (yy = y1; yy <= y2; yy++)
841 for (xx = x1; xx <= x2; xx++)
842 if (from->grid[yy * from->w + xx] != ui->state)
843 move_needed = TRUE;
844
845 ui->dragging = FALSE;
846
847 if (move_needed) {
848 ret = dup_game(from);
849 for (yy = y1; yy <= y2; yy++)
850 for (xx = x1; xx <= x2; xx++)
851 ret->grid[yy * ret->w + xx] = ui->state;
852
853 /*
854 * An actual change, so check to see if we've completed
855 * the game.
856 */
857 if (!ret->completed) {
858 int *rowdata = snewn(ret->rowsize, int);
859 int i, len;
860
861 ret->completed = TRUE;
862
863 for (i=0; i<ret->w; i++) {
864 len = compute_rowdata(rowdata,
865 ret->grid+i, ret->h, ret->w);
866 if (len != ret->rowlen[i] ||
867 memcmp(ret->rowdata+i*ret->rowsize, rowdata,
868 len * sizeof(int))) {
869 ret->completed = FALSE;
870 break;
871 }
872 }
873 for (i=0; i<ret->h; i++) {
874 len = compute_rowdata(rowdata,
875 ret->grid+i*ret->w, ret->w, 1);
876 if (len != ret->rowlen[i+ret->w] ||
877 memcmp(ret->rowdata+(i+ret->w)*ret->rowsize, rowdata,
878 len * sizeof(int))) {
879 ret->completed = FALSE;
880 break;
881 }
882 }
883
884 sfree(rowdata);
885 }
886
887 return ret;
888 } else
889 return from; /* UI activity occurred */
890 }
891
892 return NULL;
893 }
894
895 /* ----------------------------------------------------------------------
896 * Drawing routines.
897 */
898
899 struct game_drawstate {
900 int started;
901 int w, h;
902 unsigned char *visible;
903 };
904
905 static void game_size(game_params *params, int *x, int *y)
906 {
907 *x = SIZE(params->w);
908 *y = SIZE(params->h);
909 }
910
911 static float *game_colours(frontend *fe, game_state *state, int *ncolours)
912 {
913 float *ret = snewn(3 * NCOLOURS, float);
914
915 frontend_default_colour(fe, &ret[COL_BACKGROUND * 3]);
916
917 ret[COL_GRID * 3 + 0] = 0.3F;
918 ret[COL_GRID * 3 + 1] = 0.3F;
919 ret[COL_GRID * 3 + 2] = 0.3F;
920
921 ret[COL_UNKNOWN * 3 + 0] = 0.5F;
922 ret[COL_UNKNOWN * 3 + 1] = 0.5F;
923 ret[COL_UNKNOWN * 3 + 2] = 0.5F;
924
925 ret[COL_FULL * 3 + 0] = 0.0F;
926 ret[COL_FULL * 3 + 1] = 0.0F;
927 ret[COL_FULL * 3 + 2] = 0.0F;
928
929 ret[COL_EMPTY * 3 + 0] = 1.0F;
930 ret[COL_EMPTY * 3 + 1] = 1.0F;
931 ret[COL_EMPTY * 3 + 2] = 1.0F;
932
933 *ncolours = NCOLOURS;
934 return ret;
935 }
936
937 static game_drawstate *game_new_drawstate(game_state *state)
938 {
939 struct game_drawstate *ds = snew(struct game_drawstate);
940
941 ds->started = FALSE;
942 ds->w = state->w;
943 ds->h = state->h;
944 ds->visible = snewn(ds->w * ds->h, unsigned char);
945 memset(ds->visible, 255, ds->w * ds->h);
946
947 return ds;
948 }
949
950 static void game_free_drawstate(game_drawstate *ds)
951 {
952 sfree(ds->visible);
953 sfree(ds);
954 }
955
956 static void grid_square(frontend *fe, game_drawstate *ds,
957 int y, int x, int state)
958 {
959 int xl, xr, yt, yb;
960
961 draw_rect(fe, TOCOORD(ds->w, x), TOCOORD(ds->h, y),
962 TILE_SIZE, TILE_SIZE, COL_GRID);
963
964 xl = (x % 5 == 0 ? 1 : 0);
965 yt = (y % 5 == 0 ? 1 : 0);
966 xr = (x % 5 == 4 || x == ds->w-1 ? 1 : 0);
967 yb = (y % 5 == 4 || y == ds->h-1 ? 1 : 0);
968
969 draw_rect(fe, TOCOORD(ds->w, x) + 1 + xl, TOCOORD(ds->h, y) + 1 + yt,
970 TILE_SIZE - xl - xr - 1, TILE_SIZE - yt - yb - 1,
971 (state == GRID_FULL ? COL_FULL :
972 state == GRID_EMPTY ? COL_EMPTY : COL_UNKNOWN));
973
974 draw_update(fe, TOCOORD(ds->w, x), TOCOORD(ds->h, y),
975 TILE_SIZE, TILE_SIZE);
976 }
977
978 static void game_redraw(frontend *fe, game_drawstate *ds, game_state *oldstate,
979 game_state *state, int dir, game_ui *ui,
980 float animtime, float flashtime)
981 {
982 int i, j;
983 int x1, x2, y1, y2;
984
985 if (!ds->started) {
986 /*
987 * The initial contents of the window are not guaranteed
988 * and can vary with front ends. To be on the safe side,
989 * all games should start by drawing a big background-
990 * colour rectangle covering the whole window.
991 */
992 draw_rect(fe, 0, 0, SIZE(ds->w), SIZE(ds->h), COL_BACKGROUND);
993
994 /*
995 * Draw the numbers.
996 */
997 for (i = 0; i < ds->w + ds->h; i++) {
998 int rowlen = state->rowlen[i];
999 int *rowdata = state->rowdata + state->rowsize * i;
1000 int nfit;
1001
1002 /*
1003 * Normally I space the numbers out by the same
1004 * distance as the tile size. However, if there are
1005 * more numbers than available spaces, I have to squash
1006 * them up a bit.
1007 */
1008 nfit = max(rowlen, TLBORDER(ds->h))-1;
1009 assert(nfit > 0);
1010
1011 for (j = 0; j < rowlen; j++) {
1012 int x, y;
1013 char str[80];
1014
1015 if (i < ds->w) {
1016 x = TOCOORD(ds->w, i);
1017 y = BORDER + TILE_SIZE * (TLBORDER(ds->h)-1);
1018 y -= ((rowlen-j-1)*TILE_SIZE) * (TLBORDER(ds->h)-1) / nfit;
1019 } else {
1020 y = TOCOORD(ds->h, i - ds->w);
1021 x = BORDER + TILE_SIZE * (TLBORDER(ds->w)-1);
1022 x -= ((rowlen-j-1)*TILE_SIZE) * (TLBORDER(ds->h)-1) / nfit;
1023 }
1024
1025 sprintf(str, "%d", rowdata[j]);
1026 draw_text(fe, x+TILE_SIZE/2, y+TILE_SIZE/2, FONT_VARIABLE,
1027 TILE_SIZE/2, ALIGN_HCENTRE | ALIGN_VCENTRE,
1028 COL_FULL, str); /* FIXME: COL_TEXT */
1029 }
1030 }
1031
1032 /*
1033 * Draw the grid outline.
1034 */
1035 draw_rect(fe, TOCOORD(ds->w, 0) - 1, TOCOORD(ds->h, 0) - 1,
1036 ds->w * TILE_SIZE + 3, ds->h * TILE_SIZE + 3,
1037 COL_GRID);
1038
1039 ds->started = TRUE;
1040
1041 draw_update(fe, 0, 0, SIZE(ds->w), SIZE(ds->h));
1042 }
1043
1044 if (ui->dragging) {
1045 x1 = min(ui->drag_start_x, ui->drag_end_x);
1046 x2 = max(ui->drag_start_x, ui->drag_end_x);
1047 y1 = min(ui->drag_start_y, ui->drag_end_y);
1048 y2 = max(ui->drag_start_y, ui->drag_end_y);
1049 } else {
1050 x1 = x2 = y1 = y2 = -1; /* placate gcc warnings */
1051 }
1052
1053 /*
1054 * Now draw any grid squares which have changed since last
1055 * redraw.
1056 */
1057 for (i = 0; i < ds->h; i++) {
1058 for (j = 0; j < ds->w; j++) {
1059 int val;
1060
1061 /*
1062 * Work out what state this square should be drawn in,
1063 * taking any current drag operation into account.
1064 */
1065 if (ui->dragging && x1 <= j && j <= x2 && y1 <= i && i <= y2)
1066 val = ui->state;
1067 else
1068 val = state->grid[i * state->w + j];
1069
1070 /*
1071 * Briefly invert everything twice during a completion
1072 * flash.
1073 */
1074 if (flashtime > 0 &&
1075 (flashtime <= FLASH_TIME/3 || flashtime >= FLASH_TIME*2/3) &&
1076 val != GRID_UNKNOWN)
1077 val = (GRID_FULL ^ GRID_EMPTY) ^ val;
1078
1079 if (ds->visible[i * ds->w + j] != val) {
1080 grid_square(fe, ds, i, j, val);
1081 ds->visible[i * ds->w + j] = val;
1082 }
1083 }
1084 }
1085 }
1086
1087 static float game_anim_length(game_state *oldstate,
1088 game_state *newstate, int dir, game_ui *ui)
1089 {
1090 return 0.0F;
1091 }
1092
1093 static float game_flash_length(game_state *oldstate,
1094 game_state *newstate, int dir, game_ui *ui)
1095 {
1096 if (!oldstate->completed && newstate->completed &&
1097 !oldstate->cheated && !newstate->cheated)
1098 return FLASH_TIME;
1099 return 0.0F;
1100 }
1101
1102 static int game_wants_statusbar(void)
1103 {
1104 return FALSE;
1105 }
1106
1107 static int game_timing_state(game_state *state)
1108 {
1109 return TRUE;
1110 }
1111
1112 #ifdef COMBINED
1113 #define thegame pattern
1114 #endif
1115
1116 const struct game thegame = {
1117 "Pattern", "games.pattern",
1118 default_params,
1119 game_fetch_preset,
1120 decode_params,
1121 encode_params,
1122 free_params,
1123 dup_params,
1124 TRUE, game_configure, custom_params,
1125 validate_params,
1126 new_game_desc,
1127 game_free_aux_info,
1128 validate_desc,
1129 new_game,
1130 dup_game,
1131 free_game,
1132 TRUE, solve_game,
1133 FALSE, game_text_format,
1134 new_ui,
1135 free_ui,
1136 make_move,
1137 game_size,
1138 game_colours,
1139 game_new_drawstate,
1140 game_free_drawstate,
1141 game_redraw,
1142 game_anim_length,
1143 game_flash_length,
1144 game_wants_statusbar,
1145 FALSE, game_timing_state,
1146 };
1147
1148 #ifdef STANDALONE_SOLVER
1149
1150 /*
1151 * gcc -DSTANDALONE_SOLVER -o patternsolver pattern.c malloc.c
1152 */
1153
1154 #include <stdarg.h>
1155
1156 void frontend_default_colour(frontend *fe, float *output) {}
1157 void draw_text(frontend *fe, int x, int y, int fonttype, int fontsize,
1158 int align, int colour, char *text) {}
1159 void draw_rect(frontend *fe, int x, int y, int w, int h, int colour) {}
1160 void draw_line(frontend *fe, int x1, int y1, int x2, int y2, int colour) {}
1161 void draw_polygon(frontend *fe, int *coords, int npoints,
1162 int fill, int colour) {}
1163 void clip(frontend *fe, int x, int y, int w, int h) {}
1164 void unclip(frontend *fe) {}
1165 void start_draw(frontend *fe) {}
1166 void draw_update(frontend *fe, int x, int y, int w, int h) {}
1167 void end_draw(frontend *fe) {}
1168 unsigned long random_upto(random_state *state, unsigned long limit)
1169 { assert(!"Shouldn't get randomness"); return 0; }
1170
1171 void fatal(char *fmt, ...)
1172 {
1173 va_list ap;
1174
1175 fprintf(stderr, "fatal error: ");
1176
1177 va_start(ap, fmt);
1178 vfprintf(stderr, fmt, ap);
1179 va_end(ap);
1180
1181 fprintf(stderr, "\n");
1182 exit(1);
1183 }
1184
1185 int main(int argc, char **argv)
1186 {
1187 game_params *p;
1188 game_state *s;
1189 int recurse = TRUE;
1190 char *id = NULL, *desc, *err;
1191 int y, x;
1192 int grade = FALSE;
1193
1194 while (--argc > 0) {
1195 char *p = *++argv;
1196 if (*p == '-') {
1197 fprintf(stderr, "%s: unrecognised option `%s'\n", argv[0]);
1198 return 1;
1199 } else {
1200 id = p;
1201 }
1202 }
1203
1204 if (!id) {
1205 fprintf(stderr, "usage: %s <game_id>\n", argv[0]);
1206 return 1;
1207 }
1208
1209 desc = strchr(id, ':');
1210 if (!desc) {
1211 fprintf(stderr, "%s: game id expects a colon in it\n", argv[0]);
1212 return 1;
1213 }
1214 *desc++ = '\0';
1215
1216 p = default_params();
1217 decode_params(p, id);
1218 err = validate_desc(p, desc);
1219 if (err) {
1220 fprintf(stderr, "%s: %s\n", argv[0], err);
1221 return 1;
1222 }
1223 s = new_game(p, desc);
1224
1225 {
1226 int w = p->w, h = p->h, i, j, done_any, max;
1227 unsigned char *matrix, *workspace;
1228 int *rowdata;
1229
1230 matrix = snewn(w*h, unsigned char);
1231 max = max(w, h);
1232 workspace = snewn(max*3, unsigned char);
1233 rowdata = snewn(max+1, int);
1234
1235 memset(matrix, 0, w*h);
1236
1237 do {
1238 done_any = 0;
1239 for (i=0; i<h; i++) {
1240 memcpy(rowdata, s->rowdata + s->rowsize*(w+i),
1241 max*sizeof(int));
1242 rowdata[s->rowlen[w+i]] = 0;
1243 done_any |= do_row(workspace, workspace+max, workspace+2*max,
1244 matrix+i*w, w, 1, rowdata);
1245 }
1246 for (i=0; i<w; i++) {
1247 memcpy(rowdata, s->rowdata + s->rowsize*i, max*sizeof(int));
1248 rowdata[s->rowlen[i]] = 0;
1249 done_any |= do_row(workspace, workspace+max, workspace+2*max,
1250 matrix+i, h, w, rowdata);
1251 }
1252 } while (done_any);
1253
1254 for (i = 0; i < h; i++) {
1255 for (j = 0; j < w; j++) {
1256 int c = (matrix[i*w+j] == UNKNOWN ? '?' :
1257 matrix[i*w+j] == BLOCK ? '#' :
1258 matrix[i*w+j] == DOT ? '.' :
1259 '!');
1260 putchar(c);
1261 }
1262 printf("\n");
1263 }
1264 }
1265
1266 return 0;
1267 }
1268
1269 #endif