ref: 23d4322fec38f8ffac930bc541e08309e1d02f11
dir: /auxiliary/spectre-gen.c/
/* * Generate the lookup tables used by the Spectre tiling. */ #include <assert.h> #include <errno.h> #include <math.h> #include <stdio.h> #include <string.h> #include "puzzles.h" #include "tree234.h" #include "spectre-internal.h" #include "spectre-tables-manual.h" #include "spectre-tables-extra.h" #include "spectre-help.h" struct HexData { const Hex *subhexes; const unsigned *orientations; const int *edges; Point hex_outline_start, hex_outline_direction; unsigned spectre_outline_start_spec, spectre_outline_start_vertex; }; static const struct HexData hexdata[] = { #define HEXDATA_ENTRY(x) { subhexes_##x, orientations_##x, edges_##x, \ HEX_OUTLINE_START_##x, SPEC_OUTLINE_START_##x }, HEX_LETTERS(HEXDATA_ENTRY) #undef HEXDATA_ENTRY }; /* * Store information about an edge of the hexagonal tiling. */ typedef struct EdgeData { /* Edges are regarded as directed, so that we can store * information separately about what's on each side of one. The * names 'start' and 'finish' indicate a direction of travel, * which is taken to be anticlockwise around a hexagon, i.e. if * you walk from 'start' to 'finish' then the hexagon in question * is the one on your left. */ Point start, finish; /* Whether this edge is internal (i.e. owned by a hexagon). */ bool internal; /* * High- and low-order parts of the edge identity. * * If the edge is internal, then 'hi' indexes the hexagon it's an * edge of, and 'lo' identifies one of its edges. * * If it's external, then 'hi' is the index of the edge segment * corresponding to a particular edge of the superhex, and 'lo' * the sub-index within that segment. */ unsigned hi, lo; } EdgeData; static int edge_cmp(void *av, void *bv) { const EdgeData *a = (const EdgeData *)av; const EdgeData *b = (const EdgeData *)bv; size_t i; for (i = 0; i < 4; i++) { if (a->start.coeffs[i] < b->start.coeffs[i]) return -1; if (a->start.coeffs[i] > b->start.coeffs[i]) return +1; } for (i = 0; i < 4; i++) { if (a->finish.coeffs[i] < b->finish.coeffs[i]) return -1; if (a->finish.coeffs[i] > b->finish.coeffs[i]) return +1; } return 0; } static void lay_out_hexagons(Hex h, Graphics *gr, FILE *hdr) { size_t i, j; tree234 *edge_map = newtree234(edge_cmp); EdgeData *edge; EdgeData *intmap[48], *extmap[22]; unsigned edgestarts[7]; const struct HexData *hd = h == NO_HEX ? NULL : &hexdata[h]; /* * Iterate over all hexagons and enter their edges into the edge * map. */ for (i = 0; i < (h == NO_HEX ? 8 : num_subhexes(h)); i++) { Point centre = hex_centres[i]; Point vrel = {{ -2, 0, 4, 0 }}; Point vertices[6]; if (hd) vrel = point_mul(vrel, point_rot(2*hd->orientations[i])); for (j = 0; j < 6; j++) { Point vrelnext = point_mul(vrel, point_rot(2)); edge = snew(EdgeData); edge->start = point_add(centre, vrel); edge->finish = point_add(centre, vrelnext); edge->internal = true; edge->hi = i; edge->lo = j; add234(edge_map, edge); intmap[6*i + j] = edge; vertices[j] = edge->start; vrel = vrelnext; } gr_draw_hex(gr, gr->jigsaw_mode ? -1 : i, hd ? hd->subhexes[i] : NO_HEX, vertices); } /* * Trace round the exterior outline of the hex expansion, * following the list of edge types. */ if (hd) { Point pos, dir; size_t mappos = 0; pos = hd->hex_outline_start; dir = hd->hex_outline_direction; for (i = 0; i < 6; i++) { int edge_type = hd->edges[i]; int sign = edge_type < 0 ? -1 : +1; const int *edge_shape = hex_edge_shapes[abs(edge_type)]; size_t len = hex_edge_lengths[abs(edge_type)]; size_t index = sign < 0 ? len-2 : 0; if (gr->vertex_blobs) gr_draw_blob(gr, (i == 0 ? "startpoint" : "edgesep"), gr_logcoords(pos), (i == 0 ? 0.6 : 0.3)); edgestarts[i] = mappos; for (j = 0; j < len; j++) { Point posnext = point_add(pos, dir); if (j < len-1) { dir = point_mul(dir, point_rot(sign * edge_shape[index])); index += sign; } edge = snew(EdgeData); edge->start = pos; edge->finish = posnext; edge->internal = false; edge->hi = i; edge->lo = j; add234(edge_map, edge); assert(mappos < lenof(extmap)); extmap[mappos++] = edge; pos = posnext; } /* * In the hex expansion, every pair of edges meet at a * 60-degree left turn. */ dir = point_mul(dir, point_rot(-2)); } edgestarts[i] = mappos; /* record end position */ for (i = 0; i < 4; i++) assert(pos.coeffs[i] == hd->hex_outline_start.coeffs[i]); } /* * Draw the labels on the edges. */ if (gr->number_edges) { for (i = 0; (edge = index234(edge_map, i)) != NULL; i++) { char buf[64]; double textheight = 0.8, offset = textheight * 0.2; GrCoords start = gr_logcoords(edge->start); GrCoords finish = gr_logcoords(edge->finish); GrCoords len = { finish.x - start.x, finish.y - start.y }; GrCoords perp = { -len.y, +len.x }; GrCoords mid = { (start.x+finish.x)/2, (start.y+finish.y)/2 }; if (edge->internal) { sprintf(buf, "%u", edge->lo); } else { sprintf(buf, "%u.%u", edge->lo, edge->hi); offset = textheight * 0.3; } { GrCoords pos = { mid.x + offset * perp.x, mid.y + offset * perp.y, }; gr_draw_text(gr, pos, textheight, buf); } } } /* * Write out C array declarations for the machine-readable version * of the maps we just generated. */ if (hdr) { fprintf(hdr, "static const struct MapEntry hexmap_%s[] = {\n", hex_names[h]); for (i = 0; i < 6 * num_subhexes(h); i++) { EdgeData *our_edge = intmap[i]; EdgeData key, *rev_edge; key.finish = our_edge->start; key.start = our_edge->finish; rev_edge = find234(edge_map, &key, NULL); assert(rev_edge); fprintf(hdr, " { %-6s %u, %u }, /* edge %u of hex %u (%s) */\n", rev_edge->internal ? "true," : "false,", rev_edge->hi, rev_edge->lo, our_edge->lo, our_edge->hi, hex_names[hd->subhexes[our_edge->hi]]); } fprintf(hdr, "};\n"); fprintf(hdr, "static const struct MapEdge hexedges_%s[] = {\n", hex_names[h]); for (i = 0; i < 6; i++) fprintf(hdr, " { %2u, %u },\n", edgestarts[i], edgestarts[i+1] - edgestarts[i]); fprintf(hdr, "};\n"); fprintf(hdr, "static const struct MapEntry hexin_%s[] = {\n", hex_names[h]); for (i = 0; i < edgestarts[6]; i++) { EdgeData *our_edge = extmap[i]; EdgeData key, *rev_edge; key.finish = our_edge->start; key.start = our_edge->finish; rev_edge = find234(edge_map, &key, NULL); assert(rev_edge); fprintf(hdr, " { %-6s %u, %u }, /* subedge %u of edge %u */\n", rev_edge->internal ? "true," : "false,", rev_edge->hi, rev_edge->lo, our_edge->lo, our_edge->hi); } fprintf(hdr, "};\n"); } while ((edge = delpos234(edge_map, 0)) != NULL) sfree(edge); freetree234(edge_map); } static void lay_out_spectres(Hex h, Graphics *gr, FILE *hdr) { size_t i, j; tree234 *edge_map = newtree234(edge_cmp); EdgeData *edge; EdgeData *intmap[28], *extmap[24]; Point vertices[28]; unsigned edgestarts[7]; const struct HexData *hd = (h == NO_HEX ? NULL : &hexdata[h]); /* * Iterate over the Spectres in a hex (usually only one), and enter * their edges into the edge map. */ for (i = 0; i < (h == NO_HEX ? 2 : num_spectres(h)); i++) { Point start = {{ 0, 0, 0, 0 }}; Point pos = start; Point diag = {{ 2, 0, 0, 2 }}; Point dir = point_mul(diag, point_rot(5)); /* * Usually the single Spectre in each map is oriented in the * same place. For spectre #1 in the G map, however, we orient * it manually in a different location. (There's no point * making an organised lookup table for just this one * exceptional case.) */ if (i == 1) { Point unusual_start = {{ 2, 6, 2, 0 }}; pos = unusual_start; dir = point_mul(dir, point_rot(+1)); } for (j = 0; j < 14; j++) { edge = snew(EdgeData); edge->start = pos; edge->finish = point_add(pos, dir); edge->internal = true; edge->hi = i; edge->lo = j; add234(edge_map, edge); intmap[14*i + j] = edge; vertices[14*i + j] = edge->start; pos = edge->finish; dir = point_mul(dir, point_rot(spectre_angles[(j+1) % 14])); } gr_draw_spectre(gr, h, i, vertices + 14*i); } /* * Trace round the exterior outline of the hex expansion, * following the list of edge types. Due to the confusing * reflection of all the expansions, we end up doing this in the * reverse order to the hexes code above. */ if (hd) { Point start, pos, dir; size_t mappos = lenof(extmap); start = pos = vertices[14 * hd->spectre_outline_start_spec + hd->spectre_outline_start_vertex]; edgestarts[6] = mappos; for (i = 0; i < 6; i++) { int edge_type = hd->edges[5-i]; int sign = edge_type < 0 ? -1 : +1; const int *edge_shape = spec_edge_shapes[abs(edge_type)]; size_t len = spec_edge_lengths[abs(edge_type)]; size_t index = sign < 0 ? len-2 : 0; if (gr->vertex_blobs) gr_draw_blob(gr, (i == 0 ? "startpoint" : "edgesep"), gr_logcoords(pos), (i == 0 ? 0.6 : 0.3)); if (h == HEX_S && i >= 4) { /* * Two special cases */ if (i == 4) /* leave dir from last time */; else dir = point_mul(dir, point_rot(6)); /* reverse */ } else { /* * Determine the direction of the first sub-edge of * this edge expansion, by iterating over all the * edges in edge_map starting at this point and * finding one whose reverse isn't in the map (hence, * it's an exterior edge). */ EdgeData dummy, *iter, *found = NULL; dummy.start = pos; for (j = 0; j < 4; j++) dummy.finish.coeffs[j] = INT_MIN; for (iter = findrel234(edge_map, &dummy, NULL, REL234_GE); iter != NULL && point_equal(iter->start, pos); iter = findrel234(edge_map, iter, NULL, REL234_GT)) { EdgeData *rev; dummy.finish = iter->start; dummy.start = iter->finish; rev = find234(edge_map, &dummy, NULL); if (!rev) { found = iter; break; } } assert(found); dir = point_sub(found->finish, found->start); } for (j = 0; j < len; j++) { Point posnext = point_add(pos, dir); if (j < len-1) { dir = point_mul(dir, point_rot(sign * edge_shape[index])); index += sign; } edge = snew(EdgeData); edge->start = posnext; edge->finish = pos; edge->internal = false; edge->hi = 5-i; edge->lo = len-1-j; add234(edge_map, edge); assert(mappos > 0); extmap[--mappos] = edge; pos = posnext; } edgestarts[5-i] = mappos; } assert(point_equal(pos, start)); } /* * Draw the labels on the edges. */ if (gr->number_edges) { for (i = 0; (edge = index234(edge_map, i)) != NULL; i++) { char buf[64]; double textheight = 0.8, offset = textheight * 0.2; GrCoords start = gr_logcoords(edge->start); GrCoords finish = gr_logcoords(edge->finish); GrCoords len = { finish.x - start.x, finish.y - start.y }; GrCoords perp = { +len.y, -len.x }; GrCoords mid = { (start.x+finish.x)/2, (start.y+finish.y)/2 }; if (edge->internal) { sprintf(buf, "%u", edge->lo); } else { sprintf(buf, "%u.%u", edge->lo, edge->hi); textheight = 0.6; } if (strlen(buf) > 1) offset = textheight * 0.35; { GrCoords pos = { mid.x + offset * perp.x, mid.y + offset * perp.y, }; gr_draw_text(gr, pos, textheight, buf); } } } /* * Write out C array declarations for the machine-readable version * of the maps we just generated. * * Also, because it's easier than having a whole extra iteration, * draw lines for the extraordinary edges outside the S diagram. */ if (hdr) { fprintf(hdr, "static const struct MapEntry specmap_%s[] = {\n", hex_names[h]); for (i = 0; i < 14 * num_spectres(h); i++) { EdgeData *our_edge = intmap[i]; EdgeData key, *rev_edge; key.finish = our_edge->start; key.start = our_edge->finish; rev_edge = find234(edge_map, &key, NULL); assert(rev_edge); fprintf(hdr, " { %-6s %u, %2u }, /* edge %2u of Spectre %u */\n", rev_edge->internal ? "true," : "false,", rev_edge->hi, rev_edge->lo, our_edge->lo, our_edge->hi); } fprintf(hdr, "};\n"); fprintf(hdr, "static const struct MapEdge specedges_%s[] = {\n", hex_names[h]); for (i = 0; i < 6; i++) fprintf(hdr, " { %2u, %u },\n", edgestarts[i] - edgestarts[0], edgestarts[i+1] - edgestarts[i]); fprintf(hdr, "};\n"); fprintf(hdr, "static const struct MapEntry specin_%s[] = {\n", hex_names[h]); for (i = edgestarts[0]; i < edgestarts[6]; i++) { EdgeData *our_edge = extmap[i]; EdgeData key, *rev_edge; key.finish = our_edge->start; key.start = our_edge->finish; rev_edge = find234(edge_map, &key, NULL); assert(rev_edge); fprintf(hdr, " { %-6s %u, %2u }, /* subedge %u of edge %u */\n", rev_edge->internal ? "true," : "false,", rev_edge->hi, rev_edge->lo, our_edge->lo, our_edge->hi); if (!our_edge->internal && !rev_edge->internal) gr_draw_extra_edge(gr, key.start, key.finish); } fprintf(hdr, "};\n"); } while ((edge = delpos234(edge_map, 0)) != NULL) sfree(edge); freetree234(edge_map); } static void draw_base_hex(Hex h, Graphics *gr) { size_t i; Point vertices[6]; /* * Plot the points of the hex. */ for (i = 0; i < 6; i++) { Point startvertex = {{ -2, 0, 4, 0 }}; vertices[i] = point_mul(startvertex, point_rot(2*i)); } /* * Draw the hex itself. */ gr_draw_hex(gr, -1, h, vertices); if (gr->vertex_blobs) { /* * Draw edge-division blobs on all vertices, to match the ones on * the expansion diagrams. */ for (i = 0; i < 6; i++) { gr_draw_blob(gr, (i == 0 ? "startpoint" : "edgesep"), gr_logcoords(vertices[i]), (i == 0 ? 0.6 : 0.3)); } } if (gr->number_edges) { /* * Draw the labels on its edges. */ for (i = 0; i < 6; i++) { char buf[64]; double textheight = 0.8, offset = textheight * 0.2; GrCoords start = gr_logcoords(vertices[i]); GrCoords finish = gr_logcoords(vertices[(i+1) % 6]); GrCoords len = { finish.x - start.x, finish.y - start.y }; GrCoords perp = { -len.y, +len.x }; GrCoords mid = { (start.x+finish.x)/2, (start.y+finish.y)/2 }; sprintf(buf, "%zu", i); { GrCoords pos = { mid.x + offset * perp.x, mid.y + offset * perp.y, }; gr_draw_text(gr, pos, textheight, buf); } } } } static void draw_one_spectre(Graphics *gr) { size_t i, j; Point vertices[14]; { Point start = {{ 0, 0, 0, 0 }}; Point pos = start; Point diag = {{ 2, 0, 0, 2 }}; Point dir = point_mul(diag, point_rot(9)); for (j = 0; j < 14; j++) { vertices[j] = pos; pos = point_add(pos, dir); dir = point_mul(dir, point_rot(spectre_angles[(j+1) % 14])); } gr_draw_spectre(gr, NO_HEX, -1, vertices); } /* * Draw the labels on the edges. */ if (gr->number_edges) { for (i = 0; i < 14; i++) { char buf[64]; double textheight = 0.8, offset = textheight * 0.2; GrCoords start = gr_logcoords(vertices[i]); GrCoords finish = gr_logcoords(vertices[(i+1) % 14]); GrCoords len = { finish.x - start.x, finish.y - start.y }; GrCoords perp = { +len.y, -len.x }; GrCoords mid = { (start.x+finish.x)/2, (start.y+finish.y)/2 }; sprintf(buf, "%zu", i); if (strlen(buf) > 1) offset = textheight * 0.35; { GrCoords pos = { mid.x + offset * perp.x, mid.y + offset * perp.y, }; gr_draw_text(gr, pos, textheight, buf); } } } } static void make_parent_tables(FILE *fp) { size_t i, j, k; for (i = 0; i < 9; i++) { fprintf(fp, "static const struct Possibility poss_%s[] = {\n", hex_names[i]); for (j = 0; j < 9; j++) { for (k = 0; k < num_subhexes(j); k++) { if (hexdata[j].subhexes[k] == i) { fprintf(fp, " { HEX_%s, %zu, PROB_%s },\n", hex_names[j], k, hex_names[j]); } } } fprintf(fp, "};\n"); } fprintf(fp, "static const struct Possibility poss_spectre[] = {\n"); for (j = 0; j < 9; j++) { for (k = 0; k < num_spectres(j); k++) { fprintf(fp, " { HEX_%s, %zu, PROB_%s },\n", hex_names[j], k, hex_names[j]); } } fprintf(fp, "};\n"); } int main(void) { size_t i; FILE *fp = fopen("spectre-tables-auto.h", "w"); fprintf(fp, "/*\n" " * Autogenerated transition tables for the Spectre tiling.\n" " * Generated by auxiliary/spectre-gen.c.\n" " */\n\n"); for (i = 0; i < 9; i++) { char buf[64]; sprintf(buf, "hexmap_%s.svg", hex_names[i]); Graphics *gr = gr_new(buf, -11, +11, -20, +4.5, 13); lay_out_hexagons(i, gr, fp); gr_free(gr); } for (i = 0; i < 9; i++) { char buf[64]; sprintf(buf, "specmap_%s.svg", hex_names[i]); Graphics *gr = gr_new(buf, (i == HEX_S ? -14 : -11.5), (i == HEX_G ? +10 : 0.5), -2, +12, 15); lay_out_spectres(i, gr, fp); gr_free(gr); } for (i = 0; i < 9; i++) { char buf[64]; sprintf(buf, "basehex_%s.svg", hex_names[i]); Graphics *gr = gr_new(buf, -4, +4, -4.2, +4.5, 15); draw_base_hex(i, gr); gr_free(gr); } for (i = 0; i < 9; i++) { char buf[64]; sprintf(buf, "jigsawhex_%s.svg", hex_names[i]); Graphics *gr = gr_new(buf, -4, +4, -4.2, +4.5, 20); gr->jigsaw_mode = true; gr->vertex_blobs = false; gr->number_edges = false; draw_base_hex(i, gr); gr_free(gr); } { Graphics *gr = gr_new("basehex_null.svg", -4, +4, -4.2, +4.5, 20); gr->vertex_blobs = false; draw_base_hex(NO_HEX, gr); gr_free(gr); } { Graphics *gr = gr_new("basespec_null.svg", -7, +6, -14, +1, 15); gr->vertex_blobs = false; draw_one_spectre(gr); gr_free(gr); } { Graphics *gr = gr_new("hexmap_null.svg", -11, +11, -20, +4.5, 10); gr->vertex_blobs = false; gr->number_edges = false; gr->hex_arrows = false; lay_out_hexagons(NO_HEX, gr, NULL); gr_free(gr); } { Graphics *gr = gr_new("specmap_null.svg", -11.5, +10, -2, +12, 15); gr->vertex_blobs = false; gr->number_edges = false; gr->hex_arrows = false; lay_out_spectres(NO_HEX, gr, NULL); gr_free(gr); } for (i = 0; i < 2; i++) { char buf[64]; sprintf(buf, "jigsawexpand_%s.svg", hex_names[i]); Graphics *gr = gr_new(buf, -11, +11, -20, +4.5, 10); gr->jigsaw_mode = true; gr->vertex_blobs = false; gr->number_edges = false; lay_out_hexagons(i, gr, fp); gr_free(gr); } make_parent_tables(fp); fclose(fp); return 0; }