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(const 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 },
153 { 10, 10, 3, 2, TRUE },
155 { 15, 10, 3, 2, TRUE },
157 { 15, 10, 4, 2, TRUE },
158 { 20, 15, 4, 2, TRUE }
161 static int game_fetch_preset(int i, char **name, game_params **params)
166 if (i < 0 || i >= lenof(samegame_presets))
169 ret = snew(game_params);
170 *ret = samegame_presets[i];
172 sprintf(str, "%dx%d, %d colours", ret->w, ret->h, ret->ncols);
179 static void free_params(game_params *params)
184 static game_params *dup_params(const game_params *params)
186 game_params *ret = snew(game_params);
187 *ret = *params; /* structure copy */
191 static void decode_params(game_params *params, char const *string)
193 char const *p = string;
196 while (*p && isdigit((unsigned char)*p)) p++;
200 while (*p && isdigit((unsigned char)*p)) p++;
202 params->h = params->w;
206 params->ncols = atoi(p);
207 while (*p && isdigit((unsigned char)*p)) p++;
213 params->scoresub = atoi(p);
214 while (*p && isdigit((unsigned char)*p)) p++;
216 params->scoresub = 2;
220 params->soluble = FALSE;
224 static char *encode_params(const game_params *params, int full)
228 sprintf(ret, "%dx%dc%ds%d%s",
229 params->w, params->h, params->ncols, params->scoresub,
230 full && !params->soluble ? "r" : "");
234 static config_item *game_configure(const game_params *params)
239 ret = snewn(6, config_item);
241 ret[0].name = "Width";
242 ret[0].type = C_STRING;
243 sprintf(buf, "%d", params->w);
244 ret[0].u.string.sval = dupstr(buf);
246 ret[1].name = "Height";
247 ret[1].type = C_STRING;
248 sprintf(buf, "%d", params->h);
249 ret[1].u.string.sval = dupstr(buf);
251 ret[2].name = "No. of colours";
252 ret[2].type = C_STRING;
253 sprintf(buf, "%d", params->ncols);
254 ret[2].u.string.sval = dupstr(buf);
256 ret[3].name = "Scoring system";
257 ret[3].type = C_CHOICES;
258 ret[3].u.choices.choicenames = ":(n-1)^2:(n-2)^2";
259 ret[3].u.choices.selected = params->scoresub-1;
261 ret[4].name = "Ensure solubility";
262 ret[4].type = C_BOOLEAN;
263 ret[4].u.boolean.bval = params->soluble;
271 static game_params *custom_params(const config_item *cfg)
273 game_params *ret = snew(game_params);
275 ret->w = atoi(cfg[0].u.string.sval);
276 ret->h = atoi(cfg[1].u.string.sval);
277 ret->ncols = atoi(cfg[2].u.string.sval);
278 ret->scoresub = cfg[3].u.choices.selected + 1;
279 ret->soluble = cfg[4].u.boolean.bval;
284 static const char *validate_params(const game_params *params, int full)
286 if (params->w < 1 || params->h < 1)
287 return "Width and height must both be positive";
289 if (params->ncols > 9)
290 return "Maximum of 9 colours";
292 if (params->soluble) {
293 if (params->ncols < 3)
294 return "Number of colours must be at least three";
295 if (params->w * params->h <= 1)
296 return "Grid area must be greater than 1";
298 if (params->ncols < 2)
299 return "Number of colours must be at least three";
300 /* ...and we must make sure we can generate at least 2 squares
301 * of each colour so it's theoretically soluble. */
302 if ((params->w * params->h) < (params->ncols * 2))
303 return "Too many colours makes given grid size impossible";
306 if ((params->scoresub < 1) || (params->scoresub > 2))
307 return "Scoring system not recognised";
313 * Guaranteed-soluble grid generator.
315 static void gen_grid(int w, int h, int nc, int *grid, random_state *rs)
317 int wh = w*h, tc = nc+1;
318 int i, j, k, c, x, y, pos, n;
320 int ok, failures = 0;
323 * We'll use `list' to track the possible places to put our
324 * next insertion. There are up to h places to insert in each
325 * column: in a column of height n there are n+1 places because
326 * we can insert at the very bottom or the very top, but a
327 * column of height h can't have anything at all inserted in it
328 * so we have up to h in each column. Likewise, with n columns
329 * present there are n+1 places to fit a new one in between but
330 * we can't insert a column if there are already w; so there
331 * are a maximum of w new columns too. Total is wh + w.
333 list = snewn(wh + w, int);
334 grid2 = snewn(wh, int);
338 * Start with two or three squares - depending on parity of w*h
339 * - of a random colour.
341 for (i = 0; i < wh; i++)
344 c = 1 + random_upto(rs, nc);
346 for (i = 0; i < j; i++)
350 for (i = 0; i < j; i++)
355 * Now repeatedly insert a two-square blob in the grid, of
356 * whatever colour will go at the position we chose.
362 * Build up a list of insertion points. Each point is
363 * encoded as y*w+x; insertion points between columns are
367 if (grid[wh - 1] == 0) {
369 * The final column is empty, so we can insert new
372 for (i = 0; i < w; i++) {
374 if (grid[(h-1)*w + i] == 0)
380 * Now look for places to insert within columns.
382 for (i = 0; i < w; i++) {
383 if (grid[(h-1)*w+i] == 0)
384 break; /* no more columns */
387 continue; /* this column is full */
389 for (j = h; j-- > 0 ;) {
391 if (grid[j*w+i] == 0)
392 break; /* this column is exhausted */
397 break; /* we're done */
399 #ifdef GENERATION_DIAGNOSTICS
400 printf("initial grid:\n");
403 for (y = 0; y < h; y++) {
404 for (x = 0; x < w; x++) {
405 if (grid[y*w+x] == 0)
408 printf("%d", grid[y*w+x]);
416 * Now go through the list one element at a time in
417 * random order, and actually attempt to insert
421 int dirs[4], ndirs, dir;
423 i = random_upto(rs, n+1);
430 memcpy(grid2, grid, wh * sizeof(int));
434 * Insert a column at position x.
436 for (i = w-1; i > x; i--)
437 for (j = 0; j < h; j++)
438 grid2[j*w+i] = grid2[j*w+(i-1)];
440 * Clear the new column.
442 for (j = 0; j < h; j++)
445 * Decrement y so that our first square is actually
446 * inserted _in_ the grid rather than just below it.
452 * Insert a square within column x at position y.
454 for (i = 0; i+1 <= y; i++)
455 grid2[i*w+x] = grid2[(i+1)*w+x];
457 #ifdef GENERATION_DIAGNOSTICS
458 printf("trying at n=%d (%d,%d)\n", n, x, y);
462 for (y = 0; y < h; y++) {
463 for (x = 0; x < w; x++) {
464 if (grid2[y*w+x] == 0)
466 else if (grid2[y*w+x] <= nc)
467 printf("%d", grid2[y*w+x]);
477 * Pick our square colour so that it doesn't match any
481 int wrongcol[4], nwrong = 0;
484 * List the neighbouring colours.
487 wrongcol[nwrong++] = grid2[y*w+(x-1)];
489 wrongcol[nwrong++] = grid2[y*w+(x+1)];
491 wrongcol[nwrong++] = grid2[(y-1)*w+x];
493 wrongcol[nwrong++] = grid2[(y+1)*w+x];
496 * Eliminate duplicates. We can afford a shoddy
497 * algorithm here because the problem size is
500 for (i = j = 0 ;; i++) {
501 int pos = -1, min = 0;
504 for (k = i; k < nwrong; k++)
505 if (wrongcol[k] > min &&
506 (pos == -1 || wrongcol[k] < wrongcol[pos]))
509 int v = wrongcol[pos];
510 wrongcol[pos] = wrongcol[j];
518 * If no colour will go here, stop trying.
524 * Otherwise, pick a colour from the remaining
527 c = 1 + random_upto(rs, nc - nwrong);
528 for (i = 0; i < nwrong; i++) {
529 if (c >= wrongcol[i])
537 * Place the new square.
539 * Although I've _chosen_ the new region's colour
540 * (so that we can check adjacency), I'm going to
541 * actually place it as an invalid colour (tc)
542 * until I'm sure it's viable. This is so that I
543 * can conveniently check that I really have made a
544 * _valid_ inverse move later on.
546 #ifdef GENERATION_DIAGNOSTICS
547 printf("picked colour %d\n", c);
552 * Now attempt to extend it in one of three ways: left,
557 grid2[y*w+(x-1)] != c &&
559 (y+1 >= h || grid2[(y+1)*w+(x-1)] != c) &&
560 (y+1 >= h || grid2[(y+1)*w+(x-1)] != 0) &&
561 (x <= 1 || grid2[y*w+(x-2)] != c))
562 dirs[ndirs++] = -1; /* left */
564 grid2[y*w+(x+1)] != c &&
566 (y+1 >= h || grid2[(y+1)*w+(x+1)] != c) &&
567 (y+1 >= h || grid2[(y+1)*w+(x+1)] != 0) &&
568 (x+2 >= w || grid2[y*w+(x+2)] != c))
569 dirs[ndirs++] = +1; /* right */
572 (x <= 0 || grid2[(y-1)*w+(x-1)] != c) &&
573 (x+1 >= w || grid2[(y-1)*w+(x+1)] != c)) {
575 * We add this possibility _twice_, so that the
576 * probability of placing a vertical domino is
577 * about the same as that of a horizontal. This
578 * should yield less bias in the generated
581 dirs[ndirs++] = 0; /* up */
582 dirs[ndirs++] = 0; /* up */
588 dir = dirs[random_upto(rs, ndirs)];
590 #ifdef GENERATION_DIAGNOSTICS
591 printf("picked dir %d\n", dir);
595 * Insert a square within column (x+dir) at position y.
597 for (i = 0; i+1 <= y; i++)
598 grid2[i*w+x+dir] = grid2[(i+1)*w+x+dir];
599 grid2[y*w+x+dir] = tc;
602 * See if we've divided the remaining grid squares
603 * into sub-areas. If so, we need every sub-area to
604 * have an even area or we won't be able to
605 * complete generation.
607 * If the height is odd and not all columns are
608 * present, we can increase the area of a subarea
609 * by adding a new column in it, so in that
610 * situation we don't mind having as many odd
611 * subareas as there are spare columns.
613 * If the height is even, we can't fix it at all.
616 int nerrs = 0, nfix = 0;
617 k = 0; /* current subarea size */
618 for (i = 0; i < w; i++) {
619 if (grid2[(h-1)*w+i] == 0) {
624 for (j = 0; j < h && grid2[j*w+i] == 0; j++);
628 * End of previous subarea.
640 continue; /* try a different placement */
644 * We've made a move. Verify that it is a valid
645 * move and that if made it would indeed yield the
646 * previous grid state. The criteria are:
648 * (a) removing all the squares of colour tc (and
649 * shuffling the columns up etc) from grid2
651 * (b) no square of colour tc is adjacent to one
653 * (c) all the squares of colour tc form a single
654 * connected component
656 * We verify the latter property at the same time
657 * as checking that removing all the tc squares
658 * would yield the previous grid. Then we colour
659 * the tc squares in colour c by breadth-first
660 * search, which conveniently permits us to test
661 * that they're all connected.
666 int fillstart = -1, ntc = 0;
668 #ifdef GENERATION_DIAGNOSTICS
671 printf("testing move (new, old):\n");
672 for (y = 0; y < h; y++) {
673 for (x = 0; x < w; x++) {
674 if (grid2[y*w+x] == 0)
676 else if (grid2[y*w+x] <= nc)
677 printf("%d", grid2[y*w+x]);
682 for (x = 0; x < w; x++) {
683 if (grid[y*w+x] == 0)
686 printf("%d", grid[y*w+x]);
693 for (x1 = x2 = 0; x2 < w; x2++) {
696 for (y1 = y2 = h-1; y2 >= 0; y2--) {
697 if (grid2[y2*w+x2] == tc) {
701 if ((y2+1 < h && grid2[(y2+1)*w+x2] == c) ||
702 (y2-1 >= 0 && grid2[(y2-1)*w+x2] == c) ||
703 (x2+1 < w && grid2[y2*w+x2+1] == c) ||
704 (x2-1 >= 0 && grid2[y2*w+x2-1] == c)) {
705 #ifdef GENERATION_DIAGNOSTICS
706 printf("adjacency failure at %d,%d\n",
713 if (grid2[y2*w+x2] == 0)
716 if (grid2[y2*w+x2] != grid[y1*w+x1]) {
717 #ifdef GENERATION_DIAGNOSTICS
718 printf("matching failure at %d,%d vs %d,%d\n",
727 * If we've reached the top of the column
728 * in grid2, verify that we've also reached
729 * the top of the column in `grid'.
733 if (grid[y1*w+x1] != 0) {
734 #ifdef GENERATION_DIAGNOSTICS
735 printf("junk at column top (%d,%d)\n",
752 assert(!"This should never happen");
755 * If this game is compiled NDEBUG so that
756 * the assertion doesn't bring it to a
757 * crashing halt, the only thing we can do
758 * is to give up, loop round again, and
759 * hope to randomly avoid making whatever
760 * type of move just caused this failure.
766 * Now use bfs to fill in the tc section as
767 * colour c. We use `list' to store the set of
768 * squares we have to process.
771 assert(fillstart >= 0);
772 list[i++] = fillstart;
773 #ifdef OUTPUT_SOLUTION
780 #ifdef OUTPUT_SOLUTION
781 printf("%s%d", j ? "," : "", k);
785 assert(grid2[k] == tc);
788 if (x > 0 && grid2[k-1] == tc)
790 if (x+1 < w && grid2[k+1] == tc)
792 if (y > 0 && grid2[k-w] == tc)
794 if (y+1 < h && grid2[k+w] == tc)
797 #ifdef OUTPUT_SOLUTION
802 * Check that we've filled the same number of
803 * tc squares as we originally found.
808 memcpy(grid, grid2, wh * sizeof(int));
810 break; /* done it! */
813 #ifdef GENERATION_DIAGNOSTICS
817 for (y = 0; y < h; y++) {
818 for (x = 0; x < w; x++) {
819 if (grid[y*w+x] == 0)
822 printf("%d", grid[y*w+x]);
834 for (i = 0; i < wh; i++)
838 #if defined GENERATION_DIAGNOSTICS || defined SHOW_INCOMPLETE
841 printf("incomplete grid:\n");
842 for (y = 0; y < h; y++) {
843 for (x = 0; x < w; x++) {
844 if (grid[y*w+x] == 0)
847 printf("%d", grid[y*w+x]);
858 #if defined GENERATION_DIAGNOSTICS || defined COUNT_FAILURES
859 printf("%d failures\n", failures);
861 #ifdef GENERATION_DIAGNOSTICS
864 printf("final grid:\n");
865 for (y = 0; y < h; y++) {
866 for (x = 0; x < w; x++) {
867 printf("%d", grid[y*w+x]);
879 * Not-guaranteed-soluble grid generator; kept as a legacy, and in
880 * case someone finds the slightly odd quality of the guaranteed-
881 * soluble grids to be aesthetically displeasing or finds its CPU
882 * utilisation to be excessive.
884 static void gen_grid_random(int w, int h, int nc, int *grid, random_state *rs)
889 for (i = 0; i < n; i++)
893 * Our sole concession to not gratuitously generating insoluble
894 * grids is to ensure we have at least two of every colour.
896 for (c = 1; c <= nc; c++) {
897 for (j = 0; j < 2; j++) {
899 i = (int)random_upto(rs, n);
900 } while (grid[i] != 0);
906 * Fill in the rest of the grid at random.
908 for (i = 0; i < n; i++) {
910 grid[i] = (int)random_upto(rs, nc)+1;
914 static char *new_game_desc(const game_params *params, random_state *rs,
915 char **aux, int interactive)
918 int n, i, retlen, *tiles;
920 n = params->w * params->h;
921 tiles = snewn(n, int);
924 gen_grid(params->w, params->h, params->ncols, tiles, rs);
926 gen_grid_random(params->w, params->h, params->ncols, tiles, rs);
930 for (i = 0; i < n; i++) {
934 k = sprintf(buf, "%d,", tiles[i]);
935 ret = sresize(ret, retlen + k + 1, char);
936 strcpy(ret + retlen, buf);
939 ret[retlen-1] = '\0'; /* delete last comma */
945 static const char *validate_desc(const game_params *params, const char *desc)
947 int area = params->w * params->h, i;
948 const char *p = desc;
950 for (i = 0; i < area; i++) {
954 if (!isdigit((unsigned char)*p))
955 return "Not enough numbers in string";
956 while (isdigit((unsigned char)*p)) p++;
958 if (i < area-1 && *p != ',')
959 return "Expected comma after number";
960 else if (i == area-1 && *p)
961 return "Excess junk at end of string";
964 if (n < 0 || n > params->ncols)
965 return "Colour out of range";
967 if (*p) p++; /* eat comma */
972 static game_state *new_game(midend *me, const game_params *params,
975 game_state *state = snew(game_state);
976 const char *p = desc;
979 state->params = *params; /* struct copy */
980 state->n = state->params.w * state->params.h;
981 state->tiles = snewn(state->n, int);
983 for (i = 0; i < state->n; i++) {
985 state->tiles[i] = atoi(p);
986 while (*p && *p != ',')
988 if (*p) p++; /* eat comma */
990 state->complete = state->impossible = 0;
996 static game_state *dup_game(const game_state *state)
998 game_state *ret = snew(game_state);
1000 *ret = *state; /* structure copy, except... */
1002 ret->tiles = snewn(state->n, int);
1003 memcpy(ret->tiles, state->tiles, state->n * sizeof(int));
1008 static void free_game(game_state *state)
1010 sfree(state->tiles);
1014 static char *solve_game(const game_state *state, const game_state *currstate,
1015 const char *aux, const char **error)
1020 static int game_can_format_as_text_now(const game_params *params)
1025 static char *game_text_format(const game_state *state)
1030 maxlen = state->params.h * (state->params.w + 1);
1031 ret = snewn(maxlen+1, char);
1034 for (y = 0; y < state->params.h; y++) {
1035 for (x = 0; x < state->params.w; x++) {
1036 int t = TILE(state,x,y);
1037 if (t <= 0) *p++ = ' ';
1038 else if (t < 10) *p++ = '0'+t;
1039 else *p++ = 'a'+(t-10);
1043 assert(p - ret == maxlen);
1049 struct game_params params;
1050 int *tiles; /* selected-ness only */
1052 int xsel, ysel, displaysel;
1055 static game_ui *new_ui(const game_state *state)
1057 game_ui *ui = snew(game_ui);
1059 ui->params = state->params; /* structure copy */
1060 ui->tiles = snewn(state->n, int);
1061 memset(ui->tiles, 0, state->n*sizeof(int));
1064 ui->xsel = ui->ysel = ui->displaysel = 0;
1069 static void free_ui(game_ui *ui)
1075 static char *encode_ui(const game_ui *ui)
1080 static void decode_ui(game_ui *ui, const char *encoding)
1084 static void sel_clear(game_ui *ui, const game_state *state)
1088 for (i = 0; i < state->n; i++)
1089 ui->tiles[i] &= ~TILE_SELECTED;
1094 static void game_changed_state(game_ui *ui, const game_state *oldstate,
1095 const game_state *newstate)
1097 sel_clear(ui, newstate);
1100 * If the game state has just changed into an unplayable one
1101 * (either completed or impossible), we vanish the keyboard-
1104 if (newstate->complete || newstate->impossible)
1108 static char *sel_movedesc(game_ui *ui, const game_state *state)
1111 char *ret, *sep, buf[80];
1112 int retlen, retsize;
1115 ret = snewn(retsize, char);
1117 ret[retlen++] = 'M';
1120 for (i = 0; i < state->n; i++) {
1121 if (ui->tiles[i] & TILE_SELECTED) {
1122 sprintf(buf, "%s%d", sep, i);
1124 if (retlen + (int)strlen(buf) >= retsize) {
1125 retsize = retlen + strlen(buf) + 256;
1126 ret = sresize(ret, retsize, char);
1128 strcpy(ret + retlen, buf);
1129 retlen += strlen(buf);
1131 ui->tiles[i] &= ~TILE_SELECTED;
1136 assert(retlen < retsize);
1137 ret[retlen++] = '\0';
1138 return sresize(ret, retlen, char);
1141 static void sel_expand(game_ui *ui, const game_state *state, int tx, int ty)
1143 int ns = 1, nadded, x, y, c;
1145 TILE(ui,tx,ty) |= TILE_SELECTED;
1149 for (x = 0; x < state->params.w; x++) {
1150 for (y = 0; y < state->params.h; y++) {
1151 if (x == tx && y == ty) continue;
1152 if (ISSEL(ui,x,y)) continue;
1156 ISSEL(ui,x-1,y) && COL(state,x-1,y) == c) {
1157 TILE(ui,x,y) |= TILE_SELECTED;
1162 if ((x+1 < state->params.w) &&
1163 ISSEL(ui,x+1,y) && COL(state,x+1,y) == c) {
1164 TILE(ui,x,y) |= TILE_SELECTED;
1170 ISSEL(ui,x,y-1) && COL(state,x,y-1) == c) {
1171 TILE(ui,x,y) |= TILE_SELECTED;
1176 if ((y+1 < state->params.h) &&
1177 ISSEL(ui,x,y+1) && COL(state,x,y+1) == c) {
1178 TILE(ui,x,y) |= TILE_SELECTED;
1185 } while (nadded > 0);
1190 sel_clear(ui, state);
1194 static int sg_emptycol(game_state *ret, int x)
1197 for (y = 0; y < ret->params.h; y++) {
1198 if (COL(ret,x,y)) return 0;
1204 static void sg_snuggle(game_state *ret)
1208 /* make all unsupported tiles fall down. */
1211 for (x = 0; x < ret->params.w; x++) {
1212 for (y = ret->params.h-1; y > 0; y--) {
1213 if (COL(ret,x,y) != 0) continue;
1214 if (COL(ret,x,y-1) != 0) {
1215 SWAPTILE(ret,x,y,x,y-1);
1222 /* shuffle all columns as far left as they can go. */
1225 for (x = 0; x < ret->params.w-1; x++) {
1226 if (sg_emptycol(ret,x) && !sg_emptycol(ret,x+1)) {
1228 for (y = 0; y < ret->params.h; y++) {
1229 SWAPTILE(ret,x,y,x+1,y);
1236 static void sg_check(game_state *ret)
1238 int x,y, complete = 1, impossible = 1;
1240 for (x = 0; x < ret->params.w; x++) {
1241 for (y = 0; y < ret->params.h; y++) {
1242 if (COL(ret,x,y) == 0)
1245 if (x+1 < ret->params.w) {
1246 if (COL(ret,x,y) == COL(ret,x+1,y))
1249 if (y+1 < ret->params.h) {
1250 if (COL(ret,x,y) == COL(ret,x,y+1))
1255 ret->complete = complete;
1256 ret->impossible = impossible;
1259 struct game_drawstate {
1260 int started, bgcolour;
1261 int tileinner, tilegap;
1262 int *tiles; /* contains colour and SELECTED. */
1265 static char *interpret_move(const game_state *state, game_ui *ui,
1266 const game_drawstate *ds,
1267 int x, int y, int button)
1270 char *ret = UI_UPDATE;
1274 if (button == RIGHT_BUTTON || button == LEFT_BUTTON) {
1275 tx = FROMCOORD(x); ty= FROMCOORD(y);
1276 } else if (IS_CURSOR_MOVE(button)) {
1279 dx = (button == CURSOR_LEFT) ? -1 : ((button == CURSOR_RIGHT) ? +1 : 0);
1280 dy = (button == CURSOR_DOWN) ? +1 : ((button == CURSOR_UP) ? -1 : 0);
1281 ui->xsel = (ui->xsel + state->params.w + dx) % state->params.w;
1282 ui->ysel = (ui->ysel + state->params.h + dy) % state->params.h;
1284 } else if (IS_CURSOR_SELECT(button)) {
1291 if (tx < 0 || tx >= state->params.w || ty < 0 || ty >= state->params.h)
1293 if (COL(state, tx, ty) == 0) return NULL;
1295 if (ISSEL(ui,tx,ty)) {
1296 if (button == RIGHT_BUTTON || button == CURSOR_SELECT2)
1297 sel_clear(ui, state);
1299 ret = sel_movedesc(ui, state);
1301 sel_clear(ui, state); /* might be no-op */
1302 sel_expand(ui, state, tx, ty);
1308 static game_state *execute_move(const game_state *from, const char *move)
1313 if (move[0] == 'M') {
1314 ret = dup_game(from);
1321 if (i < 0 || i >= ret->n) {
1328 while (*move && isdigit((unsigned char)*move)) move++;
1329 if (*move == ',') move++;
1332 ret->score += npoints(&ret->params, n);
1334 sg_snuggle(ret); /* shifts blanks down and to the left */
1335 sg_check(ret); /* checks for completeness or impossibility */
1339 return NULL; /* couldn't parse move string */
1342 /* ----------------------------------------------------------------------
1346 static void game_set_size(drawing *dr, game_drawstate *ds,
1347 const game_params *params, int tilesize)
1350 ds->tileinner = tilesize - ds->tilegap;
1353 static void game_compute_size(const game_params *params, int tilesize,
1356 /* Ick: fake up tile size variables for macro expansion purposes */
1357 game_drawstate ads, *ds = &ads;
1358 game_set_size(NULL, ds, params, tilesize);
1360 *x = TILE_SIZE * params->w + 2 * BORDER - TILE_GAP;
1361 *y = TILE_SIZE * params->h + 2 * BORDER - TILE_GAP;
1364 static float *game_colours(frontend *fe, int *ncolours)
1366 float *ret = snewn(3 * NCOLOURS, float);
1368 frontend_default_colour(fe, &ret[COL_BACKGROUND * 3]);
1370 ret[COL_1 * 3 + 0] = 0.0F;
1371 ret[COL_1 * 3 + 1] = 0.0F;
1372 ret[COL_1 * 3 + 2] = 1.0F;
1374 ret[COL_2 * 3 + 0] = 0.0F;
1375 ret[COL_2 * 3 + 1] = 0.5F;
1376 ret[COL_2 * 3 + 2] = 0.0F;
1378 ret[COL_3 * 3 + 0] = 1.0F;
1379 ret[COL_3 * 3 + 1] = 0.0F;
1380 ret[COL_3 * 3 + 2] = 0.0F;
1382 ret[COL_4 * 3 + 0] = 1.0F;
1383 ret[COL_4 * 3 + 1] = 1.0F;
1384 ret[COL_4 * 3 + 2] = 0.0F;
1386 ret[COL_5 * 3 + 0] = 1.0F;
1387 ret[COL_5 * 3 + 1] = 0.0F;
1388 ret[COL_5 * 3 + 2] = 1.0F;
1390 ret[COL_6 * 3 + 0] = 0.0F;
1391 ret[COL_6 * 3 + 1] = 1.0F;
1392 ret[COL_6 * 3 + 2] = 1.0F;
1394 ret[COL_7 * 3 + 0] = 0.5F;
1395 ret[COL_7 * 3 + 1] = 0.5F;
1396 ret[COL_7 * 3 + 2] = 1.0F;
1398 ret[COL_8 * 3 + 0] = 0.5F;
1399 ret[COL_8 * 3 + 1] = 1.0F;
1400 ret[COL_8 * 3 + 2] = 0.5F;
1402 ret[COL_9 * 3 + 0] = 1.0F;
1403 ret[COL_9 * 3 + 1] = 0.5F;
1404 ret[COL_9 * 3 + 2] = 0.5F;
1406 ret[COL_IMPOSSIBLE * 3 + 0] = 0.0F;
1407 ret[COL_IMPOSSIBLE * 3 + 1] = 0.0F;
1408 ret[COL_IMPOSSIBLE * 3 + 2] = 0.0F;
1410 ret[COL_SEL * 3 + 0] = 1.0F;
1411 ret[COL_SEL * 3 + 1] = 1.0F;
1412 ret[COL_SEL * 3 + 2] = 1.0F;
1414 ret[COL_HIGHLIGHT * 3 + 0] = 1.0F;
1415 ret[COL_HIGHLIGHT * 3 + 1] = 1.0F;
1416 ret[COL_HIGHLIGHT * 3 + 2] = 1.0F;
1418 ret[COL_LOWLIGHT * 3 + 0] = ret[COL_BACKGROUND * 3 + 0] * 2.0F / 3.0F;
1419 ret[COL_LOWLIGHT * 3 + 1] = ret[COL_BACKGROUND * 3 + 1] * 2.0F / 3.0F;
1420 ret[COL_LOWLIGHT * 3 + 2] = ret[COL_BACKGROUND * 3 + 2] * 2.0F / 3.0F;
1422 *ncolours = NCOLOURS;
1426 static game_drawstate *game_new_drawstate(drawing *dr, const game_state *state)
1428 struct game_drawstate *ds = snew(struct game_drawstate);
1432 ds->tileinner = ds->tilegap = 0; /* not decided yet */
1433 ds->tiles = snewn(state->n, int);
1435 for (i = 0; i < state->n; i++)
1441 static void game_free_drawstate(drawing *dr, game_drawstate *ds)
1447 /* Drawing routing for the tile at (x,y) is responsible for drawing
1448 * itself and the gaps to its right and below. If we're the same colour
1449 * as the tile to our right, then we fill in the gap; ditto below, and if
1450 * both then we fill the teeny tiny square in the corner as well.
1453 static void tile_redraw(drawing *dr, game_drawstate *ds,
1454 int x, int y, int dright, int dbelow,
1455 int tile, int bgcolour)
1457 int outer = bgcolour, inner = outer, col = tile & TILE_COLMASK;
1460 if (tile & TILE_IMPOSSIBLE) {
1462 inner = COL_IMPOSSIBLE;
1463 } else if (tile & TILE_SELECTED) {
1467 outer = inner = col;
1470 draw_rect(dr, COORD(x), COORD(y), TILE_INNER, TILE_INNER, outer);
1471 draw_rect(dr, COORD(x)+TILE_INNER/4, COORD(y)+TILE_INNER/4,
1472 TILE_INNER/2, TILE_INNER/2, inner);
1475 draw_rect(dr, COORD(x)+TILE_INNER, COORD(y), TILE_GAP, TILE_INNER,
1476 (tile & TILE_JOINRIGHT) ? outer : bgcolour);
1478 draw_rect(dr, COORD(x), COORD(y)+TILE_INNER, TILE_INNER, TILE_GAP,
1479 (tile & TILE_JOINDOWN) ? outer : bgcolour);
1480 if (dright && dbelow)
1481 draw_rect(dr, COORD(x)+TILE_INNER, COORD(y)+TILE_INNER, TILE_GAP, TILE_GAP,
1482 (tile & TILE_JOINDIAG) ? outer : bgcolour);
1484 if (tile & TILE_HASSEL) {
1485 int sx = COORD(x)+2, sy = COORD(y)+2, ssz = TILE_INNER-5;
1486 int scol = (outer == COL_SEL) ? COL_LOWLIGHT : COL_HIGHLIGHT;
1487 draw_line(dr, sx, sy, sx+ssz, sy, scol);
1488 draw_line(dr, sx+ssz, sy, sx+ssz, sy+ssz, scol);
1489 draw_line(dr, sx+ssz, sy+ssz, sx, sy+ssz, scol);
1490 draw_line(dr, sx, sy+ssz, sx, sy, scol);
1493 draw_update(dr, COORD(x), COORD(y), TILE_SIZE, TILE_SIZE);
1496 static void game_redraw(drawing *dr, game_drawstate *ds,
1497 const game_state *oldstate, const game_state *state,
1498 int dir, const game_ui *ui,
1499 float animtime, float flashtime)
1503 /* This was entirely cloned from fifteen.c; it should probably be
1504 * moved into some generic 'draw-recessed-rectangle' utility fn. */
1509 TILE_SIZE * state->params.w + 2 * BORDER,
1510 TILE_SIZE * state->params.h + 2 * BORDER, COL_BACKGROUND);
1511 draw_update(dr, 0, 0,
1512 TILE_SIZE * state->params.w + 2 * BORDER,
1513 TILE_SIZE * state->params.h + 2 * BORDER);
1516 * Recessed area containing the whole puzzle.
1518 coords[0] = COORD(state->params.w) + HIGHLIGHT_WIDTH - 1 - TILE_GAP;
1519 coords[1] = COORD(state->params.h) + HIGHLIGHT_WIDTH - 1 - TILE_GAP;
1520 coords[2] = COORD(state->params.w) + HIGHLIGHT_WIDTH - 1 - TILE_GAP;
1521 coords[3] = COORD(0) - HIGHLIGHT_WIDTH;
1522 coords[4] = coords[2] - TILE_SIZE;
1523 coords[5] = coords[3] + TILE_SIZE;
1524 coords[8] = COORD(0) - HIGHLIGHT_WIDTH;
1525 coords[9] = COORD(state->params.h) + HIGHLIGHT_WIDTH - 1 - TILE_GAP;
1526 coords[6] = coords[8] + TILE_SIZE;
1527 coords[7] = coords[9] - TILE_SIZE;
1528 draw_polygon(dr, coords, 5, COL_HIGHLIGHT, COL_HIGHLIGHT);
1530 coords[1] = COORD(0) - HIGHLIGHT_WIDTH;
1531 coords[0] = COORD(0) - HIGHLIGHT_WIDTH;
1532 draw_polygon(dr, coords, 5, COL_LOWLIGHT, COL_LOWLIGHT);
1537 if (flashtime > 0.0) {
1538 int frame = (int)(flashtime / FLASH_FRAME);
1539 bgcolour = (frame % 2 ? COL_LOWLIGHT : COL_HIGHLIGHT);
1541 bgcolour = COL_BACKGROUND;
1543 for (x = 0; x < state->params.w; x++) {
1544 for (y = 0; y < state->params.h; y++) {
1545 int i = (state->params.w * y) + x;
1546 int col = COL(state,x,y), tile = col;
1547 int dright = (x+1 < state->params.w);
1548 int dbelow = (y+1 < state->params.h);
1550 tile |= ISSEL(ui,x,y);
1551 if (state->impossible)
1552 tile |= TILE_IMPOSSIBLE;
1553 if (dright && COL(state,x+1,y) == col)
1554 tile |= TILE_JOINRIGHT;
1555 if (dbelow && COL(state,x,y+1) == col)
1556 tile |= TILE_JOINDOWN;
1557 if ((tile & TILE_JOINRIGHT) && (tile & TILE_JOINDOWN) &&
1558 COL(state,x+1,y+1) == col)
1559 tile |= TILE_JOINDIAG;
1561 if (ui->displaysel && ui->xsel == x && ui->ysel == y)
1562 tile |= TILE_HASSEL;
1564 /* For now we're never expecting oldstate at all (because we have
1565 * no animation); when we do we might well want to be looking
1566 * at the tile colours from oldstate, not state. */
1567 if ((oldstate && COL(oldstate,x,y) != col) ||
1568 (ds->bgcolour != bgcolour) ||
1569 (tile != ds->tiles[i])) {
1570 tile_redraw(dr, ds, x, y, dright, dbelow, tile, bgcolour);
1571 ds->tiles[i] = tile;
1575 ds->bgcolour = bgcolour;
1578 char status[255], score[80];
1580 sprintf(score, "Score: %d", state->score);
1582 if (state->complete)
1583 sprintf(status, "COMPLETE! %s", score);
1584 else if (state->impossible)
1585 sprintf(status, "Cannot move! %s", score);
1586 else if (ui->nselected)
1587 sprintf(status, "%s Selected: %d (%d)",
1588 score, ui->nselected, npoints(&state->params, ui->nselected));
1590 sprintf(status, "%s", score);
1591 status_bar(dr, status);
1595 static float game_anim_length(const game_state *oldstate,
1596 const game_state *newstate, int dir, game_ui *ui)
1601 static float game_flash_length(const game_state *oldstate,
1602 const game_state *newstate, int dir, game_ui *ui)
1604 if ((!oldstate->complete && newstate->complete) ||
1605 (!oldstate->impossible && newstate->impossible))
1606 return 2 * FLASH_FRAME;
1611 static int game_status(const game_state *state)
1614 * Dead-end situations are assumed to be rescuable by Undo, so we
1615 * don't bother to identify them and return -1.
1617 return state->complete ? +1 : 0;
1620 static int game_timing_state(const game_state *state, game_ui *ui)
1625 static void game_print_size(const game_params *params, float *x, float *y)
1629 static void game_print(drawing *dr, const game_state *state, int tilesize)
1634 #define thegame samegame
1637 const struct game thegame = {
1638 "Same Game", "games.samegame", "samegame",
1640 game_fetch_preset, NULL,
1645 TRUE, game_configure, custom_params,
1653 TRUE, game_can_format_as_text_now, game_text_format,
1661 PREFERRED_TILE_SIZE, game_compute_size, game_set_size,
1664 game_free_drawstate,
1669 FALSE, FALSE, game_print_size, game_print,
1670 TRUE, /* wants_statusbar */
1671 FALSE, game_timing_state,