3 hexlib - a library for hexagon grids
11 hexagon is a C library for performing calculations on hexagon grids.
12 Hexagons are represented by their canonical ID, which is a single
13 integer representation of their two dimensional coordinates.
14 Algorithms and functions are provided for calculating hexagon
15 centers, vertexes, and distances on the grid. An A* algorithm
16 is also implemented for pathfinding.
18 The canonical integer id of a hexagon is computed from its
19 two dimensional integer coordinates using a modified
20 cantor pairing function. The canonical integer ids are
21 referred to as cantors.
37 The Grid is numbered as above, and generalizes to negative coordinates,
38 thus the hex labeled A would have coordinates (-1,4), and the
39 hex (not shown) two hexes below 1,1 would be hex 1,-1. If you
40 need different coordinates, you will have to translate them to the
43 =head3 Inverted Y coordinates
45 Many games and displays use a positive Y down, rather than the
46 usual mathematical positive Y up. The library uses the mathematical
47 convention. In general though, this will not matter. The Y coordinate
48 of the hex centers has the same direction as the Y coordinate of the
49 hex grid. If your display is Y down, and your grid is too, you can
50 use the coordinates as given. If your display is Y up and you want
51 your grid to be Y down, you will, obviously, need to invert the Y
52 coordinates for display, and re-invert them when passing them back to
55 To convert to a positive Y down, you can take the negative of the Y coordinate
56 as given by the library. See the HL_hexbin() example below.
58 =head3 Horizontal Grids
60 A horizontal grid layout can be created by either rotating the given
61 coordinates by 90 degrees, or, equivalently, swapping the X and Y coordinates
62 as given by the library. Obviously, you will need to swap them when passing
63 them into the library also. You may also need to invert the (resulting) Y
64 coordinate as above for display if your display is positive Y down.
68 Two dimensional hex locations are converted into a single integer
69 hexagon ID with a pairing function. A pairing function uniquely
70 and reversably maps two integers onto one integer. At the moment,
71 only a modified Cantor's original triangular pairing function,
72 extended to handle negative integers,
75 As most hexagon grids will only use positive coordinates, additional
76 pairing functions will be provided in the future.
78 =head3 int HL_cantor(int x, int y)
80 Converts a two dimensional coordinate to a canonical id.
83 hex = HL_cantor(1,1); /* hex == 5 */
85 =head2 Hexagon grid functions
87 The hexagon grid is constrained to be a vertical grid, with the hexagon at
88 (2,1) being to the right and half a hex below the hex at (1,1). Horizontal
89 grid layouts are not supported.
91 =head3 int HL_cantor_x(int cantor);
93 Returns the X coordinate of a hex identified by the given cantor id.
95 int x = HL_cantor_x(5); /* x == 1 */
97 =head3 int HL_cantor_y(int cantor);
99 Returns the Y coordinate of a hex identified by the given cantor id.
101 int x = HL_cantor_x(5); /* x == 1 */
103 =head3 int HL_hexbin(double scale, double cx, double cy, int *x, int *y);
105 This function determines which hex a given cartesian coordinate falls
106 in. The width from side to side of a hex is given by scale. The
107 function returns the cantor id of the hex. If x or y are not NULL, the
108 x and y coordinates of the hex are placed into *x and *y.
110 If you are inverting the Y coordinate for display, do so on the result
111 of this function, not the display Y coordinate you pass in to this function.
114 HL_hexbin(scale, cx, cy, &x, &y);
117 to get the Y coordinate of the hex. Doing the following
119 HL_hexbin(scale, cx, -cy, &x, &y);
121 will give the wrong result for odd numbered hex columns. This
122 is because the X axis passes through the center of the even columns,
123 so the negation works, but it passes along the edge of the odd columns,
124 and you end up with an off by one error.
128 Some pre-calculated data is available.
130 =head3 double HL_fand[16]
132 An array of hexagon coordinates, with the hex center x,y at indexes 0 and
133 1 (these are 0.0,0.0), and each vertex following. The first vertex
134 is repeated at the end of the array. Each vertex takes up two consecutive
135 array elements for it's X and Y coordinates. Thus for hex vertexes 1 to
136 6, and hex center C this array is CxCy1x1y2x2y3x3y4x4y5x5y6x6y1x1y.
137 This is suitable for passing directly to opengl for drawing a hexagon
140 =head3 float HL_fanf[16]
142 An array of floats, laid out the same way as HL_fand.
144 =head3 double HL_hfand[16]
146 This is the same as HL_fand, but will draw a horizontal hex. The same
147 effect could be had by rotating 90 degrees.
149 =head3 float HL_hfanf[16]
151 An array of float with horizontal layout.
155 The library provides an A* implementation for pathfinding on
158 struct HL_astar *state;
159 state = HL_astar_init(NULL);
160 state->start = HL_cantor_xy(1,1);
161 state->goal = HL_cantor_xy(4,14);
162 int length = HL_astar_findpath(state,0);
164 The implementation uses three callbacks which can be
165 set as members of the HL_astar struct.
167 double (*metric)(int hex, int hex2);
168 double (*heuristic)(int hex, int hex2);
169 int (*neighbor)(int hex, int n);
171 The metric callback is used to get the actual cost to move from
172 hex to hex2. It will only be called on adjacent hexes. HL_astar_init
173 will set this to a default metric that returns 1.0 for any input.
175 The heuristic callback is used to estimate the distance between
176 two hexes, which may not be adjacent. By default, a function is
177 used that returns the hex grid distance between the hexes.
178 It is important that the function not return a distance that is
179 greater than the actual distance, as the A* algorithm depends on
180 this. If you have any hexes that cost less than 1.0 to traverse,
181 the default heuristic won't work, so you'll need to provide your
182 own. You could also provide a metric that multiplied the actual
183 cost by an amount sufficient to raise the minimum cost to 1.0.
184 (e.g. if you had roads that reduced the move cost to 1/2, you
185 could provide a metric returned twice the actual cost).
187 The neighbor callback should return the id of the neighbor
188 at the index given by n. The callback should return 0 if
189 there is no neighbor with the given index. It's ok if
190 a neighbor has more than one index. That is, you can
191 return the same neighbor for more than one index. The
192 first neighbor should be at index 0. The HL_findpath
193 function will call this method starting at index 0 and
194 working up until the function returns 0, at which point
195 it is assumed that there are no more neighbors.
197 =head3 struct HL_astar *HL_astar_init(HL_astar *state);
199 Initializes the given state. You can either pass in a pointer to your
200 own data structure, or pass in NULL, in which case the library
201 will use malloc(3) to create a new structure.
203 =head3 void HL_astar_free(HL_astar *state);
205 Frees any memory allocated by the structure.
215 This library was entirely written by Nathan Wagner.
219 This library and the source code for it are released into
220 the public domain. The author asserts no copyright claim