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/spectre-internal.h | 327 ++++++++++++++++++++++++++++ 1 file changed, 327 insertions(+) create mode 100644 apps/plugins/puzzles/src/spectre-internal.h (limited to 'apps/plugins/puzzles/src/spectre-internal.h') diff --git a/apps/plugins/puzzles/src/spectre-internal.h b/apps/plugins/puzzles/src/spectre-internal.h new file mode 100644 index 0000000000..e43d30bfef --- /dev/null +++ b/apps/plugins/puzzles/src/spectre-internal.h @@ -0,0 +1,327 @@ +#include "spectre.h" + +/* + * List macro of the names for hexagon types, which will be reused all + * over the place. + * + * (I have to call the parameter to this list macro something other + * than X, because here, X is also one of the macro arguments!) + */ +#define HEX_LETTERS(Z) Z(G) Z(D) Z(J) Z(L) Z(X) Z(P) Z(S) Z(F) Z(Y) + +typedef enum Hex { + #define HEX_ENUM_DECL(x) HEX_##x, + HEX_LETTERS(HEX_ENUM_DECL) + #undef HEX_ENUM_DECL +} Hex; + +static inline unsigned num_subhexes(Hex h) +{ + return h == HEX_G ? 7 : 8; +} + +static inline unsigned num_spectres(Hex h) +{ + return h == HEX_G ? 2 : 1; +} + +/* + * Data types used in the lookup tables. + */ +struct MapEntry { + bool internal; + unsigned char hi, lo; +}; +struct MapEdge { + unsigned char startindex, len; +}; +struct Possibility { + unsigned char hi, lo; + unsigned long prob; +}; + +/* + * Coordinate system for tracking Spectres and their hexagonal + * metatiles. + * + * SpectreCoords will store the index of a single Spectre within a + * smallest-size hexagon, plus an array of HexCoord each indexing a + * hexagon within the expansion of a larger hexagon. + * + * The last coordinate stored, sc->c[sc->nc-1], will have a hex 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 HexCoord { + int index; /* index within that tile, or -1 if not yet known */ + Hex type; /* type of this hexagon */ +} HexCoord; + +typedef struct SpectreCoords { + int index; /* index of Spectre within the order-0 hexagon */ + HexCoord *c; + size_t nc, csize; + + /* Used by spectre-test to four-colour output tilings, and + * maintained unconditionally because it's easier than making it + * conditional */ + unsigned char hex_colour, prev_hex_colour, incoming_hex_edge; +} SpectreCoords; + +SpectreCoords *spectre_coords_new(void); +void spectre_coords_free(SpectreCoords *hc); +void spectre_coords_make_space(SpectreCoords *hc, size_t size); +SpectreCoords *spectre_coords_copy(SpectreCoords *hc_in); + +/* + * Coordinate system for locating Spectres in the plane. + * + * The 'Point' structure represents a single point by means of an + * integer linear combination of {1, d, d^2, d^3}, where d is the + * complex number exp(i pi/6) representing 1/12 of a turn about the + * origin. + * + * The 'Spectre' structure represents an entire Spectre in a tiling, + * giving both the locations of all of its vertices and its + * combinatorial coordinates. It also contains a linked-list pointer, + * used during breadth-first search to generate all the Spectres in an + * area. + */ +typedef struct Point { + int coeffs[4]; +} Point; +typedef struct Spectre Spectre; +struct Spectre { + Point vertices[14]; + SpectreCoords *sc; + Spectre *next; /* used in breadth-first search */ +}; + +/* Fill in all the coordinates of a Spectre starting from any single edge */ +void spectre_place(Spectre *spec, Point u, Point v, int index_of_u); + +/* Free a Spectre and its contained coordinates */ +void spectre_free(Spectre *spec); + +/* + * A Point is really a complex number, so we can add, subtract and + * multiply them. + */ +static inline Point point_add(Point a, Point b) +{ + Point r; + size_t i; + for (i = 0; i < 4; i++) + r.coeffs[i] = a.coeffs[i] + b.coeffs[i]; + return r; +} +static inline Point point_sub(Point a, Point b) +{ + Point r; + size_t i; + for (i = 0; i < 4; i++) + r.coeffs[i] = a.coeffs[i] - b.coeffs[i]; + return r; +} +static inline Point point_mul_by_d(Point x) +{ + Point r; + /* Multiply by d by using the identity d^4 - d^2 + 1 = 0, so d^4 = d^2+1 */ + r.coeffs[0] = -x.coeffs[3]; + r.coeffs[1] = x.coeffs[0]; + r.coeffs[2] = x.coeffs[1] + x.coeffs[3]; + r.coeffs[3] = x.coeffs[2]; + return r; +} +static inline Point point_mul(Point a, Point b) +{ + size_t i, j; + Point r; + + /* Initialise r to be a, scaled by b's d^3 term */ + for (j = 0; j < 4; j++) + r.coeffs[j] = a.coeffs[j] * b.coeffs[3]; + + /* Now iterate r = d*r + (next coefficient down), by Horner's rule */ + for (i = 3; i-- > 0 ;) { + r = point_mul_by_d(r); + for (j = 0; j < 4; j++) + r.coeffs[j] += a.coeffs[j] * b.coeffs[i]; + } + + return r; +} +static inline bool point_equal(Point a, Point b) +{ + size_t i; + for (i = 0; i < 4; i++) + if (a.coeffs[i] != b.coeffs[i]) + return false; + return true; +} + +/* + * Return the Point corresponding to a rotation of s steps around the + * origin, i.e. a rotation by 30*s degrees or s*pi/6 radians. + */ +static inline Point point_rot(int s) +{ + Point r = {{ 1, 0, 0, 0 }}; + Point dpower = {{ 0, 1, 0, 0 }}; + + /* Reduce to a sensible range */ + s = s % 12; + if (s < 0) + s += 12; + + while (true) { + if (s & 1) + r = point_mul(r, dpower); + s >>= 1; + if (!s) + break; + dpower = point_mul(dpower, dpower); + } + + return r; +} + +/* + * SpectreContext is the shared context of a whole run of the + * algorithm. Its 'prototype' SpectreCoords object represents the + * coordinates of the starting Spectre, and is extended as necessary; + * any other SpectreCoord 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, as in the + * corresponding hat.c system. + * + * For a normal (non-testing) caller, spectrectx_generate() is the + * main useful function. It breadth-first searches a whole area to + * generate all the Spectres in it, starting from a (typically + * central) one with the coordinates of ctx->prototype. The callback + * function processes each Spectre as it's generated, and returns true + * or false to indicate whether that Spectre is within the bounds of + * the target area (and therefore the search should continue exploring + * its neighbours). + */ +typedef struct SpectreContext { + random_state *rs; + bool must_free_rs; + Point start_vertices[2]; /* vertices 0,1 of the starting Spectre */ + int orientation; /* orientation to put in SpectrePatchParams */ + SpectreCoords *prototype; +} SpectreContext; + +void spectrectx_init_random(SpectreContext *ctx, random_state *rs); +void spectrectx_init_from_params( + SpectreContext *ctx, const struct SpectrePatchParams *ps); +void spectrectx_cleanup(SpectreContext *ctx); +SpectreCoords *spectrectx_initial_coords(SpectreContext *ctx); +void spectrectx_extend_coords(SpectreContext *ctx, SpectreCoords *hc, + size_t n); +void spectrectx_step(SpectreContext *ctx, SpectreCoords *sc, + unsigned edge, unsigned *outedge); +void spectrectx_generate(SpectreContext *ctx, + bool (*callback)(void *cbctx, const Spectre *spec), + void *cbctx); + +/* For spectre-test to directly generate a tiling of hexes */ +void spectrectx_step_hex(SpectreContext *ctx, SpectreCoords *sc, + size_t depth, unsigned edge, unsigned *outedge); + +/* Subroutines that step around the tiling specified by a SpectreCtx, + * delivering both plane and combinatorial coordinates as they go */ +Spectre *spectre_initial(SpectreContext *ctx); +Spectre *spectre_adjacent(SpectreContext *ctx, const Spectre *src_spec, + unsigned src_edge, unsigned *dst_edge); + +/* For extracting the point coordinates */ +typedef struct Coord { + int c1, cr3; /* coefficients of 1 and sqrt(3) respectively */ +} Coord; + +static inline Coord point_x(Point p) +{ + Coord x = { 2 * p.coeffs[0] + p.coeffs[2], p.coeffs[1] }; + return x; +} + +static inline Coord point_y(Point p) +{ + Coord y = { 2 * p.coeffs[3] + p.coeffs[1], p.coeffs[2] }; + return y; +} + +static inline int coord_sign(Coord x) +{ + if (x.c1 == 0 && x.cr3 == 0) + return 0; + if (x.c1 >= 0 && x.cr3 >= 0) + return +1; + if (x.c1 <= 0 && x.cr3 <= 0) + return -1; + + if (x.c1 * x.c1 > 3 * x.cr3 * x.cr3) + return x.c1 < 0 ? -1 : +1; + else + return x.cr3 < 0 ? -1 : +1; +} + +static inline Coord coord_construct(int c1, int cr3) +{ + Coord c = { c1, cr3 }; + return c; +} + +static inline Coord coord_integer(int c1) +{ + return coord_construct(c1, 0); +} + +static inline Coord coord_add(Coord a, Coord b) +{ + Coord sum; + sum.c1 = a.c1 + b.c1; + sum.cr3 = a.cr3 + b.cr3; + return sum; +} + +static inline Coord coord_sub(Coord a, Coord b) +{ + Coord diff; + diff.c1 = a.c1 - b.c1; + diff.cr3 = a.cr3 - b.cr3; + return diff; +} + +static inline Coord coord_mul(Coord a, Coord b) +{ + Coord prod; + prod.c1 = a.c1 * b.c1 + 3 * a.cr3 * b.cr3; + prod.cr3 = a.c1 * b.cr3 + a.cr3 * b.c1; + return prod; +} + +static inline Coord coord_abs(Coord a) +{ + int sign = coord_sign(a); + Coord abs; + abs.c1 = a.c1 * sign; + abs.cr3 = a.cr3 * sign; + return abs; +} + +static inline int coord_cmp(Coord a, Coord b) +{ + return coord_sign(coord_sub(a, b)); +} -- cgit v1.2.3