ref: dd0004fb5ebb581eced0820cd6373f88e98d93e3
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);