diff options
Diffstat (limited to 'apps/plugins/puzzles/src/grid.h')
-rw-r--r-- | apps/plugins/puzzles/src/grid.h | 133 |
1 files changed, 133 insertions, 0 deletions
diff --git a/apps/plugins/puzzles/src/grid.h b/apps/plugins/puzzles/src/grid.h new file mode 100644 index 0000000000..fb8ac48790 --- /dev/null +++ b/apps/plugins/puzzles/src/grid.h | |||
@@ -0,0 +1,133 @@ | |||
1 | /* | ||
2 | * (c) Lambros Lambrou 2008 | ||
3 | * | ||
4 | * Code for working with general grids, which can be any planar graph | ||
5 | * with faces, edges and vertices (dots). Includes generators for a few | ||
6 | * types of grid, including square, hexagonal, triangular and others. | ||
7 | */ | ||
8 | |||
9 | #ifndef PUZZLES_GRID_H | ||
10 | #define PUZZLES_GRID_H | ||
11 | |||
12 | #include "puzzles.h" /* for random_state */ | ||
13 | |||
14 | /* Useful macros */ | ||
15 | #define SQ(x) ( (x) * (x) ) | ||
16 | |||
17 | /* ---------------------------------------------------------------------- | ||
18 | * Grid structures: | ||
19 | * A grid is made up of faces, edges and dots. These structures hold | ||
20 | * the incidence relationships between these types. For example, an | ||
21 | * edge always joins two dots, and is adjacent to two faces. | ||
22 | * The "grid_xxx **" members are lists of pointers which are dynamically | ||
23 | * allocated during grid generation. | ||
24 | * A pointer to a face/edge/dot will always point somewhere inside one of the | ||
25 | * three lists of the main "grid" structure: faces, edges, dots. | ||
26 | * Could have used integer offsets into these lists, but using actual | ||
27 | * pointers instead gives us type-safety. | ||
28 | */ | ||
29 | |||
30 | /* Need forward declarations */ | ||
31 | typedef struct grid_face grid_face; | ||
32 | typedef struct grid_edge grid_edge; | ||
33 | typedef struct grid_dot grid_dot; | ||
34 | |||
35 | struct grid_face { | ||
36 | int order; /* Number of edges, also the number of dots */ | ||
37 | grid_edge **edges; /* edges around this face */ | ||
38 | grid_dot **dots; /* corners of this face */ | ||
39 | /* | ||
40 | * For each face, we optionally compute and store its 'incentre'. | ||
41 | * The incentre of a triangle is the centre of a circle tangent to | ||
42 | * all three edges; I generalise the concept to arbitrary polygons | ||
43 | * by defining it to be the centre of the largest circle you can fit | ||
44 | * anywhere in the polygon. It's a useful thing to know because if | ||
45 | * you want to draw any symbol or text in the face (e.g. clue | ||
46 | * numbers in Loopy), that's the place it will most easily fit. | ||
47 | * | ||
48 | * When a grid is first generated, no face has this information | ||
49 | * computed, because it's fiddly to do. You can call | ||
50 | * grid_find_incentre() on a face, and it will fill in ix,iy below | ||
51 | * and set has_incentre to indicate that it's done so. | ||
52 | */ | ||
53 | int has_incentre; | ||
54 | int ix, iy; /* incentre (centre of largest inscribed circle) */ | ||
55 | }; | ||
56 | struct grid_edge { | ||
57 | grid_dot *dot1, *dot2; | ||
58 | grid_face *face1, *face2; /* Use NULL for the infinite outside face */ | ||
59 | }; | ||
60 | struct grid_dot { | ||
61 | int order; | ||
62 | grid_edge **edges; | ||
63 | grid_face **faces; /* A NULL grid_face* means infinite outside face */ | ||
64 | |||
65 | /* Position in some fairly arbitrary (Cartesian) coordinate system. | ||
66 | * Use large enough values such that we can get away with | ||
67 | * integer arithmetic, but small enough such that arithmetic | ||
68 | * won't overflow. */ | ||
69 | int x, y; | ||
70 | }; | ||
71 | typedef struct grid { | ||
72 | /* These are (dynamically allocated) arrays of all the | ||
73 | * faces, edges, dots that are in the grid. */ | ||
74 | int num_faces; grid_face *faces; | ||
75 | int num_edges; grid_edge *edges; | ||
76 | int num_dots; grid_dot *dots; | ||
77 | |||
78 | /* Cache the bounding-box of the grid, so the drawing-code can quickly | ||
79 | * figure out the proper scaling to draw onto a given area. */ | ||
80 | int lowest_x, lowest_y, highest_x, highest_y; | ||
81 | |||
82 | /* A measure of tile size for this grid (in grid coordinates), to help | ||
83 | * the renderer decide how large to draw the grid. | ||
84 | * Roughly the size of a single tile - for example the side-length | ||
85 | * of a square cell. */ | ||
86 | int tilesize; | ||
87 | |||
88 | /* We really don't want to copy this monstrosity! | ||
89 | * A grid is immutable once generated. | ||
90 | */ | ||
91 | int refcount; | ||
92 | } grid; | ||
93 | |||
94 | /* Grids are specified by type: GRID_SQUARE, GRID_KITE, etc. */ | ||
95 | |||
96 | #define GRIDGEN_LIST(A) \ | ||
97 | A(SQUARE,square) \ | ||
98 | A(HONEYCOMB,honeycomb) \ | ||
99 | A(TRIANGULAR,triangular) \ | ||
100 | A(SNUBSQUARE,snubsquare) \ | ||
101 | A(CAIRO,cairo) \ | ||
102 | A(GREATHEXAGONAL,greathexagonal) \ | ||
103 | A(OCTAGONAL,octagonal) \ | ||
104 | A(KITE,kites) \ | ||
105 | A(FLORET,floret) \ | ||
106 | A(DODECAGONAL,dodecagonal) \ | ||
107 | A(GREATDODECAGONAL,greatdodecagonal) \ | ||
108 | A(GREATGREATDODECAGONAL,greatgreatdodecagonal) \ | ||
109 | A(PENROSE_P2,penrose_p2_kite) \ | ||
110 | A(PENROSE_P3,penrose_p3_thick) | ||
111 | |||
112 | #define ENUM(upper,lower) GRID_ ## upper, | ||
113 | typedef enum grid_type { GRIDGEN_LIST(ENUM) GRID_TYPE_MAX } grid_type; | ||
114 | #undef ENUM | ||
115 | |||
116 | /* Free directly after use if non-NULL. Will never contain an underscore | ||
117 | * (so clients can safely use that as a separator). */ | ||
118 | char *grid_new_desc(grid_type type, int width, int height, random_state *rs); | ||
119 | char *grid_validate_desc(grid_type type, int width, int height, | ||
120 | const char *desc); | ||
121 | |||
122 | grid *grid_new(grid_type type, int width, int height, const char *desc); | ||
123 | |||
124 | void grid_free(grid *g); | ||
125 | |||
126 | grid_edge *grid_nearest_edge(grid *g, int x, int y); | ||
127 | |||
128 | void grid_compute_size(grid_type type, int width, int height, | ||
129 | int *tilesize, int *xextent, int *yextent); | ||
130 | |||
131 | void grid_find_incentre(grid_face *f); | ||
132 | |||
133 | #endif /* PUZZLES_GRID_H */ | ||