2 * twiddle.c: Puzzle involving rearranging a grid of squares by
3 * rotating subsquares. Adapted and generalised from a
4 * door-unlocking puzzle in Metroid Prime 2 (the one in the Main
11 * - it's horribly tempting to give the pieces significant
12 * _orientations_, perhaps by drawing some sort of oriented
13 * polygonal figure beneath the number. (An arrow pointing
14 * upwards springs readily to mind.)
27 #define BORDER (TILE_SIZE / 2)
28 #define HIGHLIGHT_WIDTH (TILE_SIZE / 20)
29 #define COORD(x) ( (x) * TILE_SIZE + BORDER )
30 #define FROMCOORD(x) ( ((x) - BORDER + TILE_SIZE) / TILE_SIZE - 1 )
32 #define PI 3.141592653589793238462643383279502884197169399
34 #define ANIM_PER_RADIUS_UNIT 0.13F
35 #define FLASH_FRAME 0.13F
57 int lastx
, lasty
, lastr
; /* coordinates of last rotation */
60 static game_params
*default_params(void)
62 game_params
*ret
= snew(game_params
);
66 ret
->rowsonly
= FALSE
;
72 static void free_params(game_params
*params
)
77 static game_params
*dup_params(game_params
*params
)
79 game_params
*ret
= snew(game_params
);
80 *ret
= *params
; /* structure copy */
84 static int game_fetch_preset(int i
, char **name
, game_params
**params
)
90 { "3x3 rows only", { 3, 3, 2, TRUE
} },
91 { "3x3 normal", { 3, 3, 2, FALSE
} },
92 { "4x4 normal", { 4, 4, 2, FALSE
} },
93 { "4x4 radius 3", { 4, 4, 3, FALSE
} },
94 { "5x5 radius 3", { 5, 5, 3, FALSE
} },
95 { "6x6 radius 4", { 6, 6, 4, FALSE
} },
98 if (i
< 0 || i
>= lenof(presets
))
101 *name
= dupstr(presets
[i
].title
);
102 *params
= dup_params(&presets
[i
].params
);
107 static game_params
*decode_params(char const *string
)
109 game_params
*ret
= snew(game_params
);
111 ret
->w
= ret
->h
= atoi(string
);
113 ret
->rowsonly
= FALSE
;
114 while (*string
&& isdigit(*string
)) string
++;
115 if (*string
== 'x') {
117 ret
->h
= atoi(string
);
118 while (*string
&& isdigit(*string
)) string
++;
120 if (*string
== 'n') {
122 ret
->n
= atoi(string
);
123 while (*string
&& isdigit(*string
)) string
++;
125 if (*string
== 'r') {
127 ret
->rowsonly
= TRUE
;
133 static char *encode_params(game_params
*params
)
136 sprintf(buf
, "%dx%dn%d%s", params
->w
, params
->h
, params
->n
,
137 params
->rowsonly ?
"r" : "");
141 static config_item
*game_configure(game_params
*params
)
146 ret
= snewn(4, config_item
);
148 ret
[0].name
= "Width";
149 ret
[0].type
= C_STRING
;
150 sprintf(buf
, "%d", params
->w
);
151 ret
[0].sval
= dupstr(buf
);
154 ret
[1].name
= "Height";
155 ret
[1].type
= C_STRING
;
156 sprintf(buf
, "%d", params
->h
);
157 ret
[1].sval
= dupstr(buf
);
160 ret
[2].name
= "Rotation radius";
161 ret
[2].type
= C_STRING
;
162 sprintf(buf
, "%d", params
->n
);
163 ret
[2].sval
= dupstr(buf
);
166 ret
[3].name
= "One number per row";
167 ret
[3].type
= C_BOOLEAN
;
169 ret
[3].ival
= params
->rowsonly
;
179 static game_params
*custom_params(config_item
*cfg
)
181 game_params
*ret
= snew(game_params
);
183 ret
->w
= atoi(cfg
[0].sval
);
184 ret
->h
= atoi(cfg
[1].sval
);
185 ret
->n
= atoi(cfg
[2].sval
);
186 ret
->rowsonly
= cfg
[3].ival
;
191 static char *validate_params(game_params
*params
)
194 return "Rotation radius must be at least two";
195 if (params
->w
< params
->n
)
196 return "Width must be at least the rotation radius";
197 if (params
->h
< params
->n
)
198 return "Height must be at least the rotation radius";
203 * This function actually performs a rotation on a grid. The `x'
204 * and `y' coordinates passed in are the coordinates of the _top
205 * left corner_ of the rotated region. (Using the centre would have
206 * involved half-integers and been annoyingly fiddly. Clicking in
207 * the centre is good for a user interface, but too inconvenient to
210 static void do_rotate(int *grid
, int w
, int h
, int n
, int x
, int y
, int dir
)
214 assert(x
>= 0 && x
+n
<= w
);
215 assert(y
>= 0 && y
+n
<= h
);
218 return; /* nothing to do */
220 grid
+= y
*w
+x
; /* translate region to top corner */
223 * If we were leaving the result of the rotation in a separate
224 * grid, the simple thing to do would be to loop over each
225 * square within the rotated region and assign it from its
226 * source square. However, to do it in place without taking
227 * O(n^2) memory, we need to be marginally more clever. What
228 * I'm going to do is loop over about one _quarter_ of the
229 * rotated region and permute each element within that quarter
230 * with its rotational coset.
232 * The size of the region I need to loop over is (n+1)/2 by
233 * n/2, which is an obvious exact quarter for even n and is a
234 * rectangle for odd n. (For odd n, this technique leaves out
235 * one element of the square, which is of course the central
236 * one that never moves anyway.)
238 for (i
= 0; i
< (n
+1)/2; i
++) {
239 for (j
= 0; j
< n
/2; j
++) {
249 for (k
= 0; k
< 4; k
++)
252 for (k
= 0; k
< 4; k
++)
253 grid
[p
[k
]] = g
[(k
+dir
) & 3];
258 static int grid_complete(int *grid
, int wh
)
262 for (i
= 1; i
< wh
; i
++)
263 if (grid
[i
] < grid
[i
-1])
268 static char *new_game_seed(game_params
*params
, random_state
*rs
)
271 int w
= params
->w
, h
= params
->h
, n
= params
->n
, wh
= w
*h
;
278 * Set up a solved grid.
280 grid
= snewn(wh
, int);
281 for (i
= 0; i
< wh
; i
++)
282 grid
[i
] = (params
->rowsonly ? i
/w
: i
) + 1;
285 * Shuffle it. This game is complex enough that I don't feel up
286 * to analysing its full symmetry properties (particularly at
287 * n=4 and above!), so I'm going to do it the pedestrian way
288 * and simply shuffle the grid by making a long sequence of
289 * randomly chosen moves.
291 total_moves
= w
*h
*n
*n
*2;
292 for (i
= 0; i
< total_moves
; i
++) {
295 x
= random_upto(rs
, w
- n
+ 1);
296 y
= random_upto(rs
, h
- n
+ 1);
297 do_rotate(grid
, w
, h
, n
, x
, y
, 1 + random_upto(rs
, 3));
300 * Optionally one more move in case the entire grid has
301 * happened to come out solved.
303 if (i
== total_moves
- 1 && grid_complete(grid
, wh
))
308 * Now construct the game seed, by describing the grid as a
309 * simple sequence of comma-separated integers.
313 for (i
= 0; i
< wh
; i
++) {
317 k
= sprintf(buf
, "%d,", grid
[i
]);
319 ret
= sresize(ret
, retlen
+ k
+ 1, char);
320 strcpy(ret
+ retlen
, buf
);
323 ret
[retlen
-1] = '\0'; /* delete last comma */
329 static char *validate_seed(game_params
*params
, char *seed
)
332 int w
= params
->w
, h
= params
->h
, wh
= w
*h
;
338 for (i
= 0; i
< wh
; i
++) {
339 if (*p
< '0' || *p
> '9') {
340 return "Not enough numbers in string";
342 while (*p
>= '0' && *p
<= '9')
344 if (i
< wh
-1 && *p
!= ',') {
345 return "Expected comma after number";
347 else if (i
== wh
-1 && *p
) {
348 return "Excess junk at end of string";
351 if (*p
) p
++; /* eat comma */
357 static game_state
*new_game(game_params
*params
, char *seed
)
359 game_state
*state
= snew(game_state
);
360 int w
= params
->w
, h
= params
->h
, n
= params
->n
, wh
= w
*h
;
367 state
->completed
= 0;
368 state
->movecount
= 0;
369 state
->lastx
= state
->lasty
= state
->lastr
= -1;
371 state
->grid
= snewn(wh
, int);
375 for (i
= 0; i
< wh
; i
++) {
376 state
->grid
[i
] = atoi(p
);
377 while (*p
>= '0' && *p
<= '9')
380 if (*p
) p
++; /* eat comma */
386 static game_state
*dup_game(game_state
*state
)
388 game_state
*ret
= snew(game_state
);
393 ret
->completed
= state
->completed
;
394 ret
->movecount
= state
->movecount
;
395 ret
->lastx
= state
->lastx
;
396 ret
->lasty
= state
->lasty
;
397 ret
->lastr
= state
->lastr
;
399 ret
->grid
= snewn(ret
->w
* ret
->h
, int);
400 memcpy(ret
->grid
, state
->grid
, ret
->w
* ret
->h
* sizeof(int));
405 static void free_game(game_state
*state
)
411 static game_ui
*new_ui(game_state
*state
)
416 static void free_ui(game_ui
*ui
)
420 static game_state
*make_move(game_state
*from
, game_ui
*ui
, int x
, int y
,
423 int w
= from
->w
, h
= from
->h
, n
= from
->n
, wh
= w
*h
;
427 if (button
== LEFT_BUTTON
|| button
== RIGHT_BUTTON
) {
429 * Determine the coordinates of the click. We offset by n-1
430 * half-blocks so that the user must click at the centre of
431 * a rotation region rather than at the corner.
433 x
-= (n
-1) * TILE_SIZE
/ 2;
434 y
-= (n
-1) * TILE_SIZE
/ 2;
437 if (x
< 0 || x
> w
-n
|| y
< 0 || y
> w
-n
)
441 * This is a valid move. Make it.
443 ret
= dup_game(from
);
445 dir
= (button
== LEFT_BUTTON ?
1 : -1);
446 do_rotate(ret
->grid
, w
, h
, n
, x
, y
, dir
);
452 * See if the game has been completed. To do this we simply
453 * test that the grid contents are in increasing order.
455 if (!ret
->completed
&& grid_complete(ret
->grid
, wh
))
456 ret
->completed
= ret
->movecount
;
462 /* ----------------------------------------------------------------------
466 struct game_drawstate
{
472 static void game_size(game_params
*params
, int *x
, int *y
)
474 *x
= TILE_SIZE
* params
->w
+ 2 * BORDER
;
475 *y
= TILE_SIZE
* params
->h
+ 2 * BORDER
;
478 static float *game_colours(frontend
*fe
, game_state
*state
, int *ncolours
)
480 float *ret
= snewn(3 * NCOLOURS
, float);
484 frontend_default_colour(fe
, &ret
[COL_BACKGROUND
* 3]);
487 * Drop the background colour so that the highlight is
488 * noticeably brighter than it while still being under 1.
490 max
= ret
[COL_BACKGROUND
*3];
491 for (i
= 1; i
< 3; i
++)
492 if (ret
[COL_BACKGROUND
*3+i
] > max
)
493 max
= ret
[COL_BACKGROUND
*3+i
];
494 if (max
* 1.2F
> 1.0F
) {
495 for (i
= 0; i
< 3; i
++)
496 ret
[COL_BACKGROUND
*3+i
] /= (max
* 1.2F
);
499 for (i
= 0; i
< 3; i
++) {
500 ret
[COL_HIGHLIGHT
* 3 + i
] = ret
[COL_BACKGROUND
* 3 + i
] * 1.2F
;
501 ret
[COL_HIGHLIGHT_GENTLE
* 3 + i
] = ret
[COL_BACKGROUND
* 3 + i
] * 1.1F
;
502 ret
[COL_LOWLIGHT
* 3 + i
] = ret
[COL_BACKGROUND
* 3 + i
] * 0.8F
;
503 ret
[COL_LOWLIGHT_GENTLE
* 3 + i
] = ret
[COL_BACKGROUND
* 3 + i
] * 0.9F
;
504 ret
[COL_TEXT
* 3 + i
] = 0.0;
507 *ncolours
= NCOLOURS
;
511 static game_drawstate
*game_new_drawstate(game_state
*state
)
513 struct game_drawstate
*ds
= snew(struct game_drawstate
);
519 ds
->bgcolour
= COL_BACKGROUND
;
520 ds
->grid
= snewn(ds
->w
*ds
->h
, int);
521 for (i
= 0; i
< ds
->w
*ds
->h
; i
++)
527 static void game_free_drawstate(game_drawstate
*ds
)
533 int cx
, cy
, cw
, ch
; /* clip region */
534 int ox
, oy
; /* rotation origin */
535 float c
, s
; /* cos and sin of rotation angle */
536 int lc
, rc
, tc
, bc
; /* colours of tile edges */
539 static void rotate(int *xy
, struct rotation
*rot
)
542 float xf
= xy
[0] - rot
->ox
, yf
= xy
[1] - rot
->oy
;
545 xf2
= rot
->c
* xf
+ rot
->s
* yf
;
546 yf2
= - rot
->s
* xf
+ rot
->c
* yf
;
548 xy
[0] = xf2
+ rot
->ox
+ 0.5; /* round to nearest */
549 xy
[1] = yf2
+ rot
->oy
+ 0.5; /* round to nearest */
553 static void draw_tile(frontend
*fe
, game_state
*state
, int x
, int y
,
554 int tile
, int flash_colour
, struct rotation
*rot
)
560 clip(fe
, rot
->cx
, rot
->cy
, rot
->cw
, rot
->ch
);
563 * We must draw each side of the tile's highlight separately,
564 * because in some cases (during rotation) they will all need
565 * to be different colours.
568 /* The centre point is common to all sides. */
569 coords
[4] = x
+ TILE_SIZE
/ 2;
570 coords
[5] = y
+ TILE_SIZE
/ 2;
571 rotate(coords
+4, rot
);
574 coords
[0] = x
+ TILE_SIZE
- 1;
575 coords
[1] = y
+ TILE_SIZE
- 1;
576 rotate(coords
+0, rot
);
577 coords
[2] = x
+ TILE_SIZE
- 1;
579 rotate(coords
+2, rot
);
580 draw_polygon(fe
, coords
, 3, TRUE
, rot ? rot
->rc
: COL_LOWLIGHT
);
581 draw_polygon(fe
, coords
, 3, FALSE
, rot ? rot
->rc
: COL_LOWLIGHT
);
585 coords
[3] = y
+ TILE_SIZE
- 1;
586 rotate(coords
+2, rot
);
587 draw_polygon(fe
, coords
, 3, TRUE
, rot ? rot
->bc
: COL_LOWLIGHT
);
588 draw_polygon(fe
, coords
, 3, FALSE
, rot ? rot
->bc
: COL_LOWLIGHT
);
593 rotate(coords
+0, rot
);
594 draw_polygon(fe
, coords
, 3, TRUE
, rot ? rot
->lc
: COL_HIGHLIGHT
);
595 draw_polygon(fe
, coords
, 3, FALSE
, rot ? rot
->lc
: COL_HIGHLIGHT
);
598 coords
[2] = x
+ TILE_SIZE
- 1;
600 rotate(coords
+2, rot
);
601 draw_polygon(fe
, coords
, 3, TRUE
, rot ? rot
->tc
: COL_HIGHLIGHT
);
602 draw_polygon(fe
, coords
, 3, FALSE
, rot ? rot
->tc
: COL_HIGHLIGHT
);
605 coords
[0] = x
+ HIGHLIGHT_WIDTH
;
606 coords
[1] = y
+ HIGHLIGHT_WIDTH
;
607 rotate(coords
+0, rot
);
608 coords
[2] = x
+ HIGHLIGHT_WIDTH
;
609 coords
[3] = y
+ TILE_SIZE
- 1 - HIGHLIGHT_WIDTH
;
610 rotate(coords
+2, rot
);
611 coords
[4] = x
+ TILE_SIZE
- 1 - HIGHLIGHT_WIDTH
;
612 coords
[5] = y
+ TILE_SIZE
- 1 - HIGHLIGHT_WIDTH
;
613 rotate(coords
+4, rot
);
614 coords
[6] = x
+ TILE_SIZE
- 1 - HIGHLIGHT_WIDTH
;
615 coords
[7] = y
+ HIGHLIGHT_WIDTH
;
616 rotate(coords
+6, rot
);
617 draw_polygon(fe
, coords
, 4, TRUE
, flash_colour
);
618 draw_polygon(fe
, coords
, 4, FALSE
, flash_colour
);
620 draw_rect(fe
, x
+ HIGHLIGHT_WIDTH
, y
+ HIGHLIGHT_WIDTH
,
621 TILE_SIZE
- 2*HIGHLIGHT_WIDTH
, TILE_SIZE
- 2*HIGHLIGHT_WIDTH
,
625 coords
[0] = x
+ TILE_SIZE
/2;
626 coords
[1] = y
+ TILE_SIZE
/2;
627 rotate(coords
+0, rot
);
628 sprintf(str
, "%d", tile
);
629 draw_text(fe
, coords
[0], coords
[1],
630 FONT_VARIABLE
, TILE_SIZE
/3, ALIGN_VCENTRE
| ALIGN_HCENTRE
,
636 draw_update(fe
, x
, y
, TILE_SIZE
, TILE_SIZE
);
639 static int highlight_colour(float angle
)
646 COL_HIGHLIGHT_GENTLE
,
647 COL_HIGHLIGHT_GENTLE
,
648 COL_HIGHLIGHT_GENTLE
,
659 COL_HIGHLIGHT_GENTLE
,
660 COL_HIGHLIGHT_GENTLE
,
661 COL_HIGHLIGHT_GENTLE
,
676 return colours
[(int)((angle
+ 2*PI
) / (PI
/16)) & 31];
679 static float game_anim_length(game_state
*oldstate
, game_state
*newstate
,
682 return ANIM_PER_RADIUS_UNIT
* sqrt(newstate
->n
-1);
685 static float game_flash_length(game_state
*oldstate
, game_state
*newstate
,
688 if (!oldstate
->completed
&& newstate
->completed
)
689 return 2 * FLASH_FRAME
;
694 static void game_redraw(frontend
*fe
, game_drawstate
*ds
, game_state
*oldstate
,
695 game_state
*state
, int dir
, game_ui
*ui
,
696 float animtime
, float flashtime
)
699 struct rotation srot
, *rot
;
700 int lastx
= -1, lasty
= -1, lastr
= -1;
703 int frame
= (int)(flashtime
/ FLASH_FRAME
);
704 bgcolour
= (frame
% 2 ? COL_LOWLIGHT
: COL_HIGHLIGHT
);
706 bgcolour
= COL_BACKGROUND
;
712 TILE_SIZE
* state
->w
+ 2 * BORDER
,
713 TILE_SIZE
* state
->h
+ 2 * BORDER
, COL_BACKGROUND
);
714 draw_update(fe
, 0, 0,
715 TILE_SIZE
* state
->w
+ 2 * BORDER
,
716 TILE_SIZE
* state
->h
+ 2 * BORDER
);
719 * Recessed area containing the whole puzzle.
721 coords
[0] = COORD(state
->w
) + HIGHLIGHT_WIDTH
- 1;
722 coords
[1] = COORD(state
->h
) + HIGHLIGHT_WIDTH
- 1;
723 coords
[2] = COORD(state
->w
) + HIGHLIGHT_WIDTH
- 1;
724 coords
[3] = COORD(0) - HIGHLIGHT_WIDTH
;
725 coords
[4] = COORD(0) - HIGHLIGHT_WIDTH
;
726 coords
[5] = COORD(state
->h
) + HIGHLIGHT_WIDTH
- 1;
727 draw_polygon(fe
, coords
, 3, TRUE
, COL_HIGHLIGHT
);
728 draw_polygon(fe
, coords
, 3, FALSE
, COL_HIGHLIGHT
);
730 coords
[1] = COORD(0) - HIGHLIGHT_WIDTH
;
731 coords
[0] = COORD(0) - HIGHLIGHT_WIDTH
;
732 draw_polygon(fe
, coords
, 3, TRUE
, COL_LOWLIGHT
);
733 draw_polygon(fe
, coords
, 3, FALSE
, COL_LOWLIGHT
);
739 * If we're drawing any rotated tiles, sort out the rotation
740 * parameters, and also zap the rotation region to the
741 * background colour before doing anything else.
745 float anim_max
= game_anim_length(oldstate
, state
, dir
);
748 lastx
= state
->lastx
;
749 lasty
= state
->lasty
;
750 lastr
= state
->lastr
;
752 lastx
= oldstate
->lastx
;
753 lasty
= oldstate
->lasty
;
754 lastr
= -oldstate
->lastr
;
758 rot
->cx
= COORD(lastx
);
759 rot
->cy
= COORD(lasty
);
760 rot
->cw
= rot
->ch
= TILE_SIZE
* state
->n
;
761 rot
->ox
= rot
->cx
+ rot
->cw
/2;
762 rot
->oy
= rot
->cy
+ rot
->ch
/2;
763 angle
= (-PI
/2 * lastr
) * (1.0 - animtime
/ anim_max
);
768 * Sort out the colours of the various sides of the tile.
770 rot
->lc
= highlight_colour(PI
+ angle
);
771 rot
->rc
= highlight_colour(angle
);
772 rot
->tc
= highlight_colour(PI
/2 + angle
);
773 rot
->bc
= highlight_colour(-PI
/2 + angle
);
775 draw_rect(fe
, rot
->cx
, rot
->cy
, rot
->cw
, rot
->ch
, bgcolour
);
780 * Now draw each tile.
782 for (i
= 0; i
< state
->w
* state
->h
; i
++) {
784 int tx
= i
% state
->w
, ty
= i
/ state
->w
;
787 * Figure out what should be displayed at this location.
788 * Usually it will be state->grid[i], unless we're in the
789 * middle of animating an actual rotation and this cell is
790 * within the rotation region, in which case we set -1
793 if (oldstate
&& lastx
>= 0 && lasty
>= 0 &&
794 tx
>= lastx
&& tx
< lastx
+ state
->n
&&
795 ty
>= lasty
&& ty
< lasty
+ state
->n
)
800 if (ds
->bgcolour
!= bgcolour
|| /* always redraw when flashing */
801 ds
->grid
[i
] != t
|| ds
->grid
[i
] == -1 || t
== -1) {
802 int x
= COORD(tx
), y
= COORD(ty
);
804 draw_tile(fe
, state
, x
, y
, state
->grid
[i
], bgcolour
, rot
);
808 ds
->bgcolour
= bgcolour
;
811 * Update the status bar.
817 * Don't show the new status until we're also showing the
818 * new _state_ - after the game animation is complete.
823 sprintf(statusbuf
, "%sMoves: %d",
824 (state
->completed ?
"COMPLETED! " : ""),
825 (state
->completed ? state
->completed
: state
->movecount
));
827 status_bar(fe
, statusbuf
);
831 static int game_wants_statusbar(void)
837 #define thegame twiddle
840 const struct game thegame
= {
841 "Twiddle", "games.twiddle", TRUE
,
866 game_wants_statusbar
,