2 * flip.c: Puzzle involving lighting up all the squares on a grid,
3 * where each click toggles an overlapping set of lights.
9 * - `Solve' could mark the squares you must click to solve
10 * + infrastructure change: this would mean the Solve operation
11 * must receive the current game_state as well as the initial
12 * one, which I've been wondering about for a while
34 #define PREFERRED_TILE_SIZE 48
35 #define TILE_SIZE (ds->tilesize)
36 #define BORDER (TILE_SIZE / 2)
37 #define COORD(x) ( (x) * TILE_SIZE + BORDER )
38 #define FROMCOORD(x) ( ((x) - BORDER + TILE_SIZE) / TILE_SIZE - 1 )
40 #define FLASH_FRAME 0.07F
43 * Possible ways to decide which lights are toggled by each click.
44 * Essentially, each of these describes a means of inventing a
57 * This structure is shared between all the game_states describing
58 * a particular game, so it's reference-counted.
62 unsigned char *matrix
; /* array of (w*h) by (w*h) */
68 unsigned char *grid
; /* array of w*h */
69 struct matrix
*matrix
;
72 static game_params
*default_params(void)
74 game_params
*ret
= snew(game_params
);
77 ret
->matrix_type
= CROSSES
;
82 static const struct game_params flip_presets
[] = {
91 static int game_fetch_preset(int i
, char **name
, game_params
**params
)
96 if (i
< 0 || i
>= lenof(flip_presets
))
99 ret
= snew(game_params
);
100 *ret
= flip_presets
[i
];
102 sprintf(str
, "%dx%d %s", ret
->w
, ret
->h
,
103 ret
->matrix_type
== CROSSES ?
"Crosses" : "Random");
110 static void free_params(game_params
*params
)
115 static game_params
*dup_params(game_params
*params
)
117 game_params
*ret
= snew(game_params
);
118 *ret
= *params
; /* structure copy */
122 static void decode_params(game_params
*ret
, char const *string
)
124 ret
->w
= ret
->h
= atoi(string
);
125 while (*string
&& isdigit(*string
)) string
++;
126 if (*string
== 'x') {
128 ret
->h
= atoi(string
);
129 while (*string
&& isdigit(*string
)) string
++;
131 if (*string
== 'r') {
133 ret
->matrix_type
= RANDOM
;
134 } else if (*string
== 'c') {
136 ret
->matrix_type
= CROSSES
;
140 static char *encode_params(game_params
*params
, int full
)
144 sprintf(data
, "%dx%d%s", params
->w
, params
->h
,
145 !full ?
"" : params
->matrix_type
== CROSSES ?
"c" : "r");
150 static config_item
*game_configure(game_params
*params
)
152 config_item
*ret
= snewn(4, config_item
);
155 ret
[0].name
= "Width";
156 ret
[0].type
= C_STRING
;
157 sprintf(buf
, "%d", params
->w
);
158 ret
[0].sval
= dupstr(buf
);
161 ret
[1].name
= "Height";
162 ret
[1].type
= C_STRING
;
163 sprintf(buf
, "%d", params
->h
);
164 ret
[1].sval
= dupstr(buf
);
167 ret
[2].name
= "Shape type";
168 ret
[2].type
= C_CHOICES
;
169 ret
[2].sval
= ":Crosses:Random";
170 ret
[2].ival
= params
->matrix_type
;
180 static game_params
*custom_params(config_item
*cfg
)
182 game_params
*ret
= snew(game_params
);
184 ret
->w
= atoi(cfg
[0].sval
);
185 ret
->h
= atoi(cfg
[1].sval
);
186 ret
->matrix_type
= cfg
[2].ival
;
191 static char *validate_params(game_params
*params
)
193 if (params
->w
<= 0 || params
->h
<= 0)
194 return "Width and height must both be greater than zero";
198 static char *encode_bitmap(unsigned char *bmp
, int len
)
200 int slen
= (len
+ 3) / 4;
204 ret
= snewn(slen
+ 1, char);
205 for (i
= 0; i
< slen
; i
++) {
208 for (j
= 0; j
< 4; j
++)
209 if (i
*4+j
< len
&& bmp
[i
*4+j
])
211 ret
[i
] = "0123456789abcdef"[v
];
217 static void decode_bitmap(unsigned char *bmp
, int len
, char *hex
)
219 int slen
= (len
+ 3) / 4;
222 for (i
= 0; i
< slen
; i
++) {
223 int j
, v
, c
= hex
[i
];
224 if (c
>= '0' && c
<= '9')
226 else if (c
>= 'A' && c
<= 'F')
228 else if (c
>= 'a' && c
<= 'f')
231 v
= 0; /* shouldn't happen */
232 for (j
= 0; j
< 4; j
++) {
244 * Structure used during random matrix generation, and a compare
245 * function to permit storage in a tree234.
248 int cx
, cy
; /* coords of click square */
249 int x
, y
; /* coords of output square */
251 * Number of click squares which currently affect this output
256 * Number of output squares currently affected by this click
261 #define SORT(field) do { \
262 if (a->field < b->field) \
264 else if (a->field > b->field) \
268 * Compare function for choosing the next square to add. We must
269 * sort by coverage, then by omino size, then everything else.
271 static int sqcmp_pick(void *av
, void *bv
)
273 struct sq
*a
= (struct sq
*)av
;
274 struct sq
*b
= (struct sq
*)bv
;
284 * Compare function for adjusting the coverage figures after a
285 * change. We sort first by coverage and output square, then by
288 static int sqcmp_cov(void *av
, void *bv
)
290 struct sq
*a
= (struct sq
*)av
;
291 struct sq
*b
= (struct sq
*)bv
;
301 * Compare function for adjusting the omino sizes after a change.
302 * We sort first by omino size and input square, then by everything
305 static int sqcmp_osize(void *av
, void *bv
)
307 struct sq
*a
= (struct sq
*)av
;
308 struct sq
*b
= (struct sq
*)bv
;
317 static void addsq(tree234
*t
, int w
, int h
, int cx
, int cy
,
318 int x
, int y
, unsigned char *matrix
)
324 if (x
< 0 || x
>= w
|| y
< 0 || y
>= h
)
326 if (abs(x
-cx
) > 1 || abs(y
-cy
) > 1)
328 if (matrix
[(cy
*w
+cx
) * wh
+ y
*w
+x
])
331 sq
= snew(struct sq
);
336 sq
->coverage
= sq
->ominosize
= 0;
337 for (i
= 0; i
< wh
; i
++) {
338 if (matrix
[i
* wh
+ y
*w
+x
])
340 if (matrix
[(cy
*w
+cx
) * wh
+ i
])
344 if (add234(t
, sq
) != sq
)
345 sfree(sq
); /* already there */
347 static void addneighbours(tree234
*t
, int w
, int h
, int cx
, int cy
,
348 int x
, int y
, unsigned char *matrix
)
350 addsq(t
, w
, h
, cx
, cy
, x
-1, y
, matrix
);
351 addsq(t
, w
, h
, cx
, cy
, x
+1, y
, matrix
);
352 addsq(t
, w
, h
, cx
, cy
, x
, y
-1, matrix
);
353 addsq(t
, w
, h
, cx
, cy
, x
, y
+1, matrix
);
356 static char *new_game_desc(game_params
*params
, random_state
*rs
,
357 game_aux_info
**aux
, int interactive
)
359 int w
= params
->w
, h
= params
->h
, wh
= w
* h
;
361 unsigned char *matrix
, *grid
;
362 char *mbmp
, *gbmp
, *ret
;
364 matrix
= snewn(wh
* wh
, unsigned char);
365 grid
= snewn(wh
, unsigned char);
368 * First set up the matrix.
370 switch (params
->matrix_type
) {
372 for (i
= 0; i
< wh
; i
++) {
373 int ix
= i
% w
, iy
= i
/ w
;
374 for (j
= 0; j
< wh
; j
++) {
375 int jx
= j
% w
, jy
= j
/ w
;
376 if (abs(jx
- ix
) + abs(jy
- iy
) <= 1)
385 tree234
*pick
, *cov
, *osize
;
388 pick
= newtree234(sqcmp_pick
);
389 cov
= newtree234(sqcmp_cov
);
390 osize
= newtree234(sqcmp_osize
);
392 memset(matrix
, 0, wh
* wh
);
393 for (i
= 0; i
< wh
; i
++) {
397 for (i
= 0; i
< wh
; i
++) {
398 int ix
= i
% w
, iy
= i
/ w
;
399 addneighbours(pick
, w
, h
, ix
, iy
, ix
, iy
, matrix
);
400 addneighbours(cov
, w
, h
, ix
, iy
, ix
, iy
, matrix
);
401 addneighbours(osize
, w
, h
, ix
, iy
, ix
, iy
, matrix
);
405 * Repeatedly choose a square to add to the matrix,
406 * until we have enough. I'll arbitrarily choose our
407 * limit to be the same as the total number of set bits
408 * in the crosses matrix.
410 limit
= 4*wh
- 2*(w
+h
); /* centre squares already present */
412 while (limit
-- > 0) {
413 struct sq
*sq
, *sq2
, sqlocal
;
417 * Find the lowest element in the pick tree.
419 sq
= index234(pick
, 0);
422 * Find the highest element with the same coverage
423 * and omino size, by setting all other elements to
427 sqlocal
.cx
= sqlocal
.cy
= sqlocal
.x
= sqlocal
.y
= wh
;
428 sq
= findrelpos234(pick
, &sqlocal
, NULL
, REL234_LT
, &k
);
432 * Pick at random from all elements up to k of the
435 k
= random_upto(rs
, k
+1);
436 sq
= delpos234(pick
, k
);
441 * Add this square to the matrix.
443 matrix
[(sq
->cy
* w
+ sq
->cx
) * wh
+ (sq
->y
* w
+ sq
->x
)] = 1;
446 * Correct the matrix coverage field of any sq
447 * which points at this output square.
450 sqlocal
.cx
= sqlocal
.cy
= sqlocal
.ominosize
= -1;
451 while ((sq2
= findrel234(cov
, &sqlocal
, NULL
,
452 REL234_GT
)) != NULL
&&
453 sq2
->coverage
== sq
->coverage
&&
454 sq2
->x
== sq
->x
&& sq2
->y
== sq
->y
) {
465 * Correct the omino size field of any sq which
466 * points at this input square.
469 sqlocal
.x
= sqlocal
.y
= sqlocal
.coverage
= -1;
470 while ((sq2
= findrel234(osize
, &sqlocal
, NULL
,
471 REL234_GT
)) != NULL
&&
472 sq2
->ominosize
== sq
->ominosize
&&
473 sq2
->cx
== sq
->cx
&& sq2
->cy
== sq
->cy
) {
484 * The sq we actually picked out of the tree is
485 * finished with; but its neighbours now need to
488 addneighbours(pick
, w
,h
, sq
->cx
,sq
->cy
, sq
->x
,sq
->y
, matrix
);
489 addneighbours(cov
, w
,h
, sq
->cx
,sq
->cy
, sq
->x
,sq
->y
, matrix
);
490 addneighbours(osize
, w
,h
, sq
->cx
,sq
->cy
, sq
->x
,sq
->y
, matrix
);
495 * Free all remaining sq structures.
499 while ((sq
= delpos234(pick
, 0)) != NULL
)
507 * Finally, check to see if any two matrix rows are
508 * exactly identical. If so, this is not an acceptable
509 * matrix, and we give up and go round again.
511 * I haven't been immediately able to think of a
512 * plausible means of algorithmically avoiding this
513 * situation (by, say, making a small perturbation to
514 * an offending matrix), so for the moment I'm just
515 * going to deal with it by throwing the whole thing
516 * away. I suspect this will lead to scalability
517 * problems (since most of the things happening in
518 * these matrices are local, the chance of _some_
519 * neighbourhood having two identical regions will
520 * increase with the grid area), but so far this puzzle
521 * seems to be really hard at large sizes so I'm not
522 * massively worried yet. Anyone needs this done
523 * better, they're welcome to submit a patch.
525 for (i
= 0; i
< wh
; i
++) {
526 for (j
= 0; j
< wh
; j
++)
528 !memcmp(matrix
+ i
* wh
, matrix
+ j
* wh
, wh
))
534 break; /* no matches found */
540 * Now invent a random initial set of lights.
542 * At first glance it looks as if it might be quite difficult
543 * to choose equiprobably from all soluble light sets. After
544 * all, soluble light sets are those in the image space of the
545 * transformation matrix; so first we'd have to identify that
546 * space and its dimension, then pick a random coordinate for
547 * each basis vector and recombine. Lot of fiddly matrix
550 * However, vector spaces are nicely orthogonal and relieve us
551 * of all that difficulty. For every point in the image space,
552 * there are precisely as many points in the input space that
553 * map to it as there are elements in the kernel of the
554 * transformation matrix (because adding any kernel element to
555 * the input does not change the output, and because any two
556 * inputs mapping to the same output must differ by an element
557 * of the kernel because that's what the kernel _is_); and
558 * these cosets are all disjoint (obviously, since no input
559 * point can map to more than one output point) and cover the
560 * whole space (equally obviously, because no input point can
561 * map to fewer than one output point!).
563 * So the input space contains the same number of points for
564 * each point in the output space; thus, we can simply choose
565 * equiprobably from elements of the _input_ space, and filter
566 * the result through the transformation matrix in the obvious
567 * way, and we thereby guarantee to choose equiprobably from
568 * all the output points. Phew!
572 for (i
= 0; i
< wh
; i
++) {
573 int v
= random_upto(rs
, 2);
575 for (j
= 0; j
< wh
; j
++)
576 grid
[j
] ^= matrix
[i
*wh
+j
];
580 * Ensure we don't have the starting state already!
582 for (i
= 0; i
< wh
; i
++)
590 * Now encode the matrix and the starting grid as a game
591 * description. We'll do this by concatenating two great big
594 mbmp
= encode_bitmap(matrix
, wh
*wh
);
595 gbmp
= encode_bitmap(grid
, wh
);
596 ret
= snewn(strlen(mbmp
) + strlen(gbmp
) + 2, char);
597 sprintf(ret
, "%s,%s", mbmp
, gbmp
);
603 static void game_free_aux_info(game_aux_info
*aux
)
605 assert(!"Shouldn't happen");
608 static char *validate_desc(game_params
*params
, char *desc
)
610 int w
= params
->w
, h
= params
->h
, wh
= w
* h
;
611 int mlen
= (wh
*wh
+3)/4, glen
= (wh
+3)/4;
613 if (strspn(desc
, "0123456789abcdefABCDEF") != mlen
)
614 return "Matrix description is wrong length";
615 if (desc
[mlen
] != ',')
616 return "Expected comma after matrix description";
617 if (strspn(desc
+mlen
+1, "0123456789abcdefABCDEF") != glen
)
618 return "Grid description is wrong length";
619 if (desc
[mlen
+1+glen
])
620 return "Unexpected data after grid description";
625 static game_state
*new_game(midend_data
*me
, game_params
*params
, char *desc
)
627 int w
= params
->w
, h
= params
->h
, wh
= w
* h
;
628 int mlen
= (wh
*wh
+3)/4;
630 game_state
*state
= snew(game_state
);
634 state
->completed
= FALSE
;
636 state
->matrix
= snew(struct matrix
);
637 state
->matrix
->refcount
= 1;
638 state
->matrix
->matrix
= snewn(wh
*wh
, unsigned char);
639 decode_bitmap(state
->matrix
->matrix
, wh
*wh
, desc
);
640 state
->grid
= snewn(wh
, unsigned char);
641 decode_bitmap(state
->grid
, wh
, desc
+ mlen
+ 1);
646 static game_state
*dup_game(game_state
*state
)
648 game_state
*ret
= snew(game_state
);
652 ret
->completed
= state
->completed
;
653 ret
->moves
= state
->moves
;
654 ret
->matrix
= state
->matrix
;
655 state
->matrix
->refcount
++;
656 ret
->grid
= snewn(ret
->w
* ret
->h
, unsigned char);
657 memcpy(ret
->grid
, state
->grid
, ret
->w
* ret
->h
);
662 static void free_game(game_state
*state
)
665 if (--state
->matrix
->refcount
<= 0) {
666 sfree(state
->matrix
->matrix
);
667 sfree(state
->matrix
);
672 static game_state
*solve_game(game_state
*state
, game_aux_info
*aux
,
678 static char *game_text_format(game_state
*state
)
683 static game_ui
*new_ui(game_state
*state
)
688 static void free_ui(game_ui
*ui
)
692 static void game_changed_state(game_ui
*ui
, game_state
*oldstate
,
693 game_state
*newstate
)
697 struct game_drawstate
{
699 unsigned char *tiles
;
703 static game_state
*make_move(game_state
*from
, game_ui
*ui
, game_drawstate
*ds
,
704 int x
, int y
, int button
)
706 int w
= from
->w
, h
= from
->h
, wh
= w
* h
;
709 if (button
== LEFT_BUTTON
) {
710 int tx
= FROMCOORD(x
), ty
= FROMCOORD(y
);
711 if (tx
>= 0 && tx
< w
&& ty
>= 0 && ty
< h
) {
714 ret
= dup_game(from
);
722 for (j
= 0; j
< wh
; j
++) {
723 ret
->grid
[j
] ^= ret
->matrix
->matrix
[i
*wh
+j
];
724 if (ret
->grid
[j
] & 1)
728 ret
->completed
= TRUE
;
737 /* ----------------------------------------------------------------------
741 static void game_size(game_params
*params
, game_drawstate
*ds
,
742 int *x
, int *y
, int expand
)
746 * Each window dimension equals the tile size times one more
747 * than the grid dimension (the border is half the width of the
750 tsx
= *x
/ (params
->w
+ 1);
751 tsy
= *y
/ (params
->h
+ 1);
756 ds
->tilesize
= min(ts
, PREFERRED_TILE_SIZE
);
758 *x
= TILE_SIZE
* params
->w
+ 2 * BORDER
;
759 *y
= TILE_SIZE
* params
->h
+ 2 * BORDER
;
762 static float *game_colours(frontend
*fe
, game_state
*state
, int *ncolours
)
764 float *ret
= snewn(3 * NCOLOURS
, float);
766 frontend_default_colour(fe
, &ret
[COL_BACKGROUND
* 3]);
768 ret
[COL_WRONG
* 3 + 0] = ret
[COL_BACKGROUND
* 3 + 0] / 3;
769 ret
[COL_WRONG
* 3 + 1] = ret
[COL_BACKGROUND
* 3 + 1] / 3;
770 ret
[COL_WRONG
* 3 + 2] = ret
[COL_BACKGROUND
* 3 + 2] / 3;
772 ret
[COL_RIGHT
* 3 + 0] = 1.0F
;
773 ret
[COL_RIGHT
* 3 + 1] = 1.0F
;
774 ret
[COL_RIGHT
* 3 + 2] = 1.0F
;
776 ret
[COL_GRID
* 3 + 0] = ret
[COL_BACKGROUND
* 3 + 0] / 1.5F
;
777 ret
[COL_GRID
* 3 + 1] = ret
[COL_BACKGROUND
* 3 + 1] / 1.5F
;
778 ret
[COL_GRID
* 3 + 2] = ret
[COL_BACKGROUND
* 3 + 2] / 1.5F
;
780 ret
[COL_DIAG
* 3 + 0] = ret
[COL_GRID
* 3 + 0];
781 ret
[COL_DIAG
* 3 + 1] = ret
[COL_GRID
* 3 + 1];
782 ret
[COL_DIAG
* 3 + 2] = ret
[COL_GRID
* 3 + 2];
784 *ncolours
= NCOLOURS
;
788 static game_drawstate
*game_new_drawstate(game_state
*state
)
790 struct game_drawstate
*ds
= snew(struct game_drawstate
);
796 ds
->tiles
= snewn(ds
->w
*ds
->h
, unsigned char);
797 ds
->tilesize
= 0; /* haven't decided yet */
798 for (i
= 0; i
< ds
->w
*ds
->h
; i
++)
804 static void game_free_drawstate(game_drawstate
*ds
)
810 static void draw_tile(frontend
*fe
, game_drawstate
*ds
,
811 game_state
*state
, int x
, int y
, int tile
)
813 int w
= ds
->w
, h
= ds
->h
, wh
= w
* h
;
814 int bx
= x
* TILE_SIZE
+ BORDER
, by
= y
* TILE_SIZE
+ BORDER
;
817 clip(fe
, bx
+1, by
+1, TILE_SIZE
-1, TILE_SIZE
-1);
819 draw_rect(fe
, bx
+1, by
+1, TILE_SIZE
-1, TILE_SIZE
-1,
820 tile
== 1 ? COL_WRONG
: COL_RIGHT
);
823 * Draw a little diagram in the tile which indicates which
824 * surrounding tiles flip when this one is clicked.
826 for (i
= 0; i
< h
; i
++)
827 for (j
= 0; j
< w
; j
++)
828 if (state
->matrix
->matrix
[(y
*w
+x
)*wh
+ i
*w
+j
]) {
829 int ox
= j
- x
, oy
= i
- y
;
830 int td
= TILE_SIZE
/ 16;
831 int cx
= (bx
+ TILE_SIZE
/2) + (2 * ox
- 1) * td
;
832 int cy
= (by
+ TILE_SIZE
/2) + (2 * oy
- 1) * td
;
833 if (ox
== 0 && oy
== 0)
834 draw_rect(fe
, cx
, cy
, 2*td
+1, 2*td
+1, COL_DIAG
);
836 draw_line(fe
, cx
, cy
, cx
+2*td
, cy
, COL_DIAG
);
837 draw_line(fe
, cx
, cy
+2*td
, cx
+2*td
, cy
+2*td
, COL_DIAG
);
838 draw_line(fe
, cx
, cy
, cx
, cy
+2*td
, COL_DIAG
);
839 draw_line(fe
, cx
+2*td
, cy
, cx
+2*td
, cy
+2*td
, COL_DIAG
);
845 draw_update(fe
, bx
+1, by
+1, TILE_SIZE
-1, TILE_SIZE
-1);
848 static void game_redraw(frontend
*fe
, game_drawstate
*ds
, game_state
*oldstate
,
849 game_state
*state
, int dir
, game_ui
*ui
,
850 float animtime
, float flashtime
)
852 int w
= ds
->w
, h
= ds
->h
, wh
= w
* h
;
856 draw_rect(fe
, 0, 0, TILE_SIZE
* w
+ 2 * BORDER
,
857 TILE_SIZE
* h
+ 2 * BORDER
, COL_BACKGROUND
);
860 * Draw the grid lines.
862 for (i
= 0; i
<= w
; i
++)
863 draw_line(fe
, i
* TILE_SIZE
+ BORDER
, BORDER
,
864 i
* TILE_SIZE
+ BORDER
, h
* TILE_SIZE
+ BORDER
,
866 for (i
= 0; i
<= h
; i
++)
867 draw_line(fe
, BORDER
, i
* TILE_SIZE
+ BORDER
,
868 w
* TILE_SIZE
+ BORDER
, i
* TILE_SIZE
+ BORDER
,
871 draw_update(fe
, 0, 0, TILE_SIZE
* w
+ 2 * BORDER
,
872 TILE_SIZE
* h
+ 2 * BORDER
);
878 flashframe
= flashtime
/ FLASH_FRAME
;
882 for (i
= 0; i
< wh
; i
++) {
883 int x
= i
% w
, y
= i
/ w
;
885 int v
= state
->grid
[i
];
887 if (flashframe
>= 0) {
888 fx
= (w
+1)/2 - min(x
+1, w
-x
);
889 fy
= (h
+1)/2 - min(y
+1, h
-y
);
891 if (fd
== flashframe
)
893 else if (fd
== flashframe
- 1)
897 if (ds
->tiles
[i
] != v
) {
898 draw_tile(fe
, ds
, state
, x
, y
, v
);
906 sprintf(buf
, "%sMoves: %d", state
->completed ?
"COMPLETED! " : "",
913 static float game_anim_length(game_state
*oldstate
, game_state
*newstate
,
914 int dir
, game_ui
*ui
)
919 static float game_flash_length(game_state
*oldstate
, game_state
*newstate
,
920 int dir
, game_ui
*ui
)
922 if (!oldstate
->completed
&& newstate
->completed
)
923 return FLASH_FRAME
* (max((newstate
->w
+1)/2, (newstate
->h
+1)/2)+1);
928 static int game_wants_statusbar(void)
933 static int game_timing_state(game_state
*state
)
942 const struct game thegame
= {
950 TRUE
, game_configure
, custom_params
,
959 FALSE
, game_text_format
,
971 game_wants_statusbar
,
972 FALSE
, game_timing_state
,
973 0, /* mouse_priorities */