ref: 7b2b742be868b4a12d08f6a9f7af3e9f2923016c
parent: 621649491dbc36285c3cfc0cd577ab04a2cbf5dc
author: Simon Tatham <anakin@pobox.com>
date: Thu Feb 24 14:06:49 EST 2011
Another patch from Chris Moore implementing two more grid types, both involving dodecagons. [originally from svn r9109]
--- a/grid.c
+++ b/grid.c
@@ -1381,4 +1381,177 @@
return g;
}
+grid *grid_new_dodecagonal(int width, int height)
+{+ int x, y;
+ /* Vector for side of triangle - ratio is close to sqrt(3) */
+ int a = 15;
+ int b = 26;
+
+ /* Upper bounds - don't have to be exact */
+ int max_faces = 3 * width * height;
+ int max_dots = 14 * width * height;
+
+ tree234 *points;
+
+ grid *g = grid_new();
+ g->tilesize = b;
+ 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 + 2*b) * x;
+ int py = (3*a + 2*b) * y;
+ if (y % 2)
+ px += 2*a + 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);
+
+ /* triangle below dodecagon */
+ if ((y < height - 1 && (x < width - 1 || !(y % 2)) && (x > 0 || (y % 2)))) {+ grid_face_add_new(g, 3);
+ 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 , py + (2*a + 2*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);
+ }
+
+ /* triangle above dodecagon */
+ if ((y && (x < width - 1 || !(y % 2)) && (x > 0 || (y % 2)))) {+ grid_face_add_new(g, 3);
+ 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 , py - (2*a + 2*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);
+ }
+ }
+ }
+
+ freetree234(points);
+ assert(g->num_faces <= max_faces);
+ assert(g->num_dots <= max_dots);
+
+ grid_make_consistent(g);
+ return g;
+}
+
+grid *grid_new_greatdodecagonal(int width, int height)
+{+ int x, y;
+ /* Vector for side of triangle - ratio is close to sqrt(3) */
+ int a = 15;
+ int b = 26;
+
+ /* Upper bounds - don't have to be exact */
+ int max_faces = 30 * width * height;
+ int max_dots = 200 * width * height;
+
+ tree234 *points;
+
+ grid *g = grid_new();
+ g->tilesize = b;
+ 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 = (6*a + 2*b) * x;
+ int py = (3*a + 3*b) * y;
+ if (y % 2)
+ px += 3*a + 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 below dodecagon */
+ if (y < height - 1 && (x < width - 1 || !(y % 2)) && (x > 0 || (y % 2))) {+ grid_face_add_new(g, 6);
+ 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 + 2*a, py + (2*a + 2*b)); grid_face_set_dot(g, d, 1);
+ d = grid_get_dot(g, points, px + a, py + (2*a + 3*b)); grid_face_set_dot(g, d, 2);
+ d = grid_get_dot(g, points, px - a, py + (2*a + 3*b)); grid_face_set_dot(g, d, 3);
+ d = grid_get_dot(g, points, px - 2*a, py + (2*a + 2*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);
+ }
+
+ /* hexagon above dodecagon */
+ if (y && (x < width - 1 || !(y % 2)) && (x > 0 || (y % 2))) {+ grid_face_add_new(g, 6);
+ 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 - 2*a, py - (2*a + 2*b)); grid_face_set_dot(g, d, 1);
+ d = grid_get_dot(g, points, px - a, py - (2*a + 3*b)); grid_face_set_dot(g, d, 2);
+ d = grid_get_dot(g, points, px + a, py - (2*a + 3*b)); grid_face_set_dot(g, d, 3);
+ d = grid_get_dot(g, points, px + 2*a, py - (2*a + 2*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);
+ }
+
+ /* square on right of dodecagon */
+ if (x < width - 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 + 4*a + b, py - a); grid_face_set_dot(g, d, 1);
+ d = grid_get_dot(g, points, px + 4*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);
+ }
+
+ /* square on top right of dodecagon */
+ if (y && (x < width - 1 || !(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 + (2*a ), py - (2*a + 2*b)); grid_face_set_dot(g, d, 1);
+ d = grid_get_dot(g, points, px + (2*a + b), py - ( a + 2*b)); 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 top left of dodecagon */
+ if (y && (x || (y % 2))) {+ 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 + 2*b)); grid_face_set_dot(g, d, 1);
+ d = grid_get_dot(g, points, px - (2*a ), py - (2*a + 2*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);
+ }
+ }
+ }
+
+ freetree234(points);
+ assert(g->num_faces <= max_faces);
+ assert(g->num_dots <= max_dots);
+
+ grid_make_consistent(g);
+ return g;
+}
+
/* ----------- End of grid generators ------------- */
--- a/grid.h
+++ b/grid.h
@@ -80,8 +80,10 @@
grid *grid_new_cairo(int width, int height);
grid *grid_new_greathexagonal(int width, int height);
grid *grid_new_octagonal(int width, int height);
-grid *grid_new_floret(int width, int height);
grid *grid_new_kites(int width, int height);
+grid *grid_new_floret(int width, int height);
+grid *grid_new_dodecagonal(int width, int height);
+grid *grid_new_greatdodecagonal(int width, int height);
void grid_free(grid *g);
--- a/loopy.c
+++ b/loopy.c
@@ -254,7 +254,9 @@
A(Great-Hexagonal,grid_new_greathexagonal,3,3) \
A(Octagonal,grid_new_octagonal,3,3) \
A(Kites,grid_new_kites,3,3) \
- A(Floret,grid_new_floret,1,2)
+ A(Floret,grid_new_floret,1,2) \
+ A(Dodecagonal,grid_new_dodecagonal,2,2) \
+ A(Great-Dodecagonal,grid_new_greatdodecagonal,2,2)
#define GRID_NAME(title,fn,amin,omin) #title,
#define GRID_CONFIG(title,fn,amin,omin) ":" #title
@@ -301,7 +303,7 @@
((field) &= ~(1<<(bit)), TRUE) : FALSE)
#define CLUE2CHAR(c) \
- ((c < 0) ? ' ' : c + '0')
+ ((c < 0) ? ' ' : c < 10 ? c + '0' : c - 10 + 'A')
/* ----------------------------------------------------------------------
* General struct manipulation and other straightforward code
@@ -506,6 +508,8 @@
{ 5, 5, DIFF_HARD, 6, NULL }, { 5, 5, DIFF_HARD, 7, NULL }, { 3, 3, DIFF_HARD, 8, NULL },+ { 3, 3, DIFF_HARD, 9, NULL },+ { 3, 3, DIFF_HARD, 10, NULL },#else
{ 7, 7, DIFF_EASY, 0, NULL }, { 10, 10, DIFF_EASY, 0, NULL },@@ -521,6 +525,8 @@
{ 7, 7, DIFF_HARD, 6, NULL }, { 5, 5, DIFF_HARD, 7, NULL }, { 5, 5, DIFF_HARD, 8, NULL },+ { 5, 4, DIFF_HARD, 9, NULL },+ { 5, 4, DIFF_HARD, 10, NULL },#endif
};
@@ -705,7 +711,7 @@
g = params->game_grid;
for (; *desc; ++desc) {- if (*desc >= '0' && *desc <= '9') {+ if ((*desc >= '0' && *desc <= '9') || (*desc >= 'A' && *desc <= 'Z')) {count++;
continue;
}
@@ -1822,6 +1828,7 @@
grid *g;
game_state *state = snew(game_state);
game_state *state_new;
+ int count = 0;
params_generate_grid(params);
state->game_grid = g = params->game_grid;
g->refcount++;
@@ -1843,6 +1850,7 @@
* preventing games smaller than 4x4 seems to stop this happening */
do {add_full_clues(state, rs);
+ if (++count%100 == 0) printf("tried %d times to make a unique board\n", count);} while (!game_has_unique_soln(state, params->diff));
state_new = remove_clues(state, rs, params->diff);
@@ -1871,7 +1879,7 @@
int i;
game_state *state = snew(game_state);
int empties_to_make = 0;
- int n;
+ int n,n2;
const char *dp = desc;
grid *g;
int num_faces, num_edges;
@@ -1899,8 +1907,11 @@
assert(*dp);
n = *dp - '0';
+ n2 = *dp - 'A' + 10;
if (n >= 0 && n < 10) {state->clues[i] = n;
+ } else if (n2 >= 10 && n2 < 36) {+ state->clues[i] = n2;
} else {n = *dp - 'a' + 1;
assert(n > 0);
@@ -2534,7 +2545,7 @@
* on that. We check this with an assertion, in case someone decides to
* make a grid which has larger faces than this. Note, this algorithm
* could get quite expensive if there are many large faces. */
-#define MAX_FACE_SIZE 8
+#define MAX_FACE_SIZE 12
for (i = 0; i < g->num_faces; i++) {int maxs[MAX_FACE_SIZE][MAX_FACE_SIZE];
@@ -3356,10 +3367,14 @@
grid *g = state->game_grid;
grid_face *f = g->faces + i;
int x, y;
- char c[2];
+ char c[3];
- c[0] = CLUE2CHAR(state->clues[i]);
- c[1] = '\0';
+ if (state->clues[i] < 10) {+ c[0] = CLUE2CHAR(state->clues[i]);
+ c[1] = '\0';
+ } else {+ sprintf(c, "%d", state->clues[i]);
+ }
face_text_pos(ds, g, f, &x, &y);
draw_text(dr, x, y,