2 * 'same game' -- try to remove all the coloured squares by
3 * selecting regions of contiguous colours.
7 * TODO on grid generation:
9 * - Generation speed could still be improved.
10 * * 15x10c3 is the only really difficult one of the existing
11 * presets. The others are all either small enough, or have
12 * the great flexibility given by four colours, that they
13 * don't take long at all.
14 * * I still suspect many problems arise from separate
15 * subareas. I wonder if we can also somehow prioritise left-
16 * or rightmost insertions so as to avoid area splitting at
17 * all where feasible? It's not easy, though, because the
18 * current shuffle-then-try-all-options approach to move
19 * choice doesn't leave room for `soft' probabilistic
20 * prioritisation: we either try all class A moves before any
21 * class B ones, or we don't.
23 * - The current generation algorithm inserts exactly two squares
24 * at a time, with a single exception at the beginning of
25 * generation for grids of odd overall size. An obvious
26 * extension would be to permit larger inverse moves during
28 * * this might reduce the number of failed generations by
29 * making the insertion algorithm more flexible
30 * * on the other hand, it would be significantly more complex
31 * * if I do this I'll need to take out the odd-subarea
33 * * a nice feature of the current algorithm is that the
34 * computer's `intended' solution always receives the minimum
35 * possible score, so that pretty much the player's entire
36 * score represents how much better they did than the
39 * - Is it possible we can _temporarily_ tolerate neighbouring
40 * squares of the same colour, until we've finished setting up
42 * * or perhaps even not choose the colour of our inserted
43 * region until we have finished placing it, and _then_ look
44 * at what colours border on it?
45 * * I don't think this is currently meaningful unless we're
46 * placing more than a domino at a time.
48 * - possibly write out a full solution so that Solve can somehow
49 * show it step by step?
50 * * aux_info would have to encode the click points
51 * * solve_game() would have to encode not only those click
52 * points but also give a move string which reconstructed the
54 * * the game_state would include a pointer to a solution move
55 * list, plus an index into that list
56 * * game_changed_state would auto-select the next move if
57 * handed a new state which had a solution move list active
58 * * execute_move, if passed such a state as input, would check
59 * to see whether the move being made was the same as the one
60 * stated by the solution, and if so would advance the move
61 * index. Failing that it would return a game_state without a
62 * solution move list active at all.
74 #define TILE_INNER (ds->tileinner)
75 #define TILE_GAP (ds->tilegap)
76 #define TILE_SIZE (TILE_INNER + TILE_GAP)
77 #define PREFERRED_TILE_SIZE 32
78 #define BORDER (TILE_SIZE / 2)
79 #define HIGHLIGHT_WIDTH 2
81 #define FLASH_FRAME 0.13F
83 #define COORD(x) ( (x) * TILE_SIZE + BORDER )
84 #define FROMCOORD(x) ( ((x) - BORDER + TILE_SIZE) / TILE_SIZE - 1 )
86 #define X(state, i) ( (i) % (state)->params.w )
87 #define Y(state, i) ( (i) / (state)->params.w )
88 #define C(state, x, y) ( (y) * (state)->w + (x) )
92 COL_1
, COL_2
, COL_3
, COL_4
, COL_5
, COL_6
, COL_7
, COL_8
, COL_9
,
93 COL_IMPOSSIBLE
, COL_SEL
, COL_HIGHLIGHT
, COL_LOWLIGHT
,
97 /* scoresub is 1 or 2 (for (n-1)^2 or (n-2)^2) */
99 int w
, h
, ncols
, scoresub
;
100 int soluble
; /* choose generation algorithm */
103 /* These flags must be unique across all uses; in the game_state,
104 * the game_ui, and the drawstate (as they all get combined in the
106 #define TILE_COLMASK 0x00ff
107 #define TILE_SELECTED 0x0100 /* used in ui and drawstate */
108 #define TILE_JOINRIGHT 0x0200 /* used in drawstate */
109 #define TILE_JOINDOWN 0x0400 /* used in drawstate */
110 #define TILE_JOINDIAG 0x0800 /* used in drawstate */
111 #define TILE_HASSEL 0x1000 /* used in drawstate */
112 #define TILE_IMPOSSIBLE 0x2000 /* used in drawstate */
114 #define TILE(gs,x,y) ((gs)->tiles[(gs)->params.w*(y)+(x)])
115 #define COL(gs,x,y) (TILE(gs,x,y) & TILE_COLMASK)
116 #define ISSEL(gs,x,y) (TILE(gs,x,y) & TILE_SELECTED)
118 #define SWAPTILE(gs,x1,y1,x2,y2) do { \
119 int t = TILE(gs,x1,y1); \
120 TILE(gs,x1,y1) = TILE(gs,x2,y2); \
121 TILE(gs,x2,y2) = t; \
124 static int npoints(game_params
*params
, int nsel
)
126 int sdiff
= nsel
- params
->scoresub
;
127 return (sdiff
> 0) ? sdiff
* sdiff
: 0;
131 struct game_params params
;
133 int *tiles
; /* colour only */
135 int complete
, impossible
;
138 static game_params
*default_params(void)
140 game_params
*ret
= snew(game_params
);
149 static const struct game_params samegame_presets
[] = {
150 { 5, 5, 3, 2, TRUE
},
151 { 10, 5, 3, 2, TRUE
},
152 { 15, 10, 3, 2, TRUE
},
153 { 15, 10, 4, 2, TRUE
},
154 { 20, 15, 4, 2, TRUE
}
157 static int game_fetch_preset(int i
, char **name
, game_params
**params
)
162 if (i
< 0 || i
>= lenof(samegame_presets
))
165 ret
= snew(game_params
);
166 *ret
= samegame_presets
[i
];
168 sprintf(str
, "%dx%d, %d colours", ret
->w
, ret
->h
, ret
->ncols
);
175 static void free_params(game_params
*params
)
180 static game_params
*dup_params(game_params
*params
)
182 game_params
*ret
= snew(game_params
);
183 *ret
= *params
; /* structure copy */
187 static void decode_params(game_params
*params
, char const *string
)
189 char const *p
= string
;
192 while (*p
&& isdigit((unsigned char)*p
)) p
++;
196 while (*p
&& isdigit((unsigned char)*p
)) p
++;
198 params
->h
= params
->w
;
202 params
->ncols
= atoi(p
);
203 while (*p
&& isdigit((unsigned char)*p
)) p
++;
209 params
->scoresub
= atoi(p
);
210 while (*p
&& isdigit((unsigned char)*p
)) p
++;
212 params
->scoresub
= 2;
216 params
->soluble
= FALSE
;
220 static char *encode_params(game_params
*params
, int full
)
224 sprintf(ret
, "%dx%dc%ds%d%s",
225 params
->w
, params
->h
, params
->ncols
, params
->scoresub
,
226 full
&& !params
->soluble ?
"r" : "");
230 static config_item
*game_configure(game_params
*params
)
235 ret
= snewn(6, config_item
);
237 ret
[0].name
= "Width";
238 ret
[0].type
= C_STRING
;
239 sprintf(buf
, "%d", params
->w
);
240 ret
[0].sval
= dupstr(buf
);
243 ret
[1].name
= "Height";
244 ret
[1].type
= C_STRING
;
245 sprintf(buf
, "%d", params
->h
);
246 ret
[1].sval
= dupstr(buf
);
249 ret
[2].name
= "No. of colours";
250 ret
[2].type
= C_STRING
;
251 sprintf(buf
, "%d", params
->ncols
);
252 ret
[2].sval
= dupstr(buf
);
255 ret
[3].name
= "Scoring system";
256 ret
[3].type
= C_CHOICES
;
257 ret
[3].sval
= ":(n-1)^2:(n-2)^2";
258 ret
[3].ival
= params
->scoresub
-1;
260 ret
[4].name
= "Ensure solubility";
261 ret
[4].type
= C_BOOLEAN
;
263 ret
[4].ival
= params
->soluble
;
273 static game_params
*custom_params(config_item
*cfg
)
275 game_params
*ret
= snew(game_params
);
277 ret
->w
= atoi(cfg
[0].sval
);
278 ret
->h
= atoi(cfg
[1].sval
);
279 ret
->ncols
= atoi(cfg
[2].sval
);
280 ret
->scoresub
= cfg
[3].ival
+ 1;
281 ret
->soluble
= cfg
[4].ival
;
286 static char *validate_params(game_params
*params
, int full
)
288 if (params
->w
< 1 || params
->h
< 1)
289 return "Width and height must both be positive";
291 if (params
->ncols
> 9)
292 return "Maximum of 9 colours";
294 if (params
->soluble
) {
295 if (params
->ncols
< 3)
296 return "Number of colours must be at least three";
297 if (params
->w
* params
->h
<= 1)
298 return "Grid area must be greater than 1";
300 if (params
->ncols
< 2)
301 return "Number of colours must be at least three";
302 /* ...and we must make sure we can generate at least 2 squares
303 * of each colour so it's theoretically soluble. */
304 if ((params
->w
* params
->h
) < (params
->ncols
* 2))
305 return "Too many colours makes given grid size impossible";
308 if ((params
->scoresub
< 1) || (params
->scoresub
> 2))
309 return "Scoring system not recognised";
315 * Guaranteed-soluble grid generator.
317 static void gen_grid(int w
, int h
, int nc
, int *grid
, random_state
*rs
)
319 int wh
= w
*h
, tc
= nc
+1;
320 int i
, j
, k
, c
, x
, y
, pos
, n
;
322 int ok
, failures
= 0;
325 * We'll use `list' to track the possible places to put our
326 * next insertion. There are up to h places to insert in each
327 * column: in a column of height n there are n+1 places because
328 * we can insert at the very bottom or the very top, but a
329 * column of height h can't have anything at all inserted in it
330 * so we have up to h in each column. Likewise, with n columns
331 * present there are n+1 places to fit a new one in between but
332 * we can't insert a column if there are already w; so there
333 * are a maximum of w new columns too. Total is wh + w.
335 list
= snewn(wh
+ w
, int);
336 grid2
= snewn(wh
, int);
340 * Start with two or three squares - depending on parity of w*h
341 * - of a random colour.
343 for (i
= 0; i
< wh
; i
++)
346 c
= 1 + random_upto(rs
, nc
);
348 for (i
= 0; i
< j
; i
++)
352 for (i
= 0; i
< j
; i
++)
357 * Now repeatedly insert a two-square blob in the grid, of
358 * whatever colour will go at the position we chose.
364 * Build up a list of insertion points. Each point is
365 * encoded as y*w+x; insertion points between columns are
369 if (grid
[wh
- 1] == 0) {
371 * The final column is empty, so we can insert new
374 for (i
= 0; i
< w
; i
++) {
376 if (grid
[(h
-1)*w
+ i
] == 0)
382 * Now look for places to insert within columns.
384 for (i
= 0; i
< w
; i
++) {
385 if (grid
[(h
-1)*w
+i
] == 0)
386 break; /* no more columns */
389 continue; /* this column is full */
391 for (j
= h
; j
-- > 0 ;) {
393 if (grid
[j
*w
+i
] == 0)
394 break; /* this column is exhausted */
399 break; /* we're done */
401 #ifdef GENERATION_DIAGNOSTICS
402 printf("initial grid:\n");
405 for (y
= 0; y
< h
; y
++) {
406 for (x
= 0; x
< w
; x
++) {
407 if (grid
[y
*w
+x
] == 0)
410 printf("%d", grid
[y
*w
+x
]);
418 * Now go through the list one element at a time in
419 * random order, and actually attempt to insert
423 int dirs
[4], ndirs
, dir
;
425 i
= random_upto(rs
, n
+1);
432 memcpy(grid2
, grid
, wh
* sizeof(int));
436 * Insert a column at position x.
438 for (i
= w
-1; i
> x
; i
--)
439 for (j
= 0; j
< h
; j
++)
440 grid2
[j
*w
+i
] = grid2
[j
*w
+(i
-1)];
442 * Clear the new column.
444 for (j
= 0; j
< h
; j
++)
447 * Decrement y so that our first square is actually
448 * inserted _in_ the grid rather than just below it.
454 * Insert a square within column x at position y.
456 for (i
= 0; i
+1 <= y
; i
++)
457 grid2
[i
*w
+x
] = grid2
[(i
+1)*w
+x
];
459 #ifdef GENERATION_DIAGNOSTICS
460 printf("trying at n=%d (%d,%d)\n", n
, x
, y
);
464 for (y
= 0; y
< h
; y
++) {
465 for (x
= 0; x
< w
; x
++) {
466 if (grid2
[y
*w
+x
] == 0)
468 else if (grid2
[y
*w
+x
] <= nc
)
469 printf("%d", grid2
[y
*w
+x
]);
479 * Pick our square colour so that it doesn't match any
483 int wrongcol
[4], nwrong
= 0;
486 * List the neighbouring colours.
489 wrongcol
[nwrong
++] = grid2
[y
*w
+(x
-1)];
491 wrongcol
[nwrong
++] = grid2
[y
*w
+(x
+1)];
493 wrongcol
[nwrong
++] = grid2
[(y
-1)*w
+x
];
495 wrongcol
[nwrong
++] = grid2
[(y
+1)*w
+x
];
498 * Eliminate duplicates. We can afford a shoddy
499 * algorithm here because the problem size is
502 for (i
= j
= 0 ;; i
++) {
503 int pos
= -1, min
= 0;
506 for (k
= i
; k
< nwrong
; k
++)
507 if (wrongcol
[k
] > min
&&
508 (pos
== -1 || wrongcol
[k
] < wrongcol
[pos
]))
511 int v
= wrongcol
[pos
];
512 wrongcol
[pos
] = wrongcol
[j
];
520 * If no colour will go here, stop trying.
526 * Otherwise, pick a colour from the remaining
529 c
= 1 + random_upto(rs
, nc
- nwrong
);
530 for (i
= 0; i
< nwrong
; i
++) {
531 if (c
>= wrongcol
[i
])
539 * Place the new square.
541 * Although I've _chosen_ the new region's colour
542 * (so that we can check adjacency), I'm going to
543 * actually place it as an invalid colour (tc)
544 * until I'm sure it's viable. This is so that I
545 * can conveniently check that I really have made a
546 * _valid_ inverse move later on.
548 #ifdef GENERATION_DIAGNOSTICS
549 printf("picked colour %d\n", c
);
554 * Now attempt to extend it in one of three ways: left,
559 grid2
[y
*w
+(x
-1)] != c
&&
561 (y
+1 >= h
|| grid2
[(y
+1)*w
+(x
-1)] != c
) &&
562 (y
+1 >= h
|| grid2
[(y
+1)*w
+(x
-1)] != 0) &&
563 (x
<= 1 || grid2
[y
*w
+(x
-2)] != c
))
564 dirs
[ndirs
++] = -1; /* left */
566 grid2
[y
*w
+(x
+1)] != c
&&
568 (y
+1 >= h
|| grid2
[(y
+1)*w
+(x
+1)] != c
) &&
569 (y
+1 >= h
|| grid2
[(y
+1)*w
+(x
+1)] != 0) &&
570 (x
+2 >= w
|| grid2
[y
*w
+(x
+2)] != c
))
571 dirs
[ndirs
++] = +1; /* right */
574 (x
<= 0 || grid2
[(y
-1)*w
+(x
-1)] != c
) &&
575 (x
+1 >= w
|| grid2
[(y
-1)*w
+(x
+1)] != c
)) {
577 * We add this possibility _twice_, so that the
578 * probability of placing a vertical domino is
579 * about the same as that of a horizontal. This
580 * should yield less bias in the generated
583 dirs
[ndirs
++] = 0; /* up */
584 dirs
[ndirs
++] = 0; /* up */
590 dir
= dirs
[random_upto(rs
, ndirs
)];
592 #ifdef GENERATION_DIAGNOSTICS
593 printf("picked dir %d\n", dir
);
597 * Insert a square within column (x+dir) at position y.
599 for (i
= 0; i
+1 <= y
; i
++)
600 grid2
[i
*w
+x
+dir
] = grid2
[(i
+1)*w
+x
+dir
];
601 grid2
[y
*w
+x
+dir
] = tc
;
604 * See if we've divided the remaining grid squares
605 * into sub-areas. If so, we need every sub-area to
606 * have an even area or we won't be able to
607 * complete generation.
609 * If the height is odd and not all columns are
610 * present, we can increase the area of a subarea
611 * by adding a new column in it, so in that
612 * situation we don't mind having as many odd
613 * subareas as there are spare columns.
615 * If the height is even, we can't fix it at all.
618 int nerrs
= 0, nfix
= 0;
619 k
= 0; /* current subarea size */
620 for (i
= 0; i
< w
; i
++) {
621 if (grid2
[(h
-1)*w
+i
] == 0) {
626 for (j
= 0; j
< h
&& grid2
[j
*w
+i
] == 0; j
++);
630 * End of previous subarea.
642 continue; /* try a different placement */
646 * We've made a move. Verify that it is a valid
647 * move and that if made it would indeed yield the
648 * previous grid state. The criteria are:
650 * (a) removing all the squares of colour tc (and
651 * shuffling the columns up etc) from grid2
653 * (b) no square of colour tc is adjacent to one
655 * (c) all the squares of colour tc form a single
656 * connected component
658 * We verify the latter property at the same time
659 * as checking that removing all the tc squares
660 * would yield the previous grid. Then we colour
661 * the tc squares in colour c by breadth-first
662 * search, which conveniently permits us to test
663 * that they're all connected.
668 int fillstart
= -1, ntc
= 0;
670 #ifdef GENERATION_DIAGNOSTICS
673 printf("testing move (new, old):\n");
674 for (y
= 0; y
< h
; y
++) {
675 for (x
= 0; x
< w
; x
++) {
676 if (grid2
[y
*w
+x
] == 0)
678 else if (grid2
[y
*w
+x
] <= nc
)
679 printf("%d", grid2
[y
*w
+x
]);
684 for (x
= 0; x
< w
; x
++) {
685 if (grid
[y
*w
+x
] == 0)
688 printf("%d", grid
[y
*w
+x
]);
695 for (x1
= x2
= 0; x2
< w
; x2
++) {
698 for (y1
= y2
= h
-1; y2
>= 0; y2
--) {
699 if (grid2
[y2
*w
+x2
] == tc
) {
703 if ((y2
+1 < h
&& grid2
[(y2
+1)*w
+x2
] == c
) ||
704 (y2
-1 >= 0 && grid2
[(y2
-1)*w
+x2
] == c
) ||
705 (x2
+1 < w
&& grid2
[y2
*w
+x2
+1] == c
) ||
706 (x2
-1 >= 0 && grid2
[y2
*w
+x2
-1] == c
)) {
707 #ifdef GENERATION_DIAGNOSTICS
708 printf("adjacency failure at %d,%d\n",
715 if (grid2
[y2
*w
+x2
] == 0)
718 if (grid2
[y2
*w
+x2
] != grid
[y1
*w
+x1
]) {
719 #ifdef GENERATION_DIAGNOSTICS
720 printf("matching failure at %d,%d vs %d,%d\n",
729 * If we've reached the top of the column
730 * in grid2, verify that we've also reached
731 * the top of the column in `grid'.
735 if (grid
[y1
*w
+x1
] != 0) {
736 #ifdef GENERATION_DIAGNOSTICS
737 printf("junk at column top (%d,%d)\n",
754 assert(!"This should never happen");
757 * If this game is compiled NDEBUG so that
758 * the assertion doesn't bring it to a
759 * crashing halt, the only thing we can do
760 * is to give up, loop round again, and
761 * hope to randomly avoid making whatever
762 * type of move just caused this failure.
768 * Now use bfs to fill in the tc section as
769 * colour c. We use `list' to store the set of
770 * squares we have to process.
773 assert(fillstart
>= 0);
774 list
[i
++] = fillstart
;
775 #ifdef OUTPUT_SOLUTION
782 #ifdef OUTPUT_SOLUTION
783 printf("%s%d", j ?
"," : "", k
);
787 assert(grid2
[k
] == tc
);
790 if (x
> 0 && grid2
[k
-1] == tc
)
792 if (x
+1 < w
&& grid2
[k
+1] == tc
)
794 if (y
> 0 && grid2
[k
-w
] == tc
)
796 if (y
+1 < h
&& grid2
[k
+w
] == tc
)
799 #ifdef OUTPUT_SOLUTION
804 * Check that we've filled the same number of
805 * tc squares as we originally found.
810 memcpy(grid
, grid2
, wh
* sizeof(int));
812 break; /* done it! */
815 #ifdef GENERATION_DIAGNOSTICS
819 for (y
= 0; y
< h
; y
++) {
820 for (x
= 0; x
< w
; x
++) {
821 if (grid
[y
*w
+x
] == 0)
824 printf("%d", grid
[y
*w
+x
]);
836 for (i
= 0; i
< wh
; i
++)
840 #if defined GENERATION_DIAGNOSTICS || defined SHOW_INCOMPLETE
843 printf("incomplete grid:\n");
844 for (y
= 0; y
< h
; y
++) {
845 for (x
= 0; x
< w
; x
++) {
846 if (grid
[y
*w
+x
] == 0)
849 printf("%d", grid
[y
*w
+x
]);
860 #if defined GENERATION_DIAGNOSTICS || defined COUNT_FAILURES
861 printf("%d failures\n", failures
);
863 #ifdef GENERATION_DIAGNOSTICS
866 printf("final grid:\n");
867 for (y
= 0; y
< h
; y
++) {
868 for (x
= 0; x
< w
; x
++) {
869 printf("%d", grid
[y
*w
+x
]);
881 * Not-guaranteed-soluble grid generator; kept as a legacy, and in
882 * case someone finds the slightly odd quality of the guaranteed-
883 * soluble grids to be aesthetically displeasing or finds its CPU
884 * utilisation to be excessive.
886 static void gen_grid_random(int w
, int h
, int nc
, int *grid
, random_state
*rs
)
891 for (i
= 0; i
< n
; i
++)
895 * Our sole concession to not gratuitously generating insoluble
896 * grids is to ensure we have at least two of every colour.
898 for (c
= 1; c
<= nc
; c
++) {
899 for (j
= 0; j
< 2; j
++) {
901 i
= (int)random_upto(rs
, n
);
902 } while (grid
[i
] != 0);
908 * Fill in the rest of the grid at random.
910 for (i
= 0; i
< n
; i
++) {
912 grid
[i
] = (int)random_upto(rs
, nc
)+1;
916 static char *new_game_desc(game_params
*params
, random_state
*rs
,
917 char **aux
, int interactive
)
920 int n
, i
, retlen
, *tiles
;
922 n
= params
->w
* params
->h
;
923 tiles
= snewn(n
, int);
926 gen_grid(params
->w
, params
->h
, params
->ncols
, tiles
, rs
);
928 gen_grid_random(params
->w
, params
->h
, params
->ncols
, tiles
, rs
);
932 for (i
= 0; i
< n
; i
++) {
936 k
= sprintf(buf
, "%d,", tiles
[i
]);
937 ret
= sresize(ret
, retlen
+ k
+ 1, char);
938 strcpy(ret
+ retlen
, buf
);
941 ret
[retlen
-1] = '\0'; /* delete last comma */
947 static char *validate_desc(game_params
*params
, char *desc
)
949 int area
= params
->w
* params
->h
, i
;
952 for (i
= 0; i
< area
; i
++) {
956 if (!isdigit((unsigned char)*p
))
957 return "Not enough numbers in string";
958 while (isdigit((unsigned char)*p
)) p
++;
960 if (i
< area
-1 && *p
!= ',')
961 return "Expected comma after number";
962 else if (i
== area
-1 && *p
)
963 return "Excess junk at end of string";
966 if (n
< 0 || n
> params
->ncols
)
967 return "Colour out of range";
969 if (*p
) p
++; /* eat comma */
974 static game_state
*new_game(midend_data
*me
, game_params
*params
, char *desc
)
976 game_state
*state
= snew(game_state
);
980 state
->params
= *params
; /* struct copy */
981 state
->n
= state
->params
.w
* state
->params
.h
;
982 state
->tiles
= snewn(state
->n
, int);
984 for (i
= 0; i
< state
->n
; i
++) {
986 state
->tiles
[i
] = atoi(p
);
987 while (*p
&& *p
!= ',')
989 if (*p
) p
++; /* eat comma */
991 state
->complete
= state
->impossible
= 0;
997 static game_state
*dup_game(game_state
*state
)
999 game_state
*ret
= snew(game_state
);
1001 *ret
= *state
; /* structure copy, except... */
1003 ret
->tiles
= snewn(state
->n
, int);
1004 memcpy(ret
->tiles
, state
->tiles
, state
->n
* sizeof(int));
1009 static void free_game(game_state
*state
)
1011 sfree(state
->tiles
);
1015 static char *solve_game(game_state
*state
, game_state
*currstate
,
1016 char *aux
, char **error
)
1021 static char *game_text_format(game_state
*state
)
1026 maxlen
= state
->params
.h
* (state
->params
.w
+ 1);
1027 ret
= snewn(maxlen
+1, char);
1030 for (y
= 0; y
< state
->params
.h
; y
++) {
1031 for (x
= 0; x
< state
->params
.w
; x
++) {
1032 int t
= TILE(state
,x
,y
);
1033 if (t
<= 0) *p
++ = ' ';
1034 else if (t
< 10) *p
++ = '0'+t
;
1035 else *p
++ = 'a'+(t
-10);
1039 assert(p
- ret
== maxlen
);
1045 struct game_params params
;
1046 int *tiles
; /* selected-ness only */
1048 int xsel
, ysel
, displaysel
;
1051 static game_ui
*new_ui(game_state
*state
)
1053 game_ui
*ui
= snew(game_ui
);
1055 ui
->params
= state
->params
; /* structure copy */
1056 ui
->tiles
= snewn(state
->n
, int);
1057 memset(ui
->tiles
, 0, state
->n
*sizeof(int));
1060 ui
->xsel
= ui
->ysel
= ui
->displaysel
= 0;
1065 static void free_ui(game_ui
*ui
)
1071 static char *encode_ui(game_ui
*ui
)
1076 static void decode_ui(game_ui
*ui
, char *encoding
)
1080 static void sel_clear(game_ui
*ui
, game_state
*state
)
1084 for (i
= 0; i
< state
->n
; i
++)
1085 ui
->tiles
[i
] &= ~TILE_SELECTED
;
1090 static void game_changed_state(game_ui
*ui
, game_state
*oldstate
,
1091 game_state
*newstate
)
1093 sel_clear(ui
, newstate
);
1096 * If the game state has just changed into an unplayable one
1097 * (either completed or impossible), we vanish the keyboard-
1100 if (newstate
->complete
|| newstate
->impossible
)
1104 static char *sel_movedesc(game_ui
*ui
, game_state
*state
)
1107 char *ret
, *sep
, buf
[80];
1108 int retlen
, retsize
;
1111 ret
= snewn(retsize
, char);
1113 ret
[retlen
++] = 'M';
1116 for (i
= 0; i
< state
->n
; i
++) {
1117 if (ui
->tiles
[i
] & TILE_SELECTED
) {
1118 sprintf(buf
, "%s%d", sep
, i
);
1120 if (retlen
+ strlen(buf
) >= retsize
) {
1121 retsize
= retlen
+ strlen(buf
) + 256;
1122 ret
= sresize(ret
, retsize
, char);
1124 strcpy(ret
+ retlen
, buf
);
1125 retlen
+= strlen(buf
);
1127 ui
->tiles
[i
] &= ~TILE_SELECTED
;
1132 assert(retlen
< retsize
);
1133 ret
[retlen
++] = '\0';
1134 return sresize(ret
, retlen
, char);
1137 static void sel_expand(game_ui
*ui
, game_state
*state
, int tx
, int ty
)
1139 int ns
= 1, nadded
, x
, y
, c
;
1141 TILE(ui
,tx
,ty
) |= TILE_SELECTED
;
1145 for (x
= 0; x
< state
->params
.w
; x
++) {
1146 for (y
= 0; y
< state
->params
.h
; y
++) {
1147 if (x
== tx
&& y
== ty
) continue;
1148 if (ISSEL(ui
,x
,y
)) continue;
1152 ISSEL(ui
,x
-1,y
) && COL(state
,x
-1,y
) == c
) {
1153 TILE(ui
,x
,y
) |= TILE_SELECTED
;
1158 if ((x
+1 < state
->params
.w
) &&
1159 ISSEL(ui
,x
+1,y
) && COL(state
,x
+1,y
) == c
) {
1160 TILE(ui
,x
,y
) |= TILE_SELECTED
;
1166 ISSEL(ui
,x
,y
-1) && COL(state
,x
,y
-1) == c
) {
1167 TILE(ui
,x
,y
) |= TILE_SELECTED
;
1172 if ((y
+1 < state
->params
.h
) &&
1173 ISSEL(ui
,x
,y
+1) && COL(state
,x
,y
+1) == c
) {
1174 TILE(ui
,x
,y
) |= TILE_SELECTED
;
1181 } while (nadded
> 0);
1186 sel_clear(ui
, state
);
1190 static int sg_emptycol(game_state
*ret
, int x
)
1193 for (y
= 0; y
< ret
->params
.h
; y
++) {
1194 if (COL(ret
,x
,y
)) return 0;
1200 static void sg_snuggle(game_state
*ret
)
1204 /* make all unsupported tiles fall down. */
1207 for (x
= 0; x
< ret
->params
.w
; x
++) {
1208 for (y
= ret
->params
.h
-1; y
> 0; y
--) {
1209 if (COL(ret
,x
,y
) != 0) continue;
1210 if (COL(ret
,x
,y
-1) != 0) {
1211 SWAPTILE(ret
,x
,y
,x
,y
-1);
1218 /* shuffle all columns as far left as they can go. */
1221 for (x
= 0; x
< ret
->params
.w
-1; x
++) {
1222 if (sg_emptycol(ret
,x
) && !sg_emptycol(ret
,x
+1)) {
1224 for (y
= 0; y
< ret
->params
.h
; y
++) {
1225 SWAPTILE(ret
,x
,y
,x
+1,y
);
1232 static void sg_check(game_state
*ret
)
1234 int x
,y
, complete
= 1, impossible
= 1;
1236 for (x
= 0; x
< ret
->params
.w
; x
++) {
1237 for (y
= 0; y
< ret
->params
.h
; y
++) {
1238 if (COL(ret
,x
,y
) == 0)
1241 if (x
+1 < ret
->params
.w
) {
1242 if (COL(ret
,x
,y
) == COL(ret
,x
+1,y
))
1245 if (y
+1 < ret
->params
.h
) {
1246 if (COL(ret
,x
,y
) == COL(ret
,x
,y
+1))
1251 ret
->complete
= complete
;
1252 ret
->impossible
= impossible
;
1255 struct game_drawstate
{
1256 int started
, bgcolour
;
1257 int tileinner
, tilegap
;
1258 int *tiles
; /* contains colour and SELECTED. */
1261 static char *interpret_move(game_state
*state
, game_ui
*ui
, game_drawstate
*ds
,
1262 int x
, int y
, int button
)
1269 if (button
== RIGHT_BUTTON
|| button
== LEFT_BUTTON
) {
1270 tx
= FROMCOORD(x
); ty
= FROMCOORD(y
);
1271 } else if (button
== CURSOR_UP
|| button
== CURSOR_DOWN
||
1272 button
== CURSOR_LEFT
|| button
== CURSOR_RIGHT
) {
1275 dx
= (button
== CURSOR_LEFT
) ?
-1 : ((button
== CURSOR_RIGHT
) ?
+1 : 0);
1276 dy
= (button
== CURSOR_DOWN
) ?
+1 : ((button
== CURSOR_UP
) ?
-1 : 0);
1277 ui
->xsel
= (ui
->xsel
+ state
->params
.w
+ dx
) % state
->params
.w
;
1278 ui
->ysel
= (ui
->ysel
+ state
->params
.h
+ dy
) % state
->params
.h
;
1280 } else if (button
== CURSOR_SELECT
|| button
== ' ' || button
== '\r' ||
1288 if (tx
< 0 || tx
>= state
->params
.w
|| ty
< 0 || ty
>= state
->params
.h
)
1290 if (COL(state
, tx
, ty
) == 0) return NULL
;
1292 if (ISSEL(ui
,tx
,ty
)) {
1293 if (button
== RIGHT_BUTTON
)
1294 sel_clear(ui
, state
);
1296 ret
= sel_movedesc(ui
, state
);
1298 sel_clear(ui
, state
); /* might be no-op */
1299 sel_expand(ui
, state
, tx
, ty
);
1305 static game_state
*execute_move(game_state
*from
, char *move
)
1310 if (move
[0] == 'M') {
1311 ret
= dup_game(from
);
1318 if (i
< 0 || i
>= ret
->n
) {
1325 while (*move
&& isdigit((unsigned char)*move
)) move
++;
1326 if (*move
== ',') move
++;
1329 ret
->score
+= npoints(&ret
->params
, n
);
1331 sg_snuggle(ret
); /* shifts blanks down and to the left */
1332 sg_check(ret
); /* checks for completeness or impossibility */
1336 return NULL
; /* couldn't parse move string */
1339 /* ----------------------------------------------------------------------
1343 static void game_set_size(game_drawstate
*ds
, game_params
*params
,
1347 ds
->tileinner
= tilesize
- ds
->tilegap
;
1350 static void game_compute_size(game_params
*params
, int tilesize
,
1353 /* Ick: fake up tile size variables for macro expansion purposes */
1354 game_drawstate ads
, *ds
= &ads
;
1355 game_set_size(ds
, params
, tilesize
);
1357 *x
= TILE_SIZE
* params
->w
+ 2 * BORDER
- TILE_GAP
;
1358 *y
= TILE_SIZE
* params
->h
+ 2 * BORDER
- TILE_GAP
;
1361 static float *game_colours(frontend
*fe
, game_state
*state
, int *ncolours
)
1363 float *ret
= snewn(3 * NCOLOURS
, float);
1365 frontend_default_colour(fe
, &ret
[COL_BACKGROUND
* 3]);
1367 ret
[COL_1
* 3 + 0] = 0.0F
;
1368 ret
[COL_1
* 3 + 1] = 0.0F
;
1369 ret
[COL_1
* 3 + 2] = 1.0F
;
1371 ret
[COL_2
* 3 + 0] = 0.0F
;
1372 ret
[COL_2
* 3 + 1] = 0.5F
;
1373 ret
[COL_2
* 3 + 2] = 0.0F
;
1375 ret
[COL_3
* 3 + 0] = 1.0F
;
1376 ret
[COL_3
* 3 + 1] = 0.0F
;
1377 ret
[COL_3
* 3 + 2] = 0.0F
;
1379 ret
[COL_4
* 3 + 0] = 1.0F
;
1380 ret
[COL_4
* 3 + 1] = 1.0F
;
1381 ret
[COL_4
* 3 + 2] = 0.0F
;
1383 ret
[COL_5
* 3 + 0] = 1.0F
;
1384 ret
[COL_5
* 3 + 1] = 0.0F
;
1385 ret
[COL_5
* 3 + 2] = 1.0F
;
1387 ret
[COL_6
* 3 + 0] = 0.0F
;
1388 ret
[COL_6
* 3 + 1] = 1.0F
;
1389 ret
[COL_6
* 3 + 2] = 1.0F
;
1391 ret
[COL_7
* 3 + 0] = 0.5F
;
1392 ret
[COL_7
* 3 + 1] = 0.5F
;
1393 ret
[COL_7
* 3 + 2] = 1.0F
;
1395 ret
[COL_8
* 3 + 0] = 0.5F
;
1396 ret
[COL_8
* 3 + 1] = 1.0F
;
1397 ret
[COL_8
* 3 + 2] = 0.5F
;
1399 ret
[COL_9
* 3 + 0] = 1.0F
;
1400 ret
[COL_9
* 3 + 1] = 0.5F
;
1401 ret
[COL_9
* 3 + 2] = 0.5F
;
1403 ret
[COL_IMPOSSIBLE
* 3 + 0] = 0.0F
;
1404 ret
[COL_IMPOSSIBLE
* 3 + 1] = 0.0F
;
1405 ret
[COL_IMPOSSIBLE
* 3 + 2] = 0.0F
;
1407 ret
[COL_SEL
* 3 + 0] = 1.0F
;
1408 ret
[COL_SEL
* 3 + 1] = 1.0F
;
1409 ret
[COL_SEL
* 3 + 2] = 1.0F
;
1411 ret
[COL_HIGHLIGHT
* 3 + 0] = 1.0F
;
1412 ret
[COL_HIGHLIGHT
* 3 + 1] = 1.0F
;
1413 ret
[COL_HIGHLIGHT
* 3 + 2] = 1.0F
;
1415 ret
[COL_LOWLIGHT
* 3 + 0] = ret
[COL_BACKGROUND
* 3 + 0] * 2.0 / 3.0;
1416 ret
[COL_LOWLIGHT
* 3 + 1] = ret
[COL_BACKGROUND
* 3 + 1] * 2.0 / 3.0;
1417 ret
[COL_LOWLIGHT
* 3 + 2] = ret
[COL_BACKGROUND
* 3 + 2] * 2.0 / 3.0;
1419 *ncolours
= NCOLOURS
;
1423 static game_drawstate
*game_new_drawstate(game_state
*state
)
1425 struct game_drawstate
*ds
= snew(struct game_drawstate
);
1429 ds
->tileinner
= ds
->tilegap
= 0; /* not decided yet */
1430 ds
->tiles
= snewn(state
->n
, int);
1431 for (i
= 0; i
< state
->n
; i
++)
1437 static void game_free_drawstate(game_drawstate
*ds
)
1443 /* Drawing routing for the tile at (x,y) is responsible for drawing
1444 * itself and the gaps to its right and below. If we're the same colour
1445 * as the tile to our right, then we fill in the gap; ditto below, and if
1446 * both then we fill the teeny tiny square in the corner as well.
1449 static void tile_redraw(frontend
*fe
, game_drawstate
*ds
,
1450 int x
, int y
, int dright
, int dbelow
,
1451 int tile
, int bgcolour
)
1453 int outer
= bgcolour
, inner
= outer
, col
= tile
& TILE_COLMASK
;
1456 if (tile
& TILE_IMPOSSIBLE
) {
1458 inner
= COL_IMPOSSIBLE
;
1459 } else if (tile
& TILE_SELECTED
) {
1463 outer
= inner
= col
;
1466 draw_rect(fe
, COORD(x
), COORD(y
), TILE_INNER
, TILE_INNER
, outer
);
1467 draw_rect(fe
, COORD(x
)+TILE_INNER
/4, COORD(y
)+TILE_INNER
/4,
1468 TILE_INNER
/2, TILE_INNER
/2, inner
);
1471 draw_rect(fe
, COORD(x
)+TILE_INNER
, COORD(y
), TILE_GAP
, TILE_INNER
,
1472 (tile
& TILE_JOINRIGHT
) ? outer
: bgcolour
);
1474 draw_rect(fe
, COORD(x
), COORD(y
)+TILE_INNER
, TILE_INNER
, TILE_GAP
,
1475 (tile
& TILE_JOINDOWN
) ? outer
: bgcolour
);
1476 if (dright
&& dbelow
)
1477 draw_rect(fe
, COORD(x
)+TILE_INNER
, COORD(y
)+TILE_INNER
, TILE_GAP
, TILE_GAP
,
1478 (tile
& TILE_JOINDIAG
) ? outer
: bgcolour
);
1480 if (tile
& TILE_HASSEL
) {
1481 int sx
= COORD(x
)+2, sy
= COORD(y
)+2, ssz
= TILE_INNER
-5;
1482 int scol
= (outer
== COL_SEL
) ? COL_LOWLIGHT
: COL_HIGHLIGHT
;
1483 draw_line(fe
, sx
, sy
, sx
+ssz
, sy
, scol
);
1484 draw_line(fe
, sx
+ssz
, sy
, sx
+ssz
, sy
+ssz
, scol
);
1485 draw_line(fe
, sx
+ssz
, sy
+ssz
, sx
, sy
+ssz
, scol
);
1486 draw_line(fe
, sx
, sy
+ssz
, sx
, sy
, scol
);
1489 draw_update(fe
, COORD(x
), COORD(y
), TILE_SIZE
, TILE_SIZE
);
1492 static void game_redraw(frontend
*fe
, game_drawstate
*ds
, game_state
*oldstate
,
1493 game_state
*state
, int dir
, game_ui
*ui
,
1494 float animtime
, float flashtime
)
1498 /* This was entirely cloned from fifteen.c; it should probably be
1499 * moved into some generic 'draw-recessed-rectangle' utility fn. */
1504 TILE_SIZE
* state
->params
.w
+ 2 * BORDER
,
1505 TILE_SIZE
* state
->params
.h
+ 2 * BORDER
, COL_BACKGROUND
);
1506 draw_update(fe
, 0, 0,
1507 TILE_SIZE
* state
->params
.w
+ 2 * BORDER
,
1508 TILE_SIZE
* state
->params
.h
+ 2 * BORDER
);
1511 * Recessed area containing the whole puzzle.
1513 coords
[0] = COORD(state
->params
.w
) + HIGHLIGHT_WIDTH
- 1 - TILE_GAP
;
1514 coords
[1] = COORD(state
->params
.h
) + HIGHLIGHT_WIDTH
- 1 - TILE_GAP
;
1515 coords
[2] = COORD(state
->params
.w
) + HIGHLIGHT_WIDTH
- 1 - TILE_GAP
;
1516 coords
[3] = COORD(0) - HIGHLIGHT_WIDTH
;
1517 coords
[4] = coords
[2] - TILE_SIZE
;
1518 coords
[5] = coords
[3] + TILE_SIZE
;
1519 coords
[8] = COORD(0) - HIGHLIGHT_WIDTH
;
1520 coords
[9] = COORD(state
->params
.h
) + HIGHLIGHT_WIDTH
- 1 - TILE_GAP
;
1521 coords
[6] = coords
[8] + TILE_SIZE
;
1522 coords
[7] = coords
[9] - TILE_SIZE
;
1523 draw_polygon(fe
, coords
, 5, COL_HIGHLIGHT
, COL_HIGHLIGHT
);
1525 coords
[1] = COORD(0) - HIGHLIGHT_WIDTH
;
1526 coords
[0] = COORD(0) - HIGHLIGHT_WIDTH
;
1527 draw_polygon(fe
, coords
, 5, COL_LOWLIGHT
, COL_LOWLIGHT
);
1532 if (flashtime
> 0.0) {
1533 int frame
= (int)(flashtime
/ FLASH_FRAME
);
1534 bgcolour
= (frame
% 2 ? COL_LOWLIGHT
: COL_HIGHLIGHT
);
1536 bgcolour
= COL_BACKGROUND
;
1538 for (x
= 0; x
< state
->params
.w
; x
++) {
1539 for (y
= 0; y
< state
->params
.h
; y
++) {
1540 int i
= (state
->params
.w
* y
) + x
;
1541 int col
= COL(state
,x
,y
), tile
= col
;
1542 int dright
= (x
+1 < state
->params
.w
);
1543 int dbelow
= (y
+1 < state
->params
.h
);
1545 tile
|= ISSEL(ui
,x
,y
);
1546 if (state
->impossible
)
1547 tile
|= TILE_IMPOSSIBLE
;
1548 if (dright
&& COL(state
,x
+1,y
) == col
)
1549 tile
|= TILE_JOINRIGHT
;
1550 if (dbelow
&& COL(state
,x
,y
+1) == col
)
1551 tile
|= TILE_JOINDOWN
;
1552 if ((tile
& TILE_JOINRIGHT
) && (tile
& TILE_JOINDOWN
) &&
1553 COL(state
,x
+1,y
+1) == col
)
1554 tile
|= TILE_JOINDIAG
;
1556 if (ui
->displaysel
&& ui
->xsel
== x
&& ui
->ysel
== y
)
1557 tile
|= TILE_HASSEL
;
1559 /* For now we're never expecting oldstate at all (because we have
1560 * no animation); when we do we might well want to be looking
1561 * at the tile colours from oldstate, not state. */
1562 if ((oldstate
&& COL(oldstate
,x
,y
) != col
) ||
1563 (flashtime
> 0.0) ||
1564 (ds
->bgcolour
!= bgcolour
) ||
1565 (tile
!= ds
->tiles
[i
])) {
1566 tile_redraw(fe
, ds
, x
, y
, dright
, dbelow
, tile
, bgcolour
);
1567 ds
->tiles
[i
] = tile
;
1571 ds
->bgcolour
= bgcolour
;
1574 char status
[255], score
[80];
1576 sprintf(score
, "Score: %d", state
->score
);
1578 if (state
->complete
)
1579 sprintf(status
, "COMPLETE! %s", score
);
1580 else if (state
->impossible
)
1581 sprintf(status
, "Cannot move! %s", score
);
1582 else if (ui
->nselected
)
1583 sprintf(status
, "%s Selected: %d (%d)",
1584 score
, ui
->nselected
, npoints(&state
->params
, ui
->nselected
));
1586 sprintf(status
, "%s", score
);
1587 status_bar(fe
, status
);
1591 static float game_anim_length(game_state
*oldstate
, game_state
*newstate
,
1592 int dir
, game_ui
*ui
)
1597 static float game_flash_length(game_state
*oldstate
, game_state
*newstate
,
1598 int dir
, game_ui
*ui
)
1600 if ((!oldstate
->complete
&& newstate
->complete
) ||
1601 (!oldstate
->impossible
&& newstate
->impossible
))
1602 return 2 * FLASH_FRAME
;
1607 static int game_wants_statusbar(void)
1612 static int game_timing_state(game_state
*state
, game_ui
*ui
)
1618 #define thegame samegame
1621 const struct game thegame
= {
1622 "Same Game", "games.samegame",
1629 TRUE
, game_configure
, custom_params
,
1637 TRUE
, game_text_format
,
1645 PREFERRED_TILE_SIZE
, game_compute_size
, game_set_size
,
1648 game_free_drawstate
,
1652 game_wants_statusbar
,
1653 FALSE
, game_timing_state
,
1654 0, /* mouse_priorities */