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 'spectre' tiling
3 * discovered in 2023.
4 *
5 * Resources about the tiling from its discoverers:
6 * https://cs.uwaterloo.ca/~csk/spectre/
7 * https://arxiv.org/abs/2305.17743
8 *
9 * Writeup of the generation algorithm:
10 * https://www.chiark.greenend.org.uk/~sgtatham/quasiblog/aperiodic-spectre/
11 */
12
13#include <assert.h>
14#include <string.h>
15
16#include "puzzles.h"
17#include "tree234.h"
18
19#include "spectre-internal.h"
20
21#include "spectre-tables-manual.h"
22#include "spectre-tables-auto.h"
23
24static const char *const letters =
25 #define STRINGIFY(x) #x
26 HEX_LETTERS(STRINGIFY)
27 #undef STRINGIFY
28 ;
29
30bool spectre_valid_hex_letter(char letter)
31{
32 return strchr(letters, letter) != NULL;
33}
34
35static Hex hex_from_letter(char letter)
36{
37 char buf[2];
38 buf[0] = letter;
39 buf[1] = '\0';
40 return strcspn(letters, buf);
41}
42
43static Hex hex_to_letter(unsigned char letter)
44{
45 return letters[letter];
46}
47
48struct HexData {
49 const struct MapEntry *hexmap, *hexin, *specmap, *specin;
50 const struct MapEdge *hexedges, *specedges;
51 const Hex *subhexes;
52 const struct Possibility *poss;
53 size_t nposs;
54};
55
56static const struct HexData hexdata[] = {
57 #define HEXDATA_ENTRY(x) { hexmap_##x, hexin_##x, specmap_##x, \
58 specin_##x, hexedges_##x, specedges_##x, subhexes_##x, \
59 poss_##x, lenof(poss_##x) },
60 HEX_LETTERS(HEXDATA_ENTRY)
61 #undef HEXDATA_ENTRY
62};
63
64static const struct Possibility *choose_poss(
65 random_state *rs, const struct Possibility *poss, size_t nposs)
66{
67 /*
68 * If we needed to do this _efficiently_, we'd rewrite all those
69 * tables above as cumulative frequency tables and use binary
70 * search. But this happens about log n times in a grid of area n,
71 * so it hardly matters, and it's easier to keep the tables
72 * legible.
73 */
74 unsigned long limit = 0, value;
75 size_t i;
76
77 for (i = 0; i < nposs; i++)
78 limit += poss[i].prob;
79
80 value = random_upto(rs, limit);
81
82 for (i = 0; i+1 < nposs; i++) {
83 if (value < poss[i].prob)
84 return &poss[i];
85 value -= poss[i].prob;
86 }
87
88 assert(i == nposs - 1);
89 assert(value < poss[i].prob);
90 return &poss[i];
91}
92
93SpectreCoords *spectre_coords_new(void)
94{
95 SpectreCoords *sc = snew(SpectreCoords);
96 sc->nc = sc->csize = 0;
97 sc->c = NULL;
98 return sc;
99}
100
101void spectre_coords_free(SpectreCoords *sc)
102{
103 if (sc) {
104 sfree(sc->c);
105 sfree(sc);
106 }
107}
108
109void spectre_coords_make_space(SpectreCoords *sc, size_t size)
110{
111 if (sc->csize < size) {
112 sc->csize = sc->csize * 5 / 4 + 16;
113 if (sc->csize < size)
114 sc->csize = size;
115 sc->c = sresize(sc->c, sc->csize, HexCoord);
116 }
117}
118
119SpectreCoords *spectre_coords_copy(SpectreCoords *sc_in)
120{
121 SpectreCoords *sc_out = spectre_coords_new();
122 spectre_coords_make_space(sc_out, sc_in->nc);
123 memcpy(sc_out->c, sc_in->c, sc_in->nc * sizeof(*sc_out->c));
124 sc_out->nc = sc_in->nc;
125 sc_out->index = sc_in->index;
126 sc_out->hex_colour = sc_in->hex_colour;
127 sc_out->prev_hex_colour = sc_in->prev_hex_colour;
128 sc_out->incoming_hex_edge = sc_in->incoming_hex_edge;
129 return sc_out;
130}
131
132void spectre_place(Spectre *spec, Point u, Point v, int index_of_u)
133{
134 size_t i;
135 Point disp;
136
137 /* Vector from u to v */
138 disp = point_sub(v, u);
139
140 for (i = 0; i < 14; i++) {
141 spec->vertices[(i + index_of_u) % 14] = u;
142 u = point_add(u, disp);
143 disp = point_mul(disp, point_rot(
144 spectre_angles[(i + 1 + index_of_u) % 14]));
145 }
146}
147
148Spectre *spectre_initial(SpectreContext *ctx)
149{
150 Spectre *spec = snew(Spectre);
151 spectre_place(spec, ctx->start_vertices[0], ctx->start_vertices[1], 0);
152 spec->sc = spectre_coords_copy(ctx->prototype);
153 return spec;
154}
155
156Spectre *spectre_adjacent(SpectreContext *ctx, const Spectre *src_spec,
157 unsigned src_edge, unsigned *dst_edge_out)
158{
159 unsigned dst_edge;
160 Spectre *dst_spec = snew(Spectre);
161 dst_spec->sc = spectre_coords_copy(src_spec->sc);
162 spectrectx_step(ctx, dst_spec->sc, src_edge, &dst_edge);
163 spectre_place(dst_spec, src_spec->vertices[(src_edge+1) % 14],
164 src_spec->vertices[src_edge], dst_edge);
165 if (dst_edge_out)
166 *dst_edge_out = dst_edge;
167 return dst_spec;
168}
169
170static int spectre_cmp(void *av, void *bv)
171{
172 Spectre *a = (Spectre *)av, *b = (Spectre *)bv;
173 size_t i, j;
174
175 /* We should only ever need to compare the first two vertices of
176 * any Spectre, because those force the rest */
177 for (i = 0; i < 2; i++) {
178 for (j = 0; j < 4; j++) {
179 int ac = a->vertices[i].coeffs[j], bc = b->vertices[i].coeffs[j];
180 if (ac < bc)
181 return -1;
182 if (ac > bc)
183 return +1;
184 }
185 }
186
187 return 0;
188}
189
190void spectre_free(Spectre *spec)
191{
192 spectre_coords_free(spec->sc);
193 sfree(spec);
194}
195
196static void spectrectx_start_vertices(SpectreContext *ctx, int orientation)
197{
198 Point minus_sqrt3 = point_add(point_rot(5), point_rot(-5));
199 Point basicedge = point_mul(point_add(point_rot(0), point_rot(-3)),
200 point_rot(orientation));
201 Point diagonal = point_add(basicedge, point_mul(basicedge, point_rot(-3)));
202 ctx->start_vertices[0] = point_mul(diagonal, minus_sqrt3);
203 ctx->start_vertices[1] = point_add(ctx->start_vertices[0], basicedge);
204 ctx->orientation = orientation;
205}
206
207void spectrectx_init_random(SpectreContext *ctx, random_state *rs)
208{
209 const struct Possibility *poss;
210
211 ctx->rs = rs;
212 ctx->must_free_rs = false;
213 ctx->prototype = spectre_coords_new();
214 spectre_coords_make_space(ctx->prototype, 1);
215 poss = choose_poss(rs, poss_spectre, lenof(poss_spectre));
216 ctx->prototype->index = poss->lo;
217 ctx->prototype->c[0].type = poss->hi;
218 ctx->prototype->c[0].index = -1;
219 ctx->prototype->nc = 1;
220
221 /*
222 * Choose a random orientation for the starting Spectre.
223 *
224 * The obvious thing is to choose the orientation out of all 12
225 * possibilities. But we do it a more complicated way.
226 *
227 * The Spectres in a tiling can be partitioned into two
228 * equivalence classes under the relation 'orientation differs by
229 * a multiple of 1/6 turn'. One class is much more common than the
230 * other class: the 'odd'-orientation Spectres occur rarely (very
231 * like the rare reflected hats in the hats tiling).
232 *
233 * I think it's nicer to arrange that there's a consistent
234 * orientation for the _common_ class of Spectres, so that there
235 * will always be plenty of them in the 'canonical' orientation
236 * with the head upwards. So if the starting Spectre is in the
237 * even class, we pick an even orientation for it, and if it's in
238 * the odd class, we pick an odd orientation.
239 *
240 * An odd-class Spectre is easy to identify from SpectreCoords.
241 * They're precisely the ones expanded from a G hex with index 1,
242 * which means they're the ones that have index 1 _at all_.
243 */
244 spectrectx_start_vertices(ctx, random_upto(rs, 6) * 2 +
245 ctx->prototype->index);
246
247 /* Initialiise the colouring fields deterministically but unhelpfully.
248 * spectre-test will set these up properly if it wants to */
249 ctx->prototype->hex_colour = 0;
250 ctx->prototype->prev_hex_colour = 0;
251 ctx->prototype->incoming_hex_edge = 0;
252}
253
254void spectrectx_init_from_params(
255 SpectreContext *ctx, const struct SpectrePatchParams *ps)
256{
257 size_t i;
258
259 ctx->rs = NULL;
260 ctx->must_free_rs = false;
261 ctx->prototype = spectre_coords_new();
262 spectre_coords_make_space(ctx->prototype, ps->ncoords);
263
264 ctx->prototype->index = ps->coords[0];
265 for (i = 1; i < ps->ncoords; i++)
266 ctx->prototype->c[i-1].index = ps->coords[i];
267 ctx->prototype->c[ps->ncoords-1].index = -1;
268 ctx->prototype->nc = ps->ncoords;
269
270 ctx->prototype->c[ps->ncoords-1].type = hex_from_letter(ps->final_hex);
271 for (i = ps->ncoords - 1; i-- > 0 ;) {
272 const struct HexData *h = &hexdata[ctx->prototype->c[i+1].type];
273 ctx->prototype->c[i].type = h->subhexes[ctx->prototype->c[i].index];
274 }
275
276 spectrectx_start_vertices(ctx, ps->orientation);
277
278 ctx->prototype->hex_colour = 0;
279 ctx->prototype->prev_hex_colour = 0;
280 ctx->prototype->incoming_hex_edge = 0;
281}
282
283void spectrectx_cleanup(SpectreContext *ctx)
284{
285 if (ctx->must_free_rs)
286 random_free(ctx->rs);
287 spectre_coords_free(ctx->prototype);
288}
289
290SpectreCoords *spectrectx_initial_coords(SpectreContext *ctx)
291{
292 return spectre_coords_copy(ctx->prototype);
293}
294
295/*
296 * Extend sc until it has at least n coordinates in, by copying from
297 * ctx->prototype if needed, and extending ctx->prototype if needed in
298 * order to do that.
299 */
300void spectrectx_extend_coords(SpectreContext *ctx, SpectreCoords *sc, size_t n)
301{
302 if (ctx->prototype->nc < n) {
303 spectre_coords_make_space(ctx->prototype, n);
304 while (ctx->prototype->nc < n) {
305 const struct HexData *h = &hexdata[
306 ctx->prototype->c[ctx->prototype->nc-1].type];
307 const struct Possibility *poss;
308
309 if (!ctx->rs) {
310 /*
311 * If there's no random_state available, it must be
312 * because we were given an explicit coordinate string
313 * and ran off the end of it.
314 *
315 * The obvious thing to do here would be to make up an
316 * answer non-randomly. But in fact there's a danger
317 * that this leads to endless recursion within a
318 * single coordinate step, if the hex edge we were
319 * trying to traverse turns into another copy of
320 * itself at the higher level. That happened in early
321 * testing before I put the random_state in at all.
322 *
323 * To avoid that risk, in this situation - which
324 * _shouldn't_ come up at all in sensibly play - we
325 * make up a random_state, and free it when the
326 * context goes away.
327 */
328 ctx->rs = random_new("dummy", 5);
329 ctx->must_free_rs = true;
330 }
331
332 poss = choose_poss(ctx->rs, h->poss, h->nposs);
333 ctx->prototype->c[ctx->prototype->nc-1].index = poss->lo;
334 ctx->prototype->c[ctx->prototype->nc].type = poss->hi;
335 ctx->prototype->c[ctx->prototype->nc].index = -1;
336 ctx->prototype->nc++;
337 }
338 }
339
340 spectre_coords_make_space(sc, n);
341 while (sc->nc < n) {
342 assert(sc->c[sc->nc - 1].index == -1);
343 assert(sc->c[sc->nc - 1].type == ctx->prototype->c[sc->nc - 1].type);
344 sc->c[sc->nc - 1].index = ctx->prototype->c[sc->nc - 1].index;
345 sc->c[sc->nc].index = -1;
346 sc->c[sc->nc].type = ctx->prototype->c[sc->nc].type;
347 sc->nc++;
348 }
349}
350
351void spectrectx_step_hex(SpectreContext *ctx, SpectreCoords *sc,
352 size_t depth, unsigned edge, unsigned *outedge)
353{
354 const struct HexData *h;
355 const struct MapEntry *m;
356
357 spectrectx_extend_coords(ctx, sc, depth+2);
358
359 assert(0 <= sc->c[depth].index);
360 assert(sc->c[depth].index < num_subhexes(sc->c[depth].type));
361 assert(0 <= edge);
362 assert(edge < 6);
363
364 h = &hexdata[sc->c[depth+1].type];
365 m = &h->hexmap[6 * sc->c[depth].index + edge];
366 if (!m->internal) {
367 unsigned recedge;
368 const struct MapEdge *me;
369 spectrectx_step_hex(ctx, sc, depth+1, m->hi, &recedge);
370 assert(recedge < 6);
371 h = &hexdata[sc->c[depth+1].type];
372 me = &h->hexedges[recedge];
373 assert(m->lo < me->len);
374 m = &h->hexin[me->startindex + me->len - 1 - m->lo];
375 assert(m->internal);
376 }
377 sc->c[depth].index = m->hi;
378 sc->c[depth].type = h->subhexes[sc->c[depth].index];
379 *outedge = m->lo;
380
381 if (depth == 0) {
382 /*
383 * Update the colouring fields to track the colour of the new
384 * hexagon.
385 */
386 unsigned char new_hex_colour;
387
388 if (!((edge ^ sc->incoming_hex_edge) & 1)) {
389 /* We're going out via the same parity of edge we came in
390 * on, so the new hex colour is the same as the previous
391 * one. */
392 new_hex_colour = sc->prev_hex_colour;
393 } else {
394 /* We're going out via the opposite parity of edge, so the
395 * new colour is the one of {0,1,2} that is neither this
396 * _nor_ the previous colour. */
397 new_hex_colour = 0+1+2 - sc->hex_colour - sc->prev_hex_colour;
398 }
399
400 sc->prev_hex_colour = sc->hex_colour;
401 sc->hex_colour = new_hex_colour;
402 sc->incoming_hex_edge = m->lo;
403 }
404}
405
406void spectrectx_step(SpectreContext *ctx, SpectreCoords *sc,
407 unsigned edge, unsigned *outedge)
408{
409 const struct HexData *h;
410 const struct MapEntry *m;
411
412 assert(0 <= sc->index);
413 assert(sc->index < num_spectres(sc->c[0].type));
414 assert(0 <= edge);
415 assert(edge < 14);
416
417 h = &hexdata[sc->c[0].type];
418 m = &h->specmap[14 * sc->index + edge];
419
420 while (!m->internal) {
421 unsigned recedge;
422 const struct MapEdge *me;
423 spectrectx_step_hex(ctx, sc, 0, m->hi, &recedge);
424 assert(recedge < 6);
425 h = &hexdata[sc->c[0].type];
426 me = &h->specedges[recedge];
427 assert(m->lo < me->len);
428 m = &h->specin[me->startindex + me->len - 1 - m->lo];
429 }
430 sc->index = m->hi;
431 *outedge = m->lo;
432}
433
434void spectrectx_generate(SpectreContext *ctx,
435 bool (*callback)(void *cbctx, const Spectre *spec),
436 void *cbctx)
437{
438 tree234 *placed = newtree234(spectre_cmp);
439 Spectre *qhead = NULL, *qtail = NULL;
440
441 {
442 Spectre *spec = spectre_initial(ctx);
443
444 add234(placed, spec);
445
446 spec->next = NULL;
447
448 if (callback(cbctx, spec))
449 qhead = qtail = spec;
450 }
451
452 while (qhead) {
453 unsigned edge;
454 Spectre *spec = qhead;
455
456 for (edge = 0; edge < 14; edge++) {
457 Spectre *new_spec;
458
459 new_spec = spectre_adjacent(ctx, spec, edge, NULL);
460
461 if (find234(placed, new_spec, NULL)) {
462 spectre_free(new_spec);
463 continue;
464 }
465
466 if (!callback(cbctx, new_spec)) {
467 spectre_free(new_spec);
468 continue;
469 }
470
471 add234(placed, new_spec);
472 qtail->next = new_spec;
473 qtail = new_spec;
474 new_spec->next = NULL;
475 }
476
477 qhead = qhead->next;
478 }
479
480 {
481 Spectre *spec;
482 while ((spec = delpos234(placed, 0)) != NULL)
483 spectre_free(spec);
484 freetree234(placed);
485 }
486}
487
488const char *spectre_tiling_params_invalid(
489 const struct SpectrePatchParams *params)
490{
491 size_t i;
492 Hex h;
493
494 if (params->ncoords == 0)
495 return "expected at least one numeric coordinate";
496 if (!spectre_valid_hex_letter(params->final_hex))
497 return "invalid final hexagon type";
498
499 h = hex_from_letter(params->final_hex);
500 for (i = params->ncoords; i-- > 0 ;) {
501 unsigned limit = (i == 0) ? num_spectres(h) : num_subhexes(h);
502 if (params->coords[i] >= limit)
503 return "coordinate out of range";
504
505 if (i > 0)
506 h = hexdata[h].subhexes[params->coords[i]];
507 }
508
509 return NULL;
510}
511
512struct SpectreCallbackContext {
513 int xoff, yoff;
514 Coord xmin, xmax, ymin, ymax;
515
516 spectre_tile_callback_fn external_cb;
517 void *external_cbctx;
518};
519
520static bool spectre_internal_callback(void *vctx, const Spectre *spec)
521{
522 struct SpectreCallbackContext *ctx = (struct SpectreCallbackContext *)vctx;
523 size_t i;
524 int output_coords[4*14];
525
526 for (i = 0; i < 14; i++) {
527 Point p = spec->vertices[i];
528 Coord x = point_x(p), y = point_y(p);
529 if (coord_cmp(x, ctx->xmin) < 0 || coord_cmp(x, ctx->xmax) > 0 ||
530 coord_cmp(y, ctx->ymin) < 0 || coord_cmp(y, ctx->ymax) > 0)
531 return false;
532
533 output_coords[4*i + 0] = ctx->xoff + x.c1;
534 output_coords[4*i + 1] = x.cr3;
535 output_coords[4*i + 2] = ctx->yoff - y.c1;
536 output_coords[4*i + 3] = -y.cr3;
537 }
538
539 if (ctx->external_cb)
540 ctx->external_cb(ctx->external_cbctx, output_coords);
541
542 return true;
543}
544
545static void spectre_set_bounds(struct SpectreCallbackContext *cbctx,
546 int w, int h)
547{
548 cbctx->xoff = w/2;
549 cbctx->yoff = h/2;
550 cbctx->xmin.c1 = -cbctx->xoff;
551 cbctx->xmax.c1 = -cbctx->xoff + w;
552 cbctx->ymin.c1 = cbctx->yoff - h;
553 cbctx->ymax.c1 = cbctx->yoff;
554 cbctx->xmin.cr3 = 0;
555 cbctx->xmax.cr3 = 0;
556 cbctx->ymin.cr3 = 0;
557 cbctx->ymax.cr3 = 0;
558}
559
560void spectre_tiling_randomise(struct SpectrePatchParams *ps, int w, int h,
561 random_state *rs)
562{
563 SpectreContext ctx[1];
564 struct SpectreCallbackContext cbctx[1];
565 size_t i;
566
567 spectre_set_bounds(cbctx, w, h);
568 cbctx->external_cb = NULL;
569 cbctx->external_cbctx = NULL;
570
571 spectrectx_init_random(ctx, rs);
572 spectrectx_generate(ctx, spectre_internal_callback, cbctx);
573
574 ps->orientation = ctx->orientation;
575 ps->ncoords = ctx->prototype->nc;
576 ps->coords = snewn(ps->ncoords, unsigned char);
577 ps->coords[0] = ctx->prototype->index;
578 for (i = 1; i < ps->ncoords; i++)
579 ps->coords[i] = ctx->prototype->c[i-1].index;
580 ps->final_hex = hex_to_letter(ctx->prototype->c[ps->ncoords-1].type);
581
582 spectrectx_cleanup(ctx);
583}
584
585void spectre_tiling_generate(
586 const struct SpectrePatchParams *params, int w, int h,
587 spectre_tile_callback_fn external_cb, void *external_cbctx)
588{
589 SpectreContext ctx[1];
590 struct SpectreCallbackContext cbctx[1];
591
592 spectre_set_bounds(cbctx, w, h);
593 cbctx->external_cb = external_cb;
594 cbctx->external_cbctx = external_cbctx;
595
596 spectrectx_init_from_params(ctx, params);
597 spectrectx_generate(ctx, spectre_internal_callback, cbctx);
598 spectrectx_cleanup(ctx);
599}