ref: 56237fa5fa0c2c56785f3667cb7d013dc9779352
dir: /spectre.c/
/*
* Code to generate patches of the aperiodic 'spectre' tiling
* discovered in 2023.
*
* Resources about the tiling from its discoverers:
* https://cs.uwaterloo.ca/~csk/spectre/
* https://arxiv.org/abs/2305.17743
*
* Writeup of the generation algorithm:
* https://www.chiark.greenend.org.uk/~sgtatham/quasiblog/aperiodic-spectre/
*/
#include <assert.h>
#include <string.h>
#include "puzzles.h"
#include "tree234.h"
#include "spectre-internal.h"
#include "spectre-tables-manual.h"
#include "spectre-tables-auto.h"
static const char *const letters =
#define STRINGIFY(x) #x
HEX_LETTERS(STRINGIFY)
#undef STRINGIFY
;
bool spectre_valid_hex_letter(char letter)
{
return strchr(letters, letter) != NULL;
}
static Hex hex_from_letter(char letter)
{
char buf[2];
buf[0] = letter;
buf[1] = '\0';
return strcspn(letters, buf);
}
static Hex hex_to_letter(unsigned char letter)
{
return letters[letter];
}
struct HexData {
const struct MapEntry *hexmap, *hexin, *specmap, *specin;
const struct MapEdge *hexedges, *specedges;
const Hex *subhexes;
const struct Possibility *poss;
size_t nposs;
};
static const struct HexData hexdata[] = {
#define HEXDATA_ENTRY(x) { hexmap_##x, hexin_##x, specmap_##x, \
specin_##x, hexedges_##x, specedges_##x, subhexes_##x, \
poss_##x, lenof(poss_##x) },
HEX_LETTERS(HEXDATA_ENTRY)
#undef HEXDATA_ENTRY
};
static const struct Possibility *choose_poss(
random_state *rs, const struct Possibility *poss, size_t nposs)
{
/*
* If we needed to do this _efficiently_, we'd rewrite all those
* tables above as cumulative frequency tables and use binary
* search. But this happens about log n times in a grid of area n,
* so it hardly matters, and it's easier to keep the tables
* legible.
*/
unsigned long limit = 0, value;
size_t i;
for (i = 0; i < nposs; i++)
limit += poss[i].prob;
value = random_upto(rs, limit);
for (i = 0; i+1 < nposs; i++) {
if (value < poss[i].prob)
return &poss[i];
value -= poss[i].prob;
}
assert(i == nposs - 1);
assert(value < poss[i].prob);
return &poss[i];
}
SpectreCoords *spectre_coords_new(void)
{
SpectreCoords *sc = snew(SpectreCoords);
sc->nc = sc->csize = 0;
sc->c = NULL;
return sc;
}
void spectre_coords_free(SpectreCoords *sc)
{
if (sc) {
sfree(sc->c);
sfree(sc);
}
}
void spectre_coords_make_space(SpectreCoords *sc, size_t size)
{
if (sc->csize < size) {
sc->csize = sc->csize * 5 / 4 + 16;
if (sc->csize < size)
sc->csize = size;
sc->c = sresize(sc->c, sc->csize, HexCoord);
}
}
SpectreCoords *spectre_coords_copy(SpectreCoords *sc_in)
{
SpectreCoords *sc_out = spectre_coords_new();
spectre_coords_make_space(sc_out, sc_in->nc);
memcpy(sc_out->c, sc_in->c, sc_in->nc * sizeof(*sc_out->c));
sc_out->nc = sc_in->nc;
sc_out->index = sc_in->index;
sc_out->hex_colour = sc_in->hex_colour;
sc_out->prev_hex_colour = sc_in->prev_hex_colour;
sc_out->incoming_hex_edge = sc_in->incoming_hex_edge;
return sc_out;
}
void spectre_place(Spectre *spec, Point u, Point v, int index_of_u)
{
size_t i;
Point disp;
/* Vector from u to v */
disp = point_sub(v, u);
for (i = 0; i < 14; i++) {
spec->vertices[(i + index_of_u) % 14] = u;
u = point_add(u, disp);
disp = point_mul(disp, point_rot(
spectre_angles[(i + 1 + index_of_u) % 14]));
}
}
Spectre *spectre_initial(SpectreContext *ctx)
{
Spectre *spec = snew(Spectre);
spectre_place(spec, ctx->start_vertices[0], ctx->start_vertices[1], 0);
spec->sc = spectre_coords_copy(ctx->prototype);
return spec;
}
Spectre *spectre_adjacent(SpectreContext *ctx, const Spectre *src_spec,
unsigned src_edge, unsigned *dst_edge_out)
{
unsigned dst_edge;
Spectre *dst_spec = snew(Spectre);
dst_spec->sc = spectre_coords_copy(src_spec->sc);
spectrectx_step(ctx, dst_spec->sc, src_edge, &dst_edge);
spectre_place(dst_spec, src_spec->vertices[(src_edge+1) % 14],
src_spec->vertices[src_edge], dst_edge);
if (dst_edge_out)
*dst_edge_out = dst_edge;
return dst_spec;
}
static int spectre_cmp(void *av, void *bv)
{
Spectre *a = (Spectre *)av, *b = (Spectre *)bv;
size_t i, j;
/* We should only ever need to compare the first two vertices of
* any Spectre, because those force the rest */
for (i = 0; i < 2; i++) {
for (j = 0; j < 4; j++) {
int ac = a->vertices[i].coeffs[j], bc = b->vertices[i].coeffs[j];
if (ac < bc)
return -1;
if (ac > bc)
return +1;
}
}
return 0;
}
void spectre_free(Spectre *spec)
{
spectre_coords_free(spec->sc);
sfree(spec);
}
static void spectrectx_start_vertices(SpectreContext *ctx, int orientation)
{
Point minus_sqrt3 = point_add(point_rot(5), point_rot(-5));
Point basicedge = point_mul(point_add(point_rot(0), point_rot(-3)),
point_rot(orientation));
Point diagonal = point_add(basicedge, point_mul(basicedge, point_rot(-3)));
ctx->start_vertices[0] = point_mul(diagonal, minus_sqrt3);
ctx->start_vertices[1] = point_add(ctx->start_vertices[0], basicedge);
ctx->orientation = orientation;
}
void spectrectx_init_random(SpectreContext *ctx, random_state *rs)
{
const struct Possibility *poss;
ctx->rs = rs;
ctx->must_free_rs = false;
ctx->prototype = spectre_coords_new();
spectre_coords_make_space(ctx->prototype, 1);
poss = choose_poss(rs, poss_spectre, lenof(poss_spectre));
ctx->prototype->index = poss->lo;
ctx->prototype->c[0].type = poss->hi;
ctx->prototype->c[0].index = -1;
ctx->prototype->nc = 1;
/*
* Choose a random orientation for the starting Spectre.
*
* The obvious thing is to choose the orientation out of all 12
* possibilities. But we do it a more complicated way.
*
* The Spectres in a tiling can be partitioned into two
* equivalence classes under the relation 'orientation differs by
* a multiple of 1/6 turn'. One class is much more common than the
* other class: the 'odd'-orientation Spectres occur rarely (very
* like the rare reflected hats in the hats tiling).
*
* I think it's nicer to arrange that there's a consistent
* orientation for the _common_ class of Spectres, so that there
* will always be plenty of them in the 'canonical' orientation
* with the head upwards. So if the starting Spectre is in the
* even class, we pick an even orientation for it, and if it's in
* the odd class, we pick an odd orientation.
*
* An odd-class Spectre is easy to identify from SpectreCoords.
* They're precisely the ones expanded from a G hex with index 1,
* which means they're the ones that have index 1 _at all_.
*/
spectrectx_start_vertices(ctx, random_upto(rs, 6) * 2 +
ctx->prototype->index);
/* Initialiise the colouring fields deterministically but unhelpfully.
* spectre-test will set these up properly if it wants to */
ctx->prototype->hex_colour = 0;
ctx->prototype->prev_hex_colour = 0;
ctx->prototype->incoming_hex_edge = 0;
}
void spectrectx_init_from_params(
SpectreContext *ctx, const struct SpectrePatchParams *ps)
{
size_t i;
ctx->rs = NULL;
ctx->must_free_rs = false;
ctx->prototype = spectre_coords_new();
spectre_coords_make_space(ctx->prototype, ps->ncoords);
ctx->prototype->index = ps->coords[0];
for (i = 1; i < ps->ncoords; i++)
ctx->prototype->c[i-1].index = ps->coords[i];
ctx->prototype->c[ps->ncoords-1].index = -1;
ctx->prototype->nc = ps->ncoords;
ctx->prototype->c[ps->ncoords-1].type = hex_from_letter(ps->final_hex);
for (i = ps->ncoords - 1; i-- > 0 ;) {
const struct HexData *h = &hexdata[ctx->prototype->c[i+1].type];
ctx->prototype->c[i].type = h->subhexes[ctx->prototype->c[i].index];
}
spectrectx_start_vertices(ctx, ps->orientation);
ctx->prototype->hex_colour = 0;
ctx->prototype->prev_hex_colour = 0;
ctx->prototype->incoming_hex_edge = 0;
}
void spectrectx_cleanup(SpectreContext *ctx)
{
if (ctx->must_free_rs)
random_free(ctx->rs);
spectre_coords_free(ctx->prototype);
}
SpectreCoords *spectrectx_initial_coords(SpectreContext *ctx)
{
return spectre_coords_copy(ctx->prototype);
}
/*
* Extend sc until it has at least n coordinates in, by copying from
* ctx->prototype if needed, and extending ctx->prototype if needed in
* order to do that.
*/
void spectrectx_extend_coords(SpectreContext *ctx, SpectreCoords *sc, size_t n)
{
if (ctx->prototype->nc < n) {
spectre_coords_make_space(ctx->prototype, n);
while (ctx->prototype->nc < n) {
const struct HexData *h = &hexdata[
ctx->prototype->c[ctx->prototype->nc-1].type];
const struct Possibility *poss;
if (!ctx->rs) {
/*
* If there's no random_state available, it must be
* because we were given an explicit coordinate string
* and ran off the end of it.
*
* The obvious thing to do here would be to make up an
* answer non-randomly. But in fact there's a danger
* that this leads to endless recursion within a
* single coordinate step, if the hex edge we were
* trying to traverse turns into another copy of
* itself at the higher level. That happened in early
* testing before I put the random_state in at all.
*
* To avoid that risk, in this situation - which
* _shouldn't_ come up at all in sensibly play - we
* make up a random_state, and free it when the
* context goes away.
*/
ctx->rs = random_new("dummy", 5);
ctx->must_free_rs = true;
}
poss = choose_poss(ctx->rs, h->poss, h->nposs);
ctx->prototype->c[ctx->prototype->nc-1].index = poss->lo;
ctx->prototype->c[ctx->prototype->nc].type = poss->hi;
ctx->prototype->c[ctx->prototype->nc].index = -1;
ctx->prototype->nc++;
}
}
spectre_coords_make_space(sc, n);
while (sc->nc < n) {
assert(sc->c[sc->nc - 1].index == -1);
assert(sc->c[sc->nc - 1].type == ctx->prototype->c[sc->nc - 1].type);
sc->c[sc->nc - 1].index = ctx->prototype->c[sc->nc - 1].index;
sc->c[sc->nc].index = -1;
sc->c[sc->nc].type = ctx->prototype->c[sc->nc].type;
sc->nc++;
}
}
void spectrectx_step_hex(SpectreContext *ctx, SpectreCoords *sc,
size_t depth, unsigned edge, unsigned *outedge)
{
const struct HexData *h;
const struct MapEntry *m;
spectrectx_extend_coords(ctx, sc, depth+2);
assert(0 <= sc->c[depth].index);
assert(sc->c[depth].index < num_subhexes(sc->c[depth].type));
assert(0 <= edge);
assert(edge < 6);
h = &hexdata[sc->c[depth+1].type];
m = &h->hexmap[6 * sc->c[depth].index + edge];
if (!m->internal) {
unsigned recedge;
const struct MapEdge *me;
spectrectx_step_hex(ctx, sc, depth+1, m->hi, &recedge);
assert(recedge < 6);
h = &hexdata[sc->c[depth+1].type];
me = &h->hexedges[recedge];
assert(m->lo < me->len);
m = &h->hexin[me->startindex + me->len - 1 - m->lo];
assert(m->internal);
}
sc->c[depth].index = m->hi;
sc->c[depth].type = h->subhexes[sc->c[depth].index];
*outedge = m->lo;
if (depth == 0) {
/*
* Update the colouring fields to track the colour of the new
* hexagon.
*/
unsigned char new_hex_colour;
if (!((edge ^ sc->incoming_hex_edge) & 1)) {
/* We're going out via the same parity of edge we came in
* on, so the new hex colour is the same as the previous
* one. */
new_hex_colour = sc->prev_hex_colour;
} else {
/* We're going out via the opposite parity of edge, so the
* new colour is the one of {0,1,2} that is neither this
* _nor_ the previous colour. */
new_hex_colour = 0+1+2 - sc->hex_colour - sc->prev_hex_colour;
}
sc->prev_hex_colour = sc->hex_colour;
sc->hex_colour = new_hex_colour;
sc->incoming_hex_edge = m->lo;
}
}
void spectrectx_step(SpectreContext *ctx, SpectreCoords *sc,
unsigned edge, unsigned *outedge)
{
const struct HexData *h;
const struct MapEntry *m;
assert(0 <= sc->index);
assert(sc->index < num_spectres(sc->c[0].type));
assert(0 <= edge);
assert(edge < 14);
h = &hexdata[sc->c[0].type];
m = &h->specmap[14 * sc->index + edge];
while (!m->internal) {
unsigned recedge;
const struct MapEdge *me;
spectrectx_step_hex(ctx, sc, 0, m->hi, &recedge);
assert(recedge < 6);
h = &hexdata[sc->c[0].type];
me = &h->specedges[recedge];
assert(m->lo < me->len);
m = &h->specin[me->startindex + me->len - 1 - m->lo];
}
sc->index = m->hi;
*outedge = m->lo;
}
void spectrectx_generate(SpectreContext *ctx,
bool (*callback)(void *cbctx, const Spectre *spec),
void *cbctx)
{
tree234 *placed = newtree234(spectre_cmp);
Spectre *qhead = NULL, *qtail = NULL;
{
Spectre *spec = spectre_initial(ctx);
add234(placed, spec);
spec->next = NULL;
if (callback(cbctx, spec))
qhead = qtail = spec;
}
while (qhead) {
unsigned edge;
Spectre *spec = qhead;
for (edge = 0; edge < 14; edge++) {
Spectre *new_spec;
new_spec = spectre_adjacent(ctx, spec, edge, NULL);
if (find234(placed, new_spec, NULL)) {
spectre_free(new_spec);
continue;
}
if (!callback(cbctx, new_spec)) {
spectre_free(new_spec);
continue;
}
add234(placed, new_spec);
qtail->next = new_spec;
qtail = new_spec;
new_spec->next = NULL;
}
qhead = qhead->next;
}
{
Spectre *spec;
while ((spec = delpos234(placed, 0)) != NULL)
spectre_free(spec);
freetree234(placed);
}
}
const char *spectre_tiling_params_invalid(
const struct SpectrePatchParams *params)
{
size_t i;
Hex h;
if (params->ncoords == 0)
return "expected at least one numeric coordinate";
if (!spectre_valid_hex_letter(params->final_hex))
return "invalid final hexagon type";
h = hex_from_letter(params->final_hex);
for (i = params->ncoords; i-- > 0 ;) {
unsigned limit = (i == 0) ? num_spectres(h) : num_subhexes(h);
if (params->coords[i] >= limit)
return "coordinate out of range";
if (i > 0)
h = hexdata[h].subhexes[params->coords[i]];
}
return NULL;
}
struct SpectreCallbackContext {
int xoff, yoff;
Coord xmin, xmax, ymin, ymax;
spectre_tile_callback_fn external_cb;
void *external_cbctx;
};
static bool spectre_internal_callback(void *vctx, const Spectre *spec)
{
struct SpectreCallbackContext *ctx = (struct SpectreCallbackContext *)vctx;
size_t i;
int output_coords[4*14];
for (i = 0; i < 14; i++) {
Point p = spec->vertices[i];
Coord x = point_x(p), y = point_y(p);
if (coord_cmp(x, ctx->xmin) < 0 || coord_cmp(x, ctx->xmax) > 0 ||
coord_cmp(y, ctx->ymin) < 0 || coord_cmp(y, ctx->ymax) > 0)
return false;
output_coords[4*i + 0] = ctx->xoff + x.c1;
output_coords[4*i + 1] = x.cr3;
output_coords[4*i + 2] = ctx->yoff - y.c1;
output_coords[4*i + 3] = -y.cr3;
}
if (ctx->external_cb)
ctx->external_cb(ctx->external_cbctx, output_coords);
return true;
}
static void spectre_set_bounds(struct SpectreCallbackContext *cbctx,
int w, int h)
{
cbctx->xoff = w/2;
cbctx->yoff = h/2;
cbctx->xmin.c1 = -cbctx->xoff;
cbctx->xmax.c1 = -cbctx->xoff + w;
cbctx->ymin.c1 = cbctx->yoff - h;
cbctx->ymax.c1 = cbctx->yoff;
cbctx->xmin.cr3 = 0;
cbctx->xmax.cr3 = 0;
cbctx->ymin.cr3 = 0;
cbctx->ymax.cr3 = 0;
}
void spectre_tiling_randomise(struct SpectrePatchParams *ps, int w, int h,
random_state *rs)
{
SpectreContext ctx[1];
struct SpectreCallbackContext cbctx[1];
size_t i;
spectre_set_bounds(cbctx, w, h);
cbctx->external_cb = NULL;
cbctx->external_cbctx = NULL;
spectrectx_init_random(ctx, rs);
spectrectx_generate(ctx, spectre_internal_callback, cbctx);
ps->orientation = ctx->orientation;
ps->ncoords = ctx->prototype->nc;
ps->coords = snewn(ps->ncoords, unsigned char);
ps->coords[0] = ctx->prototype->index;
for (i = 1; i < ps->ncoords; i++)
ps->coords[i] = ctx->prototype->c[i-1].index;
ps->final_hex = hex_to_letter(ctx->prototype->c[ps->ncoords-1].type);
spectrectx_cleanup(ctx);
}
void spectre_tiling_generate(
const struct SpectrePatchParams *params, int w, int h,
spectre_tile_callback_fn external_cb, void *external_cbctx)
{
SpectreContext ctx[1];
struct SpectreCallbackContext cbctx[1];
spectre_set_bounds(cbctx, w, h);
cbctx->external_cb = external_cb;
cbctx->external_cbctx = external_cbctx;
spectrectx_init_from_params(ctx, params);
spectrectx_generate(ctx, spectre_internal_callback, cbctx);
spectrectx_cleanup(ctx);
}