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/flip.c | 1349 +++++++++++++++++++++++++++++++++++++++ 1 file changed, 1349 insertions(+) create mode 100644 apps/plugins/puzzles/src/flip.c (limited to 'apps/plugins/puzzles/src/flip.c') diff --git a/apps/plugins/puzzles/src/flip.c b/apps/plugins/puzzles/src/flip.c new file mode 100644 index 0000000000..c7126fb7d9 --- /dev/null +++ b/apps/plugins/puzzles/src/flip.c @@ -0,0 +1,1349 @@ +/* + * flip.c: Puzzle involving lighting up all the squares on a grid, + * where each click toggles an overlapping set of lights. + */ + +#include +#include +#include +#include +#include +#include + +#include "puzzles.h" +#include "tree234.h" + +enum { + COL_BACKGROUND, + COL_WRONG, + COL_RIGHT, + COL_GRID, + COL_DIAG, + COL_HINT, + COL_CURSOR, + NCOLOURS +}; + +#define PREFERRED_TILE_SIZE 48 +#define TILE_SIZE (ds->tilesize) +#define BORDER (TILE_SIZE / 2) +#define COORD(x) ( (x) * TILE_SIZE + BORDER ) +#define FROMCOORD(x) ( ((x) - BORDER + TILE_SIZE) / TILE_SIZE - 1 ) + +#define ANIM_TIME 0.25F +#define FLASH_FRAME 0.07F + +/* + * Possible ways to decide which lights are toggled by each click. + * Essentially, each of these describes a means of inventing a + * matrix over GF(2). + */ +enum { + CROSSES, RANDOM +}; + +struct game_params { + int w, h; + int matrix_type; +}; + +/* + * This structure is shared between all the game_states describing + * a particular game, so it's reference-counted. + */ +struct matrix { + int refcount; + unsigned char *matrix; /* array of (w*h) by (w*h) */ +}; + +struct game_state { + int w, h; + int moves, completed, cheated, hints_active; + unsigned char *grid; /* array of w*h */ + struct matrix *matrix; +}; + +static game_params *default_params(void) +{ + game_params *ret = snew(game_params); + + ret->w = ret->h = 5; + ret->matrix_type = CROSSES; + + return ret; +} + +static const struct game_params flip_presets[] = { + {3, 3, CROSSES}, + {4, 4, CROSSES}, + {5, 5, CROSSES}, + {3, 3, RANDOM}, + {4, 4, RANDOM}, + {5, 5, RANDOM}, +}; + +static int game_fetch_preset(int i, char **name, game_params **params) +{ + game_params *ret; + char str[80]; + + if (i < 0 || i >= lenof(flip_presets)) + return FALSE; + + ret = snew(game_params); + *ret = flip_presets[i]; + + sprintf(str, "%dx%d %s", ret->w, ret->h, + ret->matrix_type == CROSSES ? "Crosses" : "Random"); + + *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 *ret, char const *string) +{ + ret->w = ret->h = atoi(string); + while (*string && isdigit((unsigned char)*string)) string++; + if (*string == 'x') { + string++; + ret->h = atoi(string); + while (*string && isdigit((unsigned char)*string)) string++; + } + if (*string == 'r') { + string++; + ret->matrix_type = RANDOM; + } else if (*string == 'c') { + string++; + ret->matrix_type = CROSSES; + } +} + +static char *encode_params(const game_params *params, int full) +{ + char data[256]; + + sprintf(data, "%dx%d%s", params->w, params->h, + !full ? "" : params->matrix_type == CROSSES ? "c" : "r"); + + return dupstr(data); +} + +static config_item *game_configure(const game_params *params) +{ + config_item *ret = snewn(4, config_item); + char buf[80]; + + 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 = "Shape type"; + ret[2].type = C_CHOICES; + ret[2].sval = ":Crosses:Random"; + ret[2].ival = params->matrix_type; + + ret[3].name = NULL; + ret[3].type = C_END; + ret[3].sval = NULL; + ret[3].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->matrix_type = cfg[2].ival; + + return ret; +} + +static char *validate_params(const game_params *params, int full) +{ + if (params->w <= 0 || params->h <= 0) + return "Width and height must both be greater than zero"; + return NULL; +} + +static char *encode_bitmap(unsigned char *bmp, int len) +{ + int slen = (len + 3) / 4; + char *ret; + int i; + + ret = snewn(slen + 1, char); + for (i = 0; i < slen; i++) { + int j, v; + v = 0; + for (j = 0; j < 4; j++) + if (i*4+j < len && bmp[i*4+j]) + v |= 8 >> j; + ret[i] = "0123456789abcdef"[v]; + } + ret[slen] = '\0'; + return ret; +} + +static void decode_bitmap(unsigned char *bmp, int len, const char *hex) +{ + int slen = (len + 3) / 4; + int i; + + for (i = 0; i < slen; i++) { + int j, v, c = hex[i]; + if (c >= '0' && c <= '9') + v = c - '0'; + else if (c >= 'A' && c <= 'F') + v = c - 'A' + 10; + else if (c >= 'a' && c <= 'f') + v = c - 'a' + 10; + else + v = 0; /* shouldn't happen */ + for (j = 0; j < 4; j++) { + if (i*4+j < len) { + if (v & (8 >> j)) + bmp[i*4+j] = 1; + else + bmp[i*4+j] = 0; + } + } + } +} + +/* + * Structure used during random matrix generation, and a compare + * function to permit storage in a tree234. + */ +struct sq { + int cx, cy; /* coords of click square */ + int x, y; /* coords of output square */ + /* + * Number of click squares which currently affect this output + * square. + */ + int coverage; + /* + * Number of output squares currently affected by this click + * square. + */ + int ominosize; +}; +#define SORT(field) do { \ + if (a->field < b->field) \ + return -1; \ + else if (a->field > b->field) \ + return +1; \ +} while (0) +/* + * Compare function for choosing the next square to add. We must + * sort by coverage, then by omino size, then everything else. + */ +static int sqcmp_pick(void *av, void *bv) +{ + struct sq *a = (struct sq *)av; + struct sq *b = (struct sq *)bv; + SORT(coverage); + SORT(ominosize); + SORT(cy); + SORT(cx); + SORT(y); + SORT(x); + return 0; +} +/* + * Compare function for adjusting the coverage figures after a + * change. We sort first by coverage and output square, then by + * everything else. + */ +static int sqcmp_cov(void *av, void *bv) +{ + struct sq *a = (struct sq *)av; + struct sq *b = (struct sq *)bv; + SORT(coverage); + SORT(y); + SORT(x); + SORT(ominosize); + SORT(cy); + SORT(cx); + return 0; +} +/* + * Compare function for adjusting the omino sizes after a change. + * We sort first by omino size and input square, then by everything + * else. + */ +static int sqcmp_osize(void *av, void *bv) +{ + struct sq *a = (struct sq *)av; + struct sq *b = (struct sq *)bv; + SORT(ominosize); + SORT(cy); + SORT(cx); + SORT(coverage); + SORT(y); + SORT(x); + return 0; +} +static void addsq(tree234 *t, int w, int h, int cx, int cy, + int x, int y, unsigned char *matrix) +{ + int wh = w * h; + struct sq *sq; + int i; + + if (x < 0 || x >= w || y < 0 || y >= h) + return; + if (abs(x-cx) > 1 || abs(y-cy) > 1) + return; + if (matrix[(cy*w+cx) * wh + y*w+x]) + return; + + sq = snew(struct sq); + sq->cx = cx; + sq->cy = cy; + sq->x = x; + sq->y = y; + sq->coverage = sq->ominosize = 0; + for (i = 0; i < wh; i++) { + if (matrix[i * wh + y*w+x]) + sq->coverage++; + if (matrix[(cy*w+cx) * wh + i]) + sq->ominosize++; + } + + if (add234(t, sq) != sq) + sfree(sq); /* already there */ +} +static void addneighbours(tree234 *t, int w, int h, int cx, int cy, + int x, int y, unsigned char *matrix) +{ + addsq(t, w, h, cx, cy, x-1, y, matrix); + addsq(t, w, h, cx, cy, x+1, y, matrix); + addsq(t, w, h, cx, cy, x, y-1, matrix); + addsq(t, w, h, cx, cy, x, y+1, matrix); +} + +static char *new_game_desc(const game_params *params, random_state *rs, + char **aux, int interactive) +{ + int w = params->w, h = params->h, wh = w * h; + int i, j; + unsigned char *matrix, *grid; + char *mbmp, *gbmp, *ret; + + matrix = snewn(wh * wh, unsigned char); + grid = snewn(wh, unsigned char); + + /* + * First set up the matrix. + */ + switch (params->matrix_type) { + case CROSSES: + for (i = 0; i < wh; i++) { + int ix = i % w, iy = i / w; + for (j = 0; j < wh; j++) { + int jx = j % w, jy = j / w; + if (abs(jx - ix) + abs(jy - iy) <= 1) + matrix[i*wh+j] = 1; + else + matrix[i*wh+j] = 0; + } + } + break; + case RANDOM: + while (1) { + tree234 *pick, *cov, *osize; + int limit; + + pick = newtree234(sqcmp_pick); + cov = newtree234(sqcmp_cov); + osize = newtree234(sqcmp_osize); + + memset(matrix, 0, wh * wh); + for (i = 0; i < wh; i++) { + matrix[i*wh+i] = 1; + } + + for (i = 0; i < wh; i++) { + int ix = i % w, iy = i / w; + addneighbours(pick, w, h, ix, iy, ix, iy, matrix); + addneighbours(cov, w, h, ix, iy, ix, iy, matrix); + addneighbours(osize, w, h, ix, iy, ix, iy, matrix); + } + + /* + * Repeatedly choose a square to add to the matrix, + * until we have enough. I'll arbitrarily choose our + * limit to be the same as the total number of set bits + * in the crosses matrix. + */ + limit = 4*wh - 2*(w+h); /* centre squares already present */ + + while (limit-- > 0) { + struct sq *sq, *sq2, sqlocal; + int k; + + /* + * Find the lowest element in the pick tree. + */ + sq = index234(pick, 0); + + /* + * Find the highest element with the same coverage + * and omino size, by setting all other elements to + * lots. + */ + sqlocal = *sq; + sqlocal.cx = sqlocal.cy = sqlocal.x = sqlocal.y = wh; + sq = findrelpos234(pick, &sqlocal, NULL, REL234_LT, &k); + assert(sq != 0); + + /* + * Pick at random from all elements up to k of the + * pick tree. + */ + k = random_upto(rs, k+1); + sq = delpos234(pick, k); + del234(cov, sq); + del234(osize, sq); + + /* + * Add this square to the matrix. + */ + matrix[(sq->cy * w + sq->cx) * wh + (sq->y * w + sq->x)] = 1; + + /* + * Correct the matrix coverage field of any sq + * which points at this output square. + */ + sqlocal = *sq; + sqlocal.cx = sqlocal.cy = sqlocal.ominosize = -1; + while ((sq2 = findrel234(cov, &sqlocal, NULL, + REL234_GT)) != NULL && + sq2->coverage == sq->coverage && + sq2->x == sq->x && sq2->y == sq->y) { + del234(pick, sq2); + del234(cov, sq2); + del234(osize, sq2); + sq2->coverage++; + add234(pick, sq2); + add234(cov, sq2); + add234(osize, sq2); + } + + /* + * Correct the omino size field of any sq which + * points at this input square. + */ + sqlocal = *sq; + sqlocal.x = sqlocal.y = sqlocal.coverage = -1; + while ((sq2 = findrel234(osize, &sqlocal, NULL, + REL234_GT)) != NULL && + sq2->ominosize == sq->ominosize && + sq2->cx == sq->cx && sq2->cy == sq->cy) { + del234(pick, sq2); + del234(cov, sq2); + del234(osize, sq2); + sq2->ominosize++; + add234(pick, sq2); + add234(cov, sq2); + add234(osize, sq2); + } + + /* + * The sq we actually picked out of the tree is + * finished with; but its neighbours now need to + * appear. + */ + addneighbours(pick, w,h, sq->cx,sq->cy, sq->x,sq->y, matrix); + addneighbours(cov, w,h, sq->cx,sq->cy, sq->x,sq->y, matrix); + addneighbours(osize, w,h, sq->cx,sq->cy, sq->x,sq->y, matrix); + sfree(sq); + } + + /* + * Free all remaining sq structures. + */ + { + struct sq *sq; + while ((sq = delpos234(pick, 0)) != NULL) + sfree(sq); + } + freetree234(pick); + freetree234(cov); + freetree234(osize); + + /* + * Finally, check to see if any two matrix rows are + * exactly identical. If so, this is not an acceptable + * matrix, and we give up and go round again. + * + * I haven't been immediately able to think of a + * plausible means of algorithmically avoiding this + * situation (by, say, making a small perturbation to + * an offending matrix), so for the moment I'm just + * going to deal with it by throwing the whole thing + * away. I suspect this will lead to scalability + * problems (since most of the things happening in + * these matrices are local, the chance of _some_ + * neighbourhood having two identical regions will + * increase with the grid area), but so far this puzzle + * seems to be really hard at large sizes so I'm not + * massively worried yet. Anyone needs this done + * better, they're welcome to submit a patch. + */ + for (i = 0; i < wh; i++) { + for (j = 0; j < wh; j++) + if (i != j && + !memcmp(matrix + i * wh, matrix + j * wh, wh)) + break; + if (j < wh) + break; + } + if (i == wh) + break; /* no matches found */ + } + break; + } + + /* + * Now invent a random initial set of lights. + * + * At first glance it looks as if it might be quite difficult + * to choose equiprobably from all soluble light sets. After + * all, soluble light sets are those in the image space of the + * transformation matrix; so first we'd have to identify that + * space and its dimension, then pick a random coordinate for + * each basis vector and recombine. Lot of fiddly matrix + * algebra there. + * + * However, vector spaces are nicely orthogonal and relieve us + * of all that difficulty. For every point in the image space, + * there are precisely as many points in the input space that + * map to it as there are elements in the kernel of the + * transformation matrix (because adding any kernel element to + * the input does not change the output, and because any two + * inputs mapping to the same output must differ by an element + * of the kernel because that's what the kernel _is_); and + * these cosets are all disjoint (obviously, since no input + * point can map to more than one output point) and cover the + * whole space (equally obviously, because no input point can + * map to fewer than one output point!). + * + * So the input space contains the same number of points for + * each point in the output space; thus, we can simply choose + * equiprobably from elements of the _input_ space, and filter + * the result through the transformation matrix in the obvious + * way, and we thereby guarantee to choose equiprobably from + * all the output points. Phew! + */ + while (1) { + memset(grid, 0, wh); + for (i = 0; i < wh; i++) { + int v = random_upto(rs, 2); + if (v) { + for (j = 0; j < wh; j++) + grid[j] ^= matrix[i*wh+j]; + } + } + /* + * Ensure we don't have the starting state already! + */ + for (i = 0; i < wh; i++) + if (grid[i]) + break; + if (i < wh) + break; + } + + /* + * Now encode the matrix and the starting grid as a game + * description. We'll do this by concatenating two great big + * hex bitmaps. + */ + mbmp = encode_bitmap(matrix, wh*wh); + gbmp = encode_bitmap(grid, wh); + ret = snewn(strlen(mbmp) + strlen(gbmp) + 2, char); + sprintf(ret, "%s,%s", mbmp, gbmp); + sfree(mbmp); + sfree(gbmp); + sfree(matrix); + sfree(grid); + return ret; +} + +static char *validate_desc(const game_params *params, const char *desc) +{ + int w = params->w, h = params->h, wh = w * h; + int mlen = (wh*wh+3)/4, glen = (wh+3)/4; + + if (strspn(desc, "0123456789abcdefABCDEF") != mlen) + return "Matrix description is wrong length"; + if (desc[mlen] != ',') + return "Expected comma after matrix description"; + if (strspn(desc+mlen+1, "0123456789abcdefABCDEF") != glen) + return "Grid description is wrong length"; + if (desc[mlen+1+glen]) + return "Unexpected data after grid description"; + + return NULL; +} + +static game_state *new_game(midend *me, const game_params *params, + const char *desc) +{ + int w = params->w, h = params->h, wh = w * h; + int mlen = (wh*wh+3)/4; + + game_state *state = snew(game_state); + + state->w = w; + state->h = h; + state->completed = FALSE; + state->cheated = FALSE; + state->hints_active = FALSE; + state->moves = 0; + state->matrix = snew(struct matrix); + state->matrix->refcount = 1; + state->matrix->matrix = snewn(wh*wh, unsigned char); + decode_bitmap(state->matrix->matrix, wh*wh, desc); + state->grid = snewn(wh, unsigned char); + decode_bitmap(state->grid, wh, desc + mlen + 1); + + return state; +} + +static game_state *dup_game(const game_state *state) +{ + game_state *ret = snew(game_state); + + ret->w = state->w; + ret->h = state->h; + ret->completed = state->completed; + ret->cheated = state->cheated; + ret->hints_active = state->hints_active; + ret->moves = state->moves; + ret->matrix = state->matrix; + state->matrix->refcount++; + ret->grid = snewn(ret->w * ret->h, unsigned char); + memcpy(ret->grid, state->grid, ret->w * ret->h); + + return ret; +} + +static void free_game(game_state *state) +{ + sfree(state->grid); + if (--state->matrix->refcount <= 0) { + sfree(state->matrix->matrix); + sfree(state->matrix); + } + sfree(state); +} + +static void rowxor(unsigned char *row1, unsigned char *row2, int len) +{ + int i; + for (i = 0; i < len; i++) + row1[i] ^= row2[i]; +} + +static char *solve_game(const game_state *state, const game_state *currstate, + const char *aux, char **error) +{ + int w = state->w, h = state->h, wh = w * h; + unsigned char *equations, *solution, *shortest; + int *und, nund; + int rowsdone, colsdone; + int i, j, k, len, bestlen; + char *ret; + + /* + * Set up a list of simultaneous equations. Each one is of + * length (wh+1) and has wh coefficients followed by a value. + */ + equations = snewn((wh + 1) * wh, unsigned char); + for (i = 0; i < wh; i++) { + for (j = 0; j < wh; j++) + equations[i * (wh+1) + j] = currstate->matrix->matrix[j*wh+i]; + equations[i * (wh+1) + wh] = currstate->grid[i] & 1; + } + + /* + * Perform Gaussian elimination over GF(2). + */ + rowsdone = colsdone = 0; + nund = 0; + und = snewn(wh, int); + do { + /* + * Find the leftmost column which has a 1 in it somewhere + * outside the first `rowsdone' rows. + */ + j = -1; + for (i = colsdone; i < wh; i++) { + for (j = rowsdone; j < wh; j++) + if (equations[j * (wh+1) + i]) + break; + if (j < wh) + break; /* found one */ + /* + * This is a column which will not have an equation + * controlling it. Mark it as undetermined. + */ + und[nund++] = i; + } + + /* + * If there wasn't one, then we've finished: all remaining + * equations are of the form 0 = constant. Check to see if + * any of them wants 0 to be equal to 1; this is the + * condition which indicates an insoluble problem + * (therefore _hopefully_ one typed in by a user!). + */ + if (i == wh) { + for (j = rowsdone; j < wh; j++) + if (equations[j * (wh+1) + wh]) { + *error = "No solution exists for this position"; + sfree(equations); + sfree(und); + return NULL; + } + break; + } + + /* + * We've found a 1. It's in column i, and the topmost 1 in + * that column is in row j. Do a row-XOR to move it up to + * the topmost row if it isn't already there. + */ + assert(j != -1); + if (j > rowsdone) + rowxor(equations + rowsdone*(wh+1), equations + j*(wh+1), wh+1); + + /* + * Do row-XORs to eliminate that 1 from all rows below the + * topmost row. + */ + for (j = rowsdone + 1; j < wh; j++) + if (equations[j*(wh+1) + i]) + rowxor(equations + j*(wh+1), + equations + rowsdone*(wh+1), wh+1); + + /* + * Mark this row and column as done. + */ + rowsdone++; + colsdone = i+1; + + /* + * If we've done all the rows, terminate. + */ + } while (rowsdone < wh); + + /* + * If we reach here, we have the ability to produce a solution. + * So we go through _all_ possible solutions (each + * corresponding to a set of arbitrary choices of those + * components not directly determined by an equation), and pick + * one requiring the smallest number of flips. + */ + solution = snewn(wh, unsigned char); + shortest = snewn(wh, unsigned char); + memset(solution, 0, wh); + bestlen = wh + 1; + while (1) { + /* + * Find a solution based on the current values of the + * undetermined variables. + */ + for (j = rowsdone; j-- ;) { + int v; + + /* + * Find the leftmost set bit in this equation. + */ + for (i = 0; i < wh; i++) + if (equations[j * (wh+1) + i]) + break; + assert(i < wh); /* there must have been one! */ + + /* + * Compute this variable using the rest. + */ + v = equations[j * (wh+1) + wh]; + for (k = i+1; k < wh; k++) + if (equations[j * (wh+1) + k]) + v ^= solution[k]; + + solution[i] = v; + } + + /* + * Compare this solution to the current best one, and + * replace the best one if this one is shorter. + */ + len = 0; + for (i = 0; i < wh; i++) + if (solution[i]) + len++; + if (len < bestlen) { + bestlen = len; + memcpy(shortest, solution, wh); + } + + /* + * Now increment the binary number given by the + * undetermined variables: turn all 1s into 0s until we see + * a 0, at which point we turn it into a 1. + */ + for (i = 0; i < nund; i++) { + solution[und[i]] = !solution[und[i]]; + if (solution[und[i]]) + break; + } + + /* + * If we didn't find a 0 at any point, we have wrapped + * round and are back at the start, i.e. we have enumerated + * all solutions. + */ + if (i == nund) + break; + } + + /* + * We have a solution. Produce a move string encoding the + * solution. + */ + ret = snewn(wh + 2, char); + ret[0] = 'S'; + for (i = 0; i < wh; i++) + ret[i+1] = shortest[i] ? '1' : '0'; + ret[wh+1] = '\0'; + + sfree(shortest); + sfree(solution); + sfree(equations); + sfree(und); + + return ret; +} + +static int game_can_format_as_text_now(const game_params *params) +{ + return TRUE; +} + +#define RIGHT 1 +#define DOWN gw + +static char *game_text_format(const game_state *state) +{ + int w = state->w, h = state->h, wh = w*h, r, c, dx, dy; + int cw = 4, ch = 4, gw = w * cw + 2, gh = h * ch + 1, len = gw * gh; + char *board = snewn(len + 1, char); + + memset(board, ' ', len - 1); + + for (r = 0; r < h; ++r) { + for (c = 0; c < w; ++c) { + int cell = r*ch*gw + c*cw, center = cell+(ch/2)*DOWN + cw/2*RIGHT; + char flip = (state->grid[r*w + c] & 1) ? '#' : '.'; + for (dy = -1 + (r == 0); dy <= 1 - (r == h - 1); ++dy) + for (dx = -1 + (c == 0); dx <= 1 - (c == w - 1); ++dx) + if (state->matrix->matrix[(r*w+c)*wh + ((r+dy)*w + c+dx)]) + board[center + dy*DOWN + dx*RIGHT] = flip; + board[cell] = '+'; + for (dx = 1; dx < cw; ++dx) board[cell+dx*RIGHT] = '-'; + for (dy = 1; dy < ch; ++dy) board[cell+dy*DOWN] = '|'; + } + board[r*ch*gw + gw - 2] = '+'; + board[r*ch*gw + gw - 1] = '\n'; + for (dy = 1; dy < ch; ++dy) { + board[r*ch*gw + gw - 2 + dy*DOWN] = '|'; + board[r*ch*gw + gw - 1 + dy*DOWN] = '\n'; + } + } + memset(board + len - gw, '-', gw - 2); + for (c = 0; c <= w; ++c) board[len - gw + cw*c] = '+'; + board[len - 1] = '\n'; + board[len] = '\0'; + return board; +} + +#undef RIGHT +#undef DOWN + +struct game_ui { + int cx, cy, cdraw; +}; + +static game_ui *new_ui(const game_state *state) +{ + game_ui *ui = snew(game_ui); + ui->cx = ui->cy = ui->cdraw = 0; + return ui; +} + +static void free_ui(game_ui *ui) +{ + sfree(ui); +} + +static char *encode_ui(const game_ui *ui) +{ + return NULL; +} + +static void decode_ui(game_ui *ui, const char *encoding) +{ +} + +static void game_changed_state(game_ui *ui, const game_state *oldstate, + const game_state *newstate) +{ +} + +struct game_drawstate { + int w, h, started; + unsigned char *tiles; + int tilesize; +}; + +static char *interpret_move(const game_state *state, game_ui *ui, + const game_drawstate *ds, + int x, int y, int button) +{ + int w = state->w, h = state->h, wh = w * h; + char buf[80], *nullret = NULL; + + if (button == LEFT_BUTTON || IS_CURSOR_SELECT(button)) { + int tx, ty; + if (button == LEFT_BUTTON) { + tx = FROMCOORD(x), ty = FROMCOORD(y); + ui->cdraw = 0; + } else { + tx = ui->cx; ty = ui->cy; + ui->cdraw = 1; + } + nullret = ""; + + if (tx >= 0 && tx < w && ty >= 0 && ty < h) { + /* + * It's just possible that a manually entered game ID + * will have at least one square do nothing whatsoever. + * If so, we avoid encoding a move at all. + */ + int i = ty*w+tx, j, makemove = FALSE; + for (j = 0; j < wh; j++) { + if (state->matrix->matrix[i*wh+j]) + makemove = TRUE; + } + if (makemove) { + sprintf(buf, "M%d,%d", tx, ty); + return dupstr(buf); + } else { + return NULL; + } + } + } + else if (IS_CURSOR_MOVE(button)) { + int dx = 0, dy = 0; + switch (button) { + case CURSOR_UP: dy = -1; break; + case CURSOR_DOWN: dy = 1; break; + case CURSOR_RIGHT: dx = 1; break; + case CURSOR_LEFT: dx = -1; break; + default: assert(!"shouldn't get here"); + } + ui->cx += dx; ui->cy += dy; + ui->cx = min(max(ui->cx, 0), state->w - 1); + ui->cy = min(max(ui->cy, 0), state->h - 1); + ui->cdraw = 1; + nullret = ""; + } + + return nullret; +} + +static game_state *execute_move(const game_state *from, const char *move) +{ + int w = from->w, h = from->h, wh = w * h; + game_state *ret; + int x, y; + + if (move[0] == 'S' && strlen(move) == wh+1) { + int i; + + ret = dup_game(from); + ret->hints_active = TRUE; + ret->cheated = TRUE; + for (i = 0; i < wh; i++) { + ret->grid[i] &= ~2; + if (move[i+1] != '0') + ret->grid[i] |= 2; + } + return ret; + } else if (move[0] == 'M' && + sscanf(move+1, "%d,%d", &x, &y) == 2 && + x >= 0 && x < w && y >= 0 && y < h) { + int i, j, done; + + ret = dup_game(from); + + if (!ret->completed) + ret->moves++; + + i = y * w + x; + + done = TRUE; + for (j = 0; j < wh; j++) { + ret->grid[j] ^= ret->matrix->matrix[i*wh+j]; + if (ret->grid[j] & 1) + done = FALSE; + } + ret->grid[i] ^= 2; /* toggle hint */ + if (done) { + ret->completed = TRUE; + ret->hints_active = FALSE; + } + + return ret; + } else + return NULL; /* can't parse move string */ +} + +/* ---------------------------------------------------------------------- + * Drawing routines. + */ + +static void game_compute_size(const game_params *params, int tilesize, + int *x, int *y) +{ + /* Ick: fake up `ds->tilesize' for macro expansion purposes */ + struct { int tilesize; } ads, *ds = &ads; + ads.tilesize = tilesize; + + *x = TILE_SIZE * params->w + 2 * BORDER; + *y = TILE_SIZE * params->h + 2 * BORDER; +} + +static void game_set_size(drawing *dr, game_drawstate *ds, + const game_params *params, int tilesize) +{ + ds->tilesize = tilesize; +} + +static float *game_colours(frontend *fe, int *ncolours) +{ + float *ret = snewn(3 * NCOLOURS, float); + + frontend_default_colour(fe, &ret[COL_BACKGROUND * 3]); + + ret[COL_WRONG * 3 + 0] = ret[COL_BACKGROUND * 3 + 0] / 3; + ret[COL_WRONG * 3 + 1] = ret[COL_BACKGROUND * 3 + 1] / 3; + ret[COL_WRONG * 3 + 2] = ret[COL_BACKGROUND * 3 + 2] / 3; + + ret[COL_RIGHT * 3 + 0] = 1.0F; + ret[COL_RIGHT * 3 + 1] = 1.0F; + ret[COL_RIGHT * 3 + 2] = 1.0F; + + ret[COL_GRID * 3 + 0] = ret[COL_BACKGROUND * 3 + 0] / 1.5F; + ret[COL_GRID * 3 + 1] = ret[COL_BACKGROUND * 3 + 1] / 1.5F; + ret[COL_GRID * 3 + 2] = ret[COL_BACKGROUND * 3 + 2] / 1.5F; + + ret[COL_DIAG * 3 + 0] = ret[COL_GRID * 3 + 0]; + ret[COL_DIAG * 3 + 1] = ret[COL_GRID * 3 + 1]; + ret[COL_DIAG * 3 + 2] = ret[COL_GRID * 3 + 2]; + + ret[COL_HINT * 3 + 0] = 1.0F; + ret[COL_HINT * 3 + 1] = 0.0F; + ret[COL_HINT * 3 + 2] = 0.0F; + + ret[COL_CURSOR * 3 + 0] = 0.8F; + ret[COL_CURSOR * 3 + 1] = 0.0F; + ret[COL_CURSOR * 3 + 2] = 0.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 = FALSE; + ds->w = state->w; + ds->h = state->h; + ds->tiles = snewn(ds->w*ds->h, unsigned char); + ds->tilesize = 0; /* haven't decided yet */ + for (i = 0; i < ds->w*ds->h; i++) + ds->tiles[i] = -1; + + return ds; +} + +static void game_free_drawstate(drawing *dr, game_drawstate *ds) +{ + sfree(ds->tiles); + sfree(ds); +} + +static void draw_tile(drawing *dr, game_drawstate *ds, const game_state *state, + int x, int y, int tile, int anim, float animtime) +{ + int w = ds->w, h = ds->h, wh = w * h; + int bx = x * TILE_SIZE + BORDER, by = y * TILE_SIZE + BORDER; + int i, j, dcol = (tile & 4) ? COL_CURSOR : COL_DIAG; + + clip(dr, bx+1, by+1, TILE_SIZE-1, TILE_SIZE-1); + + draw_rect(dr, bx+1, by+1, TILE_SIZE-1, TILE_SIZE-1, + anim ? COL_BACKGROUND : tile & 1 ? COL_WRONG : COL_RIGHT); + if (anim) { + /* + * Draw a polygon indicating that the square is diagonally + * flipping over. + */ + int coords[8], colour; + + coords[0] = bx + TILE_SIZE; + coords[1] = by; + coords[2] = bx + (int)((float)TILE_SIZE * animtime); + coords[3] = by + (int)((float)TILE_SIZE * animtime); + coords[4] = bx; + coords[5] = by + TILE_SIZE; + coords[6] = bx + TILE_SIZE - (int)((float)TILE_SIZE * animtime); + coords[7] = by + TILE_SIZE - (int)((float)TILE_SIZE * animtime); + + colour = (tile & 1 ? COL_WRONG : COL_RIGHT); + if (animtime < 0.5) + colour = COL_WRONG + COL_RIGHT - colour; + + draw_polygon(dr, coords, 4, colour, COL_GRID); + } + + /* + * Draw a little diagram in the tile which indicates which + * surrounding tiles flip when this one is clicked. + */ + for (i = 0; i < h; i++) + for (j = 0; j < w; j++) + if (state->matrix->matrix[(y*w+x)*wh + i*w+j]) { + int ox = j - x, oy = i - y; + int td = TILE_SIZE / 16; + int cx = (bx + TILE_SIZE/2) + (2 * ox - 1) * td; + int cy = (by + TILE_SIZE/2) + (2 * oy - 1) * td; + if (ox == 0 && oy == 0) + draw_rect(dr, cx, cy, 2*td+1, 2*td+1, dcol); + else { + draw_line(dr, cx, cy, cx+2*td, cy, dcol); + draw_line(dr, cx, cy+2*td, cx+2*td, cy+2*td, dcol); + draw_line(dr, cx, cy, cx, cy+2*td, dcol); + draw_line(dr, cx+2*td, cy, cx+2*td, cy+2*td, dcol); + } + } + + /* + * Draw a hint rectangle if required. + */ + if (tile & 2) { + int x1 = bx + TILE_SIZE / 20, x2 = bx + TILE_SIZE - TILE_SIZE / 20; + int y1 = by + TILE_SIZE / 20, y2 = by + TILE_SIZE - TILE_SIZE / 20; + int i = 3; + while (i--) { + draw_line(dr, x1, y1, x2, y1, COL_HINT); + draw_line(dr, x1, y2, x2, y2, COL_HINT); + draw_line(dr, x1, y1, x1, y2, COL_HINT); + draw_line(dr, x2, y1, x2, y2, COL_HINT); + x1++, y1++, x2--, y2--; + } + } + + unclip(dr); + + draw_update(dr, bx+1, by+1, TILE_SIZE-1, TILE_SIZE-1); +} + +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 w = ds->w, h = ds->h, wh = w * h; + int i, flashframe; + + if (!ds->started) { + draw_rect(dr, 0, 0, TILE_SIZE * w + 2 * BORDER, + TILE_SIZE * h + 2 * BORDER, COL_BACKGROUND); + + /* + * Draw the grid lines. + */ + for (i = 0; i <= w; i++) + draw_line(dr, i * TILE_SIZE + BORDER, BORDER, + i * TILE_SIZE + BORDER, h * TILE_SIZE + BORDER, + COL_GRID); + for (i = 0; i <= h; i++) + draw_line(dr, BORDER, i * TILE_SIZE + BORDER, + w * TILE_SIZE + BORDER, i * TILE_SIZE + BORDER, + COL_GRID); + + draw_update(dr, 0, 0, TILE_SIZE * w + 2 * BORDER, + TILE_SIZE * h + 2 * BORDER); + + ds->started = TRUE; + } + + if (flashtime) + flashframe = (int)(flashtime / FLASH_FRAME); + else + flashframe = -1; + + animtime /= ANIM_TIME; /* scale it so it goes from 0 to 1 */ + + for (i = 0; i < wh; i++) { + int x = i % w, y = i / w; + int fx, fy, fd; + int v = state->grid[i]; + int vv; + + if (flashframe >= 0) { + fx = (w+1)/2 - min(x+1, w-x); + fy = (h+1)/2 - min(y+1, h-y); + fd = max(fx, fy); + if (fd == flashframe) + v |= 1; + else if (fd == flashframe - 1) + v &= ~1; + } + + if (!state->hints_active) + v &= ~2; + if (ui->cdraw && ui->cx == x && ui->cy == y) + v |= 4; + + if (oldstate && ((state->grid[i] ^ oldstate->grid[i]) &~ 2)) + vv = 255; /* means `animated' */ + else + vv = v; + + if (ds->tiles[i] == 255 || vv == 255 || ds->tiles[i] != vv) { + draw_tile(dr, ds, state, x, y, v, vv == 255, animtime); + ds->tiles[i] = vv; + } + } + + { + char buf[256]; + + sprintf(buf, "%sMoves: %d", + (state->completed ? + (state->cheated ? "Auto-solved. " : "COMPLETED! ") : + (state->cheated ? "Auto-solver used. " : "")), + state->moves); + + status_bar(dr, buf); + } +} + +static float game_anim_length(const game_state *oldstate, + const game_state *newstate, int dir, game_ui *ui) +{ + return ANIM_TIME; +} + +static float game_flash_length(const game_state *oldstate, + const game_state *newstate, int dir, game_ui *ui) +{ + if (!oldstate->completed && newstate->completed) + return FLASH_FRAME * (max((newstate->w+1)/2, (newstate->h+1)/2)+1); + + return 0.0F; +} + +static int game_status(const game_state *state) +{ + return state->completed ? +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 flip +#endif + +const struct game thegame = { + "Flip", "games.flip", "flip", + 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, + TRUE, 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