#+TITLE: Implementation of Hex Grids
#+DATE: <2015-05-06>
#+OPTIONS: toc:2
#+begin_note
Note: this article is a companion guide to my [[./][guide to hex grids]]. The data structures and functions here implement the math and algorithms described on that page.
#+end_note
The [[./][main page]] covers the /theory/ for hex grid algorithms and math. Now let's write a library to handle hex grids. The first thing to think about is what the core concepts will be.
- Since most of the algorithms work with cube coordinates, I'll need a data structure for cube coordinates, along with algorithms that work with them. I'll call this the *Hex* class.
- For some games I want to show coordinates to the player, and those will probably /not/ be cube, but instead axial or offset, so I'll need a data structure for the player-visible coordinate system, as well as functions for converting back and forth. /Cube and axial are basically the same/ so I'm not going to bother implementing a separate axial system, and I'll reuse *Hex*. For offset coordinates, I'll make a separate data structure *Offset*.
- A grid map will likely need additional storage for terrain, objects, units, etc. A 2d array can be used but it's not always straightforward, so I'll create a *Map* class for this.
- To draw hexes on the screen, I need a way to convert hex coordinates into screen space. I'll call this the *Layout* class. The main article doesn't cover some of the additional features I want:
- Support y-axis pointing down (common in 2d libraries) as well as y-axis pointing up (common in 3d libraries). The main article only covers y-axis pointing down.
- Support stretched or squashed hexes, which are common with pixel graphics. The main article only supports equilateral hexes.
- Support the 0,0 hex being located on the screen anywhere. The main article always places the 0,0 hex at x=0, y=0.
- I also need a way to convert mouse clicks and other pixel coordinates back into hex coordinates. I will put this into the *Layout* class. The same things I need to deal with for hex to screen (y-axis direction, stretch/squash, origin) have to be dealt with for screen to hex, so it makes sense to put them together.
- The main article doesn't distinguish hexes that have integer coordinates from those with fractional coordinates. I'll define a second class *FractionalHex* for the two algorithms where I want to have floating point coordinates: linear interpolation and rounding.
- Once I have coordinates and the =neighbors= function implemented I can use all /graph algorithms/ including movement range and pathfinding. I cover pathfinding for graphs [[http:/pathfinding/a-star/introduction.html][on another page]] and won't duplicate that code here.
I'm going to use C++ for the code samples, but I [[#code][also have]] Java, C#, Python, Javascript, Haxe, and Lua versions of the code.
* Hex coordinates
:PROPERTIES:
:CUSTOM_ID: hex
:END:
On the main page, I treat Cube and Axial systems separately. Cube coordinates are a plane in x,y,z space, where x+y+z = 0. Axial coordinates have two axes q,r that are 60° or 120° apart. Here's a class that represents cube coordinates, but uses names =q=, =r=, =s= instead of the =x=, =y=, =z= I use on the main page:
#+begin_src cpp
struct Hex { // Cube storage, cube constructor
const int q, r, s;
Hex(int q_, int r_, int s_): q(q_), r(r_), s(s_) {
assert (q + r + s == 0);
}
};
#+end_src
Pretty simple. Here's a class that stores axial coordinates internally, but uses cube coordinates for the interface:
#+begin_src cpp
struct Hex { // Axial storage, cube constructor
const int q_, r_;
Hex(int q, int r, int s): q_(q), r_(r) {
assert (q + r + s == 0);
}
inline int q() { return q_; }
inline int r() { return r_; }
inline int s() { return - q_ - r_; }
};
#+end_src
These two classes are effectively equivalent. The first one stores =s= explicitly and the second one uses accessors and calculates =s= when needed. *Cube and Axial are essentially the same system*, so I'm not going to write a separate class for each. However *the labels on this page are different*. On the main page, the axial/cube relationship is q→x, r→z, but here I am making q→q, r→r. And that means on the main page cube coordinates are (q, -q-r, r) but on this page cube coordinates are (q, r, -q-r). /This makes my two pages inconsistent/ and I plan to update the main page to match this page.
Yet another style is to calculate =s= in the constructor instead of passing it in:
#+begin_src cpp
struct Hex { // Cube storage, axial constructor
const int q, r, s;
Hex(int q_, int r_): q(q_), r(r_), s(-q_ - r_) {}
};
#+end_src
An advantage of the axial constructor style is that more than half the time, you're doing this anyway at the call site. You'll have =q= and =r= and not =s=, so you'll pass in =-q-r= for the third parameter. You can also combine this with the second style (axial storage), and store only =q= and =r=, and calculate =s= in an accessor.
Yet another style is to use an array instead of named fields:
#+begin_src cpp
struct Hex { // Vector storage, cube constructor
const int v[3];
Hex(int q, int r, int s): v{q, r, s} {
assert (q + r + s == 0);
}
inline int q() { return v[0]; }
inline int r() { return v[1]; }
inline int s() { return v[2]; }
};
#+end_src
An advantage of this style is that you start seeing patterns where =q=, =r=, =s= are all treated the same way. You can write loops to handle them uniformly instead of duplicating code. You might use SIMD instructions on CPU. You might use =vec3= on the GPU. When you read the equality, =hex_add=, =hex_subtract=, =hex_scale=, =hex_length=, =hex_round=, and =hex_lerp= functions below, you'll see how it might be useful to treat the coordinates uniformly. When you read =hex_to_pixel= and =pixel_to_hex= you'll see that vector and matrix operations (CPU or GPU) can be used with hex coordinates when expressed this way.
Programming is full of tradeoffs. For this page, I want to focus on simplicity and readability, not performance or abstraction, so I'm going to use the first style: cube storage, cube constructor. I find it easiest to understand the algorithms in this style. However, I like all of these styles, and wouldn't hesitate to choose any of them, as long as things are consistent in the project. In a language with multiple constructors, I'd include /both/ the axial and cube constructors for convenience. In C++, the =int= could instead be a template parameter. In C or C++11, the =int v[]= style and the =int q, r, s= style can be [[http://www.reedbeta.com/blog/2013/12/28/on-vector-math-libraries/][merged with a union]]. A template parameter =w= can also be used to distinguish between positions and vectors. Putting all of these together:
#+begin_src cpp
template
struct _Hex { // Both storage types, both constructors
union {
const Number v[3];
struct { const Number q, r, s; };
};
Hex(Number q_, Number r_): v{q_, r_, -q_ - r_} {}
Hex(Number q_, Number r_, Number s_): v{q_, r_, s_} {}
};
typedef _Hex Hex;
typedef _Hex HexDifference;
typedef _Hex FractionalHex;
typedef _Hex FractionalHexDifference;
#+end_src
I didn't use this C++-specific style on this page because I want to make translation to other languages straightforward.
Another design alternative is to use the =x=, =y=, =z= names so that you can make hex coordinates and cartesian coordinates reuse the same data structures. If you're already using a vector library for geometry, you can reuse that for hex coordinates, and then use a matrix library for representing hex-to-pixel and pixel-to-hex operations.
** Equality
:PROPERTIES:
:CUSTOM_ID: hex-equality
:END:
Equality and inequality is straightforward: two hexes are equal if their coordinates are equal. In C++, use ~operator ==~; in Python, define a method =__eq__=; in Java, define a method =equals()=. Use the language's standard style if possible.
#+begin_src cpp
bool operator == (Hex a, Hex b) {
return a.q == b.q && a.r == b.r && a.s == b.s;
}
bool operator != (Hex a, Hex b) {
return !(a == b);
}
#+end_src
** Coordinate arithmetic
:PROPERTIES:
:CUSTOM_ID: hex-arithmetic
:END:
Since cube coordinates come from 3d cartesian coordinates, I automatically get things like addition, subtraction, multiplication, and division. For example, you can have =Hex(2, 0, -2)= that represents two steps northeast, and add that to location =Hex(3, -5, 2)= the obvious way: =Hex(2 + 3, 0 + -5, -2 + -2)=. With other coordinate systems like offset coordinates, you can't do that and get what you want. These operations are what you'd implement with 3d cartesian vectors, but I am using =q=, =r=, =s= names in this class instead of =x=, =y=, =z=:
#+begin_src cpp
Hex hex_add(Hex a, Hex b) {
return Hex(a.q + b.q, a.r + b.r, a.s + b.s);
}
Hex hex_subtract(Hex a, Hex b) {
return Hex(a.q - b.q, a.r - b.r, a.s - b.s);
}
Hex hex_multiply(Hex a, int k) {
return Hex(a.q * k, a.r * k, a.s * k);
}
#+end_src
An alternate design is to reuse an existing vec3 class from your geometry library to represent axial/cube coordinates, and in that case you won't have to write these functions.
** Distance
:PROPERTIES:
:CUSTOM_ID: hex-distance
:END:
The distance between two hexes is the length of the line between them. Both the distance and length operations can come in handy. It looks like [[./#distances][the distance function from the main article]]:
#+begin_src cpp
int hex_length(Hex hex) {
return int((abs(hex.q) + abs(hex.r) + abs(hex.s)) / 2);
}
int hex_distance(Hex a, Hex b) {
return hex_length(hex_subtract(a, b));
}
#+end_src
*** Neighbors
:PROPERTIES:
:CUSTOM_ID: hex-neighbors
:END:
With distance, I defined two functions: length works on one argument and distance works with two. The same is true with neighbors. The direction function is with one argument and the neighbor function is with two. It looks like [[./#neighbors][the neighbors function from the main article]]:
#+begin_src cpp
const vector hex_directions = {
Hex(1, 0, -1), Hex(1, -1, 0), Hex(0, -1, 1),
Hex(-1, 0, 1), Hex(-1, 1, 0), Hex(0, 1, -1)
};
Hex hex_direction(int direction /* 0 to 5 */) {
assert (0 <= direction && direction < 6);
return hex_directions[direction];
}
Hex hex_neighbor(Hex hex, int direction) {
return hex_add(hex, hex_direction(direction));
}
#+end_src
To make directions outside the range 0..5 work, use =hex_directions[(6 + (direction % 6)) % 6]=. Yeah, it's ugly, but it will work with negative directions too. (Side note: it would've been nice to have a [[http://stackoverflow.com/questions/4003232/how-to-code-a-modulo-operator-in-c-c-obj-c-that-handles-negative-numbers][modulo operator]] in C++.)
* Layout
:PROPERTIES:
:CUSTOM_ID: layout
:END:
The next major piece of functionality I need is a way to convert between hex coordinates and screen coordinates. There's a /pointy top/ layout and a /flat top/ hex layout. The conversion uses a matrix as well as the inverse of the matrix, so I need a way to store those. Also, for drawing the corners, pointy top starts at 30° and flat top starts at 0°, so I need a place to store that too.
I'm going to define an *Orientation* helper class to store these: the 2×2 forward matrix, the 2×2 inverse matrix, and the starting angle:
#+begin_src cpp
struct Orientation {
const double f0, f1, f2, f3;
const double b0, b1, b2, b3;
const double start_angle; // in multiples of 60°
Orientation(double f0_, double f1_, double f2_, double f3_,
double b0_, double b1_, double b2_, double b3_,
double start_angle_)
: f0(f0_), f1(f1_), f2(f2_), f3(f3_),
b0(b0_), b1(b1_), b2(b2_), b3(b3_),
start_angle(start_angle_) {}
};
#+end_src
There are only two orientations, so I'm going to make constants for them:
#+begin_src cpp
const Orientation layout_pointy
= Orientation(sqrt(3.0), sqrt(3.0) / 2.0, 0.0, 3.0 / 2.0,
sqrt(3.0) / 3.0, -1.0 / 3.0, 0.0, 2.0 / 3.0,
0.5);
const Orientation layout_flat
= Orientation(3.0 / 2.0, 0.0, sqrt(3.0) / 2.0, sqrt(3.0),
2.0 / 3.0, 0.0, -1.0 / 3.0, sqrt(3.0) / 3.0,
0.0);
#+end_src
Now I will use them for the layout class:
#+begin_src cpp
struct Layout {
const Orientation orientation;
const Point size;
const Point origin;
Layout(Orientation orientation_, Point size_, Point origin_)
: orientation(orientation_), size(size_), origin(origin_) {}
};
#+end_src
Oh, hm, I guess I need a minimal *Point* class. If your graphics/geometry library already provides one, use that.
#+begin_src cpp
struct Point {
const double x, y;
Point(double x_, double y_): x(x_), y(y_) {}
};
#+end_src
Side note: observe how many of these are arrays of numbers underneath. Hex is int[3]. Orientation is an angle, a double, and two matrices, each double[4] or double[2][2]. Point is double[2]. Layout is an Orientation and two Points. Later on the page, FractionalHex is double[3], and OffsetCoord is int[2]. I use structs instead of arrays of numbers because giving a /name/ to things helps me understand them, and also helps with type checking. However, an alternate design choice is to reuse a standard vector library for all of these types, and then use standard matrix multiply for the layout. You can then use your library's matrix inverse to calculate the inverse matrix. Using arrays of numbers (or a numeric array class) instead of separate structs with names will allow you to reuse more code. I chose not to do that but I think it's a reasonable choice.
Ok, now I'm ready to write the layout algorithms.
** Hex to screen
:PROPERTIES:
:CUSTOM_ID: hex-to-pixel
:END:
The main article has [[./#hex-to-pixel][two versions of hex-to-pixel]], one for each orientation. The code is essentially the same except the numbers are different, so for this implementation I've put the numbers into the Orientation class, as =f0= through =f3=:
#+begin_src cpp
Point hex_to_pixel(Layout layout, Hex h) {
const Orientation& M = layout.orientation;
double x = (M.f0 * h.q + M.f1 * h.r) * layout.size.x;
double y = (M.f2 * h.q + M.f3 * h.r) * layout.size.y;
return Point(x + layout.origin.x, y + layout.origin.y);
}
#+end_src
Unlike the main article, I have a separate x size and y size. That allows two things:
- You can stretch and squash the hexagon to match whatever size pixel art you have. Note that =size.x= and =size.y= are /not/ the width and height of the hexagons.
- You can use a /negative value/ for the y size to flip the y axis.
Also, the main article assumes the q=0,r=0 hexagon is centered at x=0,y=0, but in general, you might want to center it anywhere. You can do that by adding the center (=layout.origin=) to the result.
** Screen to hex
:PROPERTIES:
:CUSTOM_ID: pixel-to-hex
:END:
The main article has [[./#pixel-to-hex][two versions of pixel-to-hex]], one for each orientation. Again, the code is the same except for the numbers, which are the inverse of the matrix. I put the matrix inverse into the Orientation class, as =b0= through =b3=, and used it here. In the forward direction, to go from hex coordinates to screen coordinates I /first/ multiply by the matrix, /then/ multiply by the size, /then/ add the origin. To go in the reverse direction, I have to undo these. /First/ undo the origin by subtracting it, /then/ undo the size by dividing by it, /then/ undo the matrix multiply by multiplying by the inverse:
#+begin_src cpp
FractionalHex pixel_to_hex(Layout layout, Point p) {
{
const Orientation& M = layout.orientation;
Point pt = Point((p.x - layout.origin.x) / layout.size.x,
(p.y - layout.origin.y) / layout.size.y);
double q = M.b0 * pt.x + M.b1 * pt.y;
double r = M.b2 * pt.x + M.b3 * pt.y;
return FractionalHex(q, r, -q - r);
}
#+end_src
There's a complication here: I start with integer hex coordinates to go to screen coordinates, but when going in reverse, I have no guarantee that the screen location will be exactly at a hexagon center. Instead of getting back an integer hex coordinate, I get back a floating point value (type =double=), which means I return a *FractionalHex* instead of a *Hex*. To get back to the integer, I need to [[./#rounding][round]] it to the nearest hex. I'll implement that in a bit.
** Drawing a hex
:PROPERTIES:
:CUSTOM_ID: hex-geometry
:END:
To draw a hex, I need to know where each corner is relative to the center of the hex. With the flat top orientation, the corners are at 0°, 60°, 120°, 180°, 240°, 300°. With pointy top, they're at 30°, 90°, 150°, 210°, 270°, 330°. I encode that in the Orientation class's =start_angle= value, either 0.0 for 0° or 0.5 for 60°.
Once I know where the corners are relative to the center, I can calculate the corners in screen locations by adding the center to each corner, and putting the coordinates into an array.
#+begin_src cpp
Point hex_corner_offset(Layout layout, int corner) {
Point size = layout.size;
double angle = 2.0 * M_PI *
(layout.orientation.start_angle + corner) / 6;
return Point(size.x * cos(angle), size.y * sin(angle));
}
vector polygon_corners(Layout layout, Hex h) {
vector corners = {};
Point center = hex_to_pixel(layout, h);
for (int i = 0; i < 6; i++) {
Point offset = hex_corner_offset(layout, i);
corners.push_back(Point(center.x + offset.x,
center.y + offset.y));
}
return corners;
}
#+end_src
*** TODO Make hex_corner_offset line up with hex_neighbor
The way =hex_corner_offset= works is different enough from =hex_neighbor= that I can't use the corner offset for anything other than drawing the entire polygon. This is not ideal. I sometimes want to draw corners or edges. I need to study this a bit more before I can recommend a better =hex_corner_offset= function. This might tie into the [[http://www-cs-students.stanford.edu/~amitp/game-programming/grids/][corner and edge labeling]] I've tried in the past.
** Layout examples
:PROPERTIES:
:CUSTOM_ID: layout-examples
:END:
Ok, let's try it out! I have written Hex, Orientation, Layout, and Point and the functions that go with each. That's enough for me to draw hexes. I'm going to use the Javascript version of these functions to draw some hexes in the browser.
Let's try the two orientations, =layout_pointy= and =layout_flat=:
#+begin_export html