#+TITLE: Implementation of Hex Grids
#+DATE: <2015-05-06>
#+OPTIONS: toc:2

#+begin_export html
<style>
figure { display: grid; grid-column-gap: 0.25em; grid: auto-flow / repeat(auto-fit, minmax(7em, 1fr)); }
canvas { background-color: hsl(60, 5%, 95%); border: 1px solid hsl(60, 5%, 90%); }
</style>
#+end_export

#+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 [[href:/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.

#+begin_note
You can [[#code][download the code samples]] in C++, Python, C#, Haxe, Java, JavaScript, TypeScript, Lua, or you find [[#third-party][an existing library]] instead of reimplementing these functions.
#+end_note


* Hex coordinates
:PROPERTIES:
:CUSTOM_ID: hex
:END:

On the main page, I treat Cube and Axial systems separately. Cube coordinates derived from x,y,z cartesian coordinates, and use three axes q,r,s 120° apart, where q+r+s = 0. Axial coordinates have two axes q,r that are 120° apart.

#+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 [[https://www.reedbeta.com/blog/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 <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;
#+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> 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 [[https://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

#+begin_comment
The naming could be better, e.g. f0 could be x_from_q, f1 could be x_from_r, etc.
#+end_comment

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

The =layout.origin= variable sets the /center/ of the q=0,r=0 hexagon. It's a /translate/ transformation. The =layout.size= is a /scale/ transform. Unlike the main article, I have a separate =x= size and =y= size. I'll show some uses of these in the [[Layout examples]] section below.

** 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<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;
}
#+end_src

#+begin_comment
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.
#+end_comment 

** 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
<figure>
<canvas id="layout-test-orientation-pointy" width="300" height="200"/>
<canvas id="layout-test-orientation-flat" width="300" height="200"/>
</figure>
#+end_export

Let's try three different values for =size=: ~Point(10, 10)~, ~Point(25, 25)~, and ~Point(50, 50)~. When the two values are the same, we get /regular/ hexagons. The =size= value is half the height for pointy-top hexagons and half the width for flat-top hexagons.

#+begin_export html
<figure>
<canvas id="layout-test-size-1" width="200" height="200"/>
<canvas id="layout-test-size-2" width="200" height="200"/>
<canvas id="layout-test-size-3" width="200" height="200"/>
</figure>
#+end_export

One reason =size= has a separate =x= and =y= is that when the two values are /different/, we can stretch the hexes to *fit sprite assets*. From [[href:./#basics][the main page]], we can use these calculations:

- for /flat top/ art sprites =W✕H=, set =size= to ~Point(W/2, H/sqrt(3))~. The example fits 100✕100 sprites that are slightly taller.
- for /pointy top/ art sprites =W✕H=, set =size= to ~Point(W/sqrt(3), H/2)~. The example fits 100✕100 sprites that are slightly wider.

#+begin_export html
<figure>
<canvas id="layout-test-size-tall" width="300" height="250"/>
<canvas id="layout-test-size-wide" width="300" height="250"/>
</figure>
#+end_export

Another thing we can do with =size= is to *flip the r axis*. Compare =size= set to  ~Point(25, 25)~ and set to ~Point(25, -25)~. This is also useful if your y-axis grows upwards, as you can choose whether to make the =r= coordinate grow upwards with =y= (positive =size.y=) or downwards opposite of =y= (negative =size.y=).

#+begin_export html
<figure>
<canvas id="layout-test-y-down" width="300" height="200"/>
<canvas id="layout-test-y-up" width="300" height="200"/>
</figure>
#+end_export

The =origin= is occasionally useful too. I usually set it to ~Point(0, 0)~. That puts the /center/ of the q=0,r=0 hexagon  at x=0,y=0. But if we want the *top left* of that hexagon to be at x=0,y=0 then:

- for /flat top/ hexes, set =origin= to ~Point(size.x, size.y * sqrt(3)/2)~:

#+begin_export html
<figure>
<canvas id="layout-test-origin-flat-centered" width="300" height="250"/>
<canvas id="layout-test-origin-flat-topleft" width="300" height="250"/>
</figure>
#+end_export

- for /pointy top/ hexes, set =origin= to ~Point(size.x * sqrt(3)/2, size.y)~:

#+begin_export html
<figure>
<canvas id="layout-test-origin-pointy-centered" width="300" height="250"/>
<canvas id="layout-test-origin-pointy-topleft" width="300" height="250"/>
</figure>
#+end_export

You can of course set =size= or =offset= for reasons other than these. I think the above diagrams are a reasonable set of tests for the =orientation=, =size=, and =origin=. It shows that the =Layout= class can handle a wide variety of needs, without having to make different variants of the *Hex* class.

* Fractional Hex
:PROPERTIES:
:CUSTOM_ID: fractionalhex
:END:

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

#+begin_src cpp
struct FractionalHex {
    const double q, r, s;
    FractionalHex(double q_, double r_, double s_)
    : q(q_), r(r_), s(s_) {}
};
#+end_src

** Hex rounding
:PROPERTIES:
:CUSTOM_ID: rounding
:END:

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

#+begin_src cpp
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);
}
#+end_src

** Line drawing
:PROPERTIES:
:CUSTOM_ID: line-drawing
:END:

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:

#+begin_src cpp
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));
}
#+end_src

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

#+begin_src cpp
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;
}
#+end_src

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.

#+begin_src cpp
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;
}
#+end_src

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

* Map
:PROPERTIES:
:CUSTOM_ID: map
:END:

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.

** Map storage
:PROPERTIES:
:CUSTOM_ID: map-storage
:END:

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=:

#+begin_src cpp
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));
        }
    };
}
#+end_src

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

#+begin_src cpp
unordered_map<Hex, float> heights;
heights[Hex(1, -2, 3)] = 4.3;
cout << heights[Hex(1, -2, 3)];
#+end_src

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.

** Map shapes
:PROPERTIES:
:CUSTOM_ID: map-shapes
:END:

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.

*** Parallelograms
    :PROPERTIES:
    :CUSTOM_ID: shape-parallelogram
    :END:
    
    
With axial/cube coordinates, a straightforward loop over coordinates will produce a parallelogram map instead of a rectangular one.

#+begin_src cpp
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)));
    }
}
#+end_src

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:

#+begin_export html
<figure>
<canvas id="shape-pointy-parallelogram-qr" width="200" height="200"/>
<canvas id="shape-pointy-parallelogram-sq" width="200" height="200"/>
<canvas id="shape-pointy-parallelogram-rs" width="200" height="200"/>
</figure>
#+end_export

And these flat top maps:

#+begin_export html
<figure>
<canvas id="shape-flat-parallelogram-qr" width="200" height="200"/>
<canvas id="shape-flat-parallelogram-sq" width="200" height="200"/>
<canvas id="shape-flat-parallelogram-rs" width="200" height="200"/>
</figure>
#+end_export

*** Triangles
    :PROPERTIES:
    :CUSTOM_ID: shape-triangle
    :END:
    
    
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.

#+begin_src cpp
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));
    }
}
#+end_src

#+begin_export html
<figure>
<canvas id="shape-pointy-triangle-1" width="250" height="175"/>
<canvas id="shape-pointy-triangle-2" width="250" height="175"/>
</figure>
#+end_export

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

#+begin_src cpp
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));
    }
}
#+end_src

#+begin_export html
<figure>
<canvas id="shape-flat-triangle-1" width="250" height="175"/>
<canvas id="shape-flat-triangle-2" width="250" height="175"/>
</figure>
#+end_export

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

*** Hexagons
    :PROPERTIES:
    :CUSTOM_ID: shape-hexagon
    :END:
    
    
Generating a hexagonal shape map is described [[./#range][on the main page]].

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

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

#+begin_export html
<figure>
<canvas id="shape-pointy-hexagon" width="200" height="200"/>
<canvas id="shape-flat-hexagon" width="200" height="200"/>
</figure>
#+end_export

*** Rectangles
    :PROPERTIES:
    :CUSTOM_ID: shape-rectangle
    :END:
    
    
With axial/cube coordinates, getting rectangular maps is a little trickier! The [[./#map-storage][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 top hexes*:

#+begin_src cpp
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));
    }
}
#+end_src

That loop can produce grids like these:

#+begin_export html
<figure>
  <div>
    <canvas id="shape-pointy-rectangle-topleft" width="300" height="200"/>
    <br/>
    <code>left=0 right=6 top=0 bottom=4</code>
  </div>
  <div>
    <canvas id="shape-pointy-rectangle-centered" width="300" height="200"/>
    <br/>
    <code>left=-3 right=+3 top=-2 bottom=+2</code>
  </div>
</figure>
#+end_export

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

How about *flat top hexes*? 

#+begin_src cpp
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));
    }
}
#+end_src

#+begin_export html
<figure>
  <div>
    <canvas id="shape-flat-rectangle-topleft" width="250" height="210"/>
    <br/>
    <code>left=0 right=6 top=0 bottom=4</code>
  </div>
  <div>
    <canvas id="shape-flat-rectangle-centered" width="250" height="210"/>
    <br/>
    <code>left=-3 right=+3 top=-2 bottom=+2</code>
  </div>
</figure>
#+end_export

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.

** Optimized storage
:PROPERTIES:
:CUSTOM_ID: map-optimized-storage
:END:

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 [[./#map-storage][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

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

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)

#+begin_src cpp
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));
    }
}
#+end_src

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:

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

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

#+begin_src cpp
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);
}
#+end_src

I can encapsulate all of this into a Map class:

#+begin_src cpp
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)];
    }
};
#+end_src

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.

* Rotation
:PROPERTIES:
:CUSTOM_ID: rotation
:END:

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.

#+begin_src cpp
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);
}
#+end_src

Note that these are slightly different from the [[./#rotation][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 M^{/k/} rotates /k/ times. You can precomputate all the rotation matrices, or combine the matrix with other operations such as translate, scale, etc.
        

* Offset coordinates
:PROPERTIES:
:CUSTOM_ID: offset
:END:

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

#+begin_src cpp
struct OffsetCoord {
    const int col, row;
    OffsetCoord(int col_, int row_): col(col_), row(row_) {}
};
#+end_src

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.

#+begin_src cpp
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);
}
#+end_src

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= ([[https://en.wikipedia.org/wiki/Bitwise_operation#AND][bitwise and]]) instead of =a%2= return 0 or +1. Why?

- On systems using [[https://en.wikipedia.org/wiki/Two's_complement][two's complement]] representation, which is just about every system out there, =a&1= returns 0 for even =a= and 1 for odd =a=. This is what I want. It's not strictly portable, but [[https://www.open-std.org/jtc1/sc22/wg21/docs/papers/2018/p0907r0.html][should work everywhere in practice]].
- In some languages, including C++, =a%2= computes [[https://en.wikipedia.org/wiki/Modular_arithmetic#Remainders][remainder]], not modulo. When =a= is -1, I want to say that's odd, so I want =a%2= to be 1, but some systems will return -1. If your language computes modulo, you can safely use =a%2=.
- If you know that your coordinate =a= will never be negative, you can safely use =a%2=.
- If you don't have =a&1= available, you can use =abs(a) % 2= instead.

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

* Notes
:PROPERTIES:
:CUSTOM_ID: notes
:END:

- In languages that don't support =a>>1=, you can use =floor(a/2)= instead.
- Most of the functions are small and should be inlined in languages that support it.
- Operator overloading is sometimes abused, but might be nice for the arithmetic Hex operations =hex_add=, =hex_subtract=, =hex_scale=. I didn't use it here.
- I wrote this code in module style, but you might prefer to write it as class style, where the functions are static or class methods. In some languages, class style is the only choice. Some of the methods might be better as instance methods.
- In languages that support more than one constructor, or optional arguments, it might be handy to have both the two-argument axial constructor and the three-argument cube constructor.

** Cube vs Axial
:PROPERTIES:
:CUSTOM_ID: cube-vs-axial
:END:

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 [[http://web.cs.ucla.edu/~tianyi.zhang/perfdiff.pdf][this paper]] 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/.

** C++
:PROPERTIES:
:CUSTOM_ID: cpp
:END:

- These are all value types, cheap to copy and pass around. For a bit more compactness, if your maps are small you can use an int16 or int8 for the Hex and Offset class. If you're computing =s= in an accessor, storing =q= and =r= (or =col= and =row=) as int16 will let you fit the entire coordinate into 32 bits.
- As written, these classes have a non-default constructor, so they won't count as a POD trivial type, although I think they count as a POD standard-layout type. Switch to a default constructor and use struct initialization if you'd like them to be a POD trivial type.
- I could have written a template class =Hex<>= and instantiated it as =Hex<int>= and =Hex<double>=. I decided not to because I expect that many of the readers will be translating the code to another language.

** Python, Javascript
:PROPERTIES:
:CUSTOM_ID: dynamic-typing
:END:

- Python and other dynamically typed languages don't need Hex and FractionalHex to be separate. You can write the FractionalHex functions to work with Hex instead, and skip the FractionalHex class.

* Source Code
:PROPERTIES:
:CUSTOM_ID: code
:END:

** Code from this page
:PROPERTIES:
:CUSTOM_ID: codegen
:END:

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:

- [[./codegen/output/lib.cpp][C++]]
- [[./codegen/output/lib.py][Python]]
- [[./codegen/output/lib.cs][C#]]
- [[./codegen/output/Tests.hx][Haxe]]
- [[./codegen/output/Tests.java][Java]]
- Javascript [[./codegen/output/lib-functions.js][top-level functions]] or [[./codegen/output/lib.js][with classes]] or [[./codegen/output/lib-module.js][with es6 modules]]
- [[./codegen/output/lib.ts][Typescript]]
- [[./codegen/output/lib.lua][Lua]] 5.2; see [[./codegen/OutputLua.hx][source]] for notes about 5.1 and 5.3
- [[./codegen/output/lib.rs][Rust]] ; not entirely idiomatic Rust

Caveat: this is /procedurally generated code/ ([[https://simblob.blogspot.com/2015/03/hex-grids-code-generation.html][yes, really!]]) and doesn't follow the best style and idiom recommendations for each language. It'd be cool to add C, Objective C, 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/codegen.zip][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.

** Other libraries
:PROPERTIES:
:CUSTOM_ID: third-party
:END:

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

#+macro: section @@html:<a href="#$1">#</a> <span id="$1">$2</span>@@

- {{{section(third-party-csharp,Unity and C#)}}}
  - [[http://gamelogic.co.za/grids/][GameLogic Grids]] - Unity - includes hexagons but also many other grid types
  - [[https://www.boristhebrave.com/docs/sylves/1/articles/grids/][Sylves]] - C# - includes hexagons but also many other grid types
  - [[https://github.com/pgeerkens/HexGridUtilitiesForGames][Hex-Grid Utilities]] - C# - includes field of view, pathfinding, WinForms
  - [[https://github.com/akhra/HexCoord][akhra/HexCoord]] - C# / Unity
  - [[https://github.com/DigitalMachinist/HexGrid][DigitalMachinist/HexGrid]] - C#
  - [[https://github.com/Amaranthos/UnityHexGrid/][Amaranthos/UnityHexGrid]] - C# / Unity
  - [[https://github.com/svejdo1/HexGrid][svejdo1/HexGrid]] - C#
  - [[https://github.com/Banbury/UnityHexGrid][Banbury/UnityHexGrid]] - C# / Unity
  - [[https://aurelwu.github.io/][aurelwu.github.io]] - Unity
  - [[https://github.com/owenmoore/cube-coordinates][owenmoore/unity-hexagonal-grids]] - Unity
  - [[https://github.com/imurashka/HexagonalLib][imurashka/HexagonalLib]] - C# / .NET
  - [[https://github.com/Clpsplug/hexagonal_map][Clpsplug/hexagonal_map]] - C# - cube/axial coordinates
  - [[https://github.com/juna8001/HexEngine][juna8001/HexEngine]] - C# / Unity
- {{{section(third-party-java,Java and JVM)}}}
  - [[https://github.com/Hexworks/mixite][Hexworks/mixite]] - Java
  - [[https://github.com/timgilbert/scala-hexmap][timgilbert/scala-hexmap]] - Scala
  - [[https://github.com/mraad/grid-hex][mraad/grid-hex]] - Scala
  - [[https://github.com/dmccabe/khexgrid][dmccabe/khexgrid]] - Kotlin
  - [[https://github.com/OfflineBrain/khexagon][OfflineBrain/khexagon]] - Kotlin
- {{{section(third-party-objc,Objective C)}}}
  - [[https://github.com/denizztret/ObjectiveHexagon][denizztret/ObjectiveHexagon]] - Objective C
  - [[https://github.com/pkclsoft/HexLib][pkclsoft/HexLib]] - Objective C
  - [[https://github.com/denizztret/ObjectiveHexagon][denizztret/ObjectiveHexagon]] - Objective C
- {{{section(third-party-swift,Swift)}}}
  - [[https://github.com/MadGeorge/AmitsHexGridLibrarySwift][MadGeorge/AmitsHexGridLibrarySwift]] - Swift
  - [[https://github.com/fananek/hex-grid][fananek/hex-grid]] - Swift
- {{{section(third-party-js,JavaScript and TypeScript)}}}
  - [[https://github.com/flauwekeul/honeycomb][flauwekeul/honeycomb]] - JavaScript + TypeScript
  - [[https://github.com/mpalmerlee/HexagonTools][mpalmerlee/HexagonTools]] - JavaScript + Canvas
  - [[https://github.com/RobertBrewitz/axial-hexagonal-grid][RobertBrewitz/axial-hexagonal-grid]] - JavaScript
  - [[https://github.com/bodinaren/BHex.js][bodinaren/BHex.js]] - JavaScript
  - [[https://github.com/Hellenic/react-hexgrid/][Hellenic/react-hexgrid]] - JavaScript / React
  - [[https://github.com/vonWolfehaus/von-grid/][vonWolfehaus/von-grid]] - JavaScript / Three.js
  - [[https://github.com/othree/hexagons][othree/hexagons]] - JavaScript - odd-r coordinates
  - [[https://github.com/cefleet/hexAPI][cefleet/hexAPI]] - JavaScript
  - [[https://github.com/njlr/solid-hex][njlr/solid-hex]] - JavaScript + pipeline operator
  - [[https://github.com/aahdee/p5grid][aahdee/p5grid]] - JavaScript / P5.js
  - [[https://github.com/joshuabowers/hexagonally][joshuabowers/hexagonally]] - TypeScript
  - [[https://github.com/scrapcupcake/hexs6][scrapcupcake/hexs6]] - JavaScript
  - [[https://github.com/euoia/hex-grid.js][euoia/hex-grid.js]] - JavaScript
- {{{section(third-party-python,Python)}}}
  - [[https://github.com/RedFT/Hexy][RedFT/Hexy]] - Python
  - [[https://github.com/stephanh42/hexutil][stephanh42/hexutil]] - Python - doubled coordinates
  - [[https://github.com/BorisTheBrave/grids][BorisTheBrave/grids]] - Python - hexagon, square, and triangle grids
  - [[https://github.com/kompoth/geks][kompoth/geks]] - Python - with map generation, pathfinding
- {{{section(third-party-ruby,Ruby)}}}
  - [[https://github.com/czuger/rhex][czuger/rhex]] - Ruby
  - [[https://github.com/SpeciesFileGroup/waxy][SpeciesFileGroup/waxy]] - Ruby
- {{{section(third-party-elm,Elm)}}}
  - [[https://package.elm-lang.org/packages/Voronchuk/hexagons/2.0.0][Voronchuck/hexagons]] - Elm
  - [[https://github.com/danneu/elm-hex-grid][danneu/elm-hex-grid]] - Elm
  - [[https://github.com/etaque/elm-hexagons][etague/elm-hexagons]] - Elm
- {{{section(third-party-rust,Rust)}}}
  - [[https://github.com/alkavan/hexagon-tiles][alkavan/hexagon-tiles]] - Rust
  - [[https://github.com/dpc/hex2d-rs][dpc/hex2d-rs]] - Rust
  - [[https://github.com/leftiness/hex_math][leftiness/hex_math]] - Rust
  - [[https://github.com/ozkriff/zemeroth][ozkriff/zemeroth]] - game written in Rust; hex code not separated out into its own library
  - [[https://github.com/iancormac84/hexae][iancormac84/hexae]] - Rust
  - [[https://gitlab.com/hankruiger/bestagon][hankruiger/bestagon]] - Rust
  - [[https://github.com/cmarcbs7/chickenwire][cmarcbs7/chickenwire]] - Rust
  - [[https://github.com/ManevilleF/hexx][ManevilleF/hexx]] - Rust
- {{{section(third-party-lua,Lua)}}}
  - [[https://github.com/icrawler/HexaMoon][icrawler/Hexamoon]] - Lua
- {{{section(third-party-godot,GDScript and Godot)}}}
  - [[https://github.com/droxpopuli/HexMap][droxpopuli/HexMap]] - GDscript / Godot
  - [[https://github.com/DDoop/HexTesting][DDoop/HexTesting]] - GDscript / Godot#
  - [[https://github.com/romlok/godot-gdhexgrid][romlock/godot-gdhexgrid]] - GDscript / Godot 3
  - [[https://github.com/HugoEnzo/HexGrid_Godot_4.0][HugoEnzo/HexGrid]] - GDscript / Godot 4
- {{{section(third-party-php,PHP)}}}
  - [[https://github.com/nanosch/hexopia][nanosch/hexopia]] - PHP
  - [[https://github.com/Astatroth/php-hexgrid][Astatroth/php-hexgrid]] - PHP
- {{{section(third-party-other,Other languages)}}}
  - [[https://github.com/mhwombat/grid/wiki][mhwombat/grid]] - Haskell - includes square, triangle, hexagonal, octagonal grids
  - [[https://github.com/RyanMcNamara86/Hex][RyanMcNamara86/Hex]] - Haskell
  - [[https://github.com/andeemarks/clj-hex-grid][andeemarks/clj-hex-grid]] - Clojure
  - [[https://github.com/rayalex/hexgrid][rayalex/hexgrid]] - Elixir
  - [[https://gist.github.com/zacharycarter/c5565930ba57af5554bb8180d566f067][zacharycarter's gist]] - Nim
  - [[https://github.com/pmcxs/hexgrid][pmcxs/hexgrid]] - Go
  - [[https://github.com/hautenessa/hexagolang][hautenessa/hexagolang]] - Go
  - [[https://github.com/GiovineItalia/Hexagons.jl][GiovineItalia/Hexagons.jl]] - Julia
  - [[https://pub.dev/packages/hexagonal_grid][hexagonal_grid]] - Dart / Flutter

Also for Unity take a look at [[https://catlikecoding.com/unity/tutorials/hex-map/part-1/][CatlikeCoding's tutorial]].

#+begin_comment
  - [[https://github.com/bokeh/bokeh/blob/master/bokeh/util/hex.py][Bokeh library]] - Python hexbinning (docs http://bokeh.pydata.org/en/latest/docs/user_guide/plotting.html)
  - https://github.com/karliss/vsvg/blob/master/crates/whiskers/src/grid_helpers/hex_grid/mod.rs - Rust plotter generative art library uses doubled coordinates
#+end_comment

#+begin_export html
<x:footer>
  <script src="codegen/output/lib.js"/>
  <script src="implementation.js"/>
</x:footer>
#+end_export

#+begin_footer
Created {{{date(%e %b %Y)}}} with [[https://orgmode.org/][Emacs Org-mode]], from [[./implementation.org][implementation.org]] and the helper Javascript file [[./implementation.js][implementation.js]]. Last modified: {{{modification-time(%e %b %Y)}}}
#+end_footer