网格沉思——游戏中的网格系统探究

小篱

　　介绍

　　Amit Patel 撰写过一系列有关游戏算法的可交互教程。本文为其六角网格系列中的一篇。

　　引言

　　用网格系统来呈现与区域相关的要素的例子在电子游戏中不胜枚举。

　　具体来说：譬如有文明系列与魔兽争霸系列中的地图；撞球、台球和德州扑克中的游戏界面；一些球类游戏中的交互范围；象棋，大富翁和四联消除游戏中的游戏面板，抑或俄罗斯方块用方格表示的抽象空间。

　　这篇文章里，我将与大家分享一些关于网格系统的思考：我将尽量避免谈及实现细节（这样就可以少来点不易理解的代码），着力表述概念与算法。我曾在策略类游戏和模拟类游戏中实现过基于网格的地图系统，尽管网格系统能够在游戏的诸多方面大显神威，但本文中只涉及我感兴趣的那一部分内容。

　　常见的网格系统

　方格

图1. 方形网格

　　正方形网格自然最为常见。它直观易用，也非常适合显示在计算机屏幕上。当然，使用它最大的好处还在于简单：用轴正交的 (x, y) 坐标系就能表示出每个网格的位置。即使在游戏画面中，网格以等轴斜视的形式呈现，也还是使用相同的坐标轴系统。

　　六角网格

图2. 六角网格

　　有时我们也会使用六角网格（尤其是某些桌面游戏和策略类游戏）。相比正方形网格它有一个明显的优势，由于六角网格对角方向与邻边方向的格子等距，因此不会造成各方向的移动间出现距离偏差。此外，六角网格的样式优雅美观，自然界中的蜂巢就是六角网格的形状。

　　三角网格

图３. 三角网格

　　3d建模中会用到三角网格，但很少有人将它们用于游戏地图：最主要的原因是，这样的网格系统边很多，但每一格面积却很少：而格子过小意味着难以完整地呈现游戏素材。3d建模则主要使用三角网格，这是由于三角网格的每一格能保证处于同一平面中，而正方形网格与六角网格可能会扭曲成自然界不可能出现的样子。为方便计算，本文中涉及到三角网格的数学演绎都默认三角形以某条中垂线竖直的方式放置，对于某条中垂线水平的情况则同理可证。

　　网格的组成要素

图4. 网格的要素　　

　　网格有三大组成要素：面，边与顶点。

　　面是由边围成的闭合平面；边是以顶为端点的线段；顶点则就是零维的点。

　　具体到游戏，则往往只侧重于其中的某一方面：一些西方的游戏，以国际象棋和国际跳棋为例，使用了网格中的面，而一些东方的游戏，例如围棋和跳棋，则使用网格中的顶。而某些游戏，比方说俄罗斯轮盘赌博，则使用了所有这三种要素。

　　面，边与顶也能呈现在多边形地图中。即使没有网格坐标系统，也能对其运用相关的算法：

图4b. 多边形网格依然包含三大要素

　　用节点表示每个面，节点连线表示邻边，我们就能将网格与多边形地图转换为图形拓扑结构。这样一来，一些适用于图的算法（例如最小路径算法）就可以用于网格地图了。

　　游戏中的应用

　　电子游戏对这三种要素都有所应用，其中面的应用最为普遍。

• 面常被用于表示建筑物和地形地块（草地，沙漠，沙砾等等），也经常被用于表示玩家所有的领地范围；
• 边常用来表示领地边境，有时也会用在一些模拟水流，人流和货物运输的算法中；
• 顶常用来表示海拔高度和水深等信息。
  

　　道路与铁路网络有时会使用面来实现（以模拟人生系列游戏为例），有时也会考虑使用边（例如我曾实现过的这个机车系统：Road Building Applet）。

　　相关计算

　　我们来计算一下需要多少面，边与顶点才能构成网格。

　　基本的思路是观察相邻的要素，考虑共用的情况。

　　先来计算相对简单的三角网格（参见图4）相关数据。三角形有三个边，因此，假如不考虑共用的情况，边的数量会是面的三倍，但每条边都会由两个面分享，所以每有三个边就有两个面；同理，三角形的顶点由六个面分享，所以每2个顶点就对应一个面。这些关系在设计坐标系统时非常重要。正方形网格中一个面对应一个顶点。六角网格中顶点则比面多。

　　相关的数据参见下表：

　　为方便起见，我们用 FEV 来表示这组数据。方形网格的 FEV 为 1，2，1；六角网格为 1，3，2；三角网格则为 2，3，1。注意，六角网格与三角网格数据很类似，只是面与顶点的数据是反过来的。这是因为六角网格与三角网格存在对耦关系：如果你在三角网格每个面的中心增加一个顶点就能得到一个六角网格，反之亦然。类似的，我们会发现方形网格与自身对耦。如果在方形网格每个面的中心增加顶点会得到另一个方形网格。相关知识可以参见：http://en.wikipedia.org/wiki/List_of_uniform_planar_tilings

　　六角网格与三角网格的衍生方法

　　可以使用方形网格来衍生六角网格或者三角网格。

　　你可以先尝试一下 demo。

　　方形网格的坐标系统非常直观，而下面的方法则将演示如何设计六角网格与三角网格的坐标轴。

　　用方形网格衍生六角网格

　　将方形网格转换为六角网格需要历经两个步骤：第一步，使方形网格竖直边长度加倍，然后偏移某些列（当然行也可以）；第二步，划分方形网格的边，并将格子变形成六边形。

图5. 方形网格的偏移方法

　　这里给出两种偏移列的方法(参见图5)：比如我们可以用代码来判别列数的奇偶性，遇偶数列就将其向上偏移半格。更简单的方法是让每一列都相比前一列向上偏移半格，这样坐标的计算方法能够相对保持一致，但地图形状会显得没有那么四四方方，略有不便，尽管如此，在本文中我还是选择使用这套方案。它更容易实现，而且也能用于三角网格中（未来也许我也会撰写关于第一种方案实现的教程）。

图5. 方形网格的偏移方法

　　接着，我们将原方形网格竖直方形的边都一分为二，并以分割点为顶点弯折它们。当角度由180度达到120度时我们会得到一个正六边形的网格。这种分割方式会增加两条边（平均到每个面则多了一条边）与两个点（平均到每个面则多了一个点），因此，FEV 由 1，2，1 变为 1，3，2。

　　用方形网格衍生三角网格

图7. 方形网格转换为三角网格

　　将方形网格转换为三角网格也需经历两步：首先，“挤压”方形网格让每个格子变为菱形。接着，将菱形一分为二得到两个三角形，分割面意味着面数会加倍，边数平均到每个面则增加了一条，顶点数没有变化。因此，FEV 由 1，2，1 变为 2，3，1。

　　坐标轴系统

　　我们需要用坐标来表示网格的各个要素。我先使用简单的数字坐标来表示网格的轴，而 FEV 则能告诉我们有多少网格要素会使用相同的坐标表示。如果数　字坐标数字完全相同，为会在后面加上代表方向的字母（W：西；E：东；N：北；S：南；L：左；R：右）作为补充信息。

　　方形网格

图8. 方形网格的坐标系统：面，边与顶点

　　方形网格非常简单，它的 FEV 为 1，2，1，这意味着只有在表示边时才会用到作为补充信息的字母。对于每一个面，我们可以用面的某个顶点坐标来表示它的位置，我选用了西南角的顶点坐标作为面坐标：读者可以对比面坐标图与顶点坐标图来查看它们的关系。而对于每一个边，我们都可以指定用它某一侧的面的坐标来表示它的位置，我选用了西面和南面的边，并分别用字母 W 和字母 S 表示坐标的补充信息：读者也可以对比面坐标图和边坐标图来查看它们的关系。这样下来，有一个面，两条边和一个顶点使用同一坐标数字，恰好对应方形网格的要素向量 FEV。

　　六角网格

图9. 六角网格的坐标系统：面，边与顶点

　　我们的六角网格是基于方形网格创建的。因此六角网格的面坐标同转换前的方形网格保持一致。对比图8与图9你能够看出转换前后的面坐标关系。我们选取三条边与两个顶点与面分享一样的坐标。我选取的是 NW，N，NE 三条边，并分别用 W，N，E 作为坐标补充信息。至于顶点，则使用 L,R 来区分是面左边的顶点还是面右侧的顶点。其他选择方案当然也是可行的。

　　三角网格

图10. 三角网格的坐标系统：面，边与顶点

　　我们的三角网格也是基于方形网格创建的，并且我们把方形网格的面划分为了两个三角网格的面。这意味着我们需要在面坐标后加上 L，R 作为补充信息区别左右两个面。边的坐标与方形网格中保持一致，新增的边则采用左下角的顶点坐标，并用字母 E 作为补充信息。由于三角网格并没有新增顶点，所以顶点坐标与方形网格保持一致即可。

　　网格要素之间的关系

　　三大网格要素两两之间可以建立9组关系。还有许多其他的关系可以建立，但本文中就只研究这9组关系。我不是很熟悉该用什么标准的术语，因此这里可能杜撰了一些名词(译者按，此处的中译也使用的是杜撰的名词，如果有更合适的称呼，烦请读者告知，不胜感激)。

　　算法在游戏设计中，你实际使用的可能是上述变种之一。比方说，接壤与邻点这两种关系也可能会将对角线包含在内。而连续关系也可能涵盖两个边不在一条直线上的情况。我有选择性地列举了最简单的关系。

　　如下表所示，根据我列出的这9种关系，每一种都能够写出一组由某一要素坐标向相邻要素坐标转换的算法关系(A -> B), 我简单地将其表示为了坐标映射关系，方便读者选择用自己喜欢的编程语言来实现它们。由于在某些形状的格子中，被转换的要素可能处于不同的位置（即有多种 A 的情况），因此我将所有可能的类型都列举了出来。例如，三角格子会有居左(L)或者(居右)两种情况：

　　关系对

　　(本节内容可以跳过*)

　　上面列出了网格要素关系自身之间也存在关系。例如，由面到边的围边(borders)关系与由边到面的连接(joins)关系互为逆反。假如边B是面A的一个相邻边，那么面A也是边B的一个相邻面。因此，这9种关系实则可以精简为6种关系对。(*本节内容允许跳过)

　　如果你为这些坐标建立了数据库，则可以直接表示出这些关系对。比如，在1X2的方形网格中，面边坐标关系对如下所示：

　　给定关系对后，查看对应的列即可。比如在上表中，坐标为 (0, 0) 的面对应着4条边，符合围边(border)关系的公式表达的结果。而坐标为 (1, 0, W) 对应2个面，也符合连接(join)关系公式的结果。关系对的含义更宽泛，包含许多种对应关系；而具体到某一种关系，则会有特定的数学表达式。

　　既然有6种关系对，理应有12种关系才对啊，为什么我们只列出了9种关系呢？理由是面/面关系，边/边关系与顶点/顶点关系是对称的，所以其逆反就是本身，因此，12种关系中有三种关系是冗余的，我们一共有9种要素关系。

　　实现

　　上面列出的算法非常直观。那么我们如何在具体的代码中实现它们呢？首先，你需要从三种要素坐标中选出一种来创建数据结构。我推荐选用最为简洁透明的方式。无论哪种要素，我都会使用用整数向量 (u, v) 来表示其坐标，必要时包含L 或者 W 这样的辅助记号。

　　像这样的数据结构，如果用 Ruby 可以表示为附带 public attrs 的类；用 lisp 的话可以表示为 list；若用 C 则struct 正好合用; 使用 Java 则可以表示为包含 public fields 的类；而假如使用的是 Python ，则表示为一个简单的对象或者字典就好。辅助标记的画， lisp 和 Ruby 中可以考虑用 symbol('L/)；C中用字符('L')或者枚举变量(L);Java中用字符ython中则可以用长度为1的字符串。

　　接下来实现我们的算法。最简单的当然是写一个以 A 为参数返回值为 B 的列表的函数（或者方法）。如果 A 的情况不唯一，用 switch/case 分别处理即可。这种方法最简单，但并不是最快的办法。想要进一步优化，还可以考虑在调用时预先分配可能返回的列表，或者提供内联的回调函数（比如 C++ 的 STL 函数对象）。在某些情况下，你可能会需要一次查看多个A对应的关系，这时你可能会需要设计一种能够以A的列表为参数，返回B的列表的算法。

　　我尽量避免给出具体的实现，因为这取决于每个游戏的具体需要，但我还是在下表中列出了使用 ruby 编写的三角网格转换的一种范例。为选择使用 list 作为最基本的数据结构，并且使用 Ruby symbol(:L) 来表示附带记号。

　　就是这么容易。每一个变种使用一种分支情况处理即可。

　　坐标转换

　　无论是 2D 还是 3D 的图形系统，我们都需要在“世界”坐标与“屏幕”坐标间相互转换。使用网格系统后也不例外。这一节我们就来处理这个问题。从网格坐标往世界坐标转换时，我们选取顶点或者面的中心；从世界坐标往网格坐标转换时，我们则选取包含坐标点的面坐标，离坐标点最近的边坐标或顶点坐标。


　　方形网格

　　方形网格的情形比较容易处理。假设方格边长为s，且方格边缘与x, y轴对齐，那么只需要将网格坐标乘以s就能得到对应的世界坐标。

　　如果是其他情况(坐标轴没有与网格对齐)，我们则需要确定哪个顶点是距离世界坐标最近的。只需要将世界坐标除以s再圆整(round)就能得到最近的顶点坐标。若你希望得到的不是顶点坐标而是面坐标，使用向下取整(floor)即可。

　　六角网格

图11. 六角网格度量

　　六角网格的情形只稍微比方形网格复杂一点。计算面心很容易，参见图11，右下角标有矢量i与矢量j。从六角网格坐标向世界坐标转换，只需要做简单的矩阵乘法即可，关系如下：

　　展开后即表示为：

1. x = ix * u + jx * v
   
2. y = iy * u + jy * v

复制代码

　　如图所示，i 即 (hexagon_narrow_width, 0.5*hexagon_height) 而 j 即 (0, hexagon_height), 将其带入公式，结果为：

1. # 面心
   
2. x = hexagon_narrow_width * u
   
3. y = hexagon_height * (u * 0.5 + v)

复制代码

　　计算顶点也相当简单。在下文中，我会用L或R标记六边形的顶点。这两个顶点位于从六边形面心往左或往右横跨半个六边形的宽处（具体可参见图9），因此我们只需要加上或者减去一个 hexagon_wide_width * 0.5就能得到x坐标:

1. # 如果面心坐标为 (x, y), 则顶点坐标为：
   
2. case side
   
3.   when :L
   
4.     x -= hexagon_wide_width * 0.5
   
5.   when :R
   
6.     x += hexagon_wide_width * 0.5
   
7. end

复制代码

　　在处理六角网格时，以面心坐标作为主要坐标，顶点坐标则放在相对次要的位置。

　　从六角网格坐标(u, v)转换为世界坐标(x, y)也需要做一次矩阵乘法（即之前的矩阵乘法的逆运算）。这里我直接给出计算结果：

1. u = x / hexagon_narrow_width
   
2. v = y / hexagon_height - u * 0.5

复制代码

　　要使以上公式成立，需要将(x, y)落在面心位置上。如果(x, y)处于任意位置，还需要一点额外费一点功夫。最简单（但并不是最高效）的方案是算出浮点坐标(u, v)后比较与其相邻的整点坐标，看哪一个距离原来的世界坐标最近。这种方法适用于所有类型的坐标系统。用这种算法来实现鼠标点选，速度是足够满足要求的。通过查找最近的多边形，它还能再进一步地优化。

　　三角网格

　　三角网格是经过挤压和分割的方形网格。

　　将三角网格的顶点坐标转换为世界坐标只需乘上一个轴矢量(即坐标轴的单位向量)，正如六角网格中提到的公式：

　　将三角网格的面坐标转换为世界坐标则需要做一点调整。居于左下，标记为L的三角网格面心为(0.25*i, 0.25*j)，而居于右上，标记为R的三角网格面心则为(0.75*i, 0.75*j)。

　　由世界坐标转换为三角顶点坐标很容易。用代数知识算出(u, v)即可。可以通过划分左右三角网格的边(标注为E的那条)的位置来判断世界坐标落在了哪一个面中。如果点位于边的左侧，则点落在L面中，否则落在R面中。位于R面时，frac(u) + frac(v) >= 0.5将成立，也可以利用这个性质来判断点在哪一侧(译注：frac(...)函数用来可以取得浮点数的小数部分)。

　　处理三角网格时，着重于处理顶点，面心坐标相对次要。这和六角网格中的处理方式恰好相反。

　　相关阅读：即时战略游戏中实用的寻路算法分享

indienova独立精神编译