2 * map.c: Game involving four-colouring a map.
10 * - more solver brains?
11 * - better four-colouring algorithm?
25 * I don't seriously anticipate wanting to change the number of
26 * colours used in this game, but it doesn't cost much to use a
27 * #define just in case :-)
30 #define THREE (FOUR-1)
35 * Ghastly run-time configuration option, just for Gareth (again).
37 static int flash_type
= -1;
38 static float flash_length
;
41 * Difficulty levels. I do some macro ickery here to ensure that my
42 * enum and the various forms of my name list always match up.
47 #define ENUM(upper,title,lower) DIFF_ ## upper,
48 #define TITLE(upper,title,lower) #title,
49 #define ENCODE(upper,title,lower) #lower
50 #define CONFIG(upper,title,lower) ":" #title
51 enum { DIFFLIST(ENUM
) DIFFCOUNT
};
52 static char const *const map_diffnames
[] = { DIFFLIST(TITLE
) };
53 static char const map_diffchars
[] = DIFFLIST(ENCODE
);
54 #define DIFFCONFIG DIFFLIST(CONFIG)
56 enum { TE
, BE
, LE
, RE
}; /* top/bottom/left/right edges */
61 COL_0
, COL_1
, COL_2
, COL_3
,
82 int completed
, cheated
;
85 static game_params
*default_params(void)
87 game_params
*ret
= snew(game_params
);
92 ret
->diff
= DIFF_NORMAL
;
97 static const struct game_params map_presets
[] = {
98 {20, 15, 30, DIFF_EASY
},
99 {20, 15, 30, DIFF_NORMAL
},
100 {30, 25, 75, DIFF_NORMAL
},
103 static int game_fetch_preset(int i
, char **name
, game_params
**params
)
108 if (i
< 0 || i
>= lenof(map_presets
))
111 ret
= snew(game_params
);
112 *ret
= map_presets
[i
];
114 sprintf(str
, "%dx%d, %d regions, %s", ret
->w
, ret
->h
, ret
->n
,
115 map_diffnames
[ret
->diff
]);
122 static void free_params(game_params
*params
)
127 static game_params
*dup_params(game_params
*params
)
129 game_params
*ret
= snew(game_params
);
130 *ret
= *params
; /* structure copy */
134 static void decode_params(game_params
*params
, char const *string
)
136 char const *p
= string
;
139 while (*p
&& isdigit((unsigned char)*p
)) p
++;
143 while (*p
&& isdigit((unsigned char)*p
)) p
++;
145 params
->h
= params
->w
;
150 while (*p
&& (*p
== '.' || isdigit((unsigned char)*p
))) p
++;
152 params
->n
= params
->w
* params
->h
/ 8;
157 for (i
= 0; i
< DIFFCOUNT
; i
++)
158 if (*p
== map_diffchars
[i
])
164 static char *encode_params(game_params
*params
, int full
)
168 sprintf(ret
, "%dx%dn%d", params
->w
, params
->h
, params
->n
);
170 sprintf(ret
+ strlen(ret
), "d%c", map_diffchars
[params
->diff
]);
175 static config_item
*game_configure(game_params
*params
)
180 ret
= snewn(5, config_item
);
182 ret
[0].name
= "Width";
183 ret
[0].type
= C_STRING
;
184 sprintf(buf
, "%d", params
->w
);
185 ret
[0].sval
= dupstr(buf
);
188 ret
[1].name
= "Height";
189 ret
[1].type
= C_STRING
;
190 sprintf(buf
, "%d", params
->h
);
191 ret
[1].sval
= dupstr(buf
);
194 ret
[2].name
= "Regions";
195 ret
[2].type
= C_STRING
;
196 sprintf(buf
, "%d", params
->n
);
197 ret
[2].sval
= dupstr(buf
);
200 ret
[3].name
= "Difficulty";
201 ret
[3].type
= C_CHOICES
;
202 ret
[3].sval
= DIFFCONFIG
;
203 ret
[3].ival
= params
->diff
;
213 static game_params
*custom_params(config_item
*cfg
)
215 game_params
*ret
= snew(game_params
);
217 ret
->w
= atoi(cfg
[0].sval
);
218 ret
->h
= atoi(cfg
[1].sval
);
219 ret
->n
= atoi(cfg
[2].sval
);
220 ret
->diff
= cfg
[3].ival
;
225 static char *validate_params(game_params
*params
, int full
)
227 if (params
->w
< 2 || params
->h
< 2)
228 return "Width and height must be at least two";
230 return "Must have at least five regions";
231 if (params
->n
> params
->w
* params
->h
)
232 return "Too many regions to fit in grid";
236 /* ----------------------------------------------------------------------
237 * Cumulative frequency table functions.
241 * Initialise a cumulative frequency table. (Hardly worth writing
242 * this function; all it does is to initialise everything in the
245 static void cf_init(int *table
, int n
)
249 for (i
= 0; i
< n
; i
++)
254 * Increment the count of symbol `sym' by `count'.
256 static void cf_add(int *table
, int n
, int sym
, int count
)
273 * Cumulative frequency lookup: return the total count of symbols
274 * with value less than `sym'.
276 static int cf_clookup(int *table
, int n
, int sym
)
278 int bit
, index
, limit
, count
;
283 assert(0 < sym
&& sym
<= n
);
285 count
= table
[0]; /* start with the whole table size */
295 * Find the least number with its lowest set bit in this
296 * position which is greater than or equal to sym.
298 index
= ((sym
+ bit
- 1) &~ (bit
* 2 - 1)) + bit
;
301 count
-= table
[index
];
312 * Single frequency lookup: return the count of symbol `sym'.
314 static int cf_slookup(int *table
, int n
, int sym
)
318 assert(0 <= sym
&& sym
< n
);
322 for (bit
= 1; sym
+bit
< n
&& !(sym
& bit
); bit
<<= 1)
323 count
-= table
[sym
+bit
];
329 * Return the largest symbol index such that the cumulative
330 * frequency up to that symbol is less than _or equal to_ count.
332 static int cf_whichsym(int *table
, int n
, int count
) {
335 assert(count
>= 0 && count
< table
[0]);
346 if (count
>= top
- table
[sym
+bit
])
349 top
-= table
[sym
+bit
];
358 /* ----------------------------------------------------------------------
361 * FIXME: this isn't entirely optimal at present, because it
362 * inherently prioritises growing the largest region since there
363 * are more squares adjacent to it. This acts as a destabilising
364 * influence leading to a few large regions and mostly small ones.
365 * It might be better to do it some other way.
368 #define WEIGHT_INCREASED 2 /* for increased perimeter */
369 #define WEIGHT_DECREASED 4 /* for decreased perimeter */
370 #define WEIGHT_UNCHANGED 3 /* for unchanged perimeter */
373 * Look at a square and decide which colours can be extended into
376 * If called with index < 0, it adds together one of
377 * WEIGHT_INCREASED, WEIGHT_DECREASED or WEIGHT_UNCHANGED for each
378 * colour that has a valid extension (according to the effect that
379 * it would have on the perimeter of the region being extended) and
380 * returns the overall total.
382 * If called with index >= 0, it returns one of the possible
383 * colours depending on the value of index, in such a way that the
384 * number of possible inputs which would give rise to a given
385 * return value correspond to the weight of that value.
387 static int extend_options(int w
, int h
, int n
, int *map
,
388 int x
, int y
, int index
)
394 if (map
[y
*w
+x
] >= 0) {
396 return 0; /* can't do this square at all */
400 * Fetch the eight neighbours of this square, in order around
403 for (dy
= -1; dy
<= +1; dy
++)
404 for (dx
= -1; dx
<= +1; dx
++) {
405 int index
= (dy
< 0 ?
6-dx
: dy
> 0 ?
2+dx
: 2*(1+dx
));
406 if (x
+dx
>= 0 && x
+dx
< w
&& y
+dy
>= 0 && y
+dy
< h
)
407 col
[index
] = map
[(y
+dy
)*w
+(x
+dx
)];
413 * Iterate over each colour that might be feasible.
415 * FIXME: this routine currently has O(n) running time. We
416 * could turn it into O(FOUR) by only bothering to iterate over
417 * the colours mentioned in the four neighbouring squares.
420 for (c
= 0; c
< n
; c
++) {
421 int count
, neighbours
, runs
;
424 * One of the even indices of col (representing the
425 * orthogonal neighbours of this square) must be equal to
426 * c, or else this square is not adjacent to region c and
427 * obviously cannot become an extension of it at this time.
430 for (i
= 0; i
< 8; i
+= 2)
437 * Now we know this square is adjacent to region c. The
438 * next question is, would extending it cause the region to
439 * become non-simply-connected? If so, we mustn't do it.
441 * We determine this by looking around col to see if we can
442 * find more than one separate run of colour c.
445 for (i
= 0; i
< 8; i
++)
446 if (col
[i
] == c
&& col
[(i
+1) & 7] != c
)
454 * This square is a possibility. Determine its effect on
455 * the region's perimeter (computed from the number of
456 * orthogonal neighbours - 1 means a perimeter increase, 3
457 * a decrease, 2 no change; 4 is impossible because the
458 * region would already not be simply connected) and we're
461 assert(neighbours
> 0 && neighbours
< 4);
462 count
= (neighbours
== 1 ? WEIGHT_INCREASED
:
463 neighbours
== 2 ? WEIGHT_UNCHANGED
: WEIGHT_DECREASED
);
466 if (index
>= 0 && index
< count
)
477 static void genmap(int w
, int h
, int n
, int *map
, random_state
*rs
)
484 tmp
= snewn(wh
, int);
487 * Clear the map, and set up `tmp' as a list of grid indices.
489 for (i
= 0; i
< wh
; i
++) {
495 * Place the region seeds by selecting n members from `tmp'.
498 for (i
= 0; i
< n
; i
++) {
499 int j
= random_upto(rs
, k
);
505 * Re-initialise `tmp' as a cumulative frequency table. This
506 * will store the number of possible region colours we can
507 * extend into each square.
512 * Go through the grid and set up the initial cumulative
515 for (y
= 0; y
< h
; y
++)
516 for (x
= 0; x
< w
; x
++)
517 cf_add(tmp
, wh
, y
*w
+x
,
518 extend_options(w
, h
, n
, map
, x
, y
, -1));
521 * Now repeatedly choose a square we can extend a region into,
525 int k
= random_upto(rs
, tmp
[0]);
530 sq
= cf_whichsym(tmp
, wh
, k
);
531 k
-= cf_clookup(tmp
, wh
, sq
);
534 colour
= extend_options(w
, h
, n
, map
, x
, y
, k
);
539 * Re-scan the nine cells around the one we've just
542 for (yy
= max(y
-1, 0); yy
< min(y
+2, h
); yy
++)
543 for (xx
= max(x
-1, 0); xx
< min(x
+2, w
); xx
++) {
544 cf_add(tmp
, wh
, yy
*w
+xx
,
545 -cf_slookup(tmp
, wh
, yy
*w
+xx
) +
546 extend_options(w
, h
, n
, map
, xx
, yy
, -1));
551 * Finally, go through and normalise the region labels into
552 * order, meaning that indistinguishable maps are actually
555 for (i
= 0; i
< n
; i
++)
558 for (i
= 0; i
< wh
; i
++) {
562 map
[i
] = tmp
[map
[i
]];
568 /* ----------------------------------------------------------------------
569 * Functions to handle graphs.
573 * Having got a map in a square grid, convert it into a graph
576 static int gengraph(int w
, int h
, int n
, int *map
, int *graph
)
581 * Start by setting the graph up as an adjacency matrix. We'll
582 * turn it into a list later.
584 for (i
= 0; i
< n
*n
; i
++)
588 * Iterate over the map looking for all adjacencies.
590 for (y
= 0; y
< h
; y
++)
591 for (x
= 0; x
< w
; x
++) {
594 if (x
+1 < w
&& (vx
= map
[y
*w
+(x
+1)]) != v
)
595 graph
[v
*n
+vx
] = graph
[vx
*n
+v
] = 1;
596 if (y
+1 < h
&& (vy
= map
[(y
+1)*w
+x
]) != v
)
597 graph
[v
*n
+vy
] = graph
[vy
*n
+v
] = 1;
601 * Turn the matrix into a list.
603 for (i
= j
= 0; i
< n
*n
; i
++)
610 static int graph_adjacent(int *graph
, int n
, int ngraph
, int i
, int j
)
617 while (top
- bot
> 1) {
618 mid
= (top
+ bot
) / 2;
621 else if (graph
[mid
] < v
)
629 static int graph_vertex_start(int *graph
, int n
, int ngraph
, int i
)
636 while (top
- bot
> 1) {
637 mid
= (top
+ bot
) / 2;
646 /* ----------------------------------------------------------------------
647 * Generate a four-colouring of a graph.
649 * FIXME: it would be nice if we could convert this recursion into
650 * pseudo-recursion using some sort of explicit stack array, for
651 * the sake of the Palm port and its limited stack.
654 static int fourcolour_recurse(int *graph
, int n
, int ngraph
,
655 int *colouring
, int *scratch
, random_state
*rs
)
657 int nfree
, nvert
, start
, i
, j
, k
, c
, ci
;
661 * Find the smallest number of free colours in any uncoloured
662 * vertex, and count the number of such vertices.
665 nfree
= FIVE
; /* start off bigger than FOUR! */
667 for (i
= 0; i
< n
; i
++)
668 if (colouring
[i
] < 0 && scratch
[i
*FIVE
+FOUR
] <= nfree
) {
669 if (nfree
> scratch
[i
*FIVE
+FOUR
]) {
670 nfree
= scratch
[i
*FIVE
+FOUR
];
677 * If there aren't any uncoloured vertices at all, we're done.
680 return TRUE
; /* we've got a colouring! */
683 * Pick a random vertex in that set.
685 j
= random_upto(rs
, nvert
);
686 for (i
= 0; i
< n
; i
++)
687 if (colouring
[i
] < 0 && scratch
[i
*FIVE
+FOUR
] == nfree
)
691 start
= graph_vertex_start(graph
, n
, ngraph
, i
);
694 * Loop over the possible colours for i, and recurse for each
698 for (c
= 0; c
< FOUR
; c
++)
699 if (scratch
[i
*FIVE
+c
] == 0)
701 shuffle(cs
, ci
, sizeof(*cs
), rs
);
707 * Fill in this colour.
712 * Update the scratch space to reflect a new neighbour
713 * of this colour for each neighbour of vertex i.
715 for (j
= start
; j
< ngraph
&& graph
[j
] < n
*(i
+1); j
++) {
717 if (scratch
[k
*FIVE
+c
] == 0)
718 scratch
[k
*FIVE
+FOUR
]--;
725 if (fourcolour_recurse(graph
, n
, ngraph
, colouring
, scratch
, rs
))
726 return TRUE
; /* got one! */
729 * If that didn't work, clean up and try again with a
732 for (j
= start
; j
< ngraph
&& graph
[j
] < n
*(i
+1); j
++) {
735 if (scratch
[k
*FIVE
+c
] == 0)
736 scratch
[k
*FIVE
+FOUR
]++;
742 * If we reach here, we were unable to find a colouring at all.
743 * (This doesn't necessarily mean the Four Colour Theorem is
744 * violated; it might just mean we've gone down a dead end and
745 * need to back up and look somewhere else. It's only an FCT
746 * violation if we get all the way back up to the top level and
752 static void fourcolour(int *graph
, int n
, int ngraph
, int *colouring
,
759 * For each vertex and each colour, we store the number of
760 * neighbours that have that colour. Also, we store the number
761 * of free colours for the vertex.
763 scratch
= snewn(n
* FIVE
, int);
764 for (i
= 0; i
< n
* FIVE
; i
++)
765 scratch
[i
] = (i
% FIVE
== FOUR ? FOUR
: 0);
768 * Clear the colouring to start with.
770 for (i
= 0; i
< n
; i
++)
773 i
= fourcolour_recurse(graph
, n
, ngraph
, colouring
, scratch
, rs
);
774 assert(i
); /* by the Four Colour Theorem :-) */
779 /* ----------------------------------------------------------------------
780 * Non-recursive solver.
783 struct solver_scratch
{
784 unsigned char *possible
; /* bitmap of colours for each region */
790 static struct solver_scratch
*new_scratch(int *graph
, int n
, int ngraph
)
792 struct solver_scratch
*sc
;
794 sc
= snew(struct solver_scratch
);
798 sc
->possible
= snewn(n
, unsigned char);
803 static void free_scratch(struct solver_scratch
*sc
)
809 static int place_colour(struct solver_scratch
*sc
,
810 int *colouring
, int index
, int colour
)
812 int *graph
= sc
->graph
, n
= sc
->n
, ngraph
= sc
->ngraph
;
815 if (!(sc
->possible
[index
] & (1 << colour
)))
816 return FALSE
; /* can't do it */
818 sc
->possible
[index
] = 1 << colour
;
819 colouring
[index
] = colour
;
822 * Rule out this colour from all the region's neighbours.
824 for (j
= graph_vertex_start(graph
, n
, ngraph
, index
);
825 j
< ngraph
&& graph
[j
] < n
*(index
+1); j
++) {
826 k
= graph
[j
] - index
*n
;
827 sc
->possible
[k
] &= ~(1 << colour
);
834 * Returns 0 for impossible, 1 for success, 2 for failure to
835 * converge (i.e. puzzle is either ambiguous or just too
838 static int map_solver(struct solver_scratch
*sc
,
839 int *graph
, int n
, int ngraph
, int *colouring
,
845 * Initialise scratch space.
847 for (i
= 0; i
< n
; i
++)
848 sc
->possible
[i
] = (1 << FOUR
) - 1;
853 for (i
= 0; i
< n
; i
++)
854 if (colouring
[i
] >= 0) {
855 if (!place_colour(sc
, colouring
, i
, colouring
[i
]))
856 return 0; /* the clues aren't even consistent! */
860 * Now repeatedly loop until we find nothing further to do.
863 int done_something
= FALSE
;
865 if (difficulty
< DIFF_EASY
)
866 break; /* can't do anything at all! */
869 * Simplest possible deduction: find a region with only one
872 for (i
= 0; i
< n
; i
++) if (colouring
[i
] < 0) {
873 int p
= sc
->possible
[i
];
876 return 0; /* puzzle is inconsistent */
878 if ((p
& (p
-1)) == 0) { /* p is a power of two */
880 for (c
= 0; c
< FOUR
; c
++)
884 if (!place_colour(sc
, colouring
, i
, c
))
885 return 0; /* found puzzle to be inconsistent */
886 done_something
= TRUE
;
893 if (difficulty
< DIFF_NORMAL
)
894 break; /* can't do anything harder */
897 * Failing that, go up one level. Look for pairs of regions
898 * which (a) both have the same pair of possible colours,
899 * (b) are adjacent to one another, (c) are adjacent to the
900 * same region, and (d) that region still thinks it has one
901 * or both of those possible colours.
903 * Simplest way to do this is by going through the graph
904 * edge by edge, so that we start with property (b) and
905 * then look for (a) and finally (c) and (d).
907 for (i
= 0; i
< ngraph
; i
++) {
908 int j1
= graph
[i
] / n
, j2
= graph
[i
] % n
;
912 continue; /* done it already, other way round */
914 if (colouring
[j1
] >= 0 || colouring
[j2
] >= 0)
915 continue; /* they're not undecided */
917 if (sc
->possible
[j1
] != sc
->possible
[j2
])
918 continue; /* they don't have the same possibles */
920 v
= sc
->possible
[j1
];
922 * See if v contains exactly two set bits.
924 v2
= v
& -v
; /* find lowest set bit */
925 v2
= v
& ~v2
; /* clear it */
926 if (v2
== 0 || (v2
& (v2
-1)) != 0) /* not power of 2 */
930 * We've found regions j1 and j2 satisfying properties
931 * (a) and (b): they have two possible colours between
932 * them, and since they're adjacent to one another they
933 * must use _both_ those colours between them.
934 * Therefore, if they are both adjacent to any other
935 * region then that region cannot be either colour.
937 * Go through the neighbours of j1 and see if any are
940 for (j
= graph_vertex_start(graph
, n
, ngraph
, j1
);
941 j
< ngraph
&& graph
[j
] < n
*(j1
+1); j
++) {
943 if (graph_adjacent(graph
, n
, ngraph
, k
, j2
) &&
944 (sc
->possible
[k
] & v
)) {
945 sc
->possible
[k
] &= ~v
;
946 done_something
= TRUE
;
956 * We've run out of things to deduce. See if we've got the lot.
958 for (i
= 0; i
< n
; i
++)
959 if (colouring
[i
] < 0)
962 return 1; /* success! */
965 /* ----------------------------------------------------------------------
966 * Game generation main function.
969 static char *new_game_desc(game_params
*params
, random_state
*rs
,
970 char **aux
, int interactive
)
972 struct solver_scratch
*sc
= NULL
;
973 int *map
, *graph
, ngraph
, *colouring
, *colouring2
, *regions
;
974 int i
, j
, w
, h
, n
, solveret
, cfreq
[FOUR
];
977 #ifdef GENERATION_DIAGNOSTICS
990 map
= snewn(wh
, int);
991 graph
= snewn(n
*n
, int);
992 colouring
= snewn(n
, int);
993 colouring2
= snewn(n
, int);
994 regions
= snewn(n
, int);
997 * This is the minimum difficulty below which we'll completely
998 * reject a map design. Normally we set this to one below the
999 * requested difficulty, ensuring that we have the right
1000 * result. However, for particularly dense maps or maps with
1001 * particularly few regions it might not be possible to get the
1002 * desired difficulty, so we will eventually drop this down to
1003 * -1 to indicate that any old map will do.
1005 mindiff
= params
->diff
;
1013 genmap(w
, h
, n
, map
, rs
);
1015 #ifdef GENERATION_DIAGNOSTICS
1016 for (y
= 0; y
< h
; y
++) {
1017 for (x
= 0; x
< w
; x
++) {
1022 putchar('a' + v
-36);
1024 putchar('A' + v
-10);
1033 * Convert the map into a graph.
1035 ngraph
= gengraph(w
, h
, n
, map
, graph
);
1037 #ifdef GENERATION_DIAGNOSTICS
1038 for (i
= 0; i
< ngraph
; i
++)
1039 printf("%d-%d\n", graph
[i
]/n
, graph
[i
]%n
);
1045 fourcolour(graph
, n
, ngraph
, colouring
, rs
);
1047 #ifdef GENERATION_DIAGNOSTICS
1048 for (i
= 0; i
< n
; i
++)
1049 printf("%d: %d\n", i
, colouring
[i
]);
1051 for (y
= 0; y
< h
; y
++) {
1052 for (x
= 0; x
< w
; x
++) {
1053 int v
= colouring
[map
[y
*w
+x
]];
1055 putchar('a' + v
-36);
1057 putchar('A' + v
-10);
1066 * Encode the solution as an aux string.
1068 if (*aux
) /* in case we've come round again */
1070 retlen
= retsize
= 0;
1072 for (i
= 0; i
< n
; i
++) {
1075 if (colouring
[i
] < 0)
1078 len
= sprintf(buf
, "%s%d:%d", i ?
";" : "S;", colouring
[i
], i
);
1079 if (retlen
+ len
>= retsize
) {
1080 retsize
= retlen
+ len
+ 256;
1081 ret
= sresize(ret
, retsize
, char);
1083 strcpy(ret
+ retlen
, buf
);
1089 * Remove the region colours one by one, keeping
1090 * solubility. Also ensure that there always remains at
1091 * least one region of every colour, so that the user can
1092 * drag from somewhere.
1094 for (i
= 0; i
< FOUR
; i
++)
1096 for (i
= 0; i
< n
; i
++) {
1098 cfreq
[colouring
[i
]]++;
1100 for (i
= 0; i
< FOUR
; i
++)
1104 shuffle(regions
, n
, sizeof(*regions
), rs
);
1106 if (sc
) free_scratch(sc
);
1107 sc
= new_scratch(graph
, n
, ngraph
);
1109 for (i
= 0; i
< n
; i
++) {
1112 if (cfreq
[colouring
[j
]] == 1)
1113 continue; /* can't remove last region of colour */
1115 memcpy(colouring2
, colouring
, n
*sizeof(int));
1117 solveret
= map_solver(sc
, graph
, n
, ngraph
, colouring2
,
1119 assert(solveret
>= 0); /* mustn't be impossible! */
1120 if (solveret
== 1) {
1121 cfreq
[colouring
[j
]]--;
1126 #ifdef GENERATION_DIAGNOSTICS
1127 for (i
= 0; i
< n
; i
++)
1128 if (colouring
[i
] >= 0) {
1132 putchar('a' + i
-36);
1134 putchar('A' + i
-10);
1137 printf(": %d\n", colouring
[i
]);
1142 * Finally, check that the puzzle is _at least_ as hard as
1143 * required, and indeed that it isn't already solved.
1144 * (Calling map_solver with negative difficulty ensures the
1145 * latter - if a solver which _does nothing_ can't solve
1146 * it, it's too easy!)
1148 memcpy(colouring2
, colouring
, n
*sizeof(int));
1149 if (map_solver(sc
, graph
, n
, ngraph
, colouring2
,
1150 mindiff
- 1) == 1) {
1152 * Drop minimum difficulty if necessary.
1154 if (mindiff
> 0 && (n
< 9 || n
> 3*wh
/2)) {
1156 mindiff
= 0; /* give up and go for Easy */
1165 * Encode as a game ID. We do this by:
1167 * - first going along the horizontal edges row by row, and
1168 * then the vertical edges column by column
1169 * - encoding the lengths of runs of edges and runs of
1171 * - the decoder will reconstitute the region boundaries from
1172 * this and automatically number them the same way we did
1173 * - then we encode the initial region colours in a Slant-like
1174 * fashion (digits 0-3 interspersed with letters giving
1175 * lengths of runs of empty spaces).
1177 retlen
= retsize
= 0;
1184 * Start with a notional non-edge, so that there'll be an
1185 * explicit `a' to distinguish the case where we start with
1191 for (i
= 0; i
< w
*(h
-1) + (w
-1)*h
; i
++) {
1192 int x
, y
, dx
, dy
, v
;
1195 /* Horizontal edge. */
1201 /* Vertical edge. */
1202 x
= (i
- w
*(h
-1)) / h
;
1203 y
= (i
- w
*(h
-1)) % h
;
1208 if (retlen
+ 10 >= retsize
) {
1209 retsize
= retlen
+ 256;
1210 ret
= sresize(ret
, retsize
, char);
1213 v
= (map
[y
*w
+x
] != map
[(y
+dy
)*w
+(x
+dx
)]);
1216 ret
[retlen
++] = 'a'-1 + run
;
1221 * 'z' is a special case in this encoding. Rather
1222 * than meaning a run of 26 and a state switch, it
1223 * means a run of 25 and _no_ state switch, because
1224 * otherwise there'd be no way to encode runs of
1228 ret
[retlen
++] = 'z';
1235 ret
[retlen
++] = 'a'-1 + run
;
1236 ret
[retlen
++] = ',';
1239 for (i
= 0; i
< n
; i
++) {
1240 if (retlen
+ 10 >= retsize
) {
1241 retsize
= retlen
+ 256;
1242 ret
= sresize(ret
, retsize
, char);
1245 if (colouring
[i
] < 0) {
1247 * In _this_ encoding, 'z' is a run of 26, since
1248 * there's no implicit state switch after each run.
1249 * Confusingly different, but more compact.
1252 ret
[retlen
++] = 'z';
1258 ret
[retlen
++] = 'a'-1 + run
;
1259 ret
[retlen
++] = '0' + colouring
[i
];
1264 ret
[retlen
++] = 'a'-1 + run
;
1267 assert(retlen
< retsize
);
1280 static char *parse_edge_list(game_params
*params
, char **desc
, int *map
)
1282 int w
= params
->w
, h
= params
->h
, wh
= w
*h
, n
= params
->n
;
1283 int i
, k
, pos
, state
;
1286 for (i
= 0; i
< wh
; i
++)
1293 * Parse the game description to get the list of edges, and
1294 * build up a disjoint set forest as we go (by identifying
1295 * pairs of squares whenever the edge list shows a non-edge).
1297 while (*p
&& *p
!= ',') {
1298 if (*p
< 'a' || *p
> 'z')
1299 return "Unexpected character in edge list";
1310 } else if (pos
< w
*(h
-1)) {
1311 /* Horizontal edge. */
1316 } else if (pos
< 2*wh
-w
-h
) {
1317 /* Vertical edge. */
1318 x
= (pos
- w
*(h
-1)) / h
;
1319 y
= (pos
- w
*(h
-1)) % h
;
1323 return "Too much data in edge list";
1325 dsf_merge(map
+wh
, y
*w
+x
, (y
+dy
)*w
+(x
+dx
));
1333 assert(pos
<= 2*wh
-w
-h
);
1335 return "Too little data in edge list";
1338 * Now go through again and allocate region numbers.
1341 for (i
= 0; i
< wh
; i
++)
1343 for (i
= 0; i
< wh
; i
++) {
1344 k
= dsf_canonify(map
+wh
, i
);
1350 return "Edge list defines the wrong number of regions";
1357 static char *validate_desc(game_params
*params
, char *desc
)
1359 int w
= params
->w
, h
= params
->h
, wh
= w
*h
, n
= params
->n
;
1364 map
= snewn(2*wh
, int);
1365 ret
= parse_edge_list(params
, &desc
, map
);
1371 return "Expected comma before clue list";
1372 desc
++; /* eat comma */
1376 if (*desc
>= '0' && *desc
< '0'+FOUR
)
1378 else if (*desc
>= 'a' && *desc
<= 'z')
1379 area
+= *desc
- 'a' + 1;
1381 return "Unexpected character in clue list";
1385 return "Too little data in clue list";
1387 return "Too much data in clue list";
1392 static game_state
*new_game(midend
*me
, game_params
*params
, char *desc
)
1394 int w
= params
->w
, h
= params
->h
, wh
= w
*h
, n
= params
->n
;
1397 game_state
*state
= snew(game_state
);
1400 state
->colouring
= snewn(n
, int);
1401 for (i
= 0; i
< n
; i
++)
1402 state
->colouring
[i
] = -1;
1404 state
->completed
= state
->cheated
= FALSE
;
1406 state
->map
= snew(struct map
);
1407 state
->map
->refcount
= 1;
1408 state
->map
->map
= snewn(wh
*4, int);
1409 state
->map
->graph
= snewn(n
*n
, int);
1411 state
->map
->immutable
= snewn(n
, int);
1412 for (i
= 0; i
< n
; i
++)
1413 state
->map
->immutable
[i
] = FALSE
;
1419 ret
= parse_edge_list(params
, &p
, state
->map
->map
);
1424 * Set up the other three quadrants in `map'.
1426 for (i
= wh
; i
< 4*wh
; i
++)
1427 state
->map
->map
[i
] = state
->map
->map
[i
% wh
];
1433 * Now process the clue list.
1437 if (*p
>= '0' && *p
< '0'+FOUR
) {
1438 state
->colouring
[pos
] = *p
- '0';
1439 state
->map
->immutable
[pos
] = TRUE
;
1442 assert(*p
>= 'a' && *p
<= 'z');
1443 pos
+= *p
- 'a' + 1;
1449 state
->map
->ngraph
= gengraph(w
, h
, n
, state
->map
->map
, state
->map
->graph
);
1452 * Attempt to smooth out some of the more jagged region
1453 * outlines by the judicious use of diagonally divided squares.
1456 random_state
*rs
= random_init(desc
, strlen(desc
));
1457 int *squares
= snewn(wh
, int);
1460 for (i
= 0; i
< wh
; i
++)
1462 shuffle(squares
, wh
, sizeof(*squares
), rs
);
1465 done_something
= FALSE
;
1466 for (i
= 0; i
< wh
; i
++) {
1467 int y
= squares
[i
] / w
, x
= squares
[i
] % w
;
1468 int c
= state
->map
->map
[y
*w
+x
];
1471 if (x
== 0 || x
== w
-1 || y
== 0 || y
== h
-1)
1474 if (state
->map
->map
[TE
* wh
+ y
*w
+x
] !=
1475 state
->map
->map
[BE
* wh
+ y
*w
+x
])
1478 tc
= state
->map
->map
[BE
* wh
+ (y
-1)*w
+x
];
1479 bc
= state
->map
->map
[TE
* wh
+ (y
+1)*w
+x
];
1480 lc
= state
->map
->map
[RE
* wh
+ y
*w
+(x
-1)];
1481 rc
= state
->map
->map
[LE
* wh
+ y
*w
+(x
+1)];
1484 * If this square is adjacent on two sides to one
1485 * region and on the other two sides to the other
1486 * region, and is itself one of the two regions, we can
1487 * adjust it so that it's a diagonal.
1489 if (tc
!= bc
&& (tc
== c
|| bc
== c
)) {
1490 if ((lc
== tc
&& rc
== bc
) ||
1491 (lc
== bc
&& rc
== tc
)) {
1492 state
->map
->map
[TE
* wh
+ y
*w
+x
] = tc
;
1493 state
->map
->map
[BE
* wh
+ y
*w
+x
] = bc
;
1494 state
->map
->map
[LE
* wh
+ y
*w
+x
] = lc
;
1495 state
->map
->map
[RE
* wh
+ y
*w
+x
] = rc
;
1496 done_something
= TRUE
;
1500 } while (done_something
);
1508 static game_state
*dup_game(game_state
*state
)
1510 game_state
*ret
= snew(game_state
);
1513 ret
->colouring
= snewn(state
->p
.n
, int);
1514 memcpy(ret
->colouring
, state
->colouring
, state
->p
.n
* sizeof(int));
1515 ret
->map
= state
->map
;
1516 ret
->map
->refcount
++;
1517 ret
->completed
= state
->completed
;
1518 ret
->cheated
= state
->cheated
;
1523 static void free_game(game_state
*state
)
1525 if (--state
->map
->refcount
<= 0) {
1526 sfree(state
->map
->map
);
1527 sfree(state
->map
->graph
);
1528 sfree(state
->map
->immutable
);
1531 sfree(state
->colouring
);
1535 static char *solve_game(game_state
*state
, game_state
*currstate
,
1536 char *aux
, char **error
)
1543 struct solver_scratch
*sc
;
1547 int retlen
, retsize
;
1549 colouring
= snewn(state
->map
->n
, int);
1550 memcpy(colouring
, state
->colouring
, state
->map
->n
* sizeof(int));
1552 sc
= new_scratch(state
->map
->graph
, state
->map
->n
, state
->map
->ngraph
);
1553 sret
= map_solver(sc
, state
->map
->graph
, state
->map
->n
,
1554 state
->map
->ngraph
, colouring
, DIFFCOUNT
-1);
1560 *error
= "Puzzle is inconsistent";
1562 *error
= "Unable to find a unique solution for this puzzle";
1567 ret
= snewn(retsize
, char);
1571 for (i
= 0; i
< state
->map
->n
; i
++) {
1574 assert(colouring
[i
] >= 0);
1575 if (colouring
[i
] == currstate
->colouring
[i
])
1577 assert(!state
->map
->immutable
[i
]);
1579 len
= sprintf(buf
, ";%d:%d", colouring
[i
], i
);
1580 if (retlen
+ len
>= retsize
) {
1581 retsize
= retlen
+ len
+ 256;
1582 ret
= sresize(ret
, retsize
, char);
1584 strcpy(ret
+ retlen
, buf
);
1595 static char *game_text_format(game_state
*state
)
1601 int drag_colour
; /* -1 means no drag active */
1605 static game_ui
*new_ui(game_state
*state
)
1607 game_ui
*ui
= snew(game_ui
);
1608 ui
->dragx
= ui
->dragy
= -1;
1609 ui
->drag_colour
= -2;
1613 static void free_ui(game_ui
*ui
)
1618 static char *encode_ui(game_ui
*ui
)
1623 static void decode_ui(game_ui
*ui
, char *encoding
)
1627 static void game_changed_state(game_ui
*ui
, game_state
*oldstate
,
1628 game_state
*newstate
)
1632 struct game_drawstate
{
1634 unsigned char *drawn
;
1636 int dragx
, dragy
, drag_visible
;
1640 #define TILESIZE (ds->tilesize)
1641 #define BORDER (TILESIZE)
1642 #define COORD(x) ( (x) * TILESIZE + BORDER )
1643 #define FROMCOORD(x) ( ((x) - BORDER + TILESIZE) / TILESIZE - 1 )
1645 static int region_from_coords(game_state
*state
, game_drawstate
*ds
,
1648 int w
= state
->p
.w
, h
= state
->p
.h
, wh
= w
*h
/*, n = state->p.n */;
1649 int tx
= FROMCOORD(x
), ty
= FROMCOORD(y
);
1650 int dx
= x
- COORD(tx
), dy
= y
- COORD(ty
);
1653 if (tx
< 0 || tx
>= w
|| ty
< 0 || ty
>= h
)
1654 return -1; /* border */
1656 quadrant
= 2 * (dx
> dy
) + (TILESIZE
- dx
> dy
);
1657 quadrant
= (quadrant
== 0 ? BE
:
1658 quadrant
== 1 ? LE
:
1659 quadrant
== 2 ? RE
: TE
);
1661 return state
->map
->map
[quadrant
* wh
+ ty
*w
+tx
];
1664 static char *interpret_move(game_state
*state
, game_ui
*ui
, game_drawstate
*ds
,
1665 int x
, int y
, int button
)
1669 if (button
== LEFT_BUTTON
|| button
== RIGHT_BUTTON
) {
1670 int r
= region_from_coords(state
, ds
, x
, y
);
1673 ui
->drag_colour
= state
->colouring
[r
];
1675 ui
->drag_colour
= -1;
1681 if ((button
== LEFT_DRAG
|| button
== RIGHT_DRAG
) &&
1682 ui
->drag_colour
> -2) {
1688 if ((button
== LEFT_RELEASE
|| button
== RIGHT_RELEASE
) &&
1689 ui
->drag_colour
> -2) {
1690 int r
= region_from_coords(state
, ds
, x
, y
);
1691 int c
= ui
->drag_colour
;
1694 * Cancel the drag, whatever happens.
1696 ui
->drag_colour
= -2;
1697 ui
->dragx
= ui
->dragy
= -1;
1700 return ""; /* drag into border; do nothing else */
1702 if (state
->map
->immutable
[r
])
1703 return ""; /* can't change this region */
1705 if (state
->colouring
[r
] == c
)
1706 return ""; /* don't _need_ to change this region */
1708 sprintf(buf
, "%c:%d", (int)(c
< 0 ?
'C' : '0' + c
), r
);
1715 static game_state
*execute_move(game_state
*state
, char *move
)
1718 game_state
*ret
= dup_game(state
);
1723 if ((c
== 'C' || (c
>= '0' && c
< '0'+FOUR
)) &&
1724 sscanf(move
+1, ":%d%n", &k
, &adv
) == 1 &&
1725 k
>= 0 && k
< state
->p
.n
) {
1727 ret
->colouring
[k
] = (c
== 'C' ?
-1 : c
- '0');
1728 } else if (*move
== 'S') {
1730 ret
->cheated
= TRUE
;
1736 if (*move
&& *move
!= ';') {
1745 * Check for completion.
1747 if (!ret
->completed
) {
1750 for (i
= 0; i
< n
; i
++)
1751 if (ret
->colouring
[i
] < 0) {
1757 for (i
= 0; i
< ret
->map
->ngraph
; i
++) {
1758 int j
= ret
->map
->graph
[i
] / n
;
1759 int k
= ret
->map
->graph
[i
] % n
;
1760 if (ret
->colouring
[j
] == ret
->colouring
[k
]) {
1768 ret
->completed
= TRUE
;
1774 /* ----------------------------------------------------------------------
1778 static void game_compute_size(game_params
*params
, int tilesize
,
1781 /* Ick: fake up `ds->tilesize' for macro expansion purposes */
1782 struct { int tilesize
; } ads
, *ds
= &ads
;
1783 ads
.tilesize
= tilesize
;
1785 *x
= params
->w
* TILESIZE
+ 2 * BORDER
+ 1;
1786 *y
= params
->h
* TILESIZE
+ 2 * BORDER
+ 1;
1789 static void game_set_size(drawing
*dr
, game_drawstate
*ds
,
1790 game_params
*params
, int tilesize
)
1792 ds
->tilesize
= tilesize
;
1795 blitter_free(dr
, ds
->bl
);
1796 ds
->bl
= blitter_new(dr
, TILESIZE
+3, TILESIZE
+3);
1799 const float map_colours
[FOUR
][3] = {
1803 {0.55F
, 0.45F
, 0.35F
},
1805 const int map_hatching
[FOUR
] = {
1806 HATCH_VERT
, HATCH_SLASH
, HATCH_HORIZ
, HATCH_BACKSLASH
1809 static float *game_colours(frontend
*fe
, game_state
*state
, int *ncolours
)
1811 float *ret
= snewn(3 * NCOLOURS
, float);
1813 frontend_default_colour(fe
, &ret
[COL_BACKGROUND
* 3]);
1815 ret
[COL_GRID
* 3 + 0] = 0.0F
;
1816 ret
[COL_GRID
* 3 + 1] = 0.0F
;
1817 ret
[COL_GRID
* 3 + 2] = 0.0F
;
1819 memcpy(ret
+ COL_0
* 3, map_colours
[0], 3 * sizeof(float));
1820 memcpy(ret
+ COL_1
* 3, map_colours
[1], 3 * sizeof(float));
1821 memcpy(ret
+ COL_2
* 3, map_colours
[2], 3 * sizeof(float));
1822 memcpy(ret
+ COL_3
* 3, map_colours
[3], 3 * sizeof(float));
1824 *ncolours
= NCOLOURS
;
1828 static game_drawstate
*game_new_drawstate(drawing
*dr
, game_state
*state
)
1830 struct game_drawstate
*ds
= snew(struct game_drawstate
);
1833 ds
->drawn
= snewn(state
->p
.w
* state
->p
.h
, unsigned char);
1834 memset(ds
->drawn
, 0xFF, state
->p
.w
* state
->p
.h
);
1835 ds
->started
= FALSE
;
1837 ds
->drag_visible
= FALSE
;
1838 ds
->dragx
= ds
->dragy
= -1;
1843 static void game_free_drawstate(drawing
*dr
, game_drawstate
*ds
)
1847 blitter_free(dr
, ds
->bl
);
1851 static void draw_square(drawing
*dr
, game_drawstate
*ds
,
1852 game_params
*params
, struct map
*map
,
1853 int x
, int y
, int v
)
1855 int w
= params
->w
, h
= params
->h
, wh
= w
*h
;
1856 int tv
= v
/ FIVE
, bv
= v
% FIVE
;
1858 clip(dr
, COORD(x
), COORD(y
), TILESIZE
, TILESIZE
);
1861 * Draw the region colour.
1863 draw_rect(dr
, COORD(x
), COORD(y
), TILESIZE
, TILESIZE
,
1864 (tv
== FOUR ? COL_BACKGROUND
: COL_0
+ tv
));
1866 * Draw the second region colour, if this is a diagonally
1869 if (map
->map
[TE
* wh
+ y
*w
+x
] != map
->map
[BE
* wh
+ y
*w
+x
]) {
1871 coords
[0] = COORD(x
)-1;
1872 coords
[1] = COORD(y
+1)+1;
1873 if (map
->map
[LE
* wh
+ y
*w
+x
] == map
->map
[TE
* wh
+ y
*w
+x
])
1874 coords
[2] = COORD(x
+1)+1;
1876 coords
[2] = COORD(x
)-1;
1877 coords
[3] = COORD(y
)-1;
1878 coords
[4] = COORD(x
+1)+1;
1879 coords
[5] = COORD(y
+1)+1;
1880 draw_polygon(dr
, coords
, 3,
1881 (bv
== FOUR ? COL_BACKGROUND
: COL_0
+ bv
), COL_GRID
);
1885 * Draw the grid lines, if required.
1887 if (x
<= 0 || map
->map
[RE
*wh
+y
*w
+(x
-1)] != map
->map
[LE
*wh
+y
*w
+x
])
1888 draw_rect(dr
, COORD(x
), COORD(y
), 1, TILESIZE
, COL_GRID
);
1889 if (y
<= 0 || map
->map
[BE
*wh
+(y
-1)*w
+x
] != map
->map
[TE
*wh
+y
*w
+x
])
1890 draw_rect(dr
, COORD(x
), COORD(y
), TILESIZE
, 1, COL_GRID
);
1891 if (x
<= 0 || y
<= 0 ||
1892 map
->map
[RE
*wh
+(y
-1)*w
+(x
-1)] != map
->map
[TE
*wh
+y
*w
+x
] ||
1893 map
->map
[BE
*wh
+(y
-1)*w
+(x
-1)] != map
->map
[LE
*wh
+y
*w
+x
])
1894 draw_rect(dr
, COORD(x
), COORD(y
), 1, 1, COL_GRID
);
1897 draw_update(dr
, COORD(x
), COORD(y
), TILESIZE
, TILESIZE
);
1900 static void game_redraw(drawing
*dr
, game_drawstate
*ds
, game_state
*oldstate
,
1901 game_state
*state
, int dir
, game_ui
*ui
,
1902 float animtime
, float flashtime
)
1904 int w
= state
->p
.w
, h
= state
->p
.h
, wh
= w
*h
/*, n = state->p.n */;
1908 if (ds
->drag_visible
) {
1909 blitter_load(dr
, ds
->bl
, ds
->dragx
, ds
->dragy
);
1910 draw_update(dr
, ds
->dragx
, ds
->dragy
, TILESIZE
+ 3, TILESIZE
+ 3);
1911 ds
->drag_visible
= FALSE
;
1915 * The initial contents of the window are not guaranteed and
1916 * can vary with front ends. To be on the safe side, all games
1917 * should start by drawing a big background-colour rectangle
1918 * covering the whole window.
1923 game_compute_size(&state
->p
, TILESIZE
, &ww
, &wh
);
1924 draw_rect(dr
, 0, 0, ww
, wh
, COL_BACKGROUND
);
1925 draw_rect(dr
, COORD(0), COORD(0), w
*TILESIZE
+1, h
*TILESIZE
+1,
1928 draw_update(dr
, 0, 0, ww
, wh
);
1933 if (flash_type
== 1)
1934 flash
= (int)(flashtime
* FOUR
/ flash_length
);
1936 flash
= 1 + (int)(flashtime
* THREE
/ flash_length
);
1940 for (y
= 0; y
< h
; y
++)
1941 for (x
= 0; x
< w
; x
++) {
1942 int tv
= state
->colouring
[state
->map
->map
[TE
* wh
+ y
*w
+x
]];
1943 int bv
= state
->colouring
[state
->map
->map
[BE
* wh
+ y
*w
+x
]];
1952 if (flash_type
== 1) {
1957 } else if (flash_type
== 2) {
1962 tv
= (tv
+ flash
) % FOUR
;
1964 bv
= (bv
+ flash
) % FOUR
;
1970 if (ds
->drawn
[y
*w
+x
] != v
) {
1971 draw_square(dr
, ds
, &state
->p
, state
->map
, x
, y
, v
);
1972 ds
->drawn
[y
*w
+x
] = v
;
1977 * Draw the dragged colour blob if any.
1979 if (ui
->drag_colour
> -2) {
1980 ds
->dragx
= ui
->dragx
- TILESIZE
/2 - 2;
1981 ds
->dragy
= ui
->dragy
- TILESIZE
/2 - 2;
1982 blitter_save(dr
, ds
->bl
, ds
->dragx
, ds
->dragy
);
1983 draw_circle(dr
, ui
->dragx
, ui
->dragy
, TILESIZE
/2,
1984 (ui
->drag_colour
< 0 ? COL_BACKGROUND
:
1985 COL_0
+ ui
->drag_colour
), COL_GRID
);
1986 draw_update(dr
, ds
->dragx
, ds
->dragy
, TILESIZE
+ 3, TILESIZE
+ 3);
1987 ds
->drag_visible
= TRUE
;
1991 static float game_anim_length(game_state
*oldstate
, game_state
*newstate
,
1992 int dir
, game_ui
*ui
)
1997 static float game_flash_length(game_state
*oldstate
, game_state
*newstate
,
1998 int dir
, game_ui
*ui
)
2000 if (!oldstate
->completed
&& newstate
->completed
&&
2001 !oldstate
->cheated
&& !newstate
->cheated
) {
2002 if (flash_type
< 0) {
2003 char *env
= getenv("MAP_ALTERNATIVE_FLASH");
2005 flash_type
= atoi(env
);
2008 flash_length
= (flash_type
== 1 ?
0.50 : 0.30);
2010 return flash_length
;
2015 static int game_wants_statusbar(void)
2020 static int game_timing_state(game_state
*state
, game_ui
*ui
)
2025 static void game_print_size(game_params
*params
, float *x
, float *y
)
2030 * I'll use 4mm squares by default, I think. Simplest way to
2031 * compute this size is to compute the pixel puzzle size at a
2032 * given tile size and then scale.
2034 game_compute_size(params
, 400, &pw
, &ph
);
2039 static void game_print(drawing
*dr
, game_state
*state
, int tilesize
)
2041 int w
= state
->p
.w
, h
= state
->p
.h
, wh
= w
*h
, n
= state
->p
.n
;
2042 int ink
, c
[FOUR
], i
;
2044 int *coords
, ncoords
, coordsize
;
2046 /* Ick: fake up `ds->tilesize' for macro expansion purposes */
2047 struct { int tilesize
; } ads
, *ds
= &ads
;
2048 ads
.tilesize
= tilesize
;
2050 ink
= print_mono_colour(dr
, 0);
2051 for (i
= 0; i
< FOUR
; i
++)
2052 c
[i
] = print_rgb_colour(dr
, map_hatching
[i
], map_colours
[i
][0],
2053 map_colours
[i
][1], map_colours
[i
][2]);
2058 print_line_width(dr
, TILESIZE
/ 16);
2061 * Draw a single filled polygon around each region.
2063 for (r
= 0; r
< n
; r
++) {
2064 int octants
[8], lastdir
, d1
, d2
, ox
, oy
;
2067 * Start by finding a point on the region boundary. Any
2068 * point will do. To do this, we'll search for a square
2069 * containing the region and then decide which corner of it
2073 for (y
= 0; y
< h
; y
++) {
2074 for (x
= 0; x
< w
; x
++) {
2075 if (state
->map
->map
[wh
*0+y
*w
+x
] == r
||
2076 state
->map
->map
[wh
*1+y
*w
+x
] == r
||
2077 state
->map
->map
[wh
*2+y
*w
+x
] == r
||
2078 state
->map
->map
[wh
*3+y
*w
+x
] == r
)
2084 assert(y
< h
&& x
< w
); /* we must have found one somewhere */
2086 * This is the first square in lexicographic order which
2087 * contains part of this region. Therefore, one of the top
2088 * two corners of the square must be what we're after. The
2089 * only case in which it isn't the top left one is if the
2090 * square is diagonally divided and the region is in the
2091 * bottom right half.
2093 if (state
->map
->map
[wh
*TE
+y
*w
+x
] != r
&&
2094 state
->map
->map
[wh
*LE
+y
*w
+x
] != r
)
2095 x
++; /* could just as well have done y++ */
2098 * Now we have a point on the region boundary. Trace around
2099 * the region until we come back to this point,
2100 * accumulating coordinates for a polygon draw operation as
2110 * There are eight possible directions we could head in
2111 * from here. We identify them by octant numbers, and
2112 * we also use octant numbers to identify the spaces
2125 octants
[0] = x
<w
&& y
>0 ? state
->map
->map
[wh
*LE
+(y
-1)*w
+x
] : -1;
2126 octants
[1] = x
<w
&& y
>0 ? state
->map
->map
[wh
*BE
+(y
-1)*w
+x
] : -1;
2127 octants
[2] = x
<w
&& y
<h ? state
->map
->map
[wh
*TE
+y
*w
+x
] : -1;
2128 octants
[3] = x
<w
&& y
<h ? state
->map
->map
[wh
*LE
+y
*w
+x
] : -1;
2129 octants
[4] = x
>0 && y
<h ? state
->map
->map
[wh
*RE
+y
*w
+(x
-1)] : -1;
2130 octants
[5] = x
>0 && y
<h ? state
->map
->map
[wh
*TE
+y
*w
+(x
-1)] : -1;
2131 octants
[6] = x
>0 && y
>0 ? state
->map
->map
[wh
*BE
+(y
-1)*w
+(x
-1)] :-1;
2132 octants
[7] = x
>0 && y
>0 ? state
->map
->map
[wh
*RE
+(y
-1)*w
+(x
-1)] :-1;
2135 for (i
= 0; i
< 8; i
++)
2136 if ((octants
[i
] == r
) ^ (octants
[(i
+1)%8] == r
)) {
2143 /* printf("%% %d,%d r=%d: d1=%d d2=%d lastdir=%d\n", x, y, r, d1, d2, lastdir); */
2144 assert(d1
!= -1 && d2
!= -1);
2149 * Now we're heading in direction d1. Save the current
2152 if (ncoords
+ 2 > coordsize
) {
2154 coords
= sresize(coords
, coordsize
, int);
2156 coords
[ncoords
++] = COORD(x
);
2157 coords
[ncoords
++] = COORD(y
);
2160 * Compute the new coordinates.
2162 x
+= (d1
% 4 == 3 ?
0 : d1
< 4 ?
+1 : -1);
2163 y
+= (d1
% 4 == 1 ?
0 : d1
> 1 && d1
< 5 ?
+1 : -1);
2164 assert(x
>= 0 && x
<= w
&& y
>= 0 && y
<= h
);
2167 } while (x
!= ox
|| y
!= oy
);
2169 draw_polygon(dr
, coords
, ncoords
/2,
2170 state
->colouring
[r
] >= 0 ?
2171 c
[state
->colouring
[r
]] : -1, ink
);
2180 const struct game thegame
= {
2188 TRUE
, game_configure
, custom_params
,
2196 FALSE
, game_text_format
,
2204 20, game_compute_size
, game_set_size
,
2207 game_free_drawstate
,
2211 TRUE
, TRUE
, game_print_size
, game_print
,
2212 game_wants_statusbar
,
2213 FALSE
, game_timing_state
,
2214 0, /* mouse_priorities */