ref: e2add4185cf1e3639b7a320384098d63dc2f3d67
dir: /auxiliary/hatgen.c/
/* * Generate patches of tiling by the 'hat' aperiodic monotile * discovered in 2023. * * This implementation of hat-tiling generation was intended to be the * basis for generating hat grids for Loopy. However, it turned out * that I found a better strategy, so this source file isn't used by * the main puzzle system. I've kept it anyway because I ended up * adapting it to generate the file hat-tables.h containing the lookup * tables for the algorithm I _did_ end up using. It also generates * diagrams that are useful for understanding that algorithm, and for * debugging it if anything still turns out to be wrong with it. * * Discoverers' website: https://cs.uwaterloo.ca/~csk/hat/ * Preprint of paper: https://arxiv.org/abs/2303.10798 */ #include <assert.h> #ifdef NO_TGMATH_H # include <math.h> #else # include <tgmath.h> #endif #include <stdbool.h> #include <stdio.h> #include <stdlib.h> #include <string.h> #include "puzzles.h" #include "tree234.h" #include "hat.h" /* * General strategy: * * We construct the hat tiling by means of a substitution system of * 'metatiles' which come in four types, called H,T,P,F. A (valid) * tiling of these metatiles can be expanded to a larger one by a set * of recursive subdivision rules. Once we have a large enough patch * of metatiles, we apply a final transformation that converts each * metatile into 1, 2 or 4 instances of the aperiodically tiling * 'hat'. * * Unlike the similar substitution system for Penrose tilings, the * expansion rules are not geometrically precise: the larger versions * of each metatile fit together combinatorially in the same way, but * their shapes are distorted slightly. So we must construct our * expanded meta-tiling by breadth-first search out from a starting * metatile, because we won't quite know the coordinates of the * expanded version of each metatile until we know one of the ones * next to it. */ /* * Coordinate system: * * Everything in this code lives on the tiling known to grid.c as * 'Kites', which can be viewed as a tiling of hexagons each of which * is subdivided into six kites sharing their pointy vertex, or * (equivalently) a tiling of equilateral triangles each subdivided * into three kits sharing their blunt vertex. * * We express coordinates in this system relative to the basis (1, r) * where r = (1 + sqrt(3)i) / 2 is a primitive 6th root of unity. This * gives us a system in which two integer coordinates can address any * grid point, provided we scale up so that the side length of the * equilateral triangles in the tiling is 6. */ typedef struct Point { int x, y; /* represents x + yr */ } Point; static inline Point left6(Point p) { /* r satisfies the equation r^2 = r-1. Hence, multiplying by r * (achieving a rotation anticlockwise by 1/6 turn) transforms * x+yr into xr+yr^2 = xr+y(r-1) = (-y) + (x+y)r. * * It's easy to check that iterating this transformation six times * gives you back the same coordinates you started with. */ Point q = { -p.y, p.x + p.y }; return q; } static inline Point right6(Point p) { /* Conversely, 1/r = 1 - r, so dividing by r turns x+yr into x/r+y * = x(1-r) + y = (x+y) + (-x)r. */ Point q = { p.x + p.y, -p.x }; return q; } typedef enum MetatileType { MT_H, MT_T, MT_P, MT_F } MetatileType; typedef struct Metatile Metatile; typedef struct MetaCoord { Metatile *parent; int index; } MetaCoord; struct Metatile { /* Data fields describing the metatile and its position. */ MetatileType type; Point start, orientation; MetaCoord coords[4]; size_t ncoords; /* Auxiliary fields used to store the progress of the expansion * algorithm. */ bool queued; Metatile *qnext; }; #define MT_MAXVERT 6 /* largest number of vertices of any metatile */ #define MT_MAXVDEGREE 3 /* largest degree of any vertex of a meta-tiling */ #define MT_MAXEXPAND 13 /* largest number of metatiles in any expansion */ #define MT_MAXHAT 4 /* largest number of hats in a metatile */ #define HAT_NVERT 14 /* vertices of a single hat (counting the straight one) */ #define HAT_NKITE 8 /* kites in a single hat */ static int metatile_cmp(void *av, void *bv) { Metatile *a = (Metatile *)av, *b = (Metatile *)bv; if (a->type < b->type) return -1; if (a->type > b->type) return +1; if (a->start.x < b->start.x) return -1; if (a->start.x > b->start.x) return +1; if (a->start.y < b->start.y) return -1; if (a->start.y > b->start.y) return +1; if (a->orientation.x < b->orientation.x) return -1; if (a->orientation.x > b->orientation.x) return +1; if (a->orientation.y < b->orientation.y) return -1; if (a->orientation.y > b->orientation.y) return +1; return 0; } /* * Return the coordinates of the vertices of a metatile, given the * coordinates of the vertex we deem to be distinguished, and a vector * of Euclidean length 1 showing its direction. * * If 'expanded' is true, we instead return the coordinates of the * corresponding vertices of the expanded version of the same * metatile. */ static size_t metatile_vertices(Metatile m, Point *out, bool expanded) { static const Point vertices_H[] = { {0, 0}, {4, -2}, {12, 6}, {10, 10}, {-6, 18}, {-8, 16}, }; static const Point vertices_T[] = { {0, 0}, {6, 6}, {-6, 12}, }; static const Point vertices_P[] = { {0, 0}, {4, 4}, {-4, 20}, {-8, 16}, }; static const Point vertices_F[] = { {0, 0}, {4, -2}, {6, 0}, {-2, 16}, {-6, 12}, }; static const Point expanded_H[] = { {0, 0}, {12, -6}, {30, 12}, {24, 24}, {-12, 42}, {-18, 36}, }; static const Point expanded_T[] = { {0, 0}, {12, 12}, {-12, 24}, }; static const Point expanded_P[] = { {0, 0}, {14, 8}, {-4, 44}, {-18, 36}, }; static const Point expanded_F[] = { {0, 0}, {14, -4}, {18, 6}, {0, 42}, {-14, 34}, }; const Point *vertices; size_t nvertices; size_t i; switch (m.type) { case MT_H: vertices = expanded ? expanded_H : vertices_H; nvertices = lenof(vertices_H); break; case MT_T: vertices = expanded ? expanded_T : vertices_T; nvertices = lenof(vertices_T); break; case MT_P: vertices = expanded ? expanded_P : vertices_P; nvertices = lenof(vertices_P); break; default /* case MT_F */: vertices = expanded ? expanded_F : vertices_F; nvertices = lenof(vertices_F); break; } assert(nvertices <= MT_MAXVERT); Point orientation_r = left6(m.orientation); for (i = 0; i < nvertices; i++) { Point v = vertices[i]; out[i].x = m.start.x + v.x * m.orientation.x + v.y * orientation_r.x; out[i].y = m.start.y + v.x * m.orientation.y + v.y * orientation_r.y; } return nvertices; } /* * Return a list of metatiles that arise from expanding a given tile. */ static size_t metatile_expand(Metatile m, Metatile *out) { static const Metatile tiles_H[] = { {MT_H, {-4, 20}, {1, 0}}, {MT_H, {2, 2}, {1, 0}}, {MT_H, {8, 26}, {0, -1}}, {MT_T, {6, 24}, {-1, 0}}, {MT_P, {-8, 16}, {1, 0}}, {MT_P, {4, 34}, {0, -1}}, {MT_P, {6, 0}, {1, -1}}, {MT_F, {-10, 38}, {-1, 1}}, {MT_F, {-10, 44}, {0, -1}}, {MT_F, {-4, 2}, {1, 0}}, {MT_F, {2, 2}, {0, -1}}, {MT_F, {26, 14}, {1, 0}}, {MT_F, {32, 8}, {-1, 1}}, }; static const Metatile tiles_T[] = { {MT_H, {10, 10}, {-1, 1}}, {MT_P, {-6, 0}, {1, 0}}, {MT_P, {8, 14}, {0, 1}}, {MT_P, {18, 6}, {-1, 1}}, {MT_F, {-14, 34}, {-1, 0}}, {MT_F, {-8, -2}, {1, -1}}, {MT_F, {22, 4}, {0, 1}}, }; static const Metatile tiles_P[] = { {MT_H, {4, 22}, {0, 1}}, {MT_H, {10, 10}, {-1, 1}}, {MT_P, {-6, 0}, {1, 0}}, {MT_P, {6, 24}, {1, 0}}, {MT_P, {8, 14}, {0, 1}}, {MT_F, {-20, 40}, {1, -1}}, {MT_F, {-14, 34}, {-1, 0}}, {MT_F, {-8, -2}, {1, -1}}, {MT_F, {4, 46}, {-1, 1}}, {MT_F, {10, 10}, {1, 0}}, {MT_F, {16, 4}, {-1, 1}}, }; static const Metatile tiles_F[] = { {MT_H, {8, 20}, {0, 1}}, {MT_H, {14, 8}, {-1, 1}}, {MT_P, {10, 22}, {1, 0}}, {MT_P, {12, 12}, {0, 1}}, {MT_F, {-16, 38}, {1, -1}}, {MT_F, {-10, 32}, {-1, 0}}, {MT_F, {-4, 2}, {1, 0}}, {MT_F, {2, 2}, {0, -1}}, {MT_F, {8, 44}, {-1, 1}}, {MT_F, {14, 8}, {1, 0}}, {MT_F, {20, 2}, {-1, 1}}, }; const Metatile *tiles; size_t ntiles; size_t i; switch (m.type) { case MT_H: tiles = tiles_H; ntiles = lenof(tiles_H); break; case MT_T: tiles = tiles_T; ntiles = lenof(tiles_T); break; case MT_P: tiles = tiles_P; ntiles = lenof(tiles_P); break; default /* case MT_F */: tiles = tiles_F; ntiles = lenof(tiles_F); break; } assert(ntiles <= MT_MAXEXPAND); Point orientation_r = left6(m.orientation); for (i = 0; i < ntiles; i++) { Metatile t = tiles[i]; out[i].type = t.type; out[i].start.x = (m.start.x + t.start.x * m.orientation.x + t.start.y * orientation_r.x); out[i].start.y = (m.start.y + t.start.x * m.orientation.y + t.start.y * orientation_r.y); out[i].orientation.x = (t.orientation.x * m.orientation.x + t.orientation.y * orientation_r.x); out[i].orientation.y = (t.orientation.x * m.orientation.y + t.orientation.y * orientation_r.y); } return ntiles; } /* Store data about each vertex during an expansion. */ typedef struct VertexMapping { Point in; /* Metatiles sharing this vertex */ Metatile *tiles[MT_MAXVDEGREE]; size_t ntiles; /* The expanded coordinates of this vertex, if known */ bool mapped; Point out; } VertexMapping; static int vertexmapping_cmp(void *av, void *bv) { VertexMapping *a = (VertexMapping *)av, *b = (VertexMapping *)bv; if (a->in.x < b->in.x) return -1; if (a->in.x > b->in.x) return +1; if (a->in.y < b->in.y) return -1; if (a->in.y > b->in.y) return +1; return 0; } static int vertexmapping_find(void *av, void *bv) { Point *a = (Point *)av; VertexMapping *b = (VertexMapping *)bv; if (a->x < b->in.x) return -1; if (a->x > b->in.x) return +1; if (a->y < b->in.y) return -1; if (a->y > b->in.y) return +1; return 0; } typedef struct MetatileSet { /* The tiles in the set */ tree234 *tiles; /* * Bounding box of a rectangular region within the original single * tile this set was expanded from. We need this in order to pick * a random chunk out of the tiling to return to our client: this * box is the limit of where we might select our chunk from. * * The box is obtained by starting from the two obtuse vertices of * the starting P metatile, and then mapping those two vertices * through each expansion pass. This wouldn't work for the _other_ * two vertices of the P metatile, which end up in the middle of * another metatile after the first expansion, so that the next * expansion wouldn't find that point in its VertexMapping. But * luckily the two inner P vertices do continue working: they * alternate in subsequent expansions between vertex 1 and vertex * 4 of an F metatile. And those are the ones we need to define a * reliable bounding box - phew! */ Point vertices[2]; size_t nvertices; } MetatileSet; static MetatileSet *metatile_initial_set(MetatileType type) { MetatileSet *s; Metatile *m; Point vertices[MT_MAXVERT]; size_t nv; s = snew(MetatileSet); s->tiles = newtree234(metatile_cmp); m = snew(Metatile); m->type = type; m->start.x = 0; m->start.y = 0; m->orientation.x = 1; m->orientation.y = 0; m->ncoords = 0; add234(s->tiles, m); if (type == MT_P) { nv = metatile_vertices(*m, vertices, false); assert(nv == 4); s->vertices[0] = vertices[1]; s->vertices[1] = vertices[3]; s->nvertices = 2; } else { s->nvertices = 0; } return s; } static void metatile_free_set(MetatileSet *s) { Metatile *m; while ((m = delpos234(s->tiles, 0)) != NULL) sfree(m); freetree234(s->tiles); sfree(s); } typedef struct Queue { Metatile *head, *tail; } Queue; static void map_vertex(VertexMapping *vm, Point out, Queue *queue) { size_t i; debug(("map_vertex %d,%d -> %d,%d", vm->in.x, vm->in.y, out.x, out.y)); if (vm->mapped) { debug((" (already done)\n")); return; } debug(("\n")); vm->mapped = true; vm->out = out; for (i = 0; i < vm->ntiles; i++) { Metatile *t = vm->tiles[i]; if (!t->queued) { t->queued = true; t->qnext = NULL; if (queue->tail) queue->tail->qnext = t; else queue->head = t; queue->tail = t; debug(("queued %c @ %d,%d d=%d,%d\n", "HTPF"[t->type], t->start.x, t->start.y, t->orientation.x, t->orientation.y)); } } } /* * Expand a set of metatiles into its next-generation set. Returns the * new set. The old set is not freed, but the auxiliary fields of its * Metatile structures will be used as intermediate storage. */ static MetatileSet *metatile_set_expand(MetatileSet *si) { tree234 *vmap; VertexMapping *vm; Metatile *m; Queue queue = { NULL, NULL }; size_t i, j; MetatileSet *so = snew(MetatileSet); so->tiles = newtree234(metatile_cmp); /* * Enumerate all the vertices in our tiling, and store the set of * tiles they belong to. */ vmap = newtree234(vertexmapping_cmp); for (i = 0; (m = index234(si->tiles, i)) != NULL; i++) { Point vertices[MT_MAXVERT]; size_t nv = metatile_vertices(*m, vertices, false); for (j = 0; j < nv; j++) { VertexMapping *newvm = snew(VertexMapping); newvm->in = vertices[j]; newvm->ntiles = 0; newvm->mapped = false; vm = add234(vmap, newvm); if (vm != newvm) sfree(newvm); assert(vm->ntiles < MT_MAXVDEGREE); vm->tiles[vm->ntiles++] = m; } m->queued = false; } for (i = 0; (vm = index234(vmap, i)) != NULL; i++) { debug(("vertex @ %d,%d {", vm->in.x, vm->in.y)); for (j = 0; j < vm->ntiles; j++) { m = vm->tiles[j]; debug(("%s%c @ %d,%d d=%d,%d", j?", ":"", "HTPF"[m->type], m->start.x, m->start.y, m->orientation.x, m->orientation.y)); } debug(("}\n")); } /* * Initialise an arbitrary vertex to a known location. */ { Point p = {0, 0}; m = index234(si->tiles, 0); vm = find234(vmap, &m->start, vertexmapping_find); map_vertex(vm, p, &queue); } /* * Now process the queue of tiles to be expanded. */ debug(("-- start\n")); while (queue.head) { Metatile *m, m_moved; Metatile t[MT_MAXEXPAND]; Point vi[MT_MAXVERT], vo[MT_MAXVERT]; size_t nv, nt; m = queue.head; queue.head = queue.head->qnext; if (!queue.head) queue.tail = NULL; debug(("unqueued %c @ %d,%d d=%d,%d\n", "HTPF"[m->type], m->start.x, m->start.y, m->orientation.x, m->orientation.y)); nv = metatile_vertices(*m, vi, false); metatile_vertices(*m, vo, true); /* Find a vertex of this tile that's already mapped, and use * it to determine the placement. */ int dx, dy; for (i = 0; i < nv; i++) { vm = find234(vmap, &vi[i], vertexmapping_find); assert(vm); if (vm->mapped) { dx = vm->out.x - vo[i].x; dy = vm->out.y - vo[i].y; debug(("found mapped vertex %d,%d -> %d,%d: " "offset=%d,%d\n", vm->in.x, vm->in.y, vm->out.x, vm->out.y, dx, dy)); break; } } assert(i < nv && "Why was this tile queued without a mapped vertex?"); /* Now map all the rest of the vertices of the tile. */ for (i = 0; i < nv; i++) { vm = find234(vmap, &vi[i], vertexmapping_find); vo[i].x += dx; vo[i].y += dy; map_vertex(vm, vo[i], &queue); } /* And expand it, substituting in its new starting coordinate. */ m_moved = *m; /* structure copy */ m_moved.start = vo[0]; nt = metatile_expand(m_moved, t); for (i = 0; i < nt; i++) { Metatile *newmt = snew(Metatile); *newmt = t[i]; /* structure copy */ newmt->ncoords = 0; debug(("expanded %c @ %d,%d d=%d,%d\n", "HTPF"[newmt->type], newmt->start.x, newmt->start.y, newmt->orientation.x, newmt->orientation.y)); Metatile *added = add234(so->tiles, newmt); if (added != newmt) sfree(newmt); assert(added->ncoords < lenof(added->coords)); added->coords[added->ncoords].parent = m; added->coords[added->ncoords].index = i; added->ncoords++; } } for (i = 0; (m = index234(si->tiles, i)) != NULL; i++) { if (!m->queued) debug(("OMITTED %c @ %d,%d d=%d,%d\n", "HTPF"[m->type], m->start.x, m->start.y, m->orientation.x, m->orientation.y)); } /* * Write out the remapped versions of the tile set's bounding * vertices. */ for (i = 0; i < si->nvertices; i++) { vm = find234(vmap, &si->vertices[i], vertexmapping_find); so->vertices[i] = vm->out; } so->nvertices = si->nvertices; while ((vm = delpos234(vmap, 0)) != NULL) sfree(vm); freetree234(vmap); return so; } typedef struct Hat { Point start, orientation; bool reversed; const Metatile *parent; int index; } Hat; static size_t metatile_hats(const Metatile *m, Hat *out) { static const Hat hats_H[] = { {{6, 0}, {1, 0}, false}, {{6, 6}, {0, -1}, false}, {{0, 12}, {1, 0}, false}, {{0, 6}, {-1, 0}, true}, }; static const Hat hats_T[] = { {{-2, 10}, {-1, 1}, false}, }; static const Hat hats_P[] = { {{-2, 10}, {-1, 1}, false}, {{-2, 16}, {0, 1}, false}, }; static const Hat hats_F[] = { {{0, 6}, {-1, 1}, false}, {{0, 12}, {0, 1}, false}, }; const Hat *hats; size_t nhats; size_t i; switch (m->type) { case MT_H: hats = hats_H; nhats = lenof(hats_H); break; case MT_T: hats = hats_T; nhats = lenof(hats_T); break; case MT_P: hats = hats_P; nhats = lenof(hats_P); break; default /* case MT_F */: hats = hats_F; nhats = lenof(hats_F); break; } assert(nhats <= MT_MAXHAT); Point orientation_r = left6(m->orientation); for (i = 0; i < nhats; i++) { Hat h = hats[i]; out[i].parent = m; out[i].index = i; out[i].start.x = (m->start.x + h.start.x * m->orientation.x + h.start.y * orientation_r.x); out[i].start.y = (m->start.y + h.start.x * m->orientation.y + h.start.y * orientation_r.y); out[i].orientation.x = (h.orientation.x * m->orientation.x + h.orientation.y * orientation_r.x); out[i].orientation.y = (h.orientation.x * m->orientation.y + h.orientation.y * orientation_r.y); out[i].reversed = h.reversed; } return nhats; } static size_t hat_vertices(Hat h, Point *out) { static const Point reference_hat[] = { {0, 0}, {3, 0}, {2, 2}, {0, 3}, {-2, 4}, {-3, 3}, {-6, 6}, {-9, 6}, {-8, 4}, {-6, 3}, {-6, 0}, {-3, -3}, {-2, -2}, {0, -3}, }; size_t i; Point orientation_r; if (h.reversed) orientation_r = right6(h.orientation); else orientation_r = left6(h.orientation); assert(lenof(reference_hat) == HAT_NVERT); for (i = 0; i < lenof(reference_hat); i++) { Point v = reference_hat[h.reversed ? HAT_NVERT-1-i : i]; out[i].x = h.start.x + v.x * h.orientation.x + v.y * orientation_r.x; out[i].y = h.start.y + v.x * h.orientation.y + v.y * orientation_r.y; } return lenof(reference_hat); } typedef struct BoundingBox { Point bl, tr; } BoundingBox; static bool point_in_bbox(Point p, const BoundingBox *bbox) { int xl, xr, x; if (!bbox) return true; /* * Bounding boxes have vertical edges, not aligned with our basis * vector r. So the 'true' x coordinate of (x,y) is proportional * to 2x+y. */ if (p.y < bbox->bl.y || p.y > bbox->tr.y) return false; xl = 2*bbox->bl.x + bbox->bl.y; xr = 2*bbox->tr.x + bbox->tr.y; x = 2*p.x + p.y; if (x < xl || x > xr) return false; return true; } static bool hat_in_bbox(Hat h, const BoundingBox *bbox) { Point p[HAT_NVERT]; size_t i, np; if (!bbox) return true; np = hat_vertices(h, p); for (i = 0; i < np; i++) if (!point_in_bbox(p[i], bbox)) return false; return true; } static Hat *metatile_set_to_hats(MetatileSet *s, size_t *nhats, const BoundingBox *bbox) { Metatile *m; size_t i, j, k, n; Hat *h; n = 0; for (i = 0; (m = index234(s->tiles, i)) != NULL; i++) { Hat htmp[MT_MAXHAT]; size_t nthis = metatile_hats(m, htmp); for (k = 0; k < nthis; k++) if (hat_in_bbox(htmp[k], bbox)) n++; } *nhats = n; h = snewn(n, Hat); j = 0; for (i = 0; (m = index234(s->tiles, i)) != NULL; i++) { Hat htmp[MT_MAXHAT]; size_t nthis = metatile_hats(m, htmp); for (k = 0; k < nthis; k++) { if (hat_in_bbox(htmp[k], bbox)) { assert(j < n); h[j++] = htmp[k]; /* structure copy */ } } } assert(j == n); return h; } #if 0 void hat_tiling_randomise(struct HatPatchParams *params, random_state *rs) { MetatileSet *s, *s2; int x0, x1, y0, y1; /* * Iterate until we have a good-sized patch to select a rectangle * from. */ s = metatile_initial_set(MT_P); params->iterations = 0; while (true) { x0 = 2 * s->vertices[0].x + s->vertices[0].y; x1 = 2 * s->vertices[1].x + s->vertices[1].y; if (x1 < x0) { int t = x1; x1 = x0; x0 = t; } y0 = s->vertices[0].y; y1 = s->vertices[1].y; if (y1 < y0) { int t = y1; y1 = y0; y0 = t; } if (50*params->w <= x1-x0 && 50*params->h <= y1-y0) break; params->iterations++; s2 = metatile_set_expand(s); metatile_free_set(s); s = s2; } /* * Now select that rectangle. */ params->x = x0 + random_upto(rs, x1 - x0 - params->w + 1); params->y = y0 + random_upto(rs, y1 - y0 - params->h + 1); } void hat_tiling_generate(struct HatPatchParams *params, hat_tile_callback_fn cb, void *cbctx) { MetatileSet *s, *s2; unsigned i; size_t j, nh; BoundingBox bbox; Hat *hats; s = metatile_initial_set(MT_P); for (i = 0; i < params->iterations; i++) { s2 = metatile_set_expand(s); metatile_free_set(s); s = s2; } bbox.bl.x = (params->x - params->y) / 2; bbox.tr.x = ((params->x + params->w) - (params->y + params->h)) / 2; bbox.bl.y = params->y; bbox.tr.y = params->y + params->h; hats = metatile_set_to_hats(s, &nh, &bbox); for (j = 0; j < nh; j++) { Point vertices[HAT_NVERT]; size_t nv = hat_vertices(hats[j], vertices); int out[2 * HAT_NVERT]; size_t k; for (k = 0; k < nv; k++) { out[2*k] = 2 * vertices[k].x + vertices[k].y; out[2*k+1] = vertices[k].y; } cb(cbctx, nv, out); } sfree(hats); metatile_free_set(s); } #endif #ifdef TEST_HAT /* * Assortment of test modes that output Postscript diagrams. */ static size_t hat_kite_centres(Hat h, Point *out) { static const Point reference_hat[] = { {-7,5},{-5,4},{-5,1},{-4,-1},{-1,-1},{-2,1},{-1,2},{1,1}, }; size_t i; Point orientation_r; if (h.reversed) orientation_r = right6(h.orientation); else orientation_r = left6(h.orientation); assert(lenof(reference_hat) == HAT_NKITE); for (i = 0; i < lenof(reference_hat); i++) { Point v = reference_hat[i]; out[i].x = h.start.x + v.x * h.orientation.x + v.y * orientation_r.x; out[i].y = h.start.y + v.x * h.orientation.y + v.y * orientation_r.y; } return lenof(reference_hat); } static inline int round6(int x) { int sign = x<0 ? -1 : +1; x *= sign; x += 3; x /= 6; x *= 6; x *= sign; return x; } static inline Point kite_left(Point k) { Point centre = { round6(k.x), round6(k.y) }; Point offset = { k.x - centre.x, k.y - centre.y }; offset = left6(offset); Point r = { centre.x + offset.x, centre.y + offset.y }; return r; } static inline Point kite_right(Point k) { Point centre = { round6(k.x), round6(k.y) }; Point offset = { k.x - centre.x, k.y - centre.y }; offset = right6(offset); Point r = { centre.x + offset.x, centre.y + offset.y }; return r; } static inline Point kite_forward_left(Point k) { Point centre = { round6(k.x), round6(k.y) }; Point offset = { k.x - centre.x, k.y - centre.y }; Point rotate = left6(offset); Point r = { k.x + rotate.x + offset.x, k.y + rotate.y + offset.y }; return r; } static inline Point kite_forward_right(Point k) { Point centre = { round6(k.x), round6(k.y) }; Point offset = { k.x - centre.x, k.y - centre.y }; Point rotate = right6(offset); Point r = { k.x + rotate.x + offset.x, k.y + rotate.y + offset.y }; return r; } typedef struct pspoint { float x, y; } pspoint; static inline pspoint pscoords(Point p) { pspoint q = { p.x + p.y / 2.0F, p.y * sqrt(0.75) }; return q; } typedef struct psbbox { bool started; pspoint bl, tr; } psbbox; static inline void psbbox_add(psbbox *bbox, pspoint p) { if (!bbox->started || bbox->bl.x > p.x) bbox->bl.x = p.x; if (!bbox->started || bbox->tr.x < p.x) bbox->tr.x = p.x; if (!bbox->started || bbox->bl.y > p.y) bbox->bl.y = p.y; if (!bbox->started || bbox->tr.y < p.y) bbox->tr.y = p.y; bbox->started = true; } static void draw_metatiles_svg(const Metatile *tiles, size_t n, const Point *bounds, bool coords) { size_t i, j; psbbox bbox = { false }; for (i = 0; i < n; i++) { Point vertices[MT_MAXVERT]; size_t nv = metatile_vertices(tiles[i], vertices, false); for (j = 0; j < nv; j++) psbbox_add(&bbox, pscoords(vertices[j])); } float ascale = 10, xscale = ascale, yscale = -ascale; float border = 0.2 * ascale; /* leave room for strokes at the edges */ float ox = -xscale * bbox.bl.x + border; float oy = -yscale * bbox.tr.y + border; printf("<?xml version=\"1.0\" encoding=\"UTF-8\" standalone=\"no\"?>\n"); printf("<svg xmlns=\"http://www.w3.org/2000/svg\" version=\"1.1\" " "width=\"%g\" height=\"%g\">\n", ceil(ox + xscale * bbox.tr.x + 2*border), ceil(oy + yscale * bbox.bl.y + 2*border)); for (i = 0; i < n; i++) { Point vertices[MT_MAXVERT]; size_t nv = metatile_vertices(tiles[i], vertices, false); pspoint pp[MT_MAXVERT]; for (j = 0; j < nv; j++) { pp[j] = pscoords(vertices[j]); pp[j].x = ox + xscale * pp[j].x; pp[j].y = oy + yscale * pp[j].y; } printf("<path style=\"" "fill: none; " "stroke: black; " "stroke-width: %f; " "stroke-linejoin: round; " "stroke-linecap: round; " "\" d=\"", 0.2 * ascale); for (j = 0; j < nv; j++) printf("%s %f %f \n", j ? "L" : "M", pp[j].x, pp[j].y); printf("z\" />\n"); if (tiles[i].type != MT_F) { /* * Mark arrows on three of the metatile types (H, T, P), * following the diagrams in the paper. (The metatile * shapes other than F each have some symmetry, but their * roles in the metatile substitution system are not * similarly symmetric, so for diagnostic diagrams you * want to mark their orientation.) */ pspoint lstart, lend; pspoint astart, aend, aforward, aleft; double d; /* * Determine endpoints of a line crossing the polygon in * the appropriate direction, by case analysis on the * individual tile types. */ switch (tiles[i].type) { case MT_H: lstart.x = (pp[4].x + pp[5].x) / 2; lstart.y = (pp[4].y + pp[5].y) / 2; lend.x = (pp[1].x + pp[2].x) / 2; lend.y = (pp[1].y + pp[2].y) / 2; break; case MT_T: lstart = pp[0]; lend.x = (pp[1].x + pp[2].x) / 2; lend.y = (pp[1].y + pp[2].y) / 2; break; default /* case MT_P */: lstart.x = (5*pp[3].x + 3*pp[0].x) / 8; lstart.y = (5*pp[3].y + 3*pp[0].y) / 8; lend.x = (5*pp[1].x + 3*pp[2].x) / 8; lend.y = (5*pp[1].y + 3*pp[2].y) / 8; break; } /* * Now shorten that line a little and give it an arrowhead. */ astart.x = (4 * lstart.x + lend.x) / 5; astart.y = (4 * lstart.y + lend.y) / 5; aend.x = (lstart.x + 4 * lend.x) / 5; aend.y = (lstart.y + 4 * lend.y) / 5; aforward.x = aend.x - astart.x; aforward.y = aend.y - astart.y; d = sqrt(aforward.x*aforward.x + aforward.y*aforward.y); aforward.x /= d; aforward.y /= d; aleft.x = -aforward.y; aleft.y = +aforward.x; printf("<path style=\"" "fill: none; " "stroke: black; " "stroke-width: %f; " "stroke-opacity: 0.2; " "stroke-linejoin: round; " "stroke-linecap: round; " "\" d=\"", 0.9 * ascale); printf("M %f %f L %f %f ", astart.x, astart.y, aend.x, aend.y); printf("L %f %f ", aend.x - 1.2 * ascale * (aforward.x + aleft.x), aend.y - 1.2 * ascale * (aforward.y + aleft.y)); printf("M %f %f L %f %f ", aend.x, aend.y, aend.x - 1.2 * ascale * (aforward.x - aleft.x), aend.y - 1.2 * ascale * (aforward.y - aleft.y)); printf("\" />\n"); } if (coords) { /* * Print each tile's coordinates. */ pspoint centre; size_t j; switch (tiles[i].type) { case MT_H: centre.x = (pp[0].x + pp[2].x + pp[4].x) / 3; centre.y = (pp[0].y + pp[2].y + pp[4].y) / 3; break; case MT_T: centre.x = (pp[0].x + pp[1].x + pp[2].x) / 3; centre.y = (pp[0].y + pp[1].y + pp[2].y) / 3; break; case MT_P: centre.x = (pp[0].x + pp[2].x) / 2; centre.y = (pp[0].y + pp[2].y) / 2; break; default /* case MT_F */: centre.x = (pp[2].x + pp[4].x) / 2; centre.y = (pp[2].y + pp[4].y) / 2; break; } double lineheight = ascale * 1.5; double charheight = lineheight * 0.6; /* close enough */ double allheight = lineheight * (tiles[i].ncoords-1) + charheight; for (j = 0; j < tiles[i].ncoords; j++) { const Metatile *it; unsigned cindex; printf("<text style=\"" "fill: black; " "font-family: Sans; " "font-size: %g; " "text-anchor: middle; " "text-align: center; " "\" x=\"%g\" y=\"%g\">", lineheight, centre.x, centre.y - allheight/2 + charheight + lineheight*j); it = &tiles[i]; cindex = j; while (cindex < it->ncoords) { if (it != &tiles[i]) printf("."); printf("%d", (int)it->coords[cindex].index); it = it->coords[cindex].parent; cindex = 0; /* BODGING AHOY */ } printf("</text>\n"); } } } printf("</svg>\n"); } static void draw_metatile_set_svg( MetatileSet *tiles, const Point *bounds, bool coords) { /* * Slurp the tree234 of tiles into an array for display. * Tedious, but this test code doesn't have to be particularly * efficient. */ size_t nt = count234(tiles->tiles); Metatile *t = snewn(nt, Metatile); size_t i; for (i = 0; i < nt; i++) { Metatile *m = index234(tiles->tiles, i); t[i] = *m; /* structure copy */ } draw_metatiles_svg(t, nt, bounds, coords); sfree(t); } static void draw_hats_svg(const Hat *hats, size_t n, const Point *bounds, bool kites, char coordtype) { size_t i, j; psbbox bbox = { false }; for (i = 0; i < n; i++) { Point vertices[HAT_NVERT]; size_t nv = hat_vertices(hats[i], vertices); for (j = 0; j < nv; j++) psbbox_add(&bbox, pscoords(vertices[j])); } float ascale = (coordtype == 'k' || coordtype == 'K' ? 20 : 10); float xscale = ascale, yscale = -ascale; float border = 0.2 * ascale; /* leave room for strokes at the edges */ float ox = -xscale * bbox.bl.x + border; float oy = -yscale * bbox.tr.y + border; printf("<?xml version=\"1.0\" encoding=\"UTF-8\" standalone=\"no\"?>\n"); printf("<svg xmlns=\"http://www.w3.org/2000/svg\" version=\"1.1\" " "width=\"%g\" height=\"%g\">\n", ceil(ox + xscale * bbox.tr.x + 2*border), ceil(oy + yscale * bbox.bl.y + 2*border)); for (i = 0; i < n; i++) { Point vertices[HAT_NVERT]; pspoint psvs[HAT_NVERT]; size_t nv = hat_vertices(hats[i], vertices); int is = hats[i].reversed ? -1 : +1; int io = hats[i].reversed ? 13 : 0; printf("<path style=\"" "fill: %s; " "stroke: black; " "stroke-width: %f; " "stroke-linejoin: round; " "stroke-linecap: round; " "\" d=\"", hats[i].reversed ? "rgba(0,0,0,0.2)" : "none", 0.2 * ascale); for (j = 0; j < nv; j++) { psvs[j] = pscoords(vertices[j]); printf("%s %f %f\n", j ? "L" : "M", ox + xscale * psvs[j].x, oy + yscale * psvs[j].y); } printf("z\" />\n"); if (kites) { /* * Draw internal lines within each hat dividing it into * kites. This is done in a rather bodgy way, sorry. */ const char *fmt = "<path style=\"" "fill: none; " "stroke: rgba(0,0,0,0.2); " "stroke-width: %f; " "stroke-linejoin: round; " "stroke-linecap: round; " "\" d=\"M %f %f L %f %f\" />\n"; float strokewidth = 0.1 * ascale; printf(fmt, strokewidth, ox + xscale * psvs[io+is*0].x, oy + yscale * psvs[io+is*0].y, ox + xscale * psvs[io+is*3].x, oy + yscale * psvs[io+is*3].y); printf(fmt, strokewidth, ox + xscale * psvs[io+is*0].x, oy + yscale * psvs[io+is*0].y, ox + xscale * psvs[io+is*5].x, oy + yscale * psvs[io+is*5].y); printf(fmt, strokewidth, ox + xscale * psvs[io+is*6].x, oy + yscale * psvs[io+is*6].y, ox + xscale * psvs[io+is*9].x, oy + yscale * psvs[io+is*9].y); printf(fmt, strokewidth, ox + xscale * psvs[io+is*0].x, oy + yscale * psvs[io+is*0].y, ox + xscale * psvs[io+is*10].x, oy + yscale * psvs[io+is*10].y); printf(fmt, strokewidth, ox + xscale * psvs[io+is*9].x, oy + yscale * psvs[io+is*9].y, ox + xscale * (psvs[io+is*6].x + psvs[io+is*12].x) / 2, oy + yscale * (psvs[io+is*6].y + psvs[io+is*12].y) / 2); printf(fmt, strokewidth, ox + xscale * psvs[io+is*5].x, oy + yscale * psvs[io+is*5].y, ox + xscale * (psvs[io+is*6].x + psvs[io+is*12].x) / 2, oy + yscale * (psvs[io+is*6].y + psvs[io+is*12].y) / 2); printf(fmt, strokewidth, ox + xscale * psvs[io+is*12].x, oy + yscale * psvs[io+is*12].y, ox + xscale * (psvs[io+is*6].x + psvs[io+is*12].x) / 2, oy + yscale * (psvs[io+is*6].y + psvs[io+is*12].y) / 2); } if (coordtype == 'h') { double lineheight = ascale * 2; double charheight = lineheight * 0.6; /* close enough */ printf("<text style=\"" "fill: black; " "font-family: Sans; " "font-size: %gpx; " "text-anchor: middle; " "text-align: center; " "\" x=\"%g\" y=\"%g\">", lineheight, ox + xscale * (psvs[io+is*0].x + psvs[io+is*10].x) / 2, oy + yscale * (psvs[io+is*0].y + psvs[io+is*10].y) / 2 + charheight/2); printf("%d", (int)i); printf("</text>\n"); } else if (coordtype == 'k') { Point kites[HAT_NKITE]; size_t nk = hat_kite_centres(hats[i], kites); double lineheight = ascale * 0.5; double charheight = lineheight * 0.6; /* close enough */ for (j = 0; j < nk; j++) { pspoint p = pscoords(kites[j]); printf("<text style=\"" "fill: black; " "font-family: Sans; " "font-size: %gpx; " "text-anchor: middle; " "text-align: center; " "\" x=\"%g\" y=\"%g\">", lineheight, ox + xscale * p.x, oy + yscale * p.y + charheight/2); printf("%d.%d.%d", (int)j, hats[i].index, hats[i].parent->coords[0].index); printf("</text>\n"); } } else if (coordtype == 'K') { Point kites[HAT_NKITE]; size_t nk = hat_kite_centres(hats[i], kites); double lineheight = ascale * 1.1; double charheight = lineheight * 0.6; /* close enough */ for (j = 0; j < nk; j++) { pspoint p = pscoords(kites[j]); printf("<text style=\"" "fill: black; " "font-family: Sans; " "font-size: %gpx; " "text-anchor: middle; " "text-align: center; " "\" x=\"%g\" y=\"%g\">", lineheight, ox + xscale * p.x, oy + yscale * p.y + charheight/2); printf("%d", (int)j); printf("</text>\n"); } } } printf("</svg>\n"); } static void draw_hats_python(const Hat *hats, size_t n) { size_t i, j; printf("def hats(hat):\n"); for (i = 0; i < n; i++) { const Hat *hat = &hats[i]; Point vertices[HAT_NVERT]; size_t nv = hat_vertices(*hat, vertices); printf(" hat('%c', %d, None, [", "HTPF"[hat->parent->type], hat->index); for (j = 0; j < nv; j++) { Point v = vertices[j]; printf("%s(%d,%d)", j ? ", " : "", (v.x * 2 + v.y) / 3, v.y); } printf("])\n"); } } typedef enum KiteStep { KS_LEFT, KS_RIGHT, KS_F_LEFT, KS_F_RIGHT } KiteStep; static inline Point kite_step(Point k, KiteStep step) { switch (step) { case KS_LEFT: return kite_left(k); case KS_RIGHT: return kite_right(k); case KS_F_LEFT: return kite_forward_left(k); default /* case KS_F_RIGHT */: return kite_forward_right(k); } } int main(int argc, char **argv) { if (argc <= 1) { printf("usage: hat-test <mode>\n"); printf("modes: H,T,P,F display a single unexpanded tile\n"); printf(" xH,xT,xP,xF display the expansion of one tile\n"); printf(" cH,cT,cP,cF display expansion with tile coords\n"); printf(" CH,CT,CP,CF display double expansion with coords\n"); printf(" hH,hT,hP,hF display the hats from one tile\n"); printf(" HH,HT,HP,HF hats from an expansion, with coords\n"); printf(" m1, m2, ... nth expansion of one H metatile\n"); printf(" M1, M2, ... nth expansion turned into real hats\n"); printf(" --hat show the kites in a single hat\n"); printf(" --tables generate hat-tables.h for hat.c\n"); return 0; } if (!strcmp(argv[1], "H") || !strcmp(argv[1], "T") || !strcmp(argv[1], "P") || !strcmp(argv[1], "F")) { MetatileType type = (argv[1][0] == 'H' ? MT_H : argv[1][0] == 'T' ? MT_T : argv[1][0] == 'P' ? MT_P : MT_F); Metatile m = {type, {0, 0}, {1, 0}}; draw_metatiles_svg(&m, 1, NULL, false); return 0; } if (!strcmp(argv[1], "xH") || !strcmp(argv[1], "xT") || !strcmp(argv[1], "xP") || !strcmp(argv[1], "xF")) { MetatileType type = (argv[1][1] == 'H' ? MT_H : argv[1][1] == 'T' ? MT_T : argv[1][1] == 'P' ? MT_P : MT_F); Metatile m = {type, {0, 0}, {1, 0}}; Metatile t[MT_MAXEXPAND]; size_t nt = metatile_expand(m, t); draw_metatiles_svg(t, nt, NULL, false); return 0; } if (argv[1][0] && argv[1][1] && strchr("cC", argv[1][0]) && strchr("HTPF", argv[1][1])) { MetatileType type = (argv[1][1] == 'H' ? MT_H : argv[1][1] == 'T' ? MT_T : argv[1][1] == 'P' ? MT_P : MT_F); MetatileSet *t[3]; int nsets = (argv[1][0] == 'c' ? 2 : 3); int i; t[0] = metatile_initial_set(type); for (i = 1; i < nsets; i++) t[i] = metatile_set_expand(t[i-1]); draw_metatile_set_svg(t[nsets-1], NULL, true); for (i = 0; i < nsets; i++) metatile_free_set(t[i]); return 0; } if (!strcmp(argv[1], "hH") || !strcmp(argv[1], "hT") || !strcmp(argv[1], "hP") || !strcmp(argv[1], "hF")) { MetatileType type = ( !strcmp(argv[1], "hH") ? MT_H : !strcmp(argv[1], "hT") ? MT_T : !strcmp(argv[1], "hP") ? MT_P : MT_F); Metatile m = {type, {0, 0}, {1, 0}}; Hat h[MT_MAXHAT]; size_t nh = metatile_hats(&m, h); draw_hats_svg(h, nh, NULL, false, 'h'); return 0; } if (!strcmp(argv[1], "--hat")) { Hat h = { { 0, 0 }, { 1, 0 }, false, NULL, 0 }; draw_hats_svg(&h, 1, NULL, true, 'K'); return 0; } if (argv[1][0] == 'H' && argv[1][1] && strchr("HTPF", argv[1][1])) { MetatileType type = (argv[1][1] == 'H' ? MT_H : argv[1][1] == 'T' ? MT_T : argv[1][1] == 'P' ? MT_P : MT_F); MetatileSet *t[2]; size_t i, nh; t[0] = metatile_initial_set(type); t[1] = metatile_set_expand(t[0]); Hat *h = metatile_set_to_hats(t[1], &nh, NULL); draw_hats_svg(h, nh, NULL, true, 'k'); sfree(h); for (i = 0; i < 2; i++) metatile_free_set(t[i]); return 0; } if (argv[1][0] == 'm' || argv[1][0] == 'M') { int niter = atoi(argv[1] + 1); MetatileSet *tiles = metatile_initial_set(MT_P); while (niter-- > 0) { MetatileSet *t2 = metatile_set_expand(tiles); metatile_free_set(tiles); tiles = t2; } if (argv[1][0] == 'M') { size_t nh; Hat *h = metatile_set_to_hats(tiles, &nh, NULL); draw_hats_svg(h, nh, tiles->vertices, false, 0); sfree(h); } else { draw_metatile_set_svg(tiles, tiles->vertices, false); } metatile_free_set(tiles); return 0; } if (argv[1][0] == 'P' && argv[1][1] && strchr("HTPF", argv[1][1])) { int niter = atoi(argv[1] + 2); MetatileType type = (argv[1][1] == 'H' ? MT_H : argv[1][1] == 'T' ? MT_T : argv[1][1] == 'P' ? MT_P : MT_F); MetatileSet *tiles = metatile_initial_set(type); while (niter-- > 0) { MetatileSet *t2 = metatile_set_expand(tiles); metatile_free_set(tiles); tiles = t2; } { size_t nh; Hat *h = metatile_set_to_hats(tiles, &nh, NULL); draw_hats_python(h, nh); sfree(h); } metatile_free_set(tiles); return 0; } if (!strcmp(argv[1], "--tables")) { size_t i, j, k; printf("/*\n" " * Header file autogenerated by auxiliary/hatgen.c\n" " *\n" " * To regenerate, run 'hatgen --tables > hat-tables.h'\n" " */\n\n"); static const char HTPF[] = "HTPF"; printf("static const unsigned hats_in_metatile[] = {"); for (i = 0; i < 4; i++) { Metatile m = {i, {0, 0}, {1, 0}}; Hat h[MT_MAXHAT]; size_t nh = metatile_hats(&m, h); printf(" %zu,", nh); } printf(" };\n\n"); { size_t psizes[4] = {0, 0, 0, 0}; size_t csizes[4] = {0, 0, 0, 0}; for (i = 0; i < 4; i++) { Metatile m = {i, {0, 0}, {1, 0}}; Metatile t[MT_MAXEXPAND]; size_t nt = metatile_expand(m, t); printf("static const TileType children_%c[] = {\n" " ", HTPF[i]); for (j = 0; j < nt; j++) { MetatileType c = t[j].type; psizes[c]++; csizes[i]++; printf(" TT_%c,", HTPF[c]); } printf("\n};\n"); } printf("static const TileType *const children[] = {\n"); for (i = 0; i < 4; i++) printf(" children_%c,\n", HTPF[i]); printf("};\n"); printf("static const size_t nchildren[] = {\n"); for (i = 0; i < 4; i++) printf(" %u,\n", (unsigned)csizes[i]); printf("};\n\n"); } { for (i = 0; i < 4; i++) { MetatileSet *t[2]; size_t j, k, nh, nmeta, ti; struct list { Point kite; unsigned ik, ih, im; } list[8*MT_MAXHAT*MT_MAXEXPAND]; size_t len = 0; t[0] = metatile_initial_set(i); t[1] = metatile_set_expand(t[0]); Hat *h = metatile_set_to_hats(t[1], &nh, NULL); printf("static const KitemapEntry kitemap_%c[] = {\n", HTPF[i]); Point origin = h[0].start; for (j = 0; j < nh; j++) { Point kites[HAT_NKITE]; size_t nk = hat_kite_centres(h[j], kites); for (k = 0; k < nk; k++) { struct list *le = &list[len++]; le->kite.x = kites[k].x - origin.x; le->kite.y = kites[k].y - origin.y; le->ik = k; le->ih = h[j].index; le->im = h[j].parent->coords[0].index; #if 0 printf("// %d,%d = %u.%u.%u\n", le->kite.x, le->kite.y, le->ik, le->ih, le->im); #endif } } nmeta = count234(t[1]->tiles); for (ti = 0; ti < 8 * 4 * nmeta; ti++) { unsigned ik = ti % 8; unsigned ih = ti / 8 % 4; unsigned im = ti / (8*4); struct list *src = NULL, *dst = NULL; int istep; for (j = 0; j < len; j++) { struct list *tmp = &list[j]; if (tmp->ik == ik && tmp->ih == ih && tmp->im == im) { src = tmp; break; } } if (ik == 0) { printf(" /* hat #%u in metatile #%u (type %c)", ih, im, HTPF[((Metatile *)index234( t[1]->tiles, im))->type]); if (!src) printf(" does not exist"); printf(" */\n"); } #if 0 if (src) printf(" // src=%d,%d\n", src->kite.x, src->kite.y); #endif printf(" "); for (istep = 0; istep < 4; istep++) { KiteStep step = istep; dst = NULL; if (src) { Point pdst = kite_step(src->kite, step); #if 0 printf(" /* dst=%d,%d */", pdst.x, pdst.y); #endif for (k = 0; k < len; k++) { struct list *tmp = &list[k]; if (tmp->kite.x == pdst.x && tmp->kite.y == pdst.y) { dst = tmp; break; } } } if (!dst) { printf(" {-1,-1,-1},"); } else { printf(" {%u,%u,%u},", dst->ik, dst->ih, dst->im); } } printf("\n"); } printf("};\n"); sfree(h); for (j = 0; j < 2; j++) metatile_free_set(t[j]); } printf("static const KitemapEntry *const " "kitemap[] = {\n"); for (i = 0; i < 4; i++) printf(" kitemap_%c,\n", HTPF[i]); printf("};\n\n"); } { for (i = 0; i < 4; i++) { MetatileSet *t[3]; Metatile *m; int map[MT_MAXEXPAND * MT_MAXEXPAND]; size_t maplen; for (j = 0; j < lenof(map); j++) map[j] = -1; t[0] = metatile_initial_set(i); for (j = 1; j < 3; j++) t[j] = metatile_set_expand(t[j-1]); for (j = 0; (m = index234(t[2]->tiles, j)) != NULL; j++) { unsigned coords[4]; size_t ncoords = 0; int cindex; #if 0 printf("// ***\n"); #endif for (cindex = 0; cindex < m->ncoords; cindex++) { #if 0 printf("// %d.%d\n", (int)m->coords[cindex].index, (int)m->coords[cindex].parent->coords[0].index); #endif coords[ncoords++] = ( m->coords[cindex].index + MT_MAXEXPAND * m->coords[cindex].parent->coords[0].index); } unsigned prev = ncoords-1; for (k = 0; k < ncoords; k++) { map[coords[prev]] = coords[k]; prev = k; } } printf("static const MetamapEntry metamap_%c[] = {\n", HTPF[i]); maplen = MT_MAXEXPAND * count234(t[1]->tiles); for (j = 0; j < maplen; j++) { printf(" /* %u, %u -> */ ", (unsigned)(j % MT_MAXEXPAND), (unsigned)(j / MT_MAXEXPAND)); if (map[j] == -1) { printf("{-1,-1}, /* does not exist */\n"); } else { printf("{%u, %u},", (unsigned)(map[j] % MT_MAXEXPAND), (unsigned)(map[j] / MT_MAXEXPAND)); if (map[j] == j) printf(" /* no alternatives */"); printf("\n"); } } printf("};\n"); for (j = 0; j < 3; j++) metatile_free_set(t[j]); } printf("static const MetamapEntry *const " "metamap[] = {\n"); for (i = 0; i < 4; i++) printf(" metamap_%c,\n", HTPF[i]); printf("};\n"); } return 0; } fprintf(stderr, "unknown test mode '%s'\n", argv[1]); return 1; } #endif