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
13 #define SQ(x) ( (x) * (x) )
15 /* ----------------------------------------------------------------------
17 * A grid is made up of faces, edges and dots. These structures hold
18 * the incidence relationships between these types. For example, an
19 * edge always joins two dots, and is adjacent to two faces.
20 * The "grid_xxx **" members are lists of pointers which are dynamically
21 * allocated during grid generation.
22 * A pointer to a face/edge/dot will always point somewhere inside one of the
23 * three lists of the main "grid" structure: faces, edges, dots.
24 * Could have used integer offsets into these lists, but using actual
25 * pointers instead gives us type-safety.
28 /* Need forward declarations */
29 typedef struct grid_face grid_face
;
30 typedef struct grid_edge grid_edge
;
31 typedef struct grid_dot grid_dot
;
34 int order
; /* Number of edges, also the number of dots */
35 grid_edge
**edges
; /* edges around this face */
36 grid_dot
**dots
; /* corners of this face */
39 grid_dot
*dot1
, *dot2
;
40 grid_face
*face1
, *face2
; /* Use NULL for the infinite outside face */
45 grid_face
**faces
; /* A NULL grid_face* means infinite outside face */
47 /* Position in some fairly arbitrary (Cartesian) coordinate system.
48 * Use large enough values such that we can get away with
49 * integer arithmetic, but small enough such that arithmetic
54 /* These are (dynamically allocated) arrays of all the
55 * faces, edges, dots that are in the grid. */
56 int num_faces
; grid_face
*faces
;
57 int num_edges
; grid_edge
*edges
;
58 int num_dots
; grid_dot
*dots
;
60 /* Should be a face roughly near the middle of the grid.
61 * Used to seed path-generation, and also for nearest-edge
63 grid_face
*middle_face
;
65 /* Cache the bounding-box of the grid, so the drawing-code can quickly
66 * figure out the proper scaling to draw onto a given area. */
67 int lowest_x
, lowest_y
, highest_x
, highest_y
;
69 /* A measure of tile size for this grid (in grid coordinates), to help
70 * the renderer decide how large to draw the grid.
71 * Roughly the size of a single tile - for example the side-length
72 * of a square cell. */
75 /* We really don't want to copy this monstrosity!
76 * A grid is immutable once generated.
81 grid
*grid_new_square(int width
, int height
);
82 grid
*grid_new_honeycomb(int width
, int height
);
83 grid
*grid_new_triangular(int width
, int height
);
84 grid
*grid_new_snubsquare(int width
, int height
);
85 grid
*grid_new_cairo(int width
, int height
);
86 grid
*grid_new_greathexagonal(int width
, int height
);
87 grid
*grid_new_octagonal(int width
, int height
);
88 grid
*grid_new_kites(int width
, int height
);
90 void grid_free(grid
*g
);
92 grid_edge
*grid_nearest_edge(grid
*g
, int x
, int y
);
94 #endif /* PUZZLES_GRID_H */