X-Git-Url: https://git.distorted.org.uk/~mdw/sgt/puzzles/blobdiff_plain/f3cc3e50490f3409b85f805dae9872e09f42bd7d..HEAD:/samegame.c diff --git a/samegame.c b/samegame.c index 572e3c3..65ebef7 100644 --- a/samegame.c +++ b/samegame.c @@ -3,6 +3,65 @@ * 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 @@ -38,6 +97,7 @@ enum { /* 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, @@ -49,6 +109,7 @@ struct game_params { #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) @@ -81,15 +142,20 @@ static game_params *default_params(void) 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 }, - { 10, 5, 3, 2 }, - { 15, 10, 3, 2 }, - { 15, 10, 4, 2 }, - { 20, 15, 4, 2 } + { 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) @@ -135,26 +201,33 @@ static void decode_params(game_params *params, char const *string) } else { params->h = params->w; } - if (*p++ == 'c') { + if (*p == 'c') { + p++; params->ncols = atoi(p); while (*p && isdigit((unsigned char)*p)) p++; } else { params->ncols = 3; } - if (*p++ == 's') { + 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(game_params *params, int full) { char ret[80]; - sprintf(ret, "%dx%dc%ds%d", - params->w, params->h, params->ncols, params->scoresub); + sprintf(ret, "%dx%dc%ds%d%s", + params->w, params->h, params->ncols, params->scoresub, + full && !params->soluble ? "r" : ""); return dupstr(ret); } @@ -163,7 +236,7 @@ static config_item *game_configure(game_params *params) config_item *ret; char buf[80]; - ret = snewn(5, config_item); + ret = snewn(6, config_item); ret[0].name = "Width"; ret[0].type = C_STRING; @@ -188,10 +261,15 @@ static config_item *game_configure(game_params *params) ret[3].sval = ":(n-1)^2:(n-2)^2"; ret[3].ival = params->scoresub-1; - ret[4].name = NULL; - ret[4].type = C_END; + ret[4].name = "Ensure solubility"; + ret[4].type = C_BOOLEAN; ret[4].sval = NULL; - ret[4].ival = 0; + ret[4].ival = params->soluble; + + ret[5].name = NULL; + ret[5].type = C_END; + ret[5].sval = NULL; + ret[5].ival = 0; return ret; } @@ -204,23 +282,32 @@ static game_params *custom_params(config_item *cfg) 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(game_params *params) +static char *validate_params(game_params *params, int full) { if (params->w < 1 || params->h < 1) return "Width and height must both be positive"; - if (params->ncols < 2) - return "It's too easy with only one colour..."; + if (params->ncols > 9) return "Maximum of 9 colours"; - /* ...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->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"; @@ -228,43 +315,621 @@ static char *validate_params(game_params *params) return NULL; } -/* Currently this is a very very dumb game-generation engine; it - * just picks randomly from the tile space. I had a look at a few - * other same game implementations, and none of them attempt to do - * anything to try and make sure the grid started off with a nice - * set of large blocks. - * - * It does at least make sure that there are >= 2 of each colour - * present at the start. +/* + * 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; -static char *new_game_desc(game_params *params, random_state *rs, - game_aux_info **aux, int interactive) + /* + * 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) { - char *ret; - int n, i, j, c, retlen, *tiles; + int i, j, c; + int n = w * h; - debug(("new_game_desc: %dx%d, %d colours", - params->w, params->h, params->ncols)); - n = params->w * params->h; - tiles = snewn(n, int); - memset(tiles, 0, n*sizeof(int)); + for (i = 0; i < n; i++) + grid[i] = 0; - /* randomly place two of each colour */ - for (c = 0; c < params->ncols; c++) { + /* + * 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 (tiles[i] != 0); - tiles[i] = c+1; + } while (grid[i] != 0); + grid[i] = c; } } - /* fill in the rest randomly */ + /* + * Fill in the rest of the grid at random. + */ for (i = 0; i < n; i++) { - if (tiles[i] == 0) - tiles[i] = (int)random_upto(rs, params->ncols)+1; + if (grid[i] == 0) + grid[i] = (int)random_upto(rs, nc)+1; } +} + +static char *new_game_desc(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; @@ -283,11 +948,6 @@ static char *new_game_desc(game_params *params, random_state *rs, return ret; } -static void game_free_aux_info(game_aux_info *aux) -{ - assert(!"Shouldn't happen"); -} - static char *validate_desc(game_params *params, char *desc) { int area = params->w * params->h, i; @@ -297,9 +957,9 @@ static char *validate_desc(game_params *params, char *desc) char *q = p; int n; - if (!isdigit(*p)) + if (!isdigit((unsigned char)*p)) return "Not enough numbers in string"; - while (isdigit(*p)) p++; + while (isdigit((unsigned char)*p)) p++; if (i < area-1 && *p != ',') return "Expected comma after number"; @@ -315,7 +975,7 @@ static char *validate_desc(game_params *params, char *desc) return NULL; } -static game_state *new_game(midend_data *me, game_params *params, char *desc) +static game_state *new_game(midend *me, game_params *params, char *desc) { game_state *state = snew(game_state); char *p = desc; @@ -356,12 +1016,17 @@ static void free_game(game_state *state) sfree(state); } -static game_state *solve_game(game_state *state, game_aux_info *aux, - char **error) +static char *solve_game(game_state *state, game_state *currstate, + char *aux, char **error) { return NULL; } +static int game_can_format_as_text_now(game_params *params) +{ + return TRUE; +} + static char *game_text_format(game_state *state) { char *ret, *p; @@ -412,6 +1077,15 @@ static void free_ui(game_ui *ui) sfree(ui); } +static char *encode_ui(game_ui *ui) +{ + return NULL; +} + +static void decode_ui(game_ui *ui, char *encoding) +{ +} + static void sel_clear(game_ui *ui, game_state *state) { int i; @@ -419,7 +1093,6 @@ static void sel_clear(game_ui *ui, game_state *state) for (i = 0; i < state->n; i++) ui->tiles[i] &= ~TILE_SELECTED; ui->nselected = 0; - debug(("sel_clear")); } @@ -427,23 +1100,47 @@ static void game_changed_state(game_ui *ui, game_state *oldstate, 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 void sel_remove(game_ui *ui, game_state *state) +static char *sel_movedesc(game_ui *ui, game_state *state) { - int i, nremoved = 0; + int i; + char *ret, *sep, buf[80]; + int retlen, retsize; - state->score += npoints(&state->params, ui->nselected); + 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) { - nremoved++; - state->tiles[i] = 0; + 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; - debug(("sel_remove: removed %d selected tiles", nremoved)); + + assert(retlen < retsize); + ret[retlen++] = '\0'; + return sresize(ret, retlen, char); } static void sel_expand(game_ui *ui, game_state *state, int tx, int ty) @@ -451,7 +1148,6 @@ static void sel_expand(game_ui *ui, game_state *state, int tx, int ty) int ns = 1, nadded, x, y, c; TILE(ui,tx,ty) |= TILE_SELECTED; - debug(("sel_expand, selected initial tile")); do { nadded = 0; @@ -491,7 +1187,6 @@ static void sel_expand(game_ui *ui, game_state *state, int tx, int ty) } } ns += nadded; - debug(("sel_expand, new pass, selected %d more tiles", nadded)); } while (nadded > 0); if (ns > 1) { @@ -534,7 +1229,6 @@ static void sg_snuggle(game_state *ret) ndone = 0; for (x = 0; x < ret->params.w-1; x++) { if (sg_emptycol(ret,x) && !sg_emptycol(ret,x+1)) { - debug(("column %d is empty, shuffling from %d", x, x+1)); ndone++; for (y = 0; y < ret->params.h; y++) { SWAPTILE(ret,x,y,x+1,y); @@ -573,99 +1267,105 @@ struct game_drawstate { int *tiles; /* contains colour and SELECTED. */ }; -static game_state *make_move(game_state *from, game_ui *ui, game_drawstate *ds, - int x, int y, int button) +static char *interpret_move(game_state *state, game_ui *ui, const game_drawstate *ds, + int x, int y, int button) { int tx, ty; - game_state *ret = from; + char *ret = ""; ui->displaysel = 0; if (button == RIGHT_BUTTON || button == LEFT_BUTTON) { tx = FROMCOORD(x); ty= FROMCOORD(y); - } else if (button == CURSOR_UP || button == CURSOR_DOWN || - button == CURSOR_LEFT || button == CURSOR_RIGHT) { + } 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 + from->params.w + dx) % from->params.w; - ui->ysel = (ui->ysel + from->params.h + dy) % from->params.h; - debug(("cursor pressed, d=(%d,%d), sel=(%d,%d)",dx,dy,ui->xsel,ui->ysel)); + 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 (button == CURSOR_SELECT || button == ' ' || button == '\r' || - button == '\n') { + } else if (IS_CURSOR_SELECT(button)) { ui->displaysel = 1; tx = ui->xsel; ty = ui->ysel; - debug(("cursor select, t=(%d,%d)", tx, ty)); } else return NULL; - if (tx < 0 || tx >= from->params.w || ty < 0 || ty >= from->params.h) + if (tx < 0 || tx >= state->params.w || ty < 0 || ty >= state->params.h) return NULL; - if (COL(from, tx, ty) == 0) return NULL; + if (COL(state, tx, ty) == 0) return NULL; if (ISSEL(ui,tx,ty)) { - if (button == RIGHT_BUTTON) - sel_clear(ui, from); - else { - /* this is the actual move. */ - ret = dup_game(from); - sel_remove(ui, ret); - sg_snuggle(ret); /* shifts blanks down and to the left */ - sg_check(ret); /* checks for completeness or impossibility */ - } + if (button == RIGHT_BUTTON || button == CURSOR_SELECT2) + sel_clear(ui, state); + else + ret = sel_movedesc(ui, state); } else { - sel_clear(ui, from); /* might be no-op */ - sel_expand(ui, from, tx, ty); + sel_clear(ui, state); /* might be no-op */ + sel_expand(ui, state, tx, ty); } - if (ret->complete || ret->impossible) - ui->displaysel = 0; return ret; } +static game_state *execute_move(game_state *from, 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_size(game_params *params, game_drawstate *ds, int *x, int *y, - int expand) +static void game_set_size(drawing *dr, game_drawstate *ds, + game_params *params, int tilesize) { - int tsx, tsy, ts; - - /* - * We could choose the tile gap dynamically as well if we - * wanted to; for example, at low tile sizes it might be - * sensible to leave it out completely. However, for the moment - * and for the sake of simplicity I'm just going to fix it at - * 2. - */ ds->tilegap = 2; + ds->tileinner = tilesize - ds->tilegap; +} - /* - * Each window dimension equals the tile size (inner plus gap) - * times the grid dimension, plus another tile size (border is - * half the width of a tile), minus one tile gap. - * - * We must cast to unsigned before adding to *x and *y, since - * they might be INT_MAX! - */ - tsx = (unsigned)(*x + ds->tilegap) / (params->w + 1); - tsy = (unsigned)(*y + ds->tilegap) / (params->h + 1); - - ts = min(tsx, tsy); - if (expand) - ds->tileinner = ts - ds->tilegap; - else - ds->tileinner = min(ts, PREFERRED_TILE_SIZE) - ds->tilegap; +static void game_compute_size(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, game_state *state, int *ncolours) +static float *game_colours(frontend *fe, int *ncolours) { float *ret = snewn(3 * NCOLOURS, float); @@ -683,29 +1383,29 @@ static float *game_colours(frontend *fe, game_state *state, int *ncolours) ret[COL_3 * 3 + 1] = 0.0F; ret[COL_3 * 3 + 2] = 0.0F; - ret[COL_4 * 3 + 0] = 0.5F; - ret[COL_4 * 3 + 1] = 0.5F; - ret[COL_4 * 3 + 2] = 1.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] = 0.5F; - ret[COL_5 * 3 + 1] = 1.0F; - ret[COL_5 * 3 + 2] = 0.5F; + 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] = 1.0F; - ret[COL_6 * 3 + 1] = 0.5F; - ret[COL_6 * 3 + 2] = 0.5F; + 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] = 1.0F; - ret[COL_7 * 3 + 1] = 1.0F; - ret[COL_7 * 3 + 2] = 0.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] = 1.0F; - ret[COL_8 * 3 + 1] = 0.0F; - ret[COL_8 * 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] = 0.0F; - ret[COL_9 * 3 + 1] = 1.0F; - ret[COL_9 * 3 + 2] = 1.0F; + 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; @@ -719,15 +1419,15 @@ static float *game_colours(frontend *fe, game_state *state, int *ncolours) 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.0 / 3.0; - ret[COL_LOWLIGHT * 3 + 1] = ret[COL_BACKGROUND * 3 + 1] * 2.0 / 3.0; - ret[COL_LOWLIGHT * 3 + 2] = ret[COL_BACKGROUND * 3 + 2] * 2.0 / 3.0; + 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(game_state *state) +static game_drawstate *game_new_drawstate(drawing *dr, game_state *state) { struct game_drawstate *ds = snew(struct game_drawstate); int i; @@ -735,13 +1435,14 @@ static game_drawstate *game_new_drawstate(game_state *state) 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(game_drawstate *ds) +static void game_free_drawstate(drawing *dr, game_drawstate *ds) { sfree(ds->tiles); sfree(ds); @@ -753,14 +1454,14 @@ static void game_free_drawstate(game_drawstate *ds) * both then we fill the teeny tiny square in the corner as well. */ -static void tile_redraw(frontend *fe, game_drawstate *ds, +static void tile_redraw(drawing *dr, game_drawstate *ds, int x, int y, int dright, int dbelow, - int tile, game_state *state, int bgcolour) + int tile, int bgcolour) { int outer = bgcolour, inner = outer, col = tile & TILE_COLMASK; if (col) { - if (state->impossible) { + if (tile & TILE_IMPOSSIBLE) { outer = col; inner = COL_IMPOSSIBLE; } else if (tile & TILE_SELECTED) { @@ -770,50 +1471,47 @@ static void tile_redraw(frontend *fe, game_drawstate *ds, outer = inner = col; } } - draw_rect(fe, COORD(x), COORD(y), TILE_INNER, TILE_INNER, outer); - draw_rect(fe, COORD(x)+TILE_INNER/4, COORD(y)+TILE_INNER/4, + 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(fe, COORD(x)+TILE_INNER, COORD(y), TILE_GAP, TILE_INNER, + draw_rect(dr, COORD(x)+TILE_INNER, COORD(y), TILE_GAP, TILE_INNER, (tile & TILE_JOINRIGHT) ? outer : bgcolour); if (dbelow) - draw_rect(fe, COORD(x), COORD(y)+TILE_INNER, TILE_INNER, TILE_GAP, + draw_rect(dr, COORD(x), COORD(y)+TILE_INNER, TILE_INNER, TILE_GAP, (tile & TILE_JOINDOWN) ? outer : bgcolour); if (dright && dbelow) - draw_rect(fe, COORD(x)+TILE_INNER, COORD(y)+TILE_INNER, TILE_GAP, TILE_GAP, + 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(fe, sx, sy, sx+ssz, sy, scol); - draw_line(fe, sx+ssz, sy, sx+ssz, sy+ssz, scol); - draw_line(fe, sx+ssz, sy+ssz, sx, sy+ssz, scol); - draw_line(fe, sx, sy+ssz, sx, sy, scol); + 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(fe, COORD(x), COORD(y), TILE_SIZE, TILE_SIZE); + draw_update(dr, COORD(x), COORD(y), TILE_SIZE, TILE_SIZE); } -static void game_redraw(frontend *fe, game_drawstate *ds, game_state *oldstate, +static void game_redraw(drawing *dr, game_drawstate *ds, game_state *oldstate, game_state *state, int dir, game_ui *ui, float animtime, float flashtime) { int bgcolour, x, y; - debug(("samegame redraw: dir %d, oldstate 0x%lx, animtime %f, flashtime %f", - dir, oldstate, animtime, flashtime)); - /* 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(fe, 0, 0, + draw_rect(dr, 0, 0, TILE_SIZE * state->params.w + 2 * BORDER, TILE_SIZE * state->params.h + 2 * BORDER, COL_BACKGROUND); - draw_update(fe, 0, 0, + draw_update(dr, 0, 0, TILE_SIZE * state->params.w + 2 * BORDER, TILE_SIZE * state->params.h + 2 * BORDER); @@ -830,13 +1528,11 @@ static void game_redraw(frontend *fe, game_drawstate *ds, game_state *oldstate, 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(fe, coords, 5, TRUE, COL_HIGHLIGHT); - draw_polygon(fe, coords, 5, FALSE, COL_HIGHLIGHT); + draw_polygon(dr, coords, 5, COL_HIGHLIGHT, COL_HIGHLIGHT); coords[1] = COORD(0) - HIGHLIGHT_WIDTH; coords[0] = COORD(0) - HIGHLIGHT_WIDTH; - draw_polygon(fe, coords, 5, TRUE, COL_LOWLIGHT); - draw_polygon(fe, coords, 5, FALSE, COL_LOWLIGHT); + draw_polygon(dr, coords, 5, COL_LOWLIGHT, COL_LOWLIGHT); ds->started = 1; } @@ -855,6 +1551,8 @@ static void game_redraw(frontend *fe, game_drawstate *ds, game_state *oldstate, 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) @@ -870,11 +1568,9 @@ static void game_redraw(frontend *fe, game_drawstate *ds, game_state *oldstate, * 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) || - (flashtime > 0.0) || (ds->bgcolour != bgcolour) || (tile != ds->tiles[i])) { - tile_redraw(fe, ds, x, y, dright, dbelow, - tile, state, bgcolour); + tile_redraw(dr, ds, x, y, dright, dbelow, tile, bgcolour); ds->tiles[i] = tile; } } @@ -895,7 +1591,7 @@ static void game_redraw(frontend *fe, game_drawstate *ds, game_state *oldstate, score, ui->nselected, npoints(&state->params, ui->nselected)); else sprintf(status, "%s", score); - status_bar(fe, status); + status_bar(dr, status); } } @@ -915,22 +1611,34 @@ static float game_flash_length(game_state *oldstate, game_state *newstate, return 0.0F; } -static int game_wants_statusbar(void) +static int game_status(game_state *state) { - return TRUE; + /* + * 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(game_state *state) +static int game_timing_state(game_state *state, game_ui *ui) { return TRUE; } +static void game_print_size(game_params *params, float *x, float *y) +{ +} + +static void game_print(drawing *dr, game_state *state, int tilesize) +{ +} + #ifdef COMBINED #define thegame samegame #endif const struct game thegame = { - "Same Game", "games.samegame", + "Same Game", "games.samegame", "samegame", default_params, game_fetch_preset, decode_params, @@ -940,25 +1648,29 @@ const struct game thegame = { TRUE, game_configure, custom_params, validate_params, new_game_desc, - game_free_aux_info, validate_desc, new_game, dup_game, free_game, FALSE, solve_game, - TRUE, game_text_format, + TRUE, game_can_format_as_text_now, game_text_format, new_ui, free_ui, + encode_ui, + decode_ui, game_changed_state, - make_move, - game_size, + 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_wants_statusbar, + game_status, + FALSE, FALSE, game_print_size, game_print, + TRUE, /* wants_statusbar */ FALSE, game_timing_state, - 0, /* mouse_priorities */ + 0, /* flags */ };