/* * map.c: Game involving four-colouring a map. */ /* * TODO: * * - error highlighting * - clue marking * - more solver brains? * - better four-colouring algorithm? * - pencil marks? */ #include #include #include #include #include #include #include "puzzles.h" /* * I don't seriously anticipate wanting to change the number of * colours used in this game, but it doesn't cost much to use a * #define just in case :-) */ #define FOUR 4 #define THREE (FOUR-1) #define FIVE (FOUR+1) #define SIX (FOUR+2) /* * Ghastly run-time configuration option, just for Gareth (again). */ static int flash_type = -1; static float flash_length; /* * Difficulty levels. I do some macro ickery here to ensure that my * enum and the various forms of my name list always match up. */ #define DIFFLIST(A) \ A(EASY,Easy,e) \ A(NORMAL,Normal,n) #define ENUM(upper,title,lower) DIFF_ ## upper, #define TITLE(upper,title,lower) #title, #define ENCODE(upper,title,lower) #lower #define CONFIG(upper,title,lower) ":" #title enum { DIFFLIST(ENUM) DIFFCOUNT }; static char const *const map_diffnames[] = { DIFFLIST(TITLE) }; static char const map_diffchars[] = DIFFLIST(ENCODE); #define DIFFCONFIG DIFFLIST(CONFIG) enum { TE, BE, LE, RE }; /* top/bottom/left/right edges */ enum { COL_BACKGROUND, COL_GRID, COL_0, COL_1, COL_2, COL_3, NCOLOURS }; struct game_params { int w, h, n, diff; }; struct map { int refcount; int *map; int *graph; int n; int ngraph; int *immutable; }; struct game_state { game_params p; struct map *map; int *colouring; int completed, cheated; }; static game_params *default_params(void) { game_params *ret = snew(game_params); ret->w = 20; ret->h = 15; ret->n = 30; ret->diff = DIFF_NORMAL; return ret; } static const struct game_params map_presets[] = { {20, 15, 30, DIFF_EASY}, {20, 15, 30, DIFF_NORMAL}, {30, 25, 75, DIFF_NORMAL}, }; static int game_fetch_preset(int i, char **name, game_params **params) { game_params *ret; char str[80]; if (i < 0 || i >= lenof(map_presets)) return FALSE; ret = snew(game_params); *ret = map_presets[i]; sprintf(str, "%dx%d, %d regions, %s", ret->w, ret->h, ret->n, map_diffnames[ret->diff]); *name = dupstr(str); *params = ret; return TRUE; } static void free_params(game_params *params) { sfree(params); } static game_params *dup_params(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 == 'n') { p++; params->n = atoi(p); while (*p && (*p == '.' || isdigit((unsigned char)*p))) p++; } else { params->n = params->w * params->h / 8; } if (*p == 'd') { int i; p++; for (i = 0; i < DIFFCOUNT; i++) if (*p == map_diffchars[i]) params->diff = i; if (*p) p++; } } static char *encode_params(game_params *params, int full) { char ret[400]; sprintf(ret, "%dx%dn%d", params->w, params->h, params->n); if (full) sprintf(ret + strlen(ret), "d%c", map_diffchars[params->diff]); return dupstr(ret); } static config_item *game_configure(game_params *params) { config_item *ret; char buf[80]; ret = snewn(5, 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 = "Regions"; ret[2].type = C_STRING; sprintf(buf, "%d", params->n); ret[2].sval = dupstr(buf); ret[2].ival = 0; ret[3].name = "Difficulty"; ret[3].type = C_CHOICES; ret[3].sval = DIFFCONFIG; ret[3].ival = params->diff; ret[4].name = NULL; ret[4].type = C_END; ret[4].sval = NULL; ret[4].ival = 0; return ret; } static game_params *custom_params(config_item *cfg) { game_params *ret = snew(game_params); ret->w = atoi(cfg[0].sval); ret->h = atoi(cfg[1].sval); ret->n = atoi(cfg[2].sval); ret->diff = cfg[3].ival; return ret; } static char *validate_params(game_params *params, int full) { if (params->w < 2 || params->h < 2) return "Width and height must be at least two"; if (params->n < 5) return "Must have at least five regions"; if (params->n > params->w * params->h) return "Too many regions to fit in grid"; return NULL; } /* ---------------------------------------------------------------------- * Cumulative frequency table functions. */ /* * Initialise a cumulative frequency table. (Hardly worth writing * this function; all it does is to initialise everything in the * array to zero.) */ static void cf_init(int *table, int n) { int i; for (i = 0; i < n; i++) table[i] = 0; } /* * Increment the count of symbol `sym' by `count'. */ static void cf_add(int *table, int n, int sym, int count) { int bit; bit = 1; while (sym != 0) { if (sym & bit) { table[sym] += count; sym &= ~bit; } bit <<= 1; } table[0] += count; } /* * Cumulative frequency lookup: return the total count of symbols * with value less than `sym'. */ static int cf_clookup(int *table, int n, int sym) { int bit, index, limit, count; if (sym == 0) return 0; assert(0 < sym && sym <= n); count = table[0]; /* start with the whole table size */ bit = 1; while (bit < n) bit <<= 1; limit = n; while (bit > 0) { /* * Find the least number with its lowest set bit in this * position which is greater than or equal to sym. */ index = ((sym + bit - 1) &~ (bit * 2 - 1)) + bit; if (index < limit) { count -= table[index]; limit = index; } bit >>= 1; } return count; } /* * Single frequency lookup: return the count of symbol `sym'. */ static int cf_slookup(int *table, int n, int sym) { int count, bit; assert(0 <= sym && sym < n); count = table[sym]; for (bit = 1; sym+bit < n && !(sym & bit); bit <<= 1) count -= table[sym+bit]; return count; } /* * Return the largest symbol index such that the cumulative * frequency up to that symbol is less than _or equal to_ count. */ static int cf_whichsym(int *table, int n, int count) { int bit, sym, top; assert(count >= 0 && count < table[0]); bit = 1; while (bit < n) bit <<= 1; sym = 0; top = table[0]; while (bit > 0) { if (sym+bit < n) { if (count >= top - table[sym+bit]) sym += bit; else top -= table[sym+bit]; } bit >>= 1; } return sym; } /* ---------------------------------------------------------------------- * Map generation. * * FIXME: this isn't entirely optimal at present, because it * inherently prioritises growing the largest region since there * are more squares adjacent to it. This acts as a destabilising * influence leading to a few large regions and mostly small ones. * It might be better to do it some other way. */ #define WEIGHT_INCREASED 2 /* for increased perimeter */ #define WEIGHT_DECREASED 4 /* for decreased perimeter */ #define WEIGHT_UNCHANGED 3 /* for unchanged perimeter */ /* * Look at a square and decide which colours can be extended into * it. * * If called with index < 0, it adds together one of * WEIGHT_INCREASED, WEIGHT_DECREASED or WEIGHT_UNCHANGED for each * colour that has a valid extension (according to the effect that * it would have on the perimeter of the region being extended) and * returns the overall total. * * If called with index >= 0, it returns one of the possible * colours depending on the value of index, in such a way that the * number of possible inputs which would give rise to a given * return value correspond to the weight of that value. */ static int extend_options(int w, int h, int n, int *map, int x, int y, int index) { int c, i, dx, dy; int col[8]; int total = 0; if (map[y*w+x] >= 0) { assert(index < 0); return 0; /* can't do this square at all */ } /* * Fetch the eight neighbours of this square, in order around * the square. */ for (dy = -1; dy <= +1; dy++) for (dx = -1; dx <= +1; dx++) { int index = (dy < 0 ? 6-dx : dy > 0 ? 2+dx : 2*(1+dx)); if (x+dx >= 0 && x+dx < w && y+dy >= 0 && y+dy < h) col[index] = map[(y+dy)*w+(x+dx)]; else col[index] = -1; } /* * Iterate over each colour that might be feasible. * * FIXME: this routine currently has O(n) running time. We * could turn it into O(FOUR) by only bothering to iterate over * the colours mentioned in the four neighbouring squares. */ for (c = 0; c < n; c++) { int count, neighbours, runs; /* * One of the even indices of col (representing the * orthogonal neighbours of this square) must be equal to * c, or else this square is not adjacent to region c and * obviously cannot become an extension of it at this time. */ neighbours = 0; for (i = 0; i < 8; i += 2) if (col[i] == c) neighbours++; if (!neighbours) continue; /* * Now we know this square is adjacent to region c. The * next question is, would extending it cause the region to * become non-simply-connected? If so, we mustn't do it. * * We determine this by looking around col to see if we can * find more than one separate run of colour c. */ runs = 0; for (i = 0; i < 8; i++) if (col[i] == c && col[(i+1) & 7] != c) runs++; if (runs > 1) continue; assert(runs == 1); /* * This square is a possibility. Determine its effect on * the region's perimeter (computed from the number of * orthogonal neighbours - 1 means a perimeter increase, 3 * a decrease, 2 no change; 4 is impossible because the * region would already not be simply connected) and we're * done. */ assert(neighbours > 0 && neighbours < 4); count = (neighbours == 1 ? WEIGHT_INCREASED : neighbours == 2 ? WEIGHT_UNCHANGED : WEIGHT_DECREASED); total += count; if (index >= 0 && index < count) return c; else index -= count; } assert(index < 0); return total; } static void genmap(int w, int h, int n, int *map, random_state *rs) { int wh = w*h; int x, y, i, k; int *tmp; assert(n <= wh); tmp = snewn(wh, int); /* * Clear the map, and set up `tmp' as a list of grid indices. */ for (i = 0; i < wh; i++) { map[i] = -1; tmp[i] = i; } /* * Place the region seeds by selecting n members from `tmp'. */ k = wh; for (i = 0; i < n; i++) { int j = random_upto(rs, k); map[tmp[j]] = i; tmp[j] = tmp[--k]; } /* * Re-initialise `tmp' as a cumulative frequency table. This * will store the number of possible region colours we can * extend into each square. */ cf_init(tmp, wh); /* * Go through the grid and set up the initial cumulative * frequencies. */ for (y = 0; y < h; y++) for (x = 0; x < w; x++) cf_add(tmp, wh, y*w+x, extend_options(w, h, n, map, x, y, -1)); /* * Now repeatedly choose a square we can extend a region into, * and do so. */ while (tmp[0] > 0) { int k = random_upto(rs, tmp[0]); int sq; int colour; int xx, yy; sq = cf_whichsym(tmp, wh, k); k -= cf_clookup(tmp, wh, sq); x = sq % w; y = sq / w; colour = extend_options(w, h, n, map, x, y, k); map[sq] = colour; /* * Re-scan the nine cells around the one we've just * modified. */ for (yy = max(y-1, 0); yy < min(y+2, h); yy++) for (xx = max(x-1, 0); xx < min(x+2, w); xx++) { cf_add(tmp, wh, yy*w+xx, -cf_slookup(tmp, wh, yy*w+xx) + extend_options(w, h, n, map, xx, yy, -1)); } } /* * Finally, go through and normalise the region labels into * order, meaning that indistinguishable maps are actually * identical. */ for (i = 0; i < n; i++) tmp[i] = -1; k = 0; for (i = 0; i < wh; i++) { assert(map[i] >= 0); if (tmp[map[i]] < 0) tmp[map[i]] = k++; map[i] = tmp[map[i]]; } sfree(tmp); } /* ---------------------------------------------------------------------- * Functions to handle graphs. */ /* * Having got a map in a square grid, convert it into a graph * representation. */ static int gengraph(int w, int h, int n, int *map, int *graph) { int i, j, x, y; /* * Start by setting the graph up as an adjacency matrix. We'll * turn it into a list later. */ for (i = 0; i < n*n; i++) graph[i] = 0; /* * Iterate over the map looking for all adjacencies. */ for (y = 0; y < h; y++) for (x = 0; x < w; x++) { int v, vx, vy; v = map[y*w+x]; if (x+1 < w && (vx = map[y*w+(x+1)]) != v) graph[v*n+vx] = graph[vx*n+v] = 1; if (y+1 < h && (vy = map[(y+1)*w+x]) != v) graph[v*n+vy] = graph[vy*n+v] = 1; } /* * Turn the matrix into a list. */ for (i = j = 0; i < n*n; i++) if (graph[i]) graph[j++] = i; return j; } static int graph_adjacent(int *graph, int n, int ngraph, int i, int j) { int v = i*n+j; int top, bot, mid; bot = -1; top = ngraph; while (top - bot > 1) { mid = (top + bot) / 2; if (graph[mid] == v) return TRUE; else if (graph[mid] < v) bot = mid; else top = mid; } return FALSE; } static int graph_vertex_start(int *graph, int n, int ngraph, int i) { int v = i*n; int top, bot, mid; bot = -1; top = ngraph; while (top - bot > 1) { mid = (top + bot) / 2; if (graph[mid] < v) bot = mid; else top = mid; } return top; } /* ---------------------------------------------------------------------- * Generate a four-colouring of a graph. * * FIXME: it would be nice if we could convert this recursion into * pseudo-recursion using some sort of explicit stack array, for * the sake of the Palm port and its limited stack. */ static int fourcolour_recurse(int *graph, int n, int ngraph, int *colouring, int *scratch, random_state *rs) { int nfree, nvert, start, i, j, k, c, ci; int cs[FOUR]; /* * Find the smallest number of free colours in any uncoloured * vertex, and count the number of such vertices. */ nfree = FIVE; /* start off bigger than FOUR! */ nvert = 0; for (i = 0; i < n; i++) if (colouring[i] < 0 && scratch[i*FIVE+FOUR] <= nfree) { if (nfree > scratch[i*FIVE+FOUR]) { nfree = scratch[i*FIVE+FOUR]; nvert = 0; } nvert++; } /* * If there aren't any uncoloured vertices at all, we're done. */ if (nvert == 0) return TRUE; /* we've got a colouring! */ /* * Pick a random vertex in that set. */ j = random_upto(rs, nvert); for (i = 0; i < n; i++) if (colouring[i] < 0 && scratch[i*FIVE+FOUR] == nfree) if (j-- == 0) break; assert(i < n); start = graph_vertex_start(graph, n, ngraph, i); /* * Loop over the possible colours for i, and recurse for each * one. */ ci = 0; for (c = 0; c < FOUR; c++) if (scratch[i*FIVE+c] == 0) cs[ci++] = c; shuffle(cs, ci, sizeof(*cs), rs); while (ci-- > 0) { c = cs[ci]; /* * Fill in this colour. */ colouring[i] = c; /* * Update the scratch space to reflect a new neighbour * of this colour for each neighbour of vertex i. */ for (j = start; j < ngraph && graph[j] < n*(i+1); j++) { k = graph[j] - i*n; if (scratch[k*FIVE+c] == 0) scratch[k*FIVE+FOUR]--; scratch[k*FIVE+c]++; } /* * Recurse. */ if (fourcolour_recurse(graph, n, ngraph, colouring, scratch, rs)) return TRUE; /* got one! */ /* * If that didn't work, clean up and try again with a * different colour. */ for (j = start; j < ngraph && graph[j] < n*(i+1); j++) { k = graph[j] - i*n; scratch[k*FIVE+c]--; if (scratch[k*FIVE+c] == 0) scratch[k*FIVE+FOUR]++; } colouring[i] = -1; } /* * If we reach here, we were unable to find a colouring at all. * (This doesn't necessarily mean the Four Colour Theorem is * violated; it might just mean we've gone down a dead end and * need to back up and look somewhere else. It's only an FCT * violation if we get all the way back up to the top level and * still fail.) */ return FALSE; } static void fourcolour(int *graph, int n, int ngraph, int *colouring, random_state *rs) { int *scratch; int i; /* * For each vertex and each colour, we store the number of * neighbours that have that colour. Also, we store the number * of free colours for the vertex. */ scratch = snewn(n * FIVE, int); for (i = 0; i < n * FIVE; i++) scratch[i] = (i % FIVE == FOUR ? FOUR : 0); /* * Clear the colouring to start with. */ for (i = 0; i < n; i++) colouring[i] = -1; i = fourcolour_recurse(graph, n, ngraph, colouring, scratch, rs); assert(i); /* by the Four Colour Theorem :-) */ sfree(scratch); } /* ---------------------------------------------------------------------- * Non-recursive solver. */ struct solver_scratch { unsigned char *possible; /* bitmap of colours for each region */ int *graph; int n; int ngraph; }; static struct solver_scratch *new_scratch(int *graph, int n, int ngraph) { struct solver_scratch *sc; sc = snew(struct solver_scratch); sc->graph = graph; sc->n = n; sc->ngraph = ngraph; sc->possible = snewn(n, unsigned char); return sc; } static void free_scratch(struct solver_scratch *sc) { sfree(sc->possible); sfree(sc); } static int place_colour(struct solver_scratch *sc, int *colouring, int index, int colour) { int *graph = sc->graph, n = sc->n, ngraph = sc->ngraph; int j, k; if (!(sc->possible[index] & (1 << colour))) return FALSE; /* can't do it */ sc->possible[index] = 1 << colour; colouring[index] = colour; /* * Rule out this colour from all the region's neighbours. */ for (j = graph_vertex_start(graph, n, ngraph, index); j < ngraph && graph[j] < n*(index+1); j++) { k = graph[j] - index*n; sc->possible[k] &= ~(1 << colour); } return TRUE; } /* * Returns 0 for impossible, 1 for success, 2 for failure to * converge (i.e. puzzle is either ambiguous or just too * difficult). */ static int map_solver(struct solver_scratch *sc, int *graph, int n, int ngraph, int *colouring, int difficulty) { int i; /* * Initialise scratch space. */ for (i = 0; i < n; i++) sc->possible[i] = (1 << FOUR) - 1; /* * Place clues. */ for (i = 0; i < n; i++) if (colouring[i] >= 0) { if (!place_colour(sc, colouring, i, colouring[i])) return 0; /* the clues aren't even consistent! */ } /* * Now repeatedly loop until we find nothing further to do. */ while (1) { int done_something = FALSE; if (difficulty < DIFF_EASY) break; /* can't do anything at all! */ /* * Simplest possible deduction: find a region with only one * possible colour. */ for (i = 0; i < n; i++) if (colouring[i] < 0) { int p = sc->possible[i]; if (p == 0) return 0; /* puzzle is inconsistent */ if ((p & (p-1)) == 0) { /* p is a power of two */ int c; for (c = 0; c < FOUR; c++) if (p == (1 << c)) break; assert(c < FOUR); if (!place_colour(sc, colouring, i, c)) return 0; /* found puzzle to be inconsistent */ done_something = TRUE; } } if (done_something) continue; if (difficulty < DIFF_NORMAL) break; /* can't do anything harder */ /* * Failing that, go up one level. Look for pairs of regions * which (a) both have the same pair of possible colours, * (b) are adjacent to one another, (c) are adjacent to the * same region, and (d) that region still thinks it has one * or both of those possible colours. * * Simplest way to do this is by going through the graph * edge by edge, so that we start with property (b) and * then look for (a) and finally (c) and (d). */ for (i = 0; i < ngraph; i++) { int j1 = graph[i] / n, j2 = graph[i] % n; int j, k, v, v2; if (j1 > j2) continue; /* done it already, other way round */ if (colouring[j1] >= 0 || colouring[j2] >= 0) continue; /* they're not undecided */ if (sc->possible[j1] != sc->possible[j2]) continue; /* they don't have the same possibles */ v = sc->possible[j1]; /* * See if v contains exactly two set bits. */ v2 = v & -v; /* find lowest set bit */ v2 = v & ~v2; /* clear it */ if (v2 == 0 || (v2 & (v2-1)) != 0) /* not power of 2 */ continue; /* * We've found regions j1 and j2 satisfying properties * (a) and (b): they have two possible colours between * them, and since they're adjacent to one another they * must use _both_ those colours between them. * Therefore, if they are both adjacent to any other * region then that region cannot be either colour. * * Go through the neighbours of j1 and see if any are * shared with j2. */ for (j = graph_vertex_start(graph, n, ngraph, j1); j < ngraph && graph[j] < n*(j1+1); j++) { k = graph[j] - j1*n; if (graph_adjacent(graph, n, ngraph, k, j2) && (sc->possible[k] & v)) { sc->possible[k] &= ~v; done_something = TRUE; } } } if (!done_something) break; } /* * We've run out of things to deduce. See if we've got the lot. */ for (i = 0; i < n; i++) if (colouring[i] < 0) return 2; return 1; /* success! */ } /* ---------------------------------------------------------------------- * Game generation main function. */ static char *new_game_desc(game_params *params, random_state *rs, char **aux, int interactive) { struct solver_scratch *sc = NULL; int *map, *graph, ngraph, *colouring, *colouring2, *regions; int i, j, w, h, n, solveret, cfreq[FOUR]; int wh; int mindiff, tries; #ifdef GENERATION_DIAGNOSTICS int x, y; #endif char *ret, buf[80]; int retlen, retsize; w = params->w; h = params->h; n = params->n; wh = w*h; *aux = NULL; map = snewn(wh, int); graph = snewn(n*n, int); colouring = snewn(n, int); colouring2 = snewn(n, int); regions = snewn(n, int); /* * This is the minimum difficulty below which we'll completely * reject a map design. Normally we set this to one below the * requested difficulty, ensuring that we have the right * result. However, for particularly dense maps or maps with * particularly few regions it might not be possible to get the * desired difficulty, so we will eventually drop this down to * -1 to indicate that any old map will do. */ mindiff = params->diff; tries = 50; while (1) { /* * Create the map. */ genmap(w, h, n, map, rs); #ifdef GENERATION_DIAGNOSTICS for (y = 0; y < h; y++) { for (x = 0; x < w; x++) { int v = map[y*w+x]; if (v >= 62) putchar('!'); else if (v >= 36) putchar('a' + v-36); else if (v >= 10) putchar('A' + v-10); else putchar('0' + v); } putchar('\n'); } #endif /* * Convert the map into a graph. */ ngraph = gengraph(w, h, n, map, graph); #ifdef GENERATION_DIAGNOSTICS for (i = 0; i < ngraph; i++) printf("%d-%d\n", graph[i]/n, graph[i]%n); #endif /* * Colour the map. */ fourcolour(graph, n, ngraph, colouring, rs); #ifdef GENERATION_DIAGNOSTICS for (i = 0; i < n; i++) printf("%d: %d\n", i, colouring[i]); for (y = 0; y < h; y++) { for (x = 0; x < w; x++) { int v = colouring[map[y*w+x]]; if (v >= 36) putchar('a' + v-36); else if (v >= 10) putchar('A' + v-10); else putchar('0' + v); } putchar('\n'); } #endif /* * Encode the solution as an aux string. */ if (*aux) /* in case we've come round again */ sfree(*aux); retlen = retsize = 0; ret = NULL; for (i = 0; i < n; i++) { int len; if (colouring[i] < 0) continue; len = sprintf(buf, "%s%d:%d", i ? ";" : "S;", colouring[i], i); if (retlen + len >= retsize) { retsize = retlen + len + 256; ret = sresize(ret, retsize, char); } strcpy(ret + retlen, buf); retlen += len; } *aux = ret; /* * Remove the region colours one by one, keeping * solubility. Also ensure that there always remains at * least one region of every colour, so that the user can * drag from somewhere. */ for (i = 0; i < FOUR; i++) cfreq[i] = 0; for (i = 0; i < n; i++) { regions[i] = i; cfreq[colouring[i]]++; } for (i = 0; i < FOUR; i++) if (cfreq[i] == 0) continue; shuffle(regions, n, sizeof(*regions), rs); if (sc) free_scratch(sc); sc = new_scratch(graph, n, ngraph); for (i = 0; i < n; i++) { j = regions[i]; if (cfreq[colouring[j]] == 1) continue; /* can't remove last region of colour */ memcpy(colouring2, colouring, n*sizeof(int)); colouring2[j] = -1; solveret = map_solver(sc, graph, n, ngraph, colouring2, params->diff); assert(solveret >= 0); /* mustn't be impossible! */ if (solveret == 1) { cfreq[colouring[j]]--; colouring[j] = -1; } } #ifdef GENERATION_DIAGNOSTICS for (i = 0; i < n; i++) if (colouring[i] >= 0) { if (i >= 62) putchar('!'); else if (i >= 36) putchar('a' + i-36); else if (i >= 10) putchar('A' + i-10); else putchar('0' + i); printf(": %d\n", colouring[i]); } #endif /* * Finally, check that the puzzle is _at least_ as hard as * required, and indeed that it isn't already solved. * (Calling map_solver with negative difficulty ensures the * latter - if a solver which _does nothing_ can't solve * it, it's too easy!) */ memcpy(colouring2, colouring, n*sizeof(int)); if (map_solver(sc, graph, n, ngraph, colouring2, mindiff - 1) == 1) { /* * Drop minimum difficulty if necessary. */ if (mindiff > 0 && (n < 9 || n > 3*wh/2)) { if (tries-- <= 0) mindiff = 0; /* give up and go for Easy */ } continue; } break; } /* * Encode as a game ID. We do this by: * * - first going along the horizontal edges row by row, and * then the vertical edges column by column * - encoding the lengths of runs of edges and runs of * non-edges * - the decoder will reconstitute the region boundaries from * this and automatically number them the same way we did * - then we encode the initial region colours in a Slant-like * fashion (digits 0-3 interspersed with letters giving * lengths of runs of empty spaces). */ retlen = retsize = 0; ret = NULL; { int run, pv; /* * Start with a notional non-edge, so that there'll be an * explicit `a' to distinguish the case where we start with * an edge. */ run = 1; pv = 0; for (i = 0; i < w*(h-1) + (w-1)*h; i++) { int x, y, dx, dy, v; if (i < w*(h-1)) { /* Horizontal edge. */ y = i / w; x = i % w; dx = 0; dy = 1; } else { /* Vertical edge. */ x = (i - w*(h-1)) / h; y = (i - w*(h-1)) % h; dx = 1; dy = 0; } if (retlen + 10 >= retsize) { retsize = retlen + 256; ret = sresize(ret, retsize, char); } v = (map[y*w+x] != map[(y+dy)*w+(x+dx)]); if (pv != v) { ret[retlen++] = 'a'-1 + run; run = 1; pv = v; } else { /* * 'z' is a special case in this encoding. Rather * than meaning a run of 26 and a state switch, it * means a run of 25 and _no_ state switch, because * otherwise there'd be no way to encode runs of * more than 26. */ if (run == 25) { ret[retlen++] = 'z'; run = 0; } run++; } } ret[retlen++] = 'a'-1 + run; ret[retlen++] = ','; run = 0; for (i = 0; i < n; i++) { if (retlen + 10 >= retsize) { retsize = retlen + 256; ret = sresize(ret, retsize, char); } if (colouring[i] < 0) { /* * In _this_ encoding, 'z' is a run of 26, since * there's no implicit state switch after each run. * Confusingly different, but more compact. */ if (run == 26) { ret[retlen++] = 'z'; run = 0; } run++; } else { if (run > 0) ret[retlen++] = 'a'-1 + run; ret[retlen++] = '0' + colouring[i]; run = 0; } } if (run > 0) ret[retlen++] = 'a'-1 + run; ret[retlen] = '\0'; assert(retlen < retsize); } free_scratch(sc); sfree(regions); sfree(colouring2); sfree(colouring); sfree(graph); sfree(map); return ret; } static char *parse_edge_list(game_params *params, char **desc, int *map) { int w = params->w, h = params->h, wh = w*h, n = params->n; int i, k, pos, state; char *p = *desc; for (i = 0; i < wh; i++) map[wh+i] = i; pos = -1; state = 0; /* * Parse the game description to get the list of edges, and * build up a disjoint set forest as we go (by identifying * pairs of squares whenever the edge list shows a non-edge). */ while (*p && *p != ',') { if (*p < 'a' || *p > 'z') return "Unexpected character in edge list"; if (*p == 'z') k = 25; else k = *p - 'a' + 1; while (k-- > 0) { int x, y, dx, dy; if (pos < 0) { pos++; continue; } else if (pos < w*(h-1)) { /* Horizontal edge. */ y = pos / w; x = pos % w; dx = 0; dy = 1; } else if (pos < 2*wh-w-h) { /* Vertical edge. */ x = (pos - w*(h-1)) / h; y = (pos - w*(h-1)) % h; dx = 1; dy = 0; } else return "Too much data in edge list"; if (!state) dsf_merge(map+wh, y*w+x, (y+dy)*w+(x+dx)); pos++; } if (*p != 'z') state = !state; p++; } assert(pos <= 2*wh-w-h); if (pos < 2*wh-w-h) return "Too little data in edge list"; /* * Now go through again and allocate region numbers. */ pos = 0; for (i = 0; i < wh; i++) map[i] = -1; for (i = 0; i < wh; i++) { k = dsf_canonify(map+wh, i); if (map[k] < 0) map[k] = pos++; map[i] = map[k]; } if (pos != n) return "Edge list defines the wrong number of regions"; *desc = p; return NULL; } static char *validate_desc(game_params *params, char *desc) { int w = params->w, h = params->h, wh = w*h, n = params->n; int area; int *map; char *ret; map = snewn(2*wh, int); ret = parse_edge_list(params, &desc, map); if (ret) return ret; sfree(map); if (*desc != ',') return "Expected comma before clue list"; desc++; /* eat comma */ area = 0; while (*desc) { if (*desc >= '0' && *desc < '0'+FOUR) area++; else if (*desc >= 'a' && *desc <= 'z') area += *desc - 'a' + 1; else return "Unexpected character in clue list"; desc++; } if (area < n) return "Too little data in clue list"; else if (area > n) return "Too much data in clue list"; return NULL; } static game_state *new_game(midend *me, game_params *params, char *desc) { int w = params->w, h = params->h, wh = w*h, n = params->n; int i, pos; char *p; game_state *state = snew(game_state); state->p = *params; state->colouring = snewn(n, int); for (i = 0; i < n; i++) state->colouring[i] = -1; state->completed = state->cheated = FALSE; state->map = snew(struct map); state->map->refcount = 1; state->map->map = snewn(wh*4, int); state->map->graph = snewn(n*n, int); state->map->n = n; state->map->immutable = snewn(n, int); for (i = 0; i < n; i++) state->map->immutable[i] = FALSE; p = desc; { char *ret; ret = parse_edge_list(params, &p, state->map->map); assert(!ret); } /* * Set up the other three quadrants in `map'. */ for (i = wh; i < 4*wh; i++) state->map->map[i] = state->map->map[i % wh]; assert(*p == ','); p++; /* * Now process the clue list. */ pos = 0; while (*p) { if (*p >= '0' && *p < '0'+FOUR) { state->colouring[pos] = *p - '0'; state->map->immutable[pos] = TRUE; pos++; } else { assert(*p >= 'a' && *p <= 'z'); pos += *p - 'a' + 1; } p++; } assert(pos == n); state->map->ngraph = gengraph(w, h, n, state->map->map, state->map->graph); /* * Attempt to smooth out some of the more jagged region * outlines by the judicious use of diagonally divided squares. */ { random_state *rs = random_init(desc, strlen(desc)); int *squares = snewn(wh, int); int done_something; for (i = 0; i < wh; i++) squares[i] = i; shuffle(squares, wh, sizeof(*squares), rs); do { done_something = FALSE; for (i = 0; i < wh; i++) { int y = squares[i] / w, x = squares[i] % w; int c = state->map->map[y*w+x]; int tc, bc, lc, rc; if (x == 0 || x == w-1 || y == 0 || y == h-1) continue; if (state->map->map[TE * wh + y*w+x] != state->map->map[BE * wh + y*w+x]) continue; tc = state->map->map[BE * wh + (y-1)*w+x]; bc = state->map->map[TE * wh + (y+1)*w+x]; lc = state->map->map[RE * wh + y*w+(x-1)]; rc = state->map->map[LE * wh + y*w+(x+1)]; /* * If this square is adjacent on two sides to one * region and on the other two sides to the other * region, and is itself one of the two regions, we can * adjust it so that it's a diagonal. */ if (tc != bc && (tc == c || bc == c)) { if ((lc == tc && rc == bc) || (lc == bc && rc == tc)) { state->map->map[TE * wh + y*w+x] = tc; state->map->map[BE * wh + y*w+x] = bc; state->map->map[LE * wh + y*w+x] = lc; state->map->map[RE * wh + y*w+x] = rc; done_something = TRUE; } } } } while (done_something); sfree(squares); random_free(rs); } return state; } static game_state *dup_game(game_state *state) { game_state *ret = snew(game_state); ret->p = state->p; ret->colouring = snewn(state->p.n, int); memcpy(ret->colouring, state->colouring, state->p.n * sizeof(int)); ret->map = state->map; ret->map->refcount++; ret->completed = state->completed; ret->cheated = state->cheated; return ret; } static void free_game(game_state *state) { if (--state->map->refcount <= 0) { sfree(state->map->map); sfree(state->map->graph); sfree(state->map->immutable); sfree(state->map); } sfree(state->colouring); sfree(state); } static char *solve_game(game_state *state, game_state *currstate, char *aux, char **error) { if (!aux) { /* * Use the solver. */ int *colouring; struct solver_scratch *sc; int sret; int i; char *ret, buf[80]; int retlen, retsize; colouring = snewn(state->map->n, int); memcpy(colouring, state->colouring, state->map->n * sizeof(int)); sc = new_scratch(state->map->graph, state->map->n, state->map->ngraph); sret = map_solver(sc, state->map->graph, state->map->n, state->map->ngraph, colouring, DIFFCOUNT-1); free_scratch(sc); if (sret != 1) { sfree(colouring); if (sret == 0) *error = "Puzzle is inconsistent"; else *error = "Unable to find a unique solution for this puzzle"; return NULL; } retsize = 64; ret = snewn(retsize, char); strcpy(ret, "S"); retlen = 1; for (i = 0; i < state->map->n; i++) { int len; assert(colouring[i] >= 0); if (colouring[i] == currstate->colouring[i]) continue; assert(!state->map->immutable[i]); len = sprintf(buf, ";%d:%d", colouring[i], i); if (retlen + len >= retsize) { retsize = retlen + len + 256; ret = sresize(ret, retsize, char); } strcpy(ret + retlen, buf); retlen += len; } sfree(colouring); return ret; } return dupstr(aux); } static char *game_text_format(game_state *state) { return NULL; } struct game_ui { int drag_colour; /* -1 means no drag active */ int dragx, dragy; }; static game_ui *new_ui(game_state *state) { game_ui *ui = snew(game_ui); ui->dragx = ui->dragy = -1; ui->drag_colour = -2; return ui; } 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 game_changed_state(game_ui *ui, game_state *oldstate, game_state *newstate) { } struct game_drawstate { int tilesize; unsigned char *drawn; int started; int dragx, dragy, drag_visible; blitter *bl; }; #define TILESIZE (ds->tilesize) #define BORDER (TILESIZE) #define COORD(x) ( (x) * TILESIZE + BORDER ) #define FROMCOORD(x) ( ((x) - BORDER + TILESIZE) / TILESIZE - 1 ) static int region_from_coords(game_state *state, game_drawstate *ds, int x, int y) { int w = state->p.w, h = state->p.h, wh = w*h /*, n = state->p.n */; int tx = FROMCOORD(x), ty = FROMCOORD(y); int dx = x - COORD(tx), dy = y - COORD(ty); int quadrant; if (tx < 0 || tx >= w || ty < 0 || ty >= h) return -1; /* border */ quadrant = 2 * (dx > dy) + (TILESIZE - dx > dy); quadrant = (quadrant == 0 ? BE : quadrant == 1 ? LE : quadrant == 2 ? RE : TE); return state->map->map[quadrant * wh + ty*w+tx]; } static char *interpret_move(game_state *state, game_ui *ui, game_drawstate *ds, int x, int y, int button) { char buf[80]; if (button == LEFT_BUTTON || button == RIGHT_BUTTON) { int r = region_from_coords(state, ds, x, y); if (r >= 0) ui->drag_colour = state->colouring[r]; else ui->drag_colour = -1; ui->dragx = x; ui->dragy = y; return ""; } if ((button == LEFT_DRAG || button == RIGHT_DRAG) && ui->drag_colour > -2) { ui->dragx = x; ui->dragy = y; return ""; } if ((button == LEFT_RELEASE || button == RIGHT_RELEASE) && ui->drag_colour > -2) { int r = region_from_coords(state, ds, x, y); int c = ui->drag_colour; /* * Cancel the drag, whatever happens. */ ui->drag_colour = -2; ui->dragx = ui->dragy = -1; if (r < 0) return ""; /* drag into border; do nothing else */ if (state->map->immutable[r]) return ""; /* can't change this region */ if (state->colouring[r] == c) return ""; /* don't _need_ to change this region */ sprintf(buf, "%c:%d", (int)(c < 0 ? 'C' : '0' + c), r); return dupstr(buf); } return NULL; } static game_state *execute_move(game_state *state, char *move) { int n = state->p.n; game_state *ret = dup_game(state); int c, k, adv, i; while (*move) { c = *move; if ((c == 'C' || (c >= '0' && c < '0'+FOUR)) && sscanf(move+1, ":%d%n", &k, &adv) == 1 && k >= 0 && k < state->p.n) { move += 1 + adv; ret->colouring[k] = (c == 'C' ? -1 : c - '0'); } else if (*move == 'S') { move++; ret->cheated = TRUE; } else { free_game(ret); return NULL; } if (*move && *move != ';') { free_game(ret); return NULL; } if (*move) move++; } /* * Check for completion. */ if (!ret->completed) { int ok = TRUE; for (i = 0; i < n; i++) if (ret->colouring[i] < 0) { ok = FALSE; break; } if (ok) { for (i = 0; i < ret->map->ngraph; i++) { int j = ret->map->graph[i] / n; int k = ret->map->graph[i] % n; if (ret->colouring[j] == ret->colouring[k]) { ok = FALSE; break; } } } if (ok) ret->completed = TRUE; } return ret; } /* ---------------------------------------------------------------------- * Drawing routines. */ static void game_compute_size(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 = params->w * TILESIZE + 2 * BORDER + 1; *y = params->h * TILESIZE + 2 * BORDER + 1; } static void game_set_size(drawing *dr, game_drawstate *ds, game_params *params, int tilesize) { ds->tilesize = tilesize; if (ds->bl) blitter_free(dr, ds->bl); ds->bl = blitter_new(dr, TILESIZE+3, TILESIZE+3); } const float map_colours[FOUR][3] = { {0.7F, 0.5F, 0.4F}, {0.8F, 0.7F, 0.4F}, {0.5F, 0.6F, 0.4F}, {0.55F, 0.45F, 0.35F}, }; const int map_hatching[FOUR] = { HATCH_VERT, HATCH_SLASH, HATCH_HORIZ, HATCH_BACKSLASH }; static float *game_colours(frontend *fe, game_state *state, int *ncolours) { float *ret = snewn(3 * NCOLOURS, float); frontend_default_colour(fe, &ret[COL_BACKGROUND * 3]); ret[COL_GRID * 3 + 0] = 0.0F; ret[COL_GRID * 3 + 1] = 0.0F; ret[COL_GRID * 3 + 2] = 0.0F; memcpy(ret + COL_0 * 3, map_colours[0], 3 * sizeof(float)); memcpy(ret + COL_1 * 3, map_colours[1], 3 * sizeof(float)); memcpy(ret + COL_2 * 3, map_colours[2], 3 * sizeof(float)); memcpy(ret + COL_3 * 3, map_colours[3], 3 * sizeof(float)); *ncolours = NCOLOURS; return ret; } static game_drawstate *game_new_drawstate(drawing *dr, game_state *state) { struct game_drawstate *ds = snew(struct game_drawstate); ds->tilesize = 0; ds->drawn = snewn(state->p.w * state->p.h, unsigned char); memset(ds->drawn, 0xFF, state->p.w * state->p.h); ds->started = FALSE; ds->bl = NULL; ds->drag_visible = FALSE; ds->dragx = ds->dragy = -1; return ds; } static void game_free_drawstate(drawing *dr, game_drawstate *ds) { sfree(ds->drawn); if (ds->bl) blitter_free(dr, ds->bl); sfree(ds); } static void draw_square(drawing *dr, game_drawstate *ds, game_params *params, struct map *map, int x, int y, int v) { int w = params->w, h = params->h, wh = w*h; int tv = v / FIVE, bv = v % FIVE; clip(dr, COORD(x), COORD(y), TILESIZE, TILESIZE); /* * Draw the region colour. */ draw_rect(dr, COORD(x), COORD(y), TILESIZE, TILESIZE, (tv == FOUR ? COL_BACKGROUND : COL_0 + tv)); /* * Draw the second region colour, if this is a diagonally * divided square. */ if (map->map[TE * wh + y*w+x] != map->map[BE * wh + y*w+x]) { int coords[6]; coords[0] = COORD(x)-1; coords[1] = COORD(y+1)+1; if (map->map[LE * wh + y*w+x] == map->map[TE * wh + y*w+x]) coords[2] = COORD(x+1)+1; else coords[2] = COORD(x)-1; coords[3] = COORD(y)-1; coords[4] = COORD(x+1)+1; coords[5] = COORD(y+1)+1; draw_polygon(dr, coords, 3, (bv == FOUR ? COL_BACKGROUND : COL_0 + bv), COL_GRID); } /* * Draw the grid lines, if required. */ if (x <= 0 || map->map[RE*wh+y*w+(x-1)] != map->map[LE*wh+y*w+x]) draw_rect(dr, COORD(x), COORD(y), 1, TILESIZE, COL_GRID); if (y <= 0 || map->map[BE*wh+(y-1)*w+x] != map->map[TE*wh+y*w+x]) draw_rect(dr, COORD(x), COORD(y), TILESIZE, 1, COL_GRID); if (x <= 0 || y <= 0 || map->map[RE*wh+(y-1)*w+(x-1)] != map->map[TE*wh+y*w+x] || map->map[BE*wh+(y-1)*w+(x-1)] != map->map[LE*wh+y*w+x]) draw_rect(dr, COORD(x), COORD(y), 1, 1, COL_GRID); unclip(dr); draw_update(dr, COORD(x), COORD(y), TILESIZE, TILESIZE); } 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 w = state->p.w, h = state->p.h, wh = w*h /*, n = state->p.n */; int x, y; int flash; if (ds->drag_visible) { blitter_load(dr, ds->bl, ds->dragx, ds->dragy); draw_update(dr, ds->dragx, ds->dragy, TILESIZE + 3, TILESIZE + 3); ds->drag_visible = FALSE; } /* * The initial contents of the window are not guaranteed and * can vary with front ends. To be on the safe side, all games * should start by drawing a big background-colour rectangle * covering the whole window. */ if (!ds->started) { int ww, wh; game_compute_size(&state->p, TILESIZE, &ww, &wh); draw_rect(dr, 0, 0, ww, wh, COL_BACKGROUND); draw_rect(dr, COORD(0), COORD(0), w*TILESIZE+1, h*TILESIZE+1, COL_GRID); draw_update(dr, 0, 0, ww, wh); ds->started = TRUE; } if (flashtime) { if (flash_type == 1) flash = (int)(flashtime * FOUR / flash_length); else flash = 1 + (int)(flashtime * THREE / flash_length); } else flash = -1; for (y = 0; y < h; y++) for (x = 0; x < w; x++) { int tv = state->colouring[state->map->map[TE * wh + y*w+x]]; int bv = state->colouring[state->map->map[BE * wh + y*w+x]]; int v; if (tv < 0) tv = FOUR; if (bv < 0) bv = FOUR; if (flash >= 0) { if (flash_type == 1) { if (tv == flash) tv = FOUR; if (bv == flash) bv = FOUR; } else if (flash_type == 2) { if (flash % 2) tv = bv = FOUR; } else { if (tv != FOUR) tv = (tv + flash) % FOUR; if (bv != FOUR) bv = (bv + flash) % FOUR; } } v = tv * FIVE + bv; if (ds->drawn[y*w+x] != v) { draw_square(dr, ds, &state->p, state->map, x, y, v); ds->drawn[y*w+x] = v; } } /* * Draw the dragged colour blob if any. */ if (ui->drag_colour > -2) { ds->dragx = ui->dragx - TILESIZE/2 - 2; ds->dragy = ui->dragy - TILESIZE/2 - 2; blitter_save(dr, ds->bl, ds->dragx, ds->dragy); draw_circle(dr, ui->dragx, ui->dragy, TILESIZE/2, (ui->drag_colour < 0 ? COL_BACKGROUND : COL_0 + ui->drag_colour), COL_GRID); draw_update(dr, ds->dragx, ds->dragy, TILESIZE + 3, TILESIZE + 3); ds->drag_visible = TRUE; } } static float game_anim_length(game_state *oldstate, game_state *newstate, int dir, game_ui *ui) { return 0.0F; } static float game_flash_length(game_state *oldstate, game_state *newstate, int dir, game_ui *ui) { if (!oldstate->completed && newstate->completed && !oldstate->cheated && !newstate->cheated) { if (flash_type < 0) { char *env = getenv("MAP_ALTERNATIVE_FLASH"); if (env) flash_type = atoi(env); else flash_type = 0; flash_length = (flash_type == 1 ? 0.50 : 0.30); } return flash_length; } else return 0.0F; } static int game_wants_statusbar(void) { return FALSE; } 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) { int pw, ph; /* * I'll use 4mm squares by default, I think. Simplest way to * compute this size is to compute the pixel puzzle size at a * given tile size and then scale. */ game_compute_size(params, 400, &pw, &ph); *x = pw / 100.0; *y = ph / 100.0; } static void game_print(drawing *dr, game_state *state, int tilesize) { int w = state->p.w, h = state->p.h, wh = w*h, n = state->p.n; int ink, c[FOUR], i; int x, y, r; int *coords, ncoords, coordsize; /* Ick: fake up `ds->tilesize' for macro expansion purposes */ struct { int tilesize; } ads, *ds = &ads; ads.tilesize = tilesize; ink = print_mono_colour(dr, 0); for (i = 0; i < FOUR; i++) c[i] = print_rgb_colour(dr, map_hatching[i], map_colours[i][0], map_colours[i][1], map_colours[i][2]); coordsize = 0; coords = NULL; print_line_width(dr, TILESIZE / 16); /* * Draw a single filled polygon around each region. */ for (r = 0; r < n; r++) { int octants[8], lastdir, d1, d2, ox, oy; /* * Start by finding a point on the region boundary. Any * point will do. To do this, we'll search for a square * containing the region and then decide which corner of it * to use. */ x = w; for (y = 0; y < h; y++) { for (x = 0; x < w; x++) { if (state->map->map[wh*0+y*w+x] == r || state->map->map[wh*1+y*w+x] == r || state->map->map[wh*2+y*w+x] == r || state->map->map[wh*3+y*w+x] == r) break; } if (x < w) break; } assert(y < h && x < w); /* we must have found one somewhere */ /* * This is the first square in lexicographic order which * contains part of this region. Therefore, one of the top * two corners of the square must be what we're after. The * only case in which it isn't the top left one is if the * square is diagonally divided and the region is in the * bottom right half. */ if (state->map->map[wh*TE+y*w+x] != r && state->map->map[wh*LE+y*w+x] != r) x++; /* could just as well have done y++ */ /* * Now we have a point on the region boundary. Trace around * the region until we come back to this point, * accumulating coordinates for a polygon draw operation as * we go. */ lastdir = -1; ox = x; oy = y; ncoords = 0; do { /* * There are eight possible directions we could head in * from here. We identify them by octant numbers, and * we also use octant numbers to identify the spaces * between them: * * 6 7 0 * \ 7|0 / * \ | / * 6 \|/ 1 * 5-----+-----1 * 5 /|\ 2 * / | \ * / 4|3 \ * 4 3 2 */ octants[0] = x0 ? state->map->map[wh*LE+(y-1)*w+x] : -1; octants[1] = x0 ? state->map->map[wh*BE+(y-1)*w+x] : -1; octants[2] = xmap->map[wh*TE+y*w+x] : -1; octants[3] = xmap->map[wh*LE+y*w+x] : -1; octants[4] = x>0 && ymap->map[wh*RE+y*w+(x-1)] : -1; octants[5] = x>0 && ymap->map[wh*TE+y*w+(x-1)] : -1; octants[6] = x>0 && y>0 ? state->map->map[wh*BE+(y-1)*w+(x-1)] :-1; octants[7] = x>0 && y>0 ? state->map->map[wh*RE+(y-1)*w+(x-1)] :-1; d1 = d2 = -1; for (i = 0; i < 8; i++) if ((octants[i] == r) ^ (octants[(i+1)%8] == r)) { assert(d2 == -1); if (d1 == -1) d1 = i; else d2 = i; } /* printf("%% %d,%d r=%d: d1=%d d2=%d lastdir=%d\n", x, y, r, d1, d2, lastdir); */ assert(d1 != -1 && d2 != -1); if (d1 == lastdir) d1 = d2; /* * Now we're heading in direction d1. Save the current * coordinates. */ if (ncoords + 2 > coordsize) { coordsize += 128; coords = sresize(coords, coordsize, int); } coords[ncoords++] = COORD(x); coords[ncoords++] = COORD(y); /* * Compute the new coordinates. */ x += (d1 % 4 == 3 ? 0 : d1 < 4 ? +1 : -1); y += (d1 % 4 == 1 ? 0 : d1 > 1 && d1 < 5 ? +1 : -1); assert(x >= 0 && x <= w && y >= 0 && y <= h); lastdir = d1 ^ 4; } while (x != ox || y != oy); draw_polygon(dr, coords, ncoords/2, state->colouring[r] >= 0 ? c[state->colouring[r]] : -1, ink); } sfree(coords); } #ifdef COMBINED #define thegame map #endif const struct game thegame = { "Map", "games.map", default_params, game_fetch_preset, 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, FALSE, game_text_format, new_ui, free_ui, encode_ui, decode_ui, game_changed_state, interpret_move, execute_move, 20, game_compute_size, game_set_size, game_colours, game_new_drawstate, game_free_drawstate, game_redraw, game_anim_length, game_flash_length, TRUE, TRUE, game_print_size, game_print, game_wants_statusbar, FALSE, game_timing_state, 0, /* mouse_priorities */ }; id='n1522' href='#n1522'>1522 1523 1524 1525 1526 1527 1528 1529 1530 1531 1532 1533 1534 1535 1536 1537 1538 1539 1540 1541 1542 1543 1544 1545 1546 1547 1548 1549 1550 1551 1552 1553 1554 1555 1556 1557 1558 1559 1560 1561 1562 1563 1564 1565 1566 1567 1568 1569 1570 1571 1572 1573 1574 1575 1576 1577 1578 1579 1580 1581 1582 1583 1584 1585 1586 1587 1588 1589 1590 1591 1592 1593 1594 1595 1596 1597 1598 1599 1600 1601 1602 1603 1604 1605 1606 1607 1608 1609 1610 1611 1612 1613 1614 1615 1616 1617 1618 1619 1620 1621 1622 1623 1624 1625 1626 1627 1628 1629 1630 1631 1632 1633 1634 1635 1636 1637 1638 1639 1640 1641 1642 1643 1644 1645 1646 1647 1648 1649 1650 1651 1652 1653 1654 1655 1656 1657 1658 1659 1660 1661 1662 1663 1664 1665 1666 1667 1668 1669 1670 1671 1672 1673 1674 1675 1676 1677 1678 1679 1680 1681 1682 1683 1684 1685 1686 1687 1688 1689 1690 1691 1692 1693 1694 1695 1696 1697 1698 1699 1700 1701 1702 1703 1704 1705 1706 1707 1708 1709 1710 1711 1712 1713 1714 1715 1716 1717 1718 1719 1720 1721 1722 1723 1724 1725 1726 1727 1728 1729 1730 1731 1732 1733 1734 1735 1736 1737 1738 1739 1740 1741 1742 1743 1744 1745 1746 1747 1748 1749 1750 1751 1752 1753 1754 1755 1756 1757 1758 1759 1760 1761 1762 1763 1764 1765 1766 1767 1768 1769 1770 
/*
 * cube.c: Cube game.
 */

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <assert.h>
#include <ctype.h>
#include <math.h>

#include "puzzles.h"

#define MAXVERTICES 20
#define MAXFACES 20
#define MAXORDER 4
struct solid {
    int nvertices;
    float vertices[MAXVERTICES * 3];   /* 3*npoints coordinates */
    int order;
    int nfaces;
    int faces[MAXFACES * MAXORDER];    /* order*nfaces point indices */
    float normals[MAXFACES * 3];       /* 3*npoints vector components */
    float shear;                       /* isometric shear for nice drawing */
    float border;                      /* border required around arena */
};

static const struct solid s_tetrahedron = {
    4,
    {
        0.0F, -0.57735026919F, -0.20412414523F,
        -0.5F, 0.28867513459F, -0.20412414523F,
        0.0F, -0.0F, 0.6123724357F,
        0.5F, 0.28867513459F, -0.20412414523F,
    },
    3, 4,
    {
        0,2,1, 3,1,2, 2,0,3, 1,3,0
    },
    {
        -0.816496580928F, -0.471404520791F, 0.333333333334F,
        0.0F, 0.942809041583F, 0.333333333333F,
        0.816496580928F, -0.471404520791F, 0.333333333334F,
        0.0F, 0.0F, -1.0F,
    },
    0.0F, 0.3F
};

static const struct solid s_cube = {
    8,
    {
        -0.5F,-0.5F,-0.5F, -0.5F,-0.5F,+0.5F,
	-0.5F,+0.5F,-0.5F, -0.5F,+0.5F,+0.5F,
        +0.5F,-0.5F,-0.5F, +0.5F,-0.5F,+0.5F,
	+0.5F,+0.5F,-0.5F, +0.5F,+0.5F,+0.5F,
    },
    4, 6,
    {
        0,1,3,2, 1,5,7,3, 5,4,6,7, 4,0,2,6, 0,4,5,1, 3,7,6,2
    },
    {
        -1.0F,0.0F,0.0F, 0.0F,0.0F,+1.0F,
	+1.0F,0.0F,0.0F, 0.0F,0.0F,-1.0F,
	0.0F,-1.0F,0.0F, 0.0F,+1.0F,0.0F
    },
    0.3F, 0.5F
};

static const struct solid s_octahedron = {
    6,
    {
        -0.5F, -0.28867513459472505F, 0.4082482904638664F,
        0.5F, 0.28867513459472505F, -0.4082482904638664F,
        -0.5F, 0.28867513459472505F, -0.4082482904638664F,
        0.5F, -0.28867513459472505F, 0.4082482904638664F,
        0.0F, -0.57735026918945009F, -0.4082482904638664F,
        0.0F, 0.57735026918945009F, 0.4082482904638664F,
    },
    3, 8,
    {
        4,0,2, 0,5,2, 0,4,3, 5,0,3, 1,4,2, 5,1,2, 4,1,3, 1,5,3
    },
    {
        -0.816496580928F, -0.471404520791F, -0.333333333334F,
        -0.816496580928F, 0.471404520791F, 0.333333333334F,
        0.0F, -0.942809041583F, 0.333333333333F,
        0.0F, 0.0F, 1.0F,
        0.0F, 0.0F, -1.0F,
        0.0F, 0.942809041583F, -0.333333333333F,
        0.816496580928F, -0.471404520791F, -0.333333333334F,
        0.816496580928F, 0.471404520791F, 0.333333333334F,
    },
    0.0F, 0.5F
};

static const struct solid s_icosahedron = {
    12,
    {
        0.0F, 0.57735026919F, 0.75576131408F,
        0.0F, -0.93417235896F, 0.17841104489F,
        0.0F, 0.93417235896F, -0.17841104489F,
        0.0F, -0.57735026919F, -0.75576131408F,
        -0.5F, -0.28867513459F, 0.75576131408F,
        -0.5F, 0.28867513459F, -0.75576131408F,
        0.5F, -0.28867513459F, 0.75576131408F,
        0.5F, 0.28867513459F, -0.75576131408F,
        -0.80901699437F, 0.46708617948F, 0.17841104489F,
        0.80901699437F, 0.46708617948F, 0.17841104489F,
        -0.80901699437F, -0.46708617948F, -0.17841104489F,
        0.80901699437F, -0.46708617948F, -0.17841104489F,
    },
    3, 20,
    {
        8,0,2,  0,9,2,  1,10,3, 11,1,3,  0,4,6,
        4,1,6,  5,2,7,  3,5,7,  4,8,10,  8,5,10,
        9,6,11, 7,9,11,  0,8,4,  9,0,6,  10,1,4,
        1,11,6, 8,2,5,  2,9,7,  3,10,5, 11,3,7,
    },
    {
        -0.356822089773F, 0.87267799625F, 0.333333333333F,
        0.356822089773F, 0.87267799625F, 0.333333333333F,
        -0.356822089773F, -0.87267799625F, -0.333333333333F,
        0.356822089773F, -0.87267799625F, -0.333333333333F,
        -0.0F, 0.0F, 1.0F,
        0.0F, -0.666666666667F, 0.745355992501F,
        0.0F, 0.666666666667F, -0.745355992501F,
        0.0F, 0.0F, -1.0F,
        -0.934172358963F, -0.12732200375F, 0.333333333333F,
        -0.934172358963F, 0.12732200375F, -0.333333333333F,
        0.934172358963F, -0.12732200375F, 0.333333333333F,
        0.934172358963F, 0.12732200375F, -0.333333333333F,
        -0.57735026919F, 0.333333333334F, 0.745355992501F,
        0.57735026919F, 0.333333333334F, 0.745355992501F,
        -0.57735026919F, -0.745355992501F, 0.333333333334F,
        0.57735026919F, -0.745355992501F, 0.333333333334F,
        -0.57735026919F, 0.745355992501F, -0.333333333334F,
        0.57735026919F, 0.745355992501F, -0.333333333334F,
        -0.57735026919F, -0.333333333334F, -0.745355992501F,
        0.57735026919F, -0.333333333334F, -0.745355992501F,
    },
    0.0F, 0.8F
};

enum {
    TETRAHEDRON, CUBE, OCTAHEDRON, ICOSAHEDRON
};
static const struct solid *solids[] = {
    &s_tetrahedron, &s_cube, &s_octahedron, &s_icosahedron
};

enum {
    COL_BACKGROUND,
    COL_BORDER,
    COL_BLUE,
    NCOLOURS
};

enum { LEFT, RIGHT, UP, DOWN, UP_LEFT, UP_RIGHT, DOWN_LEFT, DOWN_RIGHT };

#define PREFERRED_GRID_SCALE 48
#define GRID_SCALE (ds->gridscale)
#define ROLLTIME 0.13F

#define SQ(x) ( (x) * (x) )

#define MATMUL(ra,m,a) do { \
    float rx, ry, rz, xx = (a)[0], yy = (a)[1], zz = (a)[2], *mat = (m); \
    rx = mat[0] * xx + mat[3] * yy + mat[6] * zz; \
    ry = mat[1] * xx + mat[4] * yy + mat[7] * zz; \
    rz = mat[2] * xx + mat[5] * yy + mat[8] * zz; \
    (ra)[0] = rx; (ra)[1] = ry; (ra)[2] = rz; \
} while (0)

#define APPROXEQ(x,y) ( SQ(x-y) < 0.1 )

struct grid_square {
    float x, y;
    int npoints;
    float points[8];                   /* maximum */
    int directions[8];                 /* bit masks showing point pairs */
    bool flip;
    int tetra_class;
};

struct game_params {
    int solid;
    /*
     * Grid dimensions. For a square grid these are width and
     * height respectively; otherwise the grid is a hexagon, with
     * the top side and the two lower diagonals having length d1
     * and the remaining three sides having length d2 (so that
     * d1==d2 gives a regular hexagon, and d2==0 gives a triangle).
     */
    int d1, d2;
};

typedef struct game_grid game_grid;
struct game_grid {
    int refcount;
    struct grid_square *squares;
    int nsquares;
};

#define SET_SQUARE(state, i, val) \
    ((state)->bluemask[(i)/32] &= ~(1 << ((i)%32)), \
     (state)->bluemask[(i)/32] |= ((!!val) << ((i)%32)))
#define GET_SQUARE(state, i) \
    (((state)->bluemask[(i)/32] >> ((i)%32)) & 1)

struct game_state {
    struct game_params params;
    const struct solid *solid;
    int *facecolours;
    game_grid *grid;
    unsigned long *bluemask;
    int current;                       /* index of current grid square */
    int sgkey[2];                      /* key-point indices into grid sq */
    int dgkey[2];                      /* key-point indices into grid sq */
    int spkey[2];                      /* key-point indices into polyhedron */
    int dpkey[2];                      /* key-point indices into polyhedron */
    int previous;
    float angle;
    int completed;                     /* stores move count at completion */
    int movecount;
};

static game_params *default_params(void)
{
    game_params *ret = snew(game_params);

    ret->solid = CUBE;
    ret->d1 = 4;
    ret->d2 = 4;

    return ret;
}

static bool game_fetch_preset(int i, char **name, game_params **params)
{
    game_params *ret = snew(game_params);
    const char *str;

    switch (i) {
      case 0:
        str = "Cube";
        ret->solid = CUBE;
        ret->d1 = 4;
        ret->d2 = 4;
        break;
      case 1:
        str = "Tetrahedron";
        ret->solid = TETRAHEDRON;
        ret->d1 = 1;
        ret->d2 = 2;
        break;
      case 2:
        str = "Octahedron";
        ret->solid = OCTAHEDRON;
        ret->d1 = 2;
        ret->d2 = 2;
        break;
      case 3:
        str = "Icosahedron";
        ret->solid = ICOSAHEDRON;
        ret->d1 = 3;
        ret->d2 = 3;
        break;
      default:
        sfree(ret);
        return false;
    }

    *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)
{
    switch (*string) {
      case 't': ret->solid = TETRAHEDRON; string++; break;
      case 'c': ret->solid = CUBE;        string++; break;
      case 'o': ret->solid = OCTAHEDRON;  string++; break;
      case 'i': ret->solid = ICOSAHEDRON; string++; break;
      default: break;
    }
    ret->d1 = ret->d2 = atoi(string);
    while (*string && isdigit((unsigned char)*string)) string++;
    if (*string == 'x') {
        string++;
        ret->d2 = atoi(string);
    }
}

static char *encode_params(const game_params *params, bool full)
{
    char data[256];

    assert(params->solid >= 0 && params->solid < 4);
    sprintf(data, "%c%dx%d", "tcoi"[params->solid], params->d1, params->d2);

    return dupstr(data);
}
typedef void (*egc_callback)(void *, struct grid_square *);

static void enum_grid_squares(const game_params *params, egc_callback callback,
                              void *ctx)
{
    const struct solid *solid = solids[params->solid];

    if (solid->order == 4) {
        int x, y;

	for (y = 0; y < params->d2; y++)
	    for (x = 0; x < params->d1; x++) {
                struct grid_square sq;

                sq.x = (float)x;
                sq.y = (float)y;
                sq.points[0] = x - 0.5F;
                sq.points[1] = y - 0.5F;
                sq.points[2] = x - 0.5F;
                sq.points[3] = y + 0.5F;
                sq.points[4] = x + 0.5F;
                sq.points[5] = y + 0.5F;
                sq.points[6] = x + 0.5F;
                sq.points[7] = y - 0.5F;
                sq.npoints = 4;

                sq.directions[LEFT]  = 0x03;   /* 0,1 */
                sq.directions[RIGHT] = 0x0C;   /* 2,3 */
                sq.directions[UP]    = 0x09;   /* 0,3 */
                sq.directions[DOWN]  = 0x06;   /* 1,2 */
                sq.directions[UP_LEFT] = 0;   /* no diagonals in a square */
                sq.directions[UP_RIGHT] = 0;   /* no diagonals in a square */
                sq.directions[DOWN_LEFT] = 0;   /* no diagonals in a square */
                sq.directions[DOWN_RIGHT] = 0;   /* no diagonals in a square */

                sq.flip = false;

                /*
                 * This is supremely irrelevant, but just to avoid
                 * having any uninitialised structure members...
                 */
                sq.tetra_class = 0;

                callback(ctx, &sq);
            }
    } else {
        int row, rowlen, other, i, firstix = -1;
        float theight = (float)(sqrt(3) / 2.0);

        for (row = 0; row < params->d1 + params->d2; row++) {
            if (row < params->d2) {
                other = +1;
                rowlen = row + params->d1;
            } else {
                other = -1;
                rowlen = 2*params->d2 + params->d1 - row;
            }

            /*
             * There are `rowlen' down-pointing triangles.
             */
            for (i = 0; i < rowlen; i++) {
                struct grid_square sq;
                int ix;
                float x, y;

                ix = (2 * i - (rowlen-1));
                x = ix * 0.5F;
                y = theight * row;
                sq.x = x;
                sq.y = y + theight / 3;
                sq.points[0] = x - 0.5F;
                sq.points[1] = y;
                sq.points[2] = x;
                sq.points[3] = y + theight;
                sq.points[4] = x + 0.5F;
                sq.points[5] = y;
                sq.npoints = 3;

                sq.directions[LEFT]  = 0x03;   /* 0,1 */
                sq.directions[RIGHT] = 0x06;   /* 1,2 */
                sq.directions[UP]    = 0x05;   /* 0,2 */
                sq.directions[DOWN]  = 0;      /* invalid move */

                /*
                 * Down-pointing triangle: both the up diagonals go
                 * up, and the down ones go left and right.
                 */
                sq.directions[UP_LEFT] = sq.directions[UP_RIGHT] =
                    sq.directions[UP];
                sq.directions[DOWN_LEFT] = sq.directions[LEFT];
                sq.directions[DOWN_RIGHT] = sq.directions[RIGHT];

                sq.flip = true;

                if (firstix < 0)
                    firstix = ix & 3;
                ix -= firstix;
                sq.tetra_class = ((row+(ix&1)) & 2) ^ (ix & 3);

                callback(ctx, &sq);
            }

            /*
             * There are `rowlen+other' up-pointing triangles.
             */
            for (i = 0; i < rowlen+other; i++) {
                struct grid_square sq;
                int ix;
                float x, y;

                ix = (2 * i - (rowlen+other-1));
                x = ix * 0.5F;
                y = theight * row;
                sq.x = x;
                sq.y = y + 2*theight / 3;
                sq.points[0] = x + 0.5F;
                sq.points[1] = y + theight;
                sq.points[2] = x;
                sq.points[3] = y;
                sq.points[4] = x - 0.5F;
                sq.points[5] = y + theight;
                sq.npoints = 3;

                sq.directions[LEFT]  = 0x06;   /* 1,2 */
                sq.directions[RIGHT] = 0x03;   /* 0,1 */
                sq.directions[DOWN]  = 0x05;   /* 0,2 */
                sq.directions[UP]    = 0;      /* invalid move */

                /*
                 * Up-pointing triangle: both the down diagonals go
                 * down, and the up ones go left and right.
                 */
                sq.directions[DOWN_LEFT] = sq.directions[DOWN_RIGHT] =
                    sq.directions[DOWN];
                sq.directions[UP_LEFT] = sq.directions[LEFT];
                sq.directions[UP_RIGHT] = sq.directions[RIGHT];

                sq.flip = false;

                if (firstix < 0)
                    firstix = (ix - 1) & 3;
                ix -= firstix;
                sq.tetra_class = ((row+(ix&1)) & 2) ^ (ix & 3);

                callback(ctx, &sq);
            }
        }
    }
}

static int grid_area(int d1, int d2, int order)
{
    /*
     * An NxM grid of squares has NM squares in it.
     * 
     * A grid of triangles with dimensions A and B has a total of
     * A^2 + B^2 + 4AB triangles in it. (You can divide it up into
     * a side-A triangle containing A^2 subtriangles, a side-B
     * triangle containing B^2, and two congruent parallelograms,
     * each with side lengths A and B, each therefore containing AB
     * two-triangle rhombuses.)
     */
    if (order == 4)
        return d1 * d2;
    else
        return d1*d1 + d2*d2 + 4*d1*d2;
}

static config_item *game_configure(const game_params *params)
{
    config_item *ret = snewn(4, config_item);
    char buf[80];

    ret[0].name = "Type of solid";
    ret[0].type = C_CHOICES;
    ret[0].u.choices.choicenames = ":Tetrahedron:Cube:Octahedron:Icosahedron";
    ret[0].u.choices.selected = params->solid;

    ret[1].name = "Width / top";
    ret[1].type = C_STRING;
    sprintf(buf, "%d", params->d1);
    ret[1].u.string.sval = dupstr(buf);

    ret[2].name = "Height / bottom";
    ret[2].type = C_STRING;
    sprintf(buf, "%d", params->d2);
    ret[2].u.string.sval = dupstr(buf);

    ret[3].name = NULL;
    ret[3].type = C_END;

    return ret;
}

static game_params *custom_params(const config_item *cfg)
{
    game_params *ret = snew(game_params);

    ret->solid = cfg[0].u.choices.selected;
    ret->d1 = atoi(cfg[1].u.string.sval);
    ret->d2 = atoi(cfg[2].u.string.sval);

    return ret;
}

static void count_grid_square_callback(void *ctx, struct grid_square *sq)
{
    int *classes = (int *)ctx;
    int thisclass;

    if (classes[4] == 4)
	thisclass = sq->tetra_class;
    else if (classes[4] == 2)
	thisclass = sq->flip;
    else
	thisclass = 0;

    classes[thisclass]++;
}

static const char *validate_params(const game_params *params, bool full)
{
    int classes[5];
    int i;

    if (params->solid < 0 || params->solid >= lenof(solids))
	return "Unrecognised solid type";

    if (solids[params->solid]->order == 4) {
	if (params->d1 <= 1 || params->d2 <= 1)
	    return "Both grid dimensions must be greater than one";
    } else {
	if (params->d1 <= 0 && params->d2 <= 0)
	    return "At least one grid dimension must be greater than zero";
    }

    for (i = 0; i < 4; i++)
	classes[i] = 0;
    if (params->solid == TETRAHEDRON)
	classes[4] = 4;
    else if (params->solid == OCTAHEDRON)
	classes[4] = 2;
    else
	classes[4] = 1;
    enum_grid_squares(params, count_grid_square_callback, classes);

    for (i = 0; i < classes[4]; i++)
	if (classes[i] < solids[params->solid]->nfaces / classes[4])
	    return "Not enough grid space to place all blue faces";

    if (grid_area(params->d1, params->d2, solids[params->solid]->order) <
	solids[params->solid]->nfaces + 1)
	return "Not enough space to place the solid on an empty square";

    return NULL;
}

struct grid_data {
    int *gridptrs[4];
    int nsquares[4];
    int nclasses;
    int squareindex;
};

static void classify_grid_square_callback(void *ctx, struct grid_square *sq)
{
    struct grid_data *data = (struct grid_data *)ctx;
    int thisclass;

    if (data->nclasses == 4)
	thisclass = sq->tetra_class;
    else if (data->nclasses == 2)
	thisclass = sq->flip;
    else
	thisclass = 0;

    data->gridptrs[thisclass][data->nsquares[thisclass]++] =
	data->squareindex++;
}

static char *new_game_desc(const game_params *params, random_state *rs,
			   char **aux, bool interactive)
{
    struct grid_data data;
    int i, j, k, m, area, facesperclass;
    bool *flags;
    char *desc, *p;

    /*
     * Enumerate the grid squares, dividing them into equivalence
     * classes as appropriate. (For the tetrahedron, there is one
     * equivalence class for each face; for the octahedron there
     * are two classes; for the other two solids there's only one.)
     */

    area = grid_area(params->d1, params->d2, solids[params->solid]->order);
    if (params->solid == TETRAHEDRON)
	data.nclasses = 4;
    else if (params->solid == OCTAHEDRON)
	data.nclasses = 2;
    else
	data.nclasses = 1;
    data.gridptrs[0] = snewn(data.nclasses * area, int);
    for (i = 0; i < data.nclasses; i++) {
	data.gridptrs[i] = data.gridptrs[0] + i * area;
	data.nsquares[i] = 0;
    }
    data.squareindex = 0;
    enum_grid_squares(params, classify_grid_square_callback, &data);

    facesperclass = solids[params->solid]->nfaces / data.nclasses;

    for (i = 0; i < data.nclasses; i++)
	assert(data.nsquares[i] >= facesperclass);
    assert(data.squareindex == area);

    /*
     * So now we know how many faces to allocate in each class. Get
     * on with it.
     */
    flags = snewn(area, bool);
    for (i = 0; i < area; i++)
	flags[i] = false;

    for (i = 0; i < data.nclasses; i++) {
	for (j = 0; j < facesperclass; j++) {
            int n = random_upto(rs, data.nsquares[i]);

	    assert(!flags[data.gridptrs[i][n]]);
	    flags[data.gridptrs[i][n]] = true;

	    /*
	     * Move everything else up the array. I ought to use a
	     * better data structure for this, but for such small
	     * numbers it hardly seems worth the effort.
	     */
	    while (n < data.nsquares[i]-1) {
		data.gridptrs[i][n] = data.gridptrs[i][n+1];
		n++;
	    }
	    data.nsquares[i]--;
	}
    }

    /*
     * Now we know precisely which squares are blue. Encode this
     * information in hex. While we're looping over this, collect
     * the non-blue squares into a list in the now-unused gridptrs
     * array.
     */
    desc = snewn(area / 4 + 40, char);
    p = desc;
    j = 0;
    k = 8;
    m = 0;
    for (i = 0; i < area; i++) {
	if (flags[i]) {
	    j |= k;
	} else {
	    data.gridptrs[0][m++] = i;
	}
	k >>= 1;
	if (!k) {
	    *p++ = "0123456789ABCDEF"[j];
	    k = 8;
	    j = 0;
	}
    }
    if (k != 8)
	*p++ = "0123456789ABCDEF"[j];

    /*
     * Choose a non-blue square for the polyhedron.
     */
    sprintf(p, ",%d", data.gridptrs[0][random_upto(rs, m)]);

    sfree(data.gridptrs[0]);
    sfree(flags);

    return desc;
}

static void add_grid_square_callback(void *ctx, struct grid_square *sq)
{
    game_grid *grid = (game_grid *)ctx;

    grid->squares[grid->nsquares++] = *sq;   /* structure copy */
}

static int lowest_face(const struct solid *solid)
{
    int i, j, best;
    float zmin;

    best = 0;
    zmin = 0.0;
    for (i = 0; i < solid->nfaces; i++) {
        float z = 0;

        for (j = 0; j < solid->order; j++) {
            int f = solid->faces[i*solid->order + j];
            z += solid->vertices[f*3+2];
        }

        if (i == 0 || zmin > z) {
            zmin = z;
            best = i;
        }
    }

    return best;
}

static bool align_poly(const struct solid *solid, struct grid_square *sq,
                       int *pkey)
{
    float zmin;
    int i, j;
    int flip = (sq->flip ? -1 : +1);

    /*
     * First, find the lowest z-coordinate present in the solid.
     */
    zmin = 0.0;
    for (i = 0; i < solid->nvertices; i++)
        if (zmin > solid->vertices[i*3+2])
            zmin = solid->vertices[i*3+2];

    /*
     * Now go round the grid square. For each point in the grid
     * square, we're looking for a point of the polyhedron with the
     * same x- and y-coordinates (relative to the square's centre),
     * and z-coordinate equal to zmin (near enough).
     */
    for (j = 0; j < sq->npoints; j++) {
        int matches, index;

        matches = 0;
        index = -1;

        for (i = 0; i < solid->nvertices; i++) {
            float dist = 0;

            dist += SQ(solid->vertices[i*3+0] * flip - sq->points[j*2+0] + sq->x);
            dist += SQ(solid->vertices[i*3+1] * flip - sq->points[j*2+1] + sq->y);
            dist += SQ(solid->vertices[i*3+2] - zmin);

            if (dist < 0.1) {
                matches++;
                index = i;
            }
        }

        if (matches != 1 || index < 0)
            return false;
        pkey[j] = index;
    }

    return true;
}

static void flip_poly(struct solid *solid, bool flip)
{
    int i;

    if (flip) {
        for (i = 0; i < solid->nvertices; i++) {
            solid->vertices[i*3+0] *= -1;
            solid->vertices[i*3+1] *= -1;
        }
        for (i = 0; i < solid->nfaces; i++) {
            solid->normals[i*3+0] *= -1;
            solid->normals[i*3+1] *= -1;
        }
    }
}

static struct solid *transform_poly(const struct solid *solid, bool flip,
                                    int key0, int key1, float angle)
{
    struct solid *ret = snew(struct solid);
    float vx, vy, ax, ay;
    float vmatrix[9], amatrix[9], vmatrix2[9];
    int i;

    *ret = *solid;                     /* structure copy */

    flip_poly(ret, flip);

    /*
     * Now rotate the polyhedron through the given angle. We must
     * rotate about the Z-axis to bring the two vertices key0 and
     * key1 into horizontal alignment, then rotate about the
     * X-axis, then rotate back again.
     */
    vx = ret->vertices[key1*3+0] - ret->vertices[key0*3+0];
    vy = ret->vertices[key1*3+1] - ret->vertices[key0*3+1];
    assert(APPROXEQ(vx*vx + vy*vy, 1.0));

    vmatrix[0] =  vx; vmatrix[3] = vy; vmatrix[6] = 0;
    vmatrix[1] = -vy; vmatrix[4] = vx; vmatrix[7] = 0;
    vmatrix[2] =   0; vmatrix[5] =  0; vmatrix[8] = 1;

    ax = (float)cos(angle);
    ay = (float)sin(angle);

    amatrix[0] = 1; amatrix[3] =   0; amatrix[6] =  0;
    amatrix[1] = 0; amatrix[4] =  ax; amatrix[7] = ay;
    amatrix[2] = 0; amatrix[5] = -ay; amatrix[8] = ax;

    memcpy(vmatrix2, vmatrix, sizeof(vmatrix));
    vmatrix2[1] = vy;
    vmatrix2[3] = -vy;

    for (i = 0; i < ret->nvertices; i++) {
        MATMUL(ret->vertices + 3*i, vmatrix, ret->vertices + 3*i);
        MATMUL(ret->vertices + 3*i, amatrix, ret->vertices + 3*i);
        MATMUL(ret->vertices + 3*i, vmatrix2, ret->vertices + 3*i);
    }
    for (i = 0; i < ret->nfaces; i++) {
        MATMUL(ret->normals + 3*i, vmatrix, ret->normals + 3*i);
        MATMUL(ret->normals + 3*i, amatrix, ret->normals + 3*i);
        MATMUL(ret->normals + 3*i, vmatrix2, ret->normals + 3*i);
    }

    return ret;
}

static const char *validate_desc(const game_params *params, const char *desc)
{
    int area = grid_area(params->d1, params->d2, solids[params->solid]->order);
    int i, j;

    i = (area + 3) / 4;
    for (j = 0; j < i; j++) {
	int c = desc[j];
	if (c >= '0' && c <= '9') continue;
	if (c >= 'A' && c <= 'F') continue;
	if (c >= 'a' && c <= 'f') continue;
	return "Not enough hex digits at start of string";
	/* NB if desc[j]=='\0' that will also be caught here, so we're safe */
    }

    if (desc[i] != ',')
	return "Expected ',' after hex digits";

    i++;
    do {
	if (desc[i] < '0' || desc[i] > '9')
	    return "Expected decimal integer after ','";
	i++;
    } while (desc[i]);

    return NULL;
}

static game_state *new_game(midend *me, const game_params *params,
                            const char *desc)
{
    game_grid *grid = snew(game_grid);
    game_state *state = snew(game_state);
    int area;

    state->params = *params;           /* structure copy */
    state->solid = solids[params->solid];

    area = grid_area(params->d1, params->d2, state->solid->order);
    grid->squares = snewn(area, struct grid_square);
    grid->nsquares = 0;
    enum_grid_squares(params, add_grid_square_callback, grid);
    assert(grid->nsquares == area);
    state->grid = grid;
    grid->refcount = 1;

    state->facecolours = snewn(state->solid->nfaces, int);
    memset(state->facecolours, 0, state->solid->nfaces * sizeof(int));

    state->bluemask = snewn((state->grid->nsquares + 31) / 32, unsigned long);
    memset(state->bluemask, 0, (state->grid->nsquares + 31) / 32 *
	   sizeof(unsigned long));

    /*
     * Set up the blue squares and polyhedron position according to
     * the game description.
     */
    {
	const char *p = desc;
	int i, j, v;

	j = 8;
	v = 0;
	for (i = 0; i < state->grid->nsquares; i++) {
	    if (j == 8) {
		v = *p++;
		if (v >= '0' && v <= '9')
		    v -= '0';
		else if (v >= 'A' && v <= 'F')
		    v -= 'A' - 10;
		else if (v >= 'a' && v <= 'f')
		    v -= 'a' - 10;
		else
		    break;
	    }
	    if (v & j)
		SET_SQUARE(state, i, true);
	    j >>= 1;
	    if (j == 0)
		j = 8;
	}

	if (*p == ',')
	    p++;

	state->current = atoi(p);
	if (state->current < 0 || state->current >= state->grid->nsquares)
	    state->current = 0;	       /* got to do _something_ */
    }

    /*
     * Align the polyhedron with its grid square and determine
     * initial key points.
     */
    {
        int pkey[4];
        bool ret;

        ret = align_poly(state->solid, &state->grid->squares[state->current], pkey);
        assert(ret);

        state->dpkey[0] = state->spkey[0] = pkey[0];
        state->dpkey[1] = state->spkey[0] = pkey[1];
        state->dgkey[0] = state->sgkey[0] = 0;
        state->dgkey[1] = state->sgkey[0] = 1;
    }

    state->previous = state->current;
    state->angle = 0.0;
    state->completed = 0;
    state->movecount = 0;

    return state;
}

static game_state *dup_game(const game_state *state)
{
    game_state *ret = snew(game_state);

    ret->params = state->params;           /* structure copy */
    ret->solid = state->solid;
    ret->facecolours = snewn(ret->solid->nfaces, int);
    memcpy(ret->facecolours, state->facecolours,
           ret->solid->nfaces * sizeof(int));
    ret->current = state->current;
    ret->grid = state->grid;
    ret->grid->refcount++;
    ret->bluemask = snewn((ret->grid->nsquares + 31) / 32, unsigned long);
    memcpy(ret->bluemask, state->bluemask, (ret->grid->nsquares + 31) / 32 *
	   sizeof(unsigned long));
    ret->dpkey[0] = state->dpkey[0];
    ret->dpkey[1] = state->dpkey[1];
    ret->dgkey[0] = state->dgkey[0];
    ret->dgkey[1] = state->dgkey[1];
    ret->spkey[0] = state->spkey[0];
    ret->spkey[1] = state->spkey[1];
    ret->sgkey[0] = state->sgkey[0];
    ret->sgkey[1] = state->sgkey[1];
    ret->previous = state->previous;
    ret->angle = state->angle;
    ret->completed = state->completed;
    ret->movecount = state->movecount;

    return ret;
}

static void free_game(game_state *state)
{
    if (--state->grid->refcount <= 0) {
	sfree(state->grid->squares);
	sfree(state->grid);
    }
    sfree(state->bluemask);
    sfree(state->facecolours);
    sfree(state);
}

static char *solve_game(const game_state *state, const game_state *currstate,
                        const char *aux, const char **error)
{
    return NULL;
}

static bool game_can_format_as_text_now(const game_params *params)
{
    return true;
}

static char *game_text_format(const game_state *state)
{
    return NULL;
}

static game_ui *new_ui(const game_state *state)
{
    return NULL;
}

static void free_ui(game_ui *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 {
    float gridscale;
    int ox, oy;                        /* pixel position of float origin */
};

/*
 * Code shared between interpret_move() and execute_move().
 */
static int find_move_dest(const game_state *from, int direction,
			  int *skey, int *dkey)
{
    int mask, dest, i, j;
    float points[4];

    /*
     * Find the two points in the current grid square which
     * correspond to this move.
     */
    mask = from->grid->squares[from->current].directions[direction];
    if (mask == 0)
        return -1;
    for (i = j = 0; i < from->grid->squares[from->current].npoints; i++)
        if (mask & (1 << i)) {
            points[j*2] = from->grid->squares[from->current].points[i*2];
            points[j*2+1] = from->grid->squares[from->current].points[i*2+1];
            skey[j] = i;
            j++;
        }
    assert(j == 2);

    /*
     * Now find the other grid square which shares those points.
     * This is our move destination.
     */
    dest = -1;
    for (i = 0; i < from->grid->nsquares; i++)
        if (i != from->current) {
            int match = 0;
            float dist;

            for (j = 0; j < from->grid->squares[i].npoints; j++) {
                dist = (SQ(from->grid->squares[i].points[j*2] - points[0]) +
                        SQ(from->grid->squares[i].points[j*2+1] - points[1]));
                if (dist < 0.1)
                    dkey[match++] = j;
                dist = (SQ(from->grid->squares[i].points[j*2] - points[2]) +
                        SQ(from->grid->squares[i].points[j*2+1] - points[3]));
                if (dist < 0.1)
                    dkey[match++] = j;
            }

            if (match == 2) {
                dest = i;
                break;
            }
        }

    return dest;
}

static char *interpret_move(const game_state *state, game_ui *ui,
                            const game_drawstate *ds,
                            int x, int y, int button)
{
    int direction, mask, i;
    int skey[2], dkey[2];

    button = button & (~MOD_MASK | MOD_NUM_KEYPAD);

    /*
     * Moves can be made with the cursor keys or numeric keypad, or
     * alternatively you can left-click and the polyhedron will
     * move in the general direction of the mouse pointer.
     */
    if (button == CURSOR_UP || button == (MOD_NUM_KEYPAD | '8'))
        direction = UP;
    else if (button == CURSOR_DOWN || button == (MOD_NUM_KEYPAD | '2'))
        direction = DOWN;
    else if (button == CURSOR_LEFT || button == (MOD_NUM_KEYPAD | '4'))
        direction = LEFT;
    else if (button == CURSOR_RIGHT || button == (MOD_NUM_KEYPAD | '6'))
        direction = RIGHT;
    else if (button == (MOD_NUM_KEYPAD | '7'))
        direction = UP_LEFT;
    else if (button == (MOD_NUM_KEYPAD | '1'))
        direction = DOWN_LEFT;
    else if (button == (MOD_NUM_KEYPAD | '9'))
        direction = UP_RIGHT;
    else if (button == (MOD_NUM_KEYPAD | '3'))
        direction = DOWN_RIGHT;
    else if (button == LEFT_BUTTON) {
        /*
         * Find the bearing of the click point from the current
         * square's centre.
         */
        int cx, cy;
        double angle;

        cx = (int)(state->grid->squares[state->current].x * GRID_SCALE) + ds->ox;
        cy = (int)(state->grid->squares[state->current].y * GRID_SCALE) + ds->oy;

        if (x == cx && y == cy)
            return NULL;               /* clicked in exact centre!  */
        angle = atan2(y - cy, x - cx);

        /*
         * There are three possibilities.
         * 
         *  - This square is a square, so we choose between UP,
         *    DOWN, LEFT and RIGHT by dividing the available angle
         *    at the 45-degree points.
         * 
         *  - This square is an up-pointing triangle, so we choose
         *    between DOWN, LEFT and RIGHT by dividing into
         *    120-degree arcs.
         * 
         *  - This square is a down-pointing triangle, so we choose
         *    between UP, LEFT and RIGHT in the inverse manner.
         * 
         * Don't forget that since our y-coordinates increase
         * downwards, `angle' is measured _clockwise_ from the
         * x-axis, not anticlockwise as most mathematicians would
         * instinctively assume.
         */
        if (state->grid->squares[state->current].npoints == 4) {
            /* Square. */
            if (fabs(angle) > 3*PI/4)
                direction = LEFT;
            else if (fabs(angle) < PI/4)
                direction = RIGHT;
            else if (angle > 0)
                direction = DOWN;
            else
                direction = UP;
        } else if (state->grid->squares[state->current].directions[UP] == 0) {
            /* Up-pointing triangle. */
            if (angle < -PI/2 || angle > 5*PI/6)
                direction = LEFT;
            else if (angle > PI/6)
                direction = DOWN;
            else
                direction = RIGHT;
        } else {
            /* Down-pointing triangle. */
            assert(state->grid->squares[state->current].directions[DOWN] == 0);
            if (angle > PI/2 || angle < -5*PI/6)
                direction = LEFT;
            else if (angle < -PI/6)
                direction = UP;
            else
                direction = RIGHT;
        }
    } else
        return NULL;

    mask = state->grid->squares[state->current].directions[direction];
    if (mask == 0)
        return NULL;

    /*
     * Translate diagonal directions into orthogonal ones.
     */
    if (direction > DOWN) {
	for (i = LEFT; i <= DOWN; i++)
	    if (state->grid->squares[state->current].directions[i] == mask) {
		direction = i;
		break;
	    }
	assert(direction <= DOWN);
    }

    if (find_move_dest(state, direction, skey, dkey) < 0)
	return NULL;

    if (direction == LEFT)  return dupstr("L");
    if (direction == RIGHT) return dupstr("R");
    if (direction == UP)    return dupstr("U");
    if (direction == DOWN)  return dupstr("D");

    return NULL;		       /* should never happen */
}

static game_state *execute_move(const game_state *from, const char *move)
{
    game_state *ret;
    float angle;
    struct solid *poly;
    int pkey[2];
    int skey[2], dkey[2];
    int i, j, dest;
    int direction;

    switch (*move) {
      case 'L': direction = LEFT; break;
      case 'R': direction = RIGHT; break;
      case 'U': direction = UP; break;
      case 'D': direction = DOWN; break;
      default: return NULL;
    }

    dest = find_move_dest(from, direction, skey, dkey);
    if (dest < 0)
        return NULL;

    ret = dup_game(from);
    ret->current = dest;

    /*
     * So we know what grid square we're aiming for, and we also
     * know the two key points (as indices in both the source and
     * destination grid squares) which are invariant between source
     * and destination.
     * 
     * Next we must roll the polyhedron on to that square. So we
     * find the indices of the key points within the polyhedron's
     * vertex array, then use those in a call to transform_poly,
     * and align the result on the new grid square.
     */
    {
        int all_pkey[4];
        align_poly(from->solid, &from->grid->squares[from->current], all_pkey);
        pkey[0] = all_pkey[skey[0]];
        pkey[1] = all_pkey[skey[1]];
        /*
         * Now pkey[0] corresponds to skey[0] and dkey[0], and
         * likewise [1].
         */
    }

    /*
     * Now find the angle through which to rotate the polyhedron.
     * Do this by finding the two faces that share the two vertices
     * we've found, and taking the dot product of their normals.
     */
    {
        int f[2], nf = 0;
        float dp;

        for (i = 0; i < from->solid->nfaces; i++) {
            int match = 0;
            for (j = 0; j < from->solid->order; j++)
                if (from->solid->faces[i*from->solid->order + j] == pkey[0] ||
                    from->solid->faces[i*from->solid->order + j] == pkey[1])
                    match++;
            if (match == 2) {
                assert(nf < 2);
                f[nf++] = i;
            }
        }

        assert(nf == 2);

        dp = 0;
        for (i = 0; i < 3; i++)
            dp += (from->solid->normals[f[0]*3+i] *
                   from->solid->normals[f[1]*3+i]);
        angle = (float)acos(dp);
    }

    /*
     * Now transform the polyhedron. We aren't entirely sure
     * whether we need to rotate through angle or -angle, and the
     * simplest way round this is to try both and see which one
     * aligns successfully!
     * 
     * Unfortunately, _both_ will align successfully if this is a
     * cube, which won't tell us anything much. So for that
     * particular case, I resort to gross hackery: I simply negate
     * the angle before trying the alignment, depending on the
     * direction. Which directions work which way is determined by
     * pure trial and error. I said it was gross :-/
     */
    {
        int all_pkey[4];
        bool success;

        if (from->solid->order == 4 && direction == UP)
            angle = -angle;            /* HACK */

        poly = transform_poly(from->solid,
                              from->grid->squares[from->current].flip,
                              pkey[0], pkey[1], angle);
        flip_poly(poly, from->grid->squares[ret->current].flip);
        success = align_poly(poly, &from->grid->squares[ret->current], all_pkey);

        if (!success) {
            sfree(poly);
            angle = -angle;
            poly = transform_poly(from->solid,
                                  from->grid->squares[from->current].flip,
                                  pkey[0], pkey[1], angle);
            flip_poly(poly, from->grid->squares[ret->current].flip);
            success = align_poly(poly, &from->grid->squares[ret->current], all_pkey);
        }

        assert(success);
    }

    /*
     * Now we have our rotated polyhedron, which we expect to be
     * exactly congruent to the one we started with - but with the
     * faces permuted. So we map that congruence and thereby figure
     * out how to permute the faces as a result of the polyhedron
     * having rolled.
     */
    {
        int *newcolours = snewn(from->solid->nfaces, int);

        for (i = 0; i < from->solid->nfaces; i++)
            newcolours[i] = -1;

        for (i = 0; i < from->solid->nfaces; i++) {
            int nmatch = 0;

            /*
             * Now go through the transformed polyhedron's faces
             * and figure out which one's normal is approximately
             * equal to this one.
             */
            for (j = 0; j < poly->nfaces; j++) {
                float dist;
                int k;

                dist = 0;

                for (k = 0; k < 3; k++)
                    dist += SQ(poly->normals[j*3+k] -
                               from->solid->normals[i*3+k]);

                if (APPROXEQ(dist, 0)) {
                    nmatch++;
                    newcolours[i] = ret->facecolours[j];
                }
            }

            assert(nmatch == 1);
        }

        for (i = 0; i < from->solid->nfaces; i++)
            assert(newcolours[i] != -1);

        sfree(ret->facecolours);
        ret->facecolours = newcolours;
    }

    ret->movecount++;

    /*
     * And finally, swap the colour between the bottom face of the
     * polyhedron and the face we've just landed on.
     * 
     * We don't do this if the game is already complete, since we
     * allow the user to roll the fully blue polyhedron around the
     * grid as a feeble reward.
     */
    if (!ret->completed) {
        i = lowest_face(from->solid);
        j = ret->facecolours[i];
        ret->facecolours[i] = GET_SQUARE(ret, ret->current);
        SET_SQUARE(ret, ret->current, j);

        /*
         * Detect game completion.
         */
        j = 0;
        for (i = 0; i < ret->solid->nfaces; i++)
            if (ret->facecolours[i])
                j++;
        if (j == ret->solid->nfaces)
            ret->completed = ret->movecount;
    }

    sfree(poly);

    /*
     * Align the normal polyhedron with its grid square, to get key
     * points for non-animated display.
     */
    {
        int pkey[4];
        bool success;

        success = align_poly(ret->solid, &ret->grid->squares[ret->current], pkey);
        assert(success);

        ret->dpkey[0] = pkey[0];
        ret->dpkey[1] = pkey[1];
        ret->dgkey[0] = 0;
        ret->dgkey[1] = 1;
    }


    ret->spkey[0] = pkey[0];
    ret->spkey[1] = pkey[1];
    ret->sgkey[0] = skey[0];
    ret->sgkey[1] = skey[1];
    ret->previous = from->current;
    ret->angle = angle;

    return ret;
}

/* ----------------------------------------------------------------------
 * Drawing routines.
 */

struct bbox {
    float l, r, u, d;
};

static void find_bbox_callback(void *ctx, struct grid_square *sq)
{
    struct bbox *bb = (struct bbox *)ctx;
    int i;

    for (i = 0; i < sq->npoints; i++) {
        if (bb->l > sq->points[i*2]) bb->l = sq->points[i*2];
        if (bb->r < sq->points[i*2]) bb->r = sq->points[i*2];
        if (bb->u > sq->points[i*2+1]) bb->u = sq->points[i*2+1];
        if (bb->d < sq->points[i*2+1]) bb->d = sq->points[i*2+1];
    }
}

static struct bbox find_bbox(const game_params *params)
{
    struct bbox bb;

    /*
     * These should be hugely more than the real bounding box will
     * be.
     */
    bb.l = 2.0F * (params->d1 + params->d2);
    bb.r = -2.0F * (params->d1 + params->d2);
    bb.u = 2.0F * (params->d1 + params->d2);
    bb.d = -2.0F * (params->d1 + params->d2);
    enum_grid_squares(params, find_bbox_callback, &bb);

    return bb;
}

#define XSIZE(gs, bb, solid) \
    ((int)(((bb).r - (bb).l + 2*(solid)->border) * gs))
#define YSIZE(gs, bb, solid) \
    ((int)(((bb).d - (bb).u + 2*(solid)->border) * gs))

static void game_compute_size(const game_params *params, int tilesize,
                              int *x, int *y)
{
    struct bbox bb = find_bbox(params);

    *x = XSIZE(tilesize, bb, solids[params->solid]);
    *y = YSIZE(tilesize, bb, solids[params->solid]);
}

static void game_set_size(drawing *dr, game_drawstate *ds,
                          const game_params *params, int tilesize)
{
    struct bbox bb = find_bbox(params);

    ds->gridscale = (float)tilesize;
    ds->ox = (int)(-(bb.l - solids[params->solid]->border) * ds->gridscale);
    ds->oy = (int)(-(bb.u - solids[params->solid]->border) * ds->gridscale);
}

static float *game_colours(frontend *fe, int *ncolours)
{
    float *ret = snewn(3 * NCOLOURS, float);

    frontend_default_colour(fe, &ret[COL_BACKGROUND * 3]);

    ret[COL_BORDER * 3 + 0] = 0.0;
    ret[COL_BORDER * 3 + 1] = 0.0;
    ret[COL_BORDER * 3 + 2] = 0.0;

    ret[COL_BLUE * 3 + 0] = 0.0;
    ret[COL_BLUE * 3 + 1] = 0.0;
    ret[COL_BLUE * 3 + 2] = 1.0;

    *ncolours = NCOLOURS;
    return ret;
}

static game_drawstate *game_new_drawstate(drawing *dr, const game_state *state)
{
    struct game_drawstate *ds = snew(struct game_drawstate);

    ds->ox = ds->oy = 0;
    ds->gridscale = 0.0F; /* not decided yet */

    return ds;
}

static void game_free_drawstate(drawing *dr, game_drawstate *ds)
{
    sfree(ds);
}

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 i, j;
    struct bbox bb = find_bbox(&state->params);
    struct solid *poly;
    const int *pkey, *gkey;
    float t[3];
    float angle;
    int square;

    draw_rect(dr, 0, 0, XSIZE(GRID_SCALE, bb, state->solid),
	      YSIZE(GRID_SCALE, bb, state->solid), COL_BACKGROUND);

    if (dir < 0) {
        const game_state *t;

        /*
         * This is an Undo. So reverse the order of the states, and
         * run the roll timer backwards.
         */
	assert(oldstate);

        t = oldstate;
        oldstate = state;
        state = t;

        animtime = ROLLTIME - animtime;
    }

    if (!oldstate) {
        oldstate = state;
        angle = 0.0;
        square = state->current;
        pkey = state->dpkey;
        gkey = state->dgkey;
    } else {
        angle = state->angle * animtime / ROLLTIME;
        square = state->previous;
        pkey = state->spkey;
        gkey = state->sgkey;
    }
    state = oldstate;

    for (i = 0; i < state->grid->nsquares; i++) {
        int coords[8];

        for (j = 0; j < state->grid->squares[i].npoints; j++) {
            coords[2*j] = ((int)(state->grid->squares[i].points[2*j] * GRID_SCALE)
			   + ds->ox);
            coords[2*j+1] = ((int)(state->grid->squares[i].points[2*j+1]*GRID_SCALE)
			     + ds->oy);
        }

        draw_polygon(dr, coords, state->grid->squares[i].npoints,
                     GET_SQUARE(state, i) ? COL_BLUE : COL_BACKGROUND,
		     COL_BORDER);
    }

    /*
     * Now compute and draw the polyhedron.
     */
    poly = transform_poly(state->solid, state->grid->squares[square].flip,
                          pkey[0], pkey[1], angle);

    /*
     * Compute the translation required to align the two key points
     * on the polyhedron with the same key points on the current
     * face.
     */
    for (i = 0; i < 3; i++) {
        float tc = 0.0;

        for (j = 0; j < 2; j++) {
            float grid_coord;

            if (i < 2) {
                grid_coord =
                    state->grid->squares[square].points[gkey[j]*2+i];
            } else {
                grid_coord = 0.0;
            }

            tc += (grid_coord - poly->vertices[pkey[j]*3+i]);
        }

        t[i] = tc / 2;
    }
    for (i = 0; i < poly->nvertices; i++)
        for (j = 0; j < 3; j++)
            poly->vertices[i*3+j] += t[j];

    /*
     * Now actually draw each face.
     */
    for (i = 0; i < poly->nfaces; i++) {
        float points[8];
        int coords[8];

        for (j = 0; j < poly->order; j++) {
            int f = poly->faces[i*poly->order + j];
            points[j*2] = (poly->vertices[f*3+0] -
                           poly->vertices[f*3+2] * poly->shear);
            points[j*2+1] = (poly->vertices[f*3+1] -
                             poly->vertices[f*3+2] * poly->shear);
        }

        for (j = 0; j < poly->order; j++) {
            coords[j*2] = (int)floor(points[j*2] * GRID_SCALE) + ds->ox;
            coords[j*2+1] = (int)floor(points[j*2+1] * GRID_SCALE) + ds->oy;
        }

        /*
         * Find out whether these points are in a clockwise or
         * anticlockwise arrangement. If the latter, discard the
         * face because it's facing away from the viewer.
         *
         * This would involve fiddly winding-number stuff for a
         * general polygon, but for the simple parallelograms we'll
         * be seeing here, all we have to do is check whether the
         * corners turn right or left. So we'll take the vector
         * from point 0 to point 1, turn it right 90 degrees,
         * and check the sign of the dot product with that and the
         * next vector (point 1 to point 2).
         */
        {
            float v1x = points[2]-points[0];
            float v1y = points[3]-points[1];
            float v2x = points[4]-points[2];
            float v2y = points[5]-points[3];
            float dp = v1x * v2y - v1y * v2x;

            if (dp <= 0)
                continue;
        }

        draw_polygon(dr, coords, poly->order,
                     state->facecolours[i] ? COL_BLUE : COL_BACKGROUND,
		     COL_BORDER);
    }
    sfree(poly);

    draw_update(dr, 0, 0, XSIZE(GRID_SCALE, bb, state->solid),
		YSIZE(GRID_SCALE, bb, state->solid));

    /*
     * Update the status bar.
     */
    {
	char statusbuf[256];

	sprintf(statusbuf, "%sMoves: %d",
		(state->completed ? "COMPLETED! " : ""),
		(state->completed ? state->completed : state->movecount));

	status_bar(dr, statusbuf);
    }
}

static float game_anim_length(const game_state *oldstate,
                              const game_state *newstate, int dir, game_ui *ui)
{
    return ROLLTIME;
}

static float game_flash_length(const game_state *oldstate,
                               const game_state *newstate, int dir, game_ui *ui)
{
    return 0.0F;
}

static int game_status(const game_state *state)
{
    return state->completed ? +1 : 0;
}

static bool 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 cube
#endif

const struct game thegame = {
    "Cube", "games.cube", "cube",
    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,
    false, game_can_format_as_text_now, game_text_format,
    new_ui,
    free_ui,
    encode_ui,
    decode_ui,
    NULL, /* game_request_keys */
    game_changed_state,
    interpret_move,
    execute_move,
    PREFERRED_GRID_SCALE, 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 */
};
generated by cgit v1.1 at 2026-05-20 02:57:44 +0000