ref: a33d9fad02d6319cb9061119a6165ed5493a3ba5
dir: /hat-internal.h/
/* * Internal definitions for the hat.c tiling generator, shared between * hat.c itself and hat-test.c. */ #include "puzzles.h" /* * Coordinate system: * * The output of 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 pointscale(int scale, Point a) { Point r = { scale * a.x, scale * a.y }; return r; } static inline Point pointadd(Point a, Point b) { Point r = { a.x + b.x, a.y + b.y }; return r; } /* * We identify a single kite by the coordinates of its four vertices. * This allows us to construct the coordinates of an adjacent kite by * taking affine transformations of the original kite's vertices. * * This is a useful way to do it because it means that if you reflect * the kite (by swapping its left and right vertices) then these * transformations also perform in a reflected way. This will be * useful in the code below that outputs the coordinates of each hat, * because this way it can work by walking around its 8 kites using a * fixed set of steps, and if the hat is reflected, then we just * reflect the starting kite before doing that, and everything still * works. */ typedef struct Kite { Point centre, left, right, outer; } Kite; static inline Kite kite_left(Kite k) { Kite r; r.centre = k.centre; r.right = k.left; r.outer = pointadd(pointscale(2, k.left), pointscale(-1, k.outer)); r.left = pointadd(pointadd(k.centre, k.left), pointscale(-1, k.right)); return r; } static inline Kite kite_right(Kite k) { Kite r; r.centre = k.centre; r.left = k.right; r.outer = pointadd(pointscale(2, k.right), pointscale(-1, k.outer)); r.right = pointadd(pointadd(k.centre, k.right), pointscale(-1, k.left)); return r; } static inline Kite kite_forward_left(Kite k) { Kite r; r.outer = k.outer; r.right = k.left; r.centre = pointadd(pointscale(2, k.left), pointscale(-1, k.centre)); r.left = pointadd(pointadd(k.right, k.left), pointscale(-1, k.centre)); return r; } static inline Kite kite_forward_right(Kite k) { Kite r; r.outer = k.outer; r.left = k.right; r.centre = pointadd(pointscale(2, k.right), pointscale(-1, k.centre)); r.right = pointadd(pointadd(k.left, k.right), pointscale(-1, k.centre)); return r; } typedef enum KiteStep { KS_LEFT, KS_RIGHT, KS_F_LEFT, KS_F_RIGHT } KiteStep; static inline Kite kite_step(Kite 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); } } /* * Functiond to enumerate the kites in a rectangular region, in a * serpentine-raster fashion so that every kite delivered shares an * edge with a recent previous one. */ #define KE_NKEEP 3 typedef struct KiteEnum { /* Fields private to the enumerator */ int state; int x, y, w, h; unsigned curr_index; /* Fields the client can legitimately read out */ Kite *curr; Kite recent[KE_NKEEP]; unsigned last_index; KiteStep last_step; /* step that got curr from recent[last_index] */ } KiteEnum; void hat_kiteenum_first(KiteEnum *s, int w, int h); bool hat_kiteenum_next(KiteEnum *s); /* * Assorted useful definitions. */ typedef enum TileType { TT_H, TT_T, TT_P, TT_F, TT_KITE, TT_HAT } TileType; static const char tilechars[] = "HTPF"; #define HAT_KITES 8 /* number of kites in a hat */ #define MT_MAXEXPAND 13 /* largest number of metatiles in any expansion */ /* * Definitions for the autogenerated hat-tables.h header file that * defines all the lookup tables. */ typedef struct KitemapEntry { int kite, hat, meta; /* all -1 if impossible */ } KitemapEntry; typedef struct MetamapEntry { int meta, meta2; } MetamapEntry; static inline size_t kitemap_index(KiteStep step, unsigned kite, unsigned hat, unsigned meta) { return step + 4 * (kite + 8 * (hat + 4 * meta)); } static inline size_t metamap_index(unsigned meta, unsigned meta2) { return meta2 * MT_MAXEXPAND + meta; } /* * Coordinate system for tracking kites within a randomly selected * part of the recursively expanded hat tiling. * * HatCoords will store an array of HatCoord, in little-endian * arrangement. So hc->c[0] will always have type TT_KITE and index a * single kite within a hat; hc->c[1] will have type TT_HAT and index * a hat within a first-order metatile; hc->c[2] will be the smallest * metatile containing this hat, and hc->c[3, 4, 5, ...] will be * higher-order metatiles as needed. * * The last coordinate stored, hc->c[hc->nc-1], will have a tile type * but no index (represented by index==-1). This means "we haven't * decided yet what this level of metatile needs to be". If we need to * refer to this level during the hatctx_step algorithm, we make it up * at random, based on a table of what metatiles each type can * possibly be part of, at what index. */ typedef struct HatCoord { int index; /* index within that tile, or -1 if not yet known */ TileType type; /* type of this tile */ } HatCoord; typedef struct HatCoords { HatCoord *c; size_t nc, csize; } HatCoords; HatCoords *hat_coords_new(void); void hat_coords_free(HatCoords *hc); void hat_coords_make_space(HatCoords *hc, size_t size); HatCoords *hat_coords_copy(HatCoords *hc_in); #ifdef HAT_COORDS_DEBUG static inline void hat_coords_debug(const char *prefix, HatCoords *hc, const char *suffix) { const char *sep = ""; static const char *const types[] = {"H","T","P","F","kite","hat"}; fputs(prefix, stderr); for (size_t i = 0; i < hc->nc; i++) { fprintf(stderr, "%s %s ", sep, types[hc->c[i].type]); sep = " ."; if (hc->c[i].index == -1) fputs("?", stderr); else fprintf(stderr, "%d", hc->c[i].index); } fputs(suffix, stderr); } #else #define hat_coords_debug(p,c,s) ((void)0) #endif /* * HatContext is the shared context of a whole run of the algorithm. * Its 'prototype' HatCoords object represents the coordinates of the * starting kite, and is extended as necessary; any other HatCoord * that needs extending will copy the higher-order values from * ctx->prototype as needed, so that once each choice has been made, * it remains consistent. * * When we're inventing a random piece of tiling in the first place, * we append to ctx->prototype by choosing a random (but legal) * higher-level metatile for the current topmost one to turn out to be * part of. When we're replaying a generation whose parameters are * already stored, we don't have a random_state, and we make fixed * decisions if not enough coordinates were provided. * * (Of course another approach would be to reject grid descriptions * that didn't define enough coordinates! But that would involve a * whole extra iteration over the whole grid region just for * validation, and that seems like more timewasting than really * needed. So we tolerate short descriptions, and do something * deterministic with them.) */ typedef struct HatContext { random_state *rs; HatCoords *prototype; } HatContext; void hatctx_init_random(HatContext *ctx, random_state *rs); void hatctx_cleanup(HatContext *ctx); HatCoords *hatctx_initial_coords(HatContext *ctx); void hatctx_extend_coords(HatContext *ctx, HatCoords *hc, size_t n); HatCoords *hatctx_step(HatContext *ctx, HatCoords *hc_in, KiteStep step); /* * Subroutine of hat_tiling_generate, called for each kite in the grid * as we iterate over it, to decide whether to generate an output hat * and pass it to the client. Exposed in this header file so that * hat-test can reuse it. * * We do this by starting from kite #0 of each hat, and tracing round * the boundary. If the whole boundary is within the caller's bounding * region, we return it; if it goes off the edge, we don't. * * (Of course, every hat we _do_ want to return will have all its * kites inside the rectangle, so its kite #0 will certainly be caught * by this iteration.) */ typedef void (*internal_hat_callback_fn)(void *ctx, Kite kite0, HatCoords *hc, int *coords); void maybe_report_hat(int w, int h, Kite kite, HatCoords *hc, internal_hat_callback_fn cb, void *cbctx);