tsiry-sandratraina.com
A modern Music Player Daemon based on Rockbox open source high quality audio player
libadwaita
audio
rust
zig
deno
mpris
rockbox
mpd
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 */
31typedef struct grid_face grid_face;
32typedef struct grid_edge grid_edge;
33typedef struct grid_dot grid_dot;
34
35struct grid_face {
36 int index; /* index in grid->faces[] where this face appears */
37 int order; /* Number of edges, also the number of dots */
38 grid_edge **edges; /* edges around this face */
39 grid_dot **dots; /* corners of this face */
40 /*
41 * For each face, we optionally compute and store its 'incentre'.
42 * The incentre of a triangle is the centre of a circle tangent to
43 * all three edges; I generalise the concept to arbitrary polygons
44 * by defining it to be the centre of the largest circle you can fit
45 * anywhere in the polygon. It's a useful thing to know because if
46 * you want to draw any symbol or text in the face (e.g. clue
47 * numbers in Loopy), that's the place it will most easily fit.
48 *
49 * When a grid is first generated, no face has this information
50 * computed, because it's fiddly to do. You can call
51 * grid_find_incentre() on a face, and it will fill in ix,iy below
52 * and set has_incentre to indicate that it's done so.
53 */
54 bool has_incentre;
55 int ix, iy; /* incentre (centre of largest inscribed circle) */
56};
57struct grid_edge {
58 grid_dot *dot1, *dot2;
59 grid_face *face1, *face2; /* Use NULL for the infinite outside face */
60 int index; /* index in grid->edges[] where this edge appears */
61};
62struct grid_dot {
63 int index; /* index in grid->dots[] where this dot appears */
64 int order;
65 grid_edge **edges;
66 grid_face **faces; /* A NULL grid_face* means infinite outside face */
67
68 /* Position in some fairly arbitrary (Cartesian) coordinate system.
69 * Use large enough values such that we can get away with
70 * integer arithmetic, but small enough such that arithmetic
71 * won't overflow. */
72 int x, y;
73};
74typedef struct grid {
75 /* Arrays of all the faces, edges, dots that are in the grid.
76 * The arrays themselves are dynamically allocated, and so is each object
77 * inside them. num_foo indicates the number of things actually stored,
78 * and size_foo indicates the allocated size of the array. */
79 int num_faces, size_faces; grid_face **faces;
80 int num_edges, size_edges; grid_edge **edges;
81 int num_dots, size_dots; grid_dot **dots;
82
83 /* Cache the bounding-box of the grid, so the drawing-code can quickly
84 * figure out the proper scaling to draw onto a given area. */
85 int lowest_x, lowest_y, highest_x, highest_y;
86
87 /* A measure of tile size for this grid (in grid coordinates), to help
88 * the renderer decide how large to draw the grid.
89 * Roughly the size of a single tile - for example the side-length
90 * of a square cell. */
91 int tilesize;
92
93 /* We really don't want to copy this monstrosity!
94 * A grid is immutable once generated.
95 */
96 int refcount;
97} grid;
98
99/* Grids are specified by type: GRID_SQUARE, GRID_KITE, etc. */
100
101#define GRIDGEN_LIST(A) \
102 A(SQUARE,square) \
103 A(HONEYCOMB,honeycomb) \
104 A(TRIANGULAR,triangular) \
105 A(SNUBSQUARE,snubsquare) \
106 A(CAIRO,cairo) \
107 A(GREATHEXAGONAL,greathexagonal) \
108 A(KAGOME,kagome) \
109 A(OCTAGONAL,octagonal) \
110 A(KITE,kites) \
111 A(FLORET,floret) \
112 A(DODECAGONAL,dodecagonal) \
113 A(GREATDODECAGONAL,greatdodecagonal) \
114 A(GREATGREATDODECAGONAL,greatgreatdodecagonal) \
115 A(COMPASSDODECAGONAL,compassdodecagonal) \
116 A(PENROSE_P2,penrose_p2_kite) \
117 A(PENROSE_P3,penrose_p3_thick) \
118 A(HATS,hats) \
119 A(SPECTRES,spectres) \
120 /* end of list */
121
122#define ENUM(upper,lower) GRID_ ## upper,
123typedef enum grid_type { GRIDGEN_LIST(ENUM) GRID_TYPE_MAX } grid_type;
124#undef ENUM
125
126const char *grid_validate_params(grid_type type, int width, int height);
127
128/* Free directly after use if non-NULL. Will never contain an underscore
129 * (so clients can safely use that as a separator). */
130char *grid_new_desc(grid_type type, int width, int height, random_state *rs);
131const char *grid_validate_desc(grid_type type, int width, int height,
132 const char *desc);
133
134grid *grid_new(grid_type type, int width, int height, const char *desc);
135
136void grid_free(grid *g);
137
138grid_edge *grid_nearest_edge(grid *g, int x, int y);
139
140void grid_compute_size(grid_type type, int width, int height,
141 int *tilesize, int *xextent, int *yextent);
142
143void grid_find_incentre(grid_face *f);
144
145#endif /* PUZZLES_GRID_H */