六角网格的实现

引言

Amit 潜心研究六角网格系统多年，本文是其系列教程中的一篇，探讨了具体如何实现六角网格系统。
文本需要参考作者的另外一篇文章《六角网格大观》(indienova译文版)来阅读。本文原文见这里。

概述

我在《网格沉思》与《六角网格大观》等文章中描述了实现六角网格系统的数学基础与算法，这里就让我们基于它们实现一个可用的六角网格系统库文件。我们首先需要考虑的是这个库需要哪些核心内容：

由于许多算法都基于立方坐标，因此我需要为其建立一个数据结构，这样就能以它为基础实现这些算法。我将这个类命名为 Hex。
某些游戏需要向玩家显示坐标，但并非显示立方坐标，而是轴坐标或偏移坐标，因此我们还需要为玩家可见的坐标系统建立一个数据结构，并且编写用于在两种坐标间相互转换的函数。立方坐标与轴坐标本质上没有区别，因此我不会为其单独建立新的坐标系统，还是继续使用 Hex 类。但我会为偏移坐标建立单独的数据结构 Offest。
网格地图中还需要存储一些额外的信息，诸如地形，对象，单元等等。用2维数列是可行之策，但有时这样会稍显不直观，因此我创建了 Map 类专门负责此项任务。
为了向屏幕绘制六边形，我需要将网格坐标转换为屏幕坐标的方法。为此需要创建 Layout 类。在六角网格大观中没有涵盖某些内容：
- 既支持 y 轴朝上的坐标系(在 3d 库中很常见)也支持 y 轴朝下的坐标系(在 2d 库中很常见)，在六角网格大观中我只讨论了 y 轴朝下的情况。
- 支持拉伸或收缩后的六边形，这在使用像素图形时尤为常见。在六角网格大观中我只讨论了正六边形的情况。
- 支持将 0,0 六角网格放置在屏幕的任意位置。在六角网格大观一文中，我只讨论了将 0,0 六角网格放置在 0,0 位置。
此外，我还需要实现将鼠标点击位置和其他像素坐标转换为六角网格坐标的方法。我会将这块功能放入 Layout 类中。六角网格坐标与屏幕坐标的相互转换有相似之处，因此将它们放到一起很合理。
《六角网格大观》中没有讨论整点六角坐标与浮点数六角网格坐标之间的区别。在需要用到浮点数坐标的地方，我会专门定义 FractionalHex 来实现线性插值与圆整的算法。
一旦创建好坐标系并实现求相邻网格的方法，就可以运用基于图论的算法来求解移动范围，寻路搜寻等诸多问题。寻路算法我已经在另外一篇教程中详细讨论过了，这里就不再重复。

我打算主要使用 C++ 来编写范例代码，但我也为这份代码编写了 Java，C#，Python，JavaScript，Haxe 和 Lua 的版本。

六角网格坐标

在《六角网格大观》一文中我将立方坐标与轴坐标视为两种不同的坐标系。立方坐标实则是 x, y, z 三维空间中的一个面 x + y + z = 0。轴坐标只有两个轴，轴间夹角为 60° 或 120°。我这里使用了以 q, r, s 而非 x, y, z 来命名坐标的立方类：

struct Hex { // 存储立方坐标，立方坐标构造函数
    const int q, r, s;
    Hex(int q_, int r_, int s_): q(q_), r(r_), s(s_) {
        assert (q + r + s == 0);
    }
};

简洁明了。下面这个类内部也存储了轴坐标，但使用立方坐标作为接口：

struct Hex { // 存储轴坐标，立方坐标构造函数
    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_; }
};

这两种写法效果一致。头一种显式地写出了 s 坐标，第二种则使用寄存器，在需要的时候再计算具体的 s。立方坐标与轴坐标本质上是一种坐标系，因此我不会为其单独编写独立的类。

另一种风格是将 s 放入构造函数而非将其作为参数传递：

struct Hex { // 存储立方坐标，轴坐标构造函数
    const int q, r, s;
    Hex(int q_, int r_): q(q_), r(r_), s(-q_ - r_) {}
};

这种写法的优势在于你需要用到 s 的时候多半是在调用的时候。你拥有 q 和 r，虽然没有 s，但是将 -q-r 作为第三个参数就可以了。你还可以将这种风格与第二种写法(存储轴坐标)相融合，只存储 q 与 r，并使用寄存器来计算 s。

还有一种风格是，使用数组而非命名字段：

struct Hex { // 存储矢量，立方坐标构造函数
    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]; }
};

这种写法的好处，就像你一开始就看到的，在于它平等看待三个坐标值 q, r, s。你可以编写循环来处理它们而无须复制代码。如果使用 CPU 运算你应该使用 SIMD(单指令多数据流) 指令，使用 GPU 运算则应该使用 vec3。如果你已经读过后文中的相等判断以及 hex_add， hex_subtract， hex_scale，hex_length，hex_round 以及 hex_lerp 等函数，你应该能感觉到统一对待三个坐标用途有多么巨大。当使用这种表达方式时，如果你读过后文的 hex_to_pixel 和 pixel_code，你会发现可以直接使用六角坐标来进行矢量与矩阵运算(无论是使用 CPU 还是 GPU)。

编程是一项充满权衡的活动。就本文而言，我首先关注的方面是简洁性和可读性，并不刻意注重性能或者抽象层次的问题，因此我选择使用第一种风格：储存立方坐标，使用立方坐标构造函数。这样最易于阐述算法。然而，以上提到这些风格我都很喜欢，如果适合项目我会毫不犹豫地选择它们。在一些具有多重构造函数的语言中，出于方便，我会同时使用轴坐标与立方坐标的构造函数。在 C++ 中，我会使用模板参数来替代 int 类型，而在 C 或 C++11 中，可以使用 union 将 int v[] 和 int q, r, s 两种风格融为一体。模板参数 w 可以用于区分位置与矢量。将它们结合在一起，代码如下：

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;

在这篇教程中，我没有选择 C++ 特有的编程风格，因为我希望本文的代码能更直接地翻译成其他语言。

相等判断

判断是否相等是非常直观的问题：坐标相等即说明是同一个六边形。在 C++ 中，使用 == 操作符；在 Python 中，使用方法 __eq__;在 Java 中，专门定义一个 equals() 方法。尽可能贴合语言本身的编程风格：

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

坐标运算

由于立方坐标来自3维笛卡尔坐标系，因此它们也可以进行一般的加减乘除运算。举例来讲，Hex(2, 0, -2) 代表指向东北长度为2的矢量，因此从位置 Hex(3, -5, 2) 向东北移动2格的方法也十分明显： Hex(2 + 3, 0 + -5, -2 + -2)。在其他的坐标系，比如偏移坐标系中，这种写法是行不通的。只有当你实现了三维笛卡尔坐标系时才能进行这些运算，但我这里选择用 q, r, s 来命名，没有使用传统的命名方法 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);
}

距离

两个六边形的距离即两者连线的长度。不管是求距离还是求连线长度，运算起来都不麻烦。参见《六角网格大观》一文：

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

相邻

计算距离时，我定义了两个函数：一个参数的 length 和两个参数的 distance。对相邻问题处理方式也很类似。direction 函数有一个参数，而 neighbor 函数有两个参数。参看六角网格大观：

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

假如超出默认的六个方向范围，就使用 hex_directions[(6 + (direction % 6)) % 6]。嗯，看起来是有点丑，但它即使对反方向也适用。(附记：如果 C++ 能有可以处理负数的取模运算符那该多好啊。参见 stackoverflow 的一篇讨论。)

布局

接着我们来实现在六角坐标与屏幕坐标间相互转换的功能。布局方案分顶点朝上和边线朝上。我们会用到转换矩阵以及它的逆矩阵，因此需要有存储矩阵的方案。在绘制顶点时，顶点朝上布局起始角度为 30° 而边线朝上则从 0° 开始，因此也需要存放布局信息。

我定义了一个辅助类 Orientation 来存储这些数据:
2x2 的转换矩阵，2x2 的逆矩阵，以及起始角度。

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

由于仅有两种朝向，因此我使用常量：

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

将它们用于 Layout 类：

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

哦，对了，我还需要定义个极简的 Point 类。如果你使用的图形库/几何库中以及提供了这个类，就用它们提供的就好：

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

附记：你可能已经注意到了，这里的许多东西其底层都是元素为数字的数组。Hex 是 int[3]。朝向是一个角度，用双精度浮点数 double 表示，而两个矩阵，都是 double[4] 或 double[2][2]。点 Point 是 double[2]。布局由一个朝向 Orientation 和两个点 Point 组成。后文中将会用到的 FractionalHex 是 double[3]，而 OffsetCoord 是 int[2]。我选择使用结构体，而没有使用数组，是因为我可以为结构体的元素命名，而这些名字能够帮助我理解它们，同时对类型检查也有好处。

一切就绪，我们来编写布局的算法吧。

六角网格到屏幕

《六角网格大观》一文中包括两种六角网格坐标转换为像素坐标的方法，每一种适应一种朝向。尽管数值有所不同，但本质上代码是一样的。因此，在实现该功能时，我将具体的数值放入了 Orientation 类中，从 f0 到 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);
}

和《六角网格大观》一文有所不同的是，我分别声明了两个方向的大小：x 与 y。这样就能实现：

你可以拉伸，收缩六边形来适配你使用的任意大小的像素材质。请注意 size.x 与 size.y 并非六边形的宽度和高度。
你可以令 y 变为负数来反转 y 轴方向。

此外，《六角网格大观》一文中将 q = 0, r = 0 的六边形面心放置在 x = 0,y = 0 位置，但起始基本上你想放到什么位置都无关紧要。如果想要其他的位置，只需要往中心位置(layout.origin)增加一个变化量就好。

屏幕到六角网格

《六角网格大观》一文也包含两种将像素坐标转换为六角网格坐标的方案，每一种适用于一种朝向。同样地，虽然数值不同，但代码没有本质差别。这次我们使用的是逆矩阵，我将矩阵求逆放入了 Orientation 中，从 b0 到 b3，并用在下面的函数中。在六角网格到屏幕坐标的转换中，我先乘以矩阵，再乘以大小，然后加上原点。而从屏幕坐标转换到六角网格，我需要逆转这个过程：首先减去原点，然后除以大小，再乘以逆矩阵：

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

此处可能会出现一点稍微麻烦的情况：我将整型的六角网格坐标转换为屏幕坐标，但反过来，却无法保证屏幕坐标转换后的六角网格坐标恰好为整数。这样我得到的不是整型的坐标，而是双精度浮点类型的坐标，转换函数的返回值为 FractionalHex 而非 Hex。为了得到整型坐标，还需要经过一次圆整，稍后我会实现这一功能。

绘制六角网格

绘制六边形需要清楚它的顶角相对于中心的位置关系。使用边线朝上布局时，顶角位于 0°，60°，120°，180°，240°，300°；使用顶点朝上布局时，顶角位于 30°, 90°, 150°, 210°, 270°, 330°。我在 Orientation 类中编码了起始角度 start_angle 的值，为 0° 时是 0.0，为 60° 时是 0.5。

当我知道顶角相对中心的位置关系后，就能够通过从中心位置移动相对距离来找到顶角的屏幕位置，并将坐标放入数组之中：

Point hex_corner_offset(Layout layout, int corner) {
    Point size = layout.size;
    double angle = 2.0 * M_PI *
             (corner + layout.orientation.start_angle) / 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;
}

布局范例

好的，下面我们来试试看。我们已经编写好了 Hex， Orientation，Layout，Point 以及他们间互相转换的函数。这样就足够绘制六边形了。我决定用 JavaScript 版本的代码在浏览器中绘制一些六边形。

我们先来尝试这两种布局：layout_pointy 和 layout_flat:

接着我们来试试大小的网格：分别为 Point(10, 10)，Point(20, 20) 以及 Point(40, 40):

我们试试拉伸和收缩六边形，将大小设置为 Point(15, 25) 和 Point(25, 15):

让我们试着将 y 轴朝下设置 Point(25, 25) 再反转 y 轴设置 Point(25, -25)。我们仔细来看一看方向反转前后 r 是如何增长的：

我认为这是一组很合理的朝向大小测试，它展现出 Layout 类能够处理广泛类型的需求，甚至无需编写其他类型的 Hex 类。

浮点数六角网格

从像素转换为六角坐标我们会用到浮点六角坐标。看起来很像 Hex 类，但使用 double 而非 int:

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

六角网格坐标圆整

将浮点六角坐标圆整到最近的整型六角坐标。六角网格大观一文中的算法十分直观：

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

线条绘制

我们通过线性插值在两个六边形间绘制连线，再将其圆整到最近的六边形上。线性插值的实现非常简单：

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

当线性插值实现后，连线的实现就非常容易了：

vector hex_linedraw(Hex a, Hex b) {
    int N = hex_distance(a, b);
    vector 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;
}

max(N, 1) 这一段代码是用来处理 A == B 长度为 0 的情况。

地图

有两个相关的问题需要解决：如何生成六边形形状以及如何存储地图数据。让我先从地图数据存储开始：

地图存储

存储地图最简单的办法是使用哈希表。在 C++ 中，为了使用 unordered_map 或者 unordered_set 我们需要为 Hex 定义哈希函数。如果 C++ 让定义它的过程简单点就好了，不过现在这样倒也还不坏。我将求出 q 和 r 字段的哈希值(这里我就略去冗余的步骤)，并使用 Boost 提供的 hash_combine 算法将其联合起来：

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

下面的例子演示了如何为每个六边形制作浮点数高度的地图：

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

哈希表本身不是很有用，我需要将其与其他数据联合起来创建地图形状。用图论术语来讲，我需要一些数据来创建节点。

地图形状

在这个章节中我会写一些循环来产生许多形状的地图。你可以利用这些循环来为你的地图生成一系列六角坐标。我编写了填充这些六角坐标的样例代码。

平行四边形

如果使用是是轴坐标/立方坐标，下面这个直观的循环代码就能产生出平行四边形的地图而不是常见的四边形地图：

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

有三个坐标，循环要求你选出其中两个： (q, r), (s, q) 或者 (r, s)。

分别产生顶点朝上布局地图为：

边线朝上布局地图为：

三角形

三角形有两种朝向，在代码中需要考虑你具体选择哪种朝向。假定 y 轴方向朝下，当使用顶点朝上布局时，这些三角形将面朝南边/西北/东北：

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

而在边线朝上布局中，这些三角形面朝东边/西北/西南：

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

如果反转 y 轴方向，只需在代码中调换南北方向即可。

六边形

六角网格大观中我演示了如何生成六边形的地图：

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

下面分别是顶点朝上布局和边线朝上布局的地图：

矩形

在轴坐标/立方坐标中，生成四边形的地图略微有些棘手。六角网格大观中给了立方坐标生成六边形地图的一个方案，但是我当时并没有给出具体的代码，这里我将它写出来，如下所示：

unordered_set map;
for (int r = 0; r < map_height; r++) {
    int r_offset = floor(r/2); // or r>>1
    for (int q = -r_offset; q < map_width - r_offset; q++) {
        map.insert(Hex(q, r, -q-r));
    }
}

和前面一样，我会从 q, r, s 中选出两个用于循环，但这一次顺序至关重要，因为外层与内层的循环是有所区别的。下面是使用顶点朝上布局，将 (outer, inner) 循环设置为 (r, q), (q, s), (s, r), (q, r), (s, q), (r, s) 时生成的地图：

他们的确都是四边形，但他们不用都得与 x， y 轴方向对齐！你们大多数人可能会希望得到第一种地图，也就是 r 作为外层循环参数而 q 作为内层循环参数。

那么使用边线朝上布局时又怎么样呢？当 (outer, inner) 循环参数分别为 (r, q), (q, s), (s, r), (q, r), (s, q), (r, s) 时地图如下所示：

为了得到第四种地图，你可以使用 q 作为外层循环参数， 作为内层循环参数 然后调换宽高：

unordered_set map;
for (int q = 0; q < map_width; q++) {
    int q_offset = floor(q/2); // or q>>1
    for (int r = -q_offset; r < map_height - q_offset; r++) {
        map.insert(Hex(q, r, -q-r));
    }
}

这两种版本的代码会产生本质上相同，但细节处稍有区别的形状。你可能需要多做一些实验才能得到精确满足你需求的地图形状。例如，你可以试着将偏移设为 floor((q+1)/2) 或者 floor((q-1)/2) 而非 floor(q/2)，以观察地图边界如何发生轻微的变化。

优化存储

哈希表是一个相当通用的解决方案，并且适用于任何一种地图形状，甚至适用于一些奇形怪状，中间带空洞的地图形状。你可以将其作为一个节点-边类型的图来查看它，使用 hex_neighbor 来存储节点，并且显式地临时计算节点之间的边。

还有一种方法也可以用于存储节点-边类型的图结构，预先计算所有的边并且显式地存储它们。每一个节点都有一个整型 id，并且我们会使用数组的数组来存储接壤的节点。或者每一个节点都是一个对象，我们使用它的一个字段来储存相邻节点的列表。这种图的拓扑结构也具有通用性，可以适用于任何形状的地图。你也可以对其使用各种基于图论的算法，可以用来求解移动范围，地图距离或者路径搜寻等诸多问题。如果地图形状规则或者经常会被编辑修改，那么隐式地存储边的数据也不会有什么问题；如果地图形状不规则(有界，有墙壁，有空洞等等)而且不会经常变动，那么还是显式储存边的数据为好。

某些地图形状也可以使用紧凑的2维数组或者1维数组来存储。六角大观中为此给出了可视化的演示。这里，我再给出一个代码范例。主要的思想是无论对哪种地图形状来说，代码中都会包含嵌套的循环：

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

如果要紧凑地存储地图数据，我会使用数组的数组，并且使用形如 array[a-a1][b-b1] 的索引。例如，下面是四边形的代码：

for (int r = 0; r < height; r++) {
    int r_offset = floor(r/2);
    for (int q = -r_offset; q < width - r_offset; q++) {
        map.insert(Hex(q, r, -q-r));
    }
}

变量 a 表示 r，而变量 b 为 q。数值 a1 为 0 而 b1 为 -floor(r/2)，即 array[r-0][q-(-floor(r/2))] ，因此可以被简化成 array[r][q+floor(r/2)]。注意 floor(r/2) 中 r >> 1。

此外，我还需要知道数组的大小 size。我需要 a2-a1 个数组，而每个数组的大小应该是 b2-b1。(务必小心检查偏移1的错误:如果循环之中 a <= a2 你会需要 a2-a1+1 个数组，类似还有 b <= b2 的情况。)我可以使用 C++ 矢量模板来建立这些数组：

vector> map(height);
for (int r = 0; r < height; r++) {
    map.emplace_back(width);
}

我可以将它们封装到 Map 类中：

template class RectangularPointyTopMap {
    vector> map;

  public:
    Map(int width, int height): map(height) {
        for (int r = 0; r < height; r++) {
            map.emplace_back(width);
        }
    }

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

如果是其他类型的地图形状，可能会略微复杂一些，但还是遵循相同的模式：为了确定地图的大小，解决数组访问的问题，我必须研究创建地图的循环代码。

如果使用1维数组会显得棘手一些，因此我这里就不展开说了。我自己的多数项目中会使用基于图论的表示方法，它具有最大的灵活性和可重用性。当存储空间比较紧要的时候我只需要考虑使用更加紧凑的地图存储格式就好了。

偏移坐标

在六角网格大观一文中我使用 q 和 r 来存放偏移坐标，但由于我也将其用于立方坐标系和轴坐标系中，所以这里我就改用 col 与 row:

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

我希望能把立方坐标系与轴坐标系使用的 Hex 类用于除了玩家看到的显示位置(那里还是偏移坐标更有用武之地)之外的所有地方。这也就是说，我需要编写 Hex 与 OffsetCoord 之间相互转换的代码。

有四种偏移坐标系类型：奇行，偶行，奇列，偶列。行类型使用顶点朝上布局，而列类型使用边线朝上布局。偶类型偏移为 +1，而奇类型偏移为 -1:

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

OffsetCoord qoffset_from_cube(int offset, Hex h) {
    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) {
    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) {
    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) {
    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);
}

如果你仅使用奇偶两种类型中的一种，可以将偏移量硬编码到代码之中，这样可以让代码更为简单快速。抑或你可以将偏移量 offset 作为模板参数，这样可以让编译器内联它从而优化代码。

使用偏移坐标系时我需要知道行列数的奇偶性，我们使用 a&1 而不用 a%2 来返回 0 或者 +1，为什么呢？

如果是使用补码的系统(几乎囊括目前大多数的系统)，当 a 为偶数时 a&1 会返回 0，为奇数时会返回 1。这正是我想要的结果。虽然严格来说，它也并非是完全可移植的。
在某些语言中，包括 C++ 在内，a%2 计算的是余数而非模数。如果 a 为 -1，我们知道这是一个奇数，我们希望 a%2 返回 1，然而一些系统却会返回 -1。如果你使用的语言可以计算模数，那就放心大胆使用 a%2 就好。
如果你使用的坐标数值永远都不可能为负数，用 a%2 也不会出什么问题。
如果你使用的语言里没有 a&1 可用，可以用 abs(a) % 2作为替代。

此外，在很多(或者说所有？)语言中，& 的优先级都比 + 低，所以最好在 a&1 外加上圆括号。

附记

立方坐标 VS 轴坐标

立方网格坐标包含三个数字，但其中一个在约束条件下可以通过另外两个求出。选择将其存放进第三个字段或者选择在访问函数计算它基本上只是代码风格的区别。如果非常关注性能问题，就有必须仔细考虑到底是使用寄存器还是临时计算结果节约开销了。在 C++ 这样的语言中，只要能使用寄存器和内联方法，就应该尽可能使用它，以节约内存(毕竟访问 RAM 的开销十分昂贵)。在有些语言中，例如 Python，使用寄存器的性能开销也不小，这时候我们应该减少函数的调用(函数调用开销并不小)，并且在字段中存储第三个坐标。

另外有兴趣的读者也可以查阅这篇论文，它提到使用轴坐标和立方坐标相比使用偏移坐标，会在视线，距离等算法的计算中更快一筹，但在用作显示时会更慢一些(正和我们预料的一样)。但我没能找到他们测试用的代码。

如果性能真的很重要，最佳做法是实际去测试具体的数据。

C++

C++ 具有各种数值类型，复制和传递它们的开销都很小。为了让代码更紧凑，如果你的地图不大，可以考虑在 Hex 或者 Offset 中使用 int16 或者 int8 的整型。假如你使用寄存器来计算 s，并使用 int16 来保存 q 和 r(或是 col 和 row)，那么整个坐标恰好用掉一个32位的字长。

。

正如前文所述，这些类没有默认为空的构造函数，因此它们不会被看作是普通的 POD 对象类型，尽管我觉得把它们当成 POD 对象也没什么关系。如果你更习惯 POD 对象那么就改用默认的构造函数并进行结构体初始化。
我本来可以写一个模板类 Hex<>，实例化就能得到 Hex 与 Hex。考虑到许多读者可能愿意将代码翻译成其他语言的版本，最后我放弃了这种想法。