六角网格大观

作者:indienova
2016-05-06
88 150 22

引言

电子游戏中六角网格的运用没有方形网格那样常见,也确实有些不够直观,因此,一直以来,这方面的资料也相对较为匮乏。来自斯坦福大学的 Amit Patel 搜罗相关资料的工作已断断续续进行了二十余年。他将多年的宝贵经验融为这篇教程,为大家提供一个用最简洁的代码来实现六角网格的优雅方案。教程参考了 Charles Fu 与 Clark Verbrugge 的一些文章,整理和讲解了如何制作六角网格,六角网格之间的关系,相关的算法等问题,尤为贴心和难得的是,这篇教程中的许多部分都是可以交互的。文中代码样例使用伪码写成,这样读者可以方便地用他们擅长与熟悉的语言来实现属于他们自己的六角网格系统。

几何学

六边形,顾名思义,就是有六个边的多边形。 六边形的六个边长度相同。我们在本文中讨论的六角网格使用的都是正六边形。六角网格最典型的朝向则有两种:水平方向( )与竖直方形( )。

六角网格系统中的每两个六边形共用一条边,每三个六边形共用一个角。关于中心,边,角关系的知识可以参看我的这篇文章(indienova译文版)

角度

正六边形的内角为120°,内部恰好可以塞下六个内角为60°的等边三角形。边角顶点 i 相对面心的坐标为 (60° * i) + 30°, size。代码如下:

function hex_corner(center, size, i):
    var angle_deg = 60 * i   + 30
    var angle_rad = PI / 180 * angle_deg
    return Point(center.x + size * cos(angle_rad),
                 center.y + size * sin(angle_rad))

依次调用方法 hex_corner(..., 0)hex_corner(..., 5) 就可以得到六边形的顶点坐标,接着绘制顶点之间的连线就能勾勒出六边形的轮廓。

两种朝向的区别在于 x, y 坐标会相互交换,因此,角度也会相应改变: 的角度分别为 0°, 60°, 120°, 180°, 240°, 300° 而 的角度分别为 30°, 90°, 150°, 210°, 270°, 330°。

大小/布局

接下来我们来放置多个六边形。在网格为 水平 朝向时,六边形的 高度高度 = size * 2. 相邻六边形的 竖直 距离则为 竖直 = 高度 * 3/4

六边形的 宽度宽度 = sqrt(3)/2 * 高度。相邻六边形的 水平 距离为 水平 = 宽度

有些以像素风格来表现六边形的游戏无法使用精确的六边形坐标位置,因此也无法套用我在本节提到的角度位置公式。但本文其余部分关于六角网格的算法即使是对变形拉伸后的六边形也适用。

切换为 或切换回

坐标系统

现在,让我们试着将六边形放入网格之中。方形网格的处理方法显而易见,无须多作他想。而六角网格则有许多种办法。我推荐使用立方坐标法为主要表示方法,使用轴坐标或偏移坐标来存储地图,以及作为面向玩家的显示坐标。

偏移坐标

最常见的处理方法是偏移其余的每一行或者每一列。列名为 colq。行名为 rowr。既可以偏移奇数行列,也可以偏移偶数行列,因此对边线朝上和顶点朝上各有两种变化:



奇数行顶点朝上
偶数行顶点朝上
奇数行边线朝上
偶数行边线朝上
立方坐标

我们还可以换一种观察方式,在六角网格中使用三种坐标轴而非在方形网格中使用的两种坐标轴。这种处理方式会呈现出一种十分优雅的对称结构。

让我们先建立一个立方坐标系,并剖开 x + y + z = 0 所在的面。看起来这种想法有点古怪,但这样我们很容易就得到了一个六边形的网格。在实际使用中,我们还是可以使用笛卡尔坐标系中的基本操作,包括坐标标量以及坐标的加减乘除。

注意立方坐标系中的三条坐标轴,观察它们如何与六角网格的六个方向相吻合;而剖面则与六角网格的边相贴合。

由于我们已经有许多可以用来处理方形与立方坐标系的算法,因此如果使用立方坐标系表示六角网格意味着这些算法也能用到六角网格的系统中。本文中的许多算法实现都会基于这套系统。为了将算法用于其他坐标系,需要将其先转换为立方坐标系,执行算法后再转换回原先的坐标系。

请尝试: 或者:

如下面的图表所示,请研究立方坐标是如何应用到六角网格上的。选中的六边线会高亮并显示对应的立方坐标。

  1. 立方网格的每一方向都与六角网格的一条边线方向相重合。试着选中 z 坐标分别为 0, 1, 2, 3 的六角网格,观察它们的关系。相关行会用蓝色标明。类似得,也可以观察 x 轴(绿色)与 y 轴(紫色)。
  2. 六角网格的每一方向都与立方网格的两个轴向的中线方向重合。例如, 六角网格的 西北 方向位于立方网格的 +y 轴与 -z 轴中间,因此,每朝 西北 方向移动一格,对应的立方坐标中,y 方向就会加 1 而 z 方向就会减 1。

切换至 或者切换回

在六角网格系统中使用立方坐标是一种非常合理的选择。我们使用 x + y + z = 0 作为约束条件,在应用这些算法时需要注意这一条件。这一约束也确保了每个六角网格都对应一个笛卡尔三维坐标。

当然,也还有其他可用的立方-六角网格,其中一些约束条件未必是 x + y + z = 0,但本文就使用这一种作为范例。你也可以尝试用 x-y, y-z, z-x 来构造立方坐标系,它的性质十分有趣,我这里就不再作更深入的探讨了。

“可是 Amit 啊!” 你突然说道,“我可不想用三个值来存储坐标系,这样我就不知道怎么储存地图数据了啊。”

轴坐标

轴坐标系,有时也叫做“梯形坐标系”,是从立方坐标系的三个坐标中取两个建立的坐标系。由于我们有约束条件 x + y + z = 0,因此第三个坐标其实是多余的。轴坐标适合用于地图数据储存,也适合用于作为面向玩家的显示坐标。类似立方坐标,你也可以使用笛卡尔坐标系中的加,减,乘,除等基本运算。

有许多种立方坐标系,因此,也自然有许多种由其衍生的轴坐标系。这篇指南中难以一一涵盖各种组合。这里我选出其中两种变化来说明,分别是 q = x 以及 r = z 的情况。这里 q 代表列而 r 表示行。

运用这套系统相比偏移网格的优势在于,算法会更加干净利落;劣势则是这套系统使用的矩形地图会有些古怪;本文的地图存储会谈及具体方法。由于已知约束条件 x + y + z = 0,因此我们还可以让算法显得更干净,我们可以为了应用某些算法先计算出第三个隐藏的坐标。

切换到 或者切换回

偏移坐标是人们最先会想到的坐标系,因为它能够直接使用方形网格的笛卡尔坐标。但不幸的是,偏移坐标系中的一个轴总会显得格格不入,并且最终会把问题变得复杂化。立方坐标和轴坐标则显得相得益彰,算法也更简单明了,只是地图存储方面会略微变得复杂一点。还有一些其他的坐标系方法,比如所谓的交织坐标或者双倍坐标等,我这里就不研究它们了;据说使用立方/轴坐标系是较为简单的。

轴的方向就是坐标值增加的方向,而轴的法线方向是坐标值不变的方向。上面的网格坐标中显示出了法线的方向。

坐标转换

虽然你有可能使用的偏移坐标或者轴坐标,但许多算法在立方坐标中会拥有更为简洁的表达。因此,你需要建立它们之间相互转换的方法。

轴坐标与立方坐标紧密相关,因此转换起来也十分容易:

# 将立方坐标转换为轴坐标
q = x
r = z

# 将轴坐标转换为立方坐标
x = q
z = r
y = -x-z
写成函数的代码则如下:
function cube_to_hex(h): # 轴坐标
    var q = h.x
    var r = h.z
    return Hex(q, r)

function hex_to_cube(h): # 轴坐标
    var x = h.q
    var z = h.r
    var y = -x-z
    return Cube(x, y, z)
偏移坐标的处理会稍微棘手一些:
# 将立方坐标转换为偶数列偏移坐标
col = x
row = z + (x + (x&1)) / 2

# 将偶数列偏移坐标转换为立方坐标
x = col
z = row - (col + (col&1)) / 2
y = -x-z

# 将立方坐标转换为奇数列偏移坐标
col = x
row = z + (x - (x&1)) / 2

# 将奇数列坐标转换为立方坐标
x = col
z = row - (col - (col&1)) / 2
y = -x-z

# 将立方坐标转换为偶数行偏移坐标
col = x + (z + (z&1)) / 2
row = z

# 将偶数行偏移坐标转换为立方坐标
x = col - (row + (row&1)) / 2
z = row
y = -x-z

# 将立方坐标转换为奇数行偏移坐标
col = x + (z - (z&1)) / 2
row = z

# 将偶数行偏移坐标转换为立方坐标
x = col - (row - (row&1)) / 2
z = row
y = -x-z

注意:我这里使用 a&1(位与)而非 a%2 来判断奇偶,这篇笔记给出了具体的原因。

相邻

怎样才能找出与每个六边形相邻的六个六边形呢? 如你所料,在立方坐标中很容易就能确定答案,由其衍生的轴坐标系中这个问题也不麻烦,但偏移坐标中会稍微有点复杂。我们可能也会想要算出六个“对角线”六边形。

立方坐标

六角网格中每挪动一格,相应的,立方网格中三个立方坐标中的某一个就会 +1 而另一个则会 -1 (而其和保持为0)。+ 1 的轴有三种可能出现的情况,剩下的两个轴中为 -1 的可能情况有 2 种,因此一共有六种可能。每种可能恰好对应六边形的一个方向。最简单和快速的解决方法是预先算出结果并在编译阶段就放进表 Cube(dx, dy, dz) 中:

var directions = [
   Cube(+1, -1,  0), Cube(+1,  0, -1), Cube( 0, +1, -1),
   Cube(-1, +1,  0), Cube(-1,  0, +1), Cube( 0, -1, +1)
]

function cube_direction(direction):
    return directions[direction]

function cube_neighbor(hex, direction):
    return cube_add(hex, cube_direction(direction))
轴坐标

正如前文,我们仍以立方坐标作为其他坐标系的基础。我们可以将表 Cube(dx, dy, dz) 转换为表 Hex(dq, dr)

var directions = [
   , , ,
   , , 
]

function hex_direction(direction):
    return directions[direction]

function hex_neighbor(hex, direction):
    var dir = hex_direction(direction)
    return Hex(hex.q + dir.q, hex.r + dir.r)
偏移坐标

偏移坐标中的数值的变化与网格的具体位置有关。是否在偏移过的行列结果会有所不同。

和前面的处理方式类似,我们会建立一个数值表,用来存放 colrow 的改变量。但这次我们使用两个数组,一个用于奇数行,另外一个用于偶数行。观察网格图中的 (1, 1) 并观察你在六个方向移动时发生的变化。再试试从 (2, 2) 出发的情况。对4种偏移的情况表格和代码都有所区别,因此点击对应的网格类型来查看对应的代码吧。

var directions = [
   [ , , ,
     , ,  ],
   [ , , ,
     , ,  ]
]

function offset_neighbor(hex, direction):
    var parity = hex. & 1
    var dir = directions[parity][direction]
    return Hex(hex.col + dir.col, hex.row + dir.row)
选择网格类型:

使用上述查表法是计算相邻格子位置最简单的办法,这里再提供另一种可行之策供好奇的同学研究: 传送门

对角线

移动到对角线位置对立方坐标造成的改变有两种情况,会让立方坐标的三个坐标中的两个出现 ±2 或 ∓1(和保持为0)。

var diagonals = [
   Cube(+2, -1, -1), Cube(+1, +1, -2), Cube(-1, +2, -1),
   Cube(-2, +1, +1), Cube(-1, -1, +2), Cube(+1, -2, +1)
]

function cube_diagonal_neighbor(hex, direction):
    return cube_add(hex, diagonals[direction])

和前面一样,你可以略去其中一个坐标得到轴坐标系,或者通过预先计算找出偏移坐标中的位置。

距离

立方坐标

立方坐标系中,每个立方体中的六边形都处在一个三维的空间中。在六角网格中距离为 1 的相邻六边形在立方网格中距离为 2。这让距离计算变得容易了起来。在方形网格中,曼哈顿距离的值为 abs(dx) + abs(dy)。在立方网格中,曼哈顿距离为 abs(dx) + abs(dy) + abs(dz)。六角网格中的距离取其一半即可:

function cube_distance(a, b):
    return (abs(a.x - b.x) + abs(a.y - b.y) + abs(a.z - b.z)) / 2

另外一种等价的算法是三坐标之一必然是其他两个之和,因此取其作为距离即可。无论是取半还是求最大值的方法都能获得同样的结果:

function cube_distance(a, b):
    return max(abs(a.x - b.x), abs(a.y - b.y), abs(a.z - b.z))

在上图中,最大值会高亮显示。请注意:每一种颜色都标识着六种不同的对角线方向。

轴坐标

轴坐标系中,第三个坐标被隐藏了起来,因此我们先将其转换为立方坐标再计算距离:

function hex_distance(a, b):
    var ac = hex_to_cube(a)
    var bc = hex_to_cube(b)
    return cube_distance(ac, bc)

如果你在编译时内联了 hex_to_cubecube_distance,则会生成如下代码:

function hex_distance(a, b):
    return (abs(a.q - b.q)
          + abs(a.q + a.r - b.q - b.r)
          + abs(a.r - b.r)) / 2

有许多种在轴坐标中计算六角网格距离的方法,但无论应用哪一种方法,都应该记住其本质: 轴坐标中计算六角网格距离都衍生自立方网格中的曼哈顿距离。举例来说,根据这篇文章的结论 ,其中所谓的区别无非是 a.q + a.r - b.q - b.r 写成 a.q - b.q + a.r - b.r,当你认识到它们与立方网格间的联系,会认识到它们本质上都是等价的。

偏移坐标

和处理轴坐标一样,我们会基于立方坐标来处理偏移坐标,然后使用立方坐标的距离:

function offset_distance(a, b):
    var ac = offset_to_cube(a)
    var bc = offset_to_cube(b)
    return cube_distance(ac, bc)
连线

我们如何确定两个六边形之间的连线所在的六边形呢?我会考虑使用线性插值法:均匀地对线条在 N + 1 个点上取样,并找到这些样本点所在的六边形。

  1. 我们先计算端点间的六角网格距离 N。
  2. 然后在端点 AB 间均匀地取 N + 1 个样本点。进行线性插值,第 i 的位置从 0N 应该是依次是 A + (B - A) * 1.0/N * i
  3. 。在图中样本点会是一些浮点数坐标,它们所在的六边形会以蓝色显示。
  4. 将每个样本点(浮点数)转换为六角网格坐标(整型)。算法名为 cube_round

综上所述, AB 之间的连线代码如下:

function cube_lerp(a, b, t):
    return Cube(a.x + (b.x - a.x) * t,
                a.y + (b.y - a.y) * t,
                a.z + (b.z - a.z) * t)

function cube_linedraw(a, b):
    var N = cube_distance(a, b)
    var results = []
    for each 0 ≤ i ≤ N:
        results.append(cube_round(cube_lerp(a, b, 1.0/N * i)))
    return results

一些备注:

  • 应用于方形网格中的差分算法会将 N 作为轴间距离的最大值。立方网格中也能使用这种奇数,而且其值恰好就是六角网格间的距离。
  • 有时候你需要在算得的坐标上做一点微小的改动,比如 Cube(1e-6, 1e-6, -2e-6) 来让结果看起来更加一致。这样会让线不至于刚好落在两个六角网格的分界线上。
  • 函数 cube_lerp 会返回一个立方浮点坐标。如果你使用的是一种强类型的语言,那么不应该使用 Cube 类型而是应该新定义一个 FloatCube,如果不想定义新的类型,你也可以考虑将这个函数定义为内联函数。
  • 通过这些方法可以进一步优化代码:内联 cube_lerp;在循环外就先算出 B.x-A.xB.x-A.y 以及 1.0/N 等数值;乘法可以转换成重复的加法;把一些计算比如差分算法放在最后等等。
  • 我一般使用立方坐标或者轴坐标来确定连线,如果你想要在偏移坐标中干这件事可以参考这篇 文章
  • 连线问题有许多变种。有时你希望尽可能将挨着的六边形包括进去(所谓的 Super Cover)。已经有人给我发过相关的代码但我暂时还没来得及研究。

移动范围

坐标范围

给出六角形面心 center 与范围 N,有哪些六边形在 N 步之内呢?

我们可以先回头看六角网格距离的公式: distance = max(abs(dx), abs(dy), abs(dz))。要找到范围 N 以内的所有六边形,需要满足的条件为 max(abs(dx), abs(dy), abs(dz)) ≤ N。这意味着我们需要分别满足: abs(dx) ≤ Nabs(dy) ≤ N 以及 abs(dz) ≤ N。去掉绝对值符号,即 -N ≤ dx ≤ N-N ≤ dy ≤ N 以及 -N ≤ dz ≤ N。在代码中使用嵌套循环:

var results = []
for each -N ≤ dx ≤ N:
    for each -N ≤ dy ≤ N:
        for each -N ≤ dz ≤ N:
            if dx + dy + dz = 0:
                results.append(cube_add(center, Cube(dx, dy, dz)))

这种写法能用,但效率有点低。我们遍历了所有的 dz 但是其中只有一个满足 dx + dy + dz = 0 的约束条件。因此,我们直接算出满足约束条件的 dz

var results = []
for each -N ≤ dx ≤ N:
    for each max(-N, -dx-N) ≤ dy ≤ min(N, -dx+N):
        var dz = -dx-dy
        results.append(cube_add(center, Cube(dx, dy, dz)))

上面的循环就只会遍历所需的坐标值。如图所示,每个范围都用一对边来表示。每一条线都对应一个不等式。我们选取满足所有六个不等式的六边形。

交叉范围

如果你想要找到位于交叉范围内的某个六边形,那么在生成六边形列表前你应该先计算出交叉范围。

你既可以把它当成一个代数问题,也可以将其看作一个几何问题。从代数角度考虑,每个范围都会被表示成形如 -N ≤ dx ≤ N 的不等式,我们需要算出这些约束条件的交集。从几何角度考虑,每个区域都是3D空间中的一个立方体,将其映射到平面 x + y + z = 0上可以求得六边形。我们用代数方法来求解。

首先我们将约束条件 -N ≤ dx ≤ N 表示成更通用的形式, xmin ≤ x ≤ xmax,并令 xmin = center.x - Nxmax = center.x + N。类似地,对 yz 坐标系会进行同样的操作,并在上一节的生成代码像下面这样写:

var results = []
for each xmin ≤ x ≤ xmax:
    for each max(ymin, -x-zmax) ≤ y ≤ min(ymax, -x-zmin):
        var z = -x-y
        results.append(Cube(x, y, z))
a ≤ x ≤ bc ≤ x ≤ d 的交集为 max(a, c) ≤ x ≤ min(b, d)。由于六边形的范围可以分别表示为 x, y, z 的范围,因此我们可以独立地计算出 x, y, z 范围的交集,然后再使用嵌套循环来生成交集范围内的六边形列表。对某个六边形区域,我们令 xmin = H.x - Nxmax = H.x + N,对 yz 亦复如是。为了求得两个六边形区域的交集,我们令 xmin = max(H1.x - N, H2.x - N)xmax = min(H1.x + N, H2.x + N),对 yz 亦复如是。在求更多区域的交集时也可以遵循类似的思路。
障碍

如果考虑有障碍物的情况,那么最简单的做法是限制距离的洪水填充算法(广度优先搜索)。参考下图,距离限制当前设置为 4。代码中的 fringes[k] 是一个数组,存放着所有能够在 k 步内到达的六边形。每经过一次主循环 k 值就 +1。

function cube_reachable(start, movement):
    var visited = set()
    add start to visited
    var fringes = []
    fringes.append([start])

    for each 1 < k ≤ movement:
        fringes.append([])
        for each cube in fringes[k-1]:
            for each 0 ≤ dir < 6:
                var neighbor = cube_neighbor(cube, dir)
                if neighbor not in visited, not blocked:
                    add neighbor to visited
                    fringes[k].append(neighbor)

    return visited

限制范围 movement = 4 :

旋转

已知一个六角矢量(由一个六边形坐标指向另外一个六边形坐标),我们想要旋转它求得另外一个不同的六边形。如果我们将旋转角度限制为 1/6 圆周的倍数,那么可以在立方坐标系中轻松地实现这一功能。

顺时针旋转 60°

    [ x,  y,  z]
to  [-z, -x, -y]

逆时针旋转 60°

    [ x,  y,  z]
to  [-y, -z, -x]

你可以在上图中自己验证这些结论:旋转 60°会造成符号反转,坐标本身也会旋转。旋转 120°再次反转回起点时的状态。旋转 180°后符号反转但坐标转回到原位。

你可以将其转换成轴坐标或偏移坐标。你也可以查看 StackExchang 上的这篇讨论来学习别的旋转计算方法。

单环

环的算法主要用于确定某个六边形是否位于一个给定半径的环上,我们还可以计算这个六边形到环心位置的距离,看它是否等于半径 radius。为得到所有满足条件的六边形的列表,可以从环心位置取半径 radius 外的六边形,再沿着环的路径旋转一圈定位其他六边形。

function cube_ring(center, radius):
    var results = []
    # this code doesn't work for radius == 0; can you see why?
    var cube = cube_add(center,
                        cube_scale(cube_direction(4), radius))
    for each 0 ≤ i < 6:
        for each 0 ≤ j < radius:
            results.append(cube)
            cube = cube_neighbor(cube, i)
    return results

作为起点的六边形位于图中大箭头指向的位置。我选取边角4的方向作为起点,你如果选择别的方向也不成问题。在内部一层的循环镇南关, cube 会沿着圆环移动,移动 6 * radius 后它将回到起点位置。

螺旋

一层一层地以螺旋状遍历环形可以填充整个区域的内部空间:

function cube_spiral(center, radius):
    var results = [center]
    for each 1 ≤ k ≤ radius:
        results = results + cube_ring(center, k)
    return results

区域内六边形的个数就是从中心开始一步一步移动的格数;这里的公式能够帮助你求得结果。

这种访问六边形的方式也可以用于计算移动范围。

视野

已知相对位置和距离,如何求某个格子是否对另外一个格子可见,而没有被障碍物遮蔽呢?最简单的做法是绘制两个六边形间的连线,如果连线没有碰触到任何墙壁,就视为互相可见。如下图所示,你可以移动鼠标来观察从中心网格出发的视线。

如果区域很大,这种算法会变得非常低效。但它十分易于实s现,因此我推荐将它作为首先学习的算法。

有许多种不同的方式定义某个位置是否可见。必须要看到另外一个六边形的中心位置吗?还是只要看到一个边角就可以呢?还是遮蔽部分不超过一半就算可见?视野的问题实际上比表明上更加棘手多变。先尝试这种简单的算法,不过它不一定能满足你项目的预期效果,有时候这种简单的算法会产生一些很不合逻辑的结果。

Clark Verbrugge的教程描述了从中心点出发逐步外移的视野算法。Duelo 的项目采用了类似的算法,并且拥有在线 demo 和 github 源码库。我的这篇 2D 游戏视野计算中的算法主要用于多边形物体,当然也包括六边形。如果是网格游戏,roguelike 社区提供了一系列非常好的算法,参看这里这里这里;这些算法有很多都适用于六角网格系统。

从六角网格到像素

如果希望将六角网格转换为像素坐标,那么请跳到本文开头浏览一下有关大小和布局部分的演示图。如果使用的轴坐标,那么可以先观察下图中示意的单位矢量。在下图中,箭头 A→Q 表示的是 q 轴的单位矢量而 A→R 是 r 轴的单位矢量。像素坐标即 q_basis * q + r_basis * r。例如,B 点位于 (1, 1),等于 q 与 r 的单位矢量之和。

如果你使用了矩阵库,那么这只不过是非常简单的矩阵乘法。然而我这里还是先写出一个不使用矩阵的版本。对本文使用的 x = q, z = r 的网格,转换关系为:

function hex_to_pixel(hex):
    x = size * sqrt(3) * (hex.q + hex.r/2)
    y = size * 3/2 * hex.rx = size * 3/2 * hex.q
    y = size * sqrt(3) * (hex.r + hex.q/2)
    return Point(x, y)
轴坐标:

如果使用矩阵算法,在后文进行像素坐标到六角网格坐标转换的时候,会非常方便。我们到时候只需要求逆矩阵就可以了。如果你使用的是立方坐标系统,你可以直接使用立方坐标 (x, y, z),也可以先将其转换为轴坐标,然后使用轴坐标 (q, r)

在偏移坐标中,我们需要偏移行数或列数(这样一来它就不再是整型了)。之后我们可以使用单位矢量 q 和 r,并将其与 x 和 y 轴对齐:

function offset_to_pixel(hex):
    x = size * sqrt(3) * (hex.col + 0.5 * (hex.row&1))
    y = size * 3/2 * hex.rowx = size * sqrt(3) * (hex.col - 0.5 * (hex.row&1))
    y = size * 3/2 * hex.rowx = size * 3/2 * hex.col
    y = size * sqrt(3) * (hex.row + 0.5 * (hex.col&1))x = size * 3/2 * hex.col
    y = size * sqrt(3) * (hex.row - 0.5 * (hex.col&1))
    return Point(x, y)
偏移坐标:

不幸的是,偏移坐标没有可用于矩阵算法的单位矢量。这也是使用偏移坐标时从像素坐标转换成六角网格坐标会更困难的原因所在。

另外一种解决方案是,先将偏移坐标转换为立方坐标或轴坐标,然后再将立方坐标或轴坐标转换成像素坐标。通过内联转换函数来进行优化,最终效果与前面所述的基本上不会有差别。

从像素到六角网格

恐怕这是最普遍的一个问题,如何才能将一个像素位置(比如鼠标点击位置)转换为一个六角网格坐标呢?下面我会演示使用轴坐标或立方坐标时的做法。对偏移坐标来说,最简单的方法是先将其转换为立方坐标,找到结果后再转换回偏移坐标。

  1. 首先我们求六角网格向像素网格转换的拟运算。这会得到一个浮点数六角网格,上图中显示为深蓝色的圆点。
  2. 接着我们找到包含蓝色圆点的六边形,如图以浅蓝色高亮显示。

为了从六角网格坐标转换为像素坐标,我们需要对 q, r 乘以单位矢量来得到 x, y。这实际上是一次矩阵乘法。下面是顶点朝上布局时的公式:

像素坐标到六角坐标的转换十分直观,我们可以使用逆矩阵:

通过上面的公式可以算出浮点轴坐标 q 和 r,而使用 hex_round() 就能将浮点轴坐标转换为整型的轴坐标。

顶点朝上布局的代码如下:

function pixel_to_hex(x, y):
    q = (x * sqrt(3)/3 - y / 3) / size
    r = y * 2/3 / size
    return hex_round(Hex(q, r))

边线朝上布局的代码如下:

function pixel_to_hex(x, y):
    q = x * 2/3 / size
    r = (-x / 3 + sqrt(3)/3 * y) / size
    return hex_round(Hex(q, r))

只需要三行代码就可以将像素坐标转换为轴坐标。如果你使用的是偏移坐标,返回值可以改为 return cube_to_hex(cube_round(Cube(q, -q-r, r)))

还有许多其他将像素坐标转换为六角网格坐标的方法,这里提供我所知的另外一种方法

将坐标圆整到最近的六角网格上

有时我们得到的结果会是一个浮点数立方坐标 (x, y, z),我们想找出它究竟在哪一个六边形网格内。在连线和从六角网格转换像素坐标这两节中我们已经遇到过这种需求。由于将浮点数转换为整型的算法称为圆整,因此我将这种算法命名为立方圆整(cube_round)

在立方坐标中,有约束条件 x + y + z = 0,即使浮点立方坐标也必须满足这个条件。因此,我们可以首先将其圆整到附近的整点坐标 (rx, ry, rz) 上。然而,由于有约束条件 x + y + z = 0,我们无法保证还能满足 rx + ry + rz = 0 在我的算法中,我们会将变化最大的坐标重置为满足约束条件的值。比如,如果 y 的改变量最大,即 abs(ry - y)abs(rx -x) 以及 abs(rz - z) 都大,那么我们会重置 ry = -rx-rz。代码如下:

function cube_round(h):
    var rx = round(h.x)
    var ry = round(h.y)
    var rz = round(h.z)

    var x_diff = abs(rx - h.x)
    var y_diff = abs(ry - h.y)
    var z_diff = abs(rz - h.z)

    if x_diff > y_diff and x_diff > z_diff:
        rx = -ry-rz
    else if y_diff > z_diff:
        ry = -rx-rz
    else:
        rz = -rx-ry

    return Cube(rx, ry, rz)

对非立方坐标系统来说,最简单的做法是先转换为立方坐标系统,使用这个圆整算法,然后再转换回原先的坐标系:

function hex_round(h):
    return cube_to_hex(cube_round(hex_to_cube(h)))

笔记: cube_roundhex_round 都以浮点数坐标为参数,而非整型坐标参数。如果你已经写好了 Cube 与 Hex 的类,它们应该可以用于动态语言,你可以直接传递浮点数参数;如果是强类型的语言,使用 unified number 类型即可。然而,在多数的强类型语言中,最好分不同的类来处理浮点坐标与整点坐标,这样在 cube_round 中会有 FloatCube → Cube,如果需要用到 hex_round,还会有 FloatHex → Hex,可以使用 floatcube_to_floathex 来代替 cube_to_hex。在一些具有参数类型的语言(例如 C++,Haskell中),你可以定义 Cube,T 可以是整数也可以是浮点数。此外,你也可以让 cube_round 接受三个参数,这样就无需为它定义一个新类型了。

轴坐标系统的地图存储

轴坐标系统最惹人抱怨的问题就是,当它使用矩形地图时,会浪费许多存储空间;这可能是偏移坐标系统受欢迎的一个原因。然而,如果使用三角形或者六边形的地图,所有类型的六角网格坐标系统都会浪费一些存储空间,我们完全可以用同一种方法来存储所有这些类型的地图。

形状:

地图存储公式: array[r][q + r/2]

注意,被浪费的存储空间会位于每一行的左侧和右侧(除了菱形地图)。这启发了我们如何进行地图存储:

  1. 忽略这个问题。用 null 初始化数组,或者使用其他能够检测无用储存空间的方法。对多种形状的地图来说这个问题有利有弊,因此不是太值得花功夫来找更加复杂的解决方法。
  2. 使用哈希表而非数组。这样地图什么形状都没关系,哪怕中间包括空洞。当你希望访问六角网格的 q, r 位置时,你实际上访问的是 hash_table(hash(q, r))。将其封装进 grid 类的 getter/setter 中,这样你就可以不用再关心这件事了。
  3. 将行向左滑移,并且使用可变大小的行。在许多语言类型中,2D 数组实际上是数组的数组。因此数组大小不需要保持定长。这样就不用浪费右侧的空间了。此外,如果你数组的开始位置不再每一列的最左侧,也可以移除掉左侧浪费的空间。

如果是任意凸形的地图,你可以额外维护保存第一列格子的数组。当你需要访问位于 q, r 的六边形时,作为替代,你可以访问 array[r][q - first_column[r]]。将其封装进格子的类中,你就不用再关心这个问题。图中的 first_column[r] 显示在每一行的左侧。

如果是固定形状的地图,可以临时计算第一行而不用固定存储在数组中。

  • 对矩形地图,有 first_column[r] == -floor(r/2),而你最终访问的是 array[r][q + r/2],可以证明与转移到偏移网格坐标等价。
  • 对三角形地图,有 first_column[r] == 0,最终访问的是 array[r][q] —— 真方便!如果三角形地图朝向另外一个方向(图中没有显示),则变成 array[r][q+r]
  • 对半径为 N 的六边形地图,当 N = max(abs(x), abs(y), abs(z),有 first_column[r] == -N - min(0, r)。最后你访问的会是 array[r][q + N + min(0, r)]。然而,由于我们可能会把一些 r < 0 的位置作为起点,因此我们也必须偏移行,有 array[r + N][q + N + min(0, r)]
  • 对菱形地图,什么问题都不会有,使用 array[r][q] 即可。

环绕型地图

在某些游戏中你希望能使用有限无界的地图。在方形网格地图中,你既可以只让 x 轴方向形成环形(地图最终近似可以视为球形),也可以让 x 轴和 y 轴都形成环形(地图形状近似甜甜圈)。环绕的方案取决于地图的形状而不是网格的形状。使用偏移坐标时让一个矩形地图呈现环形十分容易。我这里展示的是如何基于立方坐标让一个六边形的地图变得环形无界。

在地图中有六个“镜像”的中心点。当你离开地图后,你可以将当前的位置减掉一个距离你最近的镜像中心距离,直到你重新回到地图上。如下面的演示图所示,尝试从中央的地图离开,观察其中一个镜像,会从相反的一边进入地图。

最简单的实现就是预先算好所有结果。利用查表法,存储好每一个六边形边缘跳出后进入的位置。地图边缘的每一个六边形都会挨着相反边的另外一个格子,从地图一边离开到达的位置恰好和其对称镜像地图中的位置一致。用 M 表示六个镜像中心点,用 L 表示地图上的每一个位置,建立一个表 mirror_table[cube_add(M, L)] = L。当你需要的时候只需找出六边形在对称的镜像地图中的位置,然后用非镜像点将其替换即可。

半径为 N 的六边形地图镜像中心为 Cube(2*N+1, -N, -N-1) 并且它有六个角度位置。

寻路算法

如果你使用的是基于图论的 A* 算法,Dijkstra 算法或 FloydWarshall 算法,那么其实六角网格的寻路与方形网格相比没什么本质差别。有关寻路的算法和实例代码可以参看我的另外一篇教程:寻路指南

如图所示,将鼠标放在对应的网格上就能显示路径。你可以点击和拖拽墙壁瓷砖。

  1. Neighbors 方法。我提供的范例代码中,会调用 graph.neighbors 来得到相邻网格的位置。这个函数可以参看本文关于相邻的章节。抛开这个功能将难以实现寻路算法。
  2. Heuristic 方法。A* 算法的范例代码使用 heuristic 方法来求两个网格间的距离。具体的公式可以参看本文关于距离的章节。

相关文章与资源

读完本教程的朋友可以参考本系列的另外一篇教程:六角网格的实现,包含使用 C++,Java,C#,JavaScript,Haxe 以及 Python 编写的示例代码。

这篇教程的交互部分使用 Haxe 与 Javascript 编码: Cube.hxHex.hxGrid.hxScreenCoordinate.hxui.js 以及用于生成立方坐标与六角坐标转换动画的 cubegrid.js。不过,如果你希望自己编写一套六角网格程序库,我建议你参考我的另外一篇教程:六角网格的实现

目前本教程仍然处于更新之中,未来可能增添的内容列表可以在Trello 上找到。Indienova 译文版也会同步更新。有什么好的建议欢迎反馈或者在评论区留言。

近期点赞的会员

 分享这篇文章

indienova 

indienova - 独立精神 

您可能还会对这些文章感兴趣

参与此文章的讨论

  1. 林可 2016-05-06

    顶技术贴

    • eastecho 2016-05-06

      @林可:沙发被你抢了,不过,此文确实质量很高!

  2. Jerry Zhao 2016-05-06

    这是我在Indienova见过的学术程度最深,文章布局交互性最强的帖子,每一个图都能“玩”。

    • eastecho 2016-05-07

      @Jerry Zhao:后面还有……大量高能来袭……

  3. 浑身难受 2016-05-07

    看到这篇文章时感觉打开了新世界的大门,还没看完就感觉大门已经关上了= =

  4. 高鸣 交典创艺 2016-05-08

    图片全部可互动,太牛了……文章质量越来越高,全是硬货。
    我很喜欢战棋类游戏,也许是受到日式游戏毒害太深,看到六角网格的欧美战棋就觉得很不美观,而且有一种“很复杂”的感觉。
    我觉得棋类游戏在四角和六角网格的选择方面,应该是掺杂了很多具体的技术问题和心理学问题和人文历史问题的综合问题。

    • eastecho 2016-05-09

      @高鸣 交典创艺:基于六边形网格的游戏确实复杂一些,因为共享的边数多,需要考虑的情况也就更多

    • 高鸣 交典创艺 2016-05-10

      @eastecho:后来我又想到一个很核心的区别。六边形各相邻的格子距离相等,导致相邻格子从直觉上感觉是没有区别的。而四边形相邻的格子中对角线格子距离更长,从而让人感觉不同,进而可以产生一些基于对角线的特殊游戏规则和玩法——我觉得这是在做策略游戏时四边形的一大优势,更简化,却更富于变化。

  5. clonal 2016-05-11

    这个是翻译的吧,原贴早看过了。。作者搜集了很多游戏制作的文章

    • craft 2016-05-11

      @clonal:嗯,授权翻译的文章,这里会出全系列的简中版本。

  6. clonal 2016-05-11

    贴上原博主的地址,很多干货
    http://www.redblobgames.com/grids/hexagons/

  7. 至尊小夜猫 2016-05-13

    技术贴顶

  8. 夜神不说话 2016-06-25

    一脸惊恐)卧槽全是干货!

    最近由 夜神不说话 修改于:2016-06-25 15:57:13
  9. lykyyy 2016-07-02

    技术贴顶

  10. Zapper 2016-07-25

    wocao……可以

  11. ChristianTam 2016-08-02

    涨姿势了!

  12. ylsywkd 2016-09-28

    很有用!

  13. arthliant 2017-07-18

    坐标系统-偏移坐标 的后两张图应为:奇数/偶数"列" 而非 奇数/偶数 "行"

  14. 目标xx诺森德 2018-06-14

    如果是立方坐标该怎么存储到数组中呢?现转换成偏移坐标再存储吗?
    或者可以直接用三维数组存储?

  15. Daniel5691 2020-02-21

    大佬!毕设有救了!

  16. 丝缘 2020-02-25

    顶!

  17. Mr.natureQ⭐️ 2020-09-28

    ??? 在六角网格中距离为 1 的相邻六边形在 立方网格 中距离为 2 ??? 这个如何理解

您需要登录或者注册后才能发表评论

登录/注册