如果你想要进步，别在意别人觉得你很愚蠢。
郑重说明：本文适合对游戏开发感兴趣的初级及中级开发和学习者，本人力图将技术用简单的语言表达清楚。鉴于水平有限，能力一般，文章如有错漏之处，还望批评指正，谢谢。
在前面一篇 谈一谈游戏AI - 真的搞懂寻路（一） 中我们谈到了一些经典寻路算法，较为常用的算法是 A*。在讲述这些算法时，我们使用的地图都是用简单的格子来表示。实际上，游戏中的地图有很多种不同的表示方式，如网格面的方式、顶点的方式等，不同的表示方式有自己的适用场景和局限性。但是不管如何表示地图，A* 等寻路算法都是可以使用的。
下面我们看看有哪些地图表示方法。
一、2D地图之格子划分（关注可行走区+阻挡）
将地图作为一个整体考虑，可行走区域和阻挡都用格子表示。格子一般有正方形、三角形和六边形。依赖于周围的N个格子来做寻路（如使用A*）。
一般来说，用正方形格子比较简单；
六边形格子的好处是到周围的格子的距离一样，格子看起来比较漂亮，用在很多策略游戏的地图设计中：
如果要用在实际可行走的地图中，六边形的计算坐标和找周边格子则比较复杂，性能没有正方形格子好。有兴趣的可以看看这篇文章：
Implementation of Hex Grids
使用 Grid 的好处是可以更精细的存储信息，例如倾斜度，不同地形，不同寻路消耗，各种标记等等meta信息。
坐标定位快。方便扩展，定制等。
但是高精度的格子和meta信息也意味着大量的内存占用，很多地图较大的 MMO 游戏中，单张地图资源的内存占用就有十几GB、几十GB之多；此外，精度高的时候，格子数量多，这样寻路算法（如A*算法）的性能也会随之下降。
二、2D地图之路点waypoint（关注可行走区）
路点 waypoint 的思路和 Grid 的不太一样，waypoint 只表示可行走的区域，对于寻路不会用到的阻挡区域不去管它。
waypoint 找出地图中的一些关键点，然后将这些关键点连接起来。寻路算法在实施时，关注的是当前关键点周围的关键点。
一张路点的经典图：
它其实非常类似于我们日常生活中的地铁线路图，地铁站就是路点：
找出起点和终点最近的地铁站，剩下的就是按照规划好的路线进行寻路了。
waypoints 的地图表示方法有很多好处很明显：
- 使用 waypoints 可以将游戏地图划分成一些离散的区域，每个区域之间都有一个或多个连接点，这样一来，寻路算法就可以只考虑相邻的 waypoints 之间的连通关系，而不需要考虑地图上的每一个点，这样可以大大简化寻路算法的逻辑，提高寻路效率。
但它也有较大局限性：
- 需要手动标记路点，工作量大
- 由于路点都是一些离散的点，数量有限，规划出的路径有很僵硬的折角，走路不自然，容易走Z型
- 线路固定，不能根据 agent（NPC）的半径做线路调整
waypoints 路点方法在某些特定场合非常好用：
- 一些游戏中的押镖等固定线路玩法
- 塔防类型的固定路线游戏
另外，提一点，waypoints 组成的边可以动态调整，如有个门，可以开关，对应边可以行走和不可行走，这对于可变场景是很方便的。
三、2D地图之多边形可见图（关注阻挡）
将地图场景中所有的阻挡用多边形表达出来，多边形顶点之间是直线
将阻挡多边形化，确定顶点，然后找出顶点之间的连接关系，最后将起点start和终点 end 加进来，一起绘制出可见图。找到的路径可能就像黄色路径所示。
局限性：
- 每次寻路 start 和 end 每次都要在可见图中动态的添加和删除，可见图动态生成的消耗大；
- 如果地图很大，阻挡特别多，这个可见图的形状会特别复杂，因此这种方式对于复杂的地图性能不高（如下图）；
四、2D 地图之navmesh（关注可行走区域）
对于阻挡比较多的情况，我们反过来思考，把上图反过来，不关注阻挡，只关注可行走区域的分割。
前面我们也提到，waypoints 的方式也是只考虑可行走区域，只不过是在可行走区域里找出一些关键点，然后连线做路径。
其实还有一种方法，就是把可行走区域划分成一个个的不规则区块（网格navmesh），例如下图深色部分所示，把可行走区域划分成很多凸多边形：
如果我们用不规则凸多边形的相对中心点来表示这个区块，其实就可以将寻路算法（如A*）应用到区块间的寻路，效果如下：
网格是不重叠的凸多边形，这样任意一个多边形内的两点可以直线到达，而不会穿过别的区块：
如果我们要将前面 waypoints 中的地图用这种网格（navmesh）来重新组织，效果如下：
有时候，单个格子还是显得很大，就可以继续划分，精度提高之后，寻路的路径也就更自然。
4.1 unity中的navmesh寻路
在 Unity 引擎中，可以对一张 2D 地图提前生成好网格，这个过程称为烘焙（bake）：标记待烘焙的场景(Navgation Static) -> 设置参数 -> Bake
在实际使用网格 navmesh 来寻路时，设置寻路agent的目的地即可，agent 会自动根据 bake 好的 navmesh来寻路到目的地：
public class navctl : MonoBehaviour
{
// Start is called before the first frame update
void Start()
{
NavMeshAgent agent = GetComponent();
agent.SetDestination(new Vector3(-31.41f, -0.42f, 0.04f));
}
// Update is called once per frame
void Update()
{
}
}
此外，unity 的 navgation 还支持设置地形的 AreaType，可以配置不同的寻路消耗
4.2 开源 recastnagivation 库
如果想在自己的引擎中编写 navmesh 寻路相关的代码，可以使用经典开源 navmesh 实现：recastnagivation（c++）库，跨平台；作者 Mikko Mononen 曾经是 CryTek 工作室的 AI 工程师，大名鼎鼎的 CryEngine 就都是 Crytek 工作室开发的。众多游戏引擎和 AI 项目的3D寻路都是基于这个库（Unity、Unreal 等）
github.com/recastnavig…
这个开源实现包含了:
- Recast：烘焙(bake)生成navmesh数据
例如，可以将unity中的场景obj文件导出，利用 recast 库API来生成可以供服务器使用的 mesh 二进制数据（可以用官方提供的RecastDemo.exe GUI工具直接从obj文件导出二进制，build->save）
- Detour：用生成的mesh来导航，使用 A* 算法在mesh中寻路
//加载网格数据
m_navMesh = loadAll("navmesh.bin");
m_navQuery->init(m_navMesh, 2048);
//使用MeshQuery对象来寻路
m_navQuery->findNearestPoly(m_spos, m_polyPickExt, &m_filter, &m_startRef, 0);
m_navQuery->findNearestPoly(m_epos, m_polyPickExt, &m_filter, &m_endRef, 0);
m_navQuery->findPath(m_startRef, m_endRef, m_spos, m_epos, &m_filter, m_polys, &m_npolys, MAX_POLYS);
五、3D地图之格子+多层（grid+layer）
我们之前在介绍 2D 地图的格子表示时谈到可以用 Grid 来表示整张地图。Grid 在表示 2D 地图时是没有问题的，但是如果涉及 3D 地形，由于地形往往存在重叠，Grid 就有很大的问题。如：
一种比较自然的思路是采用多层 Grid。示意图如下：
- 2D的格子寻路+多层，行走会判断连通性，同一层可以认为是连通的，只需要判断2D阻挡；
- 如果路径点是不同层，连通性需要在切层处额外增加判断；
通过普通二维 grid（大地）加上多层layer补丁（地上建筑、桥梁等）的形式，是可以表示这些地图结构的。
下面是一个人上桥的行走判断：
但是，经典难题来了：螺旋楼梯怎么处理？楼梯本身就是有重叠的，在不同高度按照我们的约定，应该属于不同的层级，但是切层点应该在哪里？
上图中，从垂直方向看，红色部分和临近的路面所在的网格是相邻的，因此此时根据层级来判断连通性有很大的局限性，在复杂地形中不能得到广泛应用。
六、3D 地图之 navmesh (可行走区域)
前面我们提到，navmesh 在 2D 地图中可以很方便的使用，其实 navmesh 在 3D 地形中也是适用的。
去掉场景内的阻挡物，只建模可行走区域。下面是unity中的navmesh示例
在前面我们讲过的会重叠的 3D 桥用 navmesh 表示如下：
navmesh寻路时，在通过A*算法找到一系列连通的polygon之后，可以选择polygon的顶点或者中心点来找到路径点，连接起来后就是最终的路径。此外，也会做一些优化，比如两两相邻线段是否可以拉直合并成一条直线。
navmesh寻路看起来非常有效，但是也有很大的局限性：
- 地图建模复杂：Navmesh 寻路需要将地图划分成多网格，因此需要进行复杂的地图建模工作。如果地图结构复杂，建模工作量大，会影响开发效率。
- 因为涉及几何体，可能会有浮点数的计划，消耗大；
- 非贴地寻路(轻功)没法支持，只能沿着生成好的mesh来贴地寻路；
- 地形的定制性差
七、3D地图之体素voxel（可行走区）
voxel最开始由天涯明月刀项目在2014年引入，用于场景的碰撞计算。
7.1 体素表达
类似2D地图中用格子来做像素化(pixel)，3D世界中模型可以体素化。
实际在生成体素的时候，从每个格子的最低层向上做投影，就会产生多层的分割。举个例子，一间房子的投影：
上层为屋顶，人可以通过门从室外走入室内。在垂直方向，最下面为第0层，代表地表，往上依次为1、2层...
每一层会记录上下沿的高度值，行走时 agent 就在各个layer的上沿。
类似的，下面是一个桥的体素剖面图：
相邻的两个grid，其层id可能不同，这和之前 grid + layer 的表达方式不同，同一id层的grid不一定连通（比如高度相差很大），不同层的grid却可能连通。
下面是一个实际场景的体素化视图（场景很大，需要分割，只显示其中一块的体素效果）
7.2 碰撞/连通检测算法
从voxel A (x + y + layer) 是否能走到 voxel B(x + y + layer)，会进行如下判断：
对于轻功飞行，是不在各个layer的上沿的，会在solid层之间的空间移动，从 voxel A(x + y + z + layer)飞行到 voxel B(x + y + z + layer) 进行如下判断：
检测示例：
体素的特点有：
- 对CPU计算友好，没有浮点运算
- 资源描述与2D的格子接近，可以用规格化的数组表述，每个grid 需要存储垂直投影的多个 layer
- 资源格式自定义，可以存储很多的meta信息，例如是否是水，寻路消耗等，可以自由扩展以实现不同的需求
- 内存占用较高，如果是非常大的地图，一张地图内存占用会很大。
八、3D地图之八叉树
在一些可飞行的星际类型的游戏中，往往有很多飞行的路径。此时可以考虑使用八叉树来表示 3D 空间。
在考虑飞行时，八叉树可以用来检测碰撞：
具体的，笔者研究不多，这里只做抛砖引玉，留待读者自己继续深入学习。
小结
在本文中，我们谈到了地图中常用的表示方式，涉及：
- 2D 和 3D 游戏中地图表达，如 grid、waypoints、navmesh、体素等；
- 不同地图表示方法的优缺点和适用场景；
参考文献：
Map representations
现代游戏引擎 - 基础AI
希望本文对大家有所帮助！
作者：我是码财小子，会点编程代码，懂些投资理财；期待你的关注，不要错过我后续的文章更新。
