2 * (c) Lambros Lambrou 2008
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.
10 #define PUZZLES_GRID_H
14 # define SQ(x) ( (x) * (x) )
17 /* ----------------------------------------------------------------------
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.
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
;
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 */
41 grid_dot
*dot1
, *dot2
;
42 grid_face
*face1
, *face2
; /* Use NULL for the infinite outside face */
47 grid_face
**faces
; /* A NULL grid_face* means infinite outside face */
49 /* Position in some fairly arbitrary (Cartesian) coordinate system.
50 * Use large enough values such that we can get away with
51 * integer arithmetic, but small enough such that arithmetic
56 /* These are (dynamically allocated) arrays of all the
57 * faces, edges, dots that are in the grid. */
58 int num_faces
; grid_face
*faces
;
59 int num_edges
; grid_edge
*edges
;
60 int num_dots
; grid_dot
*dots
;
62 /* Should be a face roughly near the middle of the grid.
63 * Used to seed path-generation, and also for nearest-edge
65 grid_face
*middle_face
;
67 /* Cache the bounding-box of the grid, so the drawing-code can quickly
68 * figure out the proper scaling to draw onto a given area. */
69 int lowest_x
, lowest_y
, highest_x
, highest_y
;
71 /* A measure of tile size for this grid (in grid coordinates), to help
72 * the renderer decide how large to draw the grid.
73 * Roughly the size of a single tile - for example the side-length
74 * of a square cell. */
77 /* We really don't want to copy this monstrosity!
78 * A grid is immutable once generated.
83 grid
*grid_new_square(int width
, int height
);
84 grid
*grid_new_honeycomb(int width
, int height
);
85 grid
*grid_new_triangular(int width
, int height
);
86 grid
*grid_new_snubsquare(int width
, int height
);
87 grid
*grid_new_cairo(int width
, int height
);
88 grid
*grid_new_greathexagonal(int width
, int height
);
89 grid
*grid_new_octagonal(int width
, int height
);
90 grid
*grid_new_kites(int width
, int height
);
92 void grid_free(grid
*g
);
94 grid_edge
*grid_nearest_edge(grid
*g
, int x
, int y
);
96 #endif /* PUZZLES_GRID_H */