2 * pattern.c: the pattern-reconstruction game known as `nonograms'.
24 #define PREFERRED_TILE_SIZE 24
25 #define TILE_SIZE (ds->tilesize)
26 #define BORDER (3 * TILE_SIZE / 4)
27 #define TLBORDER(d) ( (d) / 5 + 2 )
28 #define GUTTER (TILE_SIZE / 2)
30 #define FROMCOORD(d, x) \
31 ( ((x) - (BORDER + GUTTER + TILE_SIZE * TLBORDER(d))) / TILE_SIZE )
33 #define SIZE(d) (2*BORDER + GUTTER + TILE_SIZE * (TLBORDER(d) + (d)))
34 #define GETTILESIZE(d, w) ((double)w / (2.0 + (double)TLBORDER(d) + (double)(d)))
36 #define TOCOORD(d, x) (BORDER + GUTTER + TILE_SIZE * (TLBORDER(d) + (x)))
42 #define GRID_UNKNOWN 2
50 int *rowdata
, *rowlen
;
51 int completed
, cheated
;
54 #define FLASH_TIME 0.13F
56 static game_params
*default_params(void)
58 game_params
*ret
= snew(game_params
);
65 static const struct game_params pattern_presets
[] = {
75 static int game_fetch_preset(int i
, char **name
, game_params
**params
)
80 if (i
< 0 || i
>= lenof(pattern_presets
))
83 ret
= snew(game_params
);
84 *ret
= pattern_presets
[i
];
86 sprintf(str
, "%dx%d", ret
->w
, ret
->h
);
93 static void free_params(game_params
*params
)
98 static game_params
*dup_params(game_params
*params
)
100 game_params
*ret
= snew(game_params
);
101 *ret
= *params
; /* structure copy */
105 static void decode_params(game_params
*ret
, char const *string
)
107 char const *p
= string
;
110 while (*p
&& isdigit((unsigned char)*p
)) p
++;
114 while (*p
&& isdigit((unsigned char)*p
)) p
++;
120 static char *encode_params(game_params
*params
, int full
)
125 len
= sprintf(ret
, "%dx%d", params
->w
, params
->h
);
126 assert(len
< lenof(ret
));
132 static config_item
*game_configure(game_params
*params
)
137 ret
= snewn(3, config_item
);
139 ret
[0].name
= "Width";
140 ret
[0].type
= C_STRING
;
141 sprintf(buf
, "%d", params
->w
);
142 ret
[0].sval
= dupstr(buf
);
145 ret
[1].name
= "Height";
146 ret
[1].type
= C_STRING
;
147 sprintf(buf
, "%d", params
->h
);
148 ret
[1].sval
= dupstr(buf
);
159 static game_params
*custom_params(config_item
*cfg
)
161 game_params
*ret
= snew(game_params
);
163 ret
->w
= atoi(cfg
[0].sval
);
164 ret
->h
= atoi(cfg
[1].sval
);
169 static char *validate_params(game_params
*params
, int full
)
171 if (params
->w
<= 0 || params
->h
<= 0)
172 return "Width and height must both be greater than zero";
176 /* ----------------------------------------------------------------------
177 * Puzzle generation code.
179 * For this particular puzzle, it seemed important to me to ensure
180 * a unique solution. I do this the brute-force way, by having a
181 * solver algorithm alongside the generator, and repeatedly
182 * generating a random grid until I find one whose solution is
183 * unique. It turns out that this isn't too onerous on a modern PC
184 * provided you keep grid size below around 30. Any offers of
185 * better algorithms, however, will be very gratefully received.
187 * Another annoyance of this approach is that it limits the
188 * available puzzles to those solvable by the algorithm I've used.
189 * My algorithm only ever considers a single row or column at any
190 * one time, which means it's incapable of solving the following
191 * difficult example (found by Bella Image around 1995/6, when she
192 * and I were both doing maths degrees):
206 * Obviously this cannot be solved by a one-row-or-column-at-a-time
207 * algorithm (it would require at least one row or column reading
208 * `2 1', `1 2', `3' or `4' to get started). However, it can be
209 * proved to have a unique solution: if the top left square were
210 * empty, then the only option for the top row would be to fill the
211 * two squares in the 1 columns, which would imply the squares
212 * below those were empty, leaving no place for the 2 in the second
213 * row. Contradiction. Hence the top left square is full, and the
214 * unique solution follows easily from that starting point.
216 * (The game ID for this puzzle is 4x4:2/1/2/1/1.1/2/1/1 , in case
217 * it's useful to anyone.)
220 static int float_compare(const void *av
, const void *bv
)
222 const float *a
= (const float *)av
;
223 const float *b
= (const float *)bv
;
232 static void generate(random_state
*rs
, int w
, int h
, unsigned char *retgrid
)
239 fgrid
= snewn(w
*h
, float);
241 for (i
= 0; i
< h
; i
++) {
242 for (j
= 0; j
< w
; j
++) {
243 fgrid
[i
*w
+j
] = random_upto(rs
, 100000000UL) / 100000000.F
;
248 * The above gives a completely random splattering of black and
249 * white cells. We want to gently bias this in favour of _some_
250 * reasonably thick areas of white and black, while retaining
251 * some randomness and fine detail.
253 * So we evolve the starting grid using a cellular automaton.
254 * Currently, I'm doing something very simple indeed, which is
255 * to set each square to the average of the surrounding nine
256 * cells (or the average of fewer, if we're on a corner).
258 for (step
= 0; step
< 1; step
++) {
259 fgrid2
= snewn(w
*h
, float);
261 for (i
= 0; i
< h
; i
++) {
262 for (j
= 0; j
< w
; j
++) {
267 * Compute the average of the surrounding cells.
271 for (p
= -1; p
<= +1; p
++) {
272 for (q
= -1; q
<= +1; q
++) {
273 if (i
+p
< 0 || i
+p
>= h
|| j
+q
< 0 || j
+q
>= w
)
276 * An additional special case not mentioned
277 * above: if a grid dimension is 2xn then
278 * we do not average across that dimension
279 * at all. Otherwise a 2x2 grid would
280 * contain four identical squares.
282 if ((h
==2 && p
!=0) || (w
==2 && q
!=0))
285 sx
+= fgrid
[(i
+p
)*w
+(j
+q
)];
290 fgrid2
[i
*w
+j
] = xbar
;
298 fgrid2
= snewn(w
*h
, float);
299 memcpy(fgrid2
, fgrid
, w
*h
*sizeof(float));
300 qsort(fgrid2
, w
*h
, sizeof(float), float_compare
);
301 threshold
= fgrid2
[w
*h
/2];
304 for (i
= 0; i
< h
; i
++) {
305 for (j
= 0; j
< w
; j
++) {
306 retgrid
[i
*w
+j
] = (fgrid
[i
*w
+j
] >= threshold ? GRID_FULL
:
314 static int compute_rowdata(int *ret
, unsigned char *start
, int len
, int step
)
320 for (i
= 0; i
< len
; i
++) {
321 if (start
[i
*step
] == GRID_FULL
) {
323 while (i
+runlen
< len
&& start
[(i
+runlen
)*step
] == GRID_FULL
)
329 if (i
< len
&& start
[i
*step
] == GRID_UNKNOWN
)
339 #define STILL_UNKNOWN 3
341 static void do_recurse(unsigned char *known
, unsigned char *deduced
,
342 unsigned char *row
, int *data
, int len
,
343 int freespace
, int ndone
, int lowest
)
348 for (i
=0; i
<=freespace
; i
++) {
350 for (k
=0; k
<i
; k
++) row
[j
++] = DOT
;
351 for (k
=0; k
<data
[ndone
]; k
++) row
[j
++] = BLOCK
;
352 if (j
< len
) row
[j
++] = DOT
;
353 do_recurse(known
, deduced
, row
, data
, len
,
354 freespace
-i
, ndone
+1, j
);
357 for (i
=lowest
; i
<len
; i
++)
359 for (i
=0; i
<len
; i
++)
360 if (known
[i
] && known
[i
] != row
[i
])
362 for (i
=0; i
<len
; i
++)
363 deduced
[i
] |= row
[i
];
367 static int do_row(unsigned char *known
, unsigned char *deduced
,
369 unsigned char *start
, int len
, int step
, int *data
)
371 int rowlen
, i
, freespace
, done_any
;
374 for (rowlen
= 0; data
[rowlen
]; rowlen
++)
375 freespace
-= data
[rowlen
]+1;
377 for (i
= 0; i
< len
; i
++) {
378 known
[i
] = start
[i
*step
];
382 do_recurse(known
, deduced
, row
, data
, len
, freespace
, 0, 0);
384 for (i
=0; i
<len
; i
++)
385 if (deduced
[i
] && deduced
[i
] != STILL_UNKNOWN
&& !known
[i
]) {
386 start
[i
*step
] = deduced
[i
];
392 static unsigned char *generate_soluble(random_state
*rs
, int w
, int h
)
394 int i
, j
, done_any
, ok
, ntries
, max
;
395 unsigned char *grid
, *matrix
, *workspace
;
398 grid
= snewn(w
*h
, unsigned char);
399 matrix
= snewn(w
*h
, unsigned char);
401 workspace
= snewn(max
*3, unsigned char);
402 rowdata
= snewn(max
+1, int);
409 generate(rs
, w
, h
, grid
);
412 * The game is a bit too easy if any row or column is
413 * completely black or completely white. An exception is
414 * made for rows/columns that are under 3 squares,
415 * otherwise nothing will ever be successfully generated.
419 for (i
= 0; i
< h
; i
++) {
421 for (j
= 0; j
< w
; j
++)
422 colours
|= (grid
[i
*w
+j
] == GRID_FULL ?
2 : 1);
428 for (j
= 0; j
< w
; j
++) {
430 for (i
= 0; i
< h
; i
++)
431 colours
|= (grid
[i
*w
+j
] == GRID_FULL ?
2 : 1);
439 memset(matrix
, 0, w
*h
);
443 for (i
=0; i
<h
; i
++) {
444 rowdata
[compute_rowdata(rowdata
, grid
+i
*w
, w
, 1)] = 0;
445 done_any
|= do_row(workspace
, workspace
+max
, workspace
+2*max
,
446 matrix
+i
*w
, w
, 1, rowdata
);
448 for (i
=0; i
<w
; i
++) {
449 rowdata
[compute_rowdata(rowdata
, grid
+i
, h
, w
)] = 0;
450 done_any
|= do_row(workspace
, workspace
+max
, workspace
+2*max
,
451 matrix
+i
, h
, w
, rowdata
);
456 for (i
=0; i
<h
; i
++) {
457 for (j
=0; j
<w
; j
++) {
458 if (matrix
[i
*w
+j
] == UNKNOWN
)
470 static char *new_game_desc(game_params
*params
, random_state
*rs
,
471 char **aux
, int interactive
)
474 int i
, j
, max
, rowlen
, *rowdata
;
475 char intbuf
[80], *desc
;
476 int desclen
, descpos
;
478 grid
= generate_soluble(rs
, params
->w
, params
->h
);
479 max
= max(params
->w
, params
->h
);
480 rowdata
= snewn(max
, int);
483 * Save the solved game in aux.
486 char *ai
= snewn(params
->w
* params
->h
+ 2, char);
489 * String format is exactly the same as a solve move, so we
490 * can just dupstr this in solve_game().
495 for (i
= 0; i
< params
->w
* params
->h
; i
++)
496 ai
[i
+1] = grid
[i
] ?
'1' : '0';
498 ai
[params
->w
* params
->h
+ 1] = '\0';
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).
509 * Simplest way to handle memory allocation is to make two
510 * passes, first computing the seed size and then writing it
514 for (i
= 0; i
< params
->w
+ params
->h
; i
++) {
516 rowlen
= compute_rowdata(rowdata
, grid
+i
, params
->h
, params
->w
);
518 rowlen
= compute_rowdata(rowdata
, grid
+(i
-params
->w
)*params
->w
,
521 for (j
= 0; j
< rowlen
; j
++) {
522 desclen
+= 1 + sprintf(intbuf
, "%d", rowdata
[j
]);
528 desc
= snewn(desclen
, char);
530 for (i
= 0; i
< params
->w
+ params
->h
; i
++) {
532 rowlen
= compute_rowdata(rowdata
, grid
+i
, params
->h
, params
->w
);
534 rowlen
= compute_rowdata(rowdata
, grid
+(i
-params
->w
)*params
->w
,
537 for (j
= 0; j
< rowlen
; j
++) {
538 int len
= sprintf(desc
+descpos
, "%d", rowdata
[j
]);
540 desc
[descpos
+ len
] = '.';
542 desc
[descpos
+ len
] = '/';
546 desc
[descpos
++] = '/';
549 assert(descpos
== desclen
);
550 assert(desc
[desclen
-1] == '/');
551 desc
[desclen
-1] = '\0';
557 static char *validate_desc(game_params
*params
, char *desc
)
562 for (i
= 0; i
< params
->w
+ params
->h
; i
++) {
564 rowspace
= params
->h
+ 1;
566 rowspace
= params
->w
+ 1;
568 if (*desc
&& isdigit((unsigned char)*desc
)) {
571 while (desc
&& isdigit((unsigned char)*desc
)) desc
++;
577 return "at least one column contains more numbers than will fit";
579 return "at least one row contains more numbers than will fit";
581 } while (*desc
++ == '.');
583 desc
++; /* expect a slash immediately */
586 if (desc
[-1] == '/') {
587 if (i
+1 == params
->w
+ params
->h
)
588 return "too many row/column specifications";
589 } else if (desc
[-1] == '\0') {
590 if (i
+1 < params
->w
+ params
->h
)
591 return "too few row/column specifications";
593 return "unrecognised character in game specification";
599 static game_state
*new_game(midend
*me
, game_params
*params
, char *desc
)
603 game_state
*state
= snew(game_state
);
605 state
->w
= params
->w
;
606 state
->h
= params
->h
;
608 state
->grid
= snewn(state
->w
* state
->h
, unsigned char);
609 memset(state
->grid
, GRID_UNKNOWN
, state
->w
* state
->h
);
611 state
->rowsize
= max(state
->w
, state
->h
);
612 state
->rowdata
= snewn(state
->rowsize
* (state
->w
+ state
->h
), int);
613 state
->rowlen
= snewn(state
->w
+ state
->h
, int);
615 state
->completed
= state
->cheated
= FALSE
;
617 for (i
= 0; i
< params
->w
+ params
->h
; i
++) {
618 state
->rowlen
[i
] = 0;
619 if (*desc
&& isdigit((unsigned char)*desc
)) {
622 while (desc
&& isdigit((unsigned char)*desc
)) desc
++;
623 state
->rowdata
[state
->rowsize
* i
+ state
->rowlen
[i
]++] =
625 } while (*desc
++ == '.');
627 desc
++; /* expect a slash immediately */
634 static game_state
*dup_game(game_state
*state
)
636 game_state
*ret
= snew(game_state
);
641 ret
->grid
= snewn(ret
->w
* ret
->h
, unsigned char);
642 memcpy(ret
->grid
, state
->grid
, ret
->w
* ret
->h
);
644 ret
->rowsize
= state
->rowsize
;
645 ret
->rowdata
= snewn(ret
->rowsize
* (ret
->w
+ ret
->h
), int);
646 ret
->rowlen
= snewn(ret
->w
+ ret
->h
, int);
647 memcpy(ret
->rowdata
, state
->rowdata
,
648 ret
->rowsize
* (ret
->w
+ ret
->h
) * sizeof(int));
649 memcpy(ret
->rowlen
, state
->rowlen
,
650 (ret
->w
+ ret
->h
) * sizeof(int));
652 ret
->completed
= state
->completed
;
653 ret
->cheated
= state
->cheated
;
658 static void free_game(game_state
*state
)
660 sfree(state
->rowdata
);
661 sfree(state
->rowlen
);
666 static char *solve_game(game_state
*state
, game_state
*currstate
,
667 char *ai
, char **error
)
669 unsigned char *matrix
;
670 int w
= state
->w
, h
= state
->h
;
674 unsigned char *workspace
;
678 * If we already have the solved state in ai, copy it out.
683 matrix
= snewn(w
*h
, unsigned char);
685 workspace
= snewn(max
*3, unsigned char);
686 rowdata
= snewn(max
+1, int);
688 memset(matrix
, 0, w
*h
);
692 for (i
=0; i
<h
; i
++) {
693 memcpy(rowdata
, state
->rowdata
+ state
->rowsize
*(w
+i
),
695 rowdata
[state
->rowlen
[w
+i
]] = 0;
696 done_any
|= do_row(workspace
, workspace
+max
, workspace
+2*max
,
697 matrix
+i
*w
, w
, 1, rowdata
);
699 for (i
=0; i
<w
; i
++) {
700 memcpy(rowdata
, state
->rowdata
+ state
->rowsize
*i
, max
*sizeof(int));
701 rowdata
[state
->rowlen
[i
]] = 0;
702 done_any
|= do_row(workspace
, workspace
+max
, workspace
+2*max
,
703 matrix
+i
, h
, w
, rowdata
);
710 for (i
= 0; i
< w
*h
; i
++) {
711 if (matrix
[i
] != BLOCK
&& matrix
[i
] != DOT
) {
713 *error
= "Solving algorithm cannot complete this puzzle";
718 ret
= snewn(w
*h
+2, char);
720 for (i
= 0; i
< w
*h
; i
++) {
721 assert(matrix
[i
] == BLOCK
|| matrix
[i
] == DOT
);
722 ret
[i
+1] = (matrix
[i
] == BLOCK ?
'1' : '0');
731 static char *game_text_format(game_state
*state
)
742 int drag
, release
, state
;
745 static game_ui
*new_ui(game_state
*state
)
750 ret
->dragging
= FALSE
;
755 static void free_ui(game_ui
*ui
)
760 static char *encode_ui(game_ui
*ui
)
765 static void decode_ui(game_ui
*ui
, char *encoding
)
769 static void game_changed_state(game_ui
*ui
, game_state
*oldstate
,
770 game_state
*newstate
)
774 struct game_drawstate
{
778 unsigned char *visible
;
781 static char *interpret_move(game_state
*state
, game_ui
*ui
, game_drawstate
*ds
,
782 int x
, int y
, int button
)
786 x
= FROMCOORD(state
->w
, x
);
787 y
= FROMCOORD(state
->h
, y
);
789 if (x
>= 0 && x
< state
->w
&& y
>= 0 && y
< state
->h
&&
790 (button
== LEFT_BUTTON
|| button
== RIGHT_BUTTON
||
791 button
== MIDDLE_BUTTON
)) {
795 if (button
== LEFT_BUTTON
) {
796 ui
->drag
= LEFT_DRAG
;
797 ui
->release
= LEFT_RELEASE
;
798 ui
->state
= GRID_FULL
;
799 } else if (button
== RIGHT_BUTTON
) {
800 ui
->drag
= RIGHT_DRAG
;
801 ui
->release
= RIGHT_RELEASE
;
802 ui
->state
= GRID_EMPTY
;
803 } else /* if (button == MIDDLE_BUTTON) */ {
804 ui
->drag
= MIDDLE_DRAG
;
805 ui
->release
= MIDDLE_RELEASE
;
806 ui
->state
= GRID_UNKNOWN
;
809 ui
->drag_start_x
= ui
->drag_end_x
= x
;
810 ui
->drag_start_y
= ui
->drag_end_y
= y
;
812 return ""; /* UI activity occurred */
815 if (ui
->dragging
&& button
== ui
->drag
) {
817 * There doesn't seem much point in allowing a rectangle
818 * drag; people will generally only want to drag a single
819 * horizontal or vertical line, so we make that easy by
822 * Exception: if we're _middle_-button dragging to tag
823 * things as UNKNOWN, we may well want to trash an entire
824 * area and start over!
826 if (ui
->state
!= GRID_UNKNOWN
) {
827 if (abs(x
- ui
->drag_start_x
) > abs(y
- ui
->drag_start_y
))
828 y
= ui
->drag_start_y
;
830 x
= ui
->drag_start_x
;
835 if (x
>= state
->w
) x
= state
->w
- 1;
836 if (y
>= state
->h
) y
= state
->h
- 1;
841 return ""; /* UI activity occurred */
844 if (ui
->dragging
&& button
== ui
->release
) {
845 int x1
, x2
, y1
, y2
, xx
, yy
;
846 int move_needed
= FALSE
;
848 x1
= min(ui
->drag_start_x
, ui
->drag_end_x
);
849 x2
= max(ui
->drag_start_x
, ui
->drag_end_x
);
850 y1
= min(ui
->drag_start_y
, ui
->drag_end_y
);
851 y2
= max(ui
->drag_start_y
, ui
->drag_end_y
);
853 for (yy
= y1
; yy
<= y2
; yy
++)
854 for (xx
= x1
; xx
<= x2
; xx
++)
855 if (state
->grid
[yy
* state
->w
+ xx
] != ui
->state
)
858 ui
->dragging
= FALSE
;
862 sprintf(buf
, "%c%d,%d,%d,%d",
863 (char)(ui
->state
== GRID_FULL ?
'F' :
864 ui
->state
== GRID_EMPTY ?
'E' : 'U'),
865 x1
, y1
, x2
-x1
+1, y2
-y1
+1);
868 return ""; /* UI activity occurred */
874 static game_state
*execute_move(game_state
*from
, char *move
)
877 int x1
, x2
, y1
, y2
, xx
, yy
;
880 if (move
[0] == 'S' && strlen(move
) == from
->w
* from
->h
+ 1) {
883 ret
= dup_game(from
);
885 for (i
= 0; i
< ret
->w
* ret
->h
; i
++)
886 ret
->grid
[i
] = (move
[i
+1] == '1' ? GRID_FULL
: GRID_EMPTY
);
888 ret
->completed
= ret
->cheated
= TRUE
;
891 } else if ((move
[0] == 'F' || move
[0] == 'E' || move
[0] == 'U') &&
892 sscanf(move
+1, "%d,%d,%d,%d", &x1
, &y1
, &x2
, &y2
) == 4 &&
893 x1
>= 0 && x2
>= 0 && x1
+x2
<= from
->w
&&
894 y1
>= 0 && y2
>= 0 && y1
+y2
<= from
->h
) {
898 val
= (move
[0] == 'F' ? GRID_FULL
:
899 move
[0] == 'E' ? GRID_EMPTY
: GRID_UNKNOWN
);
901 ret
= dup_game(from
);
902 for (yy
= y1
; yy
< y2
; yy
++)
903 for (xx
= x1
; xx
< x2
; xx
++)
904 ret
->grid
[yy
* ret
->w
+ xx
] = val
;
907 * An actual change, so check to see if we've completed the
910 if (!ret
->completed
) {
911 int *rowdata
= snewn(ret
->rowsize
, int);
914 ret
->completed
= TRUE
;
916 for (i
=0; i
<ret
->w
; i
++) {
917 len
= compute_rowdata(rowdata
,
918 ret
->grid
+i
, ret
->h
, ret
->w
);
919 if (len
!= ret
->rowlen
[i
] ||
920 memcmp(ret
->rowdata
+i
*ret
->rowsize
, rowdata
,
921 len
* sizeof(int))) {
922 ret
->completed
= FALSE
;
926 for (i
=0; i
<ret
->h
; i
++) {
927 len
= compute_rowdata(rowdata
,
928 ret
->grid
+i
*ret
->w
, ret
->w
, 1);
929 if (len
!= ret
->rowlen
[i
+ret
->w
] ||
930 memcmp(ret
->rowdata
+(i
+ret
->w
)*ret
->rowsize
, rowdata
,
931 len
* sizeof(int))) {
932 ret
->completed
= FALSE
;
945 /* ----------------------------------------------------------------------
949 static void game_compute_size(game_params
*params
, int tilesize
,
952 /* Ick: fake up `ds->tilesize' for macro expansion purposes */
953 struct { int tilesize
; } ads
, *ds
= &ads
;
954 ads
.tilesize
= tilesize
;
956 *x
= SIZE(params
->w
);
957 *y
= SIZE(params
->h
);
960 static void game_set_size(drawing
*dr
, game_drawstate
*ds
,
961 game_params
*params
, int tilesize
)
963 ds
->tilesize
= tilesize
;
966 static float *game_colours(frontend
*fe
, game_state
*state
, int *ncolours
)
968 float *ret
= snewn(3 * NCOLOURS
, float);
970 frontend_default_colour(fe
, &ret
[COL_BACKGROUND
* 3]);
972 ret
[COL_GRID
* 3 + 0] = 0.3F
;
973 ret
[COL_GRID
* 3 + 1] = 0.3F
;
974 ret
[COL_GRID
* 3 + 2] = 0.3F
;
976 ret
[COL_UNKNOWN
* 3 + 0] = 0.5F
;
977 ret
[COL_UNKNOWN
* 3 + 1] = 0.5F
;
978 ret
[COL_UNKNOWN
* 3 + 2] = 0.5F
;
980 ret
[COL_TEXT
* 3 + 0] = 0.0F
;
981 ret
[COL_TEXT
* 3 + 1] = 0.0F
;
982 ret
[COL_TEXT
* 3 + 2] = 0.0F
;
984 ret
[COL_FULL
* 3 + 0] = 0.0F
;
985 ret
[COL_FULL
* 3 + 1] = 0.0F
;
986 ret
[COL_FULL
* 3 + 2] = 0.0F
;
988 ret
[COL_EMPTY
* 3 + 0] = 1.0F
;
989 ret
[COL_EMPTY
* 3 + 1] = 1.0F
;
990 ret
[COL_EMPTY
* 3 + 2] = 1.0F
;
992 *ncolours
= NCOLOURS
;
996 static game_drawstate
*game_new_drawstate(drawing
*dr
, game_state
*state
)
998 struct game_drawstate
*ds
= snew(struct game_drawstate
);
1000 ds
->started
= FALSE
;
1003 ds
->visible
= snewn(ds
->w
* ds
->h
, unsigned char);
1004 ds
->tilesize
= 0; /* not decided yet */
1005 memset(ds
->visible
, 255, ds
->w
* ds
->h
);
1010 static void game_free_drawstate(drawing
*dr
, game_drawstate
*ds
)
1016 static void grid_square(drawing
*dr
, game_drawstate
*ds
,
1017 int y
, int x
, int state
)
1021 draw_rect(dr
, TOCOORD(ds
->w
, x
), TOCOORD(ds
->h
, y
),
1022 TILE_SIZE
, TILE_SIZE
, COL_GRID
);
1024 xl
= (x
% 5 == 0 ?
1 : 0);
1025 yt
= (y
% 5 == 0 ?
1 : 0);
1026 xr
= (x
% 5 == 4 || x
== ds
->w
-1 ?
1 : 0);
1027 yb
= (y
% 5 == 4 || y
== ds
->h
-1 ?
1 : 0);
1029 draw_rect(dr
, TOCOORD(ds
->w
, x
) + 1 + xl
, TOCOORD(ds
->h
, y
) + 1 + yt
,
1030 TILE_SIZE
- xl
- xr
- 1, TILE_SIZE
- yt
- yb
- 1,
1031 (state
== GRID_FULL ? COL_FULL
:
1032 state
== GRID_EMPTY ? COL_EMPTY
: COL_UNKNOWN
));
1034 draw_update(dr
, TOCOORD(ds
->w
, x
), TOCOORD(ds
->h
, y
),
1035 TILE_SIZE
, TILE_SIZE
);
1038 static void draw_numbers(drawing
*dr
, game_drawstate
*ds
, game_state
*state
,
1046 for (i
= 0; i
< state
->w
+ state
->h
; i
++) {
1047 int rowlen
= state
->rowlen
[i
];
1048 int *rowdata
= state
->rowdata
+ state
->rowsize
* i
;
1052 * Normally I space the numbers out by the same
1053 * distance as the tile size. However, if there are
1054 * more numbers than available spaces, I have to squash
1057 nfit
= max(rowlen
, TLBORDER(state
->h
))-1;
1060 for (j
= 0; j
< rowlen
; j
++) {
1065 x
= TOCOORD(state
->w
, i
);
1066 y
= BORDER
+ TILE_SIZE
* (TLBORDER(state
->h
)-1);
1067 y
-= ((rowlen
-j
-1)*TILE_SIZE
) * (TLBORDER(state
->h
)-1) / nfit
;
1069 y
= TOCOORD(state
->h
, i
- state
->w
);
1070 x
= BORDER
+ TILE_SIZE
* (TLBORDER(state
->w
)-1);
1071 x
-= ((rowlen
-j
-1)*TILE_SIZE
) * (TLBORDER(state
->h
)-1) / nfit
;
1074 sprintf(str
, "%d", rowdata
[j
]);
1075 draw_text(dr
, x
+TILE_SIZE
/2, y
+TILE_SIZE
/2, FONT_VARIABLE
,
1076 TILE_SIZE
/2, ALIGN_HCENTRE
| ALIGN_VCENTRE
, colour
, str
);
1081 static void game_redraw(drawing
*dr
, game_drawstate
*ds
, game_state
*oldstate
,
1082 game_state
*state
, int dir
, game_ui
*ui
,
1083 float animtime
, float flashtime
)
1090 * The initial contents of the window are not guaranteed
1091 * and can vary with front ends. To be on the safe side,
1092 * all games should start by drawing a big background-
1093 * colour rectangle covering the whole window.
1095 draw_rect(dr
, 0, 0, SIZE(ds
->w
), SIZE(ds
->h
), COL_BACKGROUND
);
1100 draw_numbers(dr
, ds
, state
, COL_TEXT
);
1103 * Draw the grid outline.
1105 draw_rect(dr
, TOCOORD(ds
->w
, 0) - 1, TOCOORD(ds
->h
, 0) - 1,
1106 ds
->w
* TILE_SIZE
+ 3, ds
->h
* TILE_SIZE
+ 3,
1111 draw_update(dr
, 0, 0, SIZE(ds
->w
), SIZE(ds
->h
));
1115 x1
= min(ui
->drag_start_x
, ui
->drag_end_x
);
1116 x2
= max(ui
->drag_start_x
, ui
->drag_end_x
);
1117 y1
= min(ui
->drag_start_y
, ui
->drag_end_y
);
1118 y2
= max(ui
->drag_start_y
, ui
->drag_end_y
);
1120 x1
= x2
= y1
= y2
= -1; /* placate gcc warnings */
1124 * Now draw any grid squares which have changed since last
1127 for (i
= 0; i
< ds
->h
; i
++) {
1128 for (j
= 0; j
< ds
->w
; j
++) {
1132 * Work out what state this square should be drawn in,
1133 * taking any current drag operation into account.
1135 if (ui
->dragging
&& x1
<= j
&& j
<= x2
&& y1
<= i
&& i
<= y2
)
1138 val
= state
->grid
[i
* state
->w
+ j
];
1141 * Briefly invert everything twice during a completion
1144 if (flashtime
> 0 &&
1145 (flashtime
<= FLASH_TIME
/3 || flashtime
>= FLASH_TIME
*2/3) &&
1146 val
!= GRID_UNKNOWN
)
1147 val
= (GRID_FULL
^ GRID_EMPTY
) ^ val
;
1149 if (ds
->visible
[i
* ds
->w
+ j
] != val
) {
1150 grid_square(dr
, ds
, i
, j
, val
);
1151 ds
->visible
[i
* ds
->w
+ j
] = val
;
1157 static float game_anim_length(game_state
*oldstate
,
1158 game_state
*newstate
, int dir
, game_ui
*ui
)
1163 static float game_flash_length(game_state
*oldstate
,
1164 game_state
*newstate
, int dir
, game_ui
*ui
)
1166 if (!oldstate
->completed
&& newstate
->completed
&&
1167 !oldstate
->cheated
&& !newstate
->cheated
)
1172 static int game_wants_statusbar(void)
1177 static int game_timing_state(game_state
*state
, game_ui
*ui
)
1182 static void game_print_size(game_params
*params
, float *x
, float *y
)
1187 * I'll use 5mm squares by default.
1189 game_compute_size(params
, 500, &pw
, &ph
);
1194 static void game_print(drawing
*dr
, game_state
*state
, int tilesize
)
1196 int w
= state
->w
, h
= state
->h
;
1197 int ink
= print_mono_colour(dr
, 0);
1200 /* Ick: fake up `ds->tilesize' for macro expansion purposes */
1201 game_drawstate ads
, *ds
= &ads
;
1202 ads
.tilesize
= tilesize
;
1207 print_line_width(dr
, TILE_SIZE
/ 16);
1208 draw_rect_outline(dr
, TOCOORD(w
, 0), TOCOORD(h
, 0),
1209 w
*TILE_SIZE
, h
*TILE_SIZE
, ink
);
1214 for (x
= 1; x
< w
; x
++) {
1215 print_line_width(dr
, TILE_SIZE
/ (x
% 5 ?
128 : 24));
1216 draw_line(dr
, TOCOORD(w
, x
), TOCOORD(h
, 0),
1217 TOCOORD(w
, x
), TOCOORD(h
, h
), ink
);
1219 for (y
= 1; y
< h
; y
++) {
1220 print_line_width(dr
, TILE_SIZE
/ (y
% 5 ?
128 : 24));
1221 draw_line(dr
, TOCOORD(w
, 0), TOCOORD(h
, y
),
1222 TOCOORD(w
, w
), TOCOORD(h
, y
), ink
);
1228 draw_numbers(dr
, ds
, state
, ink
);
1233 print_line_width(dr
, TILE_SIZE
/ 128);
1234 for (y
= 0; y
< h
; y
++)
1235 for (x
= 0; x
< w
; x
++) {
1236 if (state
->grid
[y
*w
+x
] == GRID_FULL
)
1237 draw_rect(dr
, TOCOORD(w
, x
), TOCOORD(h
, y
),
1238 TILE_SIZE
, TILE_SIZE
, ink
);
1239 else if (state
->grid
[y
*w
+x
] == GRID_EMPTY
)
1240 draw_circle(dr
, TOCOORD(w
, x
) + TILE_SIZE
/2,
1241 TOCOORD(h
, y
) + TILE_SIZE
/2,
1242 TILE_SIZE
/12, ink
, ink
);
1247 #define thegame pattern
1250 const struct game thegame
= {
1251 "Pattern", "games.pattern",
1258 TRUE
, game_configure
, custom_params
,
1266 FALSE
, game_text_format
,
1274 PREFERRED_TILE_SIZE
, game_compute_size
, game_set_size
,
1277 game_free_drawstate
,
1281 TRUE
, FALSE
, game_print_size
, game_print
,
1282 game_wants_statusbar
,
1283 FALSE
, game_timing_state
,
1284 0, /* mouse_priorities */
1287 #ifdef STANDALONE_SOLVER
1289 int main(int argc
, char **argv
)
1293 char *id
= NULL
, *desc
, *err
;
1295 while (--argc
> 0) {
1298 fprintf(stderr
, "%s: unrecognised option `%s'\n", argv
[0], p
);
1306 fprintf(stderr
, "usage: %s <game_id>\n", argv
[0]);
1310 desc
= strchr(id
, ':');
1312 fprintf(stderr
, "%s: game id expects a colon in it\n", argv
[0]);
1317 p
= default_params();
1318 decode_params(p
, id
);
1319 err
= validate_desc(p
, desc
);
1321 fprintf(stderr
, "%s: %s\n", argv
[0], err
);
1324 s
= new_game(NULL
, p
, desc
);
1327 int w
= p
->w
, h
= p
->h
, i
, j
, done_any
, max
;
1328 unsigned char *matrix
, *workspace
;
1331 matrix
= snewn(w
*h
, unsigned char);
1333 workspace
= snewn(max
*3, unsigned char);
1334 rowdata
= snewn(max
+1, int);
1336 memset(matrix
, 0, w
*h
);
1340 for (i
=0; i
<h
; i
++) {
1341 memcpy(rowdata
, s
->rowdata
+ s
->rowsize
*(w
+i
),
1343 rowdata
[s
->rowlen
[w
+i
]] = 0;
1344 done_any
|= do_row(workspace
, workspace
+max
, workspace
+2*max
,
1345 matrix
+i
*w
, w
, 1, rowdata
);
1347 for (i
=0; i
<w
; i
++) {
1348 memcpy(rowdata
, s
->rowdata
+ s
->rowsize
*i
, max
*sizeof(int));
1349 rowdata
[s
->rowlen
[i
]] = 0;
1350 done_any
|= do_row(workspace
, workspace
+max
, workspace
+2*max
,
1351 matrix
+i
, h
, w
, rowdata
);
1355 for (i
= 0; i
< h
; i
++) {
1356 for (j
= 0; j
< w
; j
++) {
1357 int c
= (matrix
[i
*w
+j
] == UNKNOWN ?
'?' :
1358 matrix
[i
*w
+j
] == BLOCK ?
'#' :
1359 matrix
[i
*w
+j
] == DOT ?
'.' :