diff options
Diffstat (limited to 'apps/plugins/puzzles/src/hat-internal.h')
-rw-r--r-- | apps/plugins/puzzles/src/hat-internal.h | 271 |
1 files changed, 271 insertions, 0 deletions
diff --git a/apps/plugins/puzzles/src/hat-internal.h b/apps/plugins/puzzles/src/hat-internal.h new file mode 100644 index 0000000000..2be96327a8 --- /dev/null +++ b/apps/plugins/puzzles/src/hat-internal.h | |||
@@ -0,0 +1,271 @@ | |||
1 | /* | ||
2 | * Internal definitions for the hat.c tiling generator, shared between | ||
3 | * hat.c itself and hat-test.c. | ||
4 | */ | ||
5 | |||
6 | #include "puzzles.h" | ||
7 | |||
8 | /* | ||
9 | * Coordinate system: | ||
10 | * | ||
11 | * The output of this code lives on the tiling known to grid.c as | ||
12 | * 'Kites', which can be viewed as a tiling of hexagons each of which | ||
13 | * is subdivided into six kites sharing their pointy vertex, or | ||
14 | * (equivalently) a tiling of equilateral triangles each subdivided | ||
15 | * into three kits sharing their blunt vertex. | ||
16 | * | ||
17 | * We express coordinates in this system relative to the basis (1, r) | ||
18 | * where r = (1 + sqrt(3)i) / 2 is a primitive 6th root of unity. This | ||
19 | * gives us a system in which two integer coordinates can address any | ||
20 | * grid point, provided we scale up so that the side length of the | ||
21 | * equilateral triangles in the tiling is 6. | ||
22 | */ | ||
23 | |||
24 | typedef struct Point { | ||
25 | int x, y; /* represents x + yr */ | ||
26 | } Point; | ||
27 | |||
28 | static inline Point pointscale(int scale, Point a) | ||
29 | { | ||
30 | Point r = { scale * a.x, scale * a.y }; | ||
31 | return r; | ||
32 | } | ||
33 | |||
34 | static inline Point pointadd(Point a, Point b) | ||
35 | { | ||
36 | Point r = { a.x + b.x, a.y + b.y }; | ||
37 | return r; | ||
38 | } | ||
39 | |||
40 | /* | ||
41 | * We identify a single kite by the coordinates of its four vertices. | ||
42 | * This allows us to construct the coordinates of an adjacent kite by | ||
43 | * taking affine transformations of the original kite's vertices. | ||
44 | * | ||
45 | * This is a useful way to do it because it means that if you reflect | ||
46 | * the kite (by swapping its left and right vertices) then these | ||
47 | * transformations also perform in a reflected way. This will be | ||
48 | * useful in the code below that outputs the coordinates of each hat, | ||
49 | * because this way it can work by walking around its 8 kites using a | ||
50 | * fixed set of steps, and if the hat is reflected, then we just | ||
51 | * reflect the starting kite before doing that, and everything still | ||
52 | * works. | ||
53 | */ | ||
54 | |||
55 | typedef struct Kite { | ||
56 | Point centre, left, right, outer; | ||
57 | } Kite; | ||
58 | |||
59 | static inline Kite kite_left(Kite k) | ||
60 | { | ||
61 | Kite r; | ||
62 | r.centre = k.centre; | ||
63 | r.right = k.left; | ||
64 | r.outer = pointadd(pointscale(2, k.left), pointscale(-1, k.outer)); | ||
65 | r.left = pointadd(pointadd(k.centre, k.left), pointscale(-1, k.right)); | ||
66 | return r; | ||
67 | } | ||
68 | |||
69 | static inline Kite kite_right(Kite k) | ||
70 | { | ||
71 | Kite r; | ||
72 | r.centre = k.centre; | ||
73 | r.left = k.right; | ||
74 | r.outer = pointadd(pointscale(2, k.right), pointscale(-1, k.outer)); | ||
75 | r.right = pointadd(pointadd(k.centre, k.right), pointscale(-1, k.left)); | ||
76 | return r; | ||
77 | } | ||
78 | |||
79 | static inline Kite kite_forward_left(Kite k) | ||
80 | { | ||
81 | Kite r; | ||
82 | r.outer = k.outer; | ||
83 | r.right = k.left; | ||
84 | r.centre = pointadd(pointscale(2, k.left), pointscale(-1, k.centre)); | ||
85 | r.left = pointadd(pointadd(k.right, k.left), pointscale(-1, k.centre)); | ||
86 | return r; | ||
87 | } | ||
88 | |||
89 | static inline Kite kite_forward_right(Kite k) | ||
90 | { | ||
91 | Kite r; | ||
92 | r.outer = k.outer; | ||
93 | r.left = k.right; | ||
94 | r.centre = pointadd(pointscale(2, k.right), pointscale(-1, k.centre)); | ||
95 | r.right = pointadd(pointadd(k.left, k.right), pointscale(-1, k.centre)); | ||
96 | return r; | ||
97 | } | ||
98 | |||
99 | typedef enum KiteStep { KS_LEFT, KS_RIGHT, KS_F_LEFT, KS_F_RIGHT } KiteStep; | ||
100 | |||
101 | static inline Kite kite_step(Kite k, KiteStep step) | ||
102 | { | ||
103 | switch (step) { | ||
104 | case KS_LEFT: return kite_left(k); | ||
105 | case KS_RIGHT: return kite_right(k); | ||
106 | case KS_F_LEFT: return kite_forward_left(k); | ||
107 | default /* case KS_F_RIGHT */: return kite_forward_right(k); | ||
108 | } | ||
109 | } | ||
110 | |||
111 | /* | ||
112 | * Functiond to enumerate the kites in a rectangular region, in a | ||
113 | * serpentine-raster fashion so that every kite delivered shares an | ||
114 | * edge with a recent previous one. | ||
115 | */ | ||
116 | #define KE_NKEEP 3 | ||
117 | typedef struct KiteEnum { | ||
118 | /* Fields private to the enumerator */ | ||
119 | int state; | ||
120 | int x, y, w, h; | ||
121 | unsigned curr_index; | ||
122 | |||
123 | /* Fields the client can legitimately read out */ | ||
124 | Kite *curr; | ||
125 | Kite recent[KE_NKEEP]; | ||
126 | unsigned last_index; | ||
127 | KiteStep last_step; /* step that got curr from recent[last_index] */ | ||
128 | } KiteEnum; | ||
129 | void hat_kiteenum_first(KiteEnum *s, int w, int h); | ||
130 | bool hat_kiteenum_next(KiteEnum *s); | ||
131 | |||
132 | /* | ||
133 | * Assorted useful definitions. | ||
134 | */ | ||
135 | typedef enum TileType { TT_H, TT_T, TT_P, TT_F, TT_KITE, TT_HAT } TileType; | ||
136 | static const char tilechars[] = "HTPF"; | ||
137 | |||
138 | #define HAT_KITES 8 /* number of kites in a hat */ | ||
139 | #define MT_MAXEXPAND 13 /* largest number of metatiles in any expansion */ | ||
140 | |||
141 | /* | ||
142 | * Definitions for the autogenerated hat-tables.h header file that | ||
143 | * defines all the lookup tables. | ||
144 | */ | ||
145 | typedef struct KitemapEntry { | ||
146 | int kite, hat, meta; /* all -1 if impossible */ | ||
147 | } KitemapEntry; | ||
148 | |||
149 | typedef struct MetamapEntry { | ||
150 | int meta, meta2; | ||
151 | } MetamapEntry; | ||
152 | |||
153 | static inline size_t kitemap_index(KiteStep step, unsigned kite, | ||
154 | unsigned hat, unsigned meta) | ||
155 | { | ||
156 | return step + 4 * (kite + 8 * (hat + 4 * meta)); | ||
157 | } | ||
158 | |||
159 | static inline size_t metamap_index(unsigned meta, unsigned meta2) | ||
160 | { | ||
161 | return meta2 * MT_MAXEXPAND + meta; | ||
162 | } | ||
163 | |||
164 | /* | ||
165 | * Coordinate system for tracking kites within a randomly selected | ||
166 | * part of the recursively expanded hat tiling. | ||
167 | * | ||
168 | * HatCoords will store an array of HatCoord, in little-endian | ||
169 | * arrangement. So hc->c[0] will always have type TT_KITE and index a | ||
170 | * single kite within a hat; hc->c[1] will have type TT_HAT and index | ||
171 | * a hat within a first-order metatile; hc->c[2] will be the smallest | ||
172 | * metatile containing this hat, and hc->c[3, 4, 5, ...] will be | ||
173 | * higher-order metatiles as needed. | ||
174 | * | ||
175 | * The last coordinate stored, hc->c[hc->nc-1], will have a tile type | ||
176 | * but no index (represented by index==-1). This means "we haven't | ||
177 | * decided yet what this level of metatile needs to be". If we need to | ||
178 | * refer to this level during the hatctx_step algorithm, we make it up | ||
179 | * at random, based on a table of what metatiles each type can | ||
180 | * possibly be part of, at what index. | ||
181 | */ | ||
182 | typedef struct HatCoord { | ||
183 | int index; /* index within that tile, or -1 if not yet known */ | ||
184 | TileType type; /* type of this tile */ | ||
185 | } HatCoord; | ||
186 | |||
187 | typedef struct HatCoords { | ||
188 | HatCoord *c; | ||
189 | size_t nc, csize; | ||
190 | } HatCoords; | ||
191 | |||
192 | HatCoords *hat_coords_new(void); | ||
193 | void hat_coords_free(HatCoords *hc); | ||
194 | void hat_coords_make_space(HatCoords *hc, size_t size); | ||
195 | HatCoords *hat_coords_copy(HatCoords *hc_in); | ||
196 | |||
197 | #ifdef HAT_COORDS_DEBUG | ||
198 | static inline void hat_coords_debug(const char *prefix, HatCoords *hc, | ||
199 | const char *suffix) | ||
200 | { | ||
201 | const char *sep = ""; | ||
202 | static const char *const types[] = {"H","T","P","F","kite","hat"}; | ||
203 | |||
204 | fputs(prefix, stderr); | ||
205 | for (size_t i = 0; i < hc->nc; i++) { | ||
206 | fprintf(stderr, "%s %s ", sep, types[hc->c[i].type]); | ||
207 | sep = " ."; | ||
208 | if (hc->c[i].index == -1) | ||
209 | fputs("?", stderr); | ||
210 | else | ||
211 | fprintf(stderr, "%d", hc->c[i].index); | ||
212 | } | ||
213 | fputs(suffix, stderr); | ||
214 | } | ||
215 | #else | ||
216 | #define hat_coords_debug(p,c,s) ((void)0) | ||
217 | #endif | ||
218 | |||
219 | /* | ||
220 | * HatContext is the shared context of a whole run of the algorithm. | ||
221 | * Its 'prototype' HatCoords object represents the coordinates of the | ||
222 | * starting kite, and is extended as necessary; any other HatCoord | ||
223 | * that needs extending will copy the higher-order values from | ||
224 | * ctx->prototype as needed, so that once each choice has been made, | ||
225 | * it remains consistent. | ||
226 | * | ||
227 | * When we're inventing a random piece of tiling in the first place, | ||
228 | * we append to ctx->prototype by choosing a random (but legal) | ||
229 | * higher-level metatile for the current topmost one to turn out to be | ||
230 | * part of. When we're replaying a generation whose parameters are | ||
231 | * already stored, we don't have a random_state, and we make fixed | ||
232 | * decisions if not enough coordinates were provided. | ||
233 | * | ||
234 | * (Of course another approach would be to reject grid descriptions | ||
235 | * that didn't define enough coordinates! But that would involve a | ||
236 | * whole extra iteration over the whole grid region just for | ||
237 | * validation, and that seems like more timewasting than really | ||
238 | * needed. So we tolerate short descriptions, and do something | ||
239 | * deterministic with them.) | ||
240 | */ | ||
241 | |||
242 | typedef struct HatContext { | ||
243 | random_state *rs; | ||
244 | HatCoords *prototype; | ||
245 | } HatContext; | ||
246 | |||
247 | void hatctx_init_random(HatContext *ctx, random_state *rs); | ||
248 | void hatctx_cleanup(HatContext *ctx); | ||
249 | HatCoords *hatctx_initial_coords(HatContext *ctx); | ||
250 | void hatctx_extend_coords(HatContext *ctx, HatCoords *hc, size_t n); | ||
251 | HatCoords *hatctx_step(HatContext *ctx, HatCoords *hc_in, KiteStep step); | ||
252 | |||
253 | /* | ||
254 | * Subroutine of hat_tiling_generate, called for each kite in the grid | ||
255 | * as we iterate over it, to decide whether to generate an output hat | ||
256 | * and pass it to the client. Exposed in this header file so that | ||
257 | * hat-test can reuse it. | ||
258 | * | ||
259 | * We do this by starting from kite #0 of each hat, and tracing round | ||
260 | * the boundary. If the whole boundary is within the caller's bounding | ||
261 | * region, we return it; if it goes off the edge, we don't. | ||
262 | * | ||
263 | * (Of course, every hat we _do_ want to return will have all its | ||
264 | * kites inside the rectangle, so its kite #0 will certainly be caught | ||
265 | * by this iteration.) | ||
266 | */ | ||
267 | |||
268 | typedef void (*internal_hat_callback_fn)(void *ctx, Kite kite0, HatCoords *hc, | ||
269 | int *coords); | ||
270 | void maybe_report_hat(int w, int h, Kite kite, HatCoords *hc, | ||
271 | internal_hat_callback_fn cb, void *cbctx); | ||