2 * flip.c: Puzzle involving lighting up all the squares on a grid,
3 * where each click toggles an overlapping set of lights.
27 #define PREFERRED_TILE_SIZE 48
28 #define TILE_SIZE (ds->tilesize)
29 #define BORDER (TILE_SIZE / 2)
30 #define COORD(x) ( (x) * TILE_SIZE + BORDER )
31 #define FROMCOORD(x) ( ((x) - BORDER + TILE_SIZE) / TILE_SIZE - 1 )
33 #define ANIM_TIME 0.25F
34 #define FLASH_FRAME 0.07F
37 * Possible ways to decide which lights are toggled by each click.
38 * Essentially, each of these describes a means of inventing a
51 * This structure is shared between all the game_states describing
52 * a particular game, so it's reference-counted.
56 unsigned char *matrix
; /* array of (w*h) by (w*h) */
61 int moves
, completed
, cheated
, hints_active
;
62 unsigned char *grid
; /* array of w*h */
63 struct matrix
*matrix
;
66 static game_params
*default_params(void)
68 game_params
*ret
= snew(game_params
);
71 ret
->matrix_type
= CROSSES
;
76 static const struct game_params flip_presets
[] = {
85 static int game_fetch_preset(int i
, char **name
, game_params
**params
)
90 if (i
< 0 || i
>= lenof(flip_presets
))
93 ret
= snew(game_params
);
94 *ret
= flip_presets
[i
];
96 sprintf(str
, "%dx%d %s", ret
->w
, ret
->h
,
97 ret
->matrix_type
== CROSSES
? "Crosses" : "Random");
104 static void free_params(game_params
*params
)
109 static game_params
*dup_params(const game_params
*params
)
111 game_params
*ret
= snew(game_params
);
112 *ret
= *params
; /* structure copy */
116 static void decode_params(game_params
*ret
, char const *string
)
118 ret
->w
= ret
->h
= atoi(string
);
119 while (*string
&& isdigit((unsigned char)*string
)) string
++;
120 if (*string
== 'x') {
122 ret
->h
= atoi(string
);
123 while (*string
&& isdigit((unsigned char)*string
)) string
++;
125 if (*string
== 'r') {
127 ret
->matrix_type
= RANDOM
;
128 } else if (*string
== 'c') {
130 ret
->matrix_type
= CROSSES
;
134 static char *encode_params(const game_params
*params
, int full
)
138 sprintf(data
, "%dx%d%s", params
->w
, params
->h
,
139 !full
? "" : params
->matrix_type
== CROSSES
? "c" : "r");
144 static config_item
*game_configure(const game_params
*params
)
146 config_item
*ret
= snewn(4, config_item
);
149 ret
[0].name
= "Width";
150 ret
[0].type
= C_STRING
;
151 sprintf(buf
, "%d", params
->w
);
152 ret
[0].sval
= dupstr(buf
);
155 ret
[1].name
= "Height";
156 ret
[1].type
= C_STRING
;
157 sprintf(buf
, "%d", params
->h
);
158 ret
[1].sval
= dupstr(buf
);
161 ret
[2].name
= "Shape type";
162 ret
[2].type
= C_CHOICES
;
163 ret
[2].sval
= ":Crosses:Random";
164 ret
[2].ival
= params
->matrix_type
;
174 static game_params
*custom_params(const config_item
*cfg
)
176 game_params
*ret
= snew(game_params
);
178 ret
->w
= atoi(cfg
[0].sval
);
179 ret
->h
= atoi(cfg
[1].sval
);
180 ret
->matrix_type
= cfg
[2].ival
;
185 static char *validate_params(const game_params
*params
, int full
)
187 if (params
->w
<= 0 || params
->h
<= 0)
188 return "Width and height must both be greater than zero";
192 static char *encode_bitmap(unsigned char *bmp
, int len
)
194 int slen
= (len
+ 3) / 4;
198 ret
= snewn(slen
+ 1, char);
199 for (i
= 0; i
< slen
; i
++) {
202 for (j
= 0; j
< 4; j
++)
203 if (i
*4+j
< len
&& bmp
[i
*4+j
])
205 ret
[i
] = "0123456789abcdef"[v
];
211 static void decode_bitmap(unsigned char *bmp
, int len
, const char *hex
)
213 int slen
= (len
+ 3) / 4;
216 for (i
= 0; i
< slen
; i
++) {
217 int j
, v
, c
= hex
[i
];
218 if (c
>= '0' && c
<= '9')
220 else if (c
>= 'A' && c
<= 'F')
222 else if (c
>= 'a' && c
<= 'f')
225 v
= 0; /* shouldn't happen */
226 for (j
= 0; j
< 4; j
++) {
238 * Structure used during random matrix generation, and a compare
239 * function to permit storage in a tree234.
242 int cx
, cy
; /* coords of click square */
243 int x
, y
; /* coords of output square */
245 * Number of click squares which currently affect this output
250 * Number of output squares currently affected by this click
255 #define SORT(field) do { \
256 if (a->field < b->field) \
258 else if (a->field > b->field) \
262 * Compare function for choosing the next square to add. We must
263 * sort by coverage, then by omino size, then everything else.
265 static int sqcmp_pick(void *av
, void *bv
)
267 struct sq
*a
= (struct sq
*)av
;
268 struct sq
*b
= (struct sq
*)bv
;
278 * Compare function for adjusting the coverage figures after a
279 * change. We sort first by coverage and output square, then by
282 static int sqcmp_cov(void *av
, void *bv
)
284 struct sq
*a
= (struct sq
*)av
;
285 struct sq
*b
= (struct sq
*)bv
;
295 * Compare function for adjusting the omino sizes after a change.
296 * We sort first by omino size and input square, then by everything
299 static int sqcmp_osize(void *av
, void *bv
)
301 struct sq
*a
= (struct sq
*)av
;
302 struct sq
*b
= (struct sq
*)bv
;
311 static void addsq(tree234
*t
, int w
, int h
, int cx
, int cy
,
312 int x
, int y
, unsigned char *matrix
)
318 if (x
< 0 || x
>= w
|| y
< 0 || y
>= h
)
320 if (abs(x
-cx
) > 1 || abs(y
-cy
) > 1)
322 if (matrix
[(cy
*w
+cx
) * wh
+ y
*w
+x
])
325 sq
= snew(struct sq
);
330 sq
->coverage
= sq
->ominosize
= 0;
331 for (i
= 0; i
< wh
; i
++) {
332 if (matrix
[i
* wh
+ y
*w
+x
])
334 if (matrix
[(cy
*w
+cx
) * wh
+ i
])
338 if (add234(t
, sq
) != sq
)
339 sfree(sq
); /* already there */
341 static void addneighbours(tree234
*t
, int w
, int h
, int cx
, int cy
,
342 int x
, int y
, unsigned char *matrix
)
344 addsq(t
, w
, h
, cx
, cy
, x
-1, y
, matrix
);
345 addsq(t
, w
, h
, cx
, cy
, x
+1, y
, matrix
);
346 addsq(t
, w
, h
, cx
, cy
, x
, y
-1, matrix
);
347 addsq(t
, w
, h
, cx
, cy
, x
, y
+1, matrix
);
350 static char *new_game_desc(const game_params
*params
, random_state
*rs
,
351 char **aux
, int interactive
)
353 int w
= params
->w
, h
= params
->h
, wh
= w
* h
;
355 unsigned char *matrix
, *grid
;
356 char *mbmp
, *gbmp
, *ret
;
358 matrix
= snewn(wh
* wh
, unsigned char);
359 grid
= snewn(wh
, unsigned char);
362 * First set up the matrix.
364 switch (params
->matrix_type
) {
366 for (i
= 0; i
< wh
; i
++) {
367 int ix
= i
% w
, iy
= i
/ w
;
368 for (j
= 0; j
< wh
; j
++) {
369 int jx
= j
% w
, jy
= j
/ w
;
370 if (abs(jx
- ix
) + abs(jy
- iy
) <= 1)
379 tree234
*pick
, *cov
, *osize
;
382 pick
= newtree234(sqcmp_pick
);
383 cov
= newtree234(sqcmp_cov
);
384 osize
= newtree234(sqcmp_osize
);
386 memset(matrix
, 0, wh
* wh
);
387 for (i
= 0; i
< wh
; i
++) {
391 for (i
= 0; i
< wh
; i
++) {
392 int ix
= i
% w
, iy
= i
/ w
;
393 addneighbours(pick
, w
, h
, ix
, iy
, ix
, iy
, matrix
);
394 addneighbours(cov
, w
, h
, ix
, iy
, ix
, iy
, matrix
);
395 addneighbours(osize
, w
, h
, ix
, iy
, ix
, iy
, matrix
);
399 * Repeatedly choose a square to add to the matrix,
400 * until we have enough. I'll arbitrarily choose our
401 * limit to be the same as the total number of set bits
402 * in the crosses matrix.
404 limit
= 4*wh
- 2*(w
+h
); /* centre squares already present */
406 while (limit
-- > 0) {
407 struct sq
*sq
, *sq2
, sqlocal
;
411 * Find the lowest element in the pick tree.
413 sq
= index234(pick
, 0);
416 * Find the highest element with the same coverage
417 * and omino size, by setting all other elements to
421 sqlocal
.cx
= sqlocal
.cy
= sqlocal
.x
= sqlocal
.y
= wh
;
422 sq
= findrelpos234(pick
, &sqlocal
, NULL
, REL234_LT
, &k
);
426 * Pick at random from all elements up to k of the
429 k
= random_upto(rs
, k
+1);
430 sq
= delpos234(pick
, k
);
435 * Add this square to the matrix.
437 matrix
[(sq
->cy
* w
+ sq
->cx
) * wh
+ (sq
->y
* w
+ sq
->x
)] = 1;
440 * Correct the matrix coverage field of any sq
441 * which points at this output square.
444 sqlocal
.cx
= sqlocal
.cy
= sqlocal
.ominosize
= -1;
445 while ((sq2
= findrel234(cov
, &sqlocal
, NULL
,
446 REL234_GT
)) != NULL
&&
447 sq2
->coverage
== sq
->coverage
&&
448 sq2
->x
== sq
->x
&& sq2
->y
== sq
->y
) {
459 * Correct the omino size field of any sq which
460 * points at this input square.
463 sqlocal
.x
= sqlocal
.y
= sqlocal
.coverage
= -1;
464 while ((sq2
= findrel234(osize
, &sqlocal
, NULL
,
465 REL234_GT
)) != NULL
&&
466 sq2
->ominosize
== sq
->ominosize
&&
467 sq2
->cx
== sq
->cx
&& sq2
->cy
== sq
->cy
) {
478 * The sq we actually picked out of the tree is
479 * finished with; but its neighbours now need to
482 addneighbours(pick
, w
,h
, sq
->cx
,sq
->cy
, sq
->x
,sq
->y
, matrix
);
483 addneighbours(cov
, w
,h
, sq
->cx
,sq
->cy
, sq
->x
,sq
->y
, matrix
);
484 addneighbours(osize
, w
,h
, sq
->cx
,sq
->cy
, sq
->x
,sq
->y
, matrix
);
489 * Free all remaining sq structures.
493 while ((sq
= delpos234(pick
, 0)) != NULL
)
501 * Finally, check to see if any two matrix rows are
502 * exactly identical. If so, this is not an acceptable
503 * matrix, and we give up and go round again.
505 * I haven't been immediately able to think of a
506 * plausible means of algorithmically avoiding this
507 * situation (by, say, making a small perturbation to
508 * an offending matrix), so for the moment I'm just
509 * going to deal with it by throwing the whole thing
510 * away. I suspect this will lead to scalability
511 * problems (since most of the things happening in
512 * these matrices are local, the chance of _some_
513 * neighbourhood having two identical regions will
514 * increase with the grid area), but so far this puzzle
515 * seems to be really hard at large sizes so I'm not
516 * massively worried yet. Anyone needs this done
517 * better, they're welcome to submit a patch.
519 for (i
= 0; i
< wh
; i
++) {
520 for (j
= 0; j
< wh
; j
++)
522 !memcmp(matrix
+ i
* wh
, matrix
+ j
* wh
, wh
))
528 break; /* no matches found */
534 * Now invent a random initial set of lights.
536 * At first glance it looks as if it might be quite difficult
537 * to choose equiprobably from all soluble light sets. After
538 * all, soluble light sets are those in the image space of the
539 * transformation matrix; so first we'd have to identify that
540 * space and its dimension, then pick a random coordinate for
541 * each basis vector and recombine. Lot of fiddly matrix
544 * However, vector spaces are nicely orthogonal and relieve us
545 * of all that difficulty. For every point in the image space,
546 * there are precisely as many points in the input space that
547 * map to it as there are elements in the kernel of the
548 * transformation matrix (because adding any kernel element to
549 * the input does not change the output, and because any two
550 * inputs mapping to the same output must differ by an element
551 * of the kernel because that's what the kernel _is_); and
552 * these cosets are all disjoint (obviously, since no input
553 * point can map to more than one output point) and cover the
554 * whole space (equally obviously, because no input point can
555 * map to fewer than one output point!).
557 * So the input space contains the same number of points for
558 * each point in the output space; thus, we can simply choose
559 * equiprobably from elements of the _input_ space, and filter
560 * the result through the transformation matrix in the obvious
561 * way, and we thereby guarantee to choose equiprobably from
562 * all the output points. Phew!
566 for (i
= 0; i
< wh
; i
++) {
567 int v
= random_upto(rs
, 2);
569 for (j
= 0; j
< wh
; j
++)
570 grid
[j
] ^= matrix
[i
*wh
+j
];
574 * Ensure we don't have the starting state already!
576 for (i
= 0; i
< wh
; i
++)
584 * Now encode the matrix and the starting grid as a game
585 * description. We'll do this by concatenating two great big
588 mbmp
= encode_bitmap(matrix
, wh
*wh
);
589 gbmp
= encode_bitmap(grid
, wh
);
590 ret
= snewn(strlen(mbmp
) + strlen(gbmp
) + 2, char);
591 sprintf(ret
, "%s,%s", mbmp
, gbmp
);
599 static char *validate_desc(const game_params
*params
, const char *desc
)
601 int w
= params
->w
, h
= params
->h
, wh
= w
* h
;
602 int mlen
= (wh
*wh
+3)/4, glen
= (wh
+3)/4;
604 if (strspn(desc
, "0123456789abcdefABCDEF") != mlen
)
605 return "Matrix description is wrong length";
606 if (desc
[mlen
] != ',')
607 return "Expected comma after matrix description";
608 if (strspn(desc
+mlen
+1, "0123456789abcdefABCDEF") != glen
)
609 return "Grid description is wrong length";
610 if (desc
[mlen
+1+glen
])
611 return "Unexpected data after grid description";
616 static game_state
*new_game(midend
*me
, const game_params
*params
,
619 int w
= params
->w
, h
= params
->h
, wh
= w
* h
;
620 int mlen
= (wh
*wh
+3)/4;
622 game_state
*state
= snew(game_state
);
626 state
->completed
= FALSE
;
627 state
->cheated
= FALSE
;
628 state
->hints_active
= FALSE
;
630 state
->matrix
= snew(struct matrix
);
631 state
->matrix
->refcount
= 1;
632 state
->matrix
->matrix
= snewn(wh
*wh
, unsigned char);
633 decode_bitmap(state
->matrix
->matrix
, wh
*wh
, desc
);
634 state
->grid
= snewn(wh
, unsigned char);
635 decode_bitmap(state
->grid
, wh
, desc
+ mlen
+ 1);
640 static game_state
*dup_game(const game_state
*state
)
642 game_state
*ret
= snew(game_state
);
646 ret
->completed
= state
->completed
;
647 ret
->cheated
= state
->cheated
;
648 ret
->hints_active
= state
->hints_active
;
649 ret
->moves
= state
->moves
;
650 ret
->matrix
= state
->matrix
;
651 state
->matrix
->refcount
++;
652 ret
->grid
= snewn(ret
->w
* ret
->h
, unsigned char);
653 memcpy(ret
->grid
, state
->grid
, ret
->w
* ret
->h
);
658 static void free_game(game_state
*state
)
661 if (--state
->matrix
->refcount
<= 0) {
662 sfree(state
->matrix
->matrix
);
663 sfree(state
->matrix
);
668 static void rowxor(unsigned char *row1
, unsigned char *row2
, int len
)
671 for (i
= 0; i
< len
; i
++)
675 static char *solve_game(const game_state
*state
, const game_state
*currstate
,
676 const char *aux
, char **error
)
678 int w
= state
->w
, h
= state
->h
, wh
= w
* h
;
679 unsigned char *equations
, *solution
, *shortest
;
681 int rowsdone
, colsdone
;
682 int i
, j
, k
, len
, bestlen
;
686 * Set up a list of simultaneous equations. Each one is of
687 * length (wh+1) and has wh coefficients followed by a value.
689 equations
= snewn((wh
+ 1) * wh
, unsigned char);
690 for (i
= 0; i
< wh
; i
++) {
691 for (j
= 0; j
< wh
; j
++)
692 equations
[i
* (wh
+1) + j
] = currstate
->matrix
->matrix
[j
*wh
+i
];
693 equations
[i
* (wh
+1) + wh
] = currstate
->grid
[i
] & 1;
697 * Perform Gaussian elimination over GF(2).
699 rowsdone
= colsdone
= 0;
701 und
= snewn(wh
, int);
704 * Find the leftmost column which has a 1 in it somewhere
705 * outside the first `rowsdone' rows.
708 for (i
= colsdone
; i
< wh
; i
++) {
709 for (j
= rowsdone
; j
< wh
; j
++)
710 if (equations
[j
* (wh
+1) + i
])
713 break; /* found one */
715 * This is a column which will not have an equation
716 * controlling it. Mark it as undetermined.
722 * If there wasn't one, then we've finished: all remaining
723 * equations are of the form 0 = constant. Check to see if
724 * any of them wants 0 to be equal to 1; this is the
725 * condition which indicates an insoluble problem
726 * (therefore _hopefully_ one typed in by a user!).
729 for (j
= rowsdone
; j
< wh
; j
++)
730 if (equations
[j
* (wh
+1) + wh
]) {
731 *error
= "No solution exists for this position";
740 * We've found a 1. It's in column i, and the topmost 1 in
741 * that column is in row j. Do a row-XOR to move it up to
742 * the topmost row if it isn't already there.
746 rowxor(equations
+ rowsdone
*(wh
+1), equations
+ j
*(wh
+1), wh
+1);
749 * Do row-XORs to eliminate that 1 from all rows below the
752 for (j
= rowsdone
+ 1; j
< wh
; j
++)
753 if (equations
[j
*(wh
+1) + i
])
754 rowxor(equations
+ j
*(wh
+1),
755 equations
+ rowsdone
*(wh
+1), wh
+1);
758 * Mark this row and column as done.
764 * If we've done all the rows, terminate.
766 } while (rowsdone
< wh
);
769 * If we reach here, we have the ability to produce a solution.
770 * So we go through _all_ possible solutions (each
771 * corresponding to a set of arbitrary choices of those
772 * components not directly determined by an equation), and pick
773 * one requiring the smallest number of flips.
775 solution
= snewn(wh
, unsigned char);
776 shortest
= snewn(wh
, unsigned char);
777 memset(solution
, 0, wh
);
781 * Find a solution based on the current values of the
782 * undetermined variables.
784 for (j
= rowsdone
; j
-- ;) {
788 * Find the leftmost set bit in this equation.
790 for (i
= 0; i
< wh
; i
++)
791 if (equations
[j
* (wh
+1) + i
])
793 assert(i
< wh
); /* there must have been one! */
796 * Compute this variable using the rest.
798 v
= equations
[j
* (wh
+1) + wh
];
799 for (k
= i
+1; k
< wh
; k
++)
800 if (equations
[j
* (wh
+1) + k
])
807 * Compare this solution to the current best one, and
808 * replace the best one if this one is shorter.
811 for (i
= 0; i
< wh
; i
++)
816 memcpy(shortest
, solution
, wh
);
820 * Now increment the binary number given by the
821 * undetermined variables: turn all 1s into 0s until we see
822 * a 0, at which point we turn it into a 1.
824 for (i
= 0; i
< nund
; i
++) {
825 solution
[und
[i
]] = !solution
[und
[i
]];
826 if (solution
[und
[i
]])
831 * If we didn't find a 0 at any point, we have wrapped
832 * round and are back at the start, i.e. we have enumerated
840 * We have a solution. Produce a move string encoding the
843 ret
= snewn(wh
+ 2, char);
845 for (i
= 0; i
< wh
; i
++)
846 ret
[i
+1] = shortest
[i
] ? '1' : '0';
857 static int game_can_format_as_text_now(const game_params
*params
)
865 static char *game_text_format(const game_state
*state
)
867 int w
= state
->w
, h
= state
->h
, wh
= w
*h
, r
, c
, dx
, dy
;
868 int cw
= 4, ch
= 4, gw
= w
* cw
+ 2, gh
= h
* ch
+ 1, len
= gw
* gh
;
869 char *board
= snewn(len
+ 1, char);
871 memset(board
, ' ', len
- 1);
873 for (r
= 0; r
< h
; ++r
) {
874 for (c
= 0; c
< w
; ++c
) {
875 int cell
= r
*ch
*gw
+ c
*cw
, center
= cell
+(ch
/2)*DOWN
+ cw
/2*RIGHT
;
876 char flip
= (state
->grid
[r
*w
+ c
] & 1) ? '#' : '.';
877 for (dy
= -1 + (r
== 0); dy
<= 1 - (r
== h
- 1); ++dy
)
878 for (dx
= -1 + (c
== 0); dx
<= 1 - (c
== w
- 1); ++dx
)
879 if (state
->matrix
->matrix
[(r
*w
+c
)*wh
+ ((r
+dy
)*w
+ c
+dx
)])
880 board
[center
+ dy
*DOWN
+ dx
*RIGHT
] = flip
;
882 for (dx
= 1; dx
< cw
; ++dx
) board
[cell
+dx
*RIGHT
] = '-';
883 for (dy
= 1; dy
< ch
; ++dy
) board
[cell
+dy
*DOWN
] = '|';
885 board
[r
*ch
*gw
+ gw
- 2] = '+';
886 board
[r
*ch
*gw
+ gw
- 1] = '\n';
887 for (dy
= 1; dy
< ch
; ++dy
) {
888 board
[r
*ch
*gw
+ gw
- 2 + dy
*DOWN
] = '|';
889 board
[r
*ch
*gw
+ gw
- 1 + dy
*DOWN
] = '\n';
892 memset(board
+ len
- gw
, '-', gw
- 2);
893 for (c
= 0; c
<= w
; ++c
) board
[len
- gw
+ cw
*c
] = '+';
894 board
[len
- 1] = '\n';
906 static game_ui
*new_ui(const game_state
*state
)
908 game_ui
*ui
= snew(game_ui
);
909 ui
->cx
= ui
->cy
= ui
->cdraw
= 0;
913 static void free_ui(game_ui
*ui
)
918 static char *encode_ui(const game_ui
*ui
)
923 static void decode_ui(game_ui
*ui
, const char *encoding
)
927 static void game_changed_state(game_ui
*ui
, const game_state
*oldstate
,
928 const game_state
*newstate
)
932 struct game_drawstate
{
934 unsigned char *tiles
;
938 static char *interpret_move(const game_state
*state
, game_ui
*ui
,
939 const game_drawstate
*ds
,
940 int x
, int y
, int button
)
942 int w
= state
->w
, h
= state
->h
, wh
= w
* h
;
943 char buf
[80], *nullret
= NULL
;
945 if (button
== LEFT_BUTTON
|| IS_CURSOR_SELECT(button
)) {
947 if (button
== LEFT_BUTTON
) {
948 tx
= FROMCOORD(x
), ty
= FROMCOORD(y
);
951 tx
= ui
->cx
; ty
= ui
->cy
;
956 if (tx
>= 0 && tx
< w
&& ty
>= 0 && ty
< h
) {
958 * It's just possible that a manually entered game ID
959 * will have at least one square do nothing whatsoever.
960 * If so, we avoid encoding a move at all.
962 int i
= ty
*w
+tx
, j
, makemove
= FALSE
;
963 for (j
= 0; j
< wh
; j
++) {
964 if (state
->matrix
->matrix
[i
*wh
+j
])
968 sprintf(buf
, "M%d,%d", tx
, ty
);
975 else if (IS_CURSOR_MOVE(button
)) {
978 case CURSOR_UP
: dy
= -1; break;
979 case CURSOR_DOWN
: dy
= 1; break;
980 case CURSOR_RIGHT
: dx
= 1; break;
981 case CURSOR_LEFT
: dx
= -1; break;
982 default: assert(!"shouldn't get here");
984 ui
->cx
+= dx
; ui
->cy
+= dy
;
985 ui
->cx
= min(max(ui
->cx
, 0), state
->w
- 1);
986 ui
->cy
= min(max(ui
->cy
, 0), state
->h
- 1);
994 static game_state
*execute_move(const game_state
*from
, const char *move
)
996 int w
= from
->w
, h
= from
->h
, wh
= w
* h
;
1000 if (move
[0] == 'S' && strlen(move
) == wh
+1) {
1003 ret
= dup_game(from
);
1004 ret
->hints_active
= TRUE
;
1005 ret
->cheated
= TRUE
;
1006 for (i
= 0; i
< wh
; i
++) {
1008 if (move
[i
+1] != '0')
1012 } else if (move
[0] == 'M' &&
1013 sscanf(move
+1, "%d,%d", &x
, &y
) == 2 &&
1014 x
>= 0 && x
< w
&& y
>= 0 && y
< h
) {
1017 ret
= dup_game(from
);
1019 if (!ret
->completed
)
1025 for (j
= 0; j
< wh
; j
++) {
1026 ret
->grid
[j
] ^= ret
->matrix
->matrix
[i
*wh
+j
];
1027 if (ret
->grid
[j
] & 1)
1030 ret
->grid
[i
] ^= 2; /* toggle hint */
1032 ret
->completed
= TRUE
;
1033 ret
->hints_active
= FALSE
;
1038 return NULL
; /* can't parse move string */
1041 /* ----------------------------------------------------------------------
1045 static void game_compute_size(const game_params
*params
, int tilesize
,
1048 /* Ick: fake up `ds->tilesize' for macro expansion purposes */
1049 struct { int tilesize
; } ads
, *ds
= &ads
;
1050 ads
.tilesize
= tilesize
;
1052 *x
= TILE_SIZE
* params
->w
+ 2 * BORDER
;
1053 *y
= TILE_SIZE
* params
->h
+ 2 * BORDER
;
1056 static void game_set_size(drawing
*dr
, game_drawstate
*ds
,
1057 const game_params
*params
, int tilesize
)
1059 ds
->tilesize
= tilesize
;
1062 static float *game_colours(frontend
*fe
, int *ncolours
)
1064 float *ret
= snewn(3 * NCOLOURS
, float);
1066 frontend_default_colour(fe
, &ret
[COL_BACKGROUND
* 3]);
1068 ret
[COL_WRONG
* 3 + 0] = ret
[COL_BACKGROUND
* 3 + 0] / 3;
1069 ret
[COL_WRONG
* 3 + 1] = ret
[COL_BACKGROUND
* 3 + 1] / 3;
1070 ret
[COL_WRONG
* 3 + 2] = ret
[COL_BACKGROUND
* 3 + 2] / 3;
1072 ret
[COL_RIGHT
* 3 + 0] = 1.0F
;
1073 ret
[COL_RIGHT
* 3 + 1] = 1.0F
;
1074 ret
[COL_RIGHT
* 3 + 2] = 1.0F
;
1076 ret
[COL_GRID
* 3 + 0] = ret
[COL_BACKGROUND
* 3 + 0] / 1.5F
;
1077 ret
[COL_GRID
* 3 + 1] = ret
[COL_BACKGROUND
* 3 + 1] / 1.5F
;
1078 ret
[COL_GRID
* 3 + 2] = ret
[COL_BACKGROUND
* 3 + 2] / 1.5F
;
1080 ret
[COL_DIAG
* 3 + 0] = ret
[COL_GRID
* 3 + 0];
1081 ret
[COL_DIAG
* 3 + 1] = ret
[COL_GRID
* 3 + 1];
1082 ret
[COL_DIAG
* 3 + 2] = ret
[COL_GRID
* 3 + 2];
1084 ret
[COL_HINT
* 3 + 0] = 1.0F
;
1085 ret
[COL_HINT
* 3 + 1] = 0.0F
;
1086 ret
[COL_HINT
* 3 + 2] = 0.0F
;
1088 ret
[COL_CURSOR
* 3 + 0] = 0.8F
;
1089 ret
[COL_CURSOR
* 3 + 1] = 0.0F
;
1090 ret
[COL_CURSOR
* 3 + 2] = 0.0F
;
1092 *ncolours
= NCOLOURS
;
1096 static game_drawstate
*game_new_drawstate(drawing
*dr
, const game_state
*state
)
1098 struct game_drawstate
*ds
= snew(struct game_drawstate
);
1101 ds
->started
= FALSE
;
1104 ds
->tiles
= snewn(ds
->w
*ds
->h
, unsigned char);
1105 ds
->tilesize
= 0; /* haven't decided yet */
1106 for (i
= 0; i
< ds
->w
*ds
->h
; i
++)
1112 static void game_free_drawstate(drawing
*dr
, game_drawstate
*ds
)
1118 static void draw_tile(drawing
*dr
, game_drawstate
*ds
, const game_state
*state
,
1119 int x
, int y
, int tile
, int anim
, float animtime
)
1121 int w
= ds
->w
, h
= ds
->h
, wh
= w
* h
;
1122 int bx
= x
* TILE_SIZE
+ BORDER
, by
= y
* TILE_SIZE
+ BORDER
;
1123 int i
, j
, dcol
= (tile
& 4) ? COL_CURSOR
: COL_DIAG
;
1125 clip(dr
, bx
+1, by
+1, TILE_SIZE
-1, TILE_SIZE
-1);
1127 draw_rect(dr
, bx
+1, by
+1, TILE_SIZE
-1, TILE_SIZE
-1,
1128 anim
? COL_BACKGROUND
: tile
& 1 ? COL_WRONG
: COL_RIGHT
);
1131 * Draw a polygon indicating that the square is diagonally
1134 int coords
[8], colour
;
1136 coords
[0] = bx
+ TILE_SIZE
;
1138 coords
[2] = bx
+ (int)((float)TILE_SIZE
* animtime
);
1139 coords
[3] = by
+ (int)((float)TILE_SIZE
* animtime
);
1141 coords
[5] = by
+ TILE_SIZE
;
1142 coords
[6] = bx
+ TILE_SIZE
- (int)((float)TILE_SIZE
* animtime
);
1143 coords
[7] = by
+ TILE_SIZE
- (int)((float)TILE_SIZE
* animtime
);
1145 colour
= (tile
& 1 ? COL_WRONG
: COL_RIGHT
);
1147 colour
= COL_WRONG
+ COL_RIGHT
- colour
;
1149 draw_polygon(dr
, coords
, 4, colour
, COL_GRID
);
1153 * Draw a little diagram in the tile which indicates which
1154 * surrounding tiles flip when this one is clicked.
1156 for (i
= 0; i
< h
; i
++)
1157 for (j
= 0; j
< w
; j
++)
1158 if (state
->matrix
->matrix
[(y
*w
+x
)*wh
+ i
*w
+j
]) {
1159 int ox
= j
- x
, oy
= i
- y
;
1160 int td
= TILE_SIZE
/ 16;
1161 int cx
= (bx
+ TILE_SIZE
/2) + (2 * ox
- 1) * td
;
1162 int cy
= (by
+ TILE_SIZE
/2) + (2 * oy
- 1) * td
;
1163 if (ox
== 0 && oy
== 0)
1164 draw_rect(dr
, cx
, cy
, 2*td
+1, 2*td
+1, dcol
);
1166 draw_line(dr
, cx
, cy
, cx
+2*td
, cy
, dcol
);
1167 draw_line(dr
, cx
, cy
+2*td
, cx
+2*td
, cy
+2*td
, dcol
);
1168 draw_line(dr
, cx
, cy
, cx
, cy
+2*td
, dcol
);
1169 draw_line(dr
, cx
+2*td
, cy
, cx
+2*td
, cy
+2*td
, dcol
);
1174 * Draw a hint rectangle if required.
1177 int x1
= bx
+ TILE_SIZE
/ 20, x2
= bx
+ TILE_SIZE
- TILE_SIZE
/ 20;
1178 int y1
= by
+ TILE_SIZE
/ 20, y2
= by
+ TILE_SIZE
- TILE_SIZE
/ 20;
1181 draw_line(dr
, x1
, y1
, x2
, y1
, COL_HINT
);
1182 draw_line(dr
, x1
, y2
, x2
, y2
, COL_HINT
);
1183 draw_line(dr
, x1
, y1
, x1
, y2
, COL_HINT
);
1184 draw_line(dr
, x2
, y1
, x2
, y2
, COL_HINT
);
1185 x1
++, y1
++, x2
--, y2
--;
1191 draw_update(dr
, bx
+1, by
+1, TILE_SIZE
-1, TILE_SIZE
-1);
1194 static void game_redraw(drawing
*dr
, game_drawstate
*ds
,
1195 const game_state
*oldstate
, const game_state
*state
,
1196 int dir
, const game_ui
*ui
,
1197 float animtime
, float flashtime
)
1199 int w
= ds
->w
, h
= ds
->h
, wh
= w
* h
;
1203 draw_rect(dr
, 0, 0, TILE_SIZE
* w
+ 2 * BORDER
,
1204 TILE_SIZE
* h
+ 2 * BORDER
, COL_BACKGROUND
);
1207 * Draw the grid lines.
1209 for (i
= 0; i
<= w
; i
++)
1210 draw_line(dr
, i
* TILE_SIZE
+ BORDER
, BORDER
,
1211 i
* TILE_SIZE
+ BORDER
, h
* TILE_SIZE
+ BORDER
,
1213 for (i
= 0; i
<= h
; i
++)
1214 draw_line(dr
, BORDER
, i
* TILE_SIZE
+ BORDER
,
1215 w
* TILE_SIZE
+ BORDER
, i
* TILE_SIZE
+ BORDER
,
1218 draw_update(dr
, 0, 0, TILE_SIZE
* w
+ 2 * BORDER
,
1219 TILE_SIZE
* h
+ 2 * BORDER
);
1225 flashframe
= (int)(flashtime
/ FLASH_FRAME
);
1229 animtime
/= ANIM_TIME
; /* scale it so it goes from 0 to 1 */
1231 for (i
= 0; i
< wh
; i
++) {
1232 int x
= i
% w
, y
= i
/ w
;
1234 int v
= state
->grid
[i
];
1237 if (flashframe
>= 0) {
1238 fx
= (w
+1)/2 - min(x
+1, w
-x
);
1239 fy
= (h
+1)/2 - min(y
+1, h
-y
);
1241 if (fd
== flashframe
)
1243 else if (fd
== flashframe
- 1)
1247 if (!state
->hints_active
)
1249 if (ui
->cdraw
&& ui
->cx
== x
&& ui
->cy
== y
)
1252 if (oldstate
&& ((state
->grid
[i
] ^ oldstate
->grid
[i
]) &~ 2))
1253 vv
= 255; /* means `animated' */
1257 if (ds
->tiles
[i
] == 255 || vv
== 255 || ds
->tiles
[i
] != vv
) {
1258 draw_tile(dr
, ds
, state
, x
, y
, v
, vv
== 255, animtime
);
1266 sprintf(buf
, "%sMoves: %d",
1268 (state
->cheated
? "Auto-solved. " : "COMPLETED! ") :
1269 (state
->cheated
? "Auto-solver used. " : "")),
1272 status_bar(dr
, buf
);
1276 static float game_anim_length(const game_state
*oldstate
,
1277 const game_state
*newstate
, int dir
, game_ui
*ui
)
1282 static float game_flash_length(const game_state
*oldstate
,
1283 const game_state
*newstate
, int dir
, game_ui
*ui
)
1285 if (!oldstate
->completed
&& newstate
->completed
)
1286 return FLASH_FRAME
* (max((newstate
->w
+1)/2, (newstate
->h
+1)/2)+1);
1291 static int game_status(const game_state
*state
)
1293 return state
->completed
? +1 : 0;
1296 static int game_timing_state(const game_state
*state
, game_ui
*ui
)
1301 static void game_print_size(const game_params
*params
, float *x
, float *y
)
1305 static void game_print(drawing
*dr
, const game_state
*state
, int tilesize
)
1310 #define thegame flip
1313 const struct game thegame
= {
1314 "Flip", "games.flip", "flip",
1316 game_fetch_preset
, NULL
,
1321 TRUE
, game_configure
, custom_params
,
1329 TRUE
, game_can_format_as_text_now
, game_text_format
,
1337 PREFERRED_TILE_SIZE
, game_compute_size
, game_set_size
,
1340 game_free_drawstate
,
1345 FALSE
, FALSE
, game_print_size
, game_print
,
1346 TRUE
, /* wants_statusbar */
1347 FALSE
, game_timing_state
,