tsiry-sandratraina.com
A modern Music Player Daemon based on Rockbox open source high quality audio player
libadwaita
audio
rust
zig
deno
mpris
rockbox
mpd
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
24typedef struct Point {
25 int x, y; /* represents x + yr */
26} Point;
27
28static inline Point pointscale(int scale, Point a)
29{
30 Point r = { scale * a.x, scale * a.y };
31 return r;
32}
33
34static 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
55typedef struct Kite {
56 Point centre, left, right, outer;
57} Kite;
58
59static 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
69static 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
79static 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
89static 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
99typedef enum KiteStep { KS_LEFT, KS_RIGHT, KS_F_LEFT, KS_F_RIGHT } KiteStep;
100
101static 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
117typedef 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;
129void hat_kiteenum_first(KiteEnum *s, int w, int h);
130bool hat_kiteenum_next(KiteEnum *s);
131
132/*
133 * Assorted useful definitions.
134 */
135typedef enum TileType { TT_H, TT_T, TT_P, TT_F, TT_KITE, TT_HAT } TileType;
136static 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 */
145typedef struct KitemapEntry {
146 int kite, hat, meta; /* all -1 if impossible */
147} KitemapEntry;
148
149typedef struct MetamapEntry {
150 int meta, meta2;
151} MetamapEntry;
152
153static 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
159static 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 */
182typedef 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
187typedef struct HatCoords {
188 HatCoord *c;
189 size_t nc, csize;
190} HatCoords;
191
192HatCoords *hat_coords_new(void);
193void hat_coords_free(HatCoords *hc);
194void hat_coords_make_space(HatCoords *hc, size_t size);
195HatCoords *hat_coords_copy(HatCoords *hc_in);
196
197#ifdef HAT_COORDS_DEBUG
198static 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
242typedef struct HatContext {
243 random_state *rs;
244 HatCoords *prototype;
245} HatContext;
246
247void hatctx_init_random(HatContext *ctx, random_state *rs);
248void hatctx_cleanup(HatContext *ctx);
249HatCoords *hatctx_initial_coords(HatContext *ctx);
250void hatctx_extend_coords(HatContext *ctx, HatCoords *hc, size_t n);
251HatCoords *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
268typedef void (*internal_hat_callback_fn)(void *ctx, Kite kite0, HatCoords *hc,
269 int *coords);
270void maybe_report_hat(int w, int h, Kite kite, HatCoords *hc,
271 internal_hat_callback_fn cb, void *cbctx);