=head1 NAME hexlib - a library for hexagon grids =head1 SYNOPSIS #include =head1 DESCRIPTION hexagon is a C library for performing calculations on hexagon grids. Hexagons are represented by their canonical ID, which is a single integer representation of their two dimensional coordinates. Algorithms and functions are provided for calculating hexagon centers, vertexes, and distances on the grid. An A* algorithm is also implemented for pathfinding. The canonical integer id of a hexagon is computed from its two dimensional integer coordinates using a modified cantor pairing function. The canonical integer ids are referred to as cantors. =head2 Grid Layout __/15\__/35\ __/04\__/24\__/ /A \__/14\__/34\ \__/03\__/23\__/ / \__/13\__/33\ \__/02\__/22\__/ / \__/12\__/32\ \__/01\__/21\__/ / \__/11\__/31\ \__/00\__/20\__/ \__/ \__/ The Grid is numbered as above, and generalizes to negative coordinates, thus the hex labeled A would have coordinates (-1,4), and the hex (not shown) two hexes below 1,1 would be hex 1,-1. If you need different coordinates, you will have to translate them to the above system. =head3 Inverted Y coordinates Many games and displays use a positive Y down, rather than the usual mathematical positive Y up. The library uses the mathematical convention. In general though, this will not matter. The Y coordinate of the hex centers has the same direction as the Y coordinate of the hex grid. If your display is Y down, and your grid is too, you can use the coordinates as given. If your display is Y up and you want your grid to be Y down, you will, obviously, need to invert the Y coordinates for display, and re-invert them when passing them back to the library. To convert to a positive Y down, you can take the negative of the Y coordinate as given by the library. See the HL_hexbin() example below. =head3 Horizontal Grids A horizontal grid layout can be created by either rotating the given coordinates by 90 degrees, or, equivalently, swapping the X and Y coordinates as given by the library. Obviously, you will need to swap them when passing them into the library also. You may also need to invert the (resulting) Y coordinate as above for display if your display is positive Y down. =head2 Hexagon IDs Two dimensional hex locations are converted into a single integer hexagon ID with a pairing function. A pairing function uniquely and reversably maps two integers onto one integer. At the moment, only a modified Cantor's original triangular pairing function, extended to handle negative integers, is available. As most hexagon grids will only use positive coordinates, additional pairing functions will be provided in the future. =head3 int HL_cantor(int x, int y) Converts a two dimensional coordinate to a canonical id. int hex; hex = HL_cantor(1,1); /* hex == 5 */ =head2 Hexagon grid functions The hexagon grid is constrained to be a vertical grid, with the hexagon at (2,1) being to the right and half a hex below the hex at (1,1). Horizontal grid layouts are not supported. =head3 int HL_cantor_x(int cantor); Returns the X coordinate of a hex identified by the given cantor id. int x = HL_cantor_x(5); /* x == 1 */ =head3 int HL_cantor_y(int cantor); Returns the Y coordinate of a hex identified by the given cantor id. int x = HL_cantor_x(5); /* x == 1 */ =head3 int HL_hexbin(double scale, double cx, double cy, int *x, int *y); This function determines which hex a given cartesian coordinate falls in. The width from side to side of a hex is given by scale. The function returns the cantor id of the hex. If x or y are not NULL, the x and y coordinates of the hex are placed into *x and *y. If you are inverting the Y coordinate for display, do so on the result of this function, not the display Y coordinate you pass in to this function. That is, do HL_hexbin(scale, cx, cy, &x, &y); y = -y; to get the Y coordinate of the hex. Doing the following HL_hexbin(scale, cx, -cy, &x, &y); will give the wrong result for odd numbered hex columns. This is because the X axis passes through the center of the even columns, so the negation works, but it passes along the edge of the odd columns, and you end up with an off by one error. =head2 Hexagon data Some pre-calculated data is available. =head3 double HL_fand[16] An array of hexagon coordinates, with the hex center x,y at indexes 0 and 1 (these are 0.0,0.0), and each vertex following. The first vertex is repeated at the end of the array. Each vertex takes up two consecutive array elements for it's X and Y coordinates. Thus for hex vertexes 1 to 6, and hex center C this array is CxCy1x1y2x2y3x3y4x4y5x5y6x6y1x1y. This is suitable for passing directly to opengl for drawing a hexagon as a triangle fan. =head3 float HL_fanf[16] An array of floats, laid out the same way as HL_fand. =head3 double HL_hfand[16] This is the same as HL_fand, but will draw a horizontal hex. The same effect could be had by rotating 90 degrees. =head3 float HL_hfanf[16] An array of float with horizontal layout. =head2 Pathfinding The library provides an A* implementation for pathfinding on a hex grid. struct HL_astar *state; state = HL_astar_init(NULL); state->start = HL_cantor_xy(1,1); state->goal = HL_cantor_xy(4,14); int length = HL_astar_findpath(state,0); The implementation uses three callbacks which can be set as members of the HL_astar struct. double (*metric)(int hex, int hex2); double (*heuristic)(int hex, int hex2); int (*neighbor)(int hex, int n); The metric callback is used to get the actual cost to move from hex to hex2. It will only be called on adjacent hexes. HL_astar_init will set this to a default metric that returns 1.0 for any input. The heuristic callback is used to estimate the distance between two hexes, which may not be adjacent. By default, a function is used that returns the hex grid distance between the hexes. It is important that the function not return a distance that is greater than the actual distance, as the A* algorithm depends on this. If you have any hexes that cost less than 1.0 to traverse, the default heuristic won't work, so you'll need to provide your own. You could also provide a metric that multiplied the actual cost by an amount sufficient to raise the minimum cost to 1.0. (e.g. if you had roads that reduced the move cost to 1/2, you could provide a metric returned twice the actual cost). The neighbor callback should return the id of the neighbor at the index given by n. The callback should return 0 if there is no neighbor with the given index. It's ok if a neighbor has more than one index. That is, you can return the same neighbor for more than one index. The first neighbor should be at index 0. The HL_findpath function will call this method starting at index 0 and working up until the function returns 0, at which point it is assumed that there are no more neighbors. =head3 struct HL_astar *HL_astar_init(HL_astar *state); Initializes the given state. You can either pass in a pointer to your own data structure, or pass in NULL, in which case the library will use malloc(3) to create a new structure. =head3 void HL_astar_free(HL_astar *state); Frees any memory allocated by the structure. =head1 OPTIONS =head1 DIAGNOSTICS =head1 BUGS =head1 AUTHOR This library was entirely written by Nathan Wagner. =head1 COPYRIGHT This library and the source code for it are released into the public domain. The author asserts no copyright claim of any kind. =head1