ref: 0d005b526ed554a165a83557512e745c8de335d6
dir: /auxiliary/spectre-test.c/
/*
* Standalone test program for spectre.c.
*/
#include <assert.h>
#ifdef NO_TGMATH_H
# include <math.h>
#else
# include <tgmath.h>
#endif
#include <stdarg.h>
#include <stdio.h>
#include <string.h>
#include "puzzles.h"
#include "spectre-internal.h"
#include "spectre-tables-manual.h"
#include "spectre-tables-auto.h"
#include "spectre-help.h"
static void step_tests(void)
{
SpectreContext ctx[1];
random_state *rs;
SpectreCoords *sc;
unsigned outedge;
rs = random_new("12345", 5);
spectrectx_init_random(ctx, rs);
/* Simplest possible transition: between the two Spectres making
* up a G hex. */
sc = spectre_coords_new();
spectre_coords_make_space(sc, 1);
sc->index = 0;
sc->nc = 1;
sc->c[0].type = HEX_G;
sc->c[0].index = -1;
spectrectx_step(ctx, sc, 12, &outedge);
assert(outedge == 5);
assert(sc->index == 1);
assert(sc->nc == 1);
assert(sc->c[0].type == HEX_G);
assert(sc->c[0].index == -1);
spectre_coords_free(sc);
/* Test the double Spectre transition. Here, within a F superhex,
* we attempt to step from the G subhex to the S one, in such a
* way that the place where we enter the Spectre corresponding to
* the S hex is on its spur of detached edge, causing us to
* immediately transition back out of the other side of that spur
* and end up in the D subhex instead. */
sc = spectre_coords_new();
spectre_coords_make_space(sc, 2);
sc->index = 1;
sc->nc = 2;
sc->c[0].type = HEX_G;
sc->c[0].index = 2;
sc->c[1].type = HEX_F;
sc->c[1].index = -1;
spectrectx_step(ctx, sc, 1, &outedge);
assert(outedge == 6);
assert(sc->index == 0);
assert(sc->nc == 2);
assert(sc->c[0].type == HEX_D);
assert(sc->c[0].index == 5);
assert(sc->c[1].type == HEX_F);
assert(sc->c[1].index == -1);
spectre_coords_free(sc);
/* However, _this_ transition leaves the same G subhex by the same
* edge of the hexagon, but further along it, so that we land in
* the S Spectre and stay there, without needing a double
* transition. */
sc = spectre_coords_new();
spectre_coords_make_space(sc, 2);
sc->index = 1;
sc->nc = 2;
sc->c[0].type = HEX_G;
sc->c[0].index = 2;
sc->c[1].type = HEX_F;
sc->c[1].index = -1;
spectrectx_step(ctx, sc, 13, &outedge);
assert(outedge == 4);
assert(sc->index == 0);
assert(sc->nc == 2);
assert(sc->c[0].type == HEX_S);
assert(sc->c[0].index == 3);
assert(sc->c[1].type == HEX_F);
assert(sc->c[1].index == -1);
spectre_coords_free(sc);
/* A couple of randomly generated transition tests that go a long
* way up the stack. */
sc = spectre_coords_new();
spectre_coords_make_space(sc, 7);
sc->index = 0;
sc->nc = 7;
sc->c[0].type = HEX_S;
sc->c[0].index = 3;
sc->c[1].type = HEX_Y;
sc->c[1].index = 7;
sc->c[2].type = HEX_Y;
sc->c[2].index = 4;
sc->c[3].type = HEX_Y;
sc->c[3].index = 4;
sc->c[4].type = HEX_F;
sc->c[4].index = 0;
sc->c[5].type = HEX_X;
sc->c[5].index = 1;
sc->c[6].type = HEX_G;
sc->c[6].index = -1;
spectrectx_step(ctx, sc, 13, &outedge);
assert(outedge == 12);
assert(sc->index == 0);
assert(sc->nc == 7);
assert(sc->c[0].type == HEX_Y);
assert(sc->c[0].index == 1);
assert(sc->c[1].type == HEX_P);
assert(sc->c[1].index == 1);
assert(sc->c[2].type == HEX_D);
assert(sc->c[2].index == 5);
assert(sc->c[3].type == HEX_Y);
assert(sc->c[3].index == 4);
assert(sc->c[4].type == HEX_X);
assert(sc->c[4].index == 7);
assert(sc->c[5].type == HEX_S);
assert(sc->c[5].index == 3);
assert(sc->c[6].type == HEX_G);
assert(sc->c[6].index == -1);
spectre_coords_free(sc);
sc = spectre_coords_new();
spectre_coords_make_space(sc, 7);
sc->index = 0;
sc->nc = 7;
sc->c[0].type = HEX_Y;
sc->c[0].index = 7;
sc->c[1].type = HEX_F;
sc->c[1].index = 6;
sc->c[2].type = HEX_Y;
sc->c[2].index = 4;
sc->c[3].type = HEX_X;
sc->c[3].index = 7;
sc->c[4].type = HEX_L;
sc->c[4].index = 0;
sc->c[5].type = HEX_S;
sc->c[5].index = 3;
sc->c[6].type = HEX_F;
sc->c[6].index = -1;
spectrectx_step(ctx, sc, 0, &outedge);
assert(outedge == 1);
assert(sc->index == 0);
assert(sc->nc == 7);
assert(sc->c[0].type == HEX_P);
assert(sc->c[0].index == 1);
assert(sc->c[1].type == HEX_F);
assert(sc->c[1].index == 0);
assert(sc->c[2].type == HEX_Y);
assert(sc->c[2].index == 7);
assert(sc->c[3].type == HEX_F);
assert(sc->c[3].index == 0);
assert(sc->c[4].type == HEX_G);
assert(sc->c[4].index == 2);
assert(sc->c[5].type == HEX_D);
assert(sc->c[5].index == 5);
assert(sc->c[6].type == HEX_F);
assert(sc->c[6].index == -1);
spectre_coords_free(sc);
spectrectx_cleanup(ctx);
random_free(rs);
}
struct genctx {
Graphics *gr;
FILE *fp; /* for non-graphical output modes */
random_state *rs;
Coord xmin, xmax, ymin, ymax;
};
static void gctx_set_size(
struct genctx *gctx, int width, int height, double scale, bool centre,
int *xmin, int *xmax, int *ymin, int *ymax)
{
if (centre) {
*xmax = ceil(width/(2*scale));
*xmin = -*xmax;
*ymax = ceil(height/(2*scale));
*ymin = -*ymax;
} else {
*xmin = *ymin = 0;
*xmax = ceil(width/scale);
*ymax = ceil(height/scale);
}
/* point_x() and point_y() double their output to avoid having
* to use fractions, so double the bounds we'll compare their
* results against */
gctx->xmin.c1 = *xmin * 2; gctx->xmin.cr3 = 0;
gctx->xmax.c1 = *xmax * 2; gctx->xmax.cr3 = 0;
gctx->ymin.c1 = *ymin * 2; gctx->ymin.cr3 = 0;
gctx->ymax.c1 = *ymax * 2; gctx->ymax.cr3 = 0;
}
static bool callback(void *vctx, const Spectre *spec)
{
struct genctx *gctx = (struct genctx *)vctx;
size_t i;
for (i = 0; i < 14; i++) {
Point p = spec->vertices[i];
Coord x = point_x(p), y = point_y(p);
if (coord_cmp(x, gctx->xmin) >= 0 && coord_cmp(x, gctx->xmax) <= 0 &&
coord_cmp(y, gctx->ymin) >= 0 && coord_cmp(y, gctx->ymax) <= 0)
goto ok;
}
return false;
ok:
gr_draw_spectre_from_coords(gctx->gr, spec->sc, spec->vertices);
if (gctx->fp) {
/*
* Emit calls to a made-up Python 'spectre()' function which
* takes the following parameters:
*
* - lowest-level hexagon type (one-character string)
* - index of Spectre within hexagon (0 or rarely 1)
* - array of 14 point coordinates. Each is a 2-tuple
* containing x and y. Each of those in turn is a 2-tuple
* containing coordinates of 1 and sqrt(3).
*/
fprintf(gctx->fp, "spectre('%s', %d, [",
hex_names[spec->sc->c[0].type], spec->sc->index);
for (i = 0; i < 14; i++) {
Point p = spec->vertices[i];
Coord x = point_x(p), y = point_y(p);
fprintf(gctx->fp, "%s((%d,%d),(%d,%d))", i ? ", " : "",
x.c1, x.cr3, y.c1, y.cr3);
}
fprintf(gctx->fp, "])\n");
}
return true;
}
static void spectrectx_init_random_with_four_colouring(
SpectreContext *ctx, random_state *rs)
{
spectrectx_init_random(ctx, rs);
ctx->prototype->hex_colour = random_upto(rs, 3);
ctx->prototype->prev_hex_colour = (ctx->prototype->hex_colour + 1 +
random_upto(rs, 2)) % 3;
ctx->prototype->incoming_hex_edge = random_upto(rs, 2);
}
static void generate_bfs(struct genctx *gctx)
{
SpectreContext ctx[1];
spectrectx_init_random_with_four_colouring(ctx, gctx->rs);
spectrectx_generate(ctx, callback, gctx);
spectrectx_cleanup(ctx);
}
static inline Point reflected(Point p)
{
/*
* This reflection operation is used as a conjugation by
* periodic_cheat(). For that purpose, it doesn't matter _what_
* reflection it is, only that it reverses sense.
*
* generate_raster() also uses it to conjugate between the 'find
* edges intersecting a horizontal line' and 'ditto vertical'
* operations, so for that purpose, it wants to be the specific
* reflection about the 45-degree line that swaps the positive x-
* and y-axes.
*/
Point r;
size_t i;
for (i = 0; i < 4; i++)
r.coeffs[i] = p.coeffs[3-i];
return r;
}
static void reflect_spectre(Spectre *spec)
{
size_t i;
for (i = 0; i < 14; i++)
spec->vertices[i] = reflected(spec->vertices[i]);
}
static void periodic_cheat(struct genctx *gctx)
{
Spectre start, sh, sv;
size_t i;
start.sc = NULL;
{
Point u = {{ 0, 0, 0, 0 }};
Point v = {{ 1, 0, 0, 1 }};
v = point_mul(v, point_rot(1));
spectre_place(&start, u, v, 0);
}
sh = start;
while (callback(gctx, &sh)) {
sv = sh;
i = 0;
do {
if (i) {
spectre_place(&sv, sv.vertices[6], sv.vertices[7], 0);
} else {
spectre_place(&sv, reflected(sv.vertices[6]),
reflected(sv.vertices[7]), 0);
reflect_spectre(&sv);
}
i ^= 1;
} while (callback(gctx, &sv));
sv = sh;
i = 0;
do {
if (i) {
spectre_place(&sv, sv.vertices[0], sv.vertices[1], 6);
} else {
spectre_place(&sv, reflected(sv.vertices[0]),
reflected(sv.vertices[1]), 6);
reflect_spectre(&sv);
}
i ^= 1;
} while (callback(gctx, &sv));
spectre_place(&sh, sh.vertices[12], sh.vertices[11], 4);
}
sh = start;
do {
spectre_place(&sh, sh.vertices[5], sh.vertices[4], 11);
sv = sh;
i = 0;
do {
if (i) {
spectre_place(&sv, sv.vertices[6], sv.vertices[7], 0);
} else {
spectre_place(&sv, reflected(sv.vertices[6]),
reflected(sv.vertices[7]), 0);
reflect_spectre(&sv);
}
i ^= 1;
} while (callback(gctx, &sv));
sv = sh;
i = 0;
do {
if (i) {
spectre_place(&sv, sv.vertices[0], sv.vertices[1], 6);
} else {
spectre_place(&sv, reflected(sv.vertices[0]),
reflected(sv.vertices[1]), 6);
reflect_spectre(&sv);
}
i ^= 1;
} while (callback(gctx, &sv));
} while (callback(gctx, &sh));
}
static Spectre *spectre_copy(const Spectre *orig)
{
Spectre *copy = snew(Spectre);
memcpy(copy->vertices, orig->vertices, sizeof(copy->vertices));
copy->sc = spectre_coords_copy(orig->sc);
copy->next = NULL; /* not used in this tool */
return copy;
}
static size_t find_crossings(struct genctx *gctx, const Spectre *spec, Coord y,
size_t direction, unsigned *edges_out)
{
/*
* Find edges of this Spectre which cross the horizontal line
* specified by the coordinate y.
*
* For tie-breaking purposes, we're treating the line as actually
* being at y + epsilon, so that a line with one endpoint _on_
* that coordinate is counted as crossing it if it goes upwards,
* and not downwards. Put another way, we seek edges one of whose
* vertices is < y and the other >= y.
*
* Also, we're only interested in crossings in a particular
* direction, specified by 'direction' being 0 or 1.
*/
size_t i, j;
struct Edge {
unsigned edge;
/* Location of the crossing point, as the ratio of two Coord */
Coord n, d;
} edges[14];
size_t nedges = 0;
for (i = 0; i < 14; i++) {
Coord yc[2], d[2];
yc[0] = point_y(spec->vertices[i]);
yc[1] = point_y(spec->vertices[(i+1) % 14]);
for (j = 0; j < 2; j++)
d[j] = coord_sub(yc[j], y);
if (coord_sign(d[1-direction]) >= 0 && coord_sign(d[direction]) < 0) {
Coord a0 = coord_abs(d[0]), a1 = coord_abs(d[1]);
Coord x0 = point_x(spec->vertices[i]);
Coord x1 = point_x(spec->vertices[(i+1) % 14]);
edges[nedges].d = coord_add(a0, a1);
edges[nedges].n = coord_add(coord_mul(a1, x0), coord_mul(a0, x1));
edges[nedges].edge = i;
nedges++;
/*
* Insertion sort: swap this edge backwards in the array
* until it's in the right order.
*/
{
size_t j = nedges - 1;
while (j > 0 && coord_cmp(
coord_mul(edges[j-1].n, edges[j].d),
coord_mul(edges[j].n, edges[j-1].d)) > 0) {
struct Edge tmp = edges[j-1];
edges[j-1] = edges[j];
edges[j] = tmp;
j--;
}
}
}
}
for (i = 0; i < nedges; i++)
edges_out[i] = edges[i].edge;
return nedges;
}
static void raster_emit(struct genctx *gctx, const Spectre *spec,
Coord y, unsigned edge)
{
unsigned edges[14];
size_t nedges;
Coord yprev = coord_sub(y, coord_construct(2, 4));
if (find_crossings(gctx, spec, yprev, true, edges))
return; /* we've seen this on a previous raster_x pass */
if (edge != (unsigned)-1) {
nedges = find_crossings(gctx, spec, y, false, edges);
assert(nedges > 0);
if (edge != edges[0])
return; /* we've seen this before within the same raster_x pass */
}
callback(gctx, spec);
}
static void raster_x(struct genctx *gctx, SpectreContext *ctx,
const Spectre *start, Coord *yptr, Coord xlimit)
{
Spectre *curr, *new;
Coord y;
size_t i;
unsigned incoming_edge;
/*
* Find out if this Spectre intersects our current
* y-coordinate.
*/
for (i = 0; i < 14; i++)
if (coord_cmp(point_y(start->vertices[i]), *yptr) > 0)
break;
if (i == 14) {
/*
* No, this Spectre is still below the start line.
*/
return;
}
/*
* It does! Start an x iteration here, and increment y by 2 + 4
* sqrt(3), which is the smallest possible y-extent of any
* rotation of our starting Spectre.
*/
y = *yptr;
*yptr = coord_add(*yptr, coord_construct(2, 4));
curr = spectre_copy(start);
incoming_edge = -1;
while (true) {
unsigned edges[14];
size_t nedges;
raster_emit(gctx, curr, y, incoming_edge);
nedges = find_crossings(gctx, curr, y, true, edges);
assert(nedges > 0);
for (i = 0; i+1 < nedges; i++) {
new = spectre_adjacent(ctx, curr, edges[i], &incoming_edge);
raster_emit(gctx, new, y, incoming_edge);
spectre_free(new);
}
new = spectre_adjacent(ctx, curr, edges[nedges-1], &incoming_edge);
spectre_free(curr);
curr = new;
/*
* Find out whether this Spectre is entirely beyond the
* x-limit.
*/
for (i = 0; i < 14; i++)
if (coord_cmp(point_x(curr->vertices[i]), xlimit) < 0)
break;
if (i == 14) /* no vertex broke that loop */
break;
}
spectre_free(curr);
}
static void raster_y(struct genctx *gctx, SpectreContext *ctx,
const Spectre *start, Coord x, Coord ylimit,
Coord *yptr, Coord xlimit)
{
Spectre *curr, *new;
curr = spectre_copy(start);
while (true) {
unsigned edges[14];
size_t i, nedges;
raster_x(gctx, ctx, curr, yptr, xlimit);
reflect_spectre(curr);
nedges = find_crossings(gctx, curr, x, false, edges);
reflect_spectre(curr);
assert(nedges > 0);
for (i = 0; i+1 < nedges; i++) {
new = spectre_adjacent(ctx, curr, edges[i], NULL);
raster_x(gctx, ctx, new, yptr, xlimit);
spectre_free(new);
}
new = spectre_adjacent(ctx, curr, edges[nedges-1], NULL);
spectre_free(curr);
curr = new;
/*
* Find out whether this Spectre is entirely beyond the
* y-limit.
*/
for (i = 0; i < 14; i++)
if (coord_cmp(point_y(curr->vertices[i]), ylimit) < 0)
break;
if (i == 14) /* no vertex broke that loop */
break;
}
spectre_free(curr);
}
static void generate_raster(struct genctx *gctx)
{
SpectreContext ctx[1];
Spectre *start;
Coord y = coord_integer(-10);
spectrectx_init_random_with_four_colouring(ctx, gctx->rs);
start = spectre_initial(ctx);
/*
* Move the starting Spectre down and left a bit, so that edge
* effects causing a few Spectres to be missed on the initial
* passes won't affect the overall result.
*/
{
Point offset = {{ -5, 0, 0, -5 }};
size_t i;
for (i = 0; i < 14; i++)
start->vertices[i] = point_add(start->vertices[i], offset);
}
raster_y(gctx, ctx, start, coord_integer(-10), gctx->ymax, &y, gctx->xmax);
spectre_free(start);
spectrectx_cleanup(ctx);
}
static void generate_hexes(struct genctx *gctx)
{
SpectreContext ctx[1];
spectrectx_init_random(ctx, gctx->rs);
SpectreCoords *sc;
unsigned orient, outedge, inedge;
bool printed_any = false;
size_t r = 1, ri = 0, rj = 0;
Point centre = {{ 0, 0, 0, 0 }};
const Point six = {{ 6, 0, 0, 0 }};
sc = spectre_coords_copy(ctx->prototype);
orient = random_upto(gctx->rs, 6);
while (true) {
Point top = {{ -2, 0, 4, 0 }};
Point vertices[6];
bool print_this = false;
size_t i;
for (i = 0; i < 6; i++) {
vertices[i] = point_add(centre, point_mul(
top, point_rot(2 * (orient + i))));
Coord x = point_x(vertices[i]), y = point_y(vertices[i]);
if (coord_cmp(x, gctx->xmin) >= 0 &&
coord_cmp(x, gctx->xmax) <= 0 &&
coord_cmp(y, gctx->ymin) >= 0 &&
coord_cmp(y, gctx->ymax) <= 0)
print_this = true;
}
if (print_this) {
printed_any = true;
gr_draw_hex(gctx->gr, -1, sc->c[0].type, vertices);
}
/*
* Decide which way to step next. We spiral outwards from a
* central hexagon.
*/
outedge = (ri == 0 && rj == 0) ? 5 : ri;
if (++rj >= r) {
rj = 0;
if (++ri >= 6) {
ri = 0;
if (!printed_any)
break;
printed_any = false;
++r;
}
}
spectrectx_step_hex(ctx, sc, 0, (outedge + 6 - orient) % 6, &inedge);
orient = (outedge + 9 - inedge) % 6;
centre = point_add(centre, point_mul(six, point_rot(4 + 2 * outedge)));
}
spectre_coords_free(sc);
spectrectx_cleanup(ctx);
}
int main(int argc, char **argv)
{
const char *random_seed = "12345";
const char *outfile = "-";
bool four_colour = false;
enum {
TESTS, TILING_BFS, TILING_RASTER, CHEAT, HEXES
} mode = TILING_RASTER;
enum { SVG, PYTHON } outmode = SVG;
double scale = 10, linewidth = 1.5;
int width = 1024, height = 768;
bool arcs = false;
while (--argc > 0) {
const char *arg = *++argv;
if (!strcmp(arg, "--help")) {
printf(" usage: spectre-test [FIXME]\n"
" also: spectre-test --test\n");
return 0;
} else if (!strcmp(arg, "--test")) {
mode = TESTS;
} else if (!strcmp(arg, "--hex")) {
mode = HEXES;
} else if (!strcmp(arg, "--bfs")) {
mode = TILING_BFS;
} else if (!strcmp(arg, "--cheat")) {
mode = CHEAT;
} else if (!strcmp(arg, "--python")) {
outmode = PYTHON;
} else if (!strcmp(arg, "--arcs")) {
arcs = true;
} else if (!strncmp(arg, "--seed=", 7)) {
random_seed = arg+7;
} else if (!strcmp(arg, "--fourcolour")) {
four_colour = true;
} else if (!strncmp(arg, "--scale=", 8)) {
scale = atof(arg+8);
} else if (!strncmp(arg, "--width=", 8)) {
width = atof(arg+8);
} else if (!strncmp(arg, "--height=", 9)) {
height = atof(arg+9);
} else if (!strncmp(arg, "--linewidth=", 12)) {
linewidth = atof(arg+12);
} else if (!strcmp(arg, "-o")) {
if (--argc <= 0) {
fprintf(stderr, "expected argument to '%s'\n", arg);
return 1;
}
outfile = *++argv;
} else {
fprintf(stderr, "unexpected extra argument '%s'\n", arg);
return 1;
}
}
switch (mode) {
case TESTS: {
step_tests();
break;
}
case TILING_BFS:
case TILING_RASTER:
case CHEAT: {
struct genctx gctx[1];
bool close_output = false;
int xmin, xmax, ymin, ymax;
gctx_set_size(gctx, width, height, scale, (mode != TILING_RASTER),
&xmin, &xmax, &ymin, &ymax);
switch (outmode) {
case SVG:
gctx->gr = gr_new(outfile, xmin, xmax, ymin, ymax, scale);
gctx->gr->number_cells = false;
gctx->gr->four_colour = four_colour;
gctx->gr->linewidth = linewidth;
gctx->gr->arcs = arcs;
gctx->fp = NULL;
break;
case PYTHON:
gctx->gr = NULL;
if (!strcmp(outfile, "-")) {
gctx->fp = stdout;
} else {
gctx->fp = fopen(outfile, "w");
close_output = true;
}
break;
}
gctx->rs = random_new(random_seed, strlen(random_seed));
switch (mode) {
case TILING_RASTER:
generate_raster(gctx);
break;
case TILING_BFS:
generate_bfs(gctx);
break;
case CHEAT:
periodic_cheat(gctx);
break;
default: /* shouldn't happen */
break;
}
random_free(gctx->rs);
gr_free(gctx->gr);
if (close_output)
fclose(gctx->fp);
break;
}
case HEXES: {
struct genctx gctx[1];
int xmin, xmax, ymin, ymax;
gctx_set_size(gctx, width, height, scale, true,
&xmin, &xmax, &ymin, &ymax);
gctx->gr = gr_new(outfile, xmin, xmax, ymin, ymax, scale);
gctx->gr->jigsaw_mode = true;
gctx->gr->number_edges = false;
gctx->gr->linewidth = linewidth;
gctx->rs = random_new(random_seed, strlen(random_seed));
generate_hexes(gctx); /* FIXME: bounds */
random_free(gctx->rs);
gr_free(gctx->gr);
break;
}
}
}