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/penrose.c | 1271 ++++++++++++++++++++++-------------- 1 file changed, 768 insertions(+), 503 deletions(-) (limited to 'apps/plugins/puzzles/src/penrose.c') diff --git a/apps/plugins/puzzles/src/penrose.c b/apps/plugins/puzzles/src/penrose.c index ccde30d8b4..4d7dcc4347 100644 --- a/apps/plugins/puzzles/src/penrose.c +++ b/apps/plugins/puzzles/src/penrose.c @@ -1,629 +1,894 @@ -/* penrose.c - * - * Penrose tile generator. +/* + * Generate Penrose tilings via combinatorial coordinates. * - * Uses half-tile technique outlined on: + * For general explanation of the algorithm: + * https://www.chiark.greenend.org.uk/~sgtatham/quasiblog/aperiodic-tilings/ * - * http://tartarus.org/simon/20110412-penrose/penrose.xhtml + * I use exactly the same indexing system here that's described in the + * article. For the P2 tiling, acute isosceles triangles (half-kites) + * are assigned letters A,B, and obtuse ones (half-darts) U,V; for P3, + * acute triangles (half of a thin rhomb) are C,D and obtuse ones + * (half a thick rhomb) are X,Y. Edges of all triangles are indexed + * anticlockwise around the triangle, with 0 being the base and 1,2 + * being the two equal legs. */ #include +#include #include -#include -#include -#include "puzzles.h" /* for malloc routines, and PI */ +#include "puzzles.h" #include "penrose.h" +#include "penrose-internal.h" +#include "tree234.h" -/* ------------------------------------------------------- - * 36-degree basis vector arithmetic routines. - */ +bool penrose_valid_letter(char c, int which) +{ + switch (c) { + case 'A': case 'B': case 'U': case 'V': + return which == PENROSE_P2; + case 'C': case 'D': case 'X': case 'Y': + return which == PENROSE_P3; + default: + return false; + } +} -/* Imagine drawing a - * ten-point 'clock face' like this: - * - * -E - * -D | A - * \ | / - * -C. \ | / ,B - * `-._\|/_,-' - * ,-' /|\ `-. - * -B' / | \ `C - * / | \ - * -A | D - * E - * - * In case the ASCII art isn't clear, those are supposed to be ten - * vectors of length 1, all sticking out from the origin at equal - * angular spacing (hence 36 degrees). Our basis vectors are A,B,C,D (I - * choose them to be symmetric about the x-axis so that the final - * translation into 2d coordinates will also be symmetric, which I - * think will avoid minor rounding uglinesses), so our vector - * representation sets - * - * A = (1,0,0,0) - * B = (0,1,0,0) - * C = (0,0,1,0) - * D = (0,0,0,1) - * - * The fifth vector E looks at first glance as if it needs to be - * another basis vector, but in fact it doesn't, because it can be - * represented in terms of the other four. Imagine starting from the - * origin and following the path -A, +B, -C, +D: you'll find you've - * traced four sides of a pentagram, and ended up one E-vector away - * from the origin. So we have - * - * E = (-1,1,-1,1) - * - * This tells us that we can rotate any vector in this system by 36 - * degrees: if we start with a*A + b*B + c*C + d*D, we want to end up - * with a*B + b*C + c*D + d*E, and we substitute our identity for E to - * turn that into a*B + b*C + c*D + d*(-A+B-C+D). In other words, - * - * rotate_one_notch_clockwise(a,b,c,d) = (-d, d+a, -d+b, d+c) - * - * and you can verify for yourself that applying that operation - * repeatedly starting with (1,0,0,0) cycles round ten vectors and - * comes back to where it started. - * - * The other operation that may be required is to construct vectors - * with lengths that are multiples of phi. That can be done by - * observing that the vector C-B is parallel to E and has length 1/phi, - * and the vector D-A is parallel to E and has length phi. So this - * tells us that given any vector, we can construct one which points in - * the same direction and is 1/phi or phi times its length, like this: - * - * divide_by_phi(vector) = rotate(vector, 2) - rotate(vector, 3) - * multiply_by_phi(vector) = rotate(vector, 1) - rotate(vector, 4) - * - * where rotate(vector, n) means applying the above - * rotate_one_notch_clockwise primitive n times. Expanding out the - * applications of rotate gives the following direct representation in - * terms of the vector coordinates: - * - * divide_by_phi(a,b,c,d) = (b-d, c+d-b, a+b-c, c-a) - * multiply_by_phi(a,b,c,d) = (a+b-d, c+d, a+b, c+d-a) - * - * and you can verify for yourself that those two operations are - * inverses of each other (as you'd hope!). +/* + * Result of attempting a transition within the coordinate system. + * INTERNAL means we've moved to a different child of the same parent, + * so the 'internal' substructure gives the type of the new triangle + * and which edge of it we came in through; EXTERNAL means we've moved + * out of the parent entirely, and the 'external' substructure tells + * us which edge of the parent triangle we left by, and if it's + * divided in two, which end of that edge (-1 for the left end or +1 + * for the right end). If the parent edge is undivided, end == 0. * - * Having done all of this, testing for equality between two vectors is - * a trivial matter of comparing the four integer coordinates. (Which - * it _wouldn't_ have been if we'd kept E as a fifth basis vector, - * because then (-1,1,-1,1,0) and (0,0,0,0,1) would have had to be - * considered identical. So leaving E out is vital.) + * The type FAIL _shouldn't_ ever come up! It occurs if you try to + * compute an incoming transition with an illegal value of 'end' (i.e. + * having the wrong idea of whether the edge is divided), or if you + * refer to a child triangle type that doesn't exist in that parent. + * If it ever happens in the production code then an assertion will + * fail. But it might be useful to other users of the same code. */ - -struct vector { int a, b, c, d; }; - -static vector v_origin(void) +typedef struct TransitionResult { + enum { INTERNAL, EXTERNAL, FAIL } type; + union { + struct { + char new_child; + unsigned char new_edge; + } internal; + struct { + unsigned char parent_edge; + signed char end; + } external; + } u; +} TransitionResult; + +/* Construction function to make an INTERNAL-type TransitionResult */ +static inline TransitionResult internal(char new_child, unsigned new_edge) { - vector v; - v.a = v.b = v.c = v.d = 0; - return v; + TransitionResult tr; + tr.type = INTERNAL; + tr.u.internal.new_child = new_child; + tr.u.internal.new_edge = new_edge; + return tr; } -/* We start with a unit vector of B: this means we can easily - * draw an isoceles triangle centred on the X axis. */ -#ifdef TEST_VECTORS +/* Construction function to make an EXTERNAL-type TransitionResult */ +static inline TransitionResult external(unsigned parent_edge, int end) +{ + TransitionResult tr; + tr.type = EXTERNAL; + tr.u.external.parent_edge = parent_edge; + tr.u.external.end = end; + return tr; +} -static vector v_unit(void) +/* Construction function to make a FAIL-type TransitionResult */ +static inline TransitionResult fail(void) { - vector v; + TransitionResult tr; + tr.type = FAIL; + return tr; +} - v.b = 1; - v.a = v.c = v.d = 0; - return v; +/* + * Compute a transition out of a triangle. Can return either INTERNAL + * or EXTERNAL types (or FAIL if it gets invalid data). + */ +static TransitionResult transition(char parent, char child, unsigned edge) +{ + switch (parent) { + case 'A': + switch (child) { + case 'A': + switch (edge) { + case 0: return external(2, -1); + case 1: return external(0, 0); + case 2: return internal('B', 1); + } + case 'B': + switch (edge) { + case 0: return internal('U', 1); + case 1: return internal('A', 2); + case 2: return external(1, +1); + } + case 'U': + switch (edge) { + case 0: return external(2, +1); + case 1: return internal('B', 0); + case 2: return external(1, -1); + } + default: + return fail(); + } + case 'B': + switch (child) { + case 'A': + switch (edge) { + case 0: return internal('V', 2); + case 1: return external(2, -1); + case 2: return internal('B', 1); + } + case 'B': + switch (edge) { + case 0: return external(1, +1); + case 1: return internal('A', 2); + case 2: return external(0, 0); + } + case 'V': + switch (edge) { + case 0: return external(1, -1); + case 1: return external(2, +1); + case 2: return internal('A', 0); + } + default: + return fail(); + } + case 'U': + switch (child) { + case 'B': + switch (edge) { + case 0: return internal('U', 1); + case 1: return external(2, 0); + case 2: return external(0, +1); + } + case 'U': + switch (edge) { + case 0: return external(1, 0); + case 1: return internal('B', 0); + case 2: return external(0, -1); + } + default: + return fail(); + } + case 'V': + switch (child) { + case 'A': + switch (edge) { + case 0: return internal('V', 2); + case 1: return external(0, -1); + case 2: return external(1, 0); + } + case 'V': + switch (edge) { + case 0: return external(2, 0); + case 1: return external(0, +1); + case 2: return internal('A', 0); + } + default: + return fail(); + } + case 'C': + switch (child) { + case 'C': + switch (edge) { + case 0: return external(1, +1); + case 1: return internal('Y', 1); + case 2: return external(0, 0); + } + case 'Y': + switch (edge) { + case 0: return external(2, 0); + case 1: return internal('C', 1); + case 2: return external(1, -1); + } + default: + return fail(); + } + case 'D': + switch (child) { + case 'D': + switch (edge) { + case 0: return external(2, -1); + case 1: return external(0, 0); + case 2: return internal('X', 2); + } + case 'X': + switch (edge) { + case 0: return external(1, 0); + case 1: return external(2, +1); + case 2: return internal('D', 2); + } + default: + return fail(); + } + case 'X': + switch (child) { + case 'C': + switch (edge) { + case 0: return external(2, +1); + case 1: return internal('Y', 1); + case 2: return internal('X', 1); + } + case 'X': + switch (edge) { + case 0: return external(1, 0); + case 1: return internal('C', 2); + case 2: return external(0, -1); + } + case 'Y': + switch (edge) { + case 0: return external(0, +1); + case 1: return internal('C', 1); + case 2: return external(2, -1); + } + default: + return fail(); + } + case 'Y': + switch (child) { + case 'D': + switch (edge) { + case 0: return external(1, -1); + case 1: return internal('Y', 2); + case 2: return internal('X', 2); + } + case 'X': + switch (edge) { + case 0: return external(0, -1); + case 1: return external(1, +1); + case 2: return internal('D', 2); + } + case 'Y': + switch (edge) { + case 0: return external(2, 0); + case 1: return external(0, +1); + case 2: return internal('D', 1); + } + default: + return fail(); + } + default: + return fail(); + } } -#endif +/* + * Compute a transition into a parent triangle, after the above + * function reported an EXTERNAL transition out of a neighbouring + * parent and we had to recurse. Because we're coming inwards, this + * should always return an INTERNAL TransitionResult (or FAIL if it + * gets invalid data). + */ +static TransitionResult transition_in(char parent, unsigned edge, int end) +{ + #define EDGEEND(edge, end) (3 * (edge) + 1 + (end)) + + switch (parent) { + case 'A': + switch (EDGEEND(edge, end)) { + case EDGEEND(0, 0): return internal('A', 1); + case EDGEEND(1, -1): return internal('B', 2); + case EDGEEND(1, +1): return internal('U', 2); + case EDGEEND(2, -1): return internal('U', 0); + case EDGEEND(2, +1): return internal('A', 0); + default: + return fail(); + } + case 'B': + switch (EDGEEND(edge, end)) { + case EDGEEND(0, 0): return internal('B', 2); + case EDGEEND(1, -1): return internal('B', 0); + case EDGEEND(1, +1): return internal('V', 0); + case EDGEEND(2, -1): return internal('V', 1); + case EDGEEND(2, +1): return internal('A', 1); + default: + return fail(); + } + case 'U': + switch (EDGEEND(edge, end)) { + case EDGEEND(0, -1): return internal('B', 2); + case EDGEEND(0, +1): return internal('U', 2); + case EDGEEND(1, 0): return internal('U', 0); + case EDGEEND(2, 0): return internal('B', 1); + default: + return fail(); + } + case 'V': + switch (EDGEEND(edge, end)) { + case EDGEEND(0, -1): return internal('V', 1); + case EDGEEND(0, +1): return internal('A', 1); + case EDGEEND(1, 0): return internal('A', 2); + case EDGEEND(2, 0): return internal('V', 0); + default: + return fail(); + } + case 'C': + switch (EDGEEND(edge, end)) { + case EDGEEND(0, 0): return internal('C', 2); + case EDGEEND(1, -1): return internal('C', 0); + case EDGEEND(1, +1): return internal('Y', 2); + case EDGEEND(2, 0): return internal('Y', 0); + default: + return fail(); + } + case 'D': + switch (EDGEEND(edge, end)) { + case EDGEEND(0, 0): return internal('D', 1); + case EDGEEND(1, 0): return internal('X', 0); + case EDGEEND(2, -1): return internal('X', 1); + case EDGEEND(2, +1): return internal('D', 0); + default: + return fail(); + } + case 'X': + switch (EDGEEND(edge, end)) { + case EDGEEND(0, -1): return internal('Y', 0); + case EDGEEND(0, +1): return internal('X', 2); + case EDGEEND(1, 0): return internal('X', 0); + case EDGEEND(2, -1): return internal('C', 0); + case EDGEEND(2, +1): return internal('Y', 2); + default: + return fail(); + } + case 'Y': + switch (EDGEEND(edge, end)) { + case EDGEEND(0, +1): return internal('X', 0); + case EDGEEND(0, -1): return internal('Y', 1); + case EDGEEND(1, -1): return internal('X', 1); + case EDGEEND(1, +1): return internal('D', 0); + case EDGEEND(2, 0): return internal('Y', 0); + default: + return fail(); + } + default: + return fail(); + } -#define COS54 0.5877852 -#define SIN54 0.8090169 -#define COS18 0.9510565 -#define SIN18 0.3090169 + #undef EDGEEND +} -/* These two are a bit rough-and-ready for now. Note that B/C are - * 18 degrees from the x-axis, and A/D are 54 degrees. */ -double v_x(vector *vs, int i) +PenroseCoords *penrose_coords_new(void) { - return (vs[i].a + vs[i].d) * COS54 + - (vs[i].b + vs[i].c) * COS18; + PenroseCoords *pc = snew(PenroseCoords); + pc->nc = pc->csize = 0; + pc->c = NULL; + return pc; } -double v_y(vector *vs, int i) +void penrose_coords_free(PenroseCoords *pc) { - return (vs[i].a - vs[i].d) * SIN54 + - (vs[i].b - vs[i].c) * SIN18; - + if (pc) { + sfree(pc->c); + sfree(pc); + } } -static vector v_trans(vector v, vector trans) +void penrose_coords_make_space(PenroseCoords *pc, size_t size) { - v.a += trans.a; - v.b += trans.b; - v.c += trans.c; - v.d += trans.d; - return v; + if (pc->csize < size) { + pc->csize = pc->csize * 5 / 4 + 16; + if (pc->csize < size) + pc->csize = size; + pc->c = sresize(pc->c, pc->csize, char); + } } -static vector v_rotate_36(vector v) +PenroseCoords *penrose_coords_copy(PenroseCoords *pc_in) { - vector vv; - vv.a = -v.d; - vv.b = v.d + v.a; - vv.c = -v.d + v.b; - vv.d = v.d + v.c; - return vv; + PenroseCoords *pc_out = penrose_coords_new(); + penrose_coords_make_space(pc_out, pc_in->nc); + memcpy(pc_out->c, pc_in->c, pc_in->nc * sizeof(*pc_out->c)); + pc_out->nc = pc_in->nc; + return pc_out; } -static vector v_rotate(vector v, int ang) +/* + * The main recursive function for computing the next triangle's + * combinatorial coordinates. + */ +static void penrosectx_step_recurse( + PenroseContext *ctx, PenroseCoords *pc, size_t depth, + unsigned edge, unsigned *outedge) { - int i; + TransitionResult tr; + + penrosectx_extend_coords(ctx, pc, depth+2); + + /* Look up the transition out of the starting triangle */ + tr = transition(pc->c[depth+1], pc->c[depth], edge); + + /* If we've left the parent triangle, recurse to find out what new + * triangle we've landed in at the next size up, and then call + * transition_in to find out which child of that parent we're + * going to */ + if (tr.type == EXTERNAL) { + unsigned parent_outedge; + penrosectx_step_recurse( + ctx, pc, depth+1, tr.u.external.parent_edge, &parent_outedge); + tr = transition_in(pc->c[depth+1], parent_outedge, tr.u.external.end); + } - assert((ang % 36) == 0); - while (ang < 0) ang += 360; - ang = 360-ang; - for (i = 0; i < (ang/36); i++) - v = v_rotate_36(v); - return v; + /* Now we should definitely have ended up in a child of the + * (perhaps rewritten) parent triangle */ + assert(tr.type == INTERNAL); + pc->c[depth] = tr.u.internal.new_child; + *outedge = tr.u.internal.new_edge; } -#ifdef TEST_VECTORS - -static vector v_scale(vector v, int sc) +void penrosectx_step(PenroseContext *ctx, PenroseCoords *pc, + unsigned edge, unsigned *outedge) { - v.a *= sc; - v.b *= sc; - v.c *= sc; - v.d *= sc; - return v; -} + /* Allow outedge to be NULL harmlessly, just in case */ + unsigned dummy_outedge; + if (!outedge) + outedge = &dummy_outedge; -#endif + penrosectx_step_recurse(ctx, pc, 0, edge, outedge); +} -static vector v_growphi(vector v) +static Point penrose_triangle_post_edge(char c, unsigned edge) { - vector vv; - vv.a = v.a + v.b - v.d; - vv.b = v.c + v.d; - vv.c = v.a + v.b; - vv.d = v.c + v.d - v.a; - return vv; + static const Point acute_post_edge[3] = { + {{-1, 1, 0, 1}}, /* phi * t^3 */ + {{-1, 1, -1, 1}}, /* t^4 */ + {{-1, 1, 0, 0}}, /* 1/phi * t^3 */ + }; + static const Point obtuse_post_edge[3] = { + {{0, -1, 1, 0}}, /* 1/phi * t^4 */ + {{0, 0, 1, 0}}, /* t^2 */ + {{-1, 0, 0, 1}}, /* phi * t^4 */ + }; + + switch (c) { + case 'A': case 'B': case 'C': case 'D': + return acute_post_edge[edge]; + default: /* case 'U': case 'V': case 'X': case 'Y': */ + return obtuse_post_edge[edge]; + } } -static vector v_shrinkphi(vector v) +void penrose_place(PenroseTriangle *tri, Point u, Point v, int index_of_u) { - vector vv; - vv.a = v.b - v.d; - vv.b = v.c + v.d - v.b; - vv.c = v.a + v.b - v.c; - vv.d = v.c - v.a; - return vv; + unsigned i; + Point here = u, delta = point_sub(v, u); + + for (i = 0; i < 3; i++) { + unsigned edge = (index_of_u + i) % 3; + tri->vertices[edge] = here; + here = point_add(here, delta); + delta = point_mul(delta, penrose_triangle_post_edge( + tri->pc->c[0], edge)); + } } -#ifdef TEST_VECTORS - -static const char *v_debug(vector v) +void penrose_free(PenroseTriangle *tri) { - static char buf[255]; - sprintf(buf, - "(%d,%d,%d,%d)[%2.2f,%2.2f]", - v.a, v.b, v.c, v.d, v_x(&v,0), v_y(&v,0)); - return buf; + penrose_coords_free(tri->pc); + sfree(tri); } -#endif - -/* ------------------------------------------------------- - * Tiling routines. - */ - -static vector xform_coord(vector vo, int shrink, vector vtrans, int ang) +static bool penrose_relative_probability(char c) { - if (shrink < 0) - vo = v_shrinkphi(vo); - else if (shrink > 0) - vo = v_growphi(vo); - - vo = v_rotate(vo, ang); - vo = v_trans(vo, vtrans); - - return vo; + /* Penrose tile probability ratios are always phi, so we can + * approximate that very well using two consecutive Fibonacci + * numbers */ + switch (c) { + case 'A': case 'B': case 'X': case 'Y': + return 165580141; + case 'C': case 'D': case 'U': case 'V': + return 102334155; + default: + return 0; + } } - -#define XFORM(n,o,s,a) vs[(n)] = xform_coord(v_edge, (s), vs[(o)], (a)) - -static int penrose_p2_small(penrose_state *state, int depth, int flip, - vector v_orig, vector v_edge); - -static int penrose_p2_large(penrose_state *state, int depth, int flip, - vector v_orig, vector v_edge) +static char penrose_choose_random(const char *possibilities, random_state *rs) { - vector vv_orig, vv_edge; - -#ifdef DEBUG_PENROSE - { - vector vs[3]; - vs[0] = v_orig; - XFORM(1, 0, 0, 0); - XFORM(2, 0, 0, -36*flip); - - state->new_tile(state, vs, 3, depth); + const char *p; + unsigned long value, limit = 0; + + for (p = possibilities; *p; p++) + limit += penrose_relative_probability(*p); + value = random_upto(rs, limit); + for (p = possibilities; *p; p++) { + unsigned long curr = penrose_relative_probability(*p); + if (value < curr) + return *p; + value -= curr; } -#endif - - if (flip > 0) { - vector vs[4]; + assert(false && "Probability overflow!"); + return possibilities[0]; +} - vs[0] = v_orig; - XFORM(1, 0, 0, -36); - XFORM(2, 0, 0, 0); - XFORM(3, 0, 0, 36); +static const char *penrose_starting_tiles(int which) +{ + return which == PENROSE_P2 ? "ABUV" : "CDXY"; +} - state->new_tile(state, vs, 4, depth); +static const char *penrose_valid_parents(char tile) +{ + switch (tile) { + case 'A': return "ABV"; + case 'B': return "ABU"; + case 'U': return "AU"; + case 'V': return "BV"; + case 'C': return "CX"; + case 'D': return "DY"; + case 'X': return "DXY"; + case 'Y': return "CXY"; + default: return NULL; } - if (depth >= state->max_depth) return 0; - - vv_orig = v_trans(v_orig, v_rotate(v_edge, -36*flip)); - vv_edge = v_rotate(v_edge, 108*flip); - - penrose_p2_small(state, depth+1, flip, - v_orig, v_shrinkphi(v_edge)); +} - penrose_p2_large(state, depth+1, flip, - vv_orig, v_shrinkphi(vv_edge)); - penrose_p2_large(state, depth+1, -flip, - vv_orig, v_shrinkphi(vv_edge)); +void penrosectx_init_random(PenroseContext *ctx, random_state *rs, int which) +{ + ctx->rs = rs; + ctx->must_free_rs = false; + ctx->prototype = penrose_coords_new(); + penrose_coords_make_space(ctx->prototype, 1); + ctx->prototype->c[0] = penrose_choose_random( + penrose_starting_tiles(which), rs); + ctx->prototype->nc = 1; + ctx->start_vertex = random_upto(rs, 3); + ctx->orientation = random_upto(rs, 10); +} - return 0; +void penrosectx_init_from_params( + PenroseContext *ctx, const struct PenrosePatchParams *ps) +{ + size_t i; + + ctx->rs = NULL; + ctx->must_free_rs = false; + ctx->prototype = penrose_coords_new(); + penrose_coords_make_space(ctx->prototype, ps->ncoords); + for (i = 0; i < ps->ncoords; i++) + ctx->prototype->c[i] = ps->coords[i]; + ctx->prototype->nc = ps->ncoords; + ctx->start_vertex = ps->start_vertex; + ctx->orientation = ps->orientation; } -static int penrose_p2_small(penrose_state *state, int depth, int flip, - vector v_orig, vector v_edge) +void penrosectx_cleanup(PenroseContext *ctx) { - vector vv_orig; + if (ctx->must_free_rs) + random_free(ctx->rs); + penrose_coords_free(ctx->prototype); +} -#ifdef DEBUG_PENROSE - { - vector vs[3]; - vs[0] = v_orig; - XFORM(1, 0, 0, 0); - XFORM(2, 0, -1, -36*flip); +PenroseCoords *penrosectx_initial_coords(PenroseContext *ctx) +{ + return penrose_coords_copy(ctx->prototype); +} - state->new_tile(state, vs, 3, depth); +void penrosectx_extend_coords(PenroseContext *ctx, PenroseCoords *pc, + size_t n) +{ + if (ctx->prototype->nc < n) { + penrose_coords_make_space(ctx->prototype, n); + while (ctx->prototype->nc < n) { + if (!ctx->rs) { + /* + * For safety, similarly to spectre.c, we respond to a + * lack of available random_state by making a + * deterministic one. + */ + ctx->rs = random_new("dummy", 5); + ctx->must_free_rs = true; + } + + ctx->prototype->c[ctx->prototype->nc] = penrose_choose_random( + penrose_valid_parents(ctx->prototype->c[ctx->prototype->nc-1]), + ctx->rs); + ctx->prototype->nc++; + } } -#endif - - if (flip > 0) { - vector vs[4]; - - vs[0] = v_orig; - XFORM(1, 0, 0, -72); - XFORM(2, 0, -1, -36); - XFORM(3, 0, 0, 0); - state->new_tile(state, vs, 4, depth); + penrose_coords_make_space(pc, n); + while (pc->nc < n) { + pc->c[pc->nc] = ctx->prototype->c[pc->nc]; + pc->nc++; } - - if (depth >= state->max_depth) return 0; - - vv_orig = v_trans(v_orig, v_edge); - - penrose_p2_large(state, depth+1, -flip, - v_orig, v_shrinkphi(v_rotate(v_edge, -36*flip))); - - penrose_p2_small(state, depth+1, flip, - vv_orig, v_shrinkphi(v_rotate(v_edge, -144*flip))); - - return 0; } -static int penrose_p3_small(penrose_state *state, int depth, int flip, - vector v_orig, vector v_edge); - -static int penrose_p3_large(penrose_state *state, int depth, int flip, - vector v_orig, vector v_edge) +static Point penrose_triangle_edge_0_length(char c) { - vector vv_orig; - -#ifdef DEBUG_PENROSE - { - vector vs[3]; - vs[0] = v_orig; - XFORM(1, 0, 1, 0); - XFORM(2, 0, 0, -36*flip); - - state->new_tile(state, vs, 3, depth); + static const Point one = {{ 1, 0, 0, 0 }}; + static const Point phi = {{ 1, 0, 1, -1 }}; + static const Point invphi = {{ 0, 0, 1, -1 }}; + + switch (c) { + /* P2 tiling: unit-length edges are the long edges, i.e. edges + * 1,2 of AB and edge 0 of UV. So AB have edge 0 short. */ + case 'A': case 'B': + return invphi; + case 'U': case 'V': + return one; + + /* P3 tiling: unit-length edges are edges 1,2 of everything, + * so CD have edge 0 short and XY have it long. */ + case 'C': case 'D': + return invphi; + default: /* case 'X': case 'Y': */ + return phi; } -#endif +} - if (flip > 0) { - vector vs[4]; +PenroseTriangle *penrose_initial(PenroseContext *ctx) +{ + char type = ctx->prototype->c[0]; + Point origin = {{ 0, 0, 0, 0 }}; + Point edge0 = penrose_triangle_edge_0_length(type); + Point negoffset; + size_t i; + PenroseTriangle *tri = snew(PenroseTriangle); + + /* Orient the triangle by deciding what vector edge #0 should traverse */ + edge0 = point_mul(edge0, point_rot(ctx->orientation)); + + /* Place the triangle at an arbitrary position, in that orientation */ + tri->pc = penrose_coords_copy(ctx->prototype); + penrose_place(tri, origin, edge0, 0); + + /* Now translate so that the appropriate vertex is at the origin */ + negoffset = tri->vertices[ctx->start_vertex]; + for (i = 0; i < 3; i++) + tri->vertices[i] = point_sub(tri->vertices[i], negoffset); + + return tri; +} - vs[0] = v_orig; - XFORM(1, 0, 0, -36); - XFORM(2, 0, 1, 0); - XFORM(3, 0, 0, 36); +PenroseTriangle *penrose_adjacent(PenroseContext *ctx, + const PenroseTriangle *src_tri, + unsigned src_edge, unsigned *dst_edge_out) +{ + unsigned dst_edge; + PenroseTriangle *dst_tri = snew(PenroseTriangle); + dst_tri->pc = penrose_coords_copy(src_tri->pc); + penrosectx_step(ctx, dst_tri->pc, src_edge, &dst_edge); + penrose_place(dst_tri, src_tri->vertices[(src_edge+1) % 3], + src_tri->vertices[src_edge], dst_edge); + if (dst_edge_out) + *dst_edge_out = dst_edge; + return dst_tri; +} - state->new_tile(state, vs, 4, depth); +static int penrose_cmp(void *av, void *bv) +{ + PenroseTriangle *a = (PenroseTriangle *)av, *b = (PenroseTriangle *)bv; + size_t i, j; + + /* We should only ever need to compare the first two vertices of + * any triangle, because those force the rest */ + for (i = 0; i < 2; i++) { + for (j = 0; j < 4; j++) { + int ac = a->vertices[i].coeffs[j], bc = b->vertices[i].coeffs[j]; + if (ac < bc) + return -1; + if (ac > bc) + return +1; + } } - if (depth >= state->max_depth) return 0; - - vv_orig = v_trans(v_orig, v_edge); - - penrose_p3_large(state, depth+1, -flip, - vv_orig, v_shrinkphi(v_rotate(v_edge, 180))); - - penrose_p3_small(state, depth+1, flip, - vv_orig, v_shrinkphi(v_rotate(v_edge, -108*flip))); - - vv_orig = v_trans(v_orig, v_growphi(v_edge)); - - penrose_p3_large(state, depth+1, flip, - vv_orig, v_shrinkphi(v_rotate(v_edge, -144*flip))); - return 0; } -static int penrose_p3_small(penrose_state *state, int depth, int flip, - vector v_orig, vector v_edge) +static unsigned penrose_sibling_edge_index(char c) { - vector vv_orig; - -#ifdef DEBUG_PENROSE - { - vector vs[3]; - vs[0] = v_orig; - XFORM(1, 0, 0, 0); - XFORM(2, 0, 0, -36*flip); - - state->new_tile(state, vs, 3, depth); + switch (c) { + case 'A': case 'U': return 2; + case 'B': case 'V': return 1; + default: return 0; } -#endif - - if (flip > 0) { - vector vs[4]; - - vs[0] = v_orig; - XFORM(1, 0, 0, -36); - XFORM(3, 0, 0, 0); - XFORM(2, 3, 0, -36); +} - state->new_tile(state, vs, 4, depth); - } - if (depth >= state->max_depth) return 0; +void penrosectx_generate( + PenroseContext *ctx, + bool (*inbounds)(void *inboundsctx, + const PenroseTriangle *tri), void *inboundsctx, + void (*tile)(void *tilectx, const Point *vertices), void *tilectx) +{ + tree234 *placed = newtree234(penrose_cmp); + PenroseTriangle *qhead = NULL, *qtail = NULL; - /* NB these two are identical to the first two of p3_large. */ - vv_orig = v_trans(v_orig, v_edge); + { + PenroseTriangle *tri = penrose_initial(ctx); - penrose_p3_large(state, depth+1, -flip, - vv_orig, v_shrinkphi(v_rotate(v_edge, 180))); + add234(placed, tri); - penrose_p3_small(state, depth+1, flip, - vv_orig, v_shrinkphi(v_rotate(v_edge, -108*flip))); + tri->next = NULL; + tri->reported = false; - return 0; -} + if (inbounds(inboundsctx, tri)) + qhead = qtail = tri; + } -/* ------------------------------------------------------- - * Utility routines. - */ + while (qhead) { + PenroseTriangle *tri = qhead; + unsigned edge; + unsigned sibling_edge = penrose_sibling_edge_index(tri->pc->c[0]); + + for (edge = 0; edge < 3; edge++) { + PenroseTriangle *new_tri, *found_tri; + + new_tri = penrose_adjacent(ctx, tri, edge, NULL); + + if (!inbounds(inboundsctx, new_tri)) { + penrose_free(new_tri); + continue; + } + + found_tri = find234(placed, new_tri, NULL); + if (found_tri) { + if (edge == sibling_edge && !tri->reported && + !found_tri->reported) { + /* + * found_tri and tri are opposite halves of the + * same tile; both are in the tree, and haven't + * yet been reported as a completed tile. + */ + unsigned new_sibling_edge = penrose_sibling_edge_index( + found_tri->pc->c[0]); + Point tilevertices[4] = { + tri->vertices[(sibling_edge + 1) % 3], + tri->vertices[(sibling_edge + 2) % 3], + found_tri->vertices[(new_sibling_edge + 1) % 3], + found_tri->vertices[(new_sibling_edge + 2) % 3], + }; + tile(tilectx, tilevertices); + + tri->reported = true; + found_tri->reported = true; + } + + penrose_free(new_tri); + continue; + } + + add234(placed, new_tri); + qtail->next = new_tri; + qtail = new_tri; + new_tri->next = NULL; + new_tri->reported = false; + } -double penrose_side_length(double start_size, int depth) -{ - return start_size / pow(PHI, depth); -} + qhead = qhead->next; + } -void penrose_count_tiles(int depth, int *nlarge, int *nsmall) -{ - /* Steal sgt's fibonacci thingummy. */ + { + PenroseTriangle *tri; + while ((tri = delpos234(placed, 0)) != NULL) + penrose_free(tri); + freetree234(placed); + } } -/* - * It turns out that an acute isosceles triangle with sides in ratio 1:phi:phi - * has an incentre which is conveniently 2*phi^-2 of the way from the apex to - * the base. Why's that convenient? Because: if we situate the incentre of the - * triangle at the origin, then we can place the apex at phi^-2 * (B+C), and - * the other two vertices at apex-B and apex-C respectively. So that's an acute - * triangle with its long sides of unit length, covering a circle about the - * origin of radius 1-(2*phi^-2), which is conveniently enough phi^-3. - * - * (later mail: this is an overestimate by about 5%) - */ - -int penrose(penrose_state *state, int which, int angle) +const char *penrose_tiling_params_invalid( + const struct PenrosePatchParams *params, int which) { - vector vo = v_origin(); - vector vb = v_origin(); - - vo.b = vo.c = -state->start_size; - vo = v_shrinkphi(v_shrinkphi(vo)); - - vb.b = state->start_size; + size_t i; - vo = v_rotate(vo, angle); - vb = v_rotate(vb, angle); + if (params->ncoords == 0) + return "expected at least one coordinate"; - if (which == PENROSE_P2) - return penrose_p2_large(state, 0, 1, vo, vb); - else - return penrose_p3_small(state, 0, 1, vo, vb); -} - -/* - * We're asked for a MxN grid, which just means a tiling fitting into roughly - * an MxN space in some kind of reasonable unit - say, the side length of the - * two-arrow edges of the tiles. By some reasoning in a previous email, that - * means we want to pick some subarea of a circle of radius 3.11*sqrt(M^2+N^2). - * To cover that circle, we need to subdivide a triangle large enough that it - * contains a circle of that radius. - * - * Hence: start with those three vectors marking triangle vertices, scale them - * all up by phi repeatedly until the radius of the inscribed circle gets - * bigger than the target, and then recurse into that triangle with the same - * recursion depth as the number of times you scaled up. That will give you - * tiles of unit side length, covering a circle big enough that if you randomly - * choose an orientation and coordinates within the circle, you'll be able to - * get any valid piece of Penrose tiling of size MxN. - */ -#define INCIRCLE_RADIUS 0.22426 /* phi^-3 less 5%: see above */ - -void penrose_calculate_size(int which, int tilesize, int w, int h, - double *required_radius, int *start_size, int *depth) -{ - double rradius, size; - int n = 0; - - /* - * Fudge factor to scale P2 and P3 tilings differently. This - * doesn't seem to have much relevance to questions like the - * average number of tiles per unit area; it's just aesthetic. - */ - if (which == PENROSE_P2) - tilesize = tilesize * 3 / 2; - else - tilesize = tilesize * 5 / 4; - - rradius = tilesize * 3.11 * sqrt((double)(w*w + h*h)); - size = tilesize; - - while ((size * INCIRCLE_RADIUS) < rradius) { - n++; - size = size * PHI; + for (i = 0; i < params->ncoords; i++) { + if (!penrose_valid_letter(params->coords[i], which)) + return "invalid coordinate letter"; + if (i > 0 && !strchr(penrose_valid_parents(params->coords[i-1]), + params->coords[i])) + return "invalid pair of consecutive coordinates"; } - *start_size = (int)size; - *depth = n; - *required_radius = rradius; + return NULL; } -/* ------------------------------------------------------- - * Test code. - */ - -#ifdef TEST_PENROSE - -#include -#include +struct PenroseOutputCtx { + int xoff, yoff; + Coord xmin, xmax, ymin, ymax; -int show_recursion = 0; -int ntiles, nfinal; + penrose_tile_callback_fn external_cb; + void *external_cbctx; +}; -int test_cb(penrose_state *state, vector *vs, int n, int depth) +static bool inbounds(void *vctx, const PenroseTriangle *tri) { - int i, xoff = 0, yoff = 0; - double l = penrose_side_length(state->start_size, depth); - double rball = l / 10.0; - const char *col; + struct PenroseOutputCtx *octx = (struct PenroseOutputCtx *)vctx; + size_t i; - ntiles++; - if (state->max_depth == depth) { - col = n == 4 ? "black" : "green"; - nfinal++; - } else { - if (!show_recursion) - return 0; - col = n == 4 ? "red" : "blue"; - } - if (n != 4) yoff = state->start_size; + for (i = 0; i < 3; i++) { + Coord x = point_x(tri->vertices[i]); + Coord y = point_y(tri->vertices[i]); - printf("xmin) < 0 || coord_cmp(x, octx->xmax) > 0 || + coord_cmp(y, octx->ymin) < 0 || coord_cmp(y, octx->ymax) > 0) + return false; } - printf("\" style=\"fill: %s; fill-opacity: 0.2; stroke: %s\" />\n", col, col); - printf("", - v_x(vs, 0) + xoff, v_y(vs, 0) + yoff, rball, rball, col); - return 0; + return true; } -void usage_exit(void) +static void null_output_tile(void *vctx, const Point *vertices) { - fprintf(stderr, "Usage: penrose-test [--recursion] P2|P3 SIZE DEPTH\n"); - exit(1); } -int main(int argc, char *argv[]) +static void really_output_tile(void *vctx, const Point *vertices) { - penrose_state ps; - int which = 0; - - while (--argc > 0) { - char *p = *++argv; - if (!strcmp(p, "-h") || !strcmp(p, "--help")) { - usage_exit(); - } else if (!strcmp(p, "--recursion")) { - show_recursion = 1; - } else if (*p == '-') { - fprintf(stderr, "Unrecognised option '%s'\n", p); - exit(1); - } else { - break; - } + struct PenroseOutputCtx *octx = (struct PenroseOutputCtx *)vctx; + size_t i; + int coords[16]; + + for (i = 0; i < 4; i++) { + Coord x = point_x(vertices[i]); + Coord y = point_y(vertices[i]); + + coords[4*i + 0] = x.c1 + octx->xoff; + coords[4*i + 1] = x.cr5; + coords[4*i + 2] = y.c1 + octx->yoff; + coords[4*i + 3] = y.cr5; } - if (argc < 3) usage_exit(); - - if (strcmp(argv[0], "P2") == 0) which = PENROSE_P2; - else if (strcmp(argv[0], "P3") == 0) which = PENROSE_P3; - else usage_exit(); - - ps.start_size = atoi(argv[1]); - ps.max_depth = atoi(argv[2]); - ps.new_tile = test_cb; - - ntiles = nfinal = 0; - - printf("\ -\n\ -\n\ -\n\ -\n\n"); - - printf("\n"); - penrose(&ps, which); - printf("\n"); + octx->external_cb(octx->external_cbctx, coords); +} - printf("\n", - ntiles, nfinal); +static void penrose_set_bounds(struct PenroseOutputCtx *octx, int w, int h) +{ + octx->xoff = w/2; + octx->yoff = h/2; + octx->xmin.c1 = -octx->xoff; + octx->xmax.c1 = -octx->xoff + w; + octx->ymin.c1 = octx->yoff - h; + octx->ymax.c1 = octx->yoff; + octx->xmin.cr5 = 0; + octx->xmax.cr5 = 0; + octx->ymin.cr5 = 0; + octx->ymax.cr5 = 0; +} - printf(""); +void penrose_tiling_randomise(struct PenrosePatchParams *params, int which, + int w, int h, random_state *rs) +{ + PenroseContext ctx[1]; + struct PenroseOutputCtx octx[1]; - return 0; -} + penrose_set_bounds(octx, w, h); -#endif + penrosectx_init_random(ctx, rs, which); + penrosectx_generate(ctx, inbounds, octx, null_output_tile, NULL); -#ifdef TEST_VECTORS + params->orientation = ctx->orientation; + params->start_vertex = ctx->start_vertex; + params->ncoords = ctx->prototype->nc; + params->coords = snewn(params->ncoords, char); + memcpy(params->coords, ctx->prototype->c, params->ncoords); -static void dbgv(const char *msg, vector v) -{ - printf("%s: %s\n", msg, v_debug(v)); + penrosectx_cleanup(ctx); } -int main(int argc, const char *argv[]) +void penrose_tiling_generate( + const struct PenrosePatchParams *params, int w, int h, + penrose_tile_callback_fn cb, void *cbctx) { - vector v = v_unit(); + PenroseContext ctx[1]; + struct PenroseOutputCtx octx[1]; - dbgv("unit vector", v); - v = v_rotate(v, 36); - dbgv("rotated 36", v); - v = v_scale(v, 2); - dbgv("scaled x2", v); - v = v_shrinkphi(v); - dbgv("shrunk phi", v); - v = v_rotate(v, -36); - dbgv("rotated -36", v); + penrose_set_bounds(octx, w, h); + octx->external_cb = cb; + octx->external_cbctx = cbctx; - return 0; + penrosectx_init_from_params(ctx, params); + penrosectx_generate(ctx, inbounds, octx, really_output_tile, octx); + penrosectx_cleanup(ctx); } - -#endif -/* vim: set shiftwidth=4 tabstop=8: */ -- cgit v1.2.3