From 881746789a489fad85aae8317555f73dbe261556 Mon Sep 17 00:00:00 2001 From: Franklin Wei Date: Sat, 29 Apr 2017 18:21:56 -0400 Subject: puzzles: refactor and resync with upstream This brings puzzles up-to-date with upstream revision 2d333750272c3967cfd5cd3677572cddeaad5932, though certain changes made by me, including cursor-only Untangle and some compilation fixes remain. Upstream code has been moved to its separate subdirectory and future syncs can be done by simply copying over the new sources. Change-Id: Ia6506ca5f78c3627165ea6791d38db414ace0804 --- apps/plugins/puzzles/src/samegame.c | 1679 +++++++++++++++++++++++++++++++++++ 1 file changed, 1679 insertions(+) create mode 100644 apps/plugins/puzzles/src/samegame.c (limited to 'apps/plugins/puzzles/src/samegame.c') diff --git a/apps/plugins/puzzles/src/samegame.c b/apps/plugins/puzzles/src/samegame.c new file mode 100644 index 0000000000..88edad32b1 --- /dev/null +++ b/apps/plugins/puzzles/src/samegame.c @@ -0,0 +1,1679 @@ +/* + * 'same game' -- try to remove all the coloured squares by + * selecting regions of contiguous colours. + */ + +/* + * TODO on grid generation: + * + * - Generation speed could still be improved. + * * 15x10c3 is the only really difficult one of the existing + * presets. The others are all either small enough, or have + * the great flexibility given by four colours, that they + * don't take long at all. + * * I still suspect many problems arise from separate + * subareas. I wonder if we can also somehow prioritise left- + * or rightmost insertions so as to avoid area splitting at + * all where feasible? It's not easy, though, because the + * current shuffle-then-try-all-options approach to move + * choice doesn't leave room for `soft' probabilistic + * prioritisation: we either try all class A moves before any + * class B ones, or we don't. + * + * - The current generation algorithm inserts exactly two squares + * at a time, with a single exception at the beginning of + * generation for grids of odd overall size. An obvious + * extension would be to permit larger inverse moves during + * generation. + * * this might reduce the number of failed generations by + * making the insertion algorithm more flexible + * * on the other hand, it would be significantly more complex + * * if I do this I'll need to take out the odd-subarea + * avoidance + * * a nice feature of the current algorithm is that the + * computer's `intended' solution always receives the minimum + * possible score, so that pretty much the player's entire + * score represents how much better they did than the + * computer. + * + * - Is it possible we can _temporarily_ tolerate neighbouring + * squares of the same colour, until we've finished setting up + * our inverse move? + * * or perhaps even not choose the colour of our inserted + * region until we have finished placing it, and _then_ look + * at what colours border on it? + * * I don't think this is currently meaningful unless we're + * placing more than a domino at a time. + * + * - possibly write out a full solution so that Solve can somehow + * show it step by step? + * * aux_info would have to encode the click points + * * solve_game() would have to encode not only those click + * points but also give a move string which reconstructed the + * initial state + * * the game_state would include a pointer to a solution move + * list, plus an index into that list + * * game_changed_state would auto-select the next move if + * handed a new state which had a solution move list active + * * execute_move, if passed such a state as input, would check + * to see whether the move being made was the same as the one + * stated by the solution, and if so would advance the move + * index. Failing that it would return a game_state without a + * solution move list active at all. + */ + +#include +#include +#include +#include +#include +#include + +#include "puzzles.h" + +#define TILE_INNER (ds->tileinner) +#define TILE_GAP (ds->tilegap) +#define TILE_SIZE (TILE_INNER + TILE_GAP) +#define PREFERRED_TILE_SIZE 32 +#define BORDER (TILE_SIZE / 2) +#define HIGHLIGHT_WIDTH 2 + +#define FLASH_FRAME 0.13F + +#define COORD(x) ( (x) * TILE_SIZE + BORDER ) +#define FROMCOORD(x) ( ((x) - BORDER + TILE_SIZE) / TILE_SIZE - 1 ) + +#define X(state, i) ( (i) % (state)->params.w ) +#define Y(state, i) ( (i) / (state)->params.w ) +#define C(state, x, y) ( (y) * (state)->w + (x) ) + +enum { + COL_BACKGROUND, + COL_1, COL_2, COL_3, COL_4, COL_5, COL_6, COL_7, COL_8, COL_9, + COL_IMPOSSIBLE, COL_SEL, COL_HIGHLIGHT, COL_LOWLIGHT, + NCOLOURS +}; + +/* scoresub is 1 or 2 (for (n-1)^2 or (n-2)^2) */ +struct game_params { + int w, h, ncols, scoresub; + int soluble; /* choose generation algorithm */ +}; + +/* These flags must be unique across all uses; in the game_state, + * the game_ui, and the drawstate (as they all get combined in the + * drawstate). */ +#define TILE_COLMASK 0x00ff +#define TILE_SELECTED 0x0100 /* used in ui and drawstate */ +#define TILE_JOINRIGHT 0x0200 /* used in drawstate */ +#define TILE_JOINDOWN 0x0400 /* used in drawstate */ +#define TILE_JOINDIAG 0x0800 /* used in drawstate */ +#define TILE_HASSEL 0x1000 /* used in drawstate */ +#define TILE_IMPOSSIBLE 0x2000 /* used in drawstate */ + +#define TILE(gs,x,y) ((gs)->tiles[(gs)->params.w*(y)+(x)]) +#define COL(gs,x,y) (TILE(gs,x,y) & TILE_COLMASK) +#define ISSEL(gs,x,y) (TILE(gs,x,y) & TILE_SELECTED) + +#define SWAPTILE(gs,x1,y1,x2,y2) do { \ + int t = TILE(gs,x1,y1); \ + TILE(gs,x1,y1) = TILE(gs,x2,y2); \ + TILE(gs,x2,y2) = t; \ +} while (0) + +static int npoints(const game_params *params, int nsel) +{ + int sdiff = nsel - params->scoresub; + return (sdiff > 0) ? sdiff * sdiff : 0; +} + +struct game_state { + struct game_params params; + int n; + int *tiles; /* colour only */ + int score; + int complete, impossible; +}; + +static game_params *default_params(void) +{ + game_params *ret = snew(game_params); + ret->w = 5; + ret->h = 5; + ret->ncols = 3; + ret->scoresub = 2; + ret->soluble = TRUE; + return ret; +} + +static const struct game_params samegame_presets[] = { + { 5, 5, 3, 2, TRUE }, + { 10, 5, 3, 2, TRUE }, +#ifdef SLOW_SYSTEM + { 10, 10, 3, 2, TRUE }, +#else + { 15, 10, 3, 2, TRUE }, +#endif + { 15, 10, 4, 2, TRUE }, + { 20, 15, 4, 2, TRUE } +}; + +static int game_fetch_preset(int i, char **name, game_params **params) +{ + game_params *ret; + char str[80]; + + if (i < 0 || i >= lenof(samegame_presets)) + return FALSE; + + ret = snew(game_params); + *ret = samegame_presets[i]; + + sprintf(str, "%dx%d, %d colours", ret->w, ret->h, ret->ncols); + + *name = dupstr(str); + *params = ret; + return TRUE; +} + +static void free_params(game_params *params) +{ + sfree(params); +} + +static game_params *dup_params(const game_params *params) +{ + game_params *ret = snew(game_params); + *ret = *params; /* structure copy */ + return ret; +} + +static void decode_params(game_params *params, char const *string) +{ + char const *p = string; + + params->w = atoi(p); + while (*p && isdigit((unsigned char)*p)) p++; + if (*p == 'x') { + p++; + params->h = atoi(p); + while (*p && isdigit((unsigned char)*p)) p++; + } else { + params->h = params->w; + } + if (*p == 'c') { + p++; + params->ncols = atoi(p); + while (*p && isdigit((unsigned char)*p)) p++; + } else { + params->ncols = 3; + } + if (*p == 's') { + p++; + params->scoresub = atoi(p); + while (*p && isdigit((unsigned char)*p)) p++; + } else { + params->scoresub = 2; + } + if (*p == 'r') { + p++; + params->soluble = FALSE; + } +} + +static char *encode_params(const game_params *params, int full) +{ + char ret[80]; + + sprintf(ret, "%dx%dc%ds%d%s", + params->w, params->h, params->ncols, params->scoresub, + full && !params->soluble ? "r" : ""); + return dupstr(ret); +} + +static config_item *game_configure(const game_params *params) +{ + config_item *ret; + char buf[80]; + + ret = snewn(6, config_item); + + ret[0].name = "Width"; + ret[0].type = C_STRING; + sprintf(buf, "%d", params->w); + ret[0].sval = dupstr(buf); + ret[0].ival = 0; + + ret[1].name = "Height"; + ret[1].type = C_STRING; + sprintf(buf, "%d", params->h); + ret[1].sval = dupstr(buf); + ret[1].ival = 0; + + ret[2].name = "No. of colours"; + ret[2].type = C_STRING; + sprintf(buf, "%d", params->ncols); + ret[2].sval = dupstr(buf); + ret[2].ival = 0; + + ret[3].name = "Scoring system"; + ret[3].type = C_CHOICES; + ret[3].sval = ":(n-1)^2:(n-2)^2"; + ret[3].ival = params->scoresub-1; + + ret[4].name = "Ensure solubility"; + ret[4].type = C_BOOLEAN; + ret[4].sval = NULL; + ret[4].ival = params->soluble; + + ret[5].name = NULL; + ret[5].type = C_END; + ret[5].sval = NULL; + ret[5].ival = 0; + + return ret; +} + +static game_params *custom_params(const config_item *cfg) +{ + game_params *ret = snew(game_params); + + ret->w = atoi(cfg[0].sval); + ret->h = atoi(cfg[1].sval); + ret->ncols = atoi(cfg[2].sval); + ret->scoresub = cfg[3].ival + 1; + ret->soluble = cfg[4].ival; + + return ret; +} + +static char *validate_params(const game_params *params, int full) +{ + if (params->w < 1 || params->h < 1) + return "Width and height must both be positive"; + + if (params->ncols > 9) + return "Maximum of 9 colours"; + + if (params->soluble) { + if (params->ncols < 3) + return "Number of colours must be at least three"; + if (params->w * params->h <= 1) + return "Grid area must be greater than 1"; + } else { + if (params->ncols < 2) + return "Number of colours must be at least three"; + /* ...and we must make sure we can generate at least 2 squares + * of each colour so it's theoretically soluble. */ + if ((params->w * params->h) < (params->ncols * 2)) + return "Too many colours makes given grid size impossible"; + } + + if ((params->scoresub < 1) || (params->scoresub > 2)) + return "Scoring system not recognised"; + + return NULL; +} + +/* + * Guaranteed-soluble grid generator. + */ +static void gen_grid(int w, int h, int nc, int *grid, random_state *rs) +{ + int wh = w*h, tc = nc+1; + int i, j, k, c, x, y, pos, n; + int *list, *grid2; + int ok, failures = 0; + + /* + * We'll use `list' to track the possible places to put our + * next insertion. There are up to h places to insert in each + * column: in a column of height n there are n+1 places because + * we can insert at the very bottom or the very top, but a + * column of height h can't have anything at all inserted in it + * so we have up to h in each column. Likewise, with n columns + * present there are n+1 places to fit a new one in between but + * we can't insert a column if there are already w; so there + * are a maximum of w new columns too. Total is wh + w. + */ + list = snewn(wh + w, int); + grid2 = snewn(wh, int); + + do { + /* + * Start with two or three squares - depending on parity of w*h + * - of a random colour. + */ + for (i = 0; i < wh; i++) + grid[i] = 0; + j = 2 + (wh % 2); + c = 1 + random_upto(rs, nc); + if (j <= w) { + for (i = 0; i < j; i++) + grid[(h-1)*w+i] = c; + } else { + assert(j <= h); + for (i = 0; i < j; i++) + grid[(h-1-i)*w] = c; + } + + /* + * Now repeatedly insert a two-square blob in the grid, of + * whatever colour will go at the position we chose. + */ + while (1) { + n = 0; + + /* + * Build up a list of insertion points. Each point is + * encoded as y*w+x; insertion points between columns are + * encoded as h*w+x. + */ + + if (grid[wh - 1] == 0) { + /* + * The final column is empty, so we can insert new + * columns. + */ + for (i = 0; i < w; i++) { + list[n++] = wh + i; + if (grid[(h-1)*w + i] == 0) + break; + } + } + + /* + * Now look for places to insert within columns. + */ + for (i = 0; i < w; i++) { + if (grid[(h-1)*w+i] == 0) + break; /* no more columns */ + + if (grid[i] != 0) + continue; /* this column is full */ + + for (j = h; j-- > 0 ;) { + list[n++] = j*w+i; + if (grid[j*w+i] == 0) + break; /* this column is exhausted */ + } + } + + if (n == 0) + break; /* we're done */ + +#ifdef GENERATION_DIAGNOSTICS + printf("initial grid:\n"); + { + int x,y; + for (y = 0; y < h; y++) { + for (x = 0; x < w; x++) { + if (grid[y*w+x] == 0) + printf("-"); + else + printf("%d", grid[y*w+x]); + } + printf("\n"); + } + } +#endif + + /* + * Now go through the list one element at a time in + * random order, and actually attempt to insert + * something there. + */ + while (n-- > 0) { + int dirs[4], ndirs, dir; + + i = random_upto(rs, n+1); + pos = list[i]; + list[i] = list[n]; + + x = pos % w; + y = pos / w; + + memcpy(grid2, grid, wh * sizeof(int)); + + if (y == h) { + /* + * Insert a column at position x. + */ + for (i = w-1; i > x; i--) + for (j = 0; j < h; j++) + grid2[j*w+i] = grid2[j*w+(i-1)]; + /* + * Clear the new column. + */ + for (j = 0; j < h; j++) + grid2[j*w+x] = 0; + /* + * Decrement y so that our first square is actually + * inserted _in_ the grid rather than just below it. + */ + y--; + } + + /* + * Insert a square within column x at position y. + */ + for (i = 0; i+1 <= y; i++) + grid2[i*w+x] = grid2[(i+1)*w+x]; + +#ifdef GENERATION_DIAGNOSTICS + printf("trying at n=%d (%d,%d)\n", n, x, y); + grid2[y*w+x] = tc; + { + int x,y; + for (y = 0; y < h; y++) { + for (x = 0; x < w; x++) { + if (grid2[y*w+x] == 0) + printf("-"); + else if (grid2[y*w+x] <= nc) + printf("%d", grid2[y*w+x]); + else + printf("*"); + } + printf("\n"); + } + } +#endif + + /* + * Pick our square colour so that it doesn't match any + * of its neighbours. + */ + { + int wrongcol[4], nwrong = 0; + + /* + * List the neighbouring colours. + */ + if (x > 0) + wrongcol[nwrong++] = grid2[y*w+(x-1)]; + if (x+1 < w) + wrongcol[nwrong++] = grid2[y*w+(x+1)]; + if (y > 0) + wrongcol[nwrong++] = grid2[(y-1)*w+x]; + if (y+1 < h) + wrongcol[nwrong++] = grid2[(y+1)*w+x]; + + /* + * Eliminate duplicates. We can afford a shoddy + * algorithm here because the problem size is + * bounded. + */ + for (i = j = 0 ;; i++) { + int pos = -1, min = 0; + if (j > 0) + min = wrongcol[j-1]; + for (k = i; k < nwrong; k++) + if (wrongcol[k] > min && + (pos == -1 || wrongcol[k] < wrongcol[pos])) + pos = k; + if (pos >= 0) { + int v = wrongcol[pos]; + wrongcol[pos] = wrongcol[j]; + wrongcol[j++] = v; + } else + break; + } + nwrong = j; + + /* + * If no colour will go here, stop trying. + */ + if (nwrong == nc) + continue; + + /* + * Otherwise, pick a colour from the remaining + * ones. + */ + c = 1 + random_upto(rs, nc - nwrong); + for (i = 0; i < nwrong; i++) { + if (c >= wrongcol[i]) + c++; + else + break; + } + } + + /* + * Place the new square. + * + * Although I've _chosen_ the new region's colour + * (so that we can check adjacency), I'm going to + * actually place it as an invalid colour (tc) + * until I'm sure it's viable. This is so that I + * can conveniently check that I really have made a + * _valid_ inverse move later on. + */ +#ifdef GENERATION_DIAGNOSTICS + printf("picked colour %d\n", c); +#endif + grid2[y*w+x] = tc; + + /* + * Now attempt to extend it in one of three ways: left, + * right or up. + */ + ndirs = 0; + if (x > 0 && + grid2[y*w+(x-1)] != c && + grid2[x-1] == 0 && + (y+1 >= h || grid2[(y+1)*w+(x-1)] != c) && + (y+1 >= h || grid2[(y+1)*w+(x-1)] != 0) && + (x <= 1 || grid2[y*w+(x-2)] != c)) + dirs[ndirs++] = -1; /* left */ + if (x+1 < w && + grid2[y*w+(x+1)] != c && + grid2[x+1] == 0 && + (y+1 >= h || grid2[(y+1)*w+(x+1)] != c) && + (y+1 >= h || grid2[(y+1)*w+(x+1)] != 0) && + (x+2 >= w || grid2[y*w+(x+2)] != c)) + dirs[ndirs++] = +1; /* right */ + if (y > 0 && + grid2[x] == 0 && + (x <= 0 || grid2[(y-1)*w+(x-1)] != c) && + (x+1 >= w || grid2[(y-1)*w+(x+1)] != c)) { + /* + * We add this possibility _twice_, so that the + * probability of placing a vertical domino is + * about the same as that of a horizontal. This + * should yield less bias in the generated + * grids. + */ + dirs[ndirs++] = 0; /* up */ + dirs[ndirs++] = 0; /* up */ + } + + if (ndirs == 0) + continue; + + dir = dirs[random_upto(rs, ndirs)]; + +#ifdef GENERATION_DIAGNOSTICS + printf("picked dir %d\n", dir); +#endif + + /* + * Insert a square within column (x+dir) at position y. + */ + for (i = 0; i+1 <= y; i++) + grid2[i*w+x+dir] = grid2[(i+1)*w+x+dir]; + grid2[y*w+x+dir] = tc; + + /* + * See if we've divided the remaining grid squares + * into sub-areas. If so, we need every sub-area to + * have an even area or we won't be able to + * complete generation. + * + * If the height is odd and not all columns are + * present, we can increase the area of a subarea + * by adding a new column in it, so in that + * situation we don't mind having as many odd + * subareas as there are spare columns. + * + * If the height is even, we can't fix it at all. + */ + { + int nerrs = 0, nfix = 0; + k = 0; /* current subarea size */ + for (i = 0; i < w; i++) { + if (grid2[(h-1)*w+i] == 0) { + if (h % 2) + nfix++; + continue; + } + for (j = 0; j < h && grid2[j*w+i] == 0; j++); + assert(j < h); + if (j == 0) { + /* + * End of previous subarea. + */ + if (k % 2) + nerrs++; + k = 0; + } else { + k += j; + } + } + if (k % 2) + nerrs++; + if (nerrs > nfix) + continue; /* try a different placement */ + } + + /* + * We've made a move. Verify that it is a valid + * move and that if made it would indeed yield the + * previous grid state. The criteria are: + * + * (a) removing all the squares of colour tc (and + * shuffling the columns up etc) from grid2 + * would yield grid + * (b) no square of colour tc is adjacent to one + * of colour c + * (c) all the squares of colour tc form a single + * connected component + * + * We verify the latter property at the same time + * as checking that removing all the tc squares + * would yield the previous grid. Then we colour + * the tc squares in colour c by breadth-first + * search, which conveniently permits us to test + * that they're all connected. + */ + { + int x1, x2, y1, y2; + int ok = TRUE; + int fillstart = -1, ntc = 0; + +#ifdef GENERATION_DIAGNOSTICS + { + int x,y; + printf("testing move (new, old):\n"); + for (y = 0; y < h; y++) { + for (x = 0; x < w; x++) { + if (grid2[y*w+x] == 0) + printf("-"); + else if (grid2[y*w+x] <= nc) + printf("%d", grid2[y*w+x]); + else + printf("*"); + } + printf(" "); + for (x = 0; x < w; x++) { + if (grid[y*w+x] == 0) + printf("-"); + else + printf("%d", grid[y*w+x]); + } + printf("\n"); + } + } +#endif + + for (x1 = x2 = 0; x2 < w; x2++) { + int usedcol = FALSE; + + for (y1 = y2 = h-1; y2 >= 0; y2--) { + if (grid2[y2*w+x2] == tc) { + ntc++; + if (fillstart == -1) + fillstart = y2*w+x2; + if ((y2+1 < h && grid2[(y2+1)*w+x2] == c) || + (y2-1 >= 0 && grid2[(y2-1)*w+x2] == c) || + (x2+1 < w && grid2[y2*w+x2+1] == c) || + (x2-1 >= 0 && grid2[y2*w+x2-1] == c)) { +#ifdef GENERATION_DIAGNOSTICS + printf("adjacency failure at %d,%d\n", + x2, y2); +#endif + ok = FALSE; + } + continue; + } + if (grid2[y2*w+x2] == 0) + break; + usedcol = TRUE; + if (grid2[y2*w+x2] != grid[y1*w+x1]) { +#ifdef GENERATION_DIAGNOSTICS + printf("matching failure at %d,%d vs %d,%d\n", + x2, y2, x1, y1); +#endif + ok = FALSE; + } + y1--; + } + + /* + * If we've reached the top of the column + * in grid2, verify that we've also reached + * the top of the column in `grid'. + */ + if (usedcol) { + while (y1 >= 0) { + if (grid[y1*w+x1] != 0) { +#ifdef GENERATION_DIAGNOSTICS + printf("junk at column top (%d,%d)\n", + x1, y1); +#endif + ok = FALSE; + } + y1--; + } + } + + if (!ok) + break; + + if (usedcol) + x1++; + } + + if (!ok) { + assert(!"This should never happen"); + + /* + * If this game is compiled NDEBUG so that + * the assertion doesn't bring it to a + * crashing halt, the only thing we can do + * is to give up, loop round again, and + * hope to randomly avoid making whatever + * type of move just caused this failure. + */ + continue; + } + + /* + * Now use bfs to fill in the tc section as + * colour c. We use `list' to store the set of + * squares we have to process. + */ + i = j = 0; + assert(fillstart >= 0); + list[i++] = fillstart; +#ifdef OUTPUT_SOLUTION + printf("M"); +#endif + while (j < i) { + k = list[j]; + x = k % w; + y = k / w; +#ifdef OUTPUT_SOLUTION + printf("%s%d", j ? "," : "", k); +#endif + j++; + + assert(grid2[k] == tc); + grid2[k] = c; + + if (x > 0 && grid2[k-1] == tc) + list[i++] = k-1; + if (x+1 < w && grid2[k+1] == tc) + list[i++] = k+1; + if (y > 0 && grid2[k-w] == tc) + list[i++] = k-w; + if (y+1 < h && grid2[k+w] == tc) + list[i++] = k+w; + } +#ifdef OUTPUT_SOLUTION + printf("\n"); +#endif + + /* + * Check that we've filled the same number of + * tc squares as we originally found. + */ + assert(j == ntc); + } + + memcpy(grid, grid2, wh * sizeof(int)); + + break; /* done it! */ + } + +#ifdef GENERATION_DIAGNOSTICS + { + int x,y; + printf("n=%d\n", n); + for (y = 0; y < h; y++) { + for (x = 0; x < w; x++) { + if (grid[y*w+x] == 0) + printf("-"); + else + printf("%d", grid[y*w+x]); + } + printf("\n"); + } + } +#endif + + if (n < 0) + break; + } + + ok = TRUE; + for (i = 0; i < wh; i++) + if (grid[i] == 0) { + ok = FALSE; + failures++; +#if defined GENERATION_DIAGNOSTICS || defined SHOW_INCOMPLETE + { + int x,y; + printf("incomplete grid:\n"); + for (y = 0; y < h; y++) { + for (x = 0; x < w; x++) { + if (grid[y*w+x] == 0) + printf("-"); + else + printf("%d", grid[y*w+x]); + } + printf("\n"); + } + } +#endif + break; + } + + } while (!ok); + +#if defined GENERATION_DIAGNOSTICS || defined COUNT_FAILURES + printf("%d failures\n", failures); +#endif +#ifdef GENERATION_DIAGNOSTICS + { + int x,y; + printf("final grid:\n"); + for (y = 0; y < h; y++) { + for (x = 0; x < w; x++) { + printf("%d", grid[y*w+x]); + } + printf("\n"); + } + } +#endif + + sfree(grid2); + sfree(list); +} + +/* + * Not-guaranteed-soluble grid generator; kept as a legacy, and in + * case someone finds the slightly odd quality of the guaranteed- + * soluble grids to be aesthetically displeasing or finds its CPU + * utilisation to be excessive. + */ +static void gen_grid_random(int w, int h, int nc, int *grid, random_state *rs) +{ + int i, j, c; + int n = w * h; + + for (i = 0; i < n; i++) + grid[i] = 0; + + /* + * Our sole concession to not gratuitously generating insoluble + * grids is to ensure we have at least two of every colour. + */ + for (c = 1; c <= nc; c++) { + for (j = 0; j < 2; j++) { + do { + i = (int)random_upto(rs, n); + } while (grid[i] != 0); + grid[i] = c; + } + } + + /* + * Fill in the rest of the grid at random. + */ + for (i = 0; i < n; i++) { + if (grid[i] == 0) + grid[i] = (int)random_upto(rs, nc)+1; + } +} + +static char *new_game_desc(const game_params *params, random_state *rs, + char **aux, int interactive) +{ + char *ret; + int n, i, retlen, *tiles; + + n = params->w * params->h; + tiles = snewn(n, int); + + if (params->soluble) + gen_grid(params->w, params->h, params->ncols, tiles, rs); + else + gen_grid_random(params->w, params->h, params->ncols, tiles, rs); + + ret = NULL; + retlen = 0; + for (i = 0; i < n; i++) { + char buf[80]; + int k; + + k = sprintf(buf, "%d,", tiles[i]); + ret = sresize(ret, retlen + k + 1, char); + strcpy(ret + retlen, buf); + retlen += k; + } + ret[retlen-1] = '\0'; /* delete last comma */ + + sfree(tiles); + return ret; +} + +static char *validate_desc(const game_params *params, const char *desc) +{ + int area = params->w * params->h, i; + const char *p = desc; + + for (i = 0; i < area; i++) { + const char *q = p; + int n; + + if (!isdigit((unsigned char)*p)) + return "Not enough numbers in string"; + while (isdigit((unsigned char)*p)) p++; + + if (i < area-1 && *p != ',') + return "Expected comma after number"; + else if (i == area-1 && *p) + return "Excess junk at end of string"; + + n = atoi(q); + if (n < 0 || n > params->ncols) + return "Colour out of range"; + + if (*p) p++; /* eat comma */ + } + return NULL; +} + +static game_state *new_game(midend *me, const game_params *params, + const char *desc) +{ + game_state *state = snew(game_state); + const char *p = desc; + int i; + + state->params = *params; /* struct copy */ + state->n = state->params.w * state->params.h; + state->tiles = snewn(state->n, int); + + for (i = 0; i < state->n; i++) { + assert(*p); + state->tiles[i] = atoi(p); + while (*p && *p != ',') + p++; + if (*p) p++; /* eat comma */ + } + state->complete = state->impossible = 0; + state->score = 0; + + return state; +} + +static game_state *dup_game(const game_state *state) +{ + game_state *ret = snew(game_state); + + *ret = *state; /* structure copy, except... */ + + ret->tiles = snewn(state->n, int); + memcpy(ret->tiles, state->tiles, state->n * sizeof(int)); + + return ret; +} + +static void free_game(game_state *state) +{ + sfree(state->tiles); + sfree(state); +} + +static char *solve_game(const game_state *state, const game_state *currstate, + const char *aux, char **error) +{ + return NULL; +} + +static int game_can_format_as_text_now(const game_params *params) +{ + return TRUE; +} + +static char *game_text_format(const game_state *state) +{ + char *ret, *p; + int x, y, maxlen; + + maxlen = state->params.h * (state->params.w + 1); + ret = snewn(maxlen+1, char); + p = ret; + + for (y = 0; y < state->params.h; y++) { + for (x = 0; x < state->params.w; x++) { + int t = TILE(state,x,y); + if (t <= 0) *p++ = ' '; + else if (t < 10) *p++ = '0'+t; + else *p++ = 'a'+(t-10); + } + *p++ = '\n'; + } + assert(p - ret == maxlen); + *p = '\0'; + return ret; +} + +struct game_ui { + struct game_params params; + int *tiles; /* selected-ness only */ + int nselected; + int xsel, ysel, displaysel; +}; + +static game_ui *new_ui(const game_state *state) +{ + game_ui *ui = snew(game_ui); + + ui->params = state->params; /* structure copy */ + ui->tiles = snewn(state->n, int); + memset(ui->tiles, 0, state->n*sizeof(int)); + ui->nselected = 0; + + ui->xsel = ui->ysel = ui->displaysel = 0; + + return ui; +} + +static void free_ui(game_ui *ui) +{ + sfree(ui->tiles); + sfree(ui); +} + +static char *encode_ui(const game_ui *ui) +{ + return NULL; +} + +static void decode_ui(game_ui *ui, const char *encoding) +{ +} + +static void sel_clear(game_ui *ui, const game_state *state) +{ + int i; + + for (i = 0; i < state->n; i++) + ui->tiles[i] &= ~TILE_SELECTED; + ui->nselected = 0; +} + + +static void game_changed_state(game_ui *ui, const game_state *oldstate, + const game_state *newstate) +{ + sel_clear(ui, newstate); + + /* + * If the game state has just changed into an unplayable one + * (either completed or impossible), we vanish the keyboard- + * control cursor. + */ + if (newstate->complete || newstate->impossible) + ui->displaysel = 0; +} + +static char *sel_movedesc(game_ui *ui, const game_state *state) +{ + int i; + char *ret, *sep, buf[80]; + int retlen, retsize; + + retsize = 256; + ret = snewn(retsize, char); + retlen = 0; + ret[retlen++] = 'M'; + sep = ""; + + for (i = 0; i < state->n; i++) { + if (ui->tiles[i] & TILE_SELECTED) { + sprintf(buf, "%s%d", sep, i); + sep = ","; + if (retlen + (int)strlen(buf) >= retsize) { + retsize = retlen + strlen(buf) + 256; + ret = sresize(ret, retsize, char); + } + strcpy(ret + retlen, buf); + retlen += strlen(buf); + + ui->tiles[i] &= ~TILE_SELECTED; + } + } + ui->nselected = 0; + + assert(retlen < retsize); + ret[retlen++] = '\0'; + return sresize(ret, retlen, char); +} + +static void sel_expand(game_ui *ui, const game_state *state, int tx, int ty) +{ + int ns = 1, nadded, x, y, c; + + TILE(ui,tx,ty) |= TILE_SELECTED; + do { + nadded = 0; + + for (x = 0; x < state->params.w; x++) { + for (y = 0; y < state->params.h; y++) { + if (x == tx && y == ty) continue; + if (ISSEL(ui,x,y)) continue; + + c = COL(state,x,y); + if ((x > 0) && + ISSEL(ui,x-1,y) && COL(state,x-1,y) == c) { + TILE(ui,x,y) |= TILE_SELECTED; + nadded++; + continue; + } + + if ((x+1 < state->params.w) && + ISSEL(ui,x+1,y) && COL(state,x+1,y) == c) { + TILE(ui,x,y) |= TILE_SELECTED; + nadded++; + continue; + } + + if ((y > 0) && + ISSEL(ui,x,y-1) && COL(state,x,y-1) == c) { + TILE(ui,x,y) |= TILE_SELECTED; + nadded++; + continue; + } + + if ((y+1 < state->params.h) && + ISSEL(ui,x,y+1) && COL(state,x,y+1) == c) { + TILE(ui,x,y) |= TILE_SELECTED; + nadded++; + continue; + } + } + } + ns += nadded; + } while (nadded > 0); + + if (ns > 1) { + ui->nselected = ns; + } else { + sel_clear(ui, state); + } +} + +static int sg_emptycol(game_state *ret, int x) +{ + int y; + for (y = 0; y < ret->params.h; y++) { + if (COL(ret,x,y)) return 0; + } + return 1; +} + + +static void sg_snuggle(game_state *ret) +{ + int x,y, ndone; + + /* make all unsupported tiles fall down. */ + do { + ndone = 0; + for (x = 0; x < ret->params.w; x++) { + for (y = ret->params.h-1; y > 0; y--) { + if (COL(ret,x,y) != 0) continue; + if (COL(ret,x,y-1) != 0) { + SWAPTILE(ret,x,y,x,y-1); + ndone++; + } + } + } + } while (ndone); + + /* shuffle all columns as far left as they can go. */ + do { + ndone = 0; + for (x = 0; x < ret->params.w-1; x++) { + if (sg_emptycol(ret,x) && !sg_emptycol(ret,x+1)) { + ndone++; + for (y = 0; y < ret->params.h; y++) { + SWAPTILE(ret,x,y,x+1,y); + } + } + } + } while (ndone); +} + +static void sg_check(game_state *ret) +{ + int x,y, complete = 1, impossible = 1; + + for (x = 0; x < ret->params.w; x++) { + for (y = 0; y < ret->params.h; y++) { + if (COL(ret,x,y) == 0) + continue; + complete = 0; + if (x+1 < ret->params.w) { + if (COL(ret,x,y) == COL(ret,x+1,y)) + impossible = 0; + } + if (y+1 < ret->params.h) { + if (COL(ret,x,y) == COL(ret,x,y+1)) + impossible = 0; + } + } + } + ret->complete = complete; + ret->impossible = impossible; +} + +struct game_drawstate { + int started, bgcolour; + int tileinner, tilegap; + int *tiles; /* contains colour and SELECTED. */ +}; + +static char *interpret_move(const game_state *state, game_ui *ui, + const game_drawstate *ds, + int x, int y, int button) +{ + int tx, ty; + char *ret = ""; + + ui->displaysel = 0; + + if (button == RIGHT_BUTTON || button == LEFT_BUTTON) { + tx = FROMCOORD(x); ty= FROMCOORD(y); + } else if (IS_CURSOR_MOVE(button)) { + int dx = 0, dy = 0; + ui->displaysel = 1; + dx = (button == CURSOR_LEFT) ? -1 : ((button == CURSOR_RIGHT) ? +1 : 0); + dy = (button == CURSOR_DOWN) ? +1 : ((button == CURSOR_UP) ? -1 : 0); + ui->xsel = (ui->xsel + state->params.w + dx) % state->params.w; + ui->ysel = (ui->ysel + state->params.h + dy) % state->params.h; + return ret; + } else if (IS_CURSOR_SELECT(button)) { + ui->displaysel = 1; + tx = ui->xsel; + ty = ui->ysel; + } else + return NULL; + + if (tx < 0 || tx >= state->params.w || ty < 0 || ty >= state->params.h) + return NULL; + if (COL(state, tx, ty) == 0) return NULL; + + if (ISSEL(ui,tx,ty)) { + if (button == RIGHT_BUTTON || button == CURSOR_SELECT2) + sel_clear(ui, state); + else + ret = sel_movedesc(ui, state); + } else { + sel_clear(ui, state); /* might be no-op */ + sel_expand(ui, state, tx, ty); + } + + return ret; +} + +static game_state *execute_move(const game_state *from, const char *move) +{ + int i, n; + game_state *ret; + + if (move[0] == 'M') { + ret = dup_game(from); + + n = 0; + move++; + + while (*move) { + i = atoi(move); + if (i < 0 || i >= ret->n) { + free_game(ret); + return NULL; + } + n++; + ret->tiles[i] = 0; + + while (*move && isdigit((unsigned char)*move)) move++; + if (*move == ',') move++; + } + + ret->score += npoints(&ret->params, n); + + sg_snuggle(ret); /* shifts blanks down and to the left */ + sg_check(ret); /* checks for completeness or impossibility */ + + return ret; + } else + return NULL; /* couldn't parse move string */ +} + +/* ---------------------------------------------------------------------- + * Drawing routines. + */ + +static void game_set_size(drawing *dr, game_drawstate *ds, + const game_params *params, int tilesize) +{ + ds->tilegap = 2; + ds->tileinner = tilesize - ds->tilegap; +} + +static void game_compute_size(const game_params *params, int tilesize, + int *x, int *y) +{ + /* Ick: fake up tile size variables for macro expansion purposes */ + game_drawstate ads, *ds = &ads; + game_set_size(NULL, ds, params, tilesize); + + *x = TILE_SIZE * params->w + 2 * BORDER - TILE_GAP; + *y = TILE_SIZE * params->h + 2 * BORDER - TILE_GAP; +} + +static float *game_colours(frontend *fe, int *ncolours) +{ + float *ret = snewn(3 * NCOLOURS, float); + + frontend_default_colour(fe, &ret[COL_BACKGROUND * 3]); + + ret[COL_1 * 3 + 0] = 0.0F; + ret[COL_1 * 3 + 1] = 0.0F; + ret[COL_1 * 3 + 2] = 1.0F; + + ret[COL_2 * 3 + 0] = 0.0F; + ret[COL_2 * 3 + 1] = 0.5F; + ret[COL_2 * 3 + 2] = 0.0F; + + ret[COL_3 * 3 + 0] = 1.0F; + ret[COL_3 * 3 + 1] = 0.0F; + ret[COL_3 * 3 + 2] = 0.0F; + + ret[COL_4 * 3 + 0] = 1.0F; + ret[COL_4 * 3 + 1] = 1.0F; + ret[COL_4 * 3 + 2] = 0.0F; + + ret[COL_5 * 3 + 0] = 1.0F; + ret[COL_5 * 3 + 1] = 0.0F; + ret[COL_5 * 3 + 2] = 1.0F; + + ret[COL_6 * 3 + 0] = 0.0F; + ret[COL_6 * 3 + 1] = 1.0F; + ret[COL_6 * 3 + 2] = 1.0F; + + ret[COL_7 * 3 + 0] = 0.5F; + ret[COL_7 * 3 + 1] = 0.5F; + ret[COL_7 * 3 + 2] = 1.0F; + + ret[COL_8 * 3 + 0] = 0.5F; + ret[COL_8 * 3 + 1] = 1.0F; + ret[COL_8 * 3 + 2] = 0.5F; + + ret[COL_9 * 3 + 0] = 1.0F; + ret[COL_9 * 3 + 1] = 0.5F; + ret[COL_9 * 3 + 2] = 0.5F; + + ret[COL_IMPOSSIBLE * 3 + 0] = 0.0F; + ret[COL_IMPOSSIBLE * 3 + 1] = 0.0F; + ret[COL_IMPOSSIBLE * 3 + 2] = 0.0F; + + ret[COL_SEL * 3 + 0] = 1.0F; + ret[COL_SEL * 3 + 1] = 1.0F; + ret[COL_SEL * 3 + 2] = 1.0F; + + ret[COL_HIGHLIGHT * 3 + 0] = 1.0F; + ret[COL_HIGHLIGHT * 3 + 1] = 1.0F; + ret[COL_HIGHLIGHT * 3 + 2] = 1.0F; + + ret[COL_LOWLIGHT * 3 + 0] = ret[COL_BACKGROUND * 3 + 0] * 2.0F / 3.0F; + ret[COL_LOWLIGHT * 3 + 1] = ret[COL_BACKGROUND * 3 + 1] * 2.0F / 3.0F; + ret[COL_LOWLIGHT * 3 + 2] = ret[COL_BACKGROUND * 3 + 2] * 2.0F / 3.0F; + + *ncolours = NCOLOURS; + return ret; +} + +static game_drawstate *game_new_drawstate(drawing *dr, const game_state *state) +{ + struct game_drawstate *ds = snew(struct game_drawstate); + int i; + + ds->started = 0; + ds->tileinner = ds->tilegap = 0; /* not decided yet */ + ds->tiles = snewn(state->n, int); + ds->bgcolour = -1; + for (i = 0; i < state->n; i++) + ds->tiles[i] = -1; + + return ds; +} + +static void game_free_drawstate(drawing *dr, game_drawstate *ds) +{ + sfree(ds->tiles); + sfree(ds); +} + +/* Drawing routing for the tile at (x,y) is responsible for drawing + * itself and the gaps to its right and below. If we're the same colour + * as the tile to our right, then we fill in the gap; ditto below, and if + * both then we fill the teeny tiny square in the corner as well. + */ + +static void tile_redraw(drawing *dr, game_drawstate *ds, + int x, int y, int dright, int dbelow, + int tile, int bgcolour) +{ + int outer = bgcolour, inner = outer, col = tile & TILE_COLMASK; + + if (col) { + if (tile & TILE_IMPOSSIBLE) { + outer = col; + inner = COL_IMPOSSIBLE; + } else if (tile & TILE_SELECTED) { + outer = COL_SEL; + inner = col; + } else { + outer = inner = col; + } + } + draw_rect(dr, COORD(x), COORD(y), TILE_INNER, TILE_INNER, outer); + draw_rect(dr, COORD(x)+TILE_INNER/4, COORD(y)+TILE_INNER/4, + TILE_INNER/2, TILE_INNER/2, inner); + + if (dright) + draw_rect(dr, COORD(x)+TILE_INNER, COORD(y), TILE_GAP, TILE_INNER, + (tile & TILE_JOINRIGHT) ? outer : bgcolour); + if (dbelow) + draw_rect(dr, COORD(x), COORD(y)+TILE_INNER, TILE_INNER, TILE_GAP, + (tile & TILE_JOINDOWN) ? outer : bgcolour); + if (dright && dbelow) + draw_rect(dr, COORD(x)+TILE_INNER, COORD(y)+TILE_INNER, TILE_GAP, TILE_GAP, + (tile & TILE_JOINDIAG) ? outer : bgcolour); + + if (tile & TILE_HASSEL) { + int sx = COORD(x)+2, sy = COORD(y)+2, ssz = TILE_INNER-5; + int scol = (outer == COL_SEL) ? COL_LOWLIGHT : COL_HIGHLIGHT; + draw_line(dr, sx, sy, sx+ssz, sy, scol); + draw_line(dr, sx+ssz, sy, sx+ssz, sy+ssz, scol); + draw_line(dr, sx+ssz, sy+ssz, sx, sy+ssz, scol); + draw_line(dr, sx, sy+ssz, sx, sy, scol); + } + + draw_update(dr, COORD(x), COORD(y), TILE_SIZE, TILE_SIZE); +} + +static void game_redraw(drawing *dr, game_drawstate *ds, + const game_state *oldstate, const game_state *state, + int dir, const game_ui *ui, + float animtime, float flashtime) +{ + int bgcolour, x, y; + + /* This was entirely cloned from fifteen.c; it should probably be + * moved into some generic 'draw-recessed-rectangle' utility fn. */ + if (!ds->started) { + int coords[10]; + + draw_rect(dr, 0, 0, + TILE_SIZE * state->params.w + 2 * BORDER, + TILE_SIZE * state->params.h + 2 * BORDER, COL_BACKGROUND); + draw_update(dr, 0, 0, + TILE_SIZE * state->params.w + 2 * BORDER, + TILE_SIZE * state->params.h + 2 * BORDER); + + /* + * Recessed area containing the whole puzzle. + */ + coords[0] = COORD(state->params.w) + HIGHLIGHT_WIDTH - 1 - TILE_GAP; + coords[1] = COORD(state->params.h) + HIGHLIGHT_WIDTH - 1 - TILE_GAP; + coords[2] = COORD(state->params.w) + HIGHLIGHT_WIDTH - 1 - TILE_GAP; + coords[3] = COORD(0) - HIGHLIGHT_WIDTH; + coords[4] = coords[2] - TILE_SIZE; + coords[5] = coords[3] + TILE_SIZE; + coords[8] = COORD(0) - HIGHLIGHT_WIDTH; + coords[9] = COORD(state->params.h) + HIGHLIGHT_WIDTH - 1 - TILE_GAP; + coords[6] = coords[8] + TILE_SIZE; + coords[7] = coords[9] - TILE_SIZE; + draw_polygon(dr, coords, 5, COL_HIGHLIGHT, COL_HIGHLIGHT); + + coords[1] = COORD(0) - HIGHLIGHT_WIDTH; + coords[0] = COORD(0) - HIGHLIGHT_WIDTH; + draw_polygon(dr, coords, 5, COL_LOWLIGHT, COL_LOWLIGHT); + + ds->started = 1; + } + + if (flashtime > 0.0) { + int frame = (int)(flashtime / FLASH_FRAME); + bgcolour = (frame % 2 ? COL_LOWLIGHT : COL_HIGHLIGHT); + } else + bgcolour = COL_BACKGROUND; + + for (x = 0; x < state->params.w; x++) { + for (y = 0; y < state->params.h; y++) { + int i = (state->params.w * y) + x; + int col = COL(state,x,y), tile = col; + int dright = (x+1 < state->params.w); + int dbelow = (y+1 < state->params.h); + + tile |= ISSEL(ui,x,y); + if (state->impossible) + tile |= TILE_IMPOSSIBLE; + if (dright && COL(state,x+1,y) == col) + tile |= TILE_JOINRIGHT; + if (dbelow && COL(state,x,y+1) == col) + tile |= TILE_JOINDOWN; + if ((tile & TILE_JOINRIGHT) && (tile & TILE_JOINDOWN) && + COL(state,x+1,y+1) == col) + tile |= TILE_JOINDIAG; + + if (ui->displaysel && ui->xsel == x && ui->ysel == y) + tile |= TILE_HASSEL; + + /* For now we're never expecting oldstate at all (because we have + * no animation); when we do we might well want to be looking + * at the tile colours from oldstate, not state. */ + if ((oldstate && COL(oldstate,x,y) != col) || + (ds->bgcolour != bgcolour) || + (tile != ds->tiles[i])) { + tile_redraw(dr, ds, x, y, dright, dbelow, tile, bgcolour); + ds->tiles[i] = tile; + } + } + } + ds->bgcolour = bgcolour; + + { + char status[255], score[80]; + + sprintf(score, "Score: %d", state->score); + + if (state->complete) + sprintf(status, "COMPLETE! %s", score); + else if (state->impossible) + sprintf(status, "Cannot move! %s", score); + else if (ui->nselected) + sprintf(status, "%s Selected: %d (%d)", + score, ui->nselected, npoints(&state->params, ui->nselected)); + else + sprintf(status, "%s", score); + status_bar(dr, status); + } +} + +static float game_anim_length(const game_state *oldstate, + const game_state *newstate, int dir, game_ui *ui) +{ + return 0.0F; +} + +static float game_flash_length(const game_state *oldstate, + const game_state *newstate, int dir, game_ui *ui) +{ + if ((!oldstate->complete && newstate->complete) || + (!oldstate->impossible && newstate->impossible)) + return 2 * FLASH_FRAME; + else + return 0.0F; +} + +static int game_status(const game_state *state) +{ + /* + * Dead-end situations are assumed to be rescuable by Undo, so we + * don't bother to identify them and return -1. + */ + return state->complete ? +1 : 0; +} + +static int game_timing_state(const game_state *state, game_ui *ui) +{ + return TRUE; +} + +static void game_print_size(const game_params *params, float *x, float *y) +{ +} + +static void game_print(drawing *dr, const game_state *state, int tilesize) +{ +} + +#ifdef COMBINED +#define thegame samegame +#endif + +const struct game thegame = { + "Same Game", "games.samegame", "samegame", + default_params, + game_fetch_preset, NULL, + decode_params, + encode_params, + free_params, + dup_params, + TRUE, game_configure, custom_params, + validate_params, + new_game_desc, + validate_desc, + new_game, + dup_game, + free_game, + FALSE, solve_game, + TRUE, game_can_format_as_text_now, game_text_format, + new_ui, + free_ui, + encode_ui, + decode_ui, + game_changed_state, + interpret_move, + execute_move, + PREFERRED_TILE_SIZE, game_compute_size, game_set_size, + game_colours, + game_new_drawstate, + game_free_drawstate, + game_redraw, + game_anim_length, + game_flash_length, + game_status, + FALSE, FALSE, game_print_size, game_print, + TRUE, /* wants_statusbar */ + FALSE, game_timing_state, + 0, /* flags */ +}; -- cgit v1.2.3