Unity中实现合理塔防寻路机制

前言

在一款TD游戏中，最重要的单位就两大类：防御塔（Tower）和敌人单位（Enemy）。在处理敌人单位的AI行为时，最基本也是最重要的就是自动寻路。在各式TD游戏中，防御塔的攻击方式以及敌人单位的Buff机制往往是能做出差异化的地方；而在寻路问题上，几乎是没有差异的，面对的都是同一套问题模型。

以魔兽争霸中的TD地图、KingdomRush为代表的这一类”固定路径，固定塔位“的寻路模型是最为常见的。本文对于寻路问题所参照实现的，则是久负盛名的Defense Grid（中文译名防御阵型）；作为最经典的TD游戏之一，不仅是因为其在早年发布的第一部作品中就表现出了非常优秀3D画面，更重要的是在前述的寻路模式下引入了新的机制：允许在敌人单位的前进路线上放置防御塔或障碍物，从而在运行时动态地改变路径。这一创新极大的提高了可玩性，在此之后许多流行的TD游戏都有使用这种寻路方式例如Infinitode、X-Morph、国产游戏重构Refactor等。

寻路问题的建模

我们首先要做的是根据游戏中的地图特征，将所有能够行走的地面抽象为数据结构，然后再决定合适的寻路算法。

对于路径建模有三种主流方式，我们以下图作为原版地图来说明：

格子（Grid）

格子模型将地图分割为许多大小相等的格子，利用二维数组存储起来。使用各种值表示数组中对应的位置类型如0用来表示障碍物，1表示可行走的区域。

优点：

实现简单
易于在运行时动态修改

缺点：

如果想更为细致地表达路径，则需要将格子分割地更小，从而导致内存占用更大且大范围寻路时计算代价更大

对于2D画面的小地图，是该模型最适合的场景。笔者在刚上大学时写过一个2D的塔防游戏，当时就是以这种方式来处理地图的（https://www.cnblogs.com/geek1116/p/5953456.html）

路径点（WayPoint）

这种方式需要在手动标注出所有可以行走的点，这些点互相连接的直线就是单位行走的路径。通常在这些连接边上还需要带上权重，用邻接表的数据结构存储。

优点：

内存占用小
在此基础上做寻路算法的计算代价小

缺点：

需要人工添加路径点，且在地图变动后都需要再次调整路径点，工作量大
由于单位只能沿着路径点行走，行为方式在观感上会表现的较为生硬，不够灵活；在大地图范围寻路以及需要考虑单位碰撞的场景下，该问题更为明显

对于传统的固定线路的塔防中，WayPoint是非常适合的建模方式

导航网格（NavMesh）

通过一系列的算法将可行走地形转换为由若干凸多边形组成的网格，并维护多边形之间的邻接关系。在导航网格中求两点之间的移动路径，需要根据两点所在的多边形以及多边形之间的邻接关系，按照某种寻路算法找出需要经过的所有多边形；再根据拐点算法计算途中的各个拐点来得出”平滑“的移动路径。

优点：

相比于前两种模型，NavMesh更能表达出地形的特征
适用于3D地形

缺点：

建模过程复杂，自己从零造轮子的话实现成本很大
不便于动态修改；在修改地形后再重新烘焙NavMesh的过程比较耗时，想要运行时执行这一过程的话性能代价较大

Unreal Engine、Unity等游戏引擎中的导航系统内部原理都是基于NavMesh的

寻路算法

三种经典的路径规划算法：

广度优先搜索（BFS）
Dijkstra最短路算法
A*算法（A star）

在游戏开发中实现寻路问题时，A*算法通常是不二之选。这也是Unity中采用的寻路算法。

如果是以WayPoint的方式作地图建模的话，那么数据结构存储的是一个无向加权图，在此之上进行路径规划，Dijkstra算法通常会是一个合适的选择。

在塔防游戏中选择合适的寻路方案

回到我们的主题，要以Defense Grid为蓝本在Unity中实现敌人单位的寻路。

最简单粗暴是使用游戏引擎自带的导航系统，给定一个终点后剩下的都交给导航系统去处理了。这种方式下单位在地图上寻路时所走的都是近似最短路的路线。这种方式不能说是错的，但从游戏设计的角度讲这种表现方式显得”很蠢“：在游戏实际运行中，敌人单位是一波一波出现的，但同一波次中的若干敌人在前进时会显得完全没有”集体意识“，大家都各自为战，最终会挤到同一条直线上。如下所示：