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