Implementation of Hex Grids

 from Red Blob Games
6 May 2015

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.

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.

I’m going to use C++ for the code samples, but I also have Java, C#, Python, Javascript, Haxe, and Lua versions of the code.

 1  Hex coordinates#

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, z, y I use on the main page. Note the order is different: on the main page, axial r corresponds to cube z, so Hex(q, r, s) is the same as Cube(q, s, r). This is confusing, I know, but the alternative was to use Hex(q, s, r) which I think is also confusing. Sorry about that. I will have to fix this at some point.

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);
    }
};

Pretty simple. Here’s a class that stores axial coordinates internally, but uses cube coordinates for the interface:

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_; }
};

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:

struct Hex { // Cube storage, axial constructor
    const int q, r, s;
    Hex(int q_, int r_): q(q_), r(r_), s(-q_ - r_) {}
};

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:

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]; }
};

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 merged with a union[1]. A template parameter w can also be used to distinguish between positions and vectors. Putting all of these together:

template <typename Number, int w>
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<int, 1> Hex;
typedef _Hex<int, 0> HexDifference;
typedef _Hex<double, 1> FractionalHex;
typedef _Hex<double, 0> FractionalHexDifference;

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.

 1.1. Equality

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.

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);
}

 1.2. Coordinate arithmetic

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:

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);
}

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.

 1.3. Distance

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 the distance function from the main article:

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));
}

1.3.1. Neighbors

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 the neighbors function from the main article:

const vector<Hex> 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));
}

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 modulo operator[2] in C++.)

 2  Layout#

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:

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_) {}
};

There are only two orientations, so I’m going to make constants for them:

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);

Now I will use them for the layout class:

struct Layout {
    const Orientation orientation;
    const Point size;
    const Point origin;
    Layout(Orientation orientation_, Point size_, Point origin_)
    : orientation(orientation_), size(size_), origin(origin_) {}
};

Oh, hm, I guess I need a minimal Point class. If your graphics/geometry library already provides one, use that.

struct Point {
    const double x, y;
    Point(double x_, double y_): x(x_), y(y_) {}
};

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.

 2.1. Hex to screen

The main article has 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:

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);
}

Unlike the main article, I have a separate x size and y size. That allows two things:

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.

 2.2. Screen to hex

The main article has 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:

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);
}

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 round it to the nearest hex. I’ll implement that in a bit.

 2.3. Drawing a hex

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.

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<Point> polygon_corners(Layout layout, Hex h) {
    vector<Point> 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;
}

2.3.1.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 corner and edge labeling[3] I’ve tried in the past.

 2.4. Layout examples

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:

Let’s try three different sizes, Point(10, 10), Point(20, 20), and Point(40, 40):

Let’s try stretching the hexes, by setting size to Point(15, 25) and Point(25, 15):

Let’s try a downward y-axis with size set to Point(25, 25) and a flipped y-axis (upward) with size set to Point(25, -25). Look closely at how r increases downwards vs upwards:

I think that’s a reasonable set of tests for the orientation and size, and it shows that the Layout class can handle a wide variety of needs, without having to make different variants of the Hex class.

 3  Fractional Hex#

For pixel-to-hex I need fractional hex coordinates. It looks like the Hex class, but uses double instead of int:

struct FractionalHex {
    const double q, r, s;
    FractionalHex(double q_, double r_, double s_)
    : q(q_), r(r_), s(s_) {}
};

 3.1. Hex rounding

Rounding turns a fractional hex coordinate into the nearest integer hex coordinate. The algorithm is straight out of the main article:

Hex hex_round(FractionalHex h) {
    int q = int(round(h.q));
    int r = int(round(h.r));
    int s = int(round(h.s));
    double q_diff = abs(q - h.q);
    double r_diff = abs(r - h.r);
    double s_diff = abs(s - h.s);
    if (q_diff > r_diff and q_diff > s_diff) {
        q = -r - s;
    } else if (r_diff > s_diff) {
        r = -q - s;
    } else {
        s = -q - r;
    }
    return Hex(q, r, s);
}

 3.2. Line drawing

To draw a line, I linearly interpolate between two hexes, and then round it to the nearest hex. To linearly interpolate between hex coordinates I linearly interpolate each of the components (q, r, s) independently:

float lerp(double a, double b, double t) {
    return a * (1-t) + b * t;
    /* better for floating point precision than
       a + (b - a) * t, which is what I usually write */
}

FractionalHex hex_lerp(Hex a, Hex b, double t) {
    return FractionalHex(lerp(a.q, b.q, t),
                         lerp(a.r, b.r, t),
                         lerp(a.s, b.s, t));
}

Line drawing is not too bad once I have linear interpolation:

vector<Hex> hex_linedraw(Hex a, Hex b) {
    int N = hex_distance(a, b);
    vector<Hex> results = {};
    double step = 1.0 / max(N, 1);
    for (int i = 0; i <= N; i++) {
        results.push_back(hex_round(hex_lerp(a, b, step * i)));
    }
    return results;
}

I needed to stick that max(N, 1) bit in there to handle lines with length 0 (when A == B).

Sometimes the hex_lerp will output a point that’s on an edge. On some systems, the rounding code will push that to one side or the other, somewhat unpredictably and inconsistently. To make it always push these points in the same direction, add an “epsilon” value to a. This will “nudge” things in the same direction when it’s on an edge, and leave other points unaffected.

vector<Hex> hex_linedraw(Hex a, Hex b) {
    int N = hex_distance(a, b);
    FractionalHex a_nudge(a.q + 1e-6, a.r + 1e-6, a.s - 2e-6);
    FractionalHex b_nudge(b.q + 1e-6, b.r + 1e-6, b.s - 2e-6);
    vector<Hex> results = {};
    double step = 1.0 / max(N, 1);
    for (int i = 0; i <= N; i++) {
        results.push_back(
            hex_round(hex_lerp(a_nudge, b_nudge, step * i)));
    }
    return results;
}

The nudge is not always needed. You might try without it first.

 4  Map#

There are two related problems to solve: how to generate a shape and how to store map data. Let’s start with storing map data.

 4.1. Map storage

The simplest way to store a map is to use a hash table. In C++, in order to use unordered_map<Hex,_> or unordered_set<Hex> I need to define a hash function for Hex. It would’ve been nice if C++ made it easier to define this, but it’s not too bad. I hash the q and r fields (I can skip s because it’s redundant), and combine them using the algorithm from Boost’s hash_combine:

namespace std {
    template <> struct hash<Hex> {
        size_t operator()(const Hex& h) const {
            hash<int> int_hash;
            size_t hq = int_hash(h.q);
            size_t hr = int_hash(h.r);
            return hq ^ (hr + 0x9e3779b9 + (hq << 6) + (hq >> 2));
        }
    };
}

Here’s an example of making a map with a float height at each hex:

unordered_map<Hex, float> heights;
heights[Hex(1, -2, 3)] = 4.3;
cout << heights[Hex(1, -2, 3)];

The hash table by itself isn’t that useful. I need to combine it with something that creates a map shape. In graph terms, I need something that creates the nodes.

 4.2. Map shapes

In this section I write some loops that will produce various shapes of maps. You can use these loops to make a set of hex coordinates for your map, or fill in a map data structure, or iterate over the locations in the map. I’ll write sample code that fills in a set of hex coordinates.

4.2.1. Parallelograms

With axial/cube coordinates, a straightforward loop over coordinates will produce a parallelogram map instead of a rectangular one.

unordered_set<Hex> map;
for (int q = q1; q <= q2; q++) {
    for (int r = r1; r <= r2; r++) {
        map.insert(Hex(q, r, -q-r)));
    }
}

There are three coordinates, and the loop requires you choose any two of them: (q,r), (s,q), or (r,s) lead to these pointy top maps, respectively:

And these flat top maps:

4.2.2. Triangles

There are two directions for triangles to face, and the loop depends on which direction you use. Assuming the y axis points down, with pointy top these triangles face south/northwest/northeast, and with flat top these triangles face east/northwest/southwest.

unordered_set<Hex> map;
for (int q = 0; q <= map_size; q++) {
    for (int r = 0; r <= map_size - q; r++) {
        map.insert(Hex(q, r, -q-r));
    }
}

With pointy top these triangles face north/southwest/southeast and with flat top these triangles face west/northeast/southeast:

unordered_set<Hex> map;
for (int q = 0; q <= map_size; q++) {
    for (int r = map_size - q; r <= map_size; r++) {
        map.insert(Hex(q, r, -q-r));
    }
}

If your flip your y-axis, then it’ll switch north and south here, as you might expect.

4.2.3. Hexagons

Generating a hexagonal shape map is described on the main page.

unordered_set<Hex> map;
for (int q = -map_radius; q <= map_radius; q++) {
    int r1 = max(-map_radius, -q - map_radius);
    int r2 = min(map_radius, -q + map_radius);
    for (int r = r1; r <= r2; r++) {
        map.insert(Hex(q, r, -q-r));
    }
}

Here’s what I get for pointy top and flat top orientations:

4.2.4. Rectangles

With axial/cube coordinates, getting rectangular maps is a little trickier! The main article gives a clue but I don’t actually show the code. The code depends on whether using flat top or pointy top hexes. The trick is to loop over offset coordinates and then convert those to axial. Let’s start with pointy topped hexes:

unordered_set<Hex> map;
for (int r = top; r <= bottom; r++) { // pointy top
    int r_offset = floor(r/2.0); // or r>>1
    for (int q = left - r_offset; q <= right - r_offset; q++) {
        map.insert(Hex(q, r, -q-r));
    }
}

That loop can produce grids like these:


left=0 right=6 top=0 bottom=4

left=-3 right=+3 top=-2 bottom=+2

The left/right/top/bottom are essentially offset coordinates, as offset coordinates are a more natural fit for rectangular maps.

How about flat topped hexes?

unordered_set<Hex> map;
for (int q = left; q <= right; q++) { // flat top
    int q_offset = floor(q/2.0); // or q>>1
    for (int r = top - q_offset; r <= bottom - q_offset; r++) {
        map.insert(Hex(q, r, -q-r));
    }
}

left=0 right=6 top=0 bottom=4

left=-3 right=+3 top=-2 bottom=+2

You might also need to experiment to get exactly the map you want. Try setting the offset to floor((q+1)/2.0) or floor((q-1)/2.0) instead of floor(q/2.0) for example, and the boundary will change slightly.

 4.3. Optimized storage

The hash table approach is pretty generic and works with any shape of map, including weird shapes and shapes with holes. You can view it as a type of node-and-edge graph structure, storing the nodes but explicitly but calculating the edges on the fly with the hex_neighbor function.

A different way to store the node-and-edge graph structure is to calculate all the edges ahead of time and store them explicitly. Give each node an integer id and then use an array of arrays to store neighbors. Or make each node an object and use a field to store a list of neighbors. These graph structures are also generic and work with any shape of map. You can also use any graph algorithm on them, such as movement range, distance map, or pathfinding. Storing the edges implicitly works well when the map is regular or is being edited; storing them explicitly can work well when the map is irregularly shaped (boundary, walls, holes) and isn’t changing frequently.

Some map shapes also allow a compact 2d or 1d array. The main article gives a visual explanation. Here, I’ll give an explanation based on code. The main idea is that for all the map shapes, there is a nested loop of the form

for (int a = a1; a < a2; a++) {
    for (int b = b1; b < b2; b++) {
        ...
    }
}

For compact map storage, I’ll make an array of arrays, and index it with array[a-a1][b-b1]. I subtract where the loop starts so that the first index will be 0. For example, here’s the code for a rectangular shape with pointy top hexes: (for flat top hexes, the loop is different)

for (int r = top; r <= bottom; r++) {
    int r_offset = floor(r/2.0);
    for (int q = left - r_offset; q <= right - r_offset; q++) {
        map.insert(Hex(q, r, -q-r));
    }
}

For pointy top hexes, variable a is r, and b is q. Value a1 (where the r loop starts) is top and b1 (where the q loop starts) is left - floor(r/2.0). That means the array will be indexed array[r-top][q-(left-floor(r/2.0))] which simplifies to array[r-top][q-left+floor(r/2.0)]. Note that floor(r/2.0) can be written r>>1.

The second thing I need to know is the size of the arrays. I need a2-a1 arrays, and the size of each should be b2-b1. Be sure to check for off-by-1 errors: if the loop is written a <= a2 then you’ll want a2-a1+1 arrays, and similarly for b <= b2. I can build these arrays using C++ vectors using this pattern:

vector<vector<T>> map(a2-a1);
for (int a = a1; a < a2; a++) {
    map.emplace_back(b2-b1);
}

For the rectangle example, a2-a1 becomes bottom-top+1 and b2-b1 becomes right-left+1:

int height = bottom - top + 1;
vector<vector<T>> map(height);
for (int r = 0; r < height; r++) {
    int width = right - left + 1;
    map.emplace_back(width);
}

I can encapsulate all of this into a Map class:

template<class T> class RectangularPointyTopMap {
    vector<vector<T>> map;

    int left_, top_;
  public:
    RectangularPointyTopMap(int left, int top, int right, int bottom)
                 : left_(left), top_(top)
    {
        int height = bottom - top + 1;
        map.resize(height);
        for (int r = 0; r < height; r++) {
            int width = right - left + 1;
            map.emplace_back(width);
        }
    }

    inline T& at(int q, int r) {
        return map[r - top_][q - left_ + (r >> 1)];
    }
};

For the other map shapes, it’s only slightly more complicated, but the same pattern applies: I have to study the loop that created the map in order to figure out the size and array access for the map.

1d arrays are trickier and I won’t try to tackle them here. In practice, I rarely use array storage for hex maps, except when the maps are large, and my code is written in C++. Although it’s more compact, it almost never makes a difference in practice in my projects. For most of my projects, I use a hash table and/or graph representation. It gives me the most flexibility and reusability. I only need the more compact storage when storage size matters.

 5  Rotation#

There are two one-step rotation functions, but which is “left” and which is “right” depends on your map orientation. You may have to swap these.

Hex hex_rotate_left(Hex a)
{
    return Hex(-a.s, -a.q, -a.r);
}

Hex hex_rotate_right(Hex a)
{
    return Hex(-a.r, -a.s, -a.q);
}

Note that these are slightly different from the main page because q,r,s don’t quite line up with x,y,z.

If you think of the coordinates v in vector format, these operations are 3x3 matrix multiplies, M times v, where M = [0 0 -1; -1 0 0; 0 -1 0]. The matrix inverse M-1 = [0 -1 0; 0 0 -1; -1 0 0] rotates in the opposite direction. Raising the matrix to a power Mk rotates k times. You can precomputate all the rotation matrices, or combine the matrix with other operations such as translate, scale, etc.

 6  Offset coordinates#

I use the names q and r for cube/axial coordinates, and col and row for offset coordinates:

struct OffsetCoord {
    const int col, row;
    OffsetCoord(int col_, int row_): col(col_), row(row_) {}
};

I’m expecting that I’ll use the cube/axial Hex class everywhere, except for displaying to the player. That’s where offset coordinates will be useful. That means the only operations I need are converting Hex to OffsetCoord and back.

There are four offset types: odd-r, even-r, odd-q, even-q. The “r” types are used with with pointy top hexagons and the “q” types are used with flat top. Whether it’s even or odd can be encoded as an offset direction +1 or -1. For pointy top, the offset direction tells us whether to slide alternate rows right or left. For flat top, the offset direction tells us whether to slide alternate columns up or down.

const int EVEN = +1;
const int ODD = -1;

OffsetCoord qoffset_from_cube(int offset, Hex h) {
    assert(offset == EVEN || offset == ODD);
    int col = h.q;
    int row = h.r + int((h.q + offset * (h.q & 1)) / 2);
    return OffsetCoord(col, row);
}

Hex qoffset_to_cube(int offset, OffsetCoord h) {
    assert(offset == EVEN || offset == ODD);
    int q = h.col;
    int r = h.row - int((h.col + offset * (h.col & 1)) / 2);
    int s = -q - r;
    return Hex(q, r, s);
}

OffsetCoord roffset_from_cube(int offset, Hex h) {
    assert(offset == EVEN || offset == ODD);
    int col = h.q + int((h.r + offset * (h.r & 1)) / 2);
    int row = h.r;
    return OffsetCoord(col, row);
}

Hex roffset_to_cube(int offset, OffsetCoord h) {
    assert(offset == EVEN || offset == ODD);
    int q = h.col - int((h.row + offset * (h.row & 1)) / 2);
    int r = h.row;
    int s = -q - r;
    return Hex(q, r, s);
}

If you’re only using even or odd, you can hard-code the value of offset into the code, making it simpler and faster. Alternatively, offset can be a template parameter so that the compiler can inline and optimize it.

For offset coordinates I need to know if a row/col is even or odd, and use a&1 (bitwise and[4]) instead of a%2 return 0 or +1. Why?

Also, in many (all?) languages, & has lower precedence than + so be sure to parenthesize a&1.

 7  Notes#

 7.1. Cube vs Axial

Cube coordinates are three numbers, but one can be computed from the others. Whether you want to store the third one as a field or compute it in an accessor is primarily a code style decision. If performance is the main concern, the cost of the accessor vs the cost of the computation will matter most. In languages like C++ where accessors are inlined away, save the memory (accessing RAM is expensive) and use an accessor. In languages like Python where accessors are expensive, save the function call (function calls are expensive) and store the third coordinate in a field.

Also take a look at this paper[8] which found axial and cube to be faster than offset for line of sight, distance, and other algorithms, but slower than offset for displaying offset coordinates (as expected). I can’t find their code though.

If performance matters, the best thing to do is to actually measure it.

 7.2. C++

 7.3. Python, Javascript

 8  Source Code#

 8.1. Code from this page

I have some unoptimized incomplete code in several languages, with some unit tests too, but no documentation or examples. Feel free to use these as a starting point writing your hex grid library:

Caveat: this is procedurally generated code (yes, really![9]) and doesn’t follow the best style and idiom recommendations for each language. It’d be cool to add Racket, Ruby, Haskell, Swift, and others, but I don’t know when I might have time to do that.

My procedural code generator is kinda awful but if you want to take a look at it, it’s codegen.zip.

[Changed 2016-07-20] I changed the winding direction for hex_corner_offset to match that of hex_neighbor; this should not matter in theory but it’s nice for them to match.

[Changed 2018-03-10] I changed the Java, C#, and Typescript output to use instance methods instead of static methods. I added a precondition invariant check to make sure q+r+s == 0 when you call the Hex constructor. This should help catch bugs sooner.

 8.2. Other libraries

It’s worth looking at these libraries, some of which include source code:

Also for Unity take a look at CatlikeCoding’s tutorial[72].

Email me , or tweet @redblobgames, or comment:

Endnotes

  1. [1]: http://www.reedbeta.com/blog/2013/12/28/on-vector-math-libraries/
  2. [2]: http://stackoverflow.com/questions/4003232/how-to-code-a-modulo-operator-in-c-c-obj-c-that-handles-negative-numbers
  3. [3]: http://www-cs-students.stanford.edu/~amitp/game-programming/grids/
  4. [4]: http://en.wikipedia.org/wiki/Bitwise_operation#AND
  5. [5]: http://en.wikipedia.org/wiki/Two’s_complement
  6. [6]: http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2018/p0907r0.html
  7. [7]: http://en.wikipedia.org/wiki/Modular_arithmetic#Remainders
  8. [8]: http://cs.ucla.edu/~tianyi.zhang/perfdiff.pdf
  9. [9]: http://simblob.blogspot.com/2015/03/hex-grids-code-generation.html
  10. [10]: http://gamelogic.co.za/grids/
  11. [11]: http://hexgridutilities.codeplex.com/
  12. [12]: https://github.com/tejon/HexCoord
  13. [13]: https://github.com/DigitalMachinist/HexGrid
  14. [14]: https://github.com/Amaranthos/UnityHexGrid/
  15. [15]: https://github.com/svejdo1/HexGrid
  16. [16]: https://github.com/Banbury/UnityHexGrid
  17. [17]: https://aurelwu.github.io/
  18. [18]: https://github.com/grantmoore3d/unity-hexagonal-grids
  19. [19]: https://github.com/imurashka/HexagonalLib
  20. [20]: https://github.com/Clpsplug/hexagonal_map
  21. [21]: https://github.com/Hexworks/mixite
  22. [22]: https://github.com/Sscchhmueptfter/HexUtils
  23. [23]: https://github.com/timgilbert/scala-hexmap
  24. [24]: https://github.com/mraad/grid-hex
  25. [25]: https://github.com/dmccabe/khexgrid
  26. [26]: https://github.com/denizztret/ObjectiveHexagon
  27. [27]: https://github.com/pkclsoft/HexLib
  28. [28]: https://github.com/MadGeorge/AmitsHexGridLibrarySwift
  29. [29]: https://github.com/fananek/HexGrid
  30. [30]: https://github.com/mpalmerlee/HexagonTools
  31. [31]: https://github.com/RobertBrewitz/axial-hexagonal-grid
  32. [32]: https://github.com/flauwekeul/honeycomb
  33. [33]: https://github.com/bodinaren/BHex.js
  34. [34]: https://github.com/Hellenic/react-hexgrid/
  35. [35]: https://github.com/vonWolfehaus/von-grid/
  36. [36]: https://github.com/othree/hexagons
  37. [37]: https://github.com/cefleet/hexAPI
  38. [38]: https://github.com/njlr/solid-hex
  39. [39]: https://github.com/aahdee/p5grid
  40. [40]: https://github.com/joshuabowers/hexagonally
  41. [41]: https://github.com/scrapcupcake/hexs6
  42. [42]: https://github.com/euoia/hex-grid.js
  43. [43]: https://github.com/RedFT/Hexy
  44. [44]: https://github.com/stephanh42/hexutil
  45. [45]: https://github.com/BorisTheBrave/grids
  46. [46]: https://github.com/czuger/rhex
  47. [47]: https://github.com/SpeciesFileGroup/waxy
  48. [48]: http://package.elm-lang.org/packages/Voronchuk/hexagons/2.0.0
  49. [49]: https://github.com/danneu/elm-hex-grid
  50. [50]: https://github.com/etaque/elm-hexagons
  51. [51]: https://github.com/alkavan/hexagon-tiles
  52. [52]: https://github.com/dpc/hex2d-rs
  53. [53]: https://github.com/toasteater/beehive
  54. [54]: https://github.com/leftiness/hex_math
  55. [55]: https://github.com/ozkriff/zemeroth
  56. [56]: https://github.com/iancormac84/hexae
  57. [57]: https://gitlab.com/hankruiger/bestagon
  58. [58]: https://github.com/icrawler/HexaMoon
  59. [59]: https://gist.github.com/ontoclasm/27641290d389a36dd66a017a8b18c9fa
  60. [60]: https://github.com/droxmusic/HexMap
  61. [61]: https://github.com/DDoop/HexTesting
  62. [62]: https://github.com/romlok/godot-gdhexgrid
  63. [63]: https://github.com/mhwombat/grid/wiki
  64. [64]: https://github.com/RyanMcNamara86/Hex
  65. [65]: https://github.com/andeemarks/clj-hex-grid
  66. [66]: https://github.com/rayalex/hexgrid
  67. [67]: https://gist.github.com/zacharycarter/c5565930ba57af5554bb8180d566f067
  68. [68]: https://github.com/pmcxs/hexgrid
  69. [69]: https://github.com/hautenessa/hexagolang
  70. [70]: https://github.com/GiovineItalia/Hexagons.jl
  71. [71]: https://pub.dartlang.org/packages/hexagonal_grid
  72. [72]: http://catlikecoding.com/unity/tutorials/hex-map/part-1/