]> pd.if.org Git - hexagon/blob - doc/hexagon.pod
Added HL_square
[hexagon] / doc / hexagon.pod
1 =head1 NAME
2
3         hexlib - a library for hexagon grids
4
5 =head1 SYNOPSIS
6
7         #include <hexagon.h>
8
9 =head1 DESCRIPTION
10
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.
17
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.
22
23 =head2 Grid Layout
24
25                    __/15\__/35\ 
26                 __/04\__/24\__/
27                /A \__/14\__/34\
28                \__/03\__/23\__/
29                /  \__/13\__/33\
30                \__/02\__/22\__/
31                /  \__/12\__/32\
32                \__/01\__/21\__/
33                /  \__/11\__/31\
34                \__/00\__/20\__/
35                   \__/  \__/
36
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
41 above system.
42
43 =head3 Inverted Y coordinates
44
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.  To convert to a positive Y down, you can take the
48 negative of the Y coordinate as given by the library.  See the HL_hexbin()
49 example below.
50
51 =head3 Horizontal Grids
52
53 A horizontal grid layout can be created by either rotating the
54 given coordinates by 90 degrees, or, equivalently, swapping the X and
55 Y coordinates as given by the library.  Obviously, you will need to
56 swap them when passing them into the library also.  You may also
57 need to invert the Y coordinate as above for display.
58
59 =head2 Hexagon grid functions
60
61 The hexagon grid is constrained to be a vertical grid, with
62 the hexagon at (2,1) being to the right and half a hex below
63 the hex at (1,1).  Horizontal grid layouts are not supported.
64
65 =head3 int HL_cantor(int x, int y)
66
67 Converts a two dimensional coordinate to a canonical id.
68
69         int hex;
70         hex = HL_cantor(1,1); /* hex == 5 */
71
72 =head3 int HL_cantor_x(int cantor);
73
74 Returns the X coordinate of a hex identified by the given cantor id.
75
76         int x = HL_cantor_x(5); /* x == 1 */
77
78 =head3 int HL_cantor_y(int cantor);
79
80 Returns the Y coordinate of a hex identified by the given cantor id.
81
82         int x = HL_cantor_x(5); /* x == 1 */
83
84 =head3 int HL_hexbin(double scale, double cx, double cy, int *x, int *y);
85
86 This function determines which hex a given cartesian coordinate falls
87 in.  The width from side to side of a hex is given by scale.  The
88 function returns the cantor id of the hex.  If x or y are not NULL, the
89 x and y coordinates of the hex are placed into *x and *y.
90
91 If you are inverting the Y coordinate for display, do so on the result
92 of this function, not the display Y coordinate you pass in to this function.
93 That is, do
94
95         HL_hexbin(scale, cx, cy, &x, &y);
96         y = -y;
97
98 to get the Y coordinate of the hex.  Doing the following
99
100         HL_hexbin(scale, cx, -cy, &x, &y);
101
102 will give the wrong result for odd numbered hex columns.  This
103 is because the X axis passes through the center of the even columns,
104 so the negation works, but it passes along the edge of the odd columns,
105 and you end up with an off by one error.
106
107 =head2 Pathfinding
108
109 The library provides an A* implementation for pathfinding on
110 a hex grid.
111
112         struct HL_astar *state;
113         state = HL_astar_init(NULL);
114         state->start = HL_cantor_xy(1,1);
115         state->goal = HL_cantor_xy(4,14);
116         int length = HL_astar_findpath(state,0);
117
118 The implementation uses three callbacks which can be
119 set as members of the HL_astar struct.
120
121         double (*metric)(int hex, int hex2);
122         double (*heuristic)(int hex, int hex2);
123         int (*neighbor)(int hex, int n);
124
125 The metric callback is used to get the actual cost to move from
126 hex to hex2.  It will only be called on adjacent hexes.  HL_astar_init
127 will set this to a default metric that returns 1.0 for any input.
128
129 The heuristic callback is used to estimate the distance between
130 two hexes, which may not be adjacent.  By default, a function is
131 used that returns the hex grid distance between the hexes.
132 It is important that the function not return a distance that is
133 greater than the actual distance, as the A* algorithm depends on
134 this.  If you have any hexes that cost less than 1.0 to traverse,
135 the default heuristic won't work, so you'll need to provide your
136 own.  You could also provide a metric that multiplied the actual
137 cost by an amount sufficient to raise the minimum cost to 1.0.
138 (e.g. if you had roads that reduced the move cost to 1/2, you
139 could provide a metric returned twice the actual cost).
140
141 The neighbor callback should return the id of the neighbor
142 at the index given by n.  The callback should return 0 if
143 there is no neighbor with the given index.  It's ok if
144 a neighbor has more than one index.  That is, you can
145 return the same neighbor for more than one index.  The
146 first neighbor should be at index 0.  The HL_findpath
147 function will call this method starting at index 0 and
148 working up until the function returns 0, at which point
149 it is assumed that there are no more neighbors.
150
151 =head3 struct HL_astar *HL_astar_init(HL_astar *state);
152
153 Initializes the given state.  You can either pass in a pointer to your
154 own data structure, or pass in NULL, in which case the library
155 will use malloc(3) to create a new structure.
156
157 =head3 void HL_astar_free(HL_astar *state);
158
159 Frees any memory allocated by the structure.
160
161 =head1 OPTIONS
162
163 =head1 DIAGNOSTICS
164
165 =head1 BUGS
166
167 =head1 AUTHOR
168
169 This library was entirely written by Nathan Wagner.
170
171 =head1 COPYRIGHT
172
173 This library and the source code for it are released into
174 the public domain.  The author asserts no copyright claim
175 of any kind.
176
177 =head1