X-Git-Url: http://www.chiark.greenend.org.uk/ucgi/~ian/git?a=blobdiff_plain;f=grid.c;h=4929b5c7d3c99547183543560a9180f815c555df;hb=e37d915f447e02b52236cee454dfe68749c6d876;hp=f7c6a5c0d5cfdc78e886a895ad84113240d73a8e;hpb=62c20496bf106b1034f4be95bdb7723c3ec78d00;p=sgt-puzzles.git diff --git a/grid.c b/grid.c index f7c6a5c..4929b5c 100644 --- a/grid.c +++ b/grid.c @@ -12,7 +12,7 @@ #include #include #include -#include +#include #include "puzzles.h" #include "tree234.h" @@ -52,7 +52,7 @@ void grid_free(grid *g) /* 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; @@ -225,6 +225,8 @@ xmlns:xlink=\"http://www.w3.org/1999/xlink\">\n\n"); #endif #ifdef SVG_GRID +#include + static void grid_try_svg(grid *g, int which) { char *svg = getenv("PUZZLES_SVG_GRID"); @@ -453,6 +455,14 @@ static void grid_trim_vigorously(grid *g) for (i = newdots = 0; i < g->num_dots; i++) dots[i] = (dots[i] ? newdots++ : -1); + /* + * Free the dynamically allocated 'dots' pointer lists in faces + * we're going to discard. + */ + for (i = 0; i < g->num_faces; i++) + if (faces[i] < 0) + sfree(g->faces[i].dots); + /* * Go through and compact the arrays. */ @@ -1059,7 +1069,7 @@ void grid_find_incentre(grid_face *f) 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]; @@ -1260,7 +1270,15 @@ void grid_find_incentre(grid_face *f) } 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; /* @@ -1369,7 +1387,7 @@ void grid_find_incentre(grid_face *f) #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; @@ -1379,7 +1397,7 @@ void grid_size_square(int width, int height, *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 */ @@ -1431,7 +1449,7 @@ grid *grid_new_square(int width, int height, char *desc) #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; @@ -1442,7 +1460,7 @@ void grid_size_honeycomb(int width, int height, *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; @@ -1500,22 +1518,41 @@ grid *grid_new_honeycomb(int width, int height, char *desc) #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; @@ -1529,59 +1566,144 @@ grid *grid_new_triangular(int width, int height, char *desc) 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*); - f2->edges = NULL; - f2->order = 3; - f2->dots = snewn(f2->order, grid_dot*); - - /* 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); @@ -1593,7 +1715,7 @@ grid *grid_new_triangular(int width, int height, char *desc) #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; @@ -1604,7 +1726,7 @@ void grid_size_snubsquare(int width, int height, *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; @@ -1707,7 +1829,7 @@ grid *grid_new_snubsquare(int width, int height, char *desc) #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. */ @@ -1717,7 +1839,7 @@ void grid_size_cairo(int width, int height, *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; @@ -1813,7 +1935,7 @@ grid *grid_new_cairo(int width, int height, char *desc) #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; @@ -1824,7 +1946,7 @@ void grid_size_greathexagonal(int width, int height, *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; @@ -1943,7 +2065,7 @@ grid *grid_new_greathexagonal(int width, int height, char *desc) #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; @@ -1954,7 +2076,7 @@ void grid_size_octagonal(int width, int height, *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; @@ -2026,7 +2148,7 @@ grid *grid_new_octagonal(int width, int height, char *desc) #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; @@ -2037,7 +2159,7 @@ void grid_size_kites(int width, int height, *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; @@ -2148,7 +2270,7 @@ grid *grid_new_kites(int width, int height, char *desc) #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 */ @@ -2161,7 +2283,7 @@ void grid_size_floret(int width, int height, *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 @@ -2255,7 +2377,7 @@ grid *grid_new_floret(int width, int height, char *desc) #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; @@ -2266,7 +2388,7 @@ void grid_size_dodecagonal(int width, int height, *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; @@ -2335,7 +2457,7 @@ grid *grid_new_dodecagonal(int width, int height, char *desc) 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; @@ -2346,7 +2468,7 @@ void grid_size_greatdodecagonal(int width, int height, *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) */ @@ -2449,27 +2571,193 @@ grid *grid_new_greatdodecagonal(int width, int height, char *desc) 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 @@ -2479,8 +2767,8 @@ int set_faces(penrose_state *state, vector *vs, int n, int depth) 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; @@ -2502,7 +2790,7 @@ int set_faces(penrose_state *state, vector *vs, int n, int depth) #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; @@ -2512,6 +2800,8 @@ void grid_size_penrose(int width, int height, *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; @@ -2519,41 +2809,59 @@ static char *grid_new_desc_penrose(grid_type type, int width, int height, random 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."; @@ -2570,6 +2878,15 @@ static char *grid_validate_desc_penrose(grid_type type, int width, int height, c 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; } @@ -2579,10 +2896,10 @@ static char *grid_validate_desc_penrose(grid_type type, int width, int height, c * 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; @@ -2615,10 +2932,10 @@ static grid *grid_new_penrose(int width, int height, int which, char *desc) 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; @@ -2634,7 +2951,7 @@ static grid *grid_new_penrose(int width, int height, int which, char *desc) 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); @@ -2643,7 +2960,22 @@ static grid *grid_new_penrose(int width, int height, int which, char *desc) 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); /* @@ -2659,24 +2991,24 @@ static grid *grid_new_penrose(int width, int height, int which, char *desc) 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); } @@ -2686,29 +3018,35 @@ grid *grid_new_penrose_p3_thick(int width, int height, char *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.");