#include <assert.h>
#include <ctype.h>
#include <math.h>
-#include <errno.h>
+#include <float.h>
#include "puzzles.h"
#include "tree234.h"
/* Used by the other grid generators. Create a brand new grid with nothing
* initialised (all lists are NULL) */
-static grid *grid_empty()
+static grid *grid_empty(void)
{
grid *g = snew(grid);
g->faces = NULL;
#endif
#ifdef SVG_GRID
+#include <errno.h>
+
static void grid_try_svg(grid *g, int which)
{
char *svg = getenv("PUZZLES_SVG_GRID");
eq[2] = eqs[0][3]*eqs[1][2] - eqs[1][3]*eqs[0][2];
/* Parametrise x and y in terms of some t. */
- if (abs(eq[0]) < abs(eq[1])) {
+ if (fabs(eq[0]) < fabs(eq[1])) {
/* Parameter is x. */
xt[0] = 1; xt[1] = 0;
yt[0] = -eq[0]/eq[1]; yt[1] = eq[2]/eq[1];
}
if (in) {
+#ifdef HUGE_VAL
double mindist = HUGE_VAL;
+#else
+#ifdef DBL_MAX
+ double mindist = DBL_MAX;
+#else
+#error No way to get maximum floating-point number.
+#endif
+#endif
int e, d;
/*
#define SQUARE_TILESIZE 20
-void grid_size_square(int width, int height,
+static void grid_size_square(int width, int height,
int *tilesize, int *xextent, int *yextent)
{
int a = SQUARE_TILESIZE;
*yextent = height * a;
}
-grid *grid_new_square(int width, int height, char *desc)
+static grid *grid_new_square(int width, int height, const char *desc)
{
int x, y;
/* Side length */
#define HONEY_A 15
#define HONEY_B 26
-void grid_size_honeycomb(int width, int height,
+static void grid_size_honeycomb(int width, int height,
int *tilesize, int *xextent, int *yextent)
{
int a = HONEY_A;
*yextent = (2 * b * (height-1)) + 3*b;
}
-grid *grid_new_honeycomb(int width, int height, char *desc)
+static grid *grid_new_honeycomb(int width, int height, const char *desc)
{
int x, y;
int a = HONEY_A;
#define TRIANGLE_VEC_X 15
#define TRIANGLE_VEC_Y 26
-void grid_size_triangular(int width, int height,
+static void grid_size_triangular(int width, int height,
int *tilesize, int *xextent, int *yextent)
{
int vec_x = TRIANGLE_VEC_X;
int vec_y = TRIANGLE_VEC_Y;
*tilesize = TRIANGLE_TILESIZE;
- *xextent = width * 2 * vec_x + vec_x;
+ *xextent = (width+1) * 2 * vec_x;
*yextent = height * vec_y;
}
+static char *grid_validate_desc_triangular(grid_type type, int width,
+ int height, const char *desc)
+{
+ /*
+ * Triangular grids: an absent description is valid (indicating
+ * the old-style approach which had 'ears', i.e. triangles
+ * connected to only one other face, at some grid corners), and so
+ * is a description reading just "0" (indicating the new-style
+ * approach in which those ears are trimmed off). Anything else is
+ * illegal.
+ */
+
+ if (!desc || !strcmp(desc, "0"))
+ return NULL;
+
+ return "Unrecognised grid description.";
+}
+
/* Doesn't use the previous method of generation, it pre-dates it!
* A triangular grid is just about simple enough to do by "brute force" */
-grid *grid_new_triangular(int width, int height, char *desc)
+static grid *grid_new_triangular(int width, int height, const char *desc)
{
int x,y;
+ int version = (desc == NULL ? -1 : atoi(desc));
/* Vector for side of triangle - ratio is close to sqrt(3) */
int vec_x = TRIANGLE_VEC_X;
grid *g = grid_empty();
g->tilesize = TRIANGLE_TILESIZE;
- g->num_faces = width * height * 2;
- g->num_dots = (width + 1) * (height + 1);
- g->faces = snewn(g->num_faces, grid_face);
- g->dots = snewn(g->num_dots, grid_dot);
-
- /* generate dots */
- index = 0;
- for (y = 0; y <= height; y++) {
- for (x = 0; x <= width; x++) {
- grid_dot *d = g->dots + index;
- /* odd rows are offset to the right */
- d->order = 0;
- d->edges = NULL;
- d->faces = NULL;
- d->x = x * 2 * vec_x + ((y % 2) ? vec_x : 0);
- d->y = y * vec_y;
- index++;
+ if (version == -1) {
+ /*
+ * Old-style triangular grid generation, preserved as-is for
+ * backwards compatibility with old game ids, in which it's
+ * just a little asymmetric and there are 'ears' (faces linked
+ * to only one other face) at two grid corners.
+ *
+ * Example old-style game ids, which should still work, and in
+ * which you should see the ears in the TL/BR corners on the
+ * first one and in the TL/BL corners on the second:
+ *
+ * 5x5t1:2c2a1a2a201a1a1a1112a1a2b1211f0b21a2a2a0a
+ * 5x6t1:a022a212h1a1d1a12c2b11a012b1a20d1a0a12e
+ */
+
+ g->num_faces = width * height * 2;
+ g->num_dots = (width + 1) * (height + 1);
+ g->faces = snewn(g->num_faces, grid_face);
+ g->dots = snewn(g->num_dots, grid_dot);
+
+ /* generate dots */
+ index = 0;
+ for (y = 0; y <= height; y++) {
+ for (x = 0; x <= width; x++) {
+ grid_dot *d = g->dots + index;
+ /* odd rows are offset to the right */
+ d->order = 0;
+ d->edges = NULL;
+ d->faces = NULL;
+ d->x = x * 2 * vec_x + ((y % 2) ? vec_x : 0);
+ d->y = y * vec_y;
+ index++;
+ }
}
- }
- /* generate faces */
- index = 0;
- for (y = 0; y < height; y++) {
- for (x = 0; x < width; x++) {
- /* initialise two faces for this (x,y) */
- grid_face *f1 = g->faces + index;
- grid_face *f2 = f1 + 1;
- f1->edges = NULL;
- f1->order = 3;
- f1->dots = snewn(f1->order, grid_dot*);
- f1->has_incentre = FALSE;
- f2->edges = NULL;
- f2->order = 3;
- f2->dots = snewn(f2->order, grid_dot*);
- f2->has_incentre = FALSE;
-
- /* face descriptions depend on whether the row-number is
- * odd or even */
+ /* generate faces */
+ index = 0;
+ for (y = 0; y < height; y++) {
+ for (x = 0; x < width; x++) {
+ /* initialise two faces for this (x,y) */
+ grid_face *f1 = g->faces + index;
+ grid_face *f2 = f1 + 1;
+ f1->edges = NULL;
+ f1->order = 3;
+ f1->dots = snewn(f1->order, grid_dot*);
+ f1->has_incentre = FALSE;
+ f2->edges = NULL;
+ f2->order = 3;
+ f2->dots = snewn(f2->order, grid_dot*);
+ f2->has_incentre = FALSE;
+
+ /* face descriptions depend on whether the row-number is
+ * odd or even */
+ if (y % 2) {
+ f1->dots[0] = g->dots + y * w + x;
+ f1->dots[1] = g->dots + (y + 1) * w + x + 1;
+ f1->dots[2] = g->dots + (y + 1) * w + x;
+ f2->dots[0] = g->dots + y * w + x;
+ f2->dots[1] = g->dots + y * w + x + 1;
+ f2->dots[2] = g->dots + (y + 1) * w + x + 1;
+ } else {
+ f1->dots[0] = g->dots + y * w + x;
+ f1->dots[1] = g->dots + y * w + x + 1;
+ f1->dots[2] = g->dots + (y + 1) * w + x;
+ f2->dots[0] = g->dots + y * w + x + 1;
+ f2->dots[1] = g->dots + (y + 1) * w + x + 1;
+ f2->dots[2] = g->dots + (y + 1) * w + x;
+ }
+ index += 2;
+ }
+ }
+ } else {
+ /*
+ * New-style approach, in which there are never any 'ears',
+ * and if height is even then the grid is nicely 4-way
+ * symmetric.
+ *
+ * Example new-style grids:
+ *
+ * 5x5t1:0_21120b11a1a01a1a00c1a0b211021c1h1a2a1a0a
+ * 5x6t1:0_a1212c22c2a02a2f22a0c12a110d0e1c0c0a101121a1
+ */
+ tree234 *points = newtree234(grid_point_cmp_fn);
+ /* Upper bounds - don't have to be exact */
+ int max_faces = height * (2*width+1);
+ int max_dots = (height+1) * (width+1) * 4;
+
+ g->faces = snewn(max_faces, grid_face);
+ g->dots = snewn(max_dots, grid_dot);
+
+ for (y = 0; y < height; y++) {
+ /*
+ * Each row contains (width+1) triangles one way up, and
+ * (width) triangles the other way up. Which way up is
+ * which varies with parity of y. Also, the dots around
+ * each face will flip direction with parity of y, so we
+ * set up n1 and n2 to cope with that easily.
+ */
+ int y0, y1, n1, n2;
+ y0 = y1 = y * vec_y;
if (y % 2) {
- f1->dots[0] = g->dots + y * w + x;
- f1->dots[1] = g->dots + (y + 1) * w + x + 1;
- f1->dots[2] = g->dots + (y + 1) * w + x;
- f2->dots[0] = g->dots + y * w + x;
- f2->dots[1] = g->dots + y * w + x + 1;
- f2->dots[2] = g->dots + (y + 1) * w + x + 1;
+ y1 += vec_y;
+ n1 = 2; n2 = 1;
} else {
- f1->dots[0] = g->dots + y * w + x;
- f1->dots[1] = g->dots + y * w + x + 1;
- f1->dots[2] = g->dots + (y + 1) * w + x;
- f2->dots[0] = g->dots + y * w + x + 1;
- f2->dots[1] = g->dots + (y + 1) * w + x + 1;
- f2->dots[2] = g->dots + (y + 1) * w + x;
+ y0 += vec_y;
+ n1 = 1; n2 = 2;
+ }
+
+ for (x = 0; x <= width; x++) {
+ int x0 = 2*x * vec_x, x1 = x0 + vec_x, x2 = x1 + vec_x;
+
+ /*
+ * If the grid has odd height, then we skip the first
+ * and last triangles on this row, otherwise they'll
+ * end up as ears.
+ */
+ if (height % 2 == 1 && y == height-1 && (x == 0 || x == width))
+ continue;
+
+ grid_face_add_new(g, 3);
+ grid_face_set_dot(g, grid_get_dot(g, points, x0, y0), 0);
+ grid_face_set_dot(g, grid_get_dot(g, points, x1, y1), n1);
+ grid_face_set_dot(g, grid_get_dot(g, points, x2, y0), n2);
+ }
+
+ for (x = 0; x < width; x++) {
+ int x0 = (2*x+1) * vec_x, x1 = x0 + vec_x, x2 = x1 + vec_x;
+
+ grid_face_add_new(g, 3);
+ grid_face_set_dot(g, grid_get_dot(g, points, x0, y1), 0);
+ grid_face_set_dot(g, grid_get_dot(g, points, x1, y0), n2);
+ grid_face_set_dot(g, grid_get_dot(g, points, x2, y1), n1);
}
- index += 2;
}
+
+ freetree234(points);
+ assert(g->num_faces <= max_faces);
+ assert(g->num_dots <= max_dots);
}
grid_make_consistent(g);
#define SNUBSQUARE_A 15
#define SNUBSQUARE_B 26
-void grid_size_snubsquare(int width, int height,
+static void grid_size_snubsquare(int width, int height,
int *tilesize, int *xextent, int *yextent)
{
int a = SNUBSQUARE_A;
*yextent = (a+b) * (height-1) + a + b;
}
-grid *grid_new_snubsquare(int width, int height, char *desc)
+static grid *grid_new_snubsquare(int width, int height, const char *desc)
{
int x, y;
int a = SNUBSQUARE_A;
#define CAIRO_A 14
#define CAIRO_B 31
-void grid_size_cairo(int width, int height,
+static void grid_size_cairo(int width, int height,
int *tilesize, int *xextent, int *yextent)
{
int b = CAIRO_B; /* a unused in determining grid size. */
*yextent = 2*b*(height-1) + 2*b;
}
-grid *grid_new_cairo(int width, int height, char *desc)
+static grid *grid_new_cairo(int width, int height, const char *desc)
{
int x, y;
int a = CAIRO_A;
#define GREATHEX_A 15
#define GREATHEX_B 26
-void grid_size_greathexagonal(int width, int height,
+static void grid_size_greathexagonal(int width, int height,
int *tilesize, int *xextent, int *yextent)
{
int a = GREATHEX_A;
*yextent = (2*a + 2*b) * (height-1) + 3*b + a;
}
-grid *grid_new_greathexagonal(int width, int height, char *desc)
+static grid *grid_new_greathexagonal(int width, int height, const char *desc)
{
int x, y;
int a = GREATHEX_A;
#define OCTAGONAL_A 29
#define OCTAGONAL_B 41
-void grid_size_octagonal(int width, int height,
+static void grid_size_octagonal(int width, int height,
int *tilesize, int *xextent, int *yextent)
{
int a = OCTAGONAL_A;
*yextent = (2*a + b) * height;
}
-grid *grid_new_octagonal(int width, int height, char *desc)
+static grid *grid_new_octagonal(int width, int height, const char *desc)
{
int x, y;
int a = OCTAGONAL_A;
#define KITE_A 15
#define KITE_B 26
-void grid_size_kites(int width, int height,
+static void grid_size_kites(int width, int height,
int *tilesize, int *xextent, int *yextent)
{
int a = KITE_A;
*yextent = 6*a * (height-1) + 8*a;
}
-grid *grid_new_kites(int width, int height, char *desc)
+static grid *grid_new_kites(int width, int height, const char *desc)
{
int x, y;
int a = KITE_A;
#define FLORET_PX 75
#define FLORET_PY -26
-void grid_size_floret(int width, int height,
+static void grid_size_floret(int width, int height,
int *tilesize, int *xextent, int *yextent)
{
int px = FLORET_PX, py = FLORET_PY; /* |( 75, -26)| = 79.43 */
*yextent = (5*qy-4*py) * (height-1) + 4*qy + 2*ry;
}
-grid *grid_new_floret(int width, int height, char *desc)
+static grid *grid_new_floret(int width, int height, const char *desc)
{
int x, y;
/* Vectors for sides; weird numbers needed to keep puzzle aligned with window
#define DODEC_A 15
#define DODEC_B 26
-void grid_size_dodecagonal(int width, int height,
+static void grid_size_dodecagonal(int width, int height,
int *tilesize, int *xextent, int *yextent)
{
int a = DODEC_A;
*yextent = (3*a + 2*b) * (height-1) + 2*(2*a + b);
}
-grid *grid_new_dodecagonal(int width, int height, char *desc)
+static grid *grid_new_dodecagonal(int width, int height, const char *desc)
{
int x, y;
int a = DODEC_A;
return g;
}
-void grid_size_greatdodecagonal(int width, int height,
+static void grid_size_greatdodecagonal(int width, int height,
int *tilesize, int *xextent, int *yextent)
{
int a = DODEC_A;
*yextent = (3*a + 3*b) * (height-1) + 2*(2*a + b);
}
-grid *grid_new_greatdodecagonal(int width, int height, char *desc)
+static grid *grid_new_greatdodecagonal(int width, int height, const char *desc)
{
int x, y;
/* Vector for side of triangle - ratio is close to sqrt(3) */
return g;
}
+static void grid_size_greatgreatdodecagonal(int width, int height,
+ int *tilesize, int *xextent, int *yextent)
+{
+ int a = DODEC_A;
+ int b = DODEC_B;
+
+ *tilesize = DODEC_TILESIZE;
+ *xextent = (4*a + 4*b) * (width-1) + 2*(2*a + b) + 2*a + 2*b;
+ *yextent = (6*a + 2*b) * (height-1) + 2*(2*a + b);
+}
+
+static grid *grid_new_greatgreatdodecagonal(int width, int height, const char *desc)
+{
+ int x, y;
+ /* Vector for side of triangle - ratio is close to sqrt(3) */
+ int a = DODEC_A;
+ int b = DODEC_B;
+
+ /* Upper bounds - don't have to be exact */
+ int max_faces = 50 * width * height;
+ int max_dots = 300 * width * height;
+
+ tree234 *points;
+
+ grid *g = grid_empty();
+ g->tilesize = DODEC_TILESIZE;
+ g->faces = snewn(max_faces, grid_face);
+ g->dots = snewn(max_dots, grid_dot);
+
+ points = newtree234(grid_point_cmp_fn);
+
+ for (y = 0; y < height; y++) {
+ for (x = 0; x < width; x++) {
+ grid_dot *d;
+ /* centre of dodecagon */
+ int px = (4*a + 4*b) * x;
+ int py = (6*a + 2*b) * y;
+ if (y % 2)
+ px += 2*a + 2*b;
+
+ /* dodecagon */
+ grid_face_add_new(g, 12);
+ d = grid_get_dot(g, points, px + ( a ), py - (2*a + b)); grid_face_set_dot(g, d, 0);
+ d = grid_get_dot(g, points, px + ( a + b), py - ( a + b)); grid_face_set_dot(g, d, 1);
+ d = grid_get_dot(g, points, px + (2*a + b), py - ( a )); grid_face_set_dot(g, d, 2);
+ d = grid_get_dot(g, points, px + (2*a + b), py + ( a )); grid_face_set_dot(g, d, 3);
+ d = grid_get_dot(g, points, px + ( a + b), py + ( a + b)); grid_face_set_dot(g, d, 4);
+ d = grid_get_dot(g, points, px + ( a ), py + (2*a + b)); grid_face_set_dot(g, d, 5);
+ d = grid_get_dot(g, points, px - ( a ), py + (2*a + b)); grid_face_set_dot(g, d, 6);
+ d = grid_get_dot(g, points, px - ( a + b), py + ( a + b)); grid_face_set_dot(g, d, 7);
+ d = grid_get_dot(g, points, px - (2*a + b), py + ( a )); grid_face_set_dot(g, d, 8);
+ d = grid_get_dot(g, points, px - (2*a + b), py - ( a )); grid_face_set_dot(g, d, 9);
+ d = grid_get_dot(g, points, px - ( a + b), py - ( a + b)); grid_face_set_dot(g, d, 10);
+ d = grid_get_dot(g, points, px - ( a ), py - (2*a + b)); grid_face_set_dot(g, d, 11);
+
+ /* hexagon on top right of dodecagon */
+ if (y && (x < width - 1 || !(y % 2))) {
+ grid_face_add_new(g, 6);
+ d = grid_get_dot(g, points, px + (a + 2*b), py - (4*a + b)); grid_face_set_dot(g, d, 0);
+ d = grid_get_dot(g, points, px + (a + 2*b), py - (2*a + b)); grid_face_set_dot(g, d, 1);
+ d = grid_get_dot(g, points, px + (a + b), py - ( a + b)); grid_face_set_dot(g, d, 2);
+ d = grid_get_dot(g, points, px + (a ), py - (2*a + b)); grid_face_set_dot(g, d, 3);
+ d = grid_get_dot(g, points, px + (a ), py - (4*a + b)); grid_face_set_dot(g, d, 4);
+ d = grid_get_dot(g, points, px + (a + b), py - (5*a + b)); grid_face_set_dot(g, d, 5);
+ }
+
+ /* hexagon on right of dodecagon*/
+ if (x < width - 1) {
+ grid_face_add_new(g, 6);
+ d = grid_get_dot(g, points, px + (2*a + 3*b), py - a); grid_face_set_dot(g, d, 0);
+ d = grid_get_dot(g, points, px + (2*a + 3*b), py + a); grid_face_set_dot(g, d, 1);
+ d = grid_get_dot(g, points, px + (2*a + 2*b), py + 2*a); grid_face_set_dot(g, d, 2);
+ d = grid_get_dot(g, points, px + (2*a + b), py + a); grid_face_set_dot(g, d, 3);
+ d = grid_get_dot(g, points, px + (2*a + b), py - a); grid_face_set_dot(g, d, 4);
+ d = grid_get_dot(g, points, px + (2*a + 2*b), py - 2*a); grid_face_set_dot(g, d, 5);
+ }
+
+ /* hexagon on bottom right of dodecagon */
+ if ((y < height - 1) && (x < width - 1 || !(y % 2))) {
+ grid_face_add_new(g, 6);
+ d = grid_get_dot(g, points, px + (a + 2*b), py + (2*a + b)); grid_face_set_dot(g, d, 0);
+ d = grid_get_dot(g, points, px + (a + 2*b), py + (4*a + b)); grid_face_set_dot(g, d, 1);
+ d = grid_get_dot(g, points, px + (a + b), py + (5*a + b)); grid_face_set_dot(g, d, 2);
+ d = grid_get_dot(g, points, px + (a ), py + (4*a + b)); grid_face_set_dot(g, d, 3);
+ d = grid_get_dot(g, points, px + (a ), py + (2*a + b)); grid_face_set_dot(g, d, 4);
+ d = grid_get_dot(g, points, px + (a + b), py + ( a + b)); grid_face_set_dot(g, d, 5);
+ }
+
+ /* square on top right of dodecagon */
+ if (y && (x < width - 1 )) {
+ grid_face_add_new(g, 4);
+ d = grid_get_dot(g, points, px + ( a + 2*b), py - (2*a + b)); grid_face_set_dot(g, d, 0);
+ d = grid_get_dot(g, points, px + (2*a + 2*b), py - (2*a )); grid_face_set_dot(g, d, 1);
+ d = grid_get_dot(g, points, px + (2*a + b), py - ( a )); grid_face_set_dot(g, d, 2);
+ d = grid_get_dot(g, points, px + ( a + b), py - ( a + b)); grid_face_set_dot(g, d, 3);
+ }
+
+ /* square on bottom right of dodecagon */
+ if ((y < height - 1) && (x < width - 1 )) {
+ grid_face_add_new(g, 4);
+ d = grid_get_dot(g, points, px + (2*a + 2*b), py + (2*a )); grid_face_set_dot(g, d, 0);
+ d = grid_get_dot(g, points, px + ( a + 2*b), py + (2*a + b)); grid_face_set_dot(g, d, 1);
+ d = grid_get_dot(g, points, px + ( a + b), py + ( a + b)); grid_face_set_dot(g, d, 2);
+ d = grid_get_dot(g, points, px + (2*a + b), py + ( a )); grid_face_set_dot(g, d, 3);
+ }
+
+ /* square below dodecagon */
+ if ((y < height - 1) && (x < width - 1 || !(y % 2)) && (x > 0 || (y % 2))) {
+ grid_face_add_new(g, 4);
+ d = grid_get_dot(g, points, px + a, py + (2*a + b)); grid_face_set_dot(g, d, 0);
+ d = grid_get_dot(g, points, px + a, py + (4*a + b)); grid_face_set_dot(g, d, 1);
+ d = grid_get_dot(g, points, px - a, py + (4*a + b)); grid_face_set_dot(g, d, 2);
+ d = grid_get_dot(g, points, px - a, py + (2*a + b)); grid_face_set_dot(g, d, 3);
+ }
+
+ /* square on bottom left of dodecagon */
+ if (x && (y < height - 1)) {
+ grid_face_add_new(g, 4);
+ d = grid_get_dot(g, points, px - (2*a + b), py + ( a )); grid_face_set_dot(g, d, 0);
+ d = grid_get_dot(g, points, px - ( a + b), py + ( a + b)); grid_face_set_dot(g, d, 1);
+ d = grid_get_dot(g, points, px - ( a + 2*b), py + (2*a + b)); grid_face_set_dot(g, d, 2);
+ d = grid_get_dot(g, points, px - (2*a + 2*b), py + (2*a )); grid_face_set_dot(g, d, 3);
+ }
+
+ /* square on top left of dodecagon */
+ if (x && y) {
+ grid_face_add_new(g, 4);
+ d = grid_get_dot(g, points, px - ( a + b), py - ( a + b)); grid_face_set_dot(g, d, 0);
+ d = grid_get_dot(g, points, px - (2*a + b), py - ( a )); grid_face_set_dot(g, d, 1);
+ d = grid_get_dot(g, points, px - (2*a + 2*b), py - (2*a )); grid_face_set_dot(g, d, 2);
+ d = grid_get_dot(g, points, px - ( a + 2*b), py - (2*a + b)); grid_face_set_dot(g, d, 3);
+
+ }
+
+ /* square above dodecagon */
+ if (y && (x < width - 1 || !(y % 2)) && (x > 0 || (y % 2))) {
+ grid_face_add_new(g, 4);
+ d = grid_get_dot(g, points, px + a, py - (4*a + b)); grid_face_set_dot(g, d, 0);
+ d = grid_get_dot(g, points, px + a, py - (2*a + b)); grid_face_set_dot(g, d, 1);
+ d = grid_get_dot(g, points, px - a, py - (2*a + b)); grid_face_set_dot(g, d, 2);
+ d = grid_get_dot(g, points, px - a, py - (4*a + b)); grid_face_set_dot(g, d, 3);
+ }
+
+ /* upper triangle (v) */
+ if (y && (x < width - 1)) {
+ grid_face_add_new(g, 3);
+ d = grid_get_dot(g, points, px + (3*a + 2*b), py - (2*a + b)); grid_face_set_dot(g, d, 0);
+ d = grid_get_dot(g, points, px + (2*a + 2*b), py - (2*a )); grid_face_set_dot(g, d, 1);
+ d = grid_get_dot(g, points, px + ( a + 2*b), py - (2*a + b)); grid_face_set_dot(g, d, 2);
+ }
+
+ /* lower triangle (^) */
+ if ((y < height - 1) && (x < width - 1)) {
+ grid_face_add_new(g, 3);
+ d = grid_get_dot(g, points, px + (3*a + 2*b), py + (2*a + b)); grid_face_set_dot(g, d, 0);
+ d = grid_get_dot(g, points, px + ( a + 2*b), py + (2*a + b)); grid_face_set_dot(g, d, 1);
+ d = grid_get_dot(g, points, px + (2*a + 2*b), py + (2*a )); grid_face_set_dot(g, d, 2);
+ }
+ }
+ }
+
+ freetree234(points);
+ assert(g->num_faces <= max_faces);
+ assert(g->num_dots <= max_dots);
+
+ grid_make_consistent(g);
+ return g;
+}
+
typedef struct setface_ctx
{
int xmin, xmax, ymin, ymax;
- int aoff;
grid *g;
tree234 *points;
} setface_ctx;
-double round(double r)
+static double round_int_nearest_away(double r)
{
return (r > 0.0) ? floor(r + 0.5) : ceil(r - 0.5);
}
-int set_faces(penrose_state *state, vector *vs, int n, int depth)
+static int set_faces(penrose_state *state, vector *vs, int n, int depth)
{
setface_ctx *sf_ctx = (setface_ctx *)state->ctx;
int i;
int xs[4], ys[4];
- double cosa = cos(sf_ctx->aoff * PI / 180.0);
- double sina = sin(sf_ctx->aoff * PI / 180.0);
if (depth < state->max_depth) return 0;
#ifdef DEBUG_PENROSE
for (i = 0; i < n; i++) {
double tx = v_x(vs, i), ty = v_y(vs, i);
- xs[i] = (int)round( tx*cosa + ty*sina);
- ys[i] = (int)round(-tx*sina + ty*cosa);
+ xs[i] = (int)round_int_nearest_away(tx);
+ ys[i] = (int)round_int_nearest_away(ty);
if (xs[i] < sf_ctx->xmin || xs[i] > sf_ctx->xmax) return 0;
if (ys[i] < sf_ctx->ymin || ys[i] > sf_ctx->ymax) return 0;
#define PENROSE_TILESIZE 100
-void grid_size_penrose(int width, int height,
+static void grid_size_penrose(int width, int height,
int *tilesize, int *xextent, int *yextent)
{
int l = PENROSE_TILESIZE;
*yextent = l * height;
}
+static grid *grid_new_penrose(int width, int height, int which, const char *desc); /* forward reference */
+
static char *grid_new_desc_penrose(grid_type type, int width, int height, random_state *rs)
{
int tilesize = PENROSE_TILESIZE, startsz, depth, xoff, yoff, aoff;
int inner_radius;
char gd[255];
int which = (type == GRID_PENROSE_P2 ? PENROSE_P2 : PENROSE_P3);
+ grid *g;
- /* We want to produce a random bit of penrose tiling, so we calculate
- * a random offset (within the patch that penrose.c calculates for us)
- * and an angle (multiple of 36) to rotate the patch. */
-
- penrose_calculate_size(which, tilesize, width, height,
- &outer_radius, &startsz, &depth);
-
- /* Calculate radius of (circumcircle of) patch, subtract from
- * radius calculated. */
- inner_radius = (int)(outer_radius - sqrt(width*width + height*height));
-
- /* Pick a random offset (the easy way: choose within outer square,
- * discarding while it's outside the circle) */
- do {
- xoff = random_upto(rs, 2*inner_radius) - inner_radius;
- yoff = random_upto(rs, 2*inner_radius) - inner_radius;
- } while (sqrt(xoff*xoff+yoff*yoff) > inner_radius);
-
- aoff = random_upto(rs, 360/36) * 36;
-
- debug(("grid_desc: ts %d, %dx%d patch, orad %2.2f irad %d",
- tilesize, width, height, outer_radius, inner_radius));
- debug((" -> xoff %d yoff %d aoff %d", xoff, yoff, aoff));
-
- sprintf(gd, "G%d,%d,%d", xoff, yoff, aoff);
+ while (1) {
+ /* We want to produce a random bit of penrose tiling, so we
+ * calculate a random offset (within the patch that penrose.c
+ * calculates for us) and an angle (multiple of 36) to rotate
+ * the patch. */
+
+ penrose_calculate_size(which, tilesize, width, height,
+ &outer_radius, &startsz, &depth);
+
+ /* Calculate radius of (circumcircle of) patch, subtract from
+ * radius calculated. */
+ inner_radius = (int)(outer_radius - sqrt(width*width + height*height));
+
+ /* Pick a random offset (the easy way: choose within outer
+ * square, discarding while it's outside the circle) */
+ do {
+ xoff = random_upto(rs, 2*inner_radius) - inner_radius;
+ yoff = random_upto(rs, 2*inner_radius) - inner_radius;
+ } while (sqrt(xoff*xoff+yoff*yoff) > inner_radius);
+
+ aoff = random_upto(rs, 360/36) * 36;
+
+ debug(("grid_desc: ts %d, %dx%d patch, orad %2.2f irad %d",
+ tilesize, width, height, outer_radius, inner_radius));
+ debug((" -> xoff %d yoff %d aoff %d", xoff, yoff, aoff));
+
+ sprintf(gd, "G%d,%d,%d", xoff, yoff, aoff);
+
+ /*
+ * Now test-generate our grid, to make sure it actually
+ * produces something.
+ */
+ g = grid_new_penrose(width, height, which, gd);
+ if (g) {
+ grid_free(g);
+ break;
+ }
+ /* If not, go back to the top of this while loop and try again
+ * with a different random offset. */
+ }
return dupstr(gd);
}
-static char *grid_validate_desc_penrose(grid_type type, int width, int height, char *desc)
+static char *grid_validate_desc_penrose(grid_type type, int width, int height,
+ const char *desc)
{
int tilesize = PENROSE_TILESIZE, startsz, depth, xoff, yoff, aoff, inner_radius;
double outer_radius;
int which = (type == GRID_PENROSE_P2 ? PENROSE_P2 : PENROSE_P3);
+ grid *g;
if (!desc)
return "Missing grid description string.";
if ((aoff % 36) != 0 || aoff < 0 || aoff >= 360)
return "Angle offset out of bounds.";
+ /*
+ * Test-generate to ensure these parameters don't end us up with
+ * no grid at all.
+ */
+ g = grid_new_penrose(width, height, which, desc);
+ if (!g)
+ return "Patch coordinates do not identify a usable grid fragment";
+ grid_free(g);
+
return NULL;
}
* to pick.
*/
-static grid *grid_new_penrose(int width, int height, int which, char *desc)
+static grid *grid_new_penrose(int width, int height, int which, const char *desc)
{
int max_faces, max_dots, tilesize = PENROSE_TILESIZE;
- int xsz, ysz, xoff, yoff;
+ int xsz, ysz, xoff, yoff, aoff;
double rradius;
tree234 *points;
sf_ctx.points = points;
if (desc != NULL) {
- if (sscanf(desc, "G%d,%d,%d", &xoff, &yoff, &sf_ctx.aoff) != 3)
+ if (sscanf(desc, "G%d,%d,%d", &xoff, &yoff, &aoff) != 3)
assert(!"Invalid grid description.");
} else {
- xoff = yoff = 0;
+ xoff = yoff = aoff = 0;
}
xsz = width * tilesize;
debug(("penrose: x range (%f --> %f), y range (%f --> %f)",
sf_ctx.xmin, sf_ctx.xmax, sf_ctx.ymin, sf_ctx.ymax));
- penrose(&ps, which);
+ penrose(&ps, which, aoff);
freetree234(points);
assert(g->num_faces <= max_faces);
debug(("penrose: %d faces total (equivalent to %d wide by %d high)",
g->num_faces, g->num_faces/height, g->num_faces/width));
+ /*
+ * Return NULL if we ended up with an empty grid, either because
+ * the initial generation was over too small a rectangle to
+ * encompass any face or because grid_trim_vigorously ended up
+ * removing absolutely everything.
+ */
+ if (g->num_faces == 0 || g->num_dots == 0) {
+ grid_free(g);
+ return NULL;
+ }
grid_trim_vigorously(g);
+ if (g->num_faces == 0 || g->num_dots == 0) {
+ grid_free(g);
+ return NULL;
+ }
+
grid_make_consistent(g);
/*
return g;
}
-void grid_size_penrose_p2_kite(int width, int height,
+static void grid_size_penrose_p2_kite(int width, int height,
int *tilesize, int *xextent, int *yextent)
{
grid_size_penrose(width, height, tilesize, xextent, yextent);
}
-void grid_size_penrose_p3_thick(int width, int height,
+static void grid_size_penrose_p3_thick(int width, int height,
int *tilesize, int *xextent, int *yextent)
{
grid_size_penrose(width, height, tilesize, xextent, yextent);
}
-grid *grid_new_penrose_p2_kite(int width, int height, char *desc)
+static grid *grid_new_penrose_p2_kite(int width, int height, const char *desc)
{
return grid_new_penrose(width, height, PENROSE_P2, desc);
}
-grid *grid_new_penrose_p3_thick(int width, int height, char *desc)
+static grid *grid_new_penrose_p3_thick(int width, int height, const char *desc)
{
return grid_new_penrose(width, height, PENROSE_P3, desc);
}
#define FNNEW(upper,lower) &grid_new_ ## lower,
#define FNSZ(upper,lower) &grid_size_ ## lower,
-static grid *(*(grid_news[]))(int, int, char*) = { GRIDGEN_LIST(FNNEW) };
+static grid *(*(grid_news[]))(int, int, const char*) = { GRIDGEN_LIST(FNNEW) };
static void(*(grid_sizes[]))(int, int, int*, int*, int*) = { GRIDGEN_LIST(FNSZ) };
char *grid_new_desc(grid_type type, int width, int height, random_state *rs)
{
- if (type != GRID_PENROSE_P2 && type != GRID_PENROSE_P3)
+ if (type == GRID_PENROSE_P2 || type == GRID_PENROSE_P3) {
+ return grid_new_desc_penrose(type, width, height, rs);
+ } else if (type == GRID_TRIANGULAR) {
+ return dupstr("0"); /* up-to-date version of triangular grid */
+ } else {
return NULL;
-
- return grid_new_desc_penrose(type, width, height, rs);
+ }
}
-char *grid_validate_desc(grid_type type, int width, int height, char *desc)
+char *grid_validate_desc(grid_type type, int width, int height,
+ const char *desc)
{
- if (type != GRID_PENROSE_P2 && type != GRID_PENROSE_P3) {
+ if (type == GRID_PENROSE_P2 || type == GRID_PENROSE_P3) {
+ return grid_validate_desc_penrose(type, width, height, desc);
+ } else if (type == GRID_TRIANGULAR) {
+ return grid_validate_desc_triangular(type, width, height, desc);
+ } else {
if (desc != NULL)
return "Grid description strings not used with this grid type";
return NULL;
}
-
- return grid_validate_desc_penrose(type, width, height, desc);
}
-grid *grid_new(grid_type type, int width, int height, char *desc)
+grid *grid_new(grid_type type, int width, int height, const char *desc)
{
char *err = grid_validate_desc(type, width, height, desc);
if (err) assert(!"Invalid grid description.");