From e37d915f447e02b52236cee454dfe68749c6d876 Mon Sep 17 00:00:00 2001 From: Simon Tatham Date: Sun, 23 Apr 2017 07:41:46 +0100 Subject: [PATCH] New Loopy tiling: 'Great Great Dodecagonal'. Officially known as the '3-4-6-12 tiling', according to, e.g., https://en.wikipedia.org/wiki/3-4-6-12_tiling . Thanks to Michael Quevillon for contributing this patch (and for choosing a less hard-to-remember name for the tiling :-). --- grid.c | 169 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++ grid.h | 1 + loopy.c | 3 + 3 files changed, 173 insertions(+) diff --git a/grid.c b/grid.c index 6a90c99..4929b5c 100644 --- a/grid.c +++ b/grid.c @@ -2571,6 +2571,175 @@ static grid *grid_new_greatdodecagonal(int width, int height, const 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; diff --git a/grid.h b/grid.h index 17d0aa1..fb8ac48 100644 --- a/grid.h +++ b/grid.h @@ -105,6 +105,7 @@ typedef struct grid { A(FLORET,floret) \ A(DODECAGONAL,dodecagonal) \ A(GREATDODECAGONAL,greatdodecagonal) \ + A(GREATGREATDODECAGONAL,greatgreatdodecagonal) \ A(PENROSE_P2,penrose_p2_kite) \ A(PENROSE_P3,penrose_p3_thick) diff --git a/loopy.c b/loopy.c index 44d51ee..15623ee 100644 --- a/loopy.c +++ b/loopy.c @@ -258,6 +258,7 @@ static void check_caches(const solver_state* sstate); A(Great-Dodecagonal,GRID_GREATDODECAGONAL,2,2) \ A(Penrose (kite/dart),GRID_PENROSE_P2,3,3) \ A(Penrose (rhombs),GRID_PENROSE_P3,3,3) + A(Great-Great-Dodecagonal,GRID_GREATGREATDODECAGONAL,2,2) \ #define GRID_NAME(title,type,amin,omin) #title, #define GRID_CONFIG(title,type,amin,omin) ":" #title @@ -505,6 +506,7 @@ static const game_params presets[] = { { 3, 3, DIFF_HARD, 8 }, { 3, 3, DIFF_HARD, 9 }, { 3, 3, DIFF_HARD, 10 }, + { 3, 2, DIFF_HARD, 13 }, { 6, 6, DIFF_HARD, 11 }, { 6, 6, DIFF_HARD, 12 }, #else @@ -524,6 +526,7 @@ static const game_params presets[] = { { 5, 5, DIFF_HARD, 8 }, { 5, 4, DIFF_HARD, 9 }, { 5, 4, DIFF_HARD, 10 }, + { 5, 3, DIFF_HARD, 13 }, { 10, 10, DIFF_HARD, 11 }, { 10, 10, DIFF_HARD, 12 } #endif -- 2.30.2