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 */
404 shuffle(list
, n
, sizeof(*list
), rs
);
406 #ifdef GENERATION_DIAGNOSTICS
407 printf("initial grid:\n");
410 for (y
= 0; y
< h
; y
++) {
411 for (x
= 0; x
< w
; x
++) {
412 if (grid
[y
*w
+x
] == 0)
415 printf("%d", grid
[y
*w
+x
]);
423 * Now go through the list one element at a time and
424 * actually attempt to insert something there.
427 int dirs
[4], ndirs
, dir
;
433 memcpy(grid2
, grid
, wh
* sizeof(int));
437 * Insert a column at position x.
439 for (i
= w
-1; i
> x
; i
--)
440 for (j
= 0; j
< h
; j
++)
441 grid2
[j
*w
+i
] = grid2
[j
*w
+(i
-1)];
443 * Clear the new column.
445 for (j
= 0; j
< h
; j
++)
448 * Decrement y so that our first square is actually
449 * inserted _in_ the grid rather than just below it.
455 * Insert a square within column x at position y.
457 for (i
= 0; i
+1 <= y
; i
++)
458 grid2
[i
*w
+x
] = grid2
[(i
+1)*w
+x
];
460 #ifdef GENERATION_DIAGNOSTICS
461 printf("trying at n=%d (%d,%d)\n", n
, x
, y
);
465 for (y
= 0; y
< h
; y
++) {
466 for (x
= 0; x
< w
; x
++) {
467 if (grid2
[y
*w
+x
] == 0)
469 else if (grid2
[y
*w
+x
] <= nc
)
470 printf("%d", grid2
[y
*w
+x
]);
480 * Pick our square colour so that it doesn't match any
484 int wrongcol
[4], nwrong
= 0;
487 * List the neighbouring colours.
490 wrongcol
[nwrong
++] = grid2
[y
*w
+(x
-1)];
492 wrongcol
[nwrong
++] = grid2
[y
*w
+(x
+1)];
494 wrongcol
[nwrong
++] = grid2
[(y
-1)*w
+x
];
496 wrongcol
[nwrong
++] = grid2
[(y
+1)*w
+x
];
499 * Eliminate duplicates. We can afford a shoddy
500 * algorithm here because the problem size is
503 for (i
= j
= 0 ;; i
++) {
504 int pos
= -1, min
= 0;
507 for (k
= i
; k
< nwrong
; k
++)
508 if (wrongcol
[k
] > min
&&
509 (pos
== -1 || wrongcol
[k
] < wrongcol
[pos
]))
512 int v
= wrongcol
[pos
];
513 wrongcol
[pos
] = wrongcol
[j
];
521 * If no colour will go here, stop trying.
527 * Otherwise, pick a colour from the remaining
530 c
= 1 + random_upto(rs
, nc
- nwrong
);
531 for (i
= 0; i
< nwrong
; i
++) {
532 if (c
>= wrongcol
[i
])
540 * Place the new square.
542 * Although I've _chosen_ the new region's colour
543 * (so that we can check adjacency), I'm going to
544 * actually place it as an invalid colour (tc)
545 * until I'm sure it's viable. This is so that I
546 * can conveniently check that I really have made a
547 * _valid_ inverse move later on.
549 #ifdef GENERATION_DIAGNOSTICS
550 printf("picked colour %d\n", c
);
555 * Now attempt to extend it in one of three ways: left,
560 grid2
[y
*w
+(x
-1)] != c
&&
562 (y
+1 >= h
|| grid2
[(y
+1)*w
+(x
-1)] != c
) &&
563 (y
+1 >= h
|| grid2
[(y
+1)*w
+(x
-1)] != 0) &&
564 (x
<= 1 || grid2
[y
*w
+(x
-2)] != c
))
565 dirs
[ndirs
++] = -1; /* left */
567 grid2
[y
*w
+(x
+1)] != c
&&
569 (y
+1 >= h
|| grid2
[(y
+1)*w
+(x
+1)] != c
) &&
570 (y
+1 >= h
|| grid2
[(y
+1)*w
+(x
+1)] != 0) &&
571 (x
+2 >= w
|| grid2
[y
*w
+(x
+2)] != c
))
572 dirs
[ndirs
++] = +1; /* right */
575 (x
<= 0 || grid2
[(y
-1)*w
+(x
-1)] != c
) &&
576 (x
+1 >= w
|| grid2
[(y
-1)*w
+(x
+1)] != c
)) {
578 * We add this possibility _twice_, so that the
579 * probability of placing a vertical domino is
580 * about the same as that of a horizontal. This
581 * should yield less bias in the generated
584 dirs
[ndirs
++] = 0; /* up */
585 dirs
[ndirs
++] = 0; /* up */
591 dir
= dirs
[random_upto(rs
, ndirs
)];
593 #ifdef GENERATION_DIAGNOSTICS
594 printf("picked dir %d\n", dir
);
598 * Insert a square within column (x+dir) at position y.
600 for (i
= 0; i
+1 <= y
; i
++)
601 grid2
[i
*w
+x
+dir
] = grid2
[(i
+1)*w
+x
+dir
];
602 grid2
[y
*w
+x
+dir
] = tc
;
605 * See if we've divided the remaining grid squares
606 * into sub-areas. If so, we need every sub-area to
607 * have an even area or we won't be able to
608 * complete generation.
610 * If the height is odd and not all columns are
611 * present, we can increase the area of a subarea
612 * by adding a new column in it, so in that
613 * situation we don't mind having as many odd
614 * subareas as there are spare columns.
616 * If the height is even, we can't fix it at all.
619 int nerrs
= 0, nfix
= 0;
620 k
= 0; /* current subarea size */
621 for (i
= 0; i
< w
; i
++) {
622 if (grid2
[(h
-1)*w
+i
] == 0) {
627 for (j
= 0; j
< h
&& grid2
[j
*w
+i
] == 0; j
++);
631 * End of previous subarea.
643 continue; /* try a different placement */
647 * We've made a move. Verify that it is a valid
648 * move and that if made it would indeed yield the
649 * previous grid state. The criteria are:
651 * (a) removing all the squares of colour tc (and
652 * shuffling the columns up etc) from grid2
654 * (b) no square of colour tc is adjacent to one
656 * (c) all the squares of colour tc form a single
657 * connected component
659 * We verify the latter property at the same time
660 * as checking that removing all the tc squares
661 * would yield the previous grid. Then we colour
662 * the tc squares in colour c by breadth-first
663 * search, which conveniently permits us to test
664 * that they're all connected.
669 int fillstart
= -1, ntc
= 0;
671 #ifdef GENERATION_DIAGNOSTICS
674 printf("testing move (new, old):\n");
675 for (y
= 0; y
< h
; y
++) {
676 for (x
= 0; x
< w
; x
++) {
677 if (grid2
[y
*w
+x
] == 0)
679 else if (grid2
[y
*w
+x
] <= nc
)
680 printf("%d", grid2
[y
*w
+x
]);
685 for (x
= 0; x
< w
; x
++) {
686 if (grid
[y
*w
+x
] == 0)
689 printf("%d", grid
[y
*w
+x
]);
696 for (x1
= x2
= 0; x2
< w
; x2
++) {
699 for (y1
= y2
= h
-1; y2
>= 0; y2
--) {
700 if (grid2
[y2
*w
+x2
] == tc
) {
704 if ((y2
+1 < h
&& grid2
[(y2
+1)*w
+x2
] == c
) ||
705 (y2
-1 >= 0 && grid2
[(y2
-1)*w
+x2
] == c
) ||
706 (x2
+1 < w
&& grid2
[y2
*w
+x2
+1] == c
) ||
707 (x2
-1 >= 0 && grid2
[y2
*w
+x2
-1] == c
)) {
708 #ifdef GENERATION_DIAGNOSTICS
709 printf("adjacency failure at %d,%d\n",
716 if (grid2
[y2
*w
+x2
] == 0)
719 if (grid2
[y2
*w
+x2
] != grid
[y1
*w
+x1
]) {
720 #ifdef GENERATION_DIAGNOSTICS
721 printf("matching failure at %d,%d vs %d,%d\n",
730 * If we've reached the top of the column
731 * in grid2, verify that we've also reached
732 * the top of the column in `grid'.
736 if (grid
[y1
*w
+x1
] != 0) {
737 #ifdef GENERATION_DIAGNOSTICS
738 printf("junk at column top (%d,%d)\n",
755 assert(!"This should never happen");
758 * If this game is compiled NDEBUG so that
759 * the assertion doesn't bring it to a
760 * crashing halt, the only thing we can do
761 * is to give up, loop round again, and
762 * hope to randomly avoid making whatever
763 * type of move just caused this failure.
769 * Now use bfs to fill in the tc section as
770 * colour c. We use `list' to store the set of
771 * squares we have to process.
774 assert(fillstart
>= 0);
775 list
[i
++] = fillstart
;
776 #ifdef OUTPUT_SOLUTION
783 #ifdef OUTPUT_SOLUTION
784 printf("%s%d", j ?
"," : "", k
);
788 assert(grid2
[k
] == tc
);
791 if (x
> 0 && grid2
[k
-1] == tc
)
793 if (x
+1 < w
&& grid2
[k
+1] == tc
)
795 if (y
> 0 && grid2
[k
-w
] == tc
)
797 if (y
+1 < h
&& grid2
[k
+w
] == tc
)
800 #ifdef OUTPUT_SOLUTION
805 * Check that we've filled the same number of
806 * tc squares as we originally found.
811 memcpy(grid
, grid2
, wh
* sizeof(int));
813 break; /* done it! */
816 #ifdef GENERATION_DIAGNOSTICS
820 for (y
= 0; y
< h
; y
++) {
821 for (x
= 0; x
< w
; x
++) {
822 if (grid
[y
*w
+x
] == 0)
825 printf("%d", grid
[y
*w
+x
]);
837 for (i
= 0; i
< wh
; i
++)
841 #if defined GENERATION_DIAGNOSTICS || defined SHOW_INCOMPLETE
844 printf("incomplete grid:\n");
845 for (y
= 0; y
< h
; y
++) {
846 for (x
= 0; x
< w
; x
++) {
847 if (grid
[y
*w
+x
] == 0)
850 printf("%d", grid
[y
*w
+x
]);
861 #if defined GENERATION_DIAGNOSTICS || defined COUNT_FAILURES
862 printf("%d failures\n", failures
);
864 #ifdef GENERATION_DIAGNOSTICS
867 printf("final grid:\n");
868 for (y
= 0; y
< h
; y
++) {
869 for (x
= 0; x
< w
; x
++) {
870 printf("%d", grid
[y
*w
+x
]);
882 * Not-guaranteed-soluble grid generator; kept as a legacy, and in
883 * case someone finds the slightly odd quality of the guaranteed-
884 * soluble grids to be aesthetically displeasing or finds its CPU
885 * utilisation to be excessive.
887 static void gen_grid_random(int w
, int h
, int nc
, int *grid
, random_state
*rs
)
892 for (i
= 0; i
< n
; i
++)
896 * Our sole concession to not gratuitously generating insoluble
897 * grids is to ensure we have at least two of every colour.
899 for (c
= 1; c
<= nc
; c
++) {
900 for (j
= 0; j
< 2; j
++) {
902 i
= (int)random_upto(rs
, n
);
903 } while (grid
[i
] != 0);
909 * Fill in the rest of the grid at random.
911 for (i
= 0; i
< n
; i
++) {
913 grid
[i
] = (int)random_upto(rs
, nc
)+1;
917 static char *new_game_desc(game_params
*params
, random_state
*rs
,
918 char **aux
, int interactive
)
921 int n
, i
, retlen
, *tiles
;
923 n
= params
->w
* params
->h
;
924 tiles
= snewn(n
, int);
927 gen_grid(params
->w
, params
->h
, params
->ncols
, tiles
, rs
);
929 gen_grid_random(params
->w
, params
->h
, params
->ncols
, tiles
, rs
);
933 for (i
= 0; i
< n
; i
++) {
937 k
= sprintf(buf
, "%d,", tiles
[i
]);
938 ret
= sresize(ret
, retlen
+ k
+ 1, char);
939 strcpy(ret
+ retlen
, buf
);
942 ret
[retlen
-1] = '\0'; /* delete last comma */
948 static char *validate_desc(game_params
*params
, char *desc
)
950 int area
= params
->w
* params
->h
, i
;
953 for (i
= 0; i
< area
; i
++) {
957 if (!isdigit((unsigned char)*p
))
958 return "Not enough numbers in string";
959 while (isdigit((unsigned char)*p
)) p
++;
961 if (i
< area
-1 && *p
!= ',')
962 return "Expected comma after number";
963 else if (i
== area
-1 && *p
)
964 return "Excess junk at end of string";
967 if (n
< 0 || n
> params
->ncols
)
968 return "Colour out of range";
970 if (*p
) p
++; /* eat comma */
975 static game_state
*new_game(midend_data
*me
, game_params
*params
, char *desc
)
977 game_state
*state
= snew(game_state
);
981 state
->params
= *params
; /* struct copy */
982 state
->n
= state
->params
.w
* state
->params
.h
;
983 state
->tiles
= snewn(state
->n
, int);
985 for (i
= 0; i
< state
->n
; i
++) {
987 state
->tiles
[i
] = atoi(p
);
988 while (*p
&& *p
!= ',')
990 if (*p
) p
++; /* eat comma */
992 state
->complete
= state
->impossible
= 0;
998 static game_state
*dup_game(game_state
*state
)
1000 game_state
*ret
= snew(game_state
);
1002 *ret
= *state
; /* structure copy, except... */
1004 ret
->tiles
= snewn(state
->n
, int);
1005 memcpy(ret
->tiles
, state
->tiles
, state
->n
* sizeof(int));
1010 static void free_game(game_state
*state
)
1012 sfree(state
->tiles
);
1016 static char *solve_game(game_state
*state
, game_state
*currstate
,
1017 char *aux
, char **error
)
1022 static char *game_text_format(game_state
*state
)
1027 maxlen
= state
->params
.h
* (state
->params
.w
+ 1);
1028 ret
= snewn(maxlen
+1, char);
1031 for (y
= 0; y
< state
->params
.h
; y
++) {
1032 for (x
= 0; x
< state
->params
.w
; x
++) {
1033 int t
= TILE(state
,x
,y
);
1034 if (t
<= 0) *p
++ = ' ';
1035 else if (t
< 10) *p
++ = '0'+t
;
1036 else *p
++ = 'a'+(t
-10);
1040 assert(p
- ret
== maxlen
);
1046 struct game_params params
;
1047 int *tiles
; /* selected-ness only */
1049 int xsel
, ysel
, displaysel
;
1052 static game_ui
*new_ui(game_state
*state
)
1054 game_ui
*ui
= snew(game_ui
);
1056 ui
->params
= state
->params
; /* structure copy */
1057 ui
->tiles
= snewn(state
->n
, int);
1058 memset(ui
->tiles
, 0, state
->n
*sizeof(int));
1061 ui
->xsel
= ui
->ysel
= ui
->displaysel
= 0;
1066 static void free_ui(game_ui
*ui
)
1072 static char *encode_ui(game_ui
*ui
)
1077 static void decode_ui(game_ui
*ui
, char *encoding
)
1081 static void sel_clear(game_ui
*ui
, game_state
*state
)
1085 for (i
= 0; i
< state
->n
; i
++)
1086 ui
->tiles
[i
] &= ~TILE_SELECTED
;
1091 static void game_changed_state(game_ui
*ui
, game_state
*oldstate
,
1092 game_state
*newstate
)
1094 sel_clear(ui
, newstate
);
1097 * If the game state has just changed into an unplayable one
1098 * (either completed or impossible), we vanish the keyboard-
1101 if (newstate
->complete
|| newstate
->impossible
)
1105 static char *sel_movedesc(game_ui
*ui
, game_state
*state
)
1108 char *ret
, *sep
, buf
[80];
1109 int retlen
, retsize
;
1112 ret
= snewn(retsize
, char);
1114 ret
[retlen
++] = 'M';
1117 for (i
= 0; i
< state
->n
; i
++) {
1118 if (ui
->tiles
[i
] & TILE_SELECTED
) {
1119 sprintf(buf
, "%s%d", sep
, i
);
1121 if (retlen
+ strlen(buf
) >= retsize
) {
1122 retsize
= retlen
+ strlen(buf
) + 256;
1123 ret
= sresize(ret
, retsize
, char);
1125 strcpy(ret
+ retlen
, buf
);
1126 retlen
+= strlen(buf
);
1128 ui
->tiles
[i
] &= ~TILE_SELECTED
;
1133 assert(retlen
< retsize
);
1134 ret
[retlen
++] = '\0';
1135 return sresize(ret
, retlen
, char);
1138 static void sel_expand(game_ui
*ui
, game_state
*state
, int tx
, int ty
)
1140 int ns
= 1, nadded
, x
, y
, c
;
1142 TILE(ui
,tx
,ty
) |= TILE_SELECTED
;
1146 for (x
= 0; x
< state
->params
.w
; x
++) {
1147 for (y
= 0; y
< state
->params
.h
; y
++) {
1148 if (x
== tx
&& y
== ty
) continue;
1149 if (ISSEL(ui
,x
,y
)) continue;
1153 ISSEL(ui
,x
-1,y
) && COL(state
,x
-1,y
) == c
) {
1154 TILE(ui
,x
,y
) |= TILE_SELECTED
;
1159 if ((x
+1 < state
->params
.w
) &&
1160 ISSEL(ui
,x
+1,y
) && COL(state
,x
+1,y
) == c
) {
1161 TILE(ui
,x
,y
) |= TILE_SELECTED
;
1167 ISSEL(ui
,x
,y
-1) && COL(state
,x
,y
-1) == c
) {
1168 TILE(ui
,x
,y
) |= TILE_SELECTED
;
1173 if ((y
+1 < state
->params
.h
) &&
1174 ISSEL(ui
,x
,y
+1) && COL(state
,x
,y
+1) == c
) {
1175 TILE(ui
,x
,y
) |= TILE_SELECTED
;
1182 } while (nadded
> 0);
1187 sel_clear(ui
, state
);
1191 static int sg_emptycol(game_state
*ret
, int x
)
1194 for (y
= 0; y
< ret
->params
.h
; y
++) {
1195 if (COL(ret
,x
,y
)) return 0;
1201 static void sg_snuggle(game_state
*ret
)
1205 /* make all unsupported tiles fall down. */
1208 for (x
= 0; x
< ret
->params
.w
; x
++) {
1209 for (y
= ret
->params
.h
-1; y
> 0; y
--) {
1210 if (COL(ret
,x
,y
) != 0) continue;
1211 if (COL(ret
,x
,y
-1) != 0) {
1212 SWAPTILE(ret
,x
,y
,x
,y
-1);
1219 /* shuffle all columns as far left as they can go. */
1222 for (x
= 0; x
< ret
->params
.w
-1; x
++) {
1223 if (sg_emptycol(ret
,x
) && !sg_emptycol(ret
,x
+1)) {
1225 for (y
= 0; y
< ret
->params
.h
; y
++) {
1226 SWAPTILE(ret
,x
,y
,x
+1,y
);
1233 static void sg_check(game_state
*ret
)
1235 int x
,y
, complete
= 1, impossible
= 1;
1237 for (x
= 0; x
< ret
->params
.w
; x
++) {
1238 for (y
= 0; y
< ret
->params
.h
; y
++) {
1239 if (COL(ret
,x
,y
) == 0)
1242 if (x
+1 < ret
->params
.w
) {
1243 if (COL(ret
,x
,y
) == COL(ret
,x
+1,y
))
1246 if (y
+1 < ret
->params
.h
) {
1247 if (COL(ret
,x
,y
) == COL(ret
,x
,y
+1))
1252 ret
->complete
= complete
;
1253 ret
->impossible
= impossible
;
1256 struct game_drawstate
{
1257 int started
, bgcolour
;
1258 int tileinner
, tilegap
;
1259 int *tiles
; /* contains colour and SELECTED. */
1262 static char *interpret_move(game_state
*state
, game_ui
*ui
, game_drawstate
*ds
,
1263 int x
, int y
, int button
)
1270 if (button
== RIGHT_BUTTON
|| button
== LEFT_BUTTON
) {
1271 tx
= FROMCOORD(x
); ty
= FROMCOORD(y
);
1272 } else if (button
== CURSOR_UP
|| button
== CURSOR_DOWN
||
1273 button
== CURSOR_LEFT
|| button
== CURSOR_RIGHT
) {
1276 dx
= (button
== CURSOR_LEFT
) ?
-1 : ((button
== CURSOR_RIGHT
) ?
+1 : 0);
1277 dy
= (button
== CURSOR_DOWN
) ?
+1 : ((button
== CURSOR_UP
) ?
-1 : 0);
1278 ui
->xsel
= (ui
->xsel
+ state
->params
.w
+ dx
) % state
->params
.w
;
1279 ui
->ysel
= (ui
->ysel
+ state
->params
.h
+ dy
) % state
->params
.h
;
1281 } else if (button
== CURSOR_SELECT
|| button
== ' ' || button
== '\r' ||
1289 if (tx
< 0 || tx
>= state
->params
.w
|| ty
< 0 || ty
>= state
->params
.h
)
1291 if (COL(state
, tx
, ty
) == 0) return NULL
;
1293 if (ISSEL(ui
,tx
,ty
)) {
1294 if (button
== RIGHT_BUTTON
)
1295 sel_clear(ui
, state
);
1297 ret
= sel_movedesc(ui
, state
);
1299 sel_clear(ui
, state
); /* might be no-op */
1300 sel_expand(ui
, state
, tx
, ty
);
1306 static game_state
*execute_move(game_state
*from
, char *move
)
1311 if (move
[0] == 'M') {
1312 ret
= dup_game(from
);
1319 if (i
< 0 || i
>= ret
->n
) {
1326 while (*move
&& isdigit((unsigned char)*move
)) move
++;
1327 if (*move
== ',') move
++;
1330 ret
->score
+= npoints(&ret
->params
, n
);
1332 sg_snuggle(ret
); /* shifts blanks down and to the left */
1333 sg_check(ret
); /* checks for completeness or impossibility */
1337 return NULL
; /* couldn't parse move string */
1340 /* ----------------------------------------------------------------------
1344 static void game_set_size(game_drawstate
*ds
, game_params
*params
,
1348 ds
->tileinner
= tilesize
- ds
->tilegap
;
1351 static void game_compute_size(game_params
*params
, int tilesize
,
1354 /* Ick: fake up tile size variables for macro expansion purposes */
1355 game_drawstate ads
, *ds
= &ads
;
1356 game_set_size(ds
, params
, tilesize
);
1358 *x
= TILE_SIZE
* params
->w
+ 2 * BORDER
- TILE_GAP
;
1359 *y
= TILE_SIZE
* params
->h
+ 2 * BORDER
- TILE_GAP
;
1362 static float *game_colours(frontend
*fe
, game_state
*state
, int *ncolours
)
1364 float *ret
= snewn(3 * NCOLOURS
, float);
1366 frontend_default_colour(fe
, &ret
[COL_BACKGROUND
* 3]);
1368 ret
[COL_1
* 3 + 0] = 0.0F
;
1369 ret
[COL_1
* 3 + 1] = 0.0F
;
1370 ret
[COL_1
* 3 + 2] = 1.0F
;
1372 ret
[COL_2
* 3 + 0] = 0.0F
;
1373 ret
[COL_2
* 3 + 1] = 0.5F
;
1374 ret
[COL_2
* 3 + 2] = 0.0F
;
1376 ret
[COL_3
* 3 + 0] = 1.0F
;
1377 ret
[COL_3
* 3 + 1] = 0.0F
;
1378 ret
[COL_3
* 3 + 2] = 0.0F
;
1380 ret
[COL_4
* 3 + 0] = 1.0F
;
1381 ret
[COL_4
* 3 + 1] = 1.0F
;
1382 ret
[COL_4
* 3 + 2] = 0.0F
;
1384 ret
[COL_5
* 3 + 0] = 1.0F
;
1385 ret
[COL_5
* 3 + 1] = 0.0F
;
1386 ret
[COL_5
* 3 + 2] = 1.0F
;
1388 ret
[COL_6
* 3 + 0] = 0.0F
;
1389 ret
[COL_6
* 3 + 1] = 1.0F
;
1390 ret
[COL_6
* 3 + 2] = 1.0F
;
1392 ret
[COL_7
* 3 + 0] = 0.5F
;
1393 ret
[COL_7
* 3 + 1] = 0.5F
;
1394 ret
[COL_7
* 3 + 2] = 1.0F
;
1396 ret
[COL_8
* 3 + 0] = 0.5F
;
1397 ret
[COL_8
* 3 + 1] = 1.0F
;
1398 ret
[COL_8
* 3 + 2] = 0.5F
;
1400 ret
[COL_9
* 3 + 0] = 1.0F
;
1401 ret
[COL_9
* 3 + 1] = 0.5F
;
1402 ret
[COL_9
* 3 + 2] = 0.5F
;
1404 ret
[COL_IMPOSSIBLE
* 3 + 0] = 0.0F
;
1405 ret
[COL_IMPOSSIBLE
* 3 + 1] = 0.0F
;
1406 ret
[COL_IMPOSSIBLE
* 3 + 2] = 0.0F
;
1408 ret
[COL_SEL
* 3 + 0] = 1.0F
;
1409 ret
[COL_SEL
* 3 + 1] = 1.0F
;
1410 ret
[COL_SEL
* 3 + 2] = 1.0F
;
1412 ret
[COL_HIGHLIGHT
* 3 + 0] = 1.0F
;
1413 ret
[COL_HIGHLIGHT
* 3 + 1] = 1.0F
;
1414 ret
[COL_HIGHLIGHT
* 3 + 2] = 1.0F
;
1416 ret
[COL_LOWLIGHT
* 3 + 0] = ret
[COL_BACKGROUND
* 3 + 0] * 2.0 / 3.0;
1417 ret
[COL_LOWLIGHT
* 3 + 1] = ret
[COL_BACKGROUND
* 3 + 1] * 2.0 / 3.0;
1418 ret
[COL_LOWLIGHT
* 3 + 2] = ret
[COL_BACKGROUND
* 3 + 2] * 2.0 / 3.0;
1420 *ncolours
= NCOLOURS
;
1424 static game_drawstate
*game_new_drawstate(game_state
*state
)
1426 struct game_drawstate
*ds
= snew(struct game_drawstate
);
1430 ds
->tileinner
= ds
->tilegap
= 0; /* not decided yet */
1431 ds
->tiles
= snewn(state
->n
, int);
1432 for (i
= 0; i
< state
->n
; i
++)
1438 static void game_free_drawstate(game_drawstate
*ds
)
1444 /* Drawing routing for the tile at (x,y) is responsible for drawing
1445 * itself and the gaps to its right and below. If we're the same colour
1446 * as the tile to our right, then we fill in the gap; ditto below, and if
1447 * both then we fill the teeny tiny square in the corner as well.
1450 static void tile_redraw(frontend
*fe
, game_drawstate
*ds
,
1451 int x
, int y
, int dright
, int dbelow
,
1452 int tile
, int bgcolour
)
1454 int outer
= bgcolour
, inner
= outer
, col
= tile
& TILE_COLMASK
;
1457 if (tile
& TILE_IMPOSSIBLE
) {
1459 inner
= COL_IMPOSSIBLE
;
1460 } else if (tile
& TILE_SELECTED
) {
1464 outer
= inner
= col
;
1467 draw_rect(fe
, COORD(x
), COORD(y
), TILE_INNER
, TILE_INNER
, outer
);
1468 draw_rect(fe
, COORD(x
)+TILE_INNER
/4, COORD(y
)+TILE_INNER
/4,
1469 TILE_INNER
/2, TILE_INNER
/2, inner
);
1472 draw_rect(fe
, COORD(x
)+TILE_INNER
, COORD(y
), TILE_GAP
, TILE_INNER
,
1473 (tile
& TILE_JOINRIGHT
) ? outer
: bgcolour
);
1475 draw_rect(fe
, COORD(x
), COORD(y
)+TILE_INNER
, TILE_INNER
, TILE_GAP
,
1476 (tile
& TILE_JOINDOWN
) ? outer
: bgcolour
);
1477 if (dright
&& dbelow
)
1478 draw_rect(fe
, COORD(x
)+TILE_INNER
, COORD(y
)+TILE_INNER
, TILE_GAP
, TILE_GAP
,
1479 (tile
& TILE_JOINDIAG
) ? outer
: bgcolour
);
1481 if (tile
& TILE_HASSEL
) {
1482 int sx
= COORD(x
)+2, sy
= COORD(y
)+2, ssz
= TILE_INNER
-5;
1483 int scol
= (outer
== COL_SEL
) ? COL_LOWLIGHT
: COL_HIGHLIGHT
;
1484 draw_line(fe
, sx
, sy
, sx
+ssz
, sy
, scol
);
1485 draw_line(fe
, sx
+ssz
, sy
, sx
+ssz
, sy
+ssz
, scol
);
1486 draw_line(fe
, sx
+ssz
, sy
+ssz
, sx
, sy
+ssz
, scol
);
1487 draw_line(fe
, sx
, sy
+ssz
, sx
, sy
, scol
);
1490 draw_update(fe
, COORD(x
), COORD(y
), TILE_SIZE
, TILE_SIZE
);
1493 static void game_redraw(frontend
*fe
, game_drawstate
*ds
, game_state
*oldstate
,
1494 game_state
*state
, int dir
, game_ui
*ui
,
1495 float animtime
, float flashtime
)
1499 /* This was entirely cloned from fifteen.c; it should probably be
1500 * moved into some generic 'draw-recessed-rectangle' utility fn. */
1505 TILE_SIZE
* state
->params
.w
+ 2 * BORDER
,
1506 TILE_SIZE
* state
->params
.h
+ 2 * BORDER
, COL_BACKGROUND
);
1507 draw_update(fe
, 0, 0,
1508 TILE_SIZE
* state
->params
.w
+ 2 * BORDER
,
1509 TILE_SIZE
* state
->params
.h
+ 2 * BORDER
);
1512 * Recessed area containing the whole puzzle.
1514 coords
[0] = COORD(state
->params
.w
) + HIGHLIGHT_WIDTH
- 1 - TILE_GAP
;
1515 coords
[1] = COORD(state
->params
.h
) + HIGHLIGHT_WIDTH
- 1 - TILE_GAP
;
1516 coords
[2] = COORD(state
->params
.w
) + HIGHLIGHT_WIDTH
- 1 - TILE_GAP
;
1517 coords
[3] = COORD(0) - HIGHLIGHT_WIDTH
;
1518 coords
[4] = coords
[2] - TILE_SIZE
;
1519 coords
[5] = coords
[3] + TILE_SIZE
;
1520 coords
[8] = COORD(0) - HIGHLIGHT_WIDTH
;
1521 coords
[9] = COORD(state
->params
.h
) + HIGHLIGHT_WIDTH
- 1 - TILE_GAP
;
1522 coords
[6] = coords
[8] + TILE_SIZE
;
1523 coords
[7] = coords
[9] - TILE_SIZE
;
1524 draw_polygon(fe
, coords
, 5, COL_HIGHLIGHT
, COL_HIGHLIGHT
);
1526 coords
[1] = COORD(0) - HIGHLIGHT_WIDTH
;
1527 coords
[0] = COORD(0) - HIGHLIGHT_WIDTH
;
1528 draw_polygon(fe
, coords
, 5, COL_LOWLIGHT
, COL_LOWLIGHT
);
1533 if (flashtime
> 0.0) {
1534 int frame
= (int)(flashtime
/ FLASH_FRAME
);
1535 bgcolour
= (frame
% 2 ? COL_LOWLIGHT
: COL_HIGHLIGHT
);
1537 bgcolour
= COL_BACKGROUND
;
1539 for (x
= 0; x
< state
->params
.w
; x
++) {
1540 for (y
= 0; y
< state
->params
.h
; y
++) {
1541 int i
= (state
->params
.w
* y
) + x
;
1542 int col
= COL(state
,x
,y
), tile
= col
;
1543 int dright
= (x
+1 < state
->params
.w
);
1544 int dbelow
= (y
+1 < state
->params
.h
);
1546 tile
|= ISSEL(ui
,x
,y
);
1547 if (state
->impossible
)
1548 tile
|= TILE_IMPOSSIBLE
;
1549 if (dright
&& COL(state
,x
+1,y
) == col
)
1550 tile
|= TILE_JOINRIGHT
;
1551 if (dbelow
&& COL(state
,x
,y
+1) == col
)
1552 tile
|= TILE_JOINDOWN
;
1553 if ((tile
& TILE_JOINRIGHT
) && (tile
& TILE_JOINDOWN
) &&
1554 COL(state
,x
+1,y
+1) == col
)
1555 tile
|= TILE_JOINDIAG
;
1557 if (ui
->displaysel
&& ui
->xsel
== x
&& ui
->ysel
== y
)
1558 tile
|= TILE_HASSEL
;
1560 /* For now we're never expecting oldstate at all (because we have
1561 * no animation); when we do we might well want to be looking
1562 * at the tile colours from oldstate, not state. */
1563 if ((oldstate
&& COL(oldstate
,x
,y
) != col
) ||
1564 (flashtime
> 0.0) ||
1565 (ds
->bgcolour
!= bgcolour
) ||
1566 (tile
!= ds
->tiles
[i
])) {
1567 tile_redraw(fe
, ds
, x
, y
, dright
, dbelow
, tile
, bgcolour
);
1568 ds
->tiles
[i
] = tile
;
1572 ds
->bgcolour
= bgcolour
;
1575 char status
[255], score
[80];
1577 sprintf(score
, "Score: %d", state
->score
);
1579 if (state
->complete
)
1580 sprintf(status
, "COMPLETE! %s", score
);
1581 else if (state
->impossible
)
1582 sprintf(status
, "Cannot move! %s", score
);
1583 else if (ui
->nselected
)
1584 sprintf(status
, "%s Selected: %d (%d)",
1585 score
, ui
->nselected
, npoints(&state
->params
, ui
->nselected
));
1587 sprintf(status
, "%s", score
);
1588 status_bar(fe
, status
);
1592 static float game_anim_length(game_state
*oldstate
, game_state
*newstate
,
1593 int dir
, game_ui
*ui
)
1598 static float game_flash_length(game_state
*oldstate
, game_state
*newstate
,
1599 int dir
, game_ui
*ui
)
1601 if ((!oldstate
->complete
&& newstate
->complete
) ||
1602 (!oldstate
->impossible
&& newstate
->impossible
))
1603 return 2 * FLASH_FRAME
;
1608 static int game_wants_statusbar(void)
1613 static int game_timing_state(game_state
*state
, game_ui
*ui
)
1619 #define thegame samegame
1622 const struct game thegame
= {
1623 "Same Game", "games.samegame",
1630 TRUE
, game_configure
, custom_params
,
1638 TRUE
, game_text_format
,
1646 PREFERRED_TILE_SIZE
, game_compute_size
, game_set_size
,
1649 game_free_drawstate
,
1653 game_wants_statusbar
,
1654 FALSE
, game_timing_state
,
1655 0, /* mouse_priorities */