+=head1 NAME
+
+ hexlib - a library for hexagon grids
+
+=head1 SYNOPSIS
+
+ #include <hexagon.h>
+
+=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. 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 Y coordinate as above for display.
+
+=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(int x, int y)
+
+Converts a two dimensional coordinate to a canonical id.
+
+ int hex;
+ hex = HL_cantor(1,1); /* hex == 5 */
+
+=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 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
projects / hexagon / commitdiff