2 * map.c: Game involving four-colouring a map.
9 * - better four-colouring algorithm?
10 * - can we make the pencil marks look nicer?
11 * - ability to drag a set of pencil marks?
24 * I don't seriously anticipate wanting to change the number of
25 * colours used in this game, but it doesn't cost much to use a
26 * #define just in case :-)
29 #define THREE (FOUR-1)
34 * Ghastly run-time configuration option, just for Gareth (again).
36 static int flash_type = -1;
37 static float flash_length;
40 * Difficulty levels. I do some macro ickery here to ensure that my
41 * enum and the various forms of my name list always match up.
47 A(RECURSE,Unreasonable,u)
48 #define ENUM(upper,title,lower) DIFF_ ## upper,
49 #define TITLE(upper,title,lower) #title,
50 #define ENCODE(upper,title,lower) #lower
51 #define CONFIG(upper,title,lower) ":" #title
52 enum { DIFFLIST(ENUM) DIFFCOUNT };
53 static char const *const map_diffnames[] = { DIFFLIST(TITLE) };
54 static char const map_diffchars[] = DIFFLIST(ENCODE);
55 #define DIFFCONFIG DIFFLIST(CONFIG)
57 enum { TE, BE, LE, RE }; /* top/bottom/left/right edges */
62 COL_0, COL_1, COL_2, COL_3,
63 COL_ERROR, COL_ERRTEXT,
78 int *edgex, *edgey; /* positions of a point on each edge */
84 int *colouring, *pencil;
85 int completed, cheated;
88 static game_params *default_params(void)
90 game_params *ret = snew(game_params);
95 ret->diff = DIFF_NORMAL;
100 static const struct game_params map_presets[] = {
101 {20, 15, 30, DIFF_EASY},
102 {20, 15, 30, DIFF_NORMAL},
103 {20, 15, 30, DIFF_HARD},
104 {20, 15, 30, DIFF_RECURSE},
105 {30, 25, 75, DIFF_NORMAL},
106 {30, 25, 75, DIFF_HARD},
109 static int game_fetch_preset(int i, char **name, game_params **params)
114 if (i < 0 || i >= lenof(map_presets))
117 ret = snew(game_params);
118 *ret = map_presets[i];
120 sprintf(str, "%dx%d, %d regions, %s", ret->w, ret->h, ret->n,
121 map_diffnames[ret->diff]);
128 static void free_params(game_params *params)
133 static game_params *dup_params(game_params *params)
135 game_params *ret = snew(game_params);
136 *ret = *params; /* structure copy */
140 static void decode_params(game_params *params, char const *string)
142 char const *p = string;
145 while (*p && isdigit((unsigned char)*p)) p++;
149 while (*p && isdigit((unsigned char)*p)) p++;
151 params->h = params->w;
156 while (*p && (*p == '.' || isdigit((unsigned char)*p))) p++;
158 params->n = params->w * params->h / 8;
163 for (i = 0; i < DIFFCOUNT; i++)
164 if (*p == map_diffchars[i])
170 static char *encode_params(game_params *params, int full)
174 sprintf(ret, "%dx%dn%d", params->w, params->h, params->n);
176 sprintf(ret + strlen(ret), "d%c", map_diffchars[params->diff]);
181 static config_item *game_configure(game_params *params)
186 ret = snewn(5, config_item);
188 ret[0].name = "Width";
189 ret[0].type = C_STRING;
190 sprintf(buf, "%d", params->w);
191 ret[0].sval = dupstr(buf);
194 ret[1].name = "Height";
195 ret[1].type = C_STRING;
196 sprintf(buf, "%d", params->h);
197 ret[1].sval = dupstr(buf);
200 ret[2].name = "Regions";
201 ret[2].type = C_STRING;
202 sprintf(buf, "%d", params->n);
203 ret[2].sval = dupstr(buf);
206 ret[3].name = "Difficulty";
207 ret[3].type = C_CHOICES;
208 ret[3].sval = DIFFCONFIG;
209 ret[3].ival = params->diff;
219 static game_params *custom_params(config_item *cfg)
221 game_params *ret = snew(game_params);
223 ret->w = atoi(cfg[0].sval);
224 ret->h = atoi(cfg[1].sval);
225 ret->n = atoi(cfg[2].sval);
226 ret->diff = cfg[3].ival;
231 static char *validate_params(game_params *params, int full)
233 if (params->w < 2 || params->h < 2)
234 return "Width and height must be at least two";
236 return "Must have at least five regions";
237 if (params->n > params->w * params->h)
238 return "Too many regions to fit in grid";
242 /* ----------------------------------------------------------------------
243 * Cumulative frequency table functions.
247 * Initialise a cumulative frequency table. (Hardly worth writing
248 * this function; all it does is to initialise everything in the
251 static void cf_init(int *table, int n)
255 for (i = 0; i < n; i++)
260 * Increment the count of symbol `sym' by `count'.
262 static void cf_add(int *table, int n, int sym, int count)
279 * Cumulative frequency lookup: return the total count of symbols
280 * with value less than `sym'.
282 static int cf_clookup(int *table, int n, int sym)
284 int bit, index, limit, count;
289 assert(0 < sym && sym <= n);
291 count = table[0]; /* start with the whole table size */
301 * Find the least number with its lowest set bit in this
302 * position which is greater than or equal to sym.
304 index = ((sym + bit - 1) &~ (bit * 2 - 1)) + bit;
307 count -= table[index];
318 * Single frequency lookup: return the count of symbol `sym'.
320 static int cf_slookup(int *table, int n, int sym)
324 assert(0 <= sym && sym < n);
328 for (bit = 1; sym+bit < n && !(sym & bit); bit <<= 1)
329 count -= table[sym+bit];
335 * Return the largest symbol index such that the cumulative
336 * frequency up to that symbol is less than _or equal to_ count.
338 static int cf_whichsym(int *table, int n, int count) {
341 assert(count >= 0 && count < table[0]);
352 if (count >= top - table[sym+bit])
355 top -= table[sym+bit];
364 /* ----------------------------------------------------------------------
367 * FIXME: this isn't entirely optimal at present, because it
368 * inherently prioritises growing the largest region since there
369 * are more squares adjacent to it. This acts as a destabilising
370 * influence leading to a few large regions and mostly small ones.
371 * It might be better to do it some other way.
374 #define WEIGHT_INCREASED 2 /* for increased perimeter */
375 #define WEIGHT_DECREASED 4 /* for decreased perimeter */
376 #define WEIGHT_UNCHANGED 3 /* for unchanged perimeter */
379 * Look at a square and decide which colours can be extended into
382 * If called with index < 0, it adds together one of
383 * WEIGHT_INCREASED, WEIGHT_DECREASED or WEIGHT_UNCHANGED for each
384 * colour that has a valid extension (according to the effect that
385 * it would have on the perimeter of the region being extended) and
386 * returns the overall total.
388 * If called with index >= 0, it returns one of the possible
389 * colours depending on the value of index, in such a way that the
390 * number of possible inputs which would give rise to a given
391 * return value correspond to the weight of that value.
393 static int extend_options(int w, int h, int n, int *map,
394 int x, int y, int index)
400 if (map[y*w+x] >= 0) {
402 return 0; /* can't do this square at all */
406 * Fetch the eight neighbours of this square, in order around
409 for (dy = -1; dy <= +1; dy++)
410 for (dx = -1; dx <= +1; dx++) {
411 int index = (dy < 0 ? 6-dx : dy > 0 ? 2+dx : 2*(1+dx));
412 if (x+dx >= 0 && x+dx < w && y+dy >= 0 && y+dy < h)
413 col[index] = map[(y+dy)*w+(x+dx)];
419 * Iterate over each colour that might be feasible.
421 * FIXME: this routine currently has O(n) running time. We
422 * could turn it into O(FOUR) by only bothering to iterate over
423 * the colours mentioned in the four neighbouring squares.
426 for (c = 0; c < n; c++) {
427 int count, neighbours, runs;
430 * One of the even indices of col (representing the
431 * orthogonal neighbours of this square) must be equal to
432 * c, or else this square is not adjacent to region c and
433 * obviously cannot become an extension of it at this time.
436 for (i = 0; i < 8; i += 2)
443 * Now we know this square is adjacent to region c. The
444 * next question is, would extending it cause the region to
445 * become non-simply-connected? If so, we mustn't do it.
447 * We determine this by looking around col to see if we can
448 * find more than one separate run of colour c.
451 for (i = 0; i < 8; i++)
452 if (col[i] == c && col[(i+1) & 7] != c)
460 * This square is a possibility. Determine its effect on
461 * the region's perimeter (computed from the number of
462 * orthogonal neighbours - 1 means a perimeter increase, 3
463 * a decrease, 2 no change; 4 is impossible because the
464 * region would already not be simply connected) and we're
467 assert(neighbours > 0 && neighbours < 4);
468 count = (neighbours == 1 ? WEIGHT_INCREASED :
469 neighbours == 2 ? WEIGHT_UNCHANGED : WEIGHT_DECREASED);
472 if (index >= 0 && index < count)
483 static void genmap(int w, int h, int n, int *map, random_state *rs)
490 tmp = snewn(wh, int);
493 * Clear the map, and set up `tmp' as a list of grid indices.
495 for (i = 0; i < wh; i++) {
501 * Place the region seeds by selecting n members from `tmp'.
504 for (i = 0; i < n; i++) {
505 int j = random_upto(rs, k);
511 * Re-initialise `tmp' as a cumulative frequency table. This
512 * will store the number of possible region colours we can
513 * extend into each square.
518 * Go through the grid and set up the initial cumulative
521 for (y = 0; y < h; y++)
522 for (x = 0; x < w; x++)
523 cf_add(tmp, wh, y*w+x,
524 extend_options(w, h, n, map, x, y, -1));
527 * Now repeatedly choose a square we can extend a region into,
531 int k = random_upto(rs, tmp[0]);
536 sq = cf_whichsym(tmp, wh, k);
537 k -= cf_clookup(tmp, wh, sq);
540 colour = extend_options(w, h, n, map, x, y, k);
545 * Re-scan the nine cells around the one we've just
548 for (yy = max(y-1, 0); yy < min(y+2, h); yy++)
549 for (xx = max(x-1, 0); xx < min(x+2, w); xx++) {
550 cf_add(tmp, wh, yy*w+xx,
551 -cf_slookup(tmp, wh, yy*w+xx) +
552 extend_options(w, h, n, map, xx, yy, -1));
557 * Finally, go through and normalise the region labels into
558 * order, meaning that indistinguishable maps are actually
561 for (i = 0; i < n; i++)
564 for (i = 0; i < wh; i++) {
568 map[i] = tmp[map[i]];
574 /* ----------------------------------------------------------------------
575 * Functions to handle graphs.
579 * Having got a map in a square grid, convert it into a graph
582 static int gengraph(int w, int h, int n, int *map, int *graph)
587 * Start by setting the graph up as an adjacency matrix. We'll
588 * turn it into a list later.
590 for (i = 0; i < n*n; i++)
594 * Iterate over the map looking for all adjacencies.
596 for (y = 0; y < h; y++)
597 for (x = 0; x < w; x++) {
600 if (x+1 < w && (vx = map[y*w+(x+1)]) != v)
601 graph[v*n+vx] = graph[vx*n+v] = 1;
602 if (y+1 < h && (vy = map[(y+1)*w+x]) != v)
603 graph[v*n+vy] = graph[vy*n+v] = 1;
607 * Turn the matrix into a list.
609 for (i = j = 0; i < n*n; i++)
616 static int graph_edge_index(int *graph, int n, int ngraph, int i, int j)
623 while (top - bot > 1) {
624 mid = (top + bot) / 2;
627 else if (graph[mid] < v)
635 #define graph_adjacent(graph, n, ngraph, i, j) \
636 (graph_edge_index((graph), (n), (ngraph), (i), (j)) >= 0)
638 static int graph_vertex_start(int *graph, int n, int ngraph, int i)
645 while (top - bot > 1) {
646 mid = (top + bot) / 2;
655 /* ----------------------------------------------------------------------
656 * Generate a four-colouring of a graph.
658 * FIXME: it would be nice if we could convert this recursion into
659 * pseudo-recursion using some sort of explicit stack array, for
660 * the sake of the Palm port and its limited stack.
663 static int fourcolour_recurse(int *graph, int n, int ngraph,
664 int *colouring, int *scratch, random_state *rs)
666 int nfree, nvert, start, i, j, k, c, ci;
670 * Find the smallest number of free colours in any uncoloured
671 * vertex, and count the number of such vertices.
674 nfree = FIVE; /* start off bigger than FOUR! */
676 for (i = 0; i < n; i++)
677 if (colouring[i] < 0 && scratch[i*FIVE+FOUR] <= nfree) {
678 if (nfree > scratch[i*FIVE+FOUR]) {
679 nfree = scratch[i*FIVE+FOUR];
686 * If there aren't any uncoloured vertices at all, we're done.
689 return TRUE; /* we've got a colouring! */
692 * Pick a random vertex in that set.
694 j = random_upto(rs, nvert);
695 for (i = 0; i < n; i++)
696 if (colouring[i] < 0 && scratch[i*FIVE+FOUR] == nfree)
700 start = graph_vertex_start(graph, n, ngraph, i);
703 * Loop over the possible colours for i, and recurse for each
707 for (c = 0; c < FOUR; c++)
708 if (scratch[i*FIVE+c] == 0)
710 shuffle(cs, ci, sizeof(*cs), rs);
716 * Fill in this colour.
721 * Update the scratch space to reflect a new neighbour
722 * of this colour for each neighbour of vertex i.
724 for (j = start; j < ngraph && graph[j] < n*(i+1); j++) {
726 if (scratch[k*FIVE+c] == 0)
727 scratch[k*FIVE+FOUR]--;
734 if (fourcolour_recurse(graph, n, ngraph, colouring, scratch, rs))
735 return TRUE; /* got one! */
738 * If that didn't work, clean up and try again with a
741 for (j = start; j < ngraph && graph[j] < n*(i+1); j++) {
744 if (scratch[k*FIVE+c] == 0)
745 scratch[k*FIVE+FOUR]++;
751 * If we reach here, we were unable to find a colouring at all.
752 * (This doesn't necessarily mean the Four Colour Theorem is
753 * violated; it might just mean we've gone down a dead end and
754 * need to back up and look somewhere else. It's only an FCT
755 * violation if we get all the way back up to the top level and
761 static void fourcolour(int *graph, int n, int ngraph, int *colouring,
768 * For each vertex and each colour, we store the number of
769 * neighbours that have that colour. Also, we store the number
770 * of free colours for the vertex.
772 scratch = snewn(n * FIVE, int);
773 for (i = 0; i < n * FIVE; i++)
774 scratch[i] = (i % FIVE == FOUR ? FOUR : 0);
777 * Clear the colouring to start with.
779 for (i = 0; i < n; i++)
782 i = fourcolour_recurse(graph, n, ngraph, colouring, scratch, rs);
783 assert(i); /* by the Four Colour Theorem :-) */
788 /* ----------------------------------------------------------------------
789 * Non-recursive solver.
792 struct solver_scratch {
793 unsigned char *possible; /* bitmap of colours for each region */
802 static struct solver_scratch *new_scratch(int *graph, int n, int ngraph)
804 struct solver_scratch *sc;
806 sc = snew(struct solver_scratch);
810 sc->possible = snewn(n, unsigned char);
812 sc->bfsqueue = snewn(n, int);
813 sc->bfscolour = snewn(n, int);
818 static void free_scratch(struct solver_scratch *sc)
822 sfree(sc->bfscolour);
827 * Count the bits in a word. Only needs to cope with FOUR bits.
829 static int bitcount(int word)
831 assert(FOUR <= 4); /* or this needs changing */
832 word = ((word & 0xA) >> 1) + (word & 0x5);
833 word = ((word & 0xC) >> 2) + (word & 0x3);
837 static int place_colour(struct solver_scratch *sc,
838 int *colouring, int index, int colour)
840 int *graph = sc->graph, n = sc->n, ngraph = sc->ngraph;
843 if (!(sc->possible[index] & (1 << colour)))
844 return FALSE; /* can't do it */
846 sc->possible[index] = 1 << colour;
847 colouring[index] = colour;
850 * Rule out this colour from all the region's neighbours.
852 for (j = graph_vertex_start(graph, n, ngraph, index);
853 j < ngraph && graph[j] < n*(index+1); j++) {
854 k = graph[j] - index*n;
855 sc->possible[k] &= ~(1 << colour);
862 * Returns 0 for impossible, 1 for success, 2 for failure to
863 * converge (i.e. puzzle is either ambiguous or just too
866 static int map_solver(struct solver_scratch *sc,
867 int *graph, int n, int ngraph, int *colouring,
873 * Initialise scratch space.
875 for (i = 0; i < n; i++)
876 sc->possible[i] = (1 << FOUR) - 1;
881 for (i = 0; i < n; i++)
882 if (colouring[i] >= 0) {
883 if (!place_colour(sc, colouring, i, colouring[i]))
884 return 0; /* the clues aren't even consistent! */
888 * Now repeatedly loop until we find nothing further to do.
891 int done_something = FALSE;
893 if (difficulty < DIFF_EASY)
894 break; /* can't do anything at all! */
897 * Simplest possible deduction: find a region with only one
900 for (i = 0; i < n; i++) if (colouring[i] < 0) {
901 int p = sc->possible[i];
904 return 0; /* puzzle is inconsistent */
906 if ((p & (p-1)) == 0) { /* p is a power of two */
908 for (c = 0; c < FOUR; c++)
912 if (!place_colour(sc, colouring, i, c))
913 return 0; /* found puzzle to be inconsistent */
914 done_something = TRUE;
921 if (difficulty < DIFF_NORMAL)
922 break; /* can't do anything harder */
925 * Failing that, go up one level. Look for pairs of regions
926 * which (a) both have the same pair of possible colours,
927 * (b) are adjacent to one another, (c) are adjacent to the
928 * same region, and (d) that region still thinks it has one
929 * or both of those possible colours.
931 * Simplest way to do this is by going through the graph
932 * edge by edge, so that we start with property (b) and
933 * then look for (a) and finally (c) and (d).
935 for (i = 0; i < ngraph; i++) {
936 int j1 = graph[i] / n, j2 = graph[i] % n;
940 continue; /* done it already, other way round */
942 if (colouring[j1] >= 0 || colouring[j2] >= 0)
943 continue; /* they're not undecided */
945 if (sc->possible[j1] != sc->possible[j2])
946 continue; /* they don't have the same possibles */
948 v = sc->possible[j1];
950 * See if v contains exactly two set bits.
952 v2 = v & -v; /* find lowest set bit */
953 v2 = v & ~v2; /* clear it */
954 if (v2 == 0 || (v2 & (v2-1)) != 0) /* not power of 2 */
958 * We've found regions j1 and j2 satisfying properties
959 * (a) and (b): they have two possible colours between
960 * them, and since they're adjacent to one another they
961 * must use _both_ those colours between them.
962 * Therefore, if they are both adjacent to any other
963 * region then that region cannot be either colour.
965 * Go through the neighbours of j1 and see if any are
968 for (j = graph_vertex_start(graph, n, ngraph, j1);
969 j < ngraph && graph[j] < n*(j1+1); j++) {
971 if (graph_adjacent(graph, n, ngraph, k, j2) &&
972 (sc->possible[k] & v)) {
973 sc->possible[k] &= ~v;
974 done_something = TRUE;
982 if (difficulty < DIFF_HARD)
983 break; /* can't do anything harder */
986 * Right; now we get creative. Now we're going to look for
987 * `forcing chains'. A forcing chain is a path through the
988 * graph with the following properties:
990 * (a) Each vertex on the path has precisely two possible
993 * (b) Each pair of vertices which are adjacent on the
994 * path share at least one possible colour in common.
996 * (c) Each vertex in the middle of the path shares _both_
997 * of its colours with at least one of its neighbours
998 * (not the same one with both neighbours).
1000 * These together imply that at least one of the possible
1001 * colour choices at one end of the path forces _all_ the
1002 * rest of the colours along the path. In order to make
1003 * real use of this, we need further properties:
1005 * (c) Ruling out some colour C from the vertex at one end
1006 * of the path forces the vertex at the other end to
1009 * (d) The two end vertices are mutually adjacent to some
1012 * (e) That third vertex currently has C as a possibility.
1014 * If we can find all of that lot, we can deduce that at
1015 * least one of the two ends of the forcing chain has
1016 * colour C, and that therefore the mutually adjacent third
1019 * To find forcing chains, we're going to start a bfs at
1020 * each suitable vertex of the graph, once for each of its
1021 * two possible colours.
1023 for (i = 0; i < n; i++) {
1026 if (colouring[i] >= 0 || bitcount(sc->possible[i]) != 2)
1029 for (c = 0; c < FOUR; c++)
1030 if (sc->possible[i] & (1 << c)) {
1031 int j, k, gi, origc, currc, head, tail;
1033 * Try a bfs from this vertex, ruling out
1036 * Within this loop, we work in colour bitmaps
1037 * rather than actual colours, because
1038 * converting back and forth is a needless
1039 * computational expense.
1044 for (j = 0; j < n; j++)
1045 sc->bfscolour[j] = -1;
1047 sc->bfsqueue[tail++] = i;
1048 sc->bfscolour[i] = sc->possible[i] &~ origc;
1050 while (head < tail) {
1051 j = sc->bfsqueue[head++];
1052 currc = sc->bfscolour[j];
1055 * Try neighbours of j.
1057 for (gi = graph_vertex_start(graph, n, ngraph, j);
1058 gi < ngraph && graph[gi] < n*(j+1); gi++) {
1059 k = graph[gi] - j*n;
1062 * To continue with the bfs in vertex
1063 * k, we need k to be
1064 * (a) not already visited
1065 * (b) have two possible colours
1066 * (c) those colours include currc.
1069 if (sc->bfscolour[k] < 0 &&
1071 bitcount(sc->possible[k]) == 2 &&
1072 (sc->possible[k] & currc)) {
1073 sc->bfsqueue[tail++] = k;
1075 sc->possible[k] &~ currc;
1079 * One other possibility is that k
1080 * might be the region in which we can
1081 * make a real deduction: if it's
1082 * adjacent to i, contains currc as a
1083 * possibility, and currc is equal to
1084 * the original colour we ruled out.
1086 if (currc == origc &&
1087 graph_adjacent(graph, n, ngraph, k, i) &&
1088 (sc->possible[k] & currc)) {
1089 sc->possible[k] &= ~origc;
1090 done_something = TRUE;
1099 if (!done_something)
1104 * See if we've got a complete solution, and return if so.
1106 for (i = 0; i < n; i++)
1107 if (colouring[i] < 0)
1110 return 1; /* success! */
1113 * If recursion is not permissible, we now give up.
1115 if (difficulty < DIFF_RECURSE)
1116 return 2; /* unable to complete */
1119 * Now we've got to do something recursive. So first hunt for a
1120 * currently-most-constrained region.
1124 struct solver_scratch *rsc;
1125 int *subcolouring, *origcolouring;
1127 int we_already_got_one;
1132 for (i = 0; i < n; i++) if (colouring[i] < 0) {
1133 int p = sc->possible[i];
1134 enum { compile_time_assertion = 1 / (FOUR <= 4) };
1137 /* Count the set bits. */
1138 c = (p & 5) + ((p >> 1) & 5);
1139 c = (c & 3) + ((c >> 2) & 3);
1140 assert(c > 1); /* or colouring[i] would be >= 0 */
1148 assert(best >= 0); /* or we'd be solved already */
1151 * Now iterate over the possible colours for this region.
1153 rsc = new_scratch(graph, n, ngraph);
1154 rsc->depth = sc->depth + 1;
1155 origcolouring = snewn(n, int);
1156 memcpy(origcolouring, colouring, n * sizeof(int));
1157 subcolouring = snewn(n, int);
1158 we_already_got_one = FALSE;
1161 for (i = 0; i < FOUR; i++) {
1162 if (!(sc->possible[best] & (1 << i)))
1165 memcpy(subcolouring, origcolouring, n * sizeof(int));
1166 subcolouring[best] = i;
1167 subret = map_solver(rsc, graph, n, ngraph,
1168 subcolouring, difficulty);
1171 * If this possibility turned up more than one valid
1172 * solution, or if it turned up one and we already had
1173 * one, we're definitely ambiguous.
1175 if (subret == 2 || (subret == 1 && we_already_got_one)) {
1181 * If this possibility turned up one valid solution and
1182 * it's the first we've seen, copy it into the output.
1185 memcpy(colouring, subcolouring, n * sizeof(int));
1186 we_already_got_one = TRUE;
1191 * Otherwise, this guess led to a contradiction, so we
1196 sfree(subcolouring);
1203 /* ----------------------------------------------------------------------
1204 * Game generation main function.
1207 static char *new_game_desc(game_params *params, random_state *rs,
1208 char **aux, int interactive)
1210 struct solver_scratch *sc = NULL;
1211 int *map, *graph, ngraph, *colouring, *colouring2, *regions;
1212 int i, j, w, h, n, solveret, cfreq[FOUR];
1215 #ifdef GENERATION_DIAGNOSTICS
1219 int retlen, retsize;
1228 map = snewn(wh, int);
1229 graph = snewn(n*n, int);
1230 colouring = snewn(n, int);
1231 colouring2 = snewn(n, int);
1232 regions = snewn(n, int);
1235 * This is the minimum difficulty below which we'll completely
1236 * reject a map design. Normally we set this to one below the
1237 * requested difficulty, ensuring that we have the right
1238 * result. However, for particularly dense maps or maps with
1239 * particularly few regions it might not be possible to get the
1240 * desired difficulty, so we will eventually drop this down to
1241 * -1 to indicate that any old map will do.
1243 mindiff = params->diff;
1251 genmap(w, h, n, map, rs);
1253 #ifdef GENERATION_DIAGNOSTICS
1254 for (y = 0; y < h; y++) {
1255 for (x = 0; x < w; x++) {
1260 putchar('a' + v-36);
1262 putchar('A' + v-10);
1271 * Convert the map into a graph.
1273 ngraph = gengraph(w, h, n, map, graph);
1275 #ifdef GENERATION_DIAGNOSTICS
1276 for (i = 0; i < ngraph; i++)
1277 printf("%d-%d\n", graph[i]/n, graph[i]%n);
1283 fourcolour(graph, n, ngraph, colouring, rs);
1285 #ifdef GENERATION_DIAGNOSTICS
1286 for (i = 0; i < n; i++)
1287 printf("%d: %d\n", i, colouring[i]);
1289 for (y = 0; y < h; y++) {
1290 for (x = 0; x < w; x++) {
1291 int v = colouring[map[y*w+x]];
1293 putchar('a' + v-36);
1295 putchar('A' + v-10);
1304 * Encode the solution as an aux string.
1306 if (*aux) /* in case we've come round again */
1308 retlen = retsize = 0;
1310 for (i = 0; i < n; i++) {
1313 if (colouring[i] < 0)
1316 len = sprintf(buf, "%s%d:%d", i ? ";" : "S;", colouring[i], i);
1317 if (retlen + len >= retsize) {
1318 retsize = retlen + len + 256;
1319 ret = sresize(ret, retsize, char);
1321 strcpy(ret + retlen, buf);
1327 * Remove the region colours one by one, keeping
1328 * solubility. Also ensure that there always remains at
1329 * least one region of every colour, so that the user can
1330 * drag from somewhere.
1332 for (i = 0; i < FOUR; i++)
1334 for (i = 0; i < n; i++) {
1336 cfreq[colouring[i]]++;
1338 for (i = 0; i < FOUR; i++)
1342 shuffle(regions, n, sizeof(*regions), rs);
1344 if (sc) free_scratch(sc);
1345 sc = new_scratch(graph, n, ngraph);
1347 for (i = 0; i < n; i++) {
1350 if (cfreq[colouring[j]] == 1)
1351 continue; /* can't remove last region of colour */
1353 memcpy(colouring2, colouring, n*sizeof(int));
1355 solveret = map_solver(sc, graph, n, ngraph, colouring2,
1357 assert(solveret >= 0); /* mustn't be impossible! */
1358 if (solveret == 1) {
1359 cfreq[colouring[j]]--;
1364 #ifdef GENERATION_DIAGNOSTICS
1365 for (i = 0; i < n; i++)
1366 if (colouring[i] >= 0) {
1370 putchar('a' + i-36);
1372 putchar('A' + i-10);
1375 printf(": %d\n", colouring[i]);
1380 * Finally, check that the puzzle is _at least_ as hard as
1381 * required, and indeed that it isn't already solved.
1382 * (Calling map_solver with negative difficulty ensures the
1383 * latter - if a solver which _does nothing_ can solve it,
1386 memcpy(colouring2, colouring, n*sizeof(int));
1387 if (map_solver(sc, graph, n, ngraph, colouring2,
1388 mindiff - 1) == 1) {
1390 * Drop minimum difficulty if necessary.
1392 if (mindiff > 0 && (n < 9 || n > 2*wh/3)) {
1394 mindiff = 0; /* give up and go for Easy */
1403 * Encode as a game ID. We do this by:
1405 * - first going along the horizontal edges row by row, and
1406 * then the vertical edges column by column
1407 * - encoding the lengths of runs of edges and runs of
1409 * - the decoder will reconstitute the region boundaries from
1410 * this and automatically number them the same way we did
1411 * - then we encode the initial region colours in a Slant-like
1412 * fashion (digits 0-3 interspersed with letters giving
1413 * lengths of runs of empty spaces).
1415 retlen = retsize = 0;
1422 * Start with a notional non-edge, so that there'll be an
1423 * explicit `a' to distinguish the case where we start with
1429 for (i = 0; i < w*(h-1) + (w-1)*h; i++) {
1430 int x, y, dx, dy, v;
1433 /* Horizontal edge. */
1439 /* Vertical edge. */
1440 x = (i - w*(h-1)) / h;
1441 y = (i - w*(h-1)) % h;
1446 if (retlen + 10 >= retsize) {
1447 retsize = retlen + 256;
1448 ret = sresize(ret, retsize, char);
1451 v = (map[y*w+x] != map[(y+dy)*w+(x+dx)]);
1454 ret[retlen++] = 'a'-1 + run;
1459 * 'z' is a special case in this encoding. Rather
1460 * than meaning a run of 26 and a state switch, it
1461 * means a run of 25 and _no_ state switch, because
1462 * otherwise there'd be no way to encode runs of
1466 ret[retlen++] = 'z';
1473 ret[retlen++] = 'a'-1 + run;
1474 ret[retlen++] = ',';
1477 for (i = 0; i < n; i++) {
1478 if (retlen + 10 >= retsize) {
1479 retsize = retlen + 256;
1480 ret = sresize(ret, retsize, char);
1483 if (colouring[i] < 0) {
1485 * In _this_ encoding, 'z' is a run of 26, since
1486 * there's no implicit state switch after each run.
1487 * Confusingly different, but more compact.
1490 ret[retlen++] = 'z';
1496 ret[retlen++] = 'a'-1 + run;
1497 ret[retlen++] = '0' + colouring[i];
1502 ret[retlen++] = 'a'-1 + run;
1505 assert(retlen < retsize);
1518 static char *parse_edge_list(game_params *params, char **desc, int *map)
1520 int w = params->w, h = params->h, wh = w*h, n = params->n;
1521 int i, k, pos, state;
1524 for (i = 0; i < wh; i++)
1531 * Parse the game description to get the list of edges, and
1532 * build up a disjoint set forest as we go (by identifying
1533 * pairs of squares whenever the edge list shows a non-edge).
1535 while (*p && *p != ',') {
1536 if (*p < 'a' || *p > 'z')
1537 return "Unexpected character in edge list";
1548 } else if (pos < w*(h-1)) {
1549 /* Horizontal edge. */
1554 } else if (pos < 2*wh-w-h) {
1555 /* Vertical edge. */
1556 x = (pos - w*(h-1)) / h;
1557 y = (pos - w*(h-1)) % h;
1561 return "Too much data in edge list";
1563 dsf_merge(map+wh, y*w+x, (y+dy)*w+(x+dx));
1571 assert(pos <= 2*wh-w-h);
1573 return "Too little data in edge list";
1576 * Now go through again and allocate region numbers.
1579 for (i = 0; i < wh; i++)
1581 for (i = 0; i < wh; i++) {
1582 k = dsf_canonify(map+wh, i);
1588 return "Edge list defines the wrong number of regions";
1595 static char *validate_desc(game_params *params, char *desc)
1597 int w = params->w, h = params->h, wh = w*h, n = params->n;
1602 map = snewn(2*wh, int);
1603 ret = parse_edge_list(params, &desc, map);
1609 return "Expected comma before clue list";
1610 desc++; /* eat comma */
1614 if (*desc >= '0' && *desc < '0'+FOUR)
1616 else if (*desc >= 'a' && *desc <= 'z')
1617 area += *desc - 'a' + 1;
1619 return "Unexpected character in clue list";
1623 return "Too little data in clue list";
1625 return "Too much data in clue list";
1630 static game_state *new_game(midend *me, game_params *params, char *desc)
1632 int w = params->w, h = params->h, wh = w*h, n = params->n;
1635 game_state *state = snew(game_state);
1638 state->colouring = snewn(n, int);
1639 for (i = 0; i < n; i++)
1640 state->colouring[i] = -1;
1641 state->pencil = snewn(n, int);
1642 for (i = 0; i < n; i++)
1643 state->pencil[i] = 0;
1645 state->completed = state->cheated = FALSE;
1647 state->map = snew(struct map);
1648 state->map->refcount = 1;
1649 state->map->map = snewn(wh*4, int);
1650 state->map->graph = snewn(n*n, int);
1652 state->map->immutable = snewn(n, int);
1653 for (i = 0; i < n; i++)
1654 state->map->immutable[i] = FALSE;
1660 ret = parse_edge_list(params, &p, state->map->map);
1665 * Set up the other three quadrants in `map'.
1667 for (i = wh; i < 4*wh; i++)
1668 state->map->map[i] = state->map->map[i % wh];
1674 * Now process the clue list.
1678 if (*p >= '0' && *p < '0'+FOUR) {
1679 state->colouring[pos] = *p - '0';
1680 state->map->immutable[pos] = TRUE;
1683 assert(*p >= 'a' && *p <= 'z');
1684 pos += *p - 'a' + 1;
1690 state->map->ngraph = gengraph(w, h, n, state->map->map, state->map->graph);
1693 * Attempt to smooth out some of the more jagged region
1694 * outlines by the judicious use of diagonally divided squares.
1697 random_state *rs = random_init(desc, strlen(desc));
1698 int *squares = snewn(wh, int);
1701 for (i = 0; i < wh; i++)
1703 shuffle(squares, wh, sizeof(*squares), rs);
1706 done_something = FALSE;
1707 for (i = 0; i < wh; i++) {
1708 int y = squares[i] / w, x = squares[i] % w;
1709 int c = state->map->map[y*w+x];
1712 if (x == 0 || x == w-1 || y == 0 || y == h-1)
1715 if (state->map->map[TE * wh + y*w+x] !=
1716 state->map->map[BE * wh + y*w+x])
1719 tc = state->map->map[BE * wh + (y-1)*w+x];
1720 bc = state->map->map[TE * wh + (y+1)*w+x];
1721 lc = state->map->map[RE * wh + y*w+(x-1)];
1722 rc = state->map->map[LE * wh + y*w+(x+1)];
1725 * If this square is adjacent on two sides to one
1726 * region and on the other two sides to the other
1727 * region, and is itself one of the two regions, we can
1728 * adjust it so that it's a diagonal.
1730 if (tc != bc && (tc == c || bc == c)) {
1731 if ((lc == tc && rc == bc) ||
1732 (lc == bc && rc == tc)) {
1733 state->map->map[TE * wh + y*w+x] = tc;
1734 state->map->map[BE * wh + y*w+x] = bc;
1735 state->map->map[LE * wh + y*w+x] = lc;
1736 state->map->map[RE * wh + y*w+x] = rc;
1737 done_something = TRUE;
1741 } while (done_something);
1747 * Analyse the map to find a canonical line segment
1748 * corresponding to each edge. These are where we'll eventually
1749 * put error markers.
1752 int *bestx, *besty, *an, pass;
1753 float *ax, *ay, *best;
1755 ax = snewn(state->map->ngraph, float);
1756 ay = snewn(state->map->ngraph, float);
1757 an = snewn(state->map->ngraph, int);
1758 bestx = snewn(state->map->ngraph, int);
1759 besty = snewn(state->map->ngraph, int);
1760 best = snewn(state->map->ngraph, float);
1762 for (i = 0; i < state->map->ngraph; i++) {
1763 bestx[i] = besty[i] = -1;
1764 best[i] = 2*(w+h)+1;
1765 ax[i] = ay[i] = 0.0F;
1770 * We make two passes over the map, finding all the line
1771 * segments separating regions. In the first pass, we
1772 * compute the _average_ x and y coordinate of all the line
1773 * segments separating each pair of regions; in the second
1774 * pass, for each such average point, we find the line
1775 * segment closest to it and call that canonical.
1777 * Line segments are considered to have coordinates in
1778 * their centre. Thus, at least one coordinate for any line
1779 * segment is always something-and-a-half; so we store our
1780 * coordinates as twice their normal value.
1782 for (pass = 0; pass < 2; pass++) {
1785 for (y = 0; y < h; y++)
1786 for (x = 0; x < w; x++) {
1787 int ex[4], ey[4], ea[4], eb[4], en = 0;
1790 * Look for an edge to the right of this
1791 * square, an edge below it, and an edge in the
1792 * middle of it. Also look to see if the point
1793 * at the bottom right of this square is on an
1794 * edge (and isn't a place where more than two
1799 ea[en] = state->map->map[RE * wh + y*w+x];
1800 eb[en] = state->map->map[LE * wh + y*w+(x+1)];
1801 if (ea[en] != eb[en]) {
1809 ea[en] = state->map->map[BE * wh + y*w+x];
1810 eb[en] = state->map->map[TE * wh + (y+1)*w+x];
1811 if (ea[en] != eb[en]) {
1818 ea[en] = state->map->map[TE * wh + y*w+x];
1819 eb[en] = state->map->map[BE * wh + y*w+x];
1820 if (ea[en] != eb[en]) {
1825 if (x+1 < w && y+1 < h) {
1826 /* bottom right corner */
1827 int oct[8], othercol, nchanges;
1828 oct[0] = state->map->map[RE * wh + y*w+x];
1829 oct[1] = state->map->map[LE * wh + y*w+(x+1)];
1830 oct[2] = state->map->map[BE * wh + y*w+(x+1)];
1831 oct[3] = state->map->map[TE * wh + (y+1)*w+(x+1)];
1832 oct[4] = state->map->map[LE * wh + (y+1)*w+(x+1)];
1833 oct[5] = state->map->map[RE * wh + (y+1)*w+x];
1834 oct[6] = state->map->map[TE * wh + (y+1)*w+x];
1835 oct[7] = state->map->map[BE * wh + y*w+x];
1839 for (i = 0; i < 8; i++) {
1840 if (oct[i] != oct[0]) {
1843 else if (othercol != oct[i])
1844 break; /* three colours at this point */
1846 if (oct[i] != oct[(i+1) & 7])
1851 * Now if there are exactly two regions at
1852 * this point (not one, and not three or
1853 * more), and only two changes around the
1854 * loop, then this is a valid place to put
1857 if (i == 8 && othercol >= 0 && nchanges == 2) {
1867 * Now process the edges we've found, one by
1870 for (i = 0; i < en; i++) {
1871 int emin = min(ea[i], eb[i]);
1872 int emax = max(ea[i], eb[i]);
1874 graph_edge_index(state->map->graph, n,
1875 state->map->ngraph, emin, emax);
1877 assert(gindex >= 0);
1881 * In pass 0, accumulate the values
1882 * we'll use to compute the average
1885 ax[gindex] += ex[i];
1886 ay[gindex] += ey[i];
1890 * In pass 1, work out whether this
1891 * point is closer to the average than
1892 * the last one we've seen.
1896 assert(an[gindex] > 0);
1897 dx = ex[i] - ax[gindex];
1898 dy = ey[i] - ay[gindex];
1899 d = sqrt(dx*dx + dy*dy);
1900 if (d < best[gindex]) {
1902 bestx[gindex] = ex[i];
1903 besty[gindex] = ey[i];
1910 for (i = 0; i < state->map->ngraph; i++)
1918 state->map->edgex = bestx;
1919 state->map->edgey = besty;
1921 for (i = 0; i < state->map->ngraph; i++)
1922 if (state->map->edgex[i] < 0) {
1923 /* Find the other representation of this edge. */
1924 int e = state->map->graph[i];
1925 int iprime = graph_edge_index(state->map->graph, n,
1926 state->map->ngraph, e%n, e/n);
1927 assert(state->map->edgex[iprime] >= 0);
1928 state->map->edgex[i] = state->map->edgex[iprime];
1929 state->map->edgey[i] = state->map->edgey[iprime];
1941 static game_state *dup_game(game_state *state)
1943 game_state *ret = snew(game_state);
1946 ret->colouring = snewn(state->p.n, int);
1947 memcpy(ret->colouring, state->colouring, state->p.n * sizeof(int));
1948 ret->pencil = snewn(state->p.n, int);
1949 memcpy(ret->pencil, state->pencil, state->p.n * sizeof(int));
1950 ret->map = state->map;
1951 ret->map->refcount++;
1952 ret->completed = state->completed;
1953 ret->cheated = state->cheated;
1958 static void free_game(game_state *state)
1960 if (--state->map->refcount <= 0) {
1961 sfree(state->map->map);
1962 sfree(state->map->graph);
1963 sfree(state->map->immutable);
1964 sfree(state->map->edgex);
1965 sfree(state->map->edgey);
1968 sfree(state->colouring);
1972 static char *solve_game(game_state *state, game_state *currstate,
1973 char *aux, char **error)
1980 struct solver_scratch *sc;
1984 int retlen, retsize;
1986 colouring = snewn(state->map->n, int);
1987 memcpy(colouring, state->colouring, state->map->n * sizeof(int));
1989 sc = new_scratch(state->map->graph, state->map->n, state->map->ngraph);
1990 sret = map_solver(sc, state->map->graph, state->map->n,
1991 state->map->ngraph, colouring, DIFFCOUNT-1);
1997 *error = "Puzzle is inconsistent";
1999 *error = "Unable to find a unique solution for this puzzle";
2004 ret = snewn(retsize, char);
2008 for (i = 0; i < state->map->n; i++) {
2011 assert(colouring[i] >= 0);
2012 if (colouring[i] == currstate->colouring[i])
2014 assert(!state->map->immutable[i]);
2016 len = sprintf(buf, ";%d:%d", colouring[i], i);
2017 if (retlen + len >= retsize) {
2018 retsize = retlen + len + 256;
2019 ret = sresize(ret, retsize, char);
2021 strcpy(ret + retlen, buf);
2032 static char *game_text_format(game_state *state)
2038 int drag_colour; /* -1 means no drag active */
2042 static game_ui *new_ui(game_state *state)
2044 game_ui *ui = snew(game_ui);
2045 ui->dragx = ui->dragy = -1;
2046 ui->drag_colour = -2;
2050 static void free_ui(game_ui *ui)
2055 static char *encode_ui(game_ui *ui)
2060 static void decode_ui(game_ui *ui, char *encoding)
2064 static void game_changed_state(game_ui *ui, game_state *oldstate,
2065 game_state *newstate)
2069 struct game_drawstate {
2071 unsigned long *drawn, *todraw;
2073 int dragx, dragy, drag_visible;
2077 /* Flags in `drawn'. */
2078 #define ERR_BASE 0x00800000L
2079 #define ERR_MASK 0xFF800000L
2080 #define PENCIL_T_BASE 0x00080000L
2081 #define PENCIL_T_MASK 0x00780000L
2082 #define PENCIL_B_BASE 0x00008000L
2083 #define PENCIL_B_MASK 0x00078000L
2084 #define PENCIL_MASK 0x007F8000L
2086 #define TILESIZE (ds->tilesize)
2087 #define BORDER (TILESIZE)
2088 #define COORD(x) ( (x) * TILESIZE + BORDER )
2089 #define FROMCOORD(x) ( ((x) - BORDER + TILESIZE) / TILESIZE - 1 )
2091 static int region_from_coords(game_state *state, game_drawstate *ds,
2094 int w = state->p.w, h = state->p.h, wh = w*h /*, n = state->p.n */;
2095 int tx = FROMCOORD(x), ty = FROMCOORD(y);
2096 int dx = x - COORD(tx), dy = y - COORD(ty);
2099 if (tx < 0 || tx >= w || ty < 0 || ty >= h)
2100 return -1; /* border */
2102 quadrant = 2 * (dx > dy) + (TILESIZE - dx > dy);
2103 quadrant = (quadrant == 0 ? BE :
2104 quadrant == 1 ? LE :
2105 quadrant == 2 ? RE : TE);
2107 return state->map->map[quadrant * wh + ty*w+tx];
2110 static char *interpret_move(game_state *state, game_ui *ui, game_drawstate *ds,
2111 int x, int y, int button)
2115 if (button == LEFT_BUTTON || button == RIGHT_BUTTON) {
2116 int r = region_from_coords(state, ds, x, y);
2119 ui->drag_colour = state->colouring[r];
2121 ui->drag_colour = -1;
2127 if ((button == LEFT_DRAG || button == RIGHT_DRAG) &&
2128 ui->drag_colour > -2) {
2134 if ((button == LEFT_RELEASE || button == RIGHT_RELEASE) &&
2135 ui->drag_colour > -2) {
2136 int r = region_from_coords(state, ds, x, y);
2137 int c = ui->drag_colour;
2140 * Cancel the drag, whatever happens.
2142 ui->drag_colour = -2;
2143 ui->dragx = ui->dragy = -1;
2146 return ""; /* drag into border; do nothing else */
2148 if (state->map->immutable[r])
2149 return ""; /* can't change this region */
2151 if (state->colouring[r] == c)
2152 return ""; /* don't _need_ to change this region */
2154 if (button == RIGHT_RELEASE && state->colouring[r] >= 0)
2155 return ""; /* can't pencil on a coloured region */
2157 sprintf(buf, "%s%c:%d", (button == RIGHT_RELEASE ? "p" : ""),
2158 (int)(c < 0 ? 'C' : '0' + c), r);
2165 static game_state *execute_move(game_state *state, char *move)
2168 game_state *ret = dup_game(state);
2179 if ((c == 'C' || (c >= '0' && c < '0'+FOUR)) &&
2180 sscanf(move+1, ":%d%n", &k, &adv) == 1 &&
2181 k >= 0 && k < state->p.n) {
2184 if (ret->colouring[k] >= 0) {
2191 ret->pencil[k] ^= 1 << (c - '0');
2193 ret->colouring[k] = (c == 'C' ? -1 : c - '0');
2196 } else if (*move == 'S') {
2198 ret->cheated = TRUE;
2204 if (*move && *move != ';') {
2213 * Check for completion.
2215 if (!ret->completed) {
2218 for (i = 0; i < n; i++)
2219 if (ret->colouring[i] < 0) {
2225 for (i = 0; i < ret->map->ngraph; i++) {
2226 int j = ret->map->graph[i] / n;
2227 int k = ret->map->graph[i] % n;
2228 if (ret->colouring[j] == ret->colouring[k]) {
2236 ret->completed = TRUE;
2242 /* ----------------------------------------------------------------------
2246 static void game_compute_size(game_params *params, int tilesize,
2249 /* Ick: fake up `ds->tilesize' for macro expansion purposes */
2250 struct { int tilesize; } ads, *ds = &ads;
2251 ads.tilesize = tilesize;
2253 *x = params->w * TILESIZE + 2 * BORDER + 1;
2254 *y = params->h * TILESIZE + 2 * BORDER + 1;
2257 static void game_set_size(drawing *dr, game_drawstate *ds,
2258 game_params *params, int tilesize)
2260 ds->tilesize = tilesize;
2263 blitter_free(dr, ds->bl);
2264 ds->bl = blitter_new(dr, TILESIZE+3, TILESIZE+3);
2267 const float map_colours[FOUR][3] = {
2271 {0.55F, 0.45F, 0.35F},
2273 const int map_hatching[FOUR] = {
2274 HATCH_VERT, HATCH_SLASH, HATCH_HORIZ, HATCH_BACKSLASH
2277 static float *game_colours(frontend *fe, game_state *state, int *ncolours)
2279 float *ret = snewn(3 * NCOLOURS, float);
2281 frontend_default_colour(fe, &ret[COL_BACKGROUND * 3]);
2283 ret[COL_GRID * 3 + 0] = 0.0F;
2284 ret[COL_GRID * 3 + 1] = 0.0F;
2285 ret[COL_GRID * 3 + 2] = 0.0F;
2287 memcpy(ret + COL_0 * 3, map_colours[0], 3 * sizeof(float));
2288 memcpy(ret + COL_1 * 3, map_colours[1], 3 * sizeof(float));
2289 memcpy(ret + COL_2 * 3, map_colours[2], 3 * sizeof(float));
2290 memcpy(ret + COL_3 * 3, map_colours[3], 3 * sizeof(float));
2292 ret[COL_ERROR * 3 + 0] = 1.0F;
2293 ret[COL_ERROR * 3 + 1] = 0.0F;
2294 ret[COL_ERROR * 3 + 2] = 0.0F;
2296 ret[COL_ERRTEXT * 3 + 0] = 1.0F;
2297 ret[COL_ERRTEXT * 3 + 1] = 1.0F;
2298 ret[COL_ERRTEXT * 3 + 2] = 1.0F;
2300 *ncolours = NCOLOURS;
2304 static game_drawstate *game_new_drawstate(drawing *dr, game_state *state)
2306 struct game_drawstate *ds = snew(struct game_drawstate);
2310 ds->drawn = snewn(state->p.w * state->p.h, unsigned long);
2311 for (i = 0; i < state->p.w * state->p.h; i++)
2312 ds->drawn[i] = 0xFFFFL;
2313 ds->todraw = snewn(state->p.w * state->p.h, unsigned long);
2314 ds->started = FALSE;
2316 ds->drag_visible = FALSE;
2317 ds->dragx = ds->dragy = -1;
2322 static void game_free_drawstate(drawing *dr, game_drawstate *ds)
2327 blitter_free(dr, ds->bl);
2331 static void draw_error(drawing *dr, game_drawstate *ds, int x, int y)
2339 coords[0] = x - TILESIZE*2/5;
2342 coords[3] = y - TILESIZE*2/5;
2343 coords[4] = x + TILESIZE*2/5;
2346 coords[7] = y + TILESIZE*2/5;
2347 draw_polygon(dr, coords, 4, COL_ERROR, COL_GRID);
2350 * Draw an exclamation mark in the diamond. This turns out to
2351 * look unpleasantly off-centre if done via draw_text, so I do
2352 * it by hand on the basis that exclamation marks aren't that
2353 * difficult to draw...
2356 yext = TILESIZE*2/5 - (xext*2+2);
2357 draw_rect(dr, x-xext, y-yext, xext*2+1, yext*2+1 - (xext*3),
2359 draw_rect(dr, x-xext, y+yext-xext*2+1, xext*2+1, xext*2, COL_ERRTEXT);
2362 static void draw_square(drawing *dr, game_drawstate *ds,
2363 game_params *params, struct map *map,
2364 int x, int y, int v)
2366 int w = params->w, h = params->h, wh = w*h;
2367 int tv, bv, xo, yo, errs, pencil;
2369 errs = v & ERR_MASK;
2371 pencil = v & PENCIL_MASK;
2376 clip(dr, COORD(x), COORD(y), TILESIZE, TILESIZE);
2379 * Draw the region colour.
2381 draw_rect(dr, COORD(x), COORD(y), TILESIZE, TILESIZE,
2382 (tv == FOUR ? COL_BACKGROUND : COL_0 + tv));
2384 * Draw the second region colour, if this is a diagonally
2387 if (map->map[TE * wh + y*w+x] != map->map[BE * wh + y*w+x]) {
2389 coords[0] = COORD(x)-1;
2390 coords[1] = COORD(y+1)+1;
2391 if (map->map[LE * wh + y*w+x] == map->map[TE * wh + y*w+x])
2392 coords[2] = COORD(x+1)+1;
2394 coords[2] = COORD(x)-1;
2395 coords[3] = COORD(y)-1;
2396 coords[4] = COORD(x+1)+1;
2397 coords[5] = COORD(y+1)+1;
2398 draw_polygon(dr, coords, 3,
2399 (bv == FOUR ? COL_BACKGROUND : COL_0 + bv), COL_GRID);
2403 * Draw `pencil marks'. Currently we arrange these in a square
2404 * formation, which means we may be in trouble if the value of
2405 * FOUR changes later...
2408 for (yo = 0; yo < 4; yo++)
2409 for (xo = 0; xo < 4; xo++) {
2410 int te = map->map[TE * wh + y*w+x];
2413 e = (yo < xo && yo < 3-xo ? TE :
2414 yo > xo && yo > 3-xo ? BE :
2416 ee = map->map[e * wh + y*w+x];
2418 c = (yo & 1) * 2 + (xo & 1);
2420 if (!(pencil & ((ee == te ? PENCIL_T_BASE : PENCIL_B_BASE) << c)))
2424 (map->map[TE * wh + y*w+x] != map->map[LE * wh + y*w+x]))
2425 continue; /* avoid TL-BR diagonal line */
2427 (map->map[TE * wh + y*w+x] != map->map[RE * wh + y*w+x]))
2428 continue; /* avoid BL-TR diagonal line */
2430 draw_rect(dr, COORD(x) + (5*xo+1)*TILESIZE/20,
2431 COORD(y) + (5*yo+1)*TILESIZE/20,
2432 4*TILESIZE/20, 4*TILESIZE/20, COL_0 + c);
2436 * Draw the grid lines, if required.
2438 if (x <= 0 || map->map[RE*wh+y*w+(x-1)] != map->map[LE*wh+y*w+x])
2439 draw_rect(dr, COORD(x), COORD(y), 1, TILESIZE, COL_GRID);
2440 if (y <= 0 || map->map[BE*wh+(y-1)*w+x] != map->map[TE*wh+y*w+x])
2441 draw_rect(dr, COORD(x), COORD(y), TILESIZE, 1, COL_GRID);
2442 if (x <= 0 || y <= 0 ||
2443 map->map[RE*wh+(y-1)*w+(x-1)] != map->map[TE*wh+y*w+x] ||
2444 map->map[BE*wh+(y-1)*w+(x-1)] != map->map[LE*wh+y*w+x])
2445 draw_rect(dr, COORD(x), COORD(y), 1, 1, COL_GRID);
2448 * Draw error markers.
2450 for (yo = 0; yo < 3; yo++)
2451 for (xo = 0; xo < 3; xo++)
2452 if (errs & (ERR_BASE << (yo*3+xo)))
2454 (COORD(x)*2+TILESIZE*xo)/2,
2455 (COORD(y)*2+TILESIZE*yo)/2);
2459 draw_update(dr, COORD(x), COORD(y), TILESIZE, TILESIZE);
2462 static void game_redraw(drawing *dr, game_drawstate *ds, game_state *oldstate,
2463 game_state *state, int dir, game_ui *ui,
2464 float animtime, float flashtime)
2466 int w = state->p.w, h = state->p.h, wh = w*h, n = state->p.n;
2470 if (ds->drag_visible) {
2471 blitter_load(dr, ds->bl, ds->dragx, ds->dragy);
2472 draw_update(dr, ds->dragx, ds->dragy, TILESIZE + 3, TILESIZE + 3);
2473 ds->drag_visible = FALSE;
2477 * The initial contents of the window are not guaranteed and
2478 * can vary with front ends. To be on the safe side, all games
2479 * should start by drawing a big background-colour rectangle
2480 * covering the whole window.
2485 game_compute_size(&state->p, TILESIZE, &ww, &wh);
2486 draw_rect(dr, 0, 0, ww, wh, COL_BACKGROUND);
2487 draw_rect(dr, COORD(0), COORD(0), w*TILESIZE+1, h*TILESIZE+1,
2490 draw_update(dr, 0, 0, ww, wh);
2495 if (flash_type == 1)
2496 flash = (int)(flashtime * FOUR / flash_length);
2498 flash = 1 + (int)(flashtime * THREE / flash_length);
2503 * Set up the `todraw' array.
2505 for (y = 0; y < h; y++)
2506 for (x = 0; x < w; x++) {
2507 int tv = state->colouring[state->map->map[TE * wh + y*w+x]];
2508 int bv = state->colouring[state->map->map[BE * wh + y*w+x]];
2517 if (flash_type == 1) {
2522 } else if (flash_type == 2) {
2527 tv = (tv + flash) % FOUR;
2529 bv = (bv + flash) % FOUR;
2538 for (i = 0; i < FOUR; i++) {
2539 if (state->colouring[state->map->map[TE * wh + y*w+x]] < 0 &&
2540 (state->pencil[state->map->map[TE * wh + y*w+x]] & (1<<i)))
2541 v |= PENCIL_T_BASE << i;
2542 if (state->colouring[state->map->map[BE * wh + y*w+x]] < 0 &&
2543 (state->pencil[state->map->map[BE * wh + y*w+x]] & (1<<i)))
2544 v |= PENCIL_B_BASE << i;
2547 ds->todraw[y*w+x] = v;
2551 * Add error markers to the `todraw' array.
2553 for (i = 0; i < state->map->ngraph; i++) {
2554 int v1 = state->map->graph[i] / n;
2555 int v2 = state->map->graph[i] % n;
2558 if (state->colouring[v1] < 0 || state->colouring[v2] < 0)
2560 if (state->colouring[v1] != state->colouring[v2])
2563 x = state->map->edgex[i];
2564 y = state->map->edgey[i];
2569 ds->todraw[y*w+x] |= ERR_BASE << (yo*3+xo);
2572 ds->todraw[y*w+(x-1)] |= ERR_BASE << (yo*3+2);
2576 ds->todraw[(y-1)*w+x] |= ERR_BASE << (2*3+xo);
2578 if (xo == 0 && yo == 0) {
2579 assert(x > 0 && y > 0);
2580 ds->todraw[(y-1)*w+(x-1)] |= ERR_BASE << (2*3+2);
2585 * Now actually draw everything.
2587 for (y = 0; y < h; y++)
2588 for (x = 0; x < w; x++) {
2589 int v = ds->todraw[y*w+x];
2590 if (ds->drawn[y*w+x] != v) {
2591 draw_square(dr, ds, &state->p, state->map, x, y, v);
2592 ds->drawn[y*w+x] = v;
2597 * Draw the dragged colour blob if any.
2599 if (ui->drag_colour > -2) {
2600 ds->dragx = ui->dragx - TILESIZE/2 - 2;
2601 ds->dragy = ui->dragy - TILESIZE/2 - 2;
2602 blitter_save(dr, ds->bl, ds->dragx, ds->dragy);
2603 draw_circle(dr, ui->dragx, ui->dragy, TILESIZE/2,
2604 (ui->drag_colour < 0 ? COL_BACKGROUND :
2605 COL_0 + ui->drag_colour), COL_GRID);
2606 draw_update(dr, ds->dragx, ds->dragy, TILESIZE + 3, TILESIZE + 3);
2607 ds->drag_visible = TRUE;
2611 static float game_anim_length(game_state *oldstate, game_state *newstate,
2612 int dir, game_ui *ui)
2617 static float game_flash_length(game_state *oldstate, game_state *newstate,
2618 int dir, game_ui *ui)
2620 if (!oldstate->completed && newstate->completed &&
2621 !oldstate->cheated && !newstate->cheated) {
2622 if (flash_type < 0) {
2623 char *env = getenv("MAP_ALTERNATIVE_FLASH");
2625 flash_type = atoi(env);
2628 flash_length = (flash_type == 1 ? 0.50 : 0.30);
2630 return flash_length;
2635 static int game_wants_statusbar(void)
2640 static int game_timing_state(game_state *state, game_ui *ui)
2645 static void game_print_size(game_params *params, float *x, float *y)
2650 * I'll use 4mm squares by default, I think. Simplest way to
2651 * compute this size is to compute the pixel puzzle size at a
2652 * given tile size and then scale.
2654 game_compute_size(params, 400, &pw, &ph);
2659 static void game_print(drawing *dr, game_state *state, int tilesize)
2661 int w = state->p.w, h = state->p.h, wh = w*h, n = state->p.n;
2662 int ink, c[FOUR], i;
2664 int *coords, ncoords, coordsize;
2666 /* Ick: fake up `ds->tilesize' for macro expansion purposes */
2667 struct { int tilesize; } ads, *ds = &ads;
2668 ads.tilesize = tilesize;
2670 ink = print_mono_colour(dr, 0);
2671 for (i = 0; i < FOUR; i++)
2672 c[i] = print_rgb_colour(dr, map_hatching[i], map_colours[i][0],
2673 map_colours[i][1], map_colours[i][2]);
2678 print_line_width(dr, TILESIZE / 16);
2681 * Draw a single filled polygon around each region.
2683 for (r = 0; r < n; r++) {
2684 int octants[8], lastdir, d1, d2, ox, oy;
2687 * Start by finding a point on the region boundary. Any
2688 * point will do. To do this, we'll search for a square
2689 * containing the region and then decide which corner of it
2693 for (y = 0; y < h; y++) {
2694 for (x = 0; x < w; x++) {
2695 if (state->map->map[wh*0+y*w+x] == r ||
2696 state->map->map[wh*1+y*w+x] == r ||
2697 state->map->map[wh*2+y*w+x] == r ||
2698 state->map->map[wh*3+y*w+x] == r)
2704 assert(y < h && x < w); /* we must have found one somewhere */
2706 * This is the first square in lexicographic order which
2707 * contains part of this region. Therefore, one of the top
2708 * two corners of the square must be what we're after. The
2709 * only case in which it isn't the top left one is if the
2710 * square is diagonally divided and the region is in the
2711 * bottom right half.
2713 if (state->map->map[wh*TE+y*w+x] != r &&
2714 state->map->map[wh*LE+y*w+x] != r)
2715 x++; /* could just as well have done y++ */
2718 * Now we have a point on the region boundary. Trace around
2719 * the region until we come back to this point,
2720 * accumulating coordinates for a polygon draw operation as
2730 * There are eight possible directions we could head in
2731 * from here. We identify them by octant numbers, and
2732 * we also use octant numbers to identify the spaces
2745 octants[0] = x<w && y>0 ? state->map->map[wh*LE+(y-1)*w+x] : -1;
2746 octants[1] = x<w && y>0 ? state->map->map[wh*BE+(y-1)*w+x] : -1;
2747 octants[2] = x<w && y<h ? state->map->map[wh*TE+y*w+x] : -1;
2748 octants[3] = x<w && y<h ? state->map->map[wh*LE+y*w+x] : -1;
2749 octants[4] = x>0 && y<h ? state->map->map[wh*RE+y*w+(x-1)] : -1;
2750 octants[5] = x>0 && y<h ? state->map->map[wh*TE+y*w+(x-1)] : -1;
2751 octants[6] = x>0 && y>0 ? state->map->map[wh*BE+(y-1)*w+(x-1)] :-1;
2752 octants[7] = x>0 && y>0 ? state->map->map[wh*RE+(y-1)*w+(x-1)] :-1;
2755 for (i = 0; i < 8; i++)
2756 if ((octants[i] == r) ^ (octants[(i+1)%8] == r)) {
2763 /* printf("%% %d,%d r=%d: d1=%d d2=%d lastdir=%d\n", x, y, r, d1, d2, lastdir); */
2764 assert(d1 != -1 && d2 != -1);
2769 * Now we're heading in direction d1. Save the current
2772 if (ncoords + 2 > coordsize) {
2774 coords = sresize(coords, coordsize, int);
2776 coords[ncoords++] = COORD(x);
2777 coords[ncoords++] = COORD(y);
2780 * Compute the new coordinates.
2782 x += (d1 % 4 == 3 ? 0 : d1 < 4 ? +1 : -1);
2783 y += (d1 % 4 == 1 ? 0 : d1 > 1 && d1 < 5 ? +1 : -1);
2784 assert(x >= 0 && x <= w && y >= 0 && y <= h);
2787 } while (x != ox || y != oy);
2789 draw_polygon(dr, coords, ncoords/2,
2790 state->colouring[r] >= 0 ?
2791 c[state->colouring[r]] : -1, ink);
2800 const struct game thegame = {
2808 TRUE, game_configure, custom_params,
2816 FALSE, game_text_format,
2824 20, game_compute_size, game_set_size,
2827 game_free_drawstate,
2831 TRUE, TRUE, game_print_size, game_print,
2832 game_wants_statusbar,
2833 FALSE, game_timing_state,
2834 0, /* mouse_priorities */