123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272 |
- /*
- * 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);
|