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 * Code to generate patches of the aperiodic 'hat' tiling discovered
3 * in 2023.
4 *
5 * This uses the 'combinatorial coordinates' system documented in my
6 * public article
7 * https://www.chiark.greenend.org.uk/~sgtatham/quasiblog/aperiodic-tilings/
8 *
9 * The internal document auxiliary/doc/hats.html also contains an
10 * explanation of the basic ideas of this algorithm (less polished but
11 * containing more detail).
12 *
13 * Neither of those documents can really be put in a source file,
14 * because they just have too many complicated diagrams. So read at
15 * least one of those first; the comments in here will refer to it.
16 *
17 * Discoverers' website: https://cs.uwaterloo.ca/~csk/hat/
18 * Preprint of paper: https://arxiv.org/abs/2303.10798
19 */
20
21#include <assert.h>
22#ifdef NO_TGMATH_H
23# include <math.h>
24#else
25# include <tgmath.h>
26#endif
27#include <stdbool.h>
28#include <stdio.h>
29#include <stdlib.h>
30#include <string.h>
31
32#include "puzzles.h"
33#include "hat.h"
34#include "hat-internal.h"
35
36void hat_kiteenum_first(KiteEnum *s, int w, int h)
37{
38 Kite start = { {0,0}, {0, 3}, {3, 0}, {2, 2} };
39 size_t i;
40
41 for (i = 0; i < KE_NKEEP; i++)
42 s->recent[i] = start; /* initialise to *something* */
43 s->curr_index = 0;
44 s->curr = &s->recent[s->curr_index];
45 s->state = 1;
46 s->w = w;
47 s->h = h;
48 s->x = 0;
49 s->y = 0;
50}
51
52bool hat_kiteenum_next(KiteEnum *s)
53{
54 unsigned lastbut1 = s->last_index;
55 s->last_index = s->curr_index;
56 s->curr_index = (s->curr_index + 1) % KE_NKEEP;
57 s->curr = &s->recent[s->curr_index];
58
59 switch (s->state) {
60 /* States 1,2,3 walk rightwards along the upper side of a
61 * horizontal grid line with a pointy kite end at the start
62 * point */
63 case 1:
64 s->last_step = KS_F_RIGHT;
65 s->state = 2;
66 break;
67
68 case 2:
69 if (s->x+1 >= s->w) {
70 s->last_step = KS_F_RIGHT;
71 s->state = 4;
72 break;
73 }
74 s->last_step = KS_RIGHT;
75 s->state = 3;
76 s->x++;
77 break;
78
79 case 3:
80 s->last_step = KS_RIGHT;
81 s->state = 1;
82 break;
83
84 /* State 4 is special: we've just moved up into a row below a
85 * grid line, but we can't produce the rightmost tile of that
86 * row because it's not adjacent any tile so far emitted. So
87 * instead, emit the second-rightmost tile, and next time,
88 * we'll emit the rightmost. */
89 case 4:
90 s->last_step = KS_LEFT;
91 s->state = 5;
92 break;
93
94 /* And now we have to emit the third-rightmost tile relative
95 * to the last but one tile we emitted (the one from state 2,
96 * not state 4). */
97 case 5:
98 s->last_step = KS_RIGHT;
99 s->last_index = lastbut1;
100 s->state = 6;
101 break;
102
103 /* Now states 6-8 handle the general case of walking leftwards
104 * along the lower side of a line, starting from a
105 * right-angled kite end. */
106 case 6:
107 if (s->x <= 0) {
108 if (s->y+1 >= s->h) {
109 s->state = 0;
110 return false;
111 }
112 s->last_step = KS_RIGHT;
113 s->state = 9;
114 s->y++;
115 break;
116 }
117 s->last_step = KS_F_RIGHT;
118 s->state = 7;
119 s->x--;
120 break;
121
122 case 7:
123 s->last_step = KS_RIGHT;
124 s->state = 8;
125 break;
126
127 case 8:
128 s->last_step = KS_RIGHT;
129 s->state = 6;
130 break;
131
132 /* States 9,10,11 walk rightwards along the upper side of a
133 * horizontal grid line with a right-angled kite end at the
134 * start point. This time there's no awkward transition from
135 * the previous row. */
136 case 9:
137 s->last_step = KS_RIGHT;
138 s->state = 10;
139 break;
140
141 case 10:
142 s->last_step = KS_RIGHT;
143 s->state = 11;
144 break;
145
146 case 11:
147 if (s->x+1 >= s->w) {
148 /* Another awkward transition to the next row, where we
149 * have to generate it based on the previous state-9 tile.
150 * But this time at least we generate the rightmost tile
151 * of the new row, so the next states will be simple. */
152 s->last_step = KS_F_RIGHT;
153 s->last_index = lastbut1;
154 s->state = 12;
155 break;
156 }
157 s->last_step = KS_F_RIGHT;
158 s->state = 9;
159 s->x++;
160 break;
161
162 /* States 12,13,14 walk leftwards along the upper edge of a
163 * horizontal grid line with a pointy kite end at the start
164 * point */
165 case 12:
166 s->last_step = KS_F_RIGHT;
167 s->state = 13;
168 break;
169
170 case 13:
171 if (s->x <= 0) {
172 if (s->y+1 >= s->h) {
173 s->state = 0;
174 return false;
175 }
176 s->last_step = KS_LEFT;
177 s->state = 1;
178 s->y++;
179 break;
180 }
181 s->last_step = KS_RIGHT;
182 s->state = 14;
183 s->x--;
184 break;
185
186 case 14:
187 s->last_step = KS_RIGHT;
188 s->state = 12;
189 break;
190
191 default:
192 return false;
193 }
194
195 *s->curr = kite_step(s->recent[s->last_index], s->last_step);
196 return true;
197}
198
199/*
200 * The actual tables.
201 */
202#include "hat-tables.h"
203
204/*
205 * One set of tables that we write by hand: the permitted ways to
206 * extend the coordinate system outwards from a given metatile.
207 *
208 * One obvious approach would be to make a table of all the places
209 * each metatile can appear in the expansion of another (e.g. H can be
210 * subtile 0, 1 or 2 of another H, subtile 0 of a T, or 0 or 1 of a P
211 * or an F), and when we need to decide what our current topmost tile
212 * turns out to be a subtile of, choose equiprobably at random from
213 * those options.
214 *
215 * That's what I did originally, but a better approach is to skew the
216 * probabilities. We'd like to generate our patch of actual tiling
217 * uniformly at random, in the sense that if you selected uniformly
218 * from a very large region of the plane, the distribution of possible
219 * finite patches of tiling would converge to some limit as that
220 * region tended to infinity, and we'd be picking from that limiting
221 * distribution on finite patches.
222 *
223 * For this we have to refer back to the original paper, which
224 * indicates the subset of each metatile's expansion that can be
225 * considered to 'belong' to that metatile, such that every subtile
226 * belongs to exactly one parent metatile, and the overlaps are
227 * eliminated. Reading out the diagrams from their Figure 2.8:
228 *
229 * - H: we discard three of the outer F subtiles, in the symmetric
230 * positions index by our coordinates as 7, 10, 11. So we keep the
231 * remaining subtiles {0,1,2,3,4,5,6,8,9,12}, which consist of
232 * three H, one T, three P and three F.
233 *
234 * - T: only the central H expanded from a T is considered to belong
235 * to it, so we just keep {0}, a single H.
236 *
237 * - P: we discard everything intersected by a long edge of the
238 * parallelogram, leaving the central three tiles and the endmost
239 * pair of F. That is, we keep {0,1,4,5,10}, consisting of two H,
240 * one P and two F.
241 *
242 * - F: looks like P at one end, and we retain the corresponding set
243 * of tiles there, but at the other end we keep the two F on either
244 * side of the endmost one. So we keep {0,1,3,6,8,10}, consisting of
245 * two H, one P and _three_ F.
246 *
247 * Adding up the tile numbers gives us this matrix system:
248 *
249 * (H_1) (3 1 2 2)(H_0)
250 * (T_1) = (1 0 0 0)(T_0)
251 * (P_1) (3 0 1 1)(P_0)
252 * (F_1) (3 0 2 3)(F_0)
253 *
254 * which says that if you have a patch of metatiling consisting of H_0
255 * H tiles, T_0 T tiles etc, then this matrix shows the number H_1 of
256 * smaller H tiles, etc, expanded from it.
257 *
258 * If you expand _many_ times, that's equivalent to raising the matrix
259 * to a power:
260 *
261 * n
262 * (H_n) (3 1 2 2) (H_0)
263 * (T_n) = (1 0 0 0) (T_0)
264 * (P_n) (3 0 1 1) (P_0)
265 * (F_n) (3 0 2 3) (F_0)
266 *
267 * The limiting distribution of metatiles is obtained by looking at
268 * the four-way ratio between H_n, T_n, P_n and F_n as n tends to
269 * infinity. To calculate this, we find the eigenvalues and
270 * eigenvectors of the matrix, and extract the eigenvector
271 * corresponding to the eigenvalue of largest magnitude. (Things get
272 * more complicated in cases where there isn't a _unique_ eigenvalue
273 * of largest magnitude, but here, there is.)
274 *
275 * That eigenvector is
276 *
277 * [ 1 ] [ 1 ]
278 * [ (7 - 3 sqrt(5)) / 2 ] ~= [ 0.14589803375031545538 ]
279 * [ 3 sqrt(5) - 6 ] [ 0.70820393249936908922 ]
280 * [ (9 - 3 sqrt(5)) / 2 ] [ 1.14589803375031545538 ]
281 *
282 * So those are the limiting relative proportions of metatiles.
283 *
284 * So if we have a particular metatile, how likely is it for its
285 * parent to be one of those? We have to adjust by the number of
286 * metatiles of each type that each tile has as its children. For
287 * example, the P and F tiles have one P child each, but the H has
288 * three P children. So if we have a P, the proportion of H in its
289 * potential ancestry is three times what's shown here. (And T can't
290 * occur at all as a parent.)
291 *
292 * In other words, we should choose _each coordinate_ with probability
293 * corresponding to one of those numbers (scaled down so they all sum
294 * to 1). Continuing to use P as an example, it will be:
295 *
296 * - child 4 of H with relative probability 1
297 * - child 5 of H with relative probability 1
298 * - child 6 of H with relative probability 1
299 * - child 4 of P with relative probability 0.70820393249936908922
300 * - child 3 of F with relative probability 1.14589803375031545538
301 *
302 * and then we obtain the true probabilities by scaling those values
303 * down so that they sum to 1.
304 *
305 * The tables below give a reasonable approximation in 32-bit
306 * integers to these proportions.
307 */
308
309typedef struct MetatilePossibleParent {
310 TileType type;
311 unsigned index;
312 unsigned long probability;
313} MetatilePossibleParent;
314
315/* The above probabilities scaled up by 10000000 */
316#define PROB_H 10000000
317#define PROB_T 1458980
318#define PROB_P 7082039
319#define PROB_F 11458980
320
321static const MetatilePossibleParent parents_H[] = {
322 { TT_H, 0, PROB_H },
323 { TT_H, 1, PROB_H },
324 { TT_H, 2, PROB_H },
325 { TT_T, 0, PROB_T },
326 { TT_P, 0, PROB_P },
327 { TT_P, 1, PROB_P },
328 { TT_F, 0, PROB_F },
329 { TT_F, 1, PROB_F },
330};
331static const MetatilePossibleParent parents_T[] = {
332 { TT_H, 3, PROB_H },
333};
334static const MetatilePossibleParent parents_P[] = {
335 { TT_H, 4, PROB_H },
336 { TT_H, 5, PROB_H },
337 { TT_H, 6, PROB_H },
338 { TT_P, 4, PROB_P },
339 { TT_F, 3, PROB_F },
340};
341static const MetatilePossibleParent parents_F[] = {
342 { TT_H, 8, PROB_H },
343 { TT_H, 9, PROB_H },
344 { TT_H, 12, PROB_H },
345 { TT_P, 5, PROB_P },
346 { TT_P, 10, PROB_P },
347 { TT_F, 6, PROB_F },
348 { TT_F, 8, PROB_F },
349 { TT_F, 10, PROB_F },
350};
351
352static const MetatilePossibleParent *const possible_parents[] = {
353 parents_H, parents_T, parents_P, parents_F,
354};
355static const size_t n_possible_parents[] = {
356 lenof(parents_H), lenof(parents_T), lenof(parents_P), lenof(parents_F),
357};
358
359/*
360 * Similarly, we also want to choose our absolute starting hat with
361 * close to uniform probability, which again we do by looking at the
362 * limiting ratio of the metatile types, and this time, scaling by the
363 * number of hats in each metatile.
364 *
365 * We cheatingly use the same MetatilePossibleParent struct, because
366 * it's got all the right fields, even if it has an inappropriate
367 * name.
368 */
369static const MetatilePossibleParent starting_hats[] = {
370 { TT_H, 0, PROB_H },
371 { TT_H, 1, PROB_H },
372 { TT_H, 2, PROB_H },
373 { TT_H, 3, PROB_H },
374 { TT_T, 0, PROB_P },
375 { TT_P, 0, PROB_P },
376 { TT_P, 1, PROB_P },
377 { TT_F, 0, PROB_F },
378 { TT_F, 1, PROB_F },
379};
380
381#undef PROB_H
382#undef PROB_T
383#undef PROB_P
384#undef PROB_F
385
386HatCoords *hat_coords_new(void)
387{
388 HatCoords *hc = snew(HatCoords);
389 hc->nc = hc->csize = 0;
390 hc->c = NULL;
391 return hc;
392}
393
394void hat_coords_free(HatCoords *hc)
395{
396 if (hc) {
397 sfree(hc->c);
398 sfree(hc);
399 }
400}
401
402void hat_coords_make_space(HatCoords *hc, size_t size)
403{
404 if (hc->csize < size) {
405 hc->csize = hc->csize * 5 / 4 + 16;
406 if (hc->csize < size)
407 hc->csize = size;
408 hc->c = sresize(hc->c, hc->csize, HatCoord);
409 }
410}
411
412HatCoords *hat_coords_copy(HatCoords *hc_in)
413{
414 HatCoords *hc_out = hat_coords_new();
415 hat_coords_make_space(hc_out, hc_in->nc);
416 memcpy(hc_out->c, hc_in->c, hc_in->nc * sizeof(*hc_out->c));
417 hc_out->nc = hc_in->nc;
418 return hc_out;
419}
420
421static const MetatilePossibleParent *choose_mpp(
422 random_state *rs, const MetatilePossibleParent *parents, size_t nparents)
423{
424 /*
425 * If we needed to do this _efficiently_, we'd rewrite all those
426 * tables above as cumulative frequency tables and use binary
427 * search. But this happens about log n times in a grid of area n,
428 * so it hardly matters, and it's easier to keep the tables
429 * legible.
430 */
431 unsigned long limit = 0, value;
432 size_t i;
433
434 for (i = 0; i < nparents; i++)
435 limit += parents[i].probability;
436
437 value = random_upto(rs, limit);
438
439 for (i = 0; i+1 < nparents; i++) {
440 if (value < parents[i].probability)
441 return &parents[i];
442 value -= parents[i].probability;
443 }
444
445 assert(i == nparents - 1);
446 assert(value < parents[i].probability);
447 return &parents[i];
448}
449void hatctx_init_random(HatContext *ctx, random_state *rs)
450{
451 const MetatilePossibleParent *starting_hat = choose_mpp(
452 rs, starting_hats, lenof(starting_hats));
453
454 ctx->rs = rs;
455 ctx->prototype = hat_coords_new();
456 hat_coords_make_space(ctx->prototype, 3);
457 ctx->prototype->c[2].type = starting_hat->type;
458 ctx->prototype->c[2].index = -1;
459 ctx->prototype->c[1].type = TT_HAT;
460 ctx->prototype->c[1].index = starting_hat->index;
461 ctx->prototype->c[0].type = TT_KITE;
462 ctx->prototype->c[0].index = random_upto(rs, HAT_KITES);
463 ctx->prototype->nc = 3;
464}
465
466static inline int metatile_char_to_enum(char metatile)
467{
468 return (metatile == 'H' ? TT_H :
469 metatile == 'T' ? TT_T :
470 metatile == 'P' ? TT_P :
471 metatile == 'F' ? TT_F : -1);
472}
473
474static void init_coords_params(HatContext *ctx,
475 const struct HatPatchParams *hp)
476{
477 size_t i;
478
479 ctx->rs = NULL;
480 ctx->prototype = hat_coords_new();
481
482 assert(hp->ncoords >= 3);
483
484 hat_coords_make_space(ctx->prototype, hp->ncoords + 1);
485 ctx->prototype->nc = hp->ncoords + 1;
486
487 for (i = 0; i < hp->ncoords; i++)
488 ctx->prototype->c[i].index = hp->coords[i];
489
490 ctx->prototype->c[hp->ncoords].type =
491 metatile_char_to_enum(hp->final_metatile);
492 ctx->prototype->c[hp->ncoords].index = -1;
493
494 ctx->prototype->c[0].type = TT_KITE;
495 ctx->prototype->c[1].type = TT_HAT;
496
497 for (i = hp->ncoords - 1; i > 1; i--) {
498 TileType metatile = ctx->prototype->c[i+1].type;
499 assert(hp->coords[i] < nchildren[metatile]);
500 ctx->prototype->c[i].type = children[metatile][hp->coords[i]];
501 }
502
503 assert(hp->coords[0] < 8);
504}
505
506HatCoords *hatctx_initial_coords(HatContext *ctx)
507{
508 return hat_coords_copy(ctx->prototype);
509}
510
511/*
512 * Extend hc until it has at least n coordinates in, by copying from
513 * ctx->prototype if needed, and extending ctx->prototype if needed in
514 * order to do that.
515 */
516void hatctx_extend_coords(HatContext *ctx, HatCoords *hc, size_t n)
517{
518 if (ctx->prototype->nc < n) {
519 hat_coords_make_space(ctx->prototype, n);
520 while (ctx->prototype->nc < n) {
521 TileType type = ctx->prototype->c[ctx->prototype->nc - 1].type;
522 assert(ctx->prototype->c[ctx->prototype->nc - 1].index == -1);
523 const MetatilePossibleParent *parent;
524
525 if (ctx->rs)
526 parent = choose_mpp(ctx->rs, possible_parents[type],
527 n_possible_parents[type]);
528 else
529 parent = possible_parents[type];
530
531 ctx->prototype->c[ctx->prototype->nc - 1].index = parent->index;
532 ctx->prototype->c[ctx->prototype->nc].index = -1;
533 ctx->prototype->c[ctx->prototype->nc].type = parent->type;
534 ctx->prototype->nc++;
535 }
536 }
537
538 hat_coords_make_space(hc, n);
539 while (hc->nc < n) {
540 assert(hc->c[hc->nc - 1].index == -1);
541 assert(hc->c[hc->nc - 1].type == ctx->prototype->c[hc->nc - 1].type);
542 hc->c[hc->nc - 1].index = ctx->prototype->c[hc->nc - 1].index;
543 hc->c[hc->nc].index = -1;
544 hc->c[hc->nc].type = ctx->prototype->c[hc->nc].type;
545 hc->nc++;
546 }
547}
548
549void hatctx_cleanup(HatContext *ctx)
550{
551 hat_coords_free(ctx->prototype);
552}
553
554/*
555 * The actual system for finding the coordinates of an adjacent kite.
556 */
557
558/*
559 * Kitemap step: ensure we have enough coordinates to know two levels
560 * of meta-tiling, and use the kite map for the outer layer to move
561 * around the individual kites. If this fails, return NULL.
562 */
563static HatCoords *try_step_coords_kitemap(
564 HatContext *ctx, HatCoords *hc_in, KiteStep step)
565{
566 hatctx_extend_coords(ctx, hc_in, 4);
567 hat_coords_debug(" try kitemap ", hc_in, "\n");
568 unsigned kite = hc_in->c[0].index;
569 unsigned hat = hc_in->c[1].index;
570 unsigned meta = hc_in->c[2].index;
571 TileType meta2type = hc_in->c[3].type;
572 const KitemapEntry *ke = &kitemap[meta2type][
573 kitemap_index(step, kite, hat, meta)];
574 if (ke->kite >= 0) {
575 /*
576 * Success! We've got coordinates for the next kite in this
577 * direction.
578 */
579 HatCoords *hc_out = hat_coords_copy(hc_in);
580
581 hc_out->c[2].index = ke->meta;
582 hc_out->c[2].type = children[meta2type][ke->meta];
583 hc_out->c[1].index = ke->hat;
584 hc_out->c[1].type = TT_HAT;
585 hc_out->c[0].index = ke->kite;
586 hc_out->c[0].type = TT_KITE;
587
588 hat_coords_debug(" success! ", hc_out, "\n");
589 return hc_out;
590 }
591
592 return NULL;
593}
594
595/*
596 * Recursive metamap step. Try using the metamap to rewrite the
597 * coordinates at hc->c[depth] and hc->c[depth+1] (using the metamap
598 * for the tile type described in hc->c[depth+2]). If successful,
599 * recurse back down to see if this led to a successful step via the
600 * kitemap. If even that fails (so that we need to try a higher-order
601 * metamap rewrite), return NULL.
602 */
603static HatCoords *try_step_coords_metamap(
604 HatContext *ctx, HatCoords *hc_in, KiteStep step, size_t depth)
605{
606 HatCoords *hc_tmp = NULL, *hc_out;
607
608 hatctx_extend_coords(ctx, hc_in, depth+3);
609#ifdef HAT_COORDS_DEBUG
610 fprintf(stderr, " try meta %-4d", (int)depth);
611 hat_coords_debug("", hc_in, "\n");
612#endif
613 unsigned meta_orig = hc_in->c[depth].index;
614 unsigned meta2_orig = hc_in->c[depth+1].index;
615 TileType meta3type = hc_in->c[depth+2].type;
616
617 unsigned meta = meta_orig, meta2 = meta2_orig;
618
619 while (true) {
620 const MetamapEntry *me;
621 HatCoords *hc_curr = hc_tmp ? hc_tmp : hc_in;
622
623 if (depth > 2)
624 hc_out = try_step_coords_metamap(ctx, hc_curr, step, depth - 1);
625 else
626 hc_out = try_step_coords_kitemap(ctx, hc_curr, step);
627 if (hc_out) {
628 hat_coords_free(hc_tmp);
629 return hc_out;
630 }
631
632 me = &metamap[meta3type][metamap_index(meta, meta2)];
633 assert(me->meta != -1);
634 if (me->meta == meta_orig && me->meta2 == meta2_orig) {
635 hat_coords_free(hc_tmp);
636 return NULL;
637 }
638
639 meta = me->meta;
640 meta2 = me->meta2;
641
642 /*
643 * We must do the rewrite in a copy of hc_in. It's not
644 * _necessarily_ obvious that that's the case (any successful
645 * rewrite leaves the coordinates still valid and still
646 * referring to the same kite, right?). But the problem is
647 * that we might do a rewrite at this level more than once,
648 * and in between, a metamap rewrite at the next level down
649 * might have modified _one_ of the two coordinates we're
650 * messing about with. So it's easiest to let the recursion
651 * just use a separate copy.
652 */
653 if (!hc_tmp)
654 hc_tmp = hat_coords_copy(hc_in);
655
656 hc_tmp->c[depth+1].index = meta2;
657 hc_tmp->c[depth+1].type = children[meta3type][meta2];
658 hc_tmp->c[depth].index = meta;
659 hc_tmp->c[depth].type = children[hc_tmp->c[depth+1].type][meta];
660
661 hat_coords_debug(" rewritten -> ", hc_tmp, "\n");
662 }
663}
664
665/*
666 * The top-level algorithm for finding the next tile.
667 */
668HatCoords *hatctx_step(HatContext *ctx, HatCoords *hc_in, KiteStep step)
669{
670 HatCoords *hc_out;
671 size_t depth;
672
673#ifdef HAT_COORDS_DEBUG
674 static const char *const directions[] = {
675 " left\n", " right\n", " forward left\n", " forward right\n" };
676 hat_coords_debug("step start ", hc_in, directions[step]);
677#endif
678
679 /*
680 * First, just try a kitemap step immediately. If that succeeds,
681 * we're done.
682 */
683 if ((hc_out = try_step_coords_kitemap(ctx, hc_in, step)) != NULL)
684 return hc_out;
685
686 /*
687 * Otherwise, try metamap rewrites at successively higher layers
688 * until one works. Each one will recurse back down to the
689 * kitemap, as described above.
690 */
691 for (depth = 2;; depth++) {
692 if ((hc_out = try_step_coords_metamap(
693 ctx, hc_in, step, depth)) != NULL)
694 return hc_out;
695 }
696}
697
698/*
699 * Generate a random set of parameters for a tiling of a given size.
700 * To do this, we iterate over the whole tiling via hat_kiteenum_first
701 * and hat_kiteenum_next, and for each kite, calculate its
702 * coordinates. But then we throw the coordinates away and don't do
703 * anything with them!
704 *
705 * But the side effect of _calculating_ all those coordinates is that
706 * we found out how far ctx->prototype needed to be extended, and did
707 * so, pulling random choices out of our random_state. So after this
708 * iteration, ctx->prototype contains everything we need to replicate
709 * the same piece of tiling next time.
710 */
711void hat_tiling_randomise(struct HatPatchParams *hp, int w, int h,
712 random_state *rs)
713{
714 HatContext ctx[1];
715 HatCoords *coords[KE_NKEEP];
716 KiteEnum s[1];
717 size_t i;
718
719 hatctx_init_random(ctx, rs);
720 for (i = 0; i < lenof(coords); i++)
721 coords[i] = NULL;
722
723 hat_kiteenum_first(s, w, h);
724 coords[s->curr_index] = hatctx_initial_coords(ctx);
725
726 while (hat_kiteenum_next(s)) {
727 hat_coords_free(coords[s->curr_index]);
728 coords[s->curr_index] = hatctx_step(
729 ctx, coords[s->last_index], s->last_step);
730 }
731
732 hp->ncoords = ctx->prototype->nc - 1;
733 hp->coords = snewn(hp->ncoords, unsigned char);
734 for (i = 0; i < hp->ncoords; i++)
735 hp->coords[i] = ctx->prototype->c[i].index;
736 hp->final_metatile = tilechars[ctx->prototype->c[hp->ncoords].type];
737
738 hatctx_cleanup(ctx);
739 for (i = 0; i < lenof(coords); i++)
740 hat_coords_free(coords[i]);
741}
742
743const char *hat_tiling_params_invalid(const struct HatPatchParams *hp)
744{
745 TileType metatile;
746 size_t i;
747
748 if (hp->ncoords < 3)
749 return "Grid parameters require at least three coordinates";
750 if (metatile_char_to_enum(hp->final_metatile) < 0)
751 return "Grid parameters contain an invalid final metatile";
752 if (hp->coords[0] >= 8)
753 return "Grid parameters contain an invalid kite index";
754
755 metatile = metatile_char_to_enum(hp->final_metatile);
756 for (i = hp->ncoords - 1; i > 1; i--) {
757 if (hp->coords[i] >= nchildren[metatile])
758 return "Grid parameters contain an invalid metatile index";
759 metatile = children[metatile][hp->coords[i]];
760 }
761
762 if (hp->coords[1] >= hats_in_metatile[metatile])
763 return "Grid parameters contain an invalid hat index";
764
765 return NULL;
766}
767
768void maybe_report_hat(int w, int h, Kite kite, HatCoords *hc,
769 internal_hat_callback_fn cb, void *cbctx)
770{
771 Kite kite0;
772 Point vertices[14];
773 size_t i, j;
774 bool reversed = false;
775 int coords[28];
776
777 /* Only iterate from kite #0 of a hat */
778 if (hc->c[0].index != 0)
779 return;
780 kite0 = kite;
781
782 /*
783 * Identify reflected hats: they are always hat #3 of an H
784 * metatile. If we find one, reflect the starting kite so that the
785 * kite_step operations below will go in the other direction.
786 */
787 if (hc->c[2].type == TT_H && hc->c[1].index == 3) {
788 reversed = true;
789 Point tmp = kite.left;
790 kite.left = kite.right;
791 kite.right = tmp;
792 }
793
794 vertices[0] = kite.centre;
795 vertices[1] = kite.right;
796 vertices[2] = kite.outer;
797 vertices[3] = kite.left;
798 kite = kite_left(kite); /* now on kite #1 */
799 kite = kite_forward_right(kite); /* now on kite #2 */
800 vertices[4] = kite.centre;
801 kite = kite_right(kite); /* now on kite #3 */
802 vertices[5] = kite.right;
803 vertices[6] = kite.outer;
804 kite = kite_forward_left(kite); /* now on kite #4 */
805 vertices[7] = kite.left;
806 vertices[8] = kite.centre;
807 kite = kite_right(kite); /* now on kite #5 */
808 kite = kite_right(kite); /* now on kite #6 */
809 kite = kite_right(kite); /* now on kite #7 */
810 vertices[9] = kite.right;
811 vertices[10] = kite.outer;
812 vertices[11] = kite.left;
813 kite = kite_left(kite); /* now on kite #6 again */
814 vertices[12] = kite.outer;
815 vertices[13] = kite.left;
816
817 if (reversed) {
818 /* For a reversed kite, also reverse the vertex order, so that
819 * we report every polygon in a consistent orientation */
820 for (i = 0, j = 13; i < j; i++, j--) {
821 Point tmp = vertices[i];
822 vertices[i] = vertices[j];
823 vertices[j] = tmp;
824 }
825 }
826
827 /*
828 * Convert from our internal coordinate system into the orthogonal
829 * one used in this module's external API. In the same loop, we
830 * might as well do the bounds check.
831 */
832 for (i = 0; i < 14; i++) {
833 Point v = vertices[i];
834 int x = (v.x * 2 + v.y) / 3, y = v.y;
835
836 if (x < 0 || x > 4*w || y < 0 || y > 6*h)
837 return; /* a vertex of this kite is out of bounds */
838
839 coords[2*i] = x;
840 coords[2*i+1] = y;
841 }
842
843 cb(cbctx, kite0, hc, coords);
844}
845
846struct internal_ctx {
847 hat_tile_callback_fn external_cb;
848 void *external_cbctx;
849};
850static void report_hat(void *vctx, Kite kite0, HatCoords *hc, int *coords)
851{
852 struct internal_ctx *ctx = (struct internal_ctx *)vctx;
853 ctx->external_cb(ctx->external_cbctx, 14, coords);
854}
855
856/*
857 * Generate a hat tiling from a previously generated set of parameters.
858 */
859void hat_tiling_generate(const struct HatPatchParams *hp, int w, int h,
860 hat_tile_callback_fn cb, void *cbctx)
861{
862 HatContext ctx[1];
863 HatCoords *coords[KE_NKEEP];
864 KiteEnum s[1];
865 size_t i;
866 struct internal_ctx report_hat_ctx[1];
867
868 report_hat_ctx->external_cb = cb;
869 report_hat_ctx->external_cbctx = cbctx;
870
871 init_coords_params(ctx, hp);
872 for (i = 0; i < lenof(coords); i++)
873 coords[i] = NULL;
874
875 hat_kiteenum_first(s, w, h);
876 coords[s->curr_index] = hatctx_initial_coords(ctx);
877 maybe_report_hat(w, h, *s->curr, coords[s->curr_index],
878 report_hat, report_hat_ctx);
879
880 while (hat_kiteenum_next(s)) {
881 hat_coords_free(coords[s->curr_index]);
882 coords[s->curr_index] = hatctx_step(
883 ctx, coords[s->last_index], s->last_step);
884 maybe_report_hat(w, h, *s->curr, coords[s->curr_index],
885 report_hat, report_hat_ctx);
886 }
887
888 hatctx_cleanup(ctx);
889 for (i = 0; i < lenof(coords); i++)
890 hat_coords_free(coords[i]);
891}