From 09aa8de52cb962f1ceebfb1fd44f2c54a924fc5c Mon Sep 17 00:00:00 2001 From: Franklin Wei Date: Mon, 22 Jul 2024 21:43:25 -0400 Subject: puzzles: resync with upstream This brings the puzzles source in sync with Simon's branch, commit fd304c5 (from March 2024), with some added Rockbox-specific compatibility changes: https://www.franklinwei.com/git/puzzles/commit/?h=rockbox-devel&id=516830d9d76bdfe64fe5ccf2a9b59c33f5c7c078 There are quite a lot of backend changes, including a new "Mosaic" puzzle. In addition, some new frontend changes were necessary: - New "Preferences" menu to access the user preferences system. - Enabled spacebar input for several games. Change-Id: I94c7df674089c92f32d5f07025f6a1059068af1e --- apps/plugins/puzzles/src/hat-internal.h | 271 ++++++++++++++++++++++++++++++++ 1 file changed, 271 insertions(+) create mode 100644 apps/plugins/puzzles/src/hat-internal.h (limited to 'apps/plugins/puzzles/src/hat-internal.h') diff --git a/apps/plugins/puzzles/src/hat-internal.h b/apps/plugins/puzzles/src/hat-internal.h new file mode 100644 index 0000000000..2be96327a8 --- /dev/null +++ b/apps/plugins/puzzles/src/hat-internal.h @@ -0,0 +1,271 @@ +/* + * 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); -- cgit v1.2.3